Press "Enter" to skip to content

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

原文: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
Step.02
Step.03
Step.04

 

算法的伪代码描述:

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$ 的最大值函数 :

 

这里的逻辑是:

若有一个报警 $\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 不符合抽象描述的要求,因此也无需关注此项指标。
综上所述,我们选择的特征包括: 机房环境异常来源报警日志文本摘要故障所在位置 ( 接口、类 )。

提取关键特征

 

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

 

机房和环境
异常来源
报警日志文本摘要
故障所在位置

 

泛化层次结构

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

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

图 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 的阈值,即停止聚类。

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注