View source for Data Platform/Data Lake/Traffic/Pageview hourly/Sanitization

In an effort toward privacy with regards to reader pageview data, we aim to sanitize the aggregate logs that we store long-term.  There are [[#Problems:_Reconstruction_of_browsing_patterns_.26_safe_data_publication|two reasons]] for sanitizing the dataset. The first is to protect our users from having their browsing pattern reconstructed if somebody hacks our cluster. The second is to publicly release aggregated datasets on interesting dimensions (user agent and geography, to be precise) without risk for our users. The [[#Solution:_Sanitizing_using_K-Anonymity_over_multiple_fields|approach chosen]] to sanitize the dataset is to anonymize (set value to unknown) certain values on rows, when the row is [[#Strategies|subject to identification]]. This page summarizes and links to details about the [[Analytics|Analytics Team]] approach, research and results on sanitizing the [[Analytics/Data/Pageview hourly|pageview_hourly]] dataset.  Our [[#Information_loss_analysis|analysis]] shows that the strategy we chose provides a strong level of resistance to attacks while still keeping a lot of value in our dataset.

== Problems: Reconstruction of browsing patterns & safe data publication ==

==== Browsing patterns reconstruction ====
As we found in our [[Analytics/Data/Pageview hourly/Identity reconstruction analysis|Identity reconstruction analysis]], an attacker with access to our cluster could follow user browsing patterns by combining two datasets: pageview_hourly and webrequest. More precisely, users with a rare combination of values in various fields, especially user-agent and geographical location, are at risk of first being identified in the more raw webrequest dataset, and then followed in pageview_hourly. We only keep data in the webrequest dataset for a short period of time, but we would like to keep pageview_hourly indefinitely, and so we need to make it safe against this type of attack. .

An analysis of the potential decay of fingerprinting data (see [[Analytics/Data/Pageview hourly/Fingerprinting Over Time|this page]] for more details) shows that data getting old doesn't imply enough change among user information to prevent us from sanitizing.

==== Safe pageview data publication ====
Our team core mission is to try to release publicly as much data as we can. The pageview_hourly dataset is no exception, and we'd like to use it to provide more data to our users. However the sensitivity of the data it contains needs us to be very careful about how we publish its content. This means:
* Separate page_title (or page_id) from other non-global dimensions (particularly geo data and user agent data) - Example of attack: A user modifies a page, therefore making a hit for that page_title in the pageview_hourly dataset<ref>pageview_hourly doesn't contain edits, but in order to make an edit, the probability that you'll have a pageview for the given page (either before or after editing) is very high.</ref>, and nobody else access that page for the given hour --> If we keep geo data and user agent data associated with page_title, the user geo and user agent becomes easily known. 
* Ensure published aggregated data is not easily reconcilable with page_title level traffic -  We have already released pageview data at page_title level of granularity (see [[Data Platform/AQS|pageview API in AQS]]). We want to be sure that newly published geo and user agent data aggregated at project / access / agent_type level will not be linkable to page_title traffic (or to be more precise, could only be linked to anonymized traffic were geo and user_agent data are not present anymore).

== Solution: Sanitizing using K-Anonymity over multiple fields ==
See [[Analytics/Data/Pageview hourly/Sanitization algorithm proposal|this page]] for a detail version of the algorithm we propose.

Very briefly, the idea is to group pageviews into buckets by sensitive fields, such as user agent and location.  When these buckets have less than <code>K<sub>ip</sub></code> disctinct IPs or less than Kpv distinct pages viewed, we anonymize one of the sensitive fields and repeat so that all possible buckets have more than <code>K<sub>ip</sub></code> distinct IPs and more than <code>K<sub>pv</sub></code> distinct pages viewed.  Fields with values that are unlikely to show up often are anonymized first.

== Strategies ==

=== The good Ks ===
We (the Analytics-Team) did a manual/qualitative review of browsing patterns over an hour with various distinct IPs, distinct pages and settings. Detailed data on exercise can be found on [[Analytics/Data/Pageview hourly/K Anonymity Threshold Analysis|this dedicated page]] along with Hive code.

==== We found that: ====
* When looking at groups of pages viewed by multiple people, it is sometimes easy to guess which sub-groups of pages could have been viewed together based on topics.
** It is however not possible to re-attach sub-groups to the underlying people with certainty.
** It could be feasible to reattach subgroups to the underlying people with some probability of being right using prior knowledge of browsing habits of those people.
* When looking at groups of pages having a small number of distinct pages, even with a very small number of distinct pages (2, 3, 4, 5), we have almost never identified those set sets as single sessions, and somewhat regularly we can identify them as two sessions.

==== It means that: ====
* The minimum anonymization we could go for would make sure that at least 2 distinct IPs and 2 distinct pages occur per bucket.
* We prefer to go on the safer side and add more variability to our buckets, ensuring that at least 3 distinct IPs and 5 distinct pages occur per bucket. It involves us anonymizing 91.28% of buckets making 35.11% of requests.

=== Choosing hourly or longer term data to establish the "uniqueness" of values in sensitive fields ===
We want to anonymize the most rare values first, because they are the most identifying. We can establish the "rareness" of each value by looking at either hourly statistics or longer term, such as monthly statistics:
* Using hourly statistics would establish a Local probability. This should reduce the processing time and the number of steps needed to terminate the algorithm (because locally rare values are anonymized first, leading to faster progress towards buckets of size greater than K).
* Using monthly statistics would establish a more Global probability. This normalizes any temporal patterns (such as hourly or weekly seasonality) and accounts for differences across time zones. This approach gives more value to global data quality but would run slower.

We decided as a team to use hourly statistics, for two reasons. One is technical computation resource, as statistics computation over a month would be very big, the other is data preservation, since using monthly statistics would mean anonymizing more data. 

== Information loss analysis ==

=== Entropy analysis - Definition ===

==== Per dimension ====
We used [[:en:Entropy_(information_theory)|Shannon Entropy]]  definition trying to measure how much information was lost in the process of anonymizing the pageview dataset.

For each fingerprinting dimension we computed entropy using the probability of a value (<code>P<sub>val</sub></code>) in the dimension as:

<math>
P_{val} = \sum_{rows} \textrm{view\_count}_{val} / \sum_{rows} \textrm{view\_count}
</math>

Entropy for the dimension was then computed using the formula:

<math>
H_{dim} = \sum_{val \in dim} P_{val} * \textrm{log2}(1 / P_{val})
</math>

An interesting point to notice is how to count <code>unknown</code> values in this definition. We have tried 3 methods:
* <code>unknown</code> as a regular value
* <code>unknown</code> only in adds to the total sum of view_counts for the dataset, but not as a value having a probability
* not counting <code>unknown</code> at all
Results have shown that the last method gives better result: more coherent in term of entropy definition, and providing a better view of how much data has been lost.

==== Global ====
Finally, we have computed a global value of entropy for the dataset, using the formula:

<math>
H_{dataset} = \sum_{row \in dataset} ( \sum_{val \in row} P_{val} * \textrm{log2}(1 / P_{val}) )
</math>

=== Entropy analysis - Results ===

==== Per dimension ====
[[File:Anonymization data loss per dimension.png|none|thumb|599x599px]]

==== Global ====
Tests realized over 3 hours at different time of the day (see next section for circadian patterns details):
{| class="wikitable"
!Hour (UTC)
!Entropy Default Dataset
!Entropy Anonymized Dataset
!Data loss
|-
|1
|65525642.24
|64143222.07
|2.11%
|-
|8
|65024942.53
|63503727.41
|2.34%
|-
|17
|87047745.81
|85519908.15
|1.76%
|}

=== Circadian Rhythm ===

==== Continents ====
[[File:Anonymization circadian continent.png|none|thumb|591x591px]]

==== Countries ====
[[File:Anonymization circadian country anim.gif|none|thumb|591x591px]]

[[Category:Pageviews]]
[[Category:Data platform]]