原文: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