# Specializing Context-Free Grammars for Not Inducing A Fault

## Contents

**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 Imports

These 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.- sympy

## Available Packages

These 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.

## Unreachable Grammar

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 `get_reachable_positions`

we can produce the unreachable grammar.

For ease of discussion, we name a
nonterminal E that is guaranteed to not produce fault tree `F`

as `<E neg(F)>`

.
That is, a tree that starts from <start neg(F)> is guaranteed not to contain
the fault tree `F`

.
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
grammar.
For each expansion rule of `<E>`

, we have to make sure that it does not lead
to `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
unreachable grammar.

Using it.

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.

Using

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 `neg(F1)`

Using

At this point, we can now define our `negated_grammar()`

The new grammar is as follows

Using it.

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.

Checks

## 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
`and(neg(A),neg(B))`

and `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.

## Artifacts

The runnable Python source for this notebook is available here.

The installable python wheel `gnegatedfaults`

is available here.