TY - GEN
T1 - Random testing for higher-order, stateful programs
AU - Klein, Casey
AU - Flatt, Matthew
AU - Findler, Robert
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Automated test generation
KW - Racket
KW - Random testing
KW - Software testing
UR - http://www.scopus.com/inward/record.url?scp=78650115046&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78650115046&partnerID=8YFLogxK
U2 - 10.1145/1869459.1869505
DO - 10.1145/1869459.1869505
M3 - Conference contribution
AN - SCOPUS:78650115046
SN - 9781450302036
T3 - Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, OOPSLA
SP - 555
EP - 566
BT - OOPSLA'10 - Proceedings of the 2010 ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications
T2 - 2010 ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, OOPSLA'10
Y2 - 17 October 2010 through 21 October 2010
ER -