Two generals are on hills either side of a valley. They each have an army of 1000 soldiers. In the woods in the valley is an enemy army of 1500 men. If each general attacks alone, his army will lose. If they attack together, they will win. They wish to send messengers through the valley to coordinate when to attack. However, the messengers may get lost or caught in the woods (or brainwashed into delivering different messages). How can they devise a scheme by which they either attack with high probability, or not at all?转载如下：
一个可信的计算机系统必须容忍一个或多个部件的失效。失效的部件可能送出相互矛盾的信息给系统的其他部件。这正是目前网络安全要对付的情况，如银行交易安全、存款安全。美国2001/9/11遭 恐怖袭击之后，大家普遍认识到银行的异地备份非常重要。纽约的一家银行可以在东京、巴黎、苏黎世设置异地备份。当某些点受到攻击甚至破坏以后，可以保证账 目仍然不错，得以复原和恢复。从技术的角度讲，这是一个很困难的问题。因为被攻击的系统不但可能不作为，而且可能进行破坏。国家的安全就更不必说了。对付 这类故障的问题被抽象地表达为拜占庭(Byzantine)将军问题。
拜占庭(Byzantine)将军问题
拜占庭帝国就是5～15世 纪的东罗马帝国，拜占庭即现在土耳其的伊斯坦布尔。我们可以想象，拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自的将军指挥。将军们只能靠通讯员 进行通讯。在观察了敌人以后，忠诚的将军们必须制订一个统一的行动计划。然而，这些将军中有叛徒，他们不希望忠诚的将军们能达成一致，因而影响统一行动计 划的制订与传播。问题是：将军们必须有一个算法，使所有忠诚的将军们能够达成一致，而且少数几个叛徒不能使忠诚的将军们做出错误的计划。
解决拜占庭将军问题的算法必须保证：
A．所有忠诚的将军必须基于相同的行动计划做出决策。
忠诚的将军按算法的要求行动，而叛徒则按他们自己的意志行动。算法要保证不管叛徒怎么做，条件A都能得到保证。忠诚的将军们不但要能达成一致，而且要同意一个合理的计划。这就要求条件B。
B．少数叛徒不能使忠诚的将军做出错误的计划。
这一条是很难做到的，因为"错误的计划"很难形式地加以定义。
我们考虑将军们怎么达成一致。设有n个将军，v(i)表示第i个将军送出的信息。每个将军用相同的方法把v(1),…,v(n)按某一种逻辑方式组合起来，形成一个行动计划。要满足条件A，将军们就必须用同样的方法来组合这些信息。而条件B要求使用的方法是健壮的。考虑最简单的情况，如果决定只有进攻和撤退两种可能， v(t)就是将军认为选择那一种行动最好，而最后的决定则基于多数表决。少数叛徒只有在忠诚的将军们几乎随机地（每一种选择的概率都是1/2）做出决策时才能影响决策，但既然每一种选择的概率都是1/2，那就不管怎么决策都不能说是坏的。
如果把第i个将军的信息v(i)送给其他将军。由于条件A要求每一个忠诚的将军得到v(1),…,v(n)相同的值，而叛徒将军可以给不同的将军送不同的值。为了使条件A得到满足，下面两条必须成立。
1．每一个忠诚的将军得到v(1),…,v(n)相同的值。
这就意味着忠诚的将军并不一定使用第i个将军送来的信息作为v(i)。因为第i个将军可能是叛徒。但这又可能使忠诚的将军送来的信息也被修改，因为忠诚的将军并不知道第i个将军是忠诚的，还是叛徒。如果要满足条件B，这是不能允许的。例如，我们不能因为少数叛徒说"撤退"，忠诚的将军说"进攻"，而做出"撤退"的决定。因此，要求
2．对每一个 i，如果第i个将军是忠诚的，其他忠诚的将军必须以他送出的值作为 v(i).
我们可以重写条件1如下。
1'。 对每一个 i，不论第i个将军是忠诚的，或是叛徒，任何两个忠诚的将军使用相同的值v(i).
条件1'和2都只牵涉到第i个将军怎么送一个值v(i)给其他的将军。因此，我们可以用司令送命令给副官的方式叙述如下：
拜占庭将军问题：一个司令要送一个命令给他的n-1个副官，使得
IC1 。所有忠诚的副官遵守同一个命令。
IC2。假如司令是忠诚的，则每一个忠诚的副官遵守他送出的该命令。
条件IC1和IC2称为交互一致性条件。注意，如果司令是忠诚的，IC1可以从IC2推出来。但是，司令并不一定是忠诚的。
这个问题比过去的容错更困难。因为过去的容错都是针对那样一些软硬件故障，其故障效果是固定的。而拜占庭故障却假定故障机是鲜活的，它可以做坏事。
拜占庭将军问题的可解性
（1）叛徒数大于或等于1/3，拜占庭问题不可解
如果有三位将军，一位副官是叛徒，如图1所示。当司令发进攻命令时，副官2可能告诉副官1，他收到的是"撤退"的命令。这时副官1收到一个"进攻"的命令，一个"撤退"的命令，而无所适从。
如果司令是叛徒，如图2所示。他告诉副官1"进攻"，告诉副官2"撤退"。当副官2告诉副官1，他收到"撤退"命令时，副官1由于收到了司令"进攻"的命令，而无法与副官2保持一致。
正由于上述原因，在三模冗余系统中，如果允许一机有拜占庭故障，即叛徒数等于1/3，因而，拜占庭问题不可解。也就是说，三模冗余对付不了拜占庭故障。三模冗余只能容故障-冻结(fail-frost)那类的故障,就是说，元件故障后，它就冻结在某一个状态不动了。对付这类故障，用三模冗余比较有效。
(2) 用口头信息，如果叛徒数少于1/3，拜占庭问题可解
注意，这里说"少于 1/3 "表明，要对付一个叛徒，至少要用四模冗余。在四模中有一个叛徒，叛徒数是少于1/3的。所谓口头信息，是指它满足三个条件：① 传送正确， ② 接收者知道是谁发的。③ 沉 默（不发信息）可以被检测。拜占庭问题可解是指：所有忠诚的副官遵循同一命令。若司令是忠诚的，则所有忠诚副官遵循其命令。我们可以给出一个多项式复杂性 的算法来解这一问题。算法的中心思想很简单，就是司令把命令发给每一副官，各副官又将收到的司令的命令转告给其他副官，递归下去，最后用多数表决。如图3所示。如果司令是忠诚的，他送一个命令v给所有副官。若副官3是叛徒，当他转告给副官2时命令可能变成x。但副官2收到{v, v, x} ，多数表决以后仍为v，忠诚的副官可达成一致。如果司令是叛徒，如图4所示。他发给副官们的命令可能互不相同，为x, y, z。当副官们互相转告司令发来的信息时，他们会发现，他们收到的都是{x,y,z}，因而也取得了一致。
（3）用书写信息，如果至少有2/3的将军是忠诚的，拜占庭问题可解
所谓书写信息，是指带签名的信息，即可认证的信息。它是在口头信息的基础上，增加两个条件：① 忠诚司令的签名不能伪造，内容修改可被检测。 ② 任何人都可以识别司令的签名，叛徒可以伪造叛徒司令的签名。一种已经给出的算法是接收者收到信息后，签上自己的名字后再发给别人。由于书写信息的保密性，可以证明，用书写信息，如果至少有2/3的将军是忠诚的，拜占庭问题可解。
如图5所示。如果司令是叛徒，他送"进攻"命令给副官1，并带有他的签名0，送"撤退"命令给副官2 ，也带签名0。副官们转送时也带了签名。于是副官 1收到{"进攻"：0，"撤退"：0,2}，说明司令发给自己的命令是"进攻"，而发给副官2的命令是"撤退"，司令对我们发出了不同的命令。对副官2也同样。
拜占庭将军问题的形式描述
考虑网络N，包含n个处理器，或叫游戏者，记为1,2,…,n，设n≥4。每一个处理器是一个交互的、概率的多项式时间图灵机。设网络N是完全的以私人通道连接，即每对处理器皆可互相通信而不能被其他处理器读取。该网络是同步的，即有统一的时钟。在d和d+1 个脉冲间送出的信息将在d+1个脉冲时收到。
游戏者i称为是好的，如果它遵循协议，即正确执行其程序，在适当的时间在适当的地点写入返回的值。i称为是坏的，如果它破坏了该协议。如果坏的游戏者被敌手选用和控制，则更一般的故障行为可能发生。敌手是一个算法，在一个网络中发作，腐化一定比例的游戏者。
定义：设A是一个概率算法，r为常数。A称为是一个r-敌手，如果A可以在任何n 游戏者的、运行任何协议 P的网络上发作，并且满足：
(1) A可以读取非私人通道上的任何通信链路。
(2) A可腐化任何t个游戏者。当A腐化i时，A可以读取 i的所有数据，并夺取i输出的执行写控制。
(3) 动态性： A可以在P的任何步骤上腐化游戏者。
(4) 急促性：A 读第d周期内通过非私人通道传送的信息。第d周期私人通道信息在第d周期送给坏游戏者。基于这些信息，A在第d周期腐化其他的游戏者（少于t个）。而且在第d周期把d周期信息送给新被腐化者。这一过程继续到腐化t个游戏者。在第 d+1个脉冲之前，A不需要选择在第d周期由坏游戏者送给好游戏者的信息。
(5) A 可以即时完成无限步的计算
有文章给出了拜占庭一致性算法，不要求亲信伙伴和预处理。给定私人通信链路，可望在常数时间内达成一致，如果同步网络故障机；异步网络，故障机。如果不能保证私人通信，可以用密码得到在容错和敌手有限计算能力的运行时间两方面最优的算法。在这种情况下，对异步网络也能容 n/3个故障。
可信计算中的拜占庭将军问题
可 信计算中必须考虑人为的故障，特别是人为恶意的攻击。这是保证计算安全性的基本出发点，在今天的网络环境下有非常重要的现实意义。拜占庭将军问题不过是保 持并行计算中数据一致性问题的一个抽象表达。一种抽象表达往往能把本质问题从繁琐的工程实现中提取出来，对于基础研究极其重要。工程师们常常被繁琐的工程 任务所左右，在保证安全的要求下要考虑的问题非常多，而忽略了提纲挈领的功夫。
在可信计算领域，过去考虑的故障-冻结模式，假定部件故障以后就"死"去了，不再工作了。现在我们必须考虑故障 - 活动模式，即部件故障以后，它可能仍然活动，甚至进行系统所有者所不希望它做的事情。这正是电子对抗中要着力研究的问题。
并 行计算中有两个基本问题：一个是控制的同步性；一个是数据的一致性。不论是并行的处理器，还是并行的线程，总需要保持某种程度上的同步，以期达到各个计算 部件之间的协同与合作。尽管这种同步可以是紧耦合，也可以是松散的耦合。另一方面，各计算部件之间的数据一致性也至关重要。例如银行系统在为用户存取款服 务时，人名的查找必须和存取款数量相对应，否则就错了。而这两件事可能由不同的计算部件或不同的时刻完成。而这种一致性常常能被故障，特别是恶意攻击所破 坏。敌人的攻击也常常是利用这一点。拜占庭将军问题只把数据简化为二值的0和1。当然，多版本的一致性不单是"进攻"和"撤退"这样简单的信息，但原理是一样的。
为了保持多版本的一致性，系统需要一定的时间。在这段时间内，系统还没来得及达成一致，系统可能有可攻击的脆弱之处。这段时间表现为故障潜伏期，即敌人的攻击不一定马上生效，系统在某一时机来到时就可能做出错误的响应。
解 拜占庭将军问题的算法给我们提供数据一致性的思路和算法。而在该算法中就有各位将军的同步问题。这些问题都为计算可信性的提高以启发。要解决拜占庭将军问 题需要四模冗余，硬件开销是很大的。所以，现在银行的异地备份并不都是四模冗余。这就看你的系统要求有多高的安全性，相对于那些投资，孰轻孰重。
从拜占庭将军问题解法可以看出，签名和认证对保证数据安全有节省硬件的效果。这些技术将在后文详细介绍。
关于"拜占庭将军算法"byzantine generals problem
一。拜占庭将军算法的背景：
对 于系统坏掉的风险，可以这样假设：我们的操作员可能会误操作、可能会被贿赂或背叛，系统本身可能就有木马程序，系统可能会被黑客或病毒占领，我们自己开发 的系统可能有漏洞，我们的开发人员可能会留下后门，这些都可以导致系统坏掉。因此，在这些假设在变成可能的残酷现实中，生存技术是应真正被采用的一种信息 安全技术。 入侵容忍体系就是生存技术中的核心。如果我们的网络和系统学会生存，那么也就是建立起一个完善的入侵容忍体系。 入侵容忍的技术在这样的假设空间中实现它的价值：个人的公开行为在一定的概率下是可预知的，系统在一定的概率下能够正确完成基本的功能。一定的概率并 不是指全部，所以，可以允许有错误，因此，入侵容忍还有对纠错理论的联想：即利用纠错码可以在一个错误百出、但有信道容量的信道中准确无误地传输数据，网 络系统就这样在错误中"生存"下来的，这就是我们说的入侵容忍体系，它的生存技术有两种实现方式：一是攻击响应的入侵容忍方法，它不需要重新设计系统，可 通过高效的检测系统发现异常，利用资源配置系统调整系统资源，并对对错误进行修补（修补系统）；二是攻击遮蔽的入侵容忍方法，它需要重新设计整个系统，并 通过冗余、容错技术，门槛密码学技术及"拜占庭"技术来实现。－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ －－－－
二。算法介绍： "拜占庭"技术，起源于拜占廷将军问题，这是入侵容忍体系的一个基本理论问题。 在1982年被提出的"拜占廷将军问题"在今天被许多学者看好，然而在商业上还没有体现其价值。特别是中国的产业界把它放在了一个被遗忘的角落。
描述如下：
几个师包围着敌人的一座城市。每一个师都由它自己的司令统帅，司令之间只能通过报信者互相通信。他们必须统一行动 。
某一位或几位司令可能是叛徒，企图破坏忠诚的司令们的统一行动 。
司令们必须有一个算法，使所有忠诚的司令能够达成一致，而且少数几个叛徒不能使忠诚的司令们做出错误的计划，即判国的将军虽然可以传递了虚假消息，也不会影响爱国的将军得到正确的决策。
拜占廷将军问题就是要让爱国的将军达成一致，而不是找叛国的将军。
我 们的入侵容忍体系就是这样，只要在众多服务器上得到的正确的计算结果，，那么我们就可以相信这个数据，而不需要去寻找到底谁是间谍。如果要容忍一个捣乱的 服务器，在数量上究竟会需要几个服务器？"拜占廷将军"问题可以为我们解答这个问题：在进行混乱真实消息的传播中，两个将军中一个判国，另一个肯定打败 仗，三个将军中如果有一个判国，则判国的将军一定有办法让两个爱国的将军不能达成一致，若再增加一个将军，既4个将军中如果只有一个判国，在不知道谁是判 国者的情况下，存在一种算法使将军们达成一致，实际上就是三个爱国的将军能够达成一致，而不管判国的将军如何捣乱。既4个将军的团体能够容忍1个叛国将 军。同样我们知道，当有t个判国者在捣乱而又无法找出他们的时候，存在一种算法或称做弹性协议，通过这种协议，能够保证爱国的将军达成一致。如果我们把能 够容忍t个叛国者的协议叫t弹性协议，学者证明了，不存在3t个将军下的t弹性协议而一定存在3t+1或以上将军下的t弹性协议。就是说要有3t+1个或 以上将军才能保证爱国的将军能够达成一致。既要想容忍t个判国者，必须保证总的将军的个数大于3t。 这样看来，"拜占廷将军"问题应用于信息安全就是入侵容忍体系的重要技术基础之一。以上讲述的仅仅是"拜占廷将军"问题中简化描述，加之以叙述的形 式，就是一个描述性的推理，实际上"拜占廷将军"问题程序计算的方法是很复杂的。 据荆老师的介绍，作为入侵容忍体系的理论问题，它可以应用在现实中。实验室开发的CA入侵容忍资料库系统就是应用的案例。当用户查找证书的时候，如何 保证得到的是最新的证书而不是过期的证书呢？如果一个服务器保留已经作废的证书欺骗你会如何呢。利用拜占廷法定数目团体系统，实验室很好地解决了这个问 题。即使 t个服务器捣乱，输出旧的证书，系统利用拜占廷协议，保证用户一定能够得到最新的证书。 由此看来，入侵容忍技术作为网络生存的重要技术，是保证网络和系统安全的一个新的概念和思路。网络的等级保护不仅仅是空间的，也应该是逻辑上的和技术 上的。深层防御就是在不同的地方，用不同的方式，建立多条防线，保护关键网络，入侵容忍技术在这个方面就有这不俗的表现。
最后对于如何更好的开发和利用生存技术、如何建立完善入侵容忍体系的问题，荆老师神情急切，他说，这应该是当前中国信息安全最需要的。－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
英 文解释：这个问题是在1982年由Lamport, Shostak, Pease提出，后少人问津。为了利于对"拜占廷将军"问题原意的理解和避免曲解，把英文解释奉上： Byzantine General Problem ——The problem of reaching a consensus among distributed units if some of them give misleading answers. The original problem concerns generals plotting a coup. Some generals lie about whether they will support a particular plan and what other generals told them. What percentage of liars can a decision making algorithm tolerate and still correctly determine a consensus?
三。具体分析：
1。叛徒数大于或等于1/3，拜占庭问题不可解。
情况一：A，B，C三个司令，C是叛徒。A发消息给B，C"进攻"，C发消息给B"撤退"（因为是叛徒）。B收到两个矛盾的命令，无法作出决策。
情况二：A，B，C三个司令，A是叛徒。A发消息给B"进攻"，发消息给C"撤退"（因为是叛徒）。B。C收到不同的命令。
2.用口头信息，叛徒数少于1/3,拜占庭问题可解.
口头信息三条件
传送正确
接收者知道是谁发的
沉默(不发信息)可被检测
什么叫可解？
IC1：所有忠诚副官(B.C，指消息接受者)遵循同一命令。
IC2：若司令(A，消息)是忠诚的，所有忠诚副官遵循其命令可 以证明，多项式复杂性算法OM(m)可以解决拜占庭问题(L Lamport, R Shostak, and M Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 1982, 4(3))
如果记容忍t 个叛国者的协议叫t弹性协议（即，在t弹性协议存在的情况下，可以胜利），则：
Ø 当n=3 时，不存在1弹性协议Ø 当n>=1,不存在 t>=n/3的t弹性协议n如果记容忍 t个叛国者的协议叫t弹性协议，则：Ø 当n=3 时，不存在1弹性协议Ø 当n>=1,不存在 t>=n/3的t弹性协议当n>=1,不存在 t>=n/3的t弹性协议－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－OM（m）：m个叛徒OM（0） ：发送者将其命令送给每个接收者每个接受者使用这个值，如果没有收到就认为是" 撤退" 。n OM(m),m>0
Ø
Ø
发送者发送他的值给每个接收者 发送者发送他的值给每个接收者如果第i 个接收者获得的值是vi， 接收者i执行算法OM(m-1) 发送vi给n-2 个其他的接收者
第i个接收者会收到从不同 n-1人发来的n-1个值， 取多数认同的值就可以
n OM(m),m>0
Ø
Ø
发送者发送他的值给每个接收者 发送者发送他的值给每个接收者如果第i 个接收者获得的值是vi， 接收者i执行算法OM(m-1) 发送vi给n-2 个其他的接收者
第i个接收者会收到从不同 n-1人发来的n-1个值， 取多数认同的值就可以
3。用书写信息，至少两个忠诚，拜占庭问题可解
在口头信息的基础上, 书写信息又增加了两个条件
忠诚司令的签名不能伪造，内容修改可检测
任何人都可以识别司令的签名, 叛徒可以伪造叛徒司令的签名
SM(m)算法
接收者信息收到后，签上自己的名字，再送给别人
用书写信息, 只要有两个忠诚的司令, 拜占庭问题就可解－－－－－－－－
可以证明，算法SM(m)可以解决m个叛徒的拜占庭问题。
SM(1):如A是叛徒。A给B发"进攻"，给C发"撤退"命令（都被A签名）。B比较从C发来的命令（"撤退"，该命令被C签名了）知A是叛徒。C比较从B发来的命令（"进攻"，该命令由B签名），知A是叛徒。
情况2：B是叛徒。A给B，C发"进攻"命令
四，来自原作者的相关翻译
一支拜占庭的军队在敌人的城堡外驻扎，该军队有多个将军，他们各自控制自己的部队，并能相互之间进行通信通过messager。观察敌人后他们必须决策。但是，在这些将军中存在叛徒，会阻止将军们的意见达到一致。因此，必须有一个算法，来保证：
1。所以忠心的将军都执行同一决策。
2。以少数存在的叛徒不能使将军们作出怀的决策。
要判断什么样的决策是坏的，很难。因此，我们只讨论如何让将军们作出决策。
每 个将军观察敌人，将自己的观察后的决策通知其他人。设v(i)是第i个将军的观察后的决策。每个将军以某种方法将v(1),v(2)....v(n)综合 起来（可看作是一个n维函数）得到一个计划。上面的条件1，很容易实现，只有所有将军采用相同的方法来综合v(1),v(2)....v(n)的信息。条 件2的满足还有更强的方法。
如果每个将军要做的决策只是进攻或撤退(attack or retreate)，设v(i)是第i个将军所做的认为最好的决策。那么从v(1),v(2)....v(n)到最后的计划的映射方法，就可以是多数原 则，即看attack or retreate的决策谁多，就认为是最好的。但是这种情况下，占少数的叛徒还是有机会影响最后的计划，在下面的情况下：如果忠心的将军的意见从数量差不 多分成两派。在这种两种意见的支持率不相上下的情况下，无论哪种意见都难称得上是好的。
但是条件1还是有问题，因为叛徒可能给不同的将军发不同的信息。即对第i个将军而言v(k)与第j个将军的v(k)可能是不同的（如果k是叛徒的话）。
因此，对条件1还要满足：
1。每个忠心的将军要获得相同的v(1),v(2)....v(n)
2.如果第i个将军是忠心的，则他发给每个忠心的将军的信息必须被用作v(i)。
对条件1重写（1。每个忠心的将军要获得相同的v(1),v(2)....v(n)）：
1a。两个忠心的将军使用相同的v(i)。
1a和2是第i个将军发送的信息的条件，在这样的限制下，我们来考虑一个将军是如何向其他将军传送消息的。可以将这个问题描述为一个司令向他的副官发命令，得到Byzantine Generals Problem.司令必须将他的命令发送个n-1个副官，并且：
IC1所有忠心的副官遵守相同的命令。
IC2如果司令是忠心的，每个忠心副官遵守他的命令。
因此，对于最初的问题（一支拜占庭的军队在敌人的城堡外驻扎。。。。），第i个将军向其他将军发送自己的决策可以看作是第i个将军发出"用v(i)作为我的决策"的命令，到可相对视为其副官的n-1个将军。
No comments:
Post a Comment