《针对垃圾邮件的直接多关键词匹配算法.doc》由会员分享，可在线阅读，更多相关《针对垃圾邮件的直接多关键词匹配算法.doc（7页珍藏版）》请在金锄头文库上搜索。
1、针对垃圾邮件的直接多关键词匹配算法1 本文获863项目“网络信息动态监控及防渗透技术的研究与实现”支持，项目编号：2002AA142110。刘萍 谭建龙 沙瀛中国科学院计算技术研究所北京 2704信箱，100080 E-mail: 摘要：本文提出了一种直接扫描电子邮件内容的多关键词匹配算法。邮件文本多采用Base64编码，由于Base64编码是前后相关的，所以完成匹配需要特殊的处理。本文提出的算法在不进行Base64解码情况下，直接对邮件内容进行扫描匹配；同时针对Base64编码结果是32位整型数据流的性质，本算法以32位块进行匹配操作，从而获得了比8位块的匹配更高的效率。实验结果表明，
2、本算法比“解码再匹配”策略快，比直接检索原始文本方法也要快。关键词：垃圾邮件 直接多关键词匹配 串匹配 Base64 StringMatching1 引言 为了扫描邮件病毒、拒绝垃圾邮件，安全系统需要具备对邮件内容进行分析的功能。过滤垃圾邮件，不仅仅需要对发送者地址、收件人地址、域名以及IP地址过滤，还需要对邮件文本内容和附件内容进行过滤。由于邮件内容通常采用Base64编码，而对于编码后的内容，普通关键词匹配就不能直接工作。一种简单直接的方法就是先解码再匹配，这种方法受到对Base64解码速度的限制，使邮件内容处理的速度大大下降。因此，为了实现高效的邮件内容的分析，需要一种能直接在Base6
3、4编码文本上进行快度串匹配的方法。目前可以用两种不同的方法来搜索编码后的文本。第一种方法非常实用，是一种专门针对单词、基于Huffman编码的高效解决方案【11】，但这种方法只能检索整个单词和整个句子。第二种方法针对压缩后的文本（压缩也认为是一种编码方式）【2】，目前有很多在压缩后的文本中直接进行关键词匹配的工作。但是由于Base64编码后的数据一般比原始数据要大33，因此直接进行Base64编码的关键词匹配算法不同于一般的文本压缩中的关键词匹配算法。 分析邮件内容需要单独对关键词进行编码，理由主要有两点：一，由于Base64编码是前后相关的，它的编码过程是将每组24 bit的输入表示成一组3
4、2-bit的输出。换言之，一个字符的编码值是与它前面的两个字符相关的，这样，同一个原始关键词在不同位置就会产生不同的编码，所以直接扫描Base64文本中编码后的关键词，会产生错误。二，由于电子邮件数据是网络数据中的重要部分，设计一个有针对性的关键词匹配算法将利用编码的特性，提高检索、过滤系统的性能。原始文本经Base64编码后，成为base64字符集中的一个单个字符，占32 位。现在计算机中， CPU在同样的指令执行时间内，既能处理8位的字符型数据，也能处理32位的长整型数据。因此，关键词匹配算法能够利用这个有利条件来提高算法的性能。在Wu-Manber【4】，Commentz-Walter【
5、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位做为一个块来进行处理，这样能够比以8位为一块的算法（例如：
7、Wu_Manber算法）更快的进行跳跃，从而能够加快扫描的速度。另外，由于Base64编码是前后相关的，所以当原始文本的第一个字节、第二个字节或第三个字节被分在24位中不同的8位位置上，它们产生的编码是不同的。这样，在Base64编码的文本上直接简单的利用32位块来进行串匹配是不可以的，必须要区分3个字节在3个位置的不同情况来处理，这也是本算法核心处理的地方之一。详细处理方法参看下一节的pSkipk值的计算部分。AAAAAAAA |BBBBBBBB | CCCCCCCC |DDDDDDDD |DDDDDDDD |DDDDDDDDaaaaaabbbbbbccccccdddddd00aaaaaa0
8、0bbbbbb00cccccc00dddddd图1：Base64内容传输编码3 预处理过程在预处理过程中，我们将关键词中的3个字符作为一组进行编码，转换成32位的Base64字符（一个长整数）。因为存储32位字符的直接映射表需要4G空间，为了节约空间，我们将这个长整数散列成一个短整数（16位），同时采用链地址法来处理散列冲突。这一预处理过程类似于Wu-Manber【4】算法。预处理过程中将建立两个表：一个pSkip表，一个pCheck表。pSkip表用于决定将来在扫描Base64文本时，最远能跳跃的距离（这里使用长整数的距离，而 Wu-Manber算法中使用的是字符距离）。当跳跃值为0时，就使
9、用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个字符“ten”，编码得到“dGV
10、u”，“dGVu”使用长整数表示是75564764；然后我们将75564764进行散列，散列后得到一个短整数12850，符合上述的第二种情况，所以得到pSkip12850 =1。当pSkipk=0时，pCheckk的值指向一个TCheckItem的数据结构。TcheckItem中包含从编码域到原始域需要的全部信息。TcheckItem中有一个成员pNext，pNext指向另一个TcheckItem的数据结构或为NULL。TcheckItem的信息如下表1所示。short int pattern_index; /用于匹配的候选关键词索引Long first_code; /能从此关键词中计算出的第
11、一个长整数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，它用于加快匹配校验的速度。由于对Base64编码文本
12、的窗口文本解码比较耗时，所以我们首先使用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 的算法很类似，但有两个主要的区别：一，我们把输入的Ba
13、se64文本改为长整型数组，这样可以一次处理32位，同时加快散列的速度。这也是我们的算法适宜32位计算机硬件的主要原因。二，在我们校验原始文本和原始关键词是否匹配前，我们先校验Base64文本和关键词编码后的第一个长整数是否相等。只有在这个长整数相等的情况下，才进一步解码，这样就进一步减少了需要解码的可能性。EmailMatch的主要流程如下：Step 1：计算出Base64文本中基于当前长整数的散列值k；Step 2：检查pSkipk的值，如果该值0，则向后跳跃pSkipk的距离，并回到Step 1；否则到Step 3；Step 3：检验链接在pCheckk的每一个TCheckItem结构，
14、如果TcheckItem结构的first_code等于Base64文本中相应位置的长整数则跳到Step 4；否则继续检验下一个TcheckItem结构。当全部链接在pCheckk的TCheckItem结构检验完成时，则向后跳跃一个距离，并回到Step 1；Step 4：将Base64文本中相应位置的文本解码成原始文本，直接将此原始关键词与原始文本进行核对：如果相等，则报告发现关键词。回到到步骤3；（所有原始关键词的信息都从TcheckItem中得到）。long * plong;plong=(ITEM_TYPE *)data; /change base64 text to long arrayi
15、nt 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 orig
