The success rate of cause bisection

[David Lee]

Hi,

I remember I ever saw some slides by Dmitry Vyukov, but forget the link of slides. The slide said that the success rate of cause bisection is 50% and 70% for latest releases. So why the success rate is so low?

Thanks

[Dmitry Vyukov]

Hi David,

Here is detailed info:
https://github.com/google/syzkaller/issues/1051#issuecomment-477264585

[David Lee]

Hi Dmitry,

Thanks for your reply.

But I do not understand "the crash has multiple manifestations (on the same commit or on different commits)".

The manifestations of the crash are crash log or the crash type(OOB,UAF,WARN)?

[Dmitry Vyukov]

On Fri, May 8, 2020 at 7:24 AM David Lee <sayni...@gmail.com> wrote:
>
> Hi Dmitry,
> Thanks for your reply.
> But I do not understand "the crash has multiple manifestations (on the same commit or on different commits)".
> The manifestations of the crash are crash log or the crash type(OOB,UAF,WARN)?

syzkaller uses bug title as bug identity (as extracted by pkg/report)
that's what you see in the bisection log

> On Tuesday, May 5, 2020 at 11:50:32 PM UTC-7, Dmitry Vyukov wrote:
>>
>> On Wed, May 6, 2020 at 8:45 AM David Lee <sayni...@gmail.com> wrote:
>> >
>> > Hi,
>> >
>> > I remember I ever saw some slides by Dmitry Vyukov, but forget the link of slides. The slide said that the success rate of cause bisection is 50% and 70% for latest releases. So why the success rate is so low?
>> > Thanks
>>
>> Hi David,
>>
>> Here is detailed info:
>> https://github.com/google/syzkaller/issues/1051#issuecomment-477264585
>

> --
> 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/6437c62a-90ee-46f3-84eb-b80a2ca30e3f%40googlegroups.com.

[David Lee]

Thanks for your reply.

But as https://github.com/google/syzkaller/blob/master/docs/syzbot.md#bisection and what you said in another thread. syzkaller does not identity bug in the process of bisecting. Only if there is a crash, syzkaller thinks the bug exists. This is also why unrelated bug cause incorrect cause bisection.

Is there something I understand wrongly?

On Friday, May 8, 2020 at 12:15:03 AM UTC-7, Dmitry Vyukov wrote:

On Fri, May 8, 2020 at 7:24 AM David Lee <sayni...@gmail.com> wrote:
>
> Hi Dmitry,
> Thanks for your reply.
> But I do not understand "the crash has multiple manifestations (on the same commit or on different commits)".
> The manifestations of the crash are crash log or the crash type(OOB,UAF,WARN)?

syzkaller uses bug title as bug identity (as extracted by pkg/report)
that's what you see in the bisection log


> On Tuesday, May 5, 2020 at 11:50:32 PM UTC-7, Dmitry Vyukov wrote:
>>
>> On Wed, May 6, 2020 at 8:45 AM David Lee <sayni...@gmail.com> wrote:
>> >
>> > Hi,
>> >
>> > I remember I ever saw some slides by Dmitry Vyukov, but forget the link of slides. The slide said that the success rate of cause bisection is 50% and 70% for latest releases. So why the success rate is so low?
>> > Thanks
>>
>> Hi David,
>>
>> Here is detailed info:
>> https://github.com/google/syzkaller/issues/1051#issuecomment-477264585
>
> --
> 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 syzk...@googlegroups.com.

[Dmitry Vyukov]

On Fri, May 8, 2020 at 9:19 AM David Lee <sayni...@gmail.com> wrote:
>
> Thanks for your reply.
> But as https://github.com/google/syzkaller/blob/master/docs/syzbot.md#bisection and what you said in another thread. syzkaller does not identity bug in the process of bisecting. Only if there is a crash, syzkaller thinks the bug exists. This is also why unrelated bug cause incorrect cause bisection.
> Is there something I understand wrongly?

Yes, that's correct.
During the bisection analysis I looked at the logs manually and marked
some with "different manifestations" just for understanding/research
purposes.

> On Friday, May 8, 2020 at 12:15:03 AM UTC-7, Dmitry Vyukov wrote:
>>
>> On Fri, May 8, 2020 at 7:24 AM David Lee <sayni...@gmail.com> wrote:
>> >
>> > Hi Dmitry,
>> > Thanks for your reply.
>> > But I do not understand "the crash has multiple manifestations (on the same commit or on different commits)".
>> > The manifestations of the crash are crash log or the crash type(OOB,UAF,WARN)?
>>
>> syzkaller uses bug title as bug identity (as extracted by pkg/report)
>> that's what you see in the bisection log
>>
>>
>> > On Tuesday, May 5, 2020 at 11:50:32 PM UTC-7, Dmitry Vyukov wrote:
>> >>
>> >> On Wed, May 6, 2020 at 8:45 AM David Lee <sayni...@gmail.com> wrote:
>> >> >
>> >> > Hi,
>> >> >
>> >> > I remember I ever saw some slides by Dmitry Vyukov, but forget the link of slides. The slide said that the success rate of cause bisection is 50% and 70% for latest releases. So why the success rate is so low?
>> >> > Thanks
>> >>
>> >> Hi David,
>> >>
>> >> Here is detailed info:
>> >> https://github.com/google/syzkaller/issues/1051#issuecomment-477264585
>> >
>> > --
>> > 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 syzk...@googlegroups.com.
>> > To view this discussion on the web visit https://groups.google.com/d/msgid/syzkaller/6437c62a-90ee-46f3-84eb-b80a2ca30e3f%40googlegroups.com.
>
> --
> 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/3046a43f-7e87-41bc-aeab-737addc747db%40googlegroups.com.

[Dmitry Vyukov]

On Fri, May 8, 2020 at 9:39 AM David Lee <sayni...@gmail.com> wrote:
>
> Thanks for your reply.

> So the crash has multiple manifestations should not thought as a reason why the accuracy of cause bisection is not satisfied.As there is crash, no matter what type the crash is, syzbot thinks the bug exists.
> Is my understanding right?

Yes.

Significant part of bugs having multiple manifestations is one of the
reasons why trying to understand if you are seeing the same bug or not
is infeasible.
Say, you see "use-after-free in foo" and then you see "use-after-free
in bar". It looks like completely different bug, but it may be just
that the function was renamed.

[Dmitry Vyukov]

On Sun, May 10, 2020 at 9:07 AM David Lee <sayni...@gmail.com> wrote:
>
> Hi Dmitry,
>

> I am supposed to reply https://groups.google.com/forum/#!topic/syzkaller/hOWo2XEn0EU with the below contents. But I found it was deleted automatically after I replied.
> Here is what I want to say in that thread:
>>
>> Thanks for you reply. It's very helpful.
>> I wonder if there is new update for the improvment of cause bisection. Are you still working on it?

Hi David,

No, I am not actively working on it now.
There is this recent PR that should improve bisection quality, though:
https://github.com/google/syzkaller/pull/1689

> Are there other documents about this, besides the above link?

No, there are no documents.
You may search the mailing list and issue tracker for bisection and
pkg/bisect, though.

>> Also you said that hard to reproduce bugs contributed to 46% of incorrect results. What are the main reasons that bugs are hard to reproduce?

Racer, non-determinism, global state, interaction between processes, etc.

[David Lee]

Thanks for your reply.

So the crash has multiple manifestations should not thought as a reason why the accuracy of cause bisection is not satisfied.As there is crash, no matter what type the crash is, syzbot thinks the bug exists.

Is my understanding right?

> To unsubscribe from this group and stop receiving emails from it, send an email to syzkaller+unsubscribe@googlegroups.com.

[David Lee]

Hi Damitry,

Thanks.

I have other questions now:

1,  https://docs.google.com/spreadsheets/d/1WdBAN54-csaZpD3LgmTcIMR7NDFuQoOZZqPZ-CUqQgA/edit#gid=0 , in final crash column, there are some empty cell or no output from test machine. I thought the meaning of "final crash" is the crash before cause commit. After final crash, PoC does not take effect on next commit, which is the casue commit. In this case, why are there some empty cell or no output from test machine?

2, What are the main reasons for multiple manifestations? My guess is that the root cause of a bug is the same, but there are serval vulnerability path, in other words, there are multiple impacts of the bug. Version differences or system state cause the PoC execute different path in kernel. So the crash log is different.

3,Previously, you said syzkaller only run PoC once in the process of finding cause commit, but in https://syzkaller.appspot.com/x/bisect.txt?x=1232b037200000, it seems that syzkaller runs PoC ten times for  each commit.

4,Does syzbot provide .config file for each commit in the bisect log? I want to run PoC on commits in bisect log to understand why there are multiple manifestations for the same bug.

Thanks

[Dmitry Vyukov]

On Mon, May 11, 2020 at 9:23 AM David Lee <sayni...@gmail.com> wrote:
>
> Hi Damitry,
>
> Thanks.
>
>
> I have other questions now:
>
> 1, https://docs.google.com/spreadsheets/d/1WdBAN54-csaZpD3LgmTcIMR7NDFuQoOZZqPZ-CUqQgA/edit#gid=0 , in final crash column, there are some empty cell or no output from test machine. I thought the meaning of "final crash" is the crash before cause commit. After final crash, PoC does not take effect on next commit, which is the casue commit. In this case, why are there some empty cell or no output from test machine?

I don't remember, maybe I just forgot to add it.
But "no output" is considered a crash. So that's legit final crash.

> 2, What are the main reasons for multiple manifestations? My guess is that the root cause of a bug is the same, but there are serval vulnerability path, in other words, there are multiple impacts of the bug. Version differences or system state cause the PoC execute different path in kernel. So the crash log is different.

I can hypothesize that it's again races.
Or for different manifestations on different commits, the function may
be renamed, code changes, or simply the debugging tool is changed to
produce different output.
I did not collect a more precise breakdown of reasons.

> 3,Previously, you said syzkaller only run PoC once in the process of finding cause commit, but in https://syzkaller.appspot.com/x/bisect.txt?x=1232b037200000, it seems that syzkaller runs PoC ten times for each commit.

It runs it 10 times.
Maybe I meant something else. I can't find where I said anything like
this. The only match for "once" in this thread is your question.

> 4,Does syzbot provide .config file for each commit in the bisect log? I want to run PoC on commits in bisect log to understand why there are multiple manifestations for the same bug.

It does not provide it. But it's mostly the original config after
'make oldconfig' and few changes that pkg/vcs does.
It should be possible to reconstruct it manually.

> --
> 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/6d9e6a7e-d1f4-4b9e-ba5f-a5a7edc2b4fa%40googlegroups.com.

[David Lee]

Sorry to post in this thread after one month.

But when I consider this problem recently, I think there may be another reason why the cause bisection fails to identify which commit introduce the vulnerability:

as PoCs are composed of system calls, and the implementation details of system calls with the same arguments may change between different Linux kernels, then kernel codes executed by the PoC may be different in different Linux kernels, so the PoC may fail to crash the kernel even the vulnerability exists in the kernel. 

For example, there are two system calls: sys_call1 and sys_call2 in a PoC of out-of-bounds write bug. sys_call1 calculates a global variable, then the global variable is used in sys_call2 as an index to access an array to trigger an OOB bug.

But if in a Linux kernel, the calculation of the global variable is changed, then even if we pass the same parameters to sys_call1, we can not get the out-of-bounds index. To trigger the bug, we need to change the parameter in sys_call1 to a new value according to the new calculation rules in sys_call1.

But it's just my hypothesis, I can not find an example. Also in your char https://docs.google.com/spreadsheets/d/1WdBAN54-csaZpD3LgmTcIMR7NDFuQoOZZqPZ-CUqQgA/edit#gid=348315157, there is no example like this.

From your understanding and experience in bugs finding, is this hypothesis possible? is there a PoC that can not work due to system call changes?

Thanks.

> To unsubscribe from this group and stop receiving emails from it, send an email to syzk...@googlegroups.com.

[Dmitry Vyukov]

On Mon, Jun 15, 2020 at 12:45 AM David Lee <sayni...@gmail.com> wrote:
>
> Sorry to post in this thread after one month.
> But when I consider this problem recently, I think there may be another reason why the cause bisection fails to identify which commit introduce the vulnerability:
> as PoCs are composed of system calls, and the implementation details of system calls with the same arguments may change between different Linux kernels, then kernel codes executed by the PoC may be different in different Linux kernels, so the PoC may fail to crash the kernel even the vulnerability exists in the kernel.
> For example, there are two system calls: sys_call1 and sys_call2 in a PoC of out-of-bounds write bug. sys_call1 calculates a global variable, then the global variable is used in sys_call2 as an index to access an array to trigger an OOB bug.
> But if in a Linux kernel, the calculation of the global variable is changed, then even if we pass the same parameters to sys_call1, we can not get the out-of-bounds index. To trigger the bug, we need to change the parameter in sys_call1 to a new value according to the new calculation rules in sys_call1.
> But it's just my hypothesis, I can not find an example. Also in your char https://docs.google.com/spreadsheets/d/1WdBAN54-csaZpD3LgmTcIMR7NDFuQoOZZqPZ-CUqQgA/edit#gid=348315157, there is no example like this.
> From your understanding and experience in bugs finding, is this hypothesis possible? is there a PoC that can not work due to system call changes?
> Thanks.

Yes, I think this happens.
In particular we are seeing this for reproducers that involve fault
injection. The fault injection needs to happen in the very particular
kmalloc to trigger the bug, so just adding or removing a kmalloc call
in involved parts of the kernel will break the reproducer.

> 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/a77cb7f2-0abe-4e4f-99cd-25c16424a37bo%40googlegroups.com.