Formal Specification Languages â Z Notation, VDM and B-Method
In this tutorial, you'll learn about Formal Specification Languages. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Formal specification languages use mathematical notation to describe software behavior precisely before implementation, enabling early detection of design flaws and providing a foundation for Formal Verification of correctness.
Learning Path
flowchart LR A["First-Order Logic"] --> B["Formal Specification
Z, VDM & B-Method"] B --> C["Correct-by-Construction Design"] B --> D["TLA+ & Alloy"] style B fill:#f90,color:#fff,stroke-width:2px
What you'll learn: Writing state-based specifications in Z notation, model-oriented specifications in VDM, refinement-based development with the B-Method, and how each approach supports Formal Verification.
Why it matters: Formal specifications are the starting point of every Formal Verification effort. A precise specification catches design errors before any code is written, reducing development costs.
Real-world use: DodaZIP's compression algorithm was first specified in Z notation, allowing designers to prove buffer-size invariants before implementing the optimized Rust version.
Prerequisites
First-order logic, set theory, and basic understanding of software design and data structures.
What Are Formal Specification Languages?
Formal specification languages use mathematical constructs to describe what a system does without prescribing how it does it. They eliminate ambiguity from natural-language requirements and enable automated reasoning about consistency, completeness, and correctness.
Three major schools: Z notation (state-based, using schemas), VDM (model-oriented, with explicit invariants), and the B-Method (refinement-based, with automated proof obligations).
Step-by-Step: Z Notation
Z uses schemas to describe the state space and operations of a system. A schema has a declaration part and a predicate part.
Step 1: Define a State Schema
class ZSchema:
def __init__(self, name, declarations, predicates):
self.name = name
self.declarations = declarations
self.predicates = predicates
def check_invariant(self, state):
for pred in self.predicates:
if not pred(state):
return False, f"Invariant violated: {pred.__doc__}"
return True, "Invariant holds"
def balance_non_negative(state):
"""balance >= 0"""
return state["balance"] >= 0
def owner_exists(state):
"""owner in allowed_owners"""
return state["owner"] in state.get("allowed_owners", {state["owner"]})
bank_schema = ZSchema("BankAccount", {
"owner": "PERSON",
"balance": "INTEGER",
"allowed_owners": "PERSON_SET"
}, [balance_non_negative, owner_exists])
state = {"owner": "Alice", "balance": 100, "allowed_owners": {"Alice", "Bob"}}
ok, msg = bank_schema.check_invariant(state)
print(f"Schema check: {msg}")
Expected output:
Schema check: Invariant holds
Step 2: Define an Operation Schema
class OperationSchema:
def __init__(self, name, inputs, outputs, preconditions, postconditions):
self.name = name
self.inputs = inputs
self.outputs = outputs
self.preconditions = preconditions
self.postconditions = postconditions
def is_feasible(self, state, inputs):
for pre in self.preconditions:
if not pre(state, inputs):
return False, f"Precondition failed: {pre.__doc__}"
return True, "Operation feasible"
def sufficient_balance(state, inputs):
"""amount <= balance"""
return inputs["amount"] <= state["balance"]
def positive_amount(state, inputs):
"""amount > 0"""
return inputs["amount"] > 0
withdraw_op = OperationSchema(
"Withdraw",
{"amount": "INTEGER"},
{"success": "BOOLEAN"},
[sufficient_balance, positive_amount],
[]
)
state = {"balance": 100}
ok, msg = withdraw_op.is_feasible(state, {"amount": 30})
print(f"Withdraw feasible: {msg}")
ok2, msg2 = withdraw_op.is_feasible(state, {"amount": 200})
print(f"Withdraw feasible: {msg2}")
Expected output:
Withdraw feasible: Operation feasible
Withdraw feasible: Precondition failed: amount <= balance
Step 3: Schema Composition
class SchemaComposition:
def __init__(self, schemas):
self.schemas = schemas
def compose(self, state, inputs):
for schema, s_inputs in zip(self.schemas, inputs):
feasible, msg = schema.is_feasible(state, s_inputs)
if not feasible:
return False, f"Failed at {schema.name}: {msg}"
return True, "All schemas feasible"
deposit_op = OperationSchema("Deposit", {"amount": "INTEGER"}, {}, [positive_amount], [])
comp = SchemaComposition([deposit_op, withdraw_op])
ok, msg = comp.compose({"balance": 50}, [{"amount": 100}, {"amount": 30}])
print(f"Composition: {msg}")
Expected output:
Composition: All schemas feasible
Step-by-Step: VDM-SL
VDM uses explicit invariants on data types and pre/post conditions on operations.
Step 1: Define a VDM Type
class VDMType:
def __init__(self, name, invariant):
self.name = name
self.invariant = invariant
def check(self, value):
return self.invariant(value)
class VDMRecord:
def __init__(self, fields):
self.fields = fields
def create(self, values):
instance = {}
for name, typ in self.fields.items():
instance[name] = values[name]
return instance
PositiveInt = VDMType("PositiveInt", lambda x: isinstance(x, int) and x > 0)
print(f"5 is PositiveInt: {PositiveInt.check(5)}")
print(f"-3 is PositiveInt: {PositiveInt.check(-3)}")
Expected output:
5 is PositiveInt: True
-3 is PositiveInt: False
Step 2: VDM Operation with Pre/Post
class VDMSpecification:
def __init__(self):
self.invariants = []
def add_invariant(self, name, check_fn):
self.invariants.append((name, check_fn))
def verify_transition(self, before, after, operation_name):
for name, check in self.invariants:
if not check(before):
return False, f"Invariant {name} violated before {operation_name}"
if not self.apply_op(before, after, operation_name):
return False, "Transition does not satisfy operation spec"
for name, check in self.invariants:
if not check(after):
return False, f"Invariant {name} violated after {operation_name}"
return True, "Transition verified"
def apply_op(self, before, after, op):
if op == "debit":
return after["balance"] == before["balance"] - before.get("last_amount", 0)
return True
def balance_check(state):
return state.get("balance", 0) >= 0
spec = VDMSpecification()
spec.add_invariant("non_negative_balance", balance_check)
before = {"balance": 100, "last_amount": 30}
after = {"balance": 70, "last_amount": 30}
ok, msg = spec.verify_transition(before, after, "debit")
print(f"VDM transition: {msg}")
Expected output:
VDM transition: Transition verified
Step-by-Step: B-Method
The B-Method uses stepwise refinement from an abstract specification to concrete implementation, with proof obligations at each step.
Step 1: Abstract Machine
class BMachine:
def __init__(self, name, variables, invariant, operations):
self.name = name
self.variables = variables
self.invariant = invariant
self.operations = operations
def prove_invariant_preserved(self, state, op_name, inputs):
for inv in self.invariant:
if not inv(state):
return False, f"Invariant violated before {op_name}"
op = self.operations.get(op_name)
if not op:
return False, f"Operation {op_name} not found"
new_state = op(state, inputs)
for inv in self.invariant:
if not inv(new_state):
return False, f"Invariant violated after {op_name}"
return True, f"Invariant preserved by {op_name}"
def prove_refinement(self, concrete, abstraction_map):
for c_var, a_var in abstraction_map.items():
concrete_val = concrete.get(c_var)
abstract_val = abstraction_map[c_var](concrete)
if concrete_val != abstract_val:
return False, f"Refinement mismatch for {c_var}"
return True, "Refinement verified"
def inv_total(state):
return "total" in state and state["total"] >= 0
def credit(state, inputs):
return {"total": state["total"] + inputs["amount"]}
def debit(state, inputs):
amt = inputs["amount"]
if amt <= state["total"]:
return {"total": state["total"] - amt}
return state
machine = BMachine("Account",
["total"],
[inv_total],
{"credit": credit, "debit": debit}
)
state = {"total": 100}
ok, msg = machine.prove_invariant_preserved(state, "debit", {"amount": 30})
print(f"B-Method: {msg}")
Expected output:
B-Method: Invariant preserved by debit
Step 2: Proof Obligation Generation
class ProofObligation:
def __init__(self, name, formula):
self.name = name
self.formula = formula
def verify(self, interpreter):
result = interpreter(self.formula)
return result
def po_interpreter(formula):
if "invariant_preserved" in formula:
return True
if "initialization_establishes" in formula:
return True
return False
po = ProofObligation("INV1", "invariant_preserved(credit)")
print(f"Proof obligation {po.name}: {po.verify(po_interpreter)}")
Expected output:
Proof obligation INV1: True
Common Errors
1. Ambiguous Preconditions
Operations with weak preconditions can be called in too many states, making the specification too restrictive. Weak postconditions make the specification too permissive.
2. Under-specified State Spaces
Leaving out critical state variables (like whether a device is initialized) leads to specifications that cannot distinguish important system configurations.
3. Not Checking Invariant Preservation
Every operation must preserve the state invariant. Forgetting to verify this is the most common error in formal specification.
4. Over-abstracting in Early Refinements
First refinement steps should add minimal detail. Adding implementation details too early makes proof obligations harder and hides design decisions.
5. Ignoring Non-Determinism
Specifications may be non-deterministic intentionally. Refining to a deterministic implementation must respect all possible abstract behaviors.
Practice Questions
Q1: What is a Z schema?
A structured specification element with a declaration part (variables and types) and a predicate part (constraints and invariants).
Q2: What is the difference between Z and VDM?
Z is model-based with schemas and set theory. VDM uses explicit pre/post conditions and data type invariants with a more operational style.
Q3: What is refinement in the B-Method?
The Process of transforming an abstract specification into a concrete implementation through correctness-preserving steps, each generating proof obligations.
Q4: What is a proof obligation in B?
A theorem that must be proved to show that a refinement step preserves correctness, such as invariant preservation or operation feasibility.
Q5: Why use formal specifications at all?
They eliminate ambiguity, enable automated consistency checking, provide documentation that can be verified against implementation, and catch design errors early.
Challenge
Write a Z specification for a library book management system. Define state schemas for books (with status: available, borrowed, reserved) and members. Specify operations for borrowing, returning, and reserving books. Include invariants that prevent a book from being borrowed by two members simultaneously.
FAQ
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro