JP7800678B2

JP7800678B2 - 修正装置、修正方法及び修正プログラム

Info

Publication number: JP7800678B2
Application number: JP2024526079A
Authority: JP
Inventors: 忠賢千田; 悠太岩城
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2022-06-07
Filing date: 2022-06-07
Publication date: 2026-01-16
Anticipated expiration: 2042-06-07
Also published as: JPWO2023238239A1; WO2023238239A1; US20250322065A1

Description

本発明は、修正装置、修正方法及び修正プログラムに関する。

実世界において正規表現は正規表現エンジンとして実装され、様々な場面で利用されている。例えば、正規表現エンジンは、emailアドレスを入力する画面を持つウェブアプリケーションにおいて、ユーザが入力した文字列がemailアドレスかどうかを確認するために用いられている。また、例えば、正規表現エンジンは、外部から送られてきたデータのサニタイズや要素の抽出、汎用的なプログラミング言語の標準ライブラリ等に採用されている。

ここで、多くの正規表現エンジンに採用されているバックトラッキング法に基づいた解析アルゴリズムは、解析対象のデータと正規表現の組み合わせによっては処理に膨大な時間を要するという欠点がある。そのような欠点を悪用したサイバー攻撃としてRegular Expression Denial of Service（ReDoS）が知られている（参考文献："Regular expression Denial of Service - ReDoS", https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS）。

なお、マッチさせる文字列の長さに対して、正規表現エンジン上で線形時間で動作するような正規表現を脆弱でない正規表現と呼ぶものとする。逆に、マッチさせる文字列の長さに対して、正規表現エンジン上で例えば指数関数時間で動作するような正規表現を脆弱な正規表現と呼ぶものとする。

従来、ReDoSの脅威を取り除くための技術として、正規表現の受理する言語の誤りを修正するRFixer（例えば、非特許文献１を参照）が知られている。また、純粋な正規表現を決定性有限オートマトン（Deterministic Finite Automaton）に一度変換して戻すことで脆弱でない正規表現を得る方法（例えば、非特許文献２を参照）が知られている。

Rong Pan, Qinheping Hu, Gaowei Xu, and Loris D’Antoni. 2019. Automatic Repair of Regular Expressions. Proc. ACM Program. Lang. 3, OOPSLA, Article 139 (Oct. 2019), 29 pages. Brink van der Merwe, Nicolaas Weideman, and Martin Berglund. 2017. Turning Evil Regexes Harmless. In Proceedings of the South African Institute of Computer Scientists and Information Technologists (SAICSIT’17). Association for Computing Machinery, New York, NY, USA, Article 38, 10 pages.

しかしながら、従来の技術には、実世界で利用されている正規表現の脆弱性を効率良く修正することが困難な場合があるという問題がある。

例えば、非特許文献１に記載の技術は、正規表現の誤りを修正するものであり、脆弱性を修正するものではない。また、例えば、非特許文献２に記載の技術は、は実世界で広く利用されている拡張である先読み、後読み及び後方参照といった構文の修正に対応していない。

また、実用上では、正規表現エンジンが使われるプログラムのソースコード上に脆弱な正規表現が用いられることがある。これに対し、従来の技術は、ソースコード中の脆弱な正規表現修正に特化していない。

上述した課題を解決し、目的を達成するために、修正装置は、ソースコードから第１の正規表現を抽出する抽出部と、前記第１の正規表現が、ReDoSに対して脆弱であることを示す条件を満たすか否かを判定する判定部と、前記第１の正規表現を基に、前記条件を満たさない第２の正規表現を合成する合成部と、を有することを特徴とする。

本発明によれば、実世界で利用されている正規表現の脆弱性を効率良く修正することができる。

図１は、第１の実施形態に係る修正装置の構成例を示す図である。図２は、正規表現の構文の例を示す図である。図３は、正規表現のリストの抽出方法を説明する図である。図４は、ＮＦＡの例を示す図である。図５は、ＮＦＡ上のパスの例を示す図である。図６は、Positive ExamplesとNegative Examplesの例を示す図である。図７は、文字列の集合の生成方法を説明する図である。図８は、正規表現の合成方法を説明する図である。図９は、第１の実施形態に係る修正装置の処理の流れを示すフローチャートである。図１０は、正規表現の修正処理の流れを示すフローチャートである。図１１は、正規表現の合成処理の流れを示すフローチャートである。図１２は、修正プログラムを実行するコンピュータの一例を示す図である。

以下に、本願に係る修正装置、修正方法及び修正プログラムの実施形態を図面に基づいて詳細に説明する。なお、本発明は、以下に説明する実施形態により限定されるものではない。

［第１の実施形態の構成］
まず、図１を用いて、第１の実施形態に係る修正装置の構成について説明する。図１は、第１の実施形態に係る修正装置の構成の一例を示す図である。図１に示すように、修正装置１０は、ソースコードの入力を受け付け、入力されたソースコードに含まれる正規表現の修正を行い、修正後の正規表現を出力する。

ここで、本実施形態における正規表現は、実世界の拡張を施した正規表現であって、バッカスナウア記法（ＢＮＦ：Backus-Naur form）で定義された構文に従うものとする。図２は、正規表現の構文の例を示す図である。図２の正規表現ｒは、本実施形態における正規表現の一例である。なお、以降の説明において、正規表現中の「＼」は適宜バックスラッシュに置き換えられてもよい。

図２の「C」は文字の集合であり、「x」は文字列、「i」は自然数である。図２の構文は既存の正規表現エンジンで利用されているものである（参考文献:"Perldoc Browser", https://perldoc.perl.org/perlre.html）。

また、「.」は任意の１文字を表す記号である。つまり、「.」は図２の範囲文字「[C]」と糖衣構文である。また、範囲文字「[C]」にマッチしない文字の集合は、「[^C]」と書ける。また、空集合は「[]」と表記され、任意の文字にマッチしないことを意味する。

図１に戻り、修正装置１０の各部について説明する。図１に示すように、修正装置１０は、インタフェース部１１、記憶部１２及び制御部１３を有する。

インタフェース部１１は、データの入出力及びデータの通信を行うためのインタフェースである。例えば、インタフェース部１１は、キーボード及びマウス等の入力装置からデータの入力を受け付ける。また、例えば、インタフェース部１１は、ディスプレイ及びスピーカ等の出力装置にデータを出力する。

また、インタフェース部１１は、ネットワークを介して通信を行うための装置（例えばＮＩＣ（Network Interface Card））であってもよい。

記憶部１２は、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）、光ディスク等の記憶装置である。なお、記憶部１２は、ＲＡＭ（Random Access Memory）、フラッシュメモリ、ＮＶＳＲＡＭ（Non Volatile Static Random Access Memory）等のデータを書き換え可能な半導体メモリであってもよい。記憶部１２は、修正装置１０で実行されるＯＳ（Operating System）や各種プログラムを記憶する。

記憶部１２は、置換候補構文情報１２１を記憶する。置換候補構文情報１２１は、正規表現又はテンプレートの、範囲文字又はホールと置換される正規表現の構文の集合である。

例えば、置換候補構文情報１２１は、「□□, □|□, □*, (□), ＼i, (?=□), (?!□), (?<=□), (?<!□)」である。ただし、「□」はホールである。ホール及びテンプレートについては後述する。

制御部１３は、修正装置１０全体を制御する。制御部１３は、例えば、ＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、ＧＰＵ（Graphics Processing Unit）等の電子回路や、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）等の集積回路である。

また、制御部１３は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部１３は、各種のプログラムが動作することにより各種の処理部として機能する。例えば、制御部１３は、抽出部１３１、判定部１３２、生成部１３３及び合成部１３４を有する。

抽出部１３１は、ソースコードから修正前の正規表現を抽出する。また、判定部１３２は、修正前の正規表現が、ReDoSに対して脆弱であることを示す条件を満たすか否かを判定する。そして、合成部１３４は、修正前の正規表現を基に、条件を満たさない修正後の正規表現を合成する。

なお、修正前の正規表現は第１の正規表現の一例である。また、修正後の正規表現は第２の正規表現の一例である。

このように、合成部１３４は、抽出部１３１によってソースコードから抽出された正規表現であって、ReDoSに対して脆弱である正規表現を対象として修正処理を行う。これにより、合成部１３４が本来修正が不必要な正規表現に対して修正処理を行うことが防止される。

さらに、修正装置１０には正規表現そのものではなくソースコードが入力されればよいので、例えば事前にソースコードから正規表現を抽出するといった前段階の処理が省略可能になる。

図３は、正規表現のリストの抽出方法を説明する図である。図３に示すように、まず、抽出部１３１は、ソースコードの構文解析を行い構文解析木（例えば、ＡＳＴ（（Abstract Syntax Tree）））を構築する（ステップＳ１）。

抽出部１３１は、ソースコードを記述しているプログラミング言語に応じて提供されている構文解析機能を用いてソースコードの解析を行うことができる。例えば、プログラミング言語がPythonであれば、抽出部１３１はＡＮＴＬＲ（ANother Tool for Language Recognition）（参考文献：https://www.antlr.org/）を用いてソースコードの解析を行う。

さらに、抽出部１３１は、ＡＳＴ上の解析を行い、正規表現のリストを得る（ステップＳ２）。このように、抽出部１３１は、抽出した１つ以上の正規表現を含むリストを作成することができる。

抽出部１３１は、ソースコードを構文解析木に変換し、構文解析木から抽出された変数を基に復元した正規表現を修正前の正規表現として抽出する。

まず、抽出部１３１は、ＡＳＴ上をトラバースし、ソースコードにおける正規表現、各変数の変数名及び値の集合を抽出する。

ソースコードを基にしたプログラムが実行される際には、正規表現が、変数の組み合わせによって生成される場合がある。そこで、抽出部１３１は、変数名及び値の集合を基に、正規表現を復元する。

プログラム言語であるPythonにより記述された下記のソースコードを例に挙げて、抽出部１３１が正規表現を復元する処理を具体的に説明する。なお、説明のため、ソースコードの各行の左端には、行を区別するための番号が付されている。

（ソースコード）
1: Import re
2: if input() == “example”:
3: s = “example.com”
4: else:
5: s = “example.com/abc”
6: r = ‘http://’ + s + “.*/index[.]html”
7: re.match(r, input())

この場合、正規表現rの値は、変数sの値との組み合わせで決まる。そのため、２行目から始まるif文中のinput()の値が定まるまで正規表現rは定まらない。

抽出部１３１は、変数（名）sに対応する値の集合{“example.com”,“example.com/abc”}を抽出し、当該集合を使って正規表現rを復元する。

この場合、抽出部１３１は、正規表現rとして、「http://example.com.*/index[.]html」及び「http://example.com/abc.*index[.]html」を復元し、当該正規表現を抽出する。

判定部１３２は、正規表現がＲＷＳ１Ｕ（参考文献："Repairing DoS Vulnerability of Real-World Regexes",https://www.computer.org/csdl/proceedings-article/sp/2022/131600b049/1A4Q3TnrBZK）を満たす場合、ReDoSに対して脆弱でないと判定する。一方、判定部１３２は、正規表現がＲＷＳ１Ｕを満たさない場合、ReDoSに対して脆弱であると判定する。

生成部１３３は、正規表現のリストに含まれる正規表現のうち、判定部１３２によってReDoSに対して脆弱であると判定されたものを対象として以下の処理を行う。

生成部１３３は、修正前の正規表現によって受理される文字列の集合であるPositive Examples、及び、修正前の正規表現によって拒否される文字列の集合であるNegative Examplesを生成する。

なお、Positive Examplesは第１の集合の一例である。また、Negative Examplesは第２の集合の一例である。

生成部１３３は、修正前の正規表現を非決定性有限オートマトン（ＮＦＡ：Nondeterministic Finite Automaton）に変換し、非決定性有限オートマトン上のパスのうち、受理状態に到達するパスにより得られた文字列の集合をPositive Examplesとして生成し、非決定性有限オートマトン上のパスのうち、受理状態に到達しないパスにより得られた文字列の集合をNegative Examplesとして生成する。

生成部１３３は、Thompson構成法を用いてＮＦＡを構築する。ただし、正規表現に含まれるキャプチャと後方参照はThompson構成法では扱えないため、生成部１３３は、Over approximationにより、後方参照を当該後方参照が参照するキャプチャの中の正規表現に置換する。

例えば、生成部１３３は、正規表現「(a*b)(c＼1)＼2」について、キャプチャ(「(c＼1)」)中の後方参照である「＼1」を「a*b」に置換し、「(a*b)(ca*b)＼2」を得る。さらに、生成部１３３は、後方参照「＼2」を「ca*b」に置換し、「(a*b)(ca*b)ca*b」を得る。なお、キャプチャは、Thompson構成法においてグルーピングとして扱われるのでそのままとする。

このように、生成部１３３は、後方参照を当該後方参照が参照するキャプチャの中の正規表現に置換する。キャプチャが別の後方参照を含む場合は、先に当該後方参照を、当該後方参照が参照するキャプチャの正規表現に置換する。これにより後方参照が正規表現から消えるため、Thompson構成法が利用可能となる。

生成部１３３は、キャプチャ中の後方参照を除去した正規表現をThompson構成法によりＮＦＡに変換する。図４は、ＮＦＡの例を示す図である。図５は、ＮＦＡ上のパスの例を示す図である。図４及び図５の中の二重丸は受理状態のノードである。

生成部１３３は、ＮＦＡのパスをたどり例を生成する。パスa→c、及びパスb→d（図５の破線）は受理状態に到達するため、生成部１３３は、Positive Examplesの集合｛ac，bd｝を生成する。一方、パスa、及びパスb（図５の一点鎖線）は受理状態に到達しないため、生成部１３３は、Negative Examplesの集合｛a，b｝を生成する。

なお、生成部１３３は、幅優先探索、深さ優先探索等の既知の探索アルゴリズムを利用してパスを列挙することができる。ただし、ＮＦＡ上にループがある場合、生成部１３３は、通ったパスを記録しておき、同じパスを２度以上通ることがないようにしておく。

図６は、Positive ExamplesとNegative Examplesの例を示す図である。ここでは、修正前の正規表現が「.*.*=.*」であるものとする。このとき、Positive Examplesに含まれる「=」、「abcd==」、「==abcd」及び「ab=c」は正規表現「.*.*=.*」にマッチする（受理される）。一方、Negative Examplesに含まれる「abc」は正規表現「.*.*=.*」にマッチしない（拒否される）。

生成部１３３は、特定の長さ以下の文字を組み合わせた文字列を全列挙し、各文字列が正規表現に受理されるならPositive Examplesに分類し、拒否されるならNegative Examplesに分類することができる。なお、生成部１３３は、非特許文献１に記載の方法を用いてPositive ExamplesとNegative Examplesを生成してもよい。

ここで、文字列を素直に全列挙すると、爆発的に例が生成されてしまう。これを回避するために、生成部１３３は、修正前の正規表現の中に現れる文字のみからPositive Examplesの文字列及びNegative Examplesの文字列を生成してもよい。

例えば、正規表現が「ab[c-d]*」である場合、生成部１３３は、「a」及び「b」と、「[c,d]」からランダムに選択した１文字と、を組み合わせて候補の文字列を生成する。

図７は、文字列の集合の生成方法を説明する図である。図７の例では、修正前の正規表現は「.*.*@example[.]com」である。この場合、生成部１３３は、正規表現「.*.*@example[.]com」によって受理される文字列「@example.com」、「a@example.com」、「gc@example.com」をPositive Examplesに分類する。一方、生成部１３３は、正規表現「.*.*@example[.]com」によって拒否される文字列「example.com」、「@.com」、「@examplecom」、「@example.」等をNegative Examplesに分類する。

合成部１３４は、修正前の正規表現における範囲文字を所定の構文に置換した正規表現であって、Positive Examplesの文字列を受理し、かつNegative Examplesの文字列を拒否するような正規表現である修正後の正規表現を合成する。

合成部１３４による処理は大きく、テンプレートを作成するステップと、テンプレートへの割り当てを行うステップと、に分けられる。

テンプレートを作成するステップでは、合成部１３４は、正規表現における範囲文字をプレースホルダを使って置換することによりテンプレートを作成する。

テンプレートへの割り当てを行うステップでは、合成部１３４は、プレースホルダへ所定の構文を割り当てて、脆弱でない正規表現を合成する。以降、プレースホルダをホールと呼び、「□」と表記する。

合成部１３４は、優先度付きキューを保持しつつ処理を行う。キューに格納されたテンプレートには、修正前の正規表現への近さに応じて優先度が付与される。例えば、修正前の正規表現に近いテンプレートほど高い優先度が付与される。また、正規表現への近さは、正規表現のＡＳＴ間の違う部分木のサイズの総和によって表されてもよい（例えば、非特許文献１を参照）。

合成部１３４は、キューから要素を取り出す際には、格納されているテンプレートのうち優先度が最も高いものを優先して取り出す。処理の開始時点では、合成部１３４は、修正前の正規表現をテンプレートとしてキューに格納する。なお、キューに格納された修正前の正規表現の優先度は必然的に最高になる。

まず、合成部１３４によって実行されるテンプレートを作成するステップについて説明する。合成部１３４は、キューから取り出したテンプレートが範囲文字を含む場合、当該テンプレートに含まれる当該範囲文字をホールに置換する。なお、範囲文字は、例えば「[C]」又は「.」のように表される。一方、合成部１３４は、キューから取り出したテンプレートがホールを含む場合、当該ホールのうちいずれか１つを、所定の構文に置換してもよい。

例えば、合成部１３４は、テンプレートとしてキューに格納されている修正前の正規表現「.*.*=.*」の範囲文字を置換したテンプレート「□*.*=.*」、「.*□*=.*」「.*.*=□*」を作成し、キューに格納する。なお、一度取り出されたテンプレートは破棄されるものとする。

このように、合成部１３４は、修正前の正規表現における範囲文字の少なくとも一部をホールに置換し、当該置換したホールをさらに所定の構文に置換したテンプレートを基に修正後の正規表現を合成する。

さらに、合成部１３４は、ホールを、置換候補構文情報１２１に含まれる「□□」、「□|□」、「□*」、「(□)」、「＼i」、「(?=□)」、「(?!□)」、「(?<=□)」、「(?<!□)」といった構文に置換することができる。この場合、合成部１３４は、テンプレートに含まれるホールを、ホールを含む所定の構文である「□□」、「□|□」、「□*」、「(□)」、「＼i」、「(?=□)」、「(?!□)」、「(?<=□)」、「(?<!□)」のいずれかに置換したテンプレート（ただし、□はホール）を基に修正後の正規表現を合成する。

続いて、合成部１３４によって実行されるテンプレートへの割り当てを行うステップについて説明する。ここでは、合成部１３４がテンプレートを作成するステップを繰り返し、例えばテンプレート「□*□*=.*」を作成しキューに格納したものとする。例えば、合成部１３４は、テンプレート「□*.*=.*」の左辺の範囲文字「.」をホールに置換することでテンプレート「□*□*=.*」を得る。

合成部１３４は、テンプレートが含むホールに対する、条件を満たす範囲文字の割り当てを探索する。例えば、合成部１３４は、Satisfiability Modulo Theories（ＳＭＴ) solver（例えば、Z3 solver）等を用いて探索を行う。

合成部１３４は、テンプレートが「□*□*=.*」であり、Positive Examples及びNegative Examplesが図６の通りであれば、「[]*[^=]*=.*」という割り当てを探索により得ることができる。合成部１３４は、空集合である「[]」を取り除き、正規表現「[^=]*=.*」を得る。

正規表現「[^=]*=.*」は、図６のPositive Examplesを受理し、Negative Examplesを拒否する。また、正規表現「[^=]*=.*」は、同じ文字にマッチする箇所を高々１つしか含まないため、脆弱でない性質を持っているということができる。

本実施形態では、前述の通り、マッチさせる文字列の長さに対して、正規表現エンジン上で線形時間で動作するような正規表現を脆弱でない正規表現と呼ぶ。逆に、マッチさせる文字列の長さに対して、正規表現エンジン上で例えば指数関数時間で動作するような正規表現を脆弱な正規表現と呼ぶ。

合成部１３４による脆弱でない正規表現の合成は、KochとScherzingerらにより考案されたstrongly one-unambiguous（参考文献：Christoph Koch and Stefanie Scherzinger. 2007. Attribute Grammars for Scalable Query Processing on XML Streams. The VLDB Journal 16, 3 (July 2007), 317-342.）という性質を実世界の拡張にも合わせて改良した性質を用いたものである。

Strongly one-unambiguousとは、正規表現エンジンが次に処理する演算は現在解析中の文字が何か定まれば一意に定まるという性質である。

同様に、修正前の正規表現が「.*.*@example[.]com」である場合、図８に示すように、合成部１３４は、脆弱でない正規表現「[^@]*@example[.]com」を得ることができる。

［第１の実施形態の処理］
図９は、第１の実施形態に係る修正装置の処理の流れを示すフローチャートである。図９に示すように、まず、修正装置１０は、ソースコードの入力を受け付ける（ステップＳ１１）。

次に、修正装置１０は、ソースコードから正規表現を抽出する（ステップＳ１２）。例えば、修正装置１０は、ソースコードを記述しているプログラミング言語に対応した構文解析機能を用いて正規表現を抽出する。

続いて、修正装置１０は、抽出した正規表現が、ReDoSに対して脆弱であるか否かを判定する（ステップＳ１３）。

抽出した正規表現がReDoSに対して脆弱でない場合（ステップＳ１３、Ｎｏ）、修正装置１０は処理を終了する。

そして、修正装置１０は、ReDoSに対して脆弱である（ステップＳ１３、Ｙｅｓ）と判定された正規表現を修正する（ステップＳ１４）。修正装置１０は、修正した正規表現を出力する（ステップＳ１５）。

図１０は、第１の実施形態に係る修正装置の処理の流れを示すフローチャートである。図１０の処理は、図９のステップＳ１４に相当する。まず、修正装置１０は、正規表現の入力を受け付ける（ステップＳ１４１）。

次に、修正装置１０は、入力された正規表現によって受理される文字列の集合（Positive Examples）を生成する（ステップＳ１４２）。また、修正装置１０は、入力された正規表現によって拒否される文字列の集合（Negative Examples）を生成する（ステップＳ１４３）。

例えば、修正装置１０は、入力された修正前の正規表現から拡張オートマトンを作成し、当該拡張オートマトンのパスを全てカバーするように文字列の集合を生成することができる。

続いて、修正装置１０は、入力された正規表現、受理される文字列及び拒否される文字列を基に正規表現を生成（合成）する（ステップＳ１４４）。そして、修正装置１０は、生成した正規表現を出力する（ステップＳ１４５）。

図１１は、正規表現の合成処理の流れを示すフローチャートである。図１１の処理は、図１０のステップＳ１４４に相当する。まず、修正装置１０は、入力された正規表現を、テンプレートとしてキューに格納する（ステップＳ１４４１）。

次に、修正装置１０は、入力された正規表現に最も近いテンプレートをキューから取得する（ステップＳ１４４２）。

続いて、修正装置１０は、修正装置１０は、受理される文字列を受理し、拒否される文字列を拒否し、かつ脆弱性に関する条件を満たすような、ホールへの範囲文字の割り当てを探索する（ステップＳ１４４３）。

修正装置１０は、探索結果の割り当てが存在するか否かを判定する（ステップＳ１４４４）。探索結果の割り当てが存在しない場合（ステップＳ１４４４、Ｎｏ）、修正装置１０は、範囲文字をホールに置換するか、又はホールを所定のパターンに置換する（ステップＳ１４４５）。所定のパターンは、例えば「□□」、「□|□」、「□*」、「(□)」、「＼i」、「(?=□)」、「(?!□)」、「(?<=□)」、「(?<!□)」といった構文である。なお、ステップＳ１４４１でキューに格納された、入力された正規表現がステップＳ１４４３での探索の対象となった場合、ステップＳ１４４４では割り当てが存在しないもの（Ｎｏ）とみなされる。

そして、修正装置１０は、ステップＳ１４４５で処理済みのテンプレートをキューに格納する（ステップＳ１４４６）。ここでの処理済みのテンプレートは、範囲文字がホールに置換されたテンプレート、又はホールが所定のパターンに置換されたテンプレートである。

一方、探索結果の割り当てが存在する場合（ステップＳ１４４４、Ｙｅｓ）、修正装置１０は、探索結果の割り当てを基に脆弱でない正規表現を合成する（ステップＳ１４４７）。

［第１の実施形態の効果］
これまで説明してきたように、修正装置１０の抽出部１３１は、ソースコードから第１の正規表現を抽出する。判定部１３２は、第１の正規表現が、ReDoSに対して脆弱であることを示す条件を満たすか否かを判定する。合成部１３４は、第１の正規表現を基に、条件を満たさない第２の正規表現を合成する。これにより、実世界で利用されている正規表現の脆弱性を効率良く修正することができる。例えば、事前にソースコードから正規表現を抽出しておく処理を省略することができる。

さらに、実施形態には、ReDoS攻撃の対象となるＷｅｂアプリケーションのソースコードの検査といった実用的な利用方法が可能となる。さらに、実施形態は、Ｗｅｂアプリケーションのセキュリティのテスト及び診断等に活用できる。

また、抽出部１３１は、ソースコードを構文解析木に変換し、構文解析木から抽出された変数を基に復元した正規表現を第１の正規表現として抽出する。このように、実際にプログラムを実行する際に使われる正規表現を動的に復元することができ、修正対象の正規表現を網羅することができるようになる。

また、生成部１３３は、第１の正規表現によって受理される文字列の集合である第１の集合、及び、第１の正規表現によって拒否される文字列の集合である第２の集合を生成する。合成部１３４は、第１の正規表現における範囲文字を所定の構文に置換した正規表現であって、第１の集合の文字列を受理し、かつ第２の集合の文字列を拒否するような正規表現である第２の正規表現を合成する。このような処理を行う際に、ReDoSに対して脆弱な正規表現を絞り込んでおくことで、処理を効率化できる。

生成部１３３は、第１の正規表現を非決定性有限オートマトンに変換し、非決定性有限オートマトン上のパスのうち、受理状態に到達するパスにより得られた文字列の集合を第１の集合として生成し、非決定性有限オートマトン上のパスのうち、受理状態に到達しないパスにより得られた文字列の集合を第２の集合として生成する。これにより、修正対象の正規表現を網羅的に取得することができる。

［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、各装置の分散及び統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的又は物理的に分散又は統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部又は任意の一部が、ＣＰＵ（Central Processing Unit）及び当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。なお、プログラムは、ＣＰＵだけでなく、ＧＰＵ等の他のプロセッサによって実行されてもよい。

また、本実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部又は一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部又は一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。

［プログラム］
一実施形態として、修正装置１０は、パッケージソフトウェアやオンラインソフトウェアとして上記の修正処理を実行する修正プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記の修正プログラムを情報処理装置に実行させることにより、情報処理装置を修正装置１０として機能させることができる。ここで言う情報処理装置には、デスクトップ型又はノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal Handyphone System）等の移動体通信端末、さらには、ＰＤＡ（Personal Digital Assistant）等のスレート端末等がその範疇に含まれる。

また、修正装置１０は、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記の修正処理に関するサービスを提供する修正サーバ装置として実装することもできる。例えば、修正サーバ装置は、ソースコードを入力とし、修正後の正規表現を出力とする修正サービスを提供するサーバ装置として実装される。この場合、修正サーバ装置は、Ｗｅｂサーバとして実装することとしてもよいし、アウトソーシングによって上記の修正処理に関するサービスを提供するクラウドとして実装することとしてもかまわない。

図１２は、修正プログラムを実行するコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。

メモリ１０１０は、ＲＯＭ（Read Only Memory）１０１１及びＲＡＭ（Random Access Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic Input Output System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。

ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、修正装置１０の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、修正装置１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid State Drive）により代替されてもよい。

また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０は、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した実施形態の処理を実行する。

なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３及びプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３及びプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。

１０修正装置
１１インタフェース部
１２記憶部
１３制御部
１２１置換候補構文情報
１３１抽出部
１３２判定部
１３３生成部
１３４合成部

Claims

ソースコードを構文解析木に変換し、前記構文解析木から抽出された変数を基に復元した正規表現を第１の正規表現として抽出する抽出部と、
前記第１の正規表現が、ReDoSに対して脆弱であることを示す条件を満たすか否かを判定する判定部と、
前記第１の正規表現を基に、前記条件を満たさない第２の正規表現を合成する合成部と、
を有することを特徴とする修正装置。
第１の正規表現によって受理される文字列の集合である第１の集合、及び、前記第１の正規表現によって拒否される文字列の集合である第２の集合を生成する生成部をさらに有し、
前記合成部は、前記第１の正規表現における範囲文字を所定の構文に置換した正規表現であって、前記第１の集合の文字列を受理し、かつ前記第２の集合の文字列を拒否するような正規表現である第２の正規表現を合成することを特徴とする請求項１に記載の修正装置。
前記生成部は、前記第１の正規表現を非決定性有限オートマトンに変換し、前記非決定性有限オートマトン上のパスのうち、受理状態に到達するパスにより得られた文字列の集合を前記第１の集合として生成し、前記非決定性有限オートマトン上のパスのうち、受理状態に到達しないパスにより得られた文字列の集合を前記第２の集合として生成することを特徴とする請求項２に記載の修正装置。
修正装置によって実行される修正方法であって、
ソースコードを構文解析木に変換し、前記構文解析木から抽出された変数を基に復元した正規表現を第１の正規表現として抽出する抽出工程と、
前記第１の正規表現が、ReDoSに対して脆弱であることを示す条件を満たすか否かを判定する判定工程と、
前記第１の正規表現を基に、前記条件を満たさない第２の正規表現を合成する合成工程と、
を含むことを特徴とする修正方法。
ソースコードを構文解析木に変換し、前記構文解析木から抽出された変数を基に復元した正規表現を第１の正規表現として抽出する抽出ステップと、
前記第１の正規表現が、ReDoSに対して脆弱であることを示す条件を満たすか否かを判定する判定ステップと、
前記第１の正規表現を基に、前記条件を満たさない第２の正規表現を合成する合成ステップと、
をコンピュータに実行させることを特徴とする修正プログラム。