智能合约入门系列 | 智能合约工程重要环节：形式化验证方法

北京航空航天大学分布式实验室 北京航空航天大学云南创新研究院  周楚涵 胡 凯

形式化验证（Formal Verification）是智能合约工程的重要环节，它可以成为对合约进行确定性验证的一种技术，通过形式化语言把合约中的概念、判断、推理转化成智能合约模型，可以消除自然语言的歧义性、不通用性，进而采用形式化工具对智能合约建模、分析和验证，进行一致性测试，最后自动生成验证过的合约代码，形成智能合约生产的可信全生命周期。

1. 形式化验证

形式化验证（Formal Verification）是基于形式化方法（Formal Method）相关理论。形式化方法起源于20世纪50年代对编译技术的研究，20世纪60年代发生了“软件危机”，当时针对“软件危机”，主要有两种解决方法：一种是采用合理有效的工程方法来管理和组织软件的开发过程，这也是软件工程的起源；另一种是建立严格的数学推导理论，以指导软件开发过程，这方面推进了形式化方法的深入研究。

形式化方法主要包括形式规约和形式化验证。形式规约是指应用具有精确语法和语义的形式化语言来刻画系统的性质和行为，是设计系统约束和验证系统是否正确的依据；形式化验证是在形式规约的基础上，建立系统的行为及其性质的关联，进而验证系统是否需求的关键性质。形式化验证与形式化规约之间具有紧密的联系，形式化验证就是验证已有的程序（系统）P，是否满足其规约（φ，ψ）的要求（即P（φ，ψ）），它也是形式化方法所要解决的核心问题。

目前常见的形式化验证方法主要可分为两类：演绎验证和模型检测。演绎验证主要基于定理证明（Theorem Proving）的基本思想，采用逻辑公式描述系统及其性质，通过一些公理或推理规则来证明系统具有某些性质。目前主要的演绎验证工具有：基于Manna-Pnueli证明系统的STeP（Stanford Theorem Prover）、TLV、机器定理证明器（ACL2、Coq、HOL、Isabelle、Larch、Nuprl、PVS、TPS）等。模型检测（Model Checking）方法的基本思想是通过状态空间搜索来确认合约是否具有某些性质。即给定一个合约（程序）P和规约ψ，生成对应于合约模型M，然后证明M╞ψ，即规约公式ψ在合约模型M中成立，这样就证明了合约（程序）P满足规约ψ。常用的模型验证工具有：SMV（Symbolic Model Verifier）、SPIN（Simple Promela Interpreter）、SDL（Specification and Description Language）、UPPAAL等。

模型检测技术是近三十年来最成功的自动验证技术之一，目前被广泛地应用于有限状态系统的验证，包括电路设计和通信协议的分析与验证。根据所要验证模型的规格特点，可以分为复合检验器、时态逻辑模型检测器和行为一致检验器。根据采用的不同的技术可以分为：面向状态的模型检测和符号模型检测。模型检测器的基本原理都是一样的，其工作原理如图1    所示。通常情况下，模型都需要经过迭代验证的过程，才能最终满足验证条件。

图1 模型检测器原理

形式化验证是一种基于数学和逻辑学的方法，在智能合约部署之前，对其代码和文档进行形式化建模，然后通过数学的手段对代码的安全性和功能正确性进行严格的证明，可有效检测出智能合约是否存在安全漏洞和逻辑漏洞。该方法可以有效弥补传统的靠人工经验查找代码逻辑漏洞的缺陷。形式化验证技术的优势在于，用传统的测试等手段无法穷举所有可能输入，而我们用数学证明的角度，就能克服这一问题，提供更加完备的安全审计。

2. 形式化验证在区块链领域的应用现状

随着区块链平台级应用的普遍化，智能合约涉及的金额呈指数级别增长，智能合约的安全问题也成为投资者和开发者共同关注的焦点。今年以来有数个基于ERC-20的项目因为智能合约代码出现漏洞而遭到黑客攻击，导致投资者巨额的损失。为了防止类似事件的发生，交易所、钱包、项目方等都在智能合约安全上加大投入，同时围绕着智能合约安全的周边生态成为目前投资的热点。

形式化验证技术已经在军工、航天等高系统安全要求领域的取得了相当成功的应用，将形式化方法应用于智能合约，使得合约的生成和执行有了规范性约束，保证了合约的可信性，使人们可以信任智能合约的生产过程和执行效力。通过形式化语言，把合约中的概念、判断、推理转化成智能合约模型，可以消除自然语言的歧义性、不通用性，进而采用形式化工具对智能合约建模、分析和验证，进行一致性测试。合约的形式化验证保证了合约的正确属性，自动化代码生成提高了合约的生成效率，合约的一致性测试保证了合约代码与合约文本的一致性。

目前区块链产业中与形式化验证相关的产品可以分为三类: VaaS平台，公链，和语言，应用尚在技术的早期，自动化程度和实用性，及用户工具还有待于极大的进步。

（1）Vaas平台

是直接面向开发者提供形式化验证服务的平台。目前Vaas类项目包括 CertiKzecurify.ch、Runtime Verification 等项目。目前，CertiK仍在初始阶段，Securify.ch 的测试版已经上线，而 Runtime Verification 已经在商业运营。

与其它几个项目不同，Runtime Verification是基于EVM虚拟机二进制码进行形式化验证，而非针对智能合约本身用的高级语言，因此在安全性上又更进一步，避免了因编译器编译过程中可能产生的漏洞。

（2）语言

语言类产品一般为函数式语言的子语言，提供与智能合约形式化验证相关的开发者库和工具，目前有Imandra和Tezos等项目。

其中，Imandra发布了一套开源的以太坊虚拟机用ImandraML语言标记的模型，并且专注于交易所等金融应用场景的形式化验证，用以确保金融交易的合法合规，据称相关技术已经用于华尔街顶级投行的交易系统。

（3）公链

直接包含形式化验证引擎的公链产品目前只有 The Matrix 项目，特征是基于 AI 辅助的形式化验证及动态约束的检查。AI 是否对于形式化验证的自动化带来帮助在技术上仍是个未知数。

3. 智能合约的形式化验证

智能合约的安全性验证问题迫在眉睫，智能合约可能存在的主要安全隐患有：1）合约中某一方利用合约漏洞修改合约，使得合约执行结果偏向某一方；2）智能合约攻击者利用合约漏洞攻击合约，造成合约中财产的损失。这最终都会导致人们对于智能合约的不信任。在智能合约的验证方面，形式化验证方法可以检查智能合约的很多属性，例如，合约的公平性、可达性、有界性、活锁、死锁、不可达，以及无状态二义性等。形式化方法重点可以解决智能合约产生与执行的可信性问题。采用模型检测的优点是完全自动化并且验证速度快，即便是只给出了部分描述的合约，通过搜索也可以提供关于已知部分正确性的有用信息。尤其重要的是，在性质未被满足时，搜索终止可以给出反例，这种信息常常反映了合约设计中的细微失误，因而对于合约排错有极大的帮助。

这里我们采用模型检测工具SPIN对智能合约进行验证。SPIN是用来检测和验证分布式软件系统的模型检测器。SPIN（Simple Promela Interpreter）即PROMELA解析器，是由美国贝尔（Bell）实验室开发并用于形式化验证分布式软件系统的模型检测器，是一种广泛应用于大规模复杂软件系统的形式化模型检测器，与商业性模型检测器相比，SPIN在技术上和使用上更加自由和开放。

描述一个智能合约，包括以下几个方面：合约方的信息（身份、权限等）、合约状态机（合约背景、合约状态集合、状态转换函数、合约输入、合约输出、合约的初始状态和合约的终止状态）、各个合约方的执行状态机。

我们定义智能合约 ，为一个二元组，其中：

Con为合约的基本信息描述，Con={CId，CTimeStamp，CTime，CSign}， CId为合约标识，是区分合约的唯一标识，CTime为合约的时限，即合约的有效期，CTimeStamp为合约的时间戳，即签订合约的日期，CSign为合约方的签名。

Machine={ }，表示各个合约方的执行状态机的集合， 表示第i个合约方的执行状态机。

合约状态机 =<MStatus，CInput，COutput，CFunction，CInit，CFinal，CBackground >，为一个多元组，其中：

MStatus是智能合约中第i个合约状态机的所有状态的集合和对集合的描述，MStatus={ ， ， ， }，其中，i表示第i个进程（0 i n）， 表示合约的第i个进程的进程集合。一个合约是由一个或多个进程组成的。

CInput是合约的输入集合，CInput={CIEvent，CITime}，CIEvent为合约输入的事件，CITime为合约输入的时间。智能合约有两种触发执行机制，分别为时间触发和事件触发，合约通过时间或事件的输入触发合约的执行，使得智能合约的状态发生变化。

COutput是合约输出的集合，COutput={ COData}，COData为合约输出的数据。智能合约规定可以部分执行完成，因此，合约的输出可能是合约执行中间的一个结果输出，也可能是合约全部执行完成。合约的输出统一使用数据类型表示，每一个输出都意味着合约状态的迁移，同时每一次合约输出都分别对应了一个合约状态。

CFunction是合约状态转换函数的集合，且有CFunction：MStatus MStatus。

CInit为合约初始状态值，且 。

CFinal为合约终止状态的集合，CFinal={ ， ， ， }，且 。

CBackground为智能合约其他相关信息的描述。

在智能合约的描述过程中，合约的状态变迁过程代表了合约的执行过程，合约模型采用PROMELA进行合约建模。

SPIN的验证过程，首先从描述系统模型的规格开始，经过编译器的分析确定没有语法错误后，对系统模型进程之间的交互进行模拟，直至确认系统模型中出现的行为和系统设计的预期行为一致。其次，SPIN从系统的高级规约中会生成一个优化后的on-the-fly验证程序，经过编译器编译后执行，执行中会检测是否有违背正确性说明，若有反例出现，则返回交互模拟的执行状态进行再修正，确认出错原因，直至完成正确性验证。其验证框架如图 2所示

图 2 基于SPIN验证框架

据此验证框架，我们设计完成了一个形式化验证系统，取得了较好的验证效果, 值得推广应用，后文将给出一个验证案例。