Passive sensing based on UHF RFID has increasingly proven its efficacy in various applications. However, existing security methods often face challenges in implementation on passive tags or fail to meet the high data read rates required by array sensing operations. To address these constraints, we introduce a novel security framework called PSC-tags, which is in line with the zero-trust security concept and well-suited for parallel deployment within RFID sensing array scenarios. PSC-tags leverages the phase sequence similarities inherent in tag arrays, leading to the development of an optimal tag group selection strategy. Concurrently, we customize a convolutional neural network incorporating an attention mechanism for authentication. This method is applied to XRF55, which is a comprehensive dataset of human indoor activities, as well as a sub–dataset collected in real–world scenarios. Extensive experimental results demonstrate the effectiveness of PSC-tags, with an average accuracy of 98.5% and only 56 milliseconds of authentication time per sample required. Notably, PSC-tags is compatible with commercial off-the-shelf (COTS) devices and does not require any additional data acquisition. The method significantly fortifies the defenses against multiple attacks within RFID array sensing.

The widespread use of modern network communications necessitates effective resource control and management in TCP/IP networks. However, most existing network traffic classification methods are limited to labeled known classes and struggle to handle open-set scenarios, where known classes coexist with significant volumes of unknown classes of traffic. To solve this problem more accurately and reliably, we propose RoNeTC. This method achieves high-precision classification by enhancing feature extraction and quantifying the reliability of classification decisions through uncertainty estimation. For feature extraction, we divide each packet of a flow into three views for parallel training, integrating both local and global feature representations across multiple packets to enhance accuracy. We devise a second-order classification probability to quantify the reliability of the classifier’s results and to visualize the reliability of open-set flow classification in terms of uncertainty. Additionally, we dynamically fuse classification decisions from multiple views, evaluating decision uncertainty to classify known and unknown flows and ensure robust, reliable results. We compare RoNeTC with four state-of-the-art (SOTA) methods in six open-set scenarios. RoNeTC outperforms the other methods by an average of 25.94% in F1 across all open-set scenarios, indicating its superior performance in open-set network traffic classification.

For the creation of wireless network applications, node locations are frequently necessary. However, communication effectiveness, measurement accuracy, and localization stability will be low in irregular multi-hop networks when locating nodes using conventional algorithms. To this end, a novel cooperative localization algorithm using expected minimum segments (LEMS, for short) is proposed in this paper. LEMS begins by measuring the distance between paired nodes, which is completed along with network initialization. Then, each unlocated node constructs its own sub-network, including it, based on the error characteristics among anchor nodes. Finally, each unlocated node searches for its estimated location in its sub-region based on the objective function generated by the chaotic mapping. Simulation results demonstrate that the proposed algorithm significantly outperforms the state-of-the-art regarding efficiency, accuracy, and stability for various irregular networks. Specifically, our proposed algorithm achieves a median improvement in localization accuracy of 0.62 to 29.57 times and a reduction in the range of localization errors of 0.06 to 16.8 times.

Accurate geographical information of nodes is crucial for network applications. However, many existing positioning algorithms face challenges in achieving efficient, accurate, and robust performance when applied to irregular networks with holes or obstacles. Therefore, we introduce a new algorithm, named Network Division Positioning (NDP), to tackle this issue. In NDP, we use a similarity function to derive the distance between neighboring nodes and explore routing paths concurrently, facilitating efficient distance measurement. Next, we analyze measurement errors between landmark nodes to define a threshold that filters out incorrect distances, ensuring measuring and positioning accuracy. To enhance robustness, we first identify collinearity issues by examining the positional relationship between unpositioned nodes and their nearest landmark. Subsequently, we addressed the poor positioning results and built the subnetwork utilizing the nearest landmark node and its associated measurement distance, seeking the most accurate and robust estimated position within this subnetwork. The simulation results demonstrate that NDP outperforms state-of-the-art algorithms in terms of efficiency, accuracy, and robustness when dealing with various irregular networks. Specifically, NDP enhances positioning accuracy by at least 40.82% in terms of the median.

gVisor is a Google-published application-level kernel for containers. As gVisor is lightweight and has sound isolation, it has been widely used in many IT enterprises [1],[2],[3]. When a new vulnerability of the upstream gVisor is found, it is important for the downstream developers to test the corresponding code to maintain the security. To achieve this aim, directed fuzzing is promising. Nevertheless, there are many challenges in applying existing directed fuzzing methods for gVisor. The core reason is that existing directed fuzzers are mainly for general C/C++ applications, while gVisor is an OS kernel written in the Go language. To address the above challenges, we propose G-Fuzz, a directed fuzzing framework for gVisor. There are three core methods in G-Fuzz, including lightweight and fine-grained distance calculation, target related syscall inference and utilization, and exploration and exploitation dynamic switch. Note that the methods of G-Fuzz are general and can be transferred to other OS kernels. We conduct extensive experiments to evaluate the performance of G-Fuzz. Compared to Syzkaller, the state-of-the-art kernel fuzzer, G-Fuzz outperforms it significantly. Furthermore, we have rigorously evaluated the importance for each core method of G-Fuzz. G-Fuzz has been deployed in industry and has detected multiple serious vulnerabilities.

Wireless Power Transfer (WPT) has received more and more attention for its convenience and reliability. In this paper, we first propose the notion of omnidirectional charging. First, we consider the problem of detecting whether the target area achieves omnidirectional charging given a deterministic deployment of chargers. We use piecewise constant approximation and area discretization techniques to partition the target area and approximate charging power as constants. Next, we propose the Minimum Coverage Set extraction technique to design a fast detection algorithm. Second, we design a charger deployment scheme that satisfies omnidirectional charging. By placing the chargers at the triangle lattice points, we estimate the length of triangle lattice side length that satisfies omnidirectional charging, and derive the error bound with the optimal length. Third, we determine the probability that the target area achieves omnidirectional charging given a random deployment of chargers. We devise both analytical and numerical solutions for the problem with good accuracy. Finally, we conduct simulation and field experiments, and the results show that the running speed of our omnidirectional charging detection algorithm is at least$1\times$faster than comparison algorithms, and the consistency degree of our theoretical results and field experimental results is larger than$93.6 \%$.

This paper concerns the problem of the parameter optimization of an active Physical-Layer Authentication (PLA) scheme, which is crucial for minimizing the distortion on the base signal carrying the original message caused by embedding a tag. An inappropriate parameter may significantly lower the efficiency of the entire period of message transmission. In this paper, we propose an optimization framework for an active PLA scheme and further propose a new systematic metric, defined as Secure Authentication Efficiency (SAE). In the proposed framework, we minimize the aforementioned distortion by tuning three parameters, i.e., the Probability of Message Transmission (PMT), the Probability of Message Outage (PMO), and the Probability of Secure Authentication (PSA). The proposed optimization framework deepens the understanding of the correlation between the parameters of an active PLA scheme and the conditions of a wireless channel, and allows us to systematically optimize the parameters of the active PLA scheme. Then, we establish an objective function by maximizing the SAE with both PMT and PMO constraints. We implement our approach and conduct extensive performance comparisons. Our experimental results show that when the SNR at the receiver is more than 15 dB, our approach achieves an average SAE of greater than 80%, whereas the prior scheme without parameter optimization degenerates to zero SAE under some conditions, e.g., high SNR at adversary or high communication rate.

Physical-Layer Authentication (PLA) attracts a lot of research interests because of its significant advantages over upper-layer authentication mechanisms: high security and low complexity. The PLA schemes can be categorized into passive and active schemes. In this paper, we extensively leverage the advantages of both the active and passive schemes as a reference scheme, named as the Direct Hybrid (DH) scheme. Although the DH scheme improves the authentication performance of the prior PLA schemes, it has limitations, e.g., high communication overhead. Then, we further propose two hybrid PLA schemes to overcome the limitations of the DH scheme. The first proposed scheme further uses the advantage of the Challenge-Response Authentication Mechanism (CRAM) scheme, named as the CR-based Hybrid (CRH) scheme. Although both DH and CRH schemes significantly improve the authentication performance of the prior PLA schemes, they do not address one significant limitation of the active scheme, i.e., to set the power allocation of a tag empirically. Thus, based on the CRH scheme, we further propose the Adaptive CR-Based Hybrid (ACRH) scheme to adaptively set the parameter instead of the empirical setting. Moreover, we provide the theoretical analysis of the proposed schemes over wireless fading channels and derive their closed-form expressions in terms of the Probability of Detection (PD), Probability of False Alarm (PFA), and optimal threshold, respectively. At last, we discuss the advantages and disadvantages of the proposed schemes and give some useful suggestions for seeking a better tradeoff. Our experimental results show that, in comparison with the active scheme, the DH scheme has better robustness, and the CRH scheme has better both robustness and compatibility but it sacrifices the security. The ARCH scheme achieves a better tradeoff than the remaining schemes.

Mobile radio frequency identification (RFID) systems typically experience the continual movement of many tags rapidly going in and out of the interrogating range of readers. Readers that are deployed to maintain a current, real-time list of tags, which are present in the interrogating zone at any moment, must repeatedly execute a series of reading cycles. Each of these reading cycles provides the readers very limited time to identify unknown tags (those newly entering into the reader’s range), and, at the same time, to detect missing tags (those just leaving the reader’s range). In this paper, we study the continuous tag recognition problem, which is critical for mobile RFID systems. First, we obtain a lower bound on communication time for solving this problem. We then design a near-OPTimal protocoL, called OPT-L, and prove that its communication time is approximately equal to the lower bound. Finally, we present extensive simulation and experimental results that demonstrate OPT-L’s superior performance over other existing protocols.

Cloud service providers often provision excessive resources to meet the desired Service Level Objectives (SLOs), by setting lower CPU utilization targets. This can result in a waste of resources and a noticeable increase in power consumption in large-scale cloud deployments. To address this issue, this paper presents DeepScaling, an innovative solution for minimizing resource cost while ensuring SLO requirements are met in a dynamic, large-scale production microservice-based system. We propose DeepScaling, which introduces three innovative components to adaptively refine the target CPU utilization of servers in the data center, and we maintain it at a stable value to meet SLO constraints while using minimum amount of system resources. First, DeepScaling forecasts workloads for each service using a Spatio-temporal Graph Neural Network. Secondly, it estimates CPU utilization with a Deep Neural Network, considering factors such as periodic tasks and traffic. Finally, it uses a modified Deep Q-Network (DQN) to generate an autoscaling policy that controls service resources to maximize service stability while meeting SLOs. Evaluation of DeepScaling in Ant Group’s large-scale cloud environment shows that it outperforms state-of-the-art autoscaling approaches in terms of maintaining stable performance and resource savings. The deployment of DeepScaling in the real-world environment of 1900+ microservices saves the provisioning of over 100,000 CPU cores per day, on average.

With the rapid development of the Internet of Things (IoT) related technologies, the application of digital twins (DT) in industry and healthcare becomes possible. Human activity recognition (HAR) is emerging as a hot research area with great potential in healthcare. Activity recognition systems combined with DT will make it easier to monitor human health conditions to improve the quality of life and happiness with individualized healthcare. In this paper, we design an effective HAR system, called HAR-Net, which uses WiFi time series data collected by sensors to train a deep learning network. Deep learning’s great learning ability is utilized to extract features of various human activities for activity recognition. We built the DT system with Unity, which is combined with the HAR system. In the DT system, real-world physical activities are mapped onto human models. The results of activity prediction can be evaluated in real-time in DT, and warnings can be issued quickly when dangerous activities occur. To make our human activity recognition system more adaptive, we propose a one-shot recognition method based on meta-learning. Specifically, we design a Bi-path basic network that extracts features in the time-domain and frequency-domain, and a meta-learning framework with a classification module and a WiFi metric module. Using datasets from different environments, we conducted various experiments on HAR-Net, and the results proved that our presented method was superior to the baseline network.

Context-sensitivity is essential for achieving good precision in inter-procedural static analysis. To be context-sensitive, top-down analysis needs to fully inline all the statements in a callee at all its callsites, leading to statement explosion. Compositional analysis, which inlines summaries of all the callees, scales up but often loses precision, as it is not strictly context-sensitive. We propose a compositional and strictly context-sensitive framework for static analysis. This framework is based on a key observation: a compositional analysis often loses precision only on some critical statements that need to be analyzed context-sensitively. Our approach hybridly inlines the critical statements and the summaries of non-critical statements of each callee, thus avoiding re-analyzing non-critical ones. In addition, our analysis lazily summarizes the critical statements, by stopping propagating the critical statements once the calling context accumulated is adequate. We have designed and implemented several analyses (including a pointer analysis) based on this framework. Our evaluation on the pointer analysis shows that it can analyze large Java programs from the DaCapo benchmark suite and industry in minutes. Compared to context-insensitive analysis, Hybrid Inlining introduces only 65% and 1% additional time overheads on DaCapo and industrial applications, respectively.

Graph neural networks (GNNs) are a specialized type of deep learning models on graphs by learning aggregations over neighbor nodes. However, recent studies reveal that the performance of GNNs are severely deteriorated by injecting adversarial examples. Hence, improving the robustness of GNNs is of significant importance. Prior works are devoted to reducing the influence of direct adversaries which are adversarial attacks by positioning a node's one-hop neighbors, yet these approaches are limited in protecting GNNs from indirect adversarial attacks within a node's multi-hop neighbors. In this work, we approach this problem from a new angle by exploring the graph Ricci curvature, which can characterize the relationships of both direct and indirect links from any two nodes’ neighborhoods in the Riemannian space. We first investigate the distinguishable properties of adversarial attacks with graph Ricci curvature distribution. Then, a novel defense framework called Cure-GNN is proposed to detect and mitigate adversarial effects. Cure-GNN discerns the distinction between adversarial edges and normal edges via computing curvature, and merges it into the node features reconstructed by a residual learning framework. Extensive experiments over real-world datasets on node classification task demonstrate the efficacy of Cure-GNN and achieves superiority to the state-of-the-arts without incurring high complexity.

This paper is on designing a compact data structure for multi-set membership testing that allows fast set querying. Multi-set membership testing is a fundamental operation for computing systems. Most existing schemes for multi-set membership testing are built upon Bloom filter and fall short in either storage space cost or query speed. To address this issue, we propose Noisy Bloom Filter (NBF), Error Corrected Noisy Bloom Filter (NBF-E), and Data-driven Noisy Bloom Filter (NBF-D) in this paper. We optimize their misclassification and false positive rates by theoretical analysis and present criteria for selection between NBF, NBF-E, and NBF-D. The key novelty of the three schemes is to store set ID information in a compact but noisy way that allows fast recording and querying and use a denoising method for querying. Especially, NBF-E incorporates asymmetric error-correcting coding techniques into NBF, and NBF-D encodes set ID based on their cardinality. To evaluate NBF, NBF-E, and NBF-D in comparison with the prior art, we conducted experiments using real-world network traces. The results show that NBF, NBF-E, and NBF-D significantly advance the state-of-the-art on multi-set membership testing.

The fundamental issue of how to calculate the false positive probability of widely used Bloom Filters (BF), from which the conventional wisdom is to derive the optimal value of$k$, remains elusive. Since Bloom gave the false positive formula in 1970, in 2008, Boseet al. pointed out that Bloomˆs formula is flawed; and in 2010, Christensenet al. pointed out that Bose's formula is also flawed and gave another formula. Although Christensen's formula is perfectly accurate, it is time-consuming and impossible to calculate the optimal value of$k$. Based on the following observation: for a BF with$m$bits and$n$elements, if and only if its entropy is the largest, its false positive probability is the smallest, we propose the first approach to calculating the optimal$k$without any false positive formula. Furthermore, we propose a new and more accurate upper bound for the false positive probability. When the size of a Bloom Filter becomes infinitely large, our upper bound turns equal to the lower bound, which becomes Bloomˆs formula and deepens our understanding towards it. Besides, we derive the bounds of correct rate of Counting Bloom Filters (CBFs) by applying our proposed formulas about BFs to them.

WiFi channel state information (CSI) has emerged as a plausible modality for sensing different human vital signs, i.e., respiration and body motion, as a function of modulated wireless signals that travel between WiFi devices. Although a remarkable proposition, most of the existing research in this space struggles to withstand robust performance beyond experimental conditions. To this end, we take a careful look at the dynamics of WiFi signals under human respiration and body motions in the wild. We first characterize the WiFi signal components—multipath and signal subspace—that are modulated by human respiration and body motions. We extrapolate on a set of transformations, including first-order differentiation, max-min normalization and component projections, that faithfully explains and quantifies the dynamics of respiration and body motions on WiFi signals. Grounded in this characterization, we propose two methods: 1) a respiration tracking technique that models the peak dynamics observed in the time-varying signal subspace and 2) a body-motion tracking technique built with a multi-dimensional clustering of evolving signal subspace. Finally, we reflect on the manifestation of these techniques in a practical sleep monitoring application. Our systematic evaluation with over 550 hours of data from 5 users covering both line-of-sight (LOS) and non-line-of-sight (NLOS) settings shows that the proposed techniques can achieve comparable performance to purpose-built pulse-Doppler radar.

Interference is a serious problem in Wireless Body Area Networks (WBANs) and heavily weakens system performance. In this paper, we propose an exchange-free resource scheduling scheme to overcome the interference of dynamic coexisting WBANs. For each data transmission period, we design a transmission channel/slot allocation scheme based on a Latin square, where each character denotes a specific combination of a channel and a time slot. For each data retransmission period, we design a retransmission time-slot selection scheme based on a hash function, in which the unique identity information of the collided node is used to calculate the retransmission slot. Compared with existing solutions, our work has two key advantages. First, all nodes can independently allocate and coordinate resources rather than exchange information with each other in traditional methods, and thus guaranteeing strong adaptability to the fast changes of WBANs. Second, the contention-free resource allocation pattern is implemented for both the data transmission period as well as the data retransmission period, and thus guaranteeing no intra-WBAN interference and extremely low probability of inter-WBAN interference. Our simulation results show that interferences can be well addressed based on the metrics of the packet loss rate, throughput, power dissipation, and data delivery delay.

The cloud-assisted mobile edge computing system is a critical architecture to process computation-intensive and delay-sensitive mobile applications in close proximity to mobile users with high resource efficiency. Due to the heterogenous dynamics of task arrivals at edge nodes and the distributed nature of the system, the workloads of edge nodes are prone to be unbalanced, which can cause high task response time and resource cost. This paper solves the dynamic task scheduling problem in cloud-assisted mobile edge computing (including both peer task scheduling among edge nodes and cross-layer task scheduling from edge nodes to the cloud), aiming at minimizing average task response time within resource budget limit. To overcome the challenges of task arrival dynamics, edge node heterogeneity, and computation-communication delay tradeoff, we propose aWater-filling BasedDynamic TaskScheduling (WiDaS) algorithm. WiDaS dynamically tunes the usage of cloud resources based on the Lyapunov optimization method and efficiently schedules mobile tasks among edge nodes (and the cloud) by exploiting the idea of water filling. Extensive simulations are conducted to evaluate WiDaS under a trace-driven traffic pattern and two mathematic traffic patterns. The results demonstrate that WiDaS shows two-fold benefits of efficiency and effectiveness. In terms of efficiency, WiDaS can achieve the approximate results with the KKT-based algorithm while reducing the computation complexity from exponential order to polynomial order. In terms of effectiveness, WiDaS can reduce the average task response time by up to 64.4% and 47.2% over the Fair-ratio and the Edge-first algorithm.

Radio frequency identification technology has been widely used to verify the presence of items in many applications such as warehouse management and supply chain logistics. In these applications, the challenge of how to timely identify the missing tags (namely tag searching or missing tag identification) is a key focus. Existing missing tag identification solutions have not achieved their full potentials because collision slots have not been well explored. In this paper, we propose an approach named collision resolving based missing tag identification (CR-MTI) to break through the performance bottleneck of existing missing tag identification protocols. In CR-MTI, multiple tags are allowed to respond with different binary strings in a collision slot. Then, the reader can verify them together by using the bit tracking technology and particularly designed string, thereby significantly improve the time efficiency. CR-MTI also reduces the number of messages transmitted by the reader using customized coding. We further explore the optimal parameter settings to maximize the performance of our proposed CR-MTI. Extensive simulation results show that our proposed CR-MTI outperforms prior art in terms of time efficiency, total executive time and communication complexity.

While the celebrated graph neural networks (GNNs) yield effective representations for individual nodes of a graph, there has been relatively less success in extending to the task of graph similarity learning. Recent work on graph similarity learning has considered either global-level graph-graph interactions or low-level node-node interactions, however, ignoring the rich cross-level interactions (e.g., between each node of one graph and the other whole graph). In this article, we propose a multilevel graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects in an end-to-end fashion. In particular, the proposed MGMN consists of a node-graph matching network (NGMN) for effectively learning cross-level interactions between each node of one graph and the other whole graph, and a siamese GNN to learn global-level interactions between two input graphs. Furthermore, to compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks with different sizes in order to evaluate the effectiveness and robustness of our models. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks. Compared with previous work, multilevel graph matching network (MGMN) also exhibits stronger robustness as the sizes of the two input graphs increase.

How to obtain the information from massive tags is a key focus of RFID applications. The occurrence of collisions leads to problems such as reduced identification efficiency in RFID networks. To tackle such challenges, most tag collision arbitration protocols focus on scheduling tag identification with collision avoidance. However, how to effectively identify tags in collisions to improve identification efficiency has not been well explored. In this paper, we propose a group query allocation method to divide the string space into mutually disjoint subsets which contains several strings. Each string can be viewed as a full ID or partial ID of a tag. When multiple string from a subset are sent simultaneously, the reader can identify all of them in a time slot. Based on the group query allocation method, a segment detection based characteristic group query tree (SD-CGQT) protocol is presented for fast tag identification by significantly reducing the collision slots and transmitted bits. Numerous experimental results verify the superiority of the proposed SD-CGQT, compared to prior arts in system efficiency, total identification time, communication complexity and energy consumption.

Encryption technology has been widely used in today’s network communications. The early classification of encrypted flows is of great value to the control, allocation and management of resources in TCP/IP networks. In this paper, we propose TaTic, an early classification method for encrypted traffic, which aims to reduce the time spent observing the encrypted flows to be classified, and at the same time ensure the flow classification accuracy. TaTic is based on our key observation that the majority of encrypted flows can be classified accurately using only the first few packets, and we call such flows “easy flows”, whereas the rest of encrypted flows requires more packets for fine-grained analysis to achieve accurate traffic classification, and we call such flows “hard flows”. Given an encrypted flow, in the first phase, we use only the first few packets to quickly determine whether it is an easy flow or a hard flow; if it is an easy flow, we directly classify it in this phase; otherwise, we use more packets to perform traffic classification in the second phase. Therefore, we can greatly reduce the time spent in observing the flows without sacrificing the classification accuracy. Our experimental results show that TaTic can greatly reduce the unnecessary time spent in observing the flow to be classified, and at the same time ensure high classification accuracy. We compare our experimental results of TaTic with four existing methods. TaTic is superior to the existing methods in terms of both classification accuracy and average waiting time.

Cloud service providers conservatively provision excessive resources to ensure service level objectives (SLOs) are met. They often set lower CPU utilization targets to ensure service quality is not degraded, even when the workload varies significantly. Not only does this potentially waste resources, but it can also consume excessive power in large-scale cloud deployments. This paper aims to minimize resource costs while ensuring SLO requirements are met in a dynamically varying, large-scale production microservice environment. We propose DeepScaling, which introduces three innovative components to adaptively refine the target CPU utilization to a level that is maintained at a stable value to meet SLO constraints while using minimum resources. First, DeepScaling forecasts the workload for each service using a Spatio-temporal Graph Neural Network. Second, DeepScaling estimates the CPU utilization by mapping the workload intensity to an estimated CPU utilization with a Deep Neural Network, while taking into account multiple factors in the cloud environment (e.g., periodic tasks and traffic). Third, DeepScaling generates an autoscaling policy for each service based on an improved Deep Q Network (DQN). The adaptive autoscaling policy updates the target CPU utilization to be a maximum, stable value, while ensuring SLOs is not violated. We compare DeepScaling with state-of-the-art autoscaling approaches in the large-scale production cloud environment of the Ant Group. It shows that DeepScaling outperforms other approaches both in terms of maintaining stable service performance, and saving resources, by a significant margin. The deployment of DeepScaling in Ant Group's real production environment with 135 microservices saves the provisioning of over 30,000 CPU cores per day, on average.

Multivariate time-series forecasting is a critical task for many applications, and graph time-series network is widely studied due to its capability to capture the spatial-temporal correlation simultaneously. However, most existing works focus more on learning with the explicit prior graph structure, while ignoring potential information from the implicit graph structure, yielding incomplete structure modeling. Some recent works attempts to learn the intrinsic or implicit graph structure directly, while lacking a way to combine explicit prior structure with implicit structure together. In this paper, we propose Regularized Graph Structure Learning (RGSL) model to incorporate both explicit prior structure and implicit structure together, and learn the forecasting deep networks along with the graph structure. RGSL consists of two innovative modules. First, we derive an implicit dense similarity matrix through node embedding, and learn the sparse graph structure using the Regularized Graph Generation (RGG) based on the Gumbel Softmax trick. Second, we propose a Laplacian Matrix Mixed-up Module (LM3) to fuse the explicit graph and implicit graph together. We conduct experiments on three real-word datasets. Results show that the proposed RGSL model outperforms existing graph forecasting algorithms with a notable margin, while learning meaningful graph structure simultaneously. Our code and models are made publicly available at https://github.com/alipay/RGSL.git.

One intriguing property of adversarial attacks is their “transferability” – an adversarial example crafted with respect to one deep neural network (DNN) model is often found effective against other DNNs as well. Intensive research has been conducted on this phenomenon under simplistic controlled conditions. Yet, thus far there is still a lack of comprehensive understanding about transferability-based attacks (“transfer attacks”) in real-world environments.To bridge this critical gap, we conduct the first large-scale systematic empirical study of transfer attacks against major cloud-based MLaaS platforms, taking the components of a real transfer attack into account. The study leads to a number of interesting findings which are inconsistent to the existing ones, including: (i) Simple surrogates do not necessarily improve real transfer attacks. (ii) No dominant surrogate architecture is found in real transfer attacks. (iii) It is the gap between posterior (output of the softmax layer) rather than the gap between logit (so-called κ value) that increases transferability. Moreover, by comparing with prior works, we demonstrate that transfer attacks possess many previously unknown properties in real-world environments, such as (i) Model similarity is not a well-defined concept. (ii) L2norm of perturbation can generate high transferability without usage of gradient and is a more powerful source than L∞norm. We believe this work sheds light on the vulnerabilities of popular MLaaS platforms and points to a few promising research directions.1

Nearest neighbor query processing is a fundamental problem that arises in many fields such as spatial databases and machine learning. This article aims to address the Secure Nearest Neighbor (SNN) problem in cloud computing. Prior SNN schemes are both insecure and inefficient. In this article, we formally prove and experimentally demonstrate that the SNN scheme ASPE is actually insecure against even ciphertext only attacks. Although prior work proved that it is impossible to construct an SNN scheme even in much relaxed standard security models, we point out the flaws of the hardness proof. We propose an SNN scheme and prove that it is secure against adaptive chosen keyword attacks. Our scheme is efficient as its query processing complexity is logarithmic. To evaluate the efficiency of our SNN scheme, we implemented our scheme in C++ and compared its performance with a plain text scheme, binary scheme, and a PIR scheme on a large set of over 10 million real-world data points. Experimental results show that our scheme is fast (0.124 millisecond per query when data set size is 10 million) and scalable in terms of the number of data points.

This article concerns the problem of detecting the use of information hiding at the physical layer in wireless communications because they are harder to be detected than other layer-based information hiding schemes. Prior schemes for detecting physical layer based information hiding are either heuristic based or machine learning based. The key limitation of prior heuristics based information hiding detection schemes is that they do not answer the fundamental question of why the information hidden at the physical layer can be detected. The key limitation of prior machine learning based information hiding detection schemes is that they lack robustness because wireless signals at the physical layer are very much environmental dependent, and thus an information hiding detection scheme trained in one environment often does not work well in another environment. Our insight is that embedding information on wireless signals at the physical layer will inevitably have a negative impact on the decodability of the cover signals, such as the increase of the error probability at the receiver (as well as the monitor). Based on the above insight, in our approach, after the monitor demodulates and decodes the cover signals, it will re-encode and re-modulate the cover signals, and then compare the resulting recovered signals with the raw signals that it received from the sender. We further propose a new estimation scheme for calculating receiver noise variance and conducted theoretical analysis. Specifically, we propose two hidden information detection schemes, a noise grouped based detection scheme and a constellation distance based detection scheme, both taking estimation errors into consideration. In particular, our constellation distance based detection scheme is the first scheme that can pinpoint the exact location on the received signals that are embedded with hidden information. We implemented our schemes and conducted extensive performance comparison between our schemes and prior schemes. Our experimental results show that when the received SNR is more than 20 dB, our approach with the new estimation scheme has the probability of detection more than 0.95, and our constellation distance based detection scheme can correctly pinpoint all embedded locations.

This paper concerns the fundamental problem of processing conjunctive queries that contain both keyword and range conditions on public clouds in a privacy preserving manner. No prior Searchable Symmetric Encryption (SSE) based privacy preserving conjunctive query processing scheme satisfies the three requirements of adaptive security, efficient query processing, and scalable index size. In this paper, we propose the first privacy preserving conjunctive query processing scheme that satisfies all the above three requirements. To achieve adaptive security, we propose an Indistinguishable Bloom Filter (IBF) data structure for indexing. To achieve efficient query processing and structural indistinguishability, we propose a highly balanced binary tree data structure called Indistinguishable Binary Tree (IBtree). To achieve scalable and compact index size, we propose an IBtree space compression algorithm to remove redundant information in IBFs. To optimize search efficiency, we propose a traversal minimization algorithm. To make our scheme dynamic, we propose update algorithms. We prove that our scheme is adaptive secure under the IND-CKA secure model. The key contribution of this paper is on achieving conjunctive query processing with both strong privacy guarantee and practical efficiency in terms of both speed and space. We implemented our scheme in C++, evaluated and compared its performance with the prior KRB scheme for keyword queries and the prior PBtree scheme for range queries on two real-world data sets. Experimental results show that our scheme is both fast and scalable. For example, processing a query only takes a few milliseconds for millions of records.

Recognizing surfaces based on their vibration signatures is useful as it can enable tagging of different locations without requiring any additional hardware, such as near field communication (NFC) tags. However, previous vibration based surface recognition schemes either use custom hardware for creating and sensing vibration, which makes them difficult to adopt, or use intertial (IMU) sensors in commercial off-the-shelf (COTS) smartphones to sense movements produced due to vibrations, which makes them coarse-grained because of the low sampling rates of IMU sensors. The mainstream COTS smartphones based schemes are also susceptible to inherent hardware based irregularities in vibration mechanism of the smartphones. Moreover, the existing schemes that use microphones to sense vibration are prone to short-term and constant background noises (e.g., intermittent talking, exhaust fan, etc.) because microphones not only capture the sounds created by vibration but also other interfering sounds present in the environment. In this paper, we propose VibroTag, a robust and practical vibration based sensing scheme that works with smartphones with different hardware, can extract fine-grained vibration signatures of different surfaces, and is robust to environmental noise and hardware based irregularities. We implemented VibroTag on two different Android phones and evaluated in multiple different environments where we collected data from four individuals for 5 to 20 consecutive days. Our results show that VibroTag achieves an average accuracy of 86.55 percent while recognizing 24 different locations/surfaces, even when some of those surfaces were made of similar material. VibroTag’s accuracy is 37 percent higher than the average accuracy of 49.25 percent achieved by one of the state-of-the-art IMUs based schemes, which we implemented for comparison with VibroTag.

In this paper, we propose to use commercial off-the-shelf (COTS)monostaticRFID devices (i.e. which use a single antenna at a time for both transmitting and receiving RFID signals to and from the tags) to monitor browsing activity of customers in front of display items in places such as retail stores. To this end, we proposeTagSee, a multi-person imaging system based on monostatic RFID imaging. TagSee is based on the insight that when customers are browsing the items on a shelf, they stand between the tags deployed along the boundaries of the shelf and the reader, which changes the multi-paths that the RFID signals travel along, and both the RSS and phase values of the RFID signals that the reader receives change. Based on these variations observed by the reader, TagSee constructs a coarse grained image of the customers. Afterwards, TagSee identifies the items that are being browsed by the customers by analyzing the constructed images. The key novelty of this paper is on achieving browsing behavior monitoring of multiple customers in front of display items by constructing coarse grained images via robust, analytical model-driven deep learning based, RFID imaging. To achieve this, we first mathematically formulate the problem of imaging humans using monostatic RFID devices and derive an approximate analytical imaging model that correlates the variations caused by human obstructions in the RFID signals. Based on this model, we then develop a deep learning framework to robustly image customers with high accuracy. We implement TagSee scheme using a Impinj Speedway R420 reader and SMARTRAC DogBone RFID tags. TagSee can achieve a TPR of more than${\sim }90\%$and a FPR of less than${\sim }10\%$in multi-person scenarios using training data from just 3-4 users.

In mobile edge computing, popular mobile applications, such as augmented reality, usually offload their tasks to resource-rich edge servers. The user experience can be considerably affected when many mobile users compete for the limited communication and computation resources. The key technical challenge in task offloading is to guarantee the Quality of Service (QoS) for such applications. Existing work on task offloading focus on deterministic QoS (delay) guarantee, which means that tasks have to complete before the given deadline with 100 percent. However, it is impractical to impose a deterministic QoS guarantee for tasks due to the high dynamics of the wireless environment when offloading to edge servers. In this paper, we focus on task offloading with statistical QoS guarantee (tasks are allowed to complete before a given deadline with a probability above the given threshold), which can further save more energy by loosing the QoS requirement. Specially, we first propose a statistical computation model and a statistical transmission model to quantify the correlation between the statistical QoS guarantee and task offloading strategy. Then, we formulate the task offloading problem as a mixed integer non-Linear programming problem with the statistical delay constraint. We transform the statistical delay constraint into the constraints on CPU cycle numbers and the delay exponent respectively. We propose an algorithm to provide the statistical QoS guarantee for tasks using convex optimization theory and Gibbs sampling method. Experiment results show that the proposed algorithm outperforms the three baselines.

With the rising of AR/VR technology and miniaturization of mobile devices, gesture recognition is becoming increasingly popular in the research area of human-computer interaction. Some pioneer ultrasound-based gesture recognition systems have been proposed. However, they mostly rely on low-resolution Doppler Effect, with the focus on whole hand motion and fail to deal with minor finger motions. This paper is to present UltraGesture, an ultrasonic finger motion perception and recognition system based on Channel Impulse Response (CIR). CIR measurements can provide with 7 mm resolution, which is sufficient for minor finger motion recognition. UltraGesture encapsulates CIR measurements into image, and builds a Convolutional Neural Network model to classify these images into different categories corresponding to distinct gestures. Furthermore, we use a sliding-window based method to improve accuracy and reduce response latency. UltraGesture can run on the already existed commercial speakers and microphones on most mobile devices without any hardware modification. Our results demonstrate that UltraGesture can achieve an average accuracy ofgreater than 99 percent for 12 gestures including finger click and rotation.

Radio frequency identification (RFID) has been widely applied in large-scale applications such as logistics, merchandise and transportation. However, it is still a technical challenge to effectively estimate the number of tags in complex mobile environments. Most of existing tag identification protocols assume that readers and tags remain stationary throughout the whole identification process and ideal channel assumptions are typically considered between them. Hence, conventional algorithms may fail in mobile scenarios with unreliable channels. In this paper, we propose a novel RFID anti-collision algorithm for tag identification considering path loss. Based on a probabilistic identification model, we derive the collision, empty and success probabilities in a mobile RFID environment, which will be used to define the cardinality estimation method and the optimal frame length. Both simulation and experimental results of the proposed solution show noticeable performance improvement over the commercial solutions.

Logistic Regression (LR) is the most widely used machine learning model in industry for its efficiency, robustness, and interpretability. Due to the problem of data isolation and the requirement of high model performance, many applications in industry call for building a secure and efficient LR model for multiple parties. Most existing work uses either Homomorphic Encryption (HE) or Secret Sharing (SS) to build secure LR. HE based methods can deal with high-dimensional sparse features, but they incur potential security risks. SS based methods have provable security, but they have efficiency issue under high-dimensional sparse features. In this paper, we first present CAESAR, which combines HE and SS to build secure large-scale sparse logistic regression model and achieves both efficiency and security. We then present the distributed implementation of CAESAR for scalability requirement. We have deployed CAESAR in a risk control task and conducted comprehensive experiments. Our experimental results show that CAESAR improves the state-of-the-art model by around 130 times.

Summary Crowdsourcing is emerging as a powerful paradigm that utilizes the distributed devices to sense, collect, and upload data to satisfy the requirements of the users. Currently, with the popularity of edge computing, edge device users can act as recruiters or participants to publish or perform crowdsourcing tasks and share feedback. However, due to the individual selfishness, it is still a challenge to maximize the social welfare distribution of all the participants and the recruiters for the crowdsourcing market. In view of this challenge, an incentive mechanism for the crowdsourcing market with social welfare maximization in the cloud‐edge computing is designed in this paper. Technically, a double action model under the cloud‐edge computing framework is proposed first, which aims to maximize the social welfare maximization and meanwhile meet the demands of incentive compatibility, individual rationality, market clearing, and budget constraint. Secondly, a corresponding incentive mechanism is designed based on the double auction model to achieve the market fairness. Experimental evaluation and comparison analysis are conducted to validate the efficiency and effectiveness of the mechanism.

Cloud providers have started to deploy various FPGA accelerators in their datacenters because the performance of many applications can be significantly improved by implementing their core routines in FPGAs. In conventional datacenters with FPGA accelerated servers, if a tenant wants to use FPGA accelerators, it requests for a VM instance residing in a server equipped with an FPGA accelerator. This paradigm to integrate FPGA into Cloud leads to poor resource sharing of the precious FPGA resources. In this paper, we propose FPGAPooling, an FPAG-enabled Cloud system where all FPGA accelerators are managed as a single resource pool and shared among all VMs. For a VM, instead of requesting the Cloud to run the VM on an FPGA accelerated server, at run time, when a VM needs to use FPGA acceleration, it requests an FPGA accelerator from the pool. After the VM finishes using the FPGA accelerator, it releases the FPGA accelerator back to the pool. We design a centralized scheduler to handle acceleration requests from VMs and assign each request to an idle FPGA accelerator at run time; We implemented a system prototype on IBM's OpenPower Cloud system. The key challenging of FPGAPooling is scheduling. We designed and implemented a group of scheduling algorithms for the FPGAPooling system. With extensive evaluations on both a small testbed and a large-scale simulation, we found that our algorithms can improve the average and tail job completion time by up to 7 and 4 times, respectively.

Assessing trust in online social networks (OSNs) is critical for many applications such as online marketing and network security. It is a challenging problem, however, due to the difficulties of handling complex social network topologies and conducting accurate assessment in these topologies. To address these challenges, we model trust by proposing the three-valued subjective logic (3VSL) model. 3VSL properly models the uncertainties that exist in trust, thus is able to compute trust in arbitrary graphs. We theoretically prove the capability of 3VSL based on the Dirichlet-Categorical (DC) distribution and its correctness in arbitrary OSN topologies. Based on the 3VSL model, we further design the AssessTrust (AT) algorithm to accurately compute the trust between any two users connected in an OSN. We validate 3VSL against two real-world OSN datasets: Advogato and Pretty Good Privacy (PGP). Experimental results indicate that 3VSL can accurately model the trust between any pair of indirectly connected users in the Advogato and PGP.

Code retrieval is to find the code snippet from a large corpus of source code repositories that highly matches the query of natural language description. Recent work mainly uses natural language processing techniques to process both query texts (i.e., human natural language) and code snippets (i.e., machine programming language), however, neglecting the deep structured features of query texts and source codes, both of which contain rich semantic information. In this article, we propose an end-to-end deep graph matching and searching (DGMS) model based on graph neural networks for the task of semantic code retrieval. To this end, we first represent both natural language query texts and programming language code snippets with the unified graph-structured data, and then use the proposed graph matching and searching model to retrieve the best matching code snippet. In particular, DGMS not only captures more structural information for individual query texts or code snippets, but also learns the fine-grained similarity between them by cross-attention based semantic matching operations. We evaluate the proposed DGMS model on two public code retrieval datasets with two representative programming languages (i.e., Java and Python). Experiment results demonstrate that DGMS significantly outperforms state-of-the-art baseline models by a large margin on both datasets. Moreover, our extensive ablation studies systematically investigate and illustrate the impact of each part of DGMS.

This paper studies the problem of cHarging tAskScheduling for direcTional wireless chargEr networks (HASTE), i.e., given a set of rotatable directional wireless chargers on a 2D area and a series of offline (online) charging tasks, scheduling the orientations of all the chargers with time in a centralized offline (distributed online) fashion to maximize the overall charging utility for all the tasks. We prove that HASTE is NP-hard. Then, we prove that a relaxed version of HASTE falls within the realm of maximizing a submodular function subject to a partition matroid constraint, and propose a centralized offline algorithm that achieves$(1-\rho)(1-\frac{1}{e})$approximation ratio to address HASTE where$\rho$is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves$\frac{1}{2}(1-\rho)(1-\frac{1}{e})$competitive ratio. We conduct simulations and field experiments on a testbed consisting of eight off-the-shelf power transmitters and 8 rechargeable sensor nodes. The results show that our distributed online algorithm achieves 92.97 percent of the optimal charging utility, and outperforms the comparison algorithms by up to 15.28 percent in terms of charging utility.

Gesture tracking is a basic Human-Computer Interaction mechanism to control devices, such as IoT and VR/AR devices. However, prior OFDM signal based systems focus on gesture recognition and provide results with insufficient accuracy, and thus, cannot be applied for high-precision gesture tracking. In this paper, we propose a CSI based device-free gesture tracking system, called WiTrace, which leverages the CSI values extracted from OFDM signals to enable accurate gesture tracking. For 1D tracking, WiTrace derives the phase of the signals reflected by the hand from the composite signals, and measures the phase changes to obtain the movement distance. For 2D tracking, WiTrace proposes the first CSI based scheme to accurately estimate the initial position, and adopts the Kalman Filter based on continuous Wiener process acceleration model to further filter out tracking noise. Our results show that WiTrace achieves an average accuracy of 6.23 cm for initial position estimation and achieves cm-level accuracy with average tracking errors of 1.46 cm and 2.09 cm for 1D tracking and 2D tracking, respectively.

In this article, we first study the problem of Connected wIReless Charger pLacEment (CIRCLE). That is, given a fixed number of directional wireless chargers and candidate positions, determining the placement position and orientation angle for each charger under connectivity constraint for wireless chargers such that the overall charging utility is maximized. To address CIRCLE problem, we first consider a relaxed version of CIRCLE (CIRCLE-R for short). We prove that CIRCLE-R falls into the realm of maximizing a submodular set function subject to a connectivity constraint, and propose an algorithm whose approximation ratio is at least 1.5 times better than that of the state-of-the-art algorithm. Next, we reduce the solution space for CIRCLE from infinite to finite, and propose an algorithm with a constant approximation ratio to address CIRCLE. Besides, we consider a variant of CIRCLE, CIRCLE-NB, and propose an approximation algorithm to address it. We conduct both simulation experiments and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35 percent.

With the incremental deployment of software defined networking, the routing algorithms have gained more power on observability and controllability. Deep reinforcement learning, as an experience-driven approach, shows considerable potential in routing problem with the help of the centralized controller. It is an adaptive, lightweight, and model-free approach to coping with dynamic runtime status, large-scale traffic, and heterogeneous objective of SDN routing. However, it is still not suitable for the variable and complex emerging networks, because the huge training cost prevents fast convergence in a varying or discrepant environment. In this paper, we propose a transfer reinforcement learning algorithm to improve the training efficiency, and handle the variation in network status and topology. Specifically, we leverage the generative adversarial network to learn domain-invariant features that is suitable for deep reinforcement learning-based routing in different network environments. This mechanism utilizes the previous model and accelerates the training process. We implement our routing algorithm in the production level software switches and controller, while evaluating it comprehensively with many topologies and network status distributions. The experimental results show that our work not only outperforms the state-of-the-art deep reinforcement learning-based routing frameworks, but also has more training efficiency than the naive transfer learning algorithm both on different topologies and network status distributions.

With the development of the Internet of Things (IoT) and 5G, there are ubiquitous smart devices and network functions providing emerging network services efficiently and optimally through building many network connections based on WiFi, LTE/5G, Ethernet, and etc. The Multipath TCP (MPTCP) protocol that enables these devices to establish multiple paths for simultaneous data transmission, has been a widely used extension of standard TCP in smart devices and network functions. On the other hand, more heavy and time-varying traffic loads are generated in an MPTCP network, so that an efficient congestion control mechanism that schedules the traffic between multiple subflows and avoids congestion is highly required. In this paper, we propose a decentralized learning approach, DeepCC, to adapt to the volatile environments and realize the efficient congestion control. The Multi-Agent Deep Reinforcement Learning (MADRL) is used to learn a policy of congestion control for each subflow according to the real-time network states. To deal with the problem of the fixed state space and slow convergence, we adopt two self-attention mechanisms to receive the states and train the policy, respectively. Due to the asynchronous design of DeepCC, the learning process will not introduce extra delay and overhead on the decision-making process. Experiment results show that DeepCC consistently outperforms the well-known heuristic method and DRL-based MPTCP congestion control method in terms of goodput and jitter. Besides, DeepCC with the attention mechanism reduces convergence time by about 50% and increase goodput by about 80% compared with the commonly used structures of neural networks.

As powerline communication (PLC) technology does not require dedicated cabling and network setup, it can be used to easily connect multitude of IoT devices deployed in enterprise environments for sensing and control related applications. IEEE has standardized the PLC protocol in IEEE 1901, also known as HomePlug AV (HPAV) which has been widely adopted in mainstream PLC devices. A key weakness of HPAV protocol is that it does not support spectrum sharing. Currently, each link in an HPAV PLC network operates over the whole available spectrum, and only one link can operate at any time within a single collision domain. In this work, through an extensive measurement study of HPAV PLCs in a real enterprise environment using commodity off-the-shelf (COTS) HPAV PLC devices, we discover that spectrum sharing can significantly benefit enterprise level PLC networks. To this end, we propose a distributed spectrum sharing technique for enterprise HPAV PLC networks, and show that fine-grained distributed spectrum sharing on top of current HPAV MAC protocols can significantly boost the aggregated and per-link throughput, by allowing multiple PLC links to communicate concurrently, while requiring only a few modifications to the existing HPAV devices and protocols.

Wireless Power Transfer has become a commercially viable technology to charge devices because of the convenience of no power wiring and the reliability of continuous power supply. This paper concerns the fundamental issue of wireless charger placement with electromagnetic radiation (EMR) safety. Although there are a few wireless charging schemes consider EMR safety, none of them addresses the charger placement issue. In this paper, we propose PESA, a wireless charger Placement scheme that guarantees EMR SAfety for every location on the plane. First, we discretize the whole charging area and formulate the problem into the Multidimensional 0/1 Knapsack (MDK) problem. Second, we propose a fast approximation algorithm to the MDK problem. Third, we propose a near optimal scheme to improve speed by double partitioning the area. We prove that the output of our algorithm is better than $(1-\epsilon)$ of the optimal solution to PESA with a smaller EMR threshold $(1-\epsilon /2)R_{t}$ and a larger EMR coverage radius $(1+\epsilon /2)D$ . We conducted both simulations and field experiments to evaluate the performance of our scheme. Our experimental results show that in terms of charging utility, our algorithm outperforms the comparison algorithms.

In wireless network applications, such as routing decision, network selection, etc., the Multi-Attribute Decision Making (MADM) is widely used. The MADM approach can address the multi-objective decision making issues effectively. However, when the parameters vary greatly, the traditional MADM algorithm is not effective anymore. To solve this problem, in this paper, we propose the pairwise-based MADM algorithm. In the PMADM, only two nodes' utilities are calculated and compared at each time. The PMADM algorithm is much more accurate than the traditional MADM algorithm. Moreover, we also prove that the PMADM algorithm is sensitive to the parameters which vary seriously and insensitive to the parameters which change slightly. This property is better than that of the traditional MADM algorithm. Additionally, the PMADM algorithm is more stable than traditional MADM algorithm. For reducing the computational complexity of the PMADM algorithm, we propose the low-complexity PMADM algorithm. For analyzing the computational complexity of the l PMADM algorithm, we propose the tree-based decomposing algorithm in this paper. The l PMADM algorithm has the same properties and performances as that of the PMADM algorithm; however, it is simpler than the PMADM algorithm. The simulation results show that the PMADM and l PMADM algorithms are much more effective than the traditional MADM algorithm.

This paper addresses the problem of authenticating the transmitter device in wirelessly powered communications networks (WPCNs). We proposed a physical-layer authentication scheme for a WPCN. In comparison with upper-layer authentication schemes, the proposed scheme has low complexity, low power consumption, low overhead, and high security. For comprehensively analyzing the performance of the proposed scheme by considering the requirements of transmission delay, security, and reliability together, we put forward an analytical framework by considering the probabilities of transmission, security outage, connection outage, and joint security-connection outage. Based on the proposed analytical framework, we further introduced a new systematic metric by calculating the achievable throughput of all users with considering the performance of transmission-delay, security, and reliability together. We defined this new systematic metric as the overall transmission efficiency (OTE) of a WPCN, which can effectively quantize the average efficiency of message transmission in the WPCN with physical layer authentication. We analyzed the events represented by these probability factors over random fading channels and explicitly derive their closed-form expressions. For defending against jamming attacks, we further proposed another metric to estimate which user has the high probability of suffering from jamming attacks. The new metric represents that the adversary has the largest attacking gain with the minimum cost. We implemented our scheme and conducted extensive performance comparisons through simulations. Our experimental results show that the proposed scheme accurately detects an impersonating attack and drops its contribution to the sum of long-term throughput.

Despite their tremendous success in a range of domains, deep learning systems are inherently susceptible to two types of manipulations: adversarial inputs -- maliciously crafted samples that deceive target deep neural network (DNN) models, and poisoned models -- adversely forged DNNs that misbehave on pre-defined inputs. While prior work has intensively studied the two attack vectors in parallel, there is still a lack of understanding about their fundamental connections: what are the dynamic interactions between the two attack vectors? what are the implications of such interactions for optimizing existing attacks? what are the potential countermeasures against the enhanced attacks? Answering these key questions is crucial for assessing and mitigating the holistic vulnerabilities of DNNs deployed in realistic settings.

In recent years, the Bitcoin (BTC) payment is increasingly popular in retailers and service providers. A BTC transaction (tx) needs six confirmations (one hour) to be validated, making it not suitable for fast-pay scenarios. Theoretically, a shorter waiting time period increases the success possibility of a double-spending attack. To address this problem, we propose BTCFast scheme to support fast BTC tx. BTCFast is a novel, decentralized, escrow-based scheme on top of the programmable smart contract (PSC)-enabled blockchains (e.g. Ethereum, EOS). We develop a smart contract (PayJudger) to work as a trusted payment judger, which guarantees the tx fairness. In addition, we devise a proof-of-work (PoW)-based payment judgment mechanism for PayJudger to resolve a BTC payment dispute. Our theoretical and experimental results show that BTCFast can reduce the waiting time to be less than 1 second with comparable security as the current approach (i.e., waiting for six confirmations) with no extra operation fee.

With the advent of the era of big data, deep learning has become a prevalent building block in a variety of machine learning or data mining tasks, such as signal processing, network modeling and traffic analysis, to name a few. The massive user data crowdsourced plays a crucial role in the success of deep learning models. However, it has been shown that user data may be inferred from trained neural models and thereby exposed to potential adversaries, which raises information security and privacy concerns. To address this issue, recent studies leverage the technique of differential privacy to design private-preserving deep learning algorithms. Albeit successful at privacy protection, differential privacy degrades the performance of neural models. In this paper, we develop ADADP, an adaptive and fast convergent learning algorithm with a provable privacy guarantee. ADADP significantly reduces the privacy cost by improving the convergence speed with an adaptive learning rate and mitigates the negative effect of differential privacy upon the model accuracy by introducing adaptive noise. The performance of ADADP is evaluated on real-world datasets. Experiment results show that it outperforms state-of-the-art differentially private approaches in terms of both privacy cost and model accuracy.

This paper studies the problem of robust frequent items mining in data streams that generalizes the traditional frequent items mining by considering the noise of datasets. That is, different items may correspond to the same entity because of noise; examples include different images of the same object and fluctuated data in the same setting measured by sensors. Our objective is to identify those items that correspond to the same entity and have an aggregated frequency exceeding a given threshold, which named as robust frequent items. To the best of our knowledge, there is no existing works on mining robust frequent items in a data stream. In this paper, we first propose a scheme by applying sampling and spatial partition to address the problem in low dimensional spaces. Furthermore, we extend the above algorithmic framework to high dimensional spaces by incorporating the locality sensitive hashing scheme to deal with the approximate nearest neighbor problem. We conduct evaluations using synthetic datasets and compare our scheme with two prior adapted schemes. Our results demonstrate that the efficiency of our algorithms outperforms the adaptive Space Saving by 14.8% and 9.8% in terms of precision and recall, respectively.

We propose the first budget-limited multi-armed bandit (BMAB) algorithm subject to a union of matroid constraints in arm pulling, while at the same time achieving differential privacy. Our model generalizes the arm-pulling models studied in prior BMAB schemes, and it can be used to address many practical problems such as network backbone construction and dynamic pricing in crowdsourcing. We handle the exploitation versus exploration tradeoff in our BMAB problem by exploiting the combinatorial structures of matroids, and reduce the searching complexity of arm selection based on a divide-and-conquer approach. Our algorithm achieves a uniform logarithmic regret bound with respect to B and ɛ-differential privacy, where B is the budget for pulling the arms with random costs. Without differential privacy, our algorithm achieves a uniform logarithmic regret bound with respect to B, which advances the asymptotic regret bounds achieved by prior BMAB algorithms. We performed side-by-side comparisons with prior schemes in our experiments. Experimental results show that our purely-combinatorial algorithm not only achieves significantly better regret performance, but also is more than 20 times faster than prior BMAB schemes, which use time-consuming LP-solving techniques.

Taxi services play an important role in the public transportation system of large cities. Improving taxi business efficiency is an important societal problem. Most of the recent analytical approaches on this topic only considered how to maximize the pickup chance, energy efficiency, or profit for the immediate next trip when recommending seeking routes, therefore may not be optimal for the overall profit over an extended period of time due to ignoring the destination choice of potential passengers. To tackle this issue, we propose a novel Spatial Network-based Markov Decision Process (SN-MDP) with a rolling horizon configuration to recommend better driving directions. Given a set of historical taxi records and the current status (e.g., road segment and time) of a vacant taxi, we find the best move for this taxi to maximize the profit in the near future. We propose statistical models to estimate the necessary time-variant parameters of SN-MDP from data to avoid competition between drivers. In addition, we take into account fuel cost to assess profit, rather than only income. A case study and several experimental evaluations on a real taxi dataset from a major city in China show that our proposed approach improves the profit efficiency by up to 13.7 percent and outperforms baseline methods in all the time slots.

The tag collision avoidance has been viewed as one of the most important research problems in RFID communications and bit tracking technology has been widely embedded in query tree (QT) based algorithms to tackle such challenge. Existing solutions show further opportunity to greatly improve the reading performance because collision queries and empty queries are not fully explored. In this paper, a bit query (BQ) strategy based M-ary query tree protocol (BQMT) is presented, which can not only eliminate idle queries but also separate collided tags into many small subsets and make full use of the collided bits. To further optimize the reading performance, a modified dual prefixes matching (MDPM) mechanism is presented to allow multiple tags to respond in the same slot and thus significantly reduce the number of queries. Theoretical analysis and simulations are supplemented to validate the effectiveness of the proposed BQMT and MDPM, which outperform the existing QT-based algorithms. Also, the BQMT and MDPM can be combined to BQ-MDPM to improve the reading performance in system efficiency, total identification time, communication complexity and average energy cost.

Identification efficiency is a key performance metrics to evaluate the ultra high frequency (UHF) based radio frequency identification (RFID) systems. In order to solve the tag collision problem and improve the identification rate in large scale networks, we propose a collision arbitration strategy termed as group-based binary splitting algorithm (GBSA), which is an integration of an efficient tag cardinality estimation method, an optimal grouping strategy and a modified binary splitting. In GBSA, tags are properly divided into multiple subsets according to the tag cardinality estimation and the optimal grouping strategy. In case that multiple tags fall into a same time slot and form a subset, the modified binary splitting strategy will be applied while the rest tags are waiting in the queue and will be identified in the following slots. To evaluate its performance, we first derive the closed-form expression of system throughput for GBSA. Through the theoretical analysis, the optimal grouping factor is further determined. Extensive simulation results supplemented by prototyping tests indicate that the system throughput of our proposed algorithm can reach as much as 0.4835, outperforming the existing anti-collision algorithms for UHF RFID systems.

This paper concerns the problem of phase reference estimation with noise, introduced by the imperfect phase-locked loop (PLL) circuit, or the imperfect channel estimation, or both. Prior solutions for suppressing phase noise focus on improving the accuracy of phase reference estimation. The accuracy of phase reference estimation is not high enough due to the following two limitations. First, since the PLL circuit works in radio-frequency (RF), a PLL circuit with high accuracy leads to high cost and high complexity, which makes the deployment difficult. Second, as data rates increase and wireless channels become more complex, the receiver is more difficult to obtain an ideal channel estimation and the negative effect of phase noise becomes more apparent. In this paper, we propose a machine learning approach to mitigate the negative effect of phase noise by using clustering algorithms. The key intuition of our approach is that the clustering algorithm can adaptively trace the shifted constellation point due to the phase noise. Our approach is adaptive because it can adaptively find each received symbol belongs to its original constellation point if the phase noise is not too large, e.g., no larger than $0.25 \pi $ . While the shifted distance is not too large, we can map the received symbols into the correct constellation point to mitigate the negative effect of phase noise. Instead of directly using conventional clustering algorithms into the proposed machine learning approach, we propose a new weighted ensemble clustering algorithm to further improve the performance of our approach. In comparison with prior approaches based on RF circuits, our approach has comparable reception performance but with low complexity and low cost. Our experimental results show that, for a QPSK system, our approach improves the demodulation performance and the decoding performance about 10 dB, 8 dB under BCH codes, and 3 dB under Turbo codes, respectively. Even the demodulation performance of our approach without channel coding is better than the decoding performance of the system with channel coding about 5 dB under BCH codes.

Software systems inherently contain vulnerabilities that have been exploited in the past resulting in significant revenue losses. The study of various aspects related to vulnerabilities such as their severity, rates of disclosure, exploit and patch release, and existence of common vulnerabilities in different products can help in improving the development, deployment, and maintenance process of software systems. It can also help in designing future security policies and conducting audits of past incidents. Furthermore, such an analysis can help customers to assess the security risks associated with software products of different vendors. In this paper, we conduct an exploratory measurement study of a large software vulnerability data set containing 56077 vulnerabilities disclosed since 1988 till 2013. We investigate vulnerabilities along following eight dimensions: (1) phases in the life cycle of vulnerabilities, (2) evolution of vulnerabilities over the years, (3) functionality of vulnerabilities, (4) access requirement for exploitation of vulnerabilities, (5) risk level of vulnerabilities, (6) software vendors, (7) software products, and (8) existence of common vulnerabilities in multiple software products. Our exploratory analysis uncovers several statistically significant findings that have important implications for software development and deployment.

This paper concerns the problem of finding persistent items in distributed datasets, which has many applications such as port scanning and intrusion detection. To the best of our knowledge, there is no existing solution for finding persistent items in distributed datasets. In this paper, we propose DISPERSE, a probabilistic algorithm that can find persistent items in distributed datasets without collecting all the datasets. Our basic idea is that each monitor compresses each item ID in its dataset in a lossy fashion, sends the set of lossily compressed item IDs to the server, then the server recovers the IDs of the persistent items. We design the lossy compression so that given one lossily compressed item ID, the server cannot recover the item ID, but when the number of lossily compressed versions of the same item ID exceeds a threshold, which means that such items are persistent ones, the server can recover the item ID with a high probability. This threshold is exactly the threshold in the definition of persistent items. We implemented DISPERSE and evaluated its performance. In comparison with the straightforward solution, DISPERSE achieves a compression ratio of 26.5% with FNR=3.5% and FPR=0. In comparison with a developed Bloom filter based scheme and the adapted kBF and IBF schemes, our scheme can achieve 7.9, 5.7, and 6.6 times performance gains, respectively, in terms of compression ratio.

In this paper, we consider the problem of thresholded monitoring in distributed data streams, that is, given multiple distributed data streams observed by multiple monitors during a certain period, finding the items whose global frequencies over all data streams exceeding a given threshold. We first derive a lower bound of communication overhead for any deterministic algorithm for this problem. Then, we propose two different schemas, i.e., Low-threshold Cascaded Cuckoo Filter (L-CCF) for low-threshold monitoring and High-threshold Cascaded Cuckoo Filter (H-CCF) for high-threshold monitoring. L-CCF and H-CCF can identify items whose frequencies are more than the given threshold while a desired false negative rate (FNR) is achieved and communication overhead is optimized. The key idea is to compress the communication overhead caused by transferring the ID and frequency information at the same time. First, to reduce the communication overhead of transferring IDs, we propose to encode the IDs into separate tiny parts and store these tiny parts in L-CCF or H-CCF. Second, to reduce the communication overhead of transferring frequencies, we adopt a carry-in counter technique in L-CCF and multiple sampling technique in H-CCF. We evaluated L-CCF and H-CCF on two real-world traces and compared their performance with two prior adapted algorithms. Our experimental results show that on average, L-CCF and H-CCF achieve FNRs with 55% and 65% better than that of comparison algorithms while FPRs is maintained at the level of 2%.

Unknown RFID tags appear when tagged items are not scanned before being moved into a warehouse, which can even cause serious security issues. This paper studies the practically important problem of unknown tag detection. Existing solutions either require low-cost tags to perform complex operations or beget a long detection time. To this end, we propose the Collision-Seeking Detection (CSD) protocol, in which the server finds out a collision-seed to make massive known tags hash-collide in the last $N$ slots of a time frame with size $f$ . Thus, all the leading ${f-N}$ pre-empty slots become useful for detection of unknown tags. A challenging issue is that, computation cost for finding the collision-seed is very huge. Hence, we propose a supplementary protocol called Balanced Group Partition (BGP), which divides tag population into $n$ small groups. The group number $n$ is able to trade off between communication cost and computation cost. We also give theoretical analysis to investigate the parameters to ensure the required detection accuracy. The major advantages of our CSD+BGP are two-fold: (i) it only requires tags to perform lightweight operations, which are widely used in classical framed slotted Aloha algorithms. Thus, it is more suitable for low-cost tags; (ii) it is more time-efficient to detect the unknown tags. Simulation results reveal that CSD+BGP can ensure the required detection accuracy, meanwhile achieving $1.7\times $ speedup in the single-reader scenarios and $3.9\times $ speedup in the multi-reader scenarios than the state-of-the-art detection protocol.

To improve the performance of data-intensive applications, existing datacenter schedulers optimize either the placement of tasks or the scheduling of network flows. The task scheduler strives to place tasks close to their input data (i.e., maximize data locality) to minimize network traffic, while assuming fair sharing of the network. The network scheduler strives to finish flows as quickly as possible based on their sources and destinations determined by the task scheduler, while the scheduling is based on flow properties (e.g., size, deadline, and correlation) and not bound to fair sharing. Inconsistent assumptions of the two schedulers can compromise the overall application performance. In this paper, we propose NEAT+, a task scheduling framework that leverages information from the underlying network scheduler and available compute resources to make task placement decisions. The core of NEAT+ is a task completion time predictor that estimates the completion time of a task under given network condition and a given network scheduling policy. NEAT+ leverages the predicted task completion times to minimize the average completion time of active tasks. Evaluation using ns2 simulations and real-testbed shows that NEAT+ improves application performance by up to 3.7x for the suboptimal network scheduling policies and up to 33% for the optimal network scheduling policy.

Radio-frequency identification (RFID) is a major enabler of Internet of Things (IoT), and has been widely applied in tag-intensive environments. Tag collision arbitration is considered as a crucial issue of such RFID system. To enhance the reading performance of RFID, numerous anti-collision algorithms have been presented in previous literatures. However, most of them suffer from the slot efficiency bottleneck of 0.368. In this paper, we revisit the performance of tag identification in Aloha-based RFID anti-collision approaches from the perspective of time efficiency. Based on comprehensive reviews and analysis of the existing algorithms, a novel partitioning approach is proposed to maximize identification performance in framed slotted Aloha based UHF RFID systems. In the proposed approach, the tag set is divided into many groups which only contains a few tags, and then each group is identified in sequence. Benefiting from the optimal partition, the proposed algorithm can achieve a significant performance improvement. Simulation results supplemented by prototyping tests show that the proposed solution achieves an asymptotical slot efficiency up to 0.4348, outperforming the existing UHF RFID solutions.

This paper concerns the problem of spectrum sharing in mmWave cellular networks, where multiple network operators are granted access to the same spectrum resources. Prior spectrum sharing schemes for mmWave cellular networks have two limitations: high coordination overhead and high computational complexity. In this paper, we propose two spectrum sharing schemes for the mobile scenario and the stationary scenario, respectively. In the mobile scenario, we propose a Spectrum sharing scheme using Clustering Algorithms to find the Optimal Positions of Mobile BSes (SCA-OPM). In the stationary scenario, we propose a Spectrum sharing scheme using Clustering Algorithms to Select the most appropriate Subset from all BSes (SCA-SSB). Moreover, for each newly-arriving mobile terminal (MT), we propose two online spectrum sharing schemes based on our SCA-OPM scheme and SCA-SSB scheme, which effectively saves the overall overhead and complexity. Our experimental results show that the SCA-OPM scheme has the best performance, while the SCA-SSB scheme has the same performance as that of the prior scheme but with lower overhead and lower complexity. When the MT density is 200 MTs/km2, for the sum-rate with 10-2bits/s/Hz, the performance gap between the SCA-OPM scheme and the remaining schemes achieves about 19 dB. Moreover, our online schemes have the same performance as those of their counterpart schemes but with lower overhead and lower complexity for the scenario of a few newly-arriving MTs.

This paper concerns the problem of the multi-path classification in a multi-user multi-input multi-output (MIMO) system. We propose a machine learning approach to achieve a blind multi-path classification in the uplink (UL) scheme of a multi-user massive MIMO system. Note that the “blind” term in our approach represents the achievement of the multi-path classification without different pilot sequences on different users, without prior channel state information (CSI) at each user, and without any exploiting the special properties of the received signal. Specifically, our approach consists of two phases. In the first phase, multiple users transmit communication-requests to the base station (BS) for message transmission. The BS only estimates the scaled large-scale path loss of each user, which is determined by the distance between the transmitter and the receiver and is independent of the number of multi-path. Then, the BS compares the difference of the scaled large-scale path loss between any two users. If the difference is sufficiently large, the BS notifies all users to permit their simultaneous message transmissions. However, if the difference is small, the BS notifies each user to slightly adjust their transmission power and then permits their simultaneous message transmissions as well. In the second phase, all users simultaneously transmit their messages using the same radio resource. Then the BS selects one predetermined constellation point from the received pilot symbols as the input of clustering algorithms. According to the clustering results, the BS classifies each multi-path into a specific user. The key intuition of our approach is that the clustering algorithms can generate multiple cluster centroids and each cluster centroid represents the average reception power of each user. Moreover, we use a weighted ensemble clustering algorithm to further improve the performance of our approach. We implemented our approach and conducted extensive performance comparison. Our experimental results show that, when the received signal-to-noise ratio (SNR) is more than 13 dB, our approach with the weighted ensemble clustering algorithm can correctly classify all multi-path to the corresponding user and the output SNR can be improved by 3.2 dB, where we consider three users in an 8PSK system and each user possess 50 multi-path.

This paper concerns the problem of authenticating the transmitter device in non-orthogonal multiple access (NOMA) systems. This problem is important because of high vulnerabilities in wireless communications and an additional security vulnerability when some users collude with the adversary. In this paper, we consider two attacking scenarios. In the first scenario, there is no user that colludes with the adversary. In the second scenario, at least one user colludes with the adversary. In this paper, we propose an authentication approach in the down-link scheme of a NOMA system using physical-layer authentication mechanism because of its advantages: provide information theoretic security, reduce complexity, save power and allow us to construct a two-factor authentication system. Based on the aforementioned two attacking scenarios, we propose three physical-layer authentication schemes for a NOMA system: Physical-Layer Authentication with Shared Authentication Tag (PLA-SAT), Physical-Layer Authentication with Superimposed Independent authentication Tags (PLA-SIT), and Physical-Layer Authentication with TDM authentication tags (PLA-TDM). We analyze the theoretical performance of our schemes over fading channels and derive their closed-form expressions. Then, we optimize the parameters of our schemes to achieve both the reliability fairness and the authentication-accuracy fairness. We implemented our schemes and conducted extensive performance comparisons. Our experimental results show that for the first attacking scenario, the PLA-SAT scheme offers more than 97% authentication accuracy when the received SNR of the served user with poor channel condition is at least 10 dB. For the second attacking scenario, both the PLA-SIT scheme and the PLA-TDM scheme offer more than 97% authentication accuracy when the received SNR of the served user with poor channel condition is at least 12 dB.

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today's large-scale data analytics. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job's lifetime, which makes it difficult to assign valuable tasks to well-performing machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.

Recent trends show that cloud computing is growing to span more and more globally distributed datacenters. For geo-distributed datacenters, there is an increasingly need for scheduling algorithms to place tasks across datacenters, by jointly considering WAN traffic and computation. This scheduling must deal with situations such as wide-area distributed data, data sharing, WAN bandwidth costs and datacenter capacity limits, while also minimizing makespan. However, this scheduling problem is NP-hard. We propose a new resource allocation algorithm called HPS+, an extension to Hypergraph Partition-based Scheduling. HPS+ models the combined task-data dependencies and data-datacenter dependencies as an augmented hypergraph, and adopts an improved hypergraph partition technique to minimize WAN traffic. It further uses a coordination mechanism to allocate network resources closely following the guidelines of task requirements, for minimizing the makespan. Evaluation across the real China-Astronomy-Cloud model and Google datacenter model show that HPS+ saves the amount of data transfers by upto 53 percent and reduces the makespan by 39 percent compared to existing algorithms.

Radio frequency identification (RFID) is widely applied in massive items tagged domains. Existing medium access control (MAC) solutions primarily focus on improving slot efficiency or reducing the total number of slots. However, with pervasive applications of RFID, the time and energy consumption are increasingly important and should be considered in the new design. In this paper, we re-exam the problem of tag identification in UHF RFID system from the perspective of time and energy consumption. The presented work comprehensively reviews and analyzes the prior tag reading protocols. Based on prior art, we further discuss a novel design of tag reading algorithm to improve both time and energy efficiency of EPC C1 Gen2 UHF RFID standard. By exploring the effectiveness of embedding slot-by-slot mechanism in a sub-frame observation phase and combine the sub-frame and slot-by-slot observation in the proposed algorithm, which can achieve more fine-grained frame size adjustment with time and energy-efficiency. Moreover, the cardinality estimation function of the algorithm is implemented by the look-up tables, which allows dramatically reduction in computational complexity and energy consumption. Both simulation results and experiments show clear performance improvement over the commercial solutions.

Feature selection is an important research issue in classification. As an effective global optimization technique, Particle Swarm Optimization (PSO) algorithm has been widely employed to solve feature selection problems. Population initialization is an important stage in Evolutionary Computation (EC) techniques. Therefore, in EC research field, many works focus on population initialization and it has been verified that suitable population initialization methods can significantly improve the performance of EC techniques. The efficient of PSO significantly deteriorates when being used to solve the large-scale feature selection problems. At present, only a few works have been done to enhance the performance of PSO for feature selection problems through population initialization. Meanwhile, there are many excellent traditional filter feature selection methods. Their characteristic is quick in speed but low in effect. However, they can provide a lot of useful heuristic information. Therefore, this paper focuses on improving the performance of PSO for feature selection problems by designing filter-based population initialization methods. In the proposed method, the filters are firstly used to evaluate features. Based on the obtained heuristic information, the initialization method combining the mixed initialization and the threshold selection is designed. The experiments are carried out on several datasets and the proposed initialization method is compared to some related initialization methods. Besides, the K-Nearest Neighbour (KNN) and other compatible fitness learners are used for performance assessment for feature selection. The results show that the proposed method using KNN classifier is promising to improve the performance of PSO for feature selection problems.

In this paper, we consider the problem of thresholded monitoring in distributed data streams, that is, given multiple distributed data streams observed by multiple monitors during a certain period, finding the items whose global frequencies overall data streams exceeding a given threshold. We first derive a lower bound of communication overhead for any deterministic algorithm for this problem. Then, we propose two different schemas, i.e., Low-threshold Cascaded Cuckoo Filter (L-CCF) for low-threshold monitoring and High-threshold Cascaded Cuckoo Filter (H-CCF) for high-threshold monitoring. L-CCF and H-CCF can identify items whose frequency are more than the given threshold while a desired false negative rate (FNR) is achieved and communication overhead is optimized. The key idea is to compress the communication overhead caused by transferring the ID and frequency information at the same time. First, to reduce the communication overhead of transferring IDs, we propose to encode the IDs into separate tiny parts and store these tiny parts in L-CCF or H-CCF. Second, to reduce the communication overhead of transferring frequencies, we adopt carry-in counter technique in L-CCF and multiple sampling technique in H-CCF. We evaluated L-CCF and H-CCF on two real-world traces and compared their performance with two prior adapted algorithms. Our experimental results show that on average, L-CCF and H-CCF achieve FNRs with 55.7% and 65.56% better than that of comparison algorithms while FPRs is maintained at the level of 2.23%.

Nowadays, location-based services are proliferating and being widely deployed. For example, a Yelp user can obtain a list of the recommended restaurants near his/her current location. For some small or medium location service providers, they may rely on commercial cloud services, e.g., Dropbox, to store the tremendous geospatial data and deal with a number of user queries. However, it is challenging to achieve a secure and efficient location-based query processing over encrypted geospatial data stored on the cloud. In this paper, we propose the Secure and Efficient Query Processing (SecEQP) scheme to address the secure k nearest neighbor (SkNN) query problem. SecEQP employs the projection function-based approach to code neighbor regions of a given location. Given the codes of two locations, the cloud server only needs to compare whether codes equal or not to check the proximity of the two locations. The codes are further embedded into an indistinguishable Bloom filter tree to build a secure and efficient index. The security of SecEQP is formally proved in the random oracle model. We further prototype SecEQP scheme and evaluate its performance on both real-world and synthetic datasets. Our evaluation results show that SecEQP is a highly efficient approach, e.g., top-10 NN query over 1 million datasets only needs less than 40 msec to get queried results.

Nearest neighbor query processing is a fundamental problem that arises in many fields such as spatial databases and machine learning. ASPE, which uses invertible matrices to encrypt data, is a widely adopted Secure Nearest Neighbor (SNN) query scheme. Encrypting data by matrices is actually a linear combination of the multiple dimensions of the data, which is completely consistent with the relationship between the source signals and observed signals in the signal processing. By viewing dimensions of the data and the encrypted data as source signals and observed signals, respectively, we formally prove and experimentally demonstrate that ASPE is actually insecure against even ciphertext only attacks, using signal processing theory. Prior work proved that it is impossible to construct an SNN scheme even in much relaxed standard security models, we invalidate this hardness understanding by pointing out the incorrectness of the hardness proof.

Respiration rate monitoring is beneficial for the diagnosis of a variety of diseases, such as heart failure and sleep disorders. Radio Frequency (RF) based respiration rate monitoring systems, namely ultra-wideband radar and COTS device, have been proposed without requiring any direct contact with the detected person. However, existing RF based systems either require expensive UWB radio (radar based) or work only in stationary environments (COTS device based). To address the limitations of both radar based and COTS device based systems, in this paper, we propose RespiRadio, a system that can detect a person's respiration rate in dynamic ambient environments via a single TX-RX pair of WiFi cards. The key novelty of RespiRadio is that it overcomes the limit of existing COTS device based respiration rate systems by synthesizing a wider-bandwidth WiFi radio. With the synthesized WiFi radio, we can identify the path reflected by the breathing person and then analyze the periodicity of the signal power measurements only from this path to infer the respiration rate. We experimentally evaluate the performance of RespiRadio in non-static indoor environments and the results demonstrate that the overall estimation error is 0.152 breaths per minute (bpm).

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today’s large-scale data analytics [1], [2]. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job’s lifetime, which makes it difficult to assign valuable tasks to well-performed machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.

This paper addresses the fundamental problem of identifying driver talking directions using a single smartphone, which can help drivers by warning distraction of having conversations with passengers in a vehicle and enable safety enhancement. The basic idea of our system is to perform talking status and direction identification using two microphones on a smartphone. We first use the sound recorded by the two microphones to identify whether the driver is talking or not. If yes, we then extract the so-called channel fingerprint from the speech signal and classify it into one of three typical driver talking directions, namely, front, right and back, using a trained model obtained in advance. The key novelty of our scheme is the proposition of channel fingerprint which leverages the heavy multipath effects in the harsh in-vehicle environment and cancels the variability of human voice, both of which combine to invalidate traditional TDoA, DoA and fingerprint based sound source localization approaches. We conducted extensive experiments using two kinds of phones and two vehicles for four phone placements in three representative scenarios, and collected 23 hours voice data from 20 participants. The results show that our system can achieve 95.0% classification accuracy on average.

Voice has been used as biometrics for human authentication because different people have different voice characteristics due to different vocal tract shapes and intonations. However, traditional voice based human authentication is subject to four types of attacks: impersonation, voice conversion, synthesis and voice replay. In this paper, we propose SpeakPrint, an ultrasound based human speech authentication scheme for smartphones which is resistant for these attacks. Compared with traditional speech authentication system which focuses on what a user speaks, SpeakPrint captures how a user speaks by recording mouth and vocal movement through ultrasound signal at the same time. Our key insight is that for the valid user, features extracted from voice signal should be consistent with his mouth and vocal movement recorded from ultrasound signal, while an imitator or an audio player can't produce the same signals in ultrasound domain. SpeakPrint extracts MFCC feature in normal voice frequency and MMSI features from ultrasound signal. An SVM classifier is trained to detect these attacks by comparing above feature differences. We implemented SpeakPrint on Samsung S5 and conducted experiments on 40 users. Experimental results show that SpeakPrint can detect replay attacks with 100% accuracy and replay attack with lip synching for 99.12% for passphrases longer than five words. This technology can be used in multi-factor authentication systems, where multiple authentication mechanisms are used to achieve defense in depth.

Efficient and effective objects identification using radio frequency identification (RFID) is always a challenge in large-scale industrial and commercial applications. Among existing solutions, the tree-based splitting scheme has attracted increasing attention because of its high extendibility and feasibility. However, the conventional tree splitting algorithms can only solve tag collision with counter value equals to zero and usually result in performance degradation when the number of tags is large. To overcome such drawbacks, we propose a novel tree-based method called fast splitting algorithm based on consecutive slot status detection (FSA-CSS), which includes a fast splitting (FS) mechanism and a shrink mechanism. Specifically, the FS mechanism is used to reduce collisions by increasing commands when the number of consecutive collision is above a threshold, whereas the shrink mechanism is used to reduce extra idle slots introduced by the FS. Simulation results supplemented by prototyping tests show that the proposed FSA-CSS achieves a system throughput of 0.41, outperforming the existing ultra high frequency RFID solutions.

In this paper, we propose a system called R# to estimate the number of human objects using passive RFID tags but without attaching anything to human objects. The idea is based on our observation that the more human objects are present, the higher the variation in the RSS values of the tag backscattered RF signals. Thus, based on the received RF signals, the reader can estimate the number of human objects. R# includes an RFID reader and some (say 20) passive tags, which are deployed in the region that we want to monitor the number of human objects, such as the region in front of a supermarket shelf. The RFID reader periodically emits RF signals to identify all tags and the tags simply respond with their IDs via EPCglobal Class 1 Generation 2 protocol. We implemented R# using commercial Impinj H47 passive RFID tags and Impinj reader model R420. We conducted experiments in a simulated picking aisle area of the supermarket environment. The experimental results show that R# can achieve high estimation accuracy (more than 90 percent with up to ten human objects).

Recently, handwriting recognition approaches has been widely applied to Human-Computer Interface (HCI) applications. The emergence of the novel mobile terminals urges a more man-machine friendly interface mode. The previous air-writing recognition approaches have been accomplished by virtue of cameras and sensors. However, the vision based approaches are susceptible to the light condition and sensor based methods have disadvantages in deployment and highcost. The latest researches have demonstrated that the pervasive wireless signals can be used to identify different gestures. In this paper, we attempt to utilize channel state information (CSI) derived from wireless signals to realize the device-free air-write recognition called Wi-Fi. Compared to the gesture recognition, the increased diversity and complexity of characters of the alphabet make it challenging. The Principle Component Analysis (PCA) is used for denoising effectively and the energy indicator derived from the Fast Fourier Transform (FFT) is to detect action continuously. The unique CSI waveform caused by unique writing patterns of 26 letters serve as feature space. Finally, the Hidden Markov model (HMM) is used for character modeling and classification. We conduct experiments in our laboratory and get the average accuracy of the Wi-Fi are 86.75 and 88.74 percent in two writing areas, respectively.

In this work, we present a supervised object segmentation algorithm for unconstrained video. Instead of arbitrarily picking a few frames for manual labeling, as in many existing supervised methods, the proposed method selects frames in a more reasonable manner, called supervision optimization. For this, we formulate a principled objective function by inferring the propagation error from appearance and motion clues. After this, we construct a multilevel segmentation model, which consists of low-level and high-level features. On the low level, image pixels are used for a more accurate estimation of motion and segmentation. On the high level, image segments are considered for a more semantic classification of the foreground and background. By integrating these in one segmentation graph, the result can be further improved by leveraging the knowledge from both levels. In experiments, the proposed approach is evaluated by different measures, and the results on a benchmark demonstrate the effectiveness in comparison with other state-of-the-art algorithms.

In this study, we propose an effective and efficient algorithm for unconstrained video object segmentation, which is achieved in a Markov random field (MRF). In the MRF graph, each node is modeled as a superpixel and labeled as either foreground or background during the segmentation process. The unary potential is computed for each node by learning a transductive SVM classifier under supervision by a few labeled frames. The pairwise potential is used for the spatial-temporal smoothness. In addition, a high-order potential based on the multinomial event model is employed to enhance the appearance consistency throughout the frames. To minimize this intractable feature, we also introduce a more efficient technique that simply extends the original MRF structure. The proposed approach was evaluated in experiments with different measures and the results based on a benchmark demonstrated its effectiveness compared with other state-of-the-art algorithms.

Regular Expression (RegEx) matching is the industry standard for Deep Packet Inspection (DPI) because RegExes are significantly more expressive than strings. To achieve high matching speed, we need to convert the RegExes to Deterministic Finite State Automata (DFA). However, DFA has the state explosion problem, that is, the number of DFA states and transitions can be exponential with the number of RegExes. Much work has addressed the DFA state explosion problem; however, none has met all the requirements of fast and automated construction, small memory image, and high matching speed. In this paper, we propose a decompositional approach, with fast and automated construction, small memory image, and high matching speed, to DFA state explosion. The first key idea is to decompose a complex RegEx that cause exponential state increases into a set of simpler RegExes that do not cause exponential state increases, where any character string that matches the complex RegEx also matches all the RegExes in the set of simpler RegExes; that is, the set of strings that match the complex RegEx is a subset of strings that match the set of simpler RegExes. The second key idea is to use a stateful post-processing engine to filter the matches that are actually the matches of the complex RegEx. Given an input string for matching, instead of using the large DFA constructed from the original complex RegEx to perform the matching, we first use the small DFA constructed from the set of simpler RegExes to perform the matching, and then, if the small DFA reports a match, we use the post-processing engine to determine whether it is a true match to the original complex RegEx. Because the pre-processing is simple, automaton construction can be automated and fast, and because most on-line processing is done by a DFA, its matching speed is close to that of a DFA alone. Our experimental results show that our decompositional approach achieves orders of magnitude faster DFA construction (in terms of seconds instead of minutes), 30 times smaller memory image, and 43% faster matching speeds, than state-of-the-art software based RegEx matching algorithms.

The rise of mobile crowd sensing has brought privacy issues into a sharp view. In this paper, our goal is to achieve the predictable privacy-preserving mobile crowd sensing, which we envision to have the capability to quantify the privacy protections, and simultaneously allowing application users to predict the utility loss at the same time. TheSalusalgorithm is first proposed to protect the private data against the data reconstruction attacks. To understand privacy protection, we quantify the privacy risks in terms of private data leakage under reconstruction attacks. To predict the utility, we provide accurate utility predictions for various crowd sensing applications using Salus. The risk assessments can be generally applied to different type of sensors on the mobile platform, and the utility prediction can also be used to support various applications that use data aggregators such as average, histogram, and classifiers. Finally, we propose and implement the$P^{3}$application framework. Both measurement results using online datasets and real-world case studies show that the$P^{3}$provides accurate risk assessments and utility estimations, which makes it a promising framework to support future privacy-preserving mobilecrowd sensing applications.

As powerline communication (PLC) technology does not require dedicated cabling and network setup, it can be used to easily connect multitude of IoT devices deployed in enterprise environments for sensing and control related applications. IEEE has standardized the PLC protocol in IEEE 1901, also known as HomePlug AV (HPAV), which is widely adopted PLC standard. A key weakness of HPAV protocol is that it does not support any spectrum sharing strategies. Currently, each link in an HPAV PLC network operates over the whole available spectrum, and only one link can operate at any time within a single collision domain. We conducted a large scale measurement study using commodity HPAV PLC devices and analyzed channel characteristics of PLC networks in a real enterprise environment across space, time, and spectral dimensions. Based on our findings, we propose a distributed spectrum sharing technique for enterprise PLC networks, and show that fine-grained distributed spectrum sharing on top of current HPAV MAC protocols can boost the aggregated and per-link throughput by up to 60% and 250% respectively, by allowing multiple PLC links to communicate concurrently, while requiring a few modifications to the existing HPAV PLC devices and protocols.

This paper studies the problem of cHarging tAsk Scheduling for direcTional wireless chargEr networks (HASTE), i.e., given a set of rotatable directional wireless chargers on a 2D area and a series of offline (online) charging tasks, scheduling the orientations of all the chargers with time in a centralized offline (distributed online) fashion to maximize the overall charging utility for all the tasks. We prove that HASTE is NP-hard. Then, we prove that a relaxed version of HASTE falls within the realm of maximizing a submodular function subject to a partition matroid constraint, and propose a centralized offline algorithm that achieves (1-ρ)(1-1/e) approximation ratio to address HASTE where ρ is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves 1/2(1-ρ)(1-1/e) competitive ratio. We conduct simulations, and field experiments on a testbed consisting of 8 off-the-shelf power transmitters and 8 rechargeable sensor nodes. The results show that our distributed online algorithm achieves 92.97% of the optimal charging utility, and outperforms the comparison algorithms by up to 26.19% in terms of charging utility.

This paper proposes a new counter architecture for network measurement called Cache Assisted and randomizEd ShAring counteRs (CAESAR). One of the greatest challenges for per-flow traffic measurement is designing an online measurement module to keep up with the rapid growth of link speed. To address this challenge, we use a fast on-chip memory as the cache before the slow off-chip SRAM counters, thereby decreasing the accesses per flow to off-chip counters to improve time efficiency without any packet loss. We use randomized sharing counters among multiple flows in SRAM to achieve a compact data structure with high storage efficiency. By removing the impact from other flows sharing counters with a specific flow, we theoretically analyze the expectation and confidence interval of its estimated flow size accurately. In this paper, we use the real-world network traces for software simulations and FPGA experiments on the Xilinx Virtex-7 FPGA chip to validate our theoretical findings. The results show that CAESAR is up to 92.4% and 90% faster than prior work CASE and RCS respectively, and CAESAR reduces the average relative error of CASE and RCS by more than half.

Software-Defined Networking (SDN), which separates the control plane and data plane, is a promising new network architecture for the Future Internet. OpenFlow is the de facto standard which defines the communication protocol between the controller and switches. The most challenging issue in OpenFlow switches is the lookup of multiple OpenFlow tables. The lookup of OpenFlow tables is so complicated that the state-of-the-art research are still focusing on the design of lookup pipeline architecture, and there is no specific algorithm for the lookup of OpenFlow tables. In this paper, we revise the long-pipeline architecture of OpenFlow 1.4 to a 5-stage pipeline architecture to make a trade-off between flexibility and implementability, and decompose the lookup of OpenFlow tables into three kinds of lookup: longest prefix matching (IP lookup), multi-field matching (packet classification), and exact matching. Then we design new algorithms for packet classification, because the state-of-the-art solutions for them seldom support fast update which is highly demanding for OpenFlow. The other two kinds of lookups can be well handled by state-of-the-art. Experimental results show that our proposed algorithms work excellently, and outperform state-of-the-art solutions.

This paper concerns the problem of finding persistent items in distributed datasets, which has many applications such as port scanning and intrusion detection. To the best of our knowledge, there is no existing solution for finding persistent items in distributed datasets. In this paper, we propose DISPERSE, a probabilistic algorithm that can find persistent items in distributed datasets without collecting all the datasets. Our basic idea is that each monitor compresses each item ID in its dataset in a lossy fashion, sends the set of lossily compressed item IDs to the server, then the server recovers the IDs of the persistent items. We design the lossy compression so that given one lossily compressed item ID, the server cannot recover the item ID, but when the number of lossily compressed versions of the same item ID exceeds a threshold, which means that such items are persistent ones, the server can recover the item ID with a high probability. This threshold is exactly the threshold in the definition of persistent items. We implemented DISPERSE and evaluated its performance. In comparison with the straightforward solution, DISPERSE achieves a compression ratio of 26.5% with FNR=3.5% and FPR=O. In comparison with a developed Bloom filter based scheme and the adapted kBF and IBF schemes, our scheme can achieve 7.9, 5.7, and 6.6 times performance gains, respectively, in terms of compression ratio.

In this paper, we first study the problem of Connected wIReless Charger pLacEment (CIRCLE). That is, given a fixed number of directional wireless chargers and candidate positions, determining the placement position and orientation angle for each charger under connectivity constraint for wireless chargers such that the overall charging utility is maximized. To address CIRCLE, we first consider a relaxed version of CIRCLE (CIRCLE-R for short). We prove that CIRCLE-R falls into the realm of maximizing a submodular set function subject to a connectivity constraint, and propose an algorithm whose approximation ratio is at least 1.5 times better than that of the state-of-the-art algorithm. Next, we reduce the solution space for CIRCLE from infinite to finite, and propose an algorithm with a constant approximation ratio to address CIRCLE. We conduct both simulations and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35 %.

For AR/VR systems, tapping-in-the-air is a user-friendly solution for interactions. Most prior in-air tapping schemes use customized depth-cameras and therefore have the limitations of low accuracy and high latency. In this paper, we propose a fine-grained depth-aware tapping scheme that can provide high accuracy tapping detection. Our basic idea is to use light-weight ultrasound based sensing, along with one COTS mono-camera, to enable 3D tracking of user's fingers. The mono-camera is used to track user's fingers in the 2D space and ultrasound based sensing is used to get the depth information of user's fingers in the 3D space. Using speakers and microphones that already exist on most AR/VR devices, we emit ultrasound, which is inaudible to humans, and capture the signal reflected by the finger with the microphone. From the phase changes of the ultrasound signal, we accurately measure small finger movements in the depth direction. With fast and light-weight ultrasound signal processing algorithms, our scheme can accurately track finger movements and measure the bending angle of the finger between two video frames. In our experiments on eight users, our scheme achieves a 98.4% finger tapping detection accuracy with FPR of 1.6% and FNR of 1.4%, and a detection latency of 17.69ms, which is 57.7ms less than video-only schemes. The power consumption overhead of our scheme is 48.4% more than video-only schemes.

With the rising of AR/VR technology and miniaturization of mobile devices, gesture is becoming an increasingly popular means of interacting with smart devices. Some pioneer ultrasound based human gesture recognition systems have been proposed. They mostly rely on low resolution Doppler Effect, and hence focus on whole hand motion and cannot deal with minor finger motions. In this paper, we present UltraGesture, a Channel Impulse Response (CIR) based ultrasonic finger motion perception and recognition system. CIR measurements can provide with 7 mm resolution, rendering it sufficient for minor finger motion recognition. UltraGesture encapsulates CIR measurements into an image, and builds a Convolutional Neural Network model to classify these images into different categories, which corresponding to distinct gestures. Our system runs on commercial speakers and microphones that already exist on most mobile devices without hardware modification. Our results show that UltraGesture achieves an average accuracy of greater than 97% for 12 gestures including finger click and rotation.

Gesture tracking is a basic Human-Computer Interaction mechanism to control devices such as electronic Internet of Things and VR/AR devices. However, prior WiFi signal based systems focus on gesture recognition and provide results with insufficient accuracy, and thus cannot be applied for highprecision gesture tracking. In this paper, we propose a CSI based device-free gesture tracking system, called WiTrace, which leverages the CSI values extracted from WiFi signals to enable accurate gesture tracking. For 1D tracking, WiTrace derives the phase of the signals reflected by the hand from the composite signals, and measures the phase changes to obtain the movement distance. For 2D tracking, WiTrace proposes the first CSI based scheme to accurately estimate the initial position, and adopts the Kalman filter based on Continuous Wiener Process Acceleration model to further filter out tracking noise. Our results show that WiTrace achieves the estimated accuracy of 3.91 cm for initial position on average, and achieves cm-level accuracy, with mean tracking errors of 1.46 cm and 2.09 cm for 1D tracking and 2D tracking, respectively.

Verifiable pattern matching is the problem of finding a given pattern verifiably from the outsourced textual data, which is resident in an untrusted remote server. This problem has drawn much attention due to a large number of applications. The state-of-the-art method for this problem suffers from low efficiency. To enable fast verifiable pattern matching, we propose a novel scheme in this paper. Our scheme is based on an ordered set accumulator data structure and a newly developed verifiable suffix array structure, which only involves fast cryptographic hash computations. Our scheme also supports fast multiple-occurrence pattern matching. A striking feature of our proposed scheme is that our scheme works even with no secret keys, which ensures public verifiability. We conduct extensive experiments to evaluate the proposed scheme using Java. The results show that our scheme is orders of magnitude faster than the state-of-the-art work. Specifically, our scheme with public verifiability only costs a preprocessing time of 47 s (merely one-time off-line cost during outsourcing), a search time of 30 μs, a verification time of 149 μs, and a proof size of 2760 bytes for a verifiable pattern matching query with pattern length 200 on 10-million long textual data which consists of sequences of two-byte, Unicode characters in Java.

With the increasing adoption of cloud computing, a growing number of users outsource their datasets to cloud. To preserve privacy, the datasets are usually encrypted before outsourcing. However, the common practice of encryption makes the effective utilization of the data difficult. For example, it is difficult to search the given keywords in encrypted datasets. Many schemes are proposed to make encrypted data searchable based on keywords. However, keyword-based search schemes ignore the semantic representation information of users' retrieval, and cannot completely meet with users search intention. Therefore, how to design a content-based search scheme and make semantic search more effective and context-aware is a difficult challenge. In this paper, we propose ECSED, a novel semantic search scheme based on the concept hierarchy and the semantic relationship between concepts in the encrypted datasets. ECSED uses two cloud servers. One is used to store the outsourced datasets and return the ranked results to data users. The other one is used to compute the similarity scores between the documents and the query and send the scores to the first server. To further improve the search efficiency, we utilize a tree-based index structure to organize all the document index vectors. We employ the multi-keyword ranked search over encrypted cloud data as our basic frame to propose two secure schemes. The experiment results based on the real world datasets show that the scheme is more efficient than previous schemes. We also prove that our schemes are secure under the known ciphertext model and the known background model.

The widely used RFID systems are vulnerable to the denial-of-service (DoS) attacks launched by malicious blocker tags. This paper studies how to quickly and completely identify the valid RFID tags that are blocked. The existing work that can seemingly address this problem suffers from either low time-efficiency or serious false positives. This paper proposes a hybrid approach that consists of two complementary component protocols, namelyAloha Filtering(AF) andPoll&Listen(PL).AFis fast but inaccurate, whilePLis accurate but slow. Taking the merit of each protocol, our hybrid approach is to first repeat the fastAFfor multiple rounds to quickly filter out the target tags that are definitely not blocked. Then, on the size-reduced remaining set that just contains a small number of suspicious tags, we invoke the accuratePLto verify the intactness of each suspicious tag with 100 percent confidence. We optimize the round count ofAFthat trades off between the time costs ofAFandPLto minimize the total time ofAF+PL. As required in the optimization process, we need to know the size of the blocked tag set and that of the unknown tag set, which, however, are not known in advance. To estimate these two set sizes, we propose a supplementary protocol calledSimultaneous Estimation of the Blocked tag size and the Unknown tag size(SEBU). The key advantages of our approach over the prior art are four-fold. First, unlike the detection protocol that just discovers the existence of blocking attacks, our approach exactly identifies all the blocked target tags. Second, our approach is compliant with the C1G2 standard, and does not require any modifications to be made to the commercial RFID tags. It only needs to be installed on readers as a software module. Third, our approach does not involve any false positives. Finally, our approach significantly reduces the execution time when compared with the state-of-the-art schemes that can completely identify the blocked tags.

Content delivery networks (CDNs) maintain multiple transit routes from content distribution servers to eyeball ISP networks which provide Internet connectivity to end users. Due to the dynamics of varying performance and pricing on transit routes, CDNs need to implement a transit route selection strategy to optimize performance and cost tradeoffs. In this paper, we formalize the transit routing problem using a multi-attribute objective function to simultaneously optimize end-to-end performance and cost. Our approach allows CDNs to navigate the cost and performance tradeoff in transit routing through a single control knob. We evaluate our approach using real-world measurements from CDN servers located at 19 geographically distributed Internet exchange points. Using our approach, CDNs can reduce transit costs on average by 57% without sacrificing performance.

Wireless power transfer technology is considered as one of the promising solutions to address the energy limitation problems for end-devices, but its incurred potential risk of electromagnetic radiation (EMR) exposure is largely overlooked by most existing works. In this paper, we consider the Safe Charging with Adjustable PowEr (SCAPE) problem, namely, how to adjust the power of chargers to maximize the charging utility of devices, while assuring that EMR intensity at any location in the field does not exceed a given threshold Rt. We present novel techniques to reformulate SCAPE into a traditional linear programming problem, and then remove its redundant constraints as much as possible to reduce computational effort. Next, we propose a series of distributed algorithms, including a fully distributed algorithm that provably achieves (1- ϵ) approximation ratio and requires only communications with neighbors within a constant distance for each charger. Through extensive simulation and testbed experiments, we demonstrate that our proposed algorithms can outperform the set-cover algorithm by up to 17.05%, and has an average performance gain of 41.1% over the existing algorithm in terms of the overall charging utility.

This paper studies the problem of Radiation cOnstrained scheduling of wireless Charging tasKs (ROCK), that is, given wireless charging tasks with required charging energy and charging deadline for rechargeable devices, scheduling the power of wireless chargers to maximize the overall effective charging energy for all rechargeable devices, and further to minimize the total charging time, while guaranteeing electromagnetic radiation (EMR) safety, i.e., no point on the considered 2-D area has EMR intensity exceeding a given threshold. To address ROCK, we first present a centralized algorithm. We transform ROCK from nonlinear problem to linear problem by applying two approaches of area discretization and solution regularization, and then propose a linear programming-based greedy test algorithm to solve it. We also propose a distributed algorithm that is scalable with network size by presenting an area partition scheme and two approaches called area-scaling and EMR-scaling, and prove that it achieves effective charging energy no less than (1- ε) of that of the optimal solution, and charging time no more than that of the optimal solution. We conduct both simulation and field experiments to validate our theoretical findings. The results show that our algorithm achieves 94.9% of the optimal effective charging energy and requires 47.1% smaller charging time compared with the optimal one when ε ≥ 0.2, and outperforms the other algorithms by at least 350.1% in terms of charging time with even more effective charging energy.

This paper addresses the fundamental problem of finding persistent items and estimating the number of times each persistent item occurred in a given data stream during a given period of time at any given observation point. We propose a novel scheme, PIE, that can not only accurately identify each persistent item with a probability greater than any desired false negative rate (FNR), but can also accurately estimate the number of occurrences of each persistent item. The key idea of PIE is that it uses Raptor codes to encode the ID of each item that appears at the observation point during a measurement period and stores only a few bits of the encoded ID in the memory. The item that is persistent occurs in enough measurement periods that enough encoded bits for the ID can be retrieved from the observation point to decode them correctly and get the ID of the persistent item. To estimate the number of occurrences of any given persistent item, PIE uses maximum likelihood estimation-based statistical techniques on the information already recorded during the measurement periods. We implemented and evaluated PIE using three real network traffic traces and compared its performance with three prior schemes. Our results show that PIE not only achieves the desire FNR in every scenario, its average FNR can be 19.5 times smaller than the FNR of the adapted prior scheme. Our results also show that PIE achieves any desired success probability in estimating the number of occurrences of persistent items.

The human-computer interactions have moved from the conventional approaches of entering inputs into the keyboards/touchpads to the brand-new approaches of performing interactions in the air. In this paper, we propose RF-glove, a system that recognizes concurrent multiple finger micromovement using RF signals, so as to realize the vision of “multi-touch in the air.” It uses a commercial-off-the-shelf (COTS) RFID reader with three antennas and five COTS tags attached to the five fingers of a glove, one tag per finger. During the process of a user performing finger micromovements, we let the RFID reader continuously interrogate these tags and obtain the backscattered RF signals from each tag. For each antenna-tag pair, the reader obtains a sequence of RF phase values called a phase profile from the tag's responses over time. To tradeoff between accuracy and robustness in terms of matching resolution, we propose a two phase approach, including coarse-grained filtering and fine-grained matching. To tackle the variation of template phase profiles at different positions, we propose a phase-model-based solution to reconstruct the template phase profiles based on the exact locations. Experiment results show that we achieve an average accuracy of 92.1% under various moving speeds, orientation deviations, and so on.

Inefficient bandwidth sharing in a datacenter network, between different application frameworks, e.g., MapReduce and Spark, can lead to inelastic and skewed usage of link bandwidth and increased completion times for the applications. Existing work, however, either solely focuses on managing computation and storage resources or controlling only sending/receiving rate at hosts. In this paper, we present CoMan, a solution that provides global in-network bandwidth management in multiplexed data centers, with two goals: improving bandwidth utilization and reducing application completion time. CoMan first designs a novel abstraction of virtual link groups (VLGs) to establish a shared bandwidth resource pool. Based on this pool, CoMan implements a three-level bandwidth allocation model, which enables elastic bandwidth sharing among computing frameworks as well as guarantees network performance for the applications. CoMan further improves the bandwidth utilization by devising a VLG dependency graph and solves an optimization problem to guide the path selection using a 32-approximation algorithm. We conduct comprehensive trace-driven simulations as well as small-scale testbed experiments to evaluate the performance of CoMan. Extensive simulation results show that CoMan improves the bandwidth utilization and speeds up the application completion time by up to 2.83× and 6.68×, respectively, compared to the ECMP + ElasticSwitch solution. Our implementation also verifies that CoMan can realistically speed up the application completion times by 2.32× on average.

Using FPGA as accelerators is gaining popularity in Cloud computing. Usually, FPGA accelerators in a datacenter are managed as a single resource pool. By issuing a request to this pool, a tenant can transparently access FPGA resources. FPGA requests usually arrive in batches. The objective of scheduling is to minimize the make-span of a given batch of requests, which is the completion time of the entire batch of jobs. As a result, either the responsiveness is improved, or the system throughput is maximized. The key technical challenge is the existence of multiple resource bottlenecks. An FPGA job can be bottlenecked by either computation (i.e., computation-intensive) or network (i.e., network-intensive), and sometimes by both. To the best of our knowledge, this is the first work that minimizes the make-span of batched requests for an FPGA accelerator pool in Cloud computing that considers multiple resource bottlenecks. In this paper, we design several scheduling algorithms to address the challenge. We implement our scheduling algorithms in an IBM Cloud system. We conduct extensive evaluations on both a small scale testbed and a large-scale simulator. Compared with the Shortest-Job-First scheduling, our algorithms can reduce the make-span by 36.25 percent, and improve the system throughput by 36.05 percent.

Fog computing is emerging as a powerful and popular computing paradigm to perform IoT (Internet of Things) applications, which is an extension to the cloud computing paradigm to make it possible to execute the IoT applications in the network of edge. The IoT applications could choose fog or cloud computing nodes for responding to the resource requirements, and load balancing is one of the key factors to achieve resource efficiency and avoid bottlenecks, overload, and low load. However, it is still a challenge to realize the load balance for the computing nodes in the fog environment during the execution of IoT applications. In view of this challenge, a dynamic resource allocation method, named DRAM, for load balancing in fog environment is proposed in this paper. Technically, a system framework for fog computing and the load‐balance analysis for various types of computing nodes are presented first. Then, a corresponding resource allocation method in the fog environment is designed through static resource allocation and dynamic service migration to achieve the load balance for the fog computing systems. Experimental evaluation and comparison analysis are conducted to validate the efficiency and effectiveness of DRAM.

RFID systems have been widely deployed for various applications such as supply chain management, indoor localization, inventory control, and access control. This paper deals with the fundamental problem of estimating the number of arriving and departing tags between any two time instants in dynamically changing RFID tag populations, which is needed in many applications such as warehouse monitoring and privacy sensitive RFID systems. In this paper, we propose a dynamic tag estimation scheme, namely DTE, that can achieve arbitrarily high required reliability, is compliant with the C1G2 standard, and works in single as well as multiple-reader environment. DTE uses the standardized frame slotted Aloha protocol and utilizes the number of slots that change their values in corresponding Aloha frames at the two time instants to estimate the number of arriving and departing tags. It is easy to deploy because it neither requires modification to tags nor to the communication protocol between tags and readers. We have extensively evaluated and compared DTE with the only prior scheme, ZDE, that can estimate the number of arriving and departing tags. Unfortunately, ZDE can not achieve arbitrarily high required reliability. In contrast, our proposed scheme always achieves the required reliability. For example, for a tag population containing 10 4 tags, a required reliability of 95%, and a required confidence interval of 5%, DTE takes 5.12 seconds to achieve the required reliability whereas ZDE achieves a reliability of only 66% in the same amount of time.

The fast increasing location-dependent applications in mobile devices are manufacturing a plethora of geospatial data. Outsourcing geospatial data storage to a powerful cloud is an economical approach. However, safeguarding data users' location privacy against the untrusted cloud while providing efficient location-aware query processing over encrypted data are in conflict with each other. As a step to reconcile such conflict, we study secure k nearest neighbor (SkNN) queries processing over encrypted geospatial data in cloud computing. We design 2D SkNN (2DSkNN), a scheme achieves both strong provable security and high-efficiency. Our approach employs locality sensitive hashing (LSH) in a dimensional-increased manner. This is a counter-intuitive leverage of LSH since the traditional usage of LSH is to reduce the data dimensionality and solve the so-called "curse of dimensionality" problem. We show that increasing the data dimensionality via LSH is indeed helpful to tackle 2DSkNN problem. By LSH-based neighbor region encoding and two-tier prefix-free encoding, we turn the proximity test to be sequential keywords query with a stop condition, which can be well addressed by any existing symmetric searchable encryption (SSE) scheme. We show that 2DSkNN achieves adaptive indistinguishability under chosen-keyword attack (IND2-CKA) secure in the random oracle model. A prototype implementation and experiments on both real-world and synthetic datasets confirm the high practicality of 2DSkNN.

This paper concerns the fundamental problem of processing conjunctive queries that contain both keyword conditions and range conditions on public clouds in a privacy preserving manner. No prior Searchable Symmetric Encryption (SSE) based privacy-preserving conjunctive query processing scheme satisfies the three requirements of adaptive security, efficient query processing, and scalable index size. In this paper, we propose the first privacy preserving conjunctive query processing scheme that satisfies the above requirements. To achieve adaptive security, we propose an Indistinguishable Bloom Filter (IBF) data structure for indexing. To achieve efficient query processing and structure indistinguishability, we propose a highly balanced binary tree data structure called Indistinguishable Binary Tree (IBtree). To optimize searching efficiency, we propose a traversal width minimization algorithm and a traversal depth minimization algorithm. To achieve scalable and compact index size, we propose an IBtree space compression algorithm to remove redundant information in IBFs. We formally prove that our scheme is adaptive secure using a random oracle model. The key contribution of this paper is on achieving conjunctive query processing with both strong privacy guarantee and practical efficiency in terms of both speed and space. We implemented our scheme in C++, evaluated and compared its performance with KRB [24] for keyword queries and PBtree [32] for range queries on two real-world data sets. Experimental results show that our scheme is fast and scalable (in milliseconds).

Multipath TCP (MPTCP) is an IETF standardized suite of TCP extensions that allow two endpoints to simultaneously use multiple paths between them. In this paper, we report vulnerabilities in MPTCP that arise because of cross-path interactions between MPTCP subflows. First, an attacker eavesdropping one MPTCP subflow can infer throughput of other subflows. Second, an attacker can inject forged MPTCP packets to change priorities of any MPTCP subflow. We present two attacks to exploit these vulnerabilities. In the connection hijack attack, an attacker takes full control of the MPTCP connection by suspending the subflows he has no access to. In the traffic diversion attack, an attacker diverts traffic from one path to other paths. Proposed vulnerabilities fixes, changes to MPTCP specification, provide the guarantees that MPTCP is at least as secure as TCP and the original MPTCP. We validate attacks and prevention mechanism, using MPTCP Linux implementation (v0.91), on a real-network testbed.

It is crucial for cellular data network operators to understand the service quality perceived by its customers. The state-of-art systems deployed in cellular networks mostly report service quality aggregated on cell site level, which is typically an aggregation of tens or hundreds of customers depending on the locations of the cell sites. In this paper, we propose to enhance the measurement of customer-perceived service quality by leveraging M2M devices as sensors in the field, which provide an unprecedented opportunity for cellular network operators to measure what end-users experience with better accuracy and coverage. Our approach is to identify a set of M2M devices which are stationary and communicate continuously over the cellular network over an indefinite period of time. We use these M2M devices to estimate the customer-perceived service quality during cell site outages. We implement our methodology as a system called M2MScan and evaluate M2MScan with both synthetic outages and real outages from a large-scale operational cellular network. To the best of our knowledge, this is the first work that employs M2M devices to measure the service quality perceived by customers in operational cellular networks at a large scale.

Wireless Power Transfer (WPT) technology has witnessed huge development because of its convenience and reliability. This paper concerns the fundamental issue of wireless charger PLacement with Optimized charging uTility (PLOT), that is, given a fixed number of chargers and a set of points on the plane, determining the positions and orientations of chargers such that the overall expected charging utility for all points is maximized. To address PLOT, we propose a 1 - 1/e - ε approximation algorithm. First, we present techniques to approximate the nonlinear charging power and the expected charging utility to make the problem almost linear. Second, we develop a Dominating Coverage Set extraction method to reduce the continuous search space of PLOT to a limited and discrete one without performance loss. Third, we prove that the reformulated problem is essentially maximizing a monotone submodular function subject to a matroid constraint, and propose a greedy algorithm to address this problem. We conduct both simulation and field experiments to validate our theoretical results, and the results show that our algorithm can outperform comparison algorithms by at least 46.3%.

In datacenter networks, flows can have different performance objectives. We use a tenant-objective division to denote all flows of a tenant that share the same objective. Bandwidth allocation in datacenters should support not only performance isolation among divisions but also objective-oriented scheduling among flows within the same division. This paper studies the Multi-Tenant Multi-Objective (MT-MO) bandwidth allocation problem. To our best knowledge, no existing practical work support performance isolation and objective scheduling simultaneously. We propose Stacked Congestion Control (SCC), a distributed host-based bandwidth allocation design, where an underlay congestion control (UCC) layer handles contention among divisions, and a private congestion control (PCC) layer for each division optimizes its performance objective. Via the tenant-objective tunnel abstraction, SCC achieves weighted bandwidth sharing for each division in a distributed and transparent way. By adding a rate-limiting send queue in the ingress of each tunnel, mechanisms between performance isolation and objective scheduling are completely decoupled. We evaluate SCC both on a small-scale testbed and with large-scale NS-2 simulations. Compared to the direct coexistence cases, SCC reduces latency by up to 40% for Latency-Sensitive flows, deadline miss ratio by up to 3.2× for Deadline-Sensitive flows, and average flow-completion-time by up to 53% for Completion-Sensitive flows.

This paper studies the problem of Radiation cOnstrained scheduling of wireless Charging tasKs (ROCK), that is, given wireless charging tasks with required charging energy and charging deadline for rechargeable devices, scheduling the power of wireless chargers to maximize the overall effective charging energy for all rechargeable devices, and further to minimize the total charging time, while guaranteeing electromagnetic radiation (EMR) safety, i.e., no point on the considered 2D area has EMR intensity exceeding a given threshold. To address ROCK, we first present a centralized algorithm. We transform ROCK from nonlinear problem to linear problem by applying two approaches of area discretization and solution regularization, and then propose a linear programming based greedy test algorithm to solve it. We also propose a distributed algorithm by presenting an area partition scheme and two approaches called area-scaling and EMR-scaling, and prove that it achieves effective charging energy no less than (1 -- ϵ) of that of the optimal solution, and charging time no more than that of the optimal solution. We conduct both simulation and field experiments to validate our theoretical findings. The results show that our algorithm achieves 94.9% of the optimal effective charging energy and requires 47.1% smaller charging time compared with the optimal one when ϵ ≥ 0.2, and outperforms the other algorithms by at least 350.1% in terms of charging time with even more effective charging energy.

Outdoor localization is of great importance for driving navigation, attracting many research efforts in past decades. Prevailing GPS achieves meter-level localization accuracy under general outdoor conditions. Yet, GPS service performs poorly in urban canyons where skyscrapers blocks GPS signals and drain mobile phone battery quickly within few hours. In this work, we exploit common city facilities, i.e. speed humps, as an indicator for vehicle location. The key insight is that when the vehicle passes through the speed bump, it experiences significant fluctuations, causing larger acceleration in the vertical direction. On this basis, we design a localization scheme that utilizes the accelerator equipped on modern smart phones to track sequence of speed bumps, which is further transferred into sequence of moving directions of the vehicle, and adopt effective road mapping technology to derive real-time location. As we have concerned, it is the first attempt to exploit the spatiotemporal characteristics generated by the speed humps to recover the trajectory of the travelling route and infer the current position. Experimental results in typical outdoor environment (campus) demonstrate a comparable performance with GPS method, yet achieve lower energy consumption.

Keystroke privacy is critical for ensuring the security of computer systems and the privacy of human users as what is being typed could be passwords or privacy sensitive information. In this paper, we show for the first time that WiFi signals can also be exploited to recognize keystrokes. The intuition is that while typing a certain key, the hands and fingers of a user move in a unique formation and direction and thus generate a unique pattern in the time-series of channel state information (CSI) values, which we call CSI-waveform for that key. In this paper, we propose a WiFi signal-based keystroke recognition system called WiKey. WiKey consists of two commercial off-the-shelf WiFi devices, a sender (such as a router) and a receiver (such as a laptop). The sender continuously emits signals and the receiver continuously receives signals. When a human subject types on a keyboard, WiKey recognizes the typed keys based on how the CSI values at the WiFi signal receiver end. We implemented the WiKey system using a TP-Link TL-WR1043ND WiFi router and a Lenovo X200 laptop. WiKey achieves over 97.5% detection rate for detecting the keystroke and 96.4% recognition accuracy for classifying single keys. In real-world experiments, WiKey can recognize keystrokes in a continuously typed sentence with an accuracy of 93.5%. WiKey can also recognize complete words inside a sentence with over 85% accuracy.

The emerging paradigm of network function virtualization advocates deploying virtualized network functions (VNFs) on standard virtualization platforms for significant cost reduction and management flexibility. There have been system designs for managing dynamic deployment and scaling of VNF service chains within one cloud datacenter. Many real-world network services involve geo-distributed service chains, with prominent examples of mobile core networks and IP multimedia subsystems (IMSs)). Virtualizing these service chains requires efficient coordination of dynamic VNF deployment across geo-distributed data centers, calling for a new management system. This paper designs a dynamic scaling system for geo-distributed VNF service chains, using the case of an IMS. IMSs are widely used subsystems for delivering multimedia services among mobile users in a 3G/4G network, whose virtualization has been broadly advocated in the industry for reducing cost, improving network usage efficiency and enabling dynamic network topology reconfiguration for performance optimization. Our scaling system design caters to key control-plane and data-plane service chains in an IMS, combining proactive and reactive approaches for timely, cost-effective scaling of the service chains. The design principles are applicable to scaling of other systems with multiple related service chains. We evaluate our system using real-world experiments on both an emulation platform and a geo-distributed public cloud.

Since human bodies are good reflectors of wireless signals, human activities can be recognized by monitoring changes in WiFi signals. However, existing WiFi-based human activity recognition systems do not build models that can quantify the correlation between WiFi signal dynamics and human activities. In this paper, we propose a Channel State Information (CSI)-based human Activity Recognition and Monitoring system (CARM). CARM is based on two theoretical models. First, we propose a CSI-speed model that quantifies the relation between CSI dynamics and human movement speeds. Second, we propose a CSI-activity model that quantifies the relation between human movement speeds and human activities. Based on these two models, we implemented the CARM on commercial WiFi devices. Our experimental results show that the CARM achieves recognition accuracy of 96% and is robust to environmental changes.

Nowadays, a large number of groups choose to deploy their applications to cloud platforms, especially for the big data era. Currently, the hybrid cloud is one of the most popular computing paradigms for holding the privacy-aware applications driven by the requirements of privacy protection and cost saving. However, it is still a challenge to realize data placement considering both the energy consumption in private cloud and the cost for renting the public cloud services. In view of this challenge, a cost and energy aware data placement method, named CEDP, for privacy-aware applications over big data in hybrid cloud is proposed. Technically, formalized analysis of cost, access time, and energy consumption is conducted in the hybrid cloud environment. Then a corresponding data placement method is designed to accomplish the cost saving for renting the public cloud services and energy savings for task execution within the private cloud platforms. Experimental evaluations validate the efficiency and effectiveness of our proposed method.

Firewalls are critical security devices handling all traffic in and out of a network. Firewalls, like other software and hardware network devices, have vulnerabilities, which can be exploited by motivated attackers. However, just like any other networking and computing devices, firewalls often have vulnerabilities that can be exploited by attackers. In this paper, first, we investigate some possible firewall fingerprinting methods and surprisingly found that these methods can achieve quite high accuracy. Second, we study what we call denial of firewalling (DoF) attacks, where attackers use carefully crafted traffic to effectively overload a firewall. To the best of our knowledge, this paper represents the first study of firewall fingerprinting and DoF attacks.

Given a spatial field and the traffic flow between neighboring locations, the early detection of gathering events ( edge ) problem aims to discover and localize a set of most likely gathering events. It is important for city planners to identify emerging gathering events that might cause public safety or sustainability concerns. However, it is challenging to solve the edge problem due to numerous candidate gathering footprints in a spatial field and the nontrivial task of balancing pattern quality and computational efficiency. Prior solutions to model the edge problem lack the ability to describe the dynamic flow of traffic and the potential gathering destinations because they rely on static or undirected footprints. In our recent work, we modeled the footprint of a gathering event as a Gathering Graph (G-Graph), where the root of the directed acyclic G-Graph is the potential destination and the directed edges represent the most likely paths traffic takes to move toward the destination. We also proposed an efficient algorithm called SmartEdge to discover the most likely nonoverlapping G-Graphs in the given spatial field. However, it is challenging to perform a systematic performance study of the proposed algorithm, due to unavailability of the ground truth of gathering events. In this article, we introduce an event simulation mechanism, which makes it possible to conduct a comprehensive performance study of the SmartEdge algorithm. We measure the quality of the detected patterns, in a systematic way, in terms of timeliness and location accuracy. The results show that, on average, the SmartEdge algorithm is able to detect patterns within a grid cell away (less than 500 meters) of the simulated events and detect patterns of the simulated events as early as 10 minutes prior to the first arrival to the gathering event.

With the rich functionalities and enhanced computing capabilities available on mobile computing devices with touch screens, users not only store sensitive information (such as credit card numbers) but also use privacy sensitive applications (such as online banking) on these devices, which make them hot targets for hackers and thieves. To protect private information, such devices typically lock themselves after a few minutes of inactivity and prompt a password/PIN/pattern screen when reactivated. Passwords/ PINs/patterns based schemes are inherently vulnerable to shoulder surfing attacks and smudge attacks. In this paper, we propose BEAT, an authentication scheme for touch screen devices that authenticates users based on their behavior of performing certain actions on the touch screens. An action is either a gesture, which is a brief interaction of a user's fingers with the touch screen such as swipe rightwards, or a signature, which is the conventional unique handwritten depiction of one's name. Unlike existing authentication schemes for touch screen devices, which use what user inputs as the authentication secret, BEAT authenticates users mainly based on howthey input, using distinguishing features such as velocity, device acceleration, and stroke time. Even if attackers see what action a user performs, they cannot reproduce the behavior of the user doing those actions through shoulder surfing or smudge attacks. We implemented BEATon Samsung Focus smart phones and Samsung Slate tablets running Windows, collected 15,009 gesture samples and 10,054 signature samples, and conducted real-time experiments to evaluate its performance. Experimental results show that, with only 25 training samples, for gestures, BEATachieves an average equal error rate of 0.5 percent with three gestures and for signatures, it achieves an average equal error rate of 0.52 percent with single signature.

Massive open online courses and other forms of remote education continue to increase in popularity and reach. The ability to efficiently proctor remote online examinations is an important limiting factor to the scalability of this next stage in education. Presently, human proctoring is the most common approach of evaluation, by either requiring the test taker to visit an examination center, or by monitoring them visually and acoustically during exams via a webcam. However, such methods are labor intensive and costly. In this paper, we present a multimedia analytics system that performs automatic online exam proctoring. The system hardware includes one webcam, one wearcam, and a microphone for the purpose of monitoring the visual and acoustic environment of the testing location. The system includes six basic components that continuously estimate the key behavior cues: user verification, text detection, voice detection, active window detection, gaze estimation, and phone detection. By combining the continuous estimation components, and applying a temporal sliding window, we design higher level features to classify whether the test taker is cheating at any moment during the exam. To evaluate our proposed system, we collect multimedia (audio and visual) data from $\text{24}$ subjects performing various types of cheating while taking online exams. Extensive experimental results demonstrate the accuracy, robustness, and efficiency of our online exam proctoring system.

Providing high end-to-end (E2E) performance experienced by users is critical for cellular service providers to best serve their customers. This paper focuses on the detection and localization of E2E performance degradation (such as slow webpage page loading and unsmooth video playing) at cellular service providers. Detecting and localizing E2E performance degradation is crucial for cellular service providers, content providers, device manufactures, and application developers to jointly troubleshoot root causes. To the best of our knowledge, the detection and localization of E2E performance degradation at cellular service providers has not been previously studied. In this paper, we propose a holistic approach to detecting and localizing E2E performance degradation at cellular service providers across the four dimensions of user locations, content providers, device types, and application types. Our approach consists of three steps: modeling, detection, and localization. First, we use training data to build models that can capture the normal performance of every E2E instance, which means the flows corresponding to a specific location, content provider, device type, and application type. Second, we use our models to detect performance degradation for each E2E instance on an hourly basis. Third, after each E2E instance has been labeled as non-degrading or degrading, we use association rule mining techniques to localize the source of performance degradation. Our system detected performance degradation instances over a period of one week. In 80% of the detected degraded instances, content providers, device types, and application types were the only factors of performance degradation.

As battery-powered mobile devices become more popular and energy hungry, wireless power transfer technology, which allows the power to be transferred from a charger to ambient devices wirelessly, receives intensive interests. Existing schemes mainly focus on the power transfer efficiency but overlook the health impairments caused by RF exposure. In this paper, we study the safe charging problem (SCP) of scheduling power chargers so that more energy can be received while no location in the field has electromagnetic radiation (EMR) exceeding a given threshold Rt. We show that SCP is NP-hard and propose a solution, which provably outperforms the optimal solution to SCP with a relaxed EMR threshold (1-ε)Rt. Testbed results based on 8 Powercast TX91501 chargers validate our results. Extensive simulation results show that the gap between our solution and the optimal one is only 6.7% when ε = 0.1, while a naive greedy algorithm is 34.6% below our solution.

Privacy and integrity have been the main road block to the applications of two-tiered sensor networks. The storage nodes, which act as a middle tier between the sensors and the sink, could be compromised and allow attackers to learn sensitive data and manipulate query results. Prior schemes on secure query processing are weak, because they reveal non-negligible information, and therefore, attackers can statistically estimate the data values using domain knowledge and the history of query results. In this paper, we propose the first top-k query processing scheme that protects the privacy of sensor data and the integrity of query results. To preserve privacy, we build an index for each sensor collected data item using pseudo-random hash function and Bloom filters and transform top-k queries into top-range queries. To preserve integrity, we propose a data partition algorithm to partition each data item into an interval and attach the partition information with the data. The attached information ensures that the sink can verify the integrity of query results. We formally prove that our scheme is secure under IND-CKA security model. Our experimental results on real-life data show that our approach is accurate and practical for large network sizes.

For categorized RFID systems, this paper studies the practically important problem of top-k queries, which is to find the top-k smallest and (or) the top-k largest categories, as well as the sizes of such categories. In this paper, we propose a Top-k Query (TKQ) protocol and two supplementary techniques called segmented perfect hashing (SPH) and switching to framed slotted aloha (STA) for optimizing TKQ. First, TKQ lets each tag choose a time slot to respond to the reader with a single-one geometric string using the ON-OFF Keying modulation. TKQ leverages the length of continuous leading 1 s in the combined signal to estimate the corresponding category size. TKQ can quickly eliminate most categories whose sizes are significantly different from the top-k boundary, and only needs to perform accurate estimation on a limited number of categories that may be within the top-k set. We conduct rigorous analysis to guarantee the predefined accuracy constraints on the query results. Second, to alleviate the low frame utilization of TKQ, we propose the SPH scheme, which improves its average frame utilization from 36.8% to nearly 100% by establishing a bijective mapping between tag categories and slots. To minimize the overall time cost, we optimize the key parameter that trades off between communication cost and computation cost. Third, we observed from the simulation traces that TKQ+SPH pays most execution time on querying a small number of remaining categories whose sizes are close to the top-k boundary, which sometimes even exceeds the time cost for precisely identifying these remaining tags. Motivated by this observation, we propose the STA scheme to dynamically determine when we should terminate TKQ+SPH and switch to use FSA to finish the rest of top-k query. Experimental results show that TKQ+SPH+STA not only achieves the required accuracy constraints, but also achieves several times faster speed than the existing protocols.

This paper concerns the practically important problem of multi-category radio frequency identification (RFID) estimation: given a set of RFID tags, we want to quickly and accurately estimate the number of tags in each category. However, almost all the existing RFID estimation protocols are dedicated to the estimation problem on a single set, regardless of tag categories. A feasible solution is to separately execute the existing estimation protocols on each category. The execution time of such a serial solution is proportional to the number of categories, and cannot satisfy the delay-stringent application scenarios. Simultaneous RIFD estimation over multiple categories is desirable, and hence, this paper proposes an approach called simultaneous estimation for multi-category RFID systems (SEM). SEM exploits the Manchester-coding mechanism, which is supported by the ISO 18000-6 RFID standard, to decode the combined signals, thereby simultaneously obtaining the reply status of tags from each category. As a result, multiple bit vectors are decoded from just one physical slotted frame. Built on our SEM, many existing excellent estimation protocols can be used to estimate the tag cardinality of each category in a simultaneous manner. To ensure the predefined accuracy, we calculate the variance of the estimate in one round, as well as the variance of the average estimate in multiple rounds. To find the optimal frame size, we propose an efficient binary search-based algorithm. To address significant variance in category sizes, we propose an adaptive partitioning (AP) strategy to group categories of similar sizes together and execute the estimation protocol for each group separately. Compared with the existing protocols, our approach is much faster, meanwhile satisfying the predefined estimation accuracy. For example, with 20 categories, the proposed SEM+AP is about seven times faster than prior estimation schemes. Moreover, our approach is the only one whose normalized estimation time (i.e., time per category) decreases as the number of categories increases.

With the increasing popularization of radio frequency identification (RFID) technology in the retail and logistics industry, RFID privacy concern has attracted much attention, because a tag responds to queries from readers no matter they are authorized or not. An effective solution is to use a commercially available blocker tag that behaves as if a set of tags with known blocking IDs are present. However, the use of blocker tags makes the classical RFID estimation problem much more challenging, as some genuine tag IDs are covered by the blocker tag and some are not. In this paper, we propose RFID estimation scheme with blocker tags (REB), the first RFID estimation scheme with the presence of blocker tags. REB uses the framed slotted Aloha protocol specified in the EPC C1G2 standard. For each round of the Aloha protocol, REB first executes the protocol on the genuine tags and the blocker tag, and then virtually executes the protocol on the known blocking IDs using the same Aloha protocol parameters. REB conducts statistical inference from the two sets of responses and estimates the number of genuine tags. Rigorous theoretical analysis of parameter settings is proposed to guarantee the required estimation accuracy, meanwhile minimizing the time cost and energy cost of REB. We also reveal a fundamental tradeoff between the time cost and energy cost of REB, which can be flexibly adjusted by the users according to the practical requirements. Extensive experimental results reveal that REB significantly outperforms the state-of-the-art identification protocols in terms of both time efficiency and energy efficiency.

Several data center transport protocols have been proposed in recent years (e.g., DCTCP, PDQ, and pFabric). In this paper, we first identify the underlying strategies used by the existing data center transports, namely, in-network Prioritization (used in pFabric), Arbitration (used in PDQ), and Self-adjusting at Endpoints (PASE) (used in DCTCP). We show that these strategies are complimentary to each other, rather than substitutes, as they have different strengths and can address each other's limitations. Unfortunately, prior data center transports use only one of these strategies. As a result, they either achieve near-optimal performance or deployment friendliness (i.e., require no changes to the data plane) but not both. Based on this insight, we design a data center transport protocol called PASE, which carefully synthesizes these strategies by assigning different transport responsibilities to each strategy. The key advantage of PASE over prior art is that it achieves both near-optimal performance as well as deployment friendliness. PASE does not require any changes in network switches (hardware or software); yet, it achieves comparable, or even better, performance than the state-of-the-art protocols (such as pFabric) that require changes to network elements. Our evaluation results show that the PASE performs well for a wide range of application workloads and network settings.

Many object localization applications need the relative locations of a set of objects as oppose to their absolute locations. Although many schemes for object localization using radio frequency identification (RFID) tags have been proposed, they mostly focus on absolute object localization and are not suitable for relative object localization because of large error margins and the special hardware that they require. In this paper, we propose an approach called spatial-temporal phase profiling (STPP) to RFID-based relative object localization. The basic idea of STPP is that by moving a reader over a set of tags during which the reader continuously interrogating the tags, for each tag, the reader obtains a sequence of RF phase values, which we call a phase profile, from the tag's responses over time. By analyzing the spatial-temporal dynamics in the phase profiles, STPP can calculate the spatial ordering among the tags. In comparison with prior absolute object localization schemes, STPP requires neither dedicated infrastructure nor special hardware. We implemented STPP and evaluated its performance in two real-world applications: locating misplaced books in a library and determining the baggage order in an airport. The experimental results show that STPP achieves about 84% ordering accuracy for misplaced books and 95% ordering accuracy for baggage handling. We further leverage the controllable reader antenna and upgrade STPP to infer the spacing between each pair of tags. The result shows that STPP could achieve promising performance on distance ranging.

Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.

Network Function Virtualization (NFV) is a promising technology that promises to significantly reduce the operational costs of network services by deploying virtualized network functions (VNFs) to commodity servers in place of dedicated hardware middleboxes. The VNFs are typically running on virtual machine instances in a cloud infrastructure, where the virtualization technology enables dynamic provisioning of VNF instances, to process the fluctuating traffic that needs to go through the network functions in a network service. In this paper, we target dynamic provisioning of enterprise network services - expressed as one or multiple service chains - in cloud datacenters, and design efficient online algorithms without requiring any information on future traffic rates. The key is to decide the number of instances of each VNF type to provision at each time, taking into consideration the server resource capacities and traffic rates between adjacent VNFs in a service chain. In the case of a single service chain, we discover an elegant structure of the problem and design an efficient randomized algorithm achieving a e/(e-1) competitive ratio. For multiple concurrent service chains, an online heuristic algorithm is proposed, which is O(1)-competitive. We demonstrate the effectiveness of our algorithms using solid theoretical analysis and trace-driven simulations.

Taxi services play an important role in the public transportation system of large cities. Improving taxi business efficiency is an important societal problem since it could improve the income of the drivers and reduce gas emissions and fuel consumption. The recent research on seeking strategies may not be optimal for the overall revenue over an extended period of time as they ignored the important impact of passengers' destinations on future passenger seeking. To address these issues, this paper investigates how to increase the revenue efficiency (revenue per unit time) of taxi drivers, and models the passenger seeking process as a Markov Decision Process (MDP). For each one-hour time slot, we learn a different set of parameters for the MDP from data and find the best move for a vacant taxi to maximize the total revenue in that time slot. A case study and several experimental evaluations on a real dataset from a major city in China show that our proposed approach improves the revenue efficiency of inexperienced drivers by up to 15% and outperforms a baseline method in all the time slots.

To improve the performance of data-intensive applications, existing datacenter schedulers optimize either the placement of tasks or the scheduling of network flows. The task scheduler strives to place tasks close to their input data (i.e., maximize data locality) to minimize network traffic, while assuming fair sharing of the network. The network scheduler strives to finish flows as quickly as possible based on their sources and destinations determined by the task scheduler, while the scheduling is based on flow properties (e.g., size, deadline, and correlation) and not bound to fair sharing. Inconsistent assumptions of the two schedulers can compromise the overall application performance. In this paper, we propose NEAT, a task scheduling framework that leverages information from the underlying network scheduler to make task placement decisions. The core of NEAT is a task completion time predictor that estimates the completion time of a task under given network condition and a given network scheduling policy. NEAT leverages the predicted task completion times to minimize the average completion time of active tasks. Evaluation using ns2 simulations and real-testbed shows that NEAT improves application performance by up to 3.7x for the suboptimal network scheduling policies and up to 30% for the optimal network scheduling policy.

Given a spatial field and the traffic flow between neighboring locations, the early detection of gathering events (edge) problem aims to discover and localize a set of most likely gathering events. It is important for city planners to identify emerging gathering events which might cause public safety or sustainability concerns. However, it is challenging to solve the edge problem due to numerous candidate gathering footprints in a spatial field and the non-trivial task to balance pattern quality and computational efficiency. Prior solutions to model the edge problem lack the ability to describe the dynamic flow of traffic and the potential gathering destinations because they rely on static or undirected footprints. In contrast, in this paper, we model the footprint of a gathering event as a Gathering directed acyclic Graph (G-Graph), where the root of the G-Graph is the potential destination and the directed edges represent the most likely paths traffic takes to move towards the destination. We also proposed an efficient algorithm called SmartEdge to discover the most likely non-overlapping G-Graphs in the given spatial field. Our analysis shows that the proposed G-Graph model and the SmartEdge algorithm have the ability to efficiently and effectively capture important gathering events from real-world human mobility data. Our experimental evaluations show that SmartEdge saves 50% computation time over the baseline algorithm.

In this paper, we propose WifiU, which uses commercial WiFi devices to capture fine-grained gait patterns to recognize humans. The intuition is that due to the differences in gaits of different people, the WiFi signal reflected by a walking human generates unique variations in the Channel State Information (CSI) on the WiFi receiver. To profile human movement using CSI, we use signal processing techniques to generate spectrograms from CSI measurements so that the resulting spectrograms are similar to those generated by specifically designed Doppler radars. To extract features from spectrograms that best characterize the walking pattern, we perform autocorrelation on the torso reflection to remove imperfection in spectrograms. We evaluated WifiU on a dataset with 2,800 gait instances collected from 50 human subjects walking in a room with an area of 50 square meters. Experimental results show that WifiU achieves top-1, top-2, and top-3 recognition accuracies of 79.28%, 89.52%, and 93.05%, respectively.

The popular uprisings in a number of countries in the Middle East and North Africa in the Spring of 2011 were broadcasted live and enabled by local populations' access to social networking services such as Twitter and Facebook. The goal of this paper is to study the flow characteristics of the information flow of these broadcasts on Twitter. We have used language independent features of Twitter traffic to identify differences in information flows on Twitter mentioning countries experiencing some form of unrest, compared to traffic mentioning countries with peaceful political situations. We used these features to identify countries with political unstable situation. For empirical analysis, we collected several data sets of countries that were experiencing political unrest, as well as a set of countries in a control group that were not subject to such socio-political condition. Several different methods are used to model the flow of information between Twitter users in data sets as graphs, called information cascades. By using the dynamic properties of information cascades, naïve Bayes and SVM classifiers both achieve true positives rates of 100%, with false positives rates of 3% and 0%, respectively.

Online social network graphs provide useful insights on various social phenomena such as information dissemination and epidemiology. Unfortunately, social network providers often refuse to publish their social network graphs due to privacy concerns. Recently, differential privacy has become the widely accepted criteria for privacy preserving data publishing because it provides strongest privacy guarantees for publishing sensitive datasets. Although some work has been done on publishing matrices with differential privacy, they are computationally unpractical as they are not designed to handle large matrices such as the adjacency matrices of OSN graphs. In this paper, we propose a random matrix approach to OSN graph publishing, which achieves storage and computational efficiency by reducing the dimensions of adjacency matrices and achieves differential privacy by adding a small amount of noise. Our key idea is to first project each row of an adjacency matrix into a low dimensional space using random projection, and then perturb the projected matrix with random noise, and finally publish the perturbed and projected matrix. In this paper, we first prove that random projection plus random perturbation preserve differential privacy, and also that the random noise required to achieve differential privacy is small. We then validate the proposed approach and evaluate the utility of the published data for two different applications, namely node clustering and node ranking, using publicly available OSN graphs of Facebook, Live Journal, and Pokec.

Adult (or pornographic) websites attract a large number of visitors and account for a substantial fraction of the global Internet traffic. However, little is known about the makeup and characteristics of online adult traffic. In this paper, we present the first large-scale measurement study of online adult traffic using HTTP logs collected from a major commercial content delivery network. Our data set contains approximately 323 terabytes worth of traffic from 80 million users, and includes traffic from several dozen major adult websites and their users in four different continents. We analyze several characteristics of online adult traffic including content and traffic composition, device type composition, temporal dynamics, content popularity, content injection, and user engagement. Our analysis reveals several unique characteristics of online adult traffic. We also analyze implications of our findings on adult content delivery. Our findings suggest several content delivery and cache performance optimizations for adult traffic, e.g., modifications to website design, content delivery, cache placement strategies, and cache storage configurations.

Regular expressions are a very common tool for network security applications because they can match precisely and maintain high matching speed even for many simultaneous patterns. Their core feature is efficient representation as an automaton, where much of the interaction between patterns can be pre-computed and aggregated. Many algorithms have been devised to try and improve this pre-computation to not take exponential space while keeping high performance, but none has met all the requirements of fast, automated construction, small memory image, and high matching speed. We present Match Filtering, a technique for de-composing regular expressions into segments that can be matched independently, while a stateful post-processing engine filters these matches to eliminate those that do not correspond to matches of the original regular expression. Using standard CPU instructions, the post-processing engine can more efficiently represent constructs that would require a multiplicative increase in automaton states. Because the pre-processing is simple, automaton construction can be automated and fast, and because most on-line processing is done by a DFA, its matching speed is close to that of a DFA alone. We demonstrate experimentally 30× smaller, fast (seconds, not minutes) automaton construction and 43% faster matching speeds than state-of-the-art software algorithms.

Content Distribution Networks (CDNs) maintain multiple transit routes from content distribution servers to eyeball ISP networks which provide Internet connectivity to end users. Due to the dynamics of varying performance and pricing on transit routes, CDNs need to implement a transit route selection strategy to optimize performance and cost tradeoffs. In this paper, we formalize the transit routing problem using a multi-attribute objective function to simultaneously optimize end-to-end performance and cost. Our approach allows CDNs to navigate the cost and performance tradeoff in transit routing through a single control knob. We evaluate our approach using real-world measurements from CDN servers located at 19 geographically distributed IXPs. Using our approach, CDNs can reduce transit costs on average by 57% without sacrificing performance.

Powerline communication (PLC) provides inexpensive, secure and high speed network connectivity, by leveraging the existing power distribution networks inside the buildings. While PLC technology has the potential to improve connectivity and is considered a key enabler for sensing, control, and automation applications in enterprises, it has been mainly deployed for improving connectivity in homes. Deploying PLCs in enterprises is more challenging since the power distribution network is more complex as compared to homes. Moreover, existing PLC technologies such as HomePlug AV have not been designed for and evaluated in enterprise deployments. To this end, we give guidlines for designing PLC networks for providing ubiquitous connectivity in enterprises, based on measurement study of PLC performance in enterprise settings using commodity HomePlug AV PLC devices. Based on our findings, we propose that careful planning of PLC network topology, routing and spectrum sharing can significantly boost performance of enterprise PLC networks.

Fast growing communication networks like wireless ad-hoc networks and Internet-of-things (IoT) put forth new challenges in secure communication like eavesdropping and tampering attacks. For such networks, we consider the following important problem: How to establish a shared secret group key among the nodes of a dynamically formed ad-hoc group? There are two major challenges: (a) The nodes are constrained and cannot support expensive public-key operations, especially for large groups and (b) the neighborhood of an ad-hoc node is not determined a-priori and therefore, the node needs to be able to establish a group key with any dynamic sub-set of the nodes. In this work, we describe a novel template based approach to group key establishment wherein our template is a logical shared secret distribution hierarchy built on the ad-hoc nodes prior to deployment. Our template approach ensures that any given ad-hoc node shares a distinct set of secrets with any dynamic group of nodes, regardless of the physical neighborhood, after deployment. We illustrate our approach using two instantiations of symmetric secret distribution protocols namely: sub-set and dual one-way hash chain distributions.

Wireless Power Transfer (WPT) has received more and more attentions because of its convenience and reliability. In this paper, we first propose the notion of omnidirectional charging by which an area is omnidirectionally charged if a device with directional antennas at any position in the area with any orientation can be charged by directional chargers with power being no smaller than a given threshold. We present our empirical charging model based on field experimental results using off-the-shelf WPT products. Next, we consider the problem of detecting whether the target area achieves omnidirectional charging given a deterministic deployment of chargers. We develop piecewise constant approximation and area discretization techniques to partition the target area into subareas and approximate powers from chargers as constants. Then we propose the Minimum Coverage Set extraction technique which reduces the continuous search space to a discrete one and thereby allows a fast detection algorithm. Moreover, we consider the problem of determining the probability that the target area achieves omnidirectional charging given a random deployment of chargers. We first replace the target area by grid points on triangular lattices to reduce the search space from infinite to finite, then approximate chargers' power with reasonable relaxation, and derive an upper bound of the omnidirectional charging probability. Finally, we conduct both simulation and field experiments, and the results show that our algorithm outperforms comparison algorithms by at least 120%, and the consistency degree of our theoretical results and field experimental results is larger than 93.6%.

We propose OpenFunction, an extensible data plane abstraction protocol for platform-independent software-defined middleboxes. The main challenge is how to abstract packet operations, flow states and event generations with elements. The key decision of OpenFunction is: actions/states/events operations should be defined in a uniform pattern and independent from each other. We implemented a working SDM system including one OpenFunction controller and OpenFunction boxes based on Netmap, DPDK and FPGA to verify OpenFunction abstraction.

For a datacenter running a data-parallel analytic framework, minimizing job completion time (JCT) is crucial for application performance. The key observation is that JCT could be improved, if network scheduling can exploit the opportunity of decreasing the amount of occupied machine slot-time spend on communication. We propose Macroflow, a networking abstraction that captures the primitive resource granularity of data-parallel frameworks. We study the inter-macroflow scheduling problem for decreasing application JCT. We propose the Smallest-Macroflow-First (SMF) and Smallest-Average-Macroflow-First (SAMF) heuristics that greedily schedule macroflows based on their network footprint. Trace-driven simulations demonstrate that our algorithms can reduce the average and tail JCT of network-intensive jobs by up to 20% and 25%, respectively; at the same time, the throughput of computation-intensive jobs is increased by up to 2.2×.

Fitting large and ever increasing routing tables in small on-chip memory is just like fitting an elephant in a box, which has been considered as impossible. In this paper, we propose the data structure of two-Dimensional Division Bloom Filter (D2BF) that can compactly encode almost all the needed information for performing IP lookup from a FIB in small on-chip memory. With pipelining, we further achieve the throughput of one packet per on-chip memory access.

OpenFlow packet classification needs to satisfy two requirements: high speed and fast updates. Although packet classification is a well-studied problem, no existing solution satisfies both requirements. Decision tree methods, such as HyperCuts, EffiCuts, and SmartSplit can achieve high-speed packet classification but not fast updates. The Tuple Space Search (TSS) algorithm used in Open vSwitch achieves fast updates but not high-speed packet classification. In this paper, we propose a hybrid approach, PartitionSort, that combines the benefits of both TSS and decision trees achieving both high-speed packet classification and fast updates. A key to PartitionSort is a novel notion of ruleset sortability that provides two key benefits. First, it results in far fewer partitions than TSS. Second, it allows the use of Multi-dimensional Interval Trees to achieve logarithmic classification and update time for each sortable ruleset partition. Our extensive experimental results show that PartitionSort is an order of magnitude faster than TSS in classifying packets while achieving comparable update time. PartitionSort is a few orders of magnitude faster in construction time than SmartSplit, a state-of-the-art decision tree classifier, while maintaining competitive classification time. Finally, PartitionSort is scalable to an arbitrary number of fields.

Providing high end-to-end (E2E) performance is critical for cellular service providers to best serve their customers. Detecting and localizing E2E performance degradation is crucial for cellular service providers, content providers, device manufactures, and application developers to jointly troubleshoot root causes. To the best of our knowledge, detection and localization of E2E performance degradation at cellular service providers has not been previously studied. In this paper, we propose a holistic approach to detecting and localizing E2E performance degradation at cellular service providers across the four dimensions of user locations, content providers, device types, and application types. First, we use training data to build models that can capture the normal performance of every E2E-instance, which means flows corresponding to a specific location, content provider, device type, and application type. Second, we use our models to detect performance degradation for each E2E-instance on an hourly basis. Third, after each E2E-instance has been labeled as non-degrading or degrading, we use association rule mining techniques to localize the source of performance degradation. Our system detected performance degradation instances over a period of one week. In 80% of the detected degraded instances, content providers, device types, and application types were the only factors of performance degradation.

Wireless Power Transfer has become a commercially viable technology to charge devices because of the convenience of no power wiring and the reliability of continuous power supply. This paper concerns the fundamental issue of wireless charger placement with electromagnetic radiation (EMR) safety. Although there are a few wireless charging schemes consider EMR safety, none of them addresses the charger placement issue. In this paper, we propose PESA, a wireless charger Placement scheme that guarantees EMR SAfety for every location on the plane. First, we discretize the whole charging area and formulate the problem into the Multidimensional 0/1 Knapsack (MDK) problem. Second, we propose a fast approximation algorithm to the MDK problem. Third, we optimize our scheme to improve speed by double partitioning the area. We prove that the output of our algorithm is better than (1 - ϵ) of the optimal solution to PESA with a smaller EMR threshold (1 - ϵ/2)Rt and a larger EMR coverage radius (1 + ϵ/2)D. We conducted both simulations and field experiments to evaluate the performance of our scheme. Our experimental results show that in terms of charging utility, our algorithm outperforms the prior art by up to 45.7%.

This paper studies the practically important problem of top-k queries, which is to find the top k largest categories and their corresponding sizes. In this paper, we propose a Top-k Query (TKQ) protocol and a technique that we call Segmented Perfect Hashing (SPH) for optimizing TKQ. Specifically, TKQ is based on the framed slotted Aloha protocol. Each tag responds to the reader with a Single-One Geometric (SOG) string using the ON-OFF Keying modulation. TKQ leverages the length of continuous leading 1s in the combined signal to estimate the corresponding category size. TKQ can quickly eliminate the sufficiently small categories, and only needs to focus on a limited number of large-size categories that require more accurate estimation. We conduct rigorous analysis to guarantee the predefined accuracy constraints. To further improve time-efficiency, we propose the SPH scheme, which improves the average frame utilization of TKQ from 36.8% to nearly 100% by establishing a bijective mapping between tag categories and slots. To minimize the overall time cost, we optimize the key parameter that trades off between communication cost and computation cost. Experimental results show that our TKQ+SPH protocol not only achieves the required accuracy constraints, but also achieves a 2.6~7x faster speed than the existing protocols.

Content Delivery Networks (CDNs) have emerged as a dominant mechanism to deliver content over the Internet. Despite their importance, to our best knowledge, large-scale analysis of CDN cache performance is lacking in prior literature. A CDN serves many content publishers simultaneously and thus has unique workload characteristics; it typically deals with extremely large content volume and high content diversity from multiple content publishers. CDNs also have unique performance metrics; other than hit ratio, CDNs also need to minimize network and disk load on cache servers. In this paper, we present measurement and analysis of caching workload at a large commercial CDN. Using detailed logs from four geographically distributed CDN cache servers, we analyze over 600 million content requests accounting for more than 1.3 petabytes worth of traffic. We analyze CDN workload from a wide range of perspectives, including request composition, size, popularity, and temporal dynamics. Using real-world logs, we also evaluate cache replacement algorithms, including two enhancements designed based on our CDN workload analysis: N-hit and content-aware caching. The results show that these enhancements achieve substantial performance gains in terms of cache hit ratio, disk load, and origin traffic volume.

Device-free gesture tracking is an enabling HCI mechanism for small wearable devices because fingers are too big to control the GUI elements on such small screens, and it is also an important HCI mechanism for medium-to-large size mobile devices because it allows users to provide input without blocking screen view. In this paper, we propose LLAP, a device-free gesture tracking scheme that can be deployed on existing mobile devices as software, without any hardware modification. We use speakers and microphones that already exist on most mobile devices to perform device-free tracking of a hand/finger. The key idea is to use acoustic phase to get fine-grained movement direction and movement distance measurements. LLAP first extracts the sound signal reflected by the moving hand/finger after removing the background sound signals that are relatively consistent over time. LLAP then measures the phase changes of the sound signals caused by hand/finger movements and then converts the phase changes into the distance of the movement. We implemented and evaluated LLAP using commercial-off-the-shelf mobile phones. For 1-D hand movement and 2-D drawing in the air, LLAP has a tracking accuracy of 3.5 mm and 4.6 mm, respectively. Using gesture traces tracked by LLAP, we can recognize the characters and short words drawn in the air with an accuracy of 92.3% and 91.2%, respectively.

In this demo, we present LLAP, a hand tracking system that uses ultrasound to localize the hand of the user to enable device-free gesture inputs. LLAP utilizes speakers and microphones on Commercial-Off-The-Shelf (COTS) mobile devices to play and record sound waves that are inaudible to humans. By measuring the phase of the sound signal reflected by the hands or fingers of the user, we can accurately measure the gesture movements. With a single pair of speaker/microphone, LLAP can track hand movement with accuracy of 3.5 mm. For devices with two microphones, LLAP enables drawing-in-the air capability with tracking accuracy of 4.6 mm. Moreover, the latency for LLAP is smaller than 15 ms for both the Android and the iOS platforms so that LLAP can be used for real-time applications.

This paper is on designing a compact data structure for multi-set membership testing allowing fast set querying. Multi-set membership testing is a fundamental operation for computing systems and networking applications. Most existing schemes for multi-set membership testing are built upon Bloom filter, and fall short in either storage space cost or query speed. To address this issue, in this paper we propose Noisy Bloom Filter (NBF) and Error Corrected Noisy Bloom Filter (NBF-E) for multi-set membership testing. For theoretical analysis, we optimize their classification failure rate and false positive rate, and present criteria for selection between NBF and NBF-E. The key novelty of NBF and NBF-E is to store set ID information in a compact but noisy way that allows fast recording and querying, and use denoising method for querying. Especially, NBF-E incorporates asymmetric error-correcting coding technique into NBF to enhance the resilience of query results to noise by revealing and leveraging the asymmetric error nature of query results. To evaluate NBF and NBF-E in comparison with prior art, we conducted experiments using real-world network traces. The results show that NBF and NBF-E significantly advance the state-of-the-art on multi-set membership testing.

Frequent item mining, which deals with finding items that occur frequently in a given data stream over a period of time, is one of the heavily studied problems in data stream mining. A generalized version of frequent item mining is the persistent item mining, where a persistent item, unlike a frequent item, does not necessarily occur more frequently compared to other items over a short period of time, rather persists and occurs more frequently over a long period of time. To the best of our knowledge, there is no prior work on mining persistent items in a data stream. In this paper, we address the fundamental problem of finding persistent items in a given data stream during a given period of time at any given observation point. We propose a novel scheme, PIE, that can accurately identify each persistent item with a probability greater than any desired false negative rate (FNR) while using a very small amount of memory. The key idea of PIE is that it uses Raptor codes to encode the ID of each item that appears at the observation point during a measurement period and stores only a few bits of the encoded ID in the memory of that observation point during that measurement period. The item that is persistent occurs in enough measurement periods that enough encoded bits for the ID can be retrieved from the observation point to decode them correctly and get the ID of the persistent item. We implemented and extensively evaluated PIE using three real network traffic traces and compared its performance with two prior adapted schemes. Our results show that not only PIE achieves the desired FNR in every scenario, its FNR, on average, is 19.5 times smaller than the FNR of the best adapted prior art.

Set queries are fundamental operations in computer systems and applications. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a Shifting Bloom Filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF based set data structures allocate additional memory to store auxiliary information. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.

Presents the introductory editorial for this issue of the publication.

Access control lists (ACLs) are the core of many networking and security devices. As new threats and vulnerabilities emerge, ACLs on routers and firewalls are getting larger. Therefore, compressing ACLs is an important problem. In this paper, we propose a new approach, called Diplomat, to ACL compression. The key idea is to transform higher dimensional target patterns into lower dimensional patterns by dividing the original pattern into a series of hyperplanes and then resolving differences between two adjacent hyperplanes by adding rules that specify the differences. This approach is fundamentally different from prior ACL compression algorithms and is shown to be very effective. We implemented Diplomat and conducted side-by-side comparison with the prior Firewall Compressor, TCAM Razor, and ACL Compressor algorithms on real life classifiers. Our experimental results show that Diplomat outperforms all of them on most of our real-life classifiers, often by a considerable margin, particularly as classifier size and complexity increases. In particular, on our largest ACLs, Diplomat has an average improvement ratio of 34.9% over Firewall Compressor on range-ACLs, of 14.1% over TCAM Razor on prefix-ACLs, and 8.9% over ACL Compressor on mixed-ACLs.

Privacy has been the key road block to cloud computing as clouds may not be fully trusted. This paper is concerned with the problem of privacy-preserving range query processing on clouds. Prior schemes are weak in privacy protection as they cannot achieve index indistinguishability, and therefore allow the cloud to statistically estimate the values of data and queries using domain knowledge and history query results. In this paper, we propose the first range query processing scheme that achieves index indistinguishability under the indistinguishability against chosen keyword attack (IND-CKA). Our key idea is to organize indexing elements in a complete binary tree called PBtree, which satisfies structure indistinguishability (i.e., two sets of data items have the same PBtree structure if and only if the two sets have the same number of data items) and node indistinguishability (i.e., the values of PBtree nodes are completely random and have no statistical meaning). We prove that our scheme is secure under the widely adopted IND-CKA security model. We propose two algorithms, namely PBtree traversal width minimization and PBtree traversal depth minimization, to improve query processing efficiency. We prove that the worst-case complexity of our query processing algorithm using PBtree is O(|R|logn), where n is the total number of data items and R is the set of data items in the query result. We implemented and evaluated our scheme on a real-world dataset with 5 million items. For example, for a query whose results contain 10 data items, it takes only 0.17 ms.

Packet classification is the core mechanism that enables many networking devices. Although using ternary content addressable memory (TCAM) to perform high-speed packet classification has become the widely adopted solution, TCAM is very expensive, has limited capacity, consumes large amounts of power, and generates tremendous amounts of heat because of their extremely dense and parallel circuitry. In this paper, we propose the first packet classification scheme that uses binary CAM (BCAM). BCAM is similar to TCAM except that in BCAM, every bit has only two possible states: 0 or 1; in contrast, in TCAM, every bit has three possible states: 0, 1, or * (don't care). Because of the high complexity in implementing the extra “don't care” state, TCAM has much higher circuit density than BCAM. As the power consumption, heat generation, and price grow non-linearly with circuit density, BCAM consumes much less power, generates much less heat, and costs much less money than TCAM. Our BCAM-based packet classification scheme is built on two key ideas. First, we break a multi-dimensional lookup into a series of 1-D lookups. Second, for each 1-D lookup, we convert the ternary matching problem into a binary string exact matching problem. To speed up the lookup process, we propose a number of optimization techniques, including skip lists, free expansion, minimizing maximum lookup time, minimizing average lookup time, and lookup short circuiting. We evaluated our BCAM scheme on 17 real-life packet classifiers. On these classifiers, our BCAM scheme requires roughly five times fewer CAM bits than the traditional TCAM-based scheme. The penalty is a throughput that is roughly four times less.

Regular expression (RegEx) matching, the core operation of intrusion detection and prevention systems, remains a fundamentally challenging problem. A desired RegEx matching scheme should satisfy four requirements: deterministic finite state automata (DFA) speed, nondeterministic finite state automata (NFA) size, automated construction, and scalable construction. Despite lots of work on RegEx matching, no prior scheme satisfies all four of these requirements. In this paper, we approach this holy grail by proposing OverlayCAM, a RegEx matching scheme that satisfies all four requirements. The theoretical underpinning of our scheme is overlay delayed input DFA, a new automata model proposed in this paper that captures both state replication and transition replication, which are inherent in DFAs. Our RegEx matching solution processes one input character per lookup like a DFA, requires only the space of an NFA, is grounded in sound automata models, is easy to deploy in existing network devices, and comes with scalable and automated construction algorithms.

During crowded events, cellular networks face voice and data traffic volumes that are often orders of magnitude higher than what they face during routine days. Despite the use of portable base stations for temporarily increasing communication capacity and free Wi-Fi access points for offloading Internet traffic from cellular base stations, crowded events still present significant challenges for cellular network operators looking to reduce dropped call events and improve Internet speeds. For an effective cellular network design, management, and optimization, it is crucial to understand how cellular network performance degrades during crowded events, what causes this degradation, and how practical mitigation schemes would perform in real-life crowded events. This paper makes a first step toward this end by characterizing the operational performance of a tier-1 cellular network in the U.S. during two high-profile crowded events in 2012. We illustrate how the changes in population distribution, user behavior, and application workload during crowded events result in significant voice and data performance degradation, including more than two orders of magnitude increase in connection failures. Our findings suggest two mechanisms that can improve performance without resorting to costly infrastructure changes: radio resource allocation tuning and opportunistic connection sharing. Using trace-driven simulations, we show that more aggressive release of radio resources via 1–2 s shorter radio resource control timeouts as compared with routine days helps to achieve better tradeoff between wasted radio resources, energy consumption, and delay during crowded events, and opportunistic connection sharing can reduce connection failures by 95% when employed by a small number of devices in each cell sector.

With the growth in number and significance of the emerging applications that require extremely low latencies, network operators are facing increasing need to perform latency measurement on per-flow basis for network monitoring and troubleshooting. In this paper, we propose COLATE, the first per-flow latency measurement scheme that requires no probe packets and time stamping. Given a set of observation points, COLATE records packet timing information at each point so that later, for any two points, it can accurately estimate the average and the standard deviation of the latencies experienced by the packets of any flow in passing the two points. The key idea is that when recording packet timing information, COLATE purposely allows noise to be introduced for minimizing storage space, and when querying the latency of a target flow, COLATE uses statistical techniques to denoise and obtain an accurate latency estimate. COLATE is designed to be efficiently implementable on network middleboxes. In terms of processing overhead, COLATE performs only one hash and one memory update per packet. In terms of storage space, COLATE uses less than 0.1-b/packet, which means that, on a backbone link with half a million packets per second, using a 256-GB drive, COLATE can accumulate time stamps of packets traversing the link for over 1.5 years. We evaluated COLATE using three real traffic traces, namely, a backbone traffic trace, an enterprise network traffic trace, and a data center traffic trace. Results show that COLATE always achieves the required reliability for any given confidence interval.

Radio-frequency identification (RFID) systems have been deployed to detect and identify missing products by affixing them with cheap passive RFID tags and monitoring them with RFID readers. Existing missing tag detection and identification protocols require the tag population to contain only those tags whose IDs are already known to the reader. However, in reality, tag populations often contain tags with unknown IDs, called unexpected tags. These unexpected tags cause unexpected false positives, i.e., due to them, missing tags are detected as present. We take the first step toward addressing the problem of detecting and identifying missing tags from a population that contains unexpected tags. Our protocol, RUN, uses standardized frame slotted Aloha for communication between tags and readers. It executes multiple frames with different seeds to reduce the effects of unexpected false positives. At the same time, it minimizes the missing tag detection and identification time by first estimating the number of unexpected tags in the population and then using it along with the false-positive probability to obtain optimal frame sizes and minimum number of times Aloha frames should be executed to mitigate the effects of false positives. RUN works with multiple readers with overlapping regions. It is easy to deploy, because it is implemented on readers as a software module and does not require any modifications to tags or to the communication protocol between the tags and the readers. We implemented RUN along with four major missing tag detection and identification protocols, namely, TRP, IIP, MTI, and SFMTI, and the fastest tag ID collection protocol TH and compared them side by side. Our performance evaluation results show that RUN is the only protocol that achieves required reliability in the presence of unexpected tags, whereas the best existing protocol achieves a maximum reliability of only 67%. RUN identifies 100% of missing tags in the presence of unexpected tags, whereas the best existing protocol identifies a maximum of only 60% of missing tags.

In many countries, the Internet is under stringent censorship for political or religious reasons which severely undermines the free flow of information. A censorship-resistant web browsing system must be scalable, blocking resistant, and tracing resistant. However, current censorship-resistant web browsing systems, which use a group of dedicated proxies to bypass censorship, fail to meet these requirements. To tackle these challenges, we propose Freeweb, which relies on widely-distributed peer-to-peer (P2P) nodes in a decentralized manner rather than specified proxies in a centralized manner. We also proposed enhancement methods to reduce file access delay and avoid node overloads in Freeweb. Freeweb is built on top of a Distributed Hash Table (DHT)-based P2P network, where nodes not under censorship help nodes under censorship to access blocked webpages. Freeweb has a web browser front-end whose user interface resembles existing web browsers. The underlying complex process of retrieving blocked webpages is therefore hidden from users. We implemented an open-sourced Freeweb and conducted extensive real-world experiments on PlanetLab. The experimental results show that Freeweb has a high success rate and reasonable browsing latency, and its enhancement reduces much network load and file access latency, and avoids node overloads.

Cloud computing has become indispensable in providing highly reliable data services to users. But, there are major concerns about the privacy of the data stored on cloud servers. While encryption of data provides sufficient protection, it is challenging to support rich querying functionality, such as string matching, over the encrypted data. In this work, we present the first ever symmetric key based approach to support privacy preserving string matching in cloud computing. We describe an efficient and accurate indexing structure, the PASS tree, which can execute a string pattern query in logarithmic time complexity over a set of data items. The PASS tree provides strong privacy guarantees against attacks from a semi-honest adversary. We have comprehensively evaluated our scheme over large real-life data, such as Wikipedia and Enron documents, containing up to 100000 keywords, and show that our algorithms achieve pattern search in less than a few milliseconds with 100% accuracy. Furthermore, we also describe a relevance ranking algorithm to return the most relevant documents to the user based on the pattern query. Our ranking algorithm achieves 90%+ above precision in ranking the returned documents.

RFID systems with battery powered active tags are widely used in various applications such as supply chain management and object tracking. In RFID identification, tags transmit their IDs to readers over a shared wireless medium, thus, transmissions from tags often collide causing some tags to use their scarce energy resources to retransmit their IDs. Existing RFID identification protocols are unfair in the sense that some tags transmit more times compared to others and thus deplete their batteries faster. Locating tags with depleted batteries for replacement is troublesome. This paper addresses the fundamental problem of ensuring required fairness in the number of transmissions per tag while minimizing identification time in active RFID tag identification. We propose the first Fair RFID Identification Protocol (FRIP) that can achieve any required amount of fairness. The key idea behind FRIP is to bound the expected number of tags that transmit more than once by finding optimal frame sizes for the standardized frame slotted Aloha. We implemented and performed side-by-side comparisons of FRIP with all nine major existing RFID identification protocols. Our results show that FRIP can achieve arbitrarily high fairness. FRIP reduces the average number of transmissions per tag by at least 2.62 times compared to the best existing protocol. At the same time, it is faster than the existing protocols. FRIP is easy to deploy because it is compliant with the C1G2 standard, and thus, requires no modifications to tags or to the communication protocol between tags and readers. It only needs to be implemented on readers as a software module. FRIP works with multiple readers.

In this paper, we propose a system called R# to estimate the number of human objects using passive RFID tags but without attaching anything to human objects. The idea is based on our observation that the more human objects are present, the higher the variance in the RSS values of the tag backscattered RF signal. Thus, based on the received RF signal, the reader can estimate the number of human objects. R# includes an RFID reader and some (say 20) passive tags, which are deployed in the region that we want to monitor the number of human objects, such as the region in front of a painting. The RFID reader periodically emits RF signal to identify all tags and the tags simply respond with their IDs via C1G2 standard protocols. We implemented R# using commercial Impinj H47 passive RFID tags and Impinj reader model R420. We conducted experiments in a simulated picking aisle area of the supermarket environment. The experimental results show that R# can achieve high estimation accuracy (more than 90%).

The widely used RFID tags impose serious privacy concerns as a tag responds to queries from readers no matter they are authorized or not. The common solution is to use a commercially available blocker tag which behaves as if a set of tags with known blocking IDs are present. The use of blocker tags makes RFID estimation much more challenging as some genuine tag IDs are covered by the blocker tag and some are not. In this paper, we propose REB, the first RFID estimation scheme with the presence of blocker tags. REB uses the framed slotted Aloha protocol specified in the C1G2 standard. For each round of the Aloha protocol, REB first executes the protocol on the genuine tags and the blocker tag, and then virtually executes the protocol on the known blocking IDs using the same Aloha protocol parameters. The basic idea of REB is to conduct statistically inference from the two sets of responses and estimate the number of genuine tags. We conduct extensive simulations to evaluate the performance of REB, in terms of time-efficiency and estimation reliability. The experimental results reveal that our REB scheme runs tens of times faster than the fastest identification protocol with the same accuracy requirement.

RFID systems have been deployed to detect missing products by affixing them with cheap passive RFID tags and monitoring them with RFID readers. Existing missing tag detection protocols require the tag population to contain only those tags whose IDs are already known to the reader. However, in reality, tag populations often contain tags with unknown IDs, called unexpected tags, and cause unexpected false positives i.e., due to them, missing tags are detected as present. We take the first step towards addressing the problem of detecting the missing tags from a population that contains unexpected tags. Our protocol, RUN, mitigates the adverse effects of unexpected false positives by executing multiple frames with different seeds. It minimizes the missing tag detection time by first estimating the number of unexpected tags and then using it along with the false positive probability to obtain optimal frame sizes and number of times Aloha frames should be executed. RUN works with multiple readers with overlapping regions. It is easy to deploy because it is implemented on readers as a software module and does not require modifications to tags or to the communication protocol between tags and readers. We implemented RUN along with four major missing tag detection protocols and the fastest tag ID collection protocol and compared them side-by-side. Our experimental results show that RUN always achieves the required reliability whereas the best existing protocol achieves a maximum reliability of only 67%.

Keystroke privacy is critical for ensuring the security of computer systems and the privacy of human users as what being typed could be passwords or privacy sensitive information. In this paper, we show for the first time that WiFi signals can also be exploited to recognize keystrokes. The intuition is that while typing a certain key, the hands and fingers of a user move in a unique formation and direction and thus generate a unique pattern in the time-series of Channel State Information (CSI) values, which we call CSI-waveform for that key. In this paper, we propose a WiFi signal based keystroke recognition system called WiKey. WiKey consists of two Commercial Off-The-Shelf (COTS) WiFi devices, a sender (such as a router) and a receiver (such as a laptop). The sender continuously emits signals and the receiver continuously receives signals. When a human subject types on a keyboard, WiKey recognizes the typed keys based on how the CSI values at the WiFi signal receiver end. We implemented the WiKey system using a TP-Link TL-WR1043ND WiFi router and a Lenovo X200 laptop. WiKey achieves more than 97.5\% detection rate for detecting the keystroke and 96.4% recognition accuracy for classifying single keys. In real-world experiments, WiKey can recognize keystrokes in a continuously typed sentence with an accuracy of 93.5%.

Some pioneer WiFi signal based human activity recognition systems have been proposed. Their key limitation lies in the lack of a model that can quantitatively correlate CSI dynamics and human activities. In this paper, we propose CARM, a CSI based human Activity Recognition and Monitoring system. CARM has two theoretical underpinnings: a CSI-speed model, which quantifies the correlation between CSI value dynamics and human movement speeds, and a CSI-activity model, which quantifies the correlation between the movement speeds of different human body parts and a specific human activity. By these two models, we quantitatively build the correlation between CSI value dynamics and a specific human activity. CARM uses this correlation as the profiling mechanism and recognizes a given activity by matching it to the best-fit profile. We implemented CARM using commercial WiFi devices and evaluated it in several different environments. Our results show that CARM achieves an average accuracy of greater than 96%.

Nowadays mobile device (e.g., smartphone) users not only have a high expectation on the availability of the cellular data service, but also increasingly depend on the high end-to-end (E2E) performance of their applications. Since the E2E performance of individual application sessions may vary greatly, depending on factors such as the cellular network condition, the content provider, the type/model of the mobile devices, and the application software, detecting and localizing service performance degradations in a timely manner at large scale is of great value to cellular service providers. In this paper, we build a holistic measurement system that tracks session-level E2E performance metrics along with the service attributes for these factors. Using data collected from a major cellular service provider, we first model the expected E2E service performance with a regression based approach, detect performance degradation conditions based on the time series of fine-grained measurement data, and finally localize the service degradation using association-rule-mining techniques. Our deployment experience reveals that in 80% of the detected problem instances, performance degradation can be attributed to non-network-location specific factors, such as a common content provider, or a set of applications running on certain models of devices.

Radio Frequency Identification (RFID) technology has been widely used in inventory management in many scenarios, e.g., warehouses, retail stores, hospitals, etc. This paper investigates a challenging problem of complete identification of missing tags in large-scale RFID systems. Although this problem has attracted extensive attention from academy and industry, the existing work can hardly satisfy the stringent real-time requirements. In this paper, a Slot Filter-based Missing Tag Identification (SFMTI) protocol is proposed to reconcile some expected collision slots into singleton slots and filter out the expected empty slots as well as the unreconcilable collision slots, thereby achieving the improved time-efficiency. The theoretical analysis is conducted to minimize the execution time of the proposed SFMTI. We then propose a cost-effective method to extend SFMTI to the multi-reader scenarios. The extensive simulation experiments and performance results demonstrate that the proposed SFMTI protocol outperforms the most promising Iterative ID-free Protocol (IIP) by reducing nearly 45% of the required execution time, and is just within a factor of 1.18 from the lower bound of the minimum execution time.

Unknown RFID tags appear when the unread tagged objects are moved in or tagged objects are misplaced. This paper studies the practically important problem of unknown tag detection while taking both time-efficiency and energy-efficiency of battery-powered active tags into consideration. We first propose a Sampling Bloom Filter which generalizes the standard Bloom Filter. Using the new filtering technique, we propose the Sampling Bloom Filter-based Unknown tag Detection Protocol (SBF-UDP), whose detection accuracy is tunable by the end users. We present the theoretical analysis to minimize the time and energy costs. SBF-UDP can be tuned to either the time-saving mode or the energy-saving mode, according to the specific requirements. Extensive simulations are conducted to evaluate the performance of the proposed protocol. The experimental results show that SBF-UDP considerably outperforms the previous related protocols in terms of both time-efficiency and energy-efficiency. For example, when 3 or more unknown tags appear in the RFID system with 30000 known tags, the proposed SBF-UDP is able to successfully report the existence of unknown tags with a confidence more than 99%. While our protocol runs 9 times faster than the fastest existing scheme and reducing the energy consumption by more than 80%.

This paper presents a novel approach that transforms the feature space into a new feature space such that a range query in the original space is mapped into an equivalent box query in the transformed space. Since box queries are axis aligned, there are several implementational advantages that can be exploited to speed up the retrieval of query results using R-Tree [9] like indexing schemes. For two dimensional data, the transformation is precise. For larger than two dimensions, we propose a space transformation scheme based on disjoint planer rotation and a new type of query, pruning box query, to get the precise results. Experimental results with large synthetic databases and some real databases show the effectiveness of the proposed transformation scheme. These experimental results have been corroborated with suitable mathematical models. In disjoint planer rotation, additional computation time is required to remove the false positives produced due to the bounding box not being precise. A second topological transformation scheme is presented based on optimized bounding box, which reduces the amount of false positives. The amount of this reduction is more with increasing dimensions. Optimized bounding box for higher dimensions is computed based on a novel approach of simultaneous local optimal projections.

Significant geospatial and temporal correlations, in terms of traffic volume and application access, exist in cellular network usage as shown in recent studies on cellular network measurement. Such geospatial and temporal correlation patterns provide local optimization opportunities to cellular network operators for handling the explosive growth in the traffic volume observed in recent years. To the best of our knowledge, in this paper, we provide the first fine-grained joint characterization of the geospatial and temporal dynamics of application usage in a 3G cellular data network. Our analysis is based on two simultaneously collected traces from the radio access network (containing location records) and the core network (containing traffic records) of a tier-1 cellular network in the United States. To better understand the application usage in our data, we first cluster cell locations based on their application distributions and then study the geospatial and temporal dynamics of application usage across different geographical regions. The results of our measurement study present cellular network operators with fine-grained insights that can be leveraged to tune network parameter settings for better network performance and user experience.

Network reachability is an important characteristic for understanding end-to-end network behavior and helps in detecting violations of security policies across the network. While quantifying network reachability within one administrative domain is a difficult problem in itself, performing the same computation across a network spanning multiple administrative domains presents a novel challenge. The problem of quantifying network reachability across multiple administrative domains is more difficult because the privacy of security policies of individual domains is a serious concern and needs to be protected through this process. In this paper, we propose the first cross-domain privacy-preserving protocol for quantifying network reachability. Our protocol constructs equivalent representations of the Access Control List (ACL) rules and determines network reachability while preserving the privacy of the individual ACLs. This protocol can accurately determine the network reachability along a network path through different administrative domains. We have implemented and evaluated our protocol on both real and synthetic ACLs. The experimental results show that the online processing time of an ACL containing thousands of rules is less than 25 s. Given two ACLs, each containing thousands of rules, the comparison time is less than 6 s, and the total communication cost is less than 2100 kB.

Radio frequency identification (RFID) systems have been widely deployed for various applications such as object tracking, 3-D positioning, supply chain management, inventory control, and access control. This paper concerns the fundamental problem of estimating RFID tag population size, which is needed in many applications such as tag identification, warehouse monitoring, and privacy-sensitive RFID systems. In this paper, we propose a new scheme for estimating tag population size called Average Run-based Tag estimation (ART). The technique is based on the average run length of ones in the bit string received using the standardized framed slotted Aloha protocol. ART is significantly faster than prior schemes. For example, given a required confidence interval of 0.1% and a required reliability of 99.9%, ART is consistently 7 times faster than the fastest existing schemes (UPE and EZB) for any tag population size. Furthermore, ART's estimation time is provably independent of the tag population sizes. ART works with multiple readers with overlapping regions and can estimate sizes of arbitrarily large tag populations. ART is easy to deploy because it neither requires modification to tags nor to the communication protocol between tags and readers. ART only needs to be implemented on readers as a software module.

Radio frequency identification (RFID) systems are widely used in various applications such as supply chain management, inventory control, and object tracking. Identifying RFID tags in a given tag population is the most fundamental operation in RFID systems. While the Tree Walking (TW) protocol has become the industrial standard for identifying RFID tags, little is known about the mathematical nature of this protocol, and only some ad hoc heuristics exist for optimizing it. In this paper, first we analytically model the TW protocol, and then using that model, propose the Tree Hopping (TH) protocol that optimizes TW both theoretically and practically. The key novelty of TH is to formulate tag identification as an optimization problem and find the optimal solution that ensures the minimal average number of queries or identification time as per the requirement. With this solid theoretical underpinning, for different tag population sizes ranging from 100 to 100 K tags, TH significantly outperforms the best prior tag identification protocols on the metrics of the total number of queries per tag, the total identification time per tag, and the average number of responses per tag by an average of 40%, 59%, and 67%, respectively, when tag IDs are nonuniformly distributed in the ID space, and of 50%, 10%, and 30%, respectively, when tag IDs are uniformly distributed.

The breach of privacy in encrypted instant messenger (IM) service is a serious threat to user anonymity. Performance of previous de-anonymization strategies was limited to 65%. We perform network de-anonymization by taking advantage of the cause-effect relationship between sent and received packet streams and demonstrate this approach on a data set of Yahoo! IM service traffic traces. An investigation of various measures of causality shows that IM networks can be breached with a hit rate of 99%. A KCI Causality based approach alone can provide a true positive rate of about 97%. Individual performances of Granger, Zhang and IGCI causality are limited owing to the very low SNR of packet traces and variable network delays.

Packet classification is the core mechanism that enables many networking devices. Although using Ternary Content Addressable Memories (TCAMs) to perform high speed packet classification has become the widely adopted solution, TCAMs are very expensive, have limited capacity, consume large amounts of power, and generate tremendous amounts of heat because of their extremely dense and parallel circuitry. In this paper, we propose the first packet classification scheme that uses Binary Content Addressable Memories (BCAMs). BCAMs are similar to TCAMs except that in BCAMs, every bit has only two possible states: 0 or 1; in contrast, in TCAMs, every bit has three possible states: 0, 1, or * (don't care). Because of the high complexity in implementing the extra “don't care” state, TCAMs have much higher circuit density than BCAMs. As the power consumption, heat generation, and price grow non-linearly with circuit density, BCAMs consume much less power, generate much less heat, and cost much less money than TCAMs. Our BCAM based packet classification scheme is built on two key ideas. First, we break a multi-dimensional lookup into a series of one-dimensional lookups. Second, for each one-dimensional lookup, we convert the ternary matching problem into a binary string exact matching problem. To speed up the lookup process, we propose a number of optimization techniques including skip lists, free expansion, minimizing maximum lookup time, minimizing average lookup time, and lookup short circuiting. We evaluated our BCAM scheme on 17 real-life packet classifiers. On these classifiers, our BCAM scheme requires roughly 5 times fewer CAM bits than the traditional TCAM based scheme. The penalty is a throughput that is roughly 4 times less.

Regular expression (RegEx) matching, the core operation of intrusion detection and prevention systems, remains a fundamentally challenging problem. A desired RegEx matching scheme should satisfy four requirements: DFA speed, NFA size, automated construction, and scalable construction. Despite lots of work on RegEx matching, no prior scheme satisfies all four of these requirements. In this paper, we approach this holy grail by proposing OverlayCAM, a RegEx matching scheme that satisfies all four requirements. The theoretical underpinning of our scheme is OD2FA, a new automata model proposed in this paper that captures both state and transition replication inherent in DFAs. Our RegEx matching solution processes one input character per lookup like a DFA, requires only the space of an NFA, is grounded in sound automata models, is easy to deploy in existing network devices, and comes with scalable and automated construction algorithms.

In cloud computing, a cloud provider hosts the data of an organization and replies query results to the customers of the organization. Because organization's data are confidential and the cloud provider cannot be fully trusted, some schemes have been proposed to preserve data privacy and query result integrity. However, these schemes either include false positives in query results, or are too expensive. In this paper, we propose an effective and efficient privacy and integrity preserving scheme for multi-dimensional range queries. To preserve privacy, we propose an order-preserving hash-based function to encode both data and queries so that a cloud provider can correctly process encoded queries over encoded data without knowing their values. To preserve integrity, we propose a new data structure called local bit matrices that allows a customer to verify the integrity of a query result with a high probability. Experimental results show that our scheme can efficiently process a dataset with one million data items.

Many data center transports have been proposed in recent times (e.g., DCTCP, PDQ, pFabric, etc). Contrary to the common perception that they are competitors (i.e., protocol A vs. protocol B), we claim that the underlying strategies used in these protocols are, in fact, complementary. Based on this insight, we design PASE, a transport framework that synthesizes existing transport strategies, namely, self-adjusting endpoints (used in TCP style protocols), innetwork prioritization (used in pFabric), and arbitration (used in PDQ). PASE is deployment friendly: it does not require any changes to the network fabric; yet, its performance is comparable to, or better than, the state-of-the-art protocols that require changes to network elements (e.g., pFabric). We evaluate PASE using simulations and testbed experiments. Our results show that PASE performs well for a wide range of application workloads and network settings.

The Forwarding Information Base (FIB) of backbone routers has been rapidly growing in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time and on-chip memory usage. However, no prior IP lookup algorithm achieves both requirements at the same time. In this paper, we first propose SAIL, a Splitting Approach to IP Lookup. One splitting is along the dimension of the lookup process, namely finding the prefix length and finding the next hop, and another splitting is along the dimension of prefix length, namely IP lookup on prefixes of length less than or equal to 24 and IP lookup on prefixes of length longer than 24. Second, we propose a suite of algorithms for IP lookup based on our SAIL framework. Third, we implemented our algorithms on four platforms: CPU, FPGA, GPU, and many-core. We conducted extensive experiments to evaluate our algorithms using real FIBs and real traffic from a major ISP in China. Experimental results show that our SAIL algorithms are several times or even two orders of magnitude faster than well known IP lookup algorithms.

Mobile network operators have a significant interest in the performance of streaming video on their networks because network dynamics directly influence the Quality of Experience (QoE). However, unlike video service providers, network operators are not privy to the client- or server-side logs typically used to measure key video performance metrics, such as user engagement. To address this limitation, this paper presents the first large-scale study characterizing the impact of cellular network performance on mobile video user engagement from the perspective of a network operator. Our study on a month-long anonymized data set from a major cellular network makes two main contributions. First, we quantify the effect that 31 different network factors have on user behavior in mobile video. Our results provide network operators direct guidance on how to improve user engagement --- for example, improving mean signal-to-interference ratio by 1 dB reduces the likelihood of video abandonment by 2%. Second, we model the complex relationships between these factors and video abandonment, enabling operators to monitor mobile video user engagement in real-time. Our model can predict whether a user completely downloads a video with more than 87% accuracy by observing only the initial 10 seconds of video streaming sessions. Moreover, our model achieves significantly better accuracy than prior models that require client- or server-side logs, yet we only use standard radio network statistics and/or TCP/IP headers available to network operators.

Content Delivery Networks (CDNs) differ from other caching systems in terms of both workload characteristics and performance metrics. However, there has been little prior work on large-scale measurement and characterization of content requests and caching performance in CDNs. For workload characteristics, CDNs deal with extremely large content volume, high content diversity, and strong temporal dynamics. For performance metrics, other than hit ratio, CDNs also need to minimize the disk operations and the volume of traffic from origin servers. In this paper, we conduct a large-scale measurement study to characterize the content request patterns using real-world data from a commercial CDN provider.

With the growth in number and significance of the emerging applications that require extremely low latencies, network operators are facing increasing need to perform latency measurement on per-flow basis for network monitoring and troubleshooting. In this paper, we propose COLATE, the first per-flow latency measurement scheme that requires no probe packets and time stamping. Given a set of observation points, COLATE records packet timing information at each point so that later for any two points, it can accurately estimate the average and standard deviation of the latencies experienced by the packets of any flow in passing the two points. The key idea is that when recording packet timing information, COLATE purposely allows noise to be introduced for minimizing storage space, and when querying the latency of a target flow, COLATE uses statistical techniques to denoise and obtain an accurate latency estimate. COLATE is designed to be efficiently implementable on network middleboxes. In terms of processing overhead, COLATE performs only one hash and one memory update per packet. In terms of storage space, COLATE uses less than 0.1 bit per packet, which means that, on a backbone link with about half a million packets per second, using a 256GB drive, COLATE can accumulate time stamps of packets traversing the link for over 1.5 years. We evaluated COLATE using three real traffic traces that include a backbone traffic trace, an enterprise network traffic trace, and a data center traffic trace. Results show that COLATE always achieves the required reliability for any given confidence interval.

Regular Expression (RegEx) matching, as a core operation in many network and security applications, is typically performed on Deterministic Finite Automata (DFA) to process packets at wire speed; however, DFA size is often exponential in the number of RegExes. RegEx grouping is the practical way to address DFA state explosion. Prior RegEx grouping algorithms are extremely slow and memory intensive. In this paper, we first propose DFAestimator, an algorithm that can quickly estimate DFA size for a given RegEx set without building the actual DFA. Second, we propose RegexGrouper, a RegEx grouping algorithm based on DFA size estimation. In terms of speed and memory consumption, our work is orders of magnitude more efficient than prior art because DFA size estimation is much faster and memory efficient than DFA construction. In terms of the resulting size sum of DFAs, our work is significantly more effective than prior art because we use a much finer grained quantification of the degree of interaction between two RegExes. For example, to divide the RegEx set of the L7-filter system into 7 groups, prior art uses 279.3 minutes and the resulting 7 DFAs have a total of 29047 states, whereas RegexGrouper uses 3.2 minutes and the resulting 7 DFAs have a total of 15578 states.

In this paper, we propose FlowSifter, a framework for automated online application protocol field extraction. FlowSifter is based on a new grammar model called Counting Regular Grammars (CRG) and a corresponding automata model called Counting Automata (CA). The CRG and CA models add counters with update functions and transition guards to regular grammars and finite state automata. These additions give CRGs and CAs the ability to parse and extract fields from context sensitive application protocols. These additions also facilitate fast and stackless approximate parsing of recursive structures. These new grammar models enable FlowSifter to generate optimized Layer 7 field extractors from simple extraction specifications. We compare FlowSifter against both BinPAC and UltraPAC, which represent the state-of-the-art field extractors. Our experiments show that when compared to BinPAC parsers, FlowSifter runs more than 21 times faster and uses 49 times less memory. When compared to UltraPAC parsers, FlowSifter extractors run 12 times faster and use 24 times less memory.

Privacy has been the key road block to cloud computing as clouds may not be fully trusted. This paper concerns the problem of privacy preserving range query processing on clouds. Prior schemes are weak in privacy protection as they cannot achieve index indistinguishability, and therefore allow the cloud to statistically estimate the values of data and queries using domain knowledge and history query results. In this paper, we propose the first range query processing scheme that achieves index indistinguishability under the indistinguishability against chosen keyword attack (IND-CKA). Our key idea is to organize indexing elements in a complete binary tree called PBtree, which satisfies structure indistinguishability ( i.e. , two sets of data items have the same PBtree structure if and only if the two sets have the same number of data items) and node indistinguishability ( i.e. , the values of PBtree nodes are completely random and have no statistical meaning). We prove that our scheme is secure under the widely adopted IND-CKA security model. We propose two algorithms, namely PBtree traversal width minimization and PBtree traversal depth minimization, to improve query processing efficiency. We prove that the worse case complexity of our query processing algorithm using PBtree is O (| R | log n ), where n is the total number of data items and R is the set of data items in the query result. We implemented and evaluated our scheme on a real world data set with 5 million items. For example, for a query whose results contain ten data items, it takes only 0.17 milliseconds.

Owing to its superior properties, such as fast identification and relatively long interrogating range over barcode systems, Radio Frequency Identification (RFID) technology has promising application prospects in inventory management. This paper studies the problem of complete identification of missing RFID tag, which is important in practice. Time efficiency is the key performance metric of missing tag identification. However, the existing protocols are ineffective in terms of execution time and can hardly satisfy the requirements of realtime applications. In this paper, a Multi-hashing based Missing Tag Identification (MMTI) protocol is proposed, which achieves better time efficiency by improving the utilization of the time frame used for identification. Specifically, the reader recursively sends bitmaps that reflect the current slot occupation state to guide the slot selection of the next hashing process, thereby changing more empty or collision slots to the expected singleton slots. We investigate the optimal parameter settings to maximize the performance of the MMTI protocol. Furthermore, we discuss the case of channel error and propose the countermeasures to make the MMTI workable in the scenarios with imperfect communication channels. Extensive simulation experiments are conducted to evaluate the performance of MMTI, and the results demonstrate that this new protocol significantly outperforms other related protocols reported in the current literature.

Regular expression (RE) matching is a core component of deep packet inspection in modern networking and security devices. In this paper, we propose the first hardware-based RE matching approach that uses ternary content addressable memory (TCAM), which is available as off-the-shelf chips and has been widely deployed in modern networking devices for tasks such as packet classification. We propose three novel techniques to reduce TCAM space and improve RE matching speed: transition sharing, table consolidation, and variable striding. We tested our techniques on eight real-world RE sets, and our results show that small TCAMs can be used to store large deterministic finite automata (DFAs) and achieve potentially high RE matching throughput. For space, we can store each of the corresponding eight DFAs with 25 000 states in a 0.59-Mb TCAM chip. Using a different TCAM encoding scheme that facilitates processing multiple characters per transition, we can achieve potential RE matching throughput of 10-19 Gb/s for each of the eight DFAs using only a single 2.36-Mb TCAM chip.

Network intrusion detection and prevention systems commonly use regular expression (RE) signatures to represent individual security threats. While the corresponding deterministic finite state automata (DFA) for any one RE is typically small, the DFA that corresponds to the entire set of REs is usually too large to be constructed or deployed. To address this issue, a variety of alternative automata implementations that compress the size of the final automaton have been proposed such as extended finite automata (XFA) and delayed input DFA (D2FA). The resulting final automata are typically much smaller than the corresponding DFA. However, the previously proposed automata construction algorithms do suffer from some drawbacks. First, most employ a “Union then Minimize” framework where the automata for each RE are first joined before minimization occurs. This leads to an expensive nondeterministic finite automata (NFA) to DFA subset construction on a relatively large NFA. Second, most construct the corresponding large DFA as an intermediate step. In some cases, this DFA is so large that the final automaton cannot be constructed even though the final automaton is small enough to be deployed. In this paper, we propose a “Minimize then Union” framework for constructing compact alternative automata focusing on the D2FA. We show that we can construct an almost optimal final D2FA with small intermediate parsers. The key to our approach is a space- and time-efficient routine for merging two compact D2FA into a compact D2FA. In our experiments, our algorithm runs on average 155 times faster and uses 1500 times less memory than previous algorithms. For example, we are able to construct a D2FA with over 80 000 000 states using only 1 GB of main memory in only 77 min.

Virtual network embedding, which means mapping virtual networks requested by users to a shared substrate network maintained by an Internet service provider, is a key function that network virtualization needs to provide. Prior work on virtual network embedding has primarily focused on maximizing the revenue of the Internet service provider and did not consider the energy cost in accommodating such requests. As energy cost is more than half of the operating cost of the substrate networks, while trying to accommodate more virtual network requests, minimizing energy cost is critical for infrastructure providers. In this paper, we make the first effort toward energy-aware virtual network embedding. We first propose an energy cost model and formulate the energy-aware virtual network embedding problem as an integer linear programming problem. We then propose two efficient energy-aware virtual network embedding algorithms: a heuristic-based algorithm and a particle-swarm-optimization-technique-based algorithm. We implemented our algorithms in C++ and performed side-by-side comparison with prior algorithms. The simulation results show that our algorithms significantly reduce the energy cost by up to 50% over the existing algorithm for accommodating the same sequence of virtual network requests.

Regular expression (RegEx) matching is a core function of deep packet inspection in modern network devices. Previous TCAM-based RegEx matching algorithms a priori assume that a deterministic finite automaton (DFA) can be built for a given set of RegEx patterns. However, practical RegEx patterns contain complex terms like wildcard closure and repeat character, and it may be impossible to build a DFA with a reasonable number of states. This results in prior work to being infeasible in practice. Moreover, TCAM-based RegEx matching is required to scale to a large-scale set of RegEx patterns. In this paper, we propose a compressed finite automaton implementation called (CFA) for scalable TCAM-based RegEx matching. CFA is designed to reduce TCAM space by using three compression techniques: transition, character, and state compressions. Experiments on realistic RegEx pattern sets show CFA highly outperforms previous solutions in terms of TCAM space, matching throughput, and TCAM power consumption.

Recently, the Graphics Processing Unit (GPU) has been proved to be an exciting new platform for software routers, providing high throughput and flexibility. However, it is still a challenging task to deploy some core routing functions into GPU-based software routers with anticipatory performance and scalability, such as IP address lookup. Existing solutions have good performance, but their scalability to IPv6 and frequent updates are not so encouraging. In this paper, we investigate GPU's characteristics in parallelism and memory accessing, and then encode a multibit trie into a state-jump table. On this basis, a fast and scalable IP lookup engine called GPU-Accelerated Multi-bit Trie (GAMT) has been presented. According to our experiments on real-world routing data, based on the multi-stream pipeline, GAMT enables lookup speeds as high as 1072 and 658 Million Lookups Per Second (MLPS) for IPv4/6 respectively, when performing a 16M traffic under highly frequent updates (70, 000 updates/s). Even using a small batch size, GAMT can still achieve 339 and 240 MLPS respectively, while keeping the average lookup latency below 100 μs. These results show clearly that GAMT makes significant progress on both scalability and performance.

Packet classification is the key mechanism for enabling many networking and security services. Ternary Content Addressable Memory (TCAM) has been the industrial standard for implementing high-speed packet classification because of its constant classification time. However, TCAM chips have small capacity, high power consumption, high heat generation, and large area size. This paper focuses on the TCAM-based Classifier Compression problem: given a classifier C, we want to construct the smallest possible list of TCAM entries T that implement C. In this paper, we propose the Ternary Unification Framework (TUF) for this compression problem and three concrete compression algorithms within this framework. The framework allows us to find more optimization opportunities and design new TCAM-based classifier compression algorithms. Our experimental results show that the TUF can speed up the prior algorithm TCAM Razor by twenty times or more and leads to new algorithms that improve compression performance over prior algorithms by an average of 13.7% on our largest real life classifiers.

Multipath TCP (MPTCP) allows the concurrent use of multiple paths between two end points, and as such holds great promise for improving application performance. However, in this paper, we report a newly discovered class of attacks on MPTCP that may jeopardize and hamper its wide-scale adoption. The attacks stem from the interdependence between the multiple subflows in an MPTCP connection. MPTCP congestion control algorithms are designed to achieve resource pooling and fairness with single-path TCP users at shared bottlenecks. Therefore, multiple MPTCP subflows are inherently coupled with each other, resulting in potential side-channels that can be exploited to infer cross-path properties. In particular, an ISP monitoring one or more paths used by an MPTCP connection can infer sensitive and proprietary information (e.g., level of network congestion, end-to-end TCP throughput, packet loss, network delay) about its competitors. Since the side-channel information enabled by the coupling among the subflows in an MPTCP connection results directly from the design goals of MPTCP congestion control algorithms, it is not obvious how to circumvent this attack easily. We believe our findings provide insights that can be used to guide future security-related research on MPTCP and other similar multipath extensions.

We present a novel attack on relayed instant messaging (IM) traffic that allows an attacker to infer who's talking to whom with high accuracy. This attack only requires collection of packet header traces between users and IM servers for a short time period, where each packet in the trace goes from a user to an IM server or vice-versa. The specific goal of the attack is to accurately identify a candidate set of top-k users with whom a given user possibly talked to, while using only the information available in packet header traces (packet payloads cannot be used because they are mostly encrypted). Towards this end, we propose a wavelet-based scheme, called COmmunication Link De-anonymization (COLD), and evaluate its effectiveness using a real-world Yahoo! Messenger data set. The results of our experiments show that COLD achieves a hit rate of more than 90% for a candidate set size of 10. For slightly larger candidate set size of 20, COLD achieves almost 100% hit rate. In contrast, a baseline method using time series correlation could only achieve less than 5% hit rate for similar candidate set sizes.

Regular Expression (RegEx) matching is the core operation of various network security devices such as IPSes. Despite much effort, it has remained an unsolved problem to achieve both high speed and low memory requirements.XFA, the state-of-the-art software RegEx matching solution, has two fundamental limitations: (1) XFA construction is hard to automate as it requires manual annotation by human experts, and (2) XFA is hard to implement in ASIC as the program executed upon reaching a state requires much of the complexity of a general purpose CPU. In this paper, we propose HASIC, a History-based Finite Automaton (HFA [11]) based RegEx matching scheme. HASIC can exponentially reduce state explosion by testing, setting, and clearing an auxiliary vector of history bits. Compared with XFA, HASIC advances the state of the art because it can be fully automated and it is ASIC friendly. HASIC only uses three simple bit operations and they are easy to implement in ASIC. We conducted experiments using real-world RegEx sets and various traffic traces. Experimental results show that for packet processing speed, software HFA runs an average of 3.34 times faster than XFA, for automata construction speed HFA is orders of magnitude faster than DFA, and for memory image size HFA is an average of 20 times smaller than DFA.

In many countries, the Internet is under stringent censorship for political or religious reasons which severely undermines the free flow of information. A censorship-resistant web browsing system must be scalable, blocking resistant, and tracing resistant. However, current censorship-resistant web browsing systems, which use a group of dedicated proxies to bypass censorship, fail to meet these requirements. To tackle these challenges, we propose Free web, which relies on widely-distributed peer-to-peer (P2P) nodes in a decentralized manner rather than specified proxies in a centralized manner. Free web is built on top of a Distributed Hash Table (DHT)-based P2P network, where nodes not under censorship help nodes under censorship to access blocked web pages. Free web has a web browser front end whose user interface resembles existing web browsers. The underlying complex process of retrieving blocked web pages is therefore hidden from users. We implemented and open-sourced Free web and conducted extensive real-world experiments on Planet Lab. The experimental results show that Free web has a high success rate and reasonable browsing latency.

Access Control Lists (ACLs) are the core of many networking and security devices. As new threats and vulnerabilities emerge, ACLs on routers and firewalls are getting larger. Therefore, compressing ACLs is an important problem. In this paper, we propose a new approach, called Diplomat, to ACL compression. The key idea is to transform higher dimensional target patterns into lower dimensional patterns by dividing the original pattern into a series of hyperplanes and then resolving differences between two adjacent hyperplanes by adding rules that specify the differences. This approach is fundamentally different from prior ACL compression algorithms and is shown to be very effective. We implemented Diplomat and conducted side-by-side comparison with the prior Firewall Compressor algorithm on real life classifiers. The experimental results show that Diplomat outperforms Firewall Compressor most of the time, often by a considerable margin. In particular, on our largest ACLs, Diplomat has an average improvement ratio over Firewall Compressor of 30.6%.

Two-tiered wireless sensor networks offer good scalability, efficient power usage, and space saving. However, storage nodes are more attractive to attackers than sensors because they store sensor collected data and processing sink issued queries. A compromised storage node not only reveals sensor collected data, but also may reply incomplete or wrong query results. In this paper, we propose QuerySec, a protocol that enables storage nodes to process queries correctly while prevents them from revealing both data from sensors and queries from the sink. To protect privacy, we propose an order preserving function-based scheme to encode both sensor collected data and sink issued queries, which allows storage nodes to process queries correctly without knowing the actual values of both data and queries. To preserve integrity, we proposed a link watermarking scheme, where data items are formed into a link by the watermarks embedded in them so that any deletion in query results can be detected.

Bloom filters are space-efficient data structures for fast set membership queries. Counting Bloom Filters (CBFs) extend Bloom filters by allowing insertions and deletions to support dynamic sets. The performance of CBFs is critical for various applications and systems. This paper presents a novel approach to building a fast and accurate data structure called Multiple-Partitioned Counting Bloom Filter (MPCBF) that addresses large-scale data processing challenges. MPCBF is based on two ideas: reducing the number of memory accesses from k (for k hash functions) in the standard CBF to only one memory access in the basic MPCBF-1 case, and a hierarchical structure to improve the false positive rate. We also generalize MPCBF-1 to MPCBF-g to accommodate up to g memory accesses. Our simulation and implementation in MapReduce show that MPCBF outperforms the standard CBF in terms of speed and accuracy. Compared to CBF, at the same memory consumption, MPCBF significantly reduces the false positive rate by an order of magnitude, with a reduction of processing overhead by up to 85.9%.

Radio Frequency Identification (RFID) technology is widely used in the the retail, warehouse and supply chain management. However, unknown RFID tags appear when the unregistered tagged objects are moved in or tagged objects are misplaced, which leads to huge economic losses (e.g., misplaced chilled food in a warehouse may quickly decay). This paper studies the practically important problem of unknown tag detection. To the best of our knowledge, this is the first piece of work taking both time-efficiency and energy-efficiency into consideration, where the energy-efficiency is very important when the battery-powered active tags are used. This paper proposes two efficient protocols to address the problem of unknown tag detection. Specifically, the Basic Unknown Tag Detection (B-UTD) protocol leverages a cost-effective filter vector to detect the unknown tags, based on which we then propose a Sampling based Unknown Tag Detection (SUTD) protocol by adopting the well-known sampling idea. We present theoretical analysis to optimize the performance of the proposed protocols. Extensive simulations are conducted to evaluate the performance of the proposed protocols. And the experimental results show that the proposed S-UTD protocol considerably outperforms the most related protocol by reducing more than 90% of the required execution time and energy consumption.

With the rich functionalities and enhanced computing capabilities available on mobile computing devices with touch screens, users not only store sensitive information (such as credit card numbers) but also use privacy sensitive applications (such as online banking) on these devices, which make them hot targets for hackers and thieves. To protect private information, such devices typically lock themselves after a few minutes of inactivity and prompt a password/PIN/pattern screen when reactivated. Passwords/PINs/patterns based schemes are inherently vulnerable to shoulder surfing attacks and smudge attacks. Furthermore, passwords/PINs/patterns are inconvenient for users to enter frequently. In this paper, we propose GEAT, a gesture based user authentication scheme for the secure unlocking of touch screen devices. Unlike existing authentication schemes for touch screen devices, which use what user inputs as the authentication secret, GEAT authenticates users mainly based on how they input, using distinguishing features such as finger velocity, device acceleration, and stroke time. Even if attackers see what gesture a user performs, they cannot reproduce the behavior of the user doing gestures through shoulder surfing or smudge attacks. We implemented GEAT on Samsung Focus running Windows, collected 15009 gesture samples from 50 volunteers, and conducted real-world experiments to evaluate GEAT's performance. Experimental results show that our scheme achieves an average equal error rate of 0.5% with 3 gestures using only 25 training samples.

During crowded events, cellular networks face voice and data traffic volumes that are often orders of magnitude higher than what they face during routine days. Despite the use of portable base stations for temporarily increasing communication capacity and free Wi-Fi access points for offloading Internet traffic from cellular base stations, crowded events still present significant challenges for cellular network operators looking to reduce dropped call events and improve Internet speeds. For effective cellular network design, management, and optimization, it is crucial to understand how cellular network performance degrades during crowded events, what causes this degradation, and how practical mitigation schemes would perform in real-life crowded events. This paper makes a first step towards this end by characterizing the operational performance of a tier-1 cellular network in the United States during two high-profile crowded events in 2012. We illustrate how the changes in population distribution, user behavior, and application workload during crowded events result in significant voice and data performance degradation, including more than two orders of magnitude increase in connection failures. Our findings suggest two mechanisms that can improve performance without resorting to costly infrastructure changes: radio resource allocation tuning and opportunistic connection sharing. Using trace-driven simulations, we show that more aggressive release of radio resources via 1-2 seconds shorter RRC timeouts as compared to routine days helps to achieve better tradeoff between wasted radio resources, energy consumption, and delay during crowded events; and opportunistic connection sharing can reduce connection failures by 95% when employed by a small number of devices in each cell sector.

Radio Frequency Identification (RFID) systems are widely used in various applications such as supply chain management, inventory control, and object tracking. Identifying RFID tags in a given tag population is the most fundamental operation in RFID systems. While the Tree Walking (TW) protocol has become the industrial standard for identifying RFID tags, little is known about the mathematical nature of this protocol and only some ad-hoc heuristics exist for optimizing it. In this paper, first, we analytically model the TW protocol, and then using that model, propose the Tree Hopping (TH) protocol that optimizes TW both theoretically and practically. The key novelty of TH is to formulate tag identification as an optimization problem and find the optimal solution that ensures the minimal average number of queries. With this solid theoretical underpinning, for different tag population sizes ranging from 100 to 100K tags, TH significantly outperforms the best prior tag identification protocols on the metrics of the total number of queries per tag, the total identification time per tag, and the average number of responses per tag by an average of 50%, 10%, and 30%, respectively, when tag IDs are uniformly distributed in the ID space, and of 26%, 37%, and 26%, respectively, when tag IDs are non-uniformly distributed.

This paper addresses the problem of identifying the top-k information hubs in a social network. Identifying top-k information hubs is crucial for many applications such as advertising in social networks where advertisers are interested in identifying hubs to whom free samples can be given. Existing solutions are centralized and require time stamped information about pair-wise user interactions and can only be used by social network owners as only they have access to such data. Existing distributed algorithms suffer from poor accuracy. In this paper, we propose a new algorithm to identify information hubs that preserves user privacy. Our method can identify hubs without requiring a central entity to access the complete friendship graph. We achieve this by fully distributing the computation using the Kempe-McSherry algorithm, while addressing user privacy concerns. We evaluate the effectiveness of our proposed technique using three real-world data set; The first two are Facebook data sets containing about 6 million users and more than 40 million friendship links. The third data set is from Twitter and comprises of a little over 2 million users. The results of our analysis show that our algorithm is up to 50% more accurate than existing algorithms. Results also show that the proposed algorithm can estimate the rank of the top-k information hubs users more accurately than existing approaches.

Identifying leaders and followers in online social networks is important for various applications in many domains such as advertisement, community health campaigns, administrative science, and even politics. In this paper, we study the problem of identifying leaders and followers in online social networks using user interaction information. We propose a new model, called the Longitudinal User Centered Influence (LUCI) model, that takes as input user interaction information and clusters users into four categories: introvert leaders, extrovert leaders, followers, and neutrals. To validate our model, we first apply it to a data set collected from an online social network called Everything2. Our experimental results show that our LUCI model achieves an average classification accuracy of up to 90.3% in classifying users as leaders and followers, where the ground truth is based on the labeled roles of users. Second, we apply our LUCI model on a data set collected from Facebook consisting of interactions among more than 3 million users over the duration of one year. However, we do not have ground truth data for Facebook users. Therefore, we analyze several important topological properties of the friendship graph for different user categories. Our experimental results show that different user categories exhibit different topological characteristics in the friendship graph and these observed characteristics are in accordance with the expected ones based on the general definition of the four roles.

Firewalls have been widely deployed on the Internet for securing private networks. A firewall checks each incoming or outgoing packet to decide whether to accept or discard the packet based on its policy. Optimizing firewall policies is crucial for improving network performance. Prior work on firewall optimization focuses on either intrafirewall or interfirewall optimization within one administrative domain where the privacy of firewall policies is not a concern. This paper explores interfirewall optimization across administrative domains for the first time. The key technical challenge is that firewall policies cannot be shared across domains because a firewall policy contains confidential information and even potential security holes, which can be exploited by attackers. In this paper, we propose the first cross-domain privacy-preserving cooperative firewall policy optimization protocol. Specifically, for any two adjacent firewalls belonging to two different administrative domains, our protocol can identify in each firewall the rules that can be removed because of the other firewall. The optimization process involves cooperative computation between the two firewalls without any party disclosing its policy to the other. We implemented our protocol and conducted extensive experiments. The results on real firewall policies show that our protocol can remove as many as 49% of the rules in a firewall, whereas the average is 19.4%. The communication cost is less than a few hundred kilobytes. Our protocol incurs no extra online packet processing overhead, and the offline processing time is less than a few hundred seconds.

This paper concerns the fundamental problem of identifying the content nature of a flow-namely text, binary, or encrypted-for the first time. We propose Iustitia, a framework for identifying flow nature on the fly. The key observation behind Iustitia is that text flows have the lowest entropy and encrypted flows have the highest entropy, while the entropy of binary flows stands in between. We further extend Iustitia for the finer-grained classification of binary flows so that we can differentiate different types of binary flows (such as image, video, and executables) and even the file formats (such as JPEG and GIF for images, MPEG and AVI for videos) carried by binary flows. The basic idea of Iustitia is to classify flows using machine learning techniques where a feature is the entropy of every certain number of consecutive bytes. Our experimental results show that the classification can be done with high speed and high accuracy. On average, Iustitia can classify flows with 88.27% of accuracy using a buffer size of 1 K with a classification time of less than 10% of packet interarrival time for 91.2% of flows.

Quantifying and querying network reachability is important for security monitoring and auditing as well as many aspects of network management such as troubleshooting, maintenance, and design. Although attempts to model network reachability have been made, feasible solutions to computing network reachability have remained unknown. In this paper, we propose a suite of algorithms for quantifying reachability based on network configurations [mainly Access Control Lists (ACLs)] as well as solutions for querying network reachability. We present a network reachability model that considers connectionless and connection-oriented transport protocols, stateless and stateful routers/firewalls, static and dynamic NAT, PAT, IP tunneling, etc. We implemented the algorithms in our network reachability tool called Quarnet and conducted experiments on a university network. Experimental results show that the offline computation of reachability matrices takes a few hours, and the online processing of a reachability query takes 0.075 s on average.

Cellular network-based machine-to-machine (M2M) communication is fast becoming a market-changing force for a wide spectrum of businesses and applications such as telematics, smart metering, point-of-sale terminals, and home security and automation systems. In this paper, we aim to answer the following important question: Does traffic generated by M2M devices impose new requirements and challenges for cellular network design and management? To answer this question, we take a first look at the characteristics of M2M traffic and compare it to traditional smartphone traffic. We have conducted our measurement analysis using a week-long traffic trace collected from a tier-1 cellular network in the US. We characterize M2M traffic from a wide range of perspectives, including temporal dynamics, device mobility, application usage, and network performance. Our experimental results show that M2M traffic exhibits significantly different patterns than smartphone traffic in multiple aspects. For instance, M2M devices have a much larger ratio of uplink-to-downlink traffic volume, their traffic typically exhibits different diurnal patterns, they are more likely to generate synchronized traffic resulting in bursty aggregate traffic volumes, and are less mobile compared to smartphones. On the other hand, we also find that M2M devices are generally competing with smartphones for network resources in co-located geographical regions. These and other findings suggest that better protocol design, more careful spectrum allocation, and modified pricing schemes may be needed to accommodate the rise of M2M devices.

Extracting the protocol message format specifications of unknown applications from network traces is important for a variety of applications such as application protocol parsing, vulnerability discovery, and system integration. In this paper, we propose ProDecoder, a network trace based protocol message format inference system that exploits the semantics of protocol messages without the executable code of application protocols. ProDecoder is based on the key insight that the n-grams of protocol traces exhibit highly skewed frequency distribution that can be leveraged for accurate protocol message format inference. In ProDecoder, we first discover the latent relationship among n-grams by first grouping protocol messages with the same semantics and then inferring message formats by keyword based clustering and cluster sequence alignment. We implemented and evaluated ProDecoder to infer message format specifications of SMB (a binary protocol) and SMTP (a textual protocol). Our experimental results show that ProDecoder accurately parses and infers SMB protocol with 100% precision and recall. For SMTP, ProDecoder achieves approximately 95% precision and recall.

Software systems inherently contain vulnerabilities that have been exploited in the past resulting in significant revenue losses. The study of vulnerability life cycles can help in the development, deployment, and maintenance of software systems. It can also help in designing future security policies and conducting audits of past incidents. Furthermore, such an analysis can help customers to assess the security risks associated with software products of different vendors. In this paper, we conduct an exploratory measurement study of a large software vulnerability data set containing 46310 vulnerabilities disclosed since 1988 till 2011. We investigate vulnerabilities along following seven dimensions: (1) phases in the life cycle of vulnerabilities, (2) evolution of vulnerabilities over the years, (3) functionality of vulnerabilities, (4) access requirement for exploitation of vulnerabilities, (5) risk level of vulnerabilities, (6) software vendors, and (7) software products. Our exploratory analysis uncovers several statistically significant findings that have important implications for software development and deployment.

Firewalls are critical security devices handling all traffic in and out of a network. Firewalls, like other software and hardware network devices, have vulnerabilities, which can be exploited by motivated attackers. However, because firewalls are usually placed in the network such that they are transparent to the end users, it is very hard to identify them and use their corresponding vulnerabilities to attack them. In this paper, we study firewall fingerprinting, in which one can use firewall decisions on TCP packets with unusual flags and machine learning techniques for inferring firewall implementation.

In this paper, we introduce FlowSifter, a systematic framework for online application protocol field extraction. FlowSifter introduces a new grammar model Counting Regular Grammars (CRG) and a corresponding automata model Counting Automata (CA). The CRG and CA models add counters with update functions and transition guards to regular grammars and finite state automata. These additions give CRGs and CAs the ability to parse and extract fields from context sensitive application protocols. These additions also facilitate fast and stackless approximate parsing of recursive structures. These new grammar models enable FlowSifter to generate optimized Layer 7 field extractors from simple extraction specifications. In our experiments, we compare FlowSifter against both BinPAC and UltraPAC, which are the freely available state of the art field extractors. Our experiments show that when compared to UltraPAC parsers, FlowSifter extractors run 84% faster and use 12% of the memory.

Recent studies on cellular network measurement have provided the evidence that significant geospatial correlations, in terms of traffic volume and application access, exist in cellular network usage. Such geospatial correlation patterns provide local optimization opportunities to cellular network operators for handling the explosive growth in the traffic volume observed in recent years. To the best of our knowledge, in this paper, we provide the first fine-grained characterization of the geospatial dynamics of application usage in a 3G cellular data network. Our analysis is based on two simultaneously collected traces from the radio access network (containing location records) and the core network (containing traffic records) of a tier-1 cellular network in the United States. To better understand the application usage in our data, we first cluster cell locations based on their application distributions and then study the geospatial dynamics of application usage across different geographical regions. The results of our measurement study present cellular network operators with fine-grained insights that can be leveraged to tune network parameter settings.

Radio Frequency Identification (RFID) systems have been widely deployed for various applications such as object tracking, 3D positioning, supply chain management, inventory control, and access control. This paper concerns the fundamental problem of estimating RFID tag population size, which is needed in many applications such as tag identification, warehouse monitoring, and privacy sensitive RFID systems. In this paper, we propose a new scheme for estimating tag population size called Average Run based Tag estimation (ART). The technique is based on the average run-length of ones in the bit string received using the standardized framed slotted Aloha protocol. ART is significantly faster than prior schemes because its estimator has smaller variance compared to the variances of estimators of prior schemes. For example, given a required confidence interval of 0.1% and a required reliability of 99.9%, ART is consistently 7 times faster than the fastest existing schemes (UPE and EZB) for any tag population size. Furthermore, ART's estimation time is observably independent of the tag population sizes. ART is easy to deploy because it neither requires modification to tags nor to the communication protocol between tags and readers. ART only needs to be implemented on readers as a software module. ART works with multiple readers with overlapping regions.

Cellular network based Machine-to-Machine (M2M) communication is fast becoming a market-changing force for a wide spectrum of businesses and applications such as telematics, smart metering, point-of-sale terminals, and home security and automation systems. In this paper, we aim to answer the following important question: Does traffic generated by M2M devices impose new requirements and challenges for cellular network design and management? To answer this question, we take a first look at the characteristics of M2M traffic and compare it with traditional smartphone traffic. We have conducted our measurement analysis using a week-long traffic trace collected from a tier-1 cellular network in the United States. We characterize M2M traffic from a wide range of perspectives, including temporal dynamics, device mobility, application usage, and network performance.

With the explosive growth of network-based services and attacks, the complexity and cost of firewall deployment and management have been increasing rapidly. Yet, each private network, no matter big or small, has to deploy and manage its own firewall, which is the critical first line of defense. To reduce the complexity and cost in deploying and managing firewalls, businesses have started to outsource the firewall service to their Internet Service Providers (ISPs), such as AT&T, which provide cloud-based firewal service. Such fire walling model saves businesses in managing, deploying, and upgrading firewalls. The current firewall service outsourcing model requires businesses fully trust their ISPs and give ISPs their firewall policies. However, businesses typically need to keep their firewall policies confidential. In this paper, we propose the first privacy preserving firewall outsourcing approach where businesses outsource their firewall services to ISPs without revealing their firewall policies to the ISPs. The basic idea is that businesses first anonymize their firewall policies and send the anonymized policies to their ISP, then the ISP performs packet filtering based on the anonymized firewall policies. For anonymizing firewall policies, we use Firewall Decision Diagrams to cope with the multi-dimensionality of policies and Bloom Filters for the anonymization purpose. This paper deals with a hard problem. By no means that we claim our scheme is perfect, however, this effort represents the first step towards privacy preserving outsourcing of firewall services. We implemented our scheme and conducted extensive experiments. Our experimental results show that our scheme is efficient in terms of both memory usage and packet lookup time. The firewall throughput of our scheme running at ISPs is comparable to that of software firewalls running at businesses themselves.

Firewalls are critical components of network security and have been widely deployed for protecting private networks. A firewall determines whether to accept or discard a packet that passes through it based on its policy. However, most real-life firewalls have been plagued with policy faults, which either allow malicious traffic or block legitimate traffic. Due to the complexity of firewall policies, manually locating the faults of a firewall policy and further correcting them are difficult. Automatically correcting the faults of a firewall policy is an important and challenging problem. In this article, we first propose a fault model for firewall policies including five types of faults. For each type of fault, we present an automatic correction technique. Second, we propose the first systematic approach that employs these five techniques to automatically correct all or part of the misclassified packets of a faulty firewall policy. Third, we conducted extensive experiments to evaluate the effectiveness of our approach. Experimental results show that our approach is effective to correct a faulty firewall policy with three of these types of faults.

Firewalls are the mainstay of enterprise security and the most widely adopted technology for protecting private networks. As the quality of protection provided by a firewall directly depends on the quality of its policy (i.e., configuration), ensuring the correctness of firewall policies is important and yet difficult. To help ensure the correctness, we propose a systematic structural testing approach for firewall policies. We define structural coverage (based on coverage criteria of rules, predicates, and clauses) on the firewall policy under test. To achieve high structural coverage effectively, we have developed four automated packet generation techniques: the random packet generation, the one based on local constraint solving (considering individual rules locally in a policy), the one based on global constraint solving (considering multiple rules globally in a policy), and the one based on boundary values. We have conducted an experiment on a set of real policies and a set of faulty policies to detect faults with generated packet sets. Generally, our experimental results show that a packet set with higher structural coverage has higher fault-detection capability (i.e., detecting more injected faults). Our experimental results show that a reduced packet set (maintaining the same level of structural coverage with the corresponding original packet set) maintains similar fault-detection capability with the original set.

Firewalls are the cornerstones of the security infrastructure for most enterprises. They have been widely deployed for protecting private networks. The quality of the protection provided by a firewall directly depends on the quality of its policy (i.e., configuration). Due to the lack of tools for analyzing firewall policies, many firewalls used today have policy errors. A firewall policy error either creates security holes that will allow malicious traffic to sneak into a private network or blocks legitimate traffic and disrupts normal business processes, which in turn could lead to irreparable, if not tragic, consequences. A major cause of policy errors are policy changes. Firewall policies often need to be changed as networks evolve and new threats emerge. Users behind a firewall often request the firewall administrator to modify rules to allow or protect the operation of some services. In this article, we first present the theory and algorithms for firewall policy change-impact analysis. Our algorithms take as input a firewall policy and a proposed change, then output the accurate impact of the change. Thus, a firewall administrator can verify a proposed change before committing it. We implemented our firewall change-impact analysis algorithms, and tested them on both real-life and synthetic firewall policies. The experimental results show that our algorithms are effective in terms of ensuring firewall policy correctness and efficient in terms of computing the impact of policy changes. Thus, our tool can be practically used in the iterative process of firewall policy design and maintenance. Although the focus of this article is on firewalls, the change-impact analysis algorithms proposed in this article are not limited to firewalls. Rather, they can be applied to other rule-based systems, such as router access control lists (ACLs), as well.

The architecture of two-tiered sensor networks, where storage nodes serve as an intermediate tier between sensors and a sink for storing data and processing queries, has been widely adopted because of the benefits of power and storage saving for sensors as well as the efficiency of query processing. However, the importance of storage nodes also makes them attractive to attackers. In this paper, we propose SafeQ, a protocol that prevents attackers from gaining information from both sensor collected data and sink issued queries. SafeQ also allows a sink to detect compromised storage nodes when they misbehave. To preserve privacy, SafeQ uses a novel technique to encode both data and queries such that a storage node can correctly process encoded queries over encoded data without knowing their values. To preserve integrity, we propose two schemes—one using Merkle hash trees and another using a new data structure called neighborhood chains—to generate integrity verification information so that a sink can use this information to verify whether the result of a query contains exactly the data items that satisfy the query. To improve performance, we propose an optimization technique using Bloom filters to reduce the communication cost between sensors and storage nodes.

Ternary content addressable memories (TCAMs) have become the de facto standard in industry for fast packet classification. Unfortunately, TCAMs have limitations of small capacity, high power consumption, high heat generation, and high cost. The well-known range expansion problem exacerbates these limitations as each classifier rule typically has to be converted to multiple TCAM rules. One method for coping with these limitations is to use compression schemes to reduce the number of TCAM rules required to represent a classifier. Unfortunately, all existing compression schemes only produce prefix classifiers. Thus, they all miss the compression opportunities created by non-prefix ternary classifiers. In this paper, we propose bit weaving, the first non-prefix compression scheme. Bit weaving is based on the observation that TCAM entries that have the same decision and whose predicates differ by only one bit can be merged into one entry by replacing the bit in question with . Bit weaving consists of two new techniques, bit swapping and bit merging, to first identify and then merge such rules together. The key advantages of bit weaving are that it runs fast, it is effective, and it is composable with other TCAM optimization methods as a pre/post-processing routine. We implemented bit weaving and conducted experiments on both real-world and synthetic packet classifiers. Our experimental results show the following: 1) bit weaving is an effective standalone compression technique (it achieves an average compression ratio of 23.6%); 2) bit weaving finds compression opportunities that other methods miss. Specifically, bit weaving improves the prior TCAM optimization techniques of TCAM Razor and Topological Transformation by an average of 12.8% and 36.5%, respectively.

Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classication has become the de facto standard in industry because TCAMs facilitate constant time classication by comparing packet elds against ternary encoded rules in parallel. Despite their high speed, TCAMs have limitations of small capacity, large power consumption, and relatively slow access times. One reason TCAM-based packet classiers are so large is the multiplicative eect inherent in representing d-dimensional classiers in TCAMs. To address the multiplicative effect, we propose the TCAM Split architecture, where a d-dimensional classier is split into k = 2 low dimensional classiers, each of which is stored on its own small TCAM. A d-dimensional lookup is split into k low dimensional, pipe-lined lookups with one lookup on each chip. Our experimental results with real-life classiers show that TCAM Split reduces classier size by 84% using only two small TCAM chips, this increases to 93% if we use ve small TCAM chips.

Hamming distance has been widely used in many application domains, such as near-duplicate detection and pattern recognition. We study Hamming distance range query problems, where the goal is to find all strings in a database that are within a Hamming distance bound k from a query string. If k is fixed, we have a static Hamming distance range query problem. If k is part of the input, we have a dynamic Hamming distance range query problem. For the static problem, the prior art uses lots of memory due to its aggressive replication of the database. For the dynamic range query problem, as far as we know, there is no space and time efficient solution for arbitrary databases. In this paper, we first propose a static Hamming distance range query algorithm called HEngined, which addresses the space issue in prior art by dynamically expanding the query on the fly. We then propose a dynamic Hamming distance range query algorithm called HEngined, which addresses the limitation in prior art using a divide-and-conquer strategy. We implemented our algorithms and conducted side-by-side comparisons on large real-world and synthetic datasets. In our experiments, HEnginesuses 4.65 times less space and processes queries 16% faster than the prior art, and HEnginedprocesses queries 46 times faster than linear scan while using only 1.7 times more space.

Network reachability is one of the key factors for capturing end-to-end network behavior and detecting the violation of security policies. While quantifying network reachability within one administrative domain is already difficult, quantifying network reachability across multiple administrative domains is more difficult because the privacy of security policies becomes a serious concern and needs to be protected through this process. In this paper, we propose the first cross-domain privacy-preserving protocol for quantifying network reachability. Our protocol constructs equivalent representations of the Access Control List (ACL) rules and determines network reachability while preserving the privacy of the individual ACLs. This protocol can accurately determine the network reachability along a network path through different administrative domains. We have implemented and evaluated our protocol on both real and synthetic ACLs. The experimental results show that the online processing time of an ACL with thousands of rules is less than 25 seconds, the comparison time of two ACLs is less than 6 seconds, and the communication cost between two ACLs with thousands of rules is less than 2100 KB.

Firewalls have been widely deployed on the Internet for securing private networks. A firewall checks each incoming or outgoing packet to decide whether to accept or discard the packet based on its policy. Optimizing firewall policies is crucial for improving network performance. Prior work on firewall optimization focuses on either intra-firewall or inter-firewall optimization within one administrative domain where the privacy of firewall policies is not a concern. This paper explores inter-firewall optimization across administrative domains for the first time. The key technical challenge is that firewall policies cannot be shared across domains because a firewall policy contains confidential information and even potential security holes, which can be exploited by attackers. In this paper, we propose the first cross-domain privacy-preserving cooperative firewall policy optimization protocol. Specifically, for any two adjacent firewalls belonging to two different administrative domains, our protocol can identify in each firewall the rules that can be removed because of the other firewall. The optimization process involves cooperative computation between the two firewalls without any party disclosing its policy to the other. We implemented our protocol and conducted extensive experiments. The results on real firewall policies show that our protocol can remove as many as 49% of the rules in a firewall whereas the average is 19.4%. The communication cost is less than a few hundred KBs. Our protocol incurs no extra online packet processing overhead and the offline processing time is less than a few hundred seconds.

This paper presents a novel offset encoding scheme for memory-efficient IP address lookup, called Offset Encoded Trie (OET). Each node in the OET contains only a next hop bitmap and an offset value, without the child pointers and the next hop pointers. Each traversal node uses the next hop bitmap and the offset value as two offsets to determine the location address of the next node to be searched. The on-chip OET is searched to find the longest matching prefix, and then the prefix is used as a key to retrieve the corresponding next hop from an off-chip prefix hash table. Experiments on real IP forwarding tables show that the OET outperforms previous multi-bit trie schemes in terms of the memory consumption. The OET facilitates the far more effective use of on-chip memory for faster IP address lookup.

This paper addresses the problem of identifying the top-k information hubs in a social network. Identifying top-k information hubs is crucial for many applications such as advertising in social networks where advertisers are interested in identifying hubs to whom free samples can be given. Existing solutions are centralized and require time stamped information about pair-wise user interactions and can only be used by social network owners as only they have access to such data. Existing distributed and privacy preserving algorithms suffer from poor accuracy. In this paper, we propose a new algorithm to identify information hubs that preserves user privacy. The intuition is that highly connected users tend to have more interactions with their neighbors than less connected users. Our method can identify hubs without requiring a central entity to access the complete friendship graph. We achieve this by fully distributing the computation using the Kempe-McSherry algorithm to address user privacy concerns. To the best of our knowledge, the proposed algorithm represents an arguably first attempt that (1) uses friendship graphs (instead of interaction graphs), (2) employs a truly distributed method over friendship graphs, and (3) maintains user privacy by not requiring them to disclose their friend associations and interactions, for identifying information hubs in social networks. We evaluate the effectiveness of our proposed technique using a real-world Facebook data set containing about 3.1 million users and more than 23 million friendship links. The results of our experiments show that our algorithm is 50% more accurate than existing distributed algorithms. Results also show that the proposed algorithm can estimate the rank of the top-k information hubs users more accurately than existing approaches.

Firewalls are one of the essential security elements to enforce access policies in computer networks. Open network architecture, shared wireless medium, stringent resource constraints, and highly dynamic network topology impose a new set of challenges on deploying firewalls in a mobile wireless environment. The current state-of-the-art demands for self protection by personal (i.e. local) firewalls for each node; however, this requires that all unwanted traffic travels all the way to the node before it is discarded at the destination. This wastes considerable bandwidth and power of all of the nodes in a network with multi-hop routing, specially if a node is under a denial of service (DoS) attack. In this paper, we develop a novel distributed firewalling scheme for wireless networks in which nodes collaboratively perform packet filtering to address resource squandering. The proposed scheme introduces techniques to distribute discarding rules based on both proactive and reactive routing protocols. It also proposes efficient rule placement mechanisms to maximize the number of packets discarded remotely before they reach the destination and minimize the number of unwanted packet forwardings. The scheme is evaluated through various simulation scenarios. The simulation results show that by distributing only 1% of the rules, about 42% of the unwanted traffic is discarded before it reaches the destination, which significantly saves the network resources. Saving about 30% of the wasted bandwidth can be crucial for the performance of a wireless network.

Understanding Internet traffic dynamics in large cellular networks is important for network design, troubleshooting, performance evaluation, and optimization. In this paper, we present the results from our study, which is based upon a week-long aggregated flow level mobile device traffic data collected from a major cellular operator's core network. In this study, we measure and characterize the spatial and temporal dynamics of mobile Internet traffic. We distinguish our study from other related work by conducting the measurement at a larger scale and exploring mobile data traffic patterns along two new dimensions -- device types and applications that generate such traffic patterns. Based on the findings of our measurement analysis, we propose a Zipf-like model to capture the volume distribution of application traffic and a Markov model to capture the volume dynamics of aggregate Internet traffic. We further customize our models for different device types using an unsupervised clustering algorithm to improve prediction accuracy.

Most prior research on policies has focused on correctness. While correctness is an important issue, the adoption of policy-based computing may be limited if the resulting systems are not implemented efficiently and thus perform poorly. To increase the effectiveness and adoption of policy-based computing, in this paper, we propose fast policy evaluation algorithms that can be adapted to support various policy languages. In this paper, we focus on XACML policy evaluation because XACML has become the de facto standard for specifying access control policies, has been widely used on web servers, and is most complex among existing policy languages. We implemented our algorithms in a policy evaluation system called XEngine and conducted side-by-side comparison with Sun Policy Decision Point (PDP), the industrial standard for XACML policy evaluation. The results show that XEngine is orders of magnitude faster than Sun PDP. The performance difference grows almost linearly with the number of rules in an XACML policy. To our best knowledge, there is no prior work on improving XACML policy evaluation performance. This paper represents the first step in exploring this unknown space.

Several range reencoding schemes have been proposed to mitigate the effect of range expansion and the limitations of small capacity, large power consumption, and high heat generation of ternary content addressable memory (TCAM)-based packet classification systems. However, they all disregard the semantics of classifiers and therefore miss significant opportunities for space compression. In this paper, we propose new approaches to range reencoding by taking into account classifier semantics. Fundamentally different from prior work, we view reencoding as a topological transformation process from one colored hyperrectangle to another, where the color is the decision associated with a given packet. Stated another way, we reencode the entire classifier by considering the classifier's decisions rather than reencode only ranges in the classifier ignoring the classifier's decisions as prior work does. We present two orthogonal, yet composable, reencoding approaches: domain compression and prefix alignment. Our techniques significantly outperform all previous reencoding techniques. In comparison to prior art, our experimental results show that our techniques achieve at least five times more space reduction in terms of TCAM space for an encoded classifier and at least three times more space reduction in terms of TCAM space for a reencoded classifier and its transformers. This, in turn, leads to improved throughput and decreased power consumption.

The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol that connects autonomous systems (ASes). Despite its importance for the Internet infrastructure, BGP is vulnerable to a variety of attacks due to lack of security mechanisms in place. Many BGP security mechanisms have been proposed. However, none of them has been deployed because of either high cost or high complexity. The right trade-off between efficiency and security has been ever challenging. In this paper, we attempt to trade-off between efficiency and security by giving a little dose of trust to BGP routers. We present a new flexible threat model that assumes for any path of length h, at least one BGP router is trustworthy, where h is a parameter that can be tuned according to security requirements. Based on this threat model, we present two new symmetric key approaches to securing BGP: the centralized key distribution approach and the distributed key distribution approach. Comparing our approaches to the previous SBGP scheme, our centralized approach has a 98 percent improvement in signature verification. Our distributed approach has equivalent signature generation cost as in SBGP and an improvement of 98 percent in]signature verification. Comparing our approaches to the previous SPV scheme, our centralized approach has a 42 percent improvement in signature generation and a 96 percent improvement in signature verification. Our distributed approach has a 90 percent improvement on signature generation cost and a 95 percent improvement in signature verification cost. We also describe practical techniques for increasing the long-term security and collusion resistance of our key distribution protocols without increasing the signature generation and verification costs. By combining our approaches with previous public key approaches, it is possible to simultaneously provide an increased level of security and reduced computation cost.

The widely deployed Virtual Private Network (VPN) technology allows roaming users to build an encrypted tunnel to a VPN server, which, henceforth, allows roaming users to access some resources as if that computer were residing on their home organization's network. Although VPN technology is very useful, it imposes security threats on the remote network because its firewall does not know what traffic is flowing inside the VPN tunnel. To address this issue, we propose VGuard, a framework that allows a policy owner and a request owner to collaboratively determine whether the request satisfies the policy without the policy owner knowing the request and the request owner knowing the policy. We first present an efficient protocol, called Xhash, for oblivious comparison, which allows two parties, where each party has a number, to compare whether they have the same number, without disclosing their numbers to each other. Then, we present the VGuard framework that uses Xhash as the basic building block. The basic idea of VGuard is to first convert a firewall policy to nonoverlapping numerical rules and then use Xhash to check whether a request matches a rule. Comparing with the Cross-Domain Cooperative Firewall (CDCF) framework, which represents the state-of-the-art, VGuard is not only more secure but also orders of magnitude more efficient. On real-life firewall policies, for processing packets, our experimental results show that VGuard is three to four orders of magnitude faster than CDCF.

An access control list (ACL) provides security for a private network by controlling the flow of incoming and outgoing packets. Specifically, a network policy is created in the form of a sequence of (possibly conflicting) rules. Each packet is compared against this ACL, and the first rule that the packet matches defines the decision for that packet. The size of ACLs has been increasing rapidly due to the explosive growth of Internet-based applications and malicious attacks. This increase in size degrades network performance and increases management complexity. In this paper, we propose ACL Compressor, a framework that can significantly reduce the number of rules in an access control list while maintaining the same semantics. We make three major contributions. First, we propose an optimal solution using dynamic programming techniques for compressing one-dimensional range-based access control lists. Second, we present a systematic approach for compressing multidimensional access control lists. Last, we conducted extensive experiments to evaluate ACL Compressor. In terms of effectiveness, ACL Compressor achieves an average compression ratio of 50.22 percent on real-life rule sets. In terms of efficiency, ACL runs in seconds, even for large ACLs with thousands of rules.

Quantifying and querying network reachability is important for security monitoring and auditing as well as many aspects of network management such as troubleshooting, maintenance, and design. Although attempts to model network reachability have been made, feasible solutions to computing network reachability have remained unknown. In this paper, we propose a suite of algorithms for quantifying reachability based on network configurations (mainly ACLs) as well as solutions for querying network reachability. We present a comprehensive network reachability model that considers connectionless and connection-oriented transport protocols, stateless and stateful routers/firewalls, static and dynamic NAT, PAT, etc. We implemented the algorithms in our network reachability analysis tool called Quarnet and conducted experiments on a university network. Experimental results show that the offline computation of reachability matrices takes a few hours and the online processing of a reachability query takes 0.075 seconds on average.

The architecture of two-tiered sensor networks, where storage nodes serve as an intermediate tier between sensors and a sink for storing data and processing queries, has been widely adopted because of the benefits of power and storage saving for sensors as well as the efficiency of query processing. However, the importance of storage nodes also makes them attractive to attackers. In this paper, we propose SafeQ, a protocol that prevents attackers from gaining information from both sensor collected data and sink issued queries. SafeQ also allows a sink to detect compromised storage nodes when they misbehave. To preserve privacy, SafeQ uses a novel technique to encode both data and queries such that a storage node can correctly process encoded queries over encoded data without knowing their values. To preserve integrity, we propose a new data structure called neighborhood chains that allows a sink to verify whether the result of a query contains exactly the data items that satisfy the query. In addition, we propose a solution to adapt SafeQ for event-driven sensor networks.

Range queries based on L 1 distance are a common type of queries in multimedia databases containing feature vectors. We propose a novel approach that transforms the feature space into a new feature space such that range queries in the original space are mapped into equivalent box queries in the transformed space. Since box queries are axes aligned, there are several implementational advantages that can be exploited to speed up the retrieval of query results. For two dimensional data the transformation is precise. For greater than two dimensions we propose a space transformation scheme based on disjoint planer rotation, and along with pruning query box the results are precise. Experimental results with large synthetic databases and some real databases show the effectiveness of the proposed transformation scheme. These experimental results have been corroborated with appropriate mathematical models.

Abstract Radio frequency identification (RFID) tags are cheap, simple devices that can store unique identification information and perform simple computation to keep better inventory of packages. Because of this, they are intended to replace the barcodes for supply chain management in the near future. However, unlike barcodes, these tags have a longer range in which they are allowed to be scanned, subjecting them to unauthorized scanning by malicious readers and to various attacks, including cloning. Therefore, a security protocol for RFID tags is needed to ensure privacy and authentication between each tag and their reader. In order to accomplish this, in this paper, we propose RFIDGuard, a lightweight privacy and authentication protocol for passive RFID tags. This protocol requires little computation and achieves both privacy and authentication simultaneously. The lightweight and secure nature of our RFIDGuard protocol make it particularly suitable for supply chain management. Adaptation of our protocol can be used for other applications as well. Copyright © 2009 John Wiley & Sons, Ltd.

Packet classification is the core mechanism that enables many networking services on the Internet such as firewall packet filtering and traffic accounting. Using ternary content addressable memories (TCAMs) to perform high-speed packet classification has become the de facto standard in the industry. TCAMs classify packets in constant time by comparing a packet with all classification rules of ternary encoding in parallel. Despite their high speed, TCAMs suffer from the well-known interval expansion problem. As packet classification rules usually have fields specified as intervals, converting such rules to TCAM-compatible rules may result in an explosive increase in the number of rules. This is not a problem if TCAMs have large capacities. Unfortunately, TCAMs have very limited capacity, and more rules means more power consumption and more heat generation for TCAMs. Even worse, the number of rules in packet classifiers have been increasing rapidly with the growing number of services deployed on the Internet. In this paper, we propose to address the interval expansion problem of TCAMs by removing redundant rules in classifiers. This equivalent transformation can significantly reduce the number of TCAM entries needed by a classifier. Our experiments on real-life classifiers show an average reduction of 58.2 percent in the number of TCAM entries by removing redundant rules. Given the logical interleaving nature of packet filtering rules, identifying redundant rules in classifiers is by no means trivial, and to achieve the guarantee of no redundant rules in resulting classifiers is even more challenging. In this paper, for the first time, we give a necessary and sufficient condition for identifying all redundant rules in a classifier. Based on this condition, we categorize redundant rules into upward redundant rules and downward redundant rules. Second, we present two algorithms for detecting and removing the two types of redundant rules, respectively. Third, we formally prove that the resulting classifiers have no redundant rules after running the two algorithms. Last, we conduct extensive experiments on both real-life and synthetic classifiers. The experimental results show that our redundancy removal algorithms are both effective and efficient.

This paper concerns the fundamental problem of identifying the content nature of a flow, namely text, binary, or encrypted, for the first time. We propose Iustitia, a tool for identifying flow nature on the fly. The key observation behind Iustitia is that text flows have the lowest entropy and encrypted flows have the highest entropy, while the entropy of binary flows stands in between. The basic idea of Iustitia is to classify flows using machine learning techniques where a feature is the entropy of every certain number of consecutive bytes. The key features of Iustitia are high speed (10% of average packet inter-arrival time) and high accuracy (86%).

Ternary Content Addressable Memories (TCAMs) have become the de facto standard in industry for fast packet classification. Unfortunately, TCAMs have limitations of small capacity, high power consumption, high heat generation, and high cost. The well-known range expansion problem exacerbates these limitations as each classifier rule typically has to be converted to multiple TCAM rules. One method for coping with these limitations is to use compression schemes to reduce the number of TCAM rules required to represent a classifier. Unfortunately, all existing compression schemes only produce prefix classifiers. Thus, they all miss the compression opportunities created by non-prefix ternary classifiers.

Compromised sensor nodes may collude to segregate a specific region of the sensor network preventing event reporting packets in this region from reaching the basestation. Additionally, they can cause skepticism over all data collected. Identifying and segregating such compromised nodes while identifying the type of attack with a certain confidence is critical to the smooth functioning of a sensor network. Existing work specializes in preventing or identifying specific type of attack and lacks a unified architecture to identify multiple attack types. Camouflage Event Based Malicious Node Detection Architecture (CENDA) is a proactive architecture that uses camouflage events generated by mobile-nodes to detect malicious nodes while identifying the type of attack. We exploit the spatial and temporal information of camouflage event while analyzing the packets to identify malicious activity. We simulated CENDA to compare its performance with other techniques that provide protection against individual attack types and the results show marked improvement in malicious node detection while having significantly less false positives. Moreover, CENDA is able to identify the type of malicious activity and is flexible to be configured to include other attack types in future.

Firewalls are the mainstay of enterprise security and the most widely adopted technology for protecting private networks. Ensuring the correctness of firewall policies through testing is important. In firewall policy testing, test inputs are packets and test outputs are decisions. Packets with unexpected (expected) evaluated decisions are classified as failed (passed) tests. Given failed tests together with passed tests, policy testers need to debug the policy to detect fault locations (such as faulty rules). Such a process is often time-consuming.To help reduce effort on detecting fault locations, we propose an approach to reduce the number of rules for inspection based on information collected during evaluating failed tests. Our approach ranks the reduced rules to decide which rules should be inspected first. We performed experiments on applying our approach. The empirical results show that our approach can reduce 56% of rules that are required for inspection in fault localization.

Firewalls are crucial elements in network security, and have been widely deployed in most businesses and institutions for securing private networks. The function of a firewall is to examine each incoming and outgoing packet and decide whether to accept or to discard the packet based on its policy. Due to the lack of tools for analyzing firewall policies, most firewalls on the Internet have been plagued with policy errors. A firewall policy error either creates security holes that will allow malicious traffic to sneak into a private network or blocks legitimate traffic and disrupts normal business processes, which in turn could lead to irreparable, if not tragic, consequences. Because a firewall may have a large number of rules and the rules often conflict, understanding and analyzing the function of a firewall has been known to be notoriously difficult. An effective way to assist firewall administrators to understand and analyze the function of their firewalls is by issuing queries. An example of a firewall query is "Which computers in the private network can receive packets from a known malicious host in the outside Internet?rdquo Two problems need to be solved in order to make firewall queries practically useful: how to describe a firewall query and how to process a firewall query. In this paper, we first introduce a simple and effective SQL-like query language, called the Structured Firewall Query Language (SFQL), for describing firewall queries. Second, we give a theorem, called the Firewall Query Theorem, as the foundation for developing firewall query processing algorithms. Third, we present an efficient firewall query processing algorithm, which uses decision diagrams as its core data structure. Fourth, we propose methods for optimizing firewall query results. Finally, we present methods for performing the union, intersect, and minus operations on firewall query results. Our experimental results show that our firewall query processing algorithm is very efficient: it takes less than 10 milliseconds to process a query over a firewall that has up to 10,000 rules.

The private computer network of any large enterprise has tens, or even hundreds, of firewalls. These firewalls are placed at the entry points of the network (where the network is connected with the rest of the Internet), and at many chosen points within the network. The result is a complex firewall network that seems hard to understand or analyze. In this paper, we propose a method for verifying the correctness of firewall networks with tree topologies. Our method is based on identifying two types of properties of firewall trees: accept and discard properties. An accept (or discard) property of a firewall tree specifies a class of packets that should be accepted (or discarded, respectively) by the firewall tree. We present two algorithms that can be used to decide whether a given firewall tree satisfies a given, accept or discard, property of that tree.

Firewalls are the mainstay of enterprise security and the most widely adopted technology for protecting private networks. The quality of protection provided by a firewall directly depends on the quality of its policy (i.e., configuration). Due to the lack of tools for verifying firewall policies, most firewalls on the Internet have been plagued with policy errors. A firewall policy error either creates security holes that will allow malicious traffic to sneak into a private network or blocks legitimate traffic and disrupts normal business processes, which in turn could lead to irreparable, if not tragic, consequences. We propose a firewall verification tool in this paper. Our tool takes as input a firewall policy and a given property, then outputs whether the policy satisfies the property. Despite of the importance of verifying firewall policies, this problem has not been explored in previous work. Due to the complex nature of firewall policies, designing algorithms for such a verification tool is challenging. In this paper, we designed and implemented a verification algorithm using decision diagrams, and tested it on both real-life firewall policies and synthetic firewall policies of large sizes. The experimental results show that our algorithm is very efficient. In practice, our firewal verification algorithm can be used in the iterative process of firewall policy design, verification, and maintenance. Note that the firewall policy verification algorithm proposed in this paper is not limited to firewalls. Rather, they can be potentially applied to other rule- based systems as well.

Packet classification is the core mechanism that enables many networking services on the Internet such as firewall packet filtering and traffic accounting. Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. TCAMs classify packets in constant time by comparing a packet with all classification rules of ternary encoding in parallel. Despite their high speed, TCAMs suffer from the well-known interval expansion problem. As packet classification rules usually have fields specified as intervals, converting such rules to TCAM- compatible rules may result in an explosive increase in the number of rules. This is not a problem if TCAMs have large capacities. Unfortunately, TCAMs have very limited capacity, and more rules means more power consumption and more heat generation for TCAMs. Even worse, the number of rules in packet classifiers have been increasing rapidly with the growing number of services deployed on the internet. The interval expansion problem of TCAMs can be addressed by removing redundant rules in packet classifiers. This equivalent transformation can significantly reduce the number of TCAM entries needed by a packet classifier. Our experiments on real- life packet classifiers show an average reduction of 58.2% in the number of TCAM entries by removing redundant rules. We propose an all-match based complete redundancy removal algorithm. This is the first algorithm that attempts to solve first-match problems from an all-match perspective. We formally prove that our redundancy removal algorithm guarantees no redundant rules in resulting packet classifiers. We conducted extensive experiments on both real-life and synthetic packet classifiers. These experimental results show that our redundancy removal algorithm is both effective in terms of reducing TCAM entries and efficient in terms of running time.

A firewall is a security guard placed between a private network and the outside Internet that monitors all incoming and outgoing packets. The function of a firewall is to examine every packet and decide whether to accept or discard it based upon the firewall's policy. This policy is specified as a sequence of (possibly conflicting) rules. When a packet comes to a firewall, the firewall searches for the first rule that the packet matches, and executes the decision of that rule. With the explosive growth of Internet-based applications and malicious attacks, the number of rules in firewalls have been increasing rapidly, which consequently degrades network performance and throughput. In this paper, we propose Firewall Compressor, a framework that can significantly reduce the number of rules in a firewall while keeping the semantics of the firewall unchanged. We make three major contributions in this paper. First, we propose an optimal solution using dynamic programming techniques for compressing one-dimensional firewalls. Second, we present a systematic approach to compressing multi-dimensional firewalls. Last, we conducted extensive experiments to evaluate Firewall Compressor. In terms of effectiveness, Firewall Compressor achieves an average compression ratio of 52.3% on real- life rule sets. In terms of efficiency, Firewall Compressor runs in seconds even for a large firewall with thousands of rules. Moreover, the algorithms and techniques proposed in this paper are not limited to firewalls. Rather, they can be applied to other rule-based systems such as packet filters on Internet routers.

The widely deployed Virtual Private Network (VPN) technology allows roaming users to build an encrypted tunnel to a VPN server, which henceforth allows roaming users to access some resources as if that computer is residing on their home organization's network. Although the VPN technology is very useful, it imposes security threats to the remote network because their firewall does not know what traffic is flowing inside the VPN tunnel. To address this issue, we propose VGuard, a framework that allows a policy owner and a request owner to collaboratively determine whether the request satisfies the policy without the policy owner knowing the request and the request owner knowing the policy. We first present an efficient protocol, called Xhash, for oblivious comparison, which allows two parties, where each party has a number, to compare whether they have the same number, without disclosing their numbers to each other. Then, we present the VGuard framework that uses Xhash as the basic building block. The basic idea of VGuard is to first convert a firewall policy to non-overlapping numerical rules and then use Xhash to check whether a request matches a rule. Comparing with the Cross-Domain Cooperative Firewall (CDCF) framework, which represents the state-of-the-art, VGuard is not only more secure but also orders of magnitude more efficient. On real-life firewall policies, for processing packets, our experimental results show that VGuard is 552 times faster than CDCF on one party and 5035 times faster than CDCF on the other party.

XACML has become the de facto standard for specifying access control policies for various applications, especially web services. With the explosive growth of web applications deployed on the Internet, XACML policies grow rapidly in size and complexity, which leads to longer request processing time. This paper concerns the performance of request processing, which is a critical issue and so far has been overlooked by the research community. In this paper, we propose XEngine, a scheme for efficient XACML policy evaluation. XEngine first converts a textual XACML policy to a numerical policy. Second, it converts a numerical policy with complex structures to a numerical policy with a normalized structure. Third, it converts the normalized numerical policy to tree data structures for efficient processing of requests. To evaluate the performance of XEngine, we conducted extensive experiments on both real-life and synthetic XACML policies. The experimental results show that XEngine is orders of magnitude more efficient than Sun PDP, and the performance difference between XEngine and Sun PDP grows almost linearly with the number of rules in XACML policies. For XACML policies of small sizes (with hundreds of rules), XEngine is one to two orders of magnitude faster than the widely deployed Sun PDP. For XACML policies of large sizes (with thousands of rules), XEngine is three to four orders of magnitude faster than Sun PDP.

Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry because TCAMs enable constant time classification by comparing a packet with all rules of ternary encoding in parallel. However, TCAMs have limitations of small capacity, large power consumption and heat generation, and high hardware cost. Although a hardware solution to TCAM limitations is not impossible, TCAMs are unlikely to have hardware breakthroughs because they have pushed silicon to its limit. Furthermore, the number of rules in packet classifiers increases rapidly due to the explosive growth of services deployed on the Internet. In this paper, we propose three approaches, multi-lookup, pipelined-lookup, and packing. The central theme of these three approaches is to minimize the number of TCAM bits used to represent a packet classifier. Reducing TCAM space usage directly addresses the physical limitations of TCAMs. Smaller TCAM implies lower power consumption, less heat generation, less board space, and lower hardware cost. Furthermore, reducing the number of bits used in a TCAM leads to less power consumption and heat generation because the energy consumed by a TCAM grows linearly with the number of bits it uses in storing rules. Our approaches are based on three key observations. First, information stored in TCAMs tends to have high redundancy from an information theory perspective. Specifically, we observe that the same ternary string for a specific field may be repetitively stored in multiple TCAM entries. For example, in the simple two-dimensional packet classifier in Figure 1(a), the strings 001, 010, and 100 from the first

Firewalls are the mainstay of enterprise security and the most widely adopted technology for protecting private networks. As the quality of protection provided by a firewall directly depends on the quality of its policy (i.e., configuration), ensuring the correctness of security policies is important and yet difficult.To help ensure the correctness of a firewall policy, we propose a systematic structural testing approach for firewall policies. We define structural coverage (based on coverage criteria of rules, predicates, and clauses) on the policy under test. Considering achieving higher structural coverage effectively, we develop three automated packet generation techniques: the random packet generation, the one based on local constraint solving (considering individual rules locally in a policy), and the most sophisticated one based on global constraint solving (considering multiple rules globally in a policy).We have conducted an experiment on a set of real policies and a set of faulty policies to detect faults with generated packet sets. Generally, our experimental results show that a packet set with higher structural coverage has higher fault detection capability (i.e., detecting more injected faults). Our experimental results show that a reduced packet set (maintaining the same level of structural coverage with the corresponding original packet set) maintains similar fault detection capability with the original set.

Firewalls are the mainstay of enterprise security and the most widely adopted technology for protecting private networks. An error in a firewall policy either creates security holes that will allow malicious traffic to sneak into a private network or blocks legitimate traffic and disrupts normal business processes, which in turn could lead to irreparable, if not tragic, consequences. It has been observed that most firewall policies on the Internet are poorly designed and have many errors. Therefore, how to design firewall policies correctly is an important issue. In this paper, we propose the method of diverse firewall design, which consists of three phases: a design phase, a comparison phase, and a resolution phase. In the design phase, the same requirement specification of a firewall policy is given to multiple teams who proceed independently to design different versions of the firewall policy. In the comparison phase, the resulting multiple versions are compared with each other to detect all functional discrepancies between them. In the resolution phase, all discrepancies are resolved and a firewall that is agreed upon by all teams is generated.

Packet classification is the core mechanism that enables many networking services on the Internet such as firewall packet filtering and traffic accounting. Using ternary content addressable memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. TCAMs classify packets in constant time by comparing a packet with all classification rules of ternary encoding in parallel. Despite their high speed, TCAMs suffer from the well-known range expansion problem. As packet classification rules usually have fields specified as ranges, converting such rules to TCAM-compatible rules may result in an explosive increase in the number of rules. This is not a problem if TCAMs have large capacities. Unfortunately, TCAMs have very limited capacity, and more rules means more power consumption and more heat generation for TCAMs. Even worse, the number of rules in packet classifiers have been increasing rapidly with the growing number of services deployed on the internet. To address the range expansion problem of TCAMs, we consider the following problem: given a packet classifier, how can we generate another semantically equivalent packet classifier that requires the least number of TCAM entries? In this paper, we propose a systematic approach, the TCAM Razor, that is effective, efficient, and practical. In terms of effectiveness, our TCAM Razor prototype achieves a total compression ratio of 3.9%, which is significantly better than the previously published best result of 54%. In terms of efficiency, our TCAM Razor prototype runs in seconds, even for large packet classifiers. Finally, in terms of practicality, our TCAM Razor approach can be easily deployed as it does not require any modification to existing packet classification systems, unlike many previous range expansion solutions.

Capturing an E-mail worm and containing its propagation as early as possible is desirable in order to provide better protection for the networks and hosts against severe damage that may be caused by the worm. In this paper, we propose a new approach that makes use of the propagating nature of E-mail worms. This approach inserts into each client's address book a dummy E-mail address that is not used by any registered user of the local domain, such that we can be confident that any E-mail destined to this dummy E-mail address is generated by an E-mail worm. The captured signatures can then be used to construct a user blacklist and a signature blacklist to contain the propagation of this E-mail worm. We also discuss how E-mail worms can attempt to bypass the dummy E-mail address, and propose countermeasures against these attempts. Our prototype implementation shows that this approach is easily deployable and is effective in containing E-mail worms

We propose the first model of stateful firewalls. In this model, each stateful firewall has a variable set called the state of the firewall, which is used to store some packets that the firewall has accepted previously and needs to remember in the near future. Each stateful firewall consists of two sections: a stateful section and a stateless section. Upon receiving a packet, the firewall processes it in two steps. In the first step, the firewall augments the packet with an additional field called the tag, and uses the stateful section to compute the value of this field according to the current state of the firewall. In the second step, the firewall compares the packet together with its tag value against a sequence of rules in the stateless section to identify the first rule that the packet matches: the decision of this rule determines the fate of the packet. Our model of stateful firewalls has several favorable properties. First, despite its simplicity, it can express a variety of state tracking functionalities. Second, it allows us to inherit the rich results in stateless firewall design and analysis. Third, it provides backward compatibility such that a stateless firewall can also be specified using our model. This paper goes beyond proposing this stateful firewall model itself. A significant portion of this paper is devoted to analyzing the properties of stateful firewalls that are specified using our model. We outline a method for verifying whether a firewall is truly stateful. The method is based on the three properties of firewalls: conforming, grounded, and proper. We show that if a firewall satisfies these three properties, then the firewall is truly stateful.

Cookies are the primary means for Web applications to authenticate HTTP requests and to maintain client states. Many Web applications (such as electronic commerce) demand a secure cookie protocol. Such a protocol needs to provide the following four services: authentication, confidentiality, integrity and antireplay. Several secure cookie protocols have been proposed in previous literature; however, none of them are completely satisfactory. In this paper, we propose a secure cookie protocol that is effective, efficient, and easy to deploy. In terms of effectiveness, our protocol provides all of the above four security services. In terms of efficiency, our protocol does not involve any database lookup or public key cryptography. In terms of deployability, our protocol can be easily deployed on an existing Web server, and it does not require any change to the Internet cookie specification. We implemented our secure cookie protocol using PHP, and the experimental results show that our protocol is very efficient.

Firewalls are safety-critical systems that secure most private networks. An error in a firewall either leaks secret information from its network or disrupts legitimate communication between its network and the rest of the Internet. How to design a correct firewall is therefore an important issue. In this paper, we propose the method of diverse firewall design, which is inspired by the well-known method of design diversity for building fault-tolerant software. Our method consists of two phases: a design phase and a comparison phase. In the design phase, the same requirement specification of a firewall is given to multiple teams who proceed independently to design different versions of the firewall. In the comparison phase, the resulting multiple versions are compared with each other to find out all the discrepancies between them, then each discrepancy is further investigated and a correction is applied if necessary. The technical challenge in the method of diverse firewall design is how to discover all the discrepancies between two given firewalls. We present a series of three efficient algorithms for solving this problem: (I) a construction algorithm for constructing an equivalent ordered firewall decision diagram from a sequence of rules, (2) a shaping algorithm for transforming two ordered firewall decision diagrams to become semi-isomorphic without changing their semantics, and (3) a comparison algorithm for detecting all the discrepancies between two semi-isomorphic firewall decision diagrams.

In this paper, we investigate the security of micropayment protocols that support low-value transactions. We focus on one type of such protocols that are based on hash chains. We present a formal specification of a typical hash chain based micropayment protocol using abstract protocol notation, and discuss how an adversary can attack this protocol using message loss, modification, and replay. We use convergence theory to show that this protocol is secure against these attacks. The specification and verification techniques used in this paper can be applied to other micropayment protocols as well

A firewall is often placed at the entrance of each private network in the Internet. The function of a firewall is to examine each packet that passes through the entrance and decide whether to accept the packet and allow it to proceed or to discard the packet. A firewall is usually designed as a sequence of rules. To make a decision concerning some packets, the firewall rules are compared, one by one, with the packet until one rule is found to be satisfied by the packet: this rule determines the fate of the packet. We present the first ever method for designing the sequence of rules in a firewall to be consistent, complete, and compact. Consistency means that the rules are ordered correctly, completeness means that every packet satisfies at least one rule in the firewall, and compactness means that the firewall has no redundant rules. Our method starts by designing a firewall decision diagram (FDD, for short) whose consistency and completeness can be checked systematically (by an algorithm). We then apply a sequence of five algorithms to this FDD to generate, reduce and simplify the target firewall rules while maintaining the consistency and completeness of the original FDD.