Distributed applications can be structured as parties that exchange messages according to some pre-arranged communication patterns. These sessions (or contracts, or protocols) simplify distributed programming: when coding a role for a given session, each party just has to follow the intended message flow, under the assumption that the other parties are also compliant. In an adversarial setting, remote parties may not be trusted to play their role. Hence, defensive implementations also have to monitor one another, in order to detect any deviation from the assigned roles of a session. This task involves low-level coding below session abstractions, thus giving up most of their benefits. We explore language-based support for sessions. We extend the ML language with session types that express flows of messages between roles, such that well-typed programs always play their roles. We compile session type declarations to cryptographic communication protocols that can shield programs from any low-level attempt by coalitions of remote peers to deviate from their roles. Our main result is that, when reasoning about programs that use our session implementation, one can safely assume that all session peers comply with their roles-without trusting their remote implementations. Programming networked, independent systems is complex, because the programmer has little control over the runtime environment. To simplify his task, programming languages and system libraries offer abstractions for common communication patterns (such as private channels or RPCs), with automated support to help the programmer use these abstractions reliably and to relieve him from their lowlevel implementation details (such as message format and routing). As an example, web services promote declarative types and policies for messaging, with tools that can automatically fetch these declarations and set up proxies with a simple typed programming interface. From a security perspective, when parts of the system and some of the remote parties are not trusted, communication abstractions can be especially effective: relying on cryptographic protocols, implementations of these abstractions can sometimes entirely shield programmers from low-level attacks (such as message interception and rewriting) [1, 2] . However, this is seldom the case in practice, as security concerns force the programmer to understand lowlevel protocol issues. Beyond simple abstractions for communications, distributed applications can often be structured as parties that exchange messages according to some fixed, pre-arranged patterns. These sessions (also named contracts, or workflows, or protocols) simplify distributed programming by specifying the behaviour of each network entity, or role. By agreeing on a common session specification, the parties can resolve most of the complexity upfront. Then, when coding a role for a given session, each party just has to follow the message flow for this role, under the assumption that the other parties are also compliant. At run-time, sessions can finally be instantiated by mapping roles to actual principals and their hosts. Language-based support for sessions is the subject of active research [7, 8, 9, 13, 16, 30, 32] . In particular, several recent type systems statically ensure compliance to session specifications. In their setting, type safety implies that user code that instantiates a session role always behaves as prescribed in the session. Thus, assuming that every distributed program that may participate in a session is well-typed, any run of the session follows its specification. In an adversarial setting, remote parties may not be trusted to play their role. Hence, defensive implementations also have to monitor one another, in order to prevent any confusion between parallel sessions, to ensure authentication, correlation, and causal dependencies between messages and, more generally, to detect any deviation from the assigned roles of a session. Left to the programmer, this task involves delicate low-level coding below session abstractions, which defeats their purpose. Instead, we propose to systematically compile session specifications to cryptographic protocols. In this paper, we explore language-based support for sessions and their implementations, as follows: 1. We design a small embedded language of types for specifying messages, roles, and sessions, and we identify a secure implementability condition for these sessions. 2. We extend F# [28] (a dialect of ML [23, 24]) with distributed communication and sessions, so that type safety yields functional guarantees: any sent message is expected by its receiver, with matching payload types. 3. We compile session types to cryptographic communication protocols, coded in F#, that can shield our programs from any low-level attempt by coalitions of remote peers to deviate from their roles. We thus obtain a secure, functional, distributed implementation of sessions. 4. Our main theorem states that the safety guarantees implied by session types do not depend on the implementations of any remote peers: from the viewpoint of our distributed programs, any action that may occur may also occur in an abstract setting, using a centralized implementation that enforces all session types. To our knowledge, this paper provides the first secure implementation of session types, both formally and concretely. It relates the semantics of three languages: at the level of types, simple processes to specify communication patterns and payloads; as a source language, a subset of F# with distributed communications and typed sessions; as an implementation language, a subset of F# with distributed communications and cryptography. Our compiler extracts session definitions, verifies that they meet the secure implementability condition, generates the corresponding cryptographic protocols, and emits their code as F# modules. On the other hand, it leaves the code that uses sessions unchanged, treating the session constructs of the extended language as ordinary higher-order function calls to their implementations. Hence, user code calls our generated code to enter a session and then, for each received message, generated code calls back user code and resumes the protocol once user code returns the next message to be sent. Taking advantage of this calling convention, with a separately-typed user-code continuation for each state of each role of the session, we can thus entirely rely on ordinary typingà la ML to enforce session typing in user code. (In the following, as we focus on session security, we treat this important but well-understood aspect of session types informally.) The compiled protocols rely on a combination of standard techniques for authentication and anti-replay protection. The compiler does not introduce any additional message: each abstract session message is mapped to a cryptographic message with the same sender and receiver. Principals are authenticated using X.509 certificates. All messages include a unique session identifier (obtained as the joint cryptographic hash of its session type, its assignment of principals to roles, and a fresh session nonce) and a series of signatures: one signature from the message sender, plus one forwarded signature from each peer involved in the session since the receiver's last message (or the start of the session). At any point in a session, each protocol role knows exactly which messages to expect and what they should contain, so we can use compact wire formats and compile simple, specialized message handlers. Any message that deviates from the expected format can be silently dropped, or reliably detected as anomalous. The security of automatically-generated cryptographic protocol implementations crucially relies on formal verification. To this end, our language design and prototype implementation build on the approach of Bhargavan et al. [4] , which narrows the gap between concrete executable code and its verified model. Our generated code depends on libraries for networking, cryptography, and principals, with dual implementations. A concrete implementation uses standard cryptographic algorithms and networking primitives; the produced code supports distributed execution. A second, symbolic implementation defines cryptography using algebraic datatypes, in Dolev-Yao style; the produced code supports concurrent execution, and is also our formal model. Thus, our security theorems apply directly to arbitrary user code calling our session-generated code calling our symbolic library code, within a formal model of a subset of F# (rather than an ad-hoc abstract model of the protocol loosely related to actual executable code). Related work Session types have been explored first for process calculi [17, 20, 32] , to describe interaction on single channels. Behavioral types [9, 21] support more expressive sessions, typed as CCS processes possibly involving multiple channels. Another type system [6] also combines session types and correspondence assertions [19] . Recent works consider applications of session types to concrete settings such as CORBA [29] , a multi-threaded functional language [30] , and a distributed object-oriented language [13] . In particular, the Singularity OS [16] explores the usage of typed contracts in operating system design and implementation. In all these works, type systems are used to ensure session compliance within fully trusted systems, excluding the presence of an (active, untyped) attacker. Sessions for Web Services are considered for the WSDL and WS-SecureConversation specification languages (see e.g. [3, 8] bone et al. [7] also present a language for describing Web interactions from a global viewpoint and describe their endpoint projection to local role descriptions. Their approach is similar to our treatment of session graphs and roles in Section 2; however, their descriptions are executable programs, not types. More generally, distributed languages such as Acute and HashCaml [26, 12, 5 ] also rely on types to provide general functional guarantees for networked programs, in particular type-safe marshalling and dynamic rebinding to local resources. Cryptographic communications protocols have been thoroughly studied, so we focus on related work on their use for securing implementations of programming-language abstractions. They can provide secure implementations for distributed languages with private communication channels [1, 2] . They can also help support the distributed implementation of sequential languages such as JIF/Split [33], while preserving high-level, typed-based integrity and secrecy guarantees. In a similar vein, the Fairplay [22] system compiles high-level procedural descriptions toward secure two-party computations. In other work, type-based secrecy and integrity guarantees are enforced by a combination of static typechecking and compilation to low-level cryptographic operations [15] . Protocol synthesis and transformation have been explored in other settings: for instance, the Automatic Protocol Generation (APG) tool [25] generates authentication protocols then verified using Athena [27] and, more recently, Cortier et al. [11] verify the correctness of a generic transformation to protect a protocol from active attacks (but not from compromised participants). Contents Section 2 defines two views of sessions, as global communication graphs and as local role definitions. Section 3 gives the (fairly standard) syntax and semantics for our source and target languages. Section 4 outlines the libraries that embed our assumptions on cryptography and principals, used by our implementation. Section 5 presents our optimized cryptographic protocol, as a refinement of a basic, intuitively secure protocol. Section 6 describes our implementation code for sessions. Section 7 states our main results, formally showing the correctness of the implementation. Section 8 concludes. The appendix provides additional details on our implementation, including listings for selected libraries. A companion paper also includes a detailed programming example and all proofs [10] .
The work in REF is similar in spirit to ours, but is different in conception and details, as it uses a session graph specification to generate a cryptographic functional implementation that enjoys session integrity.
Secure Implementations for Typed Session Abstractions
20th IEEE Computer Security Foundations Symposium (CSF'07)
20th IEEE Computer Security Foundations Symposium (CSF'07)
Computer Science