开放科学（资源服务）标志码（OSID）：

0 概述

随着网络技术的飞速发展，网络攻击行为的识别问题在网络安全领域中备受关注。入侵检测系统（Intrusion Detection System，IDS）已成为一种广泛使用的信息安全保障技术^[1]。IDS的主要作用是监控和收集实时的数据节点，通过分析网络流量以发现恶意活动的迹象，建立相应的分类模型和评估机制，从而判断是否为安全数据并采取相应的措施。网络信息安全的发展同时也伴随着入侵病毒类型的增加。入侵病毒逐渐呈现大规模、多步协同、分布式处理等特点，普通的单一检测无法应对不同类型病毒的攻击^[2]。在一些要求高可靠低容错的网络系统领域（如远程医疗、工业控制）中，保证入侵数据预测的高可靠性具有重要意义。

研究人员提出一系列基于机器学习的IDS相关算法，如支持向量机（Support Vector Machine，SVM）^[3-4]、决策树（Decision Tree，DT）^[5-6]、随机森林（Random Forest，SF）^[7-9]、贝叶斯网络（Bayesian network）^[10]、人工神经网络（Artificial Neural Network，ANN）^[11-13]、K近邻（K-Nearest Neighbor，K-NN）^[14-15]算法等，并有效地应用在IDS中。文献[6]构建一种基于粗糙集理论的增量DT算法并应用到IDS中。该算法在处理一条新数据时，只需更改活动决策树中的某个已知子节点或添加一个新子节点，无须重建整个决策树，从而提高增量决策树的计算效率。文献[10]提出针对无线传感网络的局部时间序列异常检测算法，该算法利用贝叶斯网络对每个传感器节点采集的数据进行异常检测与预测。文献[16]提出一种应用于智能电网的分布式IDS框架，利用SVM和人工免疫系统分类算法确定入侵时间、入侵类型和入侵发起者，从而解决智能电网来自物理层和网络层的入侵攻击。文献[17]提出将Elman神经网络（Elman Neural Network，ENN）和鲁棒SVM相结合的入侵检测方法。该方法结合ENN的包络优势进行网络数据包文本聚类，利用鲁棒SVM对含有噪声的数据去噪，有效地改善了网络数据包文本信息丢失的缺陷，从而提高整体方案的检测精度。

上述研究大多基于单一的传统机器学习方法，虽然在样本识别能力上都有提升，但是对复杂函数的表达能力有限，泛化能力较弱，不能很好地处理复杂分类问题。这些分类算法只输出预测结果标签，“非黑即白”式的判断样本数据的标签，缺少对预测结果置信度的评价机制，因此无法保证预测结果的可靠性。文献[18]提出共形预测（Conformal Prediction，CP）算法。该算法利用有效的置信度来衡量预测结果的可靠性，基于一致性原理且定义明确的数学框架，用于衡量校准集与测试实例的符合程度，使用数据实例的奇异度（不一致性）确定新实例预测的置信值，同时生成在某一范围内具有限定错误率的预测类标签（假设训练集样本和被预测实例需独立分布）。

近年来，共形预测被逐渐应用于各个领域。文献[19]提出一种基于主动学习的CP算法，结合预测数据的不确定性、多样性和典型性，通过求解带约束条件的线性回归问题以确定预测数据之间的关联性，基于CP计算预测结果的可信度和置信值，将该算法应用在人脸识别上并取得较优的效果。文献[20]使用回归树进行预测，多个测试实例会划分到一个叶子节点中，但是出现不同预测区间的现象，验证了使用CP解释这种现象发生的合理性。文献[21]构建ICP-CNN模型，将CP算法融入到卷积神经网络中，不仅在一定程度上增加了对新对象预测的可靠性，还提高了CNN的分类性能。文献[22]将CP算法与矩阵分解技术相结合运用在推荐系统中，提出并分析基于矩阵分解的不一致度量。CP模型在不断变化的条件下具有较强的通用性。文献[23]将CP算法与随机森林的基础算法相结合用于解决无声语音识别可靠性问题，利用CP算法对无标签数据进行预测，不仅降低了识别的错误率，还可获得单个数据预测的置信区间。文献[24]基于CP算法提出一种分布回归的区间预测算法，通过内核平均嵌入将输入分布嵌入到复制内核希尔伯特空间中，构建可靠的预测系统，并将此方法首次应用于温度和降水气候综合预测领域中。因此，CP算法及相关框架正逐渐走向成熟并在预测结果可靠性计算上起到了积极的作用。

本文提出一种共形预测框架下的入侵检测算法。采用传统机器学习分类算法对数据进行首次预测，利用共形预测算法计算预测结果的p-value，采用支持向量机对可靠度低的预测结果进行二次精细预测，并将可靠度高的预测结果作为最终结果。根据传统机器学习算法的各自特点，构造共形框架下与之对应的不一致性计算公式，通过引入平滑因子改进p-value的计算公式，使其能够以更平滑的方式度量预测实例与校准集的不一致程度。

1 相关理论 1.1 机器学习分类算法

共形预测是在机器学习算法基础上对预测结果进行置信度计算，因此许多分类算法（如DT、SVM、KNN、ANN、贝叶斯网络等）在CP框架下被称为底层算法。本文底层算法采用DT和SVM。

1.1.1 决策树

决策树是一种树形结构预测算法，其中每个内部节点表示一个特征的分类预测，每个分支代表一个测试输出，每个叶子节点代表一种预测结果。决策树学习算法的实质是特征选择过程，在确定每一层划分样本的特征时，按照一定的标准计算每个特征，每次都选择最重要的特征作为样本划分特征。

文献[25]提出的决策树算法（CART）是在ID3算法基础上进行优化的决策树。在CART构造决策树时根据每个特征的所有可能取值计算样本集的基尼指数，将基尼指数最小的特征和取值作为当前节点和最优切分点，并生成两个子节点，根据最优切分点将数据分成两个子集并分别分配到两个子节点中。从根节点开始，按照上述过程递归计算每个节点的基尼指数，并确定特征和生成两个子节点，直至样本的基尼指数小于阈值或样本的节点数小于阈值后，停止计算。

CART算法分类准确率高、鲁棒性强，但容易受样本的影响使得子树在决策树中可能重复多次，导致过拟合现象的发生。针对过拟合现象，本文采用基于预测误差增益和交叉验证的方式进行剪枝，从而提高泛化能力。

1.1.2 多分类支持向量机

SVM是机器学习常用的一种分类算法。传统的SVM是一种二分类模型，通过构造分类超平面寻找最优的超平面，即对样本数据进行最大间隔的分割。在实际中，网络入侵数据往往呈现非线性的特点，因此，本文利用样本数据构造非线性多分类SVM模型。

设一组带有标签的样本$ ({\mathit{\boldsymbol{x}}}_{i}, {y}_{i}) $，$ i=\mathrm{1, 2}, \cdots , n $，其中，$ {y}_{i} $为样本标签，分类超平面如式（1）所示：

$ f\left(\mathit{\boldsymbol{x}}\right)={\mathit{\boldsymbol{w}}}^{\mathrm{T}}\varphi \left(\mathit{\boldsymbol{x}}\right)+b $

(1)

其中：$ \mathit{\boldsymbol{w}} $为超平面法向量，表示$ \mathit{\boldsymbol{x}} $映射后的特征向量；$ b $为常数。在支持向量机中引入函数间隔$ \widehat{\gamma }=y\left({\mathit{\boldsymbol{w}}}^{\mathrm{T}}\varphi \right(\mathit{\boldsymbol{x}})+b) $，为了消除$ \mathit{\boldsymbol{w}} $和$ b $同时缩放产生的影响，对函数间隔进行归一化处理以形成几何间隔，即$ \widehat{\gamma }=\widehat{\gamma }/\omega $。此时的超平面是所有样本点$ ({\mathit{\boldsymbol{x}}}_{i}, {y}_{i}) $的几何间隔最小值，即$ \widehat{\gamma }=\underset{i=\mathrm{1, 2}, \cdots , n}{\mathrm{m}\mathrm{i}\mathrm{n}}\widehat{\gamma } $几何间隔衡量最大间隔超平面，因而其本质变为一个凸二次规划问题，如式（2）所示：

$ \begin{array}{l}\underset{\omega , b}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{1}{2}\left|\right|\mathit{\boldsymbol{w}}|{|}^{2}\\ \mathrm{s}.\mathrm{t}.{y}_{i}\left({\mathit{\boldsymbol{w}}}^{\mathrm{T}}\varphi \right({\mathit{\boldsymbol{x}}}_{i})+b)\ge 1, i=\mathrm{1, 2}, \cdots , n\end{array} $

(2)

引入拉格朗日乘子，将式（2）转化为对偶形式，求解该二次规划问题。

针对高维或无穷维问题，本文采用径向基核函数（Radial Basis kernel Function，RBF）进行计算，求解后得到分类函数如式（3）所示：

$ f\left(\mathit{\boldsymbol{x}}\right)=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left\{\sum\limits_{i=1}^{n}{\lambda }_{i}{y}_{i}K(\mathit{\boldsymbol{x}}, {\mathit{\boldsymbol{x}}}_{i})+b\right\} $

(3)

二分类非线性SVM模型构造完成。

由于网络入侵数据的多样性，即数据标签具有多种类别，因此在二分类SVM基础上，构造相应的多分类SVM模型。本文采用一对多构造方法，即根据样本数据构造k个SVM模型，其中k表示样本数据标签的数量，每个模型负责区分该类数据和其他类别数据，最后得到k个超平面距离最大的预测标签作为最终预测结果。

1.2 共形预测

共形预测是不使用复杂概率模型进行可靠预测的框架。对于任意的显著性水平$ \epsilon \in \left[\mathrm{0, 1}\right] $，CP将生成一个预测结果的集合。在该集合中预测正确结果的概率不低于$ 1-\epsilon $。CP的原理是设集合$ \mathit{\boldsymbol{Z}} $包含n个元素，即$ \mathit{\boldsymbol{Z}}=\{{\mathit{\boldsymbol{z}}}_{1}, {\mathit{\boldsymbol{z}}}_{2}, \cdots , {\mathit{\boldsymbol{z}}}_{n}\} $，其中$ {\mathit{\boldsymbol{z}}}_{n}=\{{\mathit{\boldsymbol{x}}}_{n}, {y}_{n}\} $，$ {\mathit{\boldsymbol{x}}}_{n} $是第n个数据样本，$ {y}_{n} $是$ {\mathit{\boldsymbol{x}}}_{n} $的标签。度量不一致性定义的函数$ A(\mathit{\boldsymbol{Z}}, \mathit{\boldsymbol{z}}) $。该函数计算实例$ \mathit{\boldsymbol{z}} $与集合$ \mathit{\boldsymbol{Z}} $的不一致程度，得到衡量该程度的得分，即$ \alpha =A(\mathit{\boldsymbol{Z}}, \mathit{\boldsymbol{z}}) $。通过函数$ A(\mathit{\boldsymbol{Z}}, \mathit{\boldsymbol{z}}) $计算$ \mathit{\boldsymbol{Z}} $中任何一个元素$ {\mathit{\boldsymbol{z}}}_{i}(i=\mathrm{1, 2}, \cdots , n) $的不一致得分$ {\alpha }_{i} $，即$ {\alpha }_{i}=A(（\mathit{\boldsymbol{Z}}-{\mathit{\boldsymbol{z}}}_{i}）, {\mathit{\boldsymbol{z}}}_{i}) $，其中$ \mathit{\boldsymbol{Z}}-{\mathit{\boldsymbol{z}}}_{i} $表示两个集合的差集。之后对新的数据实例$ {\mathit{\boldsymbol{x}}}_{n+j}(j=\mathrm{1, 2}, \cdots , n $），利用底层算法得到预测标签$ {y}_{n+j} $，此时得到$ {\mathit{\boldsymbol{z}}}_{n+j}=（{\mathit{\boldsymbol{x}}}_{n+j}, {y}_{n+j}） $。根据底层算法输出，计算$ {\mathit{\boldsymbol{z}}}_{n+j} $的不一致得分$ {\alpha }_{n+j} $，再计算$ {\mathit{\boldsymbol{z}}}_{n+j} $的p-value，其计算如式（4）所示：

$ P\left({\alpha }_{n+j}^{{y}_{q}}\right)=\frac{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(i:{\alpha }_{i}\ge {\alpha }_{n+j}^{{y}_{q}})}{n+1}, i=\mathrm{1, 2}, \cdots , n+1 $

(4)

其中：$ {\alpha }_{n+j}^{{y}_{q}} $表示$ {\mathit{\boldsymbol{X}}}_{n+j} $对应标签为$ {y}_{q}\in Y $时的不一致得分；$ \mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(i:{\alpha }_{i}\ge {\alpha }_{n+1}^{{y}_{q}}） $表示满足条件$ {\alpha }_{i}\ge {\alpha }_{n+1}^{{y}_{q}} $的$ i $的数量；$ P\left({\alpha }_{n+1}^{{y}_{q}}\right) $表示$ {\mathit{\boldsymbol{z}}}_{n+1} $的p-value。当$ P\left({\alpha }_{n+1}^{{y}_{q}}\right) > \epsilon $时（在实际应用时，$ \epsilon $取值较小，如$ \epsilon =0.05 $或$ \epsilon =0.01 $），共形预测算法预测结果具有高可靠性，否则，认为预测结果可靠性低。

2 本文算法 2.1 数据降维

网络入侵数据具有海量、高维的特点，在对原始高维数据进行处理时存在计算耗时长、检测精度低的问题。因此，通过对原始高维数据进行降维是提高入侵检测算法计算效率的必要前提。本文采用主成分分析（Principal Component Analysis，PCA）法进行数据降维。

入侵检测数据高维样本的矩阵如式（5）所示：

$ \mathit{\boldsymbol{X}} = \left( {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{x}}_{11}}}&{{\mathit{\boldsymbol{x}}_{12}}}& \cdots &{{\mathit{\boldsymbol{x}}_{1m}}}\\ {{\mathit{\boldsymbol{x}}_{21}}}&{{\mathit{\boldsymbol{x}}_{22}}}& \cdots &{{\mathit{\boldsymbol{x}}_{2m}}}\\ \vdots & \vdots &{}& \vdots \\ {{\mathit{\boldsymbol{x}}_{n1}}}&{{\mathit{\boldsymbol{x}}_{n2}}}& \cdots &{{\mathit{\boldsymbol{x}}_{nm}}} \end{array}} \right) $

(5)

其中：n为样本数量；m为样本维度。入侵检测算法确定输入的样本数据$ \mathit{\boldsymbol{X}} $后，通过对样本的特征进行均值运算，如式（6）所示：

$ \stackrel{-}{\mathit{\boldsymbol{X}}}=\frac{1}{n}\sum\limits_{i=1}^{n}{\mathit{\boldsymbol{x}}}_{i} $

(6)

其中：$ {\mathit{\boldsymbol{x}}}_{i} $为样本$ \mathit{\boldsymbol{X}} $的第i行向量。$ \mathit{\boldsymbol{X}} $的协方差矩阵$ \mathit{\boldsymbol{C}} $如式（7）所示：

$ \mathit{\boldsymbol{C}}=\frac{1}{n}\sum\limits_{i=1}^{n}\left({\mathit{\boldsymbol{x}}}_{i}-\stackrel{-}{\mathit{\boldsymbol{X}}}\right){\left({\mathit{\boldsymbol{x}}}_{i}-\stackrel{-}{\mathit{\boldsymbol{X}}}\right)}^{\mathrm{T}}=\frac{1}{n}\mathit{\boldsymbol{L}}{\mathit{\boldsymbol{L}}}^{\mathrm{T}} $

(7)

其中：$ \mathit{\boldsymbol{L}}{\mathit{\boldsymbol{L}}}^{\mathrm{T}} $是m阶方阵。矩阵$ \mathit{\boldsymbol{X}} $的特征值和特征向量的求解是将特征向量按照对应特征值由大到小的顺序排列成矩阵，根据贡献率取该矩阵的前$ \xi $行（$ \xi $ < m）组成矩阵$ \mathit{\boldsymbol{P}} $。根据矩阵$ \mathit{\boldsymbol{P}} $求得降维后的目标矩阵，如式（8）所示：

$ \mathit{\boldsymbol{Y}}=\left(\mathit{\boldsymbol{X}}-\stackrel{-}{\mathit{\boldsymbol{X}}}\right)\mathit{\boldsymbol{P}} $

(8)

贡献率$ \mu $是度量每个特征携带有效信息的量，如式（9）所示：

$ {\mu }_{i}=\frac{{\pi }_{i}}{\sum\limits_{j=1}^{k}{\pi }_{i}} $

(9)

其中：$ {\pi }_{i} $是矩阵$ \mathit{\boldsymbol{L}}{\mathit{\boldsymbol{L}}}^{\mathrm{T}} $的第i个特征值。为保证用较少的特征携带较多的有效信息，通过PCA对数据进行降维后，本文将贡献率占总贡献95%的前$ l $个特征作为最终的降维结果。

2.2 CP框架下的底层算法

本文将DT算法和多分类SVM算法与CP框架相结合，以CP框架下的p-value作为桥梁将两者有效地结合。本文构造决策树算法的的过程如算法1所示。算法1的停止条件为节点中的样本个数小于指定阈值或样本集的基尼指数小于指定阈值。

算法1   决策树构造（$ \mathrm{D}\mathrm{S} $，$ {A}_{i} $）

输入  训练数据集$ \mathrm{D}\mathrm{S} $；停止计算条件；特征$ {A}_{i} $$ ，i=\mathrm{1, 2}, \cdots , l $，其中l是样本的维度

输出  最优剪枝决策树

1.生成节点node；

2.for each特征$ {\mathrm{A}}_{\mathrm{i}} $可能的取值$ \mathrm{a}\in {\mathrm{\Gamma }}_{\mathrm{i}}，$if（$ {\mathrm{A}}_{\mathrm{i}} $=$ \mathrm{a} $）划分为$ \mathrm{D}{\mathrm{S}}_{1} $集合中，else划分为$ \mathrm{D}{\mathrm{S}}_{2} $集合中，计算基尼指数（GINI）；

3.将min（GINI）的特征和对应的取值作为最优特征和最优切分点，以当前节点为根节点生成左右两个子节点；

4.将以最优切分点划分的子集$ \mathrm{D}{\mathrm{S}}_{1} $和$ \mathrm{D}{\mathrm{S}}_{2} $分别分配到两个子节点中；

5.对两个子节点递归地调用步骤1~4，直到满足终止条件；

6.return CART决策数$ {\mathrm{T}}_{0} $；

7.for each $ {\mathrm{T}}_{0} $内部节点$ {\mathrm{t}}_{\mathrm{i}}, \mathrm{i}=\mathrm{1, 2}, \cdots , \mathrm{k} $，其中$ \mathrm{k} $表示$ {\mathrm{T}}_{0} $中内部节点数量；计算过程如式（10）所示：

$ \mathrm{g}\left({\mathrm{t}}_{\mathrm{i}}\right)=\frac{\mathrm{C}\left({\mathrm{t}}_{\mathrm{i}}\right)-\mathrm{C}\left({\mathrm{T}}_{{\mathrm{t}}_{\mathrm{i}}}\right)}{\left|{\mathrm{T}}_{{\mathrm{t}}_{\mathrm{i}}}\right|-1}\text{，}\mathrm{i}=\mathrm{1, 2}, \cdots , \mathrm{k} $

(10)

8.根据$ \underset{\mathrm{i}=\mathrm{1, 2}, \cdots , \mathrm{k}}{\mathrm{m}\mathrm{i}\mathrm{n}}\mathrm{g}\left({\mathrm{t}}_{\mathrm{i}}\right) $对节点$ {\mathrm{t}}_{\mathrm{i}} $进行剪枝，将其得到的树$ {\mathrm{T}}_{\mathrm{i}} $加入到最优剪枝数序列；

9.重复步骤7和步骤8，直到$ {\mathrm{T}}_{0} $只由初始树的根节点组成的树为止，得到最优剪枝数序列；

10.采用交叉验证法从最优剪枝数序列中选取最优子树。

DT分类算法已训练完毕。当采用DT算法预测入侵数据时，算法只输出预测结果，无法确保预测结果的可靠性，而CP算法基于预测结果计算p-value，通过p-value与显著性水平$ \epsilon $的比较，可得预测结果的可靠性。当$ P\left({\alpha }_{n+j}^{{y}_{q}}\right) < \epsilon $时，当前入侵数据$ {\mathit{\boldsymbol{x}}}_{n+1} $的预测标签$ {y}_{q} $置信值较低。本文使用多分类SVM模型对$ {\mathit{\boldsymbol{x}}}_{n+1} $重新预测，从而提高预测的整体精度。

算法2   多分类SVM模型构建（D）

输入  训练数据集$ D=\left\{\right({\mathit{\boldsymbol{x}}}_{i}, {y}_{i}), i=\mathrm{1, 2}, \cdots , n\} $，$ {y}_{i}\in H $，其中$ H $是标签集合

输出  多分类SVM分类器

1.将数据样本根据标签取值分为两个数据子集$ {\mathrm{D}}_{1}=\left\{\right({\mathrm{x}}_{\mathrm{i}}, {\mathrm{y}}_{\mathrm{i}}\left)\right|{\mathrm{y}}_{\mathrm{i}}={\mathrm{h}}_{1}\} $和$ {\mathrm{D}}_{2}=\mathrm{D}-{\mathrm{D}}_{1} $，根据$ {\mathrm{D}}_{1} $构造带约束条件的凸二次规划问题。

2.引入Lagrange乘子$ {\mathrm{\lambda }}_{\mathrm{i}}，\mathrm{i}=\mathrm{1, 2}, \cdots , \mathrm{n} $，构造Lagrange函数，将问题转换成无约束条件的最优化问题。

3.使用RBF代替$ \mathrm{\varphi }{\left({\mathrm{x}}_{\mathrm{i}}\right)}^{\mathrm{T}}\mathrm{\varphi }\left({\mathrm{x}}_{\mathrm{j}}\right) $，再通过KKT条件求解Lagrange函数，得到乘子$ {\mathrm{\lambda }}_{\mathrm{i}}，\mathrm{i}=\mathrm{1, 2}, \cdots , \mathrm{n} $。

4.得到对应$ \left({\mathrm{y}}_{\mathrm{i}}={\mathrm{h}}_{1}\right)\mathrm{v}\mathrm{s}\left({\mathrm{y}}_{\mathrm{i}}\ne {\mathrm{h}}_{1}\right) $的分类函数$ {\mathrm{f}}_{1}\left(\mathrm{x}\right)=\sum\limits_{i=1}^{n}{\mathrm{\lambda }}_{\mathrm{i}}{\mathrm{y}}_{\mathrm{i}}\mathrm{K}\left(\mathrm{x}, {\mathrm{x}}_{\mathrm{i}}\right)+{\mathrm{b}}_{1} $。

5.将数据集按照标签取下一个值重新分成两个子集，重复步骤1~4，以此类推，得到所有分类函数$ {\mathrm{f}}_{1}\left(\mathrm{x}\right), {\mathrm{f}}_{2}\left(\mathrm{x}\right), \cdots , {\mathrm{f}}_{\mathrm{M}}\left(\mathrm{x}\right) $，其中$ \mathrm{M}=\left|\mathrm{H}\right| $表示标签类别的数量。

2.3 CP算法

CP算法的核心过程包含2个部分：1）根据底层算法输出结果确定属于每个预测标签的不一致得分；2）根据这些得分，计算每个预测标签的p-value。

2.3.1 不一致得分确定

在CP框架下采用底层算法进行预测分为2个部分：1）采用DT算法对网络入侵数据进行初步预测；2）采用SVM进行精细预测。由于DT算法和SVM算法在分类原理上有很大区别，因此本文根据这2个算法的各自特点分别确定预测结果不一致得分的方法。

DT算法在输出预测结果的同时输出该条数据属于每个标签的概率，将概率值最大的标签作为预测结果。设$ {o}_{1}, {o}_{2}, \cdots , {o}_{M} $（M是分类标签类型的数量）是DT算法输出数据实例$ \mathit{\boldsymbol{x}} $属于每个标签的概率，满足$ \sum\limits_{i=1}^{M}{o}_{i}=1 $。$ \mathit{\boldsymbol{x}} $不一致得分的计算如式（11）所示：

$ \alpha =\gamma \left(1-{o}_{q}\right)+\left(1-\gamma \right)\underset{i=\mathrm{1, 2}, \cdots , M, i\ne q}{\mathrm{m}\mathrm{a}\mathrm{x}}{o}_{i} $

(11)

其中：$ {o}_{q}=\underset{i=\mathrm{1, 2}, \cdots , M}{\mathrm{m}\mathrm{a}\mathrm{x}}o{}_{i} $；$ \gamma \in \left[\mathrm{0, 1}\right] $。

SVM算法按照分类标签种类输出相应得分，该得分反映一个点与最优超平面的距离，最大得分表明点到超平面的间隔最大，即表明该条数据属于哪类标签。为清晰反映每类标签与对应得分之间的占比关系，本文以预测数据得分的最小值作为基准，计算其他标签得分与基准的相对距离，如式（12）所示：

$ {o}_{i}^{\mathrm{\text{'}}}=\frac{{o}_{i}-{o}_{d}}{\sum\limits_{j=1}^{M}\left|{o}_{j}-{o}_{d}\right|}, i=\mathrm{1, 2}, \cdots , M $

(12)

其中：$ {o}_{d}=\underset{j=\mathrm{1, 2}, \cdots , M}{\mathrm{m}\mathrm{i}\mathrm{n}}{o}_{j} $。在此基础上，SVM的不一致得分计算如式（13）所示：

$ \alpha =-\sigma {o}_{q}^{\mathrm{\text{'}}}+\left(1-\sigma \right)\underset{i=\mathrm{1, 2}, \cdots , M, i\ne q}{\mathrm{m}\mathrm{a}\mathrm{x}}{o}_{i}^{\mathrm{\text{'}}} $

(13)

其中：$ {o}_{q}^{\mathrm{\text{'}}}=\underset{i=\mathrm{1, 2}, \cdots , M}{\mathrm{m}\mathrm{a}\mathrm{x}}{o}_{i}^{\mathrm{\text{'}}} $；$ \sigma \in \left[\mathrm{0, 1}\right] $。

由式（11）和式（13）可知，$ \alpha $均随着$ {o}_{q} $和$ {o}_{q}^{\mathrm{\text{'}}} $的增大而减小。因此，本文构造关于DT和SVM算法预测结果的不一致得分与CP理论相一致。

2.3.2 p-value计算

p-value是CP算法中另一个重要组成部分。p-value反映新的数据实例$ {\mathit{\boldsymbol{x}}}_{n+j} $与校准集$ C=\left\{\left({\mathit{\boldsymbol{x}}}_{1}, {y}_{1}\right), \left({\mathit{\boldsymbol{x}}}_{2}, {y}_{2}\right), \cdots , \left({\mathit{\boldsymbol{x}}}_{n}, {y}_{n}\right)\right\} $的差异程度。随着校准集规模逐渐增大，通过式（4）计算p-value会出现随机抖动现象。为避免该现象的发生，本文对式（4）进行改进，采用更平滑的方式计算p-value，改进的p-value计算如式（14）所示：

$ \begin{array}{l}P\left({\alpha }_{n+j}^{{Y}_{q}}\right)=\frac{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}（i:{\alpha }_{i} > {\alpha }_{n+j}^{{Y}_{q}}）+\tau \mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}（i:{\alpha }_{i}={\alpha }_{n+j}^{{Y}_{q}}）}{n+1}     , \\ i=\mathrm{1, 2}, \cdots , n+1\end{array} $

(14)

其中：$ \tau \in \left[0，1\right] $。由式（14）可知，$ P\left({\alpha }_{n+j}^{{y}_{q}}\right) $越大，预测数据$ {\mathit{\boldsymbol{x}}}_{n+j} $与校准集越一致。

2.3.3 可信度与置信值

CP框架提供预测结果的可信度和置信值这2个关键性能指标。

设通过式（14）计算后得到每个标签对应的p-value分别为$ {p}_{n+j}^{1} $，$ {p}_{n+j}^{2} $，…，$ {p}_{n+j}^{M} $，预测结果的可信度$ {C}_{r} $如式（15）所示：

$ {C}_{r}=\underset{i=\mathrm{1, 2}, \cdots , M}{\mathrm{m}\mathrm{a}\mathrm{x}}{p}_{n+j}^{i} $

(15)

置信值定义如式（16）所示：

$ {C}_{o}=1-\underset{i=\mathrm{1, 2}, \cdots , M, i\ne o}{\mathrm{m}\mathrm{a}\mathrm{x}}{p}_{n+j}^{i} $

(16)

其中：$ {p}_{n+j}^{o}={C}_{r} $，即置信值等于1减去第二大的p-value。

可信度反映预测标签与真实标签之间的符合程度，而置信值反映预测标签等于真实标签的可信程度。

2.4 入侵检测算法架构

设数据集为$ \mathit{\boldsymbol{Z}}=\left\{{\mathit{\boldsymbol{z}}}_{1}, {\mathit{\boldsymbol{z}}}_{2}, \cdots , {\mathit{\boldsymbol{z}}}_{n}\right\} $，$ n\in R $，其中$ {\mathit{\boldsymbol{z}}}_{i}=\left({\mathit{\boldsymbol{x}}}_{i}, {y}_{i}\right) $，$ {\mathit{\boldsymbol{x}}}_{i} $表示一个多维数据实例，$ {y}_{i} $是这个数据实例对应的标签。在集合$ \mathit{\boldsymbol{Z}} $中某些元素可能彼此相同。入侵检测算法主要分为以下6个步骤：

1）将含有n条数据的数据集$ \mathit{\boldsymbol{Z}} $分成训练集TS和校准集CS，并将TS分成2个子集$ \mathrm{T}{\mathrm{S}}_{1} $和$ \mathrm{T}{\mathrm{S}}_{2} $，$ \mathrm{C}\mathrm{S} $分成2个子集$ \mathrm{C}{\mathrm{S}}_{1} $和$ \mathrm{C}{\mathrm{S}}_{2} $。$ \mathrm{T}{\mathrm{S}}_{1} $用于训练DT算法，$ \mathrm{T}{\mathrm{S}}_{2} $用于训练SVM模型。$ \mathrm{C}{\mathrm{S}}_{1} $用作DT算法的校准集，$ \mathrm{C}{\mathrm{S}}_{2} $用作SVM模型的校准集。其中，$ \left|\mathrm{T}{\mathrm{S}}_{1}\right|={n}_{1} $，$ \left|\mathrm{T}{\mathrm{S}}_{2}\right|={n}_{2} $，$ \left|\mathrm{C}{\mathrm{S}}_{1}\right|={n}_{3} $，$ \left|\mathrm{C}{\mathrm{S}}_{2}\right|={n}_{4} $，满足$ \sum\limits_{i=1}^{4}{n}_{i}=n $，$ {n}_{1} > > {n}_{2} $，$ {n}_{1}+{n}_{2} > > $ $ {n}_{3}+{n}_{4} $。

2）分别用$ \mathrm{T}{\mathrm{S}}_{1} $和$ \mathrm{T}{\mathrm{S}}_{2} $进行训练，得到DT算法和SVM算法。

3）利用DT算法对$ \mathrm{C}{\mathrm{S}}_{1} $中所有数据实例进行分类，通过式（11）计算所有分类结果的不一致得分，构成不一致得分集$ {\alpha }_{\mathrm{D}\mathrm{T}}=\{{\alpha }_{1}, {\alpha }_{2}, \cdots , {\alpha }_{{n}_{3}}\} $。同理，采用SVM算法对$ \mathrm{C}{\mathrm{S}}_{2} $中所有数据实例进行分类，利用式（12）和式（13）计算所有分类结果的不一致得分，构成集合$ {\alpha }_{\mathrm{S}\mathrm{V}\mathrm{M}}=\{{\alpha }_{1}, {\alpha }_{2}, \cdots , {\alpha }_{{n}_{4}}\} $。

4）利用DT算法对新的数据实例$ {\mathit{\boldsymbol{x}}}_{n+j}(j=\mathrm{1, 2}, \cdots , n) $进行预测，输出预测结果$ {y}_{n+j} $。采用式（14）计算$ {y}_{n+j} $的p-value，当p-value > $ \epsilon $时，计算$ {y}_{n+j} $的可信度和置信值，并扩充预测结果集$ \mathrm{R}\mathrm{e}=\mathrm{R}\mathrm{e}+\left\{\right({\mathit{\boldsymbol{x}}}_{n+j}, {y}_{n+j}\left)\right\} $。

5）当步骤4中的p-value < $ \epsilon $时，用SVM模型对该数据实例进行重新预测，输出预测结果$ {y}_{n+j} $。采用式（14）计算$ {y}_{n+j} $的p-value。当p-value > $ \epsilon $时，计算$ {y}_{n+j} $的可信度和置信值，并扩充预测结果集$ \mathrm{R}\mathrm{e}=\mathrm{R}\mathrm{e}+\left\{\right({\mathit{\boldsymbol{x}}}_{n+j}, {y}_{n+j}\left)\right\} $，返回步骤4，直至测试集中的所有数据预测完毕。

6）当步骤5中p-value < $ \epsilon $时，判定该数据为异常数据，丢弃该数据，返回步骤4，直至测试集中的所有数据处理完毕。

入侵检测算法流程如图 1所示。

3 仿真实验与结果分析

实验平台为苹果操作系统，CPU 2.4 GHz，内存8.0 GB的PC机，编程软件为MATLABR2018a，分别对KDD CUP 99数据集和AWID数据集进行实验。

3.1 KDD CUP99数据集的实验结果与分析

在KDD CUP99数据集中每条样本数据由41个特征属性和1个类别标签组成。特征属性包括protocol_type、service、flag等，其中3个symbolic类型，38个numeric类型。KDD CUP99数据集的特征属性如表 1所示。

标签类别包括1种正常类型（Normal）和4种攻击类型。攻击类型分别为DoS、R2L、U2R、Probe，又可划分为39类攻击。KDD CUP99数据集的数据标签类别如表 2所示。

3.1.1 数据选择与划分

本文采用KDD CUP99原始数据集中前10%的部分数据进行实验，根据KDD CUP99原始数据集前10%的数据分布情况可知，数据集中的标签具有高度不平衡的特点。本文将数据集按适当比例划分为训练数据集和测试数据集。实验数据划分情况如表 3所示。

3.1.2 在KDD CUP99数据集上的数据预处理

数据预处理包括对离散特征数值化、归一化和降维处理。

1）离散特征数值化。为满足底层分类算法输入输出数据类型均为numeric类型的要求，本文将数据集中所有symbolic类型数据转换成numeric类型数据。本文将特征protocol_type中数据取值TCP、UDP和ICMP分别转换为数字1、2、3；特征service的数据取值共有70种，包括http、ftp、smtp等，依次转换为数字1~70；特征flag的取值共有11种，包括OTH、REJ、RSTO等，依次转换为数字1~11；数据标签共有Normal、Probe、DoS、U2R、R2L这5种，依次转换为数字1~5。

2）数据归一化处理。由于在数据集中各个特征取值的数量级和量纲均不相同，因此需将原始数据进行归一化处理，从而增强实验结果的可靠性。本文使用z-score法进行归一化，该方法是基于特征数据的均值和标准差进行计算，如式（17）所示：

$ {z}_{i}=\frac{{x}_{i}-E\left(x\right)}{\sqrt{D\left(x\right)}} $

(17)

其中：$ {x}_{i} $为观测值；$ E\left(x\right) $为特征数据的均值；$ D\left(x\right) $为特征数据的方差。标准化后的数据均值为0，标准差为1。

3）数据降维处理。为降低数据特征间的冗余并加快数据的处理速度，本文采用PCA算法对数据进行降维，保留主成分累计贡献率达95%的特征，即前20个特征作为降维后的特征。

3.1.3 在KDD CUP99数据集上的参数设置

入侵检测算法的参数设置如表 4所示。

3.1.4 在KDD CUP99数据集上的实验结果

为验证本文算法的高效性，本文算法与DT算法、SVM算法、DT-SVM算法在相同训练集与测试集上从混淆矩阵准确率、查准率和误报率三个方面进行对比实验。准确率如式（18）所示：

$ {a}_{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}}=\frac{{T}_{\mathrm{T}\mathrm{P}}+{T}_{\mathrm{T}\mathrm{N}}}{{T}_{\mathrm{T}\mathrm{P}}+{T}_{\mathrm{T}\mathrm{N}}+{F}_{\mathrm{F}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{N}}} $

(18)

查准率如式（19）所示：

$ P=\frac{{T}_{\mathrm{T}\mathrm{P}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{P}}} $

(19)

召回率如式（20）所示：

$ R=\frac{{T}_{\mathrm{T}\mathrm{P}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{N}}} $

(20)

误报率如式（21）所示：

$ {F}_{\mathrm{F}\mathrm{P}\mathrm{R}}=\frac{{F}_{\mathrm{F}\mathrm{P}}}{{F}_{\mathrm{F}\mathrm{P}}+{T}_{\mathrm{T}\mathrm{N}}} $

(21)

其中：T_TP表示真实值是positive，模型认为是positive的数量；F_FN为真实值是positive，模型认为是negative的数量；F_FP表示真实值是negative，模型认为是positive的数量；T_TN表示真实值是negative，模型认为是negative的数量。

在KDD CUP99数据集中DT、SVM、DT-SVM和本文算法的混淆矩阵如图 2所示。从图 2可以看出，混淆矩阵分别为5行5列。底侧数字1~5表示数据真实标签，左侧数字1~5表示预测分类出的标签。最后一行格子（右下角格子除外）上面和下面的百分比分别表示预测各标签成功和失败的召回率。最后一列格子（右下角格子除外）上面和下面的百分比分别表示预测各标签成功和失败的查准率。右下角格子上面的百分比表示预测准确率，下面的百分比为预测失败率。其他格子下面百分比则表示该分类样本数占全部测试集样本数的比例。。

在KDD CUP99数据集中，DT、SVM、DT-SVM和本文算法的准确率对比如图 3所示。本文算法的准确率总体优于SVM算法、DT算法和DT-SVM算法，分别提高11.1、4.6和3.7个百分点。KDD CUP99数据集标签类型具有不平衡性，其中Normal与DoS标签类型的数据在训练集中的占比较大，Probe、U2R、R2L类型数据占比较少，因此在测试结果中数据各项性能的评估率有较明显的波动。

在KDD CUP99数据集中，DT、SVM、DT-SVM和本文算法的查准率对比如图 4所示。

从图 4可以看出，本文算法在Normal、Probe、U2R和R2L标签类型上的查准率较SVM算法分别提高14.4、14.8、95.3和29.4个百分点，在DoS标签类型上降低5.8个百分点。因此，本文算法的查准性能优于SVM算法。本文算法在Normal、Probe、U2R和R2L标签类型上的查准率较DT算法分别提高5.3、8.7、79.6和53.4个百分点，在DoS标签类型上降低5.9个百分点。因此，本文算法的查准率性能优于DT算法。本文算法在Probe、DoS、U2R和R2L标签类型上的查准率较DT-SVM算法分别提高7.2、7.4、42.9和27.9个百分点，在Normal标签类型上降低4.2个百分点。因此，本文算法的查准率性能优于DT-SVM算法。

在KDD CUP99数据集上不同算法的评价指标对比如表 5所示。从表 5可以看出，本文算法的各数据标签类型误报率与其他算法相比有所降低。本文算法在Normal、Probe、U2R和R2L标签类型上的误报率较SVM算法分别降低了11.85、3.97、3.08和0.81个百分点；在DoS标签类型上增加了4.38个百分点。因此，本文算法的误报性能优于SVM算法。本文算法在Normal、Probe、U2R和R2L标签类型上的误报率较DT算法分别减少了3.59、2.43、1.01和2.89个百分点，在DoS标签类型上增加了4.28个百分点。因此，本文算法的误报性能优于DT算法。本文算法在Probe、DoS、U2R和R2L标签类型上的误报率较DT-SVM算法分别降低1.75、6.16、0.02和0.71个百分点，在Normal标签类型上增加了2.97个百分点。因此，本文算法的误报性能优于DT-SVM算法。

3.2 AWID数据集的实验结果与分析

在AWID数据集上的每条数据都由154个特征和1个标签组成。AWID数据集根据数据标签种类的数量，又分为AWID-ATK和AWID-CLS数据集。本文在AWID-CLS-R-Trn数据集上进行实验。该数据集共有1 795 575个数据，数据标签由3种攻击类型标签Injection、Flooding、Impersonation和1种正常类型标签Normal组成。在AWID数据集中每种数据标签的分布情况如表 6所示。

3.2.1 数据集选择

由于在AWID-CLS-R-Trn数据集中各个类型的数据不均衡，因此本文随机选择部分数据作为实验数据集，使得该数据集中4种数据类型的数量相当。在AWID数据集中实验数据的划分情况如表 7所示。

3.2.2 在AWID数据集上的数据预处理

数据预处理包括离散特征数值化、数据归一化处理和数据降维处理。

1）离散特征数值化。本文将原始训练集中所有数据进行“清洗”，并将清洗后的数据都转换成numeric类型。将特征数据中存在的空值，即“？”转换为数字0；将特征数据中的十六进制数转换为十进制数字；丢弃即不考虑表示MAC地址的特征数据；将4种数据标签类型Normal、Flooding、Injection、Impersonation依次转换为数字1~4。

2）数据归一化处理，同式（17）。

3）数据降维处理。采用PCA算法对数据进行降维，保留主成分累计贡献率达95%的特征，即前46个特征作为降维后的特征。

3.2.3 在AWID数据集上的参数设置

算法中参数$ \gamma $、$ \sigma $和$ \tau $的设置与表 4相同。其他参数设置如表 8所示。

3.2.4 在AWID数据集上的实验结果

在AWID数据集上SVM算法、DT算法、DT-SVM算法和本文算法的混淆矩阵如图 5所示。从图 5可以看出，混淆矩阵分别为4行4列。底侧数字1~4表示数据真实标签，左侧数字1~4表示预测分类出的标签。最后一行格子（右下角格子除外）上面和下面的百分比分别表示预测各标签成功和失败的召回率。最后一列格子（右下角格子除外）上面和下面的百分比分别表示预测各标签成功和失败的查准率。右下角格子上面的百分比表示预测准确率，下面的百分比为预测失败率。其他格子下面百分比则表示该分类样本数占全部测试集样本数的比例。

在AWID数据集上不同算法的准确率对比如图 6所示。从图 6可以看出，本文算法的准确率总体上优于SVM算法、DT算法和DT-SVM算法，分别提高4、2.5和1.3个百分点。由于AWID数据集的标签类型具有较优的平衡性，因此在测试结果中数据各项性能的评估率不存在较为明显的波动。

在AWID数据集上不同算法的查准率对比如图 7所示。从图 7可以看出，本文算法在Normal、Flooding和Impersonation标签类型上的查准率较SVM算法分别提高4.5、2.5和11.2个百分点；在Injection标签类型上近乎相同。因此，本文算法的查准性能优于SVM算法。本文算法在Normal和Impersonation标签类型上的查准率较DT算法分别提高5.1和2.9个百分点，在Flooding、Injection标签类型上近乎相同。因此，本文算法的查准率性能优于DT算法。本文算法在Normal、Flooding和Impersonation标签类型上的查准率较DT-SVM算法分别提高2.5、1.4和2.3个百分点，在Injection标签类型上近乎相同。因此，本文算法的查准率性能优于DT-SVM算法。

在AWID数据集上不同算法的评价指标对比如表 9所示。本文算法在Normal和Flooding标签类型上的误报率较SVM算法分别降低了1.15和0.7个百分点。因此，本文算法的误报性能优于SVM算法。本文算法在Normal、Flooding和Impersonation标签类型上的误报率较DT算法分别减少了1.86、0.72和0.81个百分点，在Injection标签类型上增加了0.05个百分点。因此，本文算法的误报性能优于DT算法。本文算法在Normal、Flooding和Impersonation标签类型上的误报率较DT-SVM算法分别降低了0.58、0.42和0.76个百分点。因此，本文算法的误报性能优于DT-SVM算法。

4 结束语

本文提出共形预测框架下的入侵检测算法。结合共形预测算法能够给出置信值的优点，通过构造适应机器学习分类算法的不一致得分函数，得到预测结果的改进p-value，同时采用支持向量机对置信值低于阈值的预测结果进行二次精细预测，提高各类数据标签的预测精度。实验结果表明，与DT、SVM和DT-SVM算法相比，本文算法在保证检测结果可靠性的情况下具有较优的检测性能。下一步将把概率图理论与共形预测算法相融合，使得共形预测算法中的数据无需满足独立同分布的要求，进一步提高检测结果的可靠度。