计算机系统应用  2019, Vol. 28 Issue (1): 188-193 PDF

1. 福建师范大学 数学与信息学院, 福建 350117;
2. 福建师范大学 数字福建环境监测物联网实验室, 福建 350117

Defect Localization Method Based on Program Spectrum
CAI Rui1, ZHANG Shi1,2, YU Xiao-Fei1, JIANG Jian-Min1,2
1. School of Mathematics and Informatics, Fujian Normal University, Fujian 350117, China;
2. Digital Fujian Environmental Monitoring Network Laboratory, Fujian Normal University, Fujian 350117, China
Foundation item: National Natural Science Foundation of China (61772004); Open Fund of Shanghai Key Laboratory of Trustworthy Computing (07dz22304201401); Natural Science Foundation of Fujian Province (2018J01777)
Abstract: Software testing plays a vital role in producing reliable software. The debugging of software is divided into two steps: fault localization and fault modification, where the fault localization is the most time-consuming and tedious work. Generally, most of test cases in a test suite performed successfully. In order to improve the availability of the defect location method based on the program spectrum, the method should have the ability to adjust the weight of successful coverage automatically. That is, if the contribution of the number of statements to the suspiciousness is reduced gradually with the increase of the number of successful test cases, the effectiveness of fault localization method can be improved greatly. Based on this idea, this study proposes anEPStar (EP*) defect location method, which can effectively adjust the effect of successful use cases, so as to avoid the excessive influence of the number of successful use cases to the defect location effect. To improve the accuracy of error location, the experimental comparison shows that EP* method has higher defect location accuracy than several existing defect location methods.
Key words: EP* method     defect localization     program spectrum     test case     location effect

1 基于频谱的缺陷定位方法 1.1 基本概念

Reps 等人[17]首次提出程序谱概念, 后面的研究者们将程序频谱[1820]用于程序分析. 程序频谱主要是指程序执行过程中产生的关于程序语句的覆盖信息(被覆盖为1, 未覆盖为0), 以及执行是否通过信息.

Tep(s)的数值越大, 说明语句s执行且用例成功的次数多, s是缺陷语句的可能性越小; Tef(s)的数值越大, 说明语句s执行且用例错误的次数多, s是缺陷语句的可能性越大; Tnf(s)的数值越大, 则说明语句s没有被执行到的情况下错误越多, 这间接说明s是缺陷语句的可能性越小.

1.2 EP*的缺陷定位方法

Wong等人[14]总结的假设5–7说明了:可疑值与Tef(s)大小成正比, 与Tep(s)大小和Tnf(s)大小成反比, 可以设Kulczynski系数为1来表示Tef/(Tnf+Tep). 基于假设8对Tef设置更高的权重, 可以设置Kulczynski系数为2来表示2*Tef/(Tnf+Tep). 但Kulczynski系数在缺陷定位的准确性上不够. 考虑到这一点, Wong等人提出采用*系数, 取值范围从2~50增量为0.5. 提出D*方法, 通过实验验证该方法在缺陷定位上效果很好.

 $E{P^*}(s) = \frac{{T_{ef}^{}(s)}}{{{T_{nf}}(s) + {T_{ep}}{{(s)}^{\frac{1}{*}}}}}$ (1)
1.3 引例

2 实验

2.1 测试程序集

2.2 缺陷定位评测指标

 $Score = (1 - Rank({s_f})/n)*100\%$ (2)
3 实验分析

 图 1 基于Score值的缺陷定位效果对比图

4 结果与展望

 [1] Liu H, Wang WH, Zhang DF. A methodology for mapping and partitioning arbitrary n-dimensional nested loops into 2-dimensional VLSI arrays. Journal of Computer Science and Technology, 1993, 8(3): 221-232. DOI:10.1007/BF02939529 [2] Wen WZ, Li BX, Sun XB, et al. Technique of software fault localization based on hierarchical slicing spectrum. Journal of Software, 2013, 24(5): 977-992. DOI:10.3724/SP.J.1001.2013.04342 [3] Mao XG, Lei Y, Dai ZY, et al. Slice-based statistical fault localization. Journal of Systems and Software, 2014, 89: 51-62. DOI:10.1016/j.jss.2013.08.031 [4] Wong WE, Gao RZ, Li YH, et al. A survey on software fault localization. IEEE Transactions on Software Engineering, 2016, 42(8): 707-740. DOI:10.1109/TSE.2016.2521368 [5] Renieres M, Reiss SP. Fault localization with nearest neighbor queries. Proceedings of the 18th IEEE International Conference on Automated Software Engineering. Montreal, Quebec, Canada. 2003. 30–39. [6] Liu C, Yan XF, Fei L, et al. SOBER: Statistical model-based bug localization. ACM SIGSOFT Software Engineering Notes, 2005, 30(5): 286-295. DOI:10.1145/1095430 [7] Abreu R, Zoeteweij P, van Gemund AJC. On the accuracy of spectrum-based fault localization. Testing: Academic and Industrial Conference Practice and Research Techniques. Windsor, UK. 2007. 89–98. [8] Yu K, Lin MX. Advances in automatic fault localization techniques. Chinese Journal of Computers, 2011, 34(8): 1411-1422. DOI:10.3724/SP.J.1016.2011.01411 [9] Jones JA, Harrold MJ. Empirical evaluation of the Tarantula automatic fault-localization technique. Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering. Long Beach, CA, USA. 2005. 273–282. [10] Baudry B, Fleurey F, Le Traon Y. Improving test suites for efficient fault localization. Proceedings of the 28th International Conference on Software Engineering. Shanghai, China. 2006. 82–91. [11] Wen W, Li B, Sun X, et al. Program slicing spectrum-based software fault localization. In Proceedings of the 23rd International Conference on Software Engineering and Knowledge Engineering. Miami, FL, UAS. 2011. 213–218. [12] Gonzalez A. Automatic error detection techniques based on dynamic invariants[Master’s Thesis]. Delft City: Delft University of Technology, 2007. [13] Lourenço F, Lobo V, Bação F. Binary-Based similarity measures for categorical data and their application in self-organizing maps. In Proceedings of the JOCLAD,2004-XI Jornadas de Classificacao e Anlise de Dados. Lisbon. 2004. 1–18. [14] Wong WE, Debroy V, Gao RZ, et al. The DStar method for effective software fault localization. IEEE Transactions on Reliability, 2014, 63(1): 290-308. DOI:10.1109/TR.2013.2285319 [15] Wong WE, Qi Y, Zhao L, et al. Effective fault localization using code coverage. In: Proceedings of the 31sh Annual International Computer Software and Applications Conference. Beijing, China. 2007. 449–456. [16] Wong WE, Debroy V, Li YH, et al. Software fault localization using DStar (D*). Proceedings of the 6th IEEE International Conference on Software Security and Reliability. Gaithersburg, MD, USA. 2012. 21–30. [17] Reps T, Ball T, Das M, et al. The use of program profiling for software maintenance with applications to the year 2000 problem. Proceedings of the 6th European Software Engineering Conference Held Jointly with the 5th ACM SIGSOFT International Symposium on Foundations of Software Engineering. Zurich, Switzerland. 1997. 432–449. [18] Steimann F, Frenkel M, Abreu R. Threats to the validity and value of empirical assessments of the accuracy of coverage-based fault locators. Proceedings of 2013 International Symposium on Software Testing and Analysis. Lugano, Switzerland. 2013. 314–324. [19] Xie XY, Chen TY, Kuo FC, et al. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM Transactions on Software Engineering and Methodology (TOSEM), 2013, 22(4): 31. [20] Zhang YJ, Santelices R. Prioritized static slicing and its application to fault localization. Journal of Systems and Software, 2016, 114: 38-53. DOI:10.1016/j.jss.2015.10.052 [21] Yu YB, Jones J, Harrold MJ. An empirical study of the effects of test-suite reduction on fault localization. Proceedings of the ACM/IEEE 30th International Conference on Software Engineering. Leipzig, Germany. 2008. 201–210. [22] Do H, Elbaum S, Rothermel G. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering, 2005, 10(4): 405-435. DOI:10.1007/s10664-005-3861-2