DickHamlet
DaveMason
DeniseWoit
PortlandStateUniversityPortland,OR,USAhamlet@cs.pdx.edu
RyersonPolytechnicUniversityToronto,Ontario,CANADA
dmason,dwoit@scs.ryerson.ca
Abstract
Wepresentafoundationaltheoryofsoftwaresystemre-liabilitybasedoncomponents.Thetheorydescribeshowcomponentdeveloperscandesignandtesttheircomponentstoproducemeasurementsthatarelaterusedbysystemde-signerstocalculatecompositesystemreliability—withoutimplementationandtestofthesystembeingdesigned.Thetheorydescribeshowtomakecomponentmeasurementsthatareindependentofoperationalprofiles,andhowtoincor-poratetheoverallsystem-leveloperationalprofileintothesystemreliabilitycalculations.Inprinciple,thetheoryre-solvesthecentralproblemofassessingacomponent,whichis:acomponentdevelopercannotknowhowthecomponentwillbeusedandsocannotcertifyitforanarbitraryuse;butifthecomponentbuyermustcertifyeachcomponentbe-foreusingit,component-baseddevelopmentlosesmuchofitsappeal.Thisdilemmaisresolvedifthecomponentdevel-operdoesthecertificationandprovidestheresultsinsuchawaythatthecomponentbuyercanfactorintheusageinfor-mationlater,withoutrepeatingthecertification.Ourtheoryaddressesthebasictechnicalproblemsinherentincertify-ingcomponentstobereleasedforlateruseinanarbitrarysystem.
Mostcomponentresearchhasbeendirectedatfunctionalspecificationofsoftwarecomponents;ourtheoryaddressestheother,equallyimportant,sideofthecoin:componentquality.
Keywords:Softwarecomponents,reliabilitycomposi-tion,foundationaltheory,COTS,CBSE
1PromiseandPitfallsofComponents
Softwarecomponentsarethemostpromisingideaex-tantfortheefficientdesignofqualitysoftwaresystems.Mostoftheresearchincomponentsisdevotedtospecifica-tion,design,reuse,andcatalogingofthecomponentsthem-selves.Thecomplementaryissue—componentquality—isalsoimportant,buthasreceivedlessattention.Therearenoacceptedstandardsforthequalityofsoftwarecompo-nents,largelybecausethereisnotheoreticalfoundationon
orgreaterimportance,butitisnotpartofthetheory.How-ever,thecomponentdevelopermusthaveaneffectiveoracletocarryoutstatisticaltesting,anditishereassumedthataformalspecificationsuppliesthisoracle[21].
Theproblemofsoftwaresystemreliabilityfromcom-ponentdatahasbeenstudiedformorethan20years[15,13,14,11,12].Perhapsbecauseastraightforwardanaly-sisseemsoverwhelming,pastapproachesallmodelcom-ponentsandsystemsinsomeabstract,‘high-level’way,forexampleasaMarkovchain.Incontrast,theapproachtakenhereisfundamentalanddirect:thefailurebehaviorsofcom-ponentsandsystemaremodeledindetail.
2.1Basisofthetheory
Tobeusefulinsystemdesign,componentdatasheetsmustcontaintechnicalinformationsufficientforthesys-temdesignertomakereliabilitycalculations;and,itmustbepossibleforthecomponentdevelopertocollectthisin-formation.Subjectiveandmethodologicalassessmentsofthesoftwaredevelopmentprocessarenotdata-sheetinfor-mation,becausetheyamounttolittlemorethanassertionsthatthedeveloperistryingtodoagoodjob.Acurrentpre-standardsstudygrouponcomponentqualityisusingsuchsubjectivemeasuresalmostexclusively[1].Thereputationandprocessofthedeveloperarenotinconsequentialfactorsinselectingacomponent;but,theirroleshouldbetobackuphardtechnicaldata.
Twomeasuresofsoftwarequalitythatqualifyforadatasheetare(1)thatthecomponenthasbeenprovedcorrect,or(2)thatithasbeenoperationally(random)tested.Bothoftheserequireaformalspecificationofwhatthecomponentissupposedtodo(thepartofthedatasheetnotconsideredhere).Astatementthatthecomponenthasbeenprovedcor-rectisaguaranteethatitwillperformaccordingtoitsspec-ification.Astatementthat(say)itsreliabilityisbetterthan
perexecutionwithanupperconfidencebound
of99%,isastatisticalassertionthatthereisnomorethan1chancein100thatitwillnotperformaccordingtothespecificationin10,000trials.Correctnessproofs(1)canbethoughtofasthespecialcaseofaprofile-independentre-liabilityof1.0,with100%confidence.Wewillbelargelyconcernedwiththemorepracticalcase(2)oftesting.
Thereaderofadatasheetmightdoubtthatthedeveloperhasactuallyestablisheditsprecisetechnicalclaims.Butthisisaquestionthatcanbeansweredscientifically,andifthedeveloperhasliedandthereisadamagingfailureasaresult,therearelegalremedies.
Thistheoryisbasedontwoideas:
Profilemappings.Operationalprofilesmustbetakeninto
accountwhenmeasuringcomponentparametersforadatasheet.Sincethecomponentdevelopercan-notknowhowthecomponentwillbeused,andhencewhatprofileitwillfaceaspartofasystem,thedata-
sheetmusttakeprofileasaparameter.Thatis,thedatasheetspecifiesmappingsfromaprofiletorelia-bilityparameters[18].
Componentsubdomains.Acomponenthasanaturalpar-titionofitsinputspaceintofunctionalsubdomains,andthepracticaldescriptionofitsoperationalprofileisasavectorofweightsoverthesesubdomains.Thisformfortheoperationalprofileallowsthecomponentdevelopertotestacomponentwithoutknowingtheprofilethatitmaylaterface[6].
2.2ComponentandSystemDevelopmentProcess
Inoutline,theprocessofmakingandusingcomponentsisidealizedasfollows:
Thecomponentdeveloperdefinesasetstofnaturalsubdomainsforanimplementednecomponent.
nopmocThecomponentdevelopermeasuresproper-tiesofthecomponentforeachsubdomain.gnikThecomponentdeveloperpublishesadataamsheetlistingitssubdomains,andgivingreli-abilityinformationasmappingsofprofiles.Thesystemdesignerdecidesonasystemstructureutilizingcomponents.
stUsingthedatasheetsforprospectivecom-nenponentsandatrialprofileofthesystem,theopsystemdesignercalculatesthesystemrelia-mobility.
cgniIfthedesiredsystemreliabilitycannotbesuachieved,itwillbenecessarytofindbettercomponents,ortochangethesystemstruc-ture,andrepeatthereliabilitycomputation.
Thisidealizedmodelisacompromisethatacknowledgessomeoftherealitiesofpracticalapplication,butsimplifiesthereal-worldsituationsothatitcanbeanalyzedandthetheorytested.Nofundamentaltheoryforcomputingsys-temreliabilityfromcomponentscurrentlyexists,probablybecausethedetailsofpracticalapplicationaresocomplexandvaried.Asuccessfultheoreticalfoundationmustusearelativelysimplemodel,butitmustalsodrawonexistingtestingandreliabilitytheory.
3ProblemsandProposedSolutions
Anytheoryofsoftwarecomponentreliabilitymustad-dresstwoimportantissues:theoperationalprofileusedtotestthecomponentvs.theprofileitencounterswithinthe
systemwhereitisused;and,thedesignprocessforthesys-tem’smainprogramthatinvokesitscomponents.
3.1OperationalProfiles
Whenthequalityinformationonacomponent’sdatasheetisstatistical,itmustbeobtainedbyrandomtesting.Thefundamentalproblemofassessingcomponentqualitysta-tisticallyisthatanystandardprofilefromwhichtestinputsaredrawnwillnotmatchtheprofilethatthecomponentwillexperiencewhenplacedinasystem.Furthermore,thepro-fileseenbyacomponentdependsnotonlyonthesysteminputprofile,butalsoonthecomponent’spositioninthesystemandontheactionsoftheothercomponentsthere.Section4proposesasolutiontotheprofileproblemastwodata-sheetprofilemappings(oneforreliabilityandtheotherforprofiletransformation)definedusingasubdomaindecompositionofthecomponentinputdomain.Asystemdesignercanusethesemapstocalculatethesystemrelia-bilitybeforeimplementation.
3.2SystemDesign
Tomakecalculationsofsystempropertiesfromcompo-nentproperties,thesystemdesignermustnotonlyhavethecomponentdatasheets,butneedstotryvarioussystemde-signsthatsatisfythesystemrequirements.Intryingde-signs,therearetwotechnicalproblemstowhichSection5providessolutions:
‘Gluelogic.’Anysystemwillcontainexplicitcodethatin-vokesitscomponents,perhapsfirstadjustingparame-tervaluesandlatercombiningtheirresultsasneeded,andperhapsperformingsignificantcomputationsun-relatedtoanycomponent.Thesepiecesof‘gluelogic’havetobeanalyzedalongwiththecomponents.Gluelogicishandledbyconvertingsystemcodetofrag-mentsthatactlikeindependentcomponents[23].Systemcontrolflow.Componentinvocationpatternscome
fromthetop-levelcontrolstructuresinthesystemde-sign.Thesepatternsarehandledbyprovidingarelia-bilityalgebrafortheconstructionsofsequence,con-ditional,andlooping.
4OperationalProfiles
Componentdatasheetscannotdirectlyinclude‘reliabil-ity’ofthecomponent,becausereliabilityisaninput-profile-dependentquantity,andthecomponentdevelopercannot
knowwhatprofilewilloccurinasystembeingdesigned.Furthermore,eachsystemcomponentdistortstheprofilepresentedtoitasinput,andhenceinfluencestheprofileseenbyothercomponents.Weproposethatthecomponentde-velopersupplyinformationintheformofprofilemappings,butthisrequiresthattheformofprofilesbestandardized.
4.1ProfilesDefinedonSubdomains
Aprofileisaprobabilitydensity,whereisadiscreteinputdomain.Inpractice,itisverydifficulttoobtainpreciseprofiledatafromsoftwareusers.Thebestthatcanbedoneistodescribeaprofileasahis-togramofprobabilitiesoverquitebroadclassesofinputs[19].Weexploitthisideaasastandardformforprofiles.
Letacomponent
haveinputdomain,partitionedintodisjointsubdomains,
Leteachsubdomainhaveitsownprofile,anditsown
probabilityoffailure:
whereisthesubsetofonwhichfailsandistheprofilewithinsubdomain.Theoverallprofileforthecomponentmaybeexpressedasanormalizedvectorofprobabilitiesthateachsubdomainwilloccurinuse:
Inthepracticalcase,theprofileisliterallyuser-defined:apersonestimatesthelikelihoodthatvariousinputswillarise.Suchapersonishard-pressedenoughtomakees-timatesofsubdomainweightings,andcanusuallysaynothingaboutdistributions.Thuswithinthesubdomains
itisusualtotakeauniformdistribution
.Hence:ReliabilityMapping.Thereliabilitymappingcarriesapro-filevectortoarealvalue
,theprobabilitythatthecomponentwillnotfailonaninputdrawnaccordingtothisprofile.Togivethismappingonthedatasheet,thecomponentdeveloperestimatesthefailurerateswithineachsubdomainusinguniformrandomtesting.Then
(1)
Giventhismapping(thatis,giventhemeasuredbythecomponentdeveloper)andaprofile(theforthesystemtobedesigned),thesystemdesignercanuseequation(1)tocalculate,thecomponentreliabilityunderthatprofile.
Profile-transformationMapping.Theprofile-transforma-tionmappingcarriesaninputprofilevectortoanout-putprofile,takingasaparametertheoutputsubdo-mains.Themappingmustbeabletohandleanarbi-trarysetofoutputsubdomains
,unre-latedtothesubdomainsonthecomponentdatasheet,sincesuchasetofsubdomainswilldescribesomefollowingcomponentinasystemdesign.Lettheweightingstobecalculatedforanoutputprofilebe
onsubdomains.Eachisthesumofthecontri-butionsfromeachinputsubdomain,
.Supposethat
’sdatasheetliststhreesubdo-
mains:
withfailure-rateboundsof(say).01,0,and.001respec-tively.Thefailureratemeasurementswouldbeobtainedbythecomponentdeveloperfromexhaustivetestingonthesmallsubdomains,andbyuniformrandomtestingthatex-posednofailuresonthelargesubdomains.Supposethatthe
inputprofiletois
.Thenthereliabilityofalonefromequation(1)is:
Supposethat
’sdatasheethasfoursubdomains:
withfailureratesof.1,0,0,and.02respectively.
’sprofile-transformationmappingcanbeusedwiththesubdomainsfrom’sdatasheettocalculatetheprofilewillsee.(Thisisthebasiccompositionconstruction.)carries0to
rfromfrom000
.147
0.162
Sotheprofileseesfromis
,and
’sreliabilityis:
Thesystemreliabilityofthesequenceisfinallycalculated
as
.4.5‘Spikes’inIntermediateProfiles
Whenthebasiccompositioncomputationiscarriedout
evenforsimpleexamplesliketheoneinSection4.4,theap-plicabilityofthetheorydependscriticallyonthefunctionalbehaviorofthefirstcomponentinacomposition.Ifthatfirstfunctionspreadsitsoutputsrelativelyevenlyacrossaninputsubdomainofthesecond,followingcomponent,thenthetestsdonebythedeveloperofthelatterarevalid,becausetheyusedauniformprofileonthatsubdomain.However,ifthefirstcomponentinthecompositionproducesanout-putprofilewitha‘spike’inanyfollowingsubdomain,thenthedeveloper’stestingofthesecondcomponentiscalledintoquestion.Thisdifficultyoccursinrandomsystemtest-ingwhenauniformprofileisusedbecauseuserdataisnotavailable,asdiscussedinreference[7].
Asanextremeexample,ifacomponentcomputingthe
constantfunctionwithvalue
isfirstinacomposition,thenthesubdomain
ofthefollowingcomponentinwhichfallshasaspikeat.Thebasiccompositioncomputa-tionassigns100%oftheinputprofiletosubdomain
asitshould,butthecomputationobscuresthefactthatuniformly
sampling
andpredictingitsfailureratemaybewildlyinaccurate.Infact,ifthesecondcomponentiscorrectforinputthenthecomposedfailurerateshouldbe0;or,ititfailsoninput,thecomposedfailurerateshouldbe1.Buttheuniformsamplingofthecomponentdeveloperisveryunlikelytohavetriedinputatall.Inaslightlymorereal-isticexample,acomponentthatidentifiesleapyears,placedinabusinessaccountingsystem,mayseldomberequiredtogooutsidetheyears(say)1990-2010,andinanygivenyear,willmostfrequentlybeaskedaboutthatyearitself.Ifthiscomponentistestedbyitsdeveloperwithauniformprofileoverarangeof(say)1,000years,theeffectivesamplingrateduringtestis50-1000timeslowerintheactualusagerangethanwhatthecomponentwillexperienceinplace.
Althoughuniformsamplingseemsthewrongthingtodointestingacomponentthatmayreceiveaprofilespike,itisalsotheonlypossibility.Thechancethatitwillfailatexactlythepointsunderthespikecannotbeproperlyinves-tigatedwhenthosepointsareunknown,andtheuniformtestprofileisthebestavailable.
4.6Correct(Proved)Components
Inextremesituations,arequiredsystemreliabilitymay
beobtainableonlybyusingsomecomponentsthatareper-fectlyreliable—theyhavebeenprovedcorrect.Sucha
componenthasadatasheetthatspecifiesnosubdomainsorprofile-transformationmapping,andareliabilityfunctionofconstant1.0.Solongasonlycorrectcomponentsareusedinasystemdesign,thereisnoneedforcalculation—thesystemreliabilityis1.0.However,whencorrectcompo-nentsareusedinconjunctionwithotherswhosedatasheetsincludesubdomainsandthemappingsgiveninSection4.3,thecorrectcomponentstransformprofiles,andthesystemdesignermustfindthesetransformationstocalculatehowsubsequentcomponentswillbehave.Equation(2)canbeusedforcorrectcomponentsasfollows:
Let(computingfunction)andbetwocompo-nentswithstatisticaldatasheets.Supposethatisfollowedbyasequenceofcorrectcomponents,whichwithoutlossofgeneralitywetaketobeonecorrect
component,computingfunction.
isinturnfollowedby.Thatis,thecomponentsequenceis
.Thenthebasiccompositionconstruction
canbeapplieddirectlyfrom
tobyreplacinginequation(2)withThatis,thecorrectcomponentcanbetreatedasifitsimplyextendsthefunctionalityof.
5SystemDesign
Thecalculationsofasystemdesigner,madetodetermineifacomponent-baseddesignisgoodenoughtosatisfyre-quirements,aredrivenbythecontrolstructureselectedforthesystem’s‘main’program.
5.1AnAlgebraofSystemDesign
Fromthedatasheetsofpossiblecomponentsandthestructureofthesystemdesign,thesystemreliabilitycanbecomputed.Thissectiongivestherulesforcombiningcom-ponentreliabilitiesinsequences,withinconditionalcon-structs,andforindefiniteloops.SequencesofComponents
AttheendofSection4.3,abasiccompositionconstruc-tionfortwocomponentswaspresentedindetail.Theprofilefromthefirstcomponentwastransformedusingequation(2)toaprofileforthesecondcomponent,andfromtheseprofilesthetwocomponentreliabilitieswerecomputedus-ingequation(1).Thisconstructioncanbeextendedtoan
arbitrarycompositionofcomponents
bysuccessivelytransforminganinputprofileto
intopro-filesforthesuccessiveintermediatesubdomainsfromthe
datasheetsfor
.Conditional
Consideraconditionalcompositionofcomponents:
Thetest
fortheconditionalpartitionsthedomain
into
and.
Aconditionalsystemstructurecanbeanalyzedwiththebasiccompositionconstruction.Letbeacomponentthatisinvokedjustpriortotheconditional,andletthecondi-tionalinvokeafollowingcomponent.Thatis,these-quenceis
.Thesystemdesignercancalculatethereliabilityoftheconditionalasfollows:Applythebasiccompositioncon-structionto
,usingthesubdomainsfor,butincalculatingthesetinthenumeratorofequation(2),count
apointonlyif
istrue.Thatis,ifhassub-domains
,inequation(2)takeand.Similarly,treatwith
’ssubdomainsadjustedtoincludeonlythepartofeach
whereisfalse,byintersectingthesubdomainson
’sdatasheetwith
.Thesetwocalculationsdeterminetheoutputprofilesfromthataretheinputprofilesfor
and,whichallowsthereliabilitiesofeach(and)tobecalculatedfromtheirdata-sheetmappings.There-liabilityoftheentireconditionalconstructisthereforetheweightedaverageofthese:
wheretheweightsandarethefractionsofout-putssentto
andrespectively,whichcanbedeter-minedfromtheinputprofileto.(Anotherwaytolookat
isastheprofileintowhichthebasiccomposi-tionconstructiontransforms’sprofile,onthetwosubdo-mains
andoftheconditional.)Theconditionalalsoinfluencestheprofileseenbythefollowingcomponent.Thebasiccompositionconstruc-tioncanbeusedtomaptheinputprofilesobtainedabove
for
andtotwoprofilesfor,byexaminingthese-quences
and,eachusingforoutputthedata-sheetsubdomainsfor.Theprofileseenbyisthenthe
weightedaverage(using
andabove)ofthesetwoprofiles.
Aconditionalwithoutanelseisthespecialcasein
which
isacomponentcomputingtheidentityfunctionwithreliability1.
Conditionalgluelogicmaybemorecomplexthanthesimplestformgivenabove,bytheinclusionofgluefrag-mentsinthetwobranchesbeforeand/orafter
and/or.However,suchfragmentscanbetreatedascompo-nentsinsequenceandcomposedwith
orusingtherulesalreadygiven.
IndefiniteLoop
Consideranindefiniteloop:
.Thelooptestpartitions
intoasfortheconditional.
Asystemdesignercananalyzealoopconstructioninawaysimilartothatdescribedaboveforaconditional.Thecomponentbeforetheloopsuppliestheinitialprofilefor
theloop-bodycomponent(adjustedbythetest).Thentransformsthisprofileasinputtoitself(againadjustedby).Ateachiterationoftheanalysis,theaccumulatedweightingthatexitstheloopincreases,assendsafraction
ofitsoutputsinto
.Thedesignerrepeatsthecalculationuntiltheresidualprobabilitythatcontrolwillremainintheloopissufficientlysmallthatthereliabilityoftheloopbodydoesnothavemuchimpactonthereliabilityoftheloopconstructasawhole.Eachprofileseenbyalongtheway
canbeusedtocalculateareliability
foroneiteration;theloop’sreliabilityistheproductofthese.Theprofileseenbyacomponentthatfollowstheloopistheweightedaverageofalltheprofilescalculatedforalongtheway.Thatis,thesystemdesignerconsidersaloopunrolling:
andthenreplacesthepartnotunrolledwithaconditional
thatfails:
Supposecopiesoftheconditionalwereunrolled.Thebasiccompositionconstructionappliedtothesequenceas-signsaprofiletothefinalcomponentinwhichtheweight
assignedto
isnegligible.Thenthereliabilitycalcula-tioninvolvesonlyaproductofthevaluesof
underthesuccessiveprofilesofthesequence.Thezeroreliabilityoffailhasminimalimpact,sinceitsweightisnearzero.Aslongastheloopterminates,thisisaconservativeestimate—itassumesthattheresidualexecutionsoftheloopwillfail.Aseparateproofofterminationisassumed.
Inpractice,maybetoolarge;or,iftoofewpointsarechosenininvestigatingtheprofiletransformations,itmay
appearasanartifactofpoorsamplingthat
isemptywhenitisnot.Loopsaretheproblematicconstructionsinprogramanalysis,sinceitisalwaysdifficulttodeterminetheircompositeeffect.Thisanalysisisnoexception,butthesituationislessgrimthanusual.Thistheoryisonlyconcernedwiththewayinwhichprofilesaretransformedbytheloop,andthisisfarlessdemandingthantoaskabouttheexactfunctionalbehavior.
5.2SubroutineCalls
Althoughsubroutinesaretheprimarydecompositionmech-anismofprogramminglanguages,theyarecannotbeuseddirectlytofactorasystem’sreliability.Thereasonwasiden-tifiedbyParnas[20]:
WhenXcallsYinaconventionallanguage,Xde-pendsonYtoreturnproperlyandtoproducecorrectresults.IfYfails,Xusuallyfails.ThusthereliabilityofYcannotbeseparatedfromthatofX.ParnascallsthisusualcallrelationshipUSES(X,Y).
Asubroutine-basedsystemcanberestructuredsothatitssubroutinesactasindependentcomponentstowhichourtheoryapplies.Parnascalledtherelationshipofindepen-denceINV(X,Y):XpassescontroltoY,butisindifferenttowhatYdoes.WhenXisacomponent(ormainpro-gram)callingcomponentY,andUSES(X,Y),totransformthecodesothatINV(X,Y),separateXintofragmentX1be-forethecall,andX2afterthecall.X1endsbyinvokingY,passingitproperparameters,butalsopassingX2.Insteadofreturning,YinvokesX2,passinganyresultfromY.
Componentsthemselvescanbeanalyzedintofragmentsinthesamewaythatsystemcontrolstructuresweretreated,butforsimplicityinthisexplanationcomponentsarere-strictedtosubsystemsthatmakenooutsidecalls.Inthiswaythecomponentdeveloper’sjobremainsmeasurementofpropertiesofself-containedunits,whilethesystemde-signer’sjobinvolvescalculationbasedonsystemstructure.
5.3DiscussionofGlue-logicDesign
Asindicatedintheanalysisoftheconditionalconstruc-tionabove,gluelogiccanbestbetreatedbyreducingsys-temstructuretothesimplestformpossible.Anyblocksofcodeinthehighestlevelcontrolstructureofthemainpro-gramshouldbetreatedascomponentsthemselves,tobesplitoff,analyzed,andthencomposedwithothercompo-nentsused.SubroutinecallsshouldberestructuredsothattheINVrelationshipholds.ThisleavesaminimalcontrolstructureforanalysisusingthealgebraofSection5.1.Thisbasicstructureofthemainprogramisnotitselfacompo-nent,inthatwhileitdoeshaveaprofile-transformingas-pect,itisnotgivenareliabilityaspect,buttreatedascor-rect.Theinsightthisprovidesisobviousinpractice:thesystemstructureshouldbeassimpleaspossible,sothatthesystemdesignercantrustit,andcanbesurethattheonlysourceofdesignflawsoccursinthecomponents,wherethereliabilitytheoryisbroughttobear.
6ComponentIndependence
ThequestionofcomponentindependencedoesnotariseinthebasiccompositionconstructionorthealgebragiveninSection5.1,exceptinasubtleformtobediscussedbelow.Eachcomponenthasitsreliabilitymapping,independentofanyothercomponent,andtheeffectofonecomponentonanotheriscapturedentirelybytheprofiletransformationsamongthem.
6.1SequentialCase:ConservativeCalculations
Inacomposition,ifmaybeincorrect(thatis,whenonlystatisticaltestinginformationisgivenonitsdatasheet),afalseprofileformaybeproducedbythebasiccompositionconstruction,andthuswouldinfluencethereliabilitycalculatedfor.Althoughwehavedonesomepreliminaryworkonthisproblemandfoundwaystoesti-mate’sprofilesothatthereliabilitycomputationserronly
inthedirectionofsafety,furtherinvestigationisneeded.
6.2RedundantCase:DesignDiversity?
Fromaqualitystandpoint,allusesofsequentialcontrolstructurecompromisereliability.Whentwocomponentsarecombined,thecombinationissubjecttothefailuresofboth.Thesequencecanmagnifythefailuresofthesecondcom-ponenttoanarbitrarydegree,sincetheprofileitinheritsmayemphasizethesubdomainswhereitisleastreliable.Tobuybackreliabilitylostinsequentialdesign,orsim-plytoobtainsystemreliabilitybetterthanthatofitscompo-nents,requirestheuseofparallel,redundantsystemstruc-tures.Thesimplestschemeis‘Multi-VersionProgramming’(MVP)inwhichacomputationisdoneindependentlythreeormoretimesandthemajorityresulttaken.Ifredundantcomputationsaredonebytwocomponentswhosefailure
ratesare
and,theniftheirfailurebehaviorisinde-pendent,thesystemfailurerateistheproduct
(equiv-alently,thereliabilityis
).Byusingenoughindependentcomponentsthatmustagree,ar-bitrarilygoodreliabilitycanbeobtainedinprinciple.Giventheimpracticalityoftestingsoftwaretosafety-criticallev-els[4],theuseofparallelcomponentsistheonlywaythat(forexample)commercialaircraftflightcontrolprogramscanmeettheirsafetyrequirements.
Unfortunately,ithasbeenexperimentallyobserved[10]thatMVPdoesnotrealizetheexpecteddecreaseinthefail-urerate,becauseinpracticetheredundantroutineshavecoincidentfailures—theyarenotindependent.‘Designdiversity’isthenamegiventoanattempttominimizecoin-cidentfailuresbyusingdisparatedesignsintheredundantroutines.
Thecontrolstructuresofredundantcomputationarenotfundamental;rather,theyusesequencesandconditionals.IftheanalysisofSection5.1iscarriedthroughforthecontrolstructureofMVP,thecalculatedreliabilitywillnotbebetterthanthatofoneredundantcomponent.Redundantcompu-tationrequiresspecialanalysisthattakesintoaccounttheattempttoreplicatethesamefunctionindistinctcompo-nents.Imaginethattwoalgorithmsarebeingexecutedwiththeirresultstobecompared,eachmadeupofcomponents.Inourmodel,diversitycanbequantitativelydescribed:Thetwocomputationsareintuitivelydifferentifthesubdomainsandprofilesateachinterfacediffer.
7Discussion—TheoreticalIssues
Increatingadatasheet,thecomponentdevelopermustidentifyasetofappropriateinputsubdomainsforthecom-ponentasthefirststepinmeasuringtheprofilemappings.Thereappearstobelittletheoreticalguidanceinchoos-ingsubdomainsforagivencomponent.Thedeveloperfacesanoldtestingproblem:thebestsubdomainsshouldbethoseonwhichthecomponent‘actsthesame’overthesubdo-
main,sothatsamplesofitsbehaviortherearenotmislead-ing.Itisthecommonwisdom(whichunfortunatelylacksanyverystrongtheoreticalorempiricalsupport)thatstruc-turallydefinedsubdomainsbestcapturethis‘sameness.’Struc-turalsubdomainsarefamiliartothesoftwaretesterasthebasisforcoveragetechniques;forexample,branchcover-ageisdefinedbysubdomainseachofwhichcorrespondstoexecutionofonebranchcondition.
Theotherfactorthatacomponentdesignermustcon-siderispotentialprofilesthatwillreachthecomponentwhenitisplacedinasystem.Thechoiceofauniformtestingprofileispotentiallydangerousbecausewithinasystem,onecomponentmaysendanotheraprofilethatcontains‘spikes,’asdescribedinSection4.5.Thedevelopercanrespondtothisproblemonlybybeingcarefultoconsiderasmanydifferentbehaviorsaspossible,assigningeachitsownsubdomain.Forthisthe‘functional’subdomainsob-tainedfromthecomponent’sspecificationareappropriate.Thedeveloperisnotassigningprofileweightings,andsocanarbitrarilydecomposefunctionaldomainsbasedonanysubjectivecriteriaof‘sameness.’
Hencethebestcandidatesubdomainsforcomponenttest-ingareanintersectionofnaturalstructural-andfunctional-testingsubdomains,assuggestedbyRichardsonandClarke[22].However,theselectionofsubdomainsingeneralisanopenresearchproblem.
7.1Profile-independentComponents
Althoughitisgenerallyacceptedthatcorrectnessproofsarenotapracticalmethodofsoftwareverification,fortheseriouscomponentdeveloperthispositionmayneedrethink-ing.Therestrictedsizeofcomponents,andtheexistenceofgoodspecifications,maymakeproofanattractivealterna-tivetotesting.Thegreatvirtueofacorrectnessproofinourtheoryisthatthereliabilitymappingisprofileindepen-dent,andwhereacombinationofcomponentsincludesonlythoseprovedcorrect,itisunnecessarytocarryalongandtransformtheprofile.Inthisproperty,twospecialcasesareasgoodasproof:
Exhaustivetesting.Acomponentwithonlyafiniteinput
domaincanbeexhaustivelytestedsothatitsreliabil-itymappingis1;Knight[9]hassuggestedthatthiskindofdesignispossiblemoreoftenthanonemightthink.Self-checking.ManuelBlum[3]andPaulAmmann[2]have
independentlysuggestedthatsomeprogramscanbemadetoperformrandomredundancychecksatruntime,whicharesufficienttoestimateacomponentreliabilityindependentofprofile.Althoughtherelia-bilityofsuchacomponentisnot1,itisprofileinde-pendent.
7.2RelaxingAssumptions
Theprimarylimitingassumptionofthetheorypresentedhereisthatcomponentsarespecifiedtocomputepurefunc-tions.Afunctional-programmingparadigmexplicitlyavoidsstate,andsothistheoryappliestofunctionalprogramswith-outmodification.Itisanopenquestion,whichwillonlybeaddressedbyexperienceinbuildingandcertifyingcompon-ent-basedsystems,whetheritiswisesttokeepstateoutofcomponentsandcreateitonlyatsystemlevel,orthere-verse,toconfinestatetocomponentsandhavelittleatsys-temlevel.(Theobject-orienteddevelopmentparadigmar-guesforthelatter.)Howeverstateenters,itisnotprovidedforinthetheorypresentedhere.
Theproponentsofrandomtestinghavelongarguedthatsystemstatecanbehandledwithinapure-functiontheorybyincludingextra‘statevariables’intheinputspace.Inprinciplethisideafoundersonaninputprofileforthestatevariables.Sincestate-variablevaluesarecreatedbythesys-temasitruns,theirprofileisnot,likethatoftherealinputvariables,underusercontrol.Theprofile-transformationmethodsofSection5mightbeusedtocalculateaconser-vativestate-variableprofile;thiswouldbemoststraightfor-wardforsystemstatecreatedoutsideofcomponents.
Ifstructuralsubdomainsaretobeusedforcomponenttesting,theassumptionthatthedata-sheetsubdomainsaredisjointmustberelaxed.Assuggestedinreference[8],itisalwayspossibletoformatruepartitionbyintersectionorunionofoverlappingsubdomains,buttherehasbeennoinvestigationofthesomewhatpeculiarsubdomainsthatre-sult.
7.3SizeofComponents
Componentsizecanqualitativelyaltertheconceptionofwhatcomponent-basedsoftwaredevelopmentmeans.Itisquitedifferenttoimagineusingamathematicalsubroutinefromaprogramming-languagelibrary,orMicrosoftwin-dowsNT,asthetypical‘component’beingconsidered.Sizedoesnotentertheproposedtheory,exceptthroughtheim-plicitassumptionthatthecomponentdeveloperhastestedacomponenttoprepareitsdatasheet.Itissillytoimag-inethatsoftwareofthesizeandcomplexfunctionalityofanoperatingsystem(orevenacompiler)canbetestedasawhole,thatitspropersubdomainscanbedefined,andrandomtestsconductedtomakethistheoryapplicable.Ifthistheorydoesindeeddescribethecircumstancesunderwhichareliablesystemcanbebuiltfromreliablecompo-nents,thenitfollowsthatsuchsystemsmustbebuiltfromsmallercomponents,onesforwhichdirectmeasurementsarefeasible.Beforeanoperatingsystemcouldbeconsid-eredasacomponent,itwouldhavetobeanalyzedintoitsowncomponents.
Componentsizedoesenterthetheorythroughtheas-sumptionthatcomponentsdonotinvokeothercomponents.
Solongasthemeasurementsrequiredoncomponentscanbemade,thisassumptionisnotrestrictive.Ifadeveloperchoosestocreateacomplexcomponent,itcanbeanalyzedintwoways:Eithertheinternalstructurecanbeignoredandthedatasheetpreparedfrommeasurementsforthewhole;or,itcanbetreatedasa(sub)system,anditsdatasheetmap-pingsobtainedfromthoseofrestrictedcomponentsusingthetechniquesofSection5,inarecursivefashion.
8FutureWork
Aplausibletheoryisthefirststepontheroadtounder-standingsystemqualitybasedoncomponentquality.How-ever,anytheorymustbevalidated.
8.1ExperimentalValidation
Mostexperimentalsoftwareresearchisverydifficulttoperformandconsequentlyofdoubtfulvalue.Softwarede-velopmentisacomplexprocess,anddifferentapplicationsaredevelopedinsignificantlydifferentways.Sotheinves-tigatorseekingtovalidateapracticaltechniquefacesanex-tensive,hardtocontrolenvironment,andhasdifficultychar-acterizing‘typical’projectsforstudy.Theparadigmofthe-oreticalhypothesissuggestingpointedexperimentalworkthatsuggestschangesintheory—thephysical-sciencemodelthathasbeensosuccessful—doesnotworkforsoftwaretheories.
Butwearenotproposingasoftwaredevelopmentpro-cess,orevenatechniqueforpracticaluse.Rather,wearetryingtodiscoverandunderstandthefundamentalwaysinwhichcomponentreliabilitiescombineandinfluenceeachotherinasystem.Itmaybethattheunderstandinggainedwillleadtopracticaldevelopmentprocedures,perhapsevenbrute-forceapplicationofthebasiccompositionconstruc-tiontodesignreliablesystems,butthatisnotthesubjectforinitialvalidation.
Thephysical-sciencemodelofexperimentsthatdirectbasictheoryapplieshere.Anyparticularpieceofsoftwareismadeupofcomponents,whichcanbeidentifiedexpostfacto,anddatasheetscanbederivedfromtestingofthesecomponents.Usinganarbitrarysystemoperationalprofile,thetheorycanbeusedtocalculatesystemreliability.Thenthesystemreliabilitycanbemeasuredusingconventionalrandomtestingwiththatprofile.Comparingthemeasuredvaluewiththatcalculatedfromcomponentvaluesprovidesanoverallcheckofthetheory.Asinglesystemcanbethesourceofmanyexperiments,byvaryingthesysteminputprofile,andbyvaryingthegranularityoftheunitschosentobeitscomponents.Whentherearediscrepanciesbetweentheoryandexperiment,suchanexperimentcontainsinter-mediateinformationtohelpimprovethetheory.Instrumen-tationofthesystemundertestwillyieldtheprofilesinducedateachcomponent,forcomparisonwiththosecalculatedfromthetheory.So-called‘toy’programs,usuallyunin-
formativeaboutsoftwareissues,arethebestsubjectsforrevealingexperiments.Beginningprogrammingtextbooksareagoodsourceofprograms,andsimpleUNIXcommandimplementationsareanother.Apreliminaryexperimentre-portedin[17]usedtheUNIX‘grep’program.Sincegrepisasubroutine-basedprogram,ithadtobebrokenintoar-tificialcomponentsasdescribedinSection5.2.Thisexper-imentwasthesourceofimprovedunderstandingof‘gluelogic,’andyieldedpromisingresults.
8.2ApplicationtoPractice
Ifthistheoryleadstoapracticalparadigmforcomponent-basedsoftwareengineering,itwillbeoneinwhichcompo-nentdeveloperspreparedatasheets,andsystemdesignersusethemtoselect‘goodenough’componentsandtoeval-uatesystemdesigns.Theexperimentalinvestigationssug-gestedinSection8.1requiretheinvestigatorstothemselvesusethisparadigm.Inprinciple,theworkcanbedoneus-ingexistingtoolsandhandcalculation,muchaswasdoneintheexampleofSection4.4.Weplantodevelopresearchprototypesoftoolstoeasetheburdenofhandcalculation.Randomtestingbythecomponentdeveloperisawellunderstoodprocessthatdoesnotrequirenewtools.Itisthesystemdesignerwhoneedspracticalhelpapplyingthisthe-ory.Evenasimplesystemstructurerequiresmanyapplica-tionsofthebasiccompositionconstructionofSection4.3.Itmaybenecessaryforthesystemdesignertotryanumberofsysteminputprofiles,andanumberoftrialdesigns,thusrepeatingthesemanyconstructions.
Asupportingtoolwouldtakeasinputasystemcontrolstructure,anassumedoperationalprofileforthesysteminhistogramform,acollectionofcomponents’datasheets,andtheexecutablecomponentsthemselves.Itwouldthenapplythebasiccompositionconstructiontomapthesysteminputprofilethroughtoeachcomponentinturn,calculateitsreliabilityinplace,andcombinethesecomponentrelia-bilitiesintoasystemreliability.Theexistenceofatoolwillnotonlymaketheexperimentalworkmucheasier,butwillallowmeasurementstobemadeonhowefficientthebrute-forcealgorithmsare,andwhethertheyscaletosystemsofpracticalsize.
References
[1]A.F.Ackerman.http//:www.izdsw.org/projects/-CodeGrades/index.html.
[2]P.AmmannandJ.C.Knight.Datadiversity:anapproachto
softwarefaulttolerance.IEEETrans.onComputers,pages418–425,1998.
[3]M.BlumandS.Kannan.Designingprogramsthatcheck
theirwork.JACM,pages269–291,Jan.1995.
[4]R.W.ButlerandG.B.Finelli.Theinfeasibilityofex-perimentalquantificationoflife-criticalsoftwarereliability.IEEETransactionsonSoftwareEngineering,19(1):3–12,Jan.1993.
[5]D.Hamlet.Randomtesting.InJ.Marciniak,editor,En-cyclopediaofSoftwareEngineering,pages970–978.Wiley,NewYork,1994.[6]D.Hamlet.Softwarecomponentdependability,a
subdomain-basedtheory.TechnicalReportRSTR-96-999-01,ReliableSoftwareTechnologies,Sterling,VA,Sept.1996.
[7]D.Hamlet.Onsubdomains:testing,profiles,andcompo-nents.InProceedingsISSTA‘00,pages71–76,Portland,OR,2000.
[8]D.HamletandR.Taylor.Partitiontestingdoesnotinspire
confidence.IEEETransactionsonSoftwareEngineering,16:1402–1411,1990.
[9]J.Knight,A.Cass,A.Fernandez,andK.Wika.Testinga
safety-criticalapplication.InProceedingsISSTA‘94,page199,Seattle,WA,1994.
[10]J.C.KnightandN.G.Leveson.Anexperimentalevalu-ationoftheassumptionofindependenceinmulti-versionprogramming.IEEETransactionsonSoftwareEngineering,SE-12(1):96–109,1986.
[11]L.KrishnamurthyandA.Mathur.Theestimationofsys-temreliabilityusingreliabilitiesofitscomponentsandtheirinterfaces.InProceedings8thIntl.SymposiumonSoftwareReliabilityEngineering,Albuquerque,NM,USA,Nov.1997.
[12]S.Kubal,J.May,andG.Hughes.Buildingasystemfail-urerateestimatorbyidentifyingcomponentfailurerates.InProceedingsFifthInternationalSymposiumonSoftwareReliabilityEngineering,pages32–41,BocaRaton,Florida,USA,Nov.1999.IEEE.
[13]J.-C.Laprie.Dependabilityevaluationofsoftwaresystems
inoperation.IEEETransactionsonSoftwareEngineering,10(6):701–714,Nov.1984.
[14]J.-C.LaprieandK.Kanoun.SoftwareReliabilityandSystem
Reliability,pages27–70.InLyu[16],1996.[15]B.Littlewood.Softwarereliabilitymodelformodu-larprogramstructure.IEEETransactionsonReliability,
28(3):241–246,Aug.1979.
[16]M.Lyu,editor.HandbookofSoftwareReliabilityEngineer-ing.McGraw-Hill,NewYork,1996.
[17]D.MasonandD.Woit.Softwaresystemreliabilityfrom
componentreliability.InProc.of1998WorkshoponSoft-wareReliabilityEngineering(SRE’98),Ottawa,Ontario,July1998.
[18]D.MasonandD.Woit.Inputdomainanalysisforsoftware
reliabilitymeasurement.InTheFifthInternationalConfer-enceonComputerScienceandInformatics,AtlanticCity,USA,Feb.2000.
[19]J.Musa,G.Fuoco,N.Irving,andD.Kropfl.TheOpera-tionalProfile,pages167–216.InLyu[16],1996.
[20]D.Parnas.Ona“Buzzword”:Hierarchicalstructure.In
Proc.IFIPCongress,pages336–339.North-HollandPub-lishingCo.,1974.
[21]D.PetersandD.L.Parnas.Generatingatestoraclefrom
programdocumentation.InProceedingsISSTA‘94,pages58–65,Seattle,WA,1994.
[22]D.J.RichardsonandL.A.Clarke.Partitionanalysis:A
methodcombiningtestingandverification.IEEETrans-actionsonSoftwareEngineering,11(12):1477–1490,Dec.1985.
[23]D.WoitandD.Mason.Softwarecomponentindependence.
InProc.3rdIEEEHigh-AssuranceSystemsEngineeringSymposium(HASE’98),Washington,DC,Nov.1998.
因篇幅问题不能全部显示，请点此查看更多更全内容