软件测试悖论

原代码下载 TestRun0512.exe (120KB)
原文出处：Test Run：Software Testing Paradoxes

• Simpson 悖论
• Braess 悖论
• Parrondo 悖论

　　悖论很奇妙。在本月的专栏里，我将向你们展示你们进行软件测试时可能遇到的三个有趣的案例。他们本质上是数学问题，而且他们对你们的问题库是一个很好的补充。
　　在这个专栏的第一部分，我解释 Simpson 悖论。该悖论阐述的是这样一种情况：软件系统 A 与软件系统 B 相比，各方面都要差，然而软件系统 A 可能是一个更好的系统。 在第二部分，我揭示了 Braess 悖论。根据这个悖论，当增加一个完全负载平衡的服务器时， 络性能会以一种奇怪的方式降低。最后，我考虑了 Parrondo 悖论。这个悖论认为两个相互独立并且是错误百出的系统能够不可思议地产生一个正确的系统。
　　Simpson 悖论经常发生。虽然你实际碰到 Braess 悖论和 Parrondo 悖论的机会很少，我还是认为你们会有兴趣读它们。

Simpson 悖论

　　假设你有两个不同的软件系统原型：原型 A 和原型 B 。你想知道从用户的反馈来看，哪个原型更好。假设对于易用性，原型 A 从 200 个用户当中获得了 50 个用户的优秀评价，而原型 B 从 100 个用户中获得了 15 个用户的优秀评价（见图 1 ）。从这个数据来看，原型 A 的易用性显然要比原型 B 要好，因为原型 A 获得了 25% 的优秀评价，而原型 B 只得到了 15% 。
　

图1 比较原型A和原型B

　　现在，假设对于安全性，原型 A 从 100 个用户当中获得了 85 个用户的优秀评价，而原型 B 从 400 个用户中获得了 300 个用户的优秀评价。对于这个数据，你能看到原型 A （ 85% 的优秀率）再次比原型Ｂ（ 75% 的优秀率）要好。因此，你认为哪个原型要好回答之前，让我们把图 1 中的数据整合到一个单独的表格当中（图 2 ）。

图2 安全性、易用性整合数据

图3 整合后的研究生院录取数据

图4 原始的研究生院录取数据

　　Simpson 悖论从数学上来说确实不是一种真正的悖论。一个数学悖论产生一个逻辑上不一致的答案，而 Simpson 悖论的结论是奇怪的、意料之外的，但是却是能够得到解释的。如果你想深入研究， 上有很多关于 Simpson 悖论的资料。给我们的启示是，当你检查测试结果数据的时候，你要先怀疑这些数据是不是从其他原始资料整合而来的。如果是，那么你应该看看原始未经整合的数据。另外，如果你在产生一个测试数据 告，当你尝试要整合数据以便简化你的阐述时要相当仔细。有人说“统计能用来说明任何你想要的”，这种情况正是它们说提及的。

Braess 悖论

　　现在来看看 Braess 悖论。我的例子使用了一个传统场景——汽车交通，但是我描述了这个悖论是怎样扩展到软件测试和其他情况的。关于 Braess 悖论的原始工作是 Dietrich Braess 的“ über ein Paradox der Verkerhsplannung ”（ 1968 ）。而我的例子，是基于我发现的几个例子，这几个例子对 Mark Wainwright 的工作作出了贡献。当时我不能亲自参加到 Wainwright 的原始工作中。
　　Braess 悖论相当复杂，所以这里我给一个简化的、离散近似。假设象图 5 中显示的一样有四个城镇——城镇 A ，城镇 B ，城镇 C 和城镇 D 。
　　连接任意两个城镇之间的每一条路都有一个关联成本，由图中与路相邻的方程给出。成本是陆上汽车数的函数。你能想象成本代表了在这条路上行驶所需要的时间，或者所需要的汽油，或者你们想要最小化的某些因素。现在假设某一个早晨，有 6 辆车从城镇 A 离开，每次一辆，目的都是城镇 D 。汽车 1 离开的时候，路上完全是空的。该车可以从两条路径中选择： A-B-D 和 A-C-D 。 A-B-D 的成本是 [4(1) + 1] + [1 + 16] = 22 。由于该图的对称性，路径 A-C-D 的成本也是 22 。假设汽车 1 选择了路径 A-B-D 。

　　现在汽车 2 准备离开了。他看到汽车 1 在路径 A-B-D 上，因此知道了现在 A-B-D 上的成本是 [4(2) + 1] + [2 + 16] = 27 ，所以他选择了成本只有 22 的路径 A-C-D 。汽车 3 看到每条路径上都有一辆车，所以选择了成本是 27 的路径 A-B-D 。汽车 4 选择了成本是 27 的路径 A-C-D 。汽车 5 看到四辆车是均匀分布的，他选择了路径 A-B-C ，成本是 [4(3) + 1] + [3 + 16] = 32 。最后，汽车 6 选择了成本是 32 的路径 A-C-D 。现在所有六辆车都在从城镇 A 到城镇 D 的某一条路径上。因为每一条路径上有三辆车，而两条路径是对称的，每辆车的成本是 32 。
　　这是 Braess 悖论出现的地方。如果在城镇 B 和城镇 C 之间增加一条新的、有效的路径，你认为会出现怎样的结果是，增加道路容量会降低司机们的成本。但是既然这种现象被叫做“ Braess 悖论”而不是“ Braess 常识”，你应该猜到实际发生的并不是如此。
　　假设修改图 5 中的地图，在城镇 B 和城镇 C 之间增加了一条高效快捷路径，它的成本函数是一个常数 1 。在加入了快捷路径的第一个早晨，汽车 1 准备离开城镇 A 。他有四种可能路径选择，各条路经的关连成本如下：

　　这是很有希望的。汽车 1 选择了路径 A-B-C-D ，通过快捷路径来显著降低他的交通成本——至少暂时如此。汽车 2 准备离开了。他看到汽车 1 选择了路径 A-B-C-D ，于是分析他的可能成本：

　　经过快速数学计算之后，汽车２页选择了路径 A-B-C-D 。尽管汽车 1 已经在这条路径上了，快捷路径的有效性仍然使得它是汽车 2 的最好选择。

现在汽车 3 准备离开了，他的选择是：

再次，这个快捷路径 A-B-C-D 是最好的选择。汽车 4 准备离开城镇 A ，观察了钱三个司机的决定，算出了他自己的成本：

　　快捷路径上目前的交通使得 A-B-C-D 比路径 A-B-D 和 A-C-D 的成本要高。假设汽车 4 选择了路径 A-B-C （如果汽车 4 选择了 A-C-D ，细节会有一点不同，但是总的结果是一样的）。

汽车 5 现在准备离开了，他分析了他的选择：

因此汽车 5 决定选择路径 A-C-D 。最后一辆车，汽车 6 ，现在准备离开了，他观察了前面 5 个司机的决定，做出了他自己的分析：

汽车 6 选择了路径 A-C-B-D ，因为这是成本最低的。现在 6 辆车都在路上了，你可以算出每辆车的成本。

回忆一下，如果没有这条快速路，每辆车的成本是 32 。现在增加了额外公路容量，我们却增加每个司机的成本！

　　这个例子提供了一个对 Braess 悖论的实际接触。因为这和 络系统上所传输的数据包有明显的关系， Braess 悖论受到了研究人员的深入研究。你能非正式的总结这个悖论：有时候增加节点之间的路径数反而会增加 络拥塞。从软件测试角度来说， Braess 悖论会在进行 络性能测试的时候出现。老实说，你碰到 Braess 悖论的机会很少。但是这个现象确实存在。启示是，你不应该假设增加 络容量就会提高性能。如果你增加了容量但是没有看到你所期望的性能提高， Braess 悖论就是应该去调查的。

Parrondo 悖论

　　本质上， Parrondo 悖论陈述的是两个要输的赌博游戏（我们称他们为游戏 A 和游戏 B ），它们可以被设计好，这样如果一个接一个地玩，它们可以成为赢得游戏。有很多方法可以构造 Parrondo 悖论的例子，最简单的事使用三个有偏差的硬币。
　　游戏 A 是一个简单的掷硬币游戏。你掷出一枚硬币，如果硬币正面朝上，你赢 1 元，如果硬币正面朝下，你输 1 元。硬币 1 稍微有点偏差，这样它正面朝上的概率是 p1=0.495 （故正面朝下的概率就是 1-p1=0.505 ）。如果你不停的玩这个游戏，你最终会输钱。游戏 B 有点复杂，使用两个硬币。这个游戏中的第一个硬币（硬币 2 ）有一个赢（正面朝上）的概率 p2=0.095 。这是一个很糟糕的硬币。第二枚硬币（硬币 3 ），有一个赢的概率 p3=0.745 。这是一个很好的硬币。
　　你从一定数目的钱开始玩这个游戏，例如 300 元。为了玩游戏 B ，你需要两个步骤 : 先要检查你的钱数是否是 3 的倍数（例如 300 元、 297 元、 303 元等等）。如果你目前的资金是 3 的倍数，你掷硬币 2 ，要不是赢 1 元就是输 1 元。如果你目前的资金不是 3 的整数倍，你掷硬币 3 ，赢 1 元或输 1 元。尽管不是很明显，如果你不停的玩游戏 B ，你还是会输钱。
　　在这一点上，我们有两个要输的游戏。如果我们按照一种随机模式或者是固定模式来玩游戏 A 和 B ，你认为会发生什么惊奇的是，如果一起玩，这两个要输的游戏最后会赢！本专栏附带的代码给出了一个用 C# 写的仿真。图 6 是运行这个程序的一个屏幕截图。

　　这个游戏是由西班牙心理学家 Parrondo 创造的。 1999 年， G.P.Harmer 和 D.Abbott 发表了文献“ Losing Strategies Can Win by Parrondo”s Paradox ”，以 Parrondo 给这个悖论命名。从那以后，在这个游戏和它的变种上出现了很多的研究，包括改变三个硬币的概率影响和改变玩游戏 A 和 B 的模式。
　　现实中，你碰到 Parrondo 悖论的机会是很少的。在一种牵强的场景中，你由一定数目的进程优先级（与 Parrondo 悖论中的资金相对应）开始，你有一个子过程会根据 CPU 的使用情况提高或降低进程优先级（与游戏 A 对应），你也有另外一个子过程会根据目前的优先级而提高或降低进程优先级（与游戏 B 对应）。这两个子过程都设计为概率上最后都会降低进程优先级。然而，当这两个过程被反复调用，它们实际上会提高进程优先级。诚然，这只是一种扩展，然而 Parrondo 悖论太有趣了，我忍不住在这个专栏中介绍它！
　

http://www.yeeyan.com/articles/view/20618/10894g_related

http://hi.baidu.com/laladu/blog/item/c2abe6dd2f1411ea76c638cd.html