International Business Machines Corporation

Hana Chockler

Eitan D Farchi

Benyamin Godlin

Sharon Keidar-Barner

Ziv Glazberg

Dmitry Pidan

Sitvanit Ruah

Aviad Zlotnick

Oded Margalit

Lawrence Carter Blount

Orna Raz

Alexander Ivrii

Karen Frida Yorav

Ziv Nevo

Shiri Moran

Sergey Novikov

Arie Matsliah

Yochai Ben-Chaim

A method, system and product for directing verification towards bug-prone portions. The method comprising syntactically analyzing a computer program to identify portions of the computer program that correspond to one or more bug patterns; and performing verification of the computer program, wherein the verification comprises traversing a control flow graph of the computer program and tracking symbolic values of variables of the computer program, wherein said performing comprises directing the traversal of the control flow graph to nodes of the control flow graph that correspond to the identified portions, whereby bug-prone portions of the computer program are prioritized to be verified before non-bug-prone portions of the computer program.

Directing verification towards bug-prone portions

Method, apparatus, and product for performing incremental formal verification. A computer-implemented method performed by a computerized device. The method comprises: obtaining invariants with respect to a first model; determining a portion of the invariants that are invariants with respect to a second model, and utilizing the portion of the invariants to check that the second model holds a property.

Incremental formal verification

An abstract trace may be defined based on a coverage goal. An execution of a System Under Test (SUT) is guided in accordance with the coverage goal. Non-deterministic decision, which correlates to receiving a stimulus to the SUT, is decided based on a probability function. After one or more executions, the probability function is modified based on a measurement of similarity between the abstract trace and each of the one or more executions. The modification of the probability function may be performed using on Cross-Entropy method. The modification is performed in order to cause determination of non-deterministic decisions in executions to better correlate with the abstract trace. In some exemplary embodiments, a determination whether the abstract trace is reachable is determined based on a rate of convergence of the executions to the abstract trace.

Concretization of abstracted traces

A method, apparatus and product for dominant state based coverage metric. The method comprising: determining whether all possible states of a computer program were examined based on an analysis of states that were examined excluding controlled states that are dominated by a self-dominating states; wherein the controlled states are associated with a controlled nodes in a control flow graph of the computer program, wherein the self-dominating states are associated with a self-dominating node in the control flow graph; wherein each execution path in the control flow graph that reaches the controlled nodes also includes the self-dominating node; and wherein there exists an execution path in the control flow graph that both starts and ends at the self-dominating node and further includes at least one controlled node.

Dominant-state-based coverage metric

A trace associated with an abstraction of a target device is utilized to guide an execution of the target device to be substantially similar to the trace. An execution of the target device determines a non-deterministic decision based on a probability function. The probability function is configured to increase the likelihood that the execution will be substantially similar to the abstracted trace. Cross-entropy method may be utilized to guide the execution of the target device.

A coverage analysis tool may determine coverage in respect to heterogeneous coverage tasks associated with different hierarchy levels of a tasks hierarchy. The coverage analysis tool may iteratively refine coverage tasks to determine coverage of sub-tasks. In some cases, coverage tasks may be unrefined in order to reduce overhead of coverage analysis in performance of the software under test, such that the software under test may perform in an essentially similar manner as in non-testing mode.

Heterogenic Coverage Analysis

A method for replay of program executions using cross-entropy is provided. The method comprises identifying a first sequence of decision points, wherein the first sequence represents a first execution of a logic code; identifying a second sequence of decision points, wherein the second sequence represents a second execution of the logic code; computing a distance between the first and second executions; and minimizing the distance between the first and second executions using cross-entropy, in response to determining that the second execution is not within a predetermined threshold distance of the first execution.

Replay of program executions using cross-entropy

A method for detecting the occurrence of rare events in an executable logic code includes assigning a first probability of a chance of traversal of one or more decision paths, in which each path connects two decision points defined by execution of the logic code. As a result of execution of the logic code, the decision paths traversed are evaluated to determine whether said traversal conforms to a predefined performance function. The performance function defines a goal to be achieved pursuant to the execution of the logic code. A second probability is assigned to the chance of traversal of at least one of said one or more decision paths to increase the likelihood that the one or more decision paths are traversed in a subsequent execution of the logic code in a closer conformity with the predefined performance function.

Using cross-entropy to test executable logic code

A method for verifying software program code includes specifying a property that the software program code is expected to satisfy. The software program code and the property are transformed into an initial logical formula in a static single assignment (SSA) form, the formula including variables. A loop in the software program code is identified. Successive over-approximations are applied to a portion of the initial logical formula corresponding to the loop in order to produce a modified logical formula in the SSA form that represents a finite over-approximation of a set of states that are reachable by the loop. It is verified that the software program code satisfies the specified property by determining whether there is an assignment of the variables that satisfies the modified logical formula.

Model checking of non-terminating software programs

System, method and computer program product for checking a software entity, the method includes: providing a direct acyclic graph representative of possible execution paths of the software entity; wherein multiple successor nodes that succeed a certain parent node are associated with different execution probabilities; randomly selecting a successor node out of the multiple successor nodes in response the execution probabilities; and checking the software entity in response to the selection.

Growing community of inventors

Haifa, Israel

Hana Chockler