Robustness evaluation of operating systems [Elektronische Ressource] / vorgelegt von Andréas Johansson

RobustnessEvaluationofOperatingSystems

VomFachbereichInformatikderTechnischenUniversit¨atDarmstadt
genehmigte

Dissertation

zurErlangungdesakademischenGradeseinesDoktor-Ingenieur(Dr.-Ing.)
novorgelegtv

Johanssoneas´Andr

ausFalkenberg,Schweden

Prof.NeeraReferenjSuri,ten:Ph.D.
ChristofProf.Ph.D.etzer,F

DatumDatumdermder¨undlicEinreichenhPrung:¨ufung:19.11.200714.01.2008

2008DarmstadtD17

ii

Summary

ThepremisebehindthisthesisistheobservationthatOperatingSystems(OS),
beingthefoundationbehindoperationsofcomputingsystems,arecomplexentities
andalsosubjecttofailures.Consequently,whentheydofail,theimpactisthe
lossofsystemserviceandtheapplicationsrunningthereon.Whileamultitude
ofsourcesforOSfailuresexist,devicedriversareoftenidentifiedasaprominent
failures.ehindbcauseInordertocharacterizetheimpactofdriverfailures,atboththeOSand
applicationlevels,thisthesisdevelopsaframeworkforerrorpropagation-based
robustnessprofilingforanOS.Theframeworkisfirstdevelopedconceptuallyand
thenexperimentallyvalidatedonarealOS,namelyWindowsCE.Net.Thechoice
ofWindowsCEisdrivenbyitsrepresentativenessforamultitudeofOS’s,aswell
astheabilitytocustomizetheOScomponentsforparticularneeds.
Forexperimentalvalidation,faultinjectionisaprominenttechniquethatcan
beusedtosimulatefaults(orerrors)inthesystembyinsertingsyntheticones
andstudytheireffect.Threekeyquestionswithsuchatechniquearewhere,what
andwhentoinjectfaults.Thisthesisshowshowinjectingerrorsattheinterface
betweendriversandtheOScanbeveryeffectiveinevaluatingtheeffectsdriver
faultscanhave.
ToquantifytheOS’srobustness,thisthesisdefinesaseriesoferrorpropaga-
tionmeasures,specificallytailoredfordevicedrivers.Thesemeasuresallowfor
quantifyingandcomparingbothindividualservicesanddevicedriversontheir
abilities.diffusingandysusceptibilitThisthesiscomparesthreecontemporaryerrormodelsontheirsuitabilityfor
robustnessevaluation.Theclassicalbit-flipmodelisfoundtoidentifyahigher
numberofseverefailuresinthesystem.Italsoidentifiesfailuresformoreservices
thanbothothermodels,datatypeandfuzzing.However,itsmaindrawbackis
thatitrequiressubstantiallymoreinjectionsthantheothertwo.Fuzzing,even
thoughnotgivingrisetoasmanyfailuresisabletofindnewadditionalservices
failures.eresevwithAcarefulstudyoftheinjectionsperformedwiththebit-flipmodelshowsthat
onlyafewbitsaregenerallyusefulforidentifyingnewserviceswithrobustness
weaknesses.Consequently,anewcompositemodelisproposed,combiningthe
mosteffectivebitsofthebit-flipmodelwiththefuzzingmodel’sabilitytoidentify
newservices,givingrisetonewmodelwithoutlossofimportantinformationand
atthesametimeincurringamoderatenumberofinjections.
Toanswerthequestionofwhentoinjectanerrorthisthesisproposesanovel
modelofadriver’susageprofile,focusingonhigh-leveloperationsbeingcarried
out.Itguidestheinjectionoferrorstoinstanceswhenthedriveriscarryingout
specificoperations.Resultsfromextensivefaultinjectionexperimentsshowthat
moreservicevulnerabilitiescanbediscovered.Furthermore,aprioriprofilingof
thedriverscanshowhoweffectivetheproposedapproachwillbe.

iii

iv

KurzfassungDerHintergrunddieserDissertationberuhtaufderBeobachtung,dassdas
Betriebssystem,welchesdieGrundlagef¨urdenBetriebvonRechnersystemen
darstellt,einesehrkomplexeStrukturaufweist,wash¨aufigzuFehlernimBe-
triebssystemf¨uhrenkann.WenndiesebetriebssysteminternenFehlerAusf¨allevon
DienstenzurFolgehaben,sindauchdieimRahmendesBetriebssystemslaufenden
Applikationengef¨ahrdet.AuchwennesimallgemeinenvieleFehlerquellengibt,
werdenoftfehlerhafteTreiberalsdieh¨aufigsteUrsacheangegeben.
UmdieAuswirkungenvonTreiberdefektenaufderBetriebssystem-undApp-
likationsebenezucharakterisieren,wirdindieserDissertationeinaufderAusbre-
itungvonFehlernbasierendesFrameworkf¨urRobustheitsauswertungentwickelt.
DasFrameworkwirdsowohlkonzeptionellentwickeltalsauchaufeinemechtenBe-
triebssystemexperimentellvalidiert.Dasgew¨ahlteBetriebssystem,WindowsCE
.Net,istrepr¨asentativf¨urvieleandereBetriebssysteme.Esistmodularaufgebaut,
wasdieAnpassungderBetriebssystemkomponentenanverschiedeneBed¨urfnisse
erheblichvereinfacht.
FehlerinjektionisteinebedeutendeTechnikf¨urdieexperimentelleValidierung,
wobeiFehlersimuliertwerdenindemmansieindasSysteminjiziertundihreFol-
genbeobachtet.DreiwichtigeAspekte,diehierbeiber¨ucksichtigtwerdenm¨ussen,
sind:WelcheFehlersollenwoundwanninjiziertwerden.IndieserDissertation
wirdgezeigt,dassFehlerinjektionindieSchnittstellezwischendemBetriebssystem
unddenTreiberneineeffektiveVorgehensweisedarstellt,dieFolgenvonTreiber-
atzen.h¨abzuscfehlernUmdieRobustheiteinesBetriebssystemszuquantifizieren,werdeneineReihe
vonFehlerausbreitungsmetrikendefiniert,diespeziellaufTreiberfehlerzugeschnit-
tensind.AnhanddieserMetrikenk¨onnenDiensteundTreiberhinsichtlich
EmpfindlichkeitundAusbreitungsverm¨ogenverglichenwerden.
DieseDissertationvergleichtdreizeitgem¨aeFehlermodelleinBezugaufihre
TauglichkeitzurRobustheitsbewertung.DasklassischeBit-Flip-Modellermittelt
amh¨aufigstenschwereAusf¨alleimSystem.MehralsdiebeidenanderenModelle,
DataTypeundFuzzing,ermitteltdiesesModellauchdiemeistenDienste,diezu
Ausf¨allenf¨uhrenk¨onnten.Dergr¨oteNachteildiesesModellsistallerdings,dass
essehrvieleInjektionenerfordert.FuzzingermitteltwenigerDienste,daf¨uraber
neuefehlerhafte,vonBit-FlipnichterkannteDienste.
Einesorgf¨altigeUntersuchungderErgebnissedesBit-Flip-Modellszeigt,dass
schoneineTeilmengederBitsausreichendist,umneueDienste,diezuRobus-
theitsausf¨allenf¨uhren,zuermitteln.Daraufhinwirdeinneues,zusammengesetztes
Modellvorgeschlagen,dasdiegutenEigenschaftendesBit-Flip-Modellsunddas
Verm¨ogendesFuzzing-ModellsneueDienstezuidentifizierenmiteinanderkom-
biniert.DasneueModellverliertkeinewichtigeInformation,underfordertinsge-
samtdeutlichwenigerInjektionen.
UmdieFragezubeantwortenwannessinnvollistFehlerzuinjizieren,wirdein
neues,andasBenutzerprofildesTreibersangelehntesTimingmodellvorgeschla-

v

gen.

Das

neue

dellMo

basiert

auf

der

Ausfuhrung¨

nov

Befehlen

in

einer

oherenh¨

Schicht.BestimmteFehlerinjektionenwerdenzumZeitpunktderAusf¨uhrungbes-

timmterBefehleget¨atigt.DieErgebnissederFehlerinjektionenzeigen,dassein

Vielfachesanst¨orungsanf¨alligen

utzerprofilBendas

neuen

Methode.

des

ersreibT

Dienstengefundenwerdenkann.Auerdemgibt

im

orausV

vi

hlussAufsc

erub¨

die

atEffektivit¨

der

tswledgemenknoAc

andThespacious,pathtoonlyatoPh.D.beiscomealong,narrowewindingrandone.narroAtwtheer.beginningSometimesititisgowidees
steeplyupwards,sometimesdownwards.Sometimesyouthinkyouseean
opcrossings,eningandwherelightoneafterhasthetochnextooseturn,whichonlypathtotofindapursue.deadSomeend.pathsThereloareok
morepromisingthanothersbutyouquicklylearnthattheeasypathisnot
alwaystheshortest.

Iamnowattheendofthepath,onlytorealizethatitisthebeginningofa
new.Iwouldnothavegottenherewithouttheassistanceandencouragement
ofProf.severalNeerapjeople.Suri.FirstThanksofallforIwyourouldlikeguidancetothankandmsuppyort.guideIandwouldmentor,also
likeVilgot,to¨thankOrjan,allArshad,presentRobandert,formerAdina,membDinersu,oftheMarco,DEEDSDan,Ripgroup:on,Martin,Brahim,
Faisal,MajidandMatthias.ManythanksalsotoBirgit,Ute,Sabineand
bBoeymayn.oppAonengreatt.manythanksalsotoProf.ChrstofFetzerforacceptingto

theIproamjectsalsoECgratefulIPforDECOS,fundingECNoEforReSISTconductingandmbyyresearcresearchhgrancomingtsfromfrom
overMicrosoftaninternshipResearch.atAMicrosoftpartoftheResearch,researchCamvbridge.alidationAwspasecialaccomplishedthanksto
BrendanMurphyatMSRforhostingmyinternshipandforalldiscussions
ers.papwritinghelpandFinallytomybeautifulandsupportingwife,Mia.Thankyouforevery-
thing!

vii

viii

tstenCon

ductiontronI11.1Dep1.1.1endabilitDepy:endabilitTheyABasicttributesConcepts................................
1.1.21.1.3DepDependabilitendabilityyMeansThreats.....................................
1.1.4AlternateTerminology:SoftwareEngineering.....
1.1.5BohrbugsandHeisenbugs................
......................aluationEvRobustness1.21.3ThesisResearchQuestions&Contributions..........
..........................StructureThesis1.42BackgroundandContext
2.1AShortOperatingSystemHistory...............
2.1.12.1.2OSDeviceDesignDrivers................................................
2.22.1.3SourcesofWhatFisailurestheofOpProblem?eratingSystems..............................
2.2.22.2.1SoftHardwwareareRelatedRelated..........................................
.......................RelatedUser2.2.3.......................ersDrivDevice2.2.4..........................InjectionaultF2.32.4OperatingSystemsDependabilityEvaluation..........
2.5OtherTechniquesforVerificationandValidation........
2.5.12.5.2FTormalestingMethods.................................................
.............................Summary2.633.1SystemSystemandMoErrordelModel...........................
............................delMoError3.2

ix

1345677894115616171818191020212227292030313334363

3.2.1ErrorType........................
3.2.33.2.2ErrorErrorTLoriggercation.............................................
3.2.4OtherContemporarySoftwareErrorModels