垃圾邮件快速检测技术摘要:提出了高速网络环境下一种实时检测垃圾邮件的方法，将正文抽取一部分做指纹散列，散列后的指纹值可以发现重复的正文内容。

不需要解码也不需要处理全部邮件内容，并且散列内容数量和邮件大小无关尤其对于普通文本分类方法无法处理的二进制类型的垃圾邮件有较好的处理效果，适合在高速骨干网络环境下作为一种快速垃圾邮件检测的手段。

初步实验证明，该方法具有较高的处理速度，重复内容判定准确。

关键词: 垃圾邮件高速网络环境快速检测目前通常采用文本分类来识别垃圾邮件。

例如贝叶斯分.类算法.决策树.支持向量机等，这些方法通过一定的训练分类可以达到较高的识别率，但它们都需要对邮件进行解码分词和做大量概率运算，处理过程非常复杂，需要很多的处理时间，且不适合在高速网络环境下应用。

本文所指的高速网络环境是指在一些骨干网络中稳定的网络流量可以达到每秒几百兆几千兆比特，对信息进行任何处理都需要极高的性能，而在低速百兆位网中适用的方法会因为无法达到对数据的线性处理而失效。

另外，垃圾邮件的内容特征变化很大，这导致了基于内容过滤的方法需要不断地训练和更新，在对新类型的垃圾邮件的判定方面往往有一定的滞后。

目前有很多邮件蠕虫病毒或者新型的垃圾邮件为了逃避文本分类方法的过滤，将垃圾内容或者病毒以二进制附件的形式大量发送。

这是文本分类所无法处理的。

而本文所提出的基于数字指纹检测的垃圾邮件判定方法不仅可以处理这种二进制类型的垃圾邮件也适应了高速网络中快速检测要求。

1 垃圾邮件定义现有的垃圾邮件通常利用程序通过群发的方式生成。

其中发信人.主题等邮件头部都可能是虚构或者随机生成的，但正文部分或者附件部分对同一封垃圾邮件来说是固定的。

本系统垃圾邮件的定义范围是邮件内容（正文或者附件）重复率超过一定阈值的邮件。

阈值可以经过具体环境的训练后调整。

更谨慎的做法是在这一步判定后再使用一些常规的方法进一步确认是否垃圾邮件，事实上经过这一步判定后需要进一步判定邮件的范围会被大大缩小，后续的操作也不会过多的影响效率为了适应一些小型网络环境，本系统可以以分布式的结构散布在若干个小型网络上共用一个Hash 表。

2 重复邮件发现2.1 基于数字指纹的重复内容识别如何高效地识别邮件正文内容是否重复是本系统的核心，为了产生包含邮件正文数据包中的内容的特征值，采用了Manber [1] 提出的在文件系统中查找相似文件的方法。

将所有邮件正文抽取出一部分来计算Rabin 指纹[2]。

设字符集有s个元素，q为大于s的最小质数，{0,1…, q}构成一个有限域Zq。

则字符集是Zq 的一个子集，对于字符串a = a 1 a 2 .... a m ∈ ∑ 多项式f(t)将字符串映射到一个特征为q 的多项式域 F q [ t ] / g 中其中g 为一个度数为k 的不可约多项式(k 为质数) 则有f ( t ) = a 1 t + a 2 t + .... + a m ∈ F q [ t ]则这个字符串的Rabin 指纹值为f = f mod g。

实际系统中设定t 为一个质数，给定一个度数为k 的不可约多项式g M=g(t) (实现时通常直接给定M 是一个大质数)将M 设为Hash 的表大小，则可利用指纹函数计算字符串指纹值并存储到Hash 表中指纹函数和一般Hash 函数的区别在于普通Hash 函数只是将字符串均匀散列到Hash 表中它关心的是冲突时所需要跳跃的步长，而指纹函数希望总是能够避免冲突，原字符串不同而指纹相同的概率是很小。

下面定理在理论上表明了这一点定理a = a 1 a 2 .... a m ∈ ∑ |a|=m，假定为计算指纹随机选取一个度数为k 的不可约多项式g 作为域 F q [ t ] / g 的生成多项式P 表示原字符串不同而指纹值相同的概率即出现冲突的概率，那么P ≤ m k 定理的证明参见文献[2]。

图1 是本系统中随机生成200B 的邮件正文，用Rabin指纹散列后的冲突情况。

图1 的横轴表示散列后插入Hash表的邮件数目，纵轴表示产生冲突的百分比。

冲突率=产生冲突的指纹数目/指纹总数，可以发现Rabin 指纹产生的冲突是很小的。

2.2 压缩后的Hash 表存储为了防止可能出现的散列冲突，我们为每个散列后的指纹值保留了一定的原始数据，但为了避免太多的拷贝操作，我们保留的是经过压缩后的原始数据。

在本系统中，将一定字节的原始数据做散列后按一定顺序取10%的原始数据和散列后的指纹值一起存进Hash 表中在插入Hash 表的时候只有当字节的散列值和10%的压缩数据都相同时才认为其是重复正文。

本系统在上述的冲突测试中已经发现在150 万封的邮件数据中，原始数据不同，但压缩数据和散列指纹都相同的概率是0 这样已经可以保证经过指纹值和压缩数据都相同的邮件，它的邮件正文一定是相同的。

2.3 重复邮件发现算法(1)解析POP3(SMTP)协议定位到邮件正文(2)对数据调用Hash 函数计算指纹值同时读出压缩后的原始数据（3)插入Hash 表检测相应位置的元素1)如果发现相同的Hash 元素元素重复计数指针加1，判断是否达到阈值若达到阈值则报告。

2）如果指纹值和压缩数据是新发现内容，新增加一个元素，项链入散列表，重复设指针为1 插入时间为当前时间。

(4)计算Hash 表内元素是否达到需要一个临界值，如果是，调用函数来清除时间上已经过期的Hash表元素。

2.4带权值的判定手段为了判定一些明显的垃圾邮件，但重复率目前还比较低的邮件，在判定时采用一些常规的分析邮件头的手段来分析邮件头分析结果为一个权值W 如果目前邮件重复数目为Q 重新定义邮件重复值C=W*Q 这样就给具有明显垃圾邮件特征的邮件头设定一个比较高的权值这时邮件的重复值会比较大，而对一些邮件头看起来比较正规的邮件且很可能是用户群发产生的重复邮件，我们给定一个比较低的的权值。

这时邮件重复值就会比较低具体实现中我们通过判定邮件头是否伪造，重复邮件的邮件头是否固定来区分垃圾邮件。

这些判定都在发现重复内容后进行，例如从发现第2封重复邮件后才开始分析计算其后具有重复内容的邮件头，根据结果来调整这封邮件的权值。

3底层队Libnids函数的改进目前的libnids中应用层数据被拷贝的过程如下：（1）每个合法tep连接建立时为每个连接分配一个应用层缓冲区以后每个该连接的数据包来到时解析各层包头，定位到应用层数据。

（2）拷贝数据包中应用层数据到应用层缓冲区。

（3）调用应用层处理模块，将应用层缓冲区的指针提交给处理模块，上层处理完毕后返回。

(1)对每次来到的数据包定位到应用层数据后判断当前是否有残余数据(2)如果没有则直接提交给上层处理否则拷贝到应用层缓冲区后再提交给上层处理(3)上层处理完毕后判断是否有残余数据尚未处理如果有则拷贝到应用层缓冲区中再返回否则直接返回对改进的分析如下这种改进实际上延迟了数据包拷贝的时间由每次应用层数据到来就需要拷贝推迟为当发现应用层缓冲区中尚有上次未处理完的残余数据时再拷贝。

当应用层能够每次处理完所有本次提交上来的包的情况下，这种方法比原有系统完全减少了一次拷贝应用层数据的操作，当应用层需要保留一些数据和下次操作一起处理的情况下这种方法推迟了应用层数据拷贝时间也减少了一定量的数据拷贝，同时仍然保证下次提交上来的数据和本次数据在物理位置上是连续的在系统中应用层关心的只是具体数据以及数据是否连续不关心每次调用之间数据的具体位置这种方法对应用层来说改变了数据的物理位置但仍然保证了数据在物理上的连续性。

4 系统结构本系统的底层采用libnids 的结构来捕包并还原为应用层数据流如图 4 底层经过诸如零拷贝等技术的优化改进可以在高速网络环境下捕捉几百兆每字节的数据包而上层应用层的协议解析模块用于定位需要散列的邮件正文定位后即时散列每一位数据并取出压缩的原始数据散列后的散列值和原始数据插入到Hash 表中Hash 表元素会在一定时间后过期它的插入和删除都由一个Hash 表类来管理，邮件散列后在插入时判断是否达到阈值达到阈值就报告，并作后续截断处理。

5 模拟实验和性能分析我们在主机中模拟一个小型网络环境来测试系统对垃圾邮件的识别率和处理性能，采用垃圾邮件语料库中的Ling-Spam 语料。

其中包括正常邮件2 412 封和垃圾邮件481 封我们将正常邮件和垃圾邮件混合起来在模拟网络中发送和接收。

模拟网络中节点主机数目为100 个其中包括1 台邮件服务器和99 个邮件客户端邮件客户端互相在高速发送邮件。

其中有几个是垃圾邮件节点专门重复发送垃圾邮件。

发送对象为模拟网络中随机的一些节点发送的邮件数据都是真实采集下来的邮件数据，由于是在一台主机内存中做模拟因此这个模拟网络中流动的smtp 和pop3 的协议数据量可以达到高速网络环境的数据量。

所有发送和接收的邮件都由邮件服务器节点中转我们检测这个网络中流动的pop3 协议数据当发现用户在收取某封垃圾邮件后截断用户收取该邮件的操作。

我们在模拟网络中发送了2 412 封合法邮件和481 封垃圾邮件其中垃圾邮件随机向50 个100 个节点发送合法邮件随机向 1 个10 个节点发送设定阈值为10 在CPU 主频为赛扬800MHz 的主机上实验最后测试结果如表1从结果中可以看出本系统能够在高速环境下很好地进行垃圾邮件检测和封堵，对于达到阈值的垃圾邮件判定率达到100%封堵率和系统阈值以及垃圾邮件发送总数相关。

系统处理的时间性能由于CPU 等硬件的不同而会有所差异，在此先做理论上的分析本系统只需要分析邮件的前几个包，时间开销主要在固定长度n 字节的数据做Hash 散列的运算和Hash 表插入上这些时间都是一定的不受整个邮件长度的影响。

所以我们的算法的时间复杂度是O(1) 不需要训练时间，而目前其他分类算法的都需要训练和分类其时间复杂度一般是O ( n ) ~ O ( n 2 ) 之间，并且需要训练和动态调整训练集本算法的主要优势是不需要训练并且对每封邮件处理的时间复杂度是O(1)。

另外我们发现系统能适应的高速网络环境系统流量的多少取决于系统平均处理每封邮件所需要的时间。

假定在一段时间t 内并发传输n 封邮件令P 表示平均每封邮件在传输中的数据量，当时网络环境为Q bps 如果本系统处理每封邮件需要m 秒则当P/Q >m 时系统就可以在当前网络环境中做到实时快速检测。

在每封邮件传输的数据量是80kB 高速网络环境中邮件数据的流量是500Mbps 的情况下，为达到线速处理本系统处理每封邮件必须在0.16s 之内。

这种性能在通常的邮件分析算法上是达不到的。

我们在CPU 主频为赛扬800MHz 的主机上实验后，测得的每封邮件处理时间不到0.1s 这说明在硬件要求不太高的情况下，本系统就可以做到在高速网络环境中对重复邮件的完全检测。