现有研究使用的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
代表单帧的罕见程度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
质量),并可能优于任何单独的一种方法
算法流程大致如下:
特殊处理栈溢出异常,而对于非SOEs:
stack traces
中每个frame
的weight
,原因:不同的帧对stack traces similarity
的影响不一样stack traces
的edit distance
这个距离在论文中被定义为带帧权重的Levenshtein distance
Levenshtein distance
规范化,作为最终两个堆栈间距离的度量值算法细节在下方展开阐述
stack overflow exceptions
中有大量重复的递归调用产生的帧,两个stack traces
的这部分如果相似,则他们很可能指向相同的错误情况;递归部分通常占这类堆栈的很大一部分,所以按照帧频次计算他们的相似性就足够了
这里我们基于一个基本的假设:靠近栈顶的frames
的影响比更深层的frames
大,因为上层frames
更有可能包含bug
源
对于上述结论,我们用frame weight
反映;frame weight
越高,影响越大
frame weigth
的影响因素:
Stack trace
中frame
的位置frame
在数据库中所有frames(all frames of all stack traces)
中出现的频率fif_{i}fi表示一个stack
的第i
帧,整个stack trace
的所有帧表示为:ST=f0,…,fN−1S T=f_{0}, \ldots, f_{N-1}ST=f0,…,fN−1
则fif_{i}fi的总权值计算公式如下:
w(fi)=lwα(fi)∗gwβγ(fi)\mathit{w}\left(f_{i}\right)=\mathit{lw}_{\alpha}\left(f_{i}\right) * \mathit{gw}_{\beta \gamma}\left(f_{i}\right)w(fi)=lwα(fi)∗gwβγ(fi)
lwα(fi)l \mathbf{w}_{\alpha}\left(f_{i}\right)lwα(fi)是fif_{i}fi的本地权值,对应第一个因素
gwβγ(fi)\operatorname{gw}_{\beta \gamma}\left(f_{i}\right)gwβγ(fi)是fif_{i}fi的全局权值,对应第二个因素
\alpha \beta \gamma 是数值超参数,用于调整模型以适应数据(调整算法适应某个特定的stack trace集)
本地权值的计算公式:
lwα(fi)=1iα\mathit{lw}_{\alpha}\left(f_{i}\right)=\frac{1}{i^{\alpha}}lwα(fi)=iα1
靠近栈顶的frame
的本地权值更大。这是基于实践得出的结论;错误更有可能是由最近调用的方法所导致的
这里的本地权值是一个完全基于上面这条假设而来的因子,在一些场景下这样的假设比较局限
全局权值的计算:
全局权值计算基于TF-IDF
方法
TF-IDF
方法的基本定义:TF(fi)∗IDF(fi)\mathit{TF}\left(f_{i}\right) * \mathit{IDF}\left(f_{i}\right)TF(fi)∗IDF(fi)
TF(f)\mathit{TF}\left(f\right)TF(f)表示特定帧在整个stack trace
中的重要程度
IDF(f)\mathit{IDF}\left(f\right)IDF(f)表示frame f
在所有stack traces
中的罕见程度
在本篇论文中,不使用TF-IDF方法的TF部分,并认为它等于1(实际落地时可根据使用场景自行发挥,这里不做阐述),在计算lwα(fi)\mathit{lw}_{\alpha}\left(f_{i}\right)lwα(fi)时,已经考虑过了frame
的顺序问题
这里提一下我的另一个项目whosbug
[ 1 ],我们可以基于whosbug
获取到一个堆栈中各帧的责任分布(可以简单的理解为堆栈内各帧对这次crash
的contribution
);于是这里我们就可以用这个责任分布来作为各帧的TF
了
IDF(fi)\operatorname{IDF}\left(f_{i}\right)IDF(fi)计算公式:
IDF(fi)=log Total num. of stack traces Num. of stack traces ST:fi∈ST\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}IDF(fi)=log Num. of stack traces ST:fi∈ST Total num. of stack traces
gwβγ(fi)\operatorname{gw}_{\beta \gamma}\left(f_{i}\right)gwβγ(fi)计算公式:
gwβγ(fi)=σ(β(IDF(fi)−γ))σ(x)=11+e−x\mathit{gw}_{\beta \gamma}\left(f_{i}\right)=\sigma\left(\beta\left(\operatorname{IDF}\left(f_{i}\right)-\gamma\right)\right) \\ \sigma(x)=\frac{1}{1+e^{-x}}gwβγ(fi)=σ(β(IDF(fi)−γ))σ(x)=1+e−x1
其中β\betaβ,γ\gammaγ超参数是为了保证IDF(fi)\operatorname{IDF}\left(f_{i}\right)IDF(fi)的曲线比较平滑
这样的算法能保证赋予大量stack traces
中那些非常相似的frames
以小的权值;这类frames
可能是频繁调用的代码块,例如开发框架,日志或者协程池
为了在数值上表达stack traces
之间的差异,论文中使用了改进版的Levenshtein distance
我们考虑了经典Levenshtein distance
中的插入、删除、替换操作,没有考虑调换操作,因为frames
在stack trace
中的顺序是具有实际意义的;在一个stack trace
中移动两个frames
是不被允许的
对于两个字符串,经典Levenshtein distance
被定义为最少的编辑开销,即将一个字符串变成另一个字符串所需要的最少的插入、删除、替换单个字符次数
对于两个stack trace
,也用一样的方法,但这里我们使用上面提到的帧权值
插入、删除的开销即相对应的frame
的权值
替换的开销是替换前frame
和替换后新frame
的权值的总和
对两个分别长m
和长n
的堆栈ST′和ST′′S T^{\prime}和 S T^{\prime \prime}ST′和ST′′,我们定义dist(ST′,ST′′)\operatorname{\mathit{dist}}\left(S T^{\prime}, S T^{\prime \prime}\right)dist(ST′,ST′′)为ST′,ST′′S T^{\prime}, S T^{\prime \prime}ST′,ST′′的Levenshtein distance
;定义长m
宽n
的矩阵D\mathit{D}D ,其中Di,j\mathit{D}_{i,j}Di,j为ST′S T^{\prime}ST′的前i
帧到ST′′S T^{\prime \prime}ST′′的前j
帧的Levenshtein distance
,fif_ifi为ST′S T^{\prime}ST′的第i
帧,fjf_jfj为ST′′S T^{\prime \prime}ST′′的第j
帧,wiw_iwi为ST′S T^{\prime}ST′中第i
帧的帧权值,wjw_jwj为ST′′S T^{\prime \prime}ST′′中第j
帧的帧权值
则我们可以得到状态转移方程为:
Di,j={Di−1,j−1fi=fjmin(Di,j−1+wj, Di−1,j+wi, Di−1,j−1+wi+wj)fi≠fj\mathit{D}_{i,j}= \begin{cases} \mathit{D}_{i-1, j-1} &f_i = f_j \\ \min \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}_j \right) &f_i \not= f_j \end{cases}Di,j={Di−1,j−1min(Di,j−1+wj, Di−1,j+wi, Di−1,j−1+wi+wj)fi=fjfi=fj
并且在D\mathit{D}D中:
D0,0=0D0,j=wjDi,0=wi\begin{array}{lcl} \mathit{D}_{0,0} = 0 \\ \mathit{D}_{0, j} = \mathit{w}_j \\ \mathit{D}_{i, 0} = \mathit{w}_i \end{array}D0,0=0D0,j=wjDi,0=wi
代码如下:
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]
相似度归一化后即为:
sim(ST′,ST′′)=1−dist(ST′,ST′′)∑i=0N′−1w(fi′)+∑i=0N′′−1w(fi′′)\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)}sim(ST′,ST′′)=1−∑i=0N′−1w(fi′)+∑i=0N′′−1w(fi′′)dist(ST′,ST′′)
这里dist(ST′,ST′′)\operatorname{\mathit{dist}}\left(S T^{\prime}, S T^{\prime \prime}\right)dist(ST′,ST′′)为ST′,ST′′S T^{\prime}, S T^{\prime \prime}ST′,ST′′的Levenshtein distance
,但也可以替换为rebucket
中定义的distance
,关于堆栈间距离的定义还有很多,都可以尝试做替换;具体效果还需要落地后观察
总结:
stack trace
中的出现次数)来进行归类。TraceSim
算法在Jetbrain product
中的效果比其他现有算法要好(但也局限于这一个项目,在我看来每一个项目的堆栈特征都不同,对应的超参数组合也不同,实际效果是会存在差异的)TraceSim
算法中的很多部分是可以尝试基于其它算法进行优化的