The authors present dynamic reencryption of return addresses to mitigate their leakage. The authors’ method enforces programs to save return addresses as encrypted and renew the encryption states with fresh keys before or after vulnerable operations. When a function returns, it should restore the return address from its encryption using the most recent key not to cause a crash. Under the protection of their method, return addresses and keys may leak, but the disclosed bits become garbage because keys govern all return addresses through encryption, while changing before control‐flow proceeds into a vulnerable region. As a result, it becomes probabilistically infeasible to build exploits for intercepting control‐flow by using leaked return addresses or keys. They implemented the proposed method as an extension of the LLVM compiler that inserts reencryption code where necessary. They also have confirmed its effectiveness against information leak attacks carried out in the early stage of blind return‐oriented programming (BROP). The performance overhead ranges below 11.6% for processor‐intensive programs and 4.12% or less for web servers.

The authenticity of a piece of data or an instruction is crucial in mitigating threats from various forms of software attack. In spite of the various forms of protection against malicious attacks exploiting spurious data, adversaries have been successful in circumventing such protection. This paper proposes a memory-access validation scheme that manages information on spurious data at the granularity of the cache line size. A validation unit based on the proposed scheme answers queries from other components in the processor so that spurious data can be blocked before control flow diversion. We describe the design of this validation unit as well as its integration into the memory hierarchy of a modern processor and assess its memory requirement and performance impact with two simulators. The experimental results show that our scheme is able to detect synthesized payload injection attacks and to manage taint information with a moderate memory overhead under an acceptable performance impact.

This paper presents a software-transparent protection against binary code injection attacks. With a TLB (Translation Lookahead Buffer) that is usually split between data (DTLB) and instructions (ITLB) as found in modern processors, a simple protection can be developed based on an observation that activating an injected code causes a data TLB hit under ITLB miss with dirty bit set in the hit TLB entry. However, such a protection is not applicable in practice unless the system does not allow runtime code injections, while modern systems utilize runtime generated code rather extensively. The protection presented distinguishes an activation of a legitimated runtime generated codes from binary code injection attacks at an ITLB miss. The protection monitors not only address translation requests coming to TLB but also the address of the buffer used for I/O operations. This allows information flow tracking that filters out illegitimate code injection. The protection blocks an activation of the code injected via an I/O operation by analyzing TLB flags and the translation request profile. To evaluate our idea, we have revised the address translation function in Bochs x86 simulator and conducted code injection attacks available over the Internet to see how many code injections our idea can detect. The experimental results show that the proposed protection can detect all the code injection attacks tested without revising the operating system.

Software-based, fine-grain control flow integrity (CFI) validation technique has been proposed to enforce control flow integrity of program execution. By validating every indirect branch instruction, it can prevent various control flow attacks, but at the cost of non-trivial overhead: up to 50% and on average 21% as reported in a case study. We propose a new hardware mechanism to accelerate the CFI validation. It utilizes the branch prediction unit of modern processors to reduce the frequency of necessary validation, and proposes to use a small hardware structure called indirect branch filter cache (IBF cache) to further reduce the frequency of validation. The small IBF cache buffers and reuses previous validation results, which dramatically reduces the frequency of validation for all workloads we have studied. We collect the trace of indirect branch of various workloads on an Intel P4 computer and conduct trace-based simulation to estimate the performance overhead. Our results show that the overhead is negligible for all SPEC CPU2000int, SPEC CPU2006intprograms, TPC-C, WebStone and FTP server benchmarks.

Although there are various ways to exploit software vulnerabilities for malicious attacks, the attacks always result in unexpected behavior in program execution, deviating from what the programmer/user intends to do. Program execution blindly follows the execution path specified by control flow transfer instructions with the targets generated at run-time without any validation. An enhancement is therefore proposed to secure program execution by introducing a validation mechanism over control flow transfer instructions at micro-architecture level. The proposed scheme, as a behavior-based protection, treats a triplet of the indirect branch's location, its target address, and the execution path preceding it as a behavior signature of program execution and validates it at run-time. The first two pieces of information can prevent an adversary from overwriting control data and introducing foreign code or impossible targets to redirect an indirect branch. The last one is necessary to defeat the attacks that use a legitimate target but follow an unintended execution path. Interestingly, the branch predictor is found to contain the signature information already and doing a portion of the validation when resolving the branch, thus greatly reducing the validation frequency. An enhancement of branch target buffer (BTB) entry together with a signature table implemented in the form of a Bloom filter in hardware is proposed to incorporate the validation into the processor's pipeline, providing a new defense in the processor architecture to secure program execution.

Current micro-architecture blindly uses the address in the program counter to fetch and execute instructions without validating its legitimacy. Whenever this blind-folded instruction sequencing is not properly addressed at a higher level by system, it becomes a vulnerability of control data attacks, today's dominant and most critical security threats. To remedy it, this paper proposes a micro-architectural mechanism to validate control flow transfer at run-time at machine instruction level. It is proposed to have a hardware table consisting of legitimate indirect branches and their target pairs (IBPs) to aid the validation. The IBP table is implemented in the form of a cascading Bloom filter to store the security information as well as to enable fast validating. Based on a key observation that branch prediction unit existing in most speculative-execution processors already provides a portion of the control flow validation, our scheme activates the validation only on indirect branch mis-predictions. Because of the Bloom filter and the rarity of mis-predictions of indirect branches, the validation incurs moderate storage overhead and little performance penalty.

We present a solution to eliminate the requirements of routing table sorting by prefix length in IP lookup devices using ternary content addressable memories (TCAMs). This reduces delays arising from routing table updates from linear to constant time. This solution introduces slight modifications to the organization of the routing table including the elimination of the built-in priority encoder. The routing table entries are split by output port to remove their dependence on length. Overall, the solution presented reduces the insertion problem to lookup speed while maintaining similar clock rates and storage requirements of traditional designs.

This paper presents a systematic method for DDoS attack detection. DDoS attack can be considered system anomaly or misuse from which abnormal behavior is imposed on network traffic. Attack detection can be performed via abnormal behavior identification. Network traffic characterization with behavior modeling could be a good guidance of attack detection. Aggregated traffic has been found to be strong bursty across a wide range of time scales. Wavelet analysis is able to capture complex temporal correlation across multiple time scales with very low computational complexity. We utilize energy distribution based on wavelet analysis to detect DDoS attack traffic. Energy distribution over time would have limited variation if the traffic keeps its behavior over time (i.e. attack-free situation); while an introduction of attack traffic in the network would elicit significant energy distribution deviation in short time period. Our experimental results with typical Internet traffic trace show that energy distribution variance changes markedly causing a "spike" when traffic behaviors affected by DDoS attack In contrast, normal traffic exhibits a remarkably stationary energy distribution. In addition, this spike in energy distribution variance can be captured in early stage of attack, for ahead of congestion build-up, making it an effective attack detection.

For more accurate branch prediction, global as well as local histories have been studied and a need for hybrid history has emerged. Not only do different parts of a program require different types of histories, but some branches dynamically vary the type of history. To solve this problem, schemes involving dynamic selectors as opposed to static have been proposed. Initially, history represented the directions of previous branches (pattern based). Then came the idea of storing the target addresses of previous branches, thus predicting based on the path (path-based). The path- and pattern-based schemes do have their drawbacks. The paper studies a potential problem faced by the path- and pattern-based schemes and alleviates it by presenting a new scheme, in which the path and pattern histories are alloyed. This scheme is proposed as opposed to having two predictors, path-based and pattern-based, and a selector that dynamically predicts between them. Alloying path and pattern, eliminates the problem of selecting between the two schemes and instead merges the information. It also diminishes the shortcoming of the two schemes and thus acts as a double-edged sword.

The need for a low power, high performance embedded processor has grown at a very fast pace in recent years. Embedded processors require smaller cache size for low power system-on-a-chip consideration. Decreasing cache size leads to reduced power consumption because a smaller cache has less capacitance from the bit array size as well as smaller drivers in decoder or peripheral circuitry.. Unfortunately, performance also decreases due to a lower cache hit rate when the cache size becomes smaller. Recently, to improve the miss rate on a cache, many prefetching schemes have been introduced. However, on a small cache, prefetching schemes do not perform well because projected data replace the data that a processor will need in the future. This causes cache pollution, which degrades system performance. To overcome the cache pollution on a small cache, the paper introduces a new technique called "Fixed Prefetch Block" that integrates with the prefetching scheme. To evaluate the effectiveness of our scheme, extensive stimulations on SPEC95 integer benchmarks and Mediabench benchmarks suites were performed. Results from the simulations indicate that with our proposed technique, cache pollution can be reduced on a small set associative cache.

Wide-issue processors issuing tens of instructions per cycle, put heavy stress on the memory system, including data caches. For wide-issue architecture, data cache needs to be heavily multi-ported with extremely wide data-paths. The paper studies a scalable solution to achieve multi-porting with short data-paths and less hardware complexity at higher clock-rates. Our approach divides memory streams into multiple independent sub-streams with the help of a prediction mechanism before they enter the reservation stations. Partitioned memory-reference instructions are then fed into separate memory pipelines, each of which is connected to a small data-cache, called the access region cache. The separation of independent memory references, in an ideal situation, facilitates the use of multiple caches with smaller number of ports and thus increases the data-bandwidth. We describe and evaluate a wide-issue processor with distinct memory pipelines, driven by a prediction mechanism. The potential performance of the proposed design is measured by comparing it with existing multi-porting solution as well as an ideal multi-ported data cache.

Providing adequate data bandwidth is extremely important for a future wide-issue processor to achieve its full performance potential. Adding a large number of ports to a data cache, however, becomes increasingly inefficient and can add to the hardware complexity significantly. This paper takes an alternative or complementary approach for providing more data bandwidth, called data decoupling. This paper especially studies an interesting, yet less explored, behavior of memory access instructions, called access region locality, which is concerned with each static memory instruction and its range of access locations at runtime. Our experimental study using a set of SPEC95 benchmark programs shows that most memory access instructions reference a single region at runtime. Also shown is that it is possible to accurately predict the access region of a memory instruction at runtime by scrutinizing the addressing mode of the instruction and the past access history of it. We describe and evaluate a wide-issue superscalar processor with two distinct sets of memory pipelines and caches, driven by the access region predictor. Experimental results indicate that the proposed mechanism is very effective in providing high memory bandwidth to the processor, resulting in comparable or better performance than a conventional memory design with a heavily multiported data cache that can lead to much higher hardware complexity.

Providing adequate data bandwidth is extremely important for a wide-issue superscalar processor to achieve its full performance potential. Adding a large number of ports to a data cache however becomes increasingly inefficient and can add to the hardware complexity significantly. This paper takes an alternative or complementary approach for providing more data bandwidth, called the data-decoupled architecture. The approach, with support from the compiler and/or hardware, partitions the memory stream into two independent streams early in the processor pipeline, and feeds each stream to a separate memory access queue and cache. Under this model, the paper studies the potential of decoupling memory accesses to program's local variables that are allocated on the run-time stack. Using a set of integer and floating-point programs from the SPEC95 benchmark suite, it is shown that local variable accesses constitute a large portion of all the memory references, while their reference space is very small, averaging around 7 words per (static) procedure. To service local variable accesses quickly, two optimizations fast data forwarding and access combining, are proposed and studied. Some of the important design parameters, such as the cache size, the number of cache ports, and the degree of access combining, are studied based on simulations. The potential performance of the proposed scheme is measured using various configurations, and it is concluded that the scheme can become a viable alternative to building a single multi-ported data cache.

This paper studies an interesting yet less explored behavior of memory access instructions, called access region locality. Unlike the traditional temporal and spatial data locality that focuses on individual memory locations and how accesses to the locations are inter-related, the access region locality concerns with each static memory instruction and its range of access locations at run time. We consider program's data, heap, and stack regions in this paper. Our experimental study using a set of SPEC95 benchmark programs shows that most memory reference instructions access a single region at run time. Also shown is that it is possible to accurately predict the access region of a memory instruction at run time by scrutinizing the addressing mode of the instruction and the past access region history of it. A simple run-time access region predictor is developed that is similar to a branch predictor in structure. We describe and evaluate a superscalar processor with two distinct sets of memory pipelines, driven by the access region predictor. Experimental results indicate that the proposed mechanism is very effective in providing high memory bandwidth to the processor, resulting in comparable or better performance than a conventional memory design with a heavily multi-ported data cache that can lead to much higher hardware complexity.

The paper revisits three distributed shared memory (DSM) architectures to clarify them with their binding times for new addresses at the local memory: page fault time, node miss time, and cache miss time. The DSM architectures which have different binding times arrange data in different ways with different overheads at an event of reference. Since a large number of cache misses can occur in a large (relative to the cache size) working set, binding at the page fault time alone cannot efficiently utilize locality of reference at the local memory. In a small working set, most of the addresses bound to the local memory at a node miss time are not effective due to the low cache miss rate. The paper shows that binding at the cache miss time can improve system performance.

Array data flow analysis is known to be crucial to the success of array privatization, one of the most important techniques for program parallelization. It is clear that array data flow analysis should be performed interprocedurally and symbolically, and that it often needs to handle the predicates represented by IF conditions. Unfortunately, such a powerful program analysis can be extremely time-consuming if not carefully designed. How to enhance the efficiency of thk analysis to a practical level remains an issue largely untouched to date. This paper documents our experience with building a highly efficient array data flow analyzer which is based on guarded array regions and which runs faster, by one or two orders of magnitude, than other similarly powerful tools.

The asynchronous transfer mode (ATM) is the choice of transport mode for broadband integrated service digital networks (B-ISDNs). We propose a window-based contention resolution algorithm to achieve higher throughput for nonblocking switches in ATM environments. In a nonblocking switch with input queues, significant loss of throughput can occur due to head-of-line (HOL) blocking when first-in first-out (FIFO) queueing is employed. To resolve this problem, we employ bypass queueing and present a cell scheduling algorithm which maximizes the switch throughput. We also employ a queue length based priority scheme to reduce the cell delay variations and cell loss probabilities. With the employed priority scheme, the variance of cell delay is also significantly reduced under nonuniform traffic, resulting in lower cell loss rates (CLRs) at a given buffer size. As the cell scheduling controller, we propose a neural network (NN) model which uses a high degree of parallelism. Due to higher switch throughput achieved with our cell scheduling, the cell loss probabilities and the buffer sizes necessary to guarantee a given CLR become smaller than those of other approaches based on sequential input window scheduling or output queueing.

DICE is a shared-bus multiprocessor based on a distributed shared-memory architecture, known as Cache-Only Memory Architecture (COMA). Unlike previous COMA proposals for large-scale multiprocessing, DICE utilizes the COMA to effectively decrease the gap between modern high-performance microprocessors and the bus. As microprocessors become faster and demand more bandwidth, the already limited scalability of a shared bus decreases even further. DICE tries to optimize the COMA for a shared-bus medium, in particular to reduce detrimental effects of the cache coherence and the "last memory block" problem on replacement. In this paper, we present a global bus design for a bus-based COMA multiprocessor using the IEEE Futurebus+ standard backplane bus and the Texas Instruments chip-set. Our design demonstrates that necessary bus transactions for DICE can be done efficiently with existing standard bus signals. Considering the benefits of the COMA and the little design complexity it adds to the conventional shared-bus multiprocessor design, a bus-based COMA multiprocessor such as DICE can be become a viable candidate for future shared-bus multiprocessor designs.

The asynchronous transfer mode (ATM) is the choice of transport mode for B-ISDN. In this paper, we propose a window-based ATM cell scheduling scheme using a neural network to achieve higher throughput for nonblocking ATM switches. In a nonblocking switch with input queues, significant loss of throughput can occur due to head-of-line blocking when FIFO queueing is employed. To resolve this problem, we propose an optimal input bypass queueing method which maximizes switch throughput. We also employ a queue length based priority scheme to reduce cell delay variations and cell loss probabilities. With the employed priority scheme, the variance of delay is also significantly reduced under nonuniform traffic, resulting in lower cell loss rates at a given buffer size. Due to higher switch throughput achieved with our cell scheduling, the cell loss probabilities and the buffer sizes necessary to guarantee a given cell loss rate become even smaller than those with output queueing that has been known to provide better performance than input queueing.

Array dataflow information plays an important role for successful automatic parallelization of Fortran programs. This paper proposes a powerful symbolic array dataflow analysis to support array privatization and loop parallelization for programs with arbitrary control flow graphs and acyclic call graphs. Our scheme summarizes array access information using guarded array regions and propagates such regions over a Hierarchical Supergraph (HSG). The use of guards allows us to use the information in IF conditions to sharpen the array dataflow analysis and thereby to handle difficult cases which elude other existing techniques. The guarded array regions retain the simplicity of set operations for regular array regions in common cases, and they enhance regular array regions in complicated cases by using guards to handle complex symbolic expressions and array shapes. Scalar values that appear in array subscripts and loop limits are substituted on the fly during the array information propagation, which disambiguates the symbolic values precisely for set operations. We present efficient algorithms that implement our scheme. Initial experiments of applying our analysis to Perfect Benchmarks show promising results of improved array privatization.

This paper considers automatic restructuring of loops with conditional branching for parallel processing, especially a class of loops termed "conditional cyclic loops." A conditional cyclic loop possesses a dependence cycle caused by conditional branching across loop iterations, which makes it difficult to parallelize. In general, parallel execution of a conditional cyclic loop provides little benefit due to the need of solving a full-order nonlinear Boolean recurrence relation. However, the Boolean recurrence in practice is often of simpler forms. With the simpler forms, the number of possible predicate values of conditional branching is reduced drastically compared to a general conditional cyclic loop, These simple forms of conditional cyclic loops found in practice can be parallelized for O(p/ log p) speedup with p processors.>

Analyzing the performance of finite buffered multistage networks has been considered a difficult task because of dynamic blocking effects due to finite sized buffers. With the multistage networks enhanced with combining capability, in which multiple requests directed to a shared location combine together to form a single request to be forwarded, the analysis becomes even more difficult due to the interactions between combining probability and queuing delay. Performance bounds for combining networks are known under two extreme assumptions: infinite combining queues and saturated finite combining queues. We analyze multistage combining networks with the consideration of blocking due to finite combining queues. Our analysis provides iterative solutions for combining probability, blocking probability, and queuing delay.>

This paper proposes a high throughput packet switching network with bypass queues based on a MIN. We improve the switch throughput by partitioning the input buffers into disjoint buffer sets and multiplexing several sets of nonblocking packets within a time slot. A neural network model is presented as a controller for packet scheduling and multiplexing in the switch.

Multistage interconnection networks (MINs) have long been studied for use in switching networks. Since they have a unique path between source and destination and the intermediate nodes of the paths are shared, internal blocking can cause very poor throughput. This paper proposes a high throughput ATM switch consisting of an Omega network with a new form of input queues called bypass queues. We also improve the switch throughput by partitioning the Input buffers into disjoint buffer sets and multiplexing several sets of nonblocking cells within a time slot, assuming that the routing switch operates only a couple of times faster than the transmission rate. A neural network model is presented as a controller for cell scheduling and multiplexing in the switch. Our simulation results under uniform traffic show that the proposed approach achieves almost 100% of potential switch throughput.>

A bound on the delays in multistage combining networks is developed by considering an idealized combining under hot-spot traffic. It is concluded that multistage combining networks are stable, at least in theory, under hot-spot traffic. The author discusses some problems in achieving such stability in practice.>

Extra Group Networks, a class of fault-tolerant multistage interconnection networks, are introduced. An EGN-m of size N is designed to have m+1 unique-path multistage-networks of size N/m. This approach of constructing the network allows that an EGN-m can provide full-access capability in the presence of multiple faults, up to m, in any stage. EGNs can also maintain the permutation capability of the unique-path multistage-network of size N in the presence of any single fault. It is shown that EGNs are more cost-effective than other previously proposed fault-tolerant multistage-interconnection networks with a similar fault-tolerant capability.>

The feasibility of automatic restructuring of nonnumerical programs for parallel processing is studied through experiments using Parafrase, an automatic restructurer at the University of Illinois, Urbana-Champaign. Parallel processing speedup results due to automatic restructuring for several basic nonnumerical problems are presented. The loops encountered are classified at a low level. On the basis of the speedup results and the analyses of the loop types, the difficulty and the effectiveness of automatic restructuring are discussed. The experiments suggest that automatic restructuring can be a useful tool for exploiting parallelism in the sequential form of nonnumerical programs.