Node-centric Data Centers (NDCs) are highly flexible, cost-efficient, and failure-resilient, and have gained growing popularity in recent years. However, RDMA technology used in NDC still faces challenges, including high retransmission overhead, Head-of-Line Blocking (HoLB) and deadlock problems. Existing solutions for traditional data centers cannot simultaneously address these issues due to the unique topology and server transmission characteristics of NDC. In this paper, we propose a per-port flow control named PortFC for NDC. PortFC addresses the above problems through the designs of a Pause/Resume control signal, a per-port queue allocation method, an egress-detecting per-port flow control mechanism, and a server-aware queue scheduling method. Our evaluation shows that PortFC is free from retransmission, capable of eliminating HoLB and avoiding deadlocks. PortFC achieves 1.7-8.0 times higher throughput and reduces latency by 11.7%-87.7% compared to the state-of-the-art lossy RDMA based on IRN and the lossless RDMA method based on PFC. In particular, PortFC still demonstrates good performance in a Rail-only NDC with heterogeneous bandwidth domains.

BCube is a modular data center network.Compared with other topologies, BCube has natural advantages, such as lower deployment costs and stronger failure recovery capabilities.However, RDMA technology used in BCube still faces challenges, including high retransmission overhead, Head-of-Line Blocking (HoLB) and deadlock problems.Existing solutions for traditional data centers cannot simultaneously address these issues due to the unique topology and server transmission characteristics of BCube.In this paper, we propose a per-port flow control named PortFC for BCube.PortFC addresses the above problems through the designs of a Pause/Resume control signal, a per-port queue allocation method, an egress-detecting per-port flow control mechanism, and a serveraware queue scheduling method.Our evaluation shows that PortFC is free from retransmission, capable of eliminating HoLB and avoiding deadlocks.PortFC achieves 1.7-8.0times higher throughput and reduces latency by 11.7%-87.7%compared to the state-of-the-art

Finding special items in data streams, like heavy hitters, top-$k$items, and persistent items, has always been a hot topic in the field of network measurement. While data streams nowadays are usually high-dimensional, most prior works optimize data structures to accurately find special items according to a certain primary dimension and yield little insight into the correlations between dimensions, where the dimension can be a single data dimension or a combination of multiple data dimensions. Therefore, we propose to find special quadratic elements in data streams to reveal the close correlations between the primary and secondary dimensions. Here, both the primary and secondary dimensions are selected according to specific application purposes. Based on the special items mentioned above, we extend our problem to three applications related to heavy hitters, top-$k$, and persistent items, and design a generic framework DUET to process them. We analyze the error bound of our algorithm theoretically and conduct extensive experiments on four publicly available data sets. Our experimental results show that DUET can achieve 3.5 times higher throughput and three orders of magnitude lower average relative error than cutting-edge algorithms. Moreover, we propose an optimized framework based on DUET, namely O-DUET, to further improve the estimation accuracy. We also discuss a hardware-version DUET and deploy it on Tofino.

Finding special items, like heavy hitters, top-k, and persistent items, has always been a hot issue in data stream processing for web analysis. While data streams nowadays are usually high-dimensional, most prior works focus on special items according to a certain primary dimension and yield little insight into the correlations between dimensions. Therefore, we propose to find special quadratic elements to reveal close correlations. Based on the items mentioned above, we extend our problem to three applications related to heavy hitters, top-k, and persistent items, and design a generic framework DUET to process them. Besides, we analyze the error bound of our algorithm and conduct extensive experiments on four data sets. Our experimental results show that DUET can achieve 3.5 times higher throughput and three orders of magnitude lower average relative error compared with cutting-edge algorithms.

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 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.

The problem of multi-armed bandit (MAB) with fairness constraint has emerged as an important research topic recently. For such problems, one common objective is to maximize the total rewards within a fixed round of pulls, while satisfying the fairness requirement of a minimum selection fraction for each individual arm in the long run. Previous works have made substantial advancements in designing efficient online selection solutions, however, they fail to achieve a sublinear regret bound when incorporating such fairness constraints. In this paper, we study a combinatorial MAB problem with concave objective and fairness constraints. In particular, we adopt a new approach that combines online convex optimization with bandit methods to design selection algorithms. Our algorithm is computationally efficient, and more importantly, manages to achieve a sublinear regret bound with probability guarantees. Finally, we evaluate the performance of our algorithm via extensive simulations and demonstrate that it outperforms the baselines substantially.

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.

Software-Defined Networks (SDNs) introduce great flexibilities in how packet routes can be defined and changed over time, and enable a more fine-grained and adaptive traffic engineering. The recently introduced support for more accurate synchronization in SDNs further improves the degree of control an operator can have over the packets' forwarding paths, and also allows to avoid disruptions and inconsistencies during network updates, i.e., during the rerouting of flows. However, how to optimally exploit such technology algorithmically - to efficiently schedule the update of multiple flows in such timed SDNs - while accounting for possible interference and congestion, is not well-understood today. We, in this paper, initiate the study of the fundamental problem of how to reroute the updates of multiple network flows in a synchronized SDN in a congestion-free manner. We rigorously prove that the problem is NP-hard for flows of unit size and network links with unit delay. We also show that a greedy approach to update the network can delay the update significantly. Our main contribution is the first solution to this problem: Chronicle. Our approach is based on time-extended network construction and the resource dependency graph, which is implemented by Openflow 1.5 using the scheduled bundles feature. The evaluation results show that Chronicle can reduce the makespan by 63% and reduce the number of changed rules by 50% compared to state-of-the-art.

Broadcast authentication is an important problem in several network settings such as wireless sensor networks and ad-hoc networks. We focus on the problem of independent key distribution protocols, which use efficient symmetric key signatures in distributed systems to permit (local) broadcast authentication. We focus on five types of communication graphs: (1) star, (2) acyclic, (3) planar, (4) complete bipartite, and (5) fully connected graphs. A star graph is the simplest network topology where a central node is transmitting authenticated broadcast messages to several satellite nodes. For star graphs, we show that as n, the number of satellite nodes in the star network, tends to infinity, it suffices to maintain logn+1/2loglogn + 1 keys at the center node, but logn+1/2loglogn keys do not suffice. We establish that this is the optimal lower bound on the number of keys for a star graph. Building on this result, we describe storage efficient key distribution for acyclic, planar, and complete bipartite graphs, when compared to existing key distribution schemes. We extend our scheme for fully connected graphs and show that it is sufficient to store O(c log2 N) keys per node where c<1. We perform a detailed analysis of collusion resistance of our protocols and show the trade-offs against internal and external attacks depending on the size of storage. Finally, we demonstrate the practical applicability of our protocols for wireless sensor networks.

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).

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.

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.

For fast packet classification, the de-facto industry standard is to use Ternary Content Addressable Memory (TCAM) chips where each chip stores one classifier rule and a given packet is checked against all such rules in parallel. In spite of the TCAM advantages, for a large number of rules, the TCAM deployment becomes expensive and the power consumption increases significantly. Therefore, it is desirable to reduce the number of TCAM rules while retaining the original classification semantics. In this work, we present efficient graph-based algorithms and data structures that allow us to capture the rule ordering relationships and iteratively compress the TCAM rules. Through extensive experiments, we show that our algorithm achieves 75% reduction of firewall rule sets on an average and even achieves an additional 24% compression on the output rule set of the state-of-the-art solutions.

Software-Defined Networks (SDN) is a trend of research in networks. Rule placement, a common operation for network administrators, has become more complicated due to the capacity limitation of devices in which the large number of rules are deployed. Prior works on rule placement mostly consider the influence on rule placement incurred by the rules in a single device. However, the position relationships between neighbor devices have influences on rule placement. Our basic idea is to classify the position relationships into two categories: the serial relationship and the parallel relationship, and we present a novel strategy for rule placement based on the two different position relationships. There are two challenges of implementing our strategies: to check whether a rule is contained by a rule set or not and to check whether a rule can be merged by other rules or not.To overcome the challenges, we propose a novel data structure called OPTree to represent the rules, which is convenient to check whether a rule is covered by other rules. We design the insertion algorithm and search algorithm for OPTree. Extensive experiments show that our approach can effectively reduce the number of rules while ensuring placed rules work. On the other hand, the experimental results also demonstrate that it is necessary to consider the position relationships between neighbor devices when placing rules.

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.

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.

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.

Storage nodes in two-tiered sensor networks are responsible for storing sensor-collected data and processing the sink-issued queries. Therefore, storage nodes are vulnerable to attack because of their importance. In this paper, we propose a privacy and integrity preserving protocol called SSQ, which is able to prevent compromised storage nodes from leaking sensitive data and allows the sink to detect the misbehaviors of compromised storage nodes. For privacy preserving, a size-limited bucketing technique is proposed to mix the data in a range, and a prefix membership verification technique based on Bloom filters is developed to perform skyline queries on encrypted data items. For integrity preserving, a Merkle hash tree-based technique is investigated to prevent compromised storage nodes from tampering and dropping data. Detailed performance evaluations confirm the high efficacy and efficiency of SSQ. Copyright © 2013 John Wiley & Sons, Ltd.

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.