论文 | 基于根因分析的报警聚类算法

原文：Clustering intrusion detection alarms to support root cause analysis
作者：Klaus Julisch
来源：ACM Transactions on Information and System Security, 2003, 6(4):443-471.

背景

• 系统出现故障时，运维人员一般先查看错误日志定位故障原因。
• 业务流量小、逻辑复杂度低时，应用出现故障时错误日志一般较少，运维人员根据错误日志迅速定位到问题。但随着业务逻辑的迭代，系统接入的依赖服务不断增多、引入的组件不断增多，当系统出现故障时，错误日志的量级急剧增加。极端情况下更甚出现 “疯狂报错” 的现象，这时错误日志的内容会存在 相互掩埋、相互影响 的问题，运维人员面对报错一时难以理清逻辑， 失去焦点，没能第一时间解决最核心问题。
• 若在报警流出现时，通过处理程序将报警进行聚类，整理出一段时间内的报警摘要。运维人员就可以在摘要信息的帮助下，先对当前的故障有一个大致的轮廓，再结合技术知识与业务知识定位故障的根本原因。
• 围绕上面描述的问题，以及对于报警聚类处理的分析假设，本文主要做了以下事情：
  • 选定算法：选定聚类算法，简单描述算法基本原理，并给出针对报警日志聚类的一种具体实现方案。
  • 验证算法：在分布式业务服务的系统下构造了三种不同实验场景，验证了算法的效果，并且对算法的不足进行分析阐述。

目标

• 我们希望这些泛化报警既要具有很强的概括性，同时尽可能地保留细节。这样运维人员在收到报警时，便能快速定位故障的大致方向，从而提高故障排查的效率。

• 对一段时间内的报警进行聚类处理，将具有相同根因的报警归纳为能够涵盖报警内容的泛化报警，最终形成仅有几条泛化报警的报警摘要，如图 1-1 所示。

  

  图 1-1 通过聚类算法泛化报警日志

概述

• 如图 1-2 所示，文章主要分三个部分阐述：提取报警特征、算法实现以及展示报警摘要。

• 首先，是根据根因分析提取报警关键特征，并生成报警信息的泛化层次结构。其次，则是从泛化层次结构中计算得不同报警对象之间的不相似度度量，以确定最具象化的泛化表示、最大程度涵盖原始报警集合的泛化层次结构。最后，经由聚类算法获得泛化报警簇群，以簇群代表某一类报警信息。

  聚类算法还涉及 min_size 与 聚类停止条件 的调参问题，详情见下文描述。

  

  图 1-2 文章的章节布局

正文

泛化初探

• 将报警信息抽象表达、逐层分解，形成类似于 树结构 或者 有向无环图 的泛化层次结构。

  如图 1-3 所示，可将服务器的报警抽象为 “全部服务器 网络调用 故障”，也可以抽象为 “server_room_a 服务器 网络调用 产品信息获取失败” 和 “server_room_b 服务器 RPC 获取产品类型信息失败”。

  前者泛化范围较广、抽象层次较高，细节越少；后者包含的范围较小、抽象层次低，则包含的无用信息可能越多。当然不局限于一种层次关系，你也可以用其他层次的抽象来表达这个报警集群。

  

  图 1-3 服务器的报警泛化初探

算法定义

• 为了确定报警聚类泛化的程度，我们需要先了解一些定义：
  • 属性 ( Attribute )：构成报警日志的基本信息，如机器、环境、时间等，记作 $A_i$。
  • 值域 ( Domain )：属性 $A_i$ 的值域 ( 取值范围 )，记作 $Dom(A_i)$。
  • 泛化层次结构 ( Generalization Hierarchy )：对于每个属性 $A_i$，都有一个对应的泛化层次结构，记作 $G_i$。
  • 不相似度 ( Dissimilarity )：定义为 $d(\mathcal{a_1}, \mathcal{a_2})$。它接受两个报警 $\mathcal{a_1}$、$\mathcal{a_2}$ 作为输入，并返回一个数值量，表示这两个报警不相似的程度。当 $d(\mathcal{a_1}, \mathcal{a_2})$ 较小时，表示报警 $\mathcal{a_1}$ 和报警 $\mathcal{a_2}$ 越相似，相反越大则越不相似。为了计算不相似度，则需要用户预先定义好报警信息的 泛化层次结构。

• 计算 $d(\mathcal{a_1}, \mathcal{a_2})$，我们先定义两个属性值的不相似度：令 $x_1$、$x_2$ 为 $\mathcal{a_1}$、$\mathcal{a_2}$ 某个属性 $A_i$ 的两个不同的值，$x_1、x_2 \in Dom(A_i)$。

  • 在属性 $A_i$ 的泛化层次结构 $G_i$ 中，通过一个公共点父节点 $p$ 连接 $x_1$、$x_2$ 的最短路径长度。$\delta(·,·)$ 表示两节点的最短路径长度，把它们累加起来以表示两个属性的不相似度。

    $$d(x_1, x_2) := \min \left\{ \delta(x_1, p) + \delta(x_2, p) \mid p \in G_i, x1 \trianglelefteq p, x2 \trianglelefteq p \right\} \tag{1}$$

    举例：在图 1-3 的泛化层次结构中：
    d(“Thrift”, “Pigeon”) = d(“RPC”, “Thrift”) + d(“RPC”, “Pigeon”) = 1 + 1 = 2

  • 接下来把警报的所有属性都加入计算，累加报警的所有属性的不相似度，即可表示报警的不相似度。对于两个报警 $\mathcal{a_1}$、$\mathcal{a_2}$，其不相似度的计算公式为：

    $$d(\mathcal{a_1}, \mathcal{a_2}) := \sum_{i=1}^n d(\mathcal{a_1}[A_i], \mathcal{a_2}[A_i]) \tag{2}$$

    举例：参考图 1-3 的泛化层次结构：
    $\mathcal{a_1}$ = (“server_room_b-biz_tag-offline02”, “Thrift”)
    $\mathcal{a_2}$ = (“server_room_a-biz_tag-online01”, “Pigeon”)

    $d(\mathcal{a_1}, \mathcal{a_2})$ =
    d(“server_room_b-biz_tag-offline02”, “server_room_a-biz_tag-online01”) +
    d(“Thrift”, “Pigeon”)

    $d(\mathcal{a_1}, \mathcal{a_2})$ =
    d(“server_room_b-biz_tag-offline02”, “服务器”) +
    d(“server_room_a-biz_tag-online01”, “服务器”) +
    d(“RPC”, “Thrift”) +
    d(“RPC”, “Pigeon”)
    = 2 + 2 + 1 + 1 = 6

• 对于某个报警聚类来说，我们如何获得既能够涵盖它的集合又有最具象化的泛化表示？回答问题前，我们预先完成一些定义：

  • 一个警报对象是 n 维属性空间 $dom(A1) \times dom(A_2) … \times dom(A_n)$ 上的元组，记作 $\mathcal{X}{i = 1}^{n} Dom(A_i)$。

  • 我们用 $C$ 表示报警集合，$\mathbf{g}$ 是 $C$ 的一个泛化表示，满足 $\forall \mathcal{a} \in C, \mathcal{a} \trianglelefteq \mathcal{g}$。

    以报警集合 {“dx-trip-package-api02 Thrift get deal list error”, “dx-trip-package-api01 Thrift get deal list error”} 为例，dx服务器 thrift调用 获取产品信息失败 是一个泛化表示，服务器 网络调用 获取产品信息失败 也是一个泛化表示。

  • 定义 $d_i := d(\mathcal{g}, a_i), i = 1, 2$，$d_i$ 表示在警报 $a_i$ 中需要多少个属性即可让 $\mathcal{g}$ 泛化表示 $\mathcal{a_i}$。当 $d_1 + d_2$ 越小，$\mathcal{g}$ 从警报 $\mathcal{a_1}、\mathcal{a_2}$ 中获得泛化表示的步数越少，说明 $\mathcal{g}$ 对 $\mathcal{a_1}、\mathcal{a_2}$ 覆盖越充分。相反，当 $d_1 + d_2$ 越大，由于过于抽象或者未能有效捕获警报 $\mathcal{a_1}、\mathcal {a_2}$ 的详细信息，说明当前 $\mathcal{g}$ 的覆盖效果不好。

  • 因此，明确我们的目标是计算得 最小化的报警不相似度 以获得 最具象化的泛化表示。为了解决这个问题，定义以下两个指标：

    $$\overline{d} (\mathcal{g}, \mathcal{C}) := 1 / | \mathcal{C} | \times \sum _{\mathcal{a} \in C} d (\mathcal{g}, \mathcal{a}) \tag{3}$$ $$H(C) := \min \left\{ \overline {d}(\mathcal{g} , C) \mid \mathcal {g} \in \mathcal{X}_{i = 1}^{n} Dom(A_i), \forall \mathcal {a} \in C : \mathcal{a} \trianglelefteq \mathcal{g} \right\} \tag{4}$$

    $H(C)$ 代表一个报警簇群 $C$ 的相异性度量，$\overline{d} (\mathcal{g}, \mathcal{C})$ 代表一个报警簇群的平均相异性度量。$H(C)$ 值最小时对应的 $\mathcal{g}$ 就是我们要找的最适合的泛化表示，我们称 $\mathcal{g}$ 为 $C$ 的覆盖。

• 基于以上的概念，将报警日志聚类问题定义为：

  • 定义 $L$ 为一个日志集合，$G_i(i = 1, 2, 3……n)$ 为属性 $A_i$ 的泛化层次结构，min_size $ \in \mathbb{N}$ 为一个预设的常量。

  • 目标是找到一个 $L$ 的子集 $C$，簇群中元素数量满足 $|C| \geq$ min_size，且 $H(C)$ 值最小。

    min_size 是用来控制抽象程度的，即一个簇群至少包含的元素个数。若 min_size 与 $L$ 集合的大小一样，那么我们只能使用终极抽象了；若 min_size = 1，则每个报警日志是它自己的抽象。

  • 找到一个聚类之后，我们可以去除这些元素，然后在 $L$ 剩下的集合里找其他的聚类。

• 不幸的是，这是个 NP 完全问题 ( 分团问题 )。因此论文 $^{[2]}$ 提出了一种启发式算法，该算法满足 $|C| \geq$ min_size，使 $H(C)$ 值尽量小 ( 并不一定要最小化的 $H(C)$ )。

算法描述

• 启发式 Alarm-Clustering 算法：面向属性归纳的改进算法 (Attribute-oriented induction, AOI) $^{[3]}$。

  面向属性归纳的改进算法：1) 对比经典的 AOI 算法更保守地概括属性；2) 使用了类似基于密度聚类的聚类终止条件。

  • Step.01: 算法假设所有的泛化层次结构 $G_i$ 都是树，这样每个报警集群都有一个唯一的、最顶层的泛化结果。
  • Step.02: 将 $L$ 定义为一个原始的报警日志集合，算法选择一个属性 $A_i$，将 $L$ 中所有报警的 $A_i$ 值替换为 $G_i$ 中 $A_i$ 的父值，通过这一操作不断对报警进行泛化。
  • Step.03: 持续步骤 2 的操作，直到找到至少可以将原始报警泛化为报警簇群的最小值 min_size。
  • Step.04: 输出步骤 3 中找到的报警。

• 算法的伪代码描述：

  • Input：(报警日志集合 $L$，min_size，每个属性的泛化层次结构 $G_1、…、G_n$)

  • Output：(泛化报警日志集合 $L$，min_size，每个属性的泛化层次结构 $G_1、…、G_n$)

    /* 将报警日志集合 L 保存至表 T，且表中每一列代表报警的一项属性 Ai */
    T := L
    	
    /* count 是统计当前报警记录数量的变量 (可理解为报警簇群的大小)
     * count 初始化为 1 可理解为当前报警为一个仅且包含它本身的簇群 */
    for all alarms a in T do a[count] = 1; 
    	
    /* 开始对报警进行泛化操作 */
    while ∀a∈T:a[count] < min_size do {
    	
    	// Step.1 使用启发算法选择一个属性 Ai
    	
    	// Step.2 对 L 中所有报警进行泛化：
    	// 即把报警的属性 Ai 替换为泛化层次结构 Gi 中 Ai 的父值
    	for all alarms a in T do {
    		a[Ai] := parent of a[Ai] in Gi;
    	}
    		
    	// Step.3 如果 a[Ai] == a’[Ai], i = 1, 2, ..., n
    	// 即报警的所有属性 Ai 都相同
    	while identical alarms a, a' exist do {
    		// 合并相同警报于同一个泛化报警 a 中并更新泛化警报的计数
    		Set a[count] := a[count] + a'[count];
    		// 完成统计后移除报警记录 a'
    		Delete a' from T;
    	}
    }

启发式选择属性泛化报警

其中第 11 行的启发算法为:

• 统计在 $A_i$ 属性上值为 $v$ 的报警的数量，记作 $f_i(v)$：

  fi(v) := SELECT sum(count) FROM T WHERE Ai = v

• 让 $F_i$ 记作每个属性 $A_i$ 的最大值函数 ：

  $$F_i := \max \left\{ f_i(v) | v \in Dom(A_i) \right\} \tag{5}$$

• 这里的逻辑是：

  • 若有一个报警 $\mathcal{a}$ 满足 $\mathcal{a}[count] \geq$ min_size，那么对于所有属性 $A_i$ 均能满足 $F_i \geq f_i(\mathcal{a}[A_i]) \geq$ min_size。

  • 相反，如果有一个属性 $A_i$ 的 $F_i <$ min_size，那么 $\mathcal{a}[count]$ 就不可能大于 min_size。所以选择 $F_i$ 值最小的属性 $A_i$ 进行泛化。

    类似于木桶定律，装水量由最短的木板决定。

DAG 形式的泛化层次结构

• 当泛化层次结构是一个有向无环图 (Directed Acyclic Graph, DAG)，而不是一颗树时，结构上的任何一个节点都有可能包含多个父节点，那么一个属性值存在多个父节点将其泛化。

  针对此问题，基于经典的 AOI 提出两种解决策略：

• 选择其一法：基于用户定义的规则解决歧义问题。例如，考虑运行在同一 IP 下的 HTTP 服务器和 FTP 服务器，我们通过附加端口值进行准确泛化。

  if a[Destination-port] = 80
  	then generalize ip to HTTP-server 
  else generalize ip to FTP-server;

• 探索所有法：并行地探索所有可能的泛化结果 (穷举法)。改写上述代码 16 行即可实现：

  // Step.2 对 L 中所有报警进行泛化
  for all alarms a in T do {
  	T := T \ {a};
  	// 由属性 Ai 泛化报警的所有可能性都加入 T 中
  	for all parents p that a[Ai] has in Gi do {
  		a' := a; 
  		a'[Ai] := p; 
  		T := T ∪ {a'};
  	}
  }

MINSIZE 参数自适应算法

• 此外，关于 min_size 的选择问题，如果选择了一个过大的 min_size，那么会迫使算法合并具有不同根源的报警。另一方面，如果过小，那么聚类可能会提前结束，具有相同根源的报警可能会出现在不同的聚类中。
• 因此，设置一个初始值，可以记作 $ms_0$。定义一个较小的值 $\varepsilon (0 < \varepsilon < 1)$，当 min_size 取值为 $ms_0$、$ms_0 \times (1 - \varepsilon )$、$ms_0 \times (1 + \varepsilon )$ 时的聚类结果相同时，我们就说此时聚类是 $ \varepsilon$-鲁棒的。

• 如果不相同，则使 $ms_1 = ms_0 * (1 - \varepsilon)$，重复这个测试，直到找到一个鲁棒的最小值。

  需要注意的是，$ \varepsilon$-鲁棒性与特定的报警日志相关。因此，给定的最小值，可能相对于一个报警日志来说是鲁棒的，而对于另一个报警日志来说是不鲁棒的。

案例实现

提取报警特征

• 根据线上问题排查的经验，运维人员通常关注的指标包括时间、机器 ( 机房、环境 )、异常来源、报警日志文本提示、故障所在位置 ( 代码行数、接口、类 )、Case 相关的特殊 ID ( 订单号、产品编号、用户ID ) 等。
• 在本案例中，实际应用场景都是线上准实时场景，时间间隔短，因此我们不需要关注时间指标；同时，Case 相关的特殊 ID 不符合抽象描述的要求，因此也无需关注此项指标。
• 综上所述，我们选择的特征包括：机房、环境、异常来源、报警日志文本摘要、故障所在位置 ( 接口、类 )。

提取关键特征

我们的数据来源是日志中心已经格式化过的报警日志信息，这些信息主要包含：报警日志产生的时间、服务标记、在代码中的位置、日志内容等。在定义泛化层次结构前夕，我们需要从已知的数据源中梳理出关键特征。

• 机房和环境：提取这两个指标比较简单，在此不做详细赘述。
• 异常来源：获得故障所在位置后，优先使用此信息确定异常报警的来源；若不能获取，则在日志内容中根据关键字匹配。需要说明的是，两者都需要预先定义词典支持。
• 报警日志文本摘要：优先查找日志内容中是否有异常堆栈，若存在，则查找最后一个异常 ( 通常为真正的故障原因 )；若不能获取，则在日志中查找是否存在 “code=……, message=……” 这样形式的错误提示；若不能获取，则取日志内容的第一行内容 ( 以换行符为界 )，并去除其中可能存在的 Case 相关的提示信息。
• 故障所在位置：优先查找是否有异常堆栈，如存在则查找第一个本地代码的位置； 若不存在，则取日志打印位置。

泛化层次结构

• 泛化层次结构，用于记录属性的泛化关系，是泛化时向上抽象的依据，需要预先定义。

• 根据实验所用项目的实际使用环境，根据 关键特性 定义的 泛化层次结构 如下：

  

  图 1-4 机房泛化层次结构

  

  图 1-5 环境泛化层次结构

  

  图 1-6 异常来源的泛化层次结构

  

  图 1-7 报警日志文本摘要的泛化层次结构

• 故障所在位置 此属性无需泛化层次结构，每次泛化时直接按照包路径向上层截断，直到系统包名。

报警聚类算法

• 算法的执行流程，我们以图 1-8 来表述：

  

  图 1-8 报警日志聚类流程图

• min_size 参数设定：考虑到日志数据中可能包含种类极多，且根据小规模数据实验表明，min_size $= \frac15 \times$ 报警日志数量时，算法已经有较好的表现，再高会增加过度聚合的风险，因此我们取 min_size $= \frac15 \times$ 报警日志数量，$\varepsilon$ 参考论文中的实验取 0.05。

• 聚类停止条件：考虑到部分场景下，报警日志可能较少，因此 min_size 的值也较少，此时聚类已无太大意义，因此设定聚类停止条件为：聚类结果的报警摘要数量小于等于 20 或已经存在某个类别的 count 值达到 min_size 的阈值，即停止聚类。

延伸探究

• 在论文中，警报 $\mathcal{ax}$、$\mathcal{a_y}$ 的不相似度量定义为 $d(\mathcal{a_x}, \mathcal{a_y}) := \sum{i=1}^n d(\mathcal{a_x}[A_i], \mathcal{a_y}[A_i])$，$d(·,·)$ 即把警报 a 中每个属性的不相似度量累加起来。

  在现实条件下，警报对象包含的属性值理应是有主次、重要性之分。我们计算警报的不相似度，具体计算不同的属性的不相似度时，是否考虑加入权重计算系统。

• 关于泛化层次结构的表现形式包括 有向无环图 和 树。针对有向无环图形式的泛化层次结构，一个结构节点可能存在多个父节点，即一个属性值存在多个父节点将其泛化，故论文基于经典的 AOI 提出两种解决策略，以准确地选择唯一父节点去泛化报警。

  首先，是结合领域知识的 选择其一法，满足基本要求但需要人为因素干预。而现在问题是，若采取 探索所有法 将所有的泛化报警都加入集合 T 中，然而存在重复加入泛化报警的可能性，那么由原始方法构建簇群将是不正确的 (上述伪代码 23 行)。

  原论文描述解决办法：重新扫描原始警报日志，并确定与之匹配的原始警报的数量？细节和意图不明确，是否有替代方案？

参考资料

• [1] 美团技术团队. 根因分析初探：一种报警聚类算法在业务系统的落地实施. 2019. tech.meituan.com
• [2] Julisch K . Clustering intrusion detection alarms to support root cause analysis[J]. ACM Transactions on Information and System Security, 2003, 6(4):443-471.
• [3] Jiawei Han 等著; 范明等译. 数据挖掘:概念与技术 (原书第3版) [M]. 机械工业出版社., 2012. 111-116.