A method for automated test cases generation from sequence diagrams and object constraint language for concurrent programs

igure 8 represents UML sequence
V.T. Dao et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2017) 53–70 65
Fig. 8. The sequence diagram for Account Transfer in
Bank system.
diagram for account transfer functionality.
For the sake of brevity, the class diagram
(as shown in Fig. 9) shows only the specific
classes that are involved in that function.
Test scenarios generation: The proposed
algorithm traverses the CFG to generate test
scenarios (in Sect. 4). For concurrent system,
by using Algorithm 4 test scenarios would
be able to uncover some of the concurrency
issues. The account transfer functionality
identifies the quality of the test scenarios
generated by DFS, BFS and our method to
uncover the concurrency errors (Table 1).
Working of the test data generation
algorithm: consider the test scenario
described by T3= (Start-FN-M5-M6-M1-
M2-DN-M7-DN-M8-M3-M4-JN-End),
we illustrate test data generation for the
scenario T3. The predicates are shown on
their associated edges, and the constraints
and data type of variable are attached in
block node. The variables amount of money
being withdrawn of two account type are
x,y and the balance of account is balance.
All variables from class diagram are set
with integer domain. The initial domains
of input variables x,y and balance are:
Fig. 9. The class diagram and constraint OCL for
Account Transfer.
x,y:[50,50000] and balance:[100,65535]
(because balance ≥ 100 and balance is
integer variable).
Assume that the test path T3 with 2 loops,
our algorithm marks and encounters decision
node DN that traversed. If DN is 2, the
test path is: Start-M5-M6-M1-M2-DN-M7-
DN-M7-DN-M8-M3-M4-End The sub path
of M5-M6-M1-M2 introduces no change to
the input variables. To take the branch
from node DN to M7, the predicate y <
balance and y: [50,50000] and balance :
[100, 65535]. Therefore, domain of variables
indicate split point in the fourth case, and
splitPt = (right.top − le f t.bot) ∗ pt +
le f t.bot = (65535 − 50) ∗ 1/2 + 50 =
32792, so y : [50, 32792]; balance :
[32793, 65535]. Traverse block node M7,
withdraw(y) because the smallest amount of
money withdrawn is 50, so balance reduces
50, thus balance: [32743, 65485].
The next time through the loop, we have
the same predicate, domain of variables is
in the fourth case splitPt = (65485 −
50) ∗ 1/2 + 50 = 32767, thus y :
[50, 32767] and balance : [32768, 65535].
Get on traversing M7, withdraw(y) because
the smallest amount of money withdrawn is
50, so balance reduces 50, thus balance :
[32718, 65485].
66 V.T. Dao et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2017) 53–70
The final time through the loop, the branch
from DN to M8, that domains of variables are
in the fourth case and splitPt = (65485−50)∗
1/2 + 50 = 32767, because the predicate y ≥
balance, thus value of y is 32767 and domain
of balance is [32718, 32766]. Therefore, for
test scenario T3 reduced domain of test data
are: y = 32767;balance : [32718, 32766] and
x : [50, 50000].
6.3. Evaluation
In this section, we attempt to prove the
fault- detection capability of the test suite
generated using the proposed method.
6.3.1.Metrics
By using the mutation score (MS), we
measure the effectiveness of the proposed
method. The MS indicates the adequacy of
a test suite for the system under testing.
6.3.2.Experimental procedure
We used SequenceConcur tool to parse
the UML sequence diagram (in an XMI file)
and OCL for bank transaction. During the
transformation, all branches and concurrent
flows were represented as CFG. The tool
generated a set of test scenarios from the
graphs based on a given coverage criterion.
Test data are generated by using the
Algorithm in Sect. 5 (special in case of testing
loops), from which we selected only those
satisfying the generated test scenarios to be
in the test suite. As a result, we selected
20 test cases for each test scenario when
the improved strong coverage criterion was
used, four test scenarios were created in
our experiments.
Seeding faults: muJava [14] was used to
randomly seed faults into the Java program
for bank transaction. Using the muJava
system, 9 method-level and 5 class-level
operators were applicable for our study.
In these applicable operators, a total of
351 method-level and 26 class-level mutants
were generated.
Executing tests and collecting the results:
we next applied each test in the test suite to
both the original program and the mutants,
comparing with the outputs. If the output
was the same, then the current test passed;
otherwise, a fault was detected.
6.3.3.Results and analysis
Data safety error uncover capability: in
our case study, the messages m2 and m6 in
par fragment have shared data, and safety of
data is more important. Test scenarios are
generated by the algorithm that should be
able to uncover data safety errors. We use
and compare DFS, BFS and our algorithm
in generating the test scenarios (in Table 1)
from CFG.
DFS algorithm generates test scenarios
including test sequences that are not capable
of finding data safety errors because it does
not allow interleaving between the messages
of two operands in par fragments. The
test scenarios are generated by BFS and our
algorithm that are capable of finding data
safety errors. However, BFS algorithm does
not generate the test sequences in case of zero
iteration loop while our method uses with two
parts, false part and true part that means zero
and more than one iteration. Test data are also
considered to get on with 2, random n and
max, min loops.
Fault– detection capability: In order to
study the impact of the test suite size on
the effectiveness of the proposed method,
we varied the size to be 2, 10, 20 and
V.T. Dao et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2017) 53–70 67
Table 1. Test scenarios generated by DFS, BFS and our algorithm
and last column indicates data safety error uncover capability
Algorithm Test scenarios Error
uncover
capability
DFS
Start-FN-M1-M2-M3-M4-M5-M6-DN-M7-DN-M8-JN-End No
Start-FN-M5-M6-DN-M7-DN-M8-M1-M2-M3-M4-JN-End No
BFS
Start-FN-M1-M5-M2-M6-M3-DN-M7-DN-M4-M8-JN-End Yes
Start-FN-M5-M1-M6-M2-DN-M7-DN-M3-M8-M4-JN-End Yes
Our algorithm
Start-FN-M1-M5-M2-M3-M4-M6-DN-M7-DN-M8-JN-
End(T1)
Yes
Start-FN-M1-M5-M2-M3-M4-M6-DN-M8-JN-End(T2) Yes
Start-FN-M5-M6-M1-M2-DN-M7-DN-M8-M3-M4-JN-
End(T3)
Yes
Start-FN-M5-M6-M1-M2-DN-M8-M3-M4-JN-End(T4) Yes
Table 2. The MS results using the strong concurrency coverage criterion for each test scenario
Level Number of test
cases
Test
scenario 1
Test
scenario 2
Test
scenario 3
Test
scenario 4
Method-level
size = 2 51.2% 40.5% 45.7% 50.2%
size = 10/20/30 56.5% 55.7% 47.7% 60.4%
Class-level size = 2/10/20/30 74.5% 74.5% 81.5% 81.5%
30 test cases per scenario. We further
compare the fault- detection effectiveness of
the proposed method with that of random
testing, comparing their MS scores for the
same numbers of test cases.
Table 2 presents the MS results for
each test scenario, displayed according to
’Method-level’ and ’Class-level’. From the
table, we can observe the following:
(i) For both method-level and class-level
faults, the generated test scenarios show
a good fault-detection effectiveness. The
generated test case were able to detect more
than 40.5% of method-level faults and were
able to detect more than 74.5% of the class-
level faults.
(ii) the test suites are derived for different
test scenarios which have a different fault-
detection capability. Because the evaluation
results for different test suite sizes are the
same in case of 10, 20, 30 test cases per each
scenario for both method-level faults and
class-level faults, our method does not need a
large number of test cases for each scenario.
Table 3 presents the MS results of both our
method and the random method. From the
table, we can observe the following:
(i) for the same sizes, test suites generated by
our method achieve higher mutation scores
than those achieved by the random method,
with the differences being more prominent
when the size is small (with a size of two,
68 V.T. Dao et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2017) 53–70
Table 3. The mutation score MS results of our method and the random method
Our method Random Method
Number of test
cases
Level Total
mutants
Total
killed
mutants
MS Killed mutants MS
size = 2
Method-level 351 261 74.3% 139 39.6%
Class-level 26 26 100% 23 88.4%
Total 377 287 76.2% 162 42.9%
size = 10/20/30
Method-level 351 266 75.7% 153 43.5%
Class-level 26 26 100% 26 100%
Total 377 292 77.5% 179 47.4%
their MS are 76.2% and 42.9%, respectively).
(ii) regardless of test suite size, the test suites
generated by our method can detect 100%
class-level faults while it can detect only
88.4% by the random method.
The experimental results show that, the
test suite generated using our method can
detect more than 76% of seed faults with a
very small size of test suite (one test case
per scenario). Furthermore, more than 74%
of method-level faults and 100% of class-
level faults can be detected by the generated
test cases. For the same situations, our
method achieved a higher mutation score
than random testing. These results indicate
that the proposed method is both effective
and efficient.
7. Conclusions
The paper presented the automated
test data generation method based UML
sequence diagrams, class diagrams and OCL.
The method supports UML 2.0 sequence
diagrams including eight kinds of combined
fragments. The key idea of this method is to
generate all possible test scenarios in case of
exploring the message sequence with their
possible interleaving in par or seq fragments.
The test scenarios are generated to avoid
test explosion by selecting switch points.
Therefore, concurrency errors of systems can
be found. In addition, test data generation for
testing loop fragments in case of iterations 0,
1, 2, random n and max, min loops.
In some current approaches, test data are
generated in case of body of loop that is
only executed once. The method supports
different coverage criteria and can therefore
test concurrent processes effectively. Finally,
we have implemented the tool to support
the proposed method and conducted the
case study (bank transaction) to validate its
feasibility and effectiveness.
We are investigating to determine
infeasible or feasible test scenarios when
there have no input data for them to be
executed. We also are going to extend
the proposed method for other UML
diagrams (e.g., state-chart diagrams, activity
diagrams). Moreover, we would like to
further investigate and evaluate the fault-
detection effectiveness, and costs, of the
proposed concurrency coverage criteria.
V.T. Dao et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2017) 53–70 69
Algorithm 4 Generating the test scenarios to
improve the strong concurrency coverage
Input: Control-flow Graph G with initial
node in and final nodes are f ni
Output: T is a collection of test scenarios, t
is a test path
1: T = ∅; t = ∅;
2: curNode = in; //current node starts from in
3: repeat
4: move to next node;
5: if (curNode == BN) then
6: t.append(BN);
7: end if
8: if (curNode==DN and Branch is TRUE)
then
9: Append t with true part BN to MN;
10: else
11: Append t with false part BN to MN;
12: end if
13: if (curNode == FN) then
14: active all sub paths of FN;
15: repeat
16: Select random sub path;
17: Append t with node up to before or
after node having isAsyn //message
having isAsyn (true) is a switch point
18: until all sub paths are empty
19: end if
20: if (curNode == f ni) then
21: T = T + {t};
22: end if
23: until Graph end
Acknowledgments
This work is supported by the project
no. QG.16.31 granted by Vietnam National
University, Hanoi (VNU).
References
[1] M. Utting, B. Legeard, Practical Model-Based
Testing: A Tools Approach, Morgan Kaufmann
Publishers Inc., San Francisco, CA, USA, 2006.
[2] A. Nayak, D. Samanta, Automatic test data
synthesis using uml sequence diagrams, Journal
of Object Technology 9 (2) (2010) 115–144.
[3] M. Shirole, R. Kumar, Testing for concurrency
in uml diagrams, SIGSOFT Softw. Eng. Notes
37 (5) (2012) 1–8.
[4] M. Dhineshkumar, Galeebathullah, An approach
to generate test cases from sequence diagram,
in: Proceedings of the 2014 International
Conference on Intelligent Computing
Applications, ICICA ’14, IEEE Computer
Society, Washington, DC, USA, 2014, pp.
345–349.
[5] B.-L. Li, Z.-s. Li, L. Qing, Y.-H. Chen, Test case
automate generation from uml sequence diagram
and ocl expression, in: Proceedings of the
2007 International Conference on Computational
Intelligence and Security, CIS ’07, IEEE
Computer Society, Washington, DC, USA, 2007,
pp. 1048–1052.
[6] O. M. Group, The Unified Modeling Language
UML 2.0 Technical Report formal/06-04-04, The
Object Management Group (OMG), 2006.
[7] M. Khandai, A. Acharya, D. Mohapatra, A
novel approach of test case generation for
concurrent systems using uml sequence diagram,
in: Electronics Computer Technology (ICECT),
3rd International Conference, Vol. 1, 2011, pp.
157–161.
[8] C. ai Sun, Y. Zhao, L. Pan, X. He, D. Towey,
A transformation-based approach to testing
concurrent programs using uml activity
diagrams, Software: Practice and Experience.
[9] C. ai Sun, A transformation-based approach
to generating scenario-oriented test cases from
uml activity diagrams for concurrent applications
(2008) 160–167.
[10] S. C-A, W. G, C. K-Y, C. TY, Distribution-aware
mutation analysis, in: Proceedings of 9th IEEE
International Workshop on Software Cybernetics
(IWSC 2012), IEEE Computer Society, Izmir,
Turkey, 2012, pp. 170–175.
[11] A. JH, B. LC, L. Y, Is mutation an appropriate
tool for testing experiments, in: Proceedings of
the 27th International Conference on Software
Engineering (ICSE 2005), IEEE Computer
Society, St. Louis, Missouri, 2005, pp. 402–411.
[12] H. Minh Duong, L. Khanh Trinh, P. N.
Hung, An assume-guarantee model checker for
70 V.T. Dao et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2017) 53–70
component-based systems, in: The 10th IEEE-
RIVF International Conference on Computing
and Communication Technologies, 2013, pp. 22–
26.
[13] T. D. Vu, P. N. Hung, V. H. Nguyen, A
Method for Automated Test Data Generation
from Sequence Diagrams and Object Constraint
Language, in: Proceedings of the Sixth
International Symposium on Information and
Communication Technology, ACM, Hue City,
Viet Nam, 2015, pp. 335–341.
[14] M. YS, O. J, K. YR, Mujava: an automated class
mutation system, Software Testing, Verification
and Reliability 15 (2) (2005) 97–133.