10193683
Using Branch Correlation to Identify Infeasible Paths for Anomaly Detection
In this paper, we propose a system called infeasible path detection system (IPDS) to combat memory tampering attacks causing invalid program control flows. In our system, the compiler analyzes correlations between branches and then the analyzed information is conveyed to the runtime system. The runtime system detects dynamic infeasible program paths by combining compiler determined information with runtime information to check the legality of the path taken during execution. IPDS achieves a zero false positive rate and can detect a high percentage of memory tampering for many attacks in which the tampering actually causes a change in control flow. Moreover, IPDS only incurs a modest amount of hardware resource and negligible performance penalty
9131829
Memory Protection through Dynamic Access Control
Current anomaly detection schemes focus on control flow monitoring. Recently, Chen et al. discovered that a large category of attacks tamper program data but do not alter control flows. These attacks are not only realistic, but are also as important as classical attacks tampering control flows. Detecting these attacks is a critical issue but has received little attention so far. In this work, we propose an intrusion detection scheme with both compiler and micro-architecture support detecting data tampering directly. The compiler first identifies program regions in which the data should not be modified as per program semantics. Then the compiler performs an analysis to determine the conditions for modification of variables in different program regions and conveys this information to the hardware and the hardware checks the data accesses based on the information. If the compiler asserts that the data should not be modified but there is an attempt to do so at runtime, an attack is detected. The compiler starts with a basic scheme achieving maximum data protection but such a scheme also suffers from high performance overhead. We then attempt to reduce the performance overhead through different optimization techniques. Our experiments show that our scheme achieves strong memory protection with tight control over the performance degradation. Thus, our major contribution is to provide an efficient scheme to detect data tampering while minimizing the overhead
430991
Attacks and risk analysis for hardware supported software copy protection systems
<i>Recently, there is a growing interest in the research community to use tamper-resistant processors for software copy protection. Many of these tamper-resistant systems rely on a specially tailored secure processor to prevent, 1) illegal software duplication, 2) unauthorized software modification, and 3)unauthorized software reverse engineering. The published techniques primarily focused on feasibility demonstration and design details rather than analyzing security risks and potential attacks from an adversary's perspective. The uniqueness of software copy protection may lead to some potential attacks on such a secure environment that have been largely ignored or insufficiently addressed in the literature. One should not take security for granted just because it is implemented on a tamper-resistant secure processor. Detailed analysis on some proposed ideas reveal potential vulnerability and attacks. Some of the attacks are known to the security community, nevertheless, their implications to software copy protection are not well understood and discussed. This paper presents these cases for designers to improve their systems and circumvent the potential security pitfalls and for users of such systems to be aware of the potential risks</i>
15462549
Tamper-resistant whole program partitioning
Due to limited available memory (of the order of Kilobytes) on embedded devices (such as smart cards), we undertake an approach of partitioning the whole program when it does not fit in the memory. The program partitions are downloaded from the server on demand into the embedded device just before execution. We devise a method of partitioning the code and data of the program such that no information regarding the control flow behavior of the program is leaked out. This property is called tamper resistance and it is very important for secure embedded devices such as smart cards which could hold sensitive information and/or carry out critical computation such as financial transactions. A preliminary solution to this problem was proposed in our earlier work [1]. This work proposes a new and more comprehensive solution to the problem. First, we propose a new policy which is based on keeping nothing in terms of partitions on the smart card. This policy is unlike the one in previous work which mandated keeping partitions in memory to which control flow was guaranteed to return. Based on this new policy, a new partitioning algorithm is proposed for minimal safe partitions which reduces their memory requirements over previous work. The drawback of this new policy is however lower execution speed due to frequent communication encountered. In order to not significantly degrade performance, we propose caching frequently executed functions on the smart card without violation of tamper resistance. A framework is designed to determine the set of functions to be cached in conjunction with specific minimal safe partitions. Further reduction in memory requirements is achieved due to the data partitioning.The decrease in memory footprint over the previous method is 27% for code memory and 32.4% for data memory on average. The speed-up over the old method is quite significant when applied to whole programs in large benchmarks (500 times on average). The conclusion is that previous method [1] is not suitable as a whole program partitioning strategy whereas the new proposed method is a viable solution.
1373345
Leakage-proof program partitioning
Due to limited available memory (of the order of Kilobytes) on embedded devices (such as smart cards), we undertake an approach of partitioning a whole program. The program partitions are down-loaded from the server on demand into the embedded device just before execution. We devise a novel method of partitioning the code and data of the program such that no information regarding the control flow and behavior of the program is leaked out. In other words, by observing the program partitions that are down-loaded from the server, one is unable to guess which branches are taken in the program. The partitioning scheme generates minimal safe program regions which do not reveal the control flow information when transmitted on demand but any further partitioning of which will reveal such an information. Minimal safe regions allow minimal usage of memory on the embedded device and thus enable maximal number of multiple applications to simultaneously reside on the embedded device. The minimal safe regions can be merged on demand to create larger safe regions to improve runtime efficiency. The larger the number of regions to be downloaded on the device, the lower is the performance of the application and vice-versa. Our approach handles this tradeoff between the number of simultaneous applications that would reside on the embedded device and the performance of each application. This approach is scalable both to the number of simultaneous applications and to the amount of memory available. The worst case performance degradation is shown to be below 10% with the benefit of allowing arbitrarily large/multiple applications to be deployed.
17916955
Hardware-managed register allocation for embedded processors
Most modern processors (either embedded or general purpose) contain higher number of physical registers than those exposed in the ISA. Due to a variety of reasons, this phenomenon is likely to continue especially on embedded systems where encoding space is very limited. Saving the encoding space leads to lower power consumption in the I-cache; on the other hand, harnessing more physical registers saves power in the memory subsystem and reduces latency as well. These design decisions however result in the difficulty of register allocation for a compiler due to limited number of exposed registers at ISA level.In this paper, we therefore propose a hardware managed register allocation scheme to allocate more physical registers at runtime and to utilize them. As a byproduct, we also show that hardware managed register allocation has other merits such as better exploitation of low register pressure regions, more flexible management of caller-save/callee-save registers, etc.Our approach consists of both compiler and hardware enhancements. On the compiler side we assign variables at various stack offsets such that the offsets indicate the relative allocation priorities at runtime. The hardware is modified to identify such spills and make decisions whether they should be put in the (invisible) physical registers based on their relative priorities. Finally, our results show slight improvement in the instructions per cycle counts (IPC) but significant power consumption reduction in the cache.
2269279
Model-based segmentation of medical imagery by matching distributions
The segmentation of deformable objects from three-dimensional (3-D) images is an important and challenging problem, especially in the context of medical imagery. We present a new segmentation algorithm based on matching probability distributions of photometric variables that incorporates learned shape and appearance models for the objects of interest. The main innovation over similar approaches is that there is no need to compute a pixelwise correspondence between the model and the image. This allows for a fast, principled algorithm. We present promising results on difficult imagery for 3-D computed tomography images of the male pelvis for the purpose of image-guided radiotherapy of the prostate.
1202850
Anycast Algorithms Supporting Optical Burst Switched Grid Networks
In this paper we consider implementing optical burst switching as a technology for building grids with computationally intensive requirements. This architecture has been referred to as grid-over-OBS (GoOBS). First, we briefly describe the proposed layered grid architecture and show how OBS can be positioned within the grid architecture. Then, we present a generic framework for anycast routing in the context of GoOBS when requests don't have an explicit destination address and they can be serviced by any appropriate grid resource. We also develop several algorithms to support anycasting when only a single copy of a request is transmitted. Through simulation analysis, we show the performance of our anycast algorithms and compare them with traditional shortest-path unicast routing in which all jobs have specific addresses. Our performance analysis focuses on blocking probability of requests and average end-to-end delay
6519292
Event Correlation: Language and Semantics
Event correlation is a service provided by middleware platforms that allows components in a publish/subscribe architecture to subscribe to patterns of events rather than individual events. Event correlation improves the scalability and performance of distributed systems, increases their analyzability, while reducing their complexity by moving functionality to the middleware. To ensure that event correlation is provided as a standard and reliable service, it must possess well-defined and unambiguous semantics.
17846455
Systematic Design of Original and Modified Mastrovito Multipliers for General Irreducible Polynomials
This paper considers the design of bit-parallel dedicated finite field multipliers using standard basis. An explicit algorithm is proposed for efficient construction of Mastrovito product matrix, based on which we present a systematic design of Mastrovito multiplier applicable to GF(2/sup m/) generated by an arbitrary irreducible polynomial. This design effectively exploits the spatial correlation of elements in Mastrovito product matrix to reduce the complexity. Using a similar methodology, we propose a systematic design of modified Mastrovito multiplier, which is suitable for GF(2/sup m/) generated by high-Hamming weight irreducible polynomials. For both original and modified Mastrovito multipliers, the developed multiplier architectures are highly modular, which is desirable for VLSI hardware implementation. Applying the proposed algorithm and design approach, we study the Mastrovito multipliers for several special irreducible polynomials, such as trinomial and equally-spaced-polynomial, and the obtained complexity results match the best known results. Moreover, we have discovered several new special irreducible polynomials which also lead to low-complexity Mastrovito multipliers.
13956689
The Decidability of the First-Order Theory of Knuth-Bendix Order
Two kinds of orderings are widely used in term rewriting and theorem proving, namely recursive path ordering (RPO) and Knuth-Bendix ordering (KBO). They provide powerful tools to prove the termination of rewriting systems. They are also applied in ordered resolution to prune the search space without compromising refutational completeness. Solving ordering constraints is therefore essential to the successful application of ordered rewriting and ordered resolution. Besides the needs for decision procedures for quantifier-free theories, situations arise in constrained deduction where the truth value of quantified formulas must be decided. Unfortunately, the full first-order theory of recursive path orderings is undecidable. This leaves an open question whether the first-order theory of KBO is decidable. In this paper, we give a positive answer to this question using quantifier elimination. In fact, we shall show the decidability of a theory that is more expressive than the theory of KBO.