Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Software program
Reexamination Certificate
1999-01-25
2001-10-02
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Software program
C703S014000, C703S015000, C716S030000, C717S152000
Reexamination Certificate
active
06298317
ABSTRACT:
THE FIELD OF THE INVENTION
The present invention relates generally to verifying the operation of computer programs, and, more particularly to an apparatus and method for functionally testing a computer program to determine if a test suite properly tests the computer program and to determine a likelihood that undetected functional bugs still exist the computer program.
BACKGROUND OF THE INVENTION
As computer programs increase in size and complexity, there is typically a corresponding increase in the number of syntactic errors introduced into the source code of these programs. Additionally, the increased size and complexity of today's computer programs make detection and isolation of these syntactic errors a much more difficult task.
The IEEE standard definition of an error is a mistake made by a developer. An error may lead to one or more software mutations (also known as faults). Mutations are located in the source code of a computer program. A mutation is a difference between an incorrect program and a corresponding correct program. The mutation may be localized in one statement or may be textually dispersed into several locations in the computer program. Similarly, the mutation may be repairable in many ways, with each one leading to a correct, but different program. See: Offutt, A. and Hayes J.,
A Semantic Model of Program Faults
, Proceedings of the 1996 International Symposium on Software Testing and Analysis, May, 1996.
The above definition of a mutation refers to the syntactic nature of a mutation. If the mutation is being inserted into the computer program, then the syntactic nature of the mutation is described by corresponding changes to the computer program. If the mutation occurs naturally in the program, then the syntactic nature of the mutation is described by the number of changes needed to correct the program. Examples of syntactic characterizations of mutations include using an incorrect variable name, or checking to see if a called function fails. Such mutations are often caused by programmer's mistakes, such as typographical errors.
A mutation can also be characterized semantically. Each computer program P can be viewed as having a specification S that defines sets D (an input domain) and R (an output range), and a mapping from D to R
(
D
→
S
R
)
.
A semantic characterization of a mutation views the faulty computer program as containing a computation that produces incorrect output over some subset of the input domain. That is, the mapping of inputs to outputs
(
D
→
P
R
)
is incorrect
(
D
→
P
R
≠
D
→
S
R
)
for some subset of D.
The characterization of mutation as “semantic” and “syntactic” proves quite useful when considering the size of a mutation. For a syntactically small mutation, one token or one statement may be incorrect. For a semantically small mutation, P's behavior on a very small subset of D is incorrect. A mutation that is syntactically small can result in a mutation that is very large semantically, because, the syntactic mutation can affect arbitrarily many inputs. Also, a major syntactic mutation in P may affect only a few inputs, resulting in a small semantic mutation. Finally, there are cases where a small semantic mutation can be modeled as small syntactic mutations, and small syntactic mutations can result in small semantic mutations.
There are significant behavioral differences between syntactically small/semantically large mutations and syntactically small/semantically small mutations. Syntactically small/semantically large mutations are of little value during the functional testing and verification process. This is evidenced by the fact that syntactically small/semantically large mutations are readily detected by almost any test case that reaches the mutated statement. These syntactically small/semantically large mutations are also subject to a high degree of overlap. That is, a testing/verification test case that kills one syntactically small/semantically large mutation will almost always kill many other syntactically small/semantically large mutations. Conversely, the subtle, syntactically small/semantically small mutations are much harder to detect during normal functional testing and verification. Thus, detection of these subtle, syntactically small/semantically small mutations will lead to higher quality tests.
Prior art software functional testing and verification systems have focused on mutations that are small syntactically, without consideration to semantic size. As mentioned in the previous paragraph, mutations that are small syntactically but are large semantically are easily detected by a very simple set of test vectors; they add difficulty to the functional testing and verification process without increasing the testing value of the resulting regression test cases. Syntactically small faults (mutants) typically have a large semantic size and, consequently fail to increase the value of resulting test cases.
In view of the above, there is a need for a system for detecting and discarding syntactically small faults having a large semantic size, and for integrating this concept into a functional simulation and verification system to determine a likelihood that undetected functional bugs exist in a software program and if a test suite properly tests the computer program.
SUMMARY OF THE INVENTION
The present invention provides a functional testing system for functionally simulating and verifying the correctness of a computer program. The functional testing system of the present invention includes a mutation generator for generating a series of mutated computer programs, wherein each mutated computer program has a syntactic mutation. The functional testing system of the present invention also includes a first functional simulator for serially processing each mutated computer program. This first functional simulator identifies whether the syntactic mutation in each mutated computer program is a non-subtle syntactic mutation. If the syntactic mutation is indeed a non-subtle syntactic mutation, the functional simulation of the mutated computer program containing the non-subtle syntactic mutation is terminated. The first function simulator then identifies each syntactic mutation not identified as a non-subtle mutation as a subtle mutation. The functional testing system of the present invention further includes a second functional simulator for serially processing each mutated computer program having a subtle syntactic mutation. The second functional simulator terminates the functional simulation of each mutated computer program if it detects the subtle syntactic mutation within a predetermined simulation period. However, if the second functional simulator does not detect the subtle syntactic mutation within the predetermined simulation period, the second function simulator provides an indication that the subtle syntactic mutation was not detected.
In one embodiment of the present invention, the computer program includes a plurality of source code modules. In a preferred embodiment of the present invention, the plurality of source code modules are functional models of an integrated circuit. The mutation generator identifies a set of eligible source code modules from the plurality of source code modules which are candidates for insertion of a syntactic mutation. A syntactic mutation is then inserted into a member selected from the set of eligible source code modules. The selection of a member from the set of eligible source code modules is done randomly, or by a distribution scheme which reflects the actual usage of the modules within the operating computer program.
The mutation generator selects a syntactic mutation for insertion within an eligible source code module from a predefined set of syntactic mutation types. The selection of the syntactic mutation is done randomly, or by a distribution scheme which reflects the probability o
Hewlett--Packard Company
Sergent Douglas W.
Teska Kevin J.
LandOfFree
Enhanced functional testing through the filtration of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced functional testing through the filtration of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced functional testing through the filtration of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2578867