IC3: Incremental Construction of Inductive Clauses for Indubitable Correctness
E909017
SAT-based verification algorithm
model checking algorithm
safety property verification algorithm
symbolic model checking technique
IC3: Incremental Construction of Inductive Clauses for Indubitable Correctness is a seminal model checking algorithm introduced by Kenneth McMillan that incrementally builds inductive invariants to efficiently verify hardware and software system correctness.
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
SAT-based verification algorithm
ⓘ
model checking algorithm ⓘ safety property verification algorithm ⓘ symbolic model checking technique ⓘ |
| advantageOver | BDD-based methods on many hardware benchmarks ⓘ |
| alsoKnownAs | IC3/PDR in hardware verification community NERFINISHED ⓘ |
| appliedTo |
finite-state transition systems
ⓘ
hardware systems ⓘ software systems ⓘ |
| approachType |
backward reachability guided by property
ⓘ
incremental clause learning over time frames ⓘ |
| basedOn |
incremental construction of inductive clauses
ⓘ
inductive invariants ⓘ |
| characteristic |
can produce concrete counterexample traces when property is violated
ⓘ
construction of inductive strengthening of safety properties ⓘ incremental refinement of over-approximations of reachable states ⓘ maintains a sequence of clause sets approximating reachable states ⓘ pushes clauses forward across time frames ⓘ |
| comparedTo | BDD-based symbolic model checking ⓘ |
| coreConcept |
frames representing over-approximations of reachable states at increasing time steps
ⓘ
inductive strengthening of the safety property that is invariant and excludes bad states ⓘ |
| field |
formal verification
ⓘ
model checking ⓘ |
| fullName | Incremental Construction of Inductive Clauses for Indubitable Correctness NERFINISHED ⓘ |
| goal |
find counterexamples to safety properties
ⓘ
prove system correctness ⓘ |
| influenced | property directed reachability (PDR) ⓘ |
| inspired | many IC3-like algorithms and extensions ⓘ |
| introducedBy |
Ken McMillan
NERFINISHED
ⓘ
Kenneth L. McMillan NERFINISHED ⓘ |
| notableFor |
high efficiency on large industrial hardware verification problems
ⓘ
seminal impact on SAT-based safety model checking ⓘ |
| output |
counterexample trace if property is false
ⓘ
inductive invariant proving safety ⓘ |
| propertyType | safety (invariance) properties rather than liveness ⓘ |
| requires |
encoding of initial states and safety property into propositional logic
ⓘ
encoding of transition relation into propositional logic ⓘ |
| searchStrategy |
generalization of blocking clauses to exclude sets of states
ⓘ
incremental blocking of bad states ⓘ |
| shortName | IC3 NERFINISHED ⓘ |
| uses |
Boolean satisfiability (SAT) solving
ⓘ
symbolic state representation ⓘ |
| verificationDomain |
bit-level hardware verification
ⓘ
software model checking via Boolean transition systems ⓘ |
| verifies | safety properties ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.
Kenneth McMillan
→
notableWork
→
IC3: Incremental Construction of Inductive Clauses for Indubitable Correctness
ⓘ