Download Heaps and Hops
Transcript
5.3. Restrictions of the proof system solely from our proof system would meet, a more detailed account of which can be found in the original paper [VLC09]. Let us give three example programs on which the semantics directly derived from the proof rules via abstract separation logic would be too coarse, unlike the semantics we will develop in the next section. 1. Receives may happen before the corresponding sending operation has happened. Indeed, nothing in the proof rules prevents it, nor is it prevented by the interleaving of traces, and these are the only things taken into account to build the semantics of programs in abstract separation logic. For instance, given a freshly opened channel (e, f) over which one may communicate the message a, the following program would not block: receive (a,f); send(a,e); Indeed, the rule for receive says nothing about the contents of the queues of f (in fact, queues are not even present in our model), so a semantics based on it may decide to receive whenever the contract allows it. 2. What is sent does not necessarily match what is received. In fact, following the rules S and CD, the semantics of send corresponds to disposing of the message’s contents, and the one of receive to a non-deterministic allocation of a portion of storage satisfying the message’s footprint. In particular, the program (e,f) = open( C ); send(a,e ,10); x = receive (a,f); close(e,f); assigns 10 to x only if we choose φm such that it implies val = 10, whereas it should always be equivalent to x = 10; This highlights another issue of this semantics: it depends on the footprint context, which is supposed to be only an artifact of the proof. 3. The semantics would hide both forms of leaks described earlier, since the logic is not aware of them: as far as the rules are concerned, the contents of messages disappear when sent, and closing a channel is only about the endpoint heap, not the corresponding buffers. The next chapter is devoted to defining a satisfactory semantics and to establish the soundness of our proof system with respects to this semantics. Related work To the best of this author’s knowledge, this is the first extension of separation logic to message passing that supports copyless message passing. Not long after our own, another extension to copyless message passing has been published by Bell et al. [BAW10]. Their 98