Data Flow testing using Genetic Algorithms

Abstract

 

Testing a software plays a very key role in software development life cycle. There are two types of testing in software development life cycle they are – white box testing and black box testing. Data flow testing comes under white box testing technique which involves flow of control and flow of data throughout the software for testing. Evolutionary approaches in testing selects are generates test data by using optimized searching techniques. The working for data flow testing by using genetic algorithm for automatic generation of testing locations for data flow testing. This algorithm generates random initial populations of test paths for data flow testing and then based on selected testing area new paths are generated by applying genetic algorithm. A fitness function in this algorithm evaluates the fitness of a chromosomes within selected data for data flow testing. There are two techniques for data flow testing like crossover, mutation of chromosomes from the selected testing data to generate new paths and figure out test results with good fitness values. This type of approach helps us to get good results compared to random testing.

1. Introduction

Software testing is the way toward executing a program with the expectation of discovering mistakes [1]. Programming testing is one of the vital periods of programming advancement life cycle. There are diverse sorts of programming testing including white box testing and discovery testing. White box testing confirms the inner rationale of the program while dark testing manages the check of the product usefulness. Programming testing can be performed at various dimensions including unit testing, joining testing and framework testing. Unit testing tests the single unit of programming including classes and techniques. Mix testing checks the interfaces utilized for correspondence between various segments and message going through these parts. Framework testing confirms the in general usefulness of the framework. White box testing is separated into two noteworthy classes, i.e., control stream testing and information stream testing. Control stream testing utilizes the control stream chart for programming testing [2] [3]. In a control stream diagram, a hub relates to a code portion; hubs are marked utilizing letters or then again numbers. An edge relates to the stream of control between code fragments; edges are spoken to as bolts. There is a passage and leave the point in a control stream diagram. Control stream testing criteria incorporate explanation inclusion, choice inclusion, condition inclusion and so forth. Information stream testing is a white box testing procedure used to check the stream of information over the product program. Information stream testing is utilized to check the definition and utilization of program factors in an exact way [2] [3]. Information stream testing is classified into static information stream testing and dynamic information stream testing. Static information stream testing doesn’t include the execution of the programming program. In this sort of information stream testing just a static examination is performed by breaking down the source code. Dynamic information stream testing really executes the programming program for the location of information irregularity. Extraordinary inclusion criteria are characterized for dynamic information stream testing to execute distinctive ways in programming program for discovery of abnormalities [2] [3]. Robotization is a vital angle for programming testing, without the computerized device, it is difficult to perform thorough programming testing. In this paper, we have actualized a robotized device for the age of test ways for information stream testing. The use of developmental calculations [4] to programming testing for an age of test information is known as transformative testing. In this paper, we have executed an instrument that utilizes the hereditary calculation for the age for test ways in information stream testing at the unit level. We have executed hereditary calculation in our apparatus for information stream testing for the age of test ways utilizing information stream inclusion criteria. The proposed explore device called ETODF is the continuation of our past work [6] on information stream testing utilizing developmental methodologies has been executed in Java dialect for approval. It explores, different avenues regarding this device, our methodology has much better results when contrasted with irregular testing. Whatever is left of the paper is composed as pursues: Segment 2 expounds the overview of various methods proposed for programming testing utilizing developmental methodologies, segment 3 portrays the proposed instrument (Genetic Algorithms) for information stream testing utilizing developmental methodologies and segment 4 is connected with analyses and testing results as in correlation with irregular testing. Area 5 closes the paper and shows what’s to come work.

2. Related Work

Tonella [7] utilized transformative testing for testing of classes at the unit level for the age of experiments. Subterranean insect state streamlining was connected by McMinn and Holcombe [8] to take care of state issue in protest situated projects. Affixing the approach was reached out to take care of state issues in question situated projects by McMinn and Holcombe [8]. Watkins [9] performed diverse examinations for correlation of wellness function by various scientists. As per them, branch predicate and opposite way likelihood approaches were the best wellness function when contrasted with different methodologies. Wegener et al. [10] [11] built up a robotized testing framework utilizing transformative methodologies for testing of inserted frameworks.

Baresel et al. [12] propose a few alterations in wellness function configuration to enhance transformative basic testing. A very much developed function can expand the shot of finding the arrangement and achieve a superior inclusion of the product under test and result in a superior direction of the hunt and in this way in improvements with less emphasis.

McMinn [13] gives an extensive overview of developmental testing approaches and talks about the application of developmental testing. The creator examines the extraordinary approaches in which developmental testing has been connected and additionally gives future bearings in every individual zone. Developmental methodologies are for the most part connected to the programming testing for mechanized test information age [14] [15] [16] [17] [18] [19]. Cheon et al. [20] characterized a wellness work for protest situated program. Dharsana et al. [21] create test cases for Java-based projects and furthermore performed streamlining of test cases utilizing hereditary calculation. Jones et al. [22] performed programmed basic testing utilizing hereditary calculation in their approach. Bilal and Nadeem [23] proposed a state-based wellness function for protest situated projects utilizing hereditary calculation. S.A Khanand Nadeem [24, 25] proposed approaches for test information age at reconciliation level utilizing transformative approaches.

There are two persuasive factors behind this examine the device. There is no or little research chip away at the dynamic information stream testing by applying developmental approaches. The second inspiration includes that there is no mechanized device for information stream testing that utilizes transformative approaches for dynamic information stream testing.

3. Using Genetic Algorithm

The proposed methodology [6] has been executed in a model instrument called Genetic Algorithm (Developmental Testing of Information Stream) in Java. The model device utilizes the hereditary calculation for the age of test way with single point traverse and change. The abnormal state engineering of the apparatus appears in Figure 6. Genetic Algorithm has the accompanying parts:

Graph Parser

Semantic Analyzer and Preserver

Test Path Generator

Sorter and Validator

Fitness Calculator

Genetic Algorithm takes information stream diagram as information and stores the chart in the wake of breaking down and applying semantic on every hub. The info of the information stream chart is as a nearness list. Contiguousness list is the portrayal of everything being equal or bends in a chart as a rundown. The parser parses the diagram and stores it in a parser protest. The parser question peruses the diagram data from the information record in the shape contiguousness list. The parser protest contains the chart protest that stores the entire diagram as nearness list in the memory for further handling in straight away parts.

The semantic analyzer and preserver is the most essential part of the Genetic Algorithm. This segment breaks down the semantic related with every hub and stores the semantic with every hub of the diagram. The semantic analyzer, what’s more, preserver peruses the information stream data from the information record furthermore, partners this data with every hub of the chart utilizing the parser question which stores the genuine chart. After semantic examination, every hub has now all data related to the definition and utilization of every factor. The hubs are currently capable to process the information stream inclusion criteria whenever connected on hubs in a way.

Fig .l. High Level Architecture of Genetic Algorithm

The test way generator is an imperative segment of Genetic Algorithm which initially produces the test way arbitrarily and on the second cycle, it utilizes hereditary calculation for test way age. The test way generator utilizes the hereditary calculation with one-point traverse and change for the age of new populace. The test ways are arranged by the sorter part of the Genetic Algorithm and after that, every way is approved utilizing semantics of the diagram for validness. In this progression, the invalid ways are dealt with from the test ways.

The substantial ways are passed to the wellness number cruncher which ascertains the wellness of every way utilizing the information stream inclusion criteria. The wellness mini-computer takes legitimate ways from Validator segments and information stream inclusion criteria from the client as information also, compute the wellness of the way as indicated by the information stream inclusion criteria. After the assessment, the way that fulfils the inclusion criteria legitimate are included the worldwide rundown of the way while those which don’t fulfil the inclusion criteria stays in the populace and utilized in the recombination and change for straightaway cycle.

4. Genetic Algorithm implementation

The significant bundles executed in the apparatus have appeared in bundle chart in figure 2. The GraphParser class peruses the input chart and store it in parser question. The Node Information class peruses the information stream data and it contains the information stream data of every hub. The DataflowCriteria class characterizes the testing criteria for dynamic information stream of testing. The FitnessCalculator class computes the wellness of every chromosome and it likewise figures the wellness of populace. The Centralized server is the section point for Genetic Algorithm instrument, this class is in charge of producing GUI of the device, what’s more, this is the principle controller class that calls different classes. The rest of the classes are partner classes for various functionalities in the Genetic Algorithm.

5. Case Study

Trial results have been gotten utilizing proposed technique by applying apparatus Genetic Algorithm on the procedural code at the unit level. We have utilized All definitions, all uses, All-c-uses, and All p-utilizes criteria for our tests also, contrast the outcomes and irregular testing. We utilized the following code for our trials with Genetic Algorithm. In tests with this model, our methodology has much better results when contrasted with arbitrary testing.

Table .1. Source Code used for Evaluation of

Genetic Algorithm

In this precedent, there are distinctive factors characterized and utilized. We have connected the Genetic Algorithm on these factors and thought about the outcomes with irregular testing. The example ways for All definitions, All-c-uses and All-p-utilizes for variables, it is given beneath in table 2. The information stream diagram for the source code appears in figure 2.

Table .2. Sample Path for Variable ‘tv’ and ‘ti’

Fig .2. Data Flow Graph

 Figure 3 shows the generated values from a Genetic Algorithm.

Fig .3. The Generated Values using a

Genetic Algorithm

We have performed explores different avenues regarding our proposed apparatus for information stream testing criteria i.e. All definitions, All C-Uses, and All Purses and so on. We have performed hundred emphasizes with Genetic Algorithm for an age of test ways that fulfil information stream testing criteria as chosen by the client from Genetic Algorithm UI. For the age of five experiments for All definitions, arbitrary testing had taken forty-three cycles while ETODF takes just twelve emphasizes. Correspondingly for ten experiments, irregular testing took eighty-seven cycles while ETODF took as it were twenty-one cycles for All definitions testing criteria. For the age of five experiments for All C-Uses, irregular testing had taken fifty-six cycles while ETODF takes just eleven emphases. Essentially, for ten experiments irregular testing took a hundred cycles and it can’t create hundred per cent results while Genetic Algorithm took just twenty-seven cycles for All C-Uses testing criteria. For All P-Uses/Some C-Uses what not P-Uses results outlined in Table 3. For the test results, it has been presumed that our proposed instrument has much better outcomes when contrasted with irregular testing. We contend that our methodology will perform shockingly better for vast and complex programs too.

Table 3 concludes the results obtained from different approaches, our proposed genetic algorithm and random testing.

Table .3. Comparison of Random Testing and

Genetic Algorithm Values

From table 3, it has been reasoned that just Genetic Algorithm produces hundred per cent results in all cases and in all testing criteria while irregular testing performs better in the little arrangement of prerequisites and it isn’t creating hundred per cent results where prerequisites are higher regarding quantities of test cases (ways). Based on these outcomes, we contend that the approach will perform far better for substantial and complex programs too

6. Experimental Measurements

I have cross verified the efficiency of proposed values with random test values on two verifications:

Number of Iterations

Coverage

Fig .4. Genetic Algorithm and Random Iterations

Number of emphases shows that what number of cycles are required for the age of test way as per the inclusion criteria. As per the outcomes, we got from analyses Genetic Algorithm out performs arbitrary testing and has much better outcomes when contrasted with arbitrary testing as appeared in figure. The thing that matters is higher when quantities of way are more.

Fig .5. Genetic Algorithm and Random Coverage

Coverage demonstrates that how much coverage is accomplished in getting number of test ways as per the coverage criteria.

Coverage = (Generated Paths/Required Paths) *100

According to the results, we got from experimental values of Genetic Algorithm out performs random test values and has much better optimized results as compared to random test values as shown in figure 5. Genetic Algorithm has achieved 100% percent results in all the areas of testing. The difference when cross verified is much more than the greatest paths are used.

7. Conclusion and Future Work

This theory shows the usage of genetic algorithm for the automatic generation of test paths using data flow calculation. The usage of genetic algorithm is implemented and seen in Java. In experiments with this algorithm, my approach has much optimized results as compared to random test value results. I will extend this type of testing to all the other levels of testing i.e., system testing, unit testing and integration testing. Currently I compared the output of experimental testing to the random testing values only. In future, I will also carry out complete wide investigations on large case studies for the verification and clarification of this proposed approach using all data flow coverage criteria’s.

8. References

[1] Boris Beizer, “Software Testing Techniques”, International Thomson Computer Press, 1990.

[2] Lee Copeland, “A Practitioner’s Guide to Software Test Design”, STQE Publishing, 2004.

[3] Khan, M. “Different Approaches to White Box Testing Technique for Finding Errors”, International Journal of Software Engineering and Its Applications, Vol.5, No.3, July, (2011).

[4] Rao, V. and Madiraju, S. “Genetic Algorithms and Programming -An Evolutionary Methodology”, International Journal of Hybrid Information Technology, Vol.3, No.4, October, (2010).

[5] Srivastaval, P. and Kim, T.”Application of Genetic Algorithm in Software Testing”, International Journal of Software Engineering and Its Applications, Vol.3, No.4, October, (2009).

[6] Khan, S. and Nadeem, A., “Applying Evolutionary Approaches to Data Flow Testing at Unit Level”. Software Engineering, Business Continuity, and Education Communications in Computer and Information Science, 2011.

[7] Tonella, P., (2004 July) “Evolutionary Testing of Classes”, In Proceedings of the ACM SIGSOFT International Symposium of Software Testing and Analysis, Boston, MA, pp. 119-128.

[8] McMinn, P., Holcombe, M., (2003 July) “The state problem for evolutionary testing.” In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Lecture Notes in Computer Science vol. 2724, pages 2488-2497, Chicago, USA. Springer-Verlag.

[9] Watkins, A., (1995 July) “The automatic generation of test data using genetic algorithms.” In Proceedings of the Fourth Software Quality Conference, pages 300-309. ACM, 1995.

[10] Wegener, J., Baresel, A., Sthamer, H., (2001) “Evolutionary test environment for automatic structural testing.” Information and Software Technology Special Issue on Software Engineering using Metaheuristic Innovative Algorithms, 43 pp.841-854.

[11] Wegener, J., Buhr, K., Pohlheim, H., (2002 July) “Automatic test data generation for structural testing of embedded software systems by evolutionary testing”, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), pages 1233-1240, New York, USA. Morgan Kaufinann.

[12] Baresel, A., Sthamer, H., Schmidt, M., (2002 July) “Fitness Function Design to improve Evolutionary Structural Testing”, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 02), New York (NY), USA.

[13] McMinn, P., (2004) “Search-based Software Test Data Generation: A Survey”, Journal of Software Testing, Verifications, and Reliability, vol. 14, no. 2, pp. 105-156, June.

[14] McGraw, G., Michael, C., Schatz, M., (2001) “Generating software test data by evolution.” IEEE Transactions on Software Engineering, 27(12): 1085 1110.

[15] Pargas, R., Harrold, M., Peck, R., (1999) “Test-data generation using genetic algorithms. Software Testing”, Verification and Reliability, 9(4):263-282.

[16] Roper, M., (1997 May) “Computer aided software testing using genetic algorithms.” In 10th International Software Quality Week, San Francisco, USA.

[17] Tracey, N., Clark, J., Mander, K., McDermid, J., (2000) “Automated test-data generation for exception conditions”, SOFTWARE—PRACTICE AND EXPERIENCE, vol., Pages 61-79, January.

[18] Sthamer, H., (1996) “The automatic generation of software test data using genetic algorithms”, PhD Thesis, University of Ghamorgan, Pontyprid, Wales, Great Britain.

[19] Seesing, A., Gross, H., (2006) “A Genetic Programming Approach to Automated Test Generation for Object-Oriented Software”, International Transactions on Systems Science and Applications, vol. l,no. 2, pp. 127-134.

[20] Cheon, Y., Kim, M., (2006 July) “A specification-based fitness function for evolutionary testing of object-oriented programs”, Proceedings of the 8th annual conference on Genetic and evolutionary computation, Washington, USA.

[21] Dharsana, C.S.S., Askarunisha, A., (2007 December) “Java based Test Case Generation and Optimization Using Evolutionary Testing”. International Conference on Computational Intelligence and Multimedia Applications, Sivakasi, India.

[22] Jones, B., Sthamer, H., Eyres, D., (1996) “Automatic structural testing using genetic algorithms”, Software Engineering Journal, vol. 11, no. 5, pp. 299-306.

[23] Bilal, M., Nadeem, A., (2009 April) “A State based Fitness Function for Evolutionary Testing of Object-Oriented Programs”. Studies in Computational Intelligence, 2009, Volume 253/2009, 83-94, DOI: 10.1007/978-3-642-05441-9. Software Engineering Research, Management and Applications 2009.

[24] SA Khan, A Nadeem, “Automated Test Data Generation for Coupling Based Integration Testing of Object Oriented Programs Using Evolutionary Approaches”, Proceedings of the 2013 10th International Conference on Information Technology: New Generations (ITNG 2013), Pages 369-374, LAS Vegas, Nevada, USA.

[25] S.A Khan, A. Nadeem, “Automated Test Data Generation for Coupling Based Integration Testing of Object Oriented Programs Using Particle Swarm Optimization (PSO)”, Proceedings of the Seventh International Conference on Genetic and Evolutionary Computing, ICGEC 2013, August 25 – 27,2013 Prague, Czech Republic.