前言
现有研究使用的stack trace距离度量主要有以下两种：
information retrieval techniques(基于信息检索技术)string matching methods(基于字符串匹配技术)
Rebucket就是string matching methods的一种，这篇论文主要提出了TraceSim这一结合了两种方法的堆栈相似度度量方法
需要了解的词
Levenshtein Distance Calculation: 基于string matching methods的一种堆栈间距离的度量算法（本文中的Levenshtein Distance Calculation是其改进版本，下面会展开讲）TF-IDF: 基于information retrieval techniques的一种堆栈间距离的度量算法，其中TF代表单帧的重要程度，IDF代表单帧的罕见程度
TraceSim
a novel approach to this problem which combines TF-IDF, Levenshtein distance, and machine learning to construct a similarity metric
the first algorithm for computing stack trace similarity that structurally combines TF-IDF and string distance while using machine learning to improve quality.
论文的主要内容是基于TF-IDF, Levenshtein Distance Calculation结合 machine learning 来构建stack trace之间相似度的度量，相比于单纯的string matching methods（如Rebucket），这样的结合可能可以保证每个bucket内的堆栈关联更加紧密（更好的bucket质量），并可能优于任何单独的一种方法
- TF-IDF(具体算法是改进版的Campbell et al.)
- Levenshtein distance(同样也是改进版本的Levenshtein distance)
- Machine Learning(本文中具体是指基于超参数[ 1, 2, 3 ]确定最佳参数集合用于权重计算)
算法流程大致如下：
特殊处理栈溢出异常，而对于非SOEs：
- 计算
stack traces中每个frame的weight，原因：不同的帧对stack traces similarity的影响不一样 - 计算两个
stack traces的edit distance这个距离在论文中被定义为带帧权重的Levenshtein distance - 将计算所得的
Levenshtein distance规范化，作为最终两个堆栈间距离的度量值
算法细节在下方展开阐述
对SOEs(stack overflow exceptions)的特殊处理
stack overflow exceptions中有大量重复的递归调用产生的帧，两个stack traces的这部分如果相似，则他们很可能指向相同的错误情况；递归部分通常占这类堆栈的很大一部分，所以按照帧频次计算他们的相似性就足够了
帧权值计算（Frame Weight Computation）
这里我们基于一个基本的假设：靠近栈顶的frames的影响比更深层的frames大，因为上层frames更有可能包含bug源
对于上述结论，我们用frame weight反映；frame weight越高，影响越大
frame weigth的影响因素：
Stack trace中frame的位置frame在数据库中所有frames（all frames of all stack traces）中出现的频率
$f{i}$表示一个stack的第i帧，整个stack trace的所有帧表示为: $S T=f{0}, ldots, f_{N-1}$
则$f_{i}$的总权值计算公式如下：
$$
mathit{w}left(f{i}right)=mathit{lw}{alpha}left(f{i}right) * mathit{gw}{beta gamma}left(f_{i}right)
$$
$l mathbf{w}{alpha}left(f{i}right)$是$f_{i}$的本地权值，对应第一个因素
$operatorname{gw}{beta gamma}left(f{i}right)$是$f_{i}$的全局权值，对应第二个因素
$alpha beta gamma $是数值超参数，用于调整模型以适应数据（调整算法适应某个特定的stack trace集）
本地权值的计算公式：
$$
mathit{lw}{alpha}left(f{i}right)=frac{1}{i^{alpha}}
$$
靠近栈顶的frame的本地权值更大。这是基于实践得出的结论；错误更有可能是由最近调用的方法所导致的
这里的本地权值是一个完全基于上面这条假设而来的因子，在一些场景下这样的假设比较局限
全局权值的计算：
全局权值计算基于TF-IDF方法
TF-IDF方法的基本定义：$mathit{TF}left(f{i}right) * mathit{IDF}left(f{i}right)$
$mathit{TF}left(fright)$表示特定帧在整个stack trace中的重要程度
$mathit{IDF}left(fright)$表示frame f在所有stack traces中的罕见程度
在本篇论文中，不使用TF-IDF方法的TF部分，并认为它等于1（实际落地时可根据使用场景自行发挥，这里不做阐述），在计算$mathit{lw}{alpha}left(f{i}right)$时，已经考虑过了frame的顺序问题
这里提一下我的另一个项目whosbug[ 1 ]，我们可以基于whosbug获取到一个堆栈中各帧的责任分布（可以简单的理解为堆栈内各帧对这次crash的contribution）；于是这里我们就可以用这个责任分布来作为各帧的TF了
$operatorname{IDF}left(f_{i}right)$计算公式：
$$
mathit{IDF}left(f{i}right)=log frac{text { Total num. of stack traces }}{text { Num. of stack traces } S T: f{i} in S T}
$$
$operatorname{gw}{beta gamma}left(f{i}right)$计算公式：
$$
mathit{gw}{beta gamma}left(f{i}right)=sigmaleft(betaleft(operatorname{IDF}left(f_{i}right)-gammaright)right)
sigma(x)=frac{1}{1 e^{-x}}
$$
其中$beta$, $gamma$超参数是为了保证$operatorname{IDF}left(f_{i}right)$的曲线比较平滑
这样的算法能保证赋予大量stack traces中那些非常相似的frames以小的权值；这类frames可能是频繁调用的代码块，例如开发框架，日志或者协程池
Levenshtein distance 计算
为了在数值上表达stack traces之间的差异，论文中使用了改进版的Levenshtein distance
我们考虑了经典Levenshtein distance中的插入、删除、替换操作，没有考虑调换操作，因为frames在stack trace中的顺序是具有实际意义的；在一个stack trace中移动两个frames是不被允许的
对于两个字符串，经典Levenshtein distance被定义为最少的编辑开销，即将一个字符串变成另一个字符串所需要的最少的插入、删除、替换单个字符次数
对于两个stack trace，也用一样的方法，但这里我们使用上面提到的帧权值
插入、删除的开销即相对应的frame的权值
替换的开销是替换前frame和替换后新frame的权值的总和
对两个分别长m和长n的堆栈$S T^{prime}和 S T^{prime prime}$，我们定义$operatorname{mathit{dist}}left(S T^{prime}, S T^{prime prime}right)$为$S T^{prime}, S T^{prime prime}$的Levenshtein distance；定义长m宽n的矩阵 $mathit{D}$ ，其中$mathit{D}_{i,j}$为$S T^{prime}$的前i帧到$S T^{prime prime}$的前j帧的Levenshtein distance，$f_i$为$S T^{prime}$的第i帧，$f_j$为$S T^{prime prime}$的第j帧，$w_i$为$S T^{prime}$中第i帧的帧权值，$w_j$为$S T^{prime prime}$中第j帧的帧权值
则我们可以得到状态转移方程为：
$$
mathit{D}_{i,j}=
begin{cases}
mathit{D}_{i-1, j-1} &f_i = f_j
min
代码语言：txt复制left( mathit{D}_{i, j-1} mathit{w}_j, mathit{D}_{i-1, j} mathit{w}_i, mathit{D}_{i-1, j-1} mathit{w}_i mathit{w}_jright) &f_i not= f_jend{cases}
$$
并且在$mathit{D}$中:
$$
begin{array}{lcl}
代码语言：txt复制mathit{D}_{0,0} = 0 \mathit{D}_{0, j} = mathit{w}_j \mathit{D}_{i, 0} = mathit{w}_iend{array}
$$
代码如下：
代码语言：python代码运行次数：0复制def _dist(trace1: List, weights1: List, trace2: List, weights2: List) -> float:
matrix = [[0.0 for _ in range(len(trace1) 1)] for _ in range(len(trace2) 1)]
prev_column = matrix[0]
for i in range(len(trace1)):
prev_column[i 1] = prev_column[i] weights1[i]
if len(trace1) == 0 or len(trace2) == 0:
return 0.0
curr_column = matrix[1]
for i2 in range(len(trace2)):
frame2 = trace2[i2]
weight2 = weights2[i2]
curr_column[0] = prev_column[0] weight2
for i1 in range(len(trace1)):
frame1 = trace1[i1]
weight1 = weights1[i1]
if frame1 == frame2:
curr_column[i1 1] = prev_column[i1]
else:
change = weight1 weight2 prev_column[i1]
remove = weight2 prev_column[i1 1]
insert = weight1 curr_column[i1]
curr_column[i1 1] = min(change, remove, insert)
if i2 != len(trace2) - 1:
prev_column = curr_column
curr_column = matrix[i2 1]
return curr_column[-1]Normalization（归一化）
相似度归一化后即为：
$$
operatorname{mathit{sim}}left(S T^{prime}, S T^{prime prime}right)=1-frac{operatorname{mathit{dist}}left(S T^{prime}, S T^{prime prime}right)}{sum{i=0}^{N^{prime}-1} mathit{w}left(f{i}^{prime}right) sum{i=0}^{N^{prime prime}-1} mathit{w}left(f{i}^{prime prime}right)}
$$
这里$operatorname{mathit{dist}}left(S T^{prime}, S T^{prime prime}right)$为$S T^{prime}, S T^{prime prime}$的Levenshtein distance，但也可以替换为rebucket中定义的distance，关于堆栈间距离的定义还有很多，都可以尝试做替换；具体效果还需要落地后观察
总结：
- 本篇论文核心还是依据特定规则（帧到栈顶的距离，帧在
stack trace中的出现次数）来进行归类。 - 从结果上看，
TraceSim算法在Jetbrain product中的效果比其他现有算法要好（但也局限于这一个项目，在我看来每一个项目的堆栈特征都不同，对应的超参数组合也不同，实际效果是会存在差异的） TraceSim算法中的很多部分是可以尝试基于其它算法进行优化的
