编者按：一直以来，我们都理所当然地认为程序就像高墙，无法不透风，自然也无法躲过黑客无孔不入的攻击。而这篇首发于quantamagazine 的文章却要颠覆我们的认知了：采用形式验证(formal verification)编写的软件，代码就像“数学证明一样可靠”。那么，它是如何实现的？又能带给我们怎样的惊喜呢？本文由雷锋网独家编译，未经授权不得转载。
2015 年夏天，一个黑客团队在美国亚利桑那州尝试控制波音的“小鸟”（Little Bird）无人军事直升机。这队黑客的优势在于：他们一开始就能访问这架无人军事直升机计算机系统的一部分。从这里出发，他们需要做的就是黑进“小鸟”的机载飞行控制计算机，进而控制整架直升机。
在这一项目开始时，作为红方的黑客团队可以像破解家用 Wi-Fi 网络一样，轻易地控制这架直升机。但在接下来的几个月里，美国国防部高级研究计划局的工程师们部署了一种新的安全机制：一个无法被攻占的软件系统。
“小鸟”无人军事直升机计算机系统的关键部分靠现有技术无法攻破，它的代码就像数学证明一样可靠。即便给予了黑客团队六周时间和更多直升机计算机系统的访问权限，他们还是不能攻破“小鸟”无人军事直升机计算机系统的防御。
高可靠性军事网络系统(HACMS)项目发起人、美国塔夫斯大学计算机科学教授 Kathleen Fisher 表示：“黑客们无法以任何方式扩大控制并干扰机器运行。这一结果让美国国防部高级研究计划局非常高兴，他们说现在终于能用这一技术来保护核心计算机系统了。”
这一让黑客们束手无策的技术是名为形式验证(formal verification)的软件编程风格。和大多数计算机代码不同，采用形式验证风格编写的软件读起来就像是数学证明：每一个声明在逻辑上都承接上一个声明。一个这样的程序可以像证明数学定理一样，无论如何测试都一定会得到正确的结果。
微软研究院研究形式验证和安全的研究员 Bryan Parno 表示：“你写下的就是一个描述程序行为的数学公式，再利用一些证明检查器来检查声明的正确性。”
早在计算机科学诞生之初，创造形式验证风格软件的想法就已出现。很长一段时间以来，尝试创造形式验证风格软件的企图都徒劳无功，但在过去十年间，“形式方法”方面的进展让开发形式验证风格软件变得越来越靠谱。如今，学术界、美国军方和微软、亚马逊等科技公司正携手探索形式软件验证技术。
随着越来越多的关键社会职能转移到网上，研究人员们对形式软件验证技术的兴趣也越来越浓厚。在以前，计算机还只是局限于家里和办公室，程序漏洞最多也就是让使用者感到不便。但现在，程序漏洞可能会导致巨大危害，任何具备相关知识的人都能利用同一漏洞自由地进出某个计算机系统。
程序验证领域领导者之一的普林斯顿大学计算机科学教授 Andrew Appel 表示：“在上世纪，如果程序有漏洞，顶多也就是体验糟糕或者程序崩溃。但进入 21 世纪，漏洞可能成为黑客控制程序并窃取数据的通道。漏洞也从糟糕但可以忍受变成了致命威胁，这就严重多了。”
完美程序的梦想
高可靠性军事网络系统(HACMS)项目发起人、美国塔夫斯大学计算机科学教授 Kathleen Fisher
1973 年 10 月，Edsger Dijkstra 产生了一个编写零错误代码的想法。当时他正在参加一次会议，在下榻的酒店里，Edsger Dijkstra 熬到深夜来让编程变得更数学化。他在后来回忆道：“这个想法让我很兴奋，于是我凌晨两点半爬起来，写了一个多小时。”这一材料后来扩充成了《编程的修炼》(A Discipline of Programming)一书，并于 1976 年出版。这本书加上 Tony Hoare 的工作，建立了将正确性证明融入计算机程序编写过程中的视角。
计算机科学并没有采用这一视角，因为此后很多年里，要实现这一视角看起来非常不切实际，即用形式逻辑规则来明确程序的功能。
形式规范要定义一个计算机程序要做什么事，而形式验证则用来确定无疑地证明程序代码完美地符合了规范。打个比方，比如你要给无人驾驶汽车编写一个把你送到百货商店的计算机程序，你需要定义让汽车实现这一目的的动作：汽车可以左转或右转、刹车或加速、启动或停车。最终，你的程序就是为了实现这一目的而对基本操作进行的合理组合，要求是把你送到百货商店而不是机场。
检查程序是否工作正常的传统方式是跑测试。程序员们会给程序大量输入（或单元测试），以确保它符合设计要求。如果你的程序是给无人驾驶汽车规划路径的算法，你也许会用多个不同的位置点来测试它。这一基于测试的方法能得到运行正确的软件，但只是在大多数时候针对大多数应用而言。不过，单元测试并不能确保软件永远运行正确，因为没有办法用所有可能的输入来测试程序。即便程序能通过每一个测试，也不能排除它在一些极端情况下运行不正常，进而形成漏洞。在实际的程序中，这种漏洞也许会简单到只是一个缓冲溢出错误，即程序拷贝多了一丁点数据，并覆盖了某一小块计算机内存。这个看起来无害的错误很难彻底根除，是黑客们攻入计算机系统的捷径。
Bryan Parno 说道：“只要程序中有一个缺陷，就能成为安全弱点。很难测试所有可能输入的所有路径。”
实际的形式规范要比自动驾驶去百货商店细致得多。比如编写一个确认收到文件，并按收到时间对文件进行排序的程序，形式规范需要规定计数器永远只能增长（好让后面接收的文件序号总比前面收到的文件高），以及程序永远也不会泄露给文件签名的密钥。
这么说着容易，真正要用形式语言来编写一个计算机能应用的规范却很难，更何况还是要在整个软件编写过程中都这么做。
Bryan Parno 表示：“写出机器能识别的形式规范或目标非常考验智商。站在高处说‘不要泄露密码’很容易，真正要把它用数学定义的形式写出来却需要很多思考。”
再比如，给列表或数字排序的程序，程序员可能会这么给它写形式规范：
For every item j in a list, ensure that the element j ≤ j+1
（对于列表中的每一项 j，确保 j ≤ j+1）
然而这个形式规范却有一个漏洞：这个程序员默认输出会是输入的排序结果，即假设列表为 [7, 3, 5]，这个程序应该返回 [3, 5, 7]，这样就满足了定义。但列表 [1, 2] 也满足定义，因为“这是一个排序好了的列表，只不过可能不是我们希望的那种排序好了的列表。”
换言之，要把你想要让程序做的事，用排除了所有可能不正确解释的形式规范表示出来很难。上面的例子还只是一个简单的排序程序，想象一个更抽象的例子，比如保护密码。Bryan Parno 说道：“这在数学上是什么意思？定义它也许要写出保护密码的数学描述。安全的加密算法又是什么意思呢？这也是我们一直在研究中一直在思考并取得进展的问题，但要正确应用必须非常小心。”
基于代码块的安全
编写这种程序需要同时编写形式规范以及帮助编程软件推导代码所必须的额外注释， 因此其长度达到了传统程序的五倍。
用合适的工具可以在一定程度上减轻这一负担，比如专门的编程语言和辅助证明程序。但这些东西在上世纪 70 年代时还不存在。同时担任形式验证计算机系统开发团体 DeepSpec 首席研究员的 Andrew Appel 表示：“当时的很多技术都不成熟，因此到 80 年代，很多人就对它失去了兴趣。”
即便工具得到了改进，形式验证计算机程序还有另一个问题要解决：没人确定是否有必要用它。虽然形式方法爱好者们总是在说小的程序错误最后会变成灾难性漏洞，但大家看到的却是计算机程序工作得相当好。
的确，这些计算机程序有时候会崩溃，但和巨细无遗地一条条用形式逻辑系统的语言来编写程序相比，丢失未保存的数据或时不时重启机器貌似也可以接受。有时候，连形式规范最早期的领导者也会怀疑其是否有用。在上世纪 90 年代，霍尔逻辑(Hoare logic，首批推导计算机程序正确性的形式系统之一)的发明者 Hoare 就承认，也许形式规范是一个不存在的问题的劳动密集性解决方案。他在 1995 年写道：
十年前，形式方法的研究者们（我是其中错得最厉害的一个）预测，计算机世界会拥抱并感激形式化带来的每一点协助……结果是，全世界并没有碰到我们一开始打算解决的那种问题。
后来出现了互联网。互联网之于编程错误就像是飞机之于传染病：当所有电脑都连接在一起时，不方便但可以忍受的软件漏洞会导致一系列安全问题。
Andrew Appel 说道：“有一点我们当时没有特别明白，那就是互联网上有一些软件面向所有黑客开放，如果这种软件里有一个漏洞，它就会成为安全威胁。”
在微软研究院开发形式验证版 HTTPS 协议的计算机科学家 Jeannette Wing
在研究人员们开始明白互联网给计算机安全带来的致命威胁后，程序验证就开始焕发第二春了。研究人员们这一次在加强形式方法的技术上取得了很大进展：改进了支持形式方法的辅助证明程序 Coq 和 Isabelle；开发了新的逻辑系统，为计算机提供推导代码的框架；发展改进了运算语义学(operational semantics)，即可以用正确的词语来表达程序应该做什么事了。
微软研究院企业副总裁 Jeannette Wing 表示道：“所有自然语言都具有歧义性。而在形式规范中，你会写出基于数学的精确规范，以解释你想要程序做什么。”
另外，形式方法的研究人员们也修改了自己的目标。在上世纪七、八十年代，他们想要打造完整的经过形式验证的计算机系统，从芯片到计算机程序。现在，大多数形式方法研究人员都专注于验证更小但更脆弱或系统关键的组成部分，比如操作系统或加密协议。
Jeannette Wing 说道：“我们不再宣称要证明整个系统都正确，每一个比特都百分百可靠，连芯片层面也如此。做出这样的宣言很可笑。对于我们能以及不能做什么，我们现在有了更清楚的认识。”
高可靠性军事网络系统项目证明，通过明确定义计算机系统中的一小部分，就能极大地提高安全性。这个项目的最初目标是打造一架无法被黑的娱乐四旋翼无人机。但无人机运行的软件非常庞大，黑客攻破一部分，就能获得整个系统的控制权。于是在接下来的两年里，高可靠性军事网络系统团队将无人机的任务控制计算机程序代码分成了很多块。
他们还用“高可靠性构建模块”重写了软件架构，这些模块可以让程序员们证明自己代码的可靠性。其中一个经过了形式验证的模块可以确保，即便用户取得了一个代码块的控制权，他也不能提升自己的权限来进入其他代码块。
随后，高可靠性军事网络系统团队将这一区块化的软件安装到了“小鸟”无人军事直升机上。在和红方黑客团队的较量中，他们先让黑客们可以访问某一次要功能如摄像头的代码，但黑客们肯定会被困住，因为这经过了数学证明。Kathleen Fisher 说道：“我们用机器从数学上证明了红方肯定无法突破这一代码块，因此他们无法突破也就很顺理成章了。结果与定理一致，也很好确认。”
在“小鸟”无人军事直升机上测试后，美国国防部高级研究计划局就开始将这些工具和技术应用到其他军事技术上，比如卫星和无人驾驶载重卡车。新的项目和过去十年中形式验证传播的方式保持一致：每一个成功的项目都能加强下一个项目。Kathleen Fisher 表示道：“人们再也没有借口说这么做太难了。”
验证互联网
安全和可靠性是驱动形式方法的两大目标。每过一天，提高这两大目标的需要就会变得越发明显。在 2014 年，一个本可以被形式规范捕捉到的小编程错误导致了“心脏失血”漏洞，甚至可能让互联网瘫痪。一年以后，两个白帽子黑客证明了我们对联网汽车的最大恐惧：他们成功地控制了别人的大切诺基。
随着安全风险的日益增加，形式方法研究人员们正推动更具野心的计划。Andrew Appel 领导的 DeepSpec 正试图建立一个经过完全验证的端到端系统（就像网络服务器一样）。如果这一计划成功，就能将过去十年中许多更小规模的验证成果组合到一起，比如经过完全验证的操作系统内核。Andrew Appel 说道：“DeepSpec 现在专注在做但还没有做到的事情是，如何将这些组件用规范接口连接起来。”
在微软研究院中，软件工程师们已经在进行两个雄心勃勃的形式验证项目。第一个项目名为 Everest，旨在打造经过形式验证的 HTTPS 协议。
第二个项目则是希望能为无人机这样的复杂物联网系统开发出经过验证的规范。这个项目面临的挑战非常大。要知道传统软件按离散、确定的步骤执行，无人机软件会根据连续的环境数据流，运用机器学习来计算概率并进行决策。要把这种不确定性形式规范化会需要很多思考。不过形式方法在过去十年中取得了很多进展，Jeannette Wing 对此表示乐观，认为形式方法研究人员们会找到解决办法。
via quantamagazine
推荐阅读：
正在生成分享图...
张进