Modular Verification of Termination and Execution Time Bounds Using Separation Logic
Jafar Hamin, Bart Jacobs · 2016
This paper presents a formal method to verify execution time bounds of programs at the source level, where timing constraints along with other functional requirements are specified in the routines' contracts and are verified in a modular manner. The approach works based on a countdown time budget mechanism to guarantee the termination of the input program, and incorporates the concepts of separation logic, making it integrable with verification approaches for pointer-manipulating programs and applicable for concurrent programs where time resource needs to be passed among different threads. We selected the MSP430 microcontroller as well as a simple non-optimizing compiler as a case study and defined a co-inductive concrete semantics to model time consumption and potential non-termination of commands based on this platform. Accordingly, we developed the corresponding symbolic execution and proved that it is sound, i.e., if a program does not fail in the symbolic execution, then it respects the specified time bounds in the concrete execution too. Our preliminary results show that the proposed approach can be used to verify time bounds of programs involving separation logic based specifications.