FOCES: Detecting Forwarding Anomalies in Software Defined Networks

security

Peng Z, Xu S, Yang Z, et al. FOCES: Detecting Forwarding Anomalies in Software Defined Networks[C]// IEEE International Conference on Distributed Computing Systems. 2018.

B类。本文提供一种在SDN中进行forwarding anomaly 检测方法，（只提供检测，并未提供定位与解决办法）

基本思想

通过switch统计计数与controller推理计数相比较，判断是否有switch恶意转发包。

算法概念

假没有n个flows($f_1,f_2,\cdots,f_n$)和m个rules($r_1,r_2,\cdots,r_n$),定义流计数矩阵（FCM）$H_{m \times n}$,其中，如果流满足规则，则对应矩阵值为1

$$H_{i,j}=\left\{ \begin{aligned} 1 && if\ f_{i}\ matches\ r_i\\ 0 && otherwise \end{aligned} \right. \tag{1}$$
rule计数向量$Y=(y_1,y_2,\cdots,y_m)^T$,flow计数向量$X=(x_1,x_2,\cdots,x_n)$
由此可得FOCES:
$$HX=Y \tag{2}$$
这是FOCES的基本依据，即：从switch处统计到的流计数与流容量和controller中计算获得的流计数相等。
假设流容量矩阵是$X_0$当switch出现交付异常时，FCM变成了$H'$,这时观察到的计数矩阵变成了$Y'=H'X_0 \neq Y_0$。由于controller并不知道$H'$，所以当需要恢复$X_0$时就要利用
$$HX=Y' \tag{3}$$
可以解得对$X_0$的估计
$$\hat{X} = (H^TH)^{-1}H^TY' \tag{4}$$
从而计算$\hat{Y} = H\hat{X}$,再计算绝对值差
$$\Delta=|Y'-\hat{Y}| \tag{5}$$
理想情况下，当绝对值差不为0时，则认为发生了交付异常。
有的情况下交付异常无法测出，如：
$X_0=(3,4,5)^T$,
,

可算得$\hat{X}=(3,1,8)^T$,这时计算出的$\Delta=0$，可以看到，这是一个反例，出现了交付异常却无法检测出来。这里我要把原文贴上了，因为我看不懂它说什么样的情况测不出来。


阈值计算方法：

算法流程：

矩阵切片：
对于一个特定的switch Si,构造矩阵时只找与Si有关的规则，同样，也只计算流经Si的flow
切片算法流程：

缺点

只能检测出有异常，而无法定位异常发生在哪个switch