A Survey of Symbolic Execution Techniques
Open accessThe 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.
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
DART: 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
On the synthesis of a reactive module
Pnueli, A., & Rosner, R. (1989) · Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 · doi:10.1145/75277.75293 · Cited by 1,432
Search‐based software test data generation: a survey
McMinn, P. (2004) · Software Testing, Verification and Reliability · doi:10.1002/stvr.294 · Cited by 1,368
Automated Whitebox Fuzz Testing.
Godefroid, P., Levin, M. Y., & Molnar, D. A. (2008) · Cited by 1,095
SOK: (State of) The Art of War: Offensive Techniques in Binary Analysis
Shoshitaishvili, Y., Wang, R., Salls, C., Stephens, N., Polino, M., Dutcher, A., Grosen, J., Feng, S., Hauser, C., Kruegel, C., et al. (2016) · 2016 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2016.17 · Cited by 957
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
Compiler transformations for high-performance computing
Bacon, D. F., Graham, S. L., & Sharp, O. J. (1994) · ACM Computing Surveys · doi:10.1145/197405.197406 · Cited by 818
Pex–White Box Test Generation for .NET
Tillmann, N., & de Halleux, J. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79124-9_10 · Cited by 791
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
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
BitBlaze: A New Approach to Computer Security via Binary Analysis
Song, D., Brumley, D., Yin, H., Caballero, J., Jager, I., Kang, M. G., Liang, Z., Newsome, J., Poosankam, P., & Saxena, P. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-89862-7_1 · Cited by 718
Schwartz, E. J., Avgerinos, T., & Brumley, D. (2010) · 2010 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2010.26 · Cited by 717
Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory
Craig, W. (1957) · Journal of Symbolic Logic · doi:10.2307/2963594 · Cited by 667
RacerX: effective, static detection of race conditions and deadlocks
Engler, D., & Ashcraft, K. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945468 · Cited by 661
Satisfiability modulo theories: introduction and applications
De Moura, L., & Bjørner, N. (2011) · Communications of the ACM · doi:10.1145/1995376.1995394 · Cited by 645
A Decision Procedure for Bit-Vectors and Arrays
Ganesh, V., & Dill, D. L. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-73368-3_52 · Cited by 585
Generalized Symbolic Execution for Model Checking and Testing
Khurshid, S., PĂsĂreanu, C. S., & Visser, W. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36577-x_40 · Cited by 568
SAGE: whitebox fuzzing for security testing
Godefroid, P., Levin, M. Y., & Molnar, D. (2012) · Communications of the ACM · doi:10.1145/2093548.2093564 · Cited by 567
Unleashing Mayhem on Binary Code
Cha, S. K., Avgerinos, T., Rebert, A., & Brumley, D. (2012) · 2012 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2012.31 · Cited by 518
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
BAP: A Binary Analysis Platform
Brumley, D., Jager, I., Avgerinos, T., & Schwartz, E. J. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22110-1_37 · Cited by 433
Majumdar, R., & Sen, K. (2007) · 29th International Conference on Software Engineering (ICSE'07) · doi:10.1109/icse.2007.41 · Cited by 426
Heuristics for Scalable Dynamic Test Generation
Burnim, J., & Sen, K. (2008) · 2008 23rd IEEE/ACM International Conference on Automated Software Engineering · doi:10.1109/ase.2008.69 · Cited by 412
Compositional dynamic test generation
Godefroid, P. (2007) · ACM SIGPLAN Notices · doi:10.1145/1190215.1190226 · Cited by 408
SELECT—a formal system for testing and debugging programs by symbolic execution
Boyer, R. S., Elspas, B., & Levitt, K. N. (1975) · ACM SIGPLAN Notices · doi:10.1145/390016.808445 · Cited by 390
CUTE and jCUTE: Concolic Unit Testing and Explicit Path Model-Checking Tools
Sen, K., & Agha, G. (2006) · Lecture Notes in Computer Science · doi:10.1007/11817963_38 · Cited by 389
Analyzing Memory Accesses in x86 Executables
Balakrishnan, G., & Reps, T. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24723-4_2 · Cited by 379
Thorough static analysis of device drivers
Ball, T., Bounimova, E., Cook, B., Levin, V., Lichtenberg, J., McGarvey, C., Ondrusek, B., Rajamani, S. K., & Ustuner, A. (2006) · Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006 · doi:10.1145/1217935.1217943 · Cited by 371
RacerX: effective, static detection of race conditions and deadlocks
Engler, D., & Ashcraft, K. (2003) · Proceedings of the nineteenth ACM symposium on Operating systems principles · doi:10.1145/945445.945468 · Cited by 368
Firmalice - Automatic Detection of Authentication Bypass Vulnerabilities in Binary Firmware
Shoshitaishvili, Y., Wang, R., Hauser, C., Kruegel, C., & Vigna, G. (2015) · Proceedings 2015 Network and Distributed System Security Symposium · doi:10.14722/ndss.2015.23294 · Cited by 362
A Large-Scale Analysis of the Security of Embedded Firmwares
Costin, A., Zaddach, J., Francillon, A., & Balzarotti, D. (2014) · HAL · Cited by 347
SAGE: Whitebox Fuzzing for Security Testing: SAGE has had a remarkable impact at Microsoft.
Godefroid, P., Levin, M. Y., & Molnar, D. (2012) · Queue · doi:10.1145/2090147.2094081 · Cited by 328
Avatar: A Framework to Support Dynamic Security Analysis of Embedded Systems’ Firmwares
Zaddach, J., Bruno, L., Francillon, A., & Balzarotti, D. (2014) · Proceedings 2014 Network and Distributed System Security Symposium · doi:10.14722/ndss.2014.23229 · Cited by 327
Program synthesis by sketching
Bodík, R., & Solar-Lezama, A. (2008) · Cited by 326
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
Termination proofs for systems code
Cook, B., Podelski, A., & Rybalchenko, A. (2006) · ACM SIGPLAN Notices · doi:10.1145/1133255.1134029 · Cited by 317
Compositional dynamic test generation
Godefroid, P. (2007) · Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1190216.1190226 · Cited by 314
Predicate abstraction for software verification
Flanagan, C., & Qadeer, S. (2002) · Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/503272.503291 · Cited by 284
Jalangi: a selective record-replay and dynamic analysis framework for JavaScript
Sen, K., Kalasapur, S., Brutch, T., & Gibbs, S. (2013) · Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering · doi:10.1145/2491411.2491447 · Cited by 270
Effective lattice point counting in rational convex polytopes
De Loera, J. A., Hemmecke, R., Tauzer, J., & Yoshida, R. (2004) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2003.04.003 · Cited by 261
Symbolic PathFinder: symbolic execution of Java bytecode
Păsăreanu, C. S., & Rungta, N. (2010) · Proceedings of the IEEE/ACM international conference on Automated software engineering · doi:10.1145/1858996.1859035 · Cited by 259
Symbolic Testing and the DISSECT Symbolic Evaluation System
Howden, W. E. (1977) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1977.231144 · Cited by 251
Termination proofs for systems code
Cook, B., Podelski, A., & Rybalchenko, A. (2006) · Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1133981.1134029 · Cited by 240
Fitness-guided path exploration in dynamic symbolic execution
Xie, T., Tillmann, N., de Halleux, J., & Schulte, W. (2009) · 2009 IEEE/IFIP International Conference on Dependable Systems & Networks · doi:10.1109/dsn.2009.5270315 · Cited by 238
Parallel symbolic execution for automated real-world software testing
Bucur, S., Ureche, V., Zamfir, C., & Candea, G. (2011) · Proceedings of the sixth conference on Computer systems · doi:10.1145/1966445.1966463 · Cited by 236
RWset: Attacking Path Explosion in Constraint-Based Test Generation
Boonstoppel, P., Cadar, C., & Engler, D. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_27 · Cited by 234
Impeding Malware Analysis Using Conditional Code Obfuscation
Sharif, M. I., Lanzi, A., Giffin, J. T., & Lee, W. (2008) · Cited by 231
A survey of new trends in symbolic execution for software testing and analysis
Păsăreanu, C. S., & Visser, W. (2009) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-009-0118-1 · Cited by 231
Check 'n' crash: combining static checking and testing
Csallner, C., & Smaragdakis, Y. (2005) · Proceedings of the 27th international conference on Software engineering - ICSE '05 · doi:10.1145/1062455.1062533 · Cited by 220
Enhancing symbolic execution with veritesting
Avgerinos, T., Rebert, A., Cha, S. K., & Brumley, D. (2014) · Proceedings of the 36th International Conference on Software Engineering · doi:10.1145/2568225.2568293 · Cited by 218
Demand-Driven Compositional Symbolic Execution
Anand, S., Godefroid, P., & Tillmann, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_28 · Cited by 217
Scalable error detection using boolean satisfiability
Xie, Y., & Aiken, A. (2005) · Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1040305.1040334 · Cited by 213
Compositional Shape Analysis by Means of Bi-Abduction
Calcagno, C., Distefano, D., O’Hearn, P. W., & Yang, H. (2011) · Journal of the ACM · doi:10.1145/2049697.2049700 · Cited by 212
Ma, K.-K., Yit Phang, K., Foster, J. S., & Hicks, M. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-23702-7_11 · Cited by 209
The S2E Platform: Design, Implementation, and Applications
Chipounov, V., Kuznetsov, V., & Candea, G. (2012) · ACM Transactions on Computer Systems · doi:10.1145/2110356.2110358 · Cited by 206
AEG: Automatic Exploit Generation
(2018) · doi:10.1184/r1/6468296.v1 · Cited by 205
Deobfuscation: Reverse Engineering Obfuscated Code
Udupa, S. K., Debray, S. K., & Madou, M. (2006) · 12th Working Conference on Reverse Engineering (WCRE'05) · doi:10.1109/wcre.2005.13 · Cited by 204
AEG: Automatic Exploit Generation
Avgerinos, T., Kil, S., Hao, B. L. T., & Brumley, D. (2018) · doi:10.1184/r1/6468296 · Cited by 202
A Generic Approach to Automatic Deobfuscation of Executable Code
Yadegari, B., Johannesmeyer, B., Whitely, B., & Debray, S. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.47 · Cited by 195
Z3-str: a z3-based string solver for web application analysis
Zheng, Y., Zhang, X., & Ganesh, V. (2013) · Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering · doi:10.1145/2491411.2491456 · Cited by 194
A new approach to program testing
King, J. C. (1975) · ACM SIGPLAN Notices · doi:10.1145/390016.808444 · Cited by 194
Efficient state merging in symbolic execution
Kuznetsov, V., Kinder, J., Bucur, S., & Candea, G. (2012) · Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2254064.2254088 · Cited by 193
Q: Exploit Hardening Made Easy
Schwartz, E. J., Avgerinos, T., & Brumley, D. (2018) · doi:10.1184/r1/6469187 · Cited by 178
Test input generation for java containers using state matching
Visser, W., Pǎsǎreanu, C. S., & Pelánek, R. (2006) · Proceedings of the 2006 international symposium on Software testing and analysis · doi:10.1145/1146238.1146243 · Cited by 168
SELECT---a formal system for testing and debugging programs by symbolic execution
Boyer, R. S., Elspas, B., & Levitt, K. N. (1975) · Proceedings of the international conference on Reliable software - · doi:10.1145/800027.808445 · Cited by 166
Loop-extended symbolic execution on binary programs
Saxena, P., Poosankam, P., McCamant, S., & Song, D. (2009) · Proceedings of the eighteenth international symposium on Software testing and analysis · doi:10.1145/1572272.1572299 · Cited by 163
Green: reducing, reusing and recycling constraints in program analysis
Visser, W., Geldenhuys, J., & Dwyer, M. B. (2012) · Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering · doi:10.1145/2393596.2393665 · Cited by 161
Probabilistic symbolic execution
Geldenhuys, J., Dwyer, M. B., & Visser, W. (2012) · International Symposium on Software Testing and Analysis · doi:10.1145/2338965.2336773 · Cited by 149
Calysto: scalable and precise extended static checking
Babić, D., & Hu, A. J. (2008) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/1368088.1368118 · Cited by 148
FIE on firmware: finding vulnerabilities in embedded systems using symbolic execution
Davidson, D., Moench, B., Jha, S., & Ristenpart, T. (2013) · USENIX Security Symposium · Cited by 147
A Static Analysis Framework For Detecting SQL Injection Vulnerabilities
Fu, X., Lu, X. Z., Peltsverger, B., et al. (2007) · Proceedings - International Computer Software & Applications Conference · doi:10.1109/compsac.2007.43 · Cited by 146
Under-Constrained Symbolic Execution: Correctness Checking for Real Code
Ramos, D. A., & Engler, D. (2015) · USENIX Security Symposium · Cited by 145
Chandra, S., Fink, S. J., & Sridharan, M. (2009) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1542476.1542517 · Cited by 123
Automating Separation Logic Using SMT
Piskač, R., Wies, T., & Damien Zufferey, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39799-8_54 · Cited by 120
Automatic partial loop summarization in dynamic test generation
Godefroid, P., & Luchaup, D. (2011) · International Symposium on Software Testing and Analysis · doi:10.1145/2001420.2001424 · Cited by 120
Lazy Annotation for Program Testing and Verification
McMillan, K. L. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14295-6_10 · Cited by 119
Yang, G., Păsăreanu, C. S., & Khurshid, S. (2012) · International Symposium on Software Testing and Analysis · doi:10.1145/2338965.2336771 · Cited by 112
A new approach to program testing
King, J. C. (1975) · doi:10.1145/800027.808444 · Cited by 104
ATGen: automatic test data generation using constraint logic programming and symbolic execution†
Meudec, C. (2001) · Software Testing Verification and Reliability · doi:10.1002/stvr.225 · Cited by 101
SymJS: automatic symbolic testing of JavaScript web applications
Li, G., Andreasen, E., & Ghosh, I. (2014) · ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE) · doi:10.1145/2635868.2635913 · Cited by 100
Symbolic execution with mixed concrete-symbolic solving
Păsăreanu, C. S., Rungta, N., & Visser, W. (2011) · International Symposium on Software Testing and Analysis · doi:10.1145/2001420.2001425 · Cited by 96
Multi-run Side-Channel Analysis Using Symbolic Execution and Max-SMT
Păsăreanu, C. S., Phan, Q.-S., & Malacaria, P. (2016) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf.2016.34 · Cited by 96
Steering symbolic execution to less traveled paths
Li, Y., Su, Z., Wang, L., & Li, X. (2013) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2509136.2509553 · Cited by 94
TRACER: A Symbolic Execution Tool for Verification
Jaffar, J., Murali, V., Navas, J. A., et al. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31424-7_61 · Cited by 91
Symbolic Execution of Obfuscated Code
Yadegari, B., & Debray, S. (2015) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2810103.2813663 · Cited by 87
Multics security evaluation: vulnerability analysis
Karger, P. A., & Schell, R. R. (2003) · Annual Computer Security Applications Conference · doi:10.1109/csac.2002.1176286 · Cited by 84
State of the art: Dynamic symbolic execution for automated test generation
Chen, T., Zhang, X., Guo, S., Li, H., & Wu, Y. (2012) · Future Generation Computer Systems · doi:10.1016/j.future.2012.02.006 · Cited by 83
FloPSy - Search-Based Floating Point Constraint Solving for Symbolic Execution
Lakhotia, K., Tillmann, N., Harman, M., & de Halleux, J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16573-3_11 · Cited by 82
Symbolic crosschecking of floating-point and SIMD code
Collingbourne, P., Cadar, C., & Kelly, P. H. J. (2011) · doi:10.1145/1966445.1966475 · Cited by 81
Model checking Java programs using structural heuristics
Groce, A., & Visser, W. (2002) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/566171.566175 · Cited by 81
JDart: A Dynamic Symbolic Analysis Framework
Luckow, K. S., Dimjašević, M., Giannakopoulou, D., Howar, F. M., Isberner, M., Kahsai, T., Rakamarić, Z., & Raman, V. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49674-9_26 · Cited by 79
Loop invariants: Analysis, classification, and examples
Furia, C. A., Meyer, B., & Эдуардович, В. С. (2014) · ACM Computing Surveys · doi:10.1145/2506375 · Cited by 79
SMT-RAT: An Open Source C++ Toolbox for Strategic and Parallel SMT Solving
Corzilius, F., Kremer, G., Junges, S., Schupp, S., & Ábrahám, E. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-24318-4_26 · Cited by 78
Precise identification of problems for structural test generation
Xiao, X., Xie, T., Tillmann, N., & de Halleux, J. (2011) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/1985793.1985876 · Cited by 75
Symbolic security analysis of ruby-on-rails web applications
Chaudhuri, A., & Foster, J. S. (2010) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/1866307.1866373 · Cited by 72
Precise pointer reasoning for dynamic test generation
Elkarablieh, B., Godefroid, P., & Levin, M. Y. (2009) · ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) · doi:10.1145/1572272.1572288 · Cited by 72
A Race-Detection and Flipping Algorithm for Automated Testing of Multi-threaded Programs
Sen, K., & Agha, G. (2007) · Springer eBooks · doi:10.1007/978-3-540-70889-6_13 · Cited by 71
CORAL: Solving Complex Constraints for Symbolic PathFinder
Souza, M., Borges, M., d’Amorim, M., et al. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20398-5_26 · Cited by 70
Symbolic execution with abstraction
Anand, S., Păsăreanu, C. S., & Visser, W. (2008) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-008-0090-1 · Cited by 69
Linear Obfuscation to Combat Symbolic Execution
Wang, Z., Ming, J., Jia, C., et al. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23822-2_12 · Cited by 66
Engler, D., & Dunbar, D. (2007) · International Symposium on Software Testing and Analysis · doi:10.1145/1273463.1273464 · Cited by 65
Enhancing reuse of constraint solutions to improve symbolic execution
Jia, X., Ghezzi, C., & Ying, S. (2015) · International Symposium on Software Testing and Analysis · doi:10.1145/2771783.2771806 · Cited by 64
Farzan, A., Holzer, A., Razavi, N., et al. (2013) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/2491411.2491453 · Cited by 64
State Joining and Splitting for the Symbolic Execution of Binaries
Hansen, T., Schachte, P., & Søndergaard, H. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04694-0_6 · Cited by 63
Directed Proof Generation for Machine Code
Thakur, A., Lim, J., Lal, A., et al. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14295-6_27 · Cited by 61
Interpolation-Based Function Summaries in Bounded Model Checking
Šerý, O., Fedyukovich, G., & Sharygina, N. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34188-5_15 · Cited by 60
Proteus: computing disjunctive loop summary via path dependency analysis
Xie, X., Chen, B., Liu, Y., Le, W., & Li, X. (2016) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/2950290.2950340 · Cited by 59
Assertion guided symbolic execution of multithreaded programs
Guo, S., Kusano, M., Wang, C., Yang, Z., & Gupta, A. (2015) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/2786805.2786841 · Cited by 58
Boosting concolic testing via interpolation
Jaffar, J., Murali, V., & Navas, J. A. (2013) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/2491411.2491425 · Cited by 57
Abstracting Symbolic Execution with String Analysis
Shannon, D., Hajra, S., Lee, A., et al. (2007) · doi:10.1109/taic.part.2007.34 · Cited by 55
Generating performance distributions via probabilistic symbolic execution
Chen, B., Liu, Y., & Le, W. (2016) · Proceedings/Proceedings - International Conference on Software Engineering · doi:10.1145/2884781.2884794 · Cited by 55
Loop Summarization Using Abstract Transformers
Kroening, D., Sharygina, N., Tonetta, S., Tsitovich, A., & Wintersteiger, C. M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88387-6_10 · Cited by 54
An Interpolation Method for CLP Traversal
Jaffar, J., Santosa, A. E., & Voicu, R. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04244-7_37 · Cited by 54
SymDroid: Symbolic Execution for Dalvik Bytecode
Jeon, J., Micinski, K., & Foster, J. S. (2012) · University Libraries (University of Maryland) · Cited by 53
Symbolic Execution with Abstract Subsumption Checking
Anand, S., Păsăreanu, C. S., & Visser, W. (2006) · Lecture notes in computer science · doi:10.1007/11691617_10 · Cited by 51
Accelerating array constraints in symbolic execution
Perry, D. M., Mattavelli, A., Zhang, X., et al. (2017) · ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) · doi:10.1145/3092703.3092728 · Cited by 49
Targeted test input generation using symbolic-concrete backward execution
Dinges, P., & Agha, G. (2014) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/2642937.2642951 · Cited by 48
Loop Summarization and Termination Analysis
Tsitovich, A., Sharygina, N., Wintersteiger, C. M., & Kroening, D. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19835-9_9 · Cited by 46
Reducing Test Inputs Using Information Partitions
Majumdar, R., & Xu, R.-G. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02658-4_41 · Cited by 45
Dependence Guided Symbolic Execution
Wang, H., Liu, T., Guan, X., Shen, C. Q., Zheng, Q., & Yang, Z. (2016) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2016.2584063 · Cited by 45
Incremental upgrade checking by means of interpolation-based function summaries
Šerý, O., Fedyukovich, G., & Sharygina, N. (2012) · Cited by 43
Directed Incremental Symbolic Execution
Yang, G., Person, S., Rungta, N., et al. (2014) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/2629536 · Cited by 43
Synthesizing framework models for symbolic execution
Jeon, J., Qiu, X., Fetter-Degges, J., Foster, J. S., & Solar-Lezama, A. (2016) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/2884781.2884856 · Cited by 43
Deconstructing Dynamic Symbolic Execution
Thomas, B., & Jakub, D. (2015) · NATO science for peace and security series. D, Information and communication security · doi:10.3233/978-1-61499-495-4-26 · Cited by 43
Qi, D., Roychoudhury, A., Liang, Z., & Vaswani, K. (2012) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/2211616.2211622 · Cited by 42
Unbounded Symbolic Execution for Program Verification
Jaffar, J., Navas, J. A., & Santosa, A. E. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29860-8_32 · Cited by 41
HI-CFG: Construction by Binary Analysis and Application to Attack Polymorphism
Caselden, D., Bazhanyuk, A., Payer, M., et al. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40203-6_10 · Cited by 40
Building Bridges between Symbolic Computation and Satisfiability Checking
Ábrahám, E. (2015) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/2755996.2756636 · Cited by 39
BLISS: Improved Symbolic Execution by\\ Bounded Lazy Initialization with SAT Support
Rosner, N., Geldenhuys, J., Aguirre, N., et al. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2015.2389225 · Cited by 36
Solving complex path conditions through heuristic search on induced polytopes
Dinges, P., & Agha, G. (2014) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/2635868.2635889 · Cited by 35
Regular property guided dynamic symbolic execution
Zhang, Y., Chen, Z., Wang, J., et al. (2015) · doi:10.5555/2818754.2818833 · Cited by 32
Symbolic execution of multithreaded programs from arbitrary program contexts
Bergan, T., Grossman, D., & Ceze, L. (2014) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2660193.2660200 · Cited by 31
Separation Logic Verification of C Programs with an SMT Solver
Botinčan, M., Parkinson, M., & Schulte, W. (2009) · Electronic Notes in Theoretical Computer Science · doi:10.1016/j.entcs.2009.09.057 · Cited by 31
Inferring Loop Invariants by Mutation, Dynamic Analysis, and Static Checking
Galeotti, J. P., Furia, C. A., May, E., et al. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2015.2431688 · Cited by 31
Postconditioned Symbolic Execution
Yi, Q., Yang, Z., Guo, S., et al. (2015) · IEEE International Conference on Software Testing, Verification and Validation (ICST) · doi:10.1109/icst.2015.7102601 · Cited by 30
Targeted program transformations for symbolic execution
Cadar, C. (2015) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/2786805.2803205 · Cited by 30
TRACER: A symbolic execution tool for verification
Jaffar, J., Murali, V., Navas, J., et al. (2012) · Cited by 29
Type-Dependence Analysis and Program Transformation for Symbolic Execution
Anand, S., Orso, A., & Harrold, M. J. (2007) · Springer eBooks · doi:10.1007/978-3-540-71209-1_11 · Cited by 28
Efficient and formal generalized symbolic execution
Deng, X., Lee, J., & Robby (2011) · Automated Software Engineering · doi:10.1007/s10515-011-0089-9 · Cited by 27
Geldenhuys, J., Aguirre, N., Frias, M. F., et al. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38088-4_16 · Cited by 27
Overify: optimizing programs for fast verification
Wagner, J., Kuznetsov, V., & Candea, G. (2013) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 25
Studying the influence of standard compiler optimizations on symbolic execution
Dong, S., Olivo, O., Zhang, L., et al. (2015) · IEEE International Symposium on Software Reliability Engineering (ISSRE) · doi:10.1109/issre.2015.7381814 · Cited by 25
Decision procedures for bit-vectors, arrays and integers
Dill, D. L., & Ganesh, V. (2007) · Cited by 23
Path exploration based on symbolic output
Qi, D., Nguyen, H. D. T., & Roychoudhury, A. (2013) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/2522920.2522925 · Cited by 23
Obfuscation Code Localization Based on CFG Generation of Malware
Hải, N. M., Ogawa, M., & Quan, T. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-30303-1_14 · Cited by 20
Rethinking pointer reasoning in symbolic execution
Coppa, E., D’Elia, D. C., & Demetrescu, C. (2017) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2017.8115671 · Cited by 20
Self-citationMixing type checking and symbolic execution
Khoo, Y. P., Chang, B.-Y. E., & Foster, J. S. (2010) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1806596.1806645 · Cited by 19
Symbolic Execution Debugger (SED)
Hentschel, M., Bubel, R., & Hähnle, R. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11164-3_21 · Cited by 17
Synthesis of ranking functions using extremal counterexamples
Gonnord, L., Monniaux, D. P., & Radanne, G. (2015) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2737924.2737976 · Cited by 17
Generation of Library Models for Verification of Android Applications
van der Merwe, H., Tkachuk, O., van der Merwe, B., et al. (2015) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/2693208.2693247 · Cited by 17
Trtík, M., & Strejček, J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11936-6_27 · Cited by 16
Techniques to facilitate symbolic execution of real-world programs
Harrold, M. J., & Anand, S. (2012) · SMARTech Repository (Georgia Institute of Technology) · Cited by 16
Slabý, J., Strejček, J., & Trtík, M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-02444-8_15 · Cited by 14
Automated generation of model classes for Java PathFinder
Ceccarello, M., & Tkachuk, O. (2014) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/2557833.2560572 · Cited by 11
Problem Solving for the 21st Century: Efficient Solvers for Satisfiability Modulo Theories
Barrett, C., Kroening, D., & Melham, T. F. (2014) · Cited by 9
Intelligent Computer Mathematics
Sturm, T., Ábrahám, E., Abbott, J., et al. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-42547-4 · Cited by 8
What can we gain by unfolding loops?
Song, L., & Kavi, K. M. (2004) · ACM SIGPLAN Notices · doi:10.1145/967278.967284 · Cited by 6
Conflict-Directed Graph Coverage
Schwartz‐Narbonne, D., Schäf, M., Jovanović, D., et al. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-17524-9_23 · Cited by 6
An empirical investigation into path divergences for concolic execution using CREST
Chen, T., Lin, X. S., Huang, J., et al. (2015) · Security and Communication Networks · doi:10.1002/sec.1290 · Cited by 5
Enhancing Reuse of Constraint Solutions to Improve Symbolic ExecutionPreprint
Jia, X., Ghezzi, C., & Ying, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.07174 · Cited by 3
Research works printed but not linked: 12
- 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.
- 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
- 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.
- 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
AI system engineering key challenges and lessons learned
Fischer, L., Ehrlinger, L., Geist, V., Ramler, R., Sobiezky, F., Zellinger, W., Brunner, D., Kumar, M., & Moser, B. (2020) · Machine Learning and Knowledge Extraction · doi:10.3390/make3010004 · Cited by 71
“Quality assurance measures in software engineering include, for example, automated testing [131], static code analysis [132], system redocumentation [133], or symbolic execution [134].”
MethodAcademic Source Code Plagiarism Detection by Measuring Program Behavioral Similarity
Cheers, H., Lin, Y., & Smith, S. P. (2021) · IEEE Access · doi:10.1109/access.2021.3069367 · Cited by 59
Detecting Pervasive Source Code Plagiarism through Dynamic Program Behaviours
Cheers, H., Lin, Y., & Smith, S. P. (2020) · Proceedings of the Twenty-Second Australasian Computing Education Conference · doi:10.1145/3373165.3373168 · Cited by 13
“This is achieved by applying symbolic execution [36] to record all execution paths of a program in order to identify: the inputs and outputs of a program, how a program interacts with the system, and the processing of each individual piece of data.”
Method
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.