Modern programs comprise multiple threads of execution inside a single principal -- the process -- with a single protection domain, usually a page table. We propose a hardware enforced, fine-grained memory protection mechanism to divide the process into smaller principals and multiple protection domains. Our approach supports modern software engineering better than traditional processes by enabling developers to align software components with protection mechanisms. We implemented our architecture using a cycle-accurate simulator of a complex out-of-order pipeline and evaluate our solution using open-source benchmarks and synthetic micro benchmarks designed specifically to stress our system.

Hardware support can reduce the time spent operating on data structures by exploiting circuit-level parallelism. Such hardware data structures (HWDSs) can reduce the latency and jitter of data structure operations, which can benefit real-time systems by reducing worst-case execution times (WCETs). For example, a hardware priority queue (HWPQ) can enqueue and dequeue prioritized items in constant time with low variance; the best software implementations are in logarithmic-time asymptotic complexity for at least one of the enqueue or dequeue operations. The main problems with HWDSs are the limited size of hardware and the complexity of sharing it. In this paper we show that software support can help circumvent the size and sharing limitations of hardware so that applications can benefit from a HWDS. We evaluate our work by showing how the choice of software or hardware affects schedulability of task sets that use multiple priority queues of varying sizes. We model task behavior on two applications that are important in real-time and embedded domains: the grey-weighted distance transform for topology mapping and Dijkstra's algorithm for GPS navigation. Our results indicate that HWDSs can reduce the WCET of applications even when a HWDS is shared by multiple data structures or when data structure sizes exceed HWDS size constraints.

Embedded systems of an inherently distributed and highly replicated nature are vulnerable to a class of attacks that require local access and physical tampering. Processors using Encrypted Execution and Data (EED) technology, where instructions and data are stored in encrypted form in memory and locally decrypted, form an attractive solution for securing embedded systems, as these platforms have been shown to protect software and limit information leakage. However, numerous realistic attacks are still possible on EED platforms given the assumption of an adversary with physical access. In this paper, we present an integrated compiler and architectural approach to address a class of memory spoofing attacks, in which a sophisticated attacker is able to control off-chip buses and modify data blocks as they are loaded into the processor. Our approach, which utilizes cache boundaries to greatly simplify the integrity checking process, prevents an attacker from tampering, injecting, or replaying code and data. We make use of an on-chip reconfigurable logic component to implement our security mechanisms. This use of reconfigurable logic greatly simplifies the required hardware modifications - no changes are necessary to the CPU, cache, or off-chip memory. Our simulations on a number of benchmarks show that a high level of security can be achieved with a low performance overhead. The average overhead incurred is dependent on the cache size and type of integrity checking scheme used, but is less than 16% even for the most computationally intensive scheme. We present a hardware/software prototype mapped to a Field Programmable Gate Array (FPGA) platform in order to evaluate the space required and demonstrate the feasibility of our approach.

Software security has become a prominent area of research in recent years, with research efforts spanning a wide range of topics. Among these are techniques such as those in this paper that are in the general area of languages, compilers and architecture aimed at increasing the security of computing systems. This paper describes a compiler technique that performs risk-analysis on source code and generates an encrypted executable that both provides security but yet reduces overhead by selectively encrypting low-risk portions with less overhead. Regions of the code that are more vulnerable receive a higher degree of encryption. Experimental results for this technique, which we call Region-Based Security, using a collection of benchmarks show that execution overhead is reduced considerably by using this approach.

One of the key problems facing the computer industry today is ensuring the integrity of end-user applications and data. Researchers in the relatively new field of software protection investigate the development and evaluation of controls that prevent the unauthorized modification or use of system software. While many previously developed protection schemes have provided a strong level of security, their overall effectiveness has been hindered by a lack of transparency to the user in terms of performance overhead. Other approaches take to the opposite extreme and sacrifice security for the sake of this transparency. In this work we present an architecture for software protection that provides for a high level of both security and user transparency by utilizing field programmable gate array (FPGA) technology as the main protection mechanism. We demonstrate that by relying on FPGA technology, this approach can accelerate the execution of programs in a cryptographic environment, while maintaining the flexibility through reprogramming to carry out any compiler-driven protections that may be application-specific.

The new-found ubiquity of embedded processors in consumer and industrial applications brings with it an intensified focus on security, as a strong level of trust in the system software is crucial to their widespread deployment. The growing area of software protection attempts to address the key steps used by hackers in attacking a software system. In this paper, we introduce a unique approach to embedded software protection that utilizes a hardware/software codesign methodology. Results demonstrate that this framework can be the successful basis for the development of embedded applications that meet a wide range of security and performance requirements.

A strong level of trust in the software running on an embedded processor is a prerequisite for its widespread deployment in any high-risk system. The expanding field of software protection attempts to address the key steps used by hackers in attacking a software system. In this paper we present an efficient and tunable approach to some problems in embedded software protection that utilizes a hardware/software codesign methodology. By coupling our protective compiler techniques with reconfigurable hardware support, we allow for a greater flexibility of placement on the security-performance spectrum than previously proposed mainly-hardware or software approaches. Results show that for most of our benchmarks, the average performance penalty of our approach is less than 20%, and that this number can be greatly improved upon with the proper utilization of compiler and architectural optimizations.

In a wireless network some nodes incur a disproportionate share of the packet forwarding burden than the others: nodes lying toward the center tend to lie on more paths and therefore expend more energy in forwarding packets than other nodes, resulting in a shorter lifetime. While routes can be selected to alleviate this problem, we explore an entirely different and complementary approach by exploiting a wireless node's capability to adjust its transmission power. Each connection is partitioned into two segments, each of which uses the regular network or direct transmission between the source and the destination. The relative durations of each segment are optimized to balance energy consumption across the network. This paper formulates an energy balance optimization problem in terms of the segmentation time, and an algorithm is presented that reduces variance in energy consumption at the cost of a modest increase in average energy consumption. The paper also presents a distributed algorithm for this optimization problem.

Wireless sensor networks have recently attracted lots of research effort due to the wide range of applications. These networks must operate for months or years. However, the sensors are powered by battery, which may not be able to be recharged after they are deployed. Thus, energy-aware network management is extremely important. In this paper, we study the following problem: Given a set of sensors in the plane, assign transmit power to each sensor such that the induced topology containing only bidirectional links is strongly connected. This problem is significant in both theory and application. We prove its NP-completeness and propose two heuristics: power assignment based on minimum spanning tree (denoted by MST) and incremental power. We also show that the MST heuristic has a performance ratio of 2. Simulation study indicates that the performance of these two heuristics does not differ very much, but; on average, the incremental power heuristic is always better than MST.

This paper presents an experimental study of dynamic load balancing methods for a parallelized solution to a well-known problem in computational molecular biology: computing the accessible surface areas (ASA) of proteins. The main contribution is a better understanding of how certain techniques for load estimation and redistribution must be combined carefully for effectiveness and how these combinations need to change during the course of a computation. In particular, the Shrake-Rupley ASA algorithm is implemented and three aspects of dynamic load balancing are studied: how to estimate load imbalance (the estimation problem); when to invoke load redistribution (the invocation problem); and how to load balance (the mapping problem). The results in this paper show that a dynamically-selected mix of algorithms in each category that adapts to changing structure within the protein works better than a static periodic application of a static mix of algorithms.

For many real time applications, parallel computers offer a natural computing platform. However, very little attention has been paid to software support for real time embedded systems on parallel machines. The paper addresses the problem of formal software specification for parallel real time systems, and presents some features of a formal specification language-PRETSEL (Parallel REal Time SpEcification Language). The syntax of PRETSEL is presented and the formal semantic rules are defined. The effectiveness of PRETSEL is demonstrated through the specification of the functionality and timing requirements of a Sonar system.

This paper considers the problem of allocating files in a document tree among multiple processors in a parallel webserver. It is assumed that access patterns are characterized by branching probabilities for an access that starts at a node and progresses down the tree. A combinatorial optimization problem is formulated that includes load balancing and communication costs. The general problem is shown to be NP-complete, and a pseudo-polynomial time algorithm is outlined. In addition, two fast heuristic algorithms are presented and evaluated using simulation.

We study the problem of placing erasure nodes among passive stations in a slotted dual bus network. Erasure nodes are known to improve throughput by allowing slot reuse. It is also known that choices made in locating erasure nodes significantly impact network congestion and overall throughput-especially when traffic patterns exhibit a high degree of locality. We present algorithms to determine optimal placements of erasure nodes that improve upon prior work on this problem: we present simpler and faster polynomial-time algorithms and also consider various useful cost measures. These algorithms can be used to solve related placement problems in which limits on congestion and existing placements are given as input, and the goal is to find the minimum number of erasure nodes required to meet the congestion bound.

This paper addresses the problem of preemptive scheduling on parallel-task systems. A parallel-task system consists of several independent tasks, each of which can be executed on one or more processors. Du and Leung introduced the problem of minimizing the schedule length in parallel-task systems and showed that it is strongly NP-hard for both nonpreemptive and preemptive scheduling of independent tasks. This paper presents a polynomial-time approximation algorithm for preemptive scheduling of a parallel-task system with n processors and w tasks. We derive a tight worst-case performance bound of r for the approximation algorithm, where r is the maximum factor by which we can increase the number of processors on which a task can be executed. For example, $r = 2$ in the model defined by Du and Leung for parallel-task systems in which a task can be executed on any integral number of processors.

The availability of large-scale multitasked parallel architectures introduces the following processor assignment problem. We are given a long sequence of data sets, each of which is to undergo processing by a collection of tasks whose intertask data dependencies form a series-parallel partial order. Each individual task is potentially parallelizable, with a known experimentally determined execution signature. Recognizing that data sets can be pipelined through the task structure, the problem is to find a "good" assignment of processors to tasks. Two objectives interest us: minimal response time per data set, given a throughput requirement, and maximal throughput, given a response time requirement. Our approach is to decompose a series-parallel task system into its essential "serial" and "parallel" components; our problem admits the independent solution and recomposition of each such component. We provide algorithms for the series analysis, and use an algorithm due to Krishnamurti and Ma for the parallel analysis. For a p processor system and a series-parallel precedence graph with n constituent tasks, we give a O(np/sup 2/) algorithm that finds the optimal assignment (over a broad class of assignments) for the response time optimization problem; we find the assignment optimizing the constrained throughput in O(np/sup 2/ log p) time. These techniques are applied to a task system in computer vision.>

The authors introduce a family of networks that are a synthesis of banyans and hypercubes and are called the banyan-hypercubes (BH). They combine the advantageous features of banyans and hypercubes and thus have better communication capabilities. The networks can be viewed as consisting of interconnecting hypercubes. It is shown that many hypercube features can be incorporated into BHs with regard to routing, embedding of rings and meshes, and partitioning, and that improvements over the hypercube result are made. In particular, it is shown that BHs have better diameters and average distances than hypercubes, and they embed pyramids and multiple pyramids with dilation cost 1. An optimal routing algorithm for BHs and an efficient partitioning strategy are presented.>