The Great Android Security Hole Of ’08 ? – Part Seven: The Gory Details — The Loading Classes From The ‘Wrong’ classes.dex Edition

As we have seen, during the construction of the PathClassLoader to be used as an application’s ClassLoader the function dvmJarFileOpen is used to open an application’s APK.

dvmJarFileOpen in turn calls dexZipOpenArchive which calls parseZipArchive.

The function parseZipArchive is the equivalent of the java.util.ZipFile readCentralDirectory method.

It is responsible for reading the Central Directory and populating a hashtable which maps file names to File Headers.

1.0 parseZipArchive Again

Source: $(ANDROID_SRC)/dalvik/libdex/ZipArchive.cpp

    static int parseZipArchive(ZipArchive* pArchive)
    {
        int result = -1;
        const u1* cdPtr = (const u1*)pArchive->mDirectoryMap.addr;
        size_t cdLength = pArchive->mDirectoryMap.length;
        int numEntries = pArchive->mNumEntries;

        /*
         * Create hash table.  We have a minimum 75% load factor, possibly as
         * low as 50% after we round off to a power of 2.  There must be at
         * least one unused entry to avoid an infinite loop during creation.
         */
        pArchive->mHashTableSize = dexRoundUpPower2(1 + (numEntries * 4) / 3);
        pArchive->mHashTable = (ZipHashEntry*)
                calloc(pArchive->mHashTableSize, sizeof(ZipHashEntry));

        /*
         * Walk through the central directory, adding entries to the hash
         * table and verifying values.
         */
        const u1* ptr = cdPtr;
        int i;
        for (i = 0; i < numEntries; i++) {
            if (get4LE(ptr) != kCDESignature) {
                ALOGW("Zip: missed a central dir sig (at %d)", i);
                goto bail;
            }
            if (ptr + kCDELen > cdPtr + cdLength) {
                ALOGW("Zip: ran off the end (at %d)", i);
                goto bail;
            }

            long localHdrOffset = (long) get4LE(ptr + kCDELocalOffset);
            if (localHdrOffset >= pArchive->mDirectoryOffset) {
                ALOGW("Zip: bad LFH offset %ld at entry %d", localHdrOffset, i);
                goto bail;
            }

            unsigned int fileNameLen, extraLen, commentLen, hash;
            fileNameLen = get2LE(ptr + kCDENameLen);
            extraLen = get2LE(ptr + kCDEExtraLen);
            commentLen = get2LE(ptr + kCDECommentLen);

            /* add the CDE filename to the hash table */
            hash = computeHash((const char*)ptr + kCDELen, fileNameLen);
            addToHash(pArchive, (const char*)ptr + kCDELen, fileNameLen, hash);

            ptr += kCDELen + fileNameLen + extraLen + commentLen;
            if ((size_t)(ptr - cdPtr) > cdLength) {
                ALOGW("Zip: bad CD advance (%d vs %zd) at entry %d",
                    (int) (ptr - cdPtr), cdLength, i);
                goto bail;
            }
        }
        ALOGV("+++ zip good scan %d entries", numEntries);

        result = 0;

    bail:
        return result;
    }

The function is passed a pointer to a ZipArchive struct which represents the ZIP file.

    struct ZipArchive {
        /* open Zip archive */
        int         mFd;

        /* mapped central directory area */
        off_t       mDirectoryOffset;
        MemMapping  mDirectoryMap;

        /* number of entries in the Zip archive */
        int         mNumEntries;

        /*
         * We know how many entries are in the Zip archive, so we can have a
         * fixed-size hash table.  We probe on collisions.
         */
        int         mHashTableSize;
        ZipHashEntry* mHashTable;
    };

At this point the Central Directory of the ZIP file has been mapped into memory.

The function starts by allocating the memory for the hashtable which maps file names to File Headers.

The hashtable is implemented as a fixed size linear hashtable which maps file names to ZipHashEntry structs.

The struct ZipHashEntry is defined like this

    struct ZipHashEntry {
    const char*     name;
    unsigned short  nameLen;
};

and the allocated hashtable is simply an array of them.

The size of the hashtable is a power of two so the computation x mod hashtable size can be ‘optimized’.

Having allocated the hashtable it iterates over the File Headers in the Central Directory. For each one it does some basic sanity checking and then adds a pointer to the file name to the hashtable using the addToHash function.

Note that like the readCentralDirectory method it does not check to see whether there is more than one file with the same name.

1.1 computeHash

Source: $(ANDROID_SRC)/dalvik/libdex/ZipArchive.cpp

    static unsigned int computeHash(const char* str, int len)
    {
        unsigned int hash = 0;

        while (len--)
            hash = hash * 31 + *str++;

        return hash;
    }

The computeHash employs the canonical java.lang.String hashCode algorithm.

1.2 addToHash Again

Source: $(ANDROID_SRC)/dalvik/libdex/ZipArchive.cpp

    static void addToHash(ZipArchive* pArchive, const char* str, int strLen, unsigned int hash)
    {
        const int hashTableSize = pArchive->mHashTableSize;
        int ent = hash & (hashTableSize - 1);

        /*
         * We over-allocated the table, so we're guaranteed to find an empty slot.
         */
        while (pArchive->mHashTable[ent].name != NULL)
            ent = (ent + 1) & (hashTableSize-1);

        pArchive->mHashTable[ent].name = str;
        pArchive->mHashTable[ent].nameLen = strLen;
    }

The function addToHash starts by computing ent, the index at which to add the entry for the name.

The index is simply the hash value mod the hashtable size.

It then examines the entry at the index ent. If the entry is empty it adds the name there, otherwise it proceeds to look for the next empty entry.

Since the size of the hashtable is larger than the number of entries it is guaranteed to find one.

1.3 Example

Given the Central Directory of the APK shown in this example then the addition of the names to the hashtable by the parseZipArchive function goes like this.

Note that there are 16 files in the example APK so the size of the hashtable is 32.

The first seven names are all added without collisions.

Name	Hash	Index Of Entry
res/layout/activity_main.xml	3289686140	28
res/menu/activity_main.xml	3702837041	17
AndroidManifest.xml	4186266567	7
resources.arsc	810769514	10
res/drawable-hdpi/ic_action_search.png	2475784161	1
res/drawable-hdpi/ic_launcher.png	1773930598	6
res/drawable-ldpi/ic_launcher.png	138633698	2

The name res/drawable-mdpi/ic_action_search.png hashes to 679672038, which mod 32 is 6, so it collides with res/drawable-hdpi/ic_launcher.png.

The next index is 7 which gives another collision, this time with AndroidManifest.xml.

The entry at is 8 is empty, so it is added here.

The name res/drawable-mdpi/ic_launcher.png hashes to 4024776769 which mod 32 is 1 so it collides with res/drawable-hdpi/ic_action_search.png.

It collides again at 2 with res/drawable-ldpi/ic_launcher.png, and is added at 3.

The next three names are added without collisions

Name	Hash	Index Of Entry
res/drawable-xhdpi/ic_action_search.png	2409726889	9
res/drawable-xhdpi/ic_launcher.png	3887447966	30
classes.dex	4055048783	15

Then classes.dex is added for the second time.

This necessarily collides with the existing entry for the first classes.dex at 15.

The entry at 16 is empty so it is added there.

The name META-INF/MANIFEST.MF hashes to 1539143842 which mod 32 is 2 so it collides with
res/drawable-ldpi/ic_launcher.png.

It collides again with res/drawable-mdpi/ic_launcher.png at 3 before being added at 4.

The name META-INF/CERT.SF hashes to 3935803975 which mod 32 is 7 so it collides with AndroidManifest.xml

It then collides three more times at 8, 9, and 10 with

• res/drawable-mdpi/ic_action_search.png
• res/drawable-xhdpi/ic_action_search.png
• resources.arsc

respectively before being added at 11.

The name META-INF/CERT.RSA hashes to 1750838444 which mod 32 is 12. The entry is empty so it is added at 12.

After all that the hashtable looks like this

Index	Name
0:	<empty>
1:	res/drawable-hdpi/ic_action_search.png
2:	res/drawable-ldpi/ic_launcher.png
3:	res/drawable-mdpi/ic_launcher.png
4:	META-INF/MANIFEST.MF
5:	<empty>
6:	res/drawable-hdpi/ic_launcher.png
7:	AndroidManifest.xml
8:	res/drawable-mdpi/ic_action_search.png
9:	res/drawable-xhdpi/ic_action_search.png
10:	resources.arsc
11:	META-INF/CERT.SF
12:	META-INF/CERT.RSA
13:	<empty>
14:	<empty>
15:	classes.dex
16:	classes.dex
17:	res/menu/activity_main.xml
18:	<empty>
19:	<empty>
20:	<empty>
21:	<empty>
22:	<empty>
23:	<empty>
24:	<empty>
25:	<empty>
26:	<empty>
27:	<empty>
28:	res/layout/activity_main.xml
29:	<empty>
30:	res/drawable-xhdpi/ic_launcher.png
31:	<empty>

1.4 dexZipFindEntry Again

    ZipEntry dexZipFindEntry(const ZipArchive* pArchive, const char* entryName)
    {
        int nameLen = strlen(entryName);
        unsigned int hash = computeHash(entryName, nameLen);
        const int hashTableSize = pArchive->mHashTableSize;
        int ent = hash & (hashTableSize-1);

        while (pArchive->mHashTable[ent].name != NULL) {
            if (pArchive->mHashTable[ent].nameLen == nameLen &&
                memcmp(pArchive->mHashTable[ent].name, entryName, nameLen) == 0)
            {
                /* match */
                return (ZipEntry)(long)(ent + kZipEntryAdj);
            }

            ent = (ent + 1) & (hashTableSize-1);
        }

        return NULL;
    }

As you would expect the dexZipFindEntry function uses exactly the same algorithm to find an entry matching the given name as addToHash does to find where to add a given name.

The return value is a ZipEntry which is defined like this

    typedef void* ZipEntry;

Because NULL is returned when an entry is not found, the constant kZipEntryAdj has to be added to the value to be returned when an entry is found in case it is at index 0.

1.5 Example Continued

Having used the function dexZipOpenArchive to open the application’s APK, dvmJarFileOpen then calls the function dexZipFindEntry to find the application’s classes.dex file.

Continuing the example above, when dexZipFindEntry is passed the string

    "classes.dex"

it will compute the hash which gives 4055048783, which mod 32 is 15 as we know.

The entry at 15 will match and dexZipFindEntry will return.

We know that this is the entry for the first classes.dex in the APK.

We also know that this is the classes.dex file which did not get verified during installation.

---

Copyleft (c) 2013 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

The Great Android Security Hole Of ’08 ? – Part Three: dalvik.system.PathClassLoader

When an Android application is launched an instance of dalvik.system.PathClassLoader is created for use as the application’s ClassLoader.

The dalvik.system.PathClassLoader constructor is passed a ‘path’ which includes the application’s APK.

1.0 PathClassLoader

Class: dalvik.system.PathClassLoader

Source: $(ANDROID_SRC)/libcore/dalvik/src/main/java/dalvik/system/PathClassLoader.java

1.1 The Constructor

    public PathClassLoader(String dexPath, ClassLoader parent) 
    {
        super(dexPath, null, null, parent);
    }

The PathClassLoader constructor simply invokes the constructor of the super class which is BaseDexClassLoader.

2.0 BaseDexClassLoader

Class: dalvik.system.BaseDexClassLoader

Source: $(ANDROID_SRC)/libcore/libdvm/src/main/java/dalvik/system/BaseDexClassLoader.java

2.1 The Constructor

    public BaseDexClassLoader(String dexPath, File optimizedDirectory, String libraryPath, ClassLoader parent) 
    {
        super(parent);
        this.pathList = new DexPathList(this, dexPath, libraryPath, optimizedDirectory);
    }

The BaseDexClassLoader constructor creates an instance of DexPathList which it will use when attempting to load classes.

It passes the DexPathList constructor itself plus its dexPath, libraryPath and optimizedDirectory arguments.

3.0 DexPathList

Class: dalvik.system.DexPathList

Source: $(ANDROID_SRC)/libcore/libdvm/src/main/java/dalvik/system/DexPathList.java

3.1 The Constructor

    public DexPathList(ClassLoader definingContext, String dexPath, String libraryPath, File optimizedDirectory)

The constructor calls the method makeDexElements to create an array of Elements.

An Element represents either a directory, a Dex file, or a ZIP file which was specified in the dexPath argument.

3.2 makeDexElements

    private static Element[] makeDexElements(ArrayList<File> files, File optimizedDirectory)

The method iterates over the elements in the files argument.

If the name of the File ends with one of

• .apk

• .jar

• .zip

it invokes the loadDexFile method passing it the File and the optimizedDirectory argument.

3.3 loadDexFile

    private static DexFile loadDexFile(File file, File optimizedDirectory)

If the optimizedDirectory argument is null then the method creates a DexFile instance passing the File argument to the constructor.

4.0 DexFile

Class: dalvik.system.DexFile

Source: $(ANDROID_SRC)/libcore/libdvm/src/main/java/dalvik/system/DexFile.java

Source: $(ANDROID_SRC)/dalvik/vm/native/dalvik_system_DexFile.cpp

4.1 DexFile(File)

    public DexFile(File file) throws IOException {
        this(file.getPath());
    }

4.2 DexFile(String)

    public DexFile(String fileName) throws IOException

This constructor calls the method openDexFile passing it the fileName argument, null, and 0.

4.3 openDexFile

    native private static int openDexFile(
                                  String sourceName, 
                                  String outputName,
                                  int    flags) 
                              throws 
                                 IOException;

If the sourceName argument does not end with the suffix “.dex”, openDexFile calls the function dvmJarFileOpen passing it the C++ equivalents of its sourceName and outputName arguments plus a pointer to a JarFile* on the stack and false.

5.0 JarFile

Source: $(ANDROID_SRC)/dalvik/vm/JarFile.cpp

5.1 dvmJarFileOpen

     int dvmJarFileOpen(const char* fileName, const char* odexOutputName, JarFile** ppJarFile, bool isBootstrap)

The function starts by calling the function dexZipOpenArchive to open the named file.

If this is successful it then calls the function dexZipFindEntry to find the classes.dex file within the ZIP file.

6.0 ZipArchive

Source: $(ANDROID_SRC)/dalvik/libdex/ZipArchive.cpp

6.1 dexZipOpenArchive

     int dexZipOpenArchive(const char* fileName, ZipArchive* pArchive)

The function attempts to open the named file using the open system call.

If this is successful it then calls dexZipPrepArchive passing it the file descriptor returned by the call to open
and the fileName and pArchive arguments.

6.2 dexZipPrepArchive

    int dexZipPrepArchive(int fd, const char* debugFileName, ZipArchive* pArchive)

The function dexZipPrepArchive starts by mapping the Central Directory of the ZIP file into memory using the function mapCentralDirectory.

It this is successful it then calls parseZipArchive

6.2 parseZipArchive

    static int parseZipArchive(ZipArchive* pArchive)

The parseZipArchive function begins by creating a linear hash table.

It then iterates over the File Headers in the Central Directory.

For each File Header it calls the function addtoHash to create an entry in the linear hash table using the file name from the file header as the key.

The entry allocated within the linear hash table contains the address of the file name field within the File Header and the length of the file name.

Given the address of the file name field it is possible to determine the address of the File Header itself within the Central Directory.

6.4 addToHash

    static void addToHash(ZipArchive* pArchive, const char* str, int strLen, unsigned int hash)
    {
        const int hashTableSize = pArchive->mHashTableSize;
        int ent = hash & (hashTableSize - 1);

        /*
         * We over-allocated the table, so we're guaranteed to find an empty slot.
         */
        while (pArchive->mHashTable[ent].name != NULL)
            ent = (ent + 1) & (hashTableSize-1);

        pArchive->mHashTable[ent].name = str;
        pArchive->mHashTable[ent].nameLen = strLen;
   }

6.5 dexZipFindEntry

    ZipEntry dexZipFindEntry(const ZipArchive* pArchive, const char* entryName)
    {
        int nameLen = strlen(entryName);
        unsigned int hash = computeHash(entryName, nameLen);
        const int hashTableSize = pArchive->mHashTableSize;
        int ent = hash & (hashTableSize-1);

        while (pArchive->mHashTable[ent].name != NULL) {
            if (pArchive->mHashTable[ent].nameLen == nameLen &&
                memcmp(pArchive->mHashTable[ent].name, entryName, nameLen) == 0)
            {
                /* match */
                return (ZipEntry)(long)(ent + kZipEntryAdj);
            }

            ent = (ent + 1) & (hashTableSize-1);
        }

        return NULL;
    }

---

Copyright (c) 2013 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

“Alien Dalvik” ?

It is going to be interesting to find out exactly how this works.

Despite the name it cannot simply be a standalone Dalvik port. After all, all Dalvik can do is run Dexes. In fact the following would seem to suggest that it might not involve a Dalvik VM at all

Alien Dalvik enables the majority of Android applications to run unmodified, allowing application store owners to quickly kick start Android application store services by simply repackaging Android Package (APK) files.

Its not clear why you would want to mess with the APKs unless you wanted to do something else at the same time, especially if they are signed, but who knows ?

Presumably unmodified in this context refers to the source code ?

To run the majority of Android applications unmodified it must implement all the standard Java APIs and the Android APIs used by those applications some how. If the source code does not need to be modified then all those classes and methods that are referenced need to be in the runtime.

Implementing a large part of what is approximately Java 5 plus a large part of some version of the Android APIs (which version is of course another problem) is not exactly trivial given that many of the Android API methods are actually native methods, or call native methods almost immediately, and they often use Android platform specific features, for example, Skia and Surfaceflinger to name but two. In fact it is quite difficult to see how it can run the majority of Android applications unmodified unless it actually contains what amounts to a largish chunk of, not to put to fine a point on it, Android.

Which leads on to the question of where this chunk might live ? Presumably it is not per downloaded application, so the chunk must (?) be pre-installed on the device, and it is this that the device manufacturer will be licensing (?).

There is also the question of memory footprint. Android relies quite heavily on code sharing via the Zygote mechanism to keep its memory footprint down. It is possible to achieve the same effect using the standard fork()/exec() mechanism if your VM has been written with that in mind, although this is one of the techniques that Oracle argues they have a patent on. This is not necessarily a problem if the underlying VM technology is licensed from Oracle, which it might be in this case.

Then there is the question of native code. Presumably Android applications that use native code need not apply ?

And then there is security. Android applications are sand-boxed on the basis of UIDs and permissions are enforced on the basis of GIDs. If the host OS does not have these or their equivalents then there is a problem. Equally if host OS native applications are not themselves sand-boxed, even if Android applications cannot get out of their sand-boxes, everything else on the platform may be able to get into them

And if there are host OS native applications as well then how do they co-exist without some form of integration at the window manager (or equivalent) level ?

As I say it will be interesting to find out how it actually works

---

Copyright (c) 2011 By Simon Lewis. All Rights Reserved.

A Standalone Android Runtime: Running HelloWorld The Hard Way

Whichever way HelloWorld gets launched there is a point at which the runtime will start to execute the code in the HelloWorld package HelloWorld.apk. Which is a problem. HelloWorld.apk is a standard Android package built using the Android development tools so what is in it, as you might expect, is a classes.dex file, which is nice if you are the Dalvik VM but not so great if you are another kind of JVM that does not talk Dalvik bytecode, and ours does not.

So why not put the class files in the package when its being built and use them ? Where’s the fun in that ? The contents of classes.dex started out as some class files, so lets turn it back into the class files on demand !

To do this we need a specialized ClassLoader which is pretty simple, in this case at least, a Dex loader, likewise, and a DVM to JVM bytecode compiler, which is a bit trickier. Fortunately the HelloWorld application is doing nothing much at all so there are not a large number or variety of instructions to compile.

Loading the Dex file and compiling the code back into JVM bytecode on-the-fly is not necessarily how you would solve this problem for real but it will work in this case.

Compiling is not the most visual of activities so instead here is the trace from the compiler which is invoked by the ClassLoader when the first class in the HelloWorld application is accessed by the runtime. To make life simpler at this point we load the entire Dex file and compile everything in sight, which is not a lot as you can see. The compiler is printing each DVM instruction as it compiles it.

Process[25001]: 
Process[25001]: Class standalone/helloworld/HelloWorldActivity
Process[25001]: 
Process[25001]: compiling <init>
Process[25001]: 
Process[25001]: invoke-direct Landroid/app/Activity; <init> ()V
Process[25001]: return-void
Process[25001]: 
Process[25001]: compiling onCreate
Process[25001]: 
Process[25001]: invoke-super Landroid/app/Activity; onCreate (Landroid/os/Bundle;)V
Process[25001]: const #+2130903040
Process[25001]: invoke-virtual Lstandalone/helloworld/HelloWorldActivity; setContentView (I)V
Process[25001]: return-void
Process[25001]: 
Process[25001]: 
Process[25001]: 
Process[25001]: Class standalone/helloworld/R$attr
Process[25001]: 
Process[25001]: compiling <init>
Process[25001]: 
Process[25001]: invoke-direct Ljava/lang/Object; <init> ()V
Process[25001]: return-void
Process[25001]: 
Process[25001]: 
Process[25001]: 
Process[25001]: Class standalone/helloworld/R$drawable
Process[25001]: 
Process[25001]: compiling <init>
Process[25001]: 
Process[25001]: invoke-direct Ljava/lang/Object; <init> ()V
Process[25001]: return-void
Process[25001]: 
Process[25001]: 
Process[25001]: 
Process[25001]: Class standalone/helloworld/R$layout
Process[25001]: 
Process[25001]: compiling <init>
Process[25001]: 
Process[25001]: invoke-direct Ljava/lang/Object; <init> ()V
Process[25001]: return-void
Process[25001]: 
Process[25001]: 
Process[25001]: 
Process[25001]: Class standalone/helloworld/R$string
Process[25001]: 
Process[25001]: compiling <init>
Process[25001]: 
Process[25001]: invoke-direct Ljava/lang/Object; <init> ()V
Process[25001]: return-void
Process[25001]: 
Process[25001]: 
Process[25001]: 
Process[25001]: Class standalone/helloworld/R
Process[25001]: 
Process[25001]: compiling <init>
Process[25001]: 
Process[25001]: invoke-direct Ljava/lang/Object; <init> ()V
Process[25001]: return-void

---

Copyright (c) 2009 By Simon Lewis. All Rights Reserved.

A Standalone Android Runtime, Or Look Ma No Dalvik !

Having experimented with getting the Dalvik VM to run independently of the Android OS and application runtime, I thought I would try and turn the problem on its head and see whether it was possible to get the Android application runtime to start-up and run a simple HelloWorld app independently of the Android OS and the Dalvik VM, using a standard Java environment, to begin with a desktop JSE, but possibly CDC/whatever later on. To make it more interesting I wanted to do it without running any native (non-Java) code, at least initially. After all the Android runtime is written in Java so hard could it be ?

---

Copyright (c) 2009 By Simon Lewis, All Rights Reserved.

Workaround

It looks as though the problem with mmap() is that the filesystem doesn’t support making mmap()ed files writable which prevents Dalvik as currently implemented from optimizing its Dex file, which prevents it from starting. A workaround for this is to provide Dalvik with an optimized Dex file we prepared earlier. If you do then you get this

Dalvik Running Standalone (but not quite working) on an N800

A screenshot of Dalvik running in an xterm on an N800

The error (which has scrolled off the top) seems to be a failed call to mmap()

Dalvik Running Standalone On MacOSX

When the source for Google’s Dalvik Java VM became available as part of the Android open source release I thought I would see whether it was possible to build and run it standalone, i.e not as part of Android.

The answer is yes, and here’s a shot of it running in the debugger under Xcode on MacOSX to prove it

Unfortunately the canonical HelloWorld application on its own doesn’t make for particularly interesting viewing

With verbose logging on the output is certainly a lot more voluminous.

Here’s the debugger window scrolled to different positions to show all of it