AcademicPressisanimprintofElsevier 525BStreet,Suite1900,SanDiego,CA92101-4495,USA 225WymanStreet,Waltham,MA02451,USA 32JamestownRoad,London,NW17BY,UK LinacreHouse,JordanHill,OxfordOX28DP,UK Radarweg29,POBox211,1000AEAmsterdam,TheNetherlands Firstedition2012 Copyright©2012ElsevierInc.Allrightsreserved Nopartofthispublicationmaybereproduced,storedinaretrievalsystemortransmittedinanyformor byanymeanselectronic,mechanical,photocopying,recordingorotherwisewithoutthepriorwritten permissionofthepublisherPermissionsmaybesoughtdirectlyfromElsevier’sScience&Technology RightsDepartmentinOxford,UK:phone(+44)(0)1865843830;fax(+44)(0)1865853333;email: permissions@elsevier.com.AlternativelyyoucansubmityourrequestonlinebyvisitingtheElsevierweb siteathttp://elsevier.com/locate/permissions,andselectingObtainingpermissiontouseElseviermaterial Notice Noresponsibilityisassumedbythepublisherforanyinjuryand/ordamagetopersonsorpropertyasa matterofproductsliability,negligenceorotherwise,orfromanyuseoroperationofanymethods, products,instructionsorideascontainedinthematerialherein LibraryofCongressCataloging-in-PublicationData AcatalogrecordforthisbookisavailablefromtheLibraryofCongress BritishLibraryCataloguing-in-PublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary ISBN:978-0-12-396525-7 ISSN:0065-2458 ForinformationonallAcademicPresspublications visitourwebsiteatstore.elsevier.com PrintedandboundinUSA 12 13 14 10 9 8 7 6 5 4 3 2 1 Preface Advances in Computers is the oldest series to chronicle the rapid evolution of computing. The series has been in continual publication since 1960. Several volumes,eachtypicallycomprisingfourtoeightchaptersdescribingnewdevelop- ments in the theory and applications of computing, are published each year. The themeofthis84thvolumeis“EngineeringDependableSystems,”andthecontents providecomprehensivecoverageofdiverseaspectsofdependablecomputing,while illustratingtheuseofcomputinginimprovingthedependabilityofcriticalsystems invariousapplicationdomains. Computingispermeatingtheeverydaylifeofmuchoftheworld’spopulationat an ever-increasing rate. The scope of systems and applications that now exhibit significant reliance on cyberinfrastructure is unprecedented, as is the extent of coupling between physical components and the computing hardware and software by which they are governed. Domains as diverse as electric power, medicine, and educationarenowheavilyreliantoncomputingandcommunication.Thedistributed natureofcomputer-basedcontrolisadouble-edgedsword;itaddsredundancy,yet makesthesystemmorecomplex—theneteffectondependabilitydependsbothon theindividualcomponentsusedandtheinterplayimplementedamongthem.Simi- larly, communication and networking make it possible to incorporate more infor- mationindecisionsupportforphysicalsystems,whichshouldimprovethe“quality” ofcomputer-basedcontrol;however,theconnectivitycreatedcanalsofacilitatethe propagationoffailures,compromisingdependability. In this volume, we adopt the definition and taxonomy of “dependability” pre- sented in the seminal paper by Avizˇienis, Laprie, Randell, and Landwehr—an integrating concept that subsumes reliability, availability, and other attributes that leadtojustifiabletrustintheoperationofaserviceorsystem[1].Inthe7yearsthat have passed since the publication of the paper, the relevance of the definition and taxonomyhasonlyincreased.Theaimofourvolumeistoinformthereaderofthe stateoftheartandscienceofdependablesystems.Thechaptersthatcomprisethis volumeweresolicitedfromrenownedauthoritiesinthefield,eachofwhombrings tobearauniqueperspectiveonthetopic. vii viii PREFACE Inthefirstchapter,“CombiningPerformanceandAvailabilityAnalysisinPrac- tice,”Trivedi,Andrade,andMachidaarticulateapproachestoanalyticmodelingof suchattributesandpresentpracticalexampleswherethesemodelshavebeenapplied to computing and communication systems. The specific focus of the chapter is on integrating the analysis of performance and availability, achieving a means of quantifying the loss of dependability in terms of degraded performance—rather thanthemoretypicalbinaryviewofasystemas“failed”or“functional.” Identifying and understanding threats to the dependability of a system are the focus of the second chapter, “Modeling, Analysis, and Testing of System Vulner- abilities,” by Belli, Beyazit, and Mathur. This chapter presents a holistic view of dependabilitythatencompassesbothdesirableattributesthatmakeasystemdepend- ableandundesirableattributesthatcompromiseitsdependability.Thechapteralso articulates a framework where model-based testing can be used throughout the system life cycle—that is, from the design stage through implementation and maintenance—to analyze vulnerabilities in entities that range from requirements tocompletedeploymentsofasystem. Thethirdchapter,“SystemDependability:CharacterizationandBenchmarking,” extendsthediscussionofreliabilitymeasurestothebroaderscopeofcharacterizing dependability.ThefocusofthischapterbyCrouzetandKanounisonmodeling-and measurement-based benchmarks for dependability. Relevant concepts and techni- ques are presented in the context of systems that utilize commercial-off-the-shelf (COTS)components.DocumentationforCOTScomponentsistypicallyfocusedon the interfaces—a justifiable choice inlight ofthe importance ofinteroperability in component-based systems. However, intellectual property concerns (among other reasons) lead to a dearth of documentation about the internal operation of COTS components.Thisshortcomingsignificantlycomplicatestheassessmentofdepend- ability. The fourth chapter details measures and techniques that overcome this challengeandillustratestheproposedapproachusingtwocasestudies. “PragmaticDirectionsinEngineeringSecureDependableSystems,”byKhanand Paul, is the fourth and final chapter of this volume. This chapter aims to provide severaltechniquesthatcanbeconsideredaxiomaticinachievingdependabilityfor future complex systems across a broad range of application domains. The authors enumerate challenges to dependability and propose solutions for addressing these challenges, with focus on three overlapping areas: dependable hardware/software systems, secure dependable systems, and dependable cloud computing. This chap- ter,amongothers,touchesuponsecurity,whichiscomplementarytodependability as a measure of system assurance, and encompasses a number of the same system attributes—foremostamongthemavailability. PREFACE ix We hope that you find these articles of interest and useful in your teaching, research, and other professional activities. We welcome feedback on the volume andsuggestionsfortopicsforfuturevolumes. AliR.Hurson SahraSedigh MissouriUniversityofScienceandTechnology Rolla,MO,USA Reference [1] A.Avizˇienis,J.-C.Laprie,B.Randell,C.Landwehr,Basicconceptsandtaxonomyofdependableand securecomputing,IEEETrans.DependableSecureComput.1(1)(Jan.-March2004),pp.11–33. Combining Performance and Availability Analysis in Practice KISHOR TRIVEDI Department of Electrical and Computer Engineering, Duke University,Durham, North Carolina, USA ERMESON ANDRADE Department of Electrical and Computer Engineering, Duke University,Durham, North Carolina, USA Informatics Center, FederalUniversity of Pernambuco (UFPE), Recife, Pernambuco, Brazil FUMIO MACHIDA Department of Electrical and Computer Engineering, Duke University,Durham, North Carolina, USA Service Platforms Research Laboratories, NEC Corporation, Kawasaki, Japan Abstract Composite performance and availability analysis of computer systems has gained considerable attention in recent years. Pure performance analysis of a systemtendstobeoptimisticsinceitignoresthefailure–repairbehaviorofthe system.Ontheotherhand,pureavailabilityanalysistendstobetooconservative sincethebehaviorofthesystemiscapturedbyonlytwostates(functioningor failed).Toanalyzethedegradationofasystem’sperformanceinconsideration with availability metrics, combined measures of performance and availability are essential. This chapter introduces the basics of analytic models for the combined performance and availability analysis ofcomputer systems together withsomepracticalexamples. 1 ADVANCESINCOMPUTERS,VOL.84 Copyright©2012ElsevierInc. ISSN:0065-2458/DOI:10.1016/B978-0-12-396525-7.00001-0 Allrightsreserved. 2 K.TRIVEDIETAL. 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. ApproachestoModeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1. Non-State-SpaceModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. State-SpaceModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. PracticalExamples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1. PureReliability/AvailabilityandPurePerformanceAnalysis . . . . . . . . . 11 3.2. CompositePerformanceandAvailabilityAnalysis . . . . . . . . . . . . . . 23 4. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1. Introduction The need for combining performance and availability analysis of computer systems is increasing, since most computer systems can continue their operations eveninthepresenceoffaults.However,software/hardwaredesignersarestillusing performance and availability measures separately to evaluate the quality of the systems.Suchseparatedanalysisisnotsufficienttoproperlyunderstandandpredict thebehaviorofthesesystemsbecausetheperformanceisaffectedbythefailuresand recoveries of the system components. Thus, the use of evaluation methods which combineperformanceandavailabilityanalysisisessential[1–7]. In recent decades, several approaches have been developed for considering the combined evaluation of performance, availability, and reliability [8–14]. Beaudry [15] is the first author to develop the measures which provide trade-offs between reliability and performance of degradable systems. Thereafter, the term perform- ability,wheretheconceptofperformanceandreliabilityisunified,wasintroduced by Meyer [16]. He developed a general modeling framework that covers perform- abilitymeasures. Quantitative evaluation of systems’ performance and reliability/availability can be broadly classified into measurement and model-based approaches. In the mea- surementapproach,thecollecteddataaccuratelyshowthephenomenaobservedin the system, but the evaluation tends to be expensive. Some experiments are not always feasible because they are either time-consuming or need expensive proce- dures (like fault injections). By contrast, in the model-based approach, the evalua- tion ofsystemscan becarried outwithoutthe actual execution onthe real system. Themodelprovidesanabstractionofthesystemwhichdoesnotalwayspredictthe performance and availability accurately. However, if the models are properly COMBININGPERFORMANCEANDAVAILABILITYANALYSIS 3 validated,themodel-basedapproachmightpresentabettercost-effectiveapproach overthemeasurements.Boththeapproachescanbeusedtogetherdependingonthe criticality of the system and/or availability of resources. Often, measurements are madeatthesubsystemlevel,andthesearerolleduptothesystemlevelbymeansof models[17,18].Inthischapter,wediscussthemodel-basedapproach. Different modeling techniques can be used for combining performance and availability analysis. Among of them, the exact composite approach [3] has been widely used because of its accuracy. However, this approach faces largeness and stiffnessproblems.Largenessoccursbecauseofacross-productofstatesofperfor- mancemodelandavailabilitymodel.Todealwiththelargenessproblem,twobasic techniquescanbeapplied:largenesstoleranceandlargenessavoidance[4].Stiffness ariseswhentheratesrelatedtoperformancemodelsaremuchfasterthantheratesof availability models. Aggregation techniques [19] and stiffness-tolerance [20] are effective methods in dealing with the stiffness problem. Hierarchical modeling approach [12] is another potential largeness and stiffness avoidance technique. This approach divides the system model into several small submodels. The sub- models can be of different types, such as non-state-space models and state-space models. The solution of the hierarchical model is computed by passing outputs of lower-level submodels as inputs to the higher level submodels. In case of cyclic dependenceamongsubmodels,fixed-pointiterativecanbeapplied[8,21]. This chapter aims to present an overview of main techniques used in model constructionandsolutionofcompositeperformanceandavailabilityanalysis,such as exact composite approach and hierarchical modeling approaches. We also describetechniquesusedforpureavailabilityanalysisandpureperformanceanaly- sis.Practicalexampleswheresuchtechniquesweresuccessfullyappliedaredetailed. The chapter is organized as follows: Section 2 introduces basics of analytic models for evaluating performance and availability of systems and also describes modelingtechniquesforcombiningperformanceandavailabilityanalysis.Section3 describes a set of practical examples for combining availability and performance analysis.Section4concludesthechapter. 2. Approaches to Modeling In pure performance modeling, probabilistic nature of user demands (workload) aswellasinternalstatebehaviorneedstoberepresentedundertheassumptionthat the system/components do not fail [4]. Several stochastic models can be used for performance analysis, such as series–parallel directed acyclic graphs [4], product formqueuingnetworks[22],Markovchains[23],semi-Markovprocess(SMP)[1], 4 K.TRIVEDIETAL. Markov regenerative process [24], generalized stochastic Petri nets (GSPNs) [25], stochastic reward nets (SRNs) [4], hierarchical [12] and fixed-point iterative [26], and the combination of these. Metrics such as throughput, blocking probability, mean response time, response time distribution, and utilization can be computed basedonthesemodels. AccordingtoITU-TRecommendationE.800[27],“availabilityistheabilityofan itemtobeinastatetoperformarequiredfunctionatagiveninstantoftimeoratany instantoftimewithinagiventimeinterval,assumingthattheexternalresources,if required,areprovided”.OnFebruary1991,thePatriotmissiledefensesystemfailed tointerceptanincomingmissile.Thisincidentresultedinthedeathof28USArmy reservists [28]. Thus, high availability of mission-critical systems is extremely important,sincefailurescanbecatastrophic.Forbusinesscriticalsystemsandcritical infrastructures,highavailabilityisalsoimportanttominimizethecostofdowntime. Analyticmodelshavebeenwidelyusedtopredictthesystemavailability.These models can provide important insights about the availability considering different scenariosbeforethesystemisreleasedforuse.Theavailabilityaspectsofthesystem are usually describedby non-state-space models(reliabilityblock diagram (RBD), fault tree (FT), and reliability graph), state-space models such as Markov chains, SMP,Markovregenerativeprocess,stochasticPetrinets(SPNs)ofvariousilk,and hierarchical and fixed-point iterative models. Downtime, steady-state availability, instantaneousavailability,andintervalavailabilityarefrequentlyusedasmeasures. Assuming exponential failure and repair time distributions with respective rates l andm,theavailabilityattimetandtheintervalavailabilitycanbecomputedbythe followingexpressions[23]: m m AðtÞ¼ þ e(cid:2)ðlþmÞt lþm lþm Ð tAðxÞdx m l (cid:2) (cid:3) A ðtÞ¼ 0 ¼ þ 1(cid:2)e(cid:2)ðlþmÞt I t lþm ðlþmÞ2t Takingalimittoinfinityoftheinstantaneousavailability,thesteady-stateavail- abilityA canbecomputedasbelow ss m A ¼ limAðtÞ¼ ss t!1 lþm The steady-state unavailability U and downtime (in minutes per year) are ss obtainedfromA bythefollowingexpressions ss U ¼ð1(cid:2)A Þ ss ss Downtime¼ð1(cid:2)A Þ(cid:3)8760(cid:3)60 ss COMBININGPERFORMANCEANDAVAILABILITYANALYSIS 5 Composite performance and availability analysis is required especially in the evaluationofdegradablesystems.Indegradablesystems,whensomesystemcom- ponentsfail,thesystemcanundergoagracefuldegradationofperformanceandstill beabletocontinueoperationatareducedlevelofperformance.Inotherwords,the systemcanhavemorethantwoworkingstates(i.e.,functioning,partiallyfunction- ing, and down). One of the most used analytic model types for combining perfor- mance and availability analysis is Markov reward model in which each state of Markov chain is assigned a reward rate according to the performance delivered in thestate.Inthefollowingsubsections,weintroducethebasicsofanalyticmodeling forperformanceandavailabilityevaluationbasedontwotypesofmodels:non-state- spacemodelsandstate-spacemodels. 2.1 Non-State-Space Models Availability models can be constructed using non-state-space models such as reliability block diagram (RBD), reliability graph (Relgraph), and FT with and without repeated events. Non-state-space models are easy to use and have a rela- tivelyquicksolutionbecausetheycanbesolvedwithoutgeneratingtheunderlying statespace[29].Forarapidsolution,thesemodelsassumethatsystemcomponents are independent of each other. System availability, system unavailability, system reliability, and system mean time to failure can be computed using these models. Thethreecommonlyusedsolutiontechniquesfornon-state-spacemodelarefactor- ing[23],sumofdisjointproducts[23],andbinarydecisiondiagram[30].Largenon- state-spacemodelcanbesolvedbyderivingupperandlowerboundsasdescribedin Ref.[31]. RBD is a non-state-space model type that enables analysis of reliability and availability of complex systems using block diagrams. In a block diagram model, components are combined into blocks in series, parallel, or k-out-of-n. A series structure represents a direct dependency between the components where the entire system fails if one of its components fails. A parallel structure is used to show redundancyandmeansthatthewholesystemcanworkproperlyaslongasatleast onecomponentisworkingproperly.Ak-out-of-nstructurerepresentsthatthewhole subsystemcanworkproperlyaslongaskormorecomponentsareworkingproperly out of n components. Series and parallel structures are special cases of k-out-of-n structures[4].Aseriesstructureisann-out-of-nandaparallelstructureisa1-out-of-n structure.Figure1showsanRBDrepresentingastoragesystemavailabilitymodel withoneserver,onehub,andnstoragesdevices.Thesystemisworkingproperlyifat leastoneofeachdevice(server,hub,andstorage)isworkingproperly. FTcanbeusedforquantitativeanalysisofsystemreliability/availabilityaswell asqualitative analysis.FT depicts acombinationofeventsandconditionsthatcan 6 K.TRIVEDIETAL. lead to an undesired event such as system failure. Basic FT consists of events and logical event connectors such as OR gates, AND gates, and k-out-of-n gates. The eventscanbecombinedinseveralwaysusinglogicalgatesaccordingtothesystem configuration. FT can have repeated events in situations in which the same failure eventpropagatesalongdifferentpaths.Figure2presentsanFTmodelforthestorage systemwithoneserver(S),onehub(H),andnstoragedevices(SD).Incontrastto the RBD model, the FT takes a “negative” view in that it describes the condition under which the system fails. Since FTs allow repeated events, they are more powerfulthanseries–parallelRBDs.Foracomparisonofmodelingpowerofthese modeltypes,seeRef.[32]. Storage 1 Server Hub Storage 2 ... Storage “n” FIG.1. RBDforastoragesystem. Failure or and ... S H SD1SD2SD“n” FIG.2. FTforastoragesystem.