Wei Jiang
email: wjiang@mst.edu

Bharath K Samanthula

N-Gram based Secure Similar Document Detection

Keywords: privacy, security, n-gram

Secure similar document detection (SSDD) plays an important role in many applications, such as justifying the need-to-know basis and facilitating communication between government agencies. The SSDD problem considers situations where Alice with a query document wants to find similar information from Bob's document collection. During this process, the content of the query document is not disclosed to Bob, and Bob's document collection is not disclosed to Alice. Existing SSDD protocols are developed under the vector space model, which has the advantage of identifying global similar information. To effectively and securely detect similar documents with overlapping text fragments, this paper proposes a novel n-gram based SSDD protocol.

Introduction

Textual information is ubiquitous and plays major roles in information dissemination. There are many practical situations where detecting documents that are similar to a given query document in a privacy-preserving way is beneficial. Consider an FBI agent looking for the data related to potential terrorist suspect. He or she may wish to check whether there are reports that are related to the suspect from local police databases. However, neither the FBI agent nor the local police wants to exchange their data unless there is a need to share. One way to identify such a need is to detect similarities or correlations between the the FBI's query (in form of textual document) and the local police's database of reports on criminal activities. Once the need for sharing information is verified, the FBI and the local police can exchange only the needed information. During the process of identifying similar or correlated information, it is the best interest for both parties not to disclose the query document and the database. Such a process is referred as secure similar document detection (SSDD).

The SSDD problem was first introduced in [START_REF] Jiang | Similar document detection with limited information disclosure[END_REF], where vector space model and Cosine Similarity are adopted to detect similar documents. Under the vector space model, each document is represented as a vector of terms or words, and each entry of the vector indicates certain frequency information of the corresponding term. When the vectors contain normalized term frequency values, secure dot product protocols (e.g., [START_REF] Goethals | On secure scalar product computation for privacy-preserving data mining[END_REF]) can be used as the building block for an SSDD protocol that identifies similar documents through Cosine Similarity. The same work was later extended in [START_REF] Murugesan | Efficient privacypreserving similar document detection[END_REF] to improve computation efficiency.

The vector space model is not the only way to compute document similarity, and n-gram based document representation [START_REF] Manber | Finding similar files in a large file system[END_REF] can also be adopted to detect similar documents. The vector space model has the advantage of detecting global similarity, e.g., a bag of similar terms. On the other hand, the n-gram model has the advantage of finding local similarity, e.g., overlapping of pieces of texts. Also, n-gram model is language independent and has simple representation. Plus, ngram based document modeling is less sensitive to document modification. Thus, the goal of this paper is to propose a n-gram based SSDD protocol under the semi-honest model [START_REF] Goldreich | The Foundations of Cryptography, volume 2, chapter General Cryptographic Protocols[END_REF].

Related Work

The SSDD problem was first introduced in [START_REF] Jiang | Similar document detection with limited information disclosure[END_REF]. The key in their work is how to securely compute the similarity between two documents. Initially, both participating parties, Alice and Bob, compute local (their own) vector spaces for their document collections. Then each of their documents can be represented as a vector of terms or words. Cosine similarity is adopted to measure similarity between any two documents. The same work was later extended in [START_REF] Murugesan | Efficient privacypreserving similar document detection[END_REF] to improve computation efficiency by combining text clustering techniques.

The Proposed Method

We follow the same setting as in [START_REF] Jiang | Similar document detection with limited information disclosure[END_REF][START_REF] Murugesan | Efficient privacypreserving similar document detection[END_REF]. Let Alice and Bob represent two entities, each of whom has a collection of documents. Given a query document u from Alice, the goal of an SSDD protocol is to detect whether or not Bob's collection (denoted by D = {v 1 , . . . , v n }) contains a document similar to u without disclosing Bob's database to Alice and vice versa. SSDD is defined as follows [START_REF] Jiang | Similar document detection with limited information disclosure[END_REF]:

SSDD(u, D) → σ 1 , . . . , σ n (1)
Instead of returning the actual similar documents, SSDD returns n1 similarity scores σ 1 , . . . , σ n to Alice. If one or more are particularly close, arrangements can be made (e.g., via agreed access control policies) to investigate further. The SSDD protocol proposed in this paper is based on the n-gram model. In general, an n-gram is a subsequence (substring) of size n from a given sequence (string). An n-gram of size 1, 2 or 3 is referred as an uni-gram, bi-gram or trigram receptively. An n-gram of size 4 or more is simply called n-gram. If a text document is treated as a one big string, under the n-gram model, each document can be represented by a set of successive n-gram. Table 1 shows four pieces of texts and their corresponding unique tri-gram representations. Under the n-gram model, the similarity between any two documents can be calculated using set similarity. A commonly accepted way to measure set similarity is to use Jaccard Coefficient (JC). Suppose u and v are two documents under the n-gram model, then JC between u and v is given by:

JC(u, v) = |u ∩ v| |u ∪ v| = |u ∩ v| |u| + |v| -|u ∩ v| (2)
Referring to Table 1, assume u is a query document and {v 1 , v 2 , v 3 } is Bob's document collection. The similarity between u and v 1 can be calculated by JC(u, v 1 ) = 3 7+8-3 = 0.25. JC will be adopted as the similarity measure in our proposed SSDD protocol.

Secure Similarity Computation

In order to return only the JC scores, our SSDD protocol consists of two stages. Each stage is summarized as follows:

-Stage 1 -Computing Random Shares of |u ∩ v i |:
At the end of this stage, Alice receives a random number a 1i and Bob receives a random number a 2i , such that To implement the first stage, Bob first generates a global space of n-gram based on his document collection, denoted by S. Then S is mapped to an integer domain from 1 to |S|. Let M denote such a mapping function and S j denote the j th element in S, then M (S j ) = j. Under the domain of M (S), each document v i can be represented by a binary vector v i (i.e., a vector with 0/1 entries). The following properties hold for each v i :

a 1i + a 2i mod N = |u ∩ v i |,
-|v i | = |S| -v i [j] = 1 ⇒ S j ∈ v i and v i [j] = 0 ⇒ S j ∈ v i , where v i [j] denotes the j th entry or dimension of v i .
Example 1. Following the documents in Table 1, Table 2 shows a global n-gram space based on Bob's document collection and the vector representation of each document on the global space. Note that not all n-gram in u appear in S because S is only derived from Bob's document collection. However, this does not affect the set intersection computation. To compute the intersection between u and v i , we merely calculate the dot product of u and v i , i.e., |u

∩ v i | = u • v i .
Global n-gram space and its mapping to integer domain S aaa aab abb abx bbc bcd bxy caa cdd ddf xaa xxx xxy xyy yxy yyx yyy yyz M (S) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Binary vector representation of each document in the global n-gram space u 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

v1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 v2 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 v3 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 Table 2. Global n-gram space
The above example shows that to securely compute |u ∩ v i |, we can use a secure dot product protocol that computes u•v i . We will adopt the homomorphic encryption based secure dot product protocol given in [START_REF] Goethals | On secure scalar product computation for privacy-preserving data mining[END_REF].

Stage 1 -Securely Computing a 1i and a 2i

Let E pk and D pr be the encryption and decryption functions in Paillier's publickey homomorphic encryption system [START_REF] Paillier | Public key cryptosystems based on composite degree residuosity classes[END_REF]. The encryption function has the following additive homomorphic property:

E pk (x 1 ) * E pk (x 2 ) = E pk (x 1 + x 2 ).
Given two documents u and v i , represented under the global n-gram model, the main steps computing a 1i and a 2i is given in Algorithm 1. The algorithm takes u from Alice and v i from Bob's document collection, and returns a 1i to Alice and a 2i to Bob, such that a 1i + a 2i mod N = u • v i . During this process, Alice does not know anything that is computationally feasible about Bob's input vector, and vice versa. At the beginning, Alice encrypts her private input vector component-wise and sends the encrypted vector to Bob denoted as z. Upon receiving z, At step 2(b), Bob computes E pk (u • v i ), the encryption of the dot product of u and v i , denoted by s. At step 2(c), Bob computes E pk (u • v i + r). At step 2(d), Bob computes his share a 2i and sends E pk (u • v i + r) to Alice. Alice can get her share a 1i by decrypting the value received from Bob. Note that Alice's private vector u is not disclosed to Bob because only the encrypted vector is sent to Bob. No one (except Alice) can decrypt the vector to get the actual values regarding u. In addition, because The protocol in Algorithm 1 is secure in the semi-honest model. The main reason is that the messages communicated during the execution of the protocol are random shares, which can be simulated based on the input and the output.

a 1i = u • v i + r and a 2i = N -r, it is certain that a 1i + a 2i mod N = u • v i . Algorithm 1 Computing Random Shares(u, v i ) → (a 1i ,

Complexity Analysis The complexity of Computing Random Shares consists of local computation cost and communication cost between the two parties.

Since the protocol is asymmetric, the local computation cost is different for each party. The main computation cost for Alice is encrypting her input vector, and we calculate her computation complexity based on the number of encryptions she performs. According to Algorithm 1, Alice's computation cost is determined by step 1(a) where the number of encryptions performed is linearly bounded by the size of her input vector. Therefore, the computation complexity for Alice is bounded by O(|S|) number of encryptions.

Step 2(b) of Algorithm 1 determines Bob's computation cost, and it requires at most |S| multiplications of ciphertexts received from Alice. In general, one encryption operation (or exponentiation) under the Paillier's system is much more expensive than one multiplication (depends on the size of encryption key). Here, we assume that the time it takes to perform one encryption at step 2(c) is less than |S| multiplications performed at step 2(b). Then, the computation complexity for Bob is bounded by O(|S|) number of multiplications.

Let k denote the size of encryption key in number of bits. (In practice, the encryption key N should be at lest 1,024-bit long.) The communication complexity of the protocol is bounded by step 1(b). Because the size of each ciphertext is bounded by k, the communication complexity is given by O(k • |S|) in bits.

Stage 2 -Securely Computing JC Scores

Once Alice and Bob obtain a 1i and a 2i respectively, Alice sets b 1i = |u|a 1i mod N and Bob sets b 2i = |v i |-a 2i mod N . Alice and Bob can securely compute a1i+a2i mod N b1i+b2i mod N , without disclosing a 1i , b 1i to Bob and a 2i , b 2i to Alice. Suppose Bob's collection contains n documents, at the end, Alice and Bob needs to compute n JC scores, one for each pair of u and v i . Algorithm 2 lists the main steps to achieve this. The inputs to the algorithm are α 1 and α 2 , from Alice and Bob respectively. α 1 , privately owned by Alice, contains n random shares generated from stage 1. Similarly, α 2 , privately owned by Bob, contains n random shares generated from stage 1. Initially, Alice and Bob independently compute β 1 and β 2 , so for 1 ≤ i ≤ n, JC score of u and v i is given by σ i = a1i+a2i mod N b1i+b2i mod N = |u∩vi| |u∪vi| . To securely compute σ i (without disclosing α 1 to Bob and α 2 to Alice), step 3 of Algorithm 2 adopts the appropriate Secure Division protocol proposed in [START_REF] Atallah | Private collaborative forecasting and benchmarking[END_REF]. The protocol takes private input (a 1i , b 1i ) from Alice and private input (a 2i , b 2i ) from Bob. It returns σ i = a1i+a2i mod N b1i+b2i mod N to either or both parties.

Algorithm 2 Computing JC Scores(α 1 , α 2 ) → σ 1 , . . . , σ n

Require: Alice's input: α1 = a11, . . . , a1n ; Bob's input: α2 = a21, . . . , a2n , and |α1| = |α2| = n 1: Alice: Compute β1 = b11, . . . , b1n , where b1i = |u| -a1i mod N for 1 ≤ i ≤ n 2: Bob: Compute β2 = b21, . . . , b2n , where b2i = |vi| -a2i mod N for 1 ≤ i ≤ n 3: Alice (with input α1, β1) and Bob (with input α2, β2): For 1 ≤ i ≤ n, compute σi ← Secure Division((a1i, b1i), (a2i, b2i))

Complexity Analysis

The secure dot product protocol can be easily implemented using Paillier's crypto system as suggested in [START_REF] Goethals | On secure scalar product computation for privacy-preserving data mining[END_REF]. We will empirically study the performance of the proposed protocol. To further improve the efficiency and instead of fixing the global n-gram space based on Bob's entire document collection, we could apply winnowing techniques [START_REF] Schleimer | Winnowing: Local algorithms for document fingerprinting[END_REF] on each Bob's document and select representative n-gram (or fingerprints) for each document. Since winnowing selects few fingerprints by adjusting window size and noise threshold, it is possible to reduce the global space to a larger extent thereby reducing the computational cost.

  where N is a security parameter or an encryption key. -Stage 2 -Computing JC Score: Alice sets b 1i = |u|a 1i mod N and Bob sets b 2i = |v i |a 2i mod N . Alice and Bob securely compute a1i+a2i mod N b1i+b2i mod N , without disclosing a 1i , b 1i to Bob and a 2i , b 2i to Alice.

  a 2i ) Require: Alice's input: Query Document u and (g, N ); Bob's input: vi and (g, N ); |u| = |vi| = |S| (Note: the private key pr is only known to Alice) 1: Alice: (a). Encrypt u component-wise: z[j] ← E pk (u[j]) for j = 1, . . . , |S| (b). Send z to Bob 2: Bob: (a). Receive z from Alice (b). s ← |S| j=1∧v i [j]=1 z[j] (c). s ← s * E pk (r), where r is randomly chosen from Z * N (d). a2i ← Nr (e). Send s to Alice 3: Alice: (a). Receive s from Bob (b). a1i ← Dpr(s)

Algorithm 3

 3 NGram SSDD(u, D) → σ 1 , . . . , σ n Require: Alice's input: u; Bob's input: D 1: Bob: (a). Compute S and M (S) from D (b). Compute vi from D, S, M (S), for 1 ≤ i ≤ |D| (c). Send S, M (S) to Alice 2: Alice: Compute u from u, S, M (S) 3: Alice and Bob: (a). Stage 1 -Computing Random Shares(u, vi), for 1 ≤ i ≤ |D| (At the end, Alice obtains α1 = . . . , a1n , and Bob obtains α2 = a21, . . . , a2n ) (b). Stage 2 -Computing JC Scores(α1, α2) Complexity Analysis The main cost of the protocol occurs at step 3 of Algorithm 3. Stage 1 initiates n executions of Computing Random Shares protocol. From Alice's point of view, based on the computation complexity analysis of Computing Random Shares, Alice needs to encrypt her query document u n times. However, during the actual implementation, Alice only needs to encrypt u once, and uses the same encrypted u for each of the n instantiations of the Computing Random Shares protocol. As a result, the computation cost for Alice at stage 1 is O(|S|) number of encryptions. Since each instantiation of Computing Random Shares requires Bob to perform O(|S|) multiplications, the computation cost for Bob at stage 1 is O(n • |S|) multiplications. Alice needs to send the encrypted u once, so the communication complexity for stage 1 is O(k • |S|) bits where k is the encryption key size in Paillier's system. Stage 2 only calls the Computing JC Scores once; thus, its complexity analysis is the same as that of Computing JC Scores. Combining the two stages together, the computation complexity of NGram SSDD for Alice is bounded by O(|S|+n) number of encryptions. The computation complexity of NGram SSDD for Bob is bounded by O(n • |S|) number of multiplications plus O(n) number of encryptions. The total communication complexity of NGram SSDD is bounded by O(k • |S| + k • n) bits.

Table 1 .

 1 Text n-gram representation u aabbc abbde {aab, abb, bbc, bca, cab, bbd, bde} v1 ca aabbc ddf {caa, aaa, aab, abb, bbc, bcd, cdd, ddf} v2 xaab xyyyz {xaa, aab, abx, bxy, xyy, yyy, yyz} v3 xxx yyy xyyz {xxx, xxy, xyy, yyy, yyx, yxy, yyz} Sample Texts

  Once we know how to securely implement Stage 1 and Stage 2, we can combine the two stages together to derive a n-gram based SSDD protocol. The main steps of the protocol are highlighted in Algorithm 3. Initially, Bob generates the global n-gram space S from his document collection D. Then a one-to-one mapping M (S) is created to map S to {1, . . . , |S|}. At step 1(c) of Algorithm 3, Bob, according to S and M (S), computes the vector representation of each document in his document collection D under the n-gram model. Once Alice receives S and M (S), Alice generates u, the vector representation of her query document u under the n-gram model. After that Alice and Bob can proceed to Stage 1 and Stage 2. At the end of stage 2, Alice receives a set of similarity scores, or these scores can be shared by both parties. The security of the protocol is determined by the Secure Division protocol adopted at stage 2.

	Without giving fur-
	ther details, the computation cost of Secure Division for both party is bounded
	by O(1) number of encryptions. The communication cost of Secure Division is
	bounded by O(k) bits, where k is the size of an encryption key in bits. Com-
	puting JC Scores requires n executions of Secure Division, so its computation
	complexity is bounded by O(n) encryptions for each party, and the communica-
	tion complexity is bounded by O(k • n) bits.
	2.4 N-Gram based SSDD

Note that in this paper, n is used to indicate either Bob's document collection size or the length of the n-gram depends on the context.

Acknowledgment

This material is based upon work supported by the Office of Naval Research under Award No. N000141110256.


Joachim Biskup
email: joachim.biskup@cs.tu-dortmund.de

History-Dependent Inference Control of Queries by Dynamic Policy Adaption

Keywords: a priori knowledge, closed query, confidentiality policy, Controlled Query Evaluation, inference control, information system, interaction history, policy adaption, propositional logic, refusal, view

Policy-based inference control of queries submitted to a logicoriented information system requires us to consider the history of queries and answers to a particular user. In most previous approaches, the control system captures the history by maintaining a fictitious view the user is supposed to generate by exploiting rational reasoning. In this paper, we propose and explore an alternative option to represent the history, namely by suitably adapting the confidentiality policy after returning an answer to a query. Basically, such a policy adaption precomputes all relevant steps of formal proofs that the fictitious view logically implies some policy element. We focus on propositional information systems.

Introduction

Inference control is a crucial though costly mechanism to protect information rather than just the underlying data, as achieved by traditional access control or simple encryption [START_REF] Biskup | Security in Computing Systems -Challenges, Approaches and Solutions[END_REF]. In general, dynamic inference control of queries submitted to an information system necessarily requires us to consider the history of queries and answers related to a particular user. In most of the previous work, including those on Controlled Query Evaluation (CQE) [START_REF] Biskup | Usability confinement of server reactions maintaining inference-proof client views by controlled interaction execution[END_REF], the control employs the user's history in two ways: First, the control generates an (assumption about the) view that the user (supposingly) infers to represent his knowledge about the instance of the information system. This instance itself, however, remains hidden to the user, except that he has seen the previous answers and might have access to some a priori knowledge. Second, the control investigates whether that view combined with the correct answer to the next submitted query (or some closely related information) would be harmful w.r.t. a confidentiality policy specifically declared for the user.

In this context the intuitive meaning of harmful is the following: the user will be able to infer that some sentence contained in the policy actually holds in the instance. If this will be the case, the control reacts with a suitable distortion of the correct answer to avoid a security violation. In any case, after returning a reaction to the user, the control has to appropriately adjust the view generated for the user. Thus, over the time, the control enforces a suitable invariant to ensure that the view will be never harmful.

Notably, the view is dynamically updated after each reaction to a query, whereas the policy is kept unchanged once it has been statically declared by a security officer. We can rephrase this approach to dealing with the history as follows: at any point in time, the control has to confine the entailment relationship between the increasingly powerful (knowledgeable) view and the static policy.

We will illustrate this view-based approach to inference control by the following simple and straightforward example. Suppose that the policy requests to keep the propositional sentence ϕ 1 ∧ ϕ 2 secret. Furthermore, the user is assumed to have no a priori knowledge about the instance, for which both ϕ 1 and ϕ 2 are supposed to hold, and thus ϕ 1 ∧ ϕ 2 as well. Initially, the control generates an empty view. Then, as a first query, the user submits the sentence ϕ 1 in order to ask whether this sentence holds. The correct answer, ϕ 1 , i.e., that this sentence holds, together with the empty view does not entail the single policy element, and thus the control returns the correct answer to the user in undistorted form and, accordingly, updates the view, which now comprises just the returned answer ϕ 1 . Finally, as a second query, the user submits ϕ 2 . Now, the correct answer, ϕ 2 , together with the content of the updated view, ϕ 1 , obviously entails the policy element, ϕ 1 ∧ϕ 2 , and thus the control must suitably distort the answer. Note the dynamic "last-minute behavior" of the control: if the queries were submitted in reverse order, first ϕ 2 and then ϕ 1 , then ϕ 2 would have been correctly answered and the answer to ϕ 1 would have been distorted.

In this work, we will explore an alternative approach to employ the user's history. The alternative approach aims to represent the user's history by dynamically adapting the policy, thereby getting rid of the need to generate and maintain a view for the user. Intuitively, over the time, we will increasingly strengthen the policy, making it more and more restrictive as a countermeasure to the knowledge accumulated by previous answers.

To illustrate this alternative policy-adaption based approach, we reconsider the example presented above. Initially, the policy contains the sentence ϕ 1 ∧ ϕ 2 . Since the first query, ϕ 1 , is harmless, the correct answer is returned to the user. Now, once one of the conjuncts occurring in the original policy element is known to the user, he must not learn the other conjunct as well. Accordingly, the control replaces the previous policy element ϕ 1 ∧ ϕ 2 by ϕ 2 to be kept secret in future. If afterwards the second query, ϕ 2 , is submitted, the control will immediately detect that the correct answer would violate the adapted policy and thus will distort the answer, as in the view-based approach.

We can also describe the policy-adaption based approach in terms of theoremproving, as sketched in the following and elaborated in more detail in the remainder of this paper. In the starting step, for each sentence contained in the declared policy and thus explicitly wanted to be kept secret to the user while returning answers to him, the user is supposed to aim at proving (the validity of) that sentence from the answers received. Acccordingly, for simplicity here assuming no a priori knowledge, the user initially considers every sentence contained in the declared policy to be a current proof obligation. Having received a new answer Φ i in step i, the user can analyze all possible formal proofs for any of the current proof obligations whether and how Φ i will be helpful to prove it. If the user detects such a situation, he can determine the resulting remaining proof obligations and, potentially, try to satisfy them by issuing further queries. Correspondingly, inference control can track the user's abilities, and thus control can dynamically adapt the policy by always setting it to the current set of proof obligations. In the example given above, the sole initial proof obligation is ϕ 1 ∧ ϕ 2 , which can be replaced by the new proof obligation ϕ 2 , once ϕ 1 is known.

Dynamic inference control is costly, at least in general, due to the inevitable need to suitably keeping track of the history and performing some kind of theorem-proving. The basic features of policy adaption suggest the possibility of substantial improvements in computational costs at query time in comparison with the view-based approach, at least in special situations: (1) the control no longer has to maintain a separate data structure for reflecting the user's view, and (2) analyzing and remembering remaining proof obligations can bee seen as a kind of stored precomputation for the task of checking whether subsequent queries are harmful or not. Moreover, we might be able to find appropriate data structures to actually benefit from the potentials.

In the following we roughly outline such an improvement for a restricted propositional situation, where queries are just propositional atoms of the form a i and elements of the confidentiality policy are conjunctions of such atoms, thus of the form a i1 ∧. . .∧a i k with 1 ≤ k. Moreover, we will make policies redundancyfree in the sense that no policy element is a subconjunction of another policy element, just by discarding the larger one. As an example, let the policy be {a 1 ∧ a 2 ∧ a 3 , a 3 ∧ a 4 , a 4 ∧ a 5 , a 6 }, and consider the query sequence a 1 , a 2 .

The current policy will be represented by a data structure that is composed of two linked parts. The "look-up part" contains all atoms still occurring in the policy, and the "reduced part" comprises the nontrivial conjunctions (having at least 2 different atoms) still to be checked. Moreover, each atom in the former part is linked to each of the conjunctions in which it occurs in the latter part. Fig. 1 shows the initial state of the data structure for the example.

If an atom a i is submitted as a query, the control first searches for that atom in the look-up part. If the atom is not found there, the query is censored to be harmless and correctly answered. Otherwise, there are two cases: If the atom is not linked to any nontrivial conjunction, then the atom is harmful by itself and the answer must be distorted. Otherwise, if there are links, the query is censored to be harmless and correctly answered, but the policy must be adapted by manipulating the current state of the data structure appropriately: (1) the query atom a i is removed from the look-up part; (2) the query atom a i is deleted from all the conjunctions in which it occurs; (3) if after the deletion a remaining conjunction is reduced to a single atom a j , then the conjunction is dropped at all and the corresponding link from a j is deleted as well; moreover, all other conjunctions in which a j occurs are deleted with all their links, too. Finally, ifby these deletions -another atom in the look-up part has lost all its links, then that atom is deleted from the look-up part. Fig. 1 visualizes how the control operates for the parameters specified above. Querying the atom a 1 is harmless and leads to its removal from the look-up part by [START_REF] Abiteboul | Foundations of Databases[END_REF] and its deletion from the first conjunction, which is thus reduced to a 2 ∧a 3 by (2). Then querying the atom a 2 is harmless again and leads to its removal from the look-up part by [START_REF] Abiteboul | Foundations of Databases[END_REF] and its deletion from the reduced conjunction, which thus becomes the single atom a 3 by (2); but this trivial conjunction is then totally dropped by [START_REF] Bertino | A logic-based approach for enforcing access control[END_REF], and the conjunction a 3 ∧ a 4 is deleted as well.

Since only some searching and elementary link manipulations are used, the efficiency of the procedure should be evident. A full justification of the correctness is elaborated in Sect. 3 for a more general situation. Roughly summarizing, in this article we will provide the following main contributions:

-We propose the policy-adaption based approach to keeping track of the history as a promising alternative to the view-based approach (this Sect. 1). -After introducing our basic notations, briefly reviewing the view-based approach and commenting on complexity issues (Sect. 2), we fully elaborate the new approach for a special but reasonably expressive situation of Controlled Query Evaluation. This situation employs refusal as the sole distortion option and deals with a propositional information system (Sect. 3). -We relate our approach to previous work, briefly discuss first-order information systems and evaluate the expected potentials and limitations (Sect. 4).

Basic Notations and View-Based Approach

Restricting to propositional information systems, we first introduce our basic notations. Then we briefly describe the view-based approach and state some observations on the complexity of deciding the pertinent logical implications.

Basic Notations

We employ a logic-oriented approach to information systems (see, e.g., [START_REF] Abiteboul | Foundations of Databases[END_REF]), which establishes formal semantics for both query answering and updating (not considered in this paper). For simplicity, we only consider complete information systems, and we focus on propositional logic. We assume a vocabulary of propositional atoms, from which we can construct propositional sentences in the standard way, using the propositional connectives of negation and disjunction and further derived connectives. A literal is either an atom or a negated atom.

The schema (of the information system) is given by the vocabulary and the integrity constraints, which are expressed as a finite set con of sentences over this vocabulary. We consider the integrity constraints as part of any user's a priori knowledge, which in each case is given as a set of sentences over the vocabulary.

An instance db (of the information system) is a set of literals formed as follows: For each atom α of the vocabulary, either the atom α itself or the negated atom ¬α is an element. Given the vocabulary, it suffices to explicitly specify only those atoms that are contained in an instance (implicitly assuming for the remaining atoms that their negations are elements by default, as a kind of closed world assumption). An instance db defines a truth-value assignment to propositional atoms by making each atom α ∈ db true and all the remaining atoms false. Such a truth-value assignment (interpretation) is inductively extended to arbitrary sentences Φ by giving the connectives the standard meaning; eval (Φ)(db) denotes the truth value assigned to Φ by db. The standard notion of logical implication, or entailment, between (sets of) sentences is designated by |=.

As a (closed, yes/no-)query, we allow any sentence Φ of the underlying propositional logic. The correct answer to the query Φ under an instance db is given by the pertinent truth value eval (Φ)(db); however, for convenience, we alternatively express the correct answer by eval * (Φ)(db) that denotes either Φ or ¬Φ in a straightforward way. We aim at controlling any sequence of queries Q := Φ 1 , Φ 2 , . . . , Φ i , . . . , Φ k where the query Φ i is submitted by some user at the point in time i; for simplicity of the presentation, we focus on only one user.

While the user is granted a general access right for reading (querying), a security officer declares a confidentiality policy as a finite set psec of propositional sentences, called potential secrets, in order to confine the actual information gain that can be achieved by the user. Here the qualification "potential" indicates that these sentences are not necessarily true in the actual instance. Following the principle of open design, the user is supposed to be aware of this declaration, as well as of all other features of the control mechanism. In order to prevent the user from ever inferring that any sentence Ψ ∈ psec actually holds, we follow the refusal approach to inference control [START_REF] Sicherman | Answering queries without revealing secrets[END_REF][START_REF] Biskup | Controlled query evaluation for enforcing confidentiality in complete information systems[END_REF][START_REF] Biskup | Usability confinement of server reactions maintaining inference-proof client views by controlled interaction execution[END_REF], i.e., if an informative answer to a query would be harmful, then the control reacts by returning a special symbol mum. In general, the refusal approach has to examine not only whether the correct answer to a query is harmful but also whether its negation would be harmful, in order to prevent so-called meta-inferences.

Besides the policy, in general the control mechanism also has to consider the (postulated) a priori knowledge of the user and the answers to previously issued queries. To do so, the control might maintain a user log. Basically, such a user log then just contains a set log of propositional sentences. In principle, both the policy and the user log might be updated while processing queries; the current versions of them taken together form the current state s i := (psec i , log i ) of the control mechanism. The initial state is obtained by setting psec 0 := psec and log 0 := prior , where prior can be any suitable superset of the constraints con not being in conflict with psec, i.e., prior |= Ψ for all Ψ ∈ psec. In this work, for simplicity, we will not elaborate the treatment of the a priori knowledge prior in depth: we just leave it empty in our examples, and we simply process it like a sequence of queries within our initialization subprotocol.

Definition 1 (controlled query evaluation). Let be given an instance db, a finite set log i-1 of sentences (for explicitly reflecting the assumed user's current knowledge about the instance), and a finite set psec i-1 of sentences (for representing the current version of the confidentiality policy). Then a function cqe(db, psec i-1 , log i-1 , Φ i ) defines a controlled query evaluation of a query Φ i by generating a triple (ans i , psec i , log i ), where ans i is the answer returned to the user, and psec i and log i together form the updated state.

Furthermore, for the initializations specified above, this function is inductively extended to any query sequence Q := Φ 1 , . . . , Φ i , . . . , Φ k by applying it stepwise in a straightforward way:

cqe(db, psec 0 , log 0 , Q) := (ans 1 , psec 1 , log 1 ), . . . , (ans i , psec i , log i ), . . . , (ans k , psec k , , log k ) (1)
We are now ready to present our formal definition of the confidentiality requirement we want to achieve by a controlled query evaluation. Roughly summarized, given a potential secret Ψ declared in the (original) policy psec, this requirement is expressed in terms of the indistinguishability -from the point of view of the user -of the actual instance db from an alternative instance db s that does not satisfy the potential secret considered.

Definition 2 (confidentiality).

A controlled query evaluation cqe preserves confidentiality iff for all instances db, for all finite sets of sentences psec (original confidentiality policy), for all finite sets of sentences prior (a priori knowledge) satisfied by db and such that prior |= Ψ for all Ψ ∈ psec, for all query sequences Q, and for all potential secrets Ψ ∈ psec there exists an alternative instance db s satisfying prior such that:

1. [indistinguishability]: cqe(db, psec, prior , Q) = cqe(db s , psec, prior , Q) (2)
2.

[possibility of false potential secrets]:

eval * (Ψ )(db s ) = ¬Ψ (3)

View-Based Approach

The view-based approach to Controlled Query Evaluation, as surveyed in [START_REF] Biskup | Usability confinement of server reactions maintaining inference-proof client views by controlled interaction execution[END_REF], keeps track of the history by only updating the user log, while leaving the original policy unchanged. For the specific setting described above, i.e., refusal under known potential secrets for a propositional information system dealing with closed (yes/no-)queries, the function cqe view is defined by its outputs as follows:

ans i := if log i-1 |= eval * (Φ i )(db) then eval * (Φ i )(db) else if (exists Ψ ) (Ψ ∈ psec and (log i-1 ∪ {Φ i } |= Ψ or log i-1 ∪ {¬Φ i } |= Ψ )) then mum else eval * (Φ i )(db) (4) psec i := psec ( 5
)
log i := if ans i = mum then log i-1 else log i-1 ∪ {ans i } (6)
Proposition 1 ([6]). The function cqe view preserves confidentiality in the sense of Def. 2.

Definition (4) of the controlled answer indicates that the task of inference control is closely related to the problem of deciding on logical implications of the form χ |= Ψ , where the finite set of sentences χ -equivalently identified with the corresponding sentence formed as the conjunction over this set -denotes some potential knowledge of the user and Ψ is a policy element. This decision problem is well-known to be of high computational complexity in general, and thus we can expect to control answers efficiently only under some restrictions of the expressiveness of the languages for the sentences χ and Ψ , respectively.

As a starting point, we first observe the following: If both χ and Ψ are already specified in disjunctive normal form for a finite vocabulary, i.e., as a disjunction of so-called minterms that are built as a conjunction of literals (atoms or negated atoms) ranging over all atoms in the vocabulary, then χ |= Ψ holds if and only if each minterm of χ is also a minterm of Ψ .

For a slightly relaxed situation where both χ and Ψ are specified as a disjunctive form, i.e., a disjunction of conjunctions of literals ranging over different atoms in the vocabulary, the sufficiency part of this observation can be generalized along the following lines of reasoning, often referred to as subsumption. First, if some disjunctive sentences η 1 and η 2 are (syntactically) related such that each disjunct of η 1 is also a disjunct of η 2 -or at least (semantically) implies some disjunct of η 2 -, then the (semantic) implication η 1 |= η 2 holds, since η 2 is an obvious weakening of η 1 . Dually, if some conjunctive sentences θ 1 and θ 2 are (syntactically) related such that each conjunct of θ 1 is also a conjunct of θ 2 -or is at least (semantically) implied by some conjunct of θ 2 -, then the (semantic) implication θ 2 |= θ 1 holds, since θ 2 is an obvious strengthening of θ 1 .

Unfortunately, the necessity part of the observation stated above cannot be generalized for arbitrary disjunctive forms. However, the necessity part holds indeed, if the sentence Ψ consists of all the prime implicants of Ψ , i.e., (1) each disjunct of Ψ is minimal in the sense that discarding any of the literals in the conjunction that constitutes this disjunct would result in a non-equivalent sentence, and (2) Ψ contains all minimal disjuncts (conjunctions of literals ranging over different atoms in the vocabulary) that imply Ψ . Proposition 2. Let χ be a disjunctive form and Ψ a disjunctive form that consists of all its prime implicants. Then χ |= Ψ holds if and only if for each disjunct of χ there is a disjunct of Ψ such that each literal occurring as a conjunct of the latter disjunct also appears as a conjunct of the former disjunct.

Policy Adaption for Propositional Information Systems

We now present our new concept of the policy-adaption based approach in detail, exhibit an appropriate data structure for representing the current policy, and then demonstrate the correctness and comment on the efficiency.

Outline and Examples

To elaborate the policy-adaption based approach, we aim at defining the corresponding function cqe pol for controlled query evaluation such that the following properties (further explained below) hold:

1. The parameter log could be dropped. 2. The history is reflected in the current version psec i of the policy. 3. The generated outputs ans i are the same as for cqe view . 4. The current version psec i is converted to be redundancy-free (see below). 5. The current version psec i is converted to be fully vulnerable (see below).

We first outline the basic techniques to achieve these properties, then exemplify these techniques, and finally present and verify a comprehensive algorithm for cqe pol leading to a controlled query evaluation based on these techniques.

By property 3 and as a corollary to the result for cqe view stated in Prop. 1, the function cqe pol will preserve confidentiality in the sense of Def. 2 as well.

Regarding property 4, demanding the policy to be redundancy-free, we can observe the following by inspecting the guarding condition in the second line and the third line of (4): If a policy psec contains two different potential secrets Ψ 1 and Ψ 2 such that Ψ 1 |= Ψ 2 , then we can remove Ψ 1 from the policy without affecting the answer. For, if a user knowledge log ∪{Φ} or log ∪{¬Φ}, respectively, implies Ψ 1 , then that knowledge also implies Ψ 2 ; thus the outcome of the guarding condition remains the same after removing Ψ 1 . Accordingly, we will keep the set psec redundancy-free in the sense that none of its elements implies another one.

Regarding property 5, demanding the policy to be fully vulnerable, we further observe the following: If a policy psec contains a potential secret Ψ such that log |= ¬Ψ holds for the current user knowledge log, then we can remove Ψ from the policy. For, by monotonicity, this property will always be preserved later on and thus the confidentiality requirement expressed by Ψ will never be hurt.

Regarding the properties 2 and 3, which demand an appropriate reflection of the history in psec i such that the same outputs are generated as in the viewbased approach, again by inspecting the guarding condition in the second line and the third line of (4), we have to inductively achieve an equivalence of the following kind (to be made more precise later on), where ∆ i denotes the query Φ i or its negation ¬Φ i , respectively:

(exists Ψ )(Ψ ∈ psec and log i-1 ∪ {∆ i } |= Ψ ) iff (7)
(exists Ψ )(Ψ ∈ psec i-1 and {∆ i } |= Ψ ) (8)
To attain such a goal, we first impose all queries Φ i and all policy elements Ψ to be given as a disjunctive form. Moreover, we additionally extend each policy element such that it contains all its prime implicants in order to profit from the efficiently verifiable characteristic property of χ |= Ψ given in Prop. 2. Next, again for easily exploiting that property, in general we aim at representing a policy element of the form Ψ = Ψ 1 ∨ . . . ∨ Ψ m that constitutes a nontrivial disjunction with 2 ≤ m as the set of its disjuncts {Ψ 1 , . . . , Ψ m }. To achieve a homogeneous treatment with a policy element of the form Ψ = Ψ 1 having only one disjunct, we then have to represent such an element as the singleton set {Ψ 1 }. The set representations introduced will not affect the wanted equivalence, since they are functional equivalent with the original forms. If there are no semantic ambiguities, i.e., from a special context under consideration it is clear whether two disjuncts (implicants) belong to the same policy element or not, as in the examples below, we will omit the set notation for the sake of readibility.

Finally, to deal with disjunctive answers of the form Φ = Φ 1 ∨ . . . ∨ Φ n with 2 ≤ n, we will introduce policy branches: for each disjunct Φ l , a copy of the current policy is generated and then inspected regarding implications that result from Φ l alone. Subsequently, each of these branches has to be maintained with reference to the pertinent Φ l until a definite answer that ¬Φ l holds is given; then the branch is obviously contradictory and thus must be removed.

Example 1. Consider the following situation:

db := {a 1 , ¬a 2 , ¬a 3 , a 4 } is the instance, Q := a 1 , a 2 , a 3 , a 4 is the query sequence, psec := {¬a 1 ∧ ¬a 2 ∧ a 3 ∧ ¬a 4 , a 1 ∧ ¬a 2 ∧ ¬a 3 ∧ a 4 } is the policy, and log 0 := ∅ is the void a priori knowledge. Then a 1 , ¬a 2 , ¬a 3 , a 4 is the correct answer sequence, and the instance defines the first potential secret to be false and the second one to be true.

Controlling the first query a 1 , we see that neither a 1 nor ¬a 1 implies any of the potential secrets, and thus the correct answer a 1 can be returned, and it would be inserted into the user log by the view-based approach such that we would have log 1 := {a 1 }. Since the first potential secret is no longer vulnerable, we can remove it from the policy. Furthermore, once the user knows a 1 , we now have to protect the remainder of the second potential secret, i.e., we can drop a 1 from a 1 ∧ ¬a 2 ∧ ¬a 3 ∧ a 4 . Thus we get psec 1 := {¬a 2 ∧ ¬a 3 ∧ a 4 }. however, we can remove the then subsumed elements ¬a 3 ∧ ¬a 4 and a 3 ∧ a 4 . Thus we get psec 2 [¬a 2 ] := {a 4 , ¬a 3 }. In the branch for a 3 , we can drop the occurrence of a 3 from one of the elements, yielding the reduced element a 4 , and we can remove the elements ¬a 3 ∧ ¬a 4 and ¬a 2 ∧ ¬a 3 , in which the complementary literal ¬a 3 occurs. Additionally, the element ¬a 2 ∧ a 4 is now subsumed and thus can be removed. Thus we get psec 2 [a 3 ] := {a 4 }. Controlling the third query a 3 , we see that the correct answer ¬a 3 makes the policy branch for a 3 contradictory and implies an element in the remaining branch for ¬a 2 . Accordingly, the answer must be refused and both policy branches remain unchanged. Finally, controlling the fourth query a 4 , we see that the correct Fig. 2. A converted and then stepwise adapted confidentiality policy Similarly, stepwise controlling the second query a 2 and the third query a 3 , we (would) get the following:

log 2 := {a 1 , ¬a 2 }, psec 2 := {¬a 3 ∧ a 4 }, log 3 := {a 1 , ¬a 2 , ¬a 3 }, psec 3 := {a 4 }.
Finally, controlling the fourth query a 4 , we immediately see that the correct answer violates the policy, and thus the answer must be refused. Notably, if the correct answer was ¬a 4 , then that answer would have to be refused as well.

Example 2. Consider the following situation, the processing of which is further illustrated in Fig. 2: db := {a 1 , ¬a 2 , ¬a 3 , a 4 } is the instance, the same as before,

Q := a 1 , ¬a 2 ∨ a 3 , a 3 , a 4 is the query sequence, psec := { a 1 ∧ ¬a 3 ∧ ¬a 4 ∨ a 1 ∧ ¬a 2 ∧ a 4 ∨ a 1 ∧ a 2 ∧ a 3 ∧ a 4 ∨ ¬a 1 ∧ a 2 ∧ a 3 ∧ a 4 ∨ ¬a 1 ∧ a 2 ∧ ¬a 3 }
is the policy, and log 0 := ∅ is the void a priori knowledge. Obviously, then a 1 , ¬a 2 ∨ a 3 , ¬a 3 , a 4 is the correct answer sequence, and the instance defines the sole potential secret to be true.

At initialization time, we observe that the sole policy element can be equivalently simplified by combining the two disjuncts a 1 ∧ a 2 ∧ a 3 ∧ a 4 and ¬a 1 ∧ a 2 ∧ a 3 ∧ a 4 into the prime implicant a 2 ∧ a 3 ∧ a 4 . Furthermore, even afterwards the policy element does not contain all its prime implicants; in fact, we have to add four further prime implicants, namely a 2 ∧ ¬a 3 ∧ ¬a 4 , a 1 ∧ ¬a 2 ∧ ¬a 3 , a 1 ∧ a 3 ∧ a 4 , and ¬a 1 ∧ a 2 ∧ a 4 . Subsequently, we replace the sole policy element by the set of its disjuncts (prime implicants) and get the following representation of the policy:

psec 0 := {a 1 ∧ ¬a 3 ∧ ¬a 4 , a 1 ∧ ¬a 2 ∧ a 4 , a 2 ∧ a 3 ∧ a 4 , ¬a 1 ∧ a 2 ∧ ¬a 3 , a 2 ∧ ¬a 3 ∧ ¬a 4 , a 1 ∧ ¬a 2 ∧ ¬a 3 , a 1 ∧ a 3 ∧ a 4 , ¬a 1 ∧ a 2 ∧ a 4 }.
Controlling the first query a 1 , we see that neither a 1 nor ¬a 1 implies any of the potential secrets, and thus the correct answer a 1 can be returned. Since the policy elements containing the complementary literal ¬a 1 are no longer vulnerable, we can remove them from the policy. Furthermore, once the user knows a 1 , we can drop a 1 from the remaining elements. Additionally, we can remove elements that have become redundant, which is equivalent to being subsumed by a shorter disjunct. Altogether we get psec 1 := {¬a 3 ∧ ¬a 4 , ¬a 2 ∧ a 4 , ¬a 2 ∧ ¬a 3 , a 3 ∧ a 4 }. Controlling the second query ¬a 2 ∨ a 3 , we see again that neither the positive answer ¬a 2 ∨ a 3 nor the negative answer a 2 ∧ ¬a 3 implies any of the potential secrets, and thus the correct answer can be returned. However, since the correct answer is a disjunction, we split the policy into branches, one for the case that ¬a 2 is actually true and another one for the case that a 3 is actually true.

In the branch for ¬a 2 , we can drop the occurrences of ¬a 2 from two of the elements, yielding the reduced elements a 4 and ¬a 3 . As there are no occurrences of the complementary literal a 2 , all elements are still vulnerable. Additionally, however, we can remove the then subsumed elements ¬a 3 ∧ ¬a 4 and a 3 ∧ a 4 . Thus we get psec 2 [¬a 2 ] := {a 4 , ¬a 3 }. In the branch for a 3 , we can drop the occurrence of a 3 from one of the elements, yielding the reduced element a 4 , and we can remove the elements ¬a 3 ∧ ¬a 4 and ¬a 2 ∧ ¬a 3 , in which the complementary literal ¬a 3 occurs. Additionally, the element ¬a 2 ∧ a 4 is now subsumed and thus can be removed. Thus we get psec 2 [a 3 ] := {a 4 }. Controlling the third query a 3 , we see that the correct answer ¬a 3 makes the policy branch for a 3 contradictory and implies an element in the remaining branch for ¬a 2 . Accordingly, the answer must be refused and both policy branches remain unchanged. Finally, controlling the fourth query a 4 , we see that the correct answer a 4 implies a policy element in both branches, and thus the answer must be refused as well.

Protocol for Policy Adaption and Correctness

Having introduced the basic techniques, we are now ready to specify the types, inputs and methods of our new approach of policy adaption more formally. As explained in Sect. 3.1, the protocol for policy adaption has been designed to achieve the same effects as the view-based approach. Thus the protocol is claimed to be correct with respect to the view-based approach and, accordingly by Prop. 1, to preserve confidentiality. The latter claim is stated in the following theorem, the proof of which justifies the former claim. Proof. For lack of space, we only outline the inductive proof, which follows the informal arguments presented in Sect. 3.1. Basically, the induction will deal with the following items and notations:

hist i-1 := k l β k,l equivalently represents the user log log i-1 under the view-based approach as a single sentence converted into disjunctive form. -∆ i := k χ k in disjunctive form denotes the query Φ i or its negation ¬Φ i .

tent i := hist i-1 ∧ ∆ i = k,k ( l β k,l ∧ χ k ) then represents a left-hand side in a violation test according to (4), but so far ignoring that contradictory disjuncts might occur. -tent red i := k, k ( l βk ,l ∧ χk ) in disjunctive form results from tent i by discarding all contradictory disjuncts (containing both an atom α and the negated literal ¬α). The special case that tent red i becomes the empty disjunction only happens if log

i-1 |= eval * (Φ i )(db) and ∆ i = ¬eval * (Φ i )(db). -D i-1 is the set of tags D occurring in the current policy psecb i-1 . -psecb i-1 := {sec D [D] | D ∈ D i-1 }
then describes the elements of that policy.

One can verify that the generation subprotocol establishes a one-to-one correspondance between the set of non-contradictory disjuncts l β k,l of hist i-1 , ranging over all pertinent k, and D i-1 , such that for each k the corresponding tag D satisfies D = {β | β = β k,l for some l}. Note that if the generation subprotocol tentatively forms a branch corresponding to a contradictory disjunct, then this fact is detected by performing the adaption subprotocol, which leads to an immediate deletion of that branch.

Then we assert and comment the equivalence of the following assertions:

1. (exists Ψ )(Ψ ∈ psec and log i-1 ∪ {∆ i } |= Ψ ).
Such a kind of assertion is checked by the view-based approach according to (4), to be shown to satisfy the equivalence given by "(7) iff ( 8)". 2. (exists Ψ )(Ψ ∈ psec and tent red i |= Ψ ). The set on the left-hand side of |= is represented as a single sentence, which is formed as the conjunction over all elements of that set and then converted into disjunctive form (with discarding of contradictory disjuncts). 3. (exists Ψs )( Ψs = { Ψs,1 , . . . , Ψs,m } ∈ sec ∅ and k, k ( l βk ,l ∧χk ) |= r Ψs,r ).

Here { Ψs,1 , . . . , Ψs,m } are the initially determined prime implicants of Ψs . 4. (exists Ψs )( Ψs = { Ψs,1 , . . . , Ψs,m } ∈ sec ∅ and (for all k )(for all k) (exists Ψs,r )( Ψs,r ∈ Ψs and l βk ,l ∧ χk |= Ψs,r )). We have exploited Prop. 2 for treating the implication problems. The simplifications of the adaption subprotocol preserve the applicability of the efficient implication check, as stated in Prop. 2. Bascially, this kind of assertion is checked by the violation subprotocol of the policy-adaption approach.

Efficiency of Policy Adaption

Without restrictions the worst-case complexity of policy adaption is inevitably determined by the complexity of the decision problems for propositional logic and thus expected to be exponential. Exponential efforts might also be hidden in transforming sentences into disjunctive forms or even determining all prime implicants. However, queries or negated queries that consist of strict disjunctions or generate strict disjunctions, respectively, are the sole cause of branching and thus of an exponential explosion of the size of an adapted policy. Besides these general remarks, analytical complexity results on "average"-case complexity appear to be hardly obtainable and are beyond the scope of this paper. It is left open to future work to implement a prototype and to set up practical experiments. If we then aim at empirically comparing policy adaption and view generation for special cases, we will be challenged to identify the best available optimization techniques for each of the two approaches.

If we restrict on queries that are single literals and then inspect such a literal, we have to determine whether and how the atom involved occurs in one of the implicants in the current policy data. To generalize the data structure exemplified in Fig. 1, we could maintain an efficiently searchable structure of all relevant atoms, together with the set structure comprising all current implicants (then including single literals), linking an atom with all pertinent implicants.

Related Work, Extensions and Conclusions

Though the policy-adaption based approach is innovative for inference control by means of Controlled Query Evaluation, some of the underlying ideas are already implicitly present in various previous work. First of all, we observe that a mechanism for enforcing inference control can be seen as an automaton that is basically specified by its set of internal states, its state transition function and its output or reaction function. In principle, for Controlled Query Evaluation a state has to reflect both a user's history and the confidentiality policy suitably. Accordingly, in a straightforward approach, a state can just be formed by a combination of two components: a current log of the user's history and a current version of the policy. In fact, the view-based approach explicitly maintains these two components. In contrast, the policy-adaption based approach aims at representing both of the needed features within one component.

All work on state-dependent control is somehow related to our contribution, as can be seen from the following examples. The works on "enforceable security properties" [START_REF] Schneider | Enforceable security policies[END_REF][START_REF] Ligatti | A theory of runtime enforcement, with results[END_REF] treat states as abstract objects, without indicating implementations. Advanced discretionary access control based on logic programming, like the Flexible Authorization Framework [START_REF] Jajodia | Flexible support for multiple access control policies[END_REF] maintains a special "done-predicate", which can be seen as a kind of a user log or as a kind of a dynamic component of the access control policy, depending on the point of view. The Dynamic Authorization Framework [START_REF] Bertino | A logic-based approach for enforcing access control[END_REF] additionally selects a current model as a dynamic policy component to determine the current semantics. Dynamic mandatory access control [START_REF] Bell | Secure computer systems: A mathematical model, volume II[END_REF] offers to adapt security labels assigned to objects as a classification like "high-water marks", where classifications can be seen as a part of the access control policy. Many further examples stem from the dynamic control of workflows. Control of probabilistic inferences [START_REF] Chen | Protection of database security via collaborative inference detection[END_REF] uses a Bayesian network, which is updated after returning some piece of information to a user; the current network reflects the confidentiality requirements still to be enforced.

We demonstrated in detail that the proposed policy-adaption approach can be employed effectively for a specific situation of Controlled Query Evaluation, and we also indicated how to implement this approach such that inference control can be performed efficiently for special cases. It would be worthwhile to also consider more expressive situations, including incomplete instances and open queries. Such extensions will challenge us to transfer the current considerations to the more complex modal first-order logic. Seen from a even more general perspective, the ultimate goal of further efforts should be the following: We should aim at finding suitable combinations of the view-based approach and the policyadaption based appraoch, in order to achieve the best possible efficiency for specific situations; and maybe we could further aim at constructing an optimizer that automatically recognizes the best combination for a current situation.

Fig. 1 .

 1 Fig. 1. Initial and subsequent states of a data structure for dynamic policy adaption

Theorem 1 .

 1 The function cqe pol as defined by the Protocol for Policy Adaption preserves confidentiality in the sense of Def. 2.

5 .s

 5 (exists Ψs )( Ψs = { Ψs,1 , . . . , Ψs,m } ∈ sec ∅ and (for all k )(for all "non-contradictory" D ∈ D i-1 ) (exists Ψs,r )( Ψs,r ∈ Ψs and l β k( D),l ∧ χk |= Ψs,r )). We have employed the correspondance between disjuncts of hist i-1 and branches, where k( D) corresponds to D. 6. (exists Ψs )( Ψs ∈ sec ∅ and (for all k )(for all "non-contradictory" D ∈ D i-1 ) is the version of Ψs in the branch sec[ D].

Table 1 .

 1 A converted and then stepwise adapted confidentiality policy

	Description and Branch	Disjuncts (given prime implicants)	Disjuncts (additional prime implicants)
	sole element (original) sole element (after answer a1)	a1 ∧ ¬a3 ∧ ¬a4 a1 ∧ ¬a2 ∧ a4 a2 ∧ a3 ∧ a4 ¬a1 ∧ a2 ∧ ¬a3 ¬a3 ∧ ¬a4 ¬a2 ∧ a4 a2 ∧ a3 ∧ a4 (complementary)	a2 ∧ ¬a3 ∧ ¬a4 a1 ∧ ¬a2 ∧ ¬a3 a1 ∧ a3 ∧ a4 ¬a1 ∧ a2 ∧ a4 a2 ∧ ¬a3 ∧ ¬a4 ¬a2 ∧ ¬a3 a3 ∧ a4 (complementary)
	sole element (after answer a1 and subsumption)	¬a3 ∧ ¬a4 ¬a2 ∧ a4 (subsumed) (complementary)	(subsumed) ¬a2 ∧ ¬a3 a3 ∧ a4 (complementary)
	sole element (after answers a1, ¬a2 ∨ a3) for branch {¬a2}	¬a3 ∧ ¬a4 a4 (subsumed) (complementary)	(subsumed) ¬a3 a3 ∧ a4 (complementary)
	sole element (after answers a1, ¬a2 ∨ a3) for branch {a3}	(complementary) ¬a2 ∧ a4 (subsumed) (complementary)	(subsumed) (complementary) a4 (complementary)
	sole element (after answers a1, ¬a2 ∨ a3 and subsumption) for branch {¬a2} sole element (after answers a1, ¬a2 ∨ a3 and subsumption) for branch {a3}	(subsumed) a4 (subsumed) (complementary) (complementary) (subsumed) (subsumed) (complementary)	(subsumed) ¬a3 (subsumed) (complementary) (subsumed) (complementary) a4 (complementary)

  L df ⊆ L propositional sentences in disjunctive form; Lpi ⊆ L df propositional sentences that consist of all their prime implicants; L li ⊆ Lpi literals; Lim ⊆ L df implicants (conjunctions of literals over distinct atoms); C ⊆ finite ℘L declared confidentiality policies; M ⊆ finite ℘℘Lim converted confidentiality policies as multisets of "identified policy elements"; B ⊆ finite M × ℘L li policy branches; //written as imsets[liset]; Q ⊆ L queries. ∈ sec ∅ do convert Ψ such that it becomes the disjunction of all its prime implicants;foreach Ψ ∈ sec ∅ do replace Ψ having form Ψ1 ∨ . . . ∨ Ψm by the representing set {Ψ1, . . . , Ψm}Ψ ; 3. psecb 0 := {sec ∅ [∅]}; // only one policy branch of form {{. . . }, . . . , {. . . }}[∅] 4. process prior like a sequence of queries. //not elaborated for lack of space Φi into disjunctive form Φi,1 ∨ . . . ∨ Φi,n; 2. ansi := if Φi violates psecb i-1 or ¬Φi violates psecb i-1then mum else eval * (Φi)(db); 3. if ansi = Φi (let Φi = Φi,1 ∨ . . . ∨ Φi,n) then psecb i := ∅; foreach disjunct Φi,j of Φi do litj := {ϕ | ϕ occurs in Φi,j}; copyj := {sec[D ∪ litj] | sec[D] ∈ psecb i-1 };foreach literal ϕ of Φi,j do perform policy adaption for ϕ and copyj;psecb i := psecb i ∪ copyj elseif ansi = ¬Φi (let ¬Φi = ¬Φi,1 ∧ . . . ∧ ¬Φi,n) then psecb i := psecb i-1 ; foreach conjunct ¬Φi,j of ¬Φi (let ¬Φi,j = ϕ1 ∨ . . . ∨ ϕ k ) do copy := ∅; foreach literal ϕ l of ¬Φi,j do copy l := {sec[D ∪ {ϕ l }] | sec[D] ∈ psecb i };perform policy adaption for ϕ l and copy l ; copy := copy ∪ copy l ; psecb i := copy. Φi, i.e., violation test is performed for current query if there exists a branch sec[D] of policy psecb and there exists a disjunct Φj of (negated) query Φ such that Φj ∧ ϕ∈D ϕ is not contradictory //guaranteed if Φ = eval * (Φi)(db) and there exists {. . .} Ψ ∈ sec ∅ such that // Ψ "uniformly identifies" a policy element for all branches sec[D] of policy psecb and for all disjuncts Φj of (negated) query Φ such that Φj ∧ ϕ∈D ϕ is not contradictory there exists a disjunct Ψr ∈ {. . .} Ψ ∈ sec such that Φj |= Ψr (by subsumption) then return true (violation) else return false (no violation). subprotocol: adaption (for literal and policy copy). input: ϕ : L li ; var copy : B; // copy is used as input-and-output parameter method: // modify copy as followsforeachpolicy branch secj[Dj] ∈ copy do 1. if ¬ϕ ∈ Dj then delete branch secj[Dj] else foreach {χ1, . . . , χr}Ψ ∈ secj do foreach χ ∈ {χ1, . . . , χr}Ψ do if ϕ occurs in χ then drop ϕ from χ; if ¬ϕ occurs in χ then remove χ from {χ1, . . . , χr}Ψ ; foreach distinct χ1, χ2 ∈ {χ1, . . . , χr}Ψ do if χ1 |= χ2 (by subsumption) then remove χ1 from {χ1, . . . , χr}Ψ ; 2. foreach {χ1, . . . , χr}Ψ , { χ1, . . . , χr} Ψ ∈ secj with Ψ = Ψ do if χ1 ∨ . . . ∨ χr |= χ1 ∨ . . . ∨ χr then replace {χ1, . . . , χr}Ψ by ∅Ψ // consider ∅Ψ as removed.

	Protocol for Policy Adaption. types. L propositional sentences; subprotocol: initialization. input: psec : C; prior : ℘L; method: 1. sec subprotocol: generation (of answer and policy). input: Φi : L; psecb i-1 : B; method: input: Φ : L; psecb : B; 1. convert subprotocol: violation (test). method: convert Φ into disjunctive form; //nothing to do if Φ =

∅ := psec; 2. modify sec ∅ as follows:

foreach Ψ

This work has been performed within the framework of the Collaborative Research

Center "Providing Information by Resource-Constrained Data Analysis", supported by the Deutsche Forschungsgemeinschaft under grant SFB 876/A5.


Wenliang Du
email: wedu@syr.edu

Xi Tan

Tongbo Luo

Karthick Jayaraman

Zutao Zhu

Re-designing the Web's Access Control System (Extended Abstract)

Keywords:

The Web is playing a very important role in our lives, and is becoming an essential element of the computing infrastructure. With such a glory come the attacks-the Web has become criminals' preferred targets. Web-based vulnerabilities now outnumber traditional computer security concerns. Although various security solutions have been proposed to address the problems on the Web, few have addressed the root causes of why web applications are so vulnerable to these many attacks. We believe that the Web's current access control models are fundamentally inadequate to satisfy the protection needs of today's web, and they need to be redesigned. In this extended abstract, we explain our position, and summarize our efforts in redesigning the Web's access control systems.

Introduction

The Web is playing a very important role in our lives, and is becoming an essential element of the computing infrastructure. Because of its ubiquity, the Web has become attackers' preferred targets. Web-based vulnerabilities now outnumber traditional computer security concerns [START_REF] Christey | Vulnerability type distributions in cve (version 1.1)[END_REF]4]. SQL injection, cross-site scripting (XSS), and cross-site request forgery are among the most common attacks on web applications. A recent report shows that over 80 percent of websites have had at least one serious vulnerability, and the average number of serious vulnerabilities per website is 16.7 [26].

Attacks on the Web are quite unique, compared to the attacks on the traditional computer systems and networks. From the top 10 list of web attacks recently release by OWASP [START_REF]The ten most critical web application security risks[END_REF], we can tell that these attacks, to a large degree, are attributed to the unique architecture of web applications. In general, the most common structure for web applications is three-tiered [START_REF] Parno | CLAMP: Practical prevention of large-scale data leaks[END_REF]: presentation, application, and storage. The web browser belongs to the first tier, presentation. The web server, using technologies like PHP, ASP, ASP.NET, etc., is the middle tier, which controls the application logic. The database is in the storage tier. Therefore, a typical web application consists of three major components: contents (static and dynamic, such as Javascript code) for the presentation tier, code for the application tier, and interactions with the database.

Various security solutions have been proposed to address the problems on the Web [1,[START_REF] Crockford | ADSafe[END_REF][START_REF] Dalton | Nemesis: Preventing authentication & access control vulnerabilities in web applications[END_REF][START_REF] Jackson | Protecting browser state from web privacy attacks[END_REF][START_REF] Jayaraman | Escudo: A fine-grained protection model for web browsers[END_REF][START_REF] Karlof | Dynamic pharming attacks and locked same-origin policies for web browsers[END_REF][START_REF] Livshits | Using web application construction frameworks to protect against code injection attacks[END_REF][START_REF] Meyerovich | Conscript: Specifying and enforcing finegrained security policies for javascript in the browser[END_REF][START_REF] Parno | CLAMP: Practical prevention of large-scale data leaks[END_REF][START_REF] Patil | Towards fine-grained access control in javascript contexts[END_REF]; although some of them are quite effective in defending against certain specific type of attacks, few have answered the questions "why is the Web so vulnerable to these many attacks" and "what are the root causes of these problems". If we do not address the root causes, we may be able to address some known problems today, but more and more problems may arise in the future, as the Web is still evolving and new features are being introduced from time to time. We need to study the fundamental problems of why web applications are so vulnerable, and develop solutions to address these fundamental problems, instead of developing point solutions to fix each specific attack.

Most of the vulnerabilities appear to be caused by the mistakes in the programs, but, when we look deeper and think about why the developers make such mistakes, we realize that the real problem is the underlying access control architecture: because of the inadequacy of the access control support from the underlying architecture, developers are forced to implement additional access control in their programs. History has told us that asking average developers to implement access control is dangerous, and that being able to build software systems does not necessarily mean being able to build the security part correctly.

Let us look retrospectively at how the access control in operating systems has been evolved to counter the ever-increasing threats. We can see a clear trend: access control has evolved from the simple access control list, to capability-based access control in Linux [START_REF] Hallyn | Linux capabilities: making them work[END_REF] and Solaris [START_REF]White paper: Trusted Solaris 8 operating environment[END_REF], and to the support of more complicated Mandatory Access Control (MAC) models in SELinux [START_REF]Security-Enhanced Liunx[END_REF] and Windows Vista [START_REF] Conover | Analysis of the windows vista security model[END_REF]. These sophisticated access control mechanisms free application developers from building all the access control in their own applications; they can rely on the operating system to do most of the access control work.

Unfortunately, web application developers do not have such a good luck, because the access control mechanisms in the web architecture are quite rudimentary. Although the Web has been evolved quite significantly, with new features being added and new types of data incorporated, the underlying protection model is basically the same as that in the early days, and it has become much insufficient for the Web today. To make up for the insufficiency of the underlying protection model, application developers have to include a lot of access control logics in their programs. This is the exact task that the operating systems strive to free developers from. While much work has been done to secure web applications without changing the fundamental access control model, we take a bold and significantly different position in our research:

Our position: We believe that the current access control models of the web architecture are fundamentally inadequate for the Web; they need to be redesigned to address the protection needs of the current Web. A well-designed access control model can simplify application developers' tasks by enforcing much of the access control within the model, freeing developers from such a complicated and error-prone task.

To understand our position, we need to understand the access control architecture underlying web applications. Conceptually, the access control in web applications can be divided into two parts: browser-side and server-side access control. We will discuss them in the next section.

Current Access Control in the Web

Browser-side access control

Web applications have evolved to become highly interactive applications that execute on both the server and client. As a result, web pages in modern applications are no longer simple documents-they now comprise highly dynamic contents that interact with each other. In some sense, a web page has now become a "system": the dynamic contents are programs running in the system, and they interact with users, access other contents both on the web page and in the hosting browser, invoke the browser APIs, and interact with the programs on the server side. To provide security, web browsers adopt an access control model called Same Origin Policy (SOP). SOP prevents the active contents belonging to one origin from accessing the contents belonging to another origin, but it gives all the active contents from the same origin the same privileges.

Unfortunately, today's web pages no longer draw contents from a single source; contents are now derived from several sources with varying levels of trustworthiness. Contents may be included by the application itself, derived from user-supplied text, or from partially trusted third parties. Web applications merge these contents into web pages, which are then sent to users' browsers at their requests. During parsing, rendering, and execution inside the browser, entities (dynamic and static) in web pages can both act on other entities or be acted upon-in classic security parlance, they can be instantiated as both principals and objects. These principals and objects are only as trustworthy as the sources from which they originate.

With the SOP model, all these contents have the same privileges, because once embedded into a web page, from the browser's perspective, they are indeed from the same origin, and will be treated the same. This is a limitation of the SOP model. Since SOP cannot enforce access control based on contents' actual originating sources, web applications have to implement the control at the server side, even though the access actually takes place at the browser side. The goal of this access control approach is to conduct checking and filtering at the server side before merging the contents into web pages, thereby preventing specific, known attacks from even initiating an action within the generated web pages. For example, to defeat the cross-site scripting attack, one can filter out the code from the contents that are from untrusted sources.

Conducting browser-side access control at the server side has a number of limitations. First, doing the filtering and validation has proven to be difficult; many vulnerabilities are caused by the errors in such a process [START_REF] Grossman | The impending threat and the best defense[END_REF][START_REF] Hansen | XSS cheat sheet[END_REF][START_REF] Kamkar | The samy worm story[END_REF]. For example, despite the fact that Myspace had implemented many filtering rules, the Samy worms still found the ways to inject unauthorized Javascript code into users' profiles [START_REF] Kamkar | Technical explanation of the myspace worm[END_REF]. Second, if web applications need to run some third-party code (e.g. advertisement and client-side extensions) on a web page, but want to put a limitation on the code (e.g. disallow the access to cookies), it will be difficult, if possible at all, for input validation and filtering to achieve this goal on the server side. In a recent event (September 2009), an unknown person or group, posing as an advertiser, sneaked a rogue advertisement onto New York Times' pages, and successfully compromised the integrity of the publisher's web application using a malicious Javascript program [START_REF] Vance | Times web ads show security breach[END_REF]. Third, since the accesses actually take place at the browser side, the server side is fundamentally the wrong place to control these accesses. Access control should be conducted at the run time, when the access is already initiated; this way, we will have all the contexts for access control, including principals, objects, and the condition of the environment.

Therefore, we strongly believe that the browser-side access control should be put back to its proper location, namely, in browsers. This cannot be achieved with the current SOP access control model; a new access control model needs to be developed for web browsers.

Server-side access control

On the server side, access control is primarily based on sessions. When a user logs into a web application, the server creates a dedicated session for this user, separating him/her from the other users. Sessions are implemented using session cookies; as long as a request carries a session cookie, it will be given all the privileges associated with that session. Namely, within each session, all requests are given the same privileges, regardless of whether they are initiated by first-party or third-party contents, from client-side or server-side extensions, or from another origin. We refer to this access control as the "same-session" policy.

Such a single level of granularity, being sufficient for the earlier day's Web, becomes inadequate to address the protection needs of today's Web. The Web, initially designed for primarily serving static contents, has now evolved into a quite dynamic system, consisting of contents and requests from multiple sources, some more trustworthy than others. For example, nowadays, many web applications include client-side extensions, i.e., they include links to third-party code or directly include third-party code in their web pages. Examples of client-side extensions include advertisements, Facebook applications, iGoogle's gadgets, etc. Their contents, containing JavaScript code, can be very dangerous if they are vulnerable or malicious, Unfortunately, the current session-based access control at the web server cannot treat these third-party contents differently. In the current access control systems, it is very difficult to allow the requests from the same web page to access the same session, while preventing some of them from invoking certain server-side services. To achieve such a distinction, applications have to implement their own ad hoc protection logic, such as asking users to confirm their actions, embedding tokens in hidden fields, etc.

The fundamental cause of the above problem is the granularity of a session: it is too coarse. The Web has become more and more complicated, and its client-side contents are no longer uniformly trusted, so requests initiated by these contents are not uniformly trusted either. Therefore, giving all the requests within the same session the same privileges cannot satisfy the protection needs of today's Web anymore. In order not to ask application developers to bear the complete responsibility of implementing those protection needs, we need a better server-side access control system.

Our Approaches

Our approach is inspired by the access control in operating systems. Operating systems consider the implementation of access control as their own responsibility, instead of the responsibility of their applications. This is for security reasons, because OS needs to guarantee that all the accesses are mediated; relying on applications to enforce access control simply cannot achieve this goal. Unfortunately, in web applications, because of the lack of appropriate access control models, web applications have to implement their own access control mechanisms, which tend to be error prone: if they miss some places, loopholes may be created.

To satisfy the needs of access control, most operating systems have built in some basic access control models, such as the ACL model in most OSes, an integrity-focused MAC model since Windows Vista [START_REF] Conover | Analysis of the windows vista security model[END_REF], and a fine grained MAC model in SELinux [START_REF]Security-Enhanced Liunx[END_REF]. With these models, user applications do not need to worry about implementing some of the access controls if they can be covered by the models. For example, if an application system's protection needs can be satisfied by the underlying ACL model, it only needs to properly configure all the objects in the system, and then relies on the operating system to enforce the access control. If an application system needs to enforce a specific MAC policy in SELinux, it only needs to configure its system, and then lets SELinux to enforce the access control; the configuration in this case includes setting up the security policies and labeling the subjects and objects.

The benefit of replacing implementation with configuration can be summarized briefly in the following: First, from the implementation perspective, configuring a system is easier than implementing a system, and is thus less error-prone (although errors are still possible). Second, from the verification perspective, because configuration is usually defined based on logics that are much simpler than programming logics, verifying configuration is also much easier than verifying programs. Third, from the errorresistance perspective, configuration is safer: any missing configuration can fall back to a safe default; however, there is no "safe default" if an access control checking is missing. When a web application has over 1000 security checks, missing a few checks is not uncommon [START_REF] Yip | Improving application security with data flow assertions[END_REF]. Fourth, configuration allows web applications to put the access control in the place where the access actually takes place.

Motivated by the successful practice in operating systems and the benefit of configuration, we set out to investigate whether we can develop a better access control system for the Web, such that we can take some of the access control enforcement logic out of web applications, and replace them with configuration, a much easier task. The enforcement will be done by the access control system that we develop for browsers, servers, and databases. We summarize our ongoing efforts in the following.

Browser-side access control: We have developed two access control models for web browsers: Escudo [START_REF] Jayaraman | Escudo: A fine-grained protection model for web browsers[END_REF] and Contego [START_REF] Luo | Contego: Capability-based access control for web browsers[END_REF]. Escudo proposes a ring access control model for web browsers. This model allows web applications to put webpage contents in different rings, based on their trustworthiness: Elements accessible only to more trustworthy principals or from more trusted sources are placed in higher privileged rings. Ring assignments are carried out at the server side, because only the server-side code knows how trustworthy the contents are. Assigning ring labels to contents is called "configuration", and once a web page is "configured", the browser can enforce access control based on the configuration and Escudo's security policies: contents in the lower-privileged rings cannot access the contents in the higher-privileged rings. We implemented Escudo in a browser called Lobo [START_REF] Solorzano | The Lobo Project[END_REF].

To provide an even finer granularity, we have developed Contego, a capability-based access control for web browsers. Contego divides the action privileges (e.g. accessing cookies, sending AJAX requests, etc) into small "tokens" (called capabilities). A principal needs to possess the corresponding tokens if it wants to perform certain actions. For example, a Javascript code within a web page will not be able to send AJAX requests if it is not assigned the AJAX-request token. Using these fine-grained capabilities, web applications can assign the least amount of privileges to principals. We implemented Contego in the Google Chrome browser.

Server-side access control: We have developed a fine-grained server-side access control system, which can assign different privileges to the requests in the same session, based on their trustworthiness. The new access control system is called Scuta [START_REF] Tan | SCUTA: A server-side access control system for web applications[END_REF], which is a backward-compatible access control system for web application servers. Extending Escudo's ring model to the server, Scuta labels server-side data (e.g. tables in database) and programs (functions, classes, methods, or files) with rings, based on their protection needs. Programs in a lower-privileged ring cannot access data or code in a higher-privileged ring.

Scuta divides a session into multiple subsessions, each mapped to a different ring. Requests from a more trustworthy region in a web page belong to a more privileged subsession. Requests belonging to subsession k are only allowed to access the serverside programs and data in ring k and above (numerically). With the subsession and ring mechanisms, server-side programs can treat the requests in the same session differently, based on the trustworthiness of their initiators, and thus provide access control at a finer granularity. Subsessions in Scuta correspond to the rings in Escudo, i.e., requests initiated from Escudo ring k in a web page is considered as belonging to subsession k, and can thus access the corresponding server-side resources.

To demonstrate the effectiveness of Scuta, we have implemented Scuta in PHP, a widely adopted platform for web applications. We have conducted comprehensive case studies to demonstrate how Scuta can be used to satisfy the diversified protection needs in web applications.

Summary

We strongly believe that the access control systems in the current Web infrastructure is fundamentally inadequate to satisfy the protection needs of today's Web, and they have, directly and indirectly, contributed to the dire situation in web applications. It is time to think about whether we can design a better and backward-compatible access control system, instead of developing fixes to patch the existing one in order to defeat certain specific attacks. The web technology is still evolving, so a good design should not only be able to satisfy today's needs, it should also be extensible to satisfy the unknown protection needs that will inevitably come up during the technology evolution. In this extended abstract, we have summarized our pursuit in building a better access control system for the Web.

This work was supported by Award No. 1017771 from the US National Science Foundation.

Acknowledgment

Several other people have also participated in this research, including Amit Bose, Steve Chapin, Tzvetan Devnaliev, Hao Hao, Apoorva Iyer, Balamurugan Rajagopalan, Karthick Soundararaj, Shaonan Wang, and Yifei Wang. We would like to acknowledge their contributions.