基于语义的混淆

逆向工程 混淆
2021-07-06 11:28:31

我有一些(像往常一样非常模糊)关于语义混淆的思考,这来自这个问题以及@RolfRolles 和@Andrew 的出色回答。据我了解,在作者的观点。本文对基于语义的代码混淆是研究的混淆程序的语义端,而不是语法端这意味着,对程序代码的修改可能导致对抽象语义的修改,这里的抽象语义不是指称语义,而是程序的抽象表示,从抽象解释程序接收到的——作为系统静态——分析方法。

为了更清楚,我们考虑一个例子:让 P 是一个程序,t 是一个保留 P 的指称语义的变换,它将 P 修改为

P' = t(P)

并将 P 的抽象语义 S 上的修改 t' 导出为

S' = t'(S)

现在我们将说 t 是有效的,如果 P 的某些属性 Prop 与 S 的相应语义属性 SProp 相同,则: SProp 不被 t' 保留。换句话说,即使通过静态分析,Prop 也会丢失。我们也可以看到,这里我们考虑的是对抽象语义的修改,而不是对代码的修改。

代码转换(混淆器)t的强度由t未保留的属性集O(t)计算,即

t1 < t2 仅当 O(t1) 属于 O(t2)

但是(据我所知)隐含地假设 O(t1) 和 O(t2) 是可比的,我不是说 O(t1) 和 O(t2) 不属于彼此的情况,而是O(t1) 和 O(t2) 的每个元素在理性意义上不可比的情况。

例如,我们可以想象在 1960 年之前的某个时期,没有人知道快速排序,而每个人都知道布尔排序。假设有人写了一个 bublesort B 和(偶然地)一个将 bublesort 修改为快速排序 Q 的转换,因为没有人知道这种奇怪的排序算法,那么他们会(理性地)说它是一个模糊版本的 bublesort。然而,当我们将这种情况应用于上述语义框架时,我们可以看到 B 和 Q 的抽象语义属性没有任何共同点(即可比性)。

所以我的问题是:基于语义的代码混淆如何处理上述情况?

1个回答

实际上,冒泡排序和快速排序都有一个非常重要的共同语义属性,即它们都对元素数组进行排序(定义了全序关系)。当然,它们还具有其他属性,例如特定输入的平均复杂度和具体的执行轨迹,对于排序算法的输入空间中的大多数输入而言,这些属性会有所不同。

类似于基于语义的代码混淆论文的第 3.1 节:

  • 拿一个排序程序 P(无论是冒泡排序)
  • 对产生 t1(P) 的程序 P 应用混淆转换 t1(无论是快速排序)
  • 对产生 t2(P) 的程序 P 应用另一个混淆转换 t2(无论是插入排序)
  • P 的具体轨迹语义的近似与 t1(P) 和 t2(P) 的具体轨迹语义的近似不同
  • 定义一个属性\alpha,它观察程序轨迹的长度
  • 定义另一个属性 \beta,它观察 3 个程序的平均运行时间。
  • 变换 t1 混淆了 \alpha 和 \beta,它们都是 O(t1) 的一部分,同时仍然保留了对 P 和 t(P) 进行排序的共同语义属性
  • 转换 t2 只混淆了 α,而 β 则不是,因为 P 和 t2(P) 的平均运行时复杂度相同。

因此,我们得出结论,转换 t1 比 t2 更有效,因为它隐藏了 P 的更多属性。