- A grammar with no fault inducing fragments.
Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.
This post is the implementation of my paper Input Algebras
In my previous post on inducing faults I explained the deficiency of abstract failure inducing inputs mined using DDSet, and showed how to overcome that by inserting that abstract (evocative) pattern into a grammar, producing evocative grammars that guarantee that the evocative fragment is present in any input generated. In this post, I will show how to do the opposite. That is, how to generate grammars that guarantee that evocative fragments are not present. As before, let us start with importing our required modules.
System ImportsThese are available from Pyodide, but you may wish to make sure that they are installed if you are attempting to run the program directly on the machine.
Available PackagesThese are packages that refer either to my previous posts or to pure python packages that I have compiled, and is available in the below locations. As before, install them if you need to run the program directly on the machine. To install, simply download the wheel file (`pkg.whl`) and install using `pip install pkg.whl`.
- earleyparser-0.0.1-py2.py3-none-any.whl from "Earley Parser".
- hdd-0.0.1-py2.py3-none-any.whl from "Hierarchical Delta Debugging".
- simplefuzzer-0.0.1-py2.py3-none-any.whl from "The simplest grammar fuzzer in the world".
- ddset-0.0.1-py2.py3-none-any.whl from "Simple DDSet".
- gatleastsinglefault-0.0.1-py2.py3-none-any.whl from "Specializing Context-Free Grammars for Inducing Faults".
- gmultiplefaults-0.0.1-py2.py3-none-any.whl from "Specializing Context-Free Grammars for Inducing Multiple Faults".
- gfaultexpressions-0.0.1-py2.py3-none-any.whl from "Fault Expressions for Specializing Context-Free Grammars".
The imported modules
A grammar with no fault inducing fragments.
We saw how to insert a single evocative pattern into a grammar. A similar procedure can be used to make sure that no evocative fragments are present in inputs generated by given grammar. The idea is as follows.
We start with the
get_reachable_positions() output. If we can ensure
that no nonterminals in the reachable_positions can actually produce a fault
inducing fragment, then we are done. So, given the
we can produce the unreachable grammar.
For ease of discussion, we name a
nonterminal E that is guaranteed to not produce fault tree
That is, a tree that starts from <start neg(F)> is guaranteed not to contain
the fault tree
So, the definition of
<E neg(F) is simple enough given the characterizing
node of the fault tree, and the corresponding reaching positions in the
For each expansion rule of
<E>, we have to make sure that it does not lead
F. So rules for
<E> that did not have reachable positions corresponding
to characterizing node of
F can be directly added to
<E neg(F)>. Next,
for any rule that contained reachable positions, for all such positions, we
specialize the nonterminal in that position by
neg(F). This gives us the
Next, we can define unreachable grammar using it.
Negated pattern grammar.
For negated pattern grammars, there are two parts. The first part is for pattern rules. The idea is to make sure that we can produce any but not the specific pattern in the current expansion. Next, we also need to make sure that the original fault is not reachable from any of the nonterminals.
For unmatching a refined rule in a pattern grammar, we simply can look at refinements necessary, and produce rules such that each produced rule will not match the pattern at a specific point. No further restrictions on the rule is necessary. So, we can use the base nonterminal there.
Now, for negated pattern grammars, not only do we need to make sure that the
pattern is not directly matchable, but also that the pattern cannot be
embedded. For that we simply conjunct it with
At this point, we can now define our
The new grammar is as follows
This grammar is now guaranteed not to produce any instance of the characterizing node.
However, as you can see the grammar is not complete. For completing the
grammar We need to rely on
reconstruction that we discussed in the last post.
Aside: Let us construct another function that checks the double
parenthesis we abstracted.
Negation of full evocative expressions
Negation of a single pattern is useful, but we may also want
to negate larger expressions such as say
neg(or(and(f1,f2),f3)). However, we
do not need to implement the complete negation as before. Instead, we can rely
on the fact that our evocative expressions are simply boolean expressions.
That is, expressions such
neg(or(A,B)) can be simplified as
neg(and(A,B)) can be simplified as
or(neg(A),neg(B)). This means that we do not need to implement the negation
beyond negating simple faults.
Here is an example of how it works.
The source for this notebook is available here.
The runnable Python source for this notebook is available here.
The installable python wheel
gnegatedfaults is available here.