Oracle-guided component-based program synthesis
Abstract
We present a novel approach to automatic synthesis of loop-free programs. The approach is based on a combination of oracle-guided learning from examples, and constraint-based synthesis from components using satisfiability modulo theories (SMT) solvers. Our approach is suitable for many applications, including as an aid to program understanding tasks such as deobfuscating malware. We demonstrate the efficiency and effectiveness of our approach by synthesizing bit-manipulating programs and by deobfuscating programs.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
A mispredicted transition is a counterexample.
“A mispredicted transition is a counterexample [Solar-Lezama et al., 2006, Jha et al., 2010], and it serves both as a constraint for the next program and as a real observation that updates the diagnostics.”
From OPINE-World: Programmatic World Modeling with Ontology-error-Prioritized Interactive Exploration for ARC-AGI-3 (2026) · cites this paper as Jha et al., 2010
CEGIS is an iterative algorithm commonly used in Program Synthesis and Formal Methods to construct programs or solutions that satisfy a given specification.
“CEGIS is an iterative algorithm commonly used in Program Synthesis and Formal Methods to construct programs or solutions that satisfy a given specification (Abate et al. 2018; Jha et al. 2010; Solar-Lezama et al. 2005).”
From Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization (2025) · cites this paper as Jha et al. 2010
Cites
Superoptimizer: a look at the smallest program
Massalin, H. (1987) · Proceedings of the second international conference on Architectual support for programming languages and operating systems · doi:10.1145/36206.36194 · Cited by 154 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Alur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E., & Udupa, A. (2013) · 2013 Formal Methods in Computer-Aided Design · doi:10.1109/fmcad.2013.6679385 · Cited by 656 · see citing works
Self-citationVaithilingam, P., Zhang, T., & Glassman, E. L. (2022) · CHI Conference on Human Factors in Computing Systems Extended Abstracts · doi:10.1145/3491101.3519665 · Cited by 660 · see citing works
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1925844.1926423 · Cited by 581 · see citing works
Self-citationThe ManyBugs and IntroClass benchmarks for automated repair of C programs
Le Goues, C., Holtschulte, N., Smith, E. K., Brun, Y., Devanbu, P., Forrest, S., & Weimer, W. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2015.2454513 · Cited by 326 · see citing works
LLM-Based Test-Driven Interactive Code Generation: User Study and Empirical Evaluation
Fakhoury, S., Naik, A., Sakkas, G., Chakraborty, S., & Lahiri, S. K. (2024) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2024.3428972 · Cited by 120 · see citing works
“To minimize the number of user interactions, it is desirable to prioritize tests that would result in the most number of incorrect code suggestions being pruned away [15], [29].”
BackgroundMethodInfluentialProgram synthesis using conflict-driven learning
Feng, Y., Martins, R., Bastani, O., & Dillig, I. (2018) · Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3192366.3192382 · Cited by 111 · see citing works
Exploring the Learnability of Program Synthesizers by Novice Programmers
Jayagopal, D., Lubin, J., & Chasins, S. E. (2022) · Proceedings of the 35th Annual ACM Symposium on User Interface Software and Technology · doi:10.1145/3526113.3545659 · Cited by 40 · see citing works
Constraint-Based Synthesis of Datalog Programs
Albarghouthi, A., Koutris, P., Naik, M., & Smith, C. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-66158-2_44 · Cited by 40 · see citing works
Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization
Orvalho, P., Janota, M., & Manquinho, V. (2025) · arXiv · doi:10.48550/arxiv.2502.07786 · Cited by 4 · see citing works
Courtis, D., Li, W., & Sanner, S. (2026) · arXiv · doi:10.48550/arxiv.2607.01531
LLM-Based Test-Driven Interactive Code Generation: User Study and Empirical Evaluation
Fakhoury, S., Naik, A., Sakkas, G., Chakraborty, S., & Lahiri, S. K. (2024) · arXiv · doi:10.48550/arxiv.2404.10100
“To minimize the number of user interactions, it is desirable to prioritize tests that would result in the most number of incorrect code suggestions being pruned away [15], [29].”
BackgroundMethodInfluential
- Authors
- Jha, S., Gulwani, S., Seshia, S. A., & Tiwari, A.
- Affiliations
- UC Berkeley
- Microsoft Research
- SRI International
- Venue
- Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1
- Publisher
- ACM
- Published
- 2010-05
- Pages
- 215-224
- Cited by
- 365
- References
- 1
- Funders
- Division of Computer and Network Systems (CNS-0644436CNS-0627734CNS-0720721CSR-0917398)
- National Science Foundation (CNS-0644436CNS-0627734CNS-0720721CSR-0917398)
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
