Optimized DEX files

One of the less publicized ability of the Dalvik virtual machine is that it is able to execute "optimized" DEX files (or ODEX files). "Optimizing" a DEX file speeds up its execution but also ties it to the hardware platform on which the optimization was performed. ODEX optimization relies on unsafe bytecode instructions. Unsafe instructions are much faster to execute, on the other hand, malicious use of these instructions can crash the virtual machine. Dalvik has an additional layer of security, process separation and file permissions of the underlying Linux platform so this price is not that high. It is important to note, however, that much of the security normally associated to the Java virtual machine e.g. in J2ME is now provided by the underlying Linux platform.

I remember the resistance when I proposed unsafe instruction for garbage collection performance optimization on mobile platforms. The critics argued that 1. the Java bytecode is not allowed to be modified and 2. the bytecode safety must be preserved at all costs. Seemingly, Dalvik designers have done away with both ortodoxies.

The optimization is carried out on the target platform, by the target platform's virtual machine. The command to invoke the optimizer is called dexopt. There is no point in invoking this command on the emulator as it would create an optimized DEX that can be executed only on the emulator. The most important transformations are the replacement of the method indexes with vtable indexes and the field indexes with memory offsets. So instead of invoking a method by name, it is invoked by vtable index using a set of special instructions not specified in the Dalvik instruction set.

For example:

invoke-virtual-quick {v1,v2},vtable #0x3b

(Note: if anyone reads this who is knowledgeable in the way the vtable index is computed, please, drop me a comment or mail :-))

Also, for fields:

iget-object-quick v0,v2,[obj+0x100]

The dedexer tool was updated and now provides a limited support for ODEX files. Sadly, I was not able to figure out, how to calculate method or field names out of vtable indexes and byte offsets which clearly limits the usefulness of the disassembled ODEX sources. When I was at it, I also implemented debug information processing that generates line number and local variable information like this:

.var 0 is intent Landroid/content/Intent; from l144ac to l144c8
const-class v3,com/android/vending/SubCategoryListActivity
const-string v2,"android.intent.action.VIEW"
.line 180

The Dalvik opcode list was also updated with the description of the "quick" instructions.

Generating keypresses programmatically

There was already a blog entry about programmatically generating key events but I was not satisfied with the outcome. The Instrumentation framework is nice but is somewhat heavyweight. If one wants to generate just keypresses, why to have all those entries in the manifest, instrumentation object, etc? So I used the wonderful new dedexer tool to go after the inner workings of the instrumentation framework.

The critical method in android.app.Instrumentation is this:

.method public sendKeySync(Landroid/view/KeyEvent;)V
.catch android/os/RemoteException from le5cf6 to le5d12 using le5d14
 invoke-direct    {v2},android/app/Instrumentation/validateNotAppThread
                 ; validateNotAppThread()V
le5cf6:
 const-string    v0,"window"
 invoke-static    {v0},android/os/ServiceManager/getService
                 ; getService(Ljava/lang/String;)Landroid/os/IBinder;
 move-result-object    v0
 invoke-static    {v0},android/view/IWindowManager$Stub/asInterface    
                 ; asInterface(Landroid/os/IBinder;)Landroid/view/IWindowManager;
 move-result-object    v0
 const/4    v1,1
 invoke-interface    {v0,v3,v1},android/view/IWindowManager/injectKeyEvent    
                 ; injectKeyEvent(Landroid/view/KeyEvent;Z)Z
le5d12:
 return-void
le5d14:
 move-exception    v0
 goto    le5d12
.end method

This is actually a public API method. The method obtains the binder of the WindowManagerService from the ServiceManager then it invokes the injectKeyEvent method on WindowManagerService's public interface. That is something we can do ourselves, can't we?

Click here to download the example program.

Unfortunately the situation is not that simple. Ever since the non-public classes like android.os.ServiceManager, android.view.IWindowManager, etc. were removed from android.jar, applications using non-public API cannot be compiled as easily as before. If you check the example program, you will see that I created stubs for these classes. These stubs are only there to allow compilation of the program, they don't get packaged into the apk file. On the platform itself, there will be real versions of them. In order to accomodate the stub compilation step, I modified somewhat the machine-generated build.xml file too.

It is also important to notice the validateNotAppThread private method invocation at the beginning of the method. Events cannot be generated neither from the application's own thread, nor from the UI thread. That's the reason we prepare another thread and install a looper into it. Then we post our actions into that thread and that thread will be able to generate keypresses.


If you launch the program and press the "Generate keypresses" button, you will see how the text field above the button receives the keypresses we generated programmatically. At this point you may get excited and would try to generate keypresses for other applications. This will not work. Android applications are allowed to generate keypresses only for themselves. In WindowManagerService class, you will find a permission check controlling this behaviour.

 iget-object    v1,v12,com/android/server/WindowManagerService.mContext Landroid/content/Context;
 const-string    v2,"android.permission.INJECT_EVENTS"
 invoke-virtual    {v1,v2,v14,v15},android/content/Context/checkPermission    
                     ; checkPermission(Ljava/lang/String;II)I
 move-result    v1
 if-eqz    v1,l4a7e0
 const-string    v1,"WindowManager"
 new-instance    v1,java/lang/StringBuilder
 invoke-direct    {v1},java/lang/StringBuilder/    
                     ; ()V
 const-string    v2,"Permission denied: injecting key event from pid "

The android.permission.INJECT_EVENT permission is not that of the application, the WindowManagerService must have this permission otherwise requests to inject events into other applications' windows will be rejected. By default, WindowManagerService does not have this permission, that is why it is impossible to generate events for somebody else's window.

After all this diving into Android's internals, I show that there is a simpler way to generate key events by abusing the android.app.Instrumentation class. Check out the generateKeysWInst method in the example program. This method simply instantiates the Instrumentation class and calls only the sendKeyDownUpSync public method. This works because we know that sendKeyDownUpSync is so simple that it will function even with this bizarrely created instrumentation object. I don't know which method is more futureproof: using internal, non-public API or abusing a public API. Decide yourself.

Disassembling DEX files

One of the most remarkable features of the Dalvik virtual machine (the workhorse under the Android system) is that it does not use Java bytecode. Instead, a homegrown format called DEX was introduced and not even the bytecode instructions are the same as Java bytecode instructions. There was some discussion whether this makes Dalvik a Java virtual machine at all. My personal opinion is that this is a religious and legal dispute. Dalvik opcodes are clearly designed to support only the Java language. Compiling programs to Dalvik bytecode written in a language other than Java is certainly possible, as it was demonstrated with Java but neither the Java bytecode, nor the Dalvik bytecode makes any effort to support any language other than Java. This is in contrast with the .Net virtual machine where at least a claim has been made that the VM supports multiple languages - even though there are always limitations in any virtual machine that prevents running a particular language on a particular virtual machine.

Android comes with a disassembler called dexdump. The location of this tool is not intuitive, it runs on the Linux platform that hosts Android. Launch the emulator, and issue the following commands:

adb shell
dexdump

In order to use the tool, one has to move the DEX file to the Android platform (e.g. adb push in case of the emulator). Then one can say:

dexdump -d classes.dex

The output of this tool is not very easy to use, however. Take for example the bytecode compiled from the following switch statement.

000418: 2b02 0c00 0000                         |0000: packed-switch v2, 0000000c // +0000000c
00041e: 12f0                                   |0003: const/4 v0, #int -1 // #ff
000420: 0f00                                   |0004: return v0
000422: 1220                                   |0005: const/4 v0, #int 2 // #2
000424: 28fe                                   |0006: goto 0004 // -0002
000426: 1250                                   |0007: const/4 v0, #int 5 // #5
000428: 28fc                                   |0008: goto 0004 // -0004
00042a: 1260                                   |0009: const/4 v0, #int 6 // #6
00042c: 28fa                                   |000a: goto 0004 // -0006
00042e: 0000                                   |000b: nop // spacer
000430: 0001 0300 faff ffff 0500 0000 0700 ... |000c: packed-switch-data (10 units)

The jump table used by the packed-switch instruction is not disassembled at all, it is not even dumped entirely. The same problem applies to fill-array-data tables and there are further restrictions.

I decided therefore to create a more comfortable disassembler and here is the first cut.

Access the dedexer project's page on SourceForge.

This tool is easier to use than dexdump for many reasons. For starter, it is a standard Java program that runs on the usual JVMs. Its format is much more readable and is familiar to those who know the Jasmin syntax. For example the previous fragment is disassembled like this by dedexer:

.method public calc1(I)I
    packed-switch    v2,0
        ps418_422    ; case 0
        ps418_426    ; case 1
        ps418_42a    ; case 2
        default: ps418_default
ps418_default:
    const/4    v0,15
l420:
    return    v0
ps418_422:
    const/4    v0,2
    goto    l420
ps418_426:
    const/4    v0,5
    goto    l420
ps418_42a:
    const/4    v0,6
    goto    l420
    nop   
.end method

In addition, individual file is created for each class, along with the directory structure representing the package structure.

This is not a full decompiler, however. One has to know the Dalvik opcodes in order to work with the tool. This opcode list has been extended and maintained as dedexer was developed and is now in sync with the disassembler. You will see some unknown opcodes in the list. I have not encountered those instructions "out in the wild" and the disassembler does not recognize them either. If you see any of those, send me the DEX file so that I can analyse it!

This is a simple tool and is not without limitations. The most painful one is that the tool does not process the debug and annotation information in the DEX file. Array data dump could also be better. I am sure that the feature most people would like to see is a bridge toward Java class files but that is far away. Jasmin will be able to generate Java class files once the backward conversion from Dalvik opcodes to Java bytecode is provided but that's a complex task so don't hold your breath. The condition I set for myself as release condition is that the tool is able to disassemble the DEX file in framework.jar. It is able to, so I guess, the tool may be of use for others too. Enjoy!

The Dalvik opcodes

I wanted to continue with my adventures with the Android test framework but I ran into some troubles. With pre-1.0 SDKs my solution was simple in these cases: take apart the SDK's android.jar and decomplile the relevant classes. In 1.0 SDK, however, all the classes in android.jar are just stubs, at least in the version on the PC filesystem. The real classes are in DEX format, on the emulated device's file system.

That's sad news because the DEX format is not particularly well documented. More exactly: undocumented. There are some descriptions floating on the Internet but they are obsolete and inaccurate. Conveniently, the dx tool in Android SDK has some less used options that effectively document this format.

Dx is the utility that turns Java class files into DEX files. Every Android developer uses it regularly, although not everybody may be aware of its existence because the tool is invoked by automatically generated make/ant files. Dx has an option that dumps the content of the DEX file in human-readable format while generating the DEX file. This is the batch script I use to get that dump:

set BASEDIR=
javac %1\*.java
dx --dex --verbose --verbose-dump --dump-to=%BASEDIR%\%1\dexdump.txt --output=%BASEDIR%\%1\classes.dex %BASEDIR%\%1

Put your Java files into a subdirectory (e.g. test1) and invoke the batch script with the name of the directory. Beside the familiar classes.dex, dexdump.txt will be generated. This dump file is so verbose that reverse engineering of the DEX file format becomes something of a feasible project.

With using some test Java classes, the official Android opcode list and a lot of time, my first step was to document the Android opcodes. This is the bytecode the Dalvik virtual machine uses instead of the Java bytecode. If you are familiar with Java bytecode, you will see that the opcode set is pretty similar. Significant difference is that the Dalvik opcodes are register-based while Java bytecode is stack-based.

Click here to access the Dalvik opcode list.

The next step will be to put together a DEX disassembler. That will take some time, see you in 2009 with that!

Instrumentation and JUnit

JUnit has been nicely integrated into Android. JUnit classes are specialized to facilitate common Android testing tasks. In this post, I will talk about my experiences with InstrumentationTestRunner and the facilities it provides to integrate Android instrumentation with JUnit test execution.

As we have seen previously, the difficulty in JUnit-instrumentation integration stems from the fact that an instrumentation is an entire Android application, started, managed and terminated for testing purposes. One has to work quite a bit to make sure that the test controller is not terminated along with the application under test. InstrumentationTestRunner solves this problem by launching the Dalvik VM in special, instrumentation mode.

You can download the example program from here.

The test subject is our well known Calculator program that was renamed as Calculator2 so that we do not confuse it with the version coming from previous application packages, other than that it is the same simple program. Under aexp.calculator.tests, you will find two JUnit test classes. There are things to note, however.

• Instead of TestCase, the test classes inherit from ActivityInstrumentationTestCase, templated by the activity class under test.
• The constructor of the test class defines the activity under test class precisely.

One such test class or collection of test classes can be executed by InstrumentationTestRunner. Execute the following command (from command prompt).

adb shell am instrument -w aexp.calculator/android.test.InstrumentationTestRunner

The console of the command prompt reads like this:

aexp.calculator.tests.AddFunctionalTests:...
aexp.calculator.tests.SubFunctionalTests:...
Test results for InstrumentationTestRunner=......
Time: 11.448

OK (6 tests)

Meanwhile, the emulator main window flashes with action. Calculator2 is launched 4 times, each time the key input is automatically provided by the test case. All this is arranged by the Android specialization of TestCase/TestRunner.

Please observe the AndroidManifest.xml of the project. Check out the uses-library tag and the use of instrumentation tag, particularly the targetPackage attribute that refers to the application package under test (and not the Java package name of the test classes). InstrumentationTestRunner automagically looks for test classes that fit the test execution criteria (again, check out InstrumentationTestCase documentation for options), there was no need to organize the test classes into suites.

Note that the arrangement of this project is not typical. I mixed the test classes and the activity under test into the same application. This eliminates a lot of deployment problems that caused so much trouble for so many people when playing with the Android test framework. The typical deployment, however, is to place the test classes and application under test into separate application packages. I will get to that in the next post.

JUnit in Android

Now that we have the instrumentation framework in our basket and we are able to connect instrumentation objects with a test runner, it is time to put a bit of structure into out tests. The number of test cases grows quicky. If there is no way to organize them or they depend on each other in a subtle way, test case maintenance soon becomes a nightmare. Experience shows that in case of a resource-constrained project, test effort is the first to suffer cutbacks and if the test cases are not maintained properly, the team or the developer may soon feel that the test set is too much hassle compared to the value the tests provide. The result is a fallback to the default, "chaotic" way of development with the predictable drop of quality.

The popular JUnit test framework is integrated into Android. JUnit, if used properly, brings two major benefits to the test implementation.

• JUnit enforces the hierarchical organization of the test cases
• The pattern JUnit is based on guarantees the independence of the test cases and minimizes their interference.

Entire books have been written about JUnit and unit testing therefore I will restrict myself to the minimum in explaining the test framework. JUnit's main building block is the TestCase class. Actual test case classes are inherited from TestCase. One TestCase child class contains one or more test methods, these test methods are the real test cases and the TestCase descendants are really already test groups. By convention, the test method names are prefixed with "test" (like testThis(), testThat(), etc.). JUnit can discover the test methods by itself if this convention is respected, otherwise the test method names have to be declared one by one.

The most important impact of using JUnit is the way one test method is executed. For each test method, the TestCase descendant class is instantiated, its setUp() method is invoked, then the test method in question is invoked, then the tearDown() method is invoked then the instance becomes garbage. This is repeated for each test method. This guarantees that test methods are independent of each other, their interference is minimized. Of course, "clever" programmers can work around this pattern and implement test cases that depend on each other but this will bring us back to the mess that was to be eliminated in the first place. JUnit also provides ways to collect test classes into test suites and organize these suites hierarchically.

JUnit has been included into Android and Android-specific extensions were provided in the android.test package. Android test cases classes should inherit from android.test.AndroidTestCase instead of junit.framework.TestCase. The main difference between the two is that AndroidTestCase knows about the Context object and provides method to obtain the current Context. As many Android API methods need the Context object, this makes coding of Android test cases much easier. AndroidTestCase already contains one test method that tests the correct setup of the test case class, the testAndroidTestCaseSetupProperly method. This adds one test method to every AndroidTestCase descendant but this fact rarely disturbs the programmer.

Those familiar with the "big", PC-based JUnit implementations will miss a UI-oriented TestRunner. The android.test.AndroidTestRunner does not have any user interface (not even console-based UI). If you want to get any readable feedback out of it, you have to handle callbacks from the test runner.

You can download the example program from here.

Our example program contains a very simple test runner UI, implemented as an Activity. The UI provides just the main progress indicators, details are written into the log so this implementation is nowhere near to the flexible test runners of the "big" JUnit. The test suite contains two test case classes. One of them (the MathTest) is really trivial. It demonstrates, however, the hidden testAndroidTestCaseSetupProperly() test method that explains the two extra test cases (the test runner will display 5 test cases when we have really only 3). The main lesson from the other test case class (ContactTest) is that individual test cases must be made independent from each other. This test case class inserts and deletes the test contact for each test method execution, cleaning up its garbage after each test execution. This is the effort that must be made to minimize interference. ExampleSuite organizes these two test classes into a suite. As we respected the JUnit test method naming conventions, we can leave the discovery of test methods to JUnit.



At this point, we have everything to write structured, easy to maintain tests for Android, using the Android test instrumentation mechanism to drive the UI. This will be my next step.

Controlling instrumentation

Those who are familiar with test frameworks could have felt something missing after the previous instrumentation example. The test did not finish very elegantly, both the test launcher and the test program were terminated and the results should be fished out from the logs. The reason is that when the instrumentation finishes, it terminates the entire application, not just the activity that was instrumented. Although application as a notion exists since the beginning of Android's public life, developers usually concentrate on Activities. Application is a bunch of artifacts packed into one apk file, having one manifest file, running in the same JVM slice (seemingly independent JVM simulated for each application by the Dalvik virtual machine), represented by the same Application object. Instrumentation works on application level (as opposed to activity level) and when an instrumentation is finished, the entire application is terminated. That's why our instrumentation launcher did not survive the end of instrumentation - as it lived in the same application, it was also terminated along with the instrumentation object and the target application.

If we want to build a decent automated test framework, we have to control it from a separate application. This example does just that.

You can download the example program from here.

In the package, you will find two application directories. The instrumentation1 directory contains our friends, the slightly modified calculator test target, the instrumentation object and the instrumentation launcher that we will not use now. The instrcontroller directory contains a separate application, our instrumentation controller that starts the instrumentation and receives the test result. Like this:


The only interesting part is the communication between the instrumentation object and the launcher. The instrumentation object has a finish() method that is seemingly capable of sending back a result Bundle to the instrumentation's starter but I was not able to figure out, how that bundle is received by the instrumentation's starter (my Android newsgroup thread also remained unanswered). Therefore I had no better idea than to create a not too elegant do-it-yourself method of sending back the test result using broadcast intents. If anyone knows how to do it right, please notify me.

And before I finish, something completely different.

I received a mail from the Phoload people that they launched their Android content and they asked me to advertise this fact in one of my posts. Certainly, it is a new market, there is a lot of risk taking here so the early birds definitely deserve help - however small mine can be. I did have my concerns, however, how this Phoload site would coexist e.g. with Android Marketplace but the Phoload people are convinced that they can carve out a nice piece of market by offering mobile applications for multiple platforms and by providing easier navigation and more visible place for applications. Let they be right and have success!