决策树(彭展)

1、文献总结（华为项目）Using Decision Trees to Improve Signature-Based Intrusion Detection在入侵检测系统中，数据包与规则集之间的匹配过程是最耗时的，目前许多算法都是将每一个输入的数据包依次和所有的规则进行比较，从而确定匹配上的规则，或无任何匹配，但在该过程中存在大量冗余比较，所以这种方法远远没有达到最优。这里给出了一种方法，将机器学习中的聚类算法应用到规则匹配过程中，以提高匹配效率。该方法依据给定的规则集来构造一棵决策树，使匹配过程中的比较次数尽可能少，从而提高了整体效率。一、 基本思想：该方法可以分为两个步骤，首先依据给定的规则

2、集建立一棵决策树，接着利用该决策树对网络上的数据包进行匹配，具体过程如下：1. 建立“决策树”：该方法将最初的包含所有规则的集合作为决策树的根节点，然后运用ID3算法，在根节点所包含的规则集合中选取最具有区分度的规则属性，作为根节点的属性标签，再按照规则集在该属性上的不同取值，对其进行分组，分组后的每一个子集都作为根节点的孩子节点并入决策树，在由根节点到孩子节点的分支上，标注该孩子节点所代表的规则集在根节点属性上的取值。当决策树中，存在一个节点包含多于一个规则时，继续使用ID3算法和上述步骤对该节点进行分组，但在选取属性时不能选择前面已经标注过的属性。在决策树中，每一个叶子节点，都只包含一条规

3、则，或者一些规则，这些规则不能被任何属性区分开（即这些规则在所有未标注属性上的取值相同）。依照上述过程，可以确保建立起一棵最优“决策树”，即决策树的高度最短，从而将其用于数据包与规则集的匹配时，能够使平均比较次数最少。2. 利用“决策树”进行规则匹配：当IDS接受到一个数据包时，匹配过程将从决策树的根结点开始，根据当前节点的属性标签，来检测数据包中该属性的实际取值，依据该属性值选择相应的孩子节点，作为下一步进行检测的节点。如果匹配过程持续，直到在检测某节点时，无法找到与数据包在该节点属性值一致的孩子节点，这说明没有任何规则与该数据包匹配，匹配过程立即结束。如果该过程持续进行，直到终止于某个叶子

4、节点，则该叶节点所包含的所有规则就是与数据包“潜在”匹配的规则，接着要将数据包与这些规则的剩余属性（即在匹配过程中没有检测过的属性）进行比较，以确定最终匹配上的规则，或者没有任何规则与之匹配。二、 算法详解：假设规则集中有4条snort规则：Source Address(SA) -> Destination Address(DA) : Destination Port(DP)(1) 192.168.0.1 -> 192.168.0.2 : 23（content:）(2) 192.168.0.1 -> 192.168.0.3 : 23（content:）(3) 192.168.

5、0.1 -> 192.168.0.3 : 25（content:）(4) 192.168.0.4 -> 192.168.0.5 : 80（content:）在建立决策树的过程中，对每一个节点的属性选取是至关重要的，它决定了所建成决策树的形状和深度，会直接影响决策树的效率。为了说明属性的选择对决策树的影响，考虑下面的情形：如果我们简单地按“Source Address(SA)”“Destination Address(DA)”“Destination Port(DP)”的顺序来选取属性，来依次划分规则集，则建成的决策树将如图1所示：图1. 按照SA-DA-DP的顺序建立的决策树该决策

6、树的高度为3，就是说在最差情况，数据包需要进行3次属性检测才能确定与之匹配的规则，但这并不是最优情况。为了建成最优决策树（即树高最短），我们采用了ID3算法的变种，具体建树的流程如下：Step1：初始化决策树，建立根节点，其内容包括：R(规则集) = 所有规则；A(属性集) = 规则的所有属性。Step2: 如果决策树的所有叶节点满足：其规则集R在属性集A每个属性的所有取值均相同，则结束；否则，转Step3：Step3: 对所有不满足Step2中条件的叶节点，对计算其信息增益：G(R, a) = 其中，Val(a)为规则集中的所有规则在属性a上的所有可能的取值。Step4：选择具有最大信息增益

7、的属性，将R中在上具有相同值的规则分成一组，建立叶节点,其规则集且，转Step2。为了说明如何采用上述步骤来建立决策树，我们同样考虑前面的例子。首先，在根节点时，我们有R=1,2,3,4，A= SA， DA， DP，我们分别对A中的3个属性值，计算其信息增益：1.231.591.59由于DP和DA的信息增益一样，且均大于SA，因此我们选择DP（Destination Port）作为该节点的属性标签（亦可选择DA），即对该节点所包含规则进行划分的依据，根据R中规则在该属性上的不同取值，可将R划分为3个子集，如图2所示：图2. 选择Destination Port属性划分初始规则集由于划分后的3个

8、子集中，有两个子集仅包含一个规则 （3、4），因此无需对其继续划分。而规则子集1,2（根节点最左边的孩子节点）包含2条规则，需要进一步行划分，该规则子集的可用划分属性为：A=SA,DA，我们分别计算SA和DA的信息增益：0.480.72因为DA的信息增益较大，所以选择DA作为该规则子集的划分属性，根据该集合中规则在DA上的不同取值，将其进一步划分为两个子集，如图3所示：图3. 选择属性Destination Address对规则子集1,2进行划分现在，每个叶节点都只包含一条规则，因此无需继续划分，决策树建立完毕。相比之前建立的决策树（图1），新建成的决策树高度只有2，即在最坏情形，只需比较2次

9、即可确定匹配的规则，效率相比之前有所提高。三、 实验与结果分析：实验环境：我们实现了自己的决策树算法(Snort NG)，并和原始的snort2.0引擎进行性能对比。实验采用奔腾 1.8G的CPU，运行在Linux RedHat（2.4.18 kernel）操作系统下。我们采用的测试数据集是MIT Lincoln Labs的流量监控数据，该数据集由大小从216 MB 到 838 MB不等的文件组成。图4.与snort2.0对测试数据的总处理时间对比1.首先，我们测量了两种方案在处理完测试数据集时所需要的总时间，见图4。对每种测试数据文件，均运行10次，并对测量结果平均化，作为算法的运行时间。由于不同大小的测试数据文件，决策树法相比原snort引擎的提升程度也各不相同。对于所有数据集而言，决策树方法相比原snort系统，性能的最大提升幅度为103%，最小提升幅度为5%，平均提升40.3%。2.其次，我们测量了在不同规则数量下，两种方案的运行时间，见图5。规则数量从150条递增至1581条。由实验结果可知，决策树方案相比原有方案，在不同规模的规则集下，性能均有所提升，尤其对于数量较大的规则集，提升更加