The entity resolution problem in traditional databases, also known as deduplication, seeks to map multiple virtual objects to its corresponding set of real-world entities. Though the problem is challenging, it can be tackled in a variety of ways by means of leveraging several simplifying assumptions, such as the fact that the multiple virtual objects appear as the result of name or attribute ambiguity, clerical errors in data entry or formatting, missing or changing values, or abbreviations. However, in cyber security domains the entity resolution problem takes on a whole di erent form, since malicious actors that operate in certain environments like hacker forums and markets are highly motivated to remain semi-anonymous|this is because, though they wish to keep their true identities secret from law enforcement, they also have a reputation with their customers. The above simplifying assumptions cannot be made in this setting, and we therefore coin the term \adversarial deduplication". In this paper, we propose the use of probabilistic existential rules (also known as Datalog+/{) to model knowledge engineering solutions to this problem; we show that tuple-generating dependencies can be used to generate probabilistic deduplication hypotheses, and equality-generating dependencies can later be applied to leverage existing data towards grounding such hypotheses. The main advantage with respect to existing deduplication tools is that our model operates under the open-world assumption, and thus is capable of modeling hypotheses over unknown objects, which can later become known if new data becomes available.
Deduplication of objects in databases, also known as entity resolution, is a
classical problem in data cleaning [
All of the above-mentioned methods operate under the assumption that the
undesired situation that multiple records refer to the same real-world object is
caused by a mix of clerical errors in data entry (simple typos), ambiguity in
names or other attributes (consider, for instance, the result of transliterations
such as \Kurt Godel" being mapped to \Kurt Goedel"), inconsistent
abbreviations and formatting, missing values (for instance, phone number not provided),
or changing values (for example, one record has an old phone number while
others have an updated one). Though these assumptions adequately re ect many
real-world scenarios, we are interested in others in which they cannot be
assumed to hold. One example of such a scenario is in cyber-security domains
such as malicious hacker forums on the dark/deep web (the part that is not
directly accessible by traditional browsers and search engines)|the entity
resolution problem in this setting becomes quite di erent. In [
These forums and marketplaces have an interesting characteristic: though malicious actors of course wish to remain anonymous from law enforcement agents that might be patrolling, they also enjoy a reputation with their customers and readers, and so they also wish to remain identi able. In particular, the same actor typically operates under di erent screen names, keeping certain aspects constant so that others can recognize them. Furthermore, and perhaps most importantly, they also leave involuntary traces behind that can be leveraged in deduplication e orts. We refer to this as the adversarial deduplication/entity resolution problem. The following is a simpli ed example of the kind of information that we can obtain from dark web forums and marketplaces. Example 1. As a running example, consider the simpli ed domain of the malicious hacker forums. Consider the following relational schema regarding information about users and their posts in forums:
which represent users of these forums, posts by users, topics in posts, which users have posted on which topics, and the writing style similarity between users, respectively. Furthermore, id u and id po are the keys for relations User and Post, respectively. Let D1 be an instance of this schema, where t1 is \private sqli tool", t2 is \Sql Injection", and t3 is \trojan servers as a backdoor":
D1 = f d1 : Post(p1; a1; t1); d2 : Post(p2; a2; t2); d3 : Post(p3; a3; t3); d4 : User(a1; `Blackstar'); d5 : User(a2; `Archer'); d6 : User(a3; `Angel Eyes'); d7 : WritStSim(a1; a2) g
Finally, another basic assumption generally made by traditional approaches to entity resolution|which can be seen as a consequence of the other assumptions| is that the information contained in the databases is complete. In our setting, on the other hand, it may be the case that the relevant information is yet to be discovered; in these settings, the open-world assumption becomes crucial, allowing us to entertain deduplication hypotheses over unnamed entities. In the next section, we present a formalism that allows for this kind of reasoning, as well as deal with probabilistic uncertainty.
The rest of this paper is organized as follows: Section 2 presents the extension of Datalog+/{ with probabilistic annotations and strati ed negation, Section 3 presents a two-stage chase procedure that extends the classical chase with propagation of probabilistic events and EGDs. Sections 4 and 5 introduces deduplication programs and deduplication threshold queries that can be answered via the two-stage chase, respectively. We discuss conclusions and future work in Section 6. 2
In this section, we present the basics of the language of Datalog+/{ from [
We assume the existence of the following pairwise disjoint (countably in nite) sets: a set of constants, a set V of variables, and a set N of nulls. Di erent constants represent di erent values (unique name assumption), while di erent nulls may represent the same value. We assume a lexicographic order on [ N , with every symbol in N following all symbols in . We denote by X sequences of variables X1; : : : ; Xk with k > 0.
Consider relational schemas R with a possibly in nite data domain , a nite set of database predicates (relations) R 2 R, and a set of built-in predicates for evaluating \=", \:", \ ", comparisons, and arithmetic operations. Each relation R 2 R has an associated arity n, thus R has the form R(A1; : : : ; An), where each attribute Ai has associated domain Dom(Ai) . For the sake of simplicity we may assume that the Ai's are di erent, and di erent predicates do not share attributes. However, di erent attributes may share the same domain. An atomic formula (or atom) has the form P (t1; : : : ; tn), where ti 2 Dom(Ai)[V. A conjunction of atoms is often identi ed with the set of all its atoms. A database instance D for R is a (possibly in nite) set of ground atoms (or tuples) with predicates from R and arguments from .
A homomorphism is a mapping : [ V [ N ! [ V [ N such that (i) if c 2 then (c) = c, (ii) if c 2 V [ N then (c) 2 [ N , and (iii) is naturally extended to atoms, sets of atoms, and conjunctions of atoms, that is, (p(t1; : : : ; tn)) = p( (t1); : : : ; (tn)). A grounding is a homomorphism such that (c) 2 for every c 2 [ V [ N . Also, given a conjunction of atoms (X), we denote with pos( (X)) the conjunction of atoms in (X) that appear positive, and with neg( (X)) the conjunction of atoms in (X) that appear negated.
TGDs. A tuple generating dependency (TGD) is a rst-order formula: ( ) 8XY (X; Y) ! 9Z (X; Z) (1) where X; Y; Z are sequences of variables, (X; Y) is a conjunction of atoms and negated atoms over R (called the body of , denoted body( )), and (X; Z) is a conjunction of atoms over R (called the head of , denoted head( )). We use body+( ) and body ( ) to denote pos( (X; Y)) and neg( (X; Y)), respectively. For ease of presentation, we sometimes omit the universal quanti ers, and assume that all variables without quanti er are universally quanti ed.
We restrict the language so that all the variables in body ( ) appear already
in some atom in body+( ). Furthermore, we assume is strati ed [
We call h 1; : : : ; ki a strati cation of . As in the case of standard TGDs [
A TGD is satis ed in D if and only if whenever the body of is satis ed through homomorphism h, then there exists an extension h0 of h such that h0(head( )) D.
EGDs. Equality generating dependencies (EGDs) are rst order formulas of the form: 8 X (X) ! Xi = Xj , where (X) is a conjunction of atoms, X is a sequence of variables, and Xi; Xj 2 X. As with TGDs, we sometimes omit the universal quanti ers.
The body of an EGD , denoted body( ), corresponds to (X), and the head, denoted head( ), corresponds to the equality atom on the right hand side of the rule. An instance D satis es an EGD , denoted D j= , if whenever there exists a homomorphism h such that h(body( )) D, then it must be the case that h(Xi) = h(Xj ). Otherwise, we say that is violated in D.
Probabilistic Annotations
Following [
Let M be a probabilistic model that represents a joint probability distribution
over a ( nite) set of random Boolean variables X = fX1; : : : ; Xng such that there
is a 1-to-1 mapping from X to the set of all ground atoms over HM . Examples
of the type of probabilistic models that we assume in this work are Markov
Logic [
A (probabilistic) annotation , relative to M , is a ( nite) set of expressions hA = xii, where A is an atom over RM , M , and VM , xi 2 f0; 1g, and the Xi's are pairwise distinct. A probabilistic annotation is valid if and only if for any two di erent expressions A = x; B = y 2 , there does not exist a substitution such that (A) = (B). A probabilistic scenario is a valid probabilistic annotation for which j j = jXj and all hA = xii are such that A is ground. We use scn(M ) to denote the set of scenarios in M . A probabilistic annotation is equivalent to a formula that consists of the disjunction of all the scenarios that belong to the set denoted by the annotation. Therefore, with a slight abuse of notation, we sometimes combine annotations with logical operators.
Intuitively, a probabilistic annotation is used to describe an event in which the random variables in a probabilistic model M are compatible with the settings of the random variables described by , i.e., each Xi has the value xi. We will attach probabilistic annotations to formulas in our language to produce annotated formulas F : , where F is an atom, a TGD, or an EGD. Intuitively, the annotation means that F holds whenever the event associated with occurs. Note that whenever a random variable's value is left unspeci ed in a probabilistic annotation, the variable is unconstrained; in particular, a formula annotated with an empty probabilistic annotation means that the formula holds in every world. An annotated formula F : is referred to as a probabilistic atom whenever F is atom, a probabilistic TGD (pTGD) if F is a TGD, and a probabilistic EGD (pEGD) whenever F is an EGD.
De nition 2. A probabilistic Datalog+/{ knowledge base is a triple KB = (O; M; af), where O is a nite set of atoms, TGDs, and EGDs, M is probabilistic model, and af is an annotation function that maps formulas to probabilistic annotations relative to M .
For ease of presentation, we sometimes use notation \ : e" to denote \af( ) = e". Given a probabilistic Datalog+/{ KB KB = (O; M; af) and a scenario 2 scn(M ), O denotes the (non-probabilistic) Datalog+/{ knowledge base induced by . Formally, O consists of all formulas Fi (atoms, TGDs, and EGDs) such that i for some Fi : i 2 O.
Example 2. Consider the DB from Example 1, and let KB1 = (O1; M1; af1) be a Datalog+/{ KB. Then, O1 could contain the following TGD !1: (!1) User(UID; N ) ^ hasPosted(UID; t1) ! hasPosted(UID; t2) The intuition of this rule is: \Every User that has posts on topic t1, also has posts on topic t2". The annotation function af1 is de ned such that af1(!1) = e1(t1; t2) and e1(t1; t2) is an event associated with the probability that a user posted something related to t2 given that he has posted something related to t1. O1 could contain the following EGD 1
( 1) User(UID1; N ) ^ User(UID2; N ) ! UID1 = UID2: The intuition of this rule is: \Two users cannot share the same user name.". This rule is annotated with the empty event, that is af1( 1) = ;|therefore, it always holds.
Probabilistic model M1 in the above example can be learned from domain information, and it allows to infer probabilities about possible duplicate user and correlations regarding certain events, such as posts by users given speci c topics. We will discuss this in greater detail in Section 4. 3
We now extend the classical operational semantics for Datalog+/{, based on the
chase procedure, for the case of the extensions discussed above. This procedure
provides the semantics for the application of rules and constraints, extending
the well-known (oblivious) chase algorithm for testing implications of data
dependencies [
The building block for the chase procedure is the TGD chase rule; in our setting, we must also deal with the propagation of probabilistic annotations. pTGD Chase Rule. We will now de ne the probabilistic TGD chase rule for a knowledge base KB = (O = (D; ); M; af). Let 2 O be a pTGD of the form 8XY (X; Y) ! 9Z (X; Z) : e ; then, is applicable to D if and only if there exists a homomorphism h such that one the following cases occur: a) 1) h maps the atoms in pos( (X; Y)) and neg( (X; Y)) to probabilistic atoms f 1 : e1; :::; k : ekg D and f k+1 : ek+1; :::; j : ejg * D, and 2) h(e ^ Vi=1;:::;k ei) is a valid probabilistic annotation. b) 1) h maps the atoms in pos( (X; Y)) and neg( (X; Y)) to probabilistic atoms f 1 : e1; :::; k : ekg D and f k+1 : ek+1; :::; j : ejg D, and 2) h(e ^ Vi=1;:::;k ei ^ Vi=k+1;:::;j :ei) is a valid probabilistic annotations.
Let be applicable to D, and h0 be a homomorphism that extends h as follows: for each term Xi 2 X, h0(Xi) = h(Xi) and h0(Z) = zj, where Z is existentially quanti ed in head( ) and zj is a \fresh" null, i.e., zj 2 N , zj does not occur in D, and zj lexicographically follows all other nulls already introduced. The application of on D adds to D one of the following probabilistic atoms according to the case where is applicable: a) h0( (X; Z)) : h0(e ^ Vi=1;:::;k ei). b) h0( (X; Z)) : h0(e ^ Vi=1;:::;k ei ^ Vi=k+1;:::;j :ei).
As a second step, we apply the equality-generating dependencies. We do this
in a separate step over the result of the pTGD chase in order to avoid undesired
interactions between TGDs and EGDs that can lead to undecidability [
Let be applicable to D, and Xm = f 1 : e1; :::; l : elg f 1 : e1; :::; k : ekg be the set of probabilistic atoms where Xm occurs in 1 i l; then, the application of on D results in: (i) The chase fails if h(Xm) and h(Xn) are constants; this is called a hard violation. Otherwise, (ii) for all i : ei 2 Xm replace h(Xm) with h(Xn) and ei with h(e ^Vi=1;:::;k ei), if h(Xm) is a null and h(Xn) is a constant, or h(Xm) precedes h(Xn) in the lexicographic order.
The following section shows how this chase procedure can be used to answer probabilistic deduplication queries. 4
In this section we de ne a subclass of Probabilistic Datalog+/{ programs that are speci cally tailored to declaratively capture the requirements for a deduplication task in an open-world, adversarial environment.
Towards this end, we assume that there exists a set E R that we identify as entity relations, i.e., relations that represent entities of interest in the application domain. Tuples in these relations have identi ers|keys|that allows us to compare extensions of the same predicate in di erent instances and to trace changes to them. Tuple identi ers can be accommodated by simply adding to each predicate E 2 E an extra attribute (usually denoted with T ) that acts as a primary key in E. Finally, there is also a prede ned predicate called dedup hypth.
Our formalism is inspired in (relational) matching dependencies (RMDs) [
To specify the kind of rules we require, we slightly modify pTGDs so they can be used to infer potential matchings (or matching hypotheses). For this, we assume that for every attribute Aj appearing in a n-nary relation R 2 R, where the schema of R is R(A1; : : : ; An), there exists a binary similarity relation Aj that is re exive and symmetric. Thus, they are capable of expressing similarity conditions over attribute values as done in RMDs, since the \ " predicates can simply occur in the body. dhTGDs. A Duplication Hypothesis Tuple Generating Dependency (or dhTGD) is simply a pTGD of the following form: 8XY (X; Y) ! 9Zdedup hypth(X; Z) ^ OUTPUT body(ri) … not(head(ri)) dedup_hyp … Fig. 1. Overview of a possible dhTGD learning process: relational association rule mining algorithms are applied over a set of available data sources; each such rule then leads to one output dhTGD characterizing situations that violate the corresponding association rule and therefore are the basis of a duplicate entity hypothesis. where X; Y; Z are sequences of variables, X and Z are variables and X 2 X; Z 2 Z, (X; Y) is a conjunction of atoms and negated atoms over R, and is also a conjunction of atoms.
dhTGDs are a special class of pTGDs that generate deduplication hypotheses|
essentially, they allow to create hypotheses about potential matchings, which
are kept and later con rmed or discarded whenever new information is added to
(or extracted from) the data sources. Informally, dhTGDs capture situations in
which we have reasons to believe that entities may be duplicated but we do not
know which other entity could correspond to them. Figure 1 describes one
possible way in which dhTGDs could be automatically derived from data. A relational
association rule mining algorithm (such as [
Example 3. Consider the running example, and suppose we have obtained a relational association rule that states that \if a user has posts related to topic t1, then he has posts related to topic t2". This can be translated into the following dhTGD: (!2) User(UID ; N ) ^ hasPosted (UID ; t1) ^ not(hasPosted (UID ; t2)) ! 9Z dedup hypth(UID ; Z) ^ hasPosted(Z; t2): dedup_hyp atom same atoms of body(2) ( 2) ( , ) ∧ ℎ ( , 1) ∧ (ℎ ( , 2)) → ∃ _ℎ ( , ) ∧ ℎ ( , 2) dedup_hyp atom same atoms of body(2) atoms to find similar entity ( 2) _ℎ ( 1, ) ∧ ( 2, ) ∧ ℎ ( 2, 2) ∧ ( 1, 2) → = 2 The intuition of this rule is \If a user that has some post on topic t1 but he does not have any post on topic t2, then we generate the hypothesis that there exists another user corresponding to him (whose identity is currently unknown) who has posted on topic t2".
As shown in Figure 2, an equality-generating dependency can be derived from !2 by taking the atoms from body (!2) and some additional conditions that, when true, can help obtain the identity of the hitherto unknown entity that participates in the deduplication hypothesis: ( 2) dedup hypth(UID1; Z) ^ User(UID2; N ) ^ hasPosted(UID2; t2) ^
WritStSim(UID1; UID2) ! Z = UID2: The intuition of this rule is \If we have a duplicate user hypothesis between user UID1 and an unknown user Z, and user UID2 has posts on topic t2 with similar writing style to user UID1, then Z may correspond to UID2".
Putting all of this together, the following example illustrates how the chase procedure unfolds over the scenario in the running example.
Example 4. Considering the DB D1 presented in Example 1, a probabilistic Extended Datalog+/{ KB representing a deduplication program can be KB2 = (O2; M; af) where O2 = (D1; 2) and M1 is the same probabilistic model from Example 2. The set 2 contains the (classical) TGD:
( ) User(UID ; N ) ^ Post(Id po; UID; T ) ! hasPosted (UID ; T ); and also contains the dhTGD !2 and pEGD 2 from the previous example. The annotation function af is de ned as follows: { af(!2) = e1(t1; t2), where the event e1(t1; t2) is associated with the probability that a user has some post on t2 given that he has some post on t1. User(a1,‘Blackstar’)
Post(p1,a1,t1)
User(a2,‘Archer’)
Post(p2,a2,t2)
User(a3,‘Angel Eyes’)
Post(p3,a3,t3)
TGD hasPosted(a1,t1) e1(t1,t2) dhTGD 2 hasPosted(z1, t2) e1(t1,t2)
{ af( 2) = e2, where the event e2 is associated with the probability that two users with similar writing style actually correspond to the same underlying user.
In the previous example, that the application of the dhTGD !2 produces a deduplication hypothesis for user a2, but the lack of information causes the candidate for such a duplicate to remain as a null value. However, the subsequent application of pEGD 2 lets us conclude that user a2|who has a similar writing
INPUT cf. Figure 2 style to a1|is a likely option (event e1(t1; t2) ^ e2 has probability 0.76 according to Figure 4). Note that the dhTGD could be applied multiple times, so that if there are other possible candidates, fresh dedup hypth atoms can be generated as needed. 5
The problem of identifying seemingly di erent entities within a knowledge base (or set of knowledge bases) that actually correspond to the same real world entity can be addressed as a query answering problem: given a knowledge base, we want to have a principled way of answering questions regarding the occurrence of duplicate entities. The chase procedure presented above can be used to answer queries of the form:
Q(X) = dedup(eid; X; ); where eid is a speci c entity of interest, and 2 [0; 1] represents a threshold probability value. Answers to queries of this form simply consist of possible values for variable X such that the chase procedure generates atoms dedup hypth(eid,val ) with an associated event e with PrM (e) . Figure 5 illustrates the overall query answering process.
The following result states that the two-stage chase procedure described in
Section 3 can be stopped after a nite number of steps in order to answer
threshold deduplication queries whenever the underlying classical TGDs belong to a
fragment of Datalog+/{ for which conjunctive queries are decidable; this can be
guaranteed via syntactic conditions such such as guardedness [
Proposition 1. Let KB = (O = (D; ); M; af) be a probabilistic Datalog+/{ ontology with strati ed negation, and Q(X) = dedup(eid; X; ) be a threshold deduplication query. If O belongs to a fragment of Datalog+/{ for which a nite portion of chase(D; ) can be computed in order to answer conjunctive queries, then there exists a nite portion of the two-stage probabilistic chase procedure that can be used to answer threshold deduplication query Q over KB.
Essentially, this result holds since the rst stage of our chase procedure applies TGDs and dhTGDs (which are a special case of classical TGDs) in the order given by the strati cation, and the second stage is simply an application of pEGDs over a xed structure. Both stages involve carrying over probabilistic events, which are then used in conjunction with the probabilistic model to check which atoms surpass the threshold given in the query. 6
In this paper, we have introduced the adversarial deduplication problem as a variant of the classical deduplication (or entity resolution) problem in which one cannot assume that the existence of multiple records corresponding to the same real-world entity is the result of innocent or casual errors such as typos, transliterations, or inconsistently-updated values, but rather the result of actors deliberately trying to avoid identi cation. As a motivating scenario we took malicious hacker forums and marketplaces on the dark web, where this sort of practice is commonplace and having tools at hand to address it would have a great impact on e orts such as early-warning of cyber attacks, understanding the social networks of buyers and sellers, and identi cation of leading vendors of speci c types of products.
We proposed the use of probabilistic Datalog+/{ as a way to tackle the problem of nding pairs of virtual objects for which we have reasons to believe that they correspond to the same real-world entity, where a speci c kind of probabilistic TGDs (called deduplication hypothesis-generating dependencies) and EGDs can be applied in order to derive deduplication hypotheses. The main strength of this approach is that it allows to reason about unknown objects via value invention, which is essential in this setting|not having this capability renders traditional entity resolution tools ine ective. Another advantage of our approach is that dhTGDs can be automatically obtained via relational association rule mining algorithms, and corresponding EGDs can also be derived with additional domain knowledge. Finally, we developed a two-stage probabilistic chase procedure in which (dh)TGDs are rst exhaustively applied, and then pEGDs are used to associate concrete values to null values generated in the rst step. We showed that this modi ed chase procedure can be used to answer deduplication threshold queries, leveraging chase termination results from the existential rules and Datalog+/{ literature.
Ongoing and future work involves investigating other kinds of deduplication
queries, such as instance checking (\what is the probability that two given virtual
objects correspond to the same real-world entity?"), all pairs threshold (\which
pairs of virtual objects are suspected to correspond to the same real-world entity
with probability at least p?"), and more general conjunctive queries. We are
also interested in investigating the complexity of query answering algorithms
for all such queries, and under which conditions they can be guaranteed to run
in polynomial time. We plan to evaluate the performance of our approach on
both synthetic and real-world data on malicious hacker forums and marketplaces
on the dark web obtained via a collaboration with a cyber threat intelligence
company. Finally, we would also like to explore the relationship between our
formalism and other approaches to probabilistic modeling with unknown objects,
such as [