: Automated Privacy Policy Analysis using Knowledge Graphs

Hao Cui, Rahmadi Trimananda, Athina Markopoulou, Scott Jordan

University of California, Irvine

Privacy policies disclose how an organization collects and handles personal information.
Recent work has made progress in leveraging natural language processing (NLP) to automate privacy policy analysis and extract data collection statements from different sentences, considered in isolation from each other. In this paper, we view and analyze, for the first time, the entire text of a privacy policy in an integrated way.  In terms of methodology:
(1) we define , a type of knowledge graph that captures statements in a privacy policy as relations between different parts of the text; and
(2) we develop an NLP-based tool, , to automatically extract  from the text.
In addition,
(3) we revisit the notion of ontologies, previously defined  in heuristic ways, to capture subsumption relations between terms. We make a clear distinction between local and global ontologies to capture the context of individual privacy policies, application domains, and privacy laws.
Using a public dataset for evaluation, we show that  identifies 40% more collection statements than prior state-of-the-art, with 97% precision.
In terms of applications,
enables automated analysis of a corpus of privacy policies and allows us to:
(1) reveal common patterns in the texts across different privacy policies, and
(2) assess the correctness of the terms as defined within a privacy policy.
We also apply  to:
(3) detect contradictions in a privacy policy, where we show false alarms by prior work, and
(4) analyze the consistency of privacy policies and network traffic, where we identify significantly more clear disclosures than prior work.

§ INTRODUCTION

Privacy Policies Privacy laws, such as the General Data Protection Regulation (GDPR) <cit.>, the California Consumer Privacy Act (CCPA) <cit.>, and other
data protection laws, require organizations to disclose the personal information they collect, as well as how and why they use and share it.
Privacy policies are the primary legally-binding way for organizations to disclose their data collection practices to the users of their products. They receive much attention from many stakeholders, such as users who want to exercise their rights,
developers who want their systems to be compliant with privacy laws,
and law enforcement agencies who want to audit organizations' data collection practices and hold them accountable.
Unfortunately, privacy policies are typically lengthy and complicated, making it hard not only for the average user to understand, but also for experts to analyze in depth and at scale <cit.>.

(a)     (b)     (c)

Example of a privacy policy and analysis approaches.
(a) The excerpt is from the policy of KAYAK <cit.>.
It contains sections and lists, regarding: what is collected (data type), how it is used (purpose), who receives the information (entity), and references across sentences ( “personal information” relates to other data types; “this information” refers to “location”).
(b) Prior work extracts elements found in each sentence, mainly data types and entities, as disconnected tuples. Purposes can also be extracted to extend the tuple <cit.>.
(c)  is a knowledge graph that encodes data types, entities, and purposes; and two types of relations between them (collection and subsumption), possibly specified across different sentences. A  edge represents that a data type is collected by an entity, while edge attributes represent the purposes of that collection.  edges represent the subsumption relations between generic and specific terms.

NLP Analysis and Limitations
To address this challenge, as well as to facilitate expert analysis <cit.> and crowdsourced annotation <cit.>, the research community has recently applied natural language processing (NLP) to automate the analysis of privacy policies.
State-of-the-art examples include the following: PolicyLint <cit.> extracts data types and entities that collect them, and analyzes potential contradictions within a privacy policy; PoliCheck <cit.> builds on PolicyLint and further compares the privacy policy statements with the data collection practices observed in the network traffic; Polisis <cit.> and PurPliance <cit.> extract data collection purposes; and OVRseen <cit.> leverages PoliCheck and Polisis to associate data types, entities, and purposes.
Despite promising results, this body of work also has certain limitations.

First, existing privacy policy analyzers extract statements (about what is collected,  data type; who collects it,  entity; and for what purpose) as disconnected labels <cit.> or
tuples <cit.>,
ignoring the links between information disclosed across sentences, paragraphs or sections.
However, today's privacy policies typically have a structure that discloses data types being collected, third-party sharing and usage purposes in separate sections
We read through 200 privacy policies in our test set (see Section <ref>).
Among them, 135 discuss definitions and practices concerning the same data types in different sections, requiring to put the information together to get the full context about collection, use and sharing of these data types.
In particular, 104 divide content into sections addressing collection, use, and sharing of “personal information”, resembling the structure shown in Figure <ref>(a).], as shown in the example in Figure <ref>(a).
Polisis <cit.> uses separate text classifiers to label data types, third-party entities and purposes disclosed in each paragraph.
Without connecting these labels, it is unclear which data type is collected by which entity, and what purpose applies.
PolicyLint <cit.> and PurPliance <cit.> adopt tuple representations that put together entities, data types and purposes disclosed in each sentence, as shown in Figure <ref>(b).
However, the tuples still miss context from other sentences. For example, it cannot be inferred from the tuples that the purpose “provide features” applies to the collection of “location”;
or that the usage purposes and third-party entities in later sections are related to the specific types of “personal information” ( “device information”) listed in the first section.

Second, because of this incomplete context, prior work
needs to map and relate the semantics of the terms across different sentences
by introducing ontologies that encode subsumption relations between data types or entities. So far, these ontologies have been built in a manual or semi-automated fashion by domain experts, who define lists of terms commonly found in privacy policy text and other sources ( network traffic), and subsumption relations between them ( the term “device information” subsumes “IP address”). The resulting ontologies are not universal: they do not necessarily agree with all privacy policies and need to be adapted to different application domains,  mobile <cit.>, smart speakers <cit.>, and VR <cit.>.
As a result, they often generate ambiguous or wrong results that require further validation by experts. Manandhar  <cit.> recently reported  that state-of-the-art  analyzers <cit.> incorrectly reason about more than half of the privacy policies they analyzed.

The  Framework Our key observation is that a policy[In the rest of the paper, we refer to a privacy policy simply as “policy”.] should be treated in its entirety, leveraging terms in different sentences that are related. To that end, we make the following methodological contributions.

First, we propose to extract and encode statements in a policy ( what data types are collected, with what entities they are shared, and for what purposes) into a knowledge graph <cit.>, which we refer to as ; Figure <ref>(c) shows an example .
Nodes represent data types or entities. Edges represent relations between nodes,  an entity may collect a particular data type, and a more generic data type may subsume a more specific data type.
An edge representing data collection may have an attribute indicating the purposes.

The graph in Figure <ref>(c) naturally links the extracted information by merging the same data types and entities and establishing edges between them. It allows inferences such as “IP address” being collected for the purpose “provide services”, and “location” being collected by “travel partners”.

Examples of  edges, representing collection of a data type by an entity: (1) “we” (first party,  KAYAK) collect “personal information”,  with the purposes “provide services” and “authenticate your account”; (2) “travel partners” collect (or precisely, are disclosed with) “personal information”. Example of  edges, representing subsumption relations: “personal information” subsumes “location” and “device information”, which in turn subsumes “IP address”.

Second, for policies that are not well written, the extracted  may be missing subsumption relations between terms that are not fully defined in the policies.
To supplement the missing relations, we use ontologies, as in prior work <cit.>; however, we redefine and use them as follows. First, we consider the subsumption relations extracted from each individual policy as the local ontology definied by it. Next, we also define additional subsumption relations that encode external knowledge, beyond what is stated in the text of an individual policy; we refer to these as global ontologies. They can be defined by domain experts,
using information from multiple policies, or from privacy laws; for example, in Section <ref>, we define a data ontology based on the CCPA <cit.>.

Third, we present , a methodology and implementation that applies NLP linguistic analysis to automatically extract and build a  from the privacy policy text. To that end, we address several challenges, including coreference resolution, list parsing, phrase normalization, and purpose phrase classification, to extract and link more information than previously possible.

We evaluate  on a public dataset from PoliCheck
<cit.>, consisting of over 6K policies from over 13K mobile apps.
Our manual validation shows that  improves the recall of collection statements from 30% to 70%, compared to prior work <cit.>, with over 90% precision.
The improvement is enabled by both the improved NLP techniques and the knowledge graph representation, which can analyze statements spanning multiple sentences and sections.

Applications  enables two new types of automated analyses, which were not previously possible.
First,  is used to summarize policies in our dataset and reveal common patterns across them.
This is possible because , by representing each policy as a whole, allows inferences about more collection statements.
We find that 64% of policies disclose the collection of software identifiers and, in particular, cookies. Advertisers and analytics providers are major entities that collect such data. This is further reinforced by the finding that more than half of the policies disclose data usage for non-core purposes, namely for advertising and analytics.
We also find that the use of generic terms for data types ( “personal information”), often without more precise definitions, reduces the transparency and leaves the specific data types being collected unknown.
Second, different policies may have different definitions of the same terms.
By clearly separating local ontologies from global ones,  allows us to assess the correctness of the term definitions.
For example, we find that many policies declare the collected data as “non-personal information”, which contradicts common knowledge and our CCPA-based global data ontology (see Sections <ref> and <ref>). We also find that non-standard terms are widely used, with varied definitions across policies.

We also apply  to revisit two known applications of policy analysis.
First, to identify contradictions within a policy, we extend  to analyze negative statements and take into account additional contexts that are crucial for interpreting contradictions, such as (1) fine-grained actions ( “sell” for profit  “sharing”), and (2) data subjects ( children  general users).
We show that the majority of contradictions found by prior work are false alarms due to language nuances and missing contexts ( data subjects).
Second, we apply  to analyze data flow-to-policy consistency. As a result of the improved recall of our approach, we show that prior work <cit.> has underestimated the number of policies that clearly disclose some sensitive data flows.

Overview The rest of the paper is structured as follows.
Section <ref> defines the proposed  framework and the ontologies used with it.
Section <ref> describes the implementation of  that uses NLP to build  from the text of a policy.
Section <ref> presents the evaluation of our framework.
Section <ref> presents applications of  to policy analysis.
Section <ref> discusses related work.
Finally, Section <ref> concludes the paper.

§ THE  FRAMEWORK

In this section, we introduce , our proposed representation of the entire text of a policy as a knowledge graph.
We also revisit the related notion of ontologies,
and we propose a new definition and use it with .

§.§ Defining

We define  as a knowledge graph that captures statements in a policy considered as a whole. Throughout this section, we will use Figure <ref> as our running example to illustrate the terminology and definitions.

Privacy laws, such as the GDPR <cit.> and the CCPA <cit.>, require that organizations disclose their practices regarding data collection, sharing and use in their policies. To capture these three aspects of disclosures in the policy, we represent the corresponding three kinds of terms in : what data types are collected, with what entities they are shared, and  for what purposes they are used.

* Data type: This kind of terms refers to the type of data being collected.  In Figure <ref>(a), “location” is a specific collected data type. Generic terms can be used as well,  “personal information” and “device information”.

* Entity: This kind of terms refers to the organization that receives the collected data. It can be the first party if it is the developer of the product ( website, mobile app, ) that writes the policy, namely “we” in Figure <ref>(a); or, otherwise, a third party such as “travel partners” in Figure <ref>(a).

* Purpose: Policies may also specify purposes.[In this paper, we refer to purposes of processing of personal data as specified in the GDPR, namely the purposes of collection, use, and sharing. US laws often distinguish among the three,  the CCPA appears to require a policy to separately disclose the purposes of collection / use and the purposes of sharing personal information.]
In Figure <ref>(a), purposes include “provide services”,  “authenticate your account”, and “provide features”.

In , we represent data types and entities as two different types of nodes. Furthermore, we encode the following relations between them as edges.

*  edge: An entity $n$ may collect a  data type $d$.
In Figure <ref>(a), “personal information” is collected by the first-party entity “we”, but it is also shared with the entity “travel partners” (a third party).
More formally, a  edge $e_c=n$COLLECT$d$ between an entity $n$ and a data type $d$  represents that $d$ is collected by $n$, namely $collect(n, d)$.

*  edge: A generic term (hypernym) may subsume a more specific term (hyponym). For example, “personal information” subsumes “device information” and “location”, and “device information” in turn subsumes “IP address”. More formally, a  edge $e_s=hyper$SUBSUME$hypo$ connects nodes $hyper$ and $hypo$, where both nodes $hyper,~hypo$ are data types or both are entities, and it represents that the more generic term $hyper$ subsumes the more specific term $hypo$, namely $subsume(hyper,~hypo)$.

* Purposes as edge attributes:
We represent purposes by assigning them as a list of attributes $Purposes(e_c)\!=\!\{p_1, p_2, ...\}$ to each  edge $e_c$. This is a natural choice that fits how policies are written: one or more purposes are typically associated with a data type and an entity.  In Figure <ref>(a), entity “we” ( KAYAK) collects “this information”, which refers to “location”, for the purpose “to provide features”.
The purpose “to provide features” is captured in the list of attributes $Purposes(e_c)\!=\!\{\textit{provide features}\}$ assigned to the  edge $e_c\!=\!we$COLLECT$location$.

In summary, we define , representing knowledge about data collection, sharing and use disclosed within a particular policy, as follows.

A  $G = \langle D, N;$ $E_{S}, E_{C}; P \rangle$ is a directed acyclic graph.
Each node represents a term that is either a data type $d \in D$ or an entity $n \in N$. Each edge can be either a  edge $e_s \in E_{S}$, or a  edge $e_c \in E_{C}$ as defined above.
A  edge $e_c$ has a list of attributes Purposes$(e_c)=\{p_1, p_2, ...\}$, where $p_i \in P$.

Figure <ref>(c) shows the  representation of the policy text in Figure <ref>(a). The technical details about building the graph from verbatim text, such as how to map the co-reference term “this information” to “location”, are provided in Section <ref>.
Next, we define relations that can be inferred from  about policy text.

Subsumption Relation.
In a  $G$, we say that a term $t_1$  (hypernym) subsumes another term $t_2$ (hyponym), denoted as $subsume(t_1, t_2)$, iff there exists a path from $t_1$ to $t_2$ in $G$ where every edge is a  edge.[A subsumption relation is naturally transitive. To simplify other definitions, we also make it reflexive,  every term subsumes itself.

Collection Relation.

In a  $G$, we say an entity $n\!\in\!N$ collects a data type $d\!\in\!D$, denoted as $\mathit{collect}(n, d)$, iff there exists an entity $n' \in N$ and a data type $d' \in D$ where
$subsume(n', n) \wedge{} subsume(d', d)$[That is, a policy may disclose data collection using generic terms. For instance, in Figure <ref>(c), we have $\mathit{collect}(\textit{we}, \textit{IP address})$ because “IP address” is also “personal information”.]
and the edge $n'$COLLECT$d'$ exists in $G$.

Set of Purposes.

Following Definition <ref>, if a purpose $p \in \mathit{Purposes}(n'$COLLECT$d')$, we say $n$ collects $d$ for the purpose $p$. We denote the set of all instances of such $p$ in $G$ as a set $\mathit{purposes}(n, d)$.

Beyond what is captured by individual nodes, edges, and attributes, the strength of  is that it allows us to make inferences.
In Figure <ref>(c), there is no direct edge from “travel partners” to “location”, but we can still infer that “location” may be shared with “travel partners” and “social network services”.
we can also infer that $collect$(we, location) and $purposes$(we, location) = $\{ \textit{provide features} \}$.
Such data practices that are implied, but not explicitly stated, would be missed by prior work that only processes individual sentences, and possibly by human readers as well.

Prior state-of-the-art work would have extracted a list of tuples, as depicted in the example of Figure <ref>(b). PolicyLint  <cit.>  and follow-up works <cit.> extract 2-tuples: $\langle$entity, data type$\rangle$. Purposes can be extracted independently
and appended to form a longer 3-tuple $\langle$entity, data type, purpose$\rangle$ as in OVRseen <cit.>, or put in a nested tuple as in PurPliance <cit.>.
In all cases, those tuples are extracted from individual sentences that are disconnected from each other. As a result, prior work would fail to identify implied statements. In contrast,   connects terms with the same semantics in different sentences, allowing
inferences and improving coverage.

Another major strength of  is that its modular design makes it easy to extend to capture additional relations.

In Section <ref>, we present  extensions to handle finer-grained semantics, including negative edges and subtypes of  edges to distinguish among data actions ( “sell” for profit  “sharing”), as well as data subjects.

§.§ Ontologies

Policies refer to data types and entities at different semantic  granularities. For example, “device information” in Figure <ref>(a) is a generic data type that subsumes “IP address” and maybe other more specific data types.
Prior work <cit.> has introduced hierarchies of terms, namely ontologies, to define the subsumption relations between data types or entities.
They typically define the data and entity ontologies heuristically and manually, by considering a combination of information found in the network traffic and in the policy text, as well as using domain expertise to organize terms into hierarchies.

We revisit the notion of ontologies under the  framework.
First,  naturally captures subsumption relations described in an individual policy, which form the local ontology.
Ideally, if a policy is written in a clear and complete way, it should either use specific terms, or clearly define generic terms that will be captured by the corresponding local ontology.
In practice, policies are not perfectly written and parts of the ontology may be missing.
For example, in Figure <ref>(a), the term “social networking services” is not further explained.
Furthermore, some policies may provide misleading definitions,  “geolocation” is described as non-personal information, whereas it is widely considered personal by the public and privacy laws (see Section <ref>).
Second, we define and design global ontologies that encode external knowledge or ground truth, as in prior work.
For the first time, the distinction between local and global ontologies provides a principled way to summarize an individual policy, as well as to assess the completeness and correctness of definitions by comparing the local against the global ontologies.

§.§.§ Local Ontologies

In ,  edges between data types or entities induce a directed acyclic graph, which we refer to as a local ontology, capturing the relations between more generic and more specific terms, as defined within a particular policy. We define local data and entity ontologies as follows.

Local Ontology.

A local ontology is either a data ontology $o_d=\langle D, E_{d} \rangle$ or an entity ontology $o_n=\langle N, E_{n} \rangle$, a directed acyclic graph that is a subgraph of  $G = \langle D, N; E_{S}, E_{C}; P \rangle$, in which every node is a data type $d \in D$ or an entity $n \in N$, and every edge $e_d \in E_{d}, e_n \in E_{n}$ (where $E_{d},E_{n} \subset E_{S}$) is a  edge.

In Figure <ref>(c), the four blue nodes containing data types form the local data ontology: the root node is “personal information” and the leaf nodes are “location” and “IP address”.
The local entity ontology, which contains the three green nodes, does not have a nontrivial hierarchical structure because the policy does not further explain the terms “travel partners” and “social networking services”.

§.§.§ Global Ontologies

We define a global ontology to encode external knowledge,  outside a particular policy, which we consider as ground truth in that context.
It provides a reference against which we can compare and evaluate individual policies, as well as a complement to missing definitions in policies.

Global Data Ontology based on the CCPA.

Global Ontology.

A global ontology is either a data ontology $O_d=\langle D_{d},E_{d} \rangle$ or an entity ontology $O_n=\langle N_{n},E_{n} \rangle$ that is a directed acyclic graph, where every node is a data type $d \in D_{d}$ or an entity $n \in N_{n}$, and every edge $e_d \in E_{d}$ or $e \in E_{n}$ is a  edge.

Prior work <cit.> has implicitly and heuristically defined such global ontologies, by taking into account and combining
the union of all subsumption relations extracted from policies in their corpus, and
the data types and entities observed in the actual system's output ( network traffic).
However, such global ontologies have not been universal: they may include subjective judgment, and they typically do not apply across application domains.
For example, PoliCheck's data ontology does not assume “personal information” to include “device information”: this contradicts the content of the policy depicted in Figure <ref>(a). Although we recognize that there is no single way to define perfect global ontologies, we propose that we rely on authoritative sources, such as privacy laws, to define them. An example is described next, but other designs can be used with  as well.

Global Data Ontology Based on the CCPA
As a concrete, illustrative example, we propose a global data ontology that is based on the CCPA <cit.>.
The CCPA governs the collection, use, and sharing of personal information, as defined therein, by companies that do business in California.
To build the CCPA-based global data ontology, we start with the definition of “personal information” in CCPA Section 1798.140(v)(1), which includes, but is not limited to, specific data types, including a person's name, social security number, postal address, email address, and IP address. We place such specific data types into the ontology as leaf nodes. Then, since policies often disclose the collection of categories of these specific data types,  “contact information” instead of “email address” and “postal address”, we organize these specific data types into categories delineated by subsumption relations. The CCPA's definition of personal information also includes categories for which it does not list specific data types,  “biometric information”. In such cases, we include the categories in the global data ontology and augment it with common specific data types,  “biometric information” includes “voiceprint” and “fingerprint”. Similarly, the CCPA uses the term “device identifier” but does not define it, while we include it as a category in the global data ontology, and place specific device identifiers in that category. Figure <ref> shows the CCPA-based global data ontology.
The above is meant as a concrete example of a global ontology based on a privacy law. Different laws ( GDPR) can lead to different global ontologies.

Global Entity Ontology based on <cit.>.

Overview of  implementation. First,  preprocesses the HTML document to produce a simplified document tree structure. Second, the NLP pipeline takes the document tree and labels sentences with linguistic labels. Third, the labeled sentences are annotated by the annotators to produce a phrase graph containing all the annotations. Finally, the graph building stage deploys term normalization and purpose classification to transform the phrase graph into a .

Global Entity Ontology
Privacy laws give examples of the types of entities, but not the exhaustive list of entities, with whom an organization may share personal information.
We follow policies that often categorize entities by service types.
We obtain a list of entities and their categories from the DuckDuckGo Tracker Radar dataset <cit.> and a CrunchBase-based dataset <cit.>. Based on these sources, containing 4,709 entities in total, we propose a simple two-level ontology that classifies entities into six categories as shown in Figure <ref>.

The global ontologies, serving as the ground truth of subsumption relations, are used to categorize unorganized data types and entities in s (see Section <ref>), assess the correctness of term definitions in individual policies (see Section <ref>), as well as complement term definitions in case of missing definitions when we check vague disclosures of data flows (see Section <ref>).

§  IMPLEMENTATION

We present , the NLP-based system that we implement to generate  from the text of a policy.
Figure <ref> gives an overview of its implementation.

§.§ NLP on Structured Documents

HTML Preprocessing
Policies are usually published online as structured documents, mainly in HTML format, while NLP models expect plain text input. Simply stripping HTML tags, such as headings and lists, would result in a loss of semantics.
As the first step,  preprocesses each HTML document to a simplified document tree which preserves three important document structures: heading, list item, and general text.
The document tree helps to generate complete sentences as input for NLP.
Please see appendix:html-preprocessing for details.

NLP Pipeline
is built based on the spaCy library <cit.> and its RoBERTa-based NLP pipeline <cit.>.
The NLP pipeline labels text with linguistic labels originating from English linguistic features, including word lemmas, part-of-speech, sentence segmentation, and syntactic dependency trees (see the output of “NLP Pipeline” in Figure <ref>). These features are syntactic and thus require no domain adaptation.

To identify data types and entities in a policy,  uses named entity recognition (NER), a standard NLP technique to classify noun phrases into a given set of labels. In our case, we use two labels: DATA for data types and ENTITY for entities. To train the NER model, we use a synthetic training set that combines generated sentences and real policy text prelabeled by an existing NER model and rule-based NER.
Please see appendix:ner-methodology for details.

Overview of annotators in .

§.§ Annotators

In , we refer to the modules that identify relations between phrases as annotators. The relations are stored as edges in a graph structure, which we call a phrase graph. The phrase graph is still an intermediate step, in which phrases referring to the same thing have not been merged.

We use “phrase” to refer to verbatim words and phrases in the policy text. We use “term”, which appears in previous sections as well, to refer to the normalized forms (see Section <ref>) of phrases that appear in s.

To extract relations between phrases, annotators search for phrases matching specific syntactic patterns <cit.>.
In contrast to prior work that hardcodes heuristics to perform the search <cit.>, we use dependency matching to specify desired patterns as configurable rules <cit.>. For example, in the collection annotator, we set the rule collect|gather|obtain|...:ROOT to match the root verb “collect”. Then the sub-rule ENTITY:subj matches the subject “we” under the verb as the entity, and another sub-rule DATA:obj matches the object “device information” as the data type. The annotator then adds a  edge between them in the phrase graph.

By dividing linguistic analysis tasks into five annotators, each of them focuses on a specific set of patterns. Table <ref> outlines the patterns and relations that each annotator tries to identify. Note that some edge types ( and ) exist only in the phrase graph and will be converted in the final . We discuss each annotator as follows.

Collection Annotator
The collection annotator finds affirmative sentences that disclose data collection, use or sharing, extracts entities and data types, and adds  edges from entities to data types in these sentences.
The annotator matches around 40 verbs and 20 sets of syntactic patterns. Table <ref> lists some of the patterns in the active voice. For clarity, we do not list patterns in the passive voice ( “this information is shared with...”) and composite patterns ( “allow us to collect...”), but they are all handled by the annotator. We gather these patterns from actual policies in the dataset which we use to evaluate  (see Section <ref>).

The collection annotator only labels  edges for affirmative statements. To distinguish affirmative sentences from negative and interrogative ones, it checks the existence of negative modifiers ( not, never) and interrogative words in the dependency tree. While negative statements are by default excluded, we extend  in Section <ref> to use the information to analyze negative statements.

0.8Syntactic patterns used by the collection annotator.

Subsumption Annotator
The annotator identifies subsumption relations between phrases and adds  edges from a hypernym to its hyponyms.
It matches 11 syntactic patterns of subsumption as shown in Table <ref>. These extend the patterns used in prior work <cit.>.

Purpose Annotator
The annotator identifies phrases that describe purposes of data collection in three forms: (1) in order to $\langle$verb$\rangle$ ...; (2) to $\langle$verb$\rangle$ ...; (3) for ... purpose(s). It links such purpose phrases to corresponding data types with  edges, which are not part of  and will be converted into $Purposes(\cdot)$ attributes on the corresponding  edges in . For example, in the sentence “We use this information to provide ads”, the purpose phrase “to provide ads” is linked to the data type “this information”.

Coreference Annotator
The annotator resolves pronouns ( “it”, “they”, ) or phrases modified by demonstrative determiners ( “this”, “those”, ) to the phrases which they refer to. This task, known as coreference resolution, is a non-trivial NLP task.
Prior work <cit.> could not handle coreferences properly, which has resulted in a loss of semantics and misinterpretation of many collection statements.

We find that existing coreference resolution models <cit.> cannot handle non-personal references well, whereas they are commonly found in policies.
To address the issue, we design a heuristic-based coreference annotator that handles common forms of coreferences in policies.
First, for a phrase starting with a determiner “this”, “that”, “these”, “those” or “such” ( “these providers”), the annotator looks backward for the nearest phrase with the same root word ( “ad providers”) in the same or previous sentence. Specifically, if the root word is “data” or “information” ( “this information”), the annotator looks backward for the nearest data type labeled by NER as the referent.
Second, for a pronoun like “it”, “this”, “they”, or “these”, the annotator tries to infer whether the pronoun refers to a data type or an entity based on existing  edges, and looks backward for the nearest data type or entity.
The annotator links coreference phrases to the referred phrases with  edges, which are only used in phrase graphs to resolve coreferences.

We evaluate our method on 200 coreferences from our test set (see Section <ref>). 168 are resolved correctly. Four coreferences are partially resolved because they refer to multiple phrases while the annotator supports only one referent for each phrase. The other 28 are not resolved or are resolved wrongly. This yields 84-86% accuracy, which suggests that it outperforms general-purpose coreference models.[For example, Coreferee <cit.> reported 82-83% accuracy on general corpora. However, as it does not treat data types as named entities, it cannot resolve coreferences of data types.]

0.9Syntactic patterns used by the subsumption annotator.

List Annotator
This special annotator uses the document tree to discover relations between list items and their preceding sentence.
First, if a noun phrase modified by “following” or “below” ( “the following information”) precedes list items, it adds  edges from the phrase to list items.
Second, it propagates relations between the preceding sentence of a list and any list item to all list items in case other annotators fail to label them.

§.§ From Phrase Graph to

The final step of  is to build a  from a phrase graph. This involves merging phrases (data types and entities) with the same meaning to one node and converting purpose phrases to edge attributes.

Normalizing Data Types and Entities
starts by mapping data types and entities in the phrase graph to their normalized forms. For example, “contact details” and “contact data” are synonyms to the normalized term “contact information” which we want to keep in the .

For data types and entities in our global ontologies (see Section <ref>), we consider them as standard terms and write regular expressions to capture their synonyms.
For example, the regular expression contact.̱*(̱information|data|detail|method) matches synonyms of “contact information”.  maps these synonyms to “contact information”, which aligns with the term in the global data ontology, as the normalized form.
We also programmatically create regular expressions for variants of company names from public datasets. If a phrase is not a standard term and thus does not match any regular expressions,  simply strips stop words and takes the lemmatized form of the phrase as the normalized form. For example, “your vehicle records” is normalized to “vehicle record”. This is usually enough to capture variants of the same term caused by word inflections.

For coreferences, as the annotator has linked each coreference phrase to what it refers to,
follows the  edge to find the referred phrase and use the same normalized form. For example, in Figure <ref>(a), “this information” would be normalized to “geolocation”, same as the phrase “location” that it refers to.
Please see appendix:phrase-normalization for details on the phrase normalization.

Unspecified Data and Unspecified Third Party
As a special case of phrase normalization, policies often use blanket terms like “information” and “third party” without further details.
For example, in the sentence “We collect information to provide services”, the word “information” can be interpreted as unspecified (or all possible) data types.
We find it more appropriate to treat such blanket terms specially than assuming them to have consistent meaning across the text.
uses two special nodes, “unspecified data” for data types and “unspecified third party” for entities, as the normalized forms of such blanket terms in s. Please see appendix:phrase-normalization for details.

Classifying Purpose Phrases
The purpose annotator identifies purpose phrases. To allow automated analysis of , we coarsely group purpose phrases into five categories:
advertising, and
These categories are derived from the business and commercial purposes defined in the CCPA <cit.>.
As in prior work <cit.>, we distinguish between core ( services, security, and legal) and non-core ( advertising and analytics) purposes of data collection.

We fine-tune a sentence transformer model <cit.> to classify purpose phrases into these categories. For example, the phrase “to provide features” is classified as services, whereas the phrase “for advertising purposes” is classified as advertising.
Note that a purpose phrase can be classified into multiple labels if it mentions more than one purpose.
To train the model, we manually annotate a dataset of 200 phrases. We use SetFit <cit.> to enable few-shot fine-tuning with this small dataset.
This can be done because the underlying transformer model is already trained on a large corpus to gain language knowledge, and SetFit takes advantage of contrastive learning to learn the differences between classes effectively.
The performance of purpose classification is reported in Section <ref>.

Finally,  builds the  from the phrase graph by merging phrases with the same normalized form into one node, keeping  and  edges, and inferring the $Purposes(\cdot)$ attributes
from  edges in the phrase graph.

Figure <ref> shows an example of a  generated from a simple policy <cit.> for demonstration purposes.
Due to a lack of space, we show a subset of data types. The complete version can be found in Figure <ref> in appendix:poligraph-example.
A typical  from the policies that we have analyzed (see Section <ref>) can contain up to hundreds of nodes and edges.
It is common to see vague phrases like “statistical user data” that are not further clarified, and misleading definitions like claiming anonymized information to include data types that are likely personal and identifiable. However, it is important that  does capture data collection, along with its s, and subsumptions for further analysis.

The  generated from “Puzzle 100 Doors” app's policy <cit.>.

Statistics of common  edges. The numbers of edges that have $Purposes(\cdot)$ attributes are shown in parentheses.

Statistics of common  edges between data types.

§  EVALUATION

In this section, we evaluate 's performance in analyzing policies. At the beginning of each subsection, we state the research question (RQ) addressed therein, our approach, and a preview of the results.

The PoliCheck Dataset Throughout this section and Section <ref>, we use the public dataset provided by PoliCheck <cit.>.
We choose this dataset because it is among the largest public datasets for policies. The dataset consists of policies of 13,796 Android apps on Google Play Store. The number of policies is large enough to necessitate automated analysis.
Furthermore, it also comes with the apps' network traffic data that facilitate flow-to-policy consistency analysis in Section <ref>. We write a crawler script based on the Playwright library <cit.> to download the policy text from each URL. We obtain the most recent version of the policies from March 2023. After excluding non-English, invalid, and duplicate webpages, we obtain 6,084 unique policies used by 13,626 apps.

Test Set Out of the full PoliCheck dataset, we randomly select a set of 200 policies, and we read and annotate them in order to build ground truth for various evaluation tasks. This test set has no overlap with the data used to generate the NER corpus or to train the purpose classifier (see Section <ref>).

§.§  Generation

RQ1. How accurate is  in generating s from policies  the definitions in Section <ref>?

To answer this question, we present the statistics of 's  and  edges, as well as manual validation of the precision of these edges. The tool successfully generates s for 5,255 policies. The remaining policies cannot be processed because they either do not claim to collect data, or use irregular or unsupported HTML tags that cannot be correctly parsed.

§.§.§ Characterization of  Edges

First, we characterize the  and  edges in the s generated by .

extracts 103,185  edges from 100,565 sentences in total. Among them, 34,052 edges have $Purposes(\cdot)$ attributes from 38,994 purpose phrases.
Figure <ref> shows the common  edges found in the dataset.
Generic terms, such as “personal information” and “personal identifier”, are commonly used to express data types in policies.
Some specific terms, such as “cookie / pixel tag”, “email address”, and “ip address” are also found in many policies.
Furthermore, we find that policies disclose data collection  by first-party ( “we”) more frequently than by third-party entities. Major third-party entity categories are “advertiser” and “analytic provider”. Google, as the platform, is also frequently mentioned in the policies.

extracts 52,007  edges from 20,959 sentences in the dataset. Figure <ref> shows common  edges that connect data type nodes. “Personal information”, “contact information” and “personal identifier” are the most frequently used generic terms to represent data types. Notably, we find that many policies declare the collected data as “non-personal information”: this conflicts with our CCPA-based global data ontology. We will discuss the issue of misleading definitions in Section <ref>.

“Unspecified” The nodes “unspecified data” and “unspecified third party” (see Section <ref>) are found in 72.0% (3,785) of s. This is because many policies discuss data collection, sharing, and use in separate sections. When they discuss sharing, precise data types are often omitted. When they discuss purposes of use, both data types and entities can be unspecified terms. For example, KAYAK's policy states: “To protect rights and property, we may disclose your information to third parties” <cit.>. Without further details on “information” and “third parties”, the statement is captured in the  as unspecified third partyCOLLECTunspecified data with security as the purpose.

§.§.§ Manual Validation of s

We manually evaluate whether  extracts the correct edges. To evaluate the precision of  edges, we sample five edges from each of 100 randomly selected s in the dataset and read the corresponding policy text to validate whether each edge is correctly extracted from the text. To help with this evaluation,  stores the sentences from which each edge is generated.
We find that the precision for  edges is 90.4%, and the precision for  edges is 87.7%.[We do not evaluate recall as it turned out to be difficult for humans to label edges without biases for all data types and entities. We will report recalls in Section <ref> where we consider a subset of common data types.]

In theory, false positive edges can propagate to more incorrect inferences. For example, a false advertiserCOLLECT personal information edge would lead to wrong inferences of advertiser collecting all data types subsumed by personal information. However, we find that such cases are rare, and false positives are often caused by recognizing irrelevant phrases as data types or entities[For example, in the sentence “the app may use third party code”,  mistakes “third party code” as a data type.], which is less of an issue if we scope the analysis to a subset of common data types or entities (as we show in Section <ref>). Most false-positive edges come from NLP errors including: (1) NER recognizing irrelevant phrases as data types or entities, and (2) mistaking some interrogative or negative sentences as affirmative statements.

We also evaluate 's purpose classification model.

We randomly sample five purposes phrases identified by the purpose classifier from each policy in the test set, manually assign labels to the phrases, and compare them to the ones labelled by the purpose classification model.

Overall, the macro-averaged precision and recall are 91.0% and 94.8%, respectively, for this multi-label multi-class classification task.

§.§ Comparison to Prior Policy Analyzers

RQ2. How well does  analyze collection statements compared to prior state-of-the-art policy analyzers?

To answer this question, we use s to infer collection relations, namely $collect(n, d)$ indicating that an entity $n$ may collect a data type $d$.
We obtain tuples of collection statements from prior state-of-the-art, namely PolicyLint <cit.>. We compare both results to manually labeled ground truth.

Since PolicyLint extracts tuples (see Figure <ref>(b)), we convert pairs of $collect(n, d)$ relations in s into PolicyLint tuples $\langle$n, collect, d$\rangle$. Still, we cannot compare data types and entities from the two tools directly because they normalize phrases in different ways. To work around the issue, we select a subset of terms to compare. For data types, we only consider the following precise data types in PolicyLint, since they are comparable to the same data types extracted by :
“mac address”, “router ssid”, “android id”, “gsf id”,
“sim serial number”, “serial number”, “imei”, “advertising identifier”,
“email address”, “phone number”, “person name”, and “geographical location”.[Note that we map “coarse geolocation”, “precise geolocation”, and “geolocation” in  all to “geographical location” in the tuple because PolicyLint does not distinguish between them.]
For entities, we only distinguish between the first party and third party,  all tuples are converted to either $\langle$we, collect, data type$\rangle$ or $\langle$third party, collect, data type$\rangle$; “unspecified third party” in  is considered a third party.

finds 13,529 tuples in the entire dataset. PolicyLint finds 6,410 tuples.
To evaluate the precision and recall of both tools, we manually extract the same tuples (collection relations) from our test set to establish the ground truth. To do this, we first use coarse regular expressions to match all possible mentions of the 12 data types in policies with a likely high chance of false positives. Then two of our authors read the text to determine if each data type is collected by the first party or any third party to create the tuples.

Precision  achieves 96.9% precision, and PolicyLint achieves 91.8% precision. As previously explained, NLP errors are the main reason of wrong collection relations.
We improve the precision by using recent NLP models.
The precision of  is higher than reported in Section <ref> because here we only consider a subset of data types and thus many falsely labeled data types are excluded. Also note that both tools show lower precision for third-party tuples (see Table <ref>) because some policies use company names rather than “we” to refer to the first party, and both tools can mistake the company names as third parties in this case.

Recall  achieves 70.6% recall, compared to PolicyLint's 30.4% recall.
As we will explain later in the ablation studies, the graph structure and improved NLP techniques both contribute to the higher recall. Despite the improvement, the recall of our tool is still limited, mainly by its linguistic analysis approach. First, some policies use lists or tables, which does not contain complete sentences for analysis. Second, our annotators cannot capture all forms of collection statements and can miss data types and entities in long or convoluted sentences.

Given the high precision and improved, but imperfect, recall, we recommend to interpret what  captures as a lower bound of the actual collection statements.
appendix:limitations discusses the factors that impact the performance of  in more detail.

Collection of Data Types

Third-party Entities of Data Collection

Purposes of Data Collection

Policy Summarization — Statistics of policies that disclose
(a) the collection of eight categories of data types;
(b) data collection by third-party entities (per data type category); and
(c) the purposes for the collection (per data type category).
For example, 3,348 policies claim to collect data types under the “software identifier” category;
794 policies disclose that data types in this category are collected by “advertiser” as the third-party entity.
And 1,847 policies disclose the collection of this category for the “services” purpose.

Manual validation and ablation studies results

§.§ Ablation Studies

RQ3.  consists of many components. Where does the performance improvement come from?

To answer this question, we conduct ablation studies to understand how each component and design decision contributes to 's performance improvements. We modify  into the following experimental configurations, and we summarize the evaluation results in Table <ref>.

Removing Components In the no-subsumption-annotator, no-coreference-annotator, no-list-annotator configurations, we disable one component at a time and assess the effect.

As shown in Table <ref>,
disabling the subsumption annotator reduces recall from 70.6% to 37.9%. The reason is that the precise data types that we evaluate are often subsumed by generic terms. They have to be linked by  edges to allow inferences of collection relations. Each of the coreference and list annotators contributes about 3% to recall.

Limiting Extraction Area In the per-sentence-extraction configuration, we modify  to behave like PolicyLint and extract tuples within sentence boundaries[The per-sentence-extraction is different from removing  edges because PolicyLint ideally is still able to find data types and entities that are subsumed by generic terms within the same sentence.].
This is done by filtering out $collect(n, d)$ relations in s where the entity and data type comes from different sentences.
Similarly, per-section-extraction only considers collection relations within the boundaries of sections[As explained in Section <ref>,  keeps headings from HTML, which is considered as the boundaries of sections here.].
These configurations help assess the improvement by introducing the graph structure to infer relations across sentences and sections.

Table <ref> shows the results. The per-sentence-extraction configuration has only 52.1% recall compared to 's 70.6%. On one hand, the sophisticated NLP methodology still improves performance over PolicyLint. On the other hand, the graph structure is necessary to infer 18.5% of all relations. The graph is more effective in identifying third-party data collection—it allows us to find 37.9% of third-party tuples, because the disclosure of third-party sharing often uses broader terms ( “Anonymous information may be shared with analytic providers”) and the exact data types (or entities) must be inferred through .
The per-section-extraction configuration, by connecting data types and entities within a longer textual region, achieves 63.3% recall but still falls behind the full version by missing 7.3% of relations. As explained in Section <ref>, the typical structure of policies that discuss data collection, use and sharing in separate sections makes it necessary to find exact data types and entities in different sections.
Therefore, we argue that  enables a much better coverage by connecting information disclosed in different sentences and sections to infer more collection relations in a policy.

§  APPLICATIONS

In this section, we present two novel applications enabled by . Section <ref> presents policies summarization, which provides inferences on the common patterns across different policies. Section <ref> looks into how the same or similar terms are defined across different policies.
In addition, we show that  can improve two applications that have been explored by prior work. Section <ref> extends  to identify contradicted statements. Section <ref> applies  to check the consistency between the data flows of a mobile app and its policy.

§.§ Policies Summarization

We use  to summarize all policies in our dataset and reveal common patterns among them. Specifically, we aim to identify: (1) how common each category of data types is collected;
(2) what kind of entities collect these data types;
and (3) the purposes for which these data types are used.
As data types and entities captured by s are unorganized and differ across policies (see Section <ref>), we use our global ontologies to categorize data types and entities in a canonical manner.

Data Types
In this analysis, we use the eight parent nodes of the leaf nodes in the data ontology shown in  Figure <ref> to group the data types into eight categories
[“Unspecified data”, “unspecified third party” and other data types and entities that are not part of the global ontologies (see Section <ref>) are excluded from the analysis of policies summarization.]:
“government identifier”,
“contact information”,
“software identifier”,
“hardware identifier”,
“protected classification”,
“biometric information”,
“geolocation”, and
“internet activity”.
Figure <ref> shows the numbers of policies that disclose the collection of data types in each category.
Overall, 77.9% (4,093) of policies disclose the collection of at least one of these data categories.

The most frequently collected data category is “software identifier”, which mostly originates from “cookie” as the specific data type being collected.
63.7% (3,346) of policies disclose the collection of “software identifier”.
Among the specific data types, “cookie / pixel tag” is the most common and found in 80.3% (2,688 / 3,346) of these policies. On the other hand, identifiers specific to mobile apps, mainly “advertising ID” and “Android ID”, are found in only 26.0% (870) and 2.8% (95) of these policies, respectively.
Many developers simply write one policy for various products, including mobile apps and web-based services. Furthermore, some developers seem to use “cookie” as a generic term for all kinds of device identifiers for tracking.

Third-Party Entities
We use the six parent nodes of the leaf nodes in the entity ontology shown in Figure <ref> to group entities into six categoriesftnote:unknown-terms:
“analytic provider”,
“social media”,
“content provider”,
“auth provider”, and
“email service provider”.
Figure <ref> reports how each data type category is disclosed to be shared with or collected by these third-party entities ( $\mathit{collect}(n, d)$ relations).

“Software identifier” is frequently shared with advertisers. Third-party sharing of other data categories ( “geolocation”, “protected classification”,
and “internet activity”) is also non-negligible.
We find that 23.8% (796 / 3,348) of policies that disclose to collect “software identifier” involve sharing with advertisers. Analytic providers and social media are other major third parties with whom apps share data.
620 policies share data in other categories ( “geolocation”, “internet activity”, and even “protected classification”) with third parties.
As data in these categories may be sensitive, it is doubtful whether the sharing of them is appropriate.

Many policies disclose data sharing using generic terms,  “personal information”. This leads to the inference that the app may share all data types that a generic term subsumes.
This often happens when policies disclose data collection, sharing, and use separately. For example, Figure <ref> shows that “personal information” is shared with entities such as “social networking services”. This may be alarming to users since “personal information” subsumes sensitive data types, such as “location” and “IP address”.
The use of generic terms reduces transparency. Users are left wondering which, if not all, “personal information” is shared.
We find that 710 policies declare third-party collection or sharing using generic terms that subsume data types in multiple categories.

Purposes Figure <ref> reports the statistics of policies that disclose purposes of data collection, as discussed in Section <ref>, per data type category.

56.9% (2,990) policies disclose that their apps collect data for non-core purposes. In over 80% of them (2,398), the main non-core purpose is advertising.
We find that, while “software identifier” remains the most common data type category used for non-core purposes, the potential use of other data types for non-core purposes is concerning. For instance, the collection of “geolocation”, “protected classification”, and “internet activity” for non-core purposes is declared in about 10% of policies.
The CCPA <cit.> defines “government identifiers”, “precise geolocation”, and certain protected classifications as sensitive personal information—the law limits the usage of these data ( users have the right to limit the use of such personal information for non-core purposes).

§.§ Correct Definitions of Terms

The second novel application enabled by  is assessing the correctness of definitions of terms. Besides summarizing policies on their own right,
we can check whether a policy defines terms in ways that are consistent with external knowledge as captured by global ontologies.
This is necessary because policies often provide their own definitions of terms. This is not a problem if the definitions align with external knowledge ( privacy laws), but it may be misleading if they do not agree. For example, some policies define “geolocation” as “non-personal information”.
In this section, we check whether the definitions of data type terms in individual policies (as captured by their s' local ontologies) align with our CCPA-based global data ontology (see Figure <ref>).

Overall, such different definitions are found in 25.5% (1,339 / 5,255) policies in our dataset, as listed in Table <ref>.

Examples of different definitions found in s with respect to the global data ontology. For example, “geolocation” is defined as “non-personal information” in 123 policies.

Many policies define data types that they collect to  be “non-personal”, “aggregated”, “deidentified”, or “pseudonymized”. However, this can be inconsistent with the definitions in the CCPA.
Indeed, in the CCPA, “deidentified information” is defined as information that “cannot reasonably identify, relate to, describe ...
to a particular consumer”.
Although entities technically can deidentify personal information, some of the data types we observe in Table <ref>, notably “geolocation”, “gender”, “age”, and “date of birth”, are generally considered personal information by the public and according to the CCPA.
Declaring these data types as non-personal or deidentified can be misleading.
For example, Paleblue declares in its policy <cit.> that “Paleblue may also invite you to share non-personal information about yourself which may include... (1) your age or date of birth; (2) your gender...”.

Many policies use non-standard terms. They can have broad or varied definitions across different policies.
For example, it is not surprising that the definition of “profile information” is application-specific. One policy from the Manager Readme app <cit.>
defines “profile information” to include “name” and “location”, while another policy from Armor Game Inc. <cit.>
defines the term to include “gender” and “birthday”. In these cases, the use of non-standard terms is acceptable as the policies clearly explain what they mean by the terms. However, we also find many policies that do not clearly define their non-standard terms. Particularly, while “profile information” is found in 178 policies, subsumption relationships are found in only 17 of them in their corresponding s.
Table <ref> presents examples of non-standard terms and their possible definitions found in the policies.

Examples of non-standard terms found in policies. For example, “technical information” is used in 311 policies but its detailed definition is only found in 126 policies.

§.§ Contradiction Analysis

In this section, we apply  to analyze contradictions within a policy.
To that end, we extend  to also analyze negative collection statements (“We do not collect personal data”) ignored in previous sections (which only analyzed affirmative statements). We also propose extensions to the main  framework so as to capture additional contexts that are crucial to interpret contradictions.

Prior work, namely PolicyLint <cit.>, identifies contradictions by detecting affirmative and negative sentences that mention the same or conflicting entities and data types.
By manually checking all the 86 contradictions identified by PolicyLint in our test set, we found 79 of them turn out to be false alarms.
This is because the analysis ignores many contexts surrounding the “contradicted” statements, as explained below.

* Different Purposes:
PolicyLint considers “we collect PII to provide the service” and “we do not collect PII for advertising purposes” as contradicting statements, despite them discussing data collection for different purposes,   services  advertising.

* Different Data Subjects:
PolicyLint considers “we collect PII” and “we do not collect PII from minors” as contradicting. A human reader would recognize that the sentences  discuss different data subjects,  general user  child.
[Beyond semantics, another source of error for PolicyLint was its implementation. In order to find and skip text about children policy, which was considered outside the framework, it performed string matching using hardcoded regular expressions, which often failed due to sentence variability.]

* Different Actions:
PolicyLint considers “... share PII with third parties” and “... do not sell PII to any third party” as contradictions. A human reader would recognize that they refer to different actions,   share  sell.

* Contradictions According to Global Ontologies:
In addition, some policies do not literally contradict themselves, but the data types and entities in the affirmative and negative statements overlap according to PolicyLint's ontologies.
For example, in the policy of Horizone Media <cit.>, PolicyLint reports “we use anonymous identifiers” and “we do not collect personal information” as a contradiction. The policy does not define “anonymous identifiers” as “personal information”, but PolicyLint views all “identifiers” as “personal information” in its data ontology. In this case, the policy can be considered as misleading but does not directly contradict itself. Note that we already discuss misleading definitions in Section <ref>.

§.§.§ Framework Extensions

The main  framework, described in Section <ref>, introduced data types, entities and purposes.

However, it only deals with affirmative, not negative, statements. In this section, we extend  to also analyze negative statements, and we show how to deal with contradicted statements in fine-grained contexts.
To that end, we add a new type of negative edge (), actions as edge subtypes, and the notion of data subject, as described next.
[The extensions are presented in this section, as opposed to as part of the main framework, for several reasons. First, they are specific to contradiction analysis, and motivated by the limitations of prior work in taking into account fine-grained contexts in that analysis.
Second, as shown in Section <ref>, although effective in refining contexts for contradiction analysis, these extensions do not address all aspects of fine-grained contexts:  one can define additional types of actions, data subjects, and other contexts.
Third, these extensions do not affect the validity of previous results in Sections <ref> and <ref>, which were based only on affirmative, and ignored negative, statements.]

Negative Collection Statements

The collection annotator (see Section <ref>) identifies negative sentences and by default excludes them. In this section, we modify the annotator to also account for negative collection statements and represent them as  edges.

For example, “we do not collect personal information” will be represented with edge weNOT_COLLECTpersonal information in . Similarly to its positive counterpart, a  edge can have $Purposes(\cdot)$ attributes.

Refining Actions
We further consider five subtypes of   (and ) edges that represent different data actions: $\{$collect, be_shared, be_sold, use, store$\}$.
We denote an action-sensitive  edge as $n$COLLECT $[a_{pos}]$$d$, and an action-sensitive  edge as $n$NOT_COLLECT $[a_{neg}]$$d$, where $a_{pos}$ and $a_{neg}$ are one of the 5 subtypes of data actions.

We extend the collection annotator to map verbs to these subtypes accordingly.
For example, “... do not sell personal information to advertisers” is represented as edge advertisersNOT_COLLECT $[be\_sold]$personal information in .
Table <ref> in appendix:contradiction-framework-extension provides the list of verbs and corresponding actions, which can be extended if so desired.

Data Subjects
We extend data type nodes to include subjects,  the group of people to which the data type pertains, following the terminology of Contextual Integrity <cit.>. We denote a subject-sensitive data type node as a pair $(d, s)$, where $d$ is the data type, and $s$ is the subject of the collected data.

We add a new subject annotator in  to identify subjects of data types. Currently, we implement it to identify a commonly-seen data subject: children. In the current implementation, we define subject $s \in \{\textit{child, general user}\}$, and we represent the statement “we don't collect personal information from children” as  weNOT_COLLECT $[collect]$(personal information, child) in . We note, however, that the modular implementation of  allows for the set of subjects to be extended to include additional subjects.

§.§.§ Contradiction Analysis

To identify potential contradictions, we assess whether a positive edge and a negative edge in a  involve conflicting
data types, subjects, entities, actions, and purposes.
A pair of edges may contradict if all these parameters conflict; otherwise, the two statements address different aspects of data collection, as outlined earlier, thus do not contradict.

Conflicting Edges.
A positive edge $e_{pos} = n_{pos}$COLLECT $[a_{pos}]$$(d_{pos}, s_{pos})$ and a negative edge $e_{neg} = n_{neg}$ NOT_COLLECT $[a_{neg}]$ $(d_{neg}, s_{neg})$ in a  are conflicting if all the following parameters conflicts:

* Data types $d_{pos}$ and $d_{neg}$ conflict iff $d_{pos} = d_{neg}$ or $\exists d': subsume(d_{pos}, d') \land subsume(d_{neg}, d')$.

* Entities $n_{pos}$ and $n_{neg}$ conflict iff $n_{pos} = n_{neg}$ or $\exists n': subsume(n_{pos}, n') \land subsume(n_{neg}, n')$.

* Purposes $P_{pos}=Purposes(e_{pos})$ and $P_{neg}=Purposes(e_{neg})$ conflict iff (1) $P_{pos} \cap P_{neg} \neq \varnothing$, or (2) $P_{neg} = \varnothing$.

* Data subjects $s_{pos}$ and $s_{neg}$ conflict iff $s_{pos} = s_{neg}$.

* Actions $a_{pos}$ and $a_{neg}$ conflict iff $a_{pos} = a_{neg}$.

§.§.§ Results on Contradiction Analysis

Reducing False Alarms  with the above extensions encodes  additional parameters, which allows us to reclassify many of the statements erroneously classified as candidate contradictions in PolicyLint, due to missing context, as non-contradictions. To evaluate the benefit, (1) we map contradicting tuples reported by PolicyLint to  edges and (2) we check whether each pair of edges are conflicting as defined above.
maps 2,555 PolicyLint contradictions to 1,566 pairs of edges in our dataset. Out of them, only 13.5% (211) pairs are conflicting, taking contexts into account as per Definition <ref>. The remaining 86.5% are not conflicting, due to one or more of the reasons shown in Table <ref>.
Please see appendix:contradiction-methodology for details.

We manually verified all the 83 contradictions reported by PolicyLint in our test set.  reported 68 pairs as non-conflicting and we agree with all of them. For the other 15 pairs of conflicting edges, 7 pairs of edges are considered contradictions by human readers.

Despite the additional contexts captured by our extended framework compared to PolicyLint,  still has false alarms.
We manually verify all 211 pairs of conflicting edges identified by , and find that only 25.1% (53) pairs are real contradictions. The most common reason (54.0%, 114 pairs) why conflicting edges may not be real contradictions is additional language nuances,  not yet represented in .
For example, the sentence “we do not collect personal data when you visit the site” does not contradict with “we collect personal data when you sign up” due to the different conditions addressed. Other contexts we identify during manual validation include data sources and consent types. Please see appendix:contradiction-validation for details.

Reclassification of PolicyLint contradictions

Conclusion Our extensions of  to analyze contradictions, by taking account of more contexts, prevent many false alarms in prior work and narrow down possible contradictions to a smaller set.  However, one should be aware that even the extended framework does not cover all possible  contexts and nuances in human language.

§.§ Data Flow-to-Policy Consistency Analysis

In this section, we compare the statements made in a policy (extracted using ) to  the actual data collection practices (as observed in the network traffic generated). This application has been previously explored by PoliCheck for mobile apps <cit.>  and its adaptations to other app ecosystems,  smart speakers <cit.> and VR devices <cit.>.

§.§.§ Data Flow-to-Policy Consistency

As in prior work <cit.>, we represent data collection practices observed in the network traffic as data flows. A data flow is a tuple $f = (n, d)$ where $d$ is the data type that is sent to an entity $n$.
Given a , we check whether the data flow is clearly disclosed in it as below.

Clear Disclosure.

Following Definition <ref>, $G = \langle D, N; E_{S}, E_{C}; P \rangle$ is a .
A data flow $f = (n, d)$ is clearly disclosed in the policy represented by $G$ iff it contains the entity ($n \in N$) and the data type ($d \in D$), and $collect(n, d)$ is true in $G$.

Recall that PoliCheck also accepts broader terms of data types and entities as consistent but vague disclosure, if the broader terms subsume the specific data types in the data flows according to the global ontologies. We define vague disclosures of a data flow in a similar way as follows.

Vague Disclosure.

Following Definitions <ref> and <ref>,
$G = \langle D, N; E_{S}, E_{C}; P \rangle$ is a ,
$O_d=\langle D_{d}, E_{d} \rangle$ is the global data ontology, and $O_n=\langle N_{n},E_{n} \rangle$ is the global entity ontology.
A data flow $f = (n, d)$ is vaguely disclosed in $G$ according to global ontologies $O_d$ and $O_n$,
iff $f$ is not clearly disclosed in $G$, and
there exist a data type $d' \in D \cap D_d$ and an entity $n' \in N \cap N_n$ that satisfy: $collect(n', d')$ is true in $G$; $subsume(d', d)$ is true in $O_d$; and $subsume(n', n)$ is true in $O_n$.

Our definitions of clear and vague disclosures correspond to the same concepts in PoliCheck.
Both clear and vague disclosures are considered consistent disclosures. Otherwise, the data flow has inconsistent disclosure in the policy.

§.§.§ Data Flow-to-Policy Consistency Results

To facilitate a comparison to PoliCheck,
we use the same dataset from it <cit.>. In addition to policy URLs for apps, this dataset also contains data flows extracted from the apps' network traffic.
Different from the policy dataset in Section <ref>, we use the versions of policies from 2019 for a fair comparison with PoliCheck results, because the data flows were collected around February 2019.
We crawl the historical versions of policies from Internet Archive <cit.>.
In total, we have 8,757 apps with both data flows and policies available.

Flow-to-policy consistency comparison of   PoliCheck.
The numbers in parentheses represent the number of apps that collect the data type. For example, 85 apps have data flows that collect “phone number”.

Figure <ref> compares flow-to-policy consistency results per data type in    PoliCheck.
An app may send one data type to multiple entities, resulting in multiple data flows per data type. In this case, we report the worst disclosure type for the app,  if, at least, one of the data flows of the data type is inconsistent, the disclosure type is reported as inconsistent.
We present the results for nine data types—three out of 12 data types are analyzed in <cit.>, but excluded here as only less than 10 apps exhibit the three in their data flows.

Clear  disclosures
We find that  outperforms  PoliCheck in terms of capturing more clear disclosures. PoliCheck underestimates the number of clear disclosures for all data types due to its limited recall (see Section <ref>).
Clear disclosure of contact information is especially underestimated.
72 of 85 apps that collect “phone number”, and 47 of 79 apps that collect “email address” clearly disclose the collection.

Vague disclosures
Here,  extracts fewer vague disclosures than PoliCheck. Further investigation reveals that this is because our global data ontology has a different design compared to PoliCheck's. In PoliCheck's data ontology, “personal information”, a commonly seen term in policies, subsumes “device identifiers”. While this would effectively increase PoliCheck's coverage, namely that the collection of all data types related to “device identifiers” found in the data flows would be categorized as vague disclosures, it is unclear whether “device identifiers” can be strictly categorized as “personal information”.
Many policies do not consider “device identifiers” as “personal information”.

also enables the analysis of purposes of data collection associated with data flows.
Please refer to appendix:flow-to-policy-consistency-analysis for additional results.

§ RELATED WORK

Formalizing Policies A body of related work focuses on standardizing or formalizing policies. W3C P3P standard <cit.> proposed an XML schema to describe policies. The Contextual Integrity (CI) <cit.> framework expresses policies as information flows with parameters including the senders, recipients and subjects of information, data types, and transmission principles that describe the contexts of data collection. None of them replaces text-format policies, but they give insights into defining policies and serve as analysis frameworks.  builds on the CI framework by extracting entities, data types, and part of the transmission principle ( purposes) from the policy text.

Policy Analysis Another body of work analyzes policy text. OPP-115 <cit.> is a policy dataset with manual annotations for fine-grained data practices labeled by experts. Shvartzshnaider  <cit.>, with the help of crowdsourced workers, analyze CI information flows extracted from policies to identify writing issues, such as incomplete context and vagueness. This manual approach is difficult to scale up for hundreds or thousands of policies due to the significant human efforts.

Automated Policy Analysis The progress in NLP has made it possible to automate the analysis of unstructured text, such as policy text.
Privee <cit.> uses binary text classifiers to answer whether a policy specifies certain privacy practices, such as data collection, encryption and ad tracking.
Polisis <cit.>, trained on the OPP-115 dataset, uses 10 multi-label text classifiers to identify data practices, such as the category of data types being discussed and purposes. Classifier-based methods use pre-defined labels which cannot capture the finer-grained semantics in the text.
PolicyLint <cit.> first uses NLP linguistic analysis to extract data types and entities in collection statements. PurPliance <cit.>, built on top of PolicyLint, further extracts purposes. Conceptually, both works focus on analyzing one sentence at a time, and extracting a tuple $\langle$entity, collect, data type$\rangle$, as well as purpose in PurPliance, albeit in a separate, nested tuple $\langle$data type, for / not_for, $\langle$entity, purpose$\rangle\rangle$. Unlike , these  works view extracted tuples individually and do not infer data practices disclosed across multiple sentences.

Knowledge Graphs Graphs are routinely used to integrate knowledge bases as relationships between terms <cit.>. Google has used a knowledge graph built from crawled data to show suggestions in search results <cit.>. OpenIE <cit.> and T2KG <cit.> use NLP to build knowledge graphs from a large corpus of unstructured text. In , we use knowledge graphs, for the first time, to represent policies.

§ CONCLUSION

We present , a framework that represents a privacy policy as a knowledge graph that
(1) connects statements about data collection, use and sharing across different parts of the policy text, and
(2) clearly defines and distinguishes between local and global ontologies.
We design and implement —a tool that leverages NLP linguistic analysis to generate s from policy text.
Because  allows inferences of collection relations across paragraphs and sections, it significantly improves recall over prior work, while maintaining a high precision (see Section <ref>).
Our manual validation shows that  improves the recall of collection statements from 30% to 70% in comparison to PolicyLint <cit.>. Meanwhile, the precision is improved from 92% to 97%.
, and the global ontologies used with it, also enable new policy analyses that were not previously possible: summarizing patterns in a corpus of policies (see Section <ref>) and assessing the correctness of definitions of terms (see Section <ref>).
Our modular design also allows for extensions to the framework so as to analyze contradicting statements in more fine-grained contexts than prior work (see Section <ref>).

The source code of  and the dataset used in this paper are made publicly available <cit.>.

The proposed approach has its limitations.
First, wrong edges in  may propagate to wrong inferences (see Section <ref>).
Second, despite our improvement in covering more sentence patterns than prior work (see Section <ref>),  still faces the limitations of NLP. For example, it cannot parse tables and some lists, and misses a non-negligible number of collection statements. It is difficult to cover all possible syntactic patterns.

In the contradiction analysis (see Section <ref>),
although we extend  to encode additional context in policies (such as fine-grained action types and children as data subjects), we show that there are still false alarms due to the inevitability of handling all possible language nuances ( other types of data subjects, conditions, sources).
Additional discussion can be found in appendix:limitations.

Finally, as discussed in Section <ref>, given the high precision and improved, but imperfect, recall, we recommend to interpret what  captures as a lower bound of the actual collection statements.
The aforementioned limitations may unevenly affect different writing styles of policies ( text  tables), different sentence structures ( missing syntactic patterns), and even different applications.
Therefore, the results of NLP analysis,
especially results on each individual policy, should be validated by human experts.

Future Directions
Recent advancements in generative large language models (LLMs), represented by ChatGPT <cit.>, have greatly enhanced the capacity of NLP to understand complex text, easing the necessity for combining many NLP components and heuristics.
However, the natural language interface of generative models can be a challenge for automated analysis.
We expect that knowledge graphs will remain powerful tools to integrate model answers for automated analysis at scale.
We will explore the potential of LLMs in policy analysis, to extend the  framework so as to better incorporate additional elements in policy text, such as conditions of data collection and consent requirements.

§ ACKNOWLEDGMENTS

This work is supported by NSF award 1956393 and a gift from the Noyce Initiative.  We would like to thank our shepherd and reviewers from USENIX Security 2023 for their feedback, which helped to significantly improve the paper.

§  IMPLEMENTATION IN DETAIL

In Section <ref>, we present , the NLP-based system that we implement to generate . We provide additional details on its implementation in this appendix.

§.§ HTML Preprocessing

In Section <ref>, we explain that  converts each policy into a simplified document tree structure for subsequent NLP tasks.
We provide more details in this appendix.

Document Tree Given a policy in the HTML format,  starts by converting it into a document tree, a simplified HTML DOM tree. Each node in the document tree corresponds to a fragment of text, referred to as a segment.
uses three kinds of segments: (1) A heading segment corresponding to an HTML heading, whose parent, if exists, is the higher level heading segment; (2) A list-item segment corresponding to an item in an HTML list, whose parent is the text or heading segment immediately before the list;  (3) A text segment corresponding to a general HTML text container that is neither a heading nor a list item, whose parent is the heading closest to it.

A hypothetical document tree, modified from the policy example in Figure <ref>(a), looks like this:

Document Tree

Data Collection

We collect the following personal information:

- Device information, such as IP address...

- Location

We disclose the personal information as follows...

Technically,  first uses the Readability.js library <cit.> to extract the main content of a webpage ( without sidebar, footer, and other unrelated widgets). Then it parses the HTML markups to generate the document tree. In some cases, webpages use plain text lists ( prefixing each paragraph with numbers) instead of HTML lists.  has heuristics to identify such lists and convert them into list segments.

Text Concatenation NLP pipeline expects text input. And in order for it to produce correct results, we need to input complete sentences. Some segments, like the two list items in Example <ref>, are not self-contained to form full sentences. Each of them has to be concatenated after its parent text segment to form a complete sentence,  “We collect the following personal information: Name”. To do this,  uses the document tree to find the context of each segment.

In reality, nested headings and lists are common, and many policies are not written in a way that sentence boundaries can be easily identified,  it is hard to determine at which level a complete sentence starts without another NLP model. To work around the issue,  iteratively concatenates each segment with its parents up to different levels to get multiple versions of input text. For each  in Example <ref>,  generates three versions of the text for NLP:
(1) ;
(2) ; and
(3) .
NLP pipeline gets valid input as long as any of these versions aligns with sentence boundaries.

NLP Pipeline  uses spaCy library <cit.> and its en_core_web_trf NLP pipeline, which is a set of NLP models built upon the RoBERTa architecture <cit.>, to annotate common linguistic features. These linguistic features, including word lemmas, part-of-speech, sentence segmentation, and syntactic dependencies, are syntactic and, thus, they require no domain adaption. The RoBERTa-based pipeline achieves state-of-the-art performance on these tasks <cit.>. We only train our own NER model for identifying data types and entities (see Appendix <ref>).
relies on these linguistic features to build s. Although spaCy's NLP pipeline processes plain text and does not keep the document tree structure,  internally records which segment each word comes from. This way,  can revert to the document tree whenever needed. For example, the list annotator (see Section <ref>) takes advantage of the document tree to discover additional relations.

§.§ NER Model Training

Root words used for rule-based NER

In Section <ref>, we explain that  uses named entity recognition (NER) to identify data types (labeled as DATA) and entities (labeled as ENTITY) in the policy text. In this appendix, we provide details on our NER methodology.

Synthetic NER Corpus Training a new NER model requires a labeled corpus. To avoid the burden of building a dataset from scratch, we programmatically generate a synthetic corpus for NER training. The synthetic corpus is generated from the following two sources.

First, we manually write 30 sentence templates. The sentence templates looks like this: We , where  and  are placeholders for data types and entity names. The regular-expression-like format is reversely expanded to matching strings using exrex <cit.> library. We manually write 90 phrase templates for data types using the same regular-expression-like format, for example: (real|first|middle|last|...)? names?. For entity names, we obtain a list of about 12K entity names by crawling Wikidata <cit.> items that are related to companies or products. This includes both proper names ( company and organization names) and generic category names ( “email hosting services”). By using random combinations of sentence templates, data type phrases and entity names, and by expanding the regular expressions, we create a large variety of sentences. For example, a possible sentence created from previous examples is “We may share your last name with email hosting services.”
As the sentences are created programmatically, the positions of data types and entity names are already known.
We generate 50,000 synthetic sentences as the training set.

Second, we apply knowledge distillation <cit.> to transfer knowledge from spaCy's pretrained NER model and our manually defined rule-based NER. Specifically, spaCy's NER model <cit.> is capable to identify company, person and product names, which we map to the ENTITY labels. We additionally define rules to label phrases with root words like “information”, “data” and “identifier” with  DATA labels. Table <ref> shows the list of root words used in the rule-based NER. We apply both NER methods to label 200 real-world policies (which is different than our test set in Section <ref>), and include the data in the training set. As this method cannot capture all the entities and data types (otherwise we would simply use it), we mark noun phrases without labels as missing annotations. spaCy's trainer will not penalize nor reward the model for labeling these phrases.

NER Model
We fine-tune the distilroberta-base model <cit.> with the synthetic corpus as the NER model.

To evaluate the model, we randomly selected 200 segments of text, which contain about 620 sentences in total, from our test set of policies (see Section <ref>), and manually label data types and entities in them to establish the ground truth.
On the evaluation corpus, the model achieves 96.1% precision and 89.4% recall.

The performance is as good as general-purpose NER models, which have approximately 90% precision and recall <cit.>.

§.§ Phrase Normalization

In Section <ref>, we explain that  performs phrase normalization using a few strategies. We provide more details on these strategies in this appendix.

To merge phrases with the same meaning ( synonyms and coreferences) into one node in ,  maps phrases of data types and entities to their normalized forms.
This process, known as phrase normalization <cit.>, is necessary for automated analysis, because it allows us to deal with consistent normalized forms instead of many synonymous terms,  “contact information” is the normalized form for “contact details” and “contact info”.  uses a combination of NLP and manual rules for phrase normalization.
It applies the following strategies to normalize data types and entities.

Standard Terms We consider data types and entities in our global ontologies (see Section <ref>) as standard terms. To facilitate analysis of these data types and entities in Sections <ref> and <ref>, we write regular expressions to capture variants of synonyms for them.
For example, the regular expression contact.̱*(̱information|data|detail|method) maps “contact data”, “contact detail”, “contact method”, and other synonyms into “contact information”, which is the normalized form in the global data ontology.

To normalize company names, we build regular expressions from public datasets. We use the DuckDuckGo Tracker Radar dataset <cit.> and a CrunchBase-based public dataset <cit.> to obtain variants of company names,  “Alphabet Inc.” (group company) and “Firebase” (product) as alternative names for “Google” (the normalized term). We extract n-grams that are uniquely found in each company's list of alternative names to build regular expressions for the company. For example, two-grams “alphabet inc” and “google inc”, and one-grams “firebase” and “google” are all normalized to “Google”.

Unspecified Data and Unspecified Third Party

As a special case of standard terms, we use two special terms “unspecified data”  and “unspecified third party” for data types and entities that have too general meanings.
For data types, if a phrase, after removing stop words, is lemmatized to a single word “data”, “information” or “detail”, it is normalized to “unspecified data”.
For entities, if a phrase, after removing stop words, is lemmatized to “third party” or similar phrases, it is normalized to “unspecified third party”.

Other Terms

At last, if a data type or entity cannot be normalized by abovementioned strategies,  falls back to strip stop words and take the lemmatized form of the phrase. For example, “your vehicle records” is normalized to “vehicle record”. In most cases, this should be enough to capture variants of the same term caused by word inflections.

As the coreference annotator has linked each coreference phrase to what it refers to,
does not apply normalization to phrases with  edges. Instead, it follows the  edges to find the referent and use the same normalized form. For example, in Figure <ref>(a), “this information” would be normalized to “geolocation”, same as the phrase “location” that it refers to.

§.§  Example

Figure <ref> in Section <ref> shows the simplified version of the  generated from a simple policy <cit.>. We show the complete version in Figure <ref> in this appendix.
It shows all nodes and edges extracted by  as is. Besides more data types, it includes an irrelevant term “mobile device” which is wrongly labeled as a data type by the NER model. We discuss the kind of error in Section <ref>.

The complete  generated from “Puzzle 100 Doors” app's policy <cit.>.

§ CONTRADICTION ANALYSIS IN DETAIL

In Section <ref>, we presented our methodology of contradiction analysis, and we reported our main findings. In this section, we revisit and provide additional details.

§.§ Framework Extension

In Section <ref>, we present extensions to   for contradiction analysis.
One of the extensions was to include five types of finer-grained actions as subtypes of  and  edges. Table <ref> lists all the verbs and corresponding actions. We note that the modular design of  allows for this list to be easily extended, if so desired.

0.95Mapping from verbs to subtypes ( actions) of  /  edges as an extension to .

§.§ Methodology

In Section <ref>, we explain how  determines conflicts between  and  edges.
In contrast, PolicyLint reports contradictions between positive tuples
$\langle$entity, collect, data type$\rangle$
and negative tuples
$\langle$entity, not_collect, data type$\rangle$.
While, conceptually, one tuple should correspond to one  or  edge, in practice, it is not always possible to find a one-to-one mapping between PolicyLint tuples and  edges.

First, as PolicyLint and  implement text preprocessing and phrase normalization in different ways, it is not always possible to match data types, entities or even sentences from both tools. We craft rules to map terms from both tools on a best-effort basis. For example, “geographical location” in PolicyLint can match with “geolocation”, “precise geolocation”, and “coarse geolocation” in s.

Second, one tuple reported by PolicyLint may come from multiple sentences. As our tool normalizes phrases differently and, more importantly, is extended to capture more parameters, two sentences with the same PolicyLint tuple may result in different edges in .
In this case, for each pair of contradicting tuples in PolicyLint,  checks all combinations of  and  edges that match the contradicting tuples, and reports only one pair of edges that have the most conflicting parameters.

On our dataset, PolicyLint reports 2,555 contradictions (excluding “narrow definitions” as defined in <cit.>) in total, and 1,566 of them are successfully mapped to  edges. In Table <ref> in Section <ref>, we report statistics based on  edges instead of tuples for clarity.

§.§ Manual Validation of Conflicting Edges

In Section <ref>, we briefly discuss the validation of conflicting edges.
We report that, among all the 211 pairs of conflicting edges in our dataset, human readers determines that only 25.1% (53) pairs are real contradictions.
Apart from 24 pairs that are determined to be NLP errors, we explain the reasons why the remaining conflicting edges are not real contradictions as below.

Additional Contexts 114 out of 211 pairs of conflicting edges turn out not to be real contradictions because they mention additional contexts that cannot be represented in , namely:

* Conditions of data collection. For example, the sentence “we do not collect personal data when you visit our website” does not contradict with “we collect personal data when you submit a request” due to the different conditions discussed.

* Consent type of the data collection. For example, many policies declare that “we do not collect information without your consent”.

* Sources from which the data are collected. For example, the sentence “we do not collect personal data from third parties” does not contradict with “we collect personal data you provided”. In this case, the sources of data “third parties” and “you” (the user) are different.

We note that this is not a fundamental limitation of the  framework, since these additional parameters can be incorporated into  by introducing new edge, or node types and attributes.

Finer Semantics 20 out of 211 pairs of conflicting edges are not contradictions because the negative and positive sentences discuss subtly different data types, entities, or purposes where the semantic differences are beyond the granularity of 's phrase normalization. For example, one policy mentions “we share your personal information with internal third parties” but “not with unaffiliated third parties”. In this case, both phrases of entities are normalized to “unspecified third party”.
Also note that the new subject annotator is currently able to only identify children as data subjects, while in practice there can be other subjects ( “driver” and “rider” in Uber's policy <cit.>) not handled by the current implementation.

Note that this is not a limitation of the  framework, but of the implementation.
We believe that a more sophisticated approach, likely a model-based approach, to infer the meaning of a phrase, rather than normalizing phrases according to static rules (see Section <ref>), is needed to work around such limitations.

§ ADDITIONAL RESULTS FROM DATA FLOW-TO-POLICY CONSISTENCY ANALYSIS

In Section <ref>, we introduce our methodology of data flow-to-policy consistency analysis and present the main findings. Due to a lack of space, we defer additional results about purposes of data collection to this appendix.

Purposes of data flows inferred from s. Some apps disclose the collection of the data types for core or non-core functionality, or both. We ignore apps whose policies do not disclose purposes, so the total number of apps (listed in parentheses) is less than the number of apps in Figure <ref>.

Purposes of Data Flows Besides data types and entities,  also captures the purposes of data collection, use and sharing. This enables us to enrich the flow-to-policy consistency analysis by identifying the purposes associated with data flows according to policies.

Inferring the purposes from the network traffic would be limited to few purposes <cit.>[For example, while advertising as a purpose can be inferred based on a network packet's destination entity, it would not be straightforward to infer legal as a purpose.], and do not often align well with the definitions given in the policies <cit.>.
Thus, instead of directly checking the consistency between the purposes disclosed in the policies and the data flows in the network traffic as in PurPliance <cit.>, we adopt the methodology used in OVRseen <cit.> that infers the purposes of each data flow based on corresponding collection statements in policies that disclose purposes. This is captured in the corresponding  as a  edge assigned with a list of attributes that contain purposes (see Section <ref>).

To be specific, following Definitions <ref> and <ref> in Section <ref>, we extract the set of purposes $\mathit{purposes}(n, d)$ (see Definition <ref> in Section <ref>) for each clear disclosure, or $\mathit{purposes}(n', d')$ for each vague disclosure, as the inferred purposes of the corresponding data flow $(n, d)$.

We are able to extract purposes for clearly and vaguely disclosed data flows of 1,023 apps based on s of their policies.
We label the data flows with the five categories of purposes, and further group them into core and non-core purposes as discussed in Section <ref>. Services, security, and legal are grouped as core purposes; whereas analytics and advertising are grouped as non-core purposes.
Figure <ref> shows the purposes associated with these data flows.
In total, 707 apps declare that their data flows are for core purposes, whereas 692 apps declare that their data flows are for non-core purposes.
While the collection of “advertising id” (and other similar identifiers) for non-core purposes ( advertising and analytics) can be acceptable, Figure <ref> also shows that many apps collect sensitive data types,  “phone number”, “email address”, and “geolocation” for non-core purposes, which is alarming and aligns with Finding <ref> in Section <ref>.
Note that many policies declare data flows for both core and non-core purposes. This is usually due to vague disclosures and multiple purposes associated with generic terms, which reduces transparency. A similar issue about data sharing disclosed in generic terms is discussed in Finding <ref> in Section <ref>.

§ SCOPE AND LIMITATIONS OF

In Section <ref>, we show that collection statements inferred from  improve the recall from 30% to 70% in comparison to tuples in PolicyLint <cit.>.
At the same time,  achieves 97% precision, compared to 92% of PolicyLint.
In this appendix, we elaborate  upon the discussion of limitations from Section <ref>.
We also discuss how these limitations affect the applications presented in Section <ref>.

Factors Affecting Precision
We discuss major factors that affect the precision of  in analyzing collection statements as follows.

First, although  uses state-of-the-art linguistic analysis models (see Appendix <ref>), NLP errors are still non-negligible.

In general, NLP models have difficulties in parsing long and complicated sentences, which are common in policies.
As discussed in Section <ref>, the NER model can classify
irrelevant phrases as data types or entities, resulting in meaningless  or  edges like weCOLLECTthird-party code.
Furthermore, interrogative or negative sentences are occasionally mistaken as affirmative ones, which result in wrong edges.

Second, due to the graph structure of , false-positive edges can propagate to more incorrect inferences of subsumption and collection relations as discussed in Section <ref>.
Most of our analysis in Sections <ref> and <ref> focuses on a limited set of well-known data types and/or entities, so irrelevant terms are naturally excluded.

Given the relatively high precision of  (96.9%, see Section <ref>), the issue of misinterpreting some policies should not significantly impact the validity of overall trends discussed in Section <ref>.

Factors Affecting Recall
Despite our major improvement in recall over prior work,  still misses about 30% of collection relations in our ground truth data, as discussed in Section <ref>. Next, we describe factors that limit the recall of  in analyzing collection statements.

First,  relies on linguistic analysis, namely analyzing syntactic features of sentences, to extract relations. As a result, a list
such as “Information we collect: • Name; • Gender”,  which contains no complete sentence, cannot be processed.  cannot handle tables either, despite the increasing use of tables in policies for readability.
This limits the recall of our tool in discovering relations.

Second, 's annotators rely on manually written rules of syntactic patterns to extract data types, entities and purposes in the text. The flexibility of human language makes it difficult to cover all possible patterns.
For example, the collection annotator does not recognize the sentence
“Among the types of Personal Data that we collect..., there are: Cookies...”<cit.>, because there is no rule to cover the odd statement. While it is possible to write a new rule for it, we decided to only include common and intuitive patterns (see Section <ref>) in our implementation, for simplicity.

Other Limitations Additional limitations that affect the validity of our policy analysis are listed as below.

Similar to the annotators, 's phrase normalization relies on manually crafted regular expressions to capture synonyms. This is effective for data types with a few widely accepted names, which are often specific, such as “email address” and “android id”. For some generic data types, it can be difficult to handle a wide variety of English expressions. Sometimes it is even unclear to human whether a phrase should be considered as a known term,  whether “non-personal information about your use of our Apps”<cit.> is a synonym to “internet activity” or “usage data”. In this particular case,  normalizes it to “non-personal information” which we believe is not wrong but inaccurate. Note that in this case the resulting  still captures the data type but assigns an inaccurate term. Consequently, the analysis in Sections <ref> and <ref> may risk unevenly underestimating or overestimating statements regarding some categories of data types and entities.

In the contradiction analysis (see Section <ref>), we also show that the design of  in Section <ref> has to be extended to encode more parameters to allow better assessment of conflicting statements. Finally, in spite of the extensions, there are still false alarms due to the inability to capture other language nuances,  conditions, sources, consent types,  (see Appendix <ref>), in our framework and NLP.