| 1 | #!/usr/bin/env python3 |
| 2 | |
| 3 | """ |
| 4 | This takes a crashing qtest trace and tries to remove superfluous operations |
| 5 | """ |
| 6 | |
| 7 | import sys |
| 8 | import os |
| 9 | import subprocess |
| 10 | import time |
| 11 | import struct |
| 12 | |
| 13 | QEMU_ARGS = None |
| 14 | QEMU_PATH = None |
| 15 | TIMEOUT = 5 |
| 16 | CRASH_TOKEN = None |
| 17 | |
| 18 | # Minimization levels |
| 19 | M1 = False # try removing IO commands iteratively |
| 20 | M2 = False # try setting bits in operand of write/out to zero |
| 21 | |
| 22 | write_suffix_lookup = {"b": (1, "B"), |
| 23 | "w": (2, "H"), |
| 24 | "l": (4, "L"), |
| 25 | "q": (8, "Q")} |
| 26 | |
| 27 | def usage(): |
| 28 | sys.exit("""\ |
| 29 | Usage: |
| 30 | |
| 31 | QEMU_PATH="/path/to/qemu" QEMU_ARGS="args" {} [Options] input_trace output_trace |
| 32 | |
| 33 | By default, will try to use the second-to-last line in the output to identify |
| 34 | whether the crash occred. Optionally, manually set a string that idenitifes the |
| 35 | crash by setting CRASH_TOKEN= |
| 36 | |
| 37 | Options: |
| 38 | |
| 39 | -M1: enable a loop around the remove minimizer, which may help decrease some |
| 40 | timing dependent instructions. Off by default. |
| 41 | -M2: try setting bits in operand of write/out to zero. Off by default. |
| 42 | |
| 43 | """.format((sys.argv[0]))) |
| 44 | |
| 45 | deduplication_note = """\n\ |
| 46 | Note: While trimming the input, sometimes the mutated trace triggers a different |
| 47 | type crash but indicates the same bug. Under this situation, our minimizer is |
| 48 | incapable of recognizing and stopped from removing it. In the future, we may |
| 49 | use a more sophisticated crash case deduplication method. |
| 50 | \n""" |
| 51 | |
| 52 | def check_if_trace_crashes(trace, path): |
| 53 | with open(path, "w") as tracefile: |
| 54 | tracefile.write("".join(trace)) |
| 55 | |
| 56 | rc = subprocess.Popen("timeout -s 9 {timeout}s {qemu_path} {qemu_args} 2>&1\ |
| 57 | < {trace_path}".format(timeout=TIMEOUT, |
| 58 | qemu_path=QEMU_PATH, |
| 59 | qemu_args=QEMU_ARGS, |
| 60 | trace_path=path), |
| 61 | shell=True, |
| 62 | stdin=subprocess.PIPE, |
| 63 | stdout=subprocess.PIPE, |
| 64 | encoding="utf-8") |
| 65 | global CRASH_TOKEN |
| 66 | if CRASH_TOKEN is None: |
| 67 | try: |
| 68 | outs, _ = rc.communicate(timeout=5) |
| 69 | CRASH_TOKEN = " ".join(outs.splitlines()[-2].split()[0:3]) |
| 70 | except subprocess.TimeoutExpired: |
| 71 | print("subprocess.TimeoutExpired") |
| 72 | return False |
| 73 | print("Identifying Crashes by this string: {}".format(CRASH_TOKEN)) |
| 74 | global deduplication_note |
| 75 | print(deduplication_note) |
| 76 | return True |
| 77 | |
| 78 | for line in iter(rc.stdout.readline, ""): |
| 79 | if "CLOSED" in line: |
| 80 | return False |
| 81 | if CRASH_TOKEN in line: |
| 82 | return True |
| 83 | |
| 84 | print("\nWarning:") |
| 85 | print(" There is no 'CLOSED'or CRASH_TOKEN in the stdout of subprocess.") |
| 86 | print(" Usually this indicates a different type of crash.\n") |
| 87 | return False |
| 88 | |
| 89 | |
| 90 | # If previous write commands write the same length of data at the same |
| 91 | # interval, we view it as a hint. |
| 92 | def split_write_hint(newtrace, i): |
| 93 | HINT_LEN = 3 # > 2 |
| 94 | if i <=(HINT_LEN-1): |
| 95 | return None |
| 96 | |
| 97 | #find previous continuous write traces |
| 98 | k = 0 |
| 99 | l = i-1 |
| 100 | writes = [] |
| 101 | while (k != HINT_LEN and l >= 0): |
| 102 | if newtrace[l].startswith("write "): |
| 103 | writes.append(newtrace[l]) |
| 104 | k += 1 |
| 105 | l -= 1 |
| 106 | elif newtrace[l] == "": |
| 107 | l -= 1 |
| 108 | else: |
| 109 | return None |
| 110 | if k != HINT_LEN: |
| 111 | return None |
| 112 | |
| 113 | length = int(writes[0].split()[2], 16) |
| 114 | for j in range(1, HINT_LEN): |
| 115 | if length != int(writes[j].split()[2], 16): |
| 116 | return None |
| 117 | |
| 118 | step = int(writes[0].split()[1], 16) - int(writes[1].split()[1], 16) |
| 119 | for j in range(1, HINT_LEN-1): |
| 120 | if step != int(writes[j].split()[1], 16) - \ |
| 121 | int(writes[j+1].split()[1], 16): |
| 122 | return None |
| 123 | |
| 124 | return (int(writes[0].split()[1], 16)+step, length) |
| 125 | |
| 126 | |
| 127 | def remove_lines(newtrace, outpath): |
| 128 | remove_step = 1 |
| 129 | i = 0 |
| 130 | while i < len(newtrace): |
| 131 | # 1.) Try to remove lines completely and reproduce the crash. |
| 132 | # If it works, we're done. |
| 133 | if (i+remove_step) >= len(newtrace): |
| 134 | remove_step = 1 |
| 135 | prior = newtrace[i:i+remove_step] |
| 136 | for j in range(i, i+remove_step): |
| 137 | newtrace[j] = "" |
| 138 | print("Removing {lines} ...\n".format(lines=prior)) |
| 139 | if check_if_trace_crashes(newtrace, outpath): |
| 140 | i += remove_step |
| 141 | # Double the number of lines to remove for next round |
| 142 | remove_step *= 2 |
| 143 | continue |
| 144 | # Failed to remove multiple IOs, fast recovery |
| 145 | if remove_step > 1: |
| 146 | for j in range(i, i+remove_step): |
| 147 | newtrace[j] = prior[j-i] |
| 148 | remove_step = 1 |
| 149 | continue |
| 150 | newtrace[i] = prior[0] # remove_step = 1 |
| 151 | |
| 152 | # 2.) Try to replace write{bwlq} commands with a write addr, len |
| 153 | # command. Since this can require swapping endianness, try both LE and |
| 154 | # BE options. We do this, so we can "trim" the writes in (3) |
| 155 | |
| 156 | if (newtrace[i].startswith("write") and not |
| 157 | newtrace[i].startswith("write ")): |
| 158 | suffix = newtrace[i].split()[0][-1] |
| 159 | assert(suffix in write_suffix_lookup) |
| 160 | addr = int(newtrace[i].split()[1], 16) |
| 161 | value = int(newtrace[i].split()[2], 16) |
| 162 | for endianness in ['<', '>']: |
| 163 | data = struct.pack("{end}{size}".format(end=endianness, |
| 164 | size=write_suffix_lookup[suffix][1]), |
| 165 | value) |
| 166 | newtrace[i] = "write {addr} {size} 0x{data}\n".format( |
| 167 | addr=hex(addr), |
| 168 | size=hex(write_suffix_lookup[suffix][0]), |
| 169 | data=data.hex()) |
| 170 | if(check_if_trace_crashes(newtrace, outpath)): |
| 171 | break |
| 172 | else: |
| 173 | newtrace[i] = prior[0] |
| 174 | |
| 175 | # 3.) If it is a qtest write command: write addr len data, try to split |
| 176 | # it into two separate write commands. If splitting the data operand |
| 177 | # from length/2^n bytes to the left does not work, try to move the pivot |
| 178 | # to the right side, then add one to n, until length/2^n == 0. The idea |
| 179 | # is to prune unnecessary bytes from long writes, while accommodating |
| 180 | # arbitrary MemoryRegion access sizes and alignments. |
| 181 | |
| 182 | # This algorithm will fail under some rare situations. |
| 183 | # e.g., xxxxxxxxxuxxxxxx (u is the unnecessary byte) |
| 184 | |
| 185 | if newtrace[i].startswith("write "): |
| 186 | addr = int(newtrace[i].split()[1], 16) |
| 187 | length = int(newtrace[i].split()[2], 16) |
| 188 | data = newtrace[i].split()[3][2:] |
| 189 | if length > 1: |
| 190 | |
| 191 | # Can we get a hint from previous writes? |
| 192 | hint = split_write_hint(newtrace, i) |
| 193 | if hint is not None: |
| 194 | hint_addr = hint[0] |
| 195 | hint_len = hint[1] |
| 196 | if hint_addr >= addr and hint_addr+hint_len <= addr+length: |
| 197 | newtrace[i] = "write {addr} {size} 0x{data}\n".format( |
| 198 | addr=hex(hint_addr), |
| 199 | size=hex(hint_len), |
| 200 | data=data[(hint_addr-addr)*2:\ |
| 201 | (hint_addr-addr)*2+hint_len*2]) |
| 202 | if check_if_trace_crashes(newtrace, outpath): |
| 203 | # next round |
| 204 | i += 1 |
| 205 | continue |
| 206 | newtrace[i] = prior[0] |
| 207 | |
| 208 | # Try splitting it using a binary approach |
| 209 | leftlength = int(length/2) |
| 210 | rightlength = length - leftlength |
| 211 | newtrace.insert(i+1, "") |
| 212 | power = 1 |
| 213 | while leftlength > 0: |
| 214 | newtrace[i] = "write {addr} {size} 0x{data}\n".format( |
| 215 | addr=hex(addr), |
| 216 | size=hex(leftlength), |
| 217 | data=data[:leftlength*2]) |
| 218 | newtrace[i+1] = "write {addr} {size} 0x{data}\n".format( |
| 219 | addr=hex(addr+leftlength), |
| 220 | size=hex(rightlength), |
| 221 | data=data[leftlength*2:]) |
| 222 | if check_if_trace_crashes(newtrace, outpath): |
| 223 | break |
| 224 | # move the pivot to right side |
| 225 | if leftlength < rightlength: |
| 226 | rightlength, leftlength = leftlength, rightlength |
| 227 | continue |
| 228 | power += 1 |
| 229 | leftlength = int(length/pow(2, power)) |
| 230 | rightlength = length - leftlength |
| 231 | if check_if_trace_crashes(newtrace, outpath): |
| 232 | i -= 1 |
| 233 | else: |
| 234 | newtrace[i] = prior[0] |
| 235 | del newtrace[i+1] |
| 236 | i += 1 |
| 237 | |
| 238 | |
| 239 | def clear_bits(newtrace, outpath): |
| 240 | # try setting bits in operands of out/write to zero |
| 241 | i = 0 |
| 242 | while i < len(newtrace): |
| 243 | if (not newtrace[i].startswith("write ") and not |
| 244 | newtrace[i].startswith("out")): |
| 245 | i += 1 |
| 246 | continue |
| 247 | # write ADDR SIZE DATA |
| 248 | # outx ADDR VALUE |
| 249 | print("\nzero setting bits: {}".format(newtrace[i])) |
| 250 | |
| 251 | prefix = " ".join(newtrace[i].split()[:-1]) |
| 252 | data = newtrace[i].split()[-1] |
| 253 | data_bin = bin(int(data, 16)) |
| 254 | data_bin_list = list(data_bin) |
| 255 | |
| 256 | for j in range(2, len(data_bin_list)): |
| 257 | prior = newtrace[i] |
| 258 | if (data_bin_list[j] == '1'): |
| 259 | data_bin_list[j] = '0' |
| 260 | data_try = hex(int("".join(data_bin_list), 2)) |
| 261 | # It seems qtest only accepts padded hex-values. |
| 262 | if len(data_try) % 2 == 1: |
| 263 | data_try = data_try[:2] + "0" + data_try[2:] |
| 264 | |
| 265 | newtrace[i] = "{prefix} {data_try}\n".format( |
| 266 | prefix=prefix, |
| 267 | data_try=data_try) |
| 268 | |
| 269 | if not check_if_trace_crashes(newtrace, outpath): |
| 270 | data_bin_list[j] = '1' |
| 271 | newtrace[i] = prior |
| 272 | i += 1 |
| 273 | |
| 274 | |
| 275 | def minimize_trace(inpath, outpath): |
| 276 | global TIMEOUT |
| 277 | with open(inpath) as f: |
| 278 | trace = f.readlines() |
| 279 | start = time.time() |
| 280 | if not check_if_trace_crashes(trace, outpath): |
| 281 | sys.exit("The input qtest trace didn't cause a crash...") |
| 282 | end = time.time() |
| 283 | print("Crashed in {} seconds".format(end-start)) |
| 284 | TIMEOUT = (end-start)*5 |
| 285 | print("Setting the timeout for {} seconds".format(TIMEOUT)) |
| 286 | |
| 287 | newtrace = trace[:] |
| 288 | global M1, M2 |
| 289 | |
| 290 | # remove lines |
| 291 | old_len = len(newtrace) + 1 |
| 292 | while(old_len > len(newtrace)): |
| 293 | old_len = len(newtrace) |
| 294 | print("trace length = ", old_len) |
| 295 | remove_lines(newtrace, outpath) |
| 296 | if not M1 and not M2: |
| 297 | break |
| 298 | newtrace = list(filter(lambda s: s != "", newtrace)) |
| 299 | assert(check_if_trace_crashes(newtrace, outpath)) |
| 300 | |
| 301 | # set bits to zero |
| 302 | if M2: |
| 303 | clear_bits(newtrace, outpath) |
| 304 | assert(check_if_trace_crashes(newtrace, outpath)) |
| 305 | |
| 306 | |
| 307 | if __name__ == '__main__': |
| 308 | if len(sys.argv) < 3: |
| 309 | usage() |
| 310 | if "-M1" in sys.argv: |
| 311 | M1 = True |
| 312 | if "-M2" in sys.argv: |
| 313 | M2 = True |
| 314 | QEMU_PATH = os.getenv("QEMU_PATH") |
| 315 | QEMU_ARGS = os.getenv("QEMU_ARGS") |
| 316 | if QEMU_PATH is None or QEMU_ARGS is None: |
| 317 | usage() |
| 318 | # if "accel" not in QEMU_ARGS: |
| 319 | # QEMU_ARGS += " -accel qtest" |
| 320 | CRASH_TOKEN = os.getenv("CRASH_TOKEN") |
| 321 | QEMU_ARGS += " -qtest stdio -monitor none -serial none " |
| 322 | minimize_trace(sys.argv[-2], sys.argv[-1]) |