Logging is a key mechanism in the security of computer systems. Beyond supporting important forward security properties, it is critical that logging withstands both failures and intentional tampering to prevent subtle attacks leaving the system in an inconsistent state with inconclusive evidence. We propose new techniques combining forward security with crash recovery for secure log data storage. As the support of specifically forward integrity and the online nature of logging prevent the use of conventional coding, we propose and analyze a coding scheme resolving these unique design constraints. Specifically, our coding enables forward integrity, online encoding, and most importantly a constant number of operations per encoding. It adds a new log item by 𝖷𝖮𝖱 ing it to k cells of a table. If up to a certain threshold of cells is modified by the adversary, or lost due to a crash, we still guarantee recovery of all stored log items. The main advantage of the coding scheme is its efficiency and compatibility with forward integrity. The key contribution of the paper is the use of spectral graph theory techniques to prove that k is constant in the number n of all log items ever stored and small in practice, e.g., k = 5. Moreover, we prove that to cope with up to \(\sqrt {n}\) modified or lost log items, storage expansion is constant in n and small in practice. For k = 5, the size of the table is only 12% more than the simple concatenation of all n items. We propose and evaluate original techniques to scale the computation cost of recovery to several GBytes of security logs. We instantiate our scheme into an abstract data structure which allows to either detect adversarial modifications to log items or treat modifications like data loss in a system crash. The data structure can recover lost log items, thereby effectively reverting adversarial modifications.

RF emissions’ detection, classification, and spectro-temporal localization are essential not only for understanding, managing, and protecting the radio frequency resources, but also for countering today's security threats such as jammers. Achieving this goal for wideband, real-time operation remains challenging. In this article, we present WRIST, a Wideband, Real-time, Spectro-Temporal RF Identification system. WRIST can detect, classify, and precisely locate RF emissions in time and frequency using RF samples of 100 MHz spectrum in real-time. The system leverages anone-stage object detectionDeep Learning framework, and transfer learning to a multi-channel visual-based spectral representation. Towards developing WRIST, we devised an iterative training approach which leverages synthesized and augmented RF data to efficiently build a large dataset with high-quality labels. WRIST achieves over$99 \%$class detection accuracy,$94 \%$emission precision and recall, with less than 0.08 bandwidth and time offset ratios in a large anechoic chamber over-the-air environment. In the extremely congested in-the-wild environment, WRIST still achieves over$80 \%$precision and recall. WRIST currently supports five 2.4 GHz technologies (Bluetooth, Lightbridge, Wi-Fi, XPD, and ZigBee) and is easily extendable to others. We are making our curated dataset available to the whole community. It comprises over 10 million labelled RF emissions from off-the-shelf wireless radios spanning the five classes of technologies.

We present the first open-source tool capable of efficiently sniffing 5G control channels, 5GSniffer and demonstrate its potential to conduct attacks on users privacy. 5GSniffer builds on our analysis of the 5G RAN control channel exposing side-channel leakage. We note that decoding the 5G control channels is significantly more challenging than in LTE, since part of the information necessary for decoding is provided to the UEs over encrypted channels. We devise a set of techniques to achieve real-time control channels sniffing (over three orders of magnitude faster than brute-forcing). This enables, among other things, to retrieve the Radio Network Temporary Identifiers (RNTIs) of all users in a cell, and perform traffic analysis. To illustrate the potential of our sniffer, we analyse two privacy-focused messengers, Signal and Telegram. We identify privacy leaks that can be exploited to generate stealthy traffic to a target user. When combined with 5GSniffer, it enables stealthy exposure of the presence of a target user in a given location (solely based on their phone number), by linking the phone number to the RNTI. It also enables traffic analysis of the target user. We evaluate the attacks and our sniffer, demonstrating nearly 100% accuracy within 30 seconds of attack initiation.

In this paper, we present JaX, a novel approach for detecting and cancelling high-power jammers in the scenarios when the traditional spread spectrum techniques and other jammer avoidance approaches are not sufficient. JaX does not require explicit probes, sounding, training sequences, channel estimation, or the cooperation of the transmitter. We identify and address multiple challenges, resulting in a convolutional neural network for a multi-antenna system to infer the existence of interference, the number of interfering emissions and their respective phases. This information is continuously fed into an algorithm that cancels the interfering signal. We develop a two-antenna prototype system and evaluate our approach in various environment settings and modulation schemes using SDR platforms. We demonstrate that the receiving node equipped with our approach can detect a jammer with over 99% of accuracy and achieve a Bit Error Rate as low as 10^6 even when the jammer power is nearly two orders of magnitude (19 dB) higher than the legitimate signal, and without modifying the link modulation. JaX is resilient against various jammers with different characteristics of jamming signals, jamming power, and timing pattern.

Aviation datalink applications such as controller-pilot datalink communications (CPDLC) and automatic dependent surveillance-contract (ADS-C) were designed to supplement existing communication systems to accommodate increasing air traffic. These applications are typically used to provide departure clearance, en-route services such as altitude and flight plan changes, air traffic surveillance and reporting, and radio frequency assignments. Unlike most attacks proposed so far where the attacker influences decision-making through manipulated instruments, attacks on aviation datalink provide adversaries with a new attack vector to influence the flight crew’s decision-making through direct instructions. In this work, we perform a security analysis of these applications and outline the requirements for executing a successful attack. Specifically, we propose a coordinated multi-aircraft attack and show how an adversary capable of spoofing datalink messages and reactive jamming can influence the flight crew’s decision-making. Through geospatial analysis of historical flight data, we identify 48 vulnerable regions where an attacker has a 90% chance of encountering favorable conditions for coordinated multi-aircraft attacks. Next, we implement a reactive jammer that ensures stealthy attack execution by targeting messages from a specific aircraft with a reaction time of 1.48 ms and 98.85% jamming success. Even though by themselves these attacks have a lower probability of endangering the safety of the aircraft, the threat is magnified when combined with attacks on other avionics. Finally, we discuss the possibility of executing integrated attacks on aircraft system as a whole emphasizing the importance of securing individual components in the aviation ecosystem.

We introduce, design, and evaluate a set of universal receiver beamforming techniques. Our approach and system DEFORM, a Deep Learning (DL)-based RX beamforming achieves significant gain for multi-antenna RF receivers while being agnostic to the transmitted signal features (e.g., modulation or bandwidth). It is well known that combining coherent RF signals from multiple antennas results in a beamforming gain proportional to the number of receiving elements. However in practice, this approach heavily relies on explicit channel estimation techniques, which are link specific and require significant communication overhead to be transmitted to the receiver. DEFORM addresses this challenge by leveraging Convolutional Neural Network to estimate the channel characteristics in particular the relative phase to antenna elements. It is specifically designed to address the unique features of wireless signals complex samples, such as the ambiguous 2π phase discontinuity and the high sensitivity of the link Bit Error Rate. The channel prediction is subsequently used in the Maximum Ratio Combining algorithm to achieve an optimal combination of the received signals. While being trained on a fixed, basic RF settings, we show that DEFORM's DL model is universal, achieving up to 3 dB of SNR gain for a two-antenna receiver in extensive evaluation demonstrating various settings of modulations and bandwidths.

Federated learning (FL) is a well-established distributed machine-learning paradigm that enables training global models on massively distributed data i.e., training on multi-owner data. However, classic FL algorithms, such as Federated Averaging (FedAvg), generally underperform when faced with Non-Independent and Identically Distributed (Non-IID) data. Such a problem is aggravated for some hyperparametric methods such as optimizers, regularization, and normalization techniques. In this paper, we introduce FedBS, a new efficient strategy to handle global models having batch normalization layers, in the presence of Non-IID data. FedBS modifies FedAvg by introducing a new aggregation rule at the server-side, while also retaining full compatibility with Batch Normalization (BN). Through our evaluations, we have empirically proven that FedBS outperforms both classical FedAvg, as well as the state-of-the-art FedProx through a comprehensive set of experiments conducted on Cifar-10, Mnist, and Fashion-Mnist datasets under various Non-IID data settings. Furthermore, we observed that in some cases, FedBS can be 2× faster than other FL approaches, coupled with higher testing accuracy.

Bluetooth Low Energy advertisements are increasingly used for proximity privacy-preserving protocols. We investigate information leakage from BLE advertisements. Our analysis, among other things, reveals that the design of today’s Bluetooth chips enables the linking of BLE advertisements to Bluetooth Classic (BTC) frames, and to a globally unique identifier (BDADDR). We demonstrate that the inference of the BDADDR from BLE advertisements is robust achieving over 90% reliability across apps, mobile devices, density of devices, and tens of meters away from the victims. We discuss the implications of current chipsets vulnerability on privacy-preserving protocols. The attack, for instance, reveals the BDADDR of devices of infected users of contact-tracing apps. We also discuss how the vulnerability can lead to de-anonymization of victims. Furthermore, current mobile devices do not allow selective disabling of BTC independently of BLE which renders simple countermeasures impractical. We developed several mitigations for the Android OS and the Bluetooth stack and demonstrate their efficacy.

Smart speakers, such as the Amazon Echo Dot, are very popular and routinely trusted with private and sensitive information. Yet, little is known about their security and potential attack vectors. We develop and synthesize a set of IoT forensics techniques, apply them to reverse engineer the hardware and software of the Amazon Echo Dot, and demonstrate its lacking protections of private user data. An adversary with physical access to such devices (e.g., purchasing a used one) can retrieve sensitive information such as Wi-Fi credentials, the physical location of (previous) owners, and cyber-physical devices (e.g., cameras, door locks). We show that such information, including all previous passwords and tokens, remains on the flash memory, even after a factory reset. This is due to the wear-leveling algorithms of the flash memory and lack of encryption. We identify and discuss the design flaws in the storage of sensitive information and the process of de-provisioning used devices. We demonstrate the practical feasibility of such attacks on 86 used devices purchased on eBay and flea markets. Finally, we propose secure design alternatives and mitigation techniques.

The 3GPP 5G cellular system is hailed as a major step towards more ubiquitous and pervasive communications infrastructure (including for V2X, Smart Grid, and Healthcare). We disclose and evaluate SigUnder, an attack that enables an adversary to overshadow the Signal Synchronization Block (SSB) with an injected signal at 3.4dB below the legitimate signal (prior work required 3dB above). The attack exploits the polar coding mechanism of 5G and the physical layer OFDM structure. It can be used to make previous DoS and over-shadowing attacks lower-power and stealthy, but also enables new attacks unique to 5G such as setting the cellBarred field in the 5G MIB (and blocking access to a cell). We develop techniques (e.g., phase prediction) to make the attack feasible in a practical setup, and evaluate its performance both in simulations and over the air experiments. We also introduce SICUnder, an extension of Successive Interference Cancellation (SIC) to be able to address the unique challenges that SigUnder poses and demonstrate it effectiveness relatively to standard SIC.

Secure ranging is poised to play a critical role in several emerging applications such as self-driving cars, unmanned aerial systems, wireless IoT devices, and augmented reality. In this paper, we propose a design of a secure broadcast ranging system with unique features and techniques. Its spectral-flexibility, and low-power short ranging bursts enable co-existence with existing systems such as in the 2.4GHz ISM band. We exploit a set of RF techniques such as upsampling and successive interference cancellation to achieve high accuracy and scalability to tens of reflectors even when operating over narrow bands of spectrum. We demonstrate that it can be implemented on popular SDR platforms FPGA and/or hosts (with minimal FPGA modifications). The protocol design, and cryptographically generated/detected signals, and randomized timing of transmissions, provide stealth and security against denial of service, sniffing, and distance manipulation attacks. Through extensive experimental evaluations (and simulations for scalability to over 100 reflectors) we demonstrate an accuracy below 20cm on a wide range of SNR (as low as 0dB), spectrum 25MHz-100MHz, with bursts as short as 5us.

Drones are increasingly associated with incidents disturbing air traffic at airports, invading privacy, and even terrorism. Wireless Direction of Arrival (DoA) techniques, such as the MUSIC algorithm, can localize drones, but deploying a system that systematically localizes RF emissions can lead to intentional or unintentional (e.g., if compromised) abuse. Multi-Party Computation (MPC) provides a solution for controlled computation of the elevation of RF emissions, only revealing estimates when some conditions are met, such as when the elevation exceeds a specified threshold. However, we show that a straightforward implementation of MUSIC, which relies on costly computation of complex matrix operations such as eigendecomposition, in state of the art MPC frameworks is extremely inefficient requiring over 20 seconds to achieve the weakest security guarantees. In this work, we develop a set of MPC optimizations and extensions of MUSIC. We extensively evaluate our techniques in several MPC protocols achieving a speedup of 300-500 times depending on the security model and specific technique used. For instance a Malicious Shamir execution providing security against malicious adversaries enables 536 DoA estimations per second, making it practical for use in real-world setups.

Bluetooth Classic (BT) remains the de facto connectivity technology in car stereo systems, wireless headsets, laptops, and a plethora of wearables, especially for applications that require high data rates, such as audio streaming, voice calling, tethering, etc. Unlike in Bluetooth Low Energy (BLE), where address randomization is a feature available to manufactures, BT addresses are not randomized because they are largely believed to be immune to tracking attacks. We analyze the design of BT and devise a robust de-anonymization technique that hinges on the apparently benign information leaking from frame encoding, to infer a piconet's clock, hopping sequence, and ultimately the Upper Address Part (UAP) of the master device's physical address, which are never exchanged in clear. Used together with the Lower Address Part (LAP), which is present in all frames transmitted, this enables tracking of the piconet master, thereby debunking the privacy guarantees of BT. We validate this attack by developing the first Software-defined Radio (SDR) based sniffer that allows full BT spectrum analysis (79 MHz) and implements the proposed de-anonymization technique. We study the feasibility of privacy attacks with multiple testbeds, considering different numbers of devices, traffic regimes, and communication ranges. We demonstrate that it is possible to track BT devices up to 85 meters from the sniffer, and achieve more than 80% device identification accuracy within less than 1 second of sniffing and 100% detection within less than 4 seconds. Lastly, we study the identified privacy attack in the wild, capturing BT traffic at a road junction over 5 days, demonstrating that our system can re-identify hundreds of users and infer their commuting patterns.

Determining which operations are being executed by a black-box device is an important challenge to tackle in reverse engineering. Furthermore, in order to perform a successful side-channel analysis (SCA) of said operations, their precise timing must be determined. In this paper, we tackle these two challenges in context of an electromagnetic (EM) analysis of a NodeMCU Amica IoT device. More specifically, we propose a convolutional neural network (CNN) architecture that is designed to classify operations performed by the NodeMCU out of a set of 8 possible operations, namely OpenSSL AES, native AES, TinyAES, OpenSSL DES, SHA1-PRF, HMAC-SHA1, SHA1, and SHA1Transform. In addition, we use the same architecture to predict the start and end times of the operation, thereby removing the need for firmware modifications or manual triggers in SCA. Our approach is evaluated using a 66 GB dataset containing 69,632 complex traces of EM leakage, captured with a USRP B210 software defined radio. The best variant of our methodology achieves a classification accuracy of 96.47%, and is able to predict the start and end times of the operation within 34 |is of the ground truth on average. We compare our methodology to classical template matching, and provide our open-source implementation and datasets to the community so that the achieved results can be reproduced.

Location information is critical to a wide variety of navigation and tracking applications. GPS, today's de-facto outdoor localization system has been shown to be vulnerable to signal spoofing attacks. Inertial Navigation Systems (INS) are emerging as a popular complementary system, especially in road transportation systems as they enable improved navigation and tracking as well as offer resilience to wireless signals spoofing and jamming attacks. In this paper, we evaluate the security guarantees of INS-aided GPS tracking and navigation for road transportation systems. We consider an adversary required to travel from a source location to a destination and monitored by an INS-aided GPS system. The goal of the adversary is to travel to alternate locations without being detected. We develop and evaluate algorithms that achieve this goal, providing the adversary significant latitude. Our algorithms build a graph model for a given road network and enable us to derive potential destinations an attacker can reach without raising alarms even with the INS-aided GPS tracking and navigation system. The algorithms render the gyroscope and accelerometer sensors useless as they generate road trajectories indistinguishable from plausible paths (both in terms of turn angles and roads curvature). We also design, build and demonstrate that the magnetometer can be actively spoofed using a combination of carefully controlled coils. To experimentally demonstrate and evaluate the feasibility of the attack in real-world, we implement a first real-time integrated GPS/INS spoofer that accounts for traffic fluidity, congestion, lights, and dynamically generates corresponding spoofing signals. Furthermore, we evaluate our attack on ten different cities using driving traces and publicly available city plans. Our evaluations show that it is possible for an attacker to reach destinations that are as far as 30 km away from the actual destination without being detected. We also show that it is possible for the adversary to reach almost 60-80% of possible points within the target region in some cities. Such results are only a lower-bound, as an adversary can adjust our parameters to spend more resources (e.g., time) on the target source/destination than we did for our performance evaluations of thousands of paths. We propose countermeasures that limit an attacker's ability, without the need for any hardware modifications. Our system can be used as the foundation for countering such attacks, both detecting and recommending paths that are difficult to spoof.

Modern aircraft heavily rely on several wireless technologies for communications, control, and navigation. In this work, we demonstrate the vulnerability of aircraft instrument landing systems to wireless attacks. We show that it is possible to fully and in finegrain control the course deviation indicator, as displayed by the ILS receiver, in real-time, and demonstrate it on aviation-grade ILS receivers. We develop a tightly-controlled closed-loop ILS spoofer that autonomously adjusts the adversary's transmitted signals based on the aircraft's GPS location to cause an undetected off-runway landing. We demonstrate the integrated attack on an FAA certified flight-simulator (X-Plane)'s AI-based auto-land feature and show success rate with offset touchdowns of 18 meters to over 50 meters.

Abstract We present the design, implementation and evaluation of a system, called MATRIX, developed to protect the privacy of mobile device users from location inference and sensor side-channel attacks. MATRIX gives users control and visibility over location and sensor (e.g., Accelerometers and Gyroscopes) accesses by mobile apps. It implements aPrivoScopeservice that audits all location and sensor accesses by apps on the device and generates real-time notifications and graphs for visualizing these accesses; and aSynthetic Locationservice to enable users to provide obfuscated or synthetic location trajectories or sensor traces to apps they find useful, but do not trust with their private information. The services are designed to be extensible and easy for users, hiding all of the underlying complexity from them. MATRIX also implements aLocation Providercomponent that generates realistic privacy-preserving synthetic identities and trajectories for users by incorporating traffic information using historical data from Google Maps Directions API, and accelerations using statistical information from user driving experiments. These mobility patterns are generated by modeling/solving user schedule using a randomized linear program and modeling/solving for user driving behavior using a quadratic program. We extensively evaluated MATRIX using user studies, popular location-driven apps and machine learning techniques, and demonstrate that it is portable to most Android devices globally, is reliable, has low-overhead, and generates synthetic trajectories that are difficult to differentiate from real mobility trajectories by an adversary.

Although privacy compromises remain an issue among users and advocacy groups, identification of user location has emerged as another point of concern. Techniques using GPS, Wi-Fi, NFC, Bluetooth tracking and cell tower triangulation are well known. These can typically identify location accurately with meter resolution. Another technique, inferring routes via sensor exploitation, may place a user within a few hundred meters of a general location. Acoustic beacons such as those placed in malls may have more finely grained resolution yet are limited by the sensitivity of the device's microphone to ultrasonic signals and directionality. In this paper we are able to discern user location within commercial GPS resolution by leveraging the ability of mobile device magnetometers to detect externally generated signals in a permissionless attack. We are able to achieve an aggregate location identification success rate of 86% with a bit error rate of 1.5% which is only ten times the stationary error rate. We accomplish this with a signal that is a fraction of the Earth's magnetic field strength.

Demand for mobile devices continues to experience worldwide growth. Within the U.S., there is a significant shift away from broadband usage towards Smartphones as the primary Internet entry point for consumers. Although technological advancements have helped fuel demand for greater features and functionality to enhance the user experience, they have also drawn attention from malicious actors seeking to access and exfiltrate increasingly available sensitive and content rich personalized information.

Leakage of user location and traffic patterns is a serious security threat with significant implications on privacy as reported by recent surveys and identified by the US Congress Location Privacy Protection Act of 2014. While mobile phones can restrict the explicit access to location information to applications authorized by the user, they are ill-equipped to protect against side-channel attacks. In this paper, we show that a zero-permissions Android app can infer vehicular users' location and traveled routes, with high accuracy and without the users' knowledge, using gyroscope, accelerometer, and magnetometer information. We modeled this problem as a maximum likelihood route identification on a graph. The graph is generated from the OpenStreetMap publicly available database of roads. Our route identification algorithms output both a ranked list of potential routes as well a ranked list of route-clusters. Through extensive simulations over 11 cities, we show that for most cities with probability higher than 50% it is possible to output a short list of 10 routes containing the traveled route. In real driving experiments (over 980 Km) in the cities of Boston (resp. Waltham), Massachusetts, we report a probability of 30% (resp. 60%) of inferring a list of 10 routes containing the true route.

Wi-Fi (IEEE 802.11), is emerging as the primary medium for wireless Internet access. Cellular carriers are increasingly offloading their traffic to Wi-Fi Access Points to overcome capacity challenges, limited RF spectrum availability, cost of deployment, and keep up with the traffic demands driven by user generated content. The ubiquity of Wi-Fi and its emergence as a universal wireless interface makes it the perfect tracking device. The Wi-Fi offloading trend provides ample opportunities for adversaries to collect samples (e.g., Wi-Fi probes) and track the mobility patterns and location of users. In this work, we show that RF fingerprinting of Wi-Fi devices is feasible using commodity software defined radio platforms. We developed a framework for reproducible RF fingerprinting analysis of Wi-Fi cards. We developed a set of techniques for distinguishing Wi-Fi cards, most are unique to the IEEE802.11a/g/p standard, including scrambling seed pattern, carrier frequency offset, sampling frequency offset, transient ramp-up/down periods, and a symmetric Kullback-Liebler divergence-based separation technique. We evaluated the performance of our techniques over a set of 93 Wi-Fi devices spanning 13 models of cards. In order to assess the potential of the proposed techniques on similar devices, we used 3 sets of 26 Wi-Fi devices of identical model. Our results, indicate that it is easy to distinguish between models with a success rate of 95%. It is also possible to uniquely identify a device with 47% success rate if the samples are collected within a 10s interval of time.

The increasing importance of Wi-Fi in today's wireless communication systems, both as a result of Wi-Fi offloading and its integration in IoT devices, makes it an ideal target for malicious attacks. In this paper, we investigate the structure of the combined interleaver/convolutional coding scheme of IEEE 802.11a/g/n. The analysis of the first and second-round permutations of the interleaver allows us to design deterministic jamming patterns across subcarriers that when de-interleaved results in an interference burst. We show that a short burst across carefully selected sub-carriers exceeds the error correction capability of Wi-Fi. We implemented this attack as a reactive interleaving jammer on the firmware of the low-cost HackRF SDR. Our experimental evaluation shows that this attack can completely block the Wi-Fi transmissions with jamming power less than 1% of the communication (measured at the receiver) and block 95% of the packets with less than 0.1% energy. Furthermore, it is at least 5dB and up to 15dB more power-efficient than jamming attacks that are unaware of the Wi-Fi interleaving structure.

We develop a linearly constrained bimatrix game framework that can be used to model many practical problems in many disciplines, including jamming in packetized wireless networks. In contrast to the widely used zero-sum framework, in bimatrix games it is no longer required that the sum of the players' utilities be zero or constant, thus, ir can be used to model a much larger class of jamming problems. Additionally, in contrast to the standard bimatrix games, in linearly constrained bimatrix games, the players' strategies must satisfy some linear constraint/inequality, consequently, not all strategies are feasible and the existence of the Nash equilibrium (NE) is not guaranteed anymore. We provide the necessary and sufficient conditions under which the existence of the Nash equilibrium is guaranteed, and show that under linear constraints, the equilibrium pairs and the Nash equilibrium solution of the constrained game corresponds to the global maximum of a quadratic program. Finally, we use our game theoretic framework to find the optimal transmission and jamming strategies for a typical wireless link under power limited jamming.

Wi-Fi connectivity using open hotspots hosted on untrusted Access Points (APs) has been a staple of mobile network deployments for many years as mobile providers seek to offload smartphone traffic to Wi-Fi. Currently, the available hotspot solutions allow for mobility patterns and client identities to be monitored by the parties hosting the APs as well as by the underlying service provider. We propose a protocol and system that allows a service provider to authenticate its clients, and hides the client identity from both AP and service provider at the time of authentication. Particularly, the client is guaranteed that either the provider cannot do better than to guess their identity randomly or they obtain proof that the provider is trying to reveal their identity by using different keys. Our protocol is based on Private Information Retrieval (PIR) with an augmented cheating detection mechanism based on our extensions to the NTRU encryption scheme. The somewhat-homomorphic encryption makes auditing of multiple rows in a single query possible, and optimizes PIR for highly parallel GPU computations with the use of the Fast Fourier Transform (FFT).

Over the last decade botnets survived by adopting a sequence of increasingly sophisticated strategies to evade detection and take overs, and to monetize their infrastructure. At the same time, the success of privacy infrastructures such as Tor opened the door to illegal activities, including botnets, ransomware, and a marketplace for drugs and contraband. We contend that the next waves of botnets will extensively attempt to subvert privacy infrastructure and cryptographic mechanisms. In this work we propose to preemptively investigate the design and mitigation of such botnets. We first, introduce OnionBots, what we believe will be the next generation of resilient, stealthy botnets. OnionBots use privacy infrastructures for cyber attacks by completely decoupling their operation from the infected host IP address and by carrying traffic that does not leak information about its source, destination, and nature. Such bots live symbiotically within the privacy infrastructures to evade detection, measurement, scale estimation, observation, and in general all IP-based current mitigation techniques. Furthermore, we show that with an adequate self-healing network maintenance scheme, that is simple to implement, OnionBots can achieve a low diameter and a low degree and be robust to partitioning under node deletions. We develop a mitigation technique, called SOAP, that neutralizes the nodes of the basic OnionBots. In light of the potential of such botnets, we believe that the research community should proactively develop detection and mitigation methods to thwart OnionBots, potentially making adjustments to privacy infrastructure.

Exposing the rate information of wireless transmissions enables highly efficient attacks that can severely degrade the performance of a network at very low cost. In this paper, we introduce an integrated solution to conceal the rate information of wireless transmissions while simultaneously boosting the resiliency against interference. The proposed solution is based on a generalization of Trellis Coded Modulation combined with Cryptographic Interleaving. We develop algorithms for discovering explicit codes for concealing any modulation in {BPSK, QPSK, 8-PSK, 16-QAM, 64-QAM}. We propose a 2-pass frequency correction and phase tracking mechanisms that enables the proposed schemes to reach their potential. We demonstrate that in most cases this rate hiding scheme has the side effect of boosting resiliency by up to 7dB (simulations) and 4dB (SDR experiments).

Abstract We revisit the problem of privacy-preserving range search and sort queries on encrypted data in the face of an untrusted data store. Our new protocol RASP has several advantages over existing work. First, RASP strengthens privacy by ensuring forward security: after a query for range [a, b], any new record added to the data store is indistinguishable from random, even if the new record falls within range [a, b]. We are able to accomplish this using only traditional hash and block cipher operations, abstaining from expensive asymmetric cryptography and bilinear pairings. Consequently, RASP is highly practical, even for large database sizes. Additionally, we require only cloud storage and not a computational cloud like related works, which can reduce monetary costs significantly. At the heart of RASP, we develop a new update-oblivious bucket-based data structure. We allow for data to be added to buckets without leaking into which bucket it has been added. As long as a bucket is not explicitly queried, the data store does not learn anything about bucket contents. Furthermore, no information is leaked about data additions following a query. Besides formally proving RASP’s privacy, we also present a practical evaluation of RASP on Amazon Dynamo, demonstrating its efficiency and real world applicability.

Abstract We present a new, general data structure that reduces the communication cost of recent tree-based ORAMs. Contrary to ORAM trees with constant height and path lengths, our new construction r-ORAM allows for trees with varying shorter path length. Accessing an element in the ORAM tree results in different communication costs depending on the location of the element. The main idea behind r-ORAM is a recursive ORAM tree structure, where nodes in the tree are roots of other trees. While this approach results in a worst-case access cost (tree height) at most as any recent tree-based ORAM, we show that the average cost saving is around 35% for recent binary tree ORAMs. Besides reducing communication cost, r-ORAM also reduces storage overhead on the server by 4% to 20% depending on the ORAM’s client memory type. To prove r-ORAM’s soundness, we conduct a detailed overflow analysis. r-ORAM’s recursive approach is general in that it can be applied to all recent tree ORAMs, both constant and poly-log client memory ORAMs. Finally, we implement and benchmark r-ORAM in a practical setting to back up our theoretical claims.

With sensitive data being increasingly stored on mobile devices and laptops, hard disk encryption is more important than ever. In particular, being able to plausibly deny that a hard disk contains certain information is a very useful and interesting research goal. However, it has been known for some time that existing ``hidden volume'' solutions, like TrueCrypt, fail in the face of an adversary who is able to observe the contents of a disk on multiple, separate occasions. In this work, we explore more robust constructions for hidden volumes and present HiVE, which is resistant to more powerful adversaries with multiple-snapshot capabilities. In pursuit of this, we propose the first security definitions for hidden volumes, and prove HiVE secure under these definitions. At the core of HiVE, we design a new write-only Oblivious RAM. We show that, when only hiding writes, it is possible to achieve ORAM with optimal O(1) communication complexity and only poly-logarithmic user memory. This is a significant improvement over existing work and an independently interesting result. We go on to show that our write-only ORAM is specially equipped to provide hidden volume functionality with low overhead and significantly increased security. Finally, we implement HiVE as a Linux kernel block device to show both its practicality and usefulness on existing platforms.

We develop a constrained bimatrix game framework to model a packetized wireless communication link under jamming where the players' strategies must be chosen from some hyper-polyhedron defined by linear inequalities. In contrast to the widely used zero-sum framework, in bimatrix games it is no longer required that the sum of the players' payoffs to be zero (or a constant value). This allows us to model much larger class of jamming problems including scenarios where the players pursue different goals or have different views of the communication system. We provide the necessary and sufficient conditions under which the existence of the Nash equilibrium (NE) for the constrained bimatrix game is guaranteed. We study a typical jamming problem and show that the jammer can improve his payoff by switching from a zero-sum game to a bimatrix game.

Mobile phones are equipped with an increasingly large number of precise and sophisticated sensors. This raises the risk of direct and indirect privacy breaches. In this paper, we investigate the feasibility of keystroke inference when user taps on a soft keyboard are captured by the stereoscopic microphones on an Android smartphone. We developed algorithms for sensor-signals processing and domain specific machine learning to infer key taps using a combination of stereo-microphones and gyroscopes. We implemented and evaluated the performance of our system on two popular mobile phones and a tablet: Samsung S2, Samsung Tab 8 and HTC One. Based on our experiments, and to the best of our knowledge, our system (1) is the first to exceed 90% accuracy requiring a single attempt, (2) operates on the standard Android QWERTY and number keyboards, and (3) is language agnostic. We show that stereo-microphones are a much more effective side channel as compared to the gyroscope, however, their data can be combined to boost the accuracy of prediction. While previous studies focused on larger key sizes and repetitive attempts, we show that by focusing on the specifics of the keyboard and creating machine learning models and algorithms based on keyboard areas combined with adequate filtering, we can achieve an accuracy of 90% - 94% for much smaller key sizes in a single attempt. We also demonstrate how such attacks can be instrumentalized by a malicious application to log the keystrokes of other sensitive applications. Finally, we describe some techniques to mitigate these attacks.

We employ a game theoretic approach to formulate communication between two nodes over a wireless link in the presence of an adversary. We define a constrained, two-player, zero-sum game between a transmitter/receiver pair with adaptive transmission parameters and an adversary with average and maximum power constraints. In this model, the transmitter's goal is to maximize the achievable expected performance of the communication link, defined by a utility function, while the jammer's goal is to minimize the same utility function. Inspired by capacity/rate as a performance measure, we define a general utility function and a payoff matrix which may be applied to a variety of jamming problems. We show the existence of a threshold (JTH) such that if the jammer's average power exceeds JTH, the expected payoff of the transmitter at Nash Equilibrium (NE) is the same as the case when the jammer uses its maximum allowable power, Jmax, all the time. We provide analytical and numerical results for transmitter and jammer optimal strategies and a closed form expression for the expected value of the game at the NE. As a special case, we investigate the maximum achievable transmission rate of a rate-adaptive, packetized, wireless AWGN communication link under different jamming scenarios and show that randomization can significantly assist a smart jammer with limited average power.

We present a framework, Atlas, which incorporates application-awareness into Software-Defined Networking (SDN), which is currently capable of L2/3/4-based policy enforcement but agnostic to higher layers. Atlas enables fine-grained, accurate and scalable application classification in SDN. It employs a machine learning (ML) based traffic classification technique, a crowd-sourcing approach to obtain ground truth data and leverages SDN's data reporting mechanism and centralized control. We prototype Atlas on HP Labs wireless networks and observe 94% accuracy on average, for top 40 Android applications.

Wireless networks are an integral part of today's cyber-physical infrastructure. Their resiliency to jamming is critical not only for military applications, but also for civilian and commercial applications. In this paper, we design, prototype, and evaluate a system for cancelling jammers that are significantly more powerful than the transmitting node. Our system combines a novel mechanical beam-forming design with a fast auto-configuration algorithm and a software radio digital interference cancellation algorithm. Our mechanical beam-forming uses a custom-designed two-elements architecture and an iterative algorithm for jammer signal identification and cancellation. We have built a fully functional prototype (using 3D printers, servos, USRP-SDR) and demonstrate a robust communication in the presence of jammers operating at five orders of magnitude stronger power than the transmitting node. Similar performance in traditional phased arrays and radar systems requires tens to hundreds of elements, high cost and size

As the organizing committee, it is our pleasure to present the proceedings of the 4th IEEE International Workshop on Data Security and PrivAcy in wireless Networks (D-SPAN), held on June 4, 2013, in Madrid, Spain. The goal of this one-day workshop, organized in conjunction with the 14th IEEE WoWMoM 2013, is to exchange cutting-edge ideas for securing the next-generation wireless networks, systems, and applications. D-SPAN covers a wide range of security-related topics, including security and privacy of data collection, transmission, storage, publishing, and sharing in wireless networks broadly defined such as cellular and mobile ad hoc networks (MANET), vehicular ad hoc networks (VANET), cognitive and sensor networks to applying data analytics techniques to address security and privacy challenges in these networks. D-SPAN provides a forum for academic and industry researchers to present research ideas that build bridges across three communities: wireless networks, databases, and security.

Spread spectrum (SS) communication relies on the assumption that some secret is shared beforehand among communicating nodes to establish the spreading sequence for long-term wireless communication. Strasser et al. identified this as the circular dependency problem (CDP). This problem is exacerbated in large networks, where nodes join and leave the network frequently, and preconfiguration of secrets through physical contact is infeasible. In this work, we introduce an efficient and adversary-resilient secret sharing mechanism based on two novel paradigms (intractable forward decoding, efficient backward decoding) called Time Reversed Message Extraction and Key Scheduling (TREKS) that enables SS communication without preshared secrets. TREKS is four orders of magnitude faster than previous solutions to the CDP. Furthermore, our approach can be used to operate long-term SS communication without establishing any keys. The energy cost under TREKS is provably optimal with minimal storage overhead, and computation cost at most twice that of traditional SS. We evaluate TREKS through simulation and empirically using an experimental testbed consisting of USRP, GNU Radio, and GPU-equipped nodes. Using TREKS under a modest hardware setup, we can sustain a 1--Mbps long-term SS communication spread by a factor of 100 (i.e., 100 Megachips per second) over a 200-MHz bandwidth in real time.

In this paper, we propose a new Distributed Cooperation and Diversity Combining framework. Our focus is on heterogeneous networks with devices equipped with two types of radio frequency (RF) interfaces: short-range high-rate interface (e.g., IEEE802.11), and a long-range low-rate interface (e.g., cellular) communicating over urban Rayleigh fading channels. Within this framework, we propose and evaluate a set of distributed cooperation techniques operating at different hierarchical levels with resource constraints such as short-range RF bandwidth. We propose a Priority Maximum-Ratio Combining (PMRC) technique, and a Post Soft-Demodulation Combining (PSDC) technique. We show that the proposed techniques achieve significant improvements on Signal to Noise Ratio (SNR), Bit Error Rate (BER) and throughput through analysis, simulation, and experimentation on our software radio testbed. Our results also indicate that, under several communication scenarios, PMRC and PSDC can improve the throughput performance by over an order of magnitude.

We formulate the interaction between the communicating nodes and an adversary within a game-theoretic context. We show that earlier information-theoretic capacity results for a jammed channel correspond to a pure Nash Equilibrium (NE). However, when both players are allowed to randomize their actions (i.e., coding rate and jamming power) new mixed Nash equilibria appear with surprising properties. We show the existence of a threshold (JTH) such that if the jammer average power exceeds J TH, the channel capacity at the NE is the same as if the jammer was using its maximum allowable power, JMax, all the time. This indicates that randomization significantly advantages powerful jammers. We also show how the NE strategies can be derived, and we provide very simple (e.g., semi-uniform) approximations to the optimal communication and jamming strategies. Such strategies are very simple to implement in current hardware and software.

As the organizing committee, it is our pleasure to present the proceedings of the 3rd IEEE International Workshop on Data Security and PrivAcy in wireless Networks (D-SPAN), held on June 25, 2012, in San Francisco, California, USA. The goal of this one-day workshop, organized in conjunction with the 13th IEEE WoWMoM 2012, is to exchange cutting-edge ideas for securing the next-generation wireless networks, systems and applications. The scope of D-SPAN includes a wide variety of topics, including security and privacy of data collection, transmission, storage, publishing, and sharing in wireless networks broadly defined such as cellular and mobile ad hoc networks (MANET), vehicular ad hoc networks (VANET), cognitive and sensor networks to applying data analytics techniques to address security and privacy challenges in these networks. D-SPAN provides a forum for academic and industry researchers to present research ideas that build bridges across three communities: wireless networks and databases, and security.

We study the problem of designing an efficient broadcast communication system in the presence of inside attackers from a Game Theory perspective. The network consists of a server that pre-assigns key sets to users some of whom may be malicious, either compromised or inherently selfish. The keys are mapped to communication channels unique in time and frequency, and the server broadcasts access information on those channels selectively. The goal of the server would be to deliver information to users using as fewer channels as possible. The malicious users, on the other hand, collude to selectively jam channels that their keys map to and keep as many users as possible from accessing the information while remaining undetected. This interaction of a server and inside attackers can be modeled as a 2-person game with server's payoff defined as the number of honest users who receive broadcast information as a function of the channels being used for broadcast, and the traitors' payoff defined as the number of honest users affected by jamming as a function of the channels being jammed. Our main contribution is the modeling of this server/intruder interaction as a non-cooperative game. Understanding that transmission as well as jamming cost depends on the key (channel) based on the number of users who own them and thus the amount of information it may reveal about a jammer, we assign a generic weight on the player's strategies yielding a generic payoff function. For simplicity, we first assume that both of the players are rational and that they have complete information about each other's payoff function and strategy space. With this, we derive a closed expression for the Nash Equilibrium (NE). Furthermore, we show that the complexity for computing the NE under our formulation is polynomial in the number of users. Then, we discuss preliminary steps required to arrive at the same game formulation without assuming complete information about player strategies, their payoffs and their rationality.

The high density ofWiFi Access Points and large unlicensed RF bandwidth over which they operate makes them good candidates to alleviate cellular network's limitations. However, maintaining connectivity through WiFi results in depleting the mobile phone's battery in a very short time. We propose WiZi-Cloud, a system that utilizes a dual WiFi-ZigBee radio on mobile phones and Access Points, supported by WiZi-Cloud protocols, to achieve ubiquitous connectivity, high energy efficiency, real time intra-device/inter-AP handover, that is transparent to the applications. WiZi-Cloud runs mostly on commodity hardware such as Android phones and OpenWrt capable access points. Our extensive set of experiments demonstrate that for maintaining connectivity, WiZi-Cloud achieves more than a factor of 11 improvement in energy consumption in comparison with energy-optimized WiFi, and a factor of 7 in comparison with GSM. WiZi-Cloud has a better coverage than WiFi, and a low delay resulting in a good Mean Opinion Score (MOS) of 4.26 for a VoIP US cross-country communication.

As mobile devices evolve, end users have ever increasing demand for ubiquitous network access. WiFi, being now commonplace, has the potential to fulfill this demand. Apart from WiFi hotspots deployed by ISPs, home users start showing interest in sharing bandwidth with others (e.g. Fon bases its business model on users sharing open access points.) However, all existing WiFi sharing approaches are unsecured due to the difficulty of distributing access keys, discouraging potential users.

We investigate the resiliency of IEEE802.11 rate adaptation algorithms (RAA) against smart jamming attacks. We consider several classes of state-of-the-art RAAs that include the SampleRate, ONOE, AMRR, and the RAA used in Atheros Microsoft Windows XP driver. We model the behavior of these algorithms, and show the existence of very efficient attacks that exploit RAA-specific vulnerabilities as well as the inherent weaknesses that exist in the design of IEEE802.11 MAC and link layer protocol: in particular the overt packet rate information being transmitted, predictable rate selection mechanism, performance anomaly caused by the equiprobability of transmissions among all nodes regardless of the data rates being employed, and the lack of interference differentiation from poor link quality by IEEE802.11 RAAs. In this work, we present algorithms that determine optimal jamming strategies against RAAs for a given jamming budget, and experimentally demonstrate the efficiency of these smart jamming attacks, which can be orders of magnitude more efficient than naive jamming. For example, in the case of SampleRate, eight reactive jamming pulses every second are sufficient to achieve the same network throughput degradation achieved by a periodic jammer with the jamming energy cost 100 times higher. Some of the RAAs react even worse to smart jamming attacks; ONOE in particular suffers from the phenomenon of congestion collapse where the nodes fail to recover from the lowest data rate even after the jammer stops jamming. At the end, we summarize fundamental reasons behind such RAA vulnerabilities and propose a preliminary set of mitigation techniques. We leave the experimental demonstration of the efficiency of the proposed mitigation mechanisms for future work.

As the organizing committee, it is our pleasure to present the proceedings of the 2ndIEEE International Workshop on Data Security and PrivAcy in wireless Networks (D-SPAN), held on June 20, 2011, in Lucca, Italy. The goal of this one-day workshop, organized in conjunction with the 12thIEEE WoWMoM 2011, is to exchange cutting-edge ideas for securing the next-generation wireless networks, systems and applications. The scope of D-SPAN includes a wide variety of topics, including security and privacy of data collection, transmission, storage, publishing, and sharing in wireless networks broadly defined - such as cellular and mobile ad hoc networks (MANET), vehicular ad hoc networks (VANET), cognitive and sensor networks - to applying data analytics techniques to address security and privacy challenges in these networks. D-SPAN provides a forum for academic and industry researchers to present research ideas that build bridges across three communities: wireless networks and databases, and security.

In this paper, we present the design of the lightweight F_f family of privacy-preserving authentication protocols for RFID-systems. F_f results from a systematic design based on a new algebraic framework focusing on the security and privacy of RFID authentication protocols. F_f offers user-adjustable, strong authentication, and privacy against known algebraic attacks and recently popular SAT-solving attacks. In contrast to related work, F_f achieves these security properties without requiring an expensive cryptographic hash function. F_f is designed for a challenge-response protocol, where the tag sends random nonces and the results of HMAC-like computations of one of the nonces together with its secret key back to the reader. In this paper, the authentication and privacy of F_f is evaluated using analytical and experimental methods.

We introduce iPoint, a passive device that can interact and deliver information to virtually any mobile phone equipped with a WiFi network interface and a camera. The iPoint does not need any battery but harvests energy from the phone WiFi transmissions. The iPoint delivers information to the mobile phone through a low power LCD display that can be captured and processed by a software application. We introduce a mechanism of Packet Width Modulation (PWM) to encode the phone requests in the length of WiFi packets. This allows the use of phones not equipped with RFID readers, and still allows the ultralow power microcontroller to decode the information. In this paper, we describe the architecture of iPoint, discuss the design choices of each component, and report on the experimental evaluation of our prototype. Various RadioFrequency energy harvesters are discussed and a WiFi tailored, modified Greinacher voltage multiplier, a highly efficient parallel full-wave rectifier, is designed, prototyped and fully characterized. It features an energy-harvesting efficiency of up to 72% and collecting up to 2.5 mW from a phone WiFi transmission. An ultralow-power micro-controller with LCD capability (TI MSP430F417) is optimized, and customized to interface with our RF Front End (RF-FE). A PWM demodulator is designed, as an integral part of the energy-harvester, and interfaced with the microcontroller. Finally, the mobile phone application for decoding the LCD output is presented. The evaluation is based on actual measurements carried on the third generation of prototypes we built.

In this demo, we introduce iPoint, a passive device that can interact and deliver information to virtually any mobile phone equipped with a WiFi network interface and a camera. The iPoint does not need any battery but harvests energy from the phone WiFi transmissions. The iPoint delivers information to the mobile phone through a low power LCD display that can be captured and processed by a software application. We introduce a mechanism of Packet Width Modulation (PWM) to encode the phone requests in the length of WiFi packets. This allows the use of phones not equipped with RFID readers, and still allows the ultralow power microcontroller to decode the information. In this prototype, a WiFi tailored, modified Greinacher voltage multiplier, a highly efficient parallel fullwave rectifier, is designed, prototyped and fully characterized. It features an energy-harvesting efficiency of up to 72% and collecting up to 2.5 mW from a phone WiFi transmission. An ultralow-power micro-controller with LCD capability (TIMSP430F417) is optimized, and customized to interface with our RF Front End (RF-FE). A PWM demodulator is designed, as an integral part of the energy-harvester, and interfaced with the microcontroller. Finally, the mobile phone application for decoding the LCD output is presented.

We consider the problem of key establishment over a wireless radio channel in the presence of a communication jammer, initially introduced in [13]. The communicating nodes are not assumed to pre-share any secret. The established key can later be used by a conventional spread-spectrum communication system. We introduce new communication concepts called intractable forward-decoding and efficient backward-decoding. Decoding under our mechanism requires at most twice the computation cost of the conventional SS decoding and one packet worth of signal storage. We introduce techniques that apply a key schedule to packet spreading and develop a provably optimal key schedule to minimize the bit-despreading cost. We also use efficient FFT-based algorithms for packet detection. We evaluate our techniques and show that they are efficient both in terms of resiliency against jammers and computation. Finally, our technique has additional features such as the inability to detect packet transmission until the last few bits are being transmitted, and transmissions being destination-specific. To the best of our knowledge, this is the first solution that is optimal in terms of communication energy cost with very little storage and computation overhead.

In this paper, we study the performance of the IEEE 802.11 MAC protocol under a range of jammers that covers both channel-oblivious and channel-aware jamming. We study two channel-oblivious jammers: a periodic jammer that jams deterministically at a specified rate, and a memoryless jammer whose signals arrive according to a Poisson process. We also develop new models for channel-aware jamming, including a reactive jammer that only jams non-colliding transmissions and an omniscient jammer that optimally adjusts its strategy according to current states of the participating nodes. Our study comprises of a theoretical analysis of the saturation throughput of 802.11 under jamming, an extensive simulation study, and a testbed to conduct real world experimentation of jamming IEEE 802.11 using GNU Radio and USRP platform. In our theoretical analysis, we use a discrete-time Markov chain analysis to derive formulae for the saturation throughput of IEEE 802.11 under memoryless, reactive and omniscient jamming. One of our key results is a characterization of optimal omniscient jamming that establishes a lower bound on the saturation throughput of 802.11 under arbitrary jammer attacks. We validate the theoretical analysis by means of Qualnet simulations. Finally, we measure the real-world performance of periodic and memoryless jammers using our GNU radio jammer prototype.

In this paper, we address the problem of cross-layer denial of service attack in wireless data networks. We introduce SPREAD -a novel adaptive diversification approach to provide resiliency against such attacks. SPREAD relies on a mechanism-hopping technique, which can be seen as a multi-layer extension of the frequency-hopping technique. We apply a game-theoretic framework for modeling the interaction of the communicating nodes and the adversaries and analyze the proposed approach. We reason about the advantages of SPREAD against various types of jammers and demonstrate the effectiveness of our approach in the case of IEEE 802.11 protocol stack by studying the EIFS attack, periodical jamming and a Packet-Size Game. As an example, we show that mechanism-hopping over two instances of IEEE 802.11 can achieve several orders of magnitude gain in throughput over a single-instance network under the EIFS attack.

In this paper, we address the problem of countering jamming of broadcast control channels in wireless communication systems. Targeting control traffic on a system, e.g., BCCH channel in GSM, leads to smart attacks that can be four orders of magnitude more efficient than blind jamming. We propose several schemes based on coding theory and its applications that can counter both external and internal attackers (traitors). We introduce a T-(traitor) resilient scheme that requires less than (TlogTN)2control information transmissions and guarantees delivery of control information against any coalition of T traitors. The proposed scheme also allows the identification of persistently jamming traitors.

In this paper, we propose to address the energy efficient routing problem in multi-hop wireless networks with accumulative relay. In the accumulative relay model, partially overheard signals of previous transmissions for the same packet are used to decode it using a maximal ratio combiner technique [J.G. Proakis, 2001]. Therefore, additional energy saving can be achieved over traditional energy efficient routing. The idea of accumulative relay originates from the study of relay channel in information theory with a main focus on network capacity. It has been independently applied to minimum-energy broadcasting in L.G. Manish Agrawal et al. (2004), I. Maric and R. Yates (2002). We formulate the minimum energy accumulative routing problem (MEAR) and study it. We obtain hardness of approximation results counterbalanced with good heuristic solutions which we validate using simulations. Without energy accumulation, the classic shortest path (SP) algorithm finds the minimum energy path for a source-destination pair. However, we show that with energy accumulation, the SP can be arbitrarily bad. We turn our attention to heuristics and show that any optimal solution of MEAR can be converted to a canonical form - wave path. Armed with this insight, we develop a polynomial time heuristic to efficiently search over the space of all wavepaths. Simulation results show that our heuristic can provide more than 30% energy saving over minimum energy routing without accumulative relay. We also discuss the implementation issues of such a scheme.

We introduce a notion of universality in the context of optimization problems with partial information. Universality is a framework for dealing with uncertainty by guaranteeing a certain quality of goodness for all possible completions of the partial information set. Universal variants of optimization problems can be defined that are both natural and well-motivated. We consider universal versions of three classical problems: TSP, Steiner Tree and Set Cover.We present a polynomial-time algorithm to find a universal tour on a given metric space over n vertices such that for any subset of the vertices, the sub-tour induced by the subset is within O(log4n/log log n) of an optimal tour for the subset. Similarly, we show that given a metric space over n vertices and a root vertex, we can find a universal spanning tree such that for any subset of vertices containing the root, the sub-tree induced by the subset is within O(log4n/log log n) of an optimal Steiner tree for the subset. Our algorithms rely on a new notion of sparse partitions, that may be of independent interest. For the special case of doubling metrics, which includes both constant-dimensional Euclidean and growth-restricted metrics, our algorithms achieve an O(log n) upper bound. We complement our results for the universal Steiner tree problem with a lower bound of Ω(log n/log log n) that holds even for n vertices on the plane. We also show that a slight generalization of the universal Steiner Tree problem is coNP-hard and present nearly tight upper and lower bounds for a universal version of Set Cover.

We introduce a new power control scheme, for IEEE 802.11-like MAC protocols. Our scheme carefully combines collision avoidance and spatial reuse. Although many power control schemes were proposed for IEEE 802.11, to the best of our knowledge, our scheme is the first to achieve significant improvements for network throughput and energy efficiency simultaneously (up to 40% throughput increase and 3 times more data delivery with the same amount of energy), while adhering to the single-channel, single-transceiver design rule. Furthermore, our scheme solves the fairness problem identified in (J. Monks et al, IEEE INFOCOM, 2003), i.e., IEEE 802.11 and some power control schemes deliver more packets for short distance source-destination pairs than for long distance pairs. Thus, our scheme also improves the bit-metre/sec metric (by up to 70%). Our proposed scheme belongs to a more general class of power control schemes, that we extensively simulate. We also provide a theoretical analysis to justify our approach and simulation results.

In this paper, we investigate the resiliency to jamming of data protocols, such as IP, over WLAN. We show that, on existing WLAN, an adversary can successfully jam data packets at a very low energy cost. Such attacks allow a set of adversary nodes disseminated over an area to prevent communication, partition an ad hoc network or force packets to be routed over adversary chosen paths. The ratio of the jamming pulses duration to the transmission duration can be as low as 10−4. We investigate and analyze the performance of combining a cryptographic interleaver with various coding schemes to improve the robustness of wireless LANs for IP packets transmission 1. A concatenated code that is simple to decode and can maintain a low frame error rate (FER) under a jamming effort ratio of 15%. We argue that LDPC codes will be very suitable to prevent this type of jamming. We investigate the theoretical limits by analyzing the performance derived from upper bounds on binary error-control codes. We also propose an efficient anti-jamming technique for IEEE802.11b based on Reed–Solomon codes. Copyright © 2004 John Wiley & Sons, Ltd.

In this paper, we propose a novel general technique, based on renewal theory, for analyzing mobility models in ad hoc networks. Our technique enables an accurate derivation of the steady state distribution functions for node movement parameters such as distance and speed. We first apply our technique to the random waypoint model and provide alternative proofs for previous claims about the discrepancy between the steady state average speed and the average speed associated with the simulated distribution (Yoon, J et al., 2003). Our main contribution is a new methodology for simulating mobility which guarantees steady state for node movement distributions from the start of the simulation. Our methodology enables the correct and efficient simulation of a desired steady state distribution, and can be implemented in a manner transparent to the user. We support our claims through both formal proofs as well as extensive simulations.

Access control is a fundamental concern in any system that manages resources, e.g., operating systems, file systems, databases and communications systems. The problem we address is how to specify, enforce, and implement access control in distributed environments. This problem occurs in many applications such as management of distributed project resources, e-newspaper and pay TV subscription services. Starting from an access relation between users and resources, we derive a user hierarchy, a resource hierarchy, and a unified hierarchy. The unified hierarchy is then used to specify the access relation in a way that is compact and that allows efficient queries. It is also used in cryptographic schemes that enforce the access relation. We introduce three specific cryptography based hierarchical schemes, which can effectively enforce and implement access control and are designed for distributed environments because they do not need the presence of a central authority (except perhaps for setup).

Hierarchical cell structures (HCS) provide flexibility in handling non-homogenous traffic, but raises several problems to be efficiently deployed. In this paper, we show when and how resources can be shared between layers (e.g., TDMA frame partitioning between layers). We also provide several algorithms for inter-layer resource management (handover, admission control, congestion/load control).

We address the problem of detecting execution errors in communication protocols. A communication protocol is modeled as or finite state machine (FSM) that can be used as an external observer for detecting execution errors. Wang and Schwartz (1992, 1993) introduce the concept of multiple observers obtained by an adequate decomposition of the FSM. We first address the decomposition procedure from the perspective of error control codes and show that the decomposition algorithm can be restated as a simple state coding algorithm. Then, we discuss the features of fault tolerance of the resulting decomposition. We generalize the concept of multiple observers into the one of fault tolerant multiple observers. A set of observers is said to be fault tolerant if it is capable of detecting the execution errors of a protocol even when a subset of the observers is faulty. We show that error control codes can be used to generate multiple observers that are fault tolerant. We illustrate our approach on the ISO transport protocol class 4 (TP4). Finally, we give some hints on how to assign codes to the states while maximizing the fault coverage of the resulting decomposition.

Run-time fault detection in communication protocols is essential to detect faults that cannot be detected during the testing phase. We propose a signature-based method to detect run-time faults. A polynomial using the state and event information as coefficients is used to transform a sequence of states and events into a number (signature). The static signature corresponding to the correct execution of the protocol is compared with the run-time signature. This technique is more reliable, faster, and efficient compared to existing techniques. The states and events are assigned values such that multiple paths leading to the same state result in a unique signature. This reduces the number of comparisons required to verify the correct execution of the protocol. In this paper, we present eXTP4, an extended transport layer protocol that facilitate run-time fault detection.

Control applications constitute an important class of real-time systems. Such applications have specific temporal requirements that have to be taken into account during the system design. One such requirement is data temporary consistency. This paper gives an overview of the temporal consistency problem and addresses implementation issues for a distributed real-time system that is configured according to a producer/consumer communication model. Solutions are proposed that provide simple mechanisms for maintaining temporal consistency. Finally, a software architecture consisting of temporally homogeneous buffers is presented.>