A Survey of Symbolic Execution Techniques
Open accessThe DOI matches its Crossref record; 173 of the 173 references it cites were found in a registry or an index.
Abstract
Many security and software testing applications require checking whether certain properties of a program hold for any possible usage scenario. For instance, a tool for identifying software vulnerabilities may need to rule out the existence of any backdoor to bypass a program’s authentication. One approach would be to test the program using different, possibly random inputs. As the backdoor may only be hit for very specific program workloads, automated exploration of the space of possible inputs is of the essence. Symbolic execution provides an elegant solution to the problem, by systematically exploring many possible execution paths at the same time without necessarily requiring concrete inputs. Rather than taking on fully specified input values, the technique abstractly represents them as symbols, resorting to constraint solvers to construct actual instances that would cause property violations. Symbolic execution has been incubated in dozens of tools developed over the past four decades, leading to major practical breakthroughs in a number of prominent software reliability applications. The goal of this survey is to provide an overview of the main ideas, challenges, and solutions developed in the area, distilling them for a broad audience.
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
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?
The cited source says what the claim attributes to it.
In the citing paper
“Firstly, existing symbolic execution tools are designed for applying symbolic execution to program testing.In particular, they seek to identify the constraints on inputs that result in certain execution paths to aid software quality activities such as software testing or identifying bugs in code [43].”
From Academic Source Code Plagiarism Detection by Measuring Program Behavioral Similarity (2021) · cites this paper as [43]
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
de Moura, L., & Bjørner, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_24 · Cited by 6,595 · cited 2×
“ey make use of symbolic computation techniques only to a little extent, and their support for non-linear real and integer arithmetic is still in its infancy [1]. To the best of our knowledge, only Z3 [36] and SMT-RAT [33] can reason about them both. [1] states that using symbolic computation techniques as theory plugi…”
BackgroundWeiser, M. (1984) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1984.5010248 · Cited by 3,204
Symbolic execution and program testing
King, J. C. (1976) · Communications of the ACM · doi:10.1145/360248.360252 · Cited by 3,031
KLEE: unassisted and automatic generation of high-coverage tests for complex systems programs
Cadar, C., Dunbar, D., & Engler, D. (2008) · doi:10.5555/1855741.1855756 · Cited by 2,620
Efficiently computing static single assignment form and the control dependence graph
Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., & Zadeck, F. K. (1991) · ACM Transactions on Programming Languages and Systems · doi:10.1145/115372.115320 · Cited by 2,267
Valgrind: a framework for heavyweight dynamic binary instrumentation
Nethercote, N., & Seward, J. (2007) · Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1250734.1250746 · Cited by 2,244
QEMU, a fast and portable dynamic translator
Bellard, F. (2005) · USENIX Annual Technical Conference · Cited by 2,207
Separation logic: a logic for shared mutable data structures
Reynolds, J. C. (2003) · Proceedings 17th Annual IEEE Symposium on Logic in Computer Science · doi:10.1109/lics.2002.1029817 · Cited by 2,156
DART: directed automated random testing
Godefroid, P., Klarlund, N., & Sen, K. (2005) · ACM SIGPLAN Notices · doi:10.1145/1064978.1065036 · Cited by 2,067
CUTE: 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
Research works printed but not linked: 10
- 10.5555/1792734.1792771 · doi:10.5555/1792734.1792771
- 10.5555/1763507.1763522 · doi:10.5555/1763507.1763522
- 10.5555/3220903.3221139 · doi:10.5555/3220903.3221139
- 10.5555/3155562.3155638 · doi:10.5555/3155562.3155638
- 10.5555/1792734.1792766 · doi:10.5555/1792734.1792766
- 10.5555/1788994.1789034 · doi:10.5555/1788994.1789034
- 10.5555/1765871.1765924 · doi:10.5555/1765871.1765924
- 10.5555/2041552.2041563 · doi:10.5555/2041552.2041563
- 10.5555/645683.664578 · doi:10.5555/645683.664578
- 10.5555/1987389.1987400 · doi:10.5555/1987389.1987400
Cited by
Survey of machine learning techniques for malware analysis
Ucci, D., Aniello, L., & Baldoni, R. (2019) · Computers & Security · doi:10.1016/j.cose.2018.11.001 · Cited by 569
Self-citationManticore: A User-Friendly Symbolic Execution Framework for Binaries and Smart Contracts
Mossberg, M., Manzano, F., Hennenfent, E., Groce, A., Grieco, G., Feist, J., Brunson, T., & Dinaburg, A. (2019) · 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2019.00133 · Cited by 391
Automated Assessment in Computer Science Education: A State-of-the-Art Review
Paiva, J. C., Leal, J. P., & Figueira, Á. (2022) · ACM Transactions on Computing Education · doi:10.1145/3513140 · Cited by 274
HITS: High-coverage LLM-based Unit Test Generation via Method Slicing
Wang, Z., Liu, K., Li, G., & Jin, Z. G. (2024) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/3691620.3695501 · Cited by 202
HFL: Hybrid Fuzzing on the Linux Kernel
Kim, K., Jeong, D. R., Kim, C. H., Jang, Y., Shin, I., & Lee, B. (2020) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2020.24018 · Cited by 187
Metadata
- Authors
- Baldoni, R., Coppa, E., D’elia, D. C., Demetrescu, C., & Finocchi, I.
- Affiliations
- Sapienza University of Rome (IT)
- Venue
- ACM Computing Surveys
- Published
- 2018-05-23
- Volume
- 51
- Issue
- 3
- Pages
- 1-39
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2528040273
- Cited by
- 708
- References
- 170
- Citations by year
- 2026: 78 · 2025: 100 · 2024: 99 · 2023: 107 · 2022: 79 · 2021: 92 · 2020: 63 · 2019: 55 · 2018: 27
- FWCI
- 155.17
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- ACM Computing Surveys (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- IRIS Research product catalog (Sapienza University of Rome) (submittedVersion, other-oa)
- IRIS - Institutional Research Information System (Libera Università Internazionale degli Studi Sociali Guido Carli) (submittedVersion)
- arXiv (Cornell University)
- Funders
- CINI (Consorzio Interuniversitario Nazionale Informatica) National Laboratory of Cyber Security
- Italian Presidency of the Council of Ministers
- Topics
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Keywords
- symbolic execution, constraint solving, software testing, software vulnerabilities, backdoor detection, input space exploration, software security
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.