Vadim Eremichev

Faculty of computer science and technology.

Cathedra of automatic control systems.

Specialty Information control systems

Theme: Automatic test sets development for software on C1 criteria.

The scientific adviser: Cand.Tech.Sci., docent. Helen Savkova.

Abstract

Introduction

In software testing there are a number of tasks that are time consuming and cumbersome, and therefore they require automation. One such problem is the generation of test sets. Test sets are based on testing according to the criterion of the specifications of the program.

Goals and objectives which should be solved.

The problem is to automatically obtain a set of variables that would allow the test program in accordance with specific criteria for testing. In this task was chosen the criterion C1 - a criterion for testing the program branches. Therefore, the goal is to automatically obtain a set of values that would allow to test the software branch. Completeness of coverage achieved by testing the degree of testing all branches. The article provides a brief overview of the method, which can be used to create a test suite for the passage of branches of the program.

The aim of masters work is to offer a an effective way to develop automated test sets by C1 - criteria test branches of the software. In order to achieve the goal should be to solve a number of tasks listed in the list below: The task of parsing the source code to highlight it in the branches, as well as determining the possible values of the parameters of the conditions.

Construction of the control graph of the program on the basis of data obtained in the preceding paragraph, for the convenience of the degree of tracking are tested found the branches. The development of test sets for testing CGP branches. These tasks do not belong to the category of trivial and requires careful attention to itself, and a thorough study of the absence of such systems being developed by the project can be attributed to the project with a high degree of novelty

Actuality of the topic

Automated creation of test sets is one of the most labor-intensive processes in the software testing. Also, this is a very responsible and meticulous work. Because it is the quality of the product. depends from the quality of the tests The high degree of testing program depends on the coverage tests of branches or paths, depending on how the tester uses a criterion in their work. Creating a test - a very laborious process that takes up most of the time of the test. In order to increase efficiency of testing and to facilitate their work, you need to automate the process as possible. The process of creating test sets consists of the substage are presented below:

1. Creation CGP
2. The choice of test paths
• Static methods - construction of each of its way by gradually lengthening by adding arcs, until you reach the top of the output. Disadvantages - does not take into account the possible ways of testing unrealizability constructed (an unpredictable percentage of defects). - The complexity of (the transition from covering multiple ways to complete the system test is carried out manually) Dignity - a relatively small amount of resources needed
• Dynamic methods - construction of a complete system of tests that satisfy the specified criteria, by simultaneously solving the problem of constructing the spanning set of paths and test data. It is possible to automatically take into account the feasibility and unrealizability previously considered routes or parts thereof. Dignity - a level of quality - the feasibility of ways.
• Methods of implemented ways, the selection of the many ways a subset of all realizable paths that are the building covers a variety of ways.
3. Test generation, the relevant test paths.

The following are not all the tasks associated with testing software, but only those that may be of interest to the research, and require special approaches to the solution:

1. Generation and selection of test data.
2. Creating a model testing.
3. The task of a test oracle.
4. Selection criteria for test coverage and evaluation of test coverage.
5. Generation of test scenarios.

Objectives of testing based on the following postulates of software testing:

• complete testing is impossible;
• wholly-owned test automation is not possible;
• the absence of a general theory of testing.

Studies on the generation of test data being everywhere, and a large number of publications leads to the fact that the developed approach is difficult to classify.

Current research results.

To solve this problem are encouraged to use the advanced features of finite automata to model test program based on the control graph and genetic algorithms to automate the creation of tests.

For example, a program code which, by the value of an integer to print his prime characteristic - it is zero, even or odd number, positive or negative.

Figure 1 - The control graph of the program

The proposed approach involves the formalization of the maximum specifications. In turn, the program control graph can be represented as a finite automaton extended, containing variables and guard conditions on perehodah.Vse requirements specification must be met during the performance of the program. Automatic response to the event and performs conversions based on the values of variables automaton model that is used in security conditions on transitions. Type of machine is shown in Figure 2.

Figure 2 - The final enhanced machine (animation: 7 frames, 6 Kb, 7 cicles)

Presentation of the test as a sequence of events and a set of values of external variables is convenient from the viewpoint of automatic code generation test, but is inconvenient and it is not clear to the developer, which is based on specifications written in natural language. Therefore, the developer writes a test as a sequence of transitions in the model. In this case, the problem arises of finding the sequence of events and a set of values of external variables, corresponding to a given sequence of transitions in the model. The following sets out the principle of solving this problem based on the use of genetic algorithms.

The sequence of events is uniquely determined by a sequence of transitions. Harder to find the values of variables - they must meet certain requirements. First, the security conditions at all road crossings in the above must be met. Second, all of the requirements specification facilities management should be performed, since the use of real values of these variables will come from facilities management to the data specifications. In the proposed approach, genetic algorithms are applied to solve the problem of finding a set of values, which will be executed given path in the extended finite state machine. Such a problem can be reduced to an optimization problem. Construction of the optimization problem

We have a set of external variables involved in the chosen sequence of transitions. This set can be viewed as a vector of values of external variables < x₁, x₂, …, x _n >, where x_i – value of external variable, а n – number of external variables for this path.To use optimization algorithms to determine the fitness function - a function that evaluates how the chromosome solves the problem, and allows you to choose the best solution of all generations. In this problem, fitness function takes as input a vector of values and issues a number characterizing the suitability of this vector for a given path. The smaller the number, the more appropriate given the vector of values. Thus, the problem of finding a suitable set of values of external variables is reduced to an optimization problem, where you want to find a vector, which corresponds to the minimum value of fitness function.

For this task, the chromosome will be a vector of exogenous variables, consisting of one element - the variable n. For the general case of a single gene is the value of one variable for a given path. Crossing is a classic one-point method. Mutation of a gene replacement of any random value of the acceptable range of values. There is no single method for determining the fitness function does not exist. Nevertheless, there is a criterion that is the distance to the conditions (Branchdistance), to determine the fitness of chromosomes. The distance to the conditions to evaluate how close a given chromosome to perform a specific condition, which in practice has not been fulfilled. For example, for the condition A > B, the distance to the conditions will be calculated by the formula | A - B |. The smaller value of | A - B |, the closer the value of A to B, and the closer the chromosome to ensure that this condition was fulfilled. If the condition is satisfied, then the distance to the conditions of zero. The distance to the conditions can be represented as (1)

(1)

Fitness function based on the use of the criterion distance to the conditions, has been successfully applied to find values for the path in the extended finite state machine, and these values are the boundary for the condition, which increases confidence in the test program.

For a sequence of transitions can be set to a large number of conditions, so the distance to the conditions of the entire path must be calculated separately, considering the conditions at each transition of the way. Each transition is described by a set of parameters:

1. The event, at which this transition can occur.
2. Guarding condition that must be met for making the transition.
3. Steps in the transition: the challenge of methods of control objects, obtaining values of external variables of the environment or change the values of the variables of the model.
4. Preconditions of transition, which include the requirements specification of the program, which must be satisfied for the transition, and the requirements of the specification of control objects, which must be met to invoke methods of control objects involved in the transition.
5. Postconditions transition, which include the requirements of the specification of the program and its facilities management.

After this initial sequence of transitions is considered as a sequence of steps. Evaluation of fitness of the whole sequence of steps is calculated as the sum of estimates for each step separately. Each step is estimated by calculating the distance for the condition. Note that the steps are performed sequentially, and that following the steps in the beginning of the journey is more important than at its end. For example, if the conditions of all the steps except the first, then the sum of the distances to the conditions will be small, since for all but the first step, this value will be zero. In practice, this chromosome does not allow to pass a single step, so as to successfully complete the second step, you must comply with all conditions in the first step. Therefore, the proposed approach, the distance to the conditions of steps are summarized in view of the location of these steps in a way - using a weighted sum of (2) adaptation of the way

(2)

If one step is set several conditions, the distance to the conditions of this step is calculated as the sum of the distances to the conditions of each of these conditions.

Conclusion

During the progress of research were discussed many methods of testing the program. In the end the choice fell on the criterion C1 as it allows you to produce enough high-quality testing. We can also perform testing of a single branch, without affecting the entire program. The evolutionary method as a test generation will easily find the right values for external variables of the program to go to the branch.

Sources

1. Wegener J., Buhr K., Pohlheim H., 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). NY: Morgan Kauf-mann. 2002, pp. 1233–1240.

2. Ms.Roshni Rajkumari, Ms.Roshni Rajkumari. Autmatic test data generation using genetic algorithm and program dependence graph

3. Кулямин В.В., Тестирование на основе моделей.

4. Монахов А., Петренко А., Бритвина Е., Петренко О., Грошев С. Тестирование на основе моделей.

5. Дастин Э., Рэшка Д., Пол Д. Автоматизированное тестирование программного обеспечения. Внедрение, управление и эксплуатация. М.: Лори, 2003.

6. Melanie Mitchell. Genetic Algorithms: An Overview

7. Koza J. Genetic Programming: On the programming of Computers by Means of Natural Selection. Cambridge: MIT Press, 1992.

8. В.Е. Алексеев, В.А. Таланов Графы и алгоритмы.

9. Дидковская М.В. Технологии разработки и тестирования программ

10. А.М. Карпушинский. Анализ неявного потока управления и его влияние на выбор структурных критериев тестирования объектно-ориентированных программ.