Program Synthesis via Bi-directional Reduced-product Abstract Interpretation

on YouTube ↗39m

" summary

Claims that a forward-and-backward abstract interpretation pipeline with a reduced-product of simple domains (bitwise, unsigned interval, sign interval) plus finite refinement prunes partial programs so the synthesizer searches far less. Builds Simba, an inductive synthesizer for bit-manipulation grammars that solves many Hacker’s Delight-style tasks from 5–20 input/output pairs in under a second to at most 35 minutes and outperforms prior tools on fastest-solved benchmarks. Experiments report markedly higher solved counts within tight time bounds.

AI-written summary · about

" chapters (20)

1. 0:00Introduction
2. 1:31Program analysis and synthesis overview
3. 2:13Abstract interpretation analyzers
4. 3:58Commercialization challenges
5. 6:47SP analysis scalability
6. 8:55Spatial and temporal localization
7. 11:49Precision improvement techniques
8. 15:48Context sensitivity for accuracy
9. 16:10Transition to synthesis research
10. 16:30Inductive synthesis fundamentals
11. 17:33Bit manipulation synthesis
12. 19:00Deobfuscation via synthesis
13. 19:41Performance comparison
14. 20:24Hybrid synthesis approach
15. 21:49Partial program analysis
16. 25:10Combining abstract domains
17. 27:01Abstraction refinement techniques
18. 28:25Synthesis results and impact
19. 29:29Reflections on framework
20. 30:57Q&A