Network traffic anomaly detection is critical for advanced network applications. However, network traffic monitoring data arrive in a streaming fashion and could be infinite, which makes the offline algorithms that attempt to store the entire stream monitoring data for analysis not scalable. To well utilize the strong ability of tensor model, we use a tensor to represent the prior non-anomalous traffic matrices and propose a novel unsupervised anomaly detection framework that can be used to detect anomalies in a streaming fashion by making only one pass over the data while utilizing limited storage. In the framework, we propose a succinct tensor sketch to maintain, in a streaming model, the subspace that can well represent all prior non-anomalous data detected. Using the subspace, anomalies in each new incoming traffic monitoring data can be quickly detected based on a simple outlier score calculation. Further, we prove that the tensor sketch is mergeable. Exploiting this property, we propose a distributed anomaly detection framework in which the distributed node only needs to upload its succinct tensor sketch instead of the raw monitoring data to the central node to calculate the global subspace of the whole network, which greatly saves the transmission cost. We theoretically prove that our tensor sketch based anomaly detection algorithm compares favorably with the offline approach which calculates the subspace based on expensive global Singular Value Decomposition (SVD). The experimental results demonstrate the effectiveness and efficiency of our approach over other popular online anomaly detection algorithms.

Multi-set membership query is a fundamental issue for network functions such as packet processing and state machines monitoring. Given the rigid query speed and memory requirements, it would be promising if a multi-set query algorithm can be designed based on Bloom filter (BF), a space-efficient probabilistic data structure. However, existing efforts on multi-set query based on BF suffer from at least one of the following drawbacks: low query speed, low query accuracy, limitation in only supporting insertion and query operations, or limitation in the set size. To address the issues, we design a novel B h sequence-based Bloom filter (B h BF) for multi-set query, which supports four operations: insertion, query, deletion, and update. In B h BF, the set ID is encoded as a code in a B h sequence. Exploiting good properties of B h sequences, we can correctly decode the BF cells to obtain the set IDs even when the number of hash collisions is high, which brings high query accuracy. In B h BF, we propose two strategies to further speed up the query speed and increase the query accuracy. On the theoretical side, we analyze the false positive and classification failure rate of our B h BF. Our results from extensive experiments over two real datasets demonstrate that B h BF significantly advances state-of-the-art multi-set query algorithms.

With the prevalence of cloud computing, a growing number of users are delegating clouds to host their sensitive data. To preserve user privacy, it is suggested that data is encrypted before outsourcing. However, data encryption makes keyword-based searches over ciphertexts extremely difficult. This is even challenging forfuzzy searchthat allows uncertainties or misspellings of keywords in a query. In this article, we propose a prime inner product encoding (PIPE) scheme, which makes use of theindecomposableproperty of prime numbers to provide efficient, highly accurate, and flexible multi-keyword fuzzy search. Our main idea is to encode either a query keyword or an index keyword into a vector filled with primes or reciprocals of primes, such that the result of vectors’ inner product is an integer only when two keywords are similar. Specifically, we first construct$\text{PIPE}_{0}$that is secure in the known ciphertext model. Unlike existing works that have difficulty supporting AND and OR semantics simultaneously,$\text{PIPE}_{0}$gives users the flexibility to specify different search semantics in their queries. Then, we construct$\text{PIPE}_{\text{S}}$that subtly adds random noises to a query vector to resist linear analyses. Both theoretical analyses and experiment results demonstrate the effectiveness of our scheme.