ReBucket算法总结

前言

这次接触ReBucket算法是在实际需求中需要完成一个落地的相关功能模块，也算是少有的复现论文到落地项目的功能模块的机会了，这里做一下算法本身的总结，有关的实现后续会放在另一篇文章中

几个需要了解的词

• PDM：位置相关模型（Position Dependent Model）
• 并查集：一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题
• 层次聚类方法：一种自底向上的聚类方法（类似并查集，从每个元素都属于自己的集群开始）
• WER：Windows Error Reporting，微软部署的一套用于及时告警的分布式系统
• Grid Search：一项模型超参数（需要人工选择的参数）优化技术，常用于优化三个或者更少数量的超参数，本质是一种穷举法

背景

尽管在日常的开发工作中，开发团队已经在发布产品前花费大量资源和精力进行软件测试，但实际上，已发布的软件仍然有一些错误，而这些错误往往表现为release版本运行时崩溃

针对这个现象，微软部署了一套分布式系统WER（Windows Error Reporting）用于自动从崩溃现场收集崩溃信息、聚类到各个Bucket，当某个Bucket内的崩溃次数达到某个阈值后，WER会自动为其生成错误报告，并将其提供给开发人员；WER已经在运行的十几年内证明了其价值，收集了数十亿词崩溃报告，大大加快了开发人员的Debug流程，但另一方面，WER也仍存在一些问题，如“第二个Bucket问题”以及“长尾巴”问题（见下图）

ReBucket算法就是为了解决这些已知问题而产生的一种堆栈聚类算法

算法流程及逻辑

整体结构

在ReBucket算法中，对于一系列新到达的崩溃信息（一个时间片内到达的崩溃信息），首先我们对其进行预处理，以提取简化的堆栈信息。然后使用层次聚类方法将崩溃报告聚类到相应的Bucket内；同时可以使用历史Bucket数据构建的训练模型训练在PDM中使用到的参数，下图为ReBucket算法的总流程图

详细流程

堆栈预处理

在计算PDM并进行聚类前我们需要从原始堆栈信息中删除以下几种函数（方法），以提取我们真正需要的堆栈信息：

• 白名单函数：白名单函数指那些被认为在软件崩溃时被视为不可能发生错误的函数，通常包括那些非常简单的函数，或者已经成功运行了很长时间的函数
• 递归函数：递归函数经常出现在堆栈信息中，并且大多数递归函数并不包含有效信息，而且会影响到相似度的度量，尤其是当递归函数的数量比较大时。因此这里我们使用一种去除递归函数的算法来去掉它

计算堆栈间的相似度

堆栈分析

在计算堆栈间相似度的过程中需要用到两个度量：

• 当前帧到顶部帧的距离
• 对齐偏移：两个堆栈中匹配的函数到顶部帧的距离的偏移量（差的绝对值）

以上图中的两个堆栈为例，对于两个堆栈$C_1$和$C_2$，崩溃点都位于顶部帧，$C_1$中的$f_0$，$f_1$，$f_4$与$C_2$中的$f_0$，$f_2$，$f_6$匹配，则可以很明显地算出$f_4$和$f_6$的对齐偏移为2

PDM（位置相关模型）

在ReBucket算法中，我们使用PDM来衡量两个堆栈之间的相似度，而PDM是基于以下两个观点的：

• 应该放更大的权重在离顶部帧近的帧上，因为bug的根因更容易出现在离顶部帧近的帧上
• 两个相似的堆栈中的匹配函数之间的对齐偏移应该很小

基于这两个观点，两个堆栈$C_1$和$C_2$之间的相似度可以由以下流程得出：

定义$L$为$C_1$和$C_2$之间所有公共帧序列（子序列）的集合，$L_i$为公共帧序列之一，$S_{i, 1}, S_{i, 2},\ldots S_{i, k}$为$L_i$内相匹配的函数

$L=\left\{L_{1}, L_{s}, L_{3} \ldots\right\} \quad L_{i}=\left\{S_{i, 1}, S_{i, 2}, S_{i, 3}, \ldots S_{i, k} \ldots\right\}$

定义$POS(C_q, S_{i,k})$为$S_{i,k}$在$C_q$堆栈内的位置，$l$为堆栈$C_1$和$C_2$中帧数量的最小值，由下列公式$(1)$可得出$C_1$和$C_2$之间的相似度：

$\left\{ \begin{array}{lr} \operatorname{sim}\left(C_{1}, C_{2}\right)=\frac{\max_{L_{i}\in L} \left[ Q\left(L_{i}\right) \right] }{\sum_{j=0}^{l} e^{-cj}} \\\\ Q\left(L_{i}\right)=\sum_{s_{i, k} \in L_{i}}e^{-c \min \left( \operatorname{Pos}\left(C_{1}, s_{i, k}\right), \operatorname{Pos}\left(C_{2}, s_{i, k}\right) \right)}e^{-o \mid \operatorname{Pos}\left(C_{1}, s_{i, k}\right)-\operatorname{Pos}\left(C_{2}, s_{i, k}\right) \mid} \end{array} \right. \quad (1)$

其中，$c$为到顶部帧的距离系数，$o$为对齐偏移系数。$c$和$o$的值可以根据以往的经验手动设置。后续还有一种基于学习的自动获取最优系数值的方法。$Q\left(L_{i}\right)$用来衡量在公共帧序列$L_i$中匹配的函数的相似度值。其中第一个指数函数考虑了一对匹配函数到顶部帧的最小距离，第二个指数函数考虑最小对齐偏移，到顶部帧的距离以及对齐偏移越小，$Q\left( L_i \right)$的值越大

从公式$(1)$中可以看出：堆栈相似性的度量值由$Q\left(L_{i}\right)$值最大的公共帧序列决定，但穷举所有的公共帧序列效率很低，这里就可以用到求最长公共子序列问题的方法了，用二维动态规划的方法可以高效地求出$Q\left(L_{i}\right)$值最大的公共帧序列，具体步骤如下：

• 定义一个相似度矩阵$M\left[i,j\right]$，$M_{i,j}$表示$C_1$中从顶部帧开始的第$i$帧和$C_2$中从顶部帧开始的第$j$帧之间的相似度
• 根据相似度矩阵$M\left[i,j\right]$的定义，堆栈相似性的度量值由$M_{m,n}$决定，其中$m$为$C_1$的长度，$n$为$C_2$的长度（见公式$(4)$）
• $M\left[i,j\right]$的状态转移方程也可以从$(1)$中得出，与求最长公共子序列比较相似（见公式$(2)$,$(3)$）

$\begin{array}{lr} M_{i, j}=\max \left\{\begin{array}{lr} M_{i-1, j-1} + \operatorname{cost}(i, j) \\ M_{i-1, j} \\ M_{i, j-1} \end{array}\right. &(2) \\\\ \operatorname{cost}(i, j)= \left\{\begin{array}{lr} e^{-c^{*} \min (i, j)} e^{-o^{*} \left| i-j \right|} & \text {if $ith$ frame of } C_1==\text {$jth$ frame of } C_2 \\ 0 & \text { otherwise } \end{array}\right. &(3) \\\\ \operatorname{sim}\left(C_{1}, C_{2}\right)=\frac{M_{m, n}}{\sum_{j=0}^{l} e^{-c j}} &(4) \end{array}$

通过PDM我们就可以衡量任意两个堆栈的相似度，这也是下面对堆栈进行聚类操作的前提和依据

Clustering（堆栈聚类）

对堆栈的聚类基于前面通过PDM计算的堆栈相似性度量，如果堆栈之间非常相似，则相关的崩溃报告会被分到相同的Bucket内

对堆栈聚类这里采用层次聚类方法（一种自底向上的聚类方法），其流程大致为：在聚类的开始，每个堆栈都属于其自己的集群；每一次迭代选择**“最近”**的集群并进行合并

为了确定某个集群在一次迭代中应该和哪个集群合并，我们需要定义集群之间的距离度量，这里我们将这个度量定义为两个集群中所有堆栈之间的最大距离（见公式$(5)$,$(6)$），其中$Cl_i$和$Cl_j$为一对集群，$C_1$和$C_2$分别是$Cl_i$和$Cl_j$中的堆栈

$\begin{array}{lr} \operatorname{distance}\left({Cl}_{i}, {Cl}_{j}\right)=\max_{C_{1} \in {Cl}_{i}, C_{2} \in {Cl}_{j}} \operatorname{ dist }\left(C_{1}, C_{2}\right) & (5) \\ \operatorname{ dist }\left(C_{1}, C_{2}\right)=1-\operatorname{sim}\left(C_{1}, C_{2}\right) & (6) \end{array}$

在一次聚类过程中，考虑最坏的情况，所有堆栈都合并为一个集群，则层次聚类方法的时间复杂度为$O(n^3)$，但在这里我们还会采用距离阈值$d$作为聚类过程的停止标准。$d$的值可以手动设置，也可以通过训练学习；一旦一个集群与其它集群距离的最小值大于距离阈值$d$，则停止对该集群的聚类过程；最后则可以得到一系列包含集群和对应崩溃报告的Bucket，如上图中最后生成了两个Bucket

训练PDM及Clustering中的参数

PDM中用到的两个参数：

• $c$：到顶部帧的距离的系数
• $o$：对齐偏移的系数

分层聚类方法中的距离阈值$d$也是一个需要调优的参数

虽然这些参数都可以手动设置，但因为项目的不同，合适的参数也会不同，所以还是需要一个训练过程来学习这些参数的最优值

首先我们需要根据历史Bucket内的数据和相应的崩溃报告构建数据集，从同一Bucket中提取由开发人员确认的由相同错误引起的崩溃报告作为聚类正确的数据，从不同（不相似）的Bucket中提取由不同错误引起的崩溃报告作为聚类错误的数据（由于异类崩溃报告的数量通常很大，这里提取异类崩溃报告的过程是通过随机采样进行的）。基于获得的重复的和不相似的崩溃报告，收集成对的相似和不相似的堆栈，构建成数据集

对于需要训练的三个参数，它们的值独立变化，不同的参数直接导致不同的聚类性能，所以这里采用一种基于搜索的算法（类似Grid Search），在三个参数的有限集合的笛卡尔积内穷举搜索最优参数组合，流程如下：

// 训练数据集中的堆栈对的数据结构
type trainStackPair struct {
	//TODO: 添加堆栈对数据
	similarity       float64
	predictIsSimilar bool
	isSimilar        bool
}

// 训练参数
func trainParams() (bestParamC float64, bestParamO float64, bestParamD float64) {
	var (
		trainData    []trainStackPair
		paramC       float64
		paramO       float64
		paramD       float64
		bestFMeasure float64
	)
	for paramC <= 2 {
		paramO = float64(0)
		for paramO <= 2 {
			paramD = float64(0)
			for paramD <= 1 {
				for _, pair := range trainData {
					pair.getSimilarity()
					if pair.similarity > float64(1 - paramD) {
						pair.predictIsSimilar = true
					} else {
						pair.predictIsSimilar = false // 这里可以删掉，因为bool默认值就是false
					}
				}
				if newFMeasure := getFMeasure(trainData); newFMeasure > bestFMeasure {
					bestParamC, bestParamO, bestParamD = paramC, paramO, paramD
					bestFMeasure = newFMeasure
				}
				paramD += 0.01 //d的学习率为0.01
			}
			paramO += 0.1 //o的学习率为0.1
		}
		paramC += 0.1 //c的学习率为0.1
	}
	return
}

func (*trainStackPair) getSimilarity() (similarity float64) {
	//TODO: PDM算法获取堆栈间相似度
	return
}

func getFMeasure(stackPairs []trainStackPair) (FMeasure float64) {
	length := len(stackPairs)
	TP, FN, FP, TN := 0, 0, 0, 0
	for _, pair := range stackPairs {
		if pair.isSimilar {
			if pair.predictIsSimilar {
				TP += 1
			} else {
				FN += 1
			}
		} else {
			if pair.predictIsSimilar {
				FP += 1
			} else {
				TN += 1
			}
		}
	}
	FMeasure = 2 * float64(TP) / float64(length+TP-TN)
	return
}

其中$c$，$o$，$d$都初始化为0，最大值分别设定为$c_{max}=2,o_{max}=2,d_{max}=1$,训练中三个参数的学习率（步长）分别固定为0.1, 0.1, 0.01；根据每组参数预测的结果算出F值，最终返回能得到最大F值的参数组

总结

总的来说ReBucket算法可以分为四个模块：

• 堆栈预处理（白名单，递归函数等）
• PDM（二维动态规划）
• Clustering（类似并查集，只是Find函数需要改一下）
• 参数训练（二分类模型，基于F值的Grid-Search）

具体实现见下一篇文章

存在的缺陷

• 应该放更大的权重在离顶部帧近的帧上，因为bug的根因更容易出现在离顶部帧近的帧上这一观点在实际工程环境中并不对，实际上顶部帧存在许多系统调用 / sdk调用 / hook，所以顶部帧并不一定是bug的根因，这里可能可以利用堆栈预处理中的静态 / 动态白名单机制来解决（动态白名单：当一个方法被review并列入白名单后，若其发生变更，则移出白名单）
• 在oom，deadlock等崩溃报告中可能会有多个堆栈，计算其相似性度量时不能是简单的累加关系，而是应该赋予不同的权重；如oom中应该按各个调用所用的内存来分配权重、deadlock中应该按lock关键字等来分配权重。所以PDM模型应该按照崩溃类型异化