TLDR; This tutorial is a complete implementation of RPNI algorithm which infers the input specification from positive and negative samples. Such grammars can be useful for identifying the specification of blackbox programs when it is impossible to query the program directly, and only its behaviour on a limited set of samples is known. The Python interpreter is embedded so that you can work through the implementation steps.

In my previous posts, I have discussed how to parse with, fuzz with, and manipulate regular and context-free grammars. However, the availability of the input grammars may not be guaranteed in many cases. Often, the available documentation may not fully capture the input specification. For example, an input field advertizing the ISO 8601 date format as input may accept slight variations, or may not implement the format fully. In such cases, one has to rely on the available behaviour to infer the true specification.

Regular Positive and Negative Inference, RPNI for short, is a classical algorithm that allows us to determine the input specification from a set of positive and negative samples. It was introduced by Oncia and Garcia in 1992 ¹. The core idea of RPNI is to construct a Prefix Tree Acceptor (PTA, also called a Trie), then iteratively try and merge each state pair, and checking the resulting DFA against negative samples to verify that the resulting DFA is not overgeneralizing. Because the new DFA is produced by merging states within the DFA, it will continue to accept all existing positive samples. The negative samples provide the defense against overgeneralization. If any negative samples are accepted, the merging of the state pair is rejected. Continuing in this fashion, RPNI will compute the DFA that can accept all positive samples, and reject all negative samples.

Two things to note: Every DFA has a characteristic set of samples including positive and negative samples, when given to the RPNI algorithm, will result in the exact DFA of the blackbox. Further, RPNI will also infer the precise DFA in the limit. Finally, L* is called an active grammar inference algorithm because it is able to query the blackbox, while RPNI is called a passive grammar inference algorithm because it cannot query the blackbox.

Definitions

• Input symbol: A single symbol that is consumed by the machine which can move it from one state to another. The set of such symbols is called an alphabet, and is represented by \(A\).
• DFA: A Deterministic Finite-state Automaton is a machine which is a model of an input processor. It is represented as a set of discrete states, and transitions between them. The DFA is initialized to the start state.
• State: A state is one of the components of the DFA, and represents a particular phase of the machine. A state transitions to another when it is fed an input symbol. Some states are marked as accepting.
• Accepting State: Starting from the start state, and after consuming all the symbols in the input, the state reached is one of the accept states, then we say that the input was accepted by the machine.
• Starting State: The machine starts at the start state.
• Transition: A transition is a link between two states. A DFA transitions from one state to the next on consuming an input symbol.
• Terminal Symbol: A terminal symbol is a symbol in the alphabet of the language in a regular grammar. It is the equivalent of DFA transition in the grammar.
• Nonterminal Symbol: A nonterminal symbol defines the rules of expansion in the grammar. A nonterminal symbol is associated with a definition in the grammar which contains the above rules. It corresponds to a state in the DFA.
• Definition: A set of rules which can be applied to a nonterminal symbol for expansion.
• Rule: A single way to expand a nonterminal symbol. In the DFA context, it contains the transition as the token, and the ending state as the final nonterminal symbol.

Contents

1. Definitions
   1. Prerequisites
2. Grammar Inference
   1. The Reg Parse
   2. Reg parse
   3. RPNI Algorithm
   4. Building the Prefix Tree Acceptor (PTA)
      1. The PTA data structure
      2. State Merging
      3. RPNI algorithm implementation
   5. A Simple Example
   6. Modified RPNI with NFA
   7. The Blue-Fringe algorithm.
   8. The EDSM Heuristic
   9. Complexity and Limitations
   10. Extensions and Improvements
   11. Artifacts

Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.

Prerequisites

We need the fuzzer to generate inputs to parse and also to provide some utilities such as conversion of regular expression to grammars, random sampling from grammars etc. Hence, we import all that.

Grammar Inference

As before, let us assume that the specification to be inferred is a regular language.

So, given a list of inputs which contain strings that were accepted (postive samples) and rejected (negative samples), and without the ability to query the blackbox program, or look inside the blackbox program, how do you find what the program accepts? We start by constructing a PTA, which is then generalized into a DFA. The intuition here is that the PTA is already an over specialized DFA, and all we need to do is to identify which of the states are actually the same. So we keep pairing the states, and checking whether the constraints, i.e. all negative strings are rejected, hold. This is the key intuition for all algorithms that work with positive and negative samples only.

The RPNI Algorithm

RPNI is a classic algorithm for learning regular languages from positive and negative strings. As we mentioned before, the algorithm has two phases.

1. Building a Prefix Tree Acceptor: Create a PTA accepting all positive samples
2. State Merging: Iteratively merge states to generalize the DFA while holding the constraints.

The Reg Parse

Before we go further, let us define a few helper functions. First, we need to represent a DFA. A Deterministic Finite Automation can be adequately represented by a right linear regular grammar. That is, each nonterminal is equivalent to a state in the DFA. The start symbol of the grammar is the entry point for the DFA. Transitions from a state A to another state B is indicated as a rule <A> := b <B>. That is, state A transitions to state B on receiving the token b. This is represented as a Python dictionary.

{
'<A>'     : [['b', '<B>'], ['c', '<C>']],
'<B>'     : [['b', '<B>'], []],
'<C>'     : [[]]
}

As you can notice in the above representation, the accepting states are indicated by adding [] to the state. In the above, both <B> and <C> are accepting states. To make it easier to recognize, we insist that [] be only added as the last rule.

With this in mind, it becomes easy to define a matcher for this DFA. It is close to our original peg_parse, but with additional handling for the accepting states.

Reg parse

Let us test the reg parse.

RPNI Algorithm

We next detail the RPNI algorithm. The first step is to build the PTA

Building the Prefix Tree Acceptor (PTA)

We construct a PTA, from all examples.

The PTA data structure

A PTA is nothing but a simple DFA in the form of a tree. We wrap our grammar in a simple class.

Build a Prefix Tree Acceptor from positive examples. Given an example, we take it apart to characters, then take the first character, and identify the transition (i.e. the rule) from start symbol that contains the given character. Since this is a new DFA, such a transition will not be found. Hence, we create a new rule with a new nonterminal. Then, we proceed with the next character in the input the same way extending the transitions step by step in the grammar. We mark the final nonterminal created as accepting.

From the second example onward, we can start to trace the existing transitions. But as before, if a transition can’t be found, we create a new nonterminal representing the new state, and add the given transition to the grammar.

Let us test it out!

State Merging

Check if two states can be merged without accepting negative examples Two states are compatible if we can represent both state by a new common state The idea is to create a new DFA where first, we replace both states by a new state, which creates a regular grammar, then, convert it to a canonical regular grammar, then check if they are still rejecting negative samples.

First, we define a helper function

to merge two states, we first create the name of the new state, which we name as <or(state1,state2)>. Then, we replace the nonterminals representing state1 and state2 in all rules with the nonterminal <or(state1,state2)>. Once we do this, the regular grammar we obtain is no longer a simple DFA, but an NFA, i.e., a Nondeterministic Finite Automaton. We will need to reduce this back to a DFA later.

Let us test it. We can make an NFA to a DFA by calling canonical_regular_grammar() from earlier posts. We need a DFA to parse the input using dfa_parse. So we do that.

When merging two states, we also need to verify that the end result is consistent with the negative examples. So, we define this function.

Let us test it.

RPNI algorithm implementation

A Simple Example

Let us use RPNI to learn a simple pattern: strings over {a, b} that end with ‘b’.

The result illustrates a limitation of both RPNI and the DFA minimization algorithm. Effectively, we can’t factor out complex loops from the DFA because the DFA minimization is purely based on state equivalence. When there are complex loops, simple pairwise state equivalence would fail.

Next, let us attempt a larger example. Let us keep the negative strings, but use a fuzzer to generate positive strings.

Modified RPNI with NFA

Do we actually need DFA conversion as in the classical RPNI? State elimination is far easier if we are working with NFAs. NFAs are also smaller than corresponding DFAs, and the regular expression resulting from NFAs are likely to be correspondingly smaller. Finally, regular expression matching is quite fast in modern machines.

We now do not reduce the NFA to a DFA. The intuition is as follows:

1. We can directly convert the regular grammar (an NFA) to a regular expression, and quickly match.
2. We can keep merging the states in the NFA, and it should not affect correctness.
3. It should afford more repair opportunities by keeping as NFA.
4. The size should be exponentially smaller.

Let us test it.

The Blue-Fringe algorithm.

The state merging approach of naive RPNI is very simple. It first generates all possible state pairs, and tries merging each one by one. If we observe that two states could be merged, then we break the current sequence and restart merging with each state pairs again. This means that we may retry the same state pairs again and again.

Blue-Fringe ² is a solution to this problem. The idea is to have a constantly updating boundary of states that have been verified. Essentially, we colour our states into red and blue. Red states are verified to be distinct, and blue are states that are yet to be verified, but reachable directly from one of the red states.

At each step, we take one blue state, and try to merge it with each of the red states. If a merge is possible (i.e. no negative example is accepted after the merge), then we keep the merge, by retaining the merged state as a red state. If no merge can be performed, then the blue state is verified to be distinct. So, we promote it to a red state.

This allows the red/blue boundary (the blue fringe) to be expanded until all states have been verified, and the blue fringe disappears.

Since merges are only ever attempted between red and blue states, redundant merges are avoided. This makes it more efficeint than naive RPNI.

Note that which blue state to pick first is not specified. One of the best heuristics is EDSM ² which scores candidate merges by shared evidence. We implement EDSM next.

We first need a helper to fetch the states directly reachable from a given state.

Given the current DFA and the current red set, the blue fringe is simply the set of children of red states not already red.

Now, the RPNI bluefringe algorithm

Let us try bluefringe on the same example as before

The EDSM Heuristic

While Blue-Fringe solves the unbounded evaluation of states, it leaves a question unanswered: Which blue states should we try to merge with the red states first? This has an impact on the final DFA produced, and the accuracy obtained.

The Evidence-Driven State Merging (EDSM) ² heuristic is one answer. Rather than picking randomly, order all consistent merges at each step by the evidence available that the two states are actually equivalent (and hence the strongest available merge). Two states are likely equivalent if merging them triggers a merge of the states that succeeds them. So, first, we compute the score of a merge between two given states.

Let us now use this score to pick the merge with the highest score.

Let us try EDSM on the same example as before.

Complexity and Limitations

Time Complexity: The RPNI algorithm is \(O(p^3 n)\) where p is the size (sum of the lengths of all strings) of positive data, and n is the size of negative data.

Extensions and Improvements

Some of the important extensions to RPNI include Blue-Fringe together with its EDSM ² scoring heuristic (both implemented above), and RPNI2 ³.

Artifacts

The runnable Python source for this notebook is available here.

The installable python wheel rpni is available here.