Heuristiska sökalgoritmer är samlingsnamnet på en grupp sökalgoritmer som har utvecklats under senare år. Det finns ett antal olika varianter av dessa algoritmer, en del efterliknar mekanismerna inom biologin och andra hämtar inspirationen ur en avsvalnande gas [1]. Den mest kända av dessa är olika varianter av Genetisk algoritm [2]. Gemensamt för dessa är att de har förmågan att effektivt söka efter en specificerad lösning på egen hand, de behöver inte mer information än in- och utsignaler från ett system.
Dessa synnerligt kraftfulla matematiska algoritmer har potentialen att bli mycket effektiva verktyg som kan hjälpa till och förbättra kvalitén i utvecklad programvara. Tyvärr så kräver ett korrekt användande av algoritmerna även sin kvinna eller man. Det finns ett antal algoritmer fritt tillgängliga som i princip kan användas direkt, men utan en hyfsad kunskap om hur dessa algoritmer fungerar numeriskt så kan resultatet bli riktigt tokigt. Som vanligt är ett verktyg den starkes stöd och den svages krycka.
Om det nu är så besvärligt och avancerat med sökalgoritmer, kan man då använda dessa i testningen och blir det bättre? Svaret är tveklöst JA på bägge frågorna, samt ett: det beror på…
Som vanligt så finns det tyvärr ingen silverkula som löser alla våra testproblem, till en kostnad som får testchefen att plötsligt börja le vid morgonfikat…
Rickard Torkar på Blekinge tekniska högskola har sammanfattat forskning och tillämpning inom området i flera artiklar [3] och själv har jag bl.a. framgångsrikt använt metoden för att validera funktionaliteten i avioniksystem [4]. Det pågår även ett EU-projekt, EVO Test [5] och aktiviteter förekommer hos ett antal större företag, t.ex. Daimler Chrysler AG [6].
Hur fungerar detta nu? Principen är ganska enkel även om de numeriska algoritmerna bakom är avancerade. Algoritmen börjar med att slumpmässigt generera ett antal testfall bestående av kombinationer av indata. Dessa testfall körs igenom och baserat på resultatet så beräknas nya testfall ut. På detta sätt så söker programmet snabbt fram de testfall som är kritiska. En förutsättning för att detta ska fungera är att det går att definiera en utsignal eller ett tillstånd som går att mäta. Ett exempel på en sådan mätsignal är minnesanvändning i ett system. Search Based Software Testing (SBST) är en uttalad metod för Black-box-testning på funktions- och systemnivån, och fungerar bäst i system som har en högre grad av integration av delsystem där kombinatoriken medför problem vid framtagningen av testfall.
Vad vinner man på detta? För programvaruintensiva företag, t.ex. Ericsson, så kan idag testning utgöra mellan 40-60% av tiden i en stor del av utvecklingsprojekten och ha motsvarande påverkan på kostnaderna [7]. Kan ett verktyg reducera tiden och kostnaden för funktions- och systemtestning med 10 % så kommer vinsterna att bli stora. Uppskattningar visar på över 400 % ROI när kostnaden för att åtgärda fel som upptäckts hos kund har beaktats [8].
Framöver kommer jag att försöka skriva lite mera om olika tillämpningar av sökbaserad testning. Om ni har någon idé om något system, gärna Open Source, som ni tror skulle kunna vara intressant som demonstration, så hör gärna av er.
Nu är inte bara sökbaserad testning den enda delen av matematiken som kan användas. Formella metoder, Fuzzy Logic, parvis och stokastisk testning är några metoder som används i varierande omfattning. En personlig favorit är stokastiska prediktiva modeller. Genom att bygga dessa modeller baserat på tidigare testhistorik så kan man i vissa fall få en mycket god uppfattning om var merparten av alla defekter sannolikt kommer att uppstå. Rätt utnyttjat så medför det en ökad effektivitet på varje satsad testtimme och motsvarande ökning i kvalitén i produkten. Även om detta kommer jag att försöka återkomma till vid ett senare tillfälle.
I inledningen av detta inlägg så ställde jag frågan om matematik kan förbättra kvalitén i programvara – svaret är tveklös JA. Det handlar om att testa mindre men smartare.
[1] För andra exempel se: http://en.wikipedia.org/wiki/Simulated_annealing och http://en.wikipedia.org/wiki/Differential_evolution
[2] För en översikt se: http://sv.wikipedia.org/wiki/Genetisk_algoritm#Genetisk_algoritm
[3] http://www.torkar.se/Site/Publications_files/afzalTF09.pdf
[4] http://www.nt.ntnu.no/users/skoge/prost/proceedings/ecc03/pdfs/215.pdf
[5] http://evotest.iti.upv.es/
[6] http://iaser.tek.bth.se/swell/talks/afzal_090219_sast_presentation.pdf
[7] http://www.vinnova.se/upload/EPiStorePDF/ProgramvaruintensivaForetagISverige.pdf
[8] http://www.compaid.com/caiinternet/ezine/cost_of_quality_1.pdf
