Source file src/internal/fuzz/fuzz.go

     1  // Copyright 2020 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package fuzz provides common fuzzing functionality for tests built with
     6  // "go test" and for programs that use fuzzing functionality in the testing
     7  // package.
     8  package fuzz
     9  
    10  import (
    11  	"context"
    12  	"crypto/sha256"
    13  	"errors"
    14  	"fmt"
    15  	"internal/godebug"
    16  	"io"
    17  	"io/ioutil"
    18  	"math/bits"
    19  	"os"
    20  	"path/filepath"
    21  	"reflect"
    22  	"runtime"
    23  	"strings"
    24  	"sync"
    25  	"time"
    26  )
    27  
    28  // CoordinateFuzzingOpts is a set of arguments for CoordinateFuzzing.
    29  // The zero value is valid for each field unless specified otherwise.
    30  type CoordinateFuzzingOpts struct {
    31  	// Log is a writer for logging progress messages and warnings.
    32  	// If nil, io.Discard will be used instead.
    33  	Log io.Writer
    34  
    35  	// Timeout is the amount of wall clock time to spend fuzzing after the corpus
    36  	// has loaded. If zero, there will be no time limit.
    37  	Timeout time.Duration
    38  
    39  	// Limit is the number of random values to generate and test. If zero,
    40  	// there will be no limit on the number of generated values.
    41  	Limit int64
    42  
    43  	// MinimizeTimeout is the amount of wall clock time to spend minimizing
    44  	// after discovering a crasher. If zero, there will be no time limit. If
    45  	// MinimizeTimeout and MinimizeLimit are both zero, then minimization will
    46  	// be disabled.
    47  	MinimizeTimeout time.Duration
    48  
    49  	// MinimizeLimit is the maximum number of calls to the fuzz function to be
    50  	// made while minimizing after finding a crash. If zero, there will be no
    51  	// limit. Calls to the fuzz function made when minimizing also count toward
    52  	// Limit. If MinimizeTimeout and MinimizeLimit are both zero, then
    53  	// minimization will be disabled.
    54  	MinimizeLimit int64
    55  
    56  	// parallel is the number of worker processes to run in parallel. If zero,
    57  	// CoordinateFuzzing will run GOMAXPROCS workers.
    58  	Parallel int
    59  
    60  	// Seed is a list of seed values added by the fuzz target with testing.F.Add
    61  	// and in testdata.
    62  	Seed []CorpusEntry
    63  
    64  	// Types is the list of types which make up a corpus entry.
    65  	// Types must be set and must match values in Seed.
    66  	Types []reflect.Type
    67  
    68  	// CorpusDir is a directory where files containing values that crash the
    69  	// code being tested may be written. CorpusDir must be set.
    70  	CorpusDir string
    71  
    72  	// CacheDir is a directory containing additional "interesting" values.
    73  	// The fuzzer may derive new values from these, and may write new values here.
    74  	CacheDir string
    75  }
    76  
    77  // CoordinateFuzzing creates several worker processes and communicates with
    78  // them to test random inputs that could trigger crashes and expose bugs.
    79  // The worker processes run the same binary in the same directory with the
    80  // same environment variables as the coordinator process. Workers also run
    81  // with the same arguments as the coordinator, except with the -test.fuzzworker
    82  // flag prepended to the argument list.
    83  //
    84  // If a crash occurs, the function will return an error containing information
    85  // about the crash, which can be reported to the user.
    86  func CoordinateFuzzing(ctx context.Context, opts CoordinateFuzzingOpts) (err error) {
    87  	if err := ctx.Err(); err != nil {
    88  		return err
    89  	}
    90  	if opts.Log == nil {
    91  		opts.Log = io.Discard
    92  	}
    93  	if opts.Parallel == 0 {
    94  		opts.Parallel = runtime.GOMAXPROCS(0)
    95  	}
    96  	if opts.Limit > 0 && int64(opts.Parallel) > opts.Limit {
    97  		// Don't start more workers than we need.
    98  		opts.Parallel = int(opts.Limit)
    99  	}
   100  
   101  	c, err := newCoordinator(opts)
   102  	if err != nil {
   103  		return err
   104  	}
   105  
   106  	if opts.Timeout > 0 {
   107  		var cancel func()
   108  		ctx, cancel = context.WithTimeout(ctx, opts.Timeout)
   109  		defer cancel()
   110  	}
   111  
   112  	// fuzzCtx is used to stop workers, for example, after finding a crasher.
   113  	fuzzCtx, cancelWorkers := context.WithCancel(ctx)
   114  	defer cancelWorkers()
   115  	doneC := ctx.Done()
   116  
   117  	// stop is called when a worker encounters a fatal error.
   118  	var fuzzErr error
   119  	stopping := false
   120  	stop := func(err error) {
   121  		if err == fuzzCtx.Err() || isInterruptError(err) {
   122  			// Suppress cancellation errors and terminations due to SIGINT.
   123  			// The messages are not helpful since either the user triggered the error
   124  			// (with ^C) or another more helpful message will be printed (a crasher).
   125  			err = nil
   126  		}
   127  		if err != nil && (fuzzErr == nil || fuzzErr == ctx.Err()) {
   128  			fuzzErr = err
   129  		}
   130  		if stopping {
   131  			return
   132  		}
   133  		stopping = true
   134  		cancelWorkers()
   135  		doneC = nil
   136  	}
   137  
   138  	// Ensure that any crash we find is written to the corpus, even if an error
   139  	// or interruption occurs while minimizing it.
   140  	crashWritten := false
   141  	defer func() {
   142  		if c.crashMinimizing == nil || crashWritten {
   143  			return
   144  		}
   145  		werr := writeToCorpus(&c.crashMinimizing.entry, opts.CorpusDir)
   146  		if werr != nil {
   147  			err = fmt.Errorf("%w\n%v", err, werr)
   148  			return
   149  		}
   150  		if err == nil {
   151  			err = &crashError{
   152  				path: c.crashMinimizing.entry.Path,
   153  				err:  errors.New(c.crashMinimizing.crasherMsg),
   154  			}
   155  		}
   156  	}()
   157  
   158  	// Start workers.
   159  	// TODO(jayconrod): do we want to support fuzzing different binaries?
   160  	dir := "" // same as self
   161  	binPath := os.Args[0]
   162  	args := append([]string{"-test.fuzzworker"}, os.Args[1:]...)
   163  	env := os.Environ() // same as self
   164  
   165  	errC := make(chan error)
   166  	workers := make([]*worker, opts.Parallel)
   167  	for i := range workers {
   168  		var err error
   169  		workers[i], err = newWorker(c, dir, binPath, args, env)
   170  		if err != nil {
   171  			return err
   172  		}
   173  	}
   174  	for i := range workers {
   175  		w := workers[i]
   176  		go func() {
   177  			err := w.coordinate(fuzzCtx)
   178  			if fuzzCtx.Err() != nil || isInterruptError(err) {
   179  				err = nil
   180  			}
   181  			cleanErr := w.cleanup()
   182  			if err == nil {
   183  				err = cleanErr
   184  			}
   185  			errC <- err
   186  		}()
   187  	}
   188  
   189  	// Main event loop.
   190  	// Do not return until all workers have terminated. We avoid a deadlock by
   191  	// receiving messages from workers even after ctx is cancelled.
   192  	activeWorkers := len(workers)
   193  	statTicker := time.NewTicker(3 * time.Second)
   194  	defer statTicker.Stop()
   195  	defer c.logStats()
   196  
   197  	c.logStats()
   198  	for {
   199  		var inputC chan fuzzInput
   200  		input, ok := c.peekInput()
   201  		if ok && c.crashMinimizing == nil && !stopping {
   202  			inputC = c.inputC
   203  		}
   204  
   205  		var minimizeC chan fuzzMinimizeInput
   206  		minimizeInput, ok := c.peekMinimizeInput()
   207  		if ok && !stopping {
   208  			minimizeC = c.minimizeC
   209  		}
   210  
   211  		select {
   212  		case <-doneC:
   213  			// Interrupted, cancelled, or timed out.
   214  			// stop sets doneC to nil so we don't busy wait here.
   215  			stop(ctx.Err())
   216  
   217  		case err := <-errC:
   218  			// A worker terminated, possibly after encountering a fatal error.
   219  			stop(err)
   220  			activeWorkers--
   221  			if activeWorkers == 0 {
   222  				return fuzzErr
   223  			}
   224  
   225  		case result := <-c.resultC:
   226  			// Received response from worker.
   227  			if stopping {
   228  				break
   229  			}
   230  			c.updateStats(result)
   231  
   232  			if result.crasherMsg != "" {
   233  				if c.warmupRun() && result.entry.IsSeed {
   234  					target := filepath.Base(c.opts.CorpusDir)
   235  					fmt.Fprintf(c.opts.Log, "failure while testing seed corpus entry: %s/%s\n", target, testName(result.entry.Parent))
   236  					stop(errors.New(result.crasherMsg))
   237  					break
   238  				}
   239  				if c.canMinimize() && result.canMinimize {
   240  					if c.crashMinimizing != nil {
   241  						// This crash is not minimized, and another crash is being minimized.
   242  						// Ignore this one and wait for the other one to finish.
   243  						break
   244  					}
   245  					// Found a crasher but haven't yet attempted to minimize it.
   246  					// Send it back to a worker for minimization. Disable inputC so
   247  					// other workers don't continue fuzzing.
   248  					c.crashMinimizing = &result
   249  					fmt.Fprintf(c.opts.Log, "fuzz: minimizing %d-byte failing input file\n", len(result.entry.Data))
   250  					c.queueForMinimization(result, nil)
   251  				} else if !crashWritten {
   252  					// Found a crasher that's either minimized or not minimizable.
   253  					// Write to corpus and stop.
   254  					err := writeToCorpus(&result.entry, opts.CorpusDir)
   255  					if err == nil {
   256  						crashWritten = true
   257  						err = &crashError{
   258  							path: result.entry.Path,
   259  							err:  errors.New(result.crasherMsg),
   260  						}
   261  					}
   262  					if shouldPrintDebugInfo() {
   263  						fmt.Fprintf(
   264  							c.opts.Log,
   265  							"DEBUG new crasher, elapsed: %s, id: %s, parent: %s, gen: %d, size: %d, exec time: %s\n",
   266  							c.elapsed(),
   267  							result.entry.Path,
   268  							result.entry.Parent,
   269  							result.entry.Generation,
   270  							len(result.entry.Data),
   271  							result.entryDuration,
   272  						)
   273  					}
   274  					stop(err)
   275  				}
   276  			} else if result.coverageData != nil {
   277  				if c.warmupRun() {
   278  					if shouldPrintDebugInfo() {
   279  						fmt.Fprintf(
   280  							c.opts.Log,
   281  							"DEBUG processed an initial input, elapsed: %s, id: %s, new bits: %d, size: %d, exec time: %s\n",
   282  							c.elapsed(),
   283  							result.entry.Parent,
   284  							countBits(diffCoverage(c.coverageMask, result.coverageData)),
   285  							len(result.entry.Data),
   286  							result.entryDuration,
   287  						)
   288  					}
   289  					c.updateCoverage(result.coverageData)
   290  					c.warmupInputLeft--
   291  					if c.warmupInputLeft == 0 {
   292  						fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, gathering baseline coverage: %d/%d completed, now fuzzing with %d workers\n", c.elapsed(), c.warmupInputCount, c.warmupInputCount, c.opts.Parallel)
   293  						if shouldPrintDebugInfo() {
   294  							fmt.Fprintf(
   295  								c.opts.Log,
   296  								"DEBUG finished processing input corpus, elapsed: %s, entries: %d, initial coverage bits: %d\n",
   297  								c.elapsed(),
   298  								len(c.corpus.entries),
   299  								countBits(c.coverageMask),
   300  							)
   301  						}
   302  					}
   303  				} else if keepCoverage := diffCoverage(c.coverageMask, result.coverageData); keepCoverage != nil {
   304  					// Found a value that expanded coverage.
   305  					// It's not a crasher, but we may want to add it to the on-disk
   306  					// corpus and prioritize it for future fuzzing.
   307  					// TODO(jayconrod, katiehockman): Prioritize fuzzing these
   308  					// values which expanded coverage, perhaps based on the
   309  					// number of new edges that this result expanded.
   310  					// TODO(jayconrod, katiehockman): Don't write a value that's already
   311  					// in the corpus.
   312  					if c.canMinimize() && result.canMinimize && c.crashMinimizing == nil {
   313  						// Send back to workers to find a smaller value that preserves
   314  						// at least one new coverage bit.
   315  						c.queueForMinimization(result, keepCoverage)
   316  					} else {
   317  						// Update the coordinator's coverage mask and save the value.
   318  						inputSize := len(result.entry.Data)
   319  						entryNew, err := c.addCorpusEntries(true, result.entry)
   320  						if err != nil {
   321  							stop(err)
   322  							break
   323  						}
   324  						if !entryNew {
   325  							continue
   326  						}
   327  						c.updateCoverage(keepCoverage)
   328  						c.inputQueue.enqueue(result.entry)
   329  						c.interestingCount++
   330  						if shouldPrintDebugInfo() {
   331  							fmt.Fprintf(
   332  								c.opts.Log,
   333  								"DEBUG new interesting input, elapsed: %s, id: %s, parent: %s, gen: %d, new bits: %d, total bits: %d, size: %d, exec time: %s\n",
   334  								c.elapsed(),
   335  								result.entry.Path,
   336  								result.entry.Parent,
   337  								result.entry.Generation,
   338  								countBits(keepCoverage),
   339  								countBits(c.coverageMask),
   340  								inputSize,
   341  								result.entryDuration,
   342  							)
   343  						}
   344  					}
   345  				} else {
   346  					if shouldPrintDebugInfo() {
   347  						fmt.Fprintf(
   348  							c.opts.Log,
   349  							"DEBUG worker reported interesting input that doesn't expand coverage, elapsed: %s, id: %s, parent: %s, canMinimize: %t\n",
   350  							c.elapsed(),
   351  							result.entry.Path,
   352  							result.entry.Parent,
   353  							result.canMinimize,
   354  						)
   355  					}
   356  				}
   357  			} else if c.warmupRun() {
   358  				// No error or coverage data was reported for this input during
   359  				// warmup, so continue processing results.
   360  				c.warmupInputLeft--
   361  				if c.warmupInputLeft == 0 {
   362  					fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, testing seed corpus: %d/%d completed, now fuzzing with %d workers\n", c.elapsed(), c.warmupInputCount, c.warmupInputCount, c.opts.Parallel)
   363  					if shouldPrintDebugInfo() {
   364  						fmt.Fprintf(
   365  							c.opts.Log,
   366  							"DEBUG finished testing-only phase, elapsed: %s, entries: %d\n",
   367  							time.Since(c.startTime),
   368  							len(c.corpus.entries),
   369  						)
   370  					}
   371  				}
   372  			}
   373  
   374  			// Once the result has been processed, stop the worker if we
   375  			// have reached the fuzzing limit.
   376  			if c.opts.Limit > 0 && c.count >= c.opts.Limit {
   377  				stop(nil)
   378  			}
   379  
   380  		case inputC <- input:
   381  			// Sent the next input to a worker.
   382  			c.sentInput(input)
   383  
   384  		case minimizeC <- minimizeInput:
   385  			// Sent the next input for minimization to a worker.
   386  			c.sentMinimizeInput(minimizeInput)
   387  
   388  		case <-statTicker.C:
   389  			c.logStats()
   390  		}
   391  	}
   392  
   393  	// TODO(jayconrod,katiehockman): if a crasher can't be written to the corpus,
   394  	// write to the cache instead.
   395  }
   396  
   397  // crashError wraps a crasher written to the seed corpus. It saves the name
   398  // of the file where the input causing the crasher was saved. The testing
   399  // framework uses this to report a command to re-run that specific input.
   400  type crashError struct {
   401  	path string
   402  	err  error
   403  }
   404  
   405  func (e *crashError) Error() string {
   406  	return e.err.Error()
   407  }
   408  
   409  func (e *crashError) Unwrap() error {
   410  	return e.err
   411  }
   412  
   413  func (e *crashError) CrashPath() string {
   414  	return e.path
   415  }
   416  
   417  type corpus struct {
   418  	entries []CorpusEntry
   419  	hashes  map[[sha256.Size]byte]bool
   420  }
   421  
   422  // addCorpusEntries adds entries to the corpus, and optionally writes the entries
   423  // to the cache directory. If an entry is already in the corpus it is skipped. If
   424  // all of the entries are unique, addCorpusEntries returns true and a nil error,
   425  // if at least one of the entries was a duplicate, it returns false and a nil error.
   426  func (c *coordinator) addCorpusEntries(addToCache bool, entries ...CorpusEntry) (bool, error) {
   427  	noDupes := true
   428  	for _, e := range entries {
   429  		data, err := corpusEntryData(e)
   430  		if err != nil {
   431  			return false, err
   432  		}
   433  		h := sha256.Sum256(data)
   434  		if c.corpus.hashes[h] {
   435  			noDupes = false
   436  			continue
   437  		}
   438  		if addToCache {
   439  			if err := writeToCorpus(&e, c.opts.CacheDir); err != nil {
   440  				return false, err
   441  			}
   442  			// For entries written to disk, we don't hold onto the bytes,
   443  			// since the corpus would consume a significant amount of
   444  			// memory.
   445  			e.Data = nil
   446  		}
   447  		c.corpus.hashes[h] = true
   448  		c.corpus.entries = append(c.corpus.entries, e)
   449  	}
   450  	return noDupes, nil
   451  }
   452  
   453  // CorpusEntry represents an individual input for fuzzing.
   454  //
   455  // We must use an equivalent type in the testing and testing/internal/testdeps
   456  // packages, but testing can't import this package directly, and we don't want
   457  // to export this type from testing. Instead, we use the same struct type and
   458  // use a type alias (not a defined type) for convenience.
   459  type CorpusEntry = struct {
   460  	Parent string
   461  
   462  	// Path is the path of the corpus file, if the entry was loaded from disk.
   463  	// For other entries, including seed values provided by f.Add, Path is the
   464  	// name of the test, e.g. seed#0 or its hash.
   465  	Path string
   466  
   467  	// Data is the raw input data. Data should only be populated for seed
   468  	// values. For on-disk corpus files, Data will be nil, as it will be loaded
   469  	// from disk using Path.
   470  	Data []byte
   471  
   472  	// Values is the unmarshaled values from a corpus file.
   473  	Values []any
   474  
   475  	Generation int
   476  
   477  	// IsSeed indicates whether this entry is part of the seed corpus.
   478  	IsSeed bool
   479  }
   480  
   481  // corpusEntryData returns the raw input bytes, either from the data struct
   482  // field, or from disk.
   483  func corpusEntryData(ce CorpusEntry) ([]byte, error) {
   484  	if ce.Data != nil {
   485  		return ce.Data, nil
   486  	}
   487  
   488  	return os.ReadFile(ce.Path)
   489  }
   490  
   491  type fuzzInput struct {
   492  	// entry is the value to test initially. The worker will randomly mutate
   493  	// values from this starting point.
   494  	entry CorpusEntry
   495  
   496  	// timeout is the time to spend fuzzing variations of this input,
   497  	// not including starting or cleaning up.
   498  	timeout time.Duration
   499  
   500  	// limit is the maximum number of calls to the fuzz function the worker may
   501  	// make. The worker may make fewer calls, for example, if it finds an
   502  	// error early. If limit is zero, there is no limit on calls to the
   503  	// fuzz function.
   504  	limit int64
   505  
   506  	// warmup indicates whether this is a warmup input before fuzzing begins. If
   507  	// true, the input should not be fuzzed.
   508  	warmup bool
   509  
   510  	// coverageData reflects the coordinator's current coverageMask.
   511  	coverageData []byte
   512  }
   513  
   514  type fuzzResult struct {
   515  	// entry is an interesting value or a crasher.
   516  	entry CorpusEntry
   517  
   518  	// crasherMsg is an error message from a crash. It's "" if no crash was found.
   519  	crasherMsg string
   520  
   521  	// canMinimize is true if the worker should attempt to minimize this result.
   522  	// It may be false because an attempt has already been made.
   523  	canMinimize bool
   524  
   525  	// coverageData is set if the worker found new coverage.
   526  	coverageData []byte
   527  
   528  	// limit is the number of values the coordinator asked the worker
   529  	// to test. 0 if there was no limit.
   530  	limit int64
   531  
   532  	// count is the number of values the worker actually tested.
   533  	count int64
   534  
   535  	// totalDuration is the time the worker spent testing inputs.
   536  	totalDuration time.Duration
   537  
   538  	// entryDuration is the time the worker spent execution an interesting result
   539  	entryDuration time.Duration
   540  }
   541  
   542  type fuzzMinimizeInput struct {
   543  	// entry is an interesting value or crasher to minimize.
   544  	entry CorpusEntry
   545  
   546  	// crasherMsg is an error message from a crash. It's "" if no crash was found.
   547  	// If set, the worker will attempt to find a smaller input that also produces
   548  	// an error, though not necessarily the same error.
   549  	crasherMsg string
   550  
   551  	// limit is the maximum number of calls to the fuzz function the worker may
   552  	// make. The worker may make fewer calls, for example, if it can't reproduce
   553  	// an error. If limit is zero, there is no limit on calls to the fuzz function.
   554  	limit int64
   555  
   556  	// timeout is the time to spend minimizing this input.
   557  	// A zero timeout means no limit.
   558  	timeout time.Duration
   559  
   560  	// keepCoverage is a set of coverage bits that entry found that were not in
   561  	// the coordinator's combined set. When minimizing, the worker should find an
   562  	// input that preserves at least one of these bits. keepCoverage is nil for
   563  	// crashing inputs.
   564  	keepCoverage []byte
   565  }
   566  
   567  // coordinator holds channels that workers can use to communicate with
   568  // the coordinator.
   569  type coordinator struct {
   570  	opts CoordinateFuzzingOpts
   571  
   572  	// startTime is the time we started the workers after loading the corpus.
   573  	// Used for logging.
   574  	startTime time.Time
   575  
   576  	// inputC is sent values to fuzz by the coordinator. Any worker may receive
   577  	// values from this channel. Workers send results to resultC.
   578  	inputC chan fuzzInput
   579  
   580  	// minimizeC is sent values to minimize by the coordinator. Any worker may
   581  	// receive values from this channel. Workers send results to resultC.
   582  	minimizeC chan fuzzMinimizeInput
   583  
   584  	// resultC is sent results of fuzzing by workers. The coordinator
   585  	// receives these. Multiple types of messages are allowed.
   586  	resultC chan fuzzResult
   587  
   588  	// count is the number of values fuzzed so far.
   589  	count int64
   590  
   591  	// countLastLog is the number of values fuzzed when the output was last
   592  	// logged.
   593  	countLastLog int64
   594  
   595  	// timeLastLog is the time at which the output was last logged.
   596  	timeLastLog time.Time
   597  
   598  	// interestingCount is the number of unique interesting values which have
   599  	// been found this execution.
   600  	interestingCount int
   601  
   602  	// warmupInputCount is the count of all entries in the corpus which will
   603  	// need to be received from workers to run once during warmup, but not fuzz.
   604  	// This could be for coverage data, or only for the purposes of verifying
   605  	// that the seed corpus doesn't have any crashers. See warmupRun.
   606  	warmupInputCount int
   607  
   608  	// warmupInputLeft is the number of entries in the corpus which still need
   609  	// to be received from workers to run once during warmup, but not fuzz.
   610  	// See warmupInputLeft.
   611  	warmupInputLeft int
   612  
   613  	// duration is the time spent fuzzing inside workers, not counting time
   614  	// starting up or tearing down.
   615  	duration time.Duration
   616  
   617  	// countWaiting is the number of fuzzing executions the coordinator is
   618  	// waiting on workers to complete.
   619  	countWaiting int64
   620  
   621  	// corpus is a set of interesting values, including the seed corpus and
   622  	// generated values that workers reported as interesting.
   623  	corpus corpus
   624  
   625  	// minimizationAllowed is true if one or more of the types of fuzz
   626  	// function's parameters can be minimized.
   627  	minimizationAllowed bool
   628  
   629  	// inputQueue is a queue of inputs that workers should try fuzzing. This is
   630  	// initially populated from the seed corpus and cached inputs. More inputs
   631  	// may be added as new coverage is discovered.
   632  	inputQueue queue
   633  
   634  	// minimizeQueue is a queue of inputs that caused errors or exposed new
   635  	// coverage. Workers should attempt to find smaller inputs that do the
   636  	// same thing.
   637  	minimizeQueue queue
   638  
   639  	// crashMinimizing is the crash that is currently being minimized.
   640  	crashMinimizing *fuzzResult
   641  
   642  	// coverageMask aggregates coverage that was found for all inputs in the
   643  	// corpus. Each byte represents a single basic execution block. Each set bit
   644  	// within the byte indicates that an input has triggered that block at least
   645  	// 1 << n times, where n is the position of the bit in the byte. For example, a
   646  	// value of 12 indicates that separate inputs have triggered this block
   647  	// between 4-7 times and 8-15 times.
   648  	coverageMask []byte
   649  }
   650  
   651  func newCoordinator(opts CoordinateFuzzingOpts) (*coordinator, error) {
   652  	// Make sure all of the seed corpus has marshalled data.
   653  	for i := range opts.Seed {
   654  		if opts.Seed[i].Data == nil && opts.Seed[i].Values != nil {
   655  			opts.Seed[i].Data = marshalCorpusFile(opts.Seed[i].Values...)
   656  		}
   657  	}
   658  	c := &coordinator{
   659  		opts:        opts,
   660  		startTime:   time.Now(),
   661  		inputC:      make(chan fuzzInput),
   662  		minimizeC:   make(chan fuzzMinimizeInput),
   663  		resultC:     make(chan fuzzResult),
   664  		timeLastLog: time.Now(),
   665  		corpus:      corpus{hashes: make(map[[sha256.Size]byte]bool)},
   666  	}
   667  	if err := c.readCache(); err != nil {
   668  		return nil, err
   669  	}
   670  	if opts.MinimizeLimit > 0 || opts.MinimizeTimeout > 0 {
   671  		for _, t := range opts.Types {
   672  			if isMinimizable(t) {
   673  				c.minimizationAllowed = true
   674  				break
   675  			}
   676  		}
   677  	}
   678  
   679  	covSize := len(coverage())
   680  	if covSize == 0 {
   681  		fmt.Fprintf(c.opts.Log, "warning: the test binary was not built with coverage instrumentation, so fuzzing will run without coverage guidance and may be inefficient\n")
   682  		// Even though a coverage-only run won't occur, we should still run all
   683  		// of the seed corpus to make sure there are no existing failures before
   684  		// we start fuzzing.
   685  		c.warmupInputCount = len(c.opts.Seed)
   686  		for _, e := range c.opts.Seed {
   687  			c.inputQueue.enqueue(e)
   688  		}
   689  	} else {
   690  		c.warmupInputCount = len(c.corpus.entries)
   691  		for _, e := range c.corpus.entries {
   692  			c.inputQueue.enqueue(e)
   693  		}
   694  		// Set c.coverageMask to a clean []byte full of zeros.
   695  		c.coverageMask = make([]byte, covSize)
   696  	}
   697  	c.warmupInputLeft = c.warmupInputCount
   698  
   699  	if len(c.corpus.entries) == 0 {
   700  		fmt.Fprintf(c.opts.Log, "warning: starting with empty corpus\n")
   701  		var vals []any
   702  		for _, t := range opts.Types {
   703  			vals = append(vals, zeroValue(t))
   704  		}
   705  		data := marshalCorpusFile(vals...)
   706  		h := sha256.Sum256(data)
   707  		name := fmt.Sprintf("%x", h[:4])
   708  		c.addCorpusEntries(false, CorpusEntry{Path: name, Data: data})
   709  	}
   710  
   711  	return c, nil
   712  }
   713  
   714  func (c *coordinator) updateStats(result fuzzResult) {
   715  	c.count += result.count
   716  	c.countWaiting -= result.limit
   717  	c.duration += result.totalDuration
   718  }
   719  
   720  func (c *coordinator) logStats() {
   721  	now := time.Now()
   722  	if c.warmupRun() {
   723  		runSoFar := c.warmupInputCount - c.warmupInputLeft
   724  		if coverageEnabled {
   725  			fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, gathering baseline coverage: %d/%d completed\n", c.elapsed(), runSoFar, c.warmupInputCount)
   726  		} else {
   727  			fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, testing seed corpus: %d/%d completed\n", c.elapsed(), runSoFar, c.warmupInputCount)
   728  		}
   729  	} else if c.crashMinimizing != nil {
   730  		fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, minimizing\n", c.elapsed())
   731  	} else {
   732  		rate := float64(c.count-c.countLastLog) / now.Sub(c.timeLastLog).Seconds()
   733  		if coverageEnabled {
   734  			total := c.warmupInputCount + c.interestingCount
   735  			fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, execs: %d (%.0f/sec), new interesting: %d (total: %d)\n", c.elapsed(), c.count, rate, c.interestingCount, total)
   736  		} else {
   737  			fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, execs: %d (%.0f/sec)\n", c.elapsed(), c.count, rate)
   738  		}
   739  	}
   740  	c.countLastLog = c.count
   741  	c.timeLastLog = now
   742  }
   743  
   744  // peekInput returns the next value that should be sent to workers.
   745  // If the number of executions is limited, the returned value includes
   746  // a limit for one worker. If there are no executions left, peekInput returns
   747  // a zero value and false.
   748  //
   749  // peekInput doesn't actually remove the input from the queue. The caller
   750  // must call sentInput after sending the input.
   751  //
   752  // If the input queue is empty and the coverage/testing-only run has completed,
   753  // queue refills it from the corpus.
   754  func (c *coordinator) peekInput() (fuzzInput, bool) {
   755  	if c.opts.Limit > 0 && c.count+c.countWaiting >= c.opts.Limit {
   756  		// Already making the maximum number of calls to the fuzz function.
   757  		// Don't send more inputs right now.
   758  		return fuzzInput{}, false
   759  	}
   760  	if c.inputQueue.len == 0 {
   761  		if c.warmupRun() {
   762  			// Wait for coverage/testing-only run to finish before sending more
   763  			// inputs.
   764  			return fuzzInput{}, false
   765  		}
   766  		c.refillInputQueue()
   767  	}
   768  
   769  	entry, ok := c.inputQueue.peek()
   770  	if !ok {
   771  		panic("input queue empty after refill")
   772  	}
   773  	input := fuzzInput{
   774  		entry:   entry.(CorpusEntry),
   775  		timeout: workerFuzzDuration,
   776  		warmup:  c.warmupRun(),
   777  	}
   778  	if c.coverageMask != nil {
   779  		input.coverageData = make([]byte, len(c.coverageMask))
   780  		copy(input.coverageData, c.coverageMask)
   781  	}
   782  	if input.warmup {
   783  		// No fuzzing will occur, but it should count toward the limit set by
   784  		// -fuzztime.
   785  		input.limit = 1
   786  		return input, true
   787  	}
   788  
   789  	if c.opts.Limit > 0 {
   790  		input.limit = c.opts.Limit / int64(c.opts.Parallel)
   791  		if c.opts.Limit%int64(c.opts.Parallel) > 0 {
   792  			input.limit++
   793  		}
   794  		remaining := c.opts.Limit - c.count - c.countWaiting
   795  		if input.limit > remaining {
   796  			input.limit = remaining
   797  		}
   798  	}
   799  	return input, true
   800  }
   801  
   802  // sentInput updates internal counters after an input is sent to c.inputC.
   803  func (c *coordinator) sentInput(input fuzzInput) {
   804  	c.inputQueue.dequeue()
   805  	c.countWaiting += input.limit
   806  }
   807  
   808  // refillInputQueue refills the input queue from the corpus after it becomes
   809  // empty.
   810  func (c *coordinator) refillInputQueue() {
   811  	for _, e := range c.corpus.entries {
   812  		c.inputQueue.enqueue(e)
   813  	}
   814  }
   815  
   816  // queueForMinimization creates a fuzzMinimizeInput from result and adds it
   817  // to the minimization queue to be sent to workers.
   818  func (c *coordinator) queueForMinimization(result fuzzResult, keepCoverage []byte) {
   819  	if result.crasherMsg != "" {
   820  		c.minimizeQueue.clear()
   821  	}
   822  
   823  	input := fuzzMinimizeInput{
   824  		entry:        result.entry,
   825  		crasherMsg:   result.crasherMsg,
   826  		keepCoverage: keepCoverage,
   827  	}
   828  	c.minimizeQueue.enqueue(input)
   829  }
   830  
   831  // peekMinimizeInput returns the next input that should be sent to workers for
   832  // minimization.
   833  func (c *coordinator) peekMinimizeInput() (fuzzMinimizeInput, bool) {
   834  	if !c.canMinimize() {
   835  		// Already making the maximum number of calls to the fuzz function.
   836  		// Don't send more inputs right now.
   837  		return fuzzMinimizeInput{}, false
   838  	}
   839  	v, ok := c.minimizeQueue.peek()
   840  	if !ok {
   841  		return fuzzMinimizeInput{}, false
   842  	}
   843  	input := v.(fuzzMinimizeInput)
   844  
   845  	if c.opts.MinimizeTimeout > 0 {
   846  		input.timeout = c.opts.MinimizeTimeout
   847  	}
   848  	if c.opts.MinimizeLimit > 0 {
   849  		input.limit = c.opts.MinimizeLimit
   850  	} else if c.opts.Limit > 0 {
   851  		if input.crasherMsg != "" {
   852  			input.limit = c.opts.Limit
   853  		} else {
   854  			input.limit = c.opts.Limit / int64(c.opts.Parallel)
   855  			if c.opts.Limit%int64(c.opts.Parallel) > 0 {
   856  				input.limit++
   857  			}
   858  		}
   859  	}
   860  	if c.opts.Limit > 0 {
   861  		remaining := c.opts.Limit - c.count - c.countWaiting
   862  		if input.limit > remaining {
   863  			input.limit = remaining
   864  		}
   865  	}
   866  	return input, true
   867  }
   868  
   869  // sentMinimizeInput removes an input from the minimization queue after it's
   870  // sent to minimizeC.
   871  func (c *coordinator) sentMinimizeInput(input fuzzMinimizeInput) {
   872  	c.minimizeQueue.dequeue()
   873  	c.countWaiting += input.limit
   874  }
   875  
   876  // warmupRun returns true while the coordinator is running inputs without
   877  // mutating them as a warmup before fuzzing. This could be to gather baseline
   878  // coverage data for entries in the corpus, or to test all of the seed corpus
   879  // for errors before fuzzing begins.
   880  //
   881  // The coordinator doesn't store coverage data in the cache with each input
   882  // because that data would be invalid when counter offsets in the test binary
   883  // change.
   884  //
   885  // When gathering coverage, the coordinator sends each entry to a worker to
   886  // gather coverage for that entry only, without fuzzing or minimizing. This
   887  // phase ends when all workers have finished, and the coordinator has a combined
   888  // coverage map.
   889  func (c *coordinator) warmupRun() bool {
   890  	return c.warmupInputLeft > 0
   891  }
   892  
   893  // updateCoverage sets bits in c.coverageMask that are set in newCoverage.
   894  // updateCoverage returns the number of newly set bits. See the comment on
   895  // coverageMask for the format.
   896  func (c *coordinator) updateCoverage(newCoverage []byte) int {
   897  	if len(newCoverage) != len(c.coverageMask) {
   898  		panic(fmt.Sprintf("number of coverage counters changed at runtime: %d, expected %d", len(newCoverage), len(c.coverageMask)))
   899  	}
   900  	newBitCount := 0
   901  	for i := range newCoverage {
   902  		diff := newCoverage[i] &^ c.coverageMask[i]
   903  		newBitCount += bits.OnesCount8(diff)
   904  		c.coverageMask[i] |= newCoverage[i]
   905  	}
   906  	return newBitCount
   907  }
   908  
   909  // canMinimize returns whether the coordinator should attempt to find smaller
   910  // inputs that reproduce a crash or new coverage.
   911  func (c *coordinator) canMinimize() bool {
   912  	return c.minimizationAllowed &&
   913  		(c.opts.Limit == 0 || c.count+c.countWaiting < c.opts.Limit)
   914  }
   915  
   916  func (c *coordinator) elapsed() time.Duration {
   917  	return time.Since(c.startTime).Round(1 * time.Second)
   918  }
   919  
   920  // readCache creates a combined corpus from seed values and values in the cache
   921  // (in GOCACHE/fuzz).
   922  //
   923  // TODO(fuzzing): need a mechanism that can remove values that
   924  // aren't useful anymore, for example, because they have the wrong type.
   925  func (c *coordinator) readCache() error {
   926  	if _, err := c.addCorpusEntries(false, c.opts.Seed...); err != nil {
   927  		return err
   928  	}
   929  	entries, err := ReadCorpus(c.opts.CacheDir, c.opts.Types)
   930  	if err != nil {
   931  		if _, ok := err.(*MalformedCorpusError); !ok {
   932  			// It's okay if some files in the cache directory are malformed and
   933  			// are not included in the corpus, but fail if it's an I/O error.
   934  			return err
   935  		}
   936  		// TODO(jayconrod,katiehockman): consider printing some kind of warning
   937  		// indicating the number of files which were skipped because they are
   938  		// malformed.
   939  	}
   940  	if _, err := c.addCorpusEntries(false, entries...); err != nil {
   941  		return err
   942  	}
   943  	return nil
   944  }
   945  
   946  // MalformedCorpusError is an error found while reading the corpus from the
   947  // filesystem. All of the errors are stored in the errs list. The testing
   948  // framework uses this to report malformed files in testdata.
   949  type MalformedCorpusError struct {
   950  	errs []error
   951  }
   952  
   953  func (e *MalformedCorpusError) Error() string {
   954  	var msgs []string
   955  	for _, s := range e.errs {
   956  		msgs = append(msgs, s.Error())
   957  	}
   958  	return strings.Join(msgs, "\n")
   959  }
   960  
   961  // ReadCorpus reads the corpus from the provided dir. The returned corpus
   962  // entries are guaranteed to match the given types. Any malformed files will
   963  // be saved in a MalformedCorpusError and returned, along with the most recent
   964  // error.
   965  func ReadCorpus(dir string, types []reflect.Type) ([]CorpusEntry, error) {
   966  	files, err := ioutil.ReadDir(dir)
   967  	if os.IsNotExist(err) {
   968  		return nil, nil // No corpus to read
   969  	} else if err != nil {
   970  		return nil, fmt.Errorf("reading seed corpus from testdata: %v", err)
   971  	}
   972  	var corpus []CorpusEntry
   973  	var errs []error
   974  	for _, file := range files {
   975  		// TODO(jayconrod,katiehockman): determine when a file is a fuzzing input
   976  		// based on its name. We should only read files created by writeToCorpus.
   977  		// If we read ALL files, we won't be able to change the file format by
   978  		// changing the extension. We also won't be able to add files like
   979  		// README.txt explaining why the directory exists.
   980  		if file.IsDir() {
   981  			continue
   982  		}
   983  		filename := filepath.Join(dir, file.Name())
   984  		data, err := ioutil.ReadFile(filename)
   985  		if err != nil {
   986  			return nil, fmt.Errorf("failed to read corpus file: %v", err)
   987  		}
   988  		var vals []any
   989  		vals, err = readCorpusData(data, types)
   990  		if err != nil {
   991  			errs = append(errs, fmt.Errorf("%q: %v", filename, err))
   992  			continue
   993  		}
   994  		corpus = append(corpus, CorpusEntry{Path: filename, Values: vals})
   995  	}
   996  	if len(errs) > 0 {
   997  		return corpus, &MalformedCorpusError{errs: errs}
   998  	}
   999  	return corpus, nil
  1000  }
  1001  
  1002  func readCorpusData(data []byte, types []reflect.Type) ([]any, error) {
  1003  	vals, err := unmarshalCorpusFile(data)
  1004  	if err != nil {
  1005  		return nil, fmt.Errorf("unmarshal: %v", err)
  1006  	}
  1007  	if err = CheckCorpus(vals, types); err != nil {
  1008  		return nil, err
  1009  	}
  1010  	return vals, nil
  1011  }
  1012  
  1013  // CheckCorpus verifies that the types in vals match the expected types
  1014  // provided.
  1015  func CheckCorpus(vals []any, types []reflect.Type) error {
  1016  	if len(vals) != len(types) {
  1017  		return fmt.Errorf("wrong number of values in corpus entry: %d, want %d", len(vals), len(types))
  1018  	}
  1019  	valsT := make([]reflect.Type, len(vals))
  1020  	for valsI, v := range vals {
  1021  		valsT[valsI] = reflect.TypeOf(v)
  1022  	}
  1023  	for i := range types {
  1024  		if valsT[i] != types[i] {
  1025  			return fmt.Errorf("mismatched types in corpus entry: %v, want %v", valsT, types)
  1026  		}
  1027  	}
  1028  	return nil
  1029  }
  1030  
  1031  // writeToCorpus atomically writes the given bytes to a new file in testdata. If
  1032  // the directory does not exist, it will create one. If the file already exists,
  1033  // writeToCorpus will not rewrite it. writeToCorpus sets entry.Path to the new
  1034  // file that was just written or an error if it failed.
  1035  func writeToCorpus(entry *CorpusEntry, dir string) (err error) {
  1036  	sum := fmt.Sprintf("%x", sha256.Sum256(entry.Data))
  1037  	entry.Path = filepath.Join(dir, sum)
  1038  	if err := os.MkdirAll(dir, 0777); err != nil {
  1039  		return err
  1040  	}
  1041  	if err := ioutil.WriteFile(entry.Path, entry.Data, 0666); err != nil {
  1042  		os.Remove(entry.Path) // remove partially written file
  1043  		return err
  1044  	}
  1045  	return nil
  1046  }
  1047  
  1048  func testName(path string) string {
  1049  	return filepath.Base(path)
  1050  }
  1051  
  1052  func zeroValue(t reflect.Type) any {
  1053  	for _, v := range zeroVals {
  1054  		if reflect.TypeOf(v) == t {
  1055  			return v
  1056  		}
  1057  	}
  1058  	panic(fmt.Sprintf("unsupported type: %v", t))
  1059  }
  1060  
  1061  var zeroVals []any = []any{
  1062  	[]byte(""),
  1063  	string(""),
  1064  	false,
  1065  	byte(0),
  1066  	rune(0),
  1067  	float32(0),
  1068  	float64(0),
  1069  	int(0),
  1070  	int8(0),
  1071  	int16(0),
  1072  	int32(0),
  1073  	int64(0),
  1074  	uint(0),
  1075  	uint8(0),
  1076  	uint16(0),
  1077  	uint32(0),
  1078  	uint64(0),
  1079  }
  1080  
  1081  var (
  1082  	debugInfo     bool
  1083  	debugInfoOnce sync.Once
  1084  )
  1085  
  1086  func shouldPrintDebugInfo() bool {
  1087  	debugInfoOnce.Do(func() {
  1088  		debugInfo = godebug.Get("fuzzdebug") == "1"
  1089  	})
  1090  	return debugInfo
  1091  }
  1092  

View as plain text