[2/4] fuzz: split QTest writes from the rightmost byte

Currently, we split the write commands' data from the middle. If it does not
work, try to move the pivot "left" and retry until there is no space left.
But, this is complete for ram writes but not for IO writes.

For example, there is an IO write command:

  write addr uuxxxxuu

u is the unnecessary byte for the crash. Unlike ram write commands, in most
case, a split IO write won't trigger the same crash, So if we split from the
middle, we will get:

  write addr uu (will be removed in next round)
  write addr xxxxuu

For xxxxuu, since split it from the middle and retry to the leftmost byte
won't get the same crash, we will be stopped from removing the last two
bytes.

Therefore, we should split QTest writes from the rightmost byte.

Tested with Bug 1908062. Refined vs. Original result:

outl 0xcf8 0x8000081c            outl 0xcf8 0x8000081c
outb 0xcfc 0xc3                  outb 0xcfc 0xc3
outl 0xcf8 0x8000082f            outl 0xcf8 0x8000082f
outl 0xcf8 0x80000804            outl 0xcf8 0x80000804
outl 0xcfc 0x9b2765be            outl 0xcfc 0x9b2765be
write 0xc300001024 0x2 0x0055    write 0xc300001024 0x2 0x0055
write 0xc300001028 0x1 0x5a      write 0xc300001028 0x1 0x5a
write 0xc30000101c 0x1 0x01      write 0xc30000101c 0x1 0x01
writel 0xc30000100c 0x2a6f6c63   writel 0xc30000100c 0x2a6f6c63
write 0xc300001018 0x1 0xa4  <-- write 0xc300001016 0x3 0xa4a4a4
write 0x5c 0x1 0x19              write 0x5c 0x1 0x19
write 0xc300003002 0x1 0x8a      write 0xc300003002 0x1 0x8a

Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

Qiuhao Li <Qiuhao.Li@outlook.com> writes:

> Currently, we split the write commands' data from the middle. If it does not
> work, try to move the pivot "left" and retry until there is no space left.
> But, this is complete for ram writes but not for IO writes.
>
> For example, there is an IO write command:
>
>   write addr uuxxxxuu
>
> u is the unnecessary byte for the crash. Unlike ram write commands, in most
> case, a split IO write won't trigger the same crash, So if we split from the
> middle, we will get:
>
>   write addr uu (will be removed in next round)
>   write addr xxxxuu
>
> For xxxxuu, since split it from the middle and retry to the leftmost byte
> won't get the same crash, we will be stopped from removing the last two
> bytes.
>

Good catch! I missed this case.

> Therefore, we should split QTest writes from the rightmost byte.
>
> Tested with Bug 1908062. Refined vs. Original result:
>
> outl 0xcf8 0x8000081c            outl 0xcf8 0x8000081c
> outb 0xcfc 0xc3                  outb 0xcfc 0xc3
> outl 0xcf8 0x8000082f            outl 0xcf8 0x8000082f
> outl 0xcf8 0x80000804            outl 0xcf8 0x80000804
> outl 0xcfc 0x9b2765be            outl 0xcfc 0x9b2765be
> write 0xc300001024 0x2 0x0055    write 0xc300001024 0x2 0x0055
> write 0xc300001028 0x1 0x5a      write 0xc300001028 0x1 0x5a
> write 0xc30000101c 0x1 0x01      write 0xc30000101c 0x1 0x01
> writel 0xc30000100c 0x2a6f6c63   writel 0xc30000100c 0x2a6f6c63
> write 0xc300001018 0x1 0xa4  <-- write 0xc300001016 0x3 0xa4a4a4
> write 0x5c 0x1 0x19              write 0x5c 0x1 0x19
> write 0xc300003002 0x1 0x8a      write 0xc300003002 0x1 0x8a
>

Can we wrap-around to the right when we hit the end of the input on the
left, instead of going byte-by-byte? Otherwise, i think we would need
O(n) operations to reach the leftmost in a write, rather than O(logN).

i.e.
xxxxuu ->
xxx xuu ->
xx xxuu ->
x xxxuu ->
xxxxu u

I think the case where we would need to wrap around the entire input
usually happens for smaller writes, so it shouldn't slow the minimizer
down too much

-Alex

> Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> ---
>  scripts/oss-fuzz/minimize_qtest_trace.py | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
> index d3b09e6567..855c3bcb54 100755
> --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> @@ -140,7 +140,7 @@ def minimize_trace(inpath, outpath):
>
>          # 3.) If it is a qtest write command: write addr len data, try to split
>          # it into two separate write commands. If splitting the write down the
> -        # middle does not work, try to move the pivot "left" and retry, until
> +        # rightmost does not work, try to move the pivot "left" and retry, until
>          # there is no space left. The idea is to prune unneccessary bytes from
>          # long writes, while accommodating arbitrary MemoryRegion access sizes
>          # and alignments.
> @@ -149,7 +149,7 @@ def minimize_trace(inpath, outpath):
>              length = int(newtrace[i].split()[2], 16)
>              data = newtrace[i].split()[3][2:]
>              if length > 1:
> -                leftlength = int(length/2)
> +                leftlength = length - 1
>                  rightlength = length - leftlength
>                  newtrace.insert(i+1, "")
>                  while leftlength > 0:
> --
> 2.25.1

On Mon, 2020-12-21 at 15:01 -0500, Alexander Bulekov wrote:
> Qiuhao Li <Qiuhao.Li@outlook.com> writes:
> 
> > Currently, we split the write commands' data from the middle. If it
> > does not
> > work, try to move the pivot "left" and retry until there is no
> > space left.
> > But, this is complete for ram writes but not for IO writes.
> > 
> > For example, there is an IO write command:
> > 
> >   write addr uuxxxxuu
> > 
> > u is the unnecessary byte for the crash. Unlike ram write commands,
> > in most
> > case, a split IO write won't trigger the same crash, So if we split
> > from the
> > middle, we will get:
> > 
> >   write addr uu (will be removed in next round)
> >   write addr xxxxuu
> > 
> > For xxxxuu, since split it from the middle and retry to the
> > leftmost byte
> > won't get the same crash, we will be stopped from removing the last
> > two
> > bytes.
> > 
> 
> Good catch! I missed this case.
> 
> > Therefore, we should split QTest writes from the rightmost byte.
> > 
> > Tested with Bug 1908062. Refined vs. Original result:
> > 
> > outl 0xcf8 0x8000081c            outl 0xcf8 0x8000081c
> > outb 0xcfc 0xc3                  outb 0xcfc 0xc3
> > outl 0xcf8 0x8000082f            outl 0xcf8 0x8000082f
> > outl 0xcf8 0x80000804            outl 0xcf8 0x80000804
> > outl 0xcfc 0x9b2765be            outl 0xcfc 0x9b2765be
> > write 0xc300001024 0x2 0x0055    write 0xc300001024 0x2 0x0055
> > write 0xc300001028 0x1 0x5a      write 0xc300001028 0x1 0x5a
> > write 0xc30000101c 0x1 0x01      write 0xc30000101c 0x1 0x01
> > writel 0xc30000100c 0x2a6f6c63   writel 0xc30000100c 0x2a6f6c63
> > write 0xc300001018 0x1 0xa4  <-- write 0xc300001016 0x3 0xa4a4a4
> > write 0x5c 0x1 0x19              write 0x5c 0x1 0x19
> > write 0xc300003002 0x1 0x8a      write 0xc300003002 0x1 0x8a
> > 
> 
> Can we wrap-around to the right when we hit the end of the input on
> the
> left, instead of going byte-by-byte? Otherwise, i think we would need
> O(n) operations to reach the leftmost in a write, rather than
> O(logN).
> 
> i.e.
> xxxxuu ->
> xxx xuu ->
> xx xxuu ->
> x xxxuu ->
> xxxxu u
> 
> I think the case where we would need to wrap around the entire input
> usually happens for smaller writes, so it shouldn't slow the
> minimizer
> down too much
> 
> -Alex

If we want to achieve O(logN), should we change the step size besides
using a wrap-around strategy?

@@ -164,8 +164,8 @@ def minimize_trace(inpath, outpath):
                     if check_if_trace_crashes(newtrace, outpath):
                         break
                     else:
-                        leftlength -= 1
-                        rightlength += 1
+                        leftlength -= leftlength/2
+                        rightlength = length - leftlength


And how about using a binary search directly? Like:


        binary_search(newtrace, i,leftlen=1, len)

               base case: leftlen >= len


                        xxxxuu len=6
                             +
                             |
                             +
                      xxx,xuu  (1+6)/2=3
                             +
              +--------------+-------------+
              |                            |
              +                            +
       xx,xxuu (1+3)/2=2            xxxx,uu (3+6)/2=4
              +                       success
              |
       +------+--------------+
       |                     |
       |                     |
       +                     +
x,xxxuu (1+2)/2=1     xx,xxuu (2+3)/2=2
     base case            base case
> 
> > Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> > ---
> >  scripts/oss-fuzz/minimize_qtest_trace.py | 4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> > 
> > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > index d3b09e6567..855c3bcb54 100755
> > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > @@ -140,7 +140,7 @@ def minimize_trace(inpath, outpath):
> > 
> >          # 3.) If it is a qtest write command: write addr len data,
> > try to split
> >          # it into two separate write commands. If splitting the
> > write down the
> > -        # middle does not work, try to move the pivot "left" and
> > retry, until
> > +        # rightmost does not work, try to move the pivot "left"
> > and retry, until
> >          # there is no space left. The idea is to prune
> > unneccessary bytes from
> >          # long writes, while accommodating arbitrary MemoryRegion
> > access sizes
> >          # and alignments.
> > @@ -149,7 +149,7 @@ def minimize_trace(inpath, outpath):
> >              length = int(newtrace[i].split()[2], 16)
> >              data = newtrace[i].split()[3][2:]
> >              if length > 1:
> > -                leftlength = int(length/2)
> > +                leftlength = length - 1
> >                  rightlength = length - leftlength
> >                  newtrace.insert(i+1, "")
> >                  while leftlength > 0:
> > --
> > 2.25.1