Automata-Based Abstraction Refinement for µHORS 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 muHORS 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 muHORS model checking is undecidable in general, they developed a sound but incomplete procedure for muHORS 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 muHORS model checking, based on automata-based abstraction refinement. We have implemented the new procedure and confirmed that it often outperforms the previous procedure.