Combinatorial Test Sequence Set Reduction Approach for Railway Signaling Safety-Critical Software
-
摘要: 针对现有铁路信号系统安全关键软件t-路组合测试序列生成方法在处理大规模输入时产生冗余测试序列，导致测试执行成本较高的问题，提出了一种基于贪婪-粒子群混合优化算法的t-路组合测试序列集约简方法，用于降低序列集的执行成本. 首先，以执行成本最低为约简目标，建立针对t-路组合测试序列集约简的优化模型；然后，在保证测试序列集逻辑覆盖特性的基础上，采用贪婪-粒子群混合优化算法求解模型，计算约简后的测试序列集；最后，以ZPW-2000轨道电路接收器软件作为研究对象，以其生成的2-路组合测试序列集为例开展约简验证. 结果表明，所提方法在保证2-路组合覆盖和逻辑覆盖的前提下，对单个序列集的执行成本约简幅度最高达到98.33%，对序列集总的执行成本约简幅度达到36.10%，验证了所提方法的可行性和有效性.Abstract: When applying t-way combinatorial test sequence generation to a railway signaling system with large-scale inputs, test redundancy occurs, which causes high execution cost. Thus, a t-way combinatorial test sequence set reduction approach is proposed based on the greedy particle swarm optimization algorithm to reduce the cost. First, aiming at minimizing the test cost, an optimization model for t-way combinatorial test sequence set reduction is built. Then, on the basis of logic coverage of the test sequence sets, the greedy particle swarm algorithm is employed to solve the model and obtain the reduced test sequence sets. Finally, ZPW-2000 track circuit receiver software is used in a case study for the reduction of 2-way test sequence sets to validate the proposed approach. Results show that under the premise of 2-way coverage and logic coverage, the cost for a single test sequence set has decreased by up to 98.33% and the total cost for the test sequence sets has decreased by 36.10%, which indicates the feasibility and effectiveness of the approach.
-
表 1 举例SUT的2-路组合测试序列集
Table 1. 2-way test sequence sets of the example SUT
序列集 2-路组合测试序列 T1 ${\tau _{\rm{1}}}$ = {12，21，31，42}，${\tau _{\rm{2}}}$ = {11，21，32，41}，
${\tau _{\rm{3}}}$ = {12，21，33，41}，${\tau _{\rm{4}}}$ = {11，22，31，42}，
${\tau _{\rm{5}}}$ = {12，22，32，41}，${\tau _{\rm{6}}}$ = {11，22，33，42}，
${\tau _{\rm{7}}}$ = {12，23，31，41}，${\tau _{\rm{8}}}$ = {11，23，32，42}，
${\tau _{\rm{9}}}$ = {12，23，33，42}T2 ${\tau _{{\rm{10}}}}$ = {12，21，31，52，61}，${\tau _{{\rm{11}}}}$ = {11，21，32，51，61}，
${\tau _{{\rm{12}}}}$ = {12，21，33，51，61}，${\tau _{{\rm{13}}}}$ = {11，22，31，52，61}，
${\tau _{{\rm{14}}}}$ = {12，22，32，51，61}，${\tau _{{\rm{15}}}}$ = {11，22，33，52，61}，
${\tau _{{\rm{16}}}}$ = {12，23，31，51，61}，${\tau _{{\rm{17}}}}$ = {11，23，32，52，61}，
${\tau _{{\rm{18}}}}$ = {12，23，33，52，61}
下载: 导出CSV
表 2 事件取值个数及其执行成本
Table 2. Domain size and cost of the input events
输入事件 执行成本/s 取值/个 有效信号1 3 9 有效信号2 3 9 有效信号3 3 9 频率无效 1 24 电压无效 1 20 2 s 内频率无效 1 24 2 s 内电压无效 1 20 频率-电压无效 2 24 电压-频率无效 2 20
下载: 导出CSV
表 3 测试路径与序列集
Table 3. Test paths and sequence sets
测试路径 路径长度 路径对应的序列集 序列/条 P1 3 T1 480 P2 6 T2 480 P3 5 T3 576 P4 3 T4 180 P5 1 T5 9 P6 5 T6 216 P7 9 T7 607 P8 3 T8 480 注：路径长度即对应测试路径包含的事件数.
下载: 导出CSV
表 4 序列集约简结果
Table 4. Result of test sequence set reduction
序列集 约简后的序列/条 执行成本/s 成本降幅/% 约简前 约简后 T1 240 2 880 1 440 50.00 T2 400 4 320 3 600 16.67 T3 242 6 336 2 662 57.98 T4 180 1 260 1 260 0.00 T5 1 27 3 88.89 T6 84 1 512 588 61.11 T7 592 7 891 7 696 2.47 T8 8 2 880 48 98.33
下载: 导出CSV
-
郭进. 铁路信号基础[M]. 北京: 中国铁道出版社, 2010. 杨志杰, 禹志阳. 列车运行控制系统测试技术[M]. 北京: 中国铁道出版社, 2016: 1-12. AMMANN P, OFFUTT J. Introduction to software testing[M]. Cambridge: Cambridge University Press, 2016. 王秀玄. 基于UML的列控中心改变运行方向功能测试用例生成方法研究[D]. 成都: 西南交通大学, 2016. 袁磊,吕继东,刘雨,等. 一种全覆盖的列控车载系统测试用例自动生成算法研究[J]. 铁道学报,2014,36(8): 55-62. doi: 10.3969/j.issn.1001-8360.2014.08.010YUAN Lei, LÜ Jidong, LIU Yu, et al. Research on model-based test case generation method of onboard subsystem in CTCS-3[J]. Journal of the China Railway Society, 2014, 36(8): 55-62. doi: 10.3969/j.issn.1001-8360.2014.08.010 吕继东,朱晓琳,李开成,等. 基于模型的CTCS-3级列控系统测试案例自动生成方法[J]. 西南交通大学学报,2015,50(5): 917-927. doi: 10.3969/j.issn.0258-2724.2015.05.023LÜ Jidong, ZHU Xiaolin, LI Kaicheng, et al. Model-based test case automatic generation of CTCS-3 train control system[J]. Journal of Southwest Jiaotong University, 2015, 50(5): 917-927. doi: 10.3969/j.issn.0258-2724.2015.05.023 梁茨,郑伟,李开成,等. 基于路径优化算法的测试序列自动生成及验证[J]. 铁道学报,2013,35(6): 53-58. doi: 10.3969/j.issn.1001-8360.2013.06.009LIANG Ci, ZHENG Wei, LI Kaicheng, et al. Automated generation of test cases and sequences based on path optimization algorithm[J]. Journal of the China Railway Society, 2013, 35(6): 53-58. doi: 10.3969/j.issn.1001-8360.2013.06.009 赵晓宇,杨志杰,吕旌阳. 基于有色Petri网的车载设备模式转换测试序列生成方法[J]. 中国铁道科学,2017,38(4): 115-123. doi: 10.3969/j.issn.1001-4632.2017.04.16ZHAO Xiaoyu, YANG Zhijie, LÜ Jingyang. Test sequence generation method of mode transition for on-board equipment based on colored petri net[J]. China Railway Science, 2017, 38(4): 115-123. doi: 10.3969/j.issn.1001-4632.2017.04.16 陈鑫,姜鹏,张一帆,等. 一种面向列车控制系统中安全攸关场景的测试用例自动生成方法[J]. 软件学报,2015,26(2): 269-278.CHEN Xin, JIANG Peng, ZHANG Yifan, et al. Method of automatic test case generation for safety-critical scenarios in train control systems[J]. Journal of Software, 2015, 26(2): 269-278. KUHN D R, WALLACE D R, GALLO A M. Software fault interactions and implications for software testing[J]. IEEE Transactions on Software Engineering, 2004, 30(6): 418-421. doi: 10.1109/TSE.2004.24 严俊,张健. 组合测试:原理与方法[J]. 软件学报,2009,20(6): 1393-1405. doi: 10.3724/SP.J.1001.2009.03497YAN Jun, ZHANG Jian. Combinatorial testing:principles and methods[J]. Journal of Software, 2009, 20(6): 1393-1405. doi: 10.3724/SP.J.1001.2009.03497 王子元,聂长海,徐宝文,等. 相邻因素组合测试用例集的最优生成方法[J]. 计算机学报,2007,30(2): 200-211. doi: 10.3321/j.issn:0254-4164.2007.02.006WANG Ziyuan, NIE Changhai, XU Baowen, et al. Optimal test suite generation methods for neighbor factors combinatorial testing[J]. Chinese Journal of Computers, 2007, 30(2): 200-211. doi: 10.3321/j.issn:0254-4164.2007.02.006 唐抗尼,肖宝弟. 城市轨道交通ATP车载设备测试用例生成方法[J]. 中国铁道科学,2011,32(4): 99-103.TANG Kangni, XIAO Baodi. A test case generation method of on-board ATP equipment in urban rail transit[J]. China Railway Science, 2011, 32(4): 99-103. RAO C, GUO J, LI N, et al. Applying combinatorial testing to high-speed railway track circuit receiver[C]// Proceedings of the IEEE International Conference on Software Testing, Verification and Validation Workshop. [S.l.]: IEEE, 2017: 199-207. KENNEDY J, EBERHART R C. A discrete binary version of the particle swarm algorithm[C]// Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. [S.l.]: IEEE, 1997: 4104-4108. 聂长海. 组合测试研究进展[J]. 中国科技论文,2017,12(20): 418-421.NIE Changhai. The latest research development of combinatorial testing[J]. China Sciencepaper, 2017, 12(20): 418-421. LI N, LI F, OFFUTT J. Better algorithms to minimize the cost of test paths[C]//Proceedings of the IEEE Inter-national Conference on Software Testing, Verification and Validation. [S.l.]: IEEE, 2012: 280-289. LEI Y, KACKER R, KUHN D R, et al. IPOG/IPOG-D:efficient test generation for multi-way combinatorial testing[J]. Software Testing,Verification and Reliability, 2008, 18(3): 125-148. doi: 10.1002/stvr.381 -
下载:
点击查看大图
图(4) / 表(4)
计量
- 文章访问数: 555
- HTML全文浏览量: 200
- PDF下载量: 10
- 被引次数: 0