基于上下文的飞控软件老化缺陷定位方法研究

杜晓婷，王 楠

1.北京航空航天大学 自动化科学与电气工程学院，北京 100191

2.杜克大学 电子与计算机工程学院，北卡罗莱那 达勒姆 27708，美国

基于上下文的飞控软件老化缺陷定位方法研究

杜晓婷1+，王 楠2

1.北京航空航天大学 自动化科学与电气工程学院，北京 100191

2.杜克大学 电子与计算机工程学院，北卡罗莱那 达勒姆 27708，美国

随着航空工业的发展和飞控软件复杂度的提高，对飞控软件可靠性和实时性的要求也越来越高。软件老化缺陷中存在一类缺陷，会使系统响应逐渐变慢，最终出现失效，严重影响飞控软件的可靠性和实时性，但目前没有定位这类缺陷的有效方法。针对这类缺陷的定位，提出了一种基于上下文的飞控软件老化缺陷定位方法。该方法将飞控软件的主循环建模成一棵任务树，飞控软件反复运行的主循环抽象成一个任务树序列。通过Mann-Kendall Test对任务树中心节点的时间属性进行趋势检测，找到可疑任务，并根据任务树之间的关系对可疑任务进行筛选，定位出含有缺陷的任务，则该任务所对应的函数即为缺陷所在的位置。实验表明，该方法不仅能够给出缺陷的具体位置，还能给出发生失效时的调用上下文。

飞控软件；老化缺陷；缺陷定位；上下文；任务树

1 引言

由于飞控软件工作环境比较特殊，相对于一般软件而言，对实时性和可靠性都有着更高的要求。然而存在一类缺陷，会使飞控软件响应速度逐渐变慢，最终出现失效，对飞行安全带来严重挑战，这类缺陷属于老化缺陷中的一种。

老化缺陷会随着时间表现出越来越显著的现象，比如内存升高，系统响应变慢等，即出现软件老化。当软件在执行过程中遇到老化缺陷时，可能会导致不可预测的失效，这种失效会对飞控软件的正常运行造成严重影响，进而威胁飞行安全。为了增加飞控软件的可靠性，本文针对造成飞控系统响应变慢的老化缺陷，根据飞控软件运行过程特点，提出了基于上下文的老化缺陷定位方法。

飞控软件的主要运行过程是定时执行一个主循环，在主循环中，飞控系统读取外界传感器数据和驾驶指令，计算并输出到执行机构。此外，飞控系统会完成一些额外的工作，比如日志记录、通讯等。从广义的角度来看，每一次主循环都可以看作一个测试用例，输入是传感器信号和控制指令，输出是舵机角度、油门、写入的日志等。整个运行过程中反复运行的主循环，就是一连串测试用例输入的过程，将这个过程称为一个测试用例链。如果可以把飞控软件反复运行的主循环拆分成不同的子任务，然后在测试用例链运行过程中，检测这些子任务随着测试用例链输入而运行时间变长的情况，就可以利用这些信息来定位老化的源头，从而找到造成系统响应变慢的老化缺陷。

飞控软件中每一个任务的执行实际上对应于一个函数调用，因此某一个任务的执行时间逐渐变长，也就说明了该任务所对应的函数调用时间逐渐变长，即这个函数可能含有引起老化的缺陷。然而，这个结论是不完全的。因为任务的执行或者函数的调用存在嵌套关系，一个函数的调用时间出现老化，既可能是该函数本身的实现有问题，也可能是这个函数所调用的函数的实现有问题。只有当人们观察到其子任务或子函数的执行时间都没有出现老化时，才能确定是这个函数含有缺陷。另外，一个函数含有缺陷，并不代表每一次运行都会表现出来，缺陷的触发可能依赖程序运行的上下文。比如，函数A的缺陷可能只有在B→A→C这样的调用顺序下才会触发，而在D→A→C这样的情况下不会触发，捕捉这样的上下文显然有利于后续的调试工作。为了对此类造成飞控系统响应变慢的老化缺陷进行定位，并捕捉发生老化的上下文，本文建立了飞控软件运行过程的任务树模型。通过该模型，将飞控软件反复运行的主循环抽象成一个任务树序列。通过分析任务树内任务之间的父子关系，以及这些关系给缺陷定位带来的影响，根据任务和函数运行之间的对应关系，提出了针对任务树序列来定位老化缺陷的方法。通过该缺陷定位方法，不仅可以找到发生老化的任务，还可以找到老化发生时的函数调用上下文，对后续的调试过程有非常积极的意义。

本文组织结构如下：第2章介绍相关研究；第3章对飞控软件的运行过程主循环进行建模；第4章介绍基于任务上下文的飞控软件老化缺陷定位方法的基本思想和方法流程；第5章通过实验，验证本文方法的有效性；最后是结束语。

2 相关研究

1994年Parnas[1]首次提出了软件老化的概念，Huang等人[2]对老化缺陷进行了具体描述：软件老化是由内存膨胀和泄漏，未释放的文件锁，数据损坏，存储空间碎片化和舍入误差的积累等原因造成的。在软件老化中，错误随着时间积累，导致系统性能下降或出现失效。

目前解决软件老化问题的方法可以分为两类：

一类是reactive方法[3]，这种方法是在失效发生之后，采取一定的恢复机制尝试修复失效，恢复率较高。但这种方法无法保证在每次出现失效后，始终能够提供一种令人满意的恢复机制来保证软件的长期运行。

另一类proactive方法与reactive方法不同，这是一种软件恢复的方法[2-4]，相比reactive方法效果更好，应用也更广泛。软件恢复的主要步骤包括终止程序运行，清理程序的内部状态和环境，最后重新启动该程序。软件恢复本质上通过对软件进行恢复，预防软件的老化。由于软件恢复需要很高的代价，如何寻找最优软件恢复时间和最优软件恢复策略成为研究的重点。这些工作可以分为两类：基于模型的分析方法和基于测量的分析方法。基于模型的分析方法建立系统的数学模型[5-9]，通过这些模型确定软件恢复的有效性并得到最优恢复方案，模型的精确度取决于捕获老化信息时所做的假设。文献[5]使用马尔科夫再生随机Petri网（Markov regenerative stochastic Petri nets，MRSPN）模型来描述系统的行为，并计算出软件可靠性最大情况下的最优恢复间隔。基于模型的恢复策略，一般假设太过理想，在实际的工程领域中不容易验证。

基于测量的方法通过监控软件系统的操作状况[9-14]，收集关键性能数据，以此来分析软件的老化程度。文献[9]给出了一种检测和估计UNIX操作系统老化的方法，使用基于简单网络管理协议（simple network management protocol，SNMP）的分布式检测工具收集系统资源的使用数据和系统活动数据，应用趋势检测技术对这些数据进行处理，检测老化的存在，并使用坡度估计方法计算“资源耗尽时间”。文献[12]提出了一种基于时间序列的分析方法，检测和估计一个网络服务器在软件老化的影响下，系统资源的耗尽时间，并用线性回归方法对数据进行趋势检测。

基于目前提出的各种软件恢复方法，文献[15]对各种恢复策略的代价进行了估计，分析了这些方法对消除软件老化影响的效果，提出选择软件恢复策略时应合理平衡恢复效果和使用代价二者的关系，为选择合适的恢复策略提供指导。

上述这些方法都只是暂时地延缓了失效时间，并没有从根本上解决软件中存在的缺陷，老化缺陷对飞控系统的实时性和可靠性仍然存在很大威胁。如何定位老化缺陷，从而为修复缺陷提供依据，是本文要研究的问题。

传统软件缺陷定位技术依赖于对失败测试用例的分析[16-19]，而对于老化缺陷而言，失效难以复现，因此失败测试用例非常少，严重影响了现有的缺陷定位方法的效果。本文针对一类造成飞控软件响应变慢的老化缺陷，结合飞控软件运行过程的特点，设计了一种该类缺陷的定位方法。

3 飞控软件运行主循环任务树模型

首先对飞控软件的运行过程进行描述，然后提出缺陷定位的任务树模型，并对该模型进行分析。

因为飞控软件对运行过程的可预测性要求很高，所以一般不会采用抢占式多任务调度器。飞控软件的主循环调度过程如下：在主循环开始时，先运行与飞行器控制相关的关键任务；当关键任务运行完后，如果还有时间，将按照预先设定的优先级调度需要CPU时间的任务；在运行某一任务之前，先判断该任务的运行时间上限是否已经超过了主循环还剩下的时间，如果没超过，那么正常运行，如果超过了，在本次主循环中就跳过该任务。可以看出，在该调度策略下，不同任务的运行时间并不会有交叠。另外，一个任务通常包含子任务，比如更新飞行控制状态的任务包含读取GPS，读取陀螺仪等子任务。于是，可以把一次主循环用一棵任务树来表示。

下面给出任务树及其相关定义：

定义1（任务集，任务树，任务树序列）将所要讨论的所有任务组成一个集合，叫任务集。如果选取任务集的一个子集，用这些任务构成一棵树，并给每个节点赋上一个时间属性，这样一棵树叫作任务树。如图1所示，任务树的根节点为飞控软件运行的主循环，其余每个节点代表一个任务，节点的第一行是任务的名字，第二行是任务的执行时间，即该任务本次的消耗。节点之间的连线表示任务的分解，除叶子节点外，每个节点还包括一个或多个子节点，表示每个任务的完成都是通过一系列子任务来实现的。在飞控软件中，飞控主循环的每一次运行都对应着这样一棵任务树。飞控软件的运行过程中反复运行的主循环就构成一个任务树序列。

任务树还满足一定的性质：

（1）父任务的执行时间总是大于等于其所有子任务的总和。因此当某子任务的执行时间变长时，有可能使其所有直系先辈节点的执行时间变长。

（2）不同时间段上的主循环所对应的任务树并不相同，这是因为并不是所有的飞行任务在每次主循环都会执行。有些不紧急的任务周期会很长，可能长达几秒，因而被主循环执行的频率会很低；而有些紧急任务的周期可能只有几毫秒，但却会被主循环频繁执行。

定义2（上下文树，完全上下文树）关于任务t的上下文树是一棵包含t的任务树T，并且在该任务树中，t只有直系的祖先节点，且t叫作任务树T的中心节点。关于任务树T和该任务树中的一个任务t的完全上下文树ContextT(t)是任务树的一棵子树，该子树是t的上下文树，并且包含t的所有后代节点和T的根节点。

当人们说一个完全上下文树发生老化时，表示在一个任务树序列中，该完全上下文树的中心节点的时间属性呈现上升趋势。

基于上文的描述和定义，所考虑的缺陷定位问题可以这样描述：某一任务t含有执行时间老化的缺陷，将它叫作目标任务。在某一任务树序列中，t的执行时间仅在某一个上下文树出现时才可能发生老化，将它叫作目标上下文树。缺陷定位问题就转化为寻找这样一棵目标上下文树的问题。

4 基于任务上下文的飞控软件老化缺陷定位方法

首先介绍缺陷定位方法的基本步骤，并通过一个例子对该方法进行分析，最后对本文使用的Mann-Kendall趋势检测方法进行具体描述。

4.1 缺陷定位方法

Fig.1 Example of task tree图1 任务树的例子

在飞控软件中，每一个任务的执行对应于一个函数调用，当某一个任务的执行时间逐渐变长，也就说明了该任务所对应的函数调用时间逐渐变长。因为任务的执行或者函数的调用存在嵌套关系，一个函数的调用时间出现老化，既有可能是该函数本身的实现有问题，也可能是这个函数所调用的函数的实现有问题。只有当其子任务或子函数的执行时间都没有出现老化时，才能确定是这个函数含有缺陷。另一方面，一个函数含有缺陷，并不代表每一次运行都会表现出来，缺陷的触发可能依赖程序运行的上下文。为了给出缺陷的位置并捕捉缺陷触发的上下文，利用上文给出的任务树模型对飞控软件的老化缺陷进行定位。如图2所示，缺陷定位方法共分为6个步骤，下面对这6个步骤进行具体描述。

Fig.2 Procedures of context based fault localization method图2 基于任务上下文的缺陷定位方法步骤

（1）对飞控软件进行插桩，并运行能够引起老化的失效测试用例。

在飞控软件的源码中插入记录语句，记录函数的进入时间和退出时间，以便计算函数的运行时间，以及生成函数之间的调用关系，这些信息被写入日志文件中。因为人们只关心在主循环中能够被调用到的函数，所以只有这一部分函数需要被插桩。通过运行能够引起老化的失效测试用例，可以得到一个记录所有被插桩函数进入时间和退出时间的文件。

（2）构建任务树序列和完全上下文树序列。

在记录文件中，可以找到每一次主循环的开始和结束时间，对于每一次主循环的运行，可以根据各个函数的进入和退出时间，确定它们之间的调用关系，由此生成一棵任务树，如图3所示。其根节点是main函数，其余每个节点都表示一个函数，从上到下的连线表示函数之间的调用关系。对于每一次主循环的运行，都生成这样一棵任务树，于是得到一个任务树序列。对于任务树序列中的每一棵任务树，选择其任意一个节点生成一棵完全上下文树，并把相同的完全上下文树归并到一个集合里面。然后根据它们根节点的进入时间进行排序，这样就得到了若干完全上下文树序列，其中每个序列中的完全上下文树是相同的，不同序列中的完全上下文树是不同的。

Fig.3 Task tree图3 任务树

（3）对完全上下文树的中心节点进行趋势检测。

对于每一个完全上下文树序列，将其中心节点的运行时间提取出来，组成一个运行时间序列。接下来，对每一个运行时间序列进行趋势检测，图4所示为出现老化现象的完全上下文树的一个例子，图中的浅色节点是这些上下文树的中心节点，也是被检测出运行时间存在上升趋势的点。那么就可以找到存在上升趋势的时间序列所对应的完全上下文树，这些上下文树就是与老化相关的完全上下文树。本文使用Mann-Kendall趋势检测方法。

（4）提取目标上下文树。

上一步中，得到了若干与老化相关的完全上下文树。接下来，需要识别出这些完全上下文树的包含关系，对这些完全上下文树进行筛选，并提取完全上下文树的公共部分，得到目标上下文树。当一棵完全上下文树包含另一棵完全上下文树时，前者的中心节点所表现出来的老化现象很可能是受到后者的影响，因此应当将前者去掉。得到已经去掉含有子树的完全上下文树的集合后，最后一步就是去掉这些完全上下文树的多余节点。在前面的步骤，考虑了每一个中心节点运行的全部上下文，然而缺陷的触发有可能只依赖部分的上下文，甚至根本不依赖上下文。这一步中，只需要提取出上一步获得的集合中所有树的公共部分，就能找到真正与缺陷相关的上下文，也就是需要寻找的目标上下文树。

如图4，树（3）的中心节点的时间属性之所以呈上升趋势，是因为树（3）的中心节点a调用了树（2）的中心节点b，所以a的老化现象很可能是b带来的，需要排除掉树（3）。同理，需要把树（2）、（3）、（5）、（6）都去掉。去掉这些完全上下文树后的集合如图5所示。对图5中的完全上下文树提取公共部分后，得到的目标上下文树如图6所示。于是，定位到了引起老化的缺陷所在的位置：任务t所对应的函数。不仅如此，还给出了这种缺陷触发所依赖的上下文：从b到t的调用。

Fig.4 Sets of aging full context trees图4 发生老化的完全上下文树集合

从上述步骤可以看到，基于任务树的缺陷定位方法能够通过完全上下文树之间的包含关系，排除因为受其他任务影响而老化的任务，有效减少false positive的产生。另外，该方法还通过完全上下文树之间的共性，给出了与老化密切相关的调用上下文。

4.2 基于Mann-Kendall的老化趋势检测

Mann-Kendall趋势检测方法[20]是最广泛使用的非参数检验方法，不要求样本必须服从一定分布，且检验不受个别异常值的干扰，计算简便。本文关注的是任务树中的某一节点的时间属性是否有递增的趋势。对于每一个完全上下文树序列，将其中心节点的运行时间（退出时间减去进入时间）提取出来，组成一个运行时间序列，通过Mann-Kendall对每一个运行时间序列进行趋势检测，筛选出被检测到具有上升趋势的运行时间序列。

Fig.5 Sets of aging full context trees after filtering subtrees图5 去掉含有子树的完全上下文树集合

Fig.6 Goal context tree图6 目标上下文树

设运行时间序列为{xt:t=1,2,…,n}；原假设H0：时间序列{xt}没有变化趋势；备择假设H1：时间序列{xt}有变化趋势。统计量S的计算如式（1）所示：

其中，l＞k，sgn为符号函数。

如果时间序列x1,x2,…,xn中不存在相同数值，S的方差为：

如果时间序列x1,x2,…,xn中存在m组相同数值，其中tp为第p组对应的数值，S的方差为：

对S标准化，可得：

5 实验分析

本文通过在开源飞控软件Ardupilot上人工植入老化缺陷，利用上文提出的缺陷定位方法进行缺陷定位实验，验证算法的有效性。首先对实验对象及实验设计与实现过程进行描述，然后将收集到的实验数据通过Mann-Kendall进行趋势检测，最后对实验结果进行分析。

5.1 实验对象

Ardupilot是一套无人机自动飞行控制系统，支持多旋翼飞行器、固定翼飞机和传统直升机。系统由固定翼/多旋翼载机、APM飞行控制板、数传模块、电子罗盘、各类传感器和地面站组成。虽然不如载人飞行器的飞控软件复杂，但是它也有近20万行代码（不包括实时操作系统Nuttx的代码和底层驱动的代码），足够满足本次实验的要求。更重要的是，无论是Ardupilot还是客机的飞控软件，它们的主要运行过程都是一个反复执行的主循环，本文提出的缺陷定位方法正是基于飞控软件的这个特点。

5.2 实验设计与结果分析

首先，对Ardupilot进行了插桩，即在函数入口处和出口处插入了语句记录函数的进入和退出，并且记录了响应的进入时间和退出时间。在调度器、硬件抽象层和主循环这些经常运行的66个函数中进行了插桩。接下来，在Ardupilot的Copter::motors_output函数中植入一个模拟老化的缺陷，即加入了一个随着运行次数增加的延迟。将修改好的程序写入一个无人机中，然后飞行该无人机10min。最后，将无人机的日志文件取出。依据该记录文件，可以计算函数的运行时间并确定它们的调用关系。根据这些信息，每一次Ardupilot主循环的运行都可以建模成一棵任务树，图7和图8给出了这种任务树的两个例子。其中的节点对应着一个函数（或任务），其编号和具体函数的对应关系如表1所示。

Fig.7 Example 1 of main loop task tree图7 主循环任务树的样例1

Fig.8 Example 2 of main loop task tree图8 主循环任务树的样例2

通过运行实验，收集任务树，提取完全上下文树序列，得到每一个完全上下文树序列中的中心节点的运行时间，组成一个运行时间序列。并使用Mann-Kendall趋势测试对所有长度大于100的完全上下文树序列进行测试（长度太小难以进行趋势检测），其中α值取10-7。

实验表明有两个完全上下文树中心节点的时间属性呈现上升趋势，如表2所示。共有两个完全上下文树表现出了显著的老化，它们的中心节点分别是Copter::fast_loop和Copter::motors_output，所对应的完全上下文树分别如图9和图10。可以看到，中心节点为Copter::fast_loop的完全上下文树完全包含了中心节点为Copter::motors_output的完全上下文树，因此前者应该去掉，这是由于前者之所以发生老化是因为后者的影响。排除掉前者后，就找到了真正发生老化的任务或函数，即Copter::motors_output，图10为其调用的上下文。

Table1 Function names and their number表1 编号和函数名对应关系

Table2 Results of trend test表2 趋势测试结果

最终的定位结果与植入的缺陷位置是一致的，因此说明了基于上下文的缺陷定位方法的有效性。

6 结束语

本文提出了一种针对飞控软件中一类造成系统响应变慢的老化缺陷的定位方法。根据飞控软件的运行特点，建立了任务树模型。通过对飞控软件中部分函数进行插桩，并运行会使软件老化的测试用例，分析得到若干任务树序列和完全上下文树序列。使用Mann-Kendall趋势检测方法对完全上下文树序列的时间属性进行趋势检测，证明了老化的存在。最后通过识别包含关系筛选完全上下文树，去除完全上下文树中的多余节点，提取出目标上下文树。此外，以Ardupilot为实验对象，本文设计并进行了实验。实验结果表明，本文方法不仅能定位出老化缺陷的位置，还能给出发生老化时的调用上下文，对后续的调试有很大帮助。

在对飞控软件缺陷定位方法的研究中，人们仅仅针对单缺陷问题进行了研究，没有分析多个老化缺陷存在时的缺陷定位方法。此外，本文只分析了造成飞控软件响应变慢的一类缺陷。内存泄露缺陷与使飞控软件响应变慢的缺陷类似，这类缺陷的失效也有一个积累的过程，但它们并不一定会使系统响应变慢，因为这类缺陷的触发并不会像与响应时间有关的缺陷一样有一个向上传播的过程，所以无法使用本文提出的缺陷定位方法。未来将针对上述两个问题做进一步研究。

Fig.9 Afull context tree with a central node Copter::fast_loop图9 中心节点为Copter::fast_loop的完全上下文树

Fig.10 Afull context tree with a central node Copter::motors_output图10 中心节点为Copter::motors_output的完全上下文树

[1]Parnas D L.Software aging[C]//Proceedings of the 16th International Conference on Software Engineering,Sorrento,Italy,May 16-21,1994.Washington:IEEE Computer Society,1994:279-287.

[2]Huang Y,Kintala C,Kolettis N,et al.Software rejuvenation:analysis,module and applications[C]//Proceedings of the 25th International Symposium on Fault-Tolerant Computing,Pasadena,USA,1995.Washington:IEEE Computer Society,1995:381-390.

[3]Candea G,Cutler J,FoxA.Improving availability with recursive microreboots:a soft-state system case study[J].Performance Evaluation,2004,56(1/4):213-248.

[4]Trivedi K S,Vaidyanathan K.Software aging and rejuvenation[J].Wiley Encyclopedia of Computer Science and Engineering,2008:1-8.

[5]Garg S,PuliafitoA,Telek M,et al.Analysis of software rejuvenation using Markov regenerative stochastic Petri net[C]//Proceedings of the 6th International Symposium on Software Reliability Engineering,Toulouse,France,Oct 24-27,1995.Washington:IEEE Computer Society,1995:180-187.

[6]Garg S,PuliafitoA,Telek M,et al.Analysis of preventive maintenance in transactions based software systems[J].IEEE Transactions on Computers,1998,47(1):96-107.

[7]Trivedi K S,Vaidyanathan K,Goševa-Popstojanova K.Modeling and analysis of software aging and rejuvenation[C]//Proceedings of the 33rd Annual Simulation Symposium,Washington,Apr 16-22,2000.Washington:IEEE Computer Society,2000:270-279.

[8]Bao Yujuan,Sun Xiaobai,Trivedi K S.Aworkload-based analysis of software aging,and rejuvenation[J].IEEE Transactions on Reliability,2005,54(3):541-548.

[9]Castelli V,HarperR E,Heidelberger P,et al.Proactive management of software aging[J].IBM Journal of Research and Development,2001,45(2):311-332.

[10]Garg S,Van MoorselA,Vaidyanathan K,et al.Amethodology for detection and estimation of software aging[C]//Proceedings of the 9th International Symposium on SoftwareReliability Engineering,Paderborn,Germany,Nov 4-7,1998.Washington:IEEE Computer Society,1998:283-292.

[11]Vaidyanathan K,Trivedi K S.Ameasurement-based model for estimation of resource exhaustion in operational software systems[C]//Proceedings of the 10th International Symposium on Software Reliability Engineering,Boca Raton,USA,Nov 1-4,1999.Washington:IEEE Computer Society,1999:84-93.

[12]Li Lei,Vaidyanathan K,Trivedi K S.An approach for estimation of software aging in a Web server[C]//Proceedings of the 2002 International Symposium on Empirical Software Engineering,Nara,Japan,Oct 3-4,2002.Washington:IEEE Computer Society,2002:91-100.

[13]AvritzerA,CzeksterR M,Distefano S,et al.Software aging and rejuvenation for increased resilience:modeling,analysis and applications[M]//Resilience Assessment and Evaluation of Computing Systems.Berlin,Heidelberg:Springer,2012:167-183.

[14]Grottke M,Li L,Vaidyanathan K,et al.Analysis of software aging in a Web server[J].IEEE Transactions on Reliability,2006,55(3):411-420.

[15]Alonso J,MatiasR,Vicente E,et al.Acomparative experimental study of software rejuvenation overhead[J].Performance Evaluation,2013,70(3):231-250.

[16]Li Wei,Zheng Zheng,Hao Peng,et al.Predicate executionsequence based fault localization algorithm[J].Chinese Journal of Computers,2013,36(12):2406-2419.

[17]Hao Peng,Zheng Zheng,Zhang Zhenyu.et al.Self-adaptive fault localization algorithm based on predicate execution information analysis[J].Chinese Journal of Computers,2014,37(3):500-511.

[18]PytlikB,Renieris M,Krishnamurthi S,et al.Automated fault localization using potential invariants[J].arXiv preprint cs/0310040,2003.

[19]Xuan Jifeng,Monperrus M.Learning to combine multiple ranking metrics for fault localization[C]//Proceedings of the 2014 International Conference on Software Maintenance and Evolution,Victoria,Canada,Sep 28-Oct 3,2014.Washington:IEEE Computer Society,2014:191-200.

[20]GilbertR O.Statistical methods for environmental pollution monitoring[M].Hoboken,USA:John Wiley&Sons,Inc,1987.

附中文参考文献：

[16]李伟,郑征,郝鹏,等.基于谓词执行序列的软件缺陷定位算法[J].计算机学报,2013,36(12):2406-2419.

[17]郝鹏,郑征,张震宇,等.基于谓词执行信息分析的自适应缺陷定位算法[J].计算机学报,2014,37(3):500-511.

Context Based Fault Localization Method for Flight Control SoftwareAging Defects

DU Xiaoting,WANG Nan.Context based fault localization method for flight control software aging defects.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1214-1223.

DU Xiaoting1+,WANG Nan2
1.School ofAutomation Science and Electrical Engineering,Beihang University,Beijing 100191,China
2.School of Electrical and Computer Engineering,Duke University,Durham,North Carolina 27708,USA
+Corresponding author:E-mail:xiaoting_2015@buaa.edu.cn

With the development of aviation industry and the higher complexity of flight control software,the requirements of the reliability and real-time performance become higher.This paper investigates a special type of aging defects which will affect the reliability and real-time performance of software systems,due to the reason that it will result in the slow response on software systems.However,there is no effective method to address this type of defects for flight control software.Inspired by that,this paper proposes a context based fault localization method.First of all,the main loop of the flight control software is modelled as a task tree,then the repeated running processes of the main loop can be considered as a task tree series.By utilizing Mann-Kendall Test,the time attribute of the central node of the task tree is detected to find the suspicious task.Thereafter,according to the relationship among the task tree series,suspicious tasks are selected to locate defects.The function of suspicious task is the location of the defect.Finally,an experiment is implemented and the results show that the proposed method can not only locate the defect,but also give the call context.

flight control software;aging defect;fault localization;context;task tree

was born in 1990.He

the M.S.degree in aero-nautical engineering from Beihang University.Now he is a Ph.D.candidate at School of Electrical and Computer Engineering,Duke University.His research interests include software dependability modeling and software fault localization. 王楠（1990—），男，四川沐川人，美国杜克大学博士研究生，主要研究领域为软件测试建模，缺陷定位。

DU Xiaoting was born in 1992.She is an M.S.candidate at Beihang University.Her research interests include software testing and software fault localization.杜晓婷（1992—），女，山东济宁人，北京航空航天大学硕士研究生，主要研究领域为软件测试，缺陷定位。

A

：TP311

Received 2016-08,Accepted 2016-10.

CNKI网络优先出版:2016-10-19,http://www.cnki.net/kcms/detail/11.5602.TP.20161019.1458.002.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1214-10

10.3778/j.issn.1673-9418.1609021

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056