1#!/usr/bin/env python3
2# -*- coding: utf-8 -*-
3
4"""
5This takes a crashing qtest trace and tries to remove superflous operations
6"""
7
8import sys
9import os
10import subprocess
11import time
12import struct
13
14QEMU_ARGS = None
15QEMU_PATH = None
16TIMEOUT = 5
17CRASH_TOKEN = None
18
19write_suffix_lookup = {"b": (1, "B"),
20                       "w": (2, "H"),
21                       "l": (4, "L"),
22                       "q": (8, "Q")}
23
24def usage():
25    sys.exit("""\
26Usage: QEMU_PATH="/path/to/qemu" QEMU_ARGS="args" {} input_trace output_trace
27By default, will try to use the second-to-last line in the output to identify
28whether the crash occred. Optionally, manually set a string that idenitifes the
29crash by setting CRASH_TOKEN=
30""".format((sys.argv[0])))
31
32deduplication_note = """\n\
33Note: While trimming the input, sometimes the mutated trace triggers a different
34type crash but indicates the same bug. Under this situation, our minimizer is
35incapable of recognizing and stopped from removing it. In the future, we may
36use a more sophisticated crash case deduplication method.
37\n"""
38
39def check_if_trace_crashes(trace, path):
40    with open(path, "w") as tracefile:
41        tracefile.write("".join(trace))
42
43    rc = subprocess.Popen("timeout -s 9 {timeout}s {qemu_path} {qemu_args} 2>&1\
44    < {trace_path}".format(timeout=TIMEOUT,
45                           qemu_path=QEMU_PATH,
46                           qemu_args=QEMU_ARGS,
47                           trace_path=path),
48                          shell=True,
49                          stdin=subprocess.PIPE,
50                          stdout=subprocess.PIPE,
51                          encoding="utf-8")
52    global CRASH_TOKEN
53    if CRASH_TOKEN is None:
54        try:
55            outs, _ = rc.communicate(timeout=5)
56            CRASH_TOKEN = " ".join(outs.splitlines()[-2].split()[0:3])
57        except subprocess.TimeoutExpired:
58            print("subprocess.TimeoutExpired")
59            return False
60        print("Identifying Crashes by this string: {}".format(CRASH_TOKEN))
61        global deduplication_note
62        print(deduplication_note)
63        return True
64
65    for line in iter(rc.stdout.readline, ""):
66        if "CLOSED" in line:
67            return False
68        if CRASH_TOKEN in line:
69            return True
70
71    print("\nWarning:")
72    print("  There is no 'CLOSED'or CRASH_TOKEN in the stdout of subprocess.")
73    print("  Usually this indicates a different type of crash.\n")
74    return False
75
76
77def minimize_trace(inpath, outpath):
78    global TIMEOUT
79    with open(inpath) as f:
80        trace = f.readlines()
81    start = time.time()
82    if not check_if_trace_crashes(trace, outpath):
83        sys.exit("The input qtest trace didn't cause a crash...")
84    end = time.time()
85    print("Crashed in {} seconds".format(end-start))
86    TIMEOUT = (end-start)*5
87    print("Setting the timeout for {} seconds".format(TIMEOUT))
88
89    i = 0
90    newtrace = trace[:]
91    remove_step = 1
92    while i < len(newtrace):
93        # 1.) Try to remove lines completely and reproduce the crash.
94        # If it works, we're done.
95        if (i+remove_step) >= len(newtrace):
96            remove_step = 1
97        prior = newtrace[i:i+remove_step]
98        for j in range(i, i+remove_step):
99            newtrace[j] = ""
100        print("Removing {lines} ...\n".format(lines=prior))
101        if check_if_trace_crashes(newtrace, outpath):
102            i += remove_step
103            # Double the number of lines to remove for next round
104            remove_step *= 2
105            continue
106        # Failed to remove multiple IOs, fast recovery
107        if remove_step > 1:
108            for j in range(i, i+remove_step):
109                newtrace[j] = prior[j-i]
110            remove_step = 1
111            continue
112        newtrace[i] = prior[0] # remove_step = 1
113
114        # 2.) Try to replace write{bwlq} commands with a write addr, len
115        # command. Since this can require swapping endianness, try both LE and
116        # BE options. We do this, so we can "trim" the writes in (3)
117
118        if (newtrace[i].startswith("write") and not
119            newtrace[i].startswith("write ")):
120            suffix = newtrace[i].split()[0][-1]
121            assert(suffix in write_suffix_lookup)
122            addr = int(newtrace[i].split()[1], 16)
123            value = int(newtrace[i].split()[2], 16)
124            for endianness in ['<', '>']:
125                data = struct.pack("{end}{size}".format(end=endianness,
126                                   size=write_suffix_lookup[suffix][1]),
127                                   value)
128                newtrace[i] = "write {addr} {size} 0x{data}\n".format(
129                    addr=hex(addr),
130                    size=hex(write_suffix_lookup[suffix][0]),
131                    data=data.hex())
132                if(check_if_trace_crashes(newtrace, outpath)):
133                    break
134            else:
135                newtrace[i] = prior[0]
136
137        # 3.) If it is a qtest write command: write addr len data, try to split
138        # it into two separate write commands. If splitting the data operand
139        # from length/2^n bytes to the left does not work, try to move the pivot
140        # to the right side, then add one to n, until length/2^n == 0. The idea
141        # is to prune unneccessary bytes from long writes, while accommodating
142        # arbitrary MemoryRegion access sizes and alignments.
143
144        # This algorithm will fail under some rare situations.
145        # e.g., xxxxxxxxxuxxxxxx (u is the unnecessary byte)
146
147        if newtrace[i].startswith("write "):
148            addr = int(newtrace[i].split()[1], 16)
149            length = int(newtrace[i].split()[2], 16)
150            data = newtrace[i].split()[3][2:]
151            if length > 1:
152                leftlength = int(length/2)
153                rightlength = length - leftlength
154                newtrace.insert(i+1, "")
155                power = 1
156                while leftlength > 0:
157                    newtrace[i] = "write {addr} {size} 0x{data}\n".format(
158                            addr=hex(addr),
159                            size=hex(leftlength),
160                            data=data[:leftlength*2])
161                    newtrace[i+1] = "write {addr} {size} 0x{data}\n".format(
162                            addr=hex(addr+leftlength),
163                            size=hex(rightlength),
164                            data=data[leftlength*2:])
165                    if check_if_trace_crashes(newtrace, outpath):
166                        break
167                    # move the pivot to right side
168                    if leftlength < rightlength:
169                        rightlength, leftlength = leftlength, rightlength
170                        continue
171                    power += 1
172                    leftlength = int(length/pow(2, power))
173                    rightlength = length - leftlength
174                if check_if_trace_crashes(newtrace, outpath):
175                    i -= 1
176                else:
177                    newtrace[i] = prior[0]
178                    del newtrace[i+1]
179        i += 1
180    check_if_trace_crashes(newtrace, outpath)
181
182
183if __name__ == '__main__':
184    if len(sys.argv) < 3:
185        usage()
186
187    QEMU_PATH = os.getenv("QEMU_PATH")
188    QEMU_ARGS = os.getenv("QEMU_ARGS")
189    if QEMU_PATH is None or QEMU_ARGS is None:
190        usage()
191    # if "accel" not in QEMU_ARGS:
192    #     QEMU_ARGS += " -accel qtest"
193    CRASH_TOKEN = os.getenv("CRASH_TOKEN")
194    QEMU_ARGS += " -qtest stdio -monitor none -serial none "
195    minimize_trace(sys.argv[1], sys.argv[2])
196