4Chan CAPTCHAの解読
(nullpt.rs)- ブラウザ内で4Chan CAPTCHAを自動的に解くためにTensorFlow.jsモデルを作成したプロジェクトで、目標だった最低80%と、望ましい目標である90%以上の精度を達成した
- CAPTCHAの収集は、リクエストAPIの
ttl、cd、Cloudflare Turnstile、増加していく待ち時間のため、単純な大量スクレイピングでは処理しにくかった - 商用の人力解読サービスと手動ラベリングは、誤りとスロットリングに阻まれ、実際の背景約2,500枚と文字ごとに50〜150枚の画像から合成データ約50,000枚を作って学習規模を確保した
- モデルはCNN+LSTM構成とCTCエンコーディングを使用し、Keras/TensorFlowで学習した後、Python 3.10、Keras 2、
.h5フォーマットを経由してTensorFlow.jsへ変換した - 実際のブラウザでは初回ロードが約1秒、その後の実行は体感上ほぼ即時で、数百件の実際のCAPTCHAに対して90%超の成功率を示した
目標と公開コード
- 目標は、機械学習とTensorFlowの学習を兼ねて、4Chan CAPTCHAをブラウザで安定して解くモデルを作ることだった
- 基準は最低80%の精度、可能なら90%以上で、最終的に達成した
- 関連コードはGitHubの4chan-captcha-playgroundで公開されている
4Chan CAPTCHAの仕組み
- 4Chanでは、投稿や返信を行う前にCAPTCHAの入力が求められる
- 通常のCAPTCHAは5〜6文字の英数字を含む画像で、ユーザーはすべての文字を正確に入力する必要がある
- スライダーCAPTCHAは、ランダムな文字片のように見える背景画像と、透明な穴のある前景画像を合わせてCAPTCHAテキストを見えるようにする方式である
CAPTCHA収集で直面した制約
- 新しいCAPTCHAリクエストを観察すると、ブラウザは
https://sys.4chan.org/captcha?framed=1&board={board}へリクエストを送る framed=1を外すと、HTML内のpostMessage()の代わりに生のJSONが返される- JSONには
challenge、ttl、cd、img、img_width、img_height、bg、bg_widthなどが含まれる ttlは約2分後にCAPTCHAが期限切れになる時刻を表しているようだったcdは次のCAPTCHAリクエストまで待つべきクールダウン値だと解釈できる
- JSONには
- 連続してリクエストを送ると、
cdは徐々に大きくなる- 最初の数回は5秒ごとにリクエスト可能
- その後8秒に延び、以後はおおむね倍々で増加する
- 最終的には280秒で上限に達する
- 280秒タイマーに達した後は、CAPTCHAがさらに難しくなる
- 複数の横線や楕円形の妨害要素が追加された画像が現れる
- データ品質は下がるが、それでも利用は可能だった
- CAPTCHAをリクエストする前にはCloudflare Turnstileの通過が必要
- 多数のプロキシや単純なスクリプトを使う方法は現実的ではなかった
- 収集スクリプトはブラウザからCloudflareのCookieをコピーして利用し、期限切れになれば手動で差し替えていた
- この方法で数百件のCAPTCHAを収集できたが、学習には十分な量ではなく、正解ラベルもなかった
人力ラベリングの限界
- スライダーCAPTCHAの位置合わせは、
trainer/captcha_aligner.pyのヒューリスティックなスクリプトで100%の成功率を示した - 商用CAPTCHA解読サービスにCAPTCHAを送り、実際の人が正解を入力する
trainer/labeler.pyを作成した - 最初に送った数十件のCAPTCHAは、その大半で少なくとも1文字以上が誤って解読された
- サービスの「100% Recognition」機能を使い、複数作業者の回答が一致した場合にのみ結果を受け取るよう設定した
- 設定値は
n = 2、x = 2、y = 3 - まず2人に送り、2人の回答が一致しない場合は最大3人を追加し、2人の回答が一致するまで試行する
- 設定値は
- この設定で約80%のCAPTCHAが解読され、そのうち約90%は正確だったが、約10%には誤りがあった
- 複数の作業者が同じミスをする場合があった
- 自分または知人の協力でCAPTCHAを解いて画像と正解を保存するユーザースクリプトも使った
- 数百枚の画像を追加で得て、学習セットに組み込んだ
- 繰り返しリクエストに対するスロットリングとCAPTCHA難易度の上昇により、このアプローチは中止した
合成データ生成
- 4ChanとそのCAPTCHAコードはオープンソースではないため、同じコードをローカルで動かすことはできなかった
- その代わり、実際のCAPTCHA構造を近似した合成CAPTCHAを生成した
- CAPTCHAは背景と文字の2つの部分に分けて扱った
- 背景は実画像から大きなcontourを見つけ、文字領域を除去して得た
- 文字を除去した後は、ノイズ背景だけが残る
- 個々の文字は手動ラベリングで確保した
- VoTTで文字にタグ付けした
- 簡単なスクリプトで文字を抽出し、後処理した
- 文字ごとに50〜150枚の分離画像を確保した
- 4Chan CAPTCHAには
0, 2, 4, A, D, G, H, J, K, M, N, P, R, S, T, W, X, Yだけが含まれる- 曖昧さを避けるための選択である可能性がある
- 抽出した文字と背景を組み合わせ、観察した文字配置パターンに合わせて合成画像を生成した
- 入力文字があらかじめラベル付けされているため、合成CAPTCHAの正解も自動生成できた
モデル構成と前処理
- 学習データには、事前に位置合わせしたスライダーCAPTCHA、通常のCAPTCHA、合成CAPTCHAを混ぜて使用した
- 学習スクリプトは、すべての画像を300x80ピクセルにそろえ、純粋な白黒へ変換した
- モデルは、CAPTCHA解読に関する複数の記事を参考に構成したLSTM CNNアーキテクチャである
- convolution/max-poolingレイヤーを3つ使用
- LSTMレイヤーを2つ使用
- 4つ目のconvolutionレイヤーも試したが、性能は改善しなかった
- 出力長が5文字または6文字で可変のため、CTCエンコーディングを使用した
- 実装にはKerasとTensorFlowを使用した
tf.image.resize()の引数順の問題
- 一部の古い位置合わせ済みスライダーCAPTCHAは、300x80の解像度やアスペクト比に合っていなかった
- 学習スクリプトが多様な入力を処理できるよう、
tf.image.resize()を使用した - 当初はサイズ引数を
(width, height)タプルだと思っていたが、実際のtf.image.resize()は(height, width)の順序を要求していた - このミスにより、画像は80x300のように縦に引き伸ばされ、読めない形になっていた
- 32 epoch以上学習しても、見たことのある画像でさえ性能はほとんど出なかった
- 新しいCAPTCHAに対してはランダムに近い予測を出していた
- 処理済み入力画像を可視化することで問題を特定し、修正後は学習性能が大きく向上した
学習規模と結果
- 最終データセットは約500枚の手動解読画像と、約50,000枚の合成画像で構成された
- 合成画像は約2,500枚の背景画像と、文字ごとに50〜150枚の画像からランダムサンプリングして生成した
- データセットはランダムにシャッフルした後、90/10の比率で学習セットと評価セットに分割した
- NVIDIA RTX A4000 Laptop GPUでのepochあたりの学習時間は約45秒だった
- 最初のepoch終了時のlossは19程度で、予測はほとんど当たっていなかった
- 4回目のepoch終了時にはlossが0.55まで下がり、ランダムテスト予測5件中5件が正解した
- 8〜16 epochが時間と最終性能の間でよい折衷点だった
- 8回目のepochあたりでlossが安定した
- 16 epochを超えると改善幅は大きく減少した
trainer/infer.pyでPython上の推論をテストし、未見画像でも結果は有望だった
TensorFlow.jsへの変換とブラウザ実行
- ユーザースクリプトはTensorFlow.jsとTypeScriptで書かれている
- PythonコードのCAPTCHA位置合わせアルゴリズムと画像前処理コードを再実装した
- 関連コードはリポジトリの
user-scripts/ディレクトリにある - PythonのTensorFlow/Kerasモデル形式は、TensorFlow.jsが期待する形式と互換性がなかった
- 公式の変換スクリプトを使う必要があったが、2つの問題があった
- 公式のTensorFlow-to-TFJS変換器はPython 3.12では動作せず、エラーメッセージも明確ではなかった
- PyEnvでPython 3.10を使うと変換は成功した
- 変換スクリプトはKeras 3モデルをTensorFlow.js形式へ変換できたが、TensorFlow.jsはその変換済みモデルを実際には読み込めなかった
- 関連する問題はforum postで確認した
- 解決策はKeras 2の使用だった
tf_kerasレガシーパッケージをインストールしたTF_USE_LEGACY_KERAS=1環境変数を設定して学習した- レガシー
.h5モデル形式でエクスポートし、変換スクリプトに入力形式を指定した - コード変更は1行の単純な修正だけで済んだ
実際の4Chan CAPTCHAでの性能
- 実際の4Chan CAPTCHAでもモデルはよく動作した
- 最初のモデル読み込みには約1秒かかった
- その後の実行は体感上ほぼ即時だった
- ブラウザで数百件の実際のCAPTCHAを解いた経験では、成功率は90%超だった
- 文字自体を間違えるケースはまれで、不正確な場合は通常、文字を1つ丸ごと見落としていた
- 実データ学習をさらに増やすか、合成データ生成器のCAPTCHAレイアウトを調整すれば改善の余地がある
- 商用の人力CAPTCHA解読サービスよりも、このモデルの精度ははるかに高かった
4文字CAPTCHAと締めくくり
- プロジェクト完了後、記事を書いて編集している間に、4Chanがときどき4文字CAPTCHAを提供し始めた
- モデルは5文字と6文字のCAPTCHAだけで学習していたが、4文字CAPTCHAでも同程度の性能を示した
- プロジェクトの過程で機械学習とコンピュータビジョンを多く学び、当初の目標だったブラウザベースのCAPTCHA解読モデルを完成させた
1件のコメント
Hacker Newsのコメント
KerasとTensorFlow.jsの連携がひどいのは、いかにもTensorFlowらしい
TensorFlowを使っていると、常に統合されて洗練された製品というより、なんとなく関係ありそうなツールをひとつの傘の下に寄せ集めたような印象だった
実際、Googleのオープンソースライブラリやツールは全部そんな感じだとさえ言える
「なぜ2019年にKerasをTensorFlowに統合することにしたのか？」への答えは、「私が決めたことではない。2018年にTFのリーダーたちが下した決定で、当時の私はL5の個人貢献者であり、それはL8レベルの決定だった」というものだった
自分のサイト[0]でコメントフォームのスパムを防ぐためにCAPTCHAが必要だったので、以前見た面白い方法を再利用してみた
決して完璧でも難しくもないが、作る過程が本当に気に入った
[0] https://www.hybridlogic.co.uk/contact
https://vivirenremoto.github.io/doomcaptcha/
人々が歪んだテキストベースのCAPTCHAから離れたのには理由がある
いまやコンピューターのほうが人間よりうまく解けるところにほぼ来ている
https://www.usenix.org/system/files/conference/woot14/woot14...はこのテーマに関する論文で、かなり興味深いと思う
それでも驚くほど多くのテキストベースCAPTCHAは、ImageMagickでグレースケール変換、膨張と収縮処理をしてからTesseractに渡す数行のシェルスクリプトで解ける
しかしhttps://2captcha.netのようなサイトもあるので、結局CAPTCHAは最小限の小さな手間を要求する仕組みに近い
この記事の解法にもかなりの時間、技術、労力がかかっており、成果物もあまり汎化されていないので、別種のCAPTCHAなら最初からやり直しになる
ほとんどのスパマーはこれを再現できず、再現できる人は合法的に稼ぐか、もっと儲かる標的を狙う可能性が高い
こうしたCAPTCHAは、スパム成功のコストを予想収益より高くするという点で、依然としてうまく機能する
すべての会員が運営者と15分のビデオ面接をしなければならないフォーラムを作れるだろうか？ 「スケールしない」のは分かっているが、ふざけた仕掛けとしてはできそうだ
解決策ではなく、少しずつ古びていく小さな要塞のようなものだ
リンクによれば、reCAPTCHA v3は10〜15秒かかり、CAPTCHA 1000件あたり1.3ドルかかる
大規模サイトを大量にクロールするような、CAPTCHAを回避したい多くの作業では、このコストは実際かなり大きく、負担しにくいものになる
mCaptcha.orgもそのひとつで、ほかの実装もある
従来型のCAPTCHAは、少しでも効果を持たせようとするとアクセシビリティ面で悪夢になりがちだ
この手の話題に興味があるなら、2014年に自分がまとめたSilk Road CAPTCHAの分析もある: https://github.com/mieko/sr-captcha
4chanの対応は妥当に見える
どうせニューラルネットワークで簡単に解けるのだから、人間に割り当てる仕事を単純化する方向だ
もはや極端に難しいCAPTCHAを設計しても、機械が解きにくくなる可能性は低く、人間だけをよりいら立たせる公算が大きい
https://4chan.org/pass
すでにCAPTCHAなしで投稿するためのオプションとして提供されている
もしCAPTCHAが完全に無効なら、CAPTCHAと無料投稿をなくし、投稿したい人は全員4chan Passを買わなければならない、という結論になる
最近は15分の書き込み遅延まで導入していて、本当に腹が立つ
Cookie AutoDeleteで4chanを許可リストに入れなければならなかった
CAPTCHAがあるように見せかけつつ、実際にはユーザーのタイミングと挙動を分析するほうがよいのでは、という気がする
正直、もうすでにそうなっていそうでもある
完全にメタに行くなら、相手の行為主体が人間かどうかを判定するようAIを訓練することもできる
つまり逆チューリングテストを発明するようなもので、AIが普通の人間の応答と区別できなければ人間とみなす方式だ
マーケティング用の人間応答と区別するわけではない、という点が違う
もうこの考えだけで少し気分が悪くなって横になりたくなる
CAPTCHAを出す前から、TLSフィンガープリント、IP、HTTP/2、リクエスト、JavaScript環境、フォントや画像のレンダリング能力、ブラウザ自体をまず識別する
それらの情報で信頼スコアを計算し、そもそもCAPTCHAを表示するかどうかを決める
その後でようやくCAPTCHA入力を分析する意味が出てくるが、その時点でボットの90%はすでに捕捉されているようなものだ
ブラウザが何の意識もなくサーバーに伝えられる情報量は信じがたいほど多く、私たちそれぞれのデジタル指紋は実際の指紋よりも固有である可能性が高い
4chan CAPTCHA突破の元祖級の事例は、やはりYannick Kilcherが「Raiders of the Lost Kek」データセットでGPT-Jをファインチューニングしたものだと思う
動画で公開された大規模言語モデル活用例の中でも、最もクールな事例かもしれない: https://youtu.be/efPrtcLdcdM?si=errY0PrEhnX9ylDw
記録級だ
「公式のTensorFlow-to-TFJSモデル変換器がPython 3.12で動かず、文書化もまともにされていない」「TensorFlow.jsはKeras 3をサポートしていない」といったことが原因で、数年前に気軽に機械学習を試そうとしてほとんど諦めた
最新チュートリアルがすでに古くなっていることがあまりに多く、ランダムな落とし穴も多く、「はじめに」ガイドがすでに専門家であることを前提にしているケースが衝撃的なほど多かった
古いベイズ統計学の教科書で基礎を学び、そのあとでPyTorchのような主要フレームワークに進むほうがよい
最初はCNN、RNN、Transformerアーキテクチャと学習パイプラインのあらゆる部分を自分で書いてみるのがよい
データローダーまで含めて、CUDAの行列カーネルは除いてよい
LangChainのような、他人のラッパーをさらに包んだラッパーには近づかないほうがよい
ドキュメントが古いどころか、基礎について完全に間違っていることさえ多い
Hugging Faceは、基本を理解していて標準ラッパーが壊れたときに自力で直せるなら素晴らしい
これは、何時間もかけて浄化槽のふたの開け方を学ぶのに近い
CAPTCHA解答サービスのリンクをたどると、その仕事をしている人たちのプロフィールを読める
危険な工場で働くよりは倫理的だ、という触れ込みで宣伝されている