Automatic configuration tuning of online services with dynamic workloads has attracted increasing interest. Effective online tuning ensures configurations adapt to workload changes over time to maintain optimal online service performance. To be practical, online tuning must satisfy the dynamicity, efficiency, and Quality of Service (QoS) requirements. However, existing online tuning approaches fail to meet these requirements due to the inability to eliminate negative effects from historical observations. In this paper, we propose A-Tune-Online, an online configuration tuning system that tackles dynamic workloads, delivering superior tuning efficiency, and QoS guarantee simultaneously to a wide range of online scenarios. We identify that restarting the optimization based on explicit workload shift detection is necessary and critical to eliminate negative historical observations. First, to invoke optimization restarts appropriately, we design a multi-stage multi-indicator detection strategy based on heuristic rules and configuration replays. Then, to avoid initial efficiency drop after re-optimization, A-Tune-Online utilizes a similarity-based dual warm start scheme that transfers knowledge from similar historical workloads effectively. Finally, to prevent transient performance degradation from violating QoS guarantee after optimization restart, we leverage lower confidence bound to construct a safety region where each configuration is expected to perform better than the QoS requirement. Empirical study on five tuning scenarios showcases the superiority of A-Tune-Online compared with state-of-art tuning systems. A-Tune-Online achieves an average speedup of 2.90x and 1.72x compared with OnlineTune and DDPG+, respectively. We provide a version of our system in https://github.com/PKU-DAIR/A-Tune-Online.

Selecting the best items in a dataset is a common task in data exploration. However, the concept of “best” lies in the eyes of the beholder: Different users may consider different attributes more important and, hence, arrive at different rankings. Nevertheless, one can remove “dominated” items and create a “representative” subset of the data, comprising the “best items” in it. A Pareto-optimal representative is guaranteed to contain the best item of each possible ranking, but it can be a large portion of data. A much smaller representative can be found if we relax the requirement of including the best item for each user and instead just limit the users’ “regret.” Existing work defines regret as the loss in score by limiting consideration to the representative instead of the full dataset, for any chosen ranking function. However, the score is often not a meaningful number, and users may not understand its absolute value. Sometimes small ranges in score can include large fractions of the dataset. In contrast, users do understand the notion of rank ordering. Therefore, we consider items’ positions in the ranked list in defining the regret and propose the rank-regret representative as the minimal subset of the data containing at least one of the top- k of any possible ranking function. This problem is polynomial time solvable in two-dimensional space but is NP-hard on three or more dimensions. We design a suite of algorithms to fulfill different purposes, such as whether relaxation is permitted on k , the result size, or both, whether a distribution is known, whether theoretical guarantees or practical efficiency is important, and so on. Experiments on real datasets demonstrate that we can efficiently find small subsets with small rank-regrets.

Abstract Large online networks are most massive and opulent data sources these days. The inherent growing demands of analyses related data fetching conflict greatly with network providers’ efforts to protect their digital assets as well as users’ increasing awareness of privacy. Restrictions on web interfaces of online networks prevent third party researchers from gathering sufficient data and further global images of these networks are also hidden. Under such circumstances, only techniques like random walk approaches that can run under local neighborhood access will be adopted to fulfill large online network sampling tasks. Meanwhile, the presence of highly clustered community like structure in large networks leads to random walk’s poor conductance, causing intolerable and hard-to-foresee long mixing time before useful samples can be collected. With lack of techniques incorporate online network topology features being the context, in this paper we focus on taking use of community affiliation information that possibly comes with metadata when querying objects in online networks, and proposed a speeded version of random walk by raising the probability of inter-community edges being selected. Assuming the community structure is well established as promised, the community speeded random walk expects better conductance and faster convergence. Our method forces the sampler to travel rapidly among different communities that conquers the bottlenecks and thus the samples being collected are of higher quality. We also consider the scenario when community affiliation is not directly available, where we apply feature selection algorithms to select features as community.

Selecting the best items in a dataset is a common task in data exploration. However, the concept of "best'' lies in the eyes of the beholder: different users may consider different attributes more important, and hence arrive at different rankings. Nevertheless, one can remove "dominated'' items and create a "representative'' subset of the data, comprising the "best items'' in it. A Pareto-optimal representative is guaranteed to contain the best item of each possible ranking, but it can be a large portion of data. A much smaller representative can be found if we relax the requirement to include the best item for each user, and instead just limit the users' "regret''. Existing work defines regret as the loss in score by limiting consideration to the representative instead of the full data set, for any chosen ranking function. However, the score is often not a meaningful number and users may not understand its absolute value. Sometimes small ranges in score can include large fractions of the data set. In contrast, users do understand the notion of rank ordering. Therefore, we consider the position of the items in the ranked list for defining the regret and propose the \em rank-regret representative as the minimal subset of the data containing at least one of the top-k of any possible ranking function. This problem is NP-complete. We use a geometric interpretation of items to bound their ranks on ranges of functions and to utilize combinatorial geometry notions for developing effective and efficient approximation algorithms for the problem. Experiments on real datasets demonstrate that we can efficiently find small subsets with small rank-regrets.

The ranked retrieval model has rapidly become the de-facto way for search query processing in web databases. Despite the extensive efforts on designing better ranking mechanisms, in practice, many such databases fail to address the diverse and sometimes contradicting preferences of users. In this paper, we present QR2, a third-party service that uses nothing but the public search interface of a web database and enables the on-the-fly processing of queries with any user-specified ranking functions, no matter if the ranking function is supported by the database or not.

Location Based Services (LBS) have become extremely popular over the past decade. Popular LBS run the entire gamut from mapping services (such as Google Maps) to restaurants reviews (such as Yelp) and real-estate search (such as Zillow). The backend database of these applications can be a rich data source for geospatial and commercial information such as Point-Of-Interest (POI) locations, reviews, ratings, user geo-distributions, etc. However, access to the backend database is often restricted by a public query interface (often web-based) provided by the LBS owners. In most cases the public search interface of these applications can be abstractly modeled as kNN interface, taking a geolocation (i.e., latitude and longitude) as input and returning top-k POI's that are closest to the query point, where k is a small constant such as 50 or 100. Because of this restriction it becomes extremely difficult for third-party users to perform analytics or mining over LBS. We demonstrate DBLOC, a web-based system that enables analytics over the LBS by using nothing but limited access to kNN interface provided by the LBS. Specifically, using DBLOC the users can perform density based clustering over the backend database of LBS. Due to query rate limit constraint - i.e., maximum number of kNN queries a user/IP address can issue over a specific period of time, it is often impossible to access all the tuples in backend database of an LBS. Thus, DBLOC aims to mine from the LBS a cluster assignment function f(.), such that for any tuple t in the database (which may or may not have been accessed), f(.) can produce the cluster assignment of t with high accuracy. We also demonstrate how DBLOC enables the users to further analyze the discovered clusters in order to mine interesting intra/inter cluster information.

Signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an underdetermined system of linear equations that is closest to a given prior. It has a substantial number of applications in diverse areas including network traffic engineering, medical image reconstruction, acoustics, astronomy and many more. Most common approaches for SRP do not scale to large problem sizes. In this paper, we propose a dual formulation of this problem and show how adapting database techniques developed for scalable similarity joins provides a significant speedup. Extensive experiments on real-world and synthetic data show that our approach produces a significant speedup of up to 20x over competing approaches.

Transportation-based Cyber-Physical Systems (TCPS), also known as Intelligent Transportation Systems (ITS), have been introduced to increase traffic efficiency and safety. To reduce traffic congestion and traveling time, a number of real-time route guidance schemes have been developed to assist travelers in determining the optimal route for their transit. In this paper, we address the vulnerability issue of the route guiding process and study data integrity attacks against route guidance schemes. To be specific, we consider a generic attack, in which the adversary may compromise vehicles via wireless communication networks and then manipulate the real-time traffic information generated or forwarded by these vehicles, and finally broadcast the forged real-time traffic information into vehicular networks. We formally model the attack and quantitatively analyze its impact on the effectiveness of route guidance schemes. Our findings show that the investigated data integrity attack can effectively disrupt route guidance, resulting in significant traffic congestion, the increase of travel time, and the imbalanced use of transportation resources.

Location Based Services (LBS) have become extremely popular over the past decade, being used on a daily basis by millions of users. Instances of real-world LBS range from mapping services (e.g., Google Maps) to lifestyle recommendations (e.g., Yelp) to real-estate search (e.g., Redfin). In general, an LBS provides a public (often web-based) search interface over its backend database (of tuples with 2D geolocations), taking as input a 2D query point and returning k tuples in the database that are closest to the query point, where k is usually a small constant such as 20 or 50. Such a public interface is often called a k-Nearest-Neighbor, i.e., kNN, interface. In this paper, we consider a novel problem of enabling density based clustering over the backend database of an LBS using nothing but limited access to the kNN interface provided by the LBS. Specifically, a key limit enforced by most real-world LBS is a maximum number of kNN queries allowed from a user over a given time period. Since such a limit is often orders of magnitude smaller than the number of tuples in the LBS database, our goal here is to mine from the LBS a cluster assignment function f(·), such that for any tuple t in the database (which may or may not have been accessed), f(·) can produce the cluster assignment of t with high accuracy. We conduct a comprehensive set of experiments over benchmark datasets and popular real-world LBS such as Yahoo! Flickr, Zillow, Redfin and Google Maps and demonstrate the effectiveness of our proposed techniques.

We propose to demonstrate HDBExpDetector, a system for analysts to discover bursty events from a thirdparty web database by using nothing but the existing search interface of the web database to monitor and detect sudden changes to aggregates that satisfy certain user-defined conditions. Video https://youtu.be/7Pwd8o1h5CY.

Finding the maxima of a database based on a user preference, especially when the ranking function is a linear combination of the attributes, has been the subject of recent research. A critical observation is that the em convex hull is the subset of tuples that can be used to find the maxima of any linear function. However, in real world applications the convex hull can be a significant portion of the database, and thus its performance is greatly reduced. Thus, computing a subset limited to $r$ tuples that minimizes the regret ratio (a measure of the user's dissatisfaction with the result from the limited set versus the one from the entire database) is of interest.

Fog/edge computing has been proposed to be integrated with Internet of Things (IoT) to enable computing services devices deployed at network edge, aiming to improve the user's experience and resilience of the services in case of failures. With the advantage of distributed architecture and close to end-users, fog/edge computing can provide faster response and greater quality of service for IoT applications. Thus, fog/edge computing-based IoT becomes future infrastructure on IoT development. To develop fog/edge computing-based IoT infrastructure, the architecture, enabling techniques, and issues related to IoT should be investigated first, and then the integration of fog/edge computing and IoT should be explored. To this end, this paper conducts a comprehensive overview of IoT with respect to system architecture, enabling technologies, security and privacy issues, and present the integration of fog/edge computing and IoT, and applications. Particularly, this paper first explores the relationship between cyber-physical systems and IoT, both of which play important roles in realizing an intelligent cyber-physical world. Then, existing architectures, enabling technologies, and security and privacy issues in IoT are presented to enhance the understanding of the state of the art IoT development. To investigate the fog/edge computing-based IoT, this paper also investigate the relationship between IoT and fog/edge computing, and discuss issues in fog/edge computing-based IoT. Finally, several applications, including the smart grid, smart transportation, and smart cities, are presented to demonstrate how fog/edge computing-based IoT to be implemented in real-world applications.

Location Based Services (LBS), including standalone ones such as Google Maps and embedded ones such as “users near me” in the WeChat instant-messaging platform, provide great utility to millions of users. Not only that, they also form an important data source for geospatial and commercial information such as Point-Of-Interest (POI) locations, review ratings, user geo-distributions, etc. Unfortunately, it is not easy to tap into these LBS for tasks such as data analytics and mining, because the only access interface they offer is a limited k-Nearest-Neighbor (kNN) search interface - i.e., for a given input location, return the k nearest tuples in the database, where k is a small constant such as 50 or 100. This limited interface essentially precludes the crawling of an LBS' underlying database, as the small k mandates an extremely large number of queries that no real-world LBS would allow from an IP address or API account. We demonstrate ANALOC, a web based system that enables fast analytics over an LBS by issuing a small number of queries through its restricted kNN interface. ANALOC stands in sharp contrast with existing systems for analyzing geospatial data, as those systems mostly assume complete access to the underlying data. Specifically, ANALOC supports the approximate processing of a wide variety of SUM, COUNT and AVG aggregates over user-specified selection conditions. In the demonstration, we shall not only illustrate the design and accuracy of our underlying aggregate estimation techniques, but also showcase how these estimated aggregates can be used to enable exciting applications such as hotspot detection, infographics, etc. Our demonstration system is designed to query real-world LBS (systems or modules) such as Google Maps, WeChat and Sina Weibo at real time, in order to provide the audience with a practical understanding of the performance of ANALOC.

With rapidly growing popularity, Location Based Services (LBS), e.g., Google Maps, Yahoo Local, WeChat, FourSquare, etc., started offering web-based search features that resemble a kNN query interface. Specifically, for a user-specified query location q, these websites extract from the objects in their backend database the top-k nearest neighbors to q and return these k objects to the user through the web interface. Here k is often a small value like 50 or 100. For example, McDonald [1] returns the top 25 nearest restaurants for a user-specified location through its locations search webpage.

Many web databases are "hidden" behind proprietary search interfaces that enforce the top- k output constraint, i.e., each query returns at most k of all matching tuples, preferentially selected and returned according to a proprietary ranking function. In this paper, we initiate research into the novel problem of skyline discovery over top- k hidden web databases. Since skyline tuples provide critical insights into the database and include the top-ranked tuple for every possible ranking function following the monotonic order of attribute values, skyline discovery from a hidden web database can enable a wide variety of innovative third-party applications over one or multiple web databases. Our research in the paper shows that the critical factor affecting the cost of skyline discovery is the type of search interface controls provided by the website. As such, we develop efficient algorithms for three most popular types, i.e., one-ended range, free range and point predicates, and then combine them to support web databases that feature a mixture of these types. Rigorous theoretical analysis and extensive real-world online and offline experiments demonstrate the effectiveness of our proposed techniques and their superiority over baseline solutions.

The ranked retrieval model has rapidly become the de facto way for search query processing in client-server databases, especially those on the web. Despite of the extensive efforts in the database community on designing better ranking functions/mechanisms, many such databases in practice still fail to address the diverse and sometimes contradicting preferences of users on tuple ranking, perhaps (at least partially) due to the lack of expertise and/or motivation for the database owner to design truly effective ranking functions. This paper takes a different route on addressing the issue by defining a novel query reranking problem , i.e., we aim to design a third-party service that uses nothing but the public search interface of a client-server database to enable the on-the-fly processing of queries with any user-specified ranking functions (with or without selection conditions), no matter if the ranking function is supported by the database or not. We analyze the worst-case complexity of the problem and introduce a number of ideas, e.g., on-the-fly indexing, domination detection and virtual tuple pruning, to reduce the average-case cost of the query reranking algorithm. We also present extensive experimental results on real-world datasets, in both offline and live online systems, that demonstrate the effectiveness of our proposed techniques.

Logitech made the following statement in 2009: “Since the displacements of a mouse would not give any useful information to a hacker, the mouse reports are not encrypted.” In this paper, we prove the exact opposite is true-i.e., it is indeed possible to leak sensitive information such as passwords through the displacements of a Bluetooth mouse. Our results can be easily extended to other wireless mice using different radio links. We begin by presenting multiple ways to sniff unencrypted Bluetooth packets containing raw mouse movement data. We then show that such data may reveal text-based passwords entered by clicking on software keyboards. We propose two attacks, the prediction attack and replay attack, which can reconstruct the on-screen cursor trajectories from sniffed mouse movement data. Two inference strategies are used to discover passwords from cursor trajectories. We conducted a holistic study over all popular operating systems and analyzed how mouse acceleration algorithms and packet losses may affect the reconstruction results. Our real-world experiments demonstrate the severity of privacy leakage from unencrypted Bluetooth mice. We also discuss countermeasures to prevent privacy leakage from wireless mice. To the best of our knowledge, our work is the first to demonstrate privacy leakage from raw mouse data.

Many websites offering Location Based Services (LBS) provide a$k$NN search interface that returns the top-$k$nearest-neighbor objects (e.g., nearest restaurants) for a given query location. This paper addresses the problem of crawling all objects efficiently from an LBS website, through the public$k$NN web search interface it provides. Specifically, we develop crawling algorithm for 2D and higher-dimensional spaces, respectively, and demonstrate through theoretical analysis that the overhead of our algorithms can be bounded by a function of the number of dimensions and the number of crawled objects, regardless of the underlying distributions of the objects. We also extend the algorithms to leverage scenarios where certain auxiliary information about the underlying data distribution, e.g., the population density of an area which is often positively correlated with the density of LBS objects, is available. Extensive experiments on real-world datasets demonstrate the superiority of our algorithms over the state-of-the-art competitors in the literature.

Many online social networks feature restrictive web interfaces that only allow the query of a user’s local neighborhood. To enable analytics over such an online social network through its web interface, many recent efforts use Markov Chain Monte Carlo (MCMC) methods such as random walks to sample users in the social network and thereby support analytics based on the samples. The problem with such an approach, however, is the large amount of queries often required for a random walk to converge to a desired (stationary) sampling distribution. In this article, we consider a novel problem of enabling a faster random walk over online social networks by “rewiring” the social network on-the-fly. Specifically, we develop a Modified TOpology Sampling (MTO-Sampling) scheme that, by using only information exposed by the restrictive web interface, constructs a “virtual” random-walk-friendly overlay topology of the social network while performing a random walk and ensures that the random walk follows the modified overlay topology rather than the original one. We describe in this article instantiations of MTO-Sampling for various types of random walks, such as Simple Random Walk (MTO-SRW), Metropolis-Hastings Random Walk (MTO-MHRW), and General Random Walk (MTO-GRW). We not only rigidly prove that MTO-Sampling improves the efficiency of sampling, but we also demonstrate the significance of such improvement through experiments on real-world online social networks such as Google Plus, Epinion, Facebook, etc.

Today, one can find from the web vast amount of information about an individual. Specifically, such information can be classified into two categories, virtual and real-world identities. This paper addresses a novel problem of linking these two types of identities based on information publicly available on the web. We start by studying how one can link virtual identities (i.e., user profiles) at Twitter with real-world identities at Whitepages.com (containing personal information such as name, age, relatives, etc.). We demonstrate that a substantial portion (at least 0.17%) of Twitter users in the U.S. can indeed be potentially linked to their real-world identities through information available at Whitepages.com, revealing sensitive personal data. We discuss the implications of such identity linkages on both individual privacy and law enforcement, and also point out the future studies required in this topic.

An online community network such as Twitter, Yelp or amazon.com links entities (e.g., Users, products) with various relationships (e.g., Friendship, co-purchase, co-review) and make such information available for access through a web interface. Often, these community networks act as "social sensors" in which users sense information in the real world and mention them online. The web interfaces of these networks often support features such as keyword search that allow an user to quickly find entities of interest. While these interfaces are adequate for regular users, they are often too restrictive to answer complex queries such as (1) find 100 Twitter users from California with at least 100 followers who talked about earthquakes last year or (2) find 25 restaurants in Yelp with at least 10 5-star reviews with 10 or more 'useful' points. In this paper, we investigate the problem of answering complex queries that involve non-searchable attributes through the web interface of an online community network. We model such a network as a heterogeneous graph with two access channels, Content Search and Local Search. We propose a number of efficient algorithms that leverage properties of the heterogeneous graph and also propose a strategy selection algorithm based on the concept of multi-armed bandits. We conduct comprehensive experiments over popular social sensing websites such as Twitter and amazon.com which demonstrate the efficacy of our proposed algorithms.

Location based services (LBS) have become very popular in recent years. They range from map services (e.g., Google Maps) that store geographic locations of points of interests, to online social networks (e.g., WeChat, Sina Weibo, FourSquare) that leverage user geographic locations to enable various recommendation functions. The public query interfaces of these services may be abstractly modeled as a k NN interface over a database of two dimensional points on a plane: given an arbitrary query point, the system returns the k points in the database that are nearest to the query point. In this paper we consider the problem of obtaining approximate estimates of SUM and COUNT aggregates by only querying such databases via their restrictive public interfaces. We distinguish between interfaces that return location information of the returned tuples (e.g., Google Maps), and interfaces that do not return location information (e.g., Sina Weibo). For both types of interfaces, we develop aggregate estimation algorithms that are based on novel techniques for precisely computing or approximately estimating the Voronoi cell of tuples. We discuss a comprehensive set of real-world experiments for testing our algorithms, including experiments on Google Maps, WeChat, and Sina Weibo.

In this paper, we introduce a novel, general purpose, technique for faster sampling of nodes over an online social network. Specifically, unlike traditional random walks which wait for the convergence of sampling distribution to a predetermined target distribution - a waiting process that incurs a high query cost - we develop WALK-ESTIMATE, which starts with a much shorter random walk, and then proactively estimate the sampling probability for the node taken before using acceptance-rejection sampling to adjust the sampling probability to the predetermined target distribution. We present a novel backward random walk technique which provides provably unbiased estimations for the sampling probability, and demonstrate the superiority of WALK-ESTIMATE over traditional random walks through theoretical analysis and extensive experiments over real world online social networks.

In recent years, there has been much research in the adoption of Ranked Retrieval model (in addition to the Boolean retrieval model) in structured databases, especially those in a client-server environment (e.g., web databases). With this model, a search query returns top- k tuples according to not just exact matches of selection conditions, but a suitable ranking function. While much research has gone into the design of ranking functions and the efficient processing of top- k queries, this paper studies a novel problem on the privacy implications of database ranking. The motivation is a novel yet serious privacy leakage we found on real-world web databases which is caused by the ranking function design. Many such databases feature private attributes - e.g., a social network allows users to specify certain attributes as only visible to him/herself, but not to others. While these websites generally respect the privacy settings by not directly displaying private attribute values in search query answers, many of them nevertheless take into account such private attributes in the ranking function design. The conventional belief might be that tuple ranks alone are not enough to reveal the private attribute values. Our investigation, however, shows that this is not the case in reality. To address the problem, we introduce a taxonomy of the problem space with two dimensions, (1) the type of query interface and (2) the capability of adversaries. For each subspace, we develop a novel technique which either guarantees the successful inference of private attributes, or does so for a significant portion of real-world tuples. We demonstrate the effectiveness and efficiency of our techniques through theoretical analysis, extensive experiments over real-world datasets, as well as successful online attacks over websites with tens to hundreds of millions of users - e.g., Amazon Goodreads and Renren.com.

With a vast amount of data available on online social networks, how to enable efficient analytics over such data has been an increasingly important research problem. Given the sheer size of such social networks, many existing studies resort to sampling techniques that draw random nodes from an online social network through its restrictive web/API interface. While these studies differ widely in analytics tasks supported and algorithmic design, almost all of them use the exact same underlying technique ofrandom walk- a Markov Chain Monte Carlo based method which iteratively transits from one node to its random neighbor. Random walk fits naturally with this problem because, for most online social networks, the only query we can issue through the interface is to retrieve the neighbors of a given node (i.e., no access to the full graph topology). A problem with random walks, however, is the "burn-in" period which requires a large number of transitions/queries before the sampling distribution converges to a stationary value that enables the drawing of samples in a statistically valid manner. In this paper, we consider a novel problem of speeding up the fundamental design of random walks (i.e., reducing the number of queries it requires)withoutchanging the stationary distribution it achieves - thereby enabling a more efficient "drop-in" replacement for existing sampling-based analytics techniques over online social networks. Technically, our main idea is to leverage the history of random walks to construct a higher-ordered Markov chain. We develop two algorithms,Circulated NeighborsandGroupby NeighborsRandom Walk (CNRW and GNRW) and rigidly prove that, no matter what the social network topology is, CNRW and GNRW offer better efficiency than baseline random walks while achieving the same stationary distribution. We demonstrate through extensive experiments on real-world social networks and synthetic graphs the superiority of our techniques over the existing ones.

A large number of web data repositories are hidden behind restrictive web interfaces, making it an important challenge to enable data analytics over these hidden web databases. Most existing techniques assume a form-like web interface which consists solely of categorical attributes (or numeric ones that can be discretized). Nonetheless, many real-world web interfaces (of hidden databases) also feature checkbox interfaces-e.g., the specification of a set of desired features, such as A/C, navigation, etc., for a car-search website like Yahoo! Autos. We find that, for the purpose of data analytics, such checkbox-represented attributes differ fundamentally from the categorical/numerical ones that were traditionally studied. In this paper, we address the problem of data analytics over hidden databases with checkbox interfaces. Extensive experiments on both synthetic and real datasets demonstrate the accuracy and efficiency of our proposed algorithms.

The emerging paradigm of cloud computing, e.g., Amazon Elastic Compute Cloud (EC2), promises a highly flexible yet robust environment for large-scale applications. Ideally, while multiple virtual machines (VM) share the same physical resources (e.g., CPUs, caches, DRAM, and I/O devices), each application should be allocated to an independently managed VM and isolated from one another. Unfortunately, the absence of physical isolation inevitably opens doors to a number of security threats. In this paper, we demonstrate in EC2 a new type of security vulnerability caused by competition between virtual I/O workloads-i.e., by leveraging the competition for shared resources, an adversary could intentionally slow down the execution of a targeted application in a VM that shares the same hardware. In particular, we focus on I/O resources such as hard-drive throughput and/or network bandwidth-which are critical for data-intensive applications. We design and implement Swiper, a framework which uses a carefully designed workload to incur significant delays on the targeted application and VM with minimum cost (i.e., resource consumption). We conduct a comprehensive set of experiments in EC2, which clearly demonstrates that Swiper is capable of significantly slowing down various server applications while consuming a small amount of resources.

CrewScout is an expert-team finding system based on the concept of skyline teams and efficient algorithms for finding such teams. Given a set of experts, CrewScout finds all k-expert skyline teams, which are not dominated by any other k-expert teams. The dominance between teams is governed by comparing their aggregated expertise vectors. The need for finding expert teams prevails in applications such as question answering, crowdsourcing, panel selection, and project team formation. The new contributions of this paper include an end-to-end system with an interactive user interface that assists users in choosing teams and an demonstration of its application domains.

Microblogging platforms such as Twitter have experienced a phenomenal growth of popularity in recent years, making them attractive platforms for research in diverse fields from computer science to sociology. However, most microblogging platforms impose strict access restrictions (e.g., API rate limits) that prevent scientists with limited resources - e.g., who cannot afford microblog-data-access subscriptions offered by GNIP et al. - to leverage the wealth of microblogs for analytics. For example, Twitter allows only 180 queries per 15 minutes, and its search API only returns tweets posted within the last week. In this paper, we consider a novel problem of estimating aggregate queries over microblogs, e.g., "how many users mentioned the word 'privacy' in 2013?". We propose novel solutions exploiting the user-timeline information that is publicly available in most microblogging platforms. Theoretical analysis and extensive real-world experiments over Twitter, Google+ and Tumblr confirm the effectiveness of our proposed techniques.

With the proliferation of very large data repositories hidden behind web interfaces, e.g., keyword search, form-like search and hierarchical/graph-based browsing interfaces for Amazon.com, eBay.com, etc., efficient ways of searching, exploring and/or mining such web data are of increasing importance.

Numerous web databases, e.g., amazon.com, eBay.com, are "hidden" behind (i.e., accessible only through) their restrictive search and browsing interfaces. This demonstration showcases HDBTracker, a web-based system that reveals and tracks (the changes of) user-specified aggregate queries over such hidden web databases, especially those that are frequently updated, by issuing a small number of search queries through the public web interfaces of these databases. The ability to track and monitor aggregates has applications over a wide variety of domains - e.g., government agencies can track COUNT of openings at online job hunting websites to understand key economic indicators, while businesses can track the AVG price of a product over a basket of e-commerce websites to understand the competitive landscape and/or material costs. A key technique used in HDBTracker is RS-ESTIMATOR, the first algorithm that can efficiently monitor changes to aggregate query answers over a hidden web database.

Many databases on the web are "hidden" behind (i.e., accessible only through) their restrictive, form-like, search interfaces. Recent studies have shown that it is possible to estimate aggregate query answers over such hidden web databases by issuing a small number of carefully designed search queries through the restrictive web interface. A problem with these existing work, however, is that they all assume the underlying database to be static, while most real-world web databases (e.g., Amazon, eBay) are frequently updated. In this paper, we study the novel problem of estimating/tracking aggregates over dynamic hidden web databases while adhering to the stringent query-cost limitation they enforce (e.g., at most 1,000 search queries per day). Theoretical analysis and extensive real-world experiments demonstrate the effectiveness of our proposed algorithms and their superiority over baseline solutions (e.g., the repeated execution of algorithms designed for static web databases).

We formulate and investigate the novel problem of finding the skyline k-tuple groups from an n-tuple data set-i.e., groups of k tuples which are not dominated by any other group of equal size, based on aggregate-based group dominance relationship. The major technical challenge is to identify effective anti-monotonic properties for pruning the search space of skyline groups. To this end, we first show that the anti-monotonic property in the well-known Apriori algorithm does not hold for skyline group pruning. Then, we identify two anti-monotonic properties with varying degrees of applicability: order-specific property which applies to SUM, MIN, and MAX as well as weak candidate-generation property which applies to MIN and MAX only. Experimental results on both real and synthetic data sets verify that the proposed algorithms achieve orders of magnitude performance gain over the baseline method.

Cognitive radio networking allows the unlicensed secondary users to opportunistically access the licensed spectrum as long as the performance of the licensed primary users does not degrade. This dynamic spectrum access strategy is enabled by cognitive radio coupled with spectrum sensing technologies. Due to the imperfection of wireless transmissions, collaborative spectrum sensing (CSS) has been proposed to significantly improve the probability of detecting the transmissions of primary users. Nevertheless, current CSS techniques are sensitive to malicious secondary users, leading to a high false alarm rate and low detection accuracy on the presence of the primary users. In this paper, we present several robust collaborative spectrum sensing schemes that can calculate a trust value for each secondary user to reflect its suspicious level and mitigate its harmful effect on cooperative sensing. Our approach explores the spatial and temporal correlations among the reported information of the secondary users to determine the trust values. Extensive simulation study has been performed and our results demonstrate that the proposed schemes can guarantee the accuracy of the cooperative sensing system with a low false alarm rate when a considerable number of secondary users report false information.

It is critical for a power system to estimate its operation state based on meter measurements in the field and the configuration of power grid networks. Recent studies show that the adversary can bypass the existing bad data detection schemes, posing dangerous threats to the operation of power grid systems. Nevertheless, two critical issues remain open: 1) how can an adversary choose the meters to compromise to cause the most significant deviation of the system state estimation, and 2) how can a system operator defend against such attacks? To address these issues, we first study the problem of finding the optimal attack strategy--i.e., a data-injection attacking strategy that selects a set of meters to manipulate so as to cause the maximum damage. We formalize the problem and develop efficient algorithms to identify the optimal meter set. We implement and test our attack strategy on various IEEE standard bus systems, and demonstrate its superiority over a baseline strategy of random selections. To defend against false data-injection attacks, we propose a protection-based defense and a detection-based defense, respectively. For the protection-based defense, we identify and protect critical sensors and make the system more resilient to attacks. For the detection-based defense, we develop the spatial-based and temporal-based detection schemes to accurately identify data-injection attacks.

Many websites (e.g., WedMD.com, CNN.com) provide keyword search interfaces over a large corpus of documents. Meanwhile, many third parties (e.g., investors, analysts) are interested in learning big-picture analytical information over such a document corpus, but have no direct way of accessing it other than using the highly restrictive web search interface. In this paper, we study how to enable third-party data analytics over a search engine's corpus without the cooperation of its owner - specifically, by issuing a small number of search queries through the web interface.

Internet Threat Monitoring (ITM) systems have been widely deployed to detect and characterize dangerous Internet global threats such as botnet and malware propagation. Nonetheless, the effectiveness of ITM systems largely depends on the confidentiality of their monitor locations. In this paper, we investigate localization attacks aiming to identify ITM monitor location and propose the formal model of such attacks using communication channel theory. We also develop novel techniques that significantly increases the accuracy, efficiency, and secrecy of ITM localization attacks. Specifically, we introduce (i) a frequency-based modulation technique to effectively reduce the interference from the background traffic and achieve a high attack accuracy, (ii) both time and space hopping techniques to randomize signal pattern and make the attack hard to detect by the defender, and (iii) Multiple Input and Multiple Output (MIMO) based techniques to increase the attack efficiency of identifying multiple monitors simultaneously. We derive closed formulae for the performance analysis of our proposed techniques and conduct extensive simulations. Our data validate our theoretical findings and demonstrate that the adversary can identify ITM monitors accurately, efficiently, and secretly.

A large number of web databases are only accessible through proprietary form-like interfaces which require users to query the system by entering desired values for a few attributes. A key restriction enforced by such an interface is the top-k output constraint - i.e., when there are a large number of matching tuples, only a few (top-k) of them are preferentially selected and returned by the website, often according to a proprietary ranking function. Since most web database owners set k to be a small value, the top-k output constraint prevents many interesting third-party (e.g., mashup) services from being developed over real-world web databases. In this paper we consider the novel problem of “digging deeper” into such web databases. Our main contribution is the meta-algorithm GetNext that can retrieve the next ranked tuple from the hidden web database using only the restrictive interface of a web database without any prior knowledge of its ranking function. This algorithm can then be called iteratively to retrieve as many top ranked tuples as necessary. We develop principled and efficient algorithms that are based on generating and executing multiple reformulated queries and inferring the next ranked tuple from their returned results. We provide theoretical analysis of our algorithms, as well as extensive experimental results over synthetic and real-world databases that illustrate the effectiveness of our techniques.

Many online social networks feature restrictive web interfaces which only allow the query of a user's local neighborhood through the interface. To enable analytics over such an online social network through its restrictive web interface, many recent efforts reuse the existing Markov Chain Monte Carlo methods such as random walks to sample the social network and support analytics based on the samples. The problem with such an approach, however, is the large amount of queries often required (i.e., a long “mixing time”) for a random walk to reach a desired (stationary) sampling distribution. In this paper, we consider a novel problem of enabling a faster random walk over online social networks by “rewiring” the social network on-the-fly. Specifically, we develop Modified TOpology (MTO)-Sampler which, by using only information exposed by the restrictive web interface, constructs a “virtual” overlay topology of the social network while performing a random walk, and ensures that the random walk follows the modified overlay topology rather than the original one. We show that MTO-Sampler not only provably enhances the efficiency of sampling, but also achieves significant savings on query cost over real-world online social networks such as Google Plus, Epinion etc.

Body Area Networks (BANs) are expected to play a major role in the field of patient-health monitoring in the near future. While it is vital to support secure BAN access to address the obvious safety and privacy concerns, it is equally important to maintain the elasticity of such security measures. For example, elasticity is required to ensure that first-aid personnel have access to critical information stored in a BAN in emergent situations. The inherent tradeoff between security and elasticity calls for the design of novel security mechanisms for BANs. In this paper, we develop the Fuzzy Attribute-Based Signcryption (FABSC), a novel security mechanism that makes a proper tradeoff between security and elasticity. FABSC leverages fuzzy Attribute-based encryption to enable data encryption, access control, and digital signature for a patient's medical information in a BAN. It combines digital signatures and encryption, and provides confidentiality, authenticity, unforgeability, and collusion resistance. We theoretically prove that FABSC is efficient and feasible. We also analyze its security level in practical BANs.

Many web databases are only accessible through a proprietary search interface which allows users to form a query by entering the desired values for a few attributes. After receiving a query, the system returns the top-kmatching tuples according to a pre-determined ranking function. Since the rank of a tuple largely determines the attention it receives from website users, ranking information for any tuple - not just the top-ranked ones - is often of significant interest to third parties such as sellers, customers, market researchers and investors. In this paper, we define a novel problem of rank discovery over hidden web databases. We introduce a taxonomy of ranking functions, and show that different types of ranking functions require fundamentally different approaches for rank discovery. Our technical contributions include principled and efficient randomized algorithms for estimating the rank of a given tuple, as well as negative results which demonstrate the inefficiency of any deterministic algorithm. We show extensive experimental results over real-world databases, including an online experiment at Amazon.com, which illustrates the effectiveness of our proposed techniques.

In many practical applications of wireless sensor networks, it is crucial to accomplish the localization of sensors within a given time bound. We find that the traditional definition of relative localization is inappropriate for evaluating its actual overhead in localization time. To address this issue, we define a novel problem called essential localization and present the first rigorous study on the essential localizability of a wireless sensor network within a given time bound. Additionally, we propose an efficient distributed algorithm for time-bounded essential localization over a sensor network and evaluate the performance of the algorithm with analysis and extensive simulation studies.

Raw mouse movement data can be sniffed via off-the-shelf tools. In this demo, we show that such data, while seemingly harmless, may reveal extremely sensitive information such as passwords. Nonetheless, such a Bluetooth-mouse-sniffing attack can be challenging to perform mainly because of two reasons: (i) packet loss is common for Bluetooth traffic, and (ii) modern operating systems use complex mouse acceleration strategies, which make it extremely difficult, if not impossible, to reconstruct the precise on-screen cursor coordinates from raw mouse movements. To address those challenges, we have conducted an extensive and careful study, over multiple operating systems, on the reconstruction of mouse cursor trajectory from raw mouse data and the inference of privacy-sensitive information - e.g., user password - from the reconstructed trajectory. Our experimental data demonstrate the severity of privacy leaking from un-encrypted Bluetooth mouse. To the best of our knowledge, our work is the first to retrieve sensitive information from sniffed mouse raw data. Video links of successful replay attack for different target OS are given in Section 3.2.

We formulate and investigate the novel problem of finding the skyline k-tuple groups from an n-tuple dataset - i.e., groups of k tuples which are not dominated by any other group of equal size, based on aggregate-based group dominance relationship. The major technical challenge is to identify effective anti-monotonic properties for pruning the search space of skyline groups. To this end, we show that the anti-monotonic property in the well-known Apriori algorithm does not hold for skyline group pruning. We then identify order-specific property which applies to SUM, MIN, and MAX and weak candidate-generation property which applies to MIN and MAX only. Experimental results on both real and synthetic datasets verify that the proposed algorithms achieve orders of magnitude performance gain over a baseline method.

Many enterprise websites provide search engines to facilitate customer access to their underlying documents or data. With the web interface of such a search engine, a customer can specify one or a few keywords that he/she is interested in; and the search engine returns a list of documents/tuples matching the user-specified keywords, sorted by an often-proprietary scoring function.

A hidden database refers to a dataset that an organization makes accessible on the web by allowing users to issue queries through a search interface. In other words, data acquisition from such a source is not by following static hyper-links. Instead, data are obtained by querying the interface, and reading the result page dynamically generated. This, with other facts such as the interface may answer a query only partially, has prevented hidden databases from being crawled effectively by existing search engines. This paper remedies the problem by giving algorithms to extract all the tuples from a hidden database. Our algorithms are provably efficient, namely, they accomplish the task by performing only a small number of queries, even in the worst case. We also establish theoretical results indicating that these algorithms are asymptotically optimal -- i.e., it is impossible to improve their efficiency by more than a constant factor. The derivation of our upper and lower bound results reveals significant insight into the characteristics of the underlying problem. Extensive experiments confirm the proposed techniques work very well on all the real datasets examined.

As file systems reach the petabytes scale, users and administrators are increasingly interested in acquiring high-level analytical information for file management and analysis. Two particularly important tasks are the processing of aggregate and top-k queries which, unfortunately, cannot be quickly answered by hierarchical file systems such as ext3 and NTFS. Existing preprocessing-based solutions, e.g., file system crawling and index building, consume a significant amount of time and space (for generating and maintaining the indexes) which in many cases cannot be justified by the infrequent usage of such solutions. In this paper, we advocate that user interests can often be sufficiently satisfied by approximate-i.e., statistically accurate-answers. We develop Glance, a just-in-time sampling-based system which, after consuming a small number of disk accesses, is capable of producing extremely accurate answers for a broad class of aggregate and top-k queries over a file system without the requirement of any prior knowledge. We use a number of real-world file systems to demonstrate the efficiency, accuracy, and scalability of Glance.

"The Marauder's Map,” a magical map in J.K. Rowling's fantasy series Harry Potter and the Prisoner of Azkaban [CHECK END OF SENTENCE], can be used as a surveillance tool to show all moving objects within the boundary of "Hogwarts School of Witchcraft and Wizardry” at a spell. In this paper, we introduce a similar forensic surveillance tool for wireless networks. Our system, the digital Marauder's map, can reveal the locations of WiFi-enabled mobile devices within the coverage area of a high-gain antenna. The digital Marauder's map is built solely with off-the-shelf wireless equipments, and features a mobile design that can be quickly deployed to a new location for instant usage without training. We present a comprehensive set of theoretical analysis and experimental results which demonstrate the coverage and localization accuracy of the digital Marauder's map.

The operating state estimation of power system is a critical process for providing a best-fit state estimation based on the meter measurements in the field and the configuration of power-grid network. To deal with the bad meter measurements caused by various faults in state estimation, power system researchers have developed numerous detection schemes in the past. Liu et al. recently proposed a new stealthy false data injection attack, which can bypass the existing bad data detection schemes and arbitrarily manipulate the states of power system, posing dangerous threats to the control of a power system. Nevertheless, their results did not show the detailed information of meters to be compromised. In this paper, we tend to tackle this issue and develop mechanisms to efficiently compute the optimal set of meter measurements given a number of state variables to be manipulated in a power-grid network. We formalize the problem of finding the optimal set of meter measurements as a known NP-hard problem and propose a heuristic approach to derive the near-optimal set of meter measurements efficiently. We implement our proposed scheme on the IEEE 9-bus, 14-bus, 30-bus, 118-bus and 300-bus systems and our data shows its efficiency and effectiveness.

Location-based services (LBS) have become an immensely valuable source of real-time information and guidance. Nonetheless, the potential abuse of users' sensitive personal data by an LBS server is evolving into a serious concern. Privacy concerns in LBS exist on two fronts: location privacy and query privacy. In this paper we investigate issues related to query privacy. In particular, we aim to prevent the LBS server from correlating the service attribute, e.g., bar/tavern, in the query to the user's real-world identity. Location obfuscation using spatial generalization aided by anonymization of LBS queries is a conventional means to this end. However, effectiveness of this technique would abate in continuous LBS scenarios, i.e., where users are moving and recurrently requesting for LBS. In this paper, we present a novel query-perturbation-based scheme that protects query privacy in continuous LBS even when user-identities are revealed. Unlike most exiting works, our scheme does not require the presence of a trusted third party.

In this paper, we propose a novel compressive sensing (CS) based approach for sparse target counting and positioning in wireless sensor networks. While this is not the first work on applying CS to count and localize targets, it is the first to rigorously justify the validity of the problem formulation. Moreover, we propose a novel greedy matching pursuit algorithm (GMP) that complements the well-known signal recovery algorithms in CS theory and prove that GMP can accurately recover a sparse signal with a high probability. We also propose a framework for counting and positioning targets from multiple categories, a novel problem that has never been addressed before. Finally, we perform a comprehensive set of simulations whose results demonstrate the superiority of our approach over the existing CS and non-CS based techniques.

Many web databases are hidden behind form-based interfaces which are not always easy-to-use on mobile devices because of limitations such as small screen sizes, trickier text entry, etc. In this demonstration, we have developed MOBIES, a third-party system that generates mobile-user-friendly interfaces by exploiting data analytics specific to the hidden web databases. Our user studies show the effectiveness of MOBIES on improving user experience over a hidden web database.

Many web databases are hidden behind restrictive form-like interfaces which may or may not provide domain information for an attribute. When attribute domains are not available, domain discovery becomes a critical challenge facing the application of a broad range of existing techniques on third-party analytical and mash-up applications over hidden databases. In this paper, we consider the problem of domain discovery over a hidden database through its web interface. We prove that for any database schema, an achievability guarantee on domain discovery can be made based solely upon the interface design. We also develop novel techniques which provide effective guarantees on the comprehensiveness of domain discovery. We present theoretical analysis and extensive experiments to illustrate the effectiveness of our approach.

Search engines over document corpora typically provide keyword-search interfaces. Examples include search engines over the web as well as those over enterprise and government websites. The corpus of such a search engine forms a rich source of information of analytical interest to third parties, but the only available access is by issuing search queries through its interface. To support data analytics over a search engine's corpus, one needs to address two main problems, the sampling of documents (for offline analytics) and the direct (online) estimation of aggregates, while issuing a small number of queries through the keyword-search interface.Existing work on sampling produces samples with unknown bias and may incur an extremely high query cost. Existing aggregate estimation technique suffers from a similar problem, as the estimation error and query cost can both be large for certain aggregates. We propose novel techniques which produce unbiased samples as well as unbiased aggregate estimates with small variances while incurring a query cost an order of magnitude smaller than the existing techniques. We present theoretical analysis and extensive experiments to illustrate the effectiveness of our approach.

As the organizing committee, it is our pleasure to present the proceedings of the 2ndIEEE International Workshop on Data Security and PrivAcy in wireless Networks (D-SPAN), held on June 20, 2011, in Lucca, Italy. The goal of this one-day workshop, organized in conjunction with the 12thIEEE WoWMoM 2011, is to exchange cutting-edge ideas for securing the next-generation wireless networks, systems and applications. The scope of D-SPAN includes a wide variety of topics, including security and privacy of data collection, transmission, storage, publishing, and sharing in wireless networks broadly defined - such as cellular and mobile ad hoc networks (MANET), vehicular ad hoc networks (VANET), cognitive and sensor networks - to applying data analytics techniques to address security and privacy challenges in these networks. D-SPAN provides a forum for academic and industry researchers to present research ideas that build bridges across three communities: wireless networks and databases, and security.

We address issues related to the protection of private information in Online Analytical Processing (OLAP) systems, where a major privacy concern is the adversarial inference of private information from OLAP query answers. Most previous work on privacy-preserving OLAP focuses on a single aggregate function and/or addresses only exact disclosure, which eliminates from consideration an important class of privacy breaches where partial information, but not exact values, of private data is disclosed (i.e., partial disclosure). We address privacy protection against both exact and partial disclosure in OLAP systems with mixed aggregate functions. In particular, we propose an information-theoretic inference control approach that supports a combination of common aggregate functions (e.g., COUNT, SUM, MIN, MAX, and MEDIAN) and guarantees the level of privacy disclosure not to exceed thresholds predetermined by the data owners. We demonstrate that our approach is efficient and can be implemented in existing OLAP systems with little modification. It also satisfies the simulatable auditing model and leaks no private information through query rejections. Through performance analysis, we show that compared with previous approaches, our approach provides more effective privacy protection while maintaining a higher level of query-answer availability.

Recently, there has been growing interest in random sampling from online hidden databases. These databases reside behind form-like web interfaces which allow users to execute search queries by specifying the desired values for certain attributes, and the system responds by returning a few (e.g., top-k) tuples that satisfy the selection conditions, sorted by a suitable scoring function. In this paper, we consider the problem of uniform random sampling over such hidden databases. A key challenge is to eliminate the skew of samples incurred by the selective return of highly ranked tuples. To address this challenge, all state-of-the-art samplers share a common approach: they do not use overflowing queries. This is done in order to avoid favoring highly ranked tuples and thus incurring high skew in the retrieved samples. However, not considering overflowing queries substantially impacts sampling efficiency.

This paper develops toolsets for eliminating algorithm-based disclosure from existing privacy-preserving data publishing algorithms. We first show that the space of algorithm-based disclosure is larger than previously believed and thus more prevalent and dangerous. Then, we formally define Algorithm-Safe Publishing (ASP) to model the threats from algorithm-based disclosure. To eliminate algorithm-based disclosure from existing data publishing algorithms, we propose two generic tools for revising their design: worst-case eligibility test and stratified pick-up. We demonstrate the effectiveness of our tools by using them to transform two popular existing l-diversity algorithms, Mondrian and Hilb, to SP-Mondrian and SP-Hilb which are algorithm-safe. We conduct extensive experiments to demonstrate the effectiveness of SP-Mondrian and SP-Hilb in terms of data utility and efficiency.

In this paper, we present 3DLoc: an integrated system of hardware and software toolkits for locating an 802.11-compliant mobile device in a three dimensional (3D) space. 3DLoc features two specialized antennas: an azimuth antenna and an elevation antenna, for detecting the azimuth and elevation angles of a mobile device respectively in real time. To improve positioning accuracy in real-world urban settings, we propose various signal processing techniques such as clustering and wavelet-transform based denoising, and present theoretical analysis of the accuracy of these techniques. With different antenna configurations, 3DLoc is able to track single or multiple targets in one round of azimuth scanning and elevation scanning. We conduct extensive experiments to demonstrate the efficiency and accuracy of 3DLoc. 3DLoc can be used in various applications, including wireless network forensics for locating anonymous criminal mobile devices.

Motivated by the insufficiency of the existing quasi-identifier/sensitive-attribute (QI-SA) framework on modeling real-world privacy requirements for data publishing, we propose a novel versatile publishing scheme with which privacy requirements can be specified as an arbitrary set of privacy rules over attributes in the microdata table. To enable versatile publishing, we introduce the Guardian Normal Form (GNF), a novel method of publishing multiple sub-tables such that each sub-table is anonymized by an existing QI-SA publishing algorithm, while the combination of all published tables guarantees all privacy rules. We devise two algorithms, Guardian Decomposition (GD) and Utility-aware Decomposition (UAD), for decomposing a microdata table into GNF, and present extensive experiments over real-world datasets to demonstrate the effectiveness of both algorithms.

In many practical applications of wireless sensor networks, it is crucial to accomplish the localization of sensors within a given time bound. We find that the traditional definition of relative localization is inappropriate for evaluating its actual overhead. To address this problem, we define a novel problem called essential localization, and present the first rigorous study on the essential localizability of a wireless sensor network within a given time bound. We propose an efficient distributed algorithm for time-bounded essential localization over a sensor network, and evaluate the performance of our algorithm with extensive simulations.

Many websites provide restrictive form-like interfaces which allow users to execute search queries on the underlying hidden databases. In this paper, we consider the problem of estimating the size of a hidden database through its web interface. We propose novel techniques which use a small number of queries to produce unbiased estimates with small variance. These techniques can also be used for approximate query processing over hidden databases. We present theoretical analysis and extensive experiments to illustrate the effectiveness of our approach.

Abstract—Internet Threat Monitoring (ITM) systems are a widely deployed facility to detect, analyze, and characterize dangerous Internet threats such as worms and distributed denial-of-service (DDoS) attacks. Nonetheless, an ITM system can also become the target of attacks. In this paper, we address localization attacks against ITM systems in which an attacker impairs the effectiveness of an ITM system by identifying the locations of ITM monitors. We propose an information-theoretic framework that models localization attacks as communication channels. Based on this model, we generalize all existing attacks as “temporal attacks”, derive closed formulae of their performance, and propose an effective attack detection approach. The information-theoretic model also inspires a new attack called a spatial attack and motivates the corresponding detection approach. We show simulation results that support our theoretic findings.

In this paper, we address issues related to the modeling, analysis, and countermeasures of worm attacks on the Internet. Most previous work assumed that a worm always propagates itself at the highest possible speed. Some newly developed worms (e.g., “Atak” worm) contradict this assumption by deliberately reducing the propagation speed in order to avoid detection. As such, we study a new class of worms, referred to as self-disciplinary worms. These worms adapt their propagation patterns in order to reduce the probability of detection, and eventually, to infect more computers. We demonstrate that existing worm detection schemes based on traffic volume and variance cannot effectively defend against these self-disciplinary worms. To develop proper countermeasures, we introduce a game-theoretic formulation to model the interaction between the worm propagator and the defender. We show that an effective integration of multiple countermeasure schemes (e.g., worm detection and forensics analysis) is critical for defending against self-disciplinary worms. We propose different integrated schemes for fighting different self-disciplinary worms, and evaluate their performance via real-world traffic data.

We address issues related to establishing a defender's reputation in anomaly detection against two types of attackers: 1) smart insiders, who learn from historic attacks and adapt their strategies to avoid detection/punishment, and 2) naïve attackers, who blindly launch their attacks without knowledge of the history. In this paper, we propose two novel algorithms for reputation establishment--one for systems solely consisting of smart insiders and the other for systems in which both smart insiders and naïve attackers are present. The theoretical analysis and performance evaluation show that our reputation-establishment algorithms can significantly improve the performance of anomaly detection against insider attacks in terms of the tradeoff between detection and false positives.

"The Marauder's Map" is a magical map in J. K. Rowling's fantasy series, "Harry Potter and the Prisoner of Azkaban". It shows all moving objects within the boundary of the "Hogwarts School of Witchcraft and Wizardry". In this paper, we introduce a similar attack to location privacy in wireless networks. Our system, namely the digital Marauder's map, can reveal the locations of WiFi-enabled mobile devices within the coverage area of a single high-gain antenna. The digital Marauder's map is built solely with off-the-shelf wireless equipments, and features a mobile design that can be quickly deployed to a new location and instantly used without training. We present a comprehensive set of theoretical analysis and experimental results which demonstrate the coverage and localization accuracy of the digital Marauder's map.

We address issues related to privacy protection in location-based services (LBS). Most existing research in this field either requires a trusted third-party (anonymizer) or uses oblivious protocols that are computationally and communicationally expensive. Our design of privacy-preserving techniques is principled on not requiring a trusted third-party while being highly efficient in terms of time and space complexities. The problem has two interesting and challenging characteristics: First, the degree of privacy protection and LBS accuracy depends on the context, such as population and road density, around a user's location. Second, an adversary may violate a user's location privacy in two ways: (i) based on the user's location information contained in the LBS query payload, and (ii) by inferring a user's geographical location based on its device's IP address. To address these challenges, we introduce CAP, a Context-Aware Privacy-preserving LBS system with integrated protection for data privacy and communication anonymity. We have implemented CAP and integrated it with Google Maps, a popular LBS system. Theoretical analysis and experimental results validate CAP's effectiveness on privacy protection, LBS accuracy, and communication Quality-of-Service.

A large number of online databases are hidden behind form-like interfaces which allow users to execute search queries by specifying selection conditions in the interface. Most of these interfaces return restricted answers (e.g., only top-k of the selected tuples), while many of them also accompany each answer with the COUNT of the selected tuples. In this paper, we propose techniques which leverage the COUNT information to efficiently acquire unbiased samples of the hidden database. We also discuss variants for interfaces which do not provide COUNT information. We conduct extensive experiments to illustrate the efficiency and accuracy of our techniques.

Many websites provide form-like interfaces which allow users to execute search queries on the underlying hidden databases. In this paper, we explain the importance of protecting sensitive aggregate information of hidden databases from being disclosed through individual tuples returned by the search queries. This stands in contrast to the traditional privacy problem where individual tuples must be protected while ensuring access to aggregating information. We propose techniques to thwart bots from sampling the hidden database to infer aggregate information. We present theoretical analysis and extensive experiments to illustrate the effectiveness of our approach.

A large number of online databases are hidden behind the web. Users to these systems can form queries through web forms to retrieve a small sample of the database. Sampling such hidden databases is widely desired for understanding the nature and quality of data stored in them. We have developed HDSampler, which to the best of our knowledge is the first practical system for sampling structured hidden web databases. It enables efficient sampling of the databases and accurate answering of aggregate queries, to provide analysts with valuable information for data analytics, as well as help power a multitude of third-party applications such as web-mashups and meta-search engines. For the purpose of this demo, we present an instance of HDSampler on Google Base - a content-rich hidden web database maintained by Google. By using HDSampler, the demo reveals a snapshot of the marginal distribution of various attributes of Google Base in a matter of minutes.

Internet threat monitoring (ITM) systems are a widely deployed facility to detect, analyze, and characterize dangerous Internet threats such as worms and distributed denial-of-service (DDoS) attacks. Nonetheless, an ITM system can also become the target of attack. In this paper, we address localization attacks against ITM systems in which an attacker impairs the effectiveness of ITM systems by identifying the locations of ITM monitors. We propose an information-theoretic framework for the modeling of localization attacks as communication channels. Based on the information-theoretic model, we generalize all existing attacks as ldquotemporal attacksrdquo, derive closed formulae of their performance, and propose an effective detection approach. The information-theoretic model also inspires a new attack called a spatial attack and motivates the corresponding detection approach. We show simulation results that support our theoretic findings.

We address issues related to the establishment of defender's reputation in anomaly detection against insider attacks. We consider two types of attackers: smart insiders, which learn from historic attacks and adapt their strategies to avoid detection/punishment, and naive attackers, which blindly launch their attacks. We introduce two novel reputation-establishment algorithms for systems with solely smart insiders and systems with both smart insiders and naive attackers, respectively. Theoretical analysis and simulation results show that our reputation-establishment algorithms can significantly improve the performance of anomaly detection against insider attacks in terms of the tradeoff between detection and false positives.

We address issues related to sharing information in a distributed system consisting of autonomous entities, each of which holds a private database. We consider threats from malicious adversaries that can deviate from the designated protocol and change their input databases. We classify malicious adversaries into two widely existing subclasses, namely weakly and strongly malicious adversaries, and propose protocols that can effectively and efficiently protect privacy against malicious adversaries.

We address issues related to privacy protection in distributed information sharing systems where multiple autonomous entities share data across their private databases. Most existing solutions place restrictions on adversarial behavior in order to enable communication-efficient privacy-preserving information sharing. These restrictions substantially underestimate the capabilities of adversaries in reality, and do not always suffice for real systems. We consider a threat space containing more powerful adversaries, including not only semi-honest but also malicious ones, and analyze the tradeoff between privacy protection and communication complexity in information sharing. In particular, we use Kolmogorov complexity to derive lower bounds on the communication complexity required to defend against various kinds of adversaries.

We address privacy-preserving classification problem in a distributed system. Randomization has been the approach proposed to preserve privacy in such scenario. However, this approach is now proven to be insecure as it has been discovered that some privacy intrusion techniques can be used to reconstruct private information from the randomized data tuples. We introduce an algebraic-technique-based scheme. Compared to the randomization approach, our new scheme can build classifiers more accurately but disclose less private information. Furthermore, our new scheme can be readily integrated as a middleware with existing systems.

We address the inference control problem in data cubes with some data known to users through external knowledge. The goal of inference controls is to prevent exact values of sensitive data from being inferred through answers to online analytical processing (OLAP) queries. We present an information theoretic approach for cardinality-based inference control, which simply counts the number of cells that all queries have covered thus far to determine whether a new query should be answered. Compared to previous approaches in sum-only data cubes, our new approach has a more general framework (applies to MIN, MAX and SUM) and is more effective.