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.

We import the following 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.


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)


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.


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.