This paper investigates how to restrict the spread of sensitive information. This work is situated in a military context, and provides a tractable method to decide what semantic information to share, with whom, and how. The latter decision is supported by obfuscation, where a related concept or fact may be shared instead of the original. We consider uncertain information, and utilize Subjective Logic as an underlying formalism to further obfuscate concepts, and reason about obfuscated concepts.
Controlling the spread of sensitive information is a problem in various contexts. In
everyday life, users share information across a plethora of social networks and other
media. This raises concerns about unwanted usage of such information [
Following [
Information-obfuscation (or data-masking) is the practice of concealing,
restricting, fabricating, encrypting, or otherwise obscuring sensitive data. [
We consider an implicit exchange of information between two agents: a sender and
a receiver . The sender wants the receiver to know some pieces of information, and
at the same time it wants to keep some inferences4 that could be surmised from this
? Corresponding author.
4 In this paper, inference refers to any reasoning process that — when applying a specific rule
or rules (e.g. deductive modus ponens) — leads to a conclusion given a set of premises.
information private. This is analogous to the work described in [
In this paper we present the Semantic Obfuscation Framework (SOF ), which adopts
the sender ’s point of view, and thus starts considering (1) its domain model (ontology),
(2) the information to be shared, and (3) the information to be kept private. Then it
identifies the relevant ontological relationships between the shared and the private
information, and computes, using Subjective Logic5 (SL) [
The paper is organized as follows. Section 2 shows a realistic military scenario and the the main concepts of SL. Section 3 presents the requirements necessary for applying our proposal for obfuscating semantic data, which is then illustrated in Section 4. Finally, Section 5 concludes the paper by discussing related and future work. Proofs are omitted or sketched due to space constraints. 2
A realistic military scenario [
In [
Last night, two American diplomats were kidnapped, and their current whereabouts are unknown. The main VEO suspected of the kidnapping is Sumer, which operates from a safe haven in the hills just outside of Kish. The CJTF Commander “standsup” a Crisis Action Team (CAT) to help manage the fluid situation. Intelligence has contacted other intelligence organizations within the coalition to try and determine the exact whereabouts of the hostages and the size of the force holding them. CJTF Intelligence is also preparing intelligence products for the CAT on the kidnapping and any 5 Subjective Logic extends probability theory by expressing uncertainty about the probability values themselves. 6 http://goo.gl/feTio9 coalition forces in the area as well as the available capabilities of coalition local partners. This information will be used by members of the CAT in formulating possible Courses of Actions (COA) for the commander to consider.
A few hours ago, Intelligence determined a POI who is very likely to be involved in the kidnapping. The CJTF Commander needs to contact the coalition local partners because he will need support for constant surveillance of such a POI, but only if it is unlikely that they will infer that this is a hostage rescue operation: the coalition local partners might otherwise jeopardize the operation due to insufficient training.
Therefore, the CJTF Commander asks Intelligence to evaluate the likelihood of inferences that could be made by coalition local partners. In particular, he informs Intelligence that he needs to keep the nature of the operation (i.e. hostage rescue) confidential. Intelligence, following the approach presented in this paper, replies that the probability that the coalition partners will infer the nature of the operation is 12%, a value that the CJTF considers acceptable. Thus the CJTF asks the coalition local partners to support its operation with constant surveillance of a POI. 2.2
To assess the uncertainty in reasoning about another agent’s knowledge and, ultimately,
to derive a metric of obfuscation (x 4), we rely on Subjective Logic (SL) [
Definition 1 (Belief Mass Assignment). Given a frame of discernment , we can associate a belief mass assignment (BMA) m (x) with each substate x 2 2 such that 1. m (x) 0 2. m (;) = 0 3. Px22 m (x) = 1
When we speak of belief in a certain state, we refer not only to the belief mass in the state, but also to the belief masses of the state’s substates. Similarly, when we speak about disbelief, that is, the total belief that a state is not true, we need to take substates into account. Finally, SL also introduces the concept of uncertainty, that is, the amount of belief that might be in a superstate or a partially overlapping state. These concepts can be formalized as follows.
ity Expectation). Given a frame of discernment , a belief mass assignment m on , and a state x, we define: – the belief function for x: b(x) = X m (y); x; y 2 2 ;
y x – the disbelief function for x: d(x) =
X y\x=; – the uncertainty function for x: u(x) = – the relative atomicity for x w.r.t. y 2 2 : a(x=y) = jxj\yjyj ; x; y 2 2 ; y 6= ;; – the probability expectation for x: E[x] = X m (y)a(x=y); x; y 2 2 .
In particular, let us consider a focused frame of discernment, viz. a binary frame of discernment containing a state and its complement.
Atomicity). Given x 2 2 , the frame of discernment denoted by ~x, which contains two atomic states, x and :x, where :x is the complement of x in , is the focused frame of discernment with focus on x. Let ~x be the focused frame of discernment with focus on x of . Given a belief mass assignment m and the belief, disbelief and uncertainty functions for x (b(x), d(x) and u(x) respectively), the focused belief mass assignment, m ~x on ~x is defined as m ~x (x) = b(x) m ~x (:x) = d(x) m ~x ( ~x) = u(x) The focused relative atomicity of x (which approximates the role of a prior probability distribution within probability theory, weighting the likelihood of some outcomes over others) is defined as a ~x (x= ) = [E[x] b(x)]=u(x) For convenience, and when clear from the context, the focused relative atomicity of x is abbreviated to a(x).
An opinion consists of the belief, disbelief, uncertainty and relative atomicity as computed over a focused frame of discernment.
Definition 4 (Opinion). Given a focused frame of discernment containing x and its complement :x, and assuming a belief mass assignment m with belief, disbelief, uncertainty and relative atomicity functions on x in of b(x), d(x), u(x), and a(x), we define an opinion over x, written ox as ox
hb(x); d(x); u(x); a(x)i We denote the set of all possible SL opinion 4-ples with O [0; 1]4.
The probability expectation of an opinion is denoted as E[ox] = b(x) + u(x) a(x).
Given two opinions about propositions x1 and x2, [
Definition 5 (Propositional Conjunction). Let ox1 = hb(x1); d(x1); u(x1); a(x1)i and ox2 = hb(x2); d(x2); u(x2); a(x2)i be opinions about x1 and x2. Let ox1^x2 = hb(x1 ^ x2); d(x1 ^ x2); u(x1 ^ x2); a(x1 ^ x2)i be the opinion such that: b(x1 ^ x2) = b(x1) b(x2) d(x1 ^ x2) = d(x1) + d(x2) d(x1) d(x2) u(x1 ^ x2) = b(x1) u(x2) + u(x1) b(x2) + u(x1) u(x2)
b(x1) u(x2) a(x2) + u(x1) a(x1) b(x2) + u(x1) a(x1) u(x2) a(x2) a(x1 ^ x2) =
b(x1) u(x2) + u(x1) b(x2) + u(x1) u(x2) 3
We now turn our attention to the requirements for providing a formal definition for an obfuscation procedure. From a general perspective, we consider two agents: the sender shares White knowledge — i.e. a piece of information somehow linked to a domain ontology — with a receiver . The sender wants to keep private some pieces of information — Black knowledge — that might be surmised from the White knowledge by exploiting semantic connections. These connections are derived from the sender ’s domain ontology which we assume has been built by an ontology engineer.
From a formal perspective, if not explicitly mentioned, we refer to an arbitrary but
fixed ontology O built in the monotonic description logic language E L [
Returning to our running example (x 2.1), let us consider the relevant part of the deductive closure of the ISTAR ontology (OI ) shown in Figure 1; r1 denotes the role requiresOperationalCapability.
Moreover, our ontology engineer releases a certificate assessing the degree of confidence for the ontology: for instance, if the engineer is requested to describe each type of operation that the US Army can perform, and he considered those for peace-keeping only, the degree of confidence of this ontology will be quite low. Formally, the ontology engineer’s degree of confidence about the ontology is a SL opinion.
ontology O, ocO = hb(c)O ; d(c)O ; u(c)O ; a(c)O i is the confidence degree in O.
Both the White knowledge and the Black knowledge are represented as subsets of the concepts in the ontology.
knowledge) associated to the interaction between sender and receiver is B NCO (resp. W NCO , W \ B = ;).
In Figure 1, the White knowledge is v1 and v2 (W = fv1; v2g), while the Black knowledge is v7 (B = fv7g).
We introduce a machinery for evaluating the White–Black knowledge connections. For this purpose, we begin by describing a generic semantic relationship between two concepts representing a semantic connection, i.e. being part of a role, or of a taxonomic relation.
symmetric function on the domain of concepts.
NCO
NCO is a
As before, if not explicitly mentioned, we always refer to an arbitrary but fixed semantic relationship ! NCO NCO .
Let us introduce !R, a more specific semantic relationship on the concepts names, which is parametric in the domain of the roles.
Definition 9 (Relationship !R). Given R NRO , !R NCO NCO is a symmetric
R R relationship such that: v1 ! v2 and v2 ! v1 iff (v1 v v2) 2 O or (v1 u (9r:v2)) 2 O ; r 2 R Proposition 1. For every R 2 2NRO , the relationship !R is a semantic relationship. the case of v6, but sender is very biased; sender has no clue about v7 f!r1g v2. The other SL labelling do not affect our running example and are left in their symbolic form.
A semantic relationship induces an indirect graph (semantic relationship graph). We
then label each edge in such a graph with a SL opinion, which represents the likelihood
that the receiver is aware of the semantic relationship represented by such an edge.
These SL opinions can be derived from past interactions with the receiver [
is a SL labelling of !: !!(v1 ! v2) = !!(v2 ! v1).
In our running example, the semantic relationship graph induced by the semantic relation fr1g on OI is depicted in Figure 2. The meaning of the area comprised in the ! dotted lines will be explained following Alg. 1.
We can now define a semantic path as a path in the semantic relationship graph.
a sequence of nodes p! (vA; vB) = hv1; : : : ; vni s.t. v1 = vA, vn = vB, and 8i < n, vi ! vi+1 holds.
In order to assess the likelihood of surmising a concept, we rely on the intuition that the closer — in terms of semantic relationship — two concepts, the greater the likelihood to predict one from the other. Therefore, we need a measure of the semantic distance w.r.t. a semantic relationship between two sets of concepts. To this end, we first need to define the set of minimal semantic paths between two set of concepts, which is necessary to assess the distance among them.
between Z1 and Z2 is NCO , the set of minimal paths P! (Z1; Z2) = fp! (v1; v2) j v1 2 Z1; v2 2 Z2; p! (v1; v2) 2 arg min (jp! (v1; v2) j)g p!(v1;v2) such that 8v1 2 Z1; v2 2 Z2, 9!p! (v1; v2) 2 P! (Z1; Z2) .
Then, the semantic distance w.r.t. a semantic relationship between two sets of concepts is the maximum among the lengths of minimal paths between them.
the semantic relationship ! between Z1 and Z2 is
NCO , the semantic distance w.r.t. d! (Z1; Z2) =
max p!(v1;v2)2P!(Z1;Z2) (jp! (v1; v2) j) Note that Z1
NCO , d! (Z1; Z1) = 0.
Finally, in order to take into account the receiver ’s believed knowledge, a cumulative SL labelling between two concepts is defined as the conjunction of the SL labelling of the minimal paths between them.
Z1; Z2 NCO , the cumulative SL labelling between Z1 and Z2 is !, Z1!Z2 = ^ ^
!!(vi ! vi+1) p!(vA;vB)2P!(Z1;Z2) i<jp!(vA;vB)j
Although multiple minimal paths can exist between v1 2 Z1 and v2 2 Z2, we require (Def. 12) that only one of them is included in P! (Z1; Z2). We do not enforce a specific method for choosing the one: the most reasonable is to include the minimal path which maximize a metric, like the cumulative SL labelling (Def. 14). 4
We are now able to provide a formalization for semantic obfuscation. We call our approach the Semantic Obfuscation Framework (SOF ). This measures the quality of obfuscation in terms of the “likelihood” that the receiver will surmise the Black knowledge from the White knowledge. First, we formalize the concept of “surmise” based on a semantic relationship.
Definition 15 (Semantic Surmise). The surmise from a node v1 is SO! (v1) = fv1g [ fv2 j v1 ! v2g.
With a little abuse of notation, we define surmise on a set of concepts.
NCO : SO! (Z1) = Z1 [
\ v12Z1
SO! (v1)
Moreover, given the confidence degree, we define a function for estimating the dimension (in terms of number of concept) of the “perfect” domain ontology.
function iff (o;n) n and (o;n) = n iff o = h1; 0; 0; i; and (o;n + m) = (o;n) + (o;m).
In particular, let us introduce a cautious estimative function.
n O R 7! R is defined as: C (o; n) = . If E[o] = 0, C (o; n) = K 1.
E[o] Proposition 2. The cautious estimative function C is an estimative function.
We can provide now a computational procedure (Alg. 1) for deriving the degree of likelihood that a receiver will surmise the Black knowledge from the White knowledge. Alg. 1 requires as input an ontology O, the White and Black knowledge (resp. W and B), a semantic relationship !, an estimative function , and the confidence degree ocO .
Algorithm 1 performs several computations. First of all, it determines S (l. 1 of Alg. 1), namely the minimum set of surmised concept names from the White Knowledge which includes the Black Knowledge also.
It then considers the focused frame of discernment composed by two disjoint
primitive states, viz. B and S n B. In particular, it uses the cumulative labelling between W
and both B and S n B (l. 2 of Alg. 1) for computing the mass assignment of the two
primitive states (l. 3 of Alg. 1). To this end, Alg. 1 exploits the well-known relationship
between SL opinions on a focused frame of discernment and the beta distribution [
In order to prove the soundness of such approach, in the case of perfect knowledge, the SL opinion must collapse to a traditional probability value. The following propositions shows that this is the case.
Proposition 3. If ocO = h1; 0; 0; 1i and 8v1; v2 2 NCO ; !!(v1 ! v2) = h1; 0; 0; 1i, oB is equivalent to considering B as the set of outcomes of an experiment on the sample space S, and thus computing the probability of B.
Proof. From Def. 17, (ocO ; n) = n; from !!(v1 ! v2) = h1; 0; 0; 1i, W!B = h1; 0; 0; 1i and W!SnB = h1; 0; 0; 1i. Therefore, r = jBj, s = jS n Bj, V = 0. tu
In our running example, SI = fv4; v5; v6; v7g — the area comprised by dotted line in Figure 2 — is the minimum set of surmised concepts needed to reach the Black knowledge from the white knowledge. In the case of perfect knowledge, the probability to surmise the Black knowledge is 0:25 (cf. Proposition 3).
Let us consider instead the case where there is complete (unbiased) uncertainty about the completeness of OI , i.e. ocOI = h0; 0; 1; 0:5i. Therefore, C (ocOI ; n) = 2 n. Let us also suppose that the SL labelling are as depicted in Figure 2.
Algorithm 1 Procedure for deriving the degree of likelihood about surmising Black knowledge DegreeBlackSurmising(O; W; B; !; ; ocO ) 0
V = u( W!SnB) u( W!B) jSj 4: return hb(B); d(B); u(B); a(B)i d(B) =
s
V + (ocO ; r + s) a(B) = minfa( W!B); a( W!(SnB))g >8 jS n Bj b( W!SnB) s = < u( W!SnB) >: jS n Bj u( W!SnB) 6= 0 otherwise Therefore, W!B = !fr1g(v7 f!r1g v2) and W!(SI nB) = h0:61; 0:36; 0:03; 0:25i.
! The result of the computation is oB = h0; 00; 0:49; 0:51; 0:25i: E[oB] = 0:12.
Intelligence thus informs the CJTF Commander that the coalition local partners will surmise that the operation will be a hostage rescue given the request for support for constant surveillance of the POI with a 12% probability. Since the CJTF considers 12% a reasonable risk, he requests for constant surveillance of the member of the VEO Sumer. This leads the coalition forces to the location of the two American diplomats and to the solution of the situation. 5
In this paper we introduce SOF , a Semantic Obfuscation Framework, which includes
a sound and effective procedure for evaluating the likelihood that the receiver of some
pieces of information will derive some additional information that the sender desires to
keep private. Related works can be found in two different areas. First, which is the main
line of investigation that motivates this work, regards multi-agents strategic interactions
and the assessment of risk-benefit trade-off of information sharing [
The second trend in the literature regards ontology mapping under uncertainty.
Among others, the relevant work utilizes either supervised machine learning [
Although this paper is focused on sharing set of concepts, a natural evolution would
involve sharing set of axioms. In this area several approaches have been proposed for
modifying an ontology to conceal sensitive information both in E L [
Finally, it is worth mentioning that the impact of this line of research can spread beyond the military context, which we considered in this paper: for instance it could form the basis for an investigation on how to improve users’ awareness of the confidentiality of the information shared across social media.
On the other hand, considering the point of view of the receiver, such approach can
identify gaps in the received information, a relevant topic within intelligence analysis.
In intelligence analysis often the key information is lacking, and analysts must factor the
impact of missing data in their confidence when judging a situation. Failing to recognize
absence of evidence is one of the most important causes of cognitive bias [
The authors thank the anonymous reviewers for their helpful comments.
The research described in this article was sponsored by US Army Research laboratory and the UK Ministry of Defence and was accomplished under Agreement Number W911NF-06-3-0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the US Army Research Laboratory, the U.S. Government, the UK Ministry of Defense, or the UK Government. The US and UK Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon.