Wednesday, May 13, 2009

About quick method invocation

A good 3 months ago I wrote about the ODEX format when support for that DEX variant was added to the dedexer tool. Then I asked if there is anybody out there who knows, how the index in the invoke-virtual-quick Dalvik instruction can be interpreted. For example:

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


That 3BH is an offset but into what? I did not know, therefore dedexer does not interpret the offset which makes its output on ODEX files less useful. Then Nenik (nickname according to his request) finally gave me the solution. Here comes his mail, verbatim.

The index computation is pretty simple, but for reverse analysis you need more data.

The vtable contains all the methods that can be invoked by invoke-virtual, that is
all nonprivate member methods (even those final and native).
The vtable is obviously constructed by copying superclass's vtable, then replacing
overridden methods and appending all additional virtual methods.

The methods in the vtable are ordered as they were in the dex file.
Let's look at android.view.KeyCharacterMap for example. It extends java.lang.Object,
so it starts with:
Object:
0: .method protected clone()Ljava/lang/Object;
1: .method public equals(Ljava/lang/Object;)Z
2: .method protected finalize()V
3: .method public final native getClass()Ljava/lang/Class;
4: .method public native hashCode()I
5: .method public final native notify()V
6: .method public final native notifyAll()V
7: .method public toString()Ljava/lang/String;
8: .method public final wait()V
9: .method public final wait(J)V
a: .method public final native wait(JI)V

Then it replaces:
2: .method protected finalize()V
with the implementation from KeyCharacterMap

and adds:
b: .method public get(II)I
c: .method public getDisplayLabel(I)C
d: .method public getEvents([C)[Landroid/view/KeyEvent;
e: .method public getKeyData(ILandroid/view/KeyCharacterMap$KeyData;)Z
f: .method public getKeyboardType()I
10: .method public getMatch(I[C)C
11: .method public getMatch(I[CI)C
12: .method public getNumber(I)C
13: .method public isPrintingKey(I)Z

Anyway,
invoke-virtual-quick {v1},vtable #0x2
on an instance of any kind is simply the quick variant of
invoke-virtual {v1}, Ljava/lang/Object;.finalize:()V


Obviously for decoding invoke-virtual-quick opcodes inside, say,
framework.odex, you need the coresponding core.odex and ext.odex
to reconstruct the vtables of all the base classes.

An .odex file contains a list of such dependencies appended
after the body of the encapsulated dex, together with their SHA-1s:


00498D10 44 6E 95 3A │ 13 BC 10 91 │ 0E 00 00 00 │ 02 00 00 00 Dn.:.¼..........
00498D20 1C 00 00 00 │ 2F 73 79 73 │ 74 65 6D 2F │ 66 72 61 6D ..../system/fram
00498D30 65 77 6F 72 │ 6B 2F 63 6F │ 72 65 2E 6F │ 64 65 78 00 ework/core.odex.
00498D40 93 97 93 82 │ 99 DA 46 4E │ E2 13 DD 35 │ 4C 48 B5 7B .....ÚFNâ.Ý5LHµ{
00498D50 F0 06 51 D7 │ 1B 00 00 00 │ 2F 73 79 73 │ 74 65 6D 2F ð.Q×..../system/
00498D60 66 72 61 6D │ 65 77 6F 72 │ 6B 2F 65 78 │ 74 2E 6F 64 framework/ext.od
00498D70 65 78 00 54 │ F1 D0 82 95 │ 97 53 15 60 │ E4 D6 2C 48 ex.TñÐ...S.`äÖ,H
00498D80 8E 36 51 C5 │ 75 BE 2C 00 │ 50 4B 4C 43 │ 08 80 01 00 .6QÅu¾,.PKLC....
00498D90 08 80 01 00 │ 00 20 00 00 │ 00 00 21 AA │ C2 5C 31 00 ..... ....!ªÂ\1.


With all this data, it should be possible to reconstruct .dex from current
.odex format, something I would like to be able to do.


Thanks, Nenik, this is the information I needed to improve the dedexer tool. I will do that soon. If anyone has something to add, please, comment.

Thursday, May 7, 2009

Two books on Android

I have reviewed two Android books recently and now, that both are in press, I decided to write some words about the experience. The first book is Ed Burnette's Hello Android (The Pragmatic Programmers, ~22 USD).



The book is clearly written with newcomers in mind who want to produce something functional quickly. Innovative feature is the "fast forward" section at the end of each chapter. This guides the inpatient reader who don't want to read sequentially to other relevant section, much like a hypertext link. Then the book goes through the application model, user interface, 2D and 3D graphics (yes, it has a functional OpenGL example), multimedia, web programming and database issues. The book seems to concentrate on developers of UI-intensive applications, for example the Android service and content provider concepts are mentioned only shortly, meanwhile there is an abundance of UI-related examples, even advanced ones like 3D graphics. The integration of JavaScript and Java in the web programming section was a revelation for me, I did not know about the mechanism before reading the book and it is cool indeed.

The other book is Unlocking Android from Ableson, Collins and Sen (Manning, ~29$).



This book definitely has higher ambitions. It is longer than the previous one (~400 vs. ~200 pages) and expects sequential reading. Beside the usual topics, it ventures into such exotic areas like Linux-level programming in C in the Android environment. Curiously, this breadth of topics means that the Manning book deals less with UI-programming than Burnette's book (82 pages in the Burnette book vs. 62 pages in the Manning book).The Manning book does provide, however, a detailed view of Android programming model. It discusses Android services extensively and even presents, how to write a content provider (although not in detail).

To summarize, the two books follow different concepts. Burnette's book is, erm, pragmatic. It tries to make the reader productive as quickly as possible using the most common application type, the UI-intensive standalone application, with some web programming thrown in for good measure. Meanwhile, it omits a great deal of Android architecture. The Manning book builds systematically, by presenting the architectural concepts in detail. Decide yourself, which one suits you most. I enjoyed reading both.

Thursday, February 5, 2009

Asynchronous communication in Android

Old sins always come back to haunt. Once I wrote a blog post, shamelessly referring to a 2006 paper of mine. In that post, I praised the conformance of the Android system with regards to the requirements of the reflective middleware approach. I found that only one area was not covered appropriately, asynchronous communication. It could be then expected that when folks at Softwired ported their iBus//Mobile asynchronous communication framework to Android, they found me.

iBus//Mobile already supports a number of clients. For Java, there is J2SE, CDC and MIDP support, Android was just added to this list. Additionally, native clients like Windows CE and Symbian are also supported and all these clients are able to talk to each other using the iBus//Mobile queuing system. In Java, the access interface is the familiar JMS.

iBus//Mobile depends on a gateway on the network and each client talks to this gateway. Even if device-to-device communication is required, the data goes through the gateway. The protocol support is nicely done, the framework supports a bunch of protocols. Some are used in polling mode (e.g. HTTP), some of them, however, also work in push mode like the TCP or SMS bearers. In case of TCP, they maintain a TCP stream to the gateway, keep that stream alive with keepalive messages and push the device-bound messages over the gateway-device direction of this stream. The programmer has full control over the protocol selection. Also, there is pluggable encryption support.

Those who have not yet tried cannot even imagine, how time-consuming it can be to implement such a system. It sounds simple but when it comes to actually implement the communication between the client and the server parts, unpleasant surprises will pop up, e.g. about the differences of mobile networks with regards to timing, connection keepalive, etc.

How does iBus//Mobile compare to my dream system I envisioned in my paper? First, it is nicely componentized although not along the line of the Android component system. There is a pluggable protocol support which is a great feature, it is hard to survive without it in the mobile world. My dream system included protocol support for direct device-to-device communication (e.g. Bluetooth). This is missing in iBus//Mobile which may be due to their business requirements. I can imagine a creative usage of multiple protocols at the same time on the client side, e.g. falling back to SMS from TCP if packet data connection is not available or using SMS to trigger data push by e.g. HTTP to simulate a push bearer that can transfer large amount of data. I also find the relationship between queues and synchronization intriguing. iBus//Mobile uses a sliding window-based algorithm to ensure that there can be multiple queue items transmitted independently from each other at the same time. If off-line operation is a frequent requirement (e.g. the application puts large number of elements into the queue then connects to the server to deliver those elements), full-scale synchronization solution is more efficient.

But enough of the whining! Softwired provides a robust, field-tested solution to Android developers who need message queues. You'd better know about iBus//Mobile if you don't want to suffer in the weird world of mobile bearers, particularly in the push direction.

Tuesday, February 3, 2009

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.

Monday, January 19, 2009

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.

Friday, January 9, 2009

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!

Saturday, December 13, 2008

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!