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

[Alexander Bulekov]

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