爱时密码研究院:只有本地才是安全的吗?

 admin   2019-12-21 15:53   114 人阅读  0 条评论

在物理学中,局部性是指对象仅受其周围环境直接影响的概念。在计算机科学的背景下,通常会说“计算是本地的”,这意味着计算机程序的注意力通常一次只集中在一个内存区域上。这是缓存的基础:较小的焦点区域将适合缓存,并且对其的访问将很快。从本质上讲,这些是不同的概念,但是从表面上看,它们是相似的,这使我想知道各种计算过程的局部性(从物理意义上来说)。

有人会问,安全性或总体上说正确性是计算的局部属性。可以通过检查每个单独的步骤来强制实施安全性属性,还是只能通过退后一步并查看大图来验证安全性属性?或者,如果两种方法都起作用,哪种方法更有效?

让我们从一个玩具示例开始。想象一下一个服务,它向用户请求一个整数,将其加1,然后将其返回给用户。该服务可以同时处理来自多个用户的多个请求,我们希望确保无论Alice选择哪个整数,她都不会影响Bob的结果。

为了对此进行正式建模,让我们假设有一个两输入两输出图灵机的概念。就像标准的图灵机一样,只是它需要两个输入并产生两个输出。我们可以通过在磁带上放置一个特殊的符号来分隔两个输入和输出,从而用标准的图灵机模拟一个。

Peggy给我们提供了这两个输入两个输出的图灵机之一,我们将其称为X。Peggy声称X是“一对一添加”服务的安全实现,但没有提供这一事实的证明。 。X机器应该具有以下属性:对于给定的任何一对整数(A,B),您都会得到(A + 1,B + 1)。更正确地说,X计算某些函数F,并且对于所有整数A和B,如果F(A,B)=(A + 1,B + 1),则X是“安全的”。这里“安全”而不是“正确”,因为我计划稍后减弱要求。

检查X是否安全的计算复杂度是多少?如果X是一个任意的图灵机,那么这个问题是无法确定的,因为我们将不得不检查X的所有输入是否至少停止。但是,假设我们知道X的所有输入都停止了。通常,这个问题仍然无法确定,因为给定了图灵机M,我们可以通过构造X来确定M是否在空输入上暂停,以便产生正确的结果,除非该对中的第一个整数编码了M暂停的准确时间。空输入。因此,尽管X应该是多么简单,但是为了希望检查X,我们必须将兴趣限制在有限的输入范围内。

在输入限制在有限范围内的情况下,确定X的安全性的问题很困难。给定一个布尔公式,我们可以构造一个在所有输入上都是正确的X,除非该对中的第一个整数编码了令人满意的赋值。

到现在为止应该很清楚,在没有Peggy提供有用证据的情况下,并且不强迫Peggy从受限集合中选择X的情况下,确定X是否安全是非常困难的。我们是否可以通过简化X的每次计算,而不是尝试自己验证X,从而使我们的任务更轻松?我们能否在X的给定输入执行的每个步骤中检查一些局部属性,以查看其是否做正确的事情,如果发现不正确,至少返回一个错误?

想象一下,我们有一些“检查”图灵机,我们将其称为C。在X执行的每个步骤中,都为C提供了X计算的记录,包括其状态和磁带内容随时间的变化。C接受或拒绝。如果C接受,则表示X到目前为止一直可以正常工作。如果C拒绝,则意味着X不会产生正确的结果。我们可以将C视为计算中每个细节的参考监视器。如果C一直接受,则X产生正确的结果。如果C拒绝,则违反安全属性。我们将忽略查找C的问题,仅假设我们找到了存在的最有效的C。

C的计算复杂度是多少?对于这个加一的玩具示例,C可能很简单。C要做的全部工作就是接受,直到X停止之前的步骤为止,然后在该步骤上,找到输入对,为每个输入对添加一个,并检查X是否正确。这可行,但是是循环的。如果可以确信C安全地计算了我们感兴趣的函数,为什么我们不仅仅使用C?为什么要打扰X?

为了使检查图灵机的概念有用,我们需要限制C的功率。最好说“ C本身不能用来代替X”,但这行不通,因为C可能必定是图灵完备的(例如,如果Peggy声称X是通用图灵机)。相反,让我们看一下实际中运行时安全性属性检查的工作方式。当进程打开文件时,操作系统将根据进程的特权和文件的权限来做出访问控制决定。操作系统不会查看整个计算历史来做出决定。该决定是基于有限的信息做出的,因此,此处要做的显而易见的事情是限制C对信息的访问。

我们应该如何限制C对信息的访问?为C提供访问整个计算历史记录的权限不是“本地”的,因此我们至少应限制对一定数量的过去步骤的访问(取决于X)。这仍然使C可以访问整个磁带内容,与实践相比,这太多了,因此我们可能想进一步限制C的访问。但是现在,让我们将C限制为一定数量的过去步骤。

由于C的访问仅限于最后K个配置,因此C的复杂性不太明显。我们确实知道C本身并不比验证X复杂,因为C可以忽略磁带内容,而在每次运行时只检查X即可。这并不多说,因为这个问题是NP难题。C能比这更好吗?即使对于添加一个的简单功能,它也不是显而易见的。当原始输入不再可供C使用时,会发生什么?当输入消失时,C不再能够仅计算函数并检查答案。即使X足够好以至于无法保留输入内容,但是一旦C从第一步开始就不再能够访问磁带内容,C便无法确定X并未将它们更改为傻瓜C。现在的问题更加有趣了。 。

那么安全性在本地吗?是否有一个C比单独检查X更有效?如果我们要计算的函数比加1更复杂,并且涉及两个输入之间的微妙交互,或者如果安全属性不是完全正确,而是较弱的东西,将会发生什么。例如,如果说X用于计算(A,B)↦(A + B,B),那么我们关心的安全属性可能仅仅是,无论A的值如何,第二个参数都不会改变。在这种情况下,C的复杂性是什么?

这是一个推测:存在与实际相关的功能,以及这些功能的安全性,没有哪个C比单独检查X(或证明X正确)更有效。如果这个猜想是正确的,则意味着安全性不是局部的,对于那些非局部功能和安全性属性,我们能做的最好的就是证明我们的代码正确。尤其是,这些漏洞将无法缓解任何外部应用的防御措施,例如用户帐户隔离,DEP,ASLR,虚拟机隔离或网络防火墙。

正如我所说的那样,这个猜想是模棱两可的,因为不清楚X是从哪个域中提取的,甚至不清楚X是被普遍地还是存在地量化了。提出一款游戏,其中Peggy试图欺骗我们使用通常正确但仍然糟糕的X,并且我们试图找出X是好是坏,这可能是最有用的。从本质上讲,这就是软件开发人员引入错误时发生的情况。唯一的区别是它通常不是故意的。当我们将系统组合在一起时,将应用相同的模型:它们似乎可以正常工作,但是我们必须怀疑它们是否确实可以工作。我们也可以权衡取舍:如果佩吉(Peggy)向我们提供了更多信息(例如部分证明),是否可以使我们的安全检查更有效率?

(对复杂性理论家的注意:是的,我的意思是说,实际上C应该由语言C来决定复杂性,而不是特定C的任何属性,但是我是用这种方式编写的,所以我坚持使用。)


本文地址:http://lovetimes.cn/post/7.html
版权声明:本文为原创文章,版权归 admin 所有,欢迎分享本文,转载请保留出处!

 发表评论


表情

还没有留言,还不快点抢沙发?