針對垃圾郵件的直接多關鍵詞匹配算法

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

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

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

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

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

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

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

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

9、是字符距離）。當跳躍值為0時，就使用pCheck表。pCheck表用于決定哪個關鍵詞可能匹配，哪里的Base64文本必須被解碼，以及如何驗證原始文本是否和原始關鍵詞匹配。下面我們將描述pCheck表的細節(jié)。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”使用長整數(shù)表示是75564764；然后我們將75564764進行散列，散列后得到一個短整數(shù)12850，符合上述的第二種情況，所以得到pSkip12850 =1。當pSkipk=0時，pCheckk的值指向一個TCheckItem的數(shù)據(jù)結構。TcheckItem中包含從編碼域到原始域需要的全部信息。TcheckItem中有一個成員pNext，pNext指向另一個TcheckItem的數(shù)據(jù)結構或為NULL。TcheckItem的信息如下表1所示。short int pattern_index; /用于匹配的候選關鍵詞索引Long first_co

11、de; /能從此關鍵詞中計算出的第一個長整數(shù)short int first_check; /起始位置在此關鍵詞中的第一個長整數(shù)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對要解碼的窗口文本進行確認，看是否可能出現(xiàn)匹配。結構成員back_distance、decode_len和compare_postion用于對Base64文本窗口解碼并檢驗是否與原始文本匹配。它們的關系可以參看圖2的示例。first_codeBase64 文本：編碼字符串：原始字符串原始文本：decode_length:4compare_postion:2back_distance:2字符串長度：8圖2：TcheckItem示例4 掃描過程本算法的掃描過程雖然與Wu-Manber 的算法很類似，但有兩

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

14、的每一個TCheckItem結構，如果TcheckItem結構的first_code等于Base64文本中相應位置的長整數(shù)則跳到Step 4；否則繼續(xù)檢驗下一個TcheckItem結構。當全部鏈接在pCheckk的TCheckItem結構檢驗完成時，則向后跳躍一個距離，并回到Step 1；Step 4：將Base64文本中相應位置的文本解碼成原始文本，直接將此原始關鍵詞與原始文本進行核對：如果相等，則報告發(fā)現(xiàn)關鍵詞?；氐降讲襟E3；（所有原始關鍵詞的信息都從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算法的實驗為了評價算法性能，我們

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

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

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