An Analytical Approach to Architecture-Based Software Reliability Prediction

PerformanceandReliabilityPrediction

SwapnaS.Gokhale1,W.EricWong2,J.R.Horgan3andKishorS.Trivedi4

1

Dept.ofCSE,Univ.ofConnecticut,Storrs,CT062692

Dept.ofCS,Univ.ofTexasatDallas,Richardson,TX75083

AppliedResearch,TelcordiaTechnologies,Morristown,NJ07960

4

Dept.ofECE,DukeUniv.,Durham,NC27708Abstract

Conventionalapproachestoanalyzethebehaviorofsoftwareapplicationsareblackboxbased,thatis,thesoftwareapplicationistreatedasawholeandonlyitsinteractionswiththeoutsideworldaremodeled.Theblackboxapproachesignoreinformationabouttheinternalstructureoftheapplicationandthebehavioroftheindividualparts.Hencetheyareinadequatetomodelthebehaviorofarealisticsoftwareapplicationwhichislikelytobemadeupofseveralinteractingparts.Architecture–basedanalysis,whichseekstoassessthebehaviorofasoftwareapplicationtakingintoconsiderationthebehaviorofitspartsandtheinteractionsamongthepartsisthusessential.Mostoftheresearchintheareaofarchitecture–basedanalysishasbeendevotedtodevelopinganalyticalmodels,withverylittleifanyeffortbeingdevotedtohowthesemodelsmightbeappliedtorealsoftwareapplications.Inordertoapplythesemodelstosoftwareapplications,methodologiesmustbedevelopedtoextracttheparametersoftheanalyticalmodelsfrominformationcollectedduringtheexecutionoftheapplication.Inthispaperwepresentanexperimentalmethodologytoextracttheparametersofarchitecture–basedmodelsfromcodecoveragemeasurementsobtainedduringtheexecutionoftheapplication.TofacilitatethisweuseacoverageanalysistoolcalledATAC(AutomaticTestAnalyzerinC),whichisapartofTelcordiaSoftwareVisualizationandAnalysisToolsuite(TSVAT)developedatTelcordiaTechnologies.WedemonstratethemethodologybypredictingtheperformanceandreliabilityofanapplicationcalledSHARPE(SymbolicHierarchicalAutomatedReliabilityPredictor),whichhasbeenwidelyusedtosolvestochasticmodelsofreliability,performanceandperformability.

Keywords

SoftwarePerformance,SoftwareReliability,SoftwareArchitectureMarkovChain,Semi–MarkovProcess

1

1Introduction

Thesizeandcomplexityofcomputersystemshasincreasedmorerapidlyinthepastdecade,thanourabilitytodesign,test,implementandmaintainthem.Computersystemsarebeingin-creasinglyusedinvariousactive(controlling),andpassive(monitoring)applications,andthetrendwillsurelycontinueinthefuture.Computersystemfailuresmakenewspaperheadlinesbecauseatbesttheyinconveniencepeople(e.g.,malfunctionsofhomeappliances),causeeco-nomicdamage(e.g.,interruptionsofbankingservices),andintheextremecasescausedeaths(e.g.,failuresofflightcontrolsystemsormedicalsoftware).Thecomputerindustryhasseenunevenprogress.Withthesteadilygrowingpowerandreliabilityofthehardware,softwarereliabilityhasbeenidentifiedasamajorstumblingblockintherealizationofhighlydepend-ablecomputersystems.Whenlivesandfortunesdependonsoftware,assuranceofitsqualitybecomesanissueofcriticalconcern.

Conventionalapproachestoanalyzingtheperformanceandreliabilityofsoftwareapplica-tionstreatthesoftwareapplicationasawholeandonlyitsinteractionswiththeoutsideworldaremodeled[11].Oneofthemostnotabledrawbacksoftheseapproachesisthattheyignoretheinternalstructureoftheapplicationandtheperformanceandreliabilitybehaviorofthevar-iouspartsofwhichtheapplicationismadeupof[18,24].Evenamoderatesizedsoftwareapplicationislikelytobedevelopedusinga“divideandconquer”strategyandmadeupofseveralinteractingparts.Asaresult,conventionalapproacheswhichtreattheapplicationasawholeareinadequatetomodelthebehaviorofevenmoderatesizedapplications.Arecognitionoftheinadequacyofconventionalapproachesisevidentfromthefactthatafewresearchef-fortshaveaddressedtheissueofcharacterizingthebehaviorofmodularsoftwareapplicationssincethe1970s[7,31,32,33,36,38,39,40].Theadventofcomponenttechnologiesandobject–orientedprogrammingholdsthepromiseofrealizingthevisionofassemblingsoftwareapplicationsfromsystematicallydevelopedreusablesoftwarecomponents.Thishasgeneratedrenewedinterestin“architecture–basedanalysis”whichaimstocharacterizetheperformanceandreliabilitybehaviorofsoftwareapplicationsbasedonthebehaviorofthe“components”andthe“architecture”oftheapplication[10,15,13,17,19,25,28,29,44].Wenotethatthenotionof“architecture”and“components”iswelldefinedonlyinthecontextofapplicationsthatareassembledfromsoftwarecomponentsusingoneofthecomponenttechnologiessuchasMicrosoft’sCOM/DCOM[1]orCORBAcomponentmodel[2]orSunMicrosystems’Jav-aBeans[4]andEnterpriseJavaBeans[3].Thenotionofarchitectureandcomponentsisnotclearlydefinedinthecontextofapplicationswhicharebuiltgroundup.However,theuseofarchitecture–basedanalysiswhichessentiallycharacterizesthebehaviorofasoftwareap-plicationintermsofthebehaviorofitspartsandinteractionsamongthepartsisnotlimitedtoapplicationsdevelopedusingthecomponent–basedapproach.Infact,architecture–based

2

analysisisvaluabletowardsanalyzinghowdifferentpiecesoftheapplicationinteractandcon-tributetotheoverallapplicationreliabilityevenforanapplicationthatisbuiltgroundup.Theexistingapproachestoarchitecture–basedanalysiscanbeclassifiedintothreecate-gories,namely,state–based[7,27,31],path–based[25,47,41]andadditive[46]asproposedbyGoseva–Popstojanova[16].Ofthethreetypesofapproaches,state–basedapproacheshavereceivedamaximumdegreeofattention.State–basedmodelsusethecontrolflowgraphtorepresentsoftwarearchitectureandevaluatesoftwarereliabilityanalytically.TheyassumethatthetransferofcontrolamongthecomponentsfollowsaMarkovproperty.Softwarearchitec-tureismodeledusingadiscretetimeMarkovchain(DTMC)[7],continuoustimeMarkovchain(CTMC)[27,31],orasemi–Markovprocess(SMP)[26].Mostoftheresearcheffortsintheareaofstate–basedmodelshavefocusedonthedevelopmentoftheoreticalmodels.Verylittleenergyhasbeendevotedtothequestionofhowtoapplythesemodelstorealsoftwareapplications.Inordertoapplythesemodelstorealsoftwareapplications,theparametersthatdrivethesemodelsneedtobeobtained.Theseparametersdescribethearchitecturalbehav-iorofaapplicationandthefailurecharacteristicsofitscomponents.Theseparameterscanbeobtainedfromavarietyofsources.Unlikeblackboxapproacheswhichcanbeappliedonlyduringthetestingphaseoftheapplication(whichisoneofthedrawbacksoftheblackboxapproaches[18,24]),architecture–basedanalysiscanbeappliedasearlyasthedesignphaseofthesoftwareapplication.Asoftwareapplicationthatisdevelopedinanidealmannerwillgothroughafirstroundofarchitecture–basedanalysisduringthedesignphase.Whenarchitecture–basedanalysisisconductedduringthedesignphase,thearchitectureoftheappli-cationmaybeobtainedfromexpertopinion,frompriorexperiencewithasimilarproduct,fromthepreviousreleaseofthesameproduct,bysimulationormaybe“guestimated”.Itisunlikelythatthefailurebehaviorofthecomponentsisavailableduringthedesignstageexceptforcom-ponentswhicharebeingreusedorarepickedofftheshelf.Ifthecomponentisanofftheshelfcomponentitsreliabilitymaybecertified[19].Inthedesignphase,architecture–basedanalysiscanbeusedtoanswerquestionssuchas:(i)whichcomponentsarecriticaltotheperformanceandreliabilityoftheapplication,and(ii)howistheapplicationreliabilityinfluencedbytheperformanceandreliabilitiesofindividualcomponents?Ifthesoftwareapplicationisgoingtobeassembledfromacollectionofcomponents,thenanswerstosuchquestionscanhelpthede-signerstomakedecisionssuchaswhichcomponentsshouldbepickedofftheshelf,andwhichcomponentsshouldbedevelopedinhouse.Ifthesoftwareapplicationisgoingtobedevelopedgroundup,thensuchanswerscanhelpthedesignersinmakingdecisionssuchaswhichcom-ponentsshouldbedevelopedbyexperienceddevelopers.Astheapplicationprogressesthroughthedevelopmentandintegrationphases,additionaldatamaybeavailablewhichcouldbeusedtorefinetheparametersrepresentingthearchitectureaswellasthefailurebehavior.During

3

thetestingphase,measurementsobtainedduringtheexecutionoftheapplicationcanbeusedtorefinethearchitecture–basedmodelsfurther.Inordertousetheexecutioninformationgen-eratedduringthetestingoftheapplicationtorefinethearchitecturalmodels,methodologiesmustbedevelopedtorecordandprocesstheexecutioninformation.Themethodologycapa-bleofusingexecutioninformationforarchitecture–basedanalysiswillnotonlybeusefulinrefiningarchitecturalmodelsinthetestingphase,butwillalsobeusefultowardsapplyingsuchanalysistoasoftwareapplicationthathasalreadybeendeployedandisoperational.Applyingarchitecture–basedanalysistoanoperationalsoftwareapplicationwillenableustoabstractthecurrentcharacteristicsofitsarchitectureaswellasitscomponentsintoamodel.Thesecurrentcharacteristicsmaydeviatesignificantlyfromthecharacteristicsexpectedinthedesignphaseandalsofromthecharacteristicsthatexistedjustpriortodeployment.Thesedeviationsmaybearesultoftheinevitableevolutionofthesoftwareapplication.Abstractingthecurrentcharacteristicsintoamodelcanbeusedtoanswerquestionssuchas:(i)whatwillbetheim-pactonapplicationperformanceandreliabilityifcomponentXistobereplacedbycomponentY?,and(ii)inordertoimprovetheapplicationperformanceandreliabilitywhichcomponentsshouldbetargeted?Inaddition,theanalyticalmodelcanalsobeusefulinanalyzingtheeffectofportingtheapplicationbetweendifferentplatforms.Iftheapplicationwasnotdevelopedusingacomponent–basedparadigm,butneedstobeadaptedtothecomponentworld,thenmodel–basedanalysiscanenableinformeddecisionsaboutwhichpiecesshouldbedevelopedin–house,andwhichpiecesshouldbereusedbypointingtothosepiecesthatarecriticaltoapplicationperformanceandreliability.

Thekeytorefiningarchitecture–basedmodelsinthetestingphaseortoapplytheanalysisintheoperationalphaseisingeneratingandprocessingexecutioninformationtoextracttheparametersofarchitecture–basedmodels.Thegenerationandprocessingofexecutioninfor-mationwillbeinfluencedbyseveralfactorssuchas:(i)whethertheapplicationwasdevelopedgroundup,orassembledusingacomponent–basedapproach,and(ii)whetherthesourcecodeoftheapplicationiscompletelyorpartiallyavailable.Thecurrentpaperpresentsanexper-imentalapproachtogenerateandprocesstheexecutioninformationinordertoextracttheparametersofarchitecture–basedmodelsforapplicationsdevelopedgroundupandwithcom-pleteaccesstothesourcecode.Thismethodologyneedstobeadaptedinordertobeappliedtoapplicationsassembledusingsoftwarecomponents,sincesuchapplicationstendtodifferfromtheapplicationsdevelopedgroundup.InSection3webrieflydescribehowthemethodologymaybeadaptedtoapplytocomponent–basedsoftwareapplications.Forapplicationsdevel-opedgroundup,thenotionofacomponentisnotverywell–definedandislargelyamatteroftradeoffbetweennumberofcomponents,theirsizeandhoweasilythenecessaryinformationcanbeextracted.Wedesignateasinglesourcefileasanindividualcomponentoftheappli-cation.Thisdesignationwasmotivatedbythehopethatafilewouldhostagroupofrelated

4

functionswhicharelikelytobeplacedinasinglecomponentinthecomponentizedversionoftheapplication.Thisassumptionholdsreasonablywellfortheapplicationwehaveusedforthedemonstrationofourexperimentalapproach.However,wewouldliketonotethatourexperi-mentalmethodologyisnotlimitedbythisdesignation.Infact,ourexperimentalmethodologycanextractparameters,evenifanindividualcomponentisassumedtoconsistofacollectionofasmallnumberofsourcestatements.Weelaborateonthisissuefurtherinthepaper(SeeSection3.2).Weparameterizetheanalyticalmodeloftheapplicationusingcoveragemeasure-mentsgeneratedduringtheexecutionoftheapplication.Thenoveltyoftheapproachliesinitsintegrationoftwodistinctyetimportantareas,namely,state–basedsoftwareperformanceandreliabilitymodelsandcoverageanalysis.Theexperimentalapproachthuspresentsaninitialsteptowardsaddressingtheimportantissueofhowonemightapplyanalyticalarchitecture–basedsoftwarereliabilityandperformanceanalysistoarealsoftwareapplication.

Thestate–spaceapproachusedtomodelthearchitectureoftheapplicationisadiscretetimeMarkovchain(DTMC).Coveragemeasurementsgeneratedduringtheexecutionoftheap-plicationareusedtodeterminethefailurebehaviorofthecomponentsviatheenhancednonhomogeneousPoissonprocessmodel[14].Coveragemeasurementsarealsousedtoextracttheintercomponenttransitionprobabilitiesofthearchitectureoftheapplication.OurexperimentalapproachisfacilitatedbyacoverageanalysistoolcalledATAC(AutomaticTestAnalyzerinC)whichisapartoftheTelcordiaSoftwareVisualizationandAnalysisToolSuite(TSVAT)[22].Wedemonstratethemethodologybypredictingthereliabilityandperformanceofanapplica-tioncalledSHARPE(SymbolicHierarchicalAutomatedReliabilityPredictor).SHARPEhasbeenusedtosolvestochasticmodelsofreliability,performanceandperformability[37].Thelayoutofthepaperisasfollows:Section2outlinesthedescriptionandanalysesmeth-odsofstate–basedmodelsandprovidesabriefoverviewofthevariousarchitecturalmodels,failurebehaviorofthecomponentsandthemethodologytopredictreliabilityandperformance.Section3describestheexperimentalsetup.Section4presentsresultsandthesubsequentanal-yses.Section5concludesthepaperandpresentsdirectionsforfutureresearch.

2Descriptionandanalysesofstate-basedmodels

Thedescriptionofstate–basedmodelstopredicttheperformanceandreliabilityofanappli-cationbasedonitsarchitecturerequiresknowledgeabout:

•Architectureoftheapplication:Thisisthemannerinwhichthedifferentcomponents1ofthesoftwareinteract,andisgivenbytheintermodulartransitionprobabilities.The

architecturemayalsoincludeinformationabouttheexecutiontime(mean,variance,distribution)ofeachcomponent.Thearchitectureoftheapplicationcanbemodeledei-therasaDTMC(DiscreteTimeMarkovChain)[7],CTMC(ContinuousTimeMarkovChain)[27],SMP(Semi-MarkovProcess)[26],DAG(DirectedAcyclicGraph)[45]oraSPN(StochasticPetriNet).Thestateoftheapplicationatanytimeisgivenbythecomponentexecutingatthattime,andthestatetransitionsrepresentthetransferofcon-trolamongthecomponents.DTMC,CTMC,SMPandSPNcanbefurtherclassifiedintoirreducibleandabsorbingcategories,wheretheformerrepresentsaninfinitelyrunningapplication,andthelatteraterminatingone.Thearchitectureoftheapplicationprovidestheperformancemodeloftheapplication.Analysisoftheperformancemodelcanbeusedtoobtainperformancepredictionssuchastimetocompletionoftheapplication,andidentifyperformancebottlenecks.Performancemodelscanalsobeusedtoanalyzetheeffectofportingtheapplicationtoadifferentplatform,orportingitfromasequentialplatformtoadistributedone.

•Failurebehaviorofthecomponents/interfaces:Failuremayoccurduringtheexecu-tionofanycomponentorduringthecontroltransferbetweentwocomponents.Thefailurebehaviorofthecomponentsmaybespecifiedintermsoftheprobabilityoffail-ure(orreliability),time–independentfailurerateortime–dependentfailureintensity.Itisawidelyknownfactthatinterfacefailuresorfailuresthatoccurduringthetransferofcontrolbetweentwocomponentsshouldbeconsideredseparatelyfromindividualcomponentfailures.However,verylittleinformationisavailableonhowtheparame-tersrepresentingthefailurebehavioroftheinterfacesmaybeestimated.Thefailurebehavioroftheinterfacesmayalsobespecifiedintermsoftheprobabilityoffailure,time–independentfailurerateortime–dependentfailureintensity.

Theinformationaboutthearchitectureoftheapplicationandthefailurebehaviorofitscomponentsandtheinterfacesbetweenthecomponentscanbecombinedinthefollowingtwodifferentwaystopredictapplicationperformanceandreliability.

•Compositemethod:Thearchitectureoftheapplicationcanbecombinedwiththefailurebehaviorofthecomponentsandtheinterfacesintoacompositemodelwhichcanthenbeanalyzedtopredicttheperformanceandreliabilityofanapplication.Wewillrefertothismethodofperformanceandreliabilitypredictionas“CompositeMethod”.•Hierarchicalmethod:Theotherpossibilityistosolvethearchitecturalmodelandsu-perimposethefailurebehaviorofthecomponentsandtheinterfacesontothesolutionofthearchitecturalmodel,topredictreliability.Solutionofthearchitecturalmodelpro-videstheperformancemetricsfortheapplication.Werefertothismethodas“Hierar-chicalMethod”.

6

Architecture Based Software Reliability Prediction ArchitectureFailure Behavior Failure behaviorplus solution ofarchitecture1 Architecture and failure behaviorinto a single model212Hierarchical method to predict reliability and performanceComposite method to predict reliability and performanceFigure1:Descriptionandanalysesofarchitecture–basedmodels

Theinformationrequiredforthedescriptionofstate–basedmodels,andthedifferentwaysinwhichthisinformationcanbeanalyzedinordertopredictperformanceandreliabilityaredepictedinFigure1.Anexhaustivediscussionofthecompositeandhierarchicalapproachestopredictthereliabilityofanapplicationispresentedin[15].Thespecificanalyticalmodelweusehasthefollowingfeatures:

•Architecture:ThearchitectureoftheapplicationisassumedtobemodeledbyadiscretetimeMarkovchain(DTMC).

•Failurebehavior:Failurebehaviorofthecomponentsisassumedtobecharacterizedbytime–dependentfailureintensity.Time–dependentfailureintensitywaschosentocharacterizethefailurebehaviorofthecomponentsbecauseofitsabilitytoexpressthedependenceofthefailurebehavioronthecodecharacteristicsandhowthecodeisbeingused.Inaddition,time–dependentfailureintensitycanalsocaptureintra–componentdependenceviacumulativeexecutiontime.WeelaborateontheseissuesinSection2.2andSection2.3respectively.Weassumethattheinterfacesdonotfail.Wenotethatthis

7

assumptionisnotnecessarytoensuremodeltractability.Themodelcanbeextendedtoaccommodateunreliableinterfaces.However,itisnotclearhowtheparametersrepre-sentingthefailurebehavioroftheinterfacesmaybeestimatedwhenaninterfaceconsistsofitemssuchasglobalvariables,parametersandfiles.Integrationtestingproposedin[8,9]mayholdalotofpromiseforestimatinginterfacereliabilitiesandisthetopicofourfutureresearch.

•Solutionmethod:Weusethehierarchicalmethodofsolution.AsexplainedinSec-tion2.3,analysisusingthecompositemethodisnotfeasibleforthisparticularcombina-tionofarchitecturalmodelandfailurebehavior.2.1

Architectureoftheapplication

ThearchitectureoftheapplicationismodeledusingaDTMCandwepresentabriefoverviewofDTMCsinthissection.ADTMCischaracterizedbyitsone–steptransitionprobabilityma-trix,P=[pij].ThestateprobabilityvectoroftheDTMCattimestepnisdenotedbyπ(n).

π=π.Pπ.e=1

wheree=(1,1,...,1)TandthesuperscriptTdenotesthetranspose.

Fromthepointofviewofmodelingthearchitectureofsoftwareapplications,DTMCscanbeclassifiedintothefollowingtwocategories:

•Irreducible:ADTMCissaidtobeirreducibleifeverystatecanbereachedfromeveryotherstate.AnirreducibleDTMCcanbeusedtomodelthearchitectureofaninfinitelyrunningapplication.

•Absorbing:ADTMCissaidtobeabsorbing,ifthereisatleastonestatei,fromwhichthereisnooutgoingtransition.Startingfromthestartstate,aDTMCuponreachinganabsorbingstateisdestinedtoremainthereforever.AnabsorbingDTMCcanbeusedtomodelthearchitectureofaterminatingapplicationortheonethatoperatesondemand.InthecaseofaDTMCwithoneormoreabsorbingstates,theexpectednumberoftimestheprocessvisitsstatej,denotedbyVj,canbecomputedbysolvingthefollowingsystemoflinearequations:

Vj=

󰀂

(1)(2)

Vipij+πj(0)8

(3)

whereπ(0)denotestheinitialstateprobabilityvector.

WecanusetheDTMCanalysispresentedinthissectiontoobtainperformancemeasuressuchastimetocompletionoftheapplication,identifyperformancebottlenecks,determinetheeffectofchangesintheworkload,anddeterminetheeffectofchangestoaparticularmodule,asfollows:

•Timetocompletion:Iftj,theexpectedtimespentbytheapplicationincomponentjpervisitisknown(tjcaneitherbeobtainedexperimentallyormaybeknownapriori),thenVjtjistheexpectedtotaltimespentinthecomponentjinatypicalexecutionof

¯theapplication.Foranapplicationwithncomponents,theexpectedcompletiontimet

oftheapplicationisgivenby[42]:

¯=t

n󰀂j=1

Vjtj

(4)

•Performancebottlenecks:argmax{Vjtj}istheperformancebottleneckoftheapplica-tion.Thus,wenotethatneitherVj,whichistheexpectednumberofvisitstocomponent

jduringasingleexecutionoftheapplication,nortj,whichistheexpectedtimespentbytheapplicationincomponentjpervisit,areindividuallysufficienttodeterminetheper-formancebottleneck,buttheirproductVjtjis.Thisdefinitionofperformancebottleneckisapplicableonlyinthecontextofaterminatingapplication.

•Changesintheworkload:Aworkloadpatternisdeterminedbyasetofintercomponenttransitionprobabilities.Forasoftwareapplicationthesetofintercomponenttransitionprobabilitieswillbeaffectedbytheoperationalprofile[35].Upgradestothesoftwaremayintroducenewfeaturesinanapplicationwhichmayleadtoachangeinhowtheex-istingfeaturesareused.Thismayrenderanexistingestimateoftheoperationalprofileinvalid.Whentheoperationalprofilechanges,anewsetofintercomponenttransitionprobabilitiesmaybeobtainedbyexecutingtheapplicationagainstthesampletestcasesdrawnfromthenewoperationalprofile.Anestimateoftheperformanceoftheapplica-tioncouldalsobeobtainedduringtheprocessofestimatingintercomponenttransitionprobabilities.However,theprocessoftestingandestimationwillhavetoberepeatedeverytimetheoperationalprofilechanges.Inawell–designedapplicationwheretheinteractionsamongthecomponentsislimiteditmaybepossibletodeterminewhichin-teractionsareimpactedbyachangeintheoperationalprofilebyconsultingtheexperts.Model–basedanalysismaythenbeusedtodeterminethesensitivityoftheperformance

9

andreliabilityestimatestothechangesintheintercomponenttransitionprobabilitiesamongthecomponentswhicharelikelytobeimpactedbythechangeintheoperationalprofile.Ananalyticalmodelwillenableustoobtaintheperformanceandreliabilityesti-matesforvariousvaluesofintercomponenttransitionprobabilitiesamongtheimpactedcomponentswithoutactuallyhavingtoestimatethevaluesoftheprobabilities.Estima-tionoftheintercomponenttransitionprobabilitiesandperformancemetricsbyextensivetestingcanbelengthybothintermsofcomputationtimeandresources.

•Changestoamodule:Ifasinglemodulechangeswhilepreservingitsinteractionwiththeothermodules(asdeterminedbytheintercomponenttransitionprobabilities),andalltheothermodulesremainunchanged,theoverallperformancecanbepredictedbysimplymeasuringtheexecutiontimepervisitofachangedcomponent.Thus,ifcomponentcchanges,thetimetocompletionoftheapplicationisgivenby:

t=(¯∗

n󰀂

Vjtj)+Vct∗c

(5)

j=1,j=c

InEquation(5),t∗cisthenewexecutiontimepervisitforcomponentc.Wenotethat

theexpectednumberofvisitstothecomponent,denotedbyVc,whichdependsontheintercomponenttransitionprobabilitiesremainsunchanged.Model–basedanalysiscanthusprovidethecapabilitytoassesstheimpactofachangetoamodulebyestimatingthevaluesoftheparametersonlyforthechangedmodule.Iftheperformanceoftheapplicationhadbeendeterminedempiricallybyrunningtestcasesagainsttheapplicationandaveragingoveralltheruns,thenassessingtheimpactofachangetoamodulewouldrequireustorepeattheempiricalprocedure.Repetitionoftheempiricalprocedureislikelytobemorecostlythanestimatingthevaluesoftheparametersforthechangedmodule.

2.2Failurebehaviorofthecomponents

Intuitively,thefailurebehaviorofacomponentwilldependonthecodecharacteristicsofthecomponentandhowthecomponentisbeingused.Empiricalevidencehassupportedtheconjecturethatthefailurebehaviorishighlycorrelatedwithcodecoverage[5,6,12,34].Codecoveragecanthusbeausefulmeasuretocapturehowthecomponentisbeingused.Henceweusetime–dependentcodecoverageasaparameterinastatisticalmodeltoestimatethefail-ureintensityofthecomponent.Thecharacteristicsofthecodecanbecapturedbyestimatingthenumberoffaultsinthecomponentbasedonsoftwaremetrics.Weestimatethenumberoffaultsineachcomponentbasedonthenumberoflinesofcodeinthecomponentusingthefaultdensityapproach[30].

10

TheenhancednonhomogeneousPoissonprocess(ENHPP)model[14]relatesthefailureintensityofacomponenttotheexpectednumberoffaultsresidinginthecomponentanditstime–dependentcoveragebehavior.Thisrelationshipisexemplifiedbythefollowingexpres-sion:

λ(t)=ac(t)(6)

′

whereaistheexpectednumberoffaultspresentinthecomponentandc(t)isthefirstderivativeoftheexpectedcoveragebehaviorc(t)ofthecomponent.

Thereliabilityofacomponentj,denotedbyRj,giventhefailureintensityofthecomponent,andtheexpectedtimespentinthemoduleγj(whereγj=Vjtj),is:Rj=e0λj(θ)dθ

FromEquation(6),Equation(7),canbewrittenas:

Rj=e

2.3

Methodofanalyses

−

′

󰀁γj

(7)

󰀁γj

0

ajcj(θ)dθ

′

=e−ajcj(γj)

(8)

Inthissection,wemotivatethechoiceofthehierarchicalmethodofanalysesforanap-plicationwitharchitecturemodeledbyaDTMC,andthefailurebehaviormodeledbythetime–dependentfailureintensitywiththehelpofanexample.WhenthearchitectureoftheapplicationismodeledbyadiscretetimeMarkovchain(DTMC)andthefailurebehaviorofthecomponentsarecharacterizedbytheirreliabilitiesacompositemethodofanalysesispos-sibleasdiscussedbyCheung[7].However,characterizingthefailurebehaviorofacomponentbyitsreliabilitycannottakeintoconsiderationhowthecomponentisbeingused.Asdiscussedearlier,time–dependentfailureintensityexpressedasacompositionofthenumberoffaultsinthecomponentandtime–dependentcoveragebehaviorcantakeintoconsiderationboththefactorsthataffectcomponentfailures,namely,thecodecharacteristicsandthehowthecodeisbeingused.Asaresult,wecharacterizethefailurebehavioroftheindividualcomponentsbytheirtime–dependentfailureintensities.

Consideranapplicationwiththreecomponents.Thearchitectureoftheapplicationisde-scribedbytheDTMCshownontheleftinFigure2.Letthefailureintensityofcomponentjbedenotedbyλj(t),andγjbethecumulativetimespentbytheapplicationincomponentjfromthebeginningofsystemoperation.Combiningthearchitectureandthefailurebehavioroftheapplication,givesrisetoacompositereliabilitymodelasshownontherightinFigure2,wherethestateFindicatesthefailureoftheapplication.However,sincesuccessivesojournsinagivenstatearenotingeneralcontiguous,thereliabilitymodelshownontherightinFigure2

11

isacomplexstochasticprocess(itisnotanon–homogeneousCTMCnorisitasemi–Markovprocess)thatcannotbeanalyzedusingcompositemethods.

1 1λ1(γ1)p12 2p21p12 2p21λ2(γ2)Fp23p23λ3(γ3) 3 3Figure2:Compositereliabilitymodel

Theanalysisismuchsimplerusinghierarchicalmethodofanalyses,bywhichthereliabilityoftheapplication,denotedbyRisgivenby:

R=

whereRjisthereliabilityofmodulej.

Thus,thereliabilityoftheoverallapplicationisgivenby:

R=

3󰀃j=1

3󰀃j=1

Rj

(9)

e

−

󰀁γj

0

λ(θ)dθ

(10)

Equation(10)canbegeneralizedtocomputethereliabilityofanapplicationwithncompo-nents,andisgivenby:

R=

n󰀃j=1

e

−

󰀁γj

0

λ(θ)dθ

(11)

FromEquation(8),Equation(11)canbewrittenas:

R=

n󰀃j=1

e−ajcj(Vjtj)

(12)

12

Equation(10)assumesinter–componentindependence[25],thatis,theexecutionofonecomponentdoesnotinanywayaffectthefailurebehaviorofanyothercomponent,anas-sumptionwhichunderliesmoststate–basedsoftwarereliabilityandperformancemodels.Theexecutionofonecomponentcouldaffectthefailurebehaviorofanothercomponentduetoer-rorpropagationviadataflow.Henceerrorpropagationviadataflowcouldbeanimportantfactorinfluencingapplicationreliability.Thepath–basedmodelproposedbySingpurwallaet.al.[41]considerserrorpropagationviadataflowalongwiththecontrolflowoftheapplica-tion.However,path–basedmodelsareunabletoaccountfortheinfinitenumberofpathsthatmightexistduetotheexistenceofloopsinthecontrolflowgraph.State–basedmodelscananalyticallyaccountfortheinfinitenumberofpaths.Developingstate–basedmodelswhichaccountforerrorpropagationviadataflowisasubjectofourfutureresearch.Theeffectsoferrorpropagationduetodataflowcanbequantifiedusingfaultinsertiontesting[21,43].Modelingthefailurebehaviorofacomponentusingtime–dependentfailureintensityen-ablesustocaptureintra–componentdependence[25]asexplainedbelow.Intra–componentdependencecanariseforexample,whenacomponentisinvokedmorethanonceinaloop.Re-liabilityvaluesassumingintra–componentindependenceareingeneralpessimisticaspointedoutbyKrishnamurthyet.al.[25].Theyresolvetheissuebycollapsingmultipleexecutionsofthesamecomponentintokoccurrenceswherekisdefinedasthedegreeofindependence.Ifthefailurebehavioroftheindividualcomponentsismodeledbyatime–dependentfailureintensitythenitispossibletocaptureintra–componentdependenceviacumulativeexecutiontimespentinacomponent.Thereliabilityvalueobtainedassumingintra–componentinde-pendenceisingeneralpessimisticascomparedtothereliabilityvaluewhichisbasedonthecumulativetimespentinthecomponent.Weillustratethiswiththehelpofanexampleasfollows:Consideracomponentwhosefailurebehavioriscapturedbythefailureintensityfunctionλ(t)=34.05∗0.0057∗e(−0.0057∗t).Weassumethatduringaparticularrun,thecomponentisvisitedtwice,and50timeunitsarespentinthecomponentpervisit.Thusatotalof100timeunitsisspentinthecomponentduringthisparticularexecution.Thefailurein-tensitiesassumingintra–componentindependence,andintra–componentdependencecapturedviathecumulativeexecutiontimeapproachareasshownintheFigure3.Thereliabilityofthecomponentassumingintra–componentindependenceis0.84,andintra–componentdepen-dencecapturedviathecumulativetimeapproachis0.86.Time–dependentfailureintensitythusprovidesanabilitytocaptureintra–componentdependence.

Equation(11)indicatesthatthereliabilityoftheapplicationR→1.0asγj’s→0,forallj.ThisisconsistentwiththesoftwarereliabilitymodelproposedbySingpurwallaet.al.[41]whichcanbeexpressedasthefollowing:

13

21.81.61.41.210.80.60.40.20x 10−3Failure intensity for two executions Indep. Executions ActualFailure Intensity01020304050Time60708090100Figure3:Failureintensity–independentexecutionandcumulativetime

P(ε|H)=P(ε|Θ)P(Θ|H)(13)

InEquation(13)P(ε|H)isthereliabilitymodelofthesoftwareconditionaltotheback-groundinformationH.Θisknownastheparameterspaceofthereliabilitymodelandisinter-pretedasadeviceforsummarizingthebackgroundinformationH.InthecontextofEquation(11),thebackgroundinformationoftheapplicationcanbeviewedtohavetwopossibilities:(i)theapplicationisexecuted,(ii)theapplicationisnotexecuted.Thus,theparameterspaceΘintendedtocapturethebackgroundinformationinthiscaseconsistsofγj’s.Thus,γjisequaltozeroforalljiftheapplicationisnotexecutedatallresultinginareliabilityof1.Atleastoneγjwillbegreaterthanzeroiftheapplicationisexecutedresultinginareliabilityvalueoflessthanorequalto1.0.

Equation(12)expressestheoverallreliabilityofanapplicationintermsofthefailurebe-haviorofitsindividualcomponentsandarchitecturalcharacteristics.Thisapproachisveryvaluabletoidentifyreliabilitybottlenecks,aswellastheeffectofchangesinasinglemodule,asdiscussedbelow:

•Reliabilitybottlenecks:Reliabilitybottleneckisgivenbyargmax{ajcj(Vjtj)}.Thus,thecodecharacteristicsofthecomponentandthecoveragebehaviorwhichcaptureshowthecomponentisbeingused,togetherdeterminethereliabilitybottleneck.Thisdefini-tionofreliabilitybottleneckisapplicableonlyinthecontextofterminatingapplications.•Changestoamodule:Ifasinglemoduleischangedwhilepreservingalltheotheras-pectsoftheapplication,namely,theintercomponenttransitionprobabilities,andfailurebehavioroftheotherunchangedcomponents,thereliabilityoftheapplicationisgivenby:

14

R=(

∗

n󰀃

e−ajcj(Vjtj))e−accc(Vctc)

∗∗∗∗

(14)

j=1,j=c

∗∗∗wherea∗ccc(Vctc),isthemeanvaluefunctionofthechangedcomponent.Wenotethat

model–basedanalysisrendersitselfwelltoevaluatetheimpactofachangetoamodulebyestimatingtheparametersofthechangedmodule.Ifthereliabilityoftheapplicationweretobedeterminedempirically,thenachangetoamodulewouldrequiretherepetitionoftheempiricalprocedureinordertoevaluatetheimpactofthechangeinamodule.

3Experimentalmethodology

Inthissectionwedescribetheexperimentalmethodologytoobtaintheinformationnec-essaryforarchitecture–basedanalysis.Inparticular,theexperimentalmethodologyseekstoobtain:

•Architectureoftheapplicationascharacterizedbyitsintercomponenttransitionproba-bilities.

•Time–dependentcoveragebehaviorofeachcomponent.3.1

Selectingtheapplication

TheSymbolicHierarchicalAutomatedReliabilityandPerformanceEvaluator(SHARPE)[37]thatsolvesstochasticmodelsofreliability,performance,andperformabilitywasselected.Thisapplicationwasfirstdevelopedin1986forthreegroupsofusers:practicingengineers,re-searchersinperformanceandreliabilitymodeling,andstudentsinscienceandengineeringcourses.Sincethenseveralrevisionshavebeenmadetofixbugsandadoptnewrequirements.ThecurrentreleaseofSHARPEisalmostbugfree.Itcontains35,412linesofCcodein30filesandhasatotalof373functions.ThenumberoflinesofcodeineachfileofSHARPEissummarizedinTable1.EachofthesefilesisregardedasasinglecomponentforSHARPE.Thechoiceofdesignatingafileasacomponentwasbasedonatradeoffbetweenthenumberofcomponents,theirsizeandtheeasewithwhichthenecessarydatacanbecollected.Itwasalsoduetothefactthateachfilehostsagroupofrelatedfunctionswhichwouldbeplacedinasinglecomponent,hadtheoriginaldesignofSHARPEbeencomponent–based.3.2

Executingtheapplication

Asuiteof735testcasescreatedbydevelopersandtestersfortestingmodificationstotheexistingfunctionalityaswellasnewenhancementsinpreviousreleasesofSHARPEwasiden-tifiedtoexecutetheapplication.ATAC,whichisapartofTelcordiaSoftwareVisualizationandAnalysisToolSuite(TSVAT)[22]wasusedtomeasurecoverageduringtheexecutionof

15

Table1:LinesofcodeforcomponentsofSHARPE

Comp.analyze.c

387

share.c

1155

reachgraph.c

1142

util.c

880

indist.c

259

symbol.c

819

newlinear.c

621

ftree.c

315

sor.c

1957

cexpo.c

1292

cg.c

2358

newcg.c

1271

Comp.inshare.c

1322

Comp.maketree.cqninchain.c

1246383

theapplicationwiththesetestcases.CoveragemeasurementsalsoenabledustoassesshowwellthecodeofSHARPEcouldbecoveredbythissuite.TheuseofATACfocusesonthreemainactivities:instrumentingthesoftware,executingsoftwaretests,andmeasuringcoveragetodeterminehowwellthecodehasbeencovered.Instrumentationofthesoftwareoccursatcompile–time,andATACallowslargesystemstobeinstrumentedapieceatatime.Onceinstrumentationiscompleteandanexecutablehasbeenbuilt,testcasescanbeexecutedandATACtogeneratereportsordisplayuncoveredsourcecode.Thereportsrevealthecurrentcov-eragemeasureswithrespecttoselectedcriteria2,indicatinghowadequatetheexistingtestsetis.Inourexperiments,weusedblockcoverage,sincethisisthemostbasicformofcoveragethatcanbemeasuredusingATAC.

Abasicblock,orsimplyablock,isasequenceofinstructionsthat,exceptforthelastin-struction,isfreeofbranchesandfunctioncalls.Theinstructionsinanybasicblockareeitherexecutedalltogether,ornotatall.3Ablockmaycontainmorethanonestatementifnobranch-ingoccursbetweenstatements;astatementmaycontainmultipleblocksifbranchingoccursinsidethestatement;anexpressionmaycontainmultipleblocksifbranchingisimpliedwithintheexpression.Givenaprogramandatestset,theblockcoverageisthepercentageofthetotalnumberofblocksintheprogramexercisedbythetestset.Inourcase,theoverallblockcover-ageforall735testcasesonSHARPEis93.5%.TheindividualcoverageforeachcomponentislistedinTable2.

Block–levelcoveragemeasurementsobtainedduringtheexecutionoftheapplicationareusedtoobtainthetime–dependentcoveragebehaviorforeachcomponentasdescribedinSec-tion3.3.Theyarealsoaggregatedtodetermineinteractionsamongthefunctions,andsubse-quentlyamongthefilesoftheapplicationasdescribedinSection3.4.Wewouldliketonote

Table2:BlockcoverageforcomponentsofSHARPE

Comp.analyze.c

98.0

bitlib.c

87.9

cg.c

69.1

expo.c

93.4

in

pn.c

99.5

newlinear.c

95.4

multpath.c

85.2

uniform.c

85.7

mpfqn.c

95.5

sor.c

97.5

inspade.c

99.4

results.c

93.2

Comp.indist.c

97.5

reachgraph.c

97.9

Comp.pfqn.c

90.6

thattheproposedmethodologyusesblock–levelcoveragemeasurementssincetheyarereadilyavailablefromthecoverageanalysistool.However,block–levelcoveragemeasurementsarenotimperativetotheuseofthismethodology.Sincetheblock–levelcoverageinformationissubsequentlycondensedtoobtainthetime–dependentcoveragebehaviorforthewholecom-ponent,anyprofilingtoolwhichreportscoverageinformationonaperfunctionbasiswouldalsoprovidenecessaryinformation.Similarly,sinceblock–levelcoverageinformationisag-gregatedtodeterminetheinteractionsbetweenfunctionsandfiles,anyprofilerwhichrecordssimilarexecutioninformationforindividualfunctionscouldalsoprovidetheinformationnec-essaryfordeterminingtheinteractions.Forapplicationsdevelopedusingcomponent–basedsoftwareengineeringparadigm,monitoringthecomponentsattheirboundariesbyrecordingtheeventsoriginatingfromthecomponentscouldalsoprovidethenecessaryinformationtodeterminethearchitectureoftheapplication.Ifthesourcecodeofthecomponentisavailabletheninstrumentingthesourcecodeandcollectingexecutionprofileswillprovidethecoverageinformationnecessaryfordeterminingcoveragebehavior.Intheeventthatthesourcecodeisnotavailable,theninstrumentationoftheobjectcodecouldprovidethenecessarycoveragedata.3.3

Determiningfailurebehaviorofthecomponents

AsexplainedinSection2.2,todeterminethefailurebehaviorofthecomponents,weneedtoobtaintheexpectedcoverageasafunctionoftimeandtheexpectednumberoffaultsforeachcomponent(seeEquation(6)).Wefirstdescribehowtoobtaintheexpectedcoveragebehaviorforeachcomponent:

TheexecutiontimeforeachtestisthedifferencebetweenitsstartingandendingtimewhichcanbeobtainedfromtheATACtracefile.Theexpectedcoverageiscomputedbyrunningthe

17

applicationmultipletimeswiththesamesuiteoftestcasesbutindifferentorderingandaver-agingcoveragesoveralltheseruns.Stateddifferently,eachsinglerungivesonerealizationofblockcoverageovertime;anaverageoveranumberofsuchrunswascomputedtogivetheexpectedcoverageasafunctionoftime.Toavoidanypossiblebias,thetestorderingforeachrunwasgeneratedrandomly.

Wenowuseanexampletoexplainthestepsoutlinedabove.Givenanapplicationwithtwotests,t1andt2,supposethereare20blocksintheapplication:10ofthemarecoveredbyt1,5byt2,and3byboth.Assumealsotheexecutiontimefort1andt2is2secand3sec,re-spectively.Dependingonwhichtestisexecutedfirst,theblockcoveragemayvarywithtimeasshowninthefirsttwopartsofTable3.ThethirdpartofTable3showstheexpectedblockcoverage,whichistheaverageoftheblockcoverageovertherunsinthefirsttwotables.Sincerepeatedexecutionoftheapplicationwithabigtestsetisverycostly,atradeoffistouseitsblockminimizedsubsetwhichistheminimalsubsetintermsofthenumberoftestcasesthatpreservestheblockcoverageoftheoriginaltestset.Inourcase,thenumberoftestsisreducedfrom735to275becauseofaminimizationwithrespecttotheblockcoverage.Theexpectednumberoffaultsineachcomponentcanbeobtainedusingavarietyofap-proaches.Itmaybeestimatedbasedonthefailuredatacollectedduringunittestingofeachcomponent.Itmayalsobeestimatedbasedonthesoftwaremetricsofthecomponent.Wees-timatetheexpectednumberoffaultsineachcomponentusingthefaultdensityapproach[30](SeeSection4fordetails).Wenotethatthefaultdensityapproachisaspecificexampleofthebroadclassofapproachesthatarebasedonsoftwaremetrics.3.4

Determiningthearchitectureoftheapplication

Thearchitectureoftheapplicationintermsoftheintercomponenttransitionprobabilitiesisdeterminedbasedonthefollowingprotocol:weassumethatwhenafunctionAcallsanotherfunctionB,controliseventuallytransferredbacktofunctionA,exceptforwhentheappli-cationterminatessuccessfully,orthereisanerrorintheinputspecificationorofsomeotherformwhichcausestheapplicationtoterminateabnormally.Underthesesituations,thecontrolistransferredtotheterminatingstate.Thus,therearetwoterminatingstates−−onerepre-sentsnormalterminationandtheotherrepresentsabnormaltermination.Foreveryblock,thefollowingpossibilitiesexist:

•Iftheblockhasneitherafunctioncallnorareturnstatement,thenuponcompletionoftheblock,controlistransferredtothenextblockwhichisphysicallycontiguous.Inthis

18

Table3:Blockcoveragewithrespecttotimeforasampleprogramandtestset

Executionordering:t1followedbyt2

Block

(second)0

0

2

50

4

60

Time

coverage(%)

0

1

0

3

25

5

ExpectedblockcoverageExpected

(second)0

0

2

37.5

4

60

START file.1file.2file.3TFigure4:Anexampleoffileleveltransitions

casewesaythatthecontrolistransferredtoanotherblockinthesamefile,oratthefilelevelofgranularitywesaythatthecontrolistransferredbacktothesamefile.Iftheblockhappenstobethelastblockinthefile,thenthecontrolistransferredbacktothefilewhichcalledthecurrentfile.

•Iftheblockhasafunctioncalltooneoftheuser–definedfunctions4,whichmayormaynotbeinthesamefile,thenthecontrolistransferredtothefirstblockofthecalledfunction,andwesaythatthecontrolistransferredtothefileinwhichthecalledfunctionresides.

Withthisassumption,thebranchingprobabilitiesforthecontrolflowgraphofSHARPEwerecomputedbasedontheexecutioncountsextractedfromtheATACtracefiles.Theexe-cutioncountswerefirstobtainedatthefinestlevelofgranularity,i.e.,theblocklevel,andarecombinedlatertoobtaintheexecutioncountsandprobabilitiesatthefilelevel.

Weillustratethismethodwiththehelpofanexample.Supposeanapplicationconsistsofthreefiles,file.1,file.2andfile.3:file.1hastwoblocks,B11andB12,file.2hasthreeblocks,B21,B22andB23,andfile.3hastwoblocks,B31andB32.TheapplicationbeginsbyexecutingblockB11,whichcallsauser–definedfunctioninfile.2,ofwhichthefirstblockisB21.Thistransferscontroltofile.2.AssumeB21containsnofunctioncall.Hence,thenextblockB22getsexecuteduponcompletionofB21.SupposeB22callsauser–definedfunctioninfile.3whichbeginsatB31.AssumeB31executesandpassescontrolsequentiallytoB32,whichreturnscontroltofile.2atblockB23,whichthenreturnscontroltofile.1atblockB12.ThisapplicationterminatesuponcompletionofblockB12.Thus,thecallingsequenceattheblocklevelisgivenbythefollowing:B11,B21,B22,B31,B32,B23,B12,whereasthecallingsequenceatthefilelevelisfile.1,file.2,file.2,file.3,file.3,file.2,file.1,T.ThefileleveltransitionsinthisscenarioareasshowninFigure4,whereTindicatestheterminating

Block coverage vs. Time1009080706050403020100Single runAverageBlock coverage02004006008001000Time12001400160018002000Figure5:Coveragebehaviorasafunctionoftimeforshare.c

stateoftheapplication.

Afterobtainingthefileleveltransitions,weproceedtocomputethebranchingprobabilitiesusingexecutioncounts.Weexplainthemethodologyusedtoobtainthebranchingprobabilitiesbycomputingthemforfile.1.Supposeeachblockintheapplicationisexecuted10times.SinceblockB11isexecuted10times,andithasacalltoauser–definedfunctioninfile.2thefirstblockofwhichisB21,wesaythatfile.1callsfile.210times.BlockB12isalsoexecuted10times,anduponcompletionofB12theapplicationterminates.Thus,file.1transferscontrol10timestofile.2,and10timestotheterminatingstateT.Asaresult,file.1callsfile.2withprobability0.5,andcallstheterminatingstatewithprobability0.5.Branchingprobabilitiescanbecomputedforfile.2andfile.3usingsimilararguments.

4Resultsandanalyses

Theapplication5wasexecutedusingtheminimaltestsetasexplainedinSection3.3with40randomorderingsofthetestcases.Thecoveragewasmeasuredforeachfileduringeachrun.Theexpectedcoverageasafunctionoftimewasthencomputedbyaveragingoverthese40runsforeachfile.Thecoveragefor5individualrunsandtheaverageover40runsisshowninFigure5forshare.c

Givenmeasuredcoverage,toobtainthefailurebehaviorofanindividualcomponent,weneedanestimateoftheexpectednumberoffaultsaiinthecomponent.Weobtainthisestimate

usingthefaultdensityapproach[20].Sincetheapplicationismature,andhasbeeninuseatseveralhundredlocationswithoutanyknownproblems,weassumethefaultdensity(FD)tobe4per1000linesofcode[20].Theexpectednumberoffaultsincomponenti,denotedbyaiisgivenby:

ai=

FD∗li

Table4:ExpectedtimepercomponentofSHARPE

Comp.analyze.c

0.0002

share.c

3.4439

reachgraph.c

0.0010

util.c

0.0014

indist.c

0.0001

symbol.c

0.1149

newlinear.c

0.0125

ftree.c

0.0047

sor.c

0.0450

cexpo.c

0.6076

cg.c

0.1037

newcg.c

0.0005

Comp.inshare.c

0.0053

Comp.maketree.cqninchain.c

0.00080.0010

Table5:Meanvaluefunction(MVF)percomponentofSHARPE

Comp.analyze.c

0.00

share.c

0.0011

reachgraph.c

3.6359e-07

util.c

6.4805e-07

indist.c

0.00

symbol.c

0.0

newlinear.c

7.3790e-07

ftree.c

1.0705e-06

sor.c

0.00

cexpo.c

3.3561e-04

cg.c

2.6885e-05

newcg.c

0.00

Comp.inshare.c

2.1899e-06

Comp.maketree.cqninchain.c

1.9109e-070.00

tobelarge,smallvariationsintheexecutiontimesofeachblockarelikelytoaverageout.Wecomputetheexpectedexecutiontimeofablockusingthefollowingequation:

EB=

TT

4.1Validation

Theperformanceestimateorthemeantimetocompletionoftheapplicationobtainedfromourexperimentwasvalidatedusingthemeantimetocompletioncomputedempirically.IfthetotaltimetakentoexecuteRtestcasesisQ,theempiricalmeantimetocompletion(ETTC)canbecomputedusingthefollowingexpression:

ETTC=

Q

Reliability for variations in fault density for all components10.9950.99Reliability0.9850.980.97501234Fault Density5678Figure7:Effectofvariationsinfaultdensityoftheentireapplication

TherelativepriorityofeachcomponentcanbedeterminedfromtheirmeanvaluefunctionslistedinTable5,wherethecomponentwiththehighestmeanvaluefunctionismostcriticaloristhe“reliabilitybottleneck”.Fromthetable,itcanbeseenthatthecomponentpfqn.cisthereliabilitybottleneck.

4.2Sensitivityanalysis

Theapproachpresentedinthispaperallowsustocapturethedependencebetweenoverallapplicationperformance(reliability),applicationarchitecture,andtheperformance(reliability)behaviorofitsindividualcomponentsintoaparameterizedanalyticalmodel.Thisparameter-izedanalyticalmodelcanbeveryvaluabletoconductsensitivityanalysis,ortoanalyzetheimpactofthevariationintheperformance(reliability)parametersfortheindividualcompo-nentsontheoverallapplicationperformance(reliability).Wedemonstratetheeaseofuseofaparameterizedanalyticalmodelsforsensitivityanalysisusingthefollowingtwoexamples:Todeterminetheeffectofthevariationinfaultdensityoftheentireapplicationonthere-liabilityestimateobtainedusingourapproach,wecomputedthereliabilityforvariousvaluesofthefaultdensity.Figure7showsreliabilityoftheapplicationvs.faultdensity.Ascanbeseenfromthisfigure,thereliabilityoftheapplicationdropswithincreasingfaultdensity.Thisanalysiscanhelpusansweraquestionsuchas:whatisthepercentageincreaseinthereliabilityifthefaultdensityoftheapplicationisreducedfrom4.0to1.0?

Typically,inacomponentbasedsoftwaredevelopmentscenario,someofthecomponentsaredevelopedinhouse,whilesomearepickedofftheshelf.Thefailurebehaviorofthecom-ponentspickedofftheshelfiscertified,andwehaveinformationregardingthefailurebehavior

25

Reliability for variations in fault density for component pfqn.c10.995Reliability0.990.98501234Fault Density5678Figure8:Effectofvariationsinfaultdensityofpfqn.c

ofthecomponentsthataredevelopedinhouse.Inaddition,thearchitectureoftheentireap-plication(intermsofinteractionsamongthevariouscomponents)isknown.Wewouldliketoassessthesensitivityofthereliabilityestimatetothevariationsinthefailurebehavioroftheoff–the–shelfcomponent.Thefailurebehaviorofthecomponentcanvaryduetothevari-ationsinitsfaultdensity.Withoutlossofgenerality,weassumethatthecomponentpfqn.cwaspickedofftheshelf.Thereliabilityoftheapplicationforvariationsinthefaultdensityofpfqn.c,isshowninFigure8.Asexpected,thereliabilitydecreaseswithincreasingvaluesoffaultdensityofthecomponentpfqn.c.BasedonsuchanalysiswecananswerquestionssuchaswhatisthepercentageincreaseinapplicationreliabilityifcomponentAisprocuredfromvendorXasopposedtovendorY,sinethecomponentfromvendorXhasahigherreli-abilitythanthecomponentfromvendorY,butthishigherreliabilitycomesatanincreasedcost?

5Conclusionsandfutureresearch

Inthispaperwehavedescribedanexperimentalapproachtoextracttheparametersofananalyticalarchitecture–basedsoftwareperformanceandreliabilitymodelbasedontheinfor-mationobtainedfromtheexecutionofanapplication.Theexperimentalapproachcanbeusedforapplicationsthataredevelopedinagroundupmannerandprovidecompleteaccesstothesourcecode.Weusecoveragemeasurementsobtainedduringtheexecutionoftheapplicationtoextractparameters.WehavedemonstratedourexperimentalapproachusingtheSymbolicHierarchicalAutomatedReliabilityandPerformanceEvaluator(SHARPE).Wehaveillustratedhowaparameterizedanalyticalmodelcanbeusedforsensitivityanalysisaswellastoidentifyperformanceandreliabilitybottlenecksinanapplication.

26

Ourfutureresearchincludesdesigningandconductingexperimentstovalidatetherelia-bilitypredictionsobtainedusingthisapproach.Experimentalverificationoftheassumptionsunderlyingvariousarchitecture–basedsoftwarereliabilitymodelsisalsocurrentlyunderway.Developmentofempiricalmethodologiestoparameterizethearchitecture–basedperformanceandreliabilitymodelsofapplicationsdevelopedusingthecomponent–basedsoftwaredevelop-mentparadigmisalsoasubjectoffutureresearch.

6Acknowledgments

TheauthorswishtothankDr.RobinSahnerforprovidingtheregressiontestsuiteforSHARPE.TheauthorsalsowishtoacknowledgetheTSVATteamatTelcordiaTechnologies,especiallySaulLondon,forhisinvaluablehelpandguidanceintheuseofATAC.

References

[1]“COM”.http://ww.microsoft.com/com.

[2]“CORBA3.0”.http://www.omg.org/news/pr98/component.html.[3]“EnterpriseJavaBeans”.http://java.sun.com/products/ejb.[4]“JavaBeans”.http://www.sun.com/beans/spec.html.

[5]M.Chen,M.R.Lyu,andE.Wong.“Anempiricalstudyofthecorrelationbetweencode

coverageandreliabilityestimation”.InProc.ofMETRICS’96,pages133–141,Berlin,Germany,March1996.[6]M.H.Chen,M.R.Lyu,andW.E.Wong.“Effectofcodecoverageonsoftwarereliability

measurement”.IEEETrans.onReliability,50(2):165–170,June2001.[7]R.C.Cheung.“Auser–orientedsoftwarereliabilitymodel”.IEEETrans.onSoftware

Engineering,SE-6(2):118–125,March1980.[8]M.E.Delamaro,J.C.Maldonado,andA.P.Mathur.“Integrationtestingusinginterface

mutation”.InProc.ofSeventhIntl.SymposiumonSoftwareReliabilityEngineering,pages112–121,WhitePlains,NY,October1996.[9]M.E.Delamaro,J.C.Maldonado,andA.P.Mathur.“Interfacemutation:Anapproach

forintegrationtesting”.IEEETrans.onSoftwareEngineering,27(3):228–247,March2001.[10]W.W.Everett.“Softwarecomponentreliabilityanalysis”.InProc.ofApplicationSpecific

SoftwareEngineeringandTechnology,Dallas,TX,March1999.

27

[11]W.Farr.HandbookofSoftwareReliabilityEngineering,M.R.Lyu,Editor,chapter“Soft-wareReliabilityModelingSurvey”,pages71–117.McGraw-Hill,NewYork,NY,1996.[12]F.DelFrate,P.Garg,A.Mathur,andA.Pasquini.“Onthecorreleationbetweencode

coverageandsoftwarereliability”.InProc.SixthIntl.SymposiumonSoftwareReliabilityEngineering,pages124–132,Tolouse,France,October1995.[13]S.Gokhale,M.R.Lyu,andK.S.Trivedi.“Reliabilitysimulationofcomponent-based

softwaresystems”.InProc.ofNinthIntl.SymposiumonSoftwareReliabilityEngineering(ISSRE98),pages192–201,Paderborn,Germany,November1998.[14]S.Gokhale,T.Philip,P.N.Marinos,andK.S.Trivedi.“Unificationoffinitefailure

non-homogeneousPoissonprocessmodelsthroughtestcoverage”.InProc.Intl.Sypmo-siumonSoftwareReliabilityEngineering(ISSRE96),pages289–299,WhitePlains,NY,October1996.[15]S.GokhaleandK.S.Trivedi.“Structure–basedsoftwarereliabilityprediction”.InProc.

ofFifthIntl.ConferenceonAdvancedComputing(ADCOMP97),pages447–452,Chen-nai,India,December1997.[16]K.Goseva-Popstojanova,A.P.Mathur,andK.S.Trivedi.“Comparisonofarchitecture–

basedsoftwarereliabilitymodels”.InProc.ofIntl.SymposiumonSoftwareReliabilityEngineering,HongKong,November2001.[17]K.Goseva-PopstojanovaandK.S.Trivedi.“Architecture–basedapproachtoreliability

assessmentofsoftwaresystems”.PerformanceEvaluation,45(2-3),June2001.[18]D.Hamlet.“Arewetestingfortruereliability?”.IEEESoftware,13(4):21–27,July

1992.[19]D.Hamlet,D.Woit,andD.Mason.“Theoryofsoftwarereliabilitybasedoncompo-nents”.InProc.ofIntl.ConferenceonSoftwareEngineering,pages361–370,Toronto,Canada,2001.[20]M.Hecht,D.Tang,H.Hecht,andR.W.Brill.“Quantitativereliabilityandavailability

assessmentforcriticalsystemsincludingsoftware”.InProc.ofComputerAssurance’97,pages147–158,Gatheirsburg,Maryland,June1997.[21]M.Hiller,A.Jhumka,andN.Suri.“Anapproachforanalysingthepropagationofdata

errorsinsoftware”.InProc.ofDependableSystemsandNetworks,June2001.

28

[22]J.R.HorganandS.London.“ATAC:Adata-flowcoveragetestingtoolforC”.InProc.of

SecondSymposiumonAssessmentofQualitySoftwareDevelopmentTools,pages2–10,NewOrleans,Louisiana,May1992.[23]J.R.HorganandS.A.London.“DataflowcoverageandtheClanguage”.InProc.ofthe

FourthAnnualSymposiumonTesting,AnalysisandVerification,pages87–97,Victoria,BritishColumbia,Canada,October1991.[24]J.R.HorganandA.P.Mathur.HandbookofSoftwareReliabilityEngineering,M.R.Lyu,

Editor,chapter“SoftwareTestingandReliability”,pages531–566.McGraw-Hill,NewYork,NY,1996.[25]S.KrishnamurthyandA.P.Mathur.“Ontheestimationofreliabilityofasoftwaresystem

usingreliabilitiesofitscomponents”.InProc.ofEighthIntl.SymosiumonSoftwareReliabilityEngineering,pages146–155,Albuquerque,NewMexico,November1997.[26]P.Kubat.“Assessingreliabilityofmodularsoftware”.OperationsResearchLetters,

8(35–41),1989.[27]J.C.LaprieandK.Kanoun.HandbookofSoftwareReliabilityEngineering,M.R.Lyu,

Editor,chapter“SoftwareReliabilityandSystemReliability”,pages27–69.McGraw-Hill,NewYork,NY,1996.[28]J.LedouxandG.Rubino.“Acountingmodelforsoftwarereliabilityanalysis”.IASTED

JournalonSimulation,1997.[29]J.LedouxandG.Rubino.“Simpleformulasforcountingprocessesinreliabilitymodels”.

TheoryofAppliedProbability,1997.[30]M.Lipow.“Numberoffaultsperlineofcode”.IEEETrans.onSoftwareEngineering,

SE-8(4):437–439,July1982.[31]B.Littlewood.“AreliabilitymodelforMarkovstructuredsoftware”.InProc.1975Int’l

Conf.ReliableSoftware,pages204–207,LosAngeles,CA,April1975.[32]B.Littlewood.“Asemi–Markovmodelforsoftwarereliabilitywithfailurecosts”.In

Proc.Symp.Comput.SoftwareEngineering,pages281–300,PolytechnicInstituteofNewYork,April1976.[33]B.Littlewood.“Softwarereliabilitymodelformodularprogramstructure”.IEEETrans.

onReliability,R-28(3),August1979.

29

[34]Y.K.Malaiya.“Therelationshipbetweentestcoverageandreliability”.TechnicalRe-portCS-94-110,Dept.ofComputerScience,ColoradoStateUniversity,Colorado,March1994.[35]J.D.Musa.“Operationalprofilesinsoftware-reliabilityengineering”.IEEESoftware,

10(2):14–32,March1993.[36]D.L.Parnas,P.C.Clements,andD.M.Weiss.“Themodularstructureofcomplex

systems”.IEEETrans.onSoftwareEngineering,SE-11(3):259–266,March1985.[37]R.A.Sahner,K.S.Trivedi,andA.Puliafito.PerformanceandReliabilityAnalysisof

ComputerSystems:AnExample-BasedApproachUsingtheSHARPESoftwarePackage.KluwerAcademicPublishers,Boston,1996.[38]K.Seigrist.“ReliabilityofsystemswithMarkovtransferofcontrol”.IEEETrans.on

SoftwareEngineering,14(7):1049–1053,July1988.[39]K.Seigrist.“ReliabilityofsystemswithMarkovtransferofcontrol,II”.IEEETrans.on

SoftwareEngineering,14(10):1478–1480,October1988.[40]M.L.Shooman.“Structuralmodelsforsoftwarereliabilityprediction”.InProc.2ndInt’l

Conf.SoftwareEngineering,pages268–280,SanFransisco,CA,October1976.[41]N.D.SingpurwallaandS.P.Wilson.“StatisticalMethodsinSoftwareEngineering:

ReliabilityandRisk”.SpringerVerlag,NewYork,NY,1999.[42]K.S.Trivedi.ProbabilityandStatisticswithReliability,QueuingandComputerScience

Applications.JohnWiley,2001.[43]J.Voas,F.Charron,andL.Beltracchi.“Errorpropagationanalysisstudiesinanuclear

researchcode”.InProc.of1998IEEEAerospaceConference,Snowmass,CO,1998.[44]W.Wang,Y.Wu,andM.H.Chen.“Anarchitecture-basedsoftwarereliabilitymodel”.

InProc.ofPacificRimDependabilitySymposium,HongKong,December1999.[45]A.T.WeiandR.H.Campbell.“Constructionofafaulttolerantreal–timesoftwaresys-tem”.TechnicalReportUIUCDCS-R-80-1042,U.ofIllinois,Urbana-Champaign,De-cember1980.[46]M.XieandC.Wohlin.“Anadditivereliabilitymodelfortheanalysisofmodularsoftware

failuredata”.InProc.SixthIntl.SymposiumonSoftwareReliabilityEngineering,pages188–193,Tolouse,France,October1995.

30

[47]S.Yacoub,B.Cukic,andH.Ammar.“Scenario-basedanalysisofcomponent-basedsoft-ware”.InProc.ofTenthIntl.SymposiumonSoftwareReliabilityEngineering,BocaRaton,FL,November1999.

31