Research in Software Engineering from Rahul Gopinath
TLDR; This tutorial is a complete implementation of the TTT algorithm for active automata learning in Python. TTT combines the discrimination tree of Kearns and Vazirani with binary search counterexample analysis from Rivest and Schapire, and adds prefix transformation and discriminator finalization to eliminate all redundant membership queries. The Python interpreter is embedded so that you can…
TLDR; This tutorial is a complete implementation of a Daikon-like runtime invariant miner in Python. It implements basic instrumentation, collection of execution traces, invariant checking, and suppression of redundandant invariants. The Oracle Problem in Software Testing One of the key challenges in software testing is the Oracle Problem : That is, how do we determine if the output of a test is…
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…
This is a summary of best practices when using Makefiles . This post is primarily intended for my students building tools in our lab. Much of this post is based on the Make bestpractices that I learned during my stint at Sun Microsystems, updated to reflect GNU Make since it is the most common make flavour at this point by a significant margin. Contents (GNU) Makefiles best practices Automatic…
Contents Definitions Building a Tiny Prolog in Python Variables Predicates Goals Lists Environment Unification Resolution References Artifacts Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button. Run all TLDR; This tutorial is an implementation of a toy prolog interpreter in Python. It is based on an earlier implementation here…
Contents Definitions Prerequisites Building the NFA Augment Grammar with Start The State Data-structure The NFA class NFA Initialization routines NFA Start State (create_start) Advance the state of parse by one token NFA find_transitions NFA build_nfa Constructing a graph LR0 Automata Closure Compiling DFA States Building the DFA Item DFAState LR(0) DFA DFA Compute the closure DFA Start State…
Search Based Fuzzing involves generating various candidate inputs for a given program, identifying the inputs with the best score in some metric of effectiveness and choosing them for the next iteration so that one can iteratively improve the fitness of the given population of inputs. In the previous post I discussed how you can score inputs using approach level . Approach level (or approximation…
Fuzzing is one of the more easy to use and efficient means of testing software systems. The idea is that we produce random inputs that are then executed by the system. If the system does something unexpected (such as crashing) then we know that the path taken by the execution was not considered by the programmer, and that such a path may be exploited to make the program do something that was…
TL;DR This tutorial explains how to design test cases that effectively cover features of a given context-free grammar using the k-path strategy. Note : The k-path strategy discussed here is unrelated to the k-path cover from graph theory. Definitions For this post, we use the following terms as we have defiend previously: The alphabet is the set all of symbols in the input language. For example,…
TLDR; This tutorial takes you through the steps to write a simple context-free grammmar that can parse your custom data format. The Python interpreter is embedded so that you can work through the implementation steps. Definitions For this post, we use the following terms as we have defiend previously: The alphabet is the set all of symbols in the input language. For example, in this post, we use…