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

原文: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(·,·)$ 表示两节点的最短路径长度,把它们累加起来以表示两个属性的不相似度。

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

    • 接下来把警报的所有属性都加入计算,累加报警的所有属性的不相似度,即可表示报警的不相似度。对于两个报警 $\mathcal{a_1}$、$\mathcal{a_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(A_1) \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}$ 的覆盖效果不好。

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

      $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$)

      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
      /* 将报警日志集合 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)$:

    1
    fi(v) := SELECT sum(count) FROM T WHERE Ai = v
  • 让 $F_i$ 记作每个属性 $A_i$ 的最大值函数 :

  • 这里的逻辑是:

    • 若有一个报警 $\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 服务器,我们通过附加端口值进行准确泛化。

    1
    2
    3
    if a[Destination-port] = 80
    then generalize ip to HTTP-server
    else generalize ip to FTP-server;
  • 探索所有法:并行地探索所有可能的泛化结果 (穷举法)。改写上述代码 16 行即可实现:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 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{a_x}$、$\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 行)。

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

参考资料