Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[dev.fuzz] cmd/go: do not instrument packages which are non-deterministic #46410

Open
rolandshoemaker opened this issue May 27, 2021 · 6 comments
Open

Comments

@rolandshoemaker
Copy link
Member

@rolandshoemaker rolandshoemaker commented May 27, 2021

During development I've noticed that reported coverage will often decrease after restarting fuzzing, indicating that counters are being incremented by functionality not triggered by the code being fuzzed.

Doing some manual testing while working on a encoding/json indicates that sync in particular is quite noisy and will cause new edges to be triggered for the first couple of seconds.

We probably can't automate this for third party code (although we should probably document that if you're fuzzing code that i.e. spawns background goroutines in an init it may be quite noisy) we may want to make an effort to find packages in the stdlib which have this problem. The simplest approach to this would be to run a fuzz target which does nothing (f.Fuzz(func(_ *testing.T, _b_ []byte) {})) and incrementally instrument packages. Anything that then increases counted edges can probably be considered noisy, and should be considered for exclusion (there will, likely, be packages we cannot exclude, despite being noisy).

@mvdan
Copy link
Member

@mvdan mvdan commented May 27, 2021

When instrumenting for fuzzing, I wonder if we could make sync.Pool never reuse objects to work around this problem.

Some form of caching will always be possible - for example, encoding/json uses a global sync.Map to cache other stuff. But at least we could alleviate the problem for pools.

@bcmills
Copy link
Member

@bcmills bcmills commented May 27, 2021

I wonder if we could make sync.Pool never reuse objects to work around this problem.

Object-reuse is a common source of sync.Pool bugs. If I understand the suggestion correctly, I think it would be a mistake to change this behavior when fuzzing.

One alternative might be to hook the scheduler to make it deterministic (based on some seed — #46221?) even for otherwise-nondeterministic code.

My question is, though: what's the harm in exercising nondeterminism? That might mean that the fuzzer explores some redundant parts of the input space, but if the behavior of the function is nondeterministic then it's good to explore some redundant parts of the input space in order to catch scheduling-sensitive bugs (compare #22569, #43794).

@mknyszek mknyszek added this to the Go1.18 milestone May 27, 2021
@mknyszek mknyszek changed the title [dev.fuzz] do not instrument packages which are non-deterministic [dev.fuzz] cmd/go: do not instrument packages which are non-deterministic May 27, 2021
@rolandshoemaker
Copy link
Member Author

@rolandshoemaker rolandshoemaker commented Jun 1, 2021

My question is, though: what's the harm in exercising nondeterminism? That might mean that the fuzzer explores some redundant parts of the input space, but if the behavior of the function is nondeterministic then it's good to explore some redundant parts of the input space in order to catch scheduling-sensitive bugs (compare #22569, #43794).

I think exercising non-deterministic behavior of the functions being fuzzed is definitely expected behavior, my concern is with non-deterministic behavior of code that isn't being fuzzed. Going back to my initial example, if I'm fuzzing a function which simply does _ = 1 + 1, but by importing a certain package I'm seeing edge coverage increase then we are getting noise that is not productive.

Perhaps that level of noise is acceptable though? It's somewhat hard to tell without a good set of targets to test against whether this will significantly impede the performance of the fuzzing engine.

@thepudds
Copy link

@thepudds thepudds commented Jun 1, 2021

I think when it comes to fuzzing, not all forms of non-determinism are equally helpful. Randomness or pseudo-randomness is important of course within the mutator, and randomness in how threads or goroutines are scheduled can be helpful, especially if running under a race detector, but it can be less helpful to have randomness in the coverage metrics or randomness in background code that is not under test (e.g., GC runtime code) that effectively drives randomness in the coverage.

FWIW, here is a slightly older snapshot of some of the instrumentation exclusions for dvyukov/go-fuzz:

https://github.com/dvyukov/go-fuzz/blob/fc9bdef631a7086b4708dae03a370f7294c1d335/go-fuzz-build/main.go#L310-L326

	ignore := map[string]bool{
		"runtime":                         true, // lots of non-determinism and irrelevant code paths (e.g. different paths in mallocgc, chans and maps)
		"runtime/internal/atomic":         true, // runtime depends on it
		"runtime/internal/sys":            true, // runtime depends on it
		"unsafe":                          true, // nothing to see here (also creates import cycle with go-fuzz-dep)
		"errors":                          true, // nothing to see here (also creates import cycle with go-fuzz-dep)
		"syscall":                         true, // creates import cycle with go-fuzz-dep (and probably nothing to see here)
		"internal/syscall/windows/sysdll": true, //syscall depends on it
		"sync":             true, // non-deterministic and not interesting (also creates import cycle with go-fuzz-dep)
		"sync/atomic":      true, // not interesting (also creates import cycle with go-fuzz-dep)
		"time":             true, // creates import cycle with go-fuzz-dep
		"internal/bytealg": true, // runtime depends on it
		"internal/cpu":     true, // runtime depends on it
		"internal/race":    true, // runtime depends on it
		"runtime/cgo":      true, // why would we instrument it?
		"runtime/pprof":    true, // why would we instrument it?
		"runtime/race":     true, // why would we instrument it?
	}

(You can of course also look at the current code, but it is more dynamic now, without the associated per-package comments).

@bcmills
Copy link
Member

@bcmills bcmills commented Jun 1, 2021

@rolandshoemaker

my concern is with non-deterministic behavior of code that isn't being fuzzed.

If you're importing a package that does non-trivial init-time work, then perhaps one solution is for the fuzzer to distinguish between “transient” and “steady-state” runs: a program that has no pending timers and no runnable goroutines is in a steady state, whereas a program that does have pending timers or goroutines does not.

It still seems important to test the transient states, since (for example) a logical race between a background ticker and the API under test would not be diagnosed if we only tested steady states. But we could at least treat the coverage from transients different from the coverage for steady states, or try to run the program to a steady state before fuzzing to get a baseline for the “steady-state coverage”.

@thepudds
Copy link

@thepudds thepudds commented Jun 3, 2021

What packages are currently getting instrumented?

From the initial writeup of this issue, I was incorrectly interpreting that it was instrumenting the runtime and all of the stdlib, but it looks like that it currently avoids the runtime:

https://github.com/golang/go/blob/dev.fuzz/src/cmd/compile/internal/base/flag.go#L240-L241

For example, is it instrumenting syscall? If so, that's one example that was causing a crash in an earlier incarnation of the compiler instrumentation (via go114-fuzz-build) under OSS-Fuzz: google/oss-fuzz#3639 (comment).

For a beta / early MVP, it might be better to start by notching out the "noisy" / non-deterministic packages that go-fuzz was notching out from the stdlib (e.g., sync), which is part of what I was trying to say above... and which is probably a fairly short list to start...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants