Skip to main content

Embedded Systems · State-machine verification and safety boundaries

A two-door airlock is modelled by Boolean variables L and R, each 1 when that door is…

Problem

Embedded Systems practice problem

A two-door airlock is modelled by Boolean variables LL and RR, each 11 when that door is open and 00 when it is closed. Write a state as the bit pair LRLR. The safety invariant isI:¬(L∧R).I:\quad \lnot(L\land R).The intended controller exposes four guarded commands, evaluated against the current state and executed atomically:openL: if R=0 then L←1,openR: if L=0 then R←1,closeL: L←0,closeR: R←0.\begin{align*} \mathrm{openL}&:\ \textbf{if }R=0\textbf{ then }L\leftarrow 1,\\ \mathrm{openR}&:\ \textbf{if }L=0\textbf{ then }R\leftarrow 1,\\ \mathrm{closeL}&:\ L\leftarrow 0,\\ \mathrm{closeR}&:\ R\leftarrow 0. \end{align*}The system starts at 0000. A command whose guard fails is a no-op.

A proposed firmware defect implements openL\mathrm{openL} and openR\mathrm{openR} as two independent check-then-write actions in the same evaluation cycle. Both guards are evaluated against the same \emph{pre-cycle} values of LL and RR, and both passing writes commit.

1. Starting from 0000, enumerate every state reachable by a finite
sequence of the four guarded commands. Prove that the reachable set is exactly {00,10,01}\{00,10,01\}.

2. Prove II by induction on guarded executions. Then exhibit one
buggy simultaneous pair of independent opens from 0000 that reaches 1111, and confirm that 1111 falsifies II.

3. Audit both sentences: (i) “1111 is reachable under the guards,
because one can open LL and then open RR”; (ii) “even the non-atomic simultaneous pair cannot reach 1111, because one action must observe the sibling's committed post-state before evaluating its own guard.”

Do not replace the interlock by a watchdog, CRC, or lockstep-core argument, and do not encode the doors as a continuous hybrid automaton.

Hint

Hint

From 0000 the guarded opens reach 1010 and 0101. From 1010, openR\mathrm{openR} is disabled and closeL\mathrm{closeL} returns to 0000. The symmetric statement holds at 0101.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Embedded Systems sample problem: Try the free sample problem.

More Embedded Systems practice problems

Back to Embedded Systems

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.