Apparatus and method for testing computer program implementation against a design model

Abstract

A method of testing a computer program implementation according to a predefined design model, the program implementation having at least one method under test, employs a computer to generate a post-method corresponding to the method under test. A computer is further used to automatically generate a set of test cases. Then, using the automatically generated set of test cases, the computer explores different execution paths of the computer program implementation, by applying those test cases to both the method under test and the generated post-method, to reveal behavior that is not consistent with the behavior specified by the design model.

What is claimed is: 
     
       1. A method of testing a computer program implementation according to a predefined design model, the design model being of the type having a static model component and a dynamic model component, comprising:
 identifying a method under test from within the computer program implementation; 
 using a computer to extract the dynamic model component and generate a post-method corresponding to the method under test; 
 using a computer to store an initial test case value having a corresponding initial input parameter set comprising at least one parameter; 
 using a computer to instrument for symbolic execution both the method under test and the post-method; 
 using a computer to run the instrumented method under test and to build a first symbolic memory representation corresponding to a first execution path condition of the method under test, the first symbolic memory representation being stored in non-transitory computer-readable memory as a path condition (PC); 
 using a computer to run the instrumented post-method, and using the first symbolic memory representation to build a second symbolic memory representation corresponding to the post-method, the second symbolic memory representation being stored in non-transitory computer-readable memory as a post-method path condition (PCpost); 
 using a computer to test the returned Boolean state of the post-method path condition and store an indication in computer memory that an error has been detected if the returned Boolean state is FALSE and to perform the following steps if the returned Boolean state is TRUE; 
 using a computer to execute a satisfiability (SAT) solver algorithm to analyze whether all members of the input parameter set satisfying the path condition PC also satisfy the post-path condition PCpost and thereby determine that PC and PCpost correspond to a tautology relationship; 
 using a computer to further evaluate the relationship between PC and PCpost as follows: 
 if a tautology relationship is found, generate a second test case value, different from the initial test case value and run the instrumented method under test and post-method again using an execution path for the method under test that is different from the first execution path condition; 
 if a tautology relationship is not found, generate a third test case value, having a parameter set different from the initial parameter set. 
 
     
     
       2. The method of  claim 1  wherein the second test case value is used to run the post-method again using the first execution path condition. 
     
     
       3. The method of  claim 1  wherein the second test case value is used to run the post-method again using an execution path condition that is different from the first execution path condition. 
     
     
       4. The method of  claim 1  wherein the third test case value is used to run the instrumented method under test using the first execution path condition. 
     
     
       5. The method of  claim 1  wherein the third test case value is used to run the post-method again using and execution path for the post-method that is different from the first execution path condition. 
     
     
       6. The method of  claim 1  wherein the static model component is expressed using a modeling language and the dynamic model component is expressed using an object constraint language. 
     
     
       7. The method of  claim 6  wherein the post-method is generated by the computer scanning the object constraint language expression of the dynamic model and generating an abstract syntax tree that is then traversed to form a Boolean method corresponding to the method under test. 
     
     
       8. The method of  claim 1  wherein the program implementation is an object oriented language. 
     
     
       9. The method of  claim 1  wherein the program implementation is a Java language implementation, where the static model component is expressed using a unified modeling language (UML) representation and the dynamic model component is expressed using an object constraint language (OCL) representation. 
     
     
       10. An apparatus for testing a computer program implementation according to a predefined design model, the design model being of the type having a static model component and a dynamic model component, comprising:
 at least one processor programmed to extract the dynamic model component and to generate and store in memory coupled to said processor a post-method representation corresponding a method under test; 
 at least one processor programmed to store an initial test case value having a corresponding initial input parameter set comprising at least one parameter; 
 at least one processor programmed to instrument for symbolic execution both the method under test and the post-method; 
 at least one processor programmed to run the instrumented method under test and to build a first symbolic memory representation corresponding to a first execution path condition of the method under test, the first symbolic memory representation being stored in non-transitory computer-readable memory as a path condition (PC); 
 at least one processor programmed to run the instrumented post-method, and using the first symbolic memory representation to build a second symbolic memory representation corresponding to the post-method, the second symbolic memory representation being stored in non-transitory computer-readable memory as a post-method path condition (PCpost); 
 at least one processor programmed to test the returned Boolean state of the post-method path condition and store an indication in computer memory that an error has been detected if the returned Boolean state is FALSE and to perform the following steps if the returned Boolean state is TRUE; 
 at least one processor programmed to execute a satisfiability (SAT) solver algorithm to analyze whether all members of the input parameter set satisfying the path condition PC also satisfy the post-path condition PCpost and thereby determine that PC and PCpost correspond to a tautology relationship; 
 the at least one processor programmed to further evaluate the relationship between PC and PCpost as follows: 
 if a tautology relationship is found, generate a second test case value, different from the initial test case value and run the instrumented method under test and post-method again using an execution path for the method under test that is different from the first execution path condition; 
 if a tautology relationship is not found, generate a third test case value, having a parameter set different from the initial parameter set. 
 
     
     
       11. The apparatus of  claim 10  wherein the second test case value is used to run the post-method again using the first execution path condition. 
     
     
       12. The apparatus of  claim 10  wherein the second test case value is used to run the post-method again using an execution path condition that is different from the first execution path condition. 
     
     
       13. The apparatus of  claim 10  wherein the third test case value is used to run the instrumented method under test using the first execution path condition. 
     
     
       14. The apparatus of  claim 10  wherein the third test case value is used to run the post-method again using an execution path for the post-method that is different from the first execution path condition. 
     
     
       15. The apparatus of  claim 10  wherein the static model component is expressed using a modeling language and the dynamic model component is expressed using an object constraint language. 
     
     
       16. The apparatus of  claim 15  wherein the post-method is generated by the computer scanning the object constraint language expression of the dynamic model and generating an abstract syntax tree that is then traversed to form a Boolean method corresponding to the method under test. 
     
     
       17. The apparatus of  claim 10  wherein the program implementation is an object oriented language. 
     
     
       18. The apparatus of  claim 10  wherein the program implementation is a Java language implementation, where the static model component is expressed using a unified modeling language (UML) representation and the dynamic model component is expressed using an object constraint language (OCL) representation.