INFOCOM 2016 论文列表

Due to the asynchronous and distributed nature of the data plane, consistent configuration updating across multiple switches is a challenging issue in Software-Defined Networking (SDN). The existing version-stamping-based mechanism (VSM) could guarantee per-packet consistency, but this mechanism is designed for non-adversarial settings and can be compromised easily by a malicious attacker. In this paper, we propose an efficient flow-ordered update mechanism that aims to provide per-packet consistency in adversarial settings. Our proposal does not need to stamp data packets with the configuration version, and is robust against both the packet-tampering and packet-dropping attacks. It outperforms a naive mechanism that simply patches VSM using digital signatures in three aspects: First, the switches in this mechanism only need to sign and verify a single control packet, which significantly improves the packet processing time. Second, it avoids keeping both old and new policies on switches during the update, and thus achieves better space efficiency. Third, it reduces the time delay for new policies to come into force. We evaluate our mechanism on a self-constructed SDN testbed and the results demonstrate high efficiency.

The high sampling rate in Wi-Fi is set to support bandwidth-hungry applications. It becomes energy inefficient in the post-PC era in which the emerging low-end smart devices increase the disparity in workloads. Recent advances scale down the receiver's sampling rates by leveraging the redundancy in the physical layer (PHY), which, however, requires packet modifications or very high signal-to-noise ratio (SNR). To overcome these limitations, we propose Sampleless Wi-Fi, a standard compatible solution that allows energy-constrained devices to scale down their sampling rates regardless of channel conditions. Inspired by rateless codes, Sampleless Wi-Fi recovers under-sampled packets by accumulating redundancy in packet retransmissions. To harvest the diversity gain as rateless codes without modifying legacy packets, Sampleless Wi-Fi creates new constellation diversity by exploiting the time shift effect at receivers. Our evaluation using GNURadio/USRP platform and real Wi-Fi traces have demonstrated that Sampleless Wi-Fi significantly outperforms the state-of-the-art downclocking technique in both decoding performance and energy efficiency.

Extremely low-cost passive RFID tags have become key components for the Internet of Things (IoT), where ubiquitous object locating is one of the most important functions. Although the number of tags in indoor environment continues growing fast, objects cannot be always assumed tagged, whether intentionally or unintentionally. Compared to tagged objects, a tagless target which neither emits nor modulates signal is much more difficult to locate, especially when the size is small. In this paper, we achieve accurate tagless object locating through a dense and wide non-uniform sampling in the Fourier domain of target reflectivity with the help of ambient passive RFID tags as landmarks. Unlike conventional RFID systems, we leverage nonlinearity in passive tags to backscatter second harmonic signals. The frequency separation of uplink and downlink in harmonic RFID allows ready interference cancellation. We embrace spatial diversity enabled by ambient tags and frequency diversity by broadband harmonic backscattering to improve accuracy and robustness. We present the fundamental theory and a prototype system to verify the proposed approach.

Offloading part of cellular traffic through existing alternative wireless networks, such as femtocells and WiFi networks, is one promising solution to the severe traffic overload faced by cellular network providers (CSPs) nowadays. Most existing cellular offloading auction mechanisms assume the CSP has the knowledge of incoming overloaded traffic demand, and satisfy the demand by offloading. However, in practice, with the explosive growth of mobile device communications, the overloaded traffic demand at CSPs is very likely to pass over the total capability that third-party resource owners can provide. Then it is critical to enable CSPs to optimize the traffic handling capacity gain through offloading with budget constraints. In this paper, we propose two efficient Competitive Auction MEchanisms for mObile offloading, CAMEO-min and CAMEO-ws. Both mechanisms are proven to be non-budget-deficit, individually rational and incentive-compatible, and have guaranteed lower bounds on the ratio of the CSP's gain achieved in them to the maximum gain that the CSP could achieve in any omniscient auction (the auction with an omniscient auctioneer). Our extensive evaluations show that CAMEOs achieve very good performance in terms of the maximization of the CSP's gain especially when the global bidder dominance or the region dominance is big.

Nearest neighbor search (or k-nearest neighbor search in general) is one of the most fundamental queries on massive datasets, and it has extensive applications such as pattern recognition, statistical classification, graph algorithms, Location-Based Services and online recommendations. With the raising trend of outsourcing massive sensitive datasets to public clouds, it is urgent for companies and organizations to demand fast and secure nearest neighbor search solutions over their outsourced data, but without revealing privacy to untrusted clouds. However, existing solutions for secure nearest neighbor search still face significant limitations, which make them far from practice. In this paper, we propose a new searchable encryption scheme, which can efficiently and securely enable nearest neighbor search over encrypted data on untrusted clouds. Specifically, we modify the search algorithm of nearest neighbors with tree structures (e.g., R-trees), where the modified algorithm adapts to lightweight cryptographic primitives (e.g., Order-Preserving Encryption) without affecting the original faster-than-linear search complexity. As a result, we address all the limitations in the previous works while still maintaining correctness and security. Moreover, our design is general, which can be used for secure k-nearest neighbor search, and it is compatible with other similar tree structures. Our experimental results on Amazon EC2 show that our scheme is extremely practical over massive datasets.

As one type of the most popular cloud storage services, OpenStack Swift and its follow-up systems replicate each data object across multiple storage nodes and leverage object sync protocols to achieve high availability and eventual consistency. The performance of object sync protocols heavily relies on two key parameters: r (number of replicas for each object) and η (number of objects hosted by each storage node). In existing tutorials and demos, the configurations are usually r = 3 and n3 and n ≫ 1000, the object sync process is significantly delayed and produces massive network overhead. This phenomenon is referred to as the sync bottleneck problem. Then, to explore the root cause, we review the source code of OpenStack Swift and find that its object sync protocol utilizes a fairly simple and network-intensive approach to check the consistency among replicas of objects. In particular, each storage node is required to periodically multicast the hash values of all its hosted objects to all the other replica nodes. Thus in a sync round, the number of exchanged hash values per node is Θ(n×r). Further, to tackle the problem, we propose a lightweight object sync protocol called LightSync. It remarkably reduces the sync overhead by using two novel building blocks: 1) Hashing of Hashes, which aggregates all the h hash values of each data partition into a single but representative hash value with the Merkle tree; 2) Circular Hash Checking, which checks the consistency of different partition replicas by only sending the aggregated hash value to the clockwise neighbor. Its design provably reduces the per-node network overhead from Θ(n×r) to Θ(n/h). In addition, we have implemented LightSync as an open-source patch and adopted it to OpenStack Swift, thus reducing sync delay by up to 28.8× and network overhead by up to 14.2×.

We present AMPLES, Approximate Matching of Persistent LExicon using Search-Engines, to address the Mobile-Application-Identification (MApId) problem in network traffic at a per-flow granularity. We transform MApId into an information-retrieval problem where lexical similarity of short-text-documents is used as a metric for classification tasks. Specifically, a network-flow, observed at an intercept-point, is treated as a semi-structured-text-document and modified into a flow-query. This query is then run against a corpus of documents pre-indexed in a search-engine. Each index-document represents an application, and consists of distinguishable identifiers from the metadata-file and URL-strings found in the application's executable-archive. The search-engine acts as a kernel function, generating a score distribution vis-'a-vis the index-documents, to determine a match. This extends the scope of MApId to fuzzy-classification mapping a flow to a family of apps when the score distribution is spread-out. Through experiments over an emulator-generated test-dataset (400 K applications and 13.5 million flows), we obtain over 80% flow coverage and about 85% application coverage with low false-positives (4%) and nearly no false-negatives. We also validate our methodology over a real network trace. Most importantly, our methodology is platform agnostic, and subsumes previous studies, most of which focus solely on the application coverage.

Software-Defined Networks (SDN) greatly improves programmability but brings in extra challenges for debugging. We propose an SDN debugging framework, Monitor-Emulator-Debugger (MED). It closely monitors the physical network, and automatically creates an emulator that can be set to the network state at any given point of time. In the emulator, MED synchronously constructs a virtual SDN that is identical to the physical SDN and replays real packet samples. The emulator also handles the non-determinism due to packet reordering. On top of the emulator, we provide fast and efficient debugging tools including loop and reachability detector, race condition detector and forwarding table checker. All the tools run on the emulator without adding any additional overhead to the physical SDN. We implement MED for an OpenFlow-based SDN in a data center network employing 20 switches. Using a combination of micro-benchmarks and real debugging case studies, we show that MED is both fast and useful in SDN debugging. During the evaluation, we reveal two physical switch bugs that have been confirmed by the vendor.

Nowadays, cyber criminals often build web infrastructures rather than a single server to conduct their malicious activities. In order to continue their malevolent activities without being detected, cyber criminals make efforts to conceal the core servers (e.g., C&C servers, exploit servers, and drop-zone servers) in the malicious web infrastructure. Such deliberate invisibility of those concealed malicious servers, however, makes them particularly distinguishable from benign web servers that are usually promoted to be public. In this paper, we conduct the first large-scale measurement study to investigate the visibility of both malicious and benign servers. From our intensive analysis of over 100,000 benign servers, 45,000 malicious servers and 40,000 redirections, we identify a set of distinct features of malicious web infrastructures from their locations, structures, roles, and relationships perspectives, and propose a lightweight yet effective detection system called VisHunter. VisHunter identifies malicious redirections from visible servers to invisible servers at the entryway of malicious web infrastructures. We evaluate VisHunter on both online public data and large-scale enterprise network traffic, and demonstrate that VisHunter can achieve an average 96.2% detection rate with only 0.9% false positive rate on the real enterprise network traffic.

We study consistent migration of flows, with special focus on software defined networks. Given a current and a desired network flow configuration, we give the first polynomial-time algorithm to decide if a congestion-free migration is possible. However, if all flows must be integer or are unsplittable, this is NP-hard to decide. A similar problem is providing increased bandwidth to an application, while keeping all other flows in the network, but possibly migrating them consistently to other paths. We show that the maximum increase can be approximated arbitrarily well in polynomial time. Current methods as RSVP-TE consider unsplittable flows and remove flows of lesser importance in order to increase bandwidth for an application: We prove that deciding what flows need to be removed is an NP-hard optimization problem with no PTAS possible unless P = NP.

Indoor localization based on RSS fingerprinting approach has been attracting many research efforts in the past decades. Recent study presents a fundamental limit of the approach: given requirement of estimation accuracy, reliability of the user's localization result can be derived. As highly accurate indoor localization is essential to enable many location based services, a natural question to ask is: can we further improve the accuracy of the localization scheme fundamentally? In this paper, we theoretically show that the temporal correlation of the RSS can improve accuracy of the RSS fingerprinting based indoor localization. In particular, we construct a theoretical framework to evaluate how the temporal correlation of the RSS can influence the reliability of location estimation, which is based on a newly proposed radio propagation model considering the time-varying property of signals from a given Wi-Fi AP. Such a theoretical framework is then applied to analyze localization in the one dimensional physical space, which reveals the fundamental reason why performance improvement of localization can be brought by temporal correlation of the RSS. We further extend our analysis to high-dimensional scenarios. Experimental results corroborate our theoretical analysis.

We consider the problem of scheduling VMs (Virtual Machines) in a multi-server system motivated by cloud computing applications. VMs arrive dynamically over time and require various amounts of resources (e.g., CPU, Memory, Storage, etc.) for the duration of their service. When a VM arrives, it is queued and later served by one of the servers that has sufficient remaining capacity to serve it. The scheduling of VMs is subject to: (i) packing constraints, i.e., multiple VMs can be be served simultaneously by a single server if their cumulative resource requirement does not violate the capacity of the server, and (ii) non-preemption, i.e., once a VM is scheduled in a server, it cannot be interrupted or migrated to another server. To achieve maximum throughput, prior results hinge on solving a hard combinatorial problem (Knapsack) at the instances that all the servers become empty (the so-called global refresh times which require synchronization among the servers). The main contribution of this paper is that it resolves these issues. Specifically, we present a class of randomized algorithms for placing VMs in the servers that can achieve maximum throughput without preemptions. The algorithms are naturally distributed, have low complexity, and each queue needs to perform limited operations. Further, our algorithms display good delay performance in simulations, comparable to delay of heuristics that may not be throughput-optimal, and much better than the delay of the prior known throughput-optimal algorithms.

Response time plays a key role in Web services, as it significantly impacts user engagement, and consequently the Web providers' revenue. Using a large search engine as a case study, we propose a machine learning based analysis framework, called FOCUS, as the first step to automatically debug high search response time (HSRT) in search logs. The output of FOCUS offers a promising starting point for operators' further investigation. FOCUS has been deployed in one of the largest search engines for 2.5 months and analyzed about one billion search logs. Compared with a previous approach, FOCUS generates 90% less items for investigation and achieves both higher recall and higher precision. The results of FOCUS enable us to make several interesting observations. For example, we find that popular queries are more image-intensive (e.g., TV series and shopping), but they have relatively low SRT because they are cached well by servers. Additionally, as suggested by the first-month analysis results of FOCUS, we conduct an optimization on image transmission time. A one-month real-world deployment shows that we successfully reduce the 80th percentile of search response time by 253ms, and reduce the fraction of HSRT by one third.

With the advent of big data, modern businesses face an increasing need to store and process large volumes of sensitive customer information on the cloud. In these environments, resources are shared across a multitude of mutually untrusting tenants increasing propensity for data leakage. This problem stands to grow further in severity with increasing use of clouds in all aspects of our daily lives and the recent spate of high-profile data exfiltration attacks are evidence. To highlight this serious issue, we present a novel and highspeed network-based covert channel that is robust and circumvents a broad set of security mechanisms currently deployed by cloud vendors. We successfully test our channel on numerous network environments, including commercial clouds such as EC2 and Azure. Using an information theoretic model of the channel, we derive an upper bound on the maximum information rate and propose an optimal coding scheme. Our adaptive decoding algorithm caters to the cross traffic in the channel and maintains high bit rates and extremely low error rates. Finally, we discuss several effective avenues for mitigation of the aforementioned channel and provide insights into how data exfiltration can be prevented in such shared environments.

Multipath TCP (MPTCP) enables the simultaneous use of multiple links for bandwidth aggregation, better resource utilization and improved reliability. Its coupled congestion control intends to reap the increased bandwidth of multiple links, while avoiding being more aggressive than regular TCP flows on every used link. We argue that this leads to a very conservative behavior when paths do not share a bottleneck. Therefore, in this paper, we first quantify the penalty of the coupled congestion control for links that do not share a bottleneck. Then, in order to overcome this penalty, we design and implement a practical shared bottleneck detection (SBD) algorithm for MPTCP, namely MPTCP-SBD. Through extensive emulations, we show that MPTCP-SBD outperforms all currently deployed MPTCP coupled congestion controls by accurately detecting bottlenecks. For the non-shared bottleneck scenario, we observe throughput gains of up to 40% with two subflows and the gains increase significantly as the number of subflows increase, reaching more than 100% for five subflows. Furthermore, for the shared bottleneck scenario, we show that MPTCP-SBD remains fair to TCP. We complement the emulation results with real-network experiments justifying its safeness for deployment.

Cloud computing generally needs to handle large amounts of data in a real-time manner. Typical metrics include fast write and query performance. However, existing cloud systems fail to efficiently offer fast query and write services due to two main reasons. One is the design separation between query and write operations. Most schemes mainly optimize one aspect. The other is the lack of cost-efficient data analytics, which leads to the identical resource consumption for each data item. In order to address the two problems and efficiently support fast query and write services, this paper proposes a novel flat-addressing scheme, called Cheetah. The idea behind Cheetah is to leverage efficient online data compression to reduce the amounts of data to be written, and meantime make use of a flat-addressing cuckoo hashing scheme to support fast query service. In practice, conventional cuckoo hashing schemes suffer from the endless loops, thus not only leading to insertion failure but also causing long operation latency. In order to alleviate the endless loops in item insertion, we use extra space to temporarily store the items that cause hash collisions, which are often shared by multiple loops. In order to further improve system performance, we prefetch the collision data in a batch to further reduce the probability of the occurrence of endless loops, thus offering fast query services to identify the searched items. Extensive experimental results demonstrate that the flat-addressing Cheetah can efficiently support query services in the cloud.

Advances in cloud computing have greatly motivated data owners to outsource their huge amount of personal multimedia data and/or computationally expensive tasks onto the semi-trusted cloud by leveraging its abundant resources for cost saving and flexibility. From the privacy perspective, however, the outsourced multimedia data and its originated applications may reveal the data owner's private information, such as the personal identity, locations or even financial profiles. This observation has recently aroused new research interest on privacy-preserving computations over outsourced multimedia data. In this paper, we propose an effective privacy-preserving computation outsourcing protocol for the prevailing scale-invariant feature transform (SIFT) over massive encrypted image data. We first show that previous solutions to this problem have either efficiency/security or practicality issues, and none can well preserve the important characteristics of the original SIFT in terms of distinctiveness and robustness. We for the first time present a new privacy-preserving outsourcing protocol for SIFT with the preservation of its key characteristics, by randomly splitting the original image data, carefully distributing the feature extraction computations to two independent cloud servers and further leveraging the garbled circuit for secure keypoints comparisons. We both carefully analyze and extensively evaluate the security and effectiveness of our design. The results show that our solution is practically secure, outperforms the state-of-the-art and performs comparably to the original SIFT in terms of various characteristics, including rotation invariance, image scale invariance, robust matching across affine distortion and change in 3D viewpoint.

Implanted sensors and actuators in the human body promise in-situ health monitoring and rapid advancements in personalized medicine. We propose a new paradigm where such implants may communicate wirelessly through a technique called as galvanic coupling, which uses weak electrical signals and the conduction properties of body tissues. While galvanic coupling overcomes the problem of massive absorption of RF waves in the body, the unique intra-body channel raises several questions on the topology of the implants and the external (i.e., on skin) data collection nodes. This paper makes the first contributions towards (i) building an energy-efficient topology through optimal placement of data collection points/relays using measurement-driven tissue channel models, and (ii) balancing the energy consumption over the entire implant network so that the application needs are met. We achieve this via a two-phase iterative clustering algorithm for the implants and formulate an optimization problem that decides the position of external data-gathering points. Our theoretical results are validated via simulations and experimental studies on real tissues, with demonstrated increase in the network lifetime.

We study cloud-storage systems with a very large number of files stored in a very large number of servers. In such systems, files are either replicated or coded to ensure reliability, i.e., file recovery from server failures. This redundancy in storage can further be exploited to improve system performance (mean file access delay) through appropriate load-balancing (routing) schemes. However, it is unclear whether coding or replication is better from a system performance perspective since the corresponding queueing analysis of such systems is, in general, quite difficult except for the trivial case when the system load asymptotically tends to zero. Here, we study the more difficult case where the system load is not asymptotically zero. Using the fact that the system size is large, we obtain a mean-field limit for the steady-state distribution of the number of file access requests waiting at each server. We then use the mean-field limit to show that, for a given storage capacity per file, coding strictly outperforms replication at all traffic loads while improving reliability. Further, the factor by which the performance improves in the heavy-traffic is at least as large as in the light-traffic case. Finally, we validate these results through extensive simulations.