Numerical static analysis of interrupt-driven programs via sequentialization

摘要

Embedded software often involves intensive numerical computations and thus can contain a number of numerical runtime errors. The technique of numerical static analysis is of practical importance for checking the correctness of embedded software. However, most of the existing approaches of numerical static analysis consider sequential programs, while interrupts are a commonly used technique that introduces concurrency in embedded systems. To this end, a numerical static analysis approach is desired for embedded software with interrupts. In this paper, we propose a sound numerical static analysis approach specifically for interrupt-driven programs based on sequentialization techniques. A key benefit of using sequentialization is the ability to leverage the power of the state-of-the-art analysis and verification techniques for sequential programs to analyze interrupt-driven programs. To be more clear, we first propose a sequentialization algorithm to sequentialize interrupt-driven programs into non-deterministic sequential programs according to the semantics of interrupts. On this basis, we leverage the power of numerical abstract interpretation to analyze numerical properties of the sequentialized programs. Moreover, to improve the analysis precision, we design specific abstract domains to analyze sequentialized interrupt-driven programs by considering their specific features. Finally, we present encouraging experimental results obtained by our prototype implementation.