Note: Pyiodide takes time to initialize. Wait until the Run all button has a red border.

Previously, we had discussed how delta-debugging worked, and I had explained at that time that when it comes to preserving semantics, the only options are either custom passes such as CReduce or commandeering the generator as done by Hypothesis. Of the two, the Hypothesis approach is actually more generalizable to arbitrary generators. Hence we will look at how it is done. For ease of naming, I will call this approach the generator reduction approach. Note that we use the simple delta debug on the choice sequences. This is different from Hypothesis in that Hypothesis uses a number of custom passes rather than delta debug. For further information on Hypothesis, please see the paper by MacIver et al.1 at ECOOP.

For the generator reduction to work, we need a generator in the first place. So, we start with a rather simple generator that we discussed previously.



The driver is as follows. Note that the grammar describes a simple assignment language.



A sample run

$ python3 lf.py 5
o = (h) + r - 0 + i - f - 1 + 0 + 0 - 1 + (0) + j - 1 - f + (((0)) + 1) - (((w))) + (p - a + m - l + s) - b + 0 - l - 1 + 1;
s = ((c + (1) - ((1)) - ((0))));
p = 1 + 1 - (u) + e + k + 1 - 0 - l + j + t - 1 - w - (i)

The context free grammar assignment_grammar generates assignment expressions. However, it tends to use variables before they are defined. We want to avoid that. However, using only defined variables is a context sensitive feature, which we incorporate by a small modification to the fuzzer.



We now allow only defined variables to be used for later expansion. The helper procedures defining_var is invoked when we produce the left hand side of the variable assignment, and the defined_var is invoked when the variable is referred to from the right hand side. Hence defined_var ensures only defined vars are used. The sync function ensures that the definition is complete only when the assignment is finished.

Note that the modifications assume the knowledge of the <var> key in the grammar defined in the driver.

The driver now includes a context sensitive grammar in the form of pre and post functions.



A sample run

$ python3   lf.py 6 
b = 1 - (((00) + 00 - 0)) + 1 - 0;
c = (b);
y = (0 + (b) + 0) - (1 - ((0)));
d = 1;

['b', 'c', 'y', 'd']

As you can see, the variables used are only those that were defined earlier. So, how do we minimize such a generated string?

For the answer, we need to modify our fuzzer a bit more. We need to make it take a stream of integers which are interpreted as the choices at each step.



The choice sequence both keeps track of all choices made, and also allows one to reuse previous choices.



The driver is as follows



A sample run

$ python3   lf.py 6
e = (1) + 1 + 00 + 00 - 00 + 00 - 0 + 1;
f = 1 - e - 1 + 1 + e - e + e + 1 - 1 - e - e;
e = e;
c = 1;
d = (f + 0 + e - e + (e));

['e', 'f', 'e', 'c', 'd']
[9, 1, 7, 4, 0, 0, 2, 9, 7, 5, 5, 0, 4, 7, 3, 6, 8, 8, 1, 3, 9, 8, 4, 9, 1,
6, 5, 1, 5, 6, 4, 7, 1, 3, 4, 1, 0, 9, 3, 5, 7, 3, 8, 9, 8, 0, 5, 3, 9, 6, 
4, 5, 9, 1, 1, 8, 8, 3, 1, 9, 4, 4, 3, 6, 7, 3, 2, 9, 3, 8, 0, 3, 2, 0, 5, 
8, 9, 9, 4, 5, 6, 8, 6, 4, 2, 7, 0, 2]

The choice sequence is printed out at the end. The same sequence can be used later, to produce the same string. We use this in the next step. Now, all that we need is to hook up the predicate for ddmin, and its definitions.

First, the traditional ddmin that works on independent deltas that we defined in the previous post.



The ddmin now operates on choice sequences. So we need to convert them back to string



We also need our predicate. Note that we specialcase None in case the ints_to_string cannot successfully produce a value.



The driver tries to minimize the string if predicate returns true.



A sample run

$ python3   lf.py 1
original:
e = (((00 - (00 + 00) - 0))) - (1);
f = e + e - e + ((e)) + e + (0) + e - (1);
g = f;
j = (e);
 61
minimal:
d = ((00));
 7
[6, 0, 8, 3, 7, 7, 8]

As you can see, the original string that is a 61 choice long sequence has become reduced to an 8 choice long sequence, with a corresponding decrease in the string length. At this point, note that it is fairly magick how the approach performs. In particular, as soon as an edit is made, the remaining choices are not interpreted as in the original string. What if we help the reducer by specifying an NOP that allows one to delete chunks with a chance for the remaining string to be interpreted similarly?

The idea is to delete a sequence of values and replace it by a single -1 value which will cause the choice fuzzer to interpret it as fill in with default value. The ddmin is modified as follows:



Next, we need to get our fuzzer to understand the -1 value. We add defaults to each nonterminal, and modify the select function to take a default value.



Rebinding our grammar



The choice sequence now returns the default when it sees the -1 value.





These are all the modifications that we require.

Using it:



Sample run:

$ python3   lfm.py 1
original:
e = (((00 - (00 + 00) - 0))) - (1);
f = e + e - e + ((e)) + e + (0) + e - (1);
g = f;
j = (e);
 61
minimal:
0 = ((0));
a=0;
 8
[2, 9, 1, -1, 7, 7, -1, -1]

How does this modification fare against the original without modification?

$ python3   lf.py 5
original:
i = (00) + ((00) + 00 - 1 - 0 + 00 - ((00 - 1) - ((00)))) + 00 + 00 + ((1));
 40
minimal:
d = ((1));
 8
[2, 2, 0, 3, 2, 2, 4, 5]
$ python3   lfm.py 5
original:
i = (00) + ((00) + 00 - 1 - 0 + 00 - ((00 - 1) - ((00)))) + 00 + 00 + ((1));
 40
minimal:
i = 0 + 0 + 0 + ((0));
 13
[9, 4, 5, 8, 0, -1, 0, -1, 0, -1, 2, 2, -1]

another

$ python3   lf.py 9 
original:
e = ((00 + (1) + 00 + 0));
h = ((e)) - (e) - 1 - e - 1 - 1 - 0 + e - ((0 + 1)) - 1 - e + e - e + 1 - e;
 71
minimal:
e = ((00 + 1 + 0));
j = 1;
 18
[7, 9, 5, 4, 2, 2, 0, 5, 8, 9, 1, 9, 6, 6, 1, 9, 9, 3]
$ python3   lfm.py 9
original:
e = ((00 + (1) + 00 + 0));
h = ((e)) - (e) - 1 - e - 1 - 1 - 0 + e - ((0 + 1)) - 1 - e + e - e + 1 - e;
 71
minimal:
e = ((0));
a=0;
 8
[7, 9, 5, 4, 2, 2, -1, -1]

Another

$ python3   lf.py 16
original:
e = 00 - (1 - 00 + 0 + (0) + 00 + 0);
j = ((0)) + e;
 33
minimal:
a = ((00));
 7
[0, 2, 9, 0, 7, 7, 3]
$ python3   lfm.py 16
original:
e = 00 - (1 - 00 + 0 + (0) + 00 + 0);
j = ((0)) + e;
 33
minimal:
0 = 0 - 0 + 0;
a = ((0));
 15
[5, 7, 7, -1, 0, 6, -1, -1, -1, 2, 9, 0, 7, 7, -1]

There does not seem to be a lot of advantage in using an NOP.

Next: How does this compare against the custom passes of Hypothesis? and how does it compare against direct delta debug and variants of HDD including Perses.

  1. Test-Case Reduction via Test-Case Generation:Insights From the Hypothesis Reducer by David R. MacIver and Alastair F. Donaldson at ECOOP 2020