（计算机科学与技术专业论文）基于风险统计的可测控软件研究.pdf

摘要 随着信息技术的发展，应用软件越来越复杂，导致软件“软件危机”的产生。 软件的正确性和可靠性难以保障是“软件危机”中突出的一个问题【l 】。“软件工 程”的出现与发展对解决“软件危机”有很大的益处，其主要特点是“建立并使 用完善的工程化原则，以较经济的手段获得能在实际机器上有效运行的可靠软件 的一系列方法”l l 】，也就是指示出“软件工程”是从工程规范性着手解决“软件 危机”的一系列问题。伴随着“人工智能”颁域的相关学科的发展，以“人工神 经网络”和“复杂适应系统”技术为典型代表的对复杂系统特征进行数学模型抽 象或统计描述的方法越来越成熟。这些描述或亥画系统特征的技术，提供了一种 对软件系统进行测控的可能，本文在对软件系统性质进行深入分析后，针对软件 正确性和可靠性稳定，做了以下的几个方面的研究： 1 针对软件的正确性和可靠性，研究了在软件运行态提取软件运行统计信息的 方法。在此基础上研究了软件运行统计信息作为风险信息在用于描述软件正 确性和可靠性时的有效性。并且对此做了相关的实验验证。 2 针对软件运行时风险描述，对软件风险传播模型进行了研究，并利用该风险 模型，设计了基于风险传播性的软件运行正确性和可靠性测控模型。 3 为了克服基于风险传播性的软件测控模型中“软件运行正确性与软件风险传 播性成反比”这一假设，研究了基于复杂适应系统的软件运行正确性和可靠 性测控模型。 由于在数学上对逻辑和算法建模难度很大( 控制系统建模相对容易) ，所以 传统的软件工程技术对于软件正确性和稳定性的研究主要集中于软件开发过程 的工程规范化，而本文讨论的基于软件运行风险信息的软件正确性和可靠性测控 研究则是面向软件执行过程的软件测控。目前这样的研究比较少见，所以主要是 参考了一些控制学科的模型和研究成果。目前在控制学科中已经存在大量的基于 “特征统计信息”的控制模型和算法，并且已经得到了广泛的应用【3 “一】所以期 望本文进行的研究也能在软件领域发挥有益的作用。 关键词：运行态稳定性运行态风险风险传播性复杂适应系统 a b s t r a c t a c c o m p a n y i l i gw i 也t l l ed e v e l o p m e n to f i t ，t h es 0 f h r a r eb e c o m em o r ec o m p l e x t h i sc 他a 土e “s o 丘w a mc r i s i s ”h o wt om a i n t a i nm ec o r r c c n 鹊s 觚dt l l es t a _ b i l i 竹o f s o f t w a 糟i s 缸i mp l 时t a n tp o i n to f s o 肌a r ec r i s i s t h ed e v e l o p m e n to f “s o f t w a 舱 e n g i n e e 咖f p r o m o t e daw a yt os o h ，e “s o r w a 糟c r i s i s ”t h ef b a t u r eo f “s o r w a r e e n 西n e 甜n g ”i s t 0r u ns 0 f h v a r es t e a d yi na l le c o i l o m y 啪yb yl l s i n ge n 西n e e 血唱 砸n c i p l e nm e a i l s 吐1 a t “s o f t 、 ，盯ee n 百n e “n g ”s o l v 抽g “s o f t 啪r ec r i s i s ”o n l yb yt h e m e a n so fe n 西n e c f i n gs t 赳l d a r d i z a t i o n t h ed e v e l o p m e n to fa ie x pt l l ea n na n dt h e c a s ，p r o m o t eaw a yt od e s 商b ec o m p l e xs y s t e 皿i tm a k ep o s s i b l et 0s c a l e 锄d c o n n 口las o n 懈s y s t e m t l l i sp a p e rd i d 锄c hr c s e a r c h e s t h ec o n _ e 咖e s s 弛dt i l e s 讪i l 姆o f s o 硒髋 1 a m l i n ga tt h ec o n c t 芏l e s s 觚dt h es t a b i l i t yo fs o f h v a r e ，t l l i sp a p e r 咖d i e dt h e m e t h o do fd i s t i l l i l l gg 眦i s t i c a li n f o m l a t i o no f r u n t i n 圮s o 自 ，a r e ，觚dd e d u c e dm a tt l l e n m t i m ei n f o n 【l a t i o ni se 岱e c t i v e l yt od e s c r i b et i l ec o r r e d h l e s sa n dt l l es t a b i l i t y “ s o f t 、 ，a r e 2 a n i n ga lt h e 咖一t i m er i s ki 砬m a t i o no fs o f t w a r e ，t 1 1 i s 群l p e rs t u d i e dt l l e m o d e lo fr i s k 仃a i l s m i t ，舭db a s e do n 廿l i sm o d e ld e s i 鲷e dam e t h o dt 0m a i n l a i nt h e c o n e c t n e s sa n d1 h es t a ：b i l i t yo f s o f t w a r e 3 t ba v o i d u s i i l g t h e h y p o m e s i s o f t h e c o r r e c m e s s 柚d t l l es t a _ b i l i t y o f s o r w 啪 a r e 如v e r 辩r 撕ot o 吐l er i s k 缸a n s m i ta b i l i 矿，t h j sp a p e rd e s i 印e dam o d e lo fc a st o m a i 栅nt h ec o r r e 咖e s s 锄dt 1 1 e 啦a b i l i t yo f s o 行w 撇 f o rt h e 汀td i 伍c u l to fm o d e l m g1 0 西c 趣l da r i l m e t i c ，t 棚i 廿o n a 卫s o f t w a r e e n g i n e e r i i l gt e c l l l l i q u em 豳t a i nt h ec o r r e c 协e s s 锄dt l l e 鲰l b i l i t yo fs o 丘w a r eb y l e m e 柚0 fe n g i l l e e r i r 喧s t a i l d a 埘i z a t i o n t i l i sp 印e fe x p o u n dan e wm e 山o dt 0s 0 l v et t l i s p r o b l e m ，“sb 勰e d0 nt h e 舢- t i m ei 1 1 f 0 n n a t i o no fs o r w a r e b e c a u s eo f t h ea _ b s c eo f f e l a t i v er e s e a r c hp a p m i sp a p e r sr e f b r e n c ci ss o m em o d e l 锄dr c s e a r c hr e s u l to f c o n t r 0 1s c i e n c e i nm i s 五e l ds o m em e t h o do f “f ea 1 ：u r es t a t i s t i c a li l l f b n n a t i o n ，i s 、i d e u s e d i 、v i s ht h er c s e a r c hr e s l l l to f t l l i sp a p e fc o l l l db eu s e di ns o f t 、v a r cf i e l d k e ) rw o r d s ：r 肋一n m es t 曲i l i 魄r l l i l - n m e 硒s l 【，聪s kt r a i l s 商t c o m p l e xa d 印6 v e s y s t e m 玎 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属于西北工业大学。学校有权保留并向国家有关部门或机构送交论文的复印件 和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时本人 保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业大学。 保密论文待解密后适用本声明。 学位论文作者签名：趔! ： 指导教师签名 卟牛月7 日 纽 l a 明年缸月7 日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的学位论文，是本 人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 和致谢的地方外，本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成果 不包含本人或其他己申请学位或其他用途使用过的成果。对本文的研究做出重要贡献的 个人和集体均己在文中以明确方式表明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名：越 卜咖 目 西北工业大学硕士学位论文绪论 1 1 引言 第一章绪论 伴随着信息技术在生产生活中的广泛应用，计算机和软件的可靠性问题也日 益成为信息技术发展的关键问题。自从冯诺伊曼提出计算机模型，就给计算机 硬件系统的基本逻辑做出了明确的界定，所以对计算机硬件系统的可靠性研究， 就立足于逻辑的完备性、自治性的验证，并得到了一些很有效果的方法，如故障 树分析( f 1 a ) 、失效模式与效应分析( f e m a ) 、冗错技术等等。 反观软件技术，虽然近2 0 年来软件理论得到蓬勃的发展，但是软件的可靠 性还是没有得到充分的保障，甚至软件可靠性领域的相关技术也还没有完全定 型。软件的可靠性保障最主要的手段仍然是软件测试，然而软件测试过程无论是 白盒还是黑盒测试，还是归结于分类覆盖的逻辑：用尽可能少的测试用例来让软 件运行，覆盖尽可能多的软件状态，从而尽可能多的发现软件存在的问题，保障 软件的稳定性。但是软件毕竟是对生产生活中的客观逻辑的软件语言描述，在对 客观逻辑进行抽象的过程本身并不能保证客观逻辑完备性和自治性的情况下，软 件测试能否发现这种逻辑问题映射成的软件上的可靠性问题? 而这样的隐蔽的 问题一旦发生，结果往往会导致系统失去控制，并带来严重的危害。 本文正是在这样的背景环境下，把运行态软件可靠性作为研究对象，把软件 的运行状态作为是客观逻辑的统计意义上的描述，那么一个偶然的状态异常( 小 概率事件) ，就可能是程序违背客观逻辑的先兆，也很可能就是程序当前已经进 入非正常状态的预示。 1 2 相关技术发展与趋势介绍 本文讨论的基于软件运行风险信息的软件正确性和可靠性测控研究，则是面 向软件执行过程的软件测控。目前这样的研究比较少见，所以本文主要是参考了 一些控制学科的模型和研究成果。因此分别对软件可靠性研究、软件测试理论、 基于系统统计描述研究做以下介绍。 西北工业大学硕士学位论文绪论 1 2 1 软件可靠性研究介绍 当前主流的软件可靠性研究都是从故障分析开始，通过研究故障的性质，总 结软件可靠性的统计评估。在软件可靠性模型上，重点是在于寻找适当的模型， 以便能相对精确的估计软件中可能含有错误的个数。软件可靠性是“软件在规定 的条件下、规定的时间周期内，执行所要求的功能的能力”。软件可靠性同样可 以用可靠度来衡量，而软件的可靠度是“软件在规定的条件下、规定的时间周期 内不引起系统故障的概率”。该概率是系统输入与系统使用的函数，也是软件中 存在的缺陷的函数。系统输入将确定是否会遇到已存在的缺陷( 如果有缺陷存在 的话) 。在可靠性研究中主要的模型有两种： 1 从硬件可靠性理论导出的模型 这种可靠性模型所傲的假设是： ( 1 ) 在两次错误出现之间的调试时间，随错误出现率呈现指数分布，而错误 出现率和剩余错误数成正比。 ( 2 ) 每个错误一经发现，立即排除，并使错误总数减1 。 ( 3 ) 产生错误的速率是个常数。 对软件来说，上面假设的合理性可能还有问题，例如，纠正一个错误的同时 可能不小心而引入另一些错误，这样第二个假设将不成立。 2 已知错误植入模型 这种模型的思想是把已知的错误植入到程序中，以在测试中发现这些错误的 比例和发现的其它错误的个数，来评估软件中还没有被发现的错误。 1 2 2 软件测试相关理论介绍 按照特定规程，发现软件错误的过程。测试是程序的执行过程，检查软件是 否满足规定的要求，或是清楚地了解预期结果与实际结果之间的差异。其目的在 于发现软件中的错误。软件测试是对需求分析、设计、编码的最后复审，是保证 软件质量的一个重要组成部分。 软件测试的基本理论见下： 1 测试是不完全的( 测试不完全) 由于软件需求的不完整性、软件逻辑路径的组合性、输入数据的大量性 及结果多样性等因素，哪怕是个极其简单的程序，要想穷尽所有逻辑路径、 2 西北工业大学硕士学位论文绪论 所有输入数据和验证所有结果，是非常困难的一件事情。一个简单的例子， 比如说求两个整数的最大公约数。其输入信息为两个正整数。但是如果将整 个正整数域的数字进行一番测试的话，从其数目的无限性便可证明是这样的 测试在实际生活中是行不通的。 2 测试具有免疫性( 软件缺陷免疫性) 软件缺陷与病毒一样具有可怕的“免疫性”，铡试人员对其采用的测 试越多，其免疫能力就越强，寻找更多软件缺陷就更加困难。由数学上的概 率论可以推出这一结论。假设一个5 0 0 0 0 行的程序中有5 0 0 个软件缺陷并 且这些软件错误分布时均匀的，则每1 0 0 行可以找至一个软件缺陷。我们 假设测试人员用某种方法花在查找软件缺陷的精力为x 小时1 0 0 行。照 此推算，软件存在5 0 0 个缺陷时，我们查找一个软件缺陷需要x 小时，当 软件只存在5 个错误时，每查找一个软件缺陷需要l o o x 小时。实践证明， 实际的测试过程比上面的假设更为困难，为此必须更换不同的测试方式和测 试数据。该例子还说明了在软件测试中采用单一的方法，往往不能高效和完 全的针对所有软件缺陷，因此软件测试应该尽可能的多采用多种途径进行测 试。 3 测试是“泛型概念”( 全程测试) 如果单纯的只将程序设计阶段后的阶段称之为软件测试的话，需求阶段 和设计阶段的缺陷产生的放大效应会加大。这非常不利于保证软件质量。需 求缺陷、设计缺陷也是软件缺陷，即“软件缺陷具有生育能力”。软件测 试应该跨越整个软件开发流程。需求验证( 自检) 和设计验证( 自检) 也可 以算作软件测试( 建议称为：需求测试和设计测试) 的一种。软件测试应该 是一个泛型概念，涵盖整个软件生命周期，这样才能确保周期的每个阶段禁 得起考验。同时测试本身也需要有第三者进行评估( 信息系统审计和软件工 程监理) ，即测试本身也应当被测试，从而确保测试自身的可靠性和高效性。 4 8 0 2 0 原则 8 0 的软件缺陷常常生存在软件2 0 的空间里。这个原则为，如果想 使软件测试有效地话，要注意常常光临其高危多发“地段”。在那里发现软 件缺陷的可能性会大的多。这一原则对于软件测试人员提高测试效率及缺陷 发现率有着重大的意义。聪明的测试人员会根据这个原则很快找出较多的缺 陷。 8 0 2 0 原则的另外一种情况是，在系统分析、系统设计、系统实现阶段 西北工业大学硕士学位论文绪论 的复审，测试工作中能够发现和避免8 0 的软件缺陷，此后的系统测试能 够帮助我们找出剩余缺陷中的8 0 ，最后的5 的软件缺陷可能只有在系 统交付使用后用户经过大范围、长时间使用后才会曝露出来。因为软件测试 只能够保证尽可能多地发现软件缺陷，却无法保证能够发现所有的软件缺 陷。 8 0 2 0 原则还能反映到软件测试的自动化方面上来，实践证明：8 0 的 软件缺陷可以借助人工测试而发现，2 0 的软件缺陷可以借助自动化测试 得以发现。由于这二者问具有交叉的部分，因此尚有5 左右的软件缺陷需 要通过其他方式进行发现和修正。 5 缺陷的必然性 软件测试中，由于错误的关联性，并不是所有的软件缺陷都能够得以修 复。某些软件缺陷虽然能够得以修复，但在修复的过程中难免会引入新的软 件缺陷。很多软件缺陷之间是相互矛盾的，一个矛盾的消失必然会引发另外 一个矛盾的产生。如在解决通用性的缺陷后，往往会带来执行效率上的缺陷。 更何况在缺陷的修复过程中，常常还会受时间、成本等方面的限制因此无法 有效、完整地修复所有的软件缺陷。因此评估软件缺陷的重要度、影响范围， 选择一个折中的方案或是从非软件的因素( 比如提升硬件性能) 考虑软件缺 陷，也成为面对软件缺陷时一个必须直面的事实。 出于工程规范化目的，也有工程化的软件测试原则，m y e r s 软件测试十原则： ( 1 ) 程序员应避免测试自己编制的程序 ( 2 ) 测试用例的设计必须包括预期的输出结果 ( 3 ) 测试用例应包括有效的和期望的输入情况，也要包括无效的和不期望的 输入情况 ( 4 ) 彻底检查每个测试结果 ( 5 ) 只检查程序是否做了它应该做的事仅仅完成了测试工作的一半，另一半 则是要检查程序是否做了它不该做的事 ( 6 ) 避免不可重复的即兴测试，保留全部测试用例 ( 7 ) 一段程序中存在错误的概率与在这段程序中已发现的错误数成正比 ( 8 ) 测试是一项非常复杂、创造性的和需要高度智慧的挑战性任务 ( 9 ) 不要为了便于测试擅自修改程序 ( 1 0 )测试工作必须有明确的目标 4 西北工业大学硕士学位论文绪论 1 2 3 系统统计描述研究介绍 基于统计的系统描述对象一般都是直接建立数学模型比较困难的系统，如 “非典传播模型”这样的“病理社会行为”系统。或者是直接建模导致运算 出现组合爆炸的模型，如“聚类算法”这样的大运算算法。对于第一种情况，在 统计描述这一领域影响比较深远的是“复杂适应系统”理论，对于后者是“神经 网络”。由于“复杂适应系统”理论更强调层次和行为的概念，所以对于其应用 不仅仅是在系统统计描述上，也有很多情况下作为系统行为控制所应用。 c a s 理论介绍 复杂适应系统( c o m p l e xa d 印t i v es y s t e m ，简称c a s ) 理论是美国霍兰( j o h n h o l l a n d ) 教授于1 9 9 4 年，在桑塔菲研究所成立十周年时正式提出的。复杂适应 系统( c a s ) 理论的提出对于人们认识、理解、控制、管理复杂系统提供了新的 思路。c a s 理论包括微观和宏观两个方面。在微观方面，c a s 理论的最基本的概 念是具有适应能力的、主动的个体，简称主体。这种主体在与环境的交互作用中 遵循一般的刺激反应模型，所谓适应能力表现在它能够根据行为的效果修改 自己的行为规则，以便更好地在客观环境中生存。在宏观方面，由这样的主体组 成的系统，将在主体之间以及主体与环境的相互作用中发展，表现出宏观系统中 的分化、涌现等种种复杂的演化过程。c a s 理论虽然提出不久，但是由于其思想 的新颖和富有启发，它已经在许多领域得到了应用，推动着人们对于复杂系统的 行为规律进行深入研究。 c a s 理论的核心思想 复杂适应系统理论的核心思想可以这样概述：“我们把系统中的成员称为具 有适应性的主体( a d a p t i v ea g e n t ) ，简称为主体。所谓具有适应性，就是指它能 够与环境以及其它主体进行交互作用。主体在这种持续不断的交互作用的过程 中，不断地“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行 为方式。整个宏观系统的演变或进化，包括新层次的产生，分化和多样性的出现， 新的、聚合而成的、更大的主体的出现等等，都是在这个基础上逐步派生出来的。” 复杂适应系统理论把系统的成员看作是具有自身目的与主动性的、积极的主 体。更重要的是，c a s 理论认为，正是这种主动性以及它与环境的反复的、相互 的作用，才是系统发展和进化的基本动因。宏观的变化和个体分化都可以从个体 的行为规律中找到根源。霍兰把个体与环境之间这种主动的、反复的交互作用用 “适应”一词加以概括。这就是c a s 理论的基本思想适应产生复杂性。 西北 二业大学硕士学位论文绪论 c a s 理论的基本概念 系统中的个体一般称为元素，部分或子系统。复杂适应系统理论采用了 a d a p t i v ea g e n t 具有适应能力的个体这个词，这是为了强调它的主动性，强 调它具有自己的目标，内部结构和生存动力。a g e n t 这个词本来是经济学中的用 语，表示代理人或代理商的意思。霍兰借用这个词，明显地表示：经济系统是他 建立c a s 理论时心目中的主要背景之一。 围绕主体这个最核心的概念，霍兰进一步提出了研究适应和演化过程中特别 要注意的七个有关概念。它们是： 1 聚集 a g g r e g a t i o n 2 非线性n o n 一1 i n e a r i t y 3 流 f l o w s 4 多样性d i v e r s i t y 5 标识t a g 6 内部模型i n t e r n a lm o d e l s 7 构筑块b u i l d i n gb l o c k s 在这七个概念中前面四个是个体的某种属性，它们将在适应和进化中发挥作 用，而后三个则是个体与环境进行交流时的机制和有关概念。 聚集：主要用于个体通过“粘合”( a d h e s i o n ) 形成较大的所谓的多主体的聚 集体( a g g r e g a t i o na g e n t ) 。在复杂系统的演变过程中，较小的、较低层次的个 体通过某种特定的方式结合起来，形成较大的、较高层次的个体，这是一个十分 重要的关键步骤。这往往是宏观性态发生变化的转折点。然而，对于这个步骤， 以往基于还原论的思想方法是很难加以说明和理解的。聚集这个概念正是归纳与 反映了复杂系统在这方面的行为特征。由于承认了个体的主动作用，由于克服了 在整体与局部之间，非此即彼的绝对的对立，c a s 理论提供了理解与描述上述现 象的新的视角。聚集不是简单的合并，也不是消灭个体的吞并，而是新的类型的、 更高层次上的个体的出现。还有一点应当指出的是，聚集的概念对于层次的理解 也提供了有益的启发。层次之间是有质的差别的。把层次之间的差别仅仅理解为 量的差别，是一种常见的误解。然而，层次之间的质的差别究竟是怎样涌现出来 的。在这里，聚集也起了关键的作用。 非线性：指个体以及它们的属性在发生变化时，并非遵从简单的线性关系。 特别是在和系统或环境的反复的交互作用中，这一点更为明显。近代科学之所以 在许多方面遇到了困难，重要原因之一是它把自己的眼界局限于线性关系的狭窄 6 西北工业大学硕士学位论文绪论 范围内，从而无法描述和理解丰富多采的变化和发展。c a s 理论认为个体之间相 互影响不是简单的、被动的、单向的因果关系，而是主动的“适应”关系。以往 的“历史”会留下痕迹，以往的“经验”会影响将来的行为。在这种情况下，线 性的、简单的、直线式的因果链已经不复存在，实际的情况往往是各种反馈作用 ( 包括负反馈和正反馈) 交互影响的、互相缠绕的复杂关系。正因为这样，复杂系 统的行为才会如此难以预测；也正因为这样，复杂系统才会经历曲折的进化过程， 呈现出丰富多彩的性质和状态。c a s 理论把非线性的产生归之于内因，归之于个 体的主动性和适应能力。这就进一步把非线性理解为系统行为的必然的、内在的 要素，从而大大丰富和加深了对于非线性的理解。正因为如此，霍兰德在提出具 有适应性的主体这一概念时，特别强调其行为的非线性特征，并且认为这是复杂 性产生的内在根源。( 软件系统映射的目标逻辑系统是显然的非线性的) 流：在个体与环境之间，以及个体相互之间存在着物质流。能量流和信息流。 这些流的渠道是否通畅，周转迅速到什么程度，都直接影响系统的演化过程。 多样性：在适应过程中，由于种种原因，个体之间的差别会发展与扩大，最 终形成分化，这是c a s 的一个显著特点。系统复杂性的重要思想之一就是个体之 间的差别，个体类型的多样性。当前的复杂性研究着眼于个体类型多种多样的情 况，而其中的c a s 理论则进一步研究这种多样性是怎样产生的，即分化的过程。 霍兰德指出，正是相互作用和不断适应的过程，造成了个体向不同的方面发展变 化，从而形成了个体类型的多样性。 标识：为了相互识别和选择，个体的标识在个体与环境的相互作用中是非常 重要的，因而无论在建模中，还是实际系统中，标识的功能与效率是必须认真考 虑的因素。标识的作用主要在于实现信息的交流。流的概念包括物质流和信息流， 起关键作用的是信息流。在以往的系统研究中，信息和信息交流的作用没有得到 足够的重视。这是对于复杂系统行为的研究难以深入的原因之一。c a s 理论在这 方面的发展就在于把信息的交流和处理作为影响系统进化过程的重要因素加以 考虑。强调流和标识就为把信息因素引入系统研究创造了条件。 内部模型：这一点表明了层次的观念。每个个体都是有复杂的内部机制的。 对于整个系统来说，这就统称为内部模型。 构筑块：复杂系统常常是在一些相对简单的部件的基础上，通过改变它们的 组合方式而形成的。因此，事实上的复杂性往往不在于块的多少和大小，而在于 原有构筑块的重新组合。 内部模型和构筑块的作用在于加强层次的概念。客观世界的多样性不仅表现 西北工业大学硕七学位论文绪论 在同一层次中个体类型的多种多样，还表现在层次之间的差别和多样性。当我们 跨越层次的时候，就会有新的规律与特征出现。这样一来，我们需要深入考虑的 就是这样一些问题：怎样合理地区分层次，不同层次的规律之间怎样相互联系和 相互转化。内部模型和构筑块的概念就是用来回答这些问题的。概括地说，它们 提供了这样一条思路，把下一层次的内容和规律，作为内部模型“封装”起来， 作为一个整体参与上一层次的相互作用，暂时“忽略”或“搁置”其内部细节， 而把注意力集中于这个构筑块和其他构筑块之间的相互作用和相互影响，因为在 上层次中，这种相互作用和相互影响是关键性的，起决定性作用的主导因素。 了解计算机科学与技术读者不难看出，这种思想与计算机领域中的模块化技术以 及近年来广为传播的“面向对象的方法”是完全一致的。 c a s 理论的主要特点 c a s 理论的核心思想“适应产生复杂性”，具有十分重要的认识论上的意 义。可以说，这是人们在系统运动和演化规律的认识方面的一个飞跃。具有很多 特点，而对于本论文而言最重要的特点在于：把宏观和微观有机地联系起来。它 通过主体和环境的相互作用，使得个体的变化成为整个系统的变化的基础，统一 地加以考察。 极端的还原论的观点是把宏观现象的原因简单地归结为微观，否认从微观到 宏观存在着质的增加。另一种比较普遍的观念是：把统计方法当作从微观向宏观 跨越的唯一途径或唯一手段。应当承认，基于概率论的统计方法确实是从微观到 宏观的重要桥梁之。宏观系统的某些属性可以理解为微观个体的某些属性的统 计量，如气体温度之于分子的动能，总体国民教育素质之于每个社会成员的教育 程度。这显然是重要的，正确地反映了微观与宏观关系的一个方面。然而，问题 在于，这是不是反映宏观和微观关系的唯一方法? 曾有人作过这样的计算：如果 地球上的有机物只是由于按照统计规律的偶然结合而产生的话，那么，从地球诞 生到今天，连第一个蛋白质分子都还没有产生! 显然，除了统计规律之外，一定 还存在着其他的机制或渠道，它们同样也建立起微观与宏观之间的联系。c a s 理 论则在这方面给我们提供了一条新的思路。 由于本论文将利用c a s 理论建立软件测控模型，所以对于c a s 模型介绍在 建立软件测控模型章节介绍。 神经网络介绍： 神经网络的特点介绍： 西北工业大学硕士学位论文绪论 1 丰串经网络工作模式为并行分布处理。 2 神经网络具有可塑性和自组织性。 3 神经网络的信息处理与信息存贮合二为一。 4 神经网络的信息处理是系统性的。 5 神经网络能接受和处理模糊的、模拟的、随机的信息。 6 神经网络是求满意解而不是精确解 神经网络的计算能力介绍： 1 数学的近似映射；识别和分类这些计算都可以抽象成一种近似的数学映射。 如误差反播模型( b p ) 、对向传播网络模型( c p n ) 、小脑模型( c m a c ) 等都可 以完成这种计算。 2 概率密度函数的估计：通过自组织的方式，开发寻找出一组等概率“锚点! ， 来响应在空间只“中按照一个确定概率密度函数选择到的一组矢量样本。自 组织映射模型( s o m ) 和c p n 模型可以完成这样的计算。 3 从二进制数据基中提取相关的知识：这种计算是形成一种知识的聚类模型， 这些知识依照数据基的自组织在它们之间有某种统计上的共性，并依此 ，来响应输入的数据基记录。脑中盒模型( b s b ) 有能力进行这种计算。 4 形成拓扑连续及统计意义上的同构映射：它是对固定概率密度函数选择的 ，适应输入数据的一种自组织映射。其最终使得数据空间上的不同项有某种 同构。s o m 模型适合计算此类问题。 5 最近相邻模式分类：通过比较大量的存贮数据来进行模式分类，但首先应 通过学习样本模式进行分类。可用层次性的存贮模式来进行分类信息的表 示。绝大多数的神经网络模型均能进行这种计算。如自适应共振理论模型 ( 姗、双向联想记亿模型( b a m ) 、b p 模型、玻尔兹曼机模型( b m ) 、b s b 模型、c p n 模型、h o p f i e l d 模型等等。 6 数据聚类：采用自组织的方法形成所选择的“颗粒”或模式的聚类，以此来响 应输入数据。聚类是可变的但要限制其鞍点的个数。对于任何新的目标， 只要系统中没有对其提供聚类，都要形成新的聚类。很显然这种能力可直 接应用于复杂的多目标跟踪。a r t 模型最适合于这种计算。 7 最优化问题：用来求解局部甚至是全局最优解。h o p f i e l d 模型、玻尔兹曼机 模型( b m ) 有能力进行这种计算。 9 西北工业大学硕十学位论文绪论 1 3 本文主要工作 本文的主要工作介绍如下： 第二章首先利用“编码观点下的程序模型”研究了软件稳定性正确性的静 态不可判定性质，然后抽象出软件运行态数学模型对程序系统运行态性质进行了 研究，针对软件的正确性和可靠性，提出了在软件运行态提取软件运行统计信息 用以描述软件运行划分的方法。并在此基础上推导了软件运行统计信息作为风 险信息在描述软件正确性和可靠性的有效性。 第三章研究了在编码观点下运行态软件正确性和稳定性特征提取方法，从 资源、路径、数据的角度设计了三种不同性质的软件运行态风险传感器r 、s 和 d 型风险传感器。 第四章通过做实验验证了软件运行统计信息作为风险信息在用于描述软件 正确性和可靠性时的有效性。 第五章针对软件运行时风险描述，对软件风险传播模型进行研究，并利用 该风险模型。设计了基于风险传播性的软件运行正确性和可靠性测控模型。主要 解决r 型风险信息用于软件系统运行正确性和稳定性控制问题，同时也给出基 于s d 型风险的控制概念。 第六章为了避免利用“s 型和d 型风险传播性与软件正确输出的反比关联 假设”。描述了基于c a s 理论建立利用s ，d 型风险信息控制软件系统的c a s 模 型，主要解决s 仍风险信息的实际应用问题。利用一一对应原理证明了c a s 模 型用于描述软件正确性的有效性，并且做了实验进行验证。 1 0 西北工业大学硕士学位论文运行态软件性质分析 第二章运行态软件性质分析 由于一直以来软件可靠性研究以及工程方法，基本上都是基于软件程序的静 态模型来加以考虑的，所以也就缺少一种在软件运行态下对软件可靠性进行研究 的模型。本章分别从静态和运行态的观点入手，建立不同的抽象模型，对运行态 软件性质加以分析。 2 1 软件稳定性正确性的静态不可预判性 从传统的观点来看，算法和数据结构就是程序，这样的一个定义显然是从程 序实现功能的角度来讲的，而程序无论是以文件方式存在，还是以运行状态体 现，都具有“信息”这一特征。作为程序必然有输入、执行过程和结果输出， 程序也就是一种信息变换过程的描述。当把这样的信息变换过程作为编码过程 来看待，这样的编码输入是程序输入信息和程序，输出的编码结果就是程序输 出结果。 假定存在一个完美的编码平台，这个平台能完成以上的编码功能，而且在 编码过程中，可以完全的识别编码输入( 程序输入和程序) 中所有的不合法值， 从而结束编码，当然这个平台的停机问题可以映射为图灵机的停机问题，也就 是不可判断的，况且在输入和程序都合法的情况下，该平台是可停机的。但是 现在只是抽象一个平台来讨论程序的信息编码性质。显然的是在这样的一个平 台下程序和程序输入都可以认为是一种编码描述。 在编码的观点下，程序模型有如图2 1 所示的结构，显然这样的观点是成立 的。现实中对应于编码平台的实体，就是计算机系统( 硬件和操作系统) 。对程 序信息的编码规则来自于两个方面的约束，首先是来自于编码平台的约束，其次 来自于程序要实现的处理逻辑的约束。程序输入的编码约束，直观上来讲是由程 序进行的约束，本质上是由于现实处理逻辑在实现程序编码过程中产生的约束。 编码约束关系如图2 2 所示。 西北工业大学硕士学位论文 运行态软件性质分析 经奥程序模銎 编码观点下的程序橇翌 图2 - 1 不同观点下的程序模型 稿码约柬关采 图2 - 2 编码约束关系 就一个设计完善的程序而言，如果程序设计和运行满足以下两点：程序 编码完备的满足了处理逻辑约束。程序输入编码也完备的满足了程序编码约 束和处理逻辑约束。那么该程序就应该是运行正确无误的。然而现实的情况是： 以上两点都很不容易被满足，没有一种方法能判定是否程序编码和程序输入编码 完备的满足了约束。导致程序编码没有满足约束的很多情况，是因为程序设计过 程中处理逻辑约束映射不完备所导致的，而程序输入编码约束，可以认为是噪音 造成( 各种各样的复杂原因) 的。旦程序编码或程序输入编码不能完备的满足 约束，那么，由于编码平台的停机是没有办法判定的，所以没有一种理论是可以 在程序运行之前，通过检查程序编码和程序输入编码，以确定程序是否能正确执 行。也就是软件的稳定性正确性具有静态不可预判性。 1 2 西北工业大学硕士学位论文 运行态软件性质分析 2 2 运行态软件正确性研究 为了分析运行态软件系统的性质，必须对运行态软件加以抽象研究，就软件 系统作为信息处理过程的观点来看，软件系统可以抽象成以下的数学模型。 2 。2 。1 软件非并行状态正确性研究 向量x 作为输入信息，向量y 作为输出信息，软件系统映射x 到y ，即： y = f ( 均公式( 2 1 ) 式2 1 从软件系统功能上抽象软件系统为f 这样一个输入信息到输出信息的 函数，但是软件系统并不是一个简单映射系统，最重要的原因是。软件在将x 映射为y 过程中，是有动态的时序性的，所以考虑到时间因素t ，将2 1 改写如 下： y = f ( ) ( ，t )公式( 2 2 ) 式2 2 的表达是有矛盾的，就软件系统而言，正常情况下什么时候开始执行 都保持一样的映射规则，所以在理想状态下，t 作为一个无关量并不会作为x 或 y 的一个特征标【6 j l 。但是将程序执行过程离散化后，该t 就具备了深刻的意义， 虽然其并不刻画x 或y ，但是其能刻画由x 到y 的映射过程序列。 离散化f ： 假设函数序列f 1 、f 2 、f 3 f n 和离散化的时间序列t l 、t 2 、t 3 t n 满足函数f ： y - - f ( ) ( ，t ) 邛n ( f 3 ( f l o ( ，t 1 ) ，) ( ，t 2 ) ，) ( t 3 ) ，) 【，t n )公式( 2 - 3 ) 定义为函数序列f l 、f 2 、f 3 f n 离散化f 。 考察软件结构，总是一条语句接着一条语句执行，在把语句也认为是模块的 情况下，总是一个模型接着一个模块进行执行( 暂时不做并发考虑) ，对于软件的 第一个模块对应f l ，第二个模块在第一个模块( 在t l 时刻) 执行之后取第一个 模块的执行结果和x 的信息( 在t 2 时刻) 执行。所以运行态软件抽象为式 ( 2 3 ) 是合乎逻辑的。 对应于理想软件过程，函数序列中每个函数的映射规则都是非常明了的，也 就是结果可预测和执行状态可判定的。但是在实际情况下，想要清楚的了解所有 的函数规则是不现实的，另外软件系统执行是在有噪音的环境下，并不是每个函 数规则都是完全可掌握的。所以将函数序列中的函数定义为如下的形式： 即x 和y 向量中不都包含t 这一个坐标，特征标详见参考文献6 1 3 西北工业大学硕士学位论文运行态软件性质分析 f k ：由可数维空间v 描述，空间的维数为m ；每个坐标上的状态是可数的， 第i 坐标上的状态个数为n l i v 。这样整个f k 就映射为空间上的一个体积，并且这 个体积是可测的l 【”。在该空间上的每个点都影射为f k 的不同输入信息，而每个 点对应一个输出( 不要求每个点的输出不同) 。在这个空间定义一个超平面， 对这个空间的所有点作一个划分：在这个平面之内的点构成集s l ，之外的点构 成集s 2 。赋予集s l 意义为：正确的f k 映射定义域。那么如果能对进行形式化 的描述，就自然能判定f k 映射是否正确，也就是软件在模块k 是否执行正确， 进而就能判定软件系统在当前缸时刻是否正确。遗憾的是，要确定每个模块对应 的并不是一件容易的事情，这是因为是与软件映射的目标逻辑相关联的，同 一个模块在不同软件中的很可能是不同的。如何描述就成为关键问题。 正如吉布斯2 在建立统计力学时候所用的方法【6 】，我们认为基于目标逻辑的 划分的s t 是具备一定的分布的( 即使是真正的随机逻辑，也能映射为一个均匀 分布) ，并且v 是可测的3 。那么我们自然的认为s ，构成体积，总能找到对这个 体积的某个测度u 就是的等价描述4 ，如同两个规格化为l 的同心球球面之间的 体积极限就是球面积的测度1 6 j 。由于“划分的s l 是具备一定的分布的”，另外 一个含义就是“划分的s i 其分布具有各种各样的可能性”，所以直接寻找“并不 是合适的方法。 作为软件模块输入来讲s l 是半可知的，那么最简单的方法，就是记录所有软 件模块在正确运行情况下的输入，并认为这些输入集合t 就作为s t 的一个真子 集。虽然当某次输入墩落在t 之外时，可能不属于s i 也可能属于s l 。而对这样 的情况是没有办法预先进行准确的判断，但是由于t 是s 1 的一个近似分布，那 么显然可以通过t 的分布和依据i k 的值，给出一个议落在s l 之外的概率p 鸭 因此用p 来衡量软件模块出现错误的可能性是成立的。 2 2 2 软件系统并行性对正确性的影响 首先从定义上区分两类并行：逻辑并行资源并行。 逻辑并行： 对式2 3 考虑并行化： 1 实际上计算机处理的信息总是能与自然数集构成一一对应，所以维数可数和每个坐标上的状态可数是自 然成立的。 2w g b b s 美国数学家奠定了统计力学。 3 见奉页脚汪1 4 见参考文献7 的第l 章第3 节 1 4 西北工业大学硕十学位论文 运行态软件性质分析 y 2 f ( ) ( ，t ) 2 f n ( f 5 ( f 2 ( f 1 ( ) ( ，t 1 ) 咒t 2 ) ，f 4 ( f 3 ( x ，t 3 ) ，x ，协 ) ( ，t 5 ) ，) ( ，“) ( 2 - 4 ) 在式2 - 4 中f 5 以f 2 和f 4 的输出作为输入，在数学上f 2 和f 4 的s l 是完全独 立的，但是在f 5 中却将其进行了耦合，这样的情况定义为逻辑并行。 资源并行： 理解为多个式2 3 描述的系统在并行执行，假定只有两个系统，a l 和a 吐， a l 系统中的f p l 和a 2 系统中的f q 2 都使用某个资源r ，而f pj 和f q 2 的划分的 s l 不仅与输入有关，而且r 资源的获取情况也是其v 空间的一个坐标。那么就 定义这样的情况为资源并行。 对于逻辑并行，既然逻辑上是关联的，最简单的方法就是针对式2 4 中f 2 和f 4 的s l 做联合分布描述。 对于资源并行，虽然f p l 和f q 2 是关联的，但是将资源获取情况作为其v 空 间的一个坐标后，仍然可以独立的傲风险评估。 2 3 运行态软件稳定性和正确性判定结论 基于2 1 的分析，可以知道软件系统的正确性和稳定性是静态不可预判的。 但是基于2 2 严格的数学推理，可以有以下的结论： ，将软件系统作为顺序模块集合考虑时，可以依据模块正确执行过程中的输入 记录的分布和当前输入，给出软件在当前运行状态下的出错概率。从而针对运行 态的软件系统，可以给出一个概率上的正确性和稳定性判断。 两北工业大学硕士学付论文运行态软件正确性和稳定性特征提取研究 第三章运行态软件正确性和稳定性特征提取研究 基于第二章的分析，如果取得运行软件各个模块的t 分布，和通过t 的分布 以及依据当前模块输入i l 【的值给出一个i l 【落在s l 之外的概率p 出来，