界面駭客日記(31) - SPAM退治 増井俊之

最近は誰もがメールを使うようになってきたせいか、 私のところにも毎日沢山の興味深いSPAMが届くようになってしまいました。 以前はほとんど気にするほどの量は届かなかったのでよかったのですが、 毎日何十通ものSPAMメールが届くようになると 流石に何らかの対策をしたくなってきます。 マイクロソフト社の最近の研究発表イベントの報告[1]によれば、 同社は先進的な検索技術やユーザインタフェース技術の研究の他、 SPAM除去技術にも大きく力を入れているのだそうです。 SPAMの除去というテーマが 時間や頭を使って研究するべきものなのか若干疑問ではありますが、 情報検索や知識獲得などの研究との関連は深いといえるでしょう。

SPAM判定規則の利用

SPAMメールは独特の形式をしていたり 独特な文字列を含んでいることが多いので、 これらを検出する規則を記述することにより 比較的簡単にSPAMの判定を行なうことができます。 たとえば、 メールのFrom行やSubject行、本文の中の特定のキーワードを検出することにより 簡単に多くのSPAMを検出することができます。 メールのタイトルに「Viagra」という文字列が入っていればほぼこれは SPAMと断言できるでしょうし、 スパマー特有のアドレスを検出することもできます。 PerlやRubyのようなスクリプト言語を使う場合、 以下のようなパタンマッチプログラムによって 簡単にこのようなSPAMメールを検出することができます。 
/Subject:.*\s(sexy|viagra)/i
/From: spammer@hotmail.com/
とはいえこういうものを沢山記述したプログラムを書くのはきりがないので、 規則を書いておくだけでSPAM判定を行なってくれる SpamAssassin[2]というシステムがよく使われています。 SpamAssassinは、 メッセージに対し、 HTMLメールかどうか/ 特定のキーワードを含むかどうか/ 感嘆詞が沢山含まれているかどうか/ などといった各種の検査を適用してメッセージのSPAM度のスコアを計算し、 その値が設定値を越えた場合はSPAMであるというフラグをメールのヘッダに挿入します。 メール分類プログラムなどを使って、 このようなヘッダをもつメールを除去することにより SPAMを掃除することが可能になります。

とはいうものの、実際に規則を沢山記述するのは面倒ですし、 “s*e*x*y”, “V1agra” のように普通の規則にマッチしない文字列を使われた場合は フィルタがうまく働きません。 また、規則やパタンを書き間違えるとSPAMでないメールもSPAM扱いされてしまう可能性があるので、 分類結果については常に注意を払う必要があります。 このように、 ユーザが自分で規則を記述する方法は、 SPAM判定規則の作成を趣味とする人には良いのですが、あまり万人向きとはいえません。

統計的手法の利用

SPAM判定規則をユーザが指定するのではなく、 SPAMメールと非SPAMメールの例を与えるだけで システムが自動的にSPAMメールを分類してくれるようであれば、 以上のような問題点は解決するはずです。 データを与えるだけでシステムが自動的に規則を学んでいくという手法は、 機械学習、 例からのプログラミング(Programming by Example: PBE) などと呼ばれて人工知能研究の分野で長年研究が行なわれてきましたが、 複雑な規則をデータのみから学習することは一般に困難であるため、 有効な応用例は多くありませんでした。 SPAMのフィルタリングも同様に困難かと思われましたが、 実はもっとずっと単純に単語の出現頻度を計算するという 統計的な方法で簡単SPAMメールを分類できるということを、 Paul Graham氏が 「A Plan for Spam」という文書[2]で公開したため、 統計的な手法の人気が最近急に浮上してきました。 Paul Graham氏は、2001年8月号の記事で紹介した 「普通のやつらの上を行け」[3] という文書を書いたLispハッカーです。

ベイジアンフィルタリング

Graham氏によるSPAMメール検出手順は ベイズの定理の考え方にもとづいており ベイジアンフィルタリングと呼ばれています。 ベイズの定理とは、一言でいえば結果から原因を推定する計算手法で、 事象 H1, H2, H3,... のいずれかの原因で 事象Aが得られたとき、 Aが起こった原因が Hi である確率 P(Hi|A) を推定するのに使います。 原因Hiにより事象Aが起こる確率 P(A|Hi)がわかっているとき、 P(Hi|A)は、 P(A|Hi)をもとにして 以下のようにして計算することができます。

P(Hi|A) = P(Hi) * P(A|Hi) / Σj(P(Hj) * P(A|Hj))

例えばあるメッセージに「adult」という単語が含まれていた場合、 SPAMメッセージに「adult」が含まれる確率をPs、 SPAMでないメッセージに「adult」が含まれる確率をPn とすると、 上の式より、 そのメッセージがSPAMかどうか全く情報がない状態では、 そのメッセージがSPAMである確率は Ps / (Ps + Pn) となります。 SPAMらしさを表現する単語をいくつか選択して このような計算を行なうことにより、 メッセージのSPAM度をかなり正確に計算することができるというわけです。 ベイズの定理はこのような条件付き確率を計算するための基本的な計算方法ですが、 このような考え方を拡張したベイズ統計学や、 ニューラルネットに応用したベイジアンネットワークなどが 最近注目されています。

GrahamによるSPAM度判定の手順はおよそ以下のようになっています。

  1. SPAMメールと非SPAMメールを沢山用意し、 単語がSPAMメール中に出現する回数と 非SPAMメールの中に出現する回数を計算しておく。
  2. SPAMかどうか判定したいメッセージに含まれる単語Wが SPAMメールに含まれる割合と 非SPAMメールに含まれる割合を調べることにより、 その単語のSPAM度を計算する。
  3. SPAM度が高い単語と低い単語を15個選択して メッセージのSPAM度を総合判断する

計算例

GrahamによるSPAM度判定計算結果の例を以下に示します。

madam0.99
promotion0.99
republic0.99
shortest0.047225013
mandatory0.047225013
standardization0.07347802
sorry0.08221981
supported0.09019077
people's0.09019077
enter0.9075001
quality0.8921298
organization0.12454646
investment0.8568143
very0.14758544
valuable0.82347786

この結果からメッセージ全体のSPAM度は0.9027となるので これはSPAMと判定されています。 “madam” “promotion” などの単語がSPAM判定に貢献しています。 “republic” のような単語は一見無害に見えますが、 怪しげな国を相手にしたSPAMが非常に多いためSPAM度が高い単語になっています。 こういう傾向は統計的な計算によってはじめてわかるものといえるでしょう。

Grahamのベイジアンフィルタアルゴリズムはこのように単純なものですが、 これだけで、SPAMでないメールを全くSPAMと誤認識することなく、 全SPAMのうち99.5%をSPAMと判定することができたということです。

実装

Grahamのアルゴリズムやその改良版の実装がいくつかネット上で公開されています。 Bogofilter[4] はUnixで動くSPAM判定プログラムで、 SPAMメールの集合と非SPAMメールの集合を使って学習を行なわせることにより SPAM判定を行なうことができるようになっています。 「A Plan for Spam」の訳の公開者であり Lispの方言であるSchemeの実装のひとつであるGaucheの開発者であるKawai Shiro氏は、 Gausheで実装したベイジアンフィルタ「scbayes」[5]を公開していますし、 Rubyでの実装もいくつか公開されています。 ベイジアンフィルタリング機能は最近のMozillaにも実装されています。

SPAMフィルタフィングの将来

Grahamの記事では、 性能の良いSPAMフィルタが浸透すればSPAMが全く有効でなくなるはずであり、 将来はSPAMが商売として成り立たなくなって消滅してしまうという予測が述べられています。 そうなってくれれば非常に嬉しいのですが、 簡単な統計的手法だけではそれは難しいかもしれません。 例えば、督促状の形態をとって金の振込みを要求するSPAMが最近問題になっていましたが、 このようなメールは字面ではなく内容が問題であるため、 統計的な手法だけで本物の請求書と区別することは難しいように思われます。 さらに効果的なSPAMフィルタフィング手法の開発によって SPAMが根絶されることを期待したいと思います。
  1. MicrosoftのSPAMへの取り組み:
    http://www.zdnet.co.jp/news/0304/21/ne00_msresearch.html
  2. A Plan for Spam (和訳):
    http://www.shiro.dreamhost.com/scheme/trans/spam-j.html
  3. 普通の奴等の上を行け (和訳):
    http://www.shiro.dreamhost.com/scheme/trans/beating-the-averages-j.html
  4. Bogofilter:
    http://bogofilter.sourceforge.net/
  5. scbayes:
    http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Gauche:SpamFilter&l=jp
Toshiyuki Masui
[]