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：

1. 计算stack traces中每个frame的weight，原因：不同的帧对stack traces similarity的影响不一样
2. 计算两个stack traces的edit 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 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(f\right)$表示特定帧在整个stack trace中的重要程度

$\mathit{IDF}\left(f\right)$表示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)=\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中的插入、删除、替换操作，没有考虑调换操作，因为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

\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}

$$

并且在$\mathit{D}$中:

$$

\begin{array}{lcl}

\mathit{D}_{0,0} = 0 \\

\mathit{D}_{0, j} = \mathit{w}_j \\

\mathit{D}_{i, 0} = \mathit{w}_i

\end{array}

$$

代码如下：

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算法中的很多部分是可以尝试基于其它算法进行优化的