The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Heuristics for Scalable Dynamic Test Generation
Abstract
Recently there has been great success in using symbolic execution to automatically generate test inputs for small software systems. A primary challenge in scaling such approaches to larger programs is the combinatorial explosion of the path space. It is likely that sophisticated strategies for searching this path space are needed to generate inputs that effectively test large programs (by, e.g., achieving significant branch coverage). We present several such heuristic search strategies, including a novel strategy guided by the control flow graph of the program under test. We have implemented these strategies in CREST, our open source concolic testing tool for C, and evaluated them on two widely-used software tools, grep 2.2 (15 K lines of code) and Vim 5.7 (150 K lines). On these benchmarks, the presented heuristics achieve significantly greater branch coverage on the same testing budget than concolic testing with a traditional depth-first search strategy.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Symbolic execution and program testing
King, J. C. (1976) · Communications of the ACM · doi:10.1145/360248.360252 · Cited by 3,031
DART: directed automated random testing
Godefroid, P., Klarlund, N., & Sen, K. (2005) · ACM SIGPLAN Notices · doi:10.1145/1064978.1065036 · Cited by 2,067
Self-citationCUTE: a concolic unit testing engine for C
Sen, K., Marinov, D., & Agha, G. (2005) · Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering · doi:10.1145/1081706.1081750 · Cited by 1,651
Self-citationDART: directed automated random testing
Godefroid, P., Klarlund, N., & Sen, K. (2005) · Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation · doi:10.1145/1065010.1065036 · Cited by 1,570
Self-citationAutomated Whitebox Fuzz Testing.
Godefroid, P., Levin, M. Y., & Molnar, D. A. (2008) · Cited by 1,095
QuickCheck: a lightweight tool for random testing of Haskell programs
Claessen, K., & Hughes, J. (2011) · ACM SIGPLAN Notices · doi:10.1145/1988042.1988046 · Cited by 1,011
CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs
Necula, G. C., McPeak, S., Rahul, S. P., & Weimer, W. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45937-5_16 · Cited by 977
EXE: automatically generating inputs of death
Cadar, C., Ganesh, V., Pawlowski, P. M., Dill, D. L., & Engler, D. R. (2006) · Proceedings of the 13th ACM conference on Computer and communications security · doi:10.1145/1180405.1180445 · Cited by 788
A System to Generate Test Data and Symbolically Execute Programs
Clarke, L. A. (1976) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1976.233817 · Cited by 764
A Fast Linear-Arithmetic Solver for DPLL(T)
Dutertre, B., & de Moura, L. (2006) · Lecture notes in computer science · doi:10.1007/11817963_11 · Cited by 679
Test input generation with java PathFinder
Visser, W., Pǎsǎreanu, C. S., & Khurshid, S. (2004) · Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis · doi:10.1145/1007512.1007526 · Cited by 501
Grammar-based whitebox fuzzing
Godefroid, P., Kiezun, A., & Levin, M. Y. (2008) · Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1375581.1375607 · Cited by 462
JCrasher: an automatic robustness tester for Java
Csallner, C., & Smaragdakis, Y. (2004) · Software: Practice and Experience · doi:10.1002/spe.602 · Cited by 426
Majumdar, R., & Sen, K. (2007) · 29th International Conference on Software Engineering (ICSE'07) · doi:10.1109/icse.2007.41 · Cited by 426
Self-citationProbabilistic Verification of Discrete Event Systems Using Acceptance Sampling
Younes, H. L. S., & Simmons, R. G. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45657-0_17 · Cited by 373
CUTE: A Concolic Unit Testing Engine for C
Sen, K., Marinov, D., & Agha, G. (2005) · doi:10.21236/ada482657 · Cited by 300
Self-citationSymstra: A Framework for Generating Object-Oriented Unit Tests Using Symbolic Execution
Xie, T., Marinov, D., Schulte, W., & Notkin, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-31980-1_24 · Cited by 287
Statistical Model Checking of Black-Box Probabilistic Systems
Sen, K., Viswanathan, M., & Agha, G. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27813-9_16 · Cited by 281
Self-citationAn empirical study of the robustness of Windows NT applications using random testing
Forrester, J. E., & Miller, B. P. (2000) · Cited by 271
Eclat: Automatic Generation and Classification of Test Inputs
Pacheco, C., & Ernst, M. D. (2005) · Lecture Notes in Computer Science · doi:10.1007/11531142_22 · Cited by 250
Automatic generation of random self-checking test cases
Bird, D. L., & Munoz, C. U. (1983) · IBM Systems Journal · doi:10.1147/sj.223.0229 · Cited by 222
Generating Tests from Counterexamples
Beyer, D., Chlipala, A. J., Henzinger, T. A., et al. (2004) · Cited by 198
Exploring very large state spaces using genetic algorithms
Godefroid, P., & Sarfraz Khurshid, D. (2004) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-004-0141-1 · Cited by 146
Heuristics for model checking Java programs
Groce, A., & Visser, W. (2004) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-003-0130-9 · Cited by 98
Parallel Randomized State-Space Search
Dwyer, M. B., Elbaum, S. G., Person, S., & Purandare, R. (2007) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1109/icse.2007.62 · Cited by 91
Generating test data for functions with pointer inputs
Visvanathan, S., & Gupta, N. (2002) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2002.1115007 · Cited by 49
Directed test generation using symbolic grammars
Majumdar, R., & Xu, R.-G. (2007) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/1287624.1287708 · Cited by 48
Cited by
Symbolic execution for software testing: three decades later
Cadar, C., & Sen, K. (2013) · Communications of the ACM · doi:10.1145/2408776.2408795 · Cited by 776
Self-citationA survey of symbolic execution techniques
Baldoni, R., Coppa, E., D’elia, D. C., Demetrescu, C., & Finocchi, I. (2019) · ACM Computing Surveys · doi:10.1145/3182657 · Cited by 708
Concolic testing for deep neural networks
Sun, Y., Wu, M., Ruan, W., Huang, X., Kwiatkowska, M., & Kroening, D. (2018) · Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering · doi:10.1145/3238147.3238172 · Cited by 332
Symbolic execution for software testing in practice: preliminary assessment
Cadar, C., Godefroid, P., Khurshid, S., Păsăreanu, C. S., Sen, K., Tillmann, N., & Visser, W. (2011) · Proceedings of the 33rd International Conference on Software Engineering · doi:10.1145/1985793.1985995 · Cited by 325
Self-citationCarFast: achieving higher statement coverage faster
Park, S., Hossain, B. M. M., Hussain, I., Csallner, C., Grechanik, M., Taneja, K., Fu, C., & Xie, Q. (2012) · Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering · doi:10.1145/2393596.2393636 · Cited by 55
Metadata
- Authors
- Burnim, J., & Sen, K.
- Venue
- 2008 23rd IEEE/ACM International Conference on Automated Software Engineering
- Publisher
- IEEE
- Published
- 2008-09
- Pages
- 443-446
- OpenAlex
- W2163499368
- Cited by
- 412
- References
- 27
- FWCI
- 10.97
- Type
- conference paper
- Language
- en
- Open access
- closed
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.