CEAS 2005
昨日に続いて、スパムに関する国際会議の論文を紹介します。今日は、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件を紹介するつもりでしたが、今日は疲れたのでここまで。以下はまたの機会にします。ではでは。
- D. Lowd, C. Meek, "Good Word Attacks on Statistical Spam Filters "
- K. Albrecht, N. Burri, and R. Wattenhofer, "Spamato - An Extendable Spam Filter System"
