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