Learning-based methods, such as imitation learning (IL) and reinforcement learning (RL), can produce excel control policies over challenging agile robot tasks, such as sports robot. However, no existing work has harmonized learning-based policy with model-based methods to reduce training complexity and ensure the safety and stability for agile badminton robot control. In this paper, we introduce Hamlet, a novel hybrid control system for agile badminton robots. Specifically, we propose a model-based strategy for chassis locomotion which provides a base for arm policy. We introduce a physics-informed “IL+RL” training framework for learning-based arm policy. In this train framework, a modelbased strategy with privileged information is used to guide arm policy training during both IL and RL phases. In addition, we train the critic model during IL phase to alleviate the performance drop issue when transitioning from IL to RL. We present results on our self-engineered badminton robot, achieving 94.5% success rate against the serving machine and$\mathbf{9 0. 7 \%}$success rate against human players. Our system can be easily generalized to other agile mobile manipulation tasks e.g., agile catching, table tennis. A video demonstrating our system can be viewed at https://youtu.be/8-ixKAD18Mk.

Visual question answering (VQA) is challenging not only because the model has to handle multi-modal information, but also because it is just so hard to collect sufficient training examples -there are too many questions one can ask about an image.As a result, a VQA model trained solely on human-annotated examples could easily over-fit specific question styles or image contents that are being asked, leaving the model largely ignorant about the sheer diversity of questions.Existing methods address this issue primarily by introducing an auxiliary task such as visual grounding, cycle consistency, or debiasing.In this paper, we take a drastically different approach.We found that many of the "unknowns" to the learned VQA model are indeed "known" in the dataset implicitly.For instance, questions asking about the same object in different images are likely paraphrases; the number of detected or annotated objects in an image already provides the answer to the "how many" question, even if the question has not been annotated for that image.Building upon these insights, we present a simple data augmentation pipeline SIMPLEAUG to turn this "known" knowledge into training examples for VQA.We show that these augmented examples can notably improve the learned VQA models' performance, not only on the VQA-CP dataset with language prior shifts but also on the VQA v2 dataset without such shifts.Our method further opens up the door to leverage weakly-labeled or unlabeled images in a principled way to enhance VQA models.Our code and data are publicly available at https://github.com/ heendung/simpleAUG.

Many objects do not appear frequently enough in complex scenes (e.g., certain handbags in living rooms) for training an accurate object detector, but are often found frequently by themselves (e.g., in product images). Yet, these object-centric images are not effectively leveraged for improving object detection in scene-centric images. In this paper, we propose Mosaic of Object-centric images as Scene-centric images (MosaicOS), a simple and novel framework that is surprisingly effective at tackling the challenges of long-tailed object detection. Keys to our approach are three-fold: (i) pseudo scene-centric image construction from object-centric images for mitigating domain differences, (ii) high-quality bounding box imputation using the object-centric images’ class labels, and (iii) a multi-stage training procedure. On LVIS object detection (and instance segmentation), MosaicOS leads to a massive 60% (and 23%) relative improvement in average precision for rare object categories. We also show that our framework can be compatibly used with other existing approaches to achieve even further gains. Our pre-trained models are publicly available at https://github.com/czhang0528/MosaicOS/.

Vanilla models for object detection and instance segmentation suffer from the heavy bias toward detecting frequent objects in the long-tailed setting. Existing methods address this issue mostly during training, e.g., by re-sampling or re-weighting. In this paper, we investigate a largely overlooked approach --- post-processing calibration of confidence scores. We propose NorCal, Normalized Calibration for long-tailed object detection and instance segmentation, a simple and straightforward recipe that reweighs the predicted scores of each class by its training sample size. We show that separately handling the background class and normalizing the scores over classes for each proposal are keys to achieving superior performance. On the LVIS dataset, NorCal can effectively improve nearly all the baseline models not only on rare classes but also on common and frequent classes. Finally, we conduct extensive analysis and ablation studies to offer insights into various modeling choices and mechanisms of our approach. Our code is publicly available at https://github.com/tydpan/NorCal.

Identifying “superspreaders” of disease is a pressing concern for society during pandemics such as COVID-19. Superspreaders represent a group of people who have much more social contacts than others. The widespread deployment of WLAN infrastructure enables non-invasive contact tracing via people’s ubiquitous mobile devices. This technology offers promise for detecting superspreaders. In this paper, we propose a general framework for WLAN-log-based superspreader detection. In our framework, we first use WLAN logs to construct contact graphs by jointly considering human symmetric and asymmetric interactions. Next, we adopt three vertex centrality measurements over the contact graphs to generate three groups of superspreader candidates. Finally, we leverage SEIR simulation to determine groups of superspreaders among these candidates, who are the most critical individuals for the spread of disease based on the simulation results. We have implemented our framework and evaluate it over a WLAN dataset with 41 million log entries from a large-scale university. Our evaluation shows superspreaders exist on university campuses. They change over the first few weeks of a semester, but stabilize throughout the rest of the term. The data also demonstrate that both symmetric and asymmetric contact tracing can discover superspreaders, but the latter performs better with daily contact graphs. Further, the evaluation shows no consistent differences among three vertex centrality measures for long-term (i.e., weekly) contact graphs, which necessitates the inclusion of SEIR simulation in our framework. We believe our proposed framework and these results can provide timely guidance for public health administrators regarding effective testing, intervention, and vaccination policies.

Recently, intelligent sports analytics is becoming a hot area in both industry and academia for coaching, practicing tactic and technical analysis. With the growing trend of bringing sports analytics to live broadcasting, sports robots and common playfield, a low cost system that is easy to deploy and performs real-time and accurate sports analytics is very desirable. However, existing systems, such as Hawk-Eye, cannot satisfy these requirements due to various factors. In this paper, we present MV-Sports, a cost-effective system for real-time sports analysis based on motion and vision sensor integration. Taking tennis as a case study, we aim to recognize player shot types and measure ball states. For fine-grained player action recognition, we leverage motion signal for fast action highlighting and propose a long short term memory (LSTM)-based framework to integrate MV data for training and classification. For ball state measurement, we compute the initial ball state via motion sensing and devise an extended kalman filter (EKF)-based approach to combine ball motion physics-based tracking and vision positioning-based tracking to get more accurate ball state. We implement MV-Sports on commercial off-the-shelf (COTS) devices and conduct real-world experiments to evaluate the performance of our system. The results show our approach can achieve accurate player action recognition and ball state measurement with sub-second latency.

Visual (V) surveillance systems are extensively deployed and becoming the largest source of big data. On the other hand, electronic (E) data also plays an important role in surveillance and its amount increases explosively with the ubiquity of mobile devices. One of the major problems in surveillance is to determine human objects' identities among different surveillance scenes. Traditional way of processing big V and E datasets separately does not serve the purpose well because V data and E data are imperfect alone for information gathering and retrieval. Matching human objects in the two datasets can merge the good of the two for efficient large-scale surveillance. Yet such matching across two heterogeneous big datasets is challenging. In this paper, we propose an efficient set of parallel algorithms, called EV-Matching, to bridge big E and V data. We match E and V data based on their spatiotemporal correlation. The EV-Matching algorithms are implemented on Apache Spark to further accelerate the whole procedure. We conduct extensive experiments on a large synthetic dataset under different settings. Results demonstrate the feasibility and efficiency of our proposed algorithms.

In this research, we conduct a comprehensive measurement study on the predictability of human mobility with respect to demographic differences. We leverage an extensive WLAN dataset collected on a large university campus. Specifically, our dataset includes over 41 million WLAN entries gathered from over 5,000 students (with demographic information) during a four-month period in 2015. We observed surprising patterns on large increases of long-term mobility entropy by age, and the impact of academic majors on students long-term mobility entropy. The distribution of long-term entropy follows a bimodal distribution, which is different from previous studies. We also find that the predictability of students' short-term (daily or weekly) mobility varies on different days of the week and with student gender. Because of the large campus size, our results can mimic people's mobility patterns in metropolitan areas. We also anticipate that our results will provide insight that guides academic administrators' decisions regarding facilities planning, emergency management, etc. on campus.

In this paper, we study vision-based localization for robots. We anticipate that numerous mobile robots will serve or interact with humans in indoor scenarios such as healthcare, entertainment, and public service. Such scenarios entail accurate and scalable indoor visual robot localization, the subject of this work. Most existing vision-based localization approaches suffer from low localization accuracy and scalability issues due to visual environmental features' limited effective range and detection accuracy. In light of infrastructural cameras' wide indoor deployment, this paper proposes BRIDGELOC, a novel vision-based indoor robot localization system that integrates both robots' and infrastructural cameras. BRIDGELOC develops three key technologies: robot and infrastructural camera view bridging, rotation symmetric visual tag design, and continuous localization based on robots' visual and motion sensing. Our system bridges robots' and infrastructural cameras' views to accurately localize robots. We use visual tags with rotation symmetric patterns to extend scalability greatly. Our continuous localization enables robot localization in areas without visual tags and infrastructural camera coverage. We implement our system and build a prototype robot using commercial off-the-shelf hardware. Our real-world evaluation validates BRIDGELOC's promise for indoor robot localization.

Massive visual traffic data have become available recently. Though it opens the realm of intelligent traffic analysis, processing the data in a timely manner is difficult yet critical to time sensitive decisions, which are typical to traffic related management. In this paper, we study time-bounded aggregation analytics on large visual traffic data including traffic images and videos. We first find that current MapReduce framework can not work well due to two challenges: first, significant dual diversities exist on data distributions and processing time; second, apriori knowledge on these distributions and time costs are not always available. However, we also observe spatial and temporal locality on data values and processing time. Based on the examination, we design Traffic At-a-Glance (TaG), an augmented MapReduce framework for time-bounded traffic analytics jobs. Particularly, we propose a novel sampling algorithm that exploits traffic data localities and stratifies samples based on data distributions and processing time. It runs in an iterative, adaptive manner without apriori knowledge. Moreover, we propose a heuristic scheduling algorithm with considerations of batch processing overhead. Further, we refine the load balancing mechanism based on data processing time locality to respect job time bounds. In addition, we extend TaG to well handle traffic videos by sampling video data based on motion information encoded in the videos. We implement TaG on Hadoop and conduct extensive experiments on a large visual traffic dataset. The evaluations on different data sizes show TaG is able to achieve high accuracy within time bounds.

Massive visual traffic data have become available recently, which provides an opportunity for intelligent traffic analysis. Timely processing is particularly necessary for traffic analysis. In this paper, we study time-bounded aggregation analytics on large visual traffic data. We first find that current MapReduce framework can not work well due to two challenges: first, significant dual diversities exist on data distributions and processing time; second, no apriori knowledge on these distributions and time costs is available. However, we also observe spatial and temporal locality on data values and processing time. Based on the examination, we design TaG, an augmented MapReduce framework for time-bounded traffic analytics jobs. Particularly, we propose a novel sampling algorithm that exploits traffic data localities and stratifies samples based on data distributions and processing time. It runs in an iterative, adaptive manner without apriori knowledge. Moreover, we propose a heuristic scheduling algorithm with considerations of batch processing overhead. Further, we refine load balancing mechanism based on data processing time locality to respect job time bounds. We implement TaG on Hadoop and conduct extensive experiments on a large traffic image dataset. The evaluations on different data sizes show TaG is able to achieve high accuracy within different time bounds.

Accurate indoor localization is a key enabling technology for numerous applications such as indoor navigation, mobile social networking, and augmented reality. Despite major effort from the research community, state-of-the-art indoor localization performance remains unsatisfactory. Current approaches using radio frequency entail tedious site surveys and have limited accuracy. While vision-based localization techniques are promising, they struggle with human recognition and changing environments. This paper proposes Flash-Loc, an accurate indoor localization system leveraging flashes of light to localize people carrying mobile phones in areas with deployed surveillance cameras. A person's mobile phone emits a sequence of flashes that uniquely “represents” the person from the cameras' view. Flash-Loc develops three key mechanisms that distinguish people while avoiding long irritating flashes: adaptive-length flash coding, pulse width modulation based flash generation, and image subtraction based flash localization. Further, we design a system in which Flash-Loc cooperates with fingerprinting and dead reckoning for accurate human localization. We implement Flash-Loc on commercial off-the-shelf equipment. Our real-world experiments show Flash-Loc achieves accurate indoor localization by itself and in cooperation with other localization technology. In particular, Flash-Loc can localize a user 45 m away from the camera with sub-meter accuracy.

Many mobile robots are expected to work for or interact with humans indoors in applications such as guided shopping, policing, and senior care. Mobile robots' sensors alone are insufficient in order to realize these applications, infrastructural support is needed. Existing support for mobile robots requires heavy or expensive infrastructures with limited scalability or deployment of unsightly lines or magnetic strips. This paper presents S-Mirror, a novel approach that "reflects" various ambient signals towards mobile robots, greatly extending their sensing abilities. S-Mirror forms a network of S-Mirror nodes that mainly reflect visual signals (as well as electronic and acoustic signals) to assist mobile robots. To illustrate the advantages of S-Mirror, we develop a localization approach for mobile robots that integrates S-Mirror and robots' on-board motion sensors. We implement S-Mirror and a mobile robot prototype on commercial off-the-shelf hardware. Our real-world experimental validation shows that S-Mirror achieves accurate timely localization with low network bandwidth consumption as well as robustness and scalability to many mobile robots.

Abstract Location‐related mobile social network services are popular nowadays, and their methods to obtain end users’ location information are based on people's self‐report location claims, using mobile devices to check positions and send them back to the service providers. However, this mechanism has a serious vulnerability that makes malicious users be able to access restricted resource by transmitting fake locations. Both academic and industrial researchers are recently aware of this problem's importance since the commercialized trend of location‐related mobile social network services. To address this issue, we propose mobile phone‐based physical‐social location, a mobile phone‐based location proof system to verify users’ location claims and defend various fake location information. Our core idea is that a user's location claim can be proved by a set of selective physical encountered people serving as “witnesses” who are co‐located with him/her in that area. The system is composed of proof generation and verification. In the proof generation phase, we leverage a certain number of co‐located people to generate certificates as location proofs during their encounters via bluetooth interface. In the verification phase, we propose an efficient verification scheme to make our system accurate and adaptive. We have implemented the MPSL system using real world Nokia N82 (Nokia, Espoo, Finland) phones. Our experimental results show that our mobile phone‐based system can achieve high verification accuracy and good performance. Copyright © 2014 John Wiley & Sons, Ltd.

Smart devices with built-in sensors, computational capabilities, and network connectivity have become increasingly pervasive. Crowds of smart devices offer opportunities to collectively sense and perform computing tasks at an unprecedented scale. This paper presents Crowd-ML, a privacy-preserving machine learning framework for a crowd of smart devices, which can solve a wide range of learning problems for crowd sensing data with differential privacy guarantees. Crowd-ML endows a crowd sensing system with the ability to learn classifiers or predictors online from crowd sensing data privately with minimal computational overhead on devices and servers, suitable for practical large-scale use of the framework. We analyze the performance and scalability of Crowd-ML and implement the system with off-the-shelf smartphones as a proof of concept. We demonstrate the advantages of Crowd-ML with real and simulated experiments under various conditions.

Following a person is a fundamental requirement for human-robot interaction. In this paper we propose a novel tracking approach for robust human feet tracking which integrates human locomotion into tracking algorithms. The vertical displacement between the two feet is analyzed and we observe that this displacement during the walking cycle is close to a modulated cosine waveform. Based on this, we propose an adaptive model for the human walking pattern. We divide the motion of the human feet into local motion and global motion. The local motion is modeled by a modified cosine wave that updates along time. Global motion is estimated by the continuity between successive frames. This model is combined with particle filtering to guide the searching of the feet. A 2D Gaussian mask is generated according to the predicted position estimated by the motion model and used to modify the weight of the particles. Experiments are implemented in several human walking videos and the algorithm is evaluated against the generic particle filtering method. Results show that the feet can be tracked successfully with significant improvements compared to the generic particle filtering method.

Barrier coverage in visual camera sensor networks (visual barrier coverage) has important real-world applications like battlefield surveillance, environmental monitoring, and protection of government property. Cost-effective deployment, a fundamental issue of visual barrier coverage, considers how to deploy the fewest camera sensors along the barrier to detect intruders (e.g., capture faces) with desirable performance. Existing visual barrier coverage approaches like full-view coverage require numerous camera sensors for capturing intruders' faces deterministically for any trajectory and facing angle. However, intruders' trajectories and facing angles are bounded and deterministic intruder detection requires many camera sensors for rare intrusion cases. Certain practical applications can tolerate limited intrusion mis-detection given budget limitations. This paper proposes local face-view barrier coverage, a novel concept that achieves statistical barrier coverage in camera sensor networks leveraging intruders' trajectory lengths ℓ along the barrier and head rotation angles δ. Using (ℓ, δ) and other parameters, we derive a rigorous probability bound for intruder detection for local face-view barrier coverage via a feasible deployment pattern. Our detection probability bound and deployment pattern can guide practical camera sensor network deployments with camera sensor budgets. Extensive evaluations show that local face-view barrier coverage requires up to 50% fewer camera sensors than full-view barrier coverage.

Human tracking in video has many practical applications such as visual guided navigation, assisted living, etc. In such applications, it is necessary to accurately track multiple humans across multiple cameras, subject to real-time constraints. Despite recent advances in visual tracking research, the tracking systems purely relying on visual information fail to meet the accuracy and real-time requirements at the same time. In this paper, we present a novel accurate and real-time human tracking system called VM-Tracking. The system aggregates the information of motion (M) sensor on human, and integrates it with visual (V) data based on physical locations. The system has two key features, i.e. location-based VM fusion and appearance-free tracking, which significantly distinguish itself from other existing human tracking systems. We have implemented the VM-Tracking system and conducted comprehensive experiments on challenging scenarios.

This paper presents a novel video-based face recognition algorithm by using a sequential sampling and updating scheme, named sequential sample consensus. The proposed algorithm aims at providing a sequential scheme that can be applied to streaming video data. Different from existing approaches, the training video sequences serve as the sample space, and the person's identity in the testing sequence is characterized using an identity probability mass function (PMF) that is sequentially updated. For each testing frame, samples are randomly drawn from the sample space, and the numbers of samples for each identity are determined by the identity PMF. The testing frame is evaluated against the drawn samples to calculate the weights, and the sample weights are used for updating the identity PMF. Benefiting from the sampling procedure, the change in both the numbers and the weights of the samples for each individual leads to quick reaction of the algorithm. The proposed algorithm is robust against misclassification caused by pose variations, and sensitive to identity switching during recognition. The algorithm is evaluated using both public and self-made datasets, and shows better performance than other video-based face recognition approaches.

Electronic channel sounding plays a vital role in developing wireless communication systems. It is critical for transceivers' equalization and filtering operations. However, current pure electronic channel sounding techniques are not well-suited for emerging scenarios such as opportunistic spectrum access, channel impulse response (CIR) based wireless positioning, and wireless security applications, which demand rapid, high-resolution, and spectrum agile channel measurements on commercial off-the-shelf (COTS) devices. To address these critical issues, this paper proposes EV-Sounding, a novel methodology for visual assisted electronic channel sounding. Based on frequency domain channel sounding, EV-Sounding leverages cameras for visual estimation of sparsity locations to reduce the number of frequency samples, thus speeding up the sounding process. EV-Sounding achieves both high-resolution CIR measurements and spectrum agility. We prototype an EV-Sounding system on COTS devices. Our real-world experimental results and extensive simulations validate EV-Sounding's performance.

In this paper, we propose E-Shadow, a distributed mobile phone-based local social networking system. E-Shadow has two main components: (1) Local profiles. They enable E-Shadow users to record and share their names, interests, and other information with fine-grained privacy controls. (2) Mobile phone based local social interaction tools. E-Shadow provides mobile phone software that enables rich social interactions. The software maps proximate users’ local profiles to their human owners and enables user communication and content sharing. We have designed and implemented E-Shadow on mobile phones. In our E-Shadow system, we allow users to perform dynamic and layered information publishing, making use of interpersonal relevance in space and time. Our system also provides a mechanism to help users perform direction-driven localization of an E-Shadow and match it with its owner. Experiments on real world Windows Mobile phones and large-scale simulations show that our system disseminates information efficiently and helps receivers find the direction of a specific E-Shadow with accuracy. We believe our E-Shadow concept and system can lead to a more tightly-knit temporary community in one’s physical vicinity.

Recent years have witnessed mass proliferation of mobile devices with rich wireless communication capabilities as well as emerging mobile device-based information dissemination applications that leverage these capabilities. This paper proposes TurfCast, a novel information dissemination service that selectively broadcasts information in particular "turfs,â abstract logical spaces in which receivers are situated. Such turfs can be temporal or spatial based on receivers' lingering time or physical areas, respectively. TurfCast has many applications such as electronic proximity advertising and mobile social networking. To enable TurfCast, we propose two supporting technologies: TurfCode and TurfBurst. TurfCode is a nested 0-1 fountain code that enables the broadcaster to transmit either all information or none at all to receivers. TurfBurst exploits the Shannon bound to differentiate among receivers: those who cannot receive information fast enough receive none at all, even if they linger near the broadcaster. We implement TurfCast on real-world devices and conduct experiments in both indoor and outdoor environments. Our experimental results illustrate TurfCast's potential for controlling information dissemination in wireless networks.

Nowadays, more and more objects can be represented with electronic identifiers, e.g., people can be recognized from their laptops' MACs, and products can be identified by their RFID numbers. Localizing electronic identifiers is more and more important for a fully digitalized life. However, traditional wireless localization techniques are not satisfactory in performance to determine these electronic identifiers' positions. Some of them require costly hardware to achieve high accuracy and, hence, are not practical. The others are inaccurate and not robust against environmental noises, e.g., RSSI-based localization. Therefore, an accurate and practical approach for localizing electronic identifiers is needed. In this paper, we propose a new localization technique called EV-Loc. In EV-Loc, we make use of visual signals to help improve the accuracy of wireless localization. Our technique fully takes advantage of the high accuracy of visual signals and pervasiveness of electronic signals. To effectively couple these two signals together, we have designed an E-V match engine to find the correspondence between an object's electronic identifier and its visual appearance. We have implemented our technique on mobile devices and evaluated it in the real world. The localization error is less than 1 m. We have also evaluated our approach using large-scale simulations. The results show that our approach is accurate and robust.

In this article, we address a new unexplored problem: what are the optimal patterns to achieve connected coverage in wireless networks with directional antennas. As their name implies, directional antennas can focus their transmission energy in a certain direction. This feature leads to lower cross-interference and larger communication distance. It has been shown that, with proper scheduling mechanisms, directional antennas may substantially improve networking performance in wireless networks. In this article, we propose a set of deployment patterns to achieve full coverage and up to 2-connectivity under two different antenna models, namely the sector model and the knob model. These patterns are optimal under most combinations of communication and sensing ranges. We also introduce with detailed analysis several fundamental theorems and conjectures. Finally, we examine a more realistic physical model, where there might be strong interference and both the sensing range and the communication range might be irregular. The results show that our designed patterns work well even in unstable and fickle physical environments.

In this paper, we propose a new type of incentive-driven and privacy-preserving systems for large-scale message dissemination in mobile networks. To distribute incentives which encourage forwarding behaviors, such as monetary rewards, we want to keep track of the forwarder list. In our algorithms, we rely on a Probabilistic one-ownership forwarding algorithm to record the list, so that the exchanged messages can be kept short and privacy preserving. More specifically, only one hop of forwarder information, instead of the complete list, is recorded, and the information is updated probabilistically following two ownership flipping models, namely, One-Flip and Always-Flip models. We also use a Bluetooth Service Discovery Protocol (SDP) toolkit to enable fast, configuration-free message exchange. Throughout the paper, we use coupon as a typical type of message to illustrate the core ideas. We have implemented the coupon dissemination system in Java ME. Our experiments on real-world mobile phones, such as Nokia and Samsung phones, and large-scale simulations show that our system is efficient in peer-to-peer message distribution and capable of massive deployment. We believe our key methodology can serve as a general framework for facilitating information propagation on mobile phones, where incentives and privacy protection are both essential.

This paper presents a novel video-based face recognition algorithm using a sequential sampling and updating scheme, named sequential sample consensus (SSC). Different from the existing approaches, the training video sequences serve as the sample space, and the person's identity in the testing sequence is characterized by an identity probability mass function (PMF) that is sequentially updated. For each testing frame, samples are randomly drawn from the sample space with the numbers of samples for each identity determined by the identity PMF. The testing frame is evaluated against the drawn samples to calculate the weights, and the sample weights are utilized for updating the identity PMF. The proposed algorithm is robust against misclassification caused by pose variations, and sensitive to identity switching during recognition. The algorithm is evaluated using both public and self-made databases, and shows better performance than other video-based face recognition approaches.

Accurate and real-time tracing of epidemic sources is critical for epidemic origin analyses and control when outbreaks of epidemic diseases occur. Such tracing requires the simultaneous availability of information about social interactions among people as well as their body vital signs. Existing epidemic control methods are limited due to their inability to collect the above two types of information at the same time. In this paper, for the first time, we propose integrating wireless body area networks (WBANs) for body vital signs collection with mobile phones for social interaction sensing to achieve the desired epidemic source tracing. In particular, we design a mobile phone capability driven hierarchical social interaction detection framework integrated with WBANs. With this framework, we further propose a set of epidemic source tracing and control algorithms including genetic algorithm based search and dominating set identification algorithms to effectively identify epidemic sources and inhibit epidemic spread. We have also conducted extensive simulations, analyses, and case studies based on real data sets, which demonstrate the accuracy and effectiveness of our proposed solutions.

With smartphones' meteoric growth in recent years, leaking sensitive information from them has become an increasingly critical issue. Such sensitive information can originate from smartphones themselves (e.g., location information) or from many Internet sources (e.g., bank accounts, emails). While prior work has demonstrated information flow tracking's (IFT's) effectiveness at detecting information leakage from smartphones, it can only handle a limited number of sensitive information sources. This paper presents a novel IFT tagging strategy using differentiated and dynamic tagging. We partition information sources into differentiated classes and store them in fixed-length tags. We adjust tag structure based on time-varying received information sources. Our tagging strategy enables us to track at runtime numerous information sources in multiple classes and rapidly detect information leakage from any of these sources. We design and implement D2Taint, an IFT system using our tagging strategy on real-world smartphones. We experimentally evaluate D2Taint's effectiveness with 84 real-world applications downloaded from Google Play. D2Taint reports that over 80% of them leak data to third-party destinations; 14% leak highly sensitive data. Our experimental evaluation using a standard benchmark tool illustrates D2Taint's effectiveness at handling many information sources on smartphones with moderate runtime and space overhead.

Human localization is an enabling technology for many mobile applications. As more and more people carry mobile phones with them, we can now localize a person by localizing his mobile phone. However, it is observed that presence of human bodies introduces heavy interference to mobile phone signals. This has been one of the major causes of inaccurate wireless localization for humans. In this paper, we propose using video cameras to help estimate human body's interference on mobile device's signals. We combine human orientation detection and human/phone/AP relative position inference estimation to better measure how a human blocks or reflects wireless signals. We have also developed a signal distortion compensation model. Based on these technologies, we have implemented a human localization system called EV-Human. Real world experiments show that our EV-system can accurately and robustly localize humans.

In this paper, we study the problem of wireless coverage in bounded areas. Coverage is one of the fundamental requirements of wireless networks. There has been considerable research on optimal coverage of infinitely large areas. However, in the real world, the deployment areas of wireless networks are always geographically bounded. It is a much more challenging and significant problem to find optimal deployment patterns to cover bounded areas. In this paper, we approach this problem starting from the development of tight lower bounds on the number of nodes needed to cover a bounded area. Then we design several deployment patterns for different kinds of convex and concave shapes such as rectangles and L-shapes. These patterns require only few more nodes than the theoretical lower bound, and can achieve efficient coverage. We have also carefully addressed and evaluated practical conditions such as coverage modeling and connectivity regarding our deployment patterns.

This paper provides a novel side-view face authentication method based on discrete wavelet transform and random forest. A subset selection method that increases the number of training samples and allows subsets to preserve the global information is presented. The authentication method can be summarized to have the following steps: profile extraction, wavelet decomposition, subset splitting and random forest verification. The new method takes the advantage of wavelet's localization property in both frequency and spatial domains, while maintaining the generalized properties of random forest. The implementation of the proposed method is computationally feasible and the experimental results show that the performance is satisfactory. Future improvements are discussed in the paper.

ABSTRACT Recently, the direct sequence spread spectrum (DSSS)‐based technique has been proposed to trace anonymous network flows. In this technique, homogeneous pseudo‐noise (PN) codes are used to modulate multiple bit signals that are embedded into the target flow as watermarks. This technique could be maliciously used to degrade an anonymous communication network. In this paper, we propose an effective single flow‐based scheme to detect the existence of these watermarks. Our investigation shows that, even if we have no knowledge of the applied PN code, we are still able to detect malicious DSSS watermarks via mean‐square autocorrelation (MSAC) of a single modulated flow's traffic rate time series. MSAC shows periodic peaks because of self‐similarity in the modulated traffic caused by homogeneous PN codes that are used in modulating multiple bit signals. Our scheme has low complexity and does not require any PN code synchronization. We evaluate this detection scheme's effectiveness via simulations. Our results demonstrate a high detection rate with a low false positive rate. Real‐world experiments on Tor also validate the feasibility of the detection scheme. Our scheme is more flexible and accurate than the existing multiflow‐based approach in DSSS watermark detection. We also present a theory for reconstructing the DSSS code once the DSSS code length is known and simulations validate the feasibility. Copyright © 2012 John Wiley & Sons, Ltd.

In this paper, we present a study on the anonymity of Anonymizer, a well-known commercial anonymous communication system. We discovered the architecture of Anonymizer and found that the size of web packets in the Anonymizer network can be very dynamic at the client. Motivated by this finding, we investigated a class of novel packet size-based covert channel attacks against Anonymizer. The attacker between a website and the Anonymizer server can manipulate the web packet size and embed secret signal symbols into the target traffic. An accomplice at the user side can sniff the traffic and recognize the secret signal. In this way, the anonymity provided by Anonymizer is compromised. We developed intelligent and robust algorithms to cope with the packet size distortion incurred by Anonymizer and Internet. We developed techniques to make the attack harder to detect: 1) We pick up right packets of web objects to manipulate to preserve the regularity of the TCP packet size dynamics, which can be measured by the Hurst parameter; 2) We adopt the Monte Carlo sampling technique to preserve the distribution of the web packet size despite manipulation. We have implemented the attack over Anonymizer and conducted extensive analytical and experimental evaluations. It is observed that the attack is highly efficient and requires only tens of packets to compromise the anonymous web surfing via Anonymizer. The experimental results are consistent with our theoretical analysis.

Abstract—Wide range wireless networks often suffer from annoying service deterioration due to fickle wireless environment. This is especially the case with passengers on long distance train (LDT) to connect onto the Internet. To improve the service quality of wide range wireless networks, we present the DragonNet protocol with its implementation. The DragonNet system is a chained gateway which consists of a group of interlinked DragonNet routers working specifically for mobile chain transport systems. The protocol makes use of the spatial diversity of wireless signals that not all spots on a surface see the same level of radio frequency radiation. In the case of a LDT of around 500 meters, it is highly possible that some of the spanning routers still see sound signal quality, when the LDT is partially blocked from wireless Internet. DragonNet protocol fully utilizes this feature to amortize single point router failure over the whole router chain by intelligently rerouting traffics on failed ones to sound ones. We have implemented the DragonNet system and tested it in real railways over a period of three months. Our results have pinpointed two fundamental contributions of DragonNet protocol. First, DragonNet significantly reduces average temporary communication blackout (i.e. no Internet connection) to 1.5 seconds compared with 6 seconds that without DragonNet protocol. Second, DragonNet efficiently doubles the aggregate throughput on average.

Small talk is an important social lubricant that helps people, especially strangers, initiate conversations and make friends with each other in physical proximity. However, due to difficulties in quickly identifying significant topics of common interest, real-world small talk tends to be superficial. The mass popularity of mobile phones can help improve the effectiveness of small talk. In this paper, we present E-SmallTalker, a distributed mobile communications system that facilitates social networking in physical proximity. It automatically discovers and suggests topics such as common interests for more significant conversations. We build on Bluetooth Service Discovery Protocol (SDP) to exchange potential topics by customizing service attributes to publish non-service-related information without establishing a connection. We propose a novel iterative Bloom filter protocol that encodes topics to fit in SDP attributes and achieves a low false-positive rate. We have implemented the system in Java ME for ease of deployment. Our experiments on real-world phones show that it is efficient enough at the system level to facilitate social interactions among strangers in physical proximity. To the best of our knowledge, E-SmallTalker is the first distributed mobile system to achieve the same purpose.

Recent years have witnessed mass proliferation of mobile devices with rich wireless communication capabilities as well as emerging mobile device based information dissemination applications that leverage these capabilities. This paper proposes TurfCast, a novel information dissemination service that selectively broadcasts information in particular “turfs,” abstract logical spaces in which receivers are situated. Such turfs can be temporal or spatial based on receivers' lingering time or physical areas, respectively. TurfCast has many applications such as electronic proximity advertising and mobile social networking. To enable TurfCast, we propose two supporting technologies: TurfCode and TurfBurst. TurfCode is a nested 0-1 fountain code that enables the broadcaster to transmit either all information or none at all to receivers. TurfBurst exploits the Shannon bound to differentiate among receivers: those who cannot receive information fast enough receive none at all, even if they linger near the broadcaster. We implement TurfCast on real-world devices and conduct experiments in both indoor and outdoor environments. Our experimental results illustrate TurfCast's potential for controlling information dissemination in wireless networks.

Video cameras have been deployed at almost every critical location, and they keep generating huge volumes of video data. The current visual processing technologies are not efficient in handling all these data for surveillance purposes, and a large amount of human power is needed to process them. In this paper, we propose the E-V system, which uses electronic footprints to help sort through this swamp of data. Electronic footprints are wireless signals emitted by mobile devices carried by people. They are ubiquitous and amenable to collection and indexing. We study how to use electronic footprints to help quickly and accurately identify object's appearance model from large volumes of video data. We have formulated the problem and provided efficient algorithms to achieve the identification on large data sets. Real world experiments and large-scale simulations have been done, which confirms the feasibility and efficiency of the proposed algorithms.

Nowadays, an increasing number of objects can be represented by their wireless electronic identifiers. For example, people can be recognized by their phone numbers or their phones' WiFi' MAC addresses and products can be identified by their RFID numbers. Localizing objects with electronic identifiers is increasingly important as our lives become increasingly "digitalized". However, traditional wireless localization techniques cannot meet the fast growing needs of accurate and cost efficient localization. Some of these techniques require expensive hardware to achieve high accuracy, which is impractical for massive deployment. Others, such as WiFi RSSI based localization, are inaccurate and not robust to environmental noise. In this paper, we propose a new localization technique called EV-Loc. In EV-Loc, we use visual signals to help improve the accuracy of wireless localization. Our technique fully leverages visual signals' high accuracy and electronic signals' pervasiveness. To effectively couple these two signals, we design an E-V match engine to find the correspondence between an object's electronic identifier and its visual appearance. We implement our technique on mobile devices and evaluate it in real-world scenarios. The localization error is less than 1 m. We also evaluate our approach using large scale simulations. The results show that our approach is accurate and robust.

Various low-latency anonymous communication systems such as Tor and Anonymizer have been designed to provide anonymity service for users. In order to hide the communication of users, most of the anonymity systems pack the application data into equal-sized cells (e.g., 512 B for Tor, a known real-world, circuit-based, low-latency anonymous communication network). Via extensive experiments on Tor, we found that the size of IP packets in the Tor network can be very dynamic because a cell is an application concept and the IP layer may repack cells. Based on this finding, we investigate a new cell-counting-based attack against Tor, which allows the attacker to confirm anonymous communication relationship among users very quickly. In this attack, by marginally varying the number of cells in the target traffic at the malicious exit onion router, the attacker can embed a secret signal into the variation of cell counter of the target traffic. The embedded signal will be carried along with the target traffic and arrive at the malicious entry onion router. Then, an accomplice of the attacker at the malicious entry onion router will detect the embedded signal based on the received cells and confirm the communication relationship among users. We have implemented this attack against Tor, and our experimental data validate its feasibility and effectiveness. There are several unique features of this attack. First, this attack is highly efficient and can confirm very short communication sessions with only tens of cells. Second, this attack is effective, and its detection rate approaches 100% with a very low false positive rate. Third, it is possible to implement the attack in a way that appears to be very difficult for honest participants to detect (e.g., using our hopping-based signal embedding).

In this paper, we study the optimal deployment pattern problem in wireless sensor networks (WSNs). We propose a new set of patterns, particularly when sensors' communication range ($r_{\rm c}$) is relatively small compared to their sensing range ($r_{\rm s}$), and prove their optimality. In this study, we discover an interesting phenomenon—pattern mutation. To the best of our knowledge, this is the first time that mutation in pattern deployments has been discovered. This phenomenon, which contradicts the conjecture presented in a previous work that there exists a universal elemental pattern among optimal pattern deployment, significantly furthers our understanding of optimal patterns in WSNs.

This paper presents an empirical study on the performance of mobile High Speed Packet Access (a 3.5G cellular standard usually abbreviated as HSPA) networks in Hong Kong via extensive field tests. Our study, from the viewpoint of end users, covers virtually all possible mobile scenarios in urban areas, including subways, trains, off-shore ferries, and city buses. We have confirmed that mobility has largely negative impacts on the performance of HSPA networks, as fast-changing wireless environment causes serious service deterioration or even interruption. Meanwhile, our field experiment results have shown unexpected new findings and thereby exposed new features of the mobile HSPA networks, which contradict commonly held views. We surprisingly find out that mobility can improve fairness of bandwidth sharing among users and traffic flows. Also, the triggering and final results of handoffs in mobile HSPA networks are unpredictable and often inappropriate, thus calling for fast reacting fallover mechanisms. Moreover, we find that throughput performance does not monotonically decrease with increased mobility level. We have conducted in-depth research to furnish detailed analysis and explanations to what we have observed. We conclude that mobility is a double-edged sword for HSPA networks. To the best of our knowledge, this is the first public report on a large-scale empirical study on the performance of commercial mobile HSPA networks.

In this paper, we propose E-Shadow, a distributed mobile phone-based local social networking system. E-Shadow has two main components: (1) Local profiles. They enable EShadow users to record and share their names, interests, and other information with fine-grained privacy controls. (2) Mobile phone based local social interaction tools. E-Shadow provides mobile phone software that enables rich social interactions. The software maps proximate users' local profiles to their human owners and enables user communication and content sharing. We have designed and implemented E-Shadow on mobile phones. In our E-Shadow system, we allow users to perform dynamic and layered information publishing, making use of interpersonal relevance. Our system also provides a mechanism to help users perform direction-driven localization of an E-Shadow and match it with its owner. Experiments on real world Windows Mobile phones and large-scale simulations show that our system disseminates information efficiently and helps receivers find the direction of a specific E-Shadow with accuracy. We believe our E-Shadow concept and system can lead to a more tightly-knit temporary community in one's physical vicinity.

Anonymizer is a proprietary anonymous communication system. We discovered its architecture and found that the size of web packets through Anonymizer are very dynamic at the client. Motivated by this finding, we investigated a novel packet size based covert channel attack, against the anonymity service. In the attack, one attacker manipulates the web packet size between the web server and Anonymizer and embed signal symbols into the target traffic. An accomplice at the user side can sniff the traffic and recognize the secret signal. We developed intelligent and robust algorithms to cope with the packet size distortion incurred by Anonymizer and Internet. We developed several techniques to make the attack harder to detect: (i) We pick up right packets of web objects to manipulate in order to preserve the regularity of the TCP packet size dynamics; (ii) We adopt the Monte Carlo sampling technique to preserve the distribution of the web packet size despite manipulation. We have implemented the attack over Anonymizer and conducted extensive analysis and experimental evaluations. It is observed that the attack is highly efficient and requires only tens of packets to compromise the anonymous web surfing. The experimental results are consistent with our theoretical analysis.

Wide range wireless networks often suffer from annoying service deterioration due to fickle wireless environment. This is especially the case with passengers on long distance train (LDT) to connect onto the Internet. To improve the service quality of wide range wireless networks, we present the DragonNet protocol with its implementation. The DragonNet system is a chained gateway which consists of a group of interlinked DragonNet routers working specifically for mobile chain transport systems. The protocol makes use of the spatial diversity of wireless signals that not all spots on a surface see the same level of radio frequency radiation. In the case of a LDT of around 500 meters, it is highly possible that some of the spanning routers still see sound signal quality, when the LDT is partially blocked from wireless Internet. DragonNet protocol fully utilizes this feature to amortize single point router failure over the whole router chain by intelligently rerouting traffics on failed ones to sound ones. We have implemented the DragonNet system and tested it in real railways over a period of three months. Our results have pinpointed two fundamental contributions of DragonNet protocol. First, DragonNet significantly reduces average temporary communication blackout (i.e. no Internet connection) to 1.5 seconds compared with 6 seconds that without DragonNet protocol. Second, DragonNet efficiently doubles the aggregate throughput on average.

In this paper, we address a new unexplored problem - what are the optimal patterns to achieve connected coverage in wireless networks with directional antennas. As their name implies, directional antennas can focus their transmission energy in a certain direction. This feature leads to lower cross-interference and larger communication distance. It has been shown that with proper scheduling mechanisms, directional antennas may substantially improve networking performance in wireless networks. In this paper, we propose a set of optimal patterns to achieve full coverage and global connectivity under two different antenna models, i.e., the sector model and the knob model. We also introduce with detailed analysis several fundamental theorems and conjectures. Finally, we examine a more realistic physical model, where there might be strong interference, and both the sensing range and the communication range might be irregular. The results show that our designed patterns work well even in unstable and fickle physical environments.

In this paper, we propose P3-coupon, a Prompt and Privacy-preserving electronic coupon distribution system based on a Probabilistic one-ownership forwarding algorithm. In this algorithm, only one hop of forwarder (coupon owner) information instead of the complete forwarder list is recorded to keep the coupon short and privacy-preserving. Such information is updated probabilistically following two ownership flipping models, namely, One-Flip and Always-Flip models. We also use a Bluetooth Service Discovery Protocol (SDP) toolkit to enable fast, configuration-free coupon exchange. We have implemented the system in Java ME. Our experiments on real world mobile phones, such as Nokia and Samsung phones, and large scale simulations show that our system is efficient in peer to peer coupon distribution and capable of massive deployment. We believe our key methodology can serve as a general framework for facilitating information propagation on mobile phones, which requires promptness and privacy protection.

Active worms pose major security threats to the Internet. This is due to the ability of active worms to propagate in an automated fashion as they continuously compromise computers on the Internet. Active worms evolve during their propagation, and thus, pose great challenges to defend against them. In this paper, we investigate a new class of active worms, referred to as Camouflaging Worm (C-Worm in short). The C-Worm is different from traditional worms because of its ability to intelligently manipulate its scan traffic volume over time. Thereby, the C-Worm camouflages its propagation from existing worm detection systems based on analyzing the propagation traffic generated by worms. We analyze characteristics of the C-Worm and conduct a comprehensive comparison between its traffic and nonworm traffic (background traffic). We observe that these two types of traffic are barely distinguishable in the time domain. However, their distinction is clear in the frequency domain, due to the recurring manipulative nature of the C-Worm. Motivated by our observations, we design a novel spectrum-based scheme to detect the C-Worm. Our scheme uses the Power Spectral Density (PSD) distribution of the scan traffic volume and its corresponding Spectral Flatness Measure (SFM) to distinguish the C-Worm traffic from background traffic. Using a comprehensive set of detection metrics and real-world traces as background traffic, we conduct extensive performance evaluations on our proposed spectrum-based detection scheme. The performance data clearly demonstrates that our scheme can effectively detect the C-Worm propagation. Furthermore, we show the generality of our spectrum-based scheme in effectively detecting not only the C-Worm, but traditional worms as well.

Small talk is an important social lubricant that helps people, especially strangers, initiate conversations and make friends with each other in physical proximity. However, due to difficulties in quickly identifying significant topics of common interest, real-world small talk tends to be superficial. The mass popularity of mobile phones can help improve the effectiveness of small talk. In this paper, we present E-SmallTalker, a distributed mobile communications system that facilitates social networking in physical proximity. It automatically discovers and suggests topics such as common interests for more significant conversations. We build on Bluetooth Service Discovery Protocol (SDP) to exchange potential topics by customizing service attributes to publish non-service-related information without establishing a connection. We propose a novel iterative Bloom filter (IBF) protocol that encodes topics to fit in SDP attributes and achieves a low false positive rate. We have implemented the system in Java ME for ease of deployment. Our experiments on real-world phones show that it is efficient enough at the system level to facilitate social interactions among strangers in physical proximity. To the best of our knowledge, E-SmallTalker is the first distributed mobile system to achieve the same purpose.

In this paper, we study the optimal deployment pattern problem in wireless sensor networks (WSNs). We propose a new set of patterns, particularly when sensors' communication range (rc) is relatively small compared with their sensing range (rs), and prove their optimality among regular patterns. In this study, we discover a surprising and interesting phenomenon-pattern mutation. This phenomenon contradicts the conjecture presented in a previous work that there exists a universal elemental pattern among optimal pattern evolution and that pattern evolution is continuous. For example, we find mutation happens among the patterns for full-coverage and 3-connectivity when rc/rs= 1.0459, among the patterns for full-coverage and 4-connectivity when rc/rs= 1.3903, and among the patterns for full-coverage and 5-connectivity when rc/rs= 1.0406. To the best of our knowledge, this is the first time that mutation in pattern evolution has been discovered. Also, our work further completes the exploration of optimal patterns in WSNs.

Malicious shellcodes are segments of binary code disguised as normal input data. Such shellcodes can be injected into a target process's virtual memory. They overwrite the process's return addresses and hijack control flow. Detecting and filtering out such shellcodes is vital to prevent damage. In this paper, we propose a new malicious shellcode detection methodology in which we take snapshots of the process's virtual memory before input data are consumed, and feed the snapshots to a malicious shellcode detector. These snapshots are used to instantiate a runtime environment that emulates the target process's input data consumption to monitor shellcodes' behaviors. The snapshots can also be used to examine the system calls that shellcodes invoke, these system call parameters, and the process's execution flow. We implement a prototype system in Debian Linux with kernel version 2.6.26. Our extensive experiments with real traces and thousands of malicious shellcodes illustrate our system's performance with low overhead and few false negatives and few false positives.

This paper presents an empirical study on the performance of mobile High Speed Packet Access (HSPA, a 3.5G cellular standard) networks in Hong Kong via extensive field tests. Our study, from the viewpoint of end users, covers virtually all possible mobile scenarios in urban areas, including subways, trains, off-shore ferries and city buses. We have confirmed that mobility has largely negative impacts on the performance of HSPA networks, as fast-changing wireless environment causes serious service deterioration or even interruption. Meanwhile our field experiment results have shown unexpected new findings and thereby exposed new features of the mobile HSPA networks, which contradict commonly held views. We surprisingly find out that mobility can improve fairness of bandwidth sharing among users and traffic flows. Also the triggering and final results of handoffs in mobile HSPA networks are unpredictable and often inappropriate, thus calling for fast reacting fallover mechanisms. We have conducted in-depth research to furnish detailed analysis and explanations to what we have observed. We conclude that mobility is a double-edged sword for HSPA networks. To the best of our knowledge, this is the first public report on a large scale empirical study on the performance of commercial mobile HSPA networks.

Low-connectivity and full-coverage three dimensional Wireless Sensor Networks (WSNs) have many real-world applications. By low connectivity, we mean there are at least k disjoint paths between any two sensor nodes in a WSN, where k ≤ 4. In this paper, we design a set of patterns to achieve 1-, 2-, 3- and 4-connectivity and full-coverage, and prove their optimality under any value of the ratio of communication range rcover sensing range rs, among regular lattice deployment patterns. We further investigate the evolutions among all the proposed low-connectivity patterns. Finally, we study the proposed patterns under several practical settings.

In this paper, we study optimal deployment in terms of the number of sensors required to achieve four-connectivity and full coverage under different ratios of sensors' communication range (denoted by rc) to their sensing range (denoted by rs). We propose a new pattern, the Diamond pattern, which can be viewed as a series of evolving patterns. When rc/rs¿ ¿(3), the Diamond pattern coincides with the well-known triangle lattice pattern; when rc/rs¿ ¿(2), it degenerates to a Square pattern (i.e., a square grid). We prove that our proposed pattern is asymptotically optimal when rc/rs> ¿(2) to achieve four-connectivity and full coverage. We also discover another new deployment pattern called the Double-strip pattern. This pattern provides a new aspect to research on optimal deployment patterns. Our work is the first to propose an asymptotically optimal deployment pattern to achieve four-connectivity and full coverage for WSNs. Our work also provides insights on how optimal patterns evolve and how to search for them.

In this paper, we study deployment patterns to achieve full coverage andk-connectivity(k≤ 6) under different ratios of the sensor communication range (denoted byRc) to the sensing range (denoted byRs) for homogeneous wireless sensor networks (WSNs). In particular, we propose new patterns for 3- and 5-connectivity. We also discover that there exists a hexagon-based universally elemental pattern that can generate all known optimal patterns. The previously proposed Voronoi-based approach cannot be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon-based methodology. We prove the optimality of deployment patterns to achieve 3-connectivity, 4-connectivity, and 5-connectivity for certain ranges ofRc/Rs, respectively, and prove the optimality of deployment patterns to achieve 6-connectivity under all ranges ofRc/Rs.

Null data frames are a special but important type of frames in IEEE 802.11 WLANs. They are widely used in 802.11 WLANs for control purposes such as power management, channel scanning, and association keeping alive. The wide applications of null data frames come from their salient features such as lightweight frame format and implementation flexibility. However, such features can be taken advantage of by malicious attackers to launch a variety of attacks on 802.11 WLANs. In this paper, we identify potential security vulnerabilities in current null data frame applications in 802.11 WLANs. We then study two types of attacks taking advantage of these vulnerabilities in detail that are functionality-based Denial-of-Service attack and implementation-based fingerprinting attack. We also evaluate their effectiveness based on extensive experiments. Furthermore, we design and implement novel defense mechanisms against the attacks, and evaluate their effectiveness based on extensive experiments. Although our proposed defenses help alleviate the vulnerabilities, completely eliminating the vulnerabilities brought by null data frames remains an open issue. Finally, we point out that our work has broader impact in that similar vulnerabilities exist in many other networks due to the adoption of simple and lightweight messages for control purpose.

Various low-latency anonymous communication systems such as Tor and Anoymizer have been designed to provide anonymity service for users. In order to hide the communication of users, many anonymity systems pack the application data into equal-sized cells (e.g., 512 bytes for Tor, a known real-world, circuit-based low-latency anonymous communication network). In this paper, we investigate a new cell counter based attack against Tor, which allows the attacker to confirm anonymous communication relationship among users very quickly. In this attack, by marginally varying the counter of cells in the target traffic at the malicious exit onion router, the attacker can embed a secret signal into the variation of cell counter of the target traffic. The embedded signal will be carried along with the target traffic and arrive at the malicious entry onion router. Then an accomplice of the attacker at the malicious entry onion router will detect the embedded signal based on the received cells and confirm the communication relationship among users. We have implemented this attack against Tor and our experimental data validate its feasibility and effectiveness. There are several unique features of this attack. First, this attack is highly efficient and can confirm very short communication sessions with only tens of cells. Second, this attack is effective and its detection rate approaches 100% with a very low false positive rate. Third, it is possible to implement the attack in a way that appears to be very difficult for honest participants to detect (e.g. using our hopping-based signal embedding).

In this paper, we study the problem of constructing full-coverage three dimensional networks with multiple connectivity. We design a set of patterns for full coverage and two representative connectivity requirements, i.e. 14- and 6-connectivity. We prove their optimality under any ratio of the communication range over the sensing range among regular lattice deployment patterns. We also conduct a study on the proposed patterns under practical settings. To our knowledge, our work is the first one that provides deployment patterns with proven optimality that achieve both coverage and connectivity in three dimensional networks.

Recently, the direct sequence spread-spectrum (DSSS)-based technique has been proposed to trace anonymous network flows. In this technique, homogeneous pseudo-noise (PN) codes are used to modulate multiple-bit signals that are embedded into the target flow as watermarks. This technique could be maliciously used to degrade an anonymous communication network. In this paper, we propose a simple single flow-based scheme to detect the existence of these watermarks. Our investigation shows that even if we have no knowledge of the applied PN code, we are still able to detect malicious DSSS watermarks via mean-square autocorrelation (MSAC) of a single modulated flow's traffic rate time series. MSAC shows periodic peaks due to self-similarity in the modulated traffic caused by homogeneous PN codes that are used in modulating multiple-bit signals. Our scheme has low complexity and does not require any PN-code synchronization. We evaluate this detection scheme's effectiveness via simulations and real-world experiments on Tor. Our results demonstrate a high detection rate with a low false positive rate. Our scheme is more flexible and accurate than an existing multi-flow-based approach in DSSS watermark detection.

802.11 wireless networks have gained ever greater popularity nowadays. Apart from static wireless connections, people begin to expect more user-friendly features from this kind of networks, such as support for seamless roaming. In this paper, we study the handoff process in large AP-dense 802.11 networks, which is one of the most common forms of WiFi under usage. A series of field experiments are carried out and some critical handoff parameters are evaluated. With some newly discovered features, i.e. differentiated probe response time and rich AP information hidden in wireless traffic, we have managed to significantly improve the essential process of AP scan, a bottleneck towards fast and smooth handoffs. The solution is collectively called D-Scan (Scan in AP-Dense 802.11 networks). Real experiments are conducted to show the superiority of our solution.

In this paper, we introduce a new type of coverage for wireless sensor networks, called Directed Coverage (D-coverage). Basically, D-coverage is the coverage provided by a sensor network monitoring an area between two boundaries, through which the intruder attempts to penetrates the area. We also study how to measure the quality of D-coverage. Our first evaluation approach is a projection-based simple approach, while our second approach is a more comprehensive Markov chain based approach. Our evaluation approaches can accurately evaluate the quality and provide good guidelines for sensor network deployment and run-time repair.

Smartphones have been widely used in recent years due to their capabilities of supporting many applications from simple Short Message Service messages to complicated Location-based services. It is challenging for smartphones to enable their end users to manage all applications in all possible use cases to protect privacy or sensitive data. However, the security model for smartphone users is still a two-state model in which they can do anything or absolutely nothing, and it is no longer suitable. In this paper, we propose DiffUser, a differentiated user access control model to enhance smartphone security and user privacy. DiffUser classifies smartphone users based on certain sets of user access privileges. We implement a prototype of DiffUser on real-world T-Mobile G1 smartphones. The evaluation results show that our system is lightweight and flexible.

Low-connectivity and full-coverage three dimensional Wireless Sensor Networks (WSNs) have many real-world applications. By low connectivity, we mean there are at least k disjoint paths between any two sensor nodes in a WSN, where k ≤ 4. In this paper, we design a set of patterns for these networks. In particular, we design and prove the optimality of 1- and 2-connectivity patterns under any value of the ratio of communication range rc over sensing range rs, among regular lattice deployment patterns. We further propose a set of patterns to achieve 3- and 4-connectivity patterns and investigate the evolutions among all the proposed low-connectivity patterns. Finally, we study the proposed patterns under several practical settings.

In this paper, we investigate video-based vulnerabilities in 3G Smartphones. Particularly, we design a new video-based spyware, called Stealthy Video Capturer (SVC). SVC can secretly record video information for the third party, greatly compromising Smartphone users' privacy. We implement the spyware and conduct extensive experiments on real world 3G Smartphones. Our experimental results show that the spyware can capture private video information with unremarkable power consumption, CPU and memory occupancy, hence being stealthy to Smartphone users. Moreover, SVC can naturally be resistant to almost all commercial anti-virus tools, like McAfee, Kaspersky and F-Secure mobile version. To the best of our knowledge, our work is the first one to address video-based vulnerabilities in 3G Smartphones. We expect our work will prompt serious attentions on this issue.

The current 802.11i standard can provide data confidentiality, integrity and mutual authentication in enterprise Wireless Local Area Networks (WLANs). However, secure communication can only be provided after successful authentication and a robust security network association is established. In general, the wireless link layer is not protected by the current standard in WLANs, which leads to many possible attacks, especially in public open-access wireless networks. We argue that regardless of the type of network under consideration, link-layer protection and data confidentiality are of great importance in wireless applications. In this paper, we first identify and analyze the security issues ignored by the current 802.11 security standard. Then we propose our solution to patch the current 802.11i standard and address all those issues with a new dummy authentication key-establishment algorithm. Dummy means no real authentication for a user. In dummy authentication, we apply public-key cryptography's key-establishment technique to the 802.11 MAC protocol. Our solution can provide link-layer data encryption in open-access wireless networks, separate session encryption keys for different users, and protection for important frames such as management and null data frames as well as Extensible Authentication Protocol (EAP) messages.

Sensors may fail due to various reasons such as heat, malicious activity, environmental hazards, extended use, and lack of power. As more and more sensors fail, certain desired properties such as barrier coverage will diminish and eventually fall below a desired level. In such a case, the network will have to be repaired. It is therefore desirable to have mechanisms to monitor network properties. In this article, we are interested in measuring the quality of barrier coverage, which is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. In the literature, researchers only consider whether or not a sensor network provides barrier coverage. This is equivalent to measuring its quality as either 0 or 1. We believe quality of barrier coverage is not binary and propose a metric for measuring it. If the measured quality is short of a desired value, we further identify all local regions that need to be repaired. The identified regions are minimal in the sense that if one of them is not repaired then the resulting network will still be short of quality. We also discuss how to actually repair a region.

Internet threat monitoring (ITM) systems have been deployed to detect widespread attacks on the Internet in recent years. However, the effectiveness of ITM systems critically depends on the confidentiality of the location of their monitors. If adversaries learn the monitor locations of an ITM system, they can bypass the monitors and focus on the uncovered IP address space without being detected. In this paper, we study a new class of attacks, the invisible LOCalization (iLOC) attack. The iLOC attack can accurately and invisibly localize monitors of ITM systems. In the iLOC attack, the attacker launches low-rate port-scan traffic, encoded with a selected pseudonoise code (PN-code), to targeted networks. While the secret PN-code is invisible to others, the attacker can accurately determine the existence of monitors in the targeted networks based on whether the PN-code is embedded in the report data queried from the data center of the ITM system. We formally analyze the impact of various parameters on attack effectiveness. We implement the iLOC attack and conduct the performance evaluation on a real-world ITM system to demonstrate the possibility of such attacks. We also conduct extensive simulations on the iLOC attack using real-world traces. Our data show that the iLOC attack can accurately identify monitors while being invisible to ITM systems. Finally, we present a set of guidelines to counteract the iLOC attack.

Securely authenticating a human user without assistance from any auxiliary device in the presence of powerful passive adversaries is an important and challenging problem. Passive adversaries are those that can passively monitor, intercept, and analyze every part of the authentication procedure, except for an initial secret shared between the user and the server. In this paper, we propose a new secure authentication scheme called predicate-based authentication service (PAS). In this scheme, for the first time, the concept of a predicate is introduced for authentication. We conduct analysis on the proposed scheme and implement its prototype system. Our analytical data and experimental data illustrate that the PAS scheme can simultaneously achieve a desired level of security and user friendliness.

Null data frames are a special but important type of frames in IEEE 802.11 based wireless local area networks (e.g., 802.11 WLANs). They are widely used for power management, channel scanning and association keeping alive. The wide applications of null data frames come from their salient features such as lightweight frame format and implementation flexibility. However, such features can be taken advantage of by malicious attackers to launch a variety of attacks. In this paper, we identify the potential security vulnerabilities in the current applications of null data frames. We then study two types of attacks taking advantage of these vulnerabilities in detail, and evaluate their effectiveness based on extensive experiments. Finally, we point out that our work has broader impact in that similar vulnerabilities exist in many other networks.

We study the issue of optimal deployment to achieve four connectivity and full coverage for wireless sensor networks (WSNs) under different ratios of sensors' communication range (denoted by rc) to their sensing range (denoted by rs). We propose a "Diamond" pattern, which can be viewed as a series of different evolving patterns. When rc/rsges radic3, the Diamond pattern coincides with the well-known triangle lattice pattern; when rc/rsges radic2, it degenerates to a "Square" pattern. We prove the Diamond pattern to be asymptotically optimal when rc/rsges radic2- Our work is the first to propose an asymptotically optimal deployment pattern to achieve four connectivity and full coverage for WSNs. We hope our work will provide some insights on how optimal patterns evolve and how to search for them.

In this paper, we study a new class of attacks, theinvisibleLOCalization (iLOC) attack, which can accurately and invisibly localize monitors of Internet threat monitoring (ITM) systems, a class of widely deployed facilities to characterize Internet threats, such as worm propagation, denial-of-service (DoS) attacks. In theiLOCattack, the attacker launches low-rate port-scan traffic, encoded with a selectedpseudo-noisecode(PN- code), to targeted networks. While the secret PN-code is invisible to others, the attacker can accurately determine the existence of monitors in the targeted networks based on whether the PN-code is embedded in the report data queried from the data center of the ITM system. We conduct extensive simulations on theiLOCattack using real-world traces. Our data demonstrate that theiLOCattack can accurately identify monitors while remaining invisible to the ITM. Finally, we present a set of guidelines to counteract theiLOCattack.

In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by Rc) over sensing range (denoted by Rs) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when Rc/Rs ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of Rc/Rs. With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k≤6) is complete, for the first time.

Sensors may fail due to various reasons such as heat, malicious activity, environmental hazards, extended use, and lack of power. As more and more sensors fail, certain desired properties such as barrier coverage will diminish and eventually fall below a desired level. In such a case, the network will have to be repaired. It is therefore desirable to have mechanisms to monitor network properties. In this paper, we are interested in measuring the quality of barrier coverage. In the literature, researchers only consider whether or not a sensor network provides barrier coverage. This is equivalent to measuring its quality as either 0 or 1. We believe quality of barrier coverage is not binary and propose a metric for measuring it. If the measured quality is short of a desired value, we further identify all local regions that need to be repaired. The identified regions are minimum in the sense that if one of them is not repaired then the resulting network will still be short of quality. We also discuss how to actually repair a region.

In this paper, an anti-sensor network system is proposed, aiming to protect an important area from being under surveillance by an adversary's sensor nodes. The major components of the system are a set of observing points (monitors) deployed in the area of importance. The observers try to localize sensor positions using antenna arrays to measure direction of arrival (DoA) and received signal strength of the signals emitted by sensors. Once sensors are localized, additional measures are taken to physically remove or disable localized sensors. The proposed anti-sensor network system is designed to handle additional counter-measures that can be employed by sensors, including message encryption and non-uniform transmission power levels. The simulation results show the effectiveness of the proposed system and effects of counter-measures on sensor localization performance.

Law enforcement agencies need the ability to conduct electronic surveillance to combat crime, terrorism, or other malicious activities exploiting the Internet. However, the proliferation of anonymous communication systems on the Internet has posed significant challenges to providing such traceback capability. In this paper, we develop a new class of flow marking technique for invisible traceback based on direct sequence spread spectrum (DSSS), utilizing a pseudo-noise (PN) code. By interfering with a sender's traffic and marginally varying its rate, an investigator can embed a secret spread spectrum signal into the sender's traffic. The embedded signal is carried along with the traffic from the sender to the receiver, so the investigator can recognize the corresponding communication relationship, tracing the messages despite the use of anonymous networks. The secret PN code makes it difficult for others to detect the presence of such embedded signals, so the traceback, while available to investigators is, effectively invisible. We demonstrate a practical flow marking system which requires no training, and can achieve both high detection and low false positive rates. Using a combination of analytical modeling, simulations, and experiments on Tor (a popular Internet anonymous communication system), we demonstrate the effectiveness of the DSSS-basedflow marking technique.

In this paper, we study the issue of sensor network deployment using limited mobility sensors. By limited mobility, we mean that the maximum distance that sensors are capable of moving to is limited. Given an initial deployment of limited mobility sensors in a field clustered into multiple regions, our deployment problem is to determine a movement plan for the sensors to minimize the variance in number of sensors among the regions and simultaneously minimize the sensor movements. Our methodology to solve this problem is to transfer the nonlinear variance/movement minimization problem into a linear optimization problem through appropriate weight assignments to regions. In this methodology, the regions are assigned weights corresponding to the number of sensors needed. During sensor movements across regions, larger weight regions are given higher priority compared to smaller weight regions, while simultaneously ensuring a minimum number of sensor movements. Following the above methodology, we propose a set of algorithms to our deployment problem. Our first algorithm is the optimal maximum flow-based (OMF) centralized algorithm. Here, the optimal movement plan for sensors is obtained based on determining the minimum cost maximum weighted flow to the regions in the network. We then propose the simple peak-pit-based distributed (SPP) algorithm that uses local requests and responses for sensor movements. Using extensive simulations, we demonstrate the effectiveness of our algorithms from the perspective of variance minimization, number of sensor movements, and messaging overhead under different initial deployment scenarios.

An important phase of sensor networks operation is deployment of sensors in the field of interest. Critical goals during sensor networks deployment include coverage, connectivity, load balancing, etc. A class of work has recently appeared, where mobility in sensors is leveraged to meet deployment objectives. In this paper, we study deployment of sensor networks using mobile sensors. The distinguishing feature of our work is that the sensors in our model have limited mobilities. More specifically, the mobility in the sensors we consider is restricted to a flip, where the distance of the flip is bounded. We call such sensors as flip-based sensors. Given an initial deployment of flip-based sensors in a field, our problem is to determine a movement plan for the sensors in order to maximize the sensor network coverage and minimize the number of flips. We propose a minimum-cost maximum-flow-based solution to this problem. We prove that our solution optimizes both the coverage and the number of flips. We also study the sensitivity of coverage and the number of flips to flip distance under different initial deployment distributions of sensors. We observe that increased flip distance achieves better coverage and reduces the number of flips required per unit increase in coverage. However, such improvements are constrained by initial deployment distributions of sensors due to the limitations on sensor mobility

Abstract—Many wireless sensor network (WSN) applications demand secure communications. The random key predistribution ðRKPÞ protocol has been well accepted in achieving secure communications in WSNs. A host of key management protocols have been proposed based on the RKP protocol. However, due to the randomness in key distribution and strong constraint in key path construction, the RKP-based protocols can only be applied in highly dense networks, which are not always feasible in practice. In this paper, we propose a methodology called network decoupling to address this problem. With this methodology, a WSN is decoupled into a logical keysharing network and a physical neighborhood network, which significantly releases the constraint in key path construction of the RKP protocol. We design two new key management protocols, that is, RKP-DE and RKP-DEA, as well as a set of link and path dependency elimination rules in decoupled sensor networks. Our analytical and simulation data demonstrate the performance enhancement of our solutions from the perspective of connectivity and resilience and its applicability in nonhighly dense sensor networks. Index Terms—Wireless sensor networks, random key predistribution, network decoupling. 1

Active worms pose major security threats to the Internet. In this paper, we investigate a new class of active worms, i.e., camouflaging worm (C-Worm in short). The C-Worm has the capability to intelligently manipulate its scan traffic volume over time, thereby camouflaging its propagation from existing worm detection systems. We analyze characteristics of the C-Worm and conduct a comprehensive comparison between its traffic and non-worm traffic. We observe that these two types of traffic are barely distinguishable in the time domain, however, their distinction is clear in the frequency domain, due to the recurring manipulative nature of the C-Worm. Motivated by our observations, we design a novel spectrum-based scheme to detect the C-Worm. Our scheme uses the power spectral density (PSD) distribution of the scan traffic volume and its corresponding spectral flatness measure (SFM) to distinguish the C-Worm traffic from non-worm traffic. We conduct extensive performance evaluations on our proposed detection scheme against the C-Worm. The performance data clearly demonstrates that our proposed scheme can effectively detect the C-Worm propagation

Multicast services are demanded by a variety of applications. Many applications require anonymity during their communication. However, there has been very little work on anonymous multicasting and such services are not available yet. Since there are fundamental differences between multicast and unicast, the solutions proposed for anonymity in unicast communications cannot be directly applied to multicast applications. In this paper, we define the anonymous multicast system, and propose a mutual anonymous multicast (MAM) protocol including the design of a unicast mutual anonymity protocol and construction and optimization of an anonymous multicast tree. MAM is self organizing and completely distributed. We define the attack model in an anonymous multicast system and analyze the anonymity degree. We also evaluate the performance of MAM by simulations.

Secure communications are highly demanded by many wireless sensor network (WSN) applications. The random key pre-distribution (RKP) scheme has become well accepted in achieving secure communications in WSNs. However, due to its randomness in key distribution and strong constraint in key path construction, the RKP scheme can only be applied in highly dense networks, which are not always feasible in practice. In this paper, we propose a methodology called network decoupling to solve this problem. With this methodology, a wireless sensor network is decoupled into a logical key-sharing network and a physical neighborhood network, which significantly releases the constraint in key path construction of the RKP scheme. We design a secure neighbor establishment protocol (called RKP-DE) as well as a set of link and path dependency elimination rules in decoupled wireless sensor networks. Our analytical and simulation data demonstrate the performance enhancement of our solution and its applicability in non-highly dense wireless sensor networks

It is well-known that placing disks in the triangular lattice pattern is optimal for achieving full coverage on a plane. With the emergence of wireless sensor networks, however, it is now no longer enough to consider coverage alone when deploying a wireless sensor network; connectivity must also be con-sidered. While moderate loss in coverage can be tolerated by applications of wireless sensor networks, loss in connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not enough to have a wireless sensor network just connected, it should be k-connected (for k > 1 ). In this paper, we propose an optimal deployment pattern to achieve both full coverage and 2-connectivity, and prove its optimality for all values of rc/rs, where rc is the communication radius, and rs is the sensing radius. We also prove the optimality of a previously proposed deployment pattern for achieving both full coverage and 1-connectivity, when rc/rs < √3 .Finally, we compare the efficiency of some popular regular deployment patterns such as the square grid and triangular lattice, in terms of the number of sensors needed to provide coverage and connectivity.

This paper proposes a dynamic geographic hash table for data-centric storage (DCS) in sensor networks. In DCS systems, data storage locations are determined by data name. The storage locations are obtained through the use of a geographic hash table (GHT) that maps data names to geographic locations. Traditional DCS systems use a static hash function for this purpose, resulting in a static set of nodes serving the network throughout its lifetime. Hence, these nodes may experience unbalanced resource utilization problems and the network will not be capable of dealing with network dynamics such as new sensor deployments or runtime sensor failures. We address these problems by proposing a dynamic GHT solution that relies on two schemes: 1) a temporal-based geographic hash table to achieve overall load balancing among sensor nodes over time; and 2) a location selection scheme based on node contribution potential to proactively adapt the system to network dynamics. Our performance evaluations show that the dynamic GHT can alleviate the resource utilization problem of DCS systems and can prolong the network lifetime significantly

Sensor nodes being small in size and distributively deployed, are vulnerable to physical attacks that attempt to physically destroy sensors in the sensor network. Generally speaking, physical attacks in sensor networks can be classified into two types: blind physical attacks and search-based physical attacks. In blind attacks, sensors are destroyed using brute-force approaches (like bombs/grenades etc.). The advantage here is the rapidness in destroying sensors. The downside however, is the fact that the deployment field also suffers significant casualties. If the attacker wishes to preserve the deployment field, the attacker will conduct search-based attacks by searching for sensors in the field and destroying only the sensors. While this preserves the deployment field, the attack process is slow. In this paper, we present policy-driven physical attacks, where the bias between the twin objectives of the attacker (rapidly destroying sensors, and preserving the deployment field) is modeled as a policy for the attacker. In policy-driven physical attacks, the attacker walks through the sensor network deployment field using signal detecting equipment to locate active sensors. Depending on the attacker's policy, the attacker takes different actions during the attack process. Based on detailed performance measurement, we observe that the policy has impacts on the network performance and destruction in the deployment field, demonstrating that the attacker can achieve desired bias in its objectives under policy-driven physical attacks

In the framework of a set of clients communicating with a critical server over the Internet, a recent approach to protect communication from distributed denial of service (DDoS) attacks involves the usage of overlay systems. SOS, MAYDAY, and I3 are such systems. The architecture of these systems consists of a set of overlay nodes that serve as intermediate forwarders between the clients and the server, thereby controlling access to the server. Although such systems perform well under random DDoS attacks, it is questionable whether they are resilient to intelligent DDoS attacks which aim to infer architectures of the systems to launch more efficient attacks. In this paper, we define several intelligent DDoS attack models and develop analytical/simulation approaches to study the impacts of architectural design features of such, overlay systems on the system performance in terms of path availability between clients and the server under attacks. Our data clearly demonstrate that the system performance is indeed sensitive to the architectural features and the different features interact with each other to impact overall system performance under intelligent DDoS attacks. Our observations provide important guidelines in the design of such secure overlay forwarding systems.

In this paper, we address issues in implementing voice over IP (VoIP) services in packet switching networks. VoIP has been identified as a critical real-time application in the network QoS research community and has been implemented in commercial products. To provide competent quality of service for VoIP systems comparable to traditional PSTN systems, a call admission control (CAC) mechanism has to be introduced to prevent packet loss and over-queuing. Several well-designed CAC mechanisms, such as the site-utilization-based CAC-and the link-utilization-based CAC mechanisms have been in place. However, the existing commercial VoIP systems have not been able to adequately apply and support these CAC mechanisms and, hence, have been unable to provide QoS guarantees to voice over IP networks. We have designed and implemented a QoS-provisioning system that can be seamlessly integrated with the existing VoIP systems to overcome their weakness in offering QoS guarantees. A practical implementation of our QoS-provisioning system has been realized.

In a large-scale sensor network, the amount of data collected increases rapidly over time. Efficient data storage and retrieval in sensor networks is therefore critical to enhancing network lifetime. In this paper, we propose an adaptive zone-based storage architecture for sensor networks. Our design consists of three major components: 1) a distributed clustering algorithm that operates on a novel concept of node contribution potential, allowing the network to be clustered based on desired performance, 2) a local storage policy to reduce cross-network transmission which is resilient to node and network failures, and 3) an overlay of zone leaders to distribute queries and data efficiently. In cases where the query sources are limited to a number of fixed points in the network, we propose a query source adaptation policy to reduce network stress on overlay links. The strengths of our architecture include the ability to customize the network's desired performance at run time, its low protocol overhead, scalability and resilience to network failures.

Recent active worm propagation events show that active worms can spread in an automated fashion and flood the Internet in a very short period of time. Our previous results show that P2P systems with large number of hosts can be a potential vehicle for the active worm attacker to achieve fast worm propagation in the Internet. In this paper, we propose a region-based active immunization defense strategy in P2P systems to fight against P2P-based active worm attacks. We develop an analytical approach to evaluate the efficiency of our proposed defense strategy. Our numerical analysis results show that: although P2P-based attacks can significantly improve the attack performance by attacking vulnerable P2P systems, our proposed defense strategy can effectively slow down the worm propagation. We also observe that defense parameters such as defense list size, worm detection success ratio, and immunization rate have significant impacts on the performance of our defense strategy.

Abstract—In this paper, we address a Resource Constrained Lifetime Problem in sensor networks in an operating environment subject to physical node destructions. Specifically, given a limited number of sensors, our goal is to maximize the network lifetime and derive the deployment plan of the nodes to maximize the lifetime under physical node destructions. The problem of physical destructions due to hostile environmnets and small size of the sensors is a potent threat and severely constrains the practical lifetime of sensor networks. The lifetime problem we define is representative, practical and encompasses other versions of similar problems. We also define a representative physical attack model under which we study and solve the lifetime problem. Our solutions take into account both the energy minimization and node constraints. We make several observations in this realm of which an important one is the high sensitivity of lifetime to physical attacks highlighting the importance of our study. Our work has broad and immediate impacts to system designers during network deployments in hostile environments.

Recent active worm propagation events show that active worms can spread in an automated fashion and flood the Internet in a very short period of time. Due to the recent surge of peer-to-peer (P2P) systems with large numbers of users, P2P systems can be a potential vehicle for the active worms to achieve fast worm propagation in the Internet. In this paper, we address the issue of the impacts of active worm propagation on top of P2P systems. In particular: (1) we define a P2P system based active worm attack model and study two attack strategies (an off-line and on-line strategy) under the defined model; (2) we develop an analytical approach to analyze the propagation of active worms under the defined attack models and conduct an extensive study to the impacts of P2P system parameters, such as size, topology degree, and the structured/unstructured properties on active worm propagation. Based on numerical results, we observe that a P2P-based attack can significantly worsen attack effects (improve attack performance), and we observe that the speed of worm propagation is very sensitive to P2P system parameters. We believe that our work can provide important guidelines in design and control of P2P systems as well as overall active worm defense.

The small form factor of the sensors, coupled with the unattended and distributed nature of their deployment expose sensors to physical attacks that physically destroy sensors in the network. In this paper, we study the modeling and analysis of search-based physical attacks in sensor networks. We define a search-based physical attack model, where the attacker walks through the sensor network using signal detecting equipment to locate active sensors, and then destroys them. We consider both flat and hierarchical sensor networks. The attacker in our model uses a weighted random selection based approach to discriminate multiple target choices (normal sensors and cluster-heads) to enhance sensor network performance degradation. Our performance metric in this paper is accumulative coverage (AC), which effectively captures coverage and lifetime of the sensor network. We then conduct detailed evaluations on the impacts of search-based physic attacks on sensor network performance. Our performance data clearly show that search-based physical attacks significantly reduce sensor network performance. We observe that attack related parameters, namely attacker movement speed, detection range and accuracy have significant impacts on the attack effectiveness. We also observe that the attack effectiveness is significantly impacted by sensor network parameters, namely the frequency of communication and frequency of cluster-head rotation. We believe that our work in this paper on modeling and analyzing search-based physical attacks is an important first step in understanding their overall impacts, and effectively defending against them in the future.

In this paper, we study the issue of mobility based sensor networks deployment. The distinguishing feature of our work is that the sensors in our model have limited mobilities. More specifically, the mobility in the sensors we consider is restricted to a flip, where the distance of the flip is bounded. Given an initial deployment of sensors in a field, our problem is to determine a movement plan for the sensors in order to maximize the sensor network coverage, and minimize the number of flips. We propose a minimum-cost maximum-flow based solution to this problem. We prove that our solution optimizes both the coverage and the number of flips. We also study the sensitivity of coverage and the number of flips to flip distance under different initial deployment distributions of sensors. We observe that increased flip distance achieves better coverage, and reduces the number of flips required per unit increase in coverage. However, such improvements are constrained by initial deployment distributions of sensors, due to the limitations on sensor mobility

In this paper we study the defense of sensor networks against search-based physical attacks. We define search-based physical attacks as those, where an attacker detects sensors using signal detecting equipment and then physically destroys the detected sensors. In this paper, we propose a sacrificial node-assisted approach to defend against search-based physical attacks. The core principle of our defense is to trade short term local coverage for long term global coverage through the sacrificial node-assisted attack notification and states switching of sensors. The performance metric we use is accumulative coverage (AC), which effectively captures coverage and lifetime of the sensor networks to measure sensor network performance. Our simulation results clearly demonstrate that our defense approach can significantly decrease losses in AC even under intense search-based physical attacks.

Distributed denial of service (DDoS) attacks are currently major threats to communication in the Internet. A secure overlay services (SOS) architecture has been proposed to provide reliable communication between clients and a target under DDoS attacks. The SOS architecture employs a set of overlay nodes arranged in three hierarchical layers that controls access to the target. Although the architecture is novel and works well under simple congestion based attacks, we observe that it is vulnerable under more intelligent attacks. We generalize the SOS architecture by introducing more flexibility in layering to the original architecture. We define two intelligent DDoS attack models and develop an analytical approach to study the impacts of the number of layers, number of neighbors per node and the node distribution per layer on the system performance under these two attack models. Our data clearly demonstrate that performance is indeed sensitive to the design features and the different design features interact with each other to impact overall system performance.

Providing efficient data services is one of the fundamental requirements for wireless sensor networks. The data service paradigm requires that the application submit its requests as queries and the sensor network transmits the requested data to the application. While most existing work in this area focuses on data aggregation, not much attention has been paid to query aggregation. For many applications, especially ones with high query rates, query aggregation is very important. We study a query aggregation-based approach for providing efficient data services. In particular: (1) we propose a multi-layered overlay-based framework consisting of a query manager and access points (nodes), where the former provides the query aggregation plan and the latter executes the plan; (2) we design an effective query aggregation algorithm to reduce the number of duplicate/overlapping queries and save overall energy consumption in the sensor network Our performance evaluations show that by applying our query aggregation algorithm, the overall energy consumption can be significantly reduced and the sensor network lifetime can be prolonged correspondingly.

In this paper, we propose and analyze a methodology for providing absolute differentiated services for real-time applications. We develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and, hence, is scalable to large systems. We assume the underlying network to use static-priority schedulers. We design and analyze several priority assignment algorithms and investigate their ability to achieve higher utilization bounds. Traditionally, schedulers in differentiated services networks assign priorities on a class-by-class basis, with the same priority for each class on each router. In this paper, we show that relaxing this requirement, that is, allowing different routers to assign different priorities to classes, achieves significantly higher utilization bounds.

Anycasting has recently become an important research topic, especially for replicated servers. With anycasting, applications can request the "nearest" server for provision of desired (multimedia) service. In this paper, we study efficient distributed admission control (DAC) for anycast flows. We focus on algorithms that perform destination selection and efficient path establishment. Taking advantage of anycasting, our distributed algorithms differ from each other in their dependence on system status information. Performance data obtained through mathematical analysis and simulations show that, in terms of admission probabilities, DAC systems that are based on local status information have performance levels close to those that utilize global and dynamic status information. This renders our DAC algorithms useful not only for the network layer, but also for the application layer admission control for anycast flows.

We propose an approach to analyze the resilience to failures of structured P2P systems. The approach is Markov-chain based, and can be applied to systems with relatively stable size and uniformly distributed nodes. We apply our method to several well-known structured P2P systems. We find that finger neighbors and special neighbors have different influences on the resilience features of P2P systems. More particularly, finger neighbors have significant influence on the average path length while special neighbors influence the hit ratio. Following the above observation, we propose to add some finger neighbor(s) to nodes of the CAN (content-addressable network) system which originally have no such finger neighbor(s). We use the small-world phenomenon to form the CAN-small-world (CAN-SW) system. We then apply the proposed Markov-chain based approach to analyze its resilience. We find that the performance of the system under failures or not, has been improved significantly, particularly, in terms of the average path length.

We study countermeasures to traffic analysis attacks. A common strategy for such countermeasures is link padding. We consider systems where payload traffic is padded so that packets have either constant inter-arrival times or variable inter-arrival times. The adversary applies statistical recognition techniques to detect the payload traffic rates by using statistical measures like sample mean, sample variance, or sample entropy. We evaluate quantitatively the ability of the adversary to make a correct detection and derive closed-form formulas for the detection rate based on analytical models. Extensive experiments were carried out to validate the system performance predicted by the analytical method. Based on the systematic evaluations, we develop design guidelines for the proper configuration of a system in order to minimize the detection rate

We address the issues related to aggregation of anycast groups for scalable anycast routing. Anycast is a new network service that allows a sender to access anyone in a group that shares the same anycast address. Anycast has numerous potential applications. However, it also introduces new issues. One of the issues is that the size of the anycast routing tables is significantly increased The main goals of this study are to reduce the size of routing tables and to improve network end-to-end performance. Particularly, we propose three group-aggregation algorithms with different objectives: (1) group-aggregation for minimizing the routing table size, (2) group-aggregation for balancing interface load, and (3) integrated group-aggregation. These algorithms take full advantages of the anycast semantics. Our evaluation results show that our group-aggregation algorithms can efficiently reduce the size of routing tables by 90% while achieving high network performance in terms of the average end-to-end delay.

In this paper, we propose and analyze a methodology for providing statistical guarantees within the diffserv model in a network, that uses static-priority schedulers. We extend the previous work on statistical delay analysis and develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and hence is scalable to large systems. We systematically analyze the performance of our approaches in terms of system utilization. As expected, our experimental data show that statistical services can achieve much higher utilization than deterministic services.

We study a distributed admission control (DAC) procedure for anycast flows with QoS requirements. We focus on algorithms that perform destination selection, which is critical in anycast. Several algorithms are proposed. These algorithms differ from each other in their dependence on system status information. We also address the issue of resource reservation and re-trial control in the DAC procedure. Performance data obtained by mathematical analysis and computer simulation show that in terms of admission probabilities, DAC systems that are based on local status information can perform closely to those that utilize global and dynamic status information. We note that the latter is much more expensive and difficult to realize.

We propose and analyze a methodology for providing absolute differentiated services for real-time applications in networks that use static-priority schedulers. We extend previous work on worst-case delay analysis and develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and hence is scalable to large systems. We assume the underlying network to use static-priority schedulers. We design and analyze several priority assignment algorithms, and investigate their ability to achieve higher utilization bounds. Traditionally, schedulers in differentiated services networks assign priorities on a class-by-class basis, with the same priority for each class on each router. We show that relaxing this requirement, that is, allowing different routers to assign different priorities to classes, achieves significantly higher utilization bounds.

We propose and analyze a methodology for providing absolute differentiated services with statistical performance guarantees for real-time applications in networks that use class-based (as opposed to flow-aware) static priority schedulers. We develop a method that can be used to derive statistical delay guarantees in a flow-unaware fashion. Traditionally, both deterministic and statistical delay analysis methods either depend on schedulers that keep per-flow state information, or require detailed information about flow population at delay analysis time. The fact that no such information is needed for delay analysis allows us to perform deadline tests during system (re-)configuration time. We are so able to reduce the runtime admission control to a simple utilization test. No explicit delay computation is necessary at admission time, making this approach scalable to large systems.

This paper presents the general approach, design, implementation, and evaluation of NetCamo, which is a system to prevent traffic analysis in systems with real-time requirements. Integrated support for both security and real-time is becoming necessary for computer networks that support mission critical applications. This study focuses on how to integrate both the prevention of traffic analysis and guarantees for worst-case delays in an internetwork. We propose and analyze techniques that efficiently camouflage network traffic and correctly plan and schedule the transmission of payload traffic so that both security and real-time requirements are met. The performance evaluation shows that our NetCamo system is effective and efficient. By using the error between target camouflaged traffic and the observed (camouflaged) traffic as metric to measure the quality of the camouflaging, we show that NetCamo achieves very high levels of camouflaging without compromising real-time requirements.

We propose an approach to flow-unaware admission control which is a combination with an aggregate packet forwarding scheme, improving scalability of networks while guaranteeing end-to-end deadlines for real-time applications. We achieve this by using an off-line delay computation and verification step, which allows to reduce the overhead at admission control while keeping admission probability and resource utilization high. Our evaluation data show that our system's admission probabilities are very close to those of significantly more expensive flow-aware approaches. At the same time, the admission control overhead during flow establishment is very low. Our results therefore support the claim from the DS architecture literature that scalability can be achieved through flow aggregation without sacrificing resource utilization and with significant reduction in run time overhead.

In this paper, we present a methodology to use utilization-based admission control in guaranteed real-time communication in a scalable fashion. We make admission control scalable by using a configuration-time test to determine a safe utilization level of servers. Admission control at run-time then is reduced to simple utilization tests on the servers along the path of the new flow. Furthermore, we discuss how appropriate route selection improve utilization levels, design a safe route selection heuristic algorithm to achieve high utilization of resources, and derive two bounds on the maximum utilization level for given traffic in a network. We compare the results of our route selection heuristics with that of a shortest-path based algorithm, and find that our heuristics can achieve a much higher maximum utilization level than that of the shortest-path based algorithm.

An anycast packet is one that should be delivered to one member in a group of designated recipients. Using anycast services may considerably simplify some applications. Little work has been done on routing anycast packets. In this paper, we propose and analyze a routing protocol for anycast message. It is composed of two subprotocols: the routing table establishment subprotocol and the packet forwarding subprotocol. In the routing table establishment subprotocol, we propose four methods (SSP, MIN-D, SET, and GET) for enforcing an order among routers for the purpose of loop prevention. These methods differ from each other on information used to maintain orders, the impact on QoS, and the compatibility to the existing routing protocols. In the packet forwarding subprotocol, we propose a Weighted-Random Selection (WRS) approach for multiple path selection in order to balance network traffic. In particular, the fixed and adaptive methods are proposed to determine the weights. Both of them explicitly take into account the characteristics of distribution of anycast recipient group while the adaptive method uses the dynamic information of the anycast traffic as well. Correctness property of the protocol is formally proven. Extensive simulation is performed to evaluate our newly designed protocol. Performance data shows that the loop-prevention methods and the WRS approaches have great impact on the performance in terms of average end-to-end packet delay. In particular, the protocol using the SET or CBT loop-prevention methods and the adaptive WRS approach performs very close to a dynamic optimal routing protocol in most cases.

In this paper, we study an efficient fault-tolerant CBT multicast routing protocol. With our strategy, when a faulty component is detected, some pre-defined backup path(s) is (are) used to bypass the faulty component and enable the multicast communication to continue. Our protocol only requires that routers near the faulty component be reconfigured, thus reducing the runtime overhead without compromising much of the performance. Our performance evaluation shows that our new protocol performs nearly as well as the best possible global method while utilizing much less runtime overhead and implementation cost.

In this paper, we design and analyze an efficient fault-tolerant multicast routing protocol. Reliable multicast communication is critical for the success of many Internet applications. Multicast routing protocols with core-based tree techniques (CBT) have been widely used because of their scalability and simplicity. We enhance the CBT protocol with fault tolerance capability and improve its efficiency and effectiveness. With our strategy, when a faulty component is detected, some pre-defined backup path(s) is (are) used to bypass the faulty component and enable the multicast communication to continue. Our protocol only requires that routers near the faulty component be reconfigured, thus reducing the runtime overhead without compromising much of the performance. Our approach is in contrast to other approaches that often require relatively large tree reformation when faults occur. These global methods are usually costly and complicated in their attempt to achieve theoretically optimal performance. Our performance evaluation shows that our new protocol performs nearly as well as the best possible global method while utilizing much less runtime overhead and implementation cost.

We propose and analyze three routing algorithms for anycast packets: source-destination based routing with weighted random selection (SD/WRS); destination based routing with weighted random selection (D/WRS); and the shortest shortest path first (SSPF) algorithms. The SSPF algorithm is a simple extension to the traditional SPF algorithm for routing unicast packets. The SD/WRS and D/WRS algorithms explicitly take into account characteristics of anycast message traffic and its recipient group. As a result, our simulation study shows that both the SD/WRS and D/WRS algorithms perform much better than SSPF in terms of average end-to-end packet delay. In particular, SD/WRS performs very close to a dynamic optimal algorithm in most cases. Our algorithms are simple, efficient and compatible with the most of existing routing technologies. We also formally prove the loop free and correctness properties for our algorithms.