Case-reduced verification condition generation system and method using weakest precondition operator expressed using strongest postcondition operators

[0002] This application claims priority to U.S. provisional patent application No. 60/218,305, filed Jul. 14, 2000, entitled “Case-reduced Verification Condition Generation System And Method,” which is hereby incorporated by reference in its entirety.

[0003] The present invention relates generally to tools that automatically verify, using static checking techniques, the correctness of a computer program with respect to predefined criteria, and particularly to a tool that derives verification conditions from a computer program source code. In particular, the present invention relates to the simplification of the verification condition to avoid repeated evaluation by a theorem prover of a subexpression in the verification condition that corresponds to a portion of the computer program that is common to two or more alternative paths through the program.

[0004] The purpose of a computer program verification system is to analyze a given computer program to determine whether or not it has certain desirable properties. Verification systems can also be used to analyze hardware components. A typical verification system works by generating a verification condition from a given behavioral design, and then evaluating the verification condition with a theorem prover. The verification condition is a mathematical formula. Ideally this formula is valid if and only if the original source program is free of certain kinds of errors.

[0005] The verification condition (VC) is analyzed by a theorem prover that attempts to prove the “theorem” that the VC is true. When the theorem prover is unable to prove that the VC is true, it preferably provides a counter-example, which specifies at least one condition for which the VC is false. For example, if the VC is x+y>x, then a counter-example is y≦0.

[0006] In general, theorem proving is difficult and may consume exorbitant computer resources. Many verification conditions are not solvable in general. Also, the size of the VC may grow exponentially with the size of the computer program from which it is derived. Another circumstance is that two mathematical formulae may be logically equivalent but one may be harder to prove than the other. Overall, significant computer resources may be expended in theorem proving, even when the computer program corresponding to the VC is not unusually complex or long.

[0007] The theory behind VC generation and theorem proving derives from that branch of mathematics known as Logic. Principles underlying VC generation also underlie the general theory of the construction of computer programs and the operation and implementation of programming languages. A theoretical treatment of VC generation in the prior-art can be found in E. W. Dijkstra, A Discipline of Programming,Prentice-Hall, (1976); and in C. A. R. Hoare, “An Axiomatic Basis for Computer Programming,” Communications of the Association for Computing Machinery,12(10):576-83 (October 1969), both of which are hereby incorporated by reference as background information.

[0008] Several program verification systems exist in the prior art. Examples include: A Program Verifier,J. King, Ph.D. thesis, Carnegie-Mellon University (1969) in which a system, called Effigy, used Symbolic execution to generate verification conditions; L. P. Deutsch, An Interactive Program Verifier,Ph.D. thesis, Univ. Calif., Berkeley, (1973), the first program verifier to use an interactive theorem prover; D. Luckham and N. Suzuki, Automatic Program Verification V: verification-oriented rules for arrays, records and pointers,Stanford Artificial Intelligence Laboratory Memo AIM-278, (March 1976). The last of these, the Stanford Pascal Verifier, used “Hoare Logic” to generate VC's.

[0009] A major contribution to the intensivity of effort in applying the theorem prover is in case-splitting situations, i.e., where choices arise in the program. For example, an “if . . . then . . . else” construct in a computer program provides two alternative, i.e., a pair of, conditional program execution paths, more generally called a choice. Other examples of program constructs that result in a choice are a loop with a loop termination condition, and a conditional branch. All of the aforementioned systems produced VC's with enormous numbers of cases for programs containing a sequential composition of a significant number of alternative choice constructs.

[0010] When a computer program has the structure (S₁ S₂) S₃(wherein the operator represents choice), the corresponding VC generated by methods in the prior art will normally include two instances of an expression corresponding to S₃, wherein one instance is combined with an expression corresponding to S₁and another instance is combined with an expression for S₂. More generally, each choice in a computer program will approximately double the size of the resulting VC because of the duplication of S₃, and will thereby double the amount of work to be performed by the theorem prover to evaluate the VC. Thus, the presence of multiple choices within a computer program will typically cause the complexity of the corresponding VC to increase exponentially when using the methods of the prior art.

[0011] Therefore it is a goal of the present invention to generate a VC that is easier for the theorem prover to evaluate and which is smaller in size than the normal VC for the computer program for which the VC is being generated. None of the aforementioned program verification systems featured a solution to the problem, as addressed by the present invention.

[0012] The present invention relates to the generation of a verification condition (VC) from a computer program source code that comprises a collection of program statements.

[0013] Accordingly, the present invention involves a method of generating a verification condition for a computer program that comprises a collection of program statements and that contains a pair of conditional program execution paths preceding a control join point and an expression following the control join point, the method comprising: applying at least one precondition operator to the computer program to produce a verification condition which includes a single instance of a subexpression derived from the expression following the control join point, wherein, while applying the at least one precondition operator to the computer program, a label is given to a value, at the control join point, of a variable that is modified on at least one of the conditional program execution paths.

[0014] Although a computer program can be transformed directly into a VC and take advantage of the benefits of the present invention, the overall process is facilitated by introducing an intermediate step, whereby the computer program is first converted into an intermediate form comprising “guarded commands.” The preferred input to the VC generator is then a set of guarded commands. In principle, a program written in any computer language can be converted this way.

[0015] In a preferred embodiment, the VC generation algorithm is the computation of a weakest precondition. In one embodiment, the weakest precondition of the set of guarded commands is computed and assignment commands (which assign values to variables) are removed from the program through use of the “dynamic single assumption” technique that transforms assignment commands into program assumptions. In another embodiment, the weakest precondition is expressed in terms of strongest postconditions. The commonality between the embodiments is that labels are introduced for the values of variables at control join points and that duplication or near duplication in the VC of subexpressions derived from the expression following the control join point is avoided.

[0016] The present invention includes a method of generating a verification condition for a computer program that comprises a collection of program statements and that contains a pair of conditional program execution paths preceding a control join point and an expression following the control join point, the method comprising: when the program statements in the computer program include at least one assignment statement, transforming the at least one assignment statement into an assume command, wherein the transforming includes mapping a variable that is assigned a value by the at least one assignment statement into an expression denoting a value of the variable after the at least one assignment statement; and applying at least one precondition operator to the computer program to produce a verification condition which includes a single instance of a subexpression derived from the expression following the control join point, wherein, while applying the at least one precondition operator to the computer program, a label is given to a value, at the control join point, of a variable that is modified on at least one of the conditional program execution paths. A method according to the present invention also preferably comprises passing the verification condition to a theorem prover and determining whether or not the verification condition is valid.

[0017] In a preferred embodiment, the method of the present invention additionally comprises expressing the weakest precondition operator in terms of at least one strongest postcondition operator.

[0018] Accordingly the present invention additionally comprises a computer readable medium for use in conjunction with a computer system, the computer readable medium comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising: instructions for generating a verification condition for a computer program that comprises a collection of program statements and that contains a pair of conditional program execution paths preceding a control join point and an expression following the control join point; instructions for determining when the program statements in the computer program include at least one assignment statement, and, instructions for transforming the at least one assignment statement into an assume command, wherein the transforming includes mapping a variable that is assigned a value by the at least one assignment statement into an expression denoting a value of the variable after the at least one assignment statement; and instructions for applying at least one precondition operator to the computer program to produce a verification condition which includes a single instance of a subexpression derived from the expression following the control join point, wherein, while applying the at least one precondition operator to the computer program, a label is given to a value, at the control join point, of a variable that is modified on at least one of the conditional program execution paths.

[0019] The present invention also includes a computer readable medium for use in conjunction with a computer system, the computer readable medium comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising: instructions for generating a verification condition for a computer program that comprises a collection of program statements and that contains a pair of conditional program execution paths preceding a control join point and an expression following the control join point; instructions for applying at least one precondition operator to the computer program to produce a verification condition which includes a single instance of a subexpression derived from the expression following the control join point, wherein, while applying the at least one precondition operator to the computer program, a label is given to a value, at the control join point, of a variable that is modified on at least one of the conditional program execution paths.

[0020] The present invention further includes a computer readable medium that comprises instructions for computing at least one precondition operator in terms of a weakest precondition operator expressed by at least one strongest postcondition operator.

[0021] The present invention additionally includes an apparatus for generating a verification condition for a computer program that comprises a collection of program statements and that contains a pair of conditional program execution paths preceding a control join point and an expression following the control join point, the apparatus comprising: a memory containing the computer program, an operating system and at least one processor configured to execute mathematical operations on the computer program, wherein the computer processor: when the program statements in the computer program include at least one assignment statement, transforms the at least one assignment statement into an assume command, and includes mapping a variable that is assigned a value by the at least one assignment statement into an expression denoting a value of the variable after the at least one assignment statement; and applies at least one precondition operator to the computer program to produce a verification condition which includes a single instance of a subexpression derived from the expression following the control join point, wherein, while applying the at least one precondition operator to the computer program, a label is given to a value, at the control join point, of a variable that is modified on at least one of the conditional program execution paths.

[0022] The present invention also includes an apparatus for generating a verification condition for a computer program that comprises a collection of program statements and that contains a pair of conditional program execution paths preceding a control join point and an expression following the control join point, the apparatus comprising: a memory containing the computer program, an operating system and at least one processor configured to execute mathematical operations on the computer program, wherein the computer processor: applies at least one precondition operator to the computer program to produce a verification condition which includes a single instance of a subexpression derived from the expression following the control join point, wherein, while applying the at least one precondition operator to the computer program, a label is given to a value, at the control join point, of a variable that is modified on at least one of the conditional program execution paths.

[0023] The apparatus of the present invention also includes a computer processor that computes at least one precondition operator in terms of a weakest precondition operator expressed as at least one strongest postcondition operator.

[0024] Additional objects and features of the invention will be more readily apparent from the following detailed description and appended claims when taken in conjunction with the drawings, in which:

[0025] FIG. 1 is a block diagram of a programmed general purpose computer according to an embodiment of the Verification Condition Static Checking system.

[0026] FIG. 2 is a flow chart of a method of determining whether a specified computer program satisfies a set of program conditions including the step of generating a simplified verification condition according to the method of the present invention.

[0027] FIG. 3 is a schematic view of names assigned to a variable, x, on different branches of a program following a choice.

[0028] FIG. 4 is a flow chart of a method of determining whether a specified computer program satisfies a set of program conditions including a two stage process of generating a simplified verification condition according to a preferred embodiment of the method of the present invention.

[0029] FIG. 5 is a flow chart of a method of determining whether a specified computer program satisfies a set of program conditions including a process of generating a simplified verification condition expressed as strongest post conditions according to a second embodiment of the method of the present invention.

[0030] The present invention provides a method of generating a VC that is simpler and easier for a theorem prover to evaluate than a VC generated using methods in the prior art. The VC generated using the present invention takes advantage of situations where a single evaluation of an expression by the theorem prover may be valid for multiple computational contexts.

[0031] The VC has a branching structure that governs its evaluation by the theorem prover. By reducing the number of branches in accordance with the present invention, repeated evaluation of various subexpressions is eliminated or reduced. In some situations, repeated evaluations of a subtree, representing a postcondition for two conditional program execution paths of the computer program, may nevertheless be required because of differences in the assumptions that apply to evaluation of the subtree for each of the alternate execution paths. But in many situations the theorem prover will need to evaluate a subtree corresponding to the postcondition only once.

[0032] As used herein, a postcondition and a precondition are both examples of predicates. As understood by one skilled in the art, a predicate is a function whose result represents the truth or falsehood of some condition. A predicate transformer is a characterization of the semantics of a program or program statement as a function from predicates to predicates.

[0033] Referring to FIG. 1, the present invention may be implemented using a programmed general-purpose computer system 100. The computer system 100 includes: (a) one or more data processing units (CPU's) 102; (b) memory 106, which will typically include both high speed random access memory as well as non-volatile memory (such as one or more magnetic disk drives); (c) a user interface 108; (d) a network or other communication interface 110 for communicating with other computers as well as other devices; and (e) one or more communication busses 104 for interconnecting the CPU(s) 102, memory 106, user interface 108, and network interface 110.

[0034] The computer system's memory 106 stores procedures and data, typically including:

[0035] an operating system 112 for providing basic system services;

[0036] application programs 114, such as user level programs for viewing and manipulating images;

[0037] one or more authoring tools 116, for assisting with the writing of computer programs; and

[0038] an annotated computer program 118 that comprises a collection of program statements, representing a computer program to be analyzed by a verification condition static checking module 120. It is understood that the system and method of the present invention is also applicable to fragments of computer programs, for example, individual or several of the procedures, functions, subroutines, modules, or applets of which a computer program may be comprised.

[0039] The verification condition static checking module 120 preferably includes:

[0040] a verification condition generator 122, which generates as its output a verification condition 124;

[0041] a theorem prover 126 that analyzes the verification condition and optionally generates one or more counterexamples 128 when it is unable to prove the verification condition; and

[0042] an analysis module 130 that performs post processing on the counterexamples 128 generated by the theorem prover 126, and when an error or potential error in the computer program 118 is detected, produces one or more error messages 132.

[0043] A preferred embodiment of the method of the present invention is shown in FIG. 2. Referring to FIG. 2, the annotated computer program 118 to be checked is first converted into an intermediate form of the program to facilitate analysis (step 140). In a preferred embodiment, the intermediate form utilizes guarded commands that are the basis of a particularly simple programming language. Thereafter, the intermediate form of the program is processed by the verification condition generator 122. To facilitate the work of the theorem prover, the intermediate form of the program is transformed in accordance with the present invention (step 142). During the transformation step 142, labels are introduced into the VC that correspond to values of program variables at control join points. In contrast, methods in the prior art only introduce labels that correspond to the values of variables at the beginning or end of the program. The verification condition 124 produced by the VC generator according to the methods of the present invention is simplified in that certain subexpressions derived from the expressions that follow control join points are present only once in the VC. Such a simplified VC is referred to herein as a “case reduced verification condition.”

[0044] The verification condition 124 for the program is represented as a “logical equation”. In a preferred embodiment, the logical equation that is the verification condition 124 is expressed as a “weakest precondition”. The logical equation is typically represented as a tree of sub-expressions. Various subsets and combinations of the sub-expressions must be conclusively proved to be true for all possible program conditions.

[0045] The VC is passed to the theorem prover 126 whose job is to evaluate the sub-expressions of the verification condition, for all possible program conditions, to determine which ones (if any) it cannot conclusively prove to be true. Failure to prove sufficient combinations of sub-expressions to always be true means that one or more of the pre-conditions or postconditions required for proper operation of the program is not satisfied, or may potentially not be satisfied.

[0046] It is noted that the theorem prover may not be able to prove the truth of a sub-expression, even though it is in fact true, in which case a false error report may be generated. However, the operation of the theorem prover and the generation of such false error reports are outside the scope of the present document. When it is unable to prove the truth of the VC, the theorem prover ideally produces one or more counter-examples 138 that are processed by an analysis module 130 and output as error messages 132.

[0047] FIG. 3 illustrates the flow of control through a program that contains a control join point. The single execution trace 300 precedes a branch point 302. At branch point 302, one of two conditional program execution paths 304 and 306 are possible. These paths join one another at control join point 308, coalescing into a single path 310 that proceeds to execute expressions following control join point 308. In general, for any computer program, the (normal) termination of the program is a control join point. The methods of the present invention have greatest utility where they are applied to a program in which an expression or a collection of commands follows a control join point.

[0048] In this document, the term “expression” will be used, in different contexts, to mean two distinct things. First, an “expression” may be a string (such as x+1) representing the computation of a value to be stored in a variable, or used as the basis for making a decision. Secondly, an “expression” may be what is more formally called a “statement” in a program, where a statement may include a sequence or other combination of program statements (or commands). The symbol S is often used to represent a “statement” (herein called an expression), where the statement may include many lines of program code, each of which may in turn be called a statement. Taken to its natural limit, S may represent an entire computer program. Thus, the term “expression” is used to mean a sequence, collection or combination of one or more commands (or program statements). Similarly, the term “command” can mean both a single command and a sequence, collection or combination of commands.

[0049] In a preferred embodiment of the present invention, the intermediate form into which the computer program 118 is converted, is composed of guarded commands. The methods of the present invention are not limited to using intermediate forms that are based on guarded commands. Guarded commands are particularly advantageous because of their simplicity. Guarded commands are a limited set of commands that together comprise a small simplified computer programming language. The embodiment of the present invention described herein is based on Dijkstra's guarded commands (see E. W. Dijkstra, A Discipline of Programming,Prentice-Hall, (1976)). Other examples of guarded commands derived from Dijkstra are described elsewhere (see G. Nelson, “A Generalization of Dijkstra's Calculus”, ACM Transactions on Programming Languages and Systems,11(4): 517-561, (1989); and M. S. Manasse and C. G. Nelson, “Correct Compilation of Control Structures,” Bell Labs Technical Memorandum,(Sep. 9, 1984), both of which are incorporated herein by reference).

[0050] In Table 1, hereinbelow, are the “guarded commands” used in the present invention, some of which are derived from Dijkstra. The conversion of Java programs to the set of guarded commands described in Table 1 is described elsewhere in: K. R. M. Leino, J. B. Saxe and R. Stata, “Checking Java programs via guarded commands,” SRC Technical Note1999-002, Compaq Computer Corporation, May 21, 1999, also available in Formal Techniquesfor Java Programs,Workship proceedings, Ed. B. Jacobs, et al., Technical Report 251, Femuniversitäit Hagen, 1999, incorporated herein by reference.

[0051] In Table 1, x is a variable; e is an expression; and S is a statement.

[0052] Accordingly, the term “guarded command” as used herein will be taken to mean those commands set forth in Table 1, though it is understood by one of skill in the art that the methods of the present invention are not limited to those commands but are applicable to Dijkstra's original commands or many other variations thereof.

[0053] The guarded command, “var x in S₁end” is similar to the use of a temporary variable in Java as might find application in, for example, swapping the values of two variables.

[0054] The context in which “assert e” finds application is in the annotation of programs. For the purposes of generating the verification conditions, annotations other than those required by the compiler can be introduced into the program. The purpose of “assert” is to introduce proof obligations into the verification condition. Proof obligations are conditions that permit the theorem prover to test various aspects of the operation of the program. One example is in the checking for null pointer dereferences. The annotation

[0055] assert x not null

[0056] represents a condition that the theorem prover checks. If there is a possibility that x is null, that possibility is encoded within the verification condition. Other examples of annotations include: a division operation wherein an “assert” is used to check whether the divisor is ever zero; and an array boundary checker.

[0057] Implied annotations are annotations that the programmer does not need to explicitly include in a program because the implied annotations are automatically assumed to apply to all instances of certain program constructs. Thus, pointer dereference instructions may be assumed to include an implied annotation asserting that the pointer to be dereferenced is not null, and division instructions may be assumed to include an implied annotation asserting that the divisor is not equal to zero.

[0058] Details of the commands “raise” and “bang” (“!”) are discussed hereinbelow when considering exceptions.

[0059] The control constructs in Table 1 hereinabove do not include any constructs for introducing loops into the program. This can be explained as follows. All treatments of loops by automatic program verification systems ultimately work by rewriting a program with loops into some other semantically equivalent program without loops. (Several possible ways of doing this are explained in Section 3 of Leino et al., “Checking Java programs via guarded commands,” SRC Technical Note1999-002, Compaq Computer Corporation, May 21, 1999, referred to hereinabove). The methods of the present invention are to be applied to a loop-free program that results from some rewriting of this kind.

[0060] As an example illustrating the difference between Dijkstra's guarded commands and those presented here, the translation of an “if . . . else” control construct into guarded commands is presented:

[0061] if(e)

[0062] {S₁}

[0063] else

[0064] {S₂}

[0065] becomes

[0066] (assume e; S₁)(assume e; S₂).

[0067] The “if . . . else” construct has been translated into two choices: an assumption that e is True and an assumption that e is False. In the guarded command form, S₁and S₂are themselves replaced by their respective translations into guarded commands.

[0068] In contrast, in Dijkstra's original guarded command language, the “if . . . else” control construct becomes

[0069] if e→S₁e→S₂fi

[0070] wherein → is a “guard arrow”. Therefore, in the implementation presented here, “assume e” is like a guard.

[0071] A verification condition can be produced by applying a weakest precondition operator to a program. According to methods in the prior art, it is possible to compute the weakest precondition, wp, of a program from the weakest preconditions of its various subparts. By definition, the “weakest precondition” of a program is a logical condition that ensures that the program S executes without error and terminates in a state where a postcondition P is True. Formally, wp(S,P) (also written as wp[S.P] or wp.S.P) is a predicate, or condition, that ensures that program S terminates in a state where P is True. Such a precondition operator is referred to herein as a ‘traditional’ precondition operator.

[0072] As an example, consider the weakest precondition of a “program” that simply increments variable x.

[0073] wp(x :=x+1,x≦10)

[0074] In this case, the weakest precondition is the condition that must be fulfilled such that x has value ≦10 after execution. The weakest precondition is then that x is at least 9, i.e., x≦9.

[0075] The weakest precondition operators of the prior art, which are examples of traditional precondition operators, may be applied to the set of guarded commands used herein. Table 2 shows how the weakest precondition computations of the prior art are used to produce a VC. The variables that result in the VC refer to, i.e., label the values of the corresponding program variables in the initial state of the program.

[0076] As shown in Table 2 hereinabove, for an assignment command, “x gets e,” the weakest precondition, wp.S.P, is the postcondition P with every occurrence of x replaced by e. As an example, for the statement S, given by x :=x+1, (i.e., increment x), subject to the postcondition P, given by x>0, the weakest precondition, wp.S.P, is x+1>0, i.e., x>−1.

[0077] For introduction of a new variable, “var x in S₁end”, i.e., where a new variable x is introduced with scope S₁, the weakest precondition, given by wp.(var x in S₁).P, is simply:

[0078] ∀x: wp.S₁.P.

[0079] I.e., the postcondition, P, holds, no matter what the initial value of x.

[0080] For the choice expression, S₁ S₂, the weakest precondition involves a duplication of the postcondition, P (which is the precondition for the remainder of the program, if any, after the choice expression). This problem of duplication is magnified for the case of combinations of sequence and choice expressions. For example, consider the expression

[0081] S=(S₁S₂); (S₃S₄)

[0082] subject to the postcondition, P. In this case, the resulting expression involves four copies of $\begin{array}{c}\mathrm{wp}·S·P=\mathrm{wp}·\left(S_1•S_2\right)·\left(\mathrm{wp}·\left(S_3•S_4\right)·P\right)\\ =\mathrm{wp}·\left(S_1•S_2\right)·\left(\mathrm{wp}·S_3·P⩓\mathrm{wp}·S_4·P\right)\\ =\mathrm{wp}·S_1·\left(\mathrm{wp}·S_3·P⩓\mathrm{wp}·S_4·P\right)⩓\mathrm{wp}·S_2·\\ \left(\mathrm{wp}·S_3·P⩓\mathrm{wp}·S_4·P\right)\end{array}$

[0083] Similar problems arise for nested choice, meaning that the verification condition is difficult to prove. In such cases, therefore, the resulting verification condition increases exponentially in size with the number of sequentially composed choice operators, and the resulting verification condition will include a corresponding large number of instances of certain postcondition expressions. As a result, the theorem prover will need to repeatedly evaluate the correctness of the repeated postcondition expressions. It is an object of the present invention to simplify the form of the VC so that it contains fewer instances of the postcondition expressions.

[0084] the computation of weakest preconditions by the prior art methods of Table 2 hereinabove introduces labels only for initial values of program variables, which leads to large and difficult VC's. The methods of the present invention, as described hereinbelow, introduces names for the values of program variables at control join points when the variable is modified on at least one of the conditional program execution paths that preceded the control join point, in addition to names for their initial values.

[0085] In a preferred embodiment of the present invention, shown in FIG. 4, a computer program 118 is first converted to guarded command form, step 402. Then, instead of carrying out a weakest precondition computation according to the formulae of Table 2, the transformation from a set of guarded commands to a VC involves two steps. In the first step 404, the guarded command form is transformed into a semantically equivalent form called the passive guarded command form, which does not include assignments, by application of a technique referred to herein as “dynamic single assumption” (DSA). The DSA is also described in, Cormnac Flanagan and James B. Saxe, “Avoiding Exponential Explosion: Generating Compact Verification Conditions,” Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Jan. 17-19, 2001, London, UK., ACM SIGPLAN Notices36(3):193-205, (March 2001), ISBN 1-58113-336-7, which is incorporated herein by reference in its entirety.

[0086] The application of DSA permits the introduction of labels for values of variables at control join points. Implicit in step 404 can be the derivation of “fix-up” and “merge” code, as described hereinbelow. In the second step 406, a precondition operator is applied to the passive form of the guarded commands to give rise to the VC 124. The transformation of commands to DSA form in step 404 is not limited to programs expressed in guarded command form.

[0087] As an illustration, consider the following code fragment, in guarded command form, comprising three assignments:

[0088] x:=1;

[0089] x :=x+1;

[0090] x :=x+1;

[0091] While transforming each assignment statement into an assume command, the variable that is assigned a value by the respective assignment statement is mapped into a new variable corresponding to the assignment statement. Thus, for each assignment, a new variable is introduced, and each assignment in the original code is transformed, in the DSA form, into an assumption about one of the new variables. The DSA form of the code fragment is:

[0092] assume x₁=1;

[0093] assume x₂=x₁+1;

[0094] assume x₃=x₂+1;

[0095] Thus the outcome of using the DSA is to replace every assignment by an “assume,” accompanied by introduction of a new variable name. Such an “assume” can be referred to as a “guarded assume” command.

[0096] Although an “assume” appears similar to an assignment, each “assume” introduced by the DSA transformation can only be carried out once for each variable during the execution of a program. It is to be noted that two alternate conditional execution paths of a program can both contain an “assume” for the same variable.

[0097] The aim of the DSA transformation is to arrive at a program that is free of assignments. For example, if all variable names are different, the “var” statements may be taken to the outside of any control structure and effectively ignored. The resulting program consists entirely of statements comprising the guarded commands “assume”, “assert”, choice () and sequential execution (;). The DSA form of a program may also be referred to as a “passive” form of the program, since it contains no assignment statements.

[0098] In order to transform commands such as guarded commands into DSA form, it is important to keep track of the mappings between variable names in the original program and variable names in the DSA program at each control point. Such a map is referred to as the “context” for a particular control point. The transformation is defined using a function, dsa, that takes two arguments, a command S and a context R for the initial state of S, and produces a pair of results: a new command S′ and a context R′ for the final state of S.

[0099] Accordingly, the DSA of a guarded command, such as x :=e, utilizes a mapping to keep track of variable names. As an example, if e is the expression x+y−z wherein x, y, z are variables in the guarded command form of the program, let R be the mapping

[0100] {x→x₁, y→y₃, z→z₂}.

[0101] Then R(e) is the expression x₁+y₃−Z₂. In general, R(e) is obtained from e by replacing each free occurrence of any variable v by the renaming prescribed for v by R.

[0102] Operationally, the dsa function transforms a command-map pair into another such pair. For example, if R is the mapping {y→y₁} and S is the command

[0103] x :=y

[0104] then dsa(S,R) is the pair

[0105] (assume x₁=y₁, {y→y₁, x→x₁})

[0106] In general, if S is a guarded command and R is a mapping, then dsa(S,R) is a pair of passive commands (called T) and a new mapping (called U), such that

[0107] (1) dom(U), the domain of U, includes (at least) every variable in dom(R) and every variable assigned to in any execution of S; and

[0108] (2) every possible execution of S has at least one “corresponding” possible execution of T, and vice-versa,

[0109] where “corresponding” executions are related as follows:

[0110] (a) for every variable v mentioned in dom(R), the initial value of v in any execution of S is equal to the value of R(v) in any corresponding execution of T;

[0111] (b) corresponding executions of S and T either both go wrong or both complete normally; and

[0112] (c) if a corresponding pair of executions of S and T both complete normally, then for every variable v in dom(U) the final value of v after the execution of S is equal to the value of U(v) in the execution of T.

[0113] By definition, a program “goes wrong” when it is caused to execute a sub-command of the form “assert e” from a state where the expression e evaluates to False. (Note that it is unnecessary to distinguish initial and final values for the execution of T, since T includes no assignment commands.)

[0114] Condition (2)(b) hereinabove means that the verification condition for S will be valid (signifying that S can never go wrong) if and only if the verification condition for T is valid. Because T contains no assignment statements, its VC can be computed by a specialized method (described hereinbelow and summarized in Table 5). The resulting formula will often be smaller, and its validity easier to test, than would be the case for a verification condition for the original command S computed using prior art methods (e.g., as in Table 2).

[0115] The DSA for each guarded command is shown in Table 3 hereinbelow, in which “where” means that the ensuing code defines how the replacement commands (such as D₁and D₂) and the new renaming function(s) (such as R₁, and R₂) are generated. Before applying the DSA rules in Table 3, each subcommand of the form “var x in Send” should be replaced by S_{x :=x′} where the various x′ are chosen to be unique.

[0116] The DSA transformation is applied to any nested set of commands from the inside to the outside. Thus, also, as shown in Table 3, hereinbelow, a pair of conditional program execution paths is converted into a first group of guarded commands coupled by a choice operator to a second group of guarded commands.

[0117] In Table 3, FX is “fix-up” code and merge is a function that generates the “fix-up” code and a merge-map, both of which are defined below. The dsa function is thus an exemplary transformation function having as one of its outputs a modified mapping for application to a subsequent statement of the computer program, such that the modified mapping is based on variable mappings produced by transformation functions on earlier statements of the computer program.

[0118] In general, the outcome of applying dsa to a guarded command S and an initial renaming function R is both a new command S and a new renaming function R. The DSA additionally introduces new variable names.

[0119] The transformation of an assignment statement produces an assume command, such that the transformation includes mapping a variable that is assigned a value by the assignment statement into an expression denoting a value of the variable after the assignment statement.

[0120] In a preferred embodiment, as shown in the first entry in Table 3, for simple assignment expressions it is possible to avoid introducing a new variable. In such cases the mapping just associates the variable x with whatever expression was originally present, i.e., includes a mapping function that maps said variable to the result of applying to the simple expression a mapping corresponding to a program state before the assignment statement, and accompanies it with a no-op, “assume True.” Thus the range of possible mappings for an assignment includes variables to expressions as well as variables to variables. In practice, according to the preferred embodiment of the present invention, whether an assignment is represented by mapping that introduces a new variable name or one which produces a simple substitution, is determined by the complexity of the expression on the right hand side of the assignment.

[0121] The implicit assumption behind the DSA is that, as demonstrated in FIG. 3, although the same variable x starts in R, before a branch point such as 302, it may attain different variable assignments on either of the ensuing conditional program execution paths such as 304 and 306. In FIG. 3, D₁and D₂are collections of one or more executed statements. In FIG. 3, variable x before the branch point attains variable names x₁₀and x₁₁, in each respective branch 304 and 306, both of which need to be merged together after the control join point 308. There is always an implicit control join point at the end of a program.

[0122] As an example, the following program fragment is transformed into DSA, or “passive,” command form:

[0123] dsa((x:=5(x:=6;x:=x+1));assert x>y,(x→x₀,y→y₀))

[0124] where the last term in the parentheses is the mapping given, say, by R. This example comprises a choice () as well as a sequential composition (semi-colon) operator. The DSA's for each command are therefore embedded in the DSA for the program fragment. The form of the DSA translation for each command is presented in Table 3, hereinabove. Inserting the appropriate expressions, the translation is:

[0125] (((assume x₁=5; assume x₄=x₁)(assume x₂=6; assume x₃=x₂+1); assume x₄=x₃));

[0126] assert x₄>y₀.

[0127] In this example, “assume x₄=x₁” in the first parenthesis and “assume x₄=x₃” in the second set of parentheses are respectively “fix-up code.” The purpose of the fix-up code is to synchronize, i.e., produce a consistent labeling of, the variables at the conclusion of each conditional execution path of the choice operator. This is important to achieve if the program fragment is embedded in a larger piece of code that includes commands following the program fragment.

[0128] The fix-up code FX₁and FX₂for merging the renaming functions of two program paths, merge(R₁, R₂), is generated using the merge procedure of Table 4.

[0129] At the top of the merge procedure of Table 4, the fix-up codes are initially null and the mapping set is empty. The for-loop in the merge code iterates over all the variables that are either in the map R₁or the map R₂. For each variable x, if R₁and R₂map x to the same variable name, there is no conflict, no new fix-up code is needed and the return output variable map, R, just maps x to whatever it was mapped to by R₁(or R₂). However, the last else branch within the for loop takes care of the general case where x is mapped differently, i.e., to different variable names, by R₁and R₂. A new name x_nis introduced to represent the value of x at the control join point, and the fix-up code for each path to the join point is extended with an assumption that the value of x at the end of that path is equal to x_n. The extension of the fix-up code is effectively a concatenation operation and could be written in the form:

[0130] FX₁:=FX₁+“; assume x_n=R₁(x)”

[0131] Whatever string FX represented before, i.e., whatever set of assume commands, has now tacked on to it another assume command to cope with the variable in question. Ultimately, the two pieces of fix-up code and the mapping are returned; the result of merge is used in the DSA for a choice operator.

[0132] In a language with assignments, one can think of a program starting in an initial state comprising certain values of its constituent variables and finishing in a final state with certain values of its constituent variables, some of which may be different from the respective initial values.

[0133] By contrast, in a program comprising guarded commands in which assignments are represented by assumes, the starting states are constrained. As an example, consider the program:

[0134] assume x=6;

[0135] This program can only execute with the starting value, x=6. By contrast, the program:

[0136] assume x=6 assume x=7;

[0137] has only two possible starting states. Furthermore, in a language composed of assumes and asserts, certain starting states will result in error-free termination of the program, whereas others will not. The goal of the theorem prover is to ascertain those states that result in, say, a bad assertion. For example, a “good” program (i.e., a program that will execute and terminate correctly) is:

[0138] assume x>1; assert x>0.

[0139] This is a good program because it can only execute in states where x is >1 and the condition that x>0 must therefore be true. By contrast, the following program is not good:

[0140] assume x>0; assert x>1.

[0141] The assertion could be wrong in the case x=1 and the program could go wrong.

[0142] In summary, there may be some states in which a program executes correctly, some in which the program goes wrong, and even some in which the program does not execute at all.

[0143] The absence of assignment statements means that the execution of a passive statement cannot change the program state, and the only effect of such an execution is to choose among the two possible outcomes: normal termination and going wrong. Thus the semantics of a passive statement S can be completely captured by two outcome predicates, one which describes the initial states from which the execution of S may terminate normally, and one which describes states from which the execution of S may go wrong.

[0144] According to the methods of the present invention, two operators are introduced to enable computation of wp for passive commands, namely norm(S) and bad(S):

[0145] norm(S) represents the set of states from which the program S could execute normally;

[0146] bad(S) represents the set of states from which the program S could go wrong.

[0147] For any passive command, S,

[0148] wp(S,True)=bad(S)

[0149] Both bad and norm are precondition-like predicate transformers that are different from traditional precondition operators such as wp and which may only be applied to passive commands. In generating the case-reduced VC according to the methods of the present invention, bad and norm take the place of the conventional wp of the prior art. The present invention also utilizes a special predicate transformer, exc, for the “exceptional” termination of a program, which is further described hereinbelow.

[0150] In the foregoing example, represent the program:

[0151] assume x>0; assert x>1.

[0152] by S. Then:

[0153] norm(S)≡x>1;

[0154] bad(S)≡x>0Λx1.

[0155] The ultimate goal is to generate a good program, S. A program S is free of errors when bad(S)=“False”, i.e., when no states can go wrong. Accordingly, the expressions for the application of the norm and bad operators to each kind of passive guarded command are shown in Table 5, hereinbelow.

[0156] The bad and norm functions shown in Table 5 can be used to compute the weakest precondition of a specified program that is expressed in passive command form.

[0157] As an example of the representation of guarded commands in this way, consider the conversion of the following Java code fragment (which is an instance of the “if . . . else” control construct considered previously):

[0158] {if (b){

[0159] x=x+1;

[0160] }else{

[0161] x=0;

[0162] }

[0163] S (where S is some Java Statement). This simple Java construct becomes, in guarded command form:

[0164] ((assume b; x :=x+1)(assume b; x:=0)); S

[0165] where, as before, S would be represented by its translation into guarded command form. Given the initial mapping {x→x₁}, the transformation to DSA produces the following passive command and another map:

[0166] ((assume b; assume x₂=x₁+1; assume x₄=x₂)

[0167] (assume b; assume x₃=0; assume x₄=X₃)

[0168] );S′

[0169] where S′ is the passive form of S translated using {x→x₄} as the initial mapping. The variable x₄has been introduced to capture the value of x at the control join point. Referring to the preceding expression as D, it may further be written as (D₁D₂); S′. In order to obtain the verification condition, bad(D) is computed. This, according to the foregoing expression, is calculated as the bad of the two expressions, (D₁D₂) and S′, separated by the semi-colon operator. Using the expressions shown in Table 5, bad(D) is computed as follows:

[0170] bad(D)=bad(D₁₂) V (norm(D₁₂)Λbad(S′))

[0171] The first part of this expression is automatically False because in this case there are no asserts in D₁or D₂. Therefore (D₁D₂) never goes wrong in this particular case. This type of simplification is representative of the simplifications that are often (but not always) achievable when generating the VC expression for a program that has been transformed into passive form, wherein Dynamic Single Assumption has been used to transform the guarded commands into passive form.

[0172] After further simplification, bad(D) is evaluated as follows: $\begin{array}{c}\mathrm{bad}\left(D\right)\equiv \mathrm{False}⩔\left(\left(\mathrm{norm}\left(D_1\right)⩔\mathrm{norm}\left(D_2\right)\right)⩓\mathrm{bad}\left(S^{\prime }\right)\right)\\ \equiv ((\mathrm{norm}\left(\mathrm{assume}b\right)⩓\mathrm{norm}\left(\mathrm{assume}{x}_2=x_1+1\right)⩓\\ \mathrm{norm}\left(\mathrm{assume}{x}_4=x_2\right))⩔(\mathrm{norm}\left(\mathrm{assume}⫬b\right)⩓\\ \mathrm{norm}\left(\mathrm{assume}{x}_3=0\right)⩓\mathrm{norm}\left(\mathrm{assume}{x}_4=x_3\right))⩓\mathrm{bad}\left(S^{\prime }\right)\\ \equiv \left(\left(b⩓x_2=x_1+1⩓x_4=x_2\right)⩔\left(⫬b⩓x_3=0⩓x_4=x_3\right)\right)⩓\\ \mathrm{bad}\left(S^{\prime }\right)\end{array}$

[0173] The guarded command expression of the “if . . . else” construct and bad(S′) are present in the final simplification. In other words, the postcondition expression bad(S′) is only present once in the VC expression for the portion of the program comprising the “if . . . else” construct.

[0174] Thus, in a situation whereby a pair of conditional program execution paths is transformed to a first group of guarded commands coupled by a choice operator to a second group of guarded commands, the resulting verification condition comprises:

[0175] a logical OR of a first condition corresponding to the first group of guarded commands and a second condition corresponding to the second group of guarded commands; connected by an implication to a single instance of a post-condition, corresponding to the expression following the control join point, that must always be true after execution of either the first or the second groups of guarded commands.

[0176] As illustrated hereinbelow, this outcome is contrasted with the standard VC expression, obtained according to the methods of the prior art, that contains at least two instances of the postcondition expression. The same code fragment in guarded command form is:

[0177] ((assume b; x :=x+1)(assume b; x:=0)); S

[0178] Representing this expression by G, the conventional application of weakest preconditions to G is given by:

[0179] wp(G,True)≡(b(wp(S,True)_{x :=+1})Λ(b(wp(S,True) _{x :=0})

[0180] To evaluate this expression for the weakest precondition for G, it is necessary to evaluate the weakest precondition of S twice, once each with x=0 and x=x+1. If S is itself a large or complex expression, this is costly. Also if there are further “if . . . else” constructs in the same program, even further copies of S will be included in the VC and thus even further copies of the weakest precondition of S will be required to be evaluated. Furthermore, if x appears in S, the multiple copies will be slightly different from one another. In this example, one copy would have x replaced by x+1 and the other copy would have x replaced by 0. Consequently, memory resources will be taken up by the similar, but not identical, copies.

[0181] In summary, one important aspect of the present invention is that when computing the weakest precondition of an expression such as (S₁S₂); S₃, wherein S₃is a complex expression (e.g., containing a collection of commands and possibly additional choice expressions), an evaluation of the weakest precondition of S₃for both branches of the choice is avoided. The weakest precondition of an expression, such as S₃, that follows the choice operator is a postcondition for the expressions on either side of the choice operator. In particular, the application of the operators bad and norm to statements in passive form leads to a direct simplification that does not arise from the application of the conventional wp operators of the prior art. As an example, consider the program, S:

[0182] (assume e₁assume e₂); assert P

[0183] and let S₁be “assume e₁”, S₂be “assume e₁” and S₃be “assert P.” Using the bad and norm precondition operators of Table 5 hereinabove the weakest precondition is evaluated as follows: $\begin{array}{c}\mathrm{wp}\left(S,\mathrm{True}\right)=⫬\mathrm{bad}\left(S\right)\\ =⫬\mathrm{bad}\left(S_1•S_2\right)⩔\left(\mathrm{norm}\left(S_1•S_2\right)⩓\mathrm{bad}\left(S_3\right)\right)\\ =⫬\left(\mathrm{False}⩔\mathrm{False}\right)⩔\left(\left(e_1⩔e_2\right)⩓⫬P\right)\\ =⫬\left(\left(e_1⩔e_2\right)⩓⫬P\right)\end{array}$

[0184] The final form includes the postcondition P only once. By contrast, using the wp operators of Table 2, hereinabove:

[0185] wp(S, True)=(e₁P)Λ(e₂P)

[0186] This expression contains two instances of P and must be further simplified by application of a rule of logic, viz: the equivalence of the expression (pr)Λ(qr) to (p V q)r. The simplification that was inherent in the application of bad and norm to the passive command form is not automatically produced by the application of the traditional weakest precondition operator, wp.

[0187] A further important advantage of the present invention arises when expressions on either branch of program execution following a choice operator contain assignments. In general, the simplification of an expression of the form (pΛr) V (qΛr) to (p V q)Λr can only be achieved when r is the same on both branches. Assignments are troublesome because they can change the representation of r. Consequently, an expression appearing on both sides of a branch may not be the same on both sides because of the various variable replacements that occur.

[0188] As seen, the weakest precondition of any expression, P, involving an assignment, is:

[0189] wp(x :=e, P)=P_{x :=e}

[0190] Consider the program T:

[0191] ((assume e₁; x=f)(assume e₂; x =g)); assert P.

[0192] According to the application of traditional weakest precondition operators, as shown in Table 2, hereinabove,

[0193] wp(T, True)=(e₁P_{x :=f})Λ(e₂P_{x :=g})

[0194] Since the oc`currences of P with x replaced by f₁and f₂respectively are not identical to one another, the simplification discussed hereinabove cannot be applied. However, simplification becomes possible by eliminating assignments from T using the Dynamic Single Assumption methodology described hereinabove. T is transformed into passive form by translating the assignment commands into “assume” commands according to the expressions in Table 3. The weakest precondition of the passive form of T can then be obtained by application of the bad and norm operators of Table 5, as described in the foregoing example, during which the simplified form in which P appears once is automatically generated.

[0195] Ultimately, then, the embodiment of the present invention described hereinabove eliminates assignment commands to avoid the need to include multiple instances of choice expression postconditions in the VC, thereby avoiding or reducing the repetitious evaluation of effectively identical expressions (i.e., the multiple instances of the choice expression postconditions) by the theorem prover. While the application of DSA does not vitiate all possible occurrences of duplication or near duplication of subexpressions, it relieves the situation in many cases.

[0196] Heretofore, the possibility that a program may terminate exceptionally has been ignored. The guarded commands, introduced in Table 1 hereinabove, are able to model exceptions, but the discussion of DSA and weakest preconditions ignored exceptions. The additional guarded commands, “raise” and “bang” (‘!’) permit exceptions to be modelled, and the VC-generation techniques described hereinabove can be extended to apply to situations where a program terminates exceptionally. Accordingly a modified version of DSA is described, hereinbelow.

[0197] An exceptional outcome leaves the variables in some state but is not the same as an outcome in which the program goes wrong or terminates normally. Exceptions are used to model premature exit conditions from portions of the code. They are used to control the behavior of the program when such a condition arises. A program written in a language such as Java can be written to explicitly handle specified exceptions and therefore the translation of such a program into guarded commands should be able to handle exceptions. Other programming constructs such as an intermediate “return” statement from a procedure (in Java, a “method”), or a “break” statement within a loop are also modeled as exceptions. Table 6 describes how the guarded commands of Table 1 behave when an exception arises

[0198] In order to transform guarded commands into a VC that behaves properly when an exception arises, an alternate, expanded definition of the weakest precondition, wp, is utilized and written as wp (S, N, X), wherein S is a guarded command, N is a normal postcondition and X is an exceptional postcondition. In an equivalent notation, the expanded definition of the weakest precondition is expressed as wp.S.(N, X).

[0199] The weakest precondition is then the weakest predicate, P, such that:

[0200] every normally terminating execution of S that starts in a state satisfying P terminates in a state satisfying N;

[0201] every exceptionally terminating execution of S that starts in a state satisfying P, terminates in a state satisfying X, and

[0202] no execution of S starting in a state satisfying P goes wrong.

[0203] This is an extension of the teachings of Dijkstra to accommodate the possibility of exceptions. Dijkstra's only terminating condition was the normal postcondition, N. (See E. W. Dijkstra, A Discipline of programming, Prentice-Hall (1976).)

[0204] The two guarded commands, “raise,” and “bang” (‘!’) which is the “dual” of the sequential operator; find special application to the modelling of exceptions.

[0205] When using the “raise” operator to model a language with multiple exceptions, an appropriate convention is to record the particular exception raised in a reserved global variable, for example xvar. Thus the raising of a particular exception E is modeled with

[0206] xvar :=E; raise.

[0207] The “bang” operator (as in S₁!S₂) shows how to handle an exception when it is raised, say, by S₁: the bang operator catches it. Here, if S₁terminates exceptionally, then S₂is executed. For example, in a string of sequentially executed statements:

[0208] ( . . . ; raise ; . . . )!S₂

[0209] The statements in parenthesis jump straight to S₂when an exception is raised. If the statements in parenthesis all execute normally, then the program finishes normally, unless S₂itself terminates exceptionally in which case the program can finish exceptionally. Recalling the norm and bad operators, in Table 5 hereinabove, which represent, respectively, the set of states where a specified passive command could execute or terminate normally or badly, the exc operator is now introduced to enable computation of wp for passive commands that could terminate exceptionally. Accordingly,

[0210] exc (S) represents the set of states from which the program, S, could terminate exceptionally.

[0211] The exc operator is used when generating verification conditions.

[0212] Table 7 extends the VC generation technique of Table 5 hereinabove to passive commands that may include exceptions.

[0213] As with bad, the exceptional termination of “assume e” never happens and is therefore False. Furthermore, norm (raise) is False because raise never terminates normally—it automatically raises an exception. Correspondingly, because “raise” always terminates exceptionally, exc (raise) is True.

[0214] The expressions for exc and bad of the sequential composition operator S₁; S₂mirror one another. They have similar forms in which bad and exc occupy corresponding positions. On the other hand, S₁!S₂, which is the dual of S₁; S₂, is such that norm and exc have changed places as well as column positions in Table 7, compared with Table 5.

[0215] It is also possible to derive forms for exceptional termination using “weakest precondition” language. As before, the job of the theorem prover when evaluating the VC of a program is to determine if there are any states for which bad of the program is True, or alternatively to determine whether bad of the program is False for all possible states of the program.

[0216] As shown hereinafter, the technique (given in Table 3 hereinabove) for transforming guarded commands to passive form can be extended to deal with commands that may include exceptions. Before listing the version of the DSA transformation that handles exceptional as well as normal commands, the following three points should be noted.

[0217] First, the DSA transformation presented hereinabove had, as one of its results, a mapping describing the state of the program variables at termination. The result of the modified DSA transformation includes two maps, one describing the state of the program variables upon normal termination and the other describing their state upon exceptional termination.

[0218] Second, in the original guarded command language the only source of control join points was the non-deterministic choice operator .It is also important to handle additional join points, for example, in (S₁; S₂)!S₃where the exceptional outcomes of S₁and S₂join at the start of S₃. The implication for the DSA is additional calls to the merge function.

[0219] Third, since raise has no normal outcome and several commands have no exceptional outcome, it is worthwhile as an optimization to introduce the special map “bottom”, which represents the condition that control cannot reach the relevant control point. Thus “bottom” is used to indicate infeasible code paths.

[0220] A version of DSA embodying these changes is presented in Table 8. In the Table, FN and FX are fix-up codes for, respectively, normal and exceptional termination.

[0221] In Table 8, the last argument of the dsa for the guarded command, x :=e, is “bottom”, meaning that this command never terminates exceptionally so no mapping is required for that outcome.

[0222] Having introduced the special map “bottom” as an optimization, merge(R₁, R₂) can be redefined to take advantage of it, as follows:

[0223] if R₁=bottom then

[0224] return (assume True, assume True, R₂)

[0225] else if R₂=bottom then

[0226] return (assume True, assume True, R₁)

[0227] else

[0228] proceed as in the merge procedure described in Table 4 hereinabove.

[0229] In the above, “assume True” is a no-operation (a “no-op”). Since the fix-up code is only used as the right argument to “;”, and since “S; assume True” is equivalent to “S” for any command S, these cases require no insertion of fix-up code. Such a situation arises frequently, in, for example a long sequence of statements wherein many of the statements do not raise an exception. Therefore, many of the paths through the code have a “bottom” on them and it is not necessary to generate fix-up code.

[0230] In the embodiment described hereinabove, the command to be checked is translated into passive form via the DSA equations of Tables 3 and 8 and then the passive form is translated into a VC via a special version of the weakest precondition computation, using norm, bad, and, if applicable, exc, as described in Tables 5 and 7. Thereby, assignments are removed, and labels are introduced for variables at control join points as well as for their initial values.

[0231] In a second embodiment, a VC is computed directly from the original command using another special version of the weakest precondition computation, in which weakest preconditions of some subcommands are computed in terms of strongest postconditions. Although the equations involved are quite different from one another, both approaches end up labelling the values of targets at control join points, and thereby eliminate or reduce duplication or near duplication of subexpressions that follow the control join point in the eventual VC. In the second embodiment it is not necessary to remove assignments.

[0232] By definition, the strongest normal postcondition, snp, of an expression, S, is such that:

[0233] snp(S, P)≡ the strongest predicate, N, such that every normally terminating execution of S starting from a state that satisfies P, terminates in a state satisfying N.

[0234] That is, if S starts in a state satisfying P, and terminates normally, snp is the most that can be said about the final state.

[0235] Analogously, the strongest exceptional postcondition, sxp(S, P) is given by:

[0236] sxp(S, P)≡ the strongest predicate X such that every exceptionally terminating execution of S starting in a state satisfying P terminates in a state satisfying X.

[0237] The strongest postcondition, then, of an expression is computed according to the following equations, wherein Q and P are predicates, S₁and S₂are commands, x is a variable and e is an expression.

[0238] Strongest normal postconditions:

[0239] snp(assume Q, P)≡QΛP

[0240] snp(assert Q, P)≡QΛP

[0241] snp(raise, P)≡False

[0242] snp(x:=e, P)≡(∃x′:P_{x :=x′}Λx=e_{x :=x′})

[0243] snp(S₁; S₂, P)≡snp(S₂, snp(S₁, P))

[0244] snp(S₁!S₂, P)≡snp(S₁, P)Λsnp(S₂, sxp(S₁, P))

[0245] snp(S₁S₂, P)≡snp(S₁, P) V snp(S₂, P)

[0246] Strongest exceptional postconditions:

[0247] sxp(assume Q, P)≡False

[0248] sxp(assert Q, P)≡False

[0249] sxp(raise, P)≡P

[0250] sxp(x:=e, P)≡False

[0251] sxp(S₁; S₂, P)≡sxp(S₁, P) V sxp(S₂, snp(S₁, P))

[0252] sxp(S₁!S₂, P) sxp(S₂, sxp(S₁, P))

[0253] sxp(S₁S₂, P) sxp(S₁, P) V sxp(S₂, P)

[0254] An example of strongest postconditions is as follows. The strongest normal postcondition of an expression, given by:

[0255] snp(v:=v², v≧3)

[0256] becomes

[0257] ∃v′ such that v′≧3Λv=(v′)²

[0258] That is, it is desired to ascertain what values integer v could end up with when it is squared, subject to the precondition that v is at least 3. The answer is that there is some initial value of v, denoted v′, such that v′ satisfies the precondition and such that the final value of v is the value of the expression with v′ substituted for v. (v′ is rather like a dummy variable, but it is important to ensure that its name does not conflict with other variable names already used.)

[0259] For the simplification of expressions obtained by applying snp to expressions that include assignments, a general rule, the “one point rule” may be used. The one-point rule says that an expression of the form:

[0260] ∀y:y=xP

[0261] or

[0262] ∃y:y=x ΛP

[0263] is equivalent to P_y:=x′

[0264] The approach adopted to case-reduced VC generation in this embodiment, is to compute the weakest precondition of subexpressions in terms of the strongest exceptional and strongest normal postconditions, according to the following relationship, denoted by Equation 1:

[0265] wp(S, N,X)=wp(S, True, True)Λ(∀TT, T′: (snp(S_T:=TT; T′:=TT, TT=T)N_T:=T′)Λ(sxp(S_T:=TT!(T′:=TT; raise), TT=T)X_T:=T′))  (Eq. 1)

[0266] Equation 1 caters for the possibility of exceptional termination of the program. A simpler form of Equation 1 for use with a guarded command language without exceptions is presented as Equation 2:

[0267] wp(S, N)=wp(S, True)Λ(∀TT,T′:(sp(S_T:=TT;T′:=TT, TT=T)N_T:=T′))  (Eq. 2)

[0268] wherein sp is an ordinary “strongest postcondition” operator. In the discussion hereinbelow, Equation 1 is discussed.

[0269] Selective application of Equation 1 to expressions containing the choice operator can lead to the desired simplified forms of verification conditions. In Equation 1, not disclosed in any previous publication, S is a command and N and X are normal and exceptional postconditions. The variables T, TT and T′ are tuples of variables. In particular, T represents the “target variables” of command S, that is a list of all program variables that may be modified by S. (Such variables are those that occur on the left hand sides of assignment commands that are subcommands of S.) An expression such as N_T:=T′ means N with each variable in T replaced by the corresponding adorned variable in T′. T′ and TT represent “adornments” of T, i.e., systematic renamings of the variables in T to new names that do not occur in S, N, or X. An adornment of a variable is also referred to herein as an adorned variable or an inflection of the variable. For example if S contains assignments to variables u and v (and to no other variables), then Equation 1 becomes:

[0270] wp(S, N, X)Λ(∀uu, vv, u′, v′: (snp(S_{u:=uu, v:=vv}; u′:=uu ;v′:=vv, (uu, vv)=(u, v))N_{u:=u′, v:=v′})Λ(sxp(S_{u:=uu, v:=vv}!(u′:=uu ; v′:=v; raise), (uu, vv)=(u, v))X_{u:=u′, v:=v′}))

[0271] wherein uu, vv, u′, and v′ are variable names not already occurring in S, N, or X.

[0272] In both the present embodiment and in the embodiment described hereinabove in which the DSA is employed, a given program variable may have several adornments, corresponding to the labels introduced for the values taken on by the given program variable at various points in the program.

[0273] The approach according to the present embodiment is outlined in FIG. 5. The computer program 118 is optionally converted to guarded command form, step 502, and the strongest postcondition representation of the weakest precondition is computed from the guarded command form, step 504, thereby generating a VC 124. According to this approach, it is not necessary to transform the guarded commands to passive form and there is no need to remove assignments.

[0274] According to this embodiment, labels are introduced for variables by selectively applying Eq. 1 to compute weakest preconditions instead of using the formulae of Table 2 for a traditional weakest precondition operator. Specifically, if Eq. 1 is used for subexpressions of the form (S₁S₂) and if the prior art method is used for all other subexpressions, then this embodiment of the present invention effectively introduces the label T′ for the value at the control join point after (S₁S₂) for each target T.

[0275] The reason that equation 1 is promising for case-reduced VC generation is that it separates the occurrences of S from the occurrences of N and X, placing them on opposite sides of implications (symbols). If S contains choices, then antecedents of the implications (those expressions on the left hand side of the symbol) will end up containing disjunctions, but the postconditions will not be duplicated for each arm of those disjunctions.

[0276] One convenient approach to simplifying an equation such as Equation 1 is to use the following relationship:

[0277] (∀x:x=eP)≡P_x:=e

[0278] Thus, in equation 1, application of this relationship permits the factoring out of TT.

[0279] An acceptable strategy, therefore, for generating a verification condition is to use equation 1 to expand the wp of choices and to use the ordinary wp equations (Table 2) for all other operators (and also for the expression wp( . . . , True, True) on the right hand side of equation 1).

[0280] Thus, the method described herein, by which weakest preconditions are written as expressions that comprise strongest postconditions, has succeeded in avoiding the duplication (or approximate duplication) of postconditions that would result in the methods of the prior art that utilize only weakest preconditions.

[0281] A program whose weakest precondition has been computed in a manner utilizing strongest postconditions, as described hereinabove, is passed to a theorem prover to test its validity as shown in FIG. 1. Savings of resources are consequently gained by avoiding the duplication of expressions following control join points.

[0282] As would be understood by one of skill in the art, the method of transforming a computer program in guarded command form to a weakest precondition in which subexpressions separated by choice operators are expressed as strongest postconditions, is applicable to computer programs written in other guarded command forms as well as other programming languages that are not first converted to guarded command form.

[0283] As an example of this strategy, suppose it is desired to compute the following weakest precondition expression of a choice expression.

[0284] wp((x:=5x:=x+1); K, N, X)

[0285] wherein K is a potentially large command. By applying the ordinary weakest precondition calculation, using the rule for semi-colon, as shown hereinabove in Table 2, the value is:

[0286] wp((x:=5x:=x+1), wp(K, N, X), X)

[0287] Applying the strongest postcondition expression, given above in Eq. 1, wherein S is represented by the choice expression in parenthesis, N is represented by the expression wp(K,N,X) and X is simply X, the only target of the command S is x. To apply Eq. 1, the adorned variables xx and x′ are introduced. Eq. 1 then gives:

[0288] wp(x:=5x:=x+1, True, True)Λ(∀xx, x′: (snp((x:5xx:=xx+1); x′:=xx, xx=x)wp(K,N,X)_x:=x′)Λ(sxp((x:=5xx:=xx+1); x′:=xx, xx=x)X_x:=x′))

[0289] Applying the ordinary weakest precondition formula (Table 2) and simple predicate calculus, the expression

[0290] wp(x:=5x:=x+1, True, True)

[0291] simplifies to True. Also, since there are no occurrences of “raise” in the command (xx: 5xx:=xx+1); x′:=xx, the application of sxp in the antecedent of the second implication reduces to False, and the implication itself reduces to True. Thus, the entire formula reduces to

[0292] (∀xx, x′: snp((xx:=5xx:=xx+1); x′:=xx, xx=x)=>wp(K,N,X)_x:=x′)

[0293] Applying the rules for snp for assignment, the subexpression

[0294] snp((xx:=5xx:=xx+1); x′:=xx, xx=x)

[0295] is simplified to

[0296] x′=xxΛ(xx=5V xx=x+1)

[0297] and therefore the entire formula becomes, on application of the “one-point” rule,

[0298] (∀x′:(x′=5V x′=x+1)=>wp(K,N,X)_x:=x′)

[0299] which has effectively given the label x′ to the value of the program variable x at the control join point following the command (x:=5x:=x+1). Although wp(K,N,X)_{x:=x′ may be large, it is not duplicated for each arm of the nondeterministic choice. There is only one copy of this expression. Instead of substituting both}5 and x+1 separately into wp(K, N, X), it is x′ that is substituted. This result is equivalent to the result of merging variables from the DSA used in the first preferred embodiment described above.

[0300] Note that if wp(K,N,X)_x:=x′ is valid for all values of x′, then a theorem prover might prove the preceding verification condition without separately analyzing the case x′=5 and the case x′=x+1.

[0301] By contrast if the ordinary wp equations are used to compute the weakest precondition of S, i.e.,

[0302] wp((x:=5x:=x+1);K,N,X)

[0303] the expression

[0304] wp(K,N,X)_x:=5Λwp(K,N,X)_x:=x+1

[0305] is obtained, in which wp(K,N,X) is duplicated in two nearly, but not exactly, identical copies.

[0306] A method according to the present invention has been implemented, as part of the Extended Static Checker for Java (“ESC/Java”) project. ESC/Java is a tool for finding, by static analysis, common defects in Java programs that are not normally detected until run-time, if ever (see, K. R. M. Leino, J. B. Saxe and R. Stata, “Checking Java programs via guarded commands.”, in Formal Techniques for Java Programs,Technical Report 251, Ed. B. Jacobs, et al., Fernuniversität Hagen, 1999; and K. R. M. Leino, J. B. Saxe and R. Stata, “ESC/Java user's manual,” Compaq Systems Research Center Technical Note 2000-002, October 2000, available from http://research.compag.com/SRC/publications. incorporated herein by reference). The executable object code of ESC/Java is publicly available for research and educational purposes (see Extended Static Checking web-page, Compaq Systems Research Center, http://research.compag.com/SRC/esc). It takes as input a Java program, possibly including user annotations, and produces as output a list of possible defects in the program. The annotations in the input program describe program properties such as method preconditions, method postconditions, and object invariants. These annotations allow ESC/Java to catch software defects using a modular, or method-local, analysis. During this analysis, ESC/Java verifies that the annotations are consistent with the program, and it also uses the annotations to verify that each primitive operation (such as a dereference operation, an array access, or a type cast) will not raise a run-time exception (as might happen, for example, if a dereferenced pointer is null or if an array index is out-of-bounds). To perform this analysis, ESC/Java first translates each method and its correctness property into an intermediate representation, the guarded command form, then translates the intermediate representation into a verification condition, and then uses an automatic decision procedure to determine the validity of the verification condition.

[0307] In the implementation of the present invention used in this Example, the program to be checked is converted into a passive guarded command form before the VC is generated. Thus duplicated subexpressions in the VC are exact copies (and not substitution instances) of one another. This implementation uses a cutoff K, and only names a duplicated subexpression if the subexpression is larger than K (where the size of a subexpression is the number of nodes in its representation). For any finite value of this cutoff, the size of the resulting VC is linear in the size of the passive statement, and hence at most quadratic in the size of the source program. The validity of the VC is checked with an automatic decision procedure, Simplify (see for example, Nelson, G., “Techniques for program verification,” Technical Report CSL-81-10, Xerox Palo Alto Research Center, 1981).

[0308] This Example presents experimental results comparing five VC-generation options: the standard wp-based translation, and the two-stage translation based on the embodiment described hereinabove with four different values (0, 10, 30, ∞) for the cutoff size K above which to introduce names for duplicated outcome predicates.

[0309] These experiments were performed on a 667 MHz ES40 Alpha workstation containing 4 Gb of memory running Tru64 UNIX. ESC/Java is written in Java, and was run on the Compaq Fast VM. The Simplify theorem prover is written in Modula-3, and runs as a separate process. The two processes communicate via Unix pipes.

[0310] The benchmark used for these experiments is ESC/Java's front-end, which has been annotated with appropriate specifications. This front-end consists of 2292 routines (methods and constructors) totaling over 20,000 lines of code.

[0311] The routines in the benchmark have been divided into three categories according to their worst performance under any of the five options. The first category contains the ten “hardest” routines. The verification of each of these routines either exhausted a 1 Gb heap or required more than five minutes under at least one of the options. The second category of routines contains the 17 routines that required at least 100 seconds under some option, but no more than 300 seconds under any option. The third category contains the 2184 routines in the benchmark that were successfully verified in under 100 seconds regardless of the VC generation option chosen. The remaining 81 routines in the front end are routines for which ESC/Java performs no VC generation (for example, methods declared in interfaces); these routines are not included in the benchmark.

[0312] The performance of the five VC generation options on the routines in the benchmark are shown in Table 9 hereinbelow, with results for the ten “hardest” routines given individually, and summed results for the other two categories.

[0313] The columns of Table 9 identify:

[0314] the routine name (or summed category);

[0315] the size of the abstract syntax tree for the routine (number of nodes);

[0316] the size of the guarded command (number of nodes);

[0317] the size of the VC under the wp translation (number of nodes);

[0318] the time required to check this routine under the wp translation (seconds);

[0319] the size of the passive version of the guarded command (number of nodes and percentage of original guarded command);

[0320] the cutoff K for naming duplicated outcome predicates (number of nodes);

[0321] the size of the VC under the two-stage translation (number of nodes and percentage of the wp VC); and

[0322] the time required to verify this routine under the two-stage translation (seconds and percentage of time using wp).

[0323] The times in Table 9 include the time required to translate the Java abstract syntax tree representation into a guarded command, the time required to translate the guarded command into a VC (including translation into the intermediate passive representation, if necessary), and time required to check the VC. For the summed categories, the entries in the percentage columns tell how big one summed quantity is as a percentage of another.

[0324] The results indicate that all the VC generation algorithms work well on the simpler routines in the third category. The two-stage translation produces smaller VC's that are slightly easier to prove for K=30 or K=∞. Choosing K=0 results in the theorem prover performing significant extra work to process the resulting indirections.

[0325] The wp translation has difficulty scaling to the larger or more complex routines; for five of the routines in this benchmark the wp translation exhausted a 1 Gb heap limit.

[0326] The two-stage translation involving passive guarded commands performs much better on these complex routines; the resulting VC's are significantly smaller, and can easily fit in the heap. Again, choosing K=0 results in larger proof times. For K>0, the two-stage translation yields VC's that require significantly less time to prove (sometimes by an order of magnitude) than the VC's produced by the wp translation.

[0327] The routine “parseNewExpression” requires significantly more time to verify under the two-stage translation than under wp. In general, the time required by Simplify to verify a formula is highly dependent on the order in which Simplify chooses to perform various case-splits, and the case-split order is determined by a variety of heuristics. For this routine, we suspect that these heuristics are misled in some manner by the VC generated by the two-stage translation.

[0328] Overall, the two-stage translation via passive guarded commands performs significantly better than the direct wp translation. It enables ESC/Java to check all of the routines in this benchmark due to the smaller space requirements, and is significantly faster. Excluding the six routines that could not be checked using the wp translation, checking the entire benchmark using wp required 4305 seconds, whereas using the two-stage translation requires only 2994 seconds (for K=30), or 2748 seconds (for K=∞).

[0329] All references cited herein are incorporated herein by reference in their entirety and for all purposes to the same extent as if each individual publication or patent or patent application was specifically and individually indicated to be incorporated by reference in its entirety for all purposes.

[0330] The present invention can be implemented as a computer program product, or a computer readable medium, that includes a computer program mechanism embedded in a computer readable storage medium. For instance, the computer program product could contain the program modules shown in FIG. 1. These program modules may be stored on a CD-ROM, magnetic disk storage product, or any other computer readable data or program storage product. The software modules in the computer program product may also be distributed electronically, via the Internet or otherwise, by transmission of a computer data signal (in which the software modules are embedded) on a carrier wave.

[0331] While the present invention has been described with reference to a few specific embodiments, the description is illustrative of the invention and is not to be construed as limiting the invention. Various modifications may occur to those skilled in the art without departing from the true spirit and scope of the invention as defined by the appended claims.