SDNdebugging（软件定义网络诊断故障）
1. 网络中的故障：
由于网络结构的复杂，网络中的故障不可避免的会发生。2012年北美网络管理员组织进行过一次调查，调查结果如下图：
由此我们发现其中有35%的程序员每个月遇到100+的网络故障；有35%的程序员平均花费一个小时以上的时间去调试网络中一个故障。因此开发高效的网络诊断工具是迫切必要的。目前常用的网络故障诊断工具有Ping / Traceroute/ SNMP/ Netflow/ sFlow/ netperf/ iperf 等等，然而其中很多程序员常用的网络诊断工具的效果并不是很好，并且需要程序员投入大量时间进行手动调试诊断。 更好的网络故障诊断工具需要满足更多的要求： ? ? ?
2. 控制层面上的检测诊断网络故障的最新工具
可答复性：比如回答哪一个数据包可以从A节点到达B节点？回答为什么我的数据包在传输途中丢失？
自动检测发现诊断配置故障
能够监视网络中潜在的故障：意味着除了检测错误配置故障还可以检测其他的故障。
? STS (SDN Troubleshooting System):
1. 背景
SDN提供了一种简单逻辑上集中的API（应用程序编程接口），问题是：the SDN的控制平面 (包括网络操作系统以及更高的层次) 是一个复杂的分布式系统，它必须要有对出现的各种事件如故障、主机迁移、配置策略的变更等做出的快速准确的反应的能力。事实上SDN这种分布式系统是极易引发故障的，而当遇到了一个网络问题提示我们在控制平面的软件中有个故障时，软件开发人员需要识别什么事件引发了触发了这个故障，之后才能做到分离和修复这个故障。然而Troubleshooting（故障的定位诊断与修复）过程是十分耗时的。由此STS方法应运而生。
2. 目标：
通过自动排除那些从故障路径中得到的和引起故障不相干的事件，并且找出生成引起故障的事件“最小因果序列（MCS）”，从而简化诊断的范围，最终达到来减少花费在SDN控制软件上troubleshooting的时间。
需要注意的是：我们最小化路径是基于Deltadebugging方法的, 但问题是，自然产生的bugs是十分复杂的：我们输入的不是点对点的执行文件，而是一个包含多重作用的连续序列事件。因此我们要小心的控制这些触发事件的交叉等影响，以便去通过得到的最小因果运行来复制这些故障。还有关键的是我们希望最小化故障路径，其中不需要对控制软件调试的语言和指令进行事先的假设，从而大大扩大了该方法的普适性。正是基于这个功能，STS才可以对一个黑盒系统（不管是什么语言平台）进行故障诊断工作，这也是STS工具相对于其他诊断工具的最大的优势与贡献。
为此，我们搭建了一个STS系统。每当使得一个给定的执行跟踪减少用时，存入MCS（minimal casual sequence）,开发人员开始进行调试的进程。我们可以断言，这个大大简化的故障路径记录e 使得研发人员更加容易的找出哪一部分的代码路径包含着潜在的故障，从而使他们集中精力关注这部分代码本身的问题，减少了定位故障的时间。其次，当一个故障被弥补，MCSes可以把他保存成为一个测试案例并生成一个记录，从而以后再次发生类似的故障时可以自动快速修复。
3. 问题陈述定义（Problemdefinition）：
我们把一个在特定时刻的网络转发状态称为一个配置c，其中 c 中包含着所有的此网络的转发记录以及不同网络元素的转发活跃度。控制软件包含着一个或者多个控制器进程，这些进程把一系列的外部网络事件系列C=c1,c2…
我们给出一个日志记录L（由一个集中式QAtest orchestrator产生），这个记录中包含着一系列的事件
一条openflow message）。
对一个记录L的复制意味着复制外部事件，况下C=CR。
并且可考虑可能出现的内部事
件。我们尝试把这一系列作为输入，那么输出得到的是一系列配置，，记为：CR=?1,?2.... 理想情
，其中外部
事件它们被一个混杂器
是被控制软件所触发的（比如说
（例如链路故障）作为输入，然后生成了一个网络配置
（orchestrator）插入之前的日志记录中，内部事件
我们工作的目标：对于一个给定的有违反不变量（invariant violation）的记录L，去找一个小
的、重复的事件序列来复制那个不变量违例。在形式上，我们定义了一个“最小因果序列MCS”：tM，其中外部事件EM属于tM并且EM是EL的一个子序列（且replay（tM）复制了这个violation），但是对于EM的其他的子序列EN就没有一个序列tN使得replay（tN）复制这个violation。注意到一个MCS 是不需要整体上最小的，在它中间会有EL的更小的子序列来复制这个违例，但是，这个序列一定不是MCS 的子序列。（就是说tM中没有别的子序列可以复制这个违例了！）如下图所示：
4. 方法：如何最小化路径？
对于有测试平台生成的记录L，目标是找到一个近似的MCS，从而在诊断网络故障时候，不需要检查整个记录L，而是仅仅检查MCS即可。为此，我们有两个任务：第一，在外部事件集的所有子序列中寻找引起违例的子序列；第二，决定在何时在每个子序列中插入某些外部事件，以便无论何时都可以重新触发不变量违例。
? 搜索子序列
检查外部事件集EL所有的随机的子序列，这样做是很可靠的，但问题是效率十分低下，为提高效率，我们使用Delta debugging algorithm（一个分治算法，为了分离诱导故障的输入）。我们利用这个算法去循环的选择EL的子序列，然后花费一定时间来复制这些子序列。如果一个故障出现在一个给定的子序列中，那么Deltadebugging分治算法就会忽视其他的是输入子序列，并且在这个子序列中检索“最小因果序列MCS”。DeltaDebugging算法如下Figure1所示：
但是，通过上面算法找到的输入子序列不一定都是成立的。如果没有上一个故障事件，它不能很好的复制一个修复事件；而且当之前的主机迁移事件被修改过，如果没有改变起始位置，它也不能复制一个主机迁移事件。STS方法可以支持的输入类型如下表所示;
? 时间选择
何时在复制的序列中插入外部事件是十分重要的。 Existing Approaches：
最自然的想法去对外部事件进行时序分析就是保持原始的执行时间间隔。如果这样可以找到所有的最小的机会，也就是说，给所有子序列（那些是MCS的超序列）复制违例，我们说输入是独立的。
当应用在黑箱系统如“同步通信协议”时，Delta debugging的几个最初的应用使得“每个单独的输
入对应单独的程序”和快速检查的输入变得不牢靠。尝试此方法，很难复制违例。这个考虑网络可以复制或者延时消息，或者控制器可以同时处理多个输入。按照wall-clocktime 方式插入不能保证输入和当前控制软件状态一致。
因此，必须要考虑控制软件的内部事件，为了最终可以复制这些bugs，我们需要可视化每个输入/输出要求和响应、以及每个控制器的所有的路径安排决定。
但是这些方法必须保证输入是固定的。就是说，行为必须单独的依赖于线程安排 (thread schedule)，否则，控制器可能会采用一个分散的代码路径。
另一个方法：program flow reduction technique。此种方法中，输入不再需要是固定的。然而，这个方法虽然可以最小化输入事件序列，但是这些技术不能够探索出其他的也能引起违例的代码路径。
STS中提出的方法： ?
容许发散性Allowing Divergence
这篇论文讲的方法不同于以上：STS方法允许程序沿着不同路径运行，而不是单单记录低层次的输入输出和线程安排决定。
不同于其他的好处：找到更短的其他引起故障的代码路径；对比之前的“best-effort execution
minimization techniques”虽然它也可以允许替代的代码路径，但没有系统的考虑并发性和不同步性。我们的方法也是可以避免记录I/O要求以及之后的复制的运行开销。最后，我们避免了大量的花费配置给给控制软件的语言运行时间，插入的系统调用等等，而其他的方法这些花费都是不可避免的。通过避免了控制软件的语言的假设，我们可以很轻松的把我们的系统应用在用三种不同语言编写的的五种不同的控制平台上（前面介绍的）。
?
考虑交叉存取（Accounting for Interleavings）
为了复制不变量违例，我们需要插入每个输入事件e在所有事件之后。
我们考虑的内部事件！：第一种是消息传递事件（或者是在两个控制器之间，或者是在
controller和交换机之间eg.Openflow messages）第二种是控制器之间的状态转变(备份节点决定变为主节点)我们的replay 协调器获得了（a）可视性通过在测试环境中插入所有的消息。它随机的获得了b的局部的可视性通过用简单的插入层来配置控制软件。
考虑一个子序列Es，我们的目标是找到一个遵循最初“之前发生过的”关系的执行。我们不是控制内部事件的出现，但是我们可以控制它们，当它们通过interposition layer传送时，还有，我们也可以决定什么时候注入外部事件Es。选择一个安排的最主要的挑战是最初的执行已经被修改了：内部事件在语法上可能不同了，一些期望的内部事件可能不会再发生，然后在之前最初的执行中从来没有被观察到的新的内部事件可能会发生。 ? 功能等价（Functional Equivalence）
当复制原始log的一个子序列时候，内部事件可能在语法不同(例如：控制分组的序列号可能不同)。我们观察到很多的内部事件在功能上是等价的，就是说他们对引起不变量违例时系统状态的改变有着同样的作用。例如：（。。。）
我们通过定义masks在内部事件的附加场来应用上面的观察结果。表1中我们看到我们mask的场，注意：这些masks只需要被指定一次，然后之后就可以自动编程后应用。
然后我们认为一个内部事件i’ (observed in replay equivalence)to an internal event i from the original log,当且仅当所有的没有mask的场有相同的值，and i occurs 在i‘的前项和后继输入之间in the happens-before relations
? 处理缺失的内部事件（Handing absent internal events）
有一些来自最初的记录（that happen before some external input）内部事件可能缺失！例如：如果我们修剪一个障碍链路，那么相应的通知消息就不会出现。
为了避免一直等下去，在进行复制每个子序列之前，我们推断内部事件是存在的。我们为了推断内部事件存在性提出了peek（）程序如图Figure2。
<程序功能>注入了每个输入，记录网络和控制软件状态的检查点，允许系统继续运行直到下一个输入出现，记录观察到的事件，关联这些被记录的事件与在初始路径中观察到的功能上等价内部事件。
? 处理新出现的内部事件（Handling new internal events）
最后一种可能引起的改变是在原始记录L中没有被观测的新的内部事件的发生。对于在哪里插入下一个输入，新事件呈现出多种可能。考虑下面这个例子：如果i2 和i3 是在原始运行的单个事件i1的相同等价类的，在replay中观测的内部事件，我们可以在i2或者i3之后插入下一个输入。
一般的例子下面，总是有可能搭建两种引起不同输出结果的状态机器：一种是仅当我们在一个新的内部事件之前插入下一个输入时才会引起不变量违例；另一种是仅当我们在一个新的内部事件之后插入下一个输入时才会引起不变量违例的情况。
换句话说，为了保证去遍历引起违例的任何的状态转变后缀，我们必须递归分支，为每一个新的事件尝试两种可能。这就意味着最差出现所有可能的指数数量的情况。
指数搜索太不实用，耗费巨大的时间空间。我们的启发式算法：正常的进行下去如果有一些新的内部事件，总是注入下一个输入当它上一个希望的前任或者发生或者超时。这保证了我们总是找到那些包含一个原始内部事件的子序列的状态转变后缀。
? Recap（STS方法的扼要重述）：
我们结合上面那些启发式优化方法来复制由Delta debugging选择出来的每个子序列：我们为所有的被测试协调器的干涉层拦截下来的内部事件编码等价性，之后我们调用Peek（）函数来推断缺失的内部事件，然后用这些推断的因果依赖性我们复制一个输入子序列，等待时机去插入每个输入。 ? STS的复杂度：
在调用复制函数的后的Delta debugging算法的复杂度的最好情况是Ω(log(n))，最差情况是O(n）.其中n为最初路径中输入的数量。每次调用replay要花费O(n)的时间。所以整体复杂度来说，最好情况是Ω(nlog(n))，最差情况是O(n^2)。 5. STS系统的挑战
我们假设我们得到了一个错误执行路径。我们现在提供一个综述关于如何得到这些路径然后描述我们的系统然后最小化他们。 ? 获得路径（Obtaining Traces）:
所有的三种商业SDN公司都雇佣了QA团队工程师去在网络测试平台上模糊测试他们的控制