Zeng H , Kazemian P , Varghese G , et al. Automatic test packet generation[C]// International Conference on Emerging Networking Experiments & Technologies. IEEE, 2012.

背景分析

当前特别需要自动化的网络测试工具

概念

• packets
• Switch
• Rules：defines how header space at ingress is transformed into regions of header space of egress.
• Rule Historyt:包被传送过程中记录自己所经历过的规则。
• Topology:拓扑结构

测试包生成算法过程

step1:生成一个all-pairs reachability table

举个例子：

图6所示，如果在$P_A$处注入all-x test packets,包会通过A传递，它会将10.0/16发送到B，将10.1/16发送到C，B再将10.0/16,tcp=80发送到$P_A$,C发送10.1/16到$P_C$，在表4第一行可见。

step2:抽样，抽取测试包，使每一个rule都会被至少一个包测试到。 step3:压缩，找到一个最小的测试包集，它们的rule history可以覆盖所有的rule(经典的最小集覆盖问题，可由贪心算法求得。)

错误定位算法

基本定义

定义：R(r,pk) = 1,(包pk在规则r下成功验证) 否则 R(r,pk)=0 包在规则下验证失败有两种情况：行为错误，包头匹配错误，这里只考虑行为错误（包被错误地处理）。我们只能在边缘观察到包，所以重新定义： $R(pk)=\left{ \begin{aligned} 0 && if\ pk\ fails\ 1 && if\ pk\ succeeds \end{aligned} \right.$

算法过程

• 假设1（错误传递）：R(pk) = 1 if and only if $\forall r \in pk.history,R(r,pk)=1$.
• 问题2（错误定位）：对于一个给定的元组列表：$(pk_0,R(pk_0),(pk_1,R(pk_1),\dots$，找到所有的r，满足$\exists pk_i,R(pk_i,r)=0$。 step1:找到可疑规则：所有通过的规则集P，失败包的规则集F，F-P即为可疑规则。 step2:缩小可疑规则集：重新发送所有包含可疑规则的测试（该包不在上述的测试包中）包，若通过，则将该规则移出可疑规则集。 step3:获得更小的可疑集后，报告可疑集。

测试用例

功能测试

• 交付规则：包通过该规则，并从正确的端口离开
• 链路规则：包正确地通过链路，并且包头未被修改
• 丢弃规则：将这种测试包进行广播，若在接收终端接收到，则失败。

性能测试

阻塞：对每一对终端进行延迟测量，若延迟大于某个阈值，则定位延迟链路。 可用带宽：对每一个链路，队列，或服务类构造测试包进行测试（iperf/netperf或其他测试方法），可用带宽不应低于某一阈值。 严格的优先级：利用测试包阻塞低优先级类，再测试高优先级类，其带宽不应变化。

实现

测试包生成

使用python编写测试包生成器生成All-pairs reachability包，并用Min-Set-Cover算法获得包含所有测试规则的最小测试包。

网络监控器

假设前提是网络上有测试代理，网络监控器构造测试包，并指导代理发送测试包，代理通过IP proto域或TCP/UDP端口号区分测试包。如果测试失败，则从保留包集中选择其他测试包来定位错误。

可选实现

• Cooperative routers:利用路由器发送测试包。
• SDN-based testing:controller可以控制路由器发送测试包。

evaluation

在i7,3.2GHz,6G memory，8线程运行ATPG工具，在stanford 和Internet2两个网络中进行测试。 规则重复率的累积分布函数：

在模拟网络中测试

使用mininet模拟网络，并使用仿真主机发送和接收由ATPG生成的测试包。

• 交付错误：手动替换交付规则观察结果
• 阻塞：限制链路30M/s，创建两个20M/s的UDP flow观察吞吐量，如图9左下，延迟如图9右下。
• 可用带宽：使用之前的链路，把UDP流降低至20M/s,并使用Pathload监控链路带宽，可以找到该链路瓶颈：bbra-yoza。
• 优先级：重复阻塞实验，当低优先级阻塞时，高优先级测试不受影响，高优先级阻塞时，均阻塞。