可信计算VI软件容错

2006年06月21日
前进中的可信计算（Ⅵ）：
软件容错
闵应骅
在第三篇中，我们曾经提到过，提高系统可信性的方法有故障防止、故障容许、故障删除和故障预报。容错（故障容许）技术已经研究了三十五年，在学术和产业方面都大有进展。软件容错是软件能检测系统中将要发生或已经发生的软件或硬件故障并从故障中恢复的能力。望文生义，不难理解，软件容错有两层含义：一个是用软件来达到容错的目的；一个是软件本身要容许软件故障。其实，对于可信系统，这二者都不可缺少。
用软件实现容错
任何一种容错系统体系结构，都离不开软件。这是不言而喻的。问题是在软件开发之前，在写软件设计规范时，往往无法预料所有可能的异常情况，让软件作出相应的处理。也许设计者压根就没有考虑到设备维修、故障检测等方面的问题。
今有一例。2005年12月7日《新民周刊》一则报道中写道：“51岁的刘奇心电图呈直线而被宣布死亡。推往太平间的时候，鬼使神差动了动手指，又正巧被身边的家人发现，否则等待他的很可能就是焚化炉。后来才发现，心电图机分别连接胸口、四肢的5根导线中竟然断了4根。”许多报刊和传媒对此发表评论，认为“机械化”是行医之患，医生为什么不仔细“望闻问切”。这些评论不无道理。但是，如果从另一方面想，心电图机的五根输入线断了四根，为什么机器没有反应呢？在它断了一根、两根时，是不是已经给出过错误的诊断呢？这些过去的诊断可信吗？依靠医生没有错，但是，医生“望闻问切”之后就不出错吗？一般地说，在可信系统中，人是重要的错误来源。人机要结合，才能构建高度可信的系统。如果心电图机的软件系统有故障检测和异常处理、有定期维修制度，这种事故是可以防止的。所以，用软件实现容错是必不可少的。问题是如何设计这种能够实现容错目的的软件。
软件故障的容许
人们可以对软件提出很高的要求，当然软件的开发经费也就理当应该大涨。但是，软件也是人编的，软件故障是不可避免的，只有多少之分。因此，要想设计出高度可信的软件,不但要容硬件错、操作错，还要容软件自身的错。
2000年美国总统选举之后的一场争论表明，按照美国宪法第15、19、24、26次修改版本，现有的投票技术和过程不能充分保证每一个合法选民都拥有投票的权利，并把他的票计算在内。因此，开发一个安全、正确、可靠和可信的投票系统是对当前技术的重大挑战。研究表明，N-版本编程提高系统的可靠性和安全性，从而可以提高系统的可信性。
在第三篇谈到容错系统结构时已经指出，提高可靠性的主要方法是冗余，包括设备冗余、信息冗余、时间冗余等等。设备冗余包括硬件冗余和软件冗余。软件冗余可能容忍两类故障：一类是硬件的瞬时性故障，例如空间的α粒子橦击可以使存贮器或寄存器的某一位瞬间改变。另一类是软件故障。但是，要从系统的响应来区别这两类故障是很困难的，因为它们的征兆非常相似。好在有一个办法容忍这两类故障，那就是软件冗余。
软件冗余技术主要分为两类：差异冗余和无差异冗余。差异冗余可以容忍设计故障。如果各设计是互不相同的，而且设计错误的发生相互独立，发生相同故障的可能性就很小。一个版本出某一个错，另一个版本就很少有可能出相同的错。因此，一般要求各设计组人员互不相同，而且互不通讯。设计的差异性也可以对不同数据产生不同的结果，而得到故障症候。无差异冗余可以处理某些物理故障。因为某个模块发生某个物理故障，其他模块不一定也发生相同的故障。能容忍软件设计故障的差异冗余有两种技术：N-版本编程和恢复块。
恢复块技术
七十年代中期,以B. Randell为首的英国Newcastle大学研究组提出了“恢复块”方案。在进程开始时设置恢复点,执行主模块。然后进行可接受测试。如果通过,说明正确;如果通不过,则返回恢复点,执行替换模块,再进行可接受测试。如果所有不同的替换模块都不成功,只得按出错而出口。
恢复块方案依赖于一个裁决者，那就是可接受测试，由它来决定同一算法不同实现的计算结果是否正确。带有恢复块的系统被分成故障可恢复的块。整个系统就由这些容错块组成。每一块包含至少一个一级模块、一个二级模块，和一个例外处理块，以及一个可接受测试模块。值得注意的是这个定义可以是递归的，即任何部件也可以是由一级模块、二级模块，例外处理块，以及可接受测试模块组成。可接受测试模块是为了确定模块计算结果的正确性，它必须尽可能的简单。程序在进入该主要模块之前，设置一个检查点，保护现场，以备程序返回时能够重新执行。程序在运行完此一级模块之后，进行可接受测试，检查其结果是否可以接受，以判断程序运行是否正确。如果正确，则往下走。如果不正确，则返回检查点，执行二级恢复块。一级模块程序有错误，二级恢复块可能没有错，程序可以正常运行下去。如果有更多的恢复块的话，该过程可以反复。如果到最后一个恢复块都不正确，程序只能做意外紧急处理，但这种可能性应该是微乎其微的。
恢复块方法，和其他软件容错方法一样，要求设计的差异性。同时要求对于同一个设计规范，能够设计出多个程序版本。恢复块系统常常是复杂的，因为它要求系统状态卷回，以尝试另一个模块实现。这一点当然也可以用硬件来实现。这种尝试和卷回的能力是使软件高度交易化。只有一个交易被接受以后，系统才罢休。这就可能使系统进入不正确或不稳定的状态。在分布式容错系统的检查点和恢复技术中也有类似问题，将在以后提及。
恢复块技术对某一个主要模块编制若干恢复块，在正常情况下，程序只执行主模块。这里的关键技术是检查点的设置和可接受测试的质量。可接受测试是一个由软件实现的检查程序，以检查由主模块或恢复块所产生的结果的差错。它常常是根据特定应用的信息，相当于一个可执行的软件断言。例如用数学的逆运算来检查。要检查一个开平方运算是否正确，只有把结果乘平方看是否得到原操作数就可以了。检查排序函数，只要检查结果是否满足降（升）序规则就可以了。检查一些物理量，例如速度、压力等，一般容易从结果发现荒谬的差错。检查应用状态序列可以容易地从实际的可能性来判断荒谬的结果。2005年底《广州日报》报导，广州一女士收到一张“电费通知单”：她家在2005年10月10日至12月8日的两个月内，共消费用电77万度，应缴纳电费高达47万元。对一个普通家庭来说，这显然是不可能的。据说是由于抄表数据传输出错引起的。其实这很容易在计算机中用可接受测试检查出来。
N-版本编程
也是在七十年代中期, 美国加利福尼亚大学洛杉矶分校的A. Avizienis等人提出了“N版本编程”方案。根据相同的软件规范,编出相互独立的N个版本,在几乎相同的起始点执行,最后用一个可靠的判决算法来决定程序的输出。和恢复块方法比较起来, 恢复块方法是一种动态冗余的方法,而N版本编程是静态冗余。
N-版本编程是将程序的N个版本并行地连接到程序入口，同时得到输入，并行执行，就像硬件容错中的N-模冗余一样。通过多个模块或版本不同的设计软件，对于相同初始条件和相同输入的操作结果，实行多数表决，防止其中某一软件模块/版本的故障，提供错误的服务，以实现软件容错。N版本的开发由不同的程序员完成，假定各程序的失败相互独立，就像在硬件冗余那样。为了保证N版本编程的独立性，对每一个版本，用不同的设计群体、不同的规格说明、不同的程序设计语言、编译器、和软件开发工具，防止设计群体之间的合作与协调。
N-版本编程企图沿析传统的N模冗余的硬件容错概念。在N-版本软件系统中，每一个模块都有N个不同的实现。每一种实现用不同的方式完成相同的功能。它们把结果送给表决器，以确定正确的回答，作为模块的计算结果。理想地，当然希望所有实现给出相同的结果，因而都是正确的。这种系统基于各版本设计的差异性，能够容许软件的设计故障。如果这N个版本是运行在不同类型的硬件上，软件的差异性就能保证，来防止共模故障。
N-版本编程对软件规范要求很高。因为它要求各版本之间，完全能交叉运行，软件决策者可以自由选择。在保存兼容性的同时，又必须有足够的灵活性，使软件编程者有创造差异设计的自由。因此，软件容错方法对软件设计规范提出很高的要求。
N-版本方法允许在各种故障存在的条件下，成功地屏蔽和忽略系统中的这些故障。但是，在差错出现之前检测和纠正这些故障仍然是很重要的，我们总希望各版本中的故障越少越好，已经发现的故障当然希望尽可能纠正。
N-版本编程和恢复块方法在航天、航空领域已有实际应用。对N-版本编程和恢复块方法的比较，我们可以看出，N-版本编程是在程序级的冗余，这N个版本是并行运行的，类似于静态冗余，并且允许各程序版本由于不同的程序员在不同的编程方式下有随机的差异，因而是相互独立的。而恢复块则应用于模块级，在正常情况下只运行主模块，类似于动态硬件冗余，主模块和恢复块之间的独立性是由设计得故意使它们尽可能不同而获得的。但是，另一方面，我们也看到，恢复块方法和N-版本方法的区别并不很大。传统的恢复块方法让各模块串行执行，直到通过可接受测试。现在，恢复块方法已经包括各模块的并发执行。而N-版本方法则在N模硬件上并发执行。在串行的复执系统中，多个版本复执的时间开销很大，对于实时系统尤为严重。并发系统需要昂贵的N个硬件和连接它们的通讯网络。这两种方法的另一个不同是仲裁器。恢复块方法要求每一个模块建一个可接受测试器，而N-版本编程只要一个表决器。恢复块方法假定程序员可以创造一个足够简单的仲裁器。两种方法技术上有不同，投资大小各异，工程上需要权衡得失，慎重选择。