To enable parallel transaction processing in blockchain systems, recent consensus protocols have adopted directed acyclic graph (DAG) structures where DAG is used to organize and parallelize the blocks. Unfortunately, these protocols suffer from high communication overhead. Our experiment on the state-of-the-art Graded DAG[12] reveals that dissemination of transaction and consensus vote messages account for the majority of network traffic. We analyze that the overall overhead is O (N2) per replica and O (N3) for the entire system, where N is the number of replicas, and note that existing approaches have not succeeded in reducing this overhead.

Public availability of data about the supply and utilization of Dockless Electric Scooters (DESs) is needed to develop smart mobility applications to promote the use of sustainable, shared, and equitable transportation. Prior studies have analyzed some attributes of DES usage, but they are limited in three aspects. 1) Data collection methods: Prior studies relied on DES providers to provide usage data to authors. Unfortunately, convincing DES providers to provide complete usage data is extremely hard, if not impossible. Thus, this approach is not scalable and further limits the ability to study DES usage trends only in the regions and only at the times for which the DES providers provide the data. 2) Global DES usage analysis: Prior studies have not analyzed how DES usage varies in different parts of the world. 3) Aspects of the usage analysis: Prior studies have not analyzed important DES usage attributes such as the availability of DES in minority-concentrated areas, temporal trends of DES trips from different types of locations, etc. This paper fills the gap in prior work by addressing these three limitations. For data collection methods, we present novel techniques to continuously collect DES usage data in any city worldwide without relying on DES providers. For global DES usage analysis, we study the spatiotemporal DES usage trends of 12 DES providers in 11 cities worldwide. For the aspects of the usage analysis, we provide extensive analysis of various aspects of DES usage that have previously either never been studied or studied only briefly. These aspects include DES supply trends, competition among providers, supply and trip hotspots, equitable DES availability, and so on. The methods and findings that we present in this paper aid in understanding DES usage across the world and offer actionable insights to DES stakeholders.

In this paper, we propose FreeMap, an approach that uses RF signals to generate accurate indoor maps of the line of sight as well as the non line of sight parts of buildings. To generate the maps, FreeMap leverages the movements of occupants in buildings. When an RF signal reflects from an occupant, the reflected signal arrives back at the receiver both directly and as multipaths, i.e., the copies of the signal that reflect from further walls before arriving back at the receiver. These direct and multipath reflections form a triangular geometry that enables FreeMap to locate various parts of the walls in the environment. As time progresses and the occupants move around, FreeMap localizes more and more parts of all the walls. It eventually obtains the locations of enough parts of all the walls that it can then connect them together to generate the indoor map. We have implemented FreeMap using a commercial FMCW radar (which provides in-home monitoring services to elderly) and have extensively evaluated it at eight measurement sites. Our results show that FreeMap generated maps with average precision, recall, and positioning error of $\mathbf{9 7 . 3 \%}, \mathbf{9 5 . 5 \%}$, and $20.3 \mathrm{~cm}$, respectively.

Usage data on Dockless Electric Scooters (DES) is crucial for developing policies and mobility applications to support shared transportation by understanding their supply and utilization. However, such data is not publicly available and prior DES studies relied on DES providers for the provision of usage data, which is often incomplete and difficult to obtain. This limits the ability to audit these datasets and study DES usage trends globally and over time. This paper addresses these limitations by introducing scalable methods to continuously collect DES data globally without relying on providers. We collect DES usage trends from 12 providers across 11 cities worldwide and examine supply and utilization trends and provider competition in this study.

This paper addresses the fundamental problem of per-flow loss measurement: for any flow passing through two observation points, estimate the number of packets that leave the first observation point but do not arrive at the second. To the best of our knowledge, there is no prior work on per-flow loss measurement. In this paper, we propose the first per-flow packet loss measurement scheme called FLOE. Given a set of observation points, FLOE records information about size of each flow at each point so that later it can accurately estimate the number of lost packets of any flow between any two points. The key idea is to record information about the size of each flow at a set of observation points, during which noise is carefully introduced so that storage space can be minimized and the accurate loss estimate can be obtained later for any flow between any two observation points by statistically denoising the recorded information. FLOE advances the state-of-the-art on per-flow loss measurement from the following three major fronts: measurement granularity (as it measures per-flow losses), traffic interference (as it uses no probe packets), and accuracy guarantee (as it is guaranteed to satisfy the required reliability and confidence interval specified by operators). FLOE is designed to be efficiently implementable on network middleboxes. In terms of processing overhead, FLOE performs only one hash and one memory update per packet. In terms of storage space, FLOE uses less than 0.05 bits per packet, which means that, on a backbone link with about half a million packets per second, using a 256GB drive, FLOE can accumulate packet loss information of flows traversing the link for about 3 years. We evaluated FLOE using three real traffic traces that include a backbone traffic trace, an enterprise network traffic trace, and a data center traffic trace. Our results show that FLOE always achieves the required reliability for any given confidence interval and network topology.

Network monitoring and management require accurate statistics of a variety of flow-level metrics such as flow sizes, top-$k$flows, and number of flows. Arguably, the current best technique to measure these metrics is sketches. While a significant amount of work has already been done on sketching techniques, there is still a lot of room for improvement because the accuracy of existing sketches varies with changing characteristics of network traffic. In this paper, we propose the idea of using machine learning to improve the accuracy of sketches, and propose ageneric machine learning frameworkto reduce the dependence of accuracy of sketches on network traffic characteristics. We further present three case studies, where we applied our machine learning framework on sketches for measuring three flow-level network metrics, namely flow sizes, top-$k$flows, and number of flows. We implemented and extensively evaluated this framework for these three metrics using both real-world and synthetic traffic traces. To the best of our knowledge, this is the first work that uses machine learning to reduce the dependence of sketching techniques on the characteristics of network traffic. We have released all our traces and implementation codes at Github.

Generating maps of indoor environments beyond the line-of-sight finds applications in several areas such as planning, navigation, and security. While researchers have previously explored the use of RF signals to generate maps, prior work has two important limitations: (i) it requires moving the mapping setup along the entire lengths of the sides of the building, and (ii) it generates maps that are not fully connected, rather are scatter plots of locations from where some obstacles reflected the signals. Thus, prior approaches require human interpretation to locate the walls and determine how they merge. In this article, we address these limitations and propose RFMap, which generates fully connected maps, and does not require the measurement setup to be moved along the sides of the buildings. To generate the map, RFMap first transmits RF signals in many different directions and then measures the distances of different reflectors inside the building. Next, it identifies these reflectors and classifies them into various types based on the properties of the reflections. A key challenge is that RFMap does not receive reflections from all the directions due to the specular nature of the reflectors. Due to this, it only gets sparse data about the objects in the environment. To address this challenge, RFMap trains a deep generative adversarial network (GAN) to intelligently predict the missing information. At runtime, it feeds the locations and types of the detected reflectors to the trained GAN and generates complete and accurate map. We implemented RFMap using software defined radios and extensively evaluated it in several real-world environments. Our results show that RFMap generated the maps of all the buildings that we tested it on with high accuracy.

Ridesharing services do not make data of their availability (supply, utilization, idle time, and idle distance) and surge pricing publicly available. It limits the opportunities to study the spatiotemporal trends of the availability and surge pricing of these services. Only a few research studies conducted in North America analyzed these features for only Uber and Lyft. Despite the interesting observations, the results of prior works are not generalizable or reproducible because: i) the datasets collected in previous publications are spatiotemporally sensitive, i.e., previous works do not represent the current availability and surge pricing of ridesharing services in different parts of the world; and ii) the analyses presented in previous works are limited in scope (in terms of countries and ridesharing services they studied). Hence, prior works are not generally applicable to ridesharing services operating in different countries.

With the advent of the Internet of Things (IoT), sensor and actuator networks, subsequently referred to as IoT networks (IoT Ns), are proliferating at an unprecedented rate in several newfound areas such as smart cities, health care, and transportation, and consequently, securing them is of paramount importance. In this paper, we present NLSec, a fully distributed and lightweight framework that can detect arbitrary network layer (NL) attacks in any given IoTN, localize (i.e., identify) the compromised nodes, and mitigate the attacks by isolating the compromised nodes automatically. We also present insights obtained from an exploratory study on the effects of NL attacks on IoTNs, which guided us in designing NLSec. We demonstrate the effectiveness of NLSec through extensive experiments on a real IoTN test-bed under three well-known NL attacks.

In this paper, we propose CoMEt, a radio frequency based approach that measures soil moisture at multiple depths underneath the ground surface without installing any objects in the soil and without making any contact with the ground surface. The main insight behind CoMEt is that the phase of an RF signal depends on its wavelength in the medium through which it is propagating, which in turn depends on the amount of soil moisture. To measure soil moisture, CoMEt leverages the phase changes across successive antennas in a receive antenna array along with the time of flight of the received signal to jointly estimate the depth of each layer of soil and the wavelength of the signal in each layer. It then uses these estimates to obtain the amount of moisture in each soil layer. We have implemented CoMEt using a software defined radio and a Raspberry Pi to measure soil moisture in real-time. We have extensively evaluated CoMEt in both indoor and outdoor environments. Our results show that CoMEt estimated soil moisture for up to three layers of soil with a median error of just 1.1%.

Email services use spam filtering algorithms (SFAs) to filter emails that are unwanted by the user. However, at times, the emails perceived by an SFA as unwanted may be important to the user. Such incorrect decisions can have significant implications if SFAs treat emails of user interest as spam on a large scale. This is particularly important during national elections. To study whether the SFAs of popular email services have any biases in treating the campaign emails, we conducted a large-scale study of the campaign emails of the US elections 2020 by subscribing to a large number of Presidential, Senate, and House candidates using over a hundred email accounts on Gmail, Outlook, and Yahoo. We analyzed the biases in the SFAs towards the left and the right candidates and further studied the impact of the interactions (such as reading or marking emails as spam) of email recipients on these biases. We observed that the SFAs of different email services indeed exhibit biases towards different political affiliations.

Scalability and performance requirements are driving tenants to increasingly move their applications to public clouds. Unfortunately, cloud providers do not provide a view of their networking infrastructure to the tenants, rather only provide some generic service level agreements (SLAs). Tenants are, therefore, forced to plan the deployments of their applications based on these SLAs. This limits the performance that the tenants can achieve. Keeping this in view, we present a detailed network measurement study of the largest public cloud, Amazon Web Services (AWS). We collected network data to characterize the availability and latency of AWS over a period of 100 days and studied various temporal trends across several geographical locations of AWS throughout the world. We performed our study at all three levels of cloud hierarchy: inside availability zones (AZs), across AZs, and across regions. Our results show that network behavior varies significantly over time at different geographical locations, levels of hierarchy, and temporal granularities. For example, while we observed high availability at monthly granularity, it deteriorates at daily and hourly granularities. This and many other such observations that we present have significant implications for cloud tenants. We further implemented our measurement approach on Google Cloud Platform (GCP) to demonstrate that it can be deployed on any cloud platform and present some preliminary comparative observations from this implementation. Based on our observations, we present several recommendations that tenants can use to better deploy their applications.

Google’s QUIC protocol has become popular over the past few years and is being rapidly adopted as the transport protocol of choice by popular Internet services in their mobile applications. Considering this, it is crucial to understand the performance and implementation issues of integrating QUIC with mobile and wearable applications. In this paper, we conduct a comprehensive measurement analysis and comparison of QUIC with TCP on mobile and wearable platforms. Our experiments cover a wide range of environments, including different request sizes, traffic directions, and connectivity types. From our experiments, we found that the benefits of using QUIC instead of TCP to service HTTP requests are not uniform across different scenarios. We also found a bug in the current implementation of QUIC in Android’s Cronet library that prevents the applications from reverting back to using WiFi after a connection migration from LTE happens. Our experiences from this measurement study has lead us to propose a probabilistic framework, which we call Dynamic Transport Selection, that adaptively chooses the appropriate transport protocol for a given network environment. We implemented and evaluated this framework in Android and Wear OS devices and found that it improves the overall request completion performance of the application by as much as 41.76% when compared to using either QUIC or TCP alone

Among the efforts to overcome the problem of rapidly saturating RF bands, visible light communication (VLC) is garnering a renewed interest as it can be enabled using commodity LED lamps. As indoor spaces are typically illuminated by multiple lamps comprising multiple LEDs each, a natural approach to efficiently utilize the bandwidth of all the LEDs is to use MIMO communication. The state of the art approach to decode MIMO streams is to use channel matrix. Although channel matrix based decoding method (CMDM) works very well in conventional RF technologies, when used in VLC, it suffers from several limitations, such as high sensitivity to environmental conditions, and need for sophisticated receivers. To overcome these limitations, we propose PCDM, a novel parallelogram - clustering based decoding method, which is fundamentally different from CMDM and achieves an order of magnitude lower bit error rate compared to CMDM. We implement and extensively evaluate these two methods using a real VLC MIMO testbed. Our results show that PCDM outperformed CMDM in all scenarios.

WiFi based gesture recognition has received significant attention overthe past few years. However, the key limitation of prior WiFi based gesture recognition systems is that they cannot recognize the gestures of multiple users performing them simultaneously. In this article, we address this limitation and propose WiMU, a WiFi based Multi-User gesture recognition system. The key idea behind WiMU is that when it detects that some users have performed some gestures simultaneously, it first automatically determines the number of simultaneously performed gestures (Na) and then, using the training samples collected from a single user, generates virtual samples for various plausible combinations of Na gestures. The key property of these virtual samples is that the virtual samples for any given combination of gestures are identical to the real samples that would result from real users performing that combination of gestures. WiMU compares the detected sample against these virtual samples and recognizes the simultaneously performed gestures. We implemented and extensively evaluated WiMU using commodity WiFi devices. Our results show that WiMU recognizes 2, 3, 4, 5, 6, 7, and 8 simultaneously performed gestures with accuracies of 95.6, 94.9, 93.9, 92.7, 91.6, 91.0, and 90.1 percent, respectively.

Cloud computing has become the de-facto paradigm for fulfilling the computing needs of a myriad of applications like streaming, e-commerce, data analytics, etc. While a significant amount of work exists on how cloud providers can improve the networking performance of their cloud platforms, very little has been done to explore how a cloud tenant can achieve the best performance for their applications. In this paper, we study how the choice of the TCP variant impacts the performance achieved by tenant applications. We present a generic measurementbased approach to identify the best TCP variant for any given application in a given cloud environment. Our approach is comprised of first measuring several performance metrics including throughput, latency, and loss in the given cloud platform for several TCP variants, and then identifying the best TCP variant based on three things: observations from the measurements, nature of the traffic of the given application, and application requirements such as high throughput or low latency. We study the effectiveness of our approach by implementing it in two large public clouds, Amazon's AWS and Google's GCP, and present our observations from several case studies using three common cloud applications, namely streaming, distributed input-output, and sort, and four common TCP variants, namely Cubic, New Reno, BBR, and DCTCP. From our observations, we found that just by changing the TCP variant that an application uses, the average throughput can be increased by up to 13.7% and the round trip time can be decreased by up to 5 times.

The switch fabrics of today's data centers carry traffic controlled by a variety of TCP congestion control algorithms. This leads us to ask: how does the coexistence of multiple variants of TCP on shared switch fabric impacts the performance achieved by different applications in data centers? To answer this question, we conducted an extensive set of experiments with coexisting TCP variants on Leaf-Spine and Fat-Tree switch fabrics. We executed common data center workloads, which include streaming, MapReduce, and storage workloads, using four commonly used TCP variants, namely BBR, DCTCP, CUBIC, and New Reno. We also extensively executed iPerf workloads using these 4 TCP variants to purely study the impact of the coexistence of TCP variants on each other's performance without incorporating the network behavior of the application layer. Our experiments resulted in a large set of network traces comprised of 160 billion packets (we will release these traces after publication of this work). We present comprehensive observations from these traces that have important implications in ensuring optimal utilization of data center switch fabric and in meeting the network performance needs of application layer workloads.

Generating maps of indoor environments beyond the line of sight finds applications in several areas such as planning, navigation, and security. While researchers have previously explored the use of RF signals to generate maps, prior work has two important limitations: (i) it requires moving the mapping setup along the entire lengths of the sides of the building, and (ii) it generates maps that are not fully connected, rather are scatter plots of locations from where some obstacles reflected the signals. Thus, prior approaches require human interpretation to locate the walls and determine how they merge. In this paper, we address these limitations and propose RFMap, which generates fully connected maps, and does not require the measurement setup to be moved along the sides of the buildings. To generate the map, RFMap first transmits RF signals in many different directions by rotating the antennas while keeping them at the same location and then measures the distances of different reflectors inside the building. Next, it identifies these reflectors and classifies them into various types based on the properties of the reflections. A key challenge is that RFMap does not receive reflections from all the directions due to the specular nature of the reflectors. Due to this, it only gets sparse data about the objects in the environment. To address this challenge, RFMap trains deep generative adversarial network (GAN) to intelligently predict the missing information. At runtime, it feeds the locations and types of the detected reflectors to the trained GAN and generates the complete and accurate map. We implemented RFMap using software defined radios and extensively evaluated it in several real world environments. Our results show that RFMap generated the maps of all the buildings that we tested it on with high accuracy.

With a large number of connected vehicles on the roads, there is an opportunity to leverage their connectivity to minimize congestion on roads by calculating fast routes for vehicles in a way that each vehicle contributes as little to the congestion as possible. The existing commercial and research based approaches of calculating routes for vehicles suffer from one or more of the following two limitations: 1) they are not privacy preserving in the sense that they receive destination addresses from users and may either store and use them for other commercial purposes or are at a risk of getting hacked and exposing these addresses to hackers; and 2) they require expensive infrastructure such as road side units (RSUs). To address these limitations, we propose a distributed and privacy preserving routing protocol, namely DPR, which the connected vehicles collaboratively and repeatedly execute to calculate fast routes to their destinations such that the overall congestion on the road network is significantly reduced and at the same time the privacy of the vehicles is preserved. The DPR protocol relies on direct vehicle to vehicle communication and does not need any new infrastructure such as RSUs. We have implemented and evaluated our DPR protocol through simulations on a real road network under several traffic conditions. Our results show that DPR reduces the average travel time of vehicles that travel a distance of 1000, 2500, and over 4000 meters by 15%, 32%, and 42%, respectively. This reduction in travel time is significant considering that this improvement results purely from software manipulations and without requiring any new infrastructure.

Typical home security systems monitor homes for intrusions by installing contact sensors on doors and windows and motion sensors inside the house. Unfortunately, due to the high deployment and operational costs of today's home security systems, only a small fraction of homes have security systems installed (e.g., only 17% in the US and 15% in China). In this paper, we propose a WiFi based Home Security system (WiHS) that uses commodity WiFi devices, which most modern households already have, to perform the three primary tasks of typical home security systems: 1) detect when a door/window is opened/closed, 2) identify which door/window has been opened/closed, and 3) detect movements inside the house. The design of WiHS is based on our intuitive and theoretical understanding of the impacts of the movements of doors and windows on WiFi signals, which we will develop and present in this paper. We extensively evaluated WiHS using commodity WiFi devices in 3 different houses. WiHS detected intrusions with over 95% accuracy and identified the exact door/window that moved with just 4.5% average error.

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.

Sketches are probabilistic data structures designed for recording frequencies of items in a multi-set. They are widely used in various fields, especially for gathering Internet statistics from distributed data streams in network measurements. In a distributed streaming application with high data rates, a sketch in each monitoring node “fills up” very quickly and then its content is transferred to a remote collector responsible for answering queries. Thus, the size of the contents transferred must be kept as small as possible while meeting the desired accuracy requirement. To obtain significantly higher accuracy while keeping the same update and query speed as the best prior sketches, in this article, we propose a new sketch - the Slim-Fat (SF) sketch. The key idea behind the SF-sketch is to maintain two separate sketches: a larger sketch, the Fat-subsketch, and a smaller sketch, the Slim-subsketch. The Fat-subsketch is used for updating and periodically producing the Slim-subsketch, which is then transferred to the remote collector for answering queries quickly and accurately. We also present the error bound as well as an accurate model of the correct rate of the SF-sketch, and verify their correctness through experiments. We implemented and extensively evaluated the SF-sketch along with several prior sketches. Our results show that when the size of our Slim-subsketch and of the widely used Count-Min (CM) sketch are kept the same, our SF-sketch outperforms the CM-sketch by up to 33.1 times in terms of accuracy (when the ratio of the sizes of the Fat-subsketch and the Slim-subsketch is 16:1). We have made all source codes publicly available at Github [“Source code of SF sketches,” [Online]. Available: https://github.com/paper2017/SF-sketch].

With the advent of the internet of things, the number of wireless devices and the amount of wireless data traffic is increasing at an unprecedented rate. By 2020, the number of connected devices per person is expected to exceed 6.58. Due to the ubiquitous availability of IEEE 802.11n/ac (i.e., WiFi) in most modern homes and enterprise environments, the majority of the new home and enterprise focused IoT devices that are entering the market use IEEE 802.11n/ac to connect to the internet. Our literature survey revealed that there are no prior measurement studies on the performance of IEEE 802.11n/ac's MAC in dense IoT environments. Thus, in this paper, we conduct a comprehensive measurement study of various aspects of IEEE 802.11n/ac's MAC using real IoT devices and realistic IoT workloads and present several useful observations that demonstrate the need to revise some of the key aspects of IEEE 802.11n/ac's MAC to make it suitable for dense IoT environments. This need for revisions stems from the fact that IEEE 802.11n/ac was primarily designed keeping conventional devices, such as laptops, smart phones, and servers in view. For such conventional devices, the amount of uplink traffic is significantly smaller compared to the amount of downlink traffic. Contrary to this, in dense IoT deployments, the amount of uplink traffic is significantly larger compared to the downlink traffic. We conducted our study on a real test bed comprising a large number of Raspberry Pis deployed in a real world environment and studied the impact of the density and type of IoT traffic on the throughput of the wireless system, bandwidth utilization of RTS and CTS frames, block acknowledgments, and frame aggregation sizes. We further studied the impact of TCP's congestion control mechanism on the performance of IEEE 802.11n/ac's MAC.

Accurately measuring the distance traveled by an object or odometry, in indoor environments is important in many applications such as video-game controller tracking or robot route guidance. While the distance traveled by an object can be simply measured using an accelerometer, it is wellknown that distances measured with accelerometers suffer from large drift errors. In this paper, we demonstrate WIO, a WiFi-assisted Inertial Odometry technique that uses WiFi signals as an auxiliary source of information to correct such drift errors. The key intuition behind WIO is that, among multiple paths of a transmitted WiFi signal that arrive at a moving object equipped with a WiFi receiver, WIO can isolate the path that is most parallel to the object's direction of motion and use the change in the length of that path as an estimate of the traversed distance. WIO then fuses this distance estimate with the distance measured from an accelerometer on-board the object to correct drift errors. We implement WIO using commodity devices, and evaluate it on a robot car. Our results demonstrate an average error of just 4.37% in estimating the distance traversed by the car.

With the advent of the internet of things, the number of wireless devices and the amount of wireless data traffic is increasing at an unprecedented rate. By 2020, the number of connected devices per person is expected to exceed 6.58. Due to the ubiquitous availability of IEEE 802.11n/ac (i.e., WiFi) in most modern homes and enterprise environments, the majority of the new home and enterprise-focused IoT devices that are entering the market use IEEE 802.11n/ac to connect to the internet. Our literature survey revealed that there are no prior measurement studies on the performance of IEEE 802.11n/ac's MAC in dense IoT environments. Thus, in this paper, we conduct a comprehensive measurement study of various aspects of IEEE 802.11n/ac's MAC using real IoT devices and realistic IoT workloads and present several useful observations that demonstrate the need to revise some of the key aspects of IEEE 802.11n/ac's MAC to make it suitable for dense IoT environments. We conducted our study on a real testbed comprising a large number of Raspberry Pis deployed in a real-world environment and studied the impact of the density and type of IoT traffic on the throughput and frame aggregation sizes of the wireless system. We further studied the impact of TCP's congestion control mechanism on the performance of IEEE 802.11n/ac's MAC.

With the advent of the Internet of Things (IoT), sensor and actuator networks, subsequently referred to as IoT networks (IoTNs), are proliferating at an unprecedented rate in several newfound areas such as smart cities, health care, and transportation, and consequently, securing them is of paramount importance. We present NLSec, a fully distributed and lightweight framework that can detect arbitrary network layer (NL) attacks in any given IoTN, localize (i.e., identify) the compromised nodes, and mitigate the attacks by isolating the compromised nodes automatically. We also present insights obtained from an exploratory study on the effects of NL attacks on IoTNs, which guided us in designing NLSec.

Most Internet of Things (IoT) applications require unique guarantees on various performance metrics (such as latency, CPU availability, power fairness, etc.) from the IoT infrastructure. A small deterioration in these performance metrics can cause serious violations of service level agreements. To ensure that the deployed IoT infrastructure delivers the guarantees on these metrics, the first step is to measure these metrics. We present IoTm, a framework for measuring IoT performance metrics, which include both IoT network's quality of service (QoS) metrics and IoT node's resource utilization (RU) metrics. IoTm has two key properties: 1) it is lightweight and thus amenable for implementation on resource constrained IoT nodes; and 2) it can perform measurements at fine-grained levels and not just at aggregate levels. IoTm is comprised of two components, a lightweight IoT node unit (INU), which resides in each of the IoT nodes, and a control and query unit (CQU), which resides in a logically centralized management server. The primary role of INU is to record appropriate information about the desired performance metrics in the IoT nodes. To record the information, INU leverages a generic data structure that we propose. CQU is responsible for identifying the metrics and the IoT nodes on which those metrics should be monitored to achieve a desired measurement objective. CQU also stores the copies of data structures that the INU sends to it for long term storage. Both INU and CQU further contain query processing engines, which operate on the information stored in the data structures to answer measurement queries. To demonstrate the use of our framework, we apply it to one RU metric (number of disk accesses), and one QoS metric (round trip latency), and evaluate its accuracy. We also analyze the feasibility of its implementation on IoT nodes in terms of memory requirement and computational complexity.

WiFi based gesture recognition has received significant attention over the past few years. However, the key limitation of prior WiFi based gesture recognition systems is that they cannot recognize the gestures of multiple users performing them simultaneously. In this paper, we address this limitation and propose WiMU, a WiFi based Multi-User gesture recognition system. The key idea behind WiMU is that when it detects that some users have performed some gestures simultaneously, it first automatically determines the number of simultaneously performed gestures (Na) and then, using the training samples collected from a single user, generates virtual samples for various plausible combinations of Na gestures. The key property of these virtual samples is that the virtual samples for any given combination of gestures are identical to the real samples that would result from real users performing that combination of gestures. WiMU compares the detected sample against these virtual samples and recognizes the simultaneously performed gestures. We implemented and extensively evaluated WiMU using commodity WiFi devices. Our results show that WiMU recognizes 2, 3, 4, 5, and 6 simultaneously performed gestures with accuracies of 95.0, 94.6, 93.6, 92.6, and 90.9%, respectively.

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.

Hash table, a widely used data structure, can achieve an O(1) average lookup speed at the cost of large memory usage. Unfortunately, hash tables suffer from collisions and the rate of collisions is largely determined by the load factor. Broadly speaking, existing research has taken two approaches to improve the performance of hash tables. The first approach trades-off collision rate with memory usage, but only works well under low load. The second approach pursues high load and no hash collisions, but comes with update failures. The goal of this paper is to design a practical and efficient hash table that achieves high load factor, low hash collision rate, fast lookup speed, fast update speed, and zero update failures. To achieve this goal, we take a three-step approach. First, we propose a set of hashing techniques that leverage Bloom filters to significantly reduce hash collision rates. Second, we introduce a novel kick mechanism to achieve a high load factor. Last, we develop bitmaps to significantly accelerate the kick mechanism. Theoretical analysis and experimental results show that our hashing schemes significantly outperform the state-of-the-art Our hash table achieves a high load factor (greater than 95%), a low collision rate (less than 0.56%), and the number of hash buckets almost equals to the number of key-value pairs. Given n key-value pairs, the collision rate is reduced to 0 by either using 1.18 ×n buckets or allowing up to 5 blind kicks. We have released the source code of the implementations of our hash table and of 6 prior hash tables at Github [1].

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.

A sketch is a probabilistic data structure that is used to record frequencies of items in a multi-set. Sketches have been applied in a variety of fields, such as data stream processing, natural language processing, distributed data sets etc. In this paper, we propose a new sketch, called Slim-Fat (SF) sketch, which has a much smaller memory footprint for query while supporting updates. The key idea behind our proposed SF-sketch is to maintain two separate sketches: a small sketch called Slimsubsketch and a large sketch called Fat-subsketch. The Slimsubsketch enables fast and accurate querying. The Fat-subsketch is used to assist the insertion and deletion from Slim-subsketch. We implemented and evaluated SF-sketch along with several prior sketches and compared them side by side. Our experimental results show that SF-sketch significantly outperforms the most commonly used CM-sketch in terms of accuracy. The full version is provided at arXiv.org [12].

WiFi based gesture recognition systems have recently proliferated due to the ubiquitous availability of WiFi in almost every modern building. The key limitation of existing WiFi based gesture recognition systems is that they require the user to be in the same configuration (i.e., at the same position and in same orientation) when performing gestures at runtime as when providing training samples, which significantly restricts their practical usability. In this paper, we propose a WiFi based gesture recognition system, namely WiAG, which recognizes the gestures of the user irrespective of his/her configuration. The key idea behind WiAG is that it first requests the user to provide training samples for all gestures in only one configuration and then automatically generates virtual samples for all gestures in all possible configurations by applying our novel translation function on the training samples. Next, for each configuration, it generates a classification model using virtual samples corresponding to that configuration. To recognize gestures of a user at runtime, as soon as the user performs a gesture, WiAG first automatically estimates the configuration of the user and then evaluates the gesture against the classification model corresponding to that estimated configuration. Our evaluation results show that when user's configuration is not the same at runtime as at the time of providing training samples, WiAG significantly improves the gesture recognition accuracy from just 51.4% to 91.4%.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.