Sep 28, 2015
Xin Li: Automata-Based Abstraction Refinement for muHORS Model Checking
The model checking of higher-order recursion schemes (HORS), aka. higher-order model checking, is the problem of checking whether the tree generated by a given HORS satisfies a given property. It has recently been studied actively and applied to automated verification of higher-order programs. Kobayashi and Igarashi studied an extension of higher-order model checking called ?HORS model checking, where HORS has been extended with recursive types, so that a wider range of programs, including object-oriented programs and multi-threaded programs, can be precisely modeled and verified. Although the ?HORS model checking is undecidable in general, they developed a sound but incomplete procedure for ?HORS model checking. Unfortunately, however, their procedure was not scalable enough. Inspired by recent progress of (ordinary) HORS model checking, we propose a new procedure for ?HORS model checking, based on automata-based abstraction refinement. We have implemented the new procedure and confirmed that it often outperforms the previous procedure.