末尾スラッシュ除去の正規表現がCodeQLでpolynomial-redosに3箇所引っかかった

結論

**先頭にアンカー(^)を付けずに末尾だけ$で固定した正規表現で文字列を削ると、一致を試みる開始位置の探索と量指定子のバックトラックが掛け合わさり、特定の入力でO(n^2)の計算量になる。**CodeQLの js/polynomial-redos はこれを severity: high として検出する。

症状

末尾の連続スラッシュを取り除くために書かれていた、次の1行に対して CodeQL が js/polynomial-redos（high）を検出した。

const trimmed = base.replace(/\/+$/, "");

しかもこの検出は1箇所ではなかった。同じファイル内で、この1行がそのまま3つの関数にコピーされて使われており、CodeQL は3箇所すべてに同じ指摘を出していた。実行時にエラーが起きていたわけではない。静的解析が「この書き方は危険になりうる」と指摘しただけで、動作は普通に成立していた。

この種の指摘は「よくある誤検知だろう」として読み飛ばされやすい。しかし今回は誤検知ではなく、正規表現の書き方そのものに実際にO(n^2)へ広がる余地があるケースだった。

原因

\/+$ は「1つ以上のスラッシュのあとに文字列の終端が続く」という意味で、$ によって終端に固定されているぶん、一見すると安全に見える。しかしこの正規表現には、一致を試みる開始位置を固定するアンカー（^）が無い。

String.prototype.replace は、正規表現が現在の開始位置で一致しなければ、開始位置を1文字ずつ後ろへずらしながら再試行する。^ の無い \/+$ は、文字列中のどの位置からでも「そこから末尾までスラッシュが続くか」を試せてしまう。

入力が「多数のスラッシュのあとに1つだけ非スラッシュの文字が続く」という形（たとえばスラッシュを $n$ 個並べたあとに任意の1文字を置いた文字列）だと、末尾のその1文字のせいで、どの開始位置から試しても最終的に一致は失敗する。ただし失敗が確定するまでに、各開始位置で + が消費するスラッシュの数を1つずつ減らしながら $ との一致を再試行する（バックトラック）。開始位置の候補が最大で文字列長に比例する数だけあり、各開始位置でのバックトラックの試行回数も文字列長に比例しうるため、両者が掛け合わさって全体としてO(n^2)になる。これが CodeQL が js/polynomial-redos として検出した内容にあたる。

このコード自体は、環境変数からベースURLを受け取るseedスクリプトの一部で、その環境変数を設定できるのは運用者だけだった。しかし js/polynomial-redos は「外部から制御されうる値が正規表現に流れ込んでいるか」をたどる規則で、環境変数やコマンドライン引数も追跡対象の入口に含む。「実際にはその入口を運用者しか触れない」という運用上の事情までは判断できないため、severity: high として指摘される。

直す

正規表現をやめ、文字列の末尾から1文字ずつ走査してスラッシュでなくなった位置までを削る線形ループに置き換えた。

function stripTrailingSlashes(s: string): string {
  let end = s.length;
  while (end > 0 && s.charCodeAt(end - 1) === 47 /* '/' */) {
    end -= 1;
  }
  return s.slice(0, end);
}

charCodeAt で末尾から順に見るだけなので、開始位置の探索もバックトラックも発生しない。常に文字列の長さに比例した回数（O(n)）で終わる。3箇所すべてをこの関数の呼び出しに置き換え、「末尾の連続スラッシュをすべて取り除く」という挙動そのものは変えていない。

再発しない形にする

今回の3箇所は、同じ「先頭にアンカーが無く、量指定子を末尾アンカーだけで受ける」という形の正規表現をコピーして使い回していたために、同じ問題が一度に3箇所へ広がっていた。$ が付いているからといって安全とは限らない。

量指定子を使う正規表現でこの種のO(n^2)を避ける手はおもに3つある。(1) 先頭も ^ で固定して開始位置の探索自体を消す（ただし一致の意味が変わるため、今回のような「文字列のどこかにある末尾のスラッシュ列だけを削る」用途には使えない）。(2) + や * を {1,64} のように有界化し、1つの開始位置あたりの試行回数を定数で抑える。開始位置を固定できない /g 付きの正規表現で全体を走査したい場合は、これが実質的に唯一の手になる。(3) そもそも正規表現を使わず走査で書く。今回は挙動を変えずに済む(3)を選んだ。

同じ形（先頭アンカー無し・量指定子・末尾アンカーのみ）の正規表現が他にもコピーされていないかは、この修正と同じ考え方で洗い出せる。ただし js/polynomial-redos は入力の出どころを追跡する規則なので、同じ字面の正規表現でも、外部から制御されうる値が流れ込んでいなければ検出されない。静的解析ツールが同じ指摘を複数箇所で同時に出したときは、1箇所だけ直して終わりにせず、コピー元が同じ他の箇所を先に疑うとよい。