CoChat

A Survey of Symbolic Execution Techniques

Open access

The DOI matches its Crossref record; 170 of the 170 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.

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

Integrity signals

Registry

Crossref · 10.1145/3182657

Cites

170 of 170 references verified0 citation errors · 0 not checkable

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.

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

Research works printed but not linked: 12

  1. Erika Abraham , John Abbott , Bernd Becker , Anna M. Bigatti , Martin Brain , Bruno Buchberger , Alessandro Cimatti , James H. Davenport , Matthew England , Pascal Fontaine , Stephen Forrest , Alberto Griggio , Daniel Kroening , Werner M. Seiler , and Thomas Sturm . 2016 . SC2: Satisfiability checking meets symbolic computation . In Proceedings of the 9th International Conference on Intelligent Computer Math. (CICM’16) . Springer, 28--43. Erika Abraham, John Abbott, Bernd Becker, Anna M. Bigatti, Martin Brain, Bruno Buchberger, Alessandro Cimatti, James H. Davenport, Matthew England, Pascal Fontaine, Stephen Forrest, Alberto Griggio, Daniel Kroening, Werner M. Seiler, and Thomas Sturm. 2016. SC2: Satisfiability checking meets symbolic computation. In Proceedings of the 9th International Conference on Intelligent Computer Math. (CICM’16). Springer, 28--43.
  2. 10.5555/1792734.1792771 · doi:10.5555/1792734.1792771
  3. 10.5555/1763507.1763522 · doi:10.5555/1763507.1763522
  4. 10.5555/3220903.3221139 · doi:10.5555/3220903.3221139
  5. 10.5555/3155562.3155638 · doi:10.5555/3155562.3155638
  6. 10.5555/1792734.1792766 · doi:10.5555/1792734.1792766
  7. Johannes Grabmeier , Erich Kaltofen , and Volker Weispfenning . 2003. Computer Algebra Handbook: Foundations , Applications, Systems. Vol. 1 . Springer Science 8 Business Media, 109--124. Johannes Grabmeier, Erich Kaltofen, and Volker Weispfenning. 2003. Computer Algebra Handbook: Foundations, Applications, Systems. Vol. 1. Springer Science 8 Business Media, 109--124.
  8. 10.5555/1788994.1789034 · doi:10.5555/1788994.1789034
  9. 10.5555/1765871.1765924 · doi:10.5555/1765871.1765924
  10. 10.5555/2041552.2041563 · doi:10.5555/2041552.2041563
  11. 10.5555/645683.664578 · doi:10.5555/645683.664578
  12. 10.5555/1987389.1987400 · doi:10.5555/1987389.1987400

Cited by

See all 708

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
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.