Go-fuzz 解析和思考

作者：時鐘@RainSec
本文為作者投稿，Seebug Paper 期待你的分享，凡經采用即有禮品相送！ 投稿郵箱：paper@seebug.org

go-fuzz

Go-fuzz的原理很多都是基于AFL，這里只分析了一些它獨特的地方，收獲很多，也希望可以和大家交流，如有分析錯誤還望交流指正。

go-fuzz是google開源的一款go語言fuzz框架，它和AFL很大的一個不同是在于，AFL通常通過對未修改的文件的輸入進行操作，而go-fuzz需要你編寫一個Fuzz函數，go-fuzz通過不斷的調用該函數來進行fuzz，前者通常會為每一個輸入創建一個新的進程，后者則是不斷的調用Fuzz函數因此不需要經常啟動或者重啟進程。

什么是覆蓋引導型Fuzz

覆蓋引導型Fuzz通過代碼覆蓋率信息來決定一個突變是否有效，如果代碼覆蓋率增長就保存該輸入并對其進行持續變異，否則就丟棄該變異：

源碼解析

go-fuzz-build模塊

該模塊的主要作用在于將需要測試的包信息和測試用例信息打包方便進行測試。

1. 利用PProf進行性能分析
2. 加載選中的go語言包和github.com/dvyukov/go-fuzz/go-fuzz-dep這個fuzz材料包
3. 遍歷加載的go語言包里面所有的函數名查找所有的名為Fuzz的函數，同時進行簽名認證，但是Fuzz函數的個數應該大于0同時小于等于255
4. 獲取環境變量，大多是和go有關的環境變量.
5. 加載go語言標準庫
6. 忽略一些標準庫中的包和github.com/dvyukov/go-fuzz/go-fuzz-dep這個包，因為沒有理由進行fuzz測試，為了避免陷入循環（具體為啥我也不是很清楚）
7. 在/tmp下創建臨時文件夾保存需要使用的tools和包
8. 接下來就是很高階的語法樹等的建立過程，這個過程中會使用gatherLiterals獲取到你提供的初始材料
9. 獲取到需要fuzz的包的具體信息，進而可以生成go-fuzz的元數據
10. 將存儲信息的cover.exe和sonar.exe已經metadata打包生成zip文件夾

語法樹插樁實現

go語言不同于C語言可以as等匯編工具來較為方便的實現編譯時插樁（具體可以參考AFL的插樁方式），為了實現go語言的編譯時插樁，我們首先要了解go語言整體的編譯流程：

1. 詞法與語法分析
2. 類型檢查
3. 中間代碼生成
4. 機器碼生成

那么其實大致就可以看出比較理想的地方就是詞法與語法分析的時候對抽象語法書進行插樁了，同時go標準庫也提供了scanner，ast和token等相關庫來幫助很好的掃描，解析和創建相關抽象語法樹，在整個插樁的過程中其實是把go的包一個個遍歷插樁的，然后因為go-fuzz不允許導入main包，其實是因為它在插樁完成之后會自己加入相關的main函數。

在go-fuzz-build中實現了結構體File和結構體Sonar，這兩個結構體都實現了自己的Visit()函數用來遍歷相關的語法樹：

type File struct {
    fset     *token.FileSet
    pkg      string
    fullName string
    astFile  *ast.File
    blocks   *[]CoverBlock
    info     *types.Info
}

type Sonar struct {
    fset     *token.FileSet
    fullName string
    pkg      string
    blocks   *[]CoverBlock
    info     *types.Info
}

在整個的build的過程中也會生成coverBin和sonarBin兩個文件分別對應上述兩個結構體的語法樹遍歷函數執行結果。

File遍歷

在生成coverBin的時候使用的是File結構體對應的Visit遍歷函數，不過在開始遍歷之前會通過自身實現的addImport來實現go-fuzz-dep包相關內容的導入：

file.addImport("go-fuzz-dep", fuzzdepPkg, "CoverTab")

func (f *File) addImport(path, name, anyIdent string) {
    newImport := &ast.ImportSpec{
        Name: ast.NewIdent(name),
        Path: &ast.BasicLit{
            Kind:  token.STRING,
            Value: fmt.Sprintf("%q", path),
        },
    }
    impDecl := &ast.GenDecl{
        Lparen: f.astFile.Name.End(),
        Tok:    token.IMPORT,
        Specs: []ast.Spec{
            newImport,
        },
        Rparen: f.astFile.Name.End(),
    }
    // Make the new import the first Decl in the file.
    astFile := f.astFile
    astFile.Decls = append(astFile.Decls, nil)
    copy(astFile.Decls[1:], astFile.Decls[0:])
    astFile.Decls[0] = impDecl
    astFile.Imports = append(astFile.Imports, newImport)

    // Now refer to the package, just in case it ends up unused.
    // That is, append to the end of the file the declaration
    //  var _ = _cover_atomic_.AddUint32
    reference := &ast.GenDecl{
        Tok: token.VAR,
        Specs: []ast.Spec{
            &ast.ValueSpec{
                Names: []*ast.Ident{
                    ast.NewIdent("_"),
                },
                Values: []ast.Expr{
                    &ast.SelectorExpr{
                        X:   ast.NewIdent(name),
                        Sel: ast.NewIdent(anyIdent),
                    },
                },
            },
        },
    }
    astFile.Decls = append(astFile.Decls, reference)
}

觀察源碼其實邏輯也很簡單，首先創建了一個基本聲明信息節點來將相關的包導入原本的語法樹中，同時為了避免導入包但是未使用，所以導入簡單的聲明語句。導入完成之后使用ast.Walk()來遍歷語法樹，該函數會調用File結構體對應的Visit函數。

// 源碼太長，只貼部分
func (f *File) Visit(node ast.Node) ast.Visitor {
    switch n := node.(type) {
    case *ast.FuncDecl:
        if n.Name.String() == "init" {
            // Don't instrument init functions.
            // They run regardless of what we do, so it is just noise.
            return nil
        }
    case *ast.GenDecl:
        if n.Tok != token.VAR {
            return nil // constants and types are not interesting
        }

    case *ast.BlockStmt: // {}中間的語句
        // If it's a switch or select, the body is a list of case clauses; don't tag the block itself.
        if len(n.List) > 0 {
            switch n.List[0].(type) {
            case *ast.CaseClause: // switch
                for _, n := range n.List {
                    clause := n.(*ast.CaseClause)
                    clause.Body = f.addCounters(clause.Pos(), clause.End(), clause.Body, false)
                }
                return f
            case *ast.CommClause: // select
                for _, n := range n.List {
                    clause := n.(*ast.CommClause)
                    clause.Body = f.addCounters(clause.Pos(), clause.End(), clause.Body, false)
                }
                return f
            }
        }
        n.List = f.addCounters(n.Lbrace, n.Rbrace+1, n.List, true) // +1 to step past closing brace.
......
}

可以看出在遍歷語法樹的過程中對節點的類型進行了判斷，然后對{}中間的內容進行一個判斷和插樁，具體的插樁函數如下：

func (f *File) addCounters(pos, blockEnd token.Pos, list []ast.Stmt, extendToClosingBrace bool) []ast.Stmt {
    // Special case: make sure we add a counter to an empty block. Can't do this below
    // or we will add a counter to an empty statement list after, say, a return statement.
    if len(list) == 0 {
        return []ast.Stmt{f.newCounter(pos, blockEnd, 0)}
    }
    // We have a block (statement list), but it may have several basic blocks due to the
    // appearance of statements that affect the flow of control.
    var newList []ast.Stmt
    for {
        // Find first statement that affects flow of control (break, continue, if, etc.).
        // It will be the last statement of this basic block.
        var last int
        end := blockEnd
        for last = 0; last < len(list); last++ {
            end = f.statementBoundary(list[last])
            if f.endsBasicSourceBlock(list[last]) {
                extendToClosingBrace = false // Block is broken up now.
                last++
                break
            }
        }
        if extendToClosingBrace {
            end = blockEnd
        }
        if pos != end { // Can have no source to cover if e.g. blocks abut.
            newList = append(newList, f.newCounter(pos, end, last)) // 在List里面增加counter計數器
        }
        newList = append(newList, list[0:last]...)
        list = list[last:]
        if len(list) == 0 {
            break
        }
        pos = list[0].Pos()
    }
    return newList
}

假設現在有一個switch的demo

func main() {
    var n = 1
    switch n {
    case 0:
        fmt.Println("this is 0")
    case 1:
        fmt.Println("this is 1")
    }
}

這一步的具體操作就是把每一個case拿出來，然后將case相關的語法樹的起始位置和結束位置還有body部分全部傳入addCounters，addCounters的邏輯起始也非常簡單，如果body為空就直接返回一個Counter的ast.Stmt聲明語法樹結構，

Counter是作者自定義的一種插樁計數器，這種計數器主要包括兩個部分:

1. 對于每個包的File的結構體都維護了一個*[]CoverBlock，每次增加Counter都會在這個數組里面增加一個CoverBlock里面記錄了插樁語法樹的位置以及內部是否還包含多少其他聲明。
2. 一個是ast.IncDecStmt節點，這個是newCounter()函數的返回值

如果body不為空就找到所有影響控制流的聲明，比如if，switch, break ,goto等都會開啟或者中斷一個新的控制流，找到邊界聲明之后判斷其是否屬于剛才的類型：

func (f *File) endsBasicSourceBlock(s ast.Stmt) bool {
    switch s := s.(type) {
    case *ast.BlockStmt:
        // Treat blocks like basic blocks to avoid overlapping counters.
        return true
    case *ast.BranchStmt:
        return true
    case *ast.ForStmt:
        return true
    case *ast.IfStmt:
        return true
    case *ast.LabeledStmt:
        return f.endsBasicSourceBlock(s.Stmt)
    case *ast.RangeStmt:
        return true
    case *ast.SwitchStmt:
        return true
    case *ast.SelectStmt:
        return true
    case *ast.TypeSwitchStmt:
        return true
    case *ast.ExprStmt:
        // Calls to panic change the flow.
        // We really should verify that "panic" is the predefined function,
        // but without type checking we can't and the likelihood of it being
        // an actual problem is vanishingly small.
        if call, ok := s.X.(*ast.CallExpr); ok {
            if ident, ok := call.Fun.(*ast.Ident); ok && ident.Name == "panic" && len(call.Args) == 1 {
                return true
            }
        }
    }
    found, _ := hasFuncLiteral(s)
    return found
}

其實就是大量的switch語句，如果是的話，就可以將直接邊界作為end進行插樁，這一步的意義其實就是在于把{}里面的body不斷的分割成一個個可以影響控制流的小塊進行分別插樁。其實到這里我們就可以洞悉go-fuzz整個的插樁思想：在語法分析的時候就通過go-fuzz本身所包含的一個包的內容插樁到各個可以影響控制流的語句塊中，那么接下來對應的工作就應該是如何對這些進行插樁語句塊進行感知，這其實就是Sonar結構體的作用，這是go-fuzz發明的聲吶系統。

Sonar遍歷

Sonar結構體同樣實現了Visit方法來用于遍歷語法樹，部分源碼如下：

func (s *Sonar) Visit(n ast.Node) ast.Visitor {
switch nn := n.(type) {
    case *ast.BinaryExpr:
        break
......
case *ast.SwitchStmt:
        if nn.Tag == nil || nn.Body == nil {
            return s // recurse
        }
        // Replace:
        //  switch a := foo(); bar(a) {
        //  case x: ...
        //  case y: ...
        //  }
        // with:
        //  switch {
        //  default:
        //      a := foo()
        //      __tmp := bar(a)
        //      switch {
        //      case __tmp == x: ...
        //      case __tmp == y: ...
        //      }
        //  }
        // The == comparisons will be instrumented later when we recurse.
        sw := new(ast.SwitchStmt)
        *sw = *nn
        var stmts []ast.Stmt
        if sw.Init != nil {
            stmts = append(stmts, sw.Init)
            sw.Init = nil
        }
        const tmpvar = "__go_fuzz_tmp"
        tmp := ast.NewIdent(tmpvar)
        typ := s.info.Types[sw.Tag]
        s.info.Types[tmp] = typ
        stmts = append(stmts, &ast.AssignStmt{Lhs: []ast.Expr{tmp}, Tok: token.DEFINE, Rhs: []ast.Expr{sw.Tag}})
        stmts = append(stmts, &ast.AssignStmt{Lhs: []ast.Expr{ast.NewIdent("_")}, Tok: token.ASSIGN, Rhs: []ast.Expr{tmp}})
        sw.Tag = nil
        stmts = append(stmts, sw)
        for _, cas1 := range sw.Body.List {
            cas := cas1.(*ast.CaseClause)
            for i, expr := range cas.List {
                tmp := &ast.Ident{Name: tmpvar, NamePos: expr.Pos()}
                s.info.Types[tmp] = typ
                cas.List[i] = &ast.BinaryExpr{X: tmp, Op: token.EQL, Y: expr}
            }
        }
        nn.Tag = nil
        nn.Init = nil
        nn.Body = &ast.BlockStmt{List: []ast.Stmt{&ast.CaseClause{Body: stmts}}}
        return s // recurse
......
}

第一步先根據節點類型找到Switch和For這種結構進行語法樹級別的變化，整體的替換邏輯已經在注釋里面體現出來了，其實就是類似把switch的條件都提出來放在body內部，然后再body里面建立一個新的switch結構，主要作用可能就是方便識別和統計，對于ast.BinaryExpr結構則是通過自定義的flag進行標注。

整體來看其實就是對包內代碼各種語法樹節點進行類型檢查和過濾，因為一些代碼是肯定順序執行的，然后再需要的地方都插入一些標志，同時在結構體里面記錄標志的總量，方便在fuzz執行的時候確定自己的代碼位置從而更方便進行統計，具體的可以細看相關代碼。

插樁總結

其實無論是File還是Sonar，個人認為都算是一種插樁，方便對代碼覆蓋率進行統計，在結束之后都通過createFuzzMain函數進行了封裝，這個地方其實也是go-fuzz不支持fuzz的代碼包含main函數的具體原因：

func (c *Context) createFuzzMain() string {
    mainPkg := filepath.Join(c.fuzzpkg.PkgPath, "go.fuzz.main")
    path := filepath.Join(c.workdir, "gopath", "src", mainPkg)
    c.mkdirAll(path)
    c.writeFile(filepath.Join(path, "main.go"), c.funcMain())
    return mainPkg
}

其實就是將已經寫好的main函數模板寫入：

var ainSrc = template.Must(template.New("main").Parse(`
package main

import (
    target "{{.Pkg}}"
    dep "go-fuzz-dep"
)

func main() {
    fns := []func([]byte)int {
        {{range .AllFuncs}}
            target.{{.}},
        {{end}}
    }
    dep.Main(fns)
}
`))

主要作用還是調用包內的Fuzz代碼。

go-fuzz

1. 首先通過丟棄觸發相同代碼路徑的的樣本來最小化語料庫。
2. 開始改變輸入并將數據傳遞給Fuzz函數，不失敗（return 1），然后擴展代碼覆蓋率的突變會被保留和迭代形成新的樣本。
3. 當程序出現Crash的時候，會保存報告并重新啟動程序。

Fuzz這塊的具體原理其實都是參考的AFL，就不多說了，詳細也可以參考AFL的Fuzz方式和源碼。

測試用例

首先簡單介紹一下go的Fuzz函數的基本信息：

func Fuzz(data []byte) int {

}

該函數以int作為返回值，因此當其返回值為0的時候說明Fuzz對于數據不敢影響，可能的原因是測試目標發生了無意義的錯誤，比如輸入內容不合法等，返回值為1說明該數據已經被成功解析，簡單來說就是Fuzz輸入的data被目標所接受。

DNS解析器Fuzz

首先第一步是創建初始語料庫，其實就是通過拆解pcap數據包來創造數據：

package main

import (
    "crypto/rand"
    "encoding/hex"
    "log"
    "os"
    "strconv"

    "github.com/miekg/pcap"
)

func fatalIfErr(err error) {
    if err != nil {
        log.Fatal(err)
    }
}

func main() {
    handle, err := pcap.OpenOffline(os.Args[1])
    fatalIfErr(err)

    b := make([]byte, 4)
    _, err = rand.Read(b)
    fatalIfErr(err)
    prefix := hex.EncodeToString(b)

    i := 0
    for pkt := handle.Next(); pkt != nil; pkt = handle.Next() {
        pkt.Decode()

        f, err := os.Create("p_" + prefix + "_" + strconv.Itoa(i))
        fatalIfErr(err)
        _, err = f.Write(pkt.Payload)
        fatalIfErr(err)
        fatalIfErr(f.Close())

        i++
    }
}

編寫初步的Fuzz函數：

func Fuzz(rawMsg []byte) int {
    msg := &dns.Msg{}

    if unpackErr := msg.Unpack(rawMsg); unpackErr != nil {
        return 0
    }

    if _, packErr = msg.Pack(); packErr != nil {
        println("failed to pack back a message")
        spew.Dump(msg)
        panic(packErr)
    }

    return 1
}

作者在發現了越界：

func unpackTxt(msg []byte, offset, rdend int) ([]string, int, error) {
    var err error
    var ss []string
    var s string
    for offset < rdend && err == nil {
        s, offset, err = unpackTxtString(msg, offset)
        if err == nil {
            ss = append(ss, s)
        }
    }
    return ss, offset, err
}

但是因為這些越界使得程序經常崩潰，并且Fuzz變的緩慢，于是作者先進行了階段性的修復工作，主要修復是使用len(msg)而不是使用保留的偏移量：

func unpackTxt(msg []byte, off0 int) (ss []string, off int, err error) {
    off = off0
    var s string
    for off < len(msg) && err == nil {
        s, off, err = unpackTxtString(msg, off)
        if err == nil {
            ss = append(ss, s)
        }
    }
    return
}

之后修改好的Fuzz，主要的修改在于增加了ParseDNSPacketSafely，并拋棄了一些無意義的錯誤，也可能不斷測試，不斷排除已知的錯誤:

func Fuzz(rawMsg []byte) int {
    var (
        msg, msgOld = &dns.Msg{}, &old.Msg{}
        buf, bufOld = make([]byte, 100000), make([]byte, 100000)
        res, resOld []byte

        unpackErr, unpackErrOld error
        packErr, packErrOld     error
    )

    unpackErr = msg.Unpack(rawMsg)
    unpackErrOld = ParseDNSPacketSafely(rawMsg, msgOld)

    if unpackErr != nil && unpackErrOld != nil {
        return 0
    }

    if unpackErr != nil && unpackErr.Error() == "dns: out of order NSEC block" {
        // 97b0a31 - rewrite NSEC bitmap [un]packing to account for out-of-order
        return 0
    }

    if unpackErr != nil && unpackErr.Error() == "dns: bad rdlength" {
        // 3157620 - unpackStructValue: drop rdlen, reslice msg instead
        return 0
    }

    if unpackErr != nil && unpackErr.Error() == "dns: bad address family" {
        // f37c7ea - Reject a bad EDNS0_SUBNET family on unpack (not only on pack)
        return 0
    }

    if unpackErr != nil && unpackErr.Error() == "dns: bad netmask" {
        // 6d5de0a - EDNS0_SUBNET: refactor netmask handling
        return 0
    }

    if unpackErr != nil && unpackErrOld == nil {
        println("new code fails to unpack valid packets")
        panic(unpackErr)
    }

    res, packErr = msg.PackBuffer(buf)

    if packErr != nil {
        println("failed to pack back a message")
        spew.Dump(msg)
        panic(packErr)
    }

    if unpackErrOld == nil {

        resOld, packErrOld = msgOld.PackBuffer(bufOld)

        if packErrOld == nil && !bytes.Equal(res, resOld) {
            println("new code changed behavior of valid packets:")
            println()
            println(hex.Dump(res))
            println(hex.Dump(resOld))
            os.Exit(1)
        }

    }

    return 1
}

Tips：

其實在Fuzz過程中也會遇到一些結構化的問題，畢竟大型項目都會存在大量的復雜結構體難以變異，這時候才為大家提供一個神器go-fuzz-header：

https://adalogics.com/blog/structure-aware-go-fuzzing-complex-types

云原生下的Fuzz思考

云原生的很多新技術其實都是在老技術的交叉上形成的，其實可以類似go項目結構里面的不同的包，對于很多Fuzz目標來言，像以前那樣直接從最根本處下手已經不太現實可行，比如容器Fuzz其實很難通過生成大量鏡像或者docker client的命令來解決，恰恰相反深入程序內部針對不同函數來編寫Fuzz或許更有價值。

但是缺點也很明顯，首先必須和代碼審計相結合，其次就是由于代碼是否用戶可達或者crash是否真的引發漏洞效果都有待評估，正如go-fuzz創始人所說：“go-fuzz其實更適合開發者來尋求自己項目中存在的bug”，但是漏洞挖掘技術也是在不斷的進步之中，或許可以思考如何把找到的bug發展成漏洞，畢竟對于內存安全的高級語言來說直接謀求可利用漏洞相對困難。

其實在內存漏洞越來越少的現在，這種bug最終演變成漏洞的例子還是有的，就比如linux pkexec提權漏洞，過去幾年大家都認為這是一個bug，但是等利用方式被真正發掘，就能變化成為嚴重的安全問題。

參考資料

https://github.com/dvyukov/go-fuzz

本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/1864/