Polynomial reachability witnesses via Stellensätze

Asadi A, Chatterjee K, Fu H, Goharshady AK, Mahdavi M. 2021. Polynomial reachability witnesses via Stellensätze. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. PLDI: Programming Language Design and Implementation, 772–787.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Department
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 semi-complete 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.
Publishing Year
Date Published
2021-06-01
Proceedings Title
Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
Acknowledgement
This research was partially supported by the ERC CoG 863818 (ForM-SMArt), the National Natural Science Foundation of China (NSFC) Grant No. 61802254, the Huawei Innovation Research Program, the Facebook PhD Fellowship Program, and DOC Fellowship No. 24956 of the Austrian Academy of Sciences (ÖAW).
Page
772-787
Conference
PLDI: Programming Language Design and Implementation
Conference Location
Online
Conference Date
2021-06-20 – 2021-06-26
IST-REx-ID

Cite this

Asadi A, Chatterjee K, Fu H, Goharshady AK, Mahdavi M. Polynomial reachability witnesses via Stellensätze. In: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Association for Computing Machinery; 2021:772-787. doi:10.1145/3453483.3454076
Asadi, A., Chatterjee, K., Fu, H., Goharshady, A. K., & Mahdavi, M. (2021). Polynomial reachability witnesses via Stellensätze. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (pp. 772–787). Online: Association for Computing Machinery. https://doi.org/10.1145/3453483.3454076
Asadi, Ali, Krishnendu Chatterjee, Hongfei Fu, Amir Kafshdar Goharshady, and Mohammad Mahdavi. “Polynomial Reachability Witnesses via Stellensätze.” In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 772–87. Association for Computing Machinery, 2021. https://doi.org/10.1145/3453483.3454076.
A. Asadi, K. Chatterjee, H. Fu, A. K. Goharshady, and M. Mahdavi, “Polynomial reachability witnesses via Stellensätze,” in Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Online, 2021, pp. 772–787.
Asadi A, Chatterjee K, Fu H, Goharshady AK, Mahdavi M. 2021. Polynomial reachability witnesses via Stellensätze. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. PLDI: Programming Language Design and Implementation, 772–787.
Asadi, Ali, et al. “Polynomial Reachability Witnesses via Stellensätze.” Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2021, pp. 772–87, doi:10.1145/3453483.3454076.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Search this title in

Google Scholar
ISBN Search