Abstract Interpretation - Examples of Abstract Domains

Examples of Abstract Domains

One can assign to each variable x available at a given program point an interval . A state assigning the value v(x) to variable x will be a concretization of these intervals if for all x, v(x) is in . From the intervals and for variables x and y, one can easily obtain intervals for x+y and for xy ; note that these are exact abstractions, since the set of possible outcomes for, say, x+y, is precisely the interval . 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 arithmetic starting from x in, one gets z in . 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 and 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:

  • congruence relations on integers
  • convex polyhedra – with some high computational costs
  • "octagons"
  • difference-bound matrices
  • linear equalities

and combinations thereof.

When one chooses an abstract domain, one typically has to strike a balance between keeping fine-grained relationships, and high computational costs.

Read more about this topic:  Abstract Interpretation

Famous quotes containing the words examples of, examples, abstract and/or domains:

    Histories are more full of examples of the fidelity of dogs than of friends.
    Alexander Pope (1688–1744)

    In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.
    Michel de Montaigne (1533–1592)

    The whole body of what is now called moral or ethical truth existed in the golden age as abstract science. Or, if we prefer, we may say that the laws of Nature are the purest morality.
    Henry David Thoreau (1817–1862)

    I shall be a benefactor if I conquer some realms from the night, if I report to the gazettes anything transpiring about us at that season worthy of their attention,—if I can show men that there is some beauty awake while they are asleep,—if I add to the domains of poetry.
    Henry David Thoreau (1817–1862)