Privacy-Aware Data Cleaning-as-a-Service

A relation (table) $R$ with a schema $\mathcal{R}=\{A_{1},...,A_{n}\}$ is a finite set of $n$-ary tuples $\{{t}_{1},...,{t}_{N}\}$. A database (instance) $D$ is a finite set of relations $R_{1},...,R_{m}$ with schema ${\color[rgb]{0,0,0}\mathfrak{R}}=\{\mathcal{R}_{1},...\mathcal{R}_{m}\}$. We denote by small letters $x,y,z$ as variables. Let $A,B,C$ refer to single attributes and $X,Y,Z$ as sets of attributes. A cell $c=t[A_{i}]$ is the $i$-th position in tuple ${t}$ with its value denoted by $c.{\sf value}$. We use $c$ to refer to the value $c.{\sf value}$ if it is clear from the context. A functional dependency (FD) $\varphi$ over a relation $R$ with set of attributes $\mathcal{R}$ is denoted by $\varphi:X\rightarrow Y$, in which $X$ and $Y$ are subsets of $\mathcal{R}$. We say $\varphi$ holds over $R$, $R\models\varphi$, if for every pair of tuples ${t}_{1}$, ${t}_{2}$ $\in R$, ${t}_{1}[X]={t}_{2}[X]$ implies ${t}_{1}[Y]={t}_{2}[Y]$. Table 4 summarizes our symbols and notations.

A matching dependency (MD) $\phi$ over two relations $R$ and $R^{\prime}$ with schemata $\mathcal{R}=\{A_{1},A_{2},...\}$ and $\mathcal{R}^{\prime}=\{A^{\prime}_{1},A^{\prime}_{2},...\}$ is an expression of the following form:

Generalization replaces values in a private table with less specific, but semantically consistent values according to a generalization hierarchy. To generalize attribute $A$, we assume a set of levels $\mathcal{L}^{A}=\{l^{A}_{0},...,l^{A}_{h}\}$ and a partial order $\leq^{A}$, called a generalization relation on $\mathcal{L}^{A}$. Levels $l^{A}_{i}$ are assigned with disjoint domain-sets ${\sf dom}(l^{A}_{i})$. In $\leq^{A}$, each level has at most one parent. The domain-set ${\sf dom}(l^{A}_{n})$ is the maximal domain set and it is a singleton, and ${\sf dom}(l^{A}_{0})$ is the ground domain set. The definition of $\leq^{A}$ implies the existence of a totally ordered hierarchy, called the domain generalization hierarchy, ${\sf DGH}^{A}$. The domain set ${\sf dom}(l^{A}_{i})$ generalizes ${\sf dom}(l^{A}_{j})$ iff $l^{A}_{j}\leq l^{A}_{i}$. We use $h^{A}$ to refer to the number of levels in ${\sf DGH}^{A}$. Figures 1(a) and 2(a) show the DGH s for the medication and age attributes, resp. A value generalization relationship for $A$, is a partial order $\preceq^{A}$ on ${\sf Dom}^{A}=\bigcup{\sf dom}(l^{A}_{i})$. It specifies a value generalization hierarchy, ${\sf VGH}^{A}$, that is a tree whose leaves are values of the ground domain-set ${\sf dom}(l^{A}_{0})$ and whose root is the single value in the maximal domain-set ${\sf dom}(l^{A}_{n})$ in ${\sf DGH}^{A}$. For two values $v$ and $v^{\prime}$ in ${\sf Dom}^{A}$, $v^{\prime}\preceq^{A}v$ means $v^{\prime}$ is more specific than $v$ according to the VGH. We use $\preceq$ rather than $\preceq^{A}$ when the attribute is clear from the context. The VGH for the MED and AGE attributes are shown in Figures  1(b) and 2(b), respectively. According to VGH of MED, ibuprofen $\preceq$ NSAID.

A value is ground if there is no value more specific than it, and it is general if it is not ground. In Figure 1, ibuprofen is ground and analgesic is general. For a value $v$, its base denoted by ${\sf base}(v)$ is the set of ground values $u$ such that $u\preceq v$. We use $0\leq{\sf level}(v)\leq h^{A}$ to refer to the level of $v$ according to ${\sf VGH}^{A}$.

A general relation (table) is a relation with some general values and a ground relation has only ground values. A general database is a database with some general relations and a ground database has only ground relations. The generalization relation $\preceq^{A}$ trivially extends to tuples. We give an extension of the generalization relation to general relations and databases in Section 3.

The generalization hierarchies (DGH and VGH) are either created by the data owners with help from domain experts or generated automatically based on data characteristics [13]. The automatic generation of hierarchies for categorical attributes [14] and numerical attributes [15, 16, 17] apply techniques such as histogram construction, binning, numeric clustering, and entropy-based discretization [13].

We review generalized queries (GQs) to access values at different levels of the DGH [12].

Intuitively, answering a GQ involves finding the answers of $Q(R)$, and then generalizing these values to levels that match $L$. For a fixed size DGH, the complexity of answering $G$ is the same as answering $Q$.

The most well-known PPDP privacy model is $k$-anonymity that prevents re-identification of a single individual in an anonymized data set [9, 10].

As an example, Table 3 has two QI-groups, $\{g_{1},g_{2},g_{3}\}$ and $\{g_{4},g_{5},g_{6}\}$, and it is $k$-anonymous with $k=3$. $k$-anonymity is known to be prone to attribute linkage attacks where an adversary can infer sensitive values given QI values. Techniques such as (X,Y)-anonymity aim to address this weakness by ensuring that for each QI value in $X$, there are at least $k$ different values of sensitive values in attribute(s) $Y$ in the published (public) data [18].

The query $Q^{t}(R)$ in Definition 3 returns distinct values of attributes $Y$ that appear in $R$ with the values $t[X]$. Therefore, if the size of $Q^{t}(R)$ is greater than $k$ for every tuple $t$, that means every values of $X$ are linked with at least $k$ values of $Y$. Note that $k$-anonymity is a special case of (X,Y)-anonyity when $X$ is the set of QI attributes and $Y$ is the set of sensitive attributes that are also a key in $R$ [18].

The (X,Y)-anonymity model extends $k$-anonymity; if $Y$ is a key for $R$ and $X,Y$ are QI and sensitive attributes, respectively, then (X,Y)-anonymity reduces to $k$-anonymity.

The $l$-diversity privacy model extends $k$-anonymity with a stronger restriction over the $X$-groups [19]. A relation is considered $l$-diverse if each $X$-group contains at least $l$ “well-represented” values in the sensitive attributes $Y$. Well-representation is normally defined according to the application semantics, e.g., entropy $l$-diversity requires the entropy of sensitive values in each $X$-group to satisfy a given threshold [19]. When well-representation requires $l$ sensitive values in each $Y$ attribute, (X,Y)-anonymity reduces to $l$-diversity.

High quality data is a valuable commodity that has lead to increased purchasing and selling of data online. Data market services provide data across different domains such as geographic and locational (e.g., AggData [20]), advertising (e.g., Oracle [21], Acxiom [22]), social networking (e.g., Facebook [23], Twitter [24]), and people search (e.g. Spokeo [25]). These vendors have become popular in recent years, and query pricing has been proposed as a fine-grained and user-centric technique to support the exchange and marketing of data [26].

Given a database instance $D$ and query $Q$, a pricing function returns a non-negative real number representing the price to answer $Q$ [26]. A pricing function should have the desirable property of being arbitrage-free [26]. Arbitrage is defined using the concept of query determinacy [27]. Intuitively, $Q$ determines $Q^{\prime}$ if for every database $D$, the answers to $Q^{\prime}$ over $D$ can be computed from the answers to $Q$ over $D$. Arbitrage occurs when the price of $Q$ is less than that of $Q^{\prime}$, which means someone interested in purchasing $Q^{\prime}$ can purchase the cheaper $Q$ instead, and compute the answer to $Q^{\prime}$ from $Q$. For example, $Q(R)=\Pi_{Y}(R)$ determines $Q^{\prime}(R)=\Pi_{Y}(\sigma_{Y<10}(R))$ because the user can apply $Y<10$ over $Q(R)$ to obtain $Q^{\prime}(R)$. Arbitrage occurs if $Q$ is cheaper than $Q^{\prime}$ which means a user looking for $Q^{\prime}(R)$ can buy $Q$ and compute answers to $Q^{\prime}$. An arbitrage-free pricing function denies any form of arbitrage and returns consistent pricing without inadvertent data leakage [26]. A pricing scheme should also be history-aware [26]. A user should not be charged multiple times for the same data purchased through different queries. In such a pricing scheme, the data seller must track the history of queries purchased by each buyer and price future queries according to historical data.

By replacing a value $v^{\prime}$ in a relation $R$ with a generalized value $v$, there is necessarily some information loss. We present an entropy-based penalty function that quantifies this loss [28]. We then use this measure as a basis to define a distance function between two general values.

Intuitively, the entropy $H(X_{A}|X_{A}\in\textit{base}(v))$ measures the uncertainty of using the general value $v$. $E(v)$ measures the information loss of replacing values in $\textit{base}(v)$ with $v$. Note that $E(v)=0$ if $v$ is ground because $H(X_{A}|X_{A}\in\textit{base}(v))=0$, and $E(v)$ is maximum if $v$ is the root value $*$ in ${\sf VGH}^{A}$. $E(v)$ is monotonic whereby if $v\preceq v^{\prime}$, then $E(v)\leq E(v^{\prime})$. Note that the conditional entropy $H(X_{A}|X_{A}\in\textit{base}(v))$ is not a monotonic measure [28].

Intuitively, if $v$ is a descendant of $v^{\prime}$ or vice versa, i.e. $v\preceq v^{\prime}$ or $v^{\prime}\preceq v$, their distance is the the difference between their entropy-based penalties, i.e., $|E(v^{\prime})-E(v)|$. This is the information loss incurred by replacing a more informative child value $v$ with its ancestor $v^{\prime}$ when $v\preceq v^{\prime}$. If $v$ and $v^{\prime}$ do not align along the same branch in the VGH, i.e. $v\not\preceq v^{\prime}$ and $v^{\prime}\not\preceq v$, $\delta(v,v^{\prime})$ is the total distance between $v$ and $v^{\prime}$ as we travel through their least common ancestor $a$, i.e. $\delta(v,a)+\delta(a,v^{\prime})$.

The $\delta(v^{\prime}v)$ distance captures the semantic closeness between values in the VGH. We extend the definition of $\delta$ to tuples by summing the distances between corresponding values in the two tuples. The $\delta$ function naturally extends to sets of tuples and relations. We use the $\delta(v^{\prime}v)$ distance measure to define repair error in our evaluation in Section 7.

A (generalized) relation $R$ may contain generalized values that are syntactically equal but are semantically different and represent different ground values. For example, $g_{1}[{\sf AGE}]$ and $g_{2}[{\sf AGE}]$ in Table 3 are syntactically equal (containing [31,60]), but their true values in Table 3 are different, $m_{1}[{\sf AGE}]=51$ and $m_{2}[{\sf AGE}]=45$, respectively. In contrast, two syntactically different general values may represent the same ground value. For example, although analgesic and NSAID are different general values, they may both represent ibuprofen. The consistency between traditional FDs and a relation $R$ is based on syntactic equality between values. We present a revised definition of consistency with the presence of generalized values in $R$.

Given a generalized relation $R^{\prime}$ with schema $\mathcal{R}$, and FD $\varphi:A\rightarrow B$ with attributes $A,B$ in $\mathcal{R}$, $R^{\prime}$ satisfies $\varphi$ ($R^{\prime}\models\varphi$), if for every pair of tuples $t_{1},t_{2}$ in $R^{\prime}$, if $t_{1}[A]$ and $t_{2}[A]$ are equal ground values then $t_{1}[B]$ is an ancestor of $t_{2}[B]$ or vice-versa, i.e. $t_{1}[B]\preceq t_{2}[B]$ or $t_{2}[B]\preceq t_{1}[B]$. Since a general value $v$ encapsulates a set of distinct ground values in $\textit{base}(v)$, relying on syntactic equality between two (general) values, $t_{1}[B]$ and $t_{2}[B]$ is not required to determine consistency, since they may be syntactically different but represent the same ground value. Our definition requires that $t_{1}[B]$ be an ancestor of $t_{2}[B]$ (or vice-versa), which means they represent the same ground value. This definition extends to FDs $X\rightarrow Y$ with a set of attributes $X,Y$ in $\mathcal{R}$. The definition reduces to the classical FD consistency when $R^{\prime}$ is ground. Assuming VGHs have fixed size, consistency checking in the presence of generalized values is in quadratic time according to $|R^{\prime}|$.

Consider a client, CL, and a service provider, SP, with databases $D_{\textit{CL}},D_{\textit{SP}}$ containing single relations $R_{\textit{CL}},R_{\textit{SP}}$, respectively. Our discussion easily extends to databases with multiples relations. We assume a set of FDs $\Sigma$ defined over $R_{\textit{CL}}$ that is falsified. We use FDs as the benchmark for error detection, but our framework is amenable to other error detection methods. The shared generalization hierarchies are generated by the service provider (applying the techniques mentioned in Section 2.2). The problem of privacy-preserving data cleaning is twofold, defined separately for CL and SP. We assume a generalization level $l_{\max}$, which indicates the maximum level that values in our repaired database can take from the generalization hierarchy.

In our implementation, we check consistency $R^{\prime}_{\textit{CL}}\models\Sigma$ using the consistency definition in Section 3.2, and measure the distance $\delta(R^{\prime}_{\textit{CL}},R^{*}_{\textit{CL}})$ using the semantic distance function $\delta$ (Defn. 6).

Figure 3 shows the PACAS system architecture consisting of two main units that execute functions for CL and SP. Figure 3(a) shows the CL unit containing four modules. The first module finds equivalence classes in $R_{\textit{CL}}$. An equivalence class (eq) is a set of cells in $R_{\textit{CL}}$ with equal values in order for $R_{\textit{CL}}$ to satisfy $\Sigma$ [2]. The next three modules apply an iterative repair for the eqs. These modules select an eq, purchase accurate value(s) of dirty cell(s) in the class, and then repair the cells using the purchased value. If the repairs contain generalized values, the CL unit must verify consistency of the generalized relation against the defined FDs. The cleaning iterations continue until $\mathcal{B}$ is exhausted or all the eqs are repaired. We preferentially allocated the budget $\mathcal{B}$ to cells in an eq based on the proportion of errors in which the cells (in an eq) participate. Figure 3(b) shows the SP unit. The Record Matching module receives a request $r_{i}=(t,A,l)$ from CL, identifies a matching tuple $t^{\prime}$ in $R_{\textit{SP}}$, and returns $t^{\prime}[A]$ at the level $l$ according to the VGH. The Data Pricing and Validate Privacy module computes prices for these requests, and checks whether answering these requests will violate (X,Y,L)-anonymity in $R_{\textit{SP}}$. If so, the request is not safe to be answered. The Query Answering module accepts payment for requests, and returns the corresponding answers to CL.

Given an incoming CL request $r_{i}=(t,A,l)$, the SP must translate $r_{i}$ to a query that identifies a matching (clean) tuple $t^{\prime}$ in $R_{\textit{SP}}$, and returns $t^{\prime}[A]$ at level $l$. To answer each request, the SP charges the CL a price that is determined by the level $l$ of data disclosure and the adherence of $t^{\prime}[A]$ to the privacy model. To translate a request $r$ to a GQ $G_{r}$, we assume a schema mapping exists between $R_{\textit{SP}}$ and $R_{\textit{CL}}$, with similarity operators $\approx$ to compare the attribute values. This can be modeled via matching dependencies (MDs) in SP [5].

Recall from Section 2.4.1 that (X,Y,L)-anonymity extends (X,Y)-anonymity to consider the attribute domain semantics. Given a GQ, the SP must determine whether it is safe to answer this query, i.e., decide whether disclosing the value requested in $r_{i}$ violates (X,Y,L)-anonymity (defined in Defn. 4). In this section, we formalize the privacy guarantees of (X,Y,L)-anonymity, and in the next section, review the SafePrice data pricing algorithm that assigns prices to GQs to guarantee (X,Y,L)-anonymity.

(X,Y,L)-anonymity applies tighter privacy restrictions compared to (X,Y)-anonymity by tuning the parameter $L$ (determined by the data owner). At higher levels of $L$, it becomes increasingly more difficult to satisfy the (X,Y,L)-anonymity condition, while (X,Y,L)-anonymity reduces to (X,Y)-anonymity at $l_{i}=0$ for every $l_{i}\in L$. We formally state this in Theorem 5.1. (X,Y,L)-anonymity is a semantic extension of (X,Y)-anonymity. Similar extensions can be defined for PPDP models such as (X,Y)-privacy, $l$-diversity, $t$-closeness. Unfortunately, all these models do not consider the data semantics in the attribute DGHs and VGHs [11].

PPDP models have traditionally been used in non-interactive settings where a privacy-preserving table is published once. We take a user-centric approach and let users dictate the data they would like published. We apply PPDP in an interactive setting where values from relation $R_{\textit{SP}}$ are published incrementally according to (user) CL requests, while verifying that the disclosed data satisfies (X,Y,L)-anonymity [12]. We adopt a data pricing scheme that assigns prices to GQs by extending the baseline data pricing algorithm defined in [29] to guarantee (X,Y,L)-anonymity. We review this baseline pricing algorithm next.

Given a query $Q$ over a relation $R$ (a database with single relation $R$), the baseline pricing model determines the price of $Q$ based on the amount of information revealed about $R$ by answering $Q$. Let $\mathcal{I}$ be a set of possible relations that the buyer believes to be $R$, representing his initial knowledge of $R$. As the buyer receives answers to $Q(R)$, he gains new knowledge, allowing him to eliminate relations $R^{\prime}$ from $\mathcal{I}$, which provide a different answer $Q(R^{\prime})\neq Q(R)$. This set of eliminated instances $R^{\prime}$ is called the conflict set of $Q$ denoted as $\mathcal{C}_{Q}$, and intuitively represents the amount of information that is revealed by answering $Q$ (Figure 4). As more queries are answered, the size of $\mathcal{I}$ is reduced. We can apply a set function that uses $\mathcal{C}_{Q}$ to compute a price for $Q$. We can use the weighted cover set function with predefined weights assigned to the relations in $\mathcal{I}$. Query prices are computed by summing the weights for relations in $\mathcal{C}_{Q}$, which has been shown to give arbitrage-free prices [29]. In practice, the set $\mathcal{I}$ is usually infinite making it infeasible to implement. To circumvent this problem, a smaller, finite subset $\mathcal{S}$ called the support set is used to generate arbitrage-free prices [29]. The support set is defined as the neighbors of $R$, generated from $R$ via tuple updates, insertions, and deletions. The values that are used to generate the support set are from the same domain of the original relation $R$.

Several optimizations are applied to the baseline pricing, and its effectiveness is experimentally justified [29]. Most importantly, the relations in the support set can be modeled by update operations. That is, we generate each relation in $\mathcal{S}$ from $R$ by applying its corresponding update operation and use the resulting relation to compute the value of the weighted function as the final price. We roll-back the update to restore $R$, and continue this process to compute the weighted function using other relations in $\mathcal{S}$. We avoid storing all databases in $\mathcal{S}$ to enable more efficient price computations.

Algorithm 1 provides pseudocode of the baseline algorithm. The algorithm takes query $Q$, database $D$, a support set $\mathcal{S}$, and a weight function $w$, and computes the price to answer $Q$ over $R$. The baseline algorithm is history-aware as input $\mathcal{S}$ excludes databases that were already considered by past queries.

In Definition 7, $\mathcal{I}_{G}$ represents the set of relations that the buyer believes $R$ is drawn from after observing the answer $G(R)$. If there are at least $k$ tuples in the answer set of ${G}^{t}$ over $\mathcal{I}_{G}$, this indicates that the buyer does not have enough information to associate the values in $X$ to less than $k$ values of $Y$ at level $L$, thus preserving (X,Y,L)-anonymity. If the SP determines that a GQ is safe, he will assign a finite price relative to the amount of disclosed information about $R$.

Algorithm 2 presents the SafePrice details. The given support set $\mathcal{S}$ represents the user’s knowledge about relation $R$ after receiving the answer to past purchased queries. We maintain a set $\mathcal{S}_{G}$ that represents all admissible relations after answering $G$ and captures the user’s posterior knowledge about $R$ after answering $G$. We use $\mathcal{S}_{G}$ to check whether answering $G$ is safe. This is done by checking over instances in $\mathcal{S}_{G}$ whether values in $X$ are associated with at least $k$ values of $Y$ using the query ${G}^{t}$. The price for a query is computed by summing the weights of the inadmissible relations in the conflict set $\mathcal{C}_{G}=\mathcal{S}\setminus\mathcal{S}_{G}$ (Line 2). Similar to the baseline pricing, we use the support set $\mathcal{S}$ and admissible relations $\mathcal{S}_{G}$ rather than $\mathcal{I}$ and $\mathcal{I}_{G}$, respectively. We iterate over tuples $t\in R$ (Line 2), and check whether values in $X$ are associated with less than $k$ values in $Y$ over relations in $\mathcal{S}_{G}$. If so, we return an infinite price reflecting that query $G$ is not safe (Line 2).

Given the interactive setting between the CL and the SP, we must ensure that all (consecutively) disclosed values guarantee (X,Y,L)-anonymity over $R$. We ensure that SafePrice is history-aware by updating the support set $\mathcal{S}$ after answering each GQ. The SP uses the pricing function in Algorithm 2 to update $\mathcal{S}$ to reflect the current relations $R^{\prime}$ that have been eliminated by answering the latest GQ. The SP implements $\textit{AskPrice}(r_{i},R_{\textit{SP}})$ (cf. Figure 3) by translating $r_{i}$ to a GQ, and then invoking SafePrice.

We assume that requesting a query price is free. We acknowledge that returning prices might leak information about the data being priced and purchased. This problem is discussed in the data pricing literature, particularly to incentivize data owners to return trustful prices when prices reveal information about the data (cf. [30] for a survey on this issue). We consider this problem as a direction of future work.

A CL data request is executed via the $\textit{Pay}(p,r_{i},R_{\textit{SP}})$ method, where she purchases the value in $r_{i}$ at price $p$. The Query Answering module executes $\textit{Pay}(p,r_{i},R_{\textit{SP}})$ via SP accepts payment, translates $r_{i}$ to a GQ, and returns the answer over $R_{\textit{SP}}$ to CL. Lastly, SP updates the support set $\mathcal{S}$ to ensure SafePrice has an accurate history of disclosed data values.

We note that all communication between CL and SP is done via the AskPrice and Pay methods (provided by SP). We assume there is a secure communication protocol between the CL and SP, and that all data transfer is protected and encrypted. The model is limited to a single SP that sells data at non-negotiable prices. We intend to explore general cases involving multiple SP providers and price negotiation as future work.

For a fixed number of FDs $\Sigma$, the problem of finding minimal-cost data repairs to $R_{\textit{CL}}$ such that $R_{\textit{CL}}$ satisfies $\Sigma$ is NP-complete [2]. Due to these intractability results, we necessarily take a greedy approach that cleans cell values in $R_{\textit{CL}}$ that maximally reduce the overall number of errors w.r.t. $\Sigma$. This is in similar spirit to existing techniques that have used various weighted cost functions [2, 35] or conflict hypergraphs [33] to model error interactions among data dependencies in $\Sigma$.

Given $R_{\textit{CL}}$ and $\Sigma$, we identify a set of error cells that belong to tuples that falsify some $\sigma\in\Sigma$. For an error cell $e\in\mathcal{E}$, we define eq($e$) as the equivalence class to which $e$ belongs. An equivalence class is a set of database cells with the same value such that $\Sigma$ is satisfied [2]. We use eqs for two reasons: (i) by clustering cells into eqs, we determine a repair value for a group of cells rather than an individual cell, thereby improving performance; and (ii) we utilize every cell value within an eq to find the best repair.

The SafeClean algorithm repairs FD errors by first finding all the eqs in $R_{\textit{CL}}$. The algorithm then iteratively selects an eq, and purchases the true value of a cell, and updates all dirty cells in the same class to the purchased value. The SP may decide that returning a generalized value is preferred to protect user sensitive data in $R_{\textit{SP}}$. If so, then the CL must validate consistency of its data including these generalized values. At each iteration, we repair the eq class with cells that participate in the largest number of FD errors. At each iteration, SafeClean assigns a portion of the budget $\mathcal{B}$ that is proportional to the number of errors relative to the total number of errors in $R_{\textit{CL}}$ (this new extension to SafeClean is discussed in Section 6.4). SafeClean continues until all the eqs are repaired, or the budget is exhausted.