Static Analysis of Software: The Abstract Interpretation
Format: PDF / Kindle (mobi) / ePub
The existing literature currently available to students and researchers is very general, covering only the formal techniques of static analysis.
This book presents real examples of the formal techniques called "abstract interpretation" currently being used in various industrial fields: railway, aeronautics, space, automotive, etc.
The purpose of this book is to present students and researchers, in a single book, with the wealth of experience of people who are intrinsically involved in the realization and evaluation of software-based safety critical systems. As the authors are people currently working within the industry, the usual problems of confidentiality, which can occur with other books, is not an issue and so makes it possible to supply new useful information (photos, architectural plans, real examples).
Finallly, we must note the majjor impact off safety, reliaability and avvailability constrainnts on the devvelopment of systems. s Figuree 2.1. The A380 0 Airbus 2.1.2. A few f exampless Fly-bby-wire functiions (see [TRA A 05] and/or Chapter C 6 in [BOU [ 09]) thaat − since the A3800 − are groupped together with w the autop pilot (AP), whhich is the most critical system on o the plane. The T first of theese two functiions (flight coontrols) ensurees that the flight coontrol surfacess are
(Table 2.3) all the values x takes are odd (except in x0), the analysis also considers pairs (Table 2.4). The second difference concerns the final value: it is unique and is worth 10001, following the execution of the real program; whereas the analysis envisages two possibilities: 10000 and 10001. 18.104.22.168.3. Safety of F# As we have seen, the analyzer implements a mathematical function, F#, which makes the abstract state of the program evolve from instruction to instruction. This function
can freely and without formal language describe the expected properties in terms of relations between inputs and outputs. For example: – if p1 is strictly less than 10, function f1 returns the sum of values returned by each call to function f2 (and not twice the return value of function f2, as nothing tells us that f2() is a pure function); – if p1 is strictly less than 10, the value of global variable Glob is unchanged; – if p1 is greater or equal to 10, global variable Glob is assigned the
42-54. ACM Press, 2006. [LER 11] LEROY X., DOLIGEZ D., GARRIGUE J., RÉMY D., VOUILLON J., The Objective Caml system, www. caml.inria.fr/pub/docs/manual-ocaml/index.html. [MAR 04] MARTEL M., “Validation of assembler programs for dsps: a static analyzer”, PASTE ‘04: Proceedings of the 5th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pp. 8-13, ACM Press, 2004. [MAU 05] MAUBORGNE L., RIVAL X., “Trace partitioning in abstract interpretation based static
of the target application in a symbolic execution and verify dynamic properties. This symbolic execution requires the abstraction of concrete values into abstract values (lattice elements), and the computation of fixed points to cover the recursion often present in programs (loop, recursive function). These tools compute abstract values of each variable at each program point. The abstract value of a variable, v, represents all the values v can take during all possible executions of the program.