Interrupt-driven software is difficult to test and debug, especially when interrupts can be nested and subject to priorities. Interrupts can arrive at arbitrary times, leading to an explosion in the number of cases to be considered. We present a new formal approach to verifying interrupt-driven software based on symbolic execution. The approach leverages recent advances in the encoding of the execution traces of interacting, concurrent threads. We assess the performance of our method on benchmarks drawn from embedded systems code and device drivers, and experimentally compare it to conventional formal approaches that use source-to-source transformations.Our experimental results show that our method significantly outperforms conventional techniques. To the best of our knowledge, our technique is the first to demonstrate effective formal verification of low-level embedded software with nested interrupts.
Lihao Liang is a PhD student in the Department of Computer Science of University of Oxford, working with Daniel Kroening, Tom Melham and Luke Ong. His research is supported by an Intel funded project Effective Validation of Firmware. He is interested in automated software analysis and verification, particularly concurrent software and synchronization primitives such as read-copy update (RCU).