ADD / XOR / ROL

一个关于逆向工程、数学、政治、经济学等主题的博客…

2018年10月2日，星期二

图灵完备性、怪异机器、Twitter与混淆的术语

首先向读者致歉：我通常会在博客文章的可读性/润色上花些功夫，但目前时间紧张，因此以下内容的写作标准会比平时低一些。

我在Twitter上发了一条推文，称学术漏洞利用论文中使用“图灵完备性”一词是错误的，随后引发了一场讨论。在那场讨论中，暴露出更多术语上的误解。在Twitter上纠正这些内容行不通（我多么怀念有用的邮件列表时代），所以我最终写了一篇短文。Pastebin也不适合存档帖子，由于没有更好的地方放置，就放在这里了：

我们对“图灵完备性”和“怪异机器”的误用是有害且令人困惑的

1. “图灵完备性”

TC（图灵完备性）指的是可计算性（在模拟其他计算机的意义上），并且在那里有明确的定义。它意味着“可以模拟任何图灵机”。关于TC，有几点需要记住：

• 在没有I/O的情况下，我们日常使用的机器都不是TC。TC需要无限内存。
• TC出现得非常快；你只需要一条指令，该指令执行减法并在不为零时执行条件分支。它也会在相当小的递归方程中随机出现（参见生命游戏是图灵完备的事实）。

对于漏洞利用的情况，理想的结果是“我们获得了整数运算和任意读写能力”。图灵完备性对可利用性没有任何说明，因为可利用性与计算关系不大，而更多地与“给定与目标的可能交互，哪些状态是可达到的”有关。这是两个非常不同的问题。

字体渲染器是图灵完备的，Javascript也是，考虑到如果存在I/O，部分计算实际上可能在攻击者端进行，IMAP也是如此。

这完全是对术语的误用。即使是首次使用该术语的论文也只是用来说“我们目测了得到的指令，它们看起来可能能够做我们想做的所有事情”：

我们描述的gadget集合通过检查是图灵完备的，因此面向返回的程序可以做x86代码可能做的任何事情。

让我们不要滥用一个精确定义的术语来表示其他东西，仅仅因为说“TC”让我们感觉像是在做真正的计算机科学。

漏洞利用更多地是关于可达状态（和转换），而不是关于可计算性。

2. “怪异机器”

怪异机器是最被悲剧性误解的抽象之一（如果人们正确理解它，将极大地帮助推理漏洞利用）。

怪异机器研究的重点不是展示一切都是图灵完备的。怪异机器研究的重点是，当任何有限状态自动机被模拟，并且该模拟被破坏时，会出现一台新机器，拥有自己的指令集。攻击中编程的就是这个指令集。限制怪异机器的状态转换（从而限制可达状态）是使漏洞利用不可能的原因。计算能力（在TC意义上）是次要的。

本可以拯救我们所有人免于阅读25篇针锋相对的ROP和糟糕缓解措施论文的关键见解是：如果你不限制内存损坏时出现的怪异机器能做什么，你的缓解措施可能不会有帮助。大多数缓解措施黑名单特定的怪异机器程序，而不限制机器的能力。

怪异机器是推理几乎所有非基于侧信道或缺失身份验证的漏洞利用的合适框架。

不幸的是，这个抽象被一些做过大量漏洞利用的人直观地很好理解，但没有被精确化或书面化。因此，其他研究人员听到了这个术语，并“用他们的想象力填充了它”：然后他们在任何地方使用这个术语，只要他们通过按设计使用随机事物发现了令人惊讶的计算方法。这使得这个术语更难理解——就像没有人能够仅仅通过阅读ROP论文来理解“图灵完备”一样。

我对这部分特别有热情，因为我花了几个月时间将非正式定义的怪异机器建立在坚实的基础上，并写入精确的定义，以防止这个术语变得更加混乱 :-)

总结：

• 在ROP论文中使用“图灵完备性”是一种滥用；该术语的使用与理论计算机科学中的使用不符。如果我们要使用严格的术语，我们应该确保正确使用它们。我现在经常看到学生和研究人员对实际含义感到困惑。
• 如果人们在正确的抽象层次（怪异机器）上推理ROP事物，本可以避免针锋相对的ROP缓解措施论文泛滥（以及随后对CFI的不健康关注）。他们本有机会，因为针锋相对论文的作者和正确理解事物的人之间进行了相当多的对话 :-)，但我怀疑没有动力在一个抽象层次上推理，这会干扰你切片更多论文的能力。
• 理解怪异机器概念变得更加困难，因为那些没有正确理解怪异机器的人开始将所有看起来 vaguely 有趣的东西称为“怪异机器”。没有人坐在任何审查委员会阻止他们 :-)，所以现在那个术语（也有精确定义）也被错误地使用了。

我的更大观点是：我们在这个领域的论文中有太多 handwavy 和混淆的术语，这对年轻研究人员、其他领域和博士生是有害的。术语令人困惑，通常定义不清（什么是gadget？），在一般CS中有精确含义的术语被用来表示完全不同的东西，而没有人解释它（图灵完备）。

这造成了不必要且有害的混乱，应该被纠正。

发布者：halvar.flake

时间：晚上11:25

无评论：

发表评论

较新的帖子 较旧的帖子 首页

订阅：帖子评论 (Atom)

博客归档 （此处省略归档列表）

关于我 halvar.flake 查看我的完整个人资料

链接 Off Convex

由Blogger提供支持。