Lucent Technologies Inc.

At+t Corp.

Rajeev Alur

Mihalis Yannakakis

Robert Paul Kurshan

Kousha Etessami

Alon Itai

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

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

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

Ardmore, PA, United States of America

Rajeev Alur