网络空间内生安全数学基础(2)——编码信道数学模型

目录

  • (零)这篇博客在干什么
  • (一)内生安全与香农信道编码定理
  • (二)基本定义
  • (三)编码信道存在定理
    • (三.壹)编码信道存在第一定理
    • (三.贰)编码信道存在第二定理
    • (三.叁)编码信道存在第三定理
  • (四)总结

(零)这篇博客在干什么

由于本篇博客可能会涉及到较多数学方面的东西,所以我们在一开始先确定一下本文究竟想要做一个什么事情,以便于大家(以及我自己)对整体有一个较强的把握,而不至于被淹没在不知所云的符号之海之中。

从一个high level的角度来讲,《网络空间内生安全:拟态防御与广义鲁棒控制》一书中所提到的所谓编码信道数学模型就干了这么一个事儿:

从理论上证明了DHR架构可以作为实现内生安全的一种方法

那么具体是怎么证明的呢,这就是我们接下来整篇博客所要试图讲清楚的东西。

(一)内生安全与香农信道编码定理

在上一篇博文网络空间内生安全数学基础(1)——背景中,我们已经了解到了信息系统安全防御和香农可靠通信之间的关联,那么为什么要建立这种关联呢?原因是:

网络空间内生安全的基本问题可以描述为如何在一个存在非随机噪声的可重构有记忆信道上正确地处理和传输信息

注意,这个地方的描述是【非随机噪声、有记忆信道】,而香农可靠通信假设的是【随机噪声、无记忆信道】(把握住对于噪声和信道的假设很重要,正如我们在网络空间内生安全数学基础(1)——背景中提醒大家注意的那样)。

那么利用这种抽象表达,就建立起了内生安全与香农信道编码定理之间的关系——对于网络攻击所导致的信息处理和传输、可靠性与通信噪声等错误都可以采用纠错编码思路进行解决。但是需要注意的是,经典香农通信模型假设无记忆信道,而信息系统可以被抽象为一种有处理能力的可重构有记忆信道;经典香农通信模型假设噪声随机,而网络攻击具有明显的非随机性,可以抽象为广义不确定扰动(包括随机通信噪声、随机物理失效、人为攻击噪声等)。

有了这种联系,《网络空间内生安全:拟态防御与广义鲁棒控制》一书发展了香农信道编码理论,在其基础上提出了编码信道理论(这个名字起得有点随意的……),相较于前者,编码信道理论导入了一些新的因素,例如非随机噪声在有记忆可重构结构信道上的随机性变化分析,再次从一个high level的角度来讲(但是没有开篇那么high),这个编码信道理论其实就是证明了这样一个事情:

基于概率论形式化证明了对于离散有记忆信道上的任何随机和非随机扰动,存在一种内源性的动态异构冗余消记忆的信道构造与编码方案,能够使平均译码错误概率任意小。

这个表述是不是有点熟悉,和香农第二定理很像是吧,香农第二定理其实就是编码信道理论(上面的这段话)在随机噪声无记忆信道条件下的一种特例。

(二)基本定义

在介绍数学模型之前呢,肯定是要介绍一些基本定义和假设了,编码信道理论里面的这部分内容主要就是针对漏洞、后门这种攻击方可以利用的东西和结构编码、元信道、纠错译码这些信息系统内生安全模型里面的结构进行的定义和假设,具体的结构在网络空间内生安全数学基础(1)——背景最后一张图里面有所提及,我们在这里再加深一下印象。

请添加图片描述
挑重点来说,我们可以从上图中看到,信源发出的信号依次经过结构编码、元信道和纠错译码,元信道有n个是因为DHR架构本身就有动态异构冗余的特性,而且因为该模型假设信道有记忆,所以上面有一个记忆清除模块,下面的广义扰动就是指随机或非随机扰动,这个是为了适应信息系统所面临的威胁在传统的香农定理上扩展出来的,前文也已经提到过了。

主体结构大概就是这五个部分,那么我们接下来开始正式介绍定义与假设:

假设1:
对于单个漏洞,攻击方通过扰动激活漏洞并产生信道错误需要的时间 T s > 0 T_s>0 Ts>0;对于协同漏洞,由于元信道的异构性,攻击方需要时间 T i > 0 T_i>0 Ti>0 来协同漏洞并产生信道错误。

这里先解释一下什么是协同漏洞,上面的图所描述的系统里面有 n n n异构元信道,这时针对其中某个元信道 k k k 的单一漏洞进行可能无法对整个系统噪声影响(因为毕竟还有剩余 n − 1 n-1 n1 个信道),那么如果想对整个系统造成影响的话,可能需要同时对系统中的 ⌈ n 2 ⌉ \lceil\frac{n}{2}\rceil 2n 个元信道所具有的漏洞同时利用(如果用大数裁决的话),那么这种对多个元信道所具有的漏洞同时利用的方式就被称为协同漏洞。

上述 假设1 说明了单个漏洞协同漏洞的利用均需要一定的时间。

假设2:
对于单个后门,攻击方通过扰动激活后门并产生信道错误需要的时间 T s = 0 T_s=0 Ts=0;对于协同后门,由于元信道的异构性,攻击方需要时间 T i > 0 T_i>0 Ti>0 来协同后门并产生信道错误。

(协同后门的概念和上述协同漏洞类似)

上述 假设 2 说明了单个后门的利用无需时间(可以看作系统内部的攻击),而协同后门的利用需要一定的时间。

假设3:
对于元信道,假设其中可以同时存在漏洞和后门,可以有记忆或无记忆,对广义扰动造成元信道错误或失效的记忆可消除。

上述 假设 3 说明了系统可以通过“记忆清除”模块进行记忆消除(如上图),若系统在 t t t 时刻进行了记忆消除,且 t 0 < t < t 1 t_0<t<t_1 t0<t<t1,那么任意 t 0 t_0 t0 时刻发生的信道错误将不影响任意 t 1 t_1 t1 时刻的信息传递。

定义1:
无记忆元信道是指元信道 M C 0 , M C 1 , ⋯   , M C n M_{C_0},M_{C_1},\cdots,M_{C_n} MC0,MC1,,MCn T s T_s Ts 时刻受到的不确定性扰动不会影响时刻 t + T s , ( t > 0 ) t+T_s,(t>0) t+Ts,(t>0)。有传输概率:
∀ t ≥ 0 , P ( y ≠ x ∣ x ) = p , \forall t\geq 0, \mathbb{P}(y\neq x|x)=p, t0,P(y=xx)=p,
其中 x x x 为信源信息, y y y 为译码后信宿收到的信息。

定义2:
有记忆元信道是指元信道 M C 0 , M C 1 , ⋯   , M C n M_{C_0},M_{C_1},\cdots,M_{C_n} MC0,MC1,,MCn T s T_s Ts 时刻受到不确定性扰动的影响在时刻 t + T s , ( t > 0 ) t+T_s,(t>0) t+Ts,(t>0) 一直保持。有传输概率:
∃ T s , ∀ t ≥ T s , P ( y ≠ x ∣ x ) = 1 , \exists T_s, \forall t\geq T_s, \mathbb{P}(y\neq x|x)=1, Ts,tTs,P(y=xx)=1,
其中 x x x 为信源信息, y y y 为译码后信宿收到的信息。

上述 定义1、定义 2 可与 假设 3 互相进行理解:
无记忆信道中,无论在何时刻受到了扰动,传输概率不受影响(定义1);有记忆信道中,扰动影响传输概率(定义2);而上图中的记忆清除模块可以擦除这种元信道对扰动的“记忆”(假设 3)。

(三)编码信道存在定理

如下的三个编码信道存在定理分别在不同条件下由浅入深地给出了“信道出错概率可以任意小”这一结论——对标香农第二定理,对具体证明部分不感兴趣的朋友们记住前面加粗这个部分的结论和对应的条件(在下文三个子标题的定理部分会给出)就可以了。
在接下来的三个子标题中,都是先给定理再给解释。
注:下面三个定理中的一些名词的具象化解释可以在上文第(二)部分:基本定义中的图中找到。

(三.壹)编码信道存在第一定理

元信道噪声(扰动)随机到达,结构编码和纠错译码无扰动和无记忆,记离散无记忆元信道为 [ P ( y ∣ x ) ] [P(y|x)] [P(yx)],其中 x , y x,y x,y 分别为输入、输出,编码信道容量为 C C C,噪声随机到达,若编码信息传输率 R < C R<C R<C,那么存在无记忆元信道 n n n 足够大的编码信道,总可以在输入集合找到 M ′ = 2 n R M'=2^{nR} M=2nR 个码字组成的一个码集合(码长为 n n n),在一定译码规则下使得信道输出错误概率 P E ≤ ϵ P_{E}\leq\epsilon PEϵ,其中 ϵ \epsilon ϵ 为任意小正数。
(……定理结束分割线……)

上文已经提到了,定理中的条件很重要,那么这个编码信道存在第一定理的条件是这样的:

  1. 噪声(扰动)随机到达
  2. 结构编码和纠错译码无扰动和无记忆
  3. 元信道离散无记忆

在这样的条件下,编码信道的 n n n个元信道构造满足香农第二定理信道噪声随机且信道 n n n次扩展无记忆条件的约束前提,因此该编码信道存在第一定理香农第二定理等价,证明方式也相同。
作者通过这样的方式证明了上述第一定理。

(三.贰)编码信道存在第二定理

元信道噪声(扰动)非随机到达,结构编码和纠错译码无扰动和无记忆,记动态异构冗余与反馈消记忆构造后的离散有记忆编码信道为 [ P ( y ∣ x s f ) ] [P(y|xsf)] [P(yxsf)],其中 x , y , s , f x,y,s,f x,y,s,f 分别为输入、输出、记忆状态、反馈消记忆状态,编码信道容量为 C C C 且对任意时刻 t t t ∀ t > 0 , C ( t ) ∈ [ C S , C 0 ] \forall t>0, C(t)\in[C_S,C_0] t>0,C(t)[CS,C0],若时刻 t t t 编码信息传输率 R ( t ) < C ( t ) R(t)<C(t) R(t)<C(t),则只要码长与编码元信道构造数 n n n 足够大,总可以在输入集合找到 M ′ = 2 n R ( t ) M'=2^{nR(t)} M=2nR(t) 个码字组成的一个码集合,在一定译码规则下使得信道输出错误概率 P E ( t ) ≤ ϵ P_{E}(t)\leq\epsilon PE(t)ϵ,其中 ϵ \epsilon ϵ 为任意小正数。
(……定理结束分割线……)

上述编码信道存在第二定理的条件是这样的:

  1. 噪声(扰动)非随机到达
  2. 结构编码和纠错译码无扰动和无记忆
  3. 编码信道离散有记忆

可以看到,相较于前文第一定理,该第二定理放松了一些条件:噪声到达由随机推广至非随机(因为本书利用广义扰动将攻击、异常等扰动均放在了同一个框架下,所以很难将其建模为随机噪声)、编码信道无记忆推广至有记忆(有记忆信道的假设也比无记忆信道假设更加严苛,且更符合现实情况)。

在这样的条件下,作者给出了编码信道存在第二定理的证明。
【证明开始】
对于存在攻击扰动的离散有记忆信道 P ( y i + 1 ( t ) ∣ x i + 1 ( t ) s i ( t ) ) P(y_{i+1}(t)|x_{i+1}(t)s_i(t)) P(yi+1(t)xi+1(t)si(t)) s i ( t ) = 0 s_i(t)=0 si(t)=0 表示前一序列 i i i 正常输出 t t t 时刻 i + 1 i+1 i+1 序列的影响,其中攻击的影响会随着时间累积。 s i ( t ) = 1 s_i(t)=1 si(t)=1 表示前一序列 i i i 异常输出 t t t 时刻 i + 1 i+1 i+1 序列将一直以概率 1 1 1 保持该异常状态。
不失一般性,假定在攻击到达之前的时间 t t t 内,攻击成功干扰元信道的记忆性表现为时间上的负指数分布,即:
1) 假设攻击以速率 λ \lambda λ 到达,则有:
P s ( t ) = 1 − e − λ t = p ( t ) . P_s(t)=1-e^{-\lambda t}=p(t). Ps(t)=1eλt=p(t).
当引入反馈控制消记忆动作 f ( t ) f(t) f(t),假定防御方重构恢复(或攻击记忆消除)以可控速率 μ \mu μ 到达,则有:
P r ( t ) = 1 − e − μ t = p ( f ( t ) ) . P_r(t)=1-e^{-\mu t}=p(f(t)). Pr(t)=1eμt=p(f(t)).
上述过程可由下图表示,其中 S 0 S_0 S0 为元信道初始无记忆初状态, S 1 S_1 S1 为元信道攻击记忆保持状态。

于是,对单个离散有记忆元信道,有译码错误概率:
P ( y i ( t ) ≠ x i ( t ) ∣ x i ( t ) ) = − λ λ + μ e − ( λ + μ ) t + λ λ + μ < 1. P(y_i(t)\neq x_i(t)|x_i(t))=-\frac{\lambda}{\lambda+\mu}e^{-(\lambda+\mu)t}+\frac{\lambda}{\lambda+\mu}<1. P(yi(t)=xi(t)xi(t))=λ+μλe(λ+μ)t+λ+μλ<1.

2) 若攻击在某时刻 T s T_s Ts 到达,系统将以概率 1 1 1 保持该攻击状态(上文第(二)部分:基本定义中的定义二)。在该种情况下,由于防御方以 μ \mu μ 速率实现重构恢复,则元信道在 t t t 时刻的失效概率满足:
∀ t , t ∈ ( 0 , ∞ ) , P s i ( t ) < 1 − ( 1 − e − μ t ) = e − μ t < 1 , \forall t, t\in(0,\infty), P_{si}(t)<1-(1-e^{-\mu t})=e^{-\mu t}<1, t,t(0,),Psi(t)<1(1eμt)=eμt<1,
表明记忆具有不确定性。在离散有干扰有记忆元信道中,动态异构冗余架构和反馈控制消记忆动作 f ( t ) f(t) f(t) 的引入使得:
∀ t , P ( y i + 1 ( t ) ∣ x i + 1 ( t ) s i ( t ) f i + 1 ( t ) ) = p i + 1 ( t ) < 1 , \forall t, P(y_{i+1}(t)|x_{i+1}(t)s_i(t)f_{i+1}(t))=p_{i+1}(t)<1, t,P(yi+1(t)xi+1(t)si(t)fi+1(t))=pi+1(t)<1,
其中, f ( t ) = 0 f(t)=0 f(t)=0 表示 t t t 时刻反馈消记忆事件未到达, f ( t ) = 1 f(t)=1 f(t)=1 表示 t t t 时刻反馈消记忆事件到达。由非随机扰动在攻击未到达之前具有基类型,因此编码信道容量处于一定范围(而非固定值)。引入反馈可控消记忆动作 f ( t ) f(t) f(t) 后,编码信道容量将处于可控范围 [ C S , C 0 ] [C_S,C_0] [CS,C0]

若攻击到达与反馈恢复时间服从上述负指数分布,整个编码信道存在稳态分布,此时 C S C_S CS 为编码信道稳态时的信道容量, C 0 C_0 C0 为初始信道容量。

【前面的部分都还比较容易理解,接下来这里涉及到了一个小复杂的概念:】
设编码信道 t t t 时刻输入序列为 x ( t ) = ( x 1 ( t ) , x 2 ( t ) , ⋯   , x n ( t ) ) ∈ X n \bold{x}(t)=(x_1(t),x_2(t),\cdots,x_n(t))\in X^n x(t)=(x1(t),x2(t),,xn(t))Xn,译码输出为 y ( x ( t ) ) = ( y 1 ( x 1 ( t ) ) , y 2 ( x 2 ( t ) ) , ⋯   , y n ( x n ( t ) ) ) ∈ Y n \bold{y}(\bold{x}(t))=(y_1(x_1(t)),y_2(x_2(t)),\cdots,y_n(x_n(t)))\in Y^n y(x(t))=(y1(x1(t)),y2(x2(t)),,yn(xn(t)))Yn。从 X n X^n Xn 种输入中随机选 M = 2 n R ( t ) M=2^{nR(t)} M=2nR(t) 个序列作为码字,设 X X X 为随机编码(所有元素独立、等概率出现),对于时刻 t t t 所对应的接受序列 y ( x ( t ) ) \bold{y}(\bold{x}(t)) y(x(t)) 给定,若存在唯一的 k ∈ [ 1 , 2 n R ( t ) ] k\in[1,2^{nR(t)}] k[1,2nR(t)],使得:
( x k ( t ) , y ( x ( t ) ) ) ∈ T X Y ( n , ϵ ) , (\bold{x}_k(t),\bold{y}(\bold{x}(t)))\in T_{XY}(n,\epsilon), (xk(t),y(x(t)))TXY(n,ϵ),
则将 y ( x ( t ) ) \bold{y}(\bold{x}(t)) y(x(t)) 译码为 x k ( t ) \bold{x}_k(t) xk(t),即 F ( y ( x ( t ) ) ) = x k ( t ) F(\bold{y}(\bold{x}(t)))=\bold{x}_k(t) F(y(x(t)))=xk(t),其中 T X Y ( n , ϵ ) T_{XY}(n,\epsilon) TXY(n,ϵ) 表示序列对 ( x ( t ) , y ( x ( t ) ) ) (\bold{x}(t),\bold{y}(\bold{x}(t))) (x(t),y(x(t))) 是联合 ϵ \epsilon ϵ 典型序列。
【通俗一点,这里的意思就是“有典选典”:如果能构成联合典型序列,那么就选能构成典型序列的译码方式,原因也很简单,因为联合典型序列有很多好的性质,便于界定出错概率,典型序列的概念在这里不具体介绍,感兴趣的朋友们可以自行查阅相关资料。】

若发送消息为 x m ( t ) \bold{x}_m(t) xm(t),接收序列为 y ( x m ( t ) ) \bold{y}(\bold{x}_m(t)) y(xm(t)),则很自然地,译码错误概率可以表示为:
P e m = P ( x k ( t ) ≠ x m ( t ) ∣ y ( x m ( t ) ) ) . P_{em}=P(\bold{x}_k(t)\neq\bold{x}_m(t)|\bold{y}(\bold{x}_m(t))). Pem=P(xk(t)=xm(t)y(xm(t))).
我们接下来要研究的就是这个译码错误概率。

令事件:
E m ( t ) = { ( x m ( t ) , y ( x m ( t ) ) ) ∈ T X Y ( n , ϵ ) , m ∈ [ 1 , 2 n R ( t ) ] } . E_m(t)=\{(\bold{x}_m(t),\bold{y}(\bold{x}_m(t)))\in T_{XY}(n,\epsilon), m\in[1,2^{nR(t)}]\}. Em(t)={(xm(t),y(xm(t)))TXY(n,ϵ),m[1,2nR(t)]}.

如果设发送的第一个消息为 x 1 ( t ) \bold{x}_1(t) x1(t),那么译码错误概率可以被分为如下两个部分:
(1) 发送码字 x 1 ( t ) \bold{x}_1(t) x1(t) 与接收码字 y ( x 1 ( t ) ) \bold{y}(\bold{x}_1(t)) y(x1(t)) 不构成联合 ϵ \epsilon ϵ 典型序列,该事件记作 E 1 C ( t ) E_1^C(t) E1C(t)
(2) 码字 x k ( t ) , k ≠ 1 \bold{x}_k(t), k\neq 1 xk(t),k=1 与接收码字 y ( x 1 ( t ) ) \bold{y}(\bold{x}_1(t)) y(x1(t)) 构成联合 ϵ \epsilon ϵ 典型序列。
【这两个部分我们在这里再用通俗一点的语言表达一下:第一个部分很容易理解,事件 E m E_m Em 在定义的时候就是根据联合 ϵ \epsilon ϵ 典型序列定义的,所以就取补集就可以了;第二个部分是这样的:因为另外的码字与接收码字构成联合 ϵ \epsilon ϵ 典型序列,所以根据上面“有典选典”的规则,直接选取了另外的码字,导致错了。】

第一个部分的译码错误概率为:
P ( E 1 C ( t ) ) = 1 − P ( E 1 ( t ) ) ≤ ϵ . P(E_1^C(t))=1-P(E_1(t))\leq\epsilon. P(E1C(t))=1P(E1(t))ϵ.
【上面提到联合 ϵ \epsilon ϵ 典型序列有很多好性质,这个就是根据其中一个好性质 P ( E 1 ( t ) ) ≥ 1 − ϵ P(E_1(t))\geq1-\epsilon P(E1(t))1ϵ 推出来的。】

第二个部分的译码错误概率为:
【因为 E m E_m Em 在定义的时候就是根据联合 ϵ \epsilon ϵ 典型序列定义的,所以直接取 k ≠ 1 k\neq1 k=1 时候的概率和就行了。】
P e 1 ( t ) = P ( x k ( t ) ≠ x 1 ( t ) ∣ x 1 ( t ) ) = ∑ k ≠ 1 P ( E k ( t ) ∣ x 1 ( t ) ) , P_{e1}(t)=P(\bold{x}_k(t)\neq\bold{x}_1(t)|\bold{x}_1(t))=\sum_{k\neq1}P(E_k(t)|\bold{x}_1(t)), Pe1(t)=P(xk(t)=x1(t)x1(t))=k=1P(Ek(t)x1(t)),
其中:
【该式就是简单根据定义直接写下来的】
P ( E k ( t ) ∣ x 1 ( t ) ) = ∑ j = 1 Y n P ( y j ( x 1 ( t ) ) ∣ x 1 ( t ) ) P ( ( x k ( t ) , y ( x 1 ( t ) ) ) ∈ T X Y ( n , ϵ ) ) = P ( ( x k ( t ) , y ( x 1 ( t ) ) ) ∈ T X Y ( n , ϵ ) ) , k ≠ 1. P(E_k(t)|\bold{x}_1(t))=\sum_{j=1}^{Y^n}P(\bold{y}_j(\bold{x}_1(t))|\bold{x}_1(t))P((\bold{x}_k(t),\bold{y}(\bold{x}_1(t)))\in T_{XY}(n,\epsilon))=P((\bold{x}_k(t),\bold{y}(\bold{x}_1(t)))\in T_{XY}(n,\epsilon)), k\neq1. P(Ek(t)x1(t))=j=1YnP(yj(x1(t))x1(t))P((xk(t),y(x1(t)))TXY(n,ϵ))=P((xk(t),y(x1(t)))TXY(n,ϵ)),k=1.

又当 x k ( t ) , y ( x 1 ( t ) ) , ( x k ( t ) , y ( x 1 ( t ) ) ) \bold{x}_k(t),\bold{y}(\bold{x}_1(t)),(\bold{x}_k(t),\bold{y}(\bold{x}_1(t))) xk(t),y(x1(t)),(xk(t),y(x1(t)))均为 ϵ \epsilon ϵ 典型序列时,有:
P ( x k ( t ) ) ≤ 2 − n [ H ( X ) − ϵ ] , P(\bold{x}_k(t))\leq2^{-n[H(X)-\epsilon]}, P(xk(t))2n[H(X)ϵ],
P ( y ( x 1 ( t ) ) ) ≤ 2 − n [ H ( Y ) − ϵ ] , P(\bold{y}(\bold{x}_1(t)))\leq2^{-n[H(Y)-\epsilon]}, P(y(x1(t)))2n[H(Y)ϵ],
∥ T X Y ( n , ϵ ) ∥ ≤ 2 − n [ H ( X Y ) + ϵ ] . \|T_{XY}(n,\epsilon)\|\leq2^{-n[H(XY)+\epsilon]}. TXY(n,ϵ)2n[H(XY)+ϵ].
【这三个式子也是根据 ϵ \epsilon ϵ 典型序列的性质来的】

因为 y ( x 1 ( t ) ) \bold{y}(\bold{x}_1(t)) y(x1(t)) 仅由 x 1 ( t ) \bold{x}_1(t) x1(t) 产生,与 x k ( t ) , k ≠ 1 \bold{x}_k(t), k\neq1 xk(t),k=1独立,因此:
P ( E k ( t ) ∣ x 1 ( t ) ) = ∑ x k ( t ) , y ( x 1 ( t ) ) , ( x k ( t ) , y ( x 1 ( t ) ) ) ∈ T X Y ( n , ϵ ) P ( x k ( t ) ) P ( y ( x 1 ( t ) ) ) , k ≠ 1. P(E_k(t)|\bold{x}_1(t))=\sum_{\bold{x}_k(t),\bold{y}(\bold{x}_1(t)),(\bold{x}_k(t),\bold{y}(\bold{x}_1(t)))\in T_{XY}(n,\epsilon)}P(\bold{x}_k(t))P(\bold{y}(\bold{x}_1(t))), k\neq1. P(Ek(t)x1(t))=xk(t),y(x1(t)),(xk(t),y(x1(t)))TXY(n,ϵ)P(xk(t))P(y(x1(t))),k=1.

结合上面三个式子,有:
【用到了互信息的性质: I ( X Y ) = H ( X ) + H ( Y ) − H ( X Y ) I(XY)=H(X)+H(Y)-H(XY) I(XY)=H(X)+H(Y)H(XY)
P ( E k ( t ) ) ≤ 2 − n [ I ( X Y ) − 3 ϵ ] . P(E_k(t))\leq2^{-n[I(XY)-3\epsilon]}. P(Ek(t))2n[I(XY)3ϵ].

对其进行求和,有:
∑ k ≠ 1 P ( E k ( t ) ) ≤ ( 2 n R ( t ) − 1 ) 2 − n [ I ( X Y ) − 3 ϵ ] . \sum_{k\neq1}P(E_k(t))\leq(2^{nR(t)}-1)2^{-n[I(XY)-3\epsilon]}. k=1P(Ek(t))(2nR(t)1)2n[I(XY)3ϵ].

由于互信息即信道容量( I ( X Y ) = C ( t ) I(XY)=C(t) I(XY)=C(t)),上式可写为:
∑ k ≠ 1 P ( E k ( t ) ) ≤ 2 n [ R ( t ) − C ( t ) + 3 ϵ ] . \sum_{k\neq1}P(E_k(t))\leq2^{n[R(t)-C(t)+3\epsilon]}. k=1P(Ek(t))2n[R(t)C(t)+3ϵ].

∀ η = 3 ϵ > 0 , R ( t ) < C ( t ) − η , n → ∞ \forall \eta=3\epsilon>0, R(t)<C(t)-\eta, n\rightarrow\infty η=3ϵ>0,R(t)<C(t)η,n,有:
∑ k ≠ 1 P ( E k ( t ) ) → 0. \sum_{k\neq1}P(E_k(t))\rightarrow0. k=1P(Ek(t))0.

于是在 t t t 时刻,译码错误概率:
【前文译码错误概率的两个组成部分,前一部分被 ϵ \epsilon ϵ 界定住,后一部分趋近于 0 0 0
P e ( t ) = P ( E 1 C ( t ) ) + P e 1 ( t ) ≤ ϵ , P_e(t)=P(E_1^C(t))+P_{e1}(t)\leq\epsilon, Pe(t)=P(E1C(t))+Pe1(t)ϵ,
即译码错误概率 P e ( t ) P_e(t) Pe(t) 可为任意小。

【证毕】

(三.叁)编码信道存在第三定理

元信道、结构编码和纠错译码噪声(扰动)非随机到达,结构编码和纠错译码有记忆且记忆可消,记动态异构冗余与反馈消记忆构造后的离散有记忆编码信道为 [ P ( y ∣ x s f ) ] [P(y|xsf)] [P(yxsf)],其中 x , y , s , f x,y,s,f x,y,s,f 分别为输入、输出、记忆状态、反馈消记忆状态,编码信道容量为 C C C 且对任意时刻 t t t ∀ t > 0 , C ( t ) ∈ [ C S , C 0 ] \forall t>0, C(t)\in[C_S,C_0] t>0,C(t)[CS,C0],若时刻 t t t 编码信息传输率 R ( t ) < C ( t ) R(t)<C(t) R(t)<C(t),则只要码长与编码元信道构造数 n n n 足够大,总可以在输入集合找到 M ′ = 2 n R ( t ) M'=2^{nR(t)} M=2nR(t) 个码字组成的一个码集合,在一定译码规则下使得信道输出错误概率 P E ( t ) ≤ ϵ P_{E}(t)\leq\epsilon PE(t)ϵ,其中 ϵ \epsilon ϵ 为任意小正数。
(……定理结束分割线……)

上述编码信道存在第三定理的条件是这样的:

  1. 噪声(扰动)非随机到达
  2. 元信道、结构编码和纠错译码均有扰动和记忆
  3. 编码信道离散有记忆

可以看到,相较于前文第二定理,该第三定理放松了一些条件:将无噪声无记忆结构编码和纠错译码推广至有噪声和记忆的情况下,比第二定理更加严苛,且更符合现实情况。

在这样的条件下,作者给出了编码信道存在第三定理的证明,证明分为两个部分:

  1. 讨论随机扰动的情况
  2. 讨论非随机扰动的情况

在这两个部分中,由于第三定理中的编译码执行体元信道、动态异构的结构编码分路器、动态异构可消记忆的纠错译码表决器均会遭到扰动,因此也是分别将这三个部分拆开来进行证明的。

【证明开始】
(一)首先讨论随机扰动的情况

(1)编译码执行体元信道的输出错误概率
章节三.贰中已经证明了,元信道输出错误概率 P e ( t ) ≤ ϵ P_e(t)\leq\epsilon Pe(t)ϵ,其中 ϵ \epsilon ϵ 为任意小正数。

(2)结构编码分路器与纠错译码表决器的物理失效问题
∀ t \forall t t,随机噪声成功造成结构编码分路器或纠错译码表决器输出出错的概率 P e ( t ) P_e(t) Pe(t) 满足:
0 < P e ( t ) < 1. 0<P_e(t)<1. 0<Pe(t)<1.

不失一般性,设异构的结构编码分路器或纠错译码表决器可选余度为 n n n,且假设单个结构编码分路器或纠错译码表决器物理失效到达服从速率为 λ \lambda λ 的负指数分布,单个结构编码分路器或纠错译码表决器修复服从速率为 μ \mu μ 的负指数分布,则单个结构编码分路器或纠错译码表决器状态与章节三.贰中的状态图相同,为了预期进行区分,将编码器或解码器初始状态和失效状态分别记作 s c 0 sc_0 sc0 s c 1 sc_1 sc1
由此可求得稳态可用概率 P s c 0 P_{sc_0} Psc0 和失效概率 P s c 1 P_{sc_1} Psc1
P s c 0 = μ λ + μ , P s c 1 = λ λ + μ . P_{sc_0}=\frac{\mu}{\lambda+\mu},\quad P_{sc_1}=\frac{\lambda}{\lambda+\mu}. Psc0=λ+μμ,Psc1=λ+μλ.

接下来的讨论分为两种情况:(1)纠错译码表决器修复速率 μ \mu μ 足够大;(2) μ , λ \mu,\lambda μ,λ 一定。

先讨论 μ \mu μ 足够大的情况:
P s c 0 = μ λ + μ → 1 − ϵ 0 . P_{sc_0}=\frac{\mu}{\lambda+\mu}\rightarrow 1-\epsilon_0. Psc0=λ+μμ1ϵ0.

然后讨论 μ , λ \mu,\lambda μ,λ 一定的情况:
由修复速率表达式:
U = lim ⁡ t → 0 u ( t ) − u ( 0 ) t , U=\lim_{t\rightarrow 0}\frac{u(t)-u(0)}{t}, U=t0limtu(t)u(0),
n = 1 n=1 n=1 时,
U = lim ⁡ t → 0 1 − e − μ t t = μ . U=\lim_{t\rightarrow 0}\frac{1-e^{-\mu t}}{t}=\mu. U=t0limt1eμt=μ.

μ \mu μ λ \lambda λ 一定且 n > 1 n>1 n>1 时,至少有 n n n 余度同时修复以保证一个余度可用,于是有:
U ≥ lim ⁡ t → 0 n ( 1 − e − μ t ) ( e − μ t ) n − 1 + O ( t ) t = n μ . U\geq\lim_{t\rightarrow0}\frac{n(1-e^{-\mu t})(e^{-\mu t})^{n-1}+O(t)}{t}=n\mu. Ut0limtn(1eμt)(eμt)n1+O(t)=nμ.

因此对于余度为 n n n n n n 足够大(意味着修复速率 n μ n\mu nμ 足够大)的结构编码分路器或纠错译码表决器有:
P s c 0 = n μ λ + n μ → 1 − ϵ 0 , P_{sc_0}=\frac{n\mu}{\lambda+n\mu}\rightarrow 1-\epsilon_0, Psc0=λ+nμnμ1ϵ0,
其中 ϵ 0 \epsilon_0 ϵ0 为任意小正数。

综上,扰动随机的情况下,当纠错译码表决器修复速率 μ \mu μ 足够大或者余度 n n n 足够大时,结构编码分路器或纠错译码表决器异常概率为:
P e 1 = 1 − P s c 0 → ϵ 0 . P_{e1}=1-P_{sc_0}\rightarrow\epsilon_0. Pe1=1Psc0ϵ0.

(二)再来讨论非随机扰动的情况

首先,在设计层面引入一些新的假设:

假设4:
对于结构编码单元,通过对其进行拟态化设计,可以将其划分为分路器和结构编码执行体。
(1) 分路器功能足够简化,只需完成状态无关的输入报文复制分发。
在采用分光器等物理器件实现时,(由于结构足够简单)假设分路器中既没有漏洞也没有后门,对于攻击等非随机扰动不具有记忆性;在采用逻辑固化/硬化/防篡改、每次处理前存储初始化等机制时,功能足够简化可进行形式化验证,假设分路器中有漏洞无后门,对于攻击等非随机扰动的记忆可消除。
(2) 结构编码单元除分路器之外的复杂功能由编码执行体实现。
结构编码执行体采用类似元信道方式实现,假设其中可以同时存在漏洞和后门,可以有记忆或无记忆,记忆可消除。

假设5:
对于纠错译码单元,通过对其进行拟态化设计,可以将其划分为表决器和纠错译码执行体。
(1) 表决器功能足够简化,只需完成状态无关的输出报文大数表决。
在采用逻辑固化/硬化/防篡改、每次处理前存储初始化等机制时,功能足够简化可进行形式化验证,假设表决器中有漏洞无后门,对于攻击等非随机扰动的记忆可消除。
(2) 纠错译码单元除表决器之外的复杂功能由纠错译码执行体实现。
纠错译码执行体采用类似元信道方式实现,假设其中可以同时存在漏洞和后门,可以有记忆或无记忆,记忆可消除。

【这两个假设主要是将结构编码或纠错译码单元分别划分为了两个部分,其中一个部分结构足够简单,以至于不存在后门(对于分光器等物理器件而言,甚至不存在漏洞);另一个部分与元信道类似,相关出错概率分析也类似。】

(1)元信道
同样,章节三.贰中已经证明了,元信道输出错误概率 P e ( t ) ≤ ϵ P_e(t)\leq\epsilon Pe(t)ϵ,其中 ϵ \epsilon ϵ 为任意小正数。

(2)结构编码
针对结构编码,由 假设4 可知,结构编码分路器设计足够简化,有两种情况:
(1)使其成为功能单一的物理器件如分光器,仅具备复制分发功能。于是因漏洞后门问题造成其异常错误概率 P e 1 = 0 P_{e1}=0 Pe1=0

(2)使其有漏洞无后门,对于漏洞,因复制分发在多次操作之间无需共享与状态同步,可通过逻辑固化与存储初始化使得结构编码分路器记忆可消除。
在这种情况下,对于任意时刻 t t t,噪声成功造成结构编码分路器输出出错概率
P e 1 ( t ) = p 0 n , P_{e1}(t)=\frac{p_0}{n}, Pe1(t)=np0,
其中 p 0 p_0 p0 为单个分路器输出出错概率。

当可选异构纠错译码表决器数 n n n 足够大时,有:
∀ t ∈ ( 0 , ∞ ) , P e 1 ( t ) = p 0 n → ϵ 0 , \forall t\in(0,\infty), P_{e1}(t)=\frac{p_0}{n}\rightarrow\epsilon_0, t(0,),Pe1(t)=np0ϵ0,
结构编码分路器输出出错概率 P e 1 ( t ) P_{e1}(t) Pe1(t) 任意小。

(3)纠错译码
假设5 可知,纠错译码表决器设计足够简化,使其有漏洞无后门,又通过逻辑固化与逐次存储初始化使得纠错译码表决器记忆可消除。由于元信道失效概率随机化,于是针对触发纠错译码表决器漏洞的噪声或扰动具有随机性;此外,造成物理失效的噪声或扰动同样具有随机性。
【如上文第(二)部分:基本定义中的图中可以看到,纠错译码部分在元信道之后,所以元信道失效概率也会对其造成影响,因此在这里引入了一个元信道失效概率随机化的概念。不难理解,通过动态异构冗余(DHR)和反馈消记忆机制,噪声不是对整个系统永久造成影响的,因此失效概率是随机化的。】

对任意时刻 t t t,噪声成功造成纠错译码表决器输出出错的概率:
0 < P e 2 ( t ) = p 1 p 2 < 1 , 0<P_{e_2}(t)=p_1p_2<1, 0<Pe2(t)=p1p2<1,
其中 p 1 < 1 p_1<1 p1<1 为元信道失效造成的输出异常概率, p 2 < 1 p_2<1 p2<1 为由于元信道的触发致使纠错译码表决器漏洞触发失效的概率。

接下来的讨论将分为两个部分:(1)元信道修复速率 μ \mu μ 足够大;(2) μ \mu μ 一定,异构纠错译码表决器数 n n n 足够大。

先讨论 μ \mu μ 足够大的情况:
由上文 章节三.贰证明2)部分 中的结论,元信道在 t t t 时刻失效概率满足:
∀ t ∈ ( 0 , ∞ ) , P s i ( t ) ≤ e − μ t , \forall t\in(0,\infty), P_{si}(t)\leq e^{-\mu t}, t(0,),Psi(t)eμt,
因此若元信道反馈修复速率 μ \mu μ 足够大,有:
∀ t ∈ ( 0 , ∞ ) , P e 2 ( t ) = p 1 p 2 = P s i ( t ) p 2 ≤ e − μ t p 2 → ϵ 1 , \forall t\in(0,\infty), P_{e_2}(t)=p_1p_2=P_{si}(t)p_2\leq e^{-\mu t}p_2\rightarrow\epsilon_1, t(0,),Pe2(t)=p1p2=Psi(t)p2eμtp2ϵ1,
P e 2 ( t ) P_{e_2}(t) Pe2(t) 足够小。

然后讨论 μ \mu μ 一定, n n n 足够大的情况:
∀ t ∈ ( 0 , ∞ ) , P e 2 ( t ) = p 1 p 2 n ≤ e − μ t p 2 n → ϵ 1 , \forall t\in(0,\infty), P_{e_2}(t)=\frac{p_1p_2}{n}\leq\frac{e^{-\mu t}p_2}{n}\rightarrow\epsilon_1, t(0,),Pe2(t)=np1p2neμtp2ϵ1,
P e 2 ( t ) P_{e_2}(t) Pe2(t) 足够小。

因此,当元信道修复速率 μ \mu μ 足够大或异构纠错译码表决器数 n n n 足够大时,结合章节三.贰中的编码信道第二定理,整个过程系统错误概率为:
∀ t ∈ ( 0 , ∞ ) , P E ( t ) = P e 1 ( t ) + P e ( t ) + P e 2 ( t ) = ϵ 0 + ϵ + ϵ 1 = ϵ ′ , \forall t\in(0,\infty), P_E(t)=P_{e_1}(t)+P_{e}(t)+P_{e_2}(t)=\epsilon_0+\epsilon+\epsilon_1=\epsilon', t(0,),PE(t)=Pe1(t)+Pe(t)+Pe2(t)=ϵ0+ϵ+ϵ1=ϵ,
其中 ϵ ′ \epsilon' ϵ 可以为任意小正数。
P e 1 ( t ) P_{e_1}(t) Pe1(t) 为结构编码(简单结构)的出错概率, P e ( t ) P_{e}(t) Pe(t) 为元信道的出错概率, P e 2 ( t ) P_{e_2}(t) Pe2(t) 为纠错译码(简单结构)的出错概率。】

【证毕】

三个定理冗长的证明过程终于结束了,如果最终有一个take home message的话那就是:

元信道修复速率 μ \mu μ 足够大或异构纠错译码表决器数 n n n 足够大时,整个系统的出错概率可以任意小,这里面的 μ \mu μ 足够大对应着DHR架构的动态性D, n n n 足够大对应着DHR架构的异构性H和冗余性R。

(四)总结

在这片博文的最后,我们再次强调一下,上面那么多的符号、公式、推论、定理等等都只是为了这一个结论服务的:

DHR架构可以作为实现内生安全的一种方法

它给出了DHR架构保证内生安全的一种充分性(但可能非必要),通俗来说就是,想要保证内生安全性质,DHR架构可行(但是DHR不一定是唯一的方法)。在诸如工程实践等不要求掌握原理的领域中,知道这一点其实已经足够让大家放心去用DHR架构了。

此外,对于书中所给出的“有记忆元信道随机性引理”以及定理证明中所用到的“联合典型序列”等相关概念,本文为了行文连贯性并未着墨讨论,感兴趣的朋友们可以自行研究~

如果本文中某些表述或理解有误,欢迎各位大神批评指正。
谢谢!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/375524.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

用例图(Use Case Diagram)

一、定义 用例图是从用户角度描述系统功能&#xff0c;是用户所能观察到的系统功能的模型图。 用例图是描述参与者与用例、用例与用例间关系的图。 用例图多用于 静态建模 阶段(主要是业务建模和需求建模)。 二、用例图构成 参与者(Actor)用例(Use Case)关联关系(Associatio…

架设游戏服务器租用价格?腾讯云和阿里云价格对比

游戏服务器租用多少钱一年&#xff1f;1个月游戏服务器费用多少&#xff1f;阿里云游戏服务器26元1个月、腾讯云游戏服务器32元&#xff0c;游戏服务器配置从4核16G、4核32G、8核32G、16核64G等配置可选&#xff0c;可以选择轻量应用服务器和云服务器&#xff0c;阿腾云atengyu…

STM32Cubmax DAC 采集

一、概念 DMA&#xff0c;全称为&#xff1a; Direct Memory Access&#xff0c;即直接存储器访问&#xff0c; DMA 传输将数据从一个 地址空间复制到另外一个地址空间。 当 CPU 初始化这个传输动作&#xff0c;传输动作本身是由 DMA 控制器 来实行和完成。典型的例子就是移动…

jmeter二次开发函数-生成身份证号

代码参考这个 java 随机生成身份证代码 Java的身份证号码工具类 pom文件添加 <dependency><groupId>org.apache.jmeter</groupId><artifactId>ApacheJMeter_core</artifactId><version>5.4.1</version></dependency><d…

在C++的union中使用std::string(非POD对象)的陷阱

struct和union的对比 union最开始是C语言中的关键字&#xff0c;在嵌入式中比较常见&#xff0c;由于嵌入式内存比较稀缺&#xff0c;所以常用union用来节约空间&#xff0c;在其他需要节省内存的地方也可以用到这个关键字&#xff0c;写一个简单程序来说明union的用途 struc…

Nacos安装,服务注册,负载均衡配置,权重配置以及环境隔离

1. 安装 首先从官网下载 nacos 安装包&#xff0c;注意是下载 nacos-server Nacos官网 | Nacos 官方社区 | Nacos 下载 | Nacos 下载完毕后&#xff0c;解压找到文件夹bin&#xff0c;文本打开startup.cmd 修改配置如下 然后双击 startup.cmd 启动 nacos服务&#xff0c;默认…

使用Volo.Abp读取Sqlite表中数据

书接上文&#xff1a;Abp 从空白的WebApplication中添加EntityFrameworkCore生成数据库 开发环境&#xff1a;.NET6、Volo.Abp 数据库&#xff1a;Sqlite 说明&#xff1a;纯属个人强行入门。我个人觉得按照官网的操作不舒服&#xff0c;所以自己研究着来&#xff0c;请读者…

[NOIP2017 提高组] 宝藏

[NOIP2017 提高组] 宝藏 题目背景 NOIP2017 D2T2 题目描述 参与考古挖掘的小明得到了一份藏宝图&#xff0c;藏宝图上标出了 n n n 个深埋在地下的宝藏屋&#xff0c; 也给出了这 n n n 个宝藏屋之间可供开发的 m m m 条道路和它们的长度。 小明决心亲自前往挖掘所有宝…

CTF-show WEB入门--web18

今天顺便也把web18解决了 老样子我们先打开题目查看题目提示: 我们可以看到题目提示为&#xff1a; 不要着急&#xff0c;休息&#xff0c;休息一会儿&#xff0c;玩101分给你flag 然后我们打开题目链接&#xff0c;可以看到&#xff1a; 即一进题目小鸟就死&#xff0c;然后…

FLIP解读

title: FLIP解读 mathjax: true toc: true date: 2024-02-06 17:22:20 categories: Machine Learning tags:CLIPMasked AutoencodersContrastive Learning FLIP由CLIP改进而来&#xff0c;其思想非常简单&#xff0c;通过在图片侧mask掉相当比例的patch&#xff08;无须重构pa…

【k8s系列】(202402) 证书apiserver_client_certificate_expiration_seconds

apiserver_client_certificate_expiration_second证书定义的位置&#xff1a;kubernetes/staging/src/k8s.io/apiserver/pkg/authentication/request/x509/x509.go at 244fbf94fd736e94071a77a8b7c91d81163249d4 kubernetes/kubernetes (github.com) apiserver_client_certi…

Mac上新版InfluxDB使用教程

一、简介 官网&#xff1a;influxdb 二、influxdb安装 建议使用Homebrew在 macOS 上安装 InfluxDB v2&#xff1a; brew install influxdb启动influxdb服务&#xff1a;brew services start influxdb 停止influxdb服务&#xff1a;brew services stop influxdb 查看是否启…

Compose | UI组件(十四) | Navigation-Data - 页面导航传递数据

文章目录 前言传参流程实例说明普通方式传值定义接受参数格式定义接受参数类型获取参数传入参数传参和接受参数效果图 结合 ViewModel 传递参数定义ViewModel在 navigation 定义 ViewModel 实例&#xff0c;并且传入 LoginScreen传入输入框中的值&#xff0c;并且跳转传值获取值…

Arthas使用教程—— 阿里开源线上监控诊断产品

文章目录 1 简介2背景3 图形界面工具 arthas 阿里开源3.1 &#xff1a;启动 arthas3.2 help :查看arthas所有命令3.3 查看 dashboard3.4 thread 列出当前进程所有线程占用CPU和内存情况3.5 jvm 查看该进程的各项参数 &#xff08;类比 jinfo&#xff09;3.6 通过 jad 来反编译 …

React+Antd实现省、市区级联下拉多选组件(支持只选省不选市)

1、效果 是你要的效果&#xff0c;咱们继续往下看&#xff0c;搜索面板实现省市区下拉&#xff0c;原本有antd的Cascader组件&#xff0c;但是级联组件必须选到子节点&#xff0c;不能只选省&#xff0c;满足不了页面的需求 2、环境准备 1、react18 2、antd 4 3、功能实现 …

Win32 SDK Gui编程系列之--ListView自绘OwnerDraw(续)

通过所有者绘制的列表视图(2) 所有者绘制列表视图的基础已在前一页中说明。本页将展示如何在所有者绘制列表视图中显示数据库表数据。 1、访问日志 正如在另一个页面中所述,本网站的访问日志目前是通过SQLite3数据库管理的。 以下是上述程序执行的结果。为…

OpenCV-30 腐蚀操作

一、引入 腐蚀操作也是用卷积核扫描图像&#xff0c;只不过腐蚀操作的卷积核一般都是1&#xff08;卷积核内的每个数字都为1&#xff09;&#xff0c;如果卷积核内所有像素点都是白色&#xff0c;那么锚点&#xff08;中心点&#xff09;即为白色。 大部分时候腐蚀操作使用的都…

基于ESP-WROOM-32的双串口通信并显示到OLED显示屏上

目录 开发板引脚图 Arduino环境配置1.ESP32开发版下载2.Arduino开发板选择 -> ESP32 Dev Module3.安装驱动库 接线图Arduino代码现象演示 开发板 ESP-WROOM-32 引脚图 Arduino环境配置 1.ESP32开发版下载 选择 esp32 by Espressif Systems 2.Arduino开发板选择 -> E…

搜索引擎DuckDuckGo代理指南

DuckDuckGo作為一款搜索引擎&#xff0c;同時擁有自己的流覽器&#xff0c;高度保護用戶隱私&#xff0c;使其有別於其他收集和利用用戶數據進行定向廣告的搜索引擎。然而&#xff0c;單獨使用DuckDuckGo並不能保證線上完全匿名。如果你想進一步保護隱私&#xff0c;那就需要使…

寒假作业5

TCP 1&#xff1a;提供面向连接的&#xff0c;可靠的数据传输服务 2&#xff1a;传输过程中&#xff0c;数据无误、数据无丢失、数据无失序、数据无重复 3&#xff1a;数据传输效率低&#xff0c;耗费资源多 4&#xff1a;数据收发是不同步的 5&#xff1a;TCP的使用场景&#…