We illustrate several novel attacks to the confidentiality of knowledge bases (KB). Then we introduce a new confidentiality model, sensitive enough to detect those attacks, and a method for constructing secure KB views.We identify safe approximations of the background knowledge exploited in the attacks; they can be used to reduce the complexity of constructing secure KB views. Finally we describe a prototype implementation of the new approach that suggests its applicability in practice.
1 Introduction
We assume the reader to be familiar with description logics, and refer to [
Recall that axioms are expressions of the form C v D, R v S , C(a), and R(a, b) where C, D are concept expressions, R, S are role expressions, and a, b are individual constants. In some DL, an individual constant a may occur also in a nominal, that is, a concept expression {a} denoting the singleton containing a. The axioms involving v are called inclusions (or subsumptions), while C(a) and R(a, b) are called assertions. In the simplest case, C and R are first order predicates and assertions are actually standard first-order atomic formulae. Inclusions are syntactic variants of logical implications.
The notion of logical consequence is the classical one; for all K ✓ L , the logical consequences of K will be denoted by Cn(K) (K ✓ Cn(K) ✓ L ). 3
A simple confidentiality model
The most natural way of preserving confidentiality in a knowledge base KB is checking
that its answers to user queries do not entail any secret. Conceptually, the queries of a
user u are answered using u’s view KBu of the knowledge base, where KBu is a maximal
subset of KB that entails no secret. In order to illustrate some possible attacks to this
mechanism, let us formalize the above simple confidentiality model (SCM).2 It consists
of: the knowledge base KB (KB ✓ L ); a set of users U; a view KBu ✓ KB for each
u 2 U; a set of secrecies S u ✓ L for each u 2 U. Secrecies are axioms that may or may
not be entailed by KB; if they do, then they are called secrets and must not be disclosed
to u. Revealing that a secrecy is not entailed by KB is harmless, cf. [
A view KBu is secure i↵ Cn(KBu) \ S u = ; . A view KBu is maximal secure if it is secure and there exists no K such that KBu ⇢ K ✓ KB and Cn(K) \ S u = ; . Attacks using object-level background knowledge. Frequently, part of the domain knowledge is not axiomatized in KB, therefore checking that Cn(KBu)\ S u = ; does not su ce in practice to protect confidentiality. For example, suppose that there is one secret S u = {OncologyPatient(John)} and KBu = {SSN(John, 12345), SSN(user123, 12345), OncologyPatient(user123)}. KBu does not entail OncologyPatient(John), so according to the SCM model KBu is secure. However, it is common knowledge that a SSN uniquely identifies a person, then the user can infer that John = user123, and hence the secret.
In other examples, the additional knowledge used to infer secrets may be stored in a public ontology or RDF repository, and confidentiality violations may be automated. Attacks to complete knowledge. Suppose the attacker knows that KB has complete knowledge about a certain set of axioms. Then the attacker may be able to reconstruct some secrets from the “I don’t know” answers of a maximal secure view KBu. Example 1. Consider a company’s knowledge base that defines a concept Employee and a role works for that describes which employees belong to which of the n departments 1 Real knowledge bases are finite, but this restriction is not technically needed until Sec. 7. 2 This usage of term “model” is common in Security & Privacy. of the company, d1, . . . , dn. The KB consists of assertions like:
Employee(e) (1) works for(e, di) (2) where we assume that each employee e belongs to exactly one department di. A user u is authorized to see all assertions but the instances of (2) with i = n, because dn is a special department, devoted to controlling the other ones. So S u (the set of secrecies for u) is the set of all assertions works for(e, dn).
Note that there is one maximal secure view KBu. It consists of all instances of (1), plus all instances of (2) such that i , n. Clearly, KBu is secure according to SCM (because Cn(KBu) \ S u = ; ). However, observe that works for(e, dn) 2 Employee(e) 2 Cn(KBu) and for all i = 1, . . . , n, works for(e, di) < Cn(KBu) (that is, the members of dn are all the employees that apparently work for no department). Using this Cn(KB) i↵ property (based on the knowledge that for each employee e, KB contains exactly one assertion works for(e, di)) and the knowledge of the protection mechanism (i.e. maximal secure views), that we assume to be known by attackers by Kercho↵ ’s principle, a smart user can easily identify all the members of dn. tu
In practice, it is not hard to identify complete knowledge. A hospital’s KB is expected to have complete knowledge about which patients are in which ward; a company’s KB is likely to encode complete information about its employees, etc.
Some approaches filter query answers rather than publishing a subset of KB [
Cn(KB). The di↵ erence is that KBau is not required to be a subset of KB and—conceptually—KBau may be infinite. KBau is secure i↵ Cn(KBau) \ S u = ; .
The reader may easily verify that the SACM is vulnerable to the two kinds of attacks illustrated for the SCM. It is also vulnerable to a third kind of attacks, illustrated below. Attacks to the signature. Suppose the user knows the signature of KB well enough to that does not occur in KB. First assume that is a concept name. identify a symbol It can be proved that: Proposition 1. If KBau is a maximal secure answer view and occurring in KB, then for all secrecies C v D 2 S u, KBau |= C u is a concept name not v D i↵ KB |= C v D.
The problem is that although C u
v D does not entail the secret inclusion C v D, still a smart user knows that the former inclusion cannot be proved unless KB entails also the latter (then maximal secure answer views generally fail to protect secrets). This attack can be easily adapted to the case where is a role name. In practice, it is not necessary to be sure that
does not occur in KB. The attacker may make a sequence of educated guesses (say, by trying meaningless long strings, or any word that is clearly unrelated to the domain of the KB); after a su cient number of trials, the majority of answers should agree with the “real” answer with high probability. Rejecting queries whose signature is not contained in KB’s signature mitigates this kind of attacks but it leaks KB’s signature and it does not provide a complete solution. The attacker may still guess a which is logically unrelated to C and D and carry out a similar attack. 4
A meta-safe confidentiality model In this section we introduce a confidentiality model that makes the vulnerabilities illustrated above visible, by taking into account object- and meta-level background knowledge. A bk-model M = hKB, U, f , hS u, PKBu, BKuiu2 U i consists of a knowledge base KB ✓ L , a set of users U, plus: – a filtering function f : } (L) ⇥ U ! } (L), mapping each knowledge base K and each user u on a view f (K, u) ✓ Cn(K); – for all u 2 U: • a finite set of secrecies S u ✓ L ; • a set of axioms BKu ✓ L , encoding the users’ object-level knowledge; • a set of possible knowledge bases PKBu ✓ } (L) (users’ metaknowledge).3 The view of KB released to a user u is f (KB, u). We adopt PKB because at this stage we do not want to tie our framework to any specific metalanguage. PKB represents the knowledge bases that are compatible with the user’s metaknowledge.
Definition 1. A filtering function f is secure (w.r.t. M) i↵ for all u 2 U and all s 2 S u, there exists K 2 PKBu such that: 1. f (K, u) = f (KB, u); 2. s < Cn(K [ BKu).
Intuitively, if f is safe according to Def. 1, then no user u can conclude that any secret s is entailed by the KB she is interacting with—enhanced with the object-level background knowledge BKu—for the following reasons: By point 1, KB and K have the same observable behavior, and K is a possible knowledge base for u since K 2 PKBu; therefore, as far as u knows, the knowledge base might be K. Moreover, by point 2, K and the object-level background knowledge BKu do not su ce to entail the secret s.
In the rest of the paper we tacitly assume that no secret is violated a priori, that is, for all secrets s 2 S u there exists K 2 PKBu such that s < Cn(K [ BKu).4 Moreover, in order to improve readability, we shall omit the user u from subscripts and argument lists whenever u is irrelevant to the context.
The attacks discussed in Section 3 can be easily formalized in this setting; so, in general, the maximal secure views of SCM are not secure according to Def. 1. Example 2. Example 1 can be formalized in our model as follows: The set of secrecies S is the set of all assertions works for(e, dn); BK = ; and PKB is the set of all the knowledge bases K that consist of assertions like (1) and (2), and such that for each axiom Employee(e), K contains exactly one corresponding axiom works for(e, di) and viceversa. The filtering function f maps each K 2 PKB on the maximal subset of K that entails none of S ’s members, that is, f (K) = K \ S (by definition of PKB).
Note that f is injective over PKB, so condition 1 of Def. 1 is satisfied only if K = KB. So, if KB contains at least one secret, then the conditions of Def. 1 cannot be satisfied, that is, maximal secure SCM views are not secure in our model. Indeed, KB can be 3 In practice, bk-models are finite, and filterings computable, but no such assumption will be technically needed until Sec. 7. 4 Conversely, no filtering function can conceal a secret that is already known by the user.
Employee(e) 2 f (KB) ^ 8 i = 1, . . . , n, works for(e, di) < f (KB)}. reconstructed from the secure view by observing that KB = f (KB) [ { works for(e, dn) | tu Similarly, the formalizations of the other attacks yield injective filtering functions (the details are left to the reader). 5
A meta-secure query answering mechanism sentences in X+ and none of those in X In this section we introduce a secure filtering function. It is formulated as an iterative process based on a censor, that is a boolean function that decides for each axiom whether it should be obfuscated to protect confidentiality. The iterative construction manipulates pairs hX+, X i 2 } (L) ⇥ } (L) that represent a meta constraint on possible knowledge bases: we say that a knowledge base K satisfies hX+, X i i↵ K entails all the (formally, Cn(K) ◆ X+ and Cn(K) \ X = ; ).
Let PAX (the set of possible axioms) be the set of axioms that may occur in the knowledge base according to the user’s knowledge, i.e. PAX = SK02 PKB K0. Let ⌫ = |PAX| + 1 if PAX is finite and ⌫ = ! otherwise; let ↵ 1, ↵ 2, . . . , ↵ i, . . . be any enumeration of PAX (i < ⌫ ).5 The secure view construction for a knowledge base K in a bk-model M consists of the following, inductively defined sequence of pairs hKi+, Ki ii 0 : hKi++1, Ki+1i = hKi+ [ { ↵ i+1}, Ki i; • otherwise let hKi++1, Ki+1i = hKi+, Ki [ { ↵ i+1}i .
• if censorM(Ki+, Ki , ↵ i+1) = f alse and K |= ↵ i+1 then – hK0+, K0 i = h; , ;i , and for all 1 i < ⌫ , hKi++1, Ki+1i is defined as follows: • if censorM
(Ki+, Ki , ↵ i+1) = true then let hKi++1, Ki+1i = hKi+, Ki i ; Finally, let K+ = Si<⌫ Ki+, K
= Si<⌫ Ki , and fM(K, u) = K+ .
Note that the inductive construction aims at finding maximal sets K+ and K that are included neither in K+ nor in K , cf. the induction step). (i) partly describe what does / does not follow from K (as K satisfies hK+, K i by construction), and (ii) do not trigger the censor (the sentences ↵ i+1 that trigger the censor
In order to define the censor we need an auxiliary definition that captures all the sentences that can be entailed with the background knowledge BK and the meta-knowledge construction: Let CnM(X+, X ) be the set of all axioms ↵ 2 L such that PKB enriched by a given constraint hX+, X i analogous to those adopted in the iterative for all K0 2 PKB such that K0 satisfies hX+, X i, ↵ 2 Cn(K0 [ BK) .
Now the censor is defined as follows: For all X+, X ✓ L and ↵ 2 L , censorM(X+, X , ↵ ) = <> >>>: false otherwise.
or s 2 CnM(X+, X [ { ↵ }); 8> true if there exists s 2 S s.t. either s 2 CnM(X+ [ { ↵ }, X ) > (3) (4) In other words, the censor checks whether telling either that ↵ is derivable or that ↵ is not derivable to a user aware that the knowledge base satisfies hX+, X i, restricts the 5 We will show later how to restrict the construction to finite sequences, by approximating PAX. set of possible knowledge bases enough to conclude that a secret s is entailed by the knowledge base and the background knowledge BK.
Note that the censor obfuscates ↵ i+1 if any of its possible answers entail a secret, independently of the actual contents of K (the two possible answers “yes” and “no” correspond to conditions s 2 CnM(X+ [ { ↵ }, X ) and s 2 CnM(X+, X [ { ↵ }), respectively). In this way, roughly speaking, the knowledge bases that entail s are given the same observable behavior as those that don’t. Under a suitable continuity assumption on CnM, this enforces confidentiality: Theorem 1. If CnM(KB+, KB ) ✓
Si<⌫ CnM(KBi+, KBi ), then fM is secure w.r.t. M.
Examples of the behavior of fM are deferred until Sec.7. 6
Approximating background knowledge Of course, the actual confidentiality of a filtering f (KB, u) depends on a careful definition of the user’s background knowledge, that is, PKBu and BKu. If background knowledge is not exactly known, as it typically happens, then it can be safely approximated by overestimating it. More background knowledge means larger BKu and smaller PKBu, which leads to the following comparison relation k over bk-models: Definition 2. Given two bk-models M = hKB, U, f , hS u, PKBu, BKuiu2 U i and M0 = hKB0, U0, f 0, hS u0, PKB0u, BK0uiu2 U0 i, we write M k M0 i↵ 1. KB = KB0, U = U0, f = f 0, and S u = S u0 (for all u 2 U); 2. for all u 2 U, PKBu ◆ PKB0u and BKu ✓ BK0u.
The next proposition proves that a bk-model M can be safely approximated by any M0 such that M k M0: Proposition 2. If f is secure w.r.t. M0 and M k M0, then f is secure w.r.t. M. Consequently, a generic advice for estimating BK consists in including as many pieces of relevant knowledge as possible, for example:
(i) modelling as completely as possible the integrity constraints satisfied by the data, as well as role domain and range restrictions and disjointness constraints; (ii) including in BK all the relevant public sources of formalized relevant knowledge (such as ontologies and triple stores).
While object-level background knowledge is dealt with in the literature, the general metaknowledge encoded by PKB is novel. Therefore, the next section is focussed on some concrete approximations of PKB and their properties. 7
Approximating and reasoning about possible knowledge bases In this section, we investigate the real world situations where the knowledge base KB is finite and so are all the components of bk-models (U, S u, BKu, PKBu); then we focus on PKBu that contain only finite knowledge bases. Consequently, fM will turn out to be decidable and we will study its complexity under di↵ erent assumptions.
A language for defining PKB is a necessary prerequisite for the practical implementation of our framework and a detailed complexity analysis of f . Here we express PKB as the set of all theories that are contained in a given set of possible axioms PAX 6 M and satisfy a given, finite set MR of metarules like: let groundK (MR) be the ground (variable-free) instantiation of MR where metavariables are uniformly replaced by the individual constants occurring in K in all possible ways. n R(a, b) o. Then groundK (MR) = n (9 R.{a} ) A(a)), (9 R.{b} ) A(b)) o. Example 3. Let MR = n 9 R.{X} )
A(X) o, where X is a metavariable, and let K = If r denotes rule (5), then let body(r) = {↵ 1, . . . , ↵ n} and head(r) = { 1, . . . , m}. We say r is Horn if |head(r)| 1. A set of axioms K ✓ L body(r) * Cn(K) or head(r) \ Cn(K) , ; . In this case we write K |=m r. satisfies a ground metarule r if either Example 4. Let A, B, C be concept names and R be a role name. The axiom set K = {A v 9 R.B, A v C} satisfies A v 9 R ) A v B | A v C but not A v 9 R ) A v B. Therefore the formal definition of PKB now becomes: Moreover, if K satisfies all the metarules in groundK (MR) then we write K |=m MR.
PKB = {K | K ✓ PAX ^ K |=m MR} .
In accordance with Prop. 2, we approximate PAX in a conservative way. We will analyze two possible definitions: 1. PAX0 = KB (i.e., as a minimalistic choice we only assume that the axioms of KB are possible axioms; of course, by Prop. 2, this choice is safe also w.r.t. any larger PAX where at least the axioms of KB are regarded as possible axioms);
r2 groundKB(MR) head(r).
Remark 1. The latter definition is most natural when metarules are automatically extracted from KB with rule mining techniques, that typically construct rules using material from the given KB (then rule heads occur in KB).
Example 5. Consider again Example 1. The user’s metaknowledge about KB’s completeness can be encoded with:
Employee(X) ) works for(X, d1) | . . . | works for(X, dn) , (7) 6 Di↵ erently from Sec. 5, here PKB is defined in terms of PAX. (5) tu tu (6) with the role assertions with di , dn that belong to KB, while the sets KB where X is a metavariable. First let PAX = PAX1 . The secure view fM(KB) depends on the enumeration order of PAX. If the role assertions works for(e, di) precede the concept assertions Employee(e), then, in a first stage, the sets KB +j are progressively filled j accumulate all the role assertions that do not belong to KB. In a second stage, the sets KB +j are further extended with the concept assertions Employee(e) such that e does not work for dn. The role assertions works for(e, dn) of KB and the corresponding concept assertions
removing from KB all the axioms referring to the individuals that work for dn.
Analogously, in [
Now all the assertions Employee(e) of KB enter KB+, and all axioms works for(e, di) with i < n
1 enter either KB+ or KB , depending on whether they are members of KB or not. Finally, the assertions works for(e, di) 2 Cn(KB) with i 2 { n neither in KB+ nor in KB , because the corresponding instance of (7) with X = e has the 1, n} are inserted body in KB+ and the first n
swer to works for(e, dn 1) would entail the secret works for(e, dn) by (7). This triggers the censor for all assertions works for(e, dn 1). Summarizing, with this enumeration ordering it is possible to return the complete list of employees; the members of dn are protected by hiding also which employees belong to dn 1. happens with the first enumeration of PAX1.
Finally, let PAX = PAX0 . Note that in this case all possible knowledge bases are subsets of KB, that contains exactly one assertion works for(e, di(e)) for each employee e. To satisfy (7), every K 2 PKB containing Employee(e) must contain also works for(e, di(e)).
tu Definition 3. A bk-model M is canonical if for all users u 2 U, PAXu is either PAX0 or PAX1 and PKBu is defined by (6) for a given MRu. Moreover, M is in a description logic DL if for all u 2 U, all the axioms in KB, PKBu, BKu, and S u belong to DL.
finite and exponential in the size of KB [ esis on CnM of Theorem 1, and hence (using Theorem 1 and Prop. 2):
Theorem 2. If M is canonical, then fM is secure with respect to all M0 k M. underlying description logic is tractable, like EL and DL-lite for example.
Lemma 1. If the axioms occurring in MR and K are in a DL with tractable subsumption and instance checking, then checking K |=m MR is: 1. in P if either MR is ground or there exists a fixed bound on the number of distinct variables in MR; 2. coNP-complete otherwise.
Lemma 2. Let M range over canonical bk-models. If M, s, X+, and X are in a DL with tractable subsumption/instance checking, and the number of distinct variables in MR is bounded by a constant, then checking whether s 2 CnM(X+, X ) is: 1. in P if MR is Horn and PAX = PAX1; 2. coNP-complete if either MR is not Horn or PAX = PAX0.
Lemma 3. Let M be a canonical bk-model. If M, s, X+, and X are in a DL with tractable entailment problems, and there is no bound on the number of variables in the metarules of MR, then checking s 2 CnM(X+, X ) is: 1. in PNP if MR is Horn and PAX = PAX1; 2. in ⇧ 2p if either MR is not Horn or PAX = PAX0.
The value of censor(X+, X , ↵ ) can be computed straightforwardly by iterating the tests s 2 CnM(X+ [ { ↵ }, X ) and s 2 CnM(X+, X [ { ↵ }) for all secrets s 2 S . Since the set of secrets is part of the parameter M of the filtering function, the number of iterations is polynomial in the input and the complexity of the censor is dominated by the complexity of CnM(). The latter is determined by Lemma 2 and Lemma 3, so we immediately get: Corollary 1. Let M be a canonical bk-model and suppose that M, X+, X , and ↵ are in a DL with tractable entailment problems. If the number of distinct variables in MR is bounded by a constant, then computing censor(X+, X , ↵ ) is: – in P if MR is Horn and PAX = PAX1; – coNP-complete if either MR is not Horn or PAX = PAX0.
If there is no bound on the number of variables in the metarules of MR, then computing censor(X+, X , ↵ ) is: – in PNP if MR is Horn and PAX = PAX1; – in ⇧ 2p if either MR is not Horn or PAX = PAX0.
We are now ready to analyze the complexity of filtering functions: Theorem 3. If M is a canonical bk-models in a DL with tractable entailment problems, then computing fM(KB) is: 1. P-complete if the number of distinct variables in the rules of MR is bounded, MR is
Horn, and PAX = PAX1; 2. PNP-complete if the number of distinct variables in MR is bounded, and either MR is not Horn or PAX = PAX0; 3. in PNP if the variables in MR are unbounded, MR is Horn, and PAX = PAX1; 4. in 3p if MR is not restricted and PAX 2 { PAX0, PAX1}.
Theorem 4. Computing fM(KB) over canonical M in a DL with ExpTime entailment (e.g. ALCQO, ALCIO, ALCQI, SH OQ, SH IO, SH IQ), is still in ExpTime. Theorem 5. Computing fM(KB) over canonical M in SROIQ(D) is in coNPN2ExpTime.
Relationships with the SCM Here we show that the meta-secure framework is a natural generalization of the SCM. The main result—roughly speaking—demonstrates that the SCM model can be essentially regarded as a special case of our framework where PKB ◆ } (KB) and BK = ; . In this case fM is secure even if M is not assumed to be canonical.
Theorem 6. Let M = hKB, U, fM, hS u, PKBu, BKuiu2 U i. If PKB = } (KB), BK = ; , and KB is finite, then 1. CnM(KB+, KB ) = Si<⌫ CnM(KBi+, KBi ). 2. For all enumerations of PAX, the corresponding fM(KB, u) is logically equivalent to a maximal secure view KBu of KB according to the SCM; conversely, for all maximal secure view KBu of KB (according to the SCM) there exists an enumeration of PAX such that the resulting fM(KB, u) is logically equivalent to KBu. 3. fM is secure w.r.t. M and w.r.t. any M0 = hKB, U, fM, hS u, PKB0u, BK0uiu2 U i such that PKB0 ◆ } (KB) and BK0 = ; .
Theorem 6 applies to every canonical M such that MR = BK = ; , because MR = ; implies that PAX0 = PAX1 = KB and hence PKB = } (KB). This shows that the SCM can be regarded as a special case of our framework where the user has no background knowledge. Moreover, by this correspondence, one immediately obtains complexity bounds for the SCM from those for PAX1 and Horn, bounded-variable MR. 9
Framework Implementation In this section we introduce a prototypical implementation of the framework based on PAX1 and Horn metarules. Nowadays ontologies are managed with the help of the OWL API7 and DL reasoners which allow us to take full advantage of their rich underlying semantics. Unfortunately, the OWL reasoners publicly available do not o↵ er native support for conjunctive query answering required to process users’ metaknowledge. A partial exception of this rule is the Pellet reasoner discussed later. Straightforward evaluation of metarules in the presence of metavariables with an OWL reasoner would need to consider all possible ways of uniformly replacing metavariables by individual constants occurring in the ontology. On the other hand, the evaluation of a ground rule r with an OWL reasoner in the worst case would require checking that all the axioms ↵ 1, . . . , ↵ n 2 body(r) and 1, . . . , m 2 head(r) are entailed by KB. Summing up, with this method, as the ontology ABox grow, metarule evaluation can easily become unmanageable in terms of execution time. Consequently, the presence of technologies that permit native conjunctive query evaluation reveals fundamental to achieve e cient implementation of the framework. SPARQL8, the W3C standard that provide languages and protocols to query and manipulate RDF content (and so ontologies encoded in the XML/RDF Syntax), constitute a de facto standard when it comes to conjunctive query answering. It has recently been extended with the so-called entailment regimes, which 7 http://owlapi.sourceforge.net/ 8 http://www.w3.org/TR/sparql11-overview/ define how queries are evaluated under more expressive semantics, such as OWL semantics, than the SPARQL standard simple entailment, based essentially on pattern matching on graphs. Unfortunately, most of the available engines do not provide support for OWL reasoning. To the best of our knowledge only Apache Jena Semantic Web Toolkit and Pellet support OWL inference over the queried ontologies. Moreover, Pellet query engine seems not to have been reengineered for the last few years. It was therefore an obvious option to prefer the Jena query engine for our system. The Jena inference subsystem is designed to allow usage of a number of predefined Jena OWL reasoners, as well as external reasoners9. However, the usage of the internal reasoners is recommended for e ciency reasons. Note, that OWL, OWL Mini, OWL Micro Jena Reasoners are a set of useful but not a full-fledged rule-based implementations of the OWL/Lite subset of the OWL/Full language. Critical not supported constructs which go beyond OWL/Lite are complementOf and oneOf, while the support for unionOf is partial. We consider our choice to use a Jena OWL reasoner a good compromise between expressivity and e ciency. According to the theoretical framework the system consists of two modules. The first one actuates the parsing of the user’s metaknowledge represented by means of a set of metarules. The second module is in charge of the secure ontology view construction.
Algorithm 1 provides an abstract view on the implementation of our framework. It takes as input an ontology KB, a set of secrets S , a set of metarules MR and the user’s background knowledge BK. The output is the set of axioms that constitute a secure ontology view for the user. The set MM and MG form a partition of MR according to rule types (ground or containing metavariables).
Remark 2. By standard logic programming techniques, a minimal PK B ✓ PAX1 satisfying the set of metarules and the constraints K+ can be obtained with the following PTIME construction: PKB0 = K+ , PKBi+1 = PKBi [
[{ head(r) | r 2 groundPKBi (MR) ^ body(r) ✓ Cn(PKBi) }
The sequence’s limit PK B|PAX1| satisfy hK+, K i as well if Cn(PK B|PAX1|) \ K , ; .
Then, for all s 2 S , s 2 CnM(K+, K ) holds i↵ s 2 Cn(PK B|PAX1| [ BK). For more
details refer to [
By iterating over the axioms ↵ 2 PAX1 (line 6-25), PK B collects at each step all parts of PAX1 that can be revealed to the user. The repeat-until loop (lines 9-17) computes the deductive closure PKB0 of PK B under MR10. In particular, for every ground metarule (lines 10-13) we execute a SPARQL ASK query (hidden in line 11) to verify if its body is entailed by the current PKB0 . For every metarule containing metavariables (lines 14-16) we execute a SPARQL SELECT query (encoded in line 15) in order to obtain all possible bindings of the metavariables that satisfy the metarule’s body. The pair of steps described above is iterated until a fixpoint is reached (no elements are added to PK B0 (line 17)). At this point the condition Cn(PK B0 ) \ Ki , ; is checked (line 18). We are now ready to determine the value of the censor function for ↵ . We verify that no secret is entailed from the minimal PK B (line 19) taking in consideration 9 To be plugged into Jena a reasoner must expose Jena API. 10 The result of Proposition 2 guarantees that considering only the minimal PKB is sound.
Algorithm 1:
Data: KB, S , MR, BK. 1 Ki+, Ki ; ; 2 MM { ri|ri 2 MR and ri metarule containing metavariables}; 3 MG { ri|ri 2 MR and ri ground metarule}; 4 PAX1 { ↵ 2 KB [ Sr2 groundKB(MR) head(r)}; 5 PKB ; ; 6 forall ↵ 2 PAX1 do 7 PKB0 PKB [ { ↵ }; 8 MG0 MG; 9 repeat 10 forall m 2 MG0 do 11 if PKB0 |= body(m) then 12 PKB0 PKB0 [ { head(m)}; 13 MG0 MG0 \ {m}; forall m 2 MM do forall (a0, . . . , an) | PKB0 |= body(m, [X0/a0, . . . , Xn/an]) do
PKB0 PKB0 [ { head(m, [X0/a0, . . . , Xn/an])}; the background knowledge11. In case ↵ is entailed by KB, it is safe to include it in the view (line 21). Otherwise, the set Ki is updated (line 25). Note that we need an OWL reasoner in order to perform the entailment checks in lines 18-20. We make use of the incremental reasoner Pellet, that for each ↵ i in the enumeration of PAX1, is expected to restrict reasoning to the new inferences triggered by ↵ without repeating the inferences that involve only Ki+ 1.
A first optimization regards the evaluation of the set of ground rules MG. During the construction of PKB, due to the monotonicity of reasoning, at each iteration we can safely remove from MG all the ground rules already satisfied at the previous iterations (line 13,23). Another optimization concerns the evaluation order of PAX1. Checking Cn(PK B|PAX1|)\ K , ; (line 18) is time consuming, so we adopt an approach that main11 This corresponds to check whether s 2 CnM(K+ [ { ↵ }, K ) only. The condition s 2 CnM(K+, K [ { ↵ }) is in fact embedded in line 18. tain the set Ki as small as possible. This is achieved processing all {↵ 2 PAX1 | ↵ 2 KB} in line 6 first. Provided that the condition in line 19 is vacuously satisfied we are sure that the Ki remains empty.
Experimental analysis show that the generation of secure views for medium sized ontologies may take several minutes. We plan to investigate module extraction techniques that are expected to improve drastically the execution time by restricting the part of the knowledge base on which metarules apply. 10
Related work
Baader et al. [
Chen and Stuckenschmidt [
Similarly, in [
Cuenca Grau and Horrocks [
Our method is inspired by the literature on controlled query evaluation (CQE) based
on lies and/or refusals ([
Conclusions The confidentiality preservation methods that do not consider background knowledge are vulnerable to several attacks. We identified two vulnerabilities (attacks to complete knowledge and to the signature) and introduced a knowledge base confidentiality model that can detect these vulnerabilities, based on a fully generic formalization of objectand meta-level background knowledge. Confidentiality is enforced through a generic mechanism for constructing secure views (the filtering fM) that is provably secure w.r.t. the meta-confidentiality model under a continuity assumption, and generalizes a few previous approaches (cf. Thm. 6 and Ex. 5). In order to compute secure views in practice we introduced a safe, generic method for approximating background knowledge, together with a specific rule-based language for expressing metaknowledge. Based on this instantiation of the general framework, where fM is always secure, we analyzed the computational complexity of computing secure views. If the underlying DL is tractable, then in the simplest case fM can be computed in polynomial time. The number of variables in metarules and the adoption of a more secure approximation (PAX0) may increase complexity up to PNP = 2p and perhaps 3p. The complexity of non-Horn metarules, however, can be avoided by replacing each non-Horn r with one of its Horn strengthenings: body(r) ) ↵ such that ↵ 2 head(r). This approximation is safe (because it restricts PKB), and opens the way to a systematic use of the low-complexity bk-models based on PAX1 and Horn metarules. For the many ExpTime-complete DL, secure view computation does not increase asymptotic complexity. So far, the best upper complexity bound for computing secure views in the description logic underlying OWL DL (i.e. SROIQ(D)) is coNPN2ExpTime.
Finally, we have provided a prototype implementation of the low-complexity frameworks based on PAX1 and Horn metarules using incremental engine versions available for Pellet and ELK to avoid repeated classifications in the iterative construction of f . M Metarule bodies are evaluated with SPARQL. Secure views are constructed o↵ -line, so no overhead is placed on user queries, and this approach is expected to be applicable in practice.
Bibliography