0 引言

随着网络技术的发展和用户需求的不断增加，越来越多的服务需要在网络中部署。在传统网络中，设备制造商需要对每个设备进行升级改造，这导致新的网络服务和功能在网络中部署难度大、成本代价太高。软件定义网络(Software-Defined Network，SDN)^[1]则有望改变这一现状。SDN主张解耦控制面和转发面，通过提供开放的可编程接口和控制器集中化的管理，大大降低了网络的复杂度，使得网络便于管理。控制面把握全局网络状态，灵活地调度资源使网络状态达到最佳。然而，SDN在带来优越性的同时也带来了许多新的问题，如控制器的性能^[2]、网络的可扩展性^[3]、安全性问题^[4]等。

SDN的结构赋予了控制器管控全局的能力，对上通过北向接口接收上层应用提供的策略及为上层应用提供网络视图，对下通过南向接口获取全网的网络视图和下发流规则给转发设备。因此，控制器在SDN中至关重要，它的故障对网络的影响将是毁灭性的。当前控制器的可靠性保证主要是通过冗余的方式实现，但是冗余控制器间存在很强的同构关系，相同的攻击很容易再次发生。此外，交换机和控制器间静态的映射关系，使得攻击者可以不断收集网络信息以满足攻击需求，造成攻击者和防御者之间极大的不对称性。

针对上述问题，本文提出了多控制器同时管理交换机的结构，但是多控制间存在拜占庭错误^[5-6]。借鉴分布式系统领域解决拜占庭错误的方法，将拜占庭容错(Byzantine Fault-Tolerantce, BFT)算法引入SDN环境下，并导入动态性和异构性，加大了攻击者对控制器的认知和攻击难度。所提结构中，多个异构控制器同时给交换机下发流表，并通过裁决代理选出最可靠的流规则下发给交换机，有效地增强了控制层面的安全性。

1 相关工作

SDN控制层的安全问题备受研究者的关注，开放网络基金会(Open Networking Foundation, ONF)在SDN安全分析^[7]中利用微软的STRIDE威胁模型分析了控制层的安全问题，文献[8]则从认证、数据安全性、拒绝服务等方面综述了SDN安全问题，几乎所有问题都与控制层相关。

文献[9]实现了基于分布式文件系统实现的多控制器结构HyperFlow，通过发布与订阅交互方式实现了多控制器之间的通信，解决了控制面单点失效和扩展性的问题；文献[10]引入了密码学的多方计算技术，把敏感信息放在多个控制器，实现协同计算，这种方法确实保证了某些信息的泄露不会造成全局的崩溃，但实现起来较为复杂；文献[11]从控制器的部署方面考虑提高SDN的可靠性和恢复能力；也有文献利用移动目标防御的思想增强SDN的抗攻击能力，但频繁的变化对网络的性能造成一定的影响^[12]。上述研究从不同的方面强化了SDN的安全性，但是这些方法只能处理控制器的可见故障问题，无法处理一些隐性故障。

文献[5]提出了多控制器协同工作实现容错，控制器之间不再是主从关系。控制面能够容忍一定数量的控制器故障而不产生错误，但是文献的关注点是最小化控制器的数量，没有考虑控制器之间的同构问题和算法可能造成的性能问题。一般情况下，一组同构冗余的组件，攻击者只要能成功攻击一次，就可以用同样的方式实现所有组件的攻击，这对网络的可靠性和可用性造成了极大的威胁。

2 基于BFT协议的SDN结构

BFT协议主要用于解决系统中出现的随意性错误问题，通过冗余体之间的信息交互和主节点的判决，使得有限冗余体的故障和攻击可以被屏蔽，并且提供异常的检测和恢复机制，在文件系统中应用比较广泛^{[6, 13]}。本章主要描述引入拜占庭协议的SDN结构和拜占庭算法的基本过程。

2.1 基于拜占庭的SDN结构

在传统的SDN结构中，一个交换机只由一个控制器下发流表项，而在本文所提的结构中，交换机由多个控制器同时管理，所有控制器都给交换机下发流表项，通过对这些流表项的裁决，选出最合理的流表项下发给交换机。本文所提结构如图 2所示，上层为控制层，中间为代理，下层为转发层。通过多个控制器同时管理交换机和结果的统一裁决，可有效防止某些控制器已知或未知的漏洞后门被利用，同时可以防止某些控制器上恶意应用产生的恶意规则被下发。由于OF(OpenFlow)交换机并没有裁决或是归一化处理的能力，因此控制器之间的协同、数据的归一化处理以及结果裁决需要另行解决。修改交换机或控制器或OpenFlow协议的复杂性和成本都很大，考虑在控制面和数据面之间加入一个代理(类似FlowVisor)来实现必要的数据和逻辑处理。代理主要实现以下功能：1) 对控制器视图的隔离；2) 对请求的分发；3) 对流表项的处理；4) 对结果的逻辑判决。交换机把请求通过代理分发到所有的控制器，控制器对交换机的请求进行处理，控制器之间通过拜占庭协议通信，代理对结果进行判决，若通过则把结果下发到交换机，否则不作响应。

2.2 工作流程

为了要容忍f个控制器故障至少需要提供3f+1个控制器^[6]。这些控制器构成的集合称为控制器视图，简称视图。视图中有一个主控制器和若干冗余控制器。工作流程如图 2所示。

具体步骤如下：

1) PRE-PREPARE阶段：交换机通过代理向所有的控制器广播OF请求〈REQUEST, o, t, of〉_αc，各控制器将其相关信息写入日志，控制器之间推选出一个控制器作为主控制器。主控制器广播PRE-PREPARE消息〈PRE-PREPARE, v, n, D(of)〉_αp给其他控制器，这个消息包含该请求的编号n、视图号v、消息摘要D(of)。

2) PREPARE阶段：若各冗余控制器接受主控制器分配的编号n，则进入PREPARE阶段。各个控制器广播PREPARE信息〈PREPARE, v, n, D(of)〉_αi给其他控制器，并把相关信息写入日志。

3) COMMIT阶段：对每一个控制器，如果其接收到了2f个与n、v、D(of)相匹配的PREPARE消息，则该控制器进入COMMIT阶段，对外广播COMMIT消息〈COMMIT, v, n, i〉_αi。

4) 各冗余控制器等待2f+1个来自不同控制器的COMMIT消息，验证n、v等信息。若正确，则处理该OF请求，并把处理的结果通过REPLY消息〈REPLY, v, t, of, i, r〉_μis发送给代理。

5) 代理判决接收到的消息，如果接收到来自f+1个不同控制器的相同处理结果，则把该消息传递给交换机，否则丢弃消息。

2.3 视图切换

当主控制器失效或异常控制器数量超过f时，要保证拜占庭协议的正常执行，需要重新选择控制器视图并重新选择主控制器，这一过程称为视图切换。图 3描述了从视图v到视图v+1的切换过程。切换过程如下：当冗余控制器发现主控制器失效时，广播视图切换消息到所有控制器，各控制器回复确认消息到新视图的主控制器(一般为第一个发现异常的控制器)，只要主控制器收到3f个确认消息后，就向所有冗余控制器发送新的控制器视图信息。同时，需要从资源池中选出新的控制器加入到视图，接替异常控制器的工作。

为了打破交换机和控制器间的静态性，设置了一个计时器，保证在有限时间内，动态地发生视图切换，切换时间间隔T动态生成，T=T₀+rand(5) *Δt。

3 控制器视图选择

在新结构中，每一个交换机都需要一个控制器视图对其进行管理，本章主要研究视图的选择问题。

定义1 不考虑控制器的性能差异，只考虑结构上和实现上的差异，用一个四元组表示控制器，即(语言，算法，存储，平台)。这里的语言是指控制器实现的语言，如Java、C++、Python等，用L表示；算法是指控制器内部执行某些功能实现的算法，用A表示；存储是指控制器使用的数据库，如事务型数据库、键值对数据库、面向文档数据库等，用B表示；平台是指控制器依赖的操作系统，用T表示，如Windows、Linux等。因此，控制器可建模为一个四元组c_i:(l, a, b, t), l∈L, a∈A, b∈B, t∈T。

定义2 在信息论中，两个等长字符串之间的汉明距离(Hamming distance)是两个字符串对应位置不同的字符个数。例如：L={Java, C++, Python, C#}，编码为{0, 1, 2, 3}，同理对A、B、T编码，则c_i编码为(x_i0, x_i1, x_i2, x_i3)，c_j编码为(x_j0, x_j1, x_j2, x_j3)。考虑到每一种属性的重要程度不同，为每一种属性设置一个权值，分别为λ₀、λ₁、λ₂和λ₃，满足$\sum\limits_{k = 0}^3 {{\lambda _k}} = 1$，定义加权汉明距离为$\sum\limits_{k = 0}^3 {{\lambda _k}({x_{ik}} \oplus {x_{jk}})} $，其中⊕表示异或运算。

定义3 视图异构度。$I = \sum\limits_{{c_i},{c_j} \in C} {\frac{{lad{p_{ij}}}}{{{v_C} + 1}},\;} lad{p_{ij}}$表示控制器c_i和c_j之间加权汉明距离，v_C表示视图中两两控制器间加权汉明距离构成的向量的方差。这里将加权汉明距离的总和除以方差v_C的目的是防止控制器间异构性差距较大而造成整体的不均匀性，方差v_C加1的目的是防止方差为0造成公式失去意义。

3.1 网络建模

把网络拓扑建模为一个有向图G(V，E)，V表示网络中节点，包括控制器和交换机，E表示拓扑中的链路。S表示交换机集合S={s₁, s₂, …, s_m}，C表示控制器集合C={c₁, c₂, …, c_n}，|V|=|S|+|C|，其中| |表示集合中元素个数。记上层控制器c_j和c_k之间的通信时延为L_jk，由于下层交换机承担的数据流量不同，重要程度有所差异，所需容忍控制器错误的个数也不同，容忍的时延也不同，用f_i表示交换机i能容忍控制器出错的个数，δ_i表示交换机容忍控制器时延的上限。Φ_i表示交换机i分配的候选控制器集合，固定该集合大小为h，即|Φ_i|=h。D_i表示交换机i分配的控制器集合，即控制器视图。

本文通过动态异构冗余的结构来提高控制层的抗攻击能力，为了使控制器间的共性特征降到最低，选择异构度最大的视图，从而保证攻击者对每一个控制器的攻击是独立的，增大攻击者协同攻击的难度，并且使网络有更长的时间去检测出异常和恢复被攻击的控制器。

控制器间通过拜占庭容错协议通信，而拜占庭容错协议的一个很大的缺点就是控制器之间要两两交互，控制器间的最大时延会直接影响到网络的性能，为了最大化网络的性能，选择最近的控制器作为主控制器。在实际问题中，交换机和控制器之间的时延要远小于控制器之间的通信时延，因此这里仅考虑控制器之间的通信时延。为了保证网络的可用性，需满足∀s_i∈S, ∀c_j∈D_i, D_i⊂Φ_i，L_jk≤δ_i；为了满足交换机需要容错数量的要求，要保证∀s_i∈S, h≥3f_i+1, |Φ_i|≤h。因此可将问题建模如下：

目标函数：

${I_i} = \max \sum\limits_{{c_k},{c_j} \in C} {\frac{{lad{p_{jk}}}}{{{v_{{D_i}}} + 1}}} $

(1)

约束条件：

$\forall {s_i} \in S\;,\forall {c_j} \in {D_i},{D_i} \subset {\mathit{\Phi }_i},\;{L_{jk}}\; \le \;{\delta _i}\;$

(2)

$h\; \ge \;3\mathop {\max }\limits_{{s_i} \in S} {f_i} + 1$

(3)

$|{\mathit{\Phi }_i}| \le h,\;\forall {s_i} \in S$

(4)

3.2 模型求解

显然，这是一个NP难问题。把模型求解工作分为两阶段：1) 为每个交换机求解满足时延的候选控制器集合；2) 在候选控制器集合中选择最大异构度的视图。

3.2.1 候选控制器集合求解

借鉴文献[5]中的算法，设计了如下算法求解候选控制器集合。

算法1 候选控制器选举算法。

Input: G(V，E), n，δ_i，h

Output: Φ={Φ_i|1≤i≤m}

1)   C^*=∅，Φ=∅；

2)  for i= 1 to m do

3)  if C^*=∅ then

4)  C^*←c_ip；

5)  ${t_{\min }}\; = \mathop {\;\min }\limits_{{s_i} \in {S_i}} {\delta _i}$；

6)  C^*←find_cs(C, C^*, t_min, h)；

7)  end if

8)  将C^*中控制器的剩余容量按照从小到大的顺序排列:C^*={c_*1, c_*2, …, c_*h}，k_*1≤k_*2≤…≤k_*h；

9)  if k_*1>0 then

10) for j=1 to h do

11)  Φ_i←c_*j；

12)  k_*j=k_*j-1；

13)  end for

14)  end if

15)  C^*=∅；

16)  C←C-C^*；

17)  S=S-s_i；

18)  end for

算法1的输入是网络拓扑情况G(V，E)，控制器的数量n和每个交换机的最大容忍时延δ_i，候选控制器集合大小h；输出是候选控制器集合Φ={Φ_i|1≤i≤m}。算法的说明如下：首先，判断集合C^*是否为空，若为空，则通过find_cs函数计算C^*(行3) ~7))，其中C^*是候选控制器集合，初始化为空(行1))。在计算C^*时，将交换机i的主控制器c_ip放入C^*(行4))，其中主控制器的选择遵循最短时延的原则。计算所有交换机的时延上限的最小值，将该值作为时延判断标准(行5))，则C^*中的控制器可适用于所有的交换机。接着将C^*中控制器的剩余容量递增排序(行8))，然后顺序添加到交换机的候选控制器集合中(行11))。为简化计算，只要C^*中的最小容量控制器的剩余容量为0就重新计算C^*。行16) 是从C中把C^*去掉，行18) 是把完成分配的交换机从交换机集合中移除。

函数find_cs。

1)   function find_cs(C, C^*，t_min，h)

2)  for c_i∈C={c₂, c₂, …, c_n} do

3)  if对任意c^*∈C^*有L_{ci, c^*}≤t_min且k_*i=k_i then

4)   T=find_cs(C-{c_i}, C^*+{c_i}, t_min, h-1)；

5)   if |T|=h then

6)    return T；

7)  end if

8)  end if

9)  end for

10)  return C^*；

11)  end function

函数find_cs是从初始化控制器集合中选出满足交换机时延要求的控制器集合，通过递归的方式计算集合C^*(行4))。函数的输入参数h是所需控制器的数量，递归的退出条件是选出的控制器的数量达到h(行5) ~6))，函数的返回结果是控制器集合C^*(行6))。第10) 行是在找不到控制器集合的情况下把原始输入的C^*作为输出，保证函数的完整性。

选举算法的时间复杂度是O(mn²)，最坏的情况是需要调用find_cs函数找新的控制器集合，函数时间复杂度是O(mn^h/k)，m是交换机的数量，n是控制器的数量，h是候选控制器集合大小，k是最小控制器容量大小，由于候选控制器集合大小一般不超过10，算法的时间复杂度是可接受的。

3.2.2 控制器视图求解

由于h的值较小，可以利用穷举的方法计算出异构度最大的视图。视图选举算法的伪代码如算法2。

算法2 视图选择算法。

Input:Φ, f，h

Output: D={D_i|1≤i≤m}

1)  for i=1 to n do

2)  从Φ_i中选出3f_i+1个控制器组合，计算各组合的视图异构度，${I_{{q_i}}}\; = \;\sum\limits_{{c_i},{c_j} \in C} {\frac{{lad{p_{ij}}}}{{{v_{{D_i}}} + 1}}} $；

3)  ${D_i}\; = \;\mathop {\max }\limits_{{q_i} \in Q} {I_{{q_i}}}$；

4)  end for

算法的输入是每个交换机的候选控制器集合Φ，候选控制器集合h和每个交换机的容忍控制器失效的个数f={f_i|s_i∈S}，输出为交换机最终分配的控制器视图。从候选控制器集合中选择选择3f_i+1个控制器，共C_h^3f_i+1种可能性，所有情况的集合记为Q，通过计算，选择最大异构度的视图分配给交换机(行2)、3))。

4 仿真分析 4.1 仿真环境

本文利用Mininet和Matlab R2016a进行模拟仿真验证SDN中多控制器和交换机利用拜占庭算法实现多对多的交互。选用Internet2的OS3E^[14]作为网络拓扑，其共有39个节点，拓扑如图 4所示。

本文作如下假设：1) 控制器选用的语言、算法、数据库、平台等具有同等的安全性和性能，或者差异不大。2) 每个控制器的容量相同。3) 每个控制器失效的概率均为p。把控制器失效的原因归结为停机故障和拜占庭故障，假设故障是拜占庭故障的概率为p_b，则发生拜占庭故障的概率就是p*p_b。4) 所提供的控制器的数量满足算法需求。5) 取T₀=15 min，Δt=4 min，λ₀=0.2，λ₁=0.3，λ₂=0.1，λ₃=0.4。

拓扑中部署39个交换机和若干控制器，交换机和其控制器视图通过中间代理连接，控制器间执行拜占庭协议，通过评估交换机的失效数量来评估网络的抗攻击能力，即失效的交换机个数越少，抗攻击能力越强。

4.2 仿真结果分析 4.2.1 抗攻击性分析

传统结构中，由于同构的关系，攻击者对不同控制器的攻击具有一定的参考性，降低了攻击的难度。然而，在所提的结构中，控制器的选择是动态异构冗余的，攻击者认知和攻击控制器的难度都大大提高。要使控制器层失效，至少要f+1个控制器失效，成功的概率可表示为$\sum\limits_{{C_{f \in C}}} {\prod\limits_{i \in {C_u}} {(1 - {p_j})} } \prod\limits_{j \in C - {C_u}} {{p_j}} $。其中:C_f表示一个交换机的控制器视图中的控制器故障数大于f的所有情形; C_u表示未发生故障的控制器集合, u=1, 2, …, n，n是控制器个数; p_j表示控制器失效的概率。

如图 5所示，可以发现，随着控制器数量的增多，交换机失效的概率逐渐降低。如果控制器被成功攻击的概率足够小，只要有限的异构控制器就能保证SDN对抗外部攻击的能力，这说明采用异构冗余的拜占庭协议提高了SDN的抗攻击能力。

为了量化异构拜占庭协议的抗攻击能力，利用交换机的失效个数度量抗攻击能力。从上面的描述可以看出，发生拜占庭故障的概率与p_b和p有关，下面分别验证了在p_b=0.8时失效交换机个数与p的关系，以及在p=0.2时失效交换机个数和p_b的关系，如图 6和7所示。这里比较了主从切换(primary-backup, 后面简记为p-b)方法和f=1, f=2, f=3(为了简化说明，每次视图切换过程中控制器个数保持不变，即容错个数f_i保持不变，简记为f)共四种情况。为了让实验结果更可靠，重复了1000次实验，算法中取h=10，计算失效交换机个数(usn)的平均值作为最终结果。

从图 6可以看出，在p_b为定值的情况下，无论是主从切换方式还是基于拜占庭协议，失效交换机的个数均随控制器故障概率的增加而增加，因为无论什么样的机制都无法应付控制器自身较大的故障率，这些机制只是在一定的故障率范围内，尽量降低出错的概率。比较四种情况可以看出，在同等的概率p下，主从切换的方式失效交换机的个数最多，随着容忍限度f的增大，失效交换机的个数明显减少，说明采用异构冗余的拜占庭协议后，SDN的抗攻击能力明显提高。

从图 7可以看出，在p为定值的情况下，随着拜占庭故障率的增大，传统主从切换的方式下，交换机可能全部失效，因为主控制器发生拜占庭错误后很难检测出来，这将导致所有向其发出请求的交换机失效。相反，在采用了拜占庭协议后，交换机的失效与拜占庭错误率无关，这说明拜占庭协议可有效应对拜占庭错误，而且拜占庭协议的容错数量越大，出错的交换机个数越少，容错能力越强。

在p=0.15时比较了主从切换、同构和异构情况下被成功攻击的概率，结果如表 2所示，可以发现，异构的情况明显优于其他两种。

4.2.2 部署开销分析

为了测试应用BFT协议的部署开销，将其与单控制器结构相对比，两种情况下传输OF请求的平均时延如图 8所示。从图 8可以看出，应用BFT协议增加了一定的时延开销，额外的时延有两个原因，一部分是BFT协议的交互时间，另一部分是代理层的请求分发和结果裁决时间，这两部分时间使时延开销平均增加了近40 ms。第一部分时延与控制器实际的地理位置也有很大的关系，取决于控制器和交换机的最大通信时延；第二部分时延与控制器视图大小有关，时间取决于结果到达的最迟时间和采用的裁决算法。总的时延在90 ms左右，拜占庭协议对网络性能的影响可以接受，能满足网络服务的质量要求。

为了比较控制器的部署数量，在相同规模下将本文所提算法(proposed)与主从结构(p-b)、文献[5]的RQFA(Requirement First Assignment Algorithm)和随机选择算法(Random)所需控制器数量进行了对比，结果如表 3，可以看出本文算法的控制器部署开销适中。因为RQFA的主要目的是减少控制器个数，而本文的方法在原理上是通过动态、异构、冗余的开销提高安全性，而且由于冗余控制器并行工作，对网络的性能不会造成太大的影响。

5 结语

针对SDN环境控制器的同构现象和漏洞、后门难以察觉的处境，本文提出了动态异构冗余的SDN结构，利用拜占庭协议协调控制器工作，解决了控制器的动态选举问题。

本文将拜占庭协议以及动态性和异构性引入SDN，提出了相应的体系结构，给出了视图异构度的概念，并设计了控制器视图的动态选举算法，在保证交换机和控制器性能的前提下，能保证视图异构度最大，增强SDN的抗攻击能力。由于额外协议和技术的引入造成了一定的时延开销，在下一步工作中，需要进一步优化拜占庭协议和裁决方法；同时，本文仅从一维的角度量化控制器间的异构性，下一步需要从多维的角度进一步准确地度量控制器间的异构性。