Test data generation for path coverage of message-passing parallel programs based on co-evolutionary genetic algorithms

Employing genetic algorithms to generate test data for path coverage has been an important method in software testing. Previous work, however, is suitable mainly for serial programs. Automatic test data generation for path coverage of message-passing parallel programs without non-determinacy is investigated in this study by using co-evolutionary genetic algorithms. This problem is first formulated as a single-objective optimization problem, and then a novel co-evolutionary genetic algorithm is proposed to tackle the formulated optimization problem. This method employs the alternate co-evolution of two kinds of populations to generate test data that meet path coverage. The proposed method is applied to seven parallel programs, and compared with the other three methods. The experimental results show that the proposed method has the best success rate and the least number of evaluated individuals and time consumption.     

Observations in using parallel and sequential evolutionary algorithms for automatic software testing

In this paper we analyze the application of parallel and sequential evolutionary algorithms (EAs) to the automatic test data generation problem. The problem consists of automatically creating a set of input data to test a program. This is a fundamental step in software development and a time consuming task in existing software companies. Canonical sequential EAs have been used in the past for this task. We explore here the use of parallel EAs. Evidence of greater efficiency, larger diversity maintenance, additional availability of memory/CPU, and multi-solution capabilities of the parallel approach, reinforce the importance of the advances in research with these algorithms. We describe in this work how canonical genetic algorithms (GAs) and evolutionary strategies (ESs) can help in software testing, and what the advantages are (if any) of using decentralized populations in these techniques. In addition, we study the influence of some parameters of the proposed test data generator in the results. For the experiments we use a large benchmark composed of twelve programs that includes fundamental algorithms in computer science.     

A multiple-population genetic algorithm for branch coverage test data generation

The software testing phase in the software development process is considered a time-consuming process. In order to reduce the overall development cost, automatic test data generation techniques based on genetic algorithms have been widely applied. This research explores a new approach for using genetic algorithms as test data generators to execute all the branches in a program. In the literature, existing approaches for test data generation using genetic algorithms are mainly focused on maintaining a single-population of candidate tests, where the computation of the fitness function for a particular target branch is based on the closeness of the input execution path to the control dependency condition of that branch. The new approach utilizes acyclic predicate paths of the program’s control flow graph containing the target branch as goals of separate search processes using distinct island populations. The advantages of the suggested approach is its ability to explore a greater variety of execution paths, and in certain conditions, increasing the search effectiveness. When applied to a collection of programs with a moderate number of branches, it has been shown experimentally that the proposed multiple-population algorithm outperforms the single-population algorithm significantly in terms of the number of executions, execution time, time improvement, and search effectiveness.     

软件测试数据智能化生成的研究

软件测试数据自动生成是软件测试中的重要难题之一。测试数据自动生成问题可归结为测试数据的搜索或组合优化问题，通常具有不连续、不可微和非线性等特征，适合于采用遗传算法、神经网络等人工智能技术进行解决。国内外学者在此方面作了不少研究并取得一定的成果，但也存在一些问题。该文系统地综述了近年来软件测试数据智能化生成的研究和存在的问题，并对未来的发展进行了展望。     

Testability transformation based on equivalence of target statements

The application of genetic algorithms in automatically generating test data has become a research hotspot and produced many results in recent years. However, its applicability is limited in the presence of flag variables. This issue, known as the flag problem, has been studied by many researchers to date. We propose a novel method of testability transformation to tackle the flag problem. Different from traditional transformation methods, in our method, the key step is not the transformation of source code, but that of target statements. We search for a new target statement (or a set of target statements) equivalent to the original one and then transform the problem of generating test data that cover the original target statement into the one that cover the new target statement (or a set of target statements). We apply our method in many real-world programs, and the experimental results show its effectiveness.     

A Parallel Genetic Algorithm Based on Spark for Pairwise Test Suite Generation

Pairwise testing is an effective test generation technique that requires all pairs of parameter values to be covered by at least one test case. It has been proven that generating minimum test suite is an NP-complete problem. Genetic algorithms have been used for pairwise test suite generation by researchers. However, it is always a time-consuming process, which leads to significant limitations and obstacles for practical use of genetic algorithms towards large-scale test problems. Parallelism will be an effective way to not only enhance the computation performance but also improve the quality of the solutions. In this paper, we use Spark, a fast and general parallel computing platform, to parallelize the genetic algorithm to tackle the problem. We propose a two-phase parallelization algorithm including fitness evaluation parallelization and genetic operation parallelization. Experimental results show that our algorithm outperforms the sequential genetic algorithm and competes with other approaches in both test suite size and computational performance. As a result, our algorithm is a promising improvement of the genetic algorithm for pairwise test suite generation.     

Data Generation for Path Testing

We present two stochastic search algorithms for generating test cases that execute specified paths in a program. The two algorithms are: a simulated annealing algorithm (SA), and a genetic algorithm (GA). These algorithms are based on an optimization formulation of the path testing problem which include both integer- and real-value test cases. We empirically compare the SA and GA algorithms with each other and with a hill-climbing algorithm, Korel's algorithm (KA), for integer-value-input subject programs and compare SA and GA with each other on real-value subject programs. Our empirical work uses several subject programs with a number of paths. The results show that: (a) SA and GA are superior to KA in the number of executed paths, (b) SA tends to perform slightly better than GA in terms of the number of executed paths, and (c) GA is faster than SA; however, KA, when it succeeds in finding the solution, is the fastest.     

Automatic, evolutionary test data generation for dynamic software testing

This paper proposes a dynamic test data generation framework based on genetic algorithms. The framework houses a Program Analyser and a Test Case Generator, which intercommunicate to automatically generate test cases. The Program Analyser extracts statements and variables, isolates code paths and creates control flow graphs. The Test Case Generator utilises two optimisation algorithms, the Batch-Optimistic (BO) and the Close-Up (CU), and produces a near to optimum set of test cases with respect to the edge/condition coverage criterion. The efficacy of the proposed approach is assessed on a number of programs and the empirical results indicate that its performance is significantly better compared to existing dynamic test data generation methods.     

Evolutionary algorithms for the multi‐objective test data generation problem

Automatic test data generation is a very popular domain in the field of search‐based software engineering. Traditionally, the main goal has been to maximize coverage. However, other objectives can be defined, such as the oracle cost, which is the cost of executing the entire test suite and the cost of checking the system behavior. Indeed, in very large software systems, the cost spent to test the system can be an issue, and then it makes sense by considering two conflicting objectives: maximizing the coverage and minimizing the oracle cost. This is what we did in this paper. We mainly compared two approaches to deal with the multi‐objective test data generation problem: a direct multi‐objective approach and a combination of a mono‐objective algorithm together with multi‐objective test case selection optimization. Concretely, in this work, we used four state‐of‐the‐art multi‐objective algorithms and two mono‐objective evolutionary algorithms followed by a multi‐objective test case selection based on Pareto efficiency. The experimental analysis compares these techniques on two different benchmarks. The first one is composed of 800 Java programs created through a program generator. The second benchmark is composed of 13 real programs extracted from the literature. In the direct multi‐objective approach, the results indicate that the oracle cost can be properly optimized; however, the full branch coverage of the system poses a great challenge. Regarding the mono‐objective algorithms, although they need a second phase of test case selection for reducing the oracle cost, they are very effective in maximizing the branch coverage. Copyright © 2011 John Wiley & Sons, Ltd.     

Using genetic algorithms to generate test sequences for complex timed systems

The generation of test data for state-based specifications is a computationally expensive process. This problem is magnified if we consider that time constraints have to be taken into account to govern the transitions of the studied system. The main goal of this paper is to introduce a complete methodology, supported by tools, that addresses this issue by representing the test data generation problem as an optimization problem. We use heuristics to generate test cases. In order to assess the suitability of our approach we consider two different case studies: a communication protocol and the scientific application BIPS3D. We give details concerning how the test case generation problem can be presented as a search problem and automated. Genetic algorithms (GAs) and random search are used to generate test data and evaluate the approach. GAs outperform random search and seem to scale well as the problem size increases. It is worth to mention that we use a very simple fitness function that can be easily adapted to be used with other evolutionary search techniques.     

A tabu search algorithm for structural software testing

This paper presents a tabu search metaheuristic algorithm for the automatic generation of structural software tests. It is a novel work since tabu search is applied to the automation of the test generation task, whereas previous works have used other techniques such as genetic algorithms. The developed test generator has a cost function for intensifying the search and another for diversifying the search that is used when the intensification is not successful. It also combines the use of memory with a backtracking process to avoid getting stuck in local minima. Evaluation of the generator was performed using complex programs under test and large ranges for input variables. Results show that the developed generator is both effective and efficient.     

Detecting buffer overflow via automatic test input data generation

Buffer overflows cause serious problems in various categories of software systems. In critical systems, such as health-care, nuclear or aerospace software applications, a buffer overflow may cause severe threats to humans or severe economic losses. If they occur in network or security applications, they can be exploited to gain administrator privileges, perform system attacks, access unauthorized data, or misuse the system. This paper proposes a combination of genetic algorithms, linear programming, evolutionary testing, and static and dynamic information to detect buffer overflows. The newly proposed test input generation process avoids the need for human intervention to define and tune genetic algorithm weights and therefore it becomes completely automated. The process that guides the genetic search towards the detection of buffer overflow relies on a fitness function that takes into account static and dynamic information. Reported results of our case studies, consisting of two sets of open-source programs show that the new process and fitness function outperform previously published approaches.     

Fitting optimal piecewise linear functions using genetic algorithms

Constructing a model for data in R² is a common problem in many scientific fields, including pattern recognition, computer vision, and applied mathematics. Often little is known about the process which generated the data or its statistical properties. For example, in fitting a piecewise linear model, the number of pieces, as well as the knot locations, may be unknown. Hence, the method used to build the statistical model should have few assumptions, yet, still provide a model that is optimal in some sense. Such methods can be designed through the use of genetic algorithms. We examine the use of genetic algorithms to fit piecewise linear functions to data in R². The number of pieces, the location of the knots, and the underlying distribution of the data are assumed to be unknown. We discuss existing methods which attempt to solve this problem and introduce a new method which employs genetic algorithms to optimize the number and location of the pieces. Experimental results are presented which demonstrate the performance of our method and compare it to the performance of several existing methods, We conclude that our method represents a valuable tool for fitting both robust and nonrobust piecewise linear functions     

Planning exploration strategies for simultaneous localization and mapping

In this paper, we present techniques that allow one or multiple mobile robots to efficiently explore and model their environment. While much existing research in the area of Simultaneous Localization and Mapping (SLAM) focuses on issues related to uncertainty in sensor data, our work focuses on the problem of planning optimal exploration strategies. We develop a utility function that measures the quality of proposed sensing locations, give a randomized algorithm for selecting an optimal next sensing location, and provide methods for extracting features from sensor data and merging these into an incrementally constructed map.We also provide an efficient algorithm driven by our utility function. This algorithm is able to explore several steps ahead without incurring too high a computational cost. We have compared that exploration strategy with a totally greedy algorithm that optimizes our utility function with a one-step-look ahead.The planning algorithms which have been developed operate using simple but flexible models of the robot sensors and actuator abilities. Techniques that allow implementation of these sensor models on top of the capabilities of actual sensors have been provided.All of the proposed algorithms have been implemented either on real robots (for the case of individual robots) or in simulation (for the case of multiple robots), and experimental results are given.     

On the performance of multiple-objective genetic local search onthe 0/1 knapsack problem - a comparative experiment

Multiple-objective metaheuristics, e.g., multiple-objective evolutionary algorithms, constitute one of the most active fields of multiple-objective optimization. Since 1985, a significant number of different methods have been proposed. However, only few comparative studies of the methods were performed on large-scale problems. We continue two comparative experiments on the multiple-objective 0/1 knapsack problem reported in the literature. We compare the performance of two multiple-objective genetic local search (MOGLS) algorithms to the best performers in the previous experiments using the same test instances. The results of our experiment indicate that our MOGLS algorithm generates better approximations to the nondominated set in the same number of functions evaluations than the other algorithms     

通用代码Shell化技术研究

代码Shell化技术是一种实现程序从源码形态到二进制形态的程序变换技术。该技术可用于实现Shellcode生成,生成包括漏洞利用过程中的Shellcode及后渗透测试过程中的功能性Shellcode。文中形式化地描述了程序中代码与数据的关系,提出了一种基于LLVM(Low Level Virtual Machine)的通用程序变换方法,该方法可用于实现操作系统无关的代码Shell化。该技术通过构建代码内置全局数据表和添加动态重定位代码,将代码对数据的绝对内存地址访问转化为对代码内部全局数据表的相对地址访问,重构了代码与数据之间的引用关系,解决了代码执行过程中对操作系统重定位机制依赖的问题,使得生成的Shellcode代码具有位置无关特性。在验证实验中,使用适用于不同操作系统的不同规模的工程源码对基于该技术实现的Shellcode生成系统进行了功能测试,并对比了Shell化前后代码功能的一致性、文件大小、函数数量和运行时间,实验结果表明基于该技术的Shellcode生成系统功能正常,具有较好的兼容性和通用性。     

GA-based multiple paths test data generator

Developers have learned over time that software testing costs a considerable amount of a software project budget. Hence, software quality managers have been looking for solutions to reduce testing costs and time. Considering path coverage as the test adequacy criterion, we propose using genetic algorithms (GA) for automating the generation of test data for white-box testing. There are evidences that GA has been already successful in generating test data. However, existing GA-based test data generators suffer from some problems. This paper presents our approach to overcome one of these problems; that is the inefficiency in covering multiple target paths. We have designed a GA-based test data generator that is, in one run, able to synthesize multiple test data to cover multiple target paths. Moreover, we have implemented a set of variations of the generator. Experimental results show that our test data generator is more efficient and more effective than others.     

An investigation of mating and population maintenance strategies in hybrid genetic heuristics for product line designs

This research builds on prior work on developing near optimal solutions to the product line design problems within the conjoint analysis framework. In this research, we investigate and compare different genetic algorithm operators; in particular, we examine systematically the impact of employing alternative population maintenance strategies and mutation techniques within our problem context. Two alternative population maintenance methods, that we term “Emigration” and “Malthusian” strategies, are deployed to govern how individual product lines in one generation are carried over to the next generation. We also allow for two different types of reproduction methods termed “Equal Opportunity” in which the parents to be paired for mating are selected with equal opportunity and a second based on always choosing the best string in the current generation as one of the parents which is referred to as the “Queen bee”, while the other parent is randomly selected from the set of parent strings. We also look at the impact of integrating the artificial intelligence approach with a traditional optimization approach by seeding the GA with solutions obtained from a Dynamic Programming heuristic proposed by others. A detailed statistical analysis is also carried out to determine the impact of various problem and technique aspects on multiple measures of performance through means of a Monte Carlo simulation study. Our results indicate that such proposed procedures are able to provide multiple “good” solutions. This provides more flexibility for the decision makers as they now have the opportunity to select from a number of very good product lines. The results obtained using our approaches are encouraging, with statistically significant improvements averaging 5% or more, when compared to the traditional benchmark of the heuristic dynamic programming technique.     

Particle swarm optimization for determining fuzzy measures from data

Fuzzy measures and fuzzy integrals have been successfully used in many real applications. How to determine fuzzy measures is the most difficult problem in these applications. Though there have existed some methodologies for solving this problem, such as genetic algorithms, gradient descent algorithms and neural networks, it is hard to say which one is more appropriate and more feasible. Each method has its advantages and limitations. Therefore it is necessary to develop new methods or techniques to learn distinct fuzzy measures. In this paper, we make the first attempt to design a special particle swarm algorithm to determine a type of general fuzzy measures from data, and demonstrate that the algorithm is effective and efficient. Furthermore we extend this algorithm to identify and revise other types of fuzzy measures. To test our algorithms, we compare them with the basic particle swarm algorithms, gradient descent algorithms and genetic algorithms in literatures. In addition, for verifying whether our algorithms are robust in noisy-situations, a number of numerical experiments are conducted. Theoretical analysis and experimental results show that, for determining fuzzy measures, the particle swarm optimization is feasible and has a better performance than the existing genetic algorithms and gradient descent algorithms.     

Artificial immune systems for assembly sequence planning exploration

Assembly sequence planning (ASP) needs to take relevant constraint factors such as the geometric characteristics and tool factors into consideration so as to work out a particular assembly sequence. At last, a product will come into being through the assembly of each part according to the assembly sequence. A problem encountered in ASP is that a larger number of components will cause more constraints to assembly a product, thus increasing the complexity of assembly problem. Therefore, it has been an objective for researchers to look for suitable methods for the solution space of feasible solutions.Among them, traditional genetic algorithms (GAs) belong to a random searching method. When the constraints are complicated in ASP, GAs often come out with a large number of solutions not feasible. Consequently, previous research results have proposed some approaches such as Guided genetic algorithms (Guided-GAs) or memetic algorithms (MAs) to enhance the structure of GAs to cope with the complexity of constraints in ASP problems. In this study, artificial immune systems (AIS) were proposed to help solve the assembly sequence problem. In AIS algorithm, the antibody (Ab) in the immune system is simulated to encounter one or more unknown antigens (Ags). Moreover, the clonal selection concept is employed in the immune system in which a better antibody will be selected in each generation of revolution and different antibodies will be cloned to protect the infection of the original antigen. With this mechanism, the shortcoming such as the traditional GAs to converge in local optimal solution will be overcome. Practical examples have demonstrated that AIS can solve the ASP problem with complicated constraints. Compared with guided genetic algorithms and memetic algorithms, AIS can generate the same or better solutions in terms of quality and searching time.