Abstract
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 firstclass 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.
Original language | English (US) |
---|---|
Pages (from-to) | 555-566 |
Number of pages | 12 |
Journal | ACM SIGPLAN Notices |
Volume | 45 |
Issue number | 10 |
DOIs | |
State | Published - Oct 2010 |
Keywords
- Automated test generation
- Racket
- Random testing
- Software testing
ASJC Scopus subject areas
- General Computer Science