Go Dynamic Tools

Gophercon 2015, July 9, 2015

Video

A video of this talk was recorded at GopherCon in Denver.

Watch the talk on YouTube

About me

Did a bunch of work on Go:

• Scalable goroutine scheduler
• Integrated network poller
• Parallel GC, concurrent sweeping
• Memory allocator speed/space improvements
• Sync primitives
• Race detector
• Blocking profile
• 800+ commits, filed 500+ bugs

But actually on dynamic testing tools team:

• Thread/Address/MemorySanitizer

Agenda

• Data race detector
• Go-fuzz, randomized testing system
• Execution tracer

Data race detector

What is a data race?

A data race occurs when two goroutines access the same variable concurrently and at least one of the accesses is a write.

All bets are off !

Any data race can destroy the memory/type-safety of a Go program.

There are no "benign" data races

// goroutine 1       // goroutine 2
m[k1] = v1           m[k2] = v2

Bad!

// goroutine 1       // goroutine 2
stat++               stat++

Also bad!

Compilers assume race-free programs and do aggressive optimizations
based on that assumption (e.g. assume "ownership" over written-to variables).

Races are non-deterministic and hard to debug.

Usage

$ go test -race mypkg    // to test the package
$ go run -race mysrc.go  // to run the source file
$ go build -race mycmd   // to build the command
$ go install -race mypkg // to install the package

That's it!

Example

package main

func main() {
    m := make(map[int]int)
    go func() {
        m[1] = 1
    }()
    m[2] = 2
}

Example report

WARNING: DATA RACE
Write by goroutine 5:
  runtime.mapassign1()
      runtime/hashmap.go:411 +0x0
  main.main.func1()
      race.go:6 +0x60

Previous write by main goroutine:
  runtime.mapassign1()
      runtime/hashmap.go:411 +0x0
  main.main()
      race.go:8 +0xb6

Goroutine 5 (running) created at:
  main.main()
      race.go:7 +0x76

Achievements

• 70+ bugs in std lib
• 350+??? bugs in Google internal code base
• ??? bugs found in the wild

Instrumentation

Compiler instrumentation pass enabled by -race.

func foo(p *int) {
    *p = 1
}

Becomes:

func foo(p *int) {
    runtime.funcenter(caller_pc)
    runtime.racewrite(p)
    *p = 1
    runtime.funcexit()
}

Run-time module

Handles:

• memory accesses (to catch racy accesses)
• synchronization (to not produce false reports)
• function calls (to collect stack traces)
• goroutine creation/exit (to keep track of live goroutines)

Algorithm is based on dynamic modelling of happens-before relation:

• no false positives
• false negatives are possible

Usage tips

Dynamic tools are only as good as your tests are.

• write good concurrent tests
• have continuous build with race detector
• run integration tests
• run race-enabled canaries in production

Go-fuzz

Randomized testing

A different approach to testing that finds [lots of] bugs that other testing approaches do not. Intended mostly for programs that parse complex inputs.

Generate random blob -> feed into program -> see if it crashes -> profit!

• cheap to use
• does not have any bias

Completely random blobs won't uncover lots of bugs.

How can we generate diverse but meaningful inputs that will trigger
nil derefs, off-by-ones, etc?

Coverage-guided fuzzing

Genetic algorithms to the rescue!

Instrument program for code coverage
Collect initial corpus of inputs
for {
    Randomly mutate an input from the corpus
    Execute and collect coverage
    If the input gives new coverage, add it to corpus
}

Example

The following code wants "ABCD" input:

if input[0] == 'A' {
    if input[1] == 'B' {
        if input[2] == 'C' {
            if input[3] == 'D' {
                panic("input must not be ABCD")
            }
        }
    }
}

Corpus progression:

""
"", "A"
"", "A", "AB"
"", "A", "AB", "ABC"
"", "A", "AB", "ABC", "ABCD"

Game over

CRC32 checksum verification in image/png/reader.go

func (d *decoder) verifyChecksum() error {
    if binary.BigEndian.Uint32(d.tmp[:4]) != d.crc.Sum32() {
        return FormatError("invalid checksum")
    }
    return nil
}

Probability that random mutations will alter input in an interesting way and
guess CRC32 at the same time is basically ZERO.

Sonar

Don't need to guess, program knows it!

+ v1 := binary.BigEndian.Uint32(d.tmp[:4])
+ v2 := d.crc.Sum32()
+ __go_fuzz.Sonar(v1, v2)
if v1 != v2 {
    return FormatError("invalid checksum")
}

Then, find v1 in the input and replace it with v2. Done!

Game over 2

Mutations and sonar do low-level changes ("bit-flipping"):

Original:

`<item name="foo"><prop name="price">100</prop></item>`

Mutated:

`<item name="foo"><prop name="price">100</prop><<item>`

Also want high-level changes!

Versifier

Versifier reverse-engineers [text] protocol and learns its structure.

abc          -> alphanum token
123, 1e-2    -> number
"..."        -> quoted
[...]        -> parenthesized
...,...,...  -> list
...\n...\n   -> lines

Then, applies structural mutations to inputs.

Versifier example

Original:

`<item name="foo"><prop name="price">100</prop></item>`

Versified (all valid xml):

<item    name="rb54ana"><item  name="foo"><prop name="price"></prop><prop/></item></item>
<item name=""><prop name="price">=</prop><prop/> </item>
<item name=""><prop F="">-026023767521520230564132665e0333302100</prop><prop/></item>
<item SN="foo_P"><prop name="_G_nx">510</prop><prop name="vC">-9e-07036514</prop></item>
<item name="foo"><prop name="c8">prop name="p"</prop>/}<prop name="price">01e-6</prop></item>
<item name="foo"><item name="foo"><prop JY="">100</prop></item>8<prop/></item>

Algorithm

Achievements

• 115 bugs in std lib (66 fixed)
• 43 bugs in golang.org/x/... (24 fixed)
• 134 elsewhere

Achievements

fmt.Sprintf("%.[]")
panic: runtime error: index out of range

regexp.MustCompile("((0(0){0}))").ReplaceAllString("00000", "00$00")
panic: runtime error: slice bounds out of range

ioutil.ReadAll(flate.NewReader(strings.NewReader("4LJNIMK\a\x00\x00\xff..\xff.....\xff")))
runs forever

var x = 1/"."[0]
crashes compiler

archive/tar: hang
archive/zip: cap out of range
encoding/gob: stack overflow
encoding/asn1: index out of range
image/jpeg: Decode hangs
image/png: nil deref
math/big: incorrect string->Float conversion
crypto/x509: division by zero
...

Usage

• go get github.com/dvyukov/go-fuzz/...
• write test:

func Fuzz(data []byte) int {
    gob.NewDecoder(bytes.NewReader(data))
    return 0
}

• build

$ go-fuzz-build github.com/dvyukov/go-fuzz/examples/gob

• collect corpus
• run

$ go-fuzz -bin=gob-fuzz.zip -workdir=examples/gob

Execution tracer

Execution tracer

Gives insight into dynamic execution of a program.

Captures with nanosecond precision:

• goroutine creation/start/end
• goroutine blocking/unblocking
• network blocking
• system calls
• GC events

Execution tracer

Recap

• race detector: always use for testing (-race)
• go-fuzz: parsing of complex inputs (github.com/dvyukov/go-fuzz)
• execution tracer: deep dive into execution (-trace)

Thank you