Bisección (ingeniería de software)

Para otros usos, consulte Bisect .

La bisección es un método utilizado en el desarrollo de software para identificar conjuntos de cambios que dan como resultado un cambio de comportamiento específico. Se emplea principalmente para encontrar el parche que introdujo un error . Otra área de aplicación es encontrar el parche que corrigió indirectamente un error.

Visión general

El proceso de localizar el conjunto de cambios que introdujo una regresión específica fue descrito como "aislamiento de cambio de fuente" en 1997 por Brian Ness y Viet Ngo de Cray Research . Las pruebas de regresión se realizaron en los compiladores de Cray en ediciones que comprenden uno o más conjuntos de cambios. Las ediciones con regresiones conocidas no se pudieron validar hasta que los desarrolladores abordaron el problema. El aislamiento del cambio de fuente redujo la causa a un único conjunto de cambios que luego podría excluirse de las ediciones, desbloqueándolos con respecto a este problema, mientras el autor del cambio trabajaba en una solución. Ness y Ngo describieron la búsqueda lineal y los métodos de búsqueda binaria para realizar este aislamiento.^[1]

La bisección de código tiene el objetivo de minimizar el esfuerzo para encontrar un conjunto de cambios específico. Emplea un algoritmo de divide y vencerás que depende de tener acceso al historial del código que generalmente se conserva mediante el control de revisión en un repositorio de código .

Método de bisección

Algoritmo de bisección de código

El historial de código tiene la estructura de un gráfico acíclico dirigido que se puede clasificar topológicamente . Esto hace posible utilizar un algoritmo de búsqueda de divide y vencerás que:

• divide el espacio de búsqueda de las revisiones de los candidatos
• pruebas para el comportamiento en cuestión
• reduce el espacio de búsqueda en función del resultado de la prueba
• reitera los pasos anteriores hasta un intervalo con a lo sumo un bisectable candidatos parche restos

Complejidad algorítmica

La bisección tiene en LSPACE una complejidad algorítmica de con denotar el número de revisiones en el espacio de búsqueda, y es similar a una búsqueda binaria .${\displaystyle O(\log N)}$${\displaystyle N}$

Propiedades deseables del repositorio

Para la bisección de código, es deseable que cada revisión en el espacio de búsqueda se pueda construir y probar de forma independiente.

Monotonicidad

Para que el algoritmo de bisección identifique un único conjunto de cambios que provocó que el comportamiento que se está probando cambie, el comportamiento debe cambiar monótonamente en el espacio de búsqueda. Para una función booleana como una prueba de aprobado / reprobado, esto significa que solo cambia una vez en todos los conjuntos de cambios entre el inicio y el final del espacio de búsqueda.

Si hay varios conjuntos de cambios en el espacio de búsqueda donde el comportamiento que se está probando cambia entre falso y verdadero, entonces el algoritmo de bisección encontrará uno de ellos, pero no será necesariamente la causa raíz del cambio de comportamiento entre el inicio y el final. del espacio de búsqueda. La causa raíz podría ser un conjunto de cambios diferente o una combinación de dos o más conjuntos de cambios en el espacio de búsqueda. Para ayudar a lidiar con este problema, las herramientas automatizadas permiten ignorar conjuntos de cambios específicos durante una búsqueda de bisección.

Soporte de automatización

Aunque el método de bisección se puede completar manualmente, una de sus principales ventajas es que se puede automatizar fácilmente. ^[1] Por lo tanto, puede encajar en los procesos de automatización de pruebas existentes : las fallas en las pruebas de regresión automatizadas exhaustivas pueden desencadenar una bisección automatizada para localizar fallas. Ness y Ngo se centraron en su potencial en el entorno de estilo de entrega continua de Cray en el que el conjunto de cambios incorrecto aislado automáticamente podría excluirse automáticamente de las compilaciones. ^[2]

Los sistemas de control de revisiones Fossil , Git y Mercurial tienen una funcionalidad incorporada para la bisección de código. ^{[3] [4] [5]} El usuario puede iniciar una sesión de bisección con un rango específico de revisiones de las cuales el sistema de control de revisiones propone una revisión para probar, el usuario le dice al sistema si la revisión fue probada como "buena" o "mala". ", y el proceso se repite hasta que se identifica la revisión" incorrecta "específica. Otros sistemas de control de revisiones, como Bazaar o Subversion , admiten la bisección a través de complementos ^[6] o scripts externos. ^[7]

Phoronix Test Suite puede realizar bisecciones automáticamente para encontrar regresiones de rendimiento.

Ver también

• Depuración delta (generalización de encontrar una causa mínima de un error)
• Anotación § Control de fuente (determinación de conjuntos de cambios que editaron una línea en un archivo)

Referencias

1. Ness, Brian; Ngo, Viet (1997). Contención de regresión mediante aislamiento de cambio de fuente . Jornada de Software y Aplicaciones Informáticas. IEEE. doi : 10.1109 / CMPSAC.1997.625082 .
2. Zeller, Andreas (1999). Ayer, mi programa funcionó. Hoy no es así. ¿Por qué? . Congreso Europeo de Ingeniería de Software. Toulouse, Francia. doi : 10.1145 / 318774.318946 .
3. "Fósil: Ayuda: bisecar" . www.fossil-scm.org . Consultado el 3 de septiembre de 2020 .
4. "git-bisect (1)" . git-scm.com . Consultado el 5 de agosto de 2017 .
5. "hg" . Selenic.com . Consultado el 9 de enero de 2017 .
6. "bisect - Encuentra la revisión que introduce un error usando una búsqueda binaria - documentación de Bazaar 2.8.0dev1" . Doc.bazaar.canonical.com . Consultado el 9 de enero de 2017 .
7. "svn-bisecar" . Metacpan.org . Consultado el 9 de enero de 2017 .