本サイトは、快適にご利用いただくためにクッキー（Cookie）を使用しております。
Cookieの使用に同意いただける場合は「同意する」ボタンを押してください。
なお本サイトのCookie使用については、「個人情報保護方針」をご覧ください。

同意する
閉じる
お問い合わせ
検索
最新情報
ニュース
採用
ソリューション
企業情報
ニュース
採用
お問い合わせ

最新情報

2017.08.21

脆弱性検査値の自動生成 - 遺伝的アルゴリズム編 -

著者：高江洲 勲

 「遺伝的アルゴリズム（Genetic Algorithm：以下、GA）」とは、生物が自然淘汰や交叉、突然変異を何世代にも渡って繰り返しながら（環境に適応するように）進化していく様をシミュレートするもので、様々なタスクにおける最適解の探索に利用されています。実用例としては、N700系新幹線における、空気抵抗が少ない先頭車両形状の計算、Fuzzer（American Fuzzy Lop）における、より多くのプログラムPathを通るFuzzの生成等があります。


 今回は、このGAを脆弱性診断の領域に拡張し、Webアプリケーションの脆弱性を検出するための検査値を自動生成する検証を行いましたので、検証手順と結果を紹介します。なお、Webアプリケーションの脆弱性は多種多様ですが、今回は反射型のXSS（Reflected Cross site scripting：以下、XSS）をターゲットにしています。


Note: 検証で使用したソースコードは「検証用コード」に掲載しています。
ご興味のある方は、ご自身の責任の下でご自由にお使いください。


GAの概要


 検証内容に入る前に、GAによる進化計算の流れを簡単に説明します。



Figure 1 進化計算の流れ

 Figure 1はGAの進化計算の流れを示しており、大きく5つのステップで計算が行われます。


Step.1. 初期集団の生成（Initialization）

複数の個体から構成される集団（世代）を生成します。
各個体は複数の遺伝子の組み合わせで構成されます。


Step.2. 適応度の評価（Fitness / Evaluation）

各個体の環境への適応度を評価します。
評価結果に基づいて、優秀な個体には高いスコアを付与します。


Step.3. 選択（Selection）

集団の中からスコアの高い個体を選択します。
選択されない低評価の個体は淘汰（破棄）されます。


Step.4. 交叉（Crossover）

選択された優秀な個体同士の遺伝子の一部を入れ替え、新しい個体を生成します。
新しい個体（子孫）が、次の集団（次世代）を構成します。


Step.5. 突然変異（Mutation）

次世代から確率的に一部の個体を選択し、遺伝子の一部をランダムに入れ替えます。
突然変異を起こすことで、環境により一層適応した個体が生成される場合があります。


 以降、次世代の集団に対してStep.2 – Step.5を実行します。そして、このサイクルを終了条件に合致するまで繰り返していきます。なお、終了条件は任意ですが、「世代交代の上限に達した場合」「全個体のスコア平均が閾値を超えた場合」等とするのが一般的です。


 上記の進化計算を何世代にも渡って繰り返すことで、徐々に環境に適応した「優秀な遺伝子の組み合わせを持った個体」のみが生き残るようになっていきます。

 なお、ここで言う「環境に適応」はタスクによって変わります。前述のN700系新幹線の例では「空気抵抗が小さくなること」を評価して環境への適応度を判断しますし、Fuzzerでは「より多くのプログラムPathを通ること」を評価して環境への適応度を判断します。すなわち、優秀な個体の遺伝子を次世代に残すためには、環境への適応度を評価する「評価関数」の設計が非常に重要になります。


Note: 組み合わせ最適化の手法は「線形探索」「ランダム探索」「動的計画」等、様々な手法が存在しますが、今回は比較的実装が容易で計算速度も速く、生成パターンに富んだGAを採用しました。


事前準備


タスクの設定

 前述したように、今回のタスクは「XSSの検査値を生成」することです。

 そこで今回は、下記二つをタスクの目標としました。


  • 過去未使用の検査値の生成（未知の検査値）
  • WAFを回避する検査値の生成

 すなわち、上記二つの目標を達成する個体を求めて、進化計算を繰り返すことになります。


 ここで、本タスクにおけるGA特有のキーワードを定義しておきます。


  • 遺伝子（Gene）
    HTML、JavaScriptの 最小構成要素。
    例）[<img/], [src=], [xxx], [onerror=], [alert();], [/>] 等の文字列
  • 個体（Individual）
    複数の遺伝子の組み合わせで構成されるXSSの検査値。
    例）[<img/][src=][xxx][onerror=][alert();][/>] 等の遺伝子の組み合わせ文字列
  • 適応度（Fitness）
    個体がXSSの検出に寄与する度合い。
  • 評価（Evaluation）
    個体がタスクの達成に寄与する度合いを「評価関数」で評価。
    評価に応じて各個体にスコアを付与。
  • 選択（Selection）
    スコアの高い個体を複数選択。
    それ以外の個体は淘汰。
  • 交叉（Crossover）
    選択された個体の遺伝子の一部を入れ替えて新たな個体（子孫）を生成。
    XSSを検出する可能性がより高い次世代の個体（検査値）を生成。
  • 突然変異（Mutation）
    次世代の個体の中から、一定割合の個体の遺伝子をランダムに入れ替え。
    集団全体がイマイチな検査値（局所解）に落ち着くのを防ぐと共に、タスク達成により一層寄与する個体を確率的に生成。


遺伝子の準備

 個体は複数の遺伝子の組み合わせで構成されるため、事前に遺伝子を収集する必要があります。今回は以下の手順で遺伝子を収集しました。


  1. 過去に診断業務等で使用した検査値を収集
  2. 各検査値をHTMLタグや属性、イベントハンドラ等の最小要素に分解
  3. 各最小要素を遺伝子として定義

Note: 診断業務で使用している検査値を公開することはできないため、今回はWAVSEPのXSSケースで使用した検査値を基に遺伝子を収集しました。

 ここで、既知の検査値から収集した遺伝子のみを使用した場合、未知の検査値は生成できないことが予測されます。そこで、今回はMDN web docsを参考にし、WAVSEPの検査で使用しなかったHTMLタグや属性、イベントハンドラ等を遺伝子として追加しました。これにより、約220種類の遺伝子を定義しました。



Figure 2 遺伝子リストの概念図

Note: 今回使用した遺伝子リストはこちらから参照可能です。


検証手順


 それでは、進化計算の様子を見ていきましょう。


初期集団の生成

 遺伝子リストから無作為に遺伝子を選んで個体を生成します。

 今回は1世代あたり100個体、各個体は5個の遺伝子で構成されるようにしました。


 ここで、遺伝子を文字列として扱うと計算が困難になるため、各遺伝子は予めユニークな番号で符号化しました。Figure 3は、初期集団の各個体（[]で囲まれたもの）を符号で表した例を示しています。


[85, 158, 96, 32, 85]  , [179, 62, 33, 130, 133]
[98, 82, 25, 41, 198]  , [55, 9, 94, 194, 55]
・・・
[76, 6, 114, 149, 70]  , [107, 140, 172, 150, 38]
[102, 169, 76, 90, 208], [21, 168, 111, 15, 159]
Figure 3 初期集団を符号で表現した例

 上記の個体を文字列で表現すると、以下のようになります。


[85, 158, 96, 32, 85] ⇒ </blockquote>content= <basefont/<form </blockquote>
[179, 62, 33, 130, 133] ⇒ <iframe/language= <keygen/</img>coords=
・・・
Figure 4 個体を文字列で表現した例

 初期集団は遺伝子リストから無作為に選んだ遺伝子で構成されるため、個体は意味のない文字列となります。当然、HTML構文としての妥当性はありませんし、スクリプトも実行することはできません。



適応度の評価

 集団内の各個体に対し、XSSの検出に寄与する度合いを評価します。

 今回は以下三つの評価基準を組み合わせて評価関数を設計しました。


  • HTML構文としての妥当性
    個体がHTML構文として妥当性があるのか、HTML構文チェッカで評価。
    チェック結果の「警告数」や「エラー数」に応じてスコアを計算。
  • スクリプトの実行可否
    個体をブラウザで読み込んでスクリプトの発火有無を観測。
    マウス操作やキー操作で発火するパターンの一部も考慮（イベントハンドラ系）。
    スクリプト発火有無に応じてスコアを計算。
  • WAFの回避可否
    やられアプリの手前にWAFを設置。
    個体を含んだHTTPリクエストをアプリに送信し、WAFによるブロック有無を観測。
    WAFのブロック有無に応じてスコアを計算。


個体の選択

 適応度評価の結果、スコアの高い個体を選択し、それ以外を淘汰。

 以下、選択された個体と淘汰された個体の一例を示します。


<iframe/language= <keygen/</img>coords=
<hr ><video>onmouseover=confirm();><a
onerror=¥u0061lert();<body/list=<iframe/<progress
<body><img/<source/onerror=prompt();>
Figure 5 選択された個体

src=/ <a/</col><td </area>
onerror=alert();><body onerror=al¥u0065rt();<output
<hr <thead </td>rowspan=accept=
</applet><isindex/alert();<progress/script:alert();
Figure 6 淘汰された個体

 若干分かり難いですが、Figure 6の個体よりFigure 5の個体の方がHTML構文としての妥当性が高いため、スコアが高くなります。



交叉

 選択された個体の中からペアを選び、遺伝子を交叉させます。

 これにより、より環境に適応する個体（子孫）が生成されます。


[親（現世代）]
<img src=/ <a/</col><td>
onerror=alert();><body onerror=al¥u0065rt();>
・・・
-----------------------------------------------------------------
[子孫（次世代）]
<img src=/ <a/onerror=alert();>
</col><td><body onerror=al¥u0065rt();>
・・・
Figure 7 交叉の様子


突然変異

 生成された次世代の個体の中から、一定割合の個体及び遺伝子を選択し、遺伝子をランダムに入れ替えます。これにより、スクリプト実行可能な個体または実行可能性が高まる個体が確率的に生成されます。


[突然変異前]
<img src=/ <a/onerror=alert();>
</col><td><body onerror=al¥u0065rt();>
<hr ><video>onmouseover=confirm();><a
・・・
-----------------------------------------------------------------
[突然変異後]
<img src=x <a/onerror=alert();>
</col><td><body onload=al¥u0065rt();>
<hr ><video>onerror=confirm();><a
・・・
Figure 8 突然変異の様子

 また、突然変異を行うことで、世代全体が局所解に陥るのを防ぐ効果もあります。


 以上の計算を繰り返し行い、タスクの目標を達成する個体が生成されるのか探索していきます。



検証結果


検証条件

 今回の検証条件は以下の通りです。


遺伝子 約220種類
1世代あたりの個体数 100個
－各個体は5個の遺伝子の組み合わせで構成
適応度の評価 HTML構文チェック：tidy 5.4.0
－警告とエラー数をカウント
スクリプト実行判定：selenium 3.4.3
－ChromeのWebドライバを使用
WAF回避判定：ModSecurity CRS 2.2.9
－onerrorのチェックを除外してルールを緩和
選択 エリート選択
－スコアの高い個体を優先的に選択
交叉 2点交叉
－遺伝子の中から2点選択し、2点間の遺伝子を交換
突然変異 変異率：0.3
－突然変異対象は世代全体の3割の個体
終了条件 下記条件の何れかを満たした場合
・10,000世代超
・1世代の個体全体の平均スコア3.0超
Table 1 検証条件

Note: ModSecurityのデフォルトCRS（Core Rule Set）は厳格過ぎるため、本検証用に一部のイベントハンドラ（onerror）のチェックを除外してルールを緩和しました。

Note: 選択/交叉の方式や突然変異率は、経験則に基づいて収束時間が短く、生成される検査値のパターンが豊富になる設定を採用しました。

 以下、今回のタスクの目標「未知の検査値の生成」と「WAFを回避する検査値の生成」について、検証結果を示します。



検証結果：未知の検査値の生成

 Table 2は、GAにより生成された検査値の一例を示しています。

 カラム「新旧」は、生成された検査値が既知のものかどうかを示しています。「新」は未知の検査値、「旧」は既知の検査値です。


No 検査値 新旧
1 <body onmouseover=alert(); <script <label <canvas </basefont> 新
2 <body onload=alert(); list=</a> 旧
3 <svg/onload=alert(); </del> 旧
4 <script>al¥u0065rt();</script> 新
5 <object data=xss.html </label> 新
6 <video><source/onerror=javascript:alert();> 新
7 <video><source onerror=alert();> 新
8 <video><source onerror=confirm(1);> 新
9 <video><source/onerror=al¥u0065rt();> 新
10 <iframe onload=alert();> 新
- ・・・ -
Table 2 検査値の自動生成結果

 上記の結果から、一部WAVSEPで使用した既知の検査値が生成されているものの、全体的には未知の検査値が多く生成されたことが分かりました。


 ただし、検証前の想定では、特異な検査値（複雑に記号や文字列が組み合わさったもの等）が生成されることを期待していましたが、上記の結果から分かるように、割とノーマルな検査値が多く生成されています。これは、今回使用した遺伝子リストの内容や粒度に起因していると考えられるため、当該リストを調整することで特異な検査値が生成できるかもしれません。



検証結果：WAFを回避する検査値の生成

 Table 3は、GAで生成した検査値のWAF回避有無を示しています。

 カラム「WAF」は、検査値がWAFを回避したか否かを示しており、「block」は回避不可、「break」は回避可を示しています。


世代 検査値 WAF
1 -（スクリプト実行不可） -
100 -（スクリプト実行不可） -
349 <video><source/onerror=al¥u0065rt();> block
1641 <video><source/onerror=javascript:window.onerror=alert();> block
2743 <video><source onerror=javascript:al¥u0065rt();> block
4568 <video><source onerror=javascript:alert();> block
… … …
5047 <video><source onerror=al¥u0065rt();> block
6067 <video><source onerror=alert();> block
6192 <video><source onerror=prompt();> block
6307 <video><source onerror=confirm(1);> break
Table 3 WAFの回避可否（一例）

 上記の結果から、序盤の世代（1 – 348世代）はスクリプト実行可能な個体すら生成できていないことが分かります。そして、349世代目で初めてスクリプト実行可能な個体が生成されていますが、この世代の個体ではWAFを回避することはできないことが分かります。その後、更に進化を繰り返し、6307世代目の個体において、初めてWAFを回避（※）する個体が生成されたことが分かります。なお、ここまでに要した時間は約5時間でした。

※前述の通り、今回の検証ではModSecurityのCRSを緩和しています。


 5時間という計算時間については議論の余地がありますが、評価関数の設計や選択/交叉/突然変異のパラメータを調整することで、計算時間をより短くできるかもしれません。



まとめ＆今後の課題


 今回の検証を纏めます。


  1. GAを使用することで、XSSの検査値を生成可能
  2. 他脆弱性の検査値（コマンドインジェクション等）にも適用できるかも（要検証）
  3. 検査値の複雑性は遺伝子リストの内容（遺伝子の種類や粒度等）に依存
  4. 評価関数や各種パラメータの調整により、計算時間を短縮できる可能性がある

 今回使用した遺伝子はWAVSEP用の比較的単純な検査値を基に生成したものであり、遺伝子の粒度も粗いものでした。これを、「実業務の検査値を使用する」や「遺伝子の粒度を細かくする（1文字単位等）」等にすることで、より複雑でパターンに富んだ検査値が生成できる可能性があります。また、今回評価に使用したWebドライバはChromeのみでしたが、複数のWebドライバ（IE、FireFox、Edge等）を併用することで、ブラウザ依存の検査値を生成できる可能性があります。更に、今回は単純に個体をブラウザで読み込んでスクリプト実行可否を評価しましたが、個体を読み込む場所（属性値やコメント及びJavaScript内等）を考慮して評価することで、値の出力個所に応じた検査値を生成できる可能性もあります。


 上記は今後の課題として検証を進めていきたいと思います。


 最後に、これまでGAという言葉は知っていたものの、具体的なロジックや利用用途を意識したことはありませんでした。今回の検証を通じて、実際に多くのタスクで実用されていることを知り、また自身のドメインでも利用できる可能性があることが分かりました。

 皆様の身近にも組み合わせ最適化のタスクが存在するかもしれませんので、ご興味のある方は一度GAを触ってみる事をお勧めします。



検証用コード

https://github.com/13o-bbr-bbq/machine_learning_security/tree/master/Generator


以上


高江洲 勲 の他のブログ記事を読む

プロフェッショナルサービス事業部
高江洲 勲

おすすめ記事

Most Read

Download

キーワードで探す

テーマで探す

筆者で探す

シリーズで探す