Modular verification for almost-sure termination of probabilistic programs

M. Huang, H. Fu, K. Chatterjee, A.K. Goharshady, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications , ACM, n.d.

Download
OA 1.02 MB
Conference Paper | Accepted | English
Author
Department
Abstract
In this work, we consider the almost-sure termination problem for probabilistic programs that asks whether a given probabilistic program terminates with probability 1. Scalable approaches for program analysis often rely on modularity as their theoretical basis. In non-probabilistic programs, the classical variant rule (V-rule) of Floyd-Hoare logic provides the foundation for modular analysis. Extension of this rule to almost-sure termination of probabilistic programs is quite tricky, and a probabilistic variant was proposed in [16]. While the proposed probabilistic variant cautiously addresses the key issue of integrability, we show that the proposed modular rule is still not sound for almost-sure termination of probabilistic programs. Besides establishing unsoundness of the previous rule, our contributions are as follows: First, we present a sound modular rule for almost-sure termination of probabilistic programs. Our approach is based on a novel notion of descent supermartingales. Second, for algorithmic approaches, we consider descent supermartingales that are linear and show that they can be synthesized in polynomial time. Finally, we present experimental results on a variety of benchmarks and several natural examples that model various types of nested while loops in probabilistic programs and demonstrate that our approach is able to efficiently prove their almost-sure termination property
Publishing Year
Date Published
2019-08-12
Proceedings Title
Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications
Conference
OOPSLA: Object-oriented Programming, Systems, Languages and Applications
Conference Location
Athens, Greece
Conference Date
2019-10-23 – 2019-10-25
IST-REx-ID

Cite this

Huang M, Fu H, Chatterjee K, Goharshady AK. Modular verification for almost-sure termination of probabilistic programs. In: Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications . ACM.
Huang, M., Fu, H., Chatterjee, K., & Goharshady, A. K. (n.d.). Modular verification for almost-sure termination of probabilistic programs. In Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications . Athens, Greece: ACM.
Huang, Mingzhang, Hongfei Fu, Krishnendu Chatterjee, and Amir Kafshdar Goharshady. “Modular Verification for Almost-Sure Termination of Probabilistic Programs.” In Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications . ACM, n.d.
M. Huang, H. Fu, K. Chatterjee, and A. K. Goharshady, “Modular verification for almost-sure termination of probabilistic programs,” in Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications , Athens, Greece.
Huang M, Fu H, Chatterjee K, Goharshady AK. Modular verification for almost-sure termination of probabilistic programs. Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications . OOPSLA: Object-oriented Programming, Systems, Languages and Applications
Huang, Mingzhang, et al. “Modular Verification for Almost-Sure Termination of Probabilistic Programs.” Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications , ACM.
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2019-08-12T15:40:57Z


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

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1901.06087

Search this title in

Google Scholar