Deriving abstract transfer functions for analyzing embedded software
Authors:
Open Access
- 14 June 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 41 (7) , 34-43
Abstract
This paper addresses the problem of creating abstract transfer functions supporting dataflow analyses. Writing these functions by hand is problematic: transfer functions are difficult to understand, difficult to make precise, and difficult to debug. Bugs in transfer functions are particularly serious since they defeat the soundness of any program analysis running on top of them. Furthermore, implementing transfer functions by hand is wasteful because the resulting code is often difficult to reuse in new analyzers and to analyze new languages. We have developed algorithms and tools for deriving transfer functions for the bitwise and unsigned interval abstract domains. The interval domain is standard; in the bitwise domain, values are vectors of three-valued bits. For both domains, important challenges are to derive transfer functions that are sound in the presence of integer overflow, and to derive precise transfer functions for operations whose semantics are a mismatch for the domain (i.e., bit-vector operations in the interval domain and arithmetic operations in the bitwise domain). We can derive transfer functions, and execute them, in time linear in the bitwidth of the operands. These functions are maximally precise in most cases. Our generated transfer functions are parameterized by a bitwidth and are independent of the language being analyzed, and also of the language in which the analyzer is written. Currently, we generate interval and bitwise transfer functions in C and OCaml for analyzing C source code, ARM object code, and AVR object code. We evaluate our derived functions by using them in an interprocedural dataflow analyzer.Keywords
This publication has 10 references indexed in Scilit:
- HOIST2004
- Link-time optimization of ARM binaries2004
- Symbolically Computing Most-Precise Abstract Operations for Shape Analysis2004
- Worst-case execution-time analysis for embedded real-time systemsInternational Journal on Software Tools for Technology Transfer, 2003
- Formal Specification and Verification of ARM6Lecture Notes in Computer Science, 2003
- Eliminating Stack Overflow by Abstract Interpretation2003
- Bidwidth analysis with application to silicon compilation2000
- An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic ExecutionReal-Time Systems, 1999
- A high-performance microarchitecture with hardware-programmable functional units1994
- Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints1977