[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PULL 06/15] fuzz: split write operand using binary approach
From: |
Thomas Huth |
Subject: |
[PULL 06/15] fuzz: split write operand using binary approach |
Date: |
Mon, 11 Jan 2021 14:43:19 +0100 |
From: Qiuhao Li <Qiuhao.Li@outlook.com>
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>
Reviewed-by: Alexander Bulekov <alxndr@bu.edu>
Tested-by: Alexander Bulekov <alxndr@bu.edu>
Message-Id:
<SYCPR01MB3502D26F1BEB680CBBC169E5FCAB0@SYCPR01MB3502.ausprd01.prod.outlook.com>
Signed-off-by: Thomas Huth <thuth@redhat.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 cacabf2638..af9767f7e4 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -97,7 +97,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
@@ -110,9 +110,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]
@@ -133,11 +135,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)
@@ -146,6 +152,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),
@@ -157,9 +164,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.27.0
- [PULL 00/15] Testing, CI and bsd-user patches, Thomas Huth, 2021/01/11
- [PULL 02/15] qtest/libqtest: fix heap-buffer-overflow in qtest_cb_for_every_machine(), Thomas Huth, 2021/01/11
- [PULL 01/15] gitlab-ci.yml: Add openSUSE Leap 15.2 for gitlab CI/CD, Thomas Huth, 2021/01/11
- [PULL 03/15] util/oslib-win32: Fix _aligned_malloc() arguments order, Thomas Huth, 2021/01/11
- [PULL 05/15] fuzz: double the IOs to remove for every loop, Thomas Huth, 2021/01/11
- [PULL 04/15] fuzz: accelerate non-crash detection, Thomas Huth, 2021/01/11
- [PULL 09/15] fuzz: add minimization options, Thomas Huth, 2021/01/11
- [PULL 08/15] fuzz: set bits in operand of write/out to zero, Thomas Huth, 2021/01/11
- [PULL 10/15] fuzz: heuristic split write based on past IOs, Thomas Huth, 2021/01/11
- [PULL 07/15] fuzz: remove IO commands iteratively, Thomas Huth, 2021/01/11
- [PULL 06/15] fuzz: split write operand using binary approach,
Thomas Huth <=
- [PULL 11/15] bsd-user: regenerate FreeBSD's system call numbers, Thomas Huth, 2021/01/11
- [PULL 13/15] bsd-user: Update strace.list for FreeBSD's latest syscalls, Thomas Huth, 2021/01/11
- [PULL 12/15] bsd-user: move strace OS/arch dependent code to host/arch dirs, Thomas Huth, 2021/01/11
- [PULL 14/15] tests/acceptance: Fix race conditions in s390x tests & skip fedora on gitlab-CI, Thomas Huth, 2021/01/11
- [PULL 15/15] fuzz: map all BARs and enable PCI devices, Thomas Huth, 2021/01/11
- Re: [PULL 00/15] Testing, CI and bsd-user patches, Peter Maydell, 2021/01/11