Florian Kerschbaum
email: florian.kerschbaum@uwaterloo.ca

Martin Härterich
email: martin.haerterich@sap.com

Searchable Encryption to Reduce Encryption Degradation in Adjustably Encrypted Databases

Processing queries on encrypted data protects sensitive data stored in cloud databases. CryptDB has introduced the approach of adjustable encryption for such processing. A database column is adjusted to the necessary level of encryption, e.g. order-preserving, for the set of executed queries, but never reversed. This has the drawback that long running cloud databases will eventually transform into only orderpreserving encrypted databases. In this paper we propose searchable encryption as an alternative in order to reduce this encryption degradation. It maintains security while only marginally impacting performance when applied only to infrequently used queries for searching. We present a budget-based encryption selection algorithm as part of query planning for making the appropriate choice between searchable and deterministic or order-preserving encryption. We evaluate our algorithm on a long-tail distributed TPC-C benchmark on an experimental implementation of encrypted queries in an in-memory database. In one choice of parameters our algorithm incurs only a 1.5% performance penalty, but one of 15 columns is not decrypted to order-preserving or deterministic encryption. Our selection algorithm is configurable, such that higher security gains are possible at the cost of performance.

Introduction

In order to protect cloud databases data can be processed in encrypted form [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF][START_REF] Hacigümüs | Efficient execution of aggregation queries over encrypted relational databases[END_REF][START_REF] Hacigümüs | Executing sql over encrypted data in the database-service-provider model[END_REF][START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF][START_REF] Tu | Processing analytical queries over encrypted data[END_REF]. A common way to enable processing of encrypted data is orderpreserving encryption [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF][START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF][START_REF] Kerschbaum | Frequency-hiding order-preserving encryption[END_REF][START_REF] Kerschbaum | Optimal average-complexity ideal-security orderpreserving encryption[END_REF][START_REF] Popa | An ideal-security protocol for orderpreserving encoding[END_REF]. Order-preserving encryption allows processing many SQL queries without modification. However, order-preserving encryption is susceptible to simple attacks on the static data [START_REF] Naveed | Inference attacks on property-preserving encrypted databases[END_REF].

In order to increase security CryptDB has introduced adjustable encryption [START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF]. The idea is to layer encryption in onions. Queries are analyzed and the encryption layer is adjusted before their execution.

This has the positive effect that only the layers necessary for the query execution, e.g. deterministic encryption instead of order-preserving encryption, are revealed and thus security is increased. A database starts in a completely secure (cold) mode and transforms into a (hot) mode which is very efficient, since no more decryption operations are necessary, but all queries can be processed on the data as is. This transformation is also never reversed. Since it is not possible to determine when a cloud database has been compromised, there is no reason to encrypt data which has once been revealed to the cloud service provider.

This lack of reversion has the negative consequence that many databases may ultimately reach a state that has only order-preserving encrypted columns. Hence, in a long running database system adjustable encryption may be no better than pure order-preserving encryption. The set of all queries determines the encryption level, even if those queries contribute little to the overall load of the database. Particularly, the long tail of the query distribution may have a severe negative security effect. These queries are infrequently executed, e.g. only once, presumably using columns that are infrequently used for searching, but have the same impact on the security as the most frequently reoccurring ones. This paper proposes dealing with these infrequent queries differently in order to confine their impact.

This raises two research questions: First, how to detect infrequently used columns and second, how to handle them. For the second problem we propose to use searchable encryption [START_REF] Cash | Highlyscalable searchable symmetric encryption with support for boolean queries[END_REF][START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF][START_REF] Hahn | Searchable encryption with secure and efficient updates[END_REF][START_REF] Hahn | Poly-logarithmic range queries on encrypted data with small leakage[END_REF]. Searchable encryption is a randomized, strongly secure encryption scheme where the key holder can issue tokens for equality or range searches. The search algorithm is different than in a regular table scan and also significantly slower. Yet, all data for which no token has been issued remains semantically secure. Hence, searchable encryption is particularly suited for infrequently searched columns, since the search pattern is sparse.

For the first problem we propose a more intelligent encryption selection algorithm. It now has two choices: searchable encryption and order-preserving or deterministic encryption. It will first try searchable encryption until a certain threshold has been reached and only then decrypt. This increases the time for transforming from a cold to a hot database, but handles infrequently used columns with searchable encryption.

We perform a set of experiments using the TPC-C benchmark on our algorithms in an implementation of encrypted queries in an in-memory, column-store database. Our algorithm is configurable in order to allow different trade-offs between security and performance according to the preference of the database administrator. However, we were particularly interested in a set of parameters where the gain of security is clearly higher than the cost of security. In one particular choice of parameters our algorithm may incur only a small 1.5% performance penalty, but the most infrequently used column is not decrypted. Note that the economic value of a single non-decrypted column can be very high for sensitive data, such as salaries, outstanding sales prices or health care data. Due to the difficulty of scientifically assessing sensitivity values, we only report the percentage of still randomly encrypted data; in our case a 6.7% security improvement which is still more than 4 times the performance penalty. We also show in detail the different trade-offs between security and performance in query planning for different parameters of the algorithm (Section 5).

Queries on Encrypted Data

Hacigümüs et al. introduce the first database for processing SQL queries on encrypted data [START_REF] Hacigümüs | Executing sql over encrypted data in the database-service-provider model[END_REF]. They use deterministic encryption and binning for range queries. Binning requires the client to post-process the result and filter nonmatching entries. Agrawal et al. improve on this by order-preserving encryption [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF]. In order-preserving encryption plaintexts are mapped to ciphertext in the same order. This removes the necessity for post-processing (and query rewriting) and range queries can be processed with the same relational operator as on plaintexts. Later, Popa et al. extend this concept using adjustable encryption which adjusts the ciphertext to the query [START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF]. Hang et al. also show how to implement this over multiple keys [START_REF] Hang | Enki: Access control for encrypted query processing[END_REF].

Boldyreva et al. formalize order-preserving encryption [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF]. They provide a proof that their scheme is the best possible stateless encryption scheme [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF]. Recently Naveed et al. have shown that this security definition is rather weak and simple attacks can exploit the static leakage of order-preserving encryption [START_REF] Naveed | Inference attacks on property-preserving encrypted databases[END_REF]. A stronger notions of security -indistinguishability under (frequency-analysing) order-preserving chosen plaintext attack -are achieved by the scheme by Popa et al. [START_REF] Popa | An ideal-security protocol for orderpreserving encoding[END_REF] and Kerschbaum [START_REF] Kerschbaum | Frequency-hiding order-preserving encryption[END_REF], respectively. Yet, their schemes are not efficiently compatible with adjustable encryption. Hence, system builders have to make a choice between the two. Our experiments indicate that adjustable encryption has a high security improvement, e.g. in the TPC-C benchmark only 15 columns need to use deterministic encryption. We hence believe that adjustable encryption is preferable to a stronger order-preserving encryption.

We build on adjustable encryption providing a further enhancement of security. Particularly, we introduce a query planning algorithm for searchable encryption in order to handle infrequently used columns in adjustable encryption, such that even not all 15 columns need to be deterministic.

Searchable Encryption

Searchable encryption offers stronger security than order-preserving or deterministic encryption. Using a token generated by the secret key one can search for values or within ranges. Without the token the ciphertext is as secure as common standard encryption.

The first sub-linear search time, (inverted) index-based searchable encryption scheme was introduced by Curtmola et al. [START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF]. Its idea is to provide an index of deterministically encrypted keywords and an encrypted list of documents. Since each deterministic ciphertext is unique, these schemes are not as susceptible to frequency analysis, but still more efficient to search. Hahn and Kerschbaum showed how the index can be built from the access pattern [START_REF] Hahn | Searchable encryption with secure and efficient updates[END_REF].

Searchable encryption also supports complex queries. The fastest method has been proposed by Demertzis et al. in [START_REF] Demertzis | Practical private range search revisited[END_REF] where all subranges in the disjunctions are indexed (and leaked on a match).

There exist also a large number of applications which have been developed on top of encrypted, in-memory, column-store database with specific protocols, e.g., benchmarking [START_REF] Catrina | Fostering the uptake of secure multiparty computation in e-commerce[END_REF][START_REF] Kerschbaum | Building a privacy-preserving benchmarking enterprise system[END_REF][START_REF] Kerschbaum | Practical privacy-preserving benchmarking[END_REF][START_REF] Kerschbaum | On the practical importance of communication complexity for secure multi-party computation protocols[END_REF][START_REF] Kerschbaum | Automatic protocol selection in secure two-party computations[END_REF][START_REF] Kerschbaum | Filtering for private collaborative benchmarking[END_REF], RFID tracking [START_REF] Kerschbaum | An access control model for mobile physical objects[END_REF][START_REF] Kerschbaum | Privacy-preserving pattern matching for anomaly detection in rfid anti-counterfeiting[END_REF][START_REF] Kerschbaum | Rfid-based supply chain partner authentication and key agreement[END_REF], smart metering [START_REF] Jawurek | Sok: Privacy technologies for smart grids -a survey of options[END_REF], supply chain planning [START_REF] Dreier | Practical privacy-preserving multiparty linear programming based on problem transformation[END_REF][START_REF] Kerschbaum | Secure collaboratiue supply-chain management[END_REF], web applications [START_REF] Fuhry | Encrypting analytical web applications[END_REF] or reputation systems [START_REF] Kerschbaum | A verifiable, centralized, coercion-free reputation system[END_REF].

3 Searchable Encryption

Definitions

We propose to use searchable encryption as an alternative to deterministic and order-preserving encryption in adjustable encryption. Searchable encryption allows the (private) key holder to issue a search token for a query string. Using this search token the ciphertext holder can compare a ciphertext to the query string. The result of this comparison (match / no match) is immediately revealed in plaintext.

We employ the symmetric key variant due to better performance and the lack of need for a public key in our scenario. A searchable encryption in our scenario consists of the following algorithms:

sk ← KeyGen(λ): Generates a secret key sk for a security parameter λ.

c ← Enc(sk, x): Encrypts a plaintext x into a ciphertext c using secret key sk. t ← T rapDoor(sk, x): Generates a trapdoor search token t for plaintext x using secret key sk. -/⊥ ← T est(t, c): Returns if the search token matches and ⊥ if not.

Note that the ability to decrypt is optional in our scenario and hence not implemented, since we can use another encrypted column of the same data for decryption.

Performance Calibration

We compare the execution time of SQL queries on searchable encryption to that of on deterministic encryption or order preserving encryption. These results are used to calibrate our query planning algorithm. This algorithm compares the runtime of a query using searchable encryption with its equivalent using deterministic or order-preserving encryption, respectively. Both executions -on searchable and on deterministic or order-preserving encryption -share some common effort which includes query pre-processing and decryption of the result set on the client and data transfer between the client and the server. We omit this time in the following evaluation, because it does not contribute to the advantage of one execution strategy over the other.

For searchable encryption we must consider the generation of the trapdoor and the runtime of the UDF. Our tests show that the UDF scales very well, so that we have the following linear cost model. Let N denote the number of entries in the searched database column, t UDF scan denote the scan time per database row and t trapdoor generation includes both the actual execution of the cryptographic algorithm and the row-independent execution time for query processing.

t searchable = N t UDF scan + t trapdoor generation

When executing equality or range searches on deterministic or order-preserving encryption, respectively, we use unmodified relational operators that compare the values stored in the database to the search values. In this case the main execution time stems from encrypting these literal values to deterministic or order-preserving ciphertexts. Hence in our linear model t deterministic = N t scan + t encryption the slope t scan is very small. Note that in particular for in-memory databases we find that t scan t UDF scan . In fact, for table sizes up to 100 million entries there is a total runtime of less than 50ms.

Our measurements lead to the following values for t UDF scan , t trapdoor generation , t scan and t encryption which we use for the calibration of our query planning algorithm.

Detecting and Handling Infrequently Used Columns

Searchable encryption in our UDF can handle selection similar to deterministic or order-preserving encryption but at higher security and lower performance. We now aim to identify infrequently used columns, such that we can decide to handle them by searchable encryption keeping the performance impact low, but maximizing the relative security gain.

Problem

Consider an adjustably encrypted database and the following two sequences A and B of queries: Using the standard adjustment algorithm both sequences result in an orderpreserving encryption of column y. Yet, if in sequence B the second query is handled using searchable encryption, then the security would remain at deterministic encryption and the performance impact would be small. Our problem is to identify and handle differently this specific (infrequent) query.

The problem is a typical scheduling problem where an optimizer has to make a decision based on future inputs (queries). The decision problem in case of the first query of sequence A and the second query of sequence B is almost identical: A query requiring a database adjustment appears for the first time. The optimizer has to decide whether to use searchable encryption or to decrypt.

The only sensible choice is to treat first-time appearing queries as infrequent until they reach a certain threshold and then decrypt. We present our algorithm in the next section.

Algorithm

We use a budget mechanism in order to determine infrequently used columns. For each column col we maintain a budget budget [col]. This budget describes the extra amount of time allowed for searchable encryption compared to deterministic or order-preserving encryption. It can be maintained in an arbitrary but fixed unit of time (say milliseconds). For each column we use searchable encryption until the budget is used up (i.e. reaches 0) and subsequently switch to the other encryption schemes.

We fix two parameters α and β for our algorithm. Whenever a query is executed the parameter α is added to the budget. The parameter β defines the upper bound of the budget, i.e. the budget is never increased beyond β. We call this process budget refilling.

When we choose searchable encryption we deduct the additional cost of the query from the budget. Let σ be the cost of searchable encryption for equality and τ be the cost of searchable encryption for ranges as determined in Section 3.2.

We can run our algorithm -in particular budget refilling -for several different sets of columns. A SQL query uses a number of columns, not only the ones in selection. We consider and later evaluate the following options for the budget update strategy, i.e. choosing the column col.

-S 1 : Increase the budget for all columns used as selection parameters.

-S 2 : Increase the budget for all columns occurring in the query in any role (e.g. also in the result list) -S 3 : Increase the budget for all columns of all tables occurring in the query.

-S 4 : Increase the budget for all columns of the database scheme used.

Cost Estimation

Note that the costs σ and τ used in our algorithm depend on the number of rows to which the test function needs to be applied. For simple scans on complete database tables this number is readily available. However, as soon as there are other selection conditions which narrow the result set it is important that they are applied first. Hence the actual number of rows the function acts on has to be estimated. This is a difficult problem and lies at the heart of many query optimizations already for non-encrypted data. In our implementation we use a straight-forward approach and assume that the selection conditions occurring in our queries are independent and reduce the result set by a fixed factor.

Experimental Results

Security Measure

We define security as the encryption state of the database after one test run, i.e. a series of queries chosen according to the distribution described before. Each column that is decrypted to deterministic encryption lowers the security compared to columns encrypted using randomized and searchable encryption. Our security measure is hence simply the number of columns not decrypted to order-preserving or deterministic encryption.

This security measure is independent of the number of queries we have executed. We simply measure the state of the database. Note that without our encryption selection algorithm all 15 columns would be decrypted to deterministic encryption after the first query accessing them, i.e. after each test run. We hypothesize that using our algorithm the database will remain in a more secure state.

We report the percentage of columns not decrypted. The baseline in our set of queries from the TPC-C benchmark is 15 columns that may be decrypted without our encryption scheme selection algorithm. Hence, each not decrypted column is a 6.7% security improvement. We ignore any different sensitivity level of columns, since they are difficult to assess scientifically, but note that any non-decrypted column may already have high economic value.

We devise a simple theoretical test whether a column is likely to be decrypted or not. Given the distribution of the test queries and the strategy used for budget refilling one can calculate the expected value of the change per query execution of the budget for a given data base column col. Let Q i be the query type of query i, p j be the probability of picking a query type j (1 ≤ j ≤ 11), and column col and 0 else. The cost σ(Q i , col) (cf. 4.3) of query i depends on the query type and the column. Then, we have

χ(Q i , col) = χ refill strategy (Q i , col
E(∆budget[col]) = i p Qi (χ(Q i , col)α -σ(Q i , col)) (1)
If the expected value E(∆budget[col]) is negative, then the budget will eventually reach 0. If, however, the expected value is positive then there is a good chance that no decryption of the column col to a weaker security level is ever necessary.

Performance Measure

We measure the wall clock time the database requires for performing the queries on encrypted data. Let t i be time for the i-th query. We use the sum s = i t i of all queries as the measured performance.

In an encrypted "hot" database without our encryption selection algorithm the query would always be performed using deterministic or order-preserving encryption. Our encryption scheme selection algorithm improves security, but infrequent queries may be slower. In order to measure this performance penalty we first measured a baseline. We executed each query type of our set from the TPC-C benchmark 500 times on deterministic encryption. We use the median b j as the baseline performance for this query type (1 ≤ j ≤ 11).

Using the randomly chosen queries in a test run we compute a baseline for the entire test run. Let Q i be the query type of query i (1 ≤ Q i ≤ 11). Then, our baseline B is B = i b Qi . We report the performance penalty of our encryption scheme selection algorithm as s B -1. A performance penalty of 5% means that an encrypted database using our algorithm (for the chosen set of parameters) executes 5% slower than encrypted database without our algorithm. Recall that our algorithm improves security, i.e. we trade performance for security.

Each test run consists of 500 queries (0 < i ≤ 500) chosen according to the geometric distribution described before. In order to have the database reach a "hot" state in our experiments, we disregard the first 100 queries in our performance measurement. Even when using our encryption scheme selection algorithm, several columns need to be decrypted to deterministic encryption. Including this time will skew our measurements, since it is not included in the baseline. We argue that the performance of a "hot" database is critical for practical use rather than the cost of reaching this state, since this can be included in an installation or setup phase. Hence, we focus our measurements on the "hot" phase.

Experimental Setup

We execute all experiments on an SAP HANA database (SP05 release) running on an HP Z820 workstation with 128GB RAM und 16 dual cores (Intel Xeon CPU running at 2.60GHz). There was no network access, connections were performed via the loopback interface. Our performance measurement is solely based on the database execution time and hence independent of network performance. Our security measurement is obviously independent of network performance.

Our client is implemented in Java 1.7 as a JDBC driver and running on the 64-bit JVM. The crypto routines are implemented in C++, compiled with GCC 4.3 and accessed via JNI. The UDFs use the same crypto routines accessible as linked libraries.

We execute series of test runs. Each test run consists of 500 queries chosen according to the geometric distribution described before. A series consists of 20 test runs and we report the median performance penalty and median security improvement as described before of those 20 test runs. Note that the median of an even number of values is the mean of the middle two values. Hence, we sometimes have "half" decrypted columns.

Each series of test runs has fixed parameters for the budget increment α, the budget upper limit β and the budget refilling strategy. The initial value for the budget is chosen to be 1 2 β. We conduct experiments varying each parameter individually. In the first experiment we vary α, in the second β and in the third the strategy. For each experiment we report the security improvement vs. performance penalty trade-off for the different parameter choices. We intend to give the database administrator guidance on configuring this trade-off in our algorithm.

Budget Increment α

We measure the impact of the budget increment α in our algorithm. As mentioned before α is linear in the expected value of the budget of a column and, hence, its probability of decryption. We choose four values for α = 3, 6, 9, 12. We choose the budget upper limit β = 100α. We choose the budget update strategy S 1 , i.e. increase the budget for all columns used as selection parameters. We explain our choice of strategy using the results from the appropriate experiments in Section 5.6. Our random choices and experimental setup are as described before. Our results are depicted in Figure 1.

Discussion We can see in Figure 1 that the performance impact of searchable encryption is high, since the slope is steep. This can be expected from our calibration in Section 3.2. Nevertheless, we also see that for the values of α = 3, 6, 9 the security gain is higher than the performance penalty whereas for α = 12 the performance penalty is higher than the security gain. Particularly, for α = 3 and β = 300 we have performance penalty of 1.5% and one non-decrypted column, i.e. a security gain of 6.7%. Hence, we conclude that for truly infrequent queries searchable encryption is indeed a viable alternative. In our subsequent experiments we use α = 3 in order to address this optimal set of infrequent queries. Note that in our test data, smaller values for α < 3 make little sense, since there is only one non-decrypted column left.

Budget Upper Limit β

We measure the impact of the budget upper limit β in our algorithm. It is linear in the expected time to reach decryption (hot state), but it also counters the probabilistic nature of the query distribution. It has to be high enough in order to allow bursts of infrequent queries in an otherwise "stable" query set. We choose the four values for β = 300, 450, 600, 750. We chose α = 3 from the results in the first experiment and the same budget update strategy S 1 as before. Our random choices and experimental setup are as described before. Our results are depicted in Figure 1.

Discussion We can see in Figure 1 again a high performance impact of searchable encryption. Nevertheless, our choice of budget increment α = 3 leads to higher security gains than performance penalties for β = 300, 450, 600. We conclude that α = 3 is indeed addressing a promising set of infrequent queries. As expected the higher the budget upper limit β, the less columns are decrypted and the better the security, but the worse performance. Note that due to our budget update strategy S 1 of refilling only selection columns very few column budgets get increased and the budget limit (and initial budget) is more critical. For β = 300, we have the best security gain to performance penalty ratio. Hence, we use α = 3 and β = 300 in our subsequent experiment for the budget update strategy.

Budget Update Strategy

We measure the impact of the budget update strategy S 1 to S 4 . We expect less columns to be decrypted from S 1 to S 4 , since budget increments occur more frequently. This implies more security gain and less performance penalty. We chose α = 3 and β = 300 from the results in the first two experiments. Our random choices and experimental setup are as described before. Our results are depicted in Figure 1.

Discussion We can see in Figure 1 somewhat surprising results. For our choices of α = 3 and β = 300 the security is not impacted by the budget update strategy. All four strategies on average do not decrypt one column. Still, we can see the expected decreased performance penalty.

Different strategies may impact different columns and hence we believe that there may be a qualitative difference between the strategies. Still, even if the security differences are just too small to be measured, the strategy S 1 is clearly superior. Hence, we recommend and used in all our other experiments strategy S 1 of refilling only selection columns.

  Sequence A: SELECT x FROM T WHERE y > 10 SELECT x FROM T WHERE y > 10 SELECT x FROM T WHERE y > 10 SELECT x FROM T WHERE y > 10 SELECT x FROM T WHERE y > 10 Sequence B: SELECT x FROM T WHERE y = 10 SELECT x FROM T WHERE y > 10 SELECT x FROM T WHERE y = 10 SELECT x FROM T WHERE y = 10 SELECT x FROM T WHERE y = 10

Fig. 1 .

 1 Fig. 1. (left) Security vs. Performance for α = 3, 6, 9, 12, β = 100α and strategy S1. (middle) Security vs. Performance for α = 3, β = 300, 450, 600, 750 and strategy S1. (right) Security vs. Performance for α = 3, β = 300 and all strategies.

Table 1 .

 1 Constants used for calibration

	t UDF scan	4.5 µs
	t trapdoor generation	65 ms
	t scan	∼ 0 µs (< 1 ns)
	t encryption	20 ms

  ) be 1 if query type Q i leads to a refill for

													10.0%
		12.0%					α = 12	20.0% 18.0%					8.0%
	Performance Impact	4.0% 6.0% 8.0% 10.0%			α = 9		Performance Impact	4.0% 6.0% 8.0% 10.0% 12.0% 14.0% 16.0%		β = 450 β = 600 β = 750	Performance Impact	2.0% 4.0% 6.0%			S2 S3 S4
		2.0%			α = 3	α = 6		2.0% 0.0% 0.0%	5.0%	β = 300 10.0%	15.0%	20.0%	0.0% 0.0%	2.0%	4.0%	6.0%	S1	8.0%	10.0%
		0.0%								Security Gain					Security Gain
		0.0%	2.0%	4.0%	6.0%	8.0%	10.0% 12.0%						Refill Strategies
				Security Gain							S1: Only Selection Columns S3: All Columns of All Used Tables	S2: All Used Columns S4: All Columns Of the DB Scheme


Thang Bui

Scott D Stoller

Shikhar Sharma

Fast Distributed Evaluation of Stateful Attribute-Based Access Control Policies

Separation of access control logic from other components of applications facilitates uniform enforcement of policies across applications in enterprise systems. This approach is popular in attribute-based access control (ABAC) systems and is embodied in the XACML standard. For this approach to be practical in an enterprise system, the access control decision engine must be scalable, able to quickly respond to access control requests from many concurrently running applications. This is especially challenging for stateful (also called history-based) access control policies, in which access control requests may trigger state updates. This paper presents an policy evaluation algorithm for stateful ABAC policies that achieves high throughput by distributed processing, using a specialized multi-version concurrency control scheme to deal with possibly conicting concurrent updates. The algorithm is especially designed to achieve low latency, by minimizing the number of messages on the critical path of each access control decision.

Introduction

Separation of access control logic from other components of applications facilitates uniform enforcement of policies across applications in enterprise systems. This approach is adopted in the ISO standard for access control in open systems [START_REF]ISO/IEC: Information technology open systems interconnection security frameworks for open systems: Access control framework. ISO/IEC Standard[END_REF] and the XACML standard 1 . Servers that run the access control policy eval- uation algorithm and provide access control decisions to applications are called policy decision points (PDPs) in XACML terminology. In this paper, we refer to them simply as servers, since we do not discuss other kinds of server.

For this approach to be practical in an enterprise system, the policy evaluation algorithm must be scalable, able to quickly respond to access control requests from many concurrently running applications. To scale beyond the capacity of a single server, distributed policy evaluation algorithms are needed, to coordinate concurrent processing of requests on multiple servers. This is relatively straightforward if the policy and the information it references are static. This material is based on work supported in part by NSF Grants CNS-1421893, and CCF-1414078, ONR Grant N00014-15-1-2208, AFOSR Grant FA9550-14-1-0261, and DARPA Contract FA8650-15-C-7561. Any opinions, ndings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reect the views of these agencies. 1 http://www.oasis-open.org/committees/xacml/ However, this is challenging for stateful (also called state-modifying, dynamic, or history-based) access control policies, in which access control requests may trigger state updates, i.e., updates to information referenced by the policy. The classical examples of stateful access control policies are dynamic separation-of-duty (DSOD) policies, such as the Chinese wall policy [START_REF] Brewer | The chinese wall security policy[END_REF] and DSOD in role-based access control (RBAC) [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF]. Another classic category of stateful access control policies are usage control policies [START_REF] Park | The ucon abc usage control model[END_REF], such as policies that limit the number of times a user can view a video or the number of videos that a user with a particular type of subscription can view each month. The research literature contains numerous additional examples of stateful access control policies, policy models, and policy evaluation algorithms [START_REF] Edjlali | History-based access control for mobile code[END_REF][START_REF] Gama | A scalable history-based policy engine[END_REF][START_REF] Chadwick | Coordinated decision making in distributed applications[END_REF][START_REF] Becker | Specication and analysis of dynamic authorisation policies[END_REF][START_REF] Becker | A logic for state-modifying authorization policies[END_REF][START_REF] Lobo | Renement of history-based policies[END_REF][START_REF] Gay | Service automata[END_REF][START_REF] Nguyen | A provenance-based access control model for dynamic separation of duties[END_REF][START_REF] Kelbert | A fully decentralized data usage control enforcement infrastructure[END_REF][START_REF] Decat | Scalable and secure concurrent evaluation of history-based access control policies[END_REF][START_REF] Weber | Access control for weakly consistent replicated information systems[END_REF][START_REF] Martinelli | Enforcement of U-XACML history-based usage control policy[END_REF]. In the context of Attribute-Based Access Control (ABAC), the updated state is typically attribute data.

The main challenge in distributed policy evaluation algorithms for stateful policies is ensuring serializability, as in concurrent transaction processing in databases [START_REF] Silberschatz | Database System Concepts[END_REF]. Processing of each access control request, including its reads of attribute data and its updates to attribute data, should be serializable with respect to processing of other requests. Since concurrent requests may read or write the same attribute data, a concurrency control mechanism is needed to ensure this.

To illustrate the importance of serializability in this context, consider a typical Chinese wall policy in which companies A and B are in the same conict of interest (COI) class, so user who has accessed documents of one them cannot access documents of the other. When a server allows a request for access to documents of either company, it updates a user attribute to reect this. Suppose a devious user concurrently submits an access request for a document of company A to one server, and an access request for a document of company B to another server. In a non-serializable execution in which both requests are evaluated in the initial state (where the user has not accessed any documents), both requests could be permitted, violating the intended policy. In a serializable execution, the result must be equivalent to a serial execution, where one of the requests sees the eect of the update performed by the other request, causing the second request to be denied, as it should be.

A straightforward approach to this problem is to use a distributed replicated database that supports serializability for multi-row transactions, and to evaluate each request in a transaction. However, this requirement eliminates well-known scalable NoSQL databases, such as Bigtable [START_REF] Chang | Bigtable: A distributed storage system for structured data[END_REF], Cassandra 2 , and MongoDB 3 , which achieve scalability in part by supporting only single-row transactions.

Master-slave replication in SQL databases, such as MySQL 4 , allows multi-row transactions, but has limited scalability, because all read-write transactions must be submitted to a single master server, and provides inadequate consistency guarantees, because slaves can return slightly out-of-date data. Multi-phase commit protocols, such as in Oracle, IBM DB2, and Microsoft SQL Sever, allow multirow tranasctions and ensure serializability, but are less scalable. Decat et al. present a distributed policy evaluation algorithm for stateful ABAC policies [START_REF] Decat | Scalable and secure concurrent evaluation of history-based access control policies[END_REF] that is more scalable than multi-phase commit protocols, by exploiting the fact that evaluation of an ABAC request involves at most two objects (i.e., two rows), typically called the subject and the resource. Their algorithm uses a specialized scheme for optimistic concurrency control [START_REF] Silberschatz | Database System Concepts[END_REF]Section 15.5]. Their experimental results demonstrate that their algorithm scales well in terms of throughput. However, their algorithm incurs a signicant increase in latency, since processing of each request involves a chain of 6 messages (including the messages to and from the client). This paper presents a new distributed policy evaluation algorithm for stateful ABAC policies. The algorithm is called FACADE (Fast Access Control Algorithm with Distributed Evaluation). It uses a specialized scheme for multiversion timestamp ordering concurrency control [START_REF] Silberschatz | Database System Concepts[END_REF]Section 15.6] that simultaneously achieves low latency by minimizing the length of the message chain on the critical path (i.e., the message chain ending with the result sent to the client). Low latency is of obvious importance for interactive applications: developers struggle to keep the latency of the application's core functionality within limits acceptable to users, especially for multi-tier enterprise applications, where many requests involve processing by multiple servers (web servers, application servers, database servers, etc.), and latency contributions from non-core functionality such as access control are acceptable only if they are low. Low latency is also important for batch applications. These applications often process large amounts of data, hence requiring many access control checks. If the latency of these checks is not kept very low, the repeated delays in the core application processing will cause poor system utilization. Reducing the number of messages per request has the additional benet of reducing the required network capacity. FACADE processes read-only requests dierently than read-write requests, in contrast to Decat et al.'s algorithm, which processes all requests the same way. This, together with use of multiversion timestamp ordering concurrency control, enables FACADE to use especially short message chains for read-only requests. Multiversion timestamp ordering concurrency control has the desirable property that read-only requests never abort.

Algorithm

System Architecture. We adopt the system architecture in [START_REF] Decat | Scalable and secure concurrent evaluation of history-based access control policies[END_REF]. There are two types of hosts: clients and servers. Each client runs applications and a small client-side stub that interacts with the access control servers. Each server runs three kinds of processes: a coordinator, which receives requests from clients and is responsible for concurrency control, a database, which stores a copy of the attribute data used by the policy, and one or more workers, which evaluate requests based on the access control policy and send the result to the coordinator and/or client.

Each worker reads attribute data from the co-located replica of the database.

Workers never update the database. The set of objects is partitioned across the set of coordinators. Thus, for each object x, there is a unique coordinator, denoted coord(x), responsible for x; we also say that coord(x) manages x. Only coord(x) submits updates of x to the master database (this is done using a standard database connector, such as ODBC or JDBC, regardless of whether the master database is on the same server or a dierent server). Coordinators never read the database.

Multiversion timestamp ordering concurrency control. Before presenting our algorithm, we briey review multiversion timestamp ordering concurrency control [START_REF] Silberschatz | Database System Concepts[END_REF]Section 15.6], with a change in terminology: we refer to requests in place of transactions. A sequence of versions is associated with each data item. In FACADE, we treat each attribute of each object as a data item. Each version v has a value v.value, a write timestamp v.wts (the timestamp of the request that created v), and a read timestamp v.rts (the largest timestamp of any request that successfully read v). Each request req is assigned a timestamp req.ts. Let v denote the most recent version of x.attr whose timestamp is at most req.ts. A read of x.attr by req returns v.value. A write by req requires a conict check: if req.ts < v.rts, then req aborts and restarts; if req.ts == v.wts, then the value of v is overwritten; otherwise (if req.ts > v.rts), a new version of x.attr is created.

Note that reads never cause aborts, and read-only transactions always commit.

To support conict checking, each coordinator maintains a data structure containing the read timestamp and write timestamp of every version of an attribute created during the coordinator's current session (i.e., since the coordinator process started running). This data structure does not store the value of each version, since it is not needed for conict checking. Entries for old versions can be garbage-collected; details are straightforward and omitted. Although this data structure has some information overlap with cachedUpdates, we keep the two data structures separate for clarity, because they serve dierent purposes. This data structure is accessed using two functions. getVersion(x,attr,ts) returns the most recent version of x.attr written at or before ts; if no such version exists, it returns a special version v with v.wts=0 and v.rts=0, representing the last version written in the previous session (any timestamp guaranteed to precede all timestamps generated in the current session is safe; 0 is a convenient choice). addVersion(x,attr,ts) creates and stores a version of x.attr with write timestamp and read timestamp equal to ts. Database. To avoid use of a heavyweight multi-phase commit protocol in the database, we assume a database that supports master-slave (also called primarysecondary) replication, in which updates are committed at one replica, called the master or primary, and the updates are visible at the other replicas, called slaves or secondaries, within a known time limit, called the database latency. The cache is accessed using the function cachedUpdates(x), which returns the set of cached updates to x. FACADE needs to store multiple versions of objects in the database. This can easily be done in any database, by including a version column in the database schema. Our implementation using MySQL works this way.

Request objects. We model requests as objects with elds subject, resource, ts (timestamp), cachedUpdates[i] (i=1 and i=2 for piggybacked cached updates to subject and resource, respectively), worker (worker selected to evaluate this request), and evalResult (result of evaluating the request, described below).

Policy language. FACADE is independent of the details of the policy language.

Any ABAC policy language can be used, provided it can express updates. For example, XACML can be used, with updates expressed as obligations, as in [START_REF] Park | The ucon abc usage control model[END_REF][START_REF] Decat | Scalable and secure concurrent evaluation of history-based access control policies[END_REF]. Details of the policy language are abstracted behind an interface containing a single function evaluateRequest(policy,request) that returns an EvalResult object with these elds: decision (permit or deny), readAttr[i] (i=1 and i=2 for the set of attributes of the subject and resource, respectively, read during evaluation of the request), updatedObj (the index of the updated object, if any, otherwise -1), rdonlyObj (if updatedObj > 0, this is the index of the other object, otherwise -1), and updates (set of attribute-value pairs, specifying updates to updatedObj). The index values are interpreted as: 1=subject, 2=resource. eval-uateRequest evaluates the request using attribute values current as of req.ts, reading values from req.cachedUpdates when they exist, otherwise reading values from the database using queries with timestamp req.ts.

Bounds on attribute accesses. Our algorithm can exploit bounds on attribute read and written by requests, when available, to improve performance. In particular, for a request r, for each object x that might be accessed by r (namely, the subject and resource), the client stub provides (1) a lower bound on the set of attributes of x that will denitely be read by r, (2) an upper bound on the set of attributes of x that might be read by r, and (3) an upper bound on the set of attributes of x that might be updated by the request. It is always safe to use the trivial bounds, i.e., the empty set for (1) and the set of all attributes for (2) and

(3). When tighter bounds are available for (1), the algorithm can sometimes use them to conclude that a request denitely conicts with an in-progress request r, without waiting to learn the exact set of attributes read by r. When tighter bounds are available for ( 2) and ( 3), the algorithm can sometimes use them to conclude that two requests involving the same object access disjoint sets of attributes and hence cannot conict, without waiting to learn the exact sets of attributes they accessed. Note that these situations arise only in the typically small fraction of cases that two concurrent requests access the same object, and at least one of the requests is not known to be read-only.

Tighter bounds can often be obtained from basic knowledge about the request and the policy. The code or rules dening these bounds could be written manually for small systems or generated by a straightforward static analysis of the access control policy, based on the types of object and type of action in each rule and the names of the attributes read and written by each rule. For example, consider an access control system for an online video service, in which requests to play a video are subject to usage control to limit the number of views, and all other requests (browsing the video catalog, paying for a video, account maintenance, etc.) are not. In this system, a client can identify a request as read-only if the resource type is not video or the action is not play. These bounds are provided by dening (possibly using trivial bounds) the following policy-specic functions, where x is req.subject or req.resource. defReadAttr(x, req) is a set of attributes of x denitely read by req. mightReadAttr(x, req) is an upper bound on the set of attributes of x that might be read by req (including denitely read attributes). (with piggybacked cached committed updates) to coordR, the coordinator for the resource of the request, which does the same and then forwards to the request to a worker on the same server. The worker evaluates the request and then sends the result to coordS. coordS checks for conicts involving the subject; specically, it checks whether any attribute of the subject read by the request was updated after it forwarded the request to coordR (any such update was not piggybacked on the request and hence might not have been used in its evaluation). If there is no conict, it forwards the result to coordR, which performs a similar conict check and, if there is no conict, commits the updates (if any) to the resource, and then sends the outcome of the conict check to coordS. coordS commits the updates to the subject and then sends the decision to the client. If either coordinator detects a conict, the request is restarted. After coordS sends the result to coordR and before it receives the outcome of coordR's conict check, it treats the request's updates to the subject specially, as tentative updates; for details, see [START_REF] Decat | Scalable and secure concurrent evaluation of history-based access control policies[END_REF].

Overview of FACADE for read-only requests. The client sends the request to coord1, the coordinator for one of the objects accessed by the request (either one is ne). coord1 updates data structures used for conict detection and then forwards the request (with piggybacked cached committed updates) to coord2, the coordinator for the other object accessed by the request. coord2 updates its data structures and forwards the request to the worker. The worker evaluates the request, sends the decision to the client, and sends the sets of read attributes of the subject and resource to their respective coordinators, which update the read timestamps of the read versions. It is safe for the worker to send the decision directly to the client, because read-only requests never abort in FACADE.

Note that this message pattern is used for any request that turns out to be read-only, regardless of whether this is known in advance, i.e., regardless of whether mightWriteAttr is empty for either object involved in the request.

Overview of FACADE for read-write requests. When the client sends the request to the coordinator for an object not updated by the request, we say that the client correctly predicts a read-only object for the request. This is guaranteed if mightWriteAttr returns an empty set for at least one object involved in the request, and has 50% probability otherwise. It is preferable for the client to send the request to such a coordinator, denoted coordR, because the worker sends the evaluation result to the coordinator for the updated object, denoted coordW, and that result message is local if the worker is co-located with coordW, which happens if coordR receives the request from the client and forwards it to coordW. If mightWriteAttr returns a non-empty set for both objects, then the client arbitrarily selects a coordinator to which to send the request. If that turns out to be coordW, we say that the client incorrectly predicts a read-only object for the request. The only consequence is that the worker's result message is a network message instead of a local message.

When the client correctly predicts a read-only object for the request, the client sends the request to the coordinator for that object, denoted coordR.

coordR updates data structures used for conict detection and then forwards the request (with piggybacked cached committed updates) to coordW. The worker evaluates the request and sends the result, including the decision and the sets of read and written attributes of the subject and resource, to coordW. coordW checks for conicts; specically, it checks whether any attribute updated by this request was read by a request with a later timestamp. Even if there is no conict yet, a conict could arise later, involving a request with a later timestamp that has already been forwarded and might read the attribute. A set of such requests, called pending might read requests, is associated with each version of an attribute. The worker waits until there are no such pending might read requests and then checks for conicts again. If there is no conict, it commits the updates, sends the decision to the client, and sends the set of read attributes of the other object to the other coordinator.

When the client incorrectly predicts a read-only object for the request, the message pattern is the same, except that coordW receives the request rst and then forwards it to coordR, and the evaluation result message from the worker to coordW is a network message instead of a local message.

Handling of requests known to be read-only. A request req is known to be readonly i mightWriteAttr(req.subject, req) and mightWriteAttr(req.resource, req) are empty. Handling of requests known to be read-only is described separately from handling of other requests, for ease of understanding, although the two are similar in places, and the code for them is integrated in our implementation.

Handling of requests known to be read-only follows the pseudocode in Figure 2.

The pseudocode syntax is generally Python-like, except we denote tuples using angle brackets instead of parentheses. Implicitly, coarse-grain locking is used to ensure that coordinators process each incoming message atomically, i.e., without interruption by processing of other messages (as an optimization, ner-grained locking could be used).

Handling of read-write requests. Handling of other requests follows the pseudocode in Figures 3 and4.

Liveness. The algorithm presented in the pseudocode is deadlock-free: the inequality on timestamps in the await statement in Figure 4 ensures that two requests cannot be stuck waiting for each other. However, it can starve some read-write requests. For example, a long stream of reads to an attribute x.attr can cause the condition in the await statement in Figure 4 to remain true for a long time, causing a pending update to x.attr to starve. The underlying reason is that FACADE gives precedence to reads over writes, in the sense that reads never abort, and writes can be aborted due to conicting reads.

To counter-balance this, and thereby help prevent starvation of writes, we modify the algorithm to delay reads in two cases (these modications are not reected in the pseudocode). ( 1) After a coordinator c receives "request", req, 1 from a client, if req might update req.obj [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF], c delays processing of incoming requests that potentially conict with req (temporarily storing them in a queue) until c determines the outcome (commit or restart) of the current execution of req, at which time c processes the delayed requests normally. An incoming request req2 potentially conicts with req if req2 might read an attribute that req might update. (2) After a coordinator c receives an evaluation result message "result", req that includes updates to an object x managed by c, while c is waiting for the await condition to become true, c delays processing of incoming requests that potentially conict with those updates until c determines the outcome (commit or restart) for req, at which time c processes the delayed requests normally An incoming request req2 potentially conicts with the updates if req2 might read one of the updated attributes. Note that these two kinds of delays 1. client: # for read-only requests, the coordinator order (subject rst or resource rst) does # not aect correctness or performance. arbitrarily do subject rst. req.obj [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF], req.obj [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF] = req.subject. req.resource send "request", req, 1 to coord(req.obj [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF])

2. coordinator: on receiving "request", req, 1 : x = req.obj [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF] req.ts = now() # now() returns the current date-time.

for attr in defReadAttr(x, req): getVersion(x, attr, req.ts).rts = req.ts for attr in mightReadAttr(x, req) -defReadAttr(x, req): getVersion(x, attr, req.ts).pendingMightReads.add( req.id, req.ts ) req.cachedUpdates [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF] = cachedUpdates(x) send "request", req, 2 to coord(req.obj [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF]) 3. coordinator: on receiving "request", req, 2 : x = req.obj [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF] for attr in defReadAttr(x, req): getVersion(x, attr, req.ts).rts = req.ts for attr in mightReadAttr(x, req) -defReadAttr(x, req): getVersion(x, attr, req.ts).pendingMightReads.add( req.id, req.ts ) select worker w to evaluate this request req.worker = w req.cachedUpdates [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF] = cachedUpdates(x) send req to w 4. worker: on receiving req: req.evalResult = evaluateRequest(policy, req) send "decision", req.id, evalResult.decision to req.client send "readAttr", req, 1 to coord(req.subject) send "readAttr", req, 2 to coord(req.resource) req.obj [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF], req.obj [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF] = 1, 2 send "request", req, 1 to coord(req.obj [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF]) 2. coordinator: on receiving "request", req, 1 : x = req.obj [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF] req.ts = now() # now() returns the current date-time. for attr in mightReadAttr(x, req) v = getVersion(x,attr,req.ts) v.pendingMightReads.add( req.id, req.ts ) req.cachedUpdates [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF] = cachedUpdates(x) send "request", req, 2 to coord(req.obj [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF]) 3. coordinator: on receiving "request", req, 2 : x = req.obj [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF] for attr in mightReadAttr(x,req) v = getVersion(x,attr,req.ts) v.pendingMightReads.add( req.id, req.ts ) select worker w to evaluate this request req.worker = w req.cachedUpdates [START_REF]International Committee for Information Technology Standards (INCITS): Role-based access control[END_REF] = cachedUpdates(x) send req to w 4. worker: on receiving req: req.evalResult = evaluateRequest(policy, req) if req.updatedObj == -1:

# req is read-only. send "decision", req.id, req.evalResult.decision to req.client send "readAttr", req, 1 to coord(req.subject) send "readAttr", req, 2 to coord(req.resource) else:

# req updated an object. send "result", req to coord(req.obj[req.updatedObj]) Fig. 3. Handling of requests not known to be read-only, part 1.

and read-write requests. Their algorithm does not incorporate any mechanism to compensate for this. This is probably acceptable for workloads in which writes are infrequent relative to reads.

Optimizations. Our implementation incorporates the following optimizations that are not reected in the pseudocode. (1) If the same coordinator is responsible for both objects involved in a request, then the coordinator performs the processing for both objects together, without sending itself a message in between. remove entries for req from all pendingMightReads sets # tell the other coordinator to restart processing of this request roCoord = coord(req.subject) if req.evalResult.rdonlyObj==1 else coord(req.resource) send "restart", req to roCoord Fig. 4. Handling of requests not known to be read-only, part 2.

(2) The await statement in Figure 4 waits for all relevant pending reads to complete before checking whether any of them conict with the pending update. As an optimization, when each relevant pending read completes, the coordinator immediately checks whether it conicts with the pending update, and if so, immediately restarts the request performing the update. (3) To reduce the number of database queries, workers piggyback data read from the database on messages sent to coordinators, and coordinators add it to the data structure that caches recent committed updates. Note that caching of attribute data is done only by coordinators, not workers, because a coordinator performs all updates to objects it manages and hence knows when cached data is stale (relative to a specied request timestamp).

Fault-tolerance. Like Decat et al. in [START_REF] Decat | Scalable and secure concurrent evaluation of history-based access control policies[END_REF], we focus in this paper on scalability and leave detailed consideration of fault-tolerance for future work. We briey sketch how to extend our algorithm to tolerate crash failures. A fault-monitoring service is needed to detect crashes and restart crashed processes. Requests that were inprogress at the time of a crash might be dropped. If a client does not receive a decision for a request in a reasonable amount of time, the client can re-submit the request with the same identier. If the request is read-only, the worker simply re-evaluates it in the current state. If the request performs updates, the worker checks whether the request already committed, and if so, re-sends the original decision, otherwise re-evaluates the request in the current state. To support this, when a coordinator commits the attribute updates for a request, it also inserts a record containing the request id and decision in a request log table. The worker looks up the request id in this table before evaluating a request.

Evaluation

Implementation. We implemented FACADE in DistAlgo [START_REF] Liu | From clarity to eciency for distributed algorithms[END_REF][START_REF] Liu | From clarity to eciency for distributed algorithms[END_REF], an extension of Python with high-level communication and synchronization constructs. The DistAlgo compiler 5 translates DistAlgo into Python for execution. We also imple- Performance with dierent write probabilities. To evaluate the eect of pWrite on performance, we also ran the latency experiments and throughput experiments (described in the Latency and Throughput paragraphs above, respectively) with pWrite=0.0 (i.e., all requests are read-only) and pWrite=0.2. We consider pWrite=0.1 to be a realistic value and pWrite=0.2 to be on the high side of the realistic range. pWrite=0.0 is a natural boundary value to consider;

it is also the best case for both algorithm's performance. For the latency experiments, the results with pWrite=0.0 and pWrite=0.2 are almost the same as those described above for pWrite=0. Performance with more conicts. To evaluate the eect of a higher conict rate on performance, we also ran the throughput experiments with an unrealistically small number of objects; decreasing nObj is the simplest way to increase the conict rate. Specically, we reduced nObj from 1000 (a more realistic value) to 200 (an unrealistically small value) for these experiments. Other workload parameters, including nClient and nWorker, are the same as described above for the throughput experiments. For FACADE with wrongWrite=0 and wrongAttr=0, the number of restarts due to conicts increased from 1 to 16, throughput de- [START_REF] Decat | Scalable and secure concurrent evaluation of history-based access control policies[END_REF] is the most closely related and is discussed in previous sections.

creased
Chadwick describes a distributed architecture for a XACML-based stateful policy framework, consisting of multiple policy decision points (PDPs) interacting with a centralized database containing the mutable state [START_REF] Chadwick | Coordinated decision making in distributed applications[END_REF]. Each PDP locks all relevant rows in the database before evaluating a request. The design has limited scalability, due to the centralized database and locking.

Alzahrani et al. describe a similar distributed architecture [START_REF] Alzahrani | Decentralized XACML overlay network[END_REF], without committing to a specic approach to storage of the state. They briey mention a few alternatives, e.g., in a centralized database, or replicated at or partitioned among the PDPs, but do not discuss any of them in detail.

Dhankhar et al. consider evaluation of stateful distributed XACML policies.

Dierent PDPs have dierent policies, and the policies can refer to each other [START_REF] Dhankhar | Evaluating distributed XACML policies[END_REF]. Concurrency control is provided by a centralized lock manager. Each PDP locks all relevant attributes before evaluating a request. The centralized lock manager limits scalability of their design.

Kelbert and Pretschner describe a fault-tolerant decentralized infrastructure for enforcement of usage control policies [START_REF] Kelbert | A fully decentralized data usage control enforcement infrastructure[END_REF]. They rely on the database, Cassandra 2 , for concurrency control. As mentioned in Section 1, Cassandra pro- vides serializability only for single-row transactions, so their system does not support serializable evaluation of requests involving attributes of two objects.

Weber et al. present a framework for stateful access control policies in distributed systems based on weakly consistent replication of the state, as provided by eventually consistent data stores [START_REF] Weber | Access control for weakly consistent replicated information systems[END_REF]. In contrast, our design is based on the traditional notion of strong consistency. When weak consistency is acceptable, it potentially allows more fault-tolerance and scalability. They do not present a completed implementation or any performance results.

  This assumption is satised by the replication schemes in popular databases, such as primary-secondary replication in MongoDB and master-slave replication in MySQL. Loose bounds on the database latency are sucient: the size of the database latency has little eect on FACADE's performance, mainly aecting how long updates are cached by coordinators. Since distributed concurrency control is provided by the coordinators, it does not matter what, if any, centralized concurrency control scheme is used by the master replica of the database. FACADE masks the database latency in the same way as Decat et al.'s algorithm. Each coordinator maintains a LRU cache of recent committed updates to objects it manages, and it piggybacks on each request (when forwarding the request to a coordinator or worker) the cached updates for objects it manages that are involved in the request. Each cached update species a write timestamp as well as an attribute and its new value. A cached update is never evicted before the current time exceeds the update's write timestamp plus the database latency.

Figure 1 .

 1 Figure 1. The sequence diagrams show the common case in which the request does not restart due to a conict and the two objects accessed by the request are managed by coordinators on dierent servers. Accesses to the database are not shown; they are the same for Decat et al.'s algorithm and FACADE.

Fig. 5 .

 5 Fig. 5. Average latency per request (left) and average number of network messages per request (right) as a function of pSameCoord.

Fig. 6 .

 6 Fig. 6. Average throughput as a function of nClient for Decat et al.'s algorithm (left) and FACADE (right).

  This helps FACADE use a shorter critical path than Decat et al.'s algorithm for read-only requests. FACADE also uses shorter message chains than Decat et al.'s algorithm for read-write requests. This is achieved partly by use of multiversion concurrency control and partly by specialization to requests that update at most one object.

	We ran experiments, described in Section 3, to compare the performance of
	FACADE and Decat et al.'s algorithm. Our experiments show that FACADE
	has signicantly lower average latency, uses signicantly fewer network messages
	per request, and has slightly higher throughput than Decat et al.'s algorithm in
	many cases.
	This specialization is motivated by the observation that in every stateful policy
	given as an example in every paper cited above, each request updates the state
	of at most one object. FACADE can be extended to handle requests that update
	two objects, but that extension is not described in this paper.
	FACADE is more exible than Decat et al.'s algorithm, in that FACADE allows an object to be a subject and a resource, while Decat et al.'s algorithm
	requires the sets of subjects and resources to be disjoint [8, Section 3.4]

  "decision", req.id, req.decision to req.client # send read attributes to coordinator for read-only object roCoord = coord(req.subject) if req.evalResult.rdonlyObj==1 else coord(req.resource) send "readAttr", req, req.evalResult.rdonlyObj to roCoord

	5. coordinator: on receiving "result", req :
	# req updates an object that this coordinator is responsible for.
	x = req.obj[req.updatedObj]
	conict = checkForConicts()
	if not conict:
	# wait for relevant pending reads to complete. await(expr) blocks until expr is true.
	await (∀ attr,val ∈ req.updates. ∀ id,ts ∈ getVersion(x, attr, req.ts).pendingMightReads.
	id == req.id or ts < req.ts)
	conict = checkForConicts()
	if not conict:
	commit req.evalResult.updates to the database with write timestamp req.ts
	# cache the updates, and store the new versions for conict checking
	for (attr, val) in req.evalResult.updates:
	cachedUpdates(x).add( attr, val, req.ts )
	addVersion(x,attr,req.ts)
	# update read timestamps
	for attr in mightReadAttr(x,req)
	v = getVersion(x,attr,req.ts)
	v.pendingMightReads.remove( req.id, req.ts )
	if attr in req.readAttr[req.updatedObj]:
	v.rts = req.ts
	# send decision to client
	else:
	restart(req)
	else:
	restart(req)
	coordinator: on receiving "restart", req :
	remove entries for req from all pendingMightReads sets
	restart processing of req, as if it were newly received from client
	def checkForConicts():
	for (attr, val) in req.updates:
	# note: if x.attr has not been read or written in this session, then
	# v is the special version with v.rts=0 and v.wts=0.
	v = getVersion(x, attr, req.ts)
	if v.rts > req.ts:
	return true
	return false
	def restart(req):

send

  attributes and written objects is possible. More generally, we see that incorrect prediction of accessed attributes and written objects have negligible eect on these results. We also see that the average latency of FACADE is almost independent of pSameCoord; this is because local processing time accounts for much of the latency, and the average number of network messages per request changes less for FACADE than Decat et al.'s algorithm.

	nClient: number of clients. This is also the maximum number of concurrent
	requests, since each client sends a request and waits for the response before
	sending the next request.
	nWorker: number of workers per coordinator.
	nObj: number of objects in database. We use objects with 10 attributes, two
	of which are mutable (i.e., might be updated by access control policy rules).
	nRequest: total number of requests (split evenly among the clients)
	pWrite: probability that a request is read-write; other requests are read-only.
	pSameCoord: probability that the two objects involved in a request have the
	same coordinator. As discussed below, we emulate experiments with nCoord
	coordinators using our platform with 2 coordinators by setting pSameCo-
	ord=1/nCoord.
	wrongWrite: ag controlling accuracy of client's prediction of written ob-
	jects. wrongWrite=0 means completely accurate. wrongWrite=1 means the
	prediction always includes an object not written by the request.
	wrongAttr: ag controlling accuracy of client's prediction of accessed at-
	tributes. wrongAttr=0 means completely accurate. wrongAttr=1 means the
	predictions of read and written attributes contain all attributes and all mu-
	table attributes, respectively.
	Latency. To evaluate how the performance, primarily latency, of FACADE would
	depend on the number of coordinators in a system, we ran experiments analo-
	gous to the latency experiments in [8, Section 3.4, Figure 9]. We use nClient=1,
	like they do, to measure the intrinsic latency of the algorithm, in the absence of
	contention. In their experiment, latency is measured instead as a function of the
	actual number of coordinators. However, the number of coordinators aects the
	latency only indirectly, by aecting the probability that the same coordinator is
	responsible for the two objects involved in the request. For clarity, we measure
	the latency directly as a function of this probability, by making pSameCoord a
	workload parameter, as described above. This also allows us to use a smaller plat-
	form for the experiments. Values of the other xed workload parameters in these
	experiments are nWorker=1, nObj=1000, nRequest=5000 and pWrite=0.1. For
	FACADE, we repeat the experiments for each of the four possible combinations
	of values of wrongWrite and wrongAttr. Figure 5 shows average latency per re-
	quest and average number of network messages sent per request for FACADE plementations of both algorithms are publicly available 6 . The experimental plat-and Decat et al.'s algorithm. When pSameCoord is 0.5 or less, corresponding to form consists of three desktop PCs with Intel Core 2 Quad processors (two at deployments with 2 or more coordinators, FACADE has lower latency and sends
	2.83GHz, one at 2.66 GHz), with Gigabit Ethernet NICs connected to a Gigabit fewer network messages than Decat et al.'s algorithm. FACADE's lower latency Ethernet switch, and running Windows 10 64-bit, Python 3.6, DistAlgo 1.0.9, stems from using fewer network messages and fewer database queries (due to
	and MySQL 5.7.17. optimization (3)). Deployments in large systems would probably use around 10
	Workload. The workload consists of pseudorandom sequences of requests. The same seeds, hence the same workload, are used for corresponding experiments coordinators, as in Decat et al.'s experiments. This corresponds to pSameCo-ord=0.1, for which the average latency of FACADE is less than half the average latency of Decat et al.'s algorithm (37.7 milliseconds compared to 91.1 millisec-with the two algorithms. Conguration parameters for each experiment include: onds), and the average network messages per request is 3.8 for FACADE vs. 5.6
	5 http://sourceforge.net/projects/distalgo/files/ for Decat et al.'s algorithm. This is true regardless of whether accurate predic-6 http://www.cs.stonybrook.edu/~stoller/software/ tion of accessed

mented Decat et al.'s algorithm in DistAlgo, to allow a performance comparison of the algorithms, not inuenced by the performance of dierent programming language implementations (Decat et al.'s implementation is in Scala). Our im-

  1, because writes have little eect on performance when there are no conicts, and there are no conicts in experiments with only one client. For the throughput experiment with pWrite=0.0, for FACADE, we found nClient=24 and nWorker=8 provided the maximum throughput of 412 requests/second, with mean latency of 56.6 milliseconds; for Decat et al.'s algorithm, we found nClient=24 and nWorker=9 provided the maximum throughput of 373 requests/second, with mean latency of 62.0 milliseconds. For throughput experiment with pWrite=0.2, for FACADE, we found nClient=24 and nWorker=2 provided the maximum throughput of 303 requests/second, with mean latency of 77.4 milliseconds; for Decat et al.'s algorithm, we found nClient=25 and nWorker=4 provided the maximum throughput of 283 requests/second, with mean latency of 86.8 milliseconds. Thus, FA-CADE's maximum throughput is 11%, 8%, and 7% higher than Decat et al.'s algorithm's maximum throughput when pWrite=0.0, 0.1, and 0.2, respectively, and FACADE has lower latency in all three experiments.

  from 344 to 295 requests/second, and average latency increased from 65.5 to 75.9 milliseconds. For Decat et al.'s algorithm, the number of restarts due to conicts increased from 1 to 6, throughput decreased from 318 to 305 requests/second, and average latency increased from 79.5 to 81.7 milliseconds. Although FACADE is more sensitive than Decat et al.'s algorithm to this change, FACADE's performance is still competitive, with 3% lower throughput and 7% lower latency than Decat et al.'s algorithm.

	4 Related Work

Decat et al.'s work in

http://cassandra.apache.org/

https://www.mongodb.com/

https://dev.mysql.com/

Acknowledgments We thank M. Decat for explaining the details of [8].