在计算机操作系统中,文件系统负责将数据写入磁盘,并记录数据的存储位置。如果计算机在写入数据时崩溃,文件系统的记录可能会损坏。数小时的工作可能因此丢失,或者程序可能无法正常运行。
MIT研究人员将于10月在ACM操作系统原理研讨会上展示首个在数学上保证崩溃期间不会丢失数据记录的文件系统。尽管以当今标准衡量,该文件系统速度较慢,但研究人员用于验证其性能的技术可以扩展到更复杂的设计中。最终,形式化验证可能会使开发可靠、高效的文件系统变得容易得多。
“许多人担心的是,如何构建既能在正常运行时保持可靠,也能应对崩溃、断电、软件漏洞、硬件故障等各种情况的文件系统,”MIT计算机科学与工程副教授Nickolai Zeldovich说,他也是这篇新论文的三位MIT计算机科学教授之一。“要确保文件系统能够在任何时间点从崩溃中恢复,是一件很棘手的事,因为可能崩溃的地方实在太多了。你真的必须考虑每一条指令或每一次磁盘操作,并思考:‘好,如果我现在崩溃,会怎样?接下来又会怎样?再接下来呢?’因此,从经验上看,人们在文件系统中发现了大量与崩溃恢复相关的漏洞,而且即使是经过充分测试的文件系统,人们仍在不断发现新的漏洞,因为这件事实在太难做好了。”
试验场
Zeldovich和他的同事们——MIT电气工程与计算机科学系(EECS)的Charles A. Piper讲席教授Frans Kaashoek、计算机科学副教授Adam Chlipala、EECS研究生Haogang Chen,以及EECS本科生Daniel Ziegler——通过一种被称为形式化验证的方法,确立了其文件系统的可靠性。
形式化验证是指以数学方式描述计算机程序可接受的运行边界,然后证明该程序永远不会超出这些边界。这一过程十分复杂,因此通常只应用于程序功能非常高层次的示意性表示。然而,将这些高层次的示意转化为可运行的代码,可能会引入大量证明未曾涉及的复杂问题。
“关于其他文件系统的所有这些纸面证明,实际上可能都是正确的,但我们无法确定有哪个文件系统真正代表了证明所针对的对象,”Ziegler说。
MIT研究人员的工作与众不同之处在于,他们证明的是文件系统最终代码的属性,而非高层次的示意。为此,他们利用了一种称为证明助手的工具,它提供了一种形式化语言,用于描述计算机系统的各个方面及其之间的关系。
“这个形式化证明环境包含一种编程语言,”Chlipala解释道,“因此我们用编写证明所用的同一种语言来实现文件系统。证明直接针对实际的文件系统进行检验,而不是针对某个与代码没有任何形式化联系的白板理想化模型。”
证明助手Coq提供了工具,但MIT研究人员仍需亲自完成工作。首先,他们必须使用Coq的形式化语言描述文件系统的各个组成部分。“你必须定义:‘什么是磁盘?’”Zeldovich说。
“还有‘什么是比特?’”Chlipala补充道。
接下来,他们必须以形式化方式描述这些不同组件在崩溃条件下行为之间的逻辑关系。只有这样,他们才能开始构建证明,证明文件系统会按照应有的方式运行。最后,他们必须编写相应的文件系统。整个过程中,Coq自动完成的部分,是确认文件系统确实遵守了证明中所描述的逻辑关系。
可复现性
在编写文件系统的过程中,他们反复回头修改系统规范,也反过来修改代码。但是,尽管他们重写文件系统“大概10次”,Zeldovich说,Kaashoek估计,他们大约90%的时间都花在了系统组件及其之间关系的定义以及证明上。
“我们已经多次编写过文件系统,所以我们确切地知道它会是什么样子,”Zeldovich说。“而对于这些逻辑和证明来说,书写方式有很多种,而且每一种都会在之后产生微妙的影响,而这些影响我们并没有真正理解。”
“从来没有人做过这件事,”Kaashoek补充道,“这不像你可以查到一篇论文告诉你‘这就是做法’。但现在你可以读我们的论文,想必能快得多地完成这件事。”
“人们过去并非没有证明过东西,”Google安全研究主管Ulfar Erlingsson说,他从远处关注了这项新工作。“但通常情况下,为创建证明而开发的方法和技术、形式化体系,都过于深奥且过于针对特定问题,因此几乎没有机会出现后续工作去在其基础上推进。但我可以肯定地说,Adam在Coq和分离逻辑方面的成果,将会被不断推进,并应用于许多不同领域。这正是最令人兴奋的地方。”
本文与 MIT News合作发布。文章发布不代表世界经济论坛认同其中观点。
如需及时了解 Agenda 订阅我们的每周通讯。
作者:Larry Hardesty是MIT News的一名撰稿人。
图片:柏林Konrad-Zuse Centre for applied mathematics and computer science(ZIB)中的一台机器人磁带库,用于数字数据的海量存储。REUTERS/Thomas Peter

