Polynomial reachability witnesses via Stellensätze
Ali Asadi, Krishnendu Chatterjee, Hongfei Fu, Amir Kafshdar Goharshady, Mohammad Mahdavi
Abstract
We consider the fundamental problem of reachability analysis over imperative programs with real variables. Previous works that tackle reachability are either unable to handle programs consisting of general loops (e.g. symbolic execution), or lack completeness guarantees (e.g. abstract interpretation), or are not automated (e.g. incorrectness logic). In contrast, we propose a novel approach for reachability analysis that can handle general and complex loops, is complete, and can be entirely automated for a wide family of programs. Through the notion of Inductive Reachability Witnesses (IRWs), our approach extends ideas from both invariant generation and termination to reachability analysis.
We first show that our IRW-based approach is sound and complete for reachability analysis of imperative programs. Then, we focus on linear and polynomial programs and develop automated methods for synthesizing linear and polynomial IRWs. In the linear case, we follow the well-known approaches using Farkas' Lemma. Our main contribution is in the polynomial case, where we present a push-button semicomplete algorithm. We achieve this using a novel combination of classical theorems in real algebraic geometry, such as Putinar's Positivstellensatz and Hilbert's Strong Nullstellensatz. Finally, our experimental results show we can prove complex reachability objectives over various benchmarks that were beyond the reach of previous methods.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
22 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs cites Polynomial invariant generation for non-deterministic recursive programs
- Quantitative Bounds on Resource Usage of Probabilistic Programs cites Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs
- Quantitative Bounds on Resource Usage of Probabilistic Programs cites Polynomial invariant generation for non-deterministic recursive programs
- Algebro-geometric Algorithms for Template-Based Synthesis of Polynomial Programs cites Polynomial invariant generation for non-deterministic recursive programs
- Finding real bugs in big programs with incorrectness logic cites Incorrectness logic
- Asparagus: Automated Synthesis of Parametric Gas Upper-Bounds for Smart Contracts cites Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs
- Asparagus: Automated Synthesis of Parametric Gas Upper-Bounds for Smart Contracts cites Polynomial invariant generation for non-deterministic recursive programs
- Asparagus: Automated Synthesis of Parametric Gas Upper-Bounds for Smart Contracts cites Algebro-geometric Algorithms for Template-Based Synthesis of Polynomial Programs
Cited by top-tier papers22
- Finding real bugs in big programs with incorrectness logicQuang Loc Le, Azalea Raad, Jules Villard, Josh Berdine et al.OOPSLA 2022 · 52 citations
- Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Dorde ZikelicCAV 2022 · 30 citations
- Quantitative Bounds on Resource Usage of Probabilistic ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Dorde ZikelicOOPSLA 2024 · 16 citations
- Asparagus: Automated Synthesis of Parametric Gas Upper-Bounds for Smart ContractsZhuo Cai, Soroush Farokhnia, Amir Kafshdar Goharshady, S. HitarthOOPSLA 2023 · 16 citations
- Algebro-geometric Algorithms for Template-Based Synthesis of Polynomial ProgramsAmir Kafshdar Goharshady, S. Hitarth, Fatemeh Mohammadi, Harshit J. MotwaniOOPSLA 2023 · 15 citations
Builds on2
Related papers
- Sound and Complete Witnesses for Template-Based Verification of LTL Properties on Polynomial ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Ehsan Kafshdar Goharshady, Mehrdad Karrabi et al.FM 2024 · 11 citations
- Scalable linear invariant generation with Farkas' lemmaHongming Liu, Hongfei Fu, Zhiyong Yu, Jiaxin Song et al.OOPSLA 2022 · 15 citations
- Simple Linear Loops: Algebraic Invariants and ApplicationsRida Ait El Manssour, George Kenison, Mahsa Shirmohammadi, Anton VaronkaPOPL 2025 · 2 citations
- Breaking the Mold: Nonlinear Ranking Function Synthesis Without TemplatesShaowei Zhu, Zachary KincaidCAV 2024 · 2 citations
- Strong Invariants Are Hard: On the Hardness of Strongest Polynomial Invariants for (Probabilistic) ProgramsJulian Müllner, Marcel Moosbrugger, Laura KovácsPOPL 2024 · 7 citations
