HOME

TheInfoList



OR:

Bisection is a method used in
software development Software development is the process of conceiving, specifying, designing, programming, documenting, testing, and bug fixing involved in creating and maintaining applications, frameworks, or other software components. Software development invol ...
to identify change sets that result in a specific behavior change. It is mostly employed for finding the patch that introduced a bug. Another application area is finding the patch that indirectly fixed a bug.


Overview

The process of locating the changeset that introduced a specific
regression Regression or regressions may refer to: Science * Marine regression, coastal advance due to falling sea level, the opposite of marine transgression * Regression (medicine), a characteristic of diseases to express lighter symptoms or less extent ( ...
was described as "source change isolation" in 1997 by Brian Ness and Viet Ngo of Cray Research. Regression testing was performed on Cray's compilers in editions comprising one or more changesets. Editions with known regressions could not be validated until developers addressed the problem. Source change isolation narrowed the cause to a single changeset that could then be excluded from editions, unblocking them with respect to this problem, while the author of the change worked on a fix. Ness and Ngo outlined
linear search In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in at ...
and binary search methods of performing this isolation. Code bisection has the goal of minimizing the effort to find a specific change set. It employs a divide and conquer algorithm that depends on having access to the code history which is usually preserved by revision control in a
code repository In version control systems, a repository is a data structure that stores metadata for a set of files or directory structure. Depending on whether the version control system in use is distributed, like Git or Mercurial, or centralized, like Subver ...
.


Bisection method


Code bisection algorithm

Code history has the structure of a directed acyclic graph which can be topologically sorted. This makes it possible to use a divide and conquer search algorithm which: * splits up the search space of candidate revisions * tests for the behavior in question * reduces the search space depending on the test result * re-iterates the steps above until a range with at most one bisectable patch candidate remains


Algorithmic complexity

Bisection is in LSPACE having an algorithmic complexity of O(\log N) with N denoting the number of revisions in the search space, and is similar to a binary search.


Desirable repository properties

For code bisection it is desirable that each revision in the search space can be built and tested independently.


Monotonicity

For the bisection algorithm to identify a single changeset which caused the behavior being tested to change, the behavior must change monotonically across the search space. For a Boolean function such as a pass/fail test, this means that it only changes once across all changesets between the start and end of the search space. If there are multiple changesets across the search space where the behavior being tested changes between false and true, then the bisection algorithm will find one of them, but it will not necessarily be the
root cause Root cause may refer to: * "Root Cause" (''Person of Interest''), a TV show episode * Root cause analysis In science Science is a systematic endeavor that builds and organizes knowledge in the form of testable explanations and predic ...
of the change in behavior between the start and the end of the search space. The root cause could be a different changeset, or a combination of two or more changesets across the search space. To help deal with this problem, automated tools allow specific changesets to be ignored during a bisection search.


Automation support

Although the bisection method can be completed manually, one of its main advantages is that it can be easily automated. It can thus fit into existing test automation processes: failures in exhaustive automated regression tests can trigger automated bisection to localize faults. Ness and Ngo focused on its potential in Cray's continuous delivery-style environment in which the automatically isolated bad changeset could be automatically excluded from builds. The revision control systems Fossil, Git and Mercurial have built-in functionality for code bisection. The user can start a bisection session with a specified range of revisions from which the revision control system proposes a revision to test, the user tells the system whether the revision tested as "good" or "bad", and the process repeats until the specific "bad" revision has been identified. Other revision control systems, such as
Bazaar A bazaar () or souk (; also transliterated as souq) is a marketplace consisting of multiple small Market stall, stalls or shops, especially in the Middle East, the Balkans, North Africa and India. However, temporary open markets elsewhere, suc ...
or
Subversion Subversion () refers to a process by which the values and principles of a system in place are contradicted or reversed in an attempt to transform the established social order and its structures of power, authority, hierarchy, and social norms. Sub ...
, support bisection through plugins or external scripts. Phoronix Test Suite can do bisection automatically to find performance regressions.


See also

* Delta debugging (generalization of finding a minimal cause of a bug) * (determining changesets that edited a line in a file)


References

{{Reflist Version control Version control systems Software development process Algorithms