Spam Deobfuscation

スパム

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

(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:スパムを通常のメッセージと誤認識する率