对网络流量异常进行快速的两阶段多维根因分析

01 引言

异常检测对网络运行和维护至关重要。为有效处理和解决网络工作异常，应进行根因分析，以识别异常并协助恢复异常。在基于网络流量的异常检测中，通常需要识别异常流量的模式，以便采取适当的访问控制规则，例如，对于 DDoS 攻击，其流量模式可能是特定目标 IP 地址和端口的属性组合。识别这样的异常流量模式通常采用基于多维属性的根因分析（Root Cause Analysis, RCA），从而确定异常流量的属性组合。

在大型 ISP 网络中，根因分析过程往往是耗时且容易出错的，因此许多研究致力于提出一种自动化的根因分析流程来提升运维效率。目前针对多维属性的根因分析工作主要分成两大类，第一类是通过设计某种指标M，穷举所有组合寻找使得M取值最大的属性组合，但是通常来说指标M的定义严重依赖于领域知识，且穷举耗时较长。第二类是通过设计适当的搜索算法来降低时间复杂度，从而快速定位异常根因的属性组合，但是随着数据量或维度的增加，这类方法的精度会下降。因此，本文提出了FTM-RCA框架（Fast Two-Stage Multi-dimensional Root-Cause Analysis快速两阶段多维根源分析），它将多维属性的根因分析分解为两个阶段：粗粒度规则过滤和细粒度定位，从而在有限的时间中能够快速准确的定位异常的根本原因。

02 模型设计

如上文所述，FTM-RCA有两个阶段，分别是粗粒度规则过滤和细粒度定位。在第一阶段，我们使用频繁项挖掘（FIM）算法快速筛选出不频繁的组合，从而大大缩小搜索空间。同时，利用属性维度下取值的互斥性，我们对现有的FIM 算法进行了优化，提出基于压缩并集表示的频繁项挖掘算法（Compressed UnionSet Cross-operation, CUSC），将频繁项挖掘的执行时间缩短了44.87%，且可用于大规模网络流量。在第二阶段，我们将筛选后的频繁项组织成一个有向无环图（DAG），并设计了一种自上而下的基于维度的启发式搜索框架来定位真正的根因组合。

2.1 为什么可以使用频繁项挖掘技术来辅助根因分析？

要想找到根因，一种直接的方法是遍历所有可能的值组合。然而即使较低的维度也能产生相当多的候选组合，穷举的方案在现实世界的网络中是不可行的。我们注意到根因组合通常在异常发生时或之前的时间段内是“显著的”。这意味着，如果某时刻的异常量为ano（通常来说，计算为真实值和预测值之间的差值），并且在异常发生之前的某个时间段内，规则r'对应的流量值v始终小于阈值ξ，那么其异常幅度将不会超过λ·ano (λ通常低于1%)，详细推导可见[1]，即规则r'对于当前时刻的异常来说是不显著的。因此，可以通过使用频繁项集挖掘技术过滤掉低于阈值的任何规则（属性值组合），从而避免大量不必要的计算。

2.2 基于压缩并集表示的频繁项挖掘算法

CUSC（Compressed UnionSet Cross-operation）

图1. 多维属性的流量数据集示例

以图1的一个简单的数据集为例，ABC分别是属性维度，RID是流量的唯一标志符，value是在当前时间段内的流量大小。如果一个属性组合的总流量值超过了预定义的最小阈值min_sup，则认为该组合是频繁出现的，即频繁项，例如，组合的总流量值为4（2+2=4）。在传统的频繁项挖掘算法中，不会考虑维度属性之间的互斥关系，例如在一条流量中不会同时出现两个A属性维度的不同取值，即 <这样的属性组合是一定不会出现在频繁项中的。因此，我们可以利用这种互斥性来避免生成不合理的候选项。

首先我们设计了一个unionSet结构来单独存储每个维度的值。假设数据集D中有n条记录，那么维度X上的unionSet可以表示为，其中是维度X的第k条记录的值。例如，维度A的unionSet是。对于维度X和Y的组合，它可以是。在第一次遍历数据集时，我们需要统计每个维度的unionSet，同时统计每个不同的维度取值的总流量值。为了表示有效的属性组合（itemset），我们为非频繁项设置掩码，称为maskSet。当设置min_sup为4时，维度A的maskSet是[0, 0, 0, 0, 0, mask]，长度为1的频繁项集是：{，称为1-itemsets。与Apriori不同，CUSC避免计算所有k-itemset的组合，而是设计了交叉操作来基于频繁的(K-1)-itemsets生成有效的K-itemsets。首先合并两个上一级维度的maskSet，例如，维度A和B的union maskSet是[0, 0, 0, mask, 0, mask]，然后计算未被掩码的属性组合的累积流量值，再进行mask操作。样例计算过程可以参考图2：

图2. 一个使用CUSC算法的频繁项挖掘的例子，min_sup设置为4

2.3 细粒度的根因定位（Fine-grained Localization）

为了建立频繁项之间的连接，我们使用一个有向无环图来描述它们的子集-超集关系，如图3所示。图中的每个节点代表一个属性组合，且有三个特征：属性组合、实际流量值和预测流量值。实际值和预测值代表属性组合的实际流量值和预测流量值。异常值是一个扩展属性，指的是预测值和实际值之间的差异。为了能准确定位到异常的根因节点，我们设计了一种启发式根因搜索算法，有两个策略组成，drill-down策略负责引导搜索方向，pruning策略决定何时终止搜索。

图3. 基于频繁项之间的子集-超集关系建立的有向无环图

2.3.1 Drill-down策略

当我们开始从根节点搜索时，我们实际上是通过选择扩展节点来进行维度钻取。如果一个节点的异常值主要由其有限数量的后代节点贡献，我们更倾向于向下钻取分析，同时过滤那些异常贡献微小的节点。具体来说，我们定义节点j对其父节点i在维度d上的贡献率（Contributive Power，CP）为节点j上的异常值与节点i上的异常值的百分比。我们先按Contributive Power的降序对子节点进行排序，并过滤掉小于阈值β的节点，再按顺序选择扩展节点，直到累积的contributive power超过阈值α。

2.3.2 Pruning策略

为了找到简洁的根因，当后代节点的异常均匀分布时，我们应当停止搜索。具体来说，我们定义节点v的相对异常值(Relative Anomalies，RA)如下：

其中，和分别表示节点v的预测值和实际值，当节点Vi的后代节点的Shannon Entropy超过阈值γ时，停止对节点v的扩展。

03 实验结果

本次实验的数据集包括公开数据集（来自AIOps比赛）、半合成数据集以及校园网采集的流量数据集，详细情况如表1所示，由于公开数据集3和校园网的流量数据集是没有标签的，因此对根因平均数不做计算；我们设置iDice[9], Hotspot[7]以及Squeeze[8]算法作为基线算法，并使用Rule Matching Index (RMI)来评估标记数据集的有效性。RMI基于Sorensen Dice系数（SDC），用于更真实地评估ground truth与模型报告的结果之间的准确性。

表格1. 数据集简述

图4. FTM-RCA和基线模型的实验结果对比

图5. 模型在不同大小的数据集上的执行时间对比

除此之外，FTM-RCA在真实网络中的应用也显示了其适用性。与之前最好的算法相比，FTM-RCA可以在3分钟内定位根因异常，而其他算法至少需要15.5小时的计算时间。

04 总结

突发事件的根因分析对于大型网络的维护和管理具有重要意义。本文提出了一种用于大规模网络根本原因分析的新技术——FTM-RCA。FTM-RCA通过使用CUSC进行粗粒度规则过滤来避免组合爆炸问题，并使用启发式搜索与下钻和剪枝策略来更精确地识别根因组合，从而实现了较高的准确率和较快的速度。在半合成公开数据集和实际网络流量数据集上的实验结果表明，FTM-RCA在精度和速度等方面均优于基线模型。

参考文献

（1）Y. Meng, Q. Zhang, X. Tang, W. Zhang and J. Wang, "FTM-RCA: A Fast Two-Stage Multi-dimensional Root-Cause Analysis of Network Anomalies," 2023 IEEE/ACM 31st International Symposium on Quality of Service (IWQoS), Orlando, FL, USA, 2023, pp. 01-10, doi: 10.1109/IWQoS57198.2023.10188732.

（2）F. Lin, K. Muzumdar, N. P. Laptev, M.-V. Curelea, S. Lee, and S. Sankar, “Fast dimensional analysis for root cause investigation in a large-scale service environment,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 4, no. 2, pp. 1–23, 2020.

（3）S. Yan, C. Shan, W. Yang, B. Xu, D. Li, L. Qiu, J. Tong, and Q. Zhang, “Cmmd: Cross-metric multi-dimensional root cause analysis,” in Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, ser. KDD ’22, 2022, p. 4310–4320.

（4）R. Bhagwan, R. Kumar, R. Ramjee, G. Varghese, S. Mohapatra, H. Manoharan, and P. Shah, “Adtributor: Revenue debugging in advertising systems,” in 11th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 14), 2014, pp. 43–55.

（5）G. Rong, H. Wang, S. Gu, Y. Xu, J. Sun, D. Shao, and H. Zhang, “Locating anomaly clues for atypical anomalous services: An industrial exploration,” IEEE Transactions on Dependable and Secure Computing, 2022.

（6）P. Jing, Y. Han, J. Sun, T. Lin, and Y. Hu, “Autoroot: A novel fault localization schema of multi-dimensional root causes,” in 2021 IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 2021, pp. 1–7.

（7）Y. Sun, Y. Zhao, Y. Su, D. Liu, X. Nie, Y. Meng, S. Cheng, D. Pei, S. Zhang, X. Qu et al., “Hotspot: Anomaly localization for additive kpis with multi- dimensional attributes,” IEEE Access, vol. 6, pp. 10 909– 10 923, 2018.

（8）Z. Li, C. Luo, Y. Zhao, Y. Sun, K. Sui, X. Wang, D. Liu, X. Jin, Q. Wang, and D. Pei, “Generic and robust localization of multi-dimensional root causes,” in 2019 IEEE 30th International Symposium on Software Reliability Engineering (ISSRE). IEEE, 2019.

（9）Q. Lin, J.-G. Lou, H. Zhang, and D. Zhang, “idice: problem identification for emerging issues,” in Proceed- ings of the 38th International Conference on Software Engineering, 2016, pp. 214–224.

（10）R. Agrawal, T. Imielin ́ski, and A. Swami, “Mining asso- ciation rules between sets of items in large databases,” in Proceedings of the 1993 ACM SIGMOD international conference on Management of data, 1993, pp. 207–216.

（11）F. Ahmed, J. Erman, Z. Ge, A. X. Liu, J. Wang, and H. Yan, “Detecting and localizing end-to-end perfor- mance degradation for cellular data services based on tcp loss ratio and round trip time,” IEEE/ACM Transactions on Networking, vol. 25, no. 6, pp. 3709–3722, 2017.

（12）G. Rong, H. Wang, Y. You, H. Zhang, J. Sun, D. Shao, and Y. Xu, “Locating the clues of declining success rate of service calls,” in 2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE). IEEE, 2020, pp. 335–345.

（13）V. Satopaa, J. Albrecht, D. Irwin, and B. Raghavan, “Finding a” kneedle” in a haystack: Detecting knee points in system behavior,” in 2011 31st international conference on distributed computing systems workshops. IEEE, 2011, pp. 166–171.

（14）N. Aryabarzan, B. Minaei-Bidgoli, and M. Teshnehlab, “negfin: An efficient algorithm for fast mining frequent itemsets,” Expert Systems with Applications, vol. 105, pp. 129–143, 2018.

（15）X. Zhang, C. Du, Y. Li, Y. Xu, H. Zhang, S. Qin, Z. Li, Q. Lin, Y. Dang, A. Zhou et al., “Halo: Hierarchy-aware fault localization for cloud systems,” in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021, pp. 3948–3958.

（16）X. Zhang, C. Du, Y. Li, Y. Xu, H. Zhang, S. Qin, Z. Li, Q. Lin, Y. Dang, A. Zhou et al., “Halo: Hierarchy-aware fault localization for cloud systems,” in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021, pp. 3948–395