Coverage guided, property based testing
Open accessThe 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.
Integrity signals
Registry
Cites
Statistics
Figures




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.
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?
In the citing paper
“Traditional mutations (e.g., changing random code elements) do not work in generating valid DL programs since they can easily cause runtime errors by incorrectly mutating the input and argument space, and also cannot easily ensure the semantic validity [38,55] of the generated programs due to the dynamically typed language.”
From Large Language Models Are Zero-Shot Fuzzers: Fuzzing Deep-Learning Libraries via Large Language Models (2023) · cites this paper as [38]
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
Security Policies and Security Models
Goguen, J. A., & Meseguer, J. (1982) · 1982 IEEE Symposium on Security and Privacy · doi:10.1109/sp.1982.10014 · Cited by 2,119
Language-based information-flow security
Sabelfeld, A., & Myers, A. C. (2003) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2002.806121 · Cited by 1,907 · cited 2×
“Machine states S 1 = pc 1 s 1 m 1 i 1 and S 2 = pc 2 s 2 m 2 i 2 are indistinguishable if their corresponding components are indistinguishable: The particular variant of noninterference we are interested in is termination-insensitive nonin-terference [Sabelfeld and Myers 2003].”
BackgroundMethodAn empirical study of the reliability of UNIX utilities
Miller, B. P., Fredriksen, L., & So, B. (1990) · Communications of the ACM · doi:10.1145/96267.96279 · Cited by 1,281
Formal verification of a realistic compiler
Leroy, X. (2009) · Communications of the ACM · doi:10.1145/1538788.1538814 · Cited by 1,187
Automated Whitebox Fuzz Testing.
Godefroid, P., Levin, M. Y., & Molnar, D. A. (2008) · Cited by 1,095
Driller: Augmenting Fuzzing Through Selective Symbolic Execution
Stephens, N., Grosen, J., Salls, C., Dutcher, A., Wang, R., Corbetta, J., Shoshitaishvili, Y., Kruegel, C., & Vigna, G. (2016) · Proceedings 2016 Network and Distributed System Security Symposium · doi:10.14722/ndss.2016.23368 · Cited by 887
(2000) · doi:10.1145/351240.351266 · Cited by 753
Coverage-based Greybox Fuzzing as Markov Chain
Böhme, M., Pham, V.-T., & Roychoudhury, A. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978428 · Cited by 649
Klees, G., Ruef, A., Cooper, B., Wei, S., & Hicks, M. (2018) · Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3243734.3243804 · Cited by 633
Self-citationAngora: Efficient Fuzzing by Principled Search
Chen, P., & Chen, H. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00046 · Cited by 552
Research works printed but not linked: 14
- 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
- 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
- Cristian Cadar, Daniel Dunbar, and Dawson Engler. 2008. KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs. In OSDI.
- 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).
- 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
- 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
- Patrice Godefroid, Adam Kiezun, and Michael Y. Levin. 2008a. Grammar-based Whitebox Fuzzing. In PLDI.
- Leonidas Lampropoulos. 2018. Random Testing for Language Design. Ph.D. Dissertation. University of Pennsylvania.
- 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
- 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
- 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
- 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
- Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. 2017. Vuzzer: Application- aware evolutionary fuzzing. In NDSS.
- 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
Deng, Y., Xia, C. S., Peng, H., Yang, C., & Zhang, L. (2023) · Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis · doi:10.1145/3597926.3598067 · Cited by 326
“…(e.g., changing random code elements) do not work in generating valid DL programs since they can easily cause runtime errors by incorrectly mutating the input and argument space, and also cannot easily ensure the semantic validity [38, 55] of the generated programs due to the dynamically language.”
BackgroundOn the unusual effectiveness of type-aware operator mutations for testing SMT solvers
Winterer, D., Zhang, C., & Su, Z. (2020) · Proceedings of the ACM on Programming Languages · doi:10.1145/3428261 · Cited by 85
Coverage-guided tensor compiler fuzzing with joint IR-pass mutation
Liu, J., Wei, Y., Yang, S., Deng, Y., & Zhang, L. (2022) · Proceedings of the ACM on Programming Languages · doi:10.1145/3527317 · Cited by 51
Property-Based Testing in Practice
Goldstein, H., Cutler, J. W., Dickstein, D., Pierce, B. C., & Head, A. (2024) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/3597503.3639581 · Cited by 86
Self-citationGenerative type-aware mutation for testing SMT solvers
Park, J., Winterer, D., Zhang, C., & Su, Z. (2021) · Proceedings of the ACM on Programming Languages · doi:10.1145/3485529 · Cited by 51
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
- diamond
- doi.org
- Licence
- 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.