Publication Details

Advanced Automata-based Algorithms for Program Termination Checking

HEIZMANN Matthias, CHEN Yu-Fang, LENGÁL Ondřej, LI Yong, TSAI Ming-Hsien, TURRINI Andrea and ZHANG Lijun. Advanced Automata-based Algorithms for Program Termination Checking. In: Proceedings of PLDI'18. Philadelphia: Association for Computing Machinery, 2018, pp. 135-150. ISBN 978-1-4503-5698-5.
Czech title
Pokročilé algoritmy pro ověřování terminace programů založené na automatech
Type
conference paper
Language
english
Authors
Heizmann Matthias (UNI Freiburg)
Chen Yu-Fang (ASIN)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Li Yong (Chinese Academy of Sciences)
Tsai Ming-Hsien (ASIN)
Turrini Andrea (Chinese Academy of Sciences)
Zhang Lijun (Chinese Academy of Sciences)
Keywords

automata theory, bug detection, correctness,program logics, software engineering, static analysis, symbolic execution, verification

Abstract

In 2014, Heizmann et al. proposed a novel framework for program termination analysis. The analysis starts with a termination proof of a sample path. The path is generalized to
a Büchi automaton (BA) whose language (by construction) represents a set of terminating paths. All these paths can be safely removed from the program. The removal of paths is done using automata difference, implemented via BA complementation and intersection. The analysis constructs in this way a set of BAs that jointly "cover" the behavior of the program, thus proving its termination. An implementation of the approach in Ultimate Automizer won the 1st place in the Termination category of SV-Comp 2017. In this paper, we exploit advanced automata-based algorithms and propose several non-trivial improvements of the framework. To alleviate the complementation computation for BAs---one of the most expensive operations in the framework---, we propose a multi-stage generalization construction. We start with generalizations producing subclasses of BAs (such as deterministic BAs) for which efficient complementation algorithms are known, and proceed to more general classes only if necessary. Particularly, we focus on the quite expressive subclass of semideterministic BAs and provide an improved complementation algorithm for this class. Our experimental evaluation shows that the proposed approach significantly improves the power of termination checking within the Ultimate Automizer framework.

Published
2018
Pages
135-150
Proceedings
Proceedings of PLDI'18
Conference
ACM SIGPLAN Conference on Programming Language Design and Implementation -- PLDI'18, Philadelphia, US
ISBN
978-1-4503-5698-5
Publisher
Association for Computing Machinery
Place
Philadelphia, US
DOI
10.1145/3192366.3192405
UT WoS
000452469600010
EID Scopus
2-s2.0-85049572424
BibTeX 
@INPROCEEDINGS{FITPUB11668,
   author = "Matthias Heizmann and Yu-Fang Chen and Ond\v{r}ej Leng\'{a}l and Yong Li and Ming-Hsien Tsai and Andrea Turrini and Lijun Zhang",
   title = "Advanced Automata-based Algorithms for Program Termination Checking",
   pages = "135--150",
   booktitle = "Proceedings of PLDI'18",
   year = 2018,
   location = "Philadelphia, US",
   publisher = "Association for Computing Machinery",
   ISBN = "978-1-4503-5698-5",
   doi = "10.1145/3192366.3192405",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11668"
}
Back to top