Authors: Yuki Satake and Hiroshi Unno
Paper Information
Title: | Propositional Dynamic Logic for Higher-Order Functional Programs |
Authors: | Yuki Satake and Hiroshi Unno |
Proceedings: | CAV All Papers |
Editors: | Georg Weissenbacher, Hana Chockler and Igor Konnov |
Keywords: | Higher-Order Programs, Temporal Verification, Propositional Dynamic Logic, Model Checking, Stack-Based Access Control, Dependent Refinement Types |
Abstract: | ABSTRACT. We present an extension of propositional dynamic logic called HOT-PDL for specifying temporal properties of higher-order functional programs. The semantics of HOT-PDL is defined over Higher-Order Traces (HOTs) that model execution traces of higher-order programs. A HOT is a sequence of events such as function calls and returns, equipped with two kinds of pointers inspired by the notion of justification pointers from game semantics: one for capturing the correspondence between call and return events, and the other for capturing higher-order control flow involving a function that is passed to or returned by a higher-order function. To allow traversal of the new kinds of pointers, HOT-PDL extends PDL with new path expressions. The extension enables HOT-PDL to specify interesting properties of higher-order programs, including stack-based access control properties and those definable using dependent refinement types. We show that HOT-PDL model checking of higher-order functional programs over bounded integers is decidable via a reduction to modal $\mu$-calculus model checking of higher-order recursion schemes. |
Pages: | 18 |
Talk: | Jul 14 11:00 (Session 95A: Model Checking) |
Paper: |