The 28th Annual Conference of the Japanese Society for Artificial Intelligence
，
2014- 1 -
Arnold’s CATMAP
ナ
ク
用い
CAPTCHA
開発
Proposal of CAPTCHA system using the complex dynamics of Arnold's CATMAP
井
聡
*1*2
Satoru Inoue
*1
埼玉
業大学大学院
学研究
*2
埼玉
業大学
学部
Graduate school of Engineering, Saitama institute of Technology Faculty of Engineering, Saitama institute of Technology
In this paper, we propose and investigate the new CAPTCHA system based on the dynamics of Arnold's CATMAP. Our system is aimed to improved its performance through the tuning test which searches the readable words from the images changing periodically.
1.
じめに
ン ー ッ WEB ー 利用 新規
ン 作成 や ン ン投票 行う ， 応答者
ン ー や人 知能技術 用い ー ン ，実
人 間 応 答 い 確 認 ，CAPTCHA
呼 ン / ン 型 認 証 行 わ 近
増加 い ．基 的 CAPTCHA ，文 列 読
取 能 力 問 う 人 間 機 械 行 う あ ． 文
列 歪 や 付加 画像 Web ー 提示 ，
ー 読 否 試 ． 文 認 識 技 術
やパ ーン 類技術 高度化 ， 認証 OCR
代 表 文 読 取 ー ン 突 破 う
あ ， 対 う CAPTCHA 課題 過剰 難化
， 人 間 自 体 課 題 解 ， う 認 証
ッ ワーク利用時 害 い， 来 目的 果
い 転倒 事例 散見 。 認証 利用 課題
キ 確 保 観 点 大 量 用 意 必 要 あ ，
技術 用い 運用 困難 い 要因 1
い 。 近 文 列 用い CAPTCHA 異
新 い方式 CAPTCHA 期待 い ． 研究 画
像 利用 CAPTCHA 的 ナ ク
Arnold's CATMAP 画 像 変 換 用 い 提 案 ，
CAPTCHA 課 題 過 剰 難 化 避 ， 認 証
堅牢性 維持 ， 運用 軽減 構築 目
指 。
2.
関連研究
現 在 CAPTCHA 機 械 読 い 文 列 読 能
力 試 ，人間 機械 区 方式 普及 い ．
，OCR 文 読 取 向
人間 い ー ン CAPTCHA 解答
可 能 ． ， 正 利 用 防
文 列 画 像 難 読 化 繰 返 行 わ ， 過 剰 難 化
機 械 人 間 読 困 難 文 列
． 近 う い 問 題 解 消 文 列 読 取
プ 方式 異 CAPTCHA 提案 ．以 2
CAPTCHA 示 ．
2.1 Assira
Asirra 画像認識能力 試 CAPTCHA 一 ，複数
画 像 2 類 プ ，応 答 者
属 性 定 方 式 あ [Elson 2007]．解 答 者 提 示
12枚 猫 犬 画像 猫 画像 選び出 ．提示 猫
犬 画 像 付 ， 解 答 者 答 え 一
致 い 場合 応答者 人間 あ 定 ．猫 犬 類
人 間 直 観 的 行 う 可 能 あ 負 荷 少
利便性 高いCAPTCHA あ ． Asirra 対 回避
策 ，機械学習 用い 画像認識攻撃 ー ー 攻撃
挙 い ．2 ク 類 問 題 得 意 ー ク
ー ン SVM 機械学習 器 Asirra 有
効 あ ， 使 用 画 像 ー ー 短 期 間 大 変
化 出 来 い ー ー 攻 撃 対 弱
あ 考え 。
2-1． Assira 実行例
2.2 SS-CAPTCHA
画 像 認 識 能 力 試 CAPTCHA 異 方 式
SS-CAPTCHA いう 違和感 能力 試 CAPTCHA
提 案 い ．SS-CAPTCHA[山 2009] 解 答 者 人 間
作 成 自 然 文 章 機 械 的 出 力 自 然 文 章 複
数 提 示 ， 中 自 然 文 章 選 び 出 出 来 否
人 間 機 械 定 ． 文 章 対 自 然 自 然
人間 容易 ，機械 自然言語 完全
解 釈 困 難 あ ． 人間 自然 文章
自然 文章 生成 人手 必要 ，膨大
パ ーン 用意 難 い 考え ．
3.
提案手法
一般的 文 列 CAPTCHA 文 読 取
解読 う可能性 あ ，提示 文 列画像
機 械 的 生 成 可 能 ー ー 攻 撃 対 耐 性
高い． 提示 文 列 入力 作業 人間
連 絡 先 ： 井 聡 ， 埼 玉 業 大 学 学 部 ， 埼 玉 県 深 谷 市 普 済
寺 69 ， e@ .ac.
The 28th Annual Conference of the Japanese Society for Artificial Intelligence
，
2014- 2 -
わ 単 純 あ ， 読 可 能 あ 誤 解 答 や 誤 操 作
起 い．一方，画像CAPTCHA ー ー 攻撃や
画 像 認 識 攻 撃 対 弱 傾 向 あ ， 人 間 機 械 画
像 認 識 能 力 差 依 然 大 様 々 方 式 CAPTCHA
提 案 後 発 展 期 待 い ． 以 勘 案
うえ 稿 Arnold's CATMAP ナ ク 用い 画
像認識能力 文 列 読 取 能力 要求 CAPTCHA
提案 ．
3.1 Arnold’s CATMAP
Arnold's CATMAP ，パ 変換 呼 現象
一 ， 数学者 Vladimir I． Arnold 猫 画像 用
い う呼 う [Peterson 1997]．パ
変換 ，パ 生地 伸 ， い
う 程 繰 返 行う 生地内 含有物 最 効率 混
いう 数学的 化 あ ． CATMAP
線形写像 次式 通 あ ．
xn+1，yn+1 =(xn+yn，xn+2yn) mod N (1)
一辺 N ク 正方形 画像 横方向 2 倍，
縦方向 3倍 引 伸 ，元 画像 取 ，
画像 変換 行わ ．
3-1． Arnold’s CATMAP 画像変換
3.2 システム 概要
提 案 手 法 CATMAP 変 換 画 像 解 答 者 簡
易 操作 復元 ，画像中 文 列 解答 画像
能 力 文 読 取 能 力 双 方 問 う
CAPTCHA あ ． 稿 ，CATMAP 任意
ップ変換 画像 変換画像．変換前 画像 元画像 呼
称 ．提案手法 出題 解答 手順 次 通 あ ．
出 題 者 出 題 単 語 ン 複 数 選 択 ， 正 方 形
画 像 配 置 元 画 像 作 成 ( 3-2 )． 元 画 像
CATMAP 変換 ，変換画像 作成 ． 時 変換
回 数 画 像 困 難 十 ， 秘 匿 性 高
ン 回 数 行 う． 作 成 変 換 画 像 質 問 画 像
解 答 者 提 示 3-2 右 ．次 解答者 提示
質問画像 CATMAP 変換 行う 1 ップ
変換 ，元画像 書 文 列 読 取 解答 ．最後
出題者 解答者 答え 選択 単語 確認 ，一致 い
場合解答者 人間 断 ．
3-2 変換前画像 初期提示画像 右
3.3 CATMAPによる変換画像作成
変換画像 作成 文 列 記述 元画像 CATMAP
変換則 従 作成 ．元画像 CATMAP 変換 則 1
ップ 変換 変換画像 ，あ 程度文 列 読 取
可能 あ ( 3-3)．
3-3 元画像 1 ップ変換後 画像
回作成 CAPTCHA 一辺 200 ク 元画像
用い 変換画像 生成 い ．一辺 200 ク 正方
画 像 CATMAP 変 換 場 合 ， 元 画 像 復 元
150 ップ 要 ． ，30 ップ周期 3-6 示
う 各単語 重 合 う 画像 ． 出題
用い 変換画像 初期状態 元画像 30〜120 ップ
範 ン 変換 行 使用 ．
3.4 解答者へ 質問
提案手法 解答者 提示 変換画像 CATMAP
変換 元画像 復元 行い，画像中 文 列 読 取
行 う ． 出 題 者 解 答 者 答 え 正 い 場 合 解 答 者 人
間 ． 質 問 解 答 プ 以
。
出題プ
1． 一辺 200 ク 正方形画像 英単語 3 選択
配置 行い，元画像 生成 ．
2．生成 元画像 CATMAP 変換 ．変換回数
30 120 ップ 範 ン 行う．
3．変換 行 画像 解答者 提示 ( 3-2右)．
解答プ
I．解答者 提示 画像 文 列 有無 確認 ．
II． 読 可 能 文 列 画 像 中 見 い 場 合 ，解 答
者 画像 CATMAP 変換 次 ップ 変換 ．
III．変換 行 画像 文 列 有無 確認 ．
IV．以降，II，III 繰 返 ，文 列 含 画像 探 ．
V． 読可能 画像 変換 ，画像 文 列 読 取
3 英単語 答え ． 時，解答者 必 変換画像
元画像 復元 必要 ，あ 頻度 出現 単語 重
合 状態 画像 解答 行う 可能 あ 3-4 ．
The 28th Annual Conference of the Japanese Society for Artificial Intelligence
，
2014- 3 -
4.
検討
4.1 利便性について 検討
提 案 手 法 利 便 性 い 検 討 行 う ． 既 文 列
CAPTCHA 提 案 手 法 比 較 場 合 ， 解 答 者 提 示 画
像 生 成 若 処 理 必 要 運 用 性 関
大 差 い 考え ．CAPTCH 人間 解答者
大 負 担 え い 望 ． 提 案 手 法 解 答
者 対 負 担 評 価 実 験 行 ． 実 験 被 験
者 提 案 手 法 CAPTCHA 解 答 い ，解 答 時 間 誤
解答数 計測 ．実験 一辺 200 ク 画像中
3 単 語 配 置 元 画 像 用 い ． 元 画 像 初 期 変 換 回
数 30〜120 ップ 間 ン 行う． 評価実験
10人 被験者 5問 解答 ．
4-1 実験 用い 解答 ン ー
実験 行 結果，提案手法 CAPTCHA 課題 解
答 要 時 間 均 34 ． 既 文 列
CAPTCHA 所要時間 約10 18 程度 あ ．既
文 列 CAPTCHA 比較 提案手法 解答時間 長
い ．解 答 所 要 時 間 ，提 示 画 像 初 期 変 換 ッ
プ数 依 ， 勘案 結果 実用的 所要
時 間 大 逸 脱 い 考え ． 誤解答
数 50 問中 4 回 いう結果 得 ．誤解答 解答
ほ 解答者 復元途中 画像 単語 読 取 う
場 合 発 生 い ． 連 続 誤 解 答 一 度
． 結 果 ， 提 案 手 法 正 答 率 92% 既 CAPTCHA
比 較 高 い 正 答 率 得 ． 提 案 手 法
誤解答 解答者 負担 少 い 考え ．
4.2 安全性について 検討
提案手法 画像認識能力 文 読 取 能力 双方 試
CAPTCHA あ ． 3．4 述 通 提案手法 解答者
提示 う 画像 CATMAP変換 ，文 情
報 含 画像 否 断 ．文 情報 持 い画像
断 場合，再度 CATMAP変換 行う．変換 解答者 文
情報 含 画像 発見 繰 返 探索 ．解答者
発見 文 情報画像 文 列 読 取 行う ，画像中
文 列 重 合 読 取 困難 あ 場合，再度探索
行 い 読 取 可 能 画 像 探 ． 読 取 可 能 文 列
含 画像 文 列 読 取 解答 行う． 安全性
い 画 像 認 識 文 読 取 基 的 耐 性 備 え い
言え ． 多 画像認識 用い CAPTCHA 威
ー ー 攻 撃 対 提 案 手 法 攻 撃 耐 性 示
． ー ー 攻撃 CAPTCHA 出題 問題 答え
記 録 ー ー 構 築 ， 記 録 問 題 出 題
ー ー 利用 機械的 解答 攻撃 あ
．画像認識能力 問うCAPTCHA 対 ，出題 問
題 取 込 ， 画 像 類 行 い 解 答 用 ー ー 構
築 ．画像CAPTCHA い 問題 使用 画像 解
答 者 提 示 い ， 攻 撃 者 ー ー
構築 防 困難 あ ．攻撃 対 対 策 ，使
用 画 像 枚 数 多 ー ー 構 築 労 力
増 大 効 果 的 ， 必 要 画 像 収 集
ー 提供者側 労力 増大 う．提案手法 い
提 示 画 像 生 成 文 列 配 置 元 画 像 用 い い ．
写真 用い 画像 CAPTCHA 異 ，出題
異 画像 生成 ー ー 攻撃 高い耐性
持 言え ．
次 OCR 文 読 取 用い 攻撃 対
耐 性 い 示 ． 一 般 的 文 列 CAPTCHA 文
列 や歪 付加 画像 解答者 提示 ，
解 答 正 誤 人 間 機 械 ． 文 列
CAPTCHA 画 像 中 文 列 読 試 あ
，OCR 文 読 取 用 い 攻 撃
突破 危険性 あ ．提案手法 解答者 対 提示
画像 文 列 読 可能 状態 提示 ．
提示 状態 画像 OCR 用い 文 読 取
い． 画像 CATMAP変換 行い文 情報 検
索 行 う 可 能 ， 文 情 報 持 画 像 ， 復
元 途 中 現 文 重 合 状 態 画 像 元 画 像
行 わ い ， 機 械 既 攻 撃 方 法
提案手法 解答 困難 あ 考え ．
5.
まとめ
稿 CATMAP 画像変換 用い CAPTCHA
提 案 ． 提 案 手 法 画 像 認 識 能 力 文 読 取 能 力
両 方 試 ， ー ー 攻 撃 や 画 像 認 識 攻 撃 対
耐 性 あ 考 え ． 利 便 性 い ー ッ ク
人 間 攻 撃 考 慮 うえ ， 難 易 度 設 定 や ー
ン ー 開 発 行 う 必 要 性 あ ． 堅 牢
性 確 保 ，現 在 固 定 い 画 像 縦 横 ク
数 可 変 ， 実 装 時 有 用 性 考 慮 ， 画 像
ク 比 1:1 い 構築 後
課題 いえ ．
参考文献
[Elson 2007] J.Elson, J.Douceur, J.Howell, J.Saul: Asirra; a CAPTCHA that exploit interest-aligned manual image categorization, 2007 ACM CSS, pp.535-542, 2007.
[山 2009] 山 匠, 西垣正勝, J.D.Tygar: 機械翻訳 違和感
用 い CAPTCHA 提 案, 情 報 処 理 学 会 研 究 報 告.
CSEC, [ ン ー キ ]. 2009(37), p. 1-8, 2009
[Bursztein 2010]E. Bursztein, S. Bethard, J. C. Mitchell, D. Jurafsky, and C. Fabry, “How good are humans at solving CAPTCHAs? a large scale evaluation,” Proc. IEEE S&P, 2010.
[小林 2010]小林司, 藤堂洋 , 森井昌克:画像認識 困難性
利用 CAPTCHA 方式 提案, 電子通信情報学会信学
