Random Testing for Higher-Order, Stateful Programs

• Published in: ACM SIGPLAN notices 2010-10, Vol.45 (10), p.555-566
• Main Authors: KLEIN, Casey, FLATT, Matthew, FINDLER, Robert Bruce
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Computer systems performance. Reliability; Exact sciences and technology; Software
• ISSN: 1523-2867; 0362-1340; 1558-1160
• DOI: 10.1145/1932682.1869505

Testing is among the most effective tools available for finding bugs. Still, we know of no automatic technique for generating test cases that expose bugs involving a combination of mutable state and callbacks, even though objects and method overriding set up exactly that combination. For such cases, a test generator must create callbacks or subclasses that aggressively exercise side-effecting operations using combinations of generated objects. This paper presents a new algorithm for randomly testing programs that use state and callbacks. Our algorithm exploits a combination of contracts and environment bindings to guide the test-case generator toward interesting inputs. Our prototype implementation for Racket (formerly PLT Scheme) - which has a Java-like class system, but with first-class classes as well as gbeta-like augmentable methods - uncovered dozens of bugs in a well-tested and widely used text-editor library. We describe our approach in a precise, formal notation, borrowing the techniques used to describe operational semantics and type systems. The formalism enables us to provide a compact and self-contained explanation of the core of our technique without the ambiguity usually present in pseudo-code descriptions.