reCAPTCHA

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ロゴ

reCAPTCHAとは、ウェブサイトの制限エリアへのアクセスを試みるボットからサイトを防御するためCAPTCHAを利用するのと同時に、そのCAPTCHAに対する返答を紙の本デジタル化に活かすシステムである。オリジナルは2007年カーネギーメロン大学ピッツバーグ本校にて開発された[1][2]2009年9月16日にGoogleはこのテクノロジーを買い取っている[3][4]

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

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

インターネット上では日々2億超のCAPTCHAが表示されているとの報告があり[8][12]、このリソースを活用しようと、Facebookチケットマスター4chanCNN.com、及びStumbleUpon英語版などの有名サイトはこのreCAPTCHAプログラムに2007年より[13]参加しており、Craigslist2008年6月より参加している[14]。その他政府機関のウェブサイトでも使われることがあり、米国国家電気通信情報管理庁英語版は、2009年に完了したデジタルテレビ放送への移行英語版の際に、クーポン資格型変換ボックス英語版(Coupon-eligible converter box, CECB. いわゆるデジアナ変換機)用のクーポン申し込みサイトにてreCAPTCHAを採用していた[15]

起源[編集]

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

運用[編集]

reCAPTCHAの出題例(2007年時点)。この例ではfollowing findingという二つの英単語が見える。文字のうねりと水平方向の曲線は、コンピュータ・プログラムによるCAPTCHAの突破をし難くするための細工である。

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

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

実装[編集]

reCAPTCHAによる文字解読テストは同プロジェクトのセントラル・サイトで試すことができる[7]。この試用サイトではJavaScriptAPIを介して、クライアントがCAPTCHAの解答をHTTPリクエストとしてサブミットした後、サーバがreCAPTCHAへコールバックする。reCAPTCHAプロジェクトは、処理をより簡単にするために様々なプログラミング言語やアプリケーション向けのライブラリを提供している。reCAPTCHAはフリーなサービスなので、CAPTCHA画像は文字解読の代償として各ウェブサイトに無償提供される[8]。しかし、reCAPTCHAソフトウェア自体はオープンソースではない。reCAPTCHAは各開発者がサービスを容易に実装できるよう、ブログウィキなどの各種ウェブアプリケーション・プラットフォーム向けにプラグインを提供しており、一例を挙げると、WordPressMediaWiki用のプラグインが存在する[23]。更に、ASP.NETRuby、またはPHPなどといった処理系向けにプラグインやAPIのリファレンスが提供されている[23]。またHaskellの処理系GHC英語版用のプラグイン[24]のようにプロジェクト外部で独自に作成されているものもある。

セキュリティ[編集]

2010年頃から出現したreCAPTCHAの問題例。この例では、and chiselsという二つの英単語が見える。この頃から以前のものと比べ文字の歪みの形状が変化しており、各単語の背景に黒い楕円が現れる様になった。

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

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

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

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

2012年5月26日にはLayerOneハッカーカンファレンスにおいて、DC949のメンバーであるAdam、C-P、Jeffballという人物が、自動化プログラムを用いて正答率99.1%を得る方法について詳細なプレゼンテーションを行った[41]。彼らの戦略は、機械学習方式の人工知能を用いて、視覚が不自由な人向けに提供されている音声版の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%の正答率を得るシステムについての論文を発表した[42]。このシステムが論文発表後にアップデートされたreCAPTCHAに対して有効かどうかに関して彼らはコメントしていないものの、システムは高性能なOCR技術に成長する見込みがあり、多少の変化には対応できるだろうとしている。

このように、CAPTCHAの自動デコード手法を開発する人物が後を絶たないため、reCAPTCHAのシステムは頻繁に改修されている。しかし却ってその事が同サービスに対する潜在的な不正利用者[誰?]を苛立たせている可能性もある[要出典]

Mailhide[編集]

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

特許[編集]

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

脚注[編集]

[ヘルプ]
  1. ^ Science, p. 1465
  2. ^ a b “Carnegie Mellon Project Boosts Book Digitization Efforts” (プレスリリース), Carnegie Mellon University, (2007年5月24日), http://www.cmu.edu/news/archive/2007/May/may24_recaptcha.shtml 2011年12月30日閲覧。 
  3. ^ Teaching computers to read: Google acquires reCAPTCHA”. googleblog.blogspot.com (2009年9月16日). 2009年9月16日閲覧。
  4. ^ “グーグル、reCAPTCHAを買収--書籍スキャンにも活用へ”. CNET. (2009年9月17日). http://japan.cnet.com/news/media/20400207/ 2011年12月30日閲覧。 
  5. ^ Olsen, Stefanie (2008年7月16日). “ReCaptcha: Reusing your 'wasted' time online”. CNET. http://news.cnet.com/8301-1023_3-9989480-93.html 2011年12月30日閲覧。 
  6. ^ Gugliotta, Guy (2011年3月28日). “Deciphering Old Texts, One Woozy, Curvy Word at a Time”. The New York Times. http://www.nytimes.com/2011/03/29/science/29recaptcha.html 2011年12月30日閲覧。 
  7. ^ a b c What is reCAPTCHA?”. Google. 2011年12月30日閲覧。
  8. ^ a b c reCAPTCHA FAQ”. Google. 2011年6月12日閲覧。
  9. ^ 次に挙げる、reCAPTCHA考案者のルイスが出演したテレビ番組より。米国外からアクセスしても権利制限されるため視聴できない。 Luis von Ahn (2009年6月30日) (英語) (flv). NOVA ScienceNow s04e01 (Season 4, Episode 1); Diamond Factory, Anthrax Investigation, Auto-Tune, Luis von Ahn (テレビ番組). PBS.. 該当時間: 46:58. http://video.pbs.org/video/1168232965 2009年7月6日閲覧. "The New York Times has this huge archive, over 130 years of newspaper archive there. And we've done maybe about 20 years so far of The New York Times in the last few months and I believe we're going to be done next year by just having people do a word at a time." 
  10. ^ 放送内容のトランスクリプト。"Transcript"をクリックすると、先述した引用がこちらから確認できる。 Profile: Luis von Ahn”. NOVA scienceNOW英語版. PBS (2009年6月30日). 2011年12月30日閲覧。
  11. ^ Gugliotta, Guy (2011年3月28日). “A Speech Lost in Digital Translation”. The New York Times. http://www.nytimes.com/2011/03/29/science/29brown.html 2011年12月30日閲覧。 
  12. ^ About Us”. Google. 2011年12月30日閲覧。
  13. ^ Rubens, Paul (2007年10月2日). “Spam weapon helps preserve books”. BBC. http://news.bbc.co.uk/2/hi/technology/7023627.stm 
  14. ^ Fight Spam, Digitize Books”. Craigslist Blog (2008年6月10日). 2011年12月30日閲覧。
  15. ^ TV Converter Box Program[リンク切れ]
  16. ^ Fellows Profile: Luis von Ahn”. MacArthur Foundation. 2011年12月30日閲覧。
  17. ^ Hutchinson, Alex (2009年3月). “Human Resources: The job you didn't even know you had”. The Walrus英語版: pp. 15–16. http://www.walrusmagazine.com/articles/2009.03-technology-human-resources-recaptcha-alex-hutchinson/. 
  18. ^ カーネギーメロン大学,画像認証を書籍デジタル化に活用するサービス「reCAPTCHA」”. itpro.nikkeibp.co.jp (2007年5月25日). 2011年12月31日閲覧。
  19. ^ a b Science, p. 1466
  20. ^ Timmer, John (2008年8月14日). “CAPTCHAs work? for digitizing old, damaged texts, manuscripts”. Ars Technica英語版. 2008年12月9日閲覧。
  21. ^ reCAPTCHAの無茶振りとその理由” (2011年9月30日). 2011年12月29日閲覧。
  22. ^ a b c d e Houck, Chad. “Decoding reCAPTCHA Paper”. n3on.org. 2010年8月19日時点のオリジナルよりアーカイブ。2011年12月31日閲覧。
  23. ^ a b Developer's Guide - reCAPTCHA - Google Code”. code.google.com. 2011年12月31日閲覧。
  24. ^ The recaptcha package”. hackage.haskell.org. 2011年12月30日閲覧。
  25. ^ moot - The 2009 TIME 100 Finalists”. TIME. 2012年1月2日閲覧。
  26. ^ von Ahn, Luis. “Why You Should Use reCAPTCHA to Protect Online Polls”. blog.recaptcha.net. 2012年1月2日閲覧。
  27. ^ 次のウェブページのルイスによる指摘部分を参照せよ。 moot wins, Time Inc. loses”. 2012年1月2日閲覧。
  28. ^ reCAPTCHAのみ突破されなかったが、その他のCAPTCHAがプログラムにより突破された例。
  29. ^ Wilkins, Jonathan. “Strong CAPTCHA Guidelines”. pp. 7-10. 2011年7月23日時点のオリジナルよりアーカイブ。2011年12月31日閲覧。
  30. ^ Guideline, p. 9
  31. ^ Google's reCAPTCHA busted by new attack”. The Register英語版 (2009年12月14日). 2011年12月31日閲覧。
  32. ^ Google's reCAPTCHA dented”. Heise Online英語版 (2009年12月17日). 2011年12月31日閲覧。
  33. ^ Guideline, pp. 7-8
  34. ^ Guideline, p. 8
  35. ^ Guideline, p. 9
  36. ^ a b reCAPTCHA Security”. Google. 2011年12月31日閲覧。
  37. ^ Google reCAPTCHA cracked” (2011年1月5日). 2011年12月31日閲覧。
  38. ^
  39. ^ 次の、「効果的楕円検知」アルゴリズムを利用した。 Yonghong Xie and Qiang Ji (2002). “A New Efficient Ellipse Detection Method” (PDF). Pattern Recognition, 2002. Proceedings. 16th International Conference on (RPI, IEEE) 2: 957-960. doi:10.1109/ICPR.2002.1048464. ISBN 0-7695-1695-X. http://www.ecse.rpi.edu/homepages/qji/Papers/ellipse_det_icpr02.pdf 2011年12月31日閲覧。. 
  40. ^ Houck, Chad. “Decoding reCAPTCHA Power Point”. n3on.org. 2010年10月24日時点のオリジナルよりアーカイブ。2011年12月31日閲覧。
  41. ^ Project Stiltwalker”. 2013年3月25日閲覧。
  42. ^ Claudia Cruz-Perez; Fernando Uceda-Ponga,Leobardo Reyes-Cabrera (27 June 2012). Carrasco-Ochoa, JesúsAriel and Martínez-Trinidad, JoséFrancisco and Olvera López, JoséArturo and Boyer, KimL. ed. Pattern Recognition. México. pp. 155-165. ISBN 978-3-642-31148-2. オリジナルの30 June 2012時点によるアーカイブ。. http://dx.doi.org/10.1007/978-3-642-31149-9_16 2013年1月23日閲覧。. 
  43. ^ Mailhide: Free Spam Protection”. Google. 2011年12月31日閲覧。
  44. ^ reCAPTCHA Mailhide API”. Google. 2011年12月31日閲覧。
  45. ^ Methods and apparatuses for controlling access to computer systems and for annotating media files”. Google Patent. 2011年12月30日閲覧。 “Filing date: Jan 23, 2008, Publication number: US 2010/0031330 A1, Application number: 12/524,149
    (出願日:2008年1月23日、公開番号: 2010年公開、US 2010/0031330 A1、出願番号: 12/524,149。"patent number" 「特許番号」は2011年時点では無し。)”

参考文献[編集]

外部リンク[編集]

ビデオ
その他