bluuebunny/crossref_metadata_2025 huggingface dataset:
Efficient reasoning about data trees via integer linear programming
Authors: David Claire , Libkin Leonid , Tan Tony
Published: September 2012

Data trees provide a standard abstraction of XML documents with data values: they are trees whose nodes, in addition to the usual labels, can carry labels from an infinite alphabet (data). Therefore, one is interested in decidable formalisms for reasoning about data trees. While some are known—such as the two-variable logic—they tend to be of very high complexity, and most decidability proofs are highly nontrivial. We are therefore interested in reasonable complexity formalisms as well as better techniques for proving decidability.

Here we show that many decidable formalisms for data trees are subsumed—fully or partially—by the power of tree automata together with set constraints and linear constraints on cardinalities of various sets of data values. All these constraints can be translated into instances of integer linear programming, giving us an NP upper bound on the complexity of the reasoning tasks. We prove that this bound, as well as the key encoding technique, remain very robust, and allow the addition of features such as counting of paths and patterns, and even a concise encoding of constraints, without increasing the complexity. The NP bound is tight, as we also show that the satisfiability of a single set constraint is already NP-hard.

We then relate our results to several reasoning tasks over XML documents, such as satisfiability of schemas and data dependencies and satisfiability of the two-variable logic. As a final contribution, we describe experimental results based on the implementation of some reasoning tasks using the SMT solver Z3.
An intuitive approach to determine test adequacy in safety-critical software
Authors: Babu P. Arun , Kumar C. Senthil , Murali N. , Jayakumar T.
Published: September 2012

Safety-critical software must adhere to stringent quality standards and is expected to be thoroughly tested. However, exhaustive testing of software is usually impractical. The two main challenges faced by a software testing team are generation of effective test cases and demonstration of testing adequacy.

This paper proposes an intuitive and conservative approach to determine the test adequacy in safety-critical software. The approach is demonstrated through a case study: the core temperature monitoring system of a nuclear reactor. We combine conservative test coverage of unique execution path test cases, and the results from mutation testing to determine the test adequacy.

Although mutation testing is a powerful technique, the difficulty in identifying equivalent mutants has limited its practical utility. To gain confidence on the computed test adequacy: (i) faults during mutation testing must be induced at all possible execution paths of the code, (ii) properties of unkilled mutants must be studied, and (iii) all equivalent mutants must be detected. In this regard; results of static, dynamic and coverage analysis of the mutants is presented, and a technique to identify the likely equivalent mutants is proposed.
Application of TLRO to refute an incorrect mutual exclusion algorithm
Authors: Bandyopadhyay Anup Kumar
Published: September 2012

Modeling of iterative commands in a concurrent process is difficult because the termination depends on the states of different processes. In this paper a Temporal Logic Related to Observation (TLRO)-based modeling of the same is considered. For simplicity we restrict ourselves to 'while do' construct only. Using a commonsense scenario it is shown that the construct may be described by a set of three state transition rules. In a concurrent system the termination condition is determined by the states of different processes. To ensure termination, therefore, temporal ordering of the executions of different state transition rules at different processes needs to be investigated. For this purpose we prove two theorems. The entire derivation is then used to refute a well known incorrect mutual exclusion algorithm. A counter example for the algorithm could be derived during this exercise. This is an improvement over our earlier effort that used the weakest precondition calculus as a modeling tool.
Maintainability prediction of object-oriented software system by multilayer perceptron model
Authors: Dubey Sanjay Kumar , Rana Ajay , Dash Yajnaseni
Published: September 2012

To accomplish software quality, correct estimation of maintainability is essential. However there is a complex and non-linear relationship between object-oriented metrics and maintainability. Thus maintainability of object-oriented software can be predicted by applying sophisticated modeling techniques like artificial neural network. Multilayer Perceptron neural network is chosen for the present study because of its robustness and adaptability. This paper presents the prediction of maintainability by using a Multilayer Perceptron (MLP) model and compares the results of this investigation with other models described earlier. It is found that efficacy of MLP model is much better than both Ward and GRNN network models.
A comprehensive study of view maintenance approaches in data warehousing evolution
Authors: Jain Hemant , Gosain Anjana
Published: September 2012

A data warehouse mainly stores integrated information over data from many different remote data sources for query and analysis. The integrated information at the data warehouse is stored in the form of materialized views. Using these materialized views, user queries may be answered quickly and efficiently as the information may be directly available. These materialized views must be maintained in answer to actual relation updates in the different remote sources. One of the issues related to materialized views is that whether they should be recomputed or they should be adapted incrementally after every change in the base relations. View maintenance is the process of updating a materialized view in response to changes to the underlying data is called view maintenance. There are several algorithms developed by different authors to ease the problem of view maintenance for data warehouse systems. In this paper, we have provided a comprehensive study on research works of different authors related to DW view maintenance considering various parameters and presented the same in tabular way.
Applying genetic algorithm to increase the efficiency of a data flow-based test data generation approach
Authors: Mahajan Manish , Kumar Sumit , Porwal Rabins
Published: September 2012

The success or failure of the entire software development process relies on the software testing component which is responsible for ensuring that the software that is released is free from bugs. One of the major labor intensive activities of software testing is the generation of the test data for the purpose of applying the testing methodologies. Many approaches have been tried and tested for automating the process of generating the test data. Meta-heuristics have been applied extensively for improving the efficiency of the process. This paper analyses the effectiveness of applying genetic algorithms for generating test data automatically using data flow testing approach. An incremental coverage measurement method is used to improve the convergence.
Reusability metrics and effect of reusability on testing of object oriented systems
Authors: Patwa Sanjeev , Malviya Anil Kumar
Published: September 2012

Software reuse has become very popular in software development. There are several beneficial aspects of object oriented systems including code reuse, reusability and reusability of testing efforts. Reusable software components are the building blocks that can make a system able to respond quickly to change. This paper presents the hypothesis that the testing effort in object-oriented software can be inherited and reused similar to that of the coding effort. Therefore the testability and maintainability of the object-oriented software can be improved by adapting a reusability approach. In this paper some new metrics namely Reusability of a Class in a System (RCS), Average Degree of Reusability (AR), Specialize class to Base class Reusable Metric (SBRM) have been proposed.
Testing for concurrency in UML diagrams
Authors: Shirole Mahesh , Kumar Rajeev
Published: September 2012

Concurrent programming is increasingly being used in many applications with the advent of multi-cores. The necessary support for execution of multi-threading is getting richer. Notwithstanding, a concurrent program may behave nondeterministically, it may result in different outputs with the same input in different runs.

The aim of this study is to generate test sequences for concurrency from unified modelling language (UML) behavioral models such as sequence and activity diagrams. Generating exhaustive test cases for all concurrent interleaving sequences is exponential in size. Therefore, it is necessary to find adequate test cases in presence of concurrency to uncover errors due to, e.g., data race, synchronization and deadlocks. In order to generate adequate test cases a novel search algorithm, which we call concurrent queue search (CQS) is proposed. The CQS handles random nature of concurrent tasks. To generate test scenarios, a sequence diagram is converted into an activity diagram. An activity diagram encapsulates sequential, conditional, iterative and concurrent ows of the control. By the experimental results, it was observed that test sequences generated by CQS algorithm are superior as compared to DFS and BFS search algorithms.
A monitoring mechanism to support agility in service-based application evolution
Authors: Wu Ye-Chi , Jiau Hewijin Christine
Published: September 2012

Service orientation promotes an agile development paradigm for rapid application development and presents evolutionary challenges to adapt to frequent environmental changes. To maintain effective service-based application operations, this research introduces a Serv-Gears framework to maintain a mechanism for evolution-need monitoring. Inheriting major characteristics of a service-oriented paradigm, this mechanism is designed in a service-based style to facilitate development agility in evolution planning and implementation. Serv-Gears allows developers to continuously specify service-based monitors even during application operations. The specified monitors are included dynamically in the running application to collect monitoring results. Evolution plans are then effectively developed and assessed. Such an integrated development environment provided by Serv-Gears facilitates agile service-based application evolution.
Modeling virtualized applications using machine learning techniques
Authors: Kundu Sajib , Rangaswami Raju , Gulati Ajay , Zhao Ming , Dutta Kaushik
Published: September 2012

With the growing adoption of virtualized datacenters and cloud hosting services, the allocation and sizing of resources such as CPU, memory, and I/O bandwidth for virtual machines (VMs) is becoming increasingly important. Accurate performance modeling of an application would help users in better VM sizing, thus reducing costs. It can also benefit cloud service providers who can offer a new charging model based on the VMs' performance instead of their configured sizes. In this paper, we present techniques to model the performance of a VM-hosted application as a function of the resources allocated to the VM and the resource contention it experiences. To address this multi-dimensional modeling problem, we propose and refine the use of two machine learning techniques: artificial neural network (ANN) and support vector machine (SVM). We evaluate these modeling techniques using five virtualized applications from the RUBiS and Filebench suite of benchmarks and demonstrate that their median and 90th percentile prediction errors are within 4.36% and 29.17% respectively. These results are substantially better than regression based approaches as well as direct applications of machine learning techniques without our refinements. We also present a simple and effective approach to VM sizing and empirically demonstrate that it can deliver optimal results for 65% of the sizing problems that we studied and produces close-to-optimal sizes for the remaining 35%.
Virtualization challenges
Authors: Lv Hui , Dong Yaozu , Duan Jiangang , Tian Kevin
Published: September 2012

Server consolidation, by running multiple virtual machines on top of a single platform with virtualization, provides an efficient solu-tion to parallelism and utilization of modern multi-core processors system. However, the performance and scalability of server con-solidation solution on modern massive advanced server is not well addressed. In this paper, we conduct a comprehensive study of Xen per-formance and scalability characterization running SPECvirt_sc2010, and identify that large memory and cache footprint, due to the unnecessary high frequent context switch, introduce additional challenges to the system performance and scalability. We propose two optimizations (dynamically-allocable tasklets and context-switch rate controller) to improve the performance. The results show the improved memory and cache efficiency with a reduction of the overall CPI, resulting in an improvement of server consolidation capability by 15% in SPECvirt_sc2010. In the meantime, our optimization achieves an up to 50% acceleration of service response, which greatly improves the QoS of Xen virtualization solution.
REEact
Authors: Wang Wei , Dey Tanima , Moore Ryan W. , Aktasoglu Mahmut , Childers Bruce R. , Davidson Jack W. , Irwin Mary Jane , Kandemir Mahmut , Soffa Mary Lou
Published: September 2012

With the shift to many-core chip multiprocessors (CMPs), a critical issue is how to effectively coordinate and manage the execution of applications and hardware resources to overcome performance, power consumption, and reliability challenges stemming from hardware and application variations inherent in this new computing environment. Effective resource and application management on CMPs requires consideration of user/application/hardware-specific requirements and dynamic adaption of management decisions based on the actual run-time environment. However, designing an algorithm to manage resources and applications that can dynamically adapt based on the run-time environment is difficult because most resource and application management and monitoring facilities are only available at the operating system level. This paper presents REEact, an infrastructure that provides the capability to specify user-level management policies with dynamic adaptation. REEact is a virtual execution environment that provides a framework and core services to quickly enable the design of custom management policies for dynamically managing resources and applications. To demonstrate the capabilities and usefulness of REEact, this paper describes three case studies--each illustrating the use of REEact to apply a specific dynamic management policy on a real CMP. Through these case studies, we demonstrate that REEact can effectively and efficiently implement policies to dynamically manage resources and adapt application execution.
DVM
Authors: Ma Zhiqiang , Sheng Zhonghua , Gu Lin , Wen Liufei , Zhang Gong
Published: September 2012

As cloud-based computation becomes increasingly important, providing a general computational interface to support datacenter-scale programming has become an imperative research agenda. Many cloud systems use existing virtual machine monitor (VMM) technologies, such as Xen, VMware, and Windows Hypervisor, to multiplex a physical host into multiple virtual hosts and isolate computation on the shared cluster platform. However, traditional multiplexing VMMs do not scale beyond one single physical host, and it alone cannot provide the programming interface and cluster-wide computation that a datacenter system requires. We design a new instruction set architecture, DISA, to unify myriads of compute nodes to form a big virtual machine called DVM, and present programmers the view of a single computer where thousands of tasks run concurrently in a large, unified, and snapshotted memory space. The DVM provides a simple yet scalable programming model and mitigates the scalability bottleneck of traditional distributed shared memory systems. Along with an efficient execution engine, the capacity of a DVM can scale up to support large clusters. We have implemented and tested DVM on three platforms, and our evaluation shows that DVM has excellent performance in terms of execution time and speedup. On one physical host, the system overhead of DVM is comparable to that of traditional VMMs. On 16 physical hosts, the DVM runs 10 times faster than MapReduce/Hadoop and X10. On 256 EC2 instances, DVM shows linear speedup on a parallelizable workload.
SimTester
Authors: Yu Tingting , Srisa-an Witawas , Rothermel Gregg
Published: September 2012

In software for embedded systems, the frequent use of interrupts for timing, sensing, and I/O processing can cause concurrency faults to occur due to interactions between applications, device drivers, and interrupt handlers. This type of fault is considered by many practitioners to be among the most difficult to detect, isolate, and correct, in part because it can be sensitive to execution interleavings and often occurs without leaving any observable incorrect output. As such, commonly used testing techniques that inspect program outputs to detect failures are often ineffective at detecting them. To test for these concurrency faults, test engineers need to be able to control interleavings so that they are deterministic. Furthermore, they also need to be able to observe faults as they occur instead of relying on observable incorrect outputs.

In this paper, we introduce SimTester, a framework that allows engineers to effectively test for subtle and non-deterministic concurrency faults by providing them with greater controllability and observability. We implemented our framework on a commercial virtual platform that is widely used to support hardware/software co-designs to promote ease of adoption. We then evaluated its effectiveness by using it to test for data races and deadlocks. The result shows that our framework can be effective and efficient at detecting these faults.
Swift
Authors: Zhang Yuan , Yang Min , Zhou Bo , Yang Zhemin , Zhang Weihua , Zang Binyu
Published: September 2012

Code quality and compilation speed are two challenges to JIT compilers, while selective compilation is commonly used to trade-off these two issues. Meanwhile, with more and more Java applications running in mobile devices, selective compilation meets many problems. Since these applications always have flat execution profile and short live time, a lightweight JIT technique without losing code quality is extremely needed. However, the overhead of compiling stack-based Java bytecode to heterogeneous register-based machine code is significant in embedded devices. This paper presents a fast and effective JIT technique for mobile devices, building on a register-based Java bytecode format which is more similar to the underlying machine architecture. Through a comprehensive study on the characteristics of Java applications, we observe that virtual registers used by more than 90% Java methods can be directly fulfilled by 11 physical registers. Based on this observation, this paper proposes Swift, a novel JIT compiler on register-based bytecode, which generates native code for RISC machines. After mapping virtual registers to physical registers, the code is generated efficiently by looking up a translation table. And the code quality is guaranteed by the static compiler which is used to generate register-based bytecode. Besides, we design two lightweight optimizations and an efficient code unloader to make Swift more suitable for embedded environment. As the prevalence of Android, a prototype of Swift is implemented upon DEX bytecode which is the official distribution format of Android applications.

Swift is evaluated with three benchmarks (SPECjvm98, EmbeddedCaffeineMark3 and JemBench2) on two different ARM SOCs: S3C6410 (armv6) and OMAP3530 (armv7). The results show that Swift achieves a speedup of 3.13 over the best-performing interpreter on the selected benchmarks. Compared with the state-of-the-art JIT compiler in Android, JITC-Droid, Swift achieves a speedup of 1.42.
Facilitating inter-application interactions for OS-level virtualization
Authors: Shan Zhiyong , Wang Xin , Chiueh Tzi-cker , Meng Xiaofeng
Published: September 2012

OS-level virtualization generates a minimal start-up and run-time overhead on the host OS and thus suits applications that require both good isolation and high efficiency. However, multiple-member applications required for forming a system may need to occasionally communicate across this isolation barrier to cooperate with each other while they are separated in different VMs to isolate intrusion or fault. Such application scenarios are often critical to enterprise-class servers, HPC clusters and intrusion/fault-tolerant systems, etc. We make the first effort to support the inter-application interactions in an OS-level virtualization system without causing a significant compromise on VM isolation. We identify all interactive operations that impact inter-application interactions, including inter-process communications, application invocations, resource name transfers and application dependencies. We propose Shuttle, a novel approach for facilitating inter-application interactions within and across OS-level virtual machines. Our results demonstrate that Shuttle can correctly address all necessary inter-application interactions while providing good isolation capability to all sample applications on different versions of Windows OS.
Enhancing TCP throughput of highly available virtual machines via speculative communication
Authors: Gerofi Balazs , Ishikawa Yutaka
Published: September 2012

Checkpoint-recovery based virtual machine (VM) replication is an attractive technique for accommodating VM installations with high-availability. It provides seamless failover for the entire software stack executed in the VM regardless the application or the underlying operating system (OS), it runs on commodity hardware, and it is inherently capable of dealing with shared memory non-determinism of symmetric multiprocessing (SMP) configurations. There have been several studies aiming at alleviating the overhead of replication, however, due to consistency requirements, network performance of the basic replication mechanism remains extremely poor.,

In this paper we revisit the replication protocol and extend it with speculative communication. Speculative communication silently acknowledges TCP packets of the VM, enabling the guest's TCP stack to progress with transmission without exposing the messages to the clients before the corresponding execution state is checkpointed to the backup host. Furthermore, we propose replication aware congestion control, an extension to the guest's TCP stack that aggressively fills up the VMM's replication buffer so that speculative packets can be backed up and released earlier to the clients. We observe up to an order of magnitude improvement in bulk data transfer with speculative communication, and close to native VM network performance when replication awareness is enabled in the guest OS. We provide results of micro-, as well as application-level benchmarks.
SecondSite
Authors: Rajagopalan Shriram , Cully Brendan , O'Connor Ryan , Warfield Andrew
Published: September 2012

This paper describes the design and implementation of SecondSite, a cloud-based service for disaster tolerance. SecondSite extends the Remus virtualization-based high availability system by allowing groups of virtual machines to be replicated across data centers over wide-area Internet links. The goal of the system is to commodify the property of availability, exposing it as a simple tick box when configuring a new virtual machine. To achieve this in the wide area, we have had to tackle the related issues of replication traffic bandwidth, reliable failure detection across geographic regions and traffic redirection over a wide-area network without compromising on transparency and consistency.
Transparent dynamic instrumentation
Authors: Bruening Derek , Zhao Qin , Amarasinghe Saman
Published: September 2012

Process virtualization provides a virtual execution environment within which an unmodified application can be monitored and controlled while it executes. The provided layer of control can be used for purposes ranging from sandboxing to compatibility to profiling. The additional operations required for this layer are performed clandestinely alongside regular program execution. Software dynamic instrumentation is one method for implementing process virtualization which dynamically instruments an application such that the application's code and the inserted code are interleaved together. DynamoRIO is a process virtualization system implemented using software code cache techniques that allows users to build customized dynamic instrumentation tools. There are many challenges to building such a runtime system. One major obstacle is transparency. In order to support executing arbitrary applications, DynamoRIO must be fully transparent so that an application cannot distinguish between running inside the virtual environment and native execution. In addition, any desired extra operations for a particular tool must avoid interfering with the behavior of the application.

Transparency has historically been provided on an ad-hoc basis, as a reaction to observed problems in target applications. This paper identifies a necessary set of transparency requirements for running mainstream Windows and Linux applications. We discuss possible solutions to each transparency issue, evaluate tradeoffs between different choices, and identify cases where maintaining transparency is not practically solvable. We believe this will provide a guideline for better design and implementation of transparent dynamic instrumentation, as well as other similar process virtualization systems using software code caches.
Adding dynamically-typed language support to a statically-typed language compiler
Authors: Ishizaki Kazuaki , Ogasawara Takeshi , Castanos Jose , Nagpurkar Priya , Edelsohn David , Nakatani Toshio
Published: September 2012

Applications written in dynamically typed scripting languages are increasingly popular for Web software development. Even on the server side, programmers are using dynamically typed scripting languages such as Ruby and Python to build complex applications quickly. As the number and complexity of dynamically typed scripting language applications grows, optimizing their performance is becoming important. Some of the best performing compilers and optimizers for dynamically typed scripting languages are developed entirely from scratch and target a specific language. This approach is not scalable, given the variety of dynamically typed scripting languages, and the effort involved in developing and maintaining separate infrastructures for each. In this paper, we evaluate the feasibility of adapting and extending an existing production-quality method-based Just-In-Time (JIT) compiler for a language with dynamic types. Our goal is to identify the challenges and shortcomings with the current infrastructure, and to propose and evaluate runtime techniques and optimizations that can be incorporated into a common optimization infrastructure for static and dynamic languages. We discuss three extensions to the compiler to support dynamically typed languages: (1) simplification of control flow graphs, (2) mapping of memory locations to stack-allocated variables, and (3) reduction of runtime overhead using language semantics. We also propose four new optimizations for Python in (2) and (3). These extensions are effective in reduction of compiler working memory and improvement of runtime performance. We present a detailed performance evaluation of our approach for Python, finding an overall improvement of 1.69x on average (up to 2.74x) over our JIT compiler without any optimization for dynamically typed languages and Python.
Block storage virtualization with commodity secure digital cards
Authors: Tuch Harvey , Laplace Cyprien , Barr Kenneth C. , Wu Bi
Published: September 2012

Smartphones, tablets and other mobile platforms typically accommodate bulk data storage with low-cost, FAT-formatted Secure Digital cards. When one uses a mobile device to run a full-system virtual machine (VM), there can be a mismatch between 1) the VM's I/O mixture, security and reliability requirements and 2) the properties of the storage media available for VM block storage and checkpoint images. To resolve this mismatch, this paper presents a new VM disk image format called the Logging Block Store (LBS). After motivating the need for a new format, LBS is described in detail with experimental results demonstrating its efficacy. As a result of this work, recommendations are made for future optimizations throughout the stack that may simplify and improve the performance of storage virtualization systems on mobile platforms.
Protecting applications against TOCTTOU races by user-space caching of file metadata
Authors: Payer Mathias , Gross Thomas R.
Published: September 2012

Time Of Check To Time Of Use (TOCTTOU) race conditions for file accesses in user-space applications are a common problem in Unix-like systems. The mapping between filename and inode and device is volatile and can provide the necessary preconditions for an exploit. Applications use filenames as the primary attribute to identify files but the mapping between filenames and inode and device can be changed by an attacker.

DynaRace is an approach that protects
unmodified
applications from file-based TOCTTOU race conditions. DynaRace uses a transparent mapping cache that keeps additional state and metadata for each accessed file in the application. The combination of file state and the current system call type are used to decide if (i) the metadata is updated or (ii) the correctness of the metadata is enforced between consecutive system calls.

DynaRace uses user-mode path resolution internally to resolve individual file atoms. Each file atom is verified or updated according to the associated state in the mapping cache. More specifically, DynaRace protects against race conditions for all file-based system calls, by replacing the unsafe system calls with a set of safe system calls that utilize the mapping cache. The system call is executed only if the state transition is allowed and the information in the mapping cache matches.

DynaRace deterministically solves the problem of file-based race conditions for unmodified applications and removes an attacker's ability to exploit the TOCTTOU race condition. DynaRace detects injected alternate inode and device pairs and terminates the application.
CAPRI
Authors: Rhu Minsoo , Erez Mattan
Published: September 2012

Wide SIMD-based GPUs have evolved into a promising platform for running general purpose workloads. Current programmable GPUs allow even code with irregular control to execute well on their SIMD pipelines. To do this, each SIMD lane is considered to execute a logical thread where hardware ensures that control flow is accurate by automatically applying masked execution. The masked execution, however, often degrades performance because the issue slots of masked lanes are wasted. This degradation can be mitigated by dynamically compacting multiple unmasked threads into a single SIMD unit. This paper proposes a fundamentally new approach to branch compaction that avoids the unnecessary synchronization required by previous techniques and that only stalls threads that are likely to benefit from compaction. Our technique is based on the compaction-adequacy predictor (CAPRI). CAPRI dynamically identifies the compaction-effectiveness of a branch and only stalls threads that are predicted to benefit from compaction. We utilize a simple single-level branch-predictor inspired structure and show that this simple configuration attains a prediction accuracy of 99.8% and 86.6% for non-divergent and divergent workloads, respectively. Our performance evaluation demonstrates that CAPRI consistently outperforms both the baseline design that never attempts compaction and prior work that stalls upon all divergent branches.
iGPU
Authors: Menon Jaikrishnan , De Kruijf Marc , Sankaralingam Karthikeyan
Published: September 2012

Since the introduction of fully programmable vertex shader hardware, GPU computing has made tremendous advances. Exception support and speculative execution are the next steps to expand the scope and improve the usability of GPUs. However, traditional mechanisms to support exceptions and speculative execution are highly intrusive to GPU hardware design. This paper builds on two related insights to provide a unified lightweight mechanism for supporting exceptions and speculation on GPUs.

First, we observe that GPU programs can be broken into code regions that contain little or no live register state at their entry point. We then also recognize that it is simple to generate these regions in such a way that they are idempotent, allowing their entry points to function as program recovery points and enabling support for exception handling, fast context switches, and speculation, all with very low overhead. We call the architecture of GPUs executing these idempotent regions the iGPU architecture. The hardware extensions required are minimal and the construction of idempotent code regions is fully transparent under the typical dynamic compilation framework of GPUs. We demonstrate how iGPU exception support enables virtual memory paging with very low overhead (1% to 4%), and how speculation support enables circuit-speculation techniques that can provide over 25% reduction in energy.
Branch regulation
Authors: Kayaalp Mehmet , Ozsoy Meltem , Abu-Ghazaleh Nael , Ponomarev Dmitry
Published: September 2012

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.
Side-channel vulnerability factor
Authors: Demme John , Martin Robert , Waksman Adam , Sethumadhavan Simha
Published: September 2012

There have been many attacks that exploit side-effects of program execution to expose secret information and many proposed countermeasures to protect against these attacks. However there is currently no systematic, holistic methodology for understanding information leakage. As a result, it is not well known how design decisions affect information leakage or the vulnerability of systems to side-channel attacks.

In this paper, we propose a metric for measuring information leakage called the Side-channel Vulnerability Factor (SVF). SVF is based on our observation that all side-channel attacks ranging from physical to microarchitectural to software rely on recognizing leaked execution patterns. SVF quantifies patterns in attackers' observations and measures their correlation to the victim's actual execution patterns and in doing so captures systems' vulnerability to side-channel attacks.

In a detailed case study of on-chip memory systems, SVF measurements help expose unexpected vulnerabilities in whole-system designs and shows how designers can make performance-security trade-offs. Thus, SVF provides a quantitative approach to secure computer architecture.
Inspection resistant memory
Authors: Valamehr Jonathan , Chase Melissa , Kamara Seny , Putnam Andrew , Shumow Dan , Vaikuntanathan Vinod , Sherwood Timothy
Published: September 2012

The ability to safely keep a secret in memory is central to the vast majority of security schemes, but storing and erasing these secrets is a difficult problem in the face of an attacker who can obtain unrestricted physical access to the underlying hardware. Depending on the memory technology, the very act of storing a 1 instead of a 0 can have physical side effects measurable even after the power has been cut. These effects cannot be hidden easily, and if the secret stored on chip is of sufficient value, an attacker may go to extraordinary means to learn even a few bits of that information. Solving this problem requires a new class of architectures that measurably increase the difficulty of physical analysis. In this paper we take a first step towards this goal by focusing on one of the backbones of any hardware system: on-chip memory. We examine the relationship between security, area, and efficiency in these architectures, and quantitatively examine the resulting systems through cryptographic analysis and microarchitectural impact. In the end, we are able to find an efficient scheme in which, even if an adversary is able to inspect the value of a stored bit with a probabilistic error of only 5%, our system will be able to prevent that adversary from learning any information about the original un-coded bits with 99.9999999999% probability.
Tolerating process variations in nanophotonic on-chip networks
Authors: Xu Yi , Yang Jun , Melhem Rami
Published: September 2012

Nanophontonic networks, a potential candidate for future networks on-chip, have been challenged for their reliability due to several device-level limitations. One of the main issues is that fabrication errors (a.k.a. process variations) can cause devices to malfunction, rendering communication unreliable. For example, microring resonator, a preferred optical modulator device, may not resonate at the designated wavelength under process variations (PV), leading to communication errors and bandwidth loss.

This paper proposes a series of solutions to the wavelength drifting problem of microrings and subsequent bandwidth loss problem of an optical network, due to PV. The objective is to maximize network bandwidth through proper arrangement among microrings and wavelengths with minimum power requirement. Our arrangement, called "MinTrim", solves this problem using simple integer linear programming, adding supplementary microrings and allowing flexible assignment of wavelengths to network nodes as long as the resulting network presents maximal bandwidth. Each step is shown to improve bandwidth provisioning with lower power requirement. Evaluations on a sample network show that a baseline network could lose more than 40% bandwidth due to PV. Such loss can be recovered by MinTrim to produce a network with 98.4% working bandwidth. In addition, the power required in arranging microrings is 39% lower than the baseline. Therefore, MinTrim provides an efficient PV-tolerant solution to improving the reliability of on-chip phontonics.
Enhancing effective throughput for transmission line-based bus
Authors: Carpenter Aaron , Hu Jianyun , Kocabas Ovunc , Huang Michael , Wu Hui
Published: September 2012

Main-stream general-purpose microprocessors require a collection of high-performance interconnects to supply the necessary data movement. The trend of continued increase in core count has prompted designs of packet-switched network as a scalable solution for future-generation chips. However, the cost of scalability can be significant and especially hard to justify for smaller-scale chips. In contrast, a circuit-switched bus using transmission lines and corresponding circuits offers lower latencies and much lower energy costs for smaller-scale chips, making it a better choice than a full-blown network-on-chip (NoC) architecture. However, shared-medium designs are perceived as only a niche solution for small- to medium-scale chips.

In this paper, we show that there are many low-cost mechanisms to enhance the effective throughput of a bus architecture. When a handful of highly cost-effective techniques are applied, the performance advantage of even the most idealistically configured NoCs becomes vanishingly small. We find transmission line-based buses to be a more compelling interconnect even for large-scale chip-multiprocessors, and thus bring into doubt the centrality of packet switching in future on-chip interconnect.
A case for random shortcut topologies for HPC interconnects
Authors: Koibuchi Michihiro , Matsutani Hiroki , Amano Hideharu , Hsu D. Frank , Casanova Henri
Published: September 2012

As the scales of parallel applications and platforms increase the negative impact of communication latencies on performance becomes large. Fortunately, modern High Performance Computing (HPC) systems can exploit low-latency topologies of high-radix switches. In this context, we propose the use of random shortcut topologies, which are generated by augmenting classical topologies with random links. Using graph analysis we find that these topologies, when compared to non-random topologies of the same degree, lead to drastically reduced diameter and average shortest path length. The best results are obtained when adding random links to a ring topology, meaning that good random shortcut topologies can easily be generated for arbitrary numbers of switches. Using flit-level discrete event simulation we find that random shortcut topologies achieve throughput comparable to and latency lower than that of existing non-random topologies such as hypercubes and tori. Finally, we discuss and quantify practical challenges for random shortcut topologies, including routing scalability and larger physical cable lengths.
Watchdog
Authors: Nagarakatte Santosh , Martin Milo M. K. , Zdancewic Steve
Published: September 2012

Languages such as C and C++ use unsafe manual memory management, allowing simple bugs (i.e., accesses to an object after deallocation) to become the root cause of exploitable security vulnerabilities. This paper proposes Watchdog, a hardware-based approach for ensuring safe and secure manual memory management. Inspired by prior software-only proposals, Watchdog generates a unique identifier for each memory allocation, associates these identifiers with pointers, and checks to ensure that the identifier is still valid on every memory access. This use of identifiers and checks enables Watchdog to detect errors even in the presence of reallocations. Watchdog stores these pointer identifiers in a disjoint shadow space to provide comprehensive protection and ensure compatibility with existing code. To streamline the implementation and reduce runtime overhead: Watchdog (1) uses micro-ops to access metadata and perform checks, (2) eliminates metadata copies among registers via modified register renaming, and (3) uses a dedicated metadata cache to reduce checking overhead. Furthermore, this paper extends Watchdog's mechanisms to detect bounds errors, thereby providing full hardware-enforced memory safety at low overheads.
The yin and yang of power and performance for asymmetric hardware and managed software
Authors: Cao Ting , Blackburn Stephen M , Gao Tiejun , McKinley Kathryn S
Published: September 2012

On thehardwareside, asymmetric multicore processors present software with the challenge and opportunity of optimizing in two dimensions: performance and power. Asymmetric multicore processors (AMP) combine general-purposebig(fast, high power) cores andsmall(slow, low power) cores to meet power constraints. Realizing their energy efficiency opportunity requires workloads with differentiated performance and power characteristics.

On the software side, managed workloads written in languages such as C#, Java, JavaScript, and PHP are ubiquitous. Managed languages abstract over hardware using Virtual Machine (VM) services (garbage collection, interpretation, and/or just-in-time compilation) that together impose substantial energy and performance costs, ranging from 10% to over 80%. We show that these services manifest a differentiated performance and power workload. To differing degrees, they are parallel, asynchronous, communicate infrequently, and are not on the application?s critical path.

We identify a synergy between AMP and VM services that we exploit to attack the 40% average energy overhead due to VM services. Using measurements and very conservative models, we show that adding small cores tailored for VM services should deliver, at least, improvements in performance of 13%, energy of 7%, and performance per energy of 22%. Theyinof VM services is overhead, but it meets theyangof small cores on an AMP. Theyinof AMP is exposed hardware complexity, but it meets theyangof abstraction in managed languages. VM services fulfill the AMP requirement for an asynchronous, non-critical, differentiated, parallel, and ubiquitous workload to deliver energy efficiency. Generalizing this approach beyond system software to applications will require substantially more software and hardware investment, but these results show the potential energy efficiency gains are significant.
VRSync
Authors: Miller Timothy N. , Thomas Renji , Pan Xiang , Teodorescu Radu
Published: September 2012

Power consumption is a primary concern for microprocessor designers. Lowering the supply voltage of processors is one of the most effective techniques for improving their energy efficiency. Unfortunately, low-voltage operation faces multiple challenges going forward. One such challenge is increased sensitivity to voltage fluctuations, which can trigger so-called "voltage emergencies" that can lead to errors. These fluctuations are caused by abrupt changes in power demand, triggered by processor activity variation as a function of workload.

This paper examines the effects of voltage fluctuations on future many-core processors. With the increase in the number of cores in a chip, the effects of chip-wide activity fluctuation -- such as that caused by global synchronization in multithreaded applications -- overshadow the effects of core-level workload variability. Starting from this observation, we developed VRSync, a novel synchronization methodology that uses emergency-aware scheduling policies that reduce the slope of load fluctuations, eliminating emergencies. We show that VRSync is very effective at eliminating emergencies, allowing voltage guardbands to be significantly lowered, which reduces energy consumption by an average of 33%.