一、前言

在之前去混淆的过程中，发现去混淆的程序中，伪代码与原程序伪代码相差无几，然而如果仔细观察汇编代码的话，可以发现存在较多的冗余代码，即混淆过程中产生的垃圾代码。那么如何去除这些冗余汇编指令呢？

二、基于Liveness Analysis的想法

先给出我们需要解决一个例子（这是一个虚假控制流混淆中的部分代码，其中标*的为冗余汇编指令）：

  mov     rax, [rbp+var_10]
  movsxd  rcx, [rbp+var_14]
  movsx   eax, byte ptr [rax+rcx]
  add     eax, [rbp+var_18]
  mov     [rbp+var_18], eax
* mov     rax, offset x
* mov     eax, [rax]
* mov     rcx, offset y
* mov     ecx, [rcx]
* mov     edx, eax
* sub     edx, 1
* imul    eax, edx
* and     eax, 1
* cmp     eax, 0
* setz    al
* cmp     ecx, 0Ah
* setl    cl 
* or      al, cl    
* test    al, 1      
* jnz     loc_401235

最开始的想法是从第20行的汇编指令开始，跟踪与该指令以及后续指令相关的指令。如何跟踪呢？简单想就是跟踪这些指令使用到的寄存器。

2.1 Liveness Analysis

Liveness Analysis是一种数据流分析技术，用于确定程序中的每个变量在程序的不同点上是否“活跃”。“活跃”的意思是变量在某个程序点后将被使用，且在这之前没有被重新定义。这项技术在编译器优化、寄存器分配和死代码消除中起着关键作用。

本文章中主要用到了里面的def和use集合的想法。

• def集合：当前汇编指令显式和隐式改变的寄存器、内存的集合。
• use集合：当前汇编指令显式和隐式使用的寄存器、内存的集合。

2.2 改进Liveness Analysis以适配

然而从图中看，似乎Liveness Analysis技术没有考虑到标志寄存器的改变和使用。对于Liveness Analysis技术能否解决我所预设的问题，我也不太清楚。因此在此基础上，进行如下改进：

• 引入标志寄存器来跟踪相关指令，这对于一些条件指令的跟踪是有帮助的。
• 对于内存操作数（例如[rbp+var_10]），还应提取其表达式中的寄存器，存入use集合中。因为我认为既要跟踪内存地址是怎么来的，也要跟踪内存地址对应的值是怎么来的。
• 对于指令中操作数既不是寄存器，也不是内存的（例如var_4、全局变量x），应认为它们是常量，即不加入use集合中。
• 由于指令中出现的寄存器名可能是同一寄存器的不同位数区分（例如rax, eax, ax, ah, al），统一将它们转换成最大位数的寄存器名。

对刚才那个例子进行def和use集合的分析，结果如下：

  mov     rax, [rbp+var_10]              def={rax}       use={[rbp+var_10], rbp}         
  movsxd  rcx, [rbp+var_14]              def={rcx}       use={[rbp+var_14], rbp}
  movsx   eax, byte ptr [rax+rcx]        def={rax}       use={[rax+rcx], rax, rcx}
  add     eax, [rbp+var_18]              def={rax}       use={rax, [rbp+var_18], rbp} 
  mov     [rbp+var_18], eax              def={[rbp+var_18]}       use={rax, rbp}//理应认为[rbp+var_18]的寻址用到了rbp
* mov     rax, offset x                  def={rax}       use={}//认为x是具体值，不加入到use集合中
* mov     eax, [rax]                     def={rax}       use={rax, [rax]}//既要知道内存地址对应的值从哪来的，也要知道内存地址从哪来的
* mov     rcx, offset y                  def={rcx}       use={}//认为y是具体值，不加入到use集合中
* mov     ecx, [rcx]                     def={rcx}       use={rcx, [rcx]}
* mov     edx, eax                       def={rdx}       use={rax}
* sub     edx, 1                         def={rdx}       use={rdx}
* imul    eax, edx                       def={rax}       use={rax, rdx}
* and     eax, 1                         def={rax}       use={rax}
* cmp     eax, 0                         def={rflags}     use={rax}
* setz    al                             def={rax}       use={rflags}
* cmp     ecx, 0Ah                       def={rflags}     use={rcx}
* setl    cl                             def={rcx}       use={rflags}
* or      al, cl                         def={rax}       use={rax, rcx}
* test    al, 1                          def={rflags}     use={rax}
* jnz     loc_401235                     def={}          use={rflags}

具体跟踪的初步想法是：

1. 给定某一指令 $I$I ，初始化跟踪集合 $trace=us$trace=useI​ （指令 $I$I 的 $use$use 集合），初始化相关指令列表 $relevantInsns=\left[I\right]$relevantInsns=[I]。
2. 往上追溯每条指令，如果 $trace\cap de\ne \varnothing$trace∩defIi​​=∅ ，那么认为指令 $$Ii​ 是相关指令，将指令 $$Ii​ 加入到 $relevantInsns$relevantInsns中， 同时在 $trace$trace 集合删除交集中的元素，并将指令 $$Ii​ 的 $use$use 集合中的元素加入进来，即进行如下运算：$trace=(trace-(trace\cap de\left)\right)\cup us$trace=(trace−(trace∩defIi​​))∪useIi​​ 。如果 $trace\cap de=\varnothing$trace∩defIi​​=∅ ，那么认为指令 $$Ii​ 是不相关指令，不进行任何操作。
3. 在追溯的过程中，如果 $trace=\varnothing$trace=∅ 或者待跟踪指令集为空，则认为跟踪结束。

感觉说的有些混乱，就那上面这个例子解释一下吧。首先我们假设跟踪的指令为jnz loc_401235，后续步骤如下：

初始化: trace = {rflags}	relevantInsns = [20]	(为了简洁，用行号代替指令)	
往上分析:
19: trace ∩ use = {rflags},  是相关指令。   更新 trace = {rax}, relevantInsns = [19, 20]
18: trace ∩ use = {rax},     是相关指令。   更新 trace = {rax, rcx}, relevantInsns = [18, 19, 20]
17: trace ∩ use = {rcx},     是相关指令。   更新 trace = {rax, rflags}, relevantInsns = [17, 18, 19, 20]
16: trace ∩ use = {rflags},  是相关指令。   更新 trace = {rax, rcx}, relevantInsns = [16, 18, 19, 20]
15: trace ∩ use = {rax},     是相关指令。   更新 trace = {rcx, rflags}, relevantInsns = [15, 16, 18, 19, 20]
14: trace ∩ use = {rflags},  是相关指令。   更新 trace = {rax, rcx}, relevantInsns = [14, 15, 16, 18, 19, 20]
13: trace ∩ use = {rax},     是相关指令。   更新 trace = {rax, rcx}, relevantInsns = [13, 14, 15, 16, 18, 19, 20]
12: trace ∩ use = {rax},     是相关指令。   更新 trace = {rax, rcx, rdx}, relevantInsns = [12, 13, 14, 15, 16, 18, 19, 20]
11: trace ∩ use = {rdx},     是相关指令。   更新 trace = {rax, rcx, rdx}, relevantInsns = [11, 12, 13, 14, 15, 16, 18, 19, 20]
10: trace ∩ use = {rdx},     是相关指令。   更新 trace = {rax, rcx}, relevantInsns = [10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
9: trace ∩ use = {rcx},      是相关指令。   更新 trace = {rax, rcx, [rcx]}, relevantInsns = [9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
8: trace ∩ use = {rcx},      是相关指令。   更新 trace = {rax, [rcx]}, relevantInsns = [8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
7: trace ∩ use = {rax},      是相关指令。   更新 trace = {rax, [rax], [rcx]}, relevantInsns = [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
6: trace ∩ use = {rax},      是相关指令。   更新 trace = {[rax], [rcx]}, relevantInsns = [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
5: trace ∩ use = {},         不是相关指令。     trace = {[rax], [rcx]}, relevantInsns = [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
4: trace ∩ use = {},         不是相关指令。     trace = {[rax], [rcx]}, relevantInsns = [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
3: trace ∩ use = {},         不是相关指令。  	 trace = {[rax], [rcx]}, relevantInsns = [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
2: trace ∩ use = {},         不是相关指令。   	 trace = {[rax], [rcx]}, relevantInsns = [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
1: trace ∩ use = {},         不是相关指令。  	 trace = {[rax], [rcx]}, relevantInsns = [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20]
待分析指令集为空，结束跟踪

对于上述例子，我们的想法成功的追踪到了所有冗余指令。然而当存在cmovcc指令时，我们的想法并不是很理想。

2.3 cmovcc指令所带来的问题

以下是控制流平坦化混淆的垃圾汇编指令（其中标*的为冗余汇编指令）。

* mov edx, [rbp+var_4]			def={rdx} 			use={[rbp+var_4], rbp}
* mov eax, 4A...h 				def={rdx} 			use={}
* mov ecx, 32..h				def={rcx} 			use={}
* cmp edx, 2					def={rflags} 		use={rdx}
* cmovnz eax, ecx				def={rax} 			use={rcx,rflags}	或者	def={}		use={rflags}
* mov [rbp+var_1c], eax  		def={[rbp+var_1c]} 	use={rax, rbp}
* jmp loc_401418 				def={} 				use={}

由于cmovnz存在执行和不执行的情况，因此需要分两种情况讨论：

• 当标志寄存器满足cmovnz的条件时，执行cmovnz指令，此时def={rax}, use={rcx,rflags}。
• 当标志寄存器不满足cmovnz的条件时，不执行cmovnz指令，此时def={}, use={rflags}。

单独分析以上任何一种情况，其结果都不能覆盖所有的冗余指令，但其两者情况的并集能够覆盖所有冗余指令。因此在向上溯源时，需要注意是否时cmovcc指令，如果是，则需要保存当前状态，探索其中一条路径，当该路径探索完毕后，再探索另一种路径。此情况可通过递归实现。

三、代码实现

接下来主要展示代码中重要的部分，完整代码请参考https://github.com/gal2xy/AssembleCodeTracer。

3.1 汇编指令字典的建立

对于刚才所展示的例子中，我们可以直观的看出指令的def和use集合，但是计算机不行。这是我所面临的第一个麻烦，解决这个问题，后续分析才能进行下去。为此，我建立了一个简单的汇编指令字典，部分示例如下：

3.2 解析指令中的操作数

由于汇编指令中的操作数有多种类型，且对于不同类型的操作数，我们需要进行不同的操作。

• 寄存器类型可以直接放入def和use集合中。
• 内存不仅可以直接放入def和use集合中，而且还需要解析其表达式中的寄存器，这些寄存器也要放入def和use集合中。
• 立即数则不应放入def和use集合中，应认为它是某一寄存器跟踪结束的标志。

3.3 从内存表达式中提取寄存器

由于指令中的内存可能是一个表达式的情形，例如[2*rax+rbx-1]，我们可以直观的看出，它肯定使用了rax、rbx寄存器，因此我们需要实现一个函数来提取内存表达式中的寄存器。

3.4 获取指令中的def和use集合

这一步就需要借助到 3.1 所定义的汇编指令字典。整个函数的功能为：

• 获取def集合：获取当前指令的def_exp_index键值，根据索引值列表找到对应的具体操作数，并根据操作数的类型进行不同操作。之后再获取当前指令的def_imp_reg键值，将隐式定义的寄存器加入到def集合中。
• 获取use集合：同理类似。

3.5 跟踪相关汇编指令

最终算法如下：

1. 给定待跟踪的指令I，以及所需跟踪的指令范围，初始化 $traceSet=useSe$traceSet=useSetI​，$relevantInsPos=\left\{I\right\}$relevantInsPos={I}，$startPos=po$startPos=posI​，其中$po$posI​为指令 $I$I 在$Insns$Insns中的索引值。
2. 开始向上探索（即$startPos--$startPos−−），对于每一条指令 $$Ii​，$i\in [,po)$i∈[0,posI​)：
   1. 如果 $traceSet\cap defSe\ne \varnothing$traceSet∩defSetIi​​=∅ ，则指令 $$Ii​ 为相关指令，更新 $tarceSet=(traceSet-defSe)\cup useSe$tarceSet=(traceSet−defSetIi​​)∪useSetIi​​ 以及 $\to relevantInsPos$Ii​→relevantInsPos。（对于cmovcc指令，需先进行如下操作：定义 $newTarceSet=traceSet\cup \left\{rflags\right\}$newTarceSet=traceSet∪{rflags} ，递归调用当前算法，将返回结果当前 $relevantInsPos$relevantInsPos合并)
   2. 如果 $traceSet\cap defSe=\varnothing$traceSet∩defSetIi​​=∅ ，则指令 $$Ii​ 为非相关指令，不进行任何操作。
3. 如果 $traceSet=\varnothing$traceSet=∅或者startPos<0， 则跟踪结束，返回 $relevantInsPos$relevantInsPos ，否则继续进行步骤2。

四、不足之处

当真实汇编指令与垃圾汇编指令构成了标志寄存器的前者定义后者使用的关系时，此算法会造成误判。具体例子如下所示。（其中标*的为冗余汇编指令，其余为真实代码）

  mov     rax, [rbp + var_10] 
  movsx   edx, byte ptr [rax + 3]
* mov     eax, 7A39EAC0h
* mov     ecx, 9BEE23F6h
  cmp     edx, 65h 
* cmovl   eax, ecx
* mov      [rbp + var_1C], eax
* jmp      loc_401418

由于cmovl指令依赖标志寄存器，因此会将第5行的cmp指令纳入到相关指令集合中（然而第5行的cmp指令是真实代码），以至于后续将其余真实代码也囊括进来，最终造成了误判！这个问题似乎解决不了，所以我认为我这个想法到头来还是失败的。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课