A formal method gives you a precise guarantee: the behaviour described by a specification written in mathematical notation holds for all the cases the specification allows, not only for the ones you tried. It costs time and expertise, so it pays off when two conditions hold together: an error costs far more than the verification, and the property to be guaranteed can be written down exactly. If the first is missing, tests and review are enough; if the second is missing, the formal method rigorously proves something that was not the right thing. This article opens the series with the criteria for deciding, a public case studied on the original document, and a program that shows where testing stops.
What a formal method proves, and what it does not
Take the cart of an online shop and the rule "if the payment fails, the items stay in the cart and no order is created". With a test you run a payment that fails and look at the result: you check one case, the one you thought of trying. With a formal method you write the rule as a formula over the states of the system and a tool checks it on all the reachable states of the model. A test looks for bugs in the cases you run; formal verification rules out a class of bugs in all the cases the model describes.
The words "the model describes" are the limit. Verification establishes that a program, or a design, satisfies a specification; it does not establish that the specification is the one you needed. These are two different questions, and formal methods answer well only the first: the other remains the work of whoever understands the problem, the domain of the data and the physical environment. The case that follows shows where this difference falls.
Ariane 501: the datum that was not in the specification
On 4 June 1996 the first flight of the Ariane 5 launcher ended with the destruction of the rocket about 37 seconds after the launch instant H0. The report of the inquiry board, dated 19 July 1996, reconstructs the chain of events backwards, and the technical starting point is precise: the software of the inertial reference system (SRI) performed a conversion from a 64-bit floating-point number to a signed 16-bit integer, the value was too large for that format and the conversion raised an operand error. The conversion concerned an internal alignment variable called BH (Horizontal Bias, related to the horizontal velocity measured by the platform), whose value on Ariane 5 was much higher than expected because the first part of the trajectory differs from that of Ariane 4.
Three details of the report matter to anyone deciding whether to invest in verification. First: the vulnerability analysis had identified seven variables at risk of an operand error, but only four were protected; the other three, BH among them, had been left uncovered on the reasoning that they were physically limited or had a wide safety margin, a reasoning that proved wrong for BH. Second: the specification of the SRI did not contain the trajectory data of Ariane 5, and for this reason no ground test was run with the new trajectory; the report states that such a test would have brought the failure mechanism to light. Third: faced with the exception the software shut down the processor, as the specification prescribed, and since the two SRIs ran the same software the second one stopped for the same reason.
The lesson for this article is that none of the three facts is a logic error in the code: the function did what the specification asked of it, on an input domain that the specification did not state. A proof of correctness with respect to that specification cannot notice a datum that the specification does not contain. The report specifies that no use of the trajectory data is recorded for analysing the behaviour of the unprotected variables: that step, computing the ranges of the values from the physics of the flight, is what formal methods ask to make explicit, together with the verification of the code.
Three ways to read an addition that leaves the type
Hoare, in his 1969 paper on the axiomatic basis of programming, observes that arithmetic properties hold only if the implementation satisfies the chosen axioms, and compares three interpretations of finite arithmetic: strict (the out-of-range result does not exist), firm boundary (the result stops at the limit) and modulo (the result wraps around). The program below applies the three readings to a signed 16-bit integer, the range of the Ariane conversion, and then compares two ways of looking for the error on a domain that is a test scenario of ours, not real data: the specification declares the values from 0 to 30000, the physical system produces values from 0 to 99999.
import random
LO, HI = -32768, 32767 # range of a signed 16-bit integer
def strict(x):
"""Strict interpretation: out of range, the operation does not exist."""
if not LO <= x <= HI:
raise OverflowError(f"{x} does not fit in signed 16 bits")
return x
def saturation(x):
"""'Firm boundary' interpretation: the value stops at the limit."""
return max(LO, min(HI, x))
def modulo(x):
"""Modulo 2**16 interpretation: the value wraps around."""
return (x + 32768) % 65536 - 32768
print("x strict saturation modulo")
for x in (100, 32767, 32768, 40000, -32769):
try:
s = strict(x)
except OverflowError:
s = "OverflowError"
print(f"{x:<8} {str(s):<14} {saturation(x):<12} {modulo(x)}")
# Test scenario: the specification declares the domain 0..30000,
# the physical system instead produces values 0..99999.
SPEC_DOMAIN = range(0, 30001)
REAL_DOMAIN = range(0, 100000)
def conversion_ok(x):
try:
strict(x)
return True
except OverflowError:
return False
random.seed(7)
sample = [random.choice(SPEC_DOMAIN) for _ in range(10000)]
failed_test = sum(not conversion_ok(x) for x in sample)
failed_all = sum(not conversion_ok(x) for x in REAL_DOMAIN)
print("\nTest: 10000 values from the specification domain ->", failed_test, "failed conversions")
print("Exploration of the whole real domain (", len(REAL_DOMAIN), "values ) ->", failed_all, "failed")
print("Closed-form check:", len(REAL_DOMAIN) - (HI + 1))
# Output:
# x strict saturation modulo
# 100 100 100 100
# 32767 32767 32767 32767
# 32768 OverflowError 32767 -32768
# 40000 OverflowError 32767 -25536
# -32769 OverflowError -32768 32767
#
# Test: 10000 values from the specification domain -> 0 failed conversions
# Exploration of the whole real domain ( 100000 values ) -> 67232 failed
# Closed-form check: 67232
The initial table shows that 32768 is the first value that does not fit: the strict reading raises OverflowError, saturation returns 32767, modulo returns -32768, that is a negative number in place of a positive one. None of the three is "right" in absolute terms, and the choice has to be written in the specification. The second part is the point of the program: ten thousand values drawn with a fixed seed from the declared domain (random.seed(7)) produce no error at all, while the exploration of the whole physical domain finds 67232 failed conversions out of 100000. The second count, in closed form, is 100000 - 32768 = 67232 and it matches.
If you drop the comparison with the real domain and check only the declared one, the program says everything is fine: it is the same situation as in the report, in miniature. The test did not get it wrong, it sampled from the set that the specification pointed it to. This is why, before choosing a verification tool, the most profitable work is writing down where the data come from: physical ranges, units of measure, frequency of events. The program was run with Python 3.14.4; the range from -32768 to 32767 is that of the signed 16-bit format cited in the report.
What you can do at each level of effort
There is no such thing as "the" formal method: there is a scale of techniques with growing effort and growing guarantees. The list below is ordered from the lightest to the most demanding, and the order matters because each step requires more skills and time than the previous one.
- Static type system (Rust, TypeScript in
strictmode, Haskell): the compiler rejects whole classes of errors before execution, and it does so without you writing a separate specification. - Contracts and
assert: you write preconditions and postconditions in the code and check them at runtime, during tests. - Property-based testing (Hypothesis, QuickCheck): you describe a property and the framework generates many inputs; it is not a proof, but it explores more than hand-written tests.
- Model checking (SPIN, TLC): you describe the system as a model and the tool explores all the reachable states; it requires learning a specification language.
- Proof assistants (Rocq, Lean, Isabelle): you build a proof checked by the machine; it is the level with the strongest guarantees and the highest cost.
The criterion that holds the scale together is the question "what do you want to be able to say at the end?". With types you say that certain errors do not exist; with contracts you say that, in the tests run, none violated the rule; with model checking you say that in the model no behaviour violates it; with a proof assistant you say that it holds for the program itself. For a module of a website the first two steps are enough; for a distributed protocol model checking starts to pay off, as the following case shows. The last step has a public example: the CompCert project describes its C compiler as having a machine-checked proof that the generated code behaves as the semantics of the source prescribes. The project declares compatibility with Rocq 9.2, the proof assistant formerly known as Coq.
What a company that tried it has shown
The most useful source on costs and benefits in a company is the account by the engineers of Amazon Web Services. The text, in the working version of 29 September 2014, says that since 2011 the engineers have used the formal specification language TLA+ and model checking for the designs of critical systems; it reports that seven teams were using it and that engineers of every level learned TLA+ from scratch and got useful results in 2-3 weeks. The case told first is DynamoDB: the TLC model checker found a bug that could lose data, and the shortest error trace showing it contained 35 high-level steps; the flaw had gone unnoticed by design reviews, code reviews and tests. The table in the text lists for each system the lines of specification (from 102 to 939) and the bugs found.
The authors also write where the method does not help: it is not useful against sustained performance degradation caused by feedback loops, and one case in the table shows a liveness bug that was not found because that property had not been checked. This confirms the criterion from the start: the investment pays off where the cost of the error is high, the system is concurrent (the combinations of events exceed the reviewer's imagination) and the property can be written in a few hundred lines.
Where it does not pay off
The opposite boundary is just as sharp, and it concerns the relation between the cost of verification and the cost of the error.
- A newsletter sign-up form: the behaviour is linear and an error is fixed in an hour; tests, static analysis and review are enough.
- A product feature still being explored: you do not yet have a stable specification, and a formal method on a requirement that changes every week is wasted work.
- An existing system with no budget to review it: a specification written after the fact on code nobody understands becomes a second document to maintain.
In all three cases the common thread is the instability of the requirement or the low severity of the error. This does not mean that formal methods are "for big companies": if in a small project there is a single piece where the error costs a lot (an amount calculation, a synchronisation protocol), that piece deserves the highest level, and the rest can stay with tests.
A rule for deciding in your project
Before opening a tool, answer four questions in writing, in order, and stop at the first one that gets a negative answer.
- What happens, and to whom, if this piece gets it wrong? If the answer is "we republish tomorrow", stop.
- Can you write in one sentence the property to be guaranteed, for example "the balance never becomes negative"?
- Do you know where the input data come from and in which ranges, measured and not assumed?
- Is the piece small and stable enough to be modelled in a few hundred lines?
The questions are in order because each presupposes the previous one: there is no point in modelling what you cannot say in words, nor in declaring a range you have not measured (it is the error of the Ariane case). If you reach the end with four yeses, you can choose the step of the scale from the previous section according to how stringent the guarantee has to be. The next articles in the series give you the tools: in the second the logic for writing the specification, in the third automata for describing behaviour, in the fourth temporal logic for properties over time.
Exercises
1. In the program, set REAL_DOMAIN to range(0, 70001). How many conversions fail?
Solution
The values from 32768 to 70000 fail, that is 70001 - 32768 = 37233. A second count: counting in Python the x with x > 32767 in the range gives 37233.
2. If the real domain were range(-50000, 50000), how many conversions fail? Does the value -32768 make the strict reading fail?
Solution
The values below -32768 (from -50000 to -32769) and above 32767 (from 32768 to 49999) fail: 2 × (50000 - 32768) = 34464, confirmed by a direct count. -32768, instead, fits: the range of signed 16 bits goes from -32768 to 32767.
Frequently asked questions
Do formal methods replace tests?
No. They check properties on a model or on a specification; tests check the real program in a real environment. The Amazon Web Services engineers write in the account cited that tests, reviews and the other techniques remain necessary, and that model checking is added for the design flaws that tests do not find.
Does proving a program correct mean it has no bugs?
It means it satisfies the specification you wrote. If the specification has a wrong or missing datum, like the trajectory data in the Ariane 501 case, the proof succeeds all the same. This is why the question about the origin of the data comes before the choice of tool.
Do I have to learn Rocq (formerly Coq) or Isabelle to start?
No. The Amazon Web Services account describes engineers who learned TLA+ in two or three weeks and got results; a proof assistant is the top step of the scale and is needed only where the guarantee has to hold for the code itself.
What you can do now
You can say in what way a test and a formal verification answer different questions, and you can explain with the inquiry report why a proof that is correct with respect to an incomplete specification is not enough. You can choose a step of the scale (types, contracts, property-based tests, model checking, proof assistants) according to the cost of the error and the stability of the requirement, and you have four questions to ask before opening a tool. The program has left you a reusable method: always check the domain you declared against the one the system produces.
This is the first article of the Formal Methods series. The next one is Logic for specification: propositional and first-order; the last of this group of three is Finite state machines and automata.
The last article in the series, Petri Nets: structure, markings, reachability, liveness and safety, closes the path with a model that is an alternative to the state machine.
Sources
- Ariane 501 Inquiry Board, Ariane 5 Flight 501 Failure: Report by the Inquiry Board (Paris, 19 July 1996) - scanned PDF downloaded and the Foreword and pages 1-7 of the report read (description of the failure, chain of events, conversion from 64-bit floating point to signed 16-bit, variable BH, seven variables at risk and three unprotected, absence of the trajectory data in the specification, shutdown of the processor, qualification and testing); consulted on 2026-11-13
- C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM 12(10), 1969, pp. 576-580 - copy hosted by a university course, pages 577-578 read (Table II with the three interpretations of finite arithmetic; axioms and rules); consulted on 2026-11-13
- C. Newcombe, T. Rath, F. Zhang, B. Munteanu, M. Brooker, M. Deardeuff, Use of Formal Methods at Amazon Web Services (working version, 29 September 2014) - text downloaded and read in full: use of TLA+ since 2011, seven teams, learning in 2-3 weeks, table of the systems (from 102 to 939 lines of specification), DynamoDB bug with a 35-step trace, unchecked liveness, limits of the method; the version published in Communications of the ACM 58(4), 2015 (DOI 10.1145/2699417) was verified only in the metadata on Crossref; consulted on 2026-11-13
- CompCert project, home page - page read: the description of the compiler as verified with a machine-checked proof; consulted on 2026-11-13
- Rocq Prover, About - page read: the Rocq Prover was called the Coq Proof Assistant; consulted on 2026-11-13
The program was run with Python 3.14.4 (python3 -I), twice with identical output; the numbers of the domain (0-30000 declared, 0-99999 physical) are a scenario built for the example and do not come from the report.
Article published 2026-09-28, graduate level.
Commenti
Caricamento commenti...
Sign in to comment