Petr Hosek

Matteo Migliavacca

Ioannis Papagiannis

David M Eyers

David Evans

Brian Shand
email: brian.shand@cbcu.nhs.uk

Jean Bacon

Peter Pietzuch

Web applications in many domains such as healthcare and finance must process sensitive data, while complying with legal policies regarding the release of different classes of data to different parties. Currently, software bugs may lead to irreversible disclosure of confidential data in multi-tier web applications. An open challenge is how developers can guarantee these web applications only ever release sensitive data to authorised users without costly, recurring security audits. Our solution is to provide a trusted middleware that acts as a "safety net" to event-based enterprise web applications by preventing harmful data disclosure before it happens. We describe the design and implementation of SafeWeb, a Ruby-based middleware that associates data with security labels and transparently tracks their propagation at different granularities across a multi-tier web architecture with storage and complex event processing. For efficiency, maintainability and ease-of-use, SafeWeb exploits the dynamic features of the Ruby programming language to achieve label propagation and data flow enforcement. We evaluate SafeWeb by reporting our experience of implementing a web-based cancer treatment application and deploying it as part of the UK National Health Service (NHS).

SAFEWEB: A Middleware for Securing Ruby-based Web Applications 1 Introduction

Enterprise web applications in areas such as healthcare, financial processing and government services must selectively expose sensitive data to authorised sets of web users. For example, a cancer researcher may want to query a centralised patient database over the web for anonymised health records of patients that have a given type of cancer. The costs of inadvertently disclosing confidential data to the wrong users due to implementation errors in web applications are high-hospitals and medical practitioners in the UK are legally liable for unauthorised disclosure of patient data without prior consent. Due to new legislation introduced in 2010, organisations can be fined up to £500,000 for security breaches [START_REF]Data breaches to incur up to £500,000 penalty[END_REF]. In this paper, we address how to implement secure enterprise web applications that are guaranteed to comply with data protection policy.

Enforcing a data protection policy end-to-end, i.e. , across an entire multi-tier web application, is challenging. An implementation error in any tier of a web application may result in unauthorised data disclosure. Developers may introduce software bugs inadvertently or based on misunderstandings of requirements. Achieving correctness is even more challenging for web applications that process different types of data from multiple domains, such as hospitals, laboratories and insurance providers, each with their own security requirements.

Current best practices include manual source code auditing for new applications, which is error-prone and costly. Tools for static analysis such as Pixy [START_REF] Jovanovic | Pixy: A static analysis tool for detecting web application vulnerabilities[END_REF] validate that the implementation satisfies given invariants. Their use, however, requires expert knowledge to formalise invariants and they cannot handle large distributed web applications due to these applications' size and complexity.

We make two assumptions: [START_REF] Bell | Secure computer system: Unified exposition and Multics interpretation[END_REF] In terms of the threat model, we assume that the external environment is hostile, but that application code is not explicitly malicious, even if threats might be caused by bugs in the implementation. [START_REF] Burket | GuardRails : A datacentric web application security framework[END_REF] We assume that stakeholders are willing to accept some performance overhead-in terms of request throughput and latency-for increased security.

Our solution is to propose a middleware that implements a "safety net" by providing a data-centric security approach that integrates well with multi-tier web applications. Our middleware is based on two key ideas: It decouples the processing of confidential data from the handling of web requests. In addition, it tracks data as it flows through the web application in order to ensure its confidentiality and integrity. This means that implementation bugs in the web request handling logic cannot cause any unauthorised confidential data to be disclosed. By tracking data propagation by means of security labels, the middleware performs automatic and appropriate compliance checks at the boundaries between application components without relying on developer support. This reduces the effort required for security audits.

We demonstrate the practicality of this approach by describing SafeWeb, a Ruby-based middleware that enforces data flow policy across web applications. SafeWeb consists of an event-processing backend that processes data asynchronously from a confidential data store according to application-specific business logic. Events are associated with security labels, which are tracked by SafeWeb as they propagate between event processing components. This mechanism is implemented efficiently through isolation of processing components using Ruby's safe levels. A separate web frontend serves processed event data in response to web requests while maintaining security labels at the variable level using Ruby's meta-programming features. Before sending data to web users, SafeWeb validates the associated security labels against user privileges, thus preventing violations of the data protection policy.

SafeWeb is designed to integrate well with existing security practices at an organisational, architectural and infrastructure level. From an organisational viewpoint we complement existing security practices, such as network partitioning through firewalls and security code auditing, without requiring significant changes. At the infrastructure level, SafeWeb can easily be applied to production environments. In contrast with classical label-based approaches, we avoid complex changes in the language runtime. We are able to provide tracking purely at the middleware level through careful exploitation of Ruby's metaprogramming and security features.

We evaluate SafeWeb in a real-world healthcare environment by developing MDT web portal, a web application that provides information about ongoing cancer treatment of patients to teams of medical practitioners at hospitals. We discuss the deployment of this application using SafeWeb as part of ECRICan organisation within the UK National Health Service (NHS) that collects relevant patient-sensitive oncological data. We show that SafeWeb can guarantee that medical records are only exposed to authorised users-even with implementation bugs in the processing logic of the MDT web portal application. It integrates well with existing information systems and introduces only minimal overheads in terms of application development effort and performance.

In summary, the main contributions of the paper are: (1) a middleware for securing web applications that uses event processing to decouple queries from sensitive data; (2) an application of information flow control techniques across all tiers of a web application to prevent non-compliant disclosure of sensitive data to users and an efficient implementation of data tracking using Ruby language mechanisms; (3) an evaluation of this approach in a healthcare environment using a realistic web application for supporting cancer treatment at hospitals.

In §2 we provide background on the security requirements of web applications dealing with confidential data. Then, we present a general data-centric security mechanism addressing these requirements, explaining why existing technologies cannot be applied in production environments ( §3). The SafeWeb middleware is described in §4, focusing on the different components of its architecture. We evaluate our approach in §5 through an implementation of a web application using SafeWeb, describing its security properties and providing a performance analysis. In §6, we discuss related work, and we draw conclusions in §7.

Data Confidentiality in Enterprise Web Applications

Organisations in the public and private sector collect, process and analyse personal data to improve the quality of the services that they offer. Due to the sensitivity of personal data, maintaining its confidentiality is crucial. As a consequence, it is necessary to verify that applications are not vulnerable to compromise from external attacks and that confidential data is handled in compliance with the policies set by organisations.

Current best practices to maintain data confidentiality in applications are costly, error-prone and time consuming: organisations adopt a series of security measures including risk assessments, internal security code reviews and external security consultations. These measures are intertwined with project development to the point that development of new services is limited. For example, healthcare organisations struggle to develop new medical applications that have the potential to improve patient care quickly and cost-effectively.

Middleware can be used to reduce the cost of development and deployment of new applications by moving security auditing effort from applications to reusable middleware components. In this paper, we describe a middleware that can increase the trust placed in applications that process and provide access to confidential data by placing applications within a "safety net" that, within the constraints of a production environment, protects data from compromise and accidental disclosure. The goal is to satisfy the following two security requirements-both of which are discussed in the context of a healthcare example in the next section: S1 Access to confidential data by external users should be static and one-way; it should not be possible from the outside to change which confidential data items are exported from an internal network to the public Internet, or to alter existing data stored within the internal network.

S2 Confidential data should be protected end-to-end; implementation errors in an application should not result in the disclosure of confidential data and violations of the specific security policy for that application.

Case Study: A Cancer Registration System

In this work, we consider the following real-world case study. The Eastern Cancer Registry and Information Centre (ECRIC) is part of the UK National Health Service (NHS). ECRIC aims to produce a comprehensive picture of cancer cases in the East of England. It receives patient data from many sources including so-called Multidisciplinary Teams (MDTs), hospital Patient Administration Systems (PAS), pathology laboratories and the Office of National Statistics (ONS). ECRIC's software infrastructure has recently been chosen as the national cancer registry platform for England. Most of its software systems are implemented in the Ruby programming language for ease of development and due to existing developer expertise. The main cancer registration database, hosted in a secure private network, holds structured information about patients, tumours, and associated treatments. Data are imported into the main database from different sources and processed with the help of the domain knowledge of staff. ECRIC staff can also operate off-site by using an external web application server that has been extensively audited for security.

Based on discussions with ECRIC, we identified a new application that they would like to offer: an MDT web portal that provides relevant data that can support the operation of MDTs at hospitals. MDTs treating oncological patients currently provide reports to ECRIC about their patients through secure email and paper forms. ECRIC wants to feed back both summary and detailed patient information to MDTs, letting them compare data quality with their peers and explore the underlying data to discover the cause of any discrepancies. At present, resolving discrepancies is laborious, because staff at ECRIC have to manually extract and release the relevant records for each MDT. In summary, the MDT web portal should satisfy the following functional requirements: F1 Doctors and MDT co-ordinators that are members of an MDT can log into the MDT portal using a web browser and consult the details of patients treated by that MDT, with the option of providing feedback (handled externally, e.g. via secure NHS email).

F2 Doctors and MDT co-ordinators can consult various metrics about their patients, e.g. the level of completeness of the provided information or projected survival statistics of patients under treatment.

F3 MDT co-ordinators can put those metrics into context by comparing them with each MDT's average in the same region or with regional aggregates.

The security policy for the MDT web portal is as follows:

P1 Details about patients can be consulted only by members of the MDT that treats them. MDT-level aggregates can be consulted by all MDTs in the same region. Regional-level aggregates can be seen by all MDTs.

A design of the MDT web portal as a standard web application using the main ECRIC database would not be acceptable. The MDT web portal requires interactive access to patient-level data, in violation of security requirement S1an implementation bug could compromise the integrity and the confidentiality of the whole ECRIC database. Furthermore, errors in the MDT web portal could violate its security policy, conflicting with S2.

Enforcing the MDT security policy P1 with a traditional web application architecture is challenging. The MDT web portal has a data flow path for confidential data that involves multiple components at different layers: data must be extracted from the ECRIC database, processed in an application-specific way, and finally presented by a web front-end. Any component in the layers involved could cause unauthorised data disclosure. The security policy is difficult to enforce through a composition of local mechanisms because it is an end-to-end property. The large amount of source code that needs to be trusted increases the risk of defects and incurs a high code review effort.

In addition, the mechanisms used to protect from policy violations must operate at a fine data granularity. For example, the application must distinguish between confidential information at the level of single patients treated by an MDT and access to aggregated data at MDT or regional level.

In summary, we need a security mechanism that (a) is able to enforce endto-end data flow guarantees, reducing the amount of trusted source code, and (b) allows for fine-grained, data-centric protection of confidential information. In the next section, we describe how controlling the propagation of security-labelled data through the application, at the middleware level, can achieve this.

Controlling Data Propagation

Traditional access control models achieve security by restricting access to resources: a principal, such as a user who owns data, can delegate to other principals a subset of operations. In such a model, it is easy to control information release but difficult to control its propagation. Once a user has delegated the privilege to read data to another user, information cannot be protected anymoree.g. the second user can write the data to a public Internet site. Thus, under a traditional (discretionary) access control model, secure data processing means that processors must be trusted-a data processor authorised to read confidential patient data must not disclose it to unauthorised parties.

The problem of unauthorised data disclosure is addressed by information flow control (IFC), a mandatory access control model originally developed for military systems [START_REF] Bell | Secure computer system: Unified exposition and Multics interpretation[END_REF][START_REF]Trusted computer system evaluation criteria[END_REF]. IFC protects the propagation of data. We can model an IFC system as a set of inputs, outputs and processing components. An input component, acting on behalf of a principal, can attach a tamper-resistant security label to the data-e.g. a label can be used to protect the confidentiality of a patient medical report. The security labels can then be used to track the propagation of data through the system and middleware can enforce end-to-end restrictions on the permitted data flow. For example, if a component producing patient records labels every record, labels can prevent a mailing component from including records in emails, independently of the processing.

IFC systems can guarantee that security labels are preserved by controlling all data flow paths between components. When labelled data is copied or transformed by a component, the IFC system maintains the labels. When labelled data is processed or combined with data with different labels, the resulting labels are a composition of the previous labels, i.e. the system preserves all the data flow restrictions of the original labels. To achieve this, IFC systems require components to be "sandboxed," i.e. isolated from one another and from the external environment. Components can only communicate through primitives that are under the control of the IFC system.

To output data protected by a label, a component must have a declassification privilege [START_REF] Miglivacca | High-performance event processing with information security[END_REF]. This enables the component to remove the label from the data and use these data without restriction. The original owner of the data can restrict the data flow of, for example, a patient record by assigning declassification privileges only to components acting on behalf of treating doctors.

Labels can also be used to protect data integrity, which is the dual of confidentiality. The creator of an integrity label delegates to other components an endorsement privilege to add this label to data. Components can then trust only data that is "guaranteed" by this integrity label.

Applying Information Flow Control

IFC is a good fit for developing secure web applications because it can detect and contain the effect of application bugs which could otherwise violate a security policy (cf. security requirement S2 ). Note that we assume that application code is not intentionally malicious; this problem can be tackled by organisational safeguards such as only allowing trusted developers to develop applications. Instead, we focus on protection from unintentional software bugs.

We describe how IFC achieves our security goals in the context of the MDT web portal application from §2.1. Consider the security policy P1 for the MDT application. After creating a label for each patient, a component can (i) attach the label to each patient's data as it enters the system and (ii) assign the declassification privilege over the label only to components that execute on behalf of MDT principals treating the patient. Based on IFC enforcement, this guarantees that each patient record can only be accessed by the correct MDT, independently of the processing that happens between these two endpoints.

In the more complex case of MDT-level aggregate measures, which should be visible only to MDTs in the same region, label tracking is overly conservative because aggregates are considered as sensitive as the data of all involved patients, preventing access by any MDT. Therefore a component trusted with patient data must (i) remove all patient labels from aggregate data, (ii) relabel the aggregate data with an MDT-specific label and (iii) assign a declassification privilege over the MDT label to all MDTs in the region. The same mechanism can be used for regional-level aggregates by defining regional-level labels.

In summary, the security policy of the MDT application can be enforced by applying these three kinds of labels with corresponding privileges. Any component that is not policy compliant due to implementation errors cannot violate the MDT security policy. For example, a component for computing statistical aggregates would be constrained in terms of the data that it can disclose publicly. Even if its implementation is too large and complex to be audited, a software bug in, say, its logging function, which might otherwise reveal confidential patient data in externally accessible log files, would be prevented by IFC enforcement.

Practical Information Flow Control for Web Applications

In practice, applying a strong security model such as IFC to web applications is challenging. For IFC to be used, it must have low impact on developers and thus integrate with familiar architectures, programming models and languages.

Recently, researchers have proposed IFC techniques to improve the security of applications. Jif [START_REF] Myers | Protecting privacy using the decentralized label model[END_REF] extends the Java type system to include labels and checks them statically. DIFCA-J [START_REF] Yoshihama | Dynamic information flow control architecture for web applications[END_REF] rewrites Java bytecode to propagate labels in JVM operations. Trishul [START_REF] Nair | A virtual machine based information flow control system for policy enforcement[END_REF] and Laminar [START_REF] Roy | Laminar: Practical finegrained decentralized information flow control[END_REF] modify the JVM to track labels. DE-FCon [START_REF] Miglivacca | High-performance event processing with information security[END_REF] isolates threads allowing communication only through labelled data.

All of these systems adopt a "strict" tracking model that is invasive to the programmer and the system architecture. IFC tracking in these systems strives to avoid false negatives, as a single false negative if exploited could compromise the security of the whole platform. However, this strict application of IFC leads to false positives that require applications to be restructured to remove ambiguity in data flow tracking. Strict IFC also requires complex implementations: mature, industrial-strength implementations of IFC systems are currently lacking. Adoption of research prototypes in a production environment is undesirable because they are difficult to verify, requiring expert knowledge of JVMs, runtime libraries and bytecode rewriting techniques. Maintenance is also problematic when new versions are released by upstream developers.

In contrast, our IFC tracking approach is inspired by Resin [START_REF] Yip | Improving application security with data flow assertions[END_REF], which only targets source code that does not actively try to evade data tracking. It is thus possible to reduce the number of false positives, accepting a few false negatives which are unlikely to be exercised by non-malicious code. IFC is thus used as a safety net to catch implementation bugs, instead of acting as the primary method of security policy enforcement. This approach integrates well with current security practices adopted by organisations.

Our work differs from Resin in two key aspects. (1) We target enterprise web applications instead of stand-alone applications built directly on a specific database. In enterprise settings, it is important to support messaging services in the backend with an appropriate information processing model. To the best of our knowledge, we are the first to integrate IFC with two different processing models at different granularities (cf. §4)-a proactive event-based model in the backend with data tracking at the event level and a reactive web language model in the frontend with tracking at the variable level. (2) We manage to support IFC in the middleware without significant changes to the language runtime. By using the Ruby language support for meta-programming and its powerful security primitives, we avoid changes to the Ruby interpreter, leading to an IFC implementation that is easy to understand, verify and maintain.

SAFEWEB Middleware Design

In this section, we describe SafeWeb, a Ruby-based middleware that separates the processing of confidential data from presentation aspects, while enforcing data flow constraints throughout the application. As shown in Figure 1, Safe-Web consists of two parts: an event processing backend (left), which realises the application logic, and a web frontend (right), which handles users' requests based on processing results. Application logic in SafeWeb is implemented in an event-based fashion through one or more processing units (i.e. application components), which produce and/or consume events. This architecture largely decouples the processing of confidential data from the handling of web requests [START_REF] Ye | Event exposure for web services: a grey-box approach to compose and evolve web services[END_REF] and creates a unidirectional data flow from the backend to the frontend, in compliance with security requirement S1.

The event processing backend hosts the application logic for processing confidential data. Events are created from confidential data retrieved from a data source (illustrated as the Main Database in the figure) and labelled appropriately. Event Processing Units act as generators, filters or processors of events and exchange labelled events through an IFC-aware Event Broker. Units are constrained in their operation by the Event Processing Engine, which acts as a run-time environment for application components. Its IFC Jail controls communication of units with the environment and preserves labels during event communication. Privileges for units over specific labels are configured through a data flow Policy. Result events are stored with appropriate labels in an Application Database after processing.

The web frontend serves synchronous web requests from users by accessing the application database. State that is specific to a given web session is stored in a separate Web Database to isolate it from application data. Labels from the application database are propagated in the web application by SafeWeb's runtime Taint Tracking library and are checked when generating responses. As a result, security labels are associated with data throughout the processing pipeline and checked at boundaries between components with respect to the application policy, thus satisfying requirement S2.

Events with Security Labels

Event processing units communicate through events. Data models for events can vary widely [START_REF] Eugster | The many faces of publish/subscribe[END_REF]. For ease-of-use, we adopt one of the simplest yet popular choices: events in SafeWeb consist of a set of key-value attribute pairs and an optional data payload. The keys, values and the body are untyped strings.

SafeWeb associates a set of security labels with each event. There are two types of labels, confidentiality labels and integrity labels. Confidentiality labels prevent sensitive data from escaping a given system boundary, whereas integrity labels are used to prevent low-integrity data from entering parts of an application. Confidentiality labels are "sticky"-once they are associated with an event, all events that are derived from that event will also contain those labels. In contrast, integrity labels are "fragile"-they are applied to an event only if all the events that this event was derived from also contain the same integrity labels.

Labels are represented as URIs. For example, label:conf:ecric.org.uk/ patient/33812769 could be used as a confidentiality label to protect the data of a specific patient, while label:int:ecric.org.uk/mdt could act as the integrity label for all data contained within the whole MDT application. In the MDT application, an event processing unit periodically reads unlabelled patient records from the main ECRIC database and produces events which are labelled according to the encountered patient ID. This operation does not require privileges-it is always possible to add extra confidentiality labels to events. MDT-level aggregates, such as survival statistics or measures of information completeness (cf. §2.1), are labelled with a confidentiality label specific to that MDT.

Label enforcement is managed using associated privileges. Two types of privileges are used for confidentiality labels. The clearance privilege is used to access information protected by a confidentiality label. The privilege to make labelled information public by removing the label is referred to as declassification. Analogous privileges for integrity labels exist: clearance to low integrity and endorsement. To simplify presentation, we consider only confidentiality labels and the associated privileges in the rest of the paper.

Privilege assignment and checking is performed in SafeWeb by the event processing engine and the web frontend. Privileges associated with labels are assigned directly to units (in the backend) and requests (in the frontend) through a policy specification file. For more complex policies with dynamic privileges, a label manager could delegate privileges to units at runtime.

Event Broker

Units communicate by publishing events and by subscribing to events that they are interested in. To dispatch events among units, SafeWeb uses an event broker that matches subscriptions with published events. To support fine-grained data processing, SafeWeb uses a topic-based subscription language with optional content filtering on event attributes within a topic [START_REF] Eugster | The many faces of publish/subscribe[END_REF].

The event broker filters events according to their security labels. This is used to restrict the set of events that units can receive: for an event to be delivered to a subscriber, the set of its confidentiality labels must be a subset of those labels for which the subscriber possesses clearance privileges.

The event broker uses a modified version of the Streaming Text Oriented Message Protocol (STOMP) [START_REF]Stomp protocol[END_REF]-a simple, extensible, HTTP-inspired message protocol. It is language-and platform-agnostic and an open-source implementation [START_REF]StompServer[END_REF] exists for Ruby. In STOMP, each request consists of a command, such as CONNECT, SEND or SUBSCRIBE, a set of optional headers and an optional body. A destination header is used to match subscriptions with publications by topic. An optional SQL-92 selector header specifies content-based subscriptions.

The implementation of our IFC-aware event broker is based on the STOMP implementation but has been extended with SSL support at the transport layer. At the dispatching layer, we have changed the matching semantics to respect labels, which are encoded as event headers with special semantics in SEND and SUBSCRIBE messages. In addition, subscriptions include unique identifiers to simplify the handling of subscriptions issued by different units. The client side of the STOMP implementation uses the event-based EventMachine I/O library [8].

Event Processing Engine

The event processing engine in SafeWeb provides a framework to support and control unit execution. Its key functions are (1) control of unit execution by checking and tracking security labels, (2) assignment of privileges to units and (3) restriction of access to the environment. An event processing unit is realised as one or more classes that implement the business logic of the application. The engine configures, instantiates and runs units and provides communication facilities using the event broker. Listing 1 shows a unit that computes a daily list of patients with processed reports. The unit registers subscriptions for events published on the topics patient report (line 1) and next day (line 6). When a subscription is issued by a unit, the engine reads the set of labels from the unit's policy file for which the unit has clearance privileges. The engine then issues a subscription request to the broker with this set of labels; this set is used to check that a matching event can be processed by the unit. To support stateful units, the engine provides a unit-specific key-value store with labels associated with keys. It can be used for reading (lines 2 and 7) or storing (line 4) values, thus allowing different callbacks to communicate by exchanging state between them.

The engine prevents units from inadvertently disclosing confidential data because it controls the labelled events that they publish and isolates them from the external environment. We describe the two mechanisms for this in turn.

Label tracking. To ensure correct labelling, the engine associates a set of labels with the execution of a callback. This set, accessible to units as $LABELS, is initialised to the set of labels of the event being processed. When an event is published, the engine attaches all labels in $LABELS to the event. With each publish call, the unit can specify a set of labels to add or remove from the published event (lines 8 and 9), although removal is only permitted when the unit has the appropriate declassification privilege.

As values in the key-value store are labelled on a per-key basis, when a value is read from the store, $LABELS is updated to reflect its confidentiality-all the labels associated with the value's key are added to $LABELS. When writing to the store, all confidentiality labels in $LABELS are saved as the key's confidentiality, optionally adding and removing labels analogous to the publish call.

By maintaining labels from the received events to the published ones, and by labelling all datapaths through the shared key-store appropriately, confidentiality labels are preserved. However, unit callbacks could access other forms of unlabelled shared state, which would ignore label protection. In addition, they could bypass the event broker and use external APIs for console, disk or network I/O, thus disregarding labels completely. To prevent this, the engine must execute unit callbacks in isolation.

Isolation. The goals of isolation are twofold: to prevent the use of I/O operations and to prevent access to variables outside of the callback local scope, i.e. , global variables, instance variables and local variables of enclosing scopes. To isolate units from I/O and access to global variables, we use Ruby's safe levels. They restrict the execution mode of Ruby code and provide different kinds of isolated environments. $SAFE is a thread-local global variable that controls the current safe level. When set to safe level 4, it creates the most restrictive environment with the following irreversible effects on the current thread: (i) no access to I/O operations, (ii) all new objects are marked with a flag called "taint" and (iii) no write access to any object that is not tainted.

In Figure 2, we show how safe levels are used to achieve callback isolation. The engine executes units in a new thread, after setting $SAFE=4 to prevent the unit's initialisation code (step 1) from performing I/O operations. Units register callbacks (step 2) that execute when events arrive. When the STOMP client library that interacts with the event broker receives a matching event, it creates a new thread, sets $SAFE=4 and executes the callback (step 3). The callback code cannot perform I/O or store events in global variables. It can only store events in the unit's key-value store that is tainted explicitly during unit allocation.

Isolation in safe level 4 still allows a callback to access variables of its enclosing scopes. To prevent this, we duplicate these variables when the callback is registered by using the meta-programming features of the Rubinius runtime [START_REF]Rubinius[END_REF]. Some units, however, need access to APIs that perform I/O, e.g. units that import and export events between the event engine and databases. To support this, the engine allows privileged units to execute without isolation at $SAFE=0 and, thus, access I/O facilities. This effectively allows them to declassify any received event. To limit the power of privileged units, the engine prevents them from receiving events with certain labels by withholding their clearance privilege.

Web Frontend

The web frontend of SafeWeb presents results from the backend to users and enforces IFC without requiring changes to web applications. Web developers could be not fully aware of the policy requirements of the data that they present or, more often, they may introduce implementation bugs leading to unintended data disclosure. In the web frontend, SafeWeb's taint tracking library labels all data to reflect the confidentiality of the principals that the data correspond to. When an application that is not policy compliant attempts to return incorrect data to the client, the operation can be aborted, preventing data disclosure.

The web frontend has a traditional, database-driven architecture: a client issues an HTTP request, the request is served by the application server using the application database, and the HTTP response returns the result to the client. Since the application server handles requests from all users, it must have access to the data that any user may receive, i.e. all sensitive data in the application database. As a consequence, the web application would have to be trusted to remove all labels associated with data. Clearly, this would violate security requirement S2 because any implementation error in the web application could result in inadvertent disclosure of data that should be visible only to a particular group of users, such as a given MDT.

To achieve the end-to-end security requirement, SafeWeb tracks data at a different granularity in the web frontend than in the event-processing backend. Instead of labels being attached to events, they are associated with individual variables. For example, when a variable n stores a patient name, n will carry a label that conveys the confidentiality of the patient name.

Labels are checked by SafeWeb when the web application returns an HTTP response to a client. For example, before the content of variable n is sent to a client, the client's privileges are validated to be a superset of the confidentiality labels associated with n. As described next, this is sufficient to provide end-toend confidentiality guarantees without requiring a new application architecture, which would be challenging to adopt in a production environment [START_REF] Papagiannis | Enforcing user privacy in web applications using Erlang[END_REF].

Figure 3 shows the operation of SafeWeb's taint tracking library for Ruby. In step 1, an HTTP request arrives at the server. The request is authenticated and the confidentiality privileges of the associated user are retrieved from the web database. In step 2, the application queries the application database for the data needed to serve the request. SafeWeb's taint tracking library transparently adds the labels produced by units in the backend to the data fetched from the application database. In step 3, the application produces a response by carrying out application-specific processing of the data. SafeWeb's taint tracking library alters Ruby program statements and library methods to propagate labels correctly; e.g. , when two strings are concatenated, the resulting string receives both operands' labels. In step 4, before sending the response to the user, the response's label is compared to the user's privileges from step 1-unless the user has the required privileges, the operation is aborted.

SafeWeb implements variable taint-tracking in Ruby using labels as follows. Its taint-tracking library redefines Ruby's String and Numeric subclasses (1) to store labels within each instance and (2) to propagate labels correctly across method invocations. For example, SafeWeb's taint tracking library should propagate labels upon string concatenation. For this, it declares a new concatenation method in the String class called nconcat(). The taint tracking library then aliases the existing "+" method to call nconcat() and propagate labels. From then onwards, the runtime transparently invokes the redefined "+" method when two strings are concatenated. Since we only support non-malicious code ( §3.2), these changes are enough to effect label propagation. The implementation exploits a standard meta-programming feature of Ruby and Ruby's pure object-oriented foundations. Ruby classes are open, all operators are defined as methods, and method definitions can change at any time. Implementing a similar taint-tracking library in other popular web languages, such as Java [START_REF] Chin | Efficient character-level taint tracking for Java[END_REF] or PHP [START_REF] Yip | Improving application security with data flow assertions[END_REF], would require more extensive changes to the language runtime, making maintenance difficult in a production environment.

SafeWeb supports Ruby web applications running on the Rubinius runtime [START_REF]Rubinius[END_REF] and using the Sinatra web framework [START_REF] Sinatra | [END_REF]. We use Rubinius due to its ability to manipulate the regular expression variables ($~, $1, etc.) directly. This is necessary to add taint tracking to Ruby's regular expression methods. Sinatra is used for its well-defined interception points of HTTP requests and responses. This allows SafeWeb's taint tracking library to intercept all communication to and from the client and attach label checks or fetch user privileges.

We do not introduce explicit features to prevent traditional Cross-Site Scripting (XSS) or SQL injection (SQLI) attacks. Ruby objects support a taint method that marks a given object as originating from the user. The Ruby runtime stores this information per object and propagates it when strings are processed, similar to our label propagation. In the context of web applications, this mechanism can be used to ensure that every string is sanitised before being used in a sensitive operation, such as an HTML response or an SQL query.

Evaluation

The goals of our experimental evaluation are to explore the effectiveness of the SafeWeb middleware in preventing unauthorised data disclosure and to measure its performance overhead. We evaluate its security properties as part of the prototype implementation of the MDT web portal application.

Case Study: MDT Web Portal Application

As shown in Figure 4, the MDT web portal application uses three units: (a) A data producer obtains data from the main ECRIC database, leveraging the existing ECRIC framework for data access. It reads fields from different tables, labels them appropriately according to MDT and patient ID and publishes them as events to the event broker. For the sake of simplicity, we use only MDT-level labels as these are sufficient to satisfy our security requirements. (b) A data aggregator continuously collects all events related to individual cancer cases and combines their data. It produces aggregated records required by the MDT web application to satisfy functional requirements F1-F3. Implementation errors will not disclose data because of the isolation mechanism of SafeWeb. (c) Finally, a data storage unit, which has declassification privileges for all MDTs, handles data persistence. It stores processed records with their security labels in the CouchDB application database. Security features of SafeWeb (i.e. IFC and strong isolation) allow the application to satisfy the security policy P1.

The Sinatra-based web frontend of the application uses CouchRest [START_REF]CouchRest[END_REF] to access CouchDB, and ERB for embedding Ruby in web pages. SafeWeb's taint tracking library enforces authentication centrally by adding hooks to all defined Sinatra rules. User accounts and their label privileges are stored in the web database. Currently, the web frontend uses HTTP basic authentication and TLS. We plan to add support for authentication using NHS smartcards in the future. Deployment. Figure 4 shows how ECRIC's network is separated into three zones: an Intranet, a demilitarised zone (DMZ ) and the NHS-wide N3 network. The Intranet is a restricted zone separated from the DMZ by a firewall, which permits only unidirectional connections to the DMZ. Core ECRIC infrastructure such as the main database is accessible only from within the Intranet.

The MDT web portal application is deployed within ECRIC as follows. The event broker (1) acts as a secure event bus for event processing units and is deployed within the ECRIC internal network. The units belonging to the application execute as part of the event processing engine [START_REF] Burket | GuardRails : A datacentric web application security framework[END_REF]. The MDT application uses a CouchDB application database (3) which contains the result data from the event-processing backend and provides result data to the web frontend (4). Because ECRIC's firewall only permits connections from the Intranet to the DMZ, we run two instances of the application database: in the Intranet (3) and in the DMZ [START_REF]CouchRest[END_REF]. The application database is replicated periodically between the two instances using CouchDB push replication. The DMZ instance is read-only in order to prevent modifications by the web frontend, thus satisfying requirement S1. Data specific to the web frontend, e.g. session and usage data, is stored separately in a local web database (6) using the SQLite database engine.

Security Properties

Given the lack of third-party SafeWeb applications, we assess the security properties of SafeWeb by analysing its effectiveness in defending against known types of implementation errors. We inspected the Common Vulnerabilities and Exposures (CVE) database for vulnerabilities classified as "Information Disclosure", "Access Control" or "Design Error" and organised them into generic subcategories that share the same underlying cause. We then inject similar vulnerabilities to our MDT application and observe if SafeWeb can prevent them. Omitted Access Checks. The most common problem that leads to information disclosure (e.g. , CVE reports 2011-0701, 2010-2353 and 2010-0752) is the omission of access control checks. To emulate this, we remove the MDT privilege check from the patient filtering routine that normally precedes the filtering of patient details (Listing 2, line 5). Without SafeWeb's taint tracking library (line 2), sensitive information disclosure occurs in line 8. However, when the taint tracking library is included and an MDT requests data they are not allowed to see, the library correctly taints the JSON string (line 8) and displays an error message. Errors in Access Checks. Even when an access control check is present, it may not specify the correct security policy and may result in information disclosure. Often, these errors involve specially constructed input and do not manifest themselves under normal operation, making them hard to discover (e.g. , CVE reports 2011-0449, 2010-3092 and 2010-4403). To introduce such a problem, we modify the user lookup operation (listing 3, line 5) to ignore the case of the username. This may lead to two MDTs sharing privileges. To test this, we create two MDTs with usernames mdt1 and MDT1 but with different privileges. SafeWeb's taint tracking library, when included, successfully prevents access of the second MDT to all the patient details that only the first MDT should see. Inappropriate Access Checks. Security policies are often complicated and developers may not fully understand them. This category of vulnerabilities covers correctly applied checks that do not enforce the intended policy (e.g. , CVE reports 2010-4775 and 2009-2431). To emulate such issues, we remove the check for clinic equality from check privileges (Listing 3, line 7). This effectively enables any MDT to see the data of all the patients in the same hospital. Again, the error does not result in information disclosure: SafeWeb's taint tracking library detects the taint of the output, generates an error and prevents access. Design Errors. The last category captures vulnerabilities due to design errors in the application's business logic (e.g. , CVE reports 2011-0899 and 2010-3933). Such errors involve the application processing sensitive data in unexpected ways that lead to data disclosure. To emulate this, we modify the data aggregator unit to ignore the hospital of origin when matching events. As a result, the unit generates records that mix data of different MDTs. SafeWeb's event processing backend allows access to these events but requires that the output records have labels of all relevant MDTs. Thus, when the frontend attempts to display these records, access is prevented because no MDT has the necessary privileges.

Trusted Codebase. SafeWeb enforces security policies but it does not eliminate trusted code: (1) SafeWeb's taint tracking library must be trusted to correctly authenticate users, associate privileges with their requests, propagate labels and check the labels of each response. (2) The event backend must isolate non-privileged units and label their output. (3) Privileged units must label events that they publish or store in the application database correctly. (4) The policy file that specifies user privileges in the web frontend and unit privileges in the event backend, as well as the scripts that edit it, must be audited for errors. A code audit is still required, but it can focus on the SafeWeb implementation and only includes a small application-specific part. SafeWeb's taint tracking library consists of 1943 LOC and the event processing engine has 1908 LOC. After this trusted codebase has been audited once, data confidentiality only depends on the correctness of a small part of each application. For the MDT web portal, the code that has to be audited involves the two privileged units in the backend (138 LOC) and the code that assigns privileges to new MDTs in the frontend (142 LOC). The confidentiality of patient data does not depend on the other 2841 LOC of the MDT application-no further security audit is required.

Performance Overhead

In this section, we measure the performance overhead of SafeWeb in terms of latency and throughput. All measurements are taken on an AMD Opteron 6136 2.4GHz system with 16 GiB of RAM running Ubuntu 10.04. The 95% confidence interval for each value we report extends to each side at most 5% of the value.

For the web front-end, we measure the page generation time of the MDT application's front page with and without SafeWeb's taint tracking library. We issued 1000 requests and measured the time required to render the response. With SafeWeb's taint tracking library, the page generation time increases by 14% from 158 ms to 180 ms. For the back-end, we measure the average latency of individual events from the data producer to the data storage unit during the processing of 1000 events. With SafeWeb's isolation and label checks, the latency to process a single event increases by 15% from 73 ms to 84 ms. Overall, this is an acceptable overhead for a web application with strong security requirements.

Figure 5 shows a break-down of the overall latency when SafeWeb is enabled. In the front-end, HTTP basic authentication takes 87 ms to which privilege fetching adds 3 ms; processing of the ERB template takes 63 ms, to which label propagation adds 17 ms. "Other" includes operations like network transmission and database access. For the back-end, processing an event takes 51 ms plus 20 ms for serialisation, to which SafeWeb adds 13 ms for label management including label (de)serialisation and checking.

SafeWeb provides ample throughput for the low event rates of the MDT portal. We employ a synthetic benchmark with two units, an event producer and an event consumer, to measure the throughput reduction that SafeWeb incurs. We measured the end-to-end event throughput between the two units by having the producer publishing events at the maximum sustainable rate while confirming that the memory consumption remained stable. We sampled the throughput once per second for 1000 seconds. With label tracking active, event throughput decreased (-17%) from 4455 events/second to 3817 events/second. Due to the language isolation support in Ruby, the decrease in performance is minimal and comparable to approaches that rely on low-level runtime modifications [START_REF] Yip | Improving application security with data flow assertions[END_REF].

Related Work

The most common security problems in web applications arise from the handling of untrusted user data in the application's output. This leads to problems such as XSS and SQL injection attacks. Web application frameworks protect against such vulnerabilities (e.g. XSS, CSRF) [START_REF] Weinberger | An empirical analysis of XSS sanitization in web application frameworks[END_REF]. Applications developed with SafeWeb can still benefit from this (e.g. RailsXSS [START_REF] Railsxss | [END_REF], Rack::Csrf [START_REF] Rack | Csrf[END_REF]) to avoid traditional exploits that often disclose data by hijacking user accounts. In addition, Safe-Web improves these frameworks to prevent sensitive data disclosure.

Such data disclosure is often caused by insufficient authorisation, missing access control checks or by errors in application semantics. Potential solutions include static analysis [START_REF] Huang | Securing web application code by static analysis and runtime protection[END_REF][START_REF] Jovanovic | Pixy: A static analysis tool for detecting web application vulnerabilities[END_REF], symbolic execution [START_REF] Chaudhuri | Symbolic security analysis of Ruby-on-Rails web applications[END_REF] and runtime taint tracking [START_REF] Chin | Efficient character-level taint tracking for Java[END_REF][START_REF] Xu | Taint-enhanced policy enforcement: A practical approach to defeat a wide range of attacks[END_REF][START_REF] Nanda | Dynamic multi-process information flow tracking for web application security[END_REF][START_REF] Pietraszek | Defending against injection attacks through contextsensitive string evaluation[END_REF][START_REF] Yip | Improving application security with data flow assertions[END_REF]. Static analysis tools for dynamic web languages often have high false positive rates [START_REF] Huang | Securing web application code by static analysis and runtime protection[END_REF] or do not support all language features [START_REF] Jovanovic | Pixy: A static analysis tool for detecting web application vulnerabilities[END_REF]. Symbolic execution explores all possible execution paths of a web application and can prove absence of certain errors [START_REF] Chaudhuri | Symbolic security analysis of Ruby-on-Rails web applications[END_REF]. However, devising assertions for symbolic execution is a manual task and involves many of the shortcomings of manual security audits. In contrast, our approach requires minimal developer involvement.

At runtime, access control can be enforced transparently on each operation [START_REF] Ryck | Middleware support for complex and distributed security services in multi-tier web applications[END_REF][START_REF] Burket | GuardRails : A datacentric web application security framework[END_REF] or when sensitive events are received [START_REF] Wun | A policy management framework for content-based publish/subscribe[END_REF]. Nevertheless, if the application has to process sensitive data, errors in the application logic may still convey sensitive information. Taint tracking systems transparently track sensitive data and protect against inadvertent disclosure despite application errors. They have been provided, amongst others, for Java [START_REF] Chin | Efficient character-level taint tracking for Java[END_REF], C [START_REF] Xu | Taint-enhanced policy enforcement: A practical approach to defeat a wide range of attacks[END_REF][START_REF] Nanda | Dynamic multi-process information flow tracking for web application security[END_REF], PHP [START_REF] Pietraszek | Defending against injection attacks through contextsensitive string evaluation[END_REF][START_REF] Yip | Improving application security with data flow assertions[END_REF] and Ruby [START_REF] Burket | GuardRails : A datacentric web application security framework[END_REF]. Simple approaches use one bit taint per string for injection at-tack protection [START_REF] Pietraszek | Defending against injection attacks through contextsensitive string evaluation[END_REF]. In contrast, SafeWeb's taint tracking library attaches full security labels to each variable, offering end-to-end guarantees about sensitive data disclosure. Resin [START_REF] Yip | Improving application security with data flow assertions[END_REF] uses pointers to user-defined policy objects, such as IFC labels; however, it requires extensive language runtime modifications.

Conclusion

We have designed and implemented SafeWeb, a middleware for creating secure, event-based enterprise web applications. It provides strong end-to-end security guarantees, while integrating with existing web development practices. We have demonstrated SafeWeb as part of a web application for assisting cancer treatment practices within the UK National Health Service (NHS).

The strict data security requirements across multiple interacting organisations provided us with a set of real design constraints. The sensitivity of healthcare data required careful consideration of the parts of the middleware that push and pull data. The back-end requirements suited an event-driven design, whereas the front-end is a typical web application. We showed that information flow control can be applied to both the event-processing back-end and the web front-end as part of a middleware. This gives security assurances regarding data disclosure and minimises organisations' code audits.

In future work, we plan to explore how SafeWeb could become the basis for wider deployment of healthcare applications at the national level. Scaling up will involve creating separate, independent regional instances of SafeWeb, which can interact with each other in a secure fashion. In addition, we want to investigate the use of SafeWeb for other classes of web applications.

Fig. 1 .

 1 Fig. 1. Overview of the SafeWeb middleware architecture

1 subscribe 6 subscribe 9 : 10 end 1 .

 169101 '/patient report', 'type=cancer' do |event| 2 list = get 'patient list' 3 list push event[:patient id] 4 set 'patient list', list 5 end '/next day' do |event| 7 list = get 'patient list' 8 publish '/daily report', list, :remove => $LABELS, add => ['label:conf:ecric.org.uk/patient list'] Listing Example unit

Fig. 2 .Fig. 3 .

 23 Fig. 2. Isolation of units and callbacks performed by the event processing engine

Fig. 4 .

 4 Fig. 4. Deployment of the MDT web portal application using SafeWeb within ECRIC's infrastructure

1 require `sinatra' 2 require 7 process r 8 r.to json 9 end 2 . 1 def check privileges id 2 m 3 @ 4 :conditions => { 5 : 6 : 7 : 8 }) > 0 9 end 3 .

 1278921234567893 `safeweb-tracking' 3 get '/records/:mid' do 4 content type :json 5 return nil if !check privileges(params[:mid]) 6 r = Records.by mid(:key => params[:mid])Listing Example of a rule in the web frontend of the MDT web portal = Measurement.find(id) is admin or Privileges.count( u id => User.find by name(@username).id, hospital => m.hospital id, clinic => m.type Listing An access control check used by the MDT web portal

Fig. 5 .

 5 Fig. 5. Processing latency within the MDT web portal application


Democratizing Transactional Programming

Vincent Gramoli Rachid Guerraoui

EPFL Switzerland

Abstract. The transaction abstraction is arguably one of the most appealing middleware paradigms. It lies typically between the programmer of a concurrent or distributed application on the one hand, and the operating system with the underlying network on the other hand. It encapsulates the complex internals of failure recovery and concurrency control, significantly simplifying thereby the life of a non-expert programmer. Yet, some programmers are indeed experts and, for those, the transaction abstraction turns out to be inherently restrictive in its classic form. We argue for a genuine democratization of the paradigm, with different transactional semantics to be used by different programmers and composed within the same application.

A Brief History of Transaction

The transaction abstraction is in essence a middleware paradigm: it allows multiple processes running on one or more processors (machines) to interact. The transaction abstraction lies typically between the programmer of concurrent and distributed applications and the operating system. It encapsulates complex concurrency control and failure recovery mechanisms behind a simple user interface.

The transaction abstraction is very old. It dates back to the 70's when it was proposed as a means to ensure the consistency of shared data [START_REF] Eswaran | The notions of consistency and predicate locks in a database system[END_REF], determined with respect to a sequential behavior. To formalize this notion of consistency, the serializability definition recast the consistency of an execution of transactions in terms of its equivalence to a sequential execution of transactions [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF]: concurrent accesses have to behave as if they were executing sequentially-in other words, they must be atomic. Since that definition, researchers have derived other variants, like opacity [START_REF] Guerraoui | Principles of Transactional Memory[END_REF], applicable to different transactional contexts.

Formerly used in databases, the transaction abstraction was adapted for the first time as a language construct in the form of guards and actions [START_REF] Liskov | Guardians and actions: linguistic support for robust, distributed programs[END_REF] in particular to address issues like robustness to hardware failures. The programmability of transactions has subsequently been studied in distributed systems in various forms, e.g., Argus [START_REF] Liskov | The argus language and system[END_REF], Eden [START_REF] Almes | The eden system: A technical review[END_REF] and ACS [START_REF] Guerraoui | Nesting actions through asynchronous message passing: the ACS protocol[END_REF]. During that period, the first hardware support for such a transactional construct was invented to introduce parallelism in functional languages by providing synchronization on multiple memory words [START_REF] Knight | An architecture for mostly functional languages[END_REF].

Later, transactional memory was proposed for concurrent programming especially to remedy the existing difficulties of programming with locks, e.g., priority Fig. 1. A brief history of transactions inversion, lock-convoying and deadlocks [START_REF] Herlihy | Transactional memory: architectural support for lockfree data structures[END_REF]. Since the advent of multicore architectures, the very notion of transaction memory has became an active topic of research1 . Hardware implementations of such transactional systems [START_REF] Herlihy | Transactional memory: architectural support for lockfree data structures[END_REF] were generally limited by specific constraints and the programmer could only abstract away from these limitations using unbounded hardware transactions, a complex solution that most industrials are no longer exploring. Instead, a more hybrid tendency was adopted by implementing a best-effort hardware component that needs to be complemented by software transactions [START_REF] Dice | Early experience with a commercial hardware transactional memory implementation[END_REF][START_REF] Diestelhorst | Sane semantics of best-effort hardware transactional memory[END_REF][START_REF] Dalessandro | Hybrid NOrec: a case study in the effectiveness of best effort hardware transactional memory[END_REF][START_REF] Felber | The velox transactional memory stack[END_REF].

Software transactions were originally designed as a portable solution to execute a set of shared memory accesses fixed prior to execution [START_REF] Shavit | Software transactional memory[END_REF]. Later software transactions were applied to a dynamic variant of this model, in which the control flow of the transaction was not predetermined [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF]. Besides improvements stemming from the usage of timely information [START_REF] Dice | Transactional locking II[END_REF][START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF], new software transactions were derived to access more complex objects [START_REF] Dragojevic | Stretching transactional memory[END_REF][START_REF] Guerraoui | STMBench7: a benchmark for software transactional memory[END_REF]. Nowadays, software transactions are even used in concurrent programs for the sake of coordinated failure recovery [START_REF] Harmanci | Atomic boxes: Coordinated exception handling with transactional memory[END_REF]. Despite these promising results, early investigations on the performance of software transactions have suggested their confinement to a research toy by questioning their ability to leverage multicore architectures [START_REF] Cascaval | Software transactional memory: Why is it only a research toy?[END_REF].

Software transactions have finally won their spurs by outperforming sequential applications with only few cores. The result of [START_REF] Dragojevic | Why STM can be more than a research toy[END_REF] shows that an STM with manually instrumented benchmarks and explicit privatization outperforms sequential code by up to 29 times on SPARC with 64 concurrent threads and by up to 9 times on x86 with 16 concurrent threads. Even though the software overheads, induced by compiler instrumentation and transparent privatization, do not prevent transactions from outperforming sequential code, performance remains one of the major issue of transactions. Basically, an expert will never be able to extract as much concurrency from classic transactions than from synchronization primitives under the hood.

Not surprisingly, researchers have kept exploring possible relaxations of the classic model since the early stage of transactions. Nesting models exploited commutativity of high level operations to favor concurrency [START_REF] Lynch | Multilevel atomicity a new correctness criterion for database concurrency control[END_REF][START_REF] Moss | Open nested transactions: Semantics and support[END_REF]. In short, commutativity applies to operations whose order does not impact the transaction outcome. Such techniques would typically require the programmer to identify operations that can commute statically or to introduce code breakpoints. Others were dedicated to improve performance of typical contention hotspots: relaxed transactions were proposed for aggregate fields of database systems [START_REF] Reuter | Concurrency on high-traffic data elements[END_REF][START_REF] O'neil | The escrow transactional method[END_REF] on the one hand, and for search structures of multicore programs [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF][START_REF] Felber | Elastic transactions[END_REF] on the other hand. A large majority of these relaxations rely however on complex code refactoring to improve performance and only a few, like [START_REF] Felber | Elastic transactions[END_REF], preserve both the sequential code and composition, most of them remaining non-exploitable by novice programmers.

To summarize, the transaction is an old appealing abstraction that has been the main topic of many practical and theoretical achievements in research, however, it has never been widely adopted in practice. Despite their genericness, transactions failed to be unified across distinct usages. Instead, transactions have always been tuned differently for different purposes, enforcing their incompatibility. An example is the recent adoption of transactions by IBM in their BlueGene/Q processor. This choice has been made in order to obtain the fastest supercomputer ever, yet only a very limited set of applications, which are supercomputing applications, will benefit from these highly tuned transactions. The incompatibility between distinct transactions breaks the appeal of the abstraction itself and prevents it from being used by the masses.

The Inherent Appeal of Transactions

The transaction paradigm is appealing for its simplicity as it preserves sequential code by hiding synchronization internals and its ability to promote concurrent code composition.

Algorithm 1 An implementation of a linked list operation with transactions return result;

Preserving sequentiality

Transactions preserve the sequential code in that their usage does not alter the sequential code, besides segmenting it into several transactions. More precisely, the regions of sequential code that must remain atomic in a concurrent context are simply delimited, typically by a transaction{...} block or similar tx-begin/tx-commit delimiters, as depicted in Algorithm 1-the existing data organization appears unchanged (Algorithm 2 (left)).

Programming with transactions shifts the inherent complexity of concurrent programming to the implementation of the transaction abstraction which must be done once for all. Thanks to transactions, writing a concurrent application follows a divide-and-conquer strategy where experts have the complex task of writing a live and safe transaction system with an unsophisticated interface so that the novice has simply to write a transaction-based application, namely delimit regions of sequential code.

Algorithm 2

The linked list node On the one hand, traditional synchronization techniques require generally the programmer to first re-factorize the sequential code. Using lock-free techniques, the programmer would typically need to use subtle mechanisms, like logical deletion, to prevent inconsistent memory deallocations, yet the memory management would not even be guaranteed to be simple, and may require additional re-engineering [START_REF] Michael | High performance dynamic lock-free hash tables and list-based sets[END_REF]. Using lock-based techniques, the programmer must explicitly declare and initialize all locks before protecting memory accesses as depicted in Algorithm 2; the programmer may even need to use a logical deletion technique as well as an additional validation phase to guarantee consistency [START_REF] Heller | A lazy concurrent list-based set algorithm[END_REF]. On the other hand, the transaction abstraction hides both synchronization internals and metadata management. If locks are internally used, they are declared and initialized transparently by the transaction system. Moreover, as the transaction system wraps memory accesses, a simple reference counting can keep track of the status of transactions accessing a particular location, before freeing the memory.

Transac'on

Despite its apparent simplicity and as depicted in Figure 2, the transaction system internally hides complex synchronization mechanisms. For example a single transactional system can exploit (i) time, to associate timestamps to values and guarantee that all values read belong to the same snapshot the transaction is acting upon; (ii) locks, for concurrent transactions to detect conflicts when accessing common data; and (iii) logs, to record operations that will be reexecuted at commit time, or rolled back at abort time.

Enabling composition

Transactions are also appealing for they allow concurrent programs to be reused in a modular fashion. More specifically, transactions allow Bob to compose existing transactional operations developed by Alice into a composite one that preserves the safety and liveness of its components [START_REF] Harris | Composable memory transactions[END_REF] as depicted in Figure 3. By contrast, alternative synchronization techniques do not facilitate composition. For example, consider a simple directory abstraction mapping a name to a file. With transactions, one can compose the removal of a name and the creation of a new name into a rename action. If a user renames a file from one directory d 1 to another d 2 while another rename a file from d 2 to d 1 , directories must be protected with care to avoid deadlocks. In the lock-based file system hierarchy of the Google File System [START_REF] Ghemawat | The google file system[END_REF], each directory at the same path depth has to be locked in a pre-determined ordering to prevent deadlock in such a scenario. In other words, Bob must first understand the locking strategy of Alice to ensure the liveness of his own operations. For the same reason, the header of the Linux kernel file mm/filemap.c comprises 50 lines of comments explaining the locking strategy.

Existing lock-free techniques are even more complex as they require a multiword compare-and-swap to make the two renaming actions atomic while retaining concurrency [START_REF] Greenwald | Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS[END_REF].

By contrast, a transaction system detects a conflict between the two renaming transactions and let only one of the two commit, the other one is restarted or resumed later. Deciding upon the conflict resolution strategy is the task of a dedicated service, called a contention manager and various strategies have been proposed [START_REF] Scherer | Advanced contention management for dynamic software transactional memory[END_REF].

The Inherent Limitations of Transactions

A transaction delimits a region of accesses to shared locations and protects the set of locations that is accessed in this region. By contrast, a (fine-grained) lock generally protects a single location even though it is held during a series of accesses as depicted in Algorithm 3. This makes a crucial difference between transactions and locks in terms of expressiveness, concurrency and performance.

Algorithm 3 An implementation of a linked list operation with locks

Lacking expressiveness

To make our point that transactions are inherently limited in terms of expressiveness we define atomicity as a binary relation over shared memory accesses π and π of a single transaction within an execution α: atomicity(π, π ) is true if π and π appear in α as if they were both occurring at one common indivisible point of the execution. It is important to notice that this relation is not transitive, i.e., atomicity(π 1 , π 2 ) ∧ atomicity(π 2 , π 3 ) ⇒ atomicity(π 1 , π 3 ). In fact, as π 2 may appear to have executed at several consecutive points of the execution, the points at which π 1 and π 2 appear to have occurred may be disjoint from the points at which π 2 and π 3 appear to have occurred.

A process locking x during the point interval (p 1 ; p 2 ) of α, in which it accesses x, is guaranteed that any of its other accesses during this interval will appear atomic with its access to x. For example, the process guarantees atomicity(r(x), r(y)) and atomicity(r(y), r(z)) but not atomicity(r(x), r(z)) in the following lock-based program:

P = lock(x) r(x) lock(y) r(y) unlock(x) lock(z) r(z) unlock(y) unlock(z).
Conversely, a process executing the following transaction block ensures atomicity(r(x), r(y)), atomicity(r(y), r(z)) but also atomicity(r(x), r(z)), which is the transitive closure of the atomicity relations guaranteed by P . Note that there is no way to ensure the two former atomicity relations with classic transactions without also ensuring the latter.

P t = transaction{r(x) r(y) r(z)}.
This lack of expressiveness when using transactions is directly implied by their syntax, which consists of an open/close block delimiting a compound statement [START_REF]Transactional Memory Specification Drafting Group: Draft specification of transactional language constructs for C++[END_REF]. In this sense, this expressiveness limitation is not related to the way transactions are used but to the transaction abstraction itself. This open/close block does neither accept a memory location nor a semantic hint as a parameter. Hence, it blindly guarantees that all its accesses appear as if there was an indivisible point in the execution where they all take effect.

Admi%ed schedules Precluded schedules

Fig. 4. Among the correct linked list schedules, 20% of them are precluded when using transactions.

Impact on concurrency

The level of expressiveness is crucial especially when it restricts the set of acceptable schedules, and hence achievable concurrency, in a real workload. The low expressiveness of transactions translates actually into a concurrency loss on very common workloads. For example, consider the transactional linked list program depicted in Algorithm 1. Clearly, the value of the head → next pointer observed by the transaction (Line 6) is no longer important when the transaction is checking whether the value val corresponds to a value of a node further in the list (Line 7), yet a concurrent modification of head → next can invalidate the transaction when reading next → val ; this is a false-conflict leading to unnecessary aborts. Such unnecessary aborts limit concurrency because they preclude schedules that would be correct, be all the transactions committed [START_REF] Gramoli | On the input acceptance of transactional memory[END_REF]. Conversely, the hand-over-hand locking program of Algorithm 3 allows such concurrent update (Line 7) when checking the value (Line 8), starting from the second iteration of the while-loop. Lock-free linked list algorithms [START_REF] Harris | A pragmatic implementation of non-blocking linked-lists[END_REF][START_REF] Michael | High performance dynamic lock-free hash tables and list-based sets[END_REF] would not suffer such false-conflict either.

To quantify the impact of the limited expressiveness of transactions on the number of accepted schedules, consider that program P t above executes concurrently with program P 1 = transaction{w(x)} and P 2 = transaction{w(z)}. As there are four ways of placing the single access of one of these two programs between accesses of P t and five ways of placing the remaining one in the resulting schedule, there are twenty possible schedules. Note that all are allowed in a linked list implementation; however, transactions that ensure opacity [START_REF] Guerraoui | Principles of Transactional Memory[END_REF] (as it is the case for most classic ones) preclude four of these schedules: those in which P t accesses x before P 1 (P t ≺ P 1 ), P 1 terminates before P 2 starts (P 1 ≺ P 2 ) and in which P 2 accesses z before P t (P 2 ≺ P t ). The proportion of schedules precluded by transactions among all possible ones is depicted in Figure 4.

Impact on performance

The metadata management overhead of transactions when starting, accessing shared memory and committing, is expected to be compensated by exploiting concurrency [START_REF] Dragojevic | Why STM can be more than a research toy[END_REF]. In scenarios like the previous linked list program where transactions fail to fully exploit all available concurrency, their performance cannot compete with lock-based or lock-free algorithms. Recall that this is due to the expressiveness limitation inherent to transactions-it is thus not tied to the way transactions are used but to the abstraction itself. The conjunction of overhead and limited concurrency of transactions prevents them from outperforming wellengineered lock-based and lock-free alternatives.

To illustrate the impact on performance, we compared the existing Java concurrency package to a classic transaction library written in Java, TL2 [START_REF] Dice | Transactional locking II[END_REF], on a 64-way Niagara 2 machine. We present the results obtained on a simple Collection benchmark of 2 12 elements providing contains, add, remove and size operations with an update and a size ratios of 10% each. As the existing lock-free data structures do not support atomic size we had to use the copyOnWriteArraySet workaround of this package as recommended for circumventing this limitation [START_REF] Peierls | Java Concurrency in Practice[END_REF]. We compared it against the linked list implementation building upon TL2. The throughput speedups over sequential of classic transaction and the existing collection are depicted in Figure 5. The existing collection performs 2.2× faster than classic transactions on 64 threads.

Democratizing Transactions: the Challenge

Classic transactions share a single semantics for all types of applications. This simplifies the development of a transaction system by requiring the same guarantee for all its transactions, independently from their role in the concurrent applications. In some scenarios this semantics is, however, overly conservative and limits concurrency and performance (cf. Section 3). Without additional control, skilled programmers are frustrated by not being able to obtain highly efficient concurrent programs as depicted in Figure 6. In order to rather exploit adequately the concurrency allowed by the semantics of an application it is necessary to trade part of the simplicity of transactional memory for additional control.

We argue that for the transactional abstraction to really become a widely used programming paradigm it should be democratized. Not only is it important for transactions to be an off-the-shelf solution for novices, but also to give additional control to experts in concurrent programming.

Therefore, we believe that various transaction semantics should be able to run concurrently: a default semantics capturing the classic single-global-lock atomicity (i.e., opacity [START_REF] Guerraoui | Principles of Transactional Memory[END_REF]), and more complex semantics capturing more subtle behaviors (e.g., elastic-opacity [START_REF] Felber | Elastic transactions[END_REF]). The challenge is twofold. First, the trans-

Transac'on

tx--begin() tx--commit() Fig. 6. The novice programmer benefits from the simplicity of transactions whereas the expert programmer is frustrated by its lack of flexibility action abstraction should allow the expert programmers to easily express hints about the targeted application semantics without modifying the sequential code but simply delimiting its regions like for classic transactions. Second, the semantics of each transaction must be preserved even though multiple transactions of different semantics can access common data concurrently.

This second property is crucial and makes the development of a transactional system even more complex.

Expressiveness and simplicity

Several relaxed transaction models have been proposed as an alternative to the classic transaction model. Such relaxed models can generally achieve a greater level of flexibility than the classic model by avoiding unnecessary aborts thus tolerating additional schedules.

An explicit early release can be used to ask statically the transaction to ignore false conflicts [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF] and hence avoid unnecessary aborts. For example, to achieve the same expressiveness as the lock-based linked list of Algorithm 3 one could use early release to force the transaction to unprotect some of its read locations while executing. More precisely, a release call of location x could indicate from which point of the transaction all conflicts involving its read of x can start being ignored. Despite increasing expressiveness, the use of early release may hamper transaction composition. Alice may implement an atomic linked list add(x) using early release, yet Bob cannot reuse Alice's code to develop an atomic addIfAbsent(x, y) that inserts x only if y is absent. Typically, the resulting operation would not be atomic: two instances addIfAbsent(x, y) and addIfAbsent(y, x) may insert concurrently x and y, leading to an inconsistency.

A first relaxing methodology consists in open nesting [START_REF] Moss | Open nested transactions: Semantics and support[END_REF] that is considered effective to increase concurrency. The key underlying idea is that nested transactions typically commit before the outer transaction ends but pass a high level abstraction of their changes to the outer transaction. As a result, the changes committed by a nested transaction become immediately visible from concurrent transactions and abstract locks indicate which pairs of nested operations conflict. Open nesting may lead to deadlocks if the accesses to shared locations are not ordered with care [START_REF] Ni | Open nesting in software transactional memory[END_REF]. Specifically, this problem is similar to the one raised with explicit locks as open nesting let the programmers acquire abstract locks even upon abort.

A second relaxing methodology is transactional boosting [START_REF] Herlihy | Transactional boosting: A methodology for highlyconcurrent transactional objects[END_REF]. It benefits from commutativity by considering transactional operations at a high level of abstraction. If two high level operations commute, they can be executed in any order despite the conflicts between their low-level operations. To this end, high level operations are considered as a whole and the programmer must identify operations that commute and define inverse operations. Considering higher level operations diminishes the amount of information that needs to be logged and possibly rolled back. Each operation acquires an abstract lock similar to open nesting so that two operations conflict if and only if they do not commute. Upon abort, a transaction rolls back its changes by executing the appropriate inverse operations that compensate its logged operations. Typically such models require the programmer to identify commutative operations and to write an appropriate compensating block of action for each non-commutative operation, such a compensate block is typically as long as the corresponding transaction block itself.

Inherently more complex to use than the classic transaction model, these initial relaxed transaction models lost the appealing aspects of transactions: either by requiring significant code refactoring or by breaking composition. Therefore, it is crucial to guarantee sequential code preservation and transaction composition when deriving new relaxed models targeting high expressiveness.

Sequentiality and composition

A relaxed transaction model preserving sequential code and guaranteeing composition was proposed as the elastic transaction model [START_REF] Felber | Elastic transactions[END_REF]. This model provides a semantics of transactions that enables to efficiently implement search structures. Just like for a classic transaction, the programmer must simply delimit the blocks of code that represent elastic transactions, thus preserving sequential code as depicted in Algorithm 4. Elastic transactions are fully compatible with classic transactions thus inheriting the ability to compose of the classic model. Bob directly encapsulates Alice's elastic transactions, into another transaction, choosing between labeling it as elastic or classic, hence guaranteeing atomicity and deadlock-freedom of its own operation. Typically, Bob can easily compose Alice's elastic add(x) into a classic addIfAbsent(x, y).

In contrast with classic transactions, during its execution an elastic transaction can be cut (by the elastic transactional system) into multiple classic transactions, depending on the conflicts it detects. For example, consider the following history of shared accesses in which transaction j adds 1 while transaction i is parsing the data structure to add 3 at its end.

H = r(h) i , r(n) i , r(h) j , r(n) j , w(h) j , r(t) i , w(n) i .
This history is clearly neither serializable [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF] nor opaque [START_REF] Guerraoui | Principles of Transactional Memory[END_REF] since there is no history in which transactions i and j execute sequentially and where r(h) i occurs Algorithm 4 Java pseudocode of the add() operation with elastic transactions } before w(h) j and r(n) j occurs before w(n) i (yet the high level insert operations of this history are atomic). A traditional transactional scheme would detect two contradicting conflicts between transactions i and j, and the transactions could not both commit. Nonetheless, history H does not violate the correctness of the integer set: 1 appears to be added before 3 in the linked list and both are present at the end of the execution. The programmer has simply to label transaction i as being elastic to solve this issue. Then, history H can be viewed as the combination of several pieces:

f (H) = r(h) i , r(n) i s1 , r(h) j , r(n) j , w(h) j , r(t) i , w(n) i s2 .
In f (H), elastic transaction i has been cut into two transactions s 1 and s 2 . Crucial to the correctness of this cut no two modifications on n and t have occurred between r(n) s1 and r(t) s2 . Otherwise the transaction would have to abort.

These cuts enable more concurrency than what the expert programmer could do with classic transactions. First, a cut can split dynamically an elastic transaction depending on the interleaving of its accesses with other transaction accesses, yet it would be incorrect to replace statically the elastic transaction by multiple classic transactions, as the interleaving is not predictable. Second, identifying commutativity of accesses cannot enable the concurrency of elastic transactions because, depending on the current interleaving of accesses, two accesses that are (statically) non-commutative can be considered dynamically-commuting in elastic transactions. For example, elastic transactions enable additional concurrency between two linked list adds by allowing the history involving transactions t 1 and t 2 : r(h) t1 , r(n) t2 , w(h) t2 , w(n) t1 in which neither r(n) t2 and w(n) t1 nor r(h) t1 and w(h) t2 commute.

Impact on performance

To illustrate the benefit of combining relaxed and classic transactions, the collection benchmark was run in the exact same settings as the one used to obtain Figure 5. Each of the three parse operations contains, add and remove is implemented with an elastic transaction and the size operation, which returns an atomic snapshot of the number of elements, is implemented with a classic transaction to ensure atomicity of all four operations. As an example, the Java pseudocode of the add operation based on an elastic transaction is depicted in Algorithm 4. The performance of combining elastic transactions with classic transactions, is compared in Figure 7 against the performance obtained with the existing concurrent collection package and with the classic transactions alone. The best performance we obtained by combining elastic and classic transactions is higher than classic transactions alone by 3.5× and than the existing collection package by 1.6×. Unfortunately, the performance does not scale up to the maximum number of threads 64. We conjecture that the slow-down between 32 and 64 threads by repeatedly aborting the size operations, in the same vein as balance operations of the bank benchmark [START_REF] Harmanci | Extensible transactional memory testbed[END_REF] or toxic transactions [START_REF] Liu | Toxic transactions[END_REF]. More precisely, the size executes within a classic transaction that has limited concurrency and which may thus produce an abort each time a concurrent update (add or remove) is modifying concurrently any location of the data structure.

Mixing Several Semantics

Mixing semantics means providing multiple transactions of different semantics to let the programmer choose the right semantics for each delimited region of the program. As these transactions can potentially access concurrently the same locations, it is crucial that one transaction does not alter the semantics of the others.

More precisely, we consider the semantic of classic transactions, opacity, to be the strongest one. Hence the novice can use exclusively the default semantics for all transactions, making sure that the resulting program is correct. Nevertheless, the expert can use a relaxed semantics that preserves sequential code (like elastic one) for some transactions and the classic one for others, to obtain higher expressiveness and better performance. The challenge is to preserve the semantics of all individual transactions. In the case of mixing elastic with classic transactions the resulting correct histories should thus be equivalent to a sequential legal history of elastic sub-transactions and classic transactions, as long as elastic sub-transactions result from consistent cuts (as required by the elastic transaction semantics). Consequently, mixing additional semantics may become rapidly challenging.

Mixed

Transac-ons tx--begin(hint) tx--commit() The key idea of mixing several semantics relies on providing various kinds of transactions among which the programmer can choose the adequate one that better matches its needs. More specifically, the programmer can start a transaction that executes the default intuitive semantics unless the tx-begin call is given some parameter, that serves as a hint to indicate the transaction semantics. With mixed semantics, not only does the transaction remain an off-the-shelf paradigm for novices, but it also gives control to the experts to boost the performance of some transactions (Figure 8).

Combining classic, snapshot and elastic transactions

To go a step further in exploiting mixed transactions, here is an example of an additional transaction semantics, called snapshot, in addition to the two preexisting ones, elastic and classic. This snapshot transaction semantics provides a way for the programmer to implement an atomic snapshot operation that can run concurrently with updating transactions (elastic or classic) modifying the data structure in a complex way (even at distinct locations). This is typically an appealing semantics to design an operation whose result depends on multiple elements of the data structure, like a Java Iterator. As an example, a size operation preserving sequential code and that is depicted in Algorithm 5 uses a snapshot transaction.

Algorithm 5 Java pseudocode of the size() operation with snapshot transactions The key idea is for the snapshot to detect the locations that have been concurrently modified and to exploit multiversion concurrency control to bypass these conflicts. Using a global counter and version numbers associated with location values, the snapshot can detect at read time whether a location has been concurrently updated by comparing its current version to the value of the global counter at the time the snapshot started. If such a concurrent modification is detected, the snapshot has to select an old value (with a lower version number) of the overwritten location that is consistent with the start time of the snapshot transaction (i.e., higher than the value of the global counter at the time it started).

More precisely, multiple versions must be maintained at each location by every update transaction, be they elastic or classic-in our case two versions were maintained, this was actually sufficient to speed up the performance significantly. All update transactions create a backup value-version pair before overwriting them. The snapshot transaction has simply to detect whether the location it aims at accessing has a higher version than its upper bound ub to try getting an older version that could let it commit. Naturally, the snapshot transaction may have to abort if the older version is still too recent as no transactions keep track of more than two versions here.

Impact on performance

The performance obtained when combining snapshot semantics in addition to the elastic one on the previous collection benchmark is depicted in Figure 9. The mixed transaction model performs 4.3× faster than the classic transaction model, TL2, and improves the concurrent collection package by 1.9× on 64 threads. Thanks to the snapshot semantics that remedy the scalability issue of the classic transactions, size operation in snapshot transactions commit more frequently than in default transactions. The reason is that a snapshot size returns potentially stale values that have been concurrently overwritten, while classic size would abort. Even though the overhead of the polymorphic transactions makes it slower than the concurrent collection package at low levels of parallelism, the performance scales well with the level of concurrency up to the maximum number of hardware threads we had at our disposal, and compensates the overhead effect at high level of parallelism.

The transaction abstraction is in essence a middleware paradigm that allows multiple processes running on one or more processors (machines) to interact. The transaction abstraction was proposed long ago and has constituted an active area of research over the years.

Yet, transactions have not been widely adopted in practical concurrent and distributed programming and this is due, we believe, to their inherent cost and limited concurrency. In short, expert programmers need an alternative to bypass the simplicity of the concept and express their skills, potentially to obtain better performance.

We argue for democratizing the concept by enabling the co-existence of different semantics of it in the same application. Although a novice programmer will still be able to exploit the simplicity of the transaction abstraction in its default semantics, expert programmers would exploit, when possible, more expressive semantics of relaxed transaction models to gain in concurrency. This raises new challenges to guarantee that various semantics can cohabit smoothly in the same system but promises to further leverage the transaction abstraction.

Fig. 2 .

 2 Fig. 2. The transaction abstraction hides complex synchronization mechanisms behind a simple interface.

Fig. 3 .

 3 Fig. 3. Bob composes Alice's component operations remove and create into a new operation rename that preserves the safety and liveness of its components

Fig. 5 .

 5 Fig. 5. Throughput (normalized over the sequential one) of classic transactions and the existing concurrent collection.

Fig. 7 .

 7 Fig. 7. Throughput (normalized over the sequential one) of elastic and classic transactions, the classic transactions alone and the existing concurrent collection.

Fig. 8 .

 8 Fig. 8. Novice and expert programmers should both benefit from the simplicity and flexibility of a mixed transactional model.

Fig. 9 .

 9 Fig. 9. Throughput (normalized over the sequential one) of the mixed transactions, the classic transaction and the collection package.

A bibliography of the topic can be found at http://www.cs.wisc.edu/trans-memory/biblio/list.html.