论文标题丨Onion: identifying incident-indicating logs for cloud systems
论文来源丨ESEC/FSE 2021
论文链接丨https://dl.acm.org/doi/10.1145/3468264.3473919
源码链接丨未开源

TL;DR

论文中提出一种自动化解决方案 Onion 来精确高效地定位故障日志，首先指出定位故障日志的三个标准：一致性、影响性、双向差异，然后提出一种新颖的日志聚合方法 log clique 可以同时满足这三种标准。为了得到 log clique 论文中提出了一种事件感知的 log 表示和聚类技术，然后对 clique 进行对比分析来识别事件日志。实验部分在标注好的日志数据集中验证了 Onion 的性能，可以达到 0.95 F1-score 并且可以在分钟级内处理百万条日志，应用在真实场景微软云系统中已定性定量证实 Onion 的有效性。

Algorithm/Model

首先介绍下论文中提出的名词概念：

incident-indicating logs：指受事件影响的不同服务器日志其所描述的是同一系统事件。如下图所示

事件日志

incident-indicating logs 定位的三个原则：

  • 一致性（Consistency）：incident-indicating logs 表示跨受事件影响的服务器的一致系统事件。
  • 影响性（Impact）：incident-indicating logs 所表示的一致事件应该分布在大多数异常服务器上。
  • 双向差异（Bilateral-Difference）：incident-indicating logs 在异常服务器中较为常见而在正常服务器中较少。

综上所述的问题及其原则，论文提出的解决方案 Onion 框架如下图所示：

Onion 框架

主要包含以下四步：

  • Log Collection and Cleaning：日志收集处理
    • 为了保证告警前后日志的可比性，采取定制化策略来选择正常服务器日志，即选择同一集群或者相同功能组的服务器日志作为对比。
    • 保留大部分原始日志，利用正则表达式去除部分无用符号。
  • Incident-Aware Log Representation：事件感知日志表示
  • Log Clique：日志聚类
  • Matching and Contrast Analysis：匹配对比分析

详细学习下后三步方法。

事件感知日志表示

考虑日志中部分关键字更加能体现异常状态。

假设所有日志LL 组成词汇字典DD, 主要目标是将每条日志ll 转为向量表示vv。

每个维度的词汇值计算考虑到两方面：

  • 词频（Term Frequency）：词在日志ll 中的出现率。
  • 词重（Term Importance），分为两方面：
    • 同时出现在异常日志中的词重要；
    • 同时出现在正常/异常日志中的词不重要；

考虑上述两个方面论文中提出 Term-Importance 来度量不同词的重要性，首先计算异常服务器SaS_a 中词覆盖率，如下

Sa(w)=∣{Lai∣w∈Lai,i∈[1,ka]}∣kaS_{a}(w)=\frac{\left|\left\{L_{a}^{i} \mid w \in L_{a}^{i}, i \in\left[1, k_{a}\right]\right\}\right|}{k_{a}}

其中kak_a 表示异常服务器数量，LaiL_a^i 表示第ii 个异常服务器的日志。SnS_n 表示正常服务器中词覆盖率。然后定义词重如下所示

TI(w)=Sa2(w)⋅log⁡(Sa(w)Sn(w)+ξ)T I(w)=S_{a}^{2}(w) \cdot \log \left(\frac{S_{a}(w)}{S_{n}(w)}+\xi\right)

其中ξ\xi 通常取 1，然后综合考虑 TF + TI 来表示词向量的值

v(w)=TF(w)⋅TI(w)\boldsymbol{v}(w)=T F(w) \cdot T I(w)

日志聚类

考虑 incident-indicating logs 的三个准则，论文中提出新的聚类方法 log clique，主要包含两步：

  • Progressive Clustering

    对于异常服务器LaL_a 日志的日志向量采用传统聚类方法（层次聚类或者 K-means）分成组作为树中节点，然后定义 Popularity RatioPRaPR_a 来度量每个节点中日志的影响程度。

    PRa(N)=∑i=1kaI(N∩Vai)kaP R_{a}(\boldsymbol{N})=\frac{\sum_{i=1}^{k_{a}} \mathbb{I}\left(\boldsymbol{N} \cap \boldsymbol{V}_{\boldsymbol{a}}^{\boldsymbol{i}}\right)}{k_{a}}

    其中Vai\boldsymbol{V}_{\boldsymbol{a}}^i 表示第ii 个异常服务器的词向量，指示函数

    I(N∩Vai)={1N∩Vai≠∅0N∩Vai=∅\mathbb{I}\left(\boldsymbol{N} \cap \boldsymbol{V}_{\boldsymbol{a}}^{\boldsymbol{i}}\right)= \begin{cases}1 & \boldsymbol{N} \cap \boldsymbol{V}_{\boldsymbol{a}}^{\boldsymbol{i}} \neq \varnothing \\ 0 & \boldsymbol{N} \cap \boldsymbol{V}_{\boldsymbol{a}}^{\boldsymbol{i}}=\varnothing\end{cases}

    遍历聚类树中的节点，设定阈值tpt_p。如果树节点满足 (1)PRa>tpPR_a>t_p (2) 无子节点或子节点PRa<tpPR_a<t_p 作为一个 log clique。

  • Downward-Closure Based Pruning

    上述层次聚类过程效率低下，因此论文中采用剪枝策略来提高效率。主要想法是 Popularity Ratio 低于阈值tpt_p 不再拆分聚类。

整体日志聚类算法如下所示：

日志聚类

匹配对比分析

匹配

log cliques 可能仍包含正常服务器日志，因此需要对比正常/异常服务器中的 cliques 来去除正常的日志。

首先定义 log 向量vniv_n^i 与 clique 间的距离为其与簇中心mi=∑i=0∣Ci∣vi/∣Ci∣\boldsymbol{m}^{i}=\sum_{i=0}^{\left|C^{i}\right|} v^{i} /\left|C^{i}\right| 的距离，定义类半径rir^i 为mim^i 与其最边缘 log vector 距离。

定义簇CiC^i 包含的正常日志集合为

M(Ci)={vn∣d(vn,mi)⩽d(vn,mk)∧d(vn,mi)⩽ri}\mathcal{M}\left(C^{i}\right)=\left\{v^{n} \mid d\left(v^{n}, m^{i}\right) \leqslant d\left(v^{n}, m^{k}\right) \wedge d\left(v^{n}, m^{i}\right) \leqslant r^{i}\right\}

然后就直接将 clique 中包含的正常日志删除。

对比

定义 Contrast Score 来度量双边差异性，

score⁡(Ci)=log⁡(PRa(Ci)PRn(M(Ci)))\operatorname{score}\left(C^{i}\right)=\log \left(\frac{P R_{a}\left(C^{i}\right)}{P R_{n}\left(\mathcal{M}\left(C^{i}\right)\right)}\right)

然后选择 score 大于log⁡(tp1−tp)\log \left(\frac{t_{p}}{1-t_{p}}\right) 的 log cliques 作为 incident-indicating logs。

Experiments

实验部分采用了三种类型的日志数据进行测试，数据集统计如下

实验数据

实验准确率如下所示：

实验结果

Onion 性能如下所示：

实验结果