[建議]增加反垃圾郵件功能

[allen42]

希望建議增加反垃圾郵件功能
像是foxmail的“規則法過濾”、“學習法過濾（貝葉斯法過濾）”等技術
現在光靠open replay及mx反查是不夠的
我相信foxmail能做到雷電也可以

[Arnor]

[allen42]

貝葉斯過濾算法的基本步驟
發表日期：2004-07-04 作者：[轉貼] 出處：



原文 中國反垃圾郵件聯盟論壇


一． 貝葉斯過濾算法的基本步驟

1) 收集大量的垃圾郵件和非垃圾郵件，建立垃圾郵件集和非垃圾郵件集。
2) 提取郵件主題和郵件體中的獨立字串例如 ABC32，¥234等作為TOKEN串並統計提取出的TOKEN串出現的次數即字頻。按照上述的方法分別處理垃圾郵件集和非垃圾郵件集中的所有郵件。
3) 每一個郵件集對應一個哈希表，hashtable_good對應非垃圾郵件集而hashtable_bad對應垃圾郵件集。表中存儲TOKEN串到字頻的映射關系。
4) 計算每個哈希表中TOKEN串出現的概率P=（某TOKEN串的字頻）/（對應哈希表的長度）
5) 綜合考慮hashtable_good和hashtable_bad，推斷出當新來的郵件中出現某個TOKEN串時，該新郵件為垃圾郵件的概率。數學表達式為：
A事件----郵件為垃圾郵件;
t1,t2 …….tn代表TOKEN串
則P（A|ti）表示在郵件中出現TOKEN串ti時，該郵件為垃圾郵件的概率。
設
P1（ti）=（ti在hashtable_good中的值）
P2（ti）=（ti在hashtable_ bad中的值）
則 P（A|ti）= P1（ti）/[（P1（ti）+ P2（ti）]；
6) 建立新的哈希表 hashtable_probability存儲TOKEN串ti到P（A|ti）的映射
7) 至此，垃圾郵件集和非垃圾郵件集的學習過程結束。根据建立的哈希表 hashtable_probability可以估計一封新到的郵件為垃圾郵件的可能性。
當新到一封郵件時，按照步驟2）生成TOKEN串。查詢hashtable_probability得到該TOKEN 串的鍵值。
假設由該郵件共得到N個TOKEN串，t1,t2…….tn, hashtable_probability中對應的值為P1，P2，。。。。。。PN，
P(A|t1 ,t2, t3……tn)表示在郵件中同時出現多個TOKEN串t1,t2…….tn時，該郵件為垃圾郵件的概率。
由復合概率公式可得
P(A|t1 ,t2, t3……tn)=（P1*P2*。。。。PN）/[P1*P2*。。。。。PN+（1-P1）*（1-P2）*。。。（1-PN）]
當P(A|t1 ,t2, t3……tn)超過預定閾值時，就可以判斷郵件為垃圾郵件。

二． 貝葉斯過濾算法舉例

例如：一封含有“法輪功”字樣的垃圾郵件 A
和 一封含有“法律”字樣的非垃圾郵件B
根据郵件A生成hashtable_ bad，該哈希表中的記錄為
法：1次
輪：1次
功：1次
計算得在本表中：
法出現的概率為0。3
輪出現的概率為0。3
功出現的概率為0。3
根据郵件B生成hashtable_good，該哈希表中的記錄為：
法：1
律：1
計算得在本表中：
法出現的概率為0。5
律出現的概率為0。5
綜合考慮兩個哈希表，共有四個TOKEN串： 法 輪 功 律
當郵件中出現“法”時，該郵件為垃圾郵件的概率為：
P=0。3/（0。3+0。5）=0。375
出現“輪”時：
P=0。3/（0。3+0）=1
出現“功“時：
P=0。3/（0。3+0）=1
出現“律”時
P=0/（0+0。5）=0；
由此可得第三個哈希表：hashtable_probability 其數据為：
法：0。375
輪：1
功：1
律：0

當新到一封含有“功律”的郵件時，我們可得到兩個TOKEN串，功 律
查詢哈希表hashtable_probability可得
P（垃圾郵件| 功）=1
P （垃圾郵件|律）=0
此時該郵件為垃圾郵件的可能性為：
P=（0*1）/[0*1+（1-0）*（1-1）]=0
由此可推出該郵件為非垃圾郵件

更好的貝葉斯過濾法

譯者:李寄

2003年1月

（本文是在2003年垃圾郵件大會上的一個講話。它描述了我為提高在《一個計划》中提到算法所做的工作，以及我對未來的打算。）

我想在此給出的第一個發現，是一個用于評估科研論文的懶人算法。你只需寫下你想寫的，不去引用任何前人的工作，然后熱心讀者會把你應該引用的論文章節都寄給你。我在《一個計划》【1】發表于Slashdot之后發現的這個算法。

垃圾郵件過濾，是文件分類的一個子集，它是一個相當健全的領域。不過關于貝葉斯過濾法最早的兩個文獻都是在1988年大會上給出的，一個提供者是Pantel和Lin【2】，另一個是微軟研究所的一個小組【3】。

當我听說這項工作時我有點吃惊。如果人們早在四年前就開始貝葉斯過濾法的話，那為什麼如今沒人在用它呢？讀了文章后我明白為什麼了。Pantel和Lin的過濾法時那兩個中比較有效的一個，可它也只抓住了92%的垃圾郵件，並且是1.16%的錯糾率。

當我試著編寫一個貝葉斯過濾法時，它抓住了99.5%的垃圾郵件，且錯糾率低于0.03%【4】。兩個人做同一個實驗卻得到差別很大的結果，這是很應該引起注意的。在這件事中尤其如此，因為不同的結果可以導致完全相反的結論。誠然，不同用戶有不同的需求，不過我想了，對很多人來說，過濾效率僅92%錯糾率卻高達1.16%,意味著這個過濾法是在不好接受。而99.5%對應小于0.03%的錯糾率，則意味著相反。

那麼，為什麼我們得到如此不同的數字呢？我沒有嘗試去復制Pantel和Lin的結果，但只是讀了他們的論文，我發現有五件事大概可以解釋這個差异的。

第一個很簡單，他們的過濾法建立在一個很小的數据庫上：160個垃圾郵件和466個非垃圾郵件。即便數据庫如此之小，過濾效率還是應該高得多的。所以這些數字大概不恩那個确切說明他們算法的有效程度，更不用說廣義上的貝葉斯過濾法的有效程度了。

不過我認為，最重要的區別大概在于，他們忽略了郵件台頭。這在任何致力于垃圾郵件過濾器的人看來，都是一個不合常理的做法。可實際上在我嘗試編寫第一個過濾器時，我也忽視了台頭。為什麼呢？因為我想讓問題簡單化。那會兒我對郵件台頭知道得還不多，對我來說，它們就是一堆隨机的玩意兒。這里，對過濾器編寫者是一個教訓：不要忽略數据。你會覺得這個教訓太明顯了，不值一提，可我實際上不得不把它吸取了好几遍。

第三，Pantel和Lin對token進行了剪切，好比說，他們把“mailing”和“mailed”都壓縮成根詞“mail”來處理。他們大概覺得必須得這樣做，因為他們采用郵件集的容量之小。可若如此，這不過是一個不成熟的樂觀想法。

第四，他們用了不同的方法來算概率。他們把所有的token都用上了，而我只用了15個最具代表性的。當你使用所有的token時，你就傾向錯過較長的垃圾郵件，那些某人跟你講他們一生的故事，講直到某天他們通過某種分層營銷手段而致富的郵件。並且這樣的算法容易北垃圾散發者所愚弄：只需加上一大堆隨机文檔來中和掉那些垃圾朮語就可以了。

最后一點是，他們沒有對錯糾提起注意。我認為，不管什麼垃圾郵件過濾法，都需要包含一個方便旋鈕，你一擰，就能在降低過濾率的代价之上降低錯糾率。我用的法子，是把token在非垃圾郵件集里出現的次數加倍。

我認為，把過濾垃圾郵件當作單純是一個文件分類問題來處理不是個好主意。你可以使用文件分類技朮，可你的法子應當體現出這些文件是郵件的事實，並且特別是垃圾郵件。郵件不僅僅是文本，它具有自己的結构，過濾垃圾郵件不僅僅是分類，因為錯糾比錯放要惡劣得多多，你必須把它們看成是不同性質的差錯，並且這些差錯的來源並非什麼隨机偏差，而是活生生的致力于攻克你過濾器的垃圾郵件制作人。



Tokens


在Slashdot文章（譯者注：《一個計划》）之后，我听說的另一個項目是Bill Yerazunis的CRM114【5】。這是我剛提到過設計原理的一個反例。它是一個單純的文本分類器，但卻有著惊人的效率，可以在不知道自己在做什麼的情況下，把垃圾郵件近乎完美地給過濾掉。

當我理解了CRM114是怎麼工作的之后，看似不可避免地，我遲早德從基于單個單詞的過濾法走向類似這個的方法。不過我先是想著，我得看看依靠單個單詞能走多遠。然后那答案是，令人吃惊之遠。

總體上我致力于更精良的token化處理工作。對現有的垃圾郵件，我已能達到近似crm114的過濾效率。這些技朮跟Bill的（譯者注：CRM114用到的技朮）基本上是正交的。一個理想化方案大概是合並這二者。

《一個計划》中用的是一個對token的簡單定義方法:字母，數字，破折號，撇號，美元符號，這些是組成成分，其他的都是token分離符。我還忽略了詞格（譯者注：例如，主謂賓格）。

現在我有一個更復雜的token定義法則：

1． 詞格保留。

2． 惊嘆號是組成成分。

3． 當句號和逗號出現在兩個數字之間時，它們也是組成成分。這樣我可以使IP地址和价錢保持不碰。

4． 价格范圍如$20-25，是兩個token，$20和$25。

5． 在發往To，來自From，主題Subject，和回歸路徑Return-Path這些欄，或是url中的出現的token，作以相應的標記。例如，主題Subject中的“foo”就變成“Subject*foo”。（這里的星號可以是任何你沒定義成token組成成分的符號。）

以上措施提高了過濾器的詞匯量，于是使分辨率更高。舉例說，在現有的過濾器中，主題欄出現的“free”一詞具有98%的垃圾概率，而在正文出現的同一token概率僅為65%。

以下是現有的一些概率【6】：

Subject*FREE 0.9999
free!! 0.9999
To*free 0.9998
Subject*free 0.9782
free! 0.9199
Free 0.9198
Url*free 0.9091
FREE 0.8747
From*free 0.7636
free 0.6546

在上次的計划中，所有這些token的概率是一樣的，都是0.7602。那個過濾器識別的token大約有23,000個，現有的約為187,000個。

更大的token世界帶來的坏處是，錯放的机會會增加。對一個郵件集來說，提高其token數目的效果類似于減小其容量。例如，你要是把惊嘆號當成組成成分，結果你就找不到free連著7個惊嘆號的概率，雖然你明知道free帶兩惊嘆號的概率是99.99%。

一個解決方法是我所謂“退化法”。如果你找不到某個token的确切數值，你就把它處理成一個不那麼明确的版本。像末尾的惊嘆號，大寫字母，以及在那五個標記位置里出現，這些我都看成是使token更明确化的標志。例如，假如我找不到“Subject*free!”的概率，我就去找“Subject*free”，“free!”和“free”，然后取其中離0.5最遠的那個概率。

以下列舉的是過濾器在主題欄看見“FREE！！！”並且找不到其概率是所擁有的其他選擇【7】：

Subject*Free!!!
Subject*free!!!
Subject*FREE!
Subject*Free!
Subject*free!
Subject*FREE
Subject*Free
Subject*free
FREE!!!
Free!!!
free!!!
FREE!
Free!
free!
FREE
Free
free

當你這麼做時，注意一定要把開頭字母大寫和所有字母大寫以及所有字母小寫這些情況一起考慮進去。垃圾郵件傾向含有更多祈使句式的句子，同時那些句子的第一個字是動詞。所以開頭字母大寫的動詞比所有小寫字母的有更高的垃圾概率。我的過濾器里，“Act”的垃圾概率是98%，而“act”僅有62%。

當你提高過濾器的詞匯量，你結果會把相同的單詞算上多遍，――就你過去定義的“相同”而言。邏輯上講，它們不再是同一個token了。不過如果你還是覺得不爽的話，那麼從我的經驗看來，這些你看著是被重復計算的詞，傾向于剛好就是你想要重復計算的那些。

加大了的詞庫帶來的另一個后果，是當你觀察一個收到的郵件時，你會發現更多有趣的token，即概率遠離0.5的那些。我用15個最關鍵詞來決定一封郵件是否垃圾，不過，若是用這樣一個固定的數字你會遇上困難。如果你發現很多极度有趣的token，那結果會是，你的結論被一些莫名其妙的隨机事件所左右，是它們決定了這些同等關鍵的token的排列次序。對付這情況的方法是，把其中一些token看成比其他的更為關鍵。

舉例來說，“dalco”這個token在我的垃圾郵件集中出現過3次，從未在合法郵件集中出現過。“Url*optmails”這個token（意思是“optmails”包含在某url中）出現了1223次。可當我計算token的概率時，這兩個有相同的垃圾概率，0.99那個檻。

這感覺不大對。關于給予這兩個token本質上不同概率（Pantel和Lin是這麼干的）的問題，存在有理論依据，不過我還沒試過。看上去至少得這樣：如果我們發現有多于15個token只出現在這個或那個郵件集，我們就得優先考慮出現次數很多的那些。所以現在有兩個檻值。對于只出現在垃圾郵件集的token，當它們出現超過10次時其概率時0.999，否則0.998。對相反方向那些只出現在合法郵件集的token，我們作同樣處理。以后我大概會對概率進行實質上的權衡。不過以上這些微小份量的差別，至少确保了token整理的方向正确性。

另一個可能應該是不只考慮15個token，而是把所有token放在一個特定的有趣程度檻上進行衡量。Steven Houser在他的統計法郵件過濾器中是這麼做的【8】。如果你用一個檻，就得把它弄得非常高，不然垃圾散發者會拿更多合法詞匯充斥其郵件來瞞過你。

最后一點是，我們可以拿html怎麼辦？我試過所有可能的選擇，從忽略它到對它作語法分析。忽略html不號，因為它充滿了有用的垃圾郵件信號。但你若是對它作語法分析，你的過濾器會退化成光是一個html識別器。看來最有效的是中間方法，即注意一部分token而放過其他部分。我是查看img和font標簽，而忽略別的。鏈接和圖片自然是你應該看的，因為它們包含了url。

對付html，我大概能做的更聰明些，不過我不認為它值得花很多時間在上面。那些滿是html的垃圾郵件很容易過濾，精明些的垃圾散發者早已避開了這個。所以未來的工作情況，不應決定于你是怎麼對付html的。



工作情況


自2002年12月10日，至2003年1月10日之間，我收到約1750個垃圾郵件，其中有4個被放過了。這個過濾率大概有99.75%。這四個溜掉的垃圾郵件中，有兩個是因為它們剛好用了我合法郵件中常出現的詞。

第三個是利用一個不安全的cgi腳本把郵件發給第三方的那種垃圾郵件。只基于內容它們很難過濾，因為台頭清白並且用詞謹慎。即便如此，我一般還是能抓住它們。這一個是以0.88的概率給溜了，剛好低過0.9的檻。

自然，若是用查看多重token序列方法應該能輕易抓住它。“Below is the result of your feedback form”立馬就把它給賣了。

第四個則是我所謂“未來型”垃圾郵件，因為它正是我指望垃圾郵件會進化成的樣子：一些全然是中性的文本，接著來一個url。在這里，它來自某個聲稱剛做完主頁讓我去看一眼的家伙（那個主頁自然是一個黃色網站的廣告）。

如果垃圾散發者小心台頭，並且使用新鮮的url，那這種“未來型”垃圾郵件將沒什麼好引起過濾器注意的地方。我們當然可以放一個爬虫去其網站，進行反擊，不過那未必是必須的。這種未來型垃圾郵件，它們的回應率一定很低，不然的話所有人都在用它了。若是低得足夠的話，垃圾散發者干這個就會划不來，那麼我們也就不需要花大力氣來進行過濾了。

現在讓我們來看真正令人震惊的消息。在這同樣的一個月之內，我弄出了三個錯糾郵件。

在某種程度上，錯糾的存在是一種解脫。當我寫《一個計划》時，我一個錯糾都沒碰上，于是就沒法知道它們該長什麼樣兒。現在我有了几個。解脫的是，它們不像我擔心的那麼糟。統計方法過濾器所產生的錯糾郵件，其實就是那些听上去特象垃圾郵件的家伙，並且傾向是你最不介意錯過的那些。

錯糾郵件中，有兩個是我買過東西商家發來的新聞信。我從沒要求過接受它們，所以有理由說它們也是垃圾郵件。不過我當它們是錯糾，因為我從未把它們當垃圾郵件一樣刪掉過。過濾器捕獲它們的原因是，這兩公司都于1月份從發送自他們自己的服務器轉成商業郵件發送了，並且它們的台頭和主體都變得更垃圾化了。

第三個錯糾卻是一個坏例子。它來自埃及的某人，從頭到尾都大寫。這是把token設置得更敏感的直接后果。《一個計划》中用到的過濾器不過錯抓住它。

難說總體的錯糾率會有多高，因為統計上講，我們身處噪音之中。任何致力于過濾器的人（至少是有效的過濾器），都會警覺于這個問題。有些郵件你壓根說不好它們是不是垃圾，而當你把過濾器做得嚴格了，這些剛好就是你到頭來得面對的郵件。舉例說，迄今為止過濾器抓住了兩個因拼寫錯誤誤發到我地址來的郵件，其中一個是把我當成另外什麼人了。它們究竟是我的垃圾郵件還是非垃圾郵件，這可說不好。

另一個錯糾郵件是來自Virtumundo的某個副總經理。我裝成是他們的顧客寫信過去，然后他們回信過來。因為回信是通過Virtumundo的服務器，其台頭是你想象得出最可疑的那種。同樣這算不算錯糾也很難說，不過帶點Heisenberg不确定性效應（譯者注：Heisenberg Uncertainty Effect---“The more precisely the position is determined, the less precisely the momentum is known.”你的位置越明确，狀態就越難料。）：我收到它，只因我在寫關于垃圾郵件過濾器的東西。

不算這些的話，我總計碰到過五個錯糾郵件，在約7740個合法郵件中計0.06%。另外兩個是我買的東西被back-order的同志，和一個來自Evite的聚會提醒。

我不認為這些數字是可信的，部分因為樣本太小，部分因為我相信我可以修改過濾器，使它不再抓其中一些。

錯糾對我來說，同錯放使不同種類的差錯。過濾率是用來測量工作情況的，錯糾我則認為更象是bug。我把提高過濾率當作優化工作來做，而減少錯糾就象是debug。

所以這五個錯糾郵件就是我的bug清單。舉例說，那個垃圾郵件的被抓，是因為大寫字母使過濾器看它象一個Nigerian垃圾郵件。這确實是一種bug。跟html相似，一封郵件所有字母都大寫，從概念上講的确只是一個特征，而非每個單詞都分別有一個特征。我得用更高明的手段處理這事。

那麼，我們拿這0.06%怎麼辦呢？我沒想太多。呢可以當它是一個上限，同時別忘了樣本空間之小。不過就現階段而言，這更多是一個對在我使用下貝葉斯過濾器所產生bug的測度，而不能算成是貝葉斯過濾器本質上的錯糾率。



未來


隨后是什麼？過濾是一個優化問題，而優化的關鍵是概括。別試著去猜你的代碼在哪變慢，因為你會猜錯。你得去觀察，你的代碼在哪走慢了，然后改進它。在過濾中，以上過程即是：觀察你所錯過的垃圾郵件，然后搞明白你的怎麼做才能抓住它們。

例如，現在垃圾散發者們正主動運作，要避開過濾器，他們在做的一件事是，把單詞分割或者拼錯，這樣來防止被過濾器識別。不過這方面的努力不是我的重點，因為我能不費力地抓住這種垃圾郵件【10】。

有兩種垃圾郵件，是我現在感到麻煩的。一個是那種假裝來自某個女人，邀你去跟她聊天，或者看她在什麼黃色網站上的資料。這些能溜過過濾器是因為，它們是那種不需使用推銷詞匯的推銷手段，並且它們用的全是我真實郵件里那些詞。

另一種我不大好過濾掉的，是那些來自（例如Bulgaria）的某公司發來的提供編程服務合約的垃圾郵件。它們能通過，是因為我也是個編程員，並且那些垃圾郵件的用詞跟我真實郵件的一個樣兒。

我大概會先致力于個人廣告類。我想要是再看仔細點兒，我應該能發現它們跟我真實郵件之間的統計學差异。文筆自然是不同的，哪怕得用到多重單詞過濾法。而且，我注意到它們都傾向重復提及其url，而在合法郵件中提到url的人不大會這麼干【11】。

境外合約那種垃圾郵件將不好對付。即便你往那網站發個爬虫，你也不會發現一杆冒煙兒的統計槍。也許唯一的解答是，弄一個現有垃圾郵件包含域名的主要列表【12】。不過這種郵件的數量多不至此。如果垃圾郵件就只剩下這些不請自來的Bulgaria來的編程服務合約的話，我們也許不妨都去忙點什麼別的。

統計過濾法真能令我們走這麼遠麼？我不知道。現在對我個人來說，垃圾郵件不是個問題。不過至今為止，垃圾散發者還未曾認真努力過來瞞過統計過濾器。要是他們這麼做了，那會怎麼樣？

對網絡層的過濾器，我不感覺樂觀【13】。當有一個值得通過的靜止不動的障礙物在那呆著，垃圾散發者可以相當有效地通過去。現在已經有一個名叫Assurance Systems的公司，專門把你的郵件放在Spamassassin下運行，然后告訴你它是否會被過濾掉。

網絡層的過濾器也不是全沒用。他們大概足以用來干掉所有“opt-in”的垃圾郵件，意即來自諸如Virtumundo或Equalamail等公司的，聲稱他們确實在使用opt-in清單的垃圾郵件。你可以光是基于台頭就過濾掉那些家伙，不管他們在郵件主題說些什麼。不過，任何人只有樂意偽造台頭，或是使用開放型中繼站，（可以想象大多數黃色垃圾散發者都會如此）那他們就應該能讓一些郵件（值得一提的是，那不會是他們最想傳遞的郵件）通過網絡層過濾器，只要他們想。

我持樂觀態度的的，是那些基于每個用戶個人郵件來計算概率的過濾器。它們可以更有效得多，不光是避免錯糾，而且在過濾上也是如此。例如，在任何地方發現64位編碼的接受者地址，就是一個很好的垃圾警報器。

不過，個人化過濾器的真正優點在于，它們個個都不一樣。如果每個人的過濾器都有不同的概率數字，那會使垃圾散發者的優化系統――程序員稱之為“編輯－編譯－測試”循環――以惊人緩慢的方式打轉。他們不能光是修改一個垃圾郵件使之能通過他們桌面上的某個過濾器，而是得就每次修改都做一下測試。這就像是在缺乏互動層面的基礎上，用某個語言進行編程，我不指望任何人會喜歡干這個。



注釋


【1】 Paul Graham. 《一個關于垃圾郵件的計划》。2002年8月。http://paulgrahan.com/spam.html。

這個算法用的是一種簡化貝葉斯法則來計算概率。有兩個簡化的假設：一是單個物體（單詞）的概率是獨立的，一是我們對一封郵件是垃圾的概率一無所知。

第一個假設在文本分類中很常見。這麼做的算法叫做“幼稚的貝葉斯”。

第二個假設，我是基于我的日常垃圾郵件進項每天（事實上，每小時）都不一樣的事實而提出的，因為這樣一來，整體比例就壓根不能用來當作預設。如果你假設垃圾的概率和非垃圾的概率都是0.5，那它們就相互抵消了，你就可以把它們從計算公式里整個扔掉。

如果是在垃圾與非垃圾比例持續性很高或者，尤其是很低的情況下做貝葉斯過濾器，那你大概能用加進預設概率的方法來提高工作情況。要想這麼做，你得在一天的不同時候對比例進行跟蹤，因為垃圾郵件和合法郵件有各自不同的日常作息。

【2】 Patrick Pantel和Dekang Lin。《SpamCop-A Spam Classification & Organization Program》。AAAI-98工作間在學會文本歸類方法之后。

【3】 Mehran Sahami，Susan Dumais，David Heckerman和Eric Horvitz。《A Bayesian Approach to Filtering Junk E-mail》。AAAI-98工作間在學會文本歸類方法之后。

【4】 那時我在4000封合法郵件中沒有一個錯糾。如果下一個合法郵件被錯糾，那結果會是0.03%。正如我后來指出的，這些錯糾率不可信。我在這里引用這個數据，只是位了說明不管錯糾率會是多少，它是小于1.16%的。

【5】 Bill Yerazunis。《Sparse Binary Polynomial Hash Message Filtering and the CRM114 Discriminator》。2003垃圾郵件大會之后。

【6】 在《一個計划》中，我用了0.99和0.1的檻。把檻設得跟郵件集的大小成比例應該是有道理的。因為我現在兩種郵件都用10,000個做郵件集，現在的檻是0.9999和0.0001了。

【7】 這里有一個毛病是我大概應該修改的。現在情況是，當“Subject*foo”退化成“foo”時，這意味著你獲取的是“foo”出現在我標記的那5個部分之外的主題或台頭中的統計數字。我應該把“foo”這個詞的總體出現情況以及特殊情況都記錄下來，然后把“Subject*foo”退化成“Anywhere*foo”而不是“foo”。同樣的，我應該把字母大寫退化成所有形式，而不是字母小寫。

用這個方法來對付价錢應該也是好的，好比，“$129.99”退化成“$--9.99”，“-$--.99”，和“$--”。

你還可以把單詞退化成它們的一般形式，不過這當你使用小型郵件集時大概只能提高一開頭的過濾率。

【8】 Steven Hauser。《Statistical Spam Filter Works for Me》。 http://www.sofbot.com.

【9】 錯糾並不都等价，我們在比較各種針對垃圾郵件的技朮時，應當記住這點。不光有那些近乎垃圾郵件的你不在乎丟失的錯糾郵件，還有一些別的，好比因黑名單而造成的錯糾，那只是些別人發給你的正常郵件，因為他們使用了錯誤的ISP而被丟失了。這兩種情況下你都時抓住了“約等于”垃圾的郵件，不過對黑名單來說，這個“約等于”是物理意義上的，而對過濾器來說這是文本意義上的。

不過公平地說，象SBL這種值得信賴的新生代黑名單，它所造成的錯糾，要比早期像MAPS RBL這種黑名單要少得多多，因為早期黑名單造成一大堆錯糾，不過是它想要引起公眾對ISP的注意的一種故意手段。

【10】 如果垃圾散發者改進到能用這種混淆token的方法制造出大麻煩，我們可以簡單刪除空格，句號，逗號等，來進行反擊，並且可以用一個詞典來把單詞從得到的序列中給找出來。當然了，把這種隱藏在文本中的單詞找出來，這事本身就是垃圾郵件的一個証据。

這種找詞不會是簡單的。它需要比重組單詞邊界更多的東西；垃圾散發者添加（“xHot nPorn cSite”）並且省略（“P#rn”）這些詞。視覺研究在這里大概會有用處，因為人類視覺正是這些詭計所能嘗試的极限。

【11】 一般來說，垃圾郵件的重復率要比普通郵件為高。他們想使他們的信息一步到位。現在我並不准許15個頭號token中有重復，因為要是發送者剛好把什麼坏詞用上多遍，那就會導致錯糾。（在我現有的過濾器中，“dick”的垃圾概率有0.9999，可它同時也是個人名。）不過看來我們至少得對重復提起注意，所以我大概會嘗試，對每個token允許至多兩遍的重復，正如Brian Burton在SpamProbe里做的那樣。

【12】 這是一旦垃圾散發者被迫使用mad-lib技朮來生成文件中的所有其他文本，像Brightmail那樣的方法將退化成的樣子。

【13】 爭議是，我們是否應該致力于網絡層的過濾器，因為它更有效。當人們這麼說的時候，他們的意思一般是：我們已經在網絡層有過濾器了，就不想再從底層開始。不過問題是，你不能為了支持你的解決方案而竄改題目。

曆史上說，在軟件設計上總是小規模那方失敗。人們傾向于做的，是為使其他理由下作出的選擇（特別是不動的選擇）名正言順而使用它們。

感謝Sarah Harlin, Trevor Blackwell, Dan Giffin閱讀此文手稿，並且再次感謝Dan打造這個過濾器賴以工作的大部分基礎。

[allen42]

垃圾郵件終結者－貝氏過濾法

記者 / iThome採購情報 2004-08-02



透過不斷學習與訓練，貝氏過濾法準確度高達九成
垃圾郵件氾濫成災，是所有電子郵件使用者的夢魘。對抗垃圾信件的技術日新月異，其中最為被廣泛討論的就是「貝氏過濾法（Bayesian Filtering）」。貝氏過濾法是利用貝氏定理發明的過濾法，簡單來說，貝氏定理是結合事前機率與條件機率，導出事後機率的過程。



越來越多阻擋垃圾產品採用貝氏演算法來過濾。貝氏文字分類其實並不算為新興領域，近年來垃圾郵件氾濫，貝氏定理被應用在區分垃圾信件上有令人驚訝的成效，因此成了對抗垃圾信件的新寵兒。

貝氏過濾法如何運作
現代人已逐漸習慣使用類似貝氏定理的概念來分析垃圾信件。例如我們會認為信件中出現「未滿十八歲」字眼即可能為垃圾信件。如果這封信件同時出現「極品」、「熟女」、「偷拍」等字眼，我們便已幾乎肯定此即為不折不扣的垃圾信件。說穿了，我們用過往的收信經驗，判定新的信件是否為垃圾信。同理可證貝氏定理應用在內容過濾領域方面的強大效能，貝氏過濾法即是採用類似，但更客觀的統計方式來偵測其為垃圾信件之機率。



上述所提及「未滿十八歲」、「極品」、「熟女」、「偷拍」對「貝氏過濾法」而言皆為單詞（Token）。一般來說「貝氏過濾法」會有個資料庫，暫且稱之為「貝氏過濾法資料庫」，其主要作用為儲存單詞與單詞的機率。資料庫一開始是淨空的，所以無法判定垃圾信件。別忘了貝氏定理是要仰賴過往累積的數據來預測事件發生的機率。



因此對於空的「貝氏過濾法資料庫」，如能事先提供1000封垃圾信，與1000封正常信件，對信件辨別的訓練過程將帶來莫大幫助，首先分別將1000封的正常信與垃圾信放入資料庫，系統會將這2000封信的內容切成單詞，給予不同的機率。當下次新信件來時，一樣會把信件分解成單詞，比對訓練過的「貝氏過濾法資料庫」，分析過往的經驗，將能精確評判此封高達為垃圾信件的機率。有了訓練「貝氏過濾法資料庫」的步驟，貝氏過濾法的精準率必能達到95%~99.95%之準值。

優異的學習阻擋邏輯
貝氏過濾法仍可在眾多過濾法中一枝獨秀的最主要原因，乃為其極高的準確度、學習方式容易、可針對不同產業調整、垃圾信發送者（Spammer）不容易將垃圾信穿透。垃圾發送者會大量發放垃圾信件，於一段時間後更改內文結構，讓阻擋垃圾的產品疲於奔命更換新過濾規則。



垃圾其實類似於病毒；譬如防毒廠商必須為新病毒提供防毒定義檔，否則未被攔截的病毒勢將危害整個網路；假設一套有效系統能在初次中毒後，將病毒載入其中，日後即可自動攔阻同種病毒，聽起來是否很令人振奮？沒錯，貝氏過濾法即是基於此種理念，當同一封垃圾大量傳送時，同一間公司便會有相當人數收到同一封垃圾信，假設第一人將收到的垃圾信即刻送回系統學習，下一封垃圾信就會被有效攔截。此外，垃圾信件種類遠多於病毒，其製作門檻則反之，變形垃圾郵件在廠商還沒研發出新的垃圾定義檔時，貝氏過濾法已可先行學習，防範下一封類似的垃圾信件。



再者不同產業對垃圾的定義也會有所不同，一般人只要看到「威而剛」就想到垃圾，對於藥廠或是醫院而言則未必。使用貝氏過濾法的優點是；可針對各行各業學習不同的認定方式。一般廠商都使用規則來阻擋垃圾郵件，一旦被找出弱點，垃圾發送者即可針對弱點狡猾地避開系統偵測，長驅直入至收信者的信箱。



貝氏過濾法的使用者，基本上會依據產業需求學習自身認定垃圾與正常信件，故學習的信件不同，發送者不再輕易找到通用的弱點將信件寄給每個郵件使用者。當垃圾的攔截率高時，發送垃圾者的效益愈成反比，垃圾發送者自然漸漸將目標轉向無垃圾阻擋機制的使用者，甚或具備共通弱點的垃圾郵件阻擋機制。

貝氏過濾對抗中文垃圾信
貝氏過濾法的功效卓越，但在中文環境上並非一應俱全。貝氏過濾法以單詞（Token）作為依據，對英語系語文而言，可善加利用空白或標點符號辨識單詞。但相較於中文字，Big5乃是由兩個byte所組成，字與字間基本上並無空白，在加上語意通常由「詞」而非「字」來產生，如果想切出有意義而準確的單詞則必須搭配中文詞庫，或自然語言技術將有意義的字句取出單詞。然而這也是為何國外產品使用相同貝氏過濾法的技術，準確度卻不一的主因。

穿透貝氏過濾法的攔截
貝氏過濾法是由統計的觀點來分析，要躲過它，必須使用大量的中性且儘量不提及與「垃圾郵件」相關的字眼；或者必須是大量被使用者學習過的正常信件詞彙。雖然如此，垃圾發送者依然不容易將垃圾信件穿透貝氏過濾法的過濾，畢竟要垃圾信件完全不提及其相關字眼非常困難，因為此乃為其廣告來源。收信者將本身認定的正常信件送給貝氏過濾法學習，統計出來最常使用的正常信件用詞只有「貝氏過濾法資料庫」知道，垃圾發送者除非經過百般嘗試否則穿透機率十分渺茫。其嘗試過程中，又已迅速地被送回垃圾學習機制了。唯一要穿透貝氏過濾法的辦法，便是找到疏於訓練「貝氏過濾法資料庫」的使用者，成功機會也許較高。



貝氏過濾法的改良型
貝氏過濾法與「啟發式」最大相異處在於前者利用統計的方式找出垃圾特徵，後者乃經由人工找出垃圾特徵。啟發式同樣具備相當的優勢；例如「未滿十八歲的極品」，啟發式可採用作法為：「未滿十八歲」此字句中，其字眼出現過後的10個字內有出現「極品」一併列入垃圾特徵；換言之「未滿十八歲的極品」、「未滿十八歲的美女極品」即為此例。但一旦出現「極品燕窩未滿十八歲不適宜」，則啟發式就不認定為垃圾特徵，但由於此詞句中同時出現「未滿十八歲」與「極品」，「貝氏演算法」則可能誤判為垃圾信件。針對此點，目前貝氏過濾法也出現改良型，其改良方式為不單用單詞做統計，而改採用短句（Phrase）進行改良判斷的精準率，使用短句算是目前較新穎的技術。



貝氏過濾搭配啟發式過濾
貝氏過濾法與常被討論的「啟發式（Heuristic）」相異之處，在於啟發式可將已被研究出來的垃圾郵件特徵，採規則（Rule Base）方式給予不同的分數，進而偵測電子郵件中有多少符合的規則，再依據這些規則所被指定的分數加總，藉此判定郵件本身擁有垃圾特徵值的比重高低。與「啟發式」不同的是，「貝氏過濾法」是將信件切分成單詞，利用演算法統計每個單詞的機率，進而推算出可能為垃圾信高達的機率。



以攤販對假鈔真偽的辨為例，目前假鈔防偽線如假似真已無法逕行辨識，攤販得經由盲人點、浮水印甚至螢光燈照射…等多重管道下辨別偽鈔。同樣的，垃圾發送者的技術也越來越精進，不但使用真路由，更甚者偽造信件標頭也精進到與真正信件標頭無法區別。為避免高誤判率，目前主流技術會一併將信件標頭與內文同時進行垃圾信件特徵偵測，即使用真實信件標頭或幾可亂真之標頭的垃圾信件，其特徵仍可從內文察覺。最新趨勢是將「啟發式」與貝氏過濾法兩者搭配使用，將貝氏過濾法偵測垃圾機率當成「啟發式」的判斷條件之一。這樣的作法可以同時採用兩邊的優點，交叉比對。當然，持續訓練「貝氏過濾法資料庫」會讓準確度平穩地維持在95%~99.95%以上。文☉蔡承家



作者簡介
蔡承家

寬華網路科技自有產品處經理，曾在澳洲ISP參與系統網路工程，並曾於IBM子公司擔任軟體、系統、EC、客服部等部門經理，累積ISP網路產業共有七年經驗。 近年來致力於發展郵件稽核側錄、郵件防駭、防毒、防垃圾等相關產品開發。



SPAM的歷史
我們一般稱垃圾郵件為SPAM或Junk Mail，更繞口的說法是Unsolicited Commercial Email（未經邀約的商業電子郵件）或Unsolicited Bulk E-mail（未經邀約的大量電子郵件），就是將一份內容相同的電子郵件，未經收件人同意，大量寄送給許多人，其內容大多是與收信人無關的商業廣告，而且收件人無法拒收。



其實SPAM不是現代的產物，早在1975年，就有關於垃圾郵件的記錄，1985年8月出現第一封透過電子郵件傳送的「連鎖信」。



1994年4月，Canter & Siegel法律事務所向6000多個新聞群組發送同樣內容的垃圾郵件，也就是著名的「綠卡樂透（Greencard Lottery）」事件。



1995年5月，第一個專門發垃圾郵件的軟體Floodgate誕生，能夠自動發送大量郵件，同年8月，已經有數百萬個電子郵件地址在市面上販售。



1996年3月，專家提出過濾垃圾郵件的方法，並研發一些簡單的過濾工具。1996年4月，垃圾郵件出現另一個名稱UCE（Unsolicited Commercial Email），而且漸受企業重視，人們也開始想辦法阻檔垃圾郵件的氾濫。



為了閃避各種對垃圾郵件的抵制，Spammer開始偽造寄件人及郵件地址，1997年3月，他們把目標轉到Mail Relay，利用其他人的郵件伺服器寄送垃圾郵件。



在過去幾年，世界各地成立許多反垃圾郵件組織，例如ORBS、DSBL、MAPS、SPAMHAUS、UXN等。不過，這些組織也是Spammer攻擊的對象，如SPEWS、Osirusoft（relay.osirusoft.com)及SORBS（www.dnsbl.sorbs.net），在去年就傳出被Sobig蠕蟲攻擊的消息。



我們可以預期，這場戰爭仍會持續多年，正對邪的對抗將持續下去。文☉陳世煌
http://shoppingguide.ithome.com.tw/special/special2004-08-02-002.html

[fish206452]

呵呵好複雜
小弟看不董


不過還是希望有這種功能
_________________
pchomespammail@pchome.com.tw

[chienlun]

附議~
每天一千多封 廣告...
快煩死

[jinn0102]

加油∼
做到別人做不到的，就是賣點∼
推~推~推~

[Arnor]

http://www.raidenmaild.com/tw/kb/how-to-setup-spamassassin.html
_________________
*若是想問問題的話, 請務必不要塗改任何 IP, 網域資料, 您若不願貼上IP或網域, 請改以電子郵件來詢問. 謝謝您的配合.*
*若是回報疑似軟體的運行或邏輯或資料處理有誤的問題, 小弟很樂意去了解您的情況, 但請務必以最新版來做回報, 如果以郵件詢問, 請參考 http://www.raidenmaild.com/tw/feedback.html 的說明, 最好標題加個 RaidenMAILD 字樣, 才不致會遺漏了您的信唷. 謝謝您的配合^^*
*在版上發文請遵守網路禮儀, 並請持著虛心敘述問題請教他人, 凡發現違反的文, 均一律刪除為優先, 不另行通知喔.
*與使用者教學相長腦力激盪是我輩成就感的來源, 誠心希望您能不吝指教.
*雷電MAILD 知識庫文件 http://www.raidenmaild.com/tw/kb/

素還尊
Team John Long.
Email: arnor@raidenmaild.com
公司網站 http://www.raidenmaild.com/company/