Бисекция (программная инженерия)

Bisection — это метод, используемый в разработке программного обеспечения для определения наборов изменений , которые приводят к определенному изменению поведения. Он в основном используется для поиска патча, который внес ошибку . Другая область применения — поиск патча, который косвенно исправил ошибку.

Процесс поиска набора изменений , который внес определенную регрессию, был описан как «изоляция исходных изменений» в 1997 году Брайаном Нессом и Вьет Нго из Cray Research . Регрессионное тестирование проводилось на компиляторах Cray в редакциях, включающих один или несколько наборов изменений. Редакции с известными регрессиями не могли быть проверены, пока разработчики не устранили проблему. Изоляция исходных изменений сузила причину до одного набора изменений, который затем можно было исключить из редакций, разблокировав их в отношении этой проблемы, пока автор изменения работал над исправлением. Несс и Нго обрисовали методы линейного поиска и бинарного поиска для выполнения этой изоляции. ^[1]

Разделение кода на части имеет целью минимизировать усилия по поиску определенного набора изменений. Оно использует алгоритм «разделяй и властвуй» , который зависит от доступа к истории кода, которая обычно сохраняется контролем версий в репозитории кода .

История кода имеет структуру направленного ациклического графа , который может быть отсортирован топологически . Это позволяет использовать алгоритм поиска «разделяй и властвуй», который:

• разделяет область поиска кандидатов на ревизии
• тесты на рассматриваемое поведение
• сокращает пространство поиска в зависимости от результата теста
• повторяет шаги, описанные выше, пока не останется диапазон с максимум одним кандидатом на патч, который можно разделить пополам

Двоичное деление выполняется в LSPACE, имея алгоритмическую сложность , обозначающую количество ревизий в пространстве поиска, и похоже на двоичный поиск .${\displaystyle O(\log N)}$${\displaystyle N}$

Для деления кода на части желательно, чтобы каждая ревизия в поисковом пространстве могла быть создана и протестирована независимо.

Для того чтобы алгоритм бисекции идентифицировал один набор изменений, который вызвал изменение тестируемого поведения, поведение должно изменяться монотонно по всему пространству поиска. Для булевой функции, такой как тест pass/fail, это означает, что она изменяется только один раз по всем наборам изменений между началом и концом пространства поиска.

Если в пространстве поиска есть несколько наборов изменений, где тестируемое поведение меняется с ложного на истинное, то алгоритм деления пополам найдет один из них, но он не обязательно будет основной причиной изменения поведения между началом и концом пространства поиска. Основной причиной может быть другой набор изменений или комбинация двух или более наборов изменений в пространстве поиска. Чтобы помочь справиться с этой проблемой, автоматизированные инструменты позволяют игнорировать определенные наборы изменений во время поиска деления пополам.

Хотя метод деления пополам можно выполнить вручную, одним из его главных преимуществ является то, что его можно легко автоматизировать. ^[1] Таким образом, он может быть встроен в существующие процессы автоматизации тестирования : сбои в исчерпывающих автоматизированных регрессионных тестах могут запустить автоматическое деление пополам для локализации ошибок. Несс и Нго сосредоточились на его потенциале в среде непрерывной доставки Cray, в которой автоматически изолированный плохой набор изменений может быть автоматически исключен из сборок. ^[2]

Системы контроля версий Fossil , Git и Mercurial имеют встроенную функциональность для деления кода на части. ^{[3] [4] [5]} Пользователь может начать сеанс деления на части с указанным диапазоном ревизий, из которых система контроля версий предлагает ревизию для тестирования, пользователь сообщает системе, является ли протестированная ревизия «хорошей» или «плохой», и процесс повторяется до тех пор, пока не будет идентифицирована конкретная «плохая» ревизия. Другие системы контроля версий, такие как Bazaar или Subversion , поддерживают деление на части с помощью плагинов ^[6] или внешних скриптов. ^[7]

Тестовый набор Phoronix может автоматически выполнять деление пополам для выявления снижения производительности.

• Дельта-отладка (обобщение поиска минимальной причины ошибки)
• Аннотация § Управление исходным кодом (определение наборов изменений, которые редактировали строку в файле)