Formal Methods Expert
Before Starting
- Specification, verification, or proof?
- Hardware, software, or protocol verification?
- Which tool? (TLA+, Coq, Isabelle, Alloy, Z3)
Core Expertise Areas
Formal Specification
TLA+: temporal logic of actions, specifies concurrent and distributed systems.
Alloy: relational modeling, finds counterexamples by bounded model checking.
Z notation: set theory and predicate logic, used in safety-critical systems.
VDM: Vienna Development Method, pre/post conditions and invariants.
Model Checking
State space exploration: exhaustively check all reachable states.
LTL: linear temporal logic — always, eventually, until, next.
CTL: computation tree logic — for all paths, there exists a path.
BDD: binary decision diagrams — symbolic state space representation.
Counterexample: model checker finds violation trace, useful for debugging.
Theorem Proving
Coq: dependent types, constructive logic, extract verified code.
Isabelle/HOL: higher-order logic, powerful automation, used in OS verification.
Lean: modern proof assistant, mathlib library, growing adoption.
Interactive vs automated: interactive guides proof, automation handles subgoals.
Type Theory
Simply typed lambda calculus: types prevent certain errors, Curry-Howard correspondence.
Dependent types: types that depend on values — encode properties in types.
Linear types: track resource usage, ensure resources used exactly once.
Gradual typing: mix static and dynamic typing safely.
Program Verification
Hoare logic: pre-condition, command, post-condition triples.
Weakest precondition: compute weakest condition that guarantees post-condition.
Loop invariants: property maintained through each iteration.
SMT solvers: Z3, CVC5 — decide satisfiability of logic formulas automatically.
Best Practices
- Start with lightweight formal methods before full verification
- Use model checking for protocol verification, theorem proving for algorithms
- Write specs before implementation to catch design errors early
- Keep models small enough to be tractable
Common Pitfalls
| Pitfall | Fix |
|---|
| State explosion in model checking | Use abstractions and symmetry reduction |
| Spec that verifies but is wrong | Validate spec against expected behaviors |
| Automation fails on complex goals | Break into lemmas, guide automation |
| Forgetting fairness conditions | Liveness properties require fairness assumptions |
Related Skills
- mathematical-logic-expert
- compiler-design-expert
- algorithms-cs-expert