このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

はじめに

 この文書は[a11]Flavio D. Garcia, Jaap-Henk Hoepman, Jeroen van Nieuwenhuizen. SPAM FILTER ANALYSIS. http://citeseer.ist.psu.edu/644060.html , 2004.を日本語訳したものです。

分析の方法

 目標は現実にありえるメールトラフィックパターンを用いて、いくつかのスパムフィルターテクニックを適用して、効率的に働くかどうかということです。これは、ISPレベルとユーザーレベルの両方でみていきます。このトラフィックは、異なるユーザーが異なるトラフィックパターンを持つ異なるコンテンツのメールが使っている事実を反映すべきです。理想的な状況としては、実際のメールトラフィックを計算したいわけです。しかし、プライバシーの観点から、それは実行不可能といえます。自分だけで環境で同様の実験を行ったとしてもメールの送受信規模が小さく、ユーザーレベルの調査はともかく、ISPレベルの調査としてはうまく機能しません。そこで、普通のメールとスパムメールをシミュレータで生成することにより、分析します。そして、分析したスパムフィルターごとの正確なレベルを測定します。

分析のメカニズム

 分析の狙いは、スパムがエンドユーザーに配達されないようにするために、どのスパムフィルターが効果的かどうかを特定することです。

 まず、フィルタリングの結果を次のように表記することにします。これはゲーム理論による分析のところでも登場した表記とほぼ同じ同じです。なお、SはSpam(スパム)、HはHum(非スパム)を意味します。

S→Sスパムを正しくスパムと判別
S→Hスパムを誤って非スパムと判別
H→S非スパムを誤ってスパムと判別
H→H非スパムを正しく非スパムと判別

 フィルターにnつのメッセージを入力して、スパムとして判別された数をn_S、非スパムとして判別された数をn_Hとします。また、S→Sになった数をn_S→Sとします。他のS→H、H→S、H→Hも同様に考えます。

(数式)bunseki.bmp

 すべてのメッセージをブロックすることで、FARは人工的にゼロに減少させることができます。そうすると、FRRは増加します。

 同様の議論で、すべてのメッセージを通過させることで、FRRを人工的にゼロに減少させることができます。そうすると、FARは増加します。

 受諾(accept)率と拒否(reject)率というひとつのスカラー値によって、表現することで、スパムフィルターの実行をランク付けしたいわけです。

 まず最初に、FAR/FRRの値をプロットしていくとき、元からどのくらい離れているかということの指標として、スパムフィルターのwrongness「W」を定義します。しかし、これらのエラーを対照的なものとは考えません。エラーとしてfalse positiveを考えることができ、効果的な指標としてfalse negativeを考えることができます。このアプローチに対する別の方法は、FARを十分に減少させるためにFRRを少し増やすことを許容するということです。それでは、Wの関数を次に示す。ただし、εは小さい値で、例えばε=0.1です。

(数式)w.bmp

 このWの関数を見てわかると思いますが、入力としてFAR値とFRR値をとります。出力では、FAR値よりFRR値のほうが影響を大きいことを意味します。

普通のメールトラフィックのモデル化

 シミュレータはフィルターのテストのために、普通のユーザーの振る舞いを正確にエミュレートして、メールトラフィックを生成する必要があります。そのためには、メールの中身のコンテンツと普通のメールのトラフィックパターンを生成する効果的な方法を知らなければなりません。理想をいえば、メッセージの中身は異なる人たちから借りた本当のメールの中身を使うべきです。しかし、プライバシーの観点からこれは無理と考えています。その代わりに、USENET(news)メッセージの本文を使うことにしました。件名と語彙の集合に偏りが生じることを避けるために、あらゆるジャンルから選び出してくることにします。しかし、USENETメッセージはHTMLコードを含みません。これがスパムのフィルタリングに与えるは少々あります。

 モデル化でひとつ重要なことがあります。異なる人によって送られたメッセージの中身は違うという事実です。語彙力とは、職業、教養、趣味などによって変わってきます。モデルにこれを反映させるために、メールの送信者はそれぞれランダムに選んだ特定のトピックグループに所属します。互いのトピックグループということは、特定のnewsグループからメール本文を単純に持ってくることにします。

 もうひとつ重要なことがあります。大抵は知り合いからメールを受け取るという事実です。この振る舞いをモデル化するために、送信者と受信者がなるべく知り合いで、その間のメールをエミュレートしました。

 メーリングリストは特別なケースと考えられます。なぜなら、いくつかの側面の中で、スパマーのように振舞ってしまうこともあります。多くの異なるユーザーに同じメールを送ります。だから、この振る舞いはいくつかのフィルターを混乱させてしまいます。

 このモデルでは、各メーリングリストは、最初からメールアドレスのリストを持つように設定します。メーリングシステムのメール送信は、同じメッセージを全ユーザーに送るまで繰り返されます。メーリングシステムのメール送信が終わると、他のメッセージが選択され、プロセスが再スタートします。

スパムトラフィックのモデル化

 現実に近いスパムメールトラフィックを生成するため、バルクメーラーの振る舞いを分析して、それをモデルに反映しなければなりません。バルクメーラーを起動してメールを送り始めると、それは終わらせるまであるいは目的のターゲットリスト全員に送信するまでずっと送り続けられます。

 また、スパムトラフィックを生成するとき、報告されているスパムの割合を活用します。インターネット上のメールトラフィックにおけるスパムの割合は年々増加しています。具体的な統計データについては別項で解説しています。

 このスパムのモデルでは、それぞれのスパマーはメールアドレスのデータベース(リスト)を持っています。スパマーは送信し始めるとき、可能な限り早く送信し、データベース全員に送るまで続きます。スパマーは、私的に特定の人だけにスパムを送信することもできます。この場合、それぞれのスパムメッセージはひとつだけのターゲットのメールアドレスを持ちます。このモデルでは、メールアドレスは「login@server」、「Dear login」という行を含む本文とします。

 スパムメールを生成するためにスパムメッセージの本文のサンプルが必要です。そこで、[a15]から異なるメッセージを選びます。そして、スパムフィルタのテクニックにスパムの進化のインパクトを見せるために、最近のスパムメッセージを収集したものを含むケースも別に考えることにします。

シミュレータ

 シミュレータは現実のような普通のメールのトラフィックとバルクメールのトラフィックのパターンを生成しなければなりません。目的を達成するために、可能な限り現実世界のようにシミュレートすべきです。それによって、フィルターの効果をきちんとみていくわけです。

 バルクメーラーの新しい特徴を簡単に通過しやすいように設計しておきます。同様にフィルターの種類、フィルターのパラメータの設定を簡単にできるようにしておきます。

 そこで、次のようなシミュレータを考えます(図1参照)。

(図1)sim.bmp ←シミュレータのデザイン([a11]から抜粋)

トラフィック生成器

 まず第一にトラフィック生成器があります。これはメインモジュールです。メールトラフィックを生成する機能を持ちます。トラフィック生成器は送信者と受信者の集合を持っています。それぞれの送信者は、シミュレーションの1ステップごとにメールを送る確率を持ちます。トラフィック生成器はラウンドロビン方式で、送信者の集合を取り替えます。

 普通のユーザーである送信者が選ばれたなら、トラフィック生成器は最初にメールターゲットの数を生成します。つまり、Toヘッダ、CCヘッダ、BCCヘッダを指定するわけです。そして、受信者を選択します。受信者を選択するために、送信者リストの中からそう心者のインデックスを最初に取り出し、それから標準的な分類に使うオフセットを生成します。つまり、「インデックス+オフセット」で受信者を指定するというわけです。生成されたインデックスとより親しい人のインデックス間の違いは、赤の他人の送信者との違いより小さいはずです。

 スパマーである送信者が選ばれたなら、スパマーでない場合の送信する状況を変えます。そして、それはスパムメッセージがデータベースに載っている全員に配達されるまで、送り続けられます。

 メーリングリストのケースでは、ターゲットはデータベースから選択されるという事実を除外して、普通のユーザーのように振舞います。そして、同じ内容をデータベース全員に対して送ります。

wrapper

 2番目の部分はwrapper(ラッパー)です。これは標準的な入力においてメールを受け取るプログラムです。そして、フィルターを動かす機能を持ちます。

 そして、スパムまたは非スパムの分類を行い、トラフィック生成器へ返答します。もし、フィルターがサーバーレベルならトラフィック生成器は(エミュレートされた)ログファイルに対して、いつもシミュレートされたコネクションを記録します。そのうえ、このファイルはwrapperにアクセスできます。

 なお、それぞれのフィルターは入力書式が異なるかもしれません。だから、wrapperプログラムは特定のフィルターです。

トレーナー

 3番目の部分はトレーナーです。例えばベイジアンフィルターなどは当然ながら本格的にフィルタリングする前に学習段階が必要です。

 ところで、各ユーザーに到着したメールトラフィックは異なるパターンを持ちます。シミュレータは正しくトラフィックを分類するほどの確かな量を生成できます。それを2つの異なるファイルに送ります。ひとつはスパム、もうひとつは非スパムです。その後、トレーナーは実行され、このデータと共にフィルターを学習させることができるようにすべきです。

フィルターの分析

 実験対象のフィルターを選別します。次に示すよく知られているスパムフィルターについて調べます。

トラフィックベースフィルター

  • Mail volume-based filter

コンテンツベースフィルター

  • DCC(Distributed Checksum Clearing house)
  • Geneticアルゴリズムベースフィルター→SpamAssassin
  • ナイーブベイジアンフィルター→Bogofilter,Spamprove,Bmf

スパムフィルターの比較

 いくつかのグラフと表で、性質上の結果をみることができます。

 表はユーザーレベルとサーバーレベルの両方共におけるフィルターのパフォーマンスを含んでいます。フィルターのパフォーマンスがレベルに依存しないなら、「U/S」と記しています。

 ベイジアンフィルターをサーバーレベルで動かしたケースでは、それはユーザーごとの学習を得られないが、一般の学習を得ることがdけいる。

 次に、各々の表をします(図2、図3、図4参照)。

(図2)sim2.bmp ←表1([a11]) (図3)sim3.bmp ←表2([a11]) (図4)sim4.bmp ←表3([a11])

 表1は私的なスパムを行わないときのシミュレーション結果です。

 表2は私的なスパムが行われたときのシミュレーション結果です。この場合のフィルターはユーザーレベルで実行したときのみテストされています。

 表3は私的なスパムが行われていないときのものですが、しかしこのときスパムメールは新しいスパムテクニックのインパクトを示しています。新しいスパムテクニックとは、メッセージの中にランダムな単語を含むような手口です。このスパムのアプローチがされたとしても、特にベイジアンフィルターの場合は効果的に働いていることがわかります。それはほとんどFRR=0となっているからです。FRRはn_H→S/n_Hなので、非スパムを誤ってスパムとして識別する数が圧倒的に少ないということを意味しています。これはメール受信者にとってスパム対策がうまくできていることを表します。

 各フィルターのパフォーマンスはFigure2〜4のグラフで示されています(図5参照)。

(図5)sim5.bmp ←パフォーマンスを示すグラフ([a11])

Mail volume-based filter

 これは最新のコネクションの間において、特定ホストからどのくらいのメールが送られてくるかをチェックするアルゴリズムを使っています。これはシミュレーションにおいてログファイルから最新の15のラインを取ります。この方式はKai's Spamsieldによって使われている方法と同じです。

 あるしきい値より多くメールの量を受け取ると、メールはスパムとして識別されます。しきい値を十分高くしておけば、このフィルターはすべての正当なメールを正しく判別できます。

 このフィルターの欠点は一般にFARがとても高いということです。

 スパマーが私的なスパムを行うときには、このフィルターは有効です。これは別の影響を持つと考えられます。なぜなら、バルクメーラーの仕様上大多数にメールを送ることを目的に作られているため、より多くの接続を確立しなければなりません。これならメールの量から明らかにスパムだと判別できるわけです。しかし、スパマーは複数のオープンリレーを使えば、この種のフィルターによるスパム判定を避けることができてしまいます。

DCC(Distributed Checksum Clearing house)

 テストに使ったフィルターは標準的なDCCフィルターバージョン1.2.14を修正したものです。インターネットサーバーへ報告する機能を停止するように修正しました。その代わりに、ローカルデータベースを使い、フィルターはこのデータベースへメールのレポートを送ります。

 DCCフィルターのfalse positiveの割合は小さいことがわかります。しかし、スパムをフィルタリングするパフォーマンスも同様に小さくなってしまっています。これを防ぐには、しきい値をもう少し控えめにすればよいわけですが、今度はFRRに直接影響を与えてしまいます。

 私的なスパムの場合は、このフィルターの正確さはわずかに低下します。

Geneticアルゴリズムベースフィルター

 ここではSpamAssasin バージョン2.60を使いました。それをデフォルト設定のまま使用します。

 このフィルターはとてもよいフィルタリングをします。

 データを見るとわかるように、私的なスパムを行わないとき、ISPレベルのフィルターとしてもっともよいパフォーマンス結果を残しています。また、私的スパムが行われたときでも、フィルタリングの正確さはあまり変化していません。

 このフィルターの欠点は、ISPレベルではなくユーザーレベルで使うにはFAR、FRRの値が少し大きすぎるという点です。

ナイーブベイジアンフィルター

 ベイジアンフィルター自体はそこそこの正確さを持っています。

 ベイジアンフィルターの種類によって、パフォーマンスの違いも異なります。ユーザーレベルのときはBogofilterが一番よいパフォーマンスを示します。ほとんどfalse positiveがなく、どのシミュレーションのケースでもスパムの75%以上はフィルタリングできています。BogofilterはRobinson方式を採用しています。

 BmfはBogofilterと比較してとてもよいパフォーマンスを持ちます。しかし、状況によってパフォーマンスがまちまちで、控えめさがなくなってしまっています。それはフィルターを評価するFARをもっとも低く達成しています。しかし、いくつかの状況ではfalse positiveの数は高くなってしまっています。

 Spamproveは他のベイジアンフィルターと比較すると効果が低い結果になっています。これはSpamproveがHTMLコードを無視しているからではないかと推測されます。

 ベイジアンフィルターの共通する特徴は、ISPレベルで動かしたときは必ずユーザーレベルで動かしたときよりもパフォーマンスが落ちているということです。

 もうひとつの共通する特徴は、間違えて判別された大半のメールの本文がとても短いということがあります。これは統計的分析を実行するための情報が十分でなく、うまくフィルタリングのときに反映できていないと推測しています。

 私的スパムのときであっても、ベイジアンフィルターの正確さはあまり落ちていません。なぜなら、メッセージの本文の中に「login」のようなキーワードがスパムを示す単語として登録されるという事実に関係があると推測できます。

結論

ISPレベルでのフィルタリング

 ISPレベルでのフィルタリングでもっとも効果的な方法は、geneticアルゴリズムベースフィルターを使うということです。しかし、特定のオプションを利用するとき、それは大きい量のプロセスツリーを必要としてしまします。なぜなら、十分高いしきい値の間で、それらはfalse rejectを与えず安価であるから、それのパフォーマンスが低いとき、メール量に基づくフィルターは防衛の最初のラインを確立します。

ユーザーレベルでのフィルタリング

 ユーザーレベルでのフィルタリングでもっともよい方法は、BogofilterのようなFisher方式のナイーブベイジアンフィルターを使うことです。ユーザーがメールを自由にすることがどのくらい重大かに依存します。Bmfもよいオプションとして考えられます。