This being a book on software testing, one may wonder why we need to talk about program correctness. There are several reasons and some of them are as follows:
We let space S be the set of natural numbers and let R be the following specification on S:
We consider the following candidate programs (represented by their functions on S), and we ask the question: which of these programs is correct with respect to R?
We submit:
As a second example, we let space S be defined by two integer variables x and y, and we let R be the following relation (specification) on S:
We consider the following candidate programs (written in C-like notation), and we ask the question: which of these programs is correct with respect to R?
p1: {while (y<>0) {x=x+1; y=y-1;}}.
p2: {while (y>0) {x=x+1; y=y-1;}}
p3: {if (y>0) {while (y>0) {x=x+1; y=y-1;}
else {while (y<0) {x=x-1; y=y+1;}}
Before we make judgments on the correctness of these programs, we compute their respective functions:
We submit:
As a third example, we consider the following program on space S defined by integer variables x and y:
p: {while (y<>0) {x=x+1; y=y-1;};}
and we consider the following specifications:
As a reminder, consider that the function of program p is:
Whence we submit:
We are now ready to cast the intuition gained through these examples into formal definitions.
Note that partial correctness provides for the correct behavior of the program only whenever the program terminates; so that a program that never terminates is, by default, partially correct with respect to any specification. Despite this gaping weakness, partial correctness is a useful property that is often considered valuable in practice.
We conclude this section with a simple proposition, which stems readily from the definitions.
In this section, we introduce a number of propositions pertaining to correctness, partial correctness, and termination; for the sake of readability, we do not prove them, but comment on their intuitive significance.
As we remember, the refinement ordering was introduced in Chapter 4 to rank specifications in terms of strength, reflecting how demanding a specification is or how hard a specification is to satisfy. As we recall, this ordering plays a role in determining whether a given specification is complete with respect to a completeness property and whether a given specification is minimal with respect to a minimality property. Surprisingly, or on second thought not surprisingly, the same refinement ordering plays an important role in defining program correctness, as the following propositions provide. For the sake of simplicity, we restrict our attention to deterministic programs (i.e., programs that produce a uniquely determined final state for any given initial state).
Function P refines relation R if and only if it has a larger domain that R and for all elements s in the domain of R, the pair (s,P(s)) is an element of R; this is exactly how we defined (total) correctness in Section 5.1.
Unlike with total correctness, in partial correctness P does not have to satisfy R for all initial states in the domain of R; rather it suffices that it satisfies R for elements of the domain of R for which p terminates normally (whence the term PL). Note that if we take P=Ø (i.e., program p fails to terminate for all initial states), then this condition is satisfied.
Relation RL has the same domain as relation R, but because it assigns all the elements of S to any element of the domain of R, it imposes no condition on the final state; this is exactly what termination is about.
We conclude this section by revisiting the definition of refinement: so far we have interpreted the refinement to mean that a specification is stronger than another, more demanding than another, and so on. There is a simple way to characterize refinement, now that we have defined correctness; it is given in the following proposition.
Isn’t the essence of being a stronger specification to admit fewer correct programs? Any program that is correct with respect to the stronger/more demanding/more refined specification is necessarily correct with respect to the weaker/less demanding/less refined specification. The necessary condition of this Proposition is a mere consequence of the transitivity of the refinement ordering: if a program p is correct with respect to R, then its function P refines R; since R refines R′, then a fortiori P refines R′, hence p is correct with respect to R′.
Whereas in Section 5.1 we introduced definitions of correctness and in Section 5.2.1 we introduced propositions that formulate correctness in terms of refinement, in this section we introduce propositions that formulate correctness in terms of set theoretic formulae. In practice, these are more tractable than either the definitions or the refinement-based characterizations.
Interpretation of this formula: The set dom(R) is the set of initial states for which program p must behave as R mandates. The set is the set of initial states for which program p does behave as R mandates (see Fig. 5.1 for an illustration). Program p is correct with respect to specification R if and only if these two sets are identical.
Interpretation of this formula: The set is the set of initial states for which program p behaves as R mandates (see Fig. 5.1 for an illustration). The set is the set of states for which program p terminates and specification R has a requirement. Program p is partially correct with respect to specification R if and only if it behaves according to R whenever it terminates.
This condition simply means that dom(R) is a subset of dom(P).
As an illustration of the propositions given in the previous section, we revisit the examples of Section 5.1 and check the formulas of these propositions to ensure that we reach the same conclusions. We consider the specification and the candidate programs of the first example:
The following table shows, for each candidate program P, the values of , dom(R), dom(P), and the correctness property of P: total correctness (TC), partial correctness (PC), termination (T), or none (N).
Candidate | TC | PC | T | N | |||
P1 | {0,1,2,3} | {0,1,2,3} | {0,1,2,3} | ||||
P2 | {0,1,2,3} | {0,1,2,3} | {0,1,2,3,4,5,6} | ||||
P3 | {0,1,2} | {0,1,2,3} | {0,1,2} | ||||
P4 | {0,1,2} | {0,1,2,3} | {0,1,2,4,5,6} | ||||
P5 | {0,1,2} | {0,1,2,3} | {0,1,2,3} | ||||
P6 | {0,1,2} | {0,1,2,3} | {0,1,2,3,4,5,6} | ||||
These are indeed the conclusions we had reached earlier for the first example. For the second example, we list the specification and programs, then we draw the same table.
Candidate | , | TC | PC | T | N | ||
P1 | S | ||||||
P2 | S | S | |||||
P3 | S | S | S | ||||
These are indeed the conclusions we had reached earlier for the second example. For the third example, we had a single program and many specifications, which we present below:
p: {while (y<>0) {x=x+1; y=y-1;};}
We remember that the function of program p is , whence the domain of P is ; for each specification R we write, in the table below, the values of , dom(R), and dom(P), then make a judgment about the correctness properties of P with respect to the specification in question.
Specification | , | TC | PC | T | N | ||
R1 | S | ||||||
R2 | |||||||
R3 | |||||||
R4 | |||||||
R5 | |||||||
R6 | |||||||
R7 | S | ||||||
All the formulas of correctness we have seen so far have an important attribute in common: They define correctness by an equation that involves the function of the candidate program as well as the specification that the program is judged against. In order to use any of these formulas, we need to begin by computing the function of the program. This approach raises two problems: First, computing the function of a program is very complex and error-prone and does not lend itself to automation because it depends (to capture the function of iterative loops) on inductive arguments that are virtually impossible to codify; second, computing the function of a program in all its detail may be wasteful if the specification refers to only partial functional attributes of the program.
For the sake of illustration, consider the following program p on natural variables n, f, k:
{natural n, f, k;
f=1; k=1; while (k!=n+1) {f=f*k; k=k+1;}}
and consider the following specifications
According to the foregoing definitions and propositions, in order to prove that program p is correct with respect to any of the proposed specifications, we must first compute the function of p. Given that the specifications refer to very partial aspects of the function of the program, it seems very wasteful to have to compute the function of the program in all its minute detail before we can prove correctness.
In this section, we present an alternative verification method that is commensurate with the complexity of the specification, and proceeds by recursive descent on the control structure of the program at hand. The core formula of this method takes the form of a triplet:
Where p is a program or program part and φ and ψ are assertions on (variables of) the space of the program. This formula is interpreted as follows: If φ holds prior to execution of program p and p executes and terminates, then ψ holds after the execution of p. Such formulas are called Hoare formulas; φ is called a precondition and ψ is called a postcondition to program p.
As a way to nurture the reader’s understanding of this notation, we give below a number of formulas, which we want to consider as valid (in reference to the definition above); we let x and y be integer variables and we classify the sample formulas by the control structure of the program p.
Assignment statement:
Sequence statement:
Conditional statement:
Alternation statement:
Iteration:
We leave it to the reader to ponder, by reference to the definition of this notation, why each one of the formulas above is valid. So far we have established the validity of these formulas by inspection, in reference to the definition. For larger and more complex programs, this may not be practical; in the next section, we introduce a deductive process that aims to establish the validity of complex formulas by induction on the complexity of the program structure.
An inference system is a system for inferring conclusions from hypotheses in a systematic manner. Such a system can be defined by means of the following artifacts:
An inference in an inference system is an ordered sequence of formulas, say v1, v2, …, vn, such each formula in the sequence, say vi, is either an axiom or the conclusion of a rule whose premises appear prior to vi, that is, amongst . A theorem of a deductive system is any formula that appears in an inference.
In this section, we propose an inference system that enables us to establish the validity of Hoare formulas by induction on the complexity of the program component of the formulas. To this effect, we present in turn, the formulas, then the axioms, and finally the rules.
Assignment Statement Rule: We consider an assignment statement that affects a program variable (and implicitly preserving all other variables), and we interpret it as an assignment to the whole program state (changing the selected variable and preserving the other variables), which we denote by s=E(s), where s is the state of the program. We submit the following rule,
Interpretation: If we want ψ to hold after execution of the assignment statement, when s is replaced by E(s), then ψ(E(s)) must hold before execution of the assignment; hence the precondition φ must imply ψ(E(s)).
Sequence Rule: Let p be a sequence of two subprograms, say p1 and p2. We have the following rule,
Interpretation: if we can find an intermediate predicate int that serves as a postcondition to p1 and a precondition to p2, then the conclusion is established.
Conditional Rule: Let p be a conditional statement of the form:
if (condition) {statement;}.
We have the following rule,
Interpretation: The two premises of this rule correspond to the two execution paths through the flowchart of the conditional statement (Fig. 5.2).
Alternation Rule: Let p be an alternation statement of the form:
if (condition) {statement;} else {statement;}.
We have the following rule,
Interpretation: The two premises of this rule correspond to the two execution paths through the flowchart of the conditional statement (Fig. 5.3).
Iteration Rule: Let p be an iterative statement of the form:
while (condition) {statement;}.
We have the following rule,
Interpretation: The first and second premises establish an inductive proof to the effect that predicate inv holds after any number of iterations. The third premise provides that upon termination of the loop, the combination of predicate inv and the negation of the loop condition must logically imply the postcondition. Predicate inv is called an invariant assertion. It must be chosen so as to be sufficiently weak to satisfy the first premise, yet sufficient strong to satisfy the third premise (and the second). See the flowchart below, which highlight the points at which each of the relevant assertions is supposed to hold. Note that inv is placed upstream of the loop condition; hence the loop condition is never part of inv (since upstream of the loop condition we do not know whether t is true or not) (Fig. 5.4).
Consequence Rule: Given a Hoare formula, we can always strengthen the precondition and/or weaken the postcondition. We have the following rule:
Interpretation: This rule stems readily from the definition of these formulas.
Using the proposed axioms and rules, we can now generate theorems of the form {φ} p {ψ}. The question that arises then is: what good does it do us to generate such theorems? What does that tell us about p? The following Proposition provides the answer.
In the following section, we present sample illustrative examples of the inference system presented herein.
We consider the following program on space S defined by variables x and y of type real, and we form a triplet by embedding it between a precondition and a postcondition:
We form the following formula and we attempt to prove that this formula is a theorem of the proposed inference system:
While (y≠0){x=x+1;y=y−1;}
We apply the iteration rule to v, using the invariant assertion . This yields the following three formulas:
We find that v0 and v2 are both tautologies and hence they are axioms of the inference system. We consider v1, to which we apply the sequence rule, with the intermediate assertion . This yields two formulas:
We apply the assignment statement rule to v10 and v11, which yields the following formulas:
We find that v100 and v110 are both tautologies and hence they are axioms of the inference system. This concludes our proof to the effect that v is a theorem, since the sequence
is an inference, as the reader may check: each formula in this sequence is either an axiom or the conclusion of a rule whose premises are to the left of the formula. By virtue of the proposition labeled Proving Partial Correctness, we conclude that program p is partially correct with respect to the following specification:
It may be more expressive to view this inference as a tree structure, where leaves are the axioms and internal nodes represent the rules that were invoked in the inference; the root of the tree represents the theorem that is established in the inference (Fig. 5.5).
As a second illustrative example, we let space S be defined by three integer variables n, f, k, such that n is nonnegative, and we let program p be defined as:
{f=1; k=1; while (k≠n+1) {f=f*k; k=k+1;};}.
We choose the following precondition and postcondition:
This produces the following formula:
v : {(n = n0)} f=1; k=1; while (k≠n+1) {f=f*k; k=k+1;}
{f = n0!}.
We apply the sequence rule to v, using the intermediate predicate . This yields
while (k≠n+1) {f=f*k; k=k+1;}
{f = n0!}.
We apply the sequence rule to v0, using the intermediate assertion . This yields
We apply the assignment statement rule to v00 and v01. This yields respectively:
We find that v000 and v010 are both tautologies and hence axioms of the inference system. We now focus on v1, to which we apply the iteration rule, with the invariant assertion . This yields:
We find that formula v10 is a tautology, since the factorial of 0 is 1, and we find that formula v12 is a tautology, by simple substitution. Hence we now focus on v11, to which we apply the sequence rule, with the intermediate assertion . This yields:
Application of the assignment statement rule to v110 and v111 yields:
We find that v1100 and v1110 are both tautologies and hence axioms of the inference system. This concludes our proof; we leave it to the reader to verify that the following sequence is an inference in the proposed inference system:
Because v is a theorem, we conclude that program p is partially correct with respect to the following specification (formed from the precondition and postcondition of v):
As a third example, we consider the following GCD program on positive integer variables x and y:
{while (x≠y) {if (x>y) {x=x–y;} else {y=y–x;};},
and we consider the following precondition/postcondition pair:
We form the following formula:
We apply the iteration rule to v with the following invariant assertion: . This yields:
We find that v0 and v2 are tautologies and hence axioms of the inference system. We focus on v1, to which we apply the alternation rule, which yields:
We apply the assignment statement rule to v10 and v11, which yields:
We find that both of these formulas are tautologies and hence axioms of the inference system. This concludes the proof that v is a theorem; hence program p is partially correct with respect to
Among the most important lessons to retain from this chapter, we cite:
{z=0; while (y≠0) {y=y–1; z=z+x;};}
This program computes the product of x and y into z. Write an appropriate precondition and postcondition for this program and prove the resulting formula; compute the binary relation that stems from the precondition/postcondition pair and infer a partial correctness property of the program.
{f=1; while (n≠0) {f=f*n; n=n–1;};}
Write an appropriate precondition and postcondition that capture the function of this program, and prove the resulting formula; compute the binary relation that stems from the precondition/postcondition pair and infer a partial correctness property of the program.
{z=0; while (y≠0) {if (y%2==0) {x=2*x; y=y/2;} else {z=z+x; y=y–1;};};}.
{x=0; k=0; while (k<N) {x=x+a[k]; k=k+1;};}.
{k=N–1; a[0]=x; while (a[k]≠x) {k=k–1;}; f=(k>0);}
The definitions and propositions pertaining to program correctness are due to Linger et al. (1979) and Mills et al. (1986) or inspired from Mili et al. (1994). The proof method that is presented in Section 5.3.2 is due to C.A.R. Hoare (1969).