（计算机科学与技术专业论文）面向星载计算机瞬时故障的软件控制流错误检测技术.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 随着空间探测活动的内容越来越丰富，星载计算机的作用也越来越重要。但 是在空间环境中，硬件瞬时故障给星载计算机带来的可靠性问题非常突出。传统 上一般采用专门的抗辐照器件来建造空间星载计算机。但是，抗辐照器件价格昂 贵，难以供货且性能不高，而c o t s ( c o m m e r c i a l o f f - t h e s h e l f ，商用现货) 器件 具有成本低、性能高的优势并且不受国外进口的限制，因此，可以用c o t s 来建 造高性能星载计算机。然而，c o t s 器件本身的抗辐射能力有限，还需要用面向硬 件的软件容错技术( s h i f t ，s o f t w a r ei m p l e m e n t e dh a r d w a r ef a u l tt o l e r a n c e ) 进行加 固。 面向硬件瞬时故障的软件容错技术一般是通过复制计算并比较结果的方法来 检测发生在硬件中的瞬时故障，在编译的时候插入冗余计算的指令，可以简单高 效的实现容错，所以容错编译成为面向硬件瞬时故障的软件容错中比较流行的一 种实现方法。 本文首先在深入分析了当前控制流检测技术原理及其优缺点的基础上，提出 并实现了一种新的指令级控制流检测算法c f c p t ( c o n t r o lf l o wc h e c k i n gb yp a t h t r a c k i n g ) 。该算法巧妙地采用两个变量同时对程序的执行路径进行跟踪，在保证 检错能力的基础上，相对于传统上只采用一个变量对执行路径进行跟踪的算法， 能获得更好的性能。然后，针对控制流检测算法r s c f c ( r e l a t i o n s h i ps i g n a t u r e sf o r c o n t r o lf l o wc h e c k i n g ) 中存在的最大基本块数受机器字长限制的问题，本文提出 并实现了用分段的方式对结点标签进行设置的改进方法，该方法不仅保持了原算 法的检错能力和性能，而且极大地改善了算法的现实可用性。最后，本文采用故 障注入技术对算法的容错能力和性能进行验证，实验结果表明：c f c p t 算法的平 均错误覆盖率达到了9 8 8 ，平均性能开销为6 0 5 ；e r s c f c 算法的平均错误覆 盖率达到了9 8 7 ，平均性能开销为5 9 3 。 主题词：面向硬件故障的软件容错，c o t s 器件，星载计算机，瞬时故障， 控制流检测，故障注入 第i 页 国防科学技术大学研究生院工学硕士学位论文 a b s t r a c t w i t hm o r es p a c ee x p l o r a t i o na c t i v i t i e s ，o n b o a r dc o m p u t e rp l a y sam o r ei m p o r t a n t r o l e h o w e v e r ，t r a n s i e n th a r d w a r ef a u l t sb r i n gg r e a ti m p a c t so nc o m p u t e ri ns p a c e e n v i r o n m e n t s t r a d i t i o n a l l y ，r a d i a t i o n h a r dd e v i c ei su s i n gf o ro n - b o a r dc o m p u t e r b u t r a d i a t i o n - h a r dd e v i c ei se x p e n s i v ea n dd i f f i c u l tt op u r c h a s e ，o nt h eo t h e rh a n d ，c o t s ( c o m m e r c i a l - o f f - t h e s h e l f ) i sm o r es u i t a b l et oa p p l y i n gt os p a c ec o m p u t e rw i t ht h e a d v a n t a g e so fl o wp r i c ea n dh i g hp e r f o r m a n c e h o w e v e r ，c o t si sl i m i t e di nc a p a c i t y o fa n t i r a d i a t i o n ，s oi tm u s tb er e i n f o r c e db ys h i f t ( s h i f t ，s o f t w a r ei m p l e m e n t e d h a r d w a r ef a u l tt o l e r a n c e ) g e n e r a l l y ，s h i f td e t e c t sh a r d w a r et r a n s i e n tf a u l t sb yd u p l i c a t ec o m p u t i n ga n d c o m p a r i n gt h er e s u l t i n s e r t i n gi n s t r u c t i o n sf o rr e d u n d a n tc o m p u t i n gc a nr e a l i z ef a u l t t o l e r a n c es i m p l ya n de f f e c t i v e l yd u r i n gc o m p i l i n g ，s of a u l tt o l e r a n c eb yc o m p i l e ri sa g o o di m p l e m e n t a t i o no fs h i f t i nt h i sp a p e r ，w es t u d yo nd e s i g n i n gc o m p i l i n g f a u l t - t o l e r a n ta l g o r i t h mw i t hg r a t ef a u l td e t e c t i o nc o v e r a g ea n dh i g hp e r f o r m a n c e w i t ha ni n - d e p t hu n d e r s t a n d i n go ft h ea d v a n t a g e sa n dd i s a d v a n t a g e so fc u r r e n t f a u l t t o l e r a n tt e c h n o l o g i e s ，ac o n t r o lf l o wc h e c k i n ga l g o r i t h m c f c p t ( c o n t r o l f l o wc h e c k i n gb yp a t ht r a c k i n g ) i m p l e m e n t e db yp a t ht r a c k i n gi sp r o p o s e d c f c p t u s i n gt w ov a r i a b l e sf o rt r a c k i n gp a t ha tt h es a m et i m eh a v eah i g h e rp e r f o r m a n c et h a n t h et r a d i t i o n a lo n eu s i n go n l yo n ev a r i a b l e w ep r o p o s e da n di m p l e m e n t e da ne n h a n c e d a l g o r i t h mb a s e do nr s c f c ( r e l a t i o n s h i ps i g n a t u r e sf o rc o n t r o lf l o wc h e c k i n g ) r s c f ci sac o n t r o lf l o wc h e c k i n ga p p r o a c hf o rh a r d w a r et r a n s i e n tf a u l t s i nr s c f c ， t h em a x i m u ms u mo fb a s i cb l o c k si sl i m i t e db yt h el e n g t ho fm a c h i n ew o r d t h r o u g h t h e s e g m e n t e de n c o d i n go fs i g n a t u r e s ，o u ro p t i m i z e dm e t h o ds o l v e st h ep r o b l e m e f f e c t i v e l y c o m p a r i n g w i t h r s c f c ，0 1 1 1 a l g o r i t h mi m p r o v e s t h e a v a i l a b i l i t y r e m a r k a b l y a c c o r d i n gt ot h el a wo fd a t ef a u l ts p r e a d i n gi np r o g r a m ，w eb r i n gu pa o p t i m i z e ds t r a t e g yt h a td e c r e a s et h es u mo fc h e c k p o i n ti ne d d ir e a s o n a b l y i no r d e rt o p r o v ef a u l t t o l e r a n c ec a p a b i l i t ya n dt h ep e r f o r m a n c eo ft h ea l g o r i t h mp r o p o s e di nt h i s p a p e r ，w ec a r r i e do u ts i m u l a t i o ne x p e r i m e n tb yf a i l u r ei n j e c t i o nt e c h n o l o g y s i m u l a t i o n r e s u l ts h o wt h a tt h ea v e r a g ev a l u eo ff a u l td e t e c t i n gr a t ei s9 8 8 而t i lc f c p t ，a n dt h e a v e r a g ep e r f o r m a n c eo v e r h e a da r e6 0 5 ：t h ea v e r a g ev a l u eo ff a u l td e t e c t i n gr a t ei s 9 8 7 w i t he r s c f c a n dt h ea v e r a g ep e r f o r m a n c eo v e r h e a da r e5 9 3 k e yw o r d s ：s h i f t ，c o t s ，o n b o a r dc o m p u t e r ，t r a n s i e n tf a u l t ， c o n t r o lf l o wc h e c k i n g ，f a i l u r ein j e c t i o n 第i i 页 国防科学技术大学研究生院工学硕士学位论文 表目录 表5 1控制流检测算法性能开销。4 7 表5 2 未检测出错误输出4 7 表5 3 程序运行时间超时4 7 表5 4 故障没有影响程序运算最终结果4 7 表5 5 故障被所采用的技术检测出来4 8 表5 6 故障被操作系统检测出来。4 8 第1 i i 页 国防科学技术大学研究生院工学硕士学位论文 图目录 图2 1控制流图7 图2 2 非法分支类型8 图2 3c f c s s 示例10 图2 4c f c s s 的别名问题1 2 图2 5串联操作1 2 图2 6d s m 算法在基本块中添加检测指令示意图1 3 图2 7d s m 算法示例1 3 图2 8 无法检测的控制流错误。1 4 图2 9 添加检测基本块内部控制流错误检测指令示意图。1 4 图2 1 0y a c c a 算法在基本块中添加检测指令示意图1 6 图2 11无法检测的非法分支。：17 图2 1 2e d d i 算法中基本块依赖图及副本依赖图2 0 图3 1c f c p t 算法在基本块中添加检测指令示意图2 3 图3 2 检错示例。2 4 图3 3无法检测的控制流错误2 5 图3 4 添加t e s t l 断言后的基本块示意图2 5 图3 5c f c p t 算法。2 6 图3 6 非法分支类型2 7 图4 1 r s c f c 算法在基本块中添加检测指令示意图3 1 图4 2 改进后标签的设置方法。3 2 图4 3 进一步改进后标签s 各段位数。3 5 图4 4e r s c f c 算法。3 9 图4 5 非法分支示意图4 0 图4 6e r s c f c 算法位置信息确定示例4 2 图5 1 矩阵乘法的控制流图4 9 图5 2 快速排序的控制流图5 0 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文作者签名：冰日期：1 年 学位论文版权使用授权书 1 月形日 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目 学位论文作者 作者指导教师签名：j 骘牛 日期。1 引脑日 国防科学技术大学研究生院工学硕士学位论文 第一章绪论 1 1 课题背景 前苏联在1 9 5 7 年1 0 月4 日成功发射了人类历史上的第一颗人造卫星“斯普 特尼克”迈出了人类探索太空奥秘具有重大意义的一步，接着又于1 9 6 1 年4 月1 2 日，成功地把第一位宇航员尤里力口加林送入太空，随后美国也相继实施了阿波罗 登月计划。人类在上个世纪对太空的探索拉开了人类探索太空的新序幕，尤其是 在我国历史性的实现载人航天，并于今年成功实现了宇航员太空行走的重大突破， 世界范围内的空间探测热潮又再度兴起。 随着空间科学探测活动的扩展和深入，空间探测器执行的科学任务越来越复 杂丰富，对高性能计算能力的需求十分迫切。例如n a s a 的g l a s t ( g a m m a - r a y l a r g ea r e as p a c et e l e s c o p e ) i l 刁j 项目被设计用来观测宇宙深处的伽马射线暴 ( g a m m a r a yb u r s t ) 。在g l a s t 计划中，每秒将产生5 1 0 m b 的原始观测数据， 至少需要5 0 m i p s 的计算能力来对大量的原始观测数据进行处理和实时分析，才 能够及时地定位伽马射线暴的方位【4 j ，从而及时收集到有意义的探测数据。n a s a 的n g s t ( n e x tg e n e r a t i o ns p a c et e l e s c o p e ) 项引5 j 的目标是研制下一代空间望远 镜。n g s t 使用高分辨率的数字成像技术，产生的数据将超过5 0 m b s 。如果要把 这么大量的数据发达到地面以后再进行处理，那么会给空地通讯带来很大的负担， 所以在获取到数据后需要在太空实时的进行压缩、存储以及必要的图像处理等操 作，也需要高性能的计算机来完成。还有n a s a 的a m r s ( a u t o n o m o u sm a r sr o v e r s c i e n c e ) 1 6 j 旨在研制能够在火星上自主导航和分析岩石样本的火星车。由于火星距 离地球非常遥远，最远时电磁波需要4 0 分钟才能从地球往返火星，在这么大的通 讯延迟情况下，如果要让地面发出信号来控制指挥火星车的行动将是不可行的。 所以要求火星车必须实现高度的自主导航，而复杂的路面信息收集、分析和判断 需要高性能的计算能力。可以看出这些太空科学探测很需要高性能、高可靠性的 星载计算机来完成。 然而在太空环境中，星载计算机的运行暴露在各种带电粒子构成的恶劣环境 中，很容易受到这些空间辐射的影响。这些高能带电粒子主要来自银河系的银河 宇宙线、太阳爆发时的太阳宇宙线、被地磁场捕获的地球辐射带粒子和由于磁扰 引起的磁层沉降粒子 7 1 。当空间计算机中的硬件系统受到这些带电粒子轰击时，电 子元器件中的p n 结就会瞬时充放电，从而造成存储信息发生逻辑状态上的翻转， 比如原先存储的1 翻转成0 。宇宙空间的强辐射环境对星载计算机中的电子元器件 危害十分突出。据有关资料【8 】统计表明，自1 9 7 1 年至1 9 8 6 年，国外发射的3 9 颗 第l 页 国防科学技术大学研究生院工学硕士学位论文 同步卫星，因各种原因造成的1 5 8 9 次故障中与空间辐射有关的故障有l1 2 9 次， 占故障总数的7 1 。由辐射造成的故障中，有6 2 1 次故障是s e u 造成的，占辐射 总故障的5 5 。可见，提高星载计算机的可靠性，已经成为太空科学探测的一个 关键环节。 为了增强计算机的可靠性通常都会考虑采用故障规避( f a u l ta v o i d a n c e ) 、故 障移除( f a u l tr e m o v f l ) 和故障容忍( f a u l tt o l e r a n c e ) 三大类方法： 1 故障规避：在系统的设计和维护阶段通常采用这种技术。在系统的设计阶段， 从需求分析、系统定义、系统设计到代码编制，每个步骤都必须最大限度地保 证其合理性和正确性，从一开始就考虑避免缺陷的引入。然而，在设计阶段完 全避免错误是不可能的。 2 故障移除：在系统的测试和维护阶段通常运用这一技术。通过模拟系统真实的 工作环境，查找和发现系统中存在的缺陷，并最终把缺陷排除。但是这种方法 存在的缺点是测试覆盖率很难达到1 0 0 ，不可能穷尽所有的错误。 3 故障容忍：这一技术运用于系统运行过程中，当检测出故障后，通过采用恢复 点保存或者多版本结果投票等方式使系统不受故障的影响而继续执行。这种方 法需要故障检测技术的支持。 在以上提到的三种方法中故障容忍( 即容错) 技术一直是构建高可靠计算机 系统非常有效的技术手段。因为无论在开发过程中使用了多么严格的故障规避和 故障移除技术，总还会存在没有被发现的缺陷。甚至有时候并不是系统本身存在 问题，而是由于周围的电子噪声使系统发生故障。所以在对可靠性要求非常高的 应用中，大多都会使用容错技术。在容错研究领域中，经常会提到故障( f a u l t ) 、 错误( e r r o r ) 和失效( f a i l u r e ) 三个基本概念。它们存在多种描述形式，我们这 里介绍一种有代表性的定义1 9 j ： 故障：有时也被称为缺陷( b u g ) ，是由外部环境或人为因素引起的有可 能导致系统发生错误的事件。 错误：系统某一个部分由于故障而产生了非正常的行为或状态被称为错 误。错误可以在运行过程中通过特定机制检测出。错误如果不加以排除， 最终将导致系统失效。错误还可能在系统中传播引起其它的错误。 失效：系统在一定的条件下偏离了它预期设计的要求或规约。 从以上对故障、错误和失效的定义，我们可以得出以下三种延迟： 1 ) 故障延迟：从系统中发生故障到故障被系统中的事件触发导致系统错 误之间的时间间隔。 2 ) 错误延迟：从发生错误到错误被检测技术发现之间的时间间隔。 3 ) 容错延迟：从发现错误到排除故障，或者最终失效之间的时间间隔。 第2 页 国防科学技术大学研究生院工学硕士学位论文 我们可以通过一个简单的例子来说明从故障到失效的变化过程i j 。“固定0 ( s t u c k a t 0 ) 故障是一种硬件故障，表示某位永远都只能保持0 的逻辑状态，而 不能表示逻辑1 。如果机器是在发生故障的那一位上写o ，这时故障并没有导致错 误的产生；但是如果机器要在此位上写l 的话，错误就被触发了。随后这个错误 如果被系统的检测机制检查出来，并通过容错技术恢复正确了，那么系统就会正 常的执行下去；如果错误没有被检测出来，就会导致系统的死机或崩溃，系统就 出现了失效。 抗辐照器件是经过专门设计和实现用来容忍发生在硬件中的瞬时故障的计算 机器件，其一般是通过硬件冗刽1 1 。1 7 】来实现，即采用副本器件的方法，通过比较 原器件与副本器件的执行结果来判断执行是否发生错误。抗辐照器件可以实现较 高的可靠性，但是存在以下缺点： 1 ) 设计非常复杂，研制周期很长，产业规模和产量都很小，价格非常昂贵。 2 ) 抗辐照器件的性能通常落后于同时代的c o t s 器件很多代【1 8 以9 1 。 3 ) 由于采用硬件冗余的方法实现容错，抗辐照器件的芯片面积通常都要成倍 增加，带来了功耗的迅速增长。 4 ) 由于存在应用于航空航天等准军事领域的潜力，一些抗辐照器件还属于限 制出口的产品，难以批量采购。 综合考虑，商用器件( c o t s ，c o m m e r c i a lo f f t h es h e l f ) 【2 0 】由于其高性能， 低价格和低功耗的特点，非常适合用来制造高性能的星载计算机。但c o t s 器件 本身的故障容忍能力和故障规避能力有限，尤其是在有大量宇宙射线等电子噪声 的空间环境下，c o t s 器件的可靠性将受到很大的挑战。为了弥补c o t s 器件在 容错能力方面的不足，需要在c o t s 器件上通过软件容错技术来进行加固。 目前，对于面向硬件瞬时故障的软件容错技术已进行了比较广泛的研究，有 代表性的控制流检测算法是s t a n f o r d 大学c r c 实验室提出的c f c s s ( c o n 仃0 1f l o w c h e c k i n gb ys o f t w a r es i g n a t u r e s ) 1 2 1 】，数据流检测算法e d d i 2 2 1 和e d 4 1 1 2 3 】；普林斯 敦大学提出了s w i f t l 2 4 】容错技术；还有法国t i m a 实验室提出的控制流检测算法 d s m l 2 5 1 。 虽然目前在面向硬件的软件容错技术上的研究已经取得了一些显著的成果， 但是现有容错算法的检测覆盖率和性能并不理想。所以在星载信息处理这种对计 算性能和可靠性要求都很高的应用领域，研究检错能力更强、性能开销更小的容 错算法是很有必要的。本文的工作目标就是设计出能够满足星载计算机应用需求， 而且在检测能力和性能开销上都比较理想的控制流检测算法。 第3 页 国防科学技术大学研究生院工学硕士学位论文 1 2 课题主要研究内容及成果 本文在现有软件检测技术和错误恢复技术的基础上，提出检测覆盖率更全面、 容错能力更强和开销更小的新技术。具体的研究内容包括以下几个方面： 1 )目前典型的面向硬件瞬时故障的软件容错技术分析： 2 ) 硬件瞬时故障造成程序控制流错误的软件检测技术； 3 ) 硬件瞬时故障造成程序数据流错误的软件检测技术； 4 ) 故障恢复技术。 主要研究成果有： 1 ) 提出并实现了一种新的控制流检测技术c f c p t ，该技术采用对程序执行 路径进行跟踪的方法对控制流进行检测，可以有效地检测出发生在程序控 制流中的绝大部份错误。 2 ) 针对r s c f c 算法中存在的最大基本块数受机器字长限制的问题，提出了 分段设置结点标签的思想，使改进后的算法在不增加检测指令数量并保持 检错能力的前提下，在3 2 位机器上能够加固程序的最大基本块数比原算 法提高了3 0 多倍。如果机器字长为6 4 位，程序的最大基本块数将达到 2 1 8 。相比于原算法，改进后的算法的现实可用性得到了显著的提高。 3 ) 采用故障注入技术对算法的检错能力和性能进行了验证。 1 3 论文的组织结构 全文共分七章，各章组织如下： 第一章简要介绍课题研究的概要情况，包括课题的研究背景、研究内容与成 果。 第二章介绍本文研究的相关基础理论，包括硬件瞬时故障特征分类与分析， 程序控制流检测技术，程序数据流检测技术，故障恢复技术。 第三章给出了一种基于路径跟踪的控制流检测技术。 第四章介绍了当前控制流检测技术r s c f c 的基本原理，分析了r s c f c 的缺 点，给出了r s c f c 算法的改进思路和进一步改进方法。 第五章采用故障注入实验对算法进行模拟验证。 第六章对全文进行概括总结。 第4 页 国防科学技术大学研究生院工学硕士学位论文 第二章相关技术背景 本章将首先介绍空间辐射对计算机硬件造成的各种故障，然后简要介绍硬件 实现的各种容错技术，接下来对现有面向硬件故障的软件检测技术进行分析，其 中包括对程序控制流错误和数据流错误的检测技术的分析，最后简要介绍故障恢 复技术。 2 1 空间辐射对硬件系统的影响 在大气层外，电子设备完全暴露在宇宙射线的辐射之下，在空间环境中计算 机遇到的最主要困难就是会受到宇宙射线辐射的影响。宇宙射线由各种高能带电 粒子组成，比如高能质子流和仅射线等。这些高速运动的带电粒子穿透能力很强， 当某个带电粒子轰击到半导体电路中，就会在很短的距离上引起半导体内部电荷 的瞬时运动，从而引起充放电，改变在半导体p n 节中存储的电量，使得数据的逻 辑状态发生改变。 由于处理器实现形式基本是m o s 型集成电路，m o s 型集成电路对带电粒子 的轰击特别敏感，中子辐射对其也有影响，所以星载计算机的硬件系统并不是完 全可靠的，恶劣的空间辐射环境很有可能导致硬件发生故障。对于m o s 型集成电 路而言，空间辐射引起的失效模式主要有两种，即总剂量效应( t i d ) 和单粒子事 件( s e e ) 【2 6 1 。 总剂量效应( t i d ) ：高能带电粒子多次反复轰击半导体电路，从而使半 导体电路产生s i s i 0 2 界面态，并在栅氧化层内不断地积累正电荷，当电 荷累积到一定程度所引起的失效。总剂量效应是由于带电粒子对半导体电 路的不断累积结果，与具体带电粒子的种类和能量无关，是一种累积效应。 单粒子事件( s e e ) ：单粒子事件是指当高能粒子穿透微电子器件时释放足 够的能量引起晶体管的状态转变的事件。主要的单粒子事件可以概括为以 下三种： 1 ) 单粒子翻转( s i n g l ee v e n tu p s e t ) ：单粒子翻转事件是一种随机的 事件，当高能带电粒子轰击电子元器件时，就会造成p n 结瞬时充 放电，从而导致存储单元信息发生翻转，比如某存储单元本来内 容为“0 ”，通过翻转其中存储的内容变成了“1 。s e u 对微处 理器影响的主要对象包括指令、操作数和一些状态控制寄存器等。 当s e u 对指令码造成影响时，就会产生非法指令，最后会导致异 常和程序运行结果出错。当s e u 对指令的操作数造成影响时，会 造成计算结果出错，最后会导致程序运行结果出错。当s e u 对控 第5 页 国防科学技术大学研究生院工学硕士学位论文 制和状态寄存器造成影响时，主要会造成程序执行的异常。 2 ) 单粒子闩锁( s i n g l ee v e n tl a t c h u p ) ：由于高能带电粒子的轰击导 致半导体电路内部电极之间的短路，引起电流突然增大，此时电 路的状态被锁定，不能被输入信号所改变。如果及时发现并且断 电后重新加电，电路可以自行恢复；如果持续时间过长、电流过 大则可能直接造成器件的烧毁。 3 ) 单粒子烧毁( s i n g l ee v e n tb u r n o u t ) ：如果带电粒子对半导体进行 轰击时，能量达到一定程度就会使瞬时产生的能量超过器件本身 的承受范围，造成器件的烧毁。单粒子烧毁是永久性故障，无法 通过重复执行代码或重启电路来恢复。 单粒子翻转是引起计算机系统失效的主要原因。研究表明，计算机系统 中8 0 9 0 的失效都是由这种故障引起的【2 7 - 2 8 。这种故障的影响持续时间短 暂，没有损坏内部硬件电路，而且在电路中相同位置重复发生率极低，可以 通过重复执行出错程序代码来恢复。本文所做的研究就是针对硬件瞬时故障 的情况。 2 2 硬件容错技术 采用硬件实现的容错技术大多通过硬件冗余来实现。硬件冗余是用增加硬件 设备的方法容忍故障造成的影响，使得计算机系统在发生局部故障时，系统仍能 正常工作。 硬件容错的典型例子是三模冗余机f l 割j ( t m r ) 2 9 】。t m r 是把三个完全一致的 运算电路的输出与一个比较电路相连，对三者的输出采用少数服从多数的原则决 定最终的输出。较早应用t m r 进行计算机系统可靠性设计的代表有在上个世纪六 十年代研制的土星五号( s a t u r nv ) 1 3 0 j 导航计算机。该计算机使用了t m r 技术， 三个处理器的运算结果被比较，选取两个相同的结果作为最终的结果。后来出现 了利用并行体系结构进行冗余计算的容错方法，如在a r s m t e 3 1 1 和s r t r 3 2 】方案 中利用微处理器中已有的并行处理机制进行冗余计算，同时增加了专门比较结果 的电路d c q ( d e p e n d e n c ec h a i nq u e u e ) 3 3 】进行容错。还有w a t c h d 0 9 1 3 4 - 3 5 】采用辅 助的专用处理器来检测总线上数据的正确性。目前的商业系统很多也使用冗余技 术实现硬件差异性，如波音7 7 7 飞机的主飞行计算机( p r i m a r yf l i g h tc o m p m e r ) 就同时使用了a m d 、i n t e l 和m o t o r o l a 三种处理器【3 7 1 。 目前在内存管理和系统互联部分，已经广泛采用了e c c ( e r r o rc o r r e c t i n g c o d e ) 、e d a c ( e r r o rd e t e c t i o na n dc o r r e c t i o n ) 和奇偶校验码等硬件实现的纠错 检错机制。但是这些技术却很少用于处理器的其它单元。 第6 页 国防科学技术大学研究生院工学硕士学位论文 虽然，硬件容错的容错能力比较好，然而这些技术需要对硬件体系结构进行 比较大的修改，而且开发硬件容错系统的成本昂贵、周期长。 2 3 硬件错误的软件检测技术 在程序执行的过程中，s e u 故障不仅会影响程序指令的操作数部分，也可能 改变指令的操作码，所以瞬时故障会造成程序的数据流错误和控制流错误。研究 检错能力强、性能好的故障检测算法是容错技术必不可少的一部份。本节将对现 有典型的软件实现的控制流检测技术和数据检测技术进行介绍和分析。 2 3 1 软件实现的控制流错误检测技术 2 311 程序控制流图的概念 图2 1 控制流图 控制流故障检测方法一般将程序代码分成若干基本块1 3 引，每个基本块由一系 列指令构成。除最后一条指令外，其它指令都不能是分支指令。除第一条指令外 其它指令都不能是分支指令的目标。即基本块内部的指令只能是顺序执行。一个 程序的控制流可以由基本块以及由基本块之间的跳转关系表示的边构成的控制流 图表示，如图2 1 所示。对于程序控制流图中的每个结点v i ，我们可以定义它的后 续结点集s u c ( v i ) 和前趋结点集p r e d ( v i ) ，如果控制流图中有一条从v i 到v j 的边，则 v i 属于s u c ( v i ) ，同样，如果控制流图中有一条从v j 到v i 的边，则v j 属于p r e d ( v i ) 。 在程序的执行过程中，如果一条分支在控制流图中没有与之对应的边，则说明这 条分支是非法的b r ，嚣和b r n o 是条件型分支中分别对应条件成立与不成立的两个分 支，如果条件判断结果是要执行分支b ，但是在执行的过程中却执行了b r n o ，则 说明此时b r n o 是错误分支。像这种非法或错误分支的出现就说明在程序的执行过程 第7 页 国防科学技术大学研究生院工学硕士学位论文 中发生了控制流错误。 2 312 用软件实现控制流检测的典型技术 ( a ) 图2 2 非法分支类型 为了说明控制流检测算法的检错覆盖率，这里把结点间的非法分支归纳为图 2 2 所示的八种类型。在图2 2 ( a ) 中，结点v i 不是结点v i 的前趋结点；在图2 2 ( b ) 中，结点v i 是结点v i 的合法的前趋结点。 一、德克萨斯大学奥斯汀分校提出的控制流检测算法c c a 3 卅为每个基本块分 配两个标签b i d 和c f i d 。b i d 标识基本块，不同的基本块b i d 也不相同；在控 制流图中对于拥有同一前趋结点的所有结点的c f i d 值都相等。 算法在每个基本块的前面插入两条指令： b ：= b i d ； p u s h ( s ，c f i d n e x t ) ： 算法在每个基本块的后面插入两条指令： b r ( c f i d c p o p ( s ) ) e r r o r ； b r ( b # b i d ) e l t o r ； c c a 算法在程序的执行过程中通过在基本块前端的b ：= b i d 指令把当前基本 块的b i d 标签存进变量b ，基本块后端的b r ( b c b i d le r r o r 指令，把变量b 的值和 当前基本块的b i d 进行比较，相等的话说明基本块前端的b ：= b i d 指令没有被跳 过。反之，则说明有非法分支跳到转b ：= b i d 指令后面的指令，以此来检测从其他 第8 页 国防科学技术大学研究生院工学硕士学位论文 基本块跳转到基本块内部的非法分支。 算法中用一个先进先出的队列来存储基本块的c f i d 标签，而且这个队列最多 只能同时存储二个元素。在基本块前面插入的指令p u s h ( s ，c f i d n e x t ) 把控制流图中 合法的下一跳结点所对应的c f i d 存进队列尾部；在基本块后面插入的指令 b r ( c f i d c p o p ( s ) ) e r r o r ，让队列首部所存的c f i d 出队并把它与当前基本块的c f i d 标签进行比较来判断跳转是否和控制流图一致。在程序开始执行之前要对二元队 列所存的元素进行初始化，把队列初始化成首部元素为第一个基本块的c f i d ，尾 部为空。 c c a 能够检测出图2 2 中的8 种控制流错误，但是算法要加入队列操作以及 设置和验证变量的代码，用到的检测指令相对比较多，使得检测指令本身发生错 误的概率增大。算法无法检测在条件型分支中发生的错误分支。 二、e c c a 【4 0 】算法是在c c a 算法的基础上改进过来的，它对c c a 中的基本块 标签b i d 进行了改进，将它设为大于2 的素数，而且不再需要c c a 算法中的c f i d 标签。在基本块首部和尾部插入的指令也比c c a 少了很多，分别为： 一2面萧丽b而idla面 1 ) = 一 ilj ( 耐m o d 肋) ( 耐l o d 2 ) 一 i d = n e x t + i d b i d ( 2 ) 式( 1 ) 和式( 2 ) 中的i d 为全局变量，初始化为程序第一个基本块的标记b i d ， 算法通过式( 1 ) 和式( 2 ) 中对变量i d 的更新来进行控制流检测，并把控制流的 错误转化成式( 1 ) 中分母为o 的非法操作，从而实现对非法分支的检测。 式( 1 ) 放在基本块的前端，式中分母中的0 d m o d b i d l 表示对i d 取b i d 模后， 再进行一次逻辑反，如果i d 取b i d 模的结果不为0 ，对结果取逻辑反后就变成0 ， 如果结果为0 ，取逻辑反后就为l 。分母中的耐m o d 2 表示对变量i d 取2 模的结果。 式( 2 ) 放在基本块的后端，式中的i d b i d 表示对i d b i d 的结果进行两次 逻辑反，例如，i d b i d 不为o ，经过一次取逻辑反后，就会变成0 ，再经过一次 取逻辑反后就会变成1 。n e x t 为从当前基本块可到达的所有后继基本块标签b i d 的乘积。 当非法分支跳转到基本块前端时，这时由于变量i d 的值是源结点所有合法的 后续结点的b i d 标签的乘积，而当前结点不是源结点的后续结点，所以当前结点 的b i d 标签不是i d 的因子，从而i dm o db i d 不会为o ，那么经过取逻辑反后就变 成o ，这样式( 1 ) 的分母就为0 ，检测出控制流错误。 当非法分支跳入基本块内部时，当程序执行到基本块后端的式( 2 ) 时，由于 这时的i d 并不是当前结点的b i d ，所以i d b i d 不会为0 ，取一次逻辑反后就变成 第9 页 国防科学技术大学研究生院工学硕士学位论文 0 ，再取一次逻辑反后就变成l ，所以执行完式( 2 ) 后i d = n e x t + 1 ，由于n e x t 是 素数之间的乘积，所以n e x t + i 肯定为偶数，那么在跳转到下一个基本块时，在 式( 1 ) 分母中的i dr o o d2 会为0 ，从而检测出控制流错误。 e c c a 能够检测的控制流错误类型和c c a 相同，但是在每个基本块中插入的 检查指令比c c a 少，在很大程度上克服了c c a 算法中存在的时间和空间开销大 的缺点，而且在e c c a 算法中加入的检测指令不包含跳转指令，这样减少了检测 指令本身发生错误的可能性。但是，算法中多次用到了乘、除法操作，时间开销 还是比较大。而且对于比较大的程序，算法中的变量n e x t 有可能会发生溢出， 导致检测失败。 三、s t a n f o r d 大学c r c 实验室提出的c f c s s 算法【2 0 j 在程序编译时为每个基 本块分配一个各不相同的数字标签s 并且生成控制流图中各个分支对应的源结点 和目标结点之间的d ，d = s 。叫嗽o s d c s t i i l a t i 叩。在c f c s s 算法中用一个称为g s r ( g e n e r a l s i g n a t u r er e g i s t e r ) 的通用寄存器来存放程序执行时生成的动态结点标签g 。基本 块的开始处加入两条指令。前一条指令根据在刚刚执行完的结点中更新得到的动 态结点标签和存放在当前结点中的d 生成当前结点的动态标签g 。后一条指令把 当前结点的动态标签g 和编译时存放在结点中的静态结点标签s 进行比较，相等 则说明无控制流错误发生，不相等则跳转到错误处理例程。如图2 3 所示，现假定 v l 到v 2 是一个合法的分支并且执行完v l 后控制流是正确的，所以g = s i 。从v l 跳转到v 2 后，g = g f i ) d 2 = s l od e = s l o ( s i os 2 ) m s 2 ，因此在v 2 开头处的第二条指令 判断出当前的控制流仍然正确。但是，如果从v l 跳到v 4 ，那么g = g 0 c h = s l e c h = s 1 0 ( s 3 0 s 4 ) s 4 ，所以在v 4 开头处的第二条指令判断控制流错误。 s l = 1 0 11 ， s 2 = d 2 = = 1 分支 、 r g = g 0 d 3 b rg s 3e r r o r 八 勤 g = g o d 4 b rg s 4e r r o r b 4 图2 3c f c s s 示例 第1 0 页 国防科学技术大学研究生院