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

syz-manager: corpus rotation #1348

Open
dvyukov opened this issue Aug 19, 2019 · 0 comments
Open

syz-manager: corpus rotation #1348

dvyukov opened this issue Aug 19, 2019 · 0 comments

Comments

@dvyukov
Copy link
Collaborator

dvyukov commented Aug 19, 2019

The idea is push the fuzzer out of local maximums and help it to deal with data-driven code (where straightforward code coverage helps only once) by temporary removing part of inputs from the corpus (and associated coverage), and then letting fuzzers re-discover that coverage but potentially in a different way. After some time we should combine the removed part and the new part and minimize the corpus in some pseudo-non-deterministic way so that we get some mix of old and new inputs. Over time this should continuously rotate and refresh the corpus not letting it to stuck in local maximums, but without increasing corpus size.
The simplest strategy for selecting the part to remove is just X% of random inputs. However, a more useful strategy may be to try to free some continuous region of the state space, e.g. by removing all inputs that cover the same PC, or all inputs with a particular syscall, etc.
On implementation level the simplest strategy would be to remove part of inputs for every fuzzer/VM. I.e. each VM doesn't get some part of the corpus and the associated coverage. Then maybe the rest will even happen automatically. It may be suboptimal because VMs may be too short-lived, so that there is not enough time to refill the gap. But it still may be a good starting point.
There are multiple signals coming from different sides that this improvement should be very profitable.
Unbranched from #534

dvyukov added a commit to dvyukov/syzkaller that referenced this issue Dec 30, 2019
Use a random subset of syscalls/corpus/coverage for each individual VM run.
Hypothesis is that this should allow fuzzer to get more coverage
find more bugs in saturated state (stuck in local optimum).
See the issue and comments for details.

Update google#1348
dvyukov added a commit that referenced this issue Dec 30, 2019
Use a random subset of syscalls/corpus/coverage for each individual VM run.
Hypothesis is that this should allow fuzzer to get more coverage
find more bugs in saturated state (stuck in local optimum).
See the issue and comments for details.

Update #1348
dvyukov added a commit that referenced this issue Dec 30, 2019
dvyukov added a commit that referenced this issue Jan 7, 2020
Temporary disable corpus rotation b/c we suspect it negatively affects fuzzing.
But we don't have hard data, and the easiest way to check is to disable
and see what happens.

Update #1348
dvyukov added a commit to dvyukov/syzkaller that referenced this issue Oct 1, 2020
Let's give it another chance since the previous coverage drop wasn't
completely conclusive.
Few changes that may help:
 - do rotation at 1/5 instead of 1/3 rate
 - don't send triage candidates to rotated VMs,
   since they may not have required syscalls enabled
 - don't send new inputs/coverage to rotated VMs,
   let them run in complete isolation

Update google#1348
dvyukov added a commit that referenced this issue Oct 1, 2020
Let's give it another chance since the previous coverage drop wasn't
completely conclusive.
Few changes that may help:
 - do rotation at 1/5 instead of 1/3 rate
 - don't send triage candidates to rotated VMs,
   since they may not have required syscalls enabled
 - don't send new inputs/coverage to rotated VMs,
   let them run in complete isolation

Update #1348
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant