|
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer program which gains information about its semantics (e.g. control structure, flow of information) without performing all the calculations. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
In the main, semantics (from the Greek and in greek letters σημαντικός or in latin letters semantikós, or significant meaning, derived from sema, sign) is the study of meaning, in some sense of that term. ...
In mathematics, functions between ordered sets are monotonic (or monotone, or even isotone) if they preserve the given order. ...
...
The name lattice is suggested by the form of the Hasse diagram depicting it. ...
The terms computer program, software program, applications program, system software, or just program are used to refer to either an executable program by both lay people and computer programmers or the collection of source code from which an executable program is created (eg, compiled). ...
In the main, semantics (from the Greek and in greek letters σημαντικός or in latin letters semantikós, or significant meaning, derived from sema, sign) is the study of meaning, in some sense of that term. ...
In computer science and in computer programming, statements in pseudocode or in a program are normally obeyed one after the other in the order in which they are written (sequential flow of control). ...
In discourse-based grammatical theory, information flow is any tracking of referential information by speakers. ...
A calculation is a deliberate process for transforming one or more inputs into one or more results. ...
Its main concrete application is formal static analysis, the automatic extraction of information about the possible executions of computer programs; such analyses have two main usages: Static code analysis is a set of methods for analysing software source code or object code in an effort to gain understanding of what the software does and establish certain correctness criteria. ...
Abstract interpretation was formalized by Patrick Cousot and Radhia Cousot. A diagram of the operation of a typical multi-language compiler. ...
It has been suggested that Loop optimization be merged into this article or section. ...
ÃInsert non-formatted text here ...
Debugging is a methodical process of finding and reducing the number of bugs, or defects, in a computer program or a piece of electronic hardware thus making it behave as expected. ...
Intuition
We shall now illustrate what abstract interpretation would mean on real-world, non-computing examples.
Let us consider the people in a conference room. If we wish to prove that some persons were not present, one concrete method is to look up a list of the names and social security numbers of all participants. Since no two persons have the same number, it is possible to prove or disprove the presence of a participant simply by looking up his or her number in the list. This article needs cleanup. ...
We may however have restricted ourselves to registering only their names. If the name of a person is not found in the list, we may safely conclude that that person was not present; but if it is, we cannot conclude definitely without further enquiries, due to the possibility of homonyms. Let us note that this imprecise information will still be adequate for most purposes, because homonyms are rare in practice. However, in all rigor, we cannot say for sure that somebody was present in the room; all we can say is that he or she was possibly here. If the person we are looking up is a criminal, we will issue an alarm; but there is of course the possibility of issuing a false alarm. Similar phenomena will occur in the analysis of programs. A homonym is one of a group of two or more words that have the same phonetic form (i. ...
If we are only interested in some specific information, say, "was there a person of age n in the room", keeping a list of all names and dates of births is unnecessary. We may safely and without loss of precision restrict ourselves to keeping a list of the participants' ages. If this is already too much to handle, we might keep only the minimal m and maximal M ages. If the question is about an age strictly lower than m or strictly higher than M, then we may safely respond that no such participant was present. Otherwise, we may only be able to say that we do not know.
In the case of computing, concrete, precise information is in general not computable within finite time and memory (see Rice's theorem and the halting problem). Abstraction is used to simplify problems up to problems amenable to automatic solutions. One crucial issue is to diminish precision so as to make problems manageable while still keeping enough precision for answering the questions (such as "may the program crash?") one is interested in. Rices theorem (also known as The Rice-Myhill-Shapiro theorem) is an important result in the theory of recursive functions. ...
In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ...
Abstraction is the process of reducing the information content of a concept, typically in order to retain only information which is relevant for a particular purpose. ...
Abstract interpretation of computer programs Given a programming or specification language, abstract interpretation consists in giving several semantics linked by relations of abstraction. A semantics is a mathematical characterization of the possible behaviors of the program. The most precise semantics, describing very closely the actual execution of the program, is called the concrete semantics. For instance, the concrete semantics of an imperative programming language may associate to each program the set of execution traces it may produce – an execution trace being a sequence of possible consecutive states of the execution of the program; a state typically consists of the value of the program counter and the memory locations (globals, stack and heap). More abstract semantics are then derived; for instance, one may consider only the set of reachable states in the executions (which amounts to considering the last states in finite traces).
The goal of static analysis is to derive a computable semantic interpretation at some point. For instance, one may choose to represent the state of a program manipulating integer variables by forgetting the actual values of the variables and only keeping their signs (+, - or 0). For some elementary operations, such as multiplication, such an abstraction does not lose any precision: to get the sign of a product, it is sufficient to know the sign of the operands. For some other operations, the abstraction may lose precision: for instance, it is impossible to know the sign of a sum whose operands are respectively positive and negative. In mathematics, multiplication is an arithmetic operation which is the inverse of division, and in elementary arithmetic, can be interpreted as repeated addition. ...
Sometimes a loss of precision is necessary to make the semantics decidable (see Rice's theorem, halting problem). In general, there is a compromise to be made between the precision of the analysis and its decidability (computability), or tractability (complexity). Rices theorem (also known as The Rice-Myhill-Shapiro theorem) is an important result in the theory of recursive functions. ...
In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ...
In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ...
For the Computer Science term, see Computational complexity theory. ...
In practice the abstractions that are defined, are tailored to both the program properties one desires to analyse, and to the set of target programs.
Formalization Let L be an ordered set, called a concrete set and let L′ be another ordered set, called an abstract set. These two sets are related to each other by defining total functions that map elements from one to the other.
A function α is called an abstraction function if it maps an element x in the concrete set L to an element α(x) in the abstract set L′. That is, element α(x) in L′ is the abstraction of x in L.
A function γ is called a concretization function if it maps an element x′ in the abstract set L′ to an element γ(x′) in the concrete set L. That is, element γ(x′) in L is a concretization of x′ in L′.
Let L1, L2, L′1 and L′2 be ordered sets. The concrete semantics f is a monotonic function from L1 to L2. A function f′ from L′1 to L′2 is said to be a valid abstraction of f if for all x′ in L′1, (f ∘ γ)(x′) ≤ (γ ∘ f′)(x′).
Program semantics are generally described using fixed points in the presence of loops or recursive procedures. Let us suppose that L is a complete lattice and let f be a monotonic function from L into L. Then, any x′ such that f′(x′) ≤ x′ is an abstraction of the least fixed-point of f, which exists, according to the Knaster-Tarski theorem. In mathematics, a fixed point (sometimes shortened to fixpoint) of a function is a point that is mapped to itself by the function. ...
In the mathematical areas of order and lattice theory, the Knaster-Tarski theorem, named after Bronislaw Knaster and Alfred Tarski, states the following: Let L be a complete lattice and let f : L → L be an order-preserving function. ...
The difficulty is now to obtain such an x′. If L' is of finite height, or at least verifies the "ascending chain condition" (all ascending sequences are ultimately stationary), then such an x′ may be obtained as the stationary limit of the ascending sequence x′n defined by induction as follows: x′0=⊥ (the least element of L′) and x′n+1=f′(x′n).
In other cases, it is still possible to obtain such an x′ through a widening operator ∇: for all x and y, x ∇ y should be greater or equal than both x and y, and for all sequence y′n, the sequence defined by x′0=⊥ and x′n+1=x′n ∇ y′n is ultimately stationary. We can then take y′n=f(x′n).
In some cases, it is possible to define abstractions using Galois connections (α, γ) where α is from L to L′ and γ is from L′ to L. This supposes the existence of best abstractions, which is not necessarily the case. For instance, if we abstract sets of couples (x,y) of real numbers by enclosing convex polyhedra, there is no optimal abstraction to the disc defined by x2+y2 ≤ 1. In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets (posets). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. ...
In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ...
This article is about the geometric shape. ...
Examples of abstract domains One can assign to each variable x available at a given program point an interval [lx,hx]. A state assigning the value v(x) to variable x will be a concretization of these intervals if for all x, then v(x) is in [lx,hx]. From the intervals [lx,hx] and [ly,hy] for variables x and y, one can easily obtain intervals for x+y ([lx+ly,hx+hy]) and for x-y ([lx-hy,hx-ly]); note that these are exact abstractions, since the set of possible outcomes for, say, x+y, is precisely the interval ([lx+ly,hx+hy]). More complex formulas can be derived for multiplication, division, etc., yielding so-called interval arithmetics.
Let us now consider the following very simple program:
y = x; z = x - y; With reasonable arithmetic types, the result for z should be zero. But if we do interval arithmetics starting from x in [0,1], one gets z in [-1,1]. While each of the operations taken individually was exactly abstracted, their composition isn't.
The problem is evident: we did not keep track of the equality relationship between x y; actually, this domain of intervals does not take into account any relationships between variables, and is thus a non-relational domain. Non-relational domains tend to be fast and simple to implement, but imprecise.
Some examples of Relational numerical abstract domains are:
- convex polyhedra – with some high computational costs
- "octagons"
- difference-bound matrices
- linear equalities
and combinations thereof. In mathematics, there are three related meanings of the term polyhedron: in the traditional meaning it is a 3-dimensional polytope, and in a newer meaning that exists alongside the older one it is a bounded or unbounded generalization of a polytope of any dimension. ...
When one chooses an abstract domain, one typically has to strike a balance between keeping fine-grained relationships, and high computational costs.
Tools - ASTRÉE
- PolySpace Technologies
- PAG and PAG/WWW
- Airac
See also Daedalus and Icarus, by Charles Paul Landon, 1799 (Musée des Beaux-Arts et de la Dentelle, Alençon) In Greek mythology, Daedalus (Latin, also Hellenized Latin Daedalos, Greek Daidalos cunning worker and Etruscan Taitle) was a most skillful artificer and was even said to have first invented images. ...
An interpreter is a computer program that executes other programs. ...
Model checking is a method to algorithmically verify formal systems. ...
External links |
Feeds |
Contact