Lucent Technologies Inc.

At+t Corp.

Mihalis Yannakakis

Rajeev Alur

Gerard Johan Holzmann

Robert Paul Kurshan

Doron A Peled

Moshe Y Vardi

James J Striegel

Alon Itai

Margaret H Holzmann

Kousha Etessami

A method and apparatus for generating a covering set of test cases from a directed graph is provided. The directed graph includes nodes and edges connecting the nodes, and a test case is a path through the directed graph. To generate a partial set of test cases, a set of selected test cases is received. These test cases can be manually selected or they can be a maintained test case set. The edges or nodes on the directed graph (or requirements linked to nodes or edges) that are covered by the selected test cases are marked with an identifier. Test cases are then generated from the directed graph according to a coverage algorithm. Marked graph elements may, but need not, be included in the generated test cases. The resulting partial test case set together with the selected test cases satisfy the coverage criterion.

Automatic generation and regeneration of a covering test case set from a model

A system and method for determining whether a set of message sequence charts (MSCs) is realizable or safely realizable in an implementation is provided. The determination is made by analyzing the set of MSCs for the existence of unspecified, implied MSCs. If the set of MSCs can be realized in a deadlock-free automaton, then the set of MSCs is safely realizable. If the set of MSCs is realizable (no implied MSCs exist), a state machine can be synthesized from the set of MSCs. If the set of MSCs is not realizable, then implied, unspecified (partial) MSCs are produced. Also, given an undesirable MSC, the system determines whether the set of required MSCs implies the given undesired MSC.

Implied message sequence charts

A system and method for direct black box system verification is provided. For any property, a sequence of inputs for the black box is determined that will verify that the system exhibits the property. Counterexamples of the property are detected without inferring the black box's internal structure; that is, the verification proceeds without identifying all states and state transitions of the black box. A specification automaton operable to exhibit undesirable system behavior is constructed and it is then determined whether an accepting execution exists on the intersection of the black box and the specification automaton. To determine whether such an execution exists, the black box is configured such that it can be reset to its initial state upon command and such that the system indicates when an input is disabled from a current state. When an input is enabled, the implementation transitions to the next state. If an input is disabled, then there is no intersection on the input string. The inputs are determined through a search of a specification automaton for accepting sequences up to a given bound. The bound is the product of the number of states of the black box and the specification automaton.

Directly verifying a black box system

Model checking for message sequence charts (MSCs), message sequence chart graphs and hierarchical message sequence chart graphs (HMSCs) is provided. To verify the behavior of a given MSC, MSC graph and HMSC, a specification automaton is constructed. This specification automaton specifies the undesirable executions of the model under analysis. From the model under analysis, linearizations are defined from the model and a finite test automaton is constructed from the linearizations. The test automaton and the specification automaton are combined and it is determined whether there is an execution in the intersection. Where no state in the specification automaton is reachable from the test automaton, the model is verified.

Model checking of message flow diagrams

Model checking is applied to a hierarchical state machine (i.e., a state machine having at least one state (i.e., a superstate) that is itself a state machine) without first flattening the hierarchical state machine. In one embodiment, the model checking involves one or more or reachability, cycle-detection, linear-time requirements, and branching-time requirements analyses. For reachability analysis, in addition to keeping track of whether states have been visited, the algorithm also keeps track of the exit nodes for each superstate. Cycle-detection analysis has two phases: a primary phase in which target states are identified and a secondary phase in which it is determined whether identified target states are part of closed processing paths or loops. For cycle-detection analysis, the algorithm keeps track of (1) whether states have been visited during the primary phase, (2) the exit nodes for each superstate, and (3) whether states have been visited during the secondary phase. For linear-time requirements analysis, a formula is translated into an automaton, and a product construction is defined between the automaton and a hierarchical machine that yields a new hierarchical machine that is then analyzed using the cycle-detection algorithm. For branching-time requirements analysis, a list of subformulas is generated for an original temporal logic formula, where the subformulas are arranged in order of increasing size. An appropriate subroutine is then implemented for each subformula in the list based on the syntax of the subformula. For certain syntaxes, multiple versions are generated of the finite state machine corresponding to each superstate to represent different possible temporal logic conditions, and an appropriate version is selected for the context of each occurrence of the superstate in the hierarchical state machine. After processing the entire list of subformulas, it is determined whether the entry node of the hierarchical state machine satisfies the original temporal logic formula.

Model checking of hierarchical state machines

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.

Methods and apparatus for generating passive testers from properties

Apparatus for developing and verifying systems. The disclosed apparatus employs a computationally-tractable technique for verifying whether a system made up of a set of processes, each of which has at least one delay constraint associated with it, satisfies a given temporal property. The technique deals with the verification as a language inclusion problem, i.e., it represents both the set of processes and the temporal property as automata and determines whether there is a restriction of the set of processes such that the language of the automaton representing the restricted set of processes is included in the language of the automaton representing the temporal property. The technique is computationally tractable because it deals with the problem iteratively: it tests whether a current restriction of the set of processes is included, and if not, it employs a counter-example for the inclusion to either determine that the delay constraints render satisfaction of the given temporal property or to derive a new restriction of the set of processes. Further included in the disclosure are techniques for checking the timing consistency of the counter-example with respect to a delay constraint and techniques for finding the optimal delay constraint.

Growing community of inventors

Summit, NJ, United States of America

Mihalis Yannakakis