Application of Mahalanobis-Taguchi Method and
0-1 Programming Method to Cost-Effective
Regression Testing
Hirohisa Aman∗ , Yuta Tanaka† , Takashi Nakano† , Hideto Ogasawara† and Minoru Kawahara∗∗ Center for Information Technology, Ehime University, Matsuyama, Japan 790–8577† Toshiba Corporation, Kawasaki, Japan 212–8585

Abstract—To enhance the cost effectiveness of regression testing, this paper proposes a method for prioritizing test cases.
In general, a test case can be evaluated from various different
points of view, therefore whether it is worth it to re-run should
be discussed using multi criteria. This paper shows that theMahalanobis-Taguchi (MT) method is a useful way to successfully
integrate different evaluations of a test case. Moreover, this paper
proposes to use the 0-1 programming method together with the
MT method in order to take into account not only the priorityof a test case but also its cost to run. The empirical study with
300 test cases for an industrial software system shows that the
combination of the MT method and the 0-1 programming method
is more cost-effective than other conventional methods.

I. I NTRODUCTION
A continuous release of quality products with enhanced
functionalities is required for business success in the software
industry. All of the software development organizations haveendeavored to maintain a high quality of their products. To findas many hidden faults as possible prior to a release, software
testings have been performed at various developmental phases[1], [2]. A system testing is one of crucial testing activities
since it is performed to check the target system’s successful
behavior involving their functionalities, and to be the final
check before a release. A thorough performance of a systemtest is desired for a successful new release. Moreover, test
engineers must test not only upgraded functionalities but
also other functionalities again because unexpected failures(regressions) might occur. That is to say, it is ideal to re-run
all test cases whenever their product is upgraded.
However, many organizations have also tackled challenges
other than quality assurance: reducing cost and shortening
the time it takes to release. Since a system testing by handrequires much cost and time, it is hard to re-run all test
cases (regression testing) at every upgrade because of realistic
restrictions on the budget, resources and the time it takes
to release. Thus, test engineers have to plan a cost-effective
regression testing under such limitations. One of useful ways
to increase the cost-effectiveness of regression testing is toprioritize test cases [3], [4], [5], [6], [7]. By assessing a test
case’s expectation to find a failure, we can preferentially selectpromising test cases for regression testing. While there havebeen some criteria to assess test cases from different points ofview regarding their properties, there is a risk of overlooking
regressions when we evaluate test cases by focusing only

on a specific criterion. To reduce such a risk, we apply the
Mahalanobis-Taguchi (MT) method [8] to reasonably combine
different assessments for a better prioritization in this paper.
Even if we have a good way to evaluate priorities of test
cases, we need to consider a reasonable way to select them aswell. While it is simple to select test cases in decreasing orderof priority, that is not optimal algorithm. Hence, we use the0-1 programming method together with the MT method for abetter regression testing in this paper.
The key contributions of this paper are: 1) to propose anapplication of the MT method to a better test case prioritization, and 2) to show the cost effectiveness of the combinationof the MT method and the 0-1 programming method for aregression testing of an industrial software system.
II. M AHALANOBIS -TAGUCHI M ETHOD -BASED T EST C ASE
P RIORITIZATION
A. Mahalanobis DistanceIn general, an object such as a test case can have somedifferent aspects. Thus, the features of an object can beobserved as a multi-dimensional vector, and we would decidea similarity between two different objects by using the distance
between them. For example, let us consider a two-dimensional
example shown in Fig.1, where we have two groups A and
B. Now, object X which is plotted at (4.00, 3.00) seems to
be closer to the center of group A than that of group B.
Such a distance is referred to as the Euclid distance: let
x = (x1 , . . . , xn )T and a = (a1 , . . . , an )T be n-dimensional
position vectors of object X and the center of group A,
respectively1 . The square of the Euclid distance between x
and a, dE (x, a), is obtained by the following equation.
dE (x, a) = (x − a)T (x − a) .

(1)

We can also compute dE (x, b) by replacing a with b in theabove equation. The Euclid distance is often used as a distancemetric, but not always appropriate for deciding which groupis closer to an object. In Fig.1, there is a significant difference
between groups in their dispersions of data. While the dataof group A is concentrated in a narrower region, the data ofgroup B is scattered wider. By considering those dispersions, itwould be more natural to classify object X into group B. There
1 Superscript T signifies the transposition of vector.

TABLE I
A N E XAMPLE OF T EST H ISTORY

12
Group
A
B

Center of Group B

y

9

Test
case
T1
T2
T3
T4
T5

6

3

Center of Group A

target (X)

V1
–
P
F
–
–

V2
–
–
–
P
–

V3
–
–
P
F
F

V4
–
–
–
–
–

Version
V5
V6
–
–
–
–
–
–
–
–
F
P

V7
–
–
–
P
–

V8
P
–
–
–
–

V9
–
–
–
–
–

0
0

4

8

12

x

Fig. 1. An example of two-dimensional data groups.

is another notion of distance considering data-dispersion, theMahalanobis distance. The square of the Mahalanobis distancedM (x, a) is computed by the following equation.
−1dM (x, a) = (x − a)T SA(x − a) ,(2)

where SA is the variance-covariance matrix of data belong to−1group A, and SA
is its inverse matrix. We can also obtain thesquare of the Mahalanobis distance from group B, dM (x, b),
by replacing a with b and SA with SB , respectively.
To give an intuitive interpretation, let us consider the case ofa single dimension: x = x and a = a, where non-bold-faced
symbols x and a are scalar. By specializing Eq.(2) to the caseof a single dimension, dM (x, a) is computed as follows.
dM (x, a) =(x − a)2
,
2
σA

(3)

2
where σAis the variance of the data in group A. In simplified
terms, the Mahalanobis distance is a normalized distancewhich is the Euclid distance divided by the dispersion of data.
Equation (2) is a generalized form of Eq.(3) to any dimension.
In Fig.1, we have x = (4.00, 3.00)T , a = (1.61, 0.71)T ,b = (7.81, 6.13)T ,[][]4.001 0.502
0.197 −0.005
−1
−1
SA =
, and SB =.
0.502 8.058−0.005 0.192

We can obtain dM (x, a) = 70.73 and dM (x, b) = 4.62, sodM (x, a) > dM (x, b): x is closer to b with the Mahalanobis
distance. Therefore, we can classify object X into group B in
Fig.1 when we adopt the Mahalanobis distance.
B. Mahalanobis-Taguchi Method
The Mahalanobis distance has been utilized in the statistical
discriminant analysis to decide the group which an object
X should be classified into. That notion can be applied toa quality control as well. Let us regard group A as the setof normal objects which are working properly. Then, we canassess the quality of an object X by using the distance fromthe center of A: if X is farther from group A, then X seems
to be abnormal, i.e., something wrong in terms of its feature,and it would be better to be reviewed, repaired or replaced
preferentially. The Mahalanobis distance of X from the centerof group A can be a measure of X’s degree of abnormality.
This is a fundamental idea of the Mahalanobis-Taguchi (MT)method [8].

C. Test Case Prioritization
The aim of this study is to single out test cases which
are likely to find failures (regressions). This kind of study iscategorized as “test case prioritization” for regression testing
and there have been many studies on it. Many of them arebased on source code analyses [3], [4], [5]. Indeed, it is apromising way to associate a test case with a source code, andwe can decide which test cases we should re-run after a sourcecode modification by tracing their associations. However, there
might be accidental associations causing unexpected failuresat another functionality whose source code has not beenchanged. Moreover, there are also cases where test engineers
are independent of programmers, and they may not get sufficient information in regard to the source code modifications[7]. Therefore, this paper studies a test case prioritization byfocusing only on the test history which consists of test caseIDs, versions of products and test results. This is not to saythat we omit the information on “which functionalities are
upgraded” at the current version. Of course, we should re-run
the test cases related to those upgraded functionalities, andwe naturally re-run test cases such that they failed at their lastruns as well. After those re-runs are completed, our test caseselection is started. Thus, under the condition that “all test
cases passed at their last runs,” we consider to run test cases
again as many as possible in order to find unexpected faults
which might be hidden in the system.
Table I is a simple example of test history which we canget. In this table, we have five test cases T1 , . . ., T5 and someof them were run for nine versions of the products V1 , . . ., V9 .
Labels “P” and “F” signify whether the corresponding test caserun was “pass” or “fail,” respectively; Label “–” denotes thecorresponding test case was not run at the version.
We have empirically used the following two criteria (metrics) to evaluate test cases—GLC and FR.
1) Gap between the Last run version and the Current
version (GLC):
GLC(T ) is the number of consecutive versions at whichtest case T was not run until the current version. For
example, GLC(T1 ) = 1 and GLC(T2 ) = 8 in Table I.
2) Failure Rate (FR):
FR(T ) is the failure rate of test case T . That is to say,
it is the number of versions failed by T , divided by the
number of versions at which T was run. For example,
FR(T3 ) = 1/2 and FR(T4 ) = 1/3 in Table I.
A test case having a greater GLC value has not been run for
more versions after its last run. Such a test case has a higher

risk of overlooking regressions. Under our condition “all test
cases passed at their last runs,” GLC= 0 is the least value tore-run, because it is already re-run at the current version.
A test case having a higher FR value has a better trackrecord for finding a failure in the past. Such a test case may testa part which is fault-prone in the product through maintenance,
and we might expect a higher ability to find a regression.
On both GLC and FR, zero means that the corresponding
test case has the least expectation in finding a failure. Thus,a (squared) Mahalanobis distance from 0 can be a measureof the test case’s worth to re-run in terms of each metric’s
aspect. Table II shows their metric values and squared Maha2
lanobis distances when their variances are σGLC
= 9.00 and
2
σFR = 0.0625. In Table II, two different metrics may provide
different evaluations for the same test case. Those differences
are expected results because we successfully observe a test
case from different points of view. Thus, a use of a single
metric causes a higher risk of overlooking regressions. To
reduce the risk, we propose to combine different metrics by
the MT method. That is to say, we consider the Mahalanobis
distance from 0 = (0, 0)T to be a combined evaluation of atest case. Table II also shows the combined evaluations in thecolumn annotated by “dGLC&FR ” where we computed thosevalues with the following variance-covariance matrix S:
[
]
[
]
9.00
−0.2250.122 0.440
S=, and S −1 =.
−0.225 0.0625
0.440 17.58
III. 0-1 P ROGRAMMING M ETHOD -BASED T EST C ASE
S ELECTION
A. Greedy Method
The simplest way to select test cases is to single out test
cases in decreasing order of evaluated value. This method is
intuitive and easy-to-implement. For example, we can selectfive test cases shown in Table II by focusing on the evaluation“dGLC&FR ” in the following order: T3 , T5 , T2 , T4 and T1 . Now
we remember the cost to run a test case. The cost required
to run different test cases is not always the same. Table III
presents examples of costs. Moreover, we usually have an
upper limit of effort which can go into our testing. Thus, wewould have to give up running all test cases according to ourlimitations. If our upper limit is 20, we may select T3 and T5
in decreasing order of evaluation: the total value is 22.09.
The above method is simple, and has been known as “greedy
method.” However, the greedy method cannot always provide
the optimal solution [9] in maximizing the total value. That
is to say, the greedy method would not be a proper way toensure a high cost-effectiveness in our regression testing.
B. 0-1 Programming Method
To get a higher expectation to find more failures, we aim
to maximize the total value under our limitation of cost.
This problem comes down to the “0-1 programming problem”
which is formalized as follows.

TABLE II
M ETRIC VALUES AND S QUARED M AHALANOBIS DISTANCES OF T ESTC ASES SHOWN IN TABLE I
Test case
T1
T2
T3
T4
T5

GLC
1
8
6
2
3

FR
0
0
1/2
1/3
2/3

dGLC
0.11
7.11
4.00
0.44
1.00

dFR
0.00
0.00
4.00
1.78
7.11

dGLC&FR
0.12
7.81
11.42
3.03
10.67

TABLE IIIA N E XAMPLE OF T EST C ASE E VALUATION AND C OST TO RUN
Test case
T1
T2
T3
T4
T5

Evaluation (dGLC&FR )
0.12
7.81
11.42
3.03
10.67

Cost
1
7
8
4
12

Given N test cases Ti (i = 1, . . . , N ). Let Pi and Ci be theevaluated value of Ti and the cost to run Ti , respectively. Then,
maximizesubject to

N
∑
i=1
N
∑

Pi x i ,(4)

Ci xi ≤ L, and xi ∈ { 0, 1 },

(5)

i=1

where xi = 1 means that we select Ti ; xi = 0 denotes that
we do not select Ti . L signifies the upper limit of total costwhich we can put into the regression testing.
2
For example, we can formulate the case shown in Table III
with L = 20 as follows.
maximize 0.12x1 + 7.81x2 + 11.42x3 + 3.03x4 + 10.67x5 ,subject to 1x1 + 7x2 + 8x3 + 4x4 + 12x5 ≤ 20,
and xi ∈ { 0, 1 }.
By solving this 0-1 programming problem, we obtain the optimal solution (x1 , x2 , x3 , x4 , x5 ) = (1, 1, 1, 1, 0) corresponding
to when we select T1 , T2 , T3 and T4 with the total value
as 22.38. Remember the total value by the greedy method
was 22.09: the 0-1 programming method can always provide
a solution which is the same as or superior to the greedy
method. We can easily solve such 0-1 programming problems
by using software tools such as lp solve2 .
In reality, we also have to consider associations between test
cases. That is to say, there may be a situation that: whenever
we run test case Ti , it would be better to run Tj as well.
Such an association can be considered by the simple inequality
constraint: xi ≤ xj . If xi = 1 then we have xj ≥ 1 under theconstraint. Since xj ∈ {0, 1}, it leads to xj = 1. Therefore, theabove inequality constraint represents “xi = 1 =⇒ xj = 1,”
so we have to select Tj whenever we select Ti .
2 http://lpsolve.sourceforge.net/5.5/

TABLE IV
M ETHODS USED IN T EST C ASE S ELECTION
Symbol
GLC-g
GLC-z
FR-g
FR-z
GLC-FR-g
GLC-FR-z

Evaluation Method
dGLC
dGLC
dFR
dFR
dGLC&FR
dGLC&FR

Selecting Method
greedy0-1 programing
greedy0-1 programing
greedy0-1 programing

TABLE VN UMBER OF R EGRESSION -F INDING T EST C ASES BY M ETHOD
Effort
60
90
120
150
180
210
240

GLC-g
20
20
20
20
20
20
20

GLC-z
20
20
20
20
20
20
20

FR-g
2
2
2
2
2
2
2

Method
FR-z
2
2
2
21
22
22
22

GLC-FR-g
2
22
22
22
22
22
22

GLC-FR-z
19
22
22
22
22
22
22

IV. E MPIRICAL S TUDY

B. Procedure
This empirical study is conducted in accordance with thefollowing procedure.
1) Collect metric (GLC and FR) values and costs to run
for all test cases. Let a test case’s cost to be the actual
man-minutes required for its last running.
2) Compute the evaluated values of test cases in terms of
GLC, FR and their combination.
3) Extract associations between test cases.
If test case Tj has always been run whenever Ti wasrun, the testing by Ti might be related with the one
by Tj . In the authors’ experience, sometimes both oftheir runnings would fail at the same subsequent version.
Therefore, in order to reduce the risk of overlooking a
regression, if we select Ti , then we also select Tj . To
exclude coincidental co-runs, we focus only on test casesthat have been run two or more times.
4) Compare six combinations of methods shown in Table
IV in terms of the number of failure-finding test cases
included, for 60, 90 120, 150, 180, 210 and 240 manminutes as the upper limits of effort—these limits correspond to about 10%, 15%, 20%, . . ., 45%. Use lp solve
version 5.5 as our 0-1 programming problem solver.
C. Results and Discussion
The variances and co-variance of metric values were22
σGLC
= 8.85, σFR= 0.021 and σGLC,FR = −0.21. Using

these parameters, we obtained values of each test case: dGLC ,dFR and dGLC&FR . Because of space limitations, we will omit
the table showing all of the evaluated values.
By checking a co-run of the test cases in the test history,
we found 30 associations between them: we will also omit

25

25

20

20

15

15
Regression

The aim of this study is to examine the combination of the
MT method and the 0-1 programming method in terms of thecost-effectiveness in the regression testing. Our experimental
objects are 300 test cases for an industrial software system
maintained by a certain company. We have the test history
on their 13 versions. In order to clearly discuss the costeffectiveness of the regression testing, we ran all test cases
for the current version: the total running cost was 539 manminutes, and 22 test cases found failures. The better test-caseselection method selects those 22 test cases with less effort.

the list of them due to limitations of space. We used those 30
associations during our test case selection as follows.
• In the greedy method, we select test cases in decreasingorder of their values. If “Ti associates with Tj ” and weselected Ti , then we also select Tj . We iterated such a
chained selection for all transitive relationships such that
if Ti associates with Tj and Tj associates with Tk thenwe select Tk as well.
• In the 0-1 programming method, we add the inequality
constraint corresponding to the association. If “Ti associates with Tj ,” we add constraint “xi ≤ xj ” to ourformulation. Notice that possible transitive associations
are also supported by satisfying all inequality constraints.
Table V shows the number of failure-finding test cases
included in the set of selected test cases. The method having
a larger number of those test cases with less effort is the morecost-effective method for regression testing. Notice that the
maximum number of the target test cases is 22.
We compare ways of evaluating test cases by focusing
only on the results by the greedy method (see Fig.2(a)) and(see Fig.2(b)) on the ones by the 0-1 programming method,respectively. For both of two methods, the best performanceswere made by “dGLC&FR ” except for the case of the least
effort 60 man-minutes. While GLC contributed to select 20of the target test cases with less effort, it failed to select theremaining two test cases and those two were picked up by
FR rather than GLC. In this study, GLC seems to be useful
to find failures but it misses some of them. On the other
hand, although FR is not good at quickly finding failures, it
recovers something missed by GLC. While they have different
advantages and disadvantages, we succeeded in combining

Regression

A. Aim and Experimental Objects

10

10
Method
GLC
FR
GLC&FR

50

Method
GLC
FR
GLC&FR

5

0
100

150
Effort(a) greedy

200

100

150
Effort200(b) 0-1 programming

Fig. 2. Results of the greedy method and the 0-1 programming methods.

them to produce a more useful evaluation method by using
the MT method.
We also compare the results from another perspective: “thegreedy method vs. the 0-1 programming method.” While they
did not show significant differences in Table V, the 0-1
programming method always gives the results at the same withor superior to the greedy method for all settings.
From these results, we conclude that the combination of
the MT method and the 0-1 programming method is useful inselecting test cases for a cost-effective regression testing.
D. Threats to Validity
Since the 0-1 programming problem is a NP-hard problem,
it may take much time to solve with an increase in the numberof test cases. However, we got the most solutions in less than
one second with an average personal computer3 . Although apart of the computation (FR-z with efforts of 180, 210 and240) required a timeout processing with 30 seconds threshold,those suboptimal solutions succeeded in finding all failures inreality. Therefore, their computational complexity would not
be a serious threat to validity in our empirical study.
While our empirical data consists of 300 test cases, we have
many more test cases and their test histories. Those 300 test
cases were selected from the past maintenance records without
any bias, i.e., we adopted them without any intention. Thus,
our data selection may not be a threat to validity.
V. R ELATED W ORK
Various studies on the test case prioritization for regression
testing [3], [4], [5] have been utilized the static code analysis
techniques and the repository mining techniques. Their approaches are based on an association between a test case anda source program. While such an association can be powerful
to decide which test cases should be re-run when a part of thesource file was changed, we tackle the test case prioritizationby using only test history which is easier to collect.
Fisher [10] focused on the 0-1 programming method tominimize the number of test cases for a regression testing.
It proposed to select the minimal set of test cases such thatthey retest all elements affected by their code changes. While
it is a significant previous work, our work focuses on a test
history rather than code change information.
Kim et al. [6] proposed a method by focusing only on thetest history. Their method computes a “selection probability”
of a test case as its priority by using the exponential weighted
moving average and the exponential smoothing. While thatmethod is a useful related work matching our situation, they
did not consider the testing cost. In this paper, we take into
account not only the test case’s priority but also its cost.
The literatures [11], [12] are our previous work. Although
they proposed to apply the 0-1 programming method on thetest case selection, they are based on a single metric. As
mentioned above, a use of a single metric may lead to ahigher risk of overlooking regressions. This paper proposes to
3 CPU: Intel Core i5, 3.2GHz; Memory: 16GB; OS: Linux 3.4.110

successfully combine two or more metrics by using the MT
method and to apply it with the 0-1 programming method.
VI. C ONCLUSION
We proposed to apply the Mahalanobis-Taguchi (MT)method into a test case prioritization in a regression testing.
Since a test case has some different aspects in general, we
expressed the feature of a test case as a multi-dimensional
vector, and computed the Mahalanobis distance of the test casefrom the special test case which has the least expectation tofind a failure. The computed distance can be an index of worth
to re-run the test case. Moreover, in order to consider not only
the priority of test cases but also the cost to run, we applied
the 0-1 programming method to our test case selection.
We conducted an empirical study with 300 test cases for 13
versions of an industrial software product, and examined thatthe combination of the MT method and the 0-1 programming
method shows the best performance of cost-effectiveness inregression testing. We can expect that the proposed method
contributes to a more cost-effective regression testing and amore efficient quality management of software products.
Our future work include: 1) to apply our method to manyother products from other domains to examine the generalityof its cost-effectiveness; 2) to compare with other methods inorder to discuss the superiority of our method.
ACKNOWLEDGMENT
The authors would like to thank the anonymous reviewers
for their helpful comments.
R EFERENCES[1] R. S. Pressman, Software Engineering: a practitioner’s approach, 6th ed.
Columbus, OH: McGraw-Hill, 2005.
[2] A. P. Mathur, Foundations of Software Testing. Delhi, India: Pearson
Education, 2008.
[3] D. Jeffrey and N. Gupta, “Test case prioritization using relevant slices,”in Proc. 30th Annual Int’l Computer Softw. and Appl. Conf., vol. 1, Sept.
2006, pp. 411–420.
[4] M. Sherriff, M. Lake, and L. Williams, “Prioritization of regression tests
using singular value decomposition with empirical change records,” inProc. 18th Int’l Symp. Softw. Reliab. Eng., Nov. 2007, pp. 81–90.
[5] S. Mirarab and L. Tahvildari, “A prioritization approach for software
test cases based on bayesian networks,” in Proc. 10th Int’l Conf.
Fundamental Approaches to Softw. Eng., Mar. 2007, pp. 276–290.
[6] J.-M. Kim and A. Porter, “A history-based test prioritization techniquefor regression testing in resource constrained environments,” in Proc.
24th Int’l Conf. Softw. Eng., May 2002, pp. 119–129.
[7] M. J. Arafeen and H. Do, “Test case prioritization using requirementsbased clustering,” in Proc. 6th Int’l Conf. Softw. Testing, Verification andValidation, Mar. 2013, pp. 312–321.
[8] G. Taguchi, S. Chowdhury, and Y. Wu, The Mahalanobis-Taguchi
System. New York, NY: McGraw-Hill, 2001.
[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction
to Algorithms. Cambridge, MA: MIT Press, 2009.
[10] K.F. Fischer, “A test case selection method for the validation of software
maintenance modifications,” in Proc. Int’l Computer Softw. and Appl.
Conf., Nov. 1977, pp. 421–426.
[11] H. Aman, M. Sasaki, K. Kureishi, and H. Ogasawara, “Application of
the 0-1 programming model for cost-effective regression test,” in Proc.
37th Int’l Computer Softw. and Appl. Conf., July 2013, pp. 721–722.
[12] H. Aman, M. Sasaki, T. Nakano, H. Ogasawara, T. Sasaki, and M. Kawahara, “An efficient regression testing based on test case clustering and 0-1
programming model,” J. Japan Society for Softw. Sc. & Tech., vol. 32,
no. 3, pp. 111–125, Aug. 2015 (in Japanese).