Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-02-25
2001-08-14
Chaki, Kakali (Department: 2762)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06275976
ABSTRACT:
BACKGROUND OF THE INVENTION
Given the growing complexity of modern software systems, there is an increasing demand for easier ways of locating errors and for ensuring or verifying the correctness of software designs. Tools for accomplishing these purposes range from the simple type checking provided by many compilers and source code analysis tools to formal verification proofs.
The former, unfortunately, miss many common errors. The latter involve constructing rigorous mathematical proofs. Such proofs are extremely difficult to construct with automation research limited to small programs. Despite limited successes, these solutions do not scale to non-trivial software. Consequently, formal verification is rarely used in practice. Jackson (see U.S. Pat. No. 5,423,027) has proposed a compromise solution. This approach does not eliminate errors as does formal verification, but it lends itself to automation and does catch more errors than simple type checking (during compilation). This is accomplished via optional programmer input and an automated checking tool that references various aspects (e.g., properties) of objects (types) rather than variables. The invention involves (a) specifying input and output values of these aspects for each procedure in a program, (b) examining and constructing an approximation of actual dependencies in procedural code and (c) comparing the approximate dependencies with the procedural specifications. The comparison of specifications with the approximations in the procedural code is used to identify omissions in the latter.
The above approach, in effect, is concerned with better ways to check given source code. The Jackson invention does not deal with design issues, cannot guarantee correctness and any concrete realization must address language specific issues.
Gaboury (U.S. Pat. No. 5,481,717) takes a different approach to formal verification. In parallel with our own efforts, Gaboury has disclosed a method for verifying a computer program in relation to its specification. This method is an extension of an existing Binary Decision Diagram algorithm to compare Finite State Machines, and involves comparison of a program and its specification after they both have been represented as logic programs (e.g., in Prolog, using variables and production rules). The basic method disclosed by Gaboury involves: (a) converting two logic programs into corresponding finite state machines, each having internal states, input values and output values, (b) determining the data types of the variables of the logic programs, (c) converting all expressions in the logic program into disjunctive form, (d) expanding procedure calls into procedure bodies, (e) translating the programs into transition functions and (f) determining whether equivalencies between internal states, input values and output values of the two finite state machine descriptions produce equivalent output values for all equivalent input values and states.
As with the Jackson method, however, this method requires formal verification of both specifications and solutions as parameterized logic programs. This method offers one way to solve the problem of unspecified parameters (e.g., in specifications); it effectively replaces details with unspecified parameters for comparison purposes. Although this approach is theoretically plausible, it solves the problem by introducing non-intuitive elements into the specification. By way of contrast, the present disclosure has no requirement that either the specification or the program be represented as a logic program. Specifications deal exclusively with input-output behavior and implementations are represented in traditional (sequential/event driven) real world terms.
In a similar vein the Gaboury disclosure eliminates syntactic differences such as variable names. Syntactic differences involving names, for example, although of limited importance in mathematical formulations, play an important role in human understanding. They are essential in building and maintaining complex, real world software. In effect, the Gaboury approach is not likely to be very helpful either during development or during ongoing maintenance. Moreover, the method cannot be used with many kinds of software because comparison of unrestricted logic programs is an undecidable problem.
Rather than verifying correctness after implementation, other approaches attempt to improve software quality by design. One approach derives from contemporary software and system development methodologies (e.g., structured analysis [Hatley & Pirbhai, 1987; Yourdon, 1989]; information engineering [Chen, 1976; Flaatten et al, 1989], object oriented design [Booch, 1994; Rumbaugh et al., 1991]). Most of these methods make a sharp distinction between design, implementation and testing. Implementation, for example, comes after design, and although limited consistency checking is included in many CASE tools, correctness testing is postponed until after implementation. Given exponential growth with complexity in the number of paths to be tested, these methodologies make complete verification testing impossible. For example, after implementation, a simple system having a sequence of 100 binary decisions has 2
100
independent paths to be tested. Clearly, it is impossible to fully verify the correctness of even moderate sized programs empirically. However, only 300 paths are involved if testing is done at successive levels of refinement (see Scandura, 1992, p. 92). In this case the number of paths goes up only additively.
Traditional approaches to proving that software is correct (i.e., does exactly what specifications call for) require proving that the program will produce the desired output for any given set of inputs. This is true whether one attempts to prove correctness after software has been developed (e.g., Hoare & Shepherdson, 1985) or at successive stages of process refinement as in clean room engineering (Linger, 1994) and higher order software (Martin, 1985).
In contrast to the above, clean room engineering is based on mathematically rigorous correctness methods and has been successfully applied in a number of projects. The approach, however, involves manual verification (e.g., Linger, 1994; Linger, Mills & Witt, 1979). It is based on a hardware metaphor (where one knows all inputs and outputs before designing a system) and has not been shown to scale well to larger software systems. In recognition of the complexities of verification during development, “clean room” puts a heavy emphasis on software testing after implementation based on statistical sampling methods. Martin (1985) describes an alternative approach developed by Hamilton and Zeldin that is based on provably correct design constructs. The latter, however, also requires formal, non-intuitive modeling techniques, which again are not easily applied to large systems. A fundamental limitation of these methods is they assume that all input and output variables to a proposed system have been specified prior to system analysis (e.g., Martin, 1985, p. 50). This complicates design, especially in larger systems. Furthermore, no provision is made in the Martin (1985) approach for formulating precise specifications. Even where this is done, proving correctness is impractical using these methods because the numbers of input-output relationships to be verified is simply too large.
In contrast with Jackson, this invention deals with software design as well as code. Like other software engineering methodologies, its goal is to make software easier to understand, construct and modify. Unlike software engineering methodologies, however, including the more complete consistency checking provided by cleanroom engineering and Hamilton's “provably correct designs”, the method proposed herein not only ensures consistency but it guarantees that software is correct by design and lends itself to automation.
Rather than catching errors after implementation, like Jackson, the latter more promising approaches attempt to ensure correctness by design. Cl
LandOfFree
Automated method for building and maintaining software... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automated method for building and maintaining software..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automated method for building and maintaining software... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2465128