（计算机科学与技术专业论文）安全关键软件故障自动诊断与隔离方法研究.pdf

国防科学技术大学研究生院学位论文 摘要 安全关键软件在当前国家和国防现代化担负的责任重大，一旦出现失效将会 为安全、经济乃至生命带来重大损失，但由于自身及其环境的复杂性，软件故障 难以完全避免。因此，在软件出现故障后能够快速有效的诊断并隔离故障，使得 软件能够持续关键任务的运行就显得十分重要。 本文针对安全关键软件的特点，提出了种软件故障自动诊断与隔离的框架 a f d i f ( a u t o m a t i cf a _ u l td i a g n o s i s 锄di s o l a t i o nf 舳e w o 出) ，通过插装二进制代码收 集程序运行时数据，对样本数据进行分析和抽象，并利用布尔函数学习机制自动 定位软件故障，最后自动产生故障隔离代码并插装到程序中，能够有效避免故障 的再次发生，从而提高软件的可靠性、安全性和可生存性。 论文主要在以下几个方面进行了研究： 研究了软件故障自动诊断和隔离方法的实现原理和技术路线，提出一种软 件故障自动诊断与隔离的框架a f d i f ，包括软件运行时的数据获取、通过 测试运行方式的数据样本采集与抽象、基于布尔函数学习机制的故障自动 诊断以及基于补丁插装的故障隔离等主要步骤。 研究了软件故障的自动诊断与定位技术，利用插装技术在程序指定位置插 装指令，实现软件运行数据的收集：研究基于布尔函数学习机制的故障诊 断算法，通过分析数据样本，最终找到导致程序发生故障的“关键”变量， 从而定位故障原因。 研究了基于代码插装的软件故障隔离技术，实现程序指令执行的定向跳 转，从而避免了缺陷代码被执行而导致故障的实际产生。 基于上述理论和技术，设计实现了故障自动诊断与隔离支持工具原型，最 终结果表明，该方法能够准确定位故障原因，并及时有效的进行故障隔离。 主题词：安全关键软件，故障诊断，故障隔离，布尔函数学习，二进制代码 插装 第i 页 国防科学技术大学研究生院学位论文 a b s t 】r a c t s a f e t ) ，c r i t i c a ls o r w a r ei i lt h ec o u n t r y sc u r r e n tm t i o n a id e f b 璐em o d e m i z a t i o n s h o u l d e r 也eh ea _ v yr e s p o 璐i b i l i t ) ，i ft h e ya 他f 越l ，w k c hw i l lr e s u l ti i lm 面o rl o s so f s e c u r i t y ，e c o i l o m i c 锄de v e nl i f e a st l l eh i g hc o m p l e x i t yo fs a f b t yc r i t i c a ls o 行l 眦 t h e m s e l v e s 髓dt h ee n v i m 衄e n t ，f t w a r ef 砌t s 锄i eh 锄dt 0a v o i dc 0 珈【p l e t e l y t h e r e f o r e ，“i sv e r yi m p o r t a n tf o rl l st 0m a k e “p o s s i b l e 也a tt h ec r i t i c a lt a j 盘c 锄b e s u s t a i n e db e f o r c 蠡l u l t sa r er e p a i r e d ，谢t l le 圩e c l i v ef ；“td i a g n o s i sa n ds a f ef a u l t i s o l a t i o n b 嬲e do nt h ef b a n 鹏so fs a f 嘶c r i t i c a ls o f h a r e ，t h i sp a p e ri n 仃c d u c e sa 觑蛆e w o r k f o ra u t o m a t i cf a u l td i a g n o s i s 龃df a u n i s o l a t i o n ，w l l i c hn a l i l ei sa f d l f t 1 1 r o u g l l m s e n i n gb i i l a r yc o d ei n t ot h ep g 豫m ，t l l em e t l l o dc o l l e c t sm n t i i n ed a t a t h e n i t 锄a l y s e sd a t a 砒l dl o c a 饴sf a u l tb ym e a n so fb o o l e a nl e 枷n gm e c h 撕s m f m a l l y ，t l l e m e t h o d 、v i l la u t o m a t i c a l l yp r o d u c ei s o l a t i o nc o d e s 锄di 璐e nt l l e mi i l t ot h ep r o g r a i n i t c a n e 丘e c t i v e l yp r e v e n t t 1 1 ef a u l tr c c 岫g ，也e r e b yi 1 1 c r e 锯i n gs o f t 、 伽e 陀l i a b i l i 锣，s a f 色t y 锄ds u r v i v a b i l i t y o nm i sb a s i s ，m yr e s e a r c hm a i m yw 鹤洫f o l l o w i l l gr e s p e c t s ： 陆s t ，p 印e rf o c u so nt l l ep 血c i p l e sa i l dt 1 1 et e c l l i l i c a lr o u t e so fs o 小a r ef a u h d i a g n o s i sa n di s o l a t i o n 脚【e t h o d s o nt h i sb a s i s ，p a p e ri n t r o d u c eaf h 吼e w o r k o f s o r w a r ef a u l ta u t o m a t i cd i a g n o s i sa n di s 0 1 a t i o nt l l a t 瑚衄e da f d i f ，i n c l u d i n g t h er e a l i z a t i o no fs o f t l a m n t i m ed a t aa c q u i s i t i o nm e t h o d ，m e t h o dn l a td a 瞳a s 缸l p l i n ga n da b s 仃a c ti i l 恤ec o u r s eo ft e s t ，f 矗1 1 l td i a g n o s i sm 甜妁db a s e do n b o o l e a nl e 删n gm e c l 觚s ma 1 1 df a u l ti s o l a t i o nm e 吐l o db 嬲e d0 na u t o m a t i c p a t c hi i l s t n l f n e n t a t i o n s e c o r l d ，ir e s e a r c ho nt l l e r w a r e sa u t o m a t i cf 旮u hd i a g n o s i sa l l dp o s i t i o i l i n g t e c h n o l o g y ，i r i c l u d i l l gu s eo fi i l s t r u m e n tt e c h n o l o g ym t h ep m c e d u r e ss p e c i f i e d l o c a t i o ni 邶e r tm s t 九】c t i o n s ，w b j c h 痂t 0r e a l i z es 0 m 血gd a 协 c o l l e c t i o n ；a tt l l es 锄et i m e ，p a p e ri n t r o d u c e sf a u l td i a 粤l o s i sa l g o r i 吐l mb 嬲eo n b 0 0 l e a i lk 锄i n gm e c l l a l l i s m ，t l l | 的u g l la 1 1 a j y s i so fd a l as 扰1 p l e s ，觚d l l l t i m a t e l yf i n d ”k e y ”v a r i a b l e st h a t 晡n go n 筋1 1 1 1 i r d ir e s e a r c ho nf a u l ti s o l a t i o nb 嬲eo nc o d em s 协】m e n t a t i o na n dr e a l i z et l l e d h c t i o n a jj 硼叩p r o c e d u r c s ，也e r e b ya v o i 曲1 9m ei n l p l e m e n t a t i o no fc o d e d e f i c i e n c i e s f 砌l y ，b a s e do nt h ea _ b o v et h e o 巧c e r t i f i c a t i o n 孤dt e c h n i c a is u p p o n ，i d e s i 班a n dr e a l i z ep r o t o 帅et o o lo ft h ef h m e 、o r k t h er e s u l t ss h o wt h a t 龇 i n e n l o dc a na c c u r a t e l yp o s i t i o i l i n gt l l ec a u s eo f 恤m a l f u i l c t i o n ，a i l d l et i m e l y a n de f l j e c t i v ef a t l l ti s o l a t i o n k e yw o r d s ：s 疵够c r i t i c a ls o f h 帕r e ， f a u nd i a 朗o s i s ，f ；m ni s o l a t i 傩，b 0 0 l e 姐 l e 缸n i i 唱，b i l l a 巧c o d ei n 蛐m m e n t a t i o n 第i i 页 国防科学技术大学研究生院学位论文 表目录 表3 1软件缺陷严重等级8 表4 1p h o e n i ) 【核心组件2 4 表4 2p h o e i l i x 输入输出组件2 4 表4 3中间表示与体系结构和运行时的相关程度2 5 表4 4 单元类描述2 7 第1 i i 页 国防科学技术大学研究生院学位论文 图目录 图3 1软件失效机理示意图9 图3 2a f d i f 结构图。1 0 图3 3 数据结构格式1 3 图3 4 数据样本收集过程1 5 图3 5 代码隔离示意图18 图3 6 故障处理流程1 9 图4 1p h 0 _ e n i 】【基本架构图2 2 图4 2p h o e l l i x 编译平台体系结构2 3 图4 3中间表示的抽象程度2 5 图4 4p h o e l l i x 单元层次结构2 6 图4 5 数据采集示意图2 9 图4 6 反格3 0 图4 7 布尔函数学习算法3 0 图5 1 补丁自动生成方法3 4 图5 2 故障隔离指令插装示意图3 5 图5 3 程序定向跳转示意图3 7 图6 1原型工具基本框架图3 9 图6 2 插件层次图4 0 图6 3原型工具前台界面示意图4 1 图6 4i i l s t n 蛐e n t e x e 程序流程图4 2 图6 5 数据收集指令插装结果4 3 图6 6 故障数据收集结果一4 3 图6 7t s u i t e x e 程序流程图4 4 图6 9 反格项数据结构4 6 图6 1 0 布尔函数学习程序流程图：4 7 图6 1 l 补丁指令插装结果示意图4 9 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：塞全差熊筮佳敛睦宜动途断生匾离友洼硒究 学位论文作者签名：登；里蠢日期：2 口伊7 年，2 月，多日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：塞全差鳇塑性筮瞳自盘趁逝生匾直左鎏堑窥 学位论文作者签名：建西 作者指导教师签名： 日期：2o 。7 年，j 月，孑日 嘴：3 一年l 讲咿 国防科学技术大学研究生院学位论文 第一章引言 1 1 论文的选题背景和研究意义 安全关键系【l j s c s ( s 疵锣c r i t i c a ls y s t e 瞄) 是指系统功能一旦失效将引起生命、财产的 重大损失以及环境可能遭到严重破坏的系统。在国家和国防现代化建设中，计算机软件已 广泛应用于各类安全关键系统，如航空航天器、武器装备控制、核设施控制、通信系统等， 并充当核心和灵魂的角色。如果这些软件发生失效，将会为生命、经济和国家安全等方面 带来极大损失。提高安全关键软件可靠性和安全性的一种重要途径是在开发阶段采用更加 规范和严格的方法，例如：使用形式化设计与验证方法；采用软件容错设计；进行全面、 高效的软件测试；实施软件可靠性工程；等等。然而即使如此，人们在实践中发现，软件 可靠性往往比硬件低一个数量级，软件故障或失效仍然难以避免。这一方面是因为软件作 为人类智力产品，本身复杂度高、分析难度大，其科学原理和工程规律远未得到充分认识； 另一方面随着现代社会的高速发展，安全关键软件日益庞大和复杂，代码规模急剧膨胀， 带来了可靠性和安全性的下降、投资增加、研发周期加长、风险增加。同时安全关键软件 的应用环境也更加复杂和恶劣，从陆地、海洋到天空、太空，安全关键系统的使用环境不 断地扩展和更加严酷，由于安全关键软件往往具有分布、实时、动态等特点，软硬件之间 紧密耦合并互相影响，以上的原因使得软件故障在开发阶段难以预测。因此，在安全关键 软件部署后，如何有效诊断产生故障的原因，以及把可能出现的故障与软件正常运行隔离 开，使软件在完成维护过程并重新部署前( 即出现的故障被完全修正前) 依然能执行某些 关键任务，目前已成为提高安全关键软件安全性、可靠性和可生存性的一个重要研究内容。 软件故障诊断、隔离的目标是为了确保已部署和运行的软件全面、连续的支持系统任 务。当发现软件故障后，首先要进行故障诊断，定位导致故障发生的原因及软件缺陷。软 件的修改和更新可以通过软件维护方法，按照一定的规范和步骤进行。但对于安全关键软 件，人们希望在完成程序修正、回归测试和重新部署前，通过故障隔离技术使得缺陷代码 不会继续导致软件失效，以便软件能继续执行某些关键任务。同时，基于软件工程的原则 和理念，软件故障越早发现越有助于提高软件质量，减少软件修改和维护的开销。因此软 件故障诊断与隔离技术也可以在测试阶段部署和实施，查找定位软件故障并采取相应的措 施，这一方面尽可能避免将软件故障引入安全关键系统；另一方面可以为安全关键软件实 际运行中的故障诊断与隔离提供宝贵的经验和参考。此外，人们还希望上述故障诊断、隔 离过程和采用的相关技术能够具有快速、尽可能不中断系统运行、自动化程度高等特点。 综上所述，为了能够在安全关键软件自身规模日益庞大，复杂度日益提高，外部环境 苛刻多变的情况下，提高软件实际运行过程中的安全性、可靠性和可生存性，需要针对安 全关键软件的特点，找到一条切实可行的途径，在软件故障发生后，研究分析故障发生的 第l 页 国防科学技术大学研究生院学位论文 本质和内在规律，准确定位故障原因，同时采取积极有效的隔离应对措施，从而尽量避免 由于软件故障而导致软件和系统失效情况的发生。课题的研究意义正在于这些方面。 1 2 论文的主要研究内容 由于故障诊断与隔离的定位是在安全关键软件部署和运行之后，这意味着不能直接针 对源码实施操作，而安全关键软件的实时性和不可中断性也决定了在故障发生后回溯到软 件维护修正错误并重新部署软件并不能满足实际情况的要求，因此，需要考虑从安全关键 软件的目标码着手，即在可执行代码的层面上快速实现软件的故障诊断与隔离。本文的一 个重要研究内容即是如何实现对二进制代码的分析和操作，从而为数据样本采集和故障隔 离提供底层技术支持。此外，与大多数故障诊断方法不同，本课题力求从程序数据角度定 位故障原因，这就需要找到一种数据分析机制以支持故障查找和定位的需求，因此研究探 讨基于布尔函数学习算法的故障诊断方法则是本文的另一个关注点。 1 2 1 主要研究内容 1 针对安全关键软件特点，提出了故障自动诊断和隔离框架a f d i f 。详细描述了框 架的整体结构，深入研究了框架各个组成部分的功能，以及组成部分之间的联系， 进而分析了框架对于自动故障诊断与隔离的可行性。 2 研究实现了基于数据样本的故障诊断与定位方法，包含两个方面：第一个方面是 通过详细讨论运用代码插装收集运行时数据的过程、原理和实现机制，以及利用 测试用例变异来生成指定数据样本的采集和抽象过程，从而实现了在测试运行过 程中基于二进制代码插装技术的数据样本收集与抽象方法；在此基础上，第二个 方面主要研究了如何利用布尔函数学习机制分析数据样本并找到故障原因，从而 实现了有效的故障诊断与定位。 3 为保证在维护完成之前软件主要功能和任务的持续运行，研究并实现了使缺陷代 码不会导致实际故障产生的故障隔离技术，通过深入研究基于二迸制代码插装技 术的软件故障隔离方法，同时着重探讨如何通过补丁( 即，故障隔离代码) 插装 技术在故障条件成立的情况下将故障代码与程序运行隔离，并详细介绍了故障隔 离的处理流程和实现机制。最终在技术层面实现了故障的有效隔离。 4 在上述理论研究成果的基础上，结合微软的p h o e i l i x 和v c 平台开发实现了故障自 动诊断与隔离框架的一个原型工具，同时针对一个目标程序研究和分析工具的实 际应用情况。 1 _ 2 - 2 论文的结构 第2 页 国防科学技术大学研究生院学位论文 本文共分为七章： 第一章是引言，主要介绍论文的研究背景和意义，以及论文的研究内容和所做的 工作。 第二章是相关研究介绍，分成3 个部分： 首先从故障诊断和故障隔离两个方面分别介绍相关领域的研究现状。 接下来介绍故障诊断与隔离的发展趋势。 最后讨论与当前研究相比，本文研究的内容有何特点和针对性。 第三章是故障自动诊断与隔离框架的研究与介绍，分为2 个部分： 首先讨论和介绍了软件失效机理，通过分析软件缺陷，软件故障，软件失效 三者之间的内在联系，揭示了软件发生故障的根源以及最终导致的后果。 在此基础上，研究和提出故障自动诊断与隔离框架a f d i f ，描述了框架的整 体架构，分析和介绍了框架故障诊断与隔离的基本流程，然后分别研究了框 架主要活动的实现原理和内在机制。 第四章深入研究了故障诊断与定位的关键支撑技术，包括3 个内容： 首先从基本架构和功能特征两个方面介绍了微软的p h o e n i ) 【平台，从而揭示了 平台对于本课题的研究价值所在。 接下来深入研究了基于代码插装的样本采集技术，详细阐述和分析了如何利用 二进制代码插装技术获取程序运行时数据，从而实现样本采集。 最后研究和介绍基于布尔函数学习机制的故障诊断与定位算法的实现原理和 开销分析。 第五章深入研究了故障自动隔离技术，分为2 个部分： 首先研究介绍了隔离补丁的自动生成和插装方法，详细描述了如何结合中间数 据结果自动生成补丁的方法和过程，以及如何减少指令插装的数目以降低运行 补丁的开销。 接下来深入探讨了利用指令插装以实现程序执行的定向跳转的方法，着重研究 了如何实现根据用户选择的故障隔离处理方式改变程序执行的顺序，以跳转到 指定的程序位置。 第六章是a f d i f 框架的实现与应用研究，主要介绍根据框架模型实现的原型工具， 包括工具的基本结构，各个组成部分的作用和所实现的功能，以及组成部分之间 的联系：在此基础上分别介绍组成部分相应的程序实现，包括程序的设计原则和 实现方法，同时针对目标程序，分析各个组成程序处理而得到的中间以及最终结 果，从而研究了原型工具的应用情况。 第七章对本论文研究的主要内容和关键技术点做出了总结，并给出下一步工作的 思路。 第3 页 国防科学技术大学研究生院学位论文 第二章软件故障诊断与隔离相关研究现状 2 1 1 故障诊断 2 1 软件故障诊断与隔离的研究发展情况 随着安全关键系统中软件比例和重要性的快速提高，人们近年来逐渐认识到软件故障 诊断技术的必要性。比如在航空航天领域，故障诊断显得尤为重要：美国国家航空航天局 ( n a s a ) 将建立高度自治的故障诊断系统作为提高太空探索航天系统可靠性的一个重要手 段，主要关注如何实现空间系统的完全自治，其针对航天器自治系统的l i v i n g s t o 肿诊断系 统已投入使用，并采用模型检验技术对该诊断系统本身的正确性进行验证【2 】。受人类免疫 系统的启发，n a s a 正在研制开发一种软件工具m u l t i 1 e v e ih n m u n el e a r i l i n g d e t e c t i o n ( m i l d ) ，该工具可检测系统中的软硬件故障【3 1 。欧洲宇航局( e s a ) 对关键软件的故 障检测、隔离和恢复技术和框架进行了研究，并开始针对s m a m i 、r d s e t t a 等多个卫星进 行试验【4 】。e s a 针对航天器在轨软件o b s w ( o n - b o a r ds o f h a 化) 提出了使用 a f d i r ( a d v 觚c e df d i r ) 和s m a r t f d 取两种方法进行故障检测、隔离和恢复( f d r ) 。目 前这些方法已成功应用于e s a 先进的极轨对地观测卫星e n v i s a t 和p r o b a 1 等航天器中 h 。近年来，为保证深空探测航天器的软件运行的可靠性，e s a 又提出了s a f e 哆b a g 等方 法【5 1 。 软件故障诊断研究一开始直接借鉴了物理系统的故障诊断方法。可以将物理系统故障 诊断方法分为两大类【6 】：d x ( 诊断) 方法和f d i ( 故障检测和隔离) 方法。d x 方法进行 故障诊断的思路是参照系统中各组件正常行为的模型进行严格的逻辑推理和诊蝌：f d i 方法则根据系统非正常行为的模型来处理实际系统产生的现象喁】。这两类故障诊断方法都 可称为基于模型的诊断o v i o d e l b 如e dd i a g n o s i s ) 【9 】，即通过对比系统的逻辑模型和实际观测 结果来诊断系统是否出现异常。在早期的软件故障诊断中，更多是借鉴文献 8 】中提出的 d x 方法，即以用一阶逻辑等理论描述的系统模型为基础j 初始时将系统中的模块分类放 在观察( 0 b s e r v a t i o n ) 集和冲突( c o i l f l i c t ) 集中，并通过计算命中( h i t t i i l 曲集来获得诊断结果( 即 故障模块) 。文献【l o 】以上述方法为依据提出了一个对类p r o l o g 语言程序进行诊断和调试的 模型，结果表明其方法通过较少的用户交互即能定位程序缺陷。 但上述基于物理系统的故障诊断方法更适合于逻辑程序，未充分考虑现代软件本身的 特点，没有与程序理论和软件工程方法紧密结合，因此难以适应现在软件故障诊断的需要。 之后也出现了一些基于模型故障诊断的研究，但方法有所不同。例如，文献【1 1 】以机器人 控制系统的软件体系结构作为故障诊断的目标，通过设置观测器来判断被监测值是否出现 了异常，并在故障发生时触发诊断引擎对故障原因进行计算。此外，从程序结构中提取模 第4 页 国防科学技术大学研究生院学位论文 型也是一种途径。例如，文献 1 2 】直接从结构化程序中构造程序依赖图以获取程序模型， 通过故障值切片准则方式找到一个最小冲突集，从而缩小了查找程序缺陷的范围；文献【1 3 】 和 1 4 】则分别从j a v a 程序和汇编程序中提取基于值( v a h l e - b 勰e d ) 的模型作为依据进行故障 诊断。 故障诊断的一个重要依据是获取软件运行路径。文献 1 5 】用辅助进程的方法记录故障 发生前的运行路径，据此诊断嵌入式并发程序中的故障原因；文献【1 6 】结合基本框架监控 ( h l n 砸t r u c t u r em o l l i t o r i l l 曲，程序剖析( p r o f i l i i l g ) ，事件相关( e v e n tc o r r e l a t i o n ) 以及真实用户 监控( r e a l u s e rm o i l i t o r i n g ) 等故障分析技术，通过分析服务和方法的执行路径，从而对被 看作黑盒的分布式应用软件进行诊断。文献【1 7 】提出了一种基于路径剖析的程序分析方法， 通过分析日志提取出程序部分历史执行路径，分离故障路径以提高精确程序分析的灵活 性。 软件运行时的故障诊断对于已部署的软件来说具有实际意义。例如，美国n a s a 的研 列博】通过定义有穷序列监控逻辑( m o n i t o r i n gl o g i c ) 预先假设程序将来的行为，并在运行时 以测试预言( t e s to r a c l e ) 的方式自动判定程序运行是否与预设的行为相违背，该种方法已应 用在火星探险漫游者的规划软件p l a s m a 中【1 9 l 。加拿大w a t c d o o 大学软件可靠性研究实 验室的t s a v o r 等人采用s d l ( s p e c i f i c a t i o na i l dd e s c r i p t i o nl m g u a g e ) 对故障进行描述， 设计实现了一个软件监视器，用来对目标程序的输入和输出进行监控，从而实现了软件运 行时的故障检测1 2 0 j 。 软件测试方法也是有效故障诊断的一条重要途径。d eb e a u l i e u 大学的b e n o i tb 卸d r y 和f r a l l c kf l e u r e y 等人提出了一种基于测试用例集优化的故障诊断方法，通过变异测试用 例，使得测试用例集覆盖尽可能多的动态基本块( d b b ，d ”锄i cb 嬲i cb l o c k s ) ，从而提高了 诊断的精度，能够有效定位程序故障阱】。国内也存在这方面的研究，东南大学的聂长海等 人提出了一种基于组合测试的软件故障诊断方法，在分析初次组合测试结果的前提下，对 可能的错误原因补充一组新的测试用例重新测试，从而迅速缩小了故障原因的可能范围 【2 5 】。 研究软件失效机理，寻找和表示软件失效、故障和缺陷三者之间的联系和规律，是快 速准确的进行故障诊断，进而定位故障原因的重要依据。在安全关键软件设计时可以采用 失效模式与影响分析( f a i l u r em o d ea n de 虢c t sa n a l y s i s ) 、故障树分析( f a l l l t1 h ea n a l y s i s ) 等方法来提高软件的可靠性和安全性，同时分析结果也能作为故障诊断的参考，但对于在 代码中准确定位缺陷仍显不足。因此已有的一些工作着重研究如何在程序中定位那些反映 某些特征( f e a n 】r e ) 的代码。利用软件勘测( r e c o n n a i s s a n c e ) 【2 6 】【2 7 】技术，能够将特征代码与故 障现象相对应，从而可以用来进行故障诊断。在此基础上，将静态和动态切片技术与软件 勘测技术相结合，能够提高特征定位的效率和精度【2 扪。 2 1 2 故障隔离 第5 页 国防科学技术大学研究生院学位论文 为了使安全关键软件在缺陷被修正前依然能执行某些关键任务，需要把可能出现的故 障与软件正常运行进行隔离，以确保在后续的运行中软件不会实际产生故障。与故障诊断 不同，软件故障隔离通常在目标码的层面上进行研究。由于软件存在缺陷而经常受到外部 攻击，m i c r o s o r 公司的硅谷研究院与c a l i f o n l i a 大学、斯n c e t o n 大学联合开展了g l e i p 血 项目【2 9 】，主要研究在未消除潜在软件缺陷的情况下，如何使得软件的弱点难以被攻击。其 主要的解决方案包括通过建立程序内部监测机制以及在程序中插装隔离指令来阻止恶意 代码被执行。美国c a l i f o 】晒a 大学b e r k e l e y 分校研究了对同一地址空间中的软件模块进行 故障隔离的方法【3 0 1 ，方法首先把包含缺陷模块的代码和数据载入一个故障域( f a u l t d o m a i n ) ，故障域在地址空间中与正常软件模块是逻辑分离的，接下来方法修改故障模块 的目标代码以阻止它向故障域之外的地址进行写操作或执行跳转动作。该方法的局限性是 只能在s c 指令体系中应用，因此后来m 和h a n ，a r d 大学联合研究的p i t t s f i e l d 技术把 其扩展到c i s c 指令体系中，并进一步提高该方法的可靠性1 3 。此外，h a n ，a r d 大学的m i s f i t 项目【3 2 】研究了x 8 6 汇编语言中可能存在的指令不安全使用方式，并将其转换为安全的指 令使用方式，因而也具有一定的故障隔离作用。该方法具有通用性，并不针对具体软件故 障。美国a d z o l l as t a ：t e 大学的h a ih u 趾g 等人针对w e b 应用程序，通过二进制代码分析提 出了一种自动热补丁( a u t 哪a t e dh o tp a t c l l i n g ，a h p ) 方法【3 3 】，从程序数据输入的角度分析和 定位w e b 应用软件产生故障的原因，并生成热补丁插装到程序执行码中以隔离故障。此外， 基于统一建模语言u 叫匝的软件结构和行为模型，文献【3 4 】研究了如何利用模型检验技术找 到代表故障原因的错误消息，并消除它对其他消息的影响，从而最终达到故障隔离的目的。 2 2 软件故障诊断与隔离研究发展趋势 由于各种因素的制约，总体说来当前的软件可靠性和安全性仍达不到预期的要求，在 实际应用过程中软件故障仍然难以避免。基于目前这种情况，人们已逐渐开始注重从软件 故障诊断和隔离角度进行研究，尤其是针对安全关键软件，以期提高可靠性和安全性。从 目前看，故障诊断的研究比隔离更多一些，但对它们的研究总体仍处于起步阶段，还缺乏 有效的技术和系统的理论框架。为实现有效的故障诊断与隔离，需要针对安全关键软件的 主要特征，结合软件工程的主流技术( 如基于u m l 的分析与设计建模、软件体系结构和 基于构件的软件开发方法等) 和程序理论在实践中的最新进展( 如并发程序切片、模型检 验、抽象解释、谓词抽象、运行时验证、二进制代码分析等) ，进一步研究适用性强、自 动化程度高的安全关键软件故障诊断、隔离理论框架与关键技术。 2 3 课题的特点和针对性 大量案例和研究结果表明，在安全关键软件发生故障的原因中，最常见也是难发现和 第6 页 国防科学技术大学研究生院学位论文 诊断的故障是数据错误，例如用户输入、系统采集的外部数据等是非预期的，而逻辑缺陷 等许多其它类型的问题最终也可能表现为导致某些变量取值错误。因此与相关工作相比， 课题针对研究目标的实际特点和应用，侧重于研究外部数据输入对软件运行的影响，通过 对程序数据流实施分析和控制，达到诊断和隔离故障的目的，这主要表现在收集程序运行 数据并进行诊断和分析，找到一个变量的最小集合，包含所有导致程序故障发生的“关键” 变量，最后监控这些变量，一旦故障发生条件再次成立，即对程序故障进行隔离。基于数 据流的故障诊断与隔离方法的优点之一是能够精确定位故障原因：可以定位故障发生时正 在执行的子程序，接下来通过分析数据样本能够定位子程序中那些接收外部异常值而导致 故障发生的参数和变量，这对于有效隔离故障至关重要。第二个优点是方法不需考虑子程 序自身的业务逻辑和程序指令语义，而只需在与外部输入的接口处施加影响，这就大大降 低故障诊断与隔离的复杂度，同时减小了操作的开销。从上述角度讲，课题的研究紧贴安 全关键软件的实际情况，在重点关注故障常见原因的指导原则下，着重研究和解决故障诊 断与隔离过程中瓶颈和难点问题，从而具有很强的针对性。 第7 页 国防科学技术大学研究生院学位论文 第三章故障自动诊断与隔离框架a f d i f 3 1 软件失效机理介绍 故障诊断与隔离的目的是在软件故障发生后定位故障原因，并将故障代码与软件运行 隔离，从而避免软件实际失效的发生。因此，在研究故障诊断与隔离之前，必须首先研究 软件故障与软件失效发生的机理，了解两者产生的过程。在此基础上首先需要了解一些基 本概念【3 5 】： _ 软件缺陷( s o f l m r ed e f b c t ) ：存在于软件中的、不期望的或不可接受的偏差，其结 果是当软件运行于某一特定条件时将出现软件故障( 即，软件缺陷被激活) ， 软 件缺陷以一种静态的形式存在于软件的内部，是软件开发过程中人为错误的结果。 - 软件故障( s o f h v a r ef a u l t ) ：指在软件运行过程中出现的一种不期望的或不可接受的 内部状态，此时若无适当措施加以处理就会产生软件失效。软件故障是一种动态 行为，是软件缺陷被激活后的表现形式。 _ 软件失效( s o r w 鹏捌1 u r e ) ：指软件对要求行为的偏离，是软件运行时产生的一种 不期望的或不可接受的外部行为结果。 在某种意义上讲，软件缺陷和软件失效代表了软件的两个不同层次的问题。软件缺陷 是软件的内部问题是软件开发人员能够察觉到的问题；软件失效是软件的外部问题，是 用户能够察觉到的问题。 软件缺陷是分层次的，可以软件缺陷分成如下几个等级【3 6 】： 表3 1软件缺陷严重等级 序号等级名称描述 l 致命导致软件崩溃、死机的缺陷 2 严重妨碍主要功能实现和性能达标的缺陷 3 一般妨碍次要功能实现的缺陷 4 轻微给用户带来不方便或麻烦、但是不妨碍功能实现的缺陷 从表3 1 中可以看出，不同等级的软件缺陷对软件影响的程度是有差别的，如何对待 和处理这些软件缺陷的方法也各不相同，因此针对不同的目标系统，需要确定系统中亟待 解决的缺陷，并找到相应的解决方案。 由于人为差错和其他客观因素，软件缺陷在开发阶段被引入到软件内部，软件缺陷是 软件失效的根源，但并非所有的软件缺陷都会导致软件失效，通常软件缺陷处于静止状态， 只有在特定的运行环境和条件下，比如不恰当的操作或非法外部数据，软件缺陷才会被激 发，从而形成软件故障。此时若不采取适当措施加以处理，当一个或多个软件故障在软件 系统或子系统之间传播，积累到一定程度以至反映到用户接口时，就产生了软件失效。 第8 页 国防科学技术大学研究生院学位论文 软件失效机理可以用下图表示： 厂 弋， 特定条件 啭播 图3 1 软件失效机理示意图 从软件失效的形成过程可以看出，在实际的软件运行过程中，软件缺陷并非一定会导 致软件失效的发生，首先软件缺陷只有在特定的条件下才会转变为运行时的软件故障，其 次从故障发生到软件失效并不是一个原子性的过程，中间还需要经过故障传播阶段。因此 一个避免软件失效的办法是阻止特定条件的形成，比如，严格限定软件运行环境和条件， 提供全面详尽的软件操作规程并严格按照实施等。但在实际情况中由于受各种主客观因素 的影响，上述措施往往不能正确实施。所以，需要考虑另外的途径，一个可行的办法是在 发生软件故障后迅速定位故障产生的原因，若故障条件再次成立则在故障源头或传播过程 中及时阻止故障向外传播，采取上述措施同样可以达到避免软件失效的效果。据此形成了 研究软件故障诊断与软件隔离技术与方法的基本出发点。 就本课题来说，故障诊断与隔离的目标主要是针对安全关键软件中比较严重和致命的 缺陷，防止这两类缺陷所引起的软件失效，而对于一般和轻微的软件缺陷，由于它们对软 件运行影响并不是很大，因此不在研究范围之内。 3 2a f d i f 框架 基于课题的研究目标和研究内容，本文提出了一种针对安全关键软件特点的软件故障 自动诊断和隔离框架a f d i f ，通过代码插装收集软件运行和故障数据，并通过布尔函数学 习算法自动判断导致故障发生的关键数据范围，然后生成故障隔离代码并插装到软件中以 隔离软件故障。该方法的目标在于一旦安全关键软件发生故障，能够自动、及时地发现和 定位故障原因，并把产生故障的代码或数据范围与软件运行隔离开，使得软件中的缺陷不 会在后续运行中产生实际失效，以获得快速恢复执行关键任务的能力。 3 - 2 1 框架整体结构 安全关键软件自动故障诊断与隔离框架a f d 旺由运行数据获取、样本采集和抽象、故 障自动诊断以及故障隔离代码自动生成这四个主要活动构成，框架结构图3 2 所示( 见下 页) 。 第9 页 国防科学技术大学研究生院学位论文 实际情况表明，在软件实际运行过程中，不可预料的外部数据输入错误是最常见，也 是最难感知和防范的软件故障因素。由于软件未能对外部异常数据进行合理的处理，错误 数据的传播最终使得某个予程序中所引用的参数以及全局变量出现了异常值，一旦异常数 据进入子程序内部并被引用和处理，会导致软件运行结果不正确等故障产生。因此，a f d i f 主要针对此类问题提出故障诊断和隔离方法。软件一旦发生故障，a f d i f 通过分析安全关 键软件自身的执行日志或者向软件插装的二进制代码，监控、收集运行和故障数据并进行 分析，最终能够确定产生故障的子程序，同时提取出故障子程序所引用的参数和所依赖的 全局变量的异常值。接下来，a f d i f 通过针对性地测试运行【3 7 1 ，收集并抽象正常运行和故 障运行过程中的数据样本。故障诊断将数据样本作为布尔函数学习算法的输入，自动找到 因为出现异常值而导致程序崩溃的若干“关键”变量，“关键”的意义在于它们是导致软 件故障的本质原因。要强调的一点是，故障诊断要准确定位故障需要一定数量的数据样本， 因此，如果未能准确定位故障，a f d i f 就需要反馈到测试运行阶段，优化测试用例集洲， 以便最终能够找出那些“关键”变量。最后，在故障隔离阶段将生成隔离代码并插装到程 序中，一旦这些“关键”变量再次出现异常值，隔离代码将在程序产生实际故障前及时发 现并进行处理，避免软件失效的发生。 图3 2a f d i f 结构图 a f d i f 具有较高的自动化程度，从图3 2 可以看出，故障发生时并不需要人工干预， 框架自身将通过分析程序运行日志或插装监控代码等手段自动感知故障并启动数据收集 第1 0 页 国防科学技术大学研究生院学位论文 等活动进程。通过预先的设置和约定，框架可以自动生成一组恰当的测试用例集来进行有 针对的测试运行。而对于数据样本收集与抽象，故障诊断与定位以及故障隔离等活动来说， 它们所担负的任务相对独立，模块之间只有比较简单的数据传递关系，耦合度低，控制逻 辑和流程比较简单，因此框架通过将其功能封装，并约定好数据交互的接口和数据结构， 实现了故障诊断与隔离的自动化过程，这样方便了框架的使用，降低了对用户的要求。框 架的另一个优势在于它是在二进制代码层面上作用于目标程序，这种处理方式带来的好处 是框架屏蔽了安全关键软件的实现过程的差异，将处理和交互的对象统一到软件的可执行 代码上，这就极大的扩展了框架的可作用范围，从而使框架具有良好的可用性和兼容性。 在对a f d i f 框架有了一个总体和