法律状态公告日
法律状态信息
法律状态
2018-07-10
授权
授权
2015-10-14
实质审查的生效 IPC(主分类):G06F9/44 申请日:20150325
实质审查的生效
2015-09-16
公开
公开
技术领域
本发明涉及软件可靠性增长模型研究领域,具体是指一种基于移动点和不完美排错的软 件可靠性建模方法。
背景技术
随着计算机技术的飞速发展,软件正日益广泛地应用于社会的各个领域,且规模越来越 大,复杂性越来越高。社会对具有高可靠性的软件的需求也在大幅度地增长,特别是应用于 尖端领域的软件,保障和预测其可靠性日益重要。软件工程的质量保证和评估重点就是如何 提高软件的可靠性。软件可靠性增长模型(Software Reliability Growth Model,简称SRGM) 是在数理统计学的基础上预测和评估软件可靠性的重要手段。
软件可靠性增长模型的实质是利用软件测试阶段的失效数据,对软件的运行情况进行评 估和预测,从而决定软件的可靠性水平是否达到用户的要求和是否可以发布使用。故障检测 过程和故障排除过程是软件测试阶段影响可靠性建模精度的两个重要因素。现有的大多数模 型对于故障检测过程的建模非常精确,只有少数文献对故障排除过程进行了研究。实际上, 故障排除过程中存在不完美排错现象,在软件可靠性建模中该现象涉及到的影响因素是故障 排除率函数和故障引入率函数。由于软件测试人员的技术水平不同,故障的结构和性质不同, 故障的难易程度不同,故障排除率并不是100%,且为随测试时间变化的函数;同时,在检测 故障的过程中可能会有新的故障引入,即存在故障引入率,且为随测试时间变化的函数。
对于不完美排错现象,有的学者虽然同时考虑故障排除率和故障引入率,但为了方便计 算,简化故障引入率的函数表达形式,对此过程的建模并不精确,进而导致所提出的软件可 靠性增长模型精度降低。此外,检测过程中的故障检测率既不是常值也不是连续平滑的,在 某时刻会发生瞬间变化,即存在移动点现象。移动点现象广泛存在于软件失效过程中,但目 前在故障检测与修正过程中同时考虑不完美排错和移动点现象的研究却没有。
文献:Pham H.,Nordmann L.,Zhang X.在1999年发表的《A general imperfect software debugging model with S-shaped fault-detection rate》提出了考虑故障引入率的PNZ模型,假设 故障引入率为常数,但没考虑故障排除率。
文献:Zhang X.,Teng S.,Pham H.在2003年发表的《Considering fault removal efficiency in software reliability assessment》提出了一种考虑故障排除率和引入率的软件可靠性增长模型, 假设故障排除率和故障引入率为常数。
文献:李春芝等在2005年发表的《考虑测试覆盖率和故障排除效率的软件可靠性增长模 型》提出了同时考虑测试覆盖率和故障排除率的模型,该模型中故障排除率不为100%且为一 个常数,但没有考虑故障引入率。
文献:刘宏伟等在同年发表的《一个NHPP类软件可靠性增长模型框架》研究了故障排 除过程,提出了一种NHPP类软件可靠性增长模型框架,但没有给出其具体数学表达形式, 无法对模型进行仿真验证并直接应用于实际工程中。
文献:谢景燕等在2010年发表的《考虑不完美排错情况的NHPP类软件可靠性增长模 型》认为软件的故障过程存在故障排除率和故障引入率,并且故障排除率是随时间变化的减 函数,但为简化计算过程将故障引入率设为常值。
文献:郑垒等在2011年发表的《考虑非理想排错过程的软件可靠性模型》在谢景燕研究 的基础上,提出故障引入率函数应正比于故障排除率函数,并假设两个函数具有相同的变化 趋势的减函数,体现不了故障引入率函数是故障总数函数相对于故障均值函数的瞬时变化率, 降低了所提出模型的精度。
文献:Huang等在同年发表的《Estimation and analysis of some generalized multiple change-point software reliability models》首次分析了不完美排错过程中的移动点现象,并提出 一种统一理论,构建了基于移动点技术和考虑不完美排错的软件可靠性增长模型,但在建模 过程中只考虑了故障引入率,未考虑故障排除率。
发明内容
本发明的目的是:同时考虑软件故障排除过程中的不完美排错现象和故障检测过程中的 移动点现象,解决现有的模型在故障检测过程和故障排除过程中假设条件不充分,推导出的 软件可靠性增长模型拟合和预测误差大的问题,提出一种基于移动点和不完美排错的软件可 靠性建模方法。
该方法具体步骤如下:
步骤一、提出基于移动点和不完美排错的软件可靠性建模基本假设条件;
<1>、到t时刻的累积故障数目N(t)服从均值函数为m(t)的NHPP过程。
<2>、任意时间间隔t时刻到t+Δt时刻内的期望软件故障检测数与t时刻剩余的软件故障数 成比例,比值为b(t)。
<3>、故障排除率不是100%,故障排除率函数p(t)是随着时间变化的减函数。
<4>、故障排除过程会引入新的故障,故障引入率函数β(t)是随时间变化的减函数。
<5>、软件运行剖面与可靠性测试剖面不同。
<6>、软件中每个故障是相互独立的,每个故障导致系统发生失效的可能性均相同。
步骤二、根据软件测试过程中的不完美排错现象,获取故障引入率函数和故障排除率函 数;
故障引入率函数β(t)为:
β(t)=βexp(-wt) (1)
其中w>0,w的大小决定了故障引入率变化的快慢。w越大,β(t)随时间t下降的越快; β为初始故障引入率,β∈[0,1],β(t)∈[0,β]。
故障排除率函数p(t)为:
其中k>0,k决定了故障排除率变化的快慢。k越大,p(t)随时间t下降的越快;p为 初始故障排除率,p∈[0,1],p(t)∈[0,p]。
步骤三、根据移动点现象,获取基于移动点和不完美排错的软件可靠性增长模型;
1)、对于单移动点τ,基于不完美排错的软件可靠性增长模型的均值函数为:
2)、对于双移动点τ1和τ2,基于不完美排错的软件可靠性增长模型的均值函数为:
3)、具有n个移动点时,基于移动点和不完美排错的软件可靠性增长模型的均值函数为:
步骤四、根据移动点判断准则,采用逐步调整法得到移动点个数和位置。
利用步骤三的基于移动点和不完美排错的软件可靠性增长模型得到n个移动点,通过移 动点判断准则,采用逐步调整法得到移动点个数和位置。
移动点判断准则具体为:
首先必须满足第一个点的初始位置,选用位于样本总数据时间五分之一的点之后,不包 括五分之一处对应的点;然后满足以下三条中的任意一条准则即可。
(1)三个连续的点落在中心线的同一侧,并且至少两个点距离中心线的距离大于或等于 2σ,σ为标准差;
(2)五个连续的点落在中心线的同一侧,并且至少有四个点距离中心线的距离大于或等 于σ。
(3)至少八个连续的点落在中心线的同一侧。
若质量控制图中任意点满足移动点判断准则,则该点为移动点,若该点后连续A点均满 足移动点判断准则任意一条,A的取值范围为2~4,则只取A点中任意一点为初始的移动点, 得到n个初始的移动点,分别记为ti,i=1,2,…,n;
通过逐步调整法,得到移动点的具体位置,具体包括以下几个步骤:
首先,由τ0=0到t2时刻之间的失效数据,确定移动点τ1;然后,固定移动点τ1,通过τ1和 t3之间的失效数据确定移动点τ2;依次类推,逐步调整得到准确的移动点τi,i=0,1,…,n。
根据τi和ti+2之间的失效数据确定移动点τi+1的方法具体为:
基于移动点的软件可靠性增长模型的故障累计均值函数,得到τi和τi+2之间故障累计均值 函数为:
建立目标函数:
其中,y(t)为t时刻软件累积故障数的实测值,a1,a2,…,am为m(t)中的未知参数,m为 参数个数。
求式(18)对a1,a2,…,am的偏导,得:
上述方程组(19)对移动点τi+1的求解不存在封闭解,通过对上述等式中τi+1值在 (τi,…,τi+2)范围内的逐步选择,得到使目标函数达到最小值的移动点τi+1。
设(τi,…,τi+2)中有N个点,具体估算移动点τi+1步骤如下:
(1)取利用方程组(19),求出参数a1,a2,…,am的最小二乘估 计
(2)将带入式(18),得
(3)比较{T1,...,TN}的大小,得到τi+1的最小二乘估计值τi+1={τi+1j|Tj=min(T1,...,TN)}; 综上,最终得到软件可靠性增长模型的移动点的准确位置。
本发明的优点与积极效果在于:
(1)本发明软件可靠性增长模型建模方法考虑到现有的模型条件假设弊端,建立全面考 虑软件测试情况的软件可靠性增长模型;
(2)本发明软件可靠性增长模型建模方法同时考虑不完美排错现象和移动点现象,将两 者融合到软件可靠性建模中,更贴近软件测试实际情况;
(3)本发明软件可靠性增长模型建模方法区别于以往的考虑不完美排错的软件可靠性增 长模型,引入移动点技术,模型具有更强的拟合能力和预测能力。
附图说明
图1是本发明一种基于移动点和不完美排错的软件可靠性建模方法的流程示意图;
图2是本发明中软件失效数据的质量控制图;
图3是本发明中模型1-模型5针对故障检测数的拟合能力曲线;
图4是本发明中模型1-模型5针对故障检测数的预测能力曲线;
图5是本发明中模型5-模型6引入移动点前后的预测能力曲线。
具体实施方式
下面将结合附图和实施例对本发明作进一步的详细说明。
一种基于移动点和不完美排错的软件可靠性建模方法,同时全面考虑故障排除过程中的 不完美排错现象和故障检测过程中的移动点现象,建立基于不完美排错和移动点的软件可靠 性增长模型;首先,运用NHPP类模型假设,结合新的故障引入率函数以及现有的故障排除 率函数,拟合故障排除过程中的不完美排错,提出一种基于不完美排错的软件可靠性增长模 型;然后根据故障检测过程中的移动点现象,提出一种新的基于移动点技术和基于不完美排 错的软件可靠性增长模型。最后利用一组公开发表的数据,验证模型的精度,根据实验结果 表明,本发明提出的软件可靠性增长模型具有更好的拟合效果和预测能力。
本发明一种基于移动点和不完美排错的软件可靠性建模方法,如图1所示,包括以下步 骤:步骤一、提出基于移动点和不完美排错的软件可靠性建模基本假设条件;
为了构建基于移动点技术和不完美排错的软件可靠性增长模型,基本假设如下:
<1>、到t时刻的累积故障数目N(t)服从均值函数为m(t)的NHPP过程。
NHPP(Non-Homogeneous Poisson Process),是指运用非齐次泊松过程类模型假设。
<2>、任意时间间隔t时刻到t+Δt时刻内的期望软件故障检测数与t时刻剩余的软件故障 数成比例,比值为b(t)。
<3>、故障排除率不是100%,故障排除率函数p(t)是随着时间变化的减函数。
<4>、故障排除过程会引入新的故障,故障引入率函数β(t)是随时间变化的减函数。
<5>、软件运行剖面与可靠性测试剖面不同。
<6>、软件中每个故障是相互独立的,每个故障导致系统发生失效的可能性均相同。
只要满足步骤一的基本假设条件的系统均适用本发明的基于移动点和不完美排错的软件 可靠性建模方法,不仅仅是电子海图信息显示系统。
步骤二、根据软件测试过程中的不完美排错现象,获取故障引入率函数和故障排除率函 数;
软件的故障引入率会随着测试时间的进行而逐渐降低,当测试时间足够长时,故障引入 效率趋近于0。故障引入率函数β(t)是测试时间的函数,而且呈递减的趋势。系统中的故障 引入率越低,说明技术人员在排除故障过程中的失误和保留的故障的影响越小,系统的软件 可靠性越高。
由于故障引入率函数β(t)受到检测到的尚未被排除的故障的影响,是故障总数函数相对 于故障均值函数的瞬时变化率,与故障排除率函数的下降趋势不同。故障引入率函数采用指 数形式,能更好地体现故障排除过程中引入新故障的趋势,又能区别于故障排除率函数。
一种新的故障引入率函数为:
β(t)=βexp(-wt) (1)
其中w>0,w决定了故障引入率变化的快慢。w越大,β(t)随时间下降的越快;w越 小,β(t)随时间下降的越缓慢。β为初始故障引入率,由系统中故障的类别和性质决定, β∈[0,1],β(t)∈[0,β]。
随着软件测试的进行,保留在软件系统中的软件故障的结构和性质会受到影响,故障排 除率也会发生相应的变化。在系统中简单的故障先被开发人员排除,保留在软件中的容易排 除的软件故障会逐渐减少,难以排除的软件故障会逐渐增加,软件的故障排除率由此会逐渐 降低。随着测试时间的增加,测试工作进行到集成和系统测试阶段,测试人员越来越难以检 测到保留在系统中的故障。当测试时间足够长时,故障排除率会趋近于0。故障排除率函数 是基于测试时间的函数,随时间的增加而递减。
系统中的故障排除率越高,说明技术人员排除的故障数越多,系统的软件可靠性越高。 因此,故障排除率函数取如下形式:
其中k>0,k决定了故障排除率变化的快慢。k越大,p(t)随时间下降的越快;k越小, p(t)随时间下降的越缓慢。p为初始故障排除率,由系统中故障的类别和性质决定,p∈[0,1], p(t)∈[0,p]。
步骤三、根据移动点现象,获取基于移动点和不完美排错的软件可靠性增长模型;
移动点为:实际工程中,故障检测率依赖于测试人员的能力、测试资源的分布、故障的 难易程度和测试工具等,所以故障检测率既不是常数也不是平滑连续的,即它在某时刻发生 瞬时改变,该时刻称为移动点。移动点为参数发生变化时的时刻,是模型的参数发生不连续 的时刻。
故障检测率不再是模型中的常值,而是依据时间变化的分段函数。
对于单移动点τ基于不完美排错的软件可靠性增长模型,其故障检测率b(t)为
当累积故障时间在[0,τ]时,
根据假设<1>的条件得到:
其中,m(t)为软件故障均值函数:
m(t)=E[N(t)]
N(t):在[0,t]时间段内软件测试人员检测到的软件实际累积故障数;m(t)为选取模型的 预测值。
x(t):软件故障排除函数,到时刻t为止,被检测到并被排除的软件故障数。
n(t):软件故障总数函数,等于x(t)和到时刻t为止软件系统中未被检测到的故障数之和。
b1、b2为故障检测率在不同时刻的常数值。
根据假设<3>的条件得到:
根据假设<4>的条件得到:
对公式(4)进行微分得
令则公式(7)化简为
l'=b1l×(β(t)-p(t)) (8)
代入步骤二中的公式(1)和公式(2),求解方程可得
其中,C1为常数。
根据边界条件m(0)=0和n(0)=a,结合解出模型的故障均值函数为
其中,a为开始进行软件测试时系统中存在的软件初始故障总数;
同时可得故障排除函数x(t)为
同理,可得到当累积故障时间在[0,t]时,模型的均值函数为:
则,单移动点τ的基于不完美排错的软件可靠性模型的均值函数为,
对于双移动点τ1和τ2,基于不完美排错的软件可靠性增长模型,其故障检测率为:
其中,b1、b2、b3为故障检测率在不同时刻的常数值。
其累积故障的均值函数为:
对于具有n个移动点τ1,τ2,τ3......τn的不完美排错的软件可靠性增长模型,由具有单移
动点和双移动点的不完美排错的软件可靠性增长模型推导出,其故障均值函数为:
步骤四、根据移动点判断准则,采用逐步调整法得到移动点个数和位置。
利用一组公开发表的软件失效数据,绘制失效数据集的质量控制图,结合移动点判断准 则,分析其移动点的个数和位置;
移动点判断准则具体为:
首先必须满足第一个点的初始位置,选用位于样本总数据时间五分之一的点之后,不包 括五分之一处对应的点;然后满足以下三条中的任意一条准则即可。
(1)三个连续的点落在中心线的同一侧,并且至少两个点距离中心线的距离大于或等于 2σ,σ为标准差;
(2)五个连续的点落在中心线的同一侧,并且至少有四个点距离中心线的距离大于或等 于σ。
(3)至少八个连续的点落在中心线的同一侧。
若质量控制图中任意点满足移动点判断准则,则该点为移动点,若该点后连续A点均满 足移动点判断准则任意一条,A的取值范围为2~4,则只取A点中任意一点为初始的移动点, 得到n个初始的移动点,分别记为ti,i=1,2,…,n;
采用逐步调整法,得到移动点的准确位置。
具体包括以下几个步骤:
首先,由τ0=0到t2时刻之间的失效数据,确定移动点τ1;然后,固定移动点τ1,通过τ1和t3之间的失效数据确定移动点τ2;依次类推,逐步调整得到准确的移动点τi,i=0,1,…,n。
根据τi和ti+2之间的失效数据确定移动点τi+1的方法具体为:
基于移动点的软件可靠性增长模型的故障累计均值函数,得到τi和τi+2之间故障累计均值 函数为:
建立目标函数:
其中,y(t)为t时刻软件累积故障数的实测值,a1,a2,…,am为m(t)中的未知参数,m为 参数个数。
求式(18)对a1,a2,…,am的偏导,得:
上述方程组(19)对移动点τi+1的求解不存在封闭解,通过对上述等式中τi+1值在 (τi,…,τi+2)范围内的逐步选择,可得到使目标函数达到最小值的移动点τi+1。
设(τi,…,τi+2)中有N个点,具体估算移动点τi+1步骤如下:
(1)取τi+1j=τi+j,(j=1,…,N),利用方程组(19),求出参数a1,a2,…,am的最小二乘 估计
(2)将带入式(18),得
(3)比较{T1,...,TN}的大小,得到τi+1的最小二乘估计值τi+1={τi+1j|Tj=min(T1,...,TN)};
综上,最终得到软件可靠性增长模型的移动点的准确位置。
本发明选用的一个公开发表的软件失效数据集是:针对罗马航空研究中心项目的T1系统 得到的,T1系统是用来实时命令和控制程序的,软件大约有21700个对象指令,9名程序员 用了21周时间完成了测试。
在测试阶段,消耗了25.3CPU小时,得到136个累积故障检测数CDF(Cumulative Detected Faults)和136个累积故障排除数CRF(Cumulative Removed Faults),具体数据见表1。
表1 系统失效数据
根据失效数据集绘制质量控制图,如图2所示,横坐标表示的是故障累计时间,纵 坐标表示的是故障检测数。根据移动点判断准则,图中只有第13-18周的连续六个点都在 中心线的上侧,且这六个点与中心线的距离均大于或者等于σ,满足移动点判断准则, 初步选定第13周为该组数据集中的第一个移动点。通过质量控制图,可确定该组数据集 中只有一个移动点。采用逐步调整法,得到唯一的移动点是第12周对应的点。
本发明选用的另一个实验数据是:
电子海图信息显示系统(Electric Chart Display and Information System,简称ECDIS)包括 海图显示、信息查询、航海导航等多种功能模块;在Tornado2.2开发环境下,利用C++语言编 写,在VxWorks嵌入式系统上运行。根据测试需求说明书,测试时间共持续了65天,共设 计了130个测试用例,消耗了21天,执行测试用例和收集失效数据消耗了44天,共发现96 个软件故障,故障排除数为96个。
步骤五、利用步骤四中的数据做仿真实验,实验结果表明,本发明提出的模型具有更好 的拟合效果和预测能力;
步骤5.1、选择对比模型;
为了验证本发明提出的软件可靠性增长模型的拟合能力和预测能力,选择5个经典的软 件可靠性增长模型作为对比模型,该5个模型均为故障排除率和故障引入率相关。
(1)模型1:G-O模型,该模型假设检测到的故障被立即移除,不会引入新的故障。
(2)模型2:PNZ模型,该模型考虑引入新故障的可能性,故障引入率为常值,没 有考虑故障排除率。
(3)模型3:谢景燕等提出的模型:该模型同时考虑故障排除率和故障引入率,故障排 除率是随时间变化的函数,故障引入率为常值。
(4)模型4:郑垒等提出的模型:该模型同时考虑故障排除率和故障引入率,故障排除 率和故障引入率均是随时间递减的函数,且二者成正比例。
(5)模型5:考虑不完美排错的软件可靠性增长模型
(6)模型6:本发明中提出的模型,基于移动点和不完美排错的软件可靠性增长模型。
步骤5.2、对步骤5.1的6种模型分别进行验证;
主要是针对各个模型的均方误差、确定系数和相对误差进行比较验证;
I)、均方误差(Mean Square Error,MSE):展示长期预测的定量比较,更好地理解实际和 预期值的差异。
MSE定义为
其中n是选择数据集的大小,mi是到ti时刻检测或排除的故障的实际数量,m(ti)是到ti时 刻检测或排除故障的模型预计数量。MSE越小意味着拟合误差越小,性能更好。
II)、确定系数(R-square)定义为:
其中,
R-square的值越接近于1,说明模型的预期值与实际失效数据越接近,具有越好的拟合能 力。
III)、相对误差(Relative Error,RE):模型根据现在和过去的失效行为来预测未来失效行 为的能力为预测能力,通过计算数据集的RE值来表达:
根据每个时间间隔的RE值绘制模型的预测能力曲线。曲线越快地收敛于零轴,说明RE 越小,意味着模型具有越小的拟合误差和更好的性能。
针对故障检测数的各模型参数估计值和拟合能力如表2所示。结果表明,与其他模型相 比,模型6的MSE最小且R-square最接近1。说明随着移动点技术的引入,拟合的模型越接 近真实数据。特别是,由于失效数据集中数据较少,模型6针对故障检测数的评价结果的优 势并不大。在实际的软件测试过程中,失效数据集会比较庞大,对故障排除过程的精确建模 会令所提出的模型的性能更大限度地优于其他模型。
表2 模型1-模型6参数估计值和拟合能力
模型1-模型5针对故障检测数的拟合能力和预测能力曲线,如图3和图4所示,除了模 型1外,其他模型2-模型5均能在测试时间的60%后与实际数据保持较小的相对误差。模型 5的预测能力曲线相对于其他模型,以更快的速度向横轴靠近,RE趋近为零;表明模型5与 实际数据的相对误差最小,能够更好地拟合和预测软件的失效数据,即考虑不完美排错模型 更符合实际测试过程并且效果最好。
将模型5与引入移动点后的模型6进行对比仿真,如图5所示,可以看出,模型5和模 型6均能在测试时间的60%后与实际数据保持较小的相对误差,且收敛于横轴,RE趋近为零。 但是模型6的RE曲线相对于模型5,以更快的速度向横轴靠近,表明随着移动点技术的引入, 模型6能够更好地拟合和预测软件的失效数据。
同理,考虑移动点和不完美排错的电子海图系统软件可靠性增长模型可以更好的拟合系 统失效过程。
因此,本发明提出的一种基于移动点和不完美排错的软件可靠性建模方法,具有更强的 拟合能力和预测能力。
机译: 建模和模拟通过阵列进行不完美图案化对集成电路的影响
机译: 不完美传输介质的建模组件的结构
机译: 不完美传输介质的建模组件的结构