1. Introduction

In the last few years, mobile technologies have been rapidly expanding in everyday life. Almost every person on earth has a mobile telephone. Mobile devices are becoming more and more complex as new types of devices such as Smartphones, Communicators, Tablets, etc., have appeared. Such devices hardware hasconfigurations similar to yesterday’s desktops’, and thus they should be treated as complex hardware and software systems controlled by operating systems. In the era of conventional phones, testing processes were simple as well. Manual testing processes predominated. However, accelerated evolution of mobile devices leads to formation of a technology gap between the complexity of mobile applications and the complexity of the corresponding testing methods. Manual testing is no longer enough these days. A new complex approach with special test automation tools should come in its place. Therefore the problem of testing methods optimization is very important from the exploratory point of view and urgent from the practical point of view.

Tests generation based on an application model or proto type is one of the optimization ways that couldbe followed (in this paper prototypes are considered as models which describe applications based on user interface). Further model or prototype use depends on the way of formalizing the generation problem.

2. Analysis of Existing Tests Generation Techniques

There are different methods of formalizing the generation problem, but most of them do not take mobile specificity into consideration. In particular[1] describes an approach to UI level tests generation. The test suite generated this way, however, does not meet the requirement of mobile applications test criterion[2]. In[3] WEB-related tests generation techniques are described. The proposed approach makes use of WEB specificity – client-server architecture of the application and user-application sessions.Therefore this approach can’t be used for mobile tests generation.

There is a formalization that is based on an application’s representation as an extended finite state machine[4]. It’s well known[5] that extended finite state machines can be represented as graphs. EFSM’s states are considered as graph nodes and EFSM’s transitions – as graph edges.Therefore the tests generation problem is reduced to the graph traversal problem.Mobile applications testing coverage criterion[2], in terms of graph traversal, requires a maximum edge coverage result of traversal.[6] describesformal methods of tests generation. One of them is a «T-method» which is aimed at solving the Chinese Postman Problem (CPP)[7]. There are many particular solutions of the CPP,e.g. [7] describes a solution, based on the graph matching theory.

According to Euler Circuit Theorem[8] the graph has Euler’s circuit if and only if it’s strongly connected and its vertices are all of an even degree. Therefore one can’t solve the CPP problem for an arbitrary graph. The overall goal of a traversal is to approach the “solution” as closely as possible, namely: perform the traversal through all edges with a minimum number of each edge recurrences.

To solve the stated traversal problem, it’s appropriate to use graph path-finding algorithms. The main complication here is that the problem doesn’t define the start and end points of the path. The graph should be traversed until all of the edges are covered. There are different path-finding algorithms, so an appropriate modification of one of them could lead to a desired solution.

The Dijkstra's algorithm[9]finds closest paths from one node to the others. This algorithm is not suitable for dynamic graphs, where edges’ weights are changed according to the current context of the EFSM’s variables. The same situation is with the Bellman-Ford algorithm[9].

The Floyd-Warshall algorithm[10]finds closest paths between each pair of graph nodestherefore it’s not suitable, because the EFSM graph may change dynamically after each transition is made, so all pairs’ closest paths should be recalculated too often.

The Algorithm [11]is the minimal-cost path finding algorithm. It’s a greedy algorithm which uses heuristics to find the most suitable route “at the current moment”.There are modifications [12]which allow traversing a graph until all edges are covered. A modification of which is capable of containing the graph’s parameters and finding the path according to them is proposed in this paper.

The costs function is the base of the algorithm’s logic. The next edge to be covered is chosen according to the current value. The smaller the value, the more suitable the corresponding transition is.

3. Analytical Model of Tests Generation Process

Having studied the CPP and the Euler circuit finding problems[13], it’s proposed to use the following approach of finding the “next” edge to cover while staying in the “current” one.Let , where isthe path costs from the beginning edge to the “next” one. – heuristics that estimates the path costs from the next edge to the closest uncovered edge.

,

where- thecurrent edge, - weight of the current edge, - scale factor.

– where- the number of incoming / outgoing edges forthe- thnode.

– path costs to the closest uncovered edge.

During the traversal process:

• Before each andcalculation, thegraph is updated according to the EFSM condition of the “next” edge. The edges that become inaccessible in context of the condition are removed from the graph temporarily, until the next transition.

• The path to the closest uncovered edge is calculated, using the BFS algorithm[9].

Formally:

-thearray of all EFSM transitions.

-thearray of all covered transitions. The array is changed during the traversal process.

- thearray of all edges weights. The array is changed during the traversal process.

- theflag which indicates if the current edge is covered.

- thepath from the current edge to the closest uncovered one.

-thescale factor that prioritizes conditions: uncovered edges are chosen first, after that the closest edge to the next uncovered one is chosen.

So the following is the expression of finding the value for the -th edge:

(4)

Flowchart of the analytical model

Let’s consider a flowchart of finding the path which covers all edges of the EFSM graph. The elements “Find F value” and “Estimate extra ‘brake cycle’ conditions” will be covered below, as they are not that simple.

Findingthe F value

To find the value of for the -th transitionit’s required to find the following sum: . The procedure based on BFS algorithms is used for finding the sum.In Figure 2the flowchart of the procedure is presented.

Extra brake conditions

There are circumstances which brake the main cycle, returning the AppError: «Unable to find next transition in the current context, because of incorrect prototype parameters»

• Found paths are all equal to each other and contain all graph edges for all of the remaining successors of the current edge

• No paths are found for each of the remaining successors of the current edge

Figure 1. Flowchart of the analytical model

Figure 2. Finding F value flowchart

4. Numerical Results

Let’s estimate the efficiency of the proposed modelwith the help of following expression[2]: , where

EFSM graph complexity:, where

– thenumber of graph nodes

–thenumber of graph edges

– thenumber of graph parameters

– thenumber of graph edge conditions

–thepriority factor

On average, the number of mobile application states lies within the following edges: .The graphs of mobile applications EFSMs are always connected, therefore, the minimum number of edges is: .The estimate of the maximum number of edges is: , where - the maximum sum of incoming and outgoing edges through all the nodes. Thus, the average edges number is: . The analysis of the existing prototypes shows, that the averagevalue is 5, so.

Several EFSMs were taken to measure the efficiency of the proposed model. EFSMs parameters were taken to meet the above conditions. The test case generator[14] was chosen as the opponent model. This tool is used for tests generation based on prototypes. It works with prototypes, represented with graphml –an XML based graph description language. The tool allows setting different stop conditions, including the “100% transitions coverage” condition. This generator also makes use of the algorithm, but probably with a different expression. The following results were obtained when measuring generation processes efficiency:

Table 1. Efficiency of the proposed analytic model Prototype graph K M P C Proposed model Opponent model 6 8 1 1 2,89 2,17 6 9 1 2 2,48 2,26 6 15 2 6 2,61 1,81 13 26 5 6 1,74 0 16 36 9 11 2,34 0 16 48 2 18 2,69 2,51 21 66 3 23 2,42 2,60

The following are the curves of the obtained results.

Figure 3. Efficiency of the proposed analytic model

It can be stated from this curves, that the proposed model is more efficient than the analogue model, evidently because of the “correct” expression of the function.

5. Conclusions

The analysis of existing tests generation approaches has been made. An analytical model of tests generation process which is based on prototypes and takes mobile specificity into consideration is proposed. The scheme of the proposed model is submitted. The efficiency of the model is described in the numerical results section.