Research on SEBASE at Bham involves different issues, e.g. study of fitness landscapes of software engineering problems, design and computational complexity analysis of search algorithms, or the
application and evaluation of innovative search strategies. At the moment, our attention is focused on the following topics:
This topic deals with the runtime analysis of EAs when used for tackling different software engineering problems. Our current research concentrates on the domain of conformance testing of finite state machines. Here, an essential problem is finding a unique input output sequence for a given state. Although this problem is known to be NP-hard, interesting instances where an EA outperforms a random search have been found. It is worth then to characterise the instances where a given EA performs either efficiently or poorly, likewise to identify the EAs that succeed or not for a given problem instance.
In this topic, we deal with the generation of test data for object oriented programmes. Currently, research is being undertaken on the fulfillment of branch coverage for unit testing of classes written in JAVA. The particularities of this problem make it specially hard, and sophisticated search strategies could be an appealing alternative. Work on this includes, but is not limited to, novel fitness functions design, the analysis of appropriate solution representations and search space reduction. Owing to the novelty of this research line, relatively little literature can be found, so that the application of search methods ranging from simple (e.g. local search) to advanced algorithms (e.g. memetic) is worth of study.
Our work on this topic is at the moment focused on the use of EDAs to generate test data for object oriented software. Besides good results in terms of performance, we believe an additional benefit EDAs may provide is the knowledge contained in the probability distribution associated to the search. Furthermore, the solution of this problem involves a number of appealing issues for the EDAs research community as, for example, holding constraints and managing variable length solution points, which might result in new algorithms.
We are currently investigating an evolutionary approach to automate the task of bug fixing. On one hand, programmes are evolved (e.g. by using genetic programming) with a fitness function that is based on the degree of success in passing a set of tests. At the moment, we focus on unit tests, though more sophisticated fitness functions could be designed. On the other hand, by using the formal specification of the programme as an oracle, different tests are generated with the aim of uncovering new faults. Eventually, a co-evolution between programmes and tests might take place, resulting in software with a high level of robustness.
Runtime analysis of evolutionary algorithms in software engineering problems
Evolutionary algorithms (EAs) have already been employed for solving hard software engineering problems in a number of works. In many of them, outstanding empirical results have been obtained, thus presenting EAs as a promising solution method. Further research is needed, however, to attain a deeper understanding of the behaviour of EAs in a particular problem. More precisely, in the previous works, there is a lack of theoretical studies, which are important in order to build a solid knowledge background.This topic deals with the runtime analysis of EAs when used for tackling different software engineering problems. Our current research concentrates on the domain of conformance testing of finite state machines. Here, an essential problem is finding a unique input output sequence for a given state. Although this problem is known to be NP-hard, interesting instances where an EA outperforms a random search have been found. It is worth then to characterise the instances where a given EA performs either efficiently or poorly, likewise to identify the EAs that succeed or not for a given problem instance.
Analysis of fitness landscapes arising from software engineering
As modern software systems grow larger and more complex, there is an increasing need to support the software engineer with better techniques. Recent research in the field of search based software engineering (SBSE) has demonstrated that a wide range of problems in software engineering that traditionally have been solved manually, can be reformulated as optimisation problems. Such a reformulation opens up the possibility of applying meta-heuristic search algorithms to automatically find good solutions to the original software engineering problem. This approach has been taken on SE problems from different stages in the software development cycle, including planning, design, testing and maintenance. The existing methodology in SBSE is predominately experimental. Such results often give inconclusive answers to fundamental questions in SBSE, e.g., which algorithm should be applied to a particular problem, and how to construct algorithms that are more suited to a particular problem? We need more in-depth studies into the characteristics of SE problems and appropriate algorithms to solve them.Application of Machine Learning techniques to software engineering problems
Application of advanced search strategies for testing object oriented software
Software testing is one of the software engineering fields where search methods have been most widely used. Even so, the bulk of the related works have focused on testing procedural software, overlooking the demands imposed by the increasing productivity of programmers and the complexity of modern systems. A clear case of such a lack of attention is object oriented programming, which is a usual paradigm for software development nowadays.In this topic, we deal with the generation of test data for object oriented programmes. Currently, research is being undertaken on the fulfillment of branch coverage for unit testing of classes written in JAVA. The particularities of this problem make it specially hard, and sophisticated search strategies could be an appealing alternative. Work on this includes, but is not limited to, novel fitness functions design, the analysis of appropriate solution representations and search space reduction. Owing to the novelty of this research line, relatively little literature can be found, so that the application of search methods ranging from simple (e.g. local search) to advanced algorithms (e.g. memetic) is worth of study.
Application of Estimation of Distribution Algorithms to software engineering problems
Estimation of distribution algorithms (EDAs) constitute a family of population-based search methods that currently deserve the attention of researchers. The main characteristic of EDAs is that, during the search, a probability distribution is explicitly kept and new points are sampled from it. EDAs have already been applied to the generation of test data for procedural software, offering encouraging results. The study of these methods in the context of new software engineering problems seems interesting then.Our work on this topic is at the moment focused on the use of EDAs to generate test data for object oriented software. Besides good results in terms of performance, we believe an additional benefit EDAs may provide is the knowledge contained in the probability distribution associated to the search. Furthermore, the solution of this problem involves a number of appealing issues for the EDAs research community as, for example, holding constraints and managing variable length solution points, which might result in new algorithms.
Automated bug fixing through evolutionary techniques
Software testing can take up to half of the resources of the development of new software. Although there has been a lot of work on automating the testing phase, fixing a bug after its presence has been discovered is still a duty of the programmers. Techniques to help the software developers for locating bugs exist, however, there has been only little attempt to completely automate the actual changing of the software for fixing the bugs.We are currently investigating an evolutionary approach to automate the task of bug fixing. On one hand, programmes are evolved (e.g. by using genetic programming) with a fitness function that is based on the degree of success in passing a set of tests. At the moment, we focus on unit tests, though more sophisticated fitness functions could be designed. On the other hand, by using the formal specification of the programme as an oracle, different tests are generated with the aim of uncovering new faults. Eventually, a co-evolution between programmes and tests might take place, resulting in software with a high level of robustness.