Joachim Biskup

Sven Hartmann
email: sven.hartmann@tu-clausthal.de

Sebastian Link
email: s.link@auckland.ac.nz

Jan-Hendrik Lochner

Torsten Schlotmann

Signature-Based Inference-Usability Confinement for Relational Databases under Functional and Join Dependencies

Keywords: a priori knowledge, confidentiality policy, functional dependency, inference control, inference-usability confinement, interaction history, join dependency, refusal, relational database, select-project query, inference signature, SQL, template dependency

Inference control of queries for relational databases confines the information content and thus the usability of data returned to a client, aiming to keep some pieces of information confidential as specified in a policy, in particular for the sake of privacy. In general, there is a tradeoff between the following factors: on the one hand, the expressiveness offered to administrators to declare a schema, a confidentiality policy and assumptions about a client's a priori knowledge; on the other hand, the computational complexity of a provably confidentiality preserving enforcement mechanism. We propose and investigate a new balanced solution for a widely applicable situation: we admit relational schemas with functional and join dependencies, which are also treated as a priori knowledge, and select-project sentences for policies and queries; we design an efficient signature-based enforcement mechanism that we implement for an Oracle/SQL-system. At declaration time, the inference signatures are compiled from an analysis of all possible crucial inferences, and at run time they are employed like in the field of intrusion detection.

Introduction

Inference control for information systems in general and relational databases in particular is a mechanism to confine the information content and thus the usability of data made accessible to a client to whom some piece(s) of information should be kept confidential. Thus inference control aims at protecting information rather than just the underlying data, as achieved by traditional access control or simple encryption. Though protection of information is a crucial requirement for many public and commercial applications, the actual enforcement is facing great challenges arising from conceptual and computational problems.

On the conceptual side, among others the following main factors have to be considered: a client-specific and declaratively expressed confidentiality policy which might be balanced with availability demands; an assumption about the client's a priori knowledge regarding the information managed by the information system, which will include schema information in many cases; the client's postulated system awareness regarding the semantics of both the underlying information system and the monitoring control mechanism.

On the computational side, the high runtime complexity is a major concern. In fact, the fundamental semantics of a well-designed information system can be defined in terms of an appropriate logic. In particular, a relational database comes along with the relational calculus for querying and some class of dependencies (semantic constraints) for declaring schemas [START_REF] Abiteboul | Foundations of Databases[END_REF]. Thus, data managed by such a system can be interpreted as sentences in the underlying first-order logic. Accordingly, confining the usability of data comprises the task of monitoring all options for inferring implied (entailed) sentences from the sentences available to a client, at any point in time while the client is interacting with the system. Unfortunately, as well-known from the discipline of theorem proving, the computational treatment of entailment problems might be inherently complex.

Consequently, a major research task regarding information protection is to identify practically relevant situations that still enable a reasonably efficient enforcement of suitably restricted conceptual requirements. In our previous work [START_REF] Biskup | Chasing after secrets in relational databases[END_REF] we already introduced and theoretically analyzed the following situation as highly promising: Using the refusal approach, where harmful correct answers are replaced by a refusal notification denoted by mum, we protect select-project sentences under closed (yes/no-)select-project queries evaluated for relational database instances of a schema with functional and join dependencies. In the present article, we present a successful elaboration of the proposed approach:

-Based on the theoretical analysis, we have designed, implemented and investigated a practical, SQL-conforming signature-based enforcement method. -The inference signatures are compiled from an analysis of all crucial inferences that are possible for the given situation, and later on monitored like in the field of intrusion detection.

To set up a larger perspective, we observe that the conceptual requirements of inference-usability confinement can be captured by an invariant that a control mechanism has to guarantee for all sequences of query-response interactions. Such an invariant might have several forms, which are equivalent under careful formalizations [START_REF] Halpern | Secrecy in multiagent systems[END_REF][START_REF] Biskup | Policy-based secrecy in the Runs & Systems Framework and controlled query evaluation[END_REF]. E.g., the invariant might require that for any sentence in the confidentiality policy, based on his current knowledge, which results from the a priori knowledge and previous interactions, and his system awareness, the client cannot exclude that this sentence is not valid in the instance; the client does not know that this sentence is valid in the instance.

To enforce such an invariant, a control mechanism has to inspect each query considered as an interaction request and the answer to be returned whether or not they satisfy an adequate control condition. Clearly, a necessary control condition is that the current knowledge updated with the answer will not entail any sentence in the confidentiality policy. Unfortunately, however, this condition is not sufficient in general, since it neglects the impact of a client's system awareness, which might enable so-called meta-inferences. Thus, in general, we have to strengthen this condition to become sufficient, while preferably remaining to be necessary for the sake of availability. Moreover, as far as achievable, checking a sufficient (and necessary) control condition should be computationally feasible.

Several sufficient and "reasonably necessary" control conditions for comprehensive and general situations have been proposed in the past [START_REF] Biskup | Inference-usability confinement by maintaining inference-proof views of an information system[END_REF], which, however, inevitably tend to be infeasible in the worst case. Moreover, dedicated narrower situations have been investigated to find effective control conditions that are also efficiently testable. The contribution of the present article is particularly related to the following situations, all of which consider the refusal approach for relational databases, assuming that the client knows the confidentiality policy.

-Situation 1. As long as decidability is achieved, any a priori knowledge, confidentiality policy and closed (yes/no-)queries (of the relational calculus) are admitted. For the confinement, while maintaining and employing a log file that represents the a priori knowledge and the answers to previous queries, we have to ensure that adding neither the correct answer to the current query nor the negation of the correct answer will be harmful; additional refusals for harmful negations of correct answers guarantee that an observed "refused" answer mum cannot be traced back to its actual cause by exploiting the system awareness [START_REF] Biskup | Lying versus refusal for known potential secrets[END_REF]. -Situation 2. The a priori knowledge may only comprise a schema declaration with functional dependencies that lead to Boyce-Codd normal form with a unique minimal key. Confidentiality policies are restricted to select-project sentences of a special kind referring to "facts", and queries are restricted to arbitrary select-project sentences. For the confinement, it suffices to ensure that the query sentence does not "cover" any policy element [START_REF] Biskup | Reducing inference control to access control for normalized database schemas[END_REF]. -Situation 3. The a priori knowledge may only comprise a schema declaration with functional dependencies. Confidentiality policies are restricted to selectproject sentences, whereas queries must be closed select-queries. For the confinement, it suffices to ensure that the query sentence does not "cover" any policy element [START_REF] Biskup | Optimization of the controlled evaluation of closed relational queries[END_REF]. -Situation 4. The a priori knowledge may only comprise a schema declaration with functional dependencies and full join dependencies (without any further restrictions). Confidentiality policies and queries are restricted to select-project sentences. For the confinement, we have to ensure two conditions: (1) The query sentence does not "cover" any policy element. (2) Previous positive answers together with a positive answer to the current query do not "instantiate" any template dependency implied by the schema dependencies and "covering" an element of the confidentiality policy [START_REF] Biskup | Chasing after secrets in relational databases[END_REF]. In the present article, we will show how this requirement can be converted into an efficient enforcement mechanism.

Notably, Situations 2 to 4 postulate that the client's a priori knowledge only comprises schema declarations. Accordingly, if additional a priori knowledge was assumed, further potential sources of inferences should be considered, and thus the respective confinement method would have to be appropriately enhanced.

The control conditions sketched so far are devised to be used dynamically at run time to detect current options for crucial entailments. To avoid the runtime overhead, one might prefer a static approach [START_REF] Biskup | A sound and complete model-generation procedure for consistent and confidentiality-preserving databases[END_REF]: We then interpret the confidentiality policy and the a priori knowledge as constraints to be satisfied by an alternative instance that minimally distorts the actual instance, precompute a solution to such a constrained optimization problem, and let the solution instance be queried by the client without any further control.

We might also follow a mixed approach that suitably splits the workload among (1) some precomputations before the client is involved at all, (2) appropriate dynamic control operations after receiving a specific client request and before returning an answer, and (3) some follow-up adaptation actions between two requests [START_REF] Biskup | History-dependent inference control of queries by dynamic policy adaption[END_REF]. The present article follows a mixed approach for the specific relational framework of [START_REF] Biskup | Chasing after secrets in relational databases[END_REF] described as Situation 4 above; roughly outlined, our new signature-based enforcement mechanism consists of a two-phase protocol:

-At declaration time, we compile inference signatures as representatives of "forbidden structures" in the sense of [START_REF] Biskup | Chasing after secrets in relational databases[END_REF]: "instantiations" of template dependencies implied by the schema dependencies and "covering" a policy element. -At run time, we monitor these inference signatures for the actual queries.

Formal Framework

In this section we summarize our formal framework and restate the theorem that justifies our signature-based enforcement mechanism, referring the reader to [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Biskup | Chasing after secrets in relational databases[END_REF] for more details. Examples can be found in the next section.

A relation schema RS = R, U, Σ consists of a relation symbol R, a finite set U of attributes, and a finite set Σ of dependencies (semantic constraints). Σ comprises either functional dependencies, assumed to be a minimal cover, or full join dependencies, or both kinds of dependencies. An instance r is a finite dependency-satisfying Herbrand interpretation of the schema, considering the relation symbol as a predicate. A tuple is denoted by µ = R(a 1 , . . . , a n ) where n = |U| and a i ∈ Const, an infinite set of constants. If µ is an element of r, we write r |= M µ. More generally, |= M denotes the satisfaction relation between an interpretation and a sentence. The corresponding notion of logical implication (entailment) between sentences is denoted by |=.

Let A, B ⊆ U be attribute sets. A relation r over U satisfies the functional dependency A → B if any two tuples that agree on the values of attributes in A also agree on the values of the attributes in B.

Let C 1 , . . . , C l ⊆ U be attribute sets such that C 1 ∪ . . . ∪ C l = U. A relation r over U satisfies the (full) join dependency [C 1 , . . . , C l ] if whenever there are tuples µ 1 , . . . , µ l in r with µ

i [C i ∩ C j ] = µ j [C i ∩ C j ] for 1 ≤ i, j ≤ l, there is also a tuple µ l+1 in r with µ l+1 [C i ] = µ i [C i ] for 1 ≤ i ≤ l.
Join dependencies are a special case of template dependencies. A template dependency TD[h 1 , . . . , h l |c] over U has one or more hypothesis rows h 1 , . . . , h l and a conclusion row c. Each row consists of abstract symbols (best seen as variables), one symbol per attribute in U. A symbol may appear more than once but only for one attribute, i.e., in a typed way. For t and t denoting tuples or rows, respectively, over U, ag(t, t ) := {A | A ∈ U and t(A) = t (A)} is the agree set of these tuples or rows, respectively. The aggregated agree sets of the conclusion ∪ l j=1 ag(c, h j ) form the scheme of the template dependency. A symbol occurring in the conclusion for an attribute A in the scheme is often called "distinguished" (free variable) and denoted by a A . Any other symbol in the template dependency is often called "nondistinguished" (existentially quantified variable) and denoted by b i , where each such symbol gets a different index i.

A relation r over U satisfies the template dependency TD[h 1 , . . . , h l |c] if whenever there are tuples t 1 , . . . , t l in r with ag(h i , h j ) ⊆ ag(t i , t j ) for all i, j ∈ {1, . . . , l} there is also a tuple t in r with ag(c, h i ) ⊆ ag(t, t i ) for i = 1, . . . , l.

A template dependency TD[h 1 , . . . , h l |c] is called (hypothesis-)minimal with respect to Σ if dropping a full hypothesis row h i or replacing any symbol in a hypothesis by a new symbol, different from all others -thus (potentially) deleting an equality condition -would result in a template dependency that is not implied by Σ. Moreover, a minimal template dependency is called (conclusion-)maximal with respect to Σ if the following additionally holds: if we replace a symbol in the conclusion row c that so far is not involved in any agree set with a hypothesis by another symbol that already occurs in some hypothesis, then we would obtain a template dependency that is not implied by Σ. Finally, a template dependency enjoying both optimization properties is called a basic implication of Σ.

Queries and elements of a confidentiality policy psec, called potential secrets, are expressed in a fragment of the relational calculus, using a set of variables Var . This fragment is given by the language L of existential-R-sentences, or select-project sentences which are sentences (closed formulas) of the form (∃X 1 ) . . .

(∃X l )R(v 1 , . . . , v n ) with 0 ≤ l ≤ n, X i ∈ Var , v i ∈ Const ∪ Var , {X 1 , . . . , X l } ⊆ {v 1 , . . . , v n }, and v i = v j if v i , v j ∈
Var and i = j; these properties and the closedness imply that {X 1 , . . . , X l } = {v 1 , . . . , v n }∩Var . For Φ ∈ L , we define the scheme P of Φ as the set of attributes for which a constant appears. For a sentence in L let its corresponding "generalized tuple" denote the sentence without its prefix of existential quantifiers. In this case we think of the variables in the generalized tuple as the null value "exists but unknown".

A sentence (generalized tuple) Φ is defined to cover a sentence (generalized tuple) Ψ if every constant c that appears in Ψ appears in Φ at the same position. The following equivalence can be easily verified: Φ covers Ψ if and only if Φ |= Ψ .

Restating Theorem 2 of [8] below, we specify a "forbidden structure" an instantiation of which is necessary for any violation of a policy element by ex-ploiting the a priori knowledge about the dependencies. Additionally, Theorem 1 of [START_REF] Biskup | Chasing after secrets in relational databases[END_REF] indicates that an occurrence of such a structure is also sufficient for exploiting the dependencies. Accordingly, we obtain a necessary and "reasonably sufficient" control condition by avoiding both an immediate violation by "covering" a potential secret and an instantiated "forbidden structure"; the latter consists of an implied template dependency whose scheme comprises the scheme of a potential secret, while the schemes of the query answers "uniformly cover" the hypotheses. Our mechanism will be based on that control condition.

Theorem 1 (forbidden structures, necessary for a violation by exploiting the dependencies). Let RS = R, U, Σ be a relation schema where the dependency set Σ consists of functional and full join dependencies, and r an instance of RS. Let Ψ ∈ L be a potential secret with scheme P ⊆ U, and Φ 1 , . . . , Φ l ∈ L queries with schemes F 1 , . . . , F l such that:

1. Φ i |= Ψ , for i = 1, . . . , l, i.e., all queries do not cover the potential secret; 2. r |= M Φ i , for i = 1, . . . , l, i.e., all queries are true in the instance r; 3. Σ ∪ {Φ 1 , . . . , Φ l } |= Ψ , i.e., the answers violate the confidentiality policy.

Then there exists a nontrivial template dependency TD[h 1 , . . . , h l |c] implied by Σ such that P = ∪ l j=1 ag(c, h j ) and ∪ j∈{1,...,l} {i} ag(h i , h j ) ⊆ F i , for i = 1, . . . , l.

Examples

We will outline the fundamental features of the signature-based enforcement mechanism by means of two examples. Though only dealing with functional dependencies specifying a key, the first example is beyond the scope of the Situations 2 and 3 sketched before and thus cannot be treated by the mechanisms of [START_REF] Biskup | Reducing inference control to access control for normalized database schemas[END_REF][START_REF] Biskup | Optimization of the controlled evaluation of closed relational queries[END_REF]. The second example introduces join dependencies as a priori knowledge.

Example 1. At declaration time, we consider the following items: a relation schema RS = R, U, Σ with attribute set U = {K, A, B} and dependencies Σ = {K → A, K → B}, i.e., attribute K is the unique minimal key; an instance

r = {R(c K , c A , c B ), R(c K , c A , c B )}, where c K , cK , c A and c B are

constants in

Const; and a single potential secret Ψ = (∃X K )R(X K , c A , c B ). We will compile inference signatures in four steps.

In step 1, we see that Σ entails the template dependency

td := TD[ a K a A b 1 , a K b 2 a B | a K a A a B ]
as a "forbidden structure" that must not be instantiated by the potential secret and query answers according to the instance. In step 2, first treating the potential secret, we find that the scheme KAB of the template dependency td covers the scheme AB of the potential secret Ψ . In step 3, we specialize the conclusion ( a K a A a B ) of td with the constants appearing in the potential secret Ψ , yielding ( a K c A c B ). Then we propagate this specialization to the hypotheses on common attributes, i.e., according to agree sets, getting ( a K c A b 1 ) for the first hypothesis, and ( a K b 2 c B ) for the second hypothesis. In this way we get the instantiated template dependency

td[Ψ ] := TD[ a K c A b 1 , a K b 2 c B | a K c A c B ].
In step 4, finally considering the instance r, we further uniformly instantiate the hypotheses on the distinguished symbol a K for the further agree set ag(h 1 , h 2 ) = {K} with h 1 = ( a K c A b 1 ) and h 2 = ( a K b 2 c B ) according to tuples in the instance r. For the single tuple R(c K , c A , c B ) ∈ r used twice, we get

Sig 1 := TD[ c K c A b 1 , c K b 2 c B | c K c A c B ] as an inference signature; similarly, for the tuple R(c K , c A , c B ) ∈ r we get Sig 2 := TD[ cK c A b 1 , cK b 2 c B | cK c A c B ]
as another inference signature. Each of them indicates that the user must not learn all of its hypotheses, and thus later on we can ignore its conclusion.

Once the inference signatures have been compiled at declaration time, they have to be monitored at run time according to the queries requested by the pertinent client. Suppose the client issues

Φ 1 := R(c K , c A , c B ), Φ 2 := (∃X B )R(c K , c A , X B ), and
Φ 3 := (∃X A )R(c K , X A , c B ).
Covering the potential secret Ψ , the first query Φ 1 is immediately refused. Though the second query Φ 2 does not cover Ψ , it nevertheless might contribute to a forbidden structure together with other queries. So we consider the inference signatures: Φ 2 only covers the first hypothesis ( c K c A b 1 ) of Sig 1 . Observing that Sig 1 has another hypothesis still uncovered, we can determine the correct query evaluation, yielding a positive answer (∃X B )R(c K , c A , X B ) to be returned to the client. Moreover, we have to mark the covered hypothesis as already hit.

The third query Φ 3 again does not cover Ψ , but the second hypothesis ( c K b 2 c B ) of Sig 1 : independently of the correct query evaluation we have to refuse the answer for the following reasons. If the correct answer is positive, the knowledge about all hypotheses of the inference signature would enable the client to directly infer the validity of the conclusion and thus of the potential secret Ψ . If the correct answer is negative, this additional knowledge does not directly lead to the crucial inference; however, only refusing a positive answer would enable a meta-inference of the following kind: "the only reason for the refusal is a positive answer, which thus is valid".

Example 2. To further exemplify the compiling phase in some more detail, we now consider the relation schema RS = R, U, Σ with attribute set U = {S(ymptom), D(iagnosis), P (atient)} and two join dependencies in Σ = { [SD, SP ], [DS, DP ]}, the instance r comprising the four tuples R(Fever , Cancer , Smith), R(Fever , Fraction, Smith), R(Fever , Cancer , Miller ), and R(Fever , Fraction, Miller ), and the confidentiality policy psec = {Ψ } containing the single potential secret Ψ = (∃X S )R(X S , Cancer , Smith). The upper part of Figure 1 shows the dependencies as template dependencies in graphical notation known as tableau. Intuitively, the first dependency expresses the following: a symptom a S that both contributes to a diagnosis a D for some patient b 1 , whose identity does not matter, and applies for the patient a P contributes to the diagnosis a D for the patient a P as well. The meaning of the second dependency has a similar flavor. As proved in [START_REF] Fagin | Tools for template dependencies[END_REF], the two join dependencies By Theorem 1, we have to consider all template dependencies that are implied by Σ. However, it suffices to finally employ only the basic implications. Unfortunately, so far we do not know an efficient algorithm to compute the set Σ +basic of all basic implications, which even might be infinite. But, we can somehow successively generate all candidates, in turn check each candidate whether it is an implication by applying the chase procedure, see [START_REF] Sadri | Template dependencies: A large class of dependencies in relational databases and its complete axiomatization[END_REF][START_REF] Fagin | Tools for template dependencies[END_REF][START_REF] Abiteboul | Foundations of Databases[END_REF], and finally minimize the hypotheses and maximize the conclusion of the implied candidates.

Figure 2 shows those elements of Σ +basic that have at most three hypotheses: we get the two declared dependencies and two basic versions of their direct product, obtained by deleting the third or the second hypothesis, respectively. In step 2 of the compiling phase, we identify those dependencies in Σ +basic such that the scheme {D(iagnosis), P(atient)} of the potential secret Ψ is contained in the scheme of the dependency; in this example, so far the condition is always satisfied. Accordingly, for each element of Σ +basic determined so far, attributes D and P in the conclusion are instantiated with the constants Cancer and Smith occurring in Ψ . These instantiations are then propagated to the hypotheses. In the next step 3, the hypotheses must be further instantiated according to the instance r. We have to determine minimal sets of tuples such that all equalities The instantiated template dependencies obtained so far are candidates to become inference signatures. However, we do not have to retain all them. Firstly, if an instantiated hypothesis of a candidate covers a potential secret, we can discard the candidate, since in the monitoring phase a query whose answer would reveal such a hypothesis would be refused anyway. So, in the example the instantiation of the second basic implication is discarded. Secondly, if the hypotheses of a candidate constitute a superset of the hypotheses of another candidate, then the former candidate is redundant and can be discarded as well. So, in the example the instantiation of the third basic implication is discarded as well.

For the given simple instance r, we do not have to consider basic implications with more than three hypotheses, and thus we finally keep the inference signatures shown in Figure 3. However, due to the cyclic structure of the dependencies in the example, there are basic implications with arbitrarily many hypotheses. So we can extend the basic implications having three hypotheses by a suitable fourth hypothesis, as shown in Figure 4. In fact, e.g., we can generalize the structure of the fourth dependency shown in Figure 3 diversity to instantiate such a long path with different constants. But we could employ a single element of the instance for instantiating several hypotheses and would then obtain instantiated signatures that we already got before.

Compiling and Monitoring Signatures

Generalizing the example, we now present the new signature-based enforcement mechanism as a two phase protocol.

The compiling phase takes the dependencies Σ declared in the schema, the confidentiality policy psec, and the instance r as inputs, and proceeds as follows to generate the set psig of all inference signatures: 1. It successively, with an increasing number of hypotheses, generates all basic template dependencies implied by Σ, i.e., Σ +basic := {td | Σ |= td, td is hypothesis-minimal and conclusion-maximal}, until no further ones can exist or further ones would not lead to nonredundant instantiations for the given instance r. 2. It determines all pairs (Ψ, td) with Ψ ∈ psec and td ∈ Σ +basic as generated so far, whose components match in the sense that the scheme of Ψ is a subset of the scheme of td, i.e., of the conclusion's aggregated agree set ∪ l j=1 ag(c, h j ), where td = TD[h 1 , . . . , h l |c]. 3. For each such pair, the (distinguished) symbols (seen as free variables) in the scheme of td are instantiated with the respective constants appearing in Ψ . Then the instantiation is propagated from the conclusion to the hypotheses. The result is denoted by td[Ψ ]. 4. For each td[Ψ ] obtained so far, the instance r is searched for a minimal set of tuples r td[Ψ ] that "uniformly covers" all hypotheses: (i) all equalities required by td[Ψ ] are satisfied and, (ii) the tuple values equal the respective already propagated instantiations. For each such set, the hypotheses are further instantiated on agree sets not captured before with the respective values found in the uniform covering. The remaining symbols are left unchanged. If none of the hypotheses covers any of the potential secrets in psec, then the resulting inference signature Sig(Ψ, td, r td[Ψ ] ) is inserted into psig. 5. If the hypotheses of a result of step 3 or 4 constitute a superset of the hypotheses of another result of step 3 or 4, respectively, then the former element is discarded, since it is redundant.

Given the fullness of the join dependencies in Σ, step 1 can be based on the chase algorithm [START_REF] Sadri | Template dependencies: A large class of dependencies in relational databases and its complete axiomatization[END_REF] together with bounded searching for minimization and subsequent maximization. Though being complex in general, the computation is expected to be feasible in practice, since we only deal with schema items. Moreover, in practice, a database administrator will only admit "minor" deviations from Boyce-Codd normal form having a unique key, for example, to ensure faithful representation of all dependencies by relaxing Boyce-Codd normal form to 3NF or to provide support of expected queries by a dedicated denormalization.

Similarly, seeing the elements of the confidentiality policy as a declaration of exceptions from the general default rule of permission, we expect that in many applications steps 2 and 3 will produce only a manageable number of templates for inference signatures. Moreover, as far as the constants occurring in these templates achieve a high selectivity regarding the instance considered, step 4 will not substantially increase the number of final inference signature.

The monitoring phase takes a query Φ, the confidentiality policy psec, the set psig of all inference signatures determined in the compiling phase, and the instance r as inputs, and proceeds as follows:

1. It checks whether some Ψ ∈ psec is covered by Φ (equivalently, Ψ is entailed by Φ, see Section 2), and if this is the case, the answer is immediately refused. 2. Otherwise, it determines all hypotheses Π occurring in psig and not marked before such that Π is covered by Φ, and it tentatively marks them. If now for some signature in psig all hypotheses are marked, then the answer is refused and the tentative marking is aborted. Otherwise, the correct answer is determined from r and then returned, and the tentative marking is committed if a positive answer Φ is returned; otherwise, if ¬Φ is returned, the tentative marking is aborted.

A straightforward implementation of the monitoring phase keeps the potential secrets and the suitably tagged hypotheses of inference signatures in two dedicated relations. Given a query, these relations are searched for covered tuples and inspected for an inference signature becoming fully marked. Approximating the computational costs of these actions for one instantiated hypothesis by a constant, the overall runtime complexity of an execution of the monitoring phase is at most linear in the size of the dedicated relations. In the next section we will present how this rough design has been converted into an SQL-based prototype.

Theorem 2. Assume the Situation 4 sketched in Section 1 and analyzed in [START_REF] Biskup | Chasing after secrets in relational databases[END_REF]: the a priori knowledge is restricted to comprise only a schema declaration with functional dependencies and join dependencies, and confidentiality policies and queries are restricted to select-project sentences. Then the signature-based enforcement mechanism preserves confidentiality (in the sense of Section 1). Sketch of Proof. "Negative" answers of the form ¬Φ i do not contribute to a harmful inference of a potential secret Ψ : on the one hand, the confidentiality policy contains only positive sentences and, on the other hand, the dependencies only generate positive conclusions from positive assumptions.

So let us assume indirectly that there is a harmful inference based on some minimal set of positive answers {Φ 1 , . . . , Φ m } to derive Ψ . Then, by Theorem 1 (Theorem 2 of [START_REF] Biskup | Chasing after secrets in relational databases[END_REF]), there exists a corresponding nontrivial template dependency that witnesses such an inference. In step 1 of the compiling phase, a hypothesis-minimal and conclusion-maximal version td of this dependency is added to Σ +basic ; this version then witnesses the inference considered as well. In the subsequent steps 2 and 3 of the compiling phase, td together with Ψ is further processed to set up a generic signature of the form td[Ψ ]. Furthermore, in step 4 of the compiling phase, the tuples in the instance r leading to the harmful positive answers Φ 1 , . . . , Φ m or these answers themselves, respectively, contribute to generate an (instantiated) inference signature of the form Sig(Ψ, td, r td[Ψ ] ).

Finally, in the monitoring phase, when the last of these positive answers is controlled, the tentative marking of this inference signature results in a marking of all its hypotheses, and thus the answer is refused. This contradicts the assumption that the positive answers Φ 1 , . . . , Φ m are all returned to the client.

A Prototype for Oracle/SQL

We implemented4 the signature-based enforcement mechanism as part of a larger project to realize a general prototype for inference-usability confinement of reactions generated by the server of a relational database management system (see Section 9 of [START_REF] Biskup | Inference-usability confinement by maintaining inference-proof views of an information system[END_REF]).

This prototype has been designed as a frontend to an Oracle/(SQL)-system: the administration interface enables officers to declare and manage client-specific data like the postulated a priori knowledge, a required confidentiality policy, a permitted interaction language, and the kind of distortion; the interaction interface enables registered clients to send requests like queries and receive reactions. The interaction language is uniformly based on the relational calculus as a specific version of first-order logic, which provides the foundation of the semantics of relational databases.

Accordingly, if a client should be permitted to issue queries under a schema RS = R, U, Σ but be confined by the signature-based enforcement mechanism, then the following has to happen: the client is granted a permission to query the current instance r; the dependencies in Σ are added to that client's a priori knowledge; the language L is made available to the client to submit queries; a confidentiality policy is declared to confine the client's permission; and refusals are specified as the wanted kind of distortion. Additionally, a compatible enforcement mechanism is selected, either automatically by an optimizer or explicitly by an administrator. In the remainder of this section, we assume that inference signatures are both applicable and necessary as described in Section 1.

In a first attempt, considering the general prototype to mediate access to the underlying Oracle-system would suggest to let a wrapper translate a query Φ ∈ L into an SQL-query during the monitoring phase. In our case, for instance, assuming that R denotes the Oracle-table for the instance r, a closed (yes/no)query (∃X 1 ) . . . (∃X l )R(X 1 , . . . , X l , c l+1 , . . . , c n ) would be converted into Select A l+1 , . . . , A n From R Where A l+1 = c l+1 And . . . And A n = c n , which returns either the empty set or a singleton with a tuple µ of the form (A l+1 : c l+1 , . . . , A n : c n ) over the attribute set {A l+1 , . . . , A n }. However, while forwarding this query to the Oracle-system, we want the server not only to evaluate the query but to perform the further actions on the inference signatures described in Section 4 as well. In principle, this goal can be accomplished by the features of Oracle for active databases, i.e., by triggers. Since Oracle does not provide means to define a trigger on a query directly, we instead employ a suitable update command to an auxiliary Oracle-table QUE(RY), which together with two further tables (which will be described below) has already been created during the compiling phase.

-Basically, the table QUE(RY) has the attributes in U specified in the schema for the table R and a further attribute Rea(ction), which has a threevalued type {ref (used), pos(itive), neg(ative)}: a tuple of QUE(RY) denotes a query as a generalized tuple combined with an indicator how to react.

Regarding Oracle-privileges, any access right the client might have before on the Oracle-table R must be revoked, and instead the client is only granted the Insert-right on the auxiliary table QUE(RY). The needed trigger CQE is declared for insertions into the table QUE(RY), and this trigger is executed with the access rights of the owner (administrator) of the table R. Accordingly, we employ some kind of "right amplification", as for example offered by the operating system UNIX by means of setting the suid-flag for an executable file: the client only receives a privilege to initiate the query-and-control activities, as predefined by the trigger, without being permitted to perform such activities at his own discretion.

The trigger CQE operates on the auxiliary Oracle-table QUE(RY) and the two further Oracle-tables (POT)SEC and SIG(NATURE) that already have been created separated from the Oracle-table R during the compiling phase.

-The table (POT)SEC has the same attribute set U as R such that a declared potential secret Ψ ∈ L can be represented as a generalized tuple; however, each (originally existentially quantified) variable is uniformly replaced by a special placeholder " * ". -The table SIG(NATURE) has the attributes in U as well such that a hypothesis of an inference signature can again be represented as a generalized tuple, and three further attributes to be used as follows: the attribute Id specifies an inference signature the represented hypothesis belongs to; the Boolean attribute (Flag)Imp refers to a tentative marking during a current monitoring phase; and the Boolean attribute (Flag)Old refers to a marking already committed while controlling a preceding query.

Unfortunately, it turned out that we need the two flags, since we could not employ standard transaction functionality to freshly mark hypotheses tentatively and finally either commit the fresh markings or abort them by a rollback instruction: Oracle does not offer to direct the needed transaction functionality within trigger executions.

Figure 5 shows the Oracle-tables for the small hospital database introduced as Example 2 in Section 3 with the instance inserted into table R, after filling the table (POT)SEC with the declared confidentiality policy, populating the table SIG(NATURE) with the compiled inference signatures, and forwarding the query (∃X)R(Fever , Cancer , X) to the table QUE(RY).

Activated by the insertion of the query into the Oracle-table QUE(RY), the trigger CQE basically proceeds as follows:

1. The trigger extracts the query submitted by the client from QUE, constructs an SQL-query to determine whether or not the extracted query covers an element in SEC, executes the constructed SQL-query, and then checks the result for emptiness: if the result is nonempty, i.e., a covering has been detected, the trigger modifies the attribute Rea(ction) of the single tuple in QUE into ref (used) (which the frontend retrieves subsequently), and the trigger exits. The following SQL-query is constructed for the example:

Select Sym,Dia,P at From SEC Where (Sym = F ever Or Sym = * ) And (Dia = Cancer Or Sym = * ) And P at = * 2. Otherwise, the trigger continues to perform the actions already described in Section 4 by suitably employing the Oracle-tables in a similar way as in the first step; see Figure 6 for the rough design.

Experimental Evaluation

To determine the runtime overhead inherently caused by the signature-based enforcement mechanism, we measured the query processing times of the implementation described in Section 5. We started with the following observation.

Given the dependencies declared in the schema and the confidentiality policy, a generic inference signature signifies a typical "forbidden structure", and thus all of them together represent all possibilities for harmfulness. Thus, we aimed at constructing the instances to be used for runtime evaluations by varying the following parameters: (1) the included forbidden structures; (2) the instantiations of included forbidden structures; and (3) the fraction of confined "exceptions". Moreover, we expected an impact of the length of query sequences, since with increasing length more markings of hypotheses will be found. Accordingly, we measured the following query processing times: the maximum time that occurred up to the last query of a sequence for the whole frontend and the trigger alone, respectively; and the average time over a sequence for the whole frontend and the trigger alone, respectively. Discarding exceptional measurements caused by external factors and applying suitable roundings, we depict the results for Example 2 in Table 1: We restricted to the forbidden structures shown in Figure 2 and4; varied the number of instantiations from 1 over 10 and 100 up to 1000, in this way getting instances (by applying the chase algorithm to satisfy the dependencies) of size from 79 tuples up to 79000 tuples; declared for each instantiated forbidden structure just one potential secret (as an "exception"); and formed query sequences of length from 100 up to 100000, suitably covering all relevant cases in a random way. The results for the particular example suggest the practical feasibility of our approach, including scalability: a human user acting as a client will basically not realize a query processing time in the range of a few milliseconds up to around half a second. Of course, general practicality still has to be justified by statistically evaluating more advanced experiments for "real-world" applications using a more mature implementation with enhanced functionality and further optimizations.

Conclusions

Summarizing and concluding, we presented a signature-based enforcement mechanism that satisfies confidentiality requirements that are very general and have been considered in many contexts before, as summarized and further investigated by Halpern/O'Neill [START_REF] Halpern | Secrecy in multiagent systems[END_REF] and suitably extended to include policies by Biskup/Tadros [START_REF] Biskup | Policy-based secrecy in the Runs & Systems Framework and controlled query evaluation[END_REF]. The mechanism can be seen as a variation of a security automaton for the run time enforcement of security properties in the sense of Ligatti/Reddy [START_REF] Ligatti | A theory of runtime enforcement, with results[END_REF] and others. We demonstrated the effectiveness of the mechanism for relational databases that are constrained by the large class of functional dependencies and join dependencies, which capture a wide range of applications, see, e.g., Abiteboul/Hull/Vianu [START_REF] Abiteboul | Foundations of Databases[END_REF].

Our mechanism differs from previously considered monitoring systems by taking advantage of the particular properties of functional dependencies and join dependencies, without imposing any further restrictions on these dependencies. We provide a proactive control functionality avoiding any confidentiality breach, in contrast to auditing approaches as described by, e.g., Kaushik/Ramamurthy [START_REF] Kaushik | Efficient auditing for complex SQL queries[END_REF], which can only detect violations after the fact.

There are several lines of further research and development, dealing with the following issues: tools for the compiling phase, the distribution of functionality between the two phases, the complete integration into a database management system like Oracle, more advanced interactions like open queries, updates and transactions, and experimental evaluations with "real-world" applications.

Regarding tools for the compiling phase, a major open problem is to design a generally applicable algorithm to effectively and efficiently determine all basic implications up to a suitably chosen number of hypotheses for any set of functional dependencies and join dependencies. We conjecture that properties regarding the occurrence of cyclic structures in the hypergraph of the dependen-cies has a major impact. The computational complexity of the compiling phase should also be investigated.

Regarding distribution of functionality, we already designed a more dynamic version of the signature-based enforcement mechanism. In this version, we initially keep the inference signatures generic, without instantiating them with specific values from the instance already at compile time. Rather, instantiations are dynamically generated at run time only employing instance tuples actually returned as responses to the client. This more dynamic version can be derived from the static version detailed in this article but some subtle optimization problems still have to be solved in a satisfactory way.

Regarding a complete integration, we first of all face problems of modifying proprietary software, but we would also be challenged to make the added functionality fully compatible with all the many services already offered. Of course, from the point of view of both administrators and clients, in general a full integration would be advantageous: conceptually for employing uniform interfaces, and algorithmically for avoiding the overhead raised by the communication of a separate frontend with a server and for including the security functionality into the scope of the server's optimizer.

Regarding advanced interactions, on the one hand we have to suitably adapt previous theoretical results [START_REF] Biskup | Controlled query evaluation with open queries for a decidable relational submodel[END_REF][START_REF] Biskup | Inference-proof view update transactions with forwarded refreshments[END_REF] and, again, to exploit the features of the underlying database management system as far possible. On the other hand, in general an update of the database instance will require to update the (instantiated) inference signatures as well. Clearly, both aspects would have to be suitably combined, while also considering the optimization problems mentioned above.

Finally, regarding "real-world" applications, we would have to identify suitable classes of applications, clarify in detail how far the assumptions underlying the signature-based approach are actually satisfied by such applications, and then overcome essential mismatches by additional mechanisms. However, as pointed out in the introduction, there is an inevitable tradeoff between conceptual expressiveness and computational complexity: any extension of the work presented in this article will be challenged to maintain an appropriate balance between the conflicting goals.

Fig. 1 .

 1 Fig.1.[SD, SP ],[DS, DP ], and their direct product as tableaus

Fig. 2 .Fig. 3 .

 23 Fig. 2. All basic implications of Σ having two or three hypotheses

  by extending the present "path" a S ,a S ,b 4 ,b 4 by b 2 ,b 2 ,b 7 ,b 7 ,b 8 ,b 8 ,b 10 ,b 10 , as exhibited by the rightmost dependency shown in Figure 4. However, the instance r lacks sufficient

Fig. 4 .

 4 Fig. 4. Basic implications of Σ having four hypotheses and an example of a basic implication of Σ having "many" hypotheses

Fig. 6 .

 6 Fig. 6. Design of the trigger CQE to control a submitted query

  Fig. 5. Oracle-tables for signature-based enforcement applied to hospital database

	R	Sym F ever Cancer Smith Dia Pat	QUE Sym F ever Cancer Dia	Pat Rea X
		F ever F raction Smith F ever Cancer M iller F ever F raction M iller	SIG Sym F ever Cancer Dia F ever b2	Pat b1 Smith 1 Id Imp Old 1
	SEC Sym *	Dia Cancer Smith Pat	F ever Cancer F ever F raction b2 F raction Smith 2 b1 2 b5 2

Table 1 .

 1 Maximum and average query processing times experienced for Example 2

				Processing time pro query in msec
	Instantiations Instance Queries	whole frontend	trigger alone
		size		maximum average maximum average
	1	79	100	22	15	10	2
	10	790	1000	54	17	10	3
	100	7900	10000	421	23	150	7
	1000	79000	100000	711	78	580	61

The following exposition only outlines the implementation and slightly differs from the presently employed version of the code, which is under ongoing development for both improved usability and further optimization.

Acknowledgments: We would like to sincerely thank Martin Bring and Jaouad Zarouali for improving the implementation and conducting the experiments.

This work has been partially supported by the Deutsche Forschungsgemeinschaft under grant BI 311/12-2 and under grant SFB 876/A5 for the Collaborative Research Center "Providing Information by Resource-Constrained Data Analysis".


Rosa Karimi Adl

Mina Askari
email: maskari@ucalgary.ca

Ken Barker
email: kbarker@ucalgary.ca

Reihaneh Safavi-Naini

Privacy Consensus in Anonymization Systems Via Game Theory

Keywords: Privacy Protection, Data Anonymization, Privacy/Utility Trade-off, Privacy Parameter Setting, Game Theory, k-Anonymity

Privacy protection appears as a fundamental concern when personal data is collected, stored, and published. Several anonymization methods have been proposed to address privacy issues in private datasets. Every anonymization method has at least one parameter to adjust the level of privacy protection considering some utility for the collected data. Choosing a desirable level of privacy protection is a crucial decision and so far no systematic mechanism exists to provide directions on how to set the privacy parameter. In this paper, we model this challenge in a game theoretic framework to find consensual privacy protection levels and recognize the characteristics of each anonymization method. Our model can potentially be used to compare different anonymization methods and distinguish the settings that make one anonymization method more appealing than the others. We describe the general approach to solve such games and elaborate the procedure using k-anonymity as a sample anonymization method. Our simulations of the game results in the case of k-anonymity reveals how the equilibrium values of k depend on the number of quasi-identifiers, maximum number of repetitive records, anonymization cost, and public's privacy behaviour.

Introduction

Massive data collection about individuals on the Web raises the fundamental issue of privacy protection. A common approach to address privacy concerns is to use data anonymization methods [START_REF] Samarati | Generalizing data to provide anonymity when disclosing information[END_REF][START_REF] Sweeney | k-anonymity: a model for protecting privacy[END_REF][START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF][START_REF] Li | t-closeness: Privacy beyond k-anonymity and ldiversity[END_REF][START_REF] Dwork | Differential privacy[END_REF]. During data anonymization identifiers are removed and data perturbation, generalization, and/or suppression methods are applied to data records.

Data anonymization promises privacy up to a certain level specified by some privacy parameter(s). In setting the privacy parameter, usually the amount of the expected data utility is considered and hence the level of privacy offered by an anonymization method is never set to the maximum. Since the risk to privacy is not completely removed, we postulate that data providers must be informed about the amount of privacy risk involved (represented as the privacy parameter's value) before deciding to provide their personal data to data collectors.

To bring data providers' privacy opinion into the cycle of data anonymization, we propose a game theoretic model that finds consensual privacy and utility levels by considering preferences of data providers as well as data collectors and data users. More specifically, we analyze the privacy/utility trade-off from the perspective of three different parties: a data user who wants to perform data analysis on a dataset and is willing to pay for it; a data collector who collects and provides privacy protected data to the data user; and data providers who can choose to participate in data collection if they see it as worthwhile. As these parties try to maximize their "profit" (payoff), the collective outcome of the game produces the equilibria [START_REF] Osborne | An Introduction to Game Theory[END_REF] in our trade-off system. In an equilibrium state, no single player can achieve higher profits by changing their actions. Therefore, equilibria represent shared agreements (hence the term consensus) in which none of the players would attempt to behave differently. Using these equilibria, we are able to examine privacy trade-offs and analyze different characteristics of an anonymization technique such as the expected amount of privacy, precision, database size, and each party's profit. We believe that features of an anonymization technique must be inspected at equilibrium stages to provide more reliable evaluation results. The proposed model can be used as an evaluation framework to compare various anonymization methods from different perspectives. This is the first attempt to use game theory to analyze trade-offs in a private data collection system by considering preferences of data providers.

Paper organization: The remainder of this paper is organized as follows: Section 2 discusses the related work. Section 3 describes basic definitions in game theory. Section 4 explains our game model and its ingredients. Section 5 provides a general solution to the game. Section 6 demonstrates a sample application of our model for the case of k-anonymity. Section 7 provides conclusions and suggests future directions.

Related Work

The issue of protecting individual's privacy while collecting personal information has motivated several research projects in literature. Our work mostly relates to anonymization techniques such as k-anonymity [START_REF] Samarati | Generalizing data to provide anonymity when disclosing information[END_REF][START_REF] Sweeney | k-anonymity: a model for protecting privacy[END_REF], l-diversity [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF], t-closeness [START_REF] Li | t-closeness: Privacy beyond k-anonymity and ldiversity[END_REF], and differential privacy [START_REF] Dwork | Differential privacy[END_REF]. Anonymization techniques provide data privacy at the cost of losing some information. Several methods [START_REF] Lefevre | Workload-aware anonymization[END_REF][START_REF] Jr | Data privacy through optimal k-anonymization[END_REF][START_REF] Fung | Top-down specialization for information and privacy preservation[END_REF][START_REF] Sramka | A practice-oriented framework for measuring privacy and utility in data sanitization systems[END_REF][START_REF] Machanavajjhala | Personalized social recommendationsaccurate or private?[END_REF] have been proposed to evaluate the trade-off of privacy/utility. When data usage is unspecified, similarity between the original data and the privacy protected data is considered as information loss. The average size of equivalence classes [START_REF] Lefevre | Workload-aware anonymization[END_REF] and discernibility [START_REF] Jr | Data privacy through optimal k-anonymization[END_REF] in k-anonymity are two examples of such generic metrics. However, most scholars have noticed that more reliable utility measures must be defined in the context of data application (e.g.,data mining and queries). Various measures of utility such as information-gain-privacy-loss ratio [START_REF] Fung | Top-down specialization for information and privacy preservation[END_REF] and clustering and partitioning based measure [START_REF] Loukides | Data utility and privacy protection trade-off in k-anonymisation[END_REF] have been proposed to determine the next generalization step within anonymization algorithms. Sramka et al. [START_REF] Sramka | A practice-oriented framework for measuring privacy and utility in data sanitization systems[END_REF] developed a data mining framework that examins the privacy/utility trade-off after the anonymization has been done using a mining utility. Machanavajjhala et al. [START_REF] Machanavajjhala | Personalized social recommendationsaccurate or private?[END_REF] defines an accuracy metric for differential privacy in the context of social recommendation systems and analyzes the trade-off between accuracy and privacy. The existing privacy/utility trade-off methods all assume that a dataset already exists before choosing the privacy protection level for it. These methods do not consider the effect of privacy protection level on data providers' decision and hence the volume of the collected information.

In this work we use game theory to investigate steady levels of privacy protection by adopting a broader view of affecting parameters. Game theory has been successfully applied to analyze privacy issues from legal [START_REF] Anderson | The privacy gambit: Toward a game theoretic approach to international data protection[END_REF] and economic perspectives [START_REF] Böhme | On the viability of privacy-enhancing technologies in a self-regulated business-to-consumer market: Will privacy remain a luxury good?[END_REF][START_REF] Kleinberg | On the value of private information[END_REF][START_REF] Calzolari | Optimal design of privacy policies[END_REF][START_REF] Preibusch | Implementing privacy negotiations in e-commerce[END_REF]. Kleinberg et al. [START_REF] Kleinberg | On the value of private information[END_REF] describe three scenarios modeled as coalition games [START_REF] Osborne | An Introduction to Game Theory[END_REF] and use core and shapely values to find a "fair" reward allocation method in exchange for private information. The underlying assumption in these scenarios is that any amount of reward compensates for the loss of privacy protection. We believe this assumption oversimplifies the nature of privacy concerns and is not compatible with our perception of privacy. Calzolari and Pavan [START_REF] Calzolari | Optimal design of privacy policies[END_REF] use game theory to explore the optimum flow of customers' private information between two interested firms. The perspective of their work is possibly closest to ours but their model is substantially different from our work since they define a privacy policy as probability of revealing detailed customers' information to another party. Game theory has also been used as a means to address more technical aspects of privacy such as attacks on private location data [START_REF] Gianini | A game-theoretical approach to data-privacy protection from context-based inference attacks: A location-privacy protection case study[END_REF], implementation of dynamic privacy [START_REF] Preibusch | Implementing privacy negotiations in e-commerce[END_REF], and questioning the assumption of honest behavior in multiparty privacy preserving data mining [START_REF] Kargupta | Multi-party, privacy-preserving distributed data mining using a game theoretic framework[END_REF]. Our work builds on a commonly accepted definition of privacy among computer and social science scholars and adopts a game theoretical approach to find steady privacy levels. The novelty of our research lies on bringing the economic perspective to data anonymization issues and utilizing game theory for the first time to address privacy/utility trade-offs in a more realistic setting.

Preliminaries and Assumptions

In this paper we propose a game-theoretic framework to find steady level(s) of privacy protection for any arbitrary anonymization technique. We assume that the data providers are informed about having their personal information collected and the data collector is trustworthy in the sense that he fulfills his promises. Every instance of the game is modeled according to a chosen anonymization technique. A common factor between these techniques is a privacy parameter such as k in k-anonymity, l in l-diversity, and 1/ in differential privacy that indicates the level of privacy protection guaranteed by the corresponding privacy mechanism. To provide a generic game model, we use the letter δ to denote the privacy parameter. For any chosen anonymization technique, larger values for δ lead to higher privacy protection and lower data utility. The exact meaning of δ has to be interpreted according to the privacy definition chosen for the game. In this section we provide a brief overview of the game theoretic definitions used in this paper.

Sequential Game Model

Game theory is a mathematical approach to study interdependencies between individual's decisions in strategic situations (games). A game is explained by a set of players (decision makers), their strategies (available moves), and payoffs to each player for every possible strategy combination of all players (strategy profile). A strategy profile is a Nash equilibrium if none of the players can do better by changing their strategy assuming that other players adhere to theirs. Nash equilibrium is commonly used to predict stable outcomes of games and since it represents a steady state of a game [START_REF] Osborne | An Introduction to Game Theory[END_REF], we use the term "stable" through the rest of the paper to denote the strategies found in the equilibrium. To capture a pre-specified order for players' turn to move, a game tree is used to represent a sequential game. In this tree each node is a point of choice for a player and the branches correspond to possible actions. A sequence of actions from the root to any intermediate node or to a leaf node is called a history or a terminal history, respectively [START_REF] Osborne | An Introduction to Game Theory[END_REF]. Payoff functions define Preferences of players over each terminal history. A player's strategy explains his decision at any point in the game that he has to move.

Since the sequential structure of extensive form games is not considered in the concept of Nash equilibrium, the notion of "subgame-perfect Nash equilibrium" [START_REF] Osborne | An Introduction to Game Theory[END_REF] is normally used to determine the robust steady states of such games. Every sub-tree of the original game tree represents a subgame. A strategy profile is a subgame perfect equilibrium if it induces a Nash equilibrium in every subgame [START_REF] Osborne | An Introduction to Game Theory[END_REF]. The principle of Backward induction is a common method to deduce subgame-perfect equilibria of sequential games. Backward induction simply states that when a player has to move, he first deduces the consequences of every available action (how the subsequent player rationally reacts to his decision) and chooses the action that results in the most preferred terminal history.

The challenge of setting a desirable value for privacy parameter δ defines strategic situation with some ordering on players' turn to move. As a result, we model the problem as a sequential game.

Game Description

To define a game-theoretic model for the challenge of finding a balanced value of δ, we must specify the decision makers (players), their preferences, and the rules of the sequential game. The following sections explain the details of our model.

Players

Players of the game are the following three parties:

Data providers-Data providers are individuals that decide whether to provide their personal information at a specific privacy level δ and use the service offered by the data collector or to reject the offer. For example the service could be a discount on some online purchase activity or a software application offered for free. Since privacy preferences of each data provider is affected by several demographic and socioeconomic factors [START_REF] Acquisti | Privacy and rationality in individual decision making[END_REF][START_REF] Culnan | Information privacy concerns, procedural fairness, and impersonal trust: An empirical investigation[END_REF][START_REF] Singer | The impact of privacy and confidentiality concerns on survey participation: The case of the 1990 u.s. census[END_REF], it is practically infeasible to determine how much utility is gained by each data provider for each combination of δ and incentive. In an alternative approach, we rely on the assumption that data providers' behavior is captured by a model based on some observation rather than a game theoretic analysis. Our assumed model is a regression model which captures how the number of data providers increases as the values of δ and incentive increase. Although this specific model has not been developed yet, similar studies have been conducted to explore the effects of other parameters (such as knowledge of privacy risks, trust, age, income level, etc.) on public's privacy behavior [START_REF] Acquisti | Privacy and rationality in individual decision making[END_REF][START_REF] Singer | The impact of privacy and confidentiality concerns on survey participation: The case of the 1990 u.s. census[END_REF][START_REF] Milne | Direct mail privacy-efficiency trade-offs within an implied social contract framework[END_REF]. A regression model that explains the effects of δ and incentive seems to be a natural extension to those studies. The assumed model generally considers data providers who are interested in both privacy and incentive and is defined as:

N = n(δ, I) = β 0 + β 1 h 1 (δ) + β 2 h 2 (I) (1)
where N represents total number of individuals who accept the offer as a function of δ and incentive I (in terms of a monetary value). h 1 and h 2 are functions of δ and I. Parameters β 0 , β 1 , and β 2 are the intercept and marginal effects of h 1 (δ) and h 2 (I) on individual's decision to participate in the data collection procedure. The functions h 1 and h 2 can be any non-decreasing functions of δ and I. This regression model does not assume accurate knowledge about privacy risks for data providers and as this knowledge increases, we expect to have larger β 1 to reflect a higher level of privacy concerns.

By assuming a regression model, we mostly observe data providers' behavior rather than directly analyzing it. This assumption trims the game tree by removing the data providers from the analysis of the game. Nevertheless, the effect of data providers' decisions is reflected in other players' payoff functions and paying specific attention to their impact on the final level of privacy is one of the distinctive strengths of our work.

Data collector-A data collector is the entity who collects a dataset of personal data and provides it to some data users. The data collector receives offers from the data users, and based on their needs and the expected cardinality of the collected dataset announces a privacy level and some incentive to collect data from individuals. Once a data collector collects a dataset of personal information, he protects the privacy of the data providers at the consented level δ and provides the private dataset to the data user.

The data collector generally prefers to receive more money from the data user and spend less money on the amount of incentive he pays the data providers. Consequently, cardinality of the dataset (number of data providers) affects the payoff to the data collector. A detailed formulation of data collector's payoff is provided in Sect. 4.3.

Data user-A data user is an entity interested in accessing personal information for some data analysis purposes. A data user prefers a dataset with higher quality (more accurate query results) and higher cardinality (results with higher statistical significance). Privacy parameter δ affects these requirements in positive and negative ways. Therefore a data user chooses a value δ that balances the needs and initiates the game by offering some value for parameter δ and some price, p, for each data record. We give the detailed analysis for games with a single data user. The approach to model multiple data users and data reuse is explained elsewhere [START_REF] Adl | Privacy consensus in anonymization systems via game theory[END_REF].

Game Rules

We model interactions between the data collector and the data user as a sequential game with perfect (players are aware of the actions taken by previous players) and complete (players are aware of the available strategies and payoff functions of all other players) information. More specifically, both players know data the provider's behavior model. The data user also knows the data collector's available actions and preferences 1 .

The game starts with an offer from the data user to the data collector. In the offer, the required value for privacy parameter δ and the price p (per each record) must be specified. We denote an offer by Of = δ, p . Once the data collector receives the offer he can either reject or accept it. In case of a rejection, the game terminates with payoff zero to both the data user and the data collector. If the data collector decides to accept then he needs to announce an incentive in exchange for collecting personal information. Here, we assume that I represents monetary value of the incentive and its domain is R ≥0 . The terminal histories of this game are either of the form (Of, I) or (Of, Reject). At any terminal history, the number of data providers who will opt-in is determined by plugging the values of δ and I into Eq [START_REF] Samarati | Generalizing data to provide anonymity when disclosing information[END_REF]. Consequently, preferences of the data user and the data collector over all terminal histories are determined based on the payoff function defined over cardinality of dataset and values of δ, p, and I.

The interactions and mutual effects of players' decision are captured in Fig. 1(a). Based on the game's dynamics, Fig. 1(b) illustrates the game tree (triangles represent ranges of possible offers and incentives).

Payoffs

Payoff to the Data Collector: The data collector receives some money, p, from the data user for each data record. The total number of data records in the dataset is the same as the number of data providers who participate in the data collection procedure and is defined by N in Eq [START_REF] Samarati | Generalizing data to provide anonymity when disclosing information[END_REF]. Consequently, the income of the data collector is: income DC = p N (2) Data collection procedure, data anonymization, and storing the dataset are costly and we denote these costs by C. Moreover, the data collector has to pay some incentive, I, to each data provider. As a result, the expenses to the data collector can be defined as:

expenditure DC = I N + C (3)
For simplicity of analysis we have assumed a fixed cost C for data collector. This assumption can be dropped easily by defining cost as a function of the size of the dataset and privacy level δ without any significant modification to our analysis. The payoff to the data collector is therefore defined as:

U DC = income DC -expenditure DC = (p -I) N -C (4)
Payoff to the Data User:

The data user wants to run some data analysis on the privacy protected dataset T * . As the cardinality of this dataset increases, the dataset will have higher value to the data user. Let a denote the economic value of each record to the data user, i.e., a represents the net revenue of a data record if the data user gets the record for free. If the number of data records collected from individuals is denoted by N we can initially define the data user's income as a * N . However, after anonymization the utility of data drops due to imprecision introduced to results of the queries. We use parameter 0 ≤ P recision ≤ 1 as a coefficient of the data user's income to show how the value of the dataset decreases as data become less precise. The income of the data user is:

income DU = a N P recision (5) To estimate the precision of query results on a private dataset, various parameters must be considered. These parameters include the semantics of the query, the anonymization method and algorithm used, database schema, level of privacy protection δ, number of data records N , and etc.. For each instance of the game, all of these parameters except for δ and N are fixed (and assumed to be a common knowledge of the game). Therefore, P recision = prec(δ, N ) is defined as a function of two variables δ and N . The main characteristic of the P recision function is that for any fixed number of data records N , P recision is a decreasing function of δ2 .

If the data user pays price p per record, his expenditure is p N and therefore his payoff can be defined as:

U DU = a N P recision -p N (6)
5 General Approach to Find Subgame Perfect Equilibria

In this section we explain the steps involved in the process of finding the game's subgame perfect equilibria using backward induction [START_REF] Osborne | An Introduction to Game Theory[END_REF]. In the next section, we show the details of this process for k-anonymity as an example.

Equilibrium Strategies of Data Collector

The first step to find subgame perfect equilibria is to find the optimal actions of the data collector in each subgame of length 1. Subgames of length 1 are represented by subtrees at which the data collector has to move based on a history of the form (Of ).

Where Of = δ, p is an offer made by the data user.

The data collector can estimate the expected cardinality of the dataset for each δ and I based on Eq [START_REF] Samarati | Generalizing data to provide anonymity when disclosing information[END_REF]. If we plug this equation into the U DC formula from Eq(4), the data collector's payoff after accepting Of = δ, p will be:

UDC = (p -I)(β0 + β1h1(δ) + β2h2(I)) -C (7)
For each offer Of = δ, p , the values of δ and p are fixed. The data collector needs to find the optimum I (denoted by Î) for which the function U DC attains its maximum value. To find Î we must find the argument of the maximum:

Î = arg max I U DC = arg max I (p -I)(β 0 + β 1 h 1 (δ) + β 2 h 2 (I)) -C (8)
Subject to the constraint that Î ≥ 0.

If the maximum U DC , ÛDC , is greater than zero the data collector accepts the offer. If ÛDC = 0 then the data collector will be indifferent between accepting and rejecting and in the case where ÛDC < 0 the data collector rejects. Therefore, the data collector's best response, BR DC , to an offer Of = δ, p is:

BR DC (δ, p) = Reject if (p -Î)(β 0 + β 1 h 1 (δ) + β 2 h 2 ( Î)) -C ≤ 0 Accept with Î if (p -Î)(β 0 + β 1 h 1 (δ) + β 2 h 2 ( Î)) -C ≥ 0 (9)
The optimum incentive Î must only be calculated when the data collector accepts the offer. This means Î ≤ p, otherwise ÛDC < 0. Since U DC is continuous in the closed and bounded interval [0, p] (the domain of I), according to the Extreme value theorem [START_REF] Sydsaeter | Mathematics for economic analysis[END_REF], U DC reaches its maximum at least once and therefore Î is guaranteed to exist.

Equilibrium Strategies of Data User

The next step to find the subgame perfect equilibria is to find the most profitable action of the data user; Knowing the data collector's best response (Sect. 5.1) to each Of = δ, p , what combination of δ and p maximizes the data user's payoff? When the data collector accepts an offer Of = δ, p , he chooses the optimum incentive Î. Depending on the exact function definitions used in Eq(8), if Î is unique for every combination of δ and p, then Î can be defined as a function of δ and p (i.e., Î = î(δ, p)). Without loss of generality, we assume that this is the case. If multiple values of I maximize U DC , the one that also maximizes the data user's payoff is in the equilibria of the game.

According to Sect. 5.1, if the data collector accepts the offer he starts collecting personal information at privacy level δ with incentive Î = î(δ, p). Otherwise, no dataset will be provided to the data user. As a result, the anticipated number of records N can be determined as:

N = n(δ, Î) =    β 0 + β 1 h 1 (δ) + β 2 h 2 ( Î) if ÛDC ≥ 0 0 Otherwise (10)
Plugging the function definition of Î = î(δ, p) into Eq [START_REF] Sramka | A practice-oriented framework for measuring privacy and utility in data sanitization systems[END_REF], N = n 2 (δ, p) becomes a function of δ and p as well. Recall that P recision = prec(δ, N ) is defined as a function of δ and N . Since N is a function of δ and p, we can define P recision = prec 2 (δ, p) as a function of δ and p as well. After substituting N and P recision with n 2 (δ, p) and prec 2 (δ, p), the U DU function from Eq(6) becomes a function of two variables δ and p. The most profitable strategy for the data user is to choose values of δ and p that maximize his payoff:

δ, p = arg max δ,p U DU = arg max δ,p (a prec 2 (δ, p) -p) (n 2 (δ, p)) (11)
By definition, the lower bounds on p and δ is zero, i.e., p ≥ 0 and δ ≥ 0. Moreover, since P recision ≤ 1 then (a * prec 2 (δ, p)) ≤ a. Choosing a value p > a leads to a negative payoff to the data user and he can always do better by choosing p = 0 (which leads to payoff zero). Therefore, the upper bound for p is a. Parameter δ is not necessarily bounded from above. Consequently, we cannot use the Extreme value theorem to guarantee an equilibrium.

If U DU has an absolute maximum subject to the bounds defined on δ and p, the game has subgame perfect equilibria of the forms (( δ, p), reject) or (( δ, p), Î). The first form occurs when the data collector cannot find any profitable amount of incentive (regardless of δ and p chosen by the data user) and the negotiation is unsuccessful. The second format occurs in games where there are at least one combination of δ and p of which the data collector can make profit. The two types of equilibria provide a means to determine whether an anonymization technique is practical or impractical given other problem settings. If the cost of implementing an anonymization technique is too high and the public's trust in the method is not high enough, the game might become an instance of unsuccessful negotiations and we have a case of impractical anonymization.

Game Theoretic Analysis for k-Anonymity

To demonstrate the details of the steps explained in Sect. 5, we use k-anonymity as the anonymization technique and provide a P recision function for it. The game solution is described and a simulation of the results is provided at the end of this section.

k-Anonymity Overview

A dataset to be released contains some sensitive attributes, identifying attributes, and quasi-identifying attributes. Even after removing the identifying attributes, the values of quasi-identifying attributes can be used to uniquely identify at least a single individual in the dataset via linking attacks. Every subset of tuples in dataset that share the same values for quasi-identifiers is often referred to as an equivalence class. A released dataset is said to satisfy k-anonymity, if for each existing combination of quasi-identifier attribute values in the dataset, there are at least k -1 other records in the database that contain such a combination.

There are several methods to achieve k-anonymity. Our work is built on Mondrian algorithm [START_REF] Lefevre | Mondrian multidimensional k-anonymity[END_REF]. This greedy algorithm implements multidimensional recoding (with no cell suppression) which allows finer-grained search and thus often leads to a better data quality. In Mondrian algorithm all the identifying attributes are suppressed first. Then records are recursively partitioned into d-dimensional rectangular boxes (equivalence classes), where d is the number of quasi-identifiers. To partition each box, a quasiidentifier attribute (a dimension) is selected and the median value along this attribute is used as a binary cut to split the box into two smaller boxes. Once partitioning is done, records in each partition are generalized so that they all share the same quasi-identifier value, to form an equivalence class. A copy of this algorithm is provided in Fig. 3(b).

Data Providers' Privacy Model

Based on Sect. 4.1, we assume a regression model to explain data providers' reaction (at an aggregate level) to each combination of privacy protection levels and incentives. This model is explained in Eq [START_REF] Samarati | Generalizing data to provide anonymity when disclosing information[END_REF]. In k-anonymity, privacy parameter is k. Here, we consider the identity function for the incentive (because of its simplicity) and logarithmic function for parameter k. In other words :

N = n(k, I) = β 0 + β 1 log 2 (k) + β 2 I ( 12
)
To understand our choice of log function for h 1 , notice that when k-anonymity is used, it is assumed that the probability of re-identifying an individual is 1 k . For example, when k is 1, the probability of re-identification is 1 and the guaranteed privacy is 0. When k becomes 2, the probability of re-identification becomes 1 2 and the amount uncertainty about the identity of the individual increases from 0 (log1) to 1 (log2). However, this increase in uncertainty about the identity of individuals (privacy) is not the same as k changes from 99 to 100 because the probability changes from 1 99 to 1 100 . For this reason we use entropy (logk) of this uniform probability distribution (p = 1 k ) as the indicator for privacy protection.

Precision Estimate

To determine the payoff to the data user (see Eq( 6)) we need a metric to calculate P recision. A reasonable estimate on the amount of imprecision caused by anonymization depends on the data application. We have briefly discussed the nature of imprecision that can be introduced to the results of any SELECT query executed against an anonymized dataset elsewhere [START_REF] Adl | Privacy consensus in anonymization systems via game theory[END_REF] . In this paper we provide the precision estimates for a specific SELECT query type and consider this query as the data analysis purpose. Our SELECT query is of the following form:

Q i ≡ SELECT sensitiveAtt FROM T * WHERE q = v i
In this query sensitiveAtt represents the value of sensitive attribute, T * is the anonymized dataset, q is one of the quasi-identifiers, and v i is the i th possible value for attribute q. For example, a query Q 20 can be the following:

Q 20 ≡ SELECT disease FROM T * WHERE age = 20
Let |Q i (T )| denote cardinality of the result set of query Q i on dataset T . When Q i is run against T * , the result set Q i (T * ) contains two groups of records: a subset of them satisfy the condition q = v i and the rest of them are just included in the result because they are partitioned into the same equivalence class as the points with q = v i . The latter introduce some quantity imprecision in the result. LeFevre et al. [27] introduce an imprecision metric to find the best cuts while running the Mondrian algorithm [START_REF] Lefevre | Mondrian multidimensional k-anonymity[END_REF] on experimental datasets. After normalizing this metric, we define P recision as:

P recision(Q i , T * , T ) = |Q i (T )| |Q i (T * )| (where |Q i (T * )| > 0) (13)
As a result, to calculate P recision we first need to estimate |Q i (T )| and |Q i (T * )|. Let P r i denote the portion of the records in the dataset that have value v i for quasi-identifier q. Then the expected value of |Q i (T )| is:

|Q i (T )| = P r i N (14)
Through Theorems 1 and 2 we provide an estimate for |Q i (T * )|. In Mondrian algorithm the minimum and maximum number of records in each equivalence class are k and 2d(k -1) + m, where m denotes the maximum number of records with identical values for all quasi-identifiers [START_REF] Lefevre | Mondrian multidimensional k-anonymity[END_REF]. Since the distribution of equivalence class sizes are not known a priori, with a simplifying assumption of uniform distribution, we can estimate the average number of records in each equivalence class, ec AV G , as:

ec AV G = 2d(k -1) + m + k 2 Theorem 1.
If the average size of each equivalence class is determined by Eq [START_REF] Kleinberg | On the value of private information[END_REF], then the depth of the recursive calls, l, in Mondrian algorithm [START_REF] Lefevre | Mondrian multidimensional k-anonymity[END_REF] can be estimated as:

l = log 2 ( 2N 2d(k -1) + m + k ) (16)
Proof. (sketch) Mondrian algorithm starts with the original dataset as a single equivalence class and chooses the median value of one of the dimensions to recursively cut each equivalence class into two smaller ones. It stops when there is no more possible cuts for any of the equivalence classes. For this estimate, we assume that the algorithm stops at the point where the size of each class reaches ec AV G from Eq [START_REF] Kleinberg | On the value of private information[END_REF]. By solving the recursive definition, we get Eq [START_REF] Calzolari | Optimal design of privacy policies[END_REF]. A complete proof is available [START_REF] Adl | Privacy consensus in anonymization systems via game theory[END_REF].

Theorem 2. If N denotes the number of records in a dataset T , the cardinality of the result set of query Q i on T * can be estimated as:

|Q i (T * )| = (1 - 1 2d ) l N ( 17
)
where d is the number of quasi-identifiers and l is the depth of recursive calls estimated in Theorem 1.

Proof. (sketch) The core idea of this proof is to note that during the partitioning process, for each equivalence class if the dimension q is chosen as the cutting dimension then half of the records in the class will be partitioned into a new class that will not be included in the result set of Q i . Otherwise the cut does not reduce the size of the result set. A complete proof is available [START_REF] Adl | Privacy consensus in anonymization systems via game theory[END_REF].

Consequently, P recision is defined as:

P recision = pr i N (1 -1 2d ) l N = pr i (1 -1 2d ) l (18)
We can also use Theorem 2 to define pr i based on the parameters. In real instances of the problem pr i is independent of any specific algorithm and estimates; it is a property of the dataset. However, since we have made some simplifying assumptions for other estimates the assumptions should also be applied to pr i to produce a meaningful estimate. Theorem 2 provides an estimate on |Q i (T * )|. When k = 1, there are no irrelevant records in the result set. Therefore, |Q i (T * k=1 )| provides an estimate on the number of records that satisfy the condition q = v i and |Q i (T * k=1 )|/N can be used as an estimate for pr i .

Consequently, we can refine Equation(18) as:

P recision = (1 -1 2d ) log2 2N m+1 (1 -1 2d ) l (19)

Subgame Perfect Equilibria

As explained in Sect. 5.1, the first step to find the game's subgame perfect equilibria is to determine the optimum incentive Î from Eq [START_REF] Jr | Data privacy through optimal k-anonymization[END_REF]. If the data collector accepts the offer Of = k, p with incentive I, his payoff will be:

U DC = (p -I)(β 0 + β 1 log 2 (k) + β 2 I) -C (20)
Calculating the derivative of U DC with respect to I and setting it to zero reveals the maximizing I:

dU DC dI = -(β 0 + β 1 log 2 (k) + β 2 I) + β 2 (p -I) = 0 ⇒ Î = β 2 p -β 1 log 2 (k) -β 0 2β 2 (21)
Î is the local maximum since the second derivative of the function is negative. The restriction here is I ≥ 0. If Î < 0, the maximizing I will be zero. The lower bound on I leads us to consider two separate cases:

Case 1:

β 2 p ≥ β 1 log 2 (k) + β 0 -In this case the amount of incentive that maximizes U DC is Î = β2p-β1log2(k)-β0 2β2
. Plugging Î into Eq [START_REF] Acquisti | Privacy and rationality in individual decision making[END_REF] gives us the maximum payoff to the data collector for Case 1 (denoted as Û 1 DC ):

Û 1 DC = β 2 4 (p + β 1 log 2 (k) + β 0 β 2 ) 2 -C (22)
The data collector will accept the offer Of = k, p if Û 1 DC ≥ 0. In other words, the data collector accepts if:

p + β 1 log 2 (k) β 2 ≥ 4C β 2 - β 0 β 2 (23)
Case 2: β 2 p < β 1 log 2 (k) + β 0 -The optimum incentive in this case would be Î = 0. With this incentive the maximum payoff to the data collector (denoted as Û 2 DC ) is:

Û 2 DC = p(β 0 + β 1 log 2 (k)) -C (24)
The data collector will accept this offer if Û 2 DC ≥ 0. More precisely, the data collector accepts the offer if:

p(β 0 + β 1 log 2 (k)) ≥ C (25)
If the values of Î (from the two cases) are plugged into Eq [START_REF] Sramka | A practice-oriented framework for measuring privacy and utility in data sanitization systems[END_REF], we can define the cardinality of the private dataset as a piecewise function of k and p:

N =              β0+β1log2(k)+β2p 2 if β 2 p ≥ β 1 log 2 (k) + β 0 ∧ p + β1log2(k) β2 ≥ 4C β2 -β0 β2 β 0 + β 1 log 2 (k) if β 2 p < β 1 log 2 (k) + β 0 ∧ p(β 0 + β 1 log 2 (k)) ≥ C 0 Otherwise (26)
If the new definition of N is plugged into the P recision function, precision becomes a function of k and p. As a result, U DU from Eq(6) becomes a function of k and p. The best strategy for the data user is to compute k and p according to Eq [START_REF] Machanavajjhala | Personalized social recommendationsaccurate or private?[END_REF]. The optimum offer is Of = δ, p and this completes the process of finding perfect equilibria. (e) the effect of privacy protection level on data providers' decision β1; (f) the effect of incentive on data providers' decision β2.

Simulation Results

If the players of the game are rational and have the required information, the equilibria of the game would always conform to what Sect. 6.4 suggests because we used an analytical method to find the game's equilibria. In our proposed method, a dataset does not exist before the game is complete and the specifications of the collected dataset depend on the parameters chosen while the game is played. Therefore, running experiments on real databases does not provide meaningful results for this work. Alternatively, we choose to simulate the game and visualize the results by testing multiple parameter settings using MATLAB R2008a. In every setting, the effect of one of the parameters a, C,d, m, and β is examined on the stable values of k (while the values of the rest of the parameters are fixed to β 0 = 7000, β 1 = 2000, β 2 = 20, a = $10, C = $20, 000, m = 5, and d = 4). The results are shown in Fig. 2.

The values for a and C are randomly selected as an estimate of reasonable values commonly used in real instances of the problem. We assumed a population size of 55,000 potential data providers and the values selected for parameters β 0 , β 1 , and β 2 are chosen to reflect Westin's privacy indexes [START_REF] Kumaraguru | Privacy indexes: A survey of westins studies[END_REF]. Based on the maximum values of k (k = 100) and p (p = a), β 1 and β 2 are chosen such that the effect of maximum privacy is almost the same as maximum incentive. The value of β 0 is chosen such that 17% of the data providers fall in the privacy unconcerned category [START_REF] Kumaraguru | Privacy indexes: A survey of westins studies[END_REF].

Figure 2(a) shows how stable values of k increase as the number of quasi-identifiers increase. To understand the reason, we have provided another diagram in Fig. 3(a) which illustrates the precision curves for different values of d. According to this figure, with fewer quasi-identifiers the precision curve decreases at a higher rate. Therefore, as the number of quasi-identifiers increase, offering larger values for k becomes a better option for the data user since it can increase the size of the dataset without severely affecting data quality.

In Fig. 2(b) we can see the effect of m (maximum number of data providers with identical quasi-identifier values) on the stable values of k. We have chosen the values of m from {1, ..., 30}. As the value of m increases the stable value of k increases. To understand this counter-intuitive result, notice that as m increases less generalization will be needed to group the tuples in equivalence classes of size k. Therefore, compared to the cases with smaller m, the same precision can be achieved with higher values of k. Larger values of k attract more data providers without largely affecting the precision of query results and consequently, the data user can make more profit in this case.

The effects of anonymization, and maintenance cost (C) on stable values of k are illustrated in Fig. 2(c). Based on the settings chosen for other parameters, after a certain point the cost becomes too high for condition of the Eq(25) to be satisfied and case 1 (from Sect. 6.4) happens. In this case, the data collector is receiving a payment high enough to announce non-zero incentives. This incentive convinces several privacy concerned data providers to participate even with a low privacy protection level. As a result, the data user simply asks for no privacy protection since he is confident that enough data providers will participate to receive the incentive. Finally, after a certain value for C, the game reaches a point (demonstrated by a shaded rectangle) where no combination of k, p can be found that is acceptable by the data collector and U DU ≥ 0. This situation represents an instance of impractical anonymization.

Figures 2(d), 2(e), and 2(f) represent the effects of data providers' privacy attitude on stable values of k. According to Fig. 2(d) as the number of privacy unconcerned group (data providers who provide their personal information without any privacy or incentive) increase, the data user can receive larger volume of data without asking for sanitized dataset. By increasing the value of β 1 we model a privacy aware population. As can be seen in Fig. 2(e), when privacy has more significant impact on data providers' decisions, data will be sanitized with larger values of k. In Fig. 2(f) we showed how the value of β 2 impacts stable values of k. If β 2 is less than a certain level then it mostly affects the price of information and not the level of privacy protection. However if the weight of incentive on data providers' privacy decisions becomes heavier than a certain point, case 1 (refer to Sect. 6.4) happens and the data user can maximize his benefit by just increasing the price and asking for no privacy. These diagrams show how public's privacy awareness can force the firms to protect privacy of data providers. (f) Fig. 3. Changes to the stable k due to an increase in:?? the number of quasi-identifiers d; ?? the maximum number of data providers who have identical values for their quasiidentifiers m; ?? the cost of data sanitization, storage, and provision C; ?? in the number of privacy unconcerned data providers 0; ?? the e↵ect of privacy protection level on data providers' decision 1; ?? the e↵ect of privacy protection level on data providers' decision 1.

Conclusions and Future Work

In this paper we modeled the process of private data collection as a sequential game to achieve consensus on the level of privacy protection. We explained the general approach to solve the game and as an example provided the details of game analysis for k-anonymity. Players of the game are a data user, a data collector, and a group of data providers. We use the method of backward induction to explore the game's subgame perfect equilibria. Equilibria of the game suggest stable values of the privacy parameter that are unlikely to be changed when other parties move according to their equilibria strategies. For the k-anonymity case, we found the stable values of k and showed that these values are related to number of quasi-identifiers, maximum number of identical tuples (in their quasi-identifier values), cost of data sanitization and storage, and coefficients of public's privacy behavior model. Our results illustrate the significant impact of the number of quasi-identifiers on the decision about the value of k.

We are plannig to analyze other privacy definitions such as l-diversity [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF] and differential privacy [START_REF] Dwork | Differential privacy[END_REF] and for each privacy definition, distinguish the settings which make it the most profitable option to the players of the game. We are also planning to improve the model by dropping the assumption about the amount of information available to the data collector and data user. Our goal is to design a new evaluation framework that uses our game theoretic model to compare different anonymization methods and distinguish the settings that make one anonymization method more appealing than another.

Fig. 1 .

 1 Fig. 1. (a) The dynamics of setting a stable level for privacy protection. (b) Trimmed game tree.

Fig. 2 .

 2 Fig. 2. Changes to the stable k due to an increase in: (a) the number of quasi-identifiers d; (b) the maximum number of data providers with identical values for their quasi-identifiers m; (c) the cost of data anonymization and storage C; (d) the number of privacy unconcerned data providers β0; (e) the effect of privacy protection level on data providers' decision β1; (f) the effect of incentive on data providers' decision β2.

Fig. 4 .

 4 Fig. 4. Precision curves for di↵erent number of quasi-identifiers (d). The value of m is fixed by 5.

Fig. 5 .Fig. 3 .

 53 Fig. 5. Mondrian Algorithm

Our assumption of complete information does not mean that the data collector and the data user know privacy/incentive trade-off functions of each data provider because individual data providers are not directly modeled as players in the trimmed game tree.

Notice that N is also an increasing function of δ (see Eq[START_REF] Samarati | Generalizing data to provide anonymity when disclosing information[END_REF]) and therefore ∂ prec ∂ δ is not always greater than or equal to zero.