* [PATCH v5 1/7] fuzz: accelerate non-crash detection
2021-01-08 2:44 [PATCH v5 0/7] fuzz: improve crash case minimization Qiuhao Li
@ 2021-01-08 3:12 ` Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 2/7] fuzz: double the IOs to remove for every loop Qiuhao Li
` (6 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Qiuhao Li @ 2021-01-08 3:12 UTC (permalink / raw)
To: alxndr, qemu-devel
Cc: thuth, Qiuhao Li, darren.kenny, bsd, stefanha, pbonzini
We spend much time waiting for the timeout program during the minimization
process until it passes a time limit. This patch hacks the CLOSED (indicates
the redirection file closed) notification in QTest's output if it doesn't
crash.
Test with quadrupled trace input at:
https://bugs.launchpad.net/qemu/+bug/1890333/comments/1
Original version:
real 1m37.246s
user 0m13.069s
sys 0m8.399s
Refined version:
real 0m45.904s
user 0m16.874s
sys 0m10.042s
Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
scripts/oss-fuzz/minimize_qtest_trace.py | 39 ++++++++++++++++--------
1 file changed, 27 insertions(+), 12 deletions(-)
diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5e405a0d5f..57dcaaeba3 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -29,8 +29,14 @@ whether the crash occred. Optionally, manually set a string that idenitifes the
crash by setting CRASH_TOKEN=
""".format((sys.argv[0])))
+deduplication_note = """\n\
+Note: While trimming the input, sometimes the mutated trace triggers a different
+crash output but indicates the same bug. Under this situation, our minimizer is
+incapable of recognizing and stopped from removing it. In the future, we may
+use a more sophisticated crash case deduplication method.
+\n"""
+
def check_if_trace_crashes(trace, path):
- global CRASH_TOKEN
with open(path, "w") as tracefile:
tracefile.write("".join(trace))
@@ -41,18 +47,28 @@ def check_if_trace_crashes(trace, path):
trace_path=path),
shell=True,
stdin=subprocess.PIPE,
- stdout=subprocess.PIPE)
- stdo = rc.communicate()[0]
- output = stdo.decode('unicode_escape')
- if rc.returncode == 137: # Timed Out
- return False
- if len(output.splitlines()) < 2:
- return False
-
+ stdout=subprocess.PIPE,
+ encoding="utf-8")
+ global CRASH_TOKEN
if CRASH_TOKEN is None:
- CRASH_TOKEN = output.splitlines()[-2]
+ try:
+ outs, _ = rc.communicate(timeout=5)
+ CRASH_TOKEN = outs.splitlines()[-2]
+ except subprocess.TimeoutExpired:
+ print("subprocess.TimeoutExpired")
+ return False
+ print("Identifying Crashes by this string: {}".format(CRASH_TOKEN))
+ global deduplication_note
+ print(deduplication_note)
+ return True
- return CRASH_TOKEN in output
+ for line in iter(rc.stdout.readline, b''):
+ if "CLOSED" in line:
+ return False
+ if CRASH_TOKEN in line:
+ return True
+
+ return False
def minimize_trace(inpath, outpath):
@@ -66,7 +82,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[:]
--
2.25.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v5 2/7] fuzz: double the IOs to remove for every loop
2021-01-08 2:44 [PATCH v5 0/7] fuzz: improve crash case minimization Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 1/7] fuzz: accelerate non-crash detection Qiuhao Li
@ 2021-01-08 3:12 ` Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 3/7] fuzz: split write operand using binary approach Qiuhao Li
` (5 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Qiuhao Li @ 2021-01-08 3:12 UTC (permalink / raw)
To: alxndr, qemu-devel
Cc: thuth, Qiuhao Li, darren.kenny, bsd, stefanha, pbonzini
Instead of removing IO instructions one by one, we can try deleting multiple
instructions at once. According to the locality of reference, we double the
number of instructions to remove for the next round and recover it to one
once we fail.
This patch is usually significant for large input.
Test with quadrupled trace input at:
https://bugs.launchpad.net/qemu/+bug/1890333/comments/1
Patched 1/6 version:
real 0m45.904s
user 0m16.874s
sys 0m10.042s
Refined version:
real 0m11.412s
user 0m6.888s
sys 0m3.325s
Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
scripts/oss-fuzz/minimize_qtest_trace.py | 33 +++++++++++++++---------
1 file changed, 21 insertions(+), 12 deletions(-)
diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 57dcaaeba3..cfe8f7854c 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -85,19 +85,28 @@ def minimize_trace(inpath, outpath):
i = 0
newtrace = trace[:]
- # For each line
+ remove_step = 1
while i < len(newtrace):
- # 1.) Try to remove it completely and reproduce the crash. If it works,
- # we're done.
- prior = newtrace[i]
- print("Trying to remove {}".format(newtrace[i]))
- # Try to remove the line completely
- newtrace[i] = ""
+ # 1.) Try to remove lines completely and reproduce the crash.
+ # If it works, we're done.
+ if (i+remove_step) >= len(newtrace):
+ remove_step = 1
+ prior = newtrace[i:i+remove_step]
+ for j in range(i, i+remove_step):
+ newtrace[j] = ""
+ print("Removing {lines} ...".format(lines=prior))
if check_if_trace_crashes(newtrace, outpath):
- i += 1
+ i += remove_step
+ # Double the number of lines to remove for next round
+ remove_step *= 2
continue
- newtrace[i] = prior
-
+ # Failed to remove multiple IOs, fast recovery
+ if remove_step > 1:
+ for j in range(i, i+remove_step):
+ newtrace[j] = prior[j-i]
+ remove_step = 1
+ continue
+ newtrace[i] = prior[0] # remove_step = 1
# 2.) Try to replace write{bwlq} commands with a write addr, len
# command. Since this can require swapping endianness, try both LE and
# BE options. We do this, so we can "trim" the writes in (3)
@@ -118,7 +127,7 @@ def minimize_trace(inpath, outpath):
if(check_if_trace_crashes(newtrace, outpath)):
break
else:
- newtrace[i] = prior
+ newtrace[i] = prior[0]
# 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
@@ -151,7 +160,7 @@ def minimize_trace(inpath, outpath):
if check_if_trace_crashes(newtrace, outpath):
i -= 1
else:
- newtrace[i] = prior
+ newtrace[i] = prior[0]
del newtrace[i+1]
i += 1
check_if_trace_crashes(newtrace, outpath)
--
2.25.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v5 3/7] fuzz: split write operand using binary approach
2021-01-08 2:44 [PATCH v5 0/7] fuzz: improve crash case minimization Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 1/7] fuzz: accelerate non-crash detection Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 2/7] fuzz: double the IOs to remove for every loop Qiuhao Li
@ 2021-01-08 3:12 ` Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 4/7] fuzz: remove IO commands iteratively Qiuhao Li
` (4 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Qiuhao Li @ 2021-01-08 3:12 UTC (permalink / raw)
To: alxndr, qemu-devel
Cc: thuth, Qiuhao Li, darren.kenny, bsd, stefanha, pbonzini
Currently, we split the write commands' data from the middle. If it does not
work, try to move the pivot left by one byte and retry until there is no
space.
But, this method has two flaws:
1. It may fail to trim all unnecessary bytes on the right side.
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.
2. The algorithm complexity is O(n) since we move the pivot byte by byte.
To solve the first issue, we can try a symmetrical position on the right if
we fail on the left. As for the second issue, instead moving by one byte, we
can approach the boundary exponentially, achieving O(log(n)).
Give an example:
xxxxuu len=6
+
|
+
xxx,xuu 6/2=3 fail
+
+--------------+-------------+
| |
+ +
xx,xxuu 6/2^2=1 fail xxxxu,u 6-1=5 success
+ +
+------------------+----+ |
| | +-------------+ u removed
+ +
xx,xxu 5/2=2 fail xxxx,u 6-2=4 success
+
|
+-----------+ u removed
In some rare cases, this algorithm will fail to trim all unnecessary bytes:
xxxxxxxxxuxxxxxx
xxxxxxxx-xuxxxxxx Fail
xxxx-xxxxxuxxxxxx Fail
xxxxxxxxxuxx-xxxx Fail
...
I think the trade-off is worth it.
Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
scripts/oss-fuzz/minimize_qtest_trace.py | 29 ++++++++++++++++--------
1 file changed, 20 insertions(+), 9 deletions(-)
diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index cfe8f7854c..5cf39f4e6e 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -94,7 +94,7 @@ def minimize_trace(inpath, outpath):
prior = newtrace[i:i+remove_step]
for j in range(i, i+remove_step):
newtrace[j] = ""
- print("Removing {lines} ...".format(lines=prior))
+ print("Removing {lines} ...\n".format(lines=prior))
if check_if_trace_crashes(newtrace, outpath):
i += remove_step
# Double the number of lines to remove for next round
@@ -107,9 +107,11 @@ def minimize_trace(inpath, outpath):
remove_step = 1
continue
newtrace[i] = prior[0] # remove_step = 1
+
# 2.) Try to replace write{bwlq} commands with a write addr, len
# command. Since this can require swapping endianness, try both LE and
# BE options. We do this, so we can "trim" the writes in (3)
+
if (newtrace[i].startswith("write") and not
newtrace[i].startswith("write ")):
suffix = newtrace[i].split()[0][-1]
@@ -130,11 +132,15 @@ def minimize_trace(inpath, outpath):
newtrace[i] = prior[0]
# 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
- # there is no space left. The idea is to prune unneccessary bytes from
- # long writes, while accommodating arbitrary MemoryRegion access sizes
- # and alignments.
+ # it into two separate write commands. If splitting the data operand
+ # from length/2^n bytes to the left does not work, try to move the pivot
+ # to the right side, then add one to n, until length/2^n == 0. The idea
+ # is to prune unneccessary bytes from long writes, while accommodating
+ # arbitrary MemoryRegion access sizes and alignments.
+
+ # This algorithm will fail under some rare situations.
+ # e.g., xxxxxxxxxuxxxxxx (u is the unnecessary byte)
+
if newtrace[i].startswith("write "):
addr = int(newtrace[i].split()[1], 16)
length = int(newtrace[i].split()[2], 16)
@@ -143,6 +149,7 @@ def minimize_trace(inpath, outpath):
leftlength = int(length/2)
rightlength = length - leftlength
newtrace.insert(i+1, "")
+ power = 1
while leftlength > 0:
newtrace[i] = "write {addr} {size} 0x{data}\n".format(
addr=hex(addr),
@@ -154,9 +161,13 @@ def minimize_trace(inpath, outpath):
data=data[leftlength*2:])
if check_if_trace_crashes(newtrace, outpath):
break
- else:
- leftlength -= 1
- rightlength += 1
+ # move the pivot to right side
+ if leftlength < rightlength:
+ rightlength, leftlength = leftlength, rightlength
+ continue
+ power += 1
+ leftlength = int(length/pow(2, power))
+ rightlength = length - leftlength
if check_if_trace_crashes(newtrace, outpath):
i -= 1
else:
--
2.25.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v5 4/7] fuzz: remove IO commands iteratively
2021-01-08 2:44 [PATCH v5 0/7] fuzz: improve crash case minimization Qiuhao Li
` (2 preceding siblings ...)
2021-01-08 3:12 ` [PATCH v5 3/7] fuzz: split write operand using binary approach Qiuhao Li
@ 2021-01-08 3:12 ` Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 5/7] fuzz: set bits in operand of write/out to zero Qiuhao Li
` (3 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Qiuhao Li @ 2021-01-08 3:12 UTC (permalink / raw)
To: alxndr, qemu-devel
Cc: thuth, Qiuhao Li, darren.kenny, bsd, stefanha, pbonzini
Now we use a one-time scan and remove strategy in the minimizer,
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.
In the perfect case, we would need to be able to remove A and B (or C!) at
the same time. But for now, let's just add a loop around the minimizer.
Since we only remove instructions, this iterative algorithm is converging.
Tested with Bug 1908062.
Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
scripts/oss-fuzz/minimize_qtest_trace.py | 41 +++++++++++++++---------
1 file changed, 26 insertions(+), 15 deletions(-)
diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5cf39f4e6e..45c1627d32 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -71,21 +71,9 @@ def check_if_trace_crashes(trace, path):
return False
-def minimize_trace(inpath, outpath):
- global TIMEOUT
- with open(inpath) as f:
- trace = f.readlines()
- start = time.time()
- if not check_if_trace_crashes(trace, outpath):
- sys.exit("The input qtest trace didn't cause a crash...")
- end = time.time()
- print("Crashed in {} seconds".format(end-start))
- TIMEOUT = (end-start)*5
- print("Setting the timeout for {} seconds".format(TIMEOUT))
-
- i = 0
- newtrace = trace[:]
+def remove_lines(newtrace, outpath):
remove_step = 1
+ i = 0
while i < len(newtrace):
# 1.) Try to remove lines completely and reproduce the crash.
# If it works, we're done.
@@ -174,7 +162,30 @@ def minimize_trace(inpath, outpath):
newtrace[i] = prior[0]
del newtrace[i+1]
i += 1
- check_if_trace_crashes(newtrace, outpath)
+
+
+def minimize_trace(inpath, outpath):
+ global TIMEOUT
+ with open(inpath) as f:
+ trace = f.readlines()
+ start = time.time()
+ if not check_if_trace_crashes(trace, outpath):
+ sys.exit("The input qtest trace didn't cause a crash...")
+ end = time.time()
+ print("Crashed in {} seconds".format(end-start))
+ TIMEOUT = (end-start)*5
+ print("Setting the timeout for {} seconds".format(TIMEOUT))
+
+ newtrace = trace[:]
+
+ # remove lines
+ old_len = len(newtrace) + 1
+ while(old_len > len(newtrace)):
+ old_len = len(newtrace)
+ remove_lines(newtrace, outpath)
+ newtrace = list(filter(lambda s: s != "", newtrace))
+
+ assert(check_if_trace_crashes(newtrace, outpath))
if __name__ == '__main__':
--
2.25.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v5 5/7] fuzz: set bits in operand of write/out to zero
2021-01-08 2:44 [PATCH v5 0/7] fuzz: improve crash case minimization Qiuhao Li
` (3 preceding siblings ...)
2021-01-08 3:12 ` [PATCH v5 4/7] fuzz: remove IO commands iteratively Qiuhao Li
@ 2021-01-08 3:12 ` Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 6/7] fuzz: add minimization options Qiuhao Li
` (2 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: Qiuhao Li @ 2021-01-08 3:12 UTC (permalink / raw)
To: alxndr, qemu-devel
Cc: thuth, Qiuhao Li, darren.kenny, bsd, stefanha, pbonzini
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.
Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
scripts/oss-fuzz/minimize_qtest_trace.py | 39 ++++++++++++++++++++++++
1 file changed, 39 insertions(+)
diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 45c1627d32..2325b38dbc 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -164,6 +164,42 @@ def remove_lines(newtrace, outpath):
i += 1
+def clear_bits(newtrace, outpath):
+ # 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 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
+
+
def minimize_trace(inpath, outpath):
global TIMEOUT
with open(inpath) as f:
@@ -184,7 +220,10 @@ def minimize_trace(inpath, outpath):
old_len = len(newtrace)
remove_lines(newtrace, outpath)
newtrace = list(filter(lambda s: s != "", newtrace))
+ assert(check_if_trace_crashes(newtrace, outpath))
+ # set bits to zero
+ clear_bits(newtrace, outpath)
assert(check_if_trace_crashes(newtrace, outpath))
--
2.25.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v5 6/7] fuzz: add minimization options
2021-01-08 2:44 [PATCH v5 0/7] fuzz: improve crash case minimization Qiuhao Li
` (4 preceding siblings ...)
2021-01-08 3:12 ` [PATCH v5 5/7] fuzz: set bits in operand of write/out to zero Qiuhao Li
@ 2021-01-08 3:12 ` Qiuhao Li
2021-01-08 3:12 ` [PATCH v5 7/7] fuzz: heuristic split write based on past IOs Qiuhao Li
2021-01-08 4:30 ` [PATCH v5 0/7] fuzz: improve crash case minimization Alexander Bulekov
7 siblings, 0 replies; 10+ messages in thread
From: Qiuhao Li @ 2021-01-08 3:12 UTC (permalink / raw)
To: alxndr, qemu-devel
Cc: thuth, Qiuhao Li, darren.kenny, bsd, stefanha, pbonzini
-M1: remove IO commands iteratively
-M2: try setting bits in operand of write/out to zero
Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
scripts/oss-fuzz/minimize_qtest_trace.py | 30 ++++++++++++++++++++----
1 file changed, 26 insertions(+), 4 deletions(-)
diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 2325b38dbc..8661116075 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -16,6 +16,10 @@ QEMU_PATH = None
TIMEOUT = 5
CRASH_TOKEN = None
+# Minimization levels
+M1 = False # try removing IO commands iteratively
+M2 = False # try setting bits in operand of write/out to zero
+
write_suffix_lookup = {"b": (1, "B"),
"w": (2, "H"),
"l": (4, "L"),
@@ -23,10 +27,20 @@ write_suffix_lookup = {"b": (1, "B"),
def usage():
sys.exit("""\
-Usage: QEMU_PATH="/path/to/qemu" QEMU_ARGS="args" {} input_trace output_trace
+Usage:
+
+QEMU_PATH="/path/to/qemu" QEMU_ARGS="args" {} [Options] 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=
+
+Options:
+
+-M1: enable a loop around the remove minimizer, which may help decrease some
+ timing dependant instructions. Off by default.
+-M2: try setting bits in operand of write/out to zero. Off by default.
+
""".format((sys.argv[0])))
deduplication_note = """\n\
@@ -213,24 +227,32 @@ def minimize_trace(inpath, outpath):
print("Setting the timeout for {} seconds".format(TIMEOUT))
newtrace = trace[:]
+ global M1, M2
# remove lines
old_len = len(newtrace) + 1
while(old_len > len(newtrace)):
old_len = len(newtrace)
+ print("trace lenth = ", old_len)
remove_lines(newtrace, outpath)
+ if not M1 and not M2:
+ break
newtrace = list(filter(lambda s: s != "", newtrace))
assert(check_if_trace_crashes(newtrace, outpath))
# set bits to zero
- clear_bits(newtrace, outpath)
+ if M2:
+ clear_bits(newtrace, outpath)
assert(check_if_trace_crashes(newtrace, outpath))
if __name__ == '__main__':
if len(sys.argv) < 3:
usage()
-
+ if "-M1" in sys.argv:
+ M1 = True
+ if "-M2" in sys.argv:
+ M2 = True
QEMU_PATH = os.getenv("QEMU_PATH")
QEMU_ARGS = os.getenv("QEMU_ARGS")
if QEMU_PATH is None or QEMU_ARGS is None:
@@ -239,4 +261,4 @@ if __name__ == '__main__':
# QEMU_ARGS += " -accel qtest"
CRASH_TOKEN = os.getenv("CRASH_TOKEN")
QEMU_ARGS += " -qtest stdio -monitor none -serial none "
- minimize_trace(sys.argv[1], sys.argv[2])
+ minimize_trace(sys.argv[-2], sys.argv[-1])
--
2.25.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v5 7/7] fuzz: heuristic split write based on past IOs
2021-01-08 2:44 [PATCH v5 0/7] fuzz: improve crash case minimization Qiuhao Li
` (5 preceding siblings ...)
2021-01-08 3:12 ` [PATCH v5 6/7] fuzz: add minimization options Qiuhao Li
@ 2021-01-08 3:12 ` Qiuhao Li
2021-01-08 4:30 ` [PATCH v5 0/7] fuzz: improve crash case minimization Alexander Bulekov
7 siblings, 0 replies; 10+ messages in thread
From: Qiuhao Li @ 2021-01-08 3:12 UTC (permalink / raw)
To: alxndr, qemu-devel
Cc: thuth, Qiuhao Li, darren.kenny, bsd, stefanha, pbonzini
If previous write commands write the same length of data with the same step,
we view it as a hint.
Signed-off-by: Qiuhao Li <Qiuhao.Li@outlook.com>
---
scripts/oss-fuzz/minimize_qtest_trace.py | 56 ++++++++++++++++++++++++
1 file changed, 56 insertions(+)
diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py
index 8661116075..408ae2ac67 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -85,6 +85,43 @@ def check_if_trace_crashes(trace, path):
return False
+# If previous write commands write the same length of data at the same
+# interval, we view it as a hint.
+def split_write_hint(newtrace, i):
+ HINT_LEN = 3 # > 2
+ if i <=(HINT_LEN-1):
+ return None
+
+ #find previous continuous write traces
+ k = 0
+ l = i-1
+ writes = []
+ while (k != HINT_LEN and l >= 0):
+ if newtrace[l].startswith("write "):
+ writes.append(newtrace[l])
+ k += 1
+ l -= 1
+ elif newtrace[l] == "":
+ l -= 1
+ else:
+ return None
+ if k != HINT_LEN:
+ return None
+
+ length = int(writes[0].split()[2], 16)
+ for j in range(1, HINT_LEN):
+ if length != int(writes[j].split()[2], 16):
+ return None
+
+ step = int(writes[0].split()[1], 16) - int(writes[1].split()[1], 16)
+ for j in range(1, HINT_LEN-1):
+ if step != int(writes[j].split()[1], 16) - \
+ int(writes[j+1].split()[1], 16):
+ return None
+
+ return (int(writes[0].split()[1], 16)+step, length)
+
+
def remove_lines(newtrace, outpath):
remove_step = 1
i = 0
@@ -148,6 +185,25 @@ def remove_lines(newtrace, outpath):
length = int(newtrace[i].split()[2], 16)
data = newtrace[i].split()[3][2:]
if length > 1:
+
+ # Can we get a hint from previous writes?
+ hint = split_write_hint(newtrace, i)
+ if hint is not None:
+ hint_addr = hint[0]
+ hint_len = hint[1]
+ if hint_addr >= addr and hint_addr+hint_len <= addr+length:
+ newtrace[i] = "write {addr} {size} 0x{data}\n".format(
+ addr=hex(hint_addr),
+ size=hex(hint_len),
+ data=data[(hint_addr-addr)*2:\
+ (hint_addr-addr)*2+hint_len*2])
+ if check_if_trace_crashes(newtrace, outpath):
+ # next round
+ i += 1
+ continue
+ newtrace[i] = prior[0]
+
+ # Try splitting it using a binary approach
leftlength = int(length/2)
rightlength = length - leftlength
newtrace.insert(i+1, "")
--
2.25.1
^ permalink raw reply related [flat|nested] 10+ messages in thread* Re: [PATCH v5 0/7] fuzz: improve crash case minimization
2021-01-08 2:44 [PATCH v5 0/7] fuzz: improve crash case minimization Qiuhao Li
` (6 preceding siblings ...)
2021-01-08 3:12 ` [PATCH v5 7/7] fuzz: heuristic split write based on past IOs Qiuhao Li
@ 2021-01-08 4:30 ` Alexander Bulekov
2021-01-08 6:19 ` Qiuhao Li
7 siblings, 1 reply; 10+ messages in thread
From: Alexander Bulekov @ 2021-01-08 4:30 UTC (permalink / raw)
To: Qiuhao Li; +Cc: thuth, qemu-devel, darren.kenny, bsd, stefanha, pbonzini
Hi Qiuhao,
Can you add my Reviewed-by: tags to the patches that I have reviewed?
Thanks
-Alex
On 210108 1044, Qiuhao Li wrote:
> Extend and refine the crash case minimization process.
>
> Test input:
> Bug 1909261 full_reproducer
> 6500 QTest instructions (write mostly)
>
> Refined (-M1 minimization level) vs. Original version:
> real 38m31.942s <-- real 532m57.192s
> user 28m18.188s <-- user 89m0.536s
> sys 12m42.239s <-- sys 50m33.074s
> 2558 instructions <-- 2846 instructions
>
> Test Enviroment:
> i7-8550U, 16GB LPDDR3, SSD
> Ubuntu 20.04.1 5.4.0-58-generic x86_64
> Python 3.8.5
>
> v5:
> Fix: send SIGKILL on timeout
> Fix: rename minimization functions
>
> v4:
> Fix: messy diff in [PATCH v3 4/7]
>
> v3:
> Fix: checkpatch.pl errors
>
> v2:
> New: [PATCH v2 1/7]
> New: [PATCH v2 2/7]
> New: [PATCH v2 4/7]
> New: [PATCH v2 6/7]
> New: [PATCH v2 7/7]
> Fix: [PATCH 2/4] split using binary approach
> Fix: [PATCH 3/4] typo in comments
> Discard: [PATCH 1/4] the hardcoded regex match for crash detection
> Discard: [PATCH 4/4] the delaying minimizer
>
> Thanks for the suggestions from:
> Alexander Bulekov
>
> Qiuhao Li (7):
> fuzz: accelerate non-crash detection
> fuzz: double the IOs to remove for every loop
> fuzz: split write operand using binary approach
> fuzz: remove IO commands iteratively
> fuzz: set bits in operand of write/out to zero
> fuzz: add minimization options
> fuzz: heuristic split write based on past IOs
>
> scripts/oss-fuzz/minimize_qtest_trace.py | 257 ++++++++++++++++++-----
> 1 file changed, 210 insertions(+), 47 deletions(-)
>
> --
> 2.25.1
>
^ permalink raw reply [flat|nested] 10+ messages in thread* Re: [PATCH v5 0/7] fuzz: improve crash case minimization
2021-01-08 4:30 ` [PATCH v5 0/7] fuzz: improve crash case minimization Alexander Bulekov
@ 2021-01-08 6:19 ` Qiuhao Li
0 siblings, 0 replies; 10+ messages in thread
From: Qiuhao Li @ 2021-01-08 6:19 UTC (permalink / raw)
To: Alexander Bulekov
Cc: thuth, qemu-devel, darren.kenny, bsd, stefanha, pbonzini
On Thu, 2021-01-07 at 23:30 -0500, Alexander Bulekov wrote:
> Hi Qiuhao,
> Can you add my Reviewed-by: tags to the patches that I have reviewed?
> Thanks
> -Alex
Ok, fixed in version 6, thanks.
>
> On 210108 1044, Qiuhao Li wrote:
> > Extend and refine the crash case minimization process.
> >
> > Test input:
> > Bug 1909261 full_reproducer
> > 6500 QTest instructions (write mostly)
> >
> > Refined (-M1 minimization level) vs. Original version:
> > real 38m31.942s <-- real 532m57.192s
> > user 28m18.188s <-- user 89m0.536s
> > sys 12m42.239s <-- sys 50m33.074s
> > 2558 instructions <-- 2846 instructions
> >
> > Test Enviroment:
> > i7-8550U, 16GB LPDDR3, SSD
> > Ubuntu 20.04.1 5.4.0-58-generic x86_64
> > Python 3.8.5
> >
> > v5:
> > Fix: send SIGKILL on timeout
> > Fix: rename minimization functions
> >
> > v4:
> > Fix: messy diff in [PATCH v3 4/7]
> >
> > v3:
> > Fix: checkpatch.pl errors
> >
> > v2:
> > New: [PATCH v2 1/7]
> > New: [PATCH v2 2/7]
> > New: [PATCH v2 4/7]
> > New: [PATCH v2 6/7]
> > New: [PATCH v2 7/7]
> > Fix: [PATCH 2/4] split using binary approach
> > Fix: [PATCH 3/4] typo in comments
> > Discard: [PATCH 1/4] the hardcoded regex match for crash
> > detection
> > Discard: [PATCH 4/4] the delaying minimizer
> >
> > Thanks for the suggestions from:
> > Alexander Bulekov
> >
> > Qiuhao Li (7):
> > fuzz: accelerate non-crash detection
> > fuzz: double the IOs to remove for every loop
> > fuzz: split write operand using binary approach
> > fuzz: remove IO commands iteratively
> > fuzz: set bits in operand of write/out to zero
> > fuzz: add minimization options
> > fuzz: heuristic split write based on past IOs
> >
> > scripts/oss-fuzz/minimize_qtest_trace.py | 257 ++++++++++++++++++-
> > ----
> > 1 file changed, 210 insertions(+), 47 deletions(-)
> >
> > --
> > 2.25.1
> >
^ permalink raw reply [flat|nested] 10+ messages in thread