Microsoft recently introduced Azure Synapse Analytics, which offers an integrated experience across data ingestion, storage, and querying in Apache Spark and T-SQL over data in the lake, including files and warehouse tables. In this paper, we present our experiences with designing and implementing Hyperspace, the indexing subsystem underlying Synapse. Hyperspace enables users to build multiple types of secondary indexes on their data, maintain them through a multi-user concurrency model, and leverage them automatically---without any change to their application code---for query/workload acceleration. Many requirements of Hyperspace are based on feedback from several enterprise customers. We present the details of Hyperspace's underlying design, the user-facing APIs, its concurrency control protocol for index access, its index-aware query processing techniques, and its maintenance mechanisms for handling index updates. Evaluations over standard industry benchmarks and real customer workloads show that Hyperspace can accelerate query execution by up to 10x and in certain real-world workloads, even up to two orders of magnitude.

Helios is a distributed, highly-scalable system used at Microsoft for flexible ingestion, indexing, and aggregation of large streams of real-time data that is designed to plug into relational engines. The system collects close to a quadrillion events indexing approximately 16 trillion search keys per day from hundreds of thousands of machines across tens of data centers around the world. Helios use cases within Microsoft include debugging/diagnostics in both public and government clouds, workload characterization, cluster health monitoring, deriving business insights and performing impact analysis of incidents in other large-scale systems such as Azure Data Lake and Cosmos. Helios also serves as a reference blueprint for other large-scale systems within Microsoft. We present the simple data model behind Helios, which offers great flexibility and control over costs, and enables the system to asynchronously index massive streams of data. We also present our experiences in building and operating Helios over the last five years at Microsoft.

The task of Named Entity Recognition (NER) has been well studied under high-resource conditions (e.g., extracting named mentions of PERSON, ORGANIZATION and LOCATION from news articles). However, there are very few studies of the NER task for open-domain collections and in low-resource settings. We focus on NER for low-resource collections, in which any entity types of practical interest to the users of the system must be supported. We try to achieve this with a low cost of annotation of data from the target domain/collection. We propose an entity recognition framework that combines active learning and conditional random fields (CRF), and which provides the flexibility to define new entity types as needed by the users. Our experiments on a help & support corpus show that the system can achieve F1 measure of 0.77 by relying on only 100 manually-annotated sentences.

Stream-processing workloads and modern shared cluster environments exhibit high variability and unpredictability. Combined with the large parameter space and the diverse set of user SLOs, this makes modern streaming systems very challenging to statically configure and tune. To address these issues, in this paper we investigate a novel control-plane design, Chi, which supports continuous monitoring and feedback, and enables dynamic re-configuration. Chi leverages the key insight of embedding control-plane messages in the data-plane channels to achieve a low-latency and flexible control plane for stream-processing systems. Chi introduces a new reactive programming model and design mechanisms to asynchronously execute control policies, thus avoiding global synchronization. We show how this allows us to easily implement a wide spectrum of control policies targeting different use cases observed in production. Large-scale experiments using production workloads from a popular cloud provider demonstrate the flexibility and efficiency of our approach.

The difficulty of large-scale monitoring of app markets affects our understanding of their dynamics. This is particularly true for dimensions such as app update frequency, control and pricing, the impact of developer actions on app popularity, as well as coveted membership in top app lists. In this paper, we perform a detailed temporal analysis on two datasets we have collected from the Google Play Store, one consisting of 160000 apps and the other of 87223 newly released apps. We have monitored and collected data about these apps over more than six months. Our results show that a high number of these apps have not been updated over the monitoring interval. Moreover, these apps are controlled by a few developers that dominate the total number of app downloads. We observe that infrequently updated apps significantly impact the median app price. However, a changing app price does not correlate with the download count. Furthermore, we show that apps that attain higher ranks have better stability in top app lists. We show that app market analytics can help detect emerging threat vectors, and identify search rank fraud and even malware. Further, we discuss the research implications of app market analytics on improving developer and user experiences.

Numerous routing protocols have been designed and subjected to model checking and simulations. However, model checking the design or testing the simulator-based prototype of a protocol does not guarantee that the implementation is free of bugs and vulnerabilities. Testing implementations beyond their basic functionality (also known as adversarial testing) can increase protocol robustness. We focus on automated adversarial testing of real-world implementations of wireless routing protocols. In our previous work we created Turret, a platform that uses a network emulator and virtualization to test unmodified binaries of general distributed systems. Based on Turret, we create Turret-W designed specifically for wireless routing protocols. Turret-W includes new functionalities such as differentiating routing messages from data messages to enable evaluation of attacks on the control plane and the data plane separately, support for several additional protocols (e.g., those that use homogeneous/heterogenous packet formats, those that run on geographic forwarding (not just IP), those that operate at the data link layer instead of the network layer), support for several additional attacks (e.g., replay attacks) and for establishment of adversarial side-channels that allow for collusion. Turret-W can test not only general routing attacks, but also wireless specific attacks such as wormhole. Using Turret-W on publicly available implementations of five representative routing protocols, we (re-)discovered 37 attacks and 3 bugs. All these bugs and 5 of the total attacks were not previously reported to the best of our knowledge.

Recently emerged app markets provide a centralized paradigm for software distribution in smartphones. The difficulty of massively collecting app data has led to a lack a good understanding of app market dynamics. In this paper we seek to address this problem, through a detailed temporal analysis of Google Play, Google's app market. We perform the analysis on data that we collected daily from 160,000 apps, over a period of six months in 2012. We report often surprising results. For instance, at most 50% of the apps are updated in all categories, which significantly impacts the median price. The average price does not exhibit seasonal monthly trends and a changing price does not show any observable correlation with the download count. In addition, productive developers are not creating many popular apps, but a few developers control apps which dominate the total number of downloads. We discuss the research implications of such analytics on improving developer and user experiences, and detecting emerging threat vectors.

As the cloud computing market continues to grow, the cloud platform is becoming an attractive target for attackers to disrupt services and steal data, and to compromise resources to launch attacks. In this paper, using three months of NetFlow data in 2013 from a large cloud provider, we present the first large-scale characterization of inbound attacks towards the cloud and outbound attacks from the cloud. We investigate nine types of attacks ranging from network-level attacks such as DDoS to application-level attacks such as SQL injection and spam. Our analysis covers the complexity, intensity, duration, and distribution of these attacks, highlighting the key challenges in defending against attacks in the cloud. By characterizing the diversity of cloud attacks, we aim to motivate the research community towards improving future security solutions for cloud systems.

We introduce ConfSeer, an automated system that detects potential configuration issues or deviations from identified best practices by leveraging a knowledge base (KB) of technical solutions. The intuition is that these KB articles describe the configuration problems and their fixes so if the system can accurately understand them, it can automatically pinpoint both the errors and their resolution. Unfortunately, finding an accurate match is difficult because (a) the KB articles are written in natural language text, and (b) configuration files typically contain a large number of parameters with a high value range. Thus, expert-driven manual troubleshooting is not scalable. While there are several state-of-the-art techniques proposed for individual tasks such as keyword matching, concept determination and entity resolution, none offer a practical end-to-end solution to detect problems in machine configurations. In this paper, we describe our experiences building ConfSeer using a novel combinations of ideas from natural language processing, information retrieval and interactive learning. ConfSeer powers the recommendation engine behind Microsoft Operations Management Suite that proposes fixes for software configuration errors. The system has been running in production for about a year to proactively find misconfigurations on tens of thousands of servers. Our evaluation of ConfSeer against an expert-defined rule-based commercial system, an expert survey and web search engines shows that it achieves 80%-97.5% accuracy and incurs low runtime overheads.

An accurate Internet topology graph is important in many areas of networking, from understanding ISP business relationships to diagnosing network anomalies. Most Internet mapping efforts have derived the network structure, at the level of interconnected autonomous systems (ASes), from a rather limited set of vantage points. In this paper, we argue that a promising approach to revealing the hidden areas of the Internet topology is through active measurement from an observation platform that scales with the growing Internet. By leveraging measurements performed by an extension to a popular P2P system, we show that this approach indeed exposes significant new topological information. Our study is based on traceroute measurements from more than 992,000 IPs in over 3,700 ASes distributed across the Internet hierarchy, many in regions of the Internet not covered by publicly available path information. To address this issue we develop heuristics that identify 23,914 new AS links not visible in the publicly-available BGP data-12.86 percent more customer-provider links and 40.99 percent more peering links, than previously reported. We validate our heuristics using data from a tier-1 ISP, and show that they successfully filter out all false links introduced by public IP-to-AS mapping. We analyze properties of the Internet graph that includes these new links and characterize why they are missing. Finally, we have made the identified set of links and their inferred relationships publicly available.

One of Android's main defense mechanisms against malicious apps is a risk communication mechanism which, before a user installs an app, warns the user about the permissions the app requires, trusting that the user will make the right decision. This approach has been shown to be ineffective as it presents the risk information of each app in a “stand-alone” fashion and in a way that requires too much technical knowledge and time to distill useful information. We discuss the desired properties of risk signals and relative risk scores for Android apps in order to generate another metric that users can utilize when choosing apps. We present a wide range of techniques to generate both risk signals and risk scores that are based on heuristics as well as principled machine learning techniques. Experimental results conducted using real-world data sets show that these methods can effectively identify malware as very risky, are simple to understand, and easy to use.

Geosocial networks (GSNs) extend classic online social networks with the concept of location. Users can report their presence at venues through “check-ins” and, when certain check-in sequences are satisfied, users acquire special status in the form of “badges”. We first show that this innovative functionality is popular in Foursquare, a prominent GSN. Furthermore, we address the apparent tension between privacy and correctness, where users are unable to prove having satisfied badge conditions without revealing the corresponding time and location of their check-in sequences. To this end, we propose several privacy preserving protocols that enable users to prove having satisfied the conditions of several badge types. Specifically, we introduce (i) GeoBadge and T-Badge, solutions for acquiring location badges, (ii) FreqBadge, for mayorship badges, (iii) e-Badge, for proving various expertise levels and (iv) MPBadge, for accumulating multi-player badges. We show that a Google Nexus One smartphone is able to perform tens of badge proofs per minute while a provider can support hundreds of million of check-ins and badge verifications per day.

Some errors were introduced while preparing the final source files for the original article published in August 2013 in the 9,4 issue of TOMM. The errata are summarized here below together with attached revised pages showing the corrected elements indicated in red. The full CVoR (Corrected Version of Record) can be accessed in the ACM Digital Library, DOI=http://dx.doi.org/10.1145/2501643.2501652 —Page 8: New Figure 6(a) —Page 16: New Figures 8(a), 8(b), and 9(a) —Page 17: New Figure 10(b) —Page 18: New Figures 11 and 12; corrected text reference —Page 19: Final sentence deleted

The growing demand for always-on and low-latency cloud services is driving the creation of globally distributed datacenters. A major factor affecting service availability is reliability of the network, both inside the datacenters and wide-area links connecting them. While several research efforts focus on building scale-out datacenter networks, little has been reported on real network failures and how they impact geo-distributed services. This paper makes one of the first attempts to characterize intra-datacenter and inter-datacenter network failures from a service perspective. We describe a large-scale study analyzing and correlating failure events over three years across multiple datacenters and thousands of network elements such as Access routers, Aggregation switches, Top-of-Rack switches, and long-haul links. Our study reveals several important findings on (a) the availability of network domains, (b) root causes, (c) service impact, (d) effectiveness of repairs, and (e) modeling failures. Finally, we outline steps based on existing network mechanisms to improve service availability.

Network appliances or middleboxes such as firewalls, intrusion detection and prevention systems (IDPS), load balancers, and VPNs form an integral part of datacenters and enterprise networks. Realizing their importance and shortcomings, the research community has proposed software implementations, policy-aware switching, consolidation appliances, moving middlebox processing to VMs, end hosts, and even offloading it to the cloud. While such efforts can use middlebox failure characteristics to improve their reliability, management, and cost-effectiveness, little has been reported on these failures in the field. In this paper, we make one of the first attempts to perform a large-scale empirical study of middlebox failures over two years in a service provider network comprising thousands of middleboxes across tens of datacenters. We find that middlebox failures are prevalent and they can significantly impact hosted services. Several of our findings differ in key aspects from commonly held views: (1) Most failures are grey dominated by connectivity errors and link flaps that exhibit intermittent connectivity, (2) Hardware faults and overload problems are present but they are not in majority, (3) Middleboxes experience a variety of misconfigurations such as incorrect rules, VLAN misallocation and mismatched keys, and (4) Middlebox failover is ineffective in about 33\% of the cases for load balancers and firewalls due to configuration bugs, faulty failovers and software version mismatch. Finally, we analyze current middlebox proposals based on our study and discuss directions for future research.

As cloud services continue to grow, a key requirement is delivering an 'always-on' experience to end users. Of the several factors affecting service availability, network failures in the hosting datacenters have received little attention. This paper presents a preliminary analysis of intra-datacenter and inter-datacenter network failures from a service perspective. We describe an empirical study analyzing and correlating network failure events over an year across multiple datacenters in a service provider. Our broader goal is to outline steps leveraging existing network mechanisms to improve end-to-end service availability.

We focus on automated adversarial testing of real-world implementations of wireless routing protocols. We extend an existing platform, Turret, designed for general distributed systems, to address the specifics of wireless routing protocols. Specifically, we add functionality to differentiate routing messages from data messages and support wireless specific attacks such as blackhole and wormhole, or routing attacks such as replay attacks. The extended platform, Turret-W, uses a network emulator to create reproducible network conditions and virtualization to run unmodified binaries of wireless protocol implementations. Using the platform on publicly available implementations of two representative routing protocols we (re-)discovered 14 attacks and 3 bugs.

Video on Demand (VoD) services allow users to select and locally consume remotely stored content. We investigate the use of caching to solve the scalability issues of several existing VoD providers. We propose metrics and goals that define the requirements of a caching framework for CDNs of VoD systems. Using data logs collected from Motorola equipment from Comcast VoD deployments we show that several classic caching solutions do not satisfy the proposed goals. We address this issue by developing novel techniques for predicting future values of several metrics of interest. We rely on computed predictions to define the penalty imposed on the system, both network and caching sites, when not storing individual items. We use item penalties to devise novel caching and static content placement strategies. We use the previously mentioned data logs to validate our solutions and show that they satisfy all the defined goals.

One of Android's main defense mechanisms against malicious apps is a risk communication mechanism which, before a user installs an app, warns the user about the permissions the app requires, trusting that the user will make the right decision. This approach has been shown to be ineffective as it presents the risk information of each app in a "tand-alone" ashion and in a way that requires too much technical knowledge and time to distill useful information.

GeoSocial Networks (GSNs) are online social networks centered on the location information of their users. Users “check-in” their location and use it to acquire location-based special status (e.g., badges, mayorships) and receive venue dependent rewards. The strategy of rewarding user participation however makes cheating a profitable behavior. In this paper we introduce XACT, a suite of venue-oriented secure location verification mechanisms that enable venues and GSN providers to certify the locations claimed by users. We prove that XACT is correct, secure and easy to use. We validate the need for secure location verification mechanisms by collecting and analyzing data from the most popular GSNs today: 780,000 Foursquare users and 143,000 Gowalla users. Through a proof-of-concept implementation on a Revision C4 BeagleBoard embedded system we show that XACT is easy to deploy and economically viable. We analytically and empirically prove that XACT detects location cheating attacks.

The openness of the Android operating system increased the number of applications developed, but it also introduced a new propagation vector for mobile malware. We model the propagation of mobile malware using epidemiology theory and study the problem as a function of the underlying mobility models. We define the optimal approach to heal an infected system with the help of a set of static healers that distribute patches, as the T-COVER problem and show that it is NP-HARD. We then propose two families of healer protocols that trade-off time recovery and energy consumed by sending patches. The first one uses randomization to ensure a small recovery time but may result in healers sending more patches than needed. The second one uses system feedback to optimize energy consumed by sending patches, but it may result in a larger recovery time. We show through simulations using the NS-3 simulator that despite lacking knowledge of the future, our protocols obtain a recovery time within a 10x bound of the oracle solution that knows the arrival time of the infected nodes.

The phenomenal growth of the Android platform in the past few years has made it a lucrative target of malicious application (app) developers. There are numerous instances of malware apps that send premium rate SMS messages, track users' private data, or apps that, even if not characterized as malware, conduct questionable actions affecting the user's privacy or costing them money. In this paper, we investigate the feasibility of using both the permissions an app requests, the category of the app, and what permissions are requested by other apps in the same category to better inform users whether the risks of installing an app is commensurate with its expected benefit. Existing approaches consider only the risks of the permissions requested by an app and ignore both the benefits and what permissions are requested by other apps, thus having a limited effect. We propose several risk signals that and evaluate them using two datasets, one consists of 158,062 Android apps from the Android Market, and another consists of 121 malicious apps. We demonstrate the effectiveness of our proposal through extensive data analysis.

Video on Demand (VoD) services allow users to select and locally consume remotely stored content. We investigate the use of caching to solve the scalability issues of several existing VoD providers. We propose metrics and goals that define the requirements of a caching framework for CDNs of VoD systems. Using data logs collected from Motorola equipment from Comcast VoD deployments we show that several classic caching solutions do not satisfy the proposed goals. We address this issue by developing a novel technique for predicting future values of several metrics of interest. We use these predictions to evaluate the penalty imposed on the system (network and caches) when not caching individual items. We use item penalties to propose novel caching and static placement strategies. We use the mentioned data logs to validate our solutions and show that they satisfy all the defined goals.

Online Social Networks (OSNs) such as Facebook have become ubiquitous in the past few years, counting hundreds of millions of people as members. OSNs allow users to form friendship relationships, join groups, communicate and share information with friends. The tremendous popularity of OSNs has naturally made them an appealing target for privacy compromising attacks. In this abstract we propose a novel attack against tightly knit OSN communities. Such (artificial) communities consist of users that know well each other and that are reluctant to accept other users as friends. Becoming a member of such a community may be only a first milestone for the attacker. Harvesting private information of members of such communities and following up with offline attacks may be the longer term benefit.

An accurate Internet topology graph is important in many areas of networking, from deciding ISP business relationships to diagnosing network anomalies. Most Internet mapping efforts have derived the network structure, at the level of interconnected autonomous systems (ASes), from a limited number of either BGP- or traceroute- based data sources. While techniques for charting the topology continue to improve, the growth of the number of vantage points is significantly outpaced by the rapid growth of the Internet.