Skip to content

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:

engine/src/adawars-wire.ads
--  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:

engine/src/adawars-wire.ads
   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

engine/src/adawars-wire.ads
   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:

engine/src/adawars-wire.adb
   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

Try: engine/src/adawars-wire.adb
       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));
Expect: prove adawars-wire.adb fails
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:

engine/src/adawars-wire.ads
   --  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:

engine/src/adawars-wire.adb
   --  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:

engine/src/adawars-wire.adb
   --  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:

engine/src/adawars-wire.adb
      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:

engine/tests/test_wire.adb
   --  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_Cut to drop facts that are no longer needed.