Extended static checking (ESC) is a collective name in
computer science for a range of techniques for
statically checking the correctness of various program constraints. ESC can be thought of as an extended form of
type checking. As with type checking, ESC is performed automatically at
compile time
In computer science, compile time (or compile-time) describes the time window during which a computer program is compiled.
The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concep ...
(i.e. without human intervention). This distinguishes it from more general approaches to the
formal verification of software, which typically rely on human-generated proofs. Furthermore, it promotes practicality over soundness, in that it aims to dramatically reduce the number of ''false positives'' (overestimated errors that are not real errors, that is, ESC over strictness) at the cost of introducing some ''false negatives'' (real ESC underestimation error, but that need no programmer's attention, or are not targeted by ESC).
ESC can identify a range of errors which are currently outside the scope of a type checker, including
division by zero,
array out of bounds,
integer overflow
In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of digits – either higher than the maximum or lower t ...
and
null dereferences.
The techniques used in extended static checking come from various fields of computer science, including
static program analysis,
symbolic simulation,
model checking,
abstract interpretation
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 p ...
,
SAT solving and
automated theorem proving
Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a m ...
and
type checking. Extended static checking is generally performed only at an intraprocedural, rather than interprocedural, level in order to scale to large programs.
Furthermore, extended static checking aims to report errors by exploiting user-supplied specifications, in the form of
pre- and
post-conditions,
loop invariants and
class invariant
In computer programming, specifically object-oriented programming, a class invariant (or type invariant) is an invariant used for constraining objects of a class. Methods of the class should preserve the invariant. The class invariant constr ...
s.
Extended static checkers typically operate by propagating
strongest postconditions (resp.
weakest preconditions) intraprocedurally through a method starting from the precondition (resp. postcondition). At each point during this process an intermediate condition is generated that captures what is known at that program point. This is combined with the necessary conditions of the program statement at that point to form a ''verification condition''. An example of this is a statement involving a division, whose necessary condition is that the
divisor be non-zero. The verification condition arising from this effectively states: ''given the intermediate condition at this point, it must follow that the divisor is non-zero''. All verification conditions must be shown to be false (hence correct by means of
excluded third
In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontradi ...
) in order for a method to pass extended static checking (or "unable to find more errors"). Typically, some form of automated theorem prover is used to discharge verification conditions.
Extended Static Checking was pioneered in ESC/Modula-3 and, later,
ESC/Java
ESC/Java (and more recently ESC/Java2), the "Extended Static Checker for Java," is a programming tool that attempts to find common run-time errors in Java programs at compile time. The underlying approach used in ESC/Java is referred to as extend ...
. Its roots originate from more simplistic static checking techniques, such as static debugging
or
Lint (software) and
FindBugs
FindBugs is an open-source static code analyser created by Bill Pugh and David Hovemeyer which detects possible bugs in Java programs. Potential errors are classified in four ranks: (i) scariest, (ii) scary, (iii) troubling and (iv) of concern ...
. A number of other languages have adopted ESC, including Spec# and
SPARKada and
VHDL VSPEC. However, there is currently no widely used software programming language that provides extended static checking in its base development environment.
See also
*
Java Modeling Language (JML)
References
Further reading
*
*
*
*
*
*
*
*
{{DEFAULTSORT:Extended Static Checking
Static program analysis tools
Formal methods