Open Access
Issue
JNWPU
Volume 38, Number 4, August 2020
Page(s) 862 - 872
DOI https://doi.org/10.1051/jnwpu/20203840862
Published online 06 October 2020

© 2020 Journal of Northwestern Polytechnical University. All rights reserved.

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

航空控制软件的性能和可靠性对航空电子系统的正常运行至关重要, 软件故障可能造成经济甚至人员损失等严重后果。当前, 航空控制软件故障的修复主要是人工操作, 修复效率与技术人员的专业素质和经验相关。为提升修复效率, 包括航空控制程序在内的软件的自动化修复技术的理论研究与应用已经受到学术界和工业界的普遍关注[1]。

文献[2-4]针对抽象语法树的节点, 采用略微不同的算法和不同的启发式方法, 对其进行删除、改变和插入的方式, 实现运算符和变量的改变, 形成可能的修复方案。Demarco等[5]通过修改if条件实现故障修复; Mechtaev等[6]在此基础上对if条件修复的工作进行扩展, 采用符号执行技术尝试对任意程序的表达式进行修复。文献[7-8]采用一个符号表达式替换正在修复的程序中的表达式, 该符号表达式表示泛型条件或变量的泛型赋值, 测试套件通过符号表达式的约束执行程序时, 通过判断测试用例是否通过执行, 以达到程序修复的目的。

南京理工大学[9]在Weimer团队的研究基础上, 提出了基于不变量的程序修复进化扩展模型。

哈尔滨工业大学王雪华对算术运算符、逻辑运算符等设计8个变异算子, 对C程序运算类故障进行修复[10]。同时, 哈尔滨工业大学迟洋设计了赋值表达式和变量值替换等4个变异算子, 对C程序运算表达式类故障进行定位和修复[11]。

构成航空软件的线程行为多采用Simulink/Stateflow[12-13]或AADL行为附件建模[14], 其中, 线程行为中布尔条件表达式是构成航空系统软件循环和分支控制逻辑的主要编程手段, 因此修复此类语句具有重要意义。

1 条件表达式故障分类方法

2 布尔条件表达式的故障分类方法

本文遵循Kapoor和Bowen[14]的定义和描述方法来描述抽象层表达式, 如表 1所示。忽略表达式中具体的变量及比较操作, 将表达式抽象为由“条件变量”、“与”、“或”和“非”表示的抽象表达式。

表1

抽象层表达式符号含义

3 抽象层故障分类

由于操作符故障中的表达式否定故障和变量否定故障在本质上均是在表达式中误将某一子表达式写为其否定表达式。因此, 这2种故障可以合并为一类故障, 即否定故障。操作数故障中的分句合取故障和分句析取故障, 这2类故障发生原因均为多写了某一子表达式。其区别仅在于多余的子表达式与原表达式的连接符号。因此, 这2种故障可以合并为一类故障, 即分句故障。经过合并之后, 本文关于C语言条件表达式抽象故障分类如下:

1) 操作符引用故障, 即operator reference fault(ORF)。此类故障是指在表达式中误把∧替换为∨, 或误把∨替换为∧。

2) 否定故障, 即negation fault(NF)。此类故障是指在逻辑表达式中误将一个其值为真(或假)的表达式替换为其值为假(或真), 或将参与逻辑表达式运算的某个条件替换为其对应的否定条件。

3) 关联故障, 即associative shift fault(ASF)。此类故障是因为对操作符优先级的判断缺少括号。

4) 分句故障, 即clause fault(CF)。此类故障是因为条件表达式中某一表达式ccc′或cc′替代。

4 具体层故障分类

C语言条件表达式故障还可能出现在具体层。即为包含条件表达式中的具体变量及其之间的比较, 即把抽象中的条件具体到变量, 例如

可以简化为

式中

(1) 式为抽象层, 把具体的变量ν和具体操作简化成了条件x1x2x3, 包含“与”“或”“非”3个操作, (3)~(5)式即为具体层。

具体层表达式符号见表 2, 具体层故障的分类包括:

表2

具体层表达式符号含义

1) 操作符故障, 即operator reference fault, 记为vORF。此类故障的原因是误把表达式中的具体层符号写为另一个具体层符号。

2) 操作数故障

① 操作数引用故障, 即variable reference fault, 记为vVRF。此类故障的原因是误把表达式中的某一具体层变量写为另一个可能变量。

② 操作数数值故障, 即variable value fault(VVF)。此类故障的原因是误把表达式中某一具体数字的数值写错。

③ 操作数否定故障, 即variable negation fault, 记为vVNF。此类故障的原因是误把表达式中的某个变量写为其否定形式。

5 条件表达式故障分类案例分析

1) 抽象层故障分类案例分析

① 操作符引用故障(ORF)。表 3为此类故障在C语言程序中出现的案例, 误把“‖”写为“ & & ”。

表3

操作符引用故障

② 否定故障(NF)。表 4为此类故障在C语言程序中出现的案例, 误把原表达式子表达式(foo‖!bar)写为其否定表达!(foo‖!bar)。

表4

否定故障

③ 关联故障(ASF)。表 5为此类故障在C语言程序中出现的案例, 运算顺序出现了错误, 没有为子表达式foo ‖!bar添加括号。

表5

关联故障

④ 分句故障(CF)。表 6为此类故障在C语言程序中出现的案例, 误把子表达式(foobar & & barfoo)写为(foobar & & barfoo & & foo)。

表6

分句故障

2) 具体层故障分类案例分析

操作符故障(vORF)。表 7为此类故障在C语言程序中出现的案例, 误把子表达式foo < bar中的操作符“ < ”写为“>”。

表7

操作符故障

6 基于变异算子的条件表达式自动化修复方法

7 变异算子的设计

根据C语言条件表达式故障分类, 提出了如表 8所示变异算子。采用各故障类型的名称对变异算子进行命名。例如, 针对操作符引用故障(ORF)的变异算子名为ORF变异。变异算子的描述见表 8

表8

变异算子

8 基于变异算子的修复方法

当读取到条件表达式时进行词法分析, 语法解析, 生成抽象语法树。再分别依据故障类型对语法树或表达式进行修复。下面依次描述每个步骤。并用(6)式为例, 解释说明每一个步骤。

1) 词法分析

这一步骤将读入的表达式解析成符号串序列, 每个符号串的信息如表 9所示。

表9

符号串内容

表 10中抽象层符号的“id”即为抽象层变量, 具体层符号类型中的“v”即为具体层变量。符号类型“DONE”无实际意义, 用来标示符号串的结束。

表10

符号类型

例如, 表达(6)式解析后的结果如表 11所示。

表11

(6) 式词法解析结果

2) 语法分析

语法分析步骤将根据C语言条件表达式的词法分析结果, 即符号串序列, 运用C语言条件表达式的语法结构定义, 将符号串序列解析为抽象语法树, 抽象语法树的基本结构包括图1抽象层节点的抽象语法树结构及图2具体层节点的抽象语法树结构。

在解析成语法树的过程中, 将子表达式的“非”在节点属性体现, 并不单独用节点表示。例如, 对表 11进行语法分析的结果如图3所示。

3) 基于变异算子的修复方法

本文采取的修复方法是试图对每一种可能的故障进行变异, 即, 依次假设该表达式为某一种故障, 对其实施相应变异算子的变异, 以得到变异版本, 再通过测试用例决定这个变异版本是否为可能修复结果。对于表达式的自动化修复分为2种:一种是基于符号串, 即词法解析结果的修复; 另一种是基于抽象语法树, 即语法解析结果的修复。下面分别对2种自动化修复方法用实例进行说明。

① 基于表达式的自动化修复

对于关联故障(ASF), 需要采用基于表达式的修复方法, 因为这类故障会影响抽象语法树的生成。关联故障的修复方法是对由“或”连接的子句加括号。例如, 表达式(6)的一个关联故障版本如下

对第一个用“或”连接的2个子表达v00 < =v01v02加上括号, 其结果为(v00 < =v01v02)& &(!(v03==v04) & & v05>v06), 用测试用例对这个表达式进行测试, 发现所有测试用例均通过。所以这个变异为一个可能的正确版本。再寻找下一个用“或”连接子表达式。对于本例, 只需实施一次ASF变异。至此, 修复工作完成。

② 基于抽象语法树的自动化修复

基于抽象语法树的修复工作在后序遍历树的同时进行, 对每一个节点进行可能的变异, 然后通过测试用例决定这个变异是否为可能正确版本。为方便描述, 下面采用变异算子名对修复命名, 例如, 通过实施ORF变异的修复过程称为ORF修复。基于抽象语法树的修复过程如图4所示。

每类修复的方法描述如下:

a) ORF修复:即实施ORF变异, 用“或”操作符替换“与”操作符, 反之亦然。每次遇到“与”或“或”操作符节点时便执行ORF修复。通过抽象树遍历到“与”或“或”操作符节点时就进行ORF变异, 然后通过测试决定该变异版本是否为可能正确版本。如果一个变异版本通过了所有测试用例, 其即为一个正确版本。

b) NF修复:即实施NF变异, 对于每一个子表达式或变量用其否定表达来替代。每次遇到变量节点时便执行NF修复, 包括抽象变量和具体变量。通过抽象树遍历到变量节点时就进行NF变异, 然后通过测试决定该变异版本是否为可能正确版本。

c) CF修复:即实施CF变异, 对于每一个分句, 依次删除其中出现的子句。执行CF修复的时间为后序遍历树的过程中遇到的每一个抽象层变量节点。当后序遍历到这些节点时就进行CF变异, 即依次删除这些节点。然后通过测试决定该变异版本是否为可能正确版本。

d) vORF修复:即实施vORF变异, 对于每一个具体层操作符(即 <, < =, >, >=, ==, !=), 依次用其他具体层操作符替代之。执行vORF修复的时间为后序遍历树的过程中遇到的每一个具体层操作符节点。依次用其余具体层操作符替换当前操作符后通过测试决定该变异版本是否为正确版本。

4) 测试

测试过程即用测试用例对表达式中的变量赋值, 然后计算表达式的值。如果表达式的值与预期的值一样, 则这个测试用例成功, 否则为失败。如果一个表达式可以通过测试集中的所有测试用例, 则这个表达式为正确版本, 否则为故障表达式。计算表达式的值的过程基于表达式的抽象语法树, 类似于语义分析, 在后续便利的过程中计算表达式的值。计算规则如表 12所示。

表12

表达式计算规则

thumbnail 图1

抽象层节点抽象语法树结构

thumbnail 图2

具体层节点抽象语法树结构

thumbnail 图3

表 11对应的抽象语法树

thumbnail 图4

基于抽象语法树的修复

9 变异修复停止条件的讨论

由于基于变异技术的故障修复方法无法修复全部类型的程序故障, 因此存在找不到潜在修复版本的问题。这就要求变异修复的设计人员为变异修复设定一个停止条件。对于本文所设计的修复方案, 主要时间复杂度与空间复杂度在于测试工作中对于抽象语法树的遍历。每次产生一个新的变异版本就需要遍历计算表达式的值, 估算算法所需遍历抽象语法树的次数即可对算法开销有大概的了解。遍历树的次数(见表 13)即为产生新版本的数量。

表13

遍历树的次数

表 14例举了一些具体情况下需要遍历抽象语法树的次数。表中“计算过程”的格式为“ORF修复产生的遍历次数”+“NF修复产生的遍历次数”+“CF修复产生的遍历次数”+“ASF修复产生的遍历次数”+“vORF修复产生的遍历次数”。表中考虑最复杂情况, 即所有抽象层操作符均为“‖”, 均需要ASF修复。

表14

例举遍历树的次数

C语言嵌入式程序条件表达式的变量个数并不会非常多。从计算规则以及例举来看, 随着变量次数的增多, 遍历树的次数增长幅度并不大。因此, 对于本文提出的算法, 并不需要设定停止条件。可以假设, 在内存占有过多或耗时过长之前, 本文提出的算法可以给出修复方法, 或者得出不可修复的结论。

10 辅助工具的开发与实验验证

11 辅助工具的设计与实现

12 输入输出描述

辅助工具的目的是修复C实体文件中的条件表达式故障, 用户可将可能需要修复的表达式以及其对应的测试用例文件写入文件, 第一行为表达式, 第二行为其对应的测试文件, 以此类推。文件可输入任意多个表达式。此外, 变异修复过程中, 需要执行成功测试用例和失败测试用例, 并将执行结果与测试用例的期望输出结果进行对比来确定一个变异体是否是一个潜在修复版本。因此, 用户还需输入测试用例的输入参数及期望输出结果, 文件格式的具体例子如图56所示。

程序输出分为三部分:表达式内容及测试用例文件名、测试结果及修复得到的可能正确的表达式。

thumbnail 图5

表达式文件格式

thumbnail 图6

测试文件格式

13 架构设计

图7为程序故障自动化修复工具的结构框架图。词法分析模块从文件中读入需解析的表达式, 并将其解析成符号串。解析结果用于语法分析及一部分自动化修复工作。语法分析模块从词法分析模块获得表达式词法分析的结果, 并进行语法分析。语法分析的结果将用于自动化修复工作以及测试模块的表达式计算过程。故障修复模块从词法分析及语法分析出获得符号串和抽象语法树, 并进行修复。修复模块的输出为新抽象语法树, 将传递给测试模块做测试工作。测试模块从语法分析模块获得抽象语法树, 从文件中读入测试用例进行测试工作。如果测试通过则输出修复后的表达式。表 15总结了各个模块的输入和输出内容。其中测试模块的输出“正确版本”只在测试通过时产生。

表15

模块输入输出说明

thumbnail 图7

修复工具框架结构图

14 实验对象

本文实验对象是被广泛使用的西门子程序套件, 用于研究控制流覆盖标准的故障检测能力, 西门子程序套件执行各种任务, 例如飞机防撞控制程序, 嵌入式任务优先级调度器程序等, 包括7个基本程序的错误版本和相应的测试套件。本文讨论的航空控制软件的条件表达式均来自西门子套件中7个程序, 各表达式的故障版本数及测试用例数如表 16所示,表达式故障共10种,155个。

表16

故障版本及测试用例数量

15 实验结果与分析

本节将对表达式(8)故障版本的自动化修复过程进行详细说明, 并对结果进行分析。

其期望表达式为:

1) 程序输入

本文所研发的辅助工具接受一个文件名参数, 该文件中由所需修复的表达式及其所对应测试用例的信息。本例中, 文件名为“a2.txt”, 如图8所示, 以“vi”命名“a2.txt”中涉及的表达式, 其中i为表达式序号。例如, 第1行表达式为v1, 第3行表达式为v2, 以此类推。

2) 测试文件

文件a2.txt中第一行表达式为正确表达式, 其测试用例存储在文件“t2.txt”中, 之后的9个表达式均为第一行表达式的单故障变异版本。在修复过程中, 程序会依次读入待修复表达式以及其对应的测试用例。测试文件“t2.txt”部分内容如图9所示。

3) 修复结果及分析

图10为(8)式的修改结果, 表达式v2, v6, v7及v10的修复结果中仅包含一个表达式, 如果测试用例是充分的, 那么可以认为这个表达式即为正确的。对于本实验, 经与表达式正确版本比对, 这4个表达式的修复结果均为正确的。表达式v3, v4, v5, v8及v9的修复结果中包含不止一个表达式。这种情况的出现有2个原因:表达式间为等价关系, 或测试用例不充分导致错误表达式都被误认为是正确的。这种情况需要人工介入, 判断是以上哪一种情况, 然后确定最终表达式的正确版本。对于本例, 在对表达式v3, v4, v5, v8及v9的修复结果进行分析后发现各表达式的修复结果间均为等价关系。由此说明修复是有效的。

本实验假设测试用例是充分的, 试验结果数据结果见表 19。实验中的155个故障表达式中, 55.5%的故障表达式可由本文提出的修复方法精确修复, 得出唯一一个且最优的解, 而剩余的44.5%的故障表达式在经过修复后得出了多个不同的解。这些解均为正确的, 但是其存在一些变量或者运算冗余问题, 计算机难以对这类语义相同的解进行优化选择, 需要在自动化修复后人工介入选择, 得出最优的修复结果。针对降低变量或运算冗余问题, 人工选择的原则为:首先将表达式按照C语言运算符优先级和自左至右结合律进行化简, 化简之后, 如果若干个表示式化简的结果一致, 则可以归类为相同解。若经过化简后仍然存在不相同的解, 则需要根据该段程序所需的最为合适的条件表达式进行手动选择, 以得到最优解。下面以表达式v4的修复结果为例进行说明人工介入的过程, (11)至(13)式为(10)式(即表达式v4)自动化修复所得。

表19

修复结果

为证明(11)~(13)式均与正确表达式(9)等价, 令exp即为(9)式, exp1为(11)式, exp2为(12)式, exp3为(13)式。证明过程如下:

1) 对于(11)式:

情况1:Own_Below_Threat=0

!Own_Below_Threat=1

exp1

=1‖!(Own_Below_Threat & & (Down_Separation>=ALIM)

=1

=exp

即exp1=exp

情况2:Own_Below_Threat=1

!Own_Below_Threat=0

exp1=0‖!(1 & & (Down_Separation>=ALIM))

=!(Down_Separation>=ALIM)

exp=0‖(1 & & (!(Down_Separation>=ALIM)))

=!(Down_Separation>=ALIM)

exp1=exp

2) 对于(12)式:

情况1:Own_Below_Threat=0

同理于1)。

情况2:Own_Below_Threat=1

!Own_Below_Threat=0

exp2

=0‖!(1 & & (!(Down_Separation>=ALIM)))

=!(!(Down_Separation>=ALIM))

=!(Down_Separation>=ALIM)

exp=!(Down_Separation>=ALIM)

exp2=exp

3) 对于(13)式:

情况1:Own_Below_Threat=0

同理于1)。

情况2:Own_Below_Threat=1

!Own_Below_Threat=0

exp3=0‖1 & & (!(Down_Separation>=ALIM))

=!(Down_Separation>=ALIM)

exp=!(Down_Separation>=ALIM)

exp3=exp

综上, (11)~(13)式均与(9)式等价, 因此这3个修复结果均可以归类为同一个修复结果, 即:

!Own_Below_Threat‖!(Own_Below_Threat & & (!(Down_Separation>=ALIM))

此过程即为人工介入进行简化变量或运算冗余过程。经过化简后可得唯一的正确解。

thumbnail 图8

文件a2.txt内容

thumbnail 图9

 

thumbnail 图10

(8) 式的修复结果

16 结论

本文主要针对C语言条件表达式, 研究基于条件表达式的故障分类以及变异技术的程序故障自动化修复, 提出了一种条件表达式的自动化修复方法。在此基础上, 设计并实现了针对C语言条件表达式故障自动化修复工具。本文主要以C语言条件表达式故障为例, 验证了文中提出的程序故障自动化修复方法。但是, 本文的方法并不受制于特定的程序语言。若想修复其他语言编写的程序, 只需重新设计变异算子即可。试验结果表明, 由布尔表达式设计的自动修复程序性能优良, 修复速度快, 满足航空控制软件的维护需求, 为航空控制软件的快速修复提供了一套行之有效的解决方案, 具有广阔的发展空间和良好的发展前景, 未来工作可以研究条件表达式等价的判断条件, 以此作为基础, 对修复结果进行分析, 找出等价表达式并挑选出最优结果。

References

  1. GAZZOLA L, MARIANI L, MICUCCI D. Automatic Software Repair: a Survey[C]//2018 IEEE/ACM 40th International Conference on Software Engineering, Gothenburg, 2018 [Google Scholar]
  2. KOU R, HIGO Y, KUSUMOTO S. A Capable Crossover Technique on Automatic Program Repair[C]//Proc Int Workshop Empirical Softw Eng Practice, 2016 [Google Scholar]
  3. JI T, CHEN L, MAO X, et al. Automated Program Repair by Using Similar Code Containing Fix Ingredients[C]//Proc Annu Comput Softw Appl Conf, 2016 [Google Scholar]
  4. ARCURI A. Evolutionary Repair of Faulty Software[J]. Appl Soft Comput, 2011, 11 (4): 3494– 3514 [Article] [CrossRef] [Google Scholar]
  5. DEMARCO F, XUAN J, BERRE D L, et al. Automatic Repair of Buggy if Conditions and Missing Preconditions with Smt[C]//Proc Int Workshop Constraints Softw Testing Verification Anal, 2014: 30–39 [Google Scholar]
  6. MECHTAEV S, YI J, ROYCHOUDHURY A. Angelix: Scalablemultiline Program Patch Synthesis Via Symbolic Analysis[C]//Proc Int Conf Softw Eng, 2016: 691–701 [Google Scholar]
  7. NGUYEN H, QI D, ROYCHOUDHURY A, et al. Semfix: Program Repair Via Semantic Analysis[C]//Proc Int Conf Softw Eng, 2013: 772–781 [Google Scholar]
  8. MECHTAEV S, YI J, ROYCHOUDHURY A. Directfix: Looking for Simple Program Repairs[C]//Proc Int Conf Softw Eng, 2015: 448–458 [Google Scholar]
  9. HE Jialang, ZHANG Kun, MENG Jin, et al. Invariants Based Program Repair Evolutionary Extended Model[J]. Application Research of Computers, 2010, 27 (12): 139– 141, 146 [Article] (in Chinese) [Google Scholar]
  10. WANG Xuehua, Design and Implementation of Fault Fixing System Based on Mutation Testing[D]. Harbin: Harbin Institute of Technology, 2016(in Chinese) [Google Scholar]
  11. CHI Yang. Research on Mutation-Based Software Fault Location[D]. Harbin: Harbin Institute of Technology, 2016(in Chinese) [Google Scholar]
  12. WANG Xuming, YU Fengquan, ZHU Xiaofei, et al. Functional Simulation of a Battle Plane Fuel System Based on Simulink/Stateflow[J]. Military Automation, 2018, 37 (4): 47– 52 [Article] (in Chinese) [Google Scholar]
  13. DONG J, JIAO J, XIA H, et al. Safety Simulation and Analysis for Complex Systems Concurrency Based on Petri Net and Stateflow Model[C]//2019 Annual Reliability and Maintainability Symposium(RAMS), Orlando, FL, USA, 2019: 1–7 [Google Scholar]
  14. KAPOOR K, BOWEN J P. Test Conditions for Fault Classes in Boolean Specifications[J]. ACM Trans on Software Engineering and Methodology, 2007, 16 (3): 10 [Article] [CrossRef] [Google Scholar]
  15. SAE Avionics Systems Division Embedded Computing Systems Committee. Architecture Analysis and Design Language(AADL) Annex D: Behavior Model Annex[S]. AS5506TM/3 Annex D, 2017 [Google Scholar]

All Tables

表1

抽象层表达式符号含义

表2

具体层表达式符号含义

表3

操作符引用故障

表4

否定故障

表5

关联故障

表6

分句故障

表7

操作符故障

表8

变异算子

表9

符号串内容

表10

符号类型

表11

(6) 式词法解析结果

表12

表达式计算规则

表13

遍历树的次数

表14

例举遍历树的次数

表15

模块输入输出说明

表16

故障版本及测试用例数量

表19

修复结果

All Figures

thumbnail 图1

抽象层节点抽象语法树结构

In the text
thumbnail 图2

具体层节点抽象语法树结构

In the text
thumbnail 图3

表 11对应的抽象语法树

In the text
thumbnail 图4

基于抽象语法树的修复

In the text
thumbnail 图5

表达式文件格式

In the text
thumbnail 图6

测试文件格式

In the text
thumbnail 图7

修复工具框架结构图

In the text
thumbnail 图8

文件a2.txt内容

In the text
thumbnail 图10

(8) 式的修复结果

In the text

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.