obfuscation - 混淆理论和符号计算

Question

是否有任何文档或特定文本描述了生成功能等效但语义不同的计算机程序的理论基础？理想情况下，我正在寻找涵盖从离散指令派生符号指令的基础的文档，用于与KLEE相同的实际编程语言。

我也很好奇在确定两段代码是否共享等效连续执行状态的某个子集时是否存在复杂性的下限，即状态@指令指针和同时的全局变量、堆栈和堆值。

Answer 1

对于您的第一个问题，您可能对多态代码的研究感兴趣，这是您描述的功能的一个子集。

对于第二个问题：

确定两段代码在功能上是否等效与停止问题一样困难，这是一个众所周知的不可判定问题——没有计算机可以解决所有问题实例。

要看到这一点，请注意我们可以通过询问要测试的程序是否具有与非停止程序相同的功能来解决停止问题for(;;);。我们忽略了副作用，所以我们不在乎程序在此期间是否做了其他事情——我们只关心它是否最终完成。