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 model-checking, 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 model-checking”) or could not terminate
(such because the “refinement model-checking”) and subsequently
ought to be thought-about as incorrect, since some errors
might be forgotten:

x(t)
t

11.  False Alarms

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 model-checking an alarm within the mannequin could not correspond to an
  inevitable error within the modelized system¹.

• 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 run-time 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
interpretation-based 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 over-coverage). 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

See Also

When the Energy Macintosh ran NetWare (that includes Wormhole and Cyberpunk)

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 on-line.

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 303-342.
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 138-156. Springer, 2000.

[3]

P. Cousot.
Interprétation abstraite.
TSI, 19(1-2-3):155-164, 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 1-25. Springer, 26-29 Jul. 2000.

[5]

P. Cousot.
Constructive design of a hierarchy of semantics of a transition
system by abstract interpretation.
Theoret. Comput. Sci., 277(1-2):47-103, 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 238-252, Los Angeles, CA,
1977. ACM Press.

[7]

P. Cousot and R. Cousot.
Systematic design of program analysis frameworks.
In 6^th POPL, pages 269-282, 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, 26-28 Aug.
1992, LNCS 631, pages 269-295. Springer, 1992.

[9]

P. Cousot and R. Cousot.
Temporal abstract interpretation.
In 27^th POPL, pages 12-25, Boston, MA, Jan.
2000. ACM Press.

On-line programs on summary interpretation

Notes:

¹ 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.