文章来源：看雪学院
起源
以前做过PC端逆向，一直没有学过Android，4月的时候，读了一下 my1988 对混淆壳的分析，很感兴趣，决定深入研究。 花了大约3个月的时间基本理清了混淆壳的原理，简单写了一个App，fastvm， 针对libmakeurl2.4.9.so 可以生成原始的cfg流图，和优化过的cfg流图， 以下是函数sub_342d的 ：
优化过的如下： 
预备知识：
写这个App的时候主要参考了3本书
1. arm_arch_ref
2. Thumb-2SupplementReferenceManual
3. Modern Compiler implementation in c
代码里很多注释会有 P245，这样的写法，一般是代表1， 2中的某一本的第245页，@aar 指的1，@MCIC 指的3。
elf文件格式分析
这个分析的很多了，我就不赘述了。
词法分析
因为我们要通过编译后端优化彻底干掉混淆，必须得自己实现数据流，所以无法使用别人的反汇编引擎，我们通过实现一个简单的正则表达式引擎来对elf的代码进行反汇编 我们重新实现一个正则表达式引擎，并增加自己的命名变量，举例： 
我们定义一个正则表达式如下：
1. 字符集 只有 0， 1， *
2. 支持重复
先不管o的定义，我们看thumb_inst_cmp里面支持了 lm3和ln3，这句表达式的意义是： 我们在读取一个二进制串时，他以 0100 0010 0开始，接下去的三位提取到lm变量中，后面的3位提取到 ln变量中，这条指令用thumb_inst_cmp进行深度解析。这些变量都存放在一个arm_inst_ctx的结构中。
struct arm_inst_ctx {
reg_t ld; // 目的寄存器
reg_t ld2; // 目的寄存器2
reg_t lm; // 参数寄存器1
reg_t ln; // 参数寄存器2
reg_t lp; // 参数寄存器3
int register_list; // 寄存器列表，一般给push和pop用
int imm; // 立即数
int m;
int setflags; // 是否需要跟新flag
int cond; // 条件
int vd; // simd中需要
struct {
unsigned p : 1;
unsigned u : 1; // 在一些立即数中，指出是加还是减
unsigned w : 1;
unsigned t : 2;
};
};
我们基于这个规则，完整的定义出整个arm thumb的指令集（暂时只定义了需要的部分）：
struct arm_inst_desc desclist[] = {
{"0000 o1 i5 lm3 ld3", {t1_inst_lsl, t1_inst_lsr}, {"lsl", "lsr"}},
{"0001 0 i5 lm3 ld3", {t1_inst_asr}, {"asr"}},
{"0001 10 o1 lm3 ln3 ld3", {t1_inst_add, thumb_inst_sub_reg}, {"add", "sub"}},
{"0001 11 o1 i3 ln3 ld3", {t1_inst_add, thumb_inst_sub}, {"add", "sub"}},
{"0010 0 ld3 i8", {thumb_inst_mov}, {"mov"}},
{"0010 1 lm3 i8", {t1_inst_cmp_imm}, {"cmp"}},
{"0011 0 ld3 i8", {t1_inst_add}, {"add"}},
{"0011 1 ld3 i8", {thumb_inst_sub}, {"sub"}},
{"0100 0000 o2 lm3 ld3", {t1_inst_and, thumb_inst_eor, t1_inst_lsl, t1_inst_lsr}, {"and", "eor", "lsl2", "lsr2"}},
{"0100 0001 o2 lm3 ld3", {t1_inst_asr, t1_inst_adc, t1_inst_sbc, t1_inst_ror}, {"asr", "adc", "sbc", "ror"}},
{"0100 0010 0o1 lm3 ld3", {t1_inst_tst, t1_inst_neg}, {"tst", "neg"}},
{"0100 0010 1o1 lm3 ln3", {thumb_inst_cmp, t1_inst_cmn}, {"cmp", "cmn"}},
{"0100 0011 o2 lm3 ld3", {thumb_inst_orr, t1_inst_mul, t1_inst_bic, t1_inst_mvn}, {"orr", "mul", "bic", "mvn"}},
{"0100 0110 d1 lm4 ld3", {t1_inst_mov_0100}, {"mov"}},
{"0100 0100 d1 lm4 ld3", {t1_inst_add}, {"add"}},
{"0100 0101 01 hm3 ln3 ", {thumb_inst_cmp}, {"cmp"}},
{"0100 0101 10 lm3 hn3 ", {thumb_inst_cmp}, {"cmp"}},
{"0100 0101 11 hm3 hn3 ", {thumb_inst_cmp}, {"cmp"}},
{"0100 1 ld3 i8", {thumb_inst_ldr}, {"ldr"}},
{"0100 0111 o1 lm4 000", {t1_inst_bx_0100, thumb_inst_b}, {"bx", "blx"}},
{"0110 0i5 ln3 lm3", {thumb_inst_str}, {"str"}},
{"0110 1i5 lm3 ld3", {thumb_inst_ldr}, {"ldr"}},
{"0111 0 i5 ln3 lm3", {thumb_inst_strb}, {"strb<c> <lp>,[<ln>,#<imm>]"}},
{"0111 1 i5 ln3 ld3", {thumb_inst_ldrb}, {"ldrb<c> <ld>,[<ln>,#<imm5>]"}},
{"1001 0 lm3 i8", {thumb_inst_str}, {"str"}},
{"1001 1 ld3 i8", {thumb_inst_ldr}, {"ldr"}},
{"1010 o1 ld3 i8", {t1_inst_add1, t1_inst_add}, {"add", "add"}},
{"1011 o1 10 m1 rl8", {thumb_inst_push, thumb_inst_pop}, {"push", "pop"}},
{"1011 0000 0 i7", {thumb_inst_add}, {"add"}},
{"1011 0000 1 i7", {thumb_inst_sub}, {"sub"}},
{"1011 1111 c4 i4", {thumb_inst_it}, {"it"}},
{"1100 1 ln3 rl8", {thumb_inst_ldmia}, {"ldmia<c> <Rn>!?, <registers>"}},
{"1101 c4 i8", {thumb_inst_b}, {"b<cond>"}},
{"1110 0 i11", {t1_inst_b}, {"b"}},
{"1110 100p1 u1 1 w1 0 lm4 ln4 lp4 i8", {thumb_inst_strd}, "strd<c>.w"},
{"1110 100p1 u1 1 w1 1 ln4 ld4 le4 i8", {thumb_inst_ldr}, "ldrd<c>.w"},
{"1110 1001 0010 1101 0 m1 0 rl13", {thumb_inst_push}, "push.w"},
{"1110 1000 1011 1101 i1 m1 0 rl13", {thumb_inst_pop}, "pop.w"},
{"1110 1010 010s1 ln4 0 i3 ld4 i2 t2 lm4", {thumb_inst_orr}, "orr{s}<c>.W <ld>,<lm>{, <shift>}"},
{"1110 1101 0d1 10 1101 vd4 1011 i8", {thumb_inst_vpush}, "vpush<c> <list>"},
{"1110 1100 1d1 11 1101 vd4 1011 i8", {thumb_inst_vpop}, "vpop <list>"},
{"1110 1010 1001 ln4 0i3 1111 i2 t2 lm4", {thumb_inst_teq}, "teq<c> <ln>, <lm>{, <shift>}"},
{"111i1 1111 1d1 00 0i3 vd4 i4 0i2 1 i4", {thumb_inst_vmov}, "vmov"},
{"1110 1011 000s1 ln4 0i3 ld4 i2 t2 lm4 ", {thumb_inst_add}, "add{s}<c>.W <ld>,<ln>,<lm>{, <shift>}"},
//{"1111 0i1 01 000s1 1101 0i3 ld4 i8", {thumb_inst_add}, "add{S}<c>.W <Rd>,SP#<const>"},
{"1111 0i1 01 000s1 ln4 0i3 ld4 i8", {thumb_inst_add}, "add{S}<c>.W <Rd>,<Rn>,#<const>"},
{"1111 0s1 c4 i6 10 u1 0 w1 i11", {thumb_inst_b}, "b<c>.w <label>"},
{"1111 0s1 c4 i6 10 u1 1 w1 i11", {thumb_inst_b}, "b<c>.w <label>"},
{"1111 0s1 i10 11 u1 1 w1 i11", {thumb_inst_b}, "bl<c> <label>"},
{"1111 0s1 i10 11 u1 0 w1 i10 0", {thumb_inst_b}, "blx<c> <label>"},
{"1111 0i1 01 101s1 ln4 0i3 ld4 i8", {thumb_inst_sub}, "sub{s}<c>.w <ld>,<ln>,#<const>"},
{"1111 0i1 00010 s1 11110 i3 ld4 i8", {t1_inst_mov_w}, "mov.w"},
{"1111 0i1 101100 i4 0 i3 ld4 i8", {thumb_inst_mov}, "movt"},
{"1111 0i1 100100 i4 0 i3 ld4 i8", {thumb_inst_mov}, "movw"},
{"1111 1000 0001 ln4 ld4 1 p1 u1 w1 i8", {thumb_inst_ldrb}, {"ldrb<c>.w <ld>, [<ln>,#<imm8>]"}},
{"1111 1000 1001 ln4 ld4 i12", {thumb_inst_ldrb}, {"ldrb<c>.w <ld>, [<ln>,#<imm12>]"}},
{"1111 1000 0101 ln4 ld4 0000 00 i2 lm4", {thumb_inst_ldr}, {"ldr<c>.w <ld>, [<ln>,<lm>{,LSL #<shift>}]"}},
{"1111 1000 1101 ln4 ld4 i12", {thumb_inst_ldr}, {"ldr.w"}},
//{"1111 1000 u1 101 1111 ld4 i12", {thumb_inst_ldr}, {"ldr.w"}},
{"1111 1000 1000 ln4 lm4 i12", {thumb_inst_strb}, {"strb<c>.w <Rt>,[<Rn>,#<imm12>]"}},
{"1111 1000 0000 ln4 lm4 1p1 u1 w1 i8", {thumb_inst_strb}, {"strb<c> <Rt>,[<Rn>,#+/-<imm8>]"}},
{"1111 1000 1100 ln4 lm4 i12", {thumb_inst_str}, {"str<c>.w <Rt>,[<Rn>,#<imm12>]"}},
{"1111 1000 0100 ln4 lp4 000000 i2 lm4", {thumb_inst_str}, {"str<c>.w <lo>,[<ln>,<lm>{, LSL #<shift>}]"}},
{"1111 1001 0d1 00 ln4 vd4 i8 lm4", {thumb_inst_vst1}, {"str<c>.w <lo>,[<ln>,<lm>{, LSL #<shift>}]"}},
};
然后基于此，按 nfs -> dfs -> 2d-trans的方式来生成整个状态机图。
nfa的如下：
nfa在归纳同字符集可到达的边，生成dfa：
详细分析可以参考任意一本形式语言与自动机理论，或者 龙书， 《parsing techniques》都可。
语法分析
IT指令处理
语法分析反而比较简单，因为汇编语言不存在特殊的语法，唯一特殊的指令是IT指令，在IDA中arm的IT指令是不会做切分，和上下的代码完整的放到一个block中，比如：
但是假如我们需要用编译优化去掉混淆，必须得把IT指令做为一个单独的bcond指令来处理，比如上图中的代码，转换成c语言后如下：
if (!r0) {
rt = 0x58586a70;
}
基于此，上图中的指令，被我们转换成如下格式：
bcond指令处理
b<cond>指令没啥太多需要注意的，他末尾跟着的指令指向他的false_label分支，它的跳转指向它的true_label分支，这一点上和IT是相反的。
编译优化
生成def和use关系
因为要做后端的数据流分析，必须给出所有指令的def和use关系， 举几个例子说明需要注意的地方，因为是直接在arm的汇编上做的def和use，所以实际的代码写起来很多的corner case非常难处理，举一些典型的例子说明下：
cmp
cmp r0, r1 // def = APSR // use = ln, lm
movw
MOVW R1, #0X7571 // def = r1 // use = empty
movt
MOVT R1, #0X791
// def = r1
// use = r1, 这个地方是把0x791移到r1的高位，所以它的use也包含r1
ADD
adds r0, 1 // def = apsr, r0; add的某些指令会设置apsr寄存器，所以它的def会有多个，这也导致了普通的活跃性分析的代码，要做修改才能适应反混淆 // use = empty,
adds r0, 1 // def = apsr, r0; add的某些指令会设置apsr寄存器，所以它的def会有多个，这也导致了普通的活跃性分析的代码，要做修改才能适应反混淆// use = empty,
blx addr // def = r0, r1 // use = r0, r1, r2, r3 // 我在早期设计中使用了别名分析，因为无法准确的判断函数的传入参数，出席那了大量的错误，不得已每次进入函数都要def一遍所有的内存变量，生成了大量的垃圾指令，后来被我全部关闭了
prologue
进入函数前，需要定义r0-r3, sp, pc寄存器。
epilogue
出函数前，需要使用r0-r1, sp, pc寄存器。
活跃性分析
生成了def和use数据以后，就可以方便的做活跃性分析了，活跃性分析本身的算法很简单，伪代码如下，@MCIC.P232：
对照代码，参考fastvm中的minst.c:minst_blk_liveness_calc：
int minst_blk_liveness_calc(struct minst_blk *blk)
{
struct minst_node *succ;
struct minst *minst;
struct bitset in = { 0 }, out = { 0 }, use = {0};
int i, changed = 1;
for (i = blk->allinst.len - 1; i >= 0; i--) {
minst = blk->allinst.ptab[i];
bitset_clear(&minst->in);
bitset_clear(&minst->out);
}
while (changed) {
changed = 0;
for (i = blk->allinst.len - 1; i >= 0; i--) {
minst = blk->allinst.ptab[i];
if (minst->flag.dead_code || (minst->cfg && minst->cfg->flag.dead_code)) continue;
bitset_clone(&in, &minst->in);
bitset_clone(&out, &minst->out);
bitset_clone(&use, &minst->use);
bitset_clone(&minst->in, bitset_or(&use, bitset_sub(&minst->out, &minst->def)));
for (succ = &minst->succs; succ; succ = succ->next) {
if (succ->minst)
bitset_or(&minst->out, &succ->minst->in);
}
if (!changed && (!bitset_is_equal(&in, &minst->in) || !bitset_is_equal(&out, &minst->out)))
changed = 1;
}
}
bitset_uninit(&in);
bitset_uninit(&out);
bitset_uninit(&use);
return 0;
}
和上面的代码差不多是一一对应的。
死代码删除
在进行了活跃性分析以后，死代码删除就非常简单了，对应的c代码在minst.c:minst_blk_dead_code_elim中，原理就是： 某条指令被def，但是不在它的出口活跃列表中，则可以删除，举例：
1. mov r0, 0 2. mov r0, 1
因为r0被定义了二次，导致了指令1中的r0，在到达2的时候已经死了。也就是不在它的出口活跃列表中了。
到达定值分析
到达主要是研究，某条指令最远到达过什么地方，它在常量传播的分析中非常有用。
假如你也打算深入分析混淆壳，建议认真读下 @MCIC的17章，Dataflow Analysis。
常量传播
1: c <- 1
2: b <- c + 13: cmp c, b
在上图中b就可以被优化为2，同时cmp的结果也是为1，按算法上的描述就是：
假如某条指令被常量定值以后，后续所有使用过此条指令的代码都要根据自己的语义进行更新。
核心反混淆
1. 判断是否有混淆
判断是否有混淆，我们需要遍历所有cfg节点，然后判断其cmp指令的左右2个参数，是否大部分都是常数，假如是的话，则认为其处在混淆cfg的某一个节点中，那么直接找到其支配节点即可。 ps. 这里为了方便，我直接偷懒把一个函数中前缀最多而且大于7的节点，当作了混淆状态机的支配节点了。 这里有个简单的办法，就是先过滤所有前缀节点小于7的可以直接抛弃，因为混淆函数的支配节点前驱节点都特别多，比如：
1.1 找到其支配节点(Dominators)
支配节点的算法，我没实现，但是原理上比较简单，可以参考@MCIC.C18(Loop Optimization)。 这里简单介绍下什么是支配节点：
while (1) { <-- 这个就是支配节点 if (a) .... if (b) .... }
有些书籍上可能也翻译为必经节点，也就是从外部节点进入到内层循环时必须经历的节点，这个节点非常有用。
2. 混淆的原理
简单的例子
先看如下代码：
- printf(“hello world!”);
这个代码，我们手工尝试对他做混淆：
int a = 0;
while (1) {
if (a > -1) {
a = 1;
}
else if (a > 0) {
a = 2;
}
else if (a > 1) {
a = 3;
}
...
else if (a > 99) {
a = 101;
}
else if (a == 101) {
printf("hello world\n");
break;
}
}
我们简单审读下这个代码，把a定义为状态寄存器，只要你跟着状态寄存器走，整个循环自然会被全部展开。
复杂的例子
上面的例子只是演示了简单的statment该如何混淆，那么如何实现循环，判断呢？ 判断和循环从原理上来说都是一样的，只是判断以后，跳转点，跳到前面的某点上。从头开始，再来个例子，我们对上面的例子进行拓展：
num = 17;
ret = isprime(num);
if (ret) {
printf("%d is prime", num);
}
else {
printf("%d not is prime", num);
}
混淆过后：
num = 17;
ret = isprime(num);
a = 100;
while (1) {
if (a > 99) {
a = 101;
}
else if (a > 100) {
a = 102;
}
...
else if (a > 199) {
a = 201;
if (ret) {
a = 301;
}
}
else if (a == 201) {
a = 202;
}
else if (a == 203) {
printf("%d not is prime", num);
break;
}
else if (a > 300) {
a = 302;
}
else if (a > 301) {
printf("%d is prime", num);
break;
}
}
大家简单肉眼跟读下这个代码，发现整个混淆壳其实就是一个稍微复杂的常量状态机。只要你顺着状态寄存器走，很容易就能跟踪出整个脉络。
算法实现
my1988在他的帖子my1988算法里面提到过一个简单的算法，把混淆过的代码的cfg分为2部分，一部分为 控制节点 一部分为 状态节点，然后连接 状态节点，删除 控制节点，这个算法是有问题的，因为假如原代码里面，散落了一，二条代码在 控制节点内，就会丢代码了。 不过我们只需要简单改造即可。
步骤1 基本参数分析
代码：minst_dob_analyze
1. 判断是否有混淆2. 确认混淆逻辑的支配节点3. 确认混淆的状态寄存器是哪个
步骤2 混淆拓展
参考代码 minst_csm_expand 为什么要拓展说一下，参考以下的代码：
num = 17;
ret = isprime(num);
if (ret) {
printf("%s is prime\n", ret);
}
混淆过后：
a = 100;
ret = isprime(num);
b = 200;
if (ret) b = 300;
while (1) {
if (a == 100) {
a = 101; // cfg1
}
else if (a == 101) {
a = b; // cfg2, 注意这里
}
else if (a == 200) {
// cfg3
}
else if (a == 300) {
// cfg4
}
}
我们看一下，到了cfg2的时候，a被b定值了，但是b实际上有2个值的，假如你要进行反混淆，必须得跟踪出唯一的定值路径才行，但是从cfg2开始已经不可分析了，那如何处理呢？ 把cfg2改为如何形式：
else if (a == 101) {
a = b;
c = a;
a = 200;
if (a == c) {
continue;
}
else {
a = 300;
}
有人看到这里，可能感觉很奇怪，为什么不直接改成如下形式呢？
a == b; if (a == 200) { } else if (a == 300) { }
这是和编译优化的到达定值的生成有关，到达定值分析很蠢的，他只有对明确的定值语句，才能给出数据流分析。他无法识别
if (a == 100) {}和a = 100;
在某种程度上是等价的。
步骤3 cfg节点分类
参考: minst_blk_classify 我们把cfg节点分为3类：1. 进入混淆(csm)cfg前的cfg称为 csm_in2. 核心的混淆cfg，称为csm3. 从混淆cfg出去的节点为 csm_out
分类算法非常简单，用dfs即可：
1. 从头节点开始遍历，可达的所有节点都标注为 csm_in
2. 从混淆的支配节点开始遍历，可达的所有节点为csm
3. 出口节点标注为csm_out
4. 遍历csm_out节点的前驱节点，假如前驱节点的所有后继节点都为csm_out，则它也为csm_out
5. 重复4，一直到其不动点为止
步骤4 遍历常量定值点
循环遍历所有不为csm_out的bcond节点，也就是有条件跳转的节点。 然后分析其跳转指令参考的cmp指令的，2个寄存器的值，分析其是否为常数，是的话，进入步骤5，定值点跟踪。
步骤5 定值点跟踪
在进入定值点跟踪时，我们先简单说一下一些术语：
以下的示例代码来自于 libmakeurl2.4.9.so的jni_OnLoad，IDA F5以后，代码如下：
v2是混淆的状态寄存器：1. v2被定值为 0xb4b8ce82. v2和0x38176e52比较，比他小，所以不用break3. v2 > -526232813，所以进入if身体内4. v2 等于 0xb4b8ce8，在进去5. v8的值来自于函数的某个返回值，此时条件跳转不可计算停止
这个是IDA F5后的分析结果，我们在做实际的编译优化时，是在cfg流图上做的，我们用上面语法分析优化后得到的cfg流图操作一遍：
1. 我们从v2(也就是r6寄存器开始)找到第一个前驱不为0，也就是cfg_4的节点。
2. 从前往后复制，一直到最后一个 undefined bcond 的cfg节点的前一个节点为止，也就是cfg_14。
3. 生成一个新的cfg节点。
4. 删除cfg3和cfg4之间的边。
5. 连接新的cfg和cfg15，最后得到的图如下：
cfg51就是新生成的节点，里面有大量的指令是死的，比如 216, 219, 222都是重复定义的，后面的编译优化分析都可以彻底干掉，上图中的cfg51被编译优化后变成了，如下形式：
然后我们在找v2的另外的定值点，重复这个过程。
步骤6 编译优化
步骤7 到最小不动点结束
遍历所有的cfg，一直到找不到找不到可以跟踪的定值点结束，也就是最开始的那副优化过的图像。 一般优化到最后以后，大量的节点都找不到前驱节点都可以删除，后面优化的就是最终的图像了。 这里是一个更复杂的例子，因为图像太大了，我直接放在github上。
https://github.com/baikaishiuc/fastvm/wiki/sub_367c
遗留的问题
为什么不用ssa
我对ssa不怎么熟悉，感觉表达能力和普通的数据流分析差不多，所以没上。
为什么没生成新的so
我对Android下调试还不熟悉，小米的手机root需要申请权限。
能否使用别名分析
很困难，一开始用了别名分析，结果错误的优化了某些变量，想用别名分析，可能需要深入的分析每个函数之间的调用关系才行。
暂无评论内容