Programmable Property-Based Testing
Summary
A new approach to Property-Based Testing (PBT), called deferred binding abstract syntax (DBAS), addresses the rigid coupling between property definitions and their execution runners in existing frameworks. DBAS reifies properties as a flexible data structure, allowing users to define and customize property runners without modifying core library internals. Implemented in Rocq, utilizing dependent types, and Racket, using dynamic types and macros, this method enables rapid prototyping of diverse testing strategies, including coverage-guided fuzzing, integrated shrinking, and parallel execution. Evaluation on the ETNA platform across Binary Search Trees, Red-Black Trees, and Simply-Typed Lambda Calculus workloads shows DBAS implementations have negligible performance overhead compared to traditional shallow embeddings like QuickChick and RackCheck. For instance, a DBAS external shrinker reduced System F terms 2.66 times smaller than RackCheck's integrated shrinker, and a parallel runner achieved a 3x speed-up for certain tasks.
Key takeaway
For software engineers or research scientists requiring highly customizable property-based testing, traditional frameworks often impose rigid execution loops. You should explore DBAS-based PBT libraries, such as those implemented in Rocq or Racket, to gain user-level control over testing strategies. This approach allows you to rapidly prototype and integrate advanced techniques like coverage-guided fuzzing or parallel execution without deep library modifications, significantly enhancing testing adaptability and experimentation.
Key insights
Deferred binding abstract syntax (DBAS) decouples PBT property specifications from their execution runners, enabling user-level customization of testing logic.
Principles
- Shallow embeddings restrict PBT runner customization.
- Reifying properties as data structures allows flexible interpretation.
- Mixed embeddings balance ease of use with extensibility.
Method
DBAS represents properties as an inductive data type, binding variables at their use sites rather than universal quantification, allowing structural inspection without concrete values.
In practice
- Develop custom PBT runners for specific needs.
- Fine-tune testing aspects like seed pool strategies.
- Switch between shrinking approaches (e.g., integrated vs. external).
Topics
- Property-Based Testing
- Deferred Binding Abstract Syntax
- Mixed Embeddings
- Rocq
- Racket
- Fuzzing
- Test Case Reduction
Code references
Best for: AI Scientist, Research Scientist, Software Engineer
Related on AIssential
Editorial summary, takeaway, and curation by AIssential. Original article published by cs.SE updates on arXiv.org.