分析电子邮件的多关键词匹配算法.doc

分析电子邮件的多关键词匹配算法1 本文获973课题：“基于Internet超大规模知识检索的算法及应用”支持。项目编号：谭建龙 白硕 张鑫 沙赢中国科学院计算技术研究所北京 2704信箱，100080 E-mail: 摘要：本文第一次提出了一种直接扫描电子邮件内容的多关键词匹配算法。一般情况下，邮件文本是基于Base64编码的，由于Base64编码是前后相关的，所以需要特殊的处理。新算法在不进行Base64解码情况下，直接进行内容扫描。同时针对Base64编码结果是32位整型数据流的特性，新算法不是以8位为块,而是以32位为块进行匹配。通过和agrep和fgrep查找工具比较，新算法比解码再检索的方法快，甚至比直接检索原始文本方法还快。关键词：网络安全 信息监控 多关键词匹配 串匹配 电子邮件 Base64 StringMatching1 引言 在网络信息监控和入侵监测系统中，目前广泛使用的是用固定关键词集合检索数据流的方法。检索系统对每个“网络数据流”进行扫描，丢弃许多原始数据，大大减少后续系统需要处理数据量。对于国家级别的信息监控来说，不但关键词规模有O（103）条，而且对需要处理O(G)的带宽。美国FBI的Carnivore【9】就是这样能分析Email内容的工具。为了监测电子邮件、扫描邮件病毒，防范公司机密信息泄漏和拒绝垃圾邮件，安全系统需要具备内容分析的功能。过滤电子邮件，不仅仅需要通过发送者地址、收件人地址、域名以及IP地址过滤，还需要过邮件文本内容和附件内容中进行过滤。一般邮件内容以MIME（Multipurpose Internet Mail Extensions：多用途Internet邮件扩展）格式传输的【10】。在MIME规范中，内容传输编码域（Content-Transfer-Encoding field）可以被指定为不同类型的编码格式，每种编码格式实质都是一种可逆映射（mapping），从而保证数据原始表示与使用7位邮件传输协议（SMTP,POP3）【10】系统能过正常交换信息。由于当邮件原始内容被内容传输编码格式（如Base64）编码后，普通关键词匹配的分析系统就不能工作了。 分析邮件内容需要单独的关键词编码的理由主要有两点：第一个原因是，由于Base64编码是前后相关的，所以直接扫描Base64文本中编码后的关键词，会产生错误。Base64的编码过程是将每组24 bit的输入表示成一组32-bit的输出。换言之，字符的编码值是与它前面的两个字符相关。因此，同一个原始关键词在不同位置会产生不同编码。第二个原因是，由于电子邮件数据是网络数据中的重要部分，设计一个针对性的关键词匹配算法将利用编码的特性，提高检索系统的性能。原始文本经Base64编码后，成为base64字符集中的一个单个字符，占32 位。由于现在计算机中， CPU在同样的指令执行时间内，既能处理8位的字符型数据，也能处理32位的长整型数据。因此，关键词匹配算法能够利用这个有利条件来提高算法的性能。我们提出了一种高效的分析电子邮件内容的多关键词匹配算法，下文中将简称这种算法为EMailMatch。EMailMatch算法是对Wu-Manber【4】，Commentz-Walter【5】和Jang-Jong Fan【6】等人的算法改进后得到的，在压缩文本的直接匹配中，这些算法已经被广泛应用。我们使用P=p1,p2pr表示一组关键词，这些关键词都是一个固定字符集中的字符串，|pi|=m表示pi的长度；我们使用T=t1,t2tn 表示一段长文本，它们也由中的字符组成。S = S1,S2Sl 表示T编码后的文本。多关键词匹配问题是，只使用P和S，在S中找出所有P关键词出现的位置。解决这个问题的原始算法是，首先将字符串S解码，再进行普通的关键词匹配操作。最坏情况下，所需的时间将超过O(l)+O(n)，平均为O(l)+O(n/m) 。如果关键词编码后的字符串不变的时候，我们可以直接把关键词编码，再使用这些编码进行普通关键词匹配就可以了。例如UTF-8和Quoted-Printable等编码方式。我们只需要对关键词进行编码，再使用编码后的字符串直接对S进行检索就可以了。但是对Base64和UTF-7等编码方式，由于关键词编码后得到的字符串并不固定，上述算法就无效了。由于UTF-7和Base64编码方式的处理方法基本相同，本文只描述针对Base64文本的算法，原理同样可以使用在UTF-7中。目前可以用两种不同的方法来搜索编码后的文本。第一种方法非常实用，是一种专门针对单词，基于Huffman编码的高效解决方案【11】。但这种方法只能检索整个单词和整个句子。第二种方法针对压缩后的文本（我们压缩也当作一种编码）【2】，目前有很多在压缩后的文本中直接进行关键词匹配的工作。但是由于Base64编码后的数据一般比原始数据要大33，因此直接进行Base64编码的关键词匹配算法不同一般的文本压缩中的关键词匹配算法。对多字符串关键词匹配的许多研究可以参见文献【1，2，3】。著名的Commentz-Walter算法可以参见【6，7】，Wu-Manber算法【4】由于将块搜索方法和哈希算法法结合，因此在实际中使用多的算法。Nishimura 【13】是对Aho-Crosik算法的优化。国内研究的算法【14，15】是对Commentz-Walter算法的优化。EMailMatch算法是从Wu-Manber【6，7，14，15】算法改进得来的。 下面，我们简单描述一下EmailMatch算法的主要流程。在EMailMatch算法中，首先在原始关键词字符串中选择3个字符（24位），并按Base64格式将这3元字符编码成4元字符；然后，我们按编码后的4元字符串建立跳跃表；接下来，用4元字符（32位长整型）而不是字符（8位字节）扫描Base64文本。如果得到一个正位移，就可以跳过一段Base64文本。如果不能跳跃，就Base64文本中的窗口文本解码成正常文本，然后将正常文本同原始关键词字符串进行比较。如果正常文本与原始关键词匹配，则报告发现了某个关键词。 本文后续内容是这样安排的：第二部分，描述Base64内容传输编码方案；第三部分，详细介绍如何建立4元字符的跳跃表；第四部分，介绍详细介绍对文本进行搜索的算法；第五部分进行粗略的空间和时间分析；在最后的第六部分，我们将给出实验结果，得出我们的结论并对后继研究进行展望。2 Base64内容传输编码【10】 在本节中，我们介绍Base64内容传输编码。Base64内容传输编码被设计表达任意八位字节的序列。编码过程是将24位一组的位输入表示成32位一组的输出。处理从左向右进行的，一个24位的输入包括3个8位输入组。处理过程中，24位组被当作4个相互链接的6位组，每个6位组被转换成Base64字符集中一个单独的32位字符。下面的图1展示了3个24位转换成32位Base64字符的逻辑过程。需要注意到：输出流（编码后的字节）每32位为一组的。在当前计算机中，32位字符是一个无符号的长整数。我们还知道，如果原始文本的第一个字节、第二个字节或第三个字节被分在不同24位中，则编码后的值也会不同的。AAAAAAAA |BBBBBBBB | CCCCCCCC |DDDDDDD |DDDDDDDD |DDDDDDDDaaaaaabbbbbbccccccdddddd00aaaaaa00bbbbbb00cccccc00dddddd图1：Base64内容传输编码3 预处理过程Wu-Manber【4】提出的块技术(Multicharacter Block Match)是指一次对q元字符块的操作,而不是对一个字符的操作。块技术已经成功的应用于DNA检索及长关键词【2000】中。块技术的运用增大了字符集，从而在扫描时，可以跳得更远，减少了耗时地比较工作。在EMailMatch算法中，编码后的文本是32位字符，因此必须选择4元组。注意的是Base64编码文本中的32位字符，在原始文本只是24位字符。由于编码后的Base64文本能够被看作是一个长整数流，我们设计了针对性的EMailMatch算法。在预处理过程中，我们将关键词中的3个字符作为一组进行编码，转换成32位的Base64字符（一个长整数）。因为在内存中，存储32位的表中太大了，我们将这个长整数散列成一个短整数（16位）。我们采用链地址法来处理散列冲突。这一预处理过程类似于Sun-Manber【4】算法。预处理过程中将建立两个表：一个pSkip表，一个pCheck表。pSkip表用于决定将来在扫描Base64文本时，最远能跳跃的距离（这里使用长整数的距离，而 Sun-Manber算法中使用的是字符距离）。当跳跃值为0时，就使用pCheck表。pCheck表用于决定哪个关键词可能匹配，哪里的Base64文本必须被解码，以及如何验证原始文本是否和原始关键词匹配。我们将在下文中描述详细的pCheck表的细节。pSkip表中的跳跃值决定了我们在扫描Base64文本时，能够向前跳过多远。我们假定：k：表示16位的散列值；m：表示关键词的长度； ceilDiv(x,y)=(x+y-1)/y； Hash(x)= (ll 16)ll & 0xFFFF； Base64(s)：把字符串s使用Base64编码有两种情况：1：k不能从任何关键词的子串中计算出来：2：k能够从关键词的子串中计算出来：例如，对于字符串“Gutenberg”中的3个字符“ten”，编码得到“dGVu”，我们知道“dGVu”使用长整数表示是75564764。然后我们将75564764进行散列，散列后得到一个短整数12850。有上面公式，所以pSkip12850 =1；当pSkiph=0，pCheckh的值指向一个TCheckItem的数据结构。TcheckItem中包含也从编码域到原始域需要保存的全部信息。TcheckItem中有一个成员pNext，pNext指向另一个TcheckItem的数据结构或为NULL。TcheckItem的信息如下表1所示。表格1：CheckItem 信息short int pattern_index;/用于匹配的候选关键词索引Long first_code;/能从此关键词中计算出的第一个长整数short int first_check;/起始位置在此关键词中的第一个长整数short int back_distance;/ Base64文本索引将要回溯的长度short int decode_len;/Base64文本将会被解码的长度short int compare_postion;/原始文本将要从何处开始与关键词比较TCheckItem * pNext;/指向下一个需要匹配的候选关键词结构成员“first_code”和“first_check” 类似Sun-Manber算法中的PREFIX。它用于加快匹配校验的速度。由于对Base64文本中的window文本的解码比较耗时，所以在对Base64文本解码前我们使用first_code进行确认，看是否可能出现匹配。结构成员“back_distance”，“decode_len”和“compare_postion” 用于对Base64文本窗口解码并检验是否与原始文本匹配。可以参看图2的示例。first_codeBase64 文本：编码字符串：原始字符串原始文本：decode_length:4compare_postion:2back_distance:2字符串长度：8图2：TcheckItem示例4 扫描过程：这一节，我们详细描述EmailMatch算法的扫描过程。虽然扫描过程与Sun-Manber 的算法很类似，但有存在两个主要的区别。第一，我们把输入的Base64文本改为长整型数组，这样可以一次处理32位，同时快速散列。这也是我们的算法适宜32位计算机硬件的主要原因。第二，在我们校验原始文本和原始关键词是否匹配前，我们先校验Base64文本和关键词编码后的第一个长整数是否相等。只有这个长整数相等的情况下，才进一步解码。这样进一步减少了需要解码的可能性。EmailMatch的主要流程如下：1：计算出Base64文本中基于当前长整数的散列值h；2：检查pSkiph的值，如果该值0，则向后跳跃pSkiph值的距离，并回到步骤1；否则到步骤3；3：检验链接在pCheckh的每一个TCheckItem结构，如果TcheckItem结构的first_code等于Base64文本中相应位置的长整数则跳到步骤4；否则继续检验下一个TcheckItem结构。当全部链接在pCheckh的TCheckItem结构检验完成，则向后跳跃一个距离，并回到步骤1；4：将Base64文本中相应位置的文本解码成原始文本，直接将此原始关键词与原始文本进行核对；如果相等，则报告发现关键词。回到到步骤3；（所有原始关键词的信息都从TcheckItem中得到）。表2中，我们给出EmailMatch算法中检索文本流的部分C代码。全部代码和测试数据可以从下载2 2/seminar/members/tjl/EMaillMatch/index.htm。表格2： EMailMatch 检索文本算法long * plong;plong=(ITEM_TYPE *)data;/change base64 text to long arrayint itemDataLen=datalen/4;int itemLen=m/ 3 -1;for(i=itemLen ;i0)i=i+pSkipp;continue;/step 2: pci=pCheckp;while(pci!=NULL)pp=&(pPatternspci-pattern_index);/step 3:if(plongi - pci-first_check = 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+;5 EmailMatch算法的实验：为了评价算法性能，我们将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得到的。文本数据集与SumKim199912的数据集一致：文本文件取自Gutenberg项目中的King James Bible，关键词从Unix词典/usr/dict/words中选取。我们从这些单词中随机选取了一组关键词，它们的长度均为10。比较结果可参见如下图3：对文本字符串检索100次的运行时间之和。应该注意到：fgrep或agrep检索的是原始长度为4.7M的文本，但是EMailMatch检索的是6.2M的Base64文本。可以看到，即便EMailMatch检索的文本大小为fgrep或agrep的133，EmailMatch花的时间还少一些。图3：对文本字符串检索100次的运行时间之和更重要的是EMailMatch算法能够直接检索Base64文本。与Sun-Manber算法的平均时间一样。Base64算法解码所需的时间复杂度是O(n)，因此EmailMatch算法要显著快于解码再检索的方法（快m倍）。表3将我们的算法同解码再检索的方法进行了比较。我们可以看到EmailMatch算法平均能比解码再检索的方法加速595。解码再检索的方法所需的平均时间高于O(l)+O(n)，而EmailMatch方法所需的平均时间是O(n/m)。表格3：对长度为10的字符串检索100次的时间和字符串原始文本- agrep解码再agrepBase64-EMailMatch1006.546.76.32005008.348.68.08009.549.49.210009.749.810.46 结论和展望当然EMailMatch这种充分利用硬件数值运算能力的算法是有一定局限性的。首先它和AGREP、ShiftOr2等算法一样，在设计算法把机器的字长作为设计算法一个因素来考虑，存在一些不合适性。其次它需要关键词有一定的长度，影响了算法的通用性。但是EmailMatch算法将关键词编码，而不是把编码文本解码的思想，是通用了。利用这种思想，由于多关键词匹配算法基本上和关键词规模无关，这样可以把必须使用O(n)解码的算法优化为O(n/m)，可以提高信息监控系统的系统。其次，EmailMatch算法是在作者LongMatch【15】算法基础上改进的，这种考虑硬件加速和分前后两次校验的思想，也对优化其他算法有借鉴作用。在未来的工作中，我们将把这个设计思想应用到多DNA序列匹配系统和G带宽的网络信息安全系统中，希望能提高这些系统的性能。致谢：本文工作过程得到程学旗、郭莉、李栋栋、卜东波和安全组的全体同事等人的建议、帮助和支持，在此表示感谢！参考文献：1 Gonzalo Navarro and Mathieu 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 Conference (CPM01), 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 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. 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 bibliographi