Task selection and seed selection for Syzkaller using reinforcement learning
386 views
Skip to first unread message
Daimeng Wang
Feb 11, 2020, 10:39:57 PM2/11/20
to syzk...@googlegroups.com, Zhiyun Qian
Hi,
We're a group of researchers from the University of California Riverside. Recently we conducted some research on improving Syzkaller's coverage growth efficiency using reinforcement learning. Specifically, we used a Multi-armed-bandit-like algorithm to schedule fuzzing tasks (generate, mutate, triage) and choose seed to mutate.
We ran 10 separate single-process full-kernel fuzzers with our modification on our server for 5 days and compared the result with the unmodified Syzkaller at the commit ddc3e85997efdad885e208db6a98bca86e5dd52f on 01/08/2020. Our method improves the median coverage reached by 35,000 (16.1%) branches.
The work is now under submission to an academic conference. But we are eager to contribute to the kernel fuzzing community and are willing to upstream our changes to Syzkaller (perhaps as an optional mode in which Syzkaller can operate initially). Please let us know if you're interested and feel free to let us know if you would like to know more details.
--
We're a group of researchers from the University of California Riverside. Recently we conducted some research on improving Syzkaller's coverage growth efficiency using reinforcement learning. Specifically, we used a Multi-armed-bandit-like algorithm to schedule fuzzing tasks (generate, mutate, triage) and choose seed to mutate.
We ran 10 separate single-process full-kernel fuzzers with our modification on our server for 5 days and compared the result with the unmodified Syzkaller at the commit ddc3e85997efdad885e208db6a98bca86e5dd52f on 01/08/2020. Our method improves the median coverage reached by 35,000 (16.1%) branches.
The work is now under submission to an academic conference. But we are eager to contribute to the kernel fuzzing community and are willing to upstream our changes to Syzkaller (perhaps as an optional mode in which Syzkaller can operate initially). Please let us know if you're interested and feel free to let us know if you would like to know more details.
Best,
Daimeng
Daimeng Wang
Department of Computer Science & Engineering
University of California, Riverside
Department of Computer Science & Engineering
University of California, Riverside
Dmitry Vyukov
Feb 12, 2020, 1:39:58 AM2/12/20
to dwan...@cs.ucr.edu, syzkaller, Zhiyun Qian
On Wed, Feb 12, 2020 at 4:40 AM Daimeng Wang <dwan...@ucr.edu> wrote:
>
> Hi,
>
> We're a group of researchers from the University of California Riverside. Recently we conducted some research on improving Syzkaller's coverage growth efficiency using reinforcement learning. Specifically, we used a Multi-armed-bandit-like algorithm to schedule fuzzing tasks (generate, mutate, triage) and choose seed to mutate.
>
> We ran 10 separate single-process full-kernel fuzzers with our modification on our server for 5 days and compared the result with the unmodified Syzkaller at the commit ddc3e85997efdad885e208db6a98bca86e5dd52f on 01/08/2020. Our method improves the median coverage reached by 35,000 (16.1%) branches.
>
> The work is now under submission to an academic conference. But we are eager to contribute to the kernel fuzzing community and are willing to upstream our changes to Syzkaller (perhaps as an optional mode in which Syzkaller can operate initially). Please let us know if you're interested and feel free to let us know if you would like to know more details.
Hi Daimeng,
>
> Hi,
>
> We're a group of researchers from the University of California Riverside. Recently we conducted some research on improving Syzkaller's coverage growth efficiency using reinforcement learning. Specifically, we used a Multi-armed-bandit-like algorithm to schedule fuzzing tasks (generate, mutate, triage) and choose seed to mutate.
>
> We ran 10 separate single-process full-kernel fuzzers with our modification on our server for 5 days and compared the result with the unmodified Syzkaller at the commit ddc3e85997efdad885e208db6a98bca86e5dd52f on 01/08/2020. Our method improves the median coverage reached by 35,000 (16.1%) branches.
>
> The work is now under submission to an academic conference. But we are eager to contribute to the kernel fuzzing community and are willing to upstream our changes to Syzkaller (perhaps as an optional mode in which Syzkaller can operate initially). Please let us know if you're interested and feel free to let us know if you would like to know more details.
Sounds interesting and looks you get some good results.
Please send a pull request on github and then we can have a more
concrete discussion.
Few questions based on your high-level description. You say "can
operate initially", why only initially?
"schedule fuzzing tasks (generate, mutate, triage)" - why does it make
sense to ever de-prioritize triage? If we don't triage, we don't get
benefit from any other tasks, so I would assume it should be the
highest priority regardless. However, mutate/generate may be subject
to tuning.
When your paper is public, I would appreciate if you add it here:
https://github.com/google/syzkaller/blob/master/docs/research.md
Thanks
Dmitry Vyukov
Feb 13, 2020, 1:35:54 AM2/13/20
to dwan...@cs.ucr.edu, Zhiyun Qian, syzkaller
On Wed, Feb 12, 2020 at 9:37 PM Daimeng Wang <dwan...@ucr.edu> wrote:
>
> Hi Dmitry,
>
> Will do.
Ah, interesting.
I think inputs produced during minimization are somewhat similar to
the "smash" phase, where we indeed try to produce more derivative
inputs from the new input. The concern is that if we pile lots of
inputs into the triage queue and then the VM crashes, we lose all of
that (including potentially part of initial corpus). Maybe it makes
sense to introduce 2 triage queues (primary and secondary) and add
minimization results (and maybe inputs produced during smash) into the
secondary one.
Or maybe a more fundamental solution is to send inputs to the manager
sooner (e.g. before minimization) and then it will distribute them for
minimization and smashing later.
> --
> Daimeng (Desmond) Wang
>
> Hi Dmitry,
>
> Will do.
>
> You say "can operate initially", why only initially?
>
> By initially we mean the option to use reinforcement learning can be set when Syzkaller start running. In theory it can benefit Syzkaller throughout the fuzzing process. Sorry for the confusion.
> You say "can operate initially", why only initially?
>
>
> "schedule fuzzing tasks (generate, mutate, triage)" - why does it make sense to ever de-prioritize triage? If we don't triage, we don't get benefit from any other tasks, so I would assume it should be the highest priority regardless. However, mutate/generate may be subject to tuning.
>
> We do find that delaying triage at the fuzzer start can impact the initial seeds Syzkaller creates. Giving triage absolute priority will result in many initial seeds created by minimization. As the fuzzer runs for longer, we do find that reinforcement learning reaches the same agreement on giving triage absolute priority.
> "schedule fuzzing tasks (generate, mutate, triage)" - why does it make sense to ever de-prioritize triage? If we don't triage, we don't get benefit from any other tasks, so I would assume it should be the highest priority regardless. However, mutate/generate may be subject to tuning.
>
Ah, interesting.
I think inputs produced during minimization are somewhat similar to
the "smash" phase, where we indeed try to produce more derivative
inputs from the new input. The concern is that if we pile lots of
inputs into the triage queue and then the VM crashes, we lose all of
that (including potentially part of initial corpus). Maybe it makes
sense to introduce 2 triage queues (primary and secondary) and add
minimization results (and maybe inputs produced during smash) into the
secondary one.
Or maybe a more fundamental solution is to send inputs to the manager
sooner (e.g. before minimization) and then it will distribute them for
minimization and smashing later.
> Daimeng (Desmond) Wang
Daimeng Wang
Feb 17, 2020, 3:01:56 PM2/17/20
to Dmitry Vyukov, Daimeng Wang, Zhiyun Qian, syzkaller
I agree. We did try to sync the triage tasks with the manager but the overhead is a little bit too much. In addition, it might be argued that the triage queue is only long in the early stages of fuzzing. At this point even if we lost these triages due to VM crashing, it might not be too hard for Syzkaller to reproduce them. In the later stages, on the other hand, task selection will give triage absolute priority just like the original strategy.
--
You received this message because you are subscribed to the Google Groups "syzkaller" group.
To unsubscribe from this group and stop receiving emails from it, send an email to syzkaller+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/syzkaller/CACT4Y%2BY6hFRmE4RZvAKZzE6JYjQD5dHZpvE3ZFRcJzQkqvSF7Q%40mail.gmail.com.
aen...@gmail.com
Feb 20, 2020, 10:27:33 PM2/20/20
to syzkaller
Hi Daimeng,
在 2020年2月12日星期三 UTC+8上午11:39:57，Daimeng Wang写道：
It sounds interesting! I was intensely curious to know more about it!
When will you share the preprint paper and code?
Thanks a lot!
在 2020年2月12日星期三 UTC+8上午11:39:57，Daimeng Wang写道：
Daimeng Wang
Feb 24, 2020, 12:49:14 AM2/24/20
to aen...@gmail.com, syzkaller
I am currently cleaning up my code and will create a pull request soon.
--
You received this message because you are subscribed to the Google Groups "syzkaller" group.
To unsubscribe from this group and stop receiving emails from it, send an email to syzkaller+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/syzkaller/c6acaaa4-2719-4474-91a4-81a1589db3c7%40googlegroups.com.
Daimeng (Desmond) Wang
Reply all
Reply to author
Forward
0 new messages