This invention is directed to an apparatus and method for automatic generation extended finite state machine architectures from software specifications.
In the course of designing a new computer application or operating system, typically one first writes a specification for the application. Such a specification may be tested by automatically generated validation tests, using techniques described below. An important stage in the generation of the validation tests is the transformation of the specification into a finite state machine (FSM), which for a complex specification will typically be an extended finite state machine (EFSM), often in a multi-EFSM architecture (EFSMA) with linking among the EFSMs to form a multiple layer model. It is these EFSMs and EFSMAs that constitute the output of the transformation method of the present invention.
The production of the specification involves specifying the functions the application or system will have to fulfill, defining the types and uses of variables, defining parameters and their relationships, and the other requirements which go into a conventional specification.
Such a specification may be quite extensive. For instance, for the widespread version of UNIX known as POSIX, the specification for the system application program interface (API) for the C programming language runs over 350 pages in the book entitled ISO/IEC 9945-1 (IEEE Std 1003.1)/Information Technology--Portable Operating System Interface (POSIX)--Part I (First Edition Dec. 7, 1990), which is incorporated herein by reference.
Software applications developers, system engineers, end users operating in a UNIX environment and others refer to such a specification whenever they author applications based upon it. Typically, such applications are tested during and after their creation, for internal consistency and to ensure that they perform as intended. Such testing will be referred to herein as validation (or validity) testing.
In the case of POSIX, for example, the above-mentioned IEEE reference provides the complete English-language specification of POSIX for the C programming language. Whenever a programmer writes an application in C to run on the POSIX operating system, this reference must be consulted to ensure that all of the standards are being complied with.
It is a very difficult and involved matter to ensure that an implementation of a long specification is consistent with the specification, and yet this is crucial for the proper operation of the implementation and anything based upon it. Testing and verifying the implementation is particularly important when the specification are for a computer language such as C or an operating system such as UNIX. If, for instance, an operating system based upon POSIX includes errors, those errors will create bugs in all programs that run on the erroneous operating system. Thus, before the implementation of POSIX is ever released, it should be fully tested.
Such an implementation will, for the POSIX 1003.1 specification mentioned above, take the form of a program written in the C language. Thus, the validation tests to be run must verify the correctness of this C implementation of the specification.
The concept of specification testing is represented, for example, by STATEMATE, which provides a system by which a programmer can model a specification and test it. See The STATEMATE Approach to Complex Systems, by i-Logix of Burlington, Mass. (1990); and D. Harel et al., STATEMATE: A Working Environment for the Development of Complex Reactive Systems, IEEE Transactions on Software Engineering, Vol. 16, No. (April 1990). Testing the implementation of a specification (i.e. an application based on the specification), based upon traversal of a graph model based upon the implementation, is discussed in W. H. Jessop et al., Atlas--An Automated Software Testing System, Bell Laboratories, Inc., 13th IEEE Computer Society International Conference, pp. 337-340 (1976) and 2nd International Conference on Software Engineering, pp. 629-635 (1976). Various test selection methods for systems expressed as finite state machines are discussed in S. Fujiwara et al., Test Selection Based on Finite State Models, IEEE Transactions on Software Engineering, Vol, 17, No. 6 (June 1991) and W. H. Jessop et al. Each of the foregoing articles is incorporated herein by reference.
With the STATEMATE system, the user must convert the English-language (as opposed to computer code) specification into a machine-readable coding. Neither STATEMATE nor other prior systems automatically generate validation tests for the actual implementation of the specification, i.e. for applications which are designed to comply with it.
To generate validation tests of an application, the systems described in the Jessop and Fujiwara articles rely upon an expression of the specification as a finite state machine (FSM). Essentially any specification or software application can theoretically be expressed an FSM, whether the modeled entity is state-rich or expressed as data relationships. An "extended" finite state machine adds context to the transitions (i.e. a record of the history of traversal of the transitions). See the Introduction below for a formal definition of EFSM.
FSMs and EFSM(A)s are particularly suited to state-rich problems. A program is state-rich if it controls a system where the state of the system at any given time is important, such as a program to control an automatic teller machine. A specification for an operating system interface or a program routine, on the other hand, is typically data-rich; that is, the specification is described largely in terms of detailed data structures and their relationships.
Although one can, if necessary, generate an FSM to represent a data-rich specification as states with transitions from one state to another, such a model does not serve well as a human-readable specification.
In addition, hand-generated graph models are subject to the limitations of the programmer who creates them, which can lead to testing inefficiencies or inaccuracies, particularly in the case of a data-rich setting. Data-rich problems are particularly unsuited to being expressed as graph models such as FSMs, since they are by definition descriptions of data relationships, not of states and generating and executing such tests is described below, but is primarily the subject matter of applicant's copending patent application, Ser. No. 08/100,006 entitled "Method and Apparatus for Testing Implementations of Software Specifications" (the "ISL Testing" application), which was filed on the same date as the present application.
The disclosure of the present application overlaps extensively with that of the ISL Testing application, since the description of the transformation procedure of the present invention is best explained in proper context, i.e. the generation of tests as a whole and the execution thereof.
The specification used to generate an EFSM(A) is expressed in a computer language, which can be compiled by a processor to generate tests for the specification, by describing data relationships in the input and output to an application programming interface (API). For this purpose, applicant has created a new language called Interface Specification Language (ISL). The specification is thus expressed as ISL source code. When this source code is compiled, the output includes:
(1) an extended finite state machine (EFSM) or a multiple-EFSM architecture, which is a model of the specification; PA1 (2) user documentation for the specified interface; and PA1 (3) validation code, i.e. callable routines allowing compile and run-time validation of parameters to be used before service is provided. PA1 "Method and Apparatus for Testing Structures Expressed as Finite State Machines" (the "PFL" application), Ser. No. 08/100,002, issued as "Method and Apparatus for Generating Tests for Structures Expressed as Extended Finite State Machines," U.S. Pat. No. 5,394,347 issued Feb. 28, 1995; PA1 "Method and Apparatus for Testing Implementations of Software Specifications" (the "ISL Testing" application), Ser. No. 08/100,006; and PA1 "Method and Apparatus for Schematic Routing" (STE Routing), Ser. No. 08/100,001, U.S. Pat. No. 5,408,597 issued Apr. 18, 1995
An EFSM or EFSMA generated by compiling the ISL source contains states, transitions and outputs, with context, event and predicate definitions. These concepts are conventional in the definition of an EFSM. See "ESTELLE--A FDT based on an extended state transition model", ISO TC 97/SC21 DP 9074, September 1985, which is incorporated herein by reference. Each transition in the model contains test information describing the result of satisfying a unique data relationship, or providing flow control to allow only valid combinations of data relationships to be selected. Test information is written in the target test language (C, Ada, FORTRAN, etc.) by the ISL compiler.
The EFSMAs are, in the preferred embodiment, constructed in applicant's Path Flow Language (PFL). The construction and use of EFSMAs are discussed in detail in applicant's copending U.S. patent applications, as follows:
Each of the foregoing patent applications was filed with the United States Patent Office on the same date as the present application, and each of the applications and articles cited above is incorporated herein by reference.
The output models (i.e. EFSMs or multiple-EFSM architectures) allow one of several path generation methods to be used, filling the requirements of exhaustive testing, thorough testing and identification testing as defined in IEEE Std 1003.3--1991/IEEE Standard for Information Technology--Test Methods for Measuring Conformance to POSIX (1991). See also Chow, T., Testing Software Design Modeled by Finite-State Machines, IEEE Transactions on Software Engineering, Vol. 4, No. 3, May 1978. These two references are incorporated herein by reference. In ISL parlance, exhaustive testing may be referred to as "allpaths", and thorough testing or identification testing as "edge cover" or "transition cover".
A given path through an EFSM represents a unique combination of data relationships, and traversing the path produces values for parameters and executable code that correspond to those data relationships, in addition to an API call that, when invoked, traverses the combination of data relationships. The path traversal also produces conditions which will appear in the program shell that is used to test the implementation of the specification.
The process of compiling ISL source into EFSMs is an equivalence transformation-that is, each data relationship or other construct in the original transitions. Thus, although a data-rich specification can be expressed as an FSM, it is very cumbersome to do so, and is not an intuitive way to approach the problem. Moreover, while such a model would be computer-readable, it could not easily be interpreted by humans if complicated data structures are involved. For this reason, FSM-based systems (such as Atlas) are not, in general, useful for data-rich problems. The cited articles do not teach any mechanism for automatically generating validation tests using the specification itself as a starting point.
A system is needed which bypasses the necessity for human intervention in the creation of models to generate testing software against a specification, and which at the same time can produce a set of tests which are accurate and which can be tailored to any degree of comprehensiveness, from testing all possible paths through the model to testing only a few. In particular, a system is needed which allows for modeling of a specification in a manner which is suitable for humans, but which leads directly to an expression of the model which can be used by a computer to generate validation tests for the implementation of the software.
USPTO Backgrounds
USPTO Backgrounds