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, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an op ...
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 g ...
,
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 (TS) 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 ...
to
software engineering Software engineering is a branch of both computer science and engineering focused on designing, developing, testing, and maintaining Application software, software applications. It involves applying engineering design process, engineering principl ...
problems. Many activities in
software engineering Software engineering is a branch of both computer science and engineering focused on designing, developing, testing, and maintaining Application software, software applications. It involves applying engineering design process, engineering principl ...
can be stated as
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
problems.
Optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
techniques of
operations research Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...
such as
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
or dynamic programming are often impractical for large scale
software engineering Software engineering is a branch of both computer science and engineering focused on designing, developing, testing, and maintaining Application software, software applications. It involves applying engineering design process, engineering principl ...
problems because of their
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
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, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an op ...
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 combina ...
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, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an op ...
. 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, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an op ...
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", in contrast, refers to using
search-engine technology A search engine is a software system that provides hyperlinks to web pages, and other relevant information on the Web in response to a user's query. The user enters a query in a web browser or a mobile app, and the search results are typically ...
, 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 criteria, from some set of available alternatives. It is generally divided into two subfiel ...
to a
software engineering Software engineering is a branch of both computer science and engineering focused on designing, developing, testing, and maintaining Application software, software applications. It involves applying engineering design process, engineering principl ...
problem was reported by
Webb Miller Webb Colby Miller (born 1943) is an American bioinformatician who is 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 David Spooner in 1976 in the area of
software testing Software testing is the act of checking whether software satisfies expectations. Software testing can provide objective, independent information about the Quality (business), quality of software and the risk of its failure to a User (computin ...
. In 1992, S. Xanthakis and his colleagues applied a search technique to a
software engineering Software engineering is a branch of both computer science and engineering focused on designing, developing, testing, and maintaining Application software, software applications. It involves applying engineering design process, engineering principl ...
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 In software engineering, a software development process or software development life cycle (SDLC) is a process of planning and managing software development. It typically involves dividing software development work into smaller, parallel, or s ...
.
Software testing Software testing is the act of checking whether software satisfies expectations. Software testing can provide objective, independent information about the Quality (business), quality of software and the risk of its failure to a User (computin ...
has been one of the major applications. Search techniques have been applied to other
software engineering Software engineering is a branch of both computer science and engineering focused on designing, developing, testing, and maintaining Application software, software applications. It involves applying engineering design process, engineering principl ...
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 v ...
,
design A design is the concept or proposal for an object, process, or system. The word ''design'' refers to something that is or has been intentionally created by a thinking agent, and is sometimes used to refer to the inherent nature of something ...
,
refactoring In computer programming and software design, code refactoring is the process of restructuring existing source code—changing the '' factoring''—without changing its external behavior. Refactoring is intended to improve the design, structure, ...
,
development Development or developing may refer to: Arts *Development (music), the process by which thematic material is reshaped * Photographic development *Filmmaking, development phase, including finance and budgeting * Development hell, when a proje ...
, and
maintenance The technical meaning of maintenance involves functional checks, servicing, repairing or replacing of necessary devices, equipment, machinery, building infrastructure and supporting utilities in industrial, business, and residential installa ...
.


Requirements engineering

Requirements engineering Requirements engineering (RE) is the process of defining, documenting, and maintaining requirements in the engineering design process. It is a common role in systems engineering and software engineering. The first use of the term ''requiremen ...
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 A software bug is a design defect ( bug) in computer software. A computer program with many or serious bugs may be described as ''buggy''. The effects of a software bug range from minor (such as a misspelled word in the user interface) to sev ...
(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 met ...
) and then
debugging In engineering, debugging is the process of finding the Root cause analysis, root cause, workarounds, and possible fixes for bug (engineering), bugs. For software, debugging tactics can involve interactive debugging, control flow analysis, Logf ...
(or
refactoring In computer programming and software design, code refactoring is the process of restructuring existing source code—changing the '' factoring''—without changing its external behavior. Refactoring is intended to improve the design, structure, ...
) 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 ca ...
).
Genetic programming Genetic programming (GP) is an evolutionary algorithm, an artificial intelligence technique mimicking natural evolution, which operates on a population of programs. It applies the genetic operators selection (evolutionary algorithm), selection a ...
, 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 In biology, coevolution occurs when two or more species reciprocally affect each other's evolution through the process of natural selection. The term sometimes is used for two traits in the same species affecting each other's evolution, as well a ...
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 usually meant to cr ...
in which a suite of programs and a suite of
unit tests Unit testing, component or module testing, is a form of software testing by which isolated source code is tested to validate expected behavior. Unit testing describes tests that are run at the unit-level to contrast testing at the integration ...
evolve together and influence each other.


Testing

Search-based software engineering has been applied to software testing, including the 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 '' regr ...
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 op ...
, 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 a 9% improvement in execution time, 13% improvement in memory consumption and 4% improvement in 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, 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 is a collective term for measuring instruments, used for indicating, measuring, and recording physical quantities. It is also a field of study about the art and science about making measurement instruments, involving the related ...
in order to monitor certain parts of a program as it is executed. * Obtaining an
abstract syntax tree An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the abstract syntactic structure of text (often source code) written in a formal ...
associated with the program, which can be automatically examined to gain insights into its structure. * Applications of
program slicing In computer programming, program slicing is the computation of the set of program statements, the program slice, that may affect the values at some point of interest, referred to as a slicing criterion. Program slicing can be used in debugging t ...
relevant to SBSE include
software maintenance Software maintenance is the modification of software after delivery. Software maintenance is often considered lower skilled and less rewarding than new development. As such, it is a common target for outsourcing or offshoring. Usually, the tea ...
,
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
and
program analysis In computer science, program analysis is the process of analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness. Program analysis focuses on two major areas: program optimization an ...
. *
Code coverage In software engineering, code coverage, also called 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 code coverage has more of its ...
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 (also known as static analysis or static simulation) is the analysis of computer programs performed without executing them, in contrast with dynamic program analysis, which is performed on programs duri ...


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 a social media and social networking service owned by the American technology conglomerate Meta Platforms, Meta. Created in 2004 by Mark Zuckerberg with four other Harvard College students and roommates, Eduardo Saverin, Andre ...
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) *
Dynamic program analysis Dynamics (from Greek δυναμικός ''dynamikos'' "powerful", from δύναμις ''dynamis'' " power") or dynamic may refer to: Physics and engineering * Dynamics (mechanics), the study of forces and their effect on motion Brands and en ...
* Genetic improvement


References


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
{{Software engineering Computer-related introductions in 2001 Software testing Search algorithms Optimization algorithms and methods Metaheuristics Software quality Program analysis