android 反编译的一点思路

请大家先不否定我，不要先把事情打上不可能的标签. 只是一点思路和探索，就当是活跃思维了。

欢迎留言,不吝赐教.

android 反编译的教程帖子还是很多的，具体流程一般是 android->dex->dex.jar->java source，简单
点的 class 反编译效果还是不错的。一旦 sourcecode 太复杂，反编译效果就强差人意了。所以让我有了写自己反编译器的冲动.
这里, 反编译目标对象是运行在 dalvik 虚拟机的 class 文件. 它运行在 jvm 上的 class 文件基本结构是一样的, 但操作符的数目更少, 操作也更简单, 很多对寄存器的操作都简化了.
我使用 dex 解压 apk 文件 获得 class.dex 然后再转码为 .smali 文件, 这文件其实就是 dalvik bytecode 的文字表达方式, 相对于直接读写 byte位, 基于文字的文件更易读一些.

在我的设想里，反编译的结果应该是:
1 没有语法错误.
2 和 sourcecode 文件等效的代码。力争反编译得到的 sourcecode 再次编译后得到的 class 文件同 sourcecode 得到的 class 文件是一致的.
以下不在设计范围之内:
对于混淆代码, 反编译过程自身不负责替换被混淆的包名和变量名. 替换工作应该在完成反编译之后通过其他工具完成. 例如你如果获得了等效的源代码, 那么只要你使用市面上流行的混淆工具再次混淆源代码即可转码成一个更易读的源码版本.

具体实现上:
我认为反编译的重心是 method 的反编译. java 的基本组成部分是 class, 内部类, 接口, 匿名内部类, 方法, 静态初始化段落. 在编译时所有的类类型都会被处理成一个独立存在的 class 文件, 例如内部类就是 parentclass@innerclass 匿名内部类就是 parentclass@number. 不同的是内部类会含有一个 parent.this. 先完成 method 的反编译, 再考虑内部类的问题.

我用了一个月的时间来分析 android 编译得到的 dalvik bytecode 文件. 可供参考的资料实在不多，于是我就自己动手按照自己的思路写了一些基础的反编译代码。思路分两个部分：
1 理清程序的执行流程，识别出 while，嵌套while、if、else、dowhile等程序结构。
2 在执行结构的基础上反编译出 java code。

对于阶段 (1) 在每个while或者是goto的部分切分 bytecode 成更小的片段, 然后，把 bytecode 转化为执行流程“图”，然后通过分析节点的连通性来分析出各种语句结构(for,while,dowhile,if...)

如果源码结构不太复杂，第一阶段是可以顺利完成的，例如

    public void testContinue6() {
        int a = 0;
        int b = 0;
        int c = 0;

        out1: while (a < 100 && b < 100) {
            for (int i = 0; i < c; i += 2) {
                if (i / 5 == 2) {
                    System.out.println("innter0");
                    break out1;
                }
                if (i % 18 == 3) {
                    System.out.println("innter2");
                    continue out1;
                }
            }
        }
    }

我目前的代码已经能完整的识别出其中的 while、嵌套循环等结构。

如果执行顺序可以确定，那么阶段(2)翻译出 sourcecode 就十分简单。这基于下面的几个假设：
1 java bytecode 是基于寄存器的，bytecode中所可能使用到的寄存器的数目和参数都是可以确定的。
2 程序执行总是顺序的，即便是 while 循环也可以理解成先执行条件判断部分，然后执行while的代码部分。
3 在顺序执行的代码段中，执行过程中会根据程序结构而划分出更多变量的子作用域。
4 子作用域可以使用的变量数目>=父作用域的变量数目，在作用域结束时只有当前作用域中使用的变量结束作用(寄存器被释放). 也就是说如果 current.scope register count > parent.scope register count, 那么就能确定这个变量一定是定义在当前上下文的.

我还发现了一些解释的小技巧：
每个 bytecode 操作符其实都可以看做一个输入输出控制器，永远都是一个或者是多个输入，0 或 1 个输出。
那么语句的执行可以转化为一个"倒置的树结构"的寄存器依赖"图", 所有语句最后都会合并到一点,例如 return, 或者method invoke. 在子作用域中, 按照倒置树的起止范围可以细分更多子结构, 每个子结构都合并到一点. 追查寄存器的依赖关系就可以获得变量的依赖关系, 进而推断出变量的定义位置和作用域.
那倒置树的叶子节点是 "常量" 或者 来自 parent scope 或者可以推断他是一个当前作用域的变量, 那么可以停止树结构的建立了. 如果两个树结构有重叠的节点, 那么这个节点就应该被当作当前上下文的一个变量对象.

这里只是泛泛的说，但我相信通过上面的分析方法是可以确定各个变量的定义位置和作用域的。有了这些信息，只要把所有的 byte code 翻译成 java statement 即可获得可读的代码。再做一次代码语义的优化就可以获得获得可读性更强的代码了。

凡事总有例外，如果源码结构写的太复杂，就很难分析出来了，例如

    public void testContinue18() {
        int a = 0;
        int b = 90;
        int c = 0;

        do {
            System.out.println(a);
            if (test1()) {
                continue;
            }
            System.out.println("bb");
            if (test2()) {
                break;
            }
            System.out.println("cc");
        } while (test7() || test3() || test4());
    }

    public void testContinue20() {
        int count = 0;
        while (true) {
            System.out.println("00");
            count++;
            if (count / 32 + 5 == 113) {
                break;
            }
            System.out.println("aa");
        }
        System.out.println("bb");

        do {
            System.out.println("00");
            count++;
            if (count / 32 + 5 == 113) {
                break;
            }
            System.out.println("aa");
        } while (test2());
        System.out.println("bb");
    }

结构分析的时候就有很多等价的结构，不能确定使用哪种。并且之前在 if else 处断开 bytecode 的划分本身都太粗糙了。这里还没思路.

引用:
dalvik bytecode
http://www.netmite.com/android/mydroid/dalvik/docs/dalvik-bytecode.html