FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Propositional Dynamic Logic for Higher-Order Functional Programs

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: