blob: 8d39afdcde4818551d38775612a334163dde3e85 [file] [log] [blame]
Go Dynamic Tools
Gophercon 2015, July 9, 2015
Dmitry Vyukov
Google
dvyukov@
* Video
A video of this talk was recorded at GopherCon in Denver.
.link https://www.youtube.com/watch?v=a9xrxRsIbSU 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
.image dynamic-tools/philosoraptor.png
* 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
.image dynamic-tools/go-fuzz.png
* 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
.image dynamic-tools/algo.png
* 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
.image dynamic-tools/tracer.png
* 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
.image dynamic-tools/trace.png 450 _
* 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)