Cooperative Runtime Monitoring of LTL Interface Contracts (1/3)

Uploaded by ingmarkamprad on 02.12.2010

Hi! My name is Sylvain Hallé from University of Québec in Chicoutimi, in Canada, and in
the next half-hour I'm gonna talk to you about a new concept called Cooperative Runtime Monitoring
of Interface Contracts. What you're going to see are the slides for the presentation I gave
at the 14th EDOC conference in Brazil in October of 2010, which incidentally, won the Best
Paper Award there, so I hope you'll enjoy.
I shall first mention that if you want any further information about the contents of this
talk, you can visit my web site at the address shown, where you can download a
copy of the paper for that presentation, and also the slides themselves --and of course, please
do not hesitate to contact me if you have any questions or ideas on this topic
or any other subject I'm working on. Before we start, let's first agree on a couple
of terms I'll use during this presentation.
We're gonna talk a lot about the "client", which designates the consumer of some resource, functionality
or service, and the
"server", which provides it. Of course there has to be some form of
communication between the two, through messages. So we'll have a client first sending what we'll call
request message and the
server answering by returning a
response message. And of course, there will be a long-running interaction, which means that the client
and the server typically exchange multiple request and response messages. Now we don't precise what these
messages are made of, so we'll designate them abstractly as just, say, letters. However, we know
in advance what all the possible messages between a client and a server can be, so
we can represent this set as some form of "alphabet". Here, just for fun, I represent
them as Scrabble letters. A
trace, or a message trace, is simply a sequence of such messages. Suppose you define some
kind of protocol using, say, a finite state machine, then most probably a lot of different
traces will lead you to the same state of the machine. So in a way, we
can say that a
state is an abstraction of a trace, according to some protocol. If you have such a
protocol, you can define
a transition function, which is a function that,
given any message from the alphabet
and any state from the set of possible states,
will return either the new state of the protocol resulting from the sending or reception of
the message
or some empty symbol that expresses the fact that in the current state of the protocol,
sending or receiving that message is not defined or not allowed.
We can express this mathematically by saying that delta is a function from the set of
messages and states to the set of states, and we can extend that definition by saying
that if we give delta a sequence of messages, then its return value is simply the
repeated application of delta on each message successively from some predefined initial state.
Now we have a way of specifying, of all possible traces of messages, which ones are
valid according to the protocol embedded into the definition of delta. The interface contract is the
function which, given any trace, returns either true if that trace complies with the protocol, and
false otherwise. More formally, we can say that
the function will return true for a given sequence of messages
if and only if
applying the transition function on that sequence does not return the empty symbol --that is, it
leads us somewhere that is defined by the protocol.
OK, now that we have defined this basic terminology, we can revisit the original scenario of
a client and a server interacting through messages that must follow some interface contract, and see
how it can model a range of different contexts.
For example, in an object-oriented programming language such as Java, one can think of the server
as an instance of some class, say Iterator, the client as a Java program that uses
that instance, and the messages as method calls and return values. Then the interface contract defines
valid sequences of methods one can call on an instance of the Iterator. We have an
example here that says that two calls of the next() method, on the same instance of
an Iterator, must be separated by at least one occurrence of method hasNext() --that is, you
should always check whether the iterator can return a new element before asking for that element.
We can see that this is indeed a natural constraint on the use of an Iterator
and that it involves sequences of method calls, it is not a property that you can
express or check by looking at method calls individually.
In the context of web services, we can repeat the same process of mapping each part
of the figure to concrete elements. In this case, the server is a web service, whose
functionalities are consumed by a client like a Javascript client running in a user's web browser,
and the interaction is made through the exchange of documents in the XML format. I took
here the example of the Amazon e-commerce service, which allows clients to manipulate the contents of
a virtual shopping cart made of items from the Amazon catalog. You can do many things
with the shopping cart, but there are also things that you can't do, one example is
that if you invoke the CartClear operation in a messages, then you cannot modify the contents
of the cart or remove items from it until you actually add a new item to
the cart. This is pretty natural, it doesn't make sense to try to modify or remove
items from an empty cart.
Of course one might wonder what happens when we stray away from what an interface contract
tells us to do, and the answer depends on the context --but in general, we can
expect error messages from the server's part. In addition since we jump outside what was designed,
then basically anything can happen so we might as well obtain a response that makes us
think that everything is fine but actually contains non-sensical data. This might also trigger compensation mechanisms,
exception handling, things like that, and in general what we get is a waste of processing
time doing all these things, and potentially even security problems.
The big question then becomes how do we prevent a client-server exchange of messages from going
outside the interface contract? In particular, we are asking this question from the server side, so
the *server* is intersted in preventing the client from producing messages that violate the contract. Of
course we could ask the same question by reversing the roles, but in the scenarios I've
just shown (Java programming, the Amazon web service), we assume that the server works correctly and
that if a violation is to occur, it is the client's fault. There are currently three
solutions to this problem.
The first one is to perform what I call "a priori certification", where some trustworthy authority,
on behalf of the server, checks the cilent and tries to ensure in advance that it
behaves according to the contract. This can be done through testing, static verfication, any method that
can give the server compelling reasons to believe that the client is correct. Once this is
the authority gives the client some kind of digital certificate, a document that asserts that the
client has been checked and satisfies the server's requirements. The trick is that once this testing
is done,
the client is simply required to present that certificate to the server upon starting an interaction.
The server checks the certificates and, if it is deemed valid, lets the client start the
interaction. The server does not need to perform any other verification on the client itself at
runtime, which is nice.
An example of such a process is the certification of iPhone applications by Apple. If you
develop an application for the iPhone, you must then submit it to Apple, which eventually certifies
it and puts it on its online store. iPhones are designed not to accept any application
that does not come along an Apple certificate.
All this is very fine, but for one thing: it supposes that the client cannot change
once it has been certified, or that you cannot circumvent the certification mechanism, which in reality
is hard to achieve. For iPhones this is called "jailbreaking": it basically consists of "hacking" the
phone's operating system so that is stops requiring a certificate to let an application run. In
the case of web applications, you have Javascript prototype hijacking that allows you to replace the
application's original code with whatever you want at runtime, so that the code that has been
checked is not the one that runs when the interaction with the server starts. Of course
you can setup additional mechanisms, like verifying that the code that runs is the one that
has been certified, at runtime, but this somehow defeats the point of performing the check in
An alternate solution then is to perform monitoring of the interface contract itself, at runtime, say
on the server side. You setup a separate process at the server's entrance whose job is
to check every incoming message from the client against the interface contract.
The process lets the message through to the server itself only if it complies with the
contract, and
otherwise discards it. This way, you shield the server from any "junk", so to speak, from
the client, and the server is ensured that anything that ever comes in has been checked
and follows the contract.
This comes at a price, though, and can become a bottleneck if this single entry point
has to check incoming messages from a large number of client instances. Very well then, we
can come up with a third solution that simply flips the image and sends the monitoring
process on each instance of the client,
so "client-side monitoring". This way, bad messages are filtered before they are event sent to the
server, which in turn does not have any processing to do. Moreover, each client is responsible
for the monitoring of its own instance of the message exchange, so that the processing load
is evenly spread across all clients. This seems like a nice solution, but obviously,
having the client watch its own messages is a bit strange --and in particular, it does
not provide too many guarantees to the server that any monitoring is done at all. You
see in this scenario, the server totally relies on the fact that clients can be trusted,
but that's exactly the reason why we are doing veification in the first place. So this