探索网格环境下的一种新的容错模型
摘 要
在网格计算中，计算结果的正确性已经成为大规模分布式计算所关心的核心问题之一。恶意的计算节点以及第三方节点的攻击，计算的安全性和正确性已经成为了发展网格计算的瓶颈。不同的用户，不同的任务对计算正确性的要求程度也不一样。在网格环境中存在着大量的空闲的计算资源。本文以此为前提，在充分地分析了现有模型的优缺点的基础上提出了任务信任度的概念，并且提出了一种新的容错模型。在这个模型中充分利用了计算节点的信任度机制，这样不仅可以很好的提高容错能力，同时也使用户可以根据自己的情况在计算成本上有更多的选择，还可以使高信任度的计算节点有更好的回报，计算资源也有可能得到更好的有效利用。
关键词 网格计算；信任度；任务信任度；容错
1 引言
随着网络技术的迅猛发展，以及资源分布式应用的增加，网格技术已经日益成为现今计算机领域研究的热点。在网格技术的发展过程中，安全问题一直是束缚网格大范围应用的一个瓶颈。计算资源是网格环境中最重要同时也是最值得利用的资源之一，网格计算环境允许用户在不考虑地理位置的前提下，可以向网格环境提交并行或串行的计算任务。网格环境支持这些任务和作业在虚拟的计算机上运行。由虚拟组织完成对用户（代理）身份的认证，授权以及对任务的分配，而这一切对于用户来说都是透明的。但是网格环境的方便性同时也带来了很多网络环境所没有的安全隐患。
由于网格环境分布式的特点，网格中任务的传输以及计算节点都有可能发生物理的故障，致使计算任务没办法正常地执行下去。一些人为的破坏也不可避免，比如移动代理的安全性[1][2][3]，数据的完整性[4]以及一些恶意的计算节点在计算方为了达到某些目的对用户的数据作恶意地篡改，欺骗用户。在任务和数据的传输过程中，网络中恶意的第三方也可能对信息进行修改。
在网格环境中交互的双方主要是移动代理和负责完成计算任务的计算节点，也就是所谓计算的消费者和计算的提供者。对于计算节点，主要的安全隐患就是移动代理将会在计算方创建代理进程来执行可执行文件，而这个可执行代码如果在传输的过程中被恶意的第三方修改可能会造成对本地系统的破坏。而对于移动代理也就是用户这一方，它所关心的是它的数据和可执行的代码有没有被修改，任务在执行过程中有没有受到干扰以及计算结果的正确性。对于计算结果的正确性是考察整个任务在传输过程中以及解决过程中是否遭受攻击的一个很重要的标志,对于用户来说也是很重要的一个衡量标准。在网格环境中有些用户对计算的容错性有着很高的要求，也就是说即使在计算过程中出现了恶意节点或者其他的错误，用户仍然希望得到正确的结果。而且不同的用户愿意为其付出的代价也各不相同。网格最根本的目的就是在用户透明的环境下充分地利用网格中的资源，当然这也包括计算资源。基于这些考虑，本文在原有理论的基础上构造了一种新的容错模型。
本文的组织结构如下：第2 节介绍信任度模型的定义以及对现有模型的分析；第3 节对新的容错模型进行描述以及对新模型的评估；第4 节总结并对相关的方向提出展望。
2 现有模型的分析
信任在网格环境中是一个个体与系统相互融合的概念，个体与个体之间，系统与个体之间以及系统与系统之间都存在着信任关系。在本文中采用如下对信任的定义:
定义：信任是对一个实体身份和行为的可信度的评估，与这个实体的可靠性，诚信和性能有关，信任是一个取决于系统的概念，同时也取决于不同个体的经验，用信任度值来表示信任等级的高低，信任度值随实体的行为动态变化。
信任本身是一种以以往经验为依据来对事物进行判定的。在这个模型中，用信任度这个值来衡量信任的程度。对信任度值的表述包括以下两方面的内容：
第一方面是两个实体间的直接信任关系（本文称之为直接信任度）。这主要是指在网格环境中，这两个实体之间有过直接的交易，根据任务的完成情况，用户方会对计算节点的信任度给出相应的改变，并保存到本地用户。本地用户会维护一张表用来存储和本地用户有过直接交易的计算节点的信任度，并不断的动态的更新它。
第二方面是整个网格系统也会为每个计算节点给出它相应的信任度（本文称之为系统信任度）。如果一个新的计算节点加入到网格环境中，系统会对它设定一个初始值。根据这个计算节点对不同用户提交的任务的完成情况，系统会对这个值作相应的变化。例如节点对提交的任务计算结果正确，系统就增加信任度的值，反之就减小。这张表是由系统自身动态维护的。
在实际的网格应用中，对实体信任度的计算是通过对直接信任度和系统信任度进行相应的加权计算来得到的。而相应的加权值要按具体的系统来确定不同的加权公式。
在文献[4]中，提到了在网格环境中建立一种检测和衡量机制。它主要是通过对计算结果的第二次冗余运算来完成的，模型如图1 所示。决定一个节点的信任度的关键因素是看这个节点产生的结果的正确性。这个节点计算结果的正确性可以通过节点检测和一致性的衡量来进行判断。用户首先将任务分配给一个计算节点，然后通过正确性检测机制随机的选取另外一个计算节点，对计算任务重新执行，在选取的过程中要避免被选取的节点和原计算节点进行串谋攻击。然后检测它们的计算结果是不是一致。如果一致，我们就认为这个计算结果是正确的。如果结果不一致的话，就要再一次随机选取空闲的计算结点来执行这个任务，看结果和哪一个一致，如此下去直到判断出正确的结果。
但是这种方法有一些很明显的不足，首先，信任度模型的应用在这个模型中并没有得到良好的体现。其次，很显然对计算的容错性和准确性要求越高，用户所要付出的代价也就越大。现实生活中不同的用户对计算的容错性和正确性的要求和愿意为计算所要付出代价的大小是各不相同的。这个模型缺乏用户和虚拟组织之间对这一问题的交互。再有，在一个网格环境中，用一个节点来对另一个节点的正确性进行验证，它的一次成功率并不是一个概率很高的事情。这样就需要再一次重新选取节点。举个例子，如果在一个有100个节点的网格环境中，有两个是恶意的计算节点。那么两次都选中恶意节点的概率大约是万分之二，而选中恶意节点的概率则是百分之二。所以这对于一个真实的网格环境来说并不是一个理想的模型。
其他一些文章中也提到了对于信任度模型的构造以及对网格环境中空闲的计算节点的分配。文献[5]中是提供了一种信任度的计算方法，包括域内信任关系的计算和域间信任关系的计算。文献[6]中对于计算节点的能力，计算节点的计算时间以及反映程度等多种指标作了分类。使虚拟组织在选择计算节点的时候按各个指标对计算节点进行排序，选择排在前面的节点。这在网格环境中可能会造成某些信任度高的节点会经常被调用，而信任度低的节点却始终得不到利用。不仅造成网格中计算资源的浪费，也会使信任度高的节点信任度越来越高，而信任度低的节点得不到提高。
3 新的容错模型
对于网格上的用户来说，将任务提交给一个单一的节点来完成其风险性是很大的。因为如果一旦这个节点遭受攻击，那么用户的任务就要被错误的执行，以致得出不正确的结果，更有可能会遭受恶意的欺骗，有时会造成不可弥补的损失。
在网格计算的环境中，众多的计算节点将它们的资源共享，同时也共同的承担用户提交的任务。针对以往对用来验证计算结果正确性的模型所存在的一些不足，在这里提出了一种新的容错模型。它不仅可以在有恶意节点的情况下对用户提交的作业提供更准确地解决，同时它也可以动态的根据用户的需要来加大计算结果的可信度。
3.1新模型的构建
为了介绍这个新的容错模型，首先在这个模型中也采用了信任度机制。即对于每一个计算节点都建立它的信任度关系，它包括节点与节点之间的直接信任关系和整个网格系统中对每一个节点所给出的信任度值。信任度值的高低代表这个节点的可信程度的高低。因此，一个节点的信任度就等于它们之间的直接信任度与系统所给出的信任度的加权和。
为了更好地理解新模型，现引进任务信任度的概念。任务信任度（值）是指用户根据此任务的计算要求所提出的一个值。这个值的高低依赖于此任务的计算准确性和安全性的高低（也可以说是这个任务容错性的高低），还依赖于用户的支付能力（支付能力高的用户可以选择高的任务信任度值）。
本文提出的新模型如图2，用户不是仅仅建立一个移动代理，而是创建若干个移动代理的副本，每个代理在不同的节点上创建各自的进程，但是它们完成相同的任务。创建代理副本的数量由用户和虚拟组织来共同决定。用户在提交任务的同时，根据自身容错程度高低要求的不同提交相应的任务信任度值，这样就可以更加合理的，更充分地考虑用户的需求（用户要求的容错性越高，它所提出的任务信任度的值也就越高）。作业调度模块按照用户的要求选择节点，选择节点多少的依据是各个节点的信任度值之和等于或者刚好大于用户提出的任务信任度值。
T(u),T(i)应满足下列条件：T(u)≤T(max)； T(u)≤T1+T2+TnT(u)用户要求的任务信任度值；T(max)系统对任务信任度值所给出的最大上限；T1,T2 Tn是各个计算节点的信任度值。
网格环境中在很大一部分时间里有很多空闲的计算资源。在搭建网格的初期，要建立一个自训练的模型，来检测一下网格中在很长的一段时间内空闲资源的利用情况。从而得出空闲资源的占有率是多少，这样可以对用户提出所要求的任务信任度值给予一个限制，以免用户要求的任务信任度值过高，要求过多的计算节点为其服务，造成网格环境中计算资源短缺。所以对于不同的网格环境只要节点的数量选择合适以及信任度的模型建立的规范，对于系统来说并不会造成计算资源的浪费，而且用户也充分的发挥了自己的能动性。
3.2 新模型的分析和流程
在一个网格环境中可以认为值得信任的节点是占绝大多数的，恶意的节点仅仅是一少部分。也就是说如果让多个节点都来运算同一个作业，那么即使其中有恶意的节点，如果按照少数服从多数的原则，也会得到一个相对正确的答案，这样的确解决了某些问题。但是，例如：如果选择两个节点共同来为一个用户服务，它们的信任度分别是1和9，如果它们中有一个是恶意的计算节点。那么为了在这两个答案间得到区分，就不得不再寻求另外的计算节点了。在本人的模型中，希望引入信任度的机制。这样，再遇到这种情况时就选择信任度高的节点的结果来作为正确的答案。首先，对每个节点赋予信任度，在这里对于选择哪个运算的值为正确的结果时并不是完全依据少数服从多数的原则了，而是选择信任度值最高的结果。也就是说对每一个结果都赋予一个加权值，用户选择加权值高的结果作为正确的答案。例如：
因为T1+T3<T2+T4,所以在选择结果的时候认为信任度值高的为正确的结果，结果被确定为60.0。
为了更好地说明这个模型，在下面把从用户向网格环境提交任务到得出结果的流程作简要说明：
1. 用户首先向网格环境提交任务并且根据自身任务的需要给出相应的任务信任度值。
2. 网格环境根据用户提交的任务即时形成一个虚拟组织。虚拟组织根据用户的需求搜索资源节点，并把任务随机的分配给离用户相对比较近的资源节点（这些资源节点都完成相同的任务，并且各个节点信任度值的和等于或者大于用户提出的任务信任度值）。
3. 通过安全认证之后，用户代理在各个计算节点创建自己的代理副本，并创建进程。各个计算节点对任务进行计算，并将结果提交给虚拟组织。
4. 虚拟组织对结果进行分析，如果各个节点的计算结果都一致的话，则直接将结果提交给用户。如果结果不一致的话，则判定信任度值高的结果为正确结果，返回给用户。当然也存在例外的情况，就是对于两个不一致答案，它们的信任度值是一样的。如果一旦遇到这种情况，那系统就不得不再寻找新的计算节点来重新计算了。
5. 对用户使用过的计算节点的信任度值作相应的变动。对于这些节点的直接信任度增加，并将信任度值存储在本地。而系统信任度值也增加并存储在作业调度服务器一方。并要定期对网格环境中空闲资源的利用率做一定的监测，以便动态的调整对于计算节点的调度策略,防止造成资源的浪费或者资源的不足。
3.3 新模型的评估
对于计算结果的可信度可以作如下的考虑。从直观的角度上说，用户所选择计算节点的信任度值无非是由下面这三种组合，一是有很多低信任度的节点为它服务；二是有少数的高信任度的节点为它服务再或者是一种混合型的分布。所以用户选择的信任度值越高，从某种意义上为它计算的节点也就越多，它所被欺骗的概率也就越低。本文所提出的新模型有如下的特点：
1. 可以更有效地避免恶意节点攻击所带来的破坏性，提高容错性。原则上认为没有被恶意攻击的计算节点的计算能力是可靠的，因此，主要任务就是要避免对节点的恶意攻击所带来的影响。而在这个新模型中，可以很好地做到这一点。因为即使其中有个别的节点被恶意的攻击了，那首先这个节点的安全性是不高的，所以它的信任度值也不会很高（因为节点的高信任度值代表着节点的高可信性和高安全性），它的信任度值也不大会超过全部节点信任度值的总和。如果任务信任度的值大于恶意计算节点的信任度值，那么根据新模型知道至少有另外一个计算节点来计算提交的任务，从而可以有效地避免恶意攻击所带来的破坏性。如果用户所选择的任务信任度值小于或等于恶意计算节点的信任度值，并且正好选取了这个恶意节点，那么这种概率是非常小的，而且即使在这种最坏的情况下，也无非是目前网格环境所能达到的。
2. 在计算成本上用户可以有更多的选择。以前的模型是将任务提交给单个计算节点，而在本文的新模型中任务可能会提交给不止一个节点。费用主要是依据用户提交任务的作业量和用户所要求的任务信任度值来决定的（也就是用户对结果正确性，安全性要求的高低）。当然用户所选择的任务信任度值越高，它所涉及到的计算节点也就可能越多。因此用户可以根据自己的要求动态地提出自己所要求的任务信任度值。对于不同的任务以及自己愿意为其投入的情况，用户可以有更多更好的选择。这就更好地体现了虚拟组织和用户之间的动态交互。当然用户所要求的容错性越高，那么它所付出的代价也就越高了。对于一般的用户或者普通的任务，用户则可以降低所提出的任务信任度值，这样就更可以降低计算成本达到节约资金的目的。
3. 高信任度的计算节点有好的回报。对计算节点来说高信任度的节点在完成计算任务的时候由于其本身计算的高准确性和高安全性可能会带来的更多的计算消耗。由于本文中提出的模型是根据信任度值和工作量来计算费用的，所以这样对于信任度高的计算节点来说，从高的计算消耗中也会得到相应的回报。
4．计算资源可能更好的有效利用。由于网格环境中存在着大量空闲的计算资源，而且信任度值低的计算节点也可能会有很低的利用率。而在本文提出的新模型中，可以由多个计算节点为用户计算。计算节点选择的依据是各个计算节点信任度值的总和大于或等于用户提出的任务信任度值。所以在选择节点的时候信任度值低的节点被选中的概率同信任度值高的节点是相同的。这样不仅可以提高空闲资源的利用情况，更可以使一些信任度值低的节点得到充分的利用。
4 试验结果及测试数据
4.1 试验描述
首先，通过数组来模拟计算节点，我们设计用两个数组a[n],b[n]其中，a[n]代表这个节点信任度值，而b[n]代表这个节点是否是恶意节点。通过对这两个数组进行绑定来代表计算节点。试验主要分成三个部分，分别对500、1000和2000个计算节点进行模拟试验。同时，对于每种情况我们又分别将恶意节点的数量进行调整，分别各进行4组试验。恶意节点数分别为总节点数目的1%、2%、5%和10%。我们将各个节点的信任度值限制在1到20之间，而对于恶意节点的信任度值则限制在1到10之间。用户所提出的任务信任度值我们从1到20分别做20次试验，每次试验做100次，来判断在每一种情况计算成功的概率。
4.2 试验的步骤
1.首先取500个计算节点（后面的试验n可以分别取1000和2000），用数组a[n],b[n],n=500来表示。
2.用random函数分别生成500个1到20之间的随机数，作为信任度值赋值给a[n],对各个计算节点的信任度值进行初始化。
3.然后对恶意节点进行初始化，我们设b[i]=1的情况下此节点为正常节点，如果b[i]=-1我们则认为其为恶意节点。用random函数在1到500中随机产生m个数（ m代表恶意节点的数量，分别取总节点数的1%、2%、5%、10%）。然后我们将这些数作为数组b[]的下标，将它们赋值为-1。
4.我们对每个任务信任度值（从1到20）都作100次试验，每次试验开始前对数组a[],b[]进行重排。然后从a[0],b[0]开始向后循环，a[0]+a[1]+?+a[k]知道它们的和大于用户提出的任务信任度值。同时我们计算a[0]*b[0]+a[1]*b[1]?a[k]*b[k]看它们的结果是否大于0，如果大于0，则我们将计数器加1，进行100次试验，最后我们看计数器的值就可以判断计算结果成功的概率是多少了。例如，计数器count的值为98，那我们就可以推断在这种情况下，计算的成功率为98%。
4.3 试验数据及图示
首先我们选取500个节点，其中1%、2%、5%和10%的节点为恶意节点。任务信任度值分别问1到20之间的各个数值。下面我们通过曲线图分别来表示试验结果，如图4.1~4.4所示。
第一组试验结果：
图中横坐标代表用户提出的任务信任度值，纵坐标代表计算任务的成功概率，红颜色的虚线表示在一定数量的恶意节点的情况下，计算任务计算成功的概率，蓝颜色的节点则表示我们在试验中实际达到的成功概率。
4.4 试验结论
上面三组实验，分别对500、1000和2000个节点作了测试。并且在恶意节点数分别占1%，2%，5%和10%的不同情况下做了比较。
通过图示大家可以很明显的发现，如图4.1，只有两个节点低于理论值，也就是说在任务信任度值从1到20的这20组实验中，只有两组它们的计算任务的成功率低于理论上的99%，但事实上也都是非常接近的，为98%。而且，这两个节点都是在用户选择任务信任度值比较低的情况下产生的，当任务信任度值大于8以后，成功率基本上是保持在100%的。
当把恶意节点的数量由1%逐步升为2%、5%和10%以后，可以发现计算任务的成功率明显下降了，很难保持在100%这个水平，这是符合试验的逻辑原理的。但是，同时也可以看到计算任务的成功率仍然普遍高于理论上的成功率。再看后两种情况，当节点数取到1000和2000时，仍然可以发现上面所描述的试验结果。当然由于所选择的数值都是随机产生的，所以从曲线上我们也可以看到一些波动，但是总体的趋势是可以肯定地，可以基本说明这个模型在容错性方面的优越性。
5 总结和展望
在网格环境下，安全性是一个束缚网格发展的巨大问题。由于网格计算自身的复杂性，使得其安全问题也变得相对复杂。对于移动代理的安全性，计算节点的安全性无不困扰着我们。这篇文章仅仅是从一个方面入手，通过应用代理复制和信任度机制来提高虚拟组织的容错性和用户计算结果的正确性。但是对于在开放的网格环境中尤其是在恶意的计算节点上如何保证移动代理的安全性以及移动代理代码的完整性和数据的隐私性仍然是我们今后需要不断努力的方向。
