界面骇客日记(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
[]