| Patent application number | Description | Published |
|---|
| 20080281563 | MODELING AND VERIFICATION OF CONCURRENT SYSTEMS USING SMT-BASED BMC - A computer implemented method for modeling and verifying concurrent systems which uses Satisfiability-Modulo Theory (SMT)-based Bounded Model Checking (BMC) to detect violations of safety properties such as data races. A particularly distinguishing aspect of our inventive method is that we do not introduce wait-cycles in our symbolic models for the individual threads, which are typically required for considering an interleaved execution of the threads. These wait-cycles are detrimental to the performance of BMC. Instead, we first create independent models for the different threads, and add inter-model constraints lazily, incrementally, and on-the-fly during BMC unrolling to capture the sequential consistency and synchronization semantics. We show that our constraints provide a sound and complete modeling with respect to the considered semantics. One benefit of our lazy modeling method is the reduction in the size of the BMC problem instances, thereby, improving the verification performance in both runtime and memory. | 11-13-2008 |
| 20080282221 | ACCELERATING MODEL CHECKING VIA SYNCHRONY - A system and method for program verification by model checking in concurrent programs includes modeling each of a plurality of program threads as a circuit model, and generating a full circuit for an entire program by combining the circuit models including constraints which enforce synchronous execution of the program threads. The program is verified using the synchronous execution to reduce an amount of memory needed to verify the program and a number of steps taken to uncover an error. | 11-13-2008 |
| 20090007038 | HYBRID COUNTEREXAMPLE GUIDED ABSTRACTION REFINEMENT - Systems and methods are disclosed for performing counterexample guided abstraction refinement by transforming a design into a functionally equivalent Control and Data Flow Graph (CDFG); performing a hybrid abstraction of the design; generating a hybrid abstract model; and checking the hybrid abstract model. | 01-01-2009 |
| 20090064110 | MINING LIBRARY SPECIFICATIONS USING INDUCTIVE LEARNING - A system and method for mining program specifications includes generating unit tests to exercise functions of a library through an application program interface (API), based upon an (API) signature. A response to the unit tests is determined to generate a transaction in accordance with a target behavior. The transaction is converted into a relational form, and specifications of the library are learned using an inductive logic programming tool from the relational form of the transaction. | 03-05-2009 |
| 20090089783 | PARTIAL ORDER REDUCTION USING GUARDED INDEPENDENCE RELATIONS - A system and method for conducting symbolic partial order reduction for concurrent systems includes determining a guarded independence relation which includes transitions from different threads that are independent for a set of states, when a condition or predicate holds. Partial order reduction is performed using the guarded independence relation to permit automatic pruning of redundant thread interleavings when the guarded independence condition holds. | 04-02-2009 |
| 20090125887 | SYSTEM AND METHOD FOR GENERATING ERROR TRACES FOR CONCURRENCY BUGS - A system and method for program verification includes generating a product transaction graph for a concurrent program, which captures warnings for potential errors. The warnings are filtered to remove bogus warnings, by using constraints from synchronization primitives and invariants that are derived by performing one or more dataflow analysis methods for concurrent programs. The dataflow analysis methods are applied in order of overhead expense. Concrete execution traces are generated for remaining warnings using model checking. | 05-14-2009 |
| 20090192963 | SYSTEM AND METHOD FOR DYNAMICALLY INFERRING DATA PRECONDITIONS OVER PREDICATES BY TREE LEARNING - A system and method for inferring preconditions for procedures in a program includes formulating predicates based on inputs to a procedure, including formal arguments, global variables and external environment. Truth assignments are sampled to the predicates to provide truth assignments that lead to a feasible set of input values. Test cases are generated for testing the program in accordance with the truth assignments having feasible sets of input values. The truth assignments are classified to the predicates as providing an error or not providing an error. | 07-30-2009 |
| 20090193401 | PATH-SENSITIVE ANALYSIS THROUGH INFEASIBLE-PATH DETECTION AND SYNTACTIC LANGUAGE REFINEMENT - A system and method for infeasible path detection includes performing a static analysis on a program to prove a property of the program. If the property is not proved, infeasible paths in the program are determined by performing a path-insensitive abstract interpretation. Information about such infeasible paths is used to achieve the effects of path-sensitivity in path-insensitive program analysis. | 07-30-2009 |
| 20090204968 | SYSTEM AND METHOD FOR MONOTONIC PARTIAL ORDER REDUCTION - A system and method for analyzing concurrent programs that guarantees optimality in the number of thread inter-leavings to be explored. Optimality is ensured by globally constraining the inter-leavings of the local operations of its threads so that only quasi-monotonic sequences of threads operations are explored. For efficiency, a SAT/SMT solver is used to explore the quasi-monotonic computations of the given concurrent program. Constraints are added dynamically during exploration of the concurrent program via a SAT/SMT solver to ensure quasi-montonicity for model checking. | 08-13-2009 |
| 20090222249 | MODULAR VERIFICATION OF WEB SERVICES USING EFFICIENT SYMBOLIC ENCODING AND SUMMARIZATION - A system and method for verifying a composition of interacting services in a distributed system includes generating a concurrent process graph (CPG) for processes in a system and symbolically encoding the CPG of each process to perform a reachability analysis. Symbolic summaries are generated for concurrently running processes based on the reachability analysis. Modular verification is conducted by utilizing the symbolic summaries of the processes to verify a system of interrelated processes. | 09-03-2009 |
| 20090282288 | DYNAMIC MODEL CHECKING WITH PROPERTY DRIVEN PRUNING TO DETECT RACE CONDITIONS - A system and method for dynamic data race detection for concurrent systems includes computing lockset information using a processor for different components of a concurrent system. A controlled execution of the system is performed where the controlled execution explores different interleavings of the concurrent components. The lockset information is used during the controlled execution to check whether a search subspace associated with a state in the execution is free of data races. A race-free search subspace is dynamically pruned to reduce resource usage. | 11-12-2009 |
| 20100005454 | PROGRAM VERIFICATION THROUGH SYMBOLIC ENUMERATION OF CONTROL PATH PROGRAMS - Systems and methods are disclosed to verify a program by symbolically enumerating path programs; verifying each path program to determine if the path program is correct or leads to a violation of a correctness property; determining a conflict set from the path program if the path program is proved correct; using the conflict set to avoid enumerating other related path programs that are also correct. | 01-07-2010 |
| 20100088681 | SYMBOLIC REDUCTION OF DYNAMIC EXECUTIONS OF CONCURRENT PROGRAMS - A computer implemented method for the verification of concurrent software programs wherein the concurrent software program is partitioned into subsets named concurrent trace programs (CTPs) and each of the CTPs is evaluated using a satisfiability-based (SAT) symbolic analysis. By applying the SAT analysis to individual CTPs in isolation the symbolic analysis is advantageously more scalable and efficient. | 04-08-2010 |
| 20100094611 | SYSTEM AND METHOD FOR FEEDBACK-GUIDED TEST GENERATION FOR CYBER-PHYSICAL SYSTEMS USING MONTE-CARLO - A system and method for generating test vectors includes generating traces of a system model or program stored in memory using a simulation engine. Simulated inputs are globally optimized using a fitness objective computed using a computer processing device. The simulation inputs are adjusted in accordance with feedback from the traces and fitness objective values by computing a distance between the fitness objective value and a reachability objective. Test input vectors are output based upon optimized fitness objective values associated with the simulated inputs to test the system model or program stored in memory. | 04-15-2010 |
| 20100205592 | CONTROL STRUCTURE REFINEMENT OF LOOPS USING STATIC ANALYSIS - A system and method for discovering a set of possible iteration sequences for a given loop in a software program is described, to transform the loop representation. In a program containing a loop, the loop is partitioned into a plurality of portions based on splitting criteria. Labels are associated with the portions, and an initial loop automaton is constructed that represents the loop iterations as a regular language over the labels corresponding to the portions in the program. Subsequences of the labels are analyzed to determine infeasibility of the subsequences permitted in the automaton. The automaton is refined by removing all infeasible subsequences to discover a set of possible iteration sequences in the loop. The resulting loop automaton is used in a subsequent program verification or analysis technique to find violations of correctness properties in programs. | 08-12-2010 |
| 20100281469 | SYMBOLIC PREDICTIVE ANALYSIS FOR CONCURRENT PROGRAMS - A symbolic predictive analysis method for finding assertion violations and atomicity violations in concurrent programs is shown that derives a concurrent trace program (CTP) for a program under a given test. A logic formula is then generated based on a concurrent static single assignment (CSSA) representation of the CTP, including at least one assertion property or atomicity violation. The satisfiability of the formula is then determined, such that the outcome of the determination indicates an assertion/atomicity violation. | 11-04-2010 |
| 20100293530 | SYSTEMS AND METHODS FOR MODEL CHECKING THE PRECISION OF PROGRAMS EMPLOYING FLOATING-POINT OPERATIONS - Methods and systems for verifying the precision of a program that utilizes floating point operations are disclosed. Interval and affine arithmetic can be employed to build a model of the program including floating point operations and variables that are expressed as reals and integers, thereby permitting accurate determination of precision loss using a model checker. Abstract interpretation can be also employed to simplify the model. In addition, counterexample-guided abstraction refinement can be used to refine the values of parametric error constants introduced in the model. | 11-18-2010 |
| 20100299651 | ROBUST TESTING FOR DISCRETE-TIME AND CONTINUOUS-TIME SYSTEM MODELS - A system and method for testing robustness of a simulation model of a cyber-physical system includes computing a set of symbolic simulation traces for a simulation model for a continuous time system stored in memory, based on a discrete time simulation of given test inputs stored in memory. Simulation errors are accounted for due to at least one of numerical instabilities and numeric computations. The set of symbolic simulation traces are validated with respect to validation properties in the simulation model. Portions of the simulation model description are identified that are sources of the simulation errors. | 11-25-2010 |
