Testing by means of inductive program learning

Given a program P and a set of alternative programs $P$, we generate a sequence of test cases that are adequate, in the sense that they distinguish the given program from all alternatives The, method is related to fault-based approaches to test case generation, but programs in $P$ need not be simple mutations of P. The technique for generating an adequate test set is based on the inductive learning of programs from finite sets of input-output examples: given a partial test set, we generate inductively a program P’ in $P$ which is consistent with P on those input values; then we look for an input value that distinguishes P from P’, and we repeat the process until no program except P can be induced from the generated examples. We show that the obtained test set is adequate with respect to the alternatives belonging to $P$. The method is made possible by a program induction procedure which has evolved from recent research in manchine learning and inductive logic programming. An implemented version of the test case generation procedure is demonstrated on simple and more complex list-processing programs, and the scalability of the approach is discussed.