Search-based software engineering

From Wikipedia, the free encyclopedia

Search-based software engineering (SBSE) is an approach to apply metaheuristic search techniques like genetic algorithms, simulated annealing and tabu search to software engineering problems. It is inspired by the observation that many activities in software engineering can be formulated as optimization problems. Due to the computational complexity of these problems, exact optimization techniques of operations research like linear programming or dynamic programming are mostly impractical for large scale software engineering problems. Because of this, researchers and practitioners have used metaheuristic search techniques to find near optimal or good-enough solutions.

Broadly speaking SBSE problems can be divided into two types. The first is of the type black-box optimization, for example, assigning people to tasks (a typical combinatorial optimization problem). With this sort of problem domain, the underlying problem could have come from the software industry, but equally it could have originated from any domain where people are assigned to tasks. The second type are white-box problems where operations on source code need to be considered.[1]

Definition

The basic idea of SBSE is to take a software engineering problem and convert it into a computational search problem which can be tackled with a metaheuristic. This essentially involves a number of stages. Firstly defining a search space (the set of possible solutions to the problem). This space is typically too large to be explored exhaustively and therefore a metaheuristic is employed to sample this space. Secondly, a metric [2] (also called a fitness function, cost function, objective function or quality measure) is used to measure the quality of a potential solution. Many software engineering problems can be reformulated as a computational search problem.[3]

The term Search-based application, in contrast, refers to using search engine technology, rather than search techniques, in another industrial application.

Brief history

One of the earliest attempts in applying optimization to a software engineering problem was reported by Webb Miller and David Spooner in 1976 in the area of software testing.[4] In 1992, Xanthakis and his colleagues applied a search technique to a software engineering problem for the first time.[5] The term SBSE was first used in 2001 by Harman and Jones.[6] Since then, the research community has grown to include more than 800 authors in 2013, from approximately 270 institutions in 40 countries.[citation needed]

Application areas

SBSE is applicable to almost all phases of the software development process. Software testing has been one of the major applications of search techniques in software engineering.[7] Search techniques have also been applied to other software engineering activities, for instance requirements analysis,[8] [9] software design,[10] software development,[11] and software maintenance.[12]

Requirements Engineering

Requirements engineering is the process by which the needs of a software's users and environment are determined and managed. Search-based methods have been used for requirements selection and optimisation with the goal of finding the best possible subset of requirements that matches users' requests and different constraints such as limited resources and interdependencies between requirements. This problem is often tackled as a multiple-criteria decision-making problem and, roughly speaking, involves presenting the decision maker with a range of good compromises between cost and user satisfaction.[13] [14]

Debugging and Maintenance

Identifying a software bug (or a code smell) and then debugging (or refactoring) the software is largely a manual and labor intensive endeavor, though the process is supported by a number of tools. One objective of SBSE is to automatically identify bugs (for example via mutation testing), then automatically fix them.

Genetic Programming, a biologically-inspired technique which involves evolving programs through the use of crossover and mutation, has been used to search for repairs to programs by altering a few lines of source code. The GenProg Evolutionary Program Repair software was shown to be able to repair 55 out of 105 bugs for approximately $8 each.[15]

Coevolution has also been used as an approach. It follows a predator and prey metaphor where a population of programs and a population of unit tests evolve together and influence each other.[16]

Testing

SBSE has been applied to software testing, including automatic generation of test cases (test data), test case minimization and test case prioritization. Regression testing has also received some attention.

Optimizing Software

The use of SBSE in program optimization, or modifying a piece of software to make it more efficient in terms of speed and resource use, has been the object of developing research interest and success. Genetic Programming has been used to improve programs. In one instance, a 50,000 line program was genetically improved, resulting in a program 70 times faster on average.[17]

Project Management

A number of decisions which are normally made by a project manager can be done automatically, for example, project scheduling.[18]

Tools

There are a number of tools available for SBSE approaches. These include tools like OpenPAT.[19]

Methods and Techniques

There are a number of methods and techniques available. A non-exhaustive list of these tools includes

One method of profiling [20] is via instrumentation in order to monitor certain parts of a program as it is executed.

A different approach is obtaining an abstract syntax tree associated with the program, which can be automatically examined to gain insights into the structure of a program.

Applications of program slicing relevant to SBSE include software maintenance, optimization, program analysis.

Code coverage allows us to measure how much of the code is executed with a given set of input data.

Static program analysis

Industry Acceptance

As a relatively new area of research, SBSE does not yet benefit from broad industry acceptance. One issue is that software engineers are reluctant to adopt tools over which they have little control or that generate solutions that are quite different from the ones humans would produce.[21] In the context of SBSE use in fixing or improving programs, developers need to be confident that any automatically produced modification does not generate unexpected behavior outside the scope of a system's requirements and testing environment. Considering that fully automated programming has yet to be achieved, a desirable property of such modifications would be that they need to be easily understood by humans to favor program maintainability.[22]

Another concern is that SBSE might make the software engineer redundant. Researchers have argued that, on the contrary, the motivation for SBSE is to enhance the relationship between the engineer and the program.[23]

See also

References

  1. ↑ Harman, Mark (2010). "Why Source Code Analysis and Manipulation Will Always be Important". 10th IEEE Working Conference on Source Code Analysis and Manipulation (SCAM 2010). 10th IEEE Working Conference on Source Code Analysis and Manipulation (SCAM 2010). pp. 7–19. doi:10.1109/SCAM.2010.28. 
  2. ↑ Harman, Mark; John A. Clark (2004). "Metrics are fitness functions too". Proceedings of the 10th International Symposium on Software Metrics, 2004. 10th International Symposium on Software Metrics, 2004. pp. 58–69. doi:10.1109/METRIC.2004.1357891. 
  3. ↑ Clark, John A.; Dolado, José Javier; Harman, Mark; Hierons, Robert M.; Jones, Bryan F.; Lumkin, M.; Mitchell, Brian S.; Mancoridis, Spiros; Rees, K.; Roper, Marc; Shepperd, Martin J. (2003). "Reformulating software engineering as a search problem". IEE Proceedings - Software 150 (3): 161–175. doi:10.1049/ip-sen:20030559. ISSN 1462-5970. 
  4. ↑ Miller, Webb; Spooner, David L. (1976). "Automatic Generation of Floating-Point Test Data". IEEE Transactions on Software Engineering SE–2 (3): 223–226. doi:10.1109/TSE.1976.233818. ISSN 0098-5589. 
  5. ↑ S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas and K. Karapoulios, "Application of genetic algorithms to software testing," in Proceedings of the 5th International Conference on Software Engineering and its Applications, Toulouse, France, 1992, pp. 625–636
  6. ↑ Harman, Mark; Jones, Bryan F. (2001-12-15). "Search-based software engineering". Information and Software Technology 43 (14): 833–839. doi:10.1016/S0950-5849(01)00189-6. ISSN 0950-5849. Retrieved 2013-10-31. 
  7. ↑ McMinn, Phil (2004). "Search-based software test data generation: a survey". Software Testing, Verification and Reliability 14 (2): 105–156. doi:10.1002/stvr.294. ISSN 1099-1689. Retrieved 2013-10-31. 
  8. ↑ Greer, Des; Ruhe, Guenther (2004-03-15). "Software release planning: an evolutionary and iterative approach". Information and Software Technology 46 (4): 243–253. doi:10.1016/j.infsof.2003.07.002. ISSN 0950-5849. Retrieved 2013-09-06. 
  9. ↑ Colares, Felipe; Souza, Jerffeson; Carmo, Raphael; Pádua, Clarindo; Mateus, Geraldo R. (2009). "A New Approach to the Software Release Planning". XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09. XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09. pp. 207–215. doi:10.1109/SBES.2009.23. 
  10. ↑ Clark, John A.; Jacob, Jeremy L. (2001-12-15). "Protocols are programs too: the meta-heuristic search for security protocols". Information and Software Technology 43 (14): 891–904. doi:10.1016/S0950-5849(01)00195-1. ISSN 0950-5849. Retrieved 2013-10-31. 
  11. ↑ Alba, Enrique; Chicano, J. Francisco (2007-06-01). "Software project management with GAs". Information Sciences 177 (11): 2380–2401. doi:10.1016/j.ins.2006.12.020. ISSN 0020-0255. Retrieved 2013-10-31. 
  12. ↑ Antoniol, Giuliano; Di Penta, Massimiliano; Harman, Mark (2005). "Search-based techniques applied to optimization of project planning for a massive maintenance project". Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05. Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05. pp. 240–249. doi:10.1109/ICSM.2005.79. 
  13. ↑ Zhang, Yuanyuan (February 2010). Multi-Objective Search-based Requirements Selection and Optimisation (Ph.D.). Strand, London, UK: University of London. 
  14. ↑ Y. Zhang and M. Harman and S. L. Lim, "Search Based Optimization of Requirements Interaction Management," Department of Computer Science, University College London, Research Note RN/11/12, 2011.
  15. ↑ Le Goues, Claire; Dewey-Vogt, Michael; Forrest, Stephanie; Weimer, Westley (2012). "A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each". 2012 34th International Conference on Software Engineering (ICSE). 2012 34th International Conference on Software Engineering (ICSE). pp. 3–13. doi:10.1109/ICSE.2012.6227211. 
  16. ↑ Arcuri, Andrea; Yao, Xin (2008). "A novel co-evolutionary approach to automatic software bug fixing". IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). pp. 162–168. doi:10.1109/CEC.2008.4630793. 
  17. ↑ Langdon, William B.; Harman, Mark. "Optimising Existing Software with Genetic Programming". IEEE Transactions on Evolutionary Computation. 
  18. ↑ Minku, Leandro L.; Sudholt, Dirk; Yao, Xin (2012). "Evolutionary algorithms for the project scheduling problem: runtime analysis and improved design". Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference. GECCO '12. New York, NY, USA: ACM. pp. 1221–1228. doi:10.1145/2330163.2330332. ISBN 978-1-4503-1177-9. Retrieved 2013-10-31. 
  19. ↑ Mayo, M.; Spacey, S. (2013). "Predicting Regression Test Failures Using Genetic Algorithm-Selected Dynamic Performance Analysis Metrics" (PDF). Proceedings of the 5th International Symposium on Search-Based Software Engineering (SSBSE) 8084: 158–171. 
  20. ↑ http://java-source.net/open-source/profilers
  21. ↑ Jones, Derek (18 October 2013). "Programming using genetic algorithms: isn’t that what humans already do ;-)". The Shape of Code. Retrieved 31 October 2013. 
  22. ↑ Le Goues, Claire; Forrest, Stephanie; Weimer, Westley (2013-09-01). "Current challenges in automatic software repair". Software Quality Journal 21 (3): 421–443. doi:10.1007/s11219-013-9208-0. ISSN 1573-1367. Retrieved 2013-10-31. 
  23. ↑ Simons, Christopher L. (May 2013). "Whither (away) software engineers in SBSE?". First International Workshop on Combining Modelling with Search-Based Software Engineering,First International Workshop on Combining Modelling with Search-Based Software Engineering. San Francisco, USA: IEEE Press. pp. 49–50. Retrieved 2013-10-31. 

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.