为了更清楚地了解它,我们来看一个例子:让P为程序,t为保留P的指称语义的转换,将P修改为
P'= t(P)
,并将对P的抽象语义S的修改t'导出为
S'= t'(S)
现在我们将说,如果存在一些具有相应语义属性S的P的Prop属性,则t是有效的,这样:t不会保留SProp '。换句话说,即使通过静态分析,Prop也会丢失。我们还可以看到,这里我们考虑的是对抽象语义的修改,而不是对代码的修改。
代码转换(混淆器)t的强度由一组属性O(t)计算得出t未保留的值,即
t1
例如,我们可以想象,在1960年之前的某个时期,没人知道快速排序,每个人都知道bublesort。假设有人写了一个bublesort B,并且(有可能)写了一个将bublesort修改为quicksort Q的转换,因为没人知道这个奇怪的排序算法,那么他们会(理性地)说这是bublesort的混淆版本。但是,当我们在上面的语义框架上应用这种情况时,我们可以看到B和Q的抽象语义属性没有任何共同之处(即可比较的)。基于语义的代码混淆处理了上述情况?
#1 楼
实际上,冒泡排序和快速排序都具有非常重要的通用语义属性,即它们都对元素数组进行排序(在其上定义了总顺序关系)。当然,它们还具有其他属性,例如特定输入的平均复杂度和具体的执行轨迹,对于排序算法输入空间中的大多数输入而言,它们将有所不同。基于语义的代码模糊处理论文:采用排序程序P(可能是气泡排序)
将混淆处理t1应用于产生t1(P)的程序P (可能是快速排序)
在程序P上应用另一个混淆转换t2,该程序会生成t2(P)(可能是插入排序)
P的具体跟踪语义的近似与对t1(P)和t2(P)的具体跟踪语义具有相同的近似值。这3个程序的运行时。
转换t1混淆了\ alpha和\ beta,它们都是O(t1)的一部分,但仍然存在求出P和t(P)的排序的共同语义属性)。
因此,我们得出结论,变换t1比t2更有效,因为它隐藏了P的更多属性。