Abstract:Automatic program repair helps developers reduce the cost of manual bug fixing. Approaches to test-suite based repair aim to generate code patches to pass the test suite as well as maintain the program execution. This paper reviews available literature on test-suite based repair and report the progress in two directions:Approaches to automatic repair and empirical foundations. First, existing approaches to automatic repair are described in three categories:Search based, exhaustion based, and constraint-solving based patch generation. Second, empirical foundations on repair are detailed, including the argumentation in the research field. Related techniques are then briefly introduced as the supplementation of program repair. Finally, opportunities and challenges are presented to summarize this review.

Abstract:The design of fitness function plays one of most important roles in search based test data generation. While in some special program structures, such as nested structure, unstructured jump statements, and return/break statements, the existing fitness functions can't evaluate all the branches. The currently used approaches are to change the source program so that the branches can be evaluated completely. Changing source program might not only affect the program structure and result in errors, but also be hard to implement automatically. To solve the problem, this paper presents an approach of test case generation based on combination of schema using particle swarm optimization. First, a definition called "schema" is presented for all the branches which are able to improve the fitness value, and the branch function of the schema is obtained, solving the problem of partial evaluation. Then, a crossover is designed to place search on all the individuals which have the minimum value of branch function of the schema. The crossover views each schema as a whole and combines all the schemata into a single individual, as a result the crossover can not only prevent schemata destroyed in the process of evolution, but also improve the fitness value of individuals because of the combination. Furthermore, a local search strategy is used for the best particle in each generation in the process of test case generation. Experiments on some benchmark programs and open source programs are performed. The experimental results show that the proposed approach has obvious advantages in average coverage and generations comparing with other methods.

Abstract:Path coverage testing is one of the most important software testing methods. This paper presents a process of using genetic algorithms to generate path coverage test data. When an individual traverses the node that might be contained in the unteachable paths(which are determined based on the correlation of conditional statements), the higher the probability the node exists in the unreachable paths, the higher degree of traversing the individual has; and, the individual with higher degree of traversing should be protected. The fitness function of genetic algorithms is designed based on the individual traversing degree, so the efficiency of generating test data is improved. The proposed method is applied to benchmark and industrial programs, and is compared with other methods. The experimental results show that the proposed method is efficient in generating test data for path coverage.

Abstract:Automatic generation of testing data is an important means for improving the efficiency of software testing. Focusing on the engineering practice of software testing, a fast automatic method is proposed to improve the efficiency of testing data generation.(1) A key-point path expression method is proposed to calculate the number of theoretical paths, and find the covered paths' neighbors;(2) Brief instrumented program is executed to get some testing data by using the testing data generated from random algorithm;(3) The theoretical paths are divided into three parts:Easy-Cover paths, hard-cover paths and infeasible paths;(4) According to the information of covered paths and their testing data, the data of hard-cover paths will be generated by genetic algorithm. Simulation experimental results show that the proposed method is efficient.

Abstract:It is a novel research direction in the field of software testing to generate test data using genetic algorithms for complex software. Traditional techniques of test data generation based on genetic algorithms need to run a program using each test datum as an input, so as to obtain its fitness value and as a result, they consume a large amount of executing time. In order to reduce the time consumption of running a program, this paper proposes a method of test data generation for path coverage based on neural networks. First, a neural network is trained using a certain amount of samples to simulate an individual's fitness value. Then, when generating test data by the genetic algorithm, an individual's fitness value is roughly estimated using the trained neural network. Finally, for individuals with good estimated fitness values, their precise fitness value are calculated by running the program. The experimental results show that this method can effectively reduce the time consumption of running a program, therefore improve the efficiency of test data generation.

Abstract:Regression testing is an important part of the iterative software development, and test data generation is the premise of regression testing. Traditional regression testing methods select a part of test data from existing ones, and generate a number of new test data, so as to verify the correctness of a program. However, these methods are prone to generate redundant test data, therefore reducing the efficiency of regression testing. This paper researches the problem of branch coverage for regression testing, makes full use of information on the path coverage from existing test data, and selects a certain number of paths to cover all the target branches. First, taking a set consisting of several paths as the decision variable, the least number of paths, the largest number of covered branches, and the least number of uncovered paths as the objectives, a 3-objective optimization model for the problem of selecting paths is established. Then, a strategy of evaluating an individual based on the importance of an objective is designed in solving the above model using genetic algorithm. Finally, test data required to generate is determined according to the relation between existing test data and the selected paths. The proposed method is applied to test six benchmark and industrial programs, and compared with other regression testing methods. The experimental results show that paths selected by the proposed method can cover more branches, with fewer test data required to generate and less time consumption for regression testing.

Abstract:Generation of covering arrays, which has been solved by many mathematical methods and greedy algorithms as well as search based algorithms, is one of significant problems in combinatorial testing. As an effective evolutionary search algorithm for solving combinatorial optimization problems, ant colony optimization has also been used to generate covering arrays. Existing research shows ant colony optimization suitable for generating general covering arrays, variable strength covering arrays and the prioritization of covering arrays. Unfortunately, compared with other methods, ant colony optimization doesn't have significant advantages. To further explore and mine the potential of ant colony optimization in generating covering arrays, this paper focuses on four levels of improvement:1) the integration of ant colony variants; 2) parameter tuning; 3) the adjustment of solution structure and the improvement of evolutionary strategy; 4) using parallel computing to save executing time. The experimental results show that ant colony optimization is much more effective in generating covering arrays after the improvements.

Abstract:Spectrum-Based fault localization techniques are attractive for their effectiveness, and previous works have demonstrated that they can assist programmers to locate faults automatically. However, most of them can only work better when there is single bug than multiple bugs. Other approaches, although partially successful on multiple faults problem, are complex and need more human intervention. To better address these problems, this paper proposes a new spectrum-based fault localization technique based on genetic algorithm, called GAMFal, which can locate multiple bugs effectively with less human intervention. First, the multiple bugs' localization is converted into a search based model and a candidate expression for multiple bugs' location is encoded as an individual binary string. Then, the new approach extends the Ochiai coefficient to calculate the suspiciousness value used by genetic algorithm as a fitness function to search for a best population composed by optimal fault location candidates with highest suspiciousness value, and converts the ranking list of candidates to a checking order of program entities. According to this order, programmers finally examine program entities to locate faults. An empirical study on Siemens suites and three Linux programs(gzip, grep and sed) is conducted to compare GAMFal with other spectrum-based approaches. The Friedman test and Least Significance Difference method are then carried out to investigate the statistical significance of any differences observed in the experiments. The result suggests that the proposed method outperforms other related techniques in some respects and is feasible with respect to running time.

Abstract:In large system production line configuration, manual configuration is inevitable and hence easy to introduce nonconformities where configuration data inputted by configuration engineers violate predefined constraints(also known as conformance constraints). For large system production lines, such as cyber physical system(CPS) product lines, there are usually hundreds and thousands of configurable parameters, hundreds of conformance constraints, and complicated dependencies among the conformance constraints. Thus it is very challenging to resolve nonconformities in an efficient manner. As a first step to address this challenge, an automated nonconformity resolving recommendation approach(Zen-Fix) was presented in the previous work by this research, which relies on multi-objective search and constraint solving techniques. To further improve the search efficiency in such interactive CPS configuration process, this paper proposes a novel algorithm called DeIBEA, which combines differential evolution with IBEA(indicator-based evolutionary algorithm), and distinguishes feasible solutions from infeasible ones, generating offspring through the differential operation. Integrating Zen-Fix with DeIBEA can recommend nonconformity-free yet optimal solutions to configuration engineers. The cost effectiveness of DeIBEA(in the context of Zen-Fix) is empirically evaluated with a real-world case study, in which a configuration process is simulated containing 10189 search problems. Results show that:(1) Zen-Fix with DeIBEA can provide nonconformity resolving recommendation automatically in a quite efficient way;(2) Compared with IBEA, DeIBEA performs significantly better in terms of both time performance and search performance.

Abstract:Current researches on SaaS(software as a service) optimization placement mostly assume that the types and number of virtual machines are constant in cloud environment, namely, the optimization placement is based on the restricted resource. However, in actual situation the types and number of virtual machines are unknown, and they need to been calculated according to the resource requirement of components deployed. To address the issue, from the view of SaaS providers, this paper proposes a new approach to SaaS optimization placement problem that not only is applied to initial deployment of SaaS, but also is applied to component dynamic deployment in the running phase of SaaS. A hybrid genetic and simulated annealing algorithm(HGSA) is used in this approach that combines the advantages of genetic algorithm and simulated annealing algorithm, and overcomes the problems of the premature of genetic algorithm and the lower convergence speed. Compared with the separated using of genetic algorithm and simulated annealing algorithm, the experimental results show that HGSA has higher quality in solving the problem of SaaS component optimization placements. The approach proposed in this paper will provide the support of theory and method for the large-scale application of SaaS service mode.

Abstract:Formal methods contribute to the fundamental improvement of software quality and reliability, but this methodology is often very expensive. A compromise is to select and apply formal methods to only a subset of key components of the software system. However, currently there are few effective approaches for such selection process. This paper proposes a 0-1 constrained programming model for selecting key components for formal development, which enables the use of metaheuristic search methods to effectively solve the selection problem. The paper also designs a discrete water wave optimization(WWO) algorithm for the problem. The application to a large-scale software system validates the effectiveness of the proposed problem model, and demonstrates that the WWO algorithm outperforms some other typical metaheuristic search methods.

Abstract:Test case prioritization is a type of technique that aims at searching for the test case execution sequence to find faults early based on the whole test case suite. This technique is flexible and barely can miss important test cases, which contributes much benefit to regression testing. Multi-objective test case prioritization, where evolutionary algorithms have been widely used, aims to find a test case execution sequence that suits multiple test criteria. However, the drawback of large computation cost of the algorithms can greatly reduce the value of industrial application. This article proposes a CPU+GPU heterogeneous Computing orientation based multi-objective test case prioritization technique that utilizes advanced general purpose graphic process unit(GPGPU) technique to accelerate the process of test case prioritization. In experiment based on parallel structure, the sequential based parallel fitness and crossover operation computation is designed on NSGA-II and at last achieves 30 times speed-up rate on a well-known industrial open source project. Based on the systematic study on the benefit of different types of parallel strategies, a CPU+GPU heterogeneous computing framework is proposed and a prototype of tools is developed and available online.

Abstract:The failure of safety-critical software could result in death, injury and damage to people or loss of equipment or property. Therefore, it is important to evaluate whether software trustworthiness fulfills the user needs(i.e., trustworthiness evaluation). This paper first compares the definition of software trustworthiness and its evaluation. Then, it surveys the software trustworthiness evaluation from three different aspects:Standards, models, and CASE tools. This work studies these aspects from the view of domain-independent as well as domain-dependent. In summary, there is great progress being made for software trustworthiness evaluation theoretically and practically while its universality and scalability are still need to be improved.

Abstract:Software defined networking(SDN) facilitates rapid and open innovation by decoupling the control plane from the data plane, thus enabling high degree of openness and programmability in network protocols and applications. However, the dynamism of programmable networks also introduces new security challenges, which limit the large-scale application of SDN in many places. This paper presents a comprehensive survey on the security of SDN. First, SDN architecture and the security model of SDN are reviewed. Next, typical security threats and security issues of SDN are summarized and classified from the following two aspects:SDN specific and non-specific threats, and the security issues associated with the SDN framework. Then an in-depth analysis is provided on the latest developments in how to build a secure and dependable SDN from the following six aspects:Building a secure SDN controller or network operating system, the modular composable security services for SDN, DoS/DDoS flooding attack prevention and detection for SDN controllers, conflict resolutions and consistency resolutions for flow rules in SDN, the security of northbound application programming interface(API), and the security of applications in SDN. Finally, a brief analysis of the standardization work on SDN security is provided, along with a discussion on future research trends in building more secured SDN.

Abstract:Software defined networking(SDN) is a research trend as it decouples the control plane from the data plane. SDN applications are essential since they can be used to make the network simple to manage, flexible, more secure and more powerful. Northbound Interface is the communication interface between the controller and applications, it plays an important role in the process of the research and development of SDN. The state of the art of the programming languages in the SDN Northbound Interface is surveyed in this paper. It first summarizes the research background of the programming languages in the Northbound Interface. By classifying these languages into different categories according to their abstraction, programming model, implementation mechanisms and whether introducing new features, the study analyzes the key characteristic and language structure in each category. Incorporating with application scenarios in SDN, this paper compares the advantages and disadvantages of each language, and at the end discusses the future research trend.

Abstract:The development of computer hardware technology has led to an era of multi-core CPU. However, data structures, as the core of the software, are traditionally designed in line with single-core CPU and ordered sequence principle. Operating on the shared-memory multicore, a large number of concurrent running threads alternately modify the data structure, which brings big challenges. This paper surveys researches on multi-core data structure in shared-memory. First, the paper compares the differences between the concurrent and parallel data structures, and investigates the multicore structure classification characteristics based on progress condition. Then it reviews academic research on various types of concurrent data structures in recent years. Based on the findings, this paper summarizes the key technologies of concurrent data structure, and explains the design and development process as well as correctness verification of concurrent data structures. Finally, it discusses research prospects.

Abstract:Cloud computing is leading a revolution in computer science. However at the meantime, the large-scale ecosystem of cloud infrastructure brings about the problem of huge energy consumption. Therefore, the energy consumption management has been a research hotspot in recent years and to a large extent, the sustainable development of cloud computing has been tightly associated with the techniques of energy consumption measurement and management. Furthermore, the technique of power measurement in cloud environment is the foundation for the building of energy models as well as the evaluation of resource scheduling algorithms. In this paper, based on a survey of a wide range of methods measuring energy consumption of VMs, hosts or the whole system, four effective approaches that are widely applied in cloud system are addressed. The approaches include direct measuring techniques based on hardware or software, energy consumption estimate based on energy model, energy consumption measurement under virtualized environment, and energy consumption assessment based on simulation technology respectively. The paper analyzes and compares the advantages, drawbacks and best-fit situations of these methods. In addition, it discusses and points out the trends of future researches on energy management. These trends include smart power supply module, application type oriented energy consumption models, energy consumption model designed for mixed workloads, efficient cloud simulation toolkit for dynamic management, energy management in dynamic heterogeneous distributed cluster, energy preservation with resources scheduling towards tasks processing big data, and power provision scheduling with green energy.

Abstract:This paper presents AppISO, a novel approach to provide whole-application protection in an untrusted operating system(OS). Unlike previous virtualization-based approach, AppISO does not directly use any higher privilege hypervisor for application protection, which is known to cause high overhead due to frequent privilege transitions. Instead, AppISO introduces a software component named Inner TCB running in the same privilege layer with the untrusted OS, and uses Inner TCB to realize application protection. Meanwhile AppISO leverages hardware virtualization and software techniques such as page table lockdown, shadow IDT, and transition page to guarantee the security and isolation of Inner TCB. This paper proves that Inner TCB can achieve the same level of security as hypervisor, and experimental results show that the presented approach has significant improvement in performance.