Month: June 2017

Android O and DEX 38: Dalvik Opcodes for Dynamic Invocation

Android O – API level 26 – upgrades the DEX format in order to provide support for dynamic invocation via two new Dalvik opcodes: invoke-polymorphic and invoke-custom.1

In this post, we will:

  1. Do a brief recap of how dynamic invocation is achieved in Java
  2. Present the changes made to the DEX file format in Android O
  3. Explain what the new dynamic invocation instructions can do and how they work
  4. Show code samples to generate DEX version 38 files
  5. Have a quick look at dynamic invocations in the context of app obfuscation

Note that JEB supports DEX version 38, as well as version 39 additions. That includes API support for programmatic access to the new pools and invoke-polymorphic, invoke-custom instructions, via the IDexUnit entry point interface.

Java’s invokedynamic

As a reminder, and quoting from the official Oracle doc (emphasis mine):

“[invokedynamic] improves implementations of compilers and runtime systems for dynamic languages on the JVM. It does this by allowing the language implementer to define custom linkage behavior. This contrasts with other JVM instructions such as invokevirtual, in which linkage behavior specific to Java classes and interfaces is hard-wired by the JVM.”

If that sounded like gibberish to you, you may want to get up to speed on dynamic invocation in Java – in particular, read the javadoc of MethodHandle and CallSite. We will (re)explain a bit in this post, but it is definitely not the main purpose of it. On top of the official Oracle doc as well as the original JSR, I recommend this article from the author of ByteBuddy.

Back in the Dalvik world

Up until DEX v35/v37, the way to invoke code in Dalvik was through one of the 5 invocation instructions:

  • invoke-virtual for virtual methods (Java’s invokevirtual)
  • invoke-static for static methods (Java’s invokestatic)
  • invoke-interface for methods called on interface types (Java’s invokeinterface)
  • invoke-super for super-class methods  (Java’s invokespecial)
  • invoke-direct for constructors  (Java’s invokespecial, again)
invoke-virtual Ljava/lang/String;->length()I, v

Each one of these takes a method item, which specifies a type (class or interface) as well as a method reference – ie, the “hard-wiring” part mentioned in the above quote. Java is statically typed, and the bytecode reflects that.2 That is, until invokedynamic was introduced with Java 7.

So, what is the Dalvik equivalent of Java’s invokedynamic?

Actually, there are 4 (2×2):

  • invoke-polymorphic (as well as invoke-polymorphic/range), which does “half” of what invokedynamic can do;
  • invoke-custom (as well as invoke-custom/range), which does the other, more powerful “half”.

invoke-custom requires additional pool elements, namely method handle items and call site items. Let’s walk over the DEX format additions to support those additional pools.

DEX version 38 changes

Most DEX files have version number 35. Android Nougat introduced version 37, which did not bring any structural changes (the new version code indicated support for Java 8’s default methods). If you were wondering why Dalvik did not have the equivalent of JVM’s invokedynamic, well, brace yourself: DEX version 38 is coming.

The header magic is now “DEX\x0A038\x00”. The updated file layout shows two additional pools: call_site_ids and method_handles.

However, the header size is still 70h bytes, and therefore, contains neither the offset to, nor the count of items, for those pools. Where are they?

Let’s turn to the DEX map. Sure enough, new types were introduced: TYPE_CALL_SITE_ID_ITEM (7) and TYPE_METHOD_HANDLE_ITEM (8). We can parse the map, find those two entries, and start parsing the pools.

  • A call site item is essentially an array of DEX Values. The array contains at least 3 entries:
    • a method handle index (as in: a Java MethodHandle) to a bootstrap linker method;
    • a dynamic method name, the one to be dynamically resolved
    • a dynamic method type (as in: a DEX prototype);
    • additional arguments. More on this later when we discuss invoke-custom.
  • A method handle item contains:
    • a type, indicating whether the method handle is a method invoker or a field accessor;
    • and a method id or field id, depending on the aforementioned type.

As far as other changes go, obviously, the DEX Value entries can be of two additional types: VALUE_METHOD_TYPE (0x15) that references the prototypes pool, and VALUE_METHOD_HANDLE (0x16) that references the method handles pool. (Note that there is no VALUE_CALL_SITE.)

Now, let’s see how those pools are used by the new invoke instructions, and how those instructions work.

Dalvik’s invoke-polymorphic

Below are the specifications of invoke-polymorphic taken from Android Source:

invoke-polymorphic MH.invoke, prototype, {mh, [args]}

invoke-polymorphic is used to invoke a method handle using one of two @PolymorphicSignature 3 methods of the MethodHandle object: invoke() or invokeExact(). It takes at least 3 arguments:

  • A method reference to either MethodHandle.invoke or MethodHandle.invokeExact (MH.invoke)
  • The prototype of the method to be executed
  • A method handle (mh) of the target

See the example below: MethodHandle.invoke() is used on the method handle v0; the target method has the prototype (I)Object. Therefore, v1 is of type int; the return value will be of type Object.

invoke-polymorphic used in a Dalvik version 38 file

The return type as well as parameter types are specified in the prototype item, instead of a static method item — hello, polymorphism. Of course, the target method handle must reference a method of such type, either exactly, if MethodHandle.invokeExact() is used, or have compatibility with the type (via  conversion operations), using MethodHandle.invoke().

Wait, That looks like a normal invocation!

You would be semi-right to think so. After all, we are executing invoke() or invokeExact() the old fashion way here… so, why need an additional opcode? First, remember that those methods have polymorphic signatures; their prototype is determined at compile-time. Therefore, there are two options (using the example above):

  • either the bytecode references an invoke with an (I)Object prototype: in this case, we could simply call invoke-virtual on an artificial invoke(I)Object. This is the case with the Java bytecode: invokevirtual is used;
  • or the bytecode references the generic invoke([Object)Object: in this case, the invocation would require an additional prototype argument. Hence the requirement for a new invoke opcode. This is the case with the Dalvik bytecode: invoke-polymorphic was created. It  takes not one, but two pool indexes.4

Can’t I do the same with reflection?

You may be wondering what the point of these convoluted constructions is… After all, couldn’t we do the same with reflection? The answer is mostly yes, however, remember that invokedynamic has a different goal than introspection: the goal of invokedynamic is to provide an efficient low-level primitive meant to execute dynamic call sites, and therefore, enable the implementation of dynamic languages on top of the JVM.

Practically, and as far as Java goes,  they enable the implementation of Java 8 lambdas without the use of pre-compiled anonymous inner classes.

Also practically, true polymorphism means we are no longer dealing with the auto-boxing casts associated with Reflection API calls. MethodHandle.invoke() is a very particular method – as said above, it is has a polymorphic  signature, inferred at compile-time based from the types of arguments and return value provided in the call. Nothing like actual code to show what we mean here.

Sample Code

The example below has a triple-purpose:

  • Set up your environment to generate DEX v38 files;
  • Generate DEX files containing invoke-polymorphic instructions;
  • Compare MethodHandle.invoke() vs reflection.

First, download Android Studio 2.3. It turns out that at the time of writing, compiling DEX v38 with a non-Jack toolchain (using AS 3.0) produces invalid DEX files.  Make sure to use the Android Gradle plugin 2.3.3 or above. Finally, make sure to use SDK level 26 in your module-level Gradle script, and add the “o-b2” option to allow the generation of the new invoke instructions (thank you, Tsuyoshi Murakami):

android.defaultConfig.jackOptions {
    enabled = true
    additionalParameters 'jack.android.min-api-level': 'o-b2'
}

Now, let’s compile this 30-line activity class:

public class MainActivity extends Activity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        String text = "";
        try {
            text = String.format("dynamic=%s reflect=%s", execDynamically(), execViaReflection());
        }
        catch(Throwable e) {
            text = e.toString();
        }
        Log.d("DexVer38", text);
        TextView tv = new TextView(this);
        tv.setText(text);
        setContentView(tv);
    }

    static Object execDynamically() throws Throwable {
        return MethodHandles.lookup().findStatic(MainActivity.class,"foo",
                MethodType.methodType(int.class, String.class, int.class)).invoke("hello", 2);
    }

    static Object execViaReflection() throws Throwable {
        return MainActivity.class.getDeclaredMethod("foo", String.class, int.class).invoke(null, "hello", 2);
    }

    static int foo(String s, int i) {
        return s.charAt(i);
    }
}

Both execDynamically() and execViaReflection() methods eventually invoke foo(“hello”, 2) and return its result:

$ adb logcat -s "DexVer38"
[...] D DexVer38: dynamic=108 reflect=108

However, while the polymorphic MethodHandle.invoke() of execDynamically truly takes a String as first argument, an int as second argument, and returns an int; we know it is not the case with the non-polymorphic invocation used by the Method.invoke(): casts are in place to box/unbox the int primitives to/from an Integer object.

Open the resulting DEX file in JEB:

MethodHandle and invoke-polymorphic vs Reflection and invoke-cirtual

Carefully look at the disassembly of both methods:

  • invoke-polymorphic’s MethodHandle.invoke handles any prototype, as long as the referenced method matches it
  • reflection’s Method.invoke is called using a traditional invoke, and therefore, its arguments must be a an array of Object, and its return value an Object — hence, the casts.

I hope this sheds some light on invoke-polymorphic, in terms of MethodHandle uses and resulting differences in the bytecode.

Dalvik’s invoke-custom

Below are the specifications of invoke-custom taken from Android Source:

invoke-custom callsite, {arguments}

Dalvik’s invoke-custom ~= Java’s invokedynamic

Before we explain the mechanics behind invoke-custom, remember that unlike the legacy invoke-xxx instructions, it does not take a reference to the LType;->method() that will be executed. Both will be determined at run-time.

The invoke-custom instruction first resolves and then invokes a call site:

  • Initially, an invoke-custom instruction is an unlinked state: its call site has yet to be created. It is the resolution stage:
    • The runtime checks if a CallSite object exists for the provided callsite index
    • If not, a new CallSite object is created using the data provided by the call site item at the corresponding pool index, via a bootstrap linker method
    • The invoke-custom is now in a linked state
  • When the invoke-custom is in a linked site, the CallSite object’s MethodHandle is invoked.

The following diagram summarizes the bootstrap process of linking an unlinked invoke-custom:

Delaying the resolution and creation of the callsite until runtime allows the VM to take the decision of which type and which method should the execution flow be dispatched to.

Bear in mind that in standard Java, crafting explicit code using dynamic invocation is currently not possible. That limitation can be circumvented with custom toolchains (such as Android’s Jack, as we’ll see below). However, a prime candidate for implicit use of dynamic invocations are of course lambdas. Lambda functions have been supported since Android Nougat and are currently compiled using virtual invocations. It is safe to say that we should see lambdas using invoke-custom in the near future, maybe as early as the release candidate of Android O.

Sample Code

Currently, crafting high-level Java code that produces invoke-custom is convoluted and artificial — unfortunately, lambdas are still desugared into statically invoked methods of synthetic inner classes.

Two possible options are:

  1. Crafting Dalvik code manually , or via a custom tool, or via a bytecode manipulation library. It is outside the scope of this post;
  2. Use the soon-to-be-deprecated Jack toolchain and custom Jack annotations to generate bootstrap methods.

Using the second approach, we can generate code that contains correct call site item pools. However, at the moment, those DEX files do not pass the Verifier.

That being said, the generated bytecode looks fine. Have a look at the sample below:

public class MainActivity extends Activity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        String text = "";
        try {
            text = "" + execCustom();
        }
        catch(Throwable e) {
            text = formatThrowable(e);
        }
        Log.d("DexVer38", text);
        TextView tv = new TextView(this);
        tv.setText(text);
        setContentView(tv);
    }

    public static String formatThrowable(Throwable t) {
        Writer writer = new StringWriter();
        PrintWriter out = new PrintWriter(writer);
        t.printStackTrace(out);
        return writer.toString();
    }

    public static Character execCustom() throws Throwable {
        return foo("hello", Integer.valueOf(2));
    }

    @CalledByInvokeCustom(
            invokeMethodHandle = @LinkerMethodHandle(kind = MethodHandleKind.INVOKE_STATIC,
                    enclosingType = MainActivity.class,
                    name = "linkerMethod",
                    argumentTypes = {MethodHandles.Lookup.class, String.class, MethodType.class}),
            name = "foo",
            returnType = Character.class,
            argumentTypes = {String.class, Integer.class})
    static Character foo(String s, Integer i) {
        return s.charAt(i);
    }

    private static CallSite linkerMethod(MethodHandles.Lookup caller, String name, MethodType methodType)
            throws NoSuchMethodException, IllegalAccessException {
        return new ConstantCallSite(caller.findStatic(caller.lookupClass(), name, methodType));
    }
}

Using the CalledByInvokeCustom annotation, we can specify that foo() must be dynamically invoked. The code is a bit artificial, and the linked method trivial, but see how the seemingly static call to foo() in execCustom() was compiled to the following bytecode:

invoke-custom used in a Dalvik version 38 file

Note that the JEB syntax for invoke-custom call sites is temporary and subject to change. At the moment, the pool’s call site is displayed within double curly brackets:

{{ MethodReference / DynamicMethodName / DynamicPrototype / [additional arguments, …] }}

JEB will decompile those constructs to an invocation of the bootstrap linker method, followed by a call to invoke() on the returned CallSite’s method handle. In a real environment, the bootstrap method would be executed just once. Indeed, high-level Java code cannot reflect all forms and uses of those low-level constructs.

Keep in mind that invoke-custom‘s purpose is much broader than this dummy example. As said in the previous section, we should expect it to initially be used when generating Java 8’s lambdas. They may not be extremely popular – not yet – in traditional Java programming circles, but Google’s big push on Kotlin for Android O, including:

  • Kotlin integration in Android Studio, facilitating adoption;
  • Kotlin full compatibility with Java, allowing mixed code base during migration;
  • Kotlin’s affinities with dynamically-typed languages;

may be indicators that invoke-custom (and invoke-polymorphic) will be used to power new language features for Android app development in the near future.

Dynamic invocation used for obfuscation

Finally, let’s conclude this post with a note on obfuscation, and generally, unintended, unplanned, or at least non-primary use cases, for MethodHandle.

Just like reflection has been heavily used by all5 Dalvik protectors and obfuscators to hide API calls and make static code flow analysis difficult, we should expect MethodHandle and CallSite to be used in similar ways.

MethodHandle objects have more restrictions than pure reflection though, eg, in terms of the scope of what can be retrieved. Obviously, they cannot be used to retrieve types dynamically — which means there is no equivalent to Reflection’s Class.forName(“…”). However, they can be used to retrieve handles on methods, constructors, and fields, and therefore could be mixed in with standard reflection-based obfuscation techniques.

As for invoke-custom: parsing and analysis of the call site items pool will be required to retrieve references to boostrap linker methods, and determine their effect on code.

So, exciting times ahead! We should all be excited to see those new dynamic invoke opcodes used by apps in the future, as well as the potential they bear in terms of new languages (or more realistically, new language features) that they can provide for Android app development.

  1. And their /range counterparts. Essentially, this update is the Android implementation of JSR292 ↩
  2. That point is debated; however, the invoke call sites exhibit the static nature of type binding in the bytecode. ↩
  3. The PolymorphicSignature annotation is defined within MethodHandle and visible only to types declared  in the java.lang.invoke package ↩
  4. Both ways are conceptually valid. In the first case, we are assuming that an infinity of MethodHandle.invoke signatures exist. In the second case, we consider that MethodHandle.invoke true prototype is ([Object)Object; that means we must provide the actual prototype separately, via a new opcode. ↩
  5. The Dalvik verifier is quite strict and limits the classes of obfuscation that can be applied onto bytecode. ↩

Automatic Identification of Mirai Original Code

Context

One of the major threat on embedded devices — the so-called “Internet of things” –, is the infamous Mirai malicious software, whose source code was made public in September 2016. This malware has the ability to infect devices by brute-forcing Telnet credentials, and is primarily used to launch distributed denial-of-service attacks.

Since the source code release, numerous Mirai variants have been deployed in the wild by miscreants, like the one we documented in a recent post.

In this blog we will first take a quick look at another Mirai-based malware, quite original in its own way, to then introduce our novel signature system that can identify Mirai original code in executables.

Yet Another Mirai Variant

On May 18th, ESET’s Michal Malík mentioned on Twitter a Mirai-based sample for MIPS that grabbed our attention. Michal pointed out new functionalities like a custom update mechanism, and some strange debug routines, so we decided to take a look with our brand new MIPS decompiler. It should be noted that this sample comes with the debug symbols, which explains the names present in the decompiler output.

The malware logic starts in its main() routine, which is shown below as decompiled by JEB.

Briefly summarized, this routine first sets up a few signal handlers, in particular to create a core file in case of segmentation fault. It then calls a homemade panic() function — not to be confused with the standard Linux panic() routine. The panic() function code is shown below, as seen in JEB.

While the routine native code — seen on the left side — can be pretty dry to read, the decompiled code on the right side is fairly straightforward: a file named file.txt is opened and a given error message is written to it, accompanied by a custom system footprint built by the footprint12() routine.

Finally, main() calls the kill_run_mobile1() function, which first kills any application listening on TCP port 18899 (likely others instances of the same malware),  and then creates a thread on the mobile_loop1() function, which is shown below.

The new thread will listen for incoming connections and process them through a custom command handler. As can be seen from the numerous debug messages in the decompiled code, the code is still in a development stage.

To summarize, this sample appears to be an attempt to repackage Mirai source code with a different update mechanism, and is still in development, as can be seen from the presence of debug routines, and the fact that plenty of code remains unused.

While the technical quality of this sample is dubious, it illustrates one of the major consequence of Mirai source code public release: it has lowered the bar of entry for malicious software developers. In particular, we can expect the strain of Mirai-based malicious software to continue to grow in the following months.

Native Code Signatures

In a context where numerous Mirai-based malware are deployed in the wild, having the ability to identify original Mirai code becomes particularly useful, as it allows the analyst to focus only on the new functionalities in each sample.

Of course, most of Mirai-based samples do not come with symbols, and hence we need a proper mechanism to identify Mirai original code. That is the purpose of the native signature system released with JEB 2.3, which can actually identify code for all native architectures supported by JEB (x86, ARM, MIPS and the associated variants).

The objective of this signature system is to identify native routines with a minimal number of false positives. In others words, we want to fully trust a successful identification, while we may miss some known routines.

To realize this low false positives goal, our signatures are primarily based on two features:

  • A custom hash computed on the binary code of the unknown routine. During this computation, we remove from the native instructions the addresses and offsets that may vary depending on where the routine is located in a binary. Hence the same routine located at a different place will have the same hash. Interestingly, as our algorithm uses the generic JEB interface on native instructions (IInstruction), the hash computation is done on all architectures in the same way.
  • The names of the routines called by the unknown routine, e.g. API routines, system calls, or already identified routines. This feature allows to distinguish wrappers that have exactly the same binary code but call a different routine.  

The whole signature process can be summarized in two steps — which will be described in details in a separate documentation:

  1. Signatures are generated from a reference file. This file can be a native file with symbols, or a JEB database with some routines renamed by the user. For each named routine, a signature containing the routine features and information is created. Signatures are then grouped into packages for each platform.
  2. When JEB analyzes an unknown routine, it tries to match it with the signatures. If there is a match, the information of the original routine are imported, e.g. the matched unknown routine is renamed as the original routine.

Due to its strict reliance on the binary code, this identification process does not offer a resistance to minor changes, like the ones introduced by compilation with a different compiler version or with different optimizations. We intend to develop others signature systems in JEB, which will be more resistant to such variations, in particular by using JEB intermediate representation.

Still, it is particularly suitable in the case of Mirai, where the public source code comes with compilation instructions, such that many samples are compiled in the same way and share the exact same binary code. Therefore, JEB 2.3 comes with a set of signatures created from a non-stripped executable created from Mirai public source code.

These signatures are automatically applied when a MIPS binary is loaded in JEB. For example, here is an extract of the initial routines list after loading in JEB a stripped Mirai sample deployed last year (SHA1: 03ecd3b49aa19589599c64e4e7a51206a592b4ef).

On the 204 routines contained in the sample, 120 are automatically identified and renamed by JEB, allowing the user to focus on the unknown routines. It should be noticed that not all recognized routines belong to Mirai specific code, some of them belong to the C library used by Mirai (uClibc).

Conclusion

The JEB native signature system is still in development, but its results are encouraging and we provide a set of signatures for Mirai on MIPS platform, and for the standard C library shipped with Microsoft Visual Studio 2013 on the x86 platform. We encourage users to try it through our demo version, and report any comments to support@pnfsoftware.com.

In the following weeks, not only will the number of signatures rapidly grow — through a specific update mechanism –, but we also intend to let users generate their own signatures with JEB public API.

Acknowledgement

The malicious software analysis presented in this post was done by our intern Hugo Genesse.