03 Sept. 2012: Android Optimizer bug: while(True){ bootscreen(); }
                 Android Optimizer bug - endless booting
                             Patrick Schulz 2012
                              team@dexlabs.org

-- "while(True){ bootscreen(); }"

1. Android Optimizer and Verifier

  The Android system comes with an Optimizer and Verifier for applications. This 
  tool is called dexopt. Its primary task is to verify the dalvik bytecode of 
  applications and optimize the bytecode for efficient execution. Dexopt [1] is 
  a native program which uses libdex / dvm  [1] in order to parse the dex file 
  and interpret the dalvik bytecode. It will be called for every application when 
  it gets installed on an Android device. If the verification fails the 
  application gets rejected and will not be installed on the device. After the 
  applications has been verified dexopt generates an optimized version of it. 
  This will be stored for later execution in the dalvik-cache directory. These 
  two steps will also be executed when the devices boots up for all applications 
  which haven't been optimized before. 

  The verification is not a security feature in the first place! It is easy to 
  circumvent most parts of it where it is not recommended for application 
  developers to do so. Dexopt checks the dex file structure and does a detailed 
  bytecode analysis. By this the installation process can reject broken 
  applications early before they can be executed. The verification of the 
  bytecode has another very important advantage. The optimizing engine can 
  assume much stricter preconditions on the bytecode, which results in better 
  optimization.

  At the moment we are more interested in the  dalvik bytecode 
  analysis/optimization. Dexopt analyzes all methods for all classes within 
  the dex file. This will be done by a linear sweep algorithm which iterates 
  over the bytecode. For each instruction different checks/optimization steps 
  will be executed.

hexedit vs. dexopt  - Let's go...


2. Bug

  While playing around with some of our handcrafted dex files we discovered that 
  the installation of one of these stucks into a endless loop. So we investigated 
  into this issue.
  We started looking at the process list on the Android device while the 
  installation is still in "progress". The reason was easy to spot. A dexopt 
  process was creating 100% CPU load.
21379  1  100% R     1  66656K   4944K     u0_a79   /system/bin/dexopt
A quick check confirmed that it was caused by our APK.
cat /proc/21379/cmdline
  /system/bin/dexopt --zip 8 11 /data/app/org.dexlabs.poc-1.apk m=y
Ok, let's go deeper and see what's going on in dexopt. We started gdbserver on the device and attached it to the running dexopt process.
gdbserver –attach 0.0.0.0:9999 21379
On the local machine we started the a gdb client, which comes with the Android NDK, and connected via wifi to our Android device.
arm-linux-androideabi-gdb
gdb$ target extended-remote 10.0.23.2:9999
gdb$ info register
r0             0x0	0x0
r1             0x0	0x0
r2             0x17	0x17
r3             0x0	0x0
r4             0x405e2566	0x405e2566
r5             0x41f8e1d0	0x41f8e1d0
r6             0xb	0xb
r7             0x1	0x1
r8             0x8	0x8
r9             0x100	0x100
r10            0x2	0x2
r11            0x0	0x0
r12            0x402c9f6c	0x402c9f6c
sp             0xbec329d8	0xbec329d8
lr             0x4027ce21	0x4027ce21
pc             0x4027ce0c	0x4027ce0c
cpsr           0x20000030	0x20000030
After stepping through some instructions we knew that we were in a (short) loop. The memory map of the process told us that the loop is located in the shared object dvm.so
cat /proc/21379/maps
...
40220000-402c2000 r-xp 00000000 103:00 266       /system/lib/libdvm.so
...
Nice, it shouldn't be that hard to find the reason for this looping behavior due to the sources of libdvm are available online [1]. The loop is within the method "optimizeMethod" in vm/analysis/Optimize.cpp
static void optimizeMethod(Method* method, bool essentialOnly)
{
    bool needRetBar, forSmp;
    u4 insnsSize;
    u2* insns;

    if (dvmIsNativeMethod(method) || dvmIsAbstractMethod(method))
        return;

    forSmp = gDvm.dexOptForSmp;
    needRetBar = needsReturnBarrier(method);

    insns = (u2*) method->insns;
    assert(insns != NULL);
    insnsSize = dvmGetMethodInsnsSize(method);

    while (insnsSize > 0) {
        Opcode opc, quickOpc, volatileOpc;
        size_t width;
        bool matched = true;

        opc = dexOpcodeFromCodeUnit(*insns);
        width = dexGetWidthFromInstruction(insns);
        volatileOpc = OP_NOP;
        
...

        assert(width > 0);
        assert(width <= insnsSize);
        assert(width == dexGetWidthFromInstruction(insns));

        insns += width;
        insnsSize -= width;
    }

    assert(insnsSize == 0);
}
It's easy to see that this is an endless loop if we hit an instruction with a width of 0. The width is determined using the function "dexGetWidthFromInstruction", which can be found in libdex/InstrUtils.cpp
/*
 * Return the width of the specified instruction, or 0 if not defined.  Also
 * works for special OP_NOP entries, including switch statement data tables
 * and array data.
 */
size_t dexGetWidthFromInstruction(const u2* insns)
{
    size_t width;

...
        width = dexGetWidthFromOpcode(dexOpcodeFromCodeUnit(insns[0]));
    }

    return width;
}
The comment says, this function returns 0 for not defined/unused instructions. This is exact the case for our handcrafted dex file. We had injected an unused Opcode into the dalvik bytecode of a method, results in this endless loop. But wait, there was a check at the end of the loop for this case:
assert(width > 0);
The point is, asserts are removed by the compiler for release versions. Ups.. 3. Impact This bug can be easily triggered by an postcompiled manipulated APK file. We simply have to inject an unused Opcode into the bytecode stream. We also have to do some further manipulations in order to skip some verification steps. The optimizing engine now tries to process this bytecode and will end up in an endless loop. This happens when we try to install this particular APK on an Android phone, regardless on which way the APK gets installed. The installation process will not end due to the optimizer is still running. The only way to stop this is to get an root shell and kill the dexopt process. Trying to reboot doesn't help. It makes it even worse. When the systems boots up it starts optimizing all unoptimized applications and so our manipulated APK. Due to the fact Android waits for the optimizer to finish the system will not boot up completely. The phone will remain in the boot process showing the bootscreen. The only way to get your phone back is to kill dexopt. But this is only possible when you have a root shell e.g. via ADB. After this you should remove all manipulated APK and DEX file from the phone. Beside using a root shell you can do it via an custom recovery image. If you have no root access or an custom recovery image, which lets you delete these files, you have to reflash your phone. Be aware you will lose your data by this! A demo video showing this behavior is available [3]. 4. Solution Google has been informed about this issue in may 2012. But until now no patch has been rolled out. The fix is a very simple one. Just include a check like the assert(width>0) also in release versions e.g. by using an if construct. Until an update will be provided for your phone, you have to take care about this on your own. You can do this by checking the dalvik bytecode of every new application by hand or using our online scanner [2]. [1] https://android.googlesource.com/platform/dalvik/ [2] http://www.dexlabs.org/bytecodescanner/ [3] https://www.youtube.com/watch?v=wKTF-8otiYs
< Blog List