基于故障森林的组合测试故障定位研究

doi:10.3969/j.issn.0253-2778.2018.01.004

中国科学技术大学学报 ›› 2018, Vol. 48 ›› Issue (1): 28-34.DOI: 10.3969/j.issn.0253-2778.2018.01.004

基于故障森林的组合测试故障定位研究

王勇，黄志球，韦良芬，卢桂馥

1.南京航空航天大学计算机科学技术学院，江苏南京 210000；2.安徽工程大学计算机与信息学院，芜湖 241000；3.安徽三联学院计算机工程系，安徽合肥 230601

收稿日期:2017-05-16 修回日期:2017-06-22 出版日期:2018-01-01 发布日期:2018-01-01
通讯作者: 王勇
作者简介:王勇（通讯作者）男，1979生，博士/副教授，研究方向：软件测试，故障定位，机器学习等.Email：yongwang@ahpu.edu.cn
基金资助:
国家高技术研究发展计划（863）（2015AA105303）；国家自然科学基金（61272083，61572033）；软件新技术与产业化协同创新中心；安徽高校优秀青年人才支持计划重点项目(gxyqZD2016124)；安徽省高校自然科学基金重点项目（KJ2016A252）；安徽省自然科学基金（1608085MF147）资助.

Locating failure-inducing combinations based on fault forest

WANG Yong, HUANG Zhiqiu, WEI Liangfen, LU Guifu

1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics Nanjing 210000， China；
2. College of Computer and Information, Anhui Polytechnic University Wuhu 241000， China；
3. Department of Computer Engineering, Anhui SanLian University Hefei 230601， China）

Received:2017-05-16 Revised:2017-06-22 Online:2018-01-01 Published:2018-01-01

摘要/Abstract

摘要： 组合测试作为一种对参数组合空间抽样的系统方法，适用于待测系统中存在由特定参数组合所引发的软件失效.依据组合测试结果，定位出最小失效诱因模式（minimal failure-causing schema ,MFS）有助于程序员进行故障源检测与修复.然而，组合测试可能存在mask effect，使得测试用例中即使包含MFS也未必一定触发软件失效.因此，在存在mask effect的系统中精确定位最小失效诱因模式尤为困难.为此提出了一种基于故障森林的组合测试故障定位方法. 给定一个t-路组合测试集（t≥2）及其附加测试集，该方法首先学习由多个深度为t的基本故障分类树所组成的故障森林，然后从故障森林中提取基本故障组合模式，最后将可疑MFS进行排序，并提交给程序员进行进一步诊断.仿真实验结果表明，该方法能有效定位系统中存在的组合故障模式.特别地，对于存在mask effect的待测系统，故障定位结果健壮.

关键词: 组合测试, 故障定位, 故障森林, 最小失效诱因模式

Abstract: Combinatorial testing, a method for sampling parameter combination in the parameter space of a system, is suitable for systems in which failure is caused by a specific parameter combination. Based on the results of combination testing, locating the minimal failure causing schema (MFS) can help programmers to localize faults and repair them. However, combination testing might be affected by the mask effect, and even test cases containing MFSs may not necessarily trigger a failure. Therefore, it is extremely difficult to pinpoint MFSs in systems affected by the mask effect. A fault location method based on fault forest is proposed. Given a set of t-way combination test (t≥2) and their augment test set, this method first learns some basic fault trees which generate a fault forest, then extracts the basic suspicious MFS from the forest, and finally orders those suspicious MFSs by their suspiciousness which will help programmers perform further diagnosis. The simulation results show that the presented method can effectively identify MFS. In particular, for the systems affected by mask effect, result is robust.

Key words: combinatorial testing, fault localization, fault forest, MFS

中图分类号:

TP311

王勇，黄志球，韦良芬，卢桂馥. 基于故障森林的组合测试故障定位研究[J]. 中国科学技术大学学报, 2018, 48(1): 28-34.

WANG Yong, HUANG Zhiqiu, WEI Liangfen, LU Guifu. Locating failure-inducing combinations based on fault forest[J]. Journal of University of Science and Technology of China, 2018, 48(1): 28-34.

参考文献

［1］
NIE C, LEUNG H. A survey of combinatorial testing[J]. ACM Computing Surveys (CSUR), 2011, 43(2): 11(1-29).
[2] 严俊, 张健. 组合测试: 原理与方法[J]. 软件学报, 2009, 20(6): 1393-1405.
YAN J, ZHANG J. Combinatorial testing: Principles and methods[J]. Journal of Software, 2009, 6: 004.
[3] GHANDEHARI L S, BORAZJANY M N, LEI Y, et al. Applying combinatorial testing to the Siemens suite[C]// Proceeding of IEEE International Conference on Software Testing Verification and Validation Workshops. Luxembourg: IEEE Press, 2013: 362-371.
[4] GARGANTINI A, PETKE J, RADAVELLI M, et al. Validation of constraints among configuration parameters using search-based combinatorial interaction testing[C]// 8th International Symposium on Search Based Software Engineering. Springer, 2016: 49-63.
[5] GHANDEHARI L S G, LEI Y, XIE T, et al. Identifying failure-inducing combinations in a combinatorial test set[C]// IEEE 5th International Conference on Software Testing, Verification and Validation (ICST). IEEE, 2012: 370-379.
[6] GARGANTINI A, PETKE J, RADAVELLI M. Combinatorial Interaction Testing for Automated Constraint Repair[C]// Proceeding of IEEE International Conference on Software Testing Verification and Validation Workshops. Tokyo: IEEE Press, 2017: 239-248.
[7] ARCAINI P, GARGANTINI A, VAVASSORI P. Automatic detection and removal of conformance faults in feature models[C]// Proceeding of IEEE 9th International Conference on Software Testing Verification and Validation . Chicago: IEEE Press, 2013: 102-112.
[8] 徐宝文,聂长海,史亮,等. 一种基于组合测试的软件故障调试方法[J]. 计算机学报,2006,(01):132-138.
XU B W, NIE C H, SHI L, et al. A software failure debugging method based on combinatorial design approach for testing[J]. Chinese Journal of Computers, 2006, 29(1): 132.
[9] NIE C, LEUNG H. The minimal failure-causing schema of combinatorial testing[J]. ACM Transactions on Software Engineering and Methodology (TOSEM), 2011, 20(4): 15(1-38).
[10] ZHANG Z, ZHANG J. Characterizing failure-causing parameter interactions by adaptive testing[C]// Proceedings of the 2011 International Symposium on Software Testing and Analysis. Portland: ACM Press, 2011: 331-341.
[11] NIU X, NIE C, LEI Y, et al. Identifying failure-inducing combinations using tuple relationship[C]// IEEE 6th International Conference on Software Testing, Verification and Validation Workshops. Chicago: IEEE Press, 2013: 271-280.
[12] DUMLU E, YILMAZ C, COHEN M B, et al. Feedback driven adaptive combinatorial testing[C]// Proceedings of the 2011 International Symposium on Software Testing and Analysis. Portland: ACM Press, 2011: 243-253.
[13] GHANDEHARI L S, CHANDRASEKARAN J, LEI Y, et al. BEN: A combinatorial testing-based fault localization tool[C]// Proceeding of 2015 IEEE 8th International Conference on Software Testing Verification and Validation Workshops. Chicago: ACM Press, 2015: 1-4.
[14] YILMAZ C, FOUCHE S, COHEN M B, et al. Moving forward with combinatorial interaction testing[J]. Computer, 2014, 47(2): 37-45.
[15] YILMAZ C, COHEN M B, PORTER A A. Covering arrays for efficient fault characterization in complex configuration spaces[J]. IEEE Transactions on Software Engineering, 2006, 32(1): 20-34.
[16] SHAKYA K, XIE T, LI N, et al. Isolating failure-inducing combinations in combinatorial testing using test augmentation and classification[C]// IEEE 5th International Conference on Software Testing, Verification and Validation. Washington,:IEEE Press, 2012: 620-623.
[17] HAN J, PEI J, KAMBER M. Data Mining: Concepts and Techniques[M]. Elsevier, 2011.
[18] YU L, LEI Y, KACKER R N, et al. ACTS: A combinatorial test generation tool[C]// Proceeding of IEEE International Conference on Software Testing Verification and Validation. Luxembourg: IEEE Press, 2013: 370-375.

()
(

[1]	吴加禹，李永坤，许胤龙. 一种读写均衡的高性能键值存储系统[J]. 中国科学技术大学学报, 2020, 50(6): 825-831.
[2]	蔡勇，陈红梅，. MapReduce环境下基于概念分层的概念格并行构造算法[J]. 中国科学技术大学学报, 2018, 48(4): 275-283.
[3]	徐婉茹，杨盘隆. 移动广告用户传播能力评价与覆盖优化算法[J]. 中国科学技术大学学报, 2017, 47(7): 569-574.

基于故障森林的组合测试故障定位研究

Locating failure-inducing combinations based on fault forest

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价