Algorithm:以下、GA)」とは、生物が自然淘汰や交叉、突然変異を何世代にも渡って繰り返しながら(環境に適応するように)進化していく様をシミュレートするもので、様々なタスクにおける最適解の探索に利用されています。Lop)における、より多くのプログラムPathを通るFuzzの生成等があります。今回は、このGAを脆弱性診断の領域に拡張し、Webアプリケーションの脆弱性を検出するための検査値を自動生成する検証を行いましたので、検証手順と結果を紹介します。scripting:以下、XSS)をターゲットにしています。検証で使用したソースコードは「検証用コード」に掲載しています。ご興味のある方は、ご自身の責任の下でご自由にお使いください。検証内容に入る前に、GAによる進化計算の流れを簡単に説明します。1はGAの進化計算の流れを示しており、大きく5つのステップで計算が行われます。初期集団の生成(Initialization)複数の個体から構成される集団(世代)を生成します。各個体は複数の遺伝子の組み合わせで構成されます。Evaluation)各個体の環境への適応度を評価します。評価結果に基づいて、優秀な個体には高いスコアを付与します。選択(Selection)集団の中からスコアの高い個体を選択します。選択されない低評価の個体は淘汰(破棄)されます。交叉(Crossover)選択された優秀な個体同士の遺伝子の一部を入れ替え、新しい個体を生成します。新しい個体(子孫)が、次の集団(次世代)を構成します。変異(Mutation)次世代から確率的に一部の個体を選択し、遺伝子の一部をランダムに入れ替えます。変異を起こすことで、環境により一層適応した個体が生成される場合があります。Step.5を実行します。このサイクルを終了条件に合致するまで繰り返していきます。終了条件は任意ですが、「世代交代の上限に達した場合」「全個体のスコア平均が閾値を超えた場合」等とするのが一般的です。上記の進化計算を何世代にも渡って繰り返すことで、徐々に環境に適応した「優秀な遺伝子の組み合わせを持った個体」のみが生き残るようになっていきます。ここで言う「環境に適応」はタスクによって変わります。前述のN700系新幹線の例では「空気抵抗が小さくなること」を評価して環境への適応度を判断しますし、Fuzzerでは「より多くのプログラムPathを通ること」を評価して環境への適応度を判断します。優秀な個体の遺伝子を次世代に残すためには、環境への適応度を評価する「評価関数」の設計が非常に重要になります。手法が存在しますが、今回は比較的実装が容易で計算速度も速く、生成パターンに富んだGAを採用しました。前述したように、今回のタスクは「XSSの検査値を生成」することです。そこで今回は、下記二つをタスクの目標としました。過去未使用の検査値の生成(未知の検査値)WAFを回避する検査値の生成すなわち、上記二つの目標を達成する個体を求めて、進化計算を繰り返すことになります。ここで、本タスクにおけるGA特有のキーワードを定義しておきます。個体(Individual)複数の遺伝子の組み合わせで構成されるXSSの検査値。適応度(Fitness)個体がXSSの検出に寄与する度合い。評価(Evaluation)個体がタスクの達成に寄与する度合いを「評価関数」で評価。評価に応じて各個体にスコアを付与。選択(Selection)スコアの高い個体を複数選択。それ以外の個体は淘汰。交叉(Crossover)選択された個体の遺伝子の一部を入れ替えて新たな個体(子孫)を生成。XSSを検出する可能性がより高い次世代の個体(検査値)を生成。変異(Mutation)次世代の個体の中から、一定割合の個体の遺伝子をランダムに入れ替え。集団全体がイマイチな検査値(局所解)に落ち着くのを防ぐと共に、タスク達成により一層寄与する個体を確率的に生成。個体は複数の遺伝子の組み合わせで構成されるため、事前に遺伝子を収集する必要があります。今回は以下の手順で遺伝子を収集しました。診断業務で使用している検査値を公開することはできないため、今回はWAVSEPのXSSケースで使用した検査値を基に遺伝子を収集しました。ここで、既知の検査値から収集した遺伝子のみを使用した場合、未知の検査値は生成できないことが予測されます。docsを参考にし、WAVSEPの検査で使用しなかったHTMLタグや属性、イベントハンドラ等を遺伝子として追加しました。これにより、約220種類の遺伝子を定義しました。今回使用した遺伝子リストはこちらから参照可能です。検証手順それでは、進化計算の様子を見ていきましょう。遺伝子リストから無作為に遺伝子を選んで個体を生成します。今回は1世代あたり100個体、各個体は5個の遺伝子で構成されるようにしました。ここで、遺伝子を文字列として扱うと計算が困難になるため、各遺伝子は予めユニークな番号で符号化しました。3は、初期集団の各個体([]で囲まれたもの)を符号で表した例を示しています。上記の個体を文字列で表現すると、以下のようになります。初期集団は遺伝子リストから無作為に選んだ遺伝子で構成されるため、個体は意味のない文字列となります。HTML構文としての妥当性はありませんし、スクリプトも実行することはできません。集団内の各個体に対し、XSSの検出に寄与する度合いを評価します。今回は以下三つの評価基準を組み合わせて評価関数を設計しました。個体がHTML構文として妥当性があるのか、HTML構文チェッカで評価。チェック結果の「警告数」や「エラー数」に応じてスコアを計算。個体をブラウザで読み込んでスクリプトの発火有無を観測。マウス操作やキー操作で発火するパターンの一部も考慮(イベントハンドラ系)。スクリプト発火有無に応じてスコアを計算。WAFの回避可否やられアプリの手前にWAFを設置。個体を含んだHTTPリクエストをアプリに送信し、WAFによるブロック有無を観測。WAFのブロック有無に応じてスコアを計算。適応度評価の結果、スコアの高い個体を選択し、それ以外を淘汰。以下、選択された個体と淘汰された個体の一例を示します。5の個体の方がHTML構文としての妥当性が高いため、スコアが高くなります。選択された個体の中からペアを選び、遺伝子を交叉させます。これにより、より環境に適応する個体(子孫)が生成されます。された次世代の個体の中から、一定割合の個体及び遺伝子を選択し、遺伝子をランダムに入れ替えます。これにより、スクリプト実行可能な個体または実行可能性が高まる個体が確率的に生成されます。変異の様子また、突然変異を行うことで、世代全体が局所解に陥るのを防ぐ効果もあります。検証条件は以下の通りです。Set)は厳格過ぎるため、本検証用に一部のイベントハンドラ(onerror)のチェックを除外してルールを緩和しました。選択/交叉の方式や突然変異率は、経験則に基づいて収束時間が短く、生成される検査値のパターンが豊富になる設定を採用しました。以下、今回のタスクの目標「未知の検査値の生成」と「WAFを回避する検査値の生成」について、検証結果を示します。2は、GAにより生成された検査値の一例を示しています。カラム「新旧」は、生成された検査値が既知のものかどうかを示しています。「新」は未知の検査値、「旧」は既知の検査値です。上記の結果から、一部WAVSEPで使用した既知の検査値が生成されているものの、全体的には未知の検査値が多く生成されたことが分かりました。検証前の想定では、特異な検査値(複雑に記号や文字列が組み合わさったもの等)が生成されることを期待していましたが、上記の結果から分かるように、割とノーマルな検査値が多く生成されています。これは、今回使用した遺伝子リストの内容や粒度に起因していると考えられるため、当該リストを調整することで特異な検査値が生成できるかもしれません。3は、GAで生成した検査値のWAF回避有無を示しています。カラム「WAF」は、検査値がWAFを回避したか否かを示しており、「block」は回避不可、「break」は回避可を示しています。348世代)はスクリプト実行可能な個体すら生成できていないことが分かります。349世代目で初めてスクリプト実行可能な個体が生成されていますが、この世代の個体ではWAFを回避することはできないことが分かります。その後、更に進化を繰り返し、6307世代目の個体において、初めてWAFを回避(※)する個体が生成されたことが分かります。ここまでに要した時間は約5時間でした。※前述の通り、今回の検証ではModSecurityのCRSを緩和しています。5時間という計算時間については議論の余地がありますが、評価関数の設計や選択/交叉/突然変異のパラメータを調整することで、計算時間をより短くできるかもしれません。今回の検証を纏めます。評価関数や各種パラメータの調整により、計算時間を短縮できる可能性がある今回使用した遺伝子はWAVSEP用の比較的単純な検査値を基に生成したものであり、遺伝子の粒度も粗いものでした。これを、「実業務の検査値を使用する」や「遺伝子の粒度を細かくする(1文字単位等)」等にすることで、より複雑でパターンに富んだ検査値が生成できる可能性があります。今回評価に使用したWebドライバはChromeのみでしたが、複数のWebドライバ(IE、FireFox、Edge等)を併用することで、ブラウザ依存の検査値を生成できる可能性があります。今回は単純に個体をブラウザで読み込んでスクリプト実行可否を評価しましたが、個体を読み込む場所(属性値やコメント及びJavaScript内等)を考慮して評価することで、値の出力個所に応じた検査値を生成できる可能性もあります。上記は今後の課題として検証を進めていきたいと思います。最後に、これまでGAという言葉は知っていたものの、具体的なロジックや利用用途を意識したことはありませんでした。今回の検証を通じて、実際に多くのタスクで実用されていることを知り、また自身のドメインでも利用できる可能性があることが分かりました。皆様の身近にも組み合わせ最適化のタスクが存在するかもしれませんので、ご興味のある方は一度GAを触ってみる事をお勧めします。