ReCAPTCHA

reCAPTCHA（リキャプチャ）とは、ウェブサイトの制限エリアへのアクセスを試みるボットからサイトを防御するためCAPTCHAを利用するのと同時に、そのCAPTCHAに対する返答を紙の本のデジタル化に活かすシステムである。

オリジナルは2007年にカーネギーメロン大学ピッツバーグ本校にて開発された。

2009年9月16日にGoogleはこのテクノロジーを買い取っている。

概要
現在reCAPTCHAはニューヨーク・タイムズが持つ記事アーカイブの電子化及びGoogle ブックスの書籍電子化に利用されている。前者は2009年の時点で、130年分を超えるという全記事のうち約20年分のデジタル化を2、3ヶ月で完了しており、残余は2011年末までの完了を目指していた。

reCAPTCHAは、OCRソフトウェアが読み取れなかった文字を画像として出力し、reCAPTCHAのデータを受信する各購読サイトへ向けてそれらを割り振る。購読サイトは、書籍デジタル化プロジェクトとは概ね無関係なサイトが多いが、これらの文字を含む画像を人間に差し出して、通常通りの認証手順の一部としてCAPTCHAの文字列を解読させる。そしてreCAPTCHAサービスは解答されたデータをデジタル化プロジェクトへ送信する。

インターネット上では日々2億超のCAPTCHAが表示されているとの報告があり、このリソースを活用しようと、Facebook、チケットマスター、4chan、CNN.com、及びなどの有名サイトはこのreCAPTCHAプログラムに2007年より参加しており、Craigslistは2008年6月より参加している。その他政府機関のウェブサイトでも使われることがあり、米国のは、2009年に完了したの際に、（Coupon-eligible converter box, CECB. いわゆるデジアナ変換機）用のクーポン申し込みサイトにてreCAPTCHAを採用していた。

 起源 
reCAPTCHAの開発計画は、マッカーサー基金のフェローシップ・プログラム（MacArthur Fellows Program）による支援を受けていた、グアテマラ人の計算機科学者、ルイス・フォン・アン（Luis von Ahn）が開始した経緯を持つ。CAPTCHAの初期開発者でもある彼は、CAPTCHAを誕生させた時に、「人間の貴重なリソース、すなわち脳の思考サイクルを1回につき10秒単位で何百万時間も浪費させてしまうようなシステムをいつの間にか作ってしまった」ことに内心気付いてしまった。そこで彼はこの無駄なリソースを有用な事業に役立てることを考えた。カーネギーメロン大学のルイスのチームは、インテルの支援を受けて、紙媒体の印字をコンピュータ可読な文字へと変換するためにウェブベースのクラウドソーシングを活用するという、このreCAPTCHAシステムを開発した。reCAPTCHAは当初、文書電子化を推進するOpen Content Alliance（OCA）の一員であるインターネットアーカイブの代理として、書籍電子化事業に利用された。

 運用 

reCAPTCHAの仕組みはこうである。スキャンされたテキストを2つのOCRプログラムで各々解析に掛ける。両プログラムの結果に相違が生じた場合、疑わしい文字をCAPTCHAに変換する。ただしこの時、既にOCRで認識できている文字を「対照文字」（control word）としてこのCAPTCHAに添加して表示する。そして、CAPTCHAをタイピングした人間が、仮に対照文字を正しく認識していた場合、OCRで正確に読み取れなかった文字に対するCAPTCHAの解答も正しいものであるとシステムは仮定する。各OCRプログラムによる文字認識に対しては0.5点を与え、人間の文字解釈に対しては1点（フル・ポイント）が与えられる。ある文字認識が計2.5点に一旦達した場合、スキャンされたテキストはこの文字認識であるとみなす。例えば、あるスキャンされた1つのテキストに対し、2つのOCRプログラムの認識結果がそれぞれ"dog"と"cog"だったとする。これをreCAPTCHAを通じて人間に見せた場合、提供開始から2人が"dog"と解答した時点でこのスキャン結果は"dog"だったとみなす。また、2人が"cog"と解答した時点でも同様である。そして、3人が"bog"と解答した時点で両OCRのスキャン結果を破棄し"bog"だったとみなす。このようにしてヒューマンエラーによる誤認識を極力減らしつつ人間の視覚を利用してOCRデータを解読する。人間の判断により単一の認識結果が一貫して与えられた文字は対照文字として再利用される。

reCAPTCHAは様々な紙媒体のスキャン結果の解読を人間に要求するため、CAPTCHAとして出題される文字はラテン文字だけとは限らないが、reCAPTCHAシステムの仕組みから、対照文字さえ返答すれば認証は通ってしまう（とはいえ、どちらの文字列が対照文字であるかは利用者は把握できない）。

 実装 
reCAPTCHAは各開発者がサービスを容易に実装できるよう、ブログやウィキなどの各種ウェブアプリケーション・プラットフォーム向けにプラグインを提供しており、一例を挙げると、WordPressやMediaWiki用のプラグインが存在する。更に、ASP.NET、Ruby、またはPHPなどといった処理系向けにプラグインやAPIのリファレンスが提供されている。またHaskellの処理系GHC用のプラグインのようにプロジェクト外部で独自に作成されているものもある。

 セキュリティ 

大本のCAPTCHAシステムは、コンピュータ・プログラム、すなわちボットによるシステムへの自動アクセスを防止する為に考案された認証システムである。これに対して、自動化プログラムによるCAPTCHAの突破を試みるものが存在する。

象徴的な事件は2009年4月に起きた。タイム100の投票サイトにて4chanの匿名利用者による多重投票事件が起きたが、タイム側が投票サイトにreCAPTCHAを導入した途端、多重投票はシャットアウトされた。4chanのユーザはreCAPTCHAのクラックを試みたが、結果的には失敗している。

しかし、reCAPTCHAがクラッカーに対し常に勝利しているわけではない。近年自動化プログラムによりCAPTCHAが突破されたとの事例が複数発表されているが、2009年12月14日、ジョナサン・ウィルキンズ（Jonathan Wilkins）という人物がreCAPTCHAに関する脆弱性を解説する論文を公表し、この論文上で彼は適切に構成したソルバーを利用して17.5%の解答率を得たと主張した。彼は、当時のreCAPTCHAによる出題は英語文献のOCRを基にしたCAPTCHAが多かったため検証し易く、更に同システムには対照文字に対するCAPTCHAの解答に余裕を持たせていた（対照文字の真の解答に対するレーベンシュタイン距離がoff-by-oneエラー程度ならば許容されており、例えば、レーベンシュタイン距離1の'lone'と'tone'などは同じ解答とみなされていた）など複数の弱点があったと述べた。彼はOCRエンジンのTesseractとそのフロントエンドから構成されるソルバー、及び、ソルバーが未知の単語を出力した際にそれを補正するためのスペルチェッカ、GNU Aspellを組み合わせCAPTCHA画像の文字を自動的に解読する手法を開発した。この自動化プロセスを利用したところ、200回の出題に対して2単語とも解読した例が10回、1単語のみ解読した例が25回（実質的には1単語さえ解読できれば良い為）、全正答率=(10+25)/200=0.175を得た。この発表後、Googleは対策として画像の歪み（distortion）を強化するようreCAPTCHAを改良した。

2010年8月1日、チャド・フック（Chad Houck）という人物が" 18 Hacking Conference"にて自動化プログラムによるreCAPTCHAの突破をテーマとするプレゼンテーションを行った。彼は同年3月頃に取得したreCAPTCHAの出題画像（右画像外部リンク参照）を基に、2.53GHzのシングルコアCPUを持つマシン上の自動化プログラムを用いて時間当たり10.07%の効率で正答を得ることができたと主張した。ジョナサンとは違い彼の自動化手法は直接CAPTCHA画像に手を加える形であり、まず、文字の背景にある楕円を除去するアルゴリズム及び独自開発の文字歪みを修正するアルゴリズムを用いて、余分なピクセルを削ぎ落とし文字の歪みを解消した。その上で、文字コードマップ（Character map, CMAP）及び辞書攻撃用リストを活用し文字解読を行った。このプレゼンテーションの約2週間前に当たる7月21日にGoogleはreCAPTCHAシステムの改修を行っており、フックは"DEF CON"開催前に彼の解読手法を変更する必要があったが、むしろ以前の手法よりも「簡単な」ものになっており、時間当たりの正答率も31.8%と上昇している。また彼はこのプレゼンテーションでreCAPTCHAシステムのセキュリティ防御についても言及しており、例えば、短時間に32回連続で間違った解答を行った場合、システムは強力なセキュリティ・ロックアウトを目的として、アクセス元IPアドレスにフラグを付けると述べている。

2012年5月26日にはLayerOneハッカーカンファレンスにおいて、DC949のメンバーであるAdam、C-P、Jeffballという人物が、自動化プログラムを用いて正答率99.1%を得る方法について詳細なプレゼンテーションを行った。彼らの戦略は、機械学習方式の人工知能を用いて、視覚が不自由な人向けに提供されている音声版のreCAPTCHAを突破するものだった。Googleは彼らの発表が行われる1時間前に、音声版と画像版双方のreCAPTCHAに対して大規模なアップデートを行った。このアップデートで、音声版は再生される長さがそれまでの8秒から30秒に延び、人間にとってもプログラムにとってもより理解することが難しくなった。DC949のメンバーはこのアップデートを受け、新たにそれぞれ60.95%と59.4%の正答率を得られる2つのプログラムをリリースした。Googleはその数日後にreCAPTCHAにさらに新たなアップデートを施し、DC949は現在のところこの最新版を突破できるプログラムは発表していない。

2012年6月27日には、メキシコの学生グループのクローディア・クルーズ(Claudia Cruz)、フェルナンド・ウセダ(Fernando Uceda)、レオバルド・レイズ(Leobardo Reyes)が、reCAPTCHAの画像に対して82%の正答率を得るシステムについての論文を発表した。このシステムが論文発表後にアップデートされたreCAPTCHAに対して有効かどうかに関して彼らはコメントしていないものの、システムは高性能なOCR技術に成長する見込みがあり、多少の変化には対応できるだろうとしている。

このように、CAPTCHAの自動デコード手法を開発する人物が後を絶たないため、reCAPTCHAのシステムは頻繁に改修されている。しかし却ってその事がを苛立たせている可能性もある。

 Mailhide 
reCAPTCHAを利用した別のプロジェクトにMailhide（メールハイド）というものがある。これはウェブページ上にさらされている電子メール・アドレスをスパム・ボットのような「電子メール・アドレス収集活動」（Email address harvesting）によって捕捉されないよう防御するものである。デフォルトでは、Mailhideは、クローラには完全な電子メール・アドレスが見えないようなフォーマットにアドレスの文字列を変換する。例えば、"mailme@example.com"というアドレスは"mai...@example.com"というアドレスに変換される。サイト訪問者がこの"..."をクリックすると、CAPTCHAが出題され、それを解答してはじめて完全な電子メール・アドレスを得ることができる。また"mai"の部分も完全に除去するためにポップアップ・コードを編集することもできる。

 特許 
reCAPTCHAに関する発明は2008年1月23日に米国特許商標庁へ特許出願されている。