UQBT - A Resourceable and Retargetable Binary Translator

1996-2001

The UQBT team (June 1999)

Table of Contents

• What is binary translation?
• Resourceable and Retargetable Binary Translation - An Overview
• Demos
  • Pentium Solaris fibonacci program to Sparc Solaris
  • Sparc Solaris knights program to Linux Pentium
• Preliminary Results
• Publications
• Wiki page on Binary Translation

• The source code for UQBT is made available by Sun Microsytems Laboratories under a BSD-like license.
• Java backend for GCC (GPL license)

Funding support

• Sun Microsystems Laboratories, 1996-2001.
• Australian Research Council, 1997-1999.
• The University of Queensland, 1997.

• UQBT, July 20, 1999
• Doug Simon, Nov 17, 1998
• David Ung, Jul 22, 1997

What is Binary Translation?

We are developing general, platform-independent techniques for binary translation based on descriptions of machines and operating system-related issues. Such techniques are valuable to any software developer that wants to port legacy software to a new machine. Our aim is to develop tools that will make software available quickly on new machines, without requiring source code or re-programming, and at low cost, by reuse of machine descriptions.

Our project is constrained to translations across operating systems that are the same or similar enough, such as Solaris and Linux, i.e. OS1 ~= OS2, in order to concentrate on analyses of machine instructions and their semantics, rather than API calls. When the operating systems are not the same, i.e. OS1 != OS2, there is a lot of tedious work translating API (Application Programmer Interface) calls. Cross operating system translation issues are addressed by projects such as Wine and to a lesser extent, VMware and freeMWare.

Resourceable and Retargetable Binary Translation - An Overview

Compilers and other tools have traditionally been called retargetable when they can support multiple target machines at low cost. By extension, we call a binary-analysis tool resourceable if it can analyze binaries from multiple source machines at low cost. Retargetability is supported in the UQBT framework through specifications of properties of machines and operating system conventions. Figure 1 illustrates the components of the translation process in the form of boxes. Specifications for different machines are illustrated with the document shape. Blue shapes mean that they are not currently supported by UQBT and therefore an implementation for a particular format or analysis has been done instead. Arrows represent conceptual flow of control in the translation process.

The UQBT framework is currently implemented reusing other's backends, hence we generate low-level C code and interface to GNU's gcc, Sun's cc and Jack Davidson's VPO. This shortcut is done as we don't have the resources to build yet another optimizer using standard compilet technology. Figure 2 illustrates this process.

Figure 2: Current UQBT Implementation.

The UQBT framework generates fat binaries in the form described in Figure 3.

Figure 3: Generated Fat Target Binary.

Specification languages

The characteristics of a machine's instruction set are its syntax (i.e. which bits match which assembly instructions), its semantics (i.e. what a particular assembly instruction mean), and its control transfer instructions (i.e. which instructions change the flow of control of a program and how). Machines that exhibit delayed transfers of control can specify this fact as well. These characteristics have been specified in a variety of languages for historical reasons, but could be specified in the one language. The following are the implementation languages that UQBT uses:

• Norman Ramsey's SLED (Specification Language for Encoding and Decoding), which describes the syntax of machine instructions;
• SSL (Semantic Specification Language), which describes the semantics of machine instructions in terms of RTLs.

Conventions and formats set by an operating system come in the form of calling conventions, including where parameters are passed (e.g. stack or registers), descriptions of a procedure's stack frame and where to find local variables, and the format of the binary file that the OS expects. These pieces of information are represented by the following implementation languages:

• PAL (Procedural Abstraction Language), which describes calling conventions, parameter passing conventions, stack frames and local variable locations; and
• BFF (Binary File Format), which describes the internal format of a binary file, such as ELF for Solaris and Linux systems.

We also use specialized analysis or APIs for other parts of the translator, such as:

• Control transfer instructions, such as basic transfers of control (conditional jumps, jumps, calls or returns); and
• Delayed transfers of control removal, such as transformation of SPARC's delayed branching instructions into semantically equivalent instructions that do not understand the delay transfer mechanism.

Demos

We show two examples of translations between Sparc binaries and Pentium binaries (one in each direction). Sources and targets are included below for the fibonacci and the knights programs.
 

Fibonacci

#include <stdio.h>

int fib (int x)
{
        if (x > 1)
                return (fib(x - 1) + fib(x - 2));
        else return (x);
}

int main (void)
{       int number, value;

        printf ("Input number: ");
        scanf ("%d", &number);
        value = fib(number);
        printf("fibonacci(%d) = %d\n", number, value);
        return (0);
}

fib()

fib()
8048960:  55                  pushl  %ebp
8048961:  8b ec               movl   %esp,%ebp
8048963:  53                  pushl  %ebx
8048964:  83 7d 08 01         cmpl   $0x1,8(%ebp)
8048968:  7e 2e               jle    0x2e <8048998>
804896a:  8b 45 08            movl   8(%ebp),%eax
804896d:  48                  decl   %eax
804896e:  50                  pushl  %eax
804896f:  e8 ec ff ff ff      call   0xffffffec <fib>
8048974:  83 c4 04            addl   $0x4,%esp
8048977:  8b d8               movl   %eax,%ebx
8048979:  8b 45 08            movl   8(%ebp),%eax
804897c:  05 fe ff ff ff      addl   $0xfffffffe,%eax
8048981:  50                  pushl  %eax
8048982:  e8 d9 ff ff ff      call   0xffffffd9 <fib>
8048987:  83 c4 04            addl   $0x4,%esp
804898a:  8b c0               movl   %eax,%eax
804898c:  8d 14 18            leal   (%eax,%ebx),%edx
804898f:  8b c2               movl   %edx,%eax
8048991:  eb 0d               jmp    0xd <80489a0>
8048993:  90                  nop    
8048994:  eb 0a               jmp    0xa <80489a0>
8048996:  90                  nop    
8048997:  90                  nop    
8048998:  8b 55 08            movl   8(%ebp),%edx
804899b:  8b c2               movl   %edx,%eax
804899d:  eb 01               jmp    0x1 <80489a0>
804899f:  90                  nop    
80489a0:  8b 5d fc            movl   -4(%ebp),%ebx
80489a3:  c9                  leave  
80489a4:  c3                  ret    

The UQBT static translated version of fibo is here; it's a Sparc Solaris binary. Here is the translated version of function fib:

fib()
8050b54:  9d e3 bf 90      save         %sp, -112, %sp
8050b58:  80 a6 20 01      cmp          %i0, 1
8050b5c:  04 80 00 08      ble          0x8050b7c
8050b60:  01 00 00 00      nop     
8050b64:  7f ff ff fc      call         fib
8050b68:  90 06 3f ff      add          %i0, -1, %o0
8050b6c:  a0 10 00 08      mov          %o0, %l0
8050b70:  7f ff ff f9      call         fib
8050b74:  90 06 3f fe      add          %i0, -2, %o0
8050b78:  b0 02 00 10      add          %o0, %l0, %i0
8050b7c:  81 c7 e0 08      ret     
8050b80:  81 e8 00 00      restore

It's hard to believe that it's the same program, but the semantics of the original program have been preserved, using different instructions to perform the same tasks.

Knights

For a larger example, we compiled an ncurses demo program (slightly modified) that plays the Knight's Tour game (where you try to visit every square on a chess board exactly once using only knight moves). Here are the Sparc source and Linux target binary files. Below is a screen capture of the translated program in action:

                    KNIGHT'S MOVE -- a logical solitaire

+---+---+---+---+---+---+---+---+  Possible moves are shown with `-'.        
|###|   |   |   |   |   |   |   |  
+---+---+---+---+---+---+---+---+  You can move around with the arrow keys or
|   |   |   |   |   |   |   |   |  with the rogue/hack movement keys.  Other
+---+---+---+---+---+---+---+---+  commands allow you to undo moves or redraw.
|   |###|   | - |   |   |   |   |  Your mouse may work; try left-button to   
+---+---+---+---+---+---+---+---+  move to the square under the pointer.
| - |   |   |   | - |   |   |   |
+---+---+---+---+---+---+---+---+  x,q -- exit             y k u    7 8 9   
|   |   |#X#|   |   |   |   |   |  r -- redraw screen       \|/      \|/   
+---+---+---+---+---+---+---+---+  ^h, bsp -- undo move    h-+-l    4-+-6  
| - |   |   |   | - |   |   |   |                           /|\      /|\ 
+---+---+---+---+---+---+---+---+                          b j n    1 2 3
|   | - |   | - |   |   |   |   |
+---+---+---+---+---+---+---+---+  You can place your knight on the selected
|   |   |   |   |   |   |   |   |  square with spacebar, Enter, or the keypad
+---+---+---+---+---+---+---+---+  center key.  You can quit with `x' or `q'.


                                   Press `?' to go to game explanation

Preliminary Results

UQBT is written in C++ and compiles using gcc on Solaris and Linux systems. It uses SLED and SSL descriptions for SPARC and Pentium, and PAL descriptions for SPARC and Pentium Unix System V ABI calling conventions, which are used under Solaris. UQBT uses gcc or cc as optimizing backends. We have extended gcc's backend to generate bytecode for the JVM. We have several translators in place, we present results for the following:

• uqbtss: static SPARC to SPARC
• uqbtsp: static SPARC to Pentium
• uqbtps: static Pentium to SPARC
• uqbtpp: static Pentium to Pentium
• uqbtsj: static SPARC to Java bytecode

• Fibo(40), which calculates the fibonacci of 40 and has 63 lines of assembly code,
• Sieve(3000), which calculates the first 3000 primes and has 61 lines of assembly code, and
• Mbanner(500K), a modified version of banner(1), which loops 500,000 times to display argv[1] (``1234567890'' in this case) and has 204 lines of assembly code and a read-only data section of 336 bytes.

Java Backend for GCC

Note: egcs 1.1.2 source code and Jasmin are required, and possibly many other packages; see the README files in the tar file.

Trent Waddington implemented this backend in the first half of 1999 while a student/researcher at The University of Queensland.