マルコフ連鎖による合成文章の不自然さを用いたCAPTCHAの安全性評価と改良について

Presentation on theme: "マルコフ連鎖による合成文章の不自然さを用いたCAPTCHAの安全性評価と改良について"— Presentation transcript:

1 マルコフ連鎖による合成文章の不自然さを用いたCAPTCHAの安全性評価と改良について
東海大学大学院 工学研究科情報理工学専攻 ○鴨志田芳典　菊池浩明 2012/07/04 DICOMO2012

2 CAPTCHA CAPTCHA 文字列画像変形CAPTCHAの脆弱性 プログラムによるアカウントの大量取得対策など
(Completely Automated Public Turing test to tell Computers and Humans Apart) プログラムによるアカウントの大量取得対策など 文字列画像変形CAPTCHAの脆弱性 より高性能なOCR機能を持つ攻撃 大量の人手による攻撃 (リレーアタック・クラウドサーチング) 機械にとっては解答困難な問題を利用することで、人と機械とをより分ける。

3 関連研究 人間の高度な認知処理を用いたCAPTCHA
Assira[3] J. Elson，J. Douceur，J. Howell and J. Saul 2007 ACM CSS, pp , 2007． 特定の特徴を持つ画像を選択させるCAPTCHA 機械翻訳の違和感を用いたCAPTCHA[6] 山本匠，J. D. Tygar, 西垣正勝 CSEC-46 No. 37，2009． 文章の自然さ、不自然さを認識する事の困難さを利用

4 マルコフ連鎖による 合成文章の不自然さを用いたCAPTCHA
合成された文 (Spam)と人の書いた文(Ham)を順次提示 それぞれ不自然，自然を判断させる 正しく判断できた回数kが閾値θ以上ならばCAPTCHA成功 不自然な文としてワードサラダを合成する． ワードサラダ：マルコフ連鎖モデルを利用した合成文章 スパムの大量投稿に利用されている 文法が正しく合成される傾向があり，検出が困難 ある程度以上の語学力が無ければ，判断は難しい Question!! ラク・オバマ大統領の紛争や 国民に対して政治的に殆ど 被害を謳歌している。 自然! Answer!! 不自然!

5 要素技術：マルコフ連鎖による文章合成 単純マルコフ連鎖モデル(n=1)を用いる場合
今日は雨が降った。 今日は気温が高い。 入力(コーパス) 気温 高い 1/2 1/2 1/1 1/1 1/1 。 が 今日 は 1/1 1/2 1/2 雨 降った 出力例：今日は気温が降った。

6 本日の発表 文章校正を用いた攻撃に対する耐性の評価 より良い出題条件の検討 日本語以外への言語への適用

7 文章校正を用いた攻撃に対する耐性の評価 校正使用 総当り攻撃 23% ８％ 図4 認証成功率 閾値θ(k)
このとき，ｓ回のCAPTCHA審査にk回誤答する確率は，確率Pqの二項分布で表すことができる． ８％ 閾値θ(k)

8 実験2：実験内容 目的 評価データ 内容 文章校正ツールによる検出の精度の調査 n=1, 2, 3のワードサラダとニュース記事の切り取り
各300文 内容 評価データについて，Microsoft Word2007による文章校正が行われる確率を調査 タイプミス(赤線)、要検討（緑線）を共に校正が行われたとして、１箇所でも校正が行われた文は校正されたと扱う.

9 実験2：実験結果 実験結果 検出された例 第二次世界における影響力は、各国の影響力を樹立していったのクリストファー・検閲等から遠洋捕鯨が民間に送られてさらに各地から購入した。 表４：文章校正が行われた確率P(W|X=S) 書き間違いとして検出

10 一題当りの校正率から確率を纏める CAPTCHA 一題辺りの検出（文章校正）が行われる確率P(W)
　 CAPTCHA中のSpamの割合×Spamに校正が行われる確率 ＋CAPTCHA中のHumの割合×Humに校正が行われる確率　 = 0.24× ×0.75 = 0.06 CAPTCHA P(X=S)=0.25 P(X=H)=0.75 Spam Ham 校正無 P（W|X=S）P(X=S) =0.19 全体の中で検出が行われる割合 P(W)＝0.06 　 P（W|X=H）P(X=H) ＝0.75 　 P(W|X=S) ×P(X=S)=0.06 P（W|X=S）P(X=S) =0.06 校正有 P(W|X=H)P(X=H)=0 P(W|X=H)P(X=H)=0 10

11 機械の正解率を求める 機械の正答率 判定 検出 X=S X=H W P(X＝S|W) ＝1 P(X=H|W) ＝0 ＝0.2
　　　　　　　　　判定 検出　　 　 X=S X=H W 　 P(X＝S|W) ＝1 P(X=H|W) ＝0 ＝0.2 　P(X=H|W) ＝0.8 表７．出題と機械判定の条件付き確率P(Yw|X) 今回の場合では，検出された時必ずSpamと判定し, 検出されない時は0.8の確率でHamと判定する. (校正されないからといってHamと断定する事は出来ない) 　　　 判定 入力　　 　 Yw=H Yw=S X=H 0.798 0.202 X=S 0.394 0.606 機械の正答率

12 実験２：評価 校正使用 総当り攻撃 23% Pw＝0.697 Pr=0.625 Pq＝0.135 図4 精度 閾値θ(k)
このとき，ｓ回のCAPTCHA審査にk回誤答する確率は，確率Pqの二項分布で表すことができる． Pr=0.625 Pq＝0.135 12 閾値θ(k) 12

13 評価3.1 より良い出題条件の検討 P(X=S,Yw=S) 機械の正答率Pw Spam出題率P(X=S) P(X=S)=0.55の時
評価3.1　より良い出題条件の検討 1.0 P(X=S)=0.55の時 最低値を取る 0.8 校正使用 P(X=S,Yw=S) 機械の正答率Pw 0.6 総当り 0.4 0.2 機械にとってはHamが多い方が都合が良い． 人にとってはSpamが多い方が都合が良い． 0.2 0.4 0.6 0.8 1.0 Spam出題率P(X=S)

14 評価3.2 より良い出題条件の検討 P(X=S)=0.45の時 EER＝15% FAR P(X=S)=0.50の時 よりも精度が良い．
評価3.2　より良い出題条件の検討 1 0.1 P(X=S)=0.45の時 EER＝15% FAR 0.01 P(X=S)=0.50の時 よりも精度が良い． これは他の選択式のCAPTCHAにも応用できる可能性がある。 0.001 FRR 0.0001 0.0001 0.001 0.01 0.1 1

15 3. 日本語以外への言語への適用 実験３ 目的 内容 評価データ 被験者 提案手法を他言語へ適用する為の条件を調査する
3.　日本語以外への言語への適用 実験３ 目的 提案手法を他言語へ適用する為の条件を調査する 内容 各言語の評価データを順次提示し，正答率を計測 評価データ Wikipediaのアメリカ合衆国の記事の本文から合成した Spam (n=1,2,3)各10題と本文の一部切り取り(Ham)10題 計40題 被験者 日本人学生3名，イギリス，中国，タイ人学生それぞれ1名

16 例：英語ワードサラダ（Spam） スペースを区切りとし、括弧表現()を取り除いた． n=1 n=3
Farther west of the Dutch ceded their establishment of New Amsterdam on the United States is the north to the U.S. s American Revolution, with an American Civil War of Alaska's most recent state-eight national economy is a strong central North American is sub arctic or polar. n=3 The United States also possesses five major overseas territories: Puerto Rico and the United States displaced native tribes, acquired the Louisiana territory from France, Florida from Spain, part of the Oregon Country from the United Kingdom, Alta California and New Mexico from Mexico, and Alaska from Russia, and annexed the Republic of Hawaii.

17 例：タイ語ワードサラダ コーパスの分かち書きは， タイ人留学生に依頼し手作業で行った． n=1
ที่ราบชายฝั่งแอตแลนติกเป็นประเทศจึงรับอิสรภาพ ผลของสหรัฐอเมริกา โดยในอีกครึ่งศตวรรษต่อมาอย่างรวดเร็ว ขบวนการตรวจสอบและวัฒนธรรมของฝ่ายมหาอำนาจกลางตกต่ำครั้งที่สามารถเอาชนะของแอฟริกันเพียงแต่ระดับชาติเข้ามาจากความขัดแย้งทางการโจมตีค่ายซัมเตอร์ของประเทศ ซึ่งได้ประกาศ และยุติการค้าทาสแอฟริกันอเมริกัน ถึงแม้ว่าเป็นพลเมืองของป่าไม้ไม่ผลัดใบเข้ามาเป็นประเทศเศรษฐกิจ การทำให้รัฐกสิกรรมทางการบังคับแห่งชาติที่รู้จักกันมากอพยพจากข้อมูลของฝ่ายสมาพันธรัฐเป็นการเลิกกฎหมายในพื้นที่ครอบคลุมส่วนใหญ่ในสงครามยุติ รัฐสภาไม่นับรวมกับรองลงสมัครรับความกระตือรือร้นของประเทศไป

18 実験３.実験結果 言語 n=1 n=2 n=3 自然文 日本 0.87 0.47 0.20 0.90 英語 1.0 0.8 0.6 0.7
P(Y=S,X=S) P(Y=H,X=H) 言語 n=1 n=2 n=3 自然文 日本 0.87 0.47 0.20 0.90 英語 1.0 0.8 0.6 0.7 中国 0.5 タイ 正解率がnの増加につれて低下する事が、実装の正しさを表している。 提案方式で使用するn=1のワードサラダ(Spam)において， 高い確率で不自然と判定出来るという結果．

19 考察 タイ語では，全ての場合で不自然に見える それ以外の言語では，理想的な結果が得られた 文節記号がない為，文の終了条件を学習出来ない
形態素解析を手動で行った それ以外の言語では，理想的な結果が得られた それぞれの言語で文法等は大きく異なる 適切な形態素解析が他言語への適用条件

20 おわりに 結論 文章校正による検出で提案手法の精度は８％低下する． 攻撃者の判断の精度を考慮して出題を調整する事により精度は８％向上した．
適切な形態素解析を行えれば，提案手法は日本語以外にも適用可能である． 今後の課題 他のスパム検出法を用いた場合との精度の比較 問題に含まれるスパムの割合を一定にしない場合の精度の評価 提案手法において，検出され得るスパムを予めに除去する機能の追加 他言語への適応についての再実験

21

22

23 実験３：実験結果1 文章量による正答率 １行 ５行 増減 自然な文 (n=5) 0.91 0.59 +0.32 ワードサラダ(m=10)
0.73 0.99 -0.27 文章量による応答時間[秒](N=1) 自然な文 (n=5) 8.05 21.07 -13.2 ワードサラダ (m=10) 6.19 13.2 -7.01 不自然な箇所が現れる確率が下がるため， ワードサラダを判別できる確率は低くなっている． しかし，自然な文を判別する確率は上がっている． 少ない文字数の文章が自然であることを判断する事は容易であるためと考えられる． （文字数が多いとどっか１箇所不自然だと思ってしまうと，全体が不自然な文章になる．） このため，少ない文字数の中に確実に不自然な箇所を加えられれば， パフォーマンスの向上が可能であると推察できる．

24 実験３：実験結果2 表２：文章量による正答率 N=1 N=2 N=3 自然な文 (n=5) 0.91 0.80 0.68
ワードサラダ(m=10) 0.73 0.62 0.45 表３：文章量による応答時間[秒] 自然な文 (n=5) 8.05 8.12 7.44 ワードサラダ (m=10) 6.19 7.76 8.58 不自然な箇所が現れる確率が下がるため， ワードサラダを判別できる確率は低くなっている． しかし，自然な文を判別する確率は上がっている． 少ない文字数の文章が自然であることを判断する事は容易であるためと考えられる． （文字数が多いとどっか１箇所不自然だと思ってしまうと，全体が不自然な文章になる．） このため，少ない文字数の中に確実に不自然な箇所を加えられれば， パフォーマンスの向上が可能であると推察できる．

25 文章量によるERRの比較 必要時間 151.7秒 θ=15 のとき， FRR=0.043, FAR=0.02 また，最小 EERは0.031
必要時間　151.7秒 θ=15　のとき， FRR=0.043, FAR=0.02 また，最小 EERは0.031 0.031

26 改善案の検討 問題文を短くする より不自然な文を合成するように， ワードサラダを調整する． 今後実験予定 2.1 コーパスサイズの拡大
2.1 コーパスサイズの拡大 2.2 より適切なコーパスの選択 今後実験予定 2.3 マルコフ連鎖の遷移確率の操作 2.4 ワードサラダの検出手法の応用

27 おわりに 今後の課題 マルコフ連鎖による合成文章を利用した CAPTCHAを提案した．
提案手法は，最適な条件下では，人間拒否率及び機械受け入れ率2%の精度と，308.75秒のパフォーマンスで検査が可能である事を示した． 文章の不自然さの理解を用いた問題は， リレーアタックに耐性を持つ事を示した． 今後の課題 実験2:留学生による主観評価の再実験 提案手法の実装実験 より短い文章量で不自然さを確保できる文章合成方法の検討 n, m, θを一度のCAPTCHA毎に可変とした時の評価

28 実験結果：正答率 不自然な文書に対する正答率k/m 日本人： 0.9875 ±0.04 (N=1)
自然な文書に対する正答率k/ n 日本人： 0.59±0.19 留学生：　　※ 0.50　 ※実験を行っていないため，暫定的に最低値とした 凡そ0.2ポイントの差 X軸，Y軸の説明を明確に 1連鎖サラダの正解率が日本人でもっとも高いこと 留学生との間に差があること 日本人の自然な文に対する正解率は59%であること 留学生のものは暫定的に最低値の50%とすること センテンス

29 実験結果：応答時間 センテンス X軸は同様 Y軸は時間であること 1連鎖の応答時間がもっともばらつきが少なく，
留学生との間に差が出ていること これらの事から，1連鎖のワードサラダで問題を作ることが最も妥当であること． センテンス

30 ワードサラダの文章合成例 単純マルコフ連鎖（N=1） ３階マルコフ連鎖(N=3)
基本方針を含め、罰金の３１４年に丸投げした。本人を受け、12月中旬に目先の寄付を記載する二つの辞任を導入し、まじめに同額の事務所は、実際は50％台に組んだ４７千万円の数百万円単位の運営する政治主導した。 この３億円を含め、新生党と自由党の解党時の残金２２億円余が、小沢氏関連の３つの政治団体に移されていたことが、関係者への取材で分かった。鳩山首相は不起訴だったとはいえ、政治的責任は極めて重大である。

31 関連研究 山本匠，J. D. Tygar, 西垣正勝 機械翻訳の違和感を用いたCAPTCHA の提案 コンセプト
提案，情報処理学会研究報告, CSEC-46 No. 37，2009．　　より図を引用．

32 閾値θについてのFRRとFAR (n=5,m=15)
CAPTCHAとして適切なパラメータ n=5, m=15の20題のとき 正解数kの閾値θ=15で EERは最低値を取る． 閾値θをいくつに設定するかによる，FARとFRRのグラフ。 FAR=FRRとなる点＝EERは，閾値θ＝15のときに2%となる． したの二つは，nとmの割合を変えたときのもの． 左下がn=5,m=5.右下がn=5,m=10のとき。 EERとなる点がn=5,m=15のときよりも高くなっている事が見えればおｋ

33 ワードサラダの割合による 精度の変化 n=5, m=15の20題 正解数kの閾値θ=15 この時， FRR及びFARは2% 0.155
0.049 0.02 n=5, m=15の20題 正解数kの閾値θ=15 この時， FRR及びFARは2%

34 実験 文字列変形CAPTCHAとの比較 目的 広く利用されている文字列変形CAPTCHAとの精度とパフォーマンスの違いを調査する．
CAPTCHA公式サイトに提示されているCAPTCHAデモプログラムを利用し，2名に20回ずつCAPTCHAを行わせ，成功率と必要時間を計測する．

35 従来手法との比較：結果 FRR FAR 必要時間 リレーアタック 提案手法 (マルコフ) 2% 307.85秒 58% 文字列 画像変形
0% 9.74秒 耐性低

36 過去研究：日本人による主観評価 実験内容 日本人学生9名と留学生3名に対し評価データを100件で提示し, コンピュータで合成された文章か否かを判定させ, 正答率と応答時間を計測する. 評価データ 5000文字程度の政治・経済に関する記事から合成 作文方法 件数 ワードサラダ (Order N = 1,…,4) 40題 センテンスサラダ 10題 コーパスの一部抜粋 50題 計100題

37 実験3:日本人による主観実験２ 目的 文章量と正答率k/n, k/mの関係を調査する．
7名の被験者に対し，1行の文からなる評価データをn=5,m=10,s=15の条件で順次提示し，被験者に自然か不自然かを判断させ正答率k/n, k/mと応答時間を計測する．

38 評価方法 CAPTCHA1問あたりの成功/失敗率を以下の同時確率で与える． これらをまとめて，CAPTCHA失敗率Pqを以下のように定める．
出題が自然な文章である確率と同時に，解答が自然である確率 と、逆。 ちなみに， これらをまとめて，CAPTCHA失敗率Pqを以下のように定める．

39 評価：１ 判別文書 入力文書 Y=H Y=S X=Human 0.59 0.41 X=Spam 0.01 0.99
Order n=1, の時の条件付確率P(Y|X) 判別文書 入力文書 Y=H Y=S X=Human 0.59 0.41 X=Spam 0.01 0.99

40 実験2 タイ語ワードサラダの文章量

41 留学生と日本人との精度の差 精度に27%の差

42 文章量による精度の変化 総当たり攻撃を想定した時， 自然な文の出題数 h=15 スパムの出題数 s=5 総問題数 c=20
正解数kの閾値Θ=15　の時， EER = 3.7%　

43 提案手法：概要 正解数 k = 3 閾値 θ = 4 とした場合 自然な文書数 h = 2 不自然な文書数 s = 3
問題１：自然な文章 解答１：自然 問題２：不自然な文章 解答２：不自然 問題３：自然な文章 解答３：不自然 問題４：不自然な文章 解答４：不自然 問題５：不自然な文章 問題５：自然 正解数 k = 3 閾値 θ = 4　とした場合 自然な文書数 h = 2 不自然な文書数 s = 3 全体の問題数　 c = 5 正答率Pq = k/c = 3/5

44 リレーアタック 26714 攻撃者のWebサイト 低賃金労働者 3．CAPTCHA問題閲覧 2.問題転載 4．解答送信 5.解答取得
6．アカウント取得 １．CAPTCHA問題取得 攻撃プログラム

45 提案手法：方法 Webからのコーパス収集 n階マルコフ連鎖による文章合成 CAPTCHAによる検査 自然な文書h個，不自然な文書s個からなる
解答の方法は「自然」か「不自然」の二択 正解数kの値が閾値θ以上ならCAPTCHA成功

46 提案手法：概要 合成された文と人の書いた文を順次提示する．
出題に対して自然・不自然を正確に判断できた回数を正解数とし，正解数が閾値以上であればCAPTCHA成功とする．

47 実験２:実験内容 目的 文章量と正答率k/n, k/mの関係を調査する．
7名の被験者に対し，1行の文からなる評価データをh=5,s=10,c=15の条件で順次提示し，被験者に自然か不自然かを判断させ正答率応答時間を計測する．

48 従来研究 精度に27%の差 提案方式を実装し、実験により「日本人はどれくらいワードサラダを不自然であると感じるのか」を評価．
日本人は8割以上の確率でワードサラダを不自然と感じる． 総当り攻撃への耐性を評価． 総当り攻撃を想定した場合，人間拒否率及び機械受け入れ率は3.7%． 日本語を学んだ留学生と日本人学生との精度の比較により、リレーアタックへの耐性を評価． 同閾値では、留学生との成功率の差は２７％． 精度に27%の差 48

49 実験２：実験結果 判別文書 入力文書 Y=H Y=S X=Human 0.91 0.09 X=Spam 0.27 0.73
Order n=1, の時の条件付確率P(Y|X) 判別文書 入力文書 Y=H Y=S X=Human 0.91 0.09 X=Spam 0.27 0.73

50 Step１．一題当りの校正(検出)率を求める
一題辺りの文章校正が行われる確率は、 　 CAPTCHA中のSpamの割合×Spamに校正が行われる確率 ＋CAPTCHA中のHumの割合×Humに校正が行われる確率 CAPTCHA Spam Hum 校正されない 校正されない 校正される 校正される 50

51 Step１． 一題当りの校正(検出)率を求める
一題辺りの検出（文章校正）が行われる確率P(W)は、 　 CAPTCHA中のSpamの割合×Spamに校正が行われる確率 ＋CAPTCHA中のHumの割合×Humに校正が行われる確率　 = 0.24× ×0.75 = 0.06 CAPTCHA P(X=S)=0.25 P(X=H)=0.75 Spam Ham 校正無 P（W|X=S）P(X=S) =0.19 全体の中で検出が行われる割合 P(W)＝0.06 　 P（W|X=H）P(X=H) ＝0.75 　 P(W|X=S) ×P(X=S)=0.06 P（W|X=S）P(X=S) =0.06 校正有 P(W|X=H)P(X=H)=0 P(W|X=H)P(X=H)=0 51

52 Step2． 機械の解答率を求める 機械の解答率を求める． 校正が行われない時に機械がSpamと判定する確率
機械の解答率を求める．　　　　　　　　　　　　　 校正が行われない時に機械がSpamと判定する確率 P(X=S|W) はベイズの定理により求められる 着色部分以外を無視した時の、オレンジの割合 P(X=S|W) =0.2 P(X=H|W) =0.8

53 Step2． 機械の解答率を求める 判定 検出 X=S X=H W P(X＝S|W) ＝1 P(X=H|W) ＝0 ＝0.2
今回の場合では，検出された時必ずSpamと判定し, 検出されない時は0.8の確率でHamと判定する. (校正されないからといってHamと断定する事は出来ない) 　　　　　　　　　判定 検出　　 　 X=S X=H W 　 P(X＝S|W) ＝1 P(X=H|W) ＝0 ＝0.2 　P(X=H|W) ＝0.8

54 Step3. 機械の解答の正解率を求める 機械の解答の正解率を求める． 機械のSpam判定が正解する確率
機械による判定率P(X=H|W)，P(X=S|W) ⇒機械による出力率P(Yw=H|W)，P(Yw=S|W) 機械のSpam判定が正解する確率

55 Step3. 機械の解答の正解率を求める この判定が正解する確率Pwを求める． 出力 入力 Yw=H Yw=S X=H 0.798
総当り攻撃の正解率は0.625となる為，0.072の上昇． 表7 判定機を用いた機械による条件付確率　P(Yw|X) 　　　 出力 入力　　 　 Yw=H Yw=S X=H 0.798 0.202 X=S 0.394 0.606

56 実験２：評価 校正使用 総当り攻撃 23% 図4 認証成功率 Pw＝0.697 Pq＝0.135 閾値θ(k)
このとき，ｓ回のCAPTCHA審査にk回誤答する確率は，確率Pqの二項分布で表すことができる． Pq＝0.135 56 閾値θ(k) 56

57 日本語についてのワードサラダ n=1 n=3 コーパスの形態素解析にはMecabを用い， 括弧表現「」（）を取り除いた．
第二次世界における影響力は、各国の影響力を樹立していったのクリストファー・検閲等から遠洋捕鯨が民間に送られてさらに各地から購入した。 n=3 一方、1915年にハイチ、1916年にドミニカ共和国に出兵していない。

58 中国語ワードサラダ コーパスの形態素解析にはICACLSを用い， 括弧表現《》を取り除いた． n = 1 n = 3
1819年，1952年公布中国面积是世界上加上了许多地区是哥伦比亚特区及军事力量，数千种已经被推翻。 n = 3 本气候分类法的温带大陆性湿润气候：受墨西哥湾暖流影响，温暖湿润，年降雨量2000毫米以上。