Tech talk: Effective Verification of Low-Level Software with Nested Interrupts

  • Date Tuesday, July 28, 2015  Time 11:00 AM
  • Speaker Lihao Liang
  • Location Galois, Inc., 421 SW 6th Ave., Suite 300, Portland, OR, USA (3rd floor of the Commonwealth Building)
  • Galois is pleased to host the following tech talk. These talks are open to the interested public--please join us! (There is no need to pre-register for the talk.)

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).