Skip to content

Instantly share code, notes, and snippets.

@visualzhou

visualzhou/cut-test.py

Created April 28, 2018 00:55
Show Gist options
  • Save visualzhou/c014c07bd9fae0d2265cb99475226361 to your computer and use it in GitHub Desktop.
Save visualzhou/c014c07bd9fae0d2265cb99475226361 to your computer and use it in GitHub Desktop.
Download ZIP
Find the minimal reproduction test from a generated fuzzer test failure
Raw
cut-test.py
from __future__ import print_function
from sets import Set
import sys
import re
import subprocess
def get_allowed_cases():
allowed_cases = []
for arg in sys.argv[1:]:
if "-" in arg:
# range
start = int(arg.split("-")[0])
end = int(arg.split("-")[1])
# print("adding ", arg, " into the allowed tests")
allowed_cases.append((start, end))
else:
# print("adding ", arg, " into the allowed tests")
allowed_cases.append((int(arg), int(arg)))
# print(allowed_cases)
return allowed_cases
def get_allowed_case_set(cases):
allowed_case_set = Set([-1])
for case in cases:
for i in range(case[0], case[1]+1):
allowed_case_set.add(i)
# print(allowed_case_set)
return allowed_case_set
def print_current_statement(allowed, current, buf, outfile):
if current in allowed:
for line in buf:
outfile.write(line)
# Return the first i (start <= i < end) such that test_func returns True.
# Assuming all number >= i also makes test_func() to return true.
# If i == end, then any number in [start:end] return false.
def bisect(test_func, start, end):
if start < 0:
raise ValueError('start must be non-negative.')
# Invariant: for i in [start:lo], test_func(i) == False;
# Invariant: for i in [hi:end], test_func(i) == True;
lo = start
hi = end
while lo < hi:
mid = (lo + hi) // 2
if test_func(mid):
hi = mid
else:
lo = mid + 1
return lo
def run_test():
bashCommand = "python buildscripts/resmoke.py --numClientsPerFixture=20 --suite=jstestfuzz_replication base.js"
with open('out.out', "w") as outfile:
ret = subprocess.call(bashCommand.split(), stdout=outfile)
bashCommand = "grep -a fassert out.out"
ret = subprocess.call(bashCommand.split(), stdout=subprocess.PIPE)
return ret == 0
def generate_test_file(allowed):
allowed_set = get_allowed_case_set(allowed)
base_file_name = "base-original.js"
current = None
buf = []
with open(base_file_name, "r") as original_file:
with open('base.js', "w") as outfile:
for line in original_file:
buf.append(line)
m = re.search("Top-level statement (\d*) completed in", line)
# Start cases
if "var _________________________" in line:
current = -1
elif m:
current = int(m.group(1))
if current is not None:
print_current_statement(allowed_set, current, buf, outfile)
current = None
buf = []
def find_necessary(must_have, start, end):
print("Finding the necessary statement between ", start, " and ", end)
allowed = list(must_have)
# If we cut [pos:end], return if the test can still reproduce the bug.
def test_cut(pos):
allowed.append((start, pos-1))
generate_test_file(allowed)
print("Testing ", allowed, end="")
sys.stdout.flush()
ret = run_test()
print(" result: ", ret)
allowed.pop()
return ret
# Find the first pos such that cutting [pos:end] can still reprodcue the bug.
pos = bisect(test_cut, start, end)
print("Found a necessary statement: ", pos-1)
return pos-1
def find_all_necesary(allowed):
# allowed = get_allowed_cases()
must_have = [c for c in allowed if c[0] == c[1]]
first_pair = next(c for c in allowed if c[0] != c[1])
if first_pair is None:
return must_have
must_have = [c for c in allowed if c != first_pair]
print("We must include ", must_have)
pos = find_necessary(must_have, first_pair[0], first_pair[1])
if pos >= first_pair[0]:
must_have.append((pos, pos))
return find_all_necesary(must_have + [(first_pair[0], pos)])
else:
return must_have
def main():
allowed = get_allowed_cases()
must_have = find_all_necesary(allowed)
print("Found the minimal reproduction test statements.", must_have)
def test_binary_search():
array = [1, 2, 5, 6, 10, 22, 30, 30]
pos = bisect(lambda x: array[x] >= 30, 0, len(array))
print(pos, array[pos])
if __name__ == "__main__":
main()
# run_test()
# test_binary_search()
# find_necessary([], -1, 801)
Raw
cut-test.py output
// We know statement 765 and 1624 are necessary, find the necessary statements between 0 and 765.
$ python cut-test.py 0-765 765 1624
We must include [(765, 765), (1624, 1624)]
Found a necessary statement between 0 and 765
Testing [(765, 765), (1624, 1624), (0, 381)] result: False
Testing [(765, 765), (1624, 1624), (0, 573)] result: False
Testing [(765, 765), (1624, 1624), (0, 669)] result: False
Testing [(765, 765), (1624, 1624), (0, 717)] result: False
Testing [(765, 765), (1624, 1624), (0, 741)] result: False
Testing [(765, 765), (1624, 1624), (0, 753)] result: False
Testing [(765, 765), (1624, 1624), (0, 759)] result: False
Testing [(765, 765), (1624, 1624), (0, 762)] result: False
Testing [(765, 765), (1624, 1624), (0, 763)] result: True
Found a necessary statement: 763
We must include [(765, 765), (1624, 1624), (763, 763)]
Found a necessary statement between 0 and 763
Testing [(765, 765), (1624, 1624), (763, 763), (0, 380)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (0, 571)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (0, 667)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (0, 715)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (0, 691)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (0, 703)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (0, 697)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (0, 700)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (0, 699)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (0, 698)] result: True
Found a necessary statement: 698
We must include [(765, 765), (1624, 1624), (763, 763), (698, 698)]
Found a necessary statement between 0 and 698
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 348)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 523)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 610)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 654)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 632)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 643)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 649)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 652)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (0, 653)] result: False
Found a necessary statement: 654
We must include [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654)]
Found a necessary statement between 0 and 654
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 326)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 490)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 408)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 449)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 470)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 480)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 485)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 488)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (0, 489)] result: False
Found a necessary statement: 490
We must include [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490)]
Found a necessary statement between 0 and 490
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 244)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 121)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 183)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 214)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 199)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 191)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 195)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 193)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (0, 194)] result: False
Found a necessary statement: 195
We must include [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195)]
Found a necessary statement between 0 and 195
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (0, 96)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (0, 47)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (0, 72)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (0, 60)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (0, 66)] result: False
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (0, 69)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (0, 68)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (0, 67)] result: False
Found a necessary statement: 68
We must include [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68)]
Found a necessary statement between 0 and 68
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68), (0, 33)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68), (0, 16)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68), (0, 7)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68), (0, 3)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68), (0, 1)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68), (0, 0)] result: True
Testing [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68), (0, -1)] result: True
Found a necessary statement: -1
Found the minimal reproduction test statements. [(765, 765), (1624, 1624), (763, 763), (698, 698), (654, 654), (490, 490), (195, 195), (68, 68)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment