Automatic validation for binary translation

Binary translation is an important technique for porting programs as it allows binary code for one platform to execute on another. It is widely used in virtual machines and emulators. However, implementing a correct (and efficient) binary translator is still very challenging because many delicate details must be handled smartly. Manually identifying mistranslated instructions in an application program is difficult, especially when the application is large. Therefore, automatic validation tools are needed urgently to uncover hidden problems in a binary translator. We developed a new validation tool for binary translators. In our validation tool, the original binary code and the translated binary code run simultaneously. Both versions of the binary code continuously send their architecture states and the stored values, which are the values stored into memory cells, to a third process, the validator. Since most mistranslated instructions will result in wrong architecture states during execution, our validator can catch most mistranslated instructions emitted by a binary translator by comparing the corresponding architecture states. Corresponding architecture states may differ due to (1) translation errors, (2) different (but correct) memory layouts, and (3) return values of certain system calls. The need to differentiate the three sources of differences makes comparing architecture states very difficult, if not impossible. In our validator, we take special care to make memory layouts exactly the same and make the corresponding system calls always return exactly the same values in the original and in the translated binaries. Therefore, any differences in the corresponding architecture states indicate mistranslated instructions emitted by the binary translator. Besides solving the architecture-state-comparison problems, we also propose several methods to speed up the automatic validation. The first is the validation-block method, which reduces the number of validations while keeping the accuracy of instruction-level validation. The second is quick validation, which provides extremely fast validation at the expense of less accurate error information. Our validator can be applied to different binary translators. In our experiment, the validator has successfully validated programs translated by static, dynamic, and hybrid binary translators.     

Welcome to the opportunities of binary translation

A new processor architecture poses significant financial risk to hardware and software developers alike, so both have a vested interest in easily porting code from one processor to another. Binary translation offers solutions for automatically converting executable code to run on new architectures without recompiling the source code     

Background optimization in full system binary translation

Binary translation and dynamic optimization are widely used to provide compatibility between legacy and promising upcoming architectures on the level of executable binary codes. Dynamic optimization is one of the key contributors to dynamic binary translation system performance. At the same time it can be a major source of overhead, both in terms of CPU cycles and whole system latency, as long as optimization time is included in the execution time of the application under translation. One of the solutions that allow to eliminate dynamic optimization overhead is to perform optimization simultaneously with the execution, in a separate thread. In the paper we present implementation of this technique in full system dynamic binary translator. For this purpose, an infrastructure for multithreaded execution was implemented in binary translation system. This allowed running dynamic optimization in a separate thread independently of and concurrently with the main thread of execution of binary codes under translation. Depending on the computational resources available, this is achieved whether by interleaving the two threads on a single processor core or by moving optimization thread to an underutilized processor core. In the first case the latency introduced to the system by a computational intensive dynamic optimization is reduced. In the second case overlapping of execution and optimization threads also results in elimination of optimization time from the total execution time of original binary codes.     

UQBT: adaptable binary translation at low cost

Developments in the semiconductor industry have made possible smaller and faster processors for general-purpose computing, portable devices, multipurpose appliances, and system-on-chip designs. Binary translation offers a quick, inexpensive way to migrate software from one processor to another. Although binary-translation techniques are still in their infancy compared to their compiler counterparts, engineers have been using them for 15 years. Just as engineers build compilers partly on the basis of specifications, the authors are developing the University of Queensland Binary Translator (UQBT) on the basis of machine specifications and properties of machines and operating systems. This static binary-translation framework supports various processors, including complex-instruction-set computers (CISC), reduced-instruction-set computers (RISC), and stack-based machines. The authors describe the UQBT framework and discuss their observations while using it to instantiate six different translators across Sun Sparc, Intel Pentium, and Java virtual-machine architectures     

Light-weight kernel instrumentation framework using dynamic binary translation

Mobile platforms such as Android and iOS, which are based on typical operating systems, have been widely adopted in various computing devices from smart phones even to smart TVs. Along with this, the necessity of kernel instrumentation framework has also grown up for efficient development and debugging of a kernel itself and its components. Although the existing approaches are providing some information about the kernel state including physical register value and primitive memory map, it is hard for the developers to understand and exploit the information. Moreover, the excessive analysis overhead in the existing approach makes them impractical to be used in real systems. Meanwhile, there have been a few studies on analyzing the user-level applications using dynamic binary translation and they are now widely used. In this paper, by extending this idea of dynamic binary translation for user-level applications to the kernel, we propose a new dynamic kernel instrumentation framework. Our framework focuses on the modules such as device drivers, rather than the kernel itself, since the modules comprise a large portion of OS development. Because of the frequent execution of kernel modules, the dynamic kernel instrumentation framework should guarantee the quality of the translated target code. However, costly optimizations to achieve high execution performance are rather harmful to the overall performance. Therefore, in order to improve performance of both translations, we suggest light-weight translator based on pseudo-machine instruction representation and tabular-base translation instead of typical intermediate representation. We implement our framework on Linux system, and our experimental evaluations show that it could quite effectively instrument the target with nominal overhead.     

Dynamic memory paravirtualization transparent to guest OS

This paper introduces dynamic paravirtualization, which imitates paravirtualization and aims at reducing VM exits of full virtualization with hardware support. In dynamic paravirtualization, VMM (virtual machine monitor) dynamically monitors and replaces the hot instructions, which cause most VM exits. It is transparent to the guest OS such that the legacy OSes can benefit from this optimization. Our study focuses on reducing the overhead of memory virtualization—dynamic memory paravirtualization (DMP). We ...     

Dynamic weighted binary search trees

Summary We present an algorithm which optimizes a weighted binary tree after an insertion or deletion. The resulting tree is nearly optimal. The algorithm needs O(n) space. In the case of an insertion the expected number of operations is equal to or less than the height of the tree. All results presented in this paper can also be found in [15].     

静态二进制翻译中间接过程调用恢复技术研究

间接过程调用的恢复问题是静态二进制翻译中的难点之一。针对使用c后端的静态二进制翻译框架,提出并实现间接过程调用恢复方法,该方法结合代码间隙分析,在后端c代码生成过程中插入映射源过程地址到目标机过程地址的代码。相对于使用解释器的方法,该方法具有实现简洁、在目标机上运行速度更快的优点。     

Dynamic angle selection in binary tomography

In this paper, we present an algorithm for the dynamic selection of projection angles in binary tomography. Based on the information present in projections that have already been measured, a new projection angle is computed, which aims to maximize the information gained by adding this projection to the set of measurements. The optimization model used for angle selection is based on a characterization of solutions of the binary reconstruction problem, and a related definition of information gain. From this formal model, an algorithm is obtained by several approximation steps. Results from a series of simulation experiments demonstrate that the proposed angle selection scheme is indeed capable of finding angles for which the reconstructed image is much more accurate than for the standard angle selection scheme.     

SINOF: A dynamic-static combined framework for dynamic binary translation

Dynamic binary translation (DBT) is an important technique in virtualization, and in migrating legacy binaries to platforms based on a new architecture. However, poor profile information limits the process of optimization at runtime, so the DBT system may suffer from substantial overhead. In this paper, we design and implement a static-integrated optimization framework (SINOF) to improve the runtime performance for DBT. Combining static and dynamic approaches can greatly reduce the overhead of optimizing, profiling and translating for any program that runs repeatedly. Under this framework, once the source image has been executed, the profile information and target code will be saved in a software cache, and will be available for future runs. In the static phase, the saved code is analyzed and optimized based on the information collected in the previous run. Especially, we reorganize the code layout of the software cache. Experimental results show that the proposed framework can reduce run time by more than 30% on average compared to the original versions of DBT that the framework is based on.     

动态二进制翻译的多线程并行优化研究

为了充分利用多核CPU来实现动态二进制翻译的并行化,研究了用多线程将翻译阶段和执行阶段并行优化的方法,提供了并行化系统的程序流程。并根据翻译与执行的时序及相关性,设计实现了一种超前翻译算法,它能够有效预测程序的执行路径,为翻译过程提供导向作用。实验结果表明,该优化方法提高了翻译缓存中基本块的命中率,使执行阶段尽量不被中断,进而提升了执行效率。     

IA-64二进制翻译中跳转表恢复技术

基于IA-64体系结构下二进制翻译系统,本文提出了应用过程内静态切片技术恢复索引跳转中跳转表以及目标地址的解决方案.并通过在IA-64体系结构上对C和C++编译器产生的代码进行测试,表明通过该技术可以很好的解决二进制翻译中跳转表的恢复问题,提高二进制解码的覆盖率.     

Dynamic translation for virtual machine based traffic simulation

For virtual machine based traffic simulation platforms, the paper proposes a software framework that performs trace-based dynamic translation. Through monitoring the runtime execution status of bytecodes and translating frequently executed bytecodes, also known as hot spots, into equivalent native machine codes, the framework considerably improves the performance of virtual machine based traffic simulation platforms up to ten times or more, as the experiments showed. For the first time, the presented work clearly exhibits that a seamless combination of the two technologies – dynamic translation and virtual machine could lead to a new generation of applicable traffic simulation platforms. Such a platform not only offers high flexibility in terms of traffic model simulation, but also preserves the ability of conducting numerical computation-intensive simulations generally found in real-life industrial projects.     

Dynamic scattering in binary compensate cholesteric mixture with pleochroic dye added

The paper reports measurements of optical transmittance and of I–V characteristic performed simultaneously on the same host mixture ChCl + LCh 74:26% molar in which was introduced another azocumilphenol derivative from paraphenetidine (Dpf). The optical and electrical measurements were interpreted by correlating them with the microstructural aspects recorded by a polarizing microscope in the same conditions of field and temperature.     

简述Linux构建校园透明防火墙与透明代理

网络安全离不开防火墙的保护,深入地了解防火墙的原理、设置以及维护是大多电脑网络爱好者的目标,本文就围绕Linux环境下架设防火墙展开。     

Computing occluding and transparent motions

Computing the motions of several moving objects in image sequences involves simultaneous motion analysis and segmentation. This task can become complicated when image motion changes significantly between frames, as with camera vibrations. Such vibrations make tracking in longer sequences harder, as temporal motion constancy cannot be assumed. The problem becomes even more difficult in the case of transparent motions.A method is presented for detecting and tracking occluding and transparent moving objects, which uses temporal integration without assuming motion constancy. Each new frame in the sequence is compared to a dynamic internal representation image of the tracked object. The internal representation image is constructed by temporally integrating frames after registration based on the motion computation. The temporal integration maintains sharpness of the tracked object, while blurring objects that have other motions. Comparing new frames to the internal representation image causes the motion analysis algorithm to continue tracking the same object in subsequent frames, and to improve the segmentation.     

A transparent and adaptive reconfigurable system

In the current scenario, where computer systems are characterized by a high diversity of applications coexisting in a single device, and with the stagnation in frequency scaling because of the excessive power dissipation, reconfigurable systems have already proven to be very effective. However, they all present two major drawbacks, which are addressed by this work: lack of transparency (the need for special tools or compilers that changes the original code) and no ability to adapt to applications with different behaviors and characteristics, so significant gains are achieved only in very specific data stream oriented applications. Therefore, this work proposes the Dynamic Instruction Merging (DIM), a Binary Translation mechanism responsible for transforming sequences of instructions into a coarse-grained array configuration at run-time, in a totally transparent process, with support to speculative execution. The proposed system does not impose any kind of modification to the source or binary codes, so full binary compatibility is maintained. Moreover, it can optimize any application, even those that do not present specific kernels for optimization. DIM presents, on average, 2.7 times of performance gains and 2.35 times of energy savings over a MIPS processor, and a higher IPC than an out-of-order superscalar processor, running the MIBench benchmark set.