In this paper we examine a confidentiality framework for constructing safe KB views with respect to the object-level and the meta-level background knowledge that users may exploit to reconstruct secrets. In particular, we will present a first implementation of our framework equipped with several optimization techniques that are assessed experimentally in a concrete e-health scenario.
Recently, the Semantic Web has been increasingly used to encode sensible knowledge
on individuals, companies and public organizations. As reasoning techniques make it
possible to extract implicit information, any access control method that does not deal
with inference fails to ensure privacy [
The most popular security criterion is that the published view of a knowledge base
should not entail any secret sentence [
To tackle the vulnerabilities arising from these scenarios, [
As the works in [
Regarding complexity issues, in [
Sec. 2 will provide a general overview on the theoretical model; due to space
limitations we refer to [
We assume the reader to be familiar with description logics, and refer to [
Let KB be a knowledge base and S L a set of secrecies. Generally speaking, the confidentiality of S is preserved if a user cannot expect to discover any secret by querying the system. A possible attempt to protect the secrets is to use a view KB0 which is a maximal subset of KB that entails no secret, Cn(KB0) \ S = ;.
Unfortunately, in case some background knowledge is available to the user, this mechanism could not ensure confidentiality. Frequently, part of the domain knowledge is not axiomatized in KB. In such cases a user can import some external ontology or RDF repository BK to infer more than she is allowed to. Moreover, she may possess some meta knowledge about KB. For instance, a hospital’s KB is expected to have complete knowledge about its patients; a company’s KB is likely to encode complete information about its employees, etc. Such meta knowledge can be represented epistemically as a set of possible knowledge bases PKB, queries can be then used to narrow PKB until the user is able to reconstruct a secret. 2 Non-Horn metarules can be safely approximated with Horn metarules; the price to pay is a loss of cooperativeness, i.e. a reduction of the information available to the user.
Summarizing, we introduce a general confidentiality model which takes into account object-level and meta-level background knowledge.
Definition 1 ([
The view of KB released to a user is f (KB). Intuitively, f is secure if for each secret s there exists a possible knowledge base K 2 PKB such that (i) KB and K have the same observable behavior, that is, as far as the user knows, the knowledge base might be K, and (ii) K and the object-level background knowledge BK do not su ce to entail s. Definition 2. A filtering function f is secure (w.r.t. M) i for all s 2 S , there exists K 2 PKB such that 1) f (K) = f (KB) and 2) s < Cn(K [ BK).
In the rest of the paper we focus on concrete scenarios where all the components of bk-models are finite. Moreover, we tacitly assume that no secret is violated a priori, that is, for all secrets s 2 S there exists K 2 PKB such that s < Cn(K [ BK).3
Clearly, Definition 2 just formalizes our desiderata, consequently the next step is to exhibit a secure filtering function. This function is formulated as an iterative process where for each axiom that, according to the user’s meta knowledge, may possibly occur in the knowledge base a censor decides 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 sentences in X+ and none of those in X (formally, Cn(K) X+ and Cn(K) \ X = ;).
Let PAX (the set of possible axioms) be the set of all axioms occurring in at least one possible knowledge base, i.e. PAX = SK02PKB K0. Let = jPAXj and 1; : : : ; i; : : : ; be any enumeration of PAX. 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 : – 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 ; if censorM(Ki+; Ki ; i+1) = f alse and K j= i+1 then hKi++1; Ki+1i = hKi+ [ f i+1g; Ki i; otherwise let hKi++1; Ki+1i = hKi+; Ki [ f i+1gi .
Finally, let K+ = Si Ki+, K = Si Ki , and fM(K) = K+ : The iterative construction aims at finding maximal sets K+ and K that (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 are included neither in K+ nor in K ).
In order to define the censor we need an auxiliary definition that captures all the consequences of the background knowledge BK and the meta knowledge PKB refined by a constraint hX+; X i. Let CnM(X+; X ) be the set of all axioms 2 L such that for all K0 2 PKB such that K0 satisfies hX+; X i; 2 Cn(K0 [ BK) : (1) 3 Conversely, no filtering function can conceal a secret that is already known by the user.
Now the censor is defined as follows. For all X+; X L and
2 L,
> censorM(X+; X ; ) = <>>> or s 2 CnM(X+; X [ f g); >>: false otherwise. (2) In other words, the censor checks whether telling either that is derivable or not to a user – aware that the knowledge base satisfies hX+; X i – restricts the set of possible knowledge bases enough to conclude that a secret s is entailed by the knowledge base enriched with 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 possible answers “yes” and “no”
correspond to conditions s 2 CnM(X+ [ f g; X ) and s 2 CnM(X+; X [ f g), respectively).
This way, roughly speaking, the knowledge bases that entail s are given the same
observable behavior as those that don’t. Thm 1 in [
Of course, the actual confidentiality of a filtering f (KB) depends on a careful definition of the user’s background knowledge, that is, PKB and BK. If background knowledge is not exactly known by the knowledge engineer then it can be safely overestimated. More background knowledge means larger BK and smaller PKB, which leads to the following comparison relation k over bk-models: Definition 3. Let M = hKB; f ; S ; PKB; BKi and M0 = hKB0; f 0; S 0; PKB0; BK0i be two bk-models, we write M k M0 i KB = KB0, f = f 0, S = S 0, PKB PKB0 and BK BK0.
Then, it is easy to see that M0 is a safe approximation of M, that is if f is secure w.r.t.
M0, then it is also secure w.r.t. M (Proposition 2, [
Consequently, a generic advice for estimating BK consists in (i) including public ontologies and triple stores formalizing relevant knowledge and (ii) modeling as completely as possible the integrity constraints satisfied by the data, as well as role domain and range restrictions and disjointness constraints.
While BK can be represented with standard languages (e.g. OWL, RDF, etc.), user’s meta knowledge requires an ad-hoc language for defining PKB. Here we express PKB as the set of all theories that are contained in a given set of possible axioms PAX and satisfy a finite set MR of metarules like: 1; : : : ; n ) 1 j : : : j m (n where all i and j are in L (1 i n; 1 j m). For all metarules r, let body(r) = f 1; : : : ; ng and head(r) = f 1; : : : ; mg.
Informally, (3) means that if KB entails 1; : : : ; n then KB entails also some of 1; : : : ; m. Sets of similar metarules can be succintly specified using metavariables; they can be placed wherever individual constants may occur, that is, as arguments of assertions, and in nominals. A metarule with such variables abbreviates the set of its ground instantiations: Given a K L, let groundK (MR) be the ground instantiation of MR where metavariables are uniformly replaced by the individual constants occurring in K in all possible ways.
A set of axioms K L satisfies a ground metarule r if either body(r) * Cn(K) or head(r) \ Cn(K) , ;. In this case we write K j=m r. Moreover, if K satisfies all the metarules in groundK (MR) then we write K j=m MR. Therefore the formal definition of PKB now becomes:
PKB = fK j K
PAX ^ K j=m MRg : (4) In this paper, we assume that MR consists of Horn metarules (jhead(r)j 1) and PAX = KB [ Sr2groundKB(MR) head(r). Under such hypothesis, it can be shown that if all the axioms in KB, PKB, BK, and S belong to a tractable DL, and the number of distinct variables in MR is bounded by a constant, then fM can be calculated in polynomial time. 3
In this section we introduce SOVGen, the prototypical implementation of the confidentiality model illustrated in Section 2 based on Horn metarules. By standard logic programming techniques, a minimal K PAX satisfying the set of metarules and the constraints K+ can be obtained with the following polynomial construction: K0 = K+ ;
Ki+1 = Ki [ [f head(r) j r 2 groundKi (MR) ^ body(r)
Cn(Ki) g
It can be proved that the sequence limit KjPAXj satisfies hK+; K i as well if KjPAXj does
not entail an axiom in K . Then, for all s 2 S , s activates the censor i s is a
consequence of KjPAXj [ BK. For further details refer to [
Algorithm 1 represents the abstract algorithm underlying SOVGen. The sets MM and MG constitute a partition of MR based on the metarules’ type (ground or containing metavariables). Iterating over the axioms 2 PAX (lines 6-25), at each step K collects all the axioms of PAX that does not contribute to the entailment of secrets. The repeat-until loop (lines 9-17) computes the deductive closure K0 of K under the set of metarules MR. In particular, for each ground metarule (lines 10-13) we evaluate a conjunctive query (encoded in line 11) in order to check if m body is satisfied by the current K0 . Similarly, for each metarule containing metavariables (lines 14-16), we obtain all possible bindings for the metavariables in the body of m by means of a conjunctive query evaluation (line 15). The sequence of steps described above is iterated until a fixpoint is reached (line 17). At this point the condition Cn(K0 ) \ K j= ; is verified (line 18). It is now possible to determine the value of the censor for . We first check that no secret is entailed from the minimal K (line 19) enreached with BK. Finally, we can safely include in the view only if it is entailed by KB (line 21). Otherwise, the set K forall m 2 MM do forall (a0; : : : ; an) j K0 j= body(m; [X0=a0; : : : ; Xn=an]) do
K0 K0 [ fhead(m; [X0=a0; : : : ; Xn=an])g; is updated (line 25). Note that, 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 (lines 13, 23).
A careful analysis of the algorithm immediately points out: (1) the opportunity to apply a process of modularization designed to reduce the size of very large background knowledge bases (such as SNOMED-CT). In fact, many of the axioms in a large BK are reasonably expected to be irrelevant to the given view; (2) the need of techniques for e ective conjunctive query evaluation.4
With respect to point (1), we investigate the use of module extractors [
With respect to point (2), the presence of technologies that permit native
conjunctive query evaluation reveals fundamental to achieve e cient framework
implementation. Nowadays SPARQL5, constitute a de facto standard when it comes to conjunctive
query answering. It has been recently extended with the OWL Direct Semantics
Entailment Regime in order to permit reasoning over OWL ontologies. Unfortunately, only
few tools provide support to this new semantics. Among those our choice fell on Apache
Jena Semantic Web Toolkit6 (for more information and motivations see [
Metarule Evaluation Engine (MEE). The evaluation algorithm is based on direct calls to an incremental reasoner. In the following we provide a brief description of the procedure employed for the evaluation of the di erent types of metarules.
The evaluation of a ground metarule r requires checking that all the axioms 1; : : : ; n in body(r) are entailed by K0 . The algorithm takes advantage of short circuit evaluation techniques that permit to end the evaluation as soon as K0 6j= i and memoization of the atoms i satisfied in previous iterations in order to avoid their re-evaluation.
The evaluation of metarules with metavariables, on the other hand, comprises a preprocession step that partition the atoms 1; : : : ; n in the metarule body in sets of connected components. Within a component, atoms (that in this case can be viewed as axiom templates) share common metavariables, while there are no metavariables shared between atoms belonging to di erent connected components. Evaluating together templates belonging to non-related components increases unnecessarily the amount of intermediate results, whereas it is su cient to combine the results for the single components. Furthermore, for some types of templates, such as C(X), it is possible to retrieve the solutions directly from the reasoner, instead of verifying the satisfiability of each compatible mapping for the metavariable X. Although this can trigger some internal controls, most of the methods of reasoners are highly optimized. Other more complex 5 http://www.w3.org/TR/sparql11-overview/ 6 http://jena.apache.org/ 7 https://code.google.com/p/owl-bgp/ 8 The cost calculation is based on information about instances of concepts and roles extrapolated from an abstract model built by reasoners that implement Tableaux reasoning algorithms. 9 Note that evaluation of ground metarules results in SPARQL ASK query (line11 of Alg.1), while evaluation of metarules with metavariables in SPARQL SELECT query (line15 of Alg.1). templates, like the property assertions R(X; Y), do not allow the evaluation via dedicated reasoning tasks and require satisfiability check for each possible instantiation. Consequently, within each connected component, the evaluation is performed considering first all atoms of the type C(X) for the purpose of restricting as much as possible the compatible mappings for the metavariables, then the atoms R(X; Y) (X or Y may possibly be an individual constant) are considered.
Note that, unlike the previous engines, MEE does not need to initialize the inference model on each step of the repeat-until loop. In fact, the queries are evaluated through a number of calls to the ELK reasoner, that make it possible to exploit the characteristics of incremental classification. 4
In this section we present synthetic test cases which have been specifically designed to simulate the employment of SOVGen in a e-health scenario. In particular, each test case represents the encoding of sensitive data in a CDA-compliant electronic health record.10
According to the theoretical framework each test case comprises four di erent components: the ontology KB that contains confidential data to be protected; an ontology MR encoding the user meta knowledge with a set of metarules; a set S of secrets; a series of ontologies representing the user’s object-level background knowledge BK. KB generation. KB is generated as a set of assertions instantiating the PS ontology. PS encodes a patient summary clinical document following the HL7 Implementation Guide for CDA Rel.2 Level 3: Patient Summary. As it can be seen in Figure 1, PS currently provide a support for encoding information about (i) history of assumed medications; (ii) clinical problem list including diagnosis, diagnostic hypothesis and clinical findings; (iii) history of a family member disease; (iv) list of the procedures the patient has undergone; (v) list of relevant diagnostic tests and laboratory data. Note that, according to the CDA standards a disease in the PS ontology is represented by a ICD-9CM code, while pharmaceutical products and procedures are represented by a SNOMED CT codes. For example, <code code=”64572001” codeSystemName=”SNOMED CT”/> stands for an instance of the SNOMED CT concept Disease (SCT 64572001). The type of sections to be generated are randomly chosen among those mentioned above. A disease (resp. product, procedure, test) code to associate to the entries is chosen as a random leaf of the corresponding Disease (resp. Pharmaceutical/biologic product, Procedure by site, Measurement procedure, Imaging) concept of the SNOMED CT ontology. In case a disease code is needed, the ICD-9CM code corresponding to the SNOMED CT one is retrieved and the equivalence is added to a background knowledge ontology named EQIV-RL.
Metarule generation. The knowledge encoded in KB gives rise to several possible types of metarules. Bridge metarules associate a ICD-9CM/SNOMED CT code to the concept in the respective ontology. For instance,
CD(C); dtpCode(C; 64572001); dtpCodeSystem(C; SNOMED-CT) ) SCT 64572001(C) 10 Clinical Document Architecture (CDA) is a standard for information exchange, based on the
Health Level 7 Reference Information Model. makes it possible to derive that a code instance C is in fact an instance of the Disease concept in SNOMED CT.
The second type of metarules concerns the pharmaceutical products. The presence of a drug in the history of medication use implies that the patient su ers (certainly or with a great probability) from a specific pathology or has undertaken a specific procedure. Consider the following example of metarule which says that the presence of a medicine with active ingredient Phenytoin (SCT 40556005) indicates that the patient su ers from some kind of Epilepsy (SCT 84757006):
Patient(P); SubstanceAdministration(S A); Consumable(C); hasConsumable(S A; C); ManufacturedProduct(MP); hasManufacturedProduct(C; MP); Material(M); hasManufacturedMaterial(MP; M); SCT 40556005(CD); hasCode(M; CD) ) 9su er:SCT 84757006(P) The third type of metarules concerns the problems section. In particular the presence of a diagnosis (resp. diagnostic hypothesis) indicates that the patient su er (resp. possibly su er) a certain pathology.
Other types of metarules apply to the family history – e.g. a patient could be subject to a family members’ disease – and the procedures section. For instance, the metarule
allows to entail that the presence of an organ transplantation (SCT 77465005) in the procedure section indicates that the patient is subject to transplantation.
Note that the generation of MR is not completely random for a part of the metarules. In order to obtain a nontrivial reasoning, during the KB generation, together with the creation of a section’ entry is also created one or more corresponding bridge metarules and a metarule corresponding to the section in question. A second part of metarules are constructed by randomly selecting appropriate SNOMED CT concepts as needed. The adoption of such approach guarantees that al least part of metarules are actually fired during the secure ontology view generation. Furthermore, observe that the there are actually two levels of metarules, the bridge metarules constitute a precondition for the activation of the others.
Secrets generation. The ontology S is randomly generated as a set of assertions of the types: 9su er:X(p)
where X (resp. Y) is chosen as a random subconcept of the Disease (resp. Procedure) concept of the SNOMED CT ontology.
Background knowledge. The background knowledge BK is approximated by means of the PS, SNOMED-CT and the previously mentioned EQIV-RL ontologies. 5
In this section we present a performance analysis of SOVGen. Scalability evaluations have been carried out on synthetic test cases as described in Section 4. The size of KB is given by the parameter KB-size as the number of assertions occurring in the ontology. Then, the size of MR, MR-rate, is the ratio between the number of metarules and the number of assertions in KB. Finally, the size of S is determined by the parameter S-rate that specifies the ratio jS j=jK Bj.
The experiments were performed on an Intel Core i7 2,5GHz laptop with 16GB and OS X 10.10.1, using Java 1.7 configured with 8GB RAM and 4GB stack space. Each reported value is the average execution time of five runs over five di erent ontologies. Note that given the amount of background knowledge (consider that SNOMED-CT describes about 300K concepts) the use of module extraction techniques improves the computation time of two–three orders of magnitude at a cost of about 30 sec of overhead.
In Figure 2, the left (resp. right) column shows the experimental results obtained by using MEE (resp. OWL-BGP) to evaluate metarules – no result for Jena is reported as the execution time on all the test cases exceeded 1 hour time-out. Figures 2(a) and 2(b) report the execution time as the amount of secrets grows. Both MR-rate and KB-size are fixed, respectively to 10% and 200 assertions. Note that, MEE outperforms OWL-BGP of 1–2 orders of magnitude. Figures 2(c) and 2(d) show the impact of MR-rate when KB-size is fixed to 200 and S-size to 10%. Here, MEE runs about 10 times faster than OWL-BGP. Finally, Figures 2(e) and 2(f) illustrate the way the execution time changes as the the size of KB increases. Again MEE is 102 faster than OWL-BGP. 6
In [
(b) KB-size=200, MR-rate=10% (c) KB-size=200, S-rate=10% (d) KB-size=200, S-rate=10% (e) MR-rate=10%, S-rate=25% (f) MR-rate=10%, S-rate=25% Fig. 2. Secure view construction time with MEE e OWL-BGP on variation of the parameters S-rate, MR-rate and KB-rate e-health application. In order to maximize performance, we have compared di erent reasoning tools and designed several optimization techniques. Then, we assessed SOVGen experimentally by using realistic electronic health records that refer to SNOMEDCT concepts, and Horn rules to represent meta knowledge. In particular, we observed that module extraction techniques and a suitable, ad-hoc metarule evaluation engine – which intensively exploit ELK incremental reasoning – largely outperform general conjunctive query evaluation engines.
Considering that secure views are constructed o -line – so that no overhead is placed on user queries – performance analysis shows that SOVGen is close to meet practical use in this application scenario. In future work, we aim at improving the system with new optimizations, and extending it to general rules.