Key Concepts behind SBSE

Question:

How would you do the survey paper on search based software engineering, is it by referring to just the 4 technical papers I have uploaded or you would also consider other references ?

In this survey paper, there will be survey from literature on the topic search-based software engineering. This is a new type of software engineering techniques that introduces lots of automation and optimization process. It helps to cover wide range of solution search space. There are several key concepts behind the techniques of SBSE, in spite of having several benefits, still it is not able to get industry acceptance. All these issues will be discussed in the survey paper.

SBSE or Search based software engineering helps in implementing metaheuristic search approaches in different problems in the domain of software engineering. Some example of meta- heuristic approaches are tabu bearch, simulated annealing, genetic algorithm etc. (Harman, 2004)

From different cases, it has been observed that optimization can also help in software engineering. There are several problems in this domain that are computationally complex. There are traditional optimization techniques from operation research. These are also used in many instances. But, due to the increasing complexity of the software systems, these approaches are also becoming impractical in different cases. Search based software engineering has come into the picture from these difficulties from traditional software engineering optimization processes. (Freitas, Gomes, & Souza, 2011)

The main idea is to convert a software engineering problem into suitable computational search problem. Thus it is essentially a mapping approach. Meta- heuristic searches and optimization helps into dealing with the mapping process. (Harman, Mansouri, & Zhang, 2012)

There are different steps in this process. Those are,

1. Definition of the search space. This is the set of all possible solutions for the problem. A search space is usually a large space to explore. Hence, it is difficult to carry out exhaustive exploration.

2. Sampling the space with meta heuristic approaches.

3. A fitness function or metric is identified or created. This is also called quality measure or objective function or cost function. This is used for measurement of the quality of a solution. The solutions can be formulated as solutions of computational search problem or it can be reformulated into the some solution of computational search problem.

There are two classes of SBSE. Those are,

In this approach, different combinatorial optimization problems like assignment of tasks to resources, can be solved.

In these approach, optimization is carried out on the source codes. There are also, several methods to work with in this approach.

In 1976, David Spooner and Webb Miller, first introduced the concept of optimization in software engineering. They applied the same in software testing. During 1992, Xanthakis applied the concept in real software engineering problem for the first time. SBSE, the term was coined during 2001 by Harman and Jones. Thus, this is a relatively new field of study in software engineering. There have been many reaches and survey on the topic from different parts of the world. (Harman & Jones, 2001)

Applications of SBSE

There have been a wide range of tools and techniques that support SBSE to apply in different cases. For example EvoSuit, OpenPAT etc.

Also there are various methods. Some of the methods and techniques are,

• Instrumentation based profiling for monitoring some section of a program while execution.
• Gaining insight into the structure of a program by developing an abstract syntax tree.
• Program slicing and its application in software maintenance, program analysis and software optimization.
• Static program analysis process.
• Use of code coverage to measure the amount of executed code for some given range of input.

An extensive research on different techniques like classical techniques, meta- heuristic searches like hill climbing, genetic algorithm etc. have been describes in the paper by Harman (Harman, 2004). The author have shown almost all types of techniques used in SBSE. The paper is focused on the techniques only. The description of the techniques, hoe those are performed, the mathematical model behind the techniques etc. There is description of the techniques almost from the inception of the concept. There is also a set of future topics of research in the given topic that have been outlined in this paper.

Another algorithm KEYS2 has been described in the paper by (Gay, 2010) gives details of a real life application of SBSE. The KEYS2 algorithm is developed on a simple theory that use smaller number of variables and covers up most of the solution space. The variables are rapidly isolated in the search space and the stable solution starts to form. The paper also describes a case study for better understanding of the concept. Also, it shows a comparison of KEYS2 with other SBSE techniques and it shows that there is better performance with this one. So the author considers is a suitable baseline solution in SBSE.

In a software development process, SBSE can be applied to any phase of it. But in software testing SBSE is mostly applied. For other phases like requirement analysis, design, development, maintenance etc. SBSE can be applied also. The application of SBSE in these phases of software development process has been described as, , (Harman & Mansouri, , 2010)

In this process the requirements of the users and he environment from the proposed software solution, are identified and managed. Search based techniques can be used for optimizing the goals of finding the mostly suitable subset of requirements matching the requests of users, different constraints on resources etc. The problems are formulated as multiple criteria decision making problem and deals with searching the optimized solution y balancing the cost and level of satisfaction of the users.

In testing process, the SBSE techniques are mostly implemented. Some common application of SBSE in software testing are, automated generation of test cases, test data, minimization of the test cases, prioritization of the test cases etc. (Harman & Mansouri, , 2010), (McMinn, 2004).

Debugging and maintenance is another domain where SBSE has huge application. The techniques are used for finding bugs or code smell, refactoring or debugging code etc. Most of the techniques are white box approaches. In this phase SBSE helps in uncovering the bugs through automated processes like mutation testing. It can also help in fixing the bugs. (Di Penta, 2012)

A biologically inspired technique, called genetic programming, use crossover and mutation to find out repairs in the code of a program with the minimal number of code change.

Techniques and Methods

Another approach, called convolution, use population of unit tests, evolves the tests together and finds out the influences of the tests on one another. (Harman & Mansouri, , 2010)

Software optimization through SBSE can be done by changing some piece of code. It makes the software more efficient, faster and it consumes lesser resources. Again genetic programming is an example of such application.

Project scheduling, planning etc. can be done through the use of SBSE.

Some of the benefits of the SBSE techniques have been discussed in the paper by (Harman, Mansouri, & Zhang, 2012). The authors have explored volumes of works and researches. The benefits are,

The survey by (Harman, Mansouri, & Zhang, 2012) shows that one of the stricking benefit of the SBSE techniques is the applicability and generality of the techniques. The software testing is a pre-dominant field that has the maximum number of application of SBSE. Most of the paper discussed about this.

Two important component of SBSE is to consider here. Those are problem representation and fitness function.

In most of the software engineering applications, a consideration is the robustness of the functionalities of the solution. Locating an area from a search space having most of the part of the solution is more important than finding more number of weaker solutions.

SBSE can help in this issue. The automated tools and techniques may help to find out the most suitable solution from a solution space and the program will be robust.

Scalability of the software engineering solution is a serious consideration to the engineers. SBSE can also help in this case. There have need lots of works from many researchers and that shows good results.

One of the biggest risk and reason behind failure of most of the software projects is the false intuition. It may lead to consequences like poor communication, unclear specifications, implicit assumptions etc. These problems can be addressed effectively through SBSE. Human based search can be biased, but that is not the case with automated search. Automated search can fit into the pre-defined assumptions and consider the constraints of fitness function well.

SBSE is a relatively new field of research and application in software engineering. There is still miles to go before gaining broad industry acceptance. There are several issues to consider before being accepted widely. Some of those are,

• Software developer and engineers are accustomed with other approaches being used in the industry. Thus there is a resistance behind changing to some new idea.
• Most of the tools are automated. This saves effort, but software professionals do not like those really sometimes. Because there is least control on generation of results from the tools. And those are quite different from the ones developed by themselves.
• While improving or fixing some problems, there is very little scope to make the developers confident that the auto generated fixing solutions will not lead to some worse scenarios, there will be no unexpected behavior or the solution will go beyond the scope of the program (Harman, 2002).
• The solutions should be understandable to the human users. But there is no such property with SBSE yet, that can confirm such cases. So, there are chances that issues may raise during maintenance of the program. (Goues & Yoo, 2014)
• There may be redundancy in the process. There are arguments among the researchers in this context. These redundancies also helps in improving the involvement of software engineer in the programs.

Conclusion

In this survey paper, there is a survey from literature on the topic SBSE or Search Based Software Engineering. The topic is relatively new and now widespread. However, there have been increasing number of researches going on this topic. In this paper, survey from those paper have been included.

References

Di Penta, M. (2012). SBSE meets software maintenance: Achievements and open problems. Search Based Software Engineering , 27-28.

Freitas, d., Gomes, F., & Souza, J. T. (2011). Ten years of search based software engineering: A bibliometric analysis. Search Based Software Engineering, 18-32.

Gay, G. (2010). A baseline method for search-based software engineering. Proceedings of the 6th International Conference on Predictive Models in Software Engineering.

Goues, C. L., & Yoo, S. (2014). Search-based Software Engineering. Springer.

Harman, M. (2002). Automated test data generation using search based software engineering. In Automation of Software Test, 2007. AST’07. Second International Workshop on, 2-2.

Harman, M. (2004). The Current State and Future of Search Based Software Engineering. Future of Software Engineering IEEE, 342-357.

Harman, M., & Jones, B. F. (2001). Search-Based Software Engineering. Information and Software Technology, 833-839.

Harman, M., & Mansouri, A. (2010). Search Based Software Engineering: Introduction to the Special Issue of the IEEE Transactions on Software Engineering. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 737-741.

Harman, M., Mansouri, S. A., & Zhang, Y. (2012). Search Based Software Engineering: Trends, Techniques and Applications. ACM Computing Surveys.

McMinn, P. (2004). Searchâ€Âbased software test data generation: a survey. Software testing, Verification and reliability, 105-156.