入れ子の量指定子と照合時間
入力値の検証に，次の正規表現をバックトラック型の正規表現エンジンで用いている。
^([a-z0-9]+)*@example\.com$攻撃者が，英小文字の a を 30 個並べた後に「!@example.com」を続けた文字列を送信した場合に起こり得ることとして，適切なものはどれか。
- ア先頭と末尾への一致が指定されていないので，許可しない文字 ! を含む文字列が部分一致によって検証を通過する。
- イ入力の文字列がエンジン内部で正規表現のパターンとして解釈され，攻撃者が指定したパターンで照合が行われて，検証が回避される。
- ウ照合は入力の長さに比例する時間で終わり，文字列は ! の位置で不一致となって拒否されるだけである。
- エ+ と * が入れ子になっているので，a の並びの分け方を全て試すまで不一致が確定せず，試行回数が文字数に対して指数関数的に増えて，CPU 資源が長時間消費される。
正解と解説を見る
正解 エ
この問題の基礎知識
- バックトラック型の正規表現エンジンは，照合に失敗すると前の分岐点に戻って別の一致の仕方を試す。
- 量指定子が入れ子になったパターンでは，同じ文字列をグループに分ける方法が文字数に対して指数関数的に増え，不一致が確定するまでに膨大な試行を要することがある（ReDoS）。
- 正規表現の ^ は文字列の先頭，$ は末尾への一致を表し，これらのアンカーを付けないと部分一致で検証を通過する問題が生じる。
- ReDoS の対策には，入れ子の量指定子などの曖昧なパターンを避けること，入力長を制限すること，バックトラックを行わない方式のエンジンを用いることなどがある。
ア先頭と末尾への一致が指定されていないので，許可しない文字 ! を含む文字列が部分一致によって検証を通過する。
この正規表現は ^ と $ で先頭と末尾への一致を指定しているので，部分一致によって通過することはない。アンカーの指定漏れ（CWE-777）は別の問題である。
イ入力の文字列がエンジン内部で正規表現のパターンとして解釈され，攻撃者が指定したパターンで照合が行われて，検証が回避される。
入力は照合される対象の文字列として扱われ，パターンとして解釈されることはない。利用者の入力をパターンの組立てに使う場合の問題とは異なる。
ウ照合は入力の長さに比例する時間で終わり，文字列は ! の位置で不一致となって拒否されるだけである。
入力長に比例する時間で照合できるのは，バックトラックを行わない方式のエンジンの場合である。バックトラック型では，不一致が確定するまでに多数の照合の仕方を試す。
エ+ と * が入れ子になっているので，a の並びの分け方を全て試すまで不一致が確定せず，試行回数が文字数に対して指数関数的に増えて，CPU 資源が長時間消費される。正解
([a-z0-9]+)* では，a の並びをグループに分ける方法が文字数に対して指数関数的に存在し，! で照合に失敗するたびにバックトラックで別の分け方を試す（ReDoS）。入れ子の量指定子をなくすことなどで対策する。
検証用の出典出典照合済み
CWE-1333 Inefficient Regular Expression Complexity ／ CWE-777 Regular Expression without Anchors照合の根拠（4 件）
- エ（正解）・ウ（誤り）: バックトラック型エンジンは一致しないと別の照合の仕方を試す
Some regular expression engines have a feature called "backtracking". If the token cannot match, the engine "backtracks" to a position that may result in a different token that can match.
CWE-1333 · Background Details（新しいタブで開きます） - エ（正解）・ウ（誤り）: 試行回数が入力長に対して指数関数的で，入力が不一致になり得て，十分に長いときに問題になる（入力長に比例する時間では終わらない）
Backtracking becomes a weakness if all of these conditions are met: The number of possible backtracking attempts is exponential relative to the length of the input. The input can fail to match the regular expression. The input can be long enough.
CWE-1333 · Modes of Introduction（新しいタブで開きます） - エ（正解）: 入れ子の量指定子をなくすことが対策になる
Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
CWE-1333 · Potential Mitigations（新しいタブで開きます） - ア（誤り）: 部分一致による通過はアンカーを省いた場合の問題であり，^ と $ を指定したこの正規表現には当たらない
The product uses a regular expression to perform neutralization, but the regular expression omits one or more anchors that may allow malicious or malformed data to slip through.
CWE-777 · Description（新しいタブで開きます）
a を 30 個並べた後に ! があるので必ず不一致になり，([a-z0-9]+)* は a の並びのグループの分け方（2^29 通り）を全て試してから不一致を確定する。イ は入力がパターンとして解釈されることはないので，正解の根拠から論理的に排除される。OWASP の ReDoS 記事（owasp.org）は取得できないため CWE を用いた。