.NET とAIでスパムボットに対抗する（1） - japan.internet.com デベロッパー

はじめに

　ここでは、自動登録スパムプログラムを撃退するためにカーネギーメロン大学（CMU）とUCLAバークリー校の研究者が開発したAIアプリケーションの仕組みを紹介し、同様のアプリケーションをASP.NETとXML Webサービスで実現する方法について解説する。

「道のりは短いが、すべきことは山のようにある」（We can only see a short distance ahead, but we can see plenty there that needs to be done.）
―― A. M. Turing（AIの父、イギリスの数学者（1912-1954））

　大学での研究は今日の技術的発展と切っても切れない関係にある。ここでは、CAPTCHA（Completely Automated Public Turing Test to Tell Computers and Humans Apart：コンピュータと人間を区別する完全に自動化された公開チューリングテスト）の設計、開発、使用について取り上げる。

　我々は日々の生活の中でさまざまな形式のCAPTCHAを体験している。例えば、電子メールアカウントへのログイン、DNSルックアップ（whois）の実行、画像を使用して人間とソフトウェアプログラムとを区別する仕組みなどだ。大手のベンダ、Webポータル、電子メールプロバイダは、サービスの品質を向上させるために必ずCAPTCHAを採用している。検索エンジンやWebディレクトリは、自律的な不正投稿プログラムによって検索結果が変わってしまうのを防ぐためにCAPTCHAを利用している。オンライン投票システムでは、プロキシアドレスの偽装やIPスプーフィングによって投票の結果が左右されてしまうこともあるため、このテクニックを利用して多重投票を防止している。パスワードに対するブルートフォース攻撃や辞書攻撃にも、この単純だが効果的な手法で防ぐことが可能である。

　ここでは、まずCAPTCHAの簡単な歴史的背景を紹介し、チューリングテストの定義と機械の「視覚」について説明する。その後、Yahoo!、AltaVista、PayPalなどのポータルがそれぞれのデジタル資産を保護するためにCAPTCHAアプローチをどのように利用しているかを紹介する。最後に、Webアプリケーションを自律ボットから保護するためのプログラムをASP.NETで記述する方法について説明する。

　理論的な話はさておき、画像を操作するためのコードにASP.NETとC#を使用する。3つのサンプルでは、画像の動的生成と、辞書に基づくCAPTCHA方式の画像の作成、そしてその画像を返すWebサービスを取り扱う。また、CAPTCHAの他に、.NET画像ライブラリの使用方法、画像を動的に生成する方法、XML Webサービスを使用してバイナリデータを提供する方法についても取り上げる。

チューリングテストとは

　チューリングテストという考え方を初めて発表したのはAlan M. Turing（1912-1954）で、Turingの論文ではこれを「物真似ゲーム（the imitation game）」と呼んでいた。このテストは、コンピュータプログラムが知能を持つかどうか（より正確には、本当は機械であるのに質問者に人間だと思わせることができるかどうか）を判定することの起原になった。
　Turingの論文では、チューリングテストをこう説明している。「この新しい形の問題は、我々が『物真似ゲーム』と呼んでいるゲームによって表現できる。このゲームは3人の人物、つまり男性（A）、女性（B）、質問者（C）で行われる。質問者は男女どちらでもよいが、他の2人とは別の部屋にいる必要がある。このゲームにおける質問者の目的は、他の2人のうちどちらが男性で、どちらが女性かを見極めることである。質問者は、ゲーム中は他の2人をXとYという記号で区別し、ゲームの最後に、『XがAで、YがBである』または『XがBで、YがAである』と特定する。質問者はAとBに質問をすることができる」。
　これには批判も多かったが（「思考」と「知能」についての別の定義を示した「中国語の部屋問題」（Searle,1980）など）、チューリングテストは今もAI、哲学、認知科学の基本的アプローチとされている。
　提供：CAPTCHA.NET. The CAPTCHA Project is a project of the School of Computer Science at Carnegie Mellon University.It is funded by the NSF Aladdin Center.

CAPTCHAとは

　CAPTCHAとは、「Completely Automated Public Turing Test to Tell Computers and Humans Apart（コンピュータと人間を区別する完全に自動化された公開チューリングテスト）」の頭字語である。名前からわかるとおり、これは人間らしさを測るためのテストである。CMUコンピュータ工学部のWebサイトにあるCAPTCHAのホームページでは、次のように定義されている。

CAPTCHAとは、次のようなテストを生成、評価するためのプログラムである。

ほとんどの人間は問題なく合格できる
現在のコンピュータプログラムでは合格できない

　例えば次の画像は、本稿の後半で紹介するWebサービスを使って生成したものである。これはコンピュータプログラムにとっては判読が難しいが、人間ならば7才の子供でも簡単に読み取ることができる。

図1.1：本稿のサンプル（captchaWebservice）で生成した視覚的なCAPTCHA

CAPCHAの利用法とYahoo!での実装例

　インターネット上でのサービスやビジネスが急激に発展している今日では、オンラインセキュリティはソフトウェア開発者、設計者、管理者、ベンダにとって重要な課題になっている。人間の真似をしたり、Webサーフィンのパターンを模倣したり、オンライン活動を偽装したりするソフトウェアプログラムも増加している。このような「人間のふりをする」プログラムは、「ロボット」または「仮想エージェント」と呼ばれる。代表例として、電子メールアドレスに対してブルートフォース攻撃（総当たり検索）を実行するソフトウェアプログラムなどがある。このプログラムは、正しいものが見つかるまで可能性のあるパスワードの組み合わせをすべて試すという処理を行う。こうしたスパムボットによって、Web投票、Web登録、自動化サービス、検索エンジンの投稿などのサービスを持つデジタル資産は、さまざまな脅威にさらされている。

　こうしたことから、科学者たちは人間と機械とを区別する自動テストの必要性を感じていた。そんな中、Yahoo!の主任研究者であるUdi ManberとCMUコンピュータ工学部のManuel Blum教授ならびに大学院生は、Yahoo!のサイトのために、HTTP POSTを使用してフォームを何度も再送信する不正ルーチンを防止するCAPTCHAサポートを開発した。といっても、これは簡単に解決できるような問題ではなかった。Yahoo!のUdi Manberはこう述べている。「大学にいる人は、常におもしろい問題を探している。私のように業界にいる人は、常におもしろい問題がありすぎて困っている」。

　Yahoo!では、Yahoo!ブリーフケース、Yahoo!メール、Yahoo!グループなどのサービスにCAPTCHAを導入することで、これらのサービスを不正な自動登録から保護している。次に示す例は、辞書攻撃を防ぐためのもので、画像内の文字列を入力しないと次に進めないようになっている。

図1.2：Yahoo!のブルートフォース攻撃対策

　この画像は動的に生成され、アクセスのたびに変化する。ユーザーIDとパスワードが正しくても、画像内のテキストを正しく入力しない限り、ログインすることはできないので、人間とコンピュータを見分けることができる。

　通常のサービス悪用プログラムやブルートフォース攻撃ボット（ロボットの短縮形、自律エージェントを表す）は、このような画像内の文字を読み取ることができない。これを読み取るためにはOCR（optical character recognition：光学式文字認識）機能が必要だが、例え優れた画像認識機能を持つOCRがあったとしても、HTML内にある次のような画像のファイル名を読み取ることが難しいだろう。

http://reg.yimg.com/i/retcQ.dZFemtHS_cf_8Qk12i.XyVGZ2Ej2qW7dKNiIqt0C1AF6mlqmWnUuLe.jpg

　ファイル名は長いランダムな文字列になっており、文字列の照合のために、この画像ファイルのハッシュエンコーディングを含んでいる。これについては後で詳しく説明する。

　また、このHTMLフォームには、攻撃に備えて次のような隠しフィールドが含まれている。

<input type=hidden name=".challenge" value="c9gLhuwLilq7KGFDsNBjac2ZSvWL">

図1.3：Yahoo!のCAPTCHA画像にアクセスした様子

　この画像はディスク上に保存されており、上の図のように個別にアクセスすることもできるが、やはりOCRでの読み取りは難しい。このテキストはアフィン変換（傾斜、ストレッチ、拡大縮小）されているため、パターンマッチングに基づいて文字認識を行うOCRにとっては難易度が高い。というのも、OCRの文字認識方法が、人間とはまったく異なっているからだ。人間はただ文字の形を読み取るのではなく、その文字列の意味や前後の流れを踏まえた上で読み取るため、多少見にくくても判読できる。一方、機械の視覚ではそうはいかない。ごちゃごちゃした背景の中で「t」と「i」がくっついて配置されていて、なおかつグラデーションやノイズがかかっている場合には、OCRで読み取ることは非常に困難である。

　このように、画像はボットによる自動登録を防ぐ有効な対策の1つではあるが、ずっと防ぎ続けることはできない。ボット作成者は防御策に対抗するために、そのような画像を読み取るOCRテクニックを利用して、引き続き自動登録を行うだろう。しかし、予測可能なグリッド上に単純なテキストを配置したCAPTCHA画像よりも、傾斜やツイスト、歪みを加えた画像を利用すれば、ボットを防止できる可能性ははるかに高くなる。

　機械は文字列の意味や前後の流れを踏まえた上で読み取ることをしないため、ノイズやアフィン変換（特に鏡像にしたり、XY軸の向きを変えたりなど）、分割、傾斜、重なり、劣化などが適用された文字を判読することは非常に難しい。機械が画像を「見る」方法では、『インドの6人の盲人（The Blind Men and the Elephant）』の話のように、1つの文字を別々のものとして解釈する可能性もある。

さまざまなCAPCHA

　最近増えつつあるインテリジェントなボットを想定して、CMUはさまざまな種類のテストを作成している。ここではGimpy、Bongo、Pix、Sounds、Byanについて紹介する。

Gimpy

　CMUによれば、Gimpyは最も信頼できるシステムとされている。さらに、次のように書かれている。「これはもともとYahoo!との共同開発によるもので、Yahoo!のチャットルームからボットを排除すること、大量の電子メールアドレスを取得しようとするスクリプトを防止すること、案内広告を表示するコンピュータプログラムを防止することを目的としている」。

　Gimpyでは、本稿の後半で紹介するWebサービスやアプリケーションと同様に、辞書から一定数の単語を選び出し、ノイズを加えたり歪めたりした上で画像として表示し、画像内のテキストを入力するようユーザーに要求する。人間ならば簡単に入力できるが、ボットの場合はそうはいかない。

　次の図は、Gimpyで生成したCAPTCHA画像の例である。

図1.4：Gimpyで生成した画像（提供：CMU）

図1.5：Gimpyによる複数単語テスト（提供：CMU）

Bongo

　Bongoは、次の図のような視覚的なパターン認識をユーザーに求めるプログラムである。詳しくはCMU CAPTCHAのWebサイトを参照してほしい。

Pix

　このプログラムは、いくつかの画像をランダムに表示し、その中から共通する物をユーザーに質問する。これは斬新で知的な方法であり、この方法を使用すれば、かなりの長期間ボットを排除できるだろう。次の図がPixの使用例である。

図1.6：Pixの画像認識テスト（提供：CMU）

Sounds

　その名の通り、これは音声方式のGimpyである。Soundsでは単語または一連の数字をランダムに選択し、品質の低いサウンドクリップを生成する。このようなアプリケーションを攻略するためには、OCRだけでなく音声認識機能も備えたボットが必要になる。

視覚的なCAPTCHAに対する攻撃

　開発者や研究者は、品質を向上させるために、継続的にCAPTCHAの開発、テスト、攻撃を行っている。これは、言ってみればチューリングテストマシン用の堅牢な自動化テストを作成しているようなものだ。カリフォルニア大学バークリー校のGreg MoriとJitendra Malikは、ez-gimpyを83%の精度で破るプログラムを開発した（詳しくは「Breaking a Visual CAPTCHA」を参照）。また、ケンブリッジ大学ビジョングループのThayananthan、Stenger、Torr、Cipollaは93%の精度でez-gimpyの画像を正しく認識できるプログラムを開発した。後にMalikとMoriもそれに匹敵する精度を達成した。
　Arete AssociatesのGabriel Moy、Nathan Jones、Curt Harkless、Randy Potterは、gimpy-rを78%の精度で判読するプログラムを開発した。したがって、gimpy-rは近いうちに破られると思われる。そのため、もっと破ることが難しいテストが登場することだろう。
　各企業でのCAPTCHAの実際の利用例を示す前に、興味深い例を1つ紹介しておこう。これは、CMUのCAPTCHAホームページのオンライン投票に関する実話である。
　1999年11月、http://www.slashdot.comにおいて、最も優秀なコンピュータ工学の大学院はどこかというオンライン投票が実施された（Web投票で扱うには何とも危険な質問だ！）。この投票システムでは、たいていのオンライン投票と同様に、1人のユーザーによる多重投票を防ぐために投票者のIPアドレスを記録していた。しかし、CMUの学生達が、CMUに何千票も投票できるようなプログラムを考え出し、CMUの得票は急速に伸びていった。翌日、今度はMITの学生達が独自のプログラムを開発したため、この投票は投票ボットの対抗戦のようになってしまった。最終的に、MITは21,156票、CMUは21,032票を獲得し、他の大学は軒並み1,000票以下だった。こんなオンライン投票の結果を信用する人はまずいないだろう。

　次回「企業での CAPTCHA 利用例」へ

著者紹介

Adnan Masood（Adnan Masood）

ロンドンのUKIMのソフトウェア開発者。UNW Stratford Londonキャンパスにてソフトウェア工学の理学修士号を取得。複数のソフトウェア開発技術にまたがるハイブリッド的な視野を持って開発に臨み、主にMicrosoftおよびSunプラットフォームのサーバーサイドプログラミングを専門とする。ここ5年間はASPおよびJavaの開発者として活躍。コンピュータ工学の理学士号とSun Java-II Certification（SCJP-II）の資格を持つ。ブログのURLはwww.axisebusiness.com/adnano。電子メールアドレスはamasood@bcs.org.uk。