Formal Verification

Formal Methods Overview — Proving Software Correct

A complete overview of formal methods for software correctness — model checking, theorem proving, static analysis, and real-world verification case studies.

Propositional Logic — Truth Tables, SAT and Resolution

A practical guide to propositional logic for formal verification — truth tables, SAT solving, resolution proofs, and their use in software correctness.

Temporal Logic — LTL, CTL and Model Checking Properties

A complete guide to temporal logic for formal verification — LTL and CTL operators, model checking properties, fairness constraints, and practical examples.

Model Checking — State Space Exploration and Counterexamples

A practical guide to model checking for formal verification — state space exploration, Kripke structures, CTL model checking algorithms, and counterexample analysis.

Theorem Proving — Induction, Tactics and Proof Assistants

A step-by-step guide to theorem proving for formal verification — mathematical induction, proof tactics, and mechanized reasoning with proof assistants.

Satisfiability and SMT Solving — SAT Solvers and Z3

A practical guide to SAT and SMT solving for formal verification — DPLL algorithm, CDCL, theory solvers, and Z3 integration for program analysis.

Bounded Model Checking — CBMC and Software Verification

A complete guide to bounded model checking for software verification — loop unwinding, CBMC usage, SAT-based verification, and handling arrays and pointers.

Symbolic Execution — KLEE, Angr and Path Exploration

A practical guide to symbolic execution for formal verification — symbolic variables, path constraints, KLEE and Angr usage, and finding deep bugs in real programs.

Abstract Interpretation — Sound Static Analysis

A complete guide to abstract interpretation for formal verification — abstract domains, Galois connections, widening, and sound static analysis of programs.

TLA+ — Specifying Distributed Systems

A step-by-step guide to TLA+ for formal specification of distributed systems — state machines, temporal formulas, invariants, and model checking TLA+ specifications.

Alloy Analyzer — Lightweight Software Modeling

A practical guide to Alloy Analyzer for formal modeling — relational logic, signatures, facts, predicates, assertions, and automated instance finding.

Z3 Solver — Solving Constraints with SMT

A practical guide to the Z3 SMT solver for constraint solving — propositional logic, arithmetic, arrays, bit vectors, quantifiers, and program verification with Python bindings.

Coq Proof Assistant — Dependently Typed Programming

A step-by-step guide to the Coq proof assistant for formal verification — dependent types, tactics, inductive proofs, and program extraction for verified software.

Isabelle/HOL — Interactive Theorem Proving

A complete guide to Isabelle/HOL for interactive theorem proving — higher-order logic, structured proofs, locales, code generation, and formalizing mathematics.

Dafny — Verified Programming with Contracts

A practical guide to Dafny for verified programming — preconditions, postconditions, loop invariants, and automated verification of imperative programs with contracts.

Separation Logic — Reasoning About Pointers and Heap

A complete guide to separation logic for formal verification — heap reasoning, separating conjunction, frame rule, and automated verification of pointer-manipulating programs.

Correct-by-Construction Design — Refinement and Event-B

A complete guide to correct-by-construction software design — refinement calculus, Event-B, formal model derivation, and deriving implementation from specification.

Industrial Formal Verification — AWS, Intel and Microsoft Case Studies

A practical survey of industrial formal verification — case studies from AWS, Intel, Microsoft, and NASA, with lessons learned and adoption patterns for production environments.

SAT Solvers Explained — DPLL, CDCL and Practical Solving

A practical guide to SAT solvers for formal verification — the DPLL algorithm, conflict-driven clause learning, and using MiniSat and CryptoMiniSat for real-world problems.

SMT Solvers (Z3) Guide — Theory Solving and Program Verification

A complete guide to SMT solvers for formal verification — combining SAT with theory reasoning, using Z3 for arithmetic, arrays, bit vectors, and verifying real software properties.

Static Analysis Tools — Infer, Clang SA and SonarQube Guide

A practical guide to static analysis tools for formal verification — Infer, Clang Static Analyzer, and SonarQube for finding bugs, security vulnerabilities, and code quality issues in production code.

Hoare Logic — Axiomatic Semantics for Program Verification

A complete guide to Hoare logic for program verification — Hoare triples, weakest preconditions, loop invariants, and proving correctness of imperative programs axiomatically.

Formal Verification of Smart Contracts — Solidity, Slither and Certora

A practical guide to formal verification of Solidity smart contracts — property-based testing with Foundry, automated verification with Certora Prover, and static analysis with Slither for Ethereum security.

Probabilistic Model Checking — PRISM and Stochastic Systems

A practical guide to probabilistic model checking for formal verification — discrete-time Markov chains, probabilistic temporal logic, PRISM tool usage, and verifying reliability of stochastic systems.

Why3 Verification Platform — Program Verification with Multiple Provers

A complete guide to Why3 for program verification — WhyML language, weakest precondition calculus, interfacing with SMT solvers and proof assistants, and verifying real programs.

Verification of Reactive Systems — Safety, Liveness and Real-Time Properties

A practical guide to formal verification of reactive systems — safety and liveness properties, synchronous languages, Lustre, and verifying real-time control systems with model checking.

Fairness Properties — Justice, Compassion and Strong Fairness in Verification

A complete guide to fairness in formal verification — weak fairness, strong fairness, compassion, and how fairness assumptions affect liveness proofs in model checking and temporal logic.

Formal Specification Languages — Z Notation, VDM and B-Method

A practical guide to formal specification languages for software design — Z notation for state-based specifications, VDM for model-oriented development, and the B-Method for refinement-based verification.

First-Order Logic — Complete Guide

Learn first-order logic, a formal system extending propositional logic with quantifiers and predicates for expressing mathematical statements precisely.

Higher-Order Logic — Complete Guide

Learn higher-order logic, an expressive formal system allowing quantification over predicates and functions for reasoning about complex mathematical structures.

Modal Logic — Complete Guide

Learn modal logic, an extension of classical logic with operators for necessity and possibility to reason about knowledge, time, and obligations in systems.

Linear Temporal Logic — Complete Guide

Learn linear temporal logic, a formalism with temporal operators like always, eventually, and until to specify and verify properties of reactive systems.

Computation Tree Logic — Complete Guide

Learn computation tree logic, a branching-time temporal logic that reasons over multiple possible execution paths for verifying complex system behaviors.

Hennessy-Milner Logic — Complete Guide

Learn Hennessy-Milner logic, a modal logic for specifying properties of labeled transition systems with necessity and possibility operators and fixed points.

Mu-Calculus — Complete Guide

Learn the mu-calculus, a highly expressive fixed-point logic that subsumes most temporal and modal logics used in formal verification of reactive systems.

Induction Principle — Complete Guide

Learn the induction principle, a mathematical proof technique for establishing properties over recursively defined structures like natural numbers and lists.

Structural Induction — Complete Guide

Learn structural induction, a proof method that reasons about recursively defined data structures by assuming the property holds for all smaller substructures.

Natural Deduction — Complete Guide

Learn natural deduction, a proof calculus with introduction and elimination rules for each logical connective that mirrors natural human reasoning patterns.

Sequent Calculus — Complete Guide

Learn sequent calculus, a formal proof system that uses sequents of the form Gamma entails Delta with left and right inference rules for theorem proving.

Resolution Refutation — Complete Guide

Learn resolution refutation, a proof by contradiction technique that derives empty clauses through repeated resolution steps for automated reasoning systems.

Unification Algorithm — Complete Guide

Learn the unification algorithm, a procedure for finding substitutions that make logical expressions identical for automated theorem proving and type inference.

Matching Algorithm — Complete Guide

Learn the matching algorithm, a restricted form of unification that finds variable substitutions in one expression to match another ground expression pattern.

Rewriting Logic — Complete Guide

Learn rewriting logic, a computational logic where system behavior is specified through rewrite rules defining state transitions and concurrent computations.

Term Rewriting — Complete Guide

Learn term rewriting systems, where terms are transformed using directed equations to model computation, simplify expressions, and analyze program semantics.

Labeled Transition Systems — Complete Guide

Learn labeled transition systems, a formal model of computation consisting of states and labeled transitions representing system behaviors and interactions.

Kripke Structures — Complete Guide

Learn Kripke structures, state-transition graphs with atomic proposition labels used as the semantic foundation for modal and temporal logic model checking.

Petri Nets — Complete Guide

Learn Petri nets, a modeling language for describing distributed systems with places, tokens, and transitions for concurrency and synchronization analysis.

Buchi Automata — Complete Guide

Learn Buchi automata, finite-state automata that accept infinite words used extensively in model checking for verifying liveness properties of reactive systems.

Omega-Automata — Complete Guide

Learn omega-automata, automata over infinite words generalizing Buchi, Rabin, and Streett conditions for verification of non-terminating reactive systems.

Lambda Calculus — Complete Guide

Learn the lambda calculus, a formal system for function definition and application that serves as the foundation for functional programming languages.

Simply Typed Lambda Calculus — Complete Guide

Learn the simply typed lambda calculus, which adds type annotations and a type checker to ensure well-typed programs never encounter runtime type errors.

System F — Complete Guide

Learn System F, a polymorphic lambda calculus with universal types enabling parametric polymorphism and serving as the core of many modern typed languages.

Calculus of Constructions — Complete Guide

Learn the calculus of constructions, a higher-order typed lambda calculus unifying dependent types, polymorphism, and type operators in a single framework.

Martin-Lof Type Theory — Complete Guide

Learn Martin-Lof type theory, an intuitionistic type theory where types are propositions and programs are proofs for constructive mathematics and verification.

Homotopy Type Theory — Complete Guide

Learn homotopy type theory, an interpretation of type theory where types are spaces and equality proofs are paths for formalizing mathematics and verification.

Univalence Axiom — Complete Guide

Learn the univalence axiom, a principle in homotopy type theory stating that equivalent types are equal, transforming mathematical reasoning and proof.

Cubical Type Theory — Complete Guide

Learn cubical type theory, a computational interpretation of homotopy type theory with constructive univalence using cubes as the basis for path reasoning.

Refinement Types — Complete Guide

Learn refinement types, which enrich simple types with logical predicates to precisely capture program invariants like positive integers or sorted lists.

Liquid Types — Complete Guide

Learn liquid types, refinement types automatically inferred via predicate abstraction and SMT solving to verify program properties without manual annotations.

Gradual Typing — Complete Guide

Learn gradual typing, which integrates static and dynamic typing within a single language by allowing optional type annotations with runtime consistency checks.

Ghost Code — Complete Guide

Learn ghost code, specification-only constructs inserted into programs for verification purposes that are erased during compilation with no runtime effect.

Loop Invariants — Complete Guide

Learn loop invariants, properties that hold before, during, and after loop execution forming the foundation for proving correctness of iterative algorithms.

Variant Functions — Complete Guide

Learn variant functions, integer-valued expressions that decrease with each loop iteration to prove program termination and ensure eventual completion.

Preconditions and Postconditions — Complete Guide

Learn preconditions and postconditions, Hoare-style contract specifications defining what a function requires and guarantees for formal program verification.

Weakest Precondition — Complete Guide

Learn weakest precondition calculus, which computes the minimal condition needed before a statement to guarantee a given postcondition after execution.

Strongest Postcondition — Complete Guide

Learn strongest postcondition calculus, which computes the most precise condition guaranteed after program execution for formal software verification tasks.

Verification Condition Generation — Complete Guide

Learn verification condition generation, which produces logical formulas whose validity implies program correctness relative to specifications for checking.

Automated Verification — Complete Guide

Learn automated verification, which uses tools and algorithms to automatically prove program correctness without manual proof construction or user guidance.

Deductive Verification — Complete Guide

Learn deductive verification, a formal approach using logical inference rules and theorem proving to establish program correctness from given specifications.

Compositional Verification — Complete Guide

Learn compositional verification, a modular approach that verifies system components independently and combines guarantees to prove overall system correctness.

Assume-Guarantee Reasoning — Complete Guide

Learn assume-guarantee reasoning, a compositional verification technique where each component assumes behavior of others and guarantees its own behavior.

Rely-Guarantee Reasoning — Complete Guide

Learn rely-guarantee reasoning, a concurrency verification method where each thread relies on environmental stability and guarantees non-interference.

Invariant Generation — Complete Guide

Learn invariant generation, the automated synthesis of inductive invariants that hold at all program points for establishing correctness properties of systems.

Ranking Functions — Complete Guide

Learn ranking functions, well-founded mappings from program states to natural numbers that decrease with each step to prove program termination of loops.

Termination Proving — Complete Guide

Learn termination proving, using well-founded orders, ranking functions, and dependency pairs to establish that programs halt for all possible inputs.

Liveness Proving — Complete Guide

Learn liveness proving, techniques to verify that desirable events eventually occur in reactive systems using temporal logic and fairness constraint properties.

Safety Proving — Complete Guide

Learn safety proving, techniques to verify that nothing bad ever happens in a system by establishing invariants and checking reachable state space properties.

Fairness Constraints — Complete Guide

Learn fairness constraints, conditions ensuring that continuously enabled transitions execute for verifying liveness in concurrent and distributed systems.

Kleene Star Operator — Complete Guide

Learn the Kleene star operator, which forms the reflexive transitive closure of a set of strings, fundamental to regular expressions and automata theory.

Omega-Regular Languages — Complete Guide

Learn omega-regular languages, an extension of regular languages to infinite words using Buchi acceptance for specifying non-terminating system properties.

CSP Process Algebra — Complete Guide

Learn CSP process algebra, a formal language for describing concurrent systems through processes that communicate via synchronized events and channels.

CCS Calculus — Complete Guide

Learn CCS calculus, a process calculus for modeling concurrent systems with communication through named channels and synchronization actions between processes.

Pi-Calculus — Complete Guide

Learn the pi-calculus, a process calculus where channel names can be passed as data enabling mobile systems with dynamically changing communication structures.