arXiv:1907.01862v2 [cs.CY] 23 Jul 2019

Beyond content analysis: Detecting targeted ads via
distributed counting
Costas Iordanou

Nicolas Kourtellis

Juan Miguel Carrascosa

MPI, Germany
iordanou@mpi-inf.mpg.de

Telefonica Research, Spain
nicolas.kourtellis@telefonica.com

Cyprus University of Technology
mcarrascosa@gmail.es

Claudio Soriente

Ruben Cuevas

Nikolaos Laoutaris

NEC Laboratories Europe
claudio.soriente@emea.nec.com

Universidad Carlos III de Madrid(Telematics Engineering
Department & UC3M-Santander
Big Data Institute)rcuevas@inv.it.uc3m.es

IMDEA Networks Institutenikolaos.laoutaris@imdea.org

ABSTRACTIn its principle, the concept of targeted (or personalized)
advertising appears benign: offering to consumers products
and services that they truly care about, instead of irrelevant
ones that distract or annoy. It is in its implementation andactual use where controversies start arising. For example,
tracking should respect fundamental data protection rights ofpeople, such as their desire to opt-out, and should keep clear
from sensitive personal-data categories, such as health, political beliefs, religion or sexual orientation, protected by dataprotection laws like GDPR [23] in Europe and the California
Consumers Privacy Act (CCPA) [52] in US. Similarly, sensitive demographic groups, like children, should be protectedfrom data collection and targeting as mandated, for example,
by FTC’s COPPA [1] regulation in US. Unfortunately, this is
not always the case, as made evident by the continuous presence of the topic in the news and public debates [12, 49], orthe conducted investigations and placed fines [50]. A directconsequence of concern around privacy is the rise in popularity of anti-tracking and ad-blocking tools [2, 3, 22, 28, 44].
This surge of software can choke the web of its advertising
revenues. To avoid a Tragedy of the Commons triggered byeroding privacy [37], companies offering web services needto gain back the trust of their users. An important step in thisdirection would be to provide users with the ability to single
out and report ads that violate privacy norms and laws.
The networking, measurements, and distributed systems
community has been active in the development of a new
breed of transparency tools [37] for end users, data protection authorities, and the advertising sector’s own selfregulation initiatives. Initial efforts went to detecting online
price discrimination [30, 31, 42, 43] followed by tools for
detecting targeted advertising [16, 38–40, 46, 54]. Having theability to verify the deja vu feeling arising when running
into seemingly familiar offerings is important for user empowerment and goes beyond mere curiosity. For example, it

Being able to check whether an online advertisement has
been targeted is essential for resolving privacy controversies
and implementing in practice data protection regulations like
GDPR, CCPA, and COPPA. In this paper we describe the design, implementation, and deployment of an advertisement
auditing system called eyeWnder that uses crowdsourcing
to reveal in real time whether a display advertisement has
been targeted or not. Crowdsourcing simplifies the detectionof targeted advertising, but requires reporting to a central
repository the impressions seen by different users, thereby
jeopardizing their privacy. We break this deadlock with a
privacy preserving data sharing protocol that allows eyeWnder to compute global statistics required to detect targeting,while keeping the advertisements seen by individual users
and their browsing history private. We conduct a simulation
study to explore the effect of different parameters and a live
validation to demonstrate the accuracy of our approach. Unlike previous solutions, eyeWnder can even detect indirecttargeting, i.e., marketing campaigns that promote a productor service whose description bears no semantic overlap with
its targeted audience.

1

INTRODUCTION

Targeted advertising offers the possibility of delivering tailored advertisements (in the following ads) to users based on
their interests and demographic properties. It has helped theadvertising industry reach high growth rates and revenues(23.2% growth and $23.9B in Q1 ’18 in US only) [13], hascreated lots of jobs, subsidized the delivery of free services,and funded a lot of digital innovation. Of course, to deliver
targeted ads, so-called AdTech companies need to detect
users’ interests and intentions which is done by monitoring
visited pages, searched terms, social network activity, etc.
1

ACM, ,
Iordanou et. al.
can allow a user to check whether marketers have respected
his opt-out signals, expressed through Do-Not-Track [21],AdChoices [4], or any of the numerous self-regulation initiatives put forth by the advertising sector. Moreover, if auser runs into an ad related to sensitive, and hence protected,
data category, he should be able to verify whether this has
been targeted, or is appearing for other reasons. The latter
is not always trivial, as with the so called "re-targeted" adsdisplaying products and services visited by the user in the
recent past. Behavioral targeting can be more general and,for example, display to a user a pair of sneakers of brandB’ at store S’ because the user viewed a pair of sneakers ofbrand B at store S. A pair of jeans may then be displayed dueto the previously viewed sneakers. Detecting such indirecttargeting quickly becomes a guessing game, and is, therefore, of little use to the monitoring and enforcement of dataprotection laws.
Early work on detecting targeting has employed artificiallycreated “personas”, i.e., browsers scripted to visit certain
pages that allude to clear demographic types [9, 16, 38, 39],
as “bait” for measuring whether ad delivery channels target
these demographic types. In the “offline” version of the same
approach, researchers have looked at passively collected web
click-streams to detect correlations between the pages visitedby real users and the ads delivered to them [7, 40, 55]. Whilethese studies have made important contributions, in general,they have been designed to operate offline, at a low scale, orusing simulated personas. In this paper, we aim at addressing
the following question: “Can we detect ad targeting with realusers, in real time, and at large scale?”
Our contributions: In this paper, we propose a novel, scalable, and real-time ad detection approach, and implement iton real user’s devices. Instead of using “personas” and automated bots to collect ads from artificial visits to pages, werely on a custom protocol for collecting statistics about theactual ads encountered by real users while browsing online.
We show that a surprisingly simple count-based heuristic candetect targeting with high precision. This simple heuristic isbased on the observation that targeted ads tend to “follow”
specific users across multiple domains, while being seen byrelatively fewer users than non-targeted ones. The heuristic can be computed in real-time and in a scalable fashion.
Furthermore, it is agnostic to how users’ information wascollected, and to how impressions were auctioned and delivered. This “black box” approach only looks for correlations
between users and advertisements, and is, thus, robust to
detection countermeasures [8]. Evading it, would requireeliminating such correlations, which goes against the spirit
and the essence of targeted advertising.
Crowdsourcing is a powerful tool for detecting targeted
ads, but requires users to report the ads they encounterin different websites. The second technical contribution of

our work is a protocol for exchanging this information in a
privacy-preserving manner. We leverage a wealth of previous work on privacy-preserving aggregate statistic computation [18, 36, 41], to compute aggregate statistics requiredby the ad detection algorithm, while keeping the ads seenby users1 and their browsing history private. In particular,
we design a privacy-preserving protocol to compute distribution of ads seen by users. Different from previous work inthis area, we face the challenge of protecting not only the
distribution of the ads, but the ads themselves. This problem
was recently framed by [25] as the problem of estimating“unknown unknowns”. The techniques presented in [25] arebased on differential privacy and require clients to reporttheir “real” distribution as well as distributions computed
using n-grams of the labels (in our case, ad URLs). As such,their technique fits scenarios where labels are short and not
random. We take a different approach and propose a technique that is less involved and works with any label size.
We have implemented our count-based heuristic and theprivacy-preserving protocol to support it in a distributed
system that we call eyeWnder. The third contribution of ourwork is the deployment, validation, and measurement study
executed using eyeWnder.
Our findings: We have been operating eyeWnder live formore than one year with close to 1000 users in order toget feedback on matters of user experience and desired features. This user base includes 100 paid volunteers from FigureEight [26] who have agreed to lend their data to ourvalidation efforts. We have also conducted extensive simulation studies in which we could control how advertisements
are displayed. Our findings are as follows:- Our simulations show that it only takes 6 to 7 repetitions ofan ad to make it detectable by eyeWnder. Even with such low
repetition frequency, our algorithm achieves a false negative
rate of less than 30%. Tuning the algorithm can bring thefalse negative rate to below 10%, at the expense of requiringaround 5 more repetitions. More importantly, false positives,
i.e., non-targeted ads classified as targeted, are typically close
to zero, and reach up to 2% only in the most extreme corner
scenario that we have evaluated. Having very low false positives means that when eyeWnder classifies an ad as targeted,then it most probably is. This is fundamental, if the tool is to
be used for reporting suspected data protection violations.
- The above simulations are aligned with the results from ourlive validation with real users and advertising campaigns
that are not under our control. Count-based ad detection,even with as few as 100 users, yields high precision, with true
positive and true negative rates of 78% and 87%, respectively.
- Privacy-preserving crowdsourcing allows to compute theaggregate statistics required by the ad detection mechanism
1 Note that targeted ads can reveal user interests [17].

2ACM, ,
Beyond content analysis: Detecting targeted ads via distributed counting
while keeping user browsing history and received ads private.
In particular, the privacy-preserving protocol has a negligible
effect on the quality of the computed statistics.
- We have detected several examples of indirect targetingthat existing content-based techniques (i.e., semantic overlap
between the user profile and the received ad) are unable todetect, as well as signs of advertising bias towards different
demographic traits.
- We make available our plugin via the Chrome Store, forwide testing and use from end-users, privacy researchers andauditors2 .

the best of our knowledge, eyeWnder is the first proposalthat tackles indirectly targeted ads.

2.2

Requirements

Next, we enumerate the most important requirements ofa system for real-time detection of targeted ads. Such requirements have emerged from reviewing the limitation ofexisting approaches found in the literature. In Section 9 andTable 3 we provide an extensive comparison between oursolution and existing proposals.
Generality: The detection mechanism should be able to analyze any web-based display ad. It should not be limited
to a specific ecosystem (e.g., Facebook advertising) wheremore information about the user or the ad may be available,or platform (e.g., AdChoices initiative [4]). Moreover, detection should work independently of the tracking mechanisms
used for collecting user data, interests, and intentions (beit via cookies, browser fingerprinting, or user contributed
information such as searches or social network activity).
Precision: The mechanism should allow untrained users forauditing, and potentially reporting, offending ads. Therefore
it is essential to have a high detection precision in termsof True Positives (TP) and True Negatives (TN). Validation
should be carried out using publicly available data, i.e., without requiring special access to silo-ed data from AdTech
delivery channels, Telcos, marketing campaigns, or othergatekeepers of such information that, generally speaking,have no incentive to make it public.
Simplicity: The detection method should be as simple aspossible, so that it can be implemented as a distributed systemwith most of the functionality and code running on the enduser device (browser).
Real time operation: A user should be able to request auditing of a particular ad appearing in his browser, and thesystem should respond within at most few seconds.
Scalability: The detection method should be able to handle
a large number of users (in the order of tens of thousands)
without special requirements on the back-end, including
CPU load, memory, storage, and bandwidth consumption.
Resource consumption must be limited to “control plane”
rather than “data plane” tasks, to make the method scale.
Ad-fraud avoidance: Differently from previous work [16,38, 39], the method should avoid fake visits to pages, since
fake visits contribute to fake ad impressions and click-fraud.
Detection of indirect targeting: The detection methodshould be able to detect both direct and indirect targeting.
User privacy protection: The method should not jeopardize the privacy of end-users by, e.g., requiring them to sharesensitive data such as their browsing history or ads seen.

2 BACKGROUND AND REQUIREMENTS
2.1 Types of online ads
In the rest of the paper, we will refer to ads as either targeted
or non-targeted. Furthermore, we will distinguish targeted
ads between Directly- and Indirectly-targeted ads.
Targeted vs. Non-targeted ads: Targeted ads are selectedbased on data about the user visiting a website. The exact
algorithms used are trade secrets of the different AdTech
companies but it is widely accepted that such algorithms
rely upon user demographic information (gender and age),geo-location information (GPS coordinates, IP address or
Base-station id), behavioral information extracted from user
online activity (websites visited, searched terms, social network activity, etc.). The form of targeted advertising basedon behavioral attributes is referred to as Online Behavioral
Advertising (OBA) whereas ads regarding a previously visited webpage offering products or services (e.g., a website
offering hotels) is referred to as Retargeting [9].
Non-Targeted ads are shown irrespectively of the user visiting
the website. This class of ads includes static ads (shown to
all users visiting a website based on a private deal between
advertisers and publishers), as well as contextual ads (adsmatching the context/topic of the website, e.g., a sports adappearing on a sports website).
Direct vs. Indirect targeting: Direct targeting is the mostobvious form of targeting. In this case, an advertiser interested in selling products of a certain category (e.g., fishingproducts) targets users tagged as interested in such category(i.e., fishing). Most of previous work has focused on analyzing
this type of targeting [16, 38, 39].
Indirect targeting is applied when marketers may target acertain group of users with offerings that have no direct semantic overlap with the category this group has been tagged
with. For instance, it has been reported that fans of the Walking Dead TV series were targeted with pro Donald Trump
material [11]. This would be an example of indirect targeting,since the targeted user group (Walking Dead fans) has no
immediate semantic overlap with the advertised offering. To
2 http://www.eyewnder.com/views/index

3ACM, ,
Iordanou et. al.

3

ETHICAL CONSIDERATIONS

Back-end Server
Browser
Extensions

We have obtained ethical approval from our institutions
and the funding agencies to conduct this research. Moreover, we have obtained explicit consent from users, before
installing our extension through the FigureEight platform
interface [26], to collect and process the anonymous data
used in this paper.

4

..
.

2
Database

4

A COUNT-BASED ALGORITHM

Evaluation

Figure 1: Architecture overview of the eyeWnder system and the information flow between entities.
demonstrate the performance difference for a few of these
options and show why we settle for the mean.
In order to be able to set the Domainsth,u threshold, we require a minimum amount of information from users. Similar
to [51], we require that users have visited at least 4 domainsthat serve ads within the last 7 days. If this minimum requirement is not met, our algorithm refrains from making a guess
for lack of sufficient data.
Time-window selection: Our algorithm operates in timeintervals in order to update the Usersth threshold, since users
can continuously receive and report ads during their normal browsing sessions. We select a time window of one
week based on the following observations. First, users tend
to browse differently during weekdays and weekends [10].
Therefore, we consider a week as a natural time period where
both weekdays and weekend are captured, allowing us to
study users’ behavior in both types of days. Second, we consider how targeted ads behave, which aggressively follow
the user for a few days and gradually fade-out over time.
Thus, a window of seven days is sufficiently large to capture
targeting and allows to collect enough historical information
for the algorithm to operate. In fact, we directly contacted
4 large DSP platforms and confirmed that the majority of
ad-campaigns they serve last a week or more. Note that theDomainsth,u threshold is per individual user, thus, can be
updated in real-time within each user’s browser.

Algorithm description

Our algorithm is simple and is based on the above remarks.
By observation (1), if a given ad α is targeting a specific useru, that user is likely to encounter α across multiple domains.
Therefore, the algorithm counts the number of different domains (#Domainsu,α ) where user u has seen α, and labels
the ad as targeted if that number crosses a threshold that
we call Domainsth,u . Similarly, by observation (2), if α is targeting u, most likely very few other users will see α during
their browsing activity, i.e., only users that share similar interests with u. Therefore, the algorithm counts the numberof different users (#Usersα ) that have seen α and labels α
as targeted if that number is below the Usersth threshold.
Note that the algorithm annotates an ad as targeted if bothconditions holds.
Given an ad α, the number of domains where a user has
seen α, along with the corresponding Domainsth,u threshold
are dependent on user u and, thus, can be computed locally.
On the other hand, computing the number of different usersthat have seen α, as well as the Usersth threshold requires a
global view of the system.

4.2

3

5

In this section, we describe a count-based algorithm for detecting targeted ads using only frequency counts of impressions seen by users across different domains. The algorithm
is inspired by simple observations on how targeted ads behave, namely 1) targeted ads tend to “follow” targeted users
across multiple domains, and 2) targeted ads are seen byrelatively fewer users than non-targeted ads.

4.1

Crawler

1

Algorithm details

5

Threshold estimation:
A fundamental design choice of our algorithm is how tocompute the Domainsth,u and Usersth thresholds. We empirically evaluated different options based on several momentsof the distributions (the mean, the median, the standard deviation, and possible combinations thereof). We eventually
settled for the mean of the distribution since it offered thebest trade-off between accuracy and the data we requirefrom our users. For the sake of clarity, we do discuss all thealternatives we have considered but, in Section 7.2.3, we

THE EYEWNDER SYSTEM

In this section, we describe the high level components of thesystem and the information flows between them.
The high level architecture of eyeWnder is depicted in Figure 1. The system consists of four components: the browser
extension instances, a back-end server, a centralized database, and a crawler server.
Browser extension: The extension performs the following
functions: (1) Collects information about the ads rendered
to the user. (2) Reports information to the back-end server(Figure 1, arrow 1) through the privacy-preserving protocol
4ACM, ,
Beyond content analysis: Detecting targeted ads via distributed countingof Section 6. (3) Classifies ads as targeted or non-targeted,by leveraging the algorithm of Section 4.1.
The actual algorithm that classifies ads as targeted vs.
non-targeted consists of just a few lines of JavaScript code.
Identifying and collecting info about ads is more involved.
Indeed, different ad delivery channels use a multitude oftechniques for delivering display ads. Several of them go
at great lengths to make programmatic detection of theircode difficult, in an attempt to evade ad-blocking software.
Our extension runs an ad-detection algorithm to automatically detect ads within a page, and a landing page detection
algorithm to infer the pages where ads lead once clicked.
Our ad-detection algorithm is similar to the one of AdBlockPlus [2]. Our goal, however, is just to analyze an ad, and not
to block it.
In order to avoid click-fraud, the landing page detection
algorithm does not click on the ad, but rather applies a seriesof heuristics to discover the landing URL. In particular, thealgorithm examines <a> HTML tags to extract the URL fromthe href field; alternatively, the algorithm looks for onclick
events and extracts the URL if it exists3 . In case of JavaScript
code, we run a regex to detect any URL-like strings within thescript text. In all the above cases, if the detection algorithm
finds a URL that does not belong to well-known ad networks,
we consider the URL as the ad landing page. Otherwise, we
refrain from resolving the URL in order to avoid click-fraud.
A similar technique was used in [34, 46]. In case of ads withrandomized landing page URLs (e.g., malicious ads [53] orcustomized dynamic ads [5]), we use the ad content (i.e., theimage URL, etc.) to uniquely identify the same advertisement
across different impressions. To identify ad networks thatuse randomized landing page URLs we use the methodology
described in [15].
Back-end server: The server maintains the #Usersα counters and computes the corresponding Usersth threshold. Byleveraging the privacy-preserving protocol of Section 6, theserver receives blinded reports from the extensions, aggregates them, and extracts an estimate of the number of usersthat have seen an ad—thereby computing the #Usersα counters. The server also computes the Usersth threshold by applying the methodology of Section 4.2; the computed thresholdis then distributed to clients (Figure 1, arrow 5).
Database: We use MySQL to store system metadata, suchas, active users within the system, historic anonymized datareported by users, etc.(Figure 1, arrow 2). We also store aggregated data that we need for evaluation purposes.
Crawler server: This component is used only for evaluation
purposes, and is responsible for collecting ad-related data on
specific webpages. The crawler is controlled by the back-end

server and can be instructed to visit specific websites uponrequest (Figure 1, arrow 3). Specifically, the crawler server
visits audited pages to collect ads with a clear browsing profile (empty browser cache and an empty set of cookies). These
ads are then used for deciding whether eyeWnder has indeed
classified accurately an ad as targeted (in which case thecrawler should not encounter it during a visit). The crawler
can launch multiple instances of a clean profile browser withthe eyeWnder extension installed, and store the detected ads
directly into the database (Figure 1, arrow 4).

6

PRIVACY PRESERVING PROTOCOLIn this section, we detail a privacy-preserving protocol thatallows the back-end server to compute the #Usersα counterswhile clients keep the ads they have seen private.
We leverage techniques used in many proposals for privacypreserving aggregated statistics [18, 36, 41]. The basic idea
is that each user blinds his report before sending it to theserver. Blinding factors are agreed upon by all users and aresuch that if the server aggregates all reports, the blinding
cancels out and the aggregate statistic (e.g., the sum of allreports) becomes available to the server. In a nutshell, one
can think of the blinding factors as additive random sharesof 0. If users report a vector of values, they should computeseparate blindings for each position of the vector. One fundamental assumption underlying the design just described isthat all parties in the system (i.e., users and the server) canenumerate the whole set of elements to be reported. In our
scenario, this set—we denote it by A—includes all ads seen byat least one of our users. Therefore, its size may be large and,most importantly, users may not be able to enumerate it. For
example, user Alice may not know what ads have been seenby user Bob. In such settings, one could use synopsis data
structures for multi-sets that admit aggregation. For example
count-min-sketches [29] (CMS) or spectral bloom filters [19]can be used. In this work, we use CMS as they allow us tobound the probability of error, as well as the error itself.

6.1

Count-min-sketch

A CMS X is a bi-dimensional array with d = ⌈lnT /δ ⌉ rows
and w = ⌈e/ϵ⌉ columns, where T is the number of elements
to be counted. All the cells of the sketch are initialized to 0
and d pairwise-independent hash functions {h j : {0, 1}∗ →[w]}1≤j ≤d are chosen.
The encoding of an element x i is done by calling X.update(x i )that increments X [j, h j (x i )] by 1, for 1 ≤ j ≤ d.
The estimated frequency c̄ x i of element x i is retrieved bycalling X.query(x i ) that outputs minj X [j, h j (x i )] such that:(1) c x i ≤ c̄ x iÍ(2) c̄ x i ≤ c x i + ϵ j=1..T c x j with probability 1 − δ
where c x i is the true frequency of element x i .

3 In some cases the onclick event is redirected to a JavaScript function

instead of a URL redirection.
5

ACM, ,
Iordanou et. al.
In eyeWnder, each user encodes the set of ads he has seen
in a CMS data structure, and blinds each cell before sending
it to the server. The server aggregates all CMSes so that all
blindings cancel out, and obtains the aggregate CMS encoding the multi-set of ads seen across all users. If users sharean additive random share of 0 for each cell of the CMS, thisdesign allows for a privacy-preserving aggregate statistics
framework for scenarios where the set of elements to be
counted is (a) large and (b) not enumerable by each party.
This design is similar to the one shown in [41], that in turn,extends techniques presented in [36]. However, the clientsin [41] can enumerate the set of elements to be reported and,
therefore, [41] presents a less challenging scenario.
We also face an additional challenge, that, to the best of
our knowledge, has not been addressed by existing privacypreserving aggregate statistic techniques. Data structures
like spectral bloom filters or CMS allow to query for theestimate frequency of a given element x. That is, the querier(i.e., our server) must enumerate all the ads encoded in theaggregate CMS, in order to learn the distribution of ads as
seen by users. Of course, the server cannot do so and our
privacy goal forbids clients from sending the URLs of theads to the server. We overcome this problem as follows.
We map the URL of an ad ID in [1, |A|] by means of apseudo-random function (PRF). The latter is keyed to prevent the server from computing the mapping on its own.
In particular, given an ad URL x, its ad ID is computed as
y = F (k, x) where F is a PRF and k is a cryptographic key.
For each ad seen by a user, the extension computes the corresponding ad ID and encodes it in the CMS. Note that without
knowledge of k, it is not possible to relate ad URL x to its
identifier y.
Rather than hard-coding the key k in the extension, we borrow from previous research on Oblivious Pseudo-Random
Function (OPRF) [27] and introduce an additional server
to help clients mapping ad URLs to ad IDs. The oprf-server
holds the secret key k and aids clients to compute y = F (k, x)
for a given ad URL x. As the name suggests, the server is“oblivious” to the input of the PRF so that x remains private to the user.4 While such a design choice requires anadditional server, we note that previous work uses a similar approach in order to improve the overall security of an
application [24, 35]. In a real-world deployment, the oprfserver may be instantiated by already-deployed trusted-third
parties such as certification authorities, EFF, etc.
In practice, we have to (over)estimate |A| in order to minimize collisions when mapping an ad URL to an ad ID. However, by overestimating |A|, the server is likely to query the

CMS for ad IDs that correspond to none of the encoded ads(i.e., a false positive). Nevertheless, later we show that a CMS
is robust to false positives by design.
In the following, we provide details of the protocol.
Blinding factors: We borrow from Kursawe et al. [36] who
have shown how a set of users can agree on random sharesof 0. In particular, let N be the number of users and M be
the number of elements to be blinded (e.g., the number ofcells in a CMS). Also, denote by x i , y = дx i , the private andpublic key of user ui , respectively. Here, д is a generator
of a cyclic group G of order q, where Computational Diffie
Hellman is hard. Assume that the public key of each user isavailable to all other users in the system, e.g., by means of apublic bulletin board like an online forum5 . At round s, user
ui generates a blinding factor for the m-th cell as:bi [m] =NÕ
j=1, j,i

H (y xj i ||m||s) · (−1)i >j

where (−1)i >j is equal to 1 if i > j, or to −1 otherwise. Notethat each user can locally compute his blinding factors bysimply using the public keys of all other users. Note also thatÍNfor any m, we have i=1
bi [m] = 0, i.e., bi [m] is an additive
random share of 0.
OPRF: We leverage the RSA-based OPRF in [33]. Given an
RSA triple (N , d, e) where N is the product of two distinct
primes of sufficient length and d, e ∈ Z ϕ∗ (N ) are such thated ≡ 1 mod ϕ(N ), the PRF on input x is defined as G(H (x)d )where H : {0, 1}∗ → Z N is a hash function mapping arbitrary strings to elements of Z N , and G : Z N → {0, 1}l
H : {0, 1}∗ → Z N is a hash function mapping elements of
Z N to strings of arbitrary length l. The oprf-server generates the RSA triple (via a suitable key-generation algorithm)
and publishes N , e while keeps d private. Given an ad URL
x, the client issues a request as x ′ = H (x)r e . That is, theclient maps x to Z N and blinds the result by multiplying itwith a random group element r raised to the e-th power. The
server “signs” the request by computing y = (x ′)d . Finally,ythe server recovers y ′ = r and outputs y = G(y ′). Note thatyy ′ = r = (xr) = (H (xr)r ) = H (x )r r = H (x)d since ed = 1
mod ϕ(N ). The protocol guarantees that the server learns
nothing about x whereas the client learns nothing about d,and it is a PRF under the one-more RSA assumption [33].
CMS computation: User ui starts with an empty CMS X i .
For each newly received ad x, the user engages in an OPRF
protocol with the oprf-server to obtain the corresponding
ad ID y, and encodes y in the CMS by calling X i .update(y).
When asked to report its CMS, the user blinds each cellof X i with the blindings computed as shown above. Thatis, the client computes the blinded CMS X̂ i by computing

4 We note that in order to avoid a single point of failure, mapping function

can be distributed to multiple servers by defining F as the XOR of the output
of multiple OPRFs, each computed with its own secret key.

′ d

e d

d ed

5 The board may be as well hosted at the back-end server.

6

ACM, ,
Beyond content analysis: Detecting targeted ads via distributed countingX̂ i [j] = X i [j] + bi [j] for 1 ≤ j ≤ m where m is the number ofcells in the CMS. Finally, the client sends X̂ i to the server.
Aggregation and unblinding: Finally, the server aggreÍ
gates all received CMSes by computing X = i X̂ i where thesum is cell-wise and, for each ad ID i ∈ {1, . . . |A|} it obtains
the estimated frequency by querying X.query(i).
Fault-tolerance: Our aggregation technique requires thatall users report their blinded CMSes, so that the server canaggregate them and cancel out the blindings. If a user fails
to report its CMS, aggregation of the remaining ones at theserver results in a CMS with random noise in each of its
cells. In order to tolerate missing reports, the server andthe clients who have sent their reports must go through an
additional round of interaction to “adjust” their blindings andcater for the blindings of the non-reporting clients (see [41]).
The protocol takes only two rounds—one where the serverreports the list of “missing” clients and another round where
the clients send their CMSes obfuscated with the updated
blinding factors.
Security: The security of our scheme follows from the security of the protocol to compute blindings proposed in [36].
We tweak the protocol by using an OPRF to map ad URLs toa set that is enumerable by the server. By the security provisions of the OPRF protocol, given an ad ID y, it is impossible
to retrieve its original URL without knowledge of the key
held by the oprf-server.
We stress that our protocol remains secure against an
honest-but-curious server, and this is an assumption common to many other systems that address privacy issues when
computing statistics on crowdsourced data [18, 36, 41].

7

Probability Density

0.30
0.25
0.20
0.15

Act_Th: 2.25
CMS_Th: 2.30
Act_Th: 3.26
CMS_Th: 3.33
Act_Th: 2.54
CMS_Th: 2.62

0.10
0.05
0.00

2

4

# Users

6

8

10

Figure 2: The effect of the privacy preserving protocolon the computation of the #User distribution and its
threshold for three different weeks.
average, the communication overhead for the average user
amounts to roughly 3.5KB (assuming 100-characters URLs
using Unicode encoding). Nevertheless, some users with alarge number of ads to report can see their communication
overhead rise up to hundreds of KB (some users in our dataset
reported around 250 unique ads).
Next, we assess the communication and computation overhead required to compute the blinding factors. Exchanged
data between the server and a client amount to 0.38MB and1.9MB for 10k and 50k users, respectively. The computation
time at the client totals 30 seconds for 1k users and a sketchof size 5k. Our results are in line with results reported in [41].
We stress that both operations are carried out once per week
and can run in the background.
Also, the time to map the URL of an ad to its ID, using the
oprf-server, is always less than 500ms and requires exchanging two group elements (e.g., 1024 bits each). We stress thatthe mapping is done once per (unique) ad. It can be carriedout as ads are received and results can be stored locally sothat they are available when the CMS must be computed.
Finally, we empirically show the effect of the privacy preserving protocol on the computation of the #Userα distribution and its threshold. Figure 2 compares the distribution computed with cleartext reports versus the distribution
computed using the privacy-preserving protocol based on(blinded) CMSes. The figure shows the difference using datafrom three different weeks in our dataset. Furthermore, thefigure reports the threshold value computed on cleartext
data, and the threshold value computed on the outcome ofthe privacy-preserving protocol. The latter leads to a slightly
higher threshold and this is due to the collisions that may
happen when mapping ad URLs to ad identifiers.
To sum up, the overhead due to privacy-preserving protocol does not impose an unbearable toll on users. The protocol
to map ad URLs to identifiers is very lightweight and the

EVALUATIONIn this section, we first evaluate the overhead of our privacy
preserving protocol. Second, we present a controlled simulation study to assess the robustness of our algorithm andthe effect of key parameters on its performance. Third, we
present a live validation of the entire system with real ads
and the 100 real users recruited via FigureEight [26].

7.1

Week 1 Actual
Week 1 CMS
Week 2 Actual
Week 2 CMS
Week 3 Actual
Week 3 CMS

Performance and overhead of theprivacy preserving protocol

First, we assess the communication overhead due to the CMS
and compare it with the average communication overhead if
clients were to upload their contributions in cleartext. We
fix δ and ϵ to 0.001 and assume the size of a cell in the CMS
to be 4 bytes. The size in bytes of the CMS totals to 185,
196, and 207KB, for an input size6 of 10k, 50k, and 100k,
respectively. If users were to report their contribution incleartext, each user would simply report a vector of URLs.
Since our dataset suggests that users see 35 unique ads on
6 The number of ads to be counted.

7

ACM, ,
Iordanou et. al.
Table 1: Simulation configuration parameters

mapping is carried out as new ads are encountered. The
protocol to report the CMS requires a few (i.e.2 or 3) MB ofdata to be exchanged, assuming 50k users. This is done once
per week and the communication complexity scales linearlywith the number of users. Further, the error on the estimateddistribution due to the privacy-preserving protocol is small
as shown in Figure 2.

7.2

Variable name
Number of users
Number of websites
Average user visits
Average ads per website
Percentage of targeted ads

Value
500
1000
138
20
0.1

Controlled simulation study

The count-based algorithm of Section 4.1 and its automatedparameter tuning described in Section 4.2 can lead to false
negatives, i.e., targeted ads classified as non-targeted, andfalse positives, i.e., non-targeted ones classified as targeted.
In this section, we study the circumstances and the frequencyof such misclassification via controlled simulation experiments. Out of the two metrics, the most important are thefalse positives. This has to do with a major use case for eyeWnder, which is to report illegal targeting, as explained in
the introduction. Therefore, when eyeWnder classifies an ad
as targeted we want this to be precise with high probability
so that investigations are not triggered by mistake. On theother hand, failing to detect a targeted ad is relatively lessimportant since no investigation is launched in this case.

False Negative %

100

Mean
Mean+
Median

80
60
40
20
0

1

2

3

4

5 6 7 8 9 10 11 12
Frequency cap

Figure 3: False Negatives % Vs. Frequency Cap using
two different thresholds (Mean, Mean+Median) for
both variables (#Usersα , #Domainsu,a )

7.2.1 False negatives. As described earlier, our algorithm
uses the fact that the same ad “follows” a user across multiple
domains as an indication of targeting. But how intense should
this following be before our algorithm has a chance to detect
it? If a targeted ad appears only once, then certainly it isindistinguishable from any non-targeted ads. Considering
the other extreme, if it appears in all the pages visited bya user, then it obviously becomes easy to detect. Next, westudy the effect of the Frequency Cap i.e., the number ofrepetitions (or re-appearances) of a targeted ad on the abilityof our algorithm to detect and classify it correctly. Noticethat this parameter is not known to us, nor uniform acrossadvertisers and therefore we study its effect in our simulation
model by assigning to it different values. The Frequency Cap
is used by advertisers to avoid annoying targeted users withtoo many repetitions of the same ad. In our validation study
appearing later in Section 7.3 we demonstrate that our system
is indeed robust to the magnitude of values used in practice,
but remaining unknown to us.

many other users of eyeWnder, but non uniform user interests
can lead to misclassification as shown next.
7.2.3 Simulation results. We have built a custom simulator, based on [14], capable of simulating users, websites, andad campaigns. The main parameters of the simulator andpre-set values for our basic configuration, are depicted inTable 1.
Figure 3 shows that even few repetitions of a targeted ad
make it detectable by our algorithm with high probability.
Setting the Usersth and Domainsth,u thresholds according
to the Mean value of the corresponding counters (see Section 4.2) brings false negatives to below 30% with just 6-7
repetitions of an ad. Using as threshold the Mean+Medianvalue requires a higher number of repetitions for detection
but drops false negative even further to 10%. Our experiments with real users in the next section are in agreementwith these results. In those experiments we set the thresholds
using Mean to make sure we can have detection even with asmaller number of repetitions for a targeted ad.
Regarding false positives, we have run several different
simulations in which a subset of users visits a subset of sitesthat happen to be running large static campaigns. Theseusers get to see the same ad in different websites not because
they are being targeted but because the ad happens to be

7.2.2 False positives. The same ad can be encountered in
multiple websites without being targeted. Such is the case,for example, of large-scale “brand awareness” campaigns
paid by large corporations to display their offering in many
mainstream and even niche websites without targeting any
particular individual. Such ads will appear to be chasing auser across websites, when in reality they are not. Of course,
our algorithm also checks to see that the ad is not seen by8

ACM, ,
Beyond content analysis: Detecting targeted ads via distributed counting
in all the websites they visit. If the remaining users (themajority) visits different websites, then misclassification may
appear for the initial subset of users. Still, this happens withprobability below 2% in more than 30 different parameter
configurations that we have tried. This result is also validated
by our experiments with real users. False positives can befurther reduced by grouping users in more homogeneousgroups in terms of browsing patterns (e.g., geographicallyor based on age group, etc.).

7.3

from the crawled dataset (denoted by CR in the figure), theclassification from a content-based detection heuristic (CB)8 ,and the classification from FigureEight users (F8). These
comparisons yield False Positives (FP), False Negatives (FN),
True Positives (TP), True Negatives (TN), as well as UNKNOWN rates. As we will explain shortly, results derived
by comparing against the crawler are correct with high probability (namely FP(CR), TN(CR)). Results derived by comparing against the content-based heuristic or FigureEightare likely correct (namely TP(CB), FN(CB), TP(F8), TN(F8),FP(F8), FN(F8)). The justification for the above is that thecontent-based heuristic and FigureEight are themselves subjective means of classifying an ad. Users have limitations in
detecting bias or discrimination [47], whereas the contentbased heuristic is just another heuristic whose validation
faces the same challenges with the validation of eyeWnder.
Since, however, the heuristic is a reasonable one, and theusers have been selected carefully, we assume that their classifications will be more right than wrong. Ads falling under
UNKNOWN are ads for which it is impossible to assess precision by the previous means. We handle them separately in
Section 7.3.3. Next, we traverse the evaluation flow-chart of
Figure 4 from top to bottom, starting from the right branch.
Ads classified as targeted: If an ad is classified as targetedby eyeWnder, we check to see if the crawler happens to see
the same ad. If this happens, then we have a false positive
with high probability, since targeted ads should not be encountered by a crawler having empty browsing history.
If the crawler does not see the ad, then we proceed to checkif the ad shares any semantic overlap with the user, using themethodology described in [45]. If it does, then, and only then,we check to see if the content-based heuristic also classifies
it as targeted. We do this check in order to identify the set ofads in which eyeWnder and the content-based heuristic havea chance to agree. Such ads can only be Direct targeted ads
because the content-based heuristic can only detect those(see Section 2.1). In our evaluation, we check for semantic
overlap using the content-based heuristic which implies that
if the ad has semantic overlap with the user, eyeWnder andthe content based heuristic will agree by default9 yielding alikely true positive.

Live validation of eyeWnder

Our simulation results have shown that when eyeWnder classifies an ad as targeted then this is accurate with very highprobability (false positives <2%), whereas when it classifies
an ad as non-targeted the accuracy is again high (false negatives 10-20%). In this section we want to validate the above
results with a live experiment involving real users and campaigns. This is inherently difficult due to the lack of publicly
available ground truth about which ads are targeted andwhich not (see Requirements in Section 2.2). The situation
becomes even more challenging when the evaluation has tobe performed for a system used by real end-users (as opposed
to offline evaluation based on network traces), over a varietyof ad delivery channels (as opposed to a single channel, e.g.,
facebook ads [6, 48, 54]). Still in this section we perform sucha live validation and show that it leads to consistent resultswith those of our simulation study.
7.3.1 Datasets. We use three different datasets. The firstdataset is created with the help of a crowdsourcing platform
named FigureEight [26]. We collected data during three consecutive weeks from a population of 100 users with varying
level of activity. The dataset includes in total 6743 ads. We
call this dataset the “eyeWnder dataset” and we use it as input
to the count-based algorithm that classifies the collected ads.
In addition, we also ask the FigureEight users to label theads that they receive as targeted or not. For this purpose, we
instruct the users to provide labels to all the ads they receive
while surfing the web. We call this subset of labeled ads the“F8 dataset”.
The last dataset we use is collected by the crawler during
the same three weeks. It includes several visits and ad collections to any website in which eyeWnder has classified an
ad7 . We call this dataset, “CR dataset” and use it to identify
statically placed ads as done in [16, 46].

8 We have adapted the methodology of [16] to operate with real users insteadof personas. For each user, we have selected the most significant categoriesof the pages he visits to create his profile. We used categories appearing atleast T times in different websites. We have used T = 20 since in the context
of this paper we are seeking precision rather than recall. We classify an
ad as targeted if the main category of its landing page (as obtained from
AdWords) matches one of the categories in the user profile.
9 It might appear as redundant to check both for semantic overlap andagreement with the content-based heuristic, since we use the latter also forsemantic overlap. We have kept both stages for generality, since semantic
overlap could be checked with alternative methods than our content-basedheuristic.

7.3.2 Methodology. Figure 4 presents the work-flow of
our evaluation methodology. The idea is to compare theclassification derived by eyeWnder against the classification
7 Note that for evaluation we are using full information on our test users

after having been granted full consent. The privacy preserving protocol isdeveloped for the actual operation of the system beyond evaluation.
9

ACM, ,
Iordanou et. al.
iWnderClassiﬁcation

TN(CR)
27.27%

Yes

1789

Found
in CR
No

4355 | 91.28%
No

Static Ads = 6560 | 97.29%
No

Targeted

Total Ads = 6743 | 100%

Targeted Ads = 183 | 2.71%
Yes4771 | 72.73%

Found
in CR

160 | 95.8%
Yes

No

FP(CR)
8.74%

Yes

167 | 91.26%

No

Has semantic
overlap

16

Has semantic
overlap

Yes

416 | 8.71%
4219

136 | 3.13%

Labeled
by F8

No

Yes

45
No

UNKNOWN
96.87%
Sect.7.3.3

TN(F8)
33.09%

Targetedby F8

7 | 4.2%
148

Targeted
by CB

No

Yes

91

12 | 7.5%

Labeled
by F8

Yes

2
Yes

FN(F8)
66.91%No

UNKNOWN
92.5%
Sect.7.3.3

FN(CB)
8.71%

Targetedby CB

FP(F8)
16.67%

Targeted
by F8

Yes

10
Yes

TP(F8)
83.34%

TP(CB)
4.19%

Figure 4: The evaluation tree for precision performance of the eyeWnder classification of targeted ads.
If an ad does not share semantic overlap with the user,
we check to see if FigureEight users have tagged it. Noticehere that FigureEight users have classified only a subsetof the ads that they have seen. If they have not provided aclassification, then the ad is added to UNKNOWN. Otherwise,
if their classification agrees with eyeWnder, we have a likely
true positive, else a likely false positive.
Ads classified as non-targeted: If an ad that eyeWnderclassifies as non-targeted is seen by the crawler, then thisproduces a true negative. If the ad has semantic overlap
with the user, then, as explained before, the content-basedheuristic will classify it as targeted, thereby yielding a likely
false negative for eyeWnder. If the ad does not have semantic
overlap with the user, we check to see if FigureEight users
have classified it. If they have not, it goes to UNKNOWN. If
they have classified as targeted, it produces a false negativefor eyeWnder. If they have classified it as non-targeted, thenwe have a likely true negative for eyeWnder.

consider the profile of the user receiving the ad, in order tomanually determine if the ad is targeting such a profile.
– Targeted UNKNOWN: This group includes 148 ads that eyeWnder classified as targeted, but CB and FigureEight users
did not. Hence, they may be either FP or some form of targeting (e.g., indirect) that escapes CB or FigureEight users. A
preliminary manual inspection showed that several of themseemed to be retargeted ads [9]. To verify this, we manually
visited the landing page associated to each ad, and afterwards
we visited some of the domains where the ad re-appeared
according to our dataset. The experiment was set up for
testing the repeatability of the suspected retargeting. Whenthe experiment led to retargeting, it meant that our initial
guess was correct, and we considered the classification to bea likely TP.
For the remaining ads, we evaluated if they could be indirect OBA ads. To this end, we performed a correlation
analysis between the topics of the ad’s landing page and the
profiles of the users receiving that ad. If there exists statistically significant correlation between some of the ad’s andthe user’s topics, but these topics are not semantically overlapping, then we interpret it as likely indirect OBA ad, andthe classification is a likely TP. Some examples of ads that we
identified as indirect OBA are the following: (1) Male users
who exhibit interest in computers, electronics, cars, etc., but
receiving ads from a dating website (perhaps a classic indirect targeting of single male users). (2) Users with interestin computers, electronics, and programming, but receivingads from KFC, a famous fast food restaurant. (3) Users withinterest in websites related to beauty products, fitness, bodycare, etc., receiving ads related to seafood. Finally (4) users

7.3.3 Dealing with the unknown. Due to the lack of groundtruth, a high rate of classified ads (148 targeted and 4219 nontargeted) have ended up in the two UNKNOWN groups of
Figure 4, for which we cannot evaluate precision using thecrawler, the content-based heuristic or FigureEight. In thissection, we perform extra analysis to resolve non-targeted
UNKNOWNs into likely-TN or likely-FN, and the targeted
UNKNOWNs into likely-TP or likely-FP.
– Non-targeted UNKNOWN: In this case, both count-basedand content-based classification have identified these ads as
non-targeted. However, these ads were not manually tagged
by FigureEight users. Hence, we select a random set of 200of these ads and manually inspect them. In particular, we
10ACM, ,
Beyond content analysis: Detecting targeted ads via distributed counting
Table 2: Logistic regression modeling for targeted ads

who showed interest in governmental websites, internet services, insurance services, etc., receiving ads related to realestate and housing.

Variablefemalemale
G
30k-60keom 60k-90k
Inc90k-...
20-30
30-40
e
40-50
Ag
50-60
60-70
er
end

7.3.4 Results. The rates in Figure 4 along with the resultsfrom our analysis of unknown ads reveal that the overall
rate of likely TPs is 78%. From these, 10% have been identified by CB or FigureEight users. The rest are associated toretargeting or indirect OBA. Our analysis also reveals a TN
rate of 87%. In particular, 27% are highly probable TNs, sincethese ads have been marked as non-targeted by both, eyeWnder and the crawler. The remaining 60% are likely TNs. This
percentage has been derived from our manual inspection of
non-targeted UNKNOWN.
Based on these results, we claim that our method meetsthe high precision requirement defined in Section 2, whichguarantees that, for instance, users willing to report a privacy
incident related to an ad have high confidence that the ad isindeed targeted.
We acknowledge that there is still room for improvement,
since, as the evaluation shows, eyeWnder sometimes fails
to detect ads classified as targeted by CB (416) or F8 (91).
This is mainly due to two factors. First, as we further discuss in Section 10, we have evaluated eyeWnder with just a
few users, which is close to a worst-case analysis given thecrowdsourced nature of the system. Second, eyeWnder has
been configured to maximize the precision rather than recall
for reasons discussed in Section 2. We are confident that witha bigger dataset, our existing count-based detection would
perform better. We could also come up with more elaborate
heuristics to improve performance. Our objective in this paper, however, is to make the point that even with few users,
simple count-based detection yields precise classification forboth directly and indirectly targeted ads.
Evading detection of targeted ads: Finally, in this paragraph we discuss the situations where advertisers are intentionally trying to evade the detection of targeted ads.
Our system is robust to that since there is a lot of inherent
randomness in the current way ads are delivered, yet eyeWnder identifies such ads with good accuracy even with few
hundreds of users. For an adversary to defeat detection it
will have to effectively give up targeting or do it very mildly
which would, effectively, go against the very idea of targetingand his business model.

8

OR
0.255
0.174
1.446
1.521
0.525
1.031
1.428
1.964
0.745
2.654

SE
0.407
0.383
0.145
0.187
0.343
0.407
0.405
0.422
0.489
0.477

Z-val
-3.356-4.5662.538
2.249-1.878
0.075
0.880
1.599
-0.601
2.044

P>|z|8e-4∗∗∗∗
5e-6∗∗∗∗
0.0111∗∗0.0245∗∗0.0603∗0.94040.37900.10980.54750.0409∗∗95% CI
0.107-0.539
0.076-0.348
1.088-1.924
1.052-2.187
0.257-0.996
0.488-2.450
0.679-3.388
0.899-4.788
0.291-2.022
1.069-7.087

OR: Odds Ratio, SE: Standard Error, CI: Confidence Interval∗∗∗∗ p < 0.001, ∗∗∗ p < 0.01, ∗∗ p < 0.05, ∗ p < 0.1

8.1

Logistic regression analysis

The demographic data provided by our volunteers include
information such as gender (G), age (A), income level (L),employment status (E), etc. We want to investigate these
independent, nominal and ordinal factors, and how they
associate with the type of advertisement delivered to theparticipating users. In practice, the type of ad is the dependent variable (D) in our model, receiving a binary status of“static” or “targeted” advertisement. Using these input data,
we perform a binomial logistic regression on the 4 independent variables to model the 1 dependent variable, in the form:
D ∼ G + A + L + E.
In reality, we tested several configurations for the model,
including pairwise interactions between all independent factors, as well as removing incrementally each one of them totest if the model improved its predictive performance. In fact,
in the case of “employment status”, it was removed from themodel as it was deemed non-useful with an anova likelihood
ratio test, with non-significant impact in the final produced
model. Here, we only report the experimental setup thatyielded a logistic regression model with most statisticallysignificant results, in form: D ∼ G + A + L, considering 0-30k
and 1-20 the base levels for income and age, respectively.

8.2

Findings

The results of the logistic regression are shown in Table 2.
Also, in Figure 5 we plot the effects of the three variables andall their corresponding levels, with respect to the expected
probability for a user to receive targeted ads. From theseresults, we make the following observations:– Gender bias: From our analysis, we find statistically significant effect on the factor of gender. In particular, women are
more likely to be targeted by advertisers than men, and thisresult is significant at p < 0.001.
– Economic bias: Our results show that as the income level ofa user increases from 30k to 60k, and from 60k to 90k euros,

SOCIO-ECONOMIC BIASES

In this section, we leverage the social, economic and demographic information we have from the volunteers and thedatasets of Section 7.3.1, to look for potential socio-economic
biases of ad targeting.
11

ACM, ,

probability

Iordanou et. al.
0.32
0.30
0.28
0.26
0.24

0.30
0.25
0.20

●

●

0.4

●

●

0.3

●

0.15

●

0.2

●

0.22

●

●

0.10

●

●

0.20

the ads he receives. Then, using different heuristics and statistical means, targeted ads are identified as those having topics
that share some semantic overlap with the user’s browsing
history. Topic-based detection could, in principle, be applied
to real users, as we have done for evaluation purposes in
Section 7. Existing work, however, has only used it in conjunction with artificially constructed personas, i.e., robots
that browse the web imitating very specific (single-topic)
demographic groups [7, 16], or to emulate real-users offline
using click-streams [40].
The only topic-based solution meant to be used by realusers is MyAdchoice [46], which has been implemented in
the form of a browser extension. This extension is available
only under request, and based on the information reported
in the paper, it has been only used in a beta-testing phaseby few tens of friends and colleagues. Independently of thespecific pros and cons of individual solutions, topic-based
detection presents some common limitations. The most important being that it can only detect direct interest-basedtargeted advertising. It is unable to detect other forms oftargeting based on demographic or geographic parameters,
as well as indirect targeting (see Section 2.1 for definitions).
Correlation-based solutions treat the online advertising
ecosystem as a blackbox and apply machine learning and statistical methods to detect correlations between the browsing
behavior and other characteristics of a user (OS, device type,location, etc.) and the ads he sees. For instance, XRay [38]and Sunlight [39] create for each persona several shadow accounts. Each shadow account performs a subset of the actions
performed by the original persona. By analyzing the common
actions performed by shadow accounts receiving the same
reaction from the ecosystem (i.e., the same ad), the authors
can infer the cause of a targeting event. AdFisher [20] uses
similar concepts to find discrimination practices, for instance,in the ads shown to men vs. women. As with topic-based detection, this technique presents important challenges related
to scalability and practical implementation. Moreover, they
are not suitable for real-time targeting detection. With the
exception of [46], no previous work has been implemented
as a tool for end-users. Most of them, including [46], rely
on content-based analysis, thereby suffering from scalability
issues and inability to detect indirect targeting.
Parallel to efforts from the research community, the European Interactive Digital Advertising Alliance (EDAA) has
developed YourAdChoices [4]. It is a self-regulation programin which companies that deliver targeted ads voluntarily
add an icon that, if clicked by a user, offers some form of
explanation of why the user received the ad. This techniquescales and works in real time. It only works, however, withcompanies participating in the program. It also assumes full
trust on the reported explanations, something that has been

0.5
●

0.1

UserGender

1
20−20
30−30
40−40
50−50
60−60
−7
0

0−
30 30kk−
60 60k
k−
90
90 k
k−
...

al
e
m

fe
m

al
e

0.18

IncomeBracket

UserAge

Figure 5: Predicted probability for a targeted advertisement to be delivered to a user, vs. three independent
variables with statistically significant levels.
Table 3: Comparison of characteristics of main targeted ad detection solutions.
Fake Impressions
Click-fraud
Privacy-preserving
Real-users
Personas
Operates in Real-timeHigh scalability
Operates Offline
Topic-based
Correlation-based
Count-based

[20]
†

•

†

[7]
†
†

•

†
•

[40]
†

•

†
•

•

[16]
†
†

•

†
•

[38]
†

•

[39]
†
*

[46]
†

eyeWnder

✓

✓
✓

✓
✓

✓
✓

•

†

†

•

•

•
•

† Negative, ✓ Positive, • Neutral, * Unspecified - (Within the context of this work)

he or she is more likely to be targeted by advertisers, andthis is statistically significant at p < 0.05. However, when
the income level becomes too high (i.e., above 90k euros),the expected probability of targeted advertising is reduced.
We conjecture that advertisers profile users to constructeconomic capacities for each one, and adjust their targeting
campaigns accordingly to optimize click-through and salerates. Online advertisements targeting very wealthy users
may have proven to be less profitable than other income
brackets, and thus, such users are less targeted.
– Age bias: From the odds ratio scores, it appears that increasingly older users are more probable to be targeted by advertisers. However, some of the age brackets are less populated
by ads and users and thus, our results are not statisticallysignificant, but only demonstrate a consistent trend.

9

RELATED WORK

Table 3 summarizes and compares existing proposals for
detecting targeted advertisements. From a methodologicalview, these solutions can be grouped into topic-based [7, 16,
40, 46], and correlation-based detection [20, 38, 39].
Topic-based solutions perform content-based analysis to
extract the relevant topics on a user’s browsing history and12

ACM, ,
Beyond content analysis: Detecting targeted ads via distributed counting

REFERENCES

challenged by recent works [20]. eyeWnder offers the opportunity to conduct independent audits, which are useful for
end-users, data protection authorities, as well as for the credibility of ad-choices and related self-regulation initiatives.

10

Children’s
OnlinePrivacy
Protection[1] 1998.
Act(COPPA).
https://www.ftc.gov/enforcement/
rules/rulemaking-regulatory-reform-proceedings/
childrens-online-privacy-protection-rule. (1998).
[Online: accessed 30-January-2019].
[2] adblockplus.org. 2019. Adblock Plus. Surf the web without annoying
ads! https://adblockplus.org/. (2019). [Online: accessed 30-January2019].
[3] adguard.com. 2019.
Adguard AdBlocker browser extension.
https://adguard.com/en/adguard-adblock-browser-extension/
overview.html. (2019). [Online: accessed 30-January-2019].
[4] Digital Advertising Alliance. 2019.
YourAdChoices.
http://
youradchoices.com/. (2019). [Online: accessed 30-January-2019].
[5] Inc. Amazon Technologies. 2016.
Personalized Landing
Pages.
https://patentimages.storage.googleapis.com/72/fb/61/
7dd01f31aca7be/US20160180389A1.pdf. (2016). [Online: accessed
30-January-2019].
[6] A. Arrate, J. G. Cabanas, A. Cuevas, M. Calderon, and R. Cuevas. 2019.
Large-scale analysis of user exposure to online advertising on Facebook. IEEE Access (2019).
[7] P. Barford, I. Canadi, D. Krushevskaja, Q. Ma, and S. Muthukrishnan.
2014. Adscape: Harvesting and Analyzing Online Display Ads. In Proc.
of the Conference on World Wide Web, (WWW’14).
[8] M. Bashir, S. Arshad, E. Kirda, W. Robertson, and C. Wilson. 2018. How
Tracking Companies Circumvented Ad Blockers Using WebSockets.
In Proc. of the Internet measurement conference, (IMC’18).
[9] M. Bashir, S. Arshad, W. Robertson, and C. Wilson. 2016. Tracing
Information Flows Between Ad Exchanges Using Retargeted Ads. In
Proc. of the USENIX Security Symposium, (SEC’16).
[10] D. Boughareb and N. Farah. 2011. Toward a Web Search Personalization
Approach Based on Temporal Context. In Proc. of Digital Information
and Communication Technology and Its Applications.
[11] P. Bradshaw. 2016. It’s official: The Walking Dead helped elect Donald
Trump. https://www.theguardian.com/commentisfree/2016/nov/23/
walking-elect-dead-trump-immigration-zombies. (2016). [Online:
accessed 30-January-2019].
[12] C. Brooks. 2017. Invasion of Privacy: What Consumers Thinkof Personalized Online Ads. http://www.businessnewsdaily.com/
4632-online-shoppers-personal-ads.html. (2017). [Online: accessed
30-January-2019].
[13] Interactive Advertising Bureau. 2018. IAB Internet Advertising
Revenue Report. https://www.iab.com/wp-content/uploads/2018/11/
REPORT-IAB-Internet-Advertising-Revenue-Report-HY-2018.pdf.
(2018). [Online: accessed 30-January-2019].
[14] S. Burklen, P. J. Marron, S. Fritsch, and K. Rothermel. 2005. User
Centric Walk: An Integrated Approach for Modeling the Browsing
Behavior of Users on the Web. In Proc. of the 38th Annual Symposiumon Simulation, (ANSS’05).
[15] M. Butkiewicz, D. Wang, Z. Wu, H. V. Madhyastha, and V. Sekar. 2015.
KLOTSKI: Reprioritizing Web Content to Improve User Experience on
Mobile Devices. In Proc. of the 12th USENIX Conference on Networked
Systems Design and Implementation, (NSDI’15).
[16] J. M. Carrascosa, J. Mikians, R. Cuevas, V. Erramilli, and N. Laoutaris.
2015. I Always Feel Like Somebody’s Watching Me: Measuring Online Behavioural Advertising. In Proc. of the Conference on Emerging
Networking Experiments and Technologies, (CoNEXT’15).
[17] C. Castelluccia, M. Kaafar, and M. Tran. 2012. Betrayed by Your Ads!:
Reconstructing User Profiles from Targeted Ads. In Proc. of the Conference on Privacy Enhancing Technologies, (PETS’12).

CONCLUSIONS AND FUTURE WORK

We have showed that a simple count-based heuristic can detect targeted advertising without having to perform complex
content-based analysis, i.e.without having to understand semantically webpages or received ads. To be able to run suchan algorithm, one needs a crowdsourced database of how
many users have seen each ad. Such a crowdsourced databasecan be built efficiently and without jeopardizing user privacy, i.e., without requiring users to report the actual ads they
have seen, nor the websites where they encountered them.
Our count-based heuristic and privacy preserving crowdsourced approach have been implemented in a first of its
kind distributed system called eyeWnder, which allows users
to audit any encountered ad impression in real-time to check
whether it is targeted or not. We have developed a detailed
validation methodology for the difficult problem of assessing
the accuracy of an ad detection method using only publicly
available information.
Crowdsourcing simplifies the ad detection problem. Any
crowdsourcing method, however, has two Achilles’ heels:
privacy risks and bootstrapping its user-base. We have addressed the first and taken only very preliminary measures
for the second. For example, we circulated it among otherresearchers, and enlisting some users for pay. This has permitted us to conduct a preliminary evaluation of eyeWnderand show that the count-based approach is indeed promising. Our current effort is to scale up our user-base. To doso, we will use traditional means, e.g., seeking more exposure through media, or getting help from data protection
authorities to enlist users. Scaling up the user-base will help
us refine our count-based ad detection method, evaluation,and probably yield many more interesting findings. This,
however, remains a task for future work.

ACKNOWLEDGEMENTS
The research leading to these results has received funding
from the European Union’s Horizon 2020 Research and Innovation Programme under grant agreements No 653449(project TYPES), No 786669 (project CONCORDIA), No 786741(project SMOOTH) and Marie Sklodowska-Curie grant agreement No 690972 (project PROTASIS). The paper reflects only
the authors’ views and the Agency and the Commission
are not responsible for any use that may be made of theinformation it contains.
13

ACM, ,
Iordanou et. al.
[18] C. Castellucciae, A. C-F. Chan, E. Mykletun, and G. Tsudik. 2009. Efficient and Provably Secure Aggregation of Encrypted Data in WirelessSensor Networks. ACM Trans. Sen. Netw. 5 (2009).
[19] S. Cohen and Y. Matias. 2003. Spectral Bloom Filters. In Proc. of theInternational Conference on Management of Data, (SIGMOD’03).
[20] A. Datta, M. C. Tschantz, and A. Datta. 2014. Automated Experiments
on Ad Privacy Settings: A Tale of Opacity, Choice, and Discrimination.
CoRR abs/1408.6491 (2014).
[21] Electronic Frontier Foundation EFF. 2019. Do Not Track. https://www.
eff.org/issues/do-not-track. (2019). [Online: accessed 30-January2019].
[22] eff.org. 2018. Privacy Badger blocks spying ads and invisible trackers. https://www.eff.org/privacybadger. (2018). [Online: accessed
30-January-2019].
[23] European Commission. 2018. Data protection in the EU, The General
Data Protection Regulation (GDPR); Regulation (EU) 2016/679. https://ec.europa.eu/info/law/law-topic/data-protection/. (2018). [Online:
accessed 30-January-2019].
[24] A. Everspaugh, R. Chatterjee, S. Scott, A. Juels, and T. Ristenpart.
2015. The Pythia PRF Service. In Proc. of the 24th USENIX Security
Symposium.
[25] G. C. Fanti, V. Pihur, and Ú. Erlingsson. 2016. Building a RAPPOR with
the Unknown: Privacy-Preserving Learning of Associations and Data
Dictionaries. PoPETs (2016).
[26] FigureEight. 2019. Human-in-the-loop for Machine Learning. https://www.figure-eight.com/. (2019). [Online: accessed 30-January-2019].
[27] J. M. Freedman, Y. Ishai, B. Pinkas, and O. Reingold. 2005. Keyword
Search and Oblivious Pseudorandom Functions. In Proc. of the Second
International Conference on Theory of Cryptography, (TTC’05).
[28] ghostery.com. 2019. Ghostery - Cleaner, faster, and safer browsing.
https://www.ghostery.com/. (2019). [Online: accessed 30-January2019].
[29] C. Graham and S. Muthukrishnan. 2005. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms
55 (2005).
[30] A. Hannak, G. Soeller, D. Lazer, A. Mislove, and C. Wilson. 2014. Measuring Price Discrimination and Steering on E-commerce Web Sites.
In Proc. of the Internet measurement conference, (IMC’14).
[31] C. Iordanou, C. Soriente, M. Sirivianos, and N. Laoutaris. 2017. Who is
Fiddling with Prices? Building and Deploying a Watchdog Service for Ecommerce. In Proc. of the Special Interest Group on Data Communication,(SIGCOMM’17).
[32] iWnder. 2019. iWnder Simulator. Withheld for double blind review.
(2019).
[33] S. Jarecki and X. Liu. 2009. Efficient Oblivious Pseudorandom Function
with Applications to Adaptive OT and Secure Computation of Set
Intersection. In Proc. of the 6th Theory of Cryptography Conference on
Theory of Cryptography, (TTC’09).
[34] H. Javaid, H. K. Khalil, Z. A. Uzmi, and I. A. Qazi. 2017. Online Advertising Under Internet Censorship. In Proc. of the 16th ACM Workshop
on Hot Topics in Networks, (HotNets’17).
[35] S. Keelveedhi, M. Bellare, and T. Ristenpart. 2013. DupLESS: ServerAided Encryption for Deduplicated Storage. In Proc. of the 22th USENIX
Security Symposium.
[36] K. Kursawe, G. Danezis, and M. Kohlweiss. 2011. Privacy-Friendly
Aggregation for the Smart-Grid. In Proc. of the Privacy Enhancing
Technologies, (PETS’11).
[37] N. Laoutaris. 2018. Data Transparency: Concerns and Prospects. Proc.
of the IEEE 106 (2018).
[38] M. Lecuyer, G. Ducoffe, F. Lan, A. Papancea, T. Petsios, R. Spahn, A.
Chaintreau, and R. Geambasu. 2014. XRay: Enhancing the Web’s

Transparency with Differential Correlation. In Proc. of the USENIX
conference on Security Symposium, (SEC’14).
[39] M. Lecuyer, R. Spahn, Y. Spiliopolous, A. Chaintreau, R. Geambasu,
and D. Hsu. 2015. Sunlight: Fine-grained Targeting Detection at Scalewith Statistical Confidence. In Proc. of the Conference on Computer andCommunications Security, (CCS’15).
[40] B. Liu, A. Sheth, U. Weinsberg, J. Chandrashekar, and R. Govindan. 2013.
AdReveal: Improving Transparency into Online Targeted Advertising.
In Proc. of the Workshop on Hot Topics in Networks, (HotNets’13).
[41] L. Melis, G. Danezis, and E. De Cristofaro. 2016. Efficient Private
Statistics with Succinct Sketches. In Proc. of 23rd Annual Network andDistributed System Security Symposium, (NDSS’16).
[42] J. Mikians, L. Gyarmati, V. Erramilli, and N. Laoutaris. 2012. Detecting
Price and Search Discrimination on the Internet. In Proc. of the Hot
Topics in Networks, (HotNets’12).
[43] J. Mikians, L. Gyarmati, V. Erramilli, and N. Laoutaris. 2013. Crowdassisted Search for Price Discrimination in e-Commerce: First Results.
In Proc. of the Conference on emerging Networking EXperiments andTechnologies, (CoNEXT’13).
[44] noscript.net. 2019. NoScript Firefox Extension. https://noscript.net/.
(2019). [Online: accessed 30-January-2019].
[45] F. Papaodyssefs, C. Iordanou, J. Blackburn, N. Laoutaris, and K. Papagiannaki. 2015. Web Identity Translator: Behavioral Advertising and
Identity Privacy with WIT. In Proc. of the 14th ACM Workshop on Hot
Topics in Networks, (HotNets’15).
[46] J. Parra-Arnau, J. P. Achara, and C. Castelluccia. 2017. MyAdChoices:
Bringing Transparency and Control to Online Advertising. ACM Trans.
Web 11 (2017).
[47] A. Plane, E. Redmiles, M. Mazurek, and M. Tschantz. 2017. Exploring
User Perceptions of Discrimination in Online Targeted Advertising. In
Proc. of the USENIX Conference on Security Symposium, (SEC’17).
[48] F. N. Ribeiro, K. Saha, M. Babaei, L. Henrique, J. Messias, F. Benevenuto,
O. Goga, K. P. Gummadi, and E. M. Redmiles. 2019. On Microtargeting
Socially Divisive Ads: A Case Study of Russia-Linked Ad Campaigns
on Facebook. In Proc. of the Conference on Fairness, Accountability, andTransparency, (FAT*’19).
[49] B. Rody-Mantha. 2017.
Mobile targeting: Where’s the line
between cool and creepy? http://mediaincanada.com/2017/03/20/
when-it-comes-to-targeting-how-much-is-too-much-for-canadians/.
(2017). [Online: accessed 30-January-2019].
[50] E. T. Schneiderman. 2016. A.G. Schneiderman Announces Results
Of “Operation Child Tracker”. https://ag.ny.gov/press-release/. (2016).
[Online: accessed 30-January-2019].
[51] B. W. Silverman. 1986. Density Estimation for Statistics and Data Analysis. Chapman and Hall/CRC.
[52] State of California. 2018. California Consumer Privacy Act – Assembly Bill No. 375. https://leginfo.legislature.ca.gov/faces/billTextClient.
xhtml?bill_id=201720180AB375. (2018). [Online: accessed 30-January2019].
[53] K. Thomas, E. Bursztein, C. Grier, G. Ho, N. Jagpal, A. Kapravelos, D.
Mccoy, A. Nappa, V. Paxson, P. Pearce, N. Provos, and M. A. Rajab.
2015. Ad Injection at Scale: Assessing Deceptive Advertisement Modifications. In Proc. of the 2015 IEEE Symposium on Security and Privacy,(SP’15).
[54] G. Venkatadri, A. Mislove, and K. P. Gummadi. 2018. Treads:
Transparency-Enhancing Ads. In Proc. of the 17th ACM Workshop on
Hot Topics in Networks, (HotNets’18).
[55] C. E. Wills and C. Tatar. 2012. Understanding What They Do with
What They Know. In Proc. of the Workshop on Privacy in the ElectronicSociety, (WPES’12).

14