Saltar al contenido ForoHackers

A 20-line TLA+ spec finds the lost update before you write the code

Sistemas distribuidosMétodos formales y verificaciónPruebas
#1042 · race_condition_rita · · Denunciar

People hear "formal methods" and picture a year of proofs. Here is a tiny spec that finds the classic lost update: two processes each do counter = counter + 1 as a read followed by a separate write.

---- MODULE LostUpdate ----
EXTENDS Naturals
VARIABLES counter, tmp, pc
Procs == {1, 2}

Init == /\ counter = 0
        /\ tmp = [p \in Procs |-> 0]
        /\ pc  = [p \in Procs |-> "read"]

Read(p)  == /\ pc[p] = "read"
            /\ tmp' = [tmp EXCEPT ![p] = counter]
            /\ pc'  = [pc EXCEPT ![p] = "write"]
            /\ UNCHANGED counter

Write(p) == /\ pc[p] = "write"
            /\ counter' = tmp[p] + 1
            /\ pc' = [pc EXCEPT ![p] = "done"]
            /\ UNCHANGED tmp

Next == \E p \in Procs : Read(p) \/ Write(p)
Spec == Init /\ [][Next]_<<counter, tmp, pc>>

Correct == (\A p \in Procs : pc[p] = "done") => counter = 2
====

Tell the model checker to check Correct as an invariant (and turn off the deadlock check, since the system ends when everyone is "done"). It reports a counterexample trace in a second:

  1. P1 reads 0.
  2. P2 reads 0.
  3. P1 writes 1.
  4. P2 writes 1. Both done, counter = 1.

The trace is the bug report. Make Read and Write one atomic step (or add a lock variable), and the invariant holds over every interleaving, not just the ones your tests happened to hit.

The failure model here: processes never crash, steps interleave arbitrarily. That is small, and it is already enough to catch a bug that code review misses.

#1539 · mutex_mike · · Denunciar

I love that the counterexample is a four-line timeline. The thing I tell sceptical colleagues: the model checker does exhaustive interleaving and your brain does the three most likely ones.

#1540 · lambda_llama · · Denunciar

Specification as a state machine plus an invariant. The spirit is the same as types: describe what can never happen, and let the machine tell you where you were wrong. Also, the glorious UNCHANGED, a keyword that exists because you must say what does not change.

#1541 · two_phase_commitment · · Denunciar

I turned my last design review into a spec like this for the transaction retry logic. Found a lost update in the first run. The design had been "approved" by five people, myself included.

#1542 · legacy_cobol_whisperer · · Denunciar

"Show me what happens if the machine loses power between these two lines" is the same exercise on paper. The spec just does it for you faster and without feelings.

Inicia sesión o únete para responder.