Big Data analytics holds the promise of enabling new discoveries in medicine, more e cient business practices, and other important advances. However, much of the data involved in such analyses contains personally identi able information (PII) that needs to be removed or obscured prior to release in order to protect individuals' privacy. Anonymizing a dataset is not as easy as it seems, however, and many supposedly anonymous datasets are vulnerable to a record linkage attack. Most of these attacks are currently conducted manually and can be labor-intensive, but as semantic web technologies continue to gain popularity, the potential for automating various aspects of these attacks increases. This paper explores the components of a record linkage attack and how semantic web technologies could play a role in facilitating them.
Humanity is producing more data than ever before, and in the hands of researchers this data has led to important insights in a variety of domains, from medicine to construction to marketing. Privacy concerns are obviously an issue in this environment, and most data sets that are made public or used in research have been through some sort of anonymization process. Unfortunately, this process frequently consists entirely of removing explicit identi ers, such as name, email address, and social security number, from the data. In many cases, such an anonymization process still leaves the data vulnerable to a record linkage attack.
Consider a dataset that contains the following elds: name, social security number, job title, gender, age, zip code, and salary. A company wishes to make this dataset available to the media to show that there is no pay gap between men and women in the organization. To avoid revealing the salary of individual employees, the names and social security numbers are removed. However, the remaining elds can still be used to link individuals to their salaries given the presence of an appropriate secondary dataset. For example, if the company also keeps its employees' CVs on its website that contain their names, job titles, and addresses (and a person's gender can often be inferred from their name), then it might be possible to link the two data sources and thereby associate names with salaries. The privacy of employees who have an uncommon job title or live in a sparsely populated zip code is particularly at risk in this scenario.
Tables 2a and 2b show an example of a record linkage attack involving these
datasets. In this case, gender, job title, and zip code are quasi-identi ers that
can be used to link records across the two datasets. For example, it can be
inferred that Jonathan Wilson makes $54,750 because he is the only male Software
Developer living in the 24932 zip code, but it is not known who makes $37,500
because there are several people with the same combination of gender, job title,
and zip code: Abby Johnson, Victoria Stevens, and Stephanie Lewis. The risk
to a particular person's privacy depends on the number of people who share
that individual's quasi-identi er values. Latanya Sweeney called this number of
people k and established the concept of k-anonymity, in which the values in a
dataset are generalized such that there are at least k records for each
combination of quasi-identi er values [
Other researchers have since expanded upon the initial model of k-anonymity
[
Record linkage attacks require a dataset against which to link the anonymized data. Historically, most data was inconvenient to use since it was available only as databases or on le servers as spreadsheets, CSV les, or tables in PDF documents. Retrieving the data could also be di cult. For instance, some repositories might be accessible via websites or structured query mechanisms while others required a login and use of secure le transfer protocols. Financial drawbacks also inhibited data integration. Some data might be stored using proprietary formats that required expensive software licenses to read. These obstacles made nding and retrieving data related to an attacker's target dataset di cult.
The rise of linked data has changed this situation drastically. Linked data is
expressed as RDF and can be accessed using standard protocols. It is also proli c.
The Linked Open Data (LOD) Cloud now contains over 31 trillion triples across
295 datasets, with more than 503 million links across datasets [
Another quickly growing type of data on the Semantic Web is that annotated with schema.org markup.2 Schema.org is an initiative by major search engine companies to facilitate the description of entities and the relationships between them using a basic syntax expressed as RDFa, Microdata, or JSON-LD. As of 2014, more than 36% of websites in Google's crawl contained schema.org markup
[
While the rise of linked data and schema.org markup has made much more data available in an easily accessible manner, a record linkage attack relies on nding datasets that include relevant information about the individuals in the target dataset. Finding an appropriate dataset is often the most time-consuming aspect of a record linkage attack. However, some research currently underway can speed up this process, thereby lowering the barrier to deanonymization.
Many linked datasets have very complex or extremely simple schemas. It is
often di cult for a potential user of a dataset to quickly identify whether or not
the data is useful for their purpose, but numerous methods for summarizing a
linked dataset speed up this process. For example, the linked data summarization
approach described in [
Visualization tools are another avenue for quickly determining the general content and structure of a dataset. Many visual interfaces for data exploration on the Semantic Web involve displaying the RDF data as a graph. Unfortunately, graph-based representations frequently place entities based on graph metrics such as centrality or density, rather than according to their semantic meaning. They also have di culty scaling to large datasets without becoming unwieldy. Kow and his colleagues have attempted to move beyond this towards more semantic-based layout algorithms with their idea of an \information landscape," which places similar concepts near one another and labels clumps of
entities with terms describing the group. Users can select areas of interest that
seem likely to contain relevant entities, which automatically lters the mappings
shown in the list. This method of ltering allows users to systematically explore
an ontology at a high level of detail without losing track of the big picture [
Ontology Design Patterns (ODP) provide another means for quickly
determining linked dataset relevance to attackers. ODPs are self-contained, reusable
patterns that model concepts that commonly occur across di erent ontologies.
A well designed ODP describes the key aspects, and only the key aspects, of the
concept being modeled [
The dataset containing information about the 2012 European Semantic Web
Conference available at http://data.semanticweb.org/dumps/conferences/
contains information about, among other things, the keynote talks given at the
conference, including their start and end times, the speaker, the topic, the
setting in which the talk occurred, and the title and subject matter. A method
for detecting the presence of an ODP (such as Communications Events) in a
linked dataset was proposed by Khan and Blomqvist in [
Once a relevant dataset has been identi ed, the target dataset must be joined with it based on the quasi-identi er values. This seems straightforward, but can actually be quite di cult in practice because the schemas for the two datasets were likely developed by di erent people, for di erent purposes. Because of this, even two ontologies that represent the same domain will generally not be the same. They may use synonyms for the same concept or the same word for different concepts, they may be at di erent levels of abstraction, they may not include all of the same concepts, and they may not even be in the same language. Furthermore, the classes and properties in the ontologies may not be used consistently when describing the entities within the dataset. The goal of ontology alignment is to determine when an entity in one ontology is semantically related to an entity in another ontology, despite these challenges.
The Ontology Alignment Evaluation Initiative (OAEI) is a set of
benchmarks for evaluating the performance of alignment systems. The initiative has
held evaluations annually since 2005. Over that time, the accuracy and the
variety of problems handled by alignment systems have increased, while runtimes
have decreased.4 The top performing alignment systems include two that are
available online: AgreementMakerLight5 and LogMap.6 These systems achieve
an F-measure of .76 and .73, respectively, on an OAEI track based on aligning
ontologies related to conference organization. These results are approaching the
level of consensus that humans have when performing alignment tasks [
Coreference resolution algorithms attempt to determine when the same
instance (i.e. individual) is referred to in two in di erent ways. For instance, is John
Q Public in one dataset the same person as J.C. Publick in another? This is the
Semantic Web technology most closely related to deanonymization: determining
whether a person whose name and social security number have been replaced
with random strings, for example, is present within an external dataset such
as voter registration records is precisely what coreference resolution algorithms
attempt. Most current approaches use string similarity metrics to compare two
instances based on their property values (e.g. zip code, age, height) or their
property values together with the names of those properties. Top performing systems
on the mainbox instance matching task include the aforementioned LogMap and
RiMOM [
Traditional record linkage attacks sometimes involve speci c or general knowledge or assumptions an attacker has about a target. This can be made significantly easier using automated reasoners. For example, assume the attacker is working with a medical records dataset organized according to a schema which includes the statements below. <exSchema:hasDisease> <rdfs:domain> <exSchema:Person> <exSchema:hasDisease> <rdfs:range> <exSchema:Disease> <exSchema:LungDisease> <rdfs:subClassOf> <exSchema:Disease> <exSchema:HeartDisease> <rdfs:subClassOf> <exSchema:Disease> <exSchema:hasEthnicity> <rdfs:domain> <exSchema:Person> <exSchema:hasEthnicity> <rdfs:range> <xsd:string> <http://data.ex.org/person/12345> a <exSchema:Person> <http://data.ex.org/person/12345> <rdfs:nameFull> "Zhang Lu"
If the attacker knows that Zhang Lu has some disease and wants to determine what it is, he can add some additional statements to the knowledge base that re ect his assumptions and then use a reasoner to check whether or not it is possible to infer the disease Mr. Zhang has, based on those assumptions. For instance, the attacker may know that Mr. Zhang is of Asian ancestry. He could then add the following fact to the knowledge base: <http://data.ex.org/person/12345> <exSchema:hasEthnicity> "Asian"
The attacker could further assume that people of Asian ancestry are unlikely to get heart disease (based on statistical knowledge). The attacker would add the following fact to the knowledge base: (exSchema:Person and (exSchema:hasEthnicity Asian)) SubClassOf: not (exSchema:hasDisease some exSchema:HeartDisease)
The attacker could then use an automated reasoner to determine whether or not Mr. Zhang's disease could be inferred. While space constraints force this example to be relatively simplistic, it shows that the attacker can use existing Semantic Web languages and tools to quickly explore the rami cations of any assumptions he would like to make. 6
This position paper explored the potential for Semantic Web technologies to facilitate record linkage attacks against anonymized datasets. The emergence of linked data and schema.org markup has increased the availability of data that can be used to conduct attacks. Tools for data summarization and visualization can assist an attacker in sifting through this data to nd a relevant dataset with which to link the target dataset. Meanwhile, the emergence of automated techniques for ODP identi cation, ontology alignment, coreference resolution, and reasoners hold the potential to one day fully automate record linkage attacks.
The rami cations of Semantic Web technologies on privacy are likely to be
profound. Aggarwal showed that typical approaches to anonymize data break
down in the face of high dimensionality [
In future work on this topic, we plan to assess the volume of data containing potential quasi-identi ers that currently exists on the Semantic Web and develop a data vulnerability assessment tool based on Semantic Web technologies.