Fingerprinting / Hashing Dalvik Executables

DexFileFingerprinter.java

import gnu.trove.map.TObjectLongMap;
import gnu.trove.map.hash.TObjectLongHashMap;

import org.jf.dexlib2.Opcode;
import org.jf.dexlib2.iface.ClassDef;
import org.jf.dexlib2.iface.DexFile;
import org.jf.dexlib2.iface.Field;
import org.jf.dexlib2.iface.Method;
import org.jf.dexlib2.iface.MethodImplementation;
import org.jf.dexlib2.iface.instruction.Instruction;
import org.jf.dexlib2.iface.instruction.NarrowLiteralInstruction;
import org.jf.dexlib2.iface.instruction.ReferenceInstruction;
import org.jf.dexlib2.iface.instruction.WideLiteralInstruction;
import org.jf.dexlib2.iface.reference.Reference;
import org.jf.dexlib2.util.ReferenceUtil;

import java.nio.charset.Charset;

public class DexFileFingerprinter {

    private final DexFile dexFile;

    private final TObjectLongMap<String> classTypeToHash;
    private final TObjectLongMap<String> methodDescriptorToHash;


    public DexFileFingerprinter(DexFile dexFile) {
        this.dexFile = dexFile;
        classTypeToHash = new TObjectLongHashMap<>();
        methodDescriptorToHash = new TObjectLongHashMap<>();
    }

    public void fingerprint() {
        fingerprint(true);
    }

    public void fingerprint(boolean strict) {
        for (ClassDef classDef : dexFile.getClasses()) {
            StringBuilder fp = new StringBuilder();
            fingerprintClass(classDef, fp, strict);

            long hash = hashString(fp.toString());
            String classType = classDef.getType();
            classTypeToHash.put(classType, hash);
        }
    }

    private void fingerprintClass(ClassDef classDef, StringBuilder fp, boolean strict) {
        fp.append("CLASS\n");

        if (strict) {
            fp.append("annotation size=").append(classDef.getAnnotations().size()).append('\n');
            fp.append("interface count=").append(classDef.getInterfaces().size()).append('\n');
            fp.append("access flags=").append(classDef.getAccessFlags()).append('\n');
        }

        for (Field field : classDef.getFields()) {
            fingerprintField(field, fp, strict);
        }

        for (Method method : classDef.getMethods()) {
            fingerprintMethod(method, fp, strict);
        }
    }

    private void fingerprintField(Field field, StringBuilder fp, boolean strict) {
        fp.append("FIELD\n");

        if (strict) {
            fp.append("access flags=").append(field.getAccessFlags()).append('\n');
            fp.append("annotation count=").append(field.getAnnotations().size()).append('\n');
        }

        String typeFingerprint = buildTypeFingerprint(field.getType());
        fp.append("type=").append(typeFingerprint).append('\n');
    }

    private static String buildTypeFingerprint(String type) {
        if (type.length() == 1) {
            // It's a primitive, return that type
            return type;
        } else {
            if (type.charAt(0) == 'L') {
                // Plain object, just fingerprint that it's an object
                // Would be too fragile to fingerprint class names which frequently change
                // Could possibly use full names for protected class paths like "java.lang", but seems a little strict
                return "L";
            }

            // Must be an array, fingerprint array rank and type
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < type.length(); i++) {
                char c = type.charAt(i);
                if (c == '[') {
                    // Add another rank
                    sb.append(c);
                } else {
                    // End of array
                    if (c == 'L') {
                        // Object array
                        sb.append('L');
                    } else {
                        // Primitive array
                        sb.append(c);
                    }
                }
            }

            return sb.toString();
        }
    }

    private void fingerprintMethod(Method method, StringBuilder fp, boolean strict) {
        fp.append("METHOD\n");

        if (strict) {
            fp.append("annotation count=").append(method.getAnnotations().size()).append('\n');
            fp.append("access flags=").append(method.getAccessFlags()).append('\n');
            fp.append("parameter count=").append(method.getParameterTypes().size()).append('\n');
        }

        String returnTypeFingerprint = buildTypeFingerprint(method.getReturnType());
        fp.append("return type=").append(returnTypeFingerprint).append('\n');

        MethodImplementation implementation = method.getImplementation();
        String methodDescriptor = ReferenceUtil.getMethodDescriptor(method);
        if (implementation == null) {
            fp.append("no implementation");
            if (strict) {
                // If strict, avoid combining counts of empty methods
                fp.append(": ").append(methodDescriptor);
            }
            fp.append('\n');
        } else {
            fingerprintImplementation(method.getImplementation(), fp, strict);
        }

        long hash = hashString(fp.toString());
        methodDescriptorToHash.put(methodDescriptor, hash);
    }

    private void fingerprintImplementation(MethodImplementation implementation, StringBuilder fp, boolean strict) {
        if (strict) {
            fp.append("register count=").append(implementation.getRegisterCount()).append('\n');
            fp.append("try blocks=").append(implementation.getTryBlocks().size()).append('\n');
        }
        for (Instruction instruction : implementation.getInstructions()) {
            Opcode op = instruction.getOpcode();
            fp.append(op.toString()).append('\n');

            if (strict) {
                Object val = null;
                if (instruction instanceof NarrowLiteralInstruction) {
                    val = ((NarrowLiteralInstruction) instruction).getNarrowLiteral();
                } else if (instruction instanceof WideLiteralInstruction) {
                    val = ((WideLiteralInstruction) instruction).getWideLiteral();
                } else if (instruction instanceof ReferenceInstruction) {
                    if (op == Opcode.CONST_STRING) {
                        Reference ref = ((ReferenceInstruction) instruction).getReference();
                        val = ReferenceUtil.getReferenceString(ref);
                    }
                }
                if (val != null) {
                    fp.append(val).append('\n');
                }
            }
        }
    }

    private static long hashString(String string) {
        byte[] key = string.getBytes(Charset.forName("UTF-8"));
        int offset = 0;
        int len = string.length();
        int seed = 0x1337;
        MurmurHash3.LongPair longPair = new MurmurHash3.LongPair();
        MurmurHash3.murmurhash3_x64_128(key, offset, len, seed, longPair);

        return longPair.val1;
    }

    public TObjectLongMap<String> getClassTypeToHash() {
        return classTypeToHash;
    }

    public TObjectLongMap<String> getMethodDescriptorToHash() {
        return methodDescriptorToHash;
    }

    public long getClassHash(String classType) {
        return classTypeToHash.get(classType);
    }

    public long getClassHash(ClassDef classDef) {
        return getClassHash(classDef.getType());
    }

    public long getMethodHash(String methodDescriptor) {
        return methodDescriptorToHash.get(methodDescriptor);
    }

    public long getMethodHash(Method method) {
        String methodDescriptor = ReferenceUtil.getMethodDescriptor(method);
        return getMethodHash(methodDescriptor);
    }
}