基于LLVM的遗传编程代码变异？

Question

为了研究遗传编程，我想基于LLVM实现一个进化系统并应用代码突变（可能在IR级别上）。

我找到了llvm-mutate，它非常有用来执行点突变。据我所知，指令被计数/编号，然后可以删除一个编号的指令。

然而，引入新指令似乎是可行的，因为代码中有一个可用语句。真正的变异可以允许插入任何允许的IR指令，而不管它是否在要突变的代码中使用。此外，应该可以插入链接库的库函数调用（未在当前代码中使用，但可能可用，因为lib已在clang中链接）。

我是否在llvm-mutate中忽略了这一点，还是迄今为止确实不可能？

是否有任何项目正在尝试/已经实施了这样的llvm突变？ llvm有很多代码分析工具，应该允许实现上述方法。llvm很大，所以我有些迷茫。有哪些工具可能有帮助（例如获取可用库函数列表等）？

谢谢 Alex

- alex

Answer 1

非常有趣的问题。我一直被进行二进制级遗传编程的可能性所吸引。关于您的问题：

从他们的文档中可以看出，LLVM-mutate不能做到您所要求的。然而，我认为不这样做是明智的。我的理由是，任何机器语言遗传程序都不可避免地面临"停机问题",例如，无法知道随机生成的指令是否会完全崩溃整个计算机（例如通过向操作系统保留指针分配值），或者它可能永远运行并占用所有CPU周期。图灵的定理告诉我们，事先无法知道给定程序是否会这样做。请注意，LLVM-mutate可能会导致一个完全无害的程序仍然崩溃或永远运行，但我认为他们的方法通过只采取现有指令使得这种情况更不可能发生。

然而，“不可能”只能阻止科学家，而不能阻止工程师 :-)...

我一直在思考的是：在自然界中，真正的突变更像LLVM-mutate，而不是我们在普通遗传编程中所做的那样。换句话说，它们只是从一个非常有限的字符集（A、T、C、G）中交换字母，每个可能的变异都是由此产生的。我们可以有一个程序或一组程序，其中包含一组初始指令，以及一组“可能的函数”，这些函数可以链接或定义在程序中。大多数这些函数实际上都不会被使用，但它们将提供“原始DNA”用于突变，就像我们的DNA一样。这组函数将具有问题空间的完整（或半完整）的可能函数集。然后，我们只需使用类似于LLVM-mutate中的基本操作即可。

一些可能存在的问题：

• 考虑到可能的变异量，要想获得可接受的执行时间，唯一的方法就是拥有大量的计算能力。这可能可以在云端或使用GPU实现。

• 你仍然需要解决图灵停机问题。然而，我认为可以通过在“沙盒”中运行解决方案来解决这个问题，如果解决方案崩溃，不会影响整个系统：类似于一次性虚拟机或Docker容器，并设置时间限制（以避免无限循环）。崩溃或超时的解决方案将获得最差的适应度，以便程序会趋向于远离这些路径。

至于为什么要这样做，我可以看到许多有趣的应用：自我修复程序、针对特定环境进行自我优化的程序、针对漏洞的“疫苗”程序、突变病毒、质量保证等。

我认为这里有一个潜在的开源项目。这将是一个疯狂、危险和耗时的漩涡：正是我喜欢的项目。如果有人做这个项目，我愿意参与。

- Milton Hernandez

---

你最终尝试了吗？据我所知，没有人尝试过。我找到了slash/A，它是一种基于非AST的遗传编程的不同方法。 - Erik Garrison