Locating failure-inducing combinations based on fault forest

doi:10.3969/j.issn.0253-2778.2018.01.004

Abstract

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

CLC Number:

TP311

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.

References

［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]	WU Jiayu, LI Yongkun, XU Yinlong. A read/write balanced high-performance key-value store [J]. Journal of University of Science and Technology of China, 2020, 50(6): 825-831.
[2]	CAI Yong, CHEN Hongmei,. A parallel algorithm for constructing concept lattice based on hierarchical concept under MapReduce [J]. Journal of University of Science and Technology of China, 2018, 48(4): 275-283.
[3]	XU Wanru, YANG Panlong. Mobile user propagation capability evaluation and coverage optimization algorithm [J]. Journal of University of Science and Technology of China, 2017, 47(7): 569-574.