Re: [RFC PATCH] memory: Fix dma-reentrancy issues at the MMIO level

[Qiuhao Li]

Yes, it still works. Now it looks orthodox:

cat << EOF | ./qemu-system-x86_64 -display none -machine accel=qtest \
-machine q35 -nodefaults -drive file=null-co://,if=none,format=raw,id=disk0 \
-device nvme,drive=disk0,serial=1 -qtest stdio \

outl 0xcf8 0x8810   /* MLBAR (BAR0) – Memory Register Base 
Address, lower 32-bits */
outl 0xcfc 0xe000   /* MMIO Base Address = 0xe000 */
outl 0xcf8 0x8804   /* CMD - Command */
outw 0xcfc 0x06 /* Bus Master Enable, Memory Space Enable */
write 0x1000 0x1 0x02   /* cmd->opcode, NVME_ADM_CMD_GET_LOG_PAGE, 
nvme_get_log() */
write 0x1018 0x4 0x14e0 /* prp1 = 0xe014, NVME_REG_CC, 
nvme_ctrl_reset() */
write 0x1028 0x4 0x0304 /* cmd->cdw10, lid = 3 
NVME_LOG_FW_SLOT_INFO, nvme_fw_log_info, buf_len = 4 */
write 0x1030 0x4 0xfc01 /* cmd->cdw12 = 0x1fc, Log Page Offset, 
trans_len = sizeof(fw_log) - 0x1fc = 4 */
write 0xe024 0x4 0x02000200 /* [3] 3.1.8, Admin Queue Attributes */
write 0xe028 0x4 0x0010 /* asq = 0x1000 */
write 0xe030 0x4 0x0020 /* acq = 0x2000 */
write 0xe014 0x4 0x01004600 /* [3] 3.1.5, Controller Configuration, 
start ctrl */
write 0xe0001000 0x1 0x01   /* [3] 3.1.24, SQyTDBL – Submission Queue y 
Tail Doorbell */
clock_step
EOF

I also wrote a PoC in the guest OS which led to worse result, but the QTest 
reproducer may be enough.



From: Klaus Jensen
Sent: Friday, December 17, 2021 16:37
To: Qiuhao Li
Cc: Alexander Bulekov; qemu-devel@nongnu.org; Laurent Vivier; Peter Maydell; 
Mauro Matteo Cascella; Daniel P. Berrangé; David Hildenbrand; Jason Wang; Bin 
Meng; Li Qiang; Thomas Huth; Peter Xu; Eduardo Habkost; Darren Kenny; Bandan 
Das; Gerd Hoffmann; Stefan Hajnoczi; Paolo Bonzini; Edgar E . Iglesias; 
Philippe Mathieu-Daudé
Subject: Re: [RFC PATCH] memory: Fix dma-reentrancy issues at the MMIO level

On Dec 17 06:27, Qiuhao Li wrote:
> Thanks Alex. It seems this patch sets and checks if the destination device is 
> busy. But how about the data transfers not triggered directly by PMIO/MMIO 
> handlers? For example:
>
> 1. Device A Timer's callback -> Device A MMIO handler
> 2. Device A BH's callback -> Device A MMIO handler
>
> In these situations, when A launches a DMA to itself, the 
> dev->engaged_in_direct_io is not set, so the operation is allowed. Maybe we 
> should log the source and check the destination when we launch data 
> transfers. Is there a way to do that?
>
> Below is a reproducer in NVMe which triggers DMA in a timer's callback 
> (nvme_process_sq). I can still trigger use-after-free exception with this 
> patch on qemu-6.1.0:
>
> cat << EOF | ./qemu-system-x86_64 -display none -machine accel=qtest \
> -machine q35 -nodefaults -drive file=null-co://,if=none,format=raw,id=disk0 \
> -device nvme,drive=disk0,serial=1 -qtest stdio \
>
> outl 0xcf8 0x8810   /* MLBAR (BAR0) – Memory Register Base 
> Address, lower 32-bits */
> outl 0xcfc 0xe000   /* MMIO Base Address = 0xe000 */
> outl 0xcf8 0x8804   /* CMD - Command */
> outw 0xcfc 0x06 /* Bus Master Enable, Memory Space Enable 
> */
> write 0xe024 0x4 0x02000200 /* [3] 3.1.8, Admin Queue Attributes */
> write 0xe028 0x4 0x0010 /* asq = 0x1000 */
> write 0xe030 0x4 0x0020 /* acq = 0x2000 */
> write 0xe014 0x4 0x01004600 /* [3] 3.1.5, Controller Configuration, 
> start ctrl */
> write 0xe0001000 0x1 0x01   /* [3] 3.1.24, SQyTDBL – Submission Queue 
> y Tail Doorbell */
> write 0x1000 0x1 0x02   /* cmd->opcode, 
> NVME_ADM_CMD_GET_LOG_PAGE, nvme_get_log() */
> write 0x1018 0x4 0x14e0 /* prp1 = 0xe014, NVME_REG_CC, 
> nvme_ctrl_reset() */
> write 0x1028 0x4 0x0304 /* cmd->cdw10, lid = 3 
> NVME_LOG_FW_SLOT_INFO, nvme_fw_log_info, buf_len = 4 */
> write 0x1030 0x4 0xfc01 /* cmd->cdw12 = 0x1fc, Log Page Offset, 
> trans_len = sizeof(fw_log) - 0x1fc = 4 */
> clock_step
> EOF
>
> CC: Mauro Matteo Cascella and Philippe Mathieu-Daudé. Should we put the 
> reproducer above to https://gitlab.com/qemu-project/qemu/-/issues/556?
>

This is a good reproducer. Does it still work if you do the `write
0xe0001000 0x1 0x01` at the end instead? It looks weird that you ring
the doorbell prior to writing the command in the queue.

Re: [RFC PATCH] memory: Fix dma-reentrancy issues at the MMIO level

[Qiuhao Li]

Thanks Alex. It seems this patch sets and checks if the destination device is 
busy. But how about the data transfers not triggered directly by PMIO/MMIO 
handlers? For example:

1. Device A Timer's callback -> Device A MMIO handler
2. Device A BH's callback -> Device A MMIO handler

In these situations, when A launches a DMA to itself, the 
dev->engaged_in_direct_io is not set, so the operation is allowed. Maybe we 
should log the source and check the destination when we launch data transfers. 
Is there a way to do that?

Below is a reproducer in NVMe which triggers DMA in a timer's callback 
(nvme_process_sq). I can still trigger use-after-free exception with this patch 
on qemu-6.1.0:

cat << EOF | ./qemu-system-x86_64 -display none -machine accel=qtest \
-machine q35 -nodefaults -drive file=null-co://,if=none,format=raw,id=disk0 \
-device nvme,drive=disk0,serial=1 -qtest stdio \

outl 0xcf8 0x8810   /* MLBAR (BAR0) – Memory Register Base 
Address, lower 32-bits */
outl 0xcfc 0xe000   /* MMIO Base Address = 0xe000 */
outl 0xcf8 0x8804   /* CMD - Command */
outw 0xcfc 0x06 /* Bus Master Enable, Memory Space Enable */
write 0xe024 0x4 0x02000200 /* [3] 3.1.8, Admin Queue Attributes */
write 0xe028 0x4 0x0010 /* asq = 0x1000 */
write 0xe030 0x4 0x0020 /* acq = 0x2000 */
write 0xe014 0x4 0x01004600 /* [3] 3.1.5, Controller Configuration, 
start ctrl */
write 0xe0001000 0x1 0x01   /* [3] 3.1.24, SQyTDBL – Submission Queue y 
Tail Doorbell */
write 0x1000 0x1 0x02   /* cmd->opcode, NVME_ADM_CMD_GET_LOG_PAGE, 
nvme_get_log() */
write 0x1018 0x4 0x14e0 /* prp1 = 0xe014, NVME_REG_CC, 
nvme_ctrl_reset() */
write 0x1028 0x4 0x0304 /* cmd->cdw10, lid = 3 
NVME_LOG_FW_SLOT_INFO, nvme_fw_log_info, buf_len = 4 */
write 0x1030 0x4 0xfc01 /* cmd->cdw12 = 0x1fc, Log Page Offset, 
trans_len = sizeof(fw_log) - 0x1fc = 4 */
clock_step
EOF

CC: Mauro Matteo Cascella and Philippe Mathieu-Daudé. Should we put the 
reproducer above to https://gitlab.com/qemu-project/qemu/-/issues/556?


From: Alexander Bulekov 
Sent: Friday, December 17, 2021 11:08
To: qemu-devel@nongnu.org 
Cc: Alexander Bulekov ; Philippe Mathieu-Daudé 
; Mauro Matteo Cascella ; Qiuhao Li 
; Peter Xu ; Jason Wang 
; David Hildenbrand ; Gerd Hoffmann 
; Peter Maydell ; Li Qiang 
; Thomas Huth ; Laurent Vivier 
; Bandan Das ; Edgar E . Iglesias 
; Darren Kenny ; Bin Meng 
; Paolo Bonzini ; Stefan Hajnoczi 
; Daniel P. Berrangé ; Eduardo 
Habkost 
Subject: [RFC PATCH] memory: Fix dma-reentrancy issues at the MMIO level

Here's my shot at fixing dma-reentracy issues. This patch adds a flag to
the DeviceState, which is set/checked when we call an accessor
associated with the device's IO MRs.

The problem, in short, as I understand it: For the vast majority of
cases, we want to prevent a device from accessing it's own PIO/MMIO
regions over DMA.

This patch/solution is based on some assumptions:
1. DMA accesses that hit mmio regions are only dangerous if they end up
interacting with memory-regions belonging to the device initiating the
DMA.
Not dangerous:  sdhci_pio->dma_write->e1000_mmio
Dangerous:  sdhci_pio->dma_write->sdhci_mmio

2. Most devices do not interact with their own PIO/MMIO memory-regions
using DMA.

3. There is no way for there to be multiple simultaneous accesses to a
device's PIO/MMIO memory-regions.

4. All devices are QOMified :-)

With this patch, I wasn't able to reproduce the issues being tracked
here, with QTest reproducers:
https://gitlab.com/qemu-project/qemu/-/issues/556

This passes the i386 qos/qtests for me and I was able to boot some linux/windows
VMs with basic devices configured, without any apparent problems.

Cc: Philippe Mathieu-Daudé 
Cc: Mauro Matteo Cascella 
Cc: Qiuhao Li 
Cc: Peter Xu 
Cc: Jason Wang 
Cc: David Hildenbrand 
Cc: Gerd Hoffmann 
Cc: Peter Maydell 
Cc: Li Qiang 
Cc: Thomas Huth 
Cc: Laurent Vivier 
Cc: Bandan Das 
Cc: Edgar E. Iglesias 
Cc: Darren Kenny 
Cc: Bin Meng 
Cc: Paolo Bonzini 
Cc: Stefan Hajnoczi 

Signed-off-by: Alexander Bulekov 
---
 include/hw/qdev-core.h |  1 +
 softmmu/memory.c   | 15 +++
 softmmu/trace-events   |  1 +
 3 files changed, 17 insertions(+)

diff --git a/include/hw/qdev-core.h b/include/hw/qdev-core.h
index 20d3066595..32f7c779ab 100644
--- a/include/hw/qdev-core.h
+++ b/include/hw/qdev-core.h
@@ -193,6 +193,7 @@ struct DeviceState {
 int instance_id_alias;
 int alias_required_for_version;
 ResettableState reset;
+int engaged_in_direct_io;
 };

 struct DeviceListener {
diff --git a/softmmu/memory.c b/softmmu/memory.c
index 7340e19ff5..255c3c602f 100644
--- a/softmmu/memory.c
+++ b/softmmu/memory.c
@@ -532,6 +532,7 @@ static MemTxResult access_with_adjusted_size(hwaddr

Re: Possible reward for fuzzer bug fixes? Secure Open Source Rewards Program

[Qiuhao Li]

Sounds great. How about mentioning this program on the Security Process web 
page [1]? Hackers who report vulnerabilities may be interested in fixing bugs.

Just curious. Why didn't those bugs [2] get fixed before disclosure? It seems 
SD and virtio-9p are maintained now.

[1] https://www.qemu.org/contribute/security-process/
[2] 
https://bugs.chromium.org/p/oss-fuzz/issues/list?sort=-reported&q=Type%3DBug-Security%20label%3ADeadline-Exceeded%20qemu&can=2


From: Alexander Bulekov 
Sent: Thursday, October 28, 2021 22:48
To: qemu-devel@nongnu.org 
Cc: Paolo Bonzini ; Bandan Das ; Stefan 
Hajnoczi ; Thomas Huth ; Darren Kenny 
; Qiuhao Li 
Subject: Possible reward for fuzzer bug fixes? Secure Open Source Rewards 
Program

Recently a pilot for the Secure Open Source Rewards program was
announced [1]. Currently this program is run by the Linux Foundation and
sponsored by the Google Open Source Security Team.

The page mentions that patches for issues discovered by OSS-Fuzz may be
eligible for rewards. This seems like it could be a good incentive for
fixing fuzzer bugs.

A couple notes:
 * The program also rewards contributions besides fuzzer-bug fixes.
   Check out the page for full details.
 * It seems that QEMU would qualify for this program. The page mentions
   that the project should have a greater than 0.6 OpenSSF Criticality
   Score [2]. This score factors in statistics collected from github
   (sic!). QEMU's score is currently 0.81078
 * Not limited to individual contributors. Vendors can also qualify for
   rewards.
 * Work completed before Oct 1, 2021 does not qualify.
 * Individuals in some sanctioned countries are not eligible.
 * The process seems to be:
1. Send a fix upstream
2. Get it accepted
3. Fill out a form to apply for a reward

Any thoughts about this? Should this be something we document/advertise
somewhere, so developers are aware of this opportunity?

[1] https://sos.dev/
[2] https://github.com/ossf/criticality_score

-Alex

[PATCH] MAINTAINERS: add fuzzing reviewer

[Qiuhao Li]

To keep me cc-ed when something changes. Suggested by Alexander.

https://lists.gnu.org/archive/html/qemu-devel/2021-08/msg03631.html

Signed-off-by: Qiuhao Li 
---
 MAINTAINERS | 1 +
 1 file changed, 1 insertion(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index 6b3697962c..3a979b1bc7 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -2706,6 +2706,7 @@ R: Paolo Bonzini 
 R: Bandan Das 
 R: Stefan Hajnoczi 
 R: Thomas Huth 
+R: Qiuhao Li 
 S: Maintained
 F: tests/qtest/fuzz/
 F: tests/qtest/fuzz-*test.c
-- 
2.30.2

Re: fuzz: fuzz_dma_read_cb() may overlap with MMIO regions

[Qiuhao Li]

Aha! Nice patch.

My fault. I will search first next time :)

Thanks.
  Qiuhao Li

On Mon, 2021-08-23 at 08:41 -0400, Alexander Bulekov wrote:
> On 210823 2034, Qiuhao Li wrote:
> > I think the check in fuzz_dma_read_cb() is buggy because it doesn't
> > consider when the write address is not in the mmio region but can
> > overlap. For example, the mmio region is 0xe000 to 0xe0001000,
> > and
> > the write address is 0xd000 (not ram) and length is 0x2000. In
> > this
> > case, the address_space_translate() will return the sparse_mem_mr
> > we
> > created, thus bypassing the check and call qtest_memwrite().
> > 
> > Perhaps we need more detailed checks to ensure that the entire
> > write
> > operation occurs in the ram or won't overlap with mmio regions.
> > What do
> > you think?
> > 
> > 
> 
> Good catch. I think this will fix that:
> https://lore.kernel.org/qemu-devel/20210713150037.9297-2-alx...@bu.edu/
> 
> I mentioned that there were some fixes waiting for the 6.1 release,
> but
> didn't realize you were talking about what seems to be the same
> issue.
> -Alex

fuzz: fuzz_dma_read_cb() may overlap with MMIO regions

[Qiuhao Li]

I think the check in fuzz_dma_read_cb() is buggy because it doesn't
consider when the write address is not in the mmio region but can
overlap. For example, the mmio region is 0xe000 to 0xe0001000, and
the write address is 0xd000 (not ram) and length is 0x2000. In this
case, the address_space_translate() will return the sparse_mem_mr we
created, thus bypassing the check and call qtest_memwrite().

Perhaps we need more detailed checks to ensure that the entire write
operation occurs in the ram or won't overlap with mmio regions. What do
you think?


mr1 = address_space_translate(first_cpu->as,
  addr, &addr1, &l, true,
  MEMTXATTRS_UNSPECIFIED);

if (!(memory_region_is_ram(mr1) ||
  memory_region_is_romd(mr1)) && mr1 != sparse_mem_mr) {
l = memory_access_size(mr1, l, addr1);
} else {
/* ROM/RAM case */
// mr1 == sparse_mem_mr but it's not RAM or ROM <--
// May overlap with mmio regions<--
...
qtest_memwrite(qts_global, addr, buf, l);


Thanks.
  Qiuhao Li

On Mon, 2021-08-23 at 04:14 -0400, Alexander Bulekov wrote:
> I'm not sure I understand. We try to avoid writing to MMIO regions in
> fuzz_dma_read_cb to avoid such false-positives. E.g. that's why we have
> code to do address_space_translate and manually walk the AddressSpace
> and verify that we are writing to RAM, before doing the actual
> qtest_memwrite. There is a fix to that code that need to be applied,
> but
> those have to wait for the 6.1 release. BTW, since this is about the
> generic-fuzzer rather than this bug, I cc-ed qemu-devel. Let's continue
> the discussion there.
> 
> -Alex
> 
> On 210823 0132, 李秋豪 (@QiuhaoLi) wrote:
> > 
> > 
> > 
> > 李秋豪 commented on a discussion:
> > https://gitlab.com/qemu-project/qemu/-/issues/541#note_657305687
> > 
> > Ok, I add a reply to my report about #540 and #541.
> > 
> > Btw, it suddenly occurred to me that our generic-fuzzer can also make
> > reentry issues. For example, a device tries to read from a mmio
> > region while being fuzzed, but the fuzz_dma_read_cb() will write to
> > that region, thus leading to positive-false reentry issues. In short,
> > we change a read action to write. Should we add checks?
> > 
> > -- 
> > Reply to this email directly or view it on GitLab:
> > https://gitlab.com/qemu-project/qemu/-/issues/541#note_657305687
> > You're receiving this email because of your account on gitlab.com.
> > 
> > 
> 

Re: [Question] fuzz: double-fetches in a memory region map session

[Qiuhao Li]

On Fri, 2021-08-13 at 06:50 -0400, Alexander Bulekov wrote:
> > 
> > My question is about address_space_map() -- How do we emulate double-
> > fetch
> > bugs in the same map/unmap session? For example:
> > 
> 
> Hi Qiuhao,
> Right now we don't. One strategy would be to use mprotect. When the
> code
> fetches data the first time, we get a SEGV, where we unprotect the
> page,
> write a pattern, and enable single-stepping. Then, after the
> single-step, re-protect the page, and disable single-step.
> 

Brilliant! I can always get a lot of inspiration from you :)

> On OSS-Fuzz, we disabled double-fetch detection, for now, as we did not
> want reproducers for normal-bugs to inadvertently contain
> double-fetches. To make the double-fetch detection useful for
> developers, we probably need to limit the double fetch capability to
> only fill the DMA regions twice, rather than 10 or 20 times. Then, in
> the report, we could give the call-stacks (from the SEGV handler, or
> dma_read hook) of the exact locations in the code that read from the
> same address twice.

Got it, this is indeed the most practical solution. I will try to
detect double-fetch bugs via pattern-based analysis [1]. But it may be
hard to write PoCs to convince and help developers fix bugs, and we
can't identify those bugs caused by the compiler [2] or preprocessor.

[1]
https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/wang-pengfei

[2]
https://www.voidsecurity.in/2018/08/from-compiler-optimization-to-code.html

Thanks,
  Qiuhao Li

Re: About libfuzzer in qemu

[Qiuhao Li]

On Thu, 2021-03-04 at 10:23 -0500, Alexander Bulekov wrote:
> On 210304 1843, Yan Zhiqiang wrote:
> > Hello Alex,
> > I'm learning the fuzz in QEMU recently, I review the fuzz code
> > under
> > /tests/qtest/fuzz which is written by you.
> > I learn a lot from it, but I stuck when I want to debug the fuzz
> > code.
> > I use the gdb with command as follows:
> > 
> > >  gdb -q --args ./qemu-fuzz-i386 --fuzz-target=generic-fuzz-
> > > virtio-vga
> > > ./fuzz-output
> > 
> > and set breakpoint at generic_fuzz.c:generic_fuzz.
> > It acctually stop when hit the breakpoint. But the function
> > argument Size
> > is zero and then goto _Exit(0). (try many times but always the
> > same)
> 
> Hi Zhiqiang,
> Happy to have more people look at the fuzzing code.
> We run each input in a forked process. Maybe you need to run 
> "set follow-fork-mode child" in gdb?

Hi Alex,

Just curious why you choose to use the libfuzzer at first instead of
AFL and its descendants like AFL++ since they use a forkserver by
design, and the performance also seems better [1].

[1] https://www.fuzzbench.com/reports/2021-02-13-paper/index.html

Thank you.
  Qiuhao Li

[Bug 1913510] [NEW] [Fuzz] qemu-system-i386 virtio-mouse: Assertion in address_space_lduw_le_cached failed

[Qiuhao Li]

Public bug reported:

--[ Reproducer

cat << EOF | ./build/qemu-system-i386 -machine q35,accel=qtest -nodefaults \
-device virtio-mouse -display none -qtest stdio
outl 0xcf8 0x8820
outl 0xcfc 0xe0004000
outl 0xcf8 0x8804
outb 0xcfc 0x02
write 0xe000400c 0x4 0x003fe62e
write 0xe0004016 0x1 0x01
write 0xe0004024 0x1 0x01
write 0xe000401c 0x1 0x01
write 0xe0007007 0x1 0x00
write 0xe0004018 0x1 0x41
write 0xe0007007 0x1 0x00
EOF


--[ Output

[I 1611805425.711054] OPENED
[R +0.040080] outl 0xcf8 0x8820
OK
[S +0.040117] OK
[R +0.040136] outl 0xcfc 0xe0004000
OK
[S +0.040155] OK
[R +0.040165] outl 0xcf8 0x8804
OK
[S +0.040172] OK
[R +0.040184] outb 0xcfc 0x02
OK
[S +0.040683] OK
[R +0.040702] write 0xe000400c 0x4 0x003fe62e
OK
[S +0.040735] OK
[R +0.040743] write 0xe0004016 0x1 0x01
OK
[S +0.040748] OK
[R +0.040755] write 0xe0004024 0x1 0x01
OK
[S +0.040760] OK
[R +0.040767] write 0xe000401c 0x1 0x01
OK
[S +0.040785] OK
[R +0.040792] write 0xe0007007 0x1 0x00
OK
[S +0.040810] OK
[R +0.040817] write 0xe0004018 0x1 0x41
OK
[S +0.040822] OK
[R +0.040839] write 0xe0007007 0x1 0x00
qemu-system-i386: /home/ubuntu/qemu/include/exec/memory_ldst_cached.h.inc:54: 
uint32_t address_space_lduw_le_cached(MemoryRegionCache *, hwaddr, MemTxAttrs, 
MemTxResult *): Assertion `addr < cache->len && 2 <= cache->len - addr' failed.


-- [ Original ASAN report

qemu-fuzz-i386: /home/ubuntu/qemu/include/exec/memory_ldst_cached.h.inc:54: 
uint32_t address_space_lduw_le_cached(MemoryRegionCache *, hwaddr, MemTxAttrs, 
MemTxResult *): Assertion `addr < cache->len && 2 <= cache->len - addr' failed.
==3406167== ERROR: libFuzzer: deadly signal
#0 0x5644e4ae0f21 in __sanitizer_print_stack_trace 
(/home/ubuntu/qemu/build/qemu-fuzz-i386+0x2a47f21)
#1 0x5644e4a29fe8 in fuzzer::PrintStackTrace() 
(/home/ubuntu/qemu/build/qemu-fuzz-i386+0x2990fe8)
#2 0x5644e4a10023 in fuzzer::Fuzzer::CrashCallback() 
(/home/ubuntu/qemu/build/qemu-fuzz-i386+0x2977023)
#3 0x7f77e2a4b3bf  (/lib/x86_64-linux-gnu/libpthread.so.0+0x153bf)
#4 0x7f77e285c18a in raise (/lib/x86_64-linux-gnu/libc.so.6+0x4618a)
#5 0x7f77e283b858 in abort (/lib/x86_64-linux-gnu/libc.so.6+0x25858)
#6 0x7f77e283b728  (/lib/x86_64-linux-gnu/libc.so.6+0x25728)
#7 0x7f77e284cf35 in __assert_fail (/lib/x86_64-linux-gnu/libc.so.6+0x36f35)
#8 0x5644e60051b2 in address_space_lduw_le_cached 
/home/ubuntu/qemu/include/exec/memory_ldst_cached.h.inc:54:5
#9 0x5644e60051b2 in lduw_le_phys_cached 
/home/ubuntu/qemu/include/exec/memory_ldst_phys.h.inc:91:12
#10 0x5644e60051b2 in virtio_lduw_phys_cached 
/home/ubuntu/qemu/include/hw/virtio/virtio-access.h:166:12
#11 0x5644e5ff476d in vring_avail_ring 
/home/ubuntu/qemu/build/../hw/virtio/virtio.c:327:12
#12 0x5644e5ff476d in vring_get_used_event 
/home/ubuntu/qemu/build/../hw/virtio/virtio.c:333:12
#13 0x5644e5ff476d in virtio_split_should_notify 
/home/ubuntu/qemu/build/../hw/virtio/virtio.c:2473:35
#14 0x5644e5ff476d in virtio_should_notify 
/home/ubuntu/qemu/build/../hw/virtio/virtio.c:2524:16
#15 0x5644e5ff5556 in virtio_notify 
/home/ubuntu/qemu/build/../hw/virtio/virtio.c:2566:14
#16 0x5644e5571d2a in virtio_input_handle_sts 
/home/ubuntu/qemu/build/../hw/input/virtio-input.c:100:5
#17 0x5644e5ff20ec in virtio_queue_notify 
/home/ubuntu/qemu/build/../hw/virtio/virtio.c:2366:9
#18 0x5644e60908fb in memory_region_write_accessor 
/home/ubuntu/qemu/build/../softmmu/memory.c:491:5
#19 0x5644e6090363 in access_with_adjusted_size 
/home/ubuntu/qemu/build/../softmmu/memory.c:552:18
#20 0x5644e608fbc0 in memory_region_dispatch_write 
/home/ubuntu/qemu/build/../softmmu/memory.c
#21 0x5644e5b97bc6 in flatview_write_continue 
/home/ubuntu/qemu/build/../softmmu/physmem.c:2759:23
#22 0x5644e5b8d328 in flatview_write 
/home/ubuntu/qemu/build/../softmmu/physmem.c:2799:14
#23 0x5644e5b8d328 in address_space_write 
/home/ubuntu/qemu/build/../softmmu/physmem.c:2891:18
#24 0x5644e6018906 in qtest_process_command 
/home/ubuntu/qemu/build/../softmmu/qtest.c:539:13
#25 0x5644e60159df in qtest_process_inbuf 
/home/ubuntu/qemu/build/../softmmu/qtest.c:797:9
#26 0x5644e6015735 in qtest_server_inproc_recv 
/home/ubuntu/qemu/build/../softmmu/qtest.c:904:9
#27 0x5644e667cf68 in qtest_sendf 
/home/ubuntu/qemu/build/../tests/qtest/libqtest.c:438:5
#28 0x5644e667e54e in qtest_write 
/home/ubuntu/qemu/build/../tests/qtest/libqtest.c:1002:5
#29 0x5644e667e54e in qtest_writeq 
/home/ubuntu/qemu/build/../tests/qtest/libqtest.c:1023:5
#30 0x5644e4b1037e in __wrap_qtest_writeq 
/home/ubuntu/qemu/build/../tests/qtest/fuzz/qtest_wrappers.c:190:9
#31 0x5644e4b1c33d in op_write 
/home/ubuntu/qemu/build/../tests/qtest/fuzz/generic_fuzz.c:479:13
#32 0x5644e4b1a259 in generic_fuzz 
/home/ubuntu/qemu/build/../tests/qtest/fuzz/generic_fuzz.c:681:17
#33 0x5644e4b0b333 in LLVMFuzzerTestOneInput 
/home/ubuntu/qemu/build/../tests/qtest/fuzz/fuzz.c:151:5

[PATCH] fuzz: fix wrong index in clear_bits

[Qiuhao Li]

Signed-off-by: Qiuhao Li 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 4cba96dee2..20825768c2 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -261,7 +261,7 @@ def clear_bits(newtrace, outpath):
 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]
+data_try = data_try[:2] + "0" + data_try[2:]
 
 newtrace[i] = "{prefix} {data_try}\n".format(
 prefix=prefix,
-- 
2.25.1

Re: [RFC PATCH] rtl8139: fix stack overflow if RxBuf overlaps MMIO

[Qiuhao Li]

On Tue, 2021-01-12 at 16:02 +, Peter Maydell wrote:
> On Tue, 12 Jan 2021 at 15:23, Qiuhao Li 
> wrote:
> > Fix Bug 1910826 [1] / OSS-Fuzz Issue 29224 [2].
> > 
> > In rtl8139.c, the function rtl8139_RxBuf_write, which sets the
> > RxBuf
> > (Receive Buffer Start Address), doesn't check if this buffer
> > overlaps our
> > MMIO region. So if the guest machine set the transmit mode to
> > loopback, put
> > the RxBuf at the address of TSD (Transmit Status of Descriptor,
> > MMIO), and
> > trigger a frame transfer by directly writing to the TSD, an
> > infinite
> > recursion will occur:
> > 
> > rtl8139_ioport_write (to TSD) -> rtl8139_io_writel ->
> > rtl8139_transmit ->
> > rtl8139_transmit_one -> rtl8139_transfer_frame ->
> > rtl8139_do_receive ->
> > rtl8139_write_buffer -> pci_dma_write (to TSD) -> ... ->
> > rtl8139_ioport_write (to TSD)
> > 
> > This patch adds a check to ensure the maximum possible RxBuf [3]
> > won't
> > overlap the MMIO region.
> > 
> > P.S. There is a more concise reproducer with comments [4], which
> > may help :)
> > 
> > [1] https://bugs.launchpad.net/bugs/1910826
> > [2] https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29224
> > [3] https://www.cs.usfca.edu/~cruse/cs326f04/RTL8139D_DataSheet.pdf
> > 5.7 Transmit Configuration Register
> > [4] https://bugs.launchpad.net/qemu/+bug/1910826/comments/1
> > 
> > Signed-off-by: Qiuhao Li 
> > Reported-by: Alexander Bulekov 
> 
> This looks like a single-device workaround for the generic
> class of problems where a device can be configured to
> do DMA to itself. Why is rtl8139 special ?

Understand. I thought it is the device's duty to avoid doing DMA to
itself.

Thank you.
  Qiuhao Li
> 
> (I have on my todo list to think about the general problem.)
> 
> thanks
> -- PMM

[RFC PATCH] rtl8139: fix stack overflow if RxBuf overlaps MMIO

[Qiuhao Li]

Fix Bug 1910826 [1] / OSS-Fuzz Issue 29224 [2].

In rtl8139.c, the function rtl8139_RxBuf_write, which sets the RxBuf
(Receive Buffer Start Address), doesn't check if this buffer overlaps our
MMIO region. So if the guest machine set the transmit mode to loopback, put
the RxBuf at the address of TSD (Transmit Status of Descriptor, MMIO), and
trigger a frame transfer by directly writing to the TSD, an infinite
recursion will occur:

rtl8139_ioport_write (to TSD) -> rtl8139_io_writel -> rtl8139_transmit ->
rtl8139_transmit_one -> rtl8139_transfer_frame -> rtl8139_do_receive ->
rtl8139_write_buffer -> pci_dma_write (to TSD) -> ... ->
rtl8139_ioport_write (to TSD)

This patch adds a check to ensure the maximum possible RxBuf [3] won't
overlap the MMIO region.

P.S. There is a more concise reproducer with comments [4], which may help :)

[1] https://bugs.launchpad.net/bugs/1910826
[2] https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29224
[3] https://www.cs.usfca.edu/~cruse/cs326f04/RTL8139D_DataSheet.pdf
5.7 Transmit Configuration Register
[4] https://bugs.launchpad.net/qemu/+bug/1910826/comments/1

Signed-off-by: Qiuhao Li 
Reported-by: Alexander Bulekov 
---
 hw/net/rtl8139.c | 12 
 1 file changed, 12 insertions(+)

diff --git a/hw/net/rtl8139.c b/hw/net/rtl8139.c
index ba5ace1ab7..aa7a38220d 100644
--- a/hw/net/rtl8139.c
+++ b/hw/net/rtl8139.c
@@ -2567,6 +2567,18 @@ static void rtl8139_RxBuf_write(RTL8139State *s, 
uint32_t val)
 {
 DPRINTF("RxBuf write val=0x%08x\n", val);
 
+PCIDevice *d = PCI_DEVICE(s);
+uint64_t mmio_addr = d->io_regions[1].addr;
+uint64_t mmio_size = d->io_regions[1].size;
+
+#define MAX_Rx_BUFFER_LENGTH (64 * 1024 + 16) /* RxConfig 12-11 = 0b11 */
+
+if (val < mmio_addr + mmio_size && val + MAX_Rx_BUFFER_LENGTH > mmio_addr) 
{
+DPRINTF("The receive buffer may overlap with the MMIO region.\n");
+DPRINTF("mmio_addr: 0x%lx, mmio_size: 0x%lx\n", mmio_addr, mmio_size);
+return;
+}
+
 s->RxBuf = val;
 
 /* may need to reset rxring here */
-- 
2.25.1

[Bug 1910826] Re: [OSS-Fuzz] Issue 29224 rtl8139: Stack-overflow in rtlNUMBER_transmit_one

[Qiuhao Li]

A more concise version and corresponding notes. Might help :)

-- [ Reproducer

cat << EOF | ../build/qemu-system-i386 -machine q35 \
-nodefaults  -device rtl8139,netdev=net0 \
-netdev user,id=net0 -display none -qtest stdio
outl 0xcf8 0x8804
outb 0xcfc 0x06
outl 0xcf8 0x8817
outb 0xcfc 0xff
write 0xff37 0x1 0x0c
writel 0xff30 0xff10
write 0xff40 0x4 0x16
write 0xff44 0x4 0x01
write 0xff10 0x4 0x01
EOF

-- [ Notes

/* Make the MMIO region start from 0xff00 */
outl 0xcf8 0x8817
outb 0xcfc 0xff

/*Command Register: enable receiver and transmitter*/
write 0xff37 0x1 0x0c

/* set Receive (Rx) Buffer Start Address at 0xff10 */
/* Note: 0xff10 - 0xff00 = 0x10 is the offset of TSD0*/
writel 0xff30 0xff10

/* TXRR, Tx Retry Count = 1 */
/* set transmit mode into the loopback */
write 0xff40 0x4 0x16

/* Receive Configuration Register: Accept All Packets */
write 0xff44 0x4 0x01

/* TSD0: set Descriptor Size to 1 and trigger a tranfer*/
write 0xff10 0x4 0x01

-- 
You received this bug notification because you are a member of qemu-
devel-ml, which is subscribed to QEMU.
https://bugs.launchpad.net/bugs/1910826

Title:
  [OSS-Fuzz] Issue 29224 rtl8139: Stack-overflow in
  rtlNUMBER_transmit_one

Status in QEMU:
  New

Bug description:
  === Reproducer ===
  cat << EOF | ../build/qemu-system-i386 -machine q35 \
  -nodefaults  -device rtl8139,netdev=net0 \
  -netdev user,id=net0 -display none -qtest stdio
  outl 0xcf8 0x8804
  outb 0xcfc 0x26
  outl 0xcf8 0x8817
  outb 0xcfc 0xff
  write 0x1 0x1 0x42
  write 0x5 0x1 0x42
  write 0x9 0x1 0x42
  write 0xd 0x1 0x42
  write 0xff44 0x4 0x11
  write 0xff37 0x1 0x1c
  writel 0xff30 0xff00
  write 0xff40 0x4 0x16
  write 0xff10 0x4 0x01020
  EOF

  === Stack Trace ===
  ==2819215==ERROR: AddressSanitizer: stack-overflow on address 0x7ffd2c714040 
(pc 0x5639b3a933d9 bp 0x7ffd2c716210 sp 0x7ffd2c714040 T0)
  #0 rtl8139_transmit_one /src/qemu/hw/net/rtl8139.c:1815
  #1 rtl8139_transmit /src/qemu/hw/net/rtl8139.c:2388:9
  #2 rtl8139_TxStatus_write /src/qemu/hw/net/rtl8139.c:2442:5
  #3 rtl8139_io_writel /src/qemu/hw/net/rtl8139.c:2865:13
  #4 rtl8139_ioport_write /src/qemu/hw/net/rtl8139.c:3290:9
  #5 memory_region_write_accessor /src/qemu/softmmu/memory.c:491:5
  #6 access_with_adjusted_size /src/qemu/softmmu/memory.c:552:18
  #7 memory_region_dispatch_write /src/qemu/softmmu/memory.c:0:13
  #8 flatview_write_continue /src/qemu/softmmu/physmem.c:2759:23
  #9 flatview_write /src/qemu/softmmu/physmem.c:2799:14
  #10 address_space_write /src/qemu/softmmu/physmem.c:2891:18
  #11 address_space_rw /src/qemu/softmmu/physmem.c:2901:16
  #12 dma_memory_rw_relaxed /src/qemu/include/sysemu/dma.h:88:12
  #13 dma_memory_rw /src/qemu/include/sysemu/dma.h:127:12
  #14 pci_dma_rw /src/qemu/include/hw/pci/pci.h:801:12
  #15 pci_dma_write /src/qemu/include/hw/pci/pci.h:837:12
  #16 rtl8139_write_buffer /src/qemu/hw/net/rtl8139.c:778:5
  #17 rtl8139_do_receive /src/qemu/hw/net/rtl8139.c:1172:9
  #18 rtl8139_transfer_frame /src/qemu/hw/net/rtl8139.c:1798:9
  #19 rtl8139_transmit_one /src/qemu/hw/net/rtl8139.c:1845:5
  #20 rtl8139_transmit /src/qemu/hw/net/rtl8139.c:2388:9
  #21 rtl8139_TxStatus_write /src/qemu/hw/net/rtl8139.c:2442:5
  #22 rtl8139_io_writel /src/qemu/hw/net/rtl8139.c:2865:13
  #23 rtl8139_ioport_write /src/qemu/hw/net/rtl8139.c:3290:9
  #24 memory_region_write_accessor /src/qemu/softmmu/memory.c:491:5
  #25 access_with_adjusted_size /src/qemu/softmmu/memory.c:552:18
  #26 memory_region_dispatch_write /src/qemu/softmmu/memory.c:0:13
  #27 flatview_write_continue /src/qemu/softmmu/physmem.c:2759:23
  #28 flatview_write /src/qemu/softmmu/physmem.c:2799:14
  #29 address_space_write /src/qemu/softmmu/physmem.c:2891:18
  #30 address_space_rw /src/qemu/softmmu/physmem.c:2901:16
  #31 dma_memory_rw_relaxed /src/qemu/include/sysemu/dma.h:88:12
  #32 dma_memory_rw /src/qemu/include/sysemu/dma.h:127:12
  #33 pci_dma_rw /src/qemu/include/hw/pci/pci.h:801:12
  #34 pci_dma_write /src/qemu/include/hw/pci/pci.h:837:12
  #35 rtl8139_write_buffer /src/qemu/hw/net/rtl8139.c:778:5
  #36 rtl8139_do_receive /src/qemu/hw/net/rtl8139.c:1172:9
  #37 rtl8139_transfer_frame /src/qemu/hw/net/rtl8139.c:1798:9
  Repeat until we run out of stack

  https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29224

To manage notifications about this bug go to:
https://bugs.launchpad.net/qemu/+bug/1910826/+subscriptions

Re: [PATCH v8 5/7] fuzz: set bits in operand of write/out to zero

[Qiuhao Li]

On Mon, 2021-01-11 at 11:26 +0100, Thomas Huth wrote:
> On 11/01/2021 10.39, Qiuhao Li wrote:
> > On Mon, 2021-01-11 at 10:01 +0100, Philippe Mathieu-Daudé wrote:
> > > On 1/11/21 7:11 AM, 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.
> > > 
> > > Please use the full link as reference:
> > > https://bugs.launchpad.net/qemu/+bug/1908062
> > 
> > Ok, should I submit a new version patch? Or just change the commit
> > messages and submit this series again?
> 
> I can fix this when picking up the patches, no need to respin just
> because 
> of this.
> 
>   Thomas
> 

Thank you.

> 

Re: [PATCH v8 5/7] fuzz: set bits in operand of write/out to zero

[Qiuhao Li]

On Mon, 2021-01-11 at 10:01 +0100, Philippe Mathieu-Daudé wrote:
> On 1/11/21 7:11 AM, 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.
> 
> Please use the full link as reference:
> https://bugs.launchpad.net/qemu/+bug/1908062

Ok, should I submit a new version patch? Or just change the commit
messages and submit this series again?

Thank you.

> 
> (since this series is fully reviewed, can the
> maintainer applying the series do the change
> in place?)
> 
> Thanks,
> 
> Phil.
> 
> > Signed-off-by: Qiuhao Li 
> > Reviewed-by: Alexander Bulekov 
> > Tested-by: Alexander Bulekov 
> > ---
> >  scripts/oss-fuzz/minimize_qtest_trace.py | 39
> > 
> >  1 file changed, 39 insertions(+)
> 
> 

[PATCH v8 7/7] fuzz: heuristic split write based on past IOs

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 0e59bdbb01..4cba96dee2 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -88,6 +88,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
@@ -151,6 +188,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

[PATCH v8 6/7] fuzz: add minimization options

[Qiuhao Li]

-M1: remove IO commands iteratively
-M2: try setting bits in operand of write/out to zero

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 219858a9e3..0e59bdbb01 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\
@@ -216,24 +230,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:
@@ -242,4 +264,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

[PATCH v8 5/7] fuzz: set bits in operand of write/out 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.

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 59e91de7e2..219858a9e3 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -167,6 +167,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:
@@ -187,7 +223,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

[PATCH v8 4/7] fuzz: remove IO commands iteratively

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 af9767f7e4..59e91de7e2 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -74,21 +74,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.
@@ -177,7 +165,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

[PATCH v8 3/7] fuzz: split write operand using binary approach

[Qiuhao Li]

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 uuuu

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 uu

For uu, 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:

   uu len=6
+
|
+
 xxx,xuu 6/2=3 fail
+
 +--+-+
 ||
 ++
  xx,xxuu 6/2^2=1 fail u,u 6-1=5 success
 +   +
 +--++   |
 |  |+-+ u removed
 +  +
   xx,xxu 5/2=2 fail  ,u 6-2=4 success
   +
   |
   +---+ u removed

In some rare cases, this algorithm will fail to trim all unnecessary bytes:

  xuxx
  -xuxx Fail
  -xuxx Fail
  xuxx- Fail
  ...

I think the trade-off is worth it.

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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., xuxx (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

[PATCH v8 2/7] fuzz: double the IOs to remove for every loop

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 a28913a2a7..cacabf2638 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -88,19 +88,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)
@@ -121,7 +130,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
@@ -154,7 +163,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

[PATCH v8 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

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

Note:

Sometimes the mutated or the same trace may trigger a different crash
summary (second-to-last line) but indicates the same bug. For example, Bug
1910826 [1], which will trigger a stack overflow, may output summaries
like:

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

or

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

Etc.

If we use the whole summary line as the token, we may be prevented from
further minimization. So in this patch, we only use the first three words
which indicate the type of crash:

SUMMARY: AddressSanitizer: stack-overflow

[1] https://bugs.launchpad.net/qemu/+bug/1910826

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 42 +---
 1 file changed, 30 insertions(+), 12 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5e405a0d5f..a28913a2a7 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
+type crash 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,31 @@ 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 = " ".join(outs.splitlines()[-2].split()[0:3])
+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, ""):
+if "CLOSED" in line:
+return False
+if CRASH_TOKEN in line:
+return True
+
+print("\nWarning:")
+print("  There is no 'CLOSED'or CRASH_TOKEN in the stdout of subprocess.")
+print("  Usually this indicates a different type of crash.\n")
+return False
 
 
 def minimize_trace(inpath, outpath):
@@ -66,7 +85,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

[PATCH v8 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

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

v8:
  Fix: [PATCH v7 1/7] misused the bytes type
  Add: [PATCH v7 1/7] warn when the CRASH_TOKEN cannot be found

v7:
  Fix: [PATCH v6 1/7] get stuck in crash detection

v6:
  Fix: add Reviewed-by and Tested-by tags

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 | 260 +++
 1 file changed, 213 insertions(+), 47 deletions(-)

-- 
2.25.1

Re: [PATCH v4 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

On Sun, 2021-01-10 at 11:00 -0500, Alexander Bulekov wrote:
> On 210110 2110, Qiuhao Li wrote:
> > On Wed, 2021-01-06 at 23:18 -0500, Alexander Bulekov wrote:
> > > On 201229 1240, Qiuhao Li wrote:
> > > > 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 
> > > > ---
> > > >  scripts/oss-fuzz/minimize_qtest_trace.py | 41
> > > > --
> > > > --
> > > >  1 file changed, 28 insertions(+), 13 deletions(-)
> > > > 
> > > > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > index 5e405a0d5f..aa69c7963e 100755
> > > > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > > > @@ -29,30 +29,46 @@ 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))
> > > >  
> > > > -rc = subprocess.Popen("timeout -s 9 {timeout}s {qemu_path}
> > > > {qemu_args} 2>&1\
> > > > +proc = subprocess.Popen("timeout {timeout}s {qemu_path}
> > > > {qemu_args} 2>&1\
> > > 
> > > Why remove the -s 9 here? I ran into a case where the minimizer
> > > got
> > > stuck on one iteration. Adding back "sigkill" to the timeout can
> > > be a
> > > safety net to catch those bad cases.
> > > -Alex
> > 
> > Hi Alex,
> > 
> > After reviewed this patch again, I think this get-stuck bug may be
> > caused by code:
> > 
> > -return CRASH_TOKEN in output
> 
> Hi,
> Thanks for fixing this. Strangely, I was able to fix it by swapping
> the b'' for a ' ' when I was stuck on a testcase a few days ago.
> vvv 
> > +for line in iter(rc.stdout.readline, b''):
> > +if "CLOSED" in line:
> > +return False
> > +if CRASH_TOKEN in line:
> > +return True
> > 
> 
> I think your proposed change essentially does the same?
> -Alex

Hi Alex,

It looks like I misused the bytes type. Instead of b'', '' (the str
type) should be used here:

-for line in iter(rc.stdout.readline, b''):
+for line in iter(rc.stdout.readline, ''):
And you are right, if we use iter() with sentinel parameter '', it's
does the same as:

+if line == "":
+return False

But if we just fix the get-stuck bug here, we may fail
the assert(check_if_trace_crashes(newtrace, outpath)) check after
remove_lines() or clear_bits() since the same trace input may trigger a
different output between runs.

My solution is instead of using the whole second-to-last line as token,
we only use the the first three words

[PATCH v7 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

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

v7:
  Fix: [PATCH v6 1/7] get stuck in crash detection

v6:
  Fix: add Reviewed-by and Tested-by tags

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 | 261 +++
 1 file changed, 214 insertions(+), 47 deletions(-)

-- 
2.25.1

[PATCH v7 7/7] fuzz: heuristic split write based on past IOs

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 d2e3f67b66..831e1f107f 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -89,6 +89,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
@@ -152,6 +189,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

[PATCH v7 3/7] fuzz: split write operand using binary approach

[Qiuhao Li]

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 uuuu

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 uu

For uu, 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:

   uu len=6
+
|
+
 xxx,xuu 6/2=3 fail
+
 +--+-+
 ||
 ++
  xx,xxuu 6/2^2=1 fail u,u 6-1=5 success
 +   +
 +--++   |
 |  |+-+ u removed
 +  +
   xx,xxu 5/2=2 fail  ,u 6-2=4 success
   +
   |
   +---+ u removed

In some rare cases, this algorithm will fail to trim all unnecessary bytes:

  xuxx
  -xuxx Fail
  -xuxx Fail
  xuxx- Fail
  ...

I think the trade-off is worth it.

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 3c11db4b8a..319f4c02d0 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -98,7 +98,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
@@ -111,9 +111,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]
@@ -134,11 +136,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., xuxx (u is the unnecessary byte)
+
 if newtrace[i].startswith("write "):
 addr = int(newtrace[i].split()[1], 16)
 length = int(newtrace[i].split()[2], 16)
@@ -147,6 +153,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

[PATCH v7 6/7] fuzz: add minimization options

[Qiuhao Li]

-M1: remove IO commands iteratively
-M2: try setting bits in operand of write/out to zero

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 f86bbcf6b3..d2e3f67b66 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\
@@ -217,24 +231,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:
@@ -243,4 +265,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

[PATCH v7 4/7] fuzz: remove IO commands iteratively

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 319f4c02d0..287266fe39 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -75,21 +75,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.
@@ -178,7 +166,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

[PATCH v7 5/7] fuzz: set bits in operand of write/out 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.

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 287266fe39..f86bbcf6b3 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -168,6 +168,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:
@@ -188,7 +224,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

[PATCH v7 2/7] fuzz: double the IOs to remove for every loop

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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 97f1201747..3c11db4b8a 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -89,19 +89,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)
@@ -122,7 +131,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
@@ -155,7 +164,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

[PATCH v7 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

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

Note:

Sometimes the mutated or the same trace may trigger a different crash
summary (second-to-last line) but indicates the same bug. For example, Bug
1910826 [1], which will trigger a stack overflow, may output summaries
like:

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

or

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

Etc.

If we use the whole summary line as the token, we may be prevented from
further minimization. So in this patch, we only use the first three words
which indicate the type of crash:

SUMMARY: AddressSanitizer: stack-overflow

[1] https://bugs.launchpad.net/qemu/+bug/1910826

Signed-off-by: Qiuhao Li 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 43 +---
 1 file changed, 31 insertions(+), 12 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5e405a0d5f..97f1201747 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
+type crash 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,32 @@ 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 = " ".join(outs.splitlines()[-2].split()[0:3])
+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
+# We reach the end of stdout and there is no "CLOSED" or CRASH_TOKEN
+# Usually this is caused by a different type of crash
+if line == "":
+return False
+
+return False
 
 
 def minimize_trace(inpath, outpath):
@@ -66,7 +86,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

Re: [PATCH v4 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

On Wed, 2021-01-06 at 23:18 -0500, Alexander Bulekov wrote:
> On 201229 1240, Qiuhao Li wrote:
> > 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 
> > ---
> >  scripts/oss-fuzz/minimize_qtest_trace.py | 41 --
> > --
> >  1 file changed, 28 insertions(+), 13 deletions(-)
> > 
> > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > index 5e405a0d5f..aa69c7963e 100755
> > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > @@ -29,30 +29,46 @@ 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))
> >  
> > -rc = subprocess.Popen("timeout -s 9 {timeout}s {qemu_path}
> > {qemu_args} 2>&1\
> > +proc = subprocess.Popen("timeout {timeout}s {qemu_path}
> > {qemu_args} 2>&1\
> 
> Why remove the -s 9 here? I ran into a case where the minimizer got
> stuck on one iteration. Adding back "sigkill" to the timeout can be a
> safety net to catch those bad cases.
> -Alex

Hi Alex,

After reviewed this patch again, I think this get-stuck bug may be
caused by code:

-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

I assumed there are only two end cases in lines of stdout, but while we
are trimming the trace input, the crash output (second-to-last line)
may changes, in which case we will go through the output and fail to
find "CLOSED" and CRASH_TOKEN, thus get stuck in the loop above.

To fix this bug and get a more trimmed input trace, we can:

Use the first three words of the second-to-last line instead of the
whole string, which indicate the type of crash as the token.

-CRASH_TOKEN = output.splitlines()[-2]
+CRASH_TOKEN = " ".join(outs.splitlines()[-2].split()[0:3])

If we reach the end of a subprocess' output, return False.

+if line == "":
+return False

I fix it in [PATCH v7 1/7] and give an example. Could you review again?
Thanks :-)

FYI, I mentioned this situation firstly in [PATCH 1/4], where I gave a
more detailed example:

https://lists.gnu.org/archive/html/qemu-devel/2020-12/msg05888.html

> 
> >  < {trace_path}".format(timeout=TIMEOUT,
> > qemu_path=QEMU_PATH,
> > qemu_args=QEMU_ARGS,
> > 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, _ = proc.communicate(timeout=5)

[PATCH v6 7/7] fuzz: heuristic split write based on past IOs

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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

[PATCH v6 6/7] fuzz: add minimization options

[Qiuhao Li]

-M1: remove IO commands iteratively
-M2: try setting bits in operand of write/out to zero

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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

[PATCH v6 5/7] fuzz: set bits in operand of write/out 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.

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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

[PATCH v6 4/7] fuzz: remove IO commands iteratively

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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

[PATCH v6 3/7] fuzz: split write operand using binary approach

[Qiuhao Li]

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 uuuu

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 uu

For uu, 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:

   uu len=6
+
|
+
 xxx,xuu 6/2=3 fail
+
 +--+-+
 ||
 ++
  xx,xxuu 6/2^2=1 fail u,u 6-1=5 success
 +   +
 +--++   |
 |  |+-+ u removed
 +  +
   xx,xxu 5/2=2 fail  ,u 6-2=4 success
   +
   |
   +---+ u removed

In some rare cases, this algorithm will fail to trim all unnecessary bytes:

  xuxx
  -xuxx Fail
  -xuxx Fail
  xuxx- Fail
  ...

I think the trade-off is worth it.

Signed-off-by: Qiuhao Li 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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., xuxx (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

[PATCH v6 2/7] fuzz: double the IOs to remove for every loop

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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

[PATCH v6 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

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 
Reviewed-by: Alexander Bulekov 
Tested-by: Alexander Bulekov 
---
 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

[PATCH v6 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

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

v6:
  Fix: add Reviewed-by and Tested-by tags

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

Re: [PATCH v5 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

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

[PATCH v5 7/7] fuzz: heuristic split write based on past IOs

[Qiuhao Li]

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

[PATCH v5 6/7] fuzz: add minimization options

[Qiuhao Li]

-M1: remove IO commands iteratively
-M2: try setting bits in operand of write/out to zero

Signed-off-by: Qiuhao Li 
---
 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

[PATCH v5 5/7] fuzz: set bits in operand of write/out 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.

Signed-off-by: Qiuhao Li 
---
 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

[PATCH v5 4/7] fuzz: remove IO commands iteratively

[Qiuhao Li]

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

[PATCH v5 3/7] fuzz: split write operand using binary approach

[Qiuhao Li]

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 uuuu

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 uu

For uu, 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:

   uu len=6
+
|
+
 xxx,xuu 6/2=3 fail
+
 +--+-+
 ||
 ++
  xx,xxuu 6/2^2=1 fail u,u 6-1=5 success
 +   +
 +--++   |
 |  |+-+ u removed
 +  +
   xx,xxu 5/2=2 fail  ,u 6-2=4 success
   +
   |
   +---+ u removed

In some rare cases, this algorithm will fail to trim all unnecessary bytes:

  xuxx
  -xuxx Fail
  -xuxx Fail
  xuxx- Fail
  ...

I think the trade-off is worth it.

Signed-off-by: Qiuhao Li 
---
 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., xuxx (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 

[PATCH v5 2/7] fuzz: double the IOs to remove for every loop

[Qiuhao Li]

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

[PATCH v5 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

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

[PATCH v5 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

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

Re: [PATCH v4 4/7] fuzz: loop the remove minimizer and refactoring

[Qiuhao Li]

On Wed, 2021-01-06 at 23:53 -0500, Alexander Bulekov wrote:
> On 201229 1240, Qiuhao Li wrote:
> > Now we use a one-time scan and remove strategy in the remval
> > 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 
> 
> Small note below, but otherwise:
> Reviewed-by: Alexander Bulekov 
> 
> > ---
> >  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 1a26bf5b93..378a7ccec6 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_minimizer(newtrace, outpath):
> 
> Maybe a different name for this function?
> e.g. minimize_each_line or minimize_iter
> 
> -Alex

Ok, changed to remove_lines in version 5, thanks.

> 
> >  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 minimizer
> > +old_len = len(newtrace) + 1
> > +while(old_len > len(newtrace)):
> > +old_len = len(newtrace)
> > +remove_minimizer(newtrace, outpath)
> > +newtrace = list(filter(lambda s: s != "", newtrace))
> > +
> > +assert(check_if_trace_crashes(newtrace, outpath))
> >  
> >  
> >  if __name__ == '__main__':
> > -- 
> > 2.25.1
> > 

Re: [PATCH v4 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

On Wed, 2021-01-06 at 23:18 -0500, Alexander Bulekov wrote:
> On 201229 1240, Qiuhao Li wrote:
> > 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 
> > ---
> >  scripts/oss-fuzz/minimize_qtest_trace.py | 41 --
> > --
> >  1 file changed, 28 insertions(+), 13 deletions(-)
> > 
> > diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py
> > b/scripts/oss-fuzz/minimize_qtest_trace.py
> > index 5e405a0d5f..aa69c7963e 100755
> > --- a/scripts/oss-fuzz/minimize_qtest_trace.py
> > +++ b/scripts/oss-fuzz/minimize_qtest_trace.py
> > @@ -29,30 +29,46 @@ 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))
> >  
> > -rc = subprocess.Popen("timeout -s 9 {timeout}s {qemu_path}
> > {qemu_args} 2>&1\
> > +proc = subprocess.Popen("timeout {timeout}s {qemu_path}
> > {qemu_args} 2>&1\
> 
> Why remove the -s 9 here? I ran into a case where the minimizer got
> stuck on one iteration. Adding back "sigkill" to the timeout can be a
> safety net to catch those bad cases.
> -Alex

Oops, I thought SIGKILL is the default signal timeout will send.
Fixed in version 5, thanks.

> 
> >  < {trace_path}".format(timeout=TIMEOUT,
> > qemu_path=QEMU_PATH,
> > qemu_args=QEMU_ARGS,
> > 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, _ = proc.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(proc.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
> > 

Ping: [PATCH v4 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

Kindly ping :)

Wondering if there is anything wrong with this patch?

On Tue, 2020-12-29 at 12:39 +0800, 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
> 
> 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: loop the remove minimizer and refactoring
>   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, 209 insertions(+), 48 deletions(-)
> 

[PATCH v4 6/7] fuzz: add minimization options

[Qiuhao Li]

-M1: loop around the remove minimizer
-M2: try setting bits in operand of write/out to zero
Signed-off-by: Qiuhao Li 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 32 +++-
 1 file changed, 26 insertions(+), 6 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 70ac0c5366..a681984076 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 # loop around the remove minimizer
+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,30 @@ def minimize_trace(inpath, outpath):
 print("Setting the timeout for {} seconds".format(TIMEOUT))
 
 newtrace = trace[:]
-
+global M1, M2
 # remove minimizer
 old_len = len(newtrace) + 1
 while(old_len > len(newtrace)):
 old_len = len(newtrace)
+print("trace lenth = ", old_len)
 remove_minimizer(newtrace, outpath)
+if not M1 and not M2:
+break
 newtrace = list(filter(lambda s: s != "", newtrace))
 assert(check_if_trace_crashes(newtrace, outpath))
 
-# set zero minimizer
-set_zero_minimizer(newtrace, outpath)
+if M2:
+set_zero_minimizer(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 +259,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

[PATCH v4 5/7] fuzz: set bits in operand of write/out 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.

Signed-off-by: Qiuhao Li 
---
 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 378a7ccec6..70ac0c5366 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -164,6 +164,42 @@ def remove_minimizer(newtrace, outpath):
 i += 1
 
 
+def set_zero_minimizer(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_minimizer(newtrace, outpath)
 newtrace = list(filter(lambda s: s != "", newtrace))
+assert(check_if_trace_crashes(newtrace, outpath))
 
+# set zero minimizer
+set_zero_minimizer(newtrace, outpath)
 assert(check_if_trace_crashes(newtrace, outpath))
 
 
-- 
2.25.1

[PATCH v4 3/7] fuzz: split write operand using binary approach

[Qiuhao Li]

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 uuuu

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 uu

For uu, 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:

   uu len=6
+
|
+
 xxx,xuu 6/2=3 fail
+
 +--+-+
 ||
 ++
  xx,xxuu 6/2^2=1 fail u,u 6-1=5 success
 +   +
 +--++   |
 |  |+-+ u removed
 +  +
   xx,xxu 5/2=2 fail  ,u 6-2=4 success
   +
   |
   +---+ u removed

In some rare case, this algorithm will fail to trim all unnecessary bytes:

  xuxx
  -xuxx Fail
  -xuxx Fail
  xuxx- Fail
  ...

I think the trade-off is worth it.

Signed-off-by: Qiuhao Li 
---
 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 0b665ae657..1a26bf5b93 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., xuxx (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 

[PATCH v4 4/7] fuzz: loop the remove minimizer and refactoring

[Qiuhao Li]

Now we use a one-time scan and remove strategy in the remval 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 
---
 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 1a26bf5b93..378a7ccec6 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_minimizer(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 minimizer
+old_len = len(newtrace) + 1
+while(old_len > len(newtrace)):
+old_len = len(newtrace)
+remove_minimizer(newtrace, outpath)
+newtrace = list(filter(lambda s: s != "", newtrace))
+
+assert(check_if_trace_crashes(newtrace, outpath))
 
 
 if __name__ == '__main__':
-- 
2.25.1

[PATCH v4 7/7] fuzz: heuristic split write based on past IOs

[Qiuhao Li]

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 
---
 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 a681984076..6cbf2b0419 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_minimizer(newtrace, outpath):
 remove_step = 1
 i = 0
@@ -148,6 +185,25 @@ def remove_minimizer(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

[PATCH v4 2/7] fuzz: double the IOs to remove for every loop

[Qiuhao Li]

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 
---
 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 aa69c7963e..0b665ae657 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

[PATCH v4 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

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 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 41 
 1 file changed, 28 insertions(+), 13 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5e405a0d5f..aa69c7963e 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -29,30 +29,46 @@ 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))
 
-rc = subprocess.Popen("timeout -s 9 {timeout}s {qemu_path} {qemu_args} 
2>&1\
+proc = subprocess.Popen("timeout {timeout}s {qemu_path} {qemu_args} 2>&1\
 < {trace_path}".format(timeout=TIMEOUT,
qemu_path=QEMU_PATH,
qemu_args=QEMU_ARGS,
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, _ = proc.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(proc.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

[PATCH v4 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

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

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: loop the remove minimizer and refactoring
  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, 209 insertions(+), 48 deletions(-)

-- 
2.25.1

[PATCH v3 6/7] fuzz: set bits in operand of write/out 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.

Signed-off-by: Qiuhao Li 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 4 
 1 file changed, 4 insertions(+)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 4273ee7505..050b9f2195 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -243,6 +243,10 @@ def minimize_trace(inpath, outpath):
 set_zero_minimizer(newtrace, outpath)
 assert(check_if_trace_crashes(newtrace, outpath))
 
+# set zero minimizer
+set_zero_minimizer(newtrace, outpath)
+assert(check_if_trace_crashes(newtrace, outpath))
+
 
 if __name__ == '__main__':
 if len(sys.argv) < 3:
-- 
2.25.1

[PATCH v3 7/7] fuzz: heuristic split write based on past IOs

[Qiuhao Li]

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 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 55 
 1 file changed, 55 insertions(+)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 050b9f2195..5a8e90a604 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -83,6 +83,42 @@ 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_minimizer(newtrace, outpath):
 remove_step = 1
@@ -147,6 +183,25 @@ def remove_minimizer(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

[PATCH v3 4/7] fuzz: loop the remove minimizer and refactoring

[Qiuhao Li]

Now we use a one-time scan and remove strategy in the remval 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 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 80 +++-
 1 file changed, 65 insertions(+), 15 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 1a26bf5b93..70ac0c5366 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_minimizer(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,69 @@ def minimize_trace(inpath, outpath):
 newtrace[i] = prior[0]
 del newtrace[i+1]
 i += 1
-check_if_trace_crashes(newtrace, outpath)
+
+
+def set_zero_minimizer(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:
+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 minimizer
+old_len = len(newtrace) + 1
+while(old_len > len(newtrace)):
+old_len = len(newtrace)
+remove_minimizer(newtrace, outpath)
+newtrace = list(filter(lambda s: s != "", newtrace))
+assert(check_if_trace_crashes(newtrace, outpath))
+
+# set zero minimizer
+set_zero_minimizer(newtrace, outpath)
+assert(check_if_trace_crashes(newtrace, outpath))
 
 
 if __name__ == '__main__':
-- 
2.25.1

[PATCH v3 3/7] fuzz: split write operand using binary approach

[Qiuhao Li]

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 uuuu

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 uu

For uu, 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:

   uu len=6
+
|
+
 xxx,xuu 6/2=3 fail
+
 +--+-+
 ||
 ++
  xx,xxuu 6/2^2=1 fail u,u 6-1=5 success
 +   +
 +--++   |
 |  |+-+ u removed
 +  +
   xx,xxu 5/2=2 fail  ,u 6-2=4 success
   +
   |
   +---+ u removed

In some rare case, this algorithm will fail to trim all unnecessary bytes:

  xuxx
  -xuxx Fail
  -xuxx Fail
  xuxx- Fail
  ...

I think the trade-off is worth it.

Signed-off-by: Qiuhao Li 
---
 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 0b665ae657..1a26bf5b93 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., xuxx (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 

[PATCH v3 5/7] fuzz: add minimization options

[Qiuhao Li]

-M1: loop around the remove minimizer
-M2: try setting bits in operand of write/out to zero

Signed-off-by: Qiuhao Li 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 30 
 1 file changed, 25 insertions(+), 5 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 70ac0c5366..4273ee7505 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 # loop around the remove minimizer
+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,19 @@ 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 +226,31 @@ def minimize_trace(inpath, outpath):
 print("Setting the timeout for {} seconds".format(TIMEOUT))
 
 newtrace = trace[:]
-
+global M1, M2
 # remove minimizer
 old_len = len(newtrace) + 1
 while(old_len > len(newtrace)):
 old_len = len(newtrace)
+print("trace lenth = ", old_len)
 remove_minimizer(newtrace, outpath)
+if not M1 and not M2:
+break
 newtrace = list(filter(lambda s: s != "", newtrace))
 assert(check_if_trace_crashes(newtrace, outpath))
 
 # set zero minimizer
-set_zero_minimizer(newtrace, outpath)
+if M2:
+set_zero_minimizer(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 +259,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

[PATCH v3 2/7] fuzz: double the IOs to remove for every loop

[Qiuhao Li]

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 
---
 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 aa69c7963e..0b665ae657 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

[PATCH v3 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

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 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 41 
 1 file changed, 28 insertions(+), 13 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5e405a0d5f..aa69c7963e 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -29,30 +29,46 @@ 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))
 
-rc = subprocess.Popen("timeout -s 9 {timeout}s {qemu_path} {qemu_args} 
2>&1\
+proc = subprocess.Popen("timeout {timeout}s {qemu_path} {qemu_args} 2>&1\
 < {trace_path}".format(timeout=TIMEOUT,
qemu_path=QEMU_PATH,
qemu_args=QEMU_ARGS,
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, _ = proc.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(proc.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

[PATCH v3 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

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

v2 --> v3:
  Fix: checkpatch.pl errors

v1 --> 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: loop the remove minimizer and refactoring
  fuzz: add minimization options
  fuzz: set bits in operand of write/out to zero
  fuzz: heuristic split write based on past IOs

 scripts/oss-fuzz/minimize_qtest_trace.py | 260 ++-
 1 file changed, 212 insertions(+), 48 deletions(-)

-- 
2.25.1

[PATCH v2 7/7] fuzz: heuristic split write based on past IOs

[Qiuhao Li]

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 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 55 
 1 file changed, 55 insertions(+)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 7947eb1d40..98bcd0cc8a 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -83,6 +83,42 @@ 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_minimizer(newtrace, outpath):
 remove_step = 1
@@ -147,6 +183,25 @@ def remove_minimizer(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

[PATCH v2 5/7] fuzz: set bits in operand of write/out 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.

Signed-off-by: Qiuhao Li 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 41 +++-
 1 file changed, 40 insertions(+), 1 deletion(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 0cc88da933..bcb32ee173 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -164,6 +164,42 @@ def remove_minimizer(newtrace, outpath):
 i += 1
 
 
+def set_zero_minimizer(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_minimizer(newtrace, outpath)
 newtrace = list(filter(lambda s: s != "", newtrace))
-
+assert(check_if_trace_crashes(newtrace, outpath))
+
+# set zero minimizer
+set_zero_minimizer(newtrace, outpath)
 assert(check_if_trace_crashes(newtrace, outpath))
 
 
-- 
2.25.1

[PATCH v2 6/7] fuzz: add minimization options

[Qiuhao Li]

-M1: loop around the remove minimizer
-M2: try setting bits in operand of write/out to zero
Signed-off-by: Qiuhao Li 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 30 
 1 file changed, 25 insertions(+), 5 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index bcb32ee173..7947eb1d40 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 # loop around the remove minimizer
+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,19 @@ 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 +226,31 @@ def minimize_trace(inpath, outpath):
 print("Setting the timeout for {} seconds".format(TIMEOUT))
 
 newtrace = trace[:]
-
+global M1, M2
 # remove minimizer
 old_len = len(newtrace) + 1
 while(old_len > len(newtrace)):
 old_len = len(newtrace)
+print("trace lenth = ", old_len)
 remove_minimizer(newtrace, outpath)
+if not M1 and not M2:
+break
 newtrace = list(filter(lambda s: s != "", newtrace))
 assert(check_if_trace_crashes(newtrace, outpath))
 
 # set zero minimizer
-set_zero_minimizer(newtrace, outpath)
+if M2:
+set_zero_minimizer(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 +259,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

[PATCH v2 2/7] fuzz: double the IOs to remove for every loop

[Qiuhao Li]

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 
---
 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 a290dc0579..71fb0cef32 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

[PATCH v2 4/7] fuzz: loop the remove minimizer and refactoring

[Qiuhao Li]

Now we use a one-time scan and remove strategy in the remval 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 
---
 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 dd6eeb7258..0cc88da933 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_minimizer(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 minimizer
+old_len = len(newtrace) + 1
+while(old_len > len(newtrace)):
+old_len = len(newtrace)
+remove_minimizer(newtrace, outpath)
+newtrace = list(filter(lambda s: s != "", newtrace))
+
+assert(check_if_trace_crashes(newtrace, outpath))
 
 
 if __name__ == '__main__':
-- 
2.25.1

[PATCH v2 3/7] fuzz: split write operand using binary approach

[Qiuhao Li]

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 uuuu

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 uu

For uu, 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:

   uu len=6
+
|
+
 xxx,xuu 6/2=3 fail
+
 +--+-+
 ||
 ++
  xx,xxuu 6/2^2=1 fail u,u 6-1=5 success
 +   +
 +--++   |
 |  |+-+ u removed
 +  +
   xx,xxu 5/2=2 fail  ,u 6-2=4 success
   +
   |
   +---+ u removed

In some rare case, this algorithm will fail to trim all unnecessary bytes:

  xuxx
  -xuxx Fail
  -xuxx Fail
  xuxx- Fail
  ...

I think the trade-off is worth it.

Signed-off-by: Qiuhao Li 
---
 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 71fb0cef32..dd6eeb7258 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., xuxx (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 

[PATCH v2 1/7] fuzz: accelerate non-crash detection

[Qiuhao Li]

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 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 41 
 1 file changed, 28 insertions(+), 13 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5e405a0d5f..a290dc0579 100755
--- a/scripts/oss-fuzz/minimize_qtest_trace.py
+++ b/scripts/oss-fuzz/minimize_qtest_trace.py
@@ -29,30 +29,46 @@ 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))
 
-rc = subprocess.Popen("timeout -s 9 {timeout}s {qemu_path} {qemu_args} 
2>&1\
+proc = subprocess.Popen("timeout {timeout}s {qemu_path} {qemu_args} 2>&1\
 < {trace_path}".format(timeout=TIMEOUT,
qemu_path=QEMU_PATH,
qemu_args=QEMU_ARGS,
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, _ = proc.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(proc.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

[PATCH v2 0/7] fuzz: improve crash case minimization

[Qiuhao Li]

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

v1 --> 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: loop the remove minimizer and refactoring
  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 | 256 ++-
 1 file changed, 208 insertions(+), 48 deletions(-)

-- 
2.25.1

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

[Qiuhao Li]

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 0x881coutl 0xcf8 0x0
> > > > outb 0xcfc 0xc3| outl 0xcf8 0x881c
> > > > outl 0xcf8 0x8804  | outb 0xcfc 0xc3
> > > > outl 0xcfc 0x1006  | outl 0xcf8 0x8804
> > > > write 0xc31028 0x1 0x5a| outl 0xcfc 0x1006
> > > > write 0xc31024 0x2 0x10| write 0xc31028 0x1 0x5a
> > > > write 0xc3101c 0x1 0x01| writel 0xc3100c 0x2a6f6c63
> > > > write 0xc33002 0x1 0x0 v write 0xc31024 0x2 0x10
> > > > write 0x5c 0x1 0x10  write 0xc3101c 0x1 0x01
> > > > writel 0xc3100c 0x2a6f6c63   write 0xc31018 0x1 0x80
> > > > write 0xc31018 0x1 0x80  write 0x5c 0x1 0x10
> > > > outl 0xcf8 0x0   write 0xc33002 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 0x881c
> > outb 0xcfc 0xc3
> > outl 0xcf8 0x0<--- The A instruction, didn't be
> > removed
> > (outl 0xcfc 0x0)  <--- The B instruction, removed
> > outl 0xcf8 0x8804
> > outl 0xcfc 0x1006
> > write 0xc31024 0x2 0x10
> > write 0xc31028 0x1 0x5a
> > write 0xc3101c 0x1 0x01
> > writel 0xc3100c 0x2a6f6c63
> > write 0xc31018 0x1 0x80
> > write 0x5c 0x1 0x10
> > write 0xc33002 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
> > > w

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 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 0x881coutl 0xcf8 0x0
> > outb 0xcfc 0xc3| outl 0xcf8 0x881c
> > outl 0xcf8 0x8804  | outb 0xcfc 0xc3
> > outl 0xcfc 0x1006  | outl 0xcf8 0x8804
> > write 0xc31028 0x1 0x5a| outl 0xcfc 0x1006
> > write 0xc31024 0x2 0x10| write 0xc31028 0x1 0x5a
> > write 0xc3101c 0x1 0x01| writel 0xc3100c 0x2a6f6c63
> > write 0xc33002 0x1 0x0 v write 0xc31024 0x2 0x10
> > write 0x5c 0x1 0x10  write 0xc3101c 0x1 0x01
> > writel 0xc3100c 0x2a6f6c63   write 0xc31018 0x1 0x80
> > write 0xc31018 0x1 0x80  write 0x5c 0x1 0x10
> > outl 0xcf8 0x0   write 0xc33002 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 0x881c
outb 0xcfc 0xc3
outl 0xcf8 0x0<--- The A instruction, didn't be removed
(outl 0xcfc 0x0)  <--- The B instruction, removed
outl 0xcf8 0x8804
outl 0xcfc 0x1006
write 0xc31024 0x2 0x10
write 0xc31028 0x1 0x5a
write 0xc3101c 0x1 0x01
writel 0xc3100c 0x2a6f6c63
write 0xc31018 0x1 0x80
write 0x5c 0x1 0x10
write 0xc33002 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 0xc3100c? write 0xc31018?
> Is there another example where this type of reordering makes the
> result
> easier to read?
> 
> > Signed-off-by: Qiuhao Li 
> > ---
> >  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 >

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 0x881coutl 0xcf8 0x881c
> > outb 0xcfc 0xc3  outb 0xcfc 0xc3
> > outl 0xcf8 0x0   <-- outl 0xcf8 0x882f
> > outl 0xcf8 0x8804outl 0xcf8 0x8804
> > outl 0xcfc 0x1006<-- outl 0xcfc 0x9b2765be
> > write 0xc31024 0x2 0x10  <-- write 0xc31024 0x2 0x0055
> > write 0xc31028 0x1 0x5a  write 0xc31028 0x1 0x5a
> > write 0xc3101c 0x1 0x01  write 0xc3101c 0x1 0x01
> > writel 0xc3100c 0x2a6f6c63   writel 0xc3100c 0x2a6f6c63
> > write 0xc31018 0x1 0x80  <-- write 0xc31018 0x1 0xa4
> > write 0x5c 0x1 0x10  <-- write 0x5c 0x1 0x19
> > write 0xc33002 0x1 0x0   <-- write 0xc33002 0x1 0x8a
> > 
> > Signed-off-by: Qiuhao Li 
> 
> Looks good. One nit below.
> 
> Reviewed-by: Alexander Bulekov 
> 
> 
> > ---
> >  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
> > 

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  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 uuuu
> > 
> > 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 uu
> > 
> > For uu, 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 0x881coutl 0xcf8 0x881c
> > outb 0xcfc 0xc3  outb 0xcfc 0xc3
> > outl 0xcf8 0x882foutl 0xcf8 0x882f
> > outl 0xcf8 0x8804outl 0xcf8 0x8804
> > outl 0xcfc 0x9b2765beoutl 0xcfc 0x9b2765be
> > write 0xc31024 0x2 0x0055write 0xc31024 0x2 0x0055
> > write 0xc31028 0x1 0x5a  write 0xc31028 0x1 0x5a
> > write 0xc3101c 0x1 0x01  write 0xc3101c 0x1 0x01
> > writel 0xc3100c 0x2a6f6c63   writel 0xc3100c 0x2a6f6c63
> > write 0xc31018 0x1 0xa4  <-- write 0xc31016 0x3 0xa4a4a4
> > write 0x5c 0x1 0x19  write 0x5c 0x1 0x19
> > write 0xc33002 0x1 0x8a  write 0xc33002 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.
> uu ->
> xxx xuu ->
> xx xxuu ->
> x xxxuu ->
> u 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


uu len=6
 +
 |
 +
  xxx,xuu  (1+6)/2=3
 +
  +--+-+
  ||
  +    +
   xx,xxuu (1+3)/2=2,uu (3+6)/2=4
  +   success
  |
   +--+--+
   | |
   | |
   + +
x,xxxuu (1+2)/2=1 xx,xxuu (2+3)/2=2
 base casebase case
> 
> > Signed-off-by: Qiuhao Li 
> > ---
> >  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
> >  

[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 0x881coutl 0xcf8 0x0
outb 0xcfc 0xc3| outl 0xcf8 0x881c
outl 0xcf8 0x8804  | outb 0xcfc 0xc3
outl 0xcfc 0x1006  | outl 0xcf8 0x8804
write 0xc31028 0x1 0x5a| outl 0xcfc 0x1006
write 0xc31024 0x2 0x10| write 0xc31028 0x1 0x5a
write 0xc3101c 0x1 0x01| writel 0xc3100c 0x2a6f6c63
write 0xc33002 0x1 0x0 v write 0xc31024 0x2 0x10
write 0x5c 0x1 0x10  write 0xc3101c 0x1 0x01
writel 0xc3100c 0x2a6f6c63   write 0xc31018 0x1 0x80
write 0xc31018 0x1 0x80  write 0x5c 0x1 0x10
outl 0xcf8 0x0   write 0xc33002 0x1 0x0

Signed-off-by: Qiuhao Li 
---
 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

[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 uuuu

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 uu

For uu, 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 0x881coutl 0xcf8 0x881c
outb 0xcfc 0xc3  outb 0xcfc 0xc3
outl 0xcf8 0x882foutl 0xcf8 0x882f
outl 0xcf8 0x8804outl 0xcf8 0x8804
outl 0xcfc 0x9b2765beoutl 0xcfc 0x9b2765be
write 0xc31024 0x2 0x0055write 0xc31024 0x2 0x0055
write 0xc31028 0x1 0x5a  write 0xc31028 0x1 0x5a
write 0xc3101c 0x1 0x01  write 0xc3101c 0x1 0x01
writel 0xc3100c 0x2a6f6c63   writel 0xc3100c 0x2a6f6c63
write 0xc31018 0x1 0xa4  <-- write 0xc31016 0x3 0xa4a4a4
write 0x5c 0x1 0x19  write 0x5c 0x1 0x19
write 0xc33002 0x1 0x8a  write 0xc33002 0x1 0x8a

Signed-off-by: Qiuhao Li 
---
 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 0x881coutl 0xcf8 0x881c
outb 0xcfc 0xc3  outb 0xcfc 0xc3
outl 0xcf8 0x0   <-- outl 0xcf8 0x882f
outl 0xcf8 0x8804outl 0xcf8 0x8804
outl 0xcfc 0x1006<-- outl 0xcfc 0x9b2765be
write 0xc31024 0x2 0x10  <-- write 0xc31024 0x2 0x0055
write 0xc31028 0x1 0x5a  write 0xc31028 0x1 0x5a
write 0xc3101c 0x1 0x01  write 0xc3101c 0x1 0x01
writel 0xc3100c 0x2a6f6c63   writel 0xc3100c 0x2a6f6c63
write 0xc31018 0x1 0x80  <-- write 0xc31018 0x1 0xa4
write 0x5c 0x1 0x10  <-- write 0x5c 0x1 0x19
write 0xc33002 0x1 0x0   <-- write 0xc33002 0x1 0x8a

Signed-off-by: Qiuhao Li 
---
 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

[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 
---
 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 (th

[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] 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 
---
 scripts/oss-fuzz/minimize_qtest_trace.py | 60 +++-
 1 file changed, 47 insertions(+), 13 deletions(-)

diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py 
b/scripts/oss-fuzz/minimize_qtest_trace.py
index 5e405a0d5f..96629b42e5 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 (th

[Bug 1890333] Re: [OSS-Fuzz] Issue 26797: qemu:qemu-fuzz-i386-target-generic-fuzz-virtio-blk: ASSERT: addr < cache->len && 2 <= cache->len - addr

[Qiuhao Li]

There is a new bug that fails the same assertion, and maybe its minimized 
producer will help:
  https://bugs.launchpad.net/qemu/+bug/1908062

-- 
You received this bug notification because you are a member of qemu-
devel-ml, which is subscribed to QEMU.
https://bugs.launchpad.net/bugs/1890333

Title:
  [OSS-Fuzz]  Issue 26797: qemu:qemu-fuzz-i386-target-generic-fuzz-
  virtio-blk: ASSERT: addr < cache->len && 2 <= cache->len - addr

Status in QEMU:
  Fix Released

Bug description:
  Hello,
  Reproducer:
  cat << EOF | ./i386-softmmu/qemu-system-i386 \
  -drive id=mydrive,file=null-co://,size=2M,format=raw,if=none \
  -device virtio-blk,drive=mydrive \
  -nodefaults -qtest stdio -nographic
  outl 0xcf8 0x80001001
  outl 0xcfc 0x6574c1ff
  outl 0xcf8 0x8000100e
  outl 0xcfc 0xefe5e1e
  outl 0xe86 0x3aff9090
  outl 0xe84 0x3aff9090
  outl 0xe8e 0xe
  EOF

  qemu-system-i386: 
/home/alxndr/Development/qemu/general-fuzz/include/exec/memory_ldst_cached.inc.h:88:
 void address_space_stw_le_cached(MemoryRegionCache *, hwaddr, uint32_t, 
MemTxAttrs, MemTxResult *): Assertion `addr < cache->len && 2 <= cache->len - 
addr' failed.
  Aborted

  I can trigger similar assertions with other VIRTIO devices, as-well.
  I reported this at some point in Message-ID: 
<20200511033001.dzvtbdhl3oz5p...@mozz.bu.edu> but never created a Launchpad 
issue...
  -Alex

To manage notifications about this bug go to:
https://bugs.launchpad.net/qemu/+bug/1890333/+subscriptions

[Bug 1890333] Re: [OSS-Fuzz] Issue 26797: qemu:qemu-fuzz-i386-target-generic-fuzz-virtio-blk: ASSERT: addr < cache->len && 2 <= cache->len - addr

[Qiuhao Li]

Hi,

It seems while the minimized producer doesn't fail the assertion now,
the original reproducer provided by OSS-Fuzz[1] can still crash the
latest QEMU (1758428, Dec 12, built with --enable-sanitizers --enable-
fuzzing). Could anyone check if they trigger different bugs?

Tested on:
  Ubuntu: 20.04.1 5.4.0-58-generic x86_64
  clang: 10.0.0-4ubuntu1
  glibc: 2.31-0ubuntu9.1
  libglib2.0-dev: 2.64.3-1~ubuntu20.04.1

[1] https://bugs.launchpad.net/qemu/+bug/1890333/comments/1

-- 
You received this bug notification because you are a member of qemu-
devel-ml, which is subscribed to QEMU.
https://bugs.launchpad.net/bugs/1890333

Title:
  [OSS-Fuzz]  Issue 26797: qemu:qemu-fuzz-i386-target-generic-fuzz-
  virtio-blk: ASSERT: addr < cache->len && 2 <= cache->len - addr

Status in QEMU:
  Fix Released

Bug description:
  Hello,
  Reproducer:
  cat << EOF | ./i386-softmmu/qemu-system-i386 \
  -drive id=mydrive,file=null-co://,size=2M,format=raw,if=none \
  -device virtio-blk,drive=mydrive \
  -nodefaults -qtest stdio -nographic
  outl 0xcf8 0x80001001
  outl 0xcfc 0x6574c1ff
  outl 0xcf8 0x8000100e
  outl 0xcfc 0xefe5e1e
  outl 0xe86 0x3aff9090
  outl 0xe84 0x3aff9090
  outl 0xe8e 0xe
  EOF

  qemu-system-i386: 
/home/alxndr/Development/qemu/general-fuzz/include/exec/memory_ldst_cached.inc.h:88:
 void address_space_stw_le_cached(MemoryRegionCache *, hwaddr, uint32_t, 
MemTxAttrs, MemTxResult *): Assertion `addr < cache->len && 2 <= cache->len - 
addr' failed.
  Aborted

  I can trigger similar assertions with other VIRTIO devices, as-well.
  I reported this at some point in Message-ID: 
<20200511033001.dzvtbdhl3oz5p...@mozz.bu.edu> but never created a Launchpad 
issue...
  -Alex

To manage notifications about this bug go to:
https://bugs.launchpad.net/qemu/+bug/1890333/+subscriptions

[Bug 1908062] Re: qemu-system-i386 virtio-vga: Assertion in address_space_stw_le_cached failed again

[Qiuhao Li]

--[ Original Fuzzing output

./build/qemu-fuzz-i386 --fuzz-target=generic-fuzz-virtio-vga
../fuzz/20201208/crash-da778083c63d2b24d8f7780383b2602a7a156352

qemu-fuzz-i386: 
/home/qiuhao/hack/qemu/include/exec/memory_ldst_cached.h.inc:88: void 
address_space_stw_le_cached(MemoryRegionCache *, hwaddr, uint32_t, MemTxAttrs, 
MemTxResult *): Assertion `addr < cache->len && 2 <= cache->len - addr' failed.
==37260== ERROR: libFuzzer: deadly signal
#0 0x56336c2ebc81 in __sanitizer_print_stack_trace 
(/home/qiuhao/hack/qemu/build/qemu-fuzz-i386+0x305dc81)
#1 0x56336c236dd8 in fuzzer::PrintStackTrace() 
(/home/qiuhao/hack/qemu/build/qemu-fuzz-i386+0x2fa8dd8)
#2 0x56336c21bf23 in fuzzer::Fuzzer::CrashCallback() 
(/home/qiuhao/hack/qemu/build/qemu-fuzz-i386+0x2f8df23)
#3 0x7f3122f7b3bf  (/lib/x86_64-linux-gnu/libpthread.so.0+0x153bf)
#4 0x7f3122d8c18a in __libc_signal_restore_set 
/build/glibc-ZN95T4/glibc-2.31/signal/../sysdeps/unix/sysv/linux/internal-signals.h:86:3
#5 0x7f3122d8c18a in raise 
/build/glibc-ZN95T4/glibc-2.31/signal/../sysdeps/unix/sysv/linux/raise.c:48:3
#6 0x7f3122d6b858 in abort 
/build/glibc-ZN95T4/glibc-2.31/stdlib/abort.c:79:7
#7 0x7f3122d6b728 in __assert_fail_base 
/build/glibc-ZN95T4/glibc-2.31/assert/assert.c:92:3
#8 0x7f3122d7cf35 in __assert_fail 
/build/glibc-ZN95T4/glibc-2.31/assert/assert.c:101:3
#9 0x56336ec7c8ab in address_space_stw_le_cached 
/home/qiuhao/hack/qemu/include/exec/memory_ldst_cached.h.inc:88:5
#10 0x56336ec7b746 in stw_le_phys_cached 
/home/qiuhao/hack/qemu/include/exec/memory_ldst_phys.h.inc:121:5
#11 0x56336ec7acf8 in virtio_stw_phys_cached 
/home/qiuhao/hack/qemu/include/hw/virtio/virtio-access.h:196:9
#12 0x56336ec79f7b in vring_set_avail_event 
/home/qiuhao/hack/qemu/build/../hw/virtio/virtio.c:429:5
#13 0x56336ec376f5 in virtqueue_split_pop 
/home/qiuhao/hack/qemu/build/../hw/virtio/virtio.c:1452:9
#14 0x56336ec3131c in virtqueue_pop 
/home/qiuhao/hack/qemu/build/../hw/virtio/virtio.c:1695:16
#15 0x56336c57fa43 in virtio_gpu_handle_ctrl 
/home/qiuhao/hack/qemu/build/../hw/display/virtio-gpu.c:877:11
#16 0x56336c57f6d9 in virtio_gpu_ctrl_bh 
/home/qiuhao/hack/qemu/build/../hw/display/virtio-gpu.c:898:5
#17 0x563370ad4952 in aio_bh_call 
/home/qiuhao/hack/qemu/build/../util/async.c:136:5
#18 0x563370ad6352 in aio_bh_poll 
/home/qiuhao/hack/qemu/build/../util/async.c:164:13
#19 0x563370a2773b in aio_dispatch 
/home/qiuhao/hack/qemu/build/../util/aio-posix.c:381:5
#20 0x563370adfd5e in aio_ctx_dispatch 
/home/qiuhao/hack/qemu/build/../util/async.c:306:5
#21 0x7f312319afbc in g_main_context_dispatch 
(/lib/x86_64-linux-gnu/libglib-2.0.so.0+0x51fbc)
#22 0x563370942137 in glib_pollfds_poll 
/home/qiuhao/hack/qemu/build/../util/main-loop.c:221:9
#23 0x56337093fa37 in os_host_main_loop_wait 
/home/qiuhao/hack/qemu/build/../util/main-loop.c:244:5
#24 0x56337093f387 in main_loop_wait 
/home/qiuhao/hack/qemu/build/../util/main-loop.c:520:11
#25 0x56336c33ec22 in flush_events 
/home/qiuhao/hack/qemu/build/../tests/qtest/fuzz/fuzz.c:49:9
#26 0x56336c33311b in generic_fuzz 
/home/qiuhao/hack/qemu/build/../tests/qtest/fuzz/generic_fuzz.c:683:17
#27 0x56336c340699 in LLVMFuzzerTestOneInput 
/home/qiuhao/hack/qemu/build/../tests/qtest/fuzz/fuzz.c:151:5
#28 0x56336c21d5e1 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, 
unsigned long) (/home/qiuhao/hack/qemu/build/qemu-fuzz-i386+0x2f8f5e1)
#29 0x56336c208d52 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, 
unsigned long) (/home/qiuhao/hack/qemu/build/qemu-fuzz-i386+0x2f7ad52)
#30 0x56336c20e806 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned 
char const*, unsigned long)) 
(/home/qiuhao/hack/qemu/build/qemu-fuzz-i386+0x2f80806)
#31 0x56336c2374c2 in main 
(/home/qiuhao/hack/qemu/build/qemu-fuzz-i386+0x2fa94c2)
#32 0x7f3122d6d0b2 in __libc_start_main 
/build/glibc-ZN95T4/glibc-2.31/csu/../csu/libc-start.c:308:16
#33 0x56336c1e341d in _start 
(/home/qiuhao/hack/qemu/build/qemu-fuzz-i386+0x2f5541d)

NOTE: libFuzzer has rudimentary signal handlers.
  Combine libFuzzer with AddressSanitizer or similar for better crash 
reports.
SUMMARY: libFuzzer: deadly signal


** Attachment added: "crash-da778083c63d2b24d8f7780383b2602a7a156352"
   
https://bugs.launchpad.net/qemu/+bug/1908062/+attachment/5443422/+files/crash-da778083c63d2b24d8f7780383b2602a7a156352

-- 
You received this bug notification because you are a member of qemu-
devel-ml, which is subscribed to QEMU.
https://bugs.launchpad.net/bugs/1908062

Title:
  qemu-system-i386 virtio-vga: Assertion in address_space_stw_le_cached
  failed again

Status in QEMU:
  New

Bug description:
  When I was fuzzing virtio-vga device of the latest QEMU (1758428, Dec
  12, built with --enable-sanitizers --enable-fuzzing), an assertion
  failed in include/exec/memory_ldst_cached.h.inc.

  --[ Reproducer

  cat << EOF | ./build/i386-softmmu/qe

[Bug 1908062] [NEW] qemu-system-i386 virtio-vga: Assertion in address_space_stw_le_cached failed again

[Qiuhao Li]

Public bug reported:

When I was fuzzing virtio-vga device of the latest QEMU (1758428, Dec
12, built with --enable-sanitizers --enable-fuzzing), an assertion
failed in include/exec/memory_ldst_cached.h.inc.

--[ Reproducer

cat << EOF | ./build/i386-softmmu/qemu-system-i386 -machine accel=qtest \
-machine q35 -display none -nodefaults -device virtio-vga -qtest stdio
outl 0xcf8 0x881c
outb 0xcfc 0xc3
outl 0xcf8 0x8804
outb 0xcfc 0x06
write 0xc31024 0x2 0x0040
write 0xc31028 0x1 0x5a
write 0xc3101c 0x1 0x01
writel 0xc3100c 0x2000
write 0xc31016 0x3 0x80a080
write 0xc33002 0x1 0x80
write 0x5c 0x1 0x10
EOF

--[ Output

==35337==WARNING: ASan doesn't fully support makecontext/swapcontext functions 
and may produce false positives in some cases!
[I 1607946348.442865] OPENED
[R +0.059305] outl 0xcf8 0x881c
OK
[S +0.059326] OK
[R +0.059338] outb 0xcfc 0xc3
OK
[S +0.059355] OK
[R +0.059363] outl 0xcf8 0x8804
OK
[S +0.059369] OK
[R +0.059381] outb 0xcfc 0x06
OK
[S +0.061094] OK
[R +0.061107] write 0xc31024 0x2 0x0040
OK
[S +0.061120] OK
[R +0.061127] write 0xc31028 0x1 0x5a
OK
[S +0.061135] OK
[R +0.061142] write 0xc3101c 0x1 0x01
OK
[S +0.061158] OK
[R +0.061167] writel 0xc3100c 0x2000
OK
[S +0.061212] OK
[R +0.061222] write 0xc31016 0x3 0x80a080
OK
[S +0.061231] OK
[R +0.061238] write 0xc33002 0x1 0x80
OK
[S +0.061247] OK
[R +0.061253] write 0x5c 0x1 0x10
OK
[S +0.061403] OK
qemu-system-i386: 
/home/qiuhao/hack/qemu/include/exec/memory_ldst_cached.h.inc:88: void 
address_space_stw_le_cached(MemoryRegionCache *, hwaddr, uint32_t, MemTxAttrs, 
MemTxResult *): Assertion `addr < cache->len && 2 <= cache->len - addr' failed.

--[ Environment

Ubuntu 20.04.1 5.4.0-58-generic x86_64
clang: 10.0.0-4ubuntu1
glibc: 2.31-0ubuntu9.1
libglib2.0-dev: 2.64.3-1~ubuntu20.04.1

--[ Note

Alexander Bulekov found the same assertion failure on 2020-08-04,
https://bugs.launchpad.net/qemu/+bug/1890333, and it had been fixed in
commit 2d69eba5fe52045b2c8b0d04fd3806414352afc1.

Fam Zheng found the same assertion failure on 2018-09-29,
https://bugs.launchpad.net/qemu/+bug/1795148, and it had been fixed in
commit db812c4073c77c8a64db8d6663b3416a587c7b4a.

** Affects: qemu
 Importance: Undecided
 Status: New

-- 
You received this bug notification because you are a member of qemu-
devel-ml, which is subscribed to QEMU.
https://bugs.launchpad.net/bugs/1908062

Title:
  qemu-system-i386 virtio-vga: Assertion in address_space_stw_le_cached
  failed again

Status in QEMU:
  New

Bug description:
  When I was fuzzing virtio-vga device of the latest QEMU (1758428, Dec
  12, built with --enable-sanitizers --enable-fuzzing), an assertion
  failed in include/exec/memory_ldst_cached.h.inc.

  --[ Reproducer

  cat << EOF | ./build/i386-softmmu/qemu-system-i386 -machine accel=qtest \
  -machine q35 -display none -nodefaults -device virtio-vga -qtest stdio
  outl 0xcf8 0x881c
  outb 0xcfc 0xc3
  outl 0xcf8 0x8804
  outb 0xcfc 0x06
  write 0xc31024 0x2 0x0040
  write 0xc31028 0x1 0x5a
  write 0xc3101c 0x1 0x01
  writel 0xc3100c 0x2000
  write 0xc31016 0x3 0x80a080
  write 0xc33002 0x1 0x80
  write 0x5c 0x1 0x10
  EOF

  --[ Output

  ==35337==WARNING: ASan doesn't fully support makecontext/swapcontext 
functions and may produce false positives in some cases!
  [I 1607946348.442865] OPENED
  [R +0.059305] outl 0xcf8 0x881c
  OK
  [S +0.059326] OK
  [R +0.059338] outb 0xcfc 0xc3
  OK
  [S +0.059355] OK
  [R +0.059363] outl 0xcf8 0x8804
  OK
  [S +0.059369] OK
  [R +0.059381] outb 0xcfc 0x06
  OK
  [S +0.061094] OK
  [R +0.061107] write 0xc31024 0x2 0x0040
  OK
  [S +0.061120] OK
  [R +0.061127] write 0xc31028 0x1 0x5a
  OK
  [S +0.061135] OK
  [R +0.061142] write 0xc3101c 0x1 0x01
  OK
  [S +0.061158] OK
  [R +0.061167] writel 0xc3100c 0x2000
  OK
  [S +0.061212] OK
  [R +0.061222] write 0xc31016 0x3 0x80a080
  OK
  [S +0.061231] OK
  [R +0.061238] write 0xc33002 0x1 0x80
  OK
  [S +0.061247] OK
  [R +0.061253] write 0x5c 0x1 0x10
  OK
  [S +0.061403] OK
  qemu-system-i386: 
/home/qiuhao/hack/qemu/include/exec/memory_ldst_cached.h.inc:88: void 
address_space_stw_le_cached(MemoryRegionCache *, hwaddr, uint32_t, MemTxAttrs, 
MemTxResult *): Assertion `addr < cache->len && 2 <= cache->len - addr' failed.

  --[ Environment

  Ubuntu 20.04.1 5.4.0-58-generic x86_64
  clang: 10.0.0-4ubuntu1
  glibc: 2.31-0ubuntu9.1
  libglib2.0-dev: 2.64.3-1~ubuntu20.04.1

  --[ Note

  Alexander Bulekov found the same assertion failure on 2020-08-04,
  https://bugs.launchpad.net/qemu/+bug/1890333, and it had been fixed in
  commit 2d69eba5fe52045b2c8b0d04fd3806414352afc1.

  Fam Zheng found the same assertion failure on 2018-09-29,
  https://bugs.launchpad.net/qemu/+bug/1795148, and it had been fixed in
  commit db812c4073c77c8a64db8d6663b3416a587c7b4a.

To manage notifications about this bug go to:
https://bugs.launchpad.