Widespread event detection is a fundamental network function that has many important applications in cybersecurity, traffic engineering, and distributed data mining. This paper introduces a new probabilistic threshold-based event detection problem, which is to find all events that appear in any w-out-of-a monitors with probabilistic guarantee on false positives, where a is the total number of monitors and the threshold w(≤ a) is a positive integer parameter that can be arbitrarily set, according to specific application requirements. We develop an efficient threshold filter solution and its improved versions, which combine Bloom filters, counting Bloom filter, threshold filter and compressed filters in a series of encoding and filtering steps, providing tradeoff between detection accuracy and communication overhead. We theoretically optimize the system parameters in the proposed solutions to minimize the communication overhead under the constraint of probabilistic detection guarantee. Extensive simulations demonstrate the practical viability of the proposed solutions in their ability of finding widespread events in a large network with few false positives and low communication overhead.

Measuring traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problem of persistent traffic measurement, which was not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose three estimators for privacy-preserving persistent traffic measurement: one for point traffic, one for point-to-point traffic, and another for three-point traffic. After that, we present a general framework to measure persistent traffic that go through more than three locations. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

Per-flow traffic measurement is a fundamental problem in the era of big network data, and has been widely used in many applications, including capacity planning, anomaly detection, load balancing, traffic engineering, etc. In order to keep up with the line speed of modern network devices (e.g., routers), per-flow measurement online module is often implemented by using on-chip cache memory (such as SRAM) to minimize per-packet processing time, but on-chip SRAM is expensive and limited in size, which poses a major challenge for traffic measurement. In response, much recent research is geared towards designing highly compact data structures for approximate estimation that can provide probabilistic guarantees for per-flow measurement. The state of art, called Counter Tree (CT), requires at least 2 bits per flow in memory consumption and more than 2 memory accesses per packet in processing time. In this paper, we propose a novel design of a highly compact and efficient counter architecture, called Virtual Active Counter estimation (VAC), which achieves faster processing speed (slightly more than 1 memory access per packet on average) and provides more accurate measurement results than CT under the same allocated memory. Moreover, VAC can perform well even with a very tight memory space (less than 1 bit per flow or even one fifth of a bit per flow). Theoretical analysis and experiments based on real network traces demonstrate the superior performance of VAC.

Measuring point traffic volume and point-to-point traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problems of persistent point traffic measurement and persistent point-to-point traffic measurement, which were not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose two novel estimators for privacy-preserving persistent traffic measurement: one for point traffic and the other for point-to-point traffic. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

Thanks to the proliferation of Internet access and modern digital and mobile devices, online survey has been flourishing into data collection of marketing, social, financial and medical studies. However, traditional data collection methods in online survey suffer from serious privacy issues. Existing privacy protection techniques are not adequate for online survey for lack of strong privacy. In this paper, we propose a practical strong privacy online survey scheme SPS based on a novel data collection technique called dual matrix masking (DM2), which guarantees the correctness of the tallying results with low computation overhead, and achieves universal verifiability, robustness and strong privacy. We also propose a more robust scheme RSPS, which incorporates multiple distributed survey managers. The RSPS scheme preserves the nice properties of SPS, and further achieves robust strong privacy against joint collusion attack. Through extensive analyses, we demonstrate our proposed schemes can be efficiently applied to online survey with accuracy and strong privacy.

Per-flow counting for big network data streams is a fundamental problem in various network applications such as traffic monitoring, load balancing, capacity planning, etc. Traditional research focused on designing compact data structures to estimate flow sizes from the beginning of the data stream (i.e., landmark window model). However, for many applications, the most recent elements of a stream are more significant than those arrived long time ago, which gives rise to the sliding window model. In this paper, we consider per-flow counting over the sliding window model, and propose two novel solutions, ACE and S-ACE. Instead of allocating a separate data structure for each flow, both solutions utilize the counter sharing idea to reduce memory footprint, so they can be implemented in on-chip SRAMs in modern routers to keep up with the line speed. ACE has to reset the sliding window periodically to give precise estimates, while S-ACE based on a novel segment design can achieve persistently accurate estimates. Our extensive simulations as well as experimental evaluations based on real network traffic trace demonstrate that S-ACE can achieve fast processing speed and high measurement accuracy even with a very tight memory.

Radio frequency identification (RFID) technology has been widely used in Applications, such as inventory control, object tracking, and supply chain management. In this domain, an important research problem is called RFID cardinality estimation, which focuses on estimating the number of tags in a certain area covered by one or multiple readers. This paper extends the research in both temporal and spatial dimensions to provide much richer information about the dynamics of distributed RFID systems. Specifically, we focus on estimating the cardinalities of the intersection/differences/union of two arbitrary tag sets (called joint properties for short) that exist in different spatial or temporal domains. With many practical applications, there is, however, little prior work on this problem. We will propose a joint RFID estimation protocol that supports adaptive snapshot construction. Given the snapshots of any two tag sets, although their lengths may be very different depending on the sizes of tag sets they encode, we design a way to combine their information and more importantly, derive closed-form formulas to use the combined information and estimate the joint properties of the two tag sets, with an accuracy that can be arbitrarily set. By formal analysis, we also determine the optimal system parameters that minimize the execution time of taking snapshots, under the constraints of a given accuracy requirement. We have performed extensive simulations, and the results show that our protocol can reduce the execution time by multiple folds, as compared with the best alternative approach in literature.

Thanks to the Internet, voters can cast their ballots over the electronic voting (E-voting) systems conveniently and efficiently without going to the polling stations. However, existing E-voting protocols suffer from anonymity issues and/or high deployment overhead. In this paper, we design a practical anonymous E-voting protocol (referred to as MVP) based on a novel data collection technique called dual random matrix masking (DRMM), which guarantees anonymity with low overhead of computation, and achieves the security goals of receipt-freeness, double voting detection, fairness, ballot secrecy, and integrity. Through extensive analyses on correctness, efficiency, and security properties, we demonstrate our proposed MVP protocol can be applied to E-voting in a variety of situations with accuracy and anonymity.

Per-flow traffic measurement is a fundamental problem in the era of big network data, providing critical information for many practical applications including capacity planning, traffic engineering, data accounting, resource management, and scan/intrusion detection in modern computer networks. It is challenging to design highly compact data structures for approximate per-flow measurements. In this paper, we show that a highly compact virtual counter architecture can achieve fast processing speed (slightly more than 1 memory access per packet) and provide accurate measurement results under tight memory allocation. Extensive experiments based on real network trace data demonstrate its superior performance over the best existing work.

In this paper, we consider an important problem of privacy-preserving point-to-point traffic volume measurement in vehicular cyber physical systems (VCPS), whose focus is utilizing VCPS to enable automatic traffic data collection, and measuring point-to-point traffic volume while preserving the location privacy of all participating vehicles. The novel scheme that we propose tackles the efficiency, privacy, and accuracy problems encountered by previous solutions. Its applicability is demonstrated through both mathematical and numerical analysis. The simulation results also show its superior performance.

Radio-frequency identification (RFID) technology has been widely used in applications such as inventory control, object tracking, supply chain management. An important research is to estimate the number of tags in a certain area covered by readers. This paper extends the research in both temporal and spatial dimensions to provide much richer information for monitoring the dynamics of distributed RFID systems. More specifically, we are interested in estimating the joint properties of any two snapshots taken at arbitrary locations and arbitrary times in a system. With many practical applications, there is however little prior work on this problem. We propose a joint RFID estimation protocol based on a simple yet versatile snapshot construction. Given the snapshots of any two tag sets, although their sizes may be very different, we design a way to combine their information and more importantly derive formulas to extract the joint properties of the two tag sets from the combined information, with an accuracy that can be arbitrarily set. Through formal analysis, we determine the optimal system parameters that minimize the execution time of taking snapshots, under the constraints of a given accuracy requirement. Our simulation results show that the proposed protocol can reduce the execution time by multifold when comparing with the best alternative approach in the literature.

Data security is a major concern in cloud computing. After clients outsource their data to the cloud, will they lose control of the data? Prior research has proposed various schemes for clients to confirm the existence of their data on the cloud servers, and the goal is to ensure data integrity. This paper investigates a complementary problem: When clients delete data, how can they be sure that the deleted data will never resurface in the future if the clients do not perform the actual data removal themselves? How to confirm the non-existence of their data when the data is not in their possession? One obvious solution is to encrypt the outsourced data, but this solution has a significant technical challenge because a huge amount of key materials may have to be maintained if we allow fine-grained deletion. In this paper, we explore the feasibility of relieving clients from such a burden by outsourcing keys (after encryption) to the cloud. We propose a novel multi-layered key structure, called Recursively Encrypted Red-black Key tree (RERK), that ensures no key materials will be leaked, yet the client is able to manipulate keys by performing tree operations in collaboration with the servers. We implement our solution on the Amazon EC2. The experimental results show that our solution can efficiently support the deletion of outsourced data in cloud computing.

After clients outsource their data to the cloud, they will lose physical control of their data. Many schemes are proposed for clients to verify the integrity of their data. This paper considers a complementary problem: When a client claims that the server has lost their data, how can we be sure that the client is correct and honest about the loss? It is possible that the client's meta data is corrupted or the client is lying in order to blackmail the server. In addition, most previous work relies on sequential indices. However, the indices bring significant overhead to bind an index to each block. We propose to replace sequential indices with much flexible non-sequential {\it coordinates}. The binding of coordinates to data blocks is performed through a Coordinate Merkle Hash Tree (CMHT). Based on CMHT, we can improve both the average and the worst-case update overhead by simplifying the updating algorithm.

Cloud storage has been gaining popularity because its elasticity and pay-as-you-go manner. However, this new type of storage model also brings security challenges. This paper studies the problem of ensuring data integrity in cloud storage. In the Proof of Retrievability (PoR) model, after outsourcing the preprocessed data to the server, the client will delete its local copies and only store a small amount of meta data. Later the client will ask the server to provide a proof that its data can be retrieved correctly. However, most of the prior PoR works apply only to static data. The existing dynamic version of PoR scheme has an efficiency problem. In this paper, we extend the static PoR scheme to dynamic scenario. That is, the client can perform update operations, e.g., insertion, deletion and modification. After each update, the client can still detect the data losses even if the server tries to hide them. We develop a new version of authenticated data structure based on a B+ tree and a merkle hash tree. We call it Cloud Merkle B+ tree (CMBT). By combining the CMBT with the BLS signature, we propose a dynamic version of PoR scheme. Compared with the existing dynamic PoR scheme, our worst case communication complexity is O(logn) instead of O(n).