Bisection (software engineering)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Bisection is a method used in software development 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[edit]

The process of locating the changeset that introduced a specific regression 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 and binary search methods of performing this isolation.[1]

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.

Bisection method[edit]

Code bisection algorithm[edit]

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[edit]

Bisection is in LSPACE having an algorithmic complexity of with denoting the number of revisions in the search space, and is similar to a binary search.

Desirable repository properties[edit]

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

Automation support[edit]

Although the bisection method can be completed manually, one of its main advantages is that it can be easily automated.[1] 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.[2]

The revision control systems Git and Mercurial have built-in functionality for code bisection.[3][4] 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 or Subversion, support bisection through plugins[5] or external scripts.[6]

Phoronix Test Suite can do bisection automatically to find performance regressions.

See also[edit]

References[edit]

  1. ^ a b Ness, Brian; Ngo, Viet (1997). Regression containment through source change isolation. Computer Software and Applications Conference. IEEE. doi:10.1109/CMPSAC.1997.625082.
  2. ^ Zeller, Andreas (1999). Yesterday, my program worked. Today, it does not. Why?. European Software Engineering Conference. Toulouse, France. doi:10.1145/318774.318946.
  3. ^ "git-bisect(1)". git-scm.com. Retrieved 2017-08-05.
  4. ^ "hg". Selenic.com. Retrieved 2017-01-09.
  5. ^ "bisect - Find the revision introducing a bug using a binary search — Bazaar 2.8.0dev1 documentation". Doc.bazaar.canonical.com. Retrieved 2017-01-09.
  6. ^ "svn-bisect". Metacpan.org. Retrieved 2017-01-09.