Random testing for higher-order, stateful programs

Casey Klein*, Matthew Flatt, Robert Findler

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 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 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 languageEnglish (US)
Pages (from-to)555-566
Number of pages12
JournalACM SIGPLAN Notices
Volume45
Issue number10
DOIs
StatePublished - Oct 1 2010

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)

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

Cite this