Lucent Technologies Inc.

Doron A Peled

Robert Paul Kurshan

Gerard Johan Holzmann

Husnu Yenigun

Marius Minea

Vladimir Levin

Mihalis Yannakakis

Moshe Y Vardi

Elsa L Gunter

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

A method for visualizing and testing a sequence of a software code that includes instructions relating to assignment of variables, and decision branches. The method comprises the steps of generating a plurality of nodes, edges and text indications that correspond to the instructions in the software code. A plurality of pointers are then generated to associate the location of at least one line of the software code to at least one of the generated nodes. The pointers may also associate the location of a line in the software code to at least one of the generated edges. The method then displays a flow chart representing the generated nodes, and edges and text indications, so that the software code can be visualized. When a user selects a node or an edge in the displayed flow chart, a corresponding portion of the software code is also identified. In accordance with another embodiment, a portion of the software code defining an execution path is selected, and the system then calculates the logically most general condition for the possible execution of the selected path. In accordance with other embodiments, the path may be selected by a user, who highlights the nodes and/or edges along the displayed flow chart to calculate the conditions that allow the execution of the selected path, or by the system and the results of condition calculations are then presented to the user.

Interactive software testing system and method

A method for checking a property of a system modeled with a hierarchical message sequence chart is provided. To check a property of the modeled system, a temporal logic causality specification is defined. The specification is translated to a specification automaton, and an implementation automaton is constructed from the hierarchical message sequence chart. The intersection of the automata are then checked for emptiness.

Verification of message sequence charts

A static partial order reduction generator and process result in a substantially reduced state space graph of a multi-process system, independently of the model checking process. The process of this invention creates a modified state graph generator with appended rules that allow any desired state searching tactic (breadth first, depth first, etc.) to be employed when states and transitions are considered in the course of verification. This permits use of existing model checking tools without needing to modify them. The static partial order reduction is made possible by realizing that a prior art condition that at least one state along each cycle of the reduced state graph must be fully expanded can be guaranteed by considering the individual processes that make up the system and identifying certain transitions in those processes.

Static partial order reduction

A method and apparatus that employs static partial order reduction and symbolic verification allow the design of a system that includes both hardware and software to be verified. The system is specified in a hardware-centric language and a software-centric language, as appropriate, and properties are verified one at a time. Each property is identified whether it is hardware-centric or software-centric. A hardware-centric property that contains little software is does not employ the static partial order reduction. Software-centric properties, and hardware-centric properties that have substantial amounts of software do employ the static partial order reduction. Following partial order reduction, the software-centric language specifications are converted to synchronous form and combined with the hardware-centric specifications. The combined specification is applied to a symbolic verification tool, such as COSPAN, and the results are displayed.

Verifying hardware in its software context and vice-versa

Apparatus and methods for editing message sequence charts and determining whether a message sequence chart is consistent with a semantic of the system which the message sequence chart represents. As an editor, the apparatus maintains an internal representation of the message sequence chart as a set of processes and events, displays an image of the message sequence chart, and modifies the internal representation in response to modifications of the image by the user. The internal representation can be used to produce further representations of the message sequence chart. One of the representations is an event list which lists send events and receive events in the message sequence chart in a visual order. The event list is used together with a semantic provided by the user of the apparatus to determine whether there is an inconsistency between the message sequence chart and the semantic.

Message sequence chart analyzer

An on-the-fly verification system which employs statically-available information to reduce the size of the state space required to verify liveness and safety properties of a target system consisting of asynchronous communicating processes. The verification system generates a verifier from a description of the target system and a specification of the property to be verified. The verifier models the target system as a set of finite state machines, constructs a state space containing a graph of nodes representing states of the target system and transitions between the states, and uses the state space to verify the property. The size of the state space is reduced by using information from the description and the specification to divide transitions from a node into per-process bundles and to determine which bundles of transitions must be included in the state space and which may be left out of the state space. The state space reduction technique never increases the size of the state space and often reduces it by orders of magnitude.

Growing community of inventors

Gillette, NJ, United States of America

Doron A Peled