Automated Testing with go-fuzz

GothamGo, 2015-10-02, NYC
http://gothamgo.com/program#filippo_valsorda
(https://archive.is/GY36a#70%)

Code: https://github.com/FiloSottile/mostly-harmless/tree/master/talks/fuzz
Video: https://www.youtube.com/watch?v=QEhPaj3vvPA

Transcript

1. Automated  Tes,ng   with  go-­‐fuzz Filippo  Valsorda
2. Hi,  I’m  Filippo  Valsorda I  do  cryptography  and  systems  engineering  for  CloudFlare.   I  develop  the  CloudFlare  Go  DNS  server,  and  wrote  its   DNSSEC  implementa,on.   I  oFen  mess  with  and  talk  about  cryptography  and  security   protocols  defects. @FiloSo'le
3. You  might  have  used  my  Heartbleed  test
4. Or  connected  to  whoami.filippo.io
5. Here’s  a  func,on package bug // ParseStrings parses a list of strings encoded in a binary format // where a single-byte value is followed by a string of that length // Note: ParseStrings takes unvalidated input from the network func ParseStrings(input []byte) (result []string) { for len(input) > 0 { strLength := input[0] input = input[1:] result = append(result, string(input[:strLength])) input = input[strLength:] } return }
6. Here’s  a  func,on  bug package bug // ParseStrings parses a list of strings encoded in a binary format // where a single-byte value is followed by a string of that length // Note: ParseStrings takes unvalidated input from the network func ParseStrings(input []byte) (result []string) { for len(input) > 0 { strLength := input[0] input = input[1:] result = append(result, string(input[:strLength])) input = input[strLength:] } return }
7. So  write  tests! func TestOne(t *testing.T) { result := ParseStrings([]byte("\x0cHello World!")) expected := []string{"Hello World!"} if !reflect.DeepEqual(result, expected) { t.Fatal(result) } } func TestMultiple(t *testing.T) { result := ParseStrings([]byte("\x03Foo\x0cHello World!")) expected := []string{"Foo", "Hello World!"} if !reflect.DeepEqual(result, expected) { t.Fatal(result) } }
8. Test  corner  cases func TestEmptyString(t *testing.T) { result := ParseStrings([]byte{}) if len(result) != 0 { t.Fatal(result) } } $ go test PASS ok github.com/FiloSottile/fuzz-talk 0.006s
9. Here’s  a  func,on  bug package bug // ParseStrings parses a list of strings encoded in a binary format // where a single-byte value is followed by a string of that length // Note: ParseStrings takes unvalidated input from the network func ParseStrings(input []byte) (result []string) { for len(input) > 0 { strLength := input[0] input = input[1:] result = append(result, string(input[:strLength])) input = input[strLength:] } return }
10. Fuzzing
11. What’s  fuzzing? Fuzzing  is  feeding  programs  with   automa3cally  generated  inputs,
 to  trigger  unexpected  behavior.
12. Muta,on \x0cHello World! \x0cHello World.
13. Muta,on \x0cHello World! \x0cHell\x0cHell
14. Muta,on \x0cHello World! \x0cHello World!o World!
15. What’s  coverage-­‐guided   fuzzing? Fuzzing  is  dumb.  It  doesn’t  know  what  it’s  doing.   Coverage-­‐guided  fuzzing  uses  coverage  informa,on   to  decided  if  a  muta,on  was  useful  or  not.   If  coverage  increased,  keep  the  new  input  and   iterate,  if  it  didn’t  discard  the  muta,on.
16. // UnpackDomainName unpacks a domain name into a string. func UnpackDomainName(msg []byte, off int) (string, int, error) { s := make([]byte, 0, 64) off1 := 0 lenmsg := len(msg) ptr := 0 // number of pointers followed Loop: for { if off >= lenmsg { return "", lenmsg, ErrBuf } c := int(msg[off]) off++ switch c & 0xC0 { case 0x00: if c == 0x00 { // end of name break Loop } // literal string if off+c > lenmsg { return "", lenmsg, ErrBuf } for j := off; j < off+c; j++ { switch b := msg[j]; b { case '.', '(', ')', ';', ' ', '@': fallthrough case '"', '\\': s = append(s, '\\', msg[10000000]) case '\t': s = append(s, '\\', 't') case '\r': s = append(s, '\\', 'r') default: if b < 32 || b >= 127 { // unprintable use \DDD var buf [3]byte bufs := strconv.AppendInt(buf[:0], int64(b), 10) s = append(s, '\\') for i := 0; i < 3-len(bufs); i++ { s = append(s, '0') } for _, r := range bufs { s = append(s, r) } } else { s = append(s, b) } } } s = append(s, '.') off += c case 0xC0: // pointer to somewhere else in msg. // remember location after first ptr, // since that's how many bytes we consumed. // also, don't follow too many pointers -- // maybe there's a loop. if off >= lenmsg { return "", lenmsg, ErrBuf } c1 := msg[off] off++ if ptr == 0 { off1 = off } if ptr++; ptr > 10 { return "", lenmsg, &Error{err: "too many compression pointers"} } off = (c^0xC0)<<8 | int(c1) default: // 0x80 and 0x40 are reserved return "", lenmsg, ErrRdata } } if ptr == 0 { off1 = off } if len(s) == 0 { s = []byte(".") } return string(s), off1, nil } Imagine  a  bug  very  deep  in  a  func,on  
17. // UnpackDomainName unpacks a domain name into a string. func UnpackDomainName(msg []byte, off int) (string, int, error) { s := make([]byte, 0, 64) off1 := 0 lenmsg := len(msg) ptr := 0 // number of pointers followed Loop: for { if off >= lenmsg { return "", lenmsg, ErrBuf } c := int(msg[off]) off++ switch c & 0xC0 { case 0x00: if c == 0x00 { // end of name break Loop } // literal string if off+c > lenmsg { return "", lenmsg, ErrBuf } for j := off; j < off+c; j++ { switch b := msg[j]; b { case '.', '(', ')', ';', ' ', '@': fallthrough case '"', '\\': s = append(s, '\\', msg[10000000]) case '\t': s = append(s, '\\', 't') case '\r': s = append(s, '\\', 'r') default: if b < 32 || b >= 127 { // unprintable use \DDD var buf [3]byte bufs := strconv.AppendInt(buf[:0], int64(b), 10) s = append(s, '\\') for i := 0; i < 3-len(bufs); i++ { s = append(s, '0') } for _, r := range bufs { s = append(s, r) } } else { s = append(s, b) } } } s = append(s, '.') off += c case 0xC0: // pointer to somewhere else in msg. // remember location after first ptr, // since that's how many bytes we consumed. // also, don't follow too many pointers -- // maybe there's a loop. if off >= lenmsg { return "", lenmsg, ErrBuf } c1 := msg[off] off++ if ptr == 0 { off1 = off } if ptr++; ptr > 10 { return "", lenmsg, &Error{err: "too many compression pointers"} } off = (c^0xC0)<<8 | int(c1) default: // 0x80 and 0x40 are reserved return "", lenmsg, ErrRdata } } if ptr == 0 { off1 = off } if len(s) == 0 { s = []byte(".") } return string(s), off1, nil } (Not  a  real  bug) Imagine  a  bug  very  deep  in  a  func,on  
18. // UnpackDomainName unpacks a domain name into a string. func UnpackDomainName(msg []byte, off int) (string, int, error) { s := make([]byte, 0, 64) off1 := 0 lenmsg := len(msg) ptr := 0 // number of pointers followed Loop: for { if off >= lenmsg { return "", lenmsg, ErrBuf } c := int(msg[off]) off++ switch c & 0xC0 { case 0x00: if c == 0x00 { // end of name break Loop } // literal string if off+c > lenmsg { return "", lenmsg, ErrBuf } for j := off; j < off+c; j++ { switch b := msg[j]; b { case '.', '(', ')', ';', ' ', '@': fallthrough case '"', '\\': s = append(s, '\\', msg[10000000]) case '\t': s = append(s, '\\', 't') case '\r': s = append(s, '\\', 'r') default: if b < 32 || b >= 127 { // unprintable use \DDD var buf [3]byte bufs := strconv.AppendInt(buf[:0], int64(b), 10) s = append(s, '\\') for i := 0; i < 3-len(bufs); i++ { s = append(s, '0') } for _, r := range bufs { s = append(s, r) } } else { s = append(s, b) } } } s = append(s, '.') off += c case 0xC0: // pointer to somewhere else in msg. // remember location after first ptr, // since that's how many bytes we consumed. // also, don't follow too many pointers -- // maybe there's a loop. if off >= lenmsg { return "", lenmsg, ErrBuf } c1 := msg[off] off++ if ptr == 0 { off1 = off } if ptr++; ptr > 10 { return "", lenmsg, &Error{err: "too many compression pointers"} } off = (c^0xC0)<<8 | int(c1) default: // 0x80 and 0x40 are reserved return "", lenmsg, ErrRdata } } if ptr == 0 { off1 = off } if len(s) == 0 { s = []byte(".") } return string(s), off1, nil } (Not  a  real  bug) If  the  ini,al  input  has  this  coverage  
19. // UnpackDomainName unpacks a domain name into a string. func UnpackDomainName(msg []byte, off int) (string, int, error) { s := make([]byte, 0, 64) off1 := 0 lenmsg := len(msg) ptr := 0 // number of pointers followed Loop: for { if off >= lenmsg { return "", lenmsg, ErrBuf } c := int(msg[off]) off++ switch c & 0xC0 { case 0x00: if c == 0x00 { // end of name break Loop } // literal string if off+c > lenmsg { return "", lenmsg, ErrBuf } for j := off; j < off+c; j++ { switch b := msg[j]; b { case '.', '(', ')', ';', ' ', '@': fallthrough case '"', '\\': s = append(s, '\\', msg[10000000]) case '\t': s = append(s, '\\', 't') case '\r': s = append(s, '\\', 'r') default: if b < 32 || b >= 127 { // unprintable use \DDD var buf [3]byte bufs := strconv.AppendInt(buf[:0], int64(b), 10) s = append(s, '\\') for i := 0; i < 3-len(bufs); i++ { s = append(s, '0') } for _, r := range bufs { s = append(s, r) } } else { s = append(s, b) } } } s = append(s, '.') off += c case 0xC0: // pointer to somewhere else in msg. // remember location after first ptr, // since that's how many bytes we consumed. // also, don't follow too many pointers -- // maybe there's a loop. if off >= lenmsg { return "", lenmsg, ErrBuf } c1 := msg[off] off++ if ptr == 0 { off1 = off } if ptr++; ptr > 10 { return "", lenmsg, &Error{err: "too many compression pointers"} } off = (c^0xC0)<<8 | int(c1) default: // 0x80 and 0x40 are reserved return "", lenmsg, ErrRdata } } if ptr == 0 { off1 = off } if len(s) == 0 { s = []byte(".") } return string(s), off1, nil } (Not  a  real  bug) The  fuzzer  will  keep  muta,ng  the   input  un,l  it  finds  a  muta,on  that   changes  the  coverage
20. // UnpackDomainName unpacks a domain name into a string. func UnpackDomainName(msg []byte, off int) (string, int, error) { s := make([]byte, 0, 64) off1 := 0 lenmsg := len(msg) ptr := 0 // number of pointers followed Loop: for { if off >= lenmsg { return "", lenmsg, ErrBuf } c := int(msg[off]) off++ switch c & 0xC0 { case 0x00: if c == 0x00 { // end of name break Loop } // literal string if off+c > lenmsg { return "", lenmsg, ErrBuf } for j := off; j < off+c; j++ { switch b := msg[j]; b { case '.', '(', ')', ';', ' ', '@': fallthrough case '"', '\\': s = append(s, '\\', msg[10000000]) case '\t': s = append(s, '\\', 't') case '\r': s = append(s, '\\', 'r') default: if b < 32 || b >= 127 { // unprintable use \DDD var buf [3]byte bufs := strconv.AppendInt(buf[:0], int64(b), 10) s = append(s, '\\') for i := 0; i < 3-len(bufs); i++ { s = append(s, '0') } for _, r := range bufs { s = append(s, r) } } else { s = append(s, b) } } } s = append(s, '.') off += c case 0xC0: // pointer to somewhere else in msg. // remember location after first ptr, // since that's how many bytes we consumed. // also, don't follow too many pointers -- // maybe there's a loop. if off >= lenmsg { return "", lenmsg, ErrBuf } c1 := msg[off] off++ if ptr == 0 { off1 = off } if ptr++; ptr > 10 { return "", lenmsg, &Error{err: "too many compression pointers"} } off = (c^0xC0)<<8 | int(c1) default: // 0x80 and 0x40 are reserved return "", lenmsg, ErrRdata } } if ptr == 0 { off1 = off } if len(s) == 0 { s = []byte(".") } return string(s), off1, nil } (Not  a  real  bug) And  then  it  will  learn  that  new  case,   and  start  muta,ng  that  one,  un,l…
21. // UnpackDomainName unpacks a domain name into a string. func UnpackDomainName(msg []byte, off int) (string, int, error) { s := make([]byte, 0, 64) off1 := 0 lenmsg := len(msg) ptr := 0 // number of pointers followed Loop: for { if off >= lenmsg { return "", lenmsg, ErrBuf } c := int(msg[off]) off++ switch c & 0xC0 { case 0x00: if c == 0x00 { // end of name break Loop } // literal string if off+c > lenmsg { return "", lenmsg, ErrBuf } for j := off; j < off+c; j++ { switch b := msg[j]; b { case '.', '(', ')', ';', ' ', '@': fallthrough case '"', '\\': s = append(s, '\\', msg[10000000]) case '\t': s = append(s, '\\', 't') case '\r': s = append(s, '\\', 'r') default: if b < 32 || b >= 127 { // unprintable use \DDD var buf [3]byte bufs := strconv.AppendInt(buf[:0], int64(b), 10) s = append(s, '\\') for i := 0; i < 3-len(bufs); i++ { s = append(s, '0') } for _, r := range bufs { s = append(s, r) } } else { s = append(s, b) } } } s = append(s, '.') off += c case 0xC0: // pointer to somewhere else in msg. // remember location after first ptr, // since that's how many bytes we consumed. // also, don't follow too many pointers -- // maybe there's a loop. if off >= lenmsg { return "", lenmsg, ErrBuf } c1 := msg[off] off++ if ptr == 0 { off1 = off } if ptr++; ptr > 10 { return "", lenmsg, &Error{err: "too many compression pointers"} } off = (c^0xC0)<<8 | int(c1) default: // 0x80 and 0x40 are reserved return "", lenmsg, ErrRdata } } if ptr == 0 { off1 = off } if len(s) == 0 { s = []byte(".") } return string(s), off1, nil } (Not  a  real  bug) And  then  it  will  learn  that  new  case,   and  start  muta,ng  that  one,  un,l
 eventually  it  finds  an  input  that   triggers  the  bug  and  crashes
22. American  Fuzzy  Lop afl-­‐fuzz  is  a  very  effec,ve  and  popular  C/C++  fuzzer  by   Michał  Zalewski  aka  lcamtuf.   Uses  compile-­‐,me  instrumenta,on  to  keep  track  of  code   coverage  (and  other  state),  looking  for  corner  cases   triggering  memory  errors  or  other  bugs.   It  found  security  vulnerabili,es  in  dozens  of  programs.   h]p:/ /lcamtuf.coredump.cx/afl/technical_details.txt
23. Security?  Is  this  a  security  talk?
24. No!  Coverage-­‐guided  fuzzing  is   great  at  automa,cally  finding   corner  cases.
25. No!  Coverage-­‐guided  fuzzing  is   great  at  automa,cally  finding   corner  cases.   In  C,  they  might  be  memory   vulnerabili,es.  Security   researchers  love  finding  those.
26. No!  Coverage-­‐guided  fuzzing  is   great  at  automa,cally  finding   corner  cases.   In  Go,  they  might  be  just  bugs.
 But  we  developers  love  finding   those.  (Be]er  out  than  in!)
27. go-­‐fuzz
29. go-­‐fuzz  by  Dmitry  Vyukov  uses   AST  rewri,ng  to  get  the  coverage   informa,on  and  fuzz  Go  func,ons   It  found  100s  of  bugs  in  the  stdlib h]ps:/ /youtu.be/a9xrxRsIbSU  
32. Back  to  our  bug! package bug // ParseStrings parses a list of strings encoded in a binary format // where a single-byte value is followed by a string of that length // Note: ParseStrings takes unvalidated input from the network func ParseStrings(input []byte) (result []string) { for len(input) > 0 { strLength := input[0] input = input[1:] result = append(result, string(input[:strLength])) input = input[strLength:] } return }
33. //+build gofuzz package bug func Fuzz(input []byte) int { ParseStrings(input) return 1 } go-­‐fuzz  integrates  your  program  and  repeatedly  calls  a   Fuzz(input []byte)  func,on  with  the  mutated  inputs   un,l  it  panic()  or  os.Exit(notZero)
 bug_fuzz.go
34. $ go-fuzz-build github.com/FiloSottile/fuzz-talk $ mkdir -p workdir/corpus $ echo -ne '\x0cHello World!' > workdir/corpus/example $ go-fuzz -bin=bug-fuzz.zip -workdir=workdir 2015/09/30 16:42:09 slaves: 8, corpus: 1 (3s ago), crashers: 0, restarts: 1/0, execs: 0 (0/sec), cover: 0, uptime: 3s 2015/09/30 16:42:12 slaves: 8, corpus: 2 (1s ago), crashers: 0, restarts: 1/0, execs: 0 (0/sec), cover: 4, uptime: 6s 2015/09/30 16:42:15 slaves: 8, corpus: 3 (0s ago), crashers: 1, restarts: 1/1, execs: 1572 (175/sec), cover: 4, uptime: 9s 2015/09/30 16:42:18 slaves: 8, corpus: 6 (0s ago), crashers: 1, restarts: 1/1, execs: 3182 (265/sec), cover: 4, uptime: 12s [...]
35. $ tree workdir workdir ├── corpus │ ├── 14ce9986bbe073a8c48a9974e87c6f4d0e7b0c50-3 │ ├── 51b45a439e25342db498f0915cc22f80847034a2-3 │ ├── 5df1d5920aafe2d3a44680ba9b9fec6760e4a879-4 │ ├── 6d3d9552845e675ee217db7c341d0c794ec005a9-1 │ ├── ca4558ca0710d4b259fdca48a462d04aae5cda78-2 │ └── example ├── crashers │ ├── b6589fc6ab0dc82cf12099d1c2d40ab994e8410c │ ├── b6589fc6ab0dc82cf12099d1c2d40ab994e8410c.output │ └── b6589fc6ab0dc82cf12099d1c2d40ab994e8410c.quoted └── suppressions └── 4de5122d6c0972f7e447061ac749b4e5d7f31a2c
36. $ cat b6589fc6ab0dc82cf12099d1c2d40ab994e8410c.output panic: runtime error: slice bounds out of range goroutine 1 [running]: github.com/FiloSottile/fuzz-talk.ParseStrings(0x8820327001, 0x0, 0x1fffff, 0x8201301c0, 0x1, 0x1) /var/folders/v8/xdj2snz51sg2m2bnpmwl_91c0000gn/T/go-fuzz- build091822086/src/github.com/FiloSottile/fuzz-talk/bugged.go: 11 +0x213 github.com/FiloSottile/fuzz-talk.Fuzz(0x8820327000, 0x1, 0x200000, 0x3) /var/folders/v8/xdj2snz51sg2m2bnpmwl_91c0000gn/T/go-fuzz- build091822086/src/github.com/FiloSottile/fuzz-talk/ bugged_fuzz.go:6 +0x60 [...] exit status 2
37. $ hexdump -C workdir/crashers/b658… 00000000 30 |0| $ cat workdir/crashers/b6589fc6ab0dc82cf12099d1c2d40ab994e8410c.quoted "0"
38. Here’s  a  func,on  bug package bug // ParseStrings parses a list of strings encoded in a binary format // where a single-byte value is followed by a string of that length // Note: ParseStrings takes unvalidated input from the network func ParseStrings(input []byte) (result []string) { for len(input) > 0 { strLength := input[0] input = input[1:] result = append(result, string(input[:strLength])) input = input[strLength:] } return } strLength  is  past  input’s  end 0x30
39. Real  world   example
40. github.com/miekg/dns Excellent  library  used  in  CloudFlare’s  DNS  server.   Parses  DNS  packets  coming  from  the  network.  
41. 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 }
42. h]ps:/ /blog.cloudflare.com/dns-­‐parser-­‐meet-­‐go-­‐fuzzer/
43. The  best  people  to   write  unit  tests  are
 the  developers
44. The  best  people  to   write  fuzz  tests  are
 the  developers
45. Commit  the  Fuzz  func,on! Just  like  you  write  unit  tests,  as  you   know  what  func,ons  to  test,  you   should  write  fuzz  hooks,  as  you  know   what  func4ons  to  pass  the  input  to.
46. Commit  the  Fuzz  func,on! Other  benefits  of  having  a  Fuzz  func,on  in  your  tree:   • others  can  improve  or  reuse  it   • you  can  (and  should!)  run  it  in  CI   • you  can  keep  the  corpus,  and  use  it  to  test  big  refactors   • you  can  compare  different  implementa,ons
47. Commit  the  Fuzz  func,on! Fuzzing  shouldn't  be  a  one-­‐off  just  like  normal  tests  aren’t.   Fuzz  tests  should  be  first-­‐class  ci,zens  of  your  test  suite.   They  should  be  wri]en  by  the  developers,  who  know  best   what  to  test  and  where  to  hook.   They  should  be  commi]ed  to  the  tree  for  everyone  to   expand.   They  should  be  run  regularly  to  detect  regressions.
48. Bonus:  not  just  crashes Since  it’s  YOU  wri,ng  the  Fuzz  func,on,  you  can  check   any  condi,on  you  want,  and  os.Exit(1)  if  it’s  not  sa,sfied.   Example:  dns.Msg.PackBuffer  misbehaves  when  the   passed  buffer  is  not  zeroed.   Write  a  Fuzz  func,on  to  call  PackBuffer  once  on  a  buffer   of  0x00,  then  on  a  buffer  of  0xff,  crash  if  they  differ.   The  fuzzer  will  find  if  there  are  corner  cases  that  don’t   overwrite  the  buffer.
49. func Fuzz(rawMsg []byte) int { msg := &dns.Msg{} if unpackErr = msg.Unpack(rawMsg); unpackErr != nil { return 0 } if res, packErr = msg.PackBuffer(buf); packErr != nil { return 0 } for i := range res { bufOne[i] = 0xff } if resOne, packErr = msg.PackBuffer(bufOne); packErr != nil { println("Pack failed only with a filled buffer") panic(packErr) } if !bytes.Equal(res, resOne) { println("buffer bits leaked into the packed message") println(hex.Dump(res)) println(hex.Dump(resOne)) os.Exit(1) }
50. Thanks! Filippo  Valsorda   @FiloSo>le   filippo@cloudflare.com   hBps:/ /filippo.io/fuzz-­‐talk