spam

メーリングリストを組み合わせることで仮想ユーザを合成する実験方式にあった懸案を除去した。元々のアイデアはハムはメーリングリストから送られてくるメッセージ集合、スパムはハニーポットで収集したものとしている。この場合、ハムにはメーリングリストに固有なヘッダ情報が必ず含まれ、スパムには含まれない。Bayes方式のスパムフィルタがこの点を察知した場合、われわれの実験はわれわれの仮説に有利な結果をもたらしてしまい、正当な評価とはいえない。

そこで、ハムのメッセージ集合から、メーリングリストに固有な情報を含むヘッダを除去して実験することとした。以下のヘッダ以外は無視することとした。

• From: From に moderator が指定するようなメーリングリストは実験データに用いていない。約30,000通のハムについて From の出現頻度分布を精査したが、From に出現するのは、発言をしている個人であることが確認できた。From は利用することとした。
• Mime-Version: スパム検出に役立つとは思えないが、実害はないので残してあるが、個々のメーリングリストごとにこのフィールドは変化しないので、無視した方がいいかもしれない
• Content-Type: 個々のメーリングリストごとにContent-Typeは変化しないような気もするので、このフィールドも無視した方がいいかもしれない
• Content-Transfer-Encoding: われわれの形態素解析器は中国語、ロシア語、韓国語に対応していないため、この情報がない場合には、システムが機能しない。スパムの一定の割合がこれらの言語で書かれており、Bayes方式のスパムフィルタはこれらのEncodingとスパムの関連性を容易に発見することが予想されるが、スパムのうち？？割*1は英語、日本語であることから、この小さなチョンボは許していただきたい。
• Content-Length: スパム検出に役立つとは思えないが、実害はないので残した
• Status: スパム検出に役立つとは思えないが、実害はないので残した

以下が無視したヘッダの代表である(佐藤くんまち)。

• Delivered-To: メーリングリストのサーバ名やその周辺の転送サーバの情報が含まれるため、効果的なハムのサイン
• Subject: [Free-ML: 10001] のように特徴的な場合が多く効果的なハムのサイン*2
• X-Spam-***: 中継サーバが付与するスパム性に関するヘッダ情報。われわれのスパムフィルタとは独立なフィルタの影響を排除する目的で無視することとした。
• Reply-to: メーリングリストのメッセージでは Reply-to がメーリングリストのアドレスになっていることが多く、これが極めてハムのサインとして極めて有効である。

*1：佐藤くん待ち

*2：実は実装上の都合から、Subject に対しては形態素解析をしていない。つまり、記事番号が異なる Subject 同士は異なると認識してしまうので、われわれのスパムフィルタにとっては Subject の内容はスパムの検出に有効ではない。この理由から、このヘッダを残しておいてもよかった。そうした事情を知らない人に対して誤解を招くため、敢てこのヘッダを無視することとした。この措置によるスパム検出率の低下はないものと予想される。

疑問

1. Bayes方式のスパムフィルタを用いて、個人のメッセージを他人のフィルタを用いることの有効性は有効か。
   1. Bayes方式のスパムフィルタでは、通常、単語の出現頻度に関する情報(辞書)を学習する。辞書だけでなく、スパムの判定に用いる閾値も学習できるのではないか。(これは恐らく正しいが実証の必要がある)
   2. 他人の辞書を用いて自分のメッセージをフィルタリングする場合、もし前項が事実であれば、他人の辞書を用いつつ、閾値は学習した方が有効性が高いかもしれない。というか、前回の実験での結果が思わしくなかった原因は、スパムフィルタの基本的な性能が低かったことに加えて、この点についての配慮がなかったためかもしれない。
2. Aの辞書(D_A)を用いてBのメッセージをフィルタリングできるとはどういうことか？
   1. AはD_Aを用いて、メッセージを評価し、評価の指標として閾値t_Aを用いる。Bは、D_Aとt_Aをそのまま用いるよりも、BのためにD_Aを用いてt_Bを学習させた方が効果が高いかもしれない。
3. 多くの人々(P = {A, B, C, …})のスパムフィルタとして利用できそうなフィルタを持っている人物Aが見つかった場合に、共有フィルタはどのように構成すればいいか。
   1. Pたちの辞書を合成して、全員の総意を表すような辞書D_Pを作成し、D_Pを用いて各自が閾値を学習すればいいかもしれない。この時点で、どれだけの人がD_Pを利用できなくなるかという点は興味深い。

協調型Bayse式フィルタのアイデアを実証するための実験

1. 1,000人の仮想ユーザについてスパムフィルタ(=辞書)を生成する。
2. 仮想ユーザのペア(A, B)について相互のフィルタを利用して閾値を学習し、相互のフィルタの利用可能性を調べる。利用可能性としては、自己のフィルタと比較して、ほぼ遜色のないフィルタであれば利用可能と判断できるものとする。
3. 利用可能性に関するグラフ(A が B のフィルタを利用可能なら、A → B)を作成し、それをクラスタリングする。
   1. 本当なら神のクラスタリング*1をすべきだが、とりあえず以下のヒューリスティクスを適用する：前述のグラフにおいて入力次数の最も大きいもの(ボス)を取り出し、そのノードに入力辺を通して隣接するノード(ボスの配下)をグラフから削除する。この作業をグラフが空になるまで繰り返す。
   2. ボスたちの入力次数の大きさ(すなわち配下の人数)をプロット(rank vs. degree)する。直感的には羃分布になると予想される。
4. ボスが率いる配下が小さい場合、ボスが見つからない人についてはそもそも協調型フィルタを提供することの意味が問われるかもしれない。仮にこういうグループを無視したら、全体の性能はどこまで向上するだろうか。(一部の変な人をサポートするために多くの人々が)
   1. 一定のrankより大きなボスたちに対するフィルタの生成を無視すれば、共有フィルタの数を削減することができる。
   2. 無視するrankとその結果、フィルタサービスを利用できなくなるユーザ数の関係(cut-off rank vs. #users)をプロット
   3. 実験用のメッセージ集合を用いて、recall/precisionを計測する。結果をどのように示すのがよいか？*2

今後の予定

1. (実験)協調型フィルタの時系列的な安定性に関する実験
2. 性能劣化の際のフィルタの共有方式の再構成のアルゴリズムの提案および実験(実験はシミュレーションシステムではなく、support 関係の時系列的な変化のデータをもとにできるはず)

*1：要サーベイ

*2：要検討

しばらく前にCEAS 2005の論文概要を二つ紹介しましたが、ようやくそのうちの一方を真面目に読み終えました。隠れマルコフも堂々マルコフも存じあげなかったのですが、基本的なコンセプトは簡単なようです。

• H. Lee and A. Ng, “Spam Deobfuscation using a Hidden Markov Model“

(2月1日: 論文の後半の解説、及び考察の追加)

この研究の目標

スパムメッセージによく現れる難読化された言葉を正しい表記に戻すことが目標です。この問題に面白おかしく取り組んでいるViagraには600,426,974,379,824,381,952のスペルがあるがあります。

インターネットでマーケティングをしている連中はご親切にも薬とかアルファベットを教えることに熱心なものだから、本来は”Viagra”という言葉を熱くて、新しい、ユニークなスペルで寄越しやがる。例えば、本当なら’i'がくるところを’L'で、あるいは’a'がくるところに’@'で書いたりね。

バイアグラを宣伝する80,730種類のメッセージを受け取ってから、思ったんだ。「いったい、Viagraにはどれだけの種類のスペルがあるんだろうってね」

そこで、毎日、受けとるメッセージからViagraのスペルを探し始めたんだ。12日が過ぎて、79も集ったよ。

話をこの論文に戻すと、Viagoreaとか、ViagDrHaとか、V l a g r aとか、VyAGRAとかいったスペルを見て viagra に逆変換することを目標としています。

隠れマルコフモデルで難読化をモデルする

Viagraという語からViagDrHaという難読化された語が生成される仮定を説明します。入力としてアルファベット[A-Za-z]の列をとり、出力として空白を含めた印字可能な文字の列とし、アルファベットを状態とする機械を考えます。

[V; i; a; g; r; a] という入力列を考えましょう。この入力を受けながら、内部状態を[V; i; a; g; r; a]という順に遷移させ、遷移ごとにその状態の文字を出力すれば入力を忠実に出力する機械が実現できます。一方、入力文字を受け取らずに自状態へのε遷移をする機械であれば[V; i; a; g; g; r; r; a]と状態を遷移させることができます。さらに、それぞれの状態で文字に応じてときどき間違った文字を出力させることで “ViagDrHa” という出力が得られます。

論文で提案されている方式では、ここで説明した乱雑な振舞いをいくつかのパラメターで制御される確率変数としてモデルしています。

難読化機構についての調査

既存のスパムのなかの難読化された語に元の語を対応させる情報を与え、それのデータから前述のパラメターの推定を試みています。推定にはわずか160行のスパムメッセージを用いています。当然、このように小さなデータを用いた推定は不可能なのですが、文字の(形状や発音の)類似性*1でモデルを圧縮しています。

難読化された語をもとに戻す

ここまでの処理で隠れマルコフモデルが完成するのですが、目標はこのモデルを用いて出力から入力を予想することです。要は、与えられた出力に対していくつかの入力を想定することができるのですが、それらのうち出力を得る確率を最大化するものを選択するのです。論文には、この具体的な操作については述べられていませんが、A. J. Viterbiのアルゴリズム*2を用いるのが基本のようです。

ただ、Viterbiのアルゴリズムは大きな隠れマルコフモデルに適用すると実行性能が悪くなり、彼らのモデルの場合、状態数が約10,000もあるために、毎秒10文字くらいしか処理できなかったそうです。そこで、高速化のためにbeam search*3を試みたところ約20倍の高速化に成功し毎秒240文字を処理できるようになったとのことです。すごいけれども、実用的には、さらなる高速化が求められますね。

さて、提案されている変換アルゴリズムの性能は素晴しいものです。上で述べたように”viagra”にはたくさんの難読化が存在することが知られていますが、60種類の難読化された”viagra”のうち59個を正確に元に戻したそうです。*4また、849個の難読化語を含む606行のスパムメッセージを変換したところ、約95%の語を正確に元に戻したそうです。これだけ難読化語が元の語に戻されれば、メッセージの内容を見るスパムフィルタ*5が正確にスパム性を見抜くことができることでしょう。

Out-of-dictionary HMM

前節までの技術は(難読化される前の)メッセージに現れる語がすべて辞書に含まれることを仮定していました。実際のメッセージのなかには辞書に含まれない語 (out-of-dictionary words) も数多く現れます。たとえば、この文章のなかでも HMM や Bayes などは普通の辞書には現れないことでしょう。こういった語に対応するために、前節で構成したモデルを拡張して [a-z]+ を受理可能なように拡張する方法 (out-of-dictionary HMM) が提案されています。この拡張はすでに10,000もある状態数に26個の状態を加えるだけの簡単なものです。

OOD HMMを実験したところ、難読化された語を辞書に含まれない正規な語(OOD語)と認識する率が若干高まり、結果として難読化された語を元に戻す精度は低下するのですが、OOD語をOODとして正しく認識する率が約50%まで高まります(明確には述べられていませんが、当初の提案ではこの率はほとんど0%なのでしょう)。

OOD機能がないと “panasonic” が “pan sonic”、”palomino” が “palming” と誤認識されるそうです。

難読化されたメッセージの発見

メッセージが難読化されているということは、即ちそのメッセージがスパムだと考えていいでしょう。そこで、各メッセージについて4つの特徴量(語内の記号数、語長の平均、辞書に含まれない語の数、語数)を用いてメッセージのスパム性を判定することを試みたものの false positive*6 = 8%、false negative*7 = 22%とあまりよい結果は得られなかったそうです。残念ながら、ここでの実験の詳細は論文で明らかになっていません。

この実験結果はさらに改善できるかもしれませんが、この方法でスパムフィルタするよりは、難読化されたメッセージを元に戻した上で、Bayes法のような内容を検査するスパムフィルタに任せるのが妥当なのでしょう。

感想

隠れマルコフモデルというものがどんなものかなんとなく分ったのが嬉しいです。実際の問題を隠れマルコフ過程としてモデルするためのテクニックが丁寧に説明してあるのでとても参考になります。隠れマルコフモデルの出力から入力を推定する技術については、Viterbiを見ればよさそうです。見通しがよくなりました。また、Viterbiのアルゴリズムを高速化するbeam searchも面白そうです。

すでに述べましたが、このアルゴリズムが今すぐにも実用できるかというと残念ながら難しいでしょう。たとえば、私のところには一日にスパムを含めて300通程度のメッセージが届いていると思うのですが、それぞれが約1,000文字を含むとすれば、一日に300,000文字を処理しなくてはならず、240文字/sでは1,250秒=20分もかかります。処理の内容に比べると処理時間が多すぎるという印象です。ぼくらは一台のパソコンで100,000人をホスティングするスパムフィルタを開発していますが、この場合、20分*100,000=2,000,000分=1388日となり、千個以上のCPUを使ってこの処理をしなくてはならないというのはあまりにも悲しいです。あと数百倍の高速化が求められることでしょう。こういうニーズを掘り起こせば、よい研究テーマになるかもしれません。

あるいは、多段スパムフィルタのなかの最終段階で用いることを検討してもいいかもしれません。つまり、通常のスパムフィルタは実用性から false positive を削減するために、false negative が高目に設定されています。つまり、スパムフィルタを通しても若干のスパムが紛れ込んでしまいます。これらのメッセージに対して、難読化に関する判定結果をメッセージに埋め込み、メールソフトでの振り分けに利用してもらうのです。私の場合、通常のメッセージの10倍以上のスパムが届くのですが、それらの大部分を粗いフィルタで除去し、残った少数について、ここで提案されている精密な仕組みを通すことによって、より微妙な判定が求められているものに対して限定的に高コストな処理を施すのです。それにしても、あと10?100倍くらいの高速化は必要でしょうが。

*1：文字の類似性については(1)文字の同一性、手書き文字認識で用いられる類似性 (Shape Context Similarity), ピクセル単位の類似性、発音の類似性、空白／区切り記号としての類似性を用いています

*2：A. J. Viterbi, "Error bounds for convolutional codes and an asymtotically optimum decoding algorithm," in IEEE Transactions on Information Theory 13(2): pp. 260-267, 1967. 暗号解読の論文だろうか？

*3：F. Jelinek, "Statistical Methods for Speech Recognition," MIT Press, 1999.

*4：ちなみに、元に戻らなかったのは "viaverga"で、それは"via verge"に変換されてしまったそうです。

*5：代表的なのがBayesスパムフィルタ

*6：通常のメッセージをスパムと誤認識する率。実用的なシステムでは、false positive を限りなく 0% にしなくてはならない

*7：スパムを通常のメッセージと誤認識する率

昨日に続いて、スパムに関する国際会議の論文を紹介します。今日は、2005年の国際会議で発表された論文集から5件を選んでみました。論文概要はしっかりと読み、内容はパラパラとみくった程度ですから、詳細については踏み込みません。今日、紹介するのは以下の2件です。

• H. Lee and A. Ng, “Spam Deobfuscation using a Hidden Markov Model“

• J. Kong, P. Boykin, B. Rezaei, N. Sarshar, V. Roychowdhury, “Scalable and Reliable Collaborative Spam Filters: Harnessing the Global Social Email Networks“

H. Lee and A. Ng, “Spam Deobfuscation using a Hidden Markov Model“

Obfuscate*1という言葉を始めて知りました。例として”viagra”を”vigra”と、また”mortgage*2“を”m0rt gage”と書いたものが示されています。この論文が目標としているdeobfuscationとは、コンピュータの自然言語処理を混乱させる目的でわざとスペルを分りにくくした語がスパムメッセージに現れるわけですが、それを人間が読み取るであろう本来の語に戻す操作のようです。適切な訳ではないと思いますが、以後、obfuscation = 難読化、deobfuscation = 明瞭化と訳すことにしましょう。この論文では、明瞭化に隠れMarkovモデルを応用しているようです。

当然のことながら難読化はメッセージの内容に応じたフィルタにとっては脅威となります。従来の難読化への対抗策は(1)SPAMパターンに正規を利用したもの*3、(2)文字列の編集距離を利用したもの*4や辞書編集距離*5を利用したものがあるそうですが、いずれも実行時のコストが大きかったり、難読化の手口が変更されるにつれて距離の定義の保守が困難になる問題を抱えているようです。このことは、かつてNaive Bayes方式が提案される前に、手作業でSPAMパターンを保守していた事情に似ているのかもしれません。

この論文では、今後、出現する難読化の方式がMarkovモデル過程であると仮定し、それを予想する方式を提案しています。

隠れマルコフ過程を理解していないので、理論の部分はざっくりと読み飛ばし、評価を眺めてみるとなかなかの結果です。まず、viagraを難読化したバリエーションを60用意したところ、そのうちの59を元のviagraに明瞭化できたそうです。*6また、606行のスパムメッセージに出現する849の難読化された語について調査したところ、約95%を明瞭化できたそうです。

以下が実際に実験に用いた難読化されたメッセージの一部です。

hello dear home owpyner,

we h;avve been n3otifie!d that you!r mo>rtglage rate

is fi>xegvd avqt a very hivgh in tevrest rate.

therefor%e you arge current overpapying,

which s:ums-up to t‘housxarn ds oabf dolltyrars annuallly .

l:uckily fafor you wtce cuqan gqjufuarantee

th’e lowest rates in thkhe u.s. (3.50%).

so huzmrry beqcause the rate f:orecast is npot looking goo d!

there iws no obligations, ahsnd iwt free

lock ostn the 3.50*%, even with baiwd cr’ezsdit!!

cx6lick h’ere nepow for details

これを提案されたプロトタイプは以下のように変換します。いかがです？

hello dear homeowner

we have been notified that your mortgage rate

is fixed data very high interest rate

therefore you are current overpaying

which sums up to thousands of dollars annually

luckily for you the cuban guarantee

the lowest rates in the us

so hurry because the rate forecast is not looking good

there is no obligations and it free

lockout the even with baird credit

click here new for details

論文には、上で紹介したのとは別の手法も提案されています。実際にやりとりされている正規のメッセージにも辞書に含まれない語が使われていることがままあります。そうした語が、誤って明瞭化を経て本来とは別の語に変換されると困ります。これへの対処策を提案しています。内容は読んでいませんが、明瞭化においてはこういった視点から評価することも重要なのですね。かなり面白い論文のようです。

J. Kong, P. Boykin, B. Rezaei, N. Sarshar, V. Roychowdhury, “Scalable and Reliable Collaborative Spam Filters: Harnessing the Global Social Email Networks“

協調フィルタリングによってスパムを効率的に排除する提案は以前からあります。協調フィルタリングとは、大勢のユーザから収集した評判情報を利用して大量にやってくる情報から各個人に有益なもののみを抽出する方法です。GroupLensを搭載したニュースシステムが有名なのですが、このシステムでは各自がニュース記事を評価することができます。diggのようなものと思えばよいでしょう。評価結果に対して解析をすることで、嗜好の類似した人の集りを見つけることができます。それらの人の間では互いに相手が下した評判の結果を信頼することで、各自が好みそうなニュース記事のみを目にすることができるようになります。

協調フィルタリングは80年代に提案されており、この論文でも協調フィルタリングの方式を提案しているわけではありません。この論文のテーマは世界中に広がる人々のあいだで評判情報を効率的に共有する方法を提案しています。CEAS 2004にはGrayとHaahrがP2Pネットワークを用いてこの問題を解決する試みが提案されていました。この論文では、P2Pのような特殊なネットワークではなく受信したメッセージの評判情報を取得するために電子メールシステムを利用することに特色があります。*7また、電子メールのトラフィックがスケールフリーであることを利用して、評判情報が理論的に効率よく収集できることを示しているようです。最後に、この提案をシミュレーションによって示しています。やたらにイントロが長い論文で本文は全く読んでいません。

5件を紹介するつもりでしたが、今日は疲れたのでここまで。以下はまたの機会にします。ではでは。

• J. Hovold, “Naive Bayes Spam Filtering Using Word-Position-Based Attributes“

• D. Lowd, C. Meek, “Good Word Attacks on Statistical Spam Filters “

• K. Albrecht, N. Burri, and R. Wattenhofer, “Spamato – An Extendable Spam Filter System“

*1：ぼかす、分かりにくくする、（意図的に）混乱させる

*2：抵当権、担保、貸付金、住宅ローン

*3：CMOScript

*4：[Ristad and Yianilos, 1997]

*5：Oliver, 2005]

*6：すばらしい！

*7：なんと大胆な！

Conference on Email and Anti-Spamのなかから、面白そうな論文を学生さんにピックアップしてもらったので、アブストラクトを眺めながらまとめてみました。

I. Rigoutsos & T. Huynh: “Chung-Kwei: A pattern-discovery-based system for the automatic identification of unsolicited e-mail messages“

IBM Researchの SpamGuru システムの一部に採用されている Chung-Kwei というスパムフィルターの内部についての解説。著者らは生命科学のデータマイニングの手法であるTeiresiasパターン発見アルゴリズムを基本にしているらしい。まずTeiresiasパターン発見アルゴリズムをSPAMメッセージの集合(SPAM集合)に適用し、SPAM集合に繰り返し発生するパターンを発見する。つぎに、受信メッセージに対してパターンを適用しSPAMを発見する。

フィルタの処理性能は214メッセージ/秒(2.2GHz Intel-Pentium)とかなり遅いが、false negative = 3.44%, false positive =0.066% というのはよい。

T. Mayer and B. Whateley, “SpamBayes: Effective open-source, Bayesian based, email classification system“

SpamBayesフィルタで採用されている、「不明」メッセージの仕掛けについての解説。SpamBayesは、受信メッセージをHam, Spam, 不明の三種に分類することで性能を改善しているらしい。要するに三値論理を導入したらしい。なるほど。

関連研究の紹介では、Grahamによる最初の提案に続き、その問題点、Robinsonによる改善がわかりやすく解説されている。なかなかよいレビュー。

E. Michelakis, I. Androutsopoulos, G. Paliouras, G. Sakkis, and P. Stamatopoulow, “Filtron: A learning-based anti-Spam filter“

Wekaというオープンソースな機械学習基盤を利用して実装された学習型のスパムフィルタの報告。詳細はアブストラクトやイントロからは不明。さまざまな学習法を比較調査したということだろうか？？？

Naive Bayes, Flexible Bayes, LogitBoost, SVM (Smart Vector Machine) について vitro 評価と vivo 評価を行っている。評価には、公開コーパスを用いている。こういうコーパスが存在するんですね。ギリシア語かもしれないけど、うちのシステムで大丈夫だろうか？？

この論文で引用されている著者らのテクニカルレポート (52 pages)が詳しいだろう。

A. Gray and M. Haahr, “Personalised, collaborative filtering“

スパムフィルタの主流はメッセージの内容をもとに判断する方法だが、この論文では（今では、こちらもひとつの主流である）協調フィルタリングを提案し、実装している。内容にもとづく協調型フィルタリングを提案しているわれわれにとってのライバルといえるかも知れない。

協調フィルタでは、ある個人が受け取ったメッセージをスパムと判断した場合に、そのメッセージの特徴(signature)を彼と同様の判断を下しそうな人に伝える必要がある。このために、この著者らが提案するのはP2Pフィルタリングネットワークです。かなり、びっくり！具体的にスパムの判断が類似する人々がどのようにP2Pネットワークを組むのかについては論文を子細に読まなくてはならないだろう。もしかすると、われわれのプロファイルの共有方式にも応用できるかもしれない。評価結果を読むのが楽しみだが、検証を行っているのは小さな系(5ノード)での小規模(総メッセージ数 < 10,000)な実験にとどまっているのが残念。一応、おおまかな結果をまとめると false positive = [0.36,1.44], false negative = [0.00, 5.61]。false positive が大きすぎるかな。