本文内容是 2013 年 Google 对 packetdrill 的论文翻译。
网络协议测试很麻烦，线上的网络问题往往都是偶发的，难以捕捉。
packetdrill 是一个跨平台的脚本工具，可以用来测试整个 TCP/UDP/IP 网络栈实现的正确性和性能，从系统调用一直到硬件网络接口，从 IPv4 到 IPv6。
该工具对 Google 工程师研发 Linux TCP 中的 Early Retransmit，Fast Open，Loss Probes 这些新功能也起到了很重要的作用，并帮助工程师找到了 10 个 Linux 自身的 bug。该工具在 Google 内部进行内核研发的各个阶段都发挥了价值。
简介
网络协议在现代计算机系统中非常重要，但是在实际开发工作中，这些协议只是在部署前做一些临时的测试，并在上线后经常出各种各样的问题。宏观来说这是因为网络开发本身确实很复杂。比如 TCP 的 roadmap RFC 包含了 32 个其它的 RFC 文档。Linux 实现了其中的大多数特性。但是现在依然有新的算法涌现，并且会和既有的网络特性进行交互，在这个前提下 TCP 越来越复杂，测试起来也越来越麻烦。Google 给 Linux TCP 开发了很多特性，同时也在测试这些特性的时候面临着很大的挑战。主要是因为彼此关联的组件实在太多了：应用层，内核，驱动，网络接口和网络。基于以下原因，不得不搞一个专门的测试工具了：
- 新特性开发：给 TCP 开发新特性经常依赖在生产环境上打测试 patch，或者在模拟的网络情境下工作。要造出这些场景都非常费时间。给生产环境打 patch 风险高并且完全没法自动化，不可重复。搞虚拟的环境又非常的不现实，不一定能有真实环境的效果。
- 回归测试：虽然测试整体性能比较有用，但是基于 netperf, 或者应用压测或者生产环境的负载模拟出来的 TCP 回归测试仍然可能没办法发现一些拥塞控制、loss recovery，流控，安全，DoS 或者协议状态机方面的复杂 bug。这些过程还会受到测试环境或内容所产生的噪音干扰，并且并不准确和独立；在这种环境下也可能很难发现一些潜在的 bug。
- 问题定位：复现 TCP bug 非常有挑战，并且需要开发者去修改内核来收集相关的之间。但是生产环境修改风险过高，且需要经过多次高昂的迭代成本。需要一个专门的工具来在非生产环境的机器重现问题的 trace 流程。
packetdrill 就是基于这些原因产生的工具，可以用精确、可复现、自动化的脚本来测试整个网络协议栈。使用起来也满足设计目标：
- 方便：开发者可以快速学习 packetdrill 的语法，不需要理解 packetdrill 或者协议的内部实现。packetdrill 的语法对于脚本作者来说，可以很方便地将 packet traces 转成测试脚本。工具是实时运行，所以测试一般在一秒内也就能跑完，可以快速迭代。
- 真实环境：packetdrill 是和 packet 和 syscall 打交道的，是使用真实、精确的事件序列来测试精确的内核镜像，在物理机上是实时运行。并且和真实是物理网卡、真实的驱动、真实的线缆、真实的交换机等设备一起运行。不需要依赖虚拟机，或者用户态的虚拟机，或者模拟网络或者 TCP 的近似模型。
- 可复现：可以稳定地产生和测试脚本同样的时间序列，有较高的成功率，尽管 2500 次可能会产生一次失败。
- 通用：可以跑 IPv4，IPv6 的脚本，并且支持 IPv4-mapped IPv6 模式。可以在 Linux，FreeBSD，OpenBSD，NetBSD 上跑，跨一切 POSIX 类平台，只要平台支持 libpcap 抓包和注入库就可以。同时可以由协议的实现者用新的算法来进行扩展，因为这个库本身是开源的。
这个库本身在开发环境和生产环境中都能产生作用。开发 feature 的时候，用他来写 unit test，并使我们可以实践 TDD，增量地测试复杂的 TCP 新特性非常重要。用他来做回归测试也很简单。代码跑在生产环境以后，我们用它来做隔离和复现 bugs 也可以。packetdrill 提供了简明但准确的语言来讨论 TCP 的各种场景，可以用在 bug report 和 email 讨论时。
设计
脚本语言
packetdrill 是完全脚本驱动的，这样使其交互非常方便。packetdrill 脚本使用了我们设计的一种语言，这种语言对用习惯了 tcpdump 和 strace 的网络工程师来说应该看起来非常面熟。语言有四种语句：
• Packets, 使用了类似 tcpdump 的语法，包括 TCP, UDP, ICMP packets, 以及常见的 TCP options: SACK, Timestamp, MSS, window scale, Fast Open
• System calls, 使用类似 strace 的语法
• 用反引号包住的 shell 命令，这样可以对系统进行配置或者用 ss 之类的工具对网络栈的状态进行断言 • 用Python scripts enclosed in %{}% 包住的 Python 脚本，使我们可以进行输出或者进行 Linux 和 FreeBSD 操作系统为 TCP sockets 暴露的 tcp_info 状态断言
执行模型
packetdrill 解析整个 test 脚本，并按照脚本里的时间戳步骤来回放所有带时间戳的行，并对场景进行验证。对于每一行系统调用，packetdrill 会执行这个系统调用，并验证其是否返回了期望的结果。对于每个命令行命令，packetdrill 执行这个 shell 命令。对于每个 incoming 包(在行首用 < 来标记)，packetdrill 构造一个包并把它注入到内核。对于每一个 outgoing 的包(在行首用 > 来标记)，packetdrill 会嗅探下一个 outgoing 的包并验证这个包的时机和内容和脚本的内容相符。
考虑图 1 的脚本样例，这个例子的 packetdrill 脚本测试 TCP fast retransmit。这个测试在 Linux，FreeBSD，OpenBSD 和 NetBSD 上用真实的网卡都应该是能通过的。脚本以一个典型的打开一个 socket(1-4行)为例并建立一条连接(5-8行)。在把数据写入到 socket(9 行)后，脚本期望测试的网络栈发送一个数据包(10 行)，然后脚本让 packetdrill 注入一个 ACK 包(11 行) 让网络栈去处理。脚本会验证 fast retransmit 在三次重复的 ack 到达后会被触发。
本地和远程测试
packetdrill 有两种测试模式：本地模式使用虚拟的网络设备通道，真实模式使用物理网卡。本地模式 packetdrill 使用一台机器和虚拟的网络设备同时作为包的 source 和 sink。这样可以测试系统调用，sockets，TCP 和 IP 层，这种模式验证起来也比较简单，因为没有多台机器的交互，没有网络延迟。远程模式，用户需要运行两个 packetdrill 进程，其中一个在远程机器上运行并通过 LAN 与其它节点交互。这种流程能够验证整个网络系统：系统调用，sockets，TCP，IP 软件和硬件的 offload 策略，物理网卡驱动，网卡硬件，线缆，路由器。然而，因为要走网络交互，所以实际的时间误差会比较大，可能会导致一些随机的测试失败。
实现
packetdrill 是用 C 写的完全用户态的应用，完全遵循 Linux 内核的代码风格来方便在内核的测试环境中使用。本节深入探讨这个工具的实现细节。
组件
Lexer and Parser
为了通用性和扩展性，我们分别用 flex 和 bison 来生成 packetdrill 的 lexer 和 parser。脚本语言的结构很简单，并且包含有 c/c 风格的注释。
解析器
packetdrill 解释器开启一个单独的线程来处理事件事件的主流程，和另外一个线程来执行那些会阻塞的系统调用(比如 poll)。
Packet 事件 为了方便，脚本用一种抽象符号来标记数据包。在 packetdrill 内部会对 TCP 和 UDP 行为进行建模，维护从脚本中的值到真实数据包的映射。这个翻译过程包括 IP，UDP 和 TCP header 字段，TCP 的选项（比如 SACK 和时间戳）。因此我们会跟踪每一个 socket 和它的 IP 地址，端口号，TCP 序列号，TCP 时间戳。
对于 outbound 的 packet 事件我们会马上开始嗅探，以检测到脚本指定的包之前的任意 packet。当嗅探一个 outbound 的包时，我们会找到那个发出这个包的 socket，并验证这个包是在期望的时间被发送。然后将这个包翻译为一段等价的脚本，并用翻译后的脚本与脚本中的 bits 做等价验证。
对于 inbound 的 packet 事件，我们会暂停指定的时间，然后将脚本的值构造为一个等价的 packet，并把这个包注入到 kernel，这样我们测试的网络栈就可以处理这个 packet 了
为了嗅探流出的 packets，我们使用了 packet socket(在 linux 平台) 或者 libpcap(在 BSD 类的操作系统中)。本地模式注入 packets，我们使用 TUN 设备，远程模式注入 packet，我们用 libpcap。本地模式时，为了消费测试 packets 我们使用了 TUN 设备；远程模式 packet 会流向物理网络，并被远端的 kernel drop 掉 ，因为没有和远端 IP 地址对应的网卡(interfae)。
在 packetdrill 脚本中，一些向外流出的 TCP 包是可选的。这样可以让我们简化测试，只聚焦在单一的行为领域就行了，也简化了脚本的维护，通过避免那些协议栈的差别(与当前正在编写的测试没关系的那些网络协议栈差别)，使跨平台成为可能。举个例子，写测试脚本的时候，可以把 TCP receive window 给省略掉 ，或者用一个 <...> 的记号表示 TCP options。这里如果指定了的话，测试过程会检查；但没指定的话，测试就直接忽略这些细节了。比如在图 1 中的 <...> 用在 SYN/ACK packet 上，在各种不同的操作系统，就忽略了这里的一些细节区别。
系统调用 对于非阻塞的系统调用事件，我们会直接在主线程中调用系统调用。对于阻塞调用，我们会把事件推进事件队列，并向单独的系统调用线程发信号。主线程之后等待系统调用线程被阻塞或者完成这次调用。
在执行系统调用的时候，脚本里的那些表达式会被翻译成等价的参数，并传递给该调用。当调用返回时，会对输出进行校验，内容包括 errno 和脚本的期望输出。
Shell 命令 packetdrill 使用 system 命令来执行 shell 命令。
Python 脚本 packetdrill 执行 Python 的程序片段来记录 socket 的 tcp_info 结构体，并生成 Python 代码来导出这些数据，在测试结束后会用 Python 解析器来做结果校验。
Handling Variation
网络协议特性
packetdrill 支持很多协议特性。开发者可以在不修改脚本的情况下直接测试 IPv4，IPv6，IPv4-mapped IPv6 模式，只要用命令行 flag 指定地址模式和 MTU 大小就可以了。除了 IPv4，IPv6，TCP 和 UDP 之外，还支持 ECN 和 inbound ICMP(主要是为了 path MTU discovery)。给 packetdrill 增加那些基于 IP 的其它协议也很直接，比如 DCCP 或者 SCTP。
机器设置
我们发现很多脚本都可以共享机器的配置，因此大多脚本启动时都会调用默认的 shell 命令来配置机器参数。同时，因为脚本中的系统调用不会指定测试机器的配置，解析器会在测试期间把这些相应的值都替换成合适的值。比如，在 IPv4，IPv6，IPv4-mapped IPv6 这些协议中，我们需要选择不同的默认 IP 地址。
时间模型
很多协议对时间都很敏感，我们在脚本中支持了重要的灵活时间功能。packetdrill 强制每条语句必须带一个时间戳：如果事件没有在这个指定的时间发生，packetdrill 会触发一个 error 并报告实际事件发生的时间。表格 1 展示了 packetdrill 的时间模型。
避免随机失败
我们用 --tolerance_usecs 参数设置了 4ms 的容忍值，并持续使用了该参数长达一年，这样设置使得事件只要在我们期望时间的 4ms 范围内发生就认为测试是成功的。这也使得 1-ms 的 RTT 和 3-ms 的 RTO 能够被覆盖在内。我们认为这是基于精度和维护成本的一种折衷。已经能够帮我们找到大多数重要的时间方面的 bug，并且能够将 packetdrill 在大多数场景下不触发任何一次随机失败。
packetdrill 在内部也有一些措施来尽量减少这种时间方面的随机失败，比如让测试执行开始和内核的调度 tick 尽量对齐。控制 sleep wakeup 事件，以在一些没有常规的调度 tick 并使用实时调度优先级的 Linux kernel 环境获取到原始的 tick 值。使用 mlockall() 来尝试把内存页 pin 到 RAM，在力所能及的前提下对数据进行预计算，并在 test 结束后自动发送 TCP RST 帧，避免连接上的自动重传行为。
经验和成果
我们在 Google 生产环境机器上，使用 packetdrill 测试 Linux 内核已经有 18 个月的时间。下面我们讨论我们怎么发现这个工具很有用的。
使用 packetdrill 开发的特性
我们的团队使用 packetdrill 来测试我们在 Linux 中实现并发布的功能。成功地避免了将不计其数的 bug 推向生产环境。这其中包括 TCP Early Retransmit，TCP Fast Open，TCP Loss Probe 以及对 Linux F-RTO 实现的完全重写，我们也用它来测试 TCP 的前向纠错功能。在 packetdrill 出现之前的功能我们也进行了测试，包括 TCP 初始的窗口协商，限制 TCP 重传超时到 1 秒以及 Proportional Rate Reduction。
使用 packetdrill 找到的 Linux bug
Google 的工程师用 packetdrill 发现了很多 Linux 的 bug，感兴趣的可以去看原论文。
捕获网络协议处理的外部行为变化
Catching external behavior changes packetdrill 脚本还使我们的团队注意到 linux kernel 升级中的一些变化，虽然这学变化不是 bug，但仍然会对我们的生产环境产生一些影响，比如 timer slack，和最近修复的 packet size accounting。对于这学变化，我们也及时地对生产环境的 kernel 进行了一些适配。
测试套件
覆盖率 我们组的 9 个开发者总共写了 266 个 packetdrill 脚本来测试 Google 的生产环境的 Linux kernel 和 92 个脚本来测试 packetdrill 工具自己本身。因为 packetdrill 使开发者能够在 IPv4，IPv6，IPv4-mapped IPv6 模式下都能跑测试脚本，我们实际的测试 case 多达 657 个。表格 2 总结了我们的 packetdrill 脚本覆盖到的所有 TCP 功能。
可重复性 为了量化我们测试结果的可重复性，我们检查了过去两天在 2.2GHz 64bit 多核 PC 上跑过的所有 Google 生产环境的测试的随机失败情况。最近的 54 次 657 个测试都跑完的情况下，packetdrill 的所有测试用例中只有 14 个测试用例失败，这些都是意外的随机失败，不是程序的 bug。这说明我们的误失败率 < 0.0004，1/2500。对于我们内核组来说这是可以接受的成本。尽管如此，我们希望通过脚本的迭代进一步降低这种 test case 的误失败率。
执行时间 packetdrill 脚本执行起来非常快，所以我们在代码 review 之前会执行 packetdrill 脚本相关的测试，每次修改 Google 生产环境的 TCP 代码的 commit 都会先过一次 packetdrill 上面提到的 54 个测试，总共执行 657 个测试用例的时间是 25-26 分钟左右，平均每个 case 2.4 秒完成。
相关工具
调试和测试协议有很多工具实现如 RFC2398 categorizes late-90s 工具. Packet Shell 看起来在设计上和 packetdrill 最接近，允许脚本发包和收包来测试 TCP 节点的响应，但是这个工具是给 Solaris 系统设计的，并且已经不再公开，这个工具的设计让使用者也比较苦逼（比如你需要写 8 行 Tcl 命令来注入一个简单的 TCP SYN 包），并且不支持 socket API，不支持指定包的到达时间，不支持处理 timers。Orchestra 是一个错误注入库，能够检查 TCP 实现是否遵循了 TCP 的 RFC。这个工具是在 X-kernel 的 TCP 协议栈下又实现了一层，以执行用户指定的行为，包括 delay，drop，reorder 以及编译包的行为，结果需要人肉验证，并且测试也没法自动化，对于新的 TCP 协议栈来说比较难用。并且本身也不是为了测试目的开发的，TCPanaly 这个工具是通过分析 TCP 的 traces 来验证 TCP 的实现，诊断是否违反了 RFC 或者是否有性能问题。在 packetdrill，这种领域知识是通过脚本来建立的；但是在 TCPanaly，这些知识是通过对软件本身的理解来达成的，这种知识难以进行评审和扩展。
上面提到的这些工具都是在 1990 年代后期完成的，就我们了解到的情况，每一个工具都没有被用来测试现代的 TCP 协议栈。相比之下 IxANVL 是一个现代的商业化协议测试工具，覆盖了 TCP 的 RFS 以及一些其它的网络协议，但是和 packetdrill 不一样，这个工具扩展或者脚本化都不太容易，测试新功能也不容易且不开源。
另外一些研究怎么测试协议的结果则是用一些比较正式的语言来写一个工具，然后再用这个工具来集成到自动化测试流程中。但是这些模型为了学术化，过于严谨，维护成本很高，且不可持续，其本身和快速进化的代码也很难有效配合。还有一些工具能够自动地找到 bug，但是只覆盖了非常窄的领域，并且只能测试用户领域的代码。这些工具可以算是我们工作的一些补充。
结论
packetdrill 使得快速，准确可重现的对整个 TCP/UDP/IP 网络栈进行测试成为了可能。我们发现 packetdrill 在开发过程，回归测试以及问题定位中验证协议正确性、性能，安全方面都不可或缺。我们将 packetdrill 开源并希望和社区来分享这个优秀的工具并希望能够使互联网协议的改进更加方便。源代码和脚本可以在 http://code.google.com/p/packetdrill/ 找到。
