Optimal test sequence generation in state based testing using moth flame optimization algorithm

Abstract

Software testing contributes a strategic role in software development, as it underrates the cost of software development. Software testing can be categorized as: testing via code or white box testing, testing via specification or black box and testing via UML models. To minimize the issues associated with object-oriented software testing, testing via UML models is used. It is a procedure which derives test paths from a Unified Modelling Language (UML) model which describes the functional aspects of Software Under Test (SUT). Thus, test cases have been produced in the design phase itself, which then reduces the corresponding cost and effort of software development. This early discovery of faults makes the life of software developer much easier. Also, there is a strong need to optimize the generated test cases. The main goal of optimization is to spawn reduced and unique test cases. To accomplish the same, in this research, a nature-inspired meta-heuristic, Moth Flame Optimization Algorithm has been offered for model based testing of software based on object orientation. Also, the generated test cases have been compared with already explored meta-heuristics, namely, Firefly Algorithm and Ant Colony Optimization Algorithm. The outcomes infer that for large object-oriented software application, Moth Flame Optimization Algorithm creates optimized test cases as equated to other algorithms.

Keywords

Ant Colony Optimization cuckoo search algorithm firefly algorithm genetic algorithm moth flame algorithm meta-heuristics object-oriented state transition diagram

1 Introduction

Testing of software is the vital activity in the development of software life cycle. For the successful implementation of any software, it should be tested efficiently [1]. Moreover, about 50% of development cost inculcates the cost of software testing [2]. Also, for the development of good quality software, various software design paradigms have been used. Object-oriented is one of the software design paradigm that has been used widely in literature due to its numerous advantages [3, 4]. Researchers in their work [5, 6] emphasize the advantages of using object-oriented paradigm over other designparadigms.

However, the powerful features of object-orientation impose various risks and challenges to software testing [7]. In object-oriented system, due to encapsulation, state of object may not be observable and controllable from outside [7], which in turn increases the complexity of the testing activity. Here, in object-oriented system, complexity of testing has moved from within the code module to interface between them, which makes the integration testing an expensive activity [8]. Kung et al. [9] categorized these problems as: a) understanding problem, b) complex inter-dependency problem, c) testing problem due to object state behavior, and d) problem due to support of particular tool.

Because of the above stated problems, optimization and efficient test case generation of object-oriented software is needed critically. Numerous techniques have been used in the literature for the same [10 –14]. Xin-She-Yang compared the optimization problem to the process of treasure hunting [15] and suggested the concept of random walk which is the main feature of modern search algorithms. Thus, evolutionary meta-heuristics design the efficient optimization algorithms by the constant improvement of search agents on the basis of fitness function [15]. Empirical studies [16 –19] also suggested that optimization via nature-inspired meta-heuristics produce better results than the traditional optimization techniques. Also, irrespective of the generation of software test cases in the development phase, it is better to find the test cases in the software modelling phase itself. It will save both the cost and time of software testing process. This evolves the concept of model based testing. Hence, this model based testing extracts even those faults that are very difficult to extract via code based testing[20 –22].

As, the information regarding the software system is disbursed among several views, it is a very thought provoking process to analyze Unified Modelling Language (UML) models. A state chart diagram is one such model which provides the states that a particular object can attain in the whole program execution and also the transitions among those states.

Thus, in this paper, optimal test paths have been generated by using state transition diagram integrated with our proposed Moth Flame Optimization alg-orithm (MFO) [23]. MFO algorithm has already been applied in variety of areas [19 , 25]. Here, we are proposing it for creation of test paths. After that, the spawned test paths have been compared with other nature-inspired heuristics: 1) Firefly Algorithm (FA), and 2) Ant Colony Optimization Algorithm (ACO). This paper is arranged as follows:

Section 2 gives the background effort done in the area related to model based object-oriented testing using evolutionary algorithms. Section 3 discusses the nature-inspired meta-heuristics and object-oriented benchmarks selected in this study. Section 4 communicates the proposed MFO algorithm along with its flowchart. Section 5 provides the experimental evolution of MFO on the selected benchmarks. In Section 6 a comparison has been drawn among already existing and our proposed meta-heuristics. This article ends with Section 7, which concludes this analysis.

2 Background work

In this segment, a study of numerous research articles associated to optimization of object-oriented testing via model based testing and integrated with nature-inspired algorithms has been provided.

S.K Swain et al. [26] integrated state and activity diagrams to generate an intermediate diagram named as state-activity diagram (SAD). They proposed an algorithm for the production of test cases from activity and state transition diagram. Their approach provides a stronger level testing in which object interactions are also captured. However, they do not employ the use of nature-inspired evolutionary algorithms in their work.

A. Bouchachia et al. [27] applied Genetic Algorithm (GA) and ACO for the testing of object-oriented software articulated via finite state machine. P.R. Srivastava et al. [28] applied Cuckoo Search Algorithm (CS) for the generation of optimal test paths in testing based on state diagram. They found that CS algorithm provides better test paths than GA and ACO. H. Li and C.P. Lam [29] used ACO algorithm for automatic test case generation of state based software testing. P.R. Srivastava [30] proposed and applied ACO for the automated and complete handling of all the state transitions of the software.

M. Shirole et al. [31] used an extended flow graph. They projected framework based on GA to produce test cases integrated with state diagram. They concluded that their approach provided the improved results. P.R. Srivastava et al. [32] applied CS and Tabu Search (CSTS) algorithm for the automated generation of test cases. Their experimental results conclude that optimal test cases have been generated from their approach which are more effective than previously used meta-heuristics like GA, ACO and Ant Bee Colony (ABC) algorithm. S.S.B. Lam et al. [33] applied ABC algorithm depending upon edge coverage criteria. They then compared the ABC algorithm with Tabu search, ACO and GA. Result shows that ABC algorithm outperforms these algorithms.

S. Sabharwal et al. [34] suggested a technique, inferred from state and activity diagrams using GA. McMinn and Holcombe [35] explored evolutionary testing of state based programs. They proposed an extended chaining approach in which the problem related with internal variables is solved using hybridization. Wappler and Lammermann [12] proposed an evolutionary algorithm to accomplish the white box testing of object-oriented systems. Tonellea [36] applied GA to generate test cases for unit testing of classes. Doungsa-ard et al. [37] projected an enhanced GA for test case generation from state transition diagram. Chen and Zhong [38] applied the technique of multi-population genetic algorithm to create automated test sequences.

The above literature survey communicates the application of nature-inspired algorithms in the state based testing of SUT. However, each of the above algorithms have certain advantages and disadvantages associated with it. The major findings from the literature survey are as follows:

ACO generates repeated plus redundant test sequences and also it may stuck at native optima.

Convergence frequency of GA is very sluggish and it also may get stuck at local optima.

TS has complications in the quantity of memory needed to avoid getting trapped in native optima.

ABC works well only for small sized software.

Thus, irrespective of the extensive research in this field, efficient creation of test paths is still a vulnerable field of study. Here, in this article we offered a new meta-heuristic algorithm, Moth Flame Optimization algorithm to produce optimized and non-redundant test cases.

3 Methodology used

This section comprises of various nature-inspired techniques used in this paper to create test paths for software applications developed by object-orientation. After that, an overview of the selected object-oriented benchmarks has been provided.

3.1 Techniques used

Nature-inspired meta-heuristics have been exploited a lot in approximately past ten years. As we had already discussed in section 2 that previously used meta-heuristics do have certain limitations. Hence, to provide a better solution, we are proposing a new meta-heuristics i.e. Moth Flame Optimization Algorithm. Background concepts of this algorithm will be discussed next.

3.1.1 Moth flame optimization algorithm (MFO)

MFO was primarily given by S. Mirjalili [23]. This is grounded on the ordinary direction finding method of moths in the sky. The basic rules of MFO algorithm are as follows:

Moths fly in night by following a static angle from moon. This is termed as transverse gesture of moths.

However, these moths got misguided by the artificial lights and get trapped in spiral motion around the light.

MFO algorithm basically models this spiral motion of moths toward artificial light.

Thus, a logarithmic spiral is proposed in [23] as follows: $SP (M_{p}, F_{q}) = D_{p} \times e^{bt} \times cos (2 π t) + Fq$ (1)

Where, D_p denotes the distance of p^th moth from q^th, b defines the shape of the spiral and it is a fixed value, t is an arbitrary number in range [−1, 1].

Flames change their sequence according to the best solution in each repetition. Moths, thus modernize their position as per the flame during optimization. Following formula is used in [23] to update the flame no as: $Updated Flame number = round (P - p \times (P - 1) \div I))$ (2)

Where, P is the extreme number of flames, p denotes the present iteration number and I shows total number of iterations.

Here in this paper, we are comparing our proposed algorithm with other nature-inspired meta-heuristics. These algorithms will also be discussed in the next sub-section to gain some insights about these.

3.1.2 Firefly algorithm (FA)

FA was originally proposed by Xin-She-Yang [39] at Cambridge University. This algorithm is built on the blinking pattern of fireflies and follows below mentioned rules:

Individual firefly will be fascinated to other regardless of its gender i.e. they are unisex.

Only consideration for attraction is based on the brightness/flashing behavior of firefly. Thus, they will be fascinated towards brighter firefly. If, no more brighter firefly is found, then it will move arbitrarily.

Also, one firefly always gets attracted towards the brightest one and if, no such firefly exists, then firefly moves randomly. Intensity of illumination of firefly decreases with distance. This can be expressed as:

{xi}^{t + 1} = x_{t} + a \exp - γ_{ij}^{r 2} (x_{j}^{t} - x_{i}^{t}) + a_{t} €_{i}^{t} [39]

(3)where € is a vector of arbitrary numbers resulting from a gaussian distribution at time t, r is the distance between two fireflies, α is the brightness at r = 0, the second term is because of the attraction of fireflies, and the last term is due to the randomized association of fireflies with respect to time t.

Also, if α= 0, then fireflies just move randomly. Randomness thus depends on γ, which is called as absorption coefficient.

This brightness factor of firefly can be modelled via an objective function.

Lastly, as the distance between two fireflies increases, brightness reduces accordingly. This variation can be formulated as:

β = a exp - γ r^{2}

(4)

Where, β is the degree of brightness, α is the brightness when r = 0 (r is the space amid two fireflies) and γ is the light absorption factor.

3.1.3 Ant Colony Optimization (ACO)

ACO was anticipated by M. Dorigo [40]. This algorithm considers the behavior of ant colonies and is modelled as per the below rules:

Pheromones are left by each moving ant on the ground.

When another ant comes, it senses the pheromone of previous ant, also leaving behind its own pheromone, which increases the pheromone significance of the path in consideration.

Thus, every time, a particular path gets highest chance of to be followed upon.

These factors are implemented by Dorigo [40] in the below mentioned way:

1. Construction of the Ant Solution

Probability of movement of an ant from track a to b is: $P_{ab} = ζ_{ab}^{α} {. η}_{ab}^{β} / \sum ζ_{ab}^{α} {. η}_{ab}^{β} [41]$ (5)

Where, ζ_ab is the quantity of pheromone on edge (ab), α is the constraint that controls the impact of ζ_ab, η_ab is the desirability of edge (ab), and β is the constraint controls the impact of η_ab.

2. Updation of Pheromone

Every time a random ant comes, it follows the pheromone of previous ant and also updates the same with her own pheromone in the following manner: $ζ_{i, j} = (1 - φ) . ζ_{i, j} + φ . ζ_{0}$ (6)

Where, φε (0,1] is the deterioration coefficient of pheromone and ζ₀ is the opening value of the pheromone.

3.2 Object-oriented software used

In this sub-section, description of Software under Test (SUT) used in this study has been provided. Since, we are concerned about the isolated class, we are projecting our focus towards the applications having single class but a variety of intermediate states. Transition from one state to another helps us in deriving the test cases for that particular class. Following SUT’s has been used in this study:

Bengali Braille to Text Translator [42]

Microwave Oven [43]

ATM Transaction [43]

a. Bengali Braille to Text Translator

M. Kamal [42] in his work developed an objectoriented application for Bengali Braille to Text Translator. Braille is a specialized system of writing for visually impaired people. This application accepts the scanned image of braille and converts/translates it to text via pattern recognition. After that, subsequent text correction techniques have been applied to produce the final output.

b. Microwave Oven

Shlaer [43] in his research developed a state transition diagram for microwave oven. Oven can be in a waiting state or in an operating state. Also, it may be enabled or disabled depending upon the scenario.

c. ATM Transaction

This state transition diagram models one transaction of an ATM system. During a single transaction, ATM can be in idle, waiting or in processing stage.

4 Proposed moth flame optimization algorithm

This section discusses the proposed MFO algorithm integrated with state transition diagram for the optimization of object-oriented software testing. Here, we are proposing it for an object-oriented application. The steps included in this algorithm have been elaborated as:

4.1 Generation of state transition diagram

The very first step of our algorithm is to generate State transition diagram (STD) of the selected SUT’s. STD shows the dynamic flow of control from one state to another. Consider the example of very basic stack class. Its corresponding STD is given in Fig. 1.

Fig. 1

State Transition Diagram of Stack Class.

4.2 Conversion of STD into corresponding state graph (SG)

Every state of the STD developed in previous step is mapped to a node in the corresponding SG. Also, each and every transition of the STD is mapped to an edge in SG. State graph of the stack class from the STD developed in Fig. 1 is given in Fig. 2.

Fig. 2

State Graph of Stack Class.

4.3 Generation of adjacency matrix from SG

In this step, an adjacency matrix of the previously developed SG is created. This adjacency matrix now represents the matrix of moths. These moths are the search agents and they search for their best position in the space. For our example stack class, generated adjacency matrix is: $(\begin{matrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})$

4.4 Computation of fitness function for moths

As discussed in Section 3.1.1, Flames represents the best obtained position of moths. Thus, moths keep on searching and update every time a better result is found.

Aimed at this, a fitness function need to be developed. Here, we are proposing the fitness function on the basis of total number of nodes and probability of movement of moth from one position to another. $\begin{matrix} F (x) = (Probablity (x) X Node Number X Dfinal) / \\ (Total Number of Nodes) \end{matrix}$ (7)

Where, x represents the current node and $\begin{matrix} = (End Node Number - Current Node Number) \end{matrix}$ (8)

From First node, there exists two positions, i.e. at node 2 and 4. Hence, probability will be 0.5. Similarly probability of all the nodes will be calculated and then corresponding fitness values will be calculated as: $\begin{matrix} F (1) = (0.5 \times 1 \times 4) / 5 = 0.4 \\ F (2) = (0.33 \times 2 \times 3) / 5 = 0.396 \\ F (3) = (0.33 \times 3 \times 2) / 5 = 0.396 \\ F (4) = (1 \times 4 \times 1) / 5 = 0.8 \\ F (5) = 1000 \end{matrix}$

For node 5, since it is the end node of state diagram, so a large value is assigned to it. This is called end node affinity [44].

4.5 Generation of motion matrix

In this step, a motion matrix has been created based on the fitness values calculated above. A software named “Optimal path calculator via MFO” has been developed to achieve the same. The input of this tool is the previously generated adjacency matrix. For our sample example of stack class, motion matrix generated will be: $(\begin{matrix} 0 & 0.396 & 0 & 0.8 & 0 \\ 0.4 & 0.396 & 0.396 & 0 & 0 \\ 0 & 0.396 & 0 & 0.8 & 1000 \\ 0 & 0 & 0 & 0 & 1000 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})$

4.6 Computation of test paths based on the spiral motion of moths

As discussed in Equation 1, path from each moth/node is calculated. The paths will be calculated as follows:

For Node 1

From Node 1, two paths exists: 1 – >2 and 1 – >4

a. 1 – > 2 (Here p = 1 and q = 2) Following Equation 1, D = (2-1 = 1), parameter b which determines the shape of spiral, we consider it as (-1.28) [44] and t is taken to be 1. Also Fq computed in step 4.4 is 0.396. Substituting these values in Equation 1. Value of this motion comes out to be 0.6971.

b. 1 – > 4 Succeeding the above points, the value of this motion comes out to be 1.7033. Since value of path (1 – >2) < (1 – >4) i.e. For further motion, node in consideration will be node 2.

For Node 2

From Node 2, three paths exists: 2 - >1, 2 - >2 and 2 - >3. Their respective values of spiral motion are 0.7011, 0.396 and 0.6971. Hence path 2 - >2 will be selected. Following the same procedure, next path to be selected will be 2 - >3. So, the current node is now node 3.

For Node 3

From Node 3, paths are: 3 - >2, 3 - >4 and 3 - >5 with values 0.6971, 1.1011 and 1000.6022 respectively. Hence path 3 - >2 will beselected.

The path remaining from node 2 is 2 - >1, as other two has already been selected.

Now from node 1, path selected will be 1 - >4 and finally 4 - >5.

Since, we had reached the end node, so first test path observed will be: $1 - > 2 - > 2 - > 3 - > 2 - > 1 - > 4 - > 5$

Now, this is the best solution obtained in first iteration, after that as per the Equation 2, number of flames need to be updated. This process will be discussed as: P = number of nodes (in this example, 5); p is the iteration number, so here it will be 2; I, shows the maximum number of iterations, we took it as 10). So the value comes outto be $\begin{matrix} Updated Flame Number \\ = round (5 - 2 \times (5 - 1) \div 10)) = 4 \end{matrix}$ (9)

Since all paths from node 4 has already been covered, we skip this and update the flame number again (now p changes to 3) again value will be 4. In the next iteration (when p is 4), updated value comes out to be 3. So the current node now becomes 3 and path from it 3 - >4 will be chosen. Again no further path from node 4, so again flame number will be updated (p = 5) and the node number comes out to be 3, so the final path i.e. 3 - >5 will be selected. Continue this process for all the 10 iterations. So, finally we have the following three paths generated from MFO: $\begin{matrix} a . 1 - > 2 - > 2 - > 3 - > 2 - > 1 - > 4 - > 5, \\ b . 3 - > 4 and, \\ c . 3 - > 5 . \end{matrix}$

4.7 Generation of independent test paths

Paths obtained in previous step have been combined to obtain the independent paths as: $\begin{matrix} 1 - > 2 - > 2 - > 3 - > 2 - > 1 - > 4 - > 5, \\ 1 - > 2 - > 2 - > 3 - > 4 - > 5 and, \\ 1 - > 2 - > 2 - > 3 - > 5 . \end{matrix}$

The proposed algorithm has been summarized in the Fig. 3.

Fig. 3

Flowchart of Proposed MFA.

5 Experimental evaluation of moth flame optimization algorithm via benchmarks

This section generates the test cases using proposed MFO algorithm integrated with state transition diagram. Figures 4, 5 and 7 shows the STD’s for all the three benchmarks and their corresponding SG’s are given in Figs. 6, 8 and 9.

Fig. 4

State Transition Diagram of Bengali Braille To Text Translator.

Fig. 5

State Transition Diagram of Microwave Oven.

Fig. 6

State Graph f Bengali Braille To Text Translator.

Fig. 7

State Transition Diagram of ATM Transaction.

Fig. 8

State Graph of Microwave Oven.

Fig. 9

State Graph of ATM Transaction.

The adjacency matrices of all the SG’s are given as A, B and C respectively, which are givenbelow:-

\begin{matrix} A = (\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}) \\ (\begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}) \end{matrix}

B = (\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix})

C = (\begin{matrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix})

Table 4

Generated test paths via firefly algorithm

Ist Benchmark
Ist Path	(S1,S11,S17)
IInd Path	(S1,S2,S3,S4,S15,S16,S5,S17)
IIIrd Path	(S1,S2,S3,S4,S12,S13,S14,S4,S5,S17)
IVth Path	(S1,S2,S3,S6,S10,S3,S4,S15,S16,S5,S17)
Vth Path	(S1,S2,S3,S6,S7,S3,S4,S15,S16,S5,S17)
VIth Path	(S1,S2,S3,S6,S8,S3,S4,S15,S16,S5,S17)
VIIth Path	(S1,S2,S3,S6,S9,S3,S4,S15,S16,S5,S17)
VIIIth Path	(S1,S2,S3,S6,S10,S3,S4,S15,S16,S5,S17)
IInd Benchmark
Ist Path	(S1,S2,S4,S5,S7,S8,S9,S10)
IInd Path	(S1,S2,S3,S5,S6,S7,S8,S9,S10)
IIIrd Path	(S1,S2,S3,S4,S3,S5,S6,S7,S8,S9,S10)
IVth Path	(S1,S2,S4,S5,S7,S8,S6,S7,S8,S9,S10)
IIIrd Benchmark
Ist Path	(S1,S4,S5,S6,S5,S9,S8,S4,S7,S8,S18)
IInd Path	(S1,S2,S8,S18)
IIIrd Path	(S1,S4,S5,S6,S12,S11,S8,S18)
IVth Path	(S1,S4,S5,S6,S10,S13,S16,S15,S14,S11,S8, S18)
Vth Path	(S1,S4,S5,S6,S3,S2,S8,S18)
VIth Path	(S1,S4,S5,S6,S10,S13,S16,S3,S2,S8,S18)
VIIth Path	(S1,S4,S5,S6,S10,S13,S16,S15,S14,S10, S13,S16,S3,S2,S8,S18)

From the adjacency matrix and following the process proposed in Section 4, test paths will be generated and are given in Table 1, 2 and 3.

Table 1

Test paths for first benchmark using MFO

Ist Benchmark
Ist Path	(S1,S2,S3,S4,S5,S17)
IInd Path	(S1,S2,S3,S4,S12,S13,S14,S4,S15,S16,S5,S17)
IIIrd Path	(S1,S11,S17)
IVth Path	(S1,S2,S3,S6,S9,S3,S6,S7,S3,S4,S5,S17)
Vth Path	(S1,S2,S3,S6,S8,S3,S4,S5,S17)
VIth Path	(S1,S2,S3,S6,S10,S3,S4,S5,S17)

Table 2

Test paths generated for second benchmark via MFO

IInd Benchmark
Ist Path	(S1,S2,S3,S4,S3,S5,S6,S7,S8,S9,10)
IInd Path	(S1,S2,S3,S4,S3,S5,S6,S7,S8,S6,S7,S8,S9,10)
IIIrd Path	(S1,S2,S3,S4,S5,S6,S7,S8,S9,S10)
IVth Path	(S1,S2,S3,S4,S3,S5,S7,S8,S9,S10)
Vth Path	(S1,S2,S4,S5,S6,S7,S8,S9,S10)

Table 3

Test paths generated for third benchmark via MFO

IIIrd Benchmark
Ist Path	(S1,S4,S5,S6,S5,S9,S8,S4,S7,S8,S18)
IInd Path	(S1,S4,S5,S6,S3,S2,S8,S18)
IIIrd Path	(S1,S4,S5,S6,S10,S13,S16,S15,S14,S11,S8,S18)
IVth Path	(S1,S4,S5,S6,S10,S13,S16,S17,S10,S13,S9,S8,S18)
Vth Path	(S1,S4,S5,S6,S10,S13,S16,S3,S2,S8,S18)
VIth Path	(S1,S4,S5,S6,S12,S11,S8,S18)

6 Comparison of moth flame algorithm with existing nature inspired meta-heuristics

In this section, a comparison has been made among the test paths generated by MFO and other meta-heuristics.

6.1 Generation of test paths via firefly algorithm

Firefly algorithm has been used in the literature [18] for the generation of test paths of an object-oriented system. Following that process test paths generated for the selected benchmarks has been listed in Table 4.

6.2 generation of test paths via ant colony optimization algorithm

ACO has been broadly explored in the literature for the creation of software test cases [30, 41]. Following the same process as explained in [18] also, test paths generated via ACO have been provided in Table 5.

Table 5
Test paths generation via ACO

Ist Benchmark
Ist Path	(S1,S11,S17)
IInd Path	(S1,S2,S3,S4,S12,S13,S14,S4,S15,S16,S5, S17)
IIIrd Path	(S1,S2,S3,S6,S7,S3,S6,S8,S3,S4,S5,S17)
IVth Path	(S1,S2,S3,S6,S9,S3,S4,S5,S17)
Vth Path	(S1,S2,S3,S4,S15,S16,S5,S17)
VIth Path	(S1,S2,S3,S6,S10,S3,S4,S5,S17)
IInd Benchmark
Ist Path	(S1,S2,S4,S5,S7,S8,S6,S7,S8,S9,S10)
IInd Path	(S1,S2,S3,S4,S3,S5,S6,S7,S8,S9,S10)
IIIrd Benchmark
Ist Path	(S1,S4,S7,S8,S4,S7,S8,S18)
IInd Path	(S1,S4,S5,S9,S8,S18)
IIIrd Path	(S1,S4,S5,S6,S3,S2,S8,S4,S7,S8,S18)
IVth Path	(S1,S4,S5,S6,S12,S11,S8,S4,S7,S8,S18)
Vth Path	(S1,S4,S7,S8,S4,S5,S9,S8,S18)
VIth Path	(S1,S4,S5,S6,S10,S13,S16,S15,S14,S11,S8, S4,S5,S6,S5,S9,S8,S18)
VIIth Path	(S1,S4,S5,S6,S10,S13,S9,S8,S18)
VIIIth Path	(S1,S4,S5,S6,S10,S13,S16,S3,S2,S8,S18)
IXth Path	(S1,S4,S5,S6,S10,S13,S16,S17,S10, S13,S9,S8,S18)
Xth Path	(S1,S4,S5,S6,S10,S13,S16,S15,S14, S10,S13,S9,S8,S18)

Now, we had discussed the test paths generated by MFO, FA and ACO algorithm. The generated consequences are summarized in Table 6.

Table 6

Comparison among MFO, FA and ACO

	Number of States	Nature-inspired Meta-heuristic	Number of Test Paths Generated	Time Taken in Generation of Test Paths (in ms)	Redundancy in Test Paths (in %)
First Benchmark	17	Moth Flame Optimization	6	3247	48.8
		Firefly Algorithm	8	13103	50.12
		Ant Colony Optimization	6	18557	51.06
Second Benchmark	10	Moth Flame Optimization	5	3998	69.38
		Firefly Algorithm	4	30538	60
		Ant Colony Optimization	2	12078	30
Third Benchmark	18	Moth Flame Optimization	6	3817	54.38
		Firefly Algorithm	7	24033	57.14
		Ant Colony Optimization	10	20211	73

Table 6 is having three factors for comparison, namely: number of test paths generated by each algorithm, time take by them and redundant percentage of generated test paths.

Redundancy of test paths has been computed as: $\frac{\begin{matrix} Percentage redundancy = \\ Number of redundant paths \end{matrix}}{total number of paths} \times 100$ (10)

On the basis of Table 6, graphical analysis of the discussed algorithms has been provided in Figures 10 and 11.

Fig. 10

Comparison on the basis of redundant paths (in %).

Fig. 11

Comparison on the basis of execution time(in ms).

7 Conclusion and future work

The present research article discusses the problems imposed by object-oriented software testing. MFO algorithm has been proposed aiming the generation of unique and reduced test paths using model based testing. This algorithm has been computed on three benchmark problems having different number of states. Obtained results have been compared with Firefly and Ant Colony Optimization algorithm. Results indicate that MFO algorithm produces reduced test paths when number of states are large i.e MFO is suitable for large sized object-oriented software applications, and for small sized applications ACO generates lesser number of paths and its suits better for that. Secondly, time taken by MFO is much smaller than other algorithms. Again, MFO provides lesser redundancy for large applications and for small applications ACO would be better. Thus on the basis of above observations, we can rank these algorithms as:

For Large Object-Oriented Application

MFO>FA>ACO.

For Small Object-Oriented Application

ACO>MFO>FA.

As a primary future work, we plan to compare MFO with other meta-heuristics as well on the combination of both small and large sized software.

References

Mathur

A.P.

, Foundations of Software Testing, 1st. ed. Addison-Wesley Professional, 2008.

Episkopos

D.C.

, Li

J.J.

, Yee

H.S.

and Weiss

D.M.

, Prioritize code for testing to improve code coverage of complex software, 2011, us Patent 7,886,272.

Wirfs-Brock

, Wilkerson

and Wiener

, Designing object-oriented software, 1990.

Walden

and Nerson

J.M.

, Seamless object-oriented software architecture: Analysis and design of reliable systems, Prentice-Hall, 1995.

Al-Ahmad

, Object-oriented design patterns for detailed design, Journal of Object Technology5 (2) (2006), 155–169.

Murthy

A.R.C.

, Palani

and Iyer

N.R.

, Object-oriented programming paradigm for damage tolerant evaluation of engineering structural components, Advances in Engineering Software42 (1) (2011), 12–24.

Binder

R.V.

, Testing object-oriented systems: A status report, American Programmer7 (1994), 22–22.

Orso

and Silva

, Open issues and research di-rections in object-oriented testing, in Proceedings of the 4th International Conference on Achieving Quality in Software: Software Quality in the Communication Society, 1998.

Kung

, Gao

, Hsia

, Toyoshima

, Chen

, Kim

Y.-S.

and Song

Y.-K.

, Developing an object-oriented software testing and maintenance environment, Communications of the ACM38 (10) (1995), 75–87.

10.

Doong

R.-K.

and Frankl

P.G.

, The astoot approach to testing object-oriented programs, ACM Transactions on Software Engineering and Methodology (TOSEM)3 (2) (1994), 101–130.

11.

Kim

S.-W.

, Clark

J.A.

and McDermid

J.A.

, Investigating the effectiveness of object-oriented testing strategies using the mutation method, Software Testing, Verification and Reliability11 (4) (2001), 207–225.

12.

Wappler

and Lammermann

, Using evolutionary algorithms for the unit testing of object-oriented software, in Proceedings of the 7th annual conference on Genetic and evolutionary computation. ACM, 2005, pp. 1053–1060.

13.

Fraser

and Arcuri

, Evosuite: Automatic test suite generation for object-oriented software, in Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering. ACM, 2011, pp. 416–419.

14.

Wappler

and Wegener

, Evolutionary unit testing of object-oriented software using a hybrid evolutionary algorithm, in Evolutionary Computation, 2006. CEC 2006. IEEE Congress on. IEEE, 2006, pp. 851–858.

15.

Yang

X.S.

, Nature-inspired metaheuristic algorithms. Luniver press, 2010.

16.

Doungsa-ard

, Dahal

, Hossain

and Suwannasart

, Test data generation from uml state machine diagrams using gas, in Software Engineering Advances, 2007. ICSEA 2007. International Conference on. IEEE, 2007, pp. 47–47.

17.

and Lam

C.P.

, Software test data generation using ant colony optimisation, in International Conference on Computational Intelligence, 2004, pp. 1–4.

18.

Sharma

and Saha

, Optimization of object-oriented testing using firefly algorithm, Journal of Information and Optimization Sciences38 (6) (2017), 873–893.

19.

Zhao

, Zhao

and Guo

, Using gm (1, 1) optimized by mfo with rolling mechanism to forecast the electricity consumption of inner mongolia, Applied Sciences6 (1) (2016), 20.

20.

Pretschner

, Model-based testing, in Software Engineering, 2005. ICSE 2005. Proceedings 27th International Conference on IEEE, 2005, pp. 722–723.

21.

Jürjens

, Model-based security testing using umlsec: A case study, Electronic Notes in Theoretical Computer Science220 (1) (2008), 93–104.

22.

Utting

, Pretschner

and Legeard

, A tomy of model-based testing approaches, Software Testing, Verification and Reliability22 (5) (2012), 297–312.

23.

Mirjalili

, Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm, Knowledge-Based Systems89 (2015), 228–249.

24.

Khalilpourazari

and Pasandideh

S.H.R.

, Multi-item eoq model with nonlinear unit holding cost and partial backordering: Moth-flame optimization algorithm, Journal of Industrial and Production Engineering34 (1) (2017), 42–51.

25.

Allam

, Yousri

and Eteiba

, Parameters extraction of the three diode model for the multi-crystalline solar cell/module using moth-flame optimization algorithm, Energy Conversion and Management123 (2016), 535–548.

26.

Swain

S.K.

, Mohapatra

D.P.

and Mall

, Test case generation based on state and activity models, Journal of Object Technology9 (5) (2010), 1–27.

27.

Bouchachia

, Mittermeir

, Sielecky

, Stafiej

and Zieminski

, Nature-inspired techniques for conformance testing of object-oriented software, Applied Soft Computing.

28.

Srivastava

P.R.

, Singh

A.K.

, Kumhar

and Jain

, Optimal test sequence generation in state based testing using cuckoo search, International Journal of Applied Evolutionary Computation (IJAEC)3 (3) (2012), 17–32.

29.

and Lam

C.P.

, An ant colony optimization approach to test sequence generation for state based software testing, in Quality Software, 2005. (QSIC 2005). Fifth International Conference on. IEEE, 2005, pp. 255–262.

30.

Srivastava

P.R.

and Baby

, Automated software testing using metahurestic technique based on an ant colony optimization, in Electronic System Design (ISED), 2010 International Symposium on. IEEE, 2010, pp. 235–240.

31.

Shirole

, Suthar

and Kumar

, Generation of improved test cases from uml state diagram using genetic algorithm, in, Proceedings of the 4th India Software Engineering Conference. ACM, (2011), pp. 125–134.

32.

Srivastava

P.R.

, Khandelwal

, Kumar

and Santebennur Ranganatha

, Automated test data generation using cuckoo search and tabu search (csts) algorithm, 2012.

33.

Lam

S.S.B.

, Raju

M.H.P.

, Ch

, Srivastav

P.R.

, Automated generation of independent paths and test suite optimization using artificial bee colony, Procedia Engineering30 (2012), 191–200.

34.

Sharma

, Sabharwal

and Sibal

, Applying genetic algorithm for prioritization of test case scenarios derived from uml diagrams, arXiv preprint:1410.4838, 2014.

35.

McMinn

and Holcombe

, Evolutionary testing of state-based programs, in Proceedings of the 7th annual conference on Genetic and evolutionary computation. ACM, 2005, pp. 1013–1020.

36.

Tonella

, Evolutionary testing of classes, ACM SIGSOFT Software Engineering Notes29 (4) ACM (2004), 119–128.

37.

Doungsa-ard

, Dahal

, Hossain

and Suwannasart

, Ga-based automatic test data generation for uml state diagrams with parallel paths, Advanced Design and Manufacture to Gain a Competitive Edge, 2008, pp. 147–156.

38.

Chen

and Zhong

, Automatic path-oriented test data generation using a multi-population genetic algorithm, in Natural Computation, 2008. ICNC’08. Fourth International Conference on, vol. 1. IEEE, 2008, pp. 566–570.

39.

Yang

X.-S.

, Firefly algorithms for multimodal optimization, in International Symposium on Stochastic Algorithms. Springer, 2009, pp. 169–178.

40.

Dorigo

, Maniezzo

and Colorni

, Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)26 (1) (1996), 29–41.

41.

Colorni

, Dorigo

, Maniezzo

, Distributed optimization by ant colonies, European conference on artificial life, vol. 142France, Paris, 1991, pp. 134–142.

42.

Kamal

, Brailletotexttranslator, https://github.com/MinhasKamal/BrailleToTextTranslator, 2013.

43.

Shlaer

and Mellor

S.J.

, Object lifecycles: Modeling the world in states. Yourdon Press, 1992.

44.

Srivatsava

P.R.

, Mallikarjun

and Yang

X.-S.

, Optimal test sequence generation using firefly algorithm, Swarm and Evolutionary Computation8 (2013), 44–53.

Optimal test sequence generation in state based testing using moth flame optimization algorithm

Abstract

Keywords

1 Introduction

2 Background work

3 Methodology used

3.1 Techniques used

3.1.1 Moth flame optimization algorithm (MFO)

4 Proposed moth flame optimization algorithm

4.1 Generation of state transition diagram

4.4 Computation of fitness function for moths

4.6 Computation of test paths based on the spiral motion of moths

6.1 Generation of test paths via firefly algorithm

6.2 generation of test paths via ant colony optimization algorithm

Table 5 Test paths generation via ACO

References

Table 5
Test paths generation via ACO