Fujitsu Corporation

Synopsys, Inc.

Guodong Li

Indradeep Ghosh

Sreeranga P Rajan

John Steven

Praveen Murthy

Systems and methods for software verification. In some embodiments, an application architecture model is generated for a software application, wherein: the application architecture model is generated based on source code of the software application and a framework model representing a software framework using which the software application is developed; and the application architecture model comprises a plurality of component models. One or more component models may be selected, based on a property to be checked, from the plurality of component models. The one or more component models may be analyzed to determine if the property is satisfied.

System and methods for model-based analysis of software

Systems and methods for software verification. In some embodiments, an application architecture model is generated for a software application, wherein: the application architecture model is generated based on source code of the software application; and the application architecture model comprises a plurality of component models. A property model type may be selected, based on a property to be checked, from a plurality of property model types. One or more component models may be selected, based on the selected property model type, from the plurality of component models. The one or more selected component models may be used to construct at least one property model of the selected property model type. The at least one property model may be analyzed to determine if the property is satisfied with respect to the at least one property model.

Systems and methods for adaptive analysis of software

Systems and methods for software verification. In some embodiments, a first application architecture model is generated for a software application, wherein: the first application architecture model is generated based on a first version of source code of the software application; and the first application architecture model comprises a plurality of component models. A second version of source code may be compared against the first version of source code to determine at least one difference. At least one affected component model of the first application architecture model may be identified based on the at least one difference. A second application architecture model may be generated based on the second version of source code, wherein generating the second application architecture model comprises generating an updated version of the at least one affected component model.

Systems and methods for incremental analysis of software

Systems and methods for software verification. In some embodiments, a first statement is identified, from a discovery query written in a query language, the first statement comprising a side-effect construct with at least a first parameter and a second parameter, wherein: the first parameter of the side-effect construct comprises at least one second statement specifying one or more actions to be performed; and the second parameter of the side-effect construct comprises at least one condition specified based on a syntactic pattern. Source code of a software application may be analyzed to determine whether the at least one condition is satisfied, wherein determining whether the at least one condition is satisfied comprises determining whether the source code comprises a program element that matches the syntactic pattern.

Systems and methods for analyzing software using queries

A method may include determining sequence-execution constraints that constrain execution orders of a plurality of events of an event-driven software application. The method may also include determining sequence-position constraints that constrain positions of the plurality of events in one or more possible event sequences of the plurality of events. Further, the method may include determining event-relation constraints that each indicates a relationship between an event input and an event output of each of the plurality of events. Moreover, the method may include forming a constraint set that enumerates the one or more possible event sequences and that includes the sequence-execution constraints, the sequence-position constraints, and the event-relation constraints. In addition, the method may include encoding control flow information of the one or more possible event sequences into the constraint set.

Event-driven software testing

According to an aspect of an embodiment, a method may include determining event sequences of an event-driven software application. The method may further include determining, for each event sequence, a distance with respect to each of one or more target conditions of the event-driven software application. The event sequence distance may indicate a degree to which execution of its corresponding event sequence satisfies a corresponding target condition. The method may also include prioritizing execution of the plurality of event sequences based on the event sequence distances. Further, the method may include exploring, according to the prioritization of execution, an event space that includes one or more of the event sequences and a dependent event that corresponds to the one or more target conditions.

Event sequence construction of event-driven software by combinational computations

A satisfiability checking system may include a single instruction, multiple data (SIMD) machine configured to execute multiple threads in parallel. The multiple threads may be divided among multiple blocks. The SIMD machine may be further configured to perform satisfiability checking of a formula including multiple parts. The satisfiability checking may include assigning one or more of the parts to one or more threads of the multiple threads of a first block of the multiple blocks. The satisfiability checking may further include processing the assigned one or more parts in the first block such that first results are calculated based on a first proposition. The satisfiability checking may further include synchronizing the results among the one or more threads of the first block.

Satisfiability checking

Methods and systems for symbolic execution of software under test include the use of parametric states to losslessly represent a group of concrete execution states. Mathematical abstractions may represent differences between execution states and may define a parametric constraint for a parametric state. The parametric states may be usable for symbolic execution to reduce an amount of memory resources consumed and/or reduce a computational load during symbolic execution. Using parametric states, a larger state space and more program behaviors may be testable using symbolic execution.

Parameterized states in symbolic execution for software testing

A method of testing software may include generating a symbolic value for a return value of a software function of a software program during mixed symbolic and abstraction execution ('mixed execution') of the software program. Additionally, the mixed execution may maintain symbolic values, abstract values, and constraints of one or more variables of the software function. The method may also include deriving, during the mixed execution, an abstraction for the symbolic value. The abstraction may constrain the symbolic value and may be derived based on the return value of the paths that satisfy the abstraction. Further, the method may include exploring, during the mixed execution, the one or more paths of the software function that correspond to the return value based on the symbolic value, as constrained by the abstraction, such that a number of the one or more paths explored during the symbolic execution is constrained by the abstraction.

Symbolic execution with automatic abstractions

A method includes, by one or more computing devices, determining JavaScript statements to be evaluated, parsing the JavaScript statements, translating the JavaScript statements into Java bytecodes and JavaScript-specific instructions, executing the Java bytecodes in a Java execution engine, calling a JavaScript run-time engine from the Java execution engine, handling one or more semantic operations associated with the JavaScript-specific instructions through use of the JavaScript run-time engine, and providing return values to the Java execution engine. The statements are configured for execution on a computing device. The set of Java bytecodes and JavaScript-specific instructions is configured to conduct symbolic execution of one or more portions of the JavaScript statements. The symbolic execution is configured to evaluate the JavaScript statements.

Symbolic execution and automatic test case generation for JavaScript programs

A method of determining whether a set of constraints is satisfiable may include identifying a set of constraints associated with a software module. The method may also include modeling a string associated with a string constraint of the set of constraints as a parameterized array. Further, the method may include determining the satisfiability of the set of constraints based on a representation of the string constraint as a quantified expression. The satisfiability of the set of constraints may also be based on elimination of a quantifier associated with the quantified expression such that the string constraint is represented as a numeric constraint. The representation of the string constraint as a quantified expression may be based on the parameterized array that is associated with the string.

Mixed numeric and string constraint analysis

A method includes, by computing devices, analyzing numeric and string constraints associated with a software module that includes numeric and string variables and operations applying to specific variables for numeric or string results. The numeric constraints apply to specific numeric variables. The string constraints apply to specific string variables. The method further includes determining an over-approximated constraint from the numeric constraints or operations, representing the over-approximated constraint and string constraints with finite state machines, representing the numeric constraints with an equation, determining whether a solution does not exist for the combination of the variables that satisfies the over-approximated constraint, the numeric constraints, and the string constraints using operations, and terminating attempts to solve for the variables based on the determination whether the solution does not exist. The over-approximated constraint includes a superset of the numeric constraints or operations and applies to specific string variables.

Rule-based method for proving unsatisfiable conditions in a mixed numeric and string solver

Particular embodiments optimize a C++ function comprising one or more loops for symbolic execution, comprising for each loop, if there is a branching condition within the loop, then rewrite the loop to move the branching condition outside the loop. Particular embodiments may further optimize the C++ function through simplified symbolic expressions and adding constructs forcing delayed interpretation of symbolic expressions during the symbolic execution.

Optimizing libraries for validating C++ programs using symbolic execution

Particular embodiment compile a C++ program having one or more input variables to obtain bytecode of the C++ program; compile a C++ library to obtain bytecode of the C++ library; symbolically execute the bytecode of the C++ program and the bytecode of the C++ library, comprising assign a symbolic input to each input variable of the C++ program; determine one or more execution paths in the C++ program; and for each execution path, construct a symbolic expression that if satisfied, causes the C++ program to proceed down the execution path; and generate one or more test cases for the C++ program by solving the symbolic expressions.

Software architecture for validating C++ programs using symbolic execution

A method includes, by one or more computing devices, determining code-under-test configured for execution on a computing device to be evaluated, creating a plurality of test cases based on the symbolic execution and including a plurality of constraints, selectively conducting abstract interpretation on the constraints, selectively conducting Satisfiability Modulo Theory ('SMT') solving on the constraints, and validating or invalidating the code-under-test based on at least the SMT solving and the abstract interpretation. The abstract interpretation includes using a plurality of abstract interpretation models based on the constraints of the test case and over-approximating the constraints of the test case.

Growing community of inventors

San Jose, CA, United States of America

Guodong Li