2.5 基于日志数据的异常检测

从数据挖掘技术的角度分析，利用日志数据进行异常检测的方法大致分两类：一类是基于监督的；一类是基于无监督的。

2.5.1 基于监督学习的异常检测

基于监督学习的方法就是分类。对于系统异常检测问题，这里的类别一般就是两类：“正常”和“异常”。其本质问题就是，判定一个事件、一个用户或者一个操作是“正常”还是“异常”。例如参考文献[31]介绍了利用基于SVM的分类学习算法来判定Insider Threat。这里Insider Threat是指极少数异常并企图攻击内部系统的用户。在大型企业、学校以及政府的开放服务器系统内，通常都有几十甚至几百的用户数量。这些用户来自不同的部门甚至外部公司，所以并非每个用户都是可靠的使用者。极少数用户会试图跨越本身用户等级，获取系统更高层的权限和秘密的数据。这类用户就被称为Insider Threat。通常UNIX系统和Windows系统都会记录每个用户操作，包括系统调用、执行命令。参考文献[31]通过收集正常用户和异常用户（lnsider Threat）的用户日志数据，创建有类别的训练数据。这里的类别就是“正常”和“异常”。然后利用SVM训练算法训练得到一个SVM分类器，来对其他未知用户进行判定。

在结构化的日志数据里，训练数据的属性就是一个日志事件的字段信息。在非结构化的日志数据里，可以把一条日志消息当成一段文本，利用文本分类的方法来训练分类模型。整体来说，基于监督学习的异常检查都可以被归纳为学习一个分类函数：

其中，x是一个（或者一段）日志事件，y∈{0,1],y=0表示“正常”,y=1表示“异常”。以朴素贝叶斯分类器为例，分别以结构化和无结构化的日志事件的例子来描述如何判定异常的系统日志事件。

（1）结构化的日志事件

假如x是一个结构化的系统日志事件，且有如下若干属性：

在贝叶斯学习里，分类函数 f(x)是用条件概率模型来表达的，f(x)=p(y|x)。p(y)是先验概率，p(y|x)是后验概率。在朴素贝叶斯里，对于给定的 y,x 被表示成若干独立不相干的属性集合[32]，因此：

这里x是给定的，所以p(x)是常量。各个属性的值，诸如process_name、cpu_utilization等也是给定了的。唯一的变量就是y,y可以是0或者1。分子里的各个概率，p(y=0)、p(y=1)、p(process=′rtvscan.exe′|y=0)、p(process=′rtvscan.exe′|y=1)等在训练数据里计算得到。从最终分类的结果比较 p(y=0|x)和 p(y=1|x)的值。如果 p(y=1|x)>p(y=0|x)，那么就断定x是异常的。

（2）无结构化的日志事件

无结构化的日志事件分析方法主要来源于传统的文本挖掘技术。文本挖掘和信息检索主要研究如何处理文本数据。针对文本数据的模型建立方法千差万别。这里所谓的模型建立，在分类问题上就是指如何构造分类的属性空间（Feature Space）。例如信息检索里面提出的Bag-of-Word模型[33]将每个词当成一个属性（Feature），那么分类模型的属性空间就是一段日志数据中出现的所有词。以图2-6显示的一段PVFS2[34]运行日志为例。

假设将这3条日志数据视作一个事件，那么将这个事件表示成为一堆词（或者token）。

用朴素贝叶斯分类函数可以表示为：

其中p(w|y)表示词w在y类别的日志事件内出现的概率，它是从历史数据中计算得到的。直接使用朴素贝叶斯的方法通常还比较粗糙。日志里面出现的大量数字等词一般只出现一次，比如这里的线程 ID（0x9527208），是随机产生的。历史数据里的 ID 不一定会在未来数据里出现，所以在贝叶斯模型里计算这个词的条件概率并没有意义。通常的处理方法是预先过滤掉频率极低的词，例如只出现1次或者2次的词。这些低频词可以被当成分类模型的噪声数据。除了线程ID，有些定量的观测值也是有意义的，比如一个I/O吞吐量。当I/O吞吐量异常变大时，系统肯定是有异常事件发生，但是具体的I/O吞吐量的数值可能不会在历史数据里出现。对于贝叶斯分类模型来说，所有的属性都是离散的，那么解决方法就是将这些具体数值离散化。比如，可以将I/O吞吐量划分成3个区间：“高”“中”“低”。如果历史数据中，每次出现高吞吐量都意味着异常事件发生，那么未来运行中若出现高吞吐量，就可以加重对异常发生概率的估计。至于如何划分区间，这个涉及数据预处理和人工干预的部分，我们不在此详细讨论。

朴素贝叶斯的方法虽然十分简单粗糙，但是在很多运行日志分析里是符合人类的直观分析经验的。例如当人工扫描PVFS2的运行日志寻找系统的异常时，通常会很快过滤掉大量pthread线程操作或者磁盘I/O的统计信息。如果看到某次日志出现exception、error等相关的词，通常经验就告诉我们这里极可能是问题所在。同理，虽然贝叶斯算法并不知道这些pthread线程操作的函数和磁盘I/O函数的具体意义，但是通过历史数据统计的结果是这些词出现的时候，异常出现的概率极低，而当出现exception、error等相关词时，异常出现的概率陡增。

（3）非平衡数据的分类

异常检测的分类数据通常都是非平衡的。非平衡的意思就是绝大部分样本是“正常”的，只有极少数是“异常”的。很多分类算法都是从整体分类的结果评估精度，所以极少数“异常”样本会被忽略。例如上文所述的朴素贝叶斯，因为p(y=异常)的先验概率太低了，即便出现异常情况的几个词，分类算法还是有可能将这个事件归为“正常”。又如SVM分类器，它的优化模型是最小化整体的训练错误个数，但是不具体区分到底是哪一类错误。由于“正常”样本的数量远大于“异常”样本的数量， SVM 最终得出的分类平面会更偏向于“异常”的区间，因为这样即便“异常”样本容易被分错，但是对于整体的训练错误个数来说是相对较小的。如果SVM最终的分类平面偏向于“正常”的区间，那么一旦出错，就有可能是错一大片的样本。人们对待“正常”和“异常”事件的重视度是相反的。若正常事件被误报为“异常”，对系统影响不大。但是若“异常”事件被忽略掉，引发的后续系统问题可能很严重。

非平衡数据下的分类问题大致有两类解决办法。第一类是通过采样的方法让训练数据集平衡，以 SMOTE 算法[35]为代表。具体的采样方案可以是 under-sampling和 over-sampling。under-sampling 就是只取小部分的“正常”样本，减少“正常”样本的数量。over-sampling则是重复采样“异常”样本，增加“异常”样本的数量。最终得到一个平衡的训练样本集，虽然里面可能有很多重复的样本，但是可以避免分类算法的偏差。under-sampling 的方法适用于“正常”样本和“异常”样本的绝对数量都大的时候。在实际的系统日志训练样本集里，很可能“异常”的样本数量极少到只有几十个甚至几个。如果采用 under-sampling 来维持数据集的平衡，最后得到的训练样本集就极少，丢失了很多数据信息，因此此方法并不可取。直接的over-sampling会增加整体训练数据集的大小，重复采样“异常”样本，导致分类模型在描述“异常”样本区间的时候发生过度拟合。SMOTE算法采用的over-sampling会在重复采样的“异常”样本上增加一些属性的细微变化[35]。over-sampling的缺点是让训练数据集增大，特别是在多类别的分类数据集上。

第二类办法是加入样本的权重值，计算带权值的分类模型的分类函数 f(x)，如Cost-Sensitive SVM可以指定每类样本的权值。最终优化的目标函数被改成一个错误样本的加权求和。因此，只要让“异常”样本的权值大于“正常”样本的权值，即便“异常”样本数量少，也不会被忽略。常见的 SVM 算法包（如 LibSVM[36]和SVMLight[37]）都带有权值的设置。样本加权的优点是不用改变训练数据集，不会增大或者丢失原始训练数据。但是它的缺点是权值的调整通常是很困难的。需要注意的是，在很多分类模型里，权值并不直接反映其类别的样本的实际重要性，它还依赖于分类模型和数据集的分布。如果用户对原始数据集的分布不了解，通常唯一的办法是通过不断改变权值来测试SVM的效果（Cross-Validation）。

2.5.2 基于无监督学习的异常检测

无监督学习的异常检测指不需要提供标注的训练数据集的检测方法。标注的训练数据集通常很难收集，而且还有上述的非平衡数据集问题，所以基于无监督的学习方法应用更加广泛。简单来说，基于无监督学习的异常检测是异常点的判定。大致方法是通过数据挖掘里的聚类分析找出远离类簇的数据点。基于此类方法的异常检测都有一个大前提假设：异常的日志事件出现的概率远小于正常的日志事件。

以一个简单的例子来说明如何利用聚类分析中的离群点来判定异常的日志事件。假设现在要分析的日志数据是一个检测进程的结构化日志。每个日志包含两个属性：CPU使用率和内存使用率。图2-7显示出收集到的数据样本分布。正常情况下，CPU和内存使用率都是居中或者呈现一个正态分布的，如图2-7中的“簇”显示。图2-7右上角的离群点代表一个高CPU利用率、高内存利用率的日志事件。这个离群点远离常规的数据分布，因此可以断定此事件是异常事件。在数据挖掘技术里，离群点分析依赖聚类算法。可以先调用常见的聚类算法（如k-means[32]、DBScan[38]等）先找到聚簇。然后遍历每个数据点，计算其到最近一个聚簇的距离。如果这个距离值远大于其他大部分点，那么这个数据点即可被判定为离群点。

当然现实世界里的实际系统不可能那么简单。主要的难点在于，离群点可能并不是如图2-7显示的那么明显。在高维度的数据集内，数据点的分布可能都十分稀疏（Curse of Dimensionality）[32]。对离群点的寻找还需要在子空间内（Subspace）进行。参考文献[25]介绍了一种利用主成分分析（Principal Component Analysis，PCA）[32]寻找子空间，并通过子空间的离群点来判定系统异常的方法。

图2-8展示的是磁盘I/O的日志事件分布。这里只抽取了事件的2个维度：Active的I/O进程数量和I/O操作提交的速率。I/O进程数量和提交操作的数量是根据当前系统运行业务逻辑决定的，所以不能只依据这两个指标的大小来判定异常情况。但是，在正常情况下两个指标却有明显的线性关系。显然，在正常情况下I/O进程越多，提交的操作也相应越多。从图2-8中可以看出，这个数据分布很难找到一个簇去概括所有正常数据点。但是，当把数据线性变换到一个子空间S之后（投影到S的法线），就会发现其实大部分数据落在S直线上。从S的法线角度去看，这些正常数据都落在法线上的一个1维的簇内。原始数据空间是2维的，它的子空间则是1维或者0维度的。1维空间表现是一条直线，0维空间表现是一个点。如图2-8所示，最上面的离群点明显偏离子空间 S，因此它被判定成为离群点（异常事件）。而这个离群点到正常子空间S的距离（SPE）则用来度量其异常的置信度。显然SPE越大，其事件的异常可能性越大。

2.5.2.1 子空间聚簇分析

参考文献[25]利用PCA的方法寻找子空间S是基于如下的大前提假设的：大部分运行日志事件都是正常情况，只有极少数的事件是异常情况。PCA试图找到最大k个子空间去表达全部原始数据。因为异常数据点极少，所以这7个表达全体数据集的子空间也近似于表达全部“正常”数据点的子空间。在实际的应用环境下，有个具体的问题就是如何知道哪些子空间能很好地适合给定的一个数据集。在对日志异常事件的分析里，很多工作都是因为分析人员已经有此类的先验经验，然后通过各种子空间具体测试得出结论。

在数据挖掘领域，也有一些自动的方法寻找合适的子空间聚簇，如 GPCA、k-subspace[39]、CLIQUE[40]、SUBCLU[41]等算法。这些算法还允许空间内有多个子空间描述一类数据，例如图2-8可以有多个直线空间描绘正常的数据点。在高维度的原始数据下寻找合适的子空间却并不容易。在数据挖掘里，子空间的聚类分析大致可以分为两种情况。

一种是假定子空间的坐标轴跟原始坐标轴是并行的，即垂直投影可以获取的子空间。假设原始数据空间是d维的，那么任意{1,2,…,d}的子集都可以构成一个子空间，总共有2d个子空间的可能性。当d大的时候，取每个子空间先做投影变换再做聚类分析，至少要做2d次，显然是很低效的做法。大部分针对此类问题的算法利用一种叫作downward-closure的性质：给定任意一个空间T,T包含一个聚簇，所有T的子空间S（即S⊆T）也必然包含该聚簇。

换句话说，若在高维度的空间内找到一个聚簇，那么无论怎么并行投影到一个子空间内，这个聚簇内的数据点在子空间内依旧是一个聚簇。用欧氏距离计算也可以很好地解释这一性质。假设当前空间T是d维度的，任意两个点x=(x1,…,xd)T和y=(y1,…,yd)T如果在一个聚簇内，即满足：

其中ε是簇内距离的最大阈值，那么在其任意子空间，也存在：

这里用维度集合来表示一个空间。一个维度集合的超集称为其表达空间的超空间；一个维度集合的子集称为其表达空间的子空间。

通过downward-closure的性质，可以减少一定的子空间搜索范围。子空间的搜索算法大致有自底向上法和自顶向下法。自底向上的方法是先从低维度空间找聚簇。如果一个低维子空间内不存在任何聚簇，那么其超空间肯定也不存在这样的聚簇，因此算法就不用再搜索其超空间。自顶向下的方法则是先找出存在聚簇的空间，排除这些空间（因为其子空间肯定也存在聚簇），然后继续寻找不存在聚簇的空间的子空间集。这些算法和基于关联规则挖掘算法与Apriori性质的频繁子集挖掘算法类似[32]。

另外一种是严格按照线性代数描述的线性子空间（Linear Subspace）。这种线性子空间可以由任意一个线性变换矩阵得到。例如原始 d 维空间内的一个数据点x=(x1,…,xd)T,P是一个p×d矩阵，1≤p≤d，那么x投影到子空间内就是Px。Px是一个p维的数据点。因为矩阵P可以有无穷个，所以这种线性子空间的数量是无穷多个。在子空间聚类分析里，人们通常还加入一些其他的约束条件或者启发式的规则去限制可能的线性子空间。广义主成分分析（Generalized Principal Component Analysis,GPCA）是一个典型的线性子空间寻找算法[42]。GPCA是一种扩展形式的PCA方法。PCA是寻找一个k（k≤d）维度的子空间，并使其所有数据点都落在这个子空间内。GPCA 则是找多个 k（k≤d）维度的子空间，并让所有数据点落在其中某个子空间内。GPCA算法的思想十分简单。因为一个线性子空间在原始空间内就是采用一个线性方程表达的，那么 n个线性子空间则表示成 n个线性方程：,i=1,…,n，其中bi是一个k元的系数。如果某个数据点x落在某一个子空间，则这个数据点满足：

GPCA算法的目标就是求出系数b 1,…,bn。显然，数据点不可能完全落在某个平面内，那么问题则变换成一个最小化的问题：寻找k元系数b1,…,bn，使其能够最小化：

其中D是给定数据点集。具体的近似优化算法见参考文献[42-44]。

2.5.2.2 小结与讨论

本节主要讨论基于无监督学习的日志异常检测方法。值得注意的是，无论任何一种方法，所有找出的离群点并非就一定是异常的。例如系统启动的时候，通常会产生一些非常见的日志信息。这些日志信息虽然不常见且远离数据分布的簇，但不一定就是异常。本章讨论利用聚类分析中的离群点判定异常的方法都是启发式的。前面说过，基于离群点的异常检查都有一个大前提：异常的日志事件在整体数据上是比较罕见的。如果一个系统被错误地配置，从一开始启动到运行故障一直都产生错误异常的日志，那么这个假设的大前提就不成立。若此时利用离群点的办法进行判断，有可能找出的离群点反倒是正常的日志事件。

因为无监督的学习方法没有一个黄金标准可以判定异常，所以某种启发式判定准则在另外一个应用系统或者日志数据内就一定有效。以聚类分析的离群点来讨论是因为这个启发式规则是具有一定普遍性规则的，但并非绝对。