基于堆叠极限树集成算法的信息物理系统入侵检测方法

朱子龙 张立臣

(广东工业大学计算机学院 广东 广州 510006)

0 引 言

信息物理融合系统是一个由现代传感器、计算设备和网络技术集成为一体的系统[1]。物理世界的行为通过传感器网络传输到信息世界，由信息世界进行计算分析，发出控制指令，作用于物理世界。整个过程信息计算和物理过程进行了深度融合，其中的计算、控制和通信是以可靠、安全和实时的方式实施，不需要人为干预，形成一个协作和自治的闭环系统[2]。

CPS应用的快速增长，导致许多安全性和机密性问题的出现[3]。因为信息计算依赖于物理过程中传感器收集的数据，而这些数据需要通过网络进行传输，同时，物理过程中接收的控制指令也需要通过网络进行传输。因此，CPS设备的自治性会导致入侵和攻击的风险[4]。CPS的安全问题越来越受到业界的关注[5]。

文献[6]设计了在智能电网中使用的分布式入侵系统，通过大量的流量分析模块，结合人工免疫系统(Artificial Immune System,AIS)和支持向量机(Support Vector Machine,SVM)检测网络流量中的攻击行为。文献[7]提出了基于EBP神经网络的规则学习算法，从实验数据的ICMP分组中提取特征，输入到EBP神经网络中进行训练，使网络学习其中的规则对网络异常行为进行识别。文献[8]提取了DoS(Denial of Service)攻击下的网络流量特征，结合K-近邻(K-Nearest Neighbor，KNN)等机器学习算法对正常和攻击行为进行区分。文献[9]将PCA与核函数空间结合，实现对非线性结构的网络数据进行异常检测。文献[10]运用稀疏自编码网络进行降维，结合LightGBM算法进行分类，以二叉树的形式处理网络攻击分类的多分类问题，并在NSL-KDD标准数据集上对算法准确率进行对比实验。文献[11]搭建了一个电源系统试验台，并辅以网络监控设备，采集其中的网络流量信息运用Adaboost集成学习框架，结合JRipper规则学习算法，对电力系统中的异常行为进行检测，并与常见的机器学习算法进行对比。文献[12]提出了两种适用于CPS环境的入侵检测系统，一种是基于K均值聚类算法，另一种基于自组织映射网络(Self-Organizing Map,SOM)。实验显示两类入侵检测系统提高了检测速率和精度，可以便捷地部署在CPS环境中。基于上述工作应用于CPS入侵检测时的缺陷，需要继续优化算法应对高维数据的能力，进一步提升算法的速度，使其能满足CPS入侵检测对实时性的要求。

本文贡献在于：

(1) 提出一种结合相关性特征选择的堆叠极限树集成算法(CFS-SET)。首先通过基于相关性的特征选择算法，结合最佳优先(BestFirst)的搜索策略，对信息物理融合系统的数据特征进行筛选，选择出关联性较高的特征。能够有效地为后续的分类算法降低输入量，减轻计算压力，以达到信息物理融合系统实时分析的需求。后续选择的极限树算法，会随机选择特征，因此剔除掉关联性较低的特征将会进一步提升算法的整体表现。

(2) 将极限树算法引入信息物理融合系统入侵检测，将其作为Stacking集成算法的基学习器，虽然其算法复杂度与一般的树算法相同，同为NlogN，但是考虑到节点拆分过程的简单性，其常数因子比其他基于局部集成优化切点的方法更小。进一步提高分类速度，优化信息物理融合系统的运算时间。

(3) 使用Stacking集成学习框架，同时训练若干个极限树，将其输出送入逻辑回归分类器。采用这种堆叠式模型来提高预测的准确度，改善分类性能，同时最小化泛化错误率，增强算法的鲁棒性。本文将使用密西西比州立大学的电力系统标准数据集Power System Dataset进行实验，验证本文算法的有效性。

1 基于CFS的特征选择算法

CPS所产生的数据往往呈现出数据量庞大、特征众多的特点。一般的机器学习算法面对如此庞大的高维数据，计算所需要的时间将会直线上升，不能满足CPS对算法实时性的要求。并不是所有的特征都有利于算法的学习，其中存在着大量的冗余和不相关特征。面对高维数据，通常有降维算法和特征选择两种方式。降维算法通过挖掘特征深层的信息来达到降维的目的，缺点在于每次进行预测的时候都要对输入的特征进行降维，需要额外的时间开销。特征选择则可以选出有价值的特征，在对模型进行训练和预测的时候直接选择这些特征作为输入，减少时间开销。为了满足CPS实时性的需求，本文用特征选择算法对高维数据进行预处理。

1.1 特征选择算法概述

特征选择算法可以分为三个大类：过滤式(filter)、包裹式(wrapper)和嵌入式(embedding)。过滤式方法直接对所有特征进行筛选，保留样本对应的特征数据，送给后续模型进行训练，对特征进行选择的过程与后续模型的性能没有关系，仅仅关注数据集的特征本身。包裹式方法则是根据后续模型的分类性能作为特征，反过来矫正需要的特征，所以结果与模型直接相关。从最终模型的分类性能来看，因为针对所使用的特定学习算法对特征选择进行了优化，所以包裹式往往比过滤式的效果更好。包裹式的缺点是在进行特征选择的时候需要反复的训练模型，计算开销往往大于过滤式，尤其是当模型本身的计算非常复杂的时候。同时因为包裹式与后续模型结合太过紧密，一旦更换后续的模型，必须重新运行特征选择算法。嵌入式与上述两种特征选择算法不同，嵌入式方法没有明显的特征选择过程，它的过程是融合在模型训练的过程中，也就是说模型在训练过程中自动地进行了特征选择。

本文将特征选择引入集成算法当中，将其作为整个算法改进的一部分，具体是选择过滤式特征选择算法。它可以减少学习所需的数据量，提高预测准确性，使学习的知识更紧凑，更容易理解以及减少执行时间，不需要针对不同的学习算法重新执行。CPS是一个对实时性要求很高的系统，所以过滤式相比于其他两种特征选择算法，更符合CPS入侵检测算法的需求。

1.2 CFS特征选择算法

CFS是一种基于特征之间相关性的过滤式特征选择算法，可以快速识别并筛选不相关、冗余的特征，并在不严格依赖其他特征的情况下识别相关特征。CFS是一种全自动算法，不需要用户指定任何阈值或要选择的特征数量，同时，CFS是一种过滤式特征选择算法，因此不会重复调用学习算法而增加计算成本[13]。

CFS使用基于相关性的启发式评估函数对特征子集进行排名。评估函数偏向于包含特征与类别高度相关，特征与特征之间彼此不相关的特征的子集。与类别没有关系的特征应该被忽略，同时冗余特征应该被筛选出来，因为它们与一个或多个特征高度相关。其评估的形式化定义如下：

(1)

最佳优先搜索策略可以选择从没有特征或所有特征开始搜索，如果选择从没有特征开始搜索，会通过添加单个特征的方式在搜索空间中进行；如果选择从所有特征开始搜索，则会通过删除单个特征的方式在搜索空间中进行。如果有五个连续完全展开的子集对当前的最佳子集没有提升，则搜索将终止。由于在对特征子集进行相关性评价的时候，需要使用离散化的变量来进行计算，如果特征属性是数值型，则应当先对数值型数据进行离散化。图1展示了CFS进行特征选择时对训练集和测试集的具体流程。

图1 CFS特征选择算法流程

2 基于堆叠极限树的集成算法

2.1 极限树算法

极限树算法使用经典的自顶向下的过程构建未修剪的决策树。与其他基于树的算法的区别主要有两点，一是极限树通过完全随机的方式选择切点来分割节点，二是极限树在生长的过程中使用整个学习样本。

对于评分机制，本文使用文献[14]中的评分机制对需要进行随机选择的属性进行评价，选择其中评分最高的划分属性。在分类问题中，用信息增益来定义评分函数，对于当前划分节点，式(2)为评分度量。

(2)

算法1Single Extra Tree生成算法。

输入：训练集D={(x1,y1),(x2,y1),…,(xm,ym)}, 属性a。

输出：极限树，划分属性。

Step1如果|D|

Step2将node标记为叶节点并返回。

Step3从所有候选属性中随机选择K个属性{a1,a2,…,aK}。

Step4形成K个划分{s1,s2,…,sK}，式(3)对si计算进行了定义。

si=Pick_a_random_split(D,ai) ∀i=1,2,…,K

(3)

Step5由Score(d*,D)选择出最好的划分值d，其分数计算如式(4)所示。

(4)

Step6依据d*将样本集D分割成两个样本子集Dl和Dr。

Step7使用样本子集Dl构造左子树tl=Build_an_extra_tree(Dl)，使用样本子集Dr构造右子树tr=Build_an_extra_tree(Dr)。

Step8根据d*建立节点，tl和tr分别是它的左子树和右子树，形成一棵极限树并返回。

Step11划分属性[a

2.2 结合相关性特征选择的堆叠极限树集成算法描述

单棵极限树随机性太强，一般会使用随机森林的思想，生成众多极限树组成极限森林来提高整个算法的稳定性。但生成大量的极限树需要额外的时间和内存开销，不能满足CPS入侵检测对实时性的要求。本文提出将极限树算法和Stacking集成算法进行结合，使用极限树作为Stacking集成算法的基学习器，由于极限树的随机性，符合Stacking集成算法对基学习器之间存在差异的需求。堆叠极限树可以提升算法的稳定性，提高泛化精度。

为了能够进一步满足CPS入侵检测对实时性的要求，本文结合相关性特征选择算法和堆叠极限树算法，提出CFS-SET算法。在CPS的入侵检测中，数据常常呈现特征众多、维度高的特点，造成算法运算时间长和性能不佳的效果。采用相关性特征选择算法(CFS)，结合最佳优先(BestFirst)的启发式搜索策略，可以自动地从入侵数据的众多特征中选择出有用的特征，减少后续分类算法的训练和预测时间。同时，因为极限树是随机地选取特征来生长一棵树，所以特征选择有助于提高单棵极限树的性能。使用选择出的新特征组成新的训练集和测试集，将其送入后续的堆叠极限树(SET)算法中。堆叠极限树算法是将若干个极限树模型作为基分类器，向这些分类器中送入相同的训练数据进行训练。所有分类器输出的预测结果合并成一个新的特征，输入下一层的逻辑回归分类器进行训练。算法中使用的极限树具有随机性，改变随机种子后即可生长出两棵完全不同的极限树，所以其堆叠的数量很重要，过多的堆叠数量会导致计算时间过长，过少的堆叠数量无法获得良好的检测性能。因此对极限树的堆叠数量进行了实验，综合计算时间和检测性能，实验选择使用5棵极限树进行堆叠。算法本质是一个二层的结构，算法框架如图2所示，可以看出算法主要包含特征选择和Stacking两部分。其中：TrainingData和TestingData为训练集和测试集数据；CFS为相关性特征选择算法，具体流程如图1；CFSTrainingData和CFSTestingData为经过特征选择算法筛选后训练集和测试集数据；ExtraTree-1、ExtraTree-2等是5棵不相同的极限树作为Stacking中的基学习器；Pred-1、Pred-2等是各个基学习器产生的预测结果；MergeData是合并了基学习器预测结果的数据集；logisticsregression是第二层的逻辑回归模型。

图2 CFS-SET算法流程

具体步骤为：

(1) 将具有m个特征的训练集TrainingData进行相关性特征选择(CFS)，选择出n个特征的训练集CFSTrainingData。

(2) 从具有m个特征的测试集TestingData中挑选出相同的n个特征，组成测试集CFSTestingData。

(3) 将5份相同的训练集CFSTrainingData分别送入5个不同的ExtraTree中，使用10折交叉验证来训练，训练出5个不同的ExtraTree模型，并输出5份对应的预测结果。

(4) 将5份不同的预测结果合并成一个全新的数据集，作为训练集送入下一层逻辑回归进行训练。

(5) 保存整个模型，训练结束。

值得注意的是，虽然基学习器使用的都是极限树，但因为设置了不同的随机种子，每棵树在分裂的时候会进行随机的分裂，生长成不同的树，所以是互不相同的模型，各自得到的输出也不同。使用Stacking的目的主要是获得尽可能高的泛化精度(与学习精度相反)，其中心思想是，比简单地列出与训练集一致的父函数的所有预测结果做得更好。它通常可以结合多个基分类器的优点，提高泛化性能，并且表现稳定。

3 仿真测试

为了验证本文提出的CFS-SET算法的有效性，本文使用密西西比州立大学关键基础设施保护中心2014年建立的电力系统数据集(Power System Datasets)[15]对本文算法性能与几种代表性的机器学习和集成学习算法进行比较。测试硬件平台为：Windows 10专业版64位操作系统、Intel(R)CoreTMi7-4700HQ CPU @ 2.40 GHz处理器、8 GB内存。使用Python语言对数据进行预处理，使用Weka[16]作为机器学习算法框架进行比较。

3.1 数据预处理

Power System Datasets数据来源于一个二进线三母线智能电力系统对37种事件的仿真。现代电力传输系统依靠传感器进行远程监控。其数据包括电压和电流等测量值以及系统设备的状态，如继电器、断路器和变压器等。智能电网作为CPS在现实中应用最广泛的场景，是验证本文算法的理想环境。

本文着重于识别威胁CPS正常运作的入侵事件，所以选择对事件进行二分类的分类方案。整个数据集被分为37个事件场景，其中：28个事件为攻击行为；9个事件为正常操作。数据来自15个数据库，随机抽取1%的数据以减小大小并评估小样本大小的有效性，组成15个数据文件。表1列举了攻击行为和正常操作的序号分类。

表1 二分类事件具体分类表

Power System Datasets数据集共有78 377个样本，每条样本数据的存储形式为X=(x1,x2,…,xn,y)，每条样本数据具有128个特征属性(其中116个测量值由4个同步仪产生，余下的12个测量值来自控制面板日志、中继日志和Snort警报)和1个类标签。由于数据量充足，本文剔除了属性存在缺失值的数据。同时由于特征属性离散和连续数值混合，本文对数据进行Z-Score标准化处理，根据式(5)将数据转化为标准正态分布。

(5)

式中：x是个体观测值；μ是总体数据的均值；σ是总体数据的标准差。

3.2 分析方法

本文将采用以下评估指标来衡量用于CPS入侵检测任务的算法性能。

准确率指的是算法正确分类的样本数量与总体样本数量的比值。虽然准确率可以判断总体的准确率，但是在样本不平衡的情况下，可能会出现高准确率但其结果含有很大水分，不能准确反映分类性能。比如当正常操作的样本数量很少的情况下，极端地将所有的类别预测为攻击即可获得很高的准确率，显然，这不能准确地反映算法的性能。准确率利用式(6)进行计算。

(6)

式中：TP(真正例)表示攻击行为被正确分类的数量；TN(真反例)表示正常操作行为被正确分类的数量；FN(假反例)表示攻击行为被错误分类的数量；FP(假正例)表示正常操作行为被错误分类的数量。

精确率衡量的是，算法识别出的正例中算法预测正确的百分比，即算法分类为攻击行为的样本中，真正是攻击行为的比率。精确率越高代表算法的误报率越低。精确率利用式(7)进行计算。

(7)

灵敏度衡量的是正确识别出正例的比率，即算法正确识别出攻击行为的百分比。灵敏度越高代表算法的漏报率越低。利用式(8)可以计算出灵敏度。

(8)

F1分数指的是精确度和召回率的调和平均值，其值在0到1之间，当F1分数较高的时候说明算法分类性能较好。式(9)给出了F1值计算方法。

(9)

3.3 实验结果分析

图3展示了结合相关性特征选择的堆叠极限树集成算法(CFS-SET)和另外6种常见的经典机器学习算法在15个数据集上的分类准确率。分类准确率是通过在每个数据集上进行10折交叉验证，取得的分类准确率计算出的均值。可以看出，7种算法无论应用于15个数据集的哪个数据集，结果都是一致的，虽然有细微的变化，但分类表现都是相对稳定的。其中表现最好的两种算法分别是CFS-SET和Random Forests，分类准确率都在95%以上。作为基学习器的Extra Tree和Nearest Neighbor算法分类准确率能达到90%。

图3 15个数据集上分类准确率

图4显示了15个数据集上不同算法的平均精确率，其中每个数据集使用10折交叉验证的方法。精确率在本例中的含义是识别出的真正是攻击行为的数量与总的攻击行为数量之间的比值。精确率越高，代表算法越不会将正常的操作行为误报为攻击行为。在7种算法中，CFS-SET和Random Forests的在15个数据集上的平均精确率表现最佳。

图4 平均精确度

图5显示了15个数据集上不同算法的平均漏报率，其值是根据1-Sensitivity来确定的，其中每个数据集使用10折交叉验证的方法。可以看出SVM在漏报率上表现非常出色，15个数据集没有误报的情况发生，但结合精确率可以发现，SVM在精确率上表现很差，也就是说这种低漏报率的表现是通过高误报率换来的。在实际环境中，这种算法对决策者的价值很低，因为其分类表现是不可靠的。AdaBoost、CFS-SET和Random Forests的漏报率在0到0.1之间，表现良好。

图5 平均漏报率

图6显示了所有数据集的平均F1值，它本质上综合了分类性能的精确率和灵敏度。可以更好地反映出算法的分类性能。可以看到CFS-SET和Random Forests拥有最高的F1值，都达到了0.979。说明CFS-SET算法在分类性能上与Random Forests基本相当。

图6 平均F1值

在CPS中进行入侵检测不仅需要算法的分类性能良好，还需要满足CPS对算法实时性的要求，即算法的模型建立时间和预测时间要尽可能的短，否则即使算法的分类性能出众，也无法应用于CPS的入侵检测中。表2展示了每个算法进行10折交叉验证时，平均每折的耗时和10折总耗时情况。可以看出上文分类性能相当的CFS-SET和Random Forests算法，在计算时间上，CFS-SET算法只用了Random Forests算法的1/5的时间。可见在总体性能表现上，本文提出的CFS-SET算法更好地兼顾了分类准确率和计算时间两者间的平衡。

表2 模型运行时间汇总表 单位:s

4 结 语

利用基于特征之间相关性的特征选择算法，快速筛选出关联性高的特征，抛弃冗余和不相关的特征，这样可以加速后续的分类算法。使用Stacking的集成算法框架，提升算法的泛化能力，减少单棵极限树随机性太强带来的偏差。实验结果表明，本文提出的CFS-SET方法能够从众多的入侵数据特征中过滤出真正有用的特征，进而提升分类效率。对比其他常见的机器学习算法对CPS环境中的攻击行为检测，更好地兼顾了误报率和漏报率，F1值达到了平均0.979。同样使用集成算法思想的Random Forests算法也达到了与CFS-SET相同的F1值。但在实时性方面，CFS-SET算法只使用了Random Forests算法1/5的计算时间。本文将随机性很强的极限树算法进行堆叠，改善其因为随机性带来的分类性能不佳的问题，吸收其计算速度快的优点，使CFS-SET算法同时兼顾分类性能和分类时间，使得将其应用于CPS入侵检测成为可能。本文进一步的工作将考虑把CFS-SET算法推广至多分类的CPS入侵检测中，能够对不同的入侵检测行为进行分类，同时需要考虑多分类情况下，类别不均衡对分类算法的影响。将上采样和下采样技术融合入CFS-SET算法中，保持甚至提升算法在多分类情况下的分类性能和计算时间，能够继续应用于CPS入侵检测的多分类领域。