LCS-VMM：基于变阶马尔可夫模型和最长公共子串的调用链故障模式挖掘方法

论文标题｜ Fault Injection Analytics: A Novel Approach to Discover Failure Modes in Cloud-Computing Systems
论文来源｜ TDSC(A) 2020
论文链接｜ https://arxiv.org/abs/2010.00331
源码链接｜未公布

TL;DR

论文中基于故障注入实验提出了一种无监督 trace 异常检测方法和可视化框架，论文基于最长公共子串和变阶马尔科夫模型学习 trace 执行模式，然后预测不同 event 出现的概率来判断异常，此外，还提出了一种故障表示方法对故障模式进行表示。实验部分在多种故障实验中验证论文中方法的可行性。

Algorithm/Model

论文中提出的方法框架如下图所示：

主要包括以下七个部分：

Instrument：系统组件间通信信息采集工具库；
Fault-free execution：采集正常 traces ；
Model training：利用正常 traces 训练概率模型学习正常模式；
Fault-injected traces：注入单一类型故障后采集 traces 用于测试模型；
Anomaly detection：基于正常模式的模型，对测试 traces 中不同的 events 进行异常检测；
Clustering：对异常模式进行聚类；
Visualization：将 traces 按照不同的异常模式进行统计和可视化，然后展示给管理员；

对于每个步骤详细的流程图如下所示：

Data collection

论文中采集了三种类型的 traces：

idle traces：空闲时间产生的与负载无关的 traces，例如系统垃圾回收或者前端资源监控产生的系统调用 traces，可以理解为噪声。
N fault-free traces：正常工作负载产生的 traces 用于训练模型；
faulty traces：注入故障后产生的 traces 用于测试模型；

由于在空闲状态下系统中仍然会产生 idle trace，为了去除掉这种噪声因此在采集的 fault-free traces 和 faulty traces 中需要把 idle traces 删掉，否则模型会把这种 traces 识别为异常的。

Trace pre-processing

每个 trace 由多个 spans 或者 events 序列组成，每篇论文中叫法不同，这篇论文中称为 events。

每个 event 可以利用 API 采集通信信息包括 <message sender, service API>，分别表示发送方和服务 API。

论文中使用 symbols 来唯一标识 trace 中的 events，相同的 event 会使用同一个 symbol 来表示，这意味去除了相同的调用，📢 论文目前没说明相同 events 如何去重！

trace 中每次调用都会存在一个状态码 status code，这也可以作为一个维度特征，所以每个 symbol 包含三个属性 <message sender, service API, status code>

按照时间排序可以将 trace 转化为一条 symbols 序列组成。

在 trace 异常检测之前，论文中先过滤掉没有异常的 events，主要想法就是找到 fault-free trace 和 faulty traces 间相同的 symbols 部分然后去除，使用的方法就是 LCS(longest common sub-sequence)。

定义了字符串间最长公共子串的标准化长度计算公式如下：

$n L C S(x, y)=\frac{|L C S(x, y)|}{\sqrt{l_{x} \cdot l_{y}}}$

找到最相似的 fault-free trace 称为 selected fault-free trace ，然后根据 selected fault-free trace 去除掉 faulty trace 中公共的 events 保留不同的 events，保留下来的 non-comment events 用于异常检测模型进行分析。

Probabilitic modeling

异常检测模型的主要目的是判定保留下来的 events 是故障还是误报。

这容易理解：就算测试 trace 中存在和 fault-free trace 序列不同的 events，也不知道是故障引起的还是采集的 fault-free trace 没有覆盖到所有用户行为。

论文中基于隐马尔科夫模型提出了变阶马尔科夫模型 (Variable-order Markov Models, VMMs) 来估计 event 的故障概率。变阶马尔科夫模型可以参考论文：【2004/JAIR】On prediction using variable order markov models。

VMMs 的主要作用是：利用上下文 Sequence $s$ 估计之后 Symbol $\sigma$ 出现的条件概率，可以根据训练数据来拟合模型 $\hat{P}(\sigma, s)$ ，模型优化的对数损失函数为

$\ell\left(\hat{P}, x_{1}^{T}\right)=-\frac{1}{T} \sum_{i=1}^{T} \log \hat{P}\left(x_{i} \mid x_{1} \ldots x_{i-1}\right)$

简单的 VMMs 不能解决 zero-frequency problem，即存在 sequences 没有出现在训练集中导致学习的模型健壮性并不好。因此论文中使用 PPM (Prediction by Partial Matching) 无损压缩算法来进行优化。

PPM 是一种统计模型技术，主要思想是结合多个固定阶数 $k\in (0, D]$ 的上下文模型来构造预测模型， $D$ 表示马尔科夫模型的最大阶数，其包括两种变体： escape 和 exclusion；论文中使用的是 escape 机制，对于训练数据中未出现在序列 $s$ 后的 symbols 算法会分配一个均匀概率 $\hat{P}_{k}(\operatorname{escape} \mid s)$ ，对应的出现在 $s$ 序列后的概率为 $1-\hat{P}_{k}(\operatorname{escape} \mid s)$ 。

对应的条件概率计算计算公式变为：

$\hat{P}\left(\sigma \mid s_{n-D+1}^{n}\right)=\left\{\begin{array}{l} \hat{P}_{D}\left(\sigma \mid s_{n-D+1}^{n}\right), \quad \quad \dagger \\ \hat{P}_{D}\left(\text { escape } \mid s_{n-D+1}^{n}\right) \cdot \hat{P}\left(\sigma \mid s_{n-D+2}^{n}\right),\quad \quad \Dagger \end{array} \right.$

$\dagger$ 表示 $s_{n-D+1}^{n}$ 出现在训练序列中； $\Dagger$ 表示未出现在训练序列中，论文中设定默认 $D=5$ ，可以根据实际 sequence 长度调整。

📢 注意是使用 N-1 个 fault-free trace 训练 VMMs，1 为 selected fault-free trace。

详细计算过程没有详细说明，需要参考其它文献。

J. G. Cleary and W. J. Teahan, “Unbounded length contexts for ppm,” The Computer Journal, vol. 40, no. 2 and 3, pp. 67–75, 1997.
J. Cleary and I. Witten, “Data compression using adaptive coding and partial string matching,” IEEE Trans. on Communications, vol. 32, no. 4, pp. 396–402, 1984.
A. Moffat, “Implementing the PPM data compression scheme,” IEEE Trans. on Communications, vol. 38, no. 11, pp. 1917–1921, 1990.

Classification of anomalies

模型的异常检测结果可以将 events 划分为以下几种类型：

Comment events：表示 faulty trace 和至少一条 fault-free trace 中的 events。
Anomalous events：表示 faulty trace 和 fault-free trace 中不同的 events。可以划分为两种类型：
- Spurious events：在 fault-free 情况下没有发生的 events。（理解为新的 event)
- Missing events：在 fault-free 情况下发生但是在故障注入后未发生的 events。（理解为缺失的 event）

根据 selected fault-free trace，故障 event 诊断：

如果 faulty trace 包含 event 且 VMM 条件概率低于一定值 $\epsilon_{SPURIOUS}= 20\%$ ，那么这个 event 是 Spurious；
如果 faulty trace 不包含 event 且 VMM 条件概率大于一定值 $\epsilon_{MISSING}= 80\%$ ，那么这个 event 是 Omission；