IC3 model checking algorithm
E909016
SAT-based model checking algorithm
formal verification technique
model checking algorithm
safety property verification technique
The IC3 model checking algorithm is a SAT-based formal verification technique that incrementally constructs inductive invariants to efficiently prove or refute safety properties of hardware and software systems.
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
SAT-based model checking algorithm
ⓘ
formal verification technique ⓘ model checking algorithm ⓘ safety property verification technique ⓘ |
| abbreviation | PDR ⓘ |
| acronym | IC3 NERFINISHED ⓘ |
| advantage |
incremental and property-directed
ⓘ
often more scalable than BDD-based model checking ⓘ |
| aimsTo |
prove safety properties
ⓘ
refute safety properties ⓘ |
| alsoKnownAs | Property Directed Reachability NERFINISHED ⓘ |
| appliedTo |
hardware systems
ⓘ
software systems ⓘ |
| basedOn | Boolean satisfiability NERFINISHED ⓘ |
| checks | relative inductiveness of clauses ⓘ |
| comparedWith | BDD-based model checking ⓘ |
| constructs | inductive invariants ⓘ |
| coreIdea |
incrementally strengthen over-approximations of reachable states
ⓘ
maintain a sequence of clause sets approximating reachable states at increasing time frames ⓘ |
| ensures |
inductiveness of invariants
ⓘ
safety property holds in all reachable states ⓘ |
| frameRepresentation | conjunctions of clauses ⓘ |
| fullName | Incremental Construction of Inductive Clauses for Indubitable Correctness NERFINISHED ⓘ |
| hasVariant |
IC3 for software model checking
ⓘ
IC3 for timed systems NERFINISHED ⓘ IC3 with interpolation NERFINISHED ⓘ parallel IC3 ⓘ |
| inputType |
safety property
ⓘ
transition system ⓘ |
| inspired | many IC3-like algorithms ⓘ |
| introducedAtConference | VMCAI 2011 NERFINISHED ⓘ |
| introducedBy | Aaron R. Bradley NERFINISHED ⓘ |
| introducedInYear | 2010 ⓘ |
| maintains | sequence of frames ⓘ |
| outputType |
counterexample trace
ⓘ
proof of safety ⓘ |
| refines | over-approximation of reachable states ⓘ |
| researchArea |
automated verification
ⓘ
formal methods ⓘ |
| searchStrategy |
backward reachability from bad states
ⓘ
property-directed search ⓘ |
| terminationCondition |
counterexample to safety is found
ⓘ
fixed point of frames is reached ⓘ |
| usedIn | industrial hardware verification tools ⓘ |
| uses |
SAT solving
ⓘ
clause learning ⓘ incremental SAT solving ⓘ inductive invariants ⓘ |
| verifiesPropertyType | safety properties ⓘ |
| worksOn | finite-state transition systems ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.