Bisektion (programvaruteknik)

För annan användning, se Bisect .

Bisection är en metod som används inom mjukvaruutveckling för att identifiera förändringsuppsättningar som resulterar i en specifik beteendeförändring. Det används mest för att hitta patchen som introducerade en bugg . Ett annat applikationsområde är att hitta patchen som indirekt fixade en bugg.

Översikt

Processen att lokalisera förändringsuppsättningen som introducerade en specifik regression beskrevs som "isolering av källaförändringar" 1997 av Brian Ness och Viet Ngo från Cray Research . Regressionstestning utfördes på Crays kompilatorer i upplagor som omfattar en eller flera ändringsuppsättningar. Utgåvor med kända regressioner kunde inte valideras förrän utvecklarna åtgärdat problemet. Källändringsisolering minskade orsaken till en enda ändringsuppsättning som sedan kunde uteslutas från utgåvor, vilket avblockerade dem med avseende på detta problem, medan författaren till ändringen arbetade på en fix. Ness och Ngo beskrev linjära sök- och binära sökmetoder för att utföra denna isolering.

Kodbisektion har som mål att minimera ansträngningen att hitta en specifik förändringsuppsättning. Den använder en dividera och erövra algoritm som är beroende av att ha tillgång till kodhistoriken som vanligtvis bevaras av revisionskontroll i ett kodlager .

Bisektionsmetod

Kodhalveringsalgoritm

Kodhistorik har strukturen av en riktad acyklisk graf som kan sorteras topologiskt . Detta gör det möjligt att använda en dividera och erövra sökalgoritm som:

• delar upp sökutrymmet för kandidatrevisioner
• tester för beteendet i fråga
• minskar sökutrymmet beroende på testresultatet
• upprepar stegen ovan tills ett intervall med högst en delbar patch-kandidat återstår

Algoritmisk komplexitet

Bisektion är i LSPACE med en algoritmisk komplexitet av $O(\log N)$ med $N$ som anger antalet revisioner i sökutrymmet, och liknar en binär sökning .

Önskvärda förvarsegenskaper

För koduppdelning är det önskvärt att varje revision i sökutrymmet kan byggas och testas oberoende.

Monotonicitet

För att bisektionsalgoritmen ska identifiera en enda ändringsuppsättning som fick beteendet som testades att ändras, måste beteendet ändras monotont över sökutrymmet. För en boolesk funktion som ett godkänt/underkänd-test betyder det att det bara ändras en gång över alla ändringsuppsättningar mellan början och slutet av sökutrymmet.

Om det finns flera ändringsuppsättningar över sökutrymmet där beteendet som testas ändras mellan falskt och sant, så kommer algoritmen att hitta en av dem, men det kommer inte nödvändigtvis att vara grundorsaken till förändringen i beteende mellan början och slutet av sökutrymmet. Grundorsaken kan vara en annan ändringsuppsättning eller en kombination av två eller flera ändringsuppsättningar i sökutrymmet. För att hjälpa till att hantera detta problem tillåter automatiserade verktyg att ignorera specifika ändringsuppsättningar under en halveringssökning.

Automationsstöd

Även om halveringsmetoden kan genomföras manuellt, är en av dess främsta fördelar att den lätt kan automatiseras. Det kan alltså passa in i befintliga testautomatiseringsprocesser : misslyckanden i uttömmande automatiserade regressionstester kan utlösa automatisk halvering för att lokalisera fel. Ness och Ngo fokuserade på sin potential i Crays med kontinuerlig leverans, där den automatiskt isolerade dåliga ändringsuppsättningen automatiskt kunde uteslutas från byggen.

Revisionskontrollsystemen Fossil , Git och Mercurial har inbyggd funktionalitet för koduppdelning. Användaren kan starta en halveringssession med ett specificerat intervall av revisioner från vilka revisionskontrollsystemet föreslår en revision att testa, användaren talar om för systemet om revisionen testades som "bra" eller "dålig", och processen upprepas tills den specifika "dålig" revision har identifierats. Andra revisionskontrollsystem, som Bazaar eller Subversion , stödjer uppdelning genom plugins eller externa skript.

Phoronix Test Suite kan göra halvering automatiskt för att hitta prestandaregressioner.

Se även

• Delta-felsökning (generalisering av att hitta en minimal orsak till en bugg)
• Anteckning § Källkontroll (bestämmer ändringsuppsättningar som redigerade en rad i en fil)