Internet-of-Things (IoT) devices are vulnerable to malware and require new mitigation techniques due to their limited resources. To that end, previous research has used periodic Remote Attestation ($R A$) or Traffic Analysis ($\mathcal{T} A$) to detect malware in IoT devices. However,$\mathcal{R A}$is expensive, and$\mathcal{T}$A only raises suspicion without confirming malware presence. To solve this, we design MADEA, the first system that blends$\mathcal{R A}$and$\mathcal{T A}$to offer a comprehensive approach to malware detection for IoT.$\mathcal{T}$A builds profiles of expected packet traces during benign operations of each device and then uses them to detect malware from network traffic in real-time.$\mathcal{R A}$confirms the presence or absence of malware on the device. MADEA achieves 100 % true positive rate. It also outperforms other approaches with$160 \times$faster detection time. Finally, without MADEA, effective periodic$\mathcal{R A}$can consume at least$\sim 14 \times$the amount of energy that a device needs in one hour.

Many devices are accessed and controlled through voice assistants today, a representative example being Echo smart speakers and other Amazon devices controlled by Alexa. These offer the convenience of accessing services through voice interactions, but also raise privacy concerns, as data can be stored and used for personalization, and voice biometric information is sensitive. Unfortunately, there remains a lack of transparency and control over the collection and use of this data. Although prior work has shown evidence of ad targeting based on data derived from voice interactions and user profiles/interests, it has so far been an open question whether voice biometric information itself is utilized for targeting. In this paper, (i) we build a general auditing methodology to answer this question for off-the-shelf commercial smart speakers, and (ii) we apply it specifically to Amazon Echo Dot. Our findings suggest that Amazon Music ad content is more strongly associated with attributes (gender and age) related to voice characteristics than would be expected by chance. This has important implications for compliance, since voice contains sensitive biometric information that is protected by several privacy regulations.

The widespread adoption of Augmented Reality (AR) technologies has raised significant privacy concerns, particularly for bystanders inadvertently captured by these systems. While some solutions have been proposed, they suffer from limitations, such as dependence on biometric faceprints and lack of real-time processing. To overcome these challenges, this paper introduces BystandARIA, a novel privacy signaling system that enables real-time, selective, user-controlled privacy protection without relying on biometric face prints. We leverage, for the first time, visible light communication, utilizing an LED, to achieve this goal. Our design enables (i) an AR device to detect and spatially localize bystanders and (ii) bystanders to communicate their privacy preferences to nearby AR devices, which can then selectively blur faces in real-time. We present the design, prototype implementation, and evaluation of BystandARIA, demonstrating its effectiveness in various environments. Our results show that BystandARIA achieves up to 95% detection accuracy with an average latency of 50ms, providing a promising solution for bystander privacy protection in digital spaces. We believe that our solution has the potential for widespread adoption due to its low cost and ease of use.

Web forms are one of the primary ways to collect personal information online, yet they are relatively under-studied. Unlike web tracking, data collection through web forms is explicit and contextualized. Users (i) are asked to input specific personal information types, and (ii) know the specific context (i.e., on which website and for what purpose). For web forms to be trusted by users, they must meet the common sense standards of appropriate data collection practices within a particular context (i.e., privacy norms). In this paper, we extract the privacy norms embedded within web forms through a measurement study. First, we build a specialized crawler to discover web forms on websites. We run it on 11,500 popular websites, and we create a dataset of 293K web forms. Second, to process data of this scale, we develop a cost-efficient way to annotate web forms with form types and personal information types, using text classifiers trained with assistance of large language models (LLMs). Third, by analyzing the annotated dataset, we reveal common patterns of data collection practices. We find that (i) these patterns are explained by functional necessities and legal obligations, thus reflecting privacy norms, and that (ii) deviations from the observed norms often signal unnecessary data collection. In addition, we analyze the privacy policies that accompany web forms. We show that, despite their wide adoption and use, there is a disconnect between privacy policy disclosures and the observed privacy norms.

Virtual reality (VR) platforms enable a wide range of applications, however, pose unique privacy risks. In particular, VR devices are equipped with a rich set of sensors that collect personal and sensitive information (e.g., body motion, eye gaze, hand joints, and facial expression). The data from these newly available sensors can be used to uniquely identify a user, even in the absence of explicit identifiers. In this paper, we seek to understand the extent to which a user can be identified based solely on VR sensor data, within and across real-world apps from diverse genres. We consider adversaries with capabilities that range from observing APIs available within a single app (app adversary) to observing all or selected sensor measurements across multiple apps on the VR device (device adversary). To that end, we introduce BehaVR, a framework for collecting and analyzing data from all sensor groups collected by multiple apps running on a VR device. We use BehaVR to collect data from real users that interact with 20 popular real-world apps. We use that data to build machine learning models for user identification within and across apps, with features extracted from available sensor data. We show that these models can identify users with an accuracy of up to 100%, and we reveal the most important features and sensor groups, depending on the functionality of the app and the adversary. To the best of our knowledge, BehaVR is the first to analyze user identification in VR comprehensively, i.e., considering all sensor measurements available on consumer VR devices, collected by multiple real-world, as opposed to custom-made, apps.

Adblocking relies on filter lists, which are manually curated and maintained by a community of filter list authors. Filter list curation is a laborious process that does not scale well to a large number of sites or over time. In this article, we introduce AutoFR, a reinforcement learning framework to fully automate the process of filter rule creation and evaluation for sites of interest. We design an algorithm based on multi-arm bandits to generate filter rules that block ads while controlling the trade-off between blocking ads and avoiding visual breakage. We test AutoFR on thousands of sites and show that it is efficient: It takes only a few minutes to generate filter rules for a site of interest. AutoFR is effective: It optimizes filter rules for a particular site that can block 86% of the ads, as compared to 87% by EasyList, while achieving comparable visual breakage. Using AutoFR as a building block, we devise three methodologies that generate filter rules across sites based on: (1) a modified version of AutoFR, (2) rule popularity, and (3) site similarity. We conduct an in-depth comparative analysis of these approaches by considering their effectiveness, efficiency, and maintainability. We demonstrate that some of them can generalize well to new sites in both controlled and live settings. We envision that AutoFR can assist the adblocking community in automatically generating and updating filter rules at scale.

Children's and adolescents' online data privacy are regulated by laws such as the Children's Online Privacy Protection Act (COPPA) and the California Consumer Privacy Act (CCPA). Online services that are directed towards general audiences (i.e., including children, adolescents, and adults) must comply with these laws. In this paper, first, we present DiffAudit, a platform-agnostic privacy auditing methodology for general audience services. DiffAudit performs differential analysis of network traffic data flows to compare data processing practices (i) between child, adolescent, and adult users and (ii) before and after consent is given and user age is disclosed. We also present a data type classification method that utilizes GPT-4 and our data type ontology based on COPPA and CCPA, allowing us to identify considerably more data types than prior work. Second, we apply DiffAudit to a set of popular general audience mobile and web services and observe a rich set of behaviors extracted from over 440K outgoing requests, containing 3,968 unique data types we extracted and classified. We reveal problematic data processing practices prior to consent and age disclosure, lack of differentiation between age-specific data flows, inconsistent privacy policy disclosures, and sharing of linkable data with third parties, including advertising and tracking services.

Signal maps are essential for the planning and operation of cellular networks. However, the measurements needed to create such maps are expensive, often biased, not always reflecting the performance metrics of interest, and posing privacy risks. In this paper, we develop a unified framework for predicting cellular performance maps from limited available measurements. Our framework builds on a state-of-the-art random-forest predictor, or any other base predictor. We propose and combine three mechanisms that deal with the fact that not all measurements are equally important for a particular prediction task. First, we designquality-of-service functions ($Q$Q), including signal strength (RSRP) but also other metrics of interest to operators, such as number of bars, coverage (improving recall by 76%-92%) and call drop probability (reducing error by as much as 32%). By implicitly altering the loss function employed in learning, quality functions can also improve prediction for RSRP itself where it matters (e.g., MSE reduction up to 27% in the low signal strength regime, where high accuracy is critical). Second, we introduceweight functions($W$) to specify the relative importance of prediction at different locations and other parts of the feature space. We propose re-weighting based on importance sampling to obtain unbiased estimators when the sampling and target distributions are different. This yields improvements up to 20% for targets based on spatially uniform loss or losses based on user population density. Third, we apply theData Shapleyframework for the first time in this context: to assign values ($\phi$) to individual measurement points, which capture the importance of their contribution to the prediction task. This can improve prediction (e.g., from 64% to 94% in recall for coverage loss) by removing points with negative values and storing only the remaining data points (i.e., as low as 30%), which also has the side-benefit of helping privacy. We evaluate our methods and demonstrate significant improvement in prediction performance, using several real-world datasets.

We consider the problem of predicting cellular network performance (signal maps) from measurements collected by several mobile devices. We formulate the problem within the online federated learning framework: (i) federated learning (FL) enables users to collaboratively train a model, while keeping their training data on their devices; (ii) measurements are collected as users move around over time and are used for local training in an online fashion. We consider an honest-but-curious server, who observes the updates from target users participating in FL and infers their location using a deep leakage from gradients (DLG) type of attack, originally developed to reconstruct training data of DNN image classifiers. We make the key observation that a DLG attack, applied to our setting, infers the average location of a batch of local data, and can thus be used to reconstruct the target users' trajectory at a coarse granularity. We build on this observation to protect location privacy, in our setting, by revisiting and designing mechanisms within the federated learning framework including: tuning the FL parameters for averaging, curating local batches so as to mislead the DLG attacker, and aggregating across multiple users with different trajectories. We evaluate the performance of our algorithms through both analysis and simulation based on real-world mobile datasets, and we show that they achieve a good privacy-utility tradeoff.

Smart speakers collect voice commands, which can be used to infer sensitive information about users. Given the potential for privacy harms, there is a need for greater transparency and control over the data collected, used, and shared by smart speaker platforms as well as third party skills supported on them. To bridge this gap, we build a framework to measure data collection, usage, and sharing by the smart speaker platforms. We apply our framework to the Amazon smart speaker ecosystem. Our results show that Amazon and third parties, including advertising and tracking services that are unique to the smart speaker ecosystem, collect smart speaker interaction data. We also find that Amazon processes smart speaker interaction data to infer user interests and uses those inferences to serve targeted ads to users. Smart speaker interaction also leads to ad targeting and as much as 30X higher bids in ad auctions, from third party advertisers. Finally, we find that Amazon's and third party skills' data practices are often not clearly disclosed in their policy documents.

We consider the problem of population density estimation based on location data crowdsourced from mobile devices, using kernel density estimation (KDE). In a conventional, centralized setting, KDE requires mobile users to upload their location data to a server, thus raising privacy concerns. Here, we propose a Federated KDE framework for estimating the user population density, which not only keeps location data on the devices but also provides probabilistic privacy guarantees against a malicious server that tries to infer users' location. Our approach Federated random Fourier feature (RFF) KDE leverages a random feature representation of the KDE solution, in which each user's information is irreversibly projected onto a small number of spatially delocalized basis functions, making precise localization impossible while still allowing population density estimation. We evaluate our method on both synthetic and real-world datasets, and we show that it achieves a better utility (estimation performance)-vs-privacy (distance between inferred and true locations) tradeoff, compared to state-of-the-art baselines (e.g., GeoInd). We also vary the number of basis functions per user, to further improve the privacy-utility trade-off, and we provide analytical bounds on localization as a function of areal unit size and kernel bandwidth.

This paper proposes FingerprinTV, a fully automated methodology for extracting fingerprints from the network traffic of smart TV apps and assessing their performance. FingerprinTV (1) installs, repeatedly launches, and collects network traffic from smart TV apps; (2) extracts three different types of network fingerprints for each app, i.e., domain-based fingerprints (DBF), packet-pair-based fingerprints (PBF), and TLS-based fingerprints (TBF); and (3) analyzes the extracted fingerprints in terms of their prevalence, distinctiveness, and sizes. From applying FingerprinTV to the top-1000 apps of the three most popular smart TV platforms, we find that smart TV app network fingerprinting is feasible and effective: even the least prevalent type of fingerprint manifests itself in at least 68% of apps of each platform, and up to 89% of fingerprints uniquely identify a specific app when two fingerprinting techniques are used together. By analyzing apps that exhibit identical fingerprints, we find that these apps often stem from the same developer or “no code” app generation toolkit. Furthermore, we show that many apps that are present on all three platforms exhibit platformspecific fingerprints.

In order to improve mobile data transparency, various approaches have been proposed to inspect network traffic generated by mobile devices and detect exposure of personally identifiable information (PII), ad requests, etc. State-of-the-art approaches use features extracted from HTTP packets and train classifiers in a centralized way: users collect and label network packets on their mobile devices, then upload data to a central server; the server uses the data contributed by all users to train a packet classifier. However, training datasets from network traffic collected on user devices may contain sensitive information that users may not want to upload. In this article, we propose a federated learning approach to mobile packet classification, which enables devices to collaboratively train a global model, without uploading the training data collected on devices. We apply our framework to two packet classification tasks (i.e., to predict PII exposure or ad requests in individual packets) and we demonstrate its effectiveness in terms of classification performance, communication and computation cost, using three real-world datasets. Methodological challenges we address in the process include model and feature selection, as well as tuning the federated learning parameters specifically for our packet classification tasks. We also discuss privacy limitations and mitigation approaches.

Abstract Today’s mobile apps employ third-party advertising and tracking (A&T) libraries, which may pose a threat to privacy. State-of-the-art detects and blocks outgoing A&T HTTP/S requests by using manually curated filter lists (e.g. EasyList), and recently, using machine learning approaches. The major bottleneck of both filter lists and classifiers is that they rely on experts and the community to inspect traffic and manually create filter list rules that can then be used to block traffic or label ground truth datasets. We propose NoMoATS – a system that removes this bottleneck by reducing the daunting task of manually creating filter rules, to the much easier and scalable task of labeling A&T libraries. Our system leverages stack trace analysis to automatically label which network requests are generated by A&T libraries. Using NoMoATS, we collect and label a new mobile traffic dataset. We use this dataset to train decision tree classifiers, which can be applied in real-time on the mobile device and achieve an average F-score of 93%. We show that both our automatic labeling and our classifiers discover thousands of requests destined to hundreds of different hosts, previously undetected by popular filter lists. To the best of our knowledge, our system is the first to (1) automatically label which mobile network requests are engaged in A&T, while requiring to only manually label libraries to their purpose and (2) apply on-device machine learning classifiers that operate at the granularity of URLs, can inspect connections across all apps, and detect not only ads, but also tracking.

Abstract In this paper, we present a large-scale measurement study of the smart TV advertising and tracking ecosystem. First, we illuminate the network behavior of smart TVs as used in the wild by analyzing network traffic collected from residential gateways. We find that smart TVs connect to well-known and platform-specific advertising and tracking services (ATSes). Second, we design and implement software tools that systematically explore and collect traffic from the top-1000 apps on two popular smart TV platforms, Roku and Amazon Fire TV. We discover that a subset of apps communicate with a large number of ATSes, and that some ATS organizations only appear on certain platforms, showing a possible segmentation of the smart TV ATS ecosystem across platforms. Third, we evaluate the (in)effectiveness of DNS-based blocklists in preventing smart TVs from accessing ATSes. We highlight that even smart TV-specific blocklists suffer from missed ads and incur functionality breakage. Finally, we examine our Roku and Fire TV datasets for exposure of personally identifiable information (PII) and find that hundreds of apps exfiltrate PII to third parties and platform domains. We also find evidence that some apps send the advertising ID alongside static PII values, effectively eliminating the user’s ability to opt out of ad personalization.

Signal strength maps are of great importance to cellular providers for network planning and operation, however they are expensive to obtain and possibly limited or inaccurate in some locations. In this paper, we develop a prediction framework based on random forests to improve signal strength maps from limited measurements. First, we propose a random forests (RFs)-based predictor, with a rich set of features including location as well as time, cell ID, device hardware and other features. We show that our RFs-based predictor can significantly improve the tradeoff between prediction error and number of measurements needed compared to state-of-the-art data-driven predictors, i.e., requiring 80% less measurements for the same prediction accuracy, or reduces the relative error by 17% for the same number of measurements. Second, we leverage two types of real-world LTE RSRP datasets to evaluate into the performance of different prediction methods: (i) a small but dense Campus dataset, collected on a university campus and (ii) several large but sparser NYC and LA datasets, provided by a mobile data analytics company.

Community structure is an important property that captures inhomogeneities common in large networks, and modularity is one of the most widely used metrics for such community structure. In this paper, we introduce a principled methodology, the Spectral Graph Forge, for generating random graphs that preserves community structure from a real network of interest, in terms of modularity. Our approach leverages the fact that the spectral structure of matrix representations of a graph encodes global information about community structure. The Spectral Graph Forge uses a low-rank approximation of the modularity matrix to generate synthetic graphs that match a target modularity within user-selectable degree of accuracy, while allowing other aspects of structure to vary. We show that the Spectral Graph Forge outperforms state-of-the-art techniques in terms of accuracy in targeting the modularity and randomness of the realizations, while also preserving other local structural properties and node attributes. We discuss extensions of the Spectral Graph Forge to target other properties beyond modularity, and its applications to anonymization.

In this paper, we study the problem of generating synthetic graphs that resemble real-world graphs in terms of their degree correlations and potentially additional properties. We present an algorithmic framework that generates simple undirected graphs with the exact target joint degree matrix, which we refer to as 2K graphs, in linear time in the number of edges. Our framework imposes minimal constraints on the graph structure, which allows us to target additional graph properties during construction, namely, node attributes (2K+A), clustering (both average clustering, 2.25K, and degree-dependent clustering, 2.5K), and number of connected components (2K+CC). We also define, for the first time, the problem of directed 2K graph construction, provide necessary and sufficient conditions for realizability, and develop efficient construction algorithms. We evaluate our approach by creating synthetic graphs that target real-world graphs both undirected (such as Facebook) and directed (such as Twitter), and we show that it brings significant benefits, in terms of accuracy and running time, compared to the state-of-the-art approaches.

Community structure is an important property that captures inhomogeneities common in large networks, and modularity is one of the most widely used metrics for such community structure. In this paper, we introduce a principled methodology, the Spectral Graph Forge, for generating random graphs that preserves community structure from a real network of interest, in terms of modularity. Our approach leverages the fact that the spectral structure of matrix representations of a graph encodes global information about community structure. The Spectral Graph Forge uses a low-rank approximation of the modularity matrix to generate synthetic graphs that match a target modularity within user-selectable degree of accuracy, while allowing other aspects of structure to vary. We show that the Spectral Graph Forge outperforms state-of-the-art techniques in terms of accuracy in targeting the modularity and randomness of the realizations, while also preserving other local structural properties and node attributes. We discuss extensions of the Spectral Graph Forge to target other properties beyond modularity, and its applications to anonymization.

Mobile devices have become an essential part of our every-day lives but are also suffering from various privacy and security risks. The ease of app development has led to a plethora of apps that employ poor security practices and often expose personal identifiers to remote servers. Moreover, these privacy exposures often come from third-party libraries that are leveraged by multiple apps, leading to cross-app tracking of users. This tracking is typically used to serve personalized ads, which cost the user extra data and take up screen real estate. In this demo, we will showcase AntWall, a system for preventing exposures of personal information and blocking ads.

Abstract Although advertising is a popular strategy for mobile app monetization, it is often desirable to block ads in order to improve usability, performance, privacy, and security. In this paper, we propose NoMoAds to block ads served by any app on a mobile device. NoMoAds leverages the network interface as a universal vantage point: it can intercept, inspect, and block outgoing packets from all apps on a mobile device. NoMoAds extracts features from packet headers and/or payload to train machine learning classifiers for detecting ad requests. To evaluate NoMoAds, we collect and label a new dataset using both EasyList and manually created rules. We show that NoMoAds is effective: it achieves an F-score of up to 97.8% and performs well when deployed in the wild. Furthermore, NoMoAds is able to detect mobile ads that are missed by EasyList (more than one-third of ads in our dataset). We also show that NoMoAds is efficient: it performs ad classification on a per-packet basis in real-time. To the best of our knowledge, NoMoAds is the first mobile ad-blocker to effectively and efficiently block ads served across all apps using a machine learning approach.

We study the problem of generating synthetic graphs that resemble real-world directed graphs in terms of their degree correlations. In order to capture degree correlation specifically for directed graphs, we define directed 2K (D2K) as those graphs with a given directed degree sequence (DDS) and a given target joint degree and attribute matrix (JDAM). We provide necessary and sufficient conditions for a target D2K to be realizable and we design an efficient algorithm that generates graph realizations with exactly the target D2K. We apply our algorithm to generate synthetic graphs that target real-world directed graphs (such as Twitter), and we demonstrate its benefits compared to state-of-the-art construction algorithms.

We consider the scenario of broadcasting for real-time applications, such as multi-player games and video streaming, and loss recovery via instantly decodable network coding. The source has a single time slot or multiple time slots to broadcast (potentially coded) recovery packet(s), and the application does not need to recover all losses. Our goal is to find packet(s) that are instantly decodable and maximize the number of lost packets that the users can recover. First, we show that this problem is equivalent to the unique coverage problem in the general case, and therefore, it is hard to approximate. Then, we consider the practical probabilistic scenario, where users have i.i.d. loss probability and the number of packets is either constant (video streaming), linear (multi-player games), or polynomial in the number of users, and we provide two polynomial-time (in the number of users) algorithms. For the single-slot case, we propose Max Clique, an algorithm that provably finds the optimal coded packet w.h.p. For the case where there is a small constant number of slots, we propose Multi-Slot Max Clique, an algorithm that provably finds a near-optimal solution w.h.p. when the number of packets is sufficiently large. The proposed algorithms are evaluated using both simulation and real network traces from an Android multi-player game. And they are shown to perform near optimally and to significantly outperform the state-of-the-art baselines.

Online social networks (OSNs) serve today as a platform for information dissemination. At the same time, mobile devices provide ubiquitous network access through the cellular infrastructure. In this paper, we develop mechanisms for minimizing the peak load of the cellular network due to information cascades spreading on social media. First, we exploit the social ties for predicting information dissemination and we propose Proactive Seeding-a technique for minimizing the peak load of cellular networks. Much of such a load is due to information cascades spreading in social media, and we address it by proactively pushing (“seeding”) content to selected users before they actually request it. We develop a family of algorithms that take as input information primarily about: (i) cascades on the OSN, (ii) the background traffic load in the cellular network, and (iii) the local connectivity among mobiles; the algorithms then select which nodes to seed and when. We prove that Proactive Seeding is optimal when the prediction of information cascades is perfect. We perform simulations driven by traces from Twitter and cellular networks and we find that Proactive Seeding reduces the peak cellular load by 20-50 percent. Then, we exploit the fact that there is correlation between social ties and physical proximity and we combine Proactive Seeding with device-to-device communication to further reduce the peak load.

We consider a group of mobile users, within proximity of each other, who are interested in watching the same online video. The common practice today is that each user downloads the video independently on her mobile device using her own cellular connection, which wastes access bandwidth and may also lead to poor video quality. We propose a novel cooperative system where each mobile device uses simultaneously two network interfaces: (i) cellular to connect to the video server and download parts of the video and (ii) WiFi to connect locally to all other devices in the group to exchange those parts. Devices cooperate to efficiently utilize all network resources and to adapt to varying wireless network conditions. In the local WiFi network, we exploit overhearing, which we further combine with network coding. The end result is savings in cellular bandwidth and improved user experience. We follow a complete approach, from theory to practice. First, we formulate the problem using a network utility maximization (NUM) framework, decompose the problem, and provide a distributed solution. Then, based on the structure of the NUM solution, we design a system called MicroCast, and we implement a prototype as an Android application. We provide both simulation results of the NUM solution and experimental evaluation. We demonstrate that the proposed approach brings significant performance benefits (namely, faster download on the order of the group size) without battery penalty.

Distributed storage codes have recently received a lot of attention in the community. Independently, another body of work has proposed integrity-checking schemes for cloud storage, none of which, however, is customized for coding-based storage or can efficiently support repair. In this work, we bridge the gap between these two currently disconnected bodies of work. We propose \ssr NC \mathchar"702D Audit, a novel cryptography-based remote data integrity-checking scheme, designed specifically for network-coding-based distributed storage systems. \ssr NC \mathchar"702D Audit combines, for the first time, the following desired properties: 1) efficient checking of data integrity; 2) efficient support for repairing failed nodes; and 3) protection against information leakage when checking is performed by a third party. The key ingredient of the design of \ssr NC \mathchar"702D Audit is a novel combination of \ssr SpaceMac, a homomorphic message authentication code (MAC) scheme for network coding, and \ssr NCrypt, a novel chosen-plaintext attack (CPA) secure encryption scheme that preserves the correctness of \ssr SpaceMac. Our evaluation of \ssr NC \mathchar"702D Audit based on a real Java implementation shows that the proposed scheme has significantly lower overhead compared to the state-of-the-art schemes for both auditing and repairing of failed nodes.

Ride-sharing systems have the potential to match travelers with similar itineraries and time schedules, and to bring significant benefits to individual users and the city as a whole. However, this is a challenging task, since users' requests are not known in advance and they become available a few minutes before departure. In this paper, we design an online ride sharing system, where drivers and passengers send their requests for a ride in advance, possibly on a short notice. Our design is efficient and optimal. This is achieved by dividing the system into two components: the constraint satisfier and the matching module. The constraint satisfier takes as input the spatio-temporal constraints of drivers and passengers and provides feasible (driver, passenger) pairs in real time, and the matching module takes as input the feasible pairs and provides a maximum cardinality matching of drivers and passengers. Our preliminary evaluation shows that the constraint satisfier can resolve the most expensive queries (matching of passenger to en-route drivers) in 2 seconds (on average), while the matching module can achieve a matching ratio of 78% when the offline upper-bound is 80%.

In networking research, it is often desirable to generate synthetic graphs with certain properties. In this paper, we present a new algorithm, 2K_Simple, for exact construction of simple graphs with a target joint degree matrix (JDM). We prove that the algorithm constructs exactly the target JDM and that its running time is linear in the number of edges. Furthermore, we show that the algorithm poses less constraints on the graph structure than previous state-of-the-art construction algorithms. We exploit this flexibility to extend 2K_Simple and design two algorithms that achieve additional network properties on top of the exact target JDM. In particular, 2K_Simple_Clustering produces simple graphs with a target JDM and average clustering coefficient close to a target, while 2K_Simple_Attributes produces exactly simple graphs with a target JDM and joint occurrence of node attribute pairs. We exhaustively evaluate our algorithms through simulation for small graphs, and we also demonstrate their benefits in generating graphs that resemble real-world social networks in terms of accuracy and speed; we reduce the running time by orders of magnitudes compared to previous approaches that rely on Monte Carlo Markov Chains.

Mobile devices play an essential role in the Internet today, and there is an increasing interest in using them as a vantage point for network measurement from the edge. At the same time, these devices store personal, sensitive information, and there is a growing number of applications that leak it. We propose AntMonitor-- the first system of its kind that supports (i) collection of large-scale, semantic-rich network traffic in a way that respects users' privacy preferences and (ii) detection and prevention of leakage of private information in real time. The first property makes AntMonitor a powerful tool for network researchers who want to collect and analyze large-scale yet fine-grained mobile measurements. The second property can work as an incentive for using AntMonitor and contributing data for analysis. As a proof-of-concept, we have developed a prototype of AntMonitor, deployed it to monitor 9 users for 2 months, and collected and analyzed 20 GB of mobile data from 151 applications. Preliminary results show that fine-grained data collected from AntMonitor could enable application classification with higher accuracy than state-of-the-art approaches. In addition, we demonstrated that AntMonitor could help prevent several apps from leaking private information over unencrypted traffic, including phone numbers, emails, and device identifiers.

The goal of this paper is to infer features of urban ecology (i.e., social and economic activities, and social interaction) from spatiotemporal cell phone activity data. We present a novel approach that consists of (i) time series decomposition of the aggregate cell phone activity per unit area using spectral methods, (ii) clustering of areal units with similar activity patterns, and (ii) external validation using a ground truth data set we collected from municipal and online sources. The key to our approach is the spectral decomposition of the original cell phone activity series into seasonal communication series (SCS) and residual communication series (RCS). The former captures regular patterns of socio-economic activity within an area and can be used to segment a city into distinct clusters. RCS across areas enables the detection of regions that are subject to mutual social influence and of regions that are in direct communication contact. The RCS and SCS thus provide distinct probes into the structure and dynamics of the urban environment, both of which can be obtained from the same underlying data. We illustrate the effectiveness of our methodology by applying it to aggregate Call Description Records (CDRs) from the city of Milan.

We consider the problem of network coding across three unicast sessions over a directed acyclic graph, where the sender and receiver of each unicast session are both connected to the network via a single edge of unit capacity. We consider a network model in which the middle of the network can only perform random linear network coding, and restrict our approaches to precoding-based linear schemes, where the senders use precoding matrices to encode source symbols. We adapt a precoding-based interference alignment technique, originally developed for the wireless interference channel, to construct a precoding-based linear scheme, which we refer to as precoding-based network alignment scheme (PBNA). A primary difference between this setting and the wireless interference channel is that the network topology can introduce dependencies among the elements of the transfer matrix, which we refer to as coupling relations, and can potentially affect the achievable rate of PBNA. We identify all these coupling relations and interpret them in terms of network topology. We then present polynomial-time algorithms to check the presence of these coupling relations in a particular network. Finally, we show that, depending on the coupling relations present in the network, the optimal symmetric rate achieved by precoding-based linear scheme can take only three possible values, all of which can be achieved by PBNA.

This paper assesses the potential of ride-sharing for reducing traffic in a city -- based on mobility data extracted from 3G Call Description Records (CDRs), for the cities of Madrid and Barcelona (BCN), and from OSNs, such as Twitter and Foursquare (FSQ), collected for the cities of New York (NY) and Los Angeles (LA). First, we analyze these data sets to understand mobility patterns, home and work locations, and social ties between users. Then, we develop an efficient algorithm for matching users with similar mobility patterns, considering a range of constraints, including social distance. The solution provides an upper bound to the potential decrease in the number of cars in a city that can be achieved by ride-sharing. Our results indicate that this decrease can be as high as 31%, when users are willing to ride with friends of friends.

In this paper, we consider the problem of multiple unicast sessions over a directed acyclic graph. It is well known that linear network coding is insufficient for achieving the capacity region, in the general case. However, there exist networks for which routing is sufficient to achieve the whole rate region, and we refer to them as routing-optimal networks. We identify a class of routing-optimal networks, which we refer to as information-distributive networks, defined by three topological features. Due to these features, for each rate vector achieved by network coding, there is always a routing scheme such that it achieves the same rate vector, and the traffic transmitted through the network is exactly the information transmitted over the cut-sets between the sources and the sinks in the corresponding network coding scheme. We present examples of information-distributive networks, including some examples from (1) index coding and (2) from a single unicast session with hard deadline constraint.

In this paper, we are interested in improving the performance of TCP flows over wireless networks with a given constructive intersession network coding scheme. We are motivated by the observation that TCP does not fully exploit the potential of the underlying network coding opportunities. In order to improve the performance of TCP flows over coded wireless networks, without introducing changes to TCP itself, we propose a network-coding aware queue management scheme (NCAQM) that is implemented at intermediate network coding nodes and bridges the gap between network coding and TCP rate control. The design of NCAQM is grounded on the network utility maximization (NUM) framework and includes the following mechanisms. NCAQM: 1) stores coded packets at intermediate nodes in order to use the buffer space more efficiently; 2) determines what fraction of the flows should be coded together; and 3) drops packets at intermediate nodes so that it matches the rates of parts of different TCP flows that are coded together. We demonstrate, via simulation, that NCAQM significantly improves TCP throughput compared to TCP over baseline queue management schemes.

Understanding network structure and having access to realistic graphs plays a central role in computer and social networks research. In this paper, we propose a complete, practical methodology for generating graphs that resemble a real graph of interest. The metrics of the original topology we target to match are the joint degree distribution (JDD) and the degree-dependent average clustering coefficient (c̅(k)). We start by developing efficient estimators for these two metrics based on a node sample collected via either independence sampling or random walks. Then, we process the output of the estimators to ensure that the target metrics are realizable. Finally, we propose an efficient algorithm for generating topologies that have the exact target JDD and a c̅(k) close to the target. Extensive simulations using real-life graphs show that the graphs generated by our methodology are similar to the original graph with respect to, not only the two target metrics, but also a wide range of other topological metrics. Furthermore, our generator is order of magnitudes faster than state-of-the-art techniques.

Network tomography aims at inferring internal network characteristics based on measurements at the edge of the network. In loss tomography, in particular, the characteristic of interest is the loss rate of individual links and multicast and/or unicast end-to-end probes are typically used. Independently, recent advances in network coding have shown that there are advantages from allowing intermediate nodes to process and combine, in addition to just forward, packets. In this paper, we study the problem of loss tomography in networks with network coding capabilities. We design a framework for estimating link loss rates, which leverages network coding capabilities, and we show that it improves several aspects of tomography, including the identifiability of links, the trade-off between estimation accuracy and bandwidth efficiency, and the complexity of probe path selection. We discuss the cases of inferring link loss rates in a tree topology and in a general topology. In the latter case, the benefits of our approach are even more pronounced compared to standard techniques but we also face novel challenges, such as dealing with cycles and multiple paths between sources and receivers. Overall, this work makes the connection between active network tomography and network coding.

While every network node only relays messages in a traditional communication system, the recent network coding (NC) paradigm proposes to implement simple in-network processing with packet combinations in the nodes. NC extends the concept of “encoding” a message beyond source coding (for compression) and channel coding (for protection against errors and losses). It has been shown to increase network throughput compared to traditional networks implementation, to reduce delay and to provide robustness to transmission errors and network dynamics. These features are so appealing for multimedia applications that they have spurred a large research effort towards the development of multimedia-specific NC techniques. This paper reviews the recent work in NC for multimedia applications and focuses on the techniques that fill the gap between NC theory and practical applications. It outlines the benefits of NC and presents the open challenges in this area. The paper initially focuses on multimedia-specific aspects of network coding, in particular delay, in-network error control, and media-specific error control. These aspects permit to handle varying network conditions as well as client heterogeneity, which are critical to the design and deployment of multimedia systems. After introducing these general concepts, the paper reviews in detail two applications that lend themselves naturally to NC via the cooperation and broadcast models, namely peer-to-peer multimedia streaming and wireless networking.

Dealing with pollution attacks in inter-session network coding is challenging due to the fact that sources, in addition to intermediate nodes, can be malicious. In this work, we first define precisely corrupted packets in inter-session pollution based on the commitment of the source packets. We then propose three detection schemes: one hash-based and two MAC-based schemes: InterMacCPKand SpaceMacPM. InterMacCPKis the first multi-source homomorphic MAC scheme that supports multiple keys. Both MAC schemes can replace traditional MACs, e.g., HMAC, in networks that employ inter-session coding. All three schemes provide in-network detection, are collusion-resistant, and have very low online bandwidth and computation overhead.

Online social networks (OSNs) play an increasingly important role today in informing users about content. At the same time, mobile devices provide ubiquitous access to this content through the cellular infrastructure. In this paper, we exploit the fact that the interest in content spreads over OSNs, which makes it, to a certain extent, predictable. We propose Proactive Seeding-a technique for minimizing the peak load of cellular networks, by proactively pushing (“seeding”) content to selected users before they actually request it. We develop a family of algorithms that take as input information primarily about (i) cascades on the OSN and possibly about (ii) the background traffic load in the cellular network and (iii) the local connectivity among mobiles; the algorithms then select which nodes to seed and when. We prove that Proactive Seeding is optimal when the prediction of information cascades is perfect. In realistic simulations, driven by traces from Twitter and cellular networks, we find that Proactive Seeding reduces the peak cellular load by 20%-50%. Finally, we combine Proactive Seeding with techniques that exploit local mobile-to-mobile connections to further reduce the peak load.

We consider the problem of network coding across three unicast sessions over a directed acyclic graph, when each session has min-cut one. Previous work by Das et al. adapted a precoding-based interference alignment technique, originally developed for the wireless interference channel, specifically to this problem. We refer to this approach as precoding-based network alignment (PBNA). Similar to the wireless setting, PBNA asymptotically achieves half the minimum cut; different from the wireless setting, its feasibility depends on the graph structure. Das et al. provided a set of feasibility conditions for PBNA with respect to a particular precoding matrix. However, the set consisted of an infinite number of conditions, which is impossible to check in practice. Furthermore, the conditions were purely algebraic, without interpretation with regards to the graph structure. In this paper, we first prove that the set of conditions provided by Das. et al are also necessary for the feasibility of PBNA with respect to any precoding matrix. Then, using two graph-related properties and a degree-counting technique, we reduce the set to just four conditions. This reduction enables an efficient algorithm for checking the feasibility of PBNA on a given graph.

Video streaming is one of the increasingly popular, as well as demanding, applications on smartphones today. In this paper, we consider a group of smartphone users, within proximity of each other, who are interested in watching the same video from the Internet at the same time. The common practice today is that each user downloads the video independently using her own cellular connection, which often leads to poor quality.

In this work, we are interested in a scenario where a group of smartphone users, within proximity of each other, are interested in watching the same video at the same time. The default operation today is that each user with a cellular connection downloads the video independently from the server. However, each phone's individual cellular connection may not be sufficient for providing high video quality.

Intra-session network coding is inherently vulnerable to pollution attacks. In this paper, first, we introduce a novel homomorphic MAC scheme called SpaceMac, which allows an intermediate node to verify whether received packets belong to a specific subspace, even if the subspace is expanding over time. Then, we use SpaceMac as a building block to design a cooperative scheme that provides complete defense against pollution attacks: (i) it can detect polluted packets early at intermediate nodes, and (ii) it can identify the exact location of all, even colluding, attackers, thus making it possible to eliminate them. Our scheme is cooperative: parents and children of any node cooperate to detect any corrupted packets sent by the node, and nodes in the network cooperate with a central controller to identify the exact location of all attackers. We implement SpaceMac in both C/C++ and Java as a library, which we make publicly available. Our evaluation on both a PC and an Android device shows that the SpaceMac algorithms can be computed quickly and efficiently and that our cooperative defense scheme has low computation overhead and significantly lower communication overhead than those of state-of-the-art schemes.

In this paper, we consider the problem of blocking malicious traffic on the Internet via source-based filtering. In particular, we consider filtering via access control lists (ACLs): These are already available at the routers today, but are a scarce resource because they are stored in the expensive ternary content addressable memory (TCAM). Aggregation (by filtering source prefixes instead of individual IP addresses) helps reduce the number of filters, but comes also at the cost of blocking legitimate traffic originating from the filtered prefixes. We show how to optimally choose which source prefixes to filter for a variety of realistic attack scenarios and operators' policies. In each scenario, we design optimal, yet computationally efficient, algorithms. Using logs from Dshield.org, we evaluate the algorithms and demonstrate that they bring significant benefit in practice.

Has the behavior of spammers changed over the last few years? To answer this question, we conduct a study from three recent data sources. Specifically, we focus on the following broad questions: (a) how are email addresses harvested, (b) where is spam coming from, and (c) how does spam evolve over time. First, we discuss whether spammers still use email harvesting: 34% of the honeypot accounts we publicised received spam after 72 days on average. Interestingly, we find that simple email address obfuscation is quite effective against harvesting. Second, we identify significant skew in the spatial distribution of the origin of spam in both the IP-level and AS-level of granularity. We find that 20% of the active IPs are responsible for 80% of the total volume of spam and that 10% of the spamming ASes are responsible for the 90% of the volume. Finally, we study the temporal characteristics of the spamming IPs and find that spam activity has spread to new /8 subnetworks since 2006. Considering these spatio-temporal trends, the future of anti-spam is mixed: the current skewed spatial distribution of spam sources could be helpful in filtering spam, but the fact that spam sources are spreading in the IP space is a worrisome sign.

Phishing is an increasingly sophisticated method to steal personal user information using sites that pretend to be legitimate. In this paper, we take the following steps to identify phishing URLs. First, we carefully select lexical features of the URLs that are resistant to obfuscation techniques used by attackers. Second, we evaluate the classification accuracy when using only lexical features, both automatically and hand-selected, vs. when using additional features. We show that lexical features are sufficient for all practical purposes. Third, we thoroughly compare several classification algorithms, and we propose to use an online method (AROW) that is able to overcome noisy training data. Based on the insights gained from our analysis, we propose PhishDef, a phishing detection system that uses only URL names and combines the above three elements. PhishDef is a highly accurate method (when compared to state-of-the-art approaches over real datasets), lightweight (thus appropriate for online and client-side deployment), proactive (based on online classification rather than blacklists), and resilient to training data inaccuracies (thus enabling the use of large noisy training data).

In this work, we are interested in improving the performance of constructive network coding schemes in lossy wireless environments. We propose I2NC - an approach that combines inter-session and intra-session network coding and has two strengths. First, the error-correcting capabilities of intra-session network coding make our scheme resilient to loss. Second, redundancy allows intermediate nodes to operate without knowledge of the decoding buffers of their neighbors. Based only on the knowledge of the loss rates on the direct and overhearing links, intermediate nodes can make decisions for both intra-session (i.e., how much redundancy to add in each flow) and inter-session (i.e., what percentage of flows to code together) coding. Our approach is grounded on a network utility maximization (NUM) formulation of the problem. We propose two practical schemes, I2NC-state and I2NC-stateless, which mimic the structure of the NUM optimal solution. We also address the interaction of our approach with the transport layer. We demonstrate the benefits of our schemes through simulation in GloMoSim.

Our objective is to sample the node set of a large unknown graph via crawling, to accurately estimate a given metric of interest. We design a random walk on an appropriately defined weighted graph that achieves high efficiency by preferentially crawling those nodes and edges that convey greater information regarding the target metric. Our approach begins by employing the theory of stratification to find optimal node weights, for a given estimation problem, under an independence sampler. While optimal under independence sampling, these weights may be impractical under graph crawling due to constraints arising from the structure of the graph. Therefore, the edge weights for our random walk should be chosen so as to lead to an equilibrium distribution that strikes a balance between approximating the optimal weights under an independence sampler and achieving fast convergence. We propose a heuristic approach (stratified weighted random walk, or S-WRW) that achieves this goal, while using only limited information about the graph structure and the node properties. We evaluate our technique in simulation, and experimentally, by collecting a sample of Facebook college users. We show that S-WRW requires 13-15 times fewer samples than the simple re-weighted random walk (RW) to achieve the same estimation accuracy for a range of metrics.

State-of-the-art techniques for probability sampling of users of online social networks (OSNs) are based on random walks on a single social relation (typically friendship). While powerful, these methods rely on the social graph being fully connected. Furthermore, the mixing time of the sampling process strongly depends on the characteristics of this graph. In this paper, we observe that there often exist other relations between OSN users, such as membership in the same group or participation in the same event. We propose to exploit the graphs these relations induce, by performing a random walk on their union multigraph. We design a computationally efficient way to perform multigraph sampling by randomly selecting the graph on which to walk at each iteration. We demonstrate the benefits of our approach through (i) simulation in synthetic graphs, and (ii) measurements of Last.fm- an Internet website for music with social networking features. More specifically, we show that multigraph sampling can obtain a representative sample and faster convergence, even when the individual graphs fail, i.e., are disconnected or highly clustered.

Our goal in this paper is to develop a practical framework for obtaining a uniform sample of users in an online social network (OSN) by crawling its social graph. Such a sample allows to estimate any user property and some topological properties as well. To this end, first, we consider and compare several candidate crawling techniques. Two approaches that can produce approximately uniform samples are the Metropolis-Hasting random walk (MHRW) and a re-weighted random walk (RWRW). Both have pros and cons, which we demonstrate through a comparison to each other as well as to the "ground truth." In contrast, using Breadth-First-Search (BFS) or an unadjusted Random Walk (RW) leads to substantially biased results. Second, and in addition to offline performance assessment, we introduce online formal convergence diagnostics to assess sample quality during the data collection process. We show how these diagnostics can be used to effectively determine when a random walk sample is of adequate size and quality. Third, as a case study, we apply the above methods to Facebook and we collect the first, to the best of our knowledge, representative sample of Facebook users. We make it publicly available and employ it to characterize several key properties of Facebook.

Breadth First Search (BFS) is a widely used approach for sampling large graphs. However, it has been empirically observed that BFS sampling is biased toward high-degree nodes, which may strongly affect the measurement results. In this paper, we quantify and correct the degree bias of BFS. First, we consider a random graph RG(pk) with an arbitrary degree distribution pk. For this model, we calculate the node degree distribution expected to be observed by BFS as a function of the fraction f of covered nodes. We also show that, for RG(pk), all commonly used graph traversal techniques (BFS, DFS, Forest Fire, Snowball Sampling, RDS) have exactly the same bias. Next, we propose a practical BFS-bias correction procedure that takes as input a collected BFS sample together with the fraction f. Our correction technique is exact (i.e., leads to unbiased estimation) for RG(pk). Furthermore, it performs well when applied to a broad range of Internet topologies and to two large BFS samples of Facebook and Orkut networks.

In this paper, we study the problem of forecasting attack sources based on past attack logs from several contributors. We formulate this problem as an implicit recommendation system, and we propose a multi-level prediction model to solve it. Our model evaluates and combines various factors, namely: (i) attacker-victim history using time-series, (ii) attackers and/or victims interactions using neighborhood models and (iii) global patterns using singular value decomposition. We evaluate our combined method, referred to as Blacklisting Recommendation System (or BRS), on one month of logs from Dshield, and we demonstrate that it improves significantly the prediction rate over state-of-the-art methods as well as the robustness against poisoning attacks. Along the way, we analyze the Dshield dataset, and we reveal dominant patterns of malicious traffic.

In this paper, we study delay-optimized network coding for video streaming over wireless networks with network coding capabilities. It has been demonstrated that network coding can increase throughput in wireless networks, by mixing packets from different flows into a single packet, thus increasing the information content per transmission. However, network coding potential is not always fully exploited in this setting, because there may not be enough packets at intermediate nodes to do network coding due to bursty nature of transport protocols, packet losses, and difference in path delays. One way to deal with this problem is to delay packets at intermediate nodes in order to create more network coding opportunities. However, introducing large or varying delays eventually hurts video traffic, which requires low delay and delay jitter. In this paper, we study this tradeoff in coded wireless networks, and we propose a packet delaying scheme at intermediate nodes to maximize video quality.

With more than 250 million active users, Facebook (FB) is currently one of the most important online social networks. Our goal in this paper is to obtain a representative (unbiased) sample of Facebook users by crawling its social graph. In this quest, we consider and implement several candidate techniques. Two approaches that are found to perform well are the Metropolis-Hasting random walk (MHRW) and a re-weighted random walk (RWRW). Both have pros and cons, which we demonstrate through a comparison to each other as well as to the "ground-truth" (UNI - obtained through true uniform sampling of FB userIDs). In contrast, the traditional Breadth-First-Search (BFS) and Random Walk (RW) perform quite poorly, producing substantially biased results. In addition to offline performance assessment, we introduce online formal convergence diagnostics to assess sample quality during the data collection process. We show how these can be used to effectively determine when a random walk sample is of adequate size and quality for subsequent use (i.e., when it is safe to cease sampling). Using these methods, we collect the first, to the best of our knowledge, unbiased sample of Facebook. Finally, we use one of our representative datasets, collected through MHRW, to characterize several key properties of Facebook.

A widely used defense practice against malicious traffic on the Internet is through blacklists: lists of prolific attack sources are compiled and shared. The goal of blacklists is to predict and block future attack sources. Existing blacklisting techniques have focused on the most prolific attack sources and, more recently, on collaborative blacklisting. In this paper, we formulate the problem of forecasting attack sources (also referred to as "predictive blacklisting") based on shared attack logs, as an implicit recommendation system. We compare the performance of existing approaches against the upper bound for prediction and we demonstrate that there is much room for improvement. Inspired by the recent NetFlix competition, we propose a multi-level collaborative filtering model that is adjusted and tuned specifically for the attack forecasting problem. Our model captures and combines various factors namely: attacker-victim history (using time-series) and attackers and/or victims interactions (using neighborhood models). We evaluate our combined method on one month of logs from Dshield.org and demonstrate that it improves significantly the prediction rate over state-of-the-art methods as well as the robustness against poisoning attacks.

This paper considers the problem of network coding for multiple unicast connections in networks represented by directed acyclic graphs. The concept of interference alignment, traditionally used in interference networks, is extended to analyze the performance of linear network coding in this setup and to provide a systematic code design approach. It is shown that, for a broad class of three-source three-destination unicast networks, a rate corresponding to half the individual source-destination min-cut is achievable via alignment strategies.

Media flows coexist with TCP-based data traffic on the Internet and are required to be TCP-friendly. The TCP protocol slowly increases its sending rate until episodes of congestion occur, and then it quickly reduces its rate to remove congestion. However, media flows can be sensitive to even brief episodes of congestion. In this paper, we are interested in protecting media flows from TCP-induced congestion while maintaining their TCP friendliness. In particular, we consider media flows carried over the TCP-Friendly Rate Control (TFRC) protocol and we design algorithms that dynamically adapt the level of forward error correction (FEC) based on the congestion state of the network. To this end, first, we investigate the loss and delay characteristics of TFRC flows in several TCP-induced congestion scenarios, and we develop novel predictors of loss events based on packet delay information. Second, we use these predictors to dynamically adapt the level of FEC protection based on the predicted level of congestion. We show that this technique can significantly improve the overhead versus reliability trade-off compared to fixed FEC. Third, we select the FEC and original media packets within each FEC block, in a rate-distortion optimized way, and we show that this technique significantly improves media quality.

In this paper, we study rate control and scheduling over wireless networks with intersession network coding, as a utility maximization problem. We demonstrate that making rate control and scheduling aware of the underlying network coding increases throughput. The key intuition is that network coding introduces new network coded flows and eventually new conflicts between nodes, which should be taken into account both in rate control and in scheduling. We compare the network coding-aware to the network coding-unaware schemes in two cases: (i) optimal control and (ii) practical, suboptimal control. Our main goal is to make the case for network coding-aware rate control and scheduling, via simulation of representative examples. Along the way, we also propose a practical scheme that approximates the optimal control.

How can we protect the network infrastructure from malicious traffic, such as scanning, malicious code propagation, and distributed denial-of-service (DDoS) attacks? One mechanism for blocking malicious traffic is filtering: access control lists (ACLs) can selectively block traffic based on fields of the IP header. Filters (ACLs) are already available in the routers today but are a scarce resource because they are stored in expensive ternary content addressable memory (TCAM). In this paper, we develop, for the first time, a framework for studying filter selection as a resource allocation problem. Within this framework, we study four practical cases of source address/prefix filtering, which correspond to different attack scenarios and operator's policies. We show that filter selection optimization leads to novel variations of the multidimensional knapsack problem and we design optimal, yet computationally efficient, algorithms to solve them. We also evaluate our approach using data from Dshield.org and demonstrate that it brings significant benefits in practice. Our set of algorithms is a building block that can be immediately used by operators and manufacturers to block malicious traffic in a cost-efficient way.

In this paper, we study video streaming over wireless networks with network coding capabilities. We build upon recent work, which demonstrated that network coding can increase throughput over a broadcast medium, by mixing packets from different flows into a single packet, thus increasing the information content per transmission. Our key insight is that, when the transmitted flows are video streams, network codes should be selected so as to maximize not only the network throughput but also the video quality. We propose video-aware opportunistic network coding schemes that take into account both the decodability of network codes by several receivers and the importance and deadlines of video packets. Simulation results show that our schemes significantly improve both video quality and throughput. This work is a first step towards content-aware network coding.

Media streaming over wireless links is a challenging problem due to both the unreliable, time-varying nature of the wireless channel and the stringent delivery requirements of media traffic. In this paper, we use joint control of packet scheduling at the transmitter and content-aware playout at the receiver, so as to maximize the quality of media streaming over a wireless link. Our contributions are twofold. First, we formulate and study the problem of joint scheduling and playout control in the framework of Markov decision processes. Second, we propose a novel content-aware adaptive playout control, that takes into account the content of a video sequence, and in particular the motion characteristics of different scenes. We find that the joint scheduling and playout control can significantly improve the quality of the received video, at the expense of only a small amount of playout slowdown. Furthermore, the content-aware adaptive playout places the slowdown preferentially in the low-motion scenes, where its perceived effect is lower.

Network tomography infers internal network characteristics by sending and collecting probe packets from the network edge. Traditional tomographic techniques for general topologies typically use a mesh of multicast trees and/or unicast paths to cover the entire graph, which is suboptimal from the point of view of bandwidth efficiency and estimation accuracy. In this paper, we investigate an active probing method for link loss inference in a general topology, where multiple sources and receivers are used and intermediate nodes are equipped with network coding, in addition to unicast and multicast, capabilities. With our approach, each link is traversed by exactly one packet, which is in general a linear combination of the original probes. The receivers infer the loss rate on all links by observing not only the number but also the contents of the received probes. In this paper: (i) we propose an orientation algorithm that creates an acyclic graph with the maximum number of identifiable edges (ii) we define probe combining coding schemes and discuss some of their properties and (iii) we present simulation results over realistic topologies using Belief-Propagation (BP) algorithms.

Media streaming applications over wireless links face various challenges, due to both the nature of the wireless channel and the stringent delivery requirements of media traffic. In this paper, we seek to improve the performance of media streaming over an interference-limited wireless link, by using appropriate transmission and playout control. In particular, we choose both the power at the transmitter and the playout scheduling at the receiver, so as to minimize the power consumption and maximize the media playout quality. We formulate the problem using a dynamic programming approach, and study the structural properties of the optimal solution. We further develop a justified, low-complexity heuristic that achieves significant performance gain over benchmark systems. In particular, our joint power-playout heuristic outperforms: 1) the optimal power control policy in the regime where power is most important and 2) the optimal playout control policy in the regime where media (playout) quality is most important; furthermore, this heuristic has only a slight performance loss as compared to the optimal joint power-playout control policy over the entire range of the investigation

Portable devices (such as personal digital assistants and laptops with wireless connectivity) are becoming ubiquitous. As their functionality and capabilities increase, their energy consumption requirements also increase. Yet, these devices have to operate on limited batteries. In order to maximize the battery lifetime, it is necessary to optimize the use of energy at various components of such a device. In this paper, we consider a single portable device operating on a limited battery that transmits information over an interference-limited wireless channel. We seek to optimize the power consumption on the communication radio in this device, by controlling both the operation mode and the transmission power. We model the general problem using dynamic programming, obtain the optimal solutions for insightful special cases and explore various design tradeoffs. Our work provides an analytical framework for stochastic modeling and optimization of energy spent for communications in battery-operated portable devices.

Media streaming over wireless links is a challenging problem due to both the unreliable, time-varying nature of the wireless channel and the stringent delivery requirements of media traffic. In this paper, we use joint control of packet scheduling at the transmitter and content-aware playout at the receiver, so as to maximize the quality of media streaming over a wireless link. Our contributions are twofold. First, we formulate and study the problem of joint scheduling and playout control within a dynamic programming framework. Second, we propose a novel content-aware playout control, that takes into account the content of a video sequence, and in particular the motion characteristics of different scenes. We find that the joint scheduling and playout control can significantly improve the quality of the received video, at the expense of only a small amount of playout slowdown. Furthermore, thanks to the content-aware playout, the slowdown takes place mainly in the low-motion scenes, where its perceived effect is limited

Both data and multimedia applications over the Internet are expected to perform some kind of congestion control, typically using packet loss as an indication for congestion. However, when packets are lost due to wireless errors, decreasing the rate unnecessarily harms the application's performance. The paper proposes to use an in-band notification mechanism, called WiSE (wireless signaling via ECN), to distinguish wireless errors from congestion losses and improve the performance of rate-controlled video streamed over wireless links. A WiSE agent on the wireless network identifies wireless errors and piggy-backs this information onto other video packets. The WiSE-aware video source can benefit from this notification (1) by avoiding unnecessary decreases in the sending rate in response to wireless errors, and (2) by accurately adjusting the error resilience for the wireless link. Simulations demonstrate that WiSE provides a significant improvement in video quality over a wide range of conditions.

We analyze IS-IS routing updates from sprint's IP network to characterize failures that affect IP connectivity. Failures are first classified based on probable causes such as maintenance activities, router-related and optical layer problems. Key temporal and spatial characteristics of each class are analyzed and, when appropriate, parameterized using well-known distributions. Our results indicate that 20% of all failures is due to planned maintenance activities. Of the unplanned failures, almost 30% are shared by multiple links and can be attributed to router-related and optical equipment-related problems, while 70% affect a single link at a time. Our classification of failures according to different causes reveals the nature and extent of failures in today's IP backbones. Furthermore, our characterization of the different classes can be used to develop a probabilistic failure model, which is important for various traffic engineering problems.

As the Internet evolves into a ubiquitous communication infrastructure and provides various services including telephony, it will be expected to meet the quality standards achieved in the public switched telephone network. Our objective in this paper is to assess to what extent today's Internet meets this expectation. Our assessment is based on delay and loss measurements taken over wide-area backbone networks and uses subjective voice quality measures capturing the various impairments incurred. First, we compile the results of various studies into a single model for assessing the voice-over-IP (VoIP) quality. Then, we identify different types of typical Internet paths and study their VoIP performance. For each type of path, we identify those characteristics that affect the VoIP perceived quality. Such characteristics include the network loss and the delay variability that should be appropriately handled by the playout scheduling at the receiver. Our findings indicate that although voice services can be adequately provided by some ISPs, a significant number of Internet backbone paths lead to poor performance.

As the Internet evolves into a ubiquitous communication infrastructure and provides various services including telephony, it has to stand up to the toll quality standards set by traditional telephone companies. Our objective is to assess to what extent today's Internet meets this expectation. Our assessment is based on delay and loss measurements taken over wide-area backbone networks, considers realistic VoIP scenarios and uses quality measures appropriate for voice. Our findings indicate that although voice services can be adequately provided by some ISPs, a significant number of paths lead to poor performance even for excellent VoIP end-systems. This makes a strong case for special handling of voice traffic on those paths. Even on the good paths, rare loss events can occasionally cause perceptible degradation of voice quality. Finally, the appropriate choice of the playout buffer scheme for each path was found to be of critical importance for the perceived quality.

Traditionally the performance of a distributed system or a telecommunications network is taken into account only in the last steps of its design and it is seen as a final improvement. Recent attempts to incorporate performance considerations in the mainstream design rely on the development of a functional model consisting of entities that must be optimally distributed over a network of physical nodes. The optimal allocation is environment sensitive and probable different environments must be taken into account. Functional entities that are likely to be grouped together in different environments compose the so-called network entities. In this paper the problem of optimally composing network entities is examined. Different variations of the problem have been studied.