Patent application number | Description | Published |
20090024557 | Clause and Proof Tightening - A computer-implemented method for verification of a target system includes defining a formula describing the target system, the formula including clauses, which include variables and which express constraints on states of the target system. The formula is processed so as to derive, using the clauses, a proof relating to a property of the target system. After deriving the proof, a variable that has a constant value is identified in the proof. The number of the variables in the proof is reduced using the identified variable, thereby producing a tightened expression, which is applied in making a determination of whether the target system satisfies the formula. | 01-22-2009 |
20090064064 | Device, System and Method for Formal Verification - Device, system and method of efficient automata-based implementation of liveness properties for formal verification. A system according to embodiments of the invention includes a property transformation module to receive an assume verification directive on a liveness property in a property specification language, and to translate the property a fairness statement that uses a deterministic automaton. The deterministic automaton is exponential in the size of the input property. The assume verification directive may be transformed into a strong suffix implication in the property specification language. | 03-05-2009 |
20090248601 | EXPLOITING DOUBLE RESOLUTIONS FOR PROOF OPTIMIZATIONS - A method for simplifying resolution proofs in DAG format where each leaf node represents a clause and each internal node represents a resolution between its children includes representing a SAT proof as a stripped proof, analyzing pivots to identify redundant resolutions, and constructing a simplified proof without the redundant resolutions. | 10-01-2009 |
20090307204 | ADAPTIVE APPLICATION OF SAT SOLVING TECHNIQUES - A computer-implemented method for solving a satisfiability (SAT) problem includes defining a formula, including variables, which refers to properties of a target system. Using a chosen search strategy, a search process is performed over possible value assignments of the variables for a satisfying assignment that satisfies the formula. A performance metric estimating an effectiveness of the search process is periodically evaluated during the search process. The strategy of the search process is modified responsively to the evaluated performance metric. The method determines, using the search process, whether the formula is satisfiable on the target system. | 12-10-2009 |
20100218150 | Logic Design Verification Techniques for Liveness Checking - A technique for verification of a logic design (embodied in a netlist) using a liveness-to-safety conversion includes assigning liveness gates for liveness properties of the netlist and assigning a single loop gate to provide a loop signal for the liveness gates. Assertion of the single loop gate is prevented when none of the liveness gates are asserted. A first state of the netlist is sampled and the sampled first state provides an initial state for a first behavioral loop for at least one of the liveness gates following the assertion of the single loop gate. The sampled first state of the first behavioral loop is compared with a later state of the first behavioral loop to determine if the sampled first state is repeated. A liveness violation is returned when the sampled first state is repeated and an associated one of the liveness gates remains asserted for a duration of the first behavioral loop. | 08-26-2010 |
20110178970 | TEMPLATE CLAUSES BASED SAT TECHNIQUES - A CNF formula comprises at least one template clause representing a set of concrete clauses, each associated with a different temporal shift. The template clause is utilized by a SAT solver in determining satisfiability of the CNF formula. The template clause may be utilized to reduce amount of storage resources required for performing the satisfiability analysis. The template clause may in some cases increase feasibility of determining satisfiability. The template clause may in some cases reduce required time to determine satisfiability. The template clause may be utilized in incremental SAT solving to reuse deduced relations between literals that are applicable to additional cycles, such as invariants originating from a transition relation of a model. | 07-21-2011 |
20110213605 | Satisfiability (SAT) Based Bounded Model Checkers - Systems and methods that use a solver to find bugs in a target model of a computing system having one or more finite computation paths are provided. The bugs on computation paths of less than a predetermined length are detected by translating the target model to include a state variable AF for one or more states of the target model, wherein AF(S) represents value of the state variable AF at state S; and solving the translated version of the target model that satisfies predetermined constrains. | 09-01-2011 |
20110295789 | Context-Sensitive Dynamic Bloat Detection System - Methods and apparatus are provided for a context-sensitive dynamic bloat detection system. A profiling tool is disclosed that selects an appropriate collection implementation for a given application. The disclosed profiling tool uses semantic profiling together with a set of collection selection rules to make an informed choice. A collection implementation, such as an abstract data entity, is selected for a given program by obtaining collection usage statistics from the program. The collection implementation is selected based on the collection usage statistics using a set of collection selection rules. The collection implementation is one of a plurality of interchangeable collection implementations having a substantially similar logical behavior for substantially all collection types. The collection usage statistics indicate how the collection implementation is used in the given program. One or more suggestions can be generated for improving the collection allocated at a particular allocation context. | 12-01-2011 |
20120060064 | SOFT ERROR VERIFICATION IN HARDWARE DESIGNS - Soft error detection is performed by computation of states based on formal methods and by simulating a synthesized target identification logic together with the design. Soft errors may be simulated in response to detecting that a simulated state of the design is comprised by the states. A BDD representation of the design may be utilized to determine the states. A Boolean satisfiability problem may be defined and solved using an all-SAT solver in order to determine the states. | 03-08-2012 |
20130159241 | TEMPLATE CLAUSES BASED SAT TECHNIQUES - A CNF formula comprises at least one template clause representing a set of concrete clauses, each associated with a different temporal shift. The template clause is utilized by a SAT solver in determining satisfiability of the CNF formula. The template clause may be utilized to reduce amount of storage resources required for performing the satisfiability analysis. The template clause may in some cases increase feasibility of determining satisfiability. The template clause may in some cases reduce required time to determine satisfiability. The template clause may be utilized in incremental SAT solving to reuse deduced relations between literals that are applicable to additional cycles, such as invariants originating from a transition relation of a model. | 06-20-2013 |