11. The trust boundary¶
Every tick, each player's browser sends its controls to the server as a
small piece of JSON. The server passes it to the engine. This is the trust
boundary: the one place where data from outside, which could be anything
at all, becomes an engine value. This chapter reads Adawars.Wire, the
codec at that boundary, which is proved sound and complete.
One encoding per control¶
A control has exactly one encoding:
-- The control wire format, at the trust boundary. A control has exactly
-- one encoding, with fixed key order and no whitespace:
--
-- {"throttle":50,"turn":-100,"fire":false,"kind":"heat_seeker",
-- "flare":false,"boost":true,"arm":false}
Accepting any valid JSON would mean writing, and trusting, a JSON parser. Accepting only the one canonical form keeps the parser small enough to prove. The browser has no difficulty producing exactly that form.
Encode is the definition of the format:
function Encode (C : Control) return String is
(P1 & Image (Natural (C.Throttle))
& P2 & Signed_Image (Integer (C.Turn))
& P3 & Bool_Image (C.Fire)
& P4 & Name (C.Kind)
& P5 & Bool_Image (C.Flare)
& P6 & Bool_Image (C.Boost)
& P7 & Bool_Image (C.Arm)
& P8)
& joins strings. P1 to P8 are the fixed pieces between the fields,
such as {"throttle":.
Sound¶
function Decode (S : String) return Decoded
with
Pre => S'First = 1,
Post => (if Decode'Result.Ok then S = Encode (Decode'Result.Control));
The postcondition is soundness: if Decode accepts a string, that string
is exactly the encoding of the control it returns. Nothing else gets
through: no extra spaces, no leading zeros, no trailing junk, no turn of 101.
The trick that makes this provable is in Decode itself:
function Decode (S : String) return Decoded is
(if S'Length not in Min_Length .. Max_Length
then (Ok => False, Why => Wrong_Length)
elsif not Parse (S).Ok then (Ok => False, Why => Parse (S).Why)
elsif S /= Encode (Parse (S).Control)
then (Ok => False, Why => Not_Canonical)
else (Ok => True, Control => Parse (S).Control));
After parsing, Decode re-encodes what it parsed and insists that it gets
the input back. The parser can then be a little forgiving, and need not be
proved exact, because soundness comes from the final comparison.
And Pre => S'First = 1? Ada strings can start at any index. A slice of a
longer string keeps the original indices. The precondition saves the parser
from handling arbitrary offsets. The server renumbers each message from 1
before decoding it.
Try it: drop the check¶
elsif not Parse (S).Ok then (Ok => False, Why => Parse (S).Why)
- elsif S /= Encode (Parse (S).Control)
- then (Ok => False, Why => Not_Canonical)
else (Ok => True, Control => Parse (S).Control));
postcondition might fail, cannot prove S = Encode (Decode'Result.Control)
Without the comparison, the parser's leniency becomes the format, and the prover can no longer show that only canonical strings get in.
Complete¶
Soundness alone is easy to achieve: reject everything. The other half is completeness: every encoding decodes, to the control it encodes. It is a lemma:
-- Every encoding decodes, to the control it encodes.
procedure Lemma_Complete (C : Control)
with
Ghost,
Global => null,
Post =>
Decode (Encode (C)).Ok and then Decode (Encode (C)).Control = C;
Together, the two say that Decode and Encode are exact inverses on the
canonical form. The browser can never send a valid control that is refused,
and nothing else is accepted.
Completeness is the hardest proof in the engine, because the prover has to
follow Encode (C) through every step of the parser for every possible
control. Three techniques make it go through.
A parser written for the prover. The parser is a chain of expression functions, one per field, each reading a field and passing on everything read so far. Numbers are read as one to three digits with no loop:
-- One to three digits at P, not followed by a fourth.
function Unsigned_At (S : String; P : Position) return Read is
(if not Is_Digit (S, P) then Bad
elsif not Is_Digit (S, P + 1) then
(Ok => True, Value => Val (S, P), Next => P + 1)
Small lemmas, each in its own context. One lemma places every piece of
the encoding and says what reading each field gives (Lemma_Fields). Others
state single facts the provers will not find alone, such as this one:
-- A word whose first letter is not at P is not at P.
procedure Lemma_Not_At (S : String; P : Position; Lit : String)
Cutting the context. Facts pile up through a long proof, and every fact
the prover holds makes each step slower. pragma Assert_And_Cut proves a
condition, then forgets everything else:
pragma Assert_And_Cut
(E = Encode (C)
and then E'First = 1
and then E'Length in Min_Length .. Max_Length
and then Fits (E)
and then Parse (E).Ok
and then Parse (E).Control = C);
After it, the prover knows only those six facts, which are exactly what the
last step through Decode needs.
Tested as well¶
The tests decode the encoding of every possible control and check each comes back unchanged:
-- Every control there is: every throttle and turn, and both choices
-- of fire, weapon, flare, boost and arm.
for T in Throttle_Level loop
for R in Turn_Command loop
...
D : constant Decoded := Decode (Encode (C));
begin
Count := Count + 1;
if not (D.Ok and then D.Control = C) then
Check (False, "round trip " & Encode (C));
end if;
...
Check (Count = 101 * 201 * 2**5, "every control checked");
A for loop over a type, for T in Throttle_Level, runs over every value
of it. This is a run-time cross-check of what the lemma proves. It is not needed, but if the proof
ever went wrong in some way nobody has thought of, it would disagree.
Recap¶
- At a trust boundary, accept one canonical form, and prove the parser.
- Soundness: what is accepted is exactly an encoding. Re-encoding and comparing gets you there cheaply.
- Completeness: every encoding is accepted. It is a lemma, and the harder proof.
- Long proofs need structure: small lemmas in small contexts, and
Assert_And_Cutto drop facts that are no longer needed.