Inference-Proof Updating of a Weakened View Under the Modification of Input Parameters

Within a framework of cooperating with partners and sharing resources with them, managing the fundamental asset of own information – whether personal or institutional – has evolved as a main challenge of IT-security, leading to diverse computational techniques to enforce all kinds of an owner’s interests. This includes confidentiality-preserving data publishing [8] aiming at hiding specific pieces of information while still providing sufficient availability. One class of techniques for confidentiality-preserving data publishing distorts data by weakening the still true information content of released data, e.g., by explicitly erasing sensitive data or by substituting sensitive data items by suitably generalized ones, as for instance applied for k-anonymization with l-diversification [12, 15, 17].

Whereas the effectiveness of many such techniques relies on the appropriateness of more or less intuitive concepts, like, e.g., quasi-identifiers, our own approach has more ambitiously been based on a fully formalized notion of semantic confidentiality in terms of inference-proofness. This notion considers an authorized receiver that profits from some background knowledge and unlimited computational resources for rational reasoning. More specifically, in previous work [4] we conceptually designed a two-stage view generation procedure that weakens the information content of an actually stored relation instance, and we verified the requested confidentiality property and experimentally evaluated the runtime efficiency. This procedure takes three input parameters, (i) a confidentiality policy consisting of prohibitions in the form of pieces of information that the pertinent receiver of the view should not be able to learn, (ii) the assumed background knowledge of that receiver in the form of single-premise tuple-generating data dependencies, and (iii) the actually stored relation instance.

Example 1

(weakened view). Let R be a relation symbol (table name) with three attributes (columns) with (conceptually) countably infinite domains, having the current relation instance \(r = \{ (a,b,c), (a,c,c), (b,a,c)\}\) under closed-world assumption. Expressed in terms of first-order logic as a basis for formal semantics of relational databases [1], this means that the three ground atoms R(a, b, c), R(a, c, c) and R(b, a, c) are evaluated to \( true \), whereas all other syntactically possible ground atoms are considered to be evaluated to \( false \). For the moment still neglecting background knowledge, let us further suppose that the data owner wants to prohibit that the anticipated receiver of the view to be generated could ever learn that R(a, b, c) is \( true \), and so for R(a, b, d). Obviously, that view should not reveal that the tuple (a, b, c) is an element of the relation instance r.

The view generation procedure of [4] achieves this goal as follows. In the first stage, only treating the considered prohibitions, the procedure forms a disjunctive template \(R(a,b,c) \vee R(a,b,d)\) (notably, the truth evaluation of which is not prohibited to be known). In the second stage, the procedure checks each ground atom that is \( true \) in the instance whether it entails a disjunctive template. If this is the case the procedure replaces the ground atom by all those templates, thus weakening the originally complete information about the ground atom into still \( true \) disjunctions. Thus, so far, the view consists of the (distorted) disjunctive part \(R(a,b,c) \vee R(a,b,d)\) and the (untouched) positive part formed by R(a, c, c) and R(b, a, c). Moreover, these parts are complemented by an (adapted) negative part that replaces the original closed-world assumption by a first-order sentence intuitively expressing that any ground atom that does not entail any element of the disjunctive part and of the positive part should be evaluated to \( false \):

The weakened view consisting of the three parts does not entail any of the prohibited sentences. Moreover, capturing the receiver’s assumed awareness of the control mechanism, the view is even inference-proof in the sense that for each prohibited sentence \(\varPsi \) there is a fictitious “alternative” relation instance \(r^{\varPsi }\) that would generate the same view as r and make \(\varPsi \) \( false \). In fact, after seeing the view and in particular learning the truth of the disjunction \(R(a,b,c) \vee R(a,b,d)\), the receiver can not distinguish whether only R(a, b, c) is \( true \) or only R(a, b, d) is \( true \) or both R(a, b, c) and R(a, b, d) are \( true \).

Visualization of the problem of confidentiality-preserving view updating

Full size image

Considering the situation roughly visualized in Fig. 1, in the present work we address and solve the problem of efficiently updating a released weakened view under a modification of the input parameter values, while continuously enforcing the confidentiality policy, i.e., without revealing a prohibited piece of information, neither for the updated view nor retrospectively for the previous versions of the view. Conservatively assuming that the receiver is aware of the specification of both the view generation procedure and the updating procedure and, additionally, of the declared confidentiality policy – and thus of the whole security configuration consisting of the policy and the background knowledge – the main challenge has been to block all meta-inferences that the receiver could draw by relating subsequent views. The wanted blocking is achieved by establishing sufficient indistinguishability between the actual, possibly harmful situation and a fictitious harmless situation.

In Sect. 2, besides briefly discussing related work, we identify some basic conditions for achieving our goal in a still intuitive style. Then, in Sect. 3 we introduce our formal framework in order to prepare for proving precise assurances about our solution. This solution is presented and analyzed in Sect. 4. Finally, in Sect. 5 we report on the practical efficiency of a prototype implementation.

Example 2

(instance modification). Continuing Example 1, let the owner now insert the tuple (a, b, d) into the relation instance r. The corresponding ground fact R(a, b, d) entails the disjunctive template \(R(a,b,c) \vee R(a,b,d)\), which however is already contained in the view, such that the view generation algorithm applied to the updated relation \(r'\) returns the same view as before, which per se appears to be harmless. However, if the receiver got informed about the mere fact of a successful insertion of a new tuple, by recognizing that nevertheless the view remained unchanged the receiver could figure out that originally only exactly one of the ground atoms R(a, b, c) and R(a, b, d) has been \( true \) and, thus, now both of them are \( true \). But this would violate the requested confidentiality.

Now, suppose we start with the instance \(r' = \{ (a,b,c), (a,c,c), (b,a,c),\) \( (a,b,d)\}\) and then the owner deletes first (a, b, c) and then (a, b, d). At the beginning and also after the first deletion, the respective views are the same as above. But after the second deletion, the disjunction \(R(a,b,c) \vee R(a,b,d)\) is removed from the view and the negative part is suitably adapted. Again, if the receiver got informed about the mere fact of two successful deletions, by recognizing that first the view remained unchanged and then the disjunction was dropped, the receiver could figure out that originally both ground atoms R(a, b, c) and R(a, b, d) have been \( true \). But this would violate the requested confidentiality.

Such a kind of challenge has been identified earlier for diverse and only partially comparable settings, briefly and selectively classified in the following and further surveyed in Table 1; see also Sect. 6 of [8]. The owner’s data might be either a relation instance focused on individuals [2, 7, 11, 16, 18,19,20] or, more generically, any logic-oriented knowledge or belief base which includes any relation instance under closed world assumption (this work, [3, 5, 6]). The protection need might refer to either the values of a sensitive attribute [2, 7, 11, 16, 18,19,20] or a suitable class of sentences in the underlying logic (this work, [3, 5, 6]), aiming at either a suitably strengthened version of l-diversity (with match-uncertainty [11]) or a general notion of continuous semantic indistinguishability, respectively. Similarly, the background knowledge might dedicatedly consist of either the population concerned [2, 7, 11, 16, 18,19,20] (under uniform publication procedures [11]) or, more generically, of a suitable class of sentences in the underlying logic (this work, [3, 5, 6]). Regarding modifications, there might be either none but only sequential releases of different views [18, 20] or independently by other publishers [11], or insertion of tuples only  [7, 16] or both insertion and deletion of tuples [19] or, additionally, also value modification [2, 3, 5] or belief modification [6] or transactional modifications of not only the instance but also of the background knowledge and the confidentiality policy (this work). The modification request might be issued by either the information owner (this and most other work), or by the attacking receiver [3, 5, 6], as already earlier studied for mandatory multilevel databases with polyinstantiation. And the main distortion kind might be either lying [3] or refusals [5, 6] or value generalization [2, 7, 11, 16, 18,19,20] or weakening by disjunctions (this work), the three latter ones possibly complemented by either restricted lying by fake tuples [2, 19] or sampling and noise addition [11] or restricted refusals (this work).

Example 3

(policy modification). Again extending Example 1, let the owner now specify R(a, c, c) as a new prohibition in the confidentiality policy. The first stage of the view generation procedure would aim at forming a disjunctive template covering the specified new prohibition and also being disjoint from all other templates. To achieve these goals, the procedure has to select an additional (artificial) prohibition, say R(b, c, c), and might then add \(R(a,c,c) \vee R(b,c,c)\) as a further disjunctive template. Since the tuple (a, c, c) is an element of the relation instance r, the ground fact R(a, c, c) should no longer appear in the positive part of the modified view generated in the second stage. Instead, the weakening disjunction \(R(a,c,c) \vee R(b,c,c)\) should become a further element of the disjunctive part, with the negative part being suitably adapted.

However, if the receiver could be sure that the relation instance r has not been modified, he would still know that R(a, c, c) is \( true \). This would violate the new prohibition and, thus, the weakening would be useless. In other words, if previous knowledge about the instance already indicates a violation of the modified policy, then inference-proofness of the updated view can not be achieved. This problem can be resolved by requiring that each modification of the confidentiality policy occurs as part of a transaction that might also comprise instance modifications, and thus previous knowledge about the instance could be no longer be valid.

More generally, also dealing with background knowledge as discussed below, we will show that always leaving the receiver uninformed about the kind of the requested modifications – in particular uncertain about additional instance modifications that are not reflected in the new weakened view – is sufficient to enforce the wanted notion of confidentiality. The examples considered so far together with the claimed generalized insights indicate that the underlying view generation procedure enjoys reasonable robustness regarding modifications of the instance and the policy. This behavior mainly results from two fundamental features of the overall approach: the two-stage design dealing with the policy and the instance separately, and the strict isolation of the three parts of a weakened view regarding entailments. However, achieving this isolation in the presence of background knowledge, so far neglected, requires quite subtle considerations presented in [4] and in more detail in [14].

In particular, and only briefly sketched, background knowledge affects the forming of disjunctive templates in the first stage of the view generation procedure in two ways. First, it might become necessary to introduce further prohibitions, which in particular strengthens the needs to clean the (extended) policy from redundancies. Second, the background knowledge has to be partitioned regarding unwanted joint entailment effects such that, roughly described, disjunctive templates have to be formed of suitably “independent” prohibitions that are not affected by sentences of the same partition block. In more general terms, the set of disjunctive templates might be modified. Moreover, in some cases the weakened view has to additionally comprise a refused part consisting of so-called refusals, i.e., sentences whose truth evaluations are explicitly denied whatever the stored relation might look like.

Example 4

(background modification). Again continuing Example 1, let now the database application have been changed such that in future all relation instances will satisfy the data dependency \(R(a,b,d) \Rightarrow R(c,c,c)\). Moreover, let the owner assume that the receiver can henceforth exploit this dependency as his background knowledge. As known to him by the negative part of the view, \((a,b,d) \not \in r\) and thus the premise of the dependency is not \( true \). So, at first glance the dependency seems to be not helpful for the receiver. A second thought, however, easily indicates that the following inference would be enabled.

Since also \((c,c,c) \not \in r\) and thus the conclusion R(c, c, c) of the dependency is not \( true \) as well, applying the dependency in contraposition, i.e., \( \lnot R(c,c,c) \Rightarrow \lnot R(a,b,d)\), the receiver can learn that R(a, b, d) is \( false \). Thus, given the truth of the disjunction \(R(a,b,c) \vee R(a,b,d)\), the receiver can conclude that R(a, b, c) is \( true \). Hence, without suitable further precautions, the confidentiality policy would be violated. In fact, the underlying view generation procedure would already treat the conclusion R(c, c, c) as a further prohibition.

The insights gained from the given examples and the lessons learnt from elaborating the above sketched solutions lead to the following list of conditions for inference-proof view updating:

• C1: (only) conflict-free requests: An initial input control checks whether a modification request of the owner consists of insertions and deletions that are not conflicting. In particular, an item should not be required to be both inserted and deleted within the same modification request, and the items to be modified should be consistent.

• C2: (only) transactions: The accepted inputs of the owner are processed as a transaction with semantics that lead to either a commit (all temporary modifications of the relation instance and the security configuration are made persistent) or an abort (the relation instance and the security configuration remain unchanged, i.e., all temporary actions are rollbacked).

• C3: (only) possibly comprehensive transactions: Extending condition C2, additionally, (from the point of view of the receiver) the inputs for each transaction might be comprehensive, i.e., they might always comprise all kinds of modifications, i.e., simultaneously instance modifications, background modifications and policy modifications.

• C4: (only) state-related invariants: Each invariant whose satisfaction is checked for the final decision on either committing or aborting the transaction only refers to the preliminarily generated internal situation, but not to the relationship between the previous one and the still preliminary one.

• C5: notifications: The receiver is always notified about a request of the owner for modifications by either returning the updated weakened view or sending a note about an input rejection or a transaction abort, respectively.

• C5*: only notifications of effective and committed transactions: More restrictively, the receiver is notified about a request of the owner for modifications only if (i) the inputs are not rejected, (ii) the transaction has been committed and (iii) the view update has been effective, i.e., the weakened view has actually been changed. Otherwise, an owner’s input attempt is totally invisible to the receiver.

• C6: observability of the security configuration: The receiver can always learn the somehow “posted” current security configuration which includes the awareness of related requests for modification (but the receiver can never see the current relation instance nor requests for instance modifications).

For most applications, we see no need to inform the receiver about internal modification requests that do not actually change the published view. Accordingly, as expressed by condition C5*, it appears to be reasonable to completely hide the processing of requests that do change the external view. Technically, condition C5* would require to consider possibly differing local times of the owner and of the receiver, respectively. Then, to distinguish points in time local to the owner that are observable by the receiver and those points that are not, we would have to employ a rather complicated formal representation of our approach.

However, under the remaining conditions C1–C6 we can show that our view update procedure is inference-proof even if the receiver can observe the fact (but not the internal effects) of unsuccessful internal processing. Accordingly, to simplify the presentation by avoiding asynchronous local times, we will elaborate our approach based on conditions C1–C6, with a global discrete time for both agents, with points in time \(1,2,\dots \) used as synchronous timestamps.

Outline of the owner’s protection (upper part) against the anticipated receiver seen as a rational, omnipotent and too-curious attacker (lower part)

Full size image

We will formally define the basic concepts leading to the underlying view generation procedure, briefly summarize the assurances proved before in [4, 14], and introduce a precise notion of continuous inference-proofness to be enforced by the new view update procedure. Figure 2 outlines the framework.

3.1 Database Management System

We consider a relational database management system, which is operated under the control of the data owner. The system is based on a single relational schema, which comprises a fixed relation symbol (table name) R, a fixed finite set of attributes (column names) \(\mathcal {A}= \{ A_1, \ldots ,A_n \}\), each of which has the same infinite domain \( Dom \) of constants, and some possibly time-varying set \(SC_t\) of semantic constraints. At each point in time t the system maintains a database instance \(r_t\), which is a finite set of tuples over \(\mathcal {A}\) with values in \( Dom \), satisfying the current semantic constraints in \(SC_t\). Such an instance is treated as being complete: each tuple in \(r_t\) represents a fact that is true in some fictitious “real world”; whereas, by Closed World Assumption (CWA), each other tuple over \(\mathcal {A}\) with values in \( Dom \) represents a possible fact which is false in that world.

We follow a foundation of the relational model of data in terms of first-order logic with equality, as also used, e.g., in [1, 10]. Syntactically, the logic is specified by a language \(\mathscr {L}\) over \(\equiv \), R, \(\mathcal {A}\), \( Dom \), variables, propositional connectives and first-order quantifiers in the usual way. Semantically, for this logic we treat a database tuple \((a_1,\ldots ,a_n)\) as a ground fact \(R(a_1,\ldots ,a_n) \in \mathscr {L}\) and a database instance as a finite Herbrand interpretation of \(\mathscr {L}\) with the infinite universe \( Dom \) assuming unique names. Using an instance in this way, we can inductively assign a truth value to each sentence in \(\mathscr {L}\). This foundation also provides us with the pertinent notions of satisfaction and entailment: an instance r, seen as an Herbrand interpretation of the kind described above, satisfies a sentence \(\varPhi \in \mathscr {L}\) (r is a model of \(\varPhi \), \(r \models \varPhi \)) iff the truth evaluation according to r returns the truth value true; a set \(\mathcal {S} \subseteq \mathscr {L}\) of sentences entails a sentence \(\varPhi \in \mathscr {L}\) (\(\mathcal {S} \models \varPhi \)) iff each instance r satisfying \(\mathcal {S}\) also satisfies \(\varPhi \).

For confidentiality policies we employ the sublanguage \(\mathscr {L}_{exist}\) of existential facts, which are sentences in \(\mathscr {L}\) of the form \((\exists X_{i_1}) \ldots (\exists X_{i_m}) R(t_1,\ldots ,t_n)\) with pairwise different variables \(X_{i_1}, \ldots , X_{i_m}\) and terms \(t_{i_j} = X_{i_j}\) for \(i_j \in \{i_1, \ldots , i_m\}\) \(\subseteq \{1, \ldots ,n \}\) and \(t_i \in Dom \) otherwise. Such a sentence corresponds to a subtuple where the components for the attributes in \(\{A_{i_1}, \ldots , A_{i_m}\}\) are dropped. We also see ground facts (without any existentially quantified variables) as elements of \(\mathscr {L}_{exist}\). For weakening we employ the sublanguage \(\mathscr {L}_{exist}^{\vee }\) of strict and non-redundant disjunctions over \(\mathscr {L}_{exist}\), i.e., all sentences of the form \(\varPsi _1 \vee \varPsi _2 \vee \ldots \vee \varPsi _k\) such that \(k \ge 2\), \(\varPsi _i \in \mathscr {L}_{exist}\) and \(\varPsi _i \not \models \varPsi _j\) for \(i \not = j\).

3.2 Inference Control for Data Publishing

The database management system is protected by an inference control system for data publishing, which for each point in time t internally determines a receiver-specific current weakened view \(v_t\) on the current relation instance \(r_t\). The current view \(v_t\) also depends on the current security configuration, which consists of the currently assumed background knowledge \( prior _t \supseteq SC_t\) of the receiver, and the currently declared confidentiality policy \( ppol _t\) for the receiver.

The initial view \(v_1\) is generated by applying the underlying view generation procedure \( vgen \) [4, 14], i.e., \(v_1= vgen (r_1, prior _1, ppol _1)\). During its first still instance-independent stage, this procedure \( vgen \) also internally determines the initial set \( temp _1\) of disjunctive templates and the initial set \( refu _1\) of refusals.

All further weakened views \(v_t\), for times \(t > 1\), are determined by a view update procedure \( vupd \), to be presented in the remainder of this article, i.e., \(v_t = vupd (\, ({\scriptstyle \varDelta \!^+\!}r_t, {\scriptstyle \varDelta \!^-\!}r_t), ({\scriptstyle \varDelta \!^+\!} prior _t , {\scriptstyle \varDelta \!^-\!} prior _t), ({\scriptstyle \varDelta \!^+\!} ppol _t , {\scriptstyle \varDelta \!^-\!} ppol _t) \,)\). The following definition specifies the envisioned structure of such a procedure.

Definition 1

(specification of view update procedure). At times \(t=2,3,\dots \) a view update procedure \( vupd \) determines a weakened view \(v_t = vupd (\, ({\scriptstyle \varDelta \!^+\!}r_t, {\scriptstyle \varDelta \!^-\!}r_t), ({\scriptstyle \varDelta \!^+\!} prior _t , {\scriptstyle \varDelta \!^-\!} prior _t), ({\scriptstyle \varDelta \!^+\!} ppol _t , {\scriptstyle \varDelta \!^-\!} ppol _t) \,)\), based on the previous internal owner state, defined by

and satisfying the following conditions:

• The previous internal state \( own _{t-1}\) is accessible for the view update procedure \( vupd \), but more aged internal states are not memorized.

• The explicit input parameter values \(({\scriptstyle \varDelta \!^+\!}r_t, {\scriptstyle \varDelta \!^-\!}r_t)\), \(({\scriptstyle \varDelta \!^+\!} prior _t , {\scriptstyle \varDelta \!^-\!} prior _t)\) and \(({\scriptstyle \varDelta \!^+\!} ppol _t , {\scriptstyle \varDelta \!^-\!} ppol _t)\) for the requested modifications are internally specified by the owner, for each parameter indicating which elements are to be inserted in and which elements are to be deleted from the previous state.

• A requested modification is actually accepted and committed only if (i) the input parameter values are conflict-free and (ii) all pertinent invariants expressed in terms of a state are maintained; otherwise the request would be rejected or aborted, respectively.

• The components of the internal state are updated as follows:

  • \( ppol _t ~:= [\, ppol _{t-1} ~\,\cup ~ {\scriptstyle \varDelta \!^+\!} ppol _t\,] ~~\setminus ~ {\scriptstyle \varDelta \!^-\!} ppol _t\) ;

  • \( prior _t := [\, prior _{t-1} \cup ~ {\scriptstyle \varDelta \!^+\!} prior _t\,] ~\setminus ~ {\scriptstyle \varDelta \!^-\!} prior _t\) ;

  • \(r_t := [\,r_{t-1} \,\cup ~ {\scriptstyle \varDelta \!^+\!}r_t\,] ~\setminus ~ {\scriptstyle \varDelta \!^-\!}r_t\) ;

  • \( temp _t\) and \( refu _t\) are assigned the same results as the underlying view generation procedure \( vgen \) would do in its first stage;

  • \(v_t\) is assigned the return value of the view update procedure \( vupd \).

• The receiver always gets notified about the fact of a modification request.

Cautiously assuming condition C5 and suspecting the memorization of the full history, the observable effects of initial view generation and repeated view updates on the side of the receiver are represented by the sequence of current attacker states, each of them defined by \( att _{t} = (v_{t}, temp _{t}, refu _{t}, prior _{t}, ppol _{t}).\)

3.3 The Underlying View Generation Procedure

The underlying view generation procedure \( vgen (r, prior , ppol )\) [4, 14] takes three inputs from the owner: a relation instance r, the assumed background knowledge \( prior \) of the receiver, and the confidentiality policy \( ppol \) for that receiver. During a first, still instance-independent stage, a subprocedure \( vgen\_stage1 ( prior , ppol )\) internally determines a set \( temp \) of disjunctive templates and a set \( refu \) of elements stemming mainly from \( ppol \) and leading to refusals. In a second, instance-dependent stage, a subprocedure \( vgen\_stage2 ( temp , refu ,r)\) generates a weakened view v that consists of four parts: the refused knowledge \(v^? := refu \), the positive knowledge \(v^+\), the disjunctive knowledge \(v^\vee \), and the negative knowledge \(v^-\). In order to avoid inferences based on the editorial representation of these parts some final normalization based on standardized sorting is due. Accordingly, the view generation procedure has the following overall structure:

PROCEDURE \( vgen (r, prior , ppol )\)  {

\(( temp , refu ) := vgen\_stage1 ( prior , ppol )\);

\( (v^? , v^+ , v^\vee , v^- ) := vgen\_stage2 ( temp , refu ,r)\);

\(v := norm ( v^?, v^+ , v^\vee , v^- )\);

notify receiver by sending v  }

Employing first-order logic, all items are formalized by means of suitable subsets of \(\mathscr {L}\). Capturing the intuitions and our goals on the one hand and facing the well-known difficulty of the computational unsolvability of the general entailment problem for the full first-order logic language \(\mathscr {L}\) on the other hand, see, e.g., [13], we will apply the conventions summarized in the following.

Regarding the input parameters:

• The relation instance r is seen as a finite set of ground facts of the form \(R(a_1,\dots ,a_n)\), complemented with a pertinent completeness sentence Comp(r); i.e., for \(r = \{ (a_{1,1},\ldots ,a_{1,n}) , \ldots , (a_{m,1},\ldots ,a_{m,n})\}\) we get

  $$\begin{aligned} (\forall X_1)\dots (\forall X_n)[\bigvee _{(a_{j,1},\ldots ,a_{j,n}) \in r} \,\,\,( \bigwedge _{i \in \{ 1, \ldots ,n \} } X_i \equiv a_{j,i} ) \,\,\, \vee \lnot R(X_1,\dots , X_n)\,]. \end{aligned}$$

• Establishing knowledge about the relationship of one single fact with another single fact, the background knowledge \( prior \) is a finite set of single-premise tuple-generating dependencies [1] of the syntactic form^{Footnote 1}

  $$\begin{aligned} (\forall X_1)\dots (\forall X_k)\, [ \, R(t_1,\dots , t_n) \Rightarrow (\exists Y_1)\dots (\exists Y_l) \, R(\bar{t}_1,\dots ,\bar{t}_n) \,]\,, \end{aligned}$$

  (2)

  where \(X_1,\dots ,X_k,Y_1,\dots ,Y_l\) are pairwise different variables, each universally quantified variable \(X_i\) occurring exactly once in \(R(t_1,\dots , t_n)\) and at most once in \(R(\bar{t}_1,\dots ,\bar{t}_n)\), each existentially quantified variable \(Y_j\) occurring exactly once in \(R(\bar{t}_1,\dots ,\bar{t}_n)\), and – preferably to avoid an overall refusal – in both \(R(t_1,\dots , t_n)\) and \(R(\bar{t}_1,\dots ,\bar{t}_n)\) at least one constant of \( Dom \) occurs.

• The confidentiality policy \( ppol \subset \mathscr {L}_{exist}\) is a finite set of existential facts.

Regarding the first stage, further outlined below:

• As far as possible, the finite set \( temp \) of disjunctive templates with \( temp \subset \mathscr {L}_{exist}^{\vee }\) should only be formed by elements of the confidentiality policy, covering all of them. Moreover, all disjunctions seen together should be mutually independent in the following sense: for each two different disjunctions \(\varPsi _1 \vee \varPsi _2 \vee \ldots \vee \varPsi _k\) and \(\bar{\varPsi }_1 \vee \bar{\varPsi }_2 \vee \ldots \vee \bar{\varPsi }_{\bar{k}}\) we have \(\varPsi _i \not \models \bar{\varPsi }_{j}\) and \(\bar{\varPsi }_{j} \not \models \varPsi _i\).

• The finite set \( refu \) of refusals contains selected policy elements and possibly further prohibition sentences and, thus, \( refu \subset \mathscr {L}_{exist}\).

Regarding the second stage:

• The refused knowledge is instance-independent and just comprises the refusals determined in the first stage, i.e., \(v^? := refu \).

• The positive knowledge gathers all ground facts (tuples) of the relation instance r that entail neither a refusal nor a disjunctive template, i.e., \(v^+ := \{\, \varPhi \, | \, \varPhi \in r \text{ and } \text{ for } \text{ all } \varPsi \in refu : \varPhi \not \models \varPsi , \text{ for } \text{ all } \tau \in temp : \varPhi \not \models \tau \}\).

• The disjunctive knowledge \(v^\vee \) is formed as follows. As far as needed for confidentiality, a ground fact (tuple) \(R(a_1,\ldots ,a_n)\) in the relation instance r is disjunctively weakened by replacing it in a context-free way by a disjunction \(\varPsi _1 \vee \varPsi _2 \vee \ldots \vee \varPsi _k\) taken from the previously, in the first stage determined set of disjunctive templates \( temp \) such that \(R(a_1,\ldots ,a_n) \models \varPsi _1 \vee \varPsi _2 \vee \ldots \vee \varPsi _k\). In fact, in order to conveniently capture many simultaneous threats to confidentiality, the replacement is performed with all such disjunctions. Formally, \(v^{\vee } := \{\, \tau \, | \, \tau \in temp \text{ and } \text{ there } \text{ exists } \varPhi \in r: \varPhi \models \tau \,\}\)^{Footnote 2}.

• The negative knowledge consists of the suitably adapted pertinent completeness sentence, i.e., \(v^- := Comp(\,v^+, v^{\vee }, temp , refu \,)\).

Direct and transitive data flows and control flow in stage 1

Full size image

The first stage, which is still independent of r, can be further outlined as follows, and as also visualized in Fig. 3:

1. 1.

   extend the policy by implicit prohibitions caused by a single dependency;

2. 2.

   clean the policy from semantically redundant prohibitions;

3. 3.

   reject (delete) conflicting prohibitions and establish refusals in \( refu \) instead;

4. 4.

   partition the set of dependencies according to interactions with prohibitions;

5. 5.

   respecting the partitioning, cluster prohibitions into admissible^{Footnote 3} groups;

6. 6.

   if possible, add synthetic prohibitions for completing a partial match;

7. 7.

   reject prohibitions remained isolated and establish additional refusals in \( refu \);

8. 8.

   form templates of \( temp \) as disjunctions, one for each group of the clustering.

3.4 Continuous Inference-Proofness

Intuitively, as inspired by [9] and closely following [3, 5, 6], a prohibition sentence \(\varPsi \in ppol _{t}\) is intended to express a strong semantic confidentiality requirement: from the point of view of the receiver, based on the explicitly returned pieces of data and the somehow “posted” security configurations, at all times \(t' \ge t\) it should appear to be possible that the prohibition sentence \(\varPsi \) has not been \( true \) at time t. In other words, even if \(\varPsi \) has actually been \( true \) in the (hidden) relation instance \(r_{t}\), the receiver should not be sure about this situation.

This intuition will be formalized as roughly outlined in the following. Based on (i) his (assumed) time-depending background knowledge \( prior _{1},\) \( prior _{2}, \dots , prior _{t'}\), (ii) his awareness of the time-depending confidentiality policy \( ppol _{1}, ppol _{2}, \dots , ppol _{t'}\), and (iii) the observed notifications of either rejection, abortion or commitment, including the weakened views \(v_{1}, v_{2}, \dots , v_{t'}\) – originating from the actual (hidden) initial instance \(r_1\) and the actual (hidden) instance modification parameters \({\scriptstyle \varDelta }r_2, {\scriptstyle \varDelta }r_3, \dots , {\scriptstyle \varDelta }r_{t'}\) –, the receiver can imagine that the same observations could result from a (fictitious) alternative instance \(r^{\varPsi }_1\) and (fictitious) instance modifications \({\scriptstyle \varDelta }r^{\varPsi }_2,\,{\scriptstyle \varDelta }r^{\varPsi }_3,\dots ,\,{\scriptstyle \varDelta }r^{\varPsi }_{t'}\) such that the then resulting (also fictitious) relation instance \(r^{\varPsi }_{t}\) does not satisfy \(\varPsi \).

Definition 2

(continuous (possibilistic) inference-proofness). Under conditions C1–C6, a view update procedure \( vupd \) according to Definition 1 continuously complements the view generation procedure \( vgen \) in an inference-proof way iff, from the point of view of the receiver:

  for each (hidden) initial relation instance \(r_1\),

  for each (known) initial background knowledge \( prior _1\),

  for each (known) initial confidentiality policy \( ppol _1\) and

    for each (totally hidden) sequence of instance modifications \({\scriptstyle \varDelta }r_2, {\scriptstyle \varDelta }r_3, \dots , {\scriptstyle \varDelta }r_{t'}\),

     for each (known) sequences of background modifications \({\scriptstyle \varDelta } prior _2,{\scriptstyle \varDelta } prior _3, \dots , \)

    \({\scriptstyle \varDelta } prior _{t'}\) and policy modifications \({\scriptstyle \varDelta } ppol _2,{\scriptstyle \varDelta } ppol _3, \dots , {\scriptstyle \varDelta } ppol _{t'}\)

        under the procedures \( vgen \) and vupd leading to

        the (known) attacker states \( att _{1}, att _{2}, \dots , att _{t'}\) and

        the (hidden) relation instance \(r_{t}\) at a point in time \(t \le t'\),

          for each prohibition sentence \(\varPsi \in ppol _{t}\)

there exists an “alternative hidden situation”, i.e., there exist a (fictitious) relation instance \(r^{\varPsi }_1\) and a (fictitious) sequence of instance modifications \({\scriptstyle \varDelta }r^{\varPsi }_2,\,{\scriptstyle \varDelta }r^{\varPsi }_3,\dots ,\,{\scriptstyle \varDelta }r^{\varPsi }_{t'}\) such that

1. 1.

   indistinguishability of the alternative hidden situation: under the procedures \( vgen \) and vupd, the instance parameters \(r^{\varPsi }_1\) and \({\scriptstyle \varDelta }r^{\varPsi }_2,\,{\scriptstyle \varDelta }r^{\varPsi }_3,\dots ,\,{\scriptstyle \varDelta }r^{\varPsi }_{t'}\) together with the background parameters \( prior _1\) and \({\scriptstyle \varDelta } prior _2,{\scriptstyle \varDelta } prior _3, \dots , {\scriptstyle \varDelta } prior _{t'}\) and with the policy parameters \( ppol _1\) and \({\scriptstyle \varDelta } ppol _2,{\scriptstyle \varDelta } ppol _3, \dots , {\scriptstyle \varDelta } ppol _{t'}\) generate the same notifications and the same attacker states \( att ^{\varPsi }_{1}= att _{1}, \, att ^{\varPsi }_{2} = att _{2}, \dots , \, att ^{\varPsi }_{t'} = att _{t'} \), in particular the same weakened views, i.e., regarding \(\varPsi \), the hidden items are indistinguishable from the fictitious items;

2. 2.

   credibility of the alternative situation: \(r^{\varPsi }_{j}\) satisfies \( prior _{j}\), for \(j=1,\dots ,t'\);

3. 3.

   harmlessness of the alternative situation: \(r^{\varPsi }_{t}\) does not satisfy \(\varPsi \).

If we restrict Definition 2 to the special case \(t'=1\), i.e., that only initially, at time 1, the view generation procedure \( vgen \) has been applied but subsequently no modifications have been requested, we just obtain the notion of (static) semantic confidentiality dealt with in our previous work [4, 14] and, thus, according to Theorem 1 and Theorem 2 of [4], the following proposition holds.

Proposition 1

The view generation procedure \( vgen \) (restricted to acceptable input parameter values) complies with static (possibilistic) inference-proofness, i.e., from the point of view of the receiver: for each (hidden) initial relation instance \(r_1\), for each (known) initial background knowledge \( prior _1\), for each (known) initial confidentiality policy \( ppol _1\), for each prohibition sentence \(\varPsi \in ppol _{1}\) there exists an “alternative hidden situation”, i.e., there exists a (fictitious) relation instance \(r^{\varPsi }_1\) such that

1. 1.

   indistinguishability of the alternative situation: under the procedure \( vgen \), \(r^{\varPsi }_1\) together with \( prior _1\) and \( ppol _1\) generates the same weakened view \(v_1\);

2. 2.

   credibility of the alternative situation: \(r^{\varPsi }_1\) satisfies \( prior _1\);

3. 3.

   harmlessness of the alternative situation: \(r^{\varPsi }_1\) does not satisfy \(\varPsi \).

Based on the informally stated conditions C1–C6 identified in Sect. 2 and the formal specifications outlined in Sect. 3, we are now ready to present our main contribution: a concrete view update procedure for weakened views and a verification of its compliance with continuous inference-proofness. As discussed in Sect. 2, to show inference-proofness under as weak conditions as reasonable, we define the procedure in accordance with condition C5 (notifications), such that the receiver gets notified about the fact of any owner request. However, for practical applications, we do not recommend to do so but, following condition C5*, to inform the receiver only about actually changed views. Moreover, condition C6 (observability of security configuration) is not explicitly expressed in the procedure but only employed in its verification assuming an utmost powerful attacking receiver.

PROCEDURE \( vupd (\, ({\scriptstyle \varDelta \!^+\!}r, {\scriptstyle \varDelta \!^-\!}r), ({\scriptstyle \varDelta \!^+\!} prior , {\scriptstyle \varDelta \!^-\!} prior ), ({\scriptstyle \varDelta \!^+\!} ppol , {\scriptstyle \varDelta \!^-\!} ppol ) \,)\) \(\,\{\)

IF modification requests are not conflict-free

   THEN notify owner in detail about the detected conflicts;

              notify receiver only about the mere fact of a conflict

   ELSE*****if there are no conflicts

      BEGIN_TRANSACTION

         \( own _{prev}\) := \( own \) ;

         \( prior := [\, prior \cup {\scriptstyle \varDelta \!^+\!} prior ] ~\setminus ~ {\scriptstyle \varDelta \!^-\!} prior \) ;

         \(r ~~~~~:= [\, r \cup {\scriptstyle \varDelta \!^+\!}r] ~\setminus ~ {\scriptstyle \varDelta \!^-\!}r\) ;

         IF invariants satisfied (here: \( prior \) is satisfied by r)

            THEN \( ppol ~:= [\, ppol \cup {\scriptstyle \varDelta \!^+\!} ppol ] ~\setminus ~ {\scriptstyle \varDelta \!^-\!} ppol \) ;

                       IF \(( prior _{prev}, ppol _{prev}) \ne ( prior , ppol )\)

                         THEN \(( temp , refu ) := vgen\_stage1 ( prior , ppol )\)  FI ;

                       IF \(( temp _{prev}, refu _{prev}, r_{prev}) \ne ( temp , refu , r)\)

                         THEN \((v^? , v^+ , v^\vee , v^- ) := vgen\_stage2 ( temp , refu ,r)\) ;

                                    \(v := norm (v^? , v^+ , v^\vee , v^- )\)  FI ;

                       commit (make all modifications persistent);

                       notify owner about commit ;

                       notify receiver about commit by sending v

            ELSE  abort (restore previous values of \( prior \) and r) ;

                       notify owner in detail about violation of invariants ;

                       notify receiver only about the mere fact of a violation 

         FI

      END_TRANSACTION

FI  \(\}\)

Construction of “alternative situations” regarding instance modifications

Full size image

Theorem 1

Procedure \( vupd \) complies with continuous inference-proofness in the sense of Definition 2.

Proof

Let the procedures \( vgen \) and \( vupd \) inductively determine a sequence of internal owner states \( own _{1}, own _{2}, \dots , own _{t'}\), as defined by (1) within Definition 1. Basically, besides dedicated arguments for conflicting parameter values and transaction abortion, for the standard case of transaction commitment we will apply Proposition 1 for each point in time individually, as indicated in Fig. 4.

More specifically, for \(j=1\), Proposition 1 directly ensures the existence of an “alternative situation” with the same notification.

Inductively, for \(j >1\), according to the declaration of \( vupd \) we have to distinguish three mutually excluding cases.

Case 1, parameter values conflicting: A conflict can only occur for the following reasons: contradictory insert and delete requests or inconsistent modification requests. Both an actual contradiction and an actual inconsistency could always be imagined to result from alternative fictitious ones, respectively, leading to the same notification and leaving the internal owner state unchanged, and thus the induction hypothesis applies.

Case 2, transaction aborted: The transaction for the modification of the instance and the security configuration is only aborted if the tentatively modified (known) background knowledge \( prior _j\) does not satisfy the tentatively modified (hidden) instance \(r_j\). So, there exists a single-premise tuple-generating dependency in \( prior _j\) that is violated by \(r_j\) and is of the form defined by (2) in Sect. 3.3, e.g.,

Accordingly, there exists a substitution \(\sigma \) that replaces the universally quantified variables \(X_1, \dots , X_k\) with the constants \(c_1, \dots ,c_k\) such that (i) \(\sigma [(t_1,\dots , t_n)] \in r_j\) but (ii) for all constant substitutions \(\tau \) of the existentially quantified variables \(Y_1, \dots , Y_l\) we have \(\tau [\sigma [(\bar{t}_1,\dots ,\bar{t}_n)]] \not \in r_j\).

This actual situation could also result from a fictitious instance modification regarding the fictitious instance \(r^{\varPsi }_{j-1}\) that requests to insert \(\sigma [(t_1,\dots , t_n)]\) and to delete all those (finitely many) \(\tau [\sigma [(\bar{t}_1,\dots ,\bar{t}_n)]]\) which have been in \(r^{\varPsi }_{j-1}\). Accordingly, the abort notification for the actual situation equals the abort notification for the fictitious situation. Moreover, in both situations the internal owner state and thus also the attacker state remains the same as at time \(j-1\) such that the induction hypotheses about the situation at time \(j-1\) immediately implies the assertion about time j.

Case 3, transaction committed: Consider the committed execution of

This execution first determines new components \( prior _j\), \( ppol _j\) and \(r_j\) for the internal state, and then determines the same updated view \(v_j\) as the view generation procedure \( vgen \) would have done applied to these components. Thus, according to Proposition 1, there exists an “alternative” fictitious instance \(r^{\varPsi }_j\) leading to the same view \(v_j\) under the procedure \( vgen \) applied to \( prior _j\), \( ppol _j\) and \(r^{\varPsi }_j\). Now, we observe that this fictitious instance \(r^{\varPsi }_j\) can also be obtained from the inductively assumed fictitious instance \(r^{\varPsi }_{j-1}\) by an instance modification request with parameter values

Then, the fictitious execution of

would also generate the same view \(v_j\) for the following reasons: by condition C3, these parameter values are possible, and by condition C4, the transaction would commit for these parameter values as well. Accordingly, the notification for the actual situation equals the notification for the fictitious situation.

We presented the view update procedure \( vupd \) in a straightforward way in order to facilitate its verification. However, we might attempt to replace the employed recomputation of the new internal state by means of the two subprocedures \( vgen\_stage1 \) and \( vgen\_stage2 \) of the underlying view generation procedure \( vgen \) by a more efficient incremental determination of the new internal state.

Regarding the subprocedure \( vgen\_stage1 \), the outline given in Sect. 3.3 and visualized by Fig. 3 already roughly indicates that the final results \( temp \) and \( refu \) depend on the inputs \( ppol \) and \( prior \) in a transitively dependent way, along the whole chain of the eight steps. For example, the insertion of a new prohibition into \( ppol \) might raise further extensions in step 1, which in turn might introduce new redundancies that in step 2 can trigger rather involved non-monotonic cleaning effects: a previously kept prohibition is sometimes removed in favor of a new prohibition, but sometimes it remains untouched causing the removal of new prohibitions as being redundant. The alternatives decided in step 2, adjusted by identifying refusals in step 3, further effects all succeeding steps, both by using the result of step 3 as direct input and indirectly via the transitive data flows, in particular incorporated by the partition generated in step 4. A more detailed analysis and corresponding options for optimized, partly incremental computations are beyond the scope of the present work.

Regarding the subprocedure \( vgen\_stage2 \), we can replace its simple call by essentially more refined operations if the results of the first stage, \( temp \) and \( refu \), have remained unchanged. This is an outline of an incremental approach:

• The instance-independent refused knowledge remains \(v^? := refu \).

• For updating the positive knowledge, basically only the elements of the input parameter value \(({\scriptstyle \varDelta \!^+\!}r, {\scriptstyle \varDelta \!^-\!}r)\) have to be processed, rather than the whole modified relation r, i.e., under the precondition \( {\scriptstyle \varDelta \!^+\!}r \cap {\scriptstyle \varDelta \!^-\!}r =\emptyset \), \(v^+ := [v_{prev}^+ \cup \, \{\, \varPhi \, | \, \varPhi \in {\scriptstyle \varDelta \!^+\!}r \text{ and } \text{ for } \text{ all } \tau \in temp \cup refu : \varPhi \not \models \tau \} \,] \setminus \,\, {\scriptstyle \varDelta \!^-\!}r\).

• For updating the disjunctive knowledge, similarly only the elements of the input parameter value \(({\scriptstyle \varDelta \!^+\!}r, {\scriptstyle \varDelta \!^-\!}r)\) have to be processed, i.e., \(v^{\vee } := [v_{prev}^{\vee } \, \setminus \,\, \{ \, \tau \, | \, \tau \in v_{prev}^{\vee } \text{ and } \text{ for } \text{ all } \varPhi \in r_{prev} \text{ with } \varPhi \models \tau :\varPhi \in {\scriptstyle \varDelta \!^-\!}r \} ] \cup \{\, \tau \, | \, \tau \in temp \text{ and } \text{ there } \text{ exists } \varPhi \in {\scriptstyle \varDelta \!^+\!}r: \, \varPhi \models \tau \,\}\).

• The completeness sentence for negative knowledge is adapted accordingly.

Experimental runtime comparison of the incremental and the straightforward recomputation (of stage 2) version of the view update procedure

Full size image

We also extended the prototype implementation of [4, 14] to instantiate the new view update procedure \( vupd \) in two versions, straightforward and incremental. All crucial subroutines of this implementation, which are employed for view generations and view updates, are developed in Java 8 and parallelized to benefit from modern hardware. The experiments were run under Ubuntu 14.04 on a machine with two “Intel Xeon E5-2690” CPUs, providing a total number of 16 physical and 32 logical cores (due to hyperthreading) running at 2.9 GHz.

Within Experiment 1 an original instance with 1 000 000 database tuples is modified by inserting and deleting the same number of randomly chosen database tuples, varying from 10 000 to 970 000. Comparing the Figs. 5(a) and (b), it becomes clear that in terms of runtime an incremental view update is nearly always better than a recomputation of a weakened view with \( vgen\_stage2 \). Even if about the full database instance is to be replaced, there is usually little reason not to employ the incremental procedure.

Experiment 2 then applies a sequence of instance modifications to an original instance with initially 1 000 000 tuples. Each of these modifications inserts 500 000 random tuples and deletes only 250 000 random tuples, resulting in modified original instances enlarged up to 4 250 000 tuples. A quick look at Fig. 5(c) reveals that the incremental procedure clearly outperforms recomputations.

For a specific approach to confidentiality-preserving data publishing, we addressed the challenging problem of how to update a published view according to modifications of the underlying original data or of the security configuration without revealing sensitive information. Basically, as far as needed for complying with a declarative confidentiality policy, and whenever possible, that approach weakens the knowledge embodied in a tuple of a complete relation instance into a piece of disjunctive knowledge formed from elements of the policy. In a first still instance-independent stage disjunctive templates (and, if required, refusals) are suitably determined, and in a second instance-dependent stage each tuple is inspected individually whether it has to be disjunctively weakened according to one or more of the disjunctive templates (or even be refused). The first stage guarantees that all templates are sufficiently mutually isolated regarding logic entailments – even under background knowledge in the form of data dependencies – such that afterwards in the second stage for any actual relation instance a strong kind of (possibilistic) semantic confidentiality will always be achieved (leaving open the problem of probabilistic inference-proofness).

Exploiting the basic features of this approach, namely instance-independent mutual isolation of templates (and refusals) in the first stage and individual treatment of tuples in the second stage, we showed how confidentiality-preserving updating of views is possible while complying with an extended notion of continuous inference-proofness. Essentially, this goal can be achieved by conceptually rerunning the two stages of the underlying view generation procedure, provided some precautions are enforced: modification requests have to be formed as transactions, in general possibly dealing with modifications of both the relation instance and the security configuration, and invariants to be maintained by transaction processing should refer to committed internal states of the overall system of the underlying relational database. Due to simplification avoiding asynchronous time, we always made transactions explicit, though essentially the same confidentiality guarantees can be obtained by completely hiding rejected, non-committed and non-effective modification requests (see condition C5*).

The updating procedure preserves the practical efficiency of the underlying view generation procedure, again due to the basic features summarized above, and as confirmed by runtime experiments with a prototype implementation. Moreover, the updating procedure also preserves and extends the availability properties of the underlying procedure. As discussed in [4, 14], the latter one minimally distorts data only if locally necessary under the given setting, and the introductory examples necessitate some restrictions, and motivate the concrete ones expressed by conditions C1–C4. However, global optimization is likely to be related to NP-hardness and thus would be in conflict with efficiency.

So far, we only deal with a single relation governed by single-premise tuple-generating dependencies rather than with a multi-relational database with any intrarelational and interrelational constraints. Though any attempt towards the latter goal would be highly worthwhile to enhance practicality, it will always face substantial limitations regarding efficiency or even computability.