Method and apparatus for testing implementations of software

Abstract

A method and apparatus for automatically generating validation tests for implementations of a program specification for an operating system, software application or a machine, where the program specification is expressed at least in part in terms of data structures and relationships. The method is carried out by a computer. The program specification is expressed in an interface specification language which is automatically parsed, and is then transformed into an extended finite state machine (EFSM) or multiple-EFSM architecture internally represented in the computer, the EFSM including objects representing states and transitions between those states representing executable functions, annotated to the states. The annotations may represent predicates, test data, value assignments, branch conditions, etc. The EFSM or architecture is traversed by a path traversal procedure, either exhaustively or in part, thereby producing path files, one for each path taken. Each path file is linked to a program shell, which is automatically generated for the specification, resulting in one independent validation test for each path file. Each validation test includes a call to the implementation of the program specification, and presents that implementation with a test vector representing a given path through the model. Failure and success responses are produced, indicating whether the implementation behaved as expected. Multiple validation tests may be linked or combined in a variety of ways to form a superstructure (architecture) of validation tests for testing of many routines in conjunction with one another, such as for testing all the routines specified for an operating system at the same time.