E. E. Khatko ^{1}, V. A. Filippov ^{2}
^{1}Moscow Institute of Physics and Technology, State University, Moscow, Russian Federation
^{2}Moscow Institute of Electronics and Mathematics of National Research University a higher School of Economy, Moscow, Russian Federation
Correspondence to: V. A. Filippov , Moscow Institute of Electronics and Mathematics of National Research University a higher School of Economy, Moscow, Russian Federation.
Email:  
Copyright © 2012 Scientific & Academic Publishing. All Rights Reserved.
Abstract
Because of rapid mobile technologies expansion, there is a gap between the complexity of mobile applications and the complexity of employed testing techniques. This paper is aimed at reducing the gap from the practical point of view. Tests generation techniques are widely spread, but none of them are optimized for mobile applications. This paper proposes an analytical model of tests generation process, which is based on prototypes and takes mobile specificity into consideration. Along with this an analysis of existing tests generation approaches has beenmade. The flowchart of the proposed model has been submitted with the model. The efficiency of the model has been described in the numerical results section.
Keywords:
Testing, Tests Automation, Tests Generation, Mobile Applications
Cite this paper:
E. E. Khatko , V. A. Filippov , "An Analytical Model of Tests Generation Process for Mobile Applications", Software Engineering, Vol. 2 No. 4, 2012, pp. 174179. doi: 10.5923/j.se.20120204.11.
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] WEBrelated tests generation techniques are described. The proposed approach makes use of WEB specificity – clientserver architecture of the application and userapplication 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 «Tmethod» 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 pathfinding 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 pathfinding 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 BellmanFord algorithm[9].The FloydWarshall 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 minimalcost 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 modelLet’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 valueTo 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 conditionsThere 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]: , whereEFSM graph complexity:, where – thenumber of graph nodes–thenumber of graph edges – thenumber of graph parameters – thenumber of graph edge conditions–thepriority factorOn 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.
References
[1]  Рубинов, К. В., Веденеев, В. В. and Парфенов, В. Г. Метод разработки тестов для программных интерфейсов приложений на основе конечноавтоматной модели тестирования. СанктПетербург: СанктПетербургский государственный университет информационных технологий, механики и оптики. 
[2]  Khatko, E. E. and Fillipov, V. A. Mobile applications testing processes metrics and optimization criteria. Software Engineering. 2012, Vol.? 
[3]  Шмейлин, Б. З. Современные технологии тестирования WEB приложений. Системы и средства информатики. 2009, pp. 138147. 
[4]  Хатько, Е. Е. Об одном методе тестирования «мобильных» приложений. Труды МФТИ. 2012. 
[5]  Карпов, Ю. Г. Теория автоматов. СанкПетербург: Питер, 2003. 
[6]  Ural, H. Formal methods for test sequence generation. Computer communications. 1992, Vol. 15. 
[7]  Johnson, E. and Edmonds, J. Matching, Euler tours and the Chinese postman. Ontario: University of Waterloo, Waterloo, Ontario, Canada, 1972. 
[8]  Skiena, S. Eulerian cycle / Chinese postman. The algorithm design manual. New York: Springer, 2012. 
[9]  —. The algorithm design manual – Graph Traversal. The algorithm design manual. London: Springer, 2008, pp. 162169. 
[10]  Кормен, Т. Х., et al. Алгоритмы: построение и анализ. Москва: Вильямс, 2006. 
[11]  Decher R., Pearl J. Generalized BestFirst Search Strategies and the Optimality of A*. Journal of the Association for Computing Machinery. 1985, Vol. 32, 3. 
[12]  Современные проблемы фундаментальных и прикладных наук. Хатько, Е. Е. Москва, Долгопрудный: s.n., 2010. Один способ реализации алгоритма генерации тестов в тестировании на основе моделей. Vol. 1, pp. 9295. 52. 
[13]  Edmonds, J. Matching, Euler tours and the Chinese postman. Canada: University of Waterloo, 1972. 
[14]  Хатько, Е. Е. and Филиппов, В. А. Алгоритмы генерации тестовых сценариев для повышения качества программного обеспечения многозадачных пользовательских комплексов. Качество. Инновации. Образование. 2011, Vol. 10, pp. 4752. 
[15]  Open Source Software Engineering Tools. mbt.tigris.org. [Online] http://mbt.tigris.org/. 
[16]  Khatko, E and Fillipov, V. Mobile applications tests processes metrics and criteria. International Journal of Networks and Communications. ?, 2012, Vol. ? 