Sunday, February 15, 2009

JSON protocols (part 1)

For a long time I have been interested in describing protocols. In 2002 I published a contract system called UBF for defining protocols. This scheme was never widely adopted - perhaps it was just to strange...

I have revised UBF and recast it in a form which I call JSON Protocols - since JSON is widely implemented, this method of described protocols might be more acceptable.

What's the problem?

Client and server interaction should be regulated by some kind of contract that is independent of both the client and server. If the client-server interaction fails, then it should be evident by examining the contract which of the parts in the system has failed. Is the problem in the client or the server?

To simplify our problem we will assume that the client and server interact by exchanging JSON messages and we will add a form of contact that will allow us to check that the sequence of messages is correct.

The File Server Contract

We'll start with a simple example and build a formal description of a file server. I'll use the familiar notion of a finite state machine to describe the operations of the server.

The behaviour of the server is completely specified by a set of
4-tuples of the form:

State x RequestMessage -> ResponseMessage x StateOut

We'll start our specification of the file server somewhere in the middle of a session. We'll assume that users must be authenticated, but we'll show how they are authenticated later.

Let's assume the server is in the state ready - meaning it is ready to accept a request. We can start by defining two state transitions:

ready x getFile -> file x ready;
ready x getFile -> noFile x stop;

This means that if our machine is in the state ready and receives a getFile message it will respond by either sending a file message and transitioning to the ready state or it will respond with a noFile message and transition to the stop state.

Here getFile and file are messages and ready and stop are states.

Attached to the message is some data structure that accompanies the messages.
We can defined these data structures as follows:

data[getFile] = {fileName:string};
data[file] = {fileName:string, fileData:string};

Having defined the data we turn to the wire protocol - what data is actually sent between the client and the server? To answer this we will give a JSON example.

Suppose we want to fetch a file called "index.txt", assume also that the content of the file is "abc" then our contract says that the following JSON terms must be exchanged:

Request =
{msg:"getFile", data:{fileName:"index.txt"}}

Response =
data:{fileName:"index.txt", fileData:"abc"},
Note that exactly this interchange must take place. If either of the messages is incorrectly typed the contract checker can detect the error and determine whether the client or server has violated the contract.
There is a simple relation between the format of the message that is actually exchanged on the wire and the, algebraic specification of the messages.

[note - I have taken liberty with JSON notation here and omitted the quote marks preceding the tags in the object name, strictly I should have written {"msg":"file" etc., but I have written msg:"file"]

What happens if a file doesn't exist? We had a rule for this:

ready x getFile -> eNoFile x stop;

The reply message eNoFile has no associated data, so no data description is necessary.

As an example, suppose we request the file "badfile" which does not exist. This is what we would see "on the wire".

Request = {msg:"getFile", data:{fileName:"badfile"}}
Response = {msg:"eNoFile", state:"stop"}

Observe that the eNoFile message has no associated data.

Why do we send the state back in the response message?

This is to avoid the situation where the server performs a silent state change that cannot be observed by the client. Suppose we have two rules:

a x s1 -> c x s2
a x s1 -> c x s3

When we send an a message we always receive a c message, but we cannot tell if the server changed to state s2 or s3. To make things clearer we always include the new state in the reply.

Now that we've seen what happens in the middle of a session, we can include details of the login and authentication phase.

login x start -> challenge x wait;
response x wait -> ok x ready;
response x wait -> badpassword x stop;

data[login] = {name:string};
data[challenge] = {salt:string};
data[response] = {md5:string};

Once we are ready we might want to list files:

ready x listFiles -> files x ready;
ready x logout -> stop;

data[files] = [{filename:string}];

This completely (and formally specifies the behaviour of a file sever)

Adding time

We can easily add time to our specification:

read x getFile -> file x read within 2 seconds;

This means that we must respond within 2 seconds.

What else?

We need some meta-information, the version number and name of the protocol, and an introspection mechanism.


I've been a bit sloppy with notation here and used a notation that I hope is 'self-evident'. The state machine syntax is trivial:

StateIn x MessageIn -> MessageOut x StateOut;

The data notation is less obvious:

data[XXX] = {tag1: type1, tag2: type2 ...}

denotes a JSON message of the form:

{"msg":"XXX", data:{"tag1":Data1, "tag2": Data2, ...}}

Where Data1 is of type type1 and Data2 is of type type2. Observe I have only
used the type "string" in my examples, but this is easily extended to JSON primitive types, enumerations and sequences of types.

I also used the notation [X] (in the definiton data[files] =
[{filename:string}]. [X] means an array (or sequence) of type X.

Contract Checking

Now what we have our state machines and message we can easily write a contract checker.

Given the state of the finite machine and then next message we can easily check if the client and server are correctly responding to protocol messages as required by the specification. Each message has a data type specification can easily be checked.

Comments on this are welcomed.

In Part 2 I will post Erlang bindings for the protocol specification and code for a contract checker.

Other implementers might like to implement bindings and contract checkers for their favorite languages. having done this we could start writing multi-language applications based on formal and checkable contracts.