Reproduce “From Traces to Program Incorrectness: A Type-Theoretic Approach” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Yongwei Yuan, Zhe Zhou, Julia Belyakova, Benjamin Delaware, Suresh Jagannathan
Purdue University researchers developed a type-theoretic framework for systematically detecting program incorrectness in functional programs interacting with effectful library APIs. The approach uses symbolic regular expressions to specify undesirable behaviors and introduces a novel type inference algorithm to automatically synthesize execution witnesses for these incorrectness patterns.
Key insights
- Shifting from universal safety reasoning to existential incorrectness reasoning simplifies bug detection by focusing on specific undesirable patterns rather than exhaustive correct behavior.
- Symbolic Regular Expressions and Symbolic Finite Automata offer a powerful and concise formalism for specifying and manipulating abstract, data-aware traces compositionally.
- Trace-guided decomposition and abduction within type inference can effectively guide underapproximate reasoning, making the search for incorrectness witnesses more tractable.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.