Method and system for testing behavior of procedures

• US 6,698,012 B1
• Filed: 09/15/2000
• Issued: 02/24/2004
• Est. Priority Date: 09/17/1999
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Corporation
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Burdonov, Igor B., Petrenko, Alexander K., Galter, Dmitri, Barancev, Alexei V., Kossatchev, Alexander S.
• Primary Examiner(s): ZHEN, WEI Y
• Application Number:
  US09/663,194
• Time in Patent Office: 1,257 Days
• Field of Search: 717/124-127, 717/159-161, 712/227, 714/799-824, 709/102-108
• US Class Current: 717/126
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases

Abstract

A systematic testing method of procedures is disclosed. The testing is carried out for parallel procedures separately from consecutive procedures which have no parallelism. Behavior of a group of parallel procedures to be tested in a parallel mode is specified. Based on the behavior, the group of procedures is tested using models of correct parallel behavior.

Claims

1. A method for testing procedures, the method comprising the steps of

separating parallel procedures from consecutive procedures which have no parallelism;

defining a group of parallel procedures to be tested in a parallel mode;

specifying behaviour of the group of procedures in the parallel mode by determining if the behaviour of the group of procedures is independent from parallel calls by another process;

testing the group of procedures in the parallel mode separately from the consecutive procedures, based on the specified behaviour; and

testing the group of procedures by calling oracles consecutively in an arbitrary order when the behaviour of the group of procedures is independent.

2. The method as claimed in claim 1, wherein the separating step comprises a step of separating a procedure as a consecutive procedure when the behaviour of which is defined by implicit specification.

3. The method as claimed in claim 2, wherein the step of testing further comprises a step of assigning a positive verdict when all oracles provide positive verdicts.

4. The method as claimed in claim 1, wherein

the step of specifying comprises a step of determining if the behaviour of the group of procedures is equivalent to a sequence of their execution without parallelism; and

the step of testing comprises a step of testing the group of procedures by calling oracles in the equivalent sequence.

5. The method as claimed in claim 4, wherein the determining step comprises steps of:

providing predetermined sequences of calls of procedures; and

checking if one or more predetermined sequences are equivalent to the parallel execution of the group of procedures.

6. The method as claimed in claim 5, wherein the step of testing further comprises a step of assigning a positive verdict when all oracles provide positive verdicts.

7. The method as claimed in claim 5, wherein the determining step further comprises a step of checking additional restrictions imposed on returned values of calls of procedures;

and

the step of testing further comprises a step of assigning a positive verdict when all oracles provide positive verdicts and all returned values conform to the additional restrictions.

8. The method as claimed in claim 5, wherein the determining step comprises steps of:

generating possible sequences of calls of the group of procedures when there is no predetermined sequence which is equivalent to the parallel execution of the group of procedures; and

locating one or more generated sequences which are equivalent to the parallel execution of the group of procedures.

9. The method as claimed in claim 8, wherein the step of testing further comprises a step of assigning a positive verdict when at least one sequence yields a desired result.

10. A test plan design system for planning testing of procedures, the system comprising:

means for separating parallel procedures from consecutive procedures which have no parallelism;

means for defining a group of parallel procedures to be tested in a parallel mode;

means for specifying behaviour of the group of procedures in the parallel mode; and

a test suite for testing the group of procedures in the parallel mode separately from the consecutive procedures, based on the specified behaviour and wherein

the specifying means comprises means for determining if the behaviour of the group of procedures is independent from parallel calls by another process; and

the test suite having a script driver and oracles, and the script driver calls the oracles consecutively in an arbitrary order when the behaviour of the group of procedures is independent, and calls the oracles in a specific order when the behaviour of the group of procedures is dependent.

11. The system as claimed in claim 10, wherein the oracles assign a positive verdict when all oracles provide positive verdicts when the behaviour of the group of procedures is independent.

12. The system as claimed in claim 10, wherein

the specifying means further comprising equivalent sequence determining means for determining if the behaviour of the group of procedures is equivalent to a sequence of their execution without parallelism when the behaviour is dependent on parallel calls of another process.

13. The system as claimed in claim 12, wherein the equivalent sequence determining means comprises:

means for providing predetermined sequences of calls of procedures; and

means for checking if one or more predetermined sequences are equivalent to the parallel execution of the group of procedures.

14. The system as claimed in claim 13, wherein

the script driver calls the oracles in a predetermined sequence when the predetermined sequence is equivalent to the parallel execution of the group of procedures;

and

the oracles assign a positive verdict when all oracles provide positive verdicts.

15. The system as claimed in claim 13, wherein the equivalent sequence determining means further comprises means for checking additional restrictions imposed on returned values of calls of procedures;

and

the oracles assign a positive verdict when all oracles provide positive verdicts and all returned values conform to the additional restrictions.

16. The system as claimed in claim 13, wherein the equivalent sequence determining means comprises:

means for generating possible sequences of calls of the group of procedures when there is no predetermined sequence which is equivalent to the parallel execution of the group of procedures; and

means for locating one or more generated sequences which are equivalent to the parallel execution of the group of procedures.

17. The system as claimed in claim 16, wherein the oracles assign a positive verdict when at least one sequence yields a desired result.

18. The system as claimed in claim 10, wherein the specifying means specifies behaviour of the consecutive procedures, and the test suite tests the consecutive procedures separately from the parallel procedures.

19. A verification system generator for generating a verification system for verifying a Procedure Interface Under Test (PIUT), the verification system generator comprising:

means for producing formal specifications of procedures of PIUT in a form independent from implementation of the PIUT;

a test source generator for generating test sources based on the formal specifications said test source generator comprising;

a test driver generator for generating test driver sources which are used to produce test drivers that execute tests and analyze results of the tests in implementation environments of the PIUT; and

a test case parameter generator for generating test case parameter sources which are used to produce test case parameters used by the test drivers for test execution; and

a repository for storing the generated formal specifications and test sources.

20. The verification system generator as claimed in claim 19, wherein the test driver generator includes:

a basic driver generator for general basic driver sources, the basic driver generator analyzing the formal specifications, and generating program sources of a basic driver for each PIUT; and

a script driver generator for generating a script driver source which describes a sequence of calls to the basic driver with different test case parameters.

21. The verification system generator as claimed in claim 20, wherein the basic driver sources are used to produce basic drivers in a form independent from implementation of the PIUT, each of the basic drivers corresponding to each PIUT and, during the test execution, provides direct call of its corresponding PIUT, tests the corresponding PIUT, and traces and analyzes test results of the corresponding PIUT.

22. The verification system generator as claimed in claim 20, wherein the basic driver generator further generates a list of test situation classes that represent test coverage requirements.

23. The verification system generator as claimed in claim 20, wherein the basic driver generator further generates initial data for partition analysis of the PIUT for the test case parameter generator to generate the test case parameter sources.

24. The verification system generator as claimed in claim 23, wherein the test case parameter generator receives the initial data from the basic driver generator, and generates programs for obtaining the test case parameters.

25. The verification system generator as claimed in claim 20, wherein the script driver sources are used to produce a script driver in a form independent from implementation of the PIUT, the script driver controls a sequence of calls to the basic drivers and the test case parameters during the test execution.

26. The verification system generator as claimed in claim 25, wherein the script driver further controls serial and parallel literations of the test execution of the corresponding PIUT with different test case parameters.

27. The verification system generator as claimed in claim 20, wherein the script driver generator uses script driver skeleton description and PIUT prototype specification.

28. The verification system generator as claimed in claim 19 further comprising an implementation language compiler for compiling the test sources into an implementation language of the PIUT.

29. The verification system generator as claimed in claim 28, wherein the test source generator further comprises a manage utility which analyzes interdependencies between the formal specifications and between the tests generated and compiled by the verification system and programs generated by other systems, searches inconsistencies, and removes the searched inconsistencies.

30. A method of producing a verification system for verifying a Procedure Interface Under Test (PIUT), the method comprising the steps of:

generating formal specifications of the PIUT in a form independent from implementation of the PIUT; and

generating test sources based on the formal specifications, which test sources are used to generate a test suite in a form independent from implementation of PIUT for executing tests and analyzing test results to verify the PIUT, wherein generating test sources comprises the step of generating constant arrays and programs for generating and selecting needed test case parameters.

31. The method as claimed in claim 30, wherein the step of generating formal specifications comprises the steps of:

defining PIUT;

developing implementation independent description of the PIUT; and

deriving the formal specifications based on the implementation independent description.

32. The method as claimed in claim 30, wherein the step of generating formal specifications uses Rigorous Approach to Industrial Software Engineering (RAISE) Specification Language (RSL).

33. The method as claimed in claim 30, wherein the step of generating test sources comprises the steps of:

generating test driver sources which are used to produce test drivers that execute tests and analyze results of the tests in implementation environments of the PIUT;

generating test case parameter sources which are used to produce test case parameters used by the test drivers for test execution; and

creating test plans for carrying out tests based on the formal specifications.

34. The method as claimed in claim 33, wherein the step of generating test driver sources comprises the step of generating basic driver sources by analyzing the formal specifications, and generating program sources of a basic driver for each PIUT.

35. The method as claimed in claim 34, wherein the step of generating test driver sources further comprises the step of generating script driver sources by creating skeletons describing a general scheme of the script driver, and generating script driver sources based on the formal specifications and the skeletons.

36. The method as claimed in claim 34, wherein the step of creating test plans comprises the step of describing scripts for test execution, the scripts defining test sequences, each test sequence being an instance of a basic driver with definite test case parameters.

37. The method as claimed in claim 36, wherein the step of describing scripts uses a special script language which facilitates serial and parallel combination of the test sequences.

38. The method as claimed in claim 33, wherein the step of creating test plans includes the step of generating data for test coverage estimation.

39. The method as claimed in claim 30 further comprising the step of storing the generated formal specifications and test sources in a repository.

40. The method as claimed in claim 39, wherein the step of storing comprising the steps of:

separating manually developed components from automatically generated components; and

separately storing the manually developed components from the automatically generated components.

41. The method as claimed in claim 40, wherein the step of generating test sources includes the step of re-generating test sources using the manually developed components when the PIUT is modified.

42. The method as claimed in claim 41, wherein the step of re-generating test sources is carried out automatically.

43. The method as claimed in claim 30 further comprising the step of compiling the test sources into an implementation language used by the PIUT.

44. The method as claimed in claim 43, wherein the step of compiling the test sources includes the step of describing correspondence between the formal specifications and implementation data structures of the PIUT.

45. The method as claimed in claim 43, wherein the step of compiling the test sources using converting procedures that convert values derived from the formal specifications into value formats used by the PIUT.

46. A method of verifying a Procedure Interface Under Test (PIUT), the method comprising the steps of:

generating formal specifications of the PIUT in a form independent from implementation of the PIUT;

generating test sources based on the formal specifications including the step of re-generating test sources using the stored formal specifications and test sources when the PIUT is modified;

storing the formal specifications and the test sources in a repository;

compiling the test sources into an implementation language used by the PIUT to produce tests;

executing the test on the PIUT using tests compiled from the re-generated test sources on the modified PIUT; and

analyzing results of the tests to verify the PIUT.

47. The method as claimed in claim 46, wherein the step of executing tests comprises the step of using the generated test sources when only implementation of PIUT is modified.

48. The method as claimed in claim 46, wherein the step of executing the tests includes the step of generating and collecting trace information of the tests;

and

the step of analyzing results comprises the step of estimating completeness of test coverage using the trace information.

49. The method as claimed in claim 46, wherein the step of generating test sources comprises the steps of:

generating test driver sources which are used to produce test drivers that execute tests and analyze results of the tests in implementation environments of the PIUT;

generating test case parameter sources which are used to produce test case parameters used by the test drivers for test execution; and

creating test plans for carrying out tests based on the formal specifications; and

the step of compiling comprises the steps of;

compiling the test driver sources into the test drivers; and

compiling the test case parameter sources into the test case parameters.

50. The method as claimed in claim 49, wherein the step of executing the tests includes the steps of:

initializing the PIUT;

calling the test drivers with test case parameters in accordance with the test plans; and

receiving results of the tests.

51. The method as claimed in claim 49, wherein the step of generating test driver sources comprises the steps of:

generating basic driver sources by analyzing the formal specifications for each PIUT; and

generating script driver sources by creating skeletons describing a general scheme of the script driver and generating script driver sources based on the formal specifications and the skeletons; and

the step of compiling the test driver sources comprises the steps of;

compiling the basic driver sources into basic drivers; and

compiling the script driver sources into a script driver.

52. The method as claimed in claim 51, wherein the step of executing the tests comprises the steps of:

executing the test plans;

launching the script driver by one of the test plans;

calling one of the basic drivers by the script driver; and

calling a PIUT by the basic driver which executes the test on the PIUT.

53. The method as claimed in claim 46, wherein the step of executing the tests further comprises the step of updating the repository.