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

针对垃圾邮件的直接多关键词匹配算法1 刘萍 谭建龙 沙瀛 中国科学院计算技术研究所 北京 2704信箱，100080 E-mail: liuping@ tan@ shaying@ 摘要：本文提出了一种直接扫描电子邮件内容的多关键词匹配算法。邮件文本多采用Base64编码，由于Base64编码是前后相关的，所以完成匹配需要特殊的处理。本文提出的算法在不进行Base64解码情况下，直接对邮件内容进行扫描匹配；同时针对Base64编码结果是32位整型数据流的性质，本算法以32位块进行匹配操作，从而获得了比8位块的匹配更高的效率。实验结果表明，本算法比“解码－再匹配”策略快，比直接检索原始文本方法也要快。 关键词：垃圾邮件 直接多关键词匹配 串匹配 Base64 StringMatching 1 引言 为了扫描邮件病毒、拒绝垃圾邮件，安全系统需要具备对邮件内容进行分析的功能。过滤垃圾邮件，不仅仅需要对发送者地址、收件人地址、域名以及IP地址过滤，还需要对邮件文本内容和附件内容进行过滤。由于邮件内容通常采用Base64编码，而对于编码后的内容，普通关键词匹配就不能直接工作。一种简单直接的方法就是先解码再匹配，这种方法受到对Base64解码速度的限制，使邮件内容处理的速度大大下降。因此，为了实现高效的邮件内容的分析，需要一种能直接在Base64编码文本上进行快度串匹配的方法。 目前可以用两种不同的方法来有哪些信誉好的足球投注网站编码后的文本。第一种方法非常实用，是一种专门针对单词、基于Huffman编码的高效解决方案【11】，但这种方法只能检索整个单词和整个句子。第二种方法针对压缩后的文本（压缩也认为是一种编码方式）【2】，目前有很多在压缩后的文本中直接进行关键词匹配的工作。但是由于Base64编码后的数据一般比原始数据要大33％，因此直接进行Base64编码的关键词匹配算法不同于一般的文本压缩中的关键词匹配算法。 分析邮件内容需要单独对关键词进行编码，理由主要有两点：一，由于Base64编码是前后相关的，它的编码过程是将每组24 bit的输入表示成一组32-bit的输出。换言之，一个字符的编码值是与它前面的两个字符相关的，这样，同一个原始关键词在不同位置就会产生不同的编码，所以直接扫描Base64文本中编码后的关键词，会产生错误。二，由于电子邮件数据是网络数据中的重要部分，设计一个有针对性的关键词匹配算法将利用编码的特性，提高检索、过滤系统的性能。原始文本经Base64编码后，成为base64字符集中的一个单个字符，占32 位。现在计算机中， CPU在同样的指令执行时间内，既能处理8位的字符型数据，也能处理32位的长整型数据。因此，关键词匹配算法能够利用这个有利条件来提高算法的性能。 在Wu-Manber【4】，Commentz-Walter【5】和Jang-Jong Fan【6】等算法的基础上，本文提出了一种高效的分析电子邮件内容的多关键词匹配算法（简称为EMailMatch）。该算法首先在原始关键词字符串中选择3个字符（24位），并按Base64格式将这3元字符编码成4元字符；然后，我们按编码后的4元字符串建立跳跃表；接下来，用4元字符（32位长整型）而不是字符（8位字节）扫描Base64文本。如果得到一个正位移，就可以跳过一段Base64文本。如果不能跳跃，就将Base64文本中的窗口文本解码成正常文本，然后将正常文本同原始关键词字符串进行比较。如果正常文本与原始关键词匹配，则报告发现了某个关键词。 实验结果表明，本算法比“解码－再匹配”策略快，比直接检索原始文本方法也要快。 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位为一块的算法（例如：Wu_Manber算法）更快的进行跳跃，从而能够加快扫描的速度。 另外，由于Base64编码是前后相关的，所以当原始文本的第一个字节、第二个字节或第三个字节被分在24位中不同的8位位置上，它们产生的编码是不同的。这样，在Base64编码的文本上直接简单的利用32位块来进行串匹配是不可以的，必须要区分3个字节在3个位置的不同情况来处理，这也是本算法核心处理的地方之一。详细