一类代码迷惑的反解复杂性.docVIP

一类代码迷惑的反解复杂性问题 摘要 @@证明了借助函数指针数组的混淆的反解复杂度是NP-Hard的。本文重点介绍该结论。 关键词 代码迷惑 复杂度 函数指针数组 §1借助函数指针数组的混淆技术简介 §1.1 函数指针在软件混淆中的使用 基于函数指针的混淆技术包含3个阶段： 1、函数的分解：首先我们随机挑选一个函数并把它分解为更小的函数，然后在保持原函数语义的情况下用这几个小函数重新构造原函数。 2、函数指针的使用：函数和随机选择的分解函数可以凭借函数指针调用。例如，图中2右侧的程序可以被转换为图3中的程序。两个新的if模块被引入了，这两个新的if模块的条件值恒为1，而源程序的语义被保留了。然而，静态分析很难评估这些模块从而很难确定在这些if模块存在下的可执行路径。所以，if模块使确定函数指针指向的函数地址变得困难了。 3、函数指针数组的引入：这里我们引入函数指针数组，然后把函数地址随机地存在数组中并做出表达式用一些（直接或非直接的）函数调用来计算每个索引。现在一些函数调用被替换为通过这种数组的调用。例如，图3的程序可以转换为图4的程序。现在对于fp的分配取决于凭借fp先前的值的函数调用和A的相关元素。它们一起有效地抵御了静态分析。 §1.2 增加不可实现路径的数量 跨函数分析很困难的原因之一就是它必须遵循可执行路径，基于这个事实，我们提出两种软件混淆技术来阻止跨函数分析： 1、合并多个函数调用为一个：这个技术把多个函数调用合并为一个新创建的函数，如图5所示，随机选取两个函数调用func1（）和func2（），函数func3（）是新创建的，最后两个调用以某个混淆的方式嵌入到了func3（）中。经过这样的混淆处理，调用图的变化如图6所示，转换后比转换前多了两个不可实现路径。如果跨函数分析忽略了不可实现路径，它只会失败或产生不精确的分析结果。即使跨函数分析努力地要遵循可实现路径也会非常困难。 2、加入大量的return模块：加入大量的return模块的混淆技术也可以使调用图变得复杂并且阻止跨函数分析，如图7所示，相应的调用图如图8所示。不难看出调用图变得更复杂了并且不可实现路径的数量从2个增加到4个。所以同理这个混淆技术也很有效。 §2 借助函数指针数组的混淆技术反解复杂度 定理1：在从具有函数指针或通过函数指针进行函数调用的数组中分配函数指针的情况下（函数返回整数），确定程序中是否存在可执行路径是NP困难的。 证明 我们通过证明3-SAT问题（NP完全的）在多项式时间内可归约为定理1的问题来证明定理1。 现在，假设给定3-SAT问题，定义值为true或false的变量，以及公式： 其中的值为或，，然后我们构造一个如图1的C程序，假设所有路径都是可执行的，所有if模块的条件部分没有影响，这样用标志“-”来代替所有if模块的条件。 在代码L1部分，被定义为函数指针并与3-SAT问题中的命题变量相关联。 L2分别把true和false赋给A[0]和A[1]。 在L3中的任意的经过if模块的可执行路径都与3-SAT问题的真假值指派相对应。所以如果3-SAT问题有答案，我们也就有相应的可执行路径，函数指针fp指向L5上的函数true。 而且，如果3-SAT问题没有答案，至少存在一个子句它的三个变元都是假的，在这种情况下，fp指向函数false。 另一方面，如果函数指针指向在一个可执行路径上的L5上的函数true，那么有相同真假赋值的3-SAT问题也有解。 根据上面陈述的理由，3-SAT问题有解当且仅当我们能确定是否有可执行路径，在这个路径上函数fp指向L5上的函数地址true。 第3节 我们的实验 为了验证定理1中的问题是否真是NP-HARD，我们将文章中未作任何处理的程序和经过混淆处理的程序分别运行并列出相应的汇编代码，然后进行比较。 §3.1 未作处理的程序代码 3: int a,b; 4: 5: if (a b)8B 45 FC mov eax,dword ptr [ebp-4] 0040102B 3B 45 F8 cmp eax,dword ptr [ebp-8] 0040102E 7E 06 jle main+26h 6: { 7: a = b;8B 4D F8 mov ecx,dword ptr [ebp-8]89 4D FC mov dword ptr [ebp-4],ecx 8