syzbot bisection accuracy on Linux kernel

[Eric Biggers]

FYI, of the 97 open syzbot reports against upstream Linux that were bisected to
a single commit, I think 52 of the bisection results are probably correct, and
45 are probably incorrect. I.e., about 53% accuracy.

It would be really helpful to improve this -- ideally by producing more good
results, but even just not sending as many bad results would be an improvement.
It seems the biggest issues that cause bad results are (1) not running the
reproducer enough times for hard-to-reproduce bugs, and (2) treating every
single crash as the desired one even when there are strong indicators it's not.

These are the bugs I've marked as bisected incorrectly
(it's usually fairly obvious):

BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low! (https://syzkaller.appspot.com/bug?id=381cb436fe60dc03d7fd2a092b46d7f09542a72a)
BUG: MAX_STACK_TRACE_ENTRIES too low! (2) (https://syzkaller.appspot.com/bug?id=55fb46b50c9b08dfe294667f184db5840f9cdecc)
BUG: soft lockup in kvm_vm_ioctl (https://syzkaller.appspot.com/bug?id=60ff874c7b251129e028c90b5d4926c5b3fccbe2)
BUG: soft lockup in kvm_vm_release (https://syzkaller.appspot.com/bug?id=eff432af8dea9e5e0d14acdae66b51ef49ccb5ee)
BUG: unable to handle kernel paging request in slhc_free (https://syzkaller.appspot.com/bug?id=ca98e815aabdd1494eacb048d649ffd4fc916e2e)
INFO: rcu detected stall in __perf_sw_event (https://syzkaller.appspot.com/bug?id=c97097e0408c6c6f60ac89b78faaf0e42663cbac)
INFO: rcu detected stall in sys_sendfile64 (2) (https://syzkaller.appspot.com/bug?id=6a6553c3d34bb00172b5cbd32f4912151b6133dc)
INFO: task hung in do_exit (https://syzkaller.appspot.com/bug?id=3e6c42e24155e5f0125368e609bee32f2b7394fe)
INFO: task hung in evdev_release (https://syzkaller.appspot.com/bug?id=ebbbff1dcac574b81f9fd5e07100a4879e5bf53d)
INFO: task hung in process_measurement (https://syzkaller.appspot.com/bug?id=623c2e176b9d80b1872e7559e5b823b1ec4911b6)
INFO: task syz-executor can't die for more than 143 seconds. (https://syzkaller.appspot.com/bug?id=a0e3436829698d5824231251fad9d8e998f94f5e)
INFO: trying to register non-static key in icmp_send (https://syzkaller.appspot.com/bug?id=ea46a31df5253b18deb1e18c429c1483b111cbce)
KASAN: slab-out-of-bounds Read in _decode_session6 (2) (https://syzkaller.appspot.com/bug?id=afc5098c1a0cb7cda8aa7fdb402153ff24fcf31c)
KASAN: slab-out-of-bounds Read in bacpy (https://syzkaller.appspot.com/bug?id=3acd1155d48a5acc5d76711568b04926945a6885)
KASAN: slab-out-of-bounds Read in hci_event_packet (https://syzkaller.appspot.com/bug?id=d708485af9edc3af35f3b4d554e827c6c8bf6b0f)
KASAN: use-after-free Read in addr_handler (https://syzkaller.appspot.com/bug?id=a9796acbdecc1b2ba927578917755899c63c48af)
KASAN: use-after-free Read in crypto_gcm_init_common (https://syzkaller.appspot.com/bug?id=979d00397272e11bc334ec842074d314bde41b90)
KASAN: use-after-free Read in kfree_skb (3) (https://syzkaller.appspot.com/bug?id=db842327c655eab57b1755f661f1ab677d94e0bb)
KASAN: use-after-free Read in refcount_sub_and_test_checked (2) (https://syzkaller.appspot.com/bug?id=eaf7abde8e5497bbf7403a3d2afb9226005362cf)
KASAN: use-after-free Read in sk_psock_unlink (https://syzkaller.appspot.com/bug?id=d691981726208716cc7aec231fb915e27763d662)
KASAN: use-after-free Write in __vb2_cleanup_fileio (https://syzkaller.appspot.com/bug?id=0264f823322ea8600fbe3fb7e9e016569ca542d8)
KASAN: use-after-free Write in hci_sock_release (https://syzkaller.appspot.com/bug?id=47befb59c610a69f024db20b927dea80c88fc045)
WARNING in bpf_jit_free (https://syzkaller.appspot.com/bug?id=d04f9c2ec11ab2678f7427795ff5170cb9eb2220)
WARNING in bpf_prog_kallsyms_add (https://syzkaller.appspot.com/bug?id=b658eb696c8279d9951a4ceea79efba8a1d12467)
WARNING in cgroup_exit (https://syzkaller.appspot.com/bug?id=d9f3b78e04b3741b3d61be12bd1782581963afe5)
WARNING in debug_check_no_obj_freed (https://syzkaller.appspot.com/bug?id=83687867d4a435fce7c6045b34425b1cfb3bf2d6)
WARNING in dma_buf_vunmap (https://syzkaller.appspot.com/bug?id=163388d1fb80146cd3ba22a11a5a1995c3eaaafe)
WARNING in hsr_addr_subst_dest (https://syzkaller.appspot.com/bug?id=924b5574f42ebeddc94fad06f2fa329b199d58d3)
WARNING in hsr_forward_skb (https://syzkaller.appspot.com/bug?id=13de4605e86ebcf39093017dc255aa0fd6c2f12d)
WARNING in kvm_arch_vcpu_ioctl_run (3) (https://syzkaller.appspot.com/bug?id=4d7de0e6a195b6a5ffef01d2776e737a52c7de60)
WARNING in rcu_check_gp_start_stall (https://syzkaller.appspot.com/bug?id=0c963236471bc9561fd3b38da03cd09482e90c72)
WARNING in request_end (https://syzkaller.appspot.com/bug?id=2318b559efec9fda6c77bd5c3d57c8fc3255d922)
WARNING in untrack_pfn (https://syzkaller.appspot.com/bug?id=149d7751733001d683eca36df500722bff6cc350)
WARNING: ODEBUG bug in __do_softirq (https://syzkaller.appspot.com/bug?id=26c9593893aa8625f556867ea71649010a07e74d)
WARNING: bad unlock balance detected! (3) (https://syzkaller.appspot.com/bug?id=342beb2b368a43cbb6533c00d758759b10fbc8d8)
WARNING: locking bug in inet_autobind (https://syzkaller.appspot.com/bug?id=a7d678fba80c34b5770cc1b5638b8a2709ae9f3f)
WARNING: refcount bug in igmp_start_timer (https://syzkaller.appspot.com/bug?id=667f1bd0ab632a49ca3daaa6967cc023b1c5b0c6)
general protection fault in __bfs (2) (https://syzkaller.appspot.com/bug?id=b962be759f1c186a76fe71ba99eda6e23708dcd9)
general protection fault in __smc_diag_dump (https://syzkaller.appspot.com/bug?id=4d03c161c6cc140b6234f534c6009d8c9da39f6c)
general protection fault in kvm_pv_send_ipi (https://syzkaller.appspot.com/bug?id=f8d5004f6f749ecefaa2843e429848795cc2023f)
general protection fault in put_pid (https://syzkaller.appspot.com/bug?id=bff65b0242612090a2897a740476f20fdc765998)
general protection fault in requeue_rx_msgs (https://syzkaller.appspot.com/bug?id=da9b672629747f28e76eca9949696c410cb75d7b)
general protection fault in skb_put (https://syzkaller.appspot.com/bug?id=9abc0fdcdea0effb7b27984dbc1f336155cdad3f)
possible deadlock in __generic_file_fsync (https://syzkaller.appspot.com/bug?id=82425f52b09843fe8da85de87f9d590920bbe1fe)
possible deadlock in flush_workqueue (2) (https://syzkaller.appspot.com/bug?id=7f79b2bbcf1a6057a25d5557562141d90624d5da)

[Dmitry Vyukov]

On Tue, Jun 25, 2019 at 8:59 AM Eric Biggers <ebig...@kernel.org> wrote:
>
> FYI, of the 97 open syzbot reports against upstream Linux that were bisected to
> a single commit, I think 52 of the bisection results are probably correct, and
> 45 are probably incorrect. I.e., about 53% accuracy.
>
> It would be really helpful to improve this -- ideally by producing more good
> results, but even just not sending as many bad results would be an improvement.
> It seems the biggest issues that cause bad results are (1) not running the
> reproducer enough times for hard-to-reproduce bugs, and (2) treating every
> single crash as the desired one even when there are strong indicators it's not.
>
> These are the bugs I've marked as bisected incorrectly
> (it's usually fairly obvious):

Hi Eric,

I agree the results are not good and improving it would be useful.

You have seem this, right?
https://groups.google.com/forum/#!msg/syzkaller/sR8aAXaWEF4/tTWYRgvmAwAJ
https://docs.google.com/spreadsheets/d/1WdBAN54-csaZpD3LgmTcIMR7NDFuQoOZZqPZ-CUqQgA/edit#gid=348315157
https://docs.google.com/spreadsheets/d/1WdBAN54-csaZpD3LgmTcIMR7NDFuQoOZZqPZ-CUqQgA/edit#gid=0

My computed accuracy is 52.38% :)

I am trying to collect something actionable here:
https://github.com/google/syzkaller/issues/1051

There needs to be some tuning around number of runs. Though, any idea
have some immediate counter-examples. E.g. doing more runs will
trigger more unrelated bugs, and unrelated bugs is the major source of
incorrect results. I also wasn't able to figure out what exactly can
be done with crash identification. I see that more than half of
crashes have different manifestations, either in time or in space.
I've seen counter-examples to just any idea I could come up with. At
this point we some concrete algorithmic ideas baked by some data.