Go の RE2 でストリーミングフィルタを安全に書く

はじめに#

Go 標準の regexp パッケージは RE2 実装をベースにしており、正規表現の実行時間が入力長に対して線形 であることを保証しています。PCRE 系の実装で起きる ReDoS（Regular expression Denial of Service）の心配がなく、ユーザー入力や外部ログを正規表現で処理する CLI ツールに向いています。

この記事は先日公開した mask-pipe の実装知見をもとに、Go でストリーミングフィルタを書くときに押さえておきたい点をまとめます。

RE2 が線形時間である理由#

PCRE 系のバックトラッキング実装は (a+)+$ のようなネスト量化子で指数的に遅くなります。RE2 は NFA/DFA ベースの実装で、バックトラックを原理的に行わないため入力長 N に対して O(N) で済みます。

代償としてバックリファレンス（\1、\2）やルックアラウンド（(?=...)、(?!...)）は使えません。Go の regexp も同じ制約です。現場で書く「ユーザー入力をサニタイズしたい」「ログからパターンを抜きたい」用途はほぼすべてこの範囲で収まります。

1
import "regexp"
2

3
var awsKey = regexp.MustCompile(`AKIA[0-9A-Z]{16}`)
4

5
func main() {
6
    fmt.Println(awsKey.MatchString("AKIAIOSFODNN7EXAMPLE")) // true
7
}

MustCompile はコンパイル失敗時に panic する初期化用関数です。グローバル変数に代入して使い回すのが定石で、init() で一度コンパイルすればホットループでの再コンパイルを避けられます。

FindAllStringSubmatchIndex を使うパターン#

マスクや置換を行う場合、単に「マッチするか」だけでは足りず、マッチ位置のインデックス が必要です。FindAllStringSubmatchIndex は各マッチの開始・終了位置を []int で返します。

1
pattern := regexp.MustCompile(`sk_(live|test)_[A-Za-z0-9]{24}`)
2
line := "key=sk_live_abcdef0123456789abcdef01"
3

4
matches := pattern.FindAllStringSubmatchIndex(line, -1)
5
for _, m := range matches {
6
    start, end := m[0], m[1]
7
    fmt.Printf("match at [%d:%d] = %q\n", start, end, line[start:end])
8
}

返り値は [全体開始, 全体終了, グループ1開始, グループ1終了, ...] の繰り返しです。位置が取れれば、前後の文字列を残したまま任意のマスク文字列に置き換えられます。

1
func mask(line string, re *regexp.Regexp) string {
2
    var b strings.Builder
3
    last := 0
4
    for _, m := range re.FindAllStringSubmatchIndex(line, -1) {
5
        b.WriteString(line[last:m[0]])
6
        b.WriteString("[REDACTED]")
7
        last = m[1]
8
    }
9
    b.WriteString(line[last:])
10
    return b.String()
11
}

strings.Builder を使うと中間文字列のアロケーションが抑えられ、1 秒に数千行流れるログでも十分な速度が出ます。

bufio.Scanner で行単位に流す#

ストリーミングフィルタの基本形は bufio.Scanner です。標準入力を 1 行ずつ読み、フィルタをかけて標準出力に書き戻します。

1
func main() {
2
    scanner := bufio.NewScanner(os.Stdin)
3
    writer := bufio.NewWriter(os.Stdout)
4
    defer writer.Flush()
5

6
    for scanner.Scan() {
7
        masked := mask(scanner.Text(), awsKey)
8
        fmt.Fprintln(writer, masked)
9
    }
10
    if err := scanner.Err(); err != nil {
11
        fmt.Fprintln(os.Stderr, "scan error:", err)
12
        os.Exit(1)
13
    }
14
}

bufio.Scanner はデフォルトで最大トークンサイズ（bufio.MaxScanTokenSize = 64 KB）までしか読めず、それを超える長い行があると bufio.ErrTooLong で停止します。初期バッファは小さく、必要に応じてこの上限まで自動的に伸びます。ログが長い場合は scanner.Buffer で上限を引き上げます。

1
scanner.Buffer(make([]byte, 0, 64*1024), 1024*1024)

初期容量と最大容量を個別に指定できます。必要以上に大きくするとメモリ使用量が跳ねるので、ワークロードに合わせて決めます。

複数パターンをまとめて走らせる#

mask-pipe では AWS / GitHub / Stripe など複数の既定パターンを同時に走らせます。素朴には各パターンで FindAllStringSubmatchIndex を呼ぶのが正しく、パイプ | で連結した巨大な正規表現を作らない のが安全策です。

巨大な OR 結合は避ける
パターンを (?:pat1|pat2|pat3|...) で結合すると、グループ番号の管理が複雑になり、パターン追加時の影響範囲も広がります。RE2 上でも DFA の状態数が膨れてコンパイル時間が伸びます。各パターンを独立に扱い、マッチ区間のマージだけ後処理する方が保守しやすい構成です。

マッチ区間は互いに重なりうるので、全パターンのマッチ位置を集めてから左から右にマージします。

1
type span struct{ start, end int }
2

3
func merge(spans []span) []span {
4
    sort.Slice(spans, func(i, j int) bool { return spans[i].start < spans[j].start })
5
    out := spans[:0]
6
    for _, s := range spans {
7
        if len(out) == 0 || s.start > out[len(out)-1].end {
8
            out = append(out, s)
9
        } else if s.end > out[len(out)-1].end {
10
            out[len(out)-1].end = s.end
11
        }
12
    }
13
    return out
14
}

これで重複しない区間リストが得られ、置換が予測可能になります。

マルチライン対応のバッファリング#

PEM 秘密鍵のように複数行にまたがるブロックは行単位のフィルタでは検出できません。行単位を基本にしつつ、特定のマーカーで始まったら終端マーカーが来るまでバッファリングする方式が現実的です。

1
var inBlock bool
2
var buf []string
3

4
for scanner.Scan() {
5
    line := scanner.Text()
6
    switch {
7
    case strings.Contains(line, "-----BEGIN"):
8
        inBlock = true
9
        buf = append(buf, line)
10
    case inBlock:
11
        buf = append(buf, line)
12
        if strings.Contains(line, "-----END") {
13
            fmt.Fprintln(writer, "[REDACTED PRIVATE KEY]")
14
            buf = nil
15
            inBlock = false
16
        }
17
    default:
18
        fmt.Fprintln(writer, mask(line, awsKey))
19
    }
20
}

運用上のセーフティネットとして「バッファが一定サイズを超えたら fail-open でそのまま流す」動作にしておくと、異常な入力でフリーズしません。mask-pipe では 100 行または 64 KB を上限にしています。

ベンチマークで線形性を確認する#

Go の testing パッケージで計算量を手触りレベルで検証できます。

1
func BenchmarkMask_1KB(b *testing.B)  { benchMask(b, 1024) }
2
func BenchmarkMask_10KB(b *testing.B) { benchMask(b, 10*1024) }
3
func BenchmarkMask_100KB(b *testing.B){ benchMask(b, 100*1024) }
4

5
func benchMask(b *testing.B, n int) {
6
    input := strings.Repeat("a AKIAIOSFODNN7EXAMPLE ", n/23)
7
    b.SetBytes(int64(len(input)))
8
    b.ResetTimer()
9
    for i := 0; i < b.N; i++ {
10
        _ = mask(input, awsKey)
11
    }
12
}

go test -bench=. -benchmem で実行すると、入力サイズに比例してナノ秒が増えることを確認できます。指数的に伸びないのが RE2 の健全性の証拠です。

まとめ#

Go の regexp は RE2 ベースで ReDoS の心配がなく、CLI のストリーミングフィルタに適している
FindAllStringSubmatchIndex でマッチ位置を取り、strings.Builder で置換を組み立てる
複数パターンは OR 結合せず、独立に評価して区間マージする
マルチライン検出は行バッファ + 上限付き fail-open で安全に実装する

実装例は mask-pipe のコードが参考になります。ストリーミング前提で RE2 を使う場合、パターン設計と区間マージを分離しておくと後からパターンを足すのが楽になります。