一種新型的基于ＵＲＬ過濾的反垃圾郵件技術
2008-01-01 00:00:00吳峻李洋
計算機應用研究 2008年5期
摘要：在深入分析了傳統垃圾郵件過濾技術不足的基礎上，提出并實現了一種新型的基于URL過濾的垃圾郵件過濾技術（URL based spam filtering，UBSF）。該方法通過對比從到來郵件中提取的URL與URL庫中存儲的URL信息的相似性來判定垃圾郵件。通過語料庫以及構建實際系統原型的測試，表明該方法具有準確性高、誤報率低以及實時處理速度快的優點。
關鍵詞：網絡安全；垃圾郵件過濾；URL過濾的垃圾郵件過濾技術；統一資源定位符庫
中圖分類號：TP393．08文獻標志碼：A
文章編號：1001-3695(2008)05-1537-03
隨著Internet的發展，電子郵件在給人們帶來巨大便利的同時，也誘使有些人將之作為大量散發自己信息的工具，最終導致了互聯網中垃圾郵件的泛濫。垃圾郵件消耗了大量的網絡資源，并給人們帶來了極大的不便。人們平均每天需要花費5~10 min清理郵箱中的垃圾郵件。據統計，目前互聯網上的垃圾郵件總數量已經達到25%以上。在中國和美國，這種情況更加糟糕，超過50%的郵件都是垃圾郵件。更為嚴重的是，有的垃圾郵件帶有惡意代碼，這些都直接威脅到了用戶系統的安全。如何有效地防范垃圾郵件，已經成為網絡信息安全領域的一個經典難題。
伴隨著垃圾郵件的迅速增加，人們為對付垃圾郵件而進行的技術研究也迅速發展起來。人們與垃圾郵件的對抗已經持續了十多年。到目前為止，至少有8～10種以上基本的郵件過濾技術，它們被單獨或組合起來共同抵抗垃圾郵件的襲擊。然而，當前的垃圾郵件技術存在著誤報率高、處理開銷大、無法應對大規模網絡環境下的實時處理應用的需求等缺陷。
本文描述了在反垃圾郵件方面的相關研究工作，設計并實現了基于URL過濾的反垃圾郵件技術，并給出了基于該技術的實驗結果及分析。
1相關工作
目前，反垃圾郵件技術大致可以分成如下幾類：接入控制方法，包括黑名單、白名單、灰名單以及延遲技術；身份驗證方法，包括DNS MX查詢、反向DNS解析[1]；內容過濾技術，包括基于規則的RIPPER方法[2]、基于統計的貝葉斯方法[3]、ME（最大熵）模型[4]、SVM（支持向量機）方法[1]等，以及2005年最新出現的基于URL精確匹配過濾[5]和基于URL聚類的過濾方法[6]。
事實證明，復合使用多種技術在實踐中可能會取得比較好的效果。在上述抑制垃圾郵件的各種方法中，基于內容的過濾逐漸顯示出了其技術優勢。尤其是基于機器學習的方法，不但準確率高，而且可以自動地學習區別合法郵件和垃圾郵件的特征，省去了大量人力，并且可以隨著郵件的增加而不斷進化，過濾的郵件越多分類就越準確。
總而言之，傳統的反垃圾郵件技術雖然試圖從各個層面上解決這個問題，但是仍舊存在如下幾個方面的缺陷： a）誤報率（1 positive）高[6]。無論是基于黑白名單的實時過濾技術，還是對郵件內容進行深層次文本挖掘的機器學習技術，均存在較高的誤報率。
b)沒有針對特定用戶的傾向來區分垃圾郵件。這是傳統的垃圾郵件技術及其系統的一個通病。所有的垃圾郵件過濾都是針對整個用戶群而言的，并沒有考慮到用戶個人的喜好以及判別標準的特殊性及其隨時間的變更，這是導致垃圾郵件誤報率過高的重要原因之一。
c)處理的數據量過大，實時性能不高。由于采用黑白名單等實時過濾技術的效果普遍沒有基于內容的過濾技術好，所以基于郵件內容的過濾技術仍是目前應用的主流。而基于內容的過濾技術需要采用比較耗時的諸如Nave Bayes、SVM、N－gram等機器學習算法，它們需要對整個郵件體的內容進行學習。這樣，一方面處理的數據量大[7];另一方面很難滿足實時的應用場景。
針對上文所述的一些傳統反垃圾郵件技術的缺陷和不足，本文的工作主要是研究如何在大規模網絡環境下，實現輕量級的垃圾郵件過濾技術，以保證其實時性，并且能夠有效地減少誤報率，能夠針對用戶的傾向來區分垃圾郵件。因此，筆者借鑒了國際上先進的垃圾郵件過濾技術，并從大規模網絡環境下的實際應用需求出發，提出了一種新型的基于URL過濾的反垃圾郵件技術（URL based spam filtering，UBSF）。
2基于URL的垃圾郵件過濾技術
據分析統計，目前互聯網上出現的垃圾郵件85%以上是廣告垃圾郵件，而剩余的15%的垃圾郵件則是色情、政治等方面的。同時，由于垃圾郵件的發送是由其最終的經濟利益和一定的目的驅動的，通過這種廉價的垃圾郵件發送方式，達到宣傳其產品、宣揚某些非法政治言論等目的。本文通過對國內外一些常用的郵件語料庫（包括Spam Assassin、PU系列、Ling－Spam等）以及從骨干網上采集來的郵件數據進行歸類和分析，發現在垃圾郵件中，99%以上的均提供了與其宣傳信息緊密相關的URL鏈接，以給用戶訪問。當然，這其中也有少部分的例外，主要是一些病毒郵件，其主要通過帶有病毒的附件來侵害用戶的計算機，這不在本文的討論之列。
通過分析和驗證，筆者認為，URL（uniform resource locator，統一資源定位符）是當前垃圾郵件中最為穩定出現和起著重要作用的因素，99%以上的垃圾郵件都需要通過其達到宣傳和吸引用戶點擊的目的。從而，本文確定了基于URL的垃圾郵件過濾策略，即抓住垃圾郵件中的首要因素URL，通過對郵件中抽取的URL鏈接進行識別和辨認，便能夠有效地判定垃圾郵件。
本文所提出的UBSF方法旨在降低處理數據量、增強實時處理能力的基礎上，提高垃圾郵件過濾的正確率，并降低誤報率。它主要包括構造過濾垃圾郵件的URL庫、基于URL的垃圾郵件判定以及建立面向用戶的URL子庫三個方面的核心內容，下面分別對它們進行詳細介紹。
2．1構造過濾垃圾郵件的URL庫
從垃圾郵件的樣本中提取URL以形成URL庫是進行URL過濾的首要前提工作。具體的方法是選擇用戶已確認的各個垃圾郵件樣本中不同的URL鏈接存儲入庫，按照一定的策略（如URL的字母序、URL的域屬性等）形成基于URL垃圾郵件過濾所需要的URL庫。這樣的存儲方式既方便新來URL的插入，也方便后續階段URL的LCS（longest common subsequence）匹配過程。
在URL庫不斷更新的過程中，待加入的垃圾郵件中的URL需要首先與URL庫中現存的URL進行LCS匹配，如果匹配后的結果大于一個預定義的閾值上界Ta，則認為該URL與庫中的某個URL存在極大相似性。因而，根據后面章節所要討論的匹配算法，在判別時使用其中一個URL即可，則該URL為冗余鏈接，無須添加入庫；否則，即表明待加入的URL鏈接與庫中所存在的URL鏈接不重復，則應該入庫。通過這樣的處理方式，有效地減少了URL庫的規模，既節省了存儲空間，也為判別工作節省了較多的匹配時間。
通過上述算法形成的URL庫的規模，相對于文獻[5]中采用的方法形成的庫規模要小得多，因為UBSF方法只是保留了垃圾郵件中出現的URL鏈接（無須保留正常郵件中的任何URL鏈接），并且對于能夠采用LCS方法判定相似的URL鏈接則僅保留了其中的一種。舉個例子，對于www.advertize.com/book/list1以及www.advertize.com/book/reading這兩個從垃圾郵件中提取的URL鏈接，雖然兩者不一樣，但是兩者非常相似，通過LCS的判定可以確認它們的最大公共子串為www.advertize.com/book/。而且，通過筆者的分析發現，它們在垃圾郵件判定中起到的效果一樣，本文所述的方法通過這兩個URL中的任意一個便可以確認垃圾郵件。所以，本文的UBSF方法只保留其中的一個。這從實踐中來說顯然是合理的，也是高效的，可以具有很好的識別性，可檢測出那些經常通過變換URL非關鍵部分來躲避精確檢查的垃圾郵件。
2．2基于URL的垃圾郵件判定
建立了基準的URL庫之后，需要采用該庫來判別新來的郵件是否為垃圾郵件。為了解決上面所述的Greenview Data公司URL過濾方法的漏報率過高問題，本文采用經典的LCS字符串匹配方法對URL進行匹配。
最長公共子序列（LCS）問題的物理意義是：給定兩個序列X=〈x1，x2，…，xm〉和Y=〈y1， y2， … ， yn〉，要求找出X和Y的一個最長公共子序列。結合該算法，在本文所述的URL匹配中，筆者給出了如下的定義：如果對于給定的兩個URL序列Ua及Ub，能夠找到它們最長的公共子序列且其長度大于一個特定的閾值Ta，則認為Ua等價于Ub，也即代表它們所在的郵件性質相同，同為垃圾郵件或者同為正常郵件。否則，認為Ua并不等價于Ub，即兩個郵件的性質不同。
匹配過程分為如下兩個階段：
a)根據需要判定的郵件中URL的屬性（與上節所述存儲方式所對應的字母順序或者是域屬性）來在URL庫中查找與之最為接近的URL區間范圍（如將http://www.adversie.com/shoping的查找范圍限定在.com域內），這樣可以大大地限定匹配區間以及計算量；
b)采用LCS算法，對需判定郵件的URL與第一階段得到的URL區間中的URL進行匹配，若其與區間中任一URL的匹配值長度大于某個設定的閾值Ta，則判定該郵件為垃圾郵件，否則為正常郵件。該匹配算法描述如下：
輸入:待判定郵件的URL信息Uinput
輸出:判定結果類別（S：垃圾郵件；H：正常郵件）
(1)根據URL的字母順序或者是域屬性等信息確定判定區間D。
（2）取出D中的一條Ui，與Uinput進行LCS匹配，并將Ui從D中清除。
（3）判斷匹配結果長度Result，如果Result＞Ta，則判定該郵件為S，并轉(4)；否則，如果D不為空，則轉(2)。如果D為空，則判定該郵件為H，并轉(4)。
（4）取下一個URL，轉（1）。
2．3建立面向用戶的URL子庫
由于第2章所提到的垃圾郵件并沒有確定的標準，因用戶而異，因時間而異。對于本文所采用UBSF方法，同樣要考慮到這個問題，否則將會導致不必要的誤報和漏報。本文提出了基于用戶反饋，建立面向用戶的URL子庫的方法來解決這個問題。
該方法的主要思想是，在實際的應用中，為郵件系統的每一個用戶建立一個URL子庫，結構與2.1節所述的相同，只是其維護的是從特定用戶確認的垃圾郵件中提出的URL構成的庫。這些內容是由用戶向郵件系統提交的，他們只需要向系統提交確認的垃圾郵件，由系統自動提取其中的URL鏈接信息，并生成用戶專有的URL子庫。同時，如果用戶需要取消以前提交的URL鏈接，則用戶只需要提供待取消的URL信息，系統將為用戶自動完成。其實現機制也是輕量級的。
對于不同的用戶，系統為他們所維護生成的URL子庫的鏈接內容可能是部分重疊或完全不同的。對于部分重疊的情況，系統將需要把這些重疊的鏈接內容提取出來，形成這些用戶所確認的URL公共子庫，這是對URL存儲以及URL的匹配過程的一個優化。在URL的匹配過程中，則可以采用類似于NIDS中的Snort進行規則匹配[8]的方法進行，效率比較高。建立面向用戶的URL子庫后的匹配算法的描述如下：
輸入:待判定郵件的URL信息Uinput及郵件的目的地址ADDdest
輸出:判定結果類別（S：垃圾郵件；H：正常郵件）
(1)根據URL的字母順序或者域屬性等信息確定URL公共子庫中的判定區間Dc。
（2）從URL公共子庫中取出Dc中的一條Uc，與Uinput進行LCS匹配，并將Uc從Dc中清除。
（3）判斷匹配結果長度Result，如果Result＞Ta，則判定該郵件為S，并轉(7)；否則，如果Dc不為空，則轉(2)。如果Dc為空，則根據目的地址ADDdest選取面向用戶的URL子庫，并轉(4)。
（4）根據URL的字母順序或者域屬性等信息確定面向該用戶的URL子庫中的判定區間Ds。
（5）從該用戶URL子庫中取出Ds中的一條Us，與Uinput進行LCS匹配，并將Us從Ds中清除。
（6）判斷匹配結果長度Result，如果Result＞Ta，則判定該郵件為S，并轉(7)；否則，如果Ds不為空，則轉(5)。如果Ds為空，則判定該郵件為H，并轉(7)。
（7）取下一個URL，并轉（1）。
3實驗測試與分析
3．1實驗構建及結果
為了驗證UBSF方法的正確性和效率，本文首先采用國際上使用比較廣泛的Spam Assassin語料進行驗證。該語料共有大約6 050篇郵件，包括了大約1 900篇垃圾郵件和4 150篇合法郵件。實驗沒有對郵件內容進行任何其他處理，只是預先提取出了垃圾郵件中的URL鏈接信息形成URL庫，然后進行垃圾郵件過濾。本文將其正確率、誤報率與傳統較為高效的基于內容過濾的Nave Bayes方法、SVM方法進行了比較，結果如圖1所示（其中x軸坐標UBSF表示基于UBSF方法過濾的結果，Nave Bayes和SVM分別表示采用基于Nave Bayes（選擇貝努利事件模型，閾值取0.9）和SVM算法（郵件向量采用tf*idf權重向量模型，參數缺省）的實驗結果。
為了驗證UBSF方法在實際應用中的效果，本文在Linux（內核版本為2.4.20）下開發了一個基于本文所討論的基于UBSF方法的垃圾郵件過濾的原型系統。該系統中采用的LCS算法的實現采用動態規劃的方法，時間復雜度為O(m+n)（m和n分別為待比較的兩個URL的長度）。筆者在2005年3月10日~2005年3月17日使用用戶反饋的方法，建立了URL庫（包括公共子庫以及面向用戶的獨立子庫）。然后，從2005年3月17日~2005年10月4日部署該原型系統在筆者實驗室的郵件網關上（對外的SMTP服務器）對進出的郵件進行垃圾郵件過濾（通過反復實驗，判斷的閾值Ta選取經驗值15）。通過用戶反饋及數據分析，得出如表1所示實驗數據。
3．2結果分析
根據上述語料以及實際系統原型實驗的結果，不難看出，UBSF方法相對于傳統的垃圾郵件過濾方法具有很高的準確率和較低的誤報率，主要是因為該方法針對當前垃圾郵件最為穩定的本質特征——URL進行過濾。對于傳統的基于內容過濾的機器學習算法來說，它們需要學習整個郵件體的內容，而這些內容卻沒有URL穩定，并且垃圾郵件發送者可以通過隨機地添加正常郵件的典型內容來誘使過濾器作出錯誤的判定。而且，由于引入了用戶的反饋機制，維護了面向用戶的URL子庫，也消除了相當一部分的漏報以及誤報情況。相對于文獻[5]中的系統來說，在節省存儲空間的前提下大大地降低了漏報率。
4結束語
本文提出了一種基于URL的垃圾郵件過濾方法，其與傳統的垃圾郵件過濾方法以及國際上目前的URL過濾方法相比具有正確率高、誤報率低以及處理開銷較小的優點，能夠較好地應用于大規模網絡環境下的垃圾郵件實時判定及封堵，通過語料集以及系統原型實驗進行了驗證。但是，實驗的過程中也發現了一些問題。比如如何過濾少量的不含URL的垃圾郵件（如僅帶有附件的病毒郵件），以及如何在具體的實現過程當中，優化URL庫的存儲結構以及匹配過程，以進一步地提高該方法在大規模網絡應用環境下的實時處理能力。這都需要下一步的工作來完善和改進。
參考文獻：
［1］Barracuda Networks.An overview of spam blocking techniques[EB/OL].（2005）.http://www.symtrex.com/pdfdocs/Spam TechniquesFINAL.pdf.
[2]COHEN W W.Learning rules that classify e－mail[C]//Proc of AAAI Spring Symposium on Machine Learning in Information Access.Stanford， California:[s.n.]，1996：18-25.
[3]MEHRAN S，SUSAN D，DAVID H，et al.A Bayesian approach to filtering junk e－mail[C]//Proc of AAAI Workshop on Learning for Text Categorization.1998:55-62.
[4]HARRIS D，DONGHUI W，VLADIMIR N V.Support vector machines for spam categorization[J].IEEE Trans on Neural Networks，1999，10(5):1048－1054.
[5]SpamStopHere Corp. How URL Spam filtering beats Bayesian/Heuristics hands down [EB/OL].(2005).http://www.spamstopshere.com/download/ssh_url_filtering_white_paper.pdf.
[6]HERSHKOP S，STOLFO J.Combining e－mail models for 1 positive reduction[C]//Proc of KDD’05 of ACM.Chicago:[s.n.]，2005:98－107.
[7]MILLER E，SHEN Dan，LIU Jun－li，et al.Performance and scalability of a large－scale N－gram based information retrieval system[J].Journal of Digital Information，2000，1(5):1-25.
[8]ROESCH M.Snort－lightweight intrusion detection for networks[C]//Proc of the 13th Conf on Systems Administration.Washington DC:USENIX，1999:229-238.
[9]IETF. RFC821，Simple mail transfer protocol[S].1982.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
