[PATCH 0/4] improve crash case minimization

[PATCH 0/4] improve crash case minimization

[Qiuhao Li]

Extend and refine the crash case minimization process.

I forgot to cc some reviewers in the last patch, so I merge it as the
first on in this patch series.

Qiuhao Li (4):
  fuzz: refine crash detection mechanism
  fuzz: split QTest writes from the rightmost byte
  fuzz: setting bits in operand of out/write to zero
  fuzz: delay IO until they can't trigger the crash

 scripts/oss-fuzz/minimize_qtest_trace.py | 126 ++++++++++++++++++++---
 1 file changed, 110 insertions(+), 16 deletions(-)

-- 
2.25.1

[PATCH 1/4] fuzz: refine crash detection mechanism

[Qiuhao Li]

The original crash detection method is to fork a process to test our new
trace input. If the child process exits in time and the second-to-last line
is the same as the first crash, we think it is a crash triggered by the same
bug. However, in some situations, it doesn't work since it is a
hardcoded-offset string comparison.

For example, suppose an assertion failure makes the crash. In that case, the
second-to-last line will be 'timeout: the monitored command dumped core',
which doesn't contain any information about the assertion failure like where
it happened or the assertion statement. This may lead to a minimized input
triggers assertion failure but may indicate another bug. As for some
sanitizers' crashes, the direct string comparison may stop us from getting a
smaller input, since they may have a different leaf stack frame.

Perhaps we can detect crashes using both precise output string comparison
and rough pattern string match and info the user when the trace input
triggers different but a seminar output.

Tested:
Assertion failure, https://bugs.launchpad.net/qemu/+bug/1908062
AddressSanitizer, https://bugs.launchpad.net/qemu/+bug/1907497
Trace input that doesn't crash
Trace input that crashes Qtest

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

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5e405a0d5f..d3b09e6567 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -10,11 +10,16 @@ import os
 import subprocess
 import time
 import struct
+import re
 
 QEMU_ARGS = None
 QEMU_PATH = None
 TIMEOUT = 5
-CRASH_TOKEN = None
+
+crash_patterns = ("Assertion.+failed",
+                  "SUMMARY.+Sanitizer")
+crash_pattern = None
+crash_string = None
 
 write_suffix_lookup = {"b": (1, "B"),
                        "w": (2, "H"),
@@ -24,13 +29,12 @@ write_suffix_lookup = {"b": (1, "B"),
 def usage():
     sys.exit("""\
 Usage: QEMU_PATH="/path/to/qemu" QEMU_ARGS="args" {} input_trace output_trace
-By default, will try to use the second-to-last line in the output to identify
-whether the crash occred. Optionally, manually set a string that idenitifes the
-crash by setting CRASH_TOKEN=
+By default, we will try to search predefined crash patterns through the
+tracing output to see whether the crash occred. Optionally, manually set a
+string that idenitifes the crash by setting CRASH_PATTERN=
 """.format((sys.argv[0])))
 
 def check_if_trace_crashes(trace, path):
-    global CRASH_TOKEN
     with open(path, "w") as tracefile:
         tracefile.write("".join(trace))
 
@@ -42,17 +46,47 @@ def check_if_trace_crashes(trace, path):
                           shell=True,
                           stdin=subprocess.PIPE,
                           stdout=subprocess.PIPE)
+    if rc.returncode == 137:    # Timed Out
+        return False
+
     stdo = rc.communicate()[0]
     output = stdo.decode('unicode_escape')
-    if rc.returncode == 137:    # Timed Out
-        return False
-    if len(output.splitlines()) < 2:
+    output_lines = output.splitlines()
+    # Usually we care about the summary info in the last few lines, reverse.
+    output_lines.reverse()
+
+    global crash_pattern, crash_patterns, crash_string
+    if crash_pattern is None: # Initialization
+        for line in output_lines:
+            for c in crash_patterns:
+                if re.search(c, line) is not None:
+                    crash_pattern = c
+                    crash_string = line
+                    print("Identifying crash pattern by this string: ",\
+                          crash_string)
+                    print("Using regex pattern: ", crash_pattern)
+                    return True
+        print("Failed to initialize crash pattern: no match.")
         return False
 
-    if CRASH_TOKEN is None:
-        CRASH_TOKEN = output.splitlines()[-2]
+    # First, we search exactly the previous crash string.
+    for line in output_lines:
+        if crash_string == line:
+            return True
+
+    # Then we decide whether a similar (same pattern) crash happened.
+    # Slower now :(
+    for line in output_lines:
+        if re.search(crash_pattern, line) is not None:
+            print("\nINFO: The crash string changed during our minimization process.")
+            print("Before: ", crash_string)
+            print("After: ", line)
+            print("The original regex pattern can still match, updated the crash string.")
+            crash_string = line
+            return True
 
-    return CRASH_TOKEN in output
+    # The input did not trigger (the same type) bug.
+    return False
 
 
 def minimize_trace(inpath, outpath):
@@ -66,7 +100,6 @@ def minimize_trace(inpath, outpath):
     print("Crashed in {} seconds".format(end-start))
     TIMEOUT = (end-start)*5
     print("Setting the timeout for {} seconds".format(TIMEOUT))
-    print("Identifying Crashes by this string: {}".format(CRASH_TOKEN))
 
     i = 0
     newtrace = trace[:]
@@ -152,6 +185,6 @@ if __name__ == '__main__':
         usage()
     # if "accel" not in QEMU_ARGS:
     #     QEMU_ARGS += " -accel qtest"
-    CRASH_TOKEN = os.getenv("CRASH_TOKEN")
+    crash_pattern = os.getenv("CRASH_PATTERN")
     QEMU_ARGS += " -qtest stdio -monitor none -serial none "
     minimize_trace(sys.argv[1], sys.argv[2])
-- 
2.25.1

Re: [PATCH 1/4] fuzz: refine crash detection mechanism

[Alexander Bulekov]

Re: [PATCH 1/4] fuzz: refine crash detection mechanism

[Qiuhao Li]

This email looks empty. Is this intentional?

On Mon, 2020-12-21 at 13:46 -0500, Alexander Bulekov wrote:
> 

Re: [PATCH 1/4] fuzz: refine crash detection mechanism

[Alexander Bulekov]

Oops let me try to resend this..

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

> The original crash detection method is to fork a process to test our new
> trace input. If the child process exits in time and the second-to-last line
> is the same as the first crash, we think it is a crash triggered by the same
> bug. However, in some situations, it doesn't work since it is a
> hardcoded-offset string comparison.
>
> For example, suppose an assertion failure makes the crash. In that case, the
> second-to-last line will be 'timeout: the monitored command dumped core',
>

Ah - I have not encountered this message. Are you running an
--enable-sanitizers build? I believe ASAN disables coredumps, by
default. I have to turn them on with:
ASAN_OPTIONS=abort_on_error=1:disable_coredump=0:unmap_shadow_on_exit=1

Maybe this is a matter of setting the correct env variables/disabling
coredumps?

I like the idea of switching out CRASH_TOKEN for a regex, however I am
not sure about using the hardcoded crash_patterns to perform matching:

1.) You risk missing some crash pattern. E.g. I don't think
abort()/hw_error() are covered right now.
2.) At some point ASAN/compiler-rt might change the way it outputs
crashes.

I think the current lines[-2] approach is ugly, but it is small, works
in most cases (when coredumps are disabled), and has a simple
CRASH_TOKEN fallback mechanism. We should fix the coredump problem.

Is there any way to do this without hardcoding patterns (or at least
fall-back to something if you don't find a pattern)?

-Alex

> which doesn't contain any information about the assertion failure like where
> it happened or the assertion statement. This may lead to a minimized input
> triggers assertion failure but may indicate another bug. As for some
> sanitizers' crashes, the direct string comparison may stop us from getting a
> smaller input, since they may have a different leaf stack frame.
>
> Perhaps we can detect crashes using both precise output string comparison
> and rough pattern string match and info the user when the trace input
> triggers different but a seminar output.
>
> Tested:
> Assertion failure, https://bugs.launchpad.net/qemu/+bug/1908062
> AddressSanitizer, https://bugs.launchpad.net/qemu/+bug/1907497
> Trace input that doesn't crash
> Trace input that crashes Qtest
>
> Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> ---
>  scripts/oss-fuzz/minimize_qtest_trace.py | 59 ++++++++++++++++++------
>  1 file changed, 46 insertions(+), 13 deletions(-)
>
> diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
> index 5e405a0d5f..d3b09e6567 100755
> --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> @@ -10,11 +10,16 @@ import os
>  import subprocess
>  import time
>  import struct
> +import re
>
>  QEMU_ARGS = None
>  QEMU_PATH = None
>  TIMEOUT = 5
> -CRASH_TOKEN = None
> +
> +crash_patterns = ("Assertion.+failed",
> +                  "SUMMARY.+Sanitizer")
> +crash_pattern = None
> +crash_string = None
>
>  write_suffix_lookup = {"b": (1, "B"),
>                         "w": (2, "H"),
> @@ -24,13 +29,12 @@ write_suffix_lookup = {"b": (1, "B"),
>  def usage():
>      sys.exit("""\
>  Usage: QEMU_PATH="/path/to/qemu" QEMU_ARGS="args" {} input_trace output_trace
> -By default, will try to use the second-to-last line in the output to identify
> -whether the crash occred. Optionally, manually set a string that idenitifes the
> -crash by setting CRASH_TOKEN=
> +By default, we will try to search predefined crash patterns through the
> +tracing output to see whether the crash occred. Optionally, manually set a
> +string that idenitifes the crash by setting CRASH_PATTERN=
>  """.format((sys.argv[0])))
>
>  def check_if_trace_crashes(trace, path):
> -    global CRASH_TOKEN
>      with open(path, "w") as tracefile:
>          tracefile.write("".join(trace))
>
> @@ -42,17 +46,47 @@ def check_if_trace_crashes(trace, path):
>                            shell=True,
>                            stdin=subprocess.PIPE,
>                            stdout=subprocess.PIPE)
> +    if rc.returncode == 137:    # Timed Out
> +        return False
> +
>      stdo = rc.communicate()[0]
>      output = stdo.decode('unicode_escape')
>      > -    if rc.returncode == 137:    # Timed Out
> -        return False
> -    if len(output.splitlines()) < 2:
> +    output_lines = output.splitlines()
> +    # Usually we care about the summary info in the last few lines, reverse.
> +    output_lines.reverse()
> +
> +    global crash_pattern, crash_patterns, crash_string
> +    if crash_pattern is None: # Initialization
> +        for line in output_lines:
> +            for c in crash_patterns:
> +                if re.search(c, line) is not None:
> +                    crash_pattern = c
> +                    crash_string = line
> +                    print("Identifying crash pattern by this string: ",\
> +                          crash_string)
> +                    print("Using regex pattern: ", crash_pattern)
> +                    return True
> +        print("Failed to initialize crash pattern: no match.")
>          return False
>
> -    if CRASH_TOKEN is None:
> -        CRASH_TOKEN = output.splitlines()[-2]
> +    # First, we search exactly the previous crash string.
> +    for line in output_lines:
> +        if crash_string == line:
> +            return True
> +
> +    # Then we decide whether a similar (same pattern) crash happened.
> +    # Slower now :(
> +    for line in output_lines:
> +        if re.search(crash_pattern, line) is not None:
> +            print("\nINFO: The crash string changed during our minimization process.")
> +            print("Before: ", crash_string)
> +            print("After: ", line)
> +            print("The original regex pattern can still match, updated the crash string.")
> +            crash_string = line
> +            return True
>
> -    return CRASH_TOKEN in output
> +    # The input did not trigger (the same type) bug.
> +    return False
>
>
>  def minimize_trace(inpath, outpath):
> @@ -66,7 +100,6 @@ def minimize_trace(inpath, outpath):
>      print("Crashed in {} seconds".format(end-start))
>      TIMEOUT = (end-start)*5
>      print("Setting the timeout for {} seconds".format(TIMEOUT))
> -    print("Identifying Crashes by this string: {}".format(CRASH_TOKEN))
>
>      i = 0
>      newtrace = trace[:]
> @@ -152,6 +185,6 @@ if __name__ == '__main__':
>          usage()
>      # if "accel" not in QEMU_ARGS:
>      #     QEMU_ARGS += " -accel qtest"
> -    CRASH_TOKEN = os.getenv("CRASH_TOKEN")
> +    crash_pattern = os.getenv("CRASH_PATTERN")
>      QEMU_ARGS += " -qtest stdio -monitor none -serial none "
>      minimize_trace(sys.argv[1], sys.argv[2])
> --
> 2.25.1

Re: [PATCH 1/4] fuzz: refine crash detection mechanism

[Li Qiuhao]

On Tue, 2020-12-22 at 11:47 -0500, Alexander Bulekov wrote:
> Oops let me try to resend this..
> 
> Qiuhao Li <Qiuhao.Li@outlook.com> writes:
> 
> > The original crash detection method is to fork a process to test
> > our new
> > trace input. If the child process exits in time and the second-to-
> > last line
> > is the same as the first crash, we think it is a crash triggered by
> > the same
> > bug. However, in some situations, it doesn't work since it is a
> > hardcoded-offset string comparison.
> > 
> > For example, suppose an assertion failure makes the crash. In that
> > case, the
> > second-to-last line will be 'timeout: the monitored command dumped
> > core',
> > 
> 
> Ah - I have not encountered this message. Are you running an
> --enable-sanitizers build? I believe ASAN disables coredumps, by
> default. I have to turn them on with:
> ASAN_OPTIONS=abort_on_error=1:disable_coredump=0:unmap_shadow_on_exit
> =1
> 
> Maybe this is a matter of setting the correct env variables/disabling
> coredumps?

Yes, I built emu-system-i386 with --enable-fuzzing --enable-sanitizers.

I tested a program built with ASAN, but it did try to dump core:

---

qiuhao@XPS-13-9360:~/tmp$ cat test.c
#include <signal.h>
int main (void) {
raise(SIGABRT);
return(0);
}

qiuhao@XPS-13-9360:~/tmp$ clang --version
clang version 10.0.0-4ubuntu1 
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

qiuhao@XPS-13-9360:~/tmp$ clang -g -O0 -fsanitize=address test.c && ./a.out
Aborted (core dumped)

---

Only when I test a program built with "-fanitizer=address,fuzzer" will it disable the core dump and print the stack backtrace and info deadly signal:

---

qiuhao@XPS-13-9360:~/tmp$ cat fuzz.cc 
#include <stdint.h>
#include <signal.h>

extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
  raise(SIGABRT);
  return 0;
}

qiuhao@XPS-13-9360:~/tmp$ clang++ -fsanitize=address,fuzzer fuzz.cc && ./a.out 
INFO: Seed: 3533057472
INFO: Loaded 1 modules   (1 inline 8-bit counters): 1 [0x5a6ec0, 0x5a6ec1), 
INFO: Loaded 1 PC tables (1 PCs): 1 [0x56b140,0x56b150), 
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
==38847== ERROR: libFuzzer: deadly signal
    #0 0x526d21 in __sanitizer_print_stack_trace (/home/qiuhao/tmp/a.out+0x526d21)
    #1 0x471e78 in fuzzer::PrintStackTrace() (/home/qiuhao/tmp/a.out+0x471e78)
    #2 0x456fc3 in fuzzer::Fuzzer::CrashCallback() (/home/qiuhao/tmp/a.out+0x456fc3)
    #3 0x7fe3df4b63bf  (/lib/x86_64-linux-gnu/libpthread.so.0+0x153bf)
    #4 0x7fe3df4b624a in __libc_signal_restore_set /build/glibc-ZN95T4/glibc-2.31/nptl/../sysdeps/unix/sysv/linux/internal-signals.h:86:3
    #5 0x7fe3df4b624a in raise /build/glibc-ZN95T4/glibc-2.31/nptl/../sysdeps/unix/sysv/linux/raise.c:48:3
    #6 0x550291 in LLVMFuzzerTestOneInput (/home/qiuhao/tmp/a.out+0x550291)
    #7 0x458681 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/home/qiuhao/tmp/a.out+0x458681)
    #8 0x45a3ba in fuzzer::Fuzzer::ReadAndExecuteSeedCorpora(std::__Fuzzer::vector<fuzzer::SizedFile, fuzzer::fuzzer_allocator<fuzzer::SizedFile> >&) (/home/qiuhao/tmp/a.out+0x45a3ba)
    #9 0x45aa49 in fuzzer::Fuzzer::Loop(std::__Fuzzer::vector<fuzzer::SizedFile, fuzzer::fuzzer_allocator<fuzzer::SizedFile> >&) (/home/qiuhao/tmp/a.out+0x45aa49)
    #10 0x44971e in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) (/home/qiuhao/tmp/a.out+0x44971e)
    #11 0x472562 in main (/home/qiuhao/tmp/a.out+0x472562)
    #12 0x7fe3df2a80b2 in __libc_start_main /build/glibc-ZN95T4/glibc-2.31/csu/../csu/libc-start.c:308:16
    #13 0x41e4bd in _start (/home/qiuhao/tmp/a.out+0x41e4bd)

NOTE: libFuzzer has rudimentary signal handlers.
      Combine libFuzzer with AddressSanitizer or similar for better crash reports.
SUMMARY: libFuzzer: deadly signal
MS: 0 ; base unit: 0000000000000000000000000000000000000000


artifact_prefix='./'; Test unit written to ./crash-da39a3ee5e6b4b0d3255bfef95601890afd80709
Base64: 

---

Did I miss something? Or I misused ASAN?

> I like the idea of switching out CRASH_TOKEN for a regex, however I
> am
> not sure about using the hardcoded crash_patterns to perform
> matching:
> 
> 1.) You risk missing some crash pattern. E.g. I don't think
> abort()/hw_error() are covered right now.

I reversed your fallback in Patch, just renamed it :)

-    CRASH_TOKEN = os.getenv("CRASH_TOKEN")
+    crash_pattern = os.getenv("CRASH_PATTERN")

> 2.) At some point ASAN/compiler-rt might change the way it outputs
> crashes.

You are right, but the lines[-2] has the same problem.

> I think the current lines[-2] approach is ugly, but it is small,
> works
> in most cases (when coredumps are disabled), and has a simple
> CRASH_TOKEN fallback mechanism. We should fix the coredump problem.
> 
> Is there any way to do this without hardcoding patterns (or at least
> fall-back to something if you don't find a pattern)?
> 
> -Alex

The major reason I choose to use regex pattern is that we can keep trimming the input trace when removing a instruction triggers a different crash output, especially caused by a changed leaf stack frame. For example, Bug 1907497, https://lists.nongnu.org/archive/html/qemu-devel/2020-12/msg02380.html. Suppose there are duplicate writes which can still crash:

outl 0xcf8 0x80000804
outw 0xcfc 0xffff
write 0x0 0x1 0x12
write 0x2 0x1 0x2f
outl 0xcf8 0x80000811
outl 0xcfc 0x5a6a4406
write 0x6a44005a 0x1 0x11  <-- The only one we really need
write 0x6a44005a 0x1 0x11  <-- useless
write 0x6a44005a 0x1 0x11  <-- useless
write 0x6a44005c 0x1 0x3f
write 0x6a442050 0x4 0x0000446a
write 0x6a44204a 0x1 0xf3
write 0x6a44204c 0x1 0xff
writeq 0x6a44005a 0x17b3f0011
write 0x6a442050 0x4 0x0000446a
write 0x6a44204a 0x1 0xf3
write 0x6a44204c 0x1 0xff

For this fake input, The lines[-2] would be:

SUMMARY: AddressSanitizer: stack-overflow (/home/qiuhao/hack/qemu/build/qemu-system-i386+0x27ca049) in __asan_memcpy

But after we removed a useless write, the lines[-2] **has a chance (around 1 out of 5)** to be:

SUMMARY: AddressSanitizer: stack-overflow /home/qiuhao/hack/qemu/build/../softmmu/physmem.c:309:27 in phys_page_find

or

SUMMARY: AddressSanitizer: stack-overflow /home/qiuhao/hack/qemu/build/../softmmu/physmem.c:354 in address_space_translate_internal

or

SUMMARY: AddressSanitizer: stack-overflow /home/qiuhao/hack/qemu/build/../softmmu/physmem.c:298 in section_covers_addr

This will stop us from trimming the useless writes.

---

In all, how about we try this:

1. If CRASH_PATTERN defined (fallback), use it.
2. Else if we can find a pre-defined pattern in the crash output, use it.
3. Use the second-to-end line as the string for comparison.

P.S.
There are some sophisticated crash case deduplication methods like stack backtrace hashing or coverage-based comparison, semantics-aware Deduplication[1]. But for now, I think our solution can cover most cases.

[1] https://arxiv.org/abs/1812.00140 6.3.1 Deduplication

> > which doesn't contain any information about the assertion failure
> > like where
> > it happened or the assertion statement. This may lead to a
> > minimized input
> > triggers assertion failure but may indicate another bug. As for
> > some
> > sanitizers' crashes, the direct string comparison may stop us from
> > getting a
> > smaller input, since they may have a different leaf stack frame.
> > 
> > Perhaps we can detect crashes using both precise output string
> > comparison
> > and rough pattern string match and info the user when the trace
> > input
> > triggers different but a seminar output.
> > 
> > Tested:
> > Assertion failure, https://bugs.launchpad.net/qemu/+bug/1908062
> > AddressSanitizer, https://bugs.launchpad.net/qemu/+bug/1907497
> > Trace input that doesn't crash
> > Trace input that crashes Qtest
> > 
> > Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> > ---
> >  scripts/oss-fuzz/minimize_qtest_trace.py | 59 ++++++++++++++++++
> > ------
> >  1 file changed, 46 insertions(+), 13 deletions(-)
> > 
> > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > index 5e405a0d5f..d3b09e6567 100755
> > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > @@ -10,11 +10,16 @@ import os
> >  import subprocess
> >  import time
> >  import struct
> > +import re
> > 
> >  QEMU_ARGS = None
> >  QEMU_PATH = None
> >  TIMEOUT = 5
> > -CRASH_TOKEN = None
> > +
> > +crash_patterns = ("Assertion.+failed",
> > +                  "SUMMARY.+Sanitizer")
> > +crash_pattern = None
> > +crash_string = None
> > 
> >  write_suffix_lookup = {"b": (1, "B"),
> >                         "w": (2, "H"),
> > @@ -24,13 +29,12 @@ write_suffix_lookup = {"b": (1, "B"),
> >  def usage():
> >      sys.exit("""\
> >  Usage: QEMU_PATH="/path/to/qemu" QEMU_ARGS="args" {} input_trace
> > output_trace
> > -By default, will try to use the second-to-last line in the output
> > to identify
> > -whether the crash occred. Optionally, manually set a string that
> > idenitifes the
> > -crash by setting CRASH_TOKEN=
> > +By default, we will try to search predefined crash patterns
> > through the
> > +tracing output to see whether the crash occred. Optionally,
> > manually set a
> > +string that idenitifes the crash by setting CRASH_PATTERN=
> >  """.format((sys.argv[0])))
> > 
> >  def check_if_trace_crashes(trace, path):
> > -    global CRASH_TOKEN
> >      with open(path, "w") as tracefile:
> >          tracefile.write("".join(trace))
> > 
> > @@ -42,17 +46,47 @@ def check_if_trace_crashes(trace, path):
> >                            shell=True,
> >                            stdin=subprocess.PIPE,
> >                            stdout=subprocess.PIPE)
> > +    if rc.returncode == 137:    # Timed Out
> > +        return False
> > +
> >      stdo = rc.communicate()[0]
> >      output = stdo.decode('unicode_escape')
> >      > -    if rc.returncode == 137:    # Timed Out
> > -        return False
> > -    if len(output.splitlines()) < 2:
> > +    output_lines = output.splitlines()
> > +    # Usually we care about the summary info in the last few
> > lines, reverse.
> > +    output_lines.reverse()
> > +
> > +    global crash_pattern, crash_patterns, crash_string
> > +    if crash_pattern is None: # Initialization
> > +        for line in output_lines:
> > +            for c in crash_patterns:
> > +                if re.search(c, line) is not None:
> > +                    crash_pattern = c
> > +                    crash_string = line
> > +                    print("Identifying crash pattern by this
> > string: ",\
> > +                          crash_string)
> > +                    print("Using regex pattern: ", crash_pattern)
> > +                    return True
> > +        print("Failed to initialize crash pattern: no match.")
> >          return False
> > 
> > -    if CRASH_TOKEN is None:
> > -        CRASH_TOKEN = output.splitlines()[-2]
> > +    # First, we search exactly the previous crash string.
> > +    for line in output_lines:
> > +        if crash_string == line:
> > +            return True
> > +
> > +    # Then we decide whether a similar (same pattern) crash
> > happened.
> > +    # Slower now :(
> > +    for line in output_lines:
> > +        if re.search(crash_pattern, line) is not None:
> > +            print("\nINFO: The crash string changed during our
> > minimization process.")
> > +            print("Before: ", crash_string)
> > +            print("After: ", line)
> > +            print("The original regex pattern can still match,
> > updated the crash string.")
> > +            crash_string = line
> > +            return True
> > 
> > -    return CRASH_TOKEN in output
> > +    # The input did not trigger (the same type) bug.
> > +    return False
> > 
> > 
> >  def minimize_trace(inpath, outpath):
> > @@ -66,7 +100,6 @@ def minimize_trace(inpath, outpath):
> >      print("Crashed in {} seconds".format(end-start))
> >      TIMEOUT = (end-start)*5
> >      print("Setting the timeout for {} seconds".format(TIMEOUT))
> > -    print("Identifying Crashes by this string:
> > {}".format(CRASH_TOKEN))
> > 
> >      i = 0
> >      newtrace = trace[:]
> > @@ -152,6 +185,6 @@ if __name__ == '__main__':
> >          usage()
> >      # if "accel" not in QEMU_ARGS:
> >      #     QEMU_ARGS += " -accel qtest"
> > -    CRASH_TOKEN = os.getenv("CRASH_TOKEN")
> > +    crash_pattern = os.getenv("CRASH_PATTERN")
> >      QEMU_ARGS += " -qtest stdio -monitor none -serial none "
> >      minimize_trace(sys.argv[1], sys.argv[2])
> > --
> > 2.25.1

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

[Qiuhao Li]

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(-)

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

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

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

[PATCH 3/4] fuzz: setting bits in operand of out/write to zero

[Qiuhao Li]

Simplifying the crash cases by opportunistically setting bits in
operands of
out/write to zero may help to debug, since usually bit one means turn on
or
trigger a function while zero is the default turn-off setting.

Tested Bug 1908062. Refined vs. Original result:

outl 0xcf8 0x8000081c            outl 0xcf8 0x8000081c
outb 0xcfc 0xc3                  outb 0xcfc 0xc3
outl 0xcf8 0x0               <-- outl 0xcf8 0x8000082f
outl 0xcf8 0x80000804            outl 0xcf8 0x80000804
outl 0xcfc 0x10000006        <-- outl 0xcfc 0x9b2765be
write 0xc300001024 0x2 0x10  <-- 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 0x80  <-- write 0xc300001018 0x1 0xa4
write 0x5c 0x1 0x10          <-- write 0x5c 0x1 0x19
write 0xc300003002 0x1 0x0   <-- write 0xc300003002 0x1 0x8a

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

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 855c3bcb54..f3e88064c4 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -172,7 +172,47 @@ def minimize_trace(inpath, outpath):
                     newtrace[i] = prior
                     del newtrace[i+1]
         i += 1
-    check_if_trace_crashes(newtrace, outpath)
+
+    assert(check_if_trace_crashes(newtrace, outpath))
+
+    TIMEOUT = (end-start)*2 # input is short now
+
+    # try setting bits in operands of out/write to zero
+    i = 0
+    while i < len(newtrace):
+        if (not newtrace[i].startswith("write ") and not
+           newtrace[i].startswith("out")):
+           i += 1
+           continue
+        # write ADDR SIZE DATA
+        # outx ADDR VALUE
+        print("\nzero setting bits: {}".format(newtrace[i]))
+
+        prefix = " ".join(newtrace[i].split()[:-1])
+        data = newtrace[i].split()[-1]
+        data_bin = bin(int(data, 16))
+        data_bin_list = list(data_bin)
+
+        for j in range(2, len(data_bin_list)):
+            prior = newtrace[i]
+            if (data_bin_list[j] == '1'):
+                data_bin_list[j] = '0'
+                data_try = hex(int("".join(data_bin_list), 2))
+                # It seems qtest only accect hex with one byte zero padding
+                if len(data_try) % 2 == 1:
+                    data_try = data_try[:2] + "0" + data_try[2:-1]
+
+                newtrace[i] = "{prefix} {data_try}\n".format(
+                        prefix=prefix,
+                        data_try=data_try)
+
+                if not check_if_trace_crashes(newtrace, outpath):
+                    data_bin_list[j] = '1'
+                    newtrace[i] = prior
+
+        i += 1
+
+    assert(check_if_trace_crashes(newtrace, outpath))
 
 
 if __name__ == '__main__':
-- 
2.25.1

Re: [PATCH 3/4] fuzz: setting bits in operand of out/write to zero

[Alexander Bulekov]

On 201220 0256, Qiuhao Li wrote:
> Simplifying the crash cases by opportunistically setting bits in
> operands of
> out/write to zero may help to debug, since usually bit one means turn on
> or
> trigger a function while zero is the default turn-off setting.
> 
> Tested Bug 1908062. Refined vs. Original result:
> 
> outl 0xcf8 0x8000081c            outl 0xcf8 0x8000081c
> outb 0xcfc 0xc3                  outb 0xcfc 0xc3
> outl 0xcf8 0x0               <-- outl 0xcf8 0x8000082f
> outl 0xcf8 0x80000804            outl 0xcf8 0x80000804
> outl 0xcfc 0x10000006        <-- outl 0xcfc 0x9b2765be
> write 0xc300001024 0x2 0x10  <-- 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 0x80  <-- write 0xc300001018 0x1 0xa4
> write 0x5c 0x1 0x10          <-- write 0x5c 0x1 0x19
> write 0xc300003002 0x1 0x0   <-- write 0xc300003002 0x1 0x8a
> 
> Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>

Looks good. One nit below.

Reviewed-by: Alexander Bulekov <alxndr@bu.edu>


> ---
>  scripts/oss-fuzz/minimize_qtest_trace.py | 42 +++++++++++++++++++++++-
>  1 file changed, 41 insertions(+), 1 deletion(-)
> 
> diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
> index 855c3bcb54..f3e88064c4 100755
> --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> @@ -172,7 +172,47 @@ def minimize_trace(inpath, outpath):
>                      newtrace[i] = prior
>                      del newtrace[i+1]
>          i += 1
> -    check_if_trace_crashes(newtrace, outpath)
> +
> +    assert(check_if_trace_crashes(newtrace, outpath))
> +
> +    TIMEOUT = (end-start)*2 # input is short now
> +
> +    # try setting bits in operands of out/write to zero
> +    i = 0
> +    while i < len(newtrace):
> +        if (not newtrace[i].startswith("write ") and not
> +           newtrace[i].startswith("out")):
> +           i += 1
> +           continue
> +        # write ADDR SIZE DATA
> +        # outx ADDR VALUE
> +        print("\nzero setting bits: {}".format(newtrace[i]))
> +
> +        prefix = " ".join(newtrace[i].split()[:-1])
> +        data = newtrace[i].split()[-1]
> +        data_bin = bin(int(data, 16))
> +        data_bin_list = list(data_bin)
> +
> +        for j in range(2, len(data_bin_list)):
> +            prior = newtrace[i]
> +            if (data_bin_list[j] == '1'):
> +                data_bin_list[j] = '0'
> +                data_try = hex(int("".join(data_bin_list), 2))
> +                # It seems qtest only accect hex with one byte zero padding
                                         ^^ "accepts padded hex-values."

> +                if len(data_try) % 2 == 1:
> +                    data_try = data_try[:2] + "0" + data_try[2:-1]
> +
> +                newtrace[i] = "{prefix} {data_try}\n".format(
> +                        prefix=prefix,
> +                        data_try=data_try)
> +
> +                if not check_if_trace_crashes(newtrace, outpath):
> +                    data_bin_list[j] = '1'
> +                    newtrace[i] = prior
> +
> +        i += 1
> +
> +    assert(check_if_trace_crashes(newtrace, outpath))
>  
>  
>  if __name__ == '__main__':
> -- 
> 2.25.1
> 

Re: [PATCH 3/4] fuzz: setting bits in operand of out/write to zero

[Qiuhao Li]

On Mon, 2020-12-21 at 15:35 -0500, Alexander Bulekov wrote:
> On 201220 0256, Qiuhao Li wrote:
> > Simplifying the crash cases by opportunistically setting bits in
> > operands of
> > out/write to zero may help to debug, since usually bit one means
> > turn on
> > or
> > trigger a function while zero is the default turn-off setting.
> > 
> > Tested Bug 1908062. Refined vs. Original result:
> > 
> > outl 0xcf8 0x8000081c            outl 0xcf8 0x8000081c
> > outb 0xcfc 0xc3                  outb 0xcfc 0xc3
> > outl 0xcf8 0x0               <-- outl 0xcf8 0x8000082f
> > outl 0xcf8 0x80000804            outl 0xcf8 0x80000804
> > outl 0xcfc 0x10000006        <-- outl 0xcfc 0x9b2765be
> > write 0xc300001024 0x2 0x10  <-- 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 0x80  <-- write 0xc300001018 0x1 0xa4
> > write 0x5c 0x1 0x10          <-- write 0x5c 0x1 0x19
> > write 0xc300003002 0x1 0x0   <-- write 0xc300003002 0x1 0x8a
> > 
> > Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> 
> Looks good. One nit below.
> 
> Reviewed-by: Alexander Bulekov <alxndr@bu.edu>
> 
> 
> > ---
> >  scripts/oss-fuzz/minimize_qtest_trace.py | 42
> > +++++++++++++++++++++++-
> >  1 file changed, 41 insertions(+), 1 deletion(-)
> > 
> > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > index 855c3bcb54..f3e88064c4 100755
> > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > @@ -172,7 +172,47 @@ def minimize_trace(inpath, outpath):
> >                      newtrace[i] = prior
> >                      del newtrace[i+1]
> >          i += 1
> > -    check_if_trace_crashes(newtrace, outpath)
> > +
> > +    assert(check_if_trace_crashes(newtrace, outpath))
> > +
> > +    TIMEOUT = (end-start)*2 # input is short now
> > +
> > +    # try setting bits in operands of out/write to zero
> > +    i = 0
> > +    while i < len(newtrace):
> > +        if (not newtrace[i].startswith("write ") and not
> > +           newtrace[i].startswith("out")):
> > +           i += 1
> > +           continue
> > +        # write ADDR SIZE DATA
> > +        # outx ADDR VALUE
> > +        print("\nzero setting bits: {}".format(newtrace[i]))
> > +
> > +        prefix = " ".join(newtrace[i].split()[:-1])
> > +        data = newtrace[i].split()[-1]
> > +        data_bin = bin(int(data, 16))
> > +        data_bin_list = list(data_bin)
> > +
> > +        for j in range(2, len(data_bin_list)):
> > +            prior = newtrace[i]
> > +            if (data_bin_list[j] == '1'):
> > +                data_bin_list[j] = '0'
> > +                data_try = hex(int("".join(data_bin_list), 2))
> > +                # It seems qtest only accect hex with one byte
> > zero padding
>                                          ^^ "accepts padded hex-
> values."

Thanks.

> 
> > +                if len(data_try) % 2 == 1:
> > +                    data_try = data_try[:2] + "0" + data_try[2:-1]
> > +
> > +                newtrace[i] = "{prefix} {data_try}\n".format(
> > +                        prefix=prefix,
> > +                        data_try=data_try)
> > +
> > +                if not check_if_trace_crashes(newtrace, outpath):
> > +                    data_bin_list[j] = '1'
> > +                    newtrace[i] = prior
> > +
> > +        i += 1
> > +
> > +    assert(check_if_trace_crashes(newtrace, outpath))
> >  
> >  
> >  if __name__ == '__main__':
> > -- 
> > 2.25.1
> > 

[PATCH 4/4] fuzz: delay IO until they can't trigger the crash

[Qiuhao Li]

Since programmers usually trigger an IO just before they need it. Try to
delay some IO instructions may help us better understanding the timing
context when debug.

Tested with Bug 1908062. Refined vs. Original result:

outl 0xcf8 0x8000081c            outl 0xcf8 0x0
outb 0xcfc 0xc3                | outl 0xcf8 0x8000081c
outl 0xcf8 0x80000804          | outb 0xcfc 0xc3
outl 0xcfc 0x10000006          | outl 0xcf8 0x80000804
write 0xc300001028 0x1 0x5a    | outl 0xcfc 0x10000006
write 0xc300001024 0x2 0x10    | write 0xc300001028 0x1 0x5a
write 0xc30000101c 0x1 0x01    | writel 0xc30000100c 0x2a6f6c63
write 0xc300003002 0x1 0x0     v write 0xc300001024 0x2 0x10
write 0x5c 0x1 0x10              write 0xc30000101c 0x1 0x01
writel 0xc30000100c 0x2a6f6c63   write 0xc300001018 0x1 0x80
write 0xc300001018 0x1 0x80      write 0x5c 0x1 0x10
outl 0xcf8 0x0                   write 0xc300003002 0x1 0x0

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

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index f3e88064c4..da7aa73b3c 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -214,6 +214,27 @@ def minimize_trace(inpath, outpath):
 
     assert(check_if_trace_crashes(newtrace, outpath))
 
+    # delay IO instructions until they can't trigger the crash
+    # Note: O(n^2) and many timeouts, kinda slow
+    i = len(newtrace) - 1
+    while i >= 0:
+        tmp_i = newtrace[i]
+        if len(tmp_i) < 2:
+            i -= 1
+            continue
+        print("Delaying ", newtrace[i])
+        for j in reversed(range(i+1, len(newtrace)+1)):
+            newtrace.insert(j, tmp_i)
+            del newtrace[i]
+            if check_if_trace_crashes(newtrace, outpath):
+                break
+            newtrace.insert(i, tmp_i)
+            del newtrace[j]
+        i -= 1
+
+    assert(check_if_trace_crashes(newtrace, outpath))
+    # maybe another removing round
+
 
 if __name__ == '__main__':
     if len(sys.argv) < 3:
-- 
2.25.1

Re: [PATCH 4/4] fuzz: delay IO until they can't trigger the crash

[Alexander Bulekov]

On 201220 0256, Qiuhao Li wrote:
> Since programmers usually trigger an IO just before they need it. Try to
> delay some IO instructions may help us better understanding the timing
> context when debug.
> 
> Tested with Bug 1908062. Refined vs. Original result:
> 
> outl 0xcf8 0x8000081c            outl 0xcf8 0x0
> outb 0xcfc 0xc3                | outl 0xcf8 0x8000081c
> outl 0xcf8 0x80000804          | outb 0xcfc 0xc3
> outl 0xcfc 0x10000006          | outl 0xcf8 0x80000804
> write 0xc300001028 0x1 0x5a    | outl 0xcfc 0x10000006
> write 0xc300001024 0x2 0x10    | write 0xc300001028 0x1 0x5a
> write 0xc30000101c 0x1 0x01    | writel 0xc30000100c 0x2a6f6c63
> write 0xc300003002 0x1 0x0     v write 0xc300001024 0x2 0x10
> write 0x5c 0x1 0x10              write 0xc30000101c 0x1 0x01
> writel 0xc30000100c 0x2a6f6c63   write 0xc300001018 0x1 0x80
> write 0xc300001018 0x1 0x80      write 0x5c 0x1 0x10
> outl 0xcf8 0x0                   write 0xc300003002 0x1 0x0
> 

In this example, I can remove the outl 0xcf8 0x0, and I still see the
crash, so maybe the 1st step in the minimizer is failing somewhere.. 

Is the Refined one better? To me the original one read as:
"Do a bunch of PCI configuration to map an MMIO BAR, then interact with
the MMIO range and trigger some DMA activity". I also know exactly the
line that will trigger the DMA activity and access 0x5c. With the
refined one, I'm not so sure. Which line now causes the DMA read from
0x5c? writel 0xc30000100c? write 0xc300001018?
Is there another example where this type of reordering makes the result
easier to read?

> Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> ---
>  scripts/oss-fuzz/minimize_qtest_trace.py | 21 +++++++++++++++++++++
>  1 file changed, 21 insertions(+)
> 
> diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
> index f3e88064c4..da7aa73b3c 100755
> --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> @@ -214,6 +214,27 @@ def minimize_trace(inpath, outpath):
>  
>      assert(check_if_trace_crashes(newtrace, outpath))
>  
> +    # delay IO instructions until they can't trigger the crash
> +    # Note: O(n^2) and many timeouts, kinda slow

Maybe do a binary search instead of a linear scan for the optimal position
to save some time?
Also, if you re-run this multiple times, you can end up with different
results, since some lines might not really be tied to a position (e.g.
the outl cf8 0x0 in your example). Maybe it's not a problem, but i'm
still not sure that this is making the result easier to read.
-Alex

> +    i = len(newtrace) - 1
> +    while i >= 0:
> +        tmp_i = newtrace[i]
> +        if len(tmp_i) < 2:
> +            i -= 1
> +            continue
> +        print("Delaying ", newtrace[i])
> +        for j in reversed(range(i+1, len(newtrace)+1)):
> +            newtrace.insert(j, tmp_i)
> +            del newtrace[i]
> +            if check_if_trace_crashes(newtrace, outpath):
> +                break
> +            newtrace.insert(i, tmp_i)
> +            del newtrace[j]
> +        i -= 1
> +
> +    assert(check_if_trace_crashes(newtrace, outpath))
> +    # maybe another removing round
> +
>  
>  if __name__ == '__main__':
>      if len(sys.argv) < 3:
> -- 
> 2.25.1
> 

Re: [PATCH 4/4] fuzz: delay IO until they can't trigger the crash

[Qiuhao Li]

On Mon, 2020-12-21 at 16:17 -0500, Alexander Bulekov wrote:
> On 201220 0256, Qiuhao Li wrote:
> > Since programmers usually trigger an IO just before they need it.
> > Try to
> > delay some IO instructions may help us better understanding the
> > timing
> > context when debug.
> > 
> > Tested with Bug 1908062. Refined vs. Original result:
> > 
> > outl 0xcf8 0x8000081c            outl 0xcf8 0x0
> > outb 0xcfc 0xc3                | outl 0xcf8 0x8000081c
> > outl 0xcf8 0x80000804          | outb 0xcfc 0xc3
> > outl 0xcfc 0x10000006          | outl 0xcf8 0x80000804
> > write 0xc300001028 0x1 0x5a    | outl 0xcfc 0x10000006
> > write 0xc300001024 0x2 0x10    | write 0xc300001028 0x1 0x5a
> > write 0xc30000101c 0x1 0x01    | writel 0xc30000100c 0x2a6f6c63
> > write 0xc300003002 0x1 0x0     v write 0xc300001024 0x2 0x10
> > write 0x5c 0x1 0x10              write 0xc30000101c 0x1 0x01
> > writel 0xc30000100c 0x2a6f6c63   write 0xc300001018 0x1 0x80
> > write 0xc300001018 0x1 0x80      write 0x5c 0x1 0x10
> > outl 0xcf8 0x0                   write 0xc300003002 0x1 0x0
> > 
> 
> In this example, I can remove the outl 0xcf8 0x0, and I still see the
> crash, so maybe the 1st step in the minimizer is failing somewhere.. 

I think it might because of our one-time scan and remove strategy,
which is not suitable for timing dependent instructions.

For example, instruction A will indicate an address where the config
chunk locates, and instruction B will make the configuration active. If
we have the following instruction sequence:

...
A1
B1
A2
B2
...

A2 and B2 are the actual instructions that trigger the bug.

If we scan from top to bottom, after we remove A1, the behavior of B1
might be unknowable, including not to crash the program. But we will
successfully remove B1 later cause A2 and B2 will crash the process
anyway:

...
A1
A2
B2
...

Now one more trimming will remove A1.

As for the example I gave, the instructions before the delaying
minimizer are like this:

outl 0xcf8 0x8000081c
outb 0xcfc 0xc3
outl 0xcf8 0x0                <--- The A instruction, didn't be removed
(outl 0xcfc 0x0)              <--- The B instruction, removed
outl 0xcf8 0x80000804
outl 0xcfc 0x10000006
write 0xc300001024 0x2 0x10
write 0xc300001028 0x1 0x5a
write 0xc30000101c 0x1 0x01
writel 0xc30000100c 0x2a6f6c63
write 0xc300001018 0x1 0x80
write 0x5c 0x1 0x10
write 0xc300003002 0x1 0x0

If we run the remove minimizer again, The A instruction outl 0xcf8 0x0
will be removed.

Since we only remove instructions, this iterative algorithm is
converging. Maybe we can keep removing the trace until the
len(newtrace) become unchanged.

> 
> Is the Refined one better? To me the original one read as:
> "Do a bunch of PCI configuration to map an MMIO BAR, then interact
> with
> the MMIO range and trigger some DMA activity". I also know exactly
> the
> line that will trigger the DMA activity and access 0x5c. With the
> refined one, I'm not so sure. Which line now causes the DMA read from
> 0x5c? writel 0xc30000100c? write 0xc300001018?
> Is there another example where this type of reordering makes the
> result
> easier to read?
> 
> > Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> > ---
> >  scripts/oss-fuzz/minimize_qtest_trace.py | 21
> > +++++++++++++++++++++
> >  1 file changed, 21 insertions(+)
> > 
> > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > index f3e88064c4..da7aa73b3c 100755
> > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > @@ -214,6 +214,27 @@ def minimize_trace(inpath, outpath):
> >  
> >      assert(check_if_trace_crashes(newtrace, outpath))
> >  
> > +    # delay IO instructions until they can't trigger the crash
> > +    # Note: O(n^2) and many timeouts, kinda slow
> 
> Maybe do a binary search instead of a linear scan for the optimal
> position
> to save some time?
> Also, if you re-run this multiple times, you can end up with
> different
> results, since some lines might not really be tied to a position
> (e.g.
> the outl cf8 0x0 in your example). Maybe it's not a problem, but i'm
> still not sure that this is making the result easier to read.
> -Alex

I'm not familiar with the PCI configuration and DMA mechanism in QEMU.
This patch is just random thinking based on empiricism. Maybe I should
add the "RFC" tag :). In version 2, I won't post this patch.

BTW, may I ask where I can learn about these IO emulations? How do you
know the address corresponding to the PCI bar and DMA?

> 
> > +    i = len(newtrace) - 1
> > +    while i >= 0:
> > +        tmp_i = newtrace[i]
> > +        if len(tmp_i) < 2:
> > +            i -= 1
> > +            continue
> > +        print("Delaying ", newtrace[i])
> > +        for j in reversed(range(i+1, len(newtrace)+1)):
> > +            newtrace.insert(j, tmp_i)
> > +            del newtrace[i]
> > +            if check_if_trace_crashes(newtrace, outpath):
> > +                break
> > +            newtrace.insert(i, tmp_i)
> > +            del newtrace[j]
> > +        i -= 1
> > +
> > +    assert(check_if_trace_crashes(newtrace, outpath))
> > +    # maybe another removing round
> > +
> >  
> >  if __name__ == '__main__':
> >      if len(sys.argv) < 3:
> > -- 
> > 2.25.1
> > 

Re: [PATCH 4/4] fuzz: delay IO until they can't trigger the crash

[Alexander Bulekov]

On 201222 1922, Qiuhao Li wrote:
> On Mon, 2020-12-21 at 16:17 -0500, Alexander Bulekov wrote:
> > On 201220 0256, Qiuhao Li wrote:
> > > Since programmers usually trigger an IO just before they need it.
> > > Try to
> > > delay some IO instructions may help us better understanding the
> > > timing
> > > context when debug.
> > > 
> > > Tested with Bug 1908062. Refined vs. Original result:
> > > 
> > > outl 0xcf8 0x8000081c            outl 0xcf8 0x0
> > > outb 0xcfc 0xc3                | outl 0xcf8 0x8000081c
> > > outl 0xcf8 0x80000804          | outb 0xcfc 0xc3
> > > outl 0xcfc 0x10000006          | outl 0xcf8 0x80000804
> > > write 0xc300001028 0x1 0x5a    | outl 0xcfc 0x10000006
> > > write 0xc300001024 0x2 0x10    | write 0xc300001028 0x1 0x5a
> > > write 0xc30000101c 0x1 0x01    | writel 0xc30000100c 0x2a6f6c63
> > > write 0xc300003002 0x1 0x0     v write 0xc300001024 0x2 0x10
> > > write 0x5c 0x1 0x10              write 0xc30000101c 0x1 0x01
> > > writel 0xc30000100c 0x2a6f6c63   write 0xc300001018 0x1 0x80
> > > write 0xc300001018 0x1 0x80      write 0x5c 0x1 0x10
> > > outl 0xcf8 0x0                   write 0xc300003002 0x1 0x0
> > > 
> > 
> > In this example, I can remove the outl 0xcf8 0x0, and I still see the
> > crash, so maybe the 1st step in the minimizer is failing somewhere.. 
> 
> I think it might because of our one-time scan and remove strategy,
> which is not suitable for timing dependent instructions.
> 
> For example, instruction A will indicate an address where the config
> chunk locates, and instruction B will make the configuration active. If
> we have the following instruction sequence:
> 
> ...
> A1
> B1
> A2
> B2
> ...
> 
> A2 and B2 are the actual instructions that trigger the bug.
> 
> If we scan from top to bottom, after we remove A1, the behavior of B1
> might be unknowable, including not to crash the program. But we will
> successfully remove B1 later cause A2 and B2 will crash the process
> anyway:
> 
> ...
> A1
> A2
> B2
> ...
> 
> Now one more trimming will remove A1.
> 
> As for the example I gave, the instructions before the delaying
> minimizer are like this:
> 
> outl 0xcf8 0x8000081c
> outb 0xcfc 0xc3
> outl 0xcf8 0x0                <--- The A instruction, didn't be removed
> (outl 0xcfc 0x0)              <--- The B instruction, removed
> outl 0xcf8 0x80000804
> outl 0xcfc 0x10000006
> write 0xc300001024 0x2 0x10
> write 0xc300001028 0x1 0x5a
> write 0xc30000101c 0x1 0x01
> writel 0xc30000100c 0x2a6f6c63
> write 0xc300001018 0x1 0x80
> write 0x5c 0x1 0x10
> write 0xc300003002 0x1 0x0
> 
> If we run the remove minimizer again, The A instruction outl 0xcf8 0x0
> will be removed.
> 
> Since we only remove instructions, this iterative algorithm is
> converging. Maybe we can keep removing the trace until the
> len(newtrace) become unchanged.
> 

I found a bunch of work related to this "test-case minimization". There
are algorithms such as "ddmin" that try to tackle this. There might be
some interesting ideas there.

I think in the perfect case, we would need to be able to remove A and B
at the same time. You described the situation where B1 might lead to a
bad state without A1, but there is also the possibility that A1 might
leave bad state around, without B1. And both of these might be true at
the same time :) Probably not something we encounter very often, though.

> > 
> > Is the Refined one better? To me the original one read as:
> > "Do a bunch of PCI configuration to map an MMIO BAR, then interact
> > with
> > the MMIO range and trigger some DMA activity". I also know exactly
> > the
> > line that will trigger the DMA activity and access 0x5c. With the
> > refined one, I'm not so sure. Which line now causes the DMA read from
> > 0x5c? writel 0xc30000100c? write 0xc300001018?
> > Is there another example where this type of reordering makes the
> > result
> > easier to read?
> > 
> > > Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> > > ---
> > >  scripts/oss-fuzz/minimize_qtest_trace.py | 21
> > > +++++++++++++++++++++
> > >  1 file changed, 21 insertions(+)
> > > 
> > > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > > index f3e88064c4..da7aa73b3c 100755
> > > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > > @@ -214,6 +214,27 @@ def minimize_trace(inpath, outpath):
> > >  
> > >      assert(check_if_trace_crashes(newtrace, outpath))
> > >  
> > > +    # delay IO instructions until they can't trigger the crash
> > > +    # Note: O(n^2) and many timeouts, kinda slow
> > 
> > Maybe do a binary search instead of a linear scan for the optimal
> > position
> > to save some time?
> > Also, if you re-run this multiple times, you can end up with
> > different
> > results, since some lines might not really be tied to a position
> > (e.g.
> > the outl cf8 0x0 in your example). Maybe it's not a problem, but i'm
> > still not sure that this is making the result easier to read.
> > -Alex
> 
> I'm not familiar with the PCI configuration and DMA mechanism in QEMU.
> This patch is just random thinking based on empiricism. Maybe I should
> add the "RFC" tag :). In version 2, I won't post this patch.
> 
> BTW, may I ask where I can learn about these IO emulations? How do you
> know the address corresponding to the PCI bar and DMA?

On PCs, the PCI configuration space is accessed using two I/O ports:
0xcfc and 0xcf8. To interact further with a  PCI device, you have to
configure its BARs (i.e. the Port IO and memory ranges that will map to
device registers).
https://en.wikipedia.org/wiki/PCI_configuration_space#Bus_enumeration

So we can look at the trace again. First there are no virtio-vga MMIO/PIO
ranges accessible, so the only thing the fuzzer can do is interact with
its PCI configuration space using 0xCF8/CFC:

outl 0xcf8 0x8000081c
outb 0xcfc 0xc3
^^^ The above two lines write the value 0xc3 to PCI config address 0x1c
for the vga device. You can confirm this by running the testcase with
-trace pci\*. 0x1c is the location of the PCI register that represents
BAR #3 for the device. 
outl 0xcf8 0x80000804
outb 0xcfc 0x06
^^^ These two lines write to the PCI command register (0x04) to allow
the device to respond to memory accesses.

write 0xc300001024 0x2 0x0040
write 0xc300001028 0x1 0x5a
write 0xc30000101c 0x1 0x01
writel 0xc30000100c 0x20000000
write 0xc300001016 0x3 0x80a080
write 0xc300003002 0x1 0x80
^^^ Now we start to see what looks like MMIO accesses. And if we look at
the output of -trace pci\* we will find that the 0xc3 value we wrote
above, configured an MMIO range at 0xc300000000. That is why the MMIO
accesses are close to that address.

write 0x5c 0x1 0x10
^^^ This I am guessing is a DMA command. Usually I know this simply by
looking at the [DMA] annotations in the input file to
reorder_fuzzer_qtest_trace.py. This just means that the device tried to
read from this location in memory, so the fuzzer placed some data there.

Beyond just broadly seeing that there are some initial PCI
configurations on registers 0xCF8/0xCFC, some accesses to addresses that
look like an MMIO range, and one line that probably puts one byte at
address 0x5c in ram, I can't really tell anything else just by looking
at the trace. To write the descriptions above, I had to look at
PCI-related resources. Im not convinced that reordering the accesses
will really help much with this. Probably the best aid I found for
understanding traces are good trace events (when they exist).

-Alex

> 
> > 
> > > +    i = len(newtrace) - 1
> > > +    while i >= 0:
> > > +        tmp_i = newtrace[i]
> > > +        if len(tmp_i) < 2:
> > > +            i -= 1
> > > +            continue
> > > +        print("Delaying ", newtrace[i])
> > > +        for j in reversed(range(i+1, len(newtrace)+1)):
> > > +            newtrace.insert(j, tmp_i)
> > > +            del newtrace[i]
> > > +            if check_if_trace_crashes(newtrace, outpath):
> > > +                break
> > > +            newtrace.insert(i, tmp_i)
> > > +            del newtrace[j]
> > > +        i -= 1
> > > +
> > > +    assert(check_if_trace_crashes(newtrace, outpath))
> > > +    # maybe another removing round
> > > +
> > >  
> > >  if __name__ == '__main__':
> > >      if len(sys.argv) < 3:
> > > -- 
> > > 2.25.1
> > > 
> 

Re: [PATCH 4/4] fuzz: delay IO until they can't trigger the crash

[Qiuhao Li]

[-- Attachment #1: Type: text/plain, Size: 9763 bytes --]

On Tue, 2020-12-22 at 13:30 -0500, Alexander Bulekov wrote:
> On 201222 1922, Qiuhao Li wrote:
> > On Mon, 2020-12-21 at 16:17 -0500, Alexander Bulekov wrote:
> > > On 201220 0256, Qiuhao Li wrote:
> > > > Since programmers usually trigger an IO just before they need
> > > > it.
> > > > Try to
> > > > delay some IO instructions may help us better understanding the
> > > > timing
> > > > context when debug.
> > > >
> > > > Tested with Bug 1908062. Refined vs. Original result:
> > > >
> > > > outl 0xcf8 0x8000081c            outl 0xcf8 0x0
> > > > outb 0xcfc 0xc3                | outl 0xcf8 0x8000081c
> > > > outl 0xcf8 0x80000804          | outb 0xcfc 0xc3
> > > > outl 0xcfc 0x10000006          | outl 0xcf8 0x80000804
> > > > write 0xc300001028 0x1 0x5a    | outl 0xcfc 0x10000006
> > > > write 0xc300001024 0x2 0x10    | write 0xc300001028 0x1 0x5a
> > > > write 0xc30000101c 0x1 0x01    | writel 0xc30000100c 0x2a6f6c63
> > > > write 0xc300003002 0x1 0x0     v write 0xc300001024 0x2 0x10
> > > > write 0x5c 0x1 0x10              write 0xc30000101c 0x1 0x01
> > > > writel 0xc30000100c 0x2a6f6c63   write 0xc300001018 0x1 0x80
> > > > write 0xc300001018 0x1 0x80      write 0x5c 0x1 0x10
> > > > outl 0xcf8 0x0                   write 0xc300003002 0x1 0x0
> > > >
> > >
> > > In this example, I can remove the outl 0xcf8 0x0, and I still see
> > > the
> > > crash, so maybe the 1st step in the minimizer is failing
> > > somewhere..
> >
> > I think it might because of our one-time scan and remove strategy,
> > which is not suitable for timing dependent instructions.
> >
> > For example, instruction A will indicate an address where the
> > config
> > chunk locates, and instruction B will make the configuration
> > active. If
> > we have the following instruction sequence:
> >
> > ...
> > A1
> > B1
> > A2
> > B2
> > ...
> >
> > A2 and B2 are the actual instructions that trigger the bug.
> >
> > If we scan from top to bottom, after we remove A1, the behavior of
> > B1
> > might be unknowable, including not to crash the program. But we
> > will
> > successfully remove B1 later cause A2 and B2 will crash the process
> > anyway:
> >
> > ...
> > A1
> > A2
> > B2
> > ...
> >
> > Now one more trimming will remove A1.
> >
> > As for the example I gave, the instructions before the delaying
> > minimizer are like this:
> >
> > outl 0xcf8 0x8000081c
> > outb 0xcfc 0xc3
> > outl 0xcf8 0x0                <--- The A instruction, didn't be
> > removed
> > (outl 0xcfc 0x0)              <--- The B instruction, removed
> > outl 0xcf8 0x80000804
> > outl 0xcfc 0x10000006
> > write 0xc300001024 0x2 0x10
> > write 0xc300001028 0x1 0x5a
> > write 0xc30000101c 0x1 0x01
> > writel 0xc30000100c 0x2a6f6c63
> > write 0xc300001018 0x1 0x80
> > write 0x5c 0x1 0x10
> > write 0xc300003002 0x1 0x0
> >
> > If we run the remove minimizer again, The A instruction outl 0xcf8
> > 0x0
> > will be removed.
> >
> > Since we only remove instructions, this iterative algorithm is
> > converging. Maybe we can keep removing the trace until the
> > len(newtrace) become unchanged.
> >
>
> I found a bunch of work related to this "test-case minimization".
> There
> are algorithms such as "ddmin" that try to tackle this. There might
> be
> some interesting ideas there.

Thanks, I will have a look.

> I think in the perfect case, we would need to be able to remove A and
> B
> at the same time. You described the situation where B1 might lead to
> a
> bad state without A1, but there is also the possibility that A1 might
> leave bad state around, without B1. And both of these might be true
> at
> the same time :) Probably not something we encounter very often,
> though.

You are right, and even there can be three instructions which must be removed together ;) But for now, how about we just add a if(len(newtrace) == old_len) loop  around remove minimizer? No harm.

Do you think this kind of dependence will exist in bits of the write/out commands? How about adding if(num_bits(data) == old_num) loop around the setting zero minimizer?

> > > Is the Refined one better? To me the original one read as:
> > > "Do a bunch of PCI configuration to map an MMIO BAR, then
> > > interact
> > > with
> > > the MMIO range and trigger some DMA activity". I also know
> > > exactly
> > > the
> > > line that will trigger the DMA activity and access 0x5c. With the
> > > refined one, I'm not so sure. Which line now causes the DMA read
> > > from
> > > 0x5c? writel 0xc30000100c? write 0xc300001018?
> > > Is there another example where this type of reordering makes the
> > > result
> > > easier to read?
> > >
> > > > Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> > > > ---
> > > >  scripts/oss-fuzz/minimize_qtest_trace.py | 21
> > > > +++++++++++++++++++++
> > > >  1 file changed, 21 insertions(+)
> > > >
> > > > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > index f3e88064c4..da7aa73b3c 100755
> > > > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > @@ -214,6 +214,27 @@ def minimize_trace(inpath, outpath):
> > > >
> > > >      assert(check_if_trace_crashes(newtrace, outpath))
> > > >
> > > > +    # delay IO instructions until they can't trigger the crash
> > > > +    # Note: O(n^2) and many timeouts, kinda slow
> > >
> > > Maybe do a binary search instead of a linear scan for the optimal
> > > position
> > > to save some time?
> > > Also, if you re-run this multiple times, you can end up with
> > > different
> > > results, since some lines might not really be tied to a position
> > > (e.g.
> > > the outl cf8 0x0 in your example). Maybe it's not a problem, but
> > > i'm
> > > still not sure that this is making the result easier to read.
> > > -Alex
> >
> > I'm not familiar with the PCI configuration and DMA mechanism in
> > QEMU.
> > This patch is just random thinking based on empiricism. Maybe I
> > should
> > add the "RFC" tag :). In version 2, I won't post this patch.
> >
> > BTW, may I ask where I can learn about these IO emulations? How do
> > you
> > know the address corresponding to the PCI bar and DMA?
>
> On PCs, the PCI configuration space is accessed using two I/O ports:
> 0xcfc and 0xcf8. To interact further with a  PCI device, you have to
> configure its BARs (i.e. the Port IO and memory ranges that will map
> to
> device registers).
> https://en.wikipedia.org/wiki/PCI_configuration_space#Bus_enumeration
>
> So we can look at the trace again. First there are no virtio-vga
> MMIO/PIO
> ranges accessible, so the only thing the fuzzer can do is interact
> with
> its PCI configuration space using 0xCF8/CFC:
>
> outl 0xcf8 0x8000081c
> outb 0xcfc 0xc3
> ^^^ The above two lines write the value 0xc3 to PCI config address
> 0x1c
> for the vga device. You can confirm this by running the testcase with
> -trace pci\*. 0x1c is the location of the PCI register that
> represents
> BAR #3 for the device.
> outl 0xcf8 0x80000804
> outb 0xcfc 0x06
> ^^^ These two lines write to the PCI command register (0x04) to allow
> the device to respond to memory accesses.
>
> write 0xc300001024 0x2 0x0040
> write 0xc300001028 0x1 0x5a
> write 0xc30000101c 0x1 0x01
> writel 0xc30000100c 0x20000000
> write 0xc300001016 0x3 0x80a080
> write 0xc300003002 0x1 0x80
> ^^^ Now we start to see what looks like MMIO accesses. And if we look
> at
> the output of -trace pci\* we will find that the 0xc3 value we wrote
> above, configured an MMIO range at 0xc300000000. That is why the MMIO
> accesses are close to that address.
>
> write 0x5c 0x1 0x10
> ^^^ This I am guessing is a DMA command. Usually I know this simply
> by
> looking at the [DMA] annotations in the input file to
> reorder_fuzzer_qtest_trace.py. This just means that the device tried
> to
> read from this location in memory, so the fuzzer placed some data
> there.
>
> Beyond just broadly seeing that there are some initial PCI
> configurations on registers 0xCF8/0xCFC, some accesses to addresses
> that
> look like an MMIO range, and one line that probably puts one byte at
> address 0x5c in ram, I can't really tell anything else just by
> looking
> at the trace. To write the descriptions above, I had to look at
> PCI-related resources. Im not convinced that reordering the accesses
> will really help much with this. Probably the best aid I found for
> understanding traces are good trace events (when they exist).
>
> -Alex

Thank you so much for such a detailed and patient explanation! I will use tracing to analyze IO events in the future.

The delaying minimizer seems not constructive. I won't post it in version 2.

Thanks again :)

> > > > +    i = len(newtrace) - 1
> > > > +    while i >= 0:
> > > > +        tmp_i = newtrace[i]
> > > > +        if len(tmp_i) < 2:
> > > > +            i -= 1
> > > > +            continue
> > > > +        print("Delaying ", newtrace[i])
> > > > +        for j in reversed(range(i+1, len(newtrace)+1)):
> > > > +            newtrace.insert(j, tmp_i)
> > > > +            del newtrace[i]
> > > > +            if check_if_trace_crashes(newtrace, outpath):
> > > > +                break
> > > > +            newtrace.insert(i, tmp_i)
> > > > +            del newtrace[j]
> > > > +        i -= 1
> > > > +
> > > > +    assert(check_if_trace_crashes(newtrace, outpath))
> > > > +    # maybe another removing round
> > > > +
> > > >
> > > >  if __name__ == '__main__':
> > > >      if len(sys.argv) < 3:
> > > > --
> > > > 2.25.1
> > > >

[-- Attachment #2: Type: text/html, Size: 17078 bytes --]

Re: [PATCH 4/4] fuzz: delay IO until they can't trigger the crash

[Alexander Bulekov]

On 201223 0920, Qiuhao Li wrote:
> On Tue, 2020-12-22 at 13:30 -0500, Alexander Bulekov wrote:
> > On 201222 1922, Qiuhao Li wrote:
> > > On Mon, 2020-12-21 at 16:17 -0500, Alexander Bulekov wrote:
> > > > On 201220 0256, Qiuhao Li wrote:
> > > > > Since programmers usually trigger an IO just before they need
> > > > > it.
> > > > > Try to
> > > > > delay some IO instructions may help us better understanding the
> > > > > timing
> > > > > context when debug.
> > > > >
> > > > > Tested with Bug 1908062. Refined vs. Original result:
> > > > >
> > > > > outl 0xcf8 0x8000081c            outl 0xcf8 0x0
> > > > > outb 0xcfc 0xc3                | outl 0xcf8 0x8000081c
> > > > > outl 0xcf8 0x80000804          | outb 0xcfc 0xc3
> > > > > outl 0xcfc 0x10000006          | outl 0xcf8 0x80000804
> > > > > write 0xc300001028 0x1 0x5a    | outl 0xcfc 0x10000006
> > > > > write 0xc300001024 0x2 0x10    | write 0xc300001028 0x1 0x5a
> > > > > write 0xc30000101c 0x1 0x01    | writel 0xc30000100c 0x2a6f6c63
> > > > > write 0xc300003002 0x1 0x0     v write 0xc300001024 0x2 0x10
> > > > > write 0x5c 0x1 0x10              write 0xc30000101c 0x1 0x01
> > > > > writel 0xc30000100c 0x2a6f6c63   write 0xc300001018 0x1 0x80
> > > > > write 0xc300001018 0x1 0x80      write 0x5c 0x1 0x10
> > > > > outl 0xcf8 0x0                   write 0xc300003002 0x1 0x0
> > > > >
> > > >
> > > > In this example, I can remove the outl 0xcf8 0x0, and I still see
> > > > the
> > > > crash, so maybe the 1st step in the minimizer is failing
> > > > somewhere..
> > >
> > > I think it might because of our one-time scan and remove strategy,
> > > which is not suitable for timing dependent instructions.
> > >
> > > For example, instruction A will indicate an address where the
> > > config
> > > chunk locates, and instruction B will make the configuration
> > > active. If
> > > we have the following instruction sequence:
> > >
> > > ...
> > > A1
> > > B1
> > > A2
> > > B2
> > > ...
> > >
> > > A2 and B2 are the actual instructions that trigger the bug.
> > >
> > > If we scan from top to bottom, after we remove A1, the behavior of
> > > B1
> > > might be unknowable, including not to crash the program. But we
> > > will
> > > successfully remove B1 later cause A2 and B2 will crash the process
> > > anyway:
> > >
> > > ...
> > > A1
> > > A2
> > > B2
> > > ...
> > >
> > > Now one more trimming will remove A1.
> > >
> > > As for the example I gave, the instructions before the delaying
> > > minimizer are like this:
> > >
> > > outl 0xcf8 0x8000081c
> > > outb 0xcfc 0xc3
> > > outl 0xcf8 0x0                <--- The A instruction, didn't be
> > > removed
> > > (outl 0xcfc 0x0)              <--- The B instruction, removed
> > > outl 0xcf8 0x80000804
> > > outl 0xcfc 0x10000006
> > > write 0xc300001024 0x2 0x10
> > > write 0xc300001028 0x1 0x5a
> > > write 0xc30000101c 0x1 0x01
> > > writel 0xc30000100c 0x2a6f6c63
> > > write 0xc300001018 0x1 0x80
> > > write 0x5c 0x1 0x10
> > > write 0xc300003002 0x1 0x0
> > >
> > > If we run the remove minimizer again, The A instruction outl 0xcf8
> > > 0x0
> > > will be removed.
> > >
> > > Since we only remove instructions, this iterative algorithm is
> > > converging. Maybe we can keep removing the trace until the
> > > len(newtrace) become unchanged.
> > >
> >
> > I found a bunch of work related to this "test-case minimization".
> > There
> > are algorithms such as "ddmin" that try to tackle this. There might
> > be
> > some interesting ideas there.
> 
> Thanks, I will have a look.
> 
> > I think in the perfect case, we would need to be able to remove A and
> > B
> > at the same time. You described the situation where B1 might lead to
> > a
> > bad state without A1, but there is also the possibility that A1 might
> > leave bad state around, without B1. And both of these might be true
> > at
> > the same time :) Probably not something we encounter very often,
> > though.
> 
> You are right, and even there can be three instructions which must be removed together ;) But for now, how about we just add a if(len(newtrace) == old_len) loop  around remove minimizer? No harm.
> 
Sounds good to me. Certainly an improvement over what we have now.

> Do you think this kind of dependence will exist in bits of the write/out commands? How about adding if(num_bits(data) == old_num) loop around the setting zero minimizer?
> 

It may be, however, I am worried about the peformance penalty of
bit-wise minimization. If the penalty is too great, it might make sense
to make bit-wise minimzation optional (argv or env variable).

As a side note, I think I just minimized one of the largest reproducers
reported by OSS-Fuzz so-far (by qtest command count):
https://bugs.launchpad.net/qemu/+bug/1909261/comments/2

It's 320k bytes (6500 QTest instructions). The current script got it
down to 61k (2846 instructions), and it probably took 2+ hours.
This might be a good benchmark for testing improvements to the script
both in terms of time to minimize, and degree of minimization :)
-Alex

> > > > Is the Refined one better? To me the original one read as:
> > > > "Do a bunch of PCI configuration to map an MMIO BAR, then
> > > > interact
> > > > with
> > > > the MMIO range and trigger some DMA activity". I also know
> > > > exactly
> > > > the
> > > > line that will trigger the DMA activity and access 0x5c. With the
> > > > refined one, I'm not so sure. Which line now causes the DMA read
> > > > from
> > > > 0x5c? writel 0xc30000100c? write 0xc300001018?
> > > > Is there another example where this type of reordering makes the
> > > > result
> > > > easier to read?
> > > >
> > > > > Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
> > > > > ---
> > > > >  scripts/oss-fuzz/minimize_qtest_trace.py | 21
> > > > > +++++++++++++++++++++
> > > > >  1 file changed, 21 insertions(+)
> > > > >
> > > > > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > > index f3e88064c4..da7aa73b3c 100755
> > > > > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > > @@ -214,6 +214,27 @@ def minimize_trace(inpath, outpath):
> > > > >
> > > > >      assert(check_if_trace_crashes(newtrace, outpath))
> > > > >
> > > > > +    # delay IO instructions until they can't trigger the crash
> > > > > +    # Note: O(n^2) and many timeouts, kinda slow
> > > >
> > > > Maybe do a binary search instead of a linear scan for the optimal
> > > > position
> > > > to save some time?
> > > > Also, if you re-run this multiple times, you can end up with
> > > > different
> > > > results, since some lines might not really be tied to a position
> > > > (e.g.
> > > > the outl cf8 0x0 in your example). Maybe it's not a problem, but
> > > > i'm
> > > > still not sure that this is making the result easier to read.
> > > > -Alex
> > >
> > > I'm not familiar with the PCI configuration and DMA mechanism in
> > > QEMU.
> > > This patch is just random thinking based on empiricism. Maybe I
> > > should
> > > add the "RFC" tag :). In version 2, I won't post this patch.
> > >
> > > BTW, may I ask where I can learn about these IO emulations? How do
> > > you
> > > know the address corresponding to the PCI bar and DMA?
> >
> > On PCs, the PCI configuration space is accessed using two I/O ports:
> > 0xcfc and 0xcf8. To interact further with a  PCI device, you have to
> > configure its BARs (i.e. the Port IO and memory ranges that will map
> > to
> > device registers).
> > https://en.wikipedia.org/wiki/PCI_configuration_space#Bus_enumeration
> >
> > So we can look at the trace again. First there are no virtio-vga
> > MMIO/PIO
> > ranges accessible, so the only thing the fuzzer can do is interact
> > with
> > its PCI configuration space using 0xCF8/CFC:
> >
> > outl 0xcf8 0x8000081c
> > outb 0xcfc 0xc3
> > ^^^ The above two lines write the value 0xc3 to PCI config address
> > 0x1c
> > for the vga device. You can confirm this by running the testcase with
> > -trace pci\*. 0x1c is the location of the PCI register that
> > represents
> > BAR #3 for the device.
> > outl 0xcf8 0x80000804
> > outb 0xcfc 0x06
> > ^^^ These two lines write to the PCI command register (0x04) to allow
> > the device to respond to memory accesses.
> >
> > write 0xc300001024 0x2 0x0040
> > write 0xc300001028 0x1 0x5a
> > write 0xc30000101c 0x1 0x01
> > writel 0xc30000100c 0x20000000
> > write 0xc300001016 0x3 0x80a080
> > write 0xc300003002 0x1 0x80
> > ^^^ Now we start to see what looks like MMIO accesses. And if we look
> > at
> > the output of -trace pci\* we will find that the 0xc3 value we wrote
> > above, configured an MMIO range at 0xc300000000. That is why the MMIO
> > accesses are close to that address.
> >
> > write 0x5c 0x1 0x10
> > ^^^ This I am guessing is a DMA command. Usually I know this simply
> > by
> > looking at the [DMA] annotations in the input file to
> > reorder_fuzzer_qtest_trace.py. This just means that the device tried
> > to
> > read from this location in memory, so the fuzzer placed some data
> > there.
> >
> > Beyond just broadly seeing that there are some initial PCI
> > configurations on registers 0xCF8/0xCFC, some accesses to addresses
> > that
> > look like an MMIO range, and one line that probably puts one byte at
> > address 0x5c in ram, I can't really tell anything else just by
> > looking
> > at the trace. To write the descriptions above, I had to look at
> > PCI-related resources. Im not convinced that reordering the accesses
> > will really help much with this. Probably the best aid I found for
> > understanding traces are good trace events (when they exist).
> >
> > -Alex
> 
> Thank you so much for such a detailed and patient explanation! I will use tracing to analyze IO events in the future.
> 
> The delaying minimizer seems not constructive. I won't post it in version 2.
> 
> Thanks again :)
> 
> > > > > +    i = len(newtrace) - 1
> > > > > +    while i >= 0:
> > > > > +        tmp_i = newtrace[i]
> > > > > +        if len(tmp_i) < 2:
> > > > > +            i -= 1
> > > > > +            continue
> > > > > +        print("Delaying ", newtrace[i])
> > > > > +        for j in reversed(range(i+1, len(newtrace)+1)):
> > > > > +            newtrace.insert(j, tmp_i)
> > > > > +            del newtrace[i]
> > > > > +            if check_if_trace_crashes(newtrace, outpath):
> > > > > +                break
> > > > > +            newtrace.insert(i, tmp_i)
> > > > > +            del newtrace[j]
> > > > > +        i -= 1
> > > > > +
> > > > > +    assert(check_if_trace_crashes(newtrace, outpath))
> > > > > +    # maybe another removing round
> > > > > +
> > > > >
> > > > >  if __name__ == '__main__':
> > > > >      if len(sys.argv) < 3:
> > > > > --
> > > > > 2.25.1
> > > > >