針對垃圾郵件的直接多關(guān)鍵詞匹配算法

1、針對垃圾郵件的直接多關(guān)鍵詞匹配算法1 本文獲863項(xiàng)目“網(wǎng)絡(luò)信息動態(tài)監(jiān)控及防滲透技術(shù)的研究與實(shí)現(xiàn)”支持，項(xiàng)目編號：2002AA142110。劉萍 譚建龍 沙瀛中國科學(xué)院計(jì)算技術(shù)研究所北京 2704信箱，100080 E-mail: liuping tan shaying 摘要：本文提出了一種直接掃描電子郵件內(nèi)容的多關(guān)鍵詞匹配算法。郵件文本多采用Base64編碼，由于Base64編碼是前后相關(guān)的，所以完成匹配需要特殊的處理。本文提出的算法在不進(jìn)行Base64解碼情況下，直接對郵件內(nèi)容進(jìn)行掃描匹配；同時(shí)針對Base64編碼結(jié)果是32位整型數(shù)據(jù)流的性質(zhì)，本算法以32位塊進(jìn)行匹配操作，從而獲得了比8位

2、塊的匹配更高的效率。實(shí)驗(yàn)結(jié)果表明，本算法比“解碼再匹配”策略快，比直接檢索原始文本方法也要快。關(guān)鍵詞：垃圾郵件 直接多關(guān)鍵詞匹配 串匹配 Base64 StringMatching1 引言 為了掃描郵件病毒、拒絕垃圾郵件，安全系統(tǒng)需要具備對郵件內(nèi)容進(jìn)行分析的功能。過濾垃圾郵件，不僅僅需要對發(fā)送者地址、收件人地址、域名以及IP地址過濾，還需要對郵件文本內(nèi)容和附件內(nèi)容進(jìn)行過濾。由于郵件內(nèi)容通常采用Base64編碼，而對于編碼后的內(nèi)容，普通關(guān)鍵詞匹配就不能直接工作。一種簡單直接的方法就是先解碼再匹配，這種方法受到對Base64解碼速度的限制，使郵件內(nèi)容處理的速度大大下降。因此，為了實(shí)現(xiàn)高效的郵件內(nèi)容

3、的分析，需要一種能直接在Base64編碼文本上進(jìn)行快度串匹配的方法。目前可以用兩種不同的方法來搜索編碼后的文本。第一種方法非常實(shí)用，是一種專門針對單詞、基于Huffman編碼的高效解決方案【11】，但這種方法只能檢索整個(gè)單詞和整個(gè)句子。第二種方法針對壓縮后的文本（壓縮也認(rèn)為是一種編碼方式）【2】，目前有很多在壓縮后的文本中直接進(jìn)行關(guān)鍵詞匹配的工作。但是由于Base64編碼后的數(shù)據(jù)一般比原始數(shù)據(jù)要大33，因此直接進(jìn)行Base64編碼的關(guān)鍵詞匹配算法不同于一般的文本壓縮中的關(guān)鍵詞匹配算法。 分析郵件內(nèi)容需要單獨(dú)對關(guān)鍵詞進(jìn)行編碼，理由主要有兩點(diǎn)：一，由于Base64編碼是前后相關(guān)的，它的編碼過程是將

4、每組24 bit的輸入表示成一組32-bit的輸出。換言之，一個(gè)字符的編碼值是與它前面的兩個(gè)字符相關(guān)的，這樣，同一個(gè)原始關(guān)鍵詞在不同位置就會產(chǎn)生不同的編碼，所以直接掃描Base64文本中編碼后的關(guān)鍵詞，會產(chǎn)生錯(cuò)誤。二，由于電子郵件數(shù)據(jù)是網(wǎng)絡(luò)數(shù)據(jù)中的重要部分，設(shè)計(jì)一個(gè)有針對性的關(guān)鍵詞匹配算法將利用編碼的特性，提高檢索、過濾系統(tǒng)的性能。原始文本經(jīng)Base64編碼后，成為base64字符集中的一個(gè)單個(gè)字符，占32 位。現(xiàn)在計(jì)算機(jī)中， CPU在同樣的指令執(zhí)行時(shí)間內(nèi)，既能處理8位的字符型數(shù)據(jù)，也能處理32位的長整型數(shù)據(jù)。因此，關(guān)鍵詞匹配算法能夠利用這個(gè)有利條件來提高算法的性能。在Wu-Manber【4】

5、，Commentz-Walter【5】和Jang-Jong Fan【6】等算法的基礎(chǔ)上，本文提出了一種高效的分析電子郵件內(nèi)容的多關(guān)鍵詞匹配算法（簡稱為EMailMatch）。該算法首先在原始關(guān)鍵詞字符串中選擇3個(gè)字符（24位），并按Base64格式將這3元字符編碼成4元字符；然后，我們按編碼后的4元字符串建立跳躍表；接下來，用4元字符（32位長整型）而不是字符（8位字節(jié)）掃描Base64文本。如果得到一個(gè)正位移，就可以跳過一段Base64文本。如果不能跳躍，就將Base64文本中的窗口文本解碼成正常文本，然后將正常文本同原始關(guān)鍵詞字符串進(jìn)行比較。如果正常文本與原始關(guān)鍵詞匹配，則報(bào)告發(fā)現(xiàn)了某個(gè)關(guān)

6、鍵詞。實(shí)驗(yàn)結(jié)果表明，本算法比“解碼再匹配”策略快，比直接檢索原始文本方法也要快。2 Base64內(nèi)容傳輸編碼【10】 Base64內(nèi)容傳輸編碼用來表達(dá)任意八位字節(jié)的序列。編碼過程是將24位一組的位輸入表示成32位一組的輸出。處理從左向右進(jìn)行的，一個(gè)24位的輸入包括3個(gè)8位輸入組。處理過程中，24位組被當(dāng)作4個(gè)相互鏈接的6位組，每個(gè)6位組被轉(zhuǎn)換成Base64字符集中一個(gè)單獨(dú)的8位字符。下面的圖1展示了1個(gè)24位轉(zhuǎn)換成32位Base64編碼的邏輯過程。由于Base64編碼的輸出流是以32位為一組的，而在當(dāng)前計(jì)算機(jī)中，32位是一個(gè)無符號的長整數(shù)，所以算法利用這個(gè)特性，將32位做為一個(gè)塊來進(jìn)行處理，這

7、樣能夠比以8位為一塊的算法（例如：Wu_Manber算法）更快的進(jìn)行跳躍，從而能夠加快掃描的速度。另外，由于Base64編碼是前后相關(guān)的，所以當(dāng)原始文本的第一個(gè)字節(jié)、第二個(gè)字節(jié)或第三個(gè)字節(jié)被分在24位中不同的8位位置上，它們產(chǎn)生的編碼是不同的。這樣，在Base64編碼的文本上直接簡單的利用32位塊來進(jìn)行串匹配是不可以的，必須要區(qū)分3個(gè)字節(jié)在3個(gè)位置的不同情況來處理，這也是本算法核心處理的地方之一。詳細(xì)處理方法參看下一節(jié)的pSkipk值的計(jì)算部分。AAAAAAAA |BBBBBBBB | CCCCCCCC |DDDDDDDD |DDDDDDDD |DDDDDDDDaaaaaabbbbbbcccc

8、ccdddddd00aaaaaa00bbbbbb00cccccc00dddddd圖1：Base64內(nèi)容傳輸編碼3 預(yù)處理過程在預(yù)處理過程中，我們將關(guān)鍵詞中的3個(gè)字符作為一組進(jìn)行編碼，轉(zhuǎn)換成32位的Base64字符（一個(gè)長整數(shù)）。因?yàn)榇鎯?2位字符的直接映射表需要4G空間，為了節(jié)約空間，我們將這個(gè)長整數(shù)散列成一個(gè)短整數(shù)（16位），同時(shí)采用鏈地址法來處理散列沖突。這一預(yù)處理過程類似于Wu-Manber【4】算法。預(yù)處理過程中將建立兩個(gè)表：一個(gè)pSkip表，一個(gè)pCheck表。pSkip表用于決定將來在掃描Base64文本時(shí)，最遠(yuǎn)能跳躍的距離（這里使用長整數(shù)的距離，而 Wu-Manber算法中使用的

9、是字符距離）。當(dāng)跳躍值為0時(shí)，就使用pCheck表。pCheck表用于決定哪個(gè)關(guān)鍵詞可能匹配，哪里的Base64文本必須被解碼，以及如何驗(yàn)證原始文本是否和原始關(guān)鍵詞匹配。下面我們將描述pCheck表的細(xì)節(jié)。pSkip表中的跳躍值決定了在掃描Base64文本時(shí)，能夠向前跳過多遠(yuǎn)。我們使用k表示16位的散列值；m表示關(guān)鍵詞的長度；ceilDiv(x,y)表示(x+y-1)/y；Base64(s)表示把字符串s使用Base64編碼后的串。對于pSkipk的計(jì)算，有兩種情況：1：k不能從任何關(guān)鍵詞的子串中計(jì)算出來，則：2：k能夠從關(guān)鍵詞的子串中計(jì)算出來，則：例如，對于字符串“Gutenberg”中的3

10、個(gè)字符“ten”，編碼得到“dGVu”，“dGVu”使用長整數(shù)表示是75564764；然后我們將75564764進(jìn)行散列，散列后得到一個(gè)短整數(shù)12850，符合上述的第二種情況，所以得到pSkip12850 =1。當(dāng)pSkipk=0時(shí)，pCheckk的值指向一個(gè)TCheckItem的數(shù)據(jù)結(jié)構(gòu)。TcheckItem中包含從編碼域到原始域需要的全部信息。TcheckItem中有一個(gè)成員pNext，pNext指向另一個(gè)TcheckItem的數(shù)據(jù)結(jié)構(gòu)或?yàn)镹ULL。TcheckItem的信息如下表1所示。short int pattern_index; /用于匹配的候選關(guān)鍵詞索引Long first_co

11、de; /能從此關(guān)鍵詞中計(jì)算出的第一個(gè)長整數(shù)short int first_check; /起始位置在此關(guān)鍵詞中的第一個(gè)長整數(shù)short int back_distance; / Base64文本索引將要回溯的長度short int decode_len; /Base64文本將會被解碼的長度short int compare_postion; /原始文本將要從何處開始與關(guān)鍵詞比較TCheckItem * pNext; /指向下一個(gè)需要匹配的候選關(guān)鍵詞表1：CheckItem 信息結(jié)構(gòu)成員first_code和first_check 類似Wu-Manber算法中的Prefix，它用于加快匹配校驗(yàn)

12、的速度。由于對Base64編碼文本的窗口文本解碼比較耗時(shí)，所以我們首先使用first_code對要解碼的窗口文本進(jìn)行確認(rèn)，看是否可能出現(xiàn)匹配。結(jié)構(gòu)成員back_distance、decode_len和compare_postion用于對Base64文本窗口解碼并檢驗(yàn)是否與原始文本匹配。它們的關(guān)系可以參看圖2的示例。first_codeBase64 文本：編碼字符串：原始字符串原始文本：decode_length:4compare_postion:2back_distance:2字符串長度：8圖2：TcheckItem示例4 掃描過程本算法的掃描過程雖然與Wu-Manber 的算法很類似，但有兩

13、個(gè)主要的區(qū)別：一，我們把輸入的Base64文本改為長整型數(shù)組，這樣可以一次處理32位，同時(shí)加快散列的速度。這也是我們的算法適宜32位計(jì)算機(jī)硬件的主要原因。二，在我們校驗(yàn)原始文本和原始關(guān)鍵詞是否匹配前，我們先校驗(yàn)Base64文本和關(guān)鍵詞編碼后的第一個(gè)長整數(shù)是否相等。只有在這個(gè)長整數(shù)相等的情況下，才進(jìn)一步解碼，這樣就進(jìn)一步減少了需要解碼的可能性。EmailMatch的主要流程如下：Step 1：計(jì)算出Base64文本中基于當(dāng)前長整數(shù)的散列值k；Step 2：檢查pSkipk的值，如果該值0，則向后跳躍pSkipk的距離，并回到Step 1；否則到Step 3；Step 3：檢驗(yàn)鏈接在pCheckk

14、的每一個(gè)TCheckItem結(jié)構(gòu)，如果TcheckItem結(jié)構(gòu)的first_code等于Base64文本中相應(yīng)位置的長整數(shù)則跳到Step 4；否則繼續(xù)檢驗(yàn)下一個(gè)TcheckItem結(jié)構(gòu)。當(dāng)全部鏈接在pCheckk的TCheckItem結(jié)構(gòu)檢驗(yàn)完成時(shí)，則向后跳躍一個(gè)距離，并回到Step 1；Step 4：將Base64文本中相應(yīng)位置的文本解碼成原始文本，直接將此原始關(guān)鍵詞與原始文本進(jìn)行核對：如果相等，則報(bào)告發(fā)現(xiàn)關(guān)鍵詞。回到到步驟3；（所有原始關(guān)鍵詞的信息都從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代碼。全部代碼和測試數(shù)據(jù)可以從2 下載。5 EmailMatch算法的實(shí)驗(yàn)為了評價(jià)算法性能，我們

17、將EMailMatch同agrep，fgrep進(jìn)行了比較。我們使用0xffff 大小的pSkip表和pCheck表，一臺1.6GHz Pentium IV CPU，128M內(nèi)存的工作站。測試結(jié)果的所有時(shí)間都是用Linux的time命令得到的用戶時(shí)間。在實(shí)際運(yùn)行中，因?yàn)殛P(guān)鍵詞匹配算法的速度很快，很難準(zhǔn)確測量出一次的執(zhí)行時(shí)間，因此測試時(shí)間是運(yùn)行100次的時(shí)間總和。所有算法，包括EmailMatch，fgrep和agrep都使用相同編譯選項(xiàng)“O2”。fgrep的版本是2.5.1，agrep的是從glimpse-4.15.tar.gz得到的。文本數(shù)據(jù)集與SumKim1999【12】的數(shù)據(jù)集一致：文本文

18、件取自Gutenberg項(xiàng)目中的King James Bible，關(guān)鍵詞從Unix詞典/usr/dict/words中選取。我們從這些單詞中隨機(jī)選取了一組關(guān)鍵詞，它們的長度均為10。比較結(jié)果見圖3。應(yīng)該注意到：fgrep或agrep檢索的是原始長度為4.7M的文本，但是EMailMatch檢索的是6.2M的Base64文本。從圖中可以看到，雖然EmailMatch掃描匹配的文本大小為fgrep或agrep掃描的133，但是它所用的時(shí)間卻比它們都少。圖3：對文本字符串檢索100次的運(yùn)行時(shí)間之和更重要的是EMailMatch算法能夠直接檢索Base64文本。與Wu-Manber算法的平均時(shí)間一樣，

19、Base64算法解碼所需的時(shí)間復(fù)雜度是O(n)，因此EmailMatch算法比解碼再匹配的方法快m倍。表3將我們的算法同解碼再檢索的方法進(jìn)行了比較，從中可以看到：EmailMatch算法平均能比解碼再匹配的方法加速595。解碼再匹配的方法所需的平均時(shí)間高于O(l)+O(n)，而EmailMatch方法所需的平均時(shí)間是O(n/m)。字符串原始文本- agrep解碼再agrepBase64-EMailMatch1006.546.76.32005008.348.68.08009.549.49.210009.749.810.4表3：對長度為10的字符串檢索100次的時(shí)間和 6結(jié)論和

20、展望本文提出的EmailMatch算法針對Base64編碼結(jié)果是32位整型數(shù)據(jù)流的性質(zhì)，充分利用了計(jì)算機(jī)硬件數(shù)值運(yùn)算的能力，以32位塊代替8位塊進(jìn)行匹配操作，獲得更高的匹配效率。但是該算法也有一定的局限性：首先它和Agrep、ShiftOr【2】等算法一樣，在設(shè)計(jì)算法時(shí)把機(jī)器的字長作為一個(gè)因素來考慮，使得算法在某些情況下不適合使用；其次它需要關(guān)鍵詞有一定的長度，本算法要求大于6個(gè)字符，對于長度大于2個(gè)字符的關(guān)鍵詞，算法也可以使用同樣的思想進(jìn)行設(shè)計(jì)。EmailMatch算法的將關(guān)鍵詞編碼而不是把編碼文本解碼的思想是通用的，可以使用在UT7、UT8、BIG5等編碼文本的字符串匹配中。由于多關(guān)鍵詞匹

21、配算法基本是亞線性的算法，使用這種將關(guān)鍵詞編碼再直接匹配的方法，就可以把必須使用O(n)時(shí)間的解碼算法優(yōu)化為O(n/m)時(shí)間的匹配算法，從而提高整個(gè)系統(tǒng)的性能。另外，EmailMatch算法是在LongMatch【15】算法基礎(chǔ)上改進(jìn)的，這種考慮硬件加速和分前后兩次校驗(yàn)的思想，對優(yōu)化其他算法也有借鑒作用。在未來的工作中，我們將把這個(gè)設(shè)計(jì)思想應(yīng)用到多DNA序列匹配系統(tǒng)和G帶寬的網(wǎng)絡(luò)信息安全系統(tǒng)中，希望能提高這些系統(tǒng)的性能。致謝：本文工作過程得到程學(xué)旗、郭莉、李棟棟、卜東波和安全組的全體同事等人的建議、幫助和支持，在此表示感謝！參考文獻(xiàn)：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 王永成沈州許一震,改進(jìn)的多模式匹配算法,計(jì)算機(jī)研究與發(fā)展2002 Vol.39 No.115 譚建龍 白碩 郭莉 宋新波, 一種新的多關(guān)鍵詞匹配算法Long-Karp-Rabin