Methods and apparatus for generating passive testers from properties

• US 6,061,812 A
• Filed: 04/03/1998
• Issued: 05/09/2000
• Est. Priority Date: 04/03/1998
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Holzmann, Gerard J., Yannakakis, Mihalis
• Primary Examiner(s): HUA, LY
• Application Number:
  US09/054,470
• Time in Patent Office: 767 Days
• Field of Search: 714/38, 714/25, 714/31, 714/33, 714/35, 714/37, 714/39, 714/46, 712/25, 717/4
• US Class Current: 714/38.1
• CPC Class Codes: G06F 11/3672 Test management

Abstract

Techniques and testers for testing a system U including the steps of (a) defining a formal specification of a logical property P that system U is required not to satisfy; (b) generating a passive testing module T based upon property P to monitor system U; (c) invoking a function F at specific invocation points during the execution of system U to compute an abstract representation of the state of system U at the current point of execution; (d) passing the abstract representation computed by function F to passive testing module T in order to determine whether the abstract representation of the execution of system U to the current point matches illegal property P; and (e) declaring a "fail" result if the abstract representation of the execution of system U to the current point matches illegal property P and declaring a "pass" result if the abstract representation of the execution of system U to the current point does not match illegal property P.

Claims

1. A method for testing a software system U, comprising:

(a) defining a formal specification of a logical property P that system U is required not to satisfy;

(b) generating a passive testing module T based upon property P to monitor system U;

(c) invoking a function F at specific invocation points during the execution of system U to compute an abstract representation of the state of system U at the current point of execution;

(d) passing the abstract representation computed by function F to passive testing module T in order to determine whether the abstract representation of the execution of system U to the current point matches illegal property P;

(e) declaring a "fail" result if the abstract representation matches illegal property P and declaring a "pass" result if the abstract representation of the execution of system U to the current point does not match illegal property P.

2. A method according to claim 1, wherein steps (b)-(e) are repeated if a "pass" result in declared in step (e).

3. A method according to claim 1, wherein in step (c), the abstract representation is a small state descriptor constructed from the current state of system U at the point of invocation, the small state descriptor comprising a selection of available information relevant to the testing for property P.

4. A method according to claim 3, further including the following step (c1) performed prior to step (c):

(c1) constructing a separate formal model M of system U, formal model M defining an abstract state definition;

and wherein, in step (c), function F uses the abstract state definition defined by formal model M to compute an abstract representation of the state of system U at the current point of execution.

5. A method according to claim 1, wherein in step (c), the number of invocation points is reduced to those steps in system U where a state change happens that may be relevant to property P.

6. A method according to claim 5, further including the following step (c1) performed prior to step (c):

(c1) constructing a separate formal model M of system U, formal model M including a set of local transitions;

and wherein, in step (c), the invocation points are defined by the set of location transitions included in formal model M.

7. A method according to claim 1, wherein property P is expressed in linear temporal logic and is built from a finite number of Boolean propositions based upon the abstract representation of the state of system U as computed by function F.

8. A method according to claim 1, wherein the passive testing module T includes a non-deterministic automaton TA, which is generated by an LTL translator from property P expressed as an LTL formula.

9. A method according to claim 8, wherein the automaton TA contains simple error states that upon being reached instantly trigger a "fail" result.

10. A method according to claim 8, wherein the automaton contains accepting cycles, the execution of any of which by the system triggers a "fail" result.

11. A method according to claim 10, wherein the following method is used to establish the execution by the system of an accepting cycle:

keeping a record of possible current control states of automaton TA;

for each current automaton state in automaton TA, storing an initially empty set of pairs, the first element in each such pair being an accepting state in automaton TA, the second element of each such pair being an abstract state descriptor, as passed to passive tester T by function F;

updating the set of pairs according to the following two rules;

first, if the successors of current automaton state s_i reached upon being passed state descriptor u_i are the automaton states s_j, s_k, . . . , then the current set of pairs from s_i is included in the set of pairs for each of these successor states s_j, s_k, . . . ;

second, if a state s_i is reached upon being passed state descriptor u_i, and s_i is an accepting state in TA, then the pair (s_i, u_i) is added to the set of pairs stored for state s_i ;

reporting a "fail" result if at any time during the application of the second rule pair (s_i, u_i) is about to be added to the set of pairs that is stored for s_i and the same pair is already present in that set.

12. A tester for testing a software system U, comprising:

a passive testing module T that is based upon a formal specification of a logical property P that system U is required not to satisfy;

a state descriptor generator that receives, or has access to, current state data from software system U and computes an abstract representation of the state of system U at the current point of execution,

a passive testing module T that is based upon a formal specification of a logical property P that system U is required not to satisfy, the passive testing module receiving as an input the abstract representation to the passive testing module in order to determine whether the abstract representation of the execution of system U to the current point matches illegal property P;

means for declaring a "fail" result if the abstract representation of the execution of system U to the current point matches illegal property P and declaring a "pass" result if the abstract representation of the execution of system U to the current point does not match illegal property P.

13. A tester according to claim 12, wherein the abstract representation generated by the state descriptor generator comprises a selection of available information relevant to the testing for property P.

14. A tester according to claim 12, further including a formal model M of system U, formal model M defining an abstract state definition used by the state descriptor generator to compute the abstract representation of the state of system U at the current point of execution.

15. A tester according to claim 12, further including a formal model M of system U, formal model M including a set of local transitions which are used by the state descriptor generator to define the invocation points.

16. A tester according to claim 12, wherein property P is expressed in linear temporal logic and is built from a finite number of Boolean propositions based upon the abstract representation of the state of system U as computed by function F.

17. A tester according to claim 12, wherein the passive testing module T includes a non-deterministic automaton TA, which is generated by an LTL translator from property P expressed as an LTL formula.

18. A tester according to claim 17, wherein the automaton TA contains simple error states that, upon being reached, instantly trigger a "fail" result.

19. A tester according to claim 17, wherein the automaton TA contains accepting cycles, the execution of any of which by the system triggers a "fail result."

20. A tester according to claim 19, further includes means for establishing the execution by the system of an accepting cycle, comprising:

means for keeping a record of possible current control states of automaton TA;

means for storing, for each current automaton state in automaton TA, an initially empty set of pairs, the first element in each such pair being an accepting state in automaton TA, the second element of each such pair being an abstract state descriptor, as passed to passive tester T by function F;

means for updating the set of pairs according to the following two rules;

first, if the successors of current automaton state s_i reached upon being passed state descriptor u_i are the automaton states s_j, s_k, . . . ;

included in the set of pairs for each of these successor states s_j, s_k, . . . ;

second, if a state s_i is reached upon being passed state descriptor u_i and s_i is an accepting state in TA, then the pair (s_i, u_i) is added to the set of pairs stored for state s_i ;

means for reporting a "fail" result if at any time during the application of the second rule pair (s_i, u_i) is about to be added to the set of pairs that is stored for s_i and the same pair is already present in that set.