Go Fuzzing beta を go-yaml/yaml.v3 で試してみた

Go の fuzzing のプロポーザルについてツイートしていたら，Kaoriya さんに

すでにbeta段階まで来ててちょうど昨日ブログ記事がでてました。go test -fuzzらしいです。https://t.co/HhKR1r1lUz

— MURAOKA Taro (@kaoriya) 2021年6月4日

と教えてもらったので，早速 Go 標準で利用可能になる fuzzing 機能（現在は beta 扱い）を使ってみました．

blog.golang.org

セットアップ

上記のブログ記事に書いてあるやり方で問題なくセットアップできました．

$ git clone https://github.com/go-yaml/yaml.git -b v3
$ cd yaml
$ go get golang.org/dl/gotip  # gotip 入れる
$ gotip download dev.fuzz  # dev.fuzz ブランチの Go をビルドしてインストール
$ gotip version
go version devel go1.17-5542c10fbf Fri Jun 4 03:07:33 2021 +0000 darwin/amd64

使ってみる

gofuzz を使ったことがあるので使い方について困ることは特にありませんでした．

$ gotip doc testing.F

で API 一覧が見られます．

今回 Go に入った fuzzing の機能は go test の一部として実装されていて，Test で始まる関数が単体テスト，Bench で始まる関数がベンチマークであるのと同様に Fuzz で始まる *testing.F を引数に取る関数を書くと，それが fuzzing のターゲットとして定義されます．

上記のブログ記事に倣って fuzzing のためのファイル fuzz_test.go をリポジトリ直下に置いて，

// +build gofuzzbeta

package yaml_test

import (
    "strings"
    "testing"

    "gopkg.in/yaml.v3"
)

func FuzzMarshalUnmarshalYAML(f *testing.F) {
    f.Add("{}")
    f.Add("v: hi")
    f.Add("v: true")
    f.Add("v: 10")
    f.Add("v: 0b10")
    f.Add("v: 0xA")
    f.Add("v: 4294967296")
    f.Add("v: 0.1")
    f.Add("v: .1")
    f.Add("v: .Inf")
    f.Add("v: -.Inf")
    f.Add("v: -10")
    f.Add("v: -.1")
    f.Add("123")
    f.Add("canonical: 6.8523e+5")
    f.Add("expo: 685.230_15e+03")
    f.Add("fixed: 685_230.15")
    f.Add("neginf: -.inf")
    f.Add("fixed: 685_230.15")
    f.Add("canonical: true")
    f.Add("canonical: false")
    f.Add("bool: True")
    f.Add("bool: False")
    f.Add("bool: TRUE")
    f.Add("bool: FALSE")
    f.Add("option: on")
    f.Add("option: y")
    f.Add("option: Off")
    f.Add("option: No")
    f.Add("option: other")
    f.Add("canonical: 685230")
    f.Add("decimal: +685_230")
    f.Add("octal: 02472256")
    f.Add("octal: -02472256")
    f.Add("octal: 0o2472256")
    f.Add("octal: -0o2472256")
    f.Add("hexa: 0x_0A_74_AE")
    f.Add("bin: 0b1010_0111_0100_1010_1110")
    f.Add("bin: -0b101010")
    f.Add("bin: -0b1000000000000000000000000000000000000000000000000000000000000000")
    f.Add("decimal: +685_230")
    f.Add("empty:")
    f.Add("canonical: ~")
    f.Add("english: null")
    f.Add("~: null key")
    f.Add("empty:")
    f.Add("seq: [A,B]")
    f.Add("seq: [A,B,C,]")
    f.Add("seq: [A,1,C]")
    f.Add("seq: [A,1,C]")
    f.Add("seq: [A,1,C]")
    f.Add("seq:\n - A\n - B")
    f.Add("seq:\n - A\n - B\n - C")
    f.Add("seq:\n - A\n - 1\n - C")
    f.Add("scalar: | # Comment\n\n literal\n\n \ttext\n\n")
    f.Add("scalar: > # Comment\n\n folded\n line\n \n next\n line\n  * one\n  * two\n\n last\n line\n\n")
    f.Add("a: {b: c}")
    f.Add("a: {b: c, 1: d}")
    f.Add("hello: world")
    f.Add("a: {b: c}")
    f.Add("a: {b: c}")
    f.Add("a: 'null'")
    f.Add("a: {b: c}")
    f.Add("a: {b: c}")
    f.Add("a:")
    f.Add("a: 1")
    f.Add("a: 1.0")
    f.Add("a: [1, 2]")
    f.Add("a: YES")
    f.Add("v: 42")
    f.Add("v: -42")
    f.Add("v: 4294967296")
    f.Add("v: -4294967296")
    f.Add("int_max: 2147483647")
    f.Add("int_min: -2147483648")
    f.Add("int_overflow: 9223372036854775808")
    f.Add("int64_max: 9223372036854775807")
    f.Add("int64_max_base2: 0b111111111111111111111111111111111111111111111111111111111111111")
    f.Add("int64_min: -9223372036854775808")
    f.Add("int64_neg_base2: -0b111111111111111111111111111111111111111111111111111111111111111")
    f.Add("int64_overflow: 9223372036854775808")
    f.Add("uint_min: 0")
    f.Add("uint_max: 4294967295")
    f.Add("uint_underflow: -1")
    f.Add("uint64_min: 0")
    f.Add("uint64_max: 18446744073709551615")
    f.Add("uint64_max_base2: 0b1111111111111111111111111111111111111111111111111111111111111111")
    f.Add("uint64_maxint64: 9223372036854775807")
    f.Add("uint64_underflow: -1")
    f.Add("float32_max: 3.40282346638528859811704183484516925440e+38")
    f.Add("float32_nonzero: 1.401298464324817070923729583289916131280e-45")
    f.Add("float32_maxuint64: 18446744073709551615")
    f.Add("float32_maxuint64+1: 18446744073709551616")
    f.Add("float64_max: 1.797693134862315708145274237317043567981e+308")
    f.Add("float64_nonzero: 4.940656458412465441765687928682213723651e-324")
    f.Add("float64_maxuint64: 18446744073709551615")
    f.Add("float64_maxuint64+1: 18446744073709551616")
    f.Add("v: 4294967297")
    f.Add("v: 128")
    f.Add("'1': '\"2\"'")
    f.Add("v:\n- A\n- 'B\n\n  C'\n")
    f.Add("v: !!float '1.1'")
    f.Add("v: !!float 0")
    f.Add("v: !!float -1")
    f.Add("v: !!null ''")
    f.Add("%TAG !y! tag:yaml.org,2002:\n---\nv: !y!int '1'")
    f.Add("v: ! test")
    f.Add("a: &x 1\nb: &y 2\nc: *x\nd: *y\n")
    f.Add("a: &a {c: 1}\nb: *a")
    f.Add("a: &a [1, 2]\nb: *a")
    f.Add("foo: ''")
    f.Add("foo: null")
    f.Add("foo: null")
    f.Add("foo: null")
    f.Add("foo: ~")
    f.Add("foo: ~")
    f.Add("foo: ~")
    f.Add("a: 1\nb: 2\n")
    f.Add("Line separator\u2028Paragraph separator\u2029")
    f.Add("a: 1\nb: 2\nc: 3\n")
    f.Add("a: 1\nb: 2\nc: 3\n")
    f.Add("a: 1\n")
    f.Add("a: 1\nc: 3\nd: 4\n")
    f.Add("a: 1\nb: 2\nc: 3\n")
    f.Add("a: -b_c")
    f.Add("a: +b_c")
    f.Add("a: 50cent_of_dollar")
    f.Add("a: {b: https://github.com/go-yaml/yaml}")
    f.Add("a: [https://github.com/go-yaml/yaml]")
    f.Add("a: 3s")
    f.Add("a: <foo>")
    f.Add("a: 1:1\n")
    f.Add("a: !!binary gIGC\n")
    f.Add("a: !!binary |\n  " + strings.Repeat("kJCQ", 17) + "kJ\n  CQ\n")
    f.Add("a: !!binary |\n  " + strings.Repeat("A", 70) + "\n  ==\n")
    f.Add("a:\n b:\n  c: d\n")
    f.Add("a: {b: c}")
    f.Add("a: 1.2.3.4\n")
    f.Add("a: 2015-02-24T18:19:39Z\n")
    f.Add("a: 2015-01-01\n")
    f.Add("a: 2015-02-24T18:19:39.12Z\n")
    f.Add("a: 2015-2-3T3:4:5Z")
    f.Add("a: 2015-02-24t18:19:39Z\n")
    f.Add("a: 2015-02-24 18:19:39\n")
    f.Add("a: !!str 2015-01-01")
    f.Add("a: !!timestamp \"2015-01-01\"")
    f.Add("a: !!timestamp 2015-01-01")
    f.Add("a: \"2015-01-01\"")
    f.Add("a: !!timestamp \"2015-01-01\"")
    f.Add("a: 2015-01-01")
    f.Add("a: []")
    f.Add("\xff\xfe\xf1\x00o\x00\xf1\x00o\x00:\x00 \x00v\x00e\x00r\x00y\x00 \x00y\x00e\x00s\x00\n\x00")
    f.Add("\xff\xfe\xf1\x00o\x00\xf1\x00o\x00:\x00 \x00v\x00e\x00r\x00y\x00 \x00y\x00e\x00s\x00 \x00=\xd8\xd4\xdf\n\x00")
    f.Add("\xfe\xff\x00\xf1\x00o\x00\xf1\x00o\x00:\x00 \x00v\x00e\x00r\x00y\x00 \x00y\x00e\x00s\x00\n")
    f.Add("\xfe\xff\x00\xf1\x00o\x00\xf1\x00o\x00:\x00 \x00v\x00e\x00r\x00y\x00 \x00y\x00e\x00s\x00 \xd8=\xdf\xd4\x00\n")
    f.Add("a: 123456e1\n")
    f.Add("a: 123456E1\n")
    f.Add("First occurrence: &anchor Foo\nSecond occurrence: *anchor\nOverride anchor: &anchor Bar\nReuse anchor: *anchor\n")
    f.Add("---\nhello\n...\n}not yaml")
    f.Add("hello")
    f.Add("true")
    f.Add("true")
    f.Add("a: b\r\nc:\r\n- d\r\n- e\r\n")
    f.Add("a: b")
    f.Add("---\na: b\n...\n")
    f.Add("---\n'hello'\n...\n---\ngoodbye\n...\n")
    f.Add("hello")
    f.Add("goodbye")
    f.Add("i: &i [*h,*h,*h,*h,*h,*h,*h,*h,*h]\n")
    f.Add("yaml: document contains excessive aliasing")
    f.Add("null")
    f.Add("s2: null\ns3: null")
    f.Add("s2: null\ns3: null")
    f.Add("\"\\0\\\r\n")
    f.Add("  0: [\n] 0")
    f.Add("? ? \"\n\" 0")
    f.Add("    - {\n000}0")
    f.Add("0:\n  0: [0\n] 0")
    f.Add("    - \"\n000\"0")
    f.Add("    - \"\n000\"\"")
    f.Add("0:\n    - {\n000}0")
    f.Add("0:\n    - \"\n000\"0")
    f.Add("0:\n    - \"\n000\"\"")
    f.Add(" \ufeff\n")
    f.Add("? \ufeff\n")
    f.Add("? \ufeff:\n")
    f.Add("0: \ufeff\n")
    f.Add("? \ufeff: \ufeff\n")

    f.Fuzz(func(t *testing.T, data string) {
        var n yaml.Node

        if err := yaml.Unmarshal([]byte(data), &n); err != nil {
            t.Skip() // Not a valid input
        }

        b, err := yaml.Marshal(&n)
        if err != nil {
            t.Fatalf("Marshal failed to encode valid YAML tree %#v: %v", &n, err)
        }
        if err := yaml.Unmarshal(b, &n); err != nil {
            t.Fatalf("Marshal failed to decode valid YAML bytes %#v: %v", b, err)
        }
    })
}

簡単に中身を解説すると，

// +build gofuzzbeta

今はこのビルドタグを付けておく必要があります．リリース済みのバージョンの Go との互換性のため？みたいなので，正式リリース時には不要になりそうです．

f.Add("{}")
// ...

f.Fuzz(func(t *testing.T, data string) {
    // ...
})

fuzzing では事前にデータセット（コーパス）を与えることで効率的に入力を生成できます．多分無くても問題は無いですが，事前情報無しに入力を生成していくので効率は悪くなるはずです．Go では f.Add() で有効な入力を文字列で教えてやります．今回はお試しなので decode_test.go で使われているテストケースから適当に引っ張ってきました．

f.Fuzz() にコールバックを与えると，fuzzer が生成した入力に対してコールバックが呼ばれます．コールバックの第2引数は interface{} なので好きな引数型を指定して良さそうですが，[]byte にしてみたらランタイムエラーでダメだったので，上記ブログ記事に合わせて string にしてあります．今回は YAML パーサに対して試すので，入力はバイト列ならとりあえずなんでも良く，まあ string で OK です（Go の string は UTF-8 的に不正なシーケンスでも良いので）．

var n yaml.Node

if err := yaml.Unmarshal([]byte(data), &n); err != nil {
    t.Skip() // Not a valid input
}

b, err := yaml.Marshal(&n)
if err != nil {
    t.Fatalf("Marshal failed to encode valid YAML tree %#v: %v", &n, err)
}
if err := yaml.Unmarshal(b, &n); err != nil {
    t.Fatalf("Marshal failed to decode valid YAML bytes %#v: %v", b, err)
}

f.Fuzz() のコールバックの中では fuzzer から与えられた入力を使って，普段の単体テストのようにテストを書きます．今回は YAML のパーサとジェネレータを fuzzing したいので，パーサに食わせてみて，YAML として正しくない入力だった場合（yaml.Unmarshal が error を返した場合）はそれ以降の実行を諦めて t.Skip() します． yaml.Unmarshal が成功し，YAML として正しい入力だと分かったら，パース結果を yaml.Marshal で再度文字列化してジェネレータがクラッシュしないかを見ます．さらにジェネレータが正しい出力を吐けたか見るために，再度 yaml.Unmarshal に食わせてみています．初回のパース結果と2回目は完全に一致することが期待されるので，go-cmp などを使ってチェックしても良いかもしれません．

問題を検知した場合には普段どおり t.Fatal を使えば良いみたいです．

実行してみる

$ gotip test -fuzz=FuzzMarshalUnmarshalYAML

-fuzz にターゲットを指定すると実行が始まります．コアをあるだけ使おうとするので，-parallel でコア数を制限したほうが良いかもしれません．あとは問題を検知するまで放置するだけです．

今回はこんな感じで割とすぐ panic を引くことができました．

OK: 45 passed
fuzzing, elapsed: 3.0s, execs: 504 (168/sec), workers: 20, interesting: 19
fuzzing, elapsed: 6.0s, execs: 975 (162/sec), workers: 20, interesting: 28
fuzzing, elapsed: 9.0s, execs: 1441 (160/sec), workers: 20, interesting: 41

snip...

fuzzing, elapsed: 126.0s, execs: 19330 (153/sec), workers: 20, interesting: 126
fuzzing, elapsed: 129.0s, execs: 19794 (153/sec), workers: 20, interesting: 126
fuzzing, elapsed: 132.0s, execs: 20256 (153/sec), workers: 20, interesting: 127
found a crash, minimizing...
fuzzing, elapsed: 134.3s, execs: 20482 (153/sec), workers: 20, interesting: 127
--- FAIL: FuzzMarshalUnmarshalYAML (134.26s)
        panic: runtime error: invalid memory address or nil pointer dereference
        goroutine 2190 [running]:
        runtime/debug.Stack()
                /Users/rhysd/sdk/gotip/src/runtime/debug/stack.go:24 +0x90
        testing.tRunner.func1.2({0x12ee440, 0x14eb340})
                /Users/rhysd/sdk/gotip/src/testing/testing.go:1271 +0x267
        testing.tRunner.func1()
                /Users/rhysd/sdk/gotip/src/testing/testing.go:1278 +0x218
        panic({0x12ee440, 0x14eb340})
                /Users/rhysd/sdk/gotip/src/runtime/panic.go:1038 +0x215

        snip...

        testing.(*F).Fuzz.func1.1(0x137d850)
                /Users/rhysd/sdk/gotip/src/testing/fuzz.go:347 +0x193
        testing.tRunner(0xc0005f5a00, 0xc0006188c0)
                /Users/rhysd/sdk/gotip/src/testing/testing.go:1325 +0x102
        created by testing.(*F).Fuzz.func1
                /Users/rhysd/sdk/gotip/src/testing/fuzz.go:341 +0x545

        --- FAIL: FuzzMarshalUnmarshalYAML (0.00s)

    Crash written to testdata/corpus/FuzzMarshalUnmarshalYAML/023ce39f07f2e64e497d71b869e21d232cfd6bd939c8e2e0904adb8685cf9caa
    To re-run:
    go test gopkg.in/yaml.v3 -run=FuzzMarshalUnmarshalYAML/023ce39f07f2e64e497d71b869e21d232cfd6bd939c8e2e0904adb8685cf9caa
FAIL
exit status 1
FAIL    gopkg.in/yaml.v3        139.073s

問題を引いた入力は testdata/corpus/{ターゲット名} 以下に保存されます．保存されたファイルを見てみると，

go test fuzz v1
string("#\n - - QI\xd7")

となっていて，実際のクラッシュする入力は string 型で "#\n - - QI\xd7" という値になることが分かります．

go test gopkg.in/yaml.v3 -run=FuzzMarshalUnmarshalYAML/023ce39f07f2e64e497d71b869e21d232cfd6bd939c8e2e0904adb8685cf9caa

のように {ターゲット名}/{コーパス名} を指定してテスト実行すると，クラッシュを引いた入力を与えて再実行することができます．これでクラッシュに再現性があるかどうかを確認できます．

再現の仕方が分かれば，後はクラッシュを修正するなり報告するなりするだけです．

github.com

今回分からなかったこと

• fuzzing は通常，ある fuzzing 実施で育てたコーパスを次の fuzzing 実行で使うみたいなことをすると思うのですが，上記の f.Add() で追加する以外でコーパスを追加する方法がわかりませんでした．libFuzzer はコーパスをディレクトリに吐いたりディレクトリから読み込むとかできるので，似た機能がありそうなもんですが…
• f.Fuzz() のコールバックの第2引数に使える型が分からない．少なくとも string が使えますが，他に何が使えるのか