| Patent application number | Description | Published |
|---|
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 20100305919 | SYSTEM AND METHOD FOR MODEL CHECKING BY INTERLEAVING STATELESS AND STATE-BASED METHODS - A method for symbolic model checking for sequential systems using a combination of state-based and state-less approaches. A state-based method is used to compute frontier states by building transition relations on-the-fly using control flow information of the system, and performing successive image computations until a memory bound is reached, and efficiently storing only the new frontier states as disjunctive partitions of Boolean and Arithmetic expressions. A stateless method is used to check reachability of given goal states from a heuristically chosen set of frontier states until depth/time bound is reached. These two methods are alternated until one of the following occurs: all frontier states are explored, all goal states are reached, all computing resources are exhausted. Even though we do not store the entire reachable state set, we guarantee a complete coverage for terminating programs without the need to compute a fixed-point. | 12-02-2010 |
| 20110078511 | PRECISE THREAD-MODULAR SUMMARIZATION OF CONCURRENT PROGRAMS - Methods and systems for concurrent program verification. A concurrent program is summarized into a symbolic interference skeleton (IS) using data flow analysis. Sequential consistency constraints are enforced on read and write events in the IS. Error conditions are checked together with the IS using a processor. | 03-31-2011 |
| 20110167412 | UNIVERSAL CAUSALITY GRAPHS FOR BUG DETECTION IN CONCURRENT PROGRAMS - A system and method for predictive analysis includes generating an execution trace on an instrumented version of source code for a multithreaded computer program. Interleavings which potentially lead to a violation in the program are statically generated by performing a static predictive analysis using a Universal Causality Graph (UCG) to generate alternative interleavings that might lead to an error. The UCG includes a unified happens-before model for the concurrent program and a property being analyzed. The interleavings are symbolically checked to determine errors in the program. | 07-07-2011 |
