TraceSim算法深入浅出
前言
现有研究使用的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)
中出现的频率
stack
的第i
帧,整个stack trace
的所有帧表示为:
则
本地权值的计算公式:
靠近栈顶的frame
的本地权值更大。这是基于实践得出的结论;错误更有可能是由最近调用的方法所导致的
这里的本地权值是一个完全基于上面这条假设而来的因子,在一些场景下这样的假设比较局限
全局权值的计算:
全局权值计算基于TF-IDF
方法
TF-IDF
方法的基本定义:
stack trace
中的重要程度
frame f
在所有stack traces
中的罕见程度
在本篇论文中,不使用TF-IDF方法的TF部分,并认为它等于1(实际落地时可根据使用场景自行发挥,这里不做阐述),在计算frame
的顺序问题
这里提一下我的另一个项目whosbug
[ 1 ],我们可以基于whosbug
获取到一个堆栈中各帧的责任分布(可以简单的理解为堆栈内各帧对这次crash
的contribution
);于是这里我们就可以用这个责任分布来作为各帧的TF
了
其中
这样的算法能保证赋予大量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
的堆栈Levenshtein distance
;定义长m
宽n
的矩阵i
帧到j
帧的Levenshtein distance
,i
帧,j
帧,i
帧的帧权值,j
帧的帧权值
则我们可以得到状态转移方程为:
并且在
代码如下:
1 | def _dist(trace1: List, weights1: List, trace2: List, weights2: List) -> float: |
Normalization(归一化)
相似度归一化后即为:
这里Levenshtein distance
,但也可以替换为rebucket
中定义的distance
,关于堆栈间距离的定义还有很多,都可以尝试做替换;具体效果还需要落地后观察
总结:
- 本篇论文核心还是依据特定规则(帧到栈顶的距离,帧在
stack trace
中的出现次数)来进行归类。 - 从结果上看,
TraceSim
算法在Jetbrain product
中的效果比其他现有算法要好(但也局限于这一个项目,在我看来每一个项目的堆栈特征都不同,对应的超参数组合也不同,实际效果是会存在差异的) TraceSim
算法中的很多部分是可以尝试基于其它算法进行优化的