一种基于LLVM编译优化阶段的复杂控制流混淆方法

一种基于llvm编译优化阶段的复杂控制流混淆方法
技术领域
1.本发明涉及软件保护技术领域，尤其涉及一种基于llvm编译优化阶段的 复杂控制流混淆方法。


背景技术：

2.由于编程语句具有结构化特点，通常程序的控制流是可归约的，可以通过 控制流分析进行语义理解与程序代码反编译。近年来，程序控制流分析成为软 件分析的主流方法之一，已提出了基于符号执行、程序切片和形式化推理等的 程序控制流分析技术，大大提升了程序控制流分析的完整性和准确性。
3.但部分逆向工作者通过逆向工程对软件的控制流进行逆向分析，从而得知 软件中的重要信息，对软件核心算法剽窃复制、密钥窃取与破译等，给软件安 全带来巨大的威胁。


技术实现要素：

4.本发明的目的在于提供一种基于llvm编译优化阶段的复杂控制流混淆方 法，旨在解决软件的控制流易被进行逆向分析，导致软件安全性降低的问题。
5.为实现上述目的，本发明提供了一种基于llvm编译优化阶段的复杂控制 流混淆方法，包括以下步骤：
6.s1获取源码和与所述源码对应的编译参数；
7.s2将所述源码翻译为源表达式；
8.s3检查所述编译参数中是否有混淆参数，若没有混淆参数，则执行步骤s10， 若有混淆参数，则执行步骤s4；
9.s4使用混淆pass对所述源表达式进行混淆，得到混淆结果；
10.s5利用所述混淆结果基于二位混沌映射构造不透明谓词；
11.s6对所述不透明谓词进行强化分支路径构造的控制流不可规约化混淆，得 到变换结果；
12.s7循环步骤s4至s6，直至循环次数到达预设值，得到初步结果；
13.s8对所述初步结果进行控制流平展化混淆，得到最终结果；
14.s9对所述最终结果进行表达式替换，得到最终表达式；
15.s10使用优化层对所述中间表达式或所述最终表达式进行优化，得到对应的 优化参数。
16.其中，所述使用混淆pass对所述源表达式进行混淆，得到混淆结果的具体 方式为：
17.s41利用llvm编译器框架，遵循llvm pass编写标准，将所述混淆pass 的pass声明为控制流平展化混淆pass和强化路径分支变换pass，声明完成 后，将所述混淆pass自身注册，得到设计的混淆pass；
18.s42使用所述设计的混淆pass对源表达式进行混淆，得到混淆结果。
19.其中，所述利用所述混淆结果基于二位混沌映射构造不透明谓词的具体方 式为：
20.s51在所述混淆结果中选择随机基本块；
21.s52在所述随机基本块中选择目标基本块；
22.s53基于二位混沌映射在所述目标基本块前插入永真不透明谓词、永假不透 明谓词和可真可假不透明谓词。
23.其中，所述强化分支路径构造包括虚假路径指向前驱基本块的分支路径、 虚假路径指向后继的后继基本块的分支路径、虚假路径指向等效克隆基本块的 分支路径、虚假路径指向非等效克隆基本块的分支路径和虚假路径指向分裂基 本块的分支路径。
24.其中，所述对所述初步结果进行控制流平展化混淆，得到最终结果的具体 方式为：
25.s81构造冗余代码基本块集合；
26.s82构造调度控制基本块；
27.s83基于所述冗余代码基本块集合和所述调度控制基本块对所述初步结果 进行控制流平展化混淆，得到最终结果。
28.其中，所述对所述最终结果进行表达式替换，得到最终表达式的具体方式 为：
29.将所述最终结果中的二元运算替换为多元等价运算，得到最终表达式。
30.本发明的一种基于llvm编译优化阶段的复杂控制流混淆方法，通过获取 源码和与所述源码对应的编译参数；将所述源码翻译为源表达式；检查所述编 译参数中是否有混淆参数，若没有混淆参数，则进行优化，若有混淆参数，则 执行下一步；使用混淆pass对所述源表达式进行混淆，得到混淆结果；利用所 述混淆结果基于二位混沌映射构造不透明谓词；对所述不透明谓词进行强化分 支路径构造的控制流不可规约化混淆，得到变换结果；循环混淆步骤，直至循 环次数到达预设值，得到初步结果；对所述初步结果进行控制流平展化混淆， 得到最终结果；对所述最终结果进行表达式替换，得到最终表达式；使用优化 层对所述中间表达式或所述最终表达式进行优化，得到对应的优化参数，本发 明通过对源代码进行控制流混淆后优化，解决了软件的控制流易被进行逆向分 析，导致软件安全性降低的问题。
附图说明
31.为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施 例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述 中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付 出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
32.图1是本发明提供的一种基于llvm编译优化阶段的复杂控制流混淆方法 的流程图。
33.图2是本发明提供的一种基于llvm编译优化阶段的复杂控制流混淆方法 的线性图。
34.图3是插入冗余代码基本块的示意图。
35.图4是构造不透明谓词的示意图。
36.图5是强化分支路径构造的示意图。
37.图6是环路骨架的示意图。
具体实施方式
38.下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自 始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。 下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理 解为对本发明的限制。
39.请参阅图1至图6，本发明提供一种基于llvm编译优化阶段的复杂控制 流混淆方法，包括以下步骤：
40.s1获取源码和与所述源码对应的编译参数；
41.具体的，通过前端获取源码和与所述源码对应的编译参数。
42.s2将所述源码翻译为源表达式；
43.具体的，通过前端将所述源码翻译为源表达式，所述源表达式为llvm ir。
44.s3检查所述编译参数中是否有混淆参数，若没有混淆参数，则执行步骤s10， 若有混淆参数，则执行步骤s4；
45.具体的，llvm opt接收到前端传入参数后，调用优化器pass来对llvmir进行操作。所述混淆参数可以指定混淆的基本块选取频率及混淆轮数，若未 指定，则使用默认的频率及轮数。
46.s4使用混淆pass对所述源表达式进行混淆，得到混淆结果；
47.具体方式为：
48.s41利用llvm编译器框架，遵循llvm pass编写标准，将所述混淆pass 的pass声明为控制流平展化混淆pass和强化路径分支变换pass，声明完成 后，将所述混淆pass自身注册，得到设计的混淆pass；
49.具体的，混淆操作是在llvm编译器框架下完成的，需要遵循llvm pass 编写标准。每一个pass都需要声明自身为pass才能被编译器框架的优化器识别 为pass，然后将自身注册，才能被优化器使用。其中，我们需要在匿名空间中 给出pass的id，入口函数，参数标记信息。
50.声明加密调度变量且随机执行的控制流平展化混淆pass，编写入口函数， 注册pass,声明参数fla。有一个可选的参数fla_prob，用来表示冗余基本块构造 的比率，设置其默认值为30。
51.声明基于二维混沌映射构造不透明谓词的强化路径分支变换pass，编写入 口函数，注册pass,声明参数bcf。有两个混淆参数：混淆几率bcf_rate，默认值 为30；混淆轮数bcf_loop，默认值为1。
52.s42使用所述设计的混淆pass对源表达式进行混淆，得到混淆结果。
53.s5利用所述混淆结果基于二位混沌映射构造不透明谓词；
54.具体的，基于二维混沌映射构造不透明谓词：
55.arnold cat二维混沌映射表达式为：x0,y0∈q
+
,n∈ n
+
,
当a取时，称其为arnold cat映射，该表达式在x0,y0∈(0,1)范 围内构造的实数序列具有混沌特征。构造三元组(a,x0,y0)作为二维混沌表达式 输入，混淆函数中取随机(a,b)，a取构造arnold cat映射，图3 所示，
56.取第n轮映射则构造一个永真不透明谓 词p
t
；
57.取第n轮映射构造的谓词是一个永假不 透明谓词pf；
58.取rand
x
＝x
n-1
±
δ,randy＝y
n-1
±
δ,δ
→
0，由于 浮点运算在计算机中存在精度损失，当δ取较小值时，计算结果不定，构造的谓 词是一个真假不定不透明谓词pr。
59.所述利用所述混淆结果基于二位混沌映射构造不透明谓词的具体方式为：
60.s51在所述混淆结果中选择随机基本块；
61.s52在所述随机基本块中选择目标基本块；
62.s53基于二位混沌映射在所述目标基本块前插入永真不透明谓词、永假不透 明谓词和可真可假不透明谓词。
63.具体的，不透明谓词的构造使用二维混沌映射，表达式为：具体的，不透明谓词的构造使用二维混沌映射，表达式为：构造三元组(a,x0,y0)作为二维混沌表达式输入，a取固定的 构造arnold cat映射。设置变量元组(n,x0,y0)为混淆函数调用时生成的 随机数，
64.取第n轮映射则构造一个永真不透明谓 词p
t
；
65.取第n轮映射构造的谓词是一个永假不 透明谓词pf；
66.取rand
x
＝x
n-1
±
δ,randy＝y
n-1
±
δ,δ
→
0，构造 的谓词是一个真假不定不透明谓词pr。
67.s6对所述不透明谓词进行强化分支路径构造的控制流不可规约化混淆，得 到变换结果；
68.具体的，如图5所示，所述强化分支路径构造包括图5.a虚假路径指向前 驱基本块的分支路径、图5.b虚假路径指向后继的后继基本块的分支路径、图 5.c虚假路径指向等效
克隆基本块的分支路径、图5.d虚假路径指向非等效克隆 基本块的分支路径和图5.e虚假路径指向分裂基本块的分支路径。通过随机多轮 插入分支路径，提高控制流图复杂度。
69.对于虚假路径会执行到构造基本块，构造基本块的后继是被混淆基本块的 后继。其中构造基本块的后继有：
70.6.1构造基本块为空；
71.6.2构造基本块为被混淆基本块的等效克隆，在该构造基本块中随机添加无 关指令，同时对表达式中的算数运算、逻辑运算进行等效替换；
72.6.3构造基本块为被混淆基本块的非等效克隆，在该构造基本块中随机删除 部分指令，同时对表达式中的算数运算、逻辑运算进行随机替换；
73.6.4构造基本块为被混淆基本块的分裂部分，将被混淆基本块等分为两部分 sub1和sub2，sub1和sub2都为构造基本块。
74.检查被混淆基本块混淆后控制流的不可规约性，即局部控制流是否满足以 下条件：若|{b|a∈v-v'∧b∈v'∧《a,b》∈e-e'}|》 2，且均有e1d。
75.若不满足，则s6添加不透明谓词，然后使用6.1、6.5构造强化分支路径。
76.通过对控制流图进行不可规约化混淆，记控制流图g＝《v,e》,其中v代表结 点集,e代表边集，通过插入不透明谓词由强化分支路径随机组合，构造的局部 控制流图满足以下条件：若|{b|a∈v-v'∧b∈v'∧ 《a,b》∈e-e'}|》2，且均有e1d。则构造了不可规约化混淆的控制流。
77.混淆强度分析：设该阶段混淆五种分支路径构造几率分别为混淆强度分析：设该阶段混淆五种分支路径构造几率分别为三种不透明谓词构造几率相同为混淆基本块选 择几率为ps,原始基本块集合b＝{b
x
|x∈[0,n),x∈z,b
x
∈g}，原始基本块边的 数量为e,指令总数为co，构造m个冗余代码基本块的集合br＝ {b
r,x
|x∈[0,m),x∈z},m＝n*ps，其中等效基本块集合b
re
，非等效基本块集合 b
rn
,br＝{b
re
,b
rn
}，br中各冗余代码基本块指令数量为c
r,i
,0《i《m，不透 明谓词指令数量为c
l
,其中随机不透明谓词近似量取δ。
[0078]
控制流圈复杂度记为v(g)＝e-n+2,则混淆后圈复杂度增加率
[0079]
平均有效指令执行率为：
[0080]
该阶段混淆后控制流不可规约，设该阶段混淆轮数为α，原始控制流最大 循环嵌套深度为β，则该阶段α轮混淆后，理论最大循环嵌套深度为：η
max
＝ α+β。
[0081]
s7循环步骤s4至s6，直至循环次数到达预设值，得到初步结果；
[0082]
具体的，所述预设值为混淆轮数要求。每轮混淆完成后检查是否打成混淆 轮数要求，若满足要求执行s8，若不满足要求执行s4。
[0083]
s8对所述初步结果进行控制流平展化混淆，得到最终结果；
[0084]
具体的，控制流平展化混淆为加密调度变量且随机执行的控制流平展化混 淆：
[0085]
控制流平展化直观的表示为在控制流层面将多层关系的基本块节点，通过 改变基本块跳转关系，把这些基本块放置在控制流中的同一个层次中，并以调 度变量引导其基本块执行。传统的控制流平展化由于其具有明显的规律性既“主 分发器-代码块-预分发器”，可以通过动态调试、符号执行、模拟程序运行等方 法获取到真实代码块执行逻辑以还原程序控制流。而本方案中提出的加密调度 变量且随机执行的控制流平展化混淆如图1所示，主要做了以下工作：1).构造 随即执行的冗余代码基本块；2).构造随机调度变量；3).跳转地址动态解密。
[0086]
构造m个冗余代码基本块b'
x
的集合b':{b'
x
|x∈[0,m-1]}，构造的冗余代 码不影响正常程序的逻辑功能。
[0087]
在控制流平展化时，假设原始基本块数量为n，原始控制流图g中，基本 块b
x
的集合b:{b
x
|x∈[0,n-1],b
x
∈g}，任意基本块b
x
∈b有标签值作为调 度变量调度目的标识，被初始化为随机值被初始化为随机值调度控制基本块的标签值初始化为tc，然后构造所有原始基本 块跳转地址基本块跳转前执行状态转前执行状态为b
x
的后继基本块的标签值。
[0088]
设定阈值p,(0《p《1),调度控制基本块通过生成随机数c,c(0《c《1)， 若c《p，则不执行冗余代码，解密跳转地址jmp＝d(st,key)，程序跳转到正 常执行的基本块；若c》p，取随机冗余代码基本块b'r,b'r∈b'，其标签值为则程序跳转到冗余代码基本块执行。
[0089]
混淆强度分析：设该阶段混淆构造m个冗余代码基本块集合br＝{b
r,x
|x∈ [0,m),x∈z}，各冗余代码基本块指令数量为c
r,i
,0《i《m，边的数量为e,原始 基本块集合b＝{b
x
|x∈[0,n),x∈z,b
x
∈g}，原始基本块指令总数为co，环路指 令数量为c
l
,执行冗余代码块的阈值p,(0《p《1),
[0090]
则冗余代码执行几率为:p(br)＝1-p
[0091]
控制流圈复杂度记为v(g)＝e-n+2,则混淆后圈复杂度增加率
[0092]
平均有效指令执行率为：
[0093]
所述对所述初步结果进行控制流平展化混淆，得到最终结果的具体方式为：
[0094]
s81构造冗余代码基本块集合；
[0095]
具体的，构造m个冗余代码基本块集合br＝{b
r,x
|x∈[0,m-1]}，构造冗 余代码不影响正常程序的逻辑功能。
[0096]
s82构造调度控制基本块；
[0097]
s83基于所述冗余代码基本块集合对和所述调度控制基本块所述初步结果 进行控制流平展化混淆，得到最终结果。
[0098]
具体的，在控制流平展化时，假设原始基本块数量为n，各原始基本块b
x
：{b
x
|x∈[0,n-1],b
x
∈g}的调度变量b
x,t
被初始化为随机值b
x,t
＝ rand,(0x0≤rand≤0xffffffff)，调度控制基本块的标签值初始化为bc，然 后构造原始基本块跳转地址为b
x,j
＝bc，计算基本块跳转前执行状态st＝ e(b
next,t
,key)。
[0099]
设定阈值p,(0《p《1),调度控制基本块通过生成随机数c,c(0《c《1)， 若c《p，则不执行冗余代码，解密跳转地址jmp＝d(st,key)，程序跳转到正 常执行的基本块；若c》p，则jmp＝d(b
r,r,t
,key)，r∈[0,m-1]，程序跳转 到冗余代码基本块执行。
[0100]
创建环路骨架，环路骨架既switch结构的主体框架，如图6所示，环路骨 架包括环路的入口、出口，将第一个基本块置顶，将loopentry放在其后。将 loopend指向loopentry。将switch default指向loopend。
[0101]
将所有基本块添加到switch骨架中。
[0102]
s9对所述最终结果进行表达式替换，得到最终表达式；
[0103]
具体的，将所述最终结果中的二元运算替换为多元等价运算，得到最终表 达式。
[0104]
s10使用优化层对所述中间表达式或所述最终表达式进行优化，得到对应的 优化参数。
[0105]
具体的，ir控制权交给llvm，完成ir到机器码的工作。最终输出为复杂 控制流混淆后的可执行代码。
[0106]
有益效果：
[0107]
1.解决传统控制流平坦化混淆中，易于通过静态分析、模拟执行或动态调 试跟踪调度变量，还原原始程序控制流。本方案中加密调度变量且随机执行的 控制流平展化混淆可以有效对抗静态分析控制流分析，且模拟执行或动态调试 无法恢复为可理解语义的代码；
[0108]
2.基于二维混沌映射构造不透明谓词，arnold cat二维混沌映射其产生的实 数序列具有对初始参数的依赖性、伪随机性以及真值有限性,因此,以该映射为 基础所构造的不透明谓词具有很高的安全性能。
[0109]
3.强化分支路径构造的控制流不可规约化混淆生成的控制流图具有不可规 约化，高随机性的特点有很强的混淆强度与弹性，同时谓词表达式基于二维混 沌映射构造，且虚假路径存在等价克隆与非等价克隆的冗余代码，该混淆具有 较强隐蔽性。
[0110]
以上所揭露的仅为本发明一种基于llvm编译优化阶段的复杂控制流混淆 方法较佳实施例而已，当然不能以此来限定本发明之权利范围，本领域普通技 术人员可以理解实现上述实施例的全部或部分流程，并依本发明权利要求所作 的等同变化，仍属于发明所涵盖的范围。

技术特征：
1.一种基于llvm编译优化阶段的复杂控制流混淆方法，其特征在于，包括以下步骤：s1获取源码和与所述源码对应的编译参数；s2将所述源码翻译为源表达式；s3检查所述编译参数中是否有混淆参数，若没有混淆参数，则执行步骤s10，若有混淆参数，则执行步骤s4；s4使用混淆pass对所述源表达式进行混淆，得到混淆结果；s5利用所述混淆结果基于二位混沌映射构造不透明谓词；s6对所述不透明谓词进行强化分支路径构造的控制流不可规约化混淆，得到变换结果；s7循环步骤s4至s6，直至循环次数到达预设值，得到初步结果；s8对所述初步结果进行控制流平展化混淆，得到最终结果；s9对所述最终结果进行表达式替换，得到最终表达式；s10使用优化层对所述中间表达式或所述最终表达式进行优化，得到对应的优化参数。2.如权利要求1所述的基于llvm编译优化阶段的复杂控制流混淆方法，其特征在于，所述使用混淆pass对所述源表达式进行混淆，得到混淆结果的具体方式为：s41利用llvm编译器框架，遵循llvm pass编写标准，将所述混淆pass的pass声明为控制流平展化混淆pass和强化路径分支变换pass，声明完成后，将所述混淆pass自身注册，得到设计的混淆pass；s42使用所述设计的混淆pass对源表达式进行混淆，得到混淆结果。3.如权利要求2所述的基于llvm编译优化阶段的复杂控制流混淆方法，其特征在于，所述利用所述混淆结果基于二位混沌映射构造不透明谓词的具体方式为：s51在所述混淆结果中选择随机基本块；s52在所述随机基本块中选择目标基本块；s53基于二位混沌映射在所述目标基本块前插入永真不透明谓词、永假不透明谓词和可真可假不透明谓词。4.如权利要求3所述的基于llvm编译优化阶段的复杂控制流混淆方法，其特征在于，所述强化分支路径构造包括虚假路径指向前驱基本块的分支路径、虚假路径指向后继的后继基本块的分支路径、虚假路径指向等效克隆基本块的分支路径、虚假路径指向非等效克隆基本块的分支路径和虚假路径指向分裂基本块的分支路径。5.如权利要求4所述的基于llvm编译优化阶段的复杂控制流混淆方法，其特征在于，所述对所述初步结果进行控制流平展化混淆，得到最终结果的具体方式为：s81构造冗余代码基本块集合；s82构造调度控制基本块；s83基于所述冗余代码基本块集合和所述调度控制基本块对所述初步结果进行控制流平展化混淆，得到最终结果。6.如权利要求5所述的基于llvm编译优化阶段的复杂控制流混淆方法，其特征在于，所述对所述最终结果进行表达式替换，得到最终表达式的具体方式为：将所述最终结果中的二元运算替换为多元等价运算，得到最终表达式。

技术总结
本发明涉及软件保护技术领域，具体涉及一种基于LLVM编译优化阶段的复杂控制流混淆方法，包括获取源码和与源码对应的编译参数；将源码翻译为源表达式；检查编译参数中是否有混淆参数，若没有混淆参数，则进行优化，若有混淆参数，则使用混淆PASS对源表达式进行混淆后基于二位混沌映射构造不透明谓词；对不透明谓词进行强化分支路径构造的控制流不可规约化混淆，得到变换结果；循环混淆步骤，直至循环次数到达预设值，得到初步结果；对初步结果进行控制流平展化混淆，得到最终结果；对最终结果进行表达式替换，得到最终表达式；使用优化层对中间表达式或最终表达式进行优化，得到对应的优化参数。优化参数。优化参数。


技术研发人员：丁勇 刘德华 李振宇 杨炳年
受保护的技术使用者：桂林电子科技大学
技术研发日：2022.07.18
技术公布日：2022/12/5