Arbetar mot bug-fri, säker programvara

Forskare från NICTA (National ICT Australia), Australiens informations- och kommunikationsteknologicenter för excellence, försöker ta bort fel från programvaran:

"Nästan varje uppsats om formell verifiering börjar med iakttagelsen att mjukvarukomplexiteten ökar, att detta leder till fel och att detta är ett problem för uppdrag och säkerhetskritisk programvara. Vi håller med, liksom de flesta."

Min första tanke: inget sätt. Hur kan du eliminera varje fel? Vissa av de mer komplexa programvarupaketen måste ha minst en zillion kodrader.

NICTA-folket är väl medvetna om komplexiteten. Därför fokuserar de på små inbäddade systemprogramvaror till att börja med.

Som bilar

Varje gång min far ringer med ett datorproblem påpekar han att det är kriminellt hur vi accepterar buggy-programvara: "Det kommer att bli en kall dag i helvetet innan jag köper en sådan bil."

Spola framåt till ett telefonsamtal som nyligen gjordes från min pappa. Jag visste inte om jag skulle skratta eller gråta. Hans bil återkallades för en programuppdatering.

NICTA: s uppdrag

NICTA-forskare nämnde:

"Det behöver inte vara så. Ditt företag tar igång en ny försäljningsprogramvara ... Du skriver i ett kontrakt exakt vad programvaran ska göra.

Och sedan - det gör det. Alltid. Och utvecklarna kan bevisa det för dig - med ett faktiskt matematiskt maskinkontrollerat bevis. "

Låter för bra för att vara sant, eller hur? Ändå gör akademiker inte några underbyggda påståenden. Så vad har NICTA-teammedlemmarna upp sina kollektiva ärmar? Jag kontaktade NICTA, och Dr. Juni Andronick gavs frivilligt att förklara vad de hade lärt sig.

Kassner : Hur blev du först intresserad av kodverifiering? Och är det så skrämmande som det verkar? Andronick : Jag kommer från en matematisk bakgrund. Jag började skriva kod med tankesättet där du tänker på varför ditt program ska bete sig som du förväntar dig. Till exempel, "Varför ska det exakt upphöra?"

Jag tyckte att formell kodverifiering var ett fascinerande sätt att kombinera de två världarna ... skriva exakt vad du förväntar dig från programmet ... och sedan bevisa att det gör det.

En del av detta är intuitivt: Programmerare har vanligtvis magkänslan av varför deras program gör vad de vill. Kodverifiering formaliserar just detta resonemang och får det maskinkontrollerat och lämnar ingen plats för tvivel.

Det kan låta skrämmande, men det är faktiskt mycket roligt och beroendeframkallande. Det är som ett spel mellan dig och bevisverktyget - du försöker övertyga det varför du tror att något är sant.

Kassner : Du använde något som heter seL4-mikrokärnan för att testa dina teorier. Varför valde du den här kärnan? Andronick : Målet med L4.verifierat projekt, ledat av professor Gerwin Klein, var att formellt verifiera seL4, en ny mikrokärnan designad av Dr. Kevin Elphinstone. Det är det första steget mot den långsiktiga visionen för vår grupp, ledd av professor Gernot Heiser, att producera verkligt pålitlig programvara för vilken du kan ge stark garanti för dess säkerhet, säkerhet och tillförlitlighet.

Valet att ta itu med kärnan först drivs av en huvudsaklig orsak: Det är den mest kritiska delen av systemet, som ligger mellan hårdvaran och resten av programvaran. Den har full tillgång till alla resurser och styr vad annan programvara kan komma åt.

Systemets beteende kommer att förlita sig på alla aspekter av kärnfunktionalitet. Så alla garantier om systemet måste börja med att kärnan fungerar korrekt.

Eftersom det inte finns något skydd mot fel som uppstår i kärnan, kan något fel där potentiellt orsaka godtycklig skada. Begreppet mikrokärnor kommer från att minska mängden av sådan kritisk kod till ett minimum, minska den "betrodda databasen".

Resultatet av projektet var ett formellt bevis på seL4: s funktionella korrekthet . Detta innebär att kärnan under antagandet av beviset aldrig kan krascha eller på annat sätt bete sig oväntat.

Detta var det första formella beviset på funktionell korrekthet hos en operativsystemkärna med allmänt syfte och mer generellt av någon verklig tillämpning av betydande storlek.

Kassner : 8700 rader med C och 600 rader av monterare verkar vara mycket kod att kontrollera. Är det vad följande bild visar? Kan du förklara vad vi tittar på?

Andronick: Den här bilden visar seL4: s så kallade funktionssamtaldiagram. Varje C-funktion i kärnan är en punkt. Om funktion A kallar funktion B finns det en pil från A till B.

Grafen visar att seL4 är mycket komplex programvara med starkt sammankopplade delar. Detta är typiskt för prestationsoptimerade mikrokärnor.

Välutformad programvara på applikationsnivå skulle ha grupper eller öar med starkt besläktade prickar anslutna med ett litet antal pilar som överbryggar mellan öarna.

Kassner : Du använder termerna formell verifiering och funktionell korrekthet. Kan du beskriva vad de var och en betyder och vilka roller de spelar? Andronick : Formell verifiering avser tillämpningen av matematiska bevistekniker för att fastställa egenskaper om program. Det kan täcka inte bara alla kodrader eller alla beslut i ett program, utan alla möjliga beteenden för alla möjliga ingångar.

Denna uttömmande täckning av alla möjliga scenarier är vad som skiljer det från testning, som bara kan hitta buggar, inte bevisa frånvaron av buggar.

Funktionell korrekthet innebär att kärnan beter sig som förväntat i sin specifikation. Den här egenskapen är starkare och mer exakt än vad automatiserade tekniker som modellkontroll eller statisk analys kan uppnå.

Vi analyserar inte bara specifika aspekter av kärnan, till exempel säker körning, utan ger också en fullständig specifikation och bevis för kärnans exakta beteende.

Den metod som vi använder är en interaktiv teorem som bevisar . Det kräver mänsklig ingripande och kreativitet för att konstruera och vägleda beviset, men har fördelen att det inte är begränsat till specifika egenskaper eller fina, genomförbara tillståndsutrymmen.

Kassner : Jag förstår nu vad du letar efter. Kan du ge en kort översikt över hur du försöker hitta problem? Andronick : Ett problem upptäcks när koden inte uppför sig som specifikationen föreskriver.

Processen börjar med att skriva en formell specifikation av vad kärnan ska göra. Du kan till exempel kräva att en sorteringsfunktion returnerar en lista som är sorterad med samma element än inmatningslistan. Koden beskriver hur denna funktionalitet implementeras som att välja en sorteringsalgoritm.

Då måste du bevisa att resultatet av funktionen alltid uppfyller specifikationskravet. Återigen är den viktigaste differentieraren för testning att vi resonerar om alla möjliga ingångar. Om specifikationen inte gäller för vissa ingångar, kommer beviset att avslöja det. Buggen kommer att åtgärdas och bevisförsöket återupptas. När beviset är klart vet du att det inte finns några implementeringsfel kvar.

Kassner : Vad är nästa steg för verifieringsprocessen? Kan den här proceduren användas för att testa datoroperativsystem vi är vana med? Andronick : Exakt samma tillvägagångssätt skalas inte till system som innehåller en miljon kodrader som moderna operativsystem. Men vi har en plan för stora komplexa system.

Det första att notera är att formell verifiering inte är billig. Vi spenderade betydande e ff ort på verifiering av cirka 10 000 koder. Det verkar fortfarande kostnadseffektivt och mer ordentligt än andra metoder som uppnår lägre grad av pålitlighet.

Det huvudsakliga meddelandet är att sådana grundliga metoder verkligen är vettiga i kritiska system (medicin, fordon, försvar, etc.).

Vår metod för stora kritiska system kommer från iakttagelsen att i sådana system är inte all koden kritisk. Till exempel har medicintekniska apparater stora användargränssnitt och flygplan har underhållningsprogramvara (prof. Heiser skrev en relevant blogg som illustrerar behovet av en verifierad kärna som använder underhållningssystem under flygning som exempel).

Nyckeln till vårt nuvarande arbete är att isolera de icke-kritiska delarna från de kritiska. Detta görs med hjälp av seL4 och dess åtkomstkontroll. Detta gör att vi kan bevisa att ett fel i de icke-kritiska delarna inte kan förhindra att de kritiska delarna uppträder korrekt. På detta sätt kan vi koncentrera verifieringsinsatsen till de kritiska delarna av systemet.

Med andra ord visar vi att formell verifiering av funktionell korrekthet praktiskt kan uppnås för OS-mikrokärnor, och vi arbetar nu med att använda denna pålitliga grund för att ge starka garantier för stora kritiska system.

Kassner : Roligt att du ska nämna underhållningsprogramvara för flygbolag. Medan de senaste röda ögonen till Amsterdam sprang kabinskötare upp och ner i gångarna och ber om ursäkt. Underhållningssystemet var nere. "Det borde snart vara uppe." De sa: "Kaptenen startar om en dator."

Slutgiltiga tankar

Min brinnande fråga: "Vad styr den datorn mer?" Jag blev säker på att allt var under kontroll.

© Copyright 2020 | mobilegn.com