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
Kodkod: A Relational Model Finder
Torlak, E., & Jackson, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-71209-1_49 · Cited by 499
FairFuzz: a targeted mutation strategy for increasing greybox fuzz testing coverage
Lemieux, C., & Sen, K. (2018) · Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering · doi:10.1145/3238147.3238176 · Cited by 477 · cited 1×
“Fairfuzz [Lemieux and Sen 2018] and Vuzzer [Rawat et al. 2017] use static analysis and instrumentation to prioritize rarely covered parts of the program, and they try to mutate parts of an input that drive a program further down rare paths.”
BackgroundCollAFL: Path Sensitive Fuzzing
Gan, S., Zhang, C., Qin, X., Tu, X., Li, K., Pei, Z., & Chen, Z. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00040 · Cited by 370
Learn&Fuzz: Machine learning for input fuzzing
Godefroid, P., Peleg, H., & Singh, R. (2017) · 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2017.8115618 · Cited by 344
QSYM: a practical concolic execution engine tailored for hybrid fuzzing
Yun, I., Lee, S.-H., Xu, M., Jang, Y., & Kim, T. (2018) · USENIX Security Symposium · Cited by 343
Skyfire: Data-Driven Seed Generation for Fuzzing
Wang, J., Chen, B., Wei, L., & Liu, Y. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.23 · Cited by 315
T-Fuzz: Fuzzing by Program Transformation
Peng, H., Shoshitaishvili, Y., & Payer, M. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00056 · Cited by 293
Superion: Grammar-Aware Greybox Fuzzing
Wang, J., Chen, B., Wei, L., & Liu, Y. (2019) · 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE) · doi:10.1109/icse.2019.00081 · Cited by 260
Nitpick: A Counterexample Generator for Higher-Order Logic Based on a Relational Model Finder
Blanchette, J. C., & Nipkow, T. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14052-5_11 · Cited by 240
Flexible dynamic information flow control in Haskell
Stefan, D., Russo, A., Mitchell, J. C., & Mazières, D. (2011) · doi:10.1145/2034675.2034688 · Cited by 163
Test generation through programming in UDITA
Gligoric, M., Gvero, T., Jagannath, V., Khurshid, S., Kuncak, V., & Marinov, D. (2010) · Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1 · doi:10.1145/1806799.1806835 · Cited by 160
CertiKOS: an extensible architecture for building certified concurrent OS kernels
Gu, R., Shao, Z., Chen, H., Wu, X., Kim, J., Sjöberg, V., & Costanzo, D. (2016) · Operating Systems Design and Implementation · doi:10.5555/3026877.3026928 · Cited by 160
Hails: Protecting data privacy in untrusted web applications
Giffin, D. B., Levy, A. A., Stefan, D., Terei, D. A., Mazières, D., Mitchell, J. C., & Russo, A. (2017) · Journal of Computer Security · doi:10.3233/jcs-15801 · Cited by 142
Synthesizing program input grammars
Bastani, O., Sharma, R., Aiken, A., & Liang, P. (2017) · Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3062341.3062349 · Cited by 131
A PropEr integration of types and function specifications with property-based testing
Papadakis, M., & Sagonas, K. (2011) · ACM SIGPLAN Workshop on Erlang (Erlang) · doi:10.1145/2034654.2034663 · Cited by 102
All Your IFCException Are Belong to Us
Hriţcu, C., Greenberg, M., Karel, B., Pierce, B. C., & Morrisett, G. (2013) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2013.10 · Cited by 73
Self-citationThe New Quickcheck for Isabelle
Bulwahn, L. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-35308-6_10 · Cited by 67
Beginner's luck: a language for property-based generators
Lampropoulos, L., Gallois-Wong, D., Hriţcu, C., Hughes, J., Pierce, B. C., & Xia, L.-Y. (2017) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/3009837.3009868 · Cited by 64
Self-citationStefan, D., Russo, A., Mazières, D., & Mitchell, J. C. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29615-4_16 · Cited by 58
A verified information-flow architecture
de Amorim, A. A., Collins, N. S., DeHon, A. M., Demange, D., Hriţcu, C., Pichardie, D., Pierce, B. C., Pollack, R., & Tolmach, A. P. (2014) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/2535838.2535839 · Cited by 58
Self-citationSeidel, E. L., Vazou, N., & Jhala, R. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46669-8_33 · Cited by 49
Testing noninterference, quickly
Hriţcu, C., Hughes, J., Pierce, B. C., Spector-Zabusky, A., Vytiniotis, D., de Amorim, A. A., & Lampropoulos, L. (2013) · ACM SIGPLAN International Conference on Functional Programming (ICFP) · doi:10.1145/2500365.2500574 · Cited by 48
Self-citationJain, V., Rawat, S., Giuffrida, C., & Bos, H. (2018) · Annual Computer Security Applications Conference · doi:10.1145/3274694.3274746 · Cited by 46
Generating good generators for inductive relations
Lampropoulos, L., Paraskevopoulou, Z., & Pierce, B. C. (2018) · Proceedings of the ACM on Programming Languages · doi:10.1145/3158133 · Cited by 44
Self-citationFetscher, B., Claessen, K., Pałka, M. H., Hughes, J., & Findler, R. B. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46669-8_16 · Cited by 41
Smart Testing of Functional Programs in Isabelle
Bulwahn, L. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28717-6_14 · Cited by 34
Generating Constrained Random Data with Uniform Distribution
Claessen, K., Duregård, J., & Pałka, M. H. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07151-0_2 · Cited by 34
A Theory of Information-Flow Labels
Montagu, B., Pierce, B. C., & Pollack, R. (2013) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf.2013.8 · Cited by 33
Self-citationStatic Program Analysis as a Fuzzing Aid
Shastry, B., Leutner, M., Fiebig, T., Thimmaraju, K., Yamaguchi, F., Rieck, K., Schmid, S., Seifert, J., & Feldmann, A. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-66332-6_2 · Cited by 31
Splittable pseudorandom number generators using cryptographic hashing
Claessen, K., & Pałka, M. H. (2013) · International Symposium on Haskell · doi:10.1145/2503778.2503784 · Cited by 30
Testing noninterference, quickly
Hriţcu, C., LAMPROPOULOS, L., SPECTOR-ZABUSKY, A., AMORIM, A. A. D., DÉNÈS, M., HUGHES, J., Pierce, B. C., & Vytiniotis, D. (2016) · Journal of Functional Programming · doi:10.1017/s0956796816000058 · Cited by 30
Self-citationQuickFuzz: an automatic random fuzzer for common file formats
Grieco, G., Ceresa, M., & Buiras, P. (2016) · doi:10.1145/2976002.2976017 · Cited by 29
Bounded Model Generation for Isabelle/HOL
Weber, T. (2005) · Electronic Notes in Theoretical Computer Science · doi:10.1016/j.entcs.2004.10.027 · Cited by 22
QuickFuzz testing for fun and profit
Grieco, G., Ceresa, M., Mista, A., & Buiras, P. (2017) · Journal of Systems and Software · doi:10.1016/j.jss.2017.09.018 · Cited by 21
SAFE: A clean-slate architecture for secure systems
Chiricescu, S. M. S. A., DeHon, A. M., Demange, D., Iyer, S. V., Kliger, A., Morrisett, G., Pierce, B. C., Reubenstein, H. B., Smith, J. M., Sullivan, G. T., et al. (2013) · IEEE Conference on Technologies for Homeland Security (HST) · doi:10.1109/ths.2013.6699066 · Cited by 19
Self-citationExtending Nunchaku to Dependent Type Theory
Cruanes, S., & Blanchette, J. C. (2016) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.210.3 · Cited by 8
Superion: Grammar-Aware Greybox FuzzingPreprint
Wang, J., Chen, B., Wei, L., et al. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.01197 · Cited by 8
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.