You are here


Interpolated N-grams for Model Based Testing

Model based testing offers a powerful mechanism to test complex and rapidly evolving applications, for which a stable and reliable model is available or can be obtained. FSM models can be defined upfront or can be inferred from observations of real executions. Test cases are then derived from such FSM models, according to various algorithms (e.g., graph or random visit algorithms), so as to satisfy some adequacy criterion (e.g., FSM transition coverage). The problem is that a relatively large proportion of the test cases obtained in this way might result to be non executable, because they involve infeasible paths.

Ngram-MBT implements a novel test case derivation strategy, based on the computation of interpolated N-gram statistics. Event sequences are generated for which the subsequences of size N respect the distribution of the N-tuples observed in the execution traces. In this way, generated and observed sequences share the same context (up to length N), hence increasing the likelihood for the generated test cases of being actually executable. A consequence of the increased proportion of feasible test cases is that model coverage increases as well.

A ZIP archive containing the source and compiled code of Ngram-MBT can be downloaded here.