Random testing for higher-order, stateful programs

Casey Klein*, Matthew Flatt, Robert Findler

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publicationOOPSLA'10 - Proceedings of the 2010 ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications
Pages555-566
Number of pages12
DOIs
StatePublished - Dec 20 2010
Event2010 ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, OOPSLA'10 - Reno/Tahoe, NV, United States
Duration: Oct 17 2010Oct 21 2010

Other

Other2010 ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, OOPSLA'10
Country/TerritoryUnited States
CityReno/Tahoe, NV
Period10/17/1010/21/10

Keywords

  • Automated test generation
  • Racket
  • Random testing
  • Software testing

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Random testing for higher-order, stateful programs'. Together they form a unique fingerprint.

Cite this