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