前言

现有研究使用的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:

  1. 计算stack traces中每个frameweight,原因:不同的帧对stack traces similarity的影响不一样
  2. 计算两个stack tracesedit distance这个距离在论文中被定义为带帧权重的Levenshtein distance
  3. 将计算所得的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 traceframe的位置
  • frame在数据库中所有frames(all frames of all stack traces)中出现的频率

fif_{i}表示一个stack的第i帧,整个stack trace的所有帧表示为: ST=f0,,fN1S T=f_{0}, \ldots, f_{N-1}

fif_{i}总权值计算公式如下:

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)

lwα(fi)l \mathbf{w}_{\alpha}\left(f_{i}\right)fif_{i}的本地权值,对应第一个因素

gwβγ(fi)\operatorname{gw}_{\beta \gamma}\left(f_{i}\right)fif_{i}的全局权值,对应第二个因素

$\alpha \beta \gamma $是数值超参数,用于调整模型以适应数据(调整算法适应某个特定的stack trace集)

本地权值的计算公式:

lwα(fi)=1iα\mathit{lw}_{\alpha}\left(f_{i}\right)=\frac{1}{i^{\alpha}}

靠近栈顶的frame的本地权值更大。这是基于实践得出的结论;错误更有可能是由最近调用的方法所导致的

这里的本地权值是一个完全基于上面这条假设而来的因子,在我看来这条假设非常具有局限性,甚至在某些场景下它就是错的,所以我们可以用一些其它的因子来替代它

这里我拿我的另一个项目whosbug[ 1 ]举例,我们可以基于whosbug获取到一个堆栈中各帧的责任分布(可以简单的理解为堆栈内各帧对这次crashcontribution);于是这里我们就可以用这个责任分布来作为各帧的本地权值了

小小宣传一下我的个人项目嘿嘿

全局权值的计算:

全局权值计算基于TF-IDF方法

TF-IDF方法的基本定义:TF(fi)IDF(fi)\mathit{TF}\left(f_{i}\right) * \mathit{IDF}\left(f_{i}\right)

TF(f)\mathit{TF}\left(f\right)表示特定帧在整个stack trace中的重要程度

IDF(f)\mathit{IDF}\left(f\right)表示frame f在所有stack traces中的罕见程度

在本篇论文中,不使用TF-IDF方法的TF部分,并认为它等于1(实际落地时可根据使用场景自行发挥,这里不做阐述),在计算lwα(fi)\mathit{lw}_{\alpha}\left(f_{i}\right)时,已经考虑过了frame的顺序问题

IDF(fi)\operatorname{IDF}\left(f_{i}\right)计算公式:

IDF(fi)=log Total num. of stack traces  Num. of stack traces ST:fiST\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}

gwβγ(fi)\operatorname{gw}_{\beta \gamma}\left(f_{i}\right)计算公式:

gwβγ(fi)=σ(β(IDF(fi)γ))σ(x)=11+ex\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}}

其中$\beta \gamma超参数是为了保证\operatorname{IDF}\left(f_{i}\right)$的曲线比较平滑

这样的算法能保证赋予大量stack traces中那些非常相似的frames以小的权值;这类frames可能是频繁调用的代码块,例如开发框架,日志或者协程池

Levenshtein distance 计算

为了在数值上表达stack traces之间的差异,论文中使用了改进版的Levenshtein distance

我们考虑了经典Levenshtein distance中的插入、删除、替换操作,没有考虑调换操作,因为framesstack trace中的顺序是具有实际意义的;在一个stack trace中移动两个frames是不被允许的

对于两个字符串,经典Levenshtein distance被定义为最少的编辑开销,即将一个字符串变成另一个字符串所需要的最少的插入、删除、替换单个字符次数

对于两个stack trace,也用一样的方法,但这里我们使用上面提到的帧权值

插入、删除的开销即相对应的frame的权值

替换的开销是替换前frame和替换后新frame的权值的总和

对两个分别长m和长n的堆栈STSTS T^{\prime}和 S T^{\prime \prime},我们定义dist(ST,ST)\operatorname{\mathit{dist}}\left(S T^{\prime}, S T^{\prime \prime}\right)ST,STS T^{\prime}, S T^{\prime \prime}Levenshtein distance;定义长mn的矩阵 D\mathit{D} ,其中Di,j\mathit{D}_{i,j}STS T^{\prime}的前i帧到STS T^{\prime \prime}的前j帧的Levenshtein distancefif_iSTS T^{\prime}的第i帧,fjf_jSTS T^{\prime \prime}的第j帧,wiw_iSTS T^{\prime}中第i帧的帧权值,wjw_jSTS T^{\prime \prime}中第j帧的帧权值

则我们可以得到状态转移方程为:

Di,j={Di1,j1fi=fjmin(Di,j1+wj, Di1,j+wi, Di1,j1+wi+wj)fifj\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}

并且在D\mathit{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}

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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(归一化)

相似度归一化后即为:

sim(ST,ST)=1dist(ST,ST)i=0N1w(fi)+i=0N1w(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)}

这里dist(ST,ST)\operatorname{\mathit{dist}}\left(S T^{\prime}, S T^{\prime \prime}\right)ST,STS T^{\prime}, S T^{\prime \prime}Levenshtein distance,但也可以替换为rebucket中定义的distance,关于堆栈间距离的定义还有很多,都可以尝试做替换;具体效果还需要落地后观察

总结:

  • 本篇论文核心还是依据特定规则(帧到栈顶的距离,帧在stack trace中的出现次数)来进行归类。
  • 从结果上看,TraceSim算法在Jetbrain product中的效果比其他现有算法要好(但也局限于这一个项目,在我看来每一个项目的堆栈特征都不同,对应的超参数组合也不同,实际效果是会存在差异的)
  • TraceSim算法中的很多部分是可以尝试基于其它算法进行优化的