Nina Taft
Nina Taft is a Senior Staff Research Scientist at Google where she leads the Applied Privacy Research group. Prior to joining Google, Nina worked at Technicolor Research, Intel Labs Berkeley, Sprint Labs and SRI. She received her PhD from UC Berkeley. Over the years, she has worked in the fields of networking protocols, network traffic matrix estimation, Internet traffic modeling and prediction, intrusion detection, recommendation systems and privacy. Her current interests like in applications of machine learning for privacy, private data analytics, and user experience. She has been the chair or co-chair of the SIGCOMM, IMC and PAM conferences. (While some papers are listed here, see Google Scholar for a complete listing.)
Authored Publications
Google Publications
Other Publications
Sort By
A Decade of Privacy-Relevant Android App Reviews: Large Scale Trends
Omer Akgul
Michelle Mazurek
Benoit Seguin
Preview abstract
We present an analysis of 12 million instances of privacy-relevant reviews publicly visible on the Google Play Store that span a 10 year period. By leveraging state of the art NLP techniques, we examine what users have been writing about privacy along multiple dimensions: time, countries, app types, diverse privacy topics, and even across a spectrum of emotions. We find consistent growth of privacy-relevant reviews, and explore topics that are trending (such as Data Deletion and Data Theft), as well as those on the decline (such as privacy-relevant reviews on sensitive permissions). We find that although privacy reviews come from more than 200 countries, 33 countries provide 90% of privacy reviews. We conduct a comparison across countries by examining the distribution of privacy topics a country’s users write about, and find that geographic proximity is not a reliable indicator that nearby countries have similar privacy perspectives. We uncover some countries with unique patterns and explore those herein. Surprisingly, we uncover that it is not uncommon for reviews that discuss privacy to be positive (32%); many users express pleasure about privacy features within apps or privacy-focused apps. We also uncover some unexpected behaviors, such as the use of reviews to deliver privacy disclaimers to developers. Finally, we demonstrate the value of analyzing app reviews with our approach as a complement to existing methods for understanding users' perspectives about privacy.
View details
Balancing Privacy and Serendipity in CyberSpace
M. Satyanarayanan
Nigel Davies
International Workshop on Mobile Computing Systems and Applications (ACM HotMobile), http://www.hotmobile.org/2022/(2022)
Preview abstract
Unplanned encounters or casual collisions between colleagues have long
been recognized as catalysts for creativity and innovation. The absence of
such encounters has been a negative side effect of COVID-enforced remote
work. However, there have also been positive side effects such as less time
lost to commutes, lower carbon footprints, and improved work-life balance.
This vision paper explores how serendipity for remote workers can be
created by leveraging IoT technologies, edge computing, high-resolution
video, network protocols for live interaction, and video/audio denaturing.
We reflect on the privacy issues that technology-mediated serendipity raises
and sketch a path towards honoring diverse privacy preferences.
View details
Analyzing User Perspectives on Mobile App Privacy at Scale
International Conference on Software Engineering (ICSE)(2022)
Preview abstract
In this paper we present a methodology to analyze users’ concerns and perspectives about privacy at scale. We leverage NLP
techniques to process millions of mobile app reviews and extract
privacy concerns. Our methodology is composed of a binary classifier that distinguishes between privacy and non-privacy related
reviews. We use clustering to gather reviews that discuss similar
privacy concerns, and employ summarization metrics to extract
representative reviews to summarize each cluster. We apply our
methods on 287M reviews for about 2M apps across the 29 categories in Google Play to identify top privacy pain points in mobile
apps. We identified approximately 440K privacy related reviews.
We find that privacy related reviews occur in all 29 categories, with
some issues arising across numerous app categories and other issues
only surfacing in a small set of app categories. We show empirical
evidence that confirms dominant privacy themes – concerns about
apps requesting unnecessary permissions, collection of personal
information, frustration with privacy controls, tracking and the selling of personal data. As far as we know, this is the first large scale
analysis to confirm these findings based on hundreds of thousands
of user inputs. We also observe some unexpected findings such
as users warning each other not to install an app due to privacy
issues, users uninstalling apps due to privacy reasons, as well as
positive reviews that reward developers for privacy friendly apps.
Finally we discuss the implications of our method and findings for
developers and app stores.
View details
Hark: A Deep Learning System for Navigating Privacy Feedback at Scale
Rishabh Khandelwal
2022 IEEE Symposium on Security and Privacy (SP)
Preview abstract
Integrating user feedback is one of the pillars for building successful products. However, this feedback is generally collected in an unstructured free-text form, which is challenging to understand at scale. This is particularly demanding in the privacy domain due to the nuances associated with the concept and the limited existing solutions. In this work, we present Hark, a system for discovering and summarizing privacy-related feedback at scale. Hark automates the entire process of summarizing privacy feedback, starting from unstructured text and resulting in a hierarchy of high-level privacy themes and fine-grained issues within each theme, along with representative reviews for each issue. At the core of Hark is a set of new deep learning models trained on different tasks, such as privacy feedback classification, privacy issues generation, and high-level theme creation. We illustrate Hark’s efficacy on a corpus of 626M Google Play reviews. Out of this corpus, our privacy feedback classifier extracts 6M privacy-related reviews (with an AUC-ROC of 0.92). With three annotation studies, we show that Hark’s generated issues are of high accuracy and coverage and that the theme titles are of high quality. We illustrate Hark’s capabilities by presenting high-level insights from 1.3M Android apps.
View details
A Large Scale Study of Users Behaviors, Expectations and Engagement with Android Permissions
Weicheng Cao
Chunqiu Xia
David Lie
Lisa Austin
Usenix Security Symposium, Usenix, https://www.usenix.org/conference/usenixsecurity21(2021)
Preview abstract
We conduct a global study on the behaviors, expectations and engagement of 1,719 participants across 10 countries and regions towards Android application permissions. Participants were recruited using mobile advertising and used an application we designed for 30 days. Our app samples user behaviors (decisions made), rationales (via in-situ surveys), expectations, and attitudes, as well as some app provided explanations. We study the grant and deny decisions our users make, and build mixed effect logistic regression models to illustrate the many factors that influence this decision making. Among several interesting findings, we observed that users facing an unexpected permission request are more than twice as likely to deny it compared to a user who expects it, and that permission requests accompanied by an explanation have a deny rate that is roughly half the deny rate of app permission requests without explanations. These findings remain true even when controlling for other factors. To the best of our knowledge, this may be the first study of actual privacy behavior (not stated behavior) for Android apps, with users using their own devices, across multiple continents.
View details
"Shhh...be Quiet!" Reducing the Unwanted Interruptions of Notification Permission Prompts on Chrome
Balazs Engedy
Jud Porter
Kamila Hasanbega
Andrew Paseltiner
Hwi Lee
Edward Jung
PJ McLachlan
Jason James
30th USENIX Security Symposium (USENIX Security 21), USENIX Association, Vancouver, B.C.(2021)
Preview abstract
Push notifications are an extremely useful feature. In web browsers, they allow users to receive timely updates even if the website is not currently open. On Chrome, the feature has become extremely popular since its inception in 2015, but it is also the least likely to be accepted by users. Our telemetry shows that, although 74% of all permission prompts are about notifications, they are also the least likely to be granted with only a 10% grant rate on desktop and 21% grant rate on Android. In order to preserve its utility for the websites and to reduce unwanted interruptions for the users, we designed and tested a new UI for notification permission prompt on Chrome.
In this paper, we conduct two large-scale studies of Chrome users interactions with the notifications permission prompt in the wild, in order to understand how users interact with such prompts and to evaluate a novel design that we introduced in Chrome version 80 in February 2020. Our main goal for the redesigned UI is to reduce the unwanted interruptions due to notification permission prompts for Chrome users, the frequency at which users have to suppress them and the ease of changing a previously made choice.
Our results, based on an A/B test using behavioral data from more than 40 million users who interacted with more than 100 million prompts on more than 70 thousand websites, show that the new UI is very effective at reducing the unwanted interruptions and their frequency (up to 30% fewer unnecessary actions on the prompts), with a minimal impact (less than 5%) on the grant rates, across all types of users and websites. We achieve these results thanks to a novel adaptive activation mechanism coupled with a block list of interrupting websites, which is derived from crowd-sourced telemetry from Chrome clients.
View details
Reducing Permission Requests in Mobile Apps
Martin Pelikan
Ulfar Erlingsson
Giles Hogben
Proceedings of ACM Internet Measurement Conference (IMC)(2019)
Preview abstract
Users of mobile apps sometimes express discomfort or concerns with what they see as unnecessary or intrusive permission requests by certain apps. However encouraging mobile app developers to request fewer permissions is challenging because there are many reasons why permissions are requested; furthermore, prior work has shown it is hard to disambiguate the purpose of a particular permission with high certainty. In this work we describe a novel, algorithmic mechanism intended to discourage mobile-app developers from asking for unnecessary permissions. Developers are incentivized by an automated alert, or "nudge", shown in the Google Play Console when their apps ask for permissions that are requested by very few functionally-similar apps---in other words, by their competition. Empirically, this incentive is effective, with significant developer response since its deployment. Permissions have been redacted by 59% of apps that were warned, and this attenuation has occurred broadly across both app categories and app popularity levels. Importantly, billions of users' app installs from the Google Play have benefited from these redactions
View details
Exploring decision making with Android's runtime permission dialogs using in-context surveys
Thirteenth Symposium on Usable Privacy and Security (SOUPS), Usenix(2017)
Preview abstract
A great deal of research on the management of user data on smartphones via permission systems has revealed significant levels of user discomfort, lack of understanding, and lack of attention. The majority of these studies were conducted on Android devices before runtime permission dialogs were widely deployed. In this paper we explore how users make decisions with runtime dialogs on smartphones with Android 6.0 or higher. We employ an experience sampling methodology in order to ask users the reasons influencing their decisions immediately after they decide. We conducted a longitudinal survey with 157 participants over a 6 week period.
We explore the grant and denial rates of permissions, overall and on a per permission type basis. Overall, our participants accepted 84% of the permission requests. We observe differences in the denial rates across permissions types; these vary from 23% (for microphone) to 10% (calendar). We find that one of the main reasons for granting or denying a permission request depends on users’ expectation on whether or not an app should need a permission. A common reason for denying permissions is because users know they can change them later. Among the permissions granted, our participants said they were comfortable with 90% of those decisions - indicating that for 10% of grant decisions users may be consenting reluctantly. Interestingly, we found that women deny permissions twice as often as men.
View details
Privacy Mediators: Helping IoT Cross the Chasm
Nigel Davies
Mahadev Satyanarayanan
Sarah Clinch
Brandon Amos
International Workshop on Mobile Computing Systems and Applications (ACM HotMobile)(2016)
Preview abstract
Unease over data privacy will retard consumer acceptance of IoT
deployments. The primary source of discomfort is a lack of user
control over raw data that is streamed directly from sensors to the
cloud. This is a direct consequence of the over-centralization of
today’s cloud-based IoT hub designs. We propose a solution that
interposes a locally-controlled software component called a privacy
mediator on every raw sensor stream. Each mediator is in the same
administrative domain as the sensors whose data is being collected,
and dynamically enforces the current privacy policies of the owners
of the sensors or mobile users within the domain. This solution ne-
cessitates a logical point of presence for mediators within the admin-
istrative boundaries of each organization. Such points of presence
are provided by cloudlets, which are small locally-administered data
centers at the edge of the Internet that can support code mobility.
The use of cloudlet-based mediators aligns well with natural personal
and organizational boundaries of trust and responsibility.
View details
Preview abstract
The majority of internet traffic is now dominated
by streamed video content. As video quality continues to increase,
the strain that streaming traffic places on the network
infrastructure also increases. Caching content closer to users, e.g.,
using Content Distribution Networks, is a common solution to
reduce the load on the network. A simple approach to selecting
what to put in regional caches is to put the videos that are
most popular globally across the entire customer base. However,
this approach ignores distinct regional taste. In this paper we
explore the question of how a video content provider could go
about determining whether or not they should use a cache filling
policy based solely upon global popularity or take into account
regional tastes as well. We propose a model that captures the
overlap between inter-regional and intra-regional preferences. We
focus on movie content and derive a synthetic model that captures
“taste” using matrix factorization, similarly to the method used
in recommender systems. Our model enables us to widely explore
the parameter space, and derive a set of metrics providers can
use to determine whether populating caches according to regional
of global tastes provides better cache performance.
View details
Intuitions, analytics, and killing ants: Inference literacy of high school-educated adults in the US
Preview abstract
Analytic systems increasingly allow companies to draw inferences about users’ characteristics, yet users may not fully understand these systems due to their complex and often unintuitive nature. In this paper, we investigate inference literacy: the beliefs and misconceptions people have about how companies collect and make inferences from their data. We interviewed 21 non-student participants with a high school education, finding that few believed companies can make the type of deeply personal inferences that companies now routinely make through machine learning. Instead, most participant’s inference literacy beliefs clustered around one of two main concepts: one cluster believed companies make inferences about a person based largely on a priori stereotyping, using directly gathered demographic data; the other cluster believed that companies make inferences based on
computer processing of online behavioral data, but often expected these inferences to be limited to straightforward intuitions. We also find evidence that cultural models related to income and ethnicity influence the assumptions that users make about their own role in the data economy. We share implications for research, design, and policy on tech savviness, digital inequality, and potential inference literacy interventions.
View details
GraphSC: Parallel Secure Computation Made Easy
Kartik Nayak
Xiao S. Wang
Stratis Ioannidis
Udi Weinsberg
Elaine Shi
IEEE Symposium on Security and Privacy, IEEE(2015)
Preview abstract
We propose introducing modern parallel programming
paradigms to secure computation, enabling their secure
execution on large datasets. To address this challenge, we
present GraphSC, a framework that (i) provides a programming
paradigm that allows non-cryptography experts to write secure
code; (ii) brings parallelism to such secure implementations; and
(iii) meets the needs for obliviousness, thereby not leaking any
private information. Using GraphSC, developers can efficiently
implement an oblivious version of graph-based algorithms (including
sophisticated data mining and machine learning algorithms)
that execute in parallel with minimal communication
overhead. Importantly, our secure version of graph-based algorithms
incurs a small logarithmic overhead in comparison
with the non-secure parallel version. We build GraphSC and
demonstrate, using several algorithms as examples, that secure
computation can be brought into the realm of practicality for big
data analysis. Our secure matrix factorization implementation
can process 1 million ratings in 13 hours, which is a multiple
order-of-magnitude improvement over the only other existing attempt, which requires 3 hours to process 16K ratings.
View details
Perceived Frequency of Advertising Practices
Allen Collins
Aaron Sedley
Allison Woodruff
Symposium on Usable Privacy and Security (SOUPS), Privacy Personas and Segmentation Workshop, Usenix(2015)
Preview abstract
In this paper, we introduce a new construct for measuring individuals’ privacy-related beliefs and understandings, namely their perception of the frequency with which information about individuals is gathered and used by others for advertising purposes. We introduce a preliminary instrument for measuring this perception, called the Ad Practice Frequency Perception Scale. We report data from a survey using this instrument, as well as the results of an initial clustering of participants based on this data. Our results, while preliminary, suggest that this construct may have future potential to characterize and segment individuals, and is worthy of further exploration.
View details
Managing your Private and Public Data: Bringing down Inference Attacks against your Privacy
Amy Zhang
Branislav Kveton
Flavio du Pin Calmon
Nadia Fawaz
Pedro Oliveira
Salman Salamatian
Sandilya Bhamidipati
IEEE Journal on Signal Processing(2015)
Preview abstract
We propose a practical methodology to protect a user’s private data, when he wishes to publicly release data that is correlated with his private data, in the hope of getting some utility. Our approach relies on a general statistical inference framework that captures the privacy threat under inference
attacks, given utility constraints. Under this framework, data is distorted before it is released, according to a probabilistic privacy mapping. This mapping is obtained by solving a convex optimization problem, which minimizes information leakage under a distortion constraint. We address practical challenges encountered when applying this theoretical framework to real world
data. On one hand, the design of optimal privacy-preserving mechanisms requires knowledge of the prior distribution linking private data and data to be released, which is often unavailable in practice. On the other hand, the optimization may become untractable when data assumes values in large size alphabets, or is high dimensional. Our work makes three major contributions.
First, we provide bounds on the impact of a mismatched prior on the privacy-utility tradeoff. Second, we show how to reduce the optimization size by introducing a quantization step, and how to generate privacy mappings under quantization. Third, we evaluate our method on two datasets, including a new dataset that we collected, showing correlations between political convictions
and TV viewing habits. We demonstrate that good privacy properties can be achieved with limited distortion so as not to undermine the original purpose of the publicly released data, e.g. recommendations.
View details
Privacy Tradeoffs in Predictive Analytics
Stratis Ioannidis
Andrea Montanari
Udi Weinsberg
Smriti Bhagat
Nadia Fawaz
Sigmetrics, ACM(2014)
Preview abstract
Online services routinely mine user data to predict user preferences,
make recommendations, and place targeted ads. Recent research has demonstrated that several private user attributes (such as political affiliation, sexual orientation, and gender) can be inferred from such data. Can a privacy conscious user benefit from personalization while simultaneously protecting her private attributes? We study this question in the context of a rating prediction service based on
matrix factorization. We construct a protocol of interactions between the service and users that has remarkable optimality properties: it is privacy-preserving, in that no inference algorithm can succeed in inferring a user’s private attribute with a probability better than random guessing; it has maximal accuracy, in that no other privacy-preserving protocol improves rating prediction; and, finally, it involves a minimal
disclosure, as the prediction accuracy strictly decreases when the service reveals less information. We extensively evaluate our protocol using several rating datasets, demonstrating that it successfully blocks the inference of gender, age and political affiliation, while incurring less than 5% decrease in the accuracy of rating prediction.
View details
Recommending with an Agenda: Active Learning of Private Attributes using Matrix Factorization.
Preview abstract
Recommender systems leverage user demographic information, such as age, gender, etc., to personalize recommendations and better place their targeted ads. Oftentimes, users do not volunteer this information due to privacy concerns, or due to a lack of initiative in filling out their online profiles. We illustrate a new threat in which a recommender learns private attributes of users who do not voluntarily disclose
them. We design both passive and active attacks that solicit ratings for strategically selected items, and could thus be used by a recommender system to pursue this hidden agenda. Our methods are based on a novel usage of Bayesian matrix factorization in an active learning setting. Evaluations on multiple datasets illustrate that such attacks are indeed feasible and use significantly fewer rated items than
static inference methods. Importantly, they succeed without sacrificing the quality of recommendations to users.
View details
Privacy Preserving Ridge Regression on Hundreds of Millions of Records
Valeria Nikolaenko
Udi Weinsberg
Stratis Ioannidis
Marc Joye
Dan Boneh
Symposium on Security and Privacy, IEEE(2013), pp. 334-348
Preview abstract
Ridge regression is an algorithm that takes as input a large number of data points and finds the best-fit linear curve through these points. The algorithm is a building block for many machine-learning operations. We present a system for privacy-preserving ridge regression. The system outputs the best-fit curve in the clear, but exposes no other information about the input data. Our approach combines both homomorphic encryption and Yao garbled circuits, where each is used in a different part of the algorithm to obtain
the best performance. We implement the complete system and experiment with it on real data-sets, and show that it significantly outperforms pure implementations based only on homomorphic encryption or Yao circuits.
View details
Privacy Preserving Matrix Factorization
Valeria Nikolaenko
Stratis Ioannidis
Udi Weinsberg
Marc Joye
Dan Boneh
20th ACM Conference on Computer and Communications Security (CCS)(2013)
Preview abstract
Recommender systems typically require users to reveal their ratings to a recommender service, which subsequently uses them to provide relevant recommendations. Revealing ratings has been shown to make users susceptible to a broad set of inference attacks, allowing the recommender to learn
private user attributes, such as gender, age, etc. In this work, we show that a recommender can profile items without ever learning the ratings users provide, or even which items they have rated. We show this by designing a system
that performs matrix factorization, a popular method used in a variety of modern recommendation systems, through a cryptographic technique known as garbled circuits. Our design uses oblivious sorting networks in a novel way to
leverage sparsity in the data. This yields an efficient implementation, whose running time is Θ(M log2 M) in the number of ratings M. Crucially, our design is also highly parallelizable, giving a linear speedup with the number of
available processors. We further fully implement our system, and demonstrate that even on commodity hardware with 16 cores, our privacy-preserving implementation can factorize a matrix with 10K ratings within a few hours.
View details
BlurMe: Inferring and Obfuscating User Gender Based on Ratings.
Preview abstract
User demographics, such as age, gender and ethnicity, are routinely used for targeting content and advertising products to users. Similarly, recommender systems utilize user demographics for personalizing recommendations and overcoming the cold-start problem. Often, privacy-concerned users do not provide these details in their online profiles. In this work, we show that a recommender system can infer the gender of a user with high accuracy, based solely on the ratings
provided by users (without additional metadata), and a relatively small number of users who share their demographics. We design techniques for effectively adding ratings to a user’s profile for obfuscating the user’s gender, while having an insignificant effect on the recommendations provided to that user.
View details
CARE: Content Aware Redundancy Elimination for Challenged Networks
Athula Balachandran
Gianluca Iannaccone
Qingxi Li
Srinivasan Seshan
Udi Weinsberg
Vyas Sekar
ACM Hot Topics in Networking(2012)
Preview abstract
This paper presents the design of a novel architecture called
CARE (Content-Aware Redundancy Elimination) that enables
maximizing the informational value that challenged
networks offer their users. We focus on emerging applications
for situational awareness in disaster affected regions.
Motivated by advances in computer vision algorithms, we
propose to incorporate image similarity detection algorithms
in the forwarding path of these networks. The purpose is to
handle the large generation of redundant content. We outline
the many issues involved in such a vision. With a DelayTolerant
Network (DTN) setup, our simulations demonstrate
that CARE can substantially boost the number of unique
messages that escape the disaster zone, and it can also deliver
them faster. These benefits are achieved despite the
energy overhead needed by the similarity detectors.
View details
Finding a Needle in a Haystack of Reviews: Cold Start Context-Based Hotel Recommender System
Asher Levi
Osnat Mokryn
Christophe Diot
Proceedings of ACM Conference on Recommender Systerms(2012), pp. 115-122
Preview abstract
Online hotel searching is a daunting task due to the wealth of online information. Reviews written by other travelers replace the word-of-mouth, yet turn the search into a time consuming task. Users do
not rate enough hotels to enable a collaborative filtering based recommendation. Thus, a cold start recommender system is needed. In this work we design a cold start hotel recommender system, which uses the text of the reviews as its main data. We define context groups based on reviews extracted from TripAdvisor.com and Venere.com. We introduce a novel weighted algorithm for text mining. Our algorithm imitates a user that favors reviews written with the same trip intent and from people of similar background (nationality) and with similar preferences for hotel aspects, which are
our defined context groups. Our approach combines numerous elements, including unsupervised clustering to build a vocabulary for hotel aspects, semantic analysis to understand sentiment towards
hotel features, and the profiling of intent and nationality groups. We implemented our system which was used by the public to conduct 150 trip planning experiments. We compare our solution to the top suggestions of the mentioned web services and show that users were, on average, 20% more satisfied with our hotel recommendations. We outperform these web services even more in cities where hotel prices are high.
View details
Public Health for the Internet (PHI)
Joseph M. Hellerstein
Tyson Condie
Minos N. Garofalakis
Boon Thau Loo
Timothy Roscoe
CIDR(2007), pp. 332-340
Traffic Matrices: Balancing Measurements, Inference and Modeling
Augustin Soule
Anukool Lakhina
Konstantina Papagiannaki
Kave Salamatian
Antonio Nucci
Mark Crovella
Christophe Diot
ACM Sigmetrics: Conference on Measurement and Modeling of Computer Systems(2005)
Preview abstract
Traffic matrix estimation is well-studied, but in general has been treated simply as a statistical inference problem. In practice, however, network operators seeking traffic matrix information have a range of options available to them. Operators can measure traffic flows directly; they can perform partial flow measurement, and infer missing data using models; or they can perform no flow measurement and infer traffic matrices directly from link counts. The advent of practical flow measurement makes the study of these tradeoffs more important. In particular, an important question is whether judicious modeling, combined with partial flow measurement, can provide traffic matrix estimates that are significantly better than previous methods at relatively low cost. In this paper we make a number of contributions toward answering this question. First, we provide a taxonomy of the kinds of models that may make use of partial flow measurement, based on the nature of the measurements used and the spatial, temporal, or spatio-temporal correlation exploited. We then evaluate estimation methods which use each kind of model. In the process we propose and evaluate new methods, and extensions to methods previously proposed. We show that, using such methods, small amounts of traffic flow measurements can have significant impacts on the accuracy of traffic matrix estimation, yielding results much better than previous approaches. We also show that different methods differ in their bias and variance properties, suggesting that different methods may be suited to different applications.
View details
Combining Filtering and Statistical Methods for Anomaly Detection
Preview abstract
In this work we develop an approach for anomaly detection for large scale networks such as that of an enterprize or an ISP. The traffic patterns we focus on for analysis are that of a network-wide view of the traffic state, called the traffic matrix. In the first step a Kalman filter is used to filter out the “normal” traffic. This is done by comparing our future predictions of the traffic matrix state to an inference
of the actual traffic matrix that is made using more recent measurement data than those used for prediction. In the second step the residual filtered process is then examined for anomalies. We explain here how any anomaly detection method can be viewed as a problem in statistical hypothesis testing. We study and compare four different methods for analyzing residuals, two of which are new. These methods focus on different aspects of the traffic pattern change. One focuses on instantaneous behavior, another focuses on changes in the mean of the residual process, a third on changes in the variance behavior, and a fourth examines variance changes over multiple timescales. We evaluate
and compare all of these methods using ROC curves that illustrate the full tradeoff between false positives and false negatives for the complete spectrum of decision thresholds.
View details
Structural Analysis of Network Traffic Flows
Anukool Lakhina
Konstantina Papagiannaki
Mark Crovella
Christophe Diot
Eric Kolaczyk
ACM Sigmetrics: Conference on Measurement and Modeling of Computer Systems(2004), pp. 61-72
Preview abstract
Network traffic arises from the superposition of Origin-Destination (OD) flows. Hence, a thorough understanding of OD flows is essential for modeling network traffic, and for addressing a wide variety of problems including traffic engineering, traffic matrix estimation, capacity planning, forecasting and anomaly detection. However, to date, OD flows have not been closely studied, and there is very little known about their properties.We present the first analysis of complete sets of OD flow time-series, taken from two different backbone networks (Abilene and Sprint-Europe). Using Principal Component Analysis (PCA), we find that the set of OD flows has small intrinsic dimension. In fact, even in a network with over a hundred OD flows, these flows can be accurately modeled in time using a small number (10 or less) of independent components or dimensions.We also show how to use PCA to systematically decompose the structure of OD flow time series into three main constituents: common periodic trends, short-lived bursts, and noise. We provide insight into how the various constituents contribute to the overall structure of OD flows and explore the extent to which this decomposition varies over time.
View details
Long Term Forecasting of Internet Backbone Traffic: Observations and Initial Models
Preview abstract
We introduce a methodology to predict when and where link additions/upgrades have to take place in an IP backbone network. Using SNMP statistics, collected continuously since 1999, we compute aggregate demand between any two adjacent PoPs and look at its evolution at time scales larger than one hour. We show that IP backbone traffic exhibits visible long term trends, strong periodicities, and variability at multiple time scales. Our methodology relies on the wavelet multi-resolution analysis and linear time series models. Using wavelet multi-resolution analysis, we smooth the collected measurements until we identify the overall long-term trend. The fluctuations around the obtained trend are further analyzed at multiple time scales. We show that the largest amount of variability in the original signal is due to its fluctuations at the 12 hour time scale. We model inter-PoP aggregate demand as a multiple linear
regression model, consisting of the two identified components. We show that this model accounts for 98% of the total energy in the original signal, while explaining 90% of its variance. Weekly approximations of those components can be accurately modeled with low-order AutoRegressive Integrated Moving Average (ARIMA) models. We show that forecasting the long term trend and the fluctuations of the traffic at the 12 hour time scale yields accurate estimates for at least six months in the future.
View details
Traffic Matrix Estimation: Existing Techniques and New Directions
Alberto Medina
Kave Salamatian
Supratik Bhattacharyya
Christophe Diot
ACM Proceedings of SIGCOMM conference(2002), pp. 161-174
Preview abstract
Very few techniques have been proposed for estimating traffic matrices in the context of Internet traffic. Our work on POP-to-POP traffic matrices (TM) makes two contributions. The primary contribution is the outcome of a detailed comparative evaluation of the three existing techniques. We evaluate these methods with respect to the estimation errors yielded, sensitivity to prior information required and sensitivity to the statistical assumptions they make. We study the impact of characteristics such as path length and the amount of link sharing on the estimation errors. Using actual data from a Tier-1 backbone, we assess the validity of the typical assumptions needed by the TM estimation techniques. The secondary contribution of our work is the proposal of a new direction for TM estimation based on using choice models to model POP fanouts. These models allow us to overcome some of the problems of existing methods because they can incorporate additional data and information about POPs and they enable us to make a fundamentally different kind of modeling assumption. We validate this approach by illustrating that our modeling assumption matches actual Internet data well. Using two initial simple models we provide a proof of concept showing that the incorporation of knowledge of POP features (such as total incoming bytes, number of customers, etc.) can reduce estimation errors. Our proposed approach can be used in conjunction with existing or future methods in that it can be used to generate good priors that serve as inputs to statistical inference techniques.
View details
