Radium Software Development

HOME - ARCHIVE - ABOUT - RSS

Enron Email Corpus

2006-11-02

先日, Microsoft Research において公開された技術レポート "Addressing Email Loss with SureMail: Measurement, Design, and Evaluation" [Agarwal] は,インターネット上でやりとりされるメールのうち約 1% はただ理由もなく消失しているという研究結果を提示している。この話題は各方面においてニュースとして取り上げられ [InternetWatch] ,広く人々の注目を集めることとなった。

この研究においては,実験用の素材としてエンロン社のメール集 ― いわゆる「エンロン・コーパス」 (Enron corpus) が用いられている。ここで言うエンロン社とは,言うまでもなく,不正会計事件で有名な,あのエンロン社 [Wikipedia] である。この事件に関してエンロン社の内部調査を行った連邦エネルギー規制委員会 (Federal Energy Regulatory Commission; FERC) は,調査の際に押収した約 150 万件のメールの全てをウェブ上で公開するという大胆な行為に及んだ。この辺りの経緯とメールの内容については Tim Grieve による salon.com の記事に詳しい [Salon] 。

社内メールの全てを公に晒すという行為は,事件に関して真実を知る権利が公衆にあるとする FERC の見解から導かれたものであるが,それらのメールの全てが必ずしも事件と関連性を持っているわけではない。その中にはごく個人的な内容のものも含まれれば,社会保障番号 (Social Security Number) やクレジットカード番号などを記載したものも含まれている。さすがに後者のように個人に対して著しく損害を及ぼす可能性のあるものは削除が行われたが,前者のようなものについては多くが今もそのままに保たれている。

FERC が事件に関連するメールのみを抽出して公開するのではなく,すべてのメールを一緒くたに公開したことは,メールの自動処理を研究のテーマとしている人々にとって重要な意味を与えることになる。このコーパスを入手することは,中規模の企業の日常業務においてやりとりされているメールの「生きたサンプル」を大量に入手することを意味している。このような「生きたサンプル」は,機密保持の観点から言って,滅多に入手できるものではない。もし仮に,企業の協力によって本物のデータに触れる機会に恵まれたとしても,「できるだけ他者による追試の可能性を残すべきである」という思想に基づけば,あまり好ましい選択であるとは言えない。その点,エンロン・コーパスであれば,誰でも同じものを公に入手することができるという安心感がある。

エンロン・コーパスとその応用例については Ryan Singel による Hotwired の記事が簡潔にまとめられており面白い [Hotwired] 。

現在,エンロン・コーパスを配布しているサイトは幾つか存在する。カーネギーメロン大は William Cohen のサイトにおいて配布されているデータセットは,それらの中でも引用元として参照される頻度の最も高いものとして挙げられる [Cohen] 。このデータセットは,オリジナルのデータセットから問題のあるメールや「ゴミ」を取り除いた状態に整理されており,約 50 万件のメールを含んでいる。その配布パッケージは圧縮された状態で約 400MB にも及ぶ。

これよりも小さめのデータセットが望まれる場合は,マサチューセッツ大(アムハースト校)は Ron Bekkerman らが抽出した約2万件のメールからなるデータセットが役立つかもしれない [Bekkerman] 。このデータセットは Bekkerman らが自身の研究のために作成したものであり,オリジナルのコーパスの中でも特に件数の多い7人のユーザーに限定して抽出を行ったとされている。

同じくマサチューセッツ大の Andrés Corrada-Emmanuel は, Cohen のデータセットにおける MD5 ダイジェストからファイルパスへのマッピングを作成し公開している [Corrada-Emmanuel] 。その他にも, MD5 ダイジェストから送信者名へのマッピングや, MD5 ダイジェストから受信者名へのマッピング,これらのマッピングを利用した Python スクリプトのサンプルなど,分析を行う際に役立つユーティリティの類を公開している。

CAPTCHA

2006-11-07

061107_0.jpg
Image from MSN Hotmail

CAPTCHA とは

"CAPTCHA" とは,人間とコンピュータを自動的に区別する方法の総称で,カーネギーメロン大学の商標である [CAPTCHA] 。一般には上の画像のような「歪んだ文字列」のイメージで知られている。ただし,このような「歪んだ文字列」はあくまでも CAPTCHA の一種に過ぎず,他に画像を用いる方式や,音声を用いる方式など,多様な CAPTCHA が存在している。

逆チューリングテスト

CAPTCHA という語は "Completely Automated Public Turing Test to Tell Computers and Humans Apart" を略したもので,「コンピュータと人間を区別する完全自動化されたチューリングテスト」のうち「コードとデータが公開されたもの」を特定して表している。ここで言う「チューリングテスト」とは,いわゆる「逆チューリングテスト」のことを指しており,一般の「チューリングテスト」が人間による判断を基準としているのに対して, CAPTCHA はコンピュータが自動的に判断を行う方法を対象としている。

ここでは特に CAPTCHA の "P" ― すなわち "Public" に込められた意味に注目したい。完全な CAPTCHA はそのアルゴリズムとデータベースが公知であってもなお有効でなくてはならない。安全な暗号技術はそのアルゴリズムが公知であっても安全である(ケルクホフスの原理 [Wikipedia])のと同じ理屈であると考えてよい。逆に言えば,一見「コンピュータには難しい作業」のように思えても,それを生成するコードとデータを入手してしまえば簡単に対処できてしまうようなものでは,それは完全な CAPTCHA であるとは言えない。

PIX の堅牢性

この考えに基づく限りでは,単純な PIX は比較的脆弱な CAPTCHA であると言わざるを得ない。 PIX とは画像を利用した CAPTCHA の一種で,一連の画像を提示した上でそれらに共通するテーマを推察させるというものである [CMU] 。本来,このように比較的高度な認知が必要とされる作業は,コンピュータにとって非常に困難な問題となるはずだが,その難しさは元となる画像のデータベースが秘匿されていて始めて成立するものである。ひとたびそのデータベースが手に入ってしまえば,高度な認知など行わなくても,簡単な画像のマッチングのみで問題を突破することが可能となってしまう。

061107_1.jpg
Image from CMU ESP-PIX site

PIX が十分な CAPTCHA となるには,ランダムに画像を歪ませる,あるいはノイズを混ぜる等して,自動的なマッチングを適用しにくい形にしなくてはならない。しかしそれも度が過ぎれば,人間にとってみても解決の難しい問題となってしまう可能性がある。結局のところ,この辺りのジレンマは「歪んだ文字列」の場合とさほど変わりが無いとも言える。

CAPTCHA の思想

CAPTCHA の提唱者である Luis von Ahn らが主張することのひとつに, CAPTCHA がもたらすであろう人工知能 (AI) 技術の発展への寄与が挙げられる。氏らは, CAPTCHA がセキュリティの一種として用いられるようになれば,これを破ろうとする勢力と,それを防ごうとする勢力の両方が生じるだろうと予測する。その二つの勢力がせめぎ合うことによって,その手法の堅牢性は増していくことになる ― ちょうど暗号化技術がそうであったように。

CAPTCHA における堅牢性とは,その CAPTCHA が基としている問題(例えば PIX の場合であれば画像認識問題)が,解決不可能な問題 (hard problem) に属していることによって成立すると考えられる。これを破るには,その問題が実は解決可能であることを提示すればよい。だがこの行為は, CAPCHA の堅牢性を否定するというネガティブな効果をもたらすと同時に,これまで解決不可能であった問題を解決可能にするというポジティブな効果をももたらすと考えられる。

つまるところ, Ahn らにとって「いたちごっこ」は織り込み済みなのであろう。それを「守る側」と「破る側」の間に生じる win-win の関係こそが, CAPTCHA の真の狙いであるのかもしれない。

Breaking Visual CAPTCHAs

2006-11-08

CAPTCHA には様々な方式が存在するが,なかでも「歪んだ文字列」を表示しそれを入力させるという方式は,スパム行為を防止するための仕組みとして広く用いられている。カーネギーメロン大学は CAPTCHA Project による Gimpy [CAPTCHA] は,この方式による CAPTCHA を実装した代表的な例として挙げることができる。

061108_0.jpg
Gimpy の画像

061108_1.jpg
Gimpy-r の画像

これらの「歪んだ文字列」を用いる CAPTCHA は,実際にはどの程度堅牢なのだろうか? 結論から言ってしまえば,これらの CAPTCHA は決して堅牢ではない。最近の研究では,適切な技術を用いればこれらの文字列をコンピュータに認識させることが可能であることが明らかになってきている。故にこれらの CAPTCHA は,技術を持たない人々に対してのみ効果を発揮するものであり,本気で破ろうと思えば破れてしまうものであると考えておかなければならない。

そのような脆弱性を抱えているにも関わらず,今もなお広くこの方式が用いられているのは,スパマーの多くがここで言う「技術を持たない人々」に属すると考えられているからに他ならない。スパマーの中にも CAPTCHA 破りの技術を手にする人は存在しうるだろうが,それは全体から見ればごく小さな割合を占めるに過ぎない。完全な防止策とならずとも,多くのスパマーにとってコスト対効果の関係を破綻させるようなものとなれば,それで十分な効果が得られたものと考えることができる。

実際の CAPTCHA 破りの技術については, Wikipedia の "CAPTCHA" の項における "Defeating CAPTCHAs" のリストから多くの事例を参照することができる [Wikipedia] 。これらの事例の中には,学術的な研究によるものもあれば,趣味的な研究として行われているもの,あるいは営利的な目的から行われているものなど,様々に存在する。特に,営利的な活動として CAPTCHA 破りを行っている事例が存在することは,「技術を持たない人々」にもその技術をもたらす可能性が存在するものとして認識しておくべきかと思われる。

Gimpy 破り

カリフォルニア大学バークレイ校は Greg Mori らによる Gimpy 破りの試みは,学術的に CAPTCHA 破りの研究を行った例として広く知られている [Mori] 。 Mori らは Gimpy の簡易版である EZ-Gimpy に関してこれを自動的に認識するプログラムを作成し, 92% という非常に高い認識率を達成するに至っている。

061108_2.jpg
Image from Mori's paper

また,同氏らは簡易版ではない方の Gimpy に関しても自動認識を試みており,こちらは3単語同時に正解する確率として 33% を達成している。 EZ-Gimpy における結果と比較するとだいぶ認識率が下がっているように思われるが,これでも場合によっては十分に実用的な認識率を提供しうると考えられる。なにしろ,破る側にとってみれば全て自動で事が済むのだから,確率が多少低かろうが,その分長く放っておけばよいだけのことである。 3000 回トライすれば 1000 回は成功するのだと考えれば,それで十分な脅威ではないだろうか。

Breaking CAPTCHAs with NNs

2006-11-10

最近の研究では,「CAPTCHA 破り」にはニューラルネットワークによる機械学習が有効であることが分かってきている。前述の Mori らによる「Gimpy 破り」 [Mori] は Gimpy に特化されたものだった(特に Gimpy が固定の辞書を使用していることに着目している)が,機械学習を用いる手法であれば,文字による視覚 CAPTCHA 全般に応用することのできる可能性が与えられることになる。

ニューラルネットワークによる CAPTCHA 破りを試みた興味深い事例として Casey Chesnut によるブログ荒らし実験が挙げられる [Chesnut] 。同氏は「とあるブログサービス」において利用されている CAPTCHA を自動認識するプログラムを作成し,実際にそのプログラムを利用してコメントスパムを大量投稿するという実験を行った。同氏によれば 10 分間の試行の間に 94 ヶ所のブログに対してスパムを書き込むことに成功したという。こうしてコメントスパムを行う bot の開発が個人レベルでも可能であることを示すことにより,単一の貧弱な CAPTCHA エンジンに頼ることの危険性や,防衛側の技術向上の必要性を主張しようとしている。

ニューラルネットワークを利用した CAPTCHA 破りの学術的な研究としては Microsoft Research は Kumar Chellapilla による研究が興味深い [Kumar1] 。 Kumar らはニューラルネットワークを利用した CAPTCHA 破りシステムを Google (Gmail), Yahoo, Ticketmaster を始めとする幾つかの著名な CAPTCHA エンジンに対して適用し,これらを単一のシステムによって突破することが可能であることを示した。その成功率は 5% 程度の場合もあれば 50% に近い場合もありと非常に振れ幅が大きいが,いずれにせよ偶然に頼るよりは非常に高い確率で突破することが可能となっている。また,突破の容易な場合と困難な場合とを比較することにより,突破を難しくするために必要となる要素の抽出を行おうとしている。

ちなみに余談になるが, Kumar らは "CAPTCHA" という名称は用いずに, "HIP" (Human Interaction Proof) という名称を用いている。  CAPTCHA という名称がカーネギーメロン大学の商標であることを嫌ってか,他でもこのような名称が用いられることがある。

同じく Kumar らの研究の中に,ニューラルネットワークによる文字の認識のみに焦点を絞り,その認識率の高さを人間と比較したものがある [Kumar2] 。 CAPTCHA 破りの工程は,画像から文字を1文字づつ切り出す「分割」 (segmentation) の段階と,切り出した文字を1文字ごとに解析する「認識」 (recognition) の段階から構成されるが,このうちコンピュータにとって困難なのは「分割」の方であり,「認識」は比較的容易であるとされる。この研究は,その「容易さ」を人間との比較を行うことによって明らかにしたものである。

061110_0.jpg
分割の工程 (Image from Kumar's paper)

ここで驚くべきは,「認識」に絞って比較した場合,人間よりもコンピュータの方が高い認識率を持つという結果が導き出されている点である。つまり,「認識」に限って言うならば,実は人間よりもプログラムの方が CAPTCHA に通りやすいという矛盾した関係が存在することを示している。

例えば下図は "local warp" (文字内の細かな歪み)要素に関して人間とコンピュータの認識率を比較したものだが,歪みの度合いを上げてもコンピュータの認識率(紫色の線)は高い値を保っているのに対して,人間の認識率(青色の線)は大きく低下していることが分かる。 local warp 以外の6つの要素に関しても,この関係が逆転することは無かった。

061110_1.jpg
Image from Kumar's paper

Kumar らの研究の結果は,文字による視覚 CAPCHA に関して,文字毎の「認識」を困難にさせることを意図した歪みやノイズには全く意味が無く,そのような労力は文字の「分割」を困難にさせる方へと注がれることが望ましいという結論を導き出している。この事実は CAPTCHA を強固なものとするために非常に重要な要素であり,氏ら呼ぶところの「次世代の CAPTCHA」 には,そのような思想が盛り込まれることが予想されている。

The Birth of a Language

2006-11-16

061116_0.jpg
Image from The New York Times Magazine (photo by Susan Meiselas)

Lawrence Osborne. A Linguistic Big Bing. The New York Times Magazine, October, 1999.

Marisa Brook. The Birth of a Language. Damn Interesting, November, 2006.

Birth of a Language. PBS Documentary.

古代ギリシャの歴史家ヘロドトスはエジプトを訪れた際に,古代エジプトの王プサンメティコスが行ったとされる奇妙な実験についての話を耳にし,それを著書「歴史」に記している。その王は,人間の持つ言語の「起源」を探るために,生まれたばかりの二人の赤ん坊を羊飼いに与え,一切言葉を話しかけることなく育てるよう命令したという。王は,その子らが最初に発した言葉こそ,言語の源から生じるものであるに違いないと考えたようだった。そして2年が過ぎたある日,羊飼いはその子らが「ベコス」という言葉を発したと報告した。その後調べを重ねると,「ベコス」とはプリュギアの言葉で「パン」を意味するものであるということが分かる。こうして王は,プリュギアがエジプトよりも古い民族であることを認めるに至ったという [Wikipedia1] [Wikipedia2] 。

このヘロドトスの話はいかにも伝説のようだが,現代の言語学者にとってもプサンメティコスの実験は魅力的なものであるに違いない。生まれたばかりの無垢な赤ん坊を集め,隔離された環境に置き育てたならば,その子らは自らの言語を持つに至るだろうか? もし言語を持つに至ったならば,その「純粋培養の言語」は既存の言語と類似するものになるだろうか? しかしいくら言語学者がそのような実験を望んだとしても,現代においてそのような人道に反する実験が許されることは無いだろう。

決して誰かが許したわけではない――それは偶発的に行われたのだった。今を遡ること 20 年前,革命後間もないニカラグアにおいて。

1979 年,中央アメリカはニカラグアにおいて民族派による革命(サンディニスタ革命)が成功を収める [Wikipedia3] 。革命政府は政策のひとつに識字率の向上を掲げており,その一環として聾唖者の教育にも着手されることになる。聴覚障害を持ち,かつ喋ることの出来ない数百人の子供達が,首都マナグアの二つの学校へと集められた。しかし教師達は経験不足のうえ,教育方針も根本的に間違っていた(言語を持たない聾唖の子供達に文字綴りをベースとした手話を教えようとしていた)とあって,子供と教師の間の意思疎通がままならないという絶望的な状況がしばらくの間続けられることになる。

そのような状況にあって子供達は,いつしか簡単なジェスチャーを使って互いに意思疎通を図るようになっていた。大人達は相変わらず戸惑うばかりだが,まだ言語能力の固まっていない柔軟な頭脳を持つ子供達にとって,独自の「言語」を持つことはむしろ自然な流れだったのかもしれない。それは次第に語彙を増していき,本格的な文法を備え,ついには複雑な意思疎通をも行えるほど成熟した「言語」へと発展を遂げるに至った。後にこの「言語」にはニカラグア手話 (Nicaraguan Sign Language), またの名を Idioma de Signos Nicaragense 略して I.S.N. という名称を与えられることになる。

こうして子供達は互いに意思の疎通を図ることができるようになったが,教師との間の意思疎通は相変わらず断絶したままだった。当然,その「言語」の実態も,当の子供達以外にとっては全く謎に包まれたままであったという。そして 1986 年のこと,ニカラグアの教育省はこの謎めいた「言語」の正体を解き明かすべく,ノースイースタン大学に籍を置く手話の専門家ジュディ・ケーグル (Judy Kegl) を招聘することに決めた。ニカラグア手話の学術的な発見は,後にこのケーグルの手によって行われていくことになる。

ニカラグア手話の重大性は,それが聾唖の子供達という既存の言語から断絶された存在によって生み出された点にある。彼らは言語を持たなかったし,与えられもしなかった。しかし,そこに言語は生まれた。言語学者達は偶然から「言語の誕生の瞬間」を目にする機会に恵まれたわけである。その瞬間を近代的な科学の視点から観察することができたのは幸運に違いない。このような事例はこれまでの歴史の中に存在しなかったし,今後も極めて特殊な事例として扱われ続けることだろう。

言語が自然発生したという事実は,人間に言語を生み出すための能力が生来備わっていることを示唆している。また,ニカラグア手話は既存のあらゆる言語から断絶された存在であるはずだが,その文法には言語学者ノーム・チョムスキー [Wikipedia4] の提唱する普遍文法 (universal grammar) の概念を見ることができるという。これは,言語には生得的な性質があるとする言語学者達の意見を裏付けるものでもある。

興味深いのは,人間に生来の言語生成能力があるとしても,その発現にはコミュニティの存在が不可欠であるとする見方である。確かにマナグアの子供達は自らの言語を生み出したが,それは聾唖の子供達だけが集められ放置されたという特殊な状況にあって初めて発現したものだった。記者ローレンス・オズボーンはマナグアの子供達との対比のために,郊外の集落に住み学校にも通っていないという聾唖の子供を訪ねている。その子供は簡単なジェスチャーを使って家族と意思疎通を行うことができる(つまり,その家庭内でのみ通じる特殊な手話を操るとも言える)が,それは言語と呼べるようなレベルのものではなかった。語彙は極めて限られており,例えば「今日」や「後で」を表現することはできない。文法と呼べるようなものは存在せず,一つの文が2つよりも多くのジェスチャーから構成されることは滅多に無い。そして彼のジェスチャーは全体的にゆっくりとしており,マナグアの子供達に見られるようなリズミカルな動きや「流暢さ」が見られることは無かった。

かくして,集落の家庭に言語が生まれることは無く,学校に集められた子供達の間には言語が生み出された。たとえ人間に言語を生み出す能力が備わっているとしても,それを必要と欲するコミュニティが背景に存在しなければ,それを生み出す余地は無いのだろう。ゆえに,プサンメティコスが羊飼いに与えたという二人の子供も,羊の群れの中で育てられたとあっては,本当に意味のある言葉を生み出すことなど終ぞ無かったかもしれない――羊の群れは人間の言葉など必要としないのだから。

ニカラグア手話を操る一人,アンセルモ・アレマンが学校に通い始めたのは 15 歳になってからのことだった。一般に手話の「流暢さ」はコミュニティに加わるタイミングが早いほど優れる傾向にあり,彼のような年長者は不利にあると見られていた。それでも彼は必死に手話を勉強し,今では年少者に劣らず流暢な手話を操るまでに至っている。

その流暢な手話を操って,彼は語った――僕は子供の頃のことを覚えている。他人と意思疎通する方法を持っていなかったことも覚えている。僕の心は空白のようだった。

聴覚障害は彼から意思疎通の手段を奪うだけでなく,考えるための言葉を持つことさえも許さなかった。親米反政府ゲリラ(通称「コントラ」)の家庭に生まれた彼が覚えていることは,鬱蒼とした降雨林の中をサンディニスタ派から逃れ隠れる日々,人殺しの銃,そして恐怖。その彼にマナグアの学校のコミュニティが与えたものとは,他人と意思疎通するための手段と,自らがかつて得られなかったものを表すための言葉だった。