一种基于频谱信息并结合碰集和遗传算法的缺陷定位方法

doi:10.11896／j.issn.1002-137X.2018.09.034

摘要/Abstract

摘要： 在软件研制过程中,缺陷定位是一个重要的研究课题。但是,实际软件中的缺陷数量无法被预先判定,且已有的单缺陷定位方法不易使用,已有的多缺陷定位方法存在定位效率不高的问题。基于此,文中对多缺陷定位方法GAMFL进行了研究和改进,提出了基于频谱信息并结合碰集和遗传算法的缺陷定位方法GAHIT。该方法定义了定位基本块,并用其替代语句进行缺陷定位,缩小了搜索范围;在初始种群的构造过程中,提出了采用求解失败用例执行路径碰集的方法,优化了初始种群的生成,并给出了新的适应度函数的计算方法,提高了算法的整体执行效率;最后针对遗传算法的结果,给出了缺陷检查策略,提高了在最优种群中查找缺陷的准确性。实验结果表明,所提方法能够有效处理缺陷数量未知情况下的定位问题,在单缺陷和多缺陷程序中都有较好的定位效果。

关键词: 碰集, 缺陷定位, 缺陷数量未知, 遗传算法

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

中图分类号:

TP311

周明泉, 江国华. 一种基于频谱信息并结合碰集和遗传算法的缺陷定位方法[J]. 计算机科学, 2018, 45(9): 207-212. https://doi.org/10.11896／j.issn.1002-137X.2018.09.034

ZHOU Ming-quan, JIANG Guo-hua. New Spectrum-based Fault Localization Method Combining HittingSet and Genetic Algorithm[J]. Computer Science, 2018, 45(9): 207-212. https://doi.org/10.11896／j.issn.1002-137X.2018.09.034

参考文献

[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.

相关文章 15

[1]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[3]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[4]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[5]	王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[6]	左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[7]	常建明, 薄莉莉, 孙小兵. 面向缺陷定位的代码搜索引擎 Code Search Engine for Bug Localization 计算机科学, 2021, 48(12): 140-148. https://doi.org/10.11896/jsjkx.201100209
[8]	高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057
[9]	姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[10]	高基旭, 王珺. 一种基于遗传算法的多边缘协同计算卸载方案 Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm 计算机科学, 2021, 48(1): 72-80. https://doi.org/10.11896/jsjkx.200800088
[11]	吉顺慧, 张鹏程. 基于支配关系的数据流测试用例生成方法 Test Case Generation Approach for Data Flow Based on Dominance Relations 计算机科学, 2020, 47(9): 40-46. https://doi.org/10.11896/jsjkx.200700021
[12]	董明刚, 黄宇扬, 敬超. 基于遗传实例和特征选择的K近邻训练集优化方法 K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection 计算机科学, 2020, 47(8): 178-184. https://doi.org/10.11896/jsjkx.190700089
[13]	梁正友, 何景琳, 孙宇. 一种用于微表情自动识别的三维卷积神经网络进化方法 Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition 计算机科学, 2020, 47(8): 227-232. https://doi.org/10.11896/jsjkx.190700009
[14]	杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[15]	包振山, 郭俊南, 谢源, 张文博. 基于LSTM-GA的股票价格涨跌预测模型 Model for Stock Price Trend Prediction Based on LSTM and GA 计算机科学, 2020, 47(6A): 467-473. https://doi.org/10.11896/JsJkx.190900128

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed