吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 3009|回复: 52
上一主题 下一主题
收起左侧

[原创] vmp trace的优化处理

  [复制链接]
跳转到指定楼层
楼主
白云点缀的藍 发表于 2022-7-27 16:43 回帖奖励

前言

在之前写的《利用机器学习分析vmp的思路》中,把读写内存的操作数直接替换成了绝对地址的形式,这就产生了大量赋值语句,阅读起来也不是很友好。写这篇文章的主要目的是如何做进一步的优化,本篇文章用到了程序切片技术和编译原理中的一些优化算法,复制传播、死代码删除和有向无环图DAG的局部优化。

trace的处理

在之前写的文章基础上对trace增加了eflags寄存器的记录。利用程序切片技术提取了handle与写内存相关的指令后,通过一些简单的特征就可以处理该样本trace中所有的handle,所以本篇没有使用深度学习的方法对handle进行分类处理,深度学习也只是通过有标签的handle数据集代替了人工提取特征的过程。
trace处理后会得到以下文件:

NormalCode表示正常的代码,不需要对其优化处理,VmProcedureCode表示虚拟机中执行的代码,后面的数字表示执行的顺序。handle的识别和处理参考相应的代码

复制传播

复制传播(Copy Propagation)的思想:对于给定的关于某个变量v和s的赋值v=s,在没有出现其他关于v定值的程序范围内,可以用s来替代出现的v的引用。

handle处理后,trace中含有大量的mov语句,可以利用复制传播配合死代码消除处理掉冗余的mov语句。
比如有以下指令序列:

b=a
c=b
d=c

按照复制传播的思想,c可以用a代替,即d=a。如果c是不活跃的,那么c=b是可以删除的。
复制传播可以通过ud链(Use-Definition Chains)实现,ud链描述的是指令或语句中引用的变量可能定值点的位置。因为在很多情况下,一个定值是否能实际到达某一特定程序点是不可判定的,有时候需要依赖于特定的外部输入。当然,在trace中可以直接认为都是可到达的。ud链的构造可以通过到达定值分析实现,但是在trace中,可以认为语句之间是顺序执行的,ud链的构造只要向上遍历找到最后出现的对当前变量定值的语句即可。代码实现在VmProcedureCode类中的CopyPropagation和DeadCodeEliminatioin部分

在虚拟机的代码中,设定的活跃变量如下:

eax、ebx、ecx、edx、esi、edi、esp、eip、eflags寄存器
esp+4,对应虚拟机退出后的跳转地址,去执行正常函数
esp+8,正常函数执行完后的跳转地址,通常是虚拟机的入口
esp+12,可能是正常函数的参数一
esp+16,可能是正常函数的参数二
esp+20,可能是正常函数的参数三
esp+24,可能是正常函数的参数四
esp+28,可能是正常函数的参数五
esp+32,可能是正常函数的参数六

以VmProcedureCode0.txt中的最后几行代码为例

0x0076591d: mov eax, dword ptr [0xffffcb5c]
0x007e9342: mov dword ptr [0xffffcac8], eax
0x006cbe8e: mov eax, dword ptr [0xffffcb34]
0x006cbe9d: add eax, 0x77cb5a           
0x0068849d: mov dword ptr [0xffffcad8], eax
0x007df911: mov eax, dword ptr [0xffffcb34]
0x007df919: add eax, 0x74fbf3           
0x007df91b: mov dword ptr [0xffffcb60], eax 
0x0068867f: mov eax, dword ptr [0xffffcb34] 
0x00688684: add eax, 0x68304e       
0x0068868a: mov dword ptr [0xffffcb5c], eax 
0x007cf964: mov edx, dword ptr [0xffffcac8] 
0x006ef09c: mov dword ptr [0xffffcb58], edx     
0x006d717b: mov ebp, dword ptr [0xffffcad0]             
0x006d717e: mov ecx, dword ptr [0xffffcac4]             
0x006d7180: mov ebx, dword ptr [0xffffcaec]             
0x006d7181: mov eax, dword ptr [0xffffcad8]             
0x006d7185: mov edi, dword ptr [0xffffcae0]             
0x006d7187: mov edx, dword ptr [0xffffcab8]             
0x006d718d: mov esi, dword ptr [0xffffcac0]             
0x006d718e: popfd

最后一行的代码中esp=0xffffcb58,0x00688684地址处的0x68304e刚好对应虚拟机退出后的跳转地址,0x007df919地址处的0x74fbf3对应的是下一个虚拟机入口。0x006cbe9d地址处的 0x77cb5a 对应0x68304e函数的参数,ida中0x68304e地址处的代码反编译如下:

HMODULE __usercall GetModuleHandleA_68304E@<eax>(int a1@<eax>)
{
  unsigned int v1; // edx
  int v2; // edi
  CHAR v3; // al
  CHAR ModuleName[260]; // [esp+0h] [ebp-104h] BYREF

  v1 = 0;
  v2 = a1 - (_DWORD)ModuleName;
  do
  {
    v3 = ModuleName[v1 + v2] ^ (v1 + __ROL4__(0x4BB06C51, v1));
    ModuleName[v1] = v3;
    if ( !v3 )
      break;
    ++v1;
  }
  while ( v1 < 0x104 );
  return GetModuleHandleA_1(ModuleName);
}

程序切片技术

程序切片技术是为了替换之前使用的污点分析,方便获取handle中与写内存相关的指令。
给定一个感兴趣的语句以及它所使用的变量,程序切片(program slicing)是一个影响该条语句变量值的语句集合,而切片准则(slicing criterion)用来描述这个感兴趣的语句及其变量。切片准则可以定义为C = <statement, variables>,statement可以为语句的唯一序号,variables为变量集。比如有以下程序,令切片准则C=<10, {product}>,箭头左边为原程序,箭头右边为对应C的程序切片。

程序切片的实现主要有基于程序依赖图和基于数据流方程两种方法。程序依赖图包含数据依赖和控制依赖,它的构建可以查看鲸书等相关资料,这里只介绍基于数据流方程的方法。数据流方程迭代的公式如下:

k表示迭代次数,如果把语句当做CFG中的一个结点而不是基本块的话,那么i和j就是一个语句,其中i是j的前驱结点。
DEF(i)和REG(i)分别表示i结点的变量定值集和引用集。
C和(b, REF(b))表示相应的切边准则。
B[k][C]是分支语句集,表示影响S[k][C]中切片语句的分支语句集合,用来跟踪控制依赖关系,迭代过程中当B[k][C]不在改变时,迭代终止。
INFL(b)表示从b开始到距离它最近的后向支配语句之间的路径上除去端点以外所有语句的集合,INFL(b)在其直接后驱大于等于2时才不为空,否则为空集。INFL(b)中的语句执行受b语句执行结果的影响,控制依赖于b。
R[k]C表示结点i中与切片准则C相关的变量集合,用来跟踪数据依赖。
S[k][C]表示程序切片。
初始化时,R[0]C等于切片准则C中的变量集variables,n为C中的statement,当n≠m时,R[0]C为空集。之后再从以下公式计算各个结点的R[0][C]和S[0][C]。

基于数据流方程的过程内切片伪算法如下:

由于vmp的handle代码是顺序执行,所以针对handle的切片处理不需要多轮迭代和控制依赖的跟踪,也就不需要计算INFL(b),相应的切片算法会变得很简单,只需要一轮迭代计算出R[0][C]和S[0][C]就可以得到对应的切片。

基于DAG有向无环图的局部优化

把基本块转换到DAG有向无环图的表示,在DAG上可以对基本块中的代码进行一些转换,改进代码的质量。

龙书中的关于DAG的构造方式如下:
1)基本块中出现的每个变量有一个对应的DAG的结点表示其初始值。
2)基本块中的每个语句s都有一个相关的结点N。N的子结点是基本块中的其他语句的对应结点。这些语句是在s之前、最后一个对s所使用的某个运算分量进行定值的语句。
3)结点N的标号是s中的运算符,同时还有一组变量被关联到N,表示s是在此基本块内最晚对这些变量进行定值的语句。
4)某些结点被指明为输出结点(output node),这些结点的变量在基本块的出口处活跃。也就是说,这些变量的值可能以后会在流图的另一个基本块中被使用到。计算得到这些“活跃变量”是全局数据流分析的问题。

针对vmp的trace主要做一些以下优化:
1、消除局部公共子表达式(local common subexpression),公共子表达式就是重复计算一个已经计算得到的值的指令。当一个新的结点M将被加入到DAG中时,我们检查是否存在一个结点N,它和M具有同样的运算符和子结点,且子结点顺序相同。如果存在这样的结点,N计算的值和M计算的值是一样的,可以用N替换M
2、常量折叠
3、使用代数规则简算计算过程,比如vmp中not、and和or等指令组合起来的MBA表达式

以VmProcedureCode0.txt中的前面103行代码为例

0x0064d71e: mov dword ptr [0xffffcfe8], ecx             
0x006fa4c2: mov dword ptr [0xffffcf34], edx             
0x00746037: mov dword ptr [0xffffcf3c], ebp             
0x0064fb73: mov eax, 4              
0x006b7076: add eax, 0xffffcff8     
0x006b707f: mov dword ptr [0xffffcff4], eax             
0x0075d399: mov eax, 8              
0x0075d3a7: add eax, 0xffffcff4     
0x0081c8fb: mov ecx, eax            
0x0081c903: mov edx, dword ptr [0xffffcff4]             
0x0081c906: not ecx             
0x006e651b: not edx             
0x006e651e: or  ecx, edx        
0x00750b99: mov eax, ecx        
0x00750ba3: add eax, 0x20       
0x00750bb2: pushfd              
0x00750bba: pop dword ptr [0xffffcff4]          
0x0077cd5f: mov ecx, dword ptr [0xffffcff4]             
0x007294f8: mov dword ptr [0xffffcf18], ecx             
0x007b85c7: mov ecx, eax        
0x007b85d0: mov edx, eax        
0x007b85d3: not ecx             
0x007b85d6: not edx             
0x007b85d8: or  ecx, edx        
0x007b85e0: pushfd              
0x007b85e9: pop dword ptr [0xffffcff4]              
0x00687ebb: mov ecx, dword ptr [0xffffcf18]             
0x00687ebf: mov edx, dword ptr [0xffffcf18]             
0x00674371: not ecx             
0x0067437a: not edx             
0x0067437f: or  ecx, edx        
0x00674383: mov dword ptr [0xffffcfd8], ecx             
0x006a83d9: mov ecx, 0xfffff7ea             
0x006a83df: mov edx, dword ptr [0xffffcfd8]             
0x006a83e2: not ecx             
0x006a83e4: not edx             
0x006a83ed: and ecx, edx        
0x006a83ef: mov dword ptr [0xffffcfd8], ecx             
0x00809c7d: mov ecx, dword ptr [0xffffcff4]             
0x00809c7f: mov edx, dword ptr [0xffffcff4]             
0x00739b61: not ecx             
0x00739b63: not edx             
0x00739b65: or  ecx, edx                
0x00739b67: mov dword ptr [0xffffcfd4], ecx             
0x00740510: mov ecx, 0x815              
0x00740516: mov edx, dword ptr [0xffffcfd4]             
0x00740519: not ecx             
0x00740520: not edx             
0x00740525: and ecx, edx        
0x007f9eca: mov eax, ecx        
0x007f9ed9: add eax, dword ptr [0xffffcfd8]             
0x007bd4bc: mov dword ptr [0xffffcf50], 0               
0x0070d7e7: mov dword ptr [0xffffcf20], ebx             
0x00723792: mov dword ptr [0xffffcf14], eax             
0x006f8562: mov dword ptr [0xffffcf44], esi             
0x006d7d4c: mov ecx, dword ptr [0xffffcfe8]             
0x006d7dab: mov dword ptr [0xffffcf28], ecx             
0x007964f4: mov ecx, dword ptr [0xffffcf34]             
0x0079653f: mov dword ptr [0xffffcf1c], ecx             
0x007bdb9e: mov dword ptr [0xffffcf30], edi             
0x0069f4d8: mov dword ptr [0xffffcf24], eax             
0x007bd4bc: mov dword ptr [0xffffcf34], 0xffffcfd4       
0x006f8529: mov ecx, dword ptr fs:[0]               
0x006f8562: mov dword ptr [0xffffcf4c], ecx             
0x0068a851: mov eax, 4              
0x0068a867: add eax, 0xffffcfc0         
0x0068a86e: mov dword ptr [0xffffcfbc], eax             
0x007d8470: pushfd              
0x007d8478: pop dword ptr [0xffffcfb8]              
0x006d7d4c: mov ecx, dword ptr [0xffffcfb8]         
0x006d7dab: mov dword ptr [0xffffcf48], ecx         
0x007fb9d4: mov eax, 8              
0x007fb9d9: add eax, 0xffffcfbc     
0x007fb9ea: pushfd              
0x007fb9eb: pop dword ptr [0xffffcfb4]              
0x0067df7a: mov ecx, dword ptr [0xffffcfb4]         
0x0067dfd4: mov dword ptr [0xffffcf2c], ecx         
0x006a4226: mov ecx, dword ptr [0xffffcfbc]         
0x006d370e: not eax             
0x006d3710: not ecx             
0x006d3712: or  eax, ecx        
0x006d3717: pushfd              
0x006d3718: pop dword ptr [0xffffcfb8]              
0x0077c25e: mov ecx, dword ptr [0xffffcfb8]         
0x007e2e9f: mov dword ptr [0xffffcf38], ecx         
0x00745a49: add eax, 0x454              
0x00745a4e: pushfd                  
0x00745a4f: pop dword ptr [0xffffcfbc]              
0x007964f4: mov ecx, dword ptr [0xffffcfbc]         
0x0079653f: mov dword ptr [0xffffcf40], ecx         
0x00697f01: mov edx, eax        
0x00697f09: mov ecx, eax        
0x00697f0d: not edx             
0x00697f11: not ecx             
0x00697f14: and edx, ecx        
0x00813a43: pushfd              
0x00813a4b: pop dword ptr [0xffffcfbc]              
0x00764298: mov ecx, dword ptr [0xffffcfbc]         
0x007bdb9e: mov dword ptr [0xffffcf18], ecx         
0x00716b65: mov ecx, 0x40               
0x0064c470: pushfd                  
0x00753bc8: mov esi, 0xffffcf14             
0x00753bca: mov edi, 0xffffcab0

DAG优化后的输出为

ds[0xffffcfe8] = ecx
ds[0xffffcf28] = ecx
ds[0xffffcf1c] = edx
ds[0xffffcf3c] = ebp
ds[0xffffcfd8] = 0x815 & eflags0_0
ds[0xffffcff4] = eflags1_128
ecx = 0xfffff7ea & eflags1_128
ds[0xffffcf14] = ecx + ds[0xffffcfd8]
ds[0xffffcf24] = ds[0xffffcf14]
ds[0xffffcf50] = 0x0
ds[0xffffcf20] = ebx
ds[0xffffcf44] = esi
ds[0xffffcf30] = edi
ds[0xffffcf34] = 0xffffcfd4
ds[0xffffcf4c] = fs[0x00000000]
ds[0xffffcf48] = eflags2_128
ds[0xffffcfb4] = eflags3_144
ds[0xffffcf2c] = eflags3_144
ds[0xffffcfb8] = eflags4_0
ds[0xffffcf38] = eflags4_0
eax = 0x348f
ds[0xffffcf40] = eflags5_0
edx = 0xffffcb70
ds[0xffffcf10] = eflags6_128
ds[0xffffcfbc] = eflags6_128
ds[0xffffcf18] = eflags6_128
ecx = 0x40
ds[0xffffcaa4] = eflags7_128
esi = 0xffffcf14
edi = 0xffffcab0

eflags7_128第一个数值7表示出现次数的编号,128为eflags寄存器的值。这里用到了一个化简规则:a = ~(~a | ~a),在化简前DAG的可视化如下:

蓝色圈就对应a = ~(~a | ~a)的运算,那么可以直接使用a对应的结点代替这个蓝色圈

如果觉得赋值语句还是多的话,也可以利用DAG删除无用赋值。DAG的优化只支持部分x86指令,大家可以根据自己需要自行增减,代码的实现部分在DAGoptimizer类

参考资料

《编译器设计之路》
《编译原理》(龙书)
《高级编译器设计与实现》(鲸书)
基于程序分析与测试的二进制软件漏洞挖掘技术研究
WEISER M.Program Slicing[J].IEEE Transactions on Software Engineering,1984,SE-10(4):352--357.

源码.part1.rar

2 MB, 下载次数: 20, 下载积分: 吾爱币 -1 CB

源码.part2.rar

1.32 MB, 下载次数: 17, 下载积分: 吾爱币 -1 CB

免费评分

参与人数 15吾爱币 +18 热心值 +13 收起 理由
笙若 + 1 + 1 谢谢@Thanks!
冷心#5201 + 1 + 1 用心讨论,共获提升!
李佑辰 + 1 + 1 我很赞同!
MorichikaRinno + 1 + 1 我很赞同!
舒默哦 + 1 + 1 谢谢@Thanks!
爱飞的猫 + 3 + 1 很帅
timeslover + 1 我很赞同!
fengbolee + 2 + 1 欢迎分析讨论交流,吾爱破解论坛有你更精彩!
baihs + 1 谢谢@Thanks!
victos + 1 + 1 谢谢@Thanks!
不爱everyone + 1 + 1 用心讨论,共获提升!
asryn + 1 + 1 感谢发布原创作品,吾爱破解论坛因你更精彩!
liyitong + 1 搁这儿发论文呢
fanvalen + 2 + 1 我很赞同!
name886 + 1 + 1 我很赞同!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

推荐
slzslz 发表于 2022-7-28 20:20
编译原理是天书 根据天书的原理写的,凡人很难理解
推荐
asryn 发表于 2022-7-28 11:12
沙发
MI20220721 发表于 2022-7-27 16:51
3#
飘零未忍 发表于 2022-7-27 17:51
感谢分享!
4#
sainoa 发表于 2022-7-27 17:57
感谢分享,学习了。
5#
waiguazy 发表于 2022-7-27 18:27
完全看不懂
6#
kone153 发表于 2022-7-27 20:08
感谢分享,学习了。
7#
klshuaige 发表于 2022-7-27 21:46
。。。。。。。。
8#
CHE1027 发表于 2022-7-27 22:03
一天一学
9#
GlenSafe 发表于 2022-7-27 22:07
谢谢分享,学(照)习(抄)一下
10#
shehuizhuyihao 发表于 2022-7-27 22:50
不明觉厉~~
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:本版块禁止灌水或回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2022-8-16 15:06

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表