1
日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

ASIRRA システムに対する機械的な突破の検証
飯田 貴章

藤本 衡

アクセス者が人間であることを判別する手法である CAPTCHA 認証は近年の画像認識の発達に伴って，ボットによって突破される事例が多く発生している．その対策として認証テストが難化し，人ですら回答が困難になる問題が起きている．そこで，新たな認証として ASIRRA が開発された．ASIRRA は，動物種の画像による機械的識別が困難であるという状況を利用して，犬と猫を選ばせることで人間の判別を行うシステムである．本研究では，ASIRRA をボットで突破することがある程度現実的な確率で可能かどうかを検証する．猫および犬の画像に対して
Baf-of-Keypoints による特徴量抽出と SVM による機械学習によって個別の画像の再現率を高めることで，突破確率をどの程度まで高めることができるか数値実験を行う．

発生している．その対策として，文字列をさらに歪ま1 はじめにせるといった措置をとる影響で，ボットだけでなく人近年，ボットによる Web サービスの不正利用が問間ですら読み取りが困難になる問題が起きている．

題となっている．ボットは，自動化された処理を高速そこで，新たな認証テストを用いる ASIRRA [6] がに実行することができるため，メールアドレスやアカ開発された．ASIRRA は，人間が動物種の画像を容ウントの大量取得などが発生し，サービスの性能劣化易に識別できる一方でボットが機械的に識別することや他のサービスに対する攻撃の踏み台になるなどのが困難であるという状況を利用して，犬と猫の分類を懸念がある．

行うことで人間の判別を行うシステムである．しかそこで，人間とボットを判別するシステムである

し，色やテクスチャを特徴とした画像認識によって，CAPTCHA 認証が利用されている．CAPTCHA 認

ASIRRA の認証テストを機械的に突破する試みが既証 [7] は，Web サービスへのアクセス者が人間であるに行われている．

ことを判別するチューリングテストの一種である．出

本研究では，局所特徴量の出現頻度を特徴とした題者が，人間には容易であるがボットには識別が困画像分類手法によって，ASIRRA の認証テストを機難な問題を認証テストとして出題することで人間と械的識別で突破することが，より高い確率で可能でボットの判別を行う．最も広く使われている認証テスあるか検証する．ASIRRA の検証実験に用いる画像

トは，ボットが識別困難となるように歪ませた文字列分類システムを作成するにあたって，本研究では特画像を読み取らせる問題である．しかし，画像認識の徴量として Bag-of-Keypoints [2] を利用し，Support発達に伴って CAPTCHA 認証を突破する事例が多くVector Machine(SVM) [1] を用いた機械学習および判別を行う．

Trial for defeating ASIRRA system with automaticmethods.
Takaaki Iida, 東京電機大学大学院理工学研究科情報学専
攻, Informatics, Tokyo Denki University.
Kou Fujimoto, 東京電機大学理工学部情報システムデザイン学系, Div. of Information System Design, Tokyo
Denki University.

2 ASIRRA について
CAPTCHA 認証を突破する手法として使用されているものに，総当り攻撃やデータベース構築による攻撃，画像認識による攻撃がある．総当り攻撃は，

日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

2

暗号やパスワード解読に用いられている手法で，理ると仮定すると，ペナルティによる解答不可能な時間論的にありえる全ての組み合わせを入力することでを含め，一日中作業を行った場合でも 1ヶ月以上を要検証を行う．膨大な時間と負荷がかかる計算をコンする．さらに，Petfinder.com に登録されているペッピュータに行わせる単純かつ強引な方法であり，セトは半年で完全に入れ替わることが予想されており，キュリティ分野では広く知られている．データベー

そのことから，1 日に約 10000 枚というペースで画ス攻撃は，CAPTCHA 認証に用いられる画像を蓄積像データベースが更新されることが考えられる．まし，認証テストで出題された画像のハッシュ値と照た，Petfinder.com 上で表示されている画像は，実際合させることで検証を行う．データベースの構築にに蓄積している画像の 10%にも満たない．したがっ長い時間を要するものの，一度構築すると短時間でて，登録されている全ての画像を即時に取得する方法

CAPTCHA 認証を突破することができる．画像認識がなく，常に新しい画像が登録され続けているため，攻撃は，CAPTCHA 認証において広く利用されていウェブスクレイピングによって自動的にデータベーる手法であり，認証テストで出題される画像を識別スを構築することも不可能である．以上のことから，し，文字列の判読や画像の分類を行うことで検証を行

ASIRRA 突破のためのデータベース構築は現実的でう．近年，画像認識の精度が向上し，突破される事例はない．

が増加している．その対策として CAPTCHA 認証の第三に，ASIRRA が用いている画像は，被写体で難読化が進み，人間にも読みづらくなるという問題がある犬や猫の姿勢やアングル，明るさが多様である．

起きている．

ASIRRA を開発した MSR に在籍する専門家は，画ASIRRA では，このような攻撃手法に対して次の像 1 枚につき正答率が 3/5 を超えることは難しいとような対策を行なっている．第一に，認証テストと述べている．そのため，12 連続で正答する確率は約して，12 枚の犬と猫の画像を提示し分類させる問題1/459 となり，これは画像認識による攻撃で 1 回突破を出題している．したがって，ASIRRA は 2 クラスした後にペナルティリストへ登録されることが予想での画像分類を 12 連続で正答する問題を通して人間きる．

を判別するシステムと見なすことができる．総当り

Golle [4] は，画像内の色とテクスチャを特徴量とし攻撃では，2 クラスの画像分類問題について無作為て SVM による分類器を構築し，ASIRRA に対するに解答するため，画像 1 枚につき 1/2 の確率で解く機械的突破を試みている．結果として，分類精度がことができる．そのため，12 連続で正答する確率は82.7%の分類器を作成し ASIRRA 上で実験を行い，1/4096 であり，突破率が極めて低いことが分かる．

突破率は 10.3%を記録している．

また，ASIRRA は 1 つの IP アドレスから 1 日 500
回不正解するとペナルティリストに登録され，その3 画像分類手法

IP アドレスからの解答を数時間不正解扱いとする．

画像分類は，画像中から抽出した特徴となる数値

このことから，ASIRRA に対して総当り攻撃は有効について，機械学習による判断基準の算出を行い，画な手段でないことが分かる．

像が属するクラスを推定する手法である．本研究で第二に，ASIRRA で登録されている画像データベーは，特徴量として SIFT 特徴の出現頻度で表現されたスを常に更新することでデータベース攻撃を避けていBag-of-Keypoints [2] を，また機械学習アルゴリズム

る．ASIRRA で用いられている画像は Petfinder.com

として SVM [1] をそれぞれ用いて分類器を構築する．

[8] というペットの里親募集サイトと提携して取得している．その数はおよそ 300 万枚であり，全ての画3. 1 Bag-of-Keypoints

像に対して犬と猫のラベル付けがされている．そのた

Bag-of-Keypoints(以下，BoK) は，文書分類に用め，スクリプトによって ASIRRA から画像を取得しいられている Bag-of-Words を画像に適用した画像分

データベースを構築するためには，1 秒で 1 枚追加す類における特徴量の表現手法である．Baf-of-Words

日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

3

では，文書を単語の集合とみなし，単語の語順を考

本研究では，犬と猫の分類器を作成するためにソフ慮せず出現頻度の高い単語からなる辞書を作成する．

トマージン SVM を用いる．また，高次元特徴空間へ作成した辞書を用いてカテゴリ毎に出現頻度のヒスの写像を行うために RBF カーネル

トグラムを作成し，特徴ベクトルとする．その一方で BoK は，画像を局所特徴量の集合であるとみなし，得られた特徴量についてクラスタリングを行うこと

K(x, x′ ) = eとカイ二乗カーネル′

K(x, x ) = e

1−σ||x−x′ ||2σ∑li=0(xi −x′ )2ixi +x′i(1)(2)

によって，辞書を作成する．その後，Bag-of-Wordsを用いる．このとき，σ はカーネルパラメータであると同様にして出現頻度のヒストグラムを作成する．

標準偏差，x, x′ は特徴ベクトルを意味する．

本研究では BoK の元になる局所特徴量として，SIFT 特徴 [5] を用いた．SIFT 特徴は，スケール変動

4 個別画像についての分類実験や回転に対してロバストであり，特徴点の検出と特4. 1 評価尺度徴量の記述という 2 つの処理によって行われている．

本節では，ASIRRA 上で検証する前の予備的実験

しかし，特徴点検出によって得られた特徴量を用いるによって得られた結果を示す．結果を示すにあたり，と BoK の性能が下がることが知られている [3]．そこ

本研究では評価尺度として情報検索の性能評価に用で，特徴量のサンプリングについては SIFT による特いられる適合率，再現率，F 値を使用している．適合徴点検出でなく，画像中を一定の間隔，サイズで特徴率は，検索結果の集合に正しい検索対象が含まれてい点をとる Dense Sampling を用いる．サンプリングしる割合であり，情報検索の正確性の指標である．犬とた特徴点は，SIFT 記述子によって特徴量として記述

猫の画像分類において，アルゴリズム上で分類したカされる．特徴点のサイズを半径として，周辺領域を 4テゴリに正しく分類されているか評価することがで× 4 のブロックに分割し，ブロックそれぞれについてきる．適合率を Pprecision ，カテゴリに分類された画8 方向のヒストグラムで表現するため，特徴点 1 つに像の総数を N ，カテゴリに正しく分類された対象画対して特徴ベクトルは 128 次元となる．

像の総数を R とすると，R(3)Nと表す．再現率は，検索対象の集合の中で，実際に検Pprecision =3. 2 SVM
SVM は，教師あり学習の一種であり，未知データ索されている割合であり，情報検索の網羅性の指標でに対して高い汎化能力を持つ識別手法である．各特徴ある．画像分類において，分類対象の画像の中でどのデータ点との距離が最大となるように線形分離する最程度正しくカテゴリ分類されているか評価すること大マージン化問題を解くためのパラメータを学習すができる．再現率を Precall ，分類対象である画像のる．しかし，特徴データ点を線形分離する線形 SVM

総数を C とすると，では，オーバーラップした特徴データを分離することができない．そこで，特徴データを線形分離できるR(4)Cと表す．また，適合率と再現率は互いにトレードオフ

高次元特徴空間に写像することで分離を行う非線形の関係にあるため，2 つの指標の調和平均をとった F

SVM がある．非線形 SVM で利用する，特徴データ値も評価尺度として用いられ，F 値を PF とすると，2Pprecision Precall(5)
PF =Pprecision + Precallと表す．

点の高次元特徴空間への写像を実現するためにカーネル法を用いる．また，特徴データにノイズが含まれる

Precall =可能性が高い．マージン内に特徴データ点が入らないように境界線を引くハードマージン SVM はノイズに4. 2 SVM におけるパラメータ探索よる影響が大きい．そのため，制約をつけることで，本研究で用いる分類器は，ASIRRA のサイトで配マージン内にある程度のデータ点が入ることを許容布している画像データセットを利用して作成する．内するソフトマージン SVM を用いることで対応する．

日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

410.85

C=8C=9C=10
C=11
C=120.805
f-measure

0.9
f-measure

0.81

C=1C=10C=100
C=1000
C=10000
C=100000

0.95

0.8
0.75

0.8
0.795
0.79

0.7
0.785

0.65
0.6

0.78
0.0001

0.01

1

100

10000

0.5

1sigma

図1RBF カーネルに対する指数的なパラメータ変動に

1.5

図23リッドサーチ

訳としては，犬画像が 12499 枚，猫画像が 12498 枚

1C=10^-01C=1C=10^+01
C=10^+02の合計 24997 枚で構成されている．データセットの0.8
f-mesuare

画像それぞれについて BoK を求め，犬画像 5000 枚，習を行う．ここで，分類器の精度を高めるために最2.5

RBF カーネルに対する σ = 0.1, C = 10 周辺のグよるグリッドサーチ

猫画像 5000 枚を学習データとして SVM によって学

2sigma0.60.4

適なパラメータを SVM やカーネルに与える必要が0.2ある．本研究で用いるパラメータはソフトマージン
0

SVM に与える制約パラメータ C と，RBF カーネル

0.00010.01とカイ二乗カーネルに与える標準偏差 σ の 2 つである．この 2 つのパラメータについて，最適な値を網羅的に探索するグリッドサーチを行う．RBF カーネ

図31sigma

10010000

カイ二乗カーネルに対する指数的なパラメータ変動によるグリッドサーチ

ルに対して，パラメータを指数的に変化させることによって行ったグリッドサーチの結果を図 1 に示す．

小であることが分かる．この時点でグリッドサーチ

σ = 0.1, C = 10 の周辺に F 値のピークがみられるたを終了させ，最も大きな F 値をとるパラメータとしめ，さらにフォーカスしてグリッドサーチを行う．グて，σ = 0.7444444, C = 0.8333333 を採用する．こリッドサーチの結果を図 2 に示す． σ が 0.5〜1.5 のの時，F 値は 0.8092079，適合率は 0.8050422，再現区間にあるときピークがみられるものの，F 値の大き率は 0.8134169 となる．

な変動はみられない．これ以上 F 値が大きく向上す

2 つのカーネルのパラメータに対してグリッドサーるパラメータを発見することは見込めない為，この時チを行い，個別画像についての分類精度のピークとな点でグリッドサーチを終了させ，最も大きな F 値をとる値を求めた．カーネルの変更による分類精度の大きるパラメータとして，σ = 0.9791666, C = 8.8333333

な向上はみられなかったが，ASIRRA が画像認識攻を採用する．この時，F 値は 0.7994174，適合率は撃に対して想定している，正答率 3/5 を大きく上回

0.7936382，再現率は 0.8052814 となる．同様に，カることが確認できた．

イ二乗カーネルに対してグリッドサーチを行なった
結果を図 3 に示す． F 値のピークが σ = 1, C = 1 の4. 3 分類結果例

周辺に見られた為，その周辺について再びグリッドRBF カーネルとカイ二乗カーネルそれぞれを適用サーチを行う．その結果を図 4 に示す． σ = 0.8 のした SVM による分類結果の画像例を示す．分類テス

周辺において F 値のピークがみられるが，変動が微トでは，ASIRRA のサイトから取得したデータセッ日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集
0.82

0.805
0.8

2000
frequency

0.81
f-measure2500

C=0.7
C=0.8
C=0.9
C=1.0
C=1.1
C=1.2
C=1.3

0.815

50.7951500
1000

0.790.785500

0.780.775

00.6

0.8

11.2

1.4-4-2sigma

図4024distance

カイ二乗カーネルに対する σ = 1, C = 1 周辺のグ

図5

RBF カーネル適用時の猫画像の境界面からの距離

リッドサーチ
2500

表1

正しく分類された画像の枚数

犬RBF

6409

5929

カイ二乗

6467

6022

frequency

2000

猫1500
1000
500

トと Flickr 猫の画像が 7997 枚，犬の画像が 7499 枚
0

使用しており，2 つのカーネルによる結果のうち，正-4-2

しいクラスに分類できた画像の枚数は表 1 のようになった． その中で 2 つのカーネルから共通して正し

図60distance24

RBF カーネル適用時の犬画像の境界面からの距離く分類された画像は，それぞれ 6242 枚，5781 枚となった．

2500

SVM は，特徴点集合に対して 2 クラスに分離する
2000

よって，境界面からの距離が小さい画像は，画像分類をするうえでの識別が曖昧であることを意味する．分

frequency

ような境界面を決定することで識別を実現している．

1500
1000

類テストで使用した画像の特徴量の境界面からの距離500についてのヒストグラムを図 5，6，7，8 に示す．境0

界面を 0 として，正の方向が犬クラス領域，負の方-4向が猫クラス領域を意味している．RBF カーネルを適用した場合では，カイ二乗カーネル適用時と比較し

図7-20distance24

カイ二乗カーネル適用時の猫画像の境界面からの距離て猫と犬それぞれの画像の境界面からの距離が大きくばらついていることが分かる．

が全て写っており，画像内領域の大部分を占めている

猫画像について，正しく分類され境界面からの距離傾向にある．それに反して，境界面からの距離が小さが大きいものを図 9，距離が小さいものを図 10，正い，猫クラスへ属する判定が曖昧な画像は，顔のパーしく分類されず境界面からの距離が大きいものを図ツが一部写っておらず，分類対象が画像内を占める割

11，距離が小さいものを図 12 に示す．正しく分類さ合が低い傾向にある．また，人に抱きかかえられたもれ境界面からの距離が大きい，明らかに猫クラスに属のや，顔が大きく傾いているものは正しく分類されなすると分類器に判定された画像は，猫の顔のパーツいことが多い．BoK は，局所特徴量の出現頻度で表日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

62500

frequency

2000
1500
1000
500
0-4-2024

図 11

正しく分類されず境界面からの距離が大きい猫画像

図 12

正しく分類されず境界面からの距離が小さい猫画像

distance

図8

カイ二乗カーネル適用時の犬画像の境界面からの距離像を分類するにあたって，被写体が画像を占める割合や姿勢が影響することが分かった．猫と犬に対して姿図9

正しく分類され境界面からの距離が大きい猫画像

勢や被写体のサイズの変動にロバストな特徴量を導くことが今後の課題である．
また，ASIRRA の認証を突破するためには，12 枚の画像を正しく分類する必要がある．現段階の分類器で 12 枚の画像を正しく分類する確率は，高々1/10に満たないと考えられる．分類器と合わせて，正しく分類する確率を向上させるための手法を検討することも必要である．

図 10

正しく分類され境界面からの距離が小さい猫画像

参 考 文 献現されているため，被写体のサイズが分類に影響を与えることが考えられる．

5 まとめと今後の課題
ASIRRA に対する突破の検証を行うために，BoKによる特徴量表現と SVM による機械学習によって分類器を構築し，個別画像についての分類実験を行った．RBF カーネルでは，F 値が 0.7994174，適合率が 0.7936382，再現率が 0.8052814 となり，カイ二乗カーネルでは，F 値が 0.8092079，適合率が0.8050422，再現率が 0.8134169 を記録している．画[ 1 ] Cristianini, N. and Shawe-Taylor, J.: An Introduction to Support Vector Machines and otherkernel-based learning methods, Cambridge University Press, 2000.
[ 2 ] Csurka, G. and Dance, C. and Fan, L. andWillamowski, J. and Bray C.:Workshop on statistical learning in computer vision, ECCV 1, 2004,
pp. 1-22.
[ 3 ] Nowak, E. and Jurie, F. and Triggs, B.:Sampling
Strategies for Bag-of-Features Image Classification,
ECCV 2006 Lecture Notes in Computer Science Volume 3954, 2006, pp. 490-503.
[ 4 ] Golle, P.:Machine Learning Attacks Against theAsirra CAPTCHA, ACM CCS2008, 2008, pp. 535542.

日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集[ 5 ] Lowe, D.:Distinctive Image Features from ScaleInvariant Keypoints, International Journal of Computer Vision, Volume 60, Issue 2, 2004, pp. 91-110.
[ 6 ] ASIRRA.:http://research.microsoft.com/en-us/

7

um/redmond/projects/asirra/.
[ 7 ] The oﬃcial CAPTCHA site.:http://www.captcha.
net/.
[ 8 ] Petfinder.com.:https://www.petfinder.com/