4.窥孔优化(以除法还原示例)
窥孔优化是反编译器一个很重要的还原技术。而且这个技术没有捷径可言，大部分情况，都需要特定规则的集合。
这一章将以最经典的”整数除法“为例，展示编译器和反编译器的对于整数除法的优化与还原技术。
编译器对乘法与除法优化：
对于很多算数表达式，为了提升效率编译器会进行等价的替换。
典型案例之一就是使用左移替代2的倍数的乘法：
//源码示例，这里a为无符号整数
a = a * 4
//编译器优化后
a = a << 2这一优化就是”窥孔优化“的一种，因为在现代CPU中除法和乘法运算是十分昂贵的，尤其是除法（据说以前除法比加法慢50倍以上，比乘法慢10倍以上，直到Intel的Cannon Lake架构出现，Cannon Lake将64位整数除法的最大延时从96个周期降为了18个周期。这样除法就只比加法慢20倍，比乘法慢5倍）
实际的情况比想象中更加的复杂，单说加减乘除就有各种优化方法，下面是几个常见的典型除法类的优化示例：
无符号除法优化 https://godbolt.org/z/acm19_div3
//除法优化示例，这里edi为无符号整数
edi = edi / 3
//优化后编译成汇编 即 edi = (edi * 0xaaaaaaab) >> 33
mov eax, edi ; eax = edi
mov edi, 2863311531 ; edi = 0xaaaaaaab
imul rax, rdi ; rax = rax * 0xaaaaaaab
shr rax, 33 ; rax >>= 332.有符号除法优化
//除法优化示例，这里edi为有符号整数
edi = edi / 2;
//优化后编译成汇编 即 edi = (edi + (edi >> 33)) >> 1
//其中所有的右移都为有符号右移
mov eax, edi ; eax = edi
shr eax, 31 ; eax = eax >> 31
add eax, edi ; eax = eax + edi
sar eax ; eax = eax >> 13.无符号取余优化
//取余优化示例，这里edi为无符号整数
edi % 3 == 0
//优化后编译成汇编
imul edi, edi, -1431655765 ; edi = edi * 0xaaaaaaab
cmp edi, 1431655765 ; compare with 0x55555555
setbe al ; return 1 if edi <= 0x55555555
在GCC中，有专门的规则实现这一类优化，叫做match.pd的文件专门描述这一类优化。他是一种类LISP规则语言，反正我是看不懂，可以看上面的注释，看看具体实现了哪种优化。
反编译器的反窥孔优化：
为了将优化后的算式“反向优化”为人类可理解的算法，反编译器和编译器一样，都有这一类的匹配规则，称之为“反窥孔优化”。但是，编译器的窥孔优化不一定是绝对能还原的，所以
我这里以Ghidra为例（IDA不开源，有空再研究这玩意咋实现），Ghidra提供了一些列的规则处理这种特殊情况
https://www.lockshaw.io/static/ghidra/decompiler/doc/classRule.html#details
其中的除法优化示例：RuleDivOpt 类，他会将优化后乘法+右移的功能反编译成除法
公式为：
sub( (zext(V)*c)>>n, 0) => V / (2^n/(c-1))sub( (sext(V)*c)s>>n, 0) => V s/ (2^n/(c-1))
看上面这个公式不太直观。还是举个例子后模拟ghidra的运算方法
# 源码
unsigned divideByFive(unsigned x)
{
return x / 5;
}
# 编译器优化后的汇编实现
mov eax, edi
mov edi, 3435973837
imul rax, rdi
shr rax, 34
参考汇编，代入公式 ( 2^n / (c-1) ) 其中 n=34, c=3435973837
Python 3.10.6
>>> n=34
>>> c=3435973837
>>> ( 2**n // (c-1) )
5换成整数，约为5，因此可以反编译优化为 x / 5
反窥孔优化简单汇总
下面简单汇总了一些反窥孔优化的项目，都是从ghidra抄的
其中 V、W、X代表变量
c、d代表常量
-V => V * -1
V + -W ==> V - W
((V + c) + d) => V + (c+d)
((V * c) * d) => V * (c*d)
((V + (W + c)) + d) => (W + (c+d)) + V
V + 0xff... => V - 0x00...
(V << W) & d => (V & (W >> c)) << c
(V & c) & d => V & (c & d)
(V >> X) | (W >> X) => (V | W) >> X
!!V => V
!(V == W) => V != W
!(V < W) => W <= V
!(V <= W) => W < V
!(V != W) => V == W
V ^^ W => V != W
V * c + V * d => V * (c + d)
sub( (zext(V)*c)>>n, 0) => V / (2^n/(c-1))
sub( (sext(V)*c)s>>n, 0) => V s/ (2^n/(c-1))
sub(ext(V)*c,b)>>d + V -> sub( (ext(V)*(c+2^n))>>n,0)
W+((V-W)>>1) =>sub( (zext(V)*(c+2^n))>>(n+1), 0)
(V << c) << d => V << (c+d)
(V << c) >> c => V & 0xff
sub( concat(V,W), 0) => W
sub( concat(V,W), c) => V
sub( concat(V,W), c) => sub(V,c)
V * -1 == c => V == -c
V + c == d => V == (d-c)
~V == c => V == ~c
((V + c) + W) & 0xfff0 => (V + (c & 0xfff0)) + W对抗：不透明谓词混淆
ref:https://www.zhihu.com/question/46259412
ref:https://bbs.kanxue.com/thread-270019.htm
不透明谓词是一套很有趣且实用的静态反编译对抗技术。
它和窥孔优化很像，只不过是反向。窥孔优化从复杂到简单，它从简单到复杂。
通过添加反编译器无法计算的条件进行混淆。
todo：介绍对抗不透明谓词的反编译技术
reference
https://medium.com/@prathamesh1615/adding-peephole-optimization-to-gcc-89c329dd27b3
https://fuzhe1989.github.io/2020/01/22/optimizations-in-cpp-compilers/
https://www.computer.org/csdl/proceedings-article/arith/2005/23660131/12OmNyQYt7U
Last updated