针对垃圾邮件的直接多关键词匹配算法

1、针对垃圾邮件的直接多关键词匹配算法1 本文获863项目“网络信息动态监控及防渗透技术的研究与实现”支持，项目编号：2002AA142110。刘萍 谭建龙 沙瀛中国科学院计算技术研究所北京 2704信箱，100080 E-mail: liuping tan shaying 摘要：本文提出了一种直接扫描电子邮件内容的多关键词匹配算法。邮件文本多采用Base64编码，由于Base64编码是前后相关的，所以完成匹配需要特殊的处理。本文提出的算法在不进行Base64解码情况下，直接对邮件内容进行扫描匹配；同时针对Base64编码结果是32位整型数据流的性质，本算法以32位块进行匹配操作，从而获得了比8位

2、块的匹配更高的效率。实验结果表明，本算法比“解码再匹配”策略快，比直接检索原始文本方法也要快。关键词：垃圾邮件 直接多关键词匹配 串匹配 Base64 StringMatching1 引言 为了扫描邮件病毒、拒绝垃圾邮件，安全系统需要具备对邮件内容进行分析的功能。过滤垃圾邮件，不仅仅需要对发送者地址、收件人地址、域名以及IP地址过滤，还需要对邮件文本内容和附件内容进行过滤。由于邮件内容通常采用Base64编码，而对于编码后的内容，普通关键词匹配就不能直接工作。一种简单直接的方法就是先解码再匹配，这种方法受到对Base64解码速度的限制，使邮件内容处理的速度大大下降。因此，为了实现高效的邮件内容

3、的分析，需要一种能直接在Base64编码文本上进行快度串匹配的方法。目前可以用两种不同的方法来搜索编码后的文本。第一种方法非常实用，是一种专门针对单词、基于Huffman编码的高效解决方案【11】，但这种方法只能检索整个单词和整个句子。第二种方法针对压缩后的文本（压缩也认为是一种编码方式）【2】，目前有很多在压缩后的文本中直接进行关键词匹配的工作。但是由于Base64编码后的数据一般比原始数据要大33，因此直接进行Base64编码的关键词匹配算法不同于一般的文本压缩中的关键词匹配算法。 分析邮件内容需要单独对关键词进行编码，理由主要有两点：一，由于Base64编码是前后相关的，它的编码过程是将

4、每组24 bit的输入表示成一组32-bit的输出。换言之，一个字符的编码值是与它前面的两个字符相关的，这样，同一个原始关键词在不同位置就会产生不同的编码，所以直接扫描Base64文本中编码后的关键词，会产生错误。二，由于电子邮件数据是网络数据中的重要部分，设计一个有针对性的关键词匹配算法将利用编码的特性，提高检索、过滤系统的性能。原始文本经Base64编码后，成为base64字符集中的一个单个字符，占32 位。现在计算机中， CPU在同样的指令执行时间内，既能处理8位的字符型数据，也能处理32位的长整型数据。因此，关键词匹配算法能够利用这个有利条件来提高算法的性能。在Wu-Manber【4】

5、，Commentz-Walter【5】和Jang-Jong Fan【6】等算法的基础上，本文提出了一种高效的分析电子邮件内容的多关键词匹配算法（简称为EMailMatch）。该算法首先在原始关键词字符串中选择3个字符（24位），并按Base64格式将这3元字符编码成4元字符；然后，我们按编码后的4元字符串建立跳跃表；接下来，用4元字符（32位长整型）而不是字符（8位字节）扫描Base64文本。如果得到一个正位移，就可以跳过一段Base64文本。如果不能跳跃，就将Base64文本中的窗口文本解码成正常文本，然后将正常文本同原始关键词字符串进行比较。如果正常文本与原始关键词匹配，则报告发现了某个关

6、键词。实验结果表明，本算法比“解码再匹配”策略快，比直接检索原始文本方法也要快。2 Base64内容传输编码【10】 Base64内容传输编码用来表达任意八位字节的序列。编码过程是将24位一组的位输入表示成32位一组的输出。处理从左向右进行的，一个24位的输入包括3个8位输入组。处理过程中，24位组被当作4个相互链接的6位组，每个6位组被转换成Base64字符集中一个单独的8位字符。下面的图1展示了1个24位转换成32位Base64编码的逻辑过程。由于Base64编码的输出流是以32位为一组的，而在当前计算机中，32位是一个无符号的长整数，所以算法利用这个特性，将32位做为一个块来进行处理，这

7、样能够比以8位为一块的算法（例如：Wu_Manber算法）更快的进行跳跃，从而能够加快扫描的速度。另外，由于Base64编码是前后相关的，所以当原始文本的第一个字节、第二个字节或第三个字节被分在24位中不同的8位位置上，它们产生的编码是不同的。这样，在Base64编码的文本上直接简单的利用32位块来进行串匹配是不可以的，必须要区分3个字节在3个位置的不同情况来处理，这也是本算法核心处理的地方之一。详细处理方法参看下一节的pSkipk值的计算部分。AAAAAAAA |BBBBBBBB | CCCCCCCC |DDDDDDDD |DDDDDDDD |DDDDDDDDaaaaaabbbbbbcccc

8、ccdddddd00aaaaaa00bbbbbb00cccccc00dddddd图1：Base64内容传输编码3 预处理过程在预处理过程中，我们将关键词中的3个字符作为一组进行编码，转换成32位的Base64字符（一个长整数）。因为存储32位字符的直接映射表需要4G空间，为了节约空间，我们将这个长整数散列成一个短整数（16位），同时采用链地址法来处理散列冲突。这一预处理过程类似于Wu-Manber【4】算法。预处理过程中将建立两个表：一个pSkip表，一个pCheck表。pSkip表用于决定将来在扫描Base64文本时，最远能跳跃的距离（这里使用长整数的距离，而 Wu-Manber算法中使用的

9、是字符距离）。当跳跃值为0时，就使用pCheck表。pCheck表用于决定哪个关键词可能匹配，哪里的Base64文本必须被解码，以及如何验证原始文本是否和原始关键词匹配。下面我们将描述pCheck表的细节。pSkip表中的跳跃值决定了在扫描Base64文本时，能够向前跳过多远。我们使用k表示16位的散列值；m表示关键词的长度；ceilDiv(x,y)表示(x+y-1)/y；Base64(s)表示把字符串s使用Base64编码后的串。对于pSkipk的计算，有两种情况：1：k不能从任何关键词的子串中计算出来，则：2：k能够从关键词的子串中计算出来，则：例如，对于字符串“Gutenberg”中的3

10、个字符“ten”，编码得到“dGVu”，“dGVu”使用长整数表示是75564764；然后我们将75564764进行散列，散列后得到一个短整数12850，符合上述的第二种情况，所以得到pSkip12850 =1。当pSkipk=0时，pCheckk的值指向一个TCheckItem的数据结构。TcheckItem中包含从编码域到原始域需要的全部信息。TcheckItem中有一个成员pNext，pNext指向另一个TcheckItem的数据结构或为NULL。TcheckItem的信息如下表1所示。short int pattern_index; /用于匹配的候选关键词索引Long first_co

11、de; /能从此关键词中计算出的第一个长整数short int first_check; /起始位置在此关键词中的第一个长整数short int back_distance; / Base64文本索引将要回溯的长度short int decode_len; /Base64文本将会被解码的长度short int compare_postion; /原始文本将要从何处开始与关键词比较TCheckItem * pNext; /指向下一个需要匹配的候选关键词表1：CheckItem 信息结构成员first_code和first_check 类似Wu-Manber算法中的Prefix，它用于加快匹配校验

12、的速度。由于对Base64编码文本的窗口文本解码比较耗时，所以我们首先使用first_code对要解码的窗口文本进行确认，看是否可能出现匹配。结构成员back_distance、decode_len和compare_postion用于对Base64文本窗口解码并检验是否与原始文本匹配。它们的关系可以参看图2的示例。first_codeBase64 文本：编码字符串：原始字符串原始文本：decode_length:4compare_postion:2back_distance:2字符串长度：8图2：TcheckItem示例4 扫描过程本算法的扫描过程虽然与Wu-Manber 的算法很类似，但有两

13、个主要的区别：一，我们把输入的Base64文本改为长整型数组，这样可以一次处理32位，同时加快散列的速度。这也是我们的算法适宜32位计算机硬件的主要原因。二，在我们校验原始文本和原始关键词是否匹配前，我们先校验Base64文本和关键词编码后的第一个长整数是否相等。只有在这个长整数相等的情况下，才进一步解码，这样就进一步减少了需要解码的可能性。EmailMatch的主要流程如下：Step 1：计算出Base64文本中基于当前长整数的散列值k；Step 2：检查pSkipk的值，如果该值0，则向后跳跃pSkipk的距离，并回到Step 1；否则到Step 3；Step 3：检验链接在pCheckk

14、的每一个TCheckItem结构，如果TcheckItem结构的first_code等于Base64文本中相应位置的长整数则跳到Step 4；否则继续检验下一个TcheckItem结构。当全部链接在pCheckk的TCheckItem结构检验完成时，则向后跳跃一个距离，并回到Step 1；Step 4：将Base64文本中相应位置的文本解码成原始文本，直接将此原始关键词与原始文本进行核对：如果相等，则报告发现关键词。回到到步骤3；（所有原始关键词的信息都从TcheckItem中得到）。long * plong;plong=(ITEM_TYPE *)data; /change base64 te

15、xt to long arrayint itemDataLen=datalen/4;int itemLen=m/ 3 -1;for(i=itemLen ;i<itemDataLen;) l=plongi; p=MIX_HASH(l); /step1:hash to 16-bits if(pSkipp >0)i=i+pSkipp;continue; /step 2: pci=pCheckp;while(pci!=NULL)pp=&(pPatternspci->pattern_index); /step 3:if(plongi - pci->first_check

16、= pci->first_code) nowp=(i - pci->back_distance)*4; /step 4: DecodeBase64(&(datanowp); /If verify match of original text and original pattern ,then report the match ; pci=pci->pNext; ; i+;表2： EMailMatch 检索文本算法表2中，我们给出EmailMatch算法中检索文本流的部分C代码。全部代码和测试数据可以从2 下载。5 EmailMatch算法的实验为了评价算法性能，我们

17、将EMailMatch同agrep，fgrep进行了比较。我们使用0xffff 大小的pSkip表和pCheck表，一台1.6GHz Pentium IV CPU，128M内存的工作站。测试结果的所有时间都是用Linux的time命令得到的用户时间。在实际运行中，因为关键词匹配算法的速度很快，很难准确测量出一次的执行时间，因此测试时间是运行100次的时间总和。所有算法，包括EmailMatch，fgrep和agrep都使用相同编译选项“O2”。fgrep的版本是2.5.1，agrep的是从glimpse-4.15.tar.gz得到的。文本数据集与SumKim1999【12】的数据集一致：文本文

18、件取自Gutenberg项目中的King James Bible，关键词从Unix词典/usr/dict/words中选取。我们从这些单词中随机选取了一组关键词，它们的长度均为10。比较结果见图3。应该注意到：fgrep或agrep检索的是原始长度为4.7M的文本，但是EMailMatch检索的是6.2M的Base64文本。从图中可以看到，虽然EmailMatch扫描匹配的文本大小为fgrep或agrep扫描的133，但是它所用的时间却比它们都少。图3：对文本字符串检索100次的运行时间之和更重要的是EMailMatch算法能够直接检索Base64文本。与Wu-Manber算法的平均时间一样，

19、Base64算法解码所需的时间复杂度是O(n)，因此EmailMatch算法比解码再匹配的方法快m倍。表3将我们的算法同解码再检索的方法进行了比较，从中可以看到：EmailMatch算法平均能比解码再匹配的方法加速595。解码再匹配的方法所需的平均时间高于O(l)+O(n)，而EmailMatch方法所需的平均时间是O(n/m)。字符串原始文本- agrep解码再agrepBase64-EMailMatch1006.546.76.32005008.348.68.08009.549.49.210009.749.810.4表3：对长度为10的字符串检索100次的时间和 6结论和

20、展望本文提出的EmailMatch算法针对Base64编码结果是32位整型数据流的性质，充分利用了计算机硬件数值运算的能力，以32位块代替8位块进行匹配操作，获得更高的匹配效率。但是该算法也有一定的局限性：首先它和Agrep、ShiftOr【2】等算法一样，在设计算法时把机器的字长作为一个因素来考虑，使得算法在某些情况下不适合使用；其次它需要关键词有一定的长度，本算法要求大于6个字符，对于长度大于2个字符的关键词，算法也可以使用同样的思想进行设计。EmailMatch算法的将关键词编码而不是把编码文本解码的思想是通用的，可以使用在UT7、UT8、BIG5等编码文本的字符串匹配中。由于多关键词匹

21、配算法基本是亚线性的算法，使用这种将关键词编码再直接匹配的方法，就可以把必须使用O(n)时间的解码算法优化为O(n/m)时间的匹配算法，从而提高整个系统的性能。另外，EmailMatch算法是在LongMatch【15】算法基础上改进的，这种考虑硬件加速和分前后两次校验的思想，对优化其他算法也有借鉴作用。在未来的工作中，我们将把这个设计思想应用到多DNA序列匹配系统和G带宽的网络信息安全系统中，希望能提高这些系统的性能。致谢：本文工作过程得到程学旗、郭莉、李栋栋、卜东波和安全组的全体同事等人的建议、帮助和支持，在此表示感谢！参考文献：1 Gonzalo Navarro and Mathieu

22、Raffinot , Flexible Pattern Matching in Strings:Practical on-line search algorithms for texts and biological sequences, Cambridge University Press, 2002,ISBN 0-521-81307-72 Gonzalo Navarro. Regular Expression Searching over Ziv-Lempel Compressed Text. In Proc. 12th Combinatorial Pattern Matching Con

23、ference (CPM'01), pages 1-17, 2001. LNCS 2089.3 Dan Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and computational Biology, University of California Press, CA, 19974 Sun Wu，Udi Manber,A FAST ALGORITHM FOR MULTI-PATTERN SEARCHING”,Technical Report Department of Computer

24、Science Chung-Cheng University Chia-Yi, Taiwan .tw5 Jang-Jong Fan, Keh-Yih Su: An Efficient Algorithm for Matching Multiple Patterns. IEEE Transactions on Knowledge and Data Engineering (TKDE) 5(2): 339-351 (1993)6 Commentz-Walter, B, A string matching algorithm fast on the average, Proc

25、. 6th International Colloquium on Automata, Languages, and Programming (1979), pp. 118-132. 7 BOYER R.S., MOORE J.S., 1977, A fast string searching algorithm. Communications of the ACM. 20:762-772.8 Aho, A. V., and M. J. Corasick, Efficient string matching: an aid to bibliographic search,Communicati

26、ons of the ACM 18 (June 1975), pp. 333-340.9 Carnivore Diagnostic Tool /hq/lab/carnivore/carnivore.htm10 Request for Comments: 1521: MIME (Multipurpose Internet Mail Extensions) Part One:Mechanisms for Specifying and Describing the Format of Internet Message Bodies11 E.Moura,G.Navar

27、ro,N.Ziviani,and R.Baeza Yates.Fast and exible word searching on compressed text.ACM Trans.on Information Systems 2000,Previous versions in SIGIR'98 and SPIRE'9812 Sun Kim A Fast Multiple String-Pattern Matching Algorithm,17th AoM/IAoM Interantional Conference on Computer Science, San Diego, CA, August, 1999 1999_/sunkim/13 T. Nishimura, Shuichi Fukamachi, Takeshi Shinohara: Speed-up of Aho-Corasick Pattern Matching Machines by Rearranging States. SPIRE 2001: 175-18514 王永成沈州许一震,改进的多模式匹配算法,计算机研究与发展2002 Vol.39 No.115 谭建龙 白硕 郭莉 宋新波, 一种新的多关键词匹配算法Long-Karp-Rabin