fuzz.go

Documentation: github.com/google/gofuzz

     1  /*
     2  Copyright 2014 Google Inc. All rights reserved.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package fuzz
    18  
    19  import (
    20  	"fmt"
    21  	"math/rand"
    22  	"reflect"
    23  	"regexp"
    24  	"time"
    25  
    26  	"github.com/google/gofuzz/bytesource"
    27  	"strings"
    28  )
    29  
    30  // fuzzFuncMap is a map from a type to a fuzzFunc that handles that type.
    31  type fuzzFuncMap map[reflect.Type]reflect.Value
    32  
    33  // Fuzzer knows how to fill any object with random fields.
    34  type Fuzzer struct {
    35  	fuzzFuncs         fuzzFuncMap
    36  	defaultFuzzFuncs  fuzzFuncMap
    37  	r                 *rand.Rand
    38  	nilChance         float64
    39  	minElements       int
    40  	maxElements       int
    41  	maxDepth          int
    42  	skipFieldPatterns []*regexp.Regexp
    43  }
    44  
    45  // New returns a new Fuzzer. Customize your Fuzzer further by calling Funcs,
    46  // RandSource, NilChance, or NumElements in any order.
    47  func New() *Fuzzer {
    48  	return NewWithSeed(time.Now().UnixNano())
    49  }
    50  
    51  func NewWithSeed(seed int64) *Fuzzer {
    52  	f := &Fuzzer{
    53  		defaultFuzzFuncs: fuzzFuncMap{
    54  			reflect.TypeOf(&time.Time{}): reflect.ValueOf(fuzzTime),
    55  		},
    56  
    57  		fuzzFuncs:   fuzzFuncMap{},
    58  		r:           rand.New(rand.NewSource(seed)),
    59  		nilChance:   .2,
    60  		minElements: 1,
    61  		maxElements: 10,
    62  		maxDepth:    100,
    63  	}
    64  	return f
    65  }
    66  
    67  // NewFromGoFuzz is a helper function that enables using gofuzz (this
    68  // project) with go-fuzz (https://github.com/dvyukov/go-fuzz) for continuous
    69  // fuzzing. Essentially, it enables translating the fuzzing bytes from
    70  // go-fuzz to any Go object using this library.
    71  //
    72  // This implementation promises a constant translation from a given slice of
    73  // bytes to the fuzzed objects. This promise will remain over future
    74  // versions of Go and of this library.
    75  //
    76  // Note: the returned Fuzzer should not be shared between multiple goroutines,
    77  // as its deterministic output will no longer be available.
    78  //
    79  // Example: use go-fuzz to test the function `MyFunc(int)` in the package
    80  // `mypackage`. Add the file: "mypacakge_fuzz.go" with the content:
    81  //
    82  // // +build gofuzz
    83  // package mypacakge
    84  // import fuzz "github.com/google/gofuzz"
    85  // func Fuzz(data []byte) int {
    86  // 	var i int
    87  // 	fuzz.NewFromGoFuzz(data).Fuzz(&i)
    88  // 	MyFunc(i)
    89  // 	return 0
    90  // }
    91  func NewFromGoFuzz(data []byte) *Fuzzer {
    92  	return New().RandSource(bytesource.New(data))
    93  }
    94  
    95  // Funcs adds each entry in fuzzFuncs as a custom fuzzing function.
    96  //
    97  // Each entry in fuzzFuncs must be a function taking two parameters.
    98  // The first parameter must be a pointer or map. It is the variable that
    99  // function will fill with random data. The second parameter must be a
   100  // fuzz.Continue, which will provide a source of randomness and a way
   101  // to automatically continue fuzzing smaller pieces of the first parameter.
   102  //
   103  // These functions are called sensibly, e.g., if you wanted custom string
   104  // fuzzing, the function `func(s *string, c fuzz.Continue)` would get
   105  // called and passed the address of strings. Maps and pointers will always
   106  // be made/new'd for you, ignoring the NilChange option. For slices, it
   107  // doesn't make much sense to  pre-create them--Fuzzer doesn't know how
   108  // long you want your slice--so take a pointer to a slice, and make it
   109  // yourself. (If you don't want your map/pointer type pre-made, take a
   110  // pointer to it, and make it yourself.) See the examples for a range of
   111  // custom functions.
   112  func (f *Fuzzer) Funcs(fuzzFuncs ...interface{}) *Fuzzer {
   113  	for i := range fuzzFuncs {
   114  		v := reflect.ValueOf(fuzzFuncs[i])
   115  		if v.Kind() != reflect.Func {
   116  			panic("Need only funcs!")
   117  		}
   118  		t := v.Type()
   119  		if t.NumIn() != 2 || t.NumOut() != 0 {
   120  			panic("Need 2 in and 0 out params!")
   121  		}
   122  		argT := t.In(0)
   123  		switch argT.Kind() {
   124  		case reflect.Ptr, reflect.Map:
   125  		default:
   126  			panic("fuzzFunc must take pointer or map type")
   127  		}
   128  		if t.In(1) != reflect.TypeOf(Continue{}) {
   129  			panic("fuzzFunc's second parameter must be type fuzz.Continue")
   130  		}
   131  		f.fuzzFuncs[argT] = v
   132  	}
   133  	return f
   134  }
   135  
   136  // RandSource causes f to get values from the given source of randomness.
   137  // Use if you want deterministic fuzzing.
   138  func (f *Fuzzer) RandSource(s rand.Source) *Fuzzer {
   139  	f.r = rand.New(s)
   140  	return f
   141  }
   142  
   143  // NilChance sets the probability of creating a nil pointer, map, or slice to
   144  // 'p'. 'p' should be between 0 (no nils) and 1 (all nils), inclusive.
   145  func (f *Fuzzer) NilChance(p float64) *Fuzzer {
   146  	if p < 0 || p > 1 {
   147  		panic("p should be between 0 and 1, inclusive.")
   148  	}
   149  	f.nilChance = p
   150  	return f
   151  }
   152  
   153  // NumElements sets the minimum and maximum number of elements that will be
   154  // added to a non-nil map or slice.
   155  func (f *Fuzzer) NumElements(atLeast, atMost int) *Fuzzer {
   156  	if atLeast > atMost {
   157  		panic("atLeast must be <= atMost")
   158  	}
   159  	if atLeast < 0 {
   160  		panic("atLeast must be >= 0")
   161  	}
   162  	f.minElements = atLeast
   163  	f.maxElements = atMost
   164  	return f
   165  }
   166  
   167  func (f *Fuzzer) genElementCount() int {
   168  	if f.minElements == f.maxElements {
   169  		return f.minElements
   170  	}
   171  	return f.minElements + f.r.Intn(f.maxElements-f.minElements+1)
   172  }
   173  
   174  func (f *Fuzzer) genShouldFill() bool {
   175  	return f.r.Float64() >= f.nilChance
   176  }
   177  
   178  // MaxDepth sets the maximum number of recursive fuzz calls that will be made
   179  // before stopping.  This includes struct members, pointers, and map and slice
   180  // elements.
   181  func (f *Fuzzer) MaxDepth(d int) *Fuzzer {
   182  	f.maxDepth = d
   183  	return f
   184  }
   185  
   186  // Skip fields which match the supplied pattern. Call this multiple times if needed
   187  // This is useful to skip XXX_ fields generated by protobuf
   188  func (f *Fuzzer) SkipFieldsWithPattern(pattern *regexp.Regexp) *Fuzzer {
   189  	f.skipFieldPatterns = append(f.skipFieldPatterns, pattern)
   190  	return f
   191  }
   192  
   193  // Fuzz recursively fills all of obj's fields with something random.  First
   194  // this tries to find a custom fuzz function (see Funcs).  If there is no
   195  // custom function this tests whether the object implements fuzz.Interface and,
   196  // if so, calls Fuzz on it to fuzz itself.  If that fails, this will see if
   197  // there is a default fuzz function provided by this package.  If all of that
   198  // fails, this will generate random values for all primitive fields and then
   199  // recurse for all non-primitives.
   200  //
   201  // This is safe for cyclic or tree-like structs, up to a limit.  Use the
   202  // MaxDepth method to adjust how deep you need it to recurse.
   203  //
   204  // obj must be a pointer. Only exported (public) fields can be set (thanks,
   205  // golang :/ ) Intended for tests, so will panic on bad input or unimplemented
   206  // fields.
   207  func (f *Fuzzer) Fuzz(obj interface{}) {
   208  	v := reflect.ValueOf(obj)
   209  	if v.Kind() != reflect.Ptr {
   210  		panic("needed ptr!")
   211  	}
   212  	v = v.Elem()
   213  	f.fuzzWithContext(v, 0)
   214  }
   215  
   216  // FuzzNoCustom is just like Fuzz, except that any custom fuzz function for
   217  // obj's type will not be called and obj will not be tested for fuzz.Interface
   218  // conformance.  This applies only to obj and not other instances of obj's
   219  // type.
   220  // Not safe for cyclic or tree-like structs!
   221  // obj must be a pointer. Only exported (public) fields can be set (thanks, golang :/ )
   222  // Intended for tests, so will panic on bad input or unimplemented fields.
   223  func (f *Fuzzer) FuzzNoCustom(obj interface{}) {
   224  	v := reflect.ValueOf(obj)
   225  	if v.Kind() != reflect.Ptr {
   226  		panic("needed ptr!")
   227  	}
   228  	v = v.Elem()
   229  	f.fuzzWithContext(v, flagNoCustomFuzz)
   230  }
   231  
   232  const (
   233  	// Do not try to find a custom fuzz function.  Does not apply recursively.
   234  	flagNoCustomFuzz uint64 = 1 << iota
   235  )
   236  
   237  func (f *Fuzzer) fuzzWithContext(v reflect.Value, flags uint64) {
   238  	fc := &fuzzerContext{fuzzer: f}
   239  	fc.doFuzz(v, flags)
   240  }
   241  
   242  // fuzzerContext carries context about a single fuzzing run, which lets Fuzzer
   243  // be thread-safe.
   244  type fuzzerContext struct {
   245  	fuzzer   *Fuzzer
   246  	curDepth int
   247  }
   248  
   249  func (fc *fuzzerContext) doFuzz(v reflect.Value, flags uint64) {
   250  	if fc.curDepth >= fc.fuzzer.maxDepth {
   251  		return
   252  	}
   253  	fc.curDepth++
   254  	defer func() { fc.curDepth-- }()
   255  
   256  	if !v.CanSet() {
   257  		return
   258  	}
   259  
   260  	if flags&flagNoCustomFuzz == 0 {
   261  		// Check for both pointer and non-pointer custom functions.
   262  		if v.CanAddr() && fc.tryCustom(v.Addr()) {
   263  			return
   264  		}
   265  		if fc.tryCustom(v) {
   266  			return
   267  		}
   268  	}
   269  
   270  	if fn, ok := fillFuncMap[v.Kind()]; ok {
   271  		fn(v, fc.fuzzer.r)
   272  		return
   273  	}
   274  
   275  	switch v.Kind() {
   276  	case reflect.Map:
   277  		if fc.fuzzer.genShouldFill() {
   278  			v.Set(reflect.MakeMap(v.Type()))
   279  			n := fc.fuzzer.genElementCount()
   280  			for i := 0; i < n; i++ {
   281  				key := reflect.New(v.Type().Key()).Elem()
   282  				fc.doFuzz(key, 0)
   283  				val := reflect.New(v.Type().Elem()).Elem()
   284  				fc.doFuzz(val, 0)
   285  				v.SetMapIndex(key, val)
   286  			}
   287  			return
   288  		}
   289  		v.Set(reflect.Zero(v.Type()))
   290  	case reflect.Ptr:
   291  		if fc.fuzzer.genShouldFill() {
   292  			v.Set(reflect.New(v.Type().Elem()))
   293  			fc.doFuzz(v.Elem(), 0)
   294  			return
   295  		}
   296  		v.Set(reflect.Zero(v.Type()))
   297  	case reflect.Slice:
   298  		if fc.fuzzer.genShouldFill() {
   299  			n := fc.fuzzer.genElementCount()
   300  			v.Set(reflect.MakeSlice(v.Type(), n, n))
   301  			for i := 0; i < n; i++ {
   302  				fc.doFuzz(v.Index(i), 0)
   303  			}
   304  			return
   305  		}
   306  		v.Set(reflect.Zero(v.Type()))
   307  	case reflect.Array:
   308  		if fc.fuzzer.genShouldFill() {
   309  			n := v.Len()
   310  			for i := 0; i < n; i++ {
   311  				fc.doFuzz(v.Index(i), 0)
   312  			}
   313  			return
   314  		}
   315  		v.Set(reflect.Zero(v.Type()))
   316  	case reflect.Struct:
   317  		for i := 0; i < v.NumField(); i++ {
   318  			skipField := false
   319  			fieldName := v.Type().Field(i).Name
   320  			for _, pattern := range fc.fuzzer.skipFieldPatterns {
   321  				if pattern.MatchString(fieldName) {
   322  					skipField = true
   323  					break
   324  				}
   325  			}
   326  			if !skipField {
   327  				fc.doFuzz(v.Field(i), 0)
   328  			}
   329  		}
   330  	case reflect.Chan:
   331  		fallthrough
   332  	case reflect.Func:
   333  		fallthrough
   334  	case reflect.Interface:
   335  		fallthrough
   336  	default:
   337  		panic(fmt.Sprintf("Can't handle %#v", v.Interface()))
   338  	}
   339  }
   340  
   341  // tryCustom searches for custom handlers, and returns true iff it finds a match
   342  // and successfully randomizes v.
   343  func (fc *fuzzerContext) tryCustom(v reflect.Value) bool {
   344  	// First: see if we have a fuzz function for it.
   345  	doCustom, ok := fc.fuzzer.fuzzFuncs[v.Type()]
   346  	if !ok {
   347  		// Second: see if it can fuzz itself.
   348  		if v.CanInterface() {
   349  			intf := v.Interface()
   350  			if fuzzable, ok := intf.(Interface); ok {
   351  				fuzzable.Fuzz(Continue{fc: fc, Rand: fc.fuzzer.r})
   352  				return true
   353  			}
   354  		}
   355  		// Finally: see if there is a default fuzz function.
   356  		doCustom, ok = fc.fuzzer.defaultFuzzFuncs[v.Type()]
   357  		if !ok {
   358  			return false
   359  		}
   360  	}
   361  
   362  	switch v.Kind() {
   363  	case reflect.Ptr:
   364  		if v.IsNil() {
   365  			if !v.CanSet() {
   366  				return false
   367  			}
   368  			v.Set(reflect.New(v.Type().Elem()))
   369  		}
   370  	case reflect.Map:
   371  		if v.IsNil() {
   372  			if !v.CanSet() {
   373  				return false
   374  			}
   375  			v.Set(reflect.MakeMap(v.Type()))
   376  		}
   377  	default:
   378  		return false
   379  	}
   380  
   381  	doCustom.Call([]reflect.Value{v, reflect.ValueOf(Continue{
   382  		fc:   fc,
   383  		Rand: fc.fuzzer.r,
   384  	})})
   385  	return true
   386  }
   387  
   388  // Interface represents an object that knows how to fuzz itself.  Any time we
   389  // find a type that implements this interface we will delegate the act of
   390  // fuzzing itself.
   391  type Interface interface {
   392  	Fuzz(c Continue)
   393  }
   394  
   395  // Continue can be passed to custom fuzzing functions to allow them to use
   396  // the correct source of randomness and to continue fuzzing their members.
   397  type Continue struct {
   398  	fc *fuzzerContext
   399  
   400  	// For convenience, Continue implements rand.Rand via embedding.
   401  	// Use this for generating any randomness if you want your fuzzing
   402  	// to be repeatable for a given seed.
   403  	*rand.Rand
   404  }
   405  
   406  // Fuzz continues fuzzing obj. obj must be a pointer.
   407  func (c Continue) Fuzz(obj interface{}) {
   408  	v := reflect.ValueOf(obj)
   409  	if v.Kind() != reflect.Ptr {
   410  		panic("needed ptr!")
   411  	}
   412  	v = v.Elem()
   413  	c.fc.doFuzz(v, 0)
   414  }
   415  
   416  // FuzzNoCustom continues fuzzing obj, except that any custom fuzz function for
   417  // obj's type will not be called and obj will not be tested for fuzz.Interface
   418  // conformance.  This applies only to obj and not other instances of obj's
   419  // type.
   420  func (c Continue) FuzzNoCustom(obj interface{}) {
   421  	v := reflect.ValueOf(obj)
   422  	if v.Kind() != reflect.Ptr {
   423  		panic("needed ptr!")
   424  	}
   425  	v = v.Elem()
   426  	c.fc.doFuzz(v, flagNoCustomFuzz)
   427  }
   428  
   429  // RandString makes a random string up to 20 characters long. The returned string
   430  // may include a variety of (valid) UTF-8 encodings.
   431  func (c Continue) RandString() string {
   432  	return randString(c.Rand)
   433  }
   434  
   435  // RandUint64 makes random 64 bit numbers.
   436  // Weirdly, rand doesn't have a function that gives you 64 random bits.
   437  func (c Continue) RandUint64() uint64 {
   438  	return randUint64(c.Rand)
   439  }
   440  
   441  // RandBool returns true or false randomly.
   442  func (c Continue) RandBool() bool {
   443  	return randBool(c.Rand)
   444  }
   445  
   446  func fuzzInt(v reflect.Value, r *rand.Rand) {
   447  	v.SetInt(int64(randUint64(r)))
   448  }
   449  
   450  func fuzzUint(v reflect.Value, r *rand.Rand) {
   451  	v.SetUint(randUint64(r))
   452  }
   453  
   454  func fuzzTime(t *time.Time, c Continue) {
   455  	var sec, nsec int64
   456  	// Allow for about 1000 years of random time values, which keeps things
   457  	// like JSON parsing reasonably happy.
   458  	sec = c.Rand.Int63n(1000 * 365 * 24 * 60 * 60)
   459  	c.Fuzz(&nsec)
   460  	*t = time.Unix(sec, nsec)
   461  }
   462  
   463  var fillFuncMap = map[reflect.Kind]func(reflect.Value, *rand.Rand){
   464  	reflect.Bool: func(v reflect.Value, r *rand.Rand) {
   465  		v.SetBool(randBool(r))
   466  	},
   467  	reflect.Int:     fuzzInt,
   468  	reflect.Int8:    fuzzInt,
   469  	reflect.Int16:   fuzzInt,
   470  	reflect.Int32:   fuzzInt,
   471  	reflect.Int64:   fuzzInt,
   472  	reflect.Uint:    fuzzUint,
   473  	reflect.Uint8:   fuzzUint,
   474  	reflect.Uint16:  fuzzUint,
   475  	reflect.Uint32:  fuzzUint,
   476  	reflect.Uint64:  fuzzUint,
   477  	reflect.Uintptr: fuzzUint,
   478  	reflect.Float32: func(v reflect.Value, r *rand.Rand) {
   479  		v.SetFloat(float64(r.Float32()))
   480  	},
   481  	reflect.Float64: func(v reflect.Value, r *rand.Rand) {
   482  		v.SetFloat(r.Float64())
   483  	},
   484  	reflect.Complex64: func(v reflect.Value, r *rand.Rand) {
   485  		v.SetComplex(complex128(complex(r.Float32(), r.Float32())))
   486  	},
   487  	reflect.Complex128: func(v reflect.Value, r *rand.Rand) {
   488  		v.SetComplex(complex(r.Float64(), r.Float64()))
   489  	},
   490  	reflect.String: func(v reflect.Value, r *rand.Rand) {
   491  		v.SetString(randString(r))
   492  	},
   493  	reflect.UnsafePointer: func(v reflect.Value, r *rand.Rand) {
   494  		panic("unimplemented")
   495  	},
   496  }
   497  
   498  // randBool returns true or false randomly.
   499  func randBool(r *rand.Rand) bool {
   500  	return r.Int31()&(1<<30) == 0
   501  }
   502  
   503  type int63nPicker interface {
   504  	Int63n(int64) int64
   505  }
   506  
   507  // UnicodeRange describes a sequential range of unicode characters.
   508  // Last must be numerically greater than First.
   509  type UnicodeRange struct {
   510  	First, Last rune
   511  }
   512  
   513  // UnicodeRanges describes an arbitrary number of sequential ranges of unicode characters.
   514  // To be useful, each range must have at least one character (First <= Last) and
   515  // there must be at least one range.
   516  type UnicodeRanges []UnicodeRange
   517  
   518  // choose returns a random unicode character from the given range, using the
   519  // given randomness source.
   520  func (ur UnicodeRange) choose(r int63nPicker) rune {
   521  	count := int64(ur.Last - ur.First + 1)
   522  	return ur.First + rune(r.Int63n(count))
   523  }
   524  
   525  // CustomStringFuzzFunc constructs a FuzzFunc which produces random strings.
   526  // Each character is selected from the range ur. If there are no characters
   527  // in the range (cr.Last < cr.First), this will panic.
   528  func (ur UnicodeRange) CustomStringFuzzFunc() func(s *string, c Continue) {
   529  	ur.check()
   530  	return func(s *string, c Continue) {
   531  		*s = ur.randString(c.Rand)
   532  	}
   533  }
   534  
   535  // check is a function that used to check whether the first of ur(UnicodeRange)
   536  // is greater than the last one.
   537  func (ur UnicodeRange) check() {
   538  	if ur.Last < ur.First {
   539  		panic("The last encoding must be greater than the first one.")
   540  	}
   541  }
   542  
   543  // randString of UnicodeRange makes a random string up to 20 characters long.
   544  // Each character is selected form ur(UnicodeRange).
   545  func (ur UnicodeRange) randString(r *rand.Rand) string {
   546  	n := r.Intn(20)
   547  	sb := strings.Builder{}
   548  	sb.Grow(n)
   549  	for i := 0; i < n; i++ {
   550  		sb.WriteRune(ur.choose(r))
   551  	}
   552  	return sb.String()
   553  }
   554  
   555  // defaultUnicodeRanges sets a default unicode range when user do not set
   556  // CustomStringFuzzFunc() but wants fuzz string.
   557  var defaultUnicodeRanges = UnicodeRanges{
   558  	{' ', '~'},           // ASCII characters
   559  	{'\u00a0', '\u02af'}, // Multi-byte encoded characters
   560  	{'\u4e00', '\u9fff'}, // Common CJK (even longer encodings)
   561  }
   562  
   563  // CustomStringFuzzFunc constructs a FuzzFunc which produces random strings.
   564  // Each character is selected from one of the ranges of ur(UnicodeRanges).
   565  // Each range has an equal probability of being chosen. If there are no ranges,
   566  // or a selected range has no characters (.Last < .First), this will panic.
   567  // Do not modify any of the ranges in ur after calling this function.
   568  func (ur UnicodeRanges) CustomStringFuzzFunc() func(s *string, c Continue) {
   569  	// Check unicode ranges slice is empty.
   570  	if len(ur) == 0 {
   571  		panic("UnicodeRanges is empty.")
   572  	}
   573  	// if not empty, each range should be checked.
   574  	for i := range ur {
   575  		ur[i].check()
   576  	}
   577  	return func(s *string, c Continue) {
   578  		*s = ur.randString(c.Rand)
   579  	}
   580  }
   581  
   582  // randString of UnicodeRanges makes a random string up to 20 characters long.
   583  // Each character is selected form one of the ranges of ur(UnicodeRanges),
   584  // and each range has an equal probability of being chosen.
   585  func (ur UnicodeRanges) randString(r *rand.Rand) string {
   586  	n := r.Intn(20)
   587  	sb := strings.Builder{}
   588  	sb.Grow(n)
   589  	for i := 0; i < n; i++ {
   590  		sb.WriteRune(ur[r.Intn(len(ur))].choose(r))
   591  	}
   592  	return sb.String()
   593  }
   594  
   595  // randString makes a random string up to 20 characters long. The returned string
   596  // may include a variety of (valid) UTF-8 encodings.
   597  func randString(r *rand.Rand) string {
   598  	return defaultUnicodeRanges.randString(r)
   599  }
   600  
   601  // randUint64 makes random 64 bit numbers.
   602  // Weirdly, rand doesn't have a function that gives you 64 random bits.
   603  func randUint64(r *rand.Rand) uint64 {
   604  	return uint64(r.Uint32())<<32 | uint64(r.Uint32())
   605  }
   606
View as plain text