文章合成の不自然さを用いたCAPTCHA

Presentation on theme: "文章合成の不自然さを用いたCAPTCHA"— Presentation transcript:

1 文章合成の不自然さを用いたCAPTCHA
東海大学 工学研究科情報理工学専攻 ○鴨志田芳典　菊池浩明

2 研究背景 CAPTCHA 問題点：現行のCAPTCHAの脆弱性 プログラムによるアカウントの大量取得対策
(Completely Automated Public Turing test to tell Computers and Humans Apart) プログラムによるアカウントの大量取得対策 問題点：現行のCAPTCHAの脆弱性 高性能OCRを持つ攻撃に破られている． 低賃金労働者による攻撃(リレーアタック)

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

4 研究目的 リレーアタックによる攻撃に強く， OCR機能を持つマルウェアによる攻撃に強く， 正規アクセスの拒否率が低い．
CAPTCHAの提案． 文章の意味を理解する問題を用いる．

5 提案手法 不自然な文をワードサラダにより合成する． ワードサラダの特徴 ワードサラダ：マルコフ連鎖モデルを利用した合成文章
スパムの大量投稿に利用されている． ワードサラダの特徴 文法は正しくなる傾向があり，検出が困難． ある程度以上の語学力が無ければ，判断は難しい ネイティブが読めば不自然であると判断可能である．

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

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

8 前回の発表内容 総当り攻撃への耐性の検証 リレーアタックへの耐性の検証 文章量を減らす事によるパフォーマンスの向上

9 定義：FRR, FAR, ERR False humans Reject Rate False machines Accept Rate
このとき，ｓ回のCAPTCHA審査にk回誤答する確率は，確率Pqの二項分布で表すことができる． Equal Error Rate

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

11 文章量による精度の変化 自然な文の出題数 h=15 ワードサラダの出題数 s=5 総問題数 c=20 正解数kの閾値Θ=15 の時，
EER = 3.7%　

12 本日の発表 文章校正ツールによる検出の検討 日本語以外への言語への適用

13 実験１ 目的 内容 文章校正ツールによる検出の精度の調査
問題として使用したn=1,…,3のワードサラダと自然な文，各300文について，MicroSoftWordによる文章校正が行われる確率を調査．

14 実験１：結果 実験結果 P(w)：校正が行われる確率． n=1の時のみ，検出率24%．P(w|X=S)=0.24
その他の場合の検出は無かった． P(w|X=H)=0 P(w)：校正が行われる確率． 検出 第二次世界における影響力は、各国の影響力を樹立していったの クリストファー・検閲等から遠洋捕鯨が民間に送られてさらに各地から購入した。 未検出 ラク・オバマ大統領の紛争や国民に対して 政治的に殆ど被害を謳歌している。

15 解析.1 0.25 P(X=S)=0.25 P(w|X=S)=0.24 P(w)=0.06
= 0.24× ×0.75 = 0.06 提示される文章がワードサラダである確率 P(X=S)=0.25 0.25 P(w|X=S)=0.24 P(w)=0.06

16 解析.2 検出が行われた際の実際の機械の判定を求める． 機械はP(X=S)を知らないと仮定する．

17 解析.3 従って，機械は以下のスパム判定機を得る． 検出 判定 not w w X=H 0.6 0.4 X=S 0.0 1.0
校正が行われた場合，100%不自然と解答する． 校正が行われなかった時，60%の確率でY=H 40%の確率でY=Sと解答する． 　　　　　　検出 判定　　 　 not w w X=H 0.6 0.4 X=S 0.0 1.0

18 解析.4 この判定機が正解する確率Pqwを求める． 出力 入力 Y=H Y=S X=H 0.51 0.49 X=S 0.44 0.56
　　　　　　出力 入力　　 　 Y=H Y=S X=H 0.51 0.49 X=S 0.44 0.56 　出題率の歪みを考慮して，Pqw=0.51× ×025 ≒0.55

19 解析結果 EER = 8%

20 実験2 目的 内容 提案手法を他言語へ適用出来るか評価する
各言語の評価データの合成実験を行い，日本人学生3 名，英語，中国語，タイ語を母国語とする学生それぞれ1 名に対し40題提示し，その正答率を計測した． 評価データ Wikipedia のアメリカ合衆国の記事の本文から合成，または抽出したワードサラダと本文の一部。

21 日本語についてのワードサラダ n=1 n=3 一方、1915年にハイチ、1916年にドミニカ共和国に出兵していない。
第二次世界における影響力は、各国の影響力を樹立していったのクリストファー・検閲等から遠洋捕鯨が民間に送られてさらに各地から購入した。 n=3 一方、1915年にハイチ、1916年にドミニカ共和国に出兵していない。

22 英語ワードサラダ n=1 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 subarctic 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.

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

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

25 実験2.実験結果 言語 N=1 N=2 N=3 自然文 日本 0.87 0.47 0.20 0.90 英語 1.0 0.8 0.6 0.7
中国 0.5 タイ

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

27 考察 タイ語については，全ての場合不自然であると言う結果が得られた それ以外の言語では，理想的な結果が得られた
文節記号がない為，文の終了条件を学習出来ない． それ以外の言語では，理想的な結果が得られた 適切な形態素解析さえ行えれば， 提案方式は他言語に充分適用可能であると言える．

28 おわりに 結論 提案方式を20題の文章中に階数n = 1のワードサラダ5 題と自然な文15 題の最も精度の良くなる条件下で行った場合，人間拒否率4.3% 及び機械受入れ率2% の精度と，必要時間151.7秒のパフォーマンスで認証を行う事が可能である． 提案方式はリレーアタックに対して耐性を持つ事を示した 提案方式は日本語に限らず他言語にも適用可能である事を示した 提案方式について， 文章校正機能を用いられた場合では精度は半減する

29

30

31 実験３：実験結果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 不自然な箇所が現れる確率が下がるため， ワードサラダを判別できる確率は低くなっている． しかし，自然な文を判別する確率は上がっている． 少ない文字数の文章が自然であることを判断する事は容易であるためと考えられる． （文字数が多いとどっか１箇所不自然だと思ってしまうと，全体が不自然な文章になる．） このため，少ない文字数の中に確実に不自然な箇所を加えられれば， パフォーマンスの向上が可能であると推察できる．

32 実験３：実験結果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 不自然な箇所が現れる確率が下がるため， ワードサラダを判別できる確率は低くなっている． しかし，自然な文を判別する確率は上がっている． 少ない文字数の文章が自然であることを判断する事は容易であるためと考えられる． （文字数が多いとどっか１箇所不自然だと思ってしまうと，全体が不自然な文章になる．） このため，少ない文字数の中に確実に不自然な箇所を加えられれば， パフォーマンスの向上が可能であると推察できる．

33 文章量による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

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

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

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

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

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

39 マルコフ連鎖による文章合成のプロセス 単純マルコフ連鎖モデル(N=1)を用いる場合
鴨志田が車に轢かれた。 鴨志田が子犬に懐かれた。 入力(コーパス) 車 轢か 1/2 1/2 1/1 1/1 1/1 1/1 に れ た 。 鴨志田 が 1/1 1/2 1/2 子犬 懐か

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

41 閾値θについての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のときよりも高くなっている事が見えればおｋ

42 ワードサラダの割合による 精度の変化 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%

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

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

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

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

47 評価：１ 判別文書 入力文書 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

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