Adaptive Performance Anomaly Detection in Distributed Systems Using Online SVMs

security

Alvarez Cid-Fuentes J , Szabo C , Falkner K . Adaptive Performance Anomaly Detection in Distributed Systems Using Online SVMs[J]. IEEE Transactions on Dependable and Secure Computing, 2018:1-1.

本文提出框架，通过周期地收集系统矩阵来提取特征，并采用在线SVM法训练和对特征进行分类从而识别异常行为：deadlock,livelock,unwanted synchronization,memory leaks。

BARCA 框架

BARCA由Behavior Extractor,Behavior Identifier,Feedback Provider组成。

• Behavior Extractor:定期收集Behavior Instance(BI)
• Behavior Identifier:将BI分类为nomal或abnomal,并使用统计模型调用Behavioral Model(BM).当分为abnomal时，Behavior Indentifier提醒Feedback Provider，由它决定是否通知管理员。

行为抽取(Behavior Extractor)

定期收集系统状态矩阵生成BI。假设系统状态矩阵$M=\{m_i|1 \le i \le n\}$,定义$r_{ij}$为在时刻j读取系统矩阵i，$s_{ij}=r_{ij},r_{i(j+1)},\dots,r_{i,(j+z)}$,z为slide window size，$B_j=\{s_{ij}|1 \le i\le n\}$。Behavior会再一次从BI中提取特征，而对异常行为的检测可转换为对这些特征偏移的检测。转换过程如下：

行为识别（Behavior Identifier）

SVM

支持向量机简介

Gradient Descent

参数更新

Data Normalization(数据归一化)

对待分类的向量进行归一化

$$x_i'=\frac{1}{1+e^{\frac{x_i-u_i}{\sigma_i}}}\ for\ 1 \le i \le n,$$
u被始化为最先接收到的向量，$\sigma$初始化为$\sigma=[1,1,\cdots,1]$
后续更新为：
$$u_i'=(1-\frac{1}{t})u_i+\frac{1}{t}x_i$$
$$\sigma_i'=(1-\frac{1}{t})\sigma_i+\frac{1}{t}(x_i'-u_i')^2$$
这里的x是最样接收到的向量，t为目前已处理的向量个数。

Two-setp Classification

利用单类分类器进行未知异常的检测，利用又类分类器进行识别已知异常。

• 单类分类器算法伪代码：
  
  单类分类器分为两个部分，CLASSIFY和UPDATE_MODEL。
  CLASSIFY用于分类，即正常的分类器，UPDATE_MODEL用于更新，即对分类模型进行训练用的，这里采用online-classify即分类和训练放在一起，没有单独的训练过程。
  在UPDATE_MODEL中，假设刚开始的一个时间段进来的所有数据都是正例，则这个时间段是用来训练单类分类器的，对进来的每一个向量利用核函数计算结果，若小于$\rho$则误分，反向更新$\rho$,否则正向更新。

• 双类分类器算法伪代码
  
  与单类分类器原理相似，只是这里的更新过程中的数据是有标签的，利用标签对分类器进行训练和参数更新。

• 平衡更新过程伪代码
  
  伪代码意思就是：利用正例更新一次模型就要利用负例更新一次，因为因为分类器会偏向实例多的那个类别。

• multi-class classifier(MC)
  
  多类分类器是由多个双类分类器组成的，它的作用是用来区分检测到的异常的类别，是由多个单类分类器组成的一个类似有向无环图（DAG）。

• 两步分类：由单分类器OC确定是否是异常，由双分类器BC加强结果，再由MC确定异常种类，如下图描述了这个过程：
  
  图中，OC用来检测未知异常，BC用来加强已探测到的异常，OC和BC产生的最终结果是第一步的结果，利用权重或其他方法来控制结果占比例，如果第一步的结果是异常，则移到第二步：MC，识别异常。

模型更新

在两步分类结果结交给Feedback Provider，而FP则会通知管理员，Behavior Identifier则会根据结果更新 Behavioral Model，如果是正常就更新OC,异常就更新MC，BC在两种情况下都要更新，且每个分类器的归一化函数独立。

Feedback Provider

FB的行为用以下的状态机来描述

在该状态机中，pred表示两步分类中的结果，fb则表示管理员那返回的结果，norm和anom表示连续的正常和异常数，负值表示正常，正值表示异常，FP在train阶段开始，这个阶段可选。Tr控制训练阶段的时常，如果Tr=0则表示没有训练阶段，训练结束FP移到Nomal状态，只要接收到的是正常的预测值，就一直待在这个阶段，如果接到异常，而移到Warning状态，接到异常预测状态会一直持续直到异常数量大于Gr,这里的Gr可以帮助控制误报率。当anom>Gr时，FP产生一个alert给管理员，update()将管理员的反馈传给Behavior Identifier，这个反馈可以用来更新BM。FP移到Alert状态，只要预测任是异常，FP就一直保持在Alert，在这个状态如果收到正常预测则返回到cooling，如果正常预测norm>Gr而返回Normal状态。如果管理员确认了异常，则移到Clean状态，FP待在这个状态进行z次（滑动窗口大小）观察，如果没有异常发生则返回正常状态。

Experiment

测试集中有四种异常：deadlock,livelock,unwanted synchronization,memory leak，每种异常系统的状态矩阵变化如下：

Features

本实难中由Behavior Extractor从矩阵中抽取，以下是在实验中抽取的特征：

异常检测

本部分主要分析以哪个作为特征用以捕获异常效果更好，以精确率和召回率为和指标作直方图(Gr=20,Tr=400,Windowsize=32,64,128,256)

在分析图后，采用混合特征来进行识别异常，$S_1=\{CO,ME,B0,S1\}$,以ME作为比较(Gr=20,Tr=400,window size=128)，结果如表2

以损失少数准确性为代价，大幅提高整体准确性。

Anomaly Identification

Gr=20,Tr=6000,z=128,作各特征比较直方图如下：

根据分析，LH特征效果最好，再选择$S_2=\{LH,IN\},S_3=\{LH,IN,EP\}$进行比较，结果如下表：

以S2作为分类集作混淆矩阵

可见效果还是很好的。