Summary Interpretation in a Nutshell
This introduction to static evaluation by summary interpretation has the
goal of being easy, intuitive and casual. Extra technical
introductions in addition to bibliographic references are supplied in
[1,2,3].
A 30mn video (in French) may also be helpful.
1. Concrete semantics of packages
The concrete semantics of packages formalizes the set of
all doable executions of this program in all doable execution
environments. If an execution is represented by a curve displaying the
evolution of the vector x(t) of values of the enter,
state and output variables of this system as a perform of the time
t, this concrete semantics might be represented by a set of
curves (with steady time for brief):
x(t)
t
2. Undecidability
The concrete semantics of a program is an “infinite” mathematical object
which is not computable:
it’s not doable to put in writing a program
capable of characterize and to compute all doable executions of any program
in all its doable execution environments.
Therefore, all non trivial questions concerning the concrete semantics of a
program are undecidable: it’s not doable to put in writing a program
capable of reply any query concerning the doable executions of any program
(because the concrete semantics of this program must be
computable).
The mathematical analogy is that there isn’t a theorem prover
in a position, for instance, to show any theorem of arithmetics with out
human help.
3. Specification of Security Properties
Security properties of a program categorical that no doable execution of the
program when contemplating all doable execution environments can attain an
inaccurate state. Graphically, the set of those inaccurate states might be
represented as a forbidden zone:
x(t)
t
4. Proof of Security Properties
The verification of security properties consists in proving that the
intersection of the concrete semantics of this system with the forbidden
zone is empty. For the reason that program concrete semantics isn’t computable,
the verification downside is undecidable. It’s not at all times doable to
reply the protection questions fully routinely, with finite pc
sources, with none uncertainty concerning the reply and with none
human intervention.
5. Testing/Debugging
Testing/debugging consists in contemplating a subset of the doable executions:
x(t)
t
Testing/debugging isn’t a proof, since some inaccurate trajectories
may be forgotten. That is the issue of absence of protection.
6. Bounded mannequin checking
Bounded mannequin checking consists in exploring the prefixes of the doable executions:
x(t)
t
Bounded mannequin checking isn’t a proof, since late errors might be missed. This is identical downside of absence of protection.
7. Summary Interpretation
Summary interpretation consists in contemplating an summary semantics,
that may be a superset of the concrete program semantics:
x(t)
t
The summary semantics covers all doable circumstances. Whence, if the
summary semantics is secure (i.e. doesn’t intersect the forbidden zone)
then so is the concrete semantics.
8. Formal Strategies
Formal strategies are summary interpretations which differ in
the way in which the summary semantics is obtained. In all circumstances, the summary
semantics should be chosen to be pc representable.
 In modelchecking, the summary semantics is supplied manually
by the person within the type of a finitary mannequin of this system execution
(for instance a finite automaton) [9]. In some
circumstances the mannequin might be computed routinely, by strategies related to
static evaluation.  In deductive strategies the summary semantics is specified by
verification situations and should be supplied by the person within the type of
inductive properties (true at every program step, resembling loop
invariants) satisfying these verification situations
[5]. The inductive properties should be discovered manually by
the person and the theory prover generally wants help to show that
they’re certainly inductive. To assist the person on this discovery job, some
of those inductive properties might be computed routinely, by
strategies related to static evaluation.  In static evaluation,
the summary semantics is computed
routinely due to predefined approximations
[1,6,7,8],
presumably manually parameterizable by the person.
In all circumstances, the summary semantics ought to be sound
(part 1.8
), stay sufficiently exact to keep away from false alarms
(part 1.10
) whereas remaining so simple as doable to keep away from
combinatorial explosion phenomena (part 1.13
).
9. Faulty Abstractions
In formal strategies the summary semantics should be chosen as a superset
of the concrete semantics since in any other case reasonings within the summary
may not be right within the concrete:
x(t)
t
We are saying that an abstraction is sound (or right) if the
summary semantics covers all doable circumstances of the concrete semantics.
All formal strategies are required to make use of sound abstractions: if a
potential error isn’t signaled that it ought to be undoubtedly not possible.
Opposite to testing/debugging formal strategies present full protection.
10. Examples of Faulty Abstractions
But, some strategies, offered as formal, don’t discover
all doable trajectories, however solely prefixes (resembling
the “bounded modelchecking”) or could not terminate
(such because the “refinement modelchecking”) and subsequently
ought to be thoughtabout as incorrect, since some errors
might be forgotten:
x(t)
t
11. False Alarms
The summary semantics on which formal strategies rely are:
 right/sound, that may be a superset of the concrete semantics, and
 easy, or not less than easy sufficient to be representable in a machine.
In absence of alarms, this yields a corectness proof. Nevertheless, the
consequence of the overapproximation of the doable executions is that
inexisting executions are thoughtabout, a few of that are inaccurate, which
results in false alarms (additionally known as false positives). A
false alarm corresponds to the case when the summary semantics
intersects the forbidden zone whereas the concrete semantics doesn’t
intersect this forbidden zone. So a possible error is signaled which may
by no means happen in actuality:
x(t)
t
12. Incompleteness of Formal Strategies
Computerized formal strategies are all incomplete: there exists
an infinity of packages for which potential errors at execution
are signaled, even when they’re undoubtedly not possible in actuality.
 In modelchecking an alarm within the mannequin could not correspond to an
inevitable error within the modelized system^{1}.  In deductive strategies, false alarms could also be
because of the impossibility to show routinely that the person supplied
invariant is certainly inductive.  In static evaluation, false alarms are due
to an absence of precision of the evaluation.
Such false alarms are inevitable as a result of all questions that formal
strategies attempt to remedy are undecidable. Il will at all times be doable to search out
a program with none runtime error for which the summary semantics
will probably be too imprecise to show the absence of error absolutely routinely,
with none human intervention. The imprecision downside can typically be
solved by selecting a extra refined summary semantics, which is extra
exact and so typically extra complicated, which ends up in bigger computation
prices.
13. Excluded Miracle
In abstract, with testing/debugging a subset of the doable program
executions is taken into account, in order that errors might be forgotten. With summary
interpretationbased formal strategies, a superset of the doable
program executions is taken into account, in order that, due to the potential
imprecision, one can invent errors that don’t exist in actuality (so
known as “false alarms”).
Therefore one wish to have right formal strategies (with out inaccurate
abstractions by absence of protection) and full (with out false alarms
because of overcoverage). Such an abstraction does exists mathematically
[4], however it’s not possible to compute, and this as a result of
if undecidability, which quantities to say that it’s not possible to execute
this system in all doable execution surroundings in a finite time with
a finite reminiscence.
14. Invariants
An invariant is a property which holds for all trajectories.
Within the instance under, a primary invariant could be that every one states
reachable throughout the course of the computation might be on any
trajectory. That is already an approximation since this leaves the
chance to leap from one trajectory to a different, and even to go
backwards.
A second invariant, much less exact, could be that every one trajectories are in
the inexperienced zone
. This can be a much less exact
approximation which leaves the likelihood to succeed in factors out of any
trajectory:
x(t)
t
This second invariant imples a 3rd one, even much less exact, stating that every one
trajectories are exterior the forbidden purple zone
:
x(t)
t
15. Program Summary Invariants
A program invariant is a program property which holds throughout the
program execution. The ASTRÉE static analyzer computes routinely
an summary semantics which consists of native summary invariants
connected to program factors or to program blocks stating properties about
a part of this system variables that are seen at that program level or
withing that block. These native invariants holds of the concerned
variables at any time when management reaches that program level or stays inside
that block.
16. Summary Domains
An summary area of the ASTRÉE static analyzer is a
pc illustration of a given class of invariants and of the
operations concerned within the computation of those summary invariants.
ASTRÉE makes use of a large number of summary domains that are mixed to
acquire complicated summary invariants. The time period “summary” makes
reference to the truth that the computed invariants are right
approximations of this system concrete semantics.
A classical summary area is that of intervals
[2,6,8] which approximate an
ordered set of values by their minimal and their most. Utilized to our
instance, this interval abstraction yields the next invariant:
x(t)
t
which is simply too
imprecise to show the specification. To be exact, ASTRÉE
incorporates summary domains that are expressive sufficient to take into
account the properties of command packages controlling complicated discrete
dynamical programs.
17. Extra on summary interrpetation
Extra topcis and references on abstract interrpetation and a course [10] are additionally accessible online.
Bibliography
 [1]

P. Cousot.
Semantic foundations of program analysis.
In S.S. Muchnick and N.D. Jones, editors, Program Move
Evaluation: Idea and Purposes, chapter 10, pages 303342.
PrenticeHall, 1981.  [2]

P. Cousot.
Abstract interpretation based formal methods and future challenges,
invited paper.
In R. Wilhelm, editor, « Informatics – 10 Years Again, 10
Years Forward », quantity 2000 of LNCS, pages 138156. Springer, 2000.  [3]

P. Cousot.
Interprétation abstraite.
TSI, 19(123):155164, Jan. 2000.  [4]

P. Cousot.
Partial completeness of abstract fixpoint checking, invited paper.
In B.Y. Choueiry and T. Walsh, editors, Proc.
4^{th} Int. Symp. SARA ‘2000, Horseshoe Bay, TX, US,
LNAI 1864, pages 125. Springer, 2629 Jul. 2000.  [5]

P. Cousot.
Constructive design of a hierarchy of semantics of a transition
system by abstract interpretation.
Theoret. Comput. Sci., 277(12):47103, 2002.  [6]

P. Cousot and R. Cousot.
Abstract interpretation: a unified lattice model for static analysis
of programs by construction or approximation of fixpoints.
In 4^{th} POPL, pages 238252, Los Angeles, CA,
1977. ACM Press.  [7]

P. Cousot and R. Cousot.
Systematic design of program analysis frameworks.
In 6^{th} POPL, pages 269282, San Antonio, TX,
1979. ACM Press.  [8]

P. Cousot and R. Cousot.
Comparing the Galois connection and widening/narrowing approaches
to abstract interpretation, invited paper.
In M. Bruynooghe and M. Wirsing, editors, Proc.
4^{th} Int. Symp. PLILP ’92, Leuven, BE, 2628 Aug.
1992, LNCS 631, pages 269295. Springer, 1992.  [9]

P. Cousot and R. Cousot.
Temporal abstract interpretation.
In 27^{th} POPL, pages 1225, Boston, MA, Jan.
2000. ACM Press.
Online programs on summary interpretation
MIT
Course 16.399: Abstract Interpretation.
http://web.mit.edu/afs/athena.mit.edu/course/16/16.399/www/, 2005.
Notes:
^{1} One should additionally word the
chance of false negatives equivalent to properties which
are true of the mannequin however are false of the concrete semantics of the
modelized system, which is simply too typically the case of “liveness”
properties.