Search-based software engineering
   HOME

TheInfoList



OR:

Search-based software engineering (SBSE) applies
metaheuristic In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimizati ...
search techniques such as
genetic algorithms In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
,
simulated annealing Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. ...
and
tabu search Tabu search is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989. Local (neighborhood) searches take a potential solution to a pro ...
to
software engineering Software engineering is a systematic engineering approach to software development. A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...
problems. Many activities in
software engineering Software engineering is a systematic engineering approach to software development. A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...
can be stated as
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
problems.
Optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
techniques of
operations research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...
such as linear programming or
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
are often impractical for large scale
software engineering Software engineering is a systematic engineering approach to software development. A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...
problems because of their computational complexity or their assumptions on the problem structure. Researchers and practitioners use
metaheuristic In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimizati ...
search techniques, which impose little assumptions on the problem structure, to find near-optimal or "good-enough" solutions. SBSE problems can be divided into two types: * black-box optimization problems, for example, assigning people to tasks (a typical
combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
problem). * white-box problems where operations on source code need to be considered.


Definition

SBSE converts a software engineering problem into a computational search problem that can be tackled with a
metaheuristic In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimizati ...
. This involves defining a search space, or the set of possible solutions. This space is typically too large to be explored exhaustively, suggesting a
metaheuristic In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimizati ...
approach. A metric (also called a fitness function, cost function, objective function or quality measure) is then used to measure the quality of potential solutions. Many software engineering problems can be reformulated as a computational search problem. The term "
search-based application Search-based applications are software applications in which a search engine platform is used as the core infrastructure for information access and reporting. Search-based applications use semantic technologies to aggregate, normalize and classi ...
", in contrast, refers to using search-engine technology, rather than search techniques, in another industrial application.


Brief history

One of the earliest attempts to apply
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
to a
software engineering Software engineering is a systematic engineering approach to software development. A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...
problem was reported by
Webb Miller Webb Colby Miller (born 1943) is a professor in the Department of Biology and the Department of Computer Science and Engineering at The Pennsylvania State University. Education Miller attended Whitman College, and received his Ph.D. in mathemati ...
and David Spooner in 1976 in the area of
software testing Software testing is the act of examining the artifacts and the behavior of the software under test by validation and verification. Software testing can also provide an objective, independent view of the software to allow the business to apprecia ...
. In 1992, S. Xanthakis and his colleagues applied a search technique to a
software engineering Software engineering is a systematic engineering approach to software development. A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...
problem for the first time. The term SBSE was first used in 2001 by Harman and Jones. The research community grew to include more than 800 authors by 2013, spanning approximately 270 institutions in 40 countries.


Application areas

Search-based software engineering is applicable to almost all phases of the software development process.
Software testing Software testing is the act of examining the artifacts and the behavior of the software under test by validation and verification. Software testing can also provide an objective, independent view of the software to allow the business to apprecia ...
has been one of the major applications. Search techniques have been applied to other
software engineering Software engineering is a systematic engineering approach to software development. A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...
activities, for instance,
requirements analysis In systems engineering and software engineering, requirements analysis focuses on the tasks that determine the needs or conditions to meet the new or altered product or project, taking account of the possibly conflicting requirements of the ...
,
design A design is a plan or specification for the construction of an object or system or for the implementation of an activity or process or the result of that plan or specification in the form of a prototype, product, or process. The verb ''to design' ...
,
refactoring In computer programming and software design, code refactoring is the process of restructuring existing computer code—changing the '' factoring''—without changing its external behavior. Refactoring is intended to improve the design, structu ...
,
development Development or developing may refer to: Arts *Development hell, when a project is stuck in development *Filmmaking, development phase, including finance and budgeting *Development (music), the process thematic material is reshaped * Photograph ...
, and
maintenance Maintenance may refer to: Biological science * Maintenance of an organism * Maintenance respiration Non-technical maintenance * Alimony, also called ''maintenance'' in British English * Champerty and maintenance, two related legal doct ...
.


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 user requests amid constraints such as limited resources and interdependencies between requirements. This problem is often tackled as a multiple-criteria decision-making problem and, generally involves presenting the decision maker with a set of good compromises between cost and user satisfaction as well as the requirements risk.


Debugging and maintenance

Identifying a software bug (or a
code smell In computer programming, a code smell is any characteristic in the source code of a program that possibly indicates a deeper problem. Determining what is and is not a code smell is subjective, and varies by language, developer, and development meth ...
) and then debugging (or
refactoring In computer programming and software design, code refactoring is the process of restructuring existing computer code—changing the '' factoring''—without changing its external behavior. Refactoring is intended to improve the design, structu ...
) the software is largely a manual and labor-intensive endeavor, though the process is tool-supported. One objective of SBSE is to automatically identify and fix bugs (for example via
mutation testing Mutation testing (or ''mutation analysis'' or ''program mutation'') is used to design new software tests and evaluate the quality of existing software tests. Mutation testing involves modifying a program in small ways. Each mutated version is call ...
).
Genetic programming In artificial intelligence, genetic programming (GP) is a technique of evolving programs, starting from a population of unfit (usually random) programs, fit for a particular task by applying operations analogous to natural genetic processes to t ...
, a biologically-inspired technique that 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. Th
GenProg Evolutionary Program Repair
software repaired 55 out of 105 bugs for approximately $8 each in one test. Coevolution adopts a "predator and prey"
metaphor A metaphor is a figure of speech that, for rhetorical effect, directly refers to one thing by mentioning another. It may provide (or obscure) clarity or identify hidden similarities between two different ideas. Metaphors are often compared wi ...
in which a suite of programs and a suite of unit tests evolve together and influence each other.


Testing

Search-based software engineering has been applied to software testing, including automatic generation of test cases (test data), test case minimization and test case prioritization.
Regression testing Regression testing (rarely, ''non-regression testing'') is re-running functional and non-functional tests to ensure that previously developed and tested software still performs as expected after a change. If not, that would be called a '' regre ...
has also received some attention.


Optimizing software

The use of SBSE in
program optimization In computer science, program optimization, code optimization, or software optimization, is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources. In general, a computer program may be o ...
, or modifying a piece of software to make it more efficient in terms of speed and resource use, has been the object of successful research. In one instance, a 50,000 line program was genetically improved, resulting in a program 70 times faster on average. A recent work by Basios et al. shows that by optimising the data structure, Google Guava found 9% improvement on execution time, 13% improvement on memory consumption and 4% improvement on CPU usage separately.


Project management

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


Tools

Tools available for SBSE include OpenPAT,
EvoSuite EvoSuite is a tool that automatically generates unit tests for Java software. EvoSuite uses an evolutionary algorithm to generate JUnit tests. EvoSuite can be run from the command line, and it also has plugins to integrate it in Maven, Intelli ...
, an
Coverage
a code coverage measurement tool for Python.


Methods and techniques

A number of methods and techniques are available, including: * Profiling via
instrumentation Instrumentation a collective term for measuring instruments that are used for indicating, measuring and recording physical quantities. The term has its origins in the art and science of scientific instrument-making. Instrumentation can refer to ...
in order to monitor certain parts of a program as it is executed. * Obtaining an
abstract syntax tree In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurr ...
associated with the program, which can be automatically examined to gain insights into its structure. * Applications of program slicing relevant to SBSE include software maintenance,
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
and
program analysis In computer science, program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness. Program analysis focuses on two major areas: program op ...
. *
Code coverage In computer science, test coverage is a percentage measure of the degree to which the source code of a program is executed when a particular test suite is run. A program with high test coverage has more of its source code executed during testing, ...
allows measuring how much of the code is executed with a given set of input data. *
Static program analysis In computer science, static program analysis (or static analysis) is the analysis of computer programs performed without executing them, in contrast with dynamic program analysis, which is performed on programs during their execution. The term ...


Industry acceptance

As a relatively new area of research, SBSE does not yet experience broad industry acceptance. Successful applications of SBSE in the industry can mostly be found within software testing, where the capability to automatically generate random test inputs for uncovering bugs at a big scale is attractive to companies. In 2017,
Facebook Facebook is an online social media and social networking service owned by American company Meta Platforms. Founded in 2004 by Mark Zuckerberg with fellow Harvard College students and roommates Eduardo Saverin, Andrew McCollum, Dustin Mosk ...
acquired the software startup Majicke Limited that developed Sapienz, a search-based bug finding app. In other application scenarios, software engineers may be reluctant to adopt tools over which they have little control or that generate solutions that are unlike those that humans produce. 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 support maintenance activities. Another concern is that SBSE might make the software engineer redundant. Supporters claim that the motivation for SBSE is to enhance the relationship between the engineer and the program.


See also

*
Program analysis (computer science) In computer science, program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness. Program analysis focuses on two major areas: program op ...
*
Dynamic program analysis Dynamic program analysis is the analysis of computer software that is performed by executing programs on a real or virtual processor. For dynamic program analysis to be effective, the target program must be executed with sufficient test inputs ...
* Genetic improvement


References

{{reflist, colwidth=30em


External links


Repository of publications on SBSEMetaheuristics and Software Engineering Software-artifact Infrastructure RepositoryInternational Conference on Software EngineeringGenetic and Evolutionary Computation (GECCO)Google Scholar page on Search-based software engineering
Computer-related introductions in 2001 Software testing Search algorithms Optimization algorithms and methods Genetic algorithms Software quality Program analysis