基于模糊ID3算法的IDS规则生成技术

刘咸通++申培培++辛晓鹏++蔡硕

摘 要：本文针对计算机免疫系统模型GECISM中的类MC Agent，基于fuzzy-ID3算法构造决策树，模糊决策树使用系统调用作为数据集生成入侵检测规则，与C4.5算法生成规则的对比。Fuzzy-id3算法生成的规则具有较低的误报率和漏报率。

关键词：入侵检测；系统调用；规则

中图分类号：TP393.08 文献标识码：A 文章编号：1671-2064（2017）19-0035-03

随着网络技术的日益发展，网络安全问题日益显现出来，网络入侵和攻击的现象屡见不鲜、目前，解决网络安全问题的主要技术有：数字加密技术、访问控制、虚拟专用网、大数据安全等。访问控制技术、虚拟专用网技术可以控制已知的网络非法访问，对于一些未知的访问只能用笼统的规则来处理，无法细化未知访问的合法性，已无法完全解决网络安全的问题.近几年来，利用生物个体的细胞免疫原理，使用系统中进程的系统调用作为判断计算机系统中正常和异常的程序的依据，也就是所谓的自我和非我.这一应用克服了传统安全技术非智能化以及粒度粗化的缺点.根据自适应、自主学习的原则设计安全系统模型，使用模糊决策树区分计算机系统中的”正常“的系统调用和”异常“的异常系统调用，并删除各类的”异常“。

进程作为系统中运行的最小代码单位，也是判断是”正常“访问还是”异常“程序的主要依据，在操作系统中有应用系统日志以及系统审计日志等数据可以用来对进程进行分类，这些数据一般有具体的系统工具收集，收集起来非常方便，可移植性也较好，但是对于单个系统而言数据信息量较小，且分析粒度也非常大，并不能完全反应系统进程的特征.进程都是通过其占用的系统调用来完成工作，就像生物细胞中的DNA图谱一样，不同的进程占用的不同的系统调用不同，因此可以根据进程占用的系统调用来对进程进行分类。美国新墨西哥州大学Stephanie Forrest教授提出了这一观点，其领导的研究小组实验表明，以等长划分而成的所有程序运行时产生的系统短调用序列有明显的稳定性和连续性，因此可以通过基于定长的系统调用序列来构造样本特征库来区分”正常“进程和”异常“进程称为自我合肥我.根据已得到的系统短调用”正常“、”異常“的生成判断”正常“和”异常“的规则库，规则库中无法判断的短调用称为漏点，如果在某个时间周期T内，漏点的个数达到的限值L，规则库则进行规则更新；否则到T时进行规则更新。

决策树规则生成使用C4.5算法，该算法使用信息的熵作为启发式，并且假设样本的属性值和分类值是确定的这一前提下建立一棵清晰的决策树，然后根据决策树产生规则.在保证数量一定且分布合理的训练集的情况下使用该方法训练出的规则对未知样本进行分类预测，此时得到自我和非我的结果准确率较高.但是由于在对未知样本进行匹配时，若无法和已知规则匹配即可判断为异常即非我，所以使用此方法是无法判断漏点的，在规则库中，不是正常即是异常，因此误报率较高，所以为提高准确率，训练集数据应尽量分布合理。

本文介绍了利用模糊决策树fuzyy-id3算法构造模糊决策树规则库，对样本使用规则进行模糊匹配，根据相应的隶属度（匹配度）来对结果分类，可以达到较好判别自我和非我的效果，此方法应用于移动互联，对于移动PDA访问的判别也有良好的效果。

1 fuzzy-id3算法

1.1 模糊决策树

1965年L.A.Zadeh在数学上创立了一种描述模糊现象的方法称为模糊集合论。这种方法把待考察的对象及反映它的模糊概念作为一定的模糊集合，建立适当的隶属函数，通过模糊集合的有关运算和变换，对模糊对象进行分析.模糊集合论以模糊数学为基础，研究有关非精确的现象。客观世界中，大量存在着许多亦此亦彼的模糊现象即不确定性。现实中人类的思想与感知也是模糊的，无法用精确的确定的量来描述.事物本身具有的不确定性以及现实生活中技术条件所限造成了计算机在在知识表达及推理过程产生不确定性即所谓的模糊性.模糊集理论定义了多个不同的模糊算子以反应映现实中不确定性传播规律。模糊集合论是以模糊数学为其理论基础，运算灵活性强且富于针对性，时间复杂度也较低。

模糊集合论中的模糊分类可以有如下描述：一个模糊化后的样本集合D={d1，d2，…，dn}，其中每个di由n个模糊特征属性A1，A2，…，An和一个模糊类属性C={C1，C2，…，Cm}来描述，每个Ai又由模糊语言变量，即属性值组成，表示为Ai={Ai1，Ai2，Aik}（i=1，2，…，n）.即每个示例uj可以用一个维向量表示，形如：

则示例集D关于类别C的信息熵为：

，

而用特征属性划分的D后的模糊熵为：

则属性A相对于数据集D的信息增益为：

。

模糊决策树算法是传统决策树算法的一个扩充和完善，使得决策树学习的应用范围扩大从而能够处理不确定性。它合理的处理了学习和推理过程中的不精确信息，具有更强的分类能力及稳健性.由于能生成不同水平和不同置信度的规则，为决策者提供丰富的决策信息。

1.2 FUZZY—ID3算法

模糊决策树归纳的启发式算法有多种，比如FUZZY—ID3、Min—Ambiguity等，其中FUZZY—ID3算法是使用最多的一种.下面给出详细的FUZZY—ID3算法：

（1）初始化：F←“所有属性”，D←“所有训练示例”；

（2）选取所有属性中模糊信息熵最小的属性作为根节点；

（3）如果当前节点满足以下条件，该节点为叶子节点，计算各类的置信度CF的值，选取最大的作为节点的类别标记并记录，返回；

条件：a.属性已经全部使用

b.

c.

（4）否则，对该节点进行模糊分割，分割步骤如下：endprint

①对F中的所有属性Ai，计算启发式I（C；Ai）的值，选取使之最大的属性A作为该节点的测试属性；

②F←F＼{A}；

③依次用

（5）将生的树转换成模糊产生式规则。

2 计算机免疫系统

在计算机免疫系统中，将检测有害成分称为免疫检测，将消除有害成分称为免疫应答，而对免疫应答激烈程度的调整称为免疫调整。

计算机中”正常“与”异常“的定义。正常操作不会对计算机系统造成破坏，只有非法操作产生的异常行为才会造成对系统的破坏，保护正常行为的同时检测并消除异常行为才能保证系统的安全。我们知道程序（进程）是通过调用操作系统提供的系统调用函数服务来实现的，一个有害程序只有被调入内存中执行异常操作时才能对系统造成破坏，因此，程序的行为是正常的还是异常的可以通过执行的系统调用反映出来，但是该调用与操作系统的版本、系统服务的类型和危害发生的位置有关，所以计算机免疫系统使用程序运行所形成的系统调用序列串、操作系统版本、服务的类型和危害发生的位置等四个属性来表征一个进程是正常的还是异常的。

系统中”正常“是指正常用户行为造成的计算机系统中的系统调用函数序列串、操作系统版本、系统服务的类型和危害发生的位置的序列。”异常“是指：异常行为造成的计算机系统中的系统调用序列串、操作系统版本、服务的类型和危害发生的位置的序列。由此，计算机免疫系统的功能就可以概括为：保护”正常“程序进程；检测并消除含有”异常“的进程。

3 数据预处理

系统调用是操作系统提供给用户程序调用的一组“特殊”接口。用户程序可以通过这组“特殊”接口來获得操作系统内核提供的服务，linux系统调用主要分为硬件控制、系统状态设置以及内存管理、进程管理等，考虑到计算成本，实验中用定长滑动窗口系统调用系列，生成长度为8的系统短调用（S0，S1，S2，S3，S4，S5，Class1，Class2），其中Class1，Class2为属性类别，Class1标识为“1”，Class2标识为“0”，放入Normal库中.同样对每个”异常“系统调用系列，生成长度为8的样本点，Class1标识为“0”，Class2标识为“1”，放入Abnormal库中.删除Normal、Abnormal库中重复出现的系统断掉用，删除Abnormal库中每条在Normal库中出现的系统短调用。

3.1 决策树规则生成及匹配

合并Normal、Abnormal库到训练样本库D，每个样本有6个属性，S0，S1，S2，S3，S4，S5，和类属性C={CLASS1、CLASS2}来描述，其中，各特征属性是由一些相同的属性值，这是因为每个Linux操作系统的系统调用，例如固定体积，标准Linux 2.4.18内核有237个系统调用，即在这个系统中，每个属性有237个属性值。每个样本库中的一个记录，每个数字代表相应属性的匹配度跟这个样品（如果样品的S0是读取，然后读取相应的属性值是1，其他是0），使用ID3算法建立D进行模糊决策树学习训练，生成模糊决策树，然后生成规则。

3.2 使用以下步骤对规则进行匹配

步骤1：计算未知的短周期系统调用序列与特征属性匹配后的匹配度，把它作为确定分类结果的结论匹配度；

步骤：2：取将某个短调序列分为同一类结果的多个规则产生的不同的匹配度中最高匹配度的作为分类结果；

步骤3：对于某短调序列以不同的匹配度分到不同类结果，分别取class1、class2中的最高匹配度，并规定一个阈值，如果两个匹配度相差超过这个阈值，则取较大者所在类别，否则认为此短调序列为未知序列。

4 实验结果及其分析

实验使用Linux系统中的rlogin程序，针对rlogin特洛伊代码允许入侵通过“后门”登陆系统，系统短调用序列数据集来自墨西哥州大学计算机免疫系统网站.原始数据集中的数据由两列构成，分别是进程标识符和系统调用.正常运行的rlogin程序中有11个进程，植入特洛伊代码的rlogin程序有9个进程异常，对这两个程序的系统调用序列长度为8的窗口采集后，共得到样本点5981个.按照前所描述方法进行数据整理，最后Normal库中为835个样本点，Abnormal库中为216个，生成训练集D共1051个示例，其中来自Normal库中的数据，Class1置为1，Class2置为0，来自Abnormal库中的则正好相反。利用C4.5算法生成规则，结果如表1。

利用上述介绍的Fuzzy-ID3算法生成的规则，其中参数θ=0.1、β=0.8（置信度）、λ1=0.3，结果如表2。

在实验中，提取随机70%个数据集作为训练集，30%作为测试集.如表1所示，规则数（置信因子≥0.8），通过C4.5算法生成的，是56。其中22为判断的”正常“、”异常“的38个判断.然后对规则所设定的短信进行分类，误码率为4.3%。如表2所示，规则数（置信因子≥0.8），通过模糊ID3算法产生，56.其中，21为判断的”正常“、”异常“的35个判断.然后对所规定的短信组进行分类，错误率为2.2%，同时，由于无法判断4发短信的分类样本点，失败报告率为1.3%。由于训练集所作的关于分类确定（或”正常“和”异常“），“未知样本点“空相应项目的识别，和“未知样本点”不会产生规则，相应的项目是零和。

为什么高错误率增加的C4.5算法生成的规则的理由是，如果某些样本点从所有不同的规则，那么它将被视为正常的系统条件的违反，所以系统会判断该点为“异常”，显然，如果我们选择了过度训练组，错误率将上升.同时，把”正常“和”异常“的隶属度的样本点的匹配准则2.4中描述与ID3算法，然后判断其分类阈值的λ1，漏报率将跳下。尽管ID3算法产生的漏报率，这并不说明这种方法不能与C4.5算法相比，由于漏报率是不可避免的，C4.5算法只是考虑它的错误率。

在实验中，如果训练集少，错误率不会上升，但是，其漏报率会上升，会产生更多的“未知序列”，这是产生的规则不全面导致的，需要选择训练集或移动程序TC代理.阈值的影响λ1漏报率的选择，所以我们需要在大量的实验值。

5 结语

采用Fuzzy-ID3算法构造的规则，可以依据系统短调用序列对进程进行合理的判断，得到”正常“、”异常“或“未知”三种分类，且不会因为训练集分布的不合理而升高误报率。此方法应用于移动通讯领域，对于移动终端访问服务器时对异常访问的甄别是可行的。

参考文献

[1]王煜，王正欧，等.基于模糊决策树的文本分类规则抽取[J].计算机应用，2005，（7）：04.

[2]Somayaji A，Hofmeyr SA， Forrest S.Principles of Computer Immune System[z].New Security.Paradigms workshop，ACM， Charlottesville， Virginia， September 22 - 25 1998.

[3]王凤先，张岩，刘振鹏，等.基于系统调用的入侵检测规则的生成[J].计算机工程与应用，2003，（21）.

[4]QUINLAN JR.Induction of decision trees[J].Mach Learning，1986，1（1）：81-106.

[5]朱参世，李响.自适应模糊决策树算法在数据流挖掘中的应用[J].现代电子技术，2010，（10）：63.

[6]王熙照，孙娟，杨宏伟，等.模糊决策树算法与清晰决策树算法的比较研究[J].计算机工程与用，2003，（21）：72.

[7]李川，张永辉，译.Ian H.Witten Eibe Frank Mark A.Hall著.数据挖掘实用机器学习工具与技术.机械工业出版社，2014，（5）.endprint