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

[Qiuhao Li]

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