《基于二进制代码的代码混淆研究》
0 摘要
本文首先介绍了Collberg对代码混淆的分类方式以及定义，而后介绍了一些常见的混淆策略，最后讨论了如何构建一个二进制混淆引擎。
1代码混淆研究综述
1.1 混淆的分类
早在1997年，学术界就开始了代码混淆的研究。目前使用最广泛的混淆分类方式是Collberg[1]于1997年针对JAVA程序的安全问题提出的。根据Collbreg的定义，混淆可以分为以下四种类型：布局混淆、预防性混淆、数据混淆、控制混淆。布局混淆指删除或修改源代码中的对攻击者由于的信息，如变量名、调试信息等。显然，布局混淆在二进制代码混淆中可以忽略不计。预防性混淆指预先针对特定的反编译工具，解混淆方法进行防备。
控制混淆是目前研究的重点。Collbreg将控制混淆分为以下三类：聚合、排序、计算。聚合指将逻辑上相关的计算分割，或者将逻辑上不相干的计算聚合在一起。排序指将计算在程序中的分布随机化处理。计算指插入混淆计算代码来隐藏真实的控制流，包括扩展循环条件，引入不透明谓词等。值得一提的是，Collberg提出的排序混淆在二进制代码中实现难度较大。
数据混淆被分为以下三种：聚合、重组、编码。
当然，还有许多学者对此做了有关研究，如Chenxi Wang[10]，Wroblewsk[9]等。前者是基于C语言程序的，后者是基于二进制代码的。值得一提的是，目前使用非常广泛的控制流平坦化算法正是Wang提出的。
1.2 混淆的定义
Collberg将混淆描述为一个从源程序P到混淆后的程序P’的等价转换。更精确地说，合法的转换必须要满足以下两个条件：如果P终止失败或者异常终止，那么P’可以选择终止或不终止；在其它情况下，P’必须要正常终止，并且产生与P’相同的输出。这里的输出指的是用户可观测到的P的行为，对于那些不可观测到的行为，如创建文件与访问网络等，都是可以在合法转换中出现的。贾福春在[6]对该定义进行了修正，提出了弱语义等价。
2 常见混淆策略
2.1 基于数据流
2.1.1 指令移动
在二十年前，甚至更早，就出现了使用JMP IMM32指令连接乱序后的代码的混淆技术，以此来打乱代码顺序局部性。指令移动与此不同，指令移动是将基本块内的语句进行顺序重排。z0mbie[12]首次引入x86指令对象集的概念，解决了相邻指令的交换。潘雁[7]基于Wroblewski提出的x86系统指令形式化定义，论证了指令交换的充分条件，并提出了针对数学与逻辑运算指令进行交换时，还需要考虑交换律等问题。文献[7]同时提出了一种模拟退火算法的指令随机交换混淆算法。
本文提出使用定值分析，构建指令移动混淆，非相邻指令交换。以一段代码为例：
0 Mov var1.500
1 Mov eax,var1
2 Sub var1,20
3 Add eax,2018
4 Push eax
5 Call func
为了方便描述，以{变量1 : 定值来源行号1,...,变量i: 定值来源行号i}来描述指令的上下文。
1行指令可以进行移动，但不能移动到3行指令之后，因为3行指令的上下文是{eax:1,var1:2}，如果强行移动到3行指令以后，那么3行指令也要跟随移动，这个过程十分复杂，可谓牵一发而动全身。1行指令可以移动到2行与3行指令之间，1行指令的上下文是{var1:0}，而移动之后则其上下文变为{var1:2}，为了解决这个问题，移动时需要引入一个变量保存var1:0的值。引入的变量可以储存于活跃分析以后确定的可以使用的死寄存器，或者申请的一块内存。前者是不影响上下文的指令移动，后者则是影响上下文的指令移动。
当实现不影响上下文的指令移动时，我们要确保两个条件：1.指令移动的目标处的上下文来源必须与原位置处相同；2.指令移动的目标位置必须在第一次引用了移动指令的定值变量的指令前。
实现影响上下文的指令移动则比较自由，本文便不再赘述。
请允许我在此处出戏三秒钟，z0mbie是一位在代码变形方面造诣非常深的大牛，他的个人技术站点上的资料非常值得研究。顺便在此膜一下某零前辈。画外音：一位自称是一位十二岁花季美少年的铁杆粉丝的蒙面黑衣男子路过，并膜了一下十二岁的蒙面花季美少年。
2.1.2 插入死代码
死代码分为两种，一种是永远不会被执行的代码，常与永真（假）不透明谓词结合使用，另一种是只影响死变量（死变量是在对代码进行混淆时由混淆器分析出的）的语句。以几段代码为例，简单介绍一下后者：
Mov eax,2010
Mov eax,var1
Mov eax,2018
Call stdcall_func
Mov eax,2018
Push eax
Push var1
Call Obfscall
Obfscall:
Push var1
Call stdcall_func
这是三个死代码插入的例子。毫无疑问，例1的解混淆是最为简单的，例2使用了函数返回值使用eax传递的技巧，例3的复杂度是较高的。我举出这三个例子并不是为了指出改进死代码生成算法的必要性，而是为了强调将混淆引擎设计为支持轮换调用各种混淆算法的形式的必要性。如果说死代码生成了一个变量，那么在其它混淆算法中最好设法引用该变量。
2.1.3 常量展开
常量折叠是最早的基本编译优化手段之一。这种优化的目的是将可以在编译期就能推导出结果的计算用结果来替换。
Mov eax,2018
Add eax,2
显然，如果忽略标志位的变化，该段代码等价于Mov eax,2020。
2.1.4 数据储存、编码
数据的储存方式都是约定成俗的。如果我们要储存整数1238326，用int类型是首选，当然，用可变类型也是可以的。同理，三维数组也可以降维为一维数组。更进一步地，储存一个int变量，我们可以用连续的4字节内存，也可以采用不连续的4字节内存，当然，使用后者要自己调整加减乘除等运算。
对数据进行编码也是一种混淆方案。在对编码后的数据进行操作时，有必要将数据解码，显然，这会暴露解码函数。同态加密可以解决这个问题，使用同态加密能够在数据解码前操作它们，通过对编码后的数据定义一个等价运算。目前已经有不少文献在面向混淆的视角下讨论过这种问题，但可惜这门学科所需要的知识背景远超我的能力范围，有兴趣的读者请自行研究。
2.1.5 恒等运算替换
使用布尔代数，将一些简单的运算扩展为更为复杂的逻辑运算，该技巧为许多混淆引擎采用，比如“臭名昭著”的VMP万用门。掌握基本的几个等值式就可以进行逻辑运算的推导，该部分内容较为简单，就不再做赘述。
2.1.6 模式替换
模式替换的概念很简单，混淆者定义一些较复杂的指令序列，在待混淆程序中进行语义等价的替换。
Push imm32
Lea esp,[esp-4]
Mov [esp],imm32
Push reg32
Mov reg32,esp
Xchg [esp],reg32
Pop esp
Mov esp,[imm32]
Push reg32
Xor reg32,reg32
Dec reg32
S1: Inc reg32
Cmp reg32,esp32
Jnz S1 ;假定esp的值不可能等于-1
Xchg [esp],reg32
Pop esp
Mov esp,[imm32]
聪明如你，可看出了上面四段代码的等价关系？这三个例子说明，模式替换的匹配替换过程是可以不断继续下去的。模式替换对应的就是编译优化技术中的窥孔优化。第4段代码中对Mov的变形是一位前辈指点我的，据前辈说是污点漂白的一个上不得台面的小trick。
2.1.7 常量隐藏
将常量值直接暴露在指令的操作数中，可能会向攻击者透露一些有用的信息。将代码中的明文常量值隐藏起来似乎是非常有必要的。
0 Mov eax,2018
1 Mov eax,[402024] ;地址为402024的全局变量中储存的值为2018
上述两段代码中，1行指令较之0行指令有了一点安全性上的提升，但显然还不够。为了将常量隐藏，我们可以引入一些数学技巧，如sin^2(x) + cos^2(x) = 1，以此构造一些返回值恒定的函数。再进一步，我们可以利用一些API的特性，如故意传递错误的参数，利用API返回的异常代码。如果异常代码是200，而我们需要的定值是100，那该怎么办呢？答案当然是，得到异常代码后减去100啊！
2.2基于控制流
2.2.1 函数内联，外联和混合
函数内联的定义不再赘述。函数外联指将某一函数的一部分提取出来单独构成一个函数，并将其替换为对新创建的函数的调用。
函数混合指将多个函数混合在一起。在调用混合后的函数前，由混淆代码调整上下文，来指定究竟应该执行哪个函数。以一段代码为例。
fun1() {
s1
...
sn
}
fun2() {
k1
...
kn
}
fun_mix(n) {
if (n) {
s1
....
sn
}
else {
k1
...
kn
}
}
当然，实际混合时不会如此简单，比如可以用多个参数来指示欲执行函数。
2.3 基于控制流与数据流
2.3.1 不透明谓词
Collberg把不透明谓词定义为一个布尔表达式。该表达式的值在混淆前是已知的，且混淆后再探明其性质需要付出一定代价。如果该表达式恒为true，则称为永真不透明谓词，记为PT。同理，还有永假不透明谓词（PF），可真可假不透明谓词（P?）。值得一提的是，可真可假不透明谓词的两条分支处的代码块在语义是上等价的，但可以使用不同的混淆策略对其进行混淆。吴伟民[2]等首次提出了N态不透明谓词。
并不是说谓词所涉及到的数学知识越多就越强大，足够复杂的谓词确实可以难倒静态分析工具，但人工检测谓词的效率有时却出奇的高。这正是Collberg[1]提出的混淆评估指标中的隐蔽性。
为了增强谓词的强度，王志[3]提出了使用数学未解猜想构造不透明谓词。不过要实现它比较困难，其一是如何将某个猜想在混淆的视角下运用，其二是如何逃避人工检测。王志提出了使用角谷猜想。但如何运用，仍然是个头疼的问题。
比如最容易想到的一个性质，即角谷猜想生成的数列最终收敛于定值1。
While (x >= 30) {...}
While (x >= 30 && x - y <= 29) {...}
其中y是由程序输入引出的一个变量，并按照角谷猜想进行了若干次迭代。
类似这种混淆，要抵御人工检查仍是不太现实。
2.3.2 路径分支信息隐藏
程序的反汇编代码总是会暴露分支的信息，以一段代码为例：
0 Cmp eax,2019
1 Jnz s
0 Push eax
1 Call hash
2 Cmp eax,hash(2019)
3 Jnz s
第一段代码暴露出了分支的条件是jnz，目标是s，成立条件是eax等于2019。第二段代码是对其进行路径分支信息隐藏后的代码。
控制流平坦化与不透明谓词都只适用于无分支代码的混淆，目前的路径分支信息隐藏混淆策略，都是针对约束求解器对于非线性运算求解的困难提出的。王志[4]将保留前缀算法与哈希函数相结合提出了一种新的路径分支混淆策略。因为哈希函数不具备保序性，所以引入保留前缀算法，取能使跳转成立的所有整数的集合并取其前缀后使用哈希函数加密。贾福春等[5]提出使用随机森林构建混淆，使解混淆的难度等价于提取出随机森林的规则。但这些方法都很难抵御最原始的二分查找法暴力搜寻区间边界。
2.3.3 控制流平坦化
控制流平坦化将基本块直接的联系隐藏在对Dispatch的调用中，最简单的实现是将函
用一个switch-case结构重写。以一段代码为例：
int code = 0;
while (1)
{
switch (code)
{
case 0:
i = 50;
code = 1;
break;
case 1:
if (i < 20)
code = 2;
else
code = 3;
break;
case 2:
if (i >= 0)
code = 4;
else
code = 5;
break;
case 3:
if (i <= 100)
code = 6;
else
code = 5;
break;
case 4:
i -= 3;
code = 2;
break;
case 5:
return 0;
case 6:
i += 3;
code = 3;
基于二进制代码实现混淆器
3.1 静态分析方法
3.1.1 定值分析
定值分析是在基本块内完成的，其过程如下：
1.定值分析自顶向下分析
2.基本块首指令所有寄存器的来源均初始化为-1
3.每条指令的来源向下传递
4.当某一指令写入某寄存器时，修改来源中某寄存器为该指令的行数
请注意call指令的特殊性，从语义来看，它不影响除esp以外的7个通用寄存器，但call指令在返回后可能会修改任何寄存器！对其进行分析时，可以认为它不修改寄存器，也可以认为它修改了。前者是保守地分析，但能确保绝不会出错。后者则需要承担一定的风险，比如我们可以取所有调用方式保护寄存器的交集，认为call指令只修改这个集合中的元素。
还要注意高位与低位寄存器间的联系。以eax,ax,al,ah为例，当指令写入eax或ax时，我们认为它同时写入了(ax),al,ah。其它情况同理处理。
3.1.2 栈分析
栈分析指分析出每条指令所访问的栈变量。其实现很简单，就不多做赘述了。
在生成混淆代码中，有时我们要从栈里开辟空间。但注意，一定要使用EBP对栈空间进行访问。在常规情况下，使用ESP访问栈空间也能得到正确的结果。但MSVC提供了_alloca库函数，尽管它不在标准之中，但MSVC实现C99规定的变长数组基于_alloca。
请记住，栈分析的结果不是精确的，最好不要尝试将栈分析的结果用于活跃分析。将栈分析的结果用于活跃分析只适用于一些极端情况，如不存在指针别名等。
3.1.3 活跃分析
活跃分析的难题是如何构造出CFG，在解混淆时，这个问题尤其令人头痛，有时你要恢复控制流，就不得不恢复数据流，而恢复数据流，又要先恢复控制流……有时编译器优化后生成的目标代码也会比较难处理，比如当目标代码使用了隐式的控制流转移时，如switch-case的生成跳转表的一种优化形式。
活跃分析分为两部分，一是基本块内的活跃分析，而是基本块间的活跃分析。
基本块内的活跃分析规则如下：
1.活跃分析应从自底向上分析
2.初始化出口处的所有寄存器的活跃状况
3.寄存器的活跃性持续向上传递，但遇到对该寄存器的读写操作时，会变更活跃性
4.当某一寄存器向上传递活跃性遇到写操作时，则活跃性变为死状态，若遇到读操作时，则活跃性变为活状态
5.当出现对同一寄存器进行读写操作时，我们默认读操作先于写操作
基本块间的活跃分析初始化规则如下：
1.为每个基本块建立IN，OUT集合，记录其入口与出口处的活跃寄存器集合
2.初始化所有exit块的IN
3.计算出每个基本块的def与use集合。def集合中是在基本块中定值先于任何引用的寄存器集，use集合放入引用先于定值的寄存器集。
4.初始化所有除exit块外的基本块的IN为∅
而后开始迭代求解，伪代码如下：
while (某个IN值发生改变) {
for (除exit之外的每个基本块B) {
OUT[B] = IN[B的后继1] ∪ IN[B的后继2] ∪ ... ∪ IN[B的后继i] //1
IN[B] = useB ∪ (OUT[B] - defB) //2
}
}
1说明一个寄存器在一个基本块的出口处活跃当且仅当它在该基本块的某个后继入口处活跃。
2说明一个寄存器要在进入一个基本块时活跃，必须满足两个条件中的一个：要么它在基本块内被重新定值之前就被使用；要么它在基本块的出口处活跃且基本块没有对它进行重新定值。
实际对代码进行分析时，要首先初始化exit块的出口处的寄存器活跃状况，使用基本块内的活跃分析计算出其入口处的活跃状况。再开始基本块间的活跃分析，迭代求出所有除exit之外的基本块的出口处的活跃状况，再使用基本块内的活跃分析其每一条指令上的活跃状况。初始化exit块的出口处的寄存器活跃状况时，可以直接初始化所有寄存器为活状态，或者取所有调用约定的保护寄存器的并集赋值为活状态，这又是一个保守与冒险的问题。
4 附录
4.1 本文的姊妹篇
代码混淆之我见（一）
代码混淆之我见（三）
代码混淆之我见（四）
4.2 参考文献
[1]COLLBERG, THOMBORSONC, LOW D. A taxonomy of obfuscating transformations[R]. Department of computer science the university of auckland New Zealand, 1997
[2]吴伟民, 林水明, 林志毅. 一种基于混沌不透明谓词的压扁控制流算法[J]. 计算机科学, 2015, 42(5):178-182.
[3]王志. 二进制代码路径混淆技术研究[D]. 南开大学.
[4]王志,贾春福,刘伟杰,王晓初,张海宁,于晓旭,陈.一种抵抗符号执行的路径分支混淆技术[J].电子学报,2015,(第5期).
[5]王志, 贾春福, 刘伟杰, et al. 一种抵抗符号执行的路径分支混淆技术[J]. 电子学报, 2015, 43(5):870-878.
[6]陈喆, 贾春福, 宗楠, et al. 随机森林在程序分支混淆中的应用[J]. 电子学报, 2018, 46(10):156-164.
[7]潘雁,祝跃飞,林伟.基于指令交换的代码混淆方法[J].软件学报,2019,(第6期).
[8]数据流分析（二） https://blog.csdn.net/dashuniuniu/article/details/50709160
[9]C. Wang. A security architecture for survivability mechanisms[D]. University of Virginia, 2001
[10]G. Wroblewski. General method of program code obfuscation[D]. Wroclaw University of Technology, Institute of Engineering Cybernetics. 2002
[11]吴适. 基于二进制代码混淆的软件保护研究[D]. 电子科技大学.
[12]http://z0mbie.daemonlab.org/pcond.txt
5 感慨
玩壳也断断续续地搞了一年左右，粗略计算我扔了80h进去。然而我这80h算打水漂了，真打水漂了，就给我留了一地肤浅的鸡毛。有时候想起一年前做的那些蠢事，都能把自己逗笑。不过写完这最后一个字，我就彻底和2018的我“决裂”啦！
这篇文章从去年10月开始写起，修修补补弄了一年多，上下句，段间的联系可能根本不通。
[培训]内核驱动高级班，冲击BAT一流互联网大厂工
作，每周日13:00-18:00直播授课
上传的附件：
