Obfuscating Java bytecode with LLVM and Epona

Java bytecode to LLVM IR

• VMKit: https://vmkit.llvm.org/

• The LLVM Java frontend: https://llvm.org/svn/llvm-project/java/trunk/docs/java-frontend.txt

• JLang: https://github.com/polyglot-compiler/JLang

These solutions have been developed to run Java programs natively (without going back to Java Bytecode), thus discarding valuable information like Java specific try/catch block.

They are also incomplete, because running Java natively requires a whole translation of all the standard Java libraries. Note that we don't have such problem in our project, as we intend to transform back the LLVM IR to Java bytecode.

It is also interesting to notice that the [Zing] JVM uses LLVM via [Falcon] to compile and optimize the most frequently used pieces of codes at runtime. The paper "Obfuscating Java Programs by Translating Selected Portions of Bytecode to Native Libraries" by Pizzolotto and Ceccato (2019) [2] is the one closest to what we try to achieve. Their goal is to transform the Java code to C code, while using JNI to support more complex behavior. This approach can be seen as some kind of [Cython] for Java. Note that the sources of the tool aren't available.

LLVM IR to Java bytecode

• LLJVM: https://github.com/davidar/lljvm

• Sulong: https://github.com/oracle/graal/tree/master/sulong

• The Proteus Compile System: http://proteuscc.sourceforge.net/

The goal of these solutions is to run the LLVM bitcode within a JVM, emulating all the missing functionalities, like raw memory management. If we had reused these projects, we would have ended up with a virtual machine (the LLVM one) within a virtual machine (the JVM). We would also have had to take care of the standard Java libraries problem.

Calls

We are using a variety of abstract methods to convert Java bytecode instructions that can't be directly translated to LLVM IR, like calls to other Java methods. These calls are converted using a specific convention: all the necessary information is encoded in the called function name, and the call parameters are the same as their bytecode counterparts. This makes it easy to convert back to bytecode while still allowing the optimizer and obfuscator to do their job.

For example a bytecode INVOKESPECIAL instruction will be translated to call void @"Java_@invokespecial@java/lang/Object@<init>@()V"(i64* %1). Here calling the constructor of the target object java.lang.Object without any argument (i64* %1 is the pointer referencing this object)

We provide here a simple Java example, its corresponding Java bytecode and the generated LLVM IR:

AtomicInteger ai = new AtomicInteger(4);
Math.pow(ai.get(), 2);

NEW Ljava/util/concurrent/atomic/AtomicInteger;
DUP
BIPUSH 4
INVOKESPECIAL java/util/concurrent/atomic/AtomicInteger.<init>:(I)V
INVOKEVIRTUAL java/util/concurrent/atomic/AtomicInteger.incrementAndGet:()I
I2D
LDC 2D
INVOKESTATIC java/lang/Math.pow:(DD)D
D2I
IRETURN

%1 = call i64* @"Java_@new@java/util/concurrent/atomic/AtomicInteger"()
call void @"Java_@invokespecial@java/util/concurrent/atomic/AtomicInteger@<init>@(I)V"(i64* %1, i32 4)
%2 = call i32 @"Java_@invokevirtual@java/util/concurrent/atomic/AtomicInteger@get@()I"(i64* %1)
%3 = call double @"Java_@invokestatic@java/lang/Math@pow@(DD)D"(i32 %2, i32 2)

The same technique is also used for representing things like this which is ALOAD 0 in a non static Java methods to be used for super class instantiation.

%1 = call i64* @Java_fixed_this()
call void @"Java_@invokespecial@com/quarkslab/java2llvm/testfiles/TestFile@<init>@()V"(i64* %1)

Calls are also extensively used for Java array manipulation:

%1 = call i64* @Java_fixed_array_create_10(i32 1)
call void @Java_fixed_array_setIntCellData(%1, i32 0, i32 5)
call i32 @Java_fixed_array_getIntCellData(%1, i32 0)

With this abstraction, converting back to Java bytecode is natural, as most information required for the translation is available in the function's name. For example the array type is specified in the array create function (the opcode 10 is for integer) without having to find the first value assignment to get the array type from.

The drawback of this approach is that we suppose that all the users of these abstract functions will be calls, and they won't end up (for instance) in an array of function pointers. This is something for instance an obfuscator could generate. This means that we need to make it aware of the special semantics of these functions.

Representation of the JVM stack

Inspired from this paper about translating bytecode to native libraries [2] , we came up with a very simple way to convert the Java stack to LLVM registers. We began by writing functions to add elements and pop elements from the stack. The stack is a simple array defined with a given length (given in the bytecode) and with an index to track where we are. We then call out special functions each time we need to interact with the stack. These functions are inlined in the final LLVM IR, and the optimizations (Scalar Replacement Of Aggregates [https://llvm.org/docs/Passes.html#sroa-scalar-replacement-of-aggregates] being the most important) completely remove the stack array.

The same technique is used for store and load operations, without the need for the index to keep track of where we are on the stack.

Note: The functions are generated at build time from C, simply because it is easier to write and to understand than the LLVM IR.

Control flow

The control flow is also easily converted and optimized:

public int test(int a1, int a2) {
  return a1 > a2 ? a2 : a1;
}

Gives:

define i32 @"test@(II)I@1"(i32, i32) local_unnamed_addr {
lb_529116035_608112264:
  %"3" = tail call i64* @Java_fixed_this()
  %"9" = icmp sgt i32 %0, %1
  %. = select i1 %"9", i32 %1, i32 %0
  ret i32 %.
}

We can see that the implicit if instruction and the two possible result basic blocks have been combined into one using a select instruction.

The following example contains a loop:

public int test(int a1, int a2) {
  int j = 0;
  for (int i = 0; i < a1; i++) {
    j += a2;
  }
  return j;
}

In the generated LLVM IR, it is optimized to a simple multiplication with a select for negative values:

define i32 @"test@(II)I@1"(i32, i32) local_unnamed_addr {
lb_1433867275_-465532616:
  %"3" = tail call i64* @Java_fixed_this()
  %"1121" = icmp sgt i32 %0, 0
  %2 = mul i32 %1, %0
  %spec.select = select i1 %"1121", i32 %2, i32 0
  ret i32 %spec.select
}

The next one:

public int test(int a1, int a2) {
  for (int i = 0; i < a2; i++) {
    System.out.println();
  }
  return 0;
}

gives out:

define i32 @"test@(II)I@1"(i32, i32) local_unnamed_addr {
lb_start:
  %"17.reg2mem" = alloca i32
  %"3" = tail call i64* @Java_fixed_this()
  %"1016" = icmp sgt i32 %1, 0
  br i1 %"1016", label %lb_preloop, label %lb_return

lb_preloop:
  store i32 0, i32* %"17.reg2mem"
  br label %lb_loop

lb_loop:
  %locals.sroa.4.017.reload = load i32, i32* %"17.reg2mem"
  %"11" = tail call i64* @"Java_@getstatic@java/lang/System@out@Ljava/io/PrintStream;"()
  tail call void @"Java_@invokevirtual@java/io/PrintStream@println@()V"(i64* %"11")
  %"17" = add nuw nsw i32 %locals.sroa.4.017.reload, 1
  store i32 %"17", i32* %"17.reg2mem"
  %exitcond = icmp eq i32 %"17", %1
  br i1 %exitcond, label %lb_return, label %lb_loop

lb_return:
  ret i32 0
}

This loop stays as a loop because of the abstract Java functions. It would have been unrolled if it was possible.

Our last control flow example contains a switch:

public int test(int a1, int a2) {
  switch (a1) {
    case 0:
      return 1;
    case 1:
      return 5;
    case 20:
      return 3;
    case 15:
    case 17:
      return 666;
  }
  return 0;
}

resulting in the following IR:

define i32 @"test@(II)I@1"(i32, i32) local_unnamed_addr {
lb_791885625_-801122440:
  %merge.reg2mem = alloca i32
  %"3" = tail call i64* @Java_fixed_this()
  switch i32 %0, label %lb_2054881392_-801122440 [
    i32 0, label %lb_791885625_-801122440.lb_1887400018_-801122440_crit_edge
    i32 1, label %lb_2001112025_-801122440
    i32 15, label %lb_791885625_-801122440.lb_1288141870_-801122440_crit_edge
    i32 17, label %lb_791885625_-801122440.lb_1288141870_-801122440_crit_edge12
    i32 20, label %lb_314265080_-801122440
  ]
...

Fields

A field is a variable inside a class. It can be accessed by any method in the class and sometimes from outside the class.

We translate them as LLVM global variables. When translated back to Java bytecode, these globals will be converted back to fields.

This code:

private int test;

public int test(int a1, int a2) {
  test = 9;
  test += a1;
  test *= a2;
  return test;
}

public int getTest() {
  return test;
}

Gives out:

@"Java_@test@2@I" = external local_unnamed_addr global i32

define i32 @"test@(II)I@1"(i32, i32) local_unnamed_addr {
lb_48612937_-532753336:
  %"16" = add i32 %0, 9
  %"25" = mul i32 %"16", %1
  store i32 %"25", i32* @"Java_@test@2@I", align 4 ; A store to the variable representing the test field
  ret i32 %"25"
}

define i32 @"getTest@()I@1"() local_unnamed_addr {
lb_1618212626_-532735736:
  %"6" = load i32, i32* @"Java_@test@2@I", align 4 ; A load from the variable representing the test field
  ret i32 %"6"
}

Exceptions

Exceptions, on the contrary, are difficult to translate to LLVM IR. There is an exception system in LLVM with throw, try/catch, cleanup pads, but it doesn't behave like the Java exception system and a lot of information that would need to be forwarded back to Java would have been lost. We need to keep in mind that LLVM is not intended to be converted to Java Bytecode.

We needed to implement our own exception system. This was done with functions representing try/catch blocks to be sure that the optimizations or obfuscations wouldn't mess them up. The exception type is encoded in metadata.

For example the following code:

public void test() {
  try {
    ...;
  } catch (RuntimeException e) {
    e.printStackTrace();
  }
}

is translated to the following IR, where we can see two added functions, one for the try block and one for the catch block:

define i32 @"test@()V@1"() {
  ...
  %"6" = call i1 @Java_fixed_exception_try_1433867275(i64*  %localsPointer)
  br i1 %"6", label %lb_itsFine, label %lb_haltAndCatchFire

lb_haltAndCatchFire:
  call void @Java_fixed_exception_catch_1433867275(i64* %localsPointer)
  br label %lb_itsFine

lb_itsFine:
  ret void
}

define i1 @Java_fixed_exception_try_1433867275(i64*) { ; The function for the try part of the try/catch
  %9 = tail call i1 @Java_fixed_exception_result_1433867275()
  ret i1 %9
}

define void @Java_fixed_exception_catch_1433867275(i64*) { : The function for the catch part of the try/catch
  %"13" = tail call i64* @Java_fixed_exception_push()
  tail call void @"Java_@invokevirtual@java/lang/RuntimeException@printStackTrace@()V"(i64* %"13")
  ret void
}

So as long as each of the behavior of theses functions is the same, at a function level, before and after the transformations, everything is fine. In particular, we prevent the inlining of these functions, so that we can easily convert this scheme back to Java bytecode.

This is the simplest example. This system works fine for simple exceptions, exceptions with multiple catch clauses, exceptions in try or catch blocks. Problems arise when there is a jump out of the try/catch function, possibly in the middle of another one. This had to be accommodated for with switches and it made the exception conversion system quite complex.

On the other hand, translating exceptions back to Java bytecode is simple because with well defined names, finding the matching catch function for a try function is trivial.

Conversion of LLVM instructions

Here, we are going to speak about problems that can arise with specific LLVM instructions.

The first easy one is the phi instruction, classically used in an SSA form. We can easily use the already existing -reg2mem optimization to transform these into memory loads to and stores from an alloca'd variable.

The second instruction is the [GEP] instruction. Its job is to compute pointer offsets to access array or structure elements. To deal with GEP and pointers in general, we needed a points-to analysis to convert GEP instructions, figuring out if we need to access an array, an object, a local value or anything else. We need to be able to resolve all the pointed values when we are converting to Java bytecode otherwise we would need emulation at runtime. It generally works if the program is not too heavily obfuscated.

For others instructions like select instructions or operations on unsigned integers we can translate them with multiple Java bytecode instructions, but we easily end up with five times more instructions to do the same thing. When these instructions are not present we most of the time end up with smaller bytecode.

Another problem to solve is that we need to go from an SSA form back to a stack-based machine.

Back to a stack machine

The JVM is a stack machine, whereas LLVM is working with an infinite amount of registers. Thankfully, locals exist in Java bytecode.

Locals are the way of storing information inside a function when there are some operations the stack can't do, because a needed element is not at the right spot or available on the stack at all. Values can be loaded from locals (e.g. ILOAD 3 loads a 32 bit integer from the local at index 3) and put on the stack or stored from the stack to a local (e.g. DSTORE 4 stores a 64 bit floating point value in the local at index 4). The type of a local can't change during the execution of a method. There are about 65k locals available (index encoded on 16 bits) and 64 bits values like long or double take two consecutive spots.

Here is an example, describing the algorithm we use. For each instruction, LLVM easily gives us a list of the used values. The order of these values can be important, depending on whether the operator is commutative or not. So, we need the values on the stack to fit our needs for the next instruction.

For example, consider the following stack with the following values, D being at the top of the stack:

A B C D

We need the values C, D and E to be at the top of the stack for the next instruction. The algorithm finds that C and D are already at the top of the stack and that we only have to add E. E is added at the top of the stack and the next instruction can be executed.

The stack now looks like this, with R being the result of the previous instruction:

A B R

R is duplicated and stored for later use.

Sometimes, elements on the stack are not in the right order, for example:

A C D B

As the top of the stack is not useful to us and might be used in the future, we have to add our values, ending up with:

A C D B C D E //Before instruction
A C D B R //After instruction

This algorithm can create large stacks of unused or unusable elements (because they are "covered" by others) so we perform a cleanup at the end of the conversion. We begin by removing useless store instructions with never used values. We then remove all stack values that are never accessed.

This algorithm is simple but does not always produce optimal results. The number of loads and stores could be reduced if the stack was managed better. There are descriptions of non trivial algorithms for conversion and optimization that could be worth implementing [3] [4] [5] .