使用Z3进行软件验证和分析

这篇文章提供了有关如何利用Z3定理证明器来推断密码软件，协议和其他方面的正确性以及识别潜在安全漏洞的技术介绍。

QUIC传输协议IETF草案的旧版本中记录的算法的建模和分析。

椭圆曲线加密的特定有限域算术运算建模，整数使用统一的饱和分支调度表（四个分支，每个64位）表示，以证明与任意精度1算术等效，并用于生成测试用例。

软件系统和协议的设计和实现是复杂的（在密码学中更是如此），容易出现错误和安全漏洞。在大多数情况下，该行业并不固步自封，而是继续完善策略，策略，过程和工具，以提供一定程度的软件安全性保证。人们对形式化方法非常感兴趣，以增加对密码系统安全性的信心。 BoringSSL使用广泛的软件，它使用形式化方法来生成正确的椭圆曲线实现。 TLS 1.3协议规范设计也受到这些技术的影响。有人可能会说，这种兴趣是由多种因素共同造成的，包括但不限于消除漏洞方面的持续困难（TLS协议及其实现在这些漏洞中占有相当大的份额），更多计算资源的可用性，使用工具，甚至来自区块链世界的不断创新。无论如何，这是一个有趣的研究领域，具有切实而有益的成果。

形式验证是一组证明系统某些属性的技术。它可能针对软件（或硬件）开发生命周期的不同阶段，包括设计，实施和测试。有几种验证方法，有时是互补的。出于介绍的目的，我们将研究满意度模块理论（SMT）求解器，尤其是Z3，以及如何将其用于推理系统，证明某些属性并生成有趣的测试用例。

SMT是用一阶逻辑语言表达的问题，在该语言中，人们尝试确定在感兴趣域（理论）中解释的逻辑公式（例如整数，列表或位向量）是否可以满足。 SMT求解器主要搜索针对所述问题的解决方案，即公式是否可满足，并允许我们检查解决方案的模型。

Z3是Microsoft Research开发的流行的SMT求解器，于2015年开源。它特别适合于软件验证和分析。它已成功用于研究和商业环境。

SMT-LIB是SMT求解器的通用语言，并且具有Lisp语言语法。本文将使用SMT-LIB。请注意，Z3有几种，也许更容易接近的API，包括Python语言。

让我们以一个简单的例子来说明这些概念。我们可以查询诸如Z3之类的SMT求解器，以确定在整数和算术（例如）的上下文中是否满足表达式x + y = 5。是否存在整数x和y，它们的总和为5。我们将用SMT-LIB语言表达问题：

;这是一条评论-求解器将其忽略；将x声明为整数（declare-const x Int）;将y声明为整数（declare-const y Int）;表达问题-例如将公式添加到我们要证明的公式列表中（assert（=（+ x y）5））;查询求解器以确定SMT问题是否可以满足（check-sat）;如果是，请显示一个可能的解决方案（获取模型）

sat表示求解器确定可以满足公式。它确定了一个解决方案（模型），其中y设置为0，x设置为5，可以满足上述问题。稍后，我们将处理更复杂的示例。

现在，我们对SMT，Z3及其功能有了基本的了解，我们将更深入地研究两个用例。

在审查QUIC协议实现的过程中，作者发现了与RFC草案33中的示例非恒定时间2解码算法的差异有关的潜在问题。具体地，该样本算法暗示了许多检查，其中显然不包括某些检查，其中候选人_pn ＜1。 （1＆lt;＆lt; 62）-pn_win，或不完整，例如候选对象＆gt;从实现中使用pn_win代替候选人_pn＆gt; = pn_win：

///注意要进行额外的检查以防止上溢和下溢。//（...）如果候选人_pn＆lt; =预期_pn-pn_hwin和候选人_pn＆lt; （1＆lt;＆lt; 62）-pn_win：返回候选者pn + pn_winif候选者pn＆gt;预期的pn + pn_hwin和候选的pn＆gt; = pn_win：返回候选的pn-pn_win //（...）

差异及其影响已秘密报告给维护人员。算法步骤相对容易实现，但是在某种程度上来说更具挑战性。提出可能确实会引起上溢和下溢的输入并确定这些发生的可能性（自然地或在不利条件下）不是一件容易的事。 Z3允许我们轻松查询（并生成）此类输入。该算法易于建模为奖励。我们将很快执行此操作，但首先让我们简要介绍一下QUIC协议和数据包编号。

QUIC是基于UDP的多路复用安全传输协议。它提供流多路复用，流控制，低延迟连接建立，连接迁移以及经过身份验证和加密的标头和有效负载。 QUIC规范的最新草案版本描述了QUIC协议安全性，其中一些由TLS 1.3提供。 QUIC与TLS的集成在“使用TLS保护QUIC”草稿-ietf-quic-tls-33互联网草稿备忘中有更详尽的描述，与QUIC协议规范一样，这项工作正在进行中。 QUIC协议的许多实现都是可用的。它被Facebook和Google等组织广泛用于客户端和后端服务。

QUIC协议数据嵌入在“数据包”逻辑单元中，然后又封装在UDP数据报中。 QUIC数据包在数据包编号空间（初始，握手和应用程序数据空间）中组织；每个数据包编号空间均从数据包编号0开始，并独立递增，直至2 ^ 62-1，在此阶段必须关闭连接。端点维护一个单独的数据包号，用于发送和接收QUIC数据。 QUIC数据包数据使用加密保护。 QUIC数据包号用于确定用于数据包保护的加密随机数。

数据包在连接建立期间使用长数据包头，之后使用短数据头。两种格式均采用数据包编号的可变长度编码（8、16、24或32位）。仅表示数据包所需的数据包编号的最低有效位通过网络发送。为了成功解码和重建该号码，端点必须跟踪收到的最大数据包号码。此外，对等方必须使用足够大的数据包编号长度，以表示从最大已确认数据包编号到发送的数据包编号足以允许成功解码的足够范围。

回到在Z3中对数据包编号解码算法建模的过程中，作者后来发现，QUIC实现使用了RFC草案17中提出的算法，研究人员在其中发现了错误。这些已在RFC的后续版本中修复。有趣的是，研究人员使用正式验证发现了这些错误。

QUIC Transport RFC草案17提供了样本和错误的数据包编号解码算法，复制如下：

DecodePacketNumber（largest_pn，truncated_pn，pn_nbits）：Expected_pn = large_pn + 1 pn_win = 1＆lt;＆lt; pn_nbits pn_hwin = pn_win / 2 pn_mask = pn_win-1＃传入的数据包编号应大于＃Expected_pn-pn_hwin且小于或等于＃Expected_pn + pn_hwin＃＃这意味着我们不能只从中剥离尾随位＃Expected_pn并添加truncated_pn，因为这可能会在窗口外产生一个值。 ＃＃以下代码计算出一个候选值，并且＃确保它在数据包编号窗口内。候选人_pn =（expected_pn＆〜pn_mask）|如果候选人编号<=预期的编号-pn_hwin，则截断_pn：返回候选人编号+ pn_win＃注意，当候选人编号＃接近零时，对下溢进行额外检查。如果候选人_pn＆gt; Expected_pn + pn_hwin和候选人_pn＆gt; pn_win：返回候选人_pn-pn_win返回候选人_pn

我们将在Z3中为上述有问题的算法建模，并找到输入值以溢出数据包号解码例程。我们首先创建一个空的文本文件，名为解码.smt2。 smt2扩展名表示SMT-LIB语言格式。

表达问题时，我们需要进行声明式思考，有点像编写SQL SELECT语句或在Prolog中编程。首先，我们声明使用SMT-LIBclarify-const术语在RFC Draft 17解码算法中引入的变量，以及为方便起见添加的结果变量。我们将对数字进行运算-我们选择将它们表示为64位大小的位向量（_ BitVec 64），类似于无符号的64位C变量类型或计算机内存寄存器，以与通用编程中开发的大多数QUIC实现紧密匹配现代平台上的语言。

（声明常量最大的pn（_ BitVec 64））（声明常量截断的pn（_ BitVec 64））（声明常量pn-nbits（_ BitVec 64））（声明常量期望的pn（_ BitVec 64 ））（声明常量pn-win（_ BitVec 64））（声明常量pn-hwin（_ BitVec 64））（声明常量pn-mask（_ BitVec 64））（声明常量pn-pn（_ BitVec 64）（声明常量结果（_ BitVec 64））

（断言（bvule truncated-pn（_ bv4294967295 64）））;最大2 ** 32 -1位（断言（bvule maximum-pn（_ bv4611686018427387903 64）））;最多2 ** 62 -1位（断言（bvuge最大pn（_ bv0 64）））

我们在前面的QUIC传输协议介绍中了解到，编码的数据包号（截短的pn）不能超过2 * 32-1。我们还了解到，解码的数据包号的范围是0到2 ^ 62-1。例如，第一行断言被截断的pn变量必须始终小于或等于2 ^ 32-1（bvule或“位向量无符号更低或等于”）。在声明这些约束时，接下来，我们也逐步但显着地减少Z3求解器的搜索空间，以寻找可能导致解码的数据包编号溢出的解决方案。

请注意，在对抗性环境中，我们不能假设这些条件成立。在对诸如QUIC实施之类的系统进行安全评估时，我们需要验证从数据包中提取出truncated_pn值的正确性，以及其值不会超出范围。

（断言（或（或（= pn-nbits（_ bv8 64））（= pn-nbits（_ bv16 64））（= pn-nbits（_ bv24 64））（= pn-nbits（_ bv32 64）））） ;;确保截短的pn＆lt; 2 ^ pn-bits＆gt; = 2 ^（pn-bits-8）;;在不利的情况下可能不是这种情况（断言（和（bvult截断的pn（bvshl（_ bv1 64）pn-nbits））（bvuge截断的pn（bvshl（_ bv1 64）（bvsub pn-nbits（ _ bv8 64））））））

请记住，我们解释了编码的数据包编号大小可以是8位，16位，24位或32位。上面首先声明，编码的分组数大小pn位必须采用以下值之一，例如： （_ bv8 64）），表示“我们选择的变量表示形式为“值8且大小为64位的位向量”。

然后，我们通过一个断言确保了编码的数据包编号长度pn位对应于严格地编码截断的数据包编号pn所需的长度，以对预期的QUIC协议规范行为进行建模。例如，数据包编号0xff00可以编码为0x00ff00（三个字节长），但是前导字节是多余的，因此两个字节足以编码其长度。请注意，我们不能假设这种对应关系是在不利的环境中进行的，调查在测试QUIC实现时引入差异的潜在影响会很有趣。如果使用四个字节的长度0x000000ff对数据包编号0xff进行编码，会发生什么情况。

我们通过断言（即发表声明或描述公式）来转换Expected_pn = maximum_pn + 1，即使用bvadd的“位向量加”将Expected-pn必须取等于（=）的值等于maximum-pn + 1。

草案17算法指出pn_win取值1左移pn_nbits。如上所示，使用SMT-LIB bvshl操作可以轻松地将其转换为“向左移向量”。

上面，我们翻译了pn_hwin = pn_win /2。除以2等于偏移量为1的二进制右移，这在SMT-LIB中使用bvshlshr（“无符号（逻辑）右移）”实现。我们断言pn-hwin必须取等于pn_win除以2的某个值。

在上面的代码中，我们破坏了候选人_pn =（expected_pn＆〜pn_mask）|将truncated_pn转换为许多SMT-LIB表达式。我们断言候选人pn必须采用以下值的按位或（（算法中的|令牌和SMT-LIB中的bvor或“位向量或”）运算值：

（断言（或（和（和（bvule候选-pn（bvsub期望-pn pn-win））（=结果（bvadd候选-pn pn-win）））））和（（bvugt候选-pn（bvadd候选-pn pn-win） ））（bvugt候选-pn pn-win）（=结果（bvsub候选-pn pn-win）））（=结果候选-pn）））

该算法的if子句使用带有bvor的OR布尔运算实现。请注意，该算法具有3个条件（如果不满足两个第一个条件，则为2个显式条件和一个隐式条件），并带有3个不同的return语句。在这些条件下，使用SMT-LIB的bvand语句实现算法和布尔运算。 bvule和bvugt分别表示“二进制无符号数等于或小于”和“大于”。如果有任何条件匹配，我们断言我们的结果变量必须采用适当的值，例如，先前步骤中先前“计算”的候选人-pn值（候选人_pn =（expected_pn＆〜pn_mask）| truncated_pn）。

现在，我们已经使用SMT-LIB完全实现了我们的算法。我们需要确保它是正确的。草案17标准提供了一个测试用例：

例如，如果成功认证的最高数据包的数据包编号为0xa82f30ea，则包含16位值0x9b32的数据包将被解码为0xa82f9b3。

让我们使用以下值的十进制表示形式将其建模为单元测试用例：

（断言（和（和（=最大pn（_ bv2821665002 64））（= pn-nbits（_ bv16 64））（=截断的pn（_ bv39730 64））（=结果（_ bv2821692210 64）））））

在上面的代码片段中，我们添加了另一个断言，该断言描述了一个可能存在的有效状态。此状态将我们算法的不同变量绑定到单元测试用例的值。这是我们编写的必须满足的所有公式中的最后一个。

将以上命令附加到我们的SMT-LIB公式文件中。 （check-sat）请求Z3确定是否可以满足一组公式。如果可以，Z3将输出sat，并且（get-model）命令将输出Z3找到的解决方案的一个实例。否则，Z3将返回unsat。

$ z3解码.smt2sat（模型（定义乐趣pn-hwin（）（_ BitVec 64）＃x0000000000008000）（定义乐趣pn-win（）（_ BitVec 64）＃x0000000000010000）（定义乐趣pn-nbits（） （_ BitVec 64）＃x0000000000000010）（定义有趣的pn-mask（）（_ BitVec 64）＃x000000000000ffff）（定义有趣的最大pn（）（_ BitVec 64）＃x00000000a82f30ea）（定义有趣的预期pn（ ）（_ BitVec 64）＃x00000000a82f30eb）（定义乐趣结果（）（_ BitVec 64）＃x00000000a82f9b32）（定义乐趣截短的pn（）（_ BitVec 64）＃x0000000000009b32）（定义乐趣候选的pn（） （_ BitVec 64）＃x00000000a82f9b32））

Z3确实找到了与标准草案17的测试数据相匹配的解决方案！它还输出我们在模型中声明并绑定到满足我们所有公式的值的变量。这使我们对正确建模算法有信心。现在，我们可以尝试查找将触发此溢出条件的输入。

（断言（和（和（=最大pn（_ bv2821665002 64））（= pn-nbits（_ bv16 64））（=截断的pn（_ bv39730 64））（=结果（_ bv2821692210 64）））））

首先，请注意；人物介绍评论。 Z3将忽略它。然后，我们要求Z3为以前的公式找到一个解决方案，其附加条件是结果解码后的数据包编号优于2 ^ 62-1，这是QUIC标准所禁止的。

以下是在上述模型上运行Z3的输出。它显示触发溢出所需的变量，包括输入变量。

$ z3解码.smt2sat（模型（定义乐趣pn-hwin（）（_ BitVec 64）＃x0000000080000000）（定义乐趣pn-win（）（_ BitVec 64）＃x0000000100000000）（定义乐趣pn-nbits（） （_ BitVec 64）＃x0000000000000020）（定义有趣的pn掩码（）（_ BitVec 64）＃x00000000ffffffff）（定义有趣的最大pn（）（_ BitVec 64）＃x3fffffffffffffff）（定义有趣的预期pn（ ）（_ BitVec 64）＃x4000000000000000）（定义乐趣结果（）（_ BitVec 64）＃x4000000080000000）（定义乐趣截短的pn（）（_ BitVec 64）＃x0000000080000000）（定义乐趣候选的pn（） （_ BitVec 64）＃x4000000080000000））

因此，如果最新接受的数据包编号为2 ^ 62 -1，并且接收的编码数据包编号值为1或更大（具有32位数据包编号长度），则解码的数据包编号会溢出。可以说这是一个明显的失败场景。我们可以添加或更改断言以获得非平凡的情况，例如：

;;我们想要结果＆gt; 2 ** 62 -1（溢出）;;但不要作弊通过以2 ** 62-1数据包开头开始（断言（和（bvugt结果（_ bv4611686018427387903 64））（bvult最大pn（_ bv4611686018427387902 64））））

Z3然后找到以下解决方案，结果溢出到2 ^ 62-1 + 1026，最后接受的数据包号设置为2 ** 62-1-31743。

sat（模型（define-fun pn-hwin（）（_ BitVec 64）＃x0000000000008000）（define-fun pn-win（）（_ BitVec 64）＃x0000000000010000）（define-fun pn-nbits（）（_ BitVec 64 ）＃x0000000000000010）（定义有趣的pn-mask（）（_ BitVec 64）＃x000000000000ffff）（定义有趣的最大pn（）（_ BitVec 64）＃x3fffffffffff8400）（定义有趣的预期pn（）（_ BitVec 64）＃x3fffffffffffff8401）（定义乐趣结果（）（_ BitVec 64）＃x4000000000000401）（定义乐趣截短的pn（）（_ BitVec 64）＃x0000000000000401）（定义乐趣候选者pn（）（_ BitVec 64） ）＃x3fffffffffff0401））

引发QUIC数据包编号时，上溢或下溢的影响将随QUIC实现而变化。这可能包括在某些情况下（最有可能的情况–无法使用Z3枚举这些情况）解密受保护的数据包。在Z3中对RFC算法修订建模时，Z3无法找到解决方案（未饱和）来溢出解码后的数据包编号！

现代椭圆曲线密码学处理的基础字段元素太大，无法容纳在同时代的计算机存储寄存器中。例如，NSA量子后过渡阶段算法中指定的椭圆曲线P-384的模数p等于2 ^ 384-2 ^ 128-2 ^ 96 + 2 ^ 32-1，不适合a单64位寄存器。因此，必须设计一种跨越多个寄存器的数字表示形式。

许多编程语言都将任意精度算术功能作为其标准库的一部分提供。但是，它们针对一般用例和任意大的数量进行了优化，但不适用于特定曲线，因此可能无法提供最佳性能。更重要的是，这些库不适合加密操作，因为它们不太可能是恒定的，

......