DART: Directed Automated Random Testing

From GradTurkey

[edit] Summary

A problem with dynamic analysis tools is that they are limited to analyzing the execution paths that are exercised. DART is a tool which "blends dynamic test generation with model checking techniques". It traces the execution of conditionals in a program, and attempts to build new test inputs that exercise a different control path by using previous executions as constraints on the variables. By using constraint solving to discover inputs that lead to code paths which have not yet been tested, DART is able to exercise all feasible code paths.

The approach of DART are best summarized by this quote from the paper:

"A standard model checking approach ... represents the program's environment (here the intruder) by a nondeterminisitic process that blindly guesses possible sequences of inputs (attacks), and then checks the effect of these on the program by performing state-space exploration. In contrast, a directed search as implemented in DART does not treat the program under test as a black-box. Instead, the directed search attempts to partition iteratively the program's input space into equivalence classes, and generate new inputs in order to exhibit new program responses -- inputs that trigger a previously considered program behavior are not generated and re-tested over and over again. In this sense, a directed search can be viewed as a more white-box approach..."