From patchwork Mon Jan 11 13:43:19 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Thomas Huth X-Patchwork-Id: 1424635 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=nongnu.org (client-ip=209.51.188.17; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=hRP747Tg; dkim-atps=neutral Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4DDw2D74YPz9sSC for ; Tue, 12 Jan 2021 00:45:24 +1100 (AEDT) Received: from localhost ([::1]:51066 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kyxVZ-0002qg-84 for incoming@patchwork.ozlabs.org; Mon, 11 Jan 2021 08:45:22 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:52802) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kyxUQ-0002mU-FM for qemu-devel@nongnu.org; Mon, 11 Jan 2021 08:44:10 -0500 Received: from us-smtp-delivery-124.mimecast.com ([63.128.21.124]:45853) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.90_1) (envelope-from ) id 1kyxUI-00082z-OT for qemu-devel@nongnu.org; Mon, 11 Jan 2021 08:44:10 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1610372638; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=XNDB/zbscO4+OU66OLp30mkb+UKL1y4RXIyYgMDQTpY=; b=hRP747Tg7wLn8BF2GpD8lb9BkMiFo+if4TijXMcSTwu2EdNCCG0yLJljBwnWbe6H1PmlsE SxX8OB7AvHKiGzJ2LPrainCkyFGtYqtPA5qruPxLV6x1CD9iOG6nxm2yjj6luZjaHlvgu8 rLpj3s0YxhIThziLCjmiy0ENcZHqhYs= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-212-bTf0ohMeO3ChzOzDVsxM0g-1; Mon, 11 Jan 2021 08:43:54 -0500 X-MC-Unique: bTf0ohMeO3ChzOzDVsxM0g-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 320E719251A2; Mon, 11 Jan 2021 13:43:53 +0000 (UTC) Received: from thuth.com (ovpn-112-147.ams2.redhat.com [10.36.112.147]) by smtp.corp.redhat.com (Postfix) with ESMTP id 64E672BFE9; Mon, 11 Jan 2021 13:43:51 +0000 (UTC) From: Thomas Huth To: qemu-devel@nongnu.org, Peter Maydell Subject: [PULL 06/15] fuzz: split write operand using binary approach Date: Mon, 11 Jan 2021 14:43:19 +0100 Message-Id: <20210111134328.157775-7-thuth@redhat.com> In-Reply-To: <20210111134328.157775-1-thuth@redhat.com> References: <20210111134328.157775-1-thuth@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=thuth@redhat.com X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Received-SPF: pass client-ip=63.128.21.124; envelope-from=thuth@redhat.com; helo=us-smtp-delivery-124.mimecast.com X-Spam_score_int: -29 X-Spam_score: -3.0 X-Spam_bar: --- X-Spam_report: (-3.0 / 5.0 requ) BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.251, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Alexander Bulekov , Warner Losh , Qiuhao Li Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" From: 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 uuxxxxuu u is the unnecessary byte for the crash. Unlike ram write commands, in most case, a split IO write won't trigger the same crash, So if we split from the middle, we will get: write addr uu (will be removed in next round) write addr xxxxuu For xxxxuu, since split it from the middle and retry to the leftmost byte won't get the same crash, we will be stopped from removing the last two bytes. 2. The algorithm complexity is O(n) since we move the pivot byte by byte. To solve the first issue, we can try a symmetrical position on the right if we fail on the left. As for the second issue, instead moving by one byte, we can approach the boundary exponentially, achieving O(log(n)). Give an example: xxxxuu len=6 + | + xxx,xuu 6/2=3 fail + +--------------+-------------+ | | + + xx,xxuu 6/2^2=1 fail xxxxu,u 6-1=5 success + + +------------------+----+ | | | +-------------+ u removed + + xx,xxu 5/2=2 fail xxxx,u 6-2=4 success + | +-----------+ u removed In some rare cases, this algorithm will fail to trim all unnecessary bytes: xxxxxxxxxuxxxxxx xxxxxxxx-xuxxxxxx Fail xxxx-xxxxxuxxxxxx Fail xxxxxxxxxuxx-xxxx Fail ... I think the trade-off is worth it. Signed-off-by: Qiuhao Li Reviewed-by: Alexander Bulekov Tested-by: Alexander Bulekov Message-Id: Signed-off-by: Thomas Huth --- scripts/oss-fuzz/minimize_qtest_trace.py | 29 ++++++++++++++++-------- 1 file changed, 20 insertions(+), 9 deletions(-) diff --git a/scripts/oss-fuzz/minimize_qtest_trace.py b/scripts/oss-fuzz/minimize_qtest_trace.py index cacabf2638..af9767f7e4 100755 --- a/scripts/oss-fuzz/minimize_qtest_trace.py +++ b/scripts/oss-fuzz/minimize_qtest_trace.py @@ -97,7 +97,7 @@ def minimize_trace(inpath, outpath): prior = newtrace[i:i+remove_step] for j in range(i, i+remove_step): newtrace[j] = "" - print("Removing {lines} ...".format(lines=prior)) + print("Removing {lines} ...\n".format(lines=prior)) if check_if_trace_crashes(newtrace, outpath): i += remove_step # Double the number of lines to remove for next round @@ -110,9 +110,11 @@ def minimize_trace(inpath, outpath): remove_step = 1 continue newtrace[i] = prior[0] # remove_step = 1 + # 2.) Try to replace write{bwlq} commands with a write addr, len # command. Since this can require swapping endianness, try both LE and # BE options. We do this, so we can "trim" the writes in (3) + if (newtrace[i].startswith("write") and not newtrace[i].startswith("write ")): suffix = newtrace[i].split()[0][-1] @@ -133,11 +135,15 @@ def minimize_trace(inpath, outpath): newtrace[i] = prior[0] # 3.) If it is a qtest write command: write addr len data, try to split - # it into two separate write commands. If splitting the write down the - # middle does not work, try to move the pivot "left" and retry, until - # there is no space left. The idea is to prune unneccessary bytes from - # long writes, while accommodating arbitrary MemoryRegion access sizes - # and alignments. + # it into two separate write commands. If splitting the data operand + # from length/2^n bytes to the left does not work, try to move the pivot + # to the right side, then add one to n, until length/2^n == 0. The idea + # is to prune unneccessary bytes from long writes, while accommodating + # arbitrary MemoryRegion access sizes and alignments. + + # This algorithm will fail under some rare situations. + # e.g., xxxxxxxxxuxxxxxx (u is the unnecessary byte) + if newtrace[i].startswith("write "): addr = int(newtrace[i].split()[1], 16) length = int(newtrace[i].split()[2], 16) @@ -146,6 +152,7 @@ def minimize_trace(inpath, outpath): leftlength = int(length/2) rightlength = length - leftlength newtrace.insert(i+1, "") + power = 1 while leftlength > 0: newtrace[i] = "write {addr} {size} 0x{data}\n".format( addr=hex(addr), @@ -157,9 +164,13 @@ def minimize_trace(inpath, outpath): data=data[leftlength*2:]) if check_if_trace_crashes(newtrace, outpath): break - else: - leftlength -= 1 - rightlength += 1 + # move the pivot to right side + if leftlength < rightlength: + rightlength, leftlength = leftlength, rightlength + continue + power += 1 + leftlength = int(length/pow(2, power)) + rightlength = length - leftlength if check_if_trace_crashes(newtrace, outpath): i -= 1 else: