SCIENCE CHINA Information Sciences, Volume 60, Issue 9: 092112(2017) https://doi.org/10.1007/s11432-016-9057-8

Cost-effective testing based fault localization with distance based test-suite reduction

More info
  • ReceivedDec 30, 2016
  • AcceptedMar 29, 2017
  • PublishedJul 28, 2017


The aim of testing based fault localization (TBFL) involves improving the efficiency of program debugging by providing developers with a guide of ranked list of suspicious statements. However, collection of testing information of the whole original test-suite is excessively expensive or even infeasible for developers to conduct TBFL. Traditional test-suite reduction (TSR) techniques are utilized to reduce the size of test-suite. However, they entail a time-consuming process of whole testing information collection.In this study, the distance based test-suite reduction (DTSR) technique is proposed. As opposed to the whole testing information, the distances among the test cases are used to guide the process of test-suite reduction in DTSR. Hence, it is only necessary to collect the testing information for a portion of the test cases for TSR and TBFL. The investigation on the Siemens and SIR benchmarks reveals that DTSR can effectively reduce the size of the given test-suite as well as the time cost of TBFL. Additionally, the fault locating effectiveness of DTSR results is close to that when the whole test-suite is used.


This work was supported by National Natural Science Foundation of China (Grant Nos. 61673384, 61502497, 61562015), Guangxi Key Laboratory of Trusted Software (Grant Nos. kx201609, kx201532), Scientific Research Innovation Project for Graduate Students of Jiangsu Province (Grant No. KYLX_1390), Science and Technology Program of Xuzhou (Grant No. KC15SM051), and China Postdoctoral Science Foundation (Grant No. 2015M581887).

  • Figure 1

    (Color online) Framework of distance based test-suite reduction.

  • Figure 2

    Sliding a 3-width window to a list of coverage rates. (a) Contents are different; (b) contents are similar.

  • Figure 3

    ${\rm Relative}_{\rm cov}$ comparison on all subjects when using different distance measures. (a) Hamming; (b) Cartesian; (c) Manhattan; (d) Levenshtein; (e) CPM.

  • Figure 4

    ${\rm Relative}_{\rm par}$ comparison on all subjects when using different distance measures. (a) Hamming; (b) Cartesian; (c) Manhattan; (d) Levenshtein; (e) CPM.

  • Figure 5

    (Color online) TimeCost (s) of the fault localization when window width is 20.


    Algorithm 1 Distance based test-suite reduction

    Require:PG, TS, $t_{f1}$, ${\rm DisFunc}()$, ${\rm stop}\_{\rm cri}$;

    Output:${\rm TS}_{\rm reduced}$.

    // Phase 1: generate the distance matrix ${\rm m\_ dis}$.

    for $i=1$ to $n$

    for $j=i$ to $n$

    ${\rm m\_ dis}_{i,j}$ = ${\rm m\_ dis}_{j,i}$ = ${\rm DisFunc}(t_i, t_j)$;

    end for

    end for

    // Phase 2: reduce the original test-suite TS with a greedy algorithm.

    ${\rm TS}_{\rm reduced}$ = $t_{f1}$, ${\rm TS}_{\rm unreduced}$ = TS $- \{t_{f1}$;

    while ${\rm TS}_{\rm educed}$ cannot satisfy ${\rm stop}\_{\rm cri}$ do

    ${\rm dis}_{\rm max}$ = MIN_VALUE, $t_{\rm selected}$ = NULL;

    for all $t_u \in {\rm TS}_{\rm unreduced}$

    ${\rm dis}_{\rm min}$ = MAX_VALUE;

    for all $t_r \in {\rm TS}_{\rm reduced}$

    if ${\rm dis}_{\rm min} > {\rm m\_ dis}_{r,u}$ then

    ${\rm dis}_{\rm min} = {\rm m\_ dis}_{r,u}$;

    end if

    end for

    if ${\rm dis}_{\rm max} < {\rm dis}_{\rm min}$ then

    ${\rm dis}_{\rm max} = {\rm dis}_{\rm min},\,\, t_{\rm selected} = t_u$;

    end if

    end for

    ${\rm TS}_{\rm reduced} = {\rm TS}_{\rm reduced} \cup t_{\rm selected},\,\, {\rm TS}_{\rm reduced} = {\rm TS}_{\rm reduced} - t_{\rm selected}$;

    run PG with $t_{\rm selected}$ and collect the testing information;

    end while

    output ${\rm TS}_{\rm reduced}$.

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号