總第222期計算機與數字工程V ol . 36N o . 4　　　　　　　　　　　　　　　　　　　　　　　　　　2008年第4期C om puter &D igital Engineering 　　1

總第222期計算機與數字工程V ol . 36N o . 4

2008年第4期C om puter &D igital Engineering 　　102　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

對郵件過濾技術發(fā)展現(xiàn)狀的比較與分析

張　萍　韓立娜

(武漢理工大學計算機科學與技術學院　武漢　430070)

3

摘　要　對自學習的過濾技術進行比較和分析, 包括已經商品化的方法和目前還處于理論研究階段的方法, 尤其介紹基于機器學習的過濾技術的發(fā)展現(xiàn)狀, 重點研究該領域內的一些新興過濾技術。在綜合比較了一系列的過濾技術的優(yōu)缺點之后, 分析結果表明基于規(guī)則的方法和貝葉斯方法是最有潛力的過濾技術。

關鍵詞　垃圾郵件　過濾　組合過濾器　規(guī)則　貝葉斯中圖分類號　TP 181

Co mparison A 　H an L ina

(C of com puter science and technology, W uhan U niversity of Technology, W uhan 　430070)

A b s t ra c t 　Focus on adap tive spam filters, from comm ercial i m p lem entations to ideas confined to current research papers . Especially introduce the technology based on m achine L earning, focusing on som e innovative technology in this field . A fter the com parison and analysis of the different techniques, rule -based and B ayesian filtering appear to be the greatest potential for fu 2ture spam p revention .

Ke yw o rd s 　spam , filter, ensem ble filter, rule, bayesian C la s s N um b e r 　TP 181

1　引言

近年來, 垃圾郵件在不斷發(fā)展, 構造一個簡單

的模型來過濾垃圾郵件是很困難的, 要實現(xiàn)就更加復雜。況且, 垃圾郵件制造者經常修改郵件的信息和內容來逃避檢測, 這給精確過濾造成了更大的障礙。

目前, 用來處理垃圾郵件的方法可以分為三類:法律法規(guī), 協(xié)議的改進和過濾器。對于大量的垃圾郵件, 法律的作用是微乎其微的, 甚至由于只要遵守一定的規(guī)則, 就可以大量發(fā)送廣告郵件, 法律在一定程度上促進了垃圾郵件的發(fā)展。協(xié)議的改進是通過改變發(fā)送郵件的方式來過濾郵件, 如:需要發(fā)送者的認證, 按郵件發(fā)送量的大小收取費用, 通過驗證郵件是否來自合法區(qū)域及是否帶有正確的密碼來識別合法郵件。這些協(xié)議大多提供了較完整的解決方案, 卻往往因為需要對現(xiàn)有的郵件

協(xié)議進行升級或替換, 應用部署受到限制, 很難在電子郵件用戶中推廣。

過濾器大致可以分為兩種:交互式和非交互式。交互式的過濾器通常也被稱為“challenge re 2

(C /R) 系統(tǒng), 能夠截取來自陌生的發(fā)送者sponse ”

的郵件和可疑度較高的郵件。這些信息都儲存在

接收者的郵件服務器中, 而服務器會給相應的發(fā)送者寄出一封郵件, 郵件一般很簡單, 但是需要回復的, 以確定郵件來自人類還是批量發(fā)送郵件的機器。交互式過濾器默認的規(guī)則是由于垃圾郵件制造者通常同時發(fā)送大量的信息, 因此不會回復此類郵件。而且, 如果發(fā)送者使用的地址是假的, 將無法收到此類郵件。

非交互式的過濾器在過濾郵件時不需要與人類進行交互, 但在配置特定用戶選項和糾正錯誤分類時需要人類的介入。這類系統(tǒng)相對簡單而行之有效, 因此應用很廣泛。

3

收稿日期:2007年11月4日, 修回日期:2007年12月25日

作者簡介:張萍, 女, 碩士研究生, 研究方向:文本分類。韓立娜, 女, 碩士研究生, 研究方向:演化計算

。? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

第36卷(2008) 第4期　　　　　　　　　　　　　計算機與數字工程

　　　　　　　　　　　　103

2　基于統(tǒng)計的過濾技術的分類及評價

為了對垃圾過濾性能進行評價分析, 有必要定義一些指標來評價垃圾過濾的效果。應用比較廣泛的評價指標有召回率R (R ecall ) , 準確率P (Pre 2cision ) , F 1測試值和精確率A (A ccu racy ) 。合法郵件被誤判為垃圾郵件稱為誤檢率(false posi 2tive ) , 垃圾郵件被誤判為合法郵件稱為漏檢率(false negative ) , 如圖1所示

。

郵件, 對所有的用戶使用同樣的規(guī)則進行過濾。這種方法的好處是可以集中管理和維護, 對終端用戶的要求很低, 可以在垃圾郵件到達目的地之前就將其拒絕或者丟棄?？蛻舳说倪^濾器檢查來自郵件服務器的所有郵件, 經常是客戶郵件處理程序的一部分。通常, 基于機器學習的過濾器被安裝在客戶度時性能最佳, 因為客戶能夠糾正錯誤分類和調整規(guī)則。

大多商用過濾器和開源產品都是基于軟件的過濾器, 可以被安裝在客戶端和服務器端。其中, 。A p 2

p (, 所圖[2]

。A pp liance 包含的硬件往往是

,

。誤判率(1-A ) 指誤檢率和漏檢率的總和。很明顯, 精確度為99的條件下, 1的誤檢率帶來的損失比1的漏檢率帶來的損失大得多。因此, 這兩個評價指標比單個的精確度更能反應過濾器的性能。

[1]

H idalgo 建議使用一個新的評價指標-RO C 曲線(R eceiver O perating C haracteristics C urve, 受試者工作特征曲線) 。曲線圖表表明在分類閥值參數發(fā)生改變時, 檢出率和誤檢率之間的平衡。若對應第一個過濾器的曲線完全在對應第二個過濾器的曲線的上方, 可以推斷:第一個過濾器的性能超過了第二個的性能。曲線以下的部分作為量化指標可以直觀有效地幫助優(yōu)選分類閾值和比較不同過濾器的性能優(yōu)劣。

過濾技術大致分為兩種:基于機器學習理論和基于非機器學習理論。近年來, 基于非機器學習理論的技術, 如基于規(guī)則的, 黑名單和簽名, 多與基于機器學習的技術相結合?；跈C器學習的過濾技術可以分為獨立模型和互補型?；パa型通常被設計為主過濾器的一個組件, 對主過濾器提供技術幫助(主過濾器可以是基于機器學習的也可以是基于非機器學習的) 。獨立模型旨在構造一個完整的知識庫, 獨立地對所有的郵件進行分類。這一類的過濾器可采用不同的方法, 如:構造一個統(tǒng)一的模型來進行判斷; 將收到的郵件與以前的郵件進行比較(相似度) ; 組合型使用協(xié)作方案, 將多個過濾器結合在一起(組合) 。

過濾器可以安裝在客戶端, 也可以安裝在郵件服務器端。服務器端的過濾器檢查所有接收到的

針對郵件過濾而進行了優(yōu)化的, 因此性能比運行軟件過濾器的通用機器的性能好, 而且, A pp liance 對應的操作系統(tǒng)一般都是預先加強的, 而通用過濾器所依賴的平臺, 尤其是操作系統(tǒng), 都有潛在的安全隱患。

3　過濾技術

3. 1　非機器學習過濾器3. 1. 1　基于規(guī)則的過濾技術

基于規(guī)則的過濾技術, 通常也稱為啟發(fā)式過濾技術, 是利用電子郵件半結構化的特點, 先使用人工或者自動的方法總結出正常郵件之間的共性, 或者垃圾郵件之間的共性, 據此來生成一系列的規(guī)則。當郵件到達或者發(fā)送郵件的行為產生時, 依照規(guī)則來檢查郵件的內容或者發(fā)送行為, 并根據與規(guī)則的相符程度來決定過濾器的動作行為。簡單的基于規(guī)則的過濾系統(tǒng)依據郵件與規(guī)則的匹配數量而給郵件分配一個相應的分數。如果分數高于預定的閥值, 郵件就被判為垃圾郵件。基于規(guī)則的過濾技術簡單, 快速和精確, 應用非常廣泛。

但是, 基于規(guī)則的過濾技術也有一些缺點。由于基于靜態(tài)的規(guī)則集, 系統(tǒng)不能自動調整過濾器去識別新的垃圾郵件特征, 需要管理者構造新的識別規(guī)則或者定期下載新規(guī)則集。如果垃圾郵件制造者偽造出一種能夠破解某一類規(guī)則, 那么所偽造的郵件能夠毫無障礙地通過所有采用這類規(guī)則的郵件服務器。況且, 某些開源的基于規(guī)則的過濾器, 公開發(fā)布過濾器和規(guī)則集, 允許垃圾郵件制造者來測試垃圾郵件的性能。另外, 基于規(guī)則的過濾技術能夠得到較高的精確度, 但是如果過濾器被調整為

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

104張　萍等:對郵件過濾技術發(fā)展現(xiàn)狀的比較與分析　　　　　　　　　　　　總第222

期

可以達到100的精確度, 就會產生很高的誤檢率, 這是用戶所不能接收的。

3. 1. 2　簽名

基于簽名的過濾技術基于這樣的事實, 同一內容的垃圾郵件在一段時間內會被高頻率地重復散發(fā)。基于簽名的過濾技術會為每封已被識別的垃圾郵件產生一個唯一的哈希值(簽名) 。當新郵件到達后, 過濾器將新郵件的哈希值與所有存儲的垃圾郵件的哈希值相比較, 以判斷是否是垃圾郵件。從統(tǒng)計學來講, 一封合法郵件的哈希值不可能與垃圾郵件的哈希值相同, 因此, 基于簽名的過濾技術的誤檢率非常低。但是, 能檢測出垃圾郵件的重要前提是有類似的垃圾郵件已經被識別出來了, 并且被賦予了一個唯一的哈希值。而且, 網絡崩潰了, 圾郵件。

然而, 匹配過濾器的檢測。例如, 在垃圾郵件里插入一段隨機的字符, 郵件的哈希值就會改變, 而且需要及時更新哈希值。

商用簽名過濾器通常融合到對應組織的郵件服務器中, 并與專門的集中簽名分配服務器進行通訊, 以及時接收和提交垃圾郵件簽名。無論分布式和合作式的簽名過濾器, 都需要復雜的可以信賴的網關, 在允許接收來自用戶的垃圾郵件簽名的同時, 阻止來自網絡的攻擊和惡意的破壞。3. 1. 3　黑白名單

3. 2. 1　統(tǒng)一模型過濾器

基于貝葉斯方法的過濾器能夠克服基于規(guī)則

的過濾器的許多缺點, 因此應用非常廣泛。目前, 許多企業(yè)級的過濾器都是采用基于貝葉斯方法的過濾技術。

貝葉斯分類的原理是大多數事件都是相互依賴的, 那么一個事件將來發(fā)生的概率可以從該事件從前發(fā)生的概率進行推斷。應用同樣的原理可以對郵件進行分類, 分類器的工作一般分為訓練和分類兩個階段:在訓練階段, 分類器通過對大量郵件(包括垃圾郵件和正常郵件) , 統(tǒng)計。在分類階段, , 貝葉斯過濾技術。但是, 多數商用貝葉斯過濾器都是依靠自己的人工評分系統(tǒng), 而不是完全依賴于產生的原始概率。而且, 通常使用樸素貝葉斯方法(假設事件是互相獨立的) 。

為了解決標準貝葉斯方法的不足, Yerazu 2[3]-[4]nis 介紹了零散二元多項式拆分(Sparse bina 2ry po lynom ial hashing, SB PH ) 和正交稀疏偶圖

(O rthogonal sparse b igram , O SB ) 。SB PH 是樸素

貝葉斯方法的泛化, 將貝葉斯鏈式規(guī)則和單個特征的條件概率相結合, 不僅能識別單個的詞, 還能識別變異的短語。Yerazun is 在沒有使用白名單和黑名單的情況下, 對實時郵件郵件進行過濾, 得到了99. 9以上的試驗結果。但是, SB PH 的公認的缺

黑白名單技術利用的是最樸素的思想:列舉受歡迎的和不受歡迎的發(fā)件人名單。白名單中的發(fā)件人發(fā)送的任何郵件都認為是合法郵件, 黑名單中的發(fā)件人發(fā)送的任何郵件都認為是垃圾郵件。這是目前電子郵件過濾中廣泛使用的技術, 可以應用在服務器端或客戶端。在和其它過濾器結合時, 不需要對其他過濾器作大量的修改, 就能彌補其它過濾器的不足。通常做法是收集一個黑、白名單列表, 可以是電子郵件地址, 也可以是郵件服務器的域名、IP 地址, 收到郵件時對發(fā)件人進行實時檢查。這種名單一般由比較有信譽的組織提供, 如中國互聯(lián)網協(xié)會定期在主頁上公開垃圾郵件服務器IP 地址名單。個人也可以根據需求定義和維護自己的黑、白名單。黑白名單技術具有使用簡單可靠, 漏檢率較低的優(yōu)點。但是其簡單性導致偽造的發(fā)送地址很容易逃過檢測。而且, 誤檢率較高使其作為單一的過濾系統(tǒng)時性能不好。3. 2　基于機器學習的過濾器

點是計算時間太長。而O SB 利用的特征集遠小于

SB PH, 因此, 相對而言, O SB 需要的內存小, 速度快?；贠 SB 和W innow 算法的過濾器, 精確度最高可以達到99. 68, 比SB PH 小0. 04, 但是,

O SB 只用了600, 000個特征變量, 而SB PH 需要

1, 600, 000個特征變量。樸素貝葉斯方法是假設

特征之間都是不相關的, 現(xiàn)在有不少學者對特征詞的相關性進行研究, 例如:若同一個特征詞出現(xiàn)在郵件中的不同區(qū)域, 就將其看作不同的特征, 構造聯(lián)合權值(co -w eighting ) 來表示在同一個特征詞在不同區(qū)域中的相關。

還有很多學者致力于基于貝葉斯方法的中文垃圾郵件過濾技術的研究, 取得了一定的成效。但有幾個因素制約了其發(fā)展, 如:(1) 語言的制約, 漢語與英語在很多方面具有不同的特性, 不同直接把國外的研究結果應用到中文垃圾郵件的過濾上來。(2) 缺乏開源項目。(3) 缺乏公共的中文郵件語料, 很多實驗結果無法橫向比較, 個人收集的數據, 數量

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

第36卷(2008) 第4期　　　　　　　　　　　　　計算機與數字工程

　　　　　　　　　　　　105

少, 范圍窄, 具有很大的局限性, 其結果也缺乏說服力。目前, 已經有人開始進行相關的研究工作。

支持向量機(Support vector m achines , SVM ) 是在二十世紀90年代以來發(fā)展起來的一種統(tǒng)計學習方法, 它通過構造最優(yōu)線性分類面來指導分類。SVM 在解決小樣本學習、非線性及高維模式識別問題中表現(xiàn)較好。SVM 可以直接用于線性可分問題, 而對于線性不可分的情形, 可以構造一個變換, 將問題轉換到一個新的空間, 在這個新空間中線性可分。在文本分類中, SVM 是公認的較好的方法

[5]

之一。D rucker 將SVM 用于垃圾郵件過濾, 得到的結果再次印證這一點。D rucker 還得到一個結論就是, 采用二值表示的SVM 的性能稍高于采用多

[6]

值表示的SVM 。R ios and Zha 機森林方法(R R F , R F 過濾器在低誤判率時魯棒性更強, 但是兩者的性能都要優(yōu)于樸素貝葉斯過濾器。

[7]

L udlow 推斷大多數的垃圾郵件很有可能來自主要的150個制造者, 因此用身份認證技術對這個小團體的“文本指紋”進行驗證, 從而判斷是否是垃圾郵件。實驗結果表明, 利用這種方法可以得到較好的過濾效果, 甚至獲得了優(yōu)于貝葉斯過濾器的過濾效果。

[8]

C hhabra 提出了一種基于馬爾可夫隨機場

(M arkov R andom F ield, M R F ) 分類器模型, 這種

基于范例推理(C ase -based reasoning, CB R ) 系統(tǒng)是建立一個已有的分類實例庫(如:郵件庫) 來進行分類。當收到郵件后, 將收到的郵件與已有的郵件庫比較, 得到相似程度最高的郵件, 通過該郵件對應的類別來確定新郵件的類別。分類后, 郵件和對應的分類結果都存入郵件庫中, 為將來的郵件分類提供指導作用。C unningham 構造一個基于范例推理的分類器, 這個分類器能夠往實例庫中添加新實例, 和從實例庫中刪除舊實例, 使得系統(tǒng)能夠適應垃圾郵件和合法郵件中的特征變量的轉移。. 2. , 當郵件到達時, 先用各個組合的過濾器對郵件進行處理, 再綜合考慮單個過濾器的結果來決定郵件的類別。由于過濾器級別不同, 產生的錯誤互不相關, 因此能夠得到較好的性能。

基于B oosting 算法的過濾器是經典的組合過濾器, B oosting 算法的基本思想就是基于這樣一個事實:發(fā)現(xiàn)大量而粗略的經驗規(guī)則要比找到一條高度準確的預測規(guī)則容易得多。為了使用B oos 2ting 算法, 首先需要一個弱算法來找到大量經驗規(guī)則。B oosting 算法循環(huán)調用弱算法, 每輪循環(huán)向弱算法輸入訓練集的不同子集, 更準確的說是帶有不同權重分布的訓練集。每一次被調用, 弱算法都產生一條新的較弱的預測規(guī)則(即經驗規(guī)則) 。經過多輪循環(huán)之后, B oosting 算法將各輪循環(huán)產生的弱預測規(guī)則合并成一條預測規(guī)則, 最終的規(guī)則將會遠比任意一條弱規(guī)則準確。C arreras

[10]

and M arquez 利用A daB oost (一種B oosting 算法) 進行郵件過濾, 并與決策樹, 樸素貝葉斯和KNN 方法對比。實驗結果顯示, 性能優(yōu)于其它三種方法。而且, 能夠通過調節(jié)分類閥值得到較高的準確度。3. 2. 4　互補型過濾器灰名單是一種需要與其它過濾器結合使用的分類方法, 具體是指拒絕接收來自不熟悉的IP 地址的郵件, 同時系統(tǒng)自動回復接收郵件失敗的消息。灰名單基于的事實是, 當郵件發(fā)送失敗時, 發(fā)送垃圾郵件的軟件不會采取任何錯誤恢復措施, 更不會重新發(fā)送郵件; 而普通的郵件發(fā)送系統(tǒng)都會提醒發(fā)送者重新發(fā)送郵件。對于性能一般的垃圾郵件發(fā)送軟件, 灰名單不失為一個有效的過濾方法。

SM TP 路徑分析技術是一種以IP 地址認證電

[9]

方法考慮了郵件中單詞間的鄰近關系(M R F 基團) , 這樣在分類過程中就引入了自然語言中的相關詞之間的依賴關系。3. 2. 2　基于相似度比較的過濾器基于內容和基于事件的機器學習技術, 都是根據與存儲的郵件(如:訓練文本) 的相似度來判定收到的郵件的類別。

K 近鄰(K -N earst N eighbo r, KNN ) 是常用的基于內容的文本分類方法。分類時直接將待分類文本與訓練集合中的每個文本進行比較, 然后根據前K 篇相似的文本得到新文本的類別(最簡單的情況可以根據K 篇文本所屬的類別數的多少來確定最后類別) 。KNN 的原理非常直觀, 也很容易理解。在文本分類中KNN 也常常能夠取得好的結果。但是由于其分類速度的局限性, 不太適用于對分類速度要求較高的垃圾郵件過濾場合。有學者將KNN 方法引入到垃圾郵件過濾中, 實驗結果表明KNN 過濾器與貝葉斯過濾器的性能相當。

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

106張　萍等:對郵件過濾技術發(fā)展現(xiàn)狀的比較與分析　　　　　　　　　　　　總第222

期

[2]NU TTER R. Soft w are or app liance solution? N et 2w ork W orld Fusion [DB /OL].http://www.nw fusion . com /colum nists /2004/0301nutter . ht m l, 2004, 3, 1

[3]YO SH I DA K, ADA CH I F, W A SH I O T et al . D ensity -based spam detector[C ].In KDD ’04:P roceedings of the 2004A CM

S I G KDD

international conference on

Know ledge discovery and data m ining, A CM P ress, 2004:

子郵件寄件人身份的技術。SM TP 路徑分析算法通過檢測包含在垃圾郵件和正常郵件中的IP 地址

字串, 不斷自我學習, 自我完善。這樣當再有新郵件到來時, 它便能以相當的精度, 對郵件的真?zhèn)巫鞒雠袛?。這項技術通過檢測電子郵件中所包含的傳播路徑信息, 能較好地判斷出該郵件是否屬于電子垃圾。

486～493

[4]DAM I AN I E, PA RABO SCH I S, SAM A RA T I P et al .

P 2P -based collaborative spam detection and filtering In P 2P ’04:P roceedings of the Fourth International

[C ].

4　結語

本文總結了許多新的郵件過濾技術, 由于每個

作者所選用的郵件集和實驗平臺有所區(qū)別, 很難對分類結果進行比較, 只有使用統(tǒng)一的基準文集, 才能進行有意義的分析。但是這是一項艱巨的任務, , 涉及到個人隱私, 快, , 。

經過了多年的發(fā)展, 新興的反垃圾郵件技術層出不窮。其中, 基于規(guī)則和基于貝葉斯方法的過濾器的效果最為突出, 其改進算法也較多。但無論哪一種技術, 都無法完全應對多變的垃圾郵件。垃圾郵件和反垃圾郵件的技術演進必將長期存在, 反垃圾郵件技術的發(fā)展將日益趨向于全面包含最有效垃圾郵件阻斷技術的整體解決方案。

參考文獻

[1]H I DALGO J. Evaluating cost -sensitive unsolicited bulk em ail categorization [C ].P ress, 2002:615～620

In SA C ’02:Proceedings of

the 2002A CM sym posium on A pp lied com puting, A CM 2

C onference on Peer -to -Peer C om IEEE C om puter S ociety, 176～183