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

Andrã©As Johansson

Description

Robustness Evaluation of Operating SystemsVom Fachbereich Informatik der Technischen Universit¨ at DarmstadtgenehmigteDissertationzur Erlangung des akademischen Grades eines Doktor-Ingenieur (Dr.-Ing.)vorgelegt vonAndr´eas Johanssonaus Falkenberg, SchwedenReferenten:Prof. Neeraj Suri, Ph.D.Prof. Christof Fetzer, Ph.D.Datum der Einreichung: 19.11.2007Datum der mundlic¨ hen Prufung:¨ 14.01.2008Darmstadt 2008D17iiSummaryThe premise behind this thesis is the observation that Operating Systems (OS),being the foundation behind operations of computing systems, are complex entitiesand also subject to failures. Consequently, when they do fail, the impact is theloss of system service and the applications running thereon. While a multitudeof sources for OS failures exist, device drivers are often identified as a prominentcause behind failures.In order to characterize the impact of driver failures, at both the OS andapplication levels, this thesis develops a framework for error propagation-basedrobustness profiling for an OS. The framework is first developed conceptually andthen experimentally validated on a real OS, namely Windows CE .Net. The choiceof Windows CE is driven by its representativeness for a multitude of OS’s, as wellas the ability to customize the OS components for particular needs.

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2008
• Nombre de lectures: 40

Extrait

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