CoChat

Coverage guided, property based testing

Open access
Lampropoulos, Leonidas, Hicks, Michael, Pierce, Benjamin C. · 2019 · Proceedings of the ACM on Programming Languages

The DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.

Abstract

Property-based random testing, exemplified by frameworks such as Haskell's QuickCheck, works by testing an executable predicate (a property) on a stream of randomly generated inputs. Property testing works very well in many cases, but not always. Some properties are conditioned on the input satisfying demanding semantic invariants that are not consequences of its syntactic structure---e.g., that an input list must be sorted or have no duplicates. Most randomly generated inputs fail to satisfy properties with such sparse preconditions, and so are simply discarded. As a result, much of the target system may go untested. We address this issue with a novel technique called coverage guided, property based testing (CGPT). Our approach is inspired by the related area of coverage guided fuzzing, exemplified by tools like AFL. Rather than just generating a fresh random input at each iteration, CGPT can also produce new inputs by mutating previous ones using type-aware, generic mutator operators. The target program is instrumented to track which control flow branches are executed during a run and inputs whose runs expand control-flow coverage are retained for future mutations. This means that, when sparse conditions in the target are satisfied and new coverage is observed, the input that triggered them will be retained and used as a springboard to go further. We have implemented CGPT as an extension to the QuickChick property testing tool for Coq programs; we call our implementation FuzzChick. We evaluate FuzzChick on two Coq developments for abstract machines that aim to enforce flavors of noninterference, which has a (very) sparse precondition. We systematically inject bugs in the machines' checking rules and use FuzzChick to look for counterexamples to the claim that they satisfy a standard noninterference property. We find that vanilla QuickChick almost always fails to find any bugs after a long period of time, as does an earlier proposal for combining property testing and fuzzing. In contrast, FuzzChick often finds them within seconds to minutes. Moreover, FuzzChick is almost fully automatic; although highly tuned, hand-written generators can find the bugs faster, they require substantial amounts of insight and manual effort.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3360607

Cites

47 of 47 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1 QuickChick vs FuzzChick workflows. QuickChick (left) uses a simple testing loop: a generator produces random structured data from a standard source of pseudo-random bits, and this data is used to test the desired property. On success, repeat; on failure, report the counterexample. FuzzChick (right) instead instruments the property being tested (including the system under test (SUT), but not the testing framework itself). Coverage information is used to determine whether the input (a data structure) is interesting or not. In addition, the tool decides between mutating an existing interesting input (if one exists) or generating new inputs randomly to reset the process. Both the mutator and the generator operate at the level of algebraic data types.
Fig. 1 QuickChick vs FuzzChick workflows. QuickChick (left) uses a simple testing loop: a generator produces random structured data from a standard source of pseudo-random bits, and this data is used to test the desired property. On success, repeat; on failure, report the counterexample. FuzzChick (right) instead instruments the property being tested (including the system under test (SUT), but not the testing framework itself). Coverage information is used to determine whether the input (a data structure) is interesting or not. In addition, the tool decides between mutating an existing interesting input (if one exists) or generating new inputs randomly to reset the process. Both the mutator and the generator operate at the level of algebraic data types.CC-BY · From the PDF
Fig. 2 QcCrowbar Workflow
Fig. 2 QcCrowbar WorkflowCC-BY · From the PDF
Image 3
CC-BY · From the PDF
Fig. 6 MTTF (in seconds) across different bugs for the register machine
Fig. 6 MTTF (in seconds) across different bugs for the register machineCC-BY · From the PDF

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 47 references

Research works printed but not linked: 14

  1. Thomas H. Austin and Cormac Flanagan. 2009. Efficient purely-dynamic information flow analysis. In Workshop on Programming Languages and Analysis for Security (PLAS) (PLAS). ACM, 113ś124. http://slang.soe.ucsc.edu/cormac/ papers/plas09.pdf
  2. Jasmin Christian Blanchette. 2012. Automatic proofs and refutations for higher-order logic. Ph.D. Dissertation. Technical University Munich. http://nbn-resolving.de/urn:nbn:de:bvb:91-diss-20120628-1097834-1-6
  3. Cristian Cadar, Daniel Dunbar, and Dawson Engler. 2008. KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs. In OSDI.
  4. Jake Corina, Aravind Machiry, Christopher Salls, Yan Shoshitaishvili, Shuang Hao, Christopher Kruegel, and Giovanni Vigna. 2017. DIFUZE: Interface Aware Fuzzing for Kernel Drivers. In ACM SIGSAC Conference on Computer and Communications Security (CCS).
  5. Leonardo De Moura and Nikolaj Bjùrner. 2008. Z3: An Efficient SMT Solver. In Proceedings of the Theory and Prac- tice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'08/ETAPS'08). Springer-Verlag, Berlin, Heidelberg, 337ś340. http://dl.acm.org/citation.cfm?id=1792734.1792766 · doi:10.5555/1792734.1792766
  6. Maxime Dénès, Cătălin Hriţcu, Leonidas Lampropoulos, Zoe Paraskevopoulou, and Benjamin C. Pierce. 2014. QuickChick: Property-based testing for Coq. The Coq Workshop. http://prosecco.gforge.inria.fr/personal/hritcu/talks/coq6_ submission_4.pdf
  7. Patrice Godefroid, Adam Kiezun, and Michael Y. Levin. 2008a. Grammar-based Whitebox Fuzzing. In PLDI.
  8. Leonidas Lampropoulos. 2018. Random Testing for Language Design. Ph.D. Dissertation. University of Pennsylvania.
  9. Rohan Padhye, Caroline Lemieux, Koushik Sen, Mike Papadakis, and Yves Le Traon. 2018. Zest: Validity Fuzzing and Parametric Generators for Effective Random Testing. CoRR abs/1812.00078 (2018). · arXiv
  10. Zoe Paraskevopoulou, Cătălin Hriţcu, Maxime Dénès, Leonidas Lampropoulos, and Benjamin C. Pierce. 2015a. A Coq Framework For Verified Property-Based Testing. Workshop on Coq for PL. https://coqpl.cs.washington.edu/wp- content/uploads/2014/12/quickchick.pdf
  11. Zoe Paraskevopoulou, Cătălin Hriţcu, Maxime Dénès, Leonidas Lampropoulos, and Benjamin C. Pierce. 2015b. Foundational Property-Based Testing. In 6th International Conference on Interactive Theorem Proving (ITP) (Lecture Notes in Computer Science), Christian Urban and Xingyuan Zhang (Eds.), Vol. 9236. Springer, 325ś343. http://prosecco.gforge.inria.fr/ personal/hritcu/publications/foundational-pbt.pdf
  12. Van-Thuan Pham, Marcel Böhme, Andrew E. Santosa, Alexandru Razvan Caciulescu, and Abhik Roychoudhury. 2018. Smart Greybox Fuzzing. CoRR abs/1811.09447 (2018). arXiv:1811.09447 http://arxiv.org/abs/1811.09447 · arXiv
  13. Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. 2017. Vuzzer: Application- aware evolutionary fuzzing. In NDSS.
  14. Stephan A. Zdancewic. 2002. Programming Languages for Information Security. Ph.D. Dissertation. Cornell University. http://www.cis.upenn.edu/~stevez/papers/Zda02.pdf

Cited by

See all 49

Metadata

Authors
Lampropoulos, L., Hicks, M., & Pierce, B. C.
Affiliations
  • University of Pennsylvania (US)
  • University of Maryland, College Park (US)
Venue
Proceedings of the ACM on Programming Languages
Published
2019-10-10
Volume
3
Issue
OOPSLA
Pages
1-29
ISSN
2475-1421 (ISSN-L)
OpenAlex
W2980167976
Cited by
49
References
46
Citations by year
2026: 7 · 2025: 6 · 2024: 10 · 2023: 10 · 2022: 6 · 2021: 7 · 2020: 3
FWCI
9.61
Type
journal article
Language
en
Open access
Locations
Proceedings of the ACM on Programming Languages (publishedVersion, cc-by)
Funders
  • Defense Advanced Research Projects Agency (FA8750-16-C-0022,HR0011-18-C-0011)
  • National Science Foundation (1421243,1521523)
Topics
  • Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
  • Physical Sciences › Computer Science › Software › Logic, programming, and type systems
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
Keywords
property-based testing, fuzzing, input mutation, Coq, abstract machines, non-interference, formal verification

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.