Binary translators, which translate the binary executables from one instruction set to another, are useful tools. Indirect branches are one of the key factors that affect the efficiency of binary translators. In the previous research, our lab developed an LLVM-based binary translation framework, called Rabbit. Rabbit introduces novel optimisations: platform-dependent hyperchaining and platform-independent hyperchaining for improving the emulation of the indirect branch instructions. Indirect branch instructions may have several destinations, and these destinations are not known until runtime. Both platform-independent and platform-dependent hyperchaining establish a search table for each indirect branch instruction to record the visited branch destinations at runtime. In this work, we focus on the translation from AArch64 binary to RISC-V binary and further develop the profile-guided optimisation for indirect branch, which collects runtime information, including branch destinations and execution frequency of each destination for each indirect branch instruction, and then use the information to improve hyperchaining (i.e. accelerate the process of finding the branch destination). The profile-guided optimisation can be divided to profile-guided platform-independent hyperchaining and profile-guided platform-dependent hyperchaining. We finally use SPEC CPU 2006 CINT benchmark to evaluate the optimisations. The experiment results indicate that compared with (1) no chaining, (2) platform-independent hyperchaining and (3) platform-dependent hyperchaining, profile-guided platform-independent hyperchaining provides 1.123×, 1.066× and 1.098× speedup respectively. Similarly, profile-guided platform-dependent hyperchaining achieves 1.106×, 1.047× and 1.083× speedup with respect to the above three configurations, respectively.

Summary OpenACC is a directive‐based programming model which allows programmers to write graphic processing unit (GPU) programs by simply annotating parallel loops. However, OpenACC has poor support for irregular nested parallel loops, which are natural choices to express nested parallelism. We propose PFACC, a programming model similar to OpenACC. PFACC directives can be used to annotate parallel loops and to guide data movement between different levels of memory hierarchy. Parallel loops can be arbitrarily nested or be placed inside functions that would be (possibly recursively) called in other parallel loops. The PFACC translator translates C programs with PFACC directives into CUDA programs by inserting runtime iteration‐sharing and memory allocation routines. The PFACC runtime iteration‐sharing routine is a two‐level mechanism. Thread blocks dynamically organize loop iterations into batches and execute the batches in a depth‐first order. Different thread blocks share iterations among one another with an iteration‐stealing mechanism. PFACC generates CUDA programs with reasonable memory usage because of the depth‐first execution order. The two‐level iteration‐sharing mechanism is implemented purely in software and fits well with the CUDA thread hierarchy. Experiments show that PFACC outperforms CUDA dynamic parallelism in terms of performance and code size on most benchmarks.

Code discovery has been a main challenge for static binary translation, especially when the source instruction set architecture has variable-length instructions, such as the x86 architectures. Due to embedded data such as PC (program counter)-relative data, jump tables, or paddings in the code section, a binary translator may be misled to translate data as instructions. For variable-length instructions, once a piece of data is mis-translated as instructions, decoding subsequent bytes could also go wrong. We are concerned with static binary translation for the very popular Advanced RISC Machine (ARM) architectures. Although ARM is considered a reduced instruction set computer architecture, it does allow the mix of 32-bit (ARM) instructions and 16-bit (Thumb) instructions in the same executables. In addition to different instruction lengths, the ARM and Thumb instructions are located at 4-byte or 2-byte aligned addresses, respectively. Furthermore, because ARM and Thumb instructions share the same encoding space, a 4-byte word could sometimes be decoded as one ARM instruction or two Thumb instructions. The correct decoding of this 4-byte word is actually determined at runtime by the least-significant bit of the program counter. For unstripped binaries, the mapping symbols can be used to identify ARM code regions and Thumb code regions. However, for stripped binaries, such mapping symbols are unavailable. We propose a novel solution to statically translate stripped ARM/Thumb mixed executables. Our solution is implemented in a static binary translator. The binary translator further generates multiple versions of translated code for the code regions whose types cannot be determined with our solution. One of the code versions is selected during runtime. The binary translator also includes a series of analyses that enable the removal of most useless code versions. Based on the experimental results on stripped ARM/Thumb mixed binaries in the SPEC2006 and Embedded Microprocessor Benchmark Consortium (EEMBC) benchmark suites, our static binary translator achieves impressive performance when migrating them to run on x86 machines and the space overhead is no more than 10%.

Supporting irregular nested parallelism on modern GPUs requires much effort. One should distribute the parallel tasks evenly while preserving reasonable memory usage. Moreover, the task distribution should also fit the thread hierarchy of the underlying GPU to fully exploit its computing power. We propose partial flattening, an automatic code transformation which translates annotated C programs to CUDA kernels. Thread blocks are treated as flat SIMT processors. Iterations are dynamically organized into batches. Batches are executed in a sequential (depth-first) order. A kernel is treated as multiple independent SIMT processors with an additional task-stealing mechanism. Partial flattening allows easy expression of nested parallelism and synchronization by annotating nested parallel loops or parallel-recursive calls, while preserving reasonable memory usage by the depth-first execution order. Our 2-level task distribution scheme does not need special hardware support, and fits well with the CUDA thread hierarchy. Experiments show that partial flattening outperforms NESL significantly in most benchmarks, and obtains 2.15x and 67x speedup over CUDA dynamic parallelism in Quicksort and the Bron-Kerbosch algorithm, respectively.

Summary Binary translation attempts to emulate one instruction set with another on the same or different platforms. The important technique is widely used in modern software. Vector and floating‐point instructions are widely used in many applications, including multimedia, graphics, and gaming. Although these instructions are usually simulated with software in a binary translator, it is important to support them such that the host single‐instruction, multiple‐data (SIMD) and floating‐point hardware are efficiently used during emulation. We report our design and implementation of the emulation of ARM Neon and vector floating point (VFP) instructions in the machine‐code‐to‐low‐level‐virtual‐machine (MC2LLVM) binary translator. The Neon and VFP instructions are first translated into carefully chosen sequences of LLVM intermediate representation (IR), and later, the IR sequences are optimized and translated into the host native binary by the existing LLVM backend. Because MC2LLVM makes use of the vector and floating‐point types in LLVM IR, the generated host native binary can take full advantage of the vector and floating‐point functional units, if present, of the host machine. To be fully compliant with Neon and VFP instruction sets, all the features are supported, including the flush‐to‐zero mode, default not a number mode, and floating‐point exceptions. The experimental results show that code generated by MC2LLVM with the Neon and VFP extensions achieves an average speedup of 1.174× in SPEC 2006 benchmark suites and exhibits a floating‐point throughput of 12.05× in LINPACK, compared with code generated by MC2LLVM without the Neon and VFP extensions. Furthermore, MC2LLVM is 3.36× faster than QEMU for processing Neon/VFP instructions. Copyright © 2016 John Wiley & Sons, Ltd.

In the and-or scheduling model, a project consists of several tasks. Each task has a duration attribute. A task can be performed only when all of its requirements are satisfied. After a task is completed, more requirements become satisfied. A characteristic of the AOscheduling projects is that a requirement may be satisfied in several ways. Several questions concerning AOscheduling might be interesting, including whether the project can be completed, the earliest time a project can be completed, the minimal number of processors needed to complete the project, and assigning tasks to processors, etc. We use Petri nets and segment graphs to analyze AOscheduling projects.

Machines designed with new but incompatible Instruction Set Architecture (ISA) may lack proper applications. Binary translation can address this incompatibility by migrating applications from one legacy ISA to a new one, although binary translation has problems such as code discovery for variable-length ISA and code location issues for handling indirect branches. Dynamic Binary Translation (DBT) has been widely adopted for migrating applications since it avoids those problems. Static Binary Translation (SBT) is a less general solution and has not been actively researched. However, SBT performs more aggressive optimizations, which could yield more compact code and better code quality. Applications translated by SBT can consume less memory, processor cycles, and power than DBT and can be started more quickly. These advantages are even more critical for embedded systems than for general systems. In this article, we designed and implemented a new SBT tool, called LLBT, which translates ARM instructions into LLVM IRs and then retargets the LLVM IRs to various ISAs, including ×86, ×86--64, ARM, and MIPS. LLBT leverages two important functionalities from LLVM: comprehensive optimizations and retargetability. More importantly, LLBT solves the code discovery problem for ARM/Thumb binaries without resorting to interpretation. LLBT also effectively reduced the size of the address mapping table, making SBT a viable solution for embedded systems. Our experiments based on the EEMBC benchmark suite show that the LLBT-generated code can run more than 6× and 2.3× faster on average than emulation with QEMU and HQEMU, respectively.

Code discovery has been a main challenge for static binary translation, especially when the source ISA (Instruction Set Architecture) has variable-length instructions, such as the X86 architectures. Due to embedded data such as PC-relative data, jump tables, or paddings in the code section, a binary translator may be misled to translate data as instructions. With variable length instructions, once data is mis-translated as instructions, subsequent decoding of instructions could be wrong. This paper concerns static binary translation for the ARM architectures, which dominate the embedded-system market. Although ARM is considered RISC (Reduced Instruction Set Computing) in many aspects of processors, it does allow the mix of 32-bit instructions (ARM) with 16-bit instructions (Thumb) in the ARM/Thumb mixed executables. Since the instruction lengths of ARM and Thumb are not equal, the locations of the instructions could be 4-byte or 2-byte aligned addresses, respectively. Furthermore, because ARM and Thumb instructions share encoding space, a 4-byte word could be decoded as one ARM instruction or two Thumb instructions. The correct decoding of this 4-byte word is actually determined at run time by the least significant bit of the program counter. For unstripped binaries, mapping symbols can be used to identify ARM code regions and Thumb code regions. However, for stripped binaries, such mapping symbols are not available to assist translation. We have proposed a novel solution to statically translate the stripped executables for the ARM/Thumb mixed ISA. Our static binary translator includes a translation pass which guarantees the correctness of the translated executable by generating multiple versions of translated code for runtime selection. The binary translator also includes a series of optimization analyses which discover and remove most of the code generated in the baseline translation. Based on the SPEC2006 benchmark suite, stripped ARM/Thumb mixed binaries translated by our static binary translator achieve good performance with only 25% of code size increase.

Lack of applications has always been a serious concern for designing machines with a new but incompatible ISA. To address this concern, binary translation is one common technique to migrate applications from one legacy ISA to new ones. In the past, dynamic binary translation (DBT) has been more widely adopted for migrating applications since it avoids some challenging problems for binary translation such as code discovery for variable length ISA and code location issues for handling indirect branches. Static binary translation (SBT) is usually regarded as a less general solution and has not been actively researched on. However, SBT has advantages of performing more aggressive optimizations, which could yield more compact code and greater code quality. In general, SBT translated applications are likely to consume less memory, processor cycles and power, and can be started more quickly. All the above advantages are more critical for embedded systems than for general systems. Therefore, we believe that even though SBT is not as general as DBT, it has a unique role to play for migrating applications in embedded systems.

Abstract User authentication is a critical part of security, along with confidentiality and integrity, for computer systems that allow legitimate users remote access over an open communication network. Recently, user authentication for wireless sensor networks (WSNs) has received considerable attention. We propose a robust user authentication scheme for WSNs. The scheme is based on elliptic‐curve cryptosystems with self‐certificates. The proposed scheme allows users to change their key pairs without interaction with a key distribution center (KDC). Moreover, the proposed scheme still works well even if the adversary captures tnodes out of nnodes in the WSNs. Security of the proposed scheme is modeled and analyzed with Petri nets. Our analysis shows that the proposed scheme can successfully defend some of the most notorious attacks, including replay attacks, forgery attacks, and node‐capture attacks. Copyright © 2010 John Wiley & Sons, Ltd.

A key agreement protocol is a protocol whereby two or more communicating parties can agree on a key or exchange information over an open communication network in such a way that both of them agree on the established session keys for use in subsequent communications. Recently, several key agreement protocols based on chaotic maps are proposed. These protocols require a verification table to verify the legitimacy of a user. Since this approach clearly incurs the risk of tampering and the cost of managing the table and suffers from the stolen-verifier attack, we propose a novel key agreement protocol based on chaotic maps to enhance the security. The proposed protocol not only achieves mutual authentication without verification tables, but also allows users to anonymously interact with the server. Moreover, security of the proposed protocol is modelled and analyzed with Petri nets. Our analysis shows that the proposed protocol can successfully defend replay attacks, forgery attacks, and stolen-verifier attacks.

Abstract Smart card‐based authentication is one of the most widely used and practical solutions to remote user authentication. Compared to other authentication schemes, our proposed scheme aims to provide more functionalities and to resist well‐known attacks. These crucial merits include (1) a user can freely choose and change his passwords; (2) our scheme provides mutual authentication between a server and a user; (3) it achieves user anonymity; (4) a server and a user can generate authenticated sessions keys. Moreover, our scheme can resist replay attacks, forgery attacks, insider attacks, reflection attacks, and parallel session attacks. Copyright © 2008 John Wiley & Sons, Ltd.

Over the last few years, many researchers have paid a lot of attention to the user authentication problem. However, to date, there has been relatively little research suited for wireless sensor networks. Recently, Wong et al. proposed a dynamic user authentication scheme for WSNs that allows legitimate users to query sensor data at every sensor node of the network. We show that Wong et al.'s scheme is vulnerable to the replay and forgery attacks and propose a lightweight dynamic user authentication scheme for WSNs. The proposed scheme not only retains all the advantages in Wong et al.'s scheme but also enhances its security by withstanding the security weaknesses and allows legitimate users to change their passwords freely. In comparison with the previous scheme, our proposed scheme possesses many advantages, including resistance of the replay and forgery attacks, reduction of user's password leakage risk, capability of changeable password, and better efficiency.

We propose a family of static evaluators for subclasses of the well-defined (i.e., noncircular) attribute grammars. These evaluators augment the evaluator for the absolutely noncircular attribute grammars with look-ahead behaviors. Because this family covers exactly the set of all well-defined attribute grammars, well-defined attribute grammars may be classified into a hierarchy, called the NC hierarchy, according to their evaluators in the family. The location of a noncircular attribute grammar in the NC hierarchy is an intrinsic property of the grammar. The NC hierarchy confirms a result of Riis and Skyum (1981), which says that all well-defined attribute grammars allow a (static) pure multivisit evaluator by actually constructing such an evaluator. We also show that, for any finite m, an NC(m) attribute grammar can be transformed to an equivalent NC(0) grammar.

We identify a new class of non-circular attribute grammars, called the multi-plan attribute grammars, for which static evaluation plans can be computed. The class of multi-plan attribute grammars is larger than all currently known classes of non-circular attribute grammars with static evaluation plans. The decision procedure and the procedure for computing evaluation plans take essentially polynomial time under a new, more practical criterion (but the procedures still take exponential time based on the traditional criterion). The multi-plan attribute grammars lead to a new way to classify well-defined attribute grammars into a hierarchy based on the look-ahead behavior of the evaluators. Our work confirms a result of Riis and Skyum (1981), which says that all well-defined attribute grammars can be evaluated with static evaluators.

Attribute grammars are a formalism for specifying computations on context-free languages. Due to the nonstrictness of the if constructs in attribution equations, it is possible to avoid evaluating certain attribute instances in a syntax tree. A dynamic evaluator can easily avoid such useless computations with a demand-driven approach. However, dynamic evaluators are not efficient because they need to keep the attribute dependence graph during evaluation, and they need to decide an evaluation order for each syntax tree. In contrast, a visit-oriented (static) evaluator can carefully re-arrange the evaluation order and still avoid unnecessary computations. We propose such a technique in this paper.

Given a program Base and two variants, A and B , each created by modifying separate copies of Base , the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that includes both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the Unix diff 3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base , A , and B . The first program-integration algorithm to provide such guarantees was developed by Horwitz et al.[13]. However, a limitation of that algorithm is that it incorporates no notion of semantics-preserving transformations. This limitation causes the algorithm to be overly conservative in its definition of interference. For example, if one variant changes the way a computation is performed (without changing the values computed) while the other variant adds code that uses the result of the computation, the algorithm would classify those changes as interfering. This paper describes a new integration algorithm that is able to accommodate semantics-preserving transformations.

Abstract Programmers frequently face the need to identify the differences between two programs, usually two different versions of a program. Text‐based tools such as the UNIXr̀ utility diff often produce unsatisfactory comparisons because they cannot accurately pinpoint the differences and because they sometimes produce irrelevant differences. Since programs have a rigid syntactic structure as described by the grammar of the programming language in which they are written, we develop a comparison algorithm that exploits knowledge of the grammar. The algorithm, which is based on a dynamic programming scheme, can point out the differences between two programs more accurately than previous text comparison tools. Finally, the two programs are pretty‐printed ‘synchronously’ with the differences highlighted so that the differences are easily identified.