Recent research has shown that carefully crafted jailbreak inputs can induce large language models to produce harmful outputs, despite safety measures such as alignment.It is important to anticipate the range of potential Jailbreak attacks to guide effective defenses and accurate assessment of model safety.In this paper, we present a new approach for generating highly effective Jailbreak attacks that manipulate the attention of the model to selectively strengthen or weaken attention among different parts of the prompt.By harnessing attention loss, we develop more effective jailbreak attacks, that are also transferrable.The attacks amplify the success rate of existing Jailbreak algorithms, including GCG, AutoDAN, and ReNeLLM, while lowering their generation cost (for example, the amplified GCG attack achieves 91.2% ASR, vs. 67.9%for the original attack on Llama2-7B-chat/AdvBench, using less than a third of the generation time).Warning: This paper contains potentially harmful LLM-generated content.

Vision-language models (VLMs) have improved significantly in their capabilities, but their complex architecture makes their safety alignment challenging. In this paper, we reveal an uneven distribution of harmful information across the intermediate layers of the image encoder and show that skipping a certain set of layers and exiting early can increase the chance of the VLM generating harmful responses. We call it as “Image enCoder Early-exiT” based vulnerability (ICET). Our experiments across three VLMs: LLaVA-1.5, LLaVA-NeXT, and Llama 3.2 show that performing early exits from the image encoder significantly increases the likelihood of generating harmful outputs. To tackle this, we propose a simple yet effective modification of the Clipped-Proximal Policy Optimization (Clip-PPO) algorithm for performing layer-wise multi-modal RLHF for VLMs. We term this as Layer-Wise PPO (L-PPO). We evaluate our L-PPO algorithm across three multi-modal datasets and show that it consistently reduces the harmfulness caused by early exits.

Graphics Processing Units (GPUs) excel at high-performance computing tasks, including multimedia rendering, cryptomining, deep learning, and natural language processing, due to their massive parallelism and high memory bandwidth.However, the growing size of models and datasets in these domains increasingly exceeds the memory capacity of a single GPU, resulting in significant performance overheads.To mitigate this issue, developers are often forced to partition data and manually manage transfers between GPU and host memory-a labor-intensive approach that becomes impractical for workloads with irregular memory access patterns, such as deep learning, recommendation systems, and graph processing.Programming abstractions like Unified Virtual Memory (UVM) simplify development by offering a unified memory space across the system and handling data transfers automatically.Unfortunately, UVM introduces substantial overhead due to frequent OS involvement and inefficient data movement, particularly when GPU memory is oversubscribed.This paper presents DREAM, a GPU memory management system that leverages an RDMA-capable network device to implement a programmer-agnostic lightweight virtual memory system, eliminating CPU/OS involvement.DREAM supports on-demand page migration for GPU applications by delegating memory management and page migration tasks to GPU threads.Since current CPU architectures do not support GPU-initiated memory management, DREAM uses a network interface card to enable efficient, transparent page migration.By offloading memory management to the GPU, DREAM achieves up to 4× higher performance than UVM

Transient execution attacks (TEAs), such as Spectre and Meltdown, exploit speculative execution to leak sensitive data through residual microarchitectural state.Traditional defenses often incur high performance and hardware costs by delaying speculative execution or requiring additional shadow structures and dynamic information flow tracking.In contrast, our approach models these attacks as violations of software-defined security contracts and enforces these contracts in hardware using existing features.We introduce Speculative Address Sanitization (SpecASan), which leverages ARM's Memory Tagging Extension (MTE) to extend memory safety protection from the committed path to the speculative path.When a speculative access does not pass the MTE tag comparison, this access is delayed until speculation resolves.This ensures that only validated accesses affect the microarchitectural state while preserving the performance benefits of speculation.When combined with Control-Flow Integrity (CFI) enforcement mechanisms, already supported by some hardware implementations, our evaluation shows that SpecASan effectively mitigates a broad class of transient execution attacks, including Spectre and Microarchitectural Data Sampling (MDS).Furthermore, SpecASan achieves this with low performance overhead and minimal hardware complexity, highlighting its practicality and efficiency.

Extended Reality (XR) experiences involve interactions between users, the real world, and virtual content. A key step to enable these experiences is the XR headset sensing and estimating the user's pose in order to accurately place and render virtual content in the real world. XR headsets use multiple sensors (e.g., cameras, inertial measurement unit) to perform pose estimation and improve its robustness, but this provides an attack surface for adversaries to interfere with the pose estimation process. In this paper, we create and study the effects of acoustic attacks that create false signals in the inertial measurement unit (IMU) on XR headsets, leading to adverse downstream effects on XR applications. We generate resonant acoustic signals on a HoloLens 2 and measure the resulting perturbations in the IMU readings, and also demonstrate both finegrained and coarse attacks on the ORB-SLAM3 and an open-source XR system (ILLIXR). With the knowledge gleaned from attacking these open-source frameworks, we demonstrate four end-to-end proof-of-concept attacks on a HoloLens 2: manipulating user input, clickjacking, zone invasion, and denial of user interaction. Our experiments show that current commercial XR headsets are susceptible to acoustic attacks, raising concerns for their security.

Operating Systems enforce logical isolation using abstractions such as processes, containers, and isolation tech-nologies to protect a system from malicious or buggy code. In this paper, we show new types of side channels through the file system that break this logical isolation. The file system plays a critical role in the operating system, managing all I/O activities between the application layer and the physical storage device. We observe that the file system implementation is shared, leading to timing leakage when using common I/O system calls. Specifically, we found that modern operating systems take advantage of any flush operation (which saves cached blocks in memory to the SSD or disk) to flush all of the I/O buffers, even those used by other isolation domains. Thus, by measuring the delay of syncfs, the attacker can infer the I/O behavior of victim programs. We then demonstrate a syncfs covert channel attack on multiple file systems, including both Linux native file systems and the Windows file system, achieving a maximum bandwidth of 5 Kbps with an error rate of 0.15% on Linux and 7.6 Kbps with an error rate of 1.9% on Windows. In addition, we construct three side-channel attacks targeting both Linux and Android devices. On Linux devices, we implement a website fingerprinting attack and a video fingerprinting attack by tracking the write patterns of temporary buffering files. On Android devices, we design an application fingerprinting attack that leaks application write patterns during boot-up. The attacks achieve over 90% F1 score, precision, and recall. Finally, we demonstrate that these attacks can be exploited across containers implementing a container detection technique and a cross-container covert channel attack.

Deformable vision transformers reduce the expensive quadratic time-complexity of attention modeling by using sparse attention structures, making it possible to use transformers in large-scale vision applications, such as multiview vision systems. We show that existing adversarial attacks against conventional vision transformers do not transfer to deformable transformers, primarily due to the data-dependent, dynamic nature of sparse attention. In this work, we present for the first time, adversarial attacks against deformable vision transformers by getting control of their attention-inferring module. We develop a novel collaborative attack where a source patch manipulates attention to point to a target patch containing the adversarial noise, which fools the model. We observe that our attack alters less than 1% of the patched area in the input field, completely disrupting object detection and resulting in 0% AP in single-view object detection using MS COCO, and 0% MODA in multi-view object detection using Wildtrack.

When evaluating an iterative graph query over a large graph, systems incur significant overheads due to repeated graph transfer across the memory hierarchy coupled with repeated (redundant) propagation of values over the edges in the graph. An approach for reducing these overheads combines the use of a small proxy graph and the large original graph in a two phase query evaluation. The first phase evaluates the query on the proxy graph incurring low overheads and producing mostly precise results. The second phase uses these mostly precise results to bootstrap query evaluation on the larger original graph producing fully precise results. The effectiveness of this approach depends upon the quality of the proxy graph. Prior methods find proxy graphs that are either large or produce highly imprecise results.

We introduce new jailbreak attacks on vision language models (VLMs), which use aligned LLMs and are resilient to text-only jailbreak attacks. Specifically, we develop cross-modality attacks on alignment where we pair adversarial images going through the vision encoder with textual prompts to break the alignment of the language model. Our attacks employ a novel compositional strategy that combines an image, adversarially targeted towards toxic embeddings, with generic prompts to accomplish the jailbreak. Thus, the LLM draws the context to answer the generic prompt from the adversarial image. The generation of benign-appearing adversarial images leverages a novel embedding-space-based methodology, operating with no access to the LLM model. Instead, the attacks require access only to the vision encoder and utilize one of our four embedding space targeting strategies. By not requiring access to the LLM, the attacks lower the entry barrier for attackers, particularly when vision encoders such as CLIP are embedded in closed-source LLMs. The attacks achieve a high success rate across different VLMs, highlighting the risk of cross-modality alignment vulnerabilities, and the need for new alignment approaches for multi-modal models.

Video analytics are often performed as cloud services in edge settings, primarily to offload computation and also in situations where the results are not directly consumed at the video source. Sending high-quality video data from end devices can be expensive in terms of both bandwidth and power use. To build a streaming video analytics pipeline that makes efficient use of these resources, it is imperative to reduce the size of the video streams. Traditional video compression algorithms are unaware of the semantics of the video, and can be both inefficient and harmful to the analytics performance. In this paper, we introduce LtC, a collaborative framework between the video source and the analytics server that efficiently learns to reduce the video streams within an analytics pipeline. Specifically, LtC uses the full-size video analytics algorithm at the server as a teacher to train a lightweight student neural network, which is then deployed at the video source. The student network is trained to capture the semantic significance of different regions within a video, which is used to selectively preserve the crucial regions in high quality while aggressively compressing the remaining regions. Furthermore, LtC incorporates a novel temporal filtering algorithm based on feature differencing to omit transmitting frames that do not contribute new information. Overall, LtC reduces bandwidth usage by 28-35% and attains a response delay that is up to 45% shorter than current state-of-the-art methods, while maintaining comparable analytics performance.

Connected vehicles are a big part of the automotive industry’s overall growth trend that may be utilized to improve transportation safety, expand mobility options, lower expenses, and provide new job possibilities. Thus, a complete examination of connected driving is required before the large-scale implementation in reality, which may be done affordably and efficiently using a reliable simulation platform. Current traffic simulators ease the research and development of connected vehicles by offering incremental enhancements to traditional traffic flow modeling approaches, which cannot replicate the features of real-world connected vehicles. Moreover, current standard security features that are used by the U.S. Department of Transportation or other research entities are not considered. Network-level evaluation incorporating large-scale traffic networks and Vehicle-To-Everything (V2X) communications should also be addressed. This study develops a novel and comprehensive co-simulation platform for conventional, connected, and automated driving that tightly integrates the main components of V2X communications, cyber-security protocol, traffic networks, and conventional vehicle models. Three major open-source components, SUMO, OMNeT++, and security credential management system (SCMS) based V2X simulator, are integrated and interconnected via the Traffic Control Interface (TraCI). The whole simulation platform can be deployed in a Client/Server model. Case studies show that the proposed platform provides an appropriate and trustworthy testbed for examining the possible social/economic effects of connected driving under a security credential management system.

We consider the problem of graph analytics on evolving graphs (i.e., graphs that change over time). In this scenario, a query typically needs to be applied to different snapshots of the graph over an extended time window, for example to track the evolution of a property over time. Solving a query independently on multiple snapshots is inefficient due to repeated execution of subcomputation common to multiple snapshots. At the same time, we show that using streaming, where we start from the earliest snapshot and stream the changes to the graph incrementally updating the query results one snapshot at a time is also inefficient. We propose CommonGraph, an approach for efficient processing of queries on evolving graphs. We first observe that deletion operations are significantly more expensive than addition operations for many graph queries (those that are monotonic). CommonGraph converts all deletions to additions by finding a common graph that exists across all snapshots. After computing the query on this graph, to reach any snapshot, we simply need to add the missing edges and incrementally update the query results. CommonGraph also allows sharing of common additions among snapshots that require them, and breaks the sequential dependency inherent in the traditional streaming approach where snapshots are processed in sequence, enabling additional opportunities for parallelism. We incorporate the CommonGraph approach by extending the KickStarter streaming framework. We implement optimizations that enable efficient handling of edge additions without resorting to expensive in place graph mutations, significantly reducing the streaming overhead, and enabling direct reuse of shared edges among different snapshots. CommonGraph achieves 1.38x-8.17x improvement in performance over Kickstarter across multiple benchmarks.

Real-world adversarial physical patches were shown to be successful in compromising state-of-the-art models in a variety of computer vision applications. Existing defenses that are based on either input gradient or features analysis have been compromised by recent GAN-based attacks that generate naturalistic patches. In this paper, we propose Jedi, a new defense against adversarial patches that is resilient to realistic patch attacks. Jedi tackles the patch localization problem from an information theory perspective; leverages two new ideas: (1) it improves the identification of potential patch regions using entropy analysis: we show that the entropy of adversarial patches is high, even in naturalistic patches; and (2) it improves the localization of adversarial patches, using an autoencoder that is able to complete patch regions from high entropy kernels. Jedi achieves high-precision adversarial patch localization, which we show is critical to successfully repair the images. Since Jedi relies on an input entropy analysis, it is model-agnostic, and can be applied on pre-trained off-the-shelf models without changes to the training or inference of the protected models. Jedi detects on average 90% of adversarial patches across different benchmarks and recovers up to 94% of successful patch attacks (Compared to 75% and 65% for LGS and Jujutsu, respectively).

The deep learning revolution has been enabled in large part by GPUs, and more recently accelerators, which make it possible to carry out computationally demanding training and inference in acceptable times. As the size of machine learning networks and workloads continues to increase, multi-GPU machines have emerged as an important platform offered on High Performance Computing and cloud data centers. Since these machines are shared among multiple users, it becomes increasingly important to protect applications against potential attacks. In this paper, we explore the vulnerability of Nvidia's DGX multi-GPU machines to covert and side channel attacks. These machines consist of a number of discrete GPUs that are interconnected through a combination of custom interconnect (NVLink) and PCIe connections. We reverse engineer the interconnected cache hierarchy and show that it is possible for an attacker on one GPU to cause contention on the L2 cache of another GPU. We use this observation to first develop a covert channel attack across two GPUs, achieving the best bandwidth of around 4 MB/s. We also develop a prime and probe attack on a remote GPU allowing an attacker to recover the cache access pattern of another workload. This access pattern can be used in any number of side channel attacks: we demonstrate a proof of concept attack that fingerprints the application running on the remote GPU, with high accuracy. We also develop a proof of concept attack to extract hyperparameters of a machine learning workload. Our work establishes for the first time the vulnerability of these machines to microarchitectural attacks and can guide future research to improve their security.

Graph Processing is an emerging workload for applications working with unstructured data, such as social network analysis, transportation networks, bioinformatics and operations research. We examine the problem of graph analytics over evolving graphs, which are graphs that change over time. The problem is challenging because it requires evaluation of a graph query on a sequence of graph snapshots over a time window, typically to track the progression of a property over time. In this paper, we introduce MEGA, a hardware accelerator designed for efficiently evaluating queries over evolving graphs. MEGA leverages CommonGraph, a recently proposed software approach for incrementally processing evolving graphs that gains efficiency by avoiding the need to process expensive deletions by converting them into additions. MEGA supports incremental event-based streaming of edge additions as well as execution of multiple snapshots concurrently to support evolving graphs. We propose Batch-Oriented-Execution (BOE), a novel batch-update scheduling technique that activates snapshots that share batches simultaneously to achieve both computation and data reuse. We introduce optimizations that pack compatible batches together, and pipeline batch processing. To the best of our knowledge, MEGA is the first graph accelerator for evolving graphs that evaluates graph queries over multiple snapshots simultaneously. MEGA achieves 24 × -120 × speedup over CommonGraph. It also achieves speedups ranging from 4.08 × to 5.98 × over JetStream, a state-of-the-art streaming graph accelerator.

Advances in deep-learning have enabled a wide range of promising applications. However, these systems are vulnerable to adversarial attacks; adversarially crafted pertur-bations to their inputs could cause them to misclassify. Most state-of-the-art adversarial attack generation algorithms focus primarily on controlling the noise magnitude to make it undetectable. The execution time is a secondary consideration for these attacks and the underlying assumption is that there are no time constraints. However, just-in-time adversarial attacks where an attacker opportunistically generates adversarial examples on-the-fly represent an even more critical threat, especially against real-time applications. Therefore, this paper introduces a new problem: how to systematically generate adversarial noise under real-time constraints? Understanding this problem improves our understanding of the threat these attacks pose to real-time systems and provides security evaluation benchmarks for future defenses. Therefore, first, we conduct a run-time analysis of adversarial generation algorithms. Our analysis show that universal attacks produce a general attack offline, with no online overhead. However, their success rate is limited because of their generality. In contrast, online algorithms, which target a specific input, are computationally expensive, making them inappropriate under time constraints. Thus, we propose ROOM, a novel Real-time Online-Offline attack construction Model where an offline component warms up the online algorithm, making it possible to generate highly successful attacks under time constraints. Our results show that ROOM can achieve high attack success rates under real-time constraints with up to 90x faster adversarial attack generation than state-of-the-art methods. For example, ROOM achieves 100% adversarial attack success rate on MNIST with a throughput of up to 1250 frame per second (FPS), more than 60% success rate with 200 FPS on CIFAR-10 and 60% with 16 FPS on ImageNet.

Connected vehicle (CV) applications promise to revolutionize our transportation systems, improving safety and traffic capacity while reducing environmental footprint. Many CV applications have been proposed towards these goals, with the US Department of Transportation (USDOT) recently initiating some designated deployment sites to enable experimentation and validation. While the focus of this initial development effort is on demonstrating the functionality of a range of proposed applications, recent attacks have demonstrated their vulnerability to application level attacks. In these attacks, a malicious actor operates within the application’s parameters but providing falsified information. This paper explores a framework that protects against such application-level attacks. Then, we analyze the impact of the attacks, showing that an individual attacker can have substantial effects on the safety and efficiency of traffic flow even in the presence of message security standards developed by USDOT, motivating the need for our defense. Our defense relies on physically modeling the vehicles and their interaction using dynamic models and state estimation filters as well as reinforcement learning. It combines these observations with knowledge of application rules and guidelines to capture logic deviations. We demonstrate that the resultant defense, called CVGuard, can accurately and promptly detect attacks, with low false positive rates over a range of attack scenarios for different CV applications.

This paper provides an end-to-end solution to defend against known microarchitectural attacks such as speculative execution attacks, fault-injection attacks, covert and side channel attacks, and unknown or evasive versions of these attacks. Current defenses are attack specific and can have unacceptably high performance overhead. We propose an approach that reduces the overhead of state-of-art defenses by over 95%, by applying defenses only when attacks are detected. Many current proposed mitigations are not practical for deployment; for example, InvisiSpec has 27% overhead and Fencing has 74% overhead while protecting against only Spectre attacks. Other mitigations carry similar performance penalties. We reduce the overhead for InvisiSpec to 1.26% and for Fencing to 3.45% offering performance and security for not only spectre attacks but other known transient attacks as well, including the dangerous class of LVI and Rowhammer attacks, as well as covering a large set of future evasive and zero-day attacks. Critical to our approach is an accurate detector that is not fooled by evasive attacks and that can generalize to novel zero-day attacks. We use a novel Generative framework, Evasion Vaccination (EVAX) for training ML models and engineering new security-centric performance counters. EVAX significantly increases sensitivity to detect and classify attacks in time for mitigation to be deployed with low false positives (4 FPs in every 1M instructions in our experiments). Such performance enables efficient and timely mitigations, enabling the processor to automatically switch between performance and security as needed.

Hardware Malware Detectors (HMDs) have recently been proposed to make systems more malware-resistant. HMDs use hardware features to detect malware as a computational anomaly. Several aspects of the detector construction have been explored, leading to detectors with high accuracy. In this article, we explore whether malware developers can modify malware to avoid HMDs detection. We show that existing HMDs can be effectively reverse-engineered and subsequently evaded. Next, we explore whether retraining using evasive malware would help and show that retraining is limited. To address these limitations, we propose a new type of Resilient HMDs (RHMDs) that stochastically switch between different detectors. These detectors can be shown to be provably more difficult to reverse engineer based on recent results in probably approximately correct (PAC) learnability theory. We show that indeed such detectors are resilient to both reverse engineering and evasion, and that the resilience increases with the number and diversity of the individual detectors. Furthermore, we show that an optimal switching strategy between the RHMDs base detectors not only reduces misclassification on evasive malware but also maintains high classification accuracy on non-evasive malware. Our results demonstrate that these HMDs offer effective defense against evasive malware at low additional complexity.

The Domain Name System (DNS) is a protocol supporting name resolution from Fully Qualified Domain Names (FQDNs) to the IP address of the machines corresponding to them. This resolution process is critical to the operation of the Internet, but is susceptible to a range of attacks. One of the most dangerous attack vectors is DNS poisoning where an attacker injects malicious entries into the DNS resolution forcing clients to be redirected from legitimate to malicious servers. Typically, poisoning attacks target a DNS resolver allowing attackers to poison a DNS entry for all machines that use the compromised resolver. However, recent defenses protect resolvers substantially limiting these attacks. In this paper, we present a new class of DNS poisoning attacks targeting the client-side DNS cache, which is used in mainstream operating systems, circumventing defenses protecting resolvers. We implemented the attack on Windows, Mac OS, and Ubuntu Linux machines. We also generalize the attack to work even when the client is behind a Network Address Translation (NAT) router. Our results show that we can reliably inject malicious DNS mappings, with on average, an order of tens of seconds. We also propose client-side mitigations and demonstrate that they can effectively mitigate the vulnerability.

In the past few years, an increasing number of machine-learning and deep learning structures, such as Convolutional Neural Networks (CNNs), have been applied to solving a wide range of real-life problems. However, these architectures are vulnerable to adversarial attacks: inputs crafted carefully to force the system output to a wrong label. Since machine-learning is being deployed in safety-critical and security-sensitive domains, such attacks may have catastrophic security and safety consequences. In this paper, we propose for the first time to use hardware-supported approximate computing to improve the robustness of machine learning classifiers. We show that our approximate computing implementation achieves robustness across a wide range of attack scenarios. Specifically, we show that successful adversarial attacks against the exact classifier have poor transferability to the approximate implementation. The transferability is even poorer for the black-box attack scenarios, where adversarial attacks are generated using a proxy model. Surprisingly, the robustness advantages also apply to white-box attacks where the attacker has unrestricted access to the approximate classifier implementation: in this case, we show that substantially higher levels of adversarial noise are needed to produce adversarial examples. Furthermore, our approximate computing model maintains the same level in terms of classification accuracy, does not require retraining, and reduces resource utilization and energy consumption of the CNN. We conducted extensive experiments on a set of strong adversarial attacks; We empirically show that the proposed implementation increases the robustness of a LeNet-5 and an Alexnet CNNs by up to 99% and 87%, respectively for strong transferability-based attacks along with up to 50% saving in energy consumption due to the simpler nature of the approximate logic. We also show that a white-box attack requires a remarkably higher noise budget to fool the approximate classifier, causing an average of 4 dB degradation of the PSNR of the input image relative to the images that succeed in fooling the exact classifier.

Signature-based authentication is a core cryptographic primitive essential for most secure networking protocols. We introduce a new signature scheme, MSS, that allows a client to efficiently authenticate herself to a server. We model our new scheme in an offline/online model where client online time is premium. The offline component derives basis signatures that are then composed based on the data being signed to provide signatures efficiently and securely during run-time. MSS requires the server to maintain state and is suitable for applications where a device has long-term associations with the server. MSS allows direct comparison to hash chains-based authentication schemes used in similar settings, and is relevant to resource-constrained devices e.g., IoT. We derive MSS instantiations for two cryptographic families, assuming the hardness of RSA and decisional Diffie-Hellman (DDH) respectively, demonstrating the generality of the idea. We then use our new scheme to design an efficient time-based one-time password (TOTP) protocol. Specifically, we implement two TOTP authentication systems from our RSA and DDH instantiations. We evaluate the TOTP implementations on Raspberry Pis which demonstrate appealing gains: MSS reduces authentication latency and energy consumption by a factor of ~82 and 792, respectively, compared to a recent hash chain-based TOTP system.

As modern GPU workloads grow in size and complexity, there is an ever-increasing demand for GPU computational power. Emerging workloads contain hundreds or thousands of GPU kernel launches, which incur high overheads, and exhibit data-dependent behavior between kernels, which requires synchronization, leading to GPU under-utilization. Task-based execution models have been proposed to solve these issues, but they require significant programmer effort to port applications to proprietary task-based programming models in order to specify tasks and task dependencies. To address this need, we propose BlockMaestro, a software-hardware solution that combines command queue reordering, kernel-launch-time static analysis, and runtime hardware support to dynamically identify and resolve thread-block level data dependencies between kernels. Through static analysis of memory access patterns at kernel-launch-time, BlockMaestro can extract inter-kernel thread block-level data dependencies. BlockMaestro also introduces kernel pre-launching to reduce the kernel launch overheads experienced by multiple dependent kernels. Correctness is enforced by dynamically resolving thread block-level data dependency at runtime through hardware support. BlockMaestro achieves an average speedup of 51.76% (up to 2.92x) on data-dependent benchmarks, and requires minimal hardware overhead.

Graphics Processing Units (GPUs) are ubiquitous components used across the range of today’s computing platforms, from phones and tablets, through personal computers, to high-end server class platforms. With the increasing importance of graphics and video workloads, recent processors are shipped with GPU devices that are integrated on the same chip. Integrated GPUs share some resources with the CPU and as a result, there is a potential for microarchitectural attacks from the GPU to the CPU or vice versa. We consider the potential for covert channel attacks that arise either from shared microarchitectural components (such as caches) or through shared contention domains (e.g., shared buses). We illustrate these two types of channels by developing two reliable covert channel attacks. The first covert channel uses the shared LLC cache in Intel’s integrated GPU architectures. The second is a contention based channel targeting the ring bus connecting the CPU and GPU to the LLC. This is the first demonstrated microarchitectural attack crossing the component boundary (GPU to CPU or vice versa). Cross-component channels introduce a number of new challenges that we had to overcome since they occur across heterogeneous components that use different computation models and are interconnected using asymmetric memory hierarchies. We also exploit GPU parallelism to increase the bandwidth of the communication, even without relying on a common clock. The LLC based channel achieves a bandwidth of 120 kbps with a low error rate of 2%, while the contention based channel delivers up to 400 kbps with a 0.8% error rate. We also demonstrate a proof-of-concept prime-and-probe side channel attack that probes the full LLC from the GPU.

Connected vehicles nowadays can provide a variety of useful and advanced services to their owners, manufacturers, transportation authorities, and other mobility service providers. Securing the complex sensing and networking protocols that enable these applications is an important and difficult problem. In this paper, we use blockchain which is traditionally used in applications from cryptocurrencies to smart contracts, as a potential solution to CV security. Specifically, we exploit the immutability of blockchain to ensure safety from falsified information and attacks. We demonstrate these properties by developing an algorithm that uses blockchain to maintain trusted communications between vehicles in the context of a cooperative ramp merging application.

While connected vehicle (CV) applications have the potential to revolutionize traditional transportation system, cyber and physical attacks on them may lead to disastrous consequences. In this work, we propose an efficient dual cyber-physical blockchain framework to build trust and secure communication for CV applications. Our approach incorporates blockchain technology and physical sensing capabilities of vehicles to quickly react to attacks in a large-scale vehicular network, with low resource overhead. We explore the application of our framework to three CV applications, i.e., highway merging, intelligent intersection management, and traffic network with route choices. Simulation results demonstrate the effectiveness of our blockchain-based framework in defending against spoofing attacks, bad mouthing attacks, and Sybil and voting attacks. We also provide analysis to show the timing and resource efficiency of our framework.

Graph Processing is at the core of many critical emerging workloads operating on unstructured data, including social network analysis, bioinformatics, and many others. Many applications operate on graphs that are constantly changing, i.e., new nodes and edges are added or removed over time. In this paper, we present JetStream, a hardware accelerator for evaluating queries over streaming graphs and capable of handling additions, deletions, and updates of edges. JetStream extends a recently proposed event-based accelerator for graph workloads to support streaming updates. It handles both accumulative and monotonic graph algorithms via an event-driven computation model that limits accesses to a smaller subset of the graph vertices, efficiently reuses the prior query results to eliminate redundancy, and optimizes the memory access pattern for enhanced memory bandwidth utilization. To the best of our knowledge, JetStream is the first graph accelerator that supports streaming graphs, reducing the computation time by 90% compared with cold-start computation using an existing accelerator. In addition, JetStream achieves about 18 × speedup over KickStarter and GraphBolt software frameworks at the large baseline batch sizes that these systems use with significantly higher speedup at smaller batch sizes.

Malware infects thousands of systems globally each day causing millions of dollars in damages. Which disassembler should a malware analyst choose in order to get the most accurate disassembly and be able to detect, analyze and defuse malware quickly? There is no clear answer to this question: (a) the performance of disassemblers varies across configurations, and (b) most prior work on disassemblers focuses on benign software and the x86 CPU architecture. In this work, we take a different approach and ask: why not use all the disassemblers instead of picking one? We present DisCo, a novel and effective approach to harness the collective capability of a group of disassemblers combining their output into an ensemble consensus. We develop and evaluate our approach using 1760 IoT malware binaries compiled with different compilers and compiler options for the ARM and MIPS architectures. First, we show that DisCo can combine the collective wisdom of disassemblers effectively. For example, our approach outperforms the best contributing disassembler by as much as 17.8% in the F1 score for function start identification for MIPS binaries compiled using GCC with O3 option. Second, the collective wisdom of the disassemblers can be brought back to improve each disassembler. As a proof of concept, we show that byte-level signatures identified by DisCo can improve the performance of Ghidra by as much as 13.6% in terms of the F1 score. Third, we quantify the effect of the architecture, the compiler, and the compiler options on the performance of disassemblers. Finally, the systematic evaluation within our approach led to a bug discovery in Ghidra v9.1, which was acknowledged by the Ghidra team.

Graphics Processing Units (GPUs) are commonly integrated with computing devices to enhance the performance and capabilities of graphical workloads. In addition, they are increasingly being integrated in data centers and clouds such that they can be used to accelerate data intensive workloads. Under a number of scenarios the GPU can be shared between multiple applications at a fine granularity allowing a spy application to monitor side channels and attempt to infer the behavior of the victim. For example, OpenGL and WebGL send workloads to the GPU at the granularity of a frame, allowing an attacker to interleave the use of the GPU to measure the side-effects of the victim computation through performance counters or other resource tracking APIs. We demonstrate the vulnerability by implementing three end-to-end attacks. We show that an OpenGL or CUDA based spy can fingerprint websites accurately (attack I), track user activities within the website, and even infer the keystroke timings for a password text box (attack II) with high accuracy. The third attack demonstrates how a CUDA spy application can derive the internal parameters of a neural network model being used by another CUDA application on the cloud. To counter these attacks, the paper suggests mitigations based on limiting the rate of the calls, or limiting the granularity of the returned information.

Machine learning (ML), and deep learning in particular, have become a critical workload as they are becoming increasingly applied at the core of a wide range of application spaces. Computer systems, from the architecture up, have been impacted by ML in two primary directions: (1) ML is an increasingly important computing workload, with new accelerators and systems targeted to support both training and inference at scale; and (2) ML supporting computer system decisions, both during design and run times, with new machine learning based algorithms controlling systems to optimize their performance, reliability and robustness. In this paper, we will explore the intersection of security, ML and computing systems, identifying both security challenges and opportunities. Machine learning systems are vulnerable to new attacks including adversarial attacks crafted to fool a classifier to the attacker's advantage, membership inference attacks attempting to compromise the privacy of the training data, and model extraction attacks seeking to recover the hyperparameters of a (secret) model. Architecture can be a target of these attacks when supporting ML (or is supported by ML), but also provides an opportunity to develop defenses against them, which we will illustrate with three examples from our recent work. First, we show how ML based hardware malware detectors can be attacked with adversarial perturbations to the Malware and how we can develop detectors that resist these attacks. Second, we show an example of microarchitectural side channel attacks that can be used to extract the secret parameters of a neural network and potential defenses against it. Finally, we discuss how hardware and systems can be used to make ML more robust against adversarial and other attacks.

Detecting microarchitectural attacks is critical given their proliferation in recent years. Many of these attacks exhibit intrinsic behaviors essential to the nature of their operation, such as creating contention or misspeculation. This study systematically investigates the microarchitectural footprints of hardware-based attacks and shows how they can be detected and classified using an efficient hardware predictor. We present a methodology to use correlated microarchitectural statistics to design a hardware-based neural predictor capable of detecting and classifying microarchitectural attacks before data is leaked. Once a potential attack is detected, it can be proactively mitigated by triggering appropriate countermeasures.Our hardware-based detector, PerSpectron, uses perceptron learning to identify and classify attacks. Perceptron-based prediction has been successfully used in branch prediction and other hardware-based applications. PerSpectron has minimal performance overhead. The statistics being monitored have similar overhead to already existing performance monitoring counters. Additionally, PerSpectron operates outside the processor's critical paths, offering security without added computation delay. Our system achieves a usable detection rate for detecting attacks such as SpectreV1, SpectreV2, SpectreRSB, Meltdown, breakingKSLR, Flush+Flush, Flush+Reload, Prime+Probe as well as cache-attack calibration programs. We also believe that the large number of diverse microarchitectural features offers both evasion resilience and interpretability-features not present in previous hardware security detectors. We detect these attacks early enough to avoid any data leakage, unlike previous work that triggers countermeasures only after data has been exposed.

The Register File (RF) is a critical structure in Graphics Processing Units (GPUs) responsible for a large portion of the area and power. To simplify the architecture of the RF, it is organized in a multi-bank configuration with a single port for each bank. Not surprisingly, the frequent accesses to the register file during kernel execution incur a sizeable overhead in GPU power consumption, and introduce delays as accesses are serialized when port conflicts occur. In this paper, we observe that there is a high degree of temporal locality in accesses to the registers: within short instruction windows, the same registers are often accessed repeatedly. We characterize the opportunities to reduce register accesses as a function of the size of the instruction window considered, and establish that there are many recurring reads and updates of the same register operands in most GPU computations. To exploit this opportunity, we propose Breathing Operand Windows (BOW), an enhanced GPU pipeline and operand collector organization that supports bypassing register file accesses and instead passes values directly between instructions within the same window. Our baseline design can only bypass register reads; we introduce an improved design capable of also bypassing unnecessary write operations to the RF. We introduce compiler optimizations to help guide the write-back destination of operands depending on whether they will be reused to further reduce the write traffic. To reduce the storage overhead, we analyze the occupancy of the bypass buffers and discover that we can significantly down size them without losing performance. BOW along with optimizations reduces dynamic energy consumption of the register file by 55% and increases the performance by 11%, with a modest overhead of 12KB increase in the size of the operand collectors (4% of the register file size).

Graph processing workloads are memory intensive with irregular access patterns and large memory footprint resulting in low data locality. Their popular software implementations typically employ either Push or Pull style propagation of changes through the graph over multiple iterations that follow the Bulk Synchronous Model. The performance of these algorithms on traditional computing systems is limited by random reads/writes of vertex values, synchronization overheads, and additional overheads for tracking active sets of vertices or edges across iterations. In this paper, we present GraphPulse, a hardware framework for asynchronous graph processing with event-driven scheduling that overcomes the performance limitations of software frameworks. Event-driven computation model enables a parallel dataflow-style execution where atomic updates and active sets tracking are inherent to the model; thus, scheduling complexity is reduced and scalability is enhanced. The dataflow nature of the architecture also reduces random reads of vertex values by carrying the values in the events themselves. We capitalize on the update properties commonly present in graph algorithms to coalesce in-flight events and substantially reduce the event storage requirement and the processing overheads incurred. GraphPulse event-model naturally supports asynchronous graph processing, enabling substantially faster convergence by exploiting available parallelism, reducing work, and eliminating synchronization at iteration boundaries. The framework provides easy to use programming interface for faster development of hardware graph accelerators. A single GraphPulse accelerator achieves up to 74x speedup (28x on average) over Ligra, a state of the art software framework, running on a 12 core CPU. It also achieves an average of 6.2x speedup over Graphicionado, a state of the art graph processing accelerator.

Spectre attacks and their many subsequent variants are a new vulnerability class affecting modern CPUs. The attacks rely on the ability to misguide speculative execution, generally by exploiting the branch prediction structures, to execute a vulnerable code sequence speculatively. In this paper, we propose to use Control-Flow Integrity (CFI), a security technique used to stop control-flow hijacking attacks, on the committed path, to prevent speculative control-flow from being hijacked to launch the most dangerous variants of the Spectre attacks (Spectre-BTB and Spectre-RSB). Specifically, CFI attempts to constrain the possible targets of an indirect branch to a set of legal targets defined by a pre-calculated control-flow graph (CFG). As CFI is being adopted by commodity software (e.g., Windows and Android) and commodity hardware (e.g., Intel's CET and ARM's BTI), the CFI information becomes readily available through the hardware CFI extensions. With the CFI information, we apply CFI principles to also constrain illegal control-flow during speculative execution. Specifically, our proposed defense, SpecCFI, ensures that control flow instructions target legal destinations to constrain dangerous speculation on forward control-flow paths (indirect calls and branches). We augment this protection with a precise speculation-aware hardware stack to constrain speculation on backward control-flow edges (returns). We combine this solution with existing solutions against branch target predictor attacks (Spectre-PHT) to close all known non-vendor-specific Spectre vulnerabilities. We show that SpecCFI results in small overheads both in terms of performance and additional hardware complexity.

Hardware-based malware detectors (HMDs) are a promising new approach to defend against malware. HMDs collect low-level architectural features and use them to classify malware from normal programs. With simple hardware support, HMDs can be always on, operating as a first line of defense that prioritizes the application of more expensive and more accurate software-detector. In this paper, our goal is to increase the accuracy of HMDs, to improve detection, and reduce overhead. We use specialized detectors targeted towards a specific type of malware to improve the detection of each type. Next, we use ensemble learning techniques to improve the overall accuracy by combining detectors. We explore detectors based on logistic regression (LR) and neural networks (NN). The proposed detectors reduce the false-positive rate by more than half compared to using a single detector, while increasing their sensitivity. We develop metrics to estimate detection overhead; the proposed detectors achieve more than 16.6× overhead reduction during online detection compared to an idealized software-only detector, with an 8× improvement in relative detection time. NN detectors outperform LR detectors in accuracy, overhead (by 40 percent), and time-to-detection of the hardware component (by 5×). Finally, we characterize the hardware complexity by extending an open-core and synthesizing it on an FPGA platform, showing that the overhead is minimal.

The Register File (RF) in GPUs is a critical structure that maintains the state for thousands of threads that support the GPU processing model. The RF organization substantially affects the overall performance and the energy efficiency of a GPU. For example, the frequent accesses to the RF consume a substantial amount of the dynamic energy, and port contention due to limited ports on operand collectors and register file banks affect performance as register operations are serialized. We present CORF, a compiler-assisted Coalescing Operand Register File which performs register coalescing by combining reads to multiple registers required by a single instruction, into a single physical read. To enable register coalescing, CORF utilizes register packing to co-locate narrow-width operands in the same physical register. CORF uses compiler hints to identify which register pairs are commonly accessed together. CORF saves dynamic energy by reducing the number of physical register file accesses, and improves performance by combining read operations, as well as by reducing pressure on the register file. To increase the coalescing opportunities, we re-architect the physical register file to allow coalescing reads across different physical registers that reside in mutually exclusive sub-banks; we call this design CORF++. The compiler analysis for register allocation for CORF++ becomes a form of graph coloring called the bipartite edge frustration problem. CORF++ reduces the dynamic energy of the RF by 17%, and improves IPC by 9%.

Speculative attacks, such as Spectre and Meltdown, target speculative execution to access privileged data and leak it through a side-channel. In this paper, we introduce (SafeSpec), a new model for supporting speculation in a way that is immune to the side-channel leakage by storing side effects of speculative instructions in separate structures until they commit. Additionally, we address the possibility of a covert channel from speculative instructions to committed instructions before these instructions are committed. We develop a cycle accurate model of modified design of an x86-64 processor and show that the performance impact is negligible.

CPU memory prefetchers can substantially interfere with prime and probe cache side-channel attacks, especially on in-order CPUs which use aggressive prefetching. This interference is not accounted for in previous attacks. In this paper, we propose PAPP, a Prefetcher-Aware Prime Probe attack that can operate even in the presence of aggressive prefetchers. Specifically, we reverse engineer the prefetcher and replacement policy on several CPUs and use these insights to design a prime and probe attack that minimizes the impact of the prefetcher. We evaluate PAPP using Cache Side-channel Vulnerability (CSV) metric and demonstrate the substantial improvements in the quality of the channel under different conditions.

Graphics processing units (GPUs) are moving towards supporting concurrent kernel execution where multiple kernels may be co-executed on the same GPU and even on the same streaming multiprocessor (SM) core. While concurrent kernel execution improves hardware resource utilization, it opens up vulnerabilities to covert-channel and side-channel attacks. These attacks exploit information leakage across kernels that results from contention on shared resources; they have been shown to be a dangerous threat on CPUs, and are starting to be demonstrated on GPUs. The unique micro-architectural features of GPUs, such as specialized cache structures and massive parallel thread support, create opportunities for GPU-specific channels to be formed. In this paper, we propose GPUGuard, a decision tree based detection and a hierarchical defense framework that can reliably close the covert channels. Our results show that GPUGuard can detect contention with 100% sensitivity and a small (8.5%) false positive rate. The timing channels are mitigated through Tangram, a GPU-specific contention channel elimination scheme, with only 8% to 23% overhead when there is an attack and zero performance overhead when no attacks are detected. Compared to temporal partitioning, GPUGuard is 69%-96% faster in various architectures even when active, showing that it is possible to gain substantial performance from executing concurrent kernels on a single SM while securing GPUs against these attacks.

DNS poisoning attacks inject malicious entries into the DNS resolution system, allowing an attacker to redirect clients to malicious servers. These attacks typically target a DNS resolver allowing attackers to poison a DNS entry for all machines that use the compromised resolver. However, recent defenses can effectively protect resolvers rendering classical DNS poisoning attacks ineffective. In this paper, we present a new class of DNS poisoning attacks targeting the client-side DNS cache. The attack initiates DNS poisoning on the client cache, which is used in all main stream operating systems to improve DNS performance, circumventing defenses targeting resolvers. Our attack allows an off-path attacker to collaborate with a piece of an unprivileged malware to poison the OS-wide DNS cache on a client machine. We developed the attack on Windows, Mac OS, and Ubuntu Linux. Interestingly, the behaviors of the three operating systems are distinct and the vulnerabilities require different strategies to exploit. We also generalize the attack to work even when the client is behind a Network Address Translation (NAT) router. Our results show that we can reliably inject malicious DNS mappings, with on average, an order of tens of seconds. Finally, we propose a defense against this type of poisoning attacks.

We present LATCH (short for Locality-Aware Taint CHecker), a generalizable architecture for optimizing dynamic information flow tracking (DIFT). LATCH exploits the observation that information flows under DIFT exhibit strong temporal locality, with typical applications manipulating sensitive data during limited phases of computation. This property allows LATCH to monitor significant spans of execution using lightweight, coarse-grained checks, invoking precise, computationally intensive tracking logic only during periods of execution that involve sensitive data. LATCH implements this policy without sacrificing the accuracy of DIFT.

We present BranchScope - a new side-channel attack where the attacker infers the direction of an arbitrary conditional branch instruction in a victim program by manipulating the shared directional branch predictor. The directional component of the branch predictor stores the prediction on a given branch (taken or not-taken) and is a different component from the branch target buffer (BTB) attacked by previous work. BranchScope is the first fine-grained attack on the directional branch predictor, expanding our understanding of the side channel vulnerability of the branch prediction unit. Our attack targets complex hybrid branch predictors with unknown organization. We demonstrate how an attacker can force these predictors to switch to a simple 1-level mode to simplify the direction recovery. We carry out BranchScope on several recent Intel CPUs and also demonstrate the attack against an SGX enclave.

Graphics Processing Units (GPUs) are commonly integrated with computing devices to enhance the performance and capabilities of graphical workloads. In addition, they are increasingly being integrated in data centers and clouds such that they can be used to accelerate data intensive workloads. Under a number of scenarios the GPU can be shared between multiple applications at a fine granularity allowing a spy application to monitor side channels and attempt to infer the behavior of the victim. For example, OpenGL and WebGL send workloads to the GPU at the granularity of a frame, allowing an attacker to interleave the use of the GPU to measure the side-effects of the victim computation through performance counters or other resource tracking APIs. We demonstrate the vulnerability using two applications. First, we show that an OpenGL based spy can fingerprint websites accurately, track user activities within the website, and even infer the keystroke timings for a password text box with high accuracy. The second application demonstrates how a CUDA spy application can derive the internal parameters of a neural network model being used by another CUDA application, illustrating these threats on the cloud. To counter these attacks, the paper suggests mitigations based on limiting the rate of the calls, or limiting the granularity of the returned information.

Recent studies investigated the performance of Parallel Discrete Event Simulation (PDES) on Intel Xeon Phi manycore processors, but generally reported underwhelming performance results, especially at high scales when all cores and thread contexts are fully loaded. While the lack of scalability in an earlier study on a Knights Corner (KC) processor is an artifact of physical limitations of the KC system, performance challenges on a Knights Landing (KNL) system partially stem from a slower global virtual time (GVT) computation algorithm used in that study. In this paper, we re-examine PDES performance on KNL under more efficient GVT algorithms to alleviate the GVT bottleneck. Specifically, we compare a synchronous GVT algorithm based on barrier synchronization, and two asynchronous GVT implementations: a modified Mattern's algorithm for shared memory systems and a recently-proposed wait-free algorithm. Using the ROSS simulator, we demonstrate that minimizing the GVT bottleneck results in significant improvement in scalability, allowing the simulation to scale with performance all the way to 250 threads (per chip). Interestingly, we observe that while for the balanced models the wait-free algorithm is a clear winner, barrier-based GVT provides significantly better results for imbalanced models executed at high scale. We also perform detailed simulation profiling to understand the underlying reasons for these performance trends.

Dynamic neural networks enable higher representation flexibility compared to networks with a fixed architecture and are extensively deployed in problems dealing with varying input-induced network structure, such as those in Natural Language Processing. One of the standard optimizations used in static net training is persistency of recurrent weights on the chip. In dynamic nets, possibly-inhomogeneous computation graph for every input prevents caching recurrent weights in GPU registers. Therefore, existing solutions suffer from excessive recurring off-chip memory loads as well as compounded kernel launch overheads leading to underutilization of GPU SMs. In this paper, we present a software system that enables persistency of weight matrices during the training of dynamic neural networks on the GPU. Before the training begins, our approach named Virtual Persistent Processor Specialization (VPPS) specializes a forward-backward propagation kernel that contains in-register caching and operation routines. VPPS virtualizes persistent kernel CTAs as CISC-like vector processors that can be guided to execute supplied instructions. VPPS greatly reduces the overall amount of off-chip loads by caching weight matrices on the chip, while simultaneously, provides maximum portability as it does not make any assumptions about the shape of the given computation graphs hence fulfilling dynamic net requirements. We implemented our solution on DyNet and abstracted away its design complexities by providing simple function calls to the user. Our experiments on a Volta micro-architecture shows that, unlike the most competitive solutions, VPPS shows excellent performance even in small batch sizes and delivers up to 6x speedup on training dynamic nets.

We consider the problem of how to provide an execution environment where the application's secrets are safe even in the presence of malicious system software layers. We propose Iso-X-a flexible, fine-grained hardware-supported framework that provides isolation for security-critical pieces of an application such that they can execute securely even in the presence of untrusted system software. Isolation in Iso-X is achieved by creating and dynamically managing compartments (isolated software modules) to host critical fragments of code and associated data. Iso-X provides fine-grained isolation at the memory-page level, flexible allocation of memory, and a low-complexity, hardware-only trusted computing base. Iso-X requires minimal additional hardware, a small number of new ISA instructions to manage compartments, and minimal changes to the operating system which need not be in the trusted computing base. The run-time performance overhead of Iso-X is negligible and even the overhead of creating and destroying compartments is modest. An FPGA implementation of Iso-X runtime mechanisms shows a negligible impact on the processor cycle time.

Recently, side-channel attacks on Last Level Caches (LLCs) were demonstrated. The attacks require the ability to evict critical data from the cache hierarchy, making future accesses visible. We propose Relaxed Inclusion Caches (RIC), a low-complexity cache design protecting against LLC side channel attacks. RIC relaxes inclusion when it is not needed, preventing the attacker from replacing the victim's data from the local core caches thus protecting critical data from leakage. RIC improves performance (by about 10%) and retains snoop filtering capabilities of inclusive cache hierarchies, while requiring only minimal changes to the cache.

In this paper we revisit the security properties of extended access control schemes that are used to protect application secrets from untrusted system software. We demonstrate the vulnerability of several recent proposals to a class of attacks we call mapping attacks. We argue that protection from such attacks requires verification of the address space integrity and propose the concept of self-verified address spaces (SVAS), where the applications themselves are made aware of the requested changes in the page mappings and are placed in charge of verifying them. SVAS equips an application with a customized verification model with several attractive functional and performance properties. We implemented the attacks and a complete prototype of SVAS in Linux and the QEMU emulator. Our results demonstrate that SVAS can prevent mapping attacks on extended access control systems with minimal performance overhead, hardware modifications and software complexity.

Hardware Malware Detectors (HMDs) have recently been proposed as a defense against the proliferation of malware. These detectors use low-level features, that can be collected by the hardware performance monitoring units on modern CPUs to detect malware as a computational anomaly. Several aspects of the detector construction have been explored, leading to detectors with high accuracy. In this paper, we explore the question of how well evasive malware can avoid detection by HMDs. We show that existing HMDs can be effectively reverse-engineered and subsequently evaded, allowing malware to hide from detection without substantially slowing it down (which is important for certain types of malware). This result demonstrates that the current generation of HMDs can be easily defeated by evasive malware. Next, we explore how well a detector can evolve if it is exposed to this evasive malware during training. We show that simple detectors, such as logistic regression, cannot detect the evasive malware even with retraining. More sophisticated detectors can be retrained to detect evasive malware, but the retrained detectors can be reverse-engineered and evaded again. To address these limitations, we propose a new type of Resilient HMDs (RHMDs) that stochastically switch between different detectors. These detectors can be shown to be provably more difficult to reverse engineer based on resent results in probably approximately correct (PAC) learnability theory. We show that indeed such detectors are resilient to both reverse engineering and evasion, and that the resilience increases with the number and diversity of the individual detectors. Our results demonstrate that these HMDs offer effective defense against evasive malware at low additional complexity.

General Purpose Graphics Processing Units (GPGPUs) are present in most modern computing platforms. They are also increasingly integrated as a computational resource on clusters, data centers, and cloud infrastructure, making them possible targets for attacks. We present a first study of covert channel attacks on GPGPUs. GPGPU attacks offer a number of attractive properties relative to CPU covert channels. These channels also have characteristics different from their counterparts on CPUs. To enable the attack, we first reverse engineer the hardware block scheduler as well as the warp to warp scheduler to characterize how co-location is established. We exploit this information to manipulate the scheduling algorithms to create co-residency between the trojan and the spy. We study contention on different resources including caches, functional units and memory, and construct operational covert channels on all these resources. We also investigate approaches to increase the bandwidth of the channel including: (1) using synchronization to reduce the communication cycle and increase robustness of the channel; (2) exploiting the available parallelism on the GPU to increase the bandwidth; and (3) exploiting the scheduling algorithms to create exclusive co-location to prevent interference from other possible applications. We demonstrate operational versions of all channels on three different Nvidia GPGPUs, obtaining error-free bandwidth of over 4 Mbps, making it the fastest known microarchitectural covert channel under realistic conditions.

In this paper, we present initial experiences implementing a general Parallel Discrete Event Simulation (PDES) accelerator on a Field Programmable Gate Array (FPGA). The accelerator can be specialized to any particular simulation model by defining the object states and the event handling logic, which are then synthesized into a custom accelerator for the given model. The accelerator consists of several event processors that can process events in parallel while maintaining the dependencies between them. Events are automatically sorted by a self-sorting event queue. The accelerator supports optimistic simulation by automatically keeping track of event history and supporting rollbacks. The architecture is limited in scalability locally by the communication and port bandwidth of the different structures. However, it is designed to allow multiple accelerators to be connected together to scale up the simulation. We evaluate the design and explore several design tradeoffs and optimizations. We show the accelerator can scale to 64 concurrent event processors relative to the performance of a single event processor.

Performance and scalability of Parallel Discrete Event Simulation (PDES) is often limited by fine-grain communication, especially in execution environments with high communication cost. However, the low cost of on-chip communication in emerging many-core processors offers a promise to substantially alleviate conventional PDES bottlenecks. In this paper, we present a detailed evaluation and characterization of multi-threaded ROSS simulator on Intel's Knights Landing (KNL) processor. KNL is the second generation of the Intel Xeon Phi family of processors offering significant architecture improvements including 64 out-of-order multithreaded cores, sharing of some levels of the cache hierarchy among the cores, fast 2D mesh interconnect network and the ability to reconfigure the processor to support various clustering modes. We analyze the performance and scalability of ROSS simulator on KNL processor under different thread counts, communication patterns, event processing granularities, synchronization periods, thread placement policies, and workload partitioning schemes. We conclude that within a single KNL processor, up to 2X performance improvement can be achieved compared to commodity Xeon multicore processors. We show that in most cases the performance of ROSS scales well with the best results achieved when thread affinity is assigned, CPU cores are evenly loaded, cache sharing is exploited and communication is limited to small clusters of cores.

Recently demonstrated side-channel attacks on shared Last Level Caches (LLCs) work under a number of constraints on both the system and the victim behavior that limit their applicability. This paper demonstrates on a real system a new high-resolution LLC side channel attack that relaxes some of these assumptions. Specifically, we introduce and exploit new techniques to achieve high-resolution tracking of the victim accesses to enable attacks on ciphers where critical events have a small cache footprint. We compare the quality of the side-channel in our attack to that obtained using Flush+ Reload attacks, which are significantly more precise but work only when the sensitive data is shared between the attacker and the victim. We show that our attack frequently obtains an equal quality channel, which we also confirmed by reconstructing the victim cryptographic key.

Smart camera networks (SCNs) are increasingly used in applications such as homeland security, border control and traffic monitoring. The cameras are often wireless with an organically growing structure, to reduce the overhead of deployment. We frame a new and important problem in SCNs: how to transmit videos from multiple cameras with overlapping coverage given the limited available wireless bandwidth to maximize the quality of the received videos. We call this problem Coordinated Transport of Correlated Videos (CTCV). CTCV is a more general version of 3D video transport: in that problem, highly correlated videos from two cameras (that provide the 3D perspective) are jointly encoded exploiting their pre-defined and known overlap. In contrast, in CTCV there is an arbitrary number of cameras whose overlap is not known apriori and that require transmission as multiple video streams. To effectively support CTCV, we propose a video delivery protocol that consists of two primary components: (1) Consolidation of correlated videos from multiple cameras which removes spatially redundant fields-of-view; and (2) Network and coverage aware bandwidth allocation to optimize coverage quality cooperatively among the different video streams to match the available bandwidth. We formulate the problem of optimal bandwidth allocation for maximizing coverage. We propose and investigate different heuristic policies for bandwidth allocation. We evaluate CTCV using data from a small camera testbed as well as topologies from realistic deployments. Experiments show that CTCV achieves around 10 dB gains in video quality in the scenarios we consider.

Address Space Layout Randomization (ASLR) is a widely-used technique that protects systems against a range of attacks. ASLR works by randomizing the offset of key program segments in virtual memory, making it difficult for an attacker to derive the addresses of specific code objects and consequently redirect the control flow to this code. In this paper, we develop an attack to derive kernel and user-level ASLR offset using a side-channel attack on the branch target buffer (BTB). Our attack exploits the observation that an adversary can create BTB collisions between the branch instructions of the attacker process and either the user-level victim process or on the kernel executing on its behalf. These collisions, in turn, can impact the timing of the attacker's code, allowing the attacker to identify the locations of known branch instructions in the address space of the victim process or the kernel. We demonstrate that our attack can reliably recover kernel ASLR in about 60 milliseconds when performed on a real Haswell processor running a recent version of Linux. Finally, we describe several possible protection mechanisms, both in software and in hardware.

The inclusive permissions structure (e.g., the Intel ring model) of modern commodity CPUs provides privileged system software layers with arbitrary permissions to access and modify client processes, allowing them to manage these clients and the system resources efficiently. Unfortunately, these inclusive permissions allow a compromised high-privileged software layer to perform arbitrary malicious activities. In this article, our goal is to prevent attacks that cross system layers while maintaining the abilities of system software to manage the system and allocate resources. In particular, we present a hardware-supported page permission framework for physical pages that is based on the concept of noninclusive sets of memory permissions for different layers of system software (such as hypervisors, operating systems, and user-level applications). Instead of viewing privilege levels as an ordered hierarchy with each successive level being more privileged, we view them as distinct levels each with its own set of permissions. In order to enable system software to manage client processes, we define a set of legal permission transitions that support resource allocation but preserve security. We show that the model prevents a range of recent attacks. We also show that it can be implemented with negligible performance overhead (both at load time and at runtime), low hardware complexity, and minimal changes to the commodity OS and hypervisor code.

Covert channels through shared processor resources provide secret communication between two malicious processes: the trojan and the spy. In this article, we classify, analyze, and compare covert channels through dynamic branch prediction units in modern processors. Through experiments on a real hardware platform, we compare contention-based channel and the channel that is based on exploiting the branch predictor’s residual state. We analyze these channels in SMT and single-threaded environments under both clean and noisy conditions. Our results show that the residual state-based channel provides a cleaner signal and is effective even in noisy execution environments with another application sharing the same physical core with the trojan and the spy. We also estimate the capacity of the branch predictor covert channels and describe a software-only mitigation technique that is based on randomizing the state of the predictor tables on context switches. We show that this protection eliminates all covert channels through the branch prediction unit with minimal impact on performance.

Security exploits and ensuant malware pose an increasing challenge to computing systems as the variety and complexity of attacks continue to increase. In response, software-based malware detection tools have grown in complexity, thus making it computationally difficult to use them to protect systems in real-time. Therefore, software detectors are applied selectively and at a low frequency, creating opportunities for malware to remain undetected. In this paper, we propose Malware-Aware Processors (MAP) - processors augmented with a hardware-based online malware detector to serve as the first line of defense to differentiate malware from legitimate programs. The output of this detector helps the system prioritize how to apply more expensive software-based solutions. The always-on nature of MAP detector helps protect against intermittently operating malware. We explore the use of different features for classification and study both logistic regression and neural networks. We show that the detectors can achieve excellent performance, with little hardware overhead. We integrate the MAP implementation with an open-source x86-compatible core, synthesizing the resulting design to run on an FPGA.

The accuracy of wireless network packet simulation critically depends on the quality of wireless channel models. Path loss is the stationary component of the channel model affected by the shadowing in the environment. Existing path loss models are inaccurate, require excessive measurement or computational overhead, and/or often cannot be made to represent a given environment. This paper contributes a flexible path loss model that uses a novel approach for spatially coherent interpolation from available nearby channels to allow accurate and efficient modeling of path loss. We show that the proposed model, called Double Regression (DR), generates a correlated space, allowing both the sender and the receiver to move without abrupt change in path loss. Combining DR with a traditional temporal fading model, such as Rayleigh fading, provides an accurate and efficient channel model that we integrate with the NS-2 simulator. We use measurements to validate the accuracy of the model for a number of scenarios. We also show that there is substantial impact on simulation behavior when path loss is modeled accurately. Finally, we show that unlike statistical models, DR can make a simulation representative of a given environment by using a small number of seeding measurements. Thus, DR provides a cost-effective alternative to ray tracing or detailed site surveys.

Security exploits and ensuant malware pose an increasing challenge to computing systems as the variety and complexity of attacks continue to increase. In response, software-based malware detection tools have grown in complexity, thus making it computationally difficult to use them to protect systems in real-time. Therefore, software detectors are applied selectively and at a low frequency, creating opportunities for malware to remain undetected. In this paper, we propose Malware-Aware Processors (MAP) - processors augmented with an online hardware-based detector to serve as the first line of defense to differentiate malware from legitimate programs. The output of this detector helps the system prioritize how to apply more expensive software-based solutions. The always-on nature of MAP detector helps protect against intermittently operating malware. Our work improves on the state of the art in the following ways: (1) We define and explore the use of sub-semantic features for online detection of malware. (2) We explore hardware implementations and show that simple classifiers appropriate for such implementations can effectively classify malware. We also study different classifiers, develop implementation optimizations, and explore complexity to performance trade-offs. (3) We propose a two-level detection framework where the hardware classifier prioritizes the work of a more accurate but more expensive software defense mechanism. (4) We integrate the MAP implementation with an open-source x86-compatible core, synthesizing the resulting design to run on an FPGA.

One of the benefits of multiprogramming in conventional systems is to allow effective use of resources. For example, when one application blocks for I/O, another can use the available CPU time, improving throughput and performance. In a multithreaded environment, contention for resources can lead to substantial interference between applications: an application with dependencies can suffer if a thread holding critical dependency is not scheduled in time. In the HPC community, this problem is often addressed by reservation-based schedulers such as Gang scheduling. However, such schedulers cannot reap the benefits of resource multiplexing leading to underutilization of the resources and lower overall throughput of the system. In this paper, we explore the trade off between contention and reservation in multithreaded application scheduling on multicourse systems. We show that neither approach is optimal under all conditions. We propose Controlled Contention (CC) -- a scheduling algorithm that allows controlled contention for resources, allowing the benefits of contention while supporting limited reservation to reduce interference. CC provides around 25% improvement in relative speedup over the Completely Fair Scheduler (CFS). We also show that CC can significantly benefit from application-level interference management while providing fairness that is not possible to achieve with application-level adaptation alone. The combined approach (CC with application-level adaptation)provides an average of 21% improvement in throughput, 35% improvement in relative speedup and 36% reduction in energy for the application mixes we consider.

Code Reuse Attacks (CRAs) recently emerged as a new class of security exploits. CRAs construct malicious programs out of small fragments (gadgets) of existing code, thus eliminating the need for code injection. Existing defenses against CRAs often incur large performance overheads or require extensive binary rewriting and other changes to the system software. In this paper, we examine a signature-based detection of CRAs, where the attack is detected by observing the behavior of programs and detecting the gadget execution patterns. We first demonstrate that naive signature-based defenses can be defeated by introducing special “delay gadgets” as part of the attack. We then show how a software-configurable signature-based approach can be designed to defend against such stealth CRAs, including the attacks that manage to use longer-length gadgets. The proposed defense (called SCRAP) can be implemented entirely in hardware using simple logic at the commit stage of the pipeline. SCRAP is realized with minimal performance cost, no changes to the software layers, and no implications on binary compatibility. Finally, we show that SCRAP generates no false alarms on a wide range of applications.

Protecting modern computer systems and complex software stacks against the growing range of possible attacks is becoming increasingly difficult. The architecture of modern commodity systems allows attackers to subvert privileged system software often using a single exploit. Once the system is compromised, inclusive permissions used by current architectures and operating systems easily allow a compromised high-privileged software layer to perform arbitrary malicious activities, even on behalf of other software layers. This paper presents a hardware-supported page permission scheme for the physical pages that is based on the concept of non-inclusive sets of memory permissions for different layers of system software such as hypervisors, operating systems, and user-level applications. Instead of viewing privilege levels as an ordered hierarchy with each successive level being more privileged, we view them as distinct levels each with its own set of permissions. Such a permission mechanism, implemented as part of a processor architecture, provides a common framework for defending against a range of recent attacks. We demonstrate that such a protection can be achieved with negligible performance overhead, low hardware complexity and minimal changes to the commodity OS and hypervisor code.

We consider the problem of target coverage in visual sensor networks with Pan-Tilt-Zoom (PTZ) cameras. The finely controllable movement in PTZ dimensions creates a large number of possible Field-of-View (FoV) settings, making it prohibitively expensive to consider them all in coverage algorithms. However, these FoVs are redundant as each group of targets is generally covered by many FoVs. Thus, an important problem is, how to identify FoVs that cover all maximal subsets of targets (MaxFoV) efficiently? We show that MaxFoV is an instance of generating all maximal cliques, which is NP-hard in general but polynomial if the number of cliques is polynomial. We construct an optimal algorithm to solve the problem with a worst case complexity of O(n3). Simulation and testbed experiments show that the algorithm drastically reduces the number of FoVs allowing multi-camera coverage to scale without sacrificing coverage quality.

Topology Control (TC) algorithms for multi-hop wireless networks create a connected communication subgraph that satisfies some topological properties by assigning appropriate transmission power to each node. A topology is said to be minimum-energy path-preserving if it preserves minimum energy paths between every pair of nodes. Creating minimum-energy path-preserving sparse topologies is a fundamental research problem in TC that has been addressed in several recent research works. Although sparseness is a key metric in comparing the performance of such algorithms, none of these prior works provides analytical models to determine the sparseness. In this paper, we provide a generic analytical model for evaluating sparseness of such topologies. The derived analytical expressions are useful in determining topology size without running simulations or prior to the deployment of real systems. Moreover, we demonstrate how to analytically couple sparseness of topologies with the radio transceiver parameters. The analytical expressions are validated through extensive simulation experiments.

We consider the problem of how to provide an execution environment where the application's secrets are safe even in the presence of malicious system software layers. We propose Iso-X -- a flexible, fine-grained hardware-supported framework that provides isolation for security-critical pieces of an application such that they can execute securely even in the presence of untrusted system software. Isolation in Iso-X is achieved by creating and dynamically managing compartments to host critical fragments of code and associated data. Iso-X provides fine-grained isolation at the memory-page level, flexible allocation of memory, and a low-complexity, hardware-only trusted computing base. Iso-X requires minimal additional hardware, a small number of new ISA instructions to manage compartments, and minimal changes to the operating system which need not be in the trusted computing base. The run-time performance overhead of Iso-X is negligible and even the overhead of creating and destroying compartments is modest. Iso-X offers higher memory flexibility than the recently proposed SGX design from Intel, allowing both fluid partitioning of the vailable memory space and dynamic growth of compartments. An FPGA implementation of Iso-X runtime mechanisms shows a negligible impact on the processor cycle time.

As multicore and manycore processor architectures are emerging and the core counts per chip continue to increase, it is important to evaluate and understand the performance and scalability of Parallel Discrete Event Simulation (PDES) on these platforms. Most existing architectures are still limited to a modest number of cores, feature simple designs and do not exhibit heterogeneity, making it impossible to perform comprehensive analysis and evaluations of PDES on these platforms. Instead, in this paper we evaluate PDES using a full-system cycle-accurate simulator of a multicore processor and memory subsystem. With this approach, it is possible to flexibly configure the simulator and perform exploration of the impact of architecture design choices on the performance of PDES. In particular, we answer the following four questions with respect to PDES performance and scalability: (1) For the same total chip area, what is the best design point in terms of the number of cores and the size of the on-chip cache? (2) What is the impact of using in-order vs. out-of-order cores? (3) What is the impact of a heterogeneous system with a mix of in-order and out-of-order cores? (4) What is the impact of object partitioning on PDES performance in heterogeneous systems? To answer these questions, we use MARSSx86 simulator for evaluating performance, and rely on Cacti and McPAT tools to derive the area and latency estimates for cores and caches.

Code reuse attacks (CRAs) are recent security exploits that allow attackers to execute arbitrary code on a compromised machine. CRAs, exemplified by return-oriented and jump-oriented programming approaches, reuse fragments of the library code, thus avoiding the need for explicit injection of attack code on the stack. Since the executed code is reused existing code, CRAs bypass current hardware and software security measures that prevent execution from data or stack regions of memory. While software-based full control flow integrity (CFI) checking can protect against CRAs, it includes significant overhead, involves non-trivial effort of constructing a control flow graph, relies on proprietary tools and has potential vulnerabilities due to the presence of unintended branch instructions in architectures such as x86-those branches are not checked by the software CFI. We propose branch regulation (BR), a lightweight hardware-supported protection mechanism against the CRAs that addresses all limitations of software CFI. BR enforces simple control flow rules in hardware at the function granularity to disallow arbitrary control flow transfers from one function into the middle of another function. This prevents common classes of CRAs without the complexity and run-time overhead of full CFI enforcement. BR incurs a slowdown of about 2% and increases the code footprint by less than 1% on the average for the SPEC 2006 benchmarks.

Dynamic information flow tracking (DIFT) is a powerful technique that can protect unmodified binaries from a broad range of vulnerabilities including buffer overflow and format string attacks. Software DIFT implementations suffer from very high performance overheads, while comprehensive hardware implementations add substantial complexity to the microarchitecture, making it unlikely for chip manufacturers to adopt them. In this paper, we propose SIFT (SMT-based DIFT), where a separate thread performing taint propagation and policy checking is executed in a spare context of an SMT processor. The instructions for the checking thread are generated in hardware using self-contained off-the-critical path logic at the commit stage of the pipeline. We investigate several performance optimizations to the base design including: 1) Prefetching of the taint data from shadow memory when the corresponding data is accessed by the primary thread; 2) Optimizing the generation of the taint code to remove unneeded security instructions; and 3) The use of aggregated instructions for collapsing the frequently used groups of security instructions into a single new instruction. Together, these optimizations reduce the performance penalty of SIFT to under 20 percent on SPEC CPU 2006 benchmarks-much lower than the overhead of previously proposed software-based DIFT schemes. We also analyze the energy overhead of SIFT and show it to be very high - 113 percent for SPEC 2006 benchmarks. We then propose several techniques that reduce this overhead to only 23 percent, making SIFT design practical from the energy standpoint. To demonstrate the feasibility of SIFT, we design and synthesize a core with SIFT logic and show that the area overhead of SIFT is only 4.5 percent and that instruction generation can be performed in one additional cycle at commit time.

Carrier Sense Multiple Access (CSMA) protocols are unable to effectively arbitrate the medium in wireless networks; problems such as hidden and exposed terminals occur frequently leading to collisions, poor performance and unfairness. CSMA networks can be optimized by careful tuning of transceiver parameters, such as transmission power and carrier sensing threshold, to maximize spatial reuse of wireless channel while minimizing collisions. However, existing studies fail to jointly optimize these parameters to eliminate collisions and maximize spatial reuse. Our approach leverages on the observation that links under CSMA interfere in one of the few discrete interaction modes; each mode leads to different behavior in terms of performance and fairness. The proposed methodology controls the transceiver parameters to convert destructive interaction modes (such as various types of hidden terminals) into constructive ones; we call this approach Interaction Engineering (IE). In this paper, we first formulate a model and centralized algorithm that computes the parameters based on one-to-one interaction between the links. We then develop a distributed IE protocol. We evaluate the protocols under Wireless LAN and multi-hop wireless networks using both simulation and testbed. We show that IE eliminates a vast majority of the collisions and significantly boosts spatial reuse. For example, in the WLAN scenarios, we observed a median improvement of 4x in throughput and more than 2.5x improvement in fairness, and orders of magnitude improvement in connection delay and jitter. IE also shows significant improvements in multi-hop networks, and under different forms of traffic such as video and TCP.

Parallel Discrete Event Simulation (PDES) can substantially improve the performance and capacity of simulation, allowing the study of larger, more detailed models, in less time. PDES is a fine-grained parallel application whose performance and scalability is limited by communication latencies. Traditionally, PDES simulation kernels use message passing; often these simulators are written for distributed environments, and shared memory is used to optimize message passing among processes on the same machine. In this paper, we develop, characterize and optimize a thread-based version of a PDES simulator on three representative multi-core platforms. The multi-threaded implementation eliminates multiple message copying and significantly minimizes synchronization delays. We study the performance of the simulator on three hardware platforms: an Intel Core i7 machine, and a 48-core AMD Opteron Magny-Cours system, and a 64-core Tilera TilePro64. We discover that the three platforms encounter substantially different bottlenecks because of their different architectures. We identify these bottlenecks and propose mechanisms to overcome them. Our results show that multi-threaded implementation improves the performance over an MPI-based version by up to a factor of 3 on the Core i7, 1.4 on the AMD Magny-Cours, and 2.8 on the Tilera Tile64.

Code Reuse Attacks (CRAs) recently emerged as a new class of security exploits. CRAs construct malicious programs out of small fragments (gadgets) of existing code, thus eliminating the need for code injection. Existing defenses against CRAs often incur large performance overheads or require extensive binary rewriting and other changes to the system software. In this paper, we examine a signature-based detection of CRAs, where the attack is detected by observing the behavior of programs and detecting the gadget execution patterns. We first demonstrate that naive signature-based defenses can be defeated by introducing special “delay gadgets” as part of the attack. We then show how a software-configurable signature-based approach can be designed to defend against such stealth CRAs, including the attacks that manage to use longer-length gadgets. The proposed defense (called SCRAP) can be implemented entirely in hardware using simple logic at the commit stage of the pipeline. SCRAP is realized with minimal performance cost, no changes to the software layers and no implications on binary compatibility. Finally, we show that SCRAP generates no false alarms on a wide range of applications.

The accuracy of wireless network packet simulation critically depends on the quality of the wireless channel models. These models directly affect the fundamental network characteristics, such as link quality, transmission range, and capture effect, as well as their dynamic variation in time and space. Path loss is the stationary component of the channel model affected by the shadowing in the environment. Existing path loss models are inaccurate, require very high measurement or computational overhead, and/or often cannot be made to represent a given environment. The paper contributes a flexible path loss model that uses a novel approach for spatially coherent interpolation from available nearby channels to allow accurate and efficient modeling of path loss. We show that the proposed model, called Double Regression (DR), generates a correlated space, allowing both the sender and the receiver to move without abrupt change in path loss. Combining DR with a traditional temporal fading model, such as Rayleigh fading, provides an accurate and efficient channel model that we integrate with the NS-2 simulator. We use measurements to validate the accuracy of the model for a number of scenarios. We also show that there is substantial impact on simulation behavior (e.g., up to 600% difference in throughput for simple scenarios) when path loss is modeled accurately.

Parallel Discrete Event Simulation (PDES) harnesses the power of parallel processing to improve the performance and capacity of simulation, supporting bigger models, in more details and for more scenarios. PDES engines are typically designed and evaluated assuming a homogeneous parallel computing system that is dedicated to the simulation application. In this paper, we first show that the presence of interference from other users, even a single process in an arbitrarily large parallel environment, can lead to dramatic slowdown in the performance of the simulation. We define a new metric, which we call proportional slowdown, that represents the idealized target for graceful slowdown in the presence of interference. We identify some of the reasons why simulators fall far short of proportional slowdown. Based on these observations, we design alternative simulation scheduling and mapping algorithms that are better able to tolerate interference. More precisely, the most resilient simulators will allow dynamic mapping of simulation event execution to processing resources (a work pool model). However, this model has significant overhead and can substantially impact locality. Thus, we propose a locality-aware adaptive dynamic-mapping (LADM) algorithm for PDES on multi-core systems. LADM reduces the number of active threads in the presence of interference, avoiding having threads disabled due to context switching. We show that LADM can substantially reduce the impact of interference while maintaining memory locality reducing the gap with proportional slowdown. LADM and similar techniques can also help in situations where there is load imbalance or processor heterogeneity.

The performance and scalability of Parallel Discrete Event Simulation (PDES) is often limited by communication latencies and overheads. The emergence of multi-core processors and their expected evolution into many-cores offers the promise of low latency communication and tight memory integration between cores; these properties should significantly improve the performance of PDES in such environments. However, on clusters of multi-cores (CMs), the latency and processing overheads incurred when communicating between different machines (nodes) far outweigh those between cores on the same chip, especially when commodity networking fabrics and communication software are used. It is unclear if there is any benefit to the low latency among cores on the same node given that communication links across nodes are significantly worse. In this study, we examine the performance of a multi-threaded implementation of PDES on CMs. We demonstrate that the inter-node communication costs impose a substantial bottleneck on PDES and demonstrate that without optimizations addressing these long latencies, multi-threaded PDES does not significantly outperform the multiprocess version despite direct communication through shared memory on the individual nodes. We then propose three optimizations: message consolidation and routing, infrequent polling and latency-sensitive model partitioning. We show that with these optimizations in place, threaded implementation of PDES significantly outperforms process-based implementation even on CMs.

Visual sensor networks (VSNs) are becoming increasingly popular in a number of application domains. A distinguishing characteristic of VSNs is to self-configure to minimize the need for operator control and to improve scalability. One of the areas of self-configuration is camera coverage control that is, how should cameras adjust their field-of-views to cover maximum targets? This is an NP-hard problem. We show that the existing heuristics have a number of weaknesses that influence both coverage and overhead. Therefore, we first propose a computationally efficient centralized heuristic that provides near-optimal coverage for small-scale networks. However, it requires significant communication and computation overhead, making it unsuitable for large-scale networks. Thus, we develop a distributed algorithm that outperforms the existing distributed algorithm with lower communication overhead, at the cost of coverage accuracy. We show that the proposed heuristics guarantee to cover at least half of the targets covered by the optimal solution. Finally, to gain benefits of both centralized and distributed algorithms, we propose a hierarchical algorithm where cameras are decomposed into neighborhoods that coordinate their coverage using an elected local coordinator. We observe that the hierarchical algorithm provides scalable near-optimal coverage with networking cost significantly less than that of centralized and distributed solutions.

Parallel Discrete Event Simulation (PDES) can substantially improve performance and capacity of simulation, allowing the study of larger, more detailed models, in shorter times. PDES is a fine-grained parallel application whose performance and scalability are limited by communication latencies. Traditionally, PDES simulation kernels use processes that communicate using message passing, shared memory is used to optimize message passing for processes running on the same machine. We report on our experiences in implementing a thread-based version of the ROSS simulator. The multithreaded implementation eliminates multiple message copying and significantly minimizes synchronization delays. We study the performance of the simulator on two hardware platforms: a Core i7 machine and a 48-core AMD Opteron Magny-Cours system. We identify performance bottlenecks and propose and evaluate mechanisms to overcome them. Results show that multithreaded implementation improves performance over the MPI version by up to a factor of 3 for the Core i7 machine and 1.2 on Magny-cours for 48-way simulation.

Code reuse attacks (CRAs) are recent security exploits that allow attackers to execute arbitrary code on a compromised machine. CRAs, exemplified by return-oriented and jump-oriented programming approaches, reuse fragments of the library code, thus avoiding the need for explicit injection of attack code on the stack. Since the executed code is reused existing code, CRAs bypass current hardware and software security measures that prevent execution from data or stack regions of memory. While software-based full control flow integrity (CFI) checking can protect against CRAs, it includes significant overhead, involves non-trivial effort of constructing a control flow graph, relies on proprietary tools and has potential vulnerabilities due to the presence of unintended branch instructions in architectures such as ×86 - those branches are not checked by the software CFI. We propose branch regulation (BR), a lightweight hardware-supported protection mechanism against the CRAs that addresses all limitations of software CFI. BR enforces simple control flow rules in hardware at the function granularity to disallow arbitrary control flow transfers from one function into the middle of another function. This prevents common classes of CRAs without the complexity and run-time overhead of full CFI enforcement. BR incurs a slowdown of about 2% and increases the code footprint by less than 1% on the average for the SPEC 2006 benchmarks.

Visual sensor networks (VSNs) are becoming increasingly popular in a number of application domains. A critical ability of such networks is to self-configure to minimize the need for operator control, improve scalability, and reduce cost. One of the areas of self-configuration is camera coverage control: how cameras adjust their field-of-view to allow automatic tracking of maximum number of targets. The problem is shown to be NP-hard for stationary targets, and efficient centralized, distributed and semi-centralized heuristics exist that perform close to optimal. For stationary targets camera configuration is a one-time activity and can happen offline and before the actual deployment. In contrast, if the targets are mobile, as the targets move away from their recorded positions, the cameras need to configure dynamically and in real-time to ensure coverage accuracy. In this paper, we propose several policies for automatic control of the cameras with a goal of coverage maximization for mobile targets. We study these policies using important performance metrics such as coverage gain, adaptability, scalability, and energy consumption. Our results indicate that factors such as target mobility models, target and camera scales/densities, and target velocities have significant impact on the performance of a given policy. For most of the scenarios, we found that the protocols that take into account non-local information (e.g. neighborhood information) and have self-adapting parameters (e.g. frequency of camera configurations) outperform the protocols that are either purely local or purely global and have non-adaptive parameters.

In CSMA networks, there is significant overhead associated with packet transmission, including header and contention overhead. For applications where packets are small, such as Voice over IP (VoIP), these overheads mean that a majority of the transmission time is wasted. Packet aggregation is a technique to amortize the per-transmission overhead over multiple aggregated packets. However, existing heuristics are limited, often not considering multi-rate wireless MAC, or operation in a Wireless LAN (WLAN) environment. In this paper we formulate the problem of optimal aggregation for a multi-rate CSMA MAC protocol and show that it is NP-hard. We then propose two heuristics that solve the aggregation problem for multi-rate WLANs. The first, which we call Data Rate based Aggregation protocol (DRA), divides packets in the MAC queue into groups based on their data rate. DRA then aggregates packets in the same group and broadcasts the aggregated frame at the data rate of that group. DRA substantially increases throughput compared to state of the art aggregation protocols; in certain cases achieving up to a 200% increase in the number of VoIP calls supported by a single 802.11g AP. The second heuristic, which we call Data Rate based Aggregation with Selective Demotion (DRA-SD), enables cross data rate aggregation. Through preliminary evaluation, we show that selectively demoting packets can further improve performance.

We propose a flexibly-partitioned cache design that either drastically weakens or completely eliminates cache-based side channel attacks. The proposed Non-Monopolizable (NoMo) cache dynamically reserves cache lines for active threads and prevents other co-executing threads from evicting reserved lines. Unreserved lines remain available for dynamic sharing among threads. NoMo requires only simple modifications to the cache replacement logic, making it straightforward to adopt. It requires no software support enabling it to automatically protect pre-existing binaries. NoMo results in performance degradation of about 1% on average. We demonstrate that NoMo can provide strong security guarantees for the AES and Blowfish encryption algorithms.

This paper presents a simulation toolset for estimating the impact of Trusted Platform Modules (TPMs) on the performance of applications that use TPM services, especially in multi-core environments. The proposed toolset, consisting of an integrated CPU/TPM simulator and a set of micro-benchmarks that exercise the major TPM services, can be used to analyze and optimize the performance of TPM-based systems and the TPM itself. In this paper, we consider two such optimizations: (1) exploiting multiple TPMs; and (2) reordering requests within the software stack to minimize queueing delays. Our studies indicate that both techniques result in significant performance improvement, especially as the number of concurrent applications using the TPM increases.

In the last decade or so, the ACM, the IEEE and other organizations have acknowledged that there is a problem with the way communication is taught in the Computer Science curriculum: the writing, speaking, and presentation skills students learn in the classroom do not match what is expected of them in the workplace. The proposed solution, adopted by many undergraduate colleges, was to add a technical communication course to the CS curriculum. This does not appear to be enough, as mainstream accreditation boards are still emphasizing the need for improvement of communication skills instruction in their recent reports and recommendations. For the last two years, we have experimented with a complementary transversal approach where many "traditional CS" courses in our program have added a communication component to their syllabus, while at the same time our technical communication course has been revamped to expose students to realistic practices as promoted by situated learning theory. The results, so far anecdotal, point to improved student performance and attitude across several communication dimensions, in particular writing and presentation. We plan to develop this experiment by spreading it across more classes and by starting to collect rigorous measurements of students' communication performance.

Trends in VLSI and micro architecture design have ushered in the multi-core era, where the number of cores on a chip is expected to grow with every processor generation. Soon, each chip will have a large number of tightly integrated processing cores with communication latencies substantially lower than those present in conventional clusters. Clusters made of such microprocessors experience non-uniform latencies between cores: cores on the same chip can communicate faster than cores on different chips, cores on the same machine can communicate faster than cores on different machines. In this paper, we characterize the performance of PDES models on a cluster of dual quad-core machines using a parameterizable modified version of Phold, a standard benchmark for parallel simulation. We study various combinations of regional and remote communication patterns to quantify the impact of communication on overall performance of simulation. We discover that the amount of communication has determining impact and it's essential to optimize this communication at each level to take maximum advantage of multi-core platform. We show that partitioning significantly improves performance. We also explore the impact of load imbalance on application performance and provide critical insight into how to partition for these different environments. We believe that this study represents a significant first step in characterizing the performance space for PDES on this emerging platform.

The ISM frequency bands (902~918 MHz (region 2 only), 2.4 GHz ~ 2.483 GHz, and 5.725~5.875 GHz) are unlicensed bands available for use by commercial technologies. In particular, the 2.4 GHz ~ 2.483 GHz band is very popular and is currently used by WiFi, Zigbee, Bluetooth, and RFID technologies. Moreover, microwave ovens, hand held phones, and other wireless devices operate in the same frequency range, often interfering with each other. The effects of the coexistence of different standards are complicated and significant. However, network simulators do not model the effect of interference from co-located devices using different technologies. In particular, they model external noise, including interference from technologies outside the primary network being simulated, as a flat Gaussian component. In this paper, we propose a methodology of modeling external interference, by considering the realistic characteristics interference generated by co-located wireless standards. The traditional view that noise is flat in space and time, is inaccurate when one considers interference from co-located technologies. The noise signals are generated from their sources, attenuate over distance and experience fading. In addition, external interference exists only when its sources are active. Based on these characteristics, we propose a realistic and configurable noise model that captures such behavior. We demonstrate that this model can be well-fitted to real noise data. Moreover, we also demonstrate the impact of the model on the performance of network protocols as estimated by simulation.

Carrier Sense Multiple Access (CSMA) protocols are unable to effectively arbitrate the medium in multi-hop wireless networks; problems such as hidden and exposed terminals occur frequently leading to collisions, poor performance and unfairness. CSMA networks can be optimized by careful tuning of transceiver parameters, such as transmission power and carrier sensing threshold, to maximize transmission concurrency while minimizing collisions. Existing approaches optimize these parameters by considering only some aspects of CSMA operation (e.g., considering only PHY parameters such as SINR), thus leading to suboptimal solutions. We present a new approach that leverages recent insights into the behavior of CSMA networks. Specifically, this recent work identifies that links interfere only in a few discrete interaction modes at the MAC-layer. Each interaction mode determines how the interacting links interfere with each other and leads to different performance and fairness behavior. The proposed methodology controls the transciever parameters to convert the destructive interactions into constructive ones; we call this approach Interaction Engineering. The global optimization problem is computationally infeasible and requires central solution. Therefore, we first formulate an interaction engineering model that computes the parameters based on one-to-one interaction between the links. Second, we extend the model into a distributed interaction-aware MAC protocol (I-MAC). Testbed and simulation results show that collisions and retransmissions are almost completely eliminated, leading to large improvements in throughput and delay.

Carrier Sense Multiple Access (CSMA) based MAC protocols induce several types of harmful interactions, such as hidden and exposed terminals, in wireless networks. Existing routing protocols do not consider the effect of these MAC interactions on route quality, leading to the selection of inefficient routes. We propose a MAC Interaction Aware Routing Metric (MIAR) that explicitly accounts for MAC interactions among the links forming a route. The protocol favors routes with links that have better interactions and avoids ones with detrimental interactions. We compare the performance of the proposed metric with an existing shortest-path routing protocol and show that our metric substantially improves the performance and efficiency of the network.

Network flow models serve as a popular mathematical framework for the analysis and optimization of multi-hop wireless networks. They also serve to provide the understanding necessary to derive effective distributed protocols. However, the high computational complexity of realistic models restrict the translation of theoretical insights into distributed protocols. In this paper, we consider an NP-hard, mixed integer linear programming based routing model that computes single-path routes in a wireless network. We propose an efficient, polynomial time algorithm that applies domain specific heuristics to reduce the complexity. We employ a decomposition based approach to break the monolithic problem into several sub-problems that cooperate to find near-optimal routes. The sub-problem structure is chosen such that it captures the optimal route discovery process between a source and destination; this is a design principle that can be directly used in distributed routing protocols. We show that the resulting formulation achieves orders of magnitude improvement in the run-time. Simulation results show that the routes derived from the model are effective even in practical wireless networks with commonly used protocol stack.

In multi-hop wireless networks with Carrier Sense Multiple Access (CSMA), unfairness may arise due to a number of reasons. A majority of the existing work focuses on fairness issues due to hidden terminals and the impact on backoff mechanisms. This paper focuses on the unfairness arising due to unequal contention opportunities at a node; some nodes rarely observe an idle channel since two or more interferers that are not in range with each other can transmit together. Contention unfairness is unrelated to hidden terminals. In order to understand the impact of contention and gain insight into developing solutions for contention unfairness, we develop a model from first principles for contention in IEEE 802.11 networks. The accuracy of the model is validated through simulations and the results show that such unfairness is a common phenomenon. Based on the insights gained from the model, we propose and evaluate a distributed scheme that reduces the effect of unfairness due to contention. Simulation results show that the proposed scheme achieves an average improvement of 25% in fairness, with a small reduction in overall throughput.

In a Multi-hop Wireless Networks (MHWN), packets are routed between source and destination using a chain of intermediate nodes; chains are a fundamental communication structure in MHWNs whose behavior must be understood to enable building effective protocols. The behavior of chains is determined by a number of complex and interdependent processes that arise as the sources of different chain hops compete to transmit their packets on the shared medium. In this paper, we show that MAC level interactions play the primary role in determining the behavior of chains. We evaluate the types of chains that occur based on the MAC interactions between different links using realistic propagation and packet forwarding models. We discover that the presence of destructive interactions, due to different forms of hidden terminals, does not impact the throughput of an isolated chain significantly. However, due to the increased number of retransmissions required, the amount of band-width consumed is significantly higher in chains exhibiting destructive interactions, substantially influencing the over-all network performance. These results are validated by testbed experiments. We finally study how different types of chains interfere with each other and discover that well behaved chains in terms of self-interference are more resilient to interference from other chains.

The proliferation of wireless-enabled portable computing devices has spurred a growing need for efficient and powerful networking protocols. The key challenge in the development of robust wireless networking protocols is an ability to conduct effective and efficient evaluation of the protocol in order to ensure its successful working in real-world settings. We proposed MiNT-2, a fresh re-design of the original MiNT framework developed at Stony Brook University. One of the fundamental requirements of MiNT-2 is to provide location awareness of all the nodes within the network. In this paper, we demonstrate the use of radio-frequency identification (RFID) technology in order to carry out localization of the mobile nodes within the system. We also demonstrate the application of the localization system of constructing different scenarios for wireless protocols evaluation.

Wireless channels exhibit complex signal strength fluctuation over time due to signal propagation effects interacting with a dynamic environment. For accurate simulation of wireless networking protocols, it is important to model wireless channels accurately; without accurate models, simulation results have been shown to be significantly different from measured results. Accurate statistical models of the state of a particular channel can be constructed based on obtained experimental measurements. However, this approach cannot be easily exploited for dynamic simulations (e.g., those with mobility), because it is impossible to pre-measure all of the possible channels that arise during the simulation; for example, in a mobile ad hoc network the nodes move and a very large number of channels is encountered in the lifetime of the simulation. In this paper, we propose the use of interpolation between measured channels to produce models for other channels that have not been measured, significantly increasing the flexibility of this approach. Instead of obtaining measurement traces for every link, our method estimates the essential parameters for a new link by interpolation from nearby measured links. Thus, the flexibility of measurement based models is increased dramatically, providing a modeling approach that is both accurate and flexible. We validate the approach using representative experiments.

Chains or multi-hop paths are the fundamental communication structure in multi-hop wireless networks. Understanding chain behavior is critical in order to build effective higher layer protocols. This paper examines the problem of how MAC level interactions influence chain behavior in a general multi-hop wireless network where multiple chains coexist. We first classify chains based on the MAC interactions observed between its hops when there is no external traffic. Then we identify the interactions across two interfering chains for the most common categories of chains. We study the probability of occurrence, and estimate the effect of MAC interactions on the performance of the chains. We also show that different chains exhibit different transmission patterns; this is an effect that is necessary for accurately estimating chain performance. We observe that destructive interactions arise more frequently among two interfering chains than they do within a single chain. Moreover, chains that have hidden terminals due to self-interference are more prone to have cross-chain hidden terminals. Thus, both intra-chain as well as cross-chain interactions, ultimately provide significant insight into how chains interact.

In timing analysis attackers study the transmission pattern of different nodes in a network with the goal of extracting information about users, applications, or the structure of the network, even when the traffic is encrypted. Defeating timing analysis attacks requires expensive traffic mixing measures that equalize the transmission pattern at all nodes; such measures are especially expensive for battery operated wireless devices. In this paper, we first introduce TARP, a traffic mixing approach for defeating timing analysis tailored towards sensor networks. While TARP improves on traffic mixing approaches by combining multiple packets destined to different destinations in a single frame (amortizing packet overhead), traffic mixing remains expensive. To this end, we propose two techniques for improving the energy efficiency of TARP: (1) Using multi-path routing to exploit the available capacity engineered to defeat timing analysis; and (2) Adaptive transmission control to allow the transmission pattern to be adapted to the offered load without exposing the structure of the network. Furthermore, we define and explore the notion of relaxed timing analysis resilience where resilience is provided with a limited scope that is well defined in space and/or time. By controlling the scope to fit the application requirements, substantial savings in energy (or delay) can be achieved, while retaining desired levels of timing analysis resilience. Together, the proposed techniques significantly reduce the overhead of TARP, making timing analysis resilience more affordable for critical applications.

Carrier Sense Multiple Access (CSMA) protocols in Multi-hop Wireless Networks (MHWN) are known to suffer from different forms of hidden and exposed terminal problems, leading to inefficiency and unfairness. Recent studies have formally characterized the fundamental interactions in the IEEE 802.11 protocol by classifying and quantifying the possible interactions that arise between two interfering single hop links. However, existing studies use a simple disc based propagation model, which does not model the effect of interference accurately in the presence of capture. This paper advances this line of study by developing the analysis and performance models for the two-flow interference problem using a Signal-to-Interference-Noise (SINR) based propagation model with large scale fading. This model has been experimentally shown to accurately predict the performance in wireless testbeds. The analysis identifies four previously unknown categories of interactions, and affects the probability of occurrence of the other categories. Moreover, using a SINR model allows us for the first time to characterize the incidence of the exposed terminal problem. The paper proposes closed form expressions to estimate the probability of occurrence of each category. We then propose throughput estimation models for the frequently occurring new categories and validate them against simulation. We believe that collectively these contributions provide a substantial improvement in our understanding of the effect of interference from first principles, which is a vital step in developing protocols that account for it.

Geographic routing can provide efficient routing at a fixed overhead. However, the performance of geographic routing is impacted by physical voids, and localization errors. Accordingly, virtual coordinate systems (VCS) were proposed as an alternative approach that is resilient to localization errors and that naturally routes around physical voids. However, VCS also faces virtual anomalies. Moreover, there are no effective complementary routing algorithm that can be used to traverse voids. Most existing solutions use variants of flooding or blind searching when a void is encountered. In this paper, we make the observation that increasing the number of dimensions in virtual coordinate systems cannot eliminate all virtual anomalies since some portions of the network may be 1-connected to the rest of the network. As a result, we conjecture that a delivery guaranteed protocol must be one-dimensional and propose a spanning-path virtual coordinate system that has this property. We develop a delivery guaranteed routing algorithm on top of this system that can be used on its own, or as a complementary algorithm to traverse voids. With this approach, and for the first time, we demonstrate a stateless and delivery guaranteed geometric routing algorithm on VCS. When used in conjunction with our previously proposed aligned virtual coordinate system (AVCS), it out-performs not only all geometric routing protocols on VCS, but also geographic routing with accurate location information.

Network flow models have proven to be an effective tool in the analysis, optimization and design of network protocols. Critical to the success of these models in general multi-hop wireless networks (MHWNs) is an accurate estimation of the effect of CSMA scheduling. While the existing models capture coarse grained estimates of interference, they do not account for the substantial impact of MAC scheduling. On the other hand, accurate models of throughput in CSMA networks exist. However, they are unsuitable for use as a part of a network flow formulation because of their complexity and some of their underlying assumptions. This paper contributes an efficient and constructive model to estimate the effect of scheduling on interfering links in general MHWN settings. We integrate this approach with a network flow routing model which works with aggregate estimates of capacity to improve the quality of the solution. Simulation results show that accounting for scheduling effects leads to large improvements in the quality of the solution.

Abstract Wireless sensor networks (WSNs) have recently attracted a lot of interest due to the wide range of applications they enable. Unfortunately, WSNs are exposed to numerous security threats that can adversely affect the success of important applications. Securing WSNs is challenging due to their limited capabilities and the unique nature of the network and applications. In this paper, we argue that the WSN security research generally considers mechanisms that are modeled after and evaluated against abstract applications and WSN organizations. Instead, we propose that the solution for WSN security must be sensitive to the application and infrastructure. Specifically, we formulate a new notion of an application‐specific security context as the combination of a potential attacker's motivation and the WSN vulnerability. The vulnerability is a function of factors such as the sensor field, WSN infrastructure, application, protocols, system software, accessibility, and the observability of the WSN. To reduce the vulnerability, we argue that WSN design must balance security with traditional objectives such as the cost, energy efficiency, and application level performance to a degree proportional to the attacker's motivation. We illustrate this argumentviafour example applications. Overall, our work can be considered a basis to derive more grounded and realistic assumptions for WSN security and develop cost‐effective security solutions to handle application‐specific vulnerabilities in WSNs. Copyright © 2007 John Wiley & Sons, Ltd.

We formulate the real-time routing problem in static multi-hop wireless networks as an optimization problem, whose solution is the optimal routes relative to an end- to-end delay based objective. The problem is formulated as a mixed integer linear program. The variance of the delay with respect to the aggregate interference measures is empirically studied and a linear approximation is proposed. We show that this formulation yields routes that significantly outperform the best routes obtained by OLSR. Finally, we discuss the applications of such a model both in terms of capacity analysis, on-line algorithms for static scenarios, and extensions to allow the development of distributed protocols that solve the optimization problem.

Resource scheduling in large-scale, volatile desktop grids is challenging because resource state is both dynamic and eclectic. Matching available resources with requests is not always possible with existing approaches. Partial dissemination protocols, such as gossiping, may provide efficient schedules when resource requesters are located near providers that can meet their needs. However, when requesters are distant from available resources, regular information dissemination techniques can waste communication bandwidth with futile messages. Thus, it may be advantageous to attempt to advertise to select remote regions of the grid, without necessarily also going through all intermediate nodes. This paper proposes dissemination proxies to increase coverage footprints and reduce dissemination overhead. We incorporate selecting and adjusting the amount of proxy nodes into an adaptive dissemination algorithm, and show that dissemination proxies are able to reduce dissemination overhead, and handle available resource distribution scenarios where regular information dissemination approaches may not produce efficient protocols. We also report initial results that indicate that randomly selecting nodes to serve as proxies can perform as well as strategies that select seemingly better-qualified proxies.

Making effective use of computational grids requires scheduling grid applications onto resources that best match them. Resource-related state (e.g., load, availability, and location), and demand-related state (number and distribution of application resource requests) influences scheduling decision success. The scale of the grid makes collecting and maintaining detailed up-to-date state information for all resources and requests impractical. Thus, concurrent distributed schedulers must make scheduling decisions based on incomplete resource state information. In this paper, we evaluate the effect that the criteria for selecting scheduling matches have on the success of scheduling decisions. We focus on three criteria: information freshness, resource distance from requesters, and past behavior. We evaluate the quality of the schedule for various resource monitoring models, grid load models, and grid overlay topologies. Among our findings is the counter-intuitive result that favoring freshness can sometimes harm overall system performance; a combination of resource distance and past scheduling success performs best. We also evaluate a pure resource state pull model with caching, and discover that pro-actively pushing dynamic state information to schedulers is beneficial.

Computational grids have not scaled effectively due to administrative hurdles to resource and user participation. Most production grids are essentially multi-site supercomputer centers, rather than truly open and heterogeneous sets of resources that can join and leave dynamically, and that can provide support for an equally dynamic set of users. Large-scale grids containing individual resources with more autonomy about when and how they join and leave will require self-organizing grid middleware services that do not require centralized administrative control. This paper considers one such service, namely the dynamic discovery of high-performance variable-size clusters of grid nodes. A brute force approach to the problem of identifying these "ad-hoc clusters" would require excessive overhead in terms of both message exchange and computation. Therefore, we propose a scalable solution that uses a delay-based overlay structure to organize nodes based on their proximity to one another, using a small number of delay experiments. This overlay can then be used to provide a variable-size set of promising candidate nodes than can then be used as a cluster, or tested further to improve the selection. Simulation results show that this approach results in effective clustering with acceptable overhead

In optimistically synchronized parallel discrete event simulators, unlimited optimism can lead to excessive rollbacks and simulation thrashing. Artificially throttling the simulation is a well-known technique for improving the performance by avoiding the effects of uncontrolled optimism. Simulation throttling has been attempted based on time or event count beyond global virtual time (GVT). In this paper, we carry out a simulation study of both approaches within time warp as well as breathing time warp (BTW) synchronization algorithms in the context of the SPEEDES simulation framework. We discover that anomalies arise when limiting optimism based on event count (as is the case in the default SPEEDES BTW algorithm) and that this gives rise to forced rollbacks that generally do not arise without simulation throttling. We implement a version of BTW that limits optimism based on time beyond GVT and show that it outperforms BTW for two large scale applications. We discuss initial experiences with adaptively estimating the optimism limit

Effective scheduling in large-scale computational grids is challenging because it requires tracking the dynamic state of the large number of distributed resources that comprise the grid. Classical distributed information dissemination approaches such as push, pull, and their combinations, are not well suited to the problem of resource tracking, where resources are redundant and full information about all resources everywhere is neither necessary nor desirable. Aggregated, partial, or probabilistic forwarding protocols result in more efficient (but incomplete) dissemination, while maintaining sufficient information to enable effective scheduling. However, a static approach to dissemination in which all information is treated identically, is ineffective in the presence of spatial and temporal non-uniformity of resources and demands. For example, a single forwarding probability for gossipping-based dissemination may result in unnecessarily high overhead in some areas of the grid. Moreover, the right forwarding probability values can change over time, with changes in offered load and node utilization. Adaptive protocols can adjust the aggressiveness with which information is disseminated, based on current grid conditions, and can in turn increase query satisfaction rates, reduce overhead, or both. This paper explores the characteristics and behavior of adaptive probabilistic and change-sensitive information forwarding protocols, identifying and addressing several issues and problems, and introducing dissemination protocols that are better able to reduce overhead and increase query satisfaction rates for a variety of grid conditions.

The potential of truly large scale grids can only be realized with grid architectures and deployment strategies that lower the need for human administrative intervention, and therefore open the grid to wider participation from resources and users. Self-organizing grids (SOGs) are characterized by services, protocols, and deployment strategies that promote true scalability by eliminating administrative bottlenecks. We describe four enabling mechanisms for SOGs - automatically inferring grid structure, tracking and making available dynamic resource state information, unifying the grid service deployment model, and making effective use of intermittently connected grid hosts via lightweight fault tolerance mechanisms that take advantage of the resource fault characteristics

Geographic routing protocols achieve relatively good performance, and provide several advantages over conventional protocols for multi-hop wireless networks. However, such protocols are impacted by physical voids, and localization errors. Virtual coordinate systems (VCS) were proposed as an alternative approach that is resilient to localization errors and that naturally routes around physical voids. In this paper, we show that VCS is vulnerable to different forms of the void problem and, in general, perform worse than geographic routing in the greedy phase. We show that these anomalies arise from quantization noise in the estimate of connectivity and node location due to the integral nature of VCS coordinates. We propose an aligned virtual coordinate system (AVCS) on which the greedy routing success can be significantly improved. With our approach, and for the first time, we show that greedy routing on VCS outperforms that on geographic coordinates even with no localization errors. We compare AVCS against some of the most popular geometric routing protocols both using physical and virtual coordinates and show that it significantly improves performance over these solutions

Routing in multi-hop wireless networks is typically greedy, with every connection attempting to establish a path that minimizes its number of hops. However, interference plays a major role in limiting the capacity of such networks; this effect is ignored by most existing protocols. It is likely that approaches that coordinate routing to account for mutual interference would be able to achieve better performance than traditional approaches. Modeling routing with interference constraints is a complex non-linear optimization problem. We approach the problem using a multi commodity flow (MCF) formulation. We analyze the interaction of multiple routes and propose effective objective functions which attempt to maximize interference separation while limiting path inflation. Initial experimental results show significant improvement in performance over a traditional routing protocol. We evaluate the formulation against routes obtained using DSR under several scenarios and show that better performance is achieved in terms of throughput, goodput, and end-to-end delay

Most existing real-time protocols for sensor data dissemination use packet scheduling schemes to prioritize packets according to their deadlines. However, packet prioritization by itself cannot completely support real-time data dissemination requirements. In this paper, we propose new just-in-time scheduling (JiTS) algorithms that take advantage of the available slack, if any, to reduce contentions and improve real-time performance by judiciously delaying packets as long as their deadlines are not missed. Specifically, we explore several policies for allocating the slack among multiple hops, including a non-linear policy where packets are non-uniformly delayed at intermediate nodes to account for expected higher contentions as packets get closer to the sink(s). Notably, our JiTS policies require neither lower layer support nor synchronization among sensor nodes making for an easy deployment. In our simulation study, JiTS significantly improves the deadline miss ratio and packet drop ratio compared to existing approaches in various situations. It is also shown that the geographic forwarding often used for real-time data dissemination substantially underperforms the shortest path routing especially when the load is high

Localization is a fundamental operation in mobile and self-configuring networks such as sensor networks and mobile ad hoc networks. For example, sensor location is often critical for data interpretation. Existing research focuses on localization mechanisms: algorithms and infrastructure designed to allow the sensors to determine their location. In a mobile environment, the underlying localization mechanism must be invoked repeatedly to maintain accurate location information. We propose and investigate adaptive and predictive protocols that control the frequency of localization based on sensor mobility behavior to reduce the energy requirements for localization while bounding the localization error. In addition, we evaluate the energy-accuracy tradeoffs. Our results indicate that the proposed protocols reduce the localization energy significantly without sacrificing accuracy.

Peer-to-Peer (P2P) systems have become popular over the past few years. However, their large scale and the open nature of the system makes studying them challenging. This paper presents an extensible framework for simulating P2P networks efficiently and accurately. Efficiency is accomplished by using message level simulation rather than packet level simulation. Moreover, accuracy is maintained by tracking the network infrastructure and using a flow model to accomplish accurate estimate of the message behavior. A second contribution of the paper is to model the BitTorrent (BT) protocol. BT is a widely-used protocol that is significantly more complex than other P2P protocols because file download occurs in chunks from many other peers concurrently. Thus, contrary to models of other P2P systems such as Gnutella or Freenet, which focus on finding the location of a file in the network, BT's complexity occurs in downloading files (locating files in fact occurs out of band using Websites that host the Torrent files). We validate the model against a packet level simulator and also using a real, but small scale, BitTorrent experiment. The simulator is object oriented and extensible for simulating other P2P protocols and applications.

Network-wide broadcast (NWB) is a common operation in mobile ad hoc networks (MANETs), which are used to discover routes in routing protocols and to disseminate information in group communication operations. NWB is commonly performed via flooding, which has been shown to be expensive in dense MANETs due to its high redundancy. Existing NWB algorithms target reducing the overhead of NWB operations. In this work, we target another problem that can substantially impact the success of NWBs: since MAC level broadcasts are unreliable, it is possible for critical rebroadcasts to be lost, leading to a significant drop in the node coverage. This is especially true under heavy load and in sparse topologies. We show that the techniques that target reducing the overhead of flooding reduce its inherent redundancy and harm its reliability

Grid information dissemination protocols distribute information about the dynamic state of computational resources throughout interconnected wide area grids. Performance metrics for these protocols include the overhead of information packets, and the accuracy of the information at the time it is used to schedule applications. Our previous work advocated non-uniform protocols to keep dissemination local to the information source, as a method of keeping overhead manageable while achieving adequate freshness and accuracy. This paper considers the problem of providing better control over the dissemination of information and influencing the "coverage footprint" that defines where the information reaches within the grid. The paper describes work that investigates the coverage characteristics of existing protocols and refines and combines them into hybrid protocols that are more controllable. We consider this work to be a necessary step toward adaptive dissemination protocols that would be able to react to the state of grid resources to change dynamically how and where information is disseminated. This in turn increases the effectiveness of grid schedulers under various load levels and distributions

Route discovery in reactive routing protocols for MANETs use flooding to disseminate route requests. Such operations rely on MAC level broadcasts to reach all nearby nodes without prior knowledge of their identity. For networks with directional antennas, this creates the following challenge: only neighbors in omni-directional range are discovered, leading to long paths and suboptimal operation. To address this problem sweeping directional MAC broadcasts are often used. Sweeping broadcasts have a high overhead; in addition, we observe that they can cause suboptimal route discovery, especially under high loads. To address these shortcomings, we propose a new directional route discovery approach called route compaction. Route compaction relies on enhanced version of omni-directional route discovery to find paths, avoiding the problems with sweeping broadcast. Route compaction then attempts to compact routes by replacing multiple hops with a single directional hop whenever possible. Our experiments show that this approach provides excellent directional route discovery capability at a lower overhead than sweeping broadcast.

Network wide broadcast (NWB) is a common and important operation in mobile ad hoc networks (MANETs). NWBs are used to propagate routing requests and/or state in routing protocols as well as application data in group communication protocols. NWB rely on MAC level broadcast which is unreliable. In the presence of shadowing or collisions, this leads to loss of coverage, especially in low density networks or for optimized NWB algorithms with limited redundancy. In this work, we propose a new MAC level primitive, directed broadcast, which significantly improves the reliability of link level broadcast. In particular, directed broadcast is especially suited for optimized NWB algorithms that build a virtual backbone because it allows full reliability for the messages as they cross the backbone. We show that using directed broadcast can significantly improve the reliability of NWB operation.

In mobile ad hoc networks (MANETs), protocol behavior is most commonly studied at a macro level: connections are examined to see how their throughput fares through the entire network. In some instances, this level of analysis cannot explain the observed behavior or provide insight necessary to predict behavior in other scenarios. As a result, general solutions to problems such as unfairness which are rooted in low level behavior fail to take into account the basic behavior that causes the problems. In this paper, we use a complimentary approach where we examine behavior at a much lower level, by studying the interactions among two single hop connections in all possible configurations in terms of the relationship between of the senders and receivers. We study these connections using the standard 802.11 MAC protocol, with and without the request to send and clear to send (RTS/CTS) control packets, as well as with a well-known fairness algorithm. We isolate configurations that cause unfairness and inefficient behavior. Understanding the root causes of these problems is a first step towards a more complete understanding of connection behavior in MANETs that will allow developing fair access algorithms that directly target the causes of the observed problems.

In existing directional MAC protocols a single queue is used at the MAC layer; this is inherited from omnidirectional implementations. However, while there is a single channel state in omnidirectional transmission (either the channel is busy or not), the state of the channel varies with the desired direction of transmission in directional antennas. Thus, existing implementations which use a single FIFO queue potentially lead to head of line blocking if the medium is busy in the direction of the packet at the top of the queue but is available in other directions. We propose a new queuing organization which could take advantage of the channel more effectively using the underlying antenna system by eliminating head of line blocking. We also identify a problem with the directional virtual carrier sense implementation due to side-lobes and provide a solution to it. Our results indicate that by using a greedy approach, to schedule the packet which has the least wait time, increases the overall throughput and reduces end-to-end delay considerably, especially under heavy loads.

Effective use of computational grids requires up-to-date information about widely-distributed resources within it - a challenging problem given the scale of the grid, and the continuously changing state of the resources. We propose nonuniform information dissemination protocols to efficiently propagate information to distributed repositories, without requiring flooding or centralized approaches. Capitalizing on the observation that grid resources are of more interest to nearby users, we disseminate resource information with a frequency and resolution inversely proportional to the distance from the resource. Results indicate a significant reduction in the overhead compared to uniform dissemination to all repositories.

In this paper we report experiences on a parallel implementation of a standard cell placement algorithm on a cluster of Myrinet connected PCs. The implementation is based on a recently developed placement tool (Feng Shui) that extends recursive bisection placement to incorporate global aspects of the design using an efficient optimization called iterative deletion. Contrary to previous attempts at parallelizing placement algorithms, initial experimental results show significant performance improvement with small reduction in the placement quality. Furthermore, the reduction in the placement quality does not increase with the number of processors. 1

In mobile ad hoc networks, the topology of the network is constantly changing as nodes move in and out of each other's range, breaking and establishing links. TCP performs poorly in such networks because packets that are lost due to path disconnections trigger TCP's congestion avoidance mechanisms. We investigate the effect of preemptive routing protocols, where an alternative path is found before an actual disconnection occurs, on the performance of TCP. Preemptive routing should perform well for TCP traffic because it reduces the delays caused by TCP's unnecessary use of congestion avoidance when paths break. We observe this behavior under some, but not all scenarios. Specifically, it appears that when the network is saturated, the additional traffic introduced by preemptive routing causes small degradation in performance. In the analysis process, we encountered an unfairness problem resulting from interaction between the routing protocol and the MAC layer under multiple continuous transmission cases. Similar unfairness problems were encountered by other studies-however the observations of those studies related those problems to the number of hops, and not the routing effects as we observed. This motivates the study of fairer wireless MAC protocols for multi-hop and ad hoc networks.

The integration of processing and DRAM offers a potential solution to the memory bottleneck problem. The bandwidth available within the chip is several orders of magnitude higher than that at the memory bus with a lower access time. As workloads shift towards data-intensive/multimedia applications, the wide bandwidth can be effectively utilized by harnessing the parallelism available in these applications. There are difficult challenges in developing architectures and programming models that expose the available bandwidth to the application. This paper presents the design of an intelligent memory based on a distributed data-parallel architecture with limited support for control parallelism. We investigate some of the relevant design issues and evaluate the success of such an architecture in supporting data-intensive applications. The design is evaluated as a stand-alone system, and also as a co-processor acting as a memory access filter. A cycle-accurate simulator is developed and used to study the performance of the architecture for data-intensive applications. The performance is compared against that of a modern superscalar processor.

The gap between the speed of logic and the DRAM memory access is widening. Traditional processors hide some of the mismatch in memory latency using techniques such as multi-level caches, instruction prefetching and memory interleaving. The bandwidth available at the system bus also forms a bottleneck; even an elaborate memory hierarchy with a perfect prefetching predictor generate memory traffic that overwhelms the capabilities of modern memory subsystems. A potential solution is the integration of DRAM and logic on the same die. Such solutions are motivated by the following: (i) the bandwidth available within the chip is many orders of magnitude higher than that at the memory bus at a significantly lower access time and with lower power dissipation; and (ii) as typical workloads shift towards data-intensive/multimedia applications, the wide bandwidth can be effectively utilized. However, there are significant challenges in developing architectures and programming models that expose the available bandwidth to end users. This paper presents the design of an intelligent memory based on a distributed data-parallel architecture with limited support for control parallelism (called PPIM). We investigate some of the relevant design issues and the success of such an architecture in supporting dataintensive applications. A cycle-accurate simulator is developed to study the architecture and performance for some data-intensive applications is compared against that of a modern superscalar processor (simulated using the simplescalar tool-set).

Existing on-demand ad-hoc routing algorithms initiate route discovery only after a path breaks, incurring a significant cost in detecting the disconnection and establishing a new route. In this work, we investigate adding proactive route selection and maintenance to on-demand ad-hoc routing algorithms. More specifically, when a path is likely to be broken, a warning is sent to the source indicating the likelihood of a disconnection. The source can then initiate path discovery early, potentially avoiding the disconnection altogether. A path is considered likely to break when the received packet power becomes close to the minimum detectable power (other approaches are possible). Care must be taken to avoid initiating false route warnings due to fluctuations in received power caused by fading, multipath effects and similar random transient phenomena. Experiments demonstrate that adding proactive route selection and maintenance to DSR and AODV (on-demand ad hoc routing protocols) significantly reduces the number of broken paths, with a small increase in protocol overhead. Packet latency and jitter also goes down in most cases. We also show some experimental results obtained by running TCP on top of the proactive routing schemes proposed. Several improvements and extensions are also discussed. Pro-active route selection and maintenance is general and can be used with other routing algorithms and optimizations to them.

In time warp simulations, the overheads associated with rollbacks, state-saving and the communication induced by rollbacks are the chief contributors to the cost of the simulation; thus, these aspects of the simulation have been primary targets for optimizations. Unfortunately, the behavior of the time warp simulation is highly dynamic and greatly influenced by the application being simulated. Thus, the suggested optimizations are only effective for certain intervals of the simulation. This paper argues that the performance of time warp simulators benefits from a dynamic on-line decision process that selects and configures the sub-algorithms implementing the different aspects of the simulator to best match the current behavior of the simulation. In particular we study control strategies to dynamically: (i) adjust the checkpointing (or state-saving) interval (ii) select the cancellation strategy (lazy or aggressive), and (iii) determine the policy for aggregating the application messages (an optimization that significantly improves the performance in message passing environments). The strategies have been implemented in the WARPED time warp simulation kernel and the performance obtained via the dynamically controlled optimizations is shown to surpass that of their best performing static counterparts.

Functional parallelism may be supported on SIMD machines by interpretation. The programs and data of each function are loaded on the processing elements (PEs), and the control unit of the machine executes a central control algorithm that causes the concurrent interpretation of these functions. The performance of this paradigm has been shown to benefit considerably from a variable instruction issue schedule that delays execution of expensive and rarely occurring operations. Two new features of the interpretation paradigm, namely pipelined SIMD machines and compositional instruction sets, change the nature of the mathematical model used for variable instruction scheduling significantly. In the paper, a previously developed mathematical model of the interpretation process is extended to allow for compositional instructions and pipelining. We develop and present algorithms that produce variable instruction schedules for the extended model and investigate whether the variable instruction issue is useful for these cases. We show that the variable instruction issue improves the performance of pipelined machines but is not very effective for compositional instruction sets, especially when the composition matrix is not sparse. © 1997 by John Wiley & Sons, Ltd.

Functional parallelism can be supported on SIMD machines by interpretation. Under such a scheme, the programs and data of each task are loaded on the processing elements (PEs) and the Control Unit of the machine executes a central control algorithm that causes the concurrent interpretation of the tasks on the PEs. The central control algorithm is, in many respects, analogous to the control store program on microprogrammed machines. Accordingly, the organization of the control algorithm greatly influences the performance of the synthesized MIMD environment. Most central control algorithms are constructed to interpret the execution phase of all instructions during every cycle (iteration). However, it is possible to delay the interpretation of infrequent and costly instructions to improve the overall performance. Interpreters that attempt improved performance by delaying the issue of infrequent instructions are referred to as variable issue control algorithms. This paper examines the construction of optimized variable issue control algorithms. In particular, a mathematical model for the interpretation process is built and two objective functions (instruction throughput and PE utilization) are defined. The problem of deriving variable issue control algorithms for these objective functions has been shown elsewhere to be NP-complete. Therefore, this paper investigates three heuristic algorithms for constructing near optimal variable issue control algorithms. The performance of the algorithms is studied on four different instruction sets and the trends of the schedulers with respect to the instruction sets and the objective functions are analyzed.