Computer Science ›› 2018, Vol. 45 ›› Issue (9): 207-212.doi: 10.11896/j.issn.1002-137X.2018.09.034

• Software & Database Technology • Previous Articles     Next Articles

New Spectrum-based Fault Localization Method Combining HittingSet and Genetic Algorithm

ZHOU Ming-quan, JIANG Guo-hua   

  1. School of Computer Science and Technology,Nanjing University of Aeronautics & Astronautics,Nanjing 211100,China
  • Received:2017-08-18 Online:2018-09-20 Published:2018-10-10

Abstract: Fault localization is an important research topic in the process of software development.However,the number of faults in the actual software cannot be determined in advance.The available single fault localization technique is not convenient to be used,and the available multi-fault localization technique is of low locating efficiency.This paper studied and improved the multi-fault localization technique GAMFL,and proposed a new spectrum-based fault localization methoid combining hitting set and genetic algorithm(GAHIT).In this method,the basic block for localization is defined and used to replace statements to localize faults,narrowing the search range.In the process of constructing initial population,the method of solving the hitting sets of execution path of failure test cases is presented to optimize the generation of initial population,and a new method for calculating fitness function is also presented to improve the total efficiency of the algorithm.According to the results of genetic algorithm,the fault detecton strategy is presented to improve the accuracy of localizing faults in the optimal group.The experiment results show that the proposed method is effective in solving the problem of localizing programs with unknown number of faults,and has good performance when localizing faults in both single fault programs and multi-fault programs.

Key words: Fault localization, Genetic algorithm, Hitting set, Uncertainty of fault number

CLC Number: 

  • TP311
[1]LIU X,LIU Y,LI Z,et al.Fault Classification Oriented Spectrum Based Fault Localization[C]∥IEEE,Computer Software and Applications Conference.IEEE Computer Society,2017:256-261.
[2]GETZNER E,HOFER B,WOTAWA F.Improving Spectrum-Based Fault Localization for Spreadsheet Debugging[C]∥IEEE International Conference on Software Quality,Reliability and Security.IEEE,2017.
[3]CHEN X,JU X L,WEN W Z,et al.Review of dynamic fault localization approaches based on program spectrum[J].Journal of Software,2015,26(2):390-412.(in Chinese)
陈翔,鞠小林,文万志,等.基于程序频谱的动态缺陷定位方法研究[J].软件学报,2015,26(2):390-412.
[4]KIM J,PARK J,LEE E.A New Spectrum-based Fault Localization With the Technique of Test Case Optimization[J].Journal of Information Science & Engineering,2016,32(1):177-196.
[5]SHU T,YE T,DING Z,et al.Fault localization based on statement frequency[J].Information Sciences,2016,360(C):43-56.
[6]ZHANG X,WANG Z,ZHANG W,et al.Spectrum-Based Fault Localization Method with Test Case Reduction[C]∥IEEE,Computer Software and Applications Conference.IEEE Compu-ter Society,2015:548-549.
[7]ZHANG P,MAO X,LEI Y,et al.Fault localization based on dy-namic slicing via JSlice for Java programs[C]∥IEEE International Conference on Software Engineering and Service Science.IEEE,2014:565-568.
[8]GONG D,SU X,WANG T,et al.State dependency probabilistic model for fault localization[J].Information & Software Technology,2015,57(1):430-445.
[9]CAO H L,JIANG S J,JU X L,et al.Fault Localization Based on
Dynamic Slicing and Association Analysis[J].Chinese Journal of Computers,2015,38(11):2188-2202.(in Chinese)
曹鹤玲,姜淑娟,鞠小林,等.基于动态切片和关联分析的错误定位方法[J].计算机学报,2015,38(11):2188-2202.
[10]LAMRAOUI S M,NAKAJIMA S.A Formula-Based Approach for Automatic Fault Localization of Imperative Programs[M]∥Formal Methods and Software Engineering.Springer International Publishing,2014:88-98.
[11]WANG Z,FAN X Y,ZOU Y G,et al.Genetic algorithm based multiple faults localization technique[J].Journal of Software,2016,27(4):879-900.(in Chinese)
王赞,樊向宇,邹雨果,等.一种基于遗传算法的多缺陷定位方法[J].软件学报,2016,27(4):879-900.
[12]SOUZA H A,CHAIM M L,KON F.Spectrum-based Software Fault Localization:A Survey of Techniques,Advances,and Challenges[J].arXiv:1607.04347.
[13]MORENOCENTENO E,KARP R M.The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment[J].Operations Research,2013,61(2):453-468.
[14]KRAMER O.Genetic Algorithm Essentials[M].West Berlin and Heidelberg:Springer International Publishing,2017.
[15]ZENG R,ZANG R,DING L,et al.Fault Diagnosis of Diesel Engine Based on Genetic Algorithms and Dempster-Shafer Fusion Theory[C]∥Chinese Control And Decision Conference.IEEE,2017.
[1] YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[2] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[3] WU Shan-jie, WANG Xin. Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks [J]. Computer Science, 2021, 48(7): 308-315.
[4] ZHANG Hui. Fault Localization Technology Based on Program Mutation and Gaussian Mixture Model [J]. Computer Science, 2021, 48(6A): 572-574.
[5] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[6] WANG Jin-heng, SHAN Zhi-long, TAN Han-song, WANG Yu-lin. Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network [J]. Computer Science, 2021, 48(6): 338-342.
[7] ZUO Jian-kai, WU Jie-hong, CHEN Jia-tong, LIU Ze-yuan, LI Zhong-zhi. Study on Heterogeneous UAV Formation Defense and Evaluation Strategy [J]. Computer Science, 2021, 48(2): 55-63.
[8] GAO Shuai, XIA Liang-bin, SHENG Liang, DU Hong-liang, YUAN Yuan, HAN He-tong. Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm [J]. Computer Science, 2021, 48(11A): 166-169.
[9] ZHANG Hui. Multiple Fault Localization Method Based on Deep Convolutional Network [J]. Computer Science, 2021, 48(11A): 88-92.
[10] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[11] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[12] SUN Chang-ai, ZHANG Shou-feng, ZHU Wei-zhong. Mutation Based Fault Localization Technique for BPEL Programs [J]. Computer Science, 2021, 48(1): 301-307.
[13] JI Shun-hui, ZHANG Peng-cheng. Test Case Generation Approach for Data Flow Based on Dominance Relations [J]. Computer Science, 2020, 47(9): 40-46.
[14] DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
[15] LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!