论文部分内容阅读
[摘要]在分析现有基于网络入侵检测系统的规则匹配算法的基础上，提出一种基于哈希函数的规则匹配方法，通过与现有网络入侵检测系统Snort[1]进行比较，证明该系统匹配速度要高于Snort。
[关键词]入侵检测 规则匹配 哈希函数
中图分类号：TP309 文献标识码：A 文章编号：1671－7597(2008)0810027－01
一、引言
作为网络安全监测和防护的重要手段之一,基于网络的入侵检测系统（NIDS）已被广泛应用在各类网络环境中。NIDS 捕获计算机系统和网络中传递的所有数据包,与已知的攻击模式(即规则) 进行比较,从而发现来自网络外部的攻击行为和网络内部的违规行为。
在基于网络的入侵检测系统中,相对耗时的操作主要有四个:从网络传输介质上捕获数据包,分析数据结构,规则匹配以及对每一个数据包进行的校验。其中,规则匹配是核心运算模块,如果能够提高它的运算速度,将有效提高NIDS的整体性能。
二、提高网络入侵检测系统规则匹配速度的方法
（一）现有匹配方法介绍
1．传统的模式匹配技术。传统的模式匹配就是将收集到的信息与已知的网络入侵和系统入侵规则库进行比较，从而发现违背安全策略的行为。算法描述:对从网络上捕获的每一数据包进行分析；从网络数据包的包头开始和攻击特征比较；如果比较结果相同，则检测到一个可能的攻击；如果比较结果不同，从网络数据包中下一个位置重新开始比较；网络数据包中的所有字节匹配完毕，一个攻击特征匹配结束；重复步骤2，进入下一攻击特征的匹配；直到每一个攻击特征匹配完毕，该数据包的匹配完毕；对下一捕获的数据包进行分析。
传统模式匹配算法的缺点：不能适应高速网络环境；丢包率高。
2．协议分析方法。传统的模式匹配技术的一个基本出发点就是将数据看作一个无序随意的字节流，认为包结构是未知的。协议分析方法利用在网络通信协议的标准化、层次化、格式化的特点和模式匹配结合进来，来实现对数据流的检测。在攻击检测中，利用这种层次性对网络协议逐层分析，然后再使用模式匹配方法，以弥补单纯模式匹配方法的不足。和传统匹配技术相比，减少每个数据包需检测的规则数，提高了检测效率。
（二）模式匹配方法的进一步改进
1．哈希算法的基本思想。传统的单模式匹配算法必须对每条表示攻击特征的模式串进行逐条匹配，这样需要对被测数据包进行多次的扫描，并且扫描次数与模式的数量相当，随着检测规则数目的增加，系统的性能会急剧下降。如果能够从攻击模式库整体的角度建立检测的启发函数，进而同时对所有的攻击模式进行检测，那么整个系统的检测效率将会大大提升。
哈希算法是一种重要的算法，它的理想情况是不经过任何比较，一次存取就可以得到所查询的记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。
2．基于哈希算法的检测方案。首先根据检测的需求和特点，设计一个大小适当的哈希空间和一个计算攻击模式哈希特征值的哈希函数。在检测前先用哈希函数计算每个攻击模式的哈希特征值，并将攻击模式字符串的关键信息(如攻击模式的id号，所属类别等)存储在哈希空间中哈希值所相应的位置上。对网络包有效载荷进行检测的初步设想如下:
（1）用哈希函数计算报文中每一个与模式字符串长度相同的子串的哈希特征值。
（2）在哈希空间中寻找是否有相同哈希特征值的模式信息。
（3）如果在哈希空间检测到与报文子串具有相同哈希特征值的模式信息的话，则需要对具有相同哈希特征值的模式和报文的子串进行进一步的精确匹配检测，检测报文和模式每一字节是否完全相同，进而确定是否发现了可能的攻击，然后回到步骤1检测下一个报文子串；如果不存在具有相同哈希特征值的模式信息，则直接回到步骤1检测下一个报文子串。执行上述的操作直至到达报文的尾部。
三、性能分析
从表1中看出，SNORT[2]系统的检测时间平均为447.391ms，采用哈希算法的系统的检测时间平均为240.109ms，规则匹配的时间平均降低了约46.2％,并且随着规则数目的逐渐增加，后者的速度优势也在逐渐扩大。从理论上说，后者由于采用了多模式匹配，其检测速度应该比前者快数倍，但是由于笔者未对大量的检测规则进行详细的分类，特征数组中置1的元素也就增多，所以在扫描区间划分时会造成需要扫描的区间数目较多，从而一定程度上阻碍了后者的优势进一步扩大。但是尽管如此，通过以上实验数据的对比，我们仍然可以得出基于哈希算法的多模式匹配检测技术在入侵检测的速度上具有更大的优势。
四、结论
通过上述的实验可以看出,基于哈希算法实现的入侵检测系统从整体上大幅度提高了Snort的检测速度。在规则数目较少时，基于哈希算法的多模式匹配检测系统的优势并不是很明显，但是随着规则数目的增加，两者的差距也在扩大，基于哈希算法的多模式匹配检测系统显示出更大的优势。由此可见，基于哈希算法多模式匹配的入侵检测系统具有良好的发展前景。
参考文献：
[1]D.E.Denning，An intrusion-detection model，IEEE Transactions on Software Engineering，Vol. 13 1987， no. 2，pp.222-232。
[2]REN Xiao feng; DONG Zhan qiu，Research and Implementation on Increasing Speed of Rule-matching in Snort，Computer Applications，2003，23（4）：59-61.
[关键词]入侵检测 规则匹配 哈希函数
中图分类号：TP309 文献标识码：A 文章编号：1671－7597(2008)0810027－01
一、引言
作为网络安全监测和防护的重要手段之一,基于网络的入侵检测系统（NIDS）已被广泛应用在各类网络环境中。NIDS 捕获计算机系统和网络中传递的所有数据包,与已知的攻击模式(即规则) 进行比较,从而发现来自网络外部的攻击行为和网络内部的违规行为。
在基于网络的入侵检测系统中,相对耗时的操作主要有四个:从网络传输介质上捕获数据包,分析数据结构,规则匹配以及对每一个数据包进行的校验。其中,规则匹配是核心运算模块,如果能够提高它的运算速度,将有效提高NIDS的整体性能。
二、提高网络入侵检测系统规则匹配速度的方法
（一）现有匹配方法介绍
1．传统的模式匹配技术。传统的模式匹配就是将收集到的信息与已知的网络入侵和系统入侵规则库进行比较，从而发现违背安全策略的行为。算法描述:对从网络上捕获的每一数据包进行分析；从网络数据包的包头开始和攻击特征比较；如果比较结果相同，则检测到一个可能的攻击；如果比较结果不同，从网络数据包中下一个位置重新开始比较；网络数据包中的所有字节匹配完毕，一个攻击特征匹配结束；重复步骤2，进入下一攻击特征的匹配；直到每一个攻击特征匹配完毕，该数据包的匹配完毕；对下一捕获的数据包进行分析。
传统模式匹配算法的缺点：不能适应高速网络环境；丢包率高。
2．协议分析方法。传统的模式匹配技术的一个基本出发点就是将数据看作一个无序随意的字节流，认为包结构是未知的。协议分析方法利用在网络通信协议的标准化、层次化、格式化的特点和模式匹配结合进来，来实现对数据流的检测。在攻击检测中，利用这种层次性对网络协议逐层分析，然后再使用模式匹配方法，以弥补单纯模式匹配方法的不足。和传统匹配技术相比，减少每个数据包需检测的规则数，提高了检测效率。
（二）模式匹配方法的进一步改进
1．哈希算法的基本思想。传统的单模式匹配算法必须对每条表示攻击特征的模式串进行逐条匹配，这样需要对被测数据包进行多次的扫描，并且扫描次数与模式的数量相当，随着检测规则数目的增加，系统的性能会急剧下降。如果能够从攻击模式库整体的角度建立检测的启发函数，进而同时对所有的攻击模式进行检测，那么整个系统的检测效率将会大大提升。
哈希算法是一种重要的算法，它的理想情况是不经过任何比较，一次存取就可以得到所查询的记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。
2．基于哈希算法的检测方案。首先根据检测的需求和特点，设计一个大小适当的哈希空间和一个计算攻击模式哈希特征值的哈希函数。在检测前先用哈希函数计算每个攻击模式的哈希特征值，并将攻击模式字符串的关键信息(如攻击模式的id号，所属类别等)存储在哈希空间中哈希值所相应的位置上。对网络包有效载荷进行检测的初步设想如下:
（1）用哈希函数计算报文中每一个与模式字符串长度相同的子串的哈希特征值。
（2）在哈希空间中寻找是否有相同哈希特征值的模式信息。
（3）如果在哈希空间检测到与报文子串具有相同哈希特征值的模式信息的话，则需要对具有相同哈希特征值的模式和报文的子串进行进一步的精确匹配检测，检测报文和模式每一字节是否完全相同，进而确定是否发现了可能的攻击，然后回到步骤1检测下一个报文子串；如果不存在具有相同哈希特征值的模式信息，则直接回到步骤1检测下一个报文子串。执行上述的操作直至到达报文的尾部。
三、性能分析
从表1中看出，SNORT[2]系统的检测时间平均为447.391ms，采用哈希算法的系统的检测时间平均为240.109ms，规则匹配的时间平均降低了约46.2％,并且随着规则数目的逐渐增加，后者的速度优势也在逐渐扩大。从理论上说，后者由于采用了多模式匹配，其检测速度应该比前者快数倍，但是由于笔者未对大量的检测规则进行详细的分类，特征数组中置1的元素也就增多，所以在扫描区间划分时会造成需要扫描的区间数目较多，从而一定程度上阻碍了后者的优势进一步扩大。但是尽管如此，通过以上实验数据的对比，我们仍然可以得出基于哈希算法的多模式匹配检测技术在入侵检测的速度上具有更大的优势。
四、结论
通过上述的实验可以看出,基于哈希算法实现的入侵检测系统从整体上大幅度提高了Snort的检测速度。在规则数目较少时，基于哈希算法的多模式匹配检测系统的优势并不是很明显，但是随着规则数目的增加，两者的差距也在扩大，基于哈希算法的多模式匹配检测系统显示出更大的优势。由此可见，基于哈希算法多模式匹配的入侵检测系统具有良好的发展前景。
参考文献：
[1]D.E.Denning，An intrusion-detection model，IEEE Transactions on Software Engineering，Vol. 13 1987， no. 2，pp.222-232。
[2]REN Xiao feng; DONG Zhan qiu，Research and Implementation on Increasing Speed of Rule-matching in Snort，Computer Applications，2003，23（4）：59-61.