IMDEA Software

IMDEA initiative

Home > Events > Invited Talks > 2019 > A Bounded Model Checking Technique for Higher-Order Programs

Yu-yang Lin

Tuesday, October 15, 2019

10:45am Meeting room 302 (Mountain View), level 3

Yu-yang Lin, PhD Student, Queen Mary, London University

A Bounded Model Checking Technique for Higher-Order Programs


We present a Bounded Model Checking technique for higher-order programs based on defunctionalization and points-to analysis. The vehicle of our study is a higher-order calculus with general references. Our technique is a symbolic state syntactical translation based on SMT solvers, adapted to a setting where the values passed and stored during computation can be functions of arbitrary order. We prove that our algorithm is sound and provide a prototype implementation with experimental results showcasing its performance. The first novelty of our technique is a presentation of defunctionalization using nominal techniques, which provides a theoretical background to proving soundness of our technique, coupled with SSA adapted to higher-order values. The second novelty is our use of defunctionalization and points-to analysis to directly encode general higher-order functional programs.