Static Analysis

Static analysis is a set of techniques for analyzing and reasoning on programs without actually running them. This is why they are named static as opposed to dynamic, which corresponds to testing. Static analysis aims to analyze exhaustively a program's behavior in the sense that all input values are considered. This again can be compared to dynamic analysis where, generally, input values are considered in isolation and tested on the program. Testing is generally nonexhaustive because of the input domain size.

Abstract Interpretation is a technique explored in detail by P. Cousot and R. Cousot3 that provides results by executing an abstract version of the analyzed program. The word abstract should be understood as a simplified version, where the domains of variables are replaced by simpler ones and the program instructions operate on these simplified domains. For instance, the data type int can be replaced by the lattice I = {-,0, + } with three symbols that denote, respectively, the subset of negative, null, and positive integers. When computing with variables of abstract domains, basic operations are simplified too. For instance, the binary + operation on integers becomes the binary © operation on I elements, defined by the rules detailed in Figure 16-1.

The reader might have noticed that lattices are considered instead of types (which are equivalent to sets). In fact, domains are complete lattices, with an uppermost and a lowermost element, respectively denoted by T and 1. This is necessary because an integer might be a valid integer in the target machine representation, but also any integer (represented by the value T , meaning Top, the supremum element) or undefined integer (represented by 1, meaning Bottom, the infimum element). The theory of lattices can be found at http://en.wikipedia.org/wiki/CompleteJattice. Many other lattices can be used, such as the lattices of integer intervals, polyhedra, and octagons, as well as their combination (the composition of two complete lattices being a complete lattice).

What is important to remember is that the operations performed in the abstract program reflect those made in the actual program, albeit in a simpler but still valid manner.3

The abstract program operates on abstract values, which are coarser than the actual values, but on which the computations are simpler. Executions in the abstract world can, therefore, express results for entire classes of input values at once. Abstract calculus can be done faster than its concrete counterpart. Consider, for instance, the addition of integers that is replaced by the abstract operation © whose computation is much less complex. One factor in making these abstract executions fast is the approximation that takes place in loops, which allows the analysis of programs whose execution does not terminate to be done in a finite amount of time. However, in practice, abstract executions

®

i

0

+

-

-

T

T

0

T

0

T

é

T

T

+

Figure 16-1 Definition of function ©

Figure 16-1 Definition of function ©

3. See Patrick Cousot and Radhia Cousot's Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints, POPL, 1977 and Patrick Cousot's Méthodes itératives de construction et d'approximation de points fixes d'opérateurs monotones sur un treillis. Analyse sémantique de programmes, Ph.D. thesis dissertation, Scientific and Medical University of Grenoble, 1978.

can still be very costly in terms of time and memory space, especially if the chosen abstractions do not fit the analyzed program well. This cost can become the limiting factor in the use of abstract interpretation techniques.

Was this article helpful?

0 0
The Ultimate Computer Repair Guide

The Ultimate Computer Repair Guide

Read how to maintain and repair any desktop and laptop computer. This Ebook has articles with photos and videos that show detailed step by step pc repair and maintenance procedures. There are many links to online videos that explain how you can build, maintain, speed up, clean, and repair your computer yourself. Put the money that you were going to pay the PC Tech in your own pocket.

Get My Free Ebook


Post a comment