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 有趣的东西都称为"怪异机器"。没有人坐在任何审查委员会阻止他们 :-)，所以现在那个术语（也有明确定义）也被错误地使用了。
我的更大观点是：我们在这个领域的论文中有太多模糊和混淆的术语，这对年轻研究人员、其他领域和博士生是有害的。术语令人困惑，通常定义不清（什么是gadget？），在一般计算机科学中有精确含义的术语被用来表示完全不同的东西，而没有人解释它（图灵完备）。
这造成了不必要且有害的混乱，应该加以纠正。
发布者：halvar.flake
时间：晚上11:25
无评论：
发表评论
较新的帖子 较旧的帖子 首页
订阅： 帖子评论 (Atom)
博客归档
► 2025 (6) ► 七月 (2) ► 五月 (1) ► 四月 (2) ► 三月 (1) ► 2024 (4) ► 十二月 (1) ► 七月 (2) ► 一月 (1) ► 2023 (1) ► 十二月 (1) ► 2021 (1) ► 二月 (1) ► 2020 (4) ► 九月 (1) ► 八月 (1) ► 五月 (1) ► 三月 (1) ► 2019 (1) ► 八月 (1) ▼ 2018 (3) ▼ 十月 (1) 图灵完备性、怪异机器、Twitter和… ► 三月 (1) ► 二月 (1) ► 2017 (1) ► 八月 (1) ► 2016 (3) ► 十月 (1) ► 九月 (1) ► 一月 (1) ► 2015 (3) ► 十二月 (2) ► 五月 (1) ► 2014 (2) ► 一月 (2) ► 2013 (3) ► 六月 (1) ► 三月 (1) ► 一月 (1) ► 2012 (1) ► 七月 (1) ► 2011 (2) ► 九月 (1) ► 三月 (1) ► 2010 (3) ► 三月 (1) ► 二月 (1) ► 一月 (1) ► 2009 (17) ► 十二月 (1) ► 十一月 (3) ► 十月 (1) ► 九月 (2) ► 八月 (1) ► 七月 (4) ► 三月 (2) ► 二月 (1) ► 一月 (2) ► 2008 (34) ► 十二月 (2) ► 十一月 (5) ► 十月 (4) ► 九月 (1) ► 七月 (8) ► 六月 (4) ► 四月 (6) ► 三月 (2) ► 二月 (1) ► 一月 (1) ► 2007 (17) ► 十月 (1) ► 九月 (2) ► 八月 (3) ► 七月 (5) ► 六月 (1) ► 四月 (1) ► 三月 (1) ► 二月 (2) ► 一月 (1) ► 2006 (47) ► 十二月 (1) ► 十一月 (4) ► 十月 (2) ► 九月 (2) ► 八月 (3) ► 七月 (7) ► 六月 (5) ► 五月 (8) ► 四月 (8) ► 三月 (2) ► 二月 (4) ► 一月 (1) ► 2005 (10) ► 十二月 (4) ► 十一月 (1) ► 九月 (1) ► 八月 (4)
关于我
halvar.flake
查看我的完整个人资料
链接
Off Convex
由Blogger提供技术支持。