YAMAGUCHI::weblog

海水パンツとゴーグルで、巨万の富を築きました。カリブの怪物、フリーアルバイター瞳です。

Goの正規表現エンジンを使ってファジング用ツールを書いてみる

はじめに

こんにちは、Go界のコリン・ファースです。この記事はGo Advent Calendar 2014の21日目の記事です。昨日初サバゲーしたら、左手の薬指の爪のどまんなか含め、ピンポイントに左手の薬指3箇所を撃たれて、めっちゃ痛いです。

ところで今年のGo Advent Calendarではすでに2本の記事が正規表現に関する記事が上がっています。

@methane さんの記事の中では「Goの正規表現エンジンが遅い」という話が出ていました。また @ikawaha さんの記事では丁寧にVirtual Machine Approachな正規表現エンジンを実装する方法について書かれています。*1

本エントリでは実際にGoの正規表現エンジンはどういう実装になってるのかを簡単に触れて、そこで使われているVMを再利用してファジング用ツールを書いてみます。

TL;DR

Goの正規表現エンジン内で使っているバイトコードを利用して、ファジングなどで使えそうな正規表現パターンに合致するランダムな文字列を生成するツールを書いてみた。

Goでの正規表現エンジンの実装

Russ Coxによるアプローチ

Goのregexpパッケージの実装に大きくかかわっているRuss Coxは、Goのコアチームであり、RE2の実装をした本人です。そういった経緯からGoでの正規表現エンジンの実装もRE2で使われている手法と同様の、VMを使った実装になっています。すでに @ikawaha さんのエントリの中でも説明されていますが、雑に言えば有限オートマトンの状態をバイトコードの命令に落としこんでやるというものです。

詳しい話はRuss Coxの記事にボリューム満載に書いてあるのでぜひご一読されることをおすすめします。

regexp

そもそもGoのregexpパッケージを使うときはどのようにしていたか、ここでおさらいしてみます。Goの正規表現パッケージでは次の2段階となっています。使用方法のサンプルはドキュメントにあるもので確認してください。

  1. 正規表現パターンをCompileしてregexp.Regexpインスタンスを作成
  2. 作成したRegexpインスタンスでFind系のメソッドを実行する

この順番で見ていけばどうなってるのか分かりそうなので中を細かく見て行きたいところですが、本題に入る前に長くなってしまうので割愛。後日Qiitaにまとめてみます。

1.の段階、つまりCompile()を実行すると、中ではregexp/syntaxパッケージのParse()が呼ばれ、syntax.Regexpインスタンスが作成され、それがVMバイトコードに変換されています。そのバイトコード全体がsyntax.Progです。

2.の段階で、実際にマッチングをはじめると、regexp.doExecute()内で1.で作成されたバイトコードを実行し始めます。このときに、生成されるのが @ikawaha さんのエントリにあったmachine構造体のインスタンスです。

ということで、まとめると、次の二段階がそのままパッケージに反映されていることがわかります。

  1. 正規表現パターンをVMバイトコードにする: regexp/syntax
  2. VMを作成しバイトコードを実行する: regexp

今回は普段あまり触れられることがないであろう1のregexp/syntaxについて見てみます。

regexp/syntax

これは先に挙げたRuss Coxの2番目の記事の方法がそのまま反映された実装になっています。大きく分けて3つの構造体があります。

  • Regexpregexp.Regexpと同じ名前なので要注意。こちらはあくまでパターンをVMの実行形式に変換したまとまり)
  • Prog(VMバイトコード全体を保持する構造体)
  • Inst(各命令を表す構造体)

さきほど、「regexp.Compile()でバイトコードにする」と書いていましたが、その内部ではsyntax.Regexp.Parse()メソッドを呼んで、さらにsyntax.Regexp.Simplify()メソッドを呼んでから実際のCompile()を行っています。このSimplify()によってPCREの複雑なパターンを次の4つだけを使った形式に変換しています。

  • e1e2 (2つの状態が結合している)
  • e1|e2 (2つの状態に分岐している)
  • e1? (空またはe1の状態に分岐している)
  • e1* (e1?と同様の分岐だがループしている)

イメージは先に挙げたRuss Coxの記事の"Converting Regular Expressions to NFAs"の節を読んでください。ためしに次のコードを実行してみましょう。

package main

import (
    "fmt"
    "regexp/syntax"
)

func main() {
    pattern := `aa+bb*[c-z]{1,3}`
    exp, _ := syntax.Parse(pattern, syntax.Perl)
    fmt.Println(exp.Simplify())
}

結果は次の通り

aa+bb*[c-z](?:[c-z][c-z]?)?

このSimplifyしたパターンをバイトコードに変換するのがsyntax.Compile()です。実際にどのような形式になるのか、Compile()関数を呼んで、表示してみましょう。

package main

import (
    "fmt"
    "regexp/syntax"
)

func main() {
    pattern := `aa+bb*[c-z]{1,3}`
    exp, _ := syntax.Parse(pattern, syntax.Perl)
    prog, _ := syntax.Compile(exp.Simplify())
    fmt.Println(prog)
}

次のように表示されました。

  0  fail
  1*    rune1 "a" -> 2
  2 rune1 "a" -> 3
  3 alt -> 2, 4
  4 rune1 "b" -> 6
  5 rune1 "b" -> 6
  6 alt -> 5, 7
  7 rune "cz" -> 11
  8 rune "cz" -> 10
  9 rune "cz" -> 12
 10 alt -> 9, 12
 11 alt -> 8, 12
 12 match

いかにもバイトコードらしい出力が得られました。各命令(状態)に関してはsyntax.InstOpに列挙されています。ドキュメントに各定数が何を表しているかの記載がないので、自分でざっとコード読んでみたり動かした感じだとこんなかんじです。(InstEmptyやInstEmptyMatchらへんはまだそうなるパターンを見てません)

  • InstFail: 失敗状態
  • InstMatch: 受領状態
  • InstAlt: 分岐
  • InstAltMatch: 分岐または受領
  • InstRune1: 指定された1文字で遷移
  • InstRune: 指定された範囲のなかから1文字で遷移
  • InstCapture: 括弧の開始または終了

正規表現のマッチングではこのバイトコードを使って、入力された文字列を先頭から一文字ずつマッチしていくか見ていくわけですが、これを逆に使えば、正規表現のパターンに合致する文字列を生成することができそうです。

regexp/syntaxを使って正規表現パターンに合致する文字列を生成する

というわけで、実験的に作ってみました。

やっていることは非常に簡単で、正規表現のマッチングをするときに行うCompileまでは同じで、そこでできたバイトコードで、分岐が出たらランダムに遷移するというもの。InstRuneの場合は範囲の中から任意の文字をやはりランダムに出力しています。*2

試しに動かしてみます。

package main

import (
    "fmt"
    "regexp/syntax"

    fuzz "github.com/ymotongpoo/fuzzingo"
)

func main() {
    generator, err := fuzz.NewGenerator("aa+bb*[c-z]{1,3}", syntax.Perl)
    if err != nil {
        panic(err)
    }
    for i := 0; i < 10; i++ {
        str, err := generator.Gen()
        if err != nil {
            fmt.Println(i, err)
        } else {
            fmt.Println(i, str)
        }
    }
}

するとこういう結果が出力されます。

0 aabbbje
1 aabbbs
2 aaaaabbbbbr
3 aaabbbqye
4 aaaaabjh
5 aabbeqc
6 aabr
7 aabbho
8 aaaaabbblo
9 aabesh

パターンに対して正しい結果が出力されていますね!いまは非常に乱暴な実装をしていますが、もうちょっとちゃんと実装したらそこそこ使えるツールになるんじゃないでしょうか。

次は @hogedigo さんです。

*1:僕はそこまで詳しく書けないのでぜひ続編の続編の記事を期待しています!

*2:Unicodeの対応はまだちゃんとはしていません