本文是期末報告作業，寫得不好請海涵。Gslin 在 newzilla 雜誌也寫了一系列關於 AntiSpam 的主題，有興趣探討其他相關內容的可以一併參考。
每一封 E-mail 都有兩個主要的部份： header 和 body 。 Header 的部份包括了信件的來源、時間、郵件主旨、編碼、經由哪些伺服氣遞送、以及最初的寄送者 IP 等等； body 的部份則是文件的內文和附檔等等。如果再進一步細分，在 header 的部份還包括了 RFC 規定的 header 、和 X- 開頭的自訂欄位，如表。
| 標準 E-mail 信件的範例 | ||
|---|---|---|
|
標準 header |
From return@trafficmagnet.net Wed Jul 24 22:22:59 2002 |
|
|
Optional header |
X-Mailer: CSMTPConnection v2.17 |
|
目前來說，判斷 spam mail 大略有幾種方式：
• 以來源來判斷
• 以信件的型態來判斷
• 以信件的內容來判斷
• 以使用者行為來判斷
上述四種方式分述如下。
以來源判斷
我們假設寄廣告信的人經常使用特定幾個 IP Address ，所以如果我們可以把這些不當使用者的來源都建立成一個資料庫，那麼 mail server 在收信前，只要先檢查信件是否來自這幾個特定的 IP ，就可以過濾掉一些常發廣告信的來源。不過，由於 E-mail 也有 relay 的機制，因此單單過濾最初發信的來源仍然不夠，還需要把一些 open-relay 的 mail server 也列管，原因是這些 open-relay 的 mail server 很有可能會轉送廣告信給我們，使得這樣的防護方式產生漏洞。所謂的 RBL(Relay Black List) 就是這樣的列管名單，透過全世界 E-mail 系統管理者的共同努力，提供全世界都能使用的資料庫，列管這些有可能代發廣告信的 mail server 。
不過這樣的作法無法防止使用動態 IP 寄發的廣告信，動輒擋掉大型 ISP 的 mail server 如 msa.hinet.net 也過於武斷，所以這種方式漸漸退居防護惡意攻擊的角色，而不再是防堵廣告信的主力。
除了來源 IP 以外，使用者也可以自行建立黑名單和白名單，自動過濾或 bypass 這些名單中的 Email 。
以信的型態來判斷
正常的 E-mail 會有一些所謂 " 正常" 的格式，這些格式是郵件軟體造成的。舉例而言，一般正常的信件大多在收件者欄位 (To) 或是副本收件者欄位 (Cc) 會有收信者的 Email Address ，然而廣告信寄信程式為了效率考量，大多不會把每一封信的 To 欄位都改成不同的 Email Address ，如果我們利用這個特性，就可以阻擋許多廣告信；不過相對的，也有可能把秘件副本 (Bcc) 的信件濾掉。
另外，一般用郵件軟體寄送的 HTML 版本的信件，還會包含一個純文字版的信件內容，以避免收件者沒辦法閱讀 HTML 格式信件時發生問題。但許多廣告信軟體都沒有附上對應的純文字部份，如果我們收到一封這樣的信，它就有很高的可能性是由廣告信軟體寄出的；不過，這種特徵也常常出現在以程式自動寄發的信件中，例如會員通知信等，所以也有誤判的風險。
當我們收集到越來越多這種特徵，就可以把它們發生的狀況加以組合，用來判斷這是廣告信的可能性。
以信件的內容來判斷
利用信件的內容有兩種作法，一種是以文字分佈為基礎的，是以內容單字的分佈作為線索；另一種是關鍵字為基礎的，以特定關鍵字出現的強度作為判斷標準。
第一種作法是利用廣告信大多會重覆寄給多個使用者的特性。當一封信寄進來時，系統會記錄它的 md5 checksum ，由於 md5 演算法可以替不同的內容取得不同的特徵值，如果有大量相同特徵值的信件內容湧進來，系統就會認定這很有可能是廣告信。不過，現今部份廣告信發送軟體會在標題或是內文中加入一些無意義的短句，讓每封信都不一樣，這樣 md 5 c hecksum 的運算結果也就不一樣。因此，有一些系統會先試着只取出一部份內容來計算，以避免被那些刻意外加的文字混淆。
另一種方式則是利用關鍵字來作為判斷基礎。廣告信中可能包含某些我們一眼就可以看出來不感興趣的內容，這可以從大多數的廣告信只需要看標題就可以決定是否要刪除看出來。如果我們設定一些關鍵字，並配合語意推理引擎，就可以過濾掉一些比較常見的廣告信。不過某些廣告信程式會在這些文字之中加入無意義的分隔，例如，把 Viagra 寫成 V~i~a~g~r~a ，所以必須要先經過前處理才能夠更為準確的找出隱藏的關鍵字。
以使用者行為來判斷
如果使用者只花一點時間就看完一封信，很快就按下刪除，那麼它很有可能是一封廣告信；如果這樣的行為產生在幾百個使用者身上，那麼和它相同的 E-mail 就可以直接當作廣告信了。又或是，如果使用者看完就轉寄，那它就比較不可能是廣告信。
可行方式
由上述的概論可以看出， Email 中可以用來判斷是否為廣告信的資訊或特徵非常多，但同時也沒有一種可以保證準確無誤。所以不同的特徵彼此組合起來，才能夠提高準確度。而運用不同的 Data Mining 作法，也有不同的效果。
因為判斷廣告信是依據某些特徵決定信件是否為廣告信，所以這個問題本身是個分類問題，以下依據幾個 Classification 的方式各介紹可行的作法。
Naïve Baysian Classification
我們先收集廣告信和正常信件的樣本，針對每一個欄位都進行統計，計算個別特徵與廣告信與否的機率，接下來，當收到一封新的樣本時，我們先把它的每一個特徵取出來，再查這個特徵是廣告信的機率有多高，把每一個特徵的機率相乘起來。最後再比較是廣告信的機率或是一般信件的機率高。
表 8 列出了幾個特徵與廣告信與否的的機率，由於每個欄位都是獨立的，而且只有兩種可能，所以各欄位機率相加都是 100% 。
| 各種特徵與廣告信與否的機率 | ||||||
|---|---|---|---|---|---|---|
|
標題未正確編碼 |
標題正確 |
未知的 |
已知的 |
HTML 信件無 Alternative Part |
HTML 信件有 Alternative Part |
|
|
廣告信的機率 |
80% |
40% |
55% |
10% |
85% |
45% |
|
正常信的機率 |
20% |
60% |
45% |
90% |
15% |
55% |
下表格是一封新收到的信，我們要判斷它是否為廣告信。擷取出來的特徵有三個：標題正確編碼、未知的寄件者、 HTML 信件無 Alternative Part ，計算之後得到的結果如表 3 所示，這封信是廣告信的機率遠大於正常信的機率，所以我們可以判斷它是廣告信。
| 待判斷的信件及判斷結果 | |||||
|---|---|---|---|---|---|
|
標題正確編碼 |
未知的寄件者 |
HTML 信件無 Alternative Part |
相乘後的機率 |
正規化的機率 |
|
|
廣告信的機率 |
40% |
55% |
85% |
18.7% |
82.2% |
|
正常信的機率 |
60% |
45% |
15% |
4.05% |
17.8% |
Decision Tree
我們也可以利用 Entropy-based 的方式來建立 Spam 的 Decision Tree 。在訓練階段，我們先計算每一個欄位的 Information Gain ，為了避免 Overfitting ，所以我們採用 Gain Ratio 來當作判斷依據，以 Gain Ratio 最大的當作 Root 並依序分類，建立 Subtree ，直到每一個 Leaf Node 都是 Pure 為止。
在判斷階段，我們依照信件的特徵在 Decision Tree 上 Traverse ，直到 Leaf Node ，即可知道是否為廣告信。
Instance-Based Learning
K-Nearest Neighbor 的技巧雖然沒辦法直接套用在 E-mail 上面，原因是要比較的信件太多了，所以幾乎不太可能採用 Lazy evaluation 的方式。不過如果我們把信件當成以文字 span 而成的空間，那麼每一封信都可以在這個 Text domain 找到一個對應的點，而我們可以收集一些屬於廣告信常出現的字眼，這些點就形成了 Spam 的 keyword instances 。我們可以運用這些 keyword instances 計算距離。距離的計算方式是利用文字相差幾個字元。如果一封信的內容包含許多個 spam keyword ，而且距離又不遠 ( 代表可能是該字的變形，如 viagra 改成 v~i~a~g~r~a) ，加總起來的結果若超過臨界值，那就認定它是廣告信。這種作法雖然不是傳統的 Instance-based ，但仍類似 Instance-based 的精神。
Pesty's Articles 
親愛的版主 妳好：
不好意思不知如何稱呼，所以就稱呼您為版主XD，
您的這篇用DM來防堵廣告信的論述相當不錯，
如果想對此瞭解深一點，
不知是否有相關期刊或書籍可參考（用DM防堵廣告信）。
感謝提供!
居然在這篇出現廣告… XD
Pingback: MyShare@URL>> 全文檢索