爱华网ImprovingtheN-VersionProgrammingProcess
ThroughtheEvolutionofaDesignParadigm
MichaelR.Lyu
MemberIEEEBellCommunicationResearchMorristownYu-TaoHeStudentMemberIEEETheUniversityofIowaIowaCity
Keywords−N-VersionProgramming,DesignParadigm,Experiment,ProcessEvolution,MutationTesting,ReliabilityandCoverageAnalysis.
ReaderAids−
Purpose:PresentationofanN-versionsoftwareexperimentemphasizingareviseddesignparadigmtoshowprocessandproductimprovements
Specialmathneededforexplanations:Probabilitytheory
Specialmathneededtouseresults:None
Resultsusefulto:Fault-tolerantsoftwaredesigners/experimentersandreliabilityanalysts
Abstract−ToencourageapracticalapplicationoftheN-VersionProgramming(NVP)technique,adesignparadigmwasproposedandappliedinaSix-LanguageProject.ThedesignparadigmimprovedthedevelopmenteffortoftheN-VersionSoftware(NVS),however,thereweresomedeficienciesofthedesignparadigmwhichleadtotheleakofapairofcoincidentfaults.Inthispaper,wereportasimilarexperimentconductedbyusingarevisedNVPdesignparadigm,identifyitsimpacttothesoftwaredevelopmentprocess,anddemonstratetheimprove-mentoftheresultingNVSproduct.Thisprojectreusedtherevisedspecificationofanautomaticairplanelandingproblem,andwasparticipatedby40studentsattheUniversityofIowaandtheRockwellInternational.GuidedbytherefinedNVSdevelopmentparadigm,thestudentsformed15independentprogrammingteamstodesign,program,test,andevaluatetheapplication.Theinsights,experiences,andlearningsinconductingthisprojectarepresented.SeveralquantitativemeasuresoftheresultingNVSproductareprovided,andsomecomparisonswithotherpreviously-conductedexperimentsaddressed.
-1-
ImprovingtheN-VersionProgrammingProcess
ThroughtheEvolutionofaDesignParadigm
1.Introduction
TheN-VersionProgramming(NVP)approachachievesfault-tolerantsoftwaresystems,calledN-VersionSoftware(NVS)systems,throughthedevelopmentanduseofdesigndiversity[1].SuchsystemsarenormallyoperatedonanN-VersionExecutive(NVX)environment[2].SincetheideaofNVPwasfirstproposedin[3],numerouspaperswerepublishedineithermodelingNVSsystems[4][5][6][7][8][9][10],orprovidingempiricalstudiesofNVSsystems[11][12]
[13][14][15][16][17][18].TheeffectivenessoftheNVPapproach,however,hasremainedhighlycontroversialandinconclusive.Nevertheless,mostresearchersandpractitionersagreethatahighdegreeofversionindependencyandalowprobabilityoffailurecorrelationwouldplaythekeyroleindeterminingthesuccessofanNVSdeployment.
TomaximizetheeffectivenessoftheNVPapproach,theprobabilityofsimilarerrorsthatcoin-cideattheNVSdecisionpointsmustbereducedtothelowestpossiblevalue.ToachievethiskeyelementforNVS,arigorousNVPdevelopmentparadigmwasproposedin[19].Thiseffortincludedthefoundationofdisciplinedpracticesinmodernsoftwareengineeringtechniques,andtheincorporationofrecentknowledgeandexperienceobtainedfromfault-tolerantsystemdesignprinciples.ThemainpurposeofthisdesignparadigmwastoencouragetheinvestigationandimplementationofNVStechniquesforpracticalapplications.
Thefirstapplicationofthisdesignparadigmtoareal-worldprojectwasreportedin[18]foranextensiveevaluation.Somelimitationswerealsobepresentedin[20],leadingtoacoupleofrefinementstothedesignparadigm.ToobservetheimpactoftherevisedNVPdevelopmentparadigm,asimilarprojectwasconductedattheUniversityofIowaandtheRockwellInterna-tional.Thispaperdescribesacomprehensivereportontheapplicationofthedesignparadigmtothisprojectandtheresults.InSection2,weexaminetheNVPdesignparadigmandits
-2-
refinement.Section3describestheUniversityofIowa/RockwellNVSproject.Thethreefol-lowingSectionsgiveathoroughevaluationoftheresultingNVSproduct,includingprogrammetricsandstatistics(Section4),operationaltestingandNVSreliabilityevaluation(Section5),andmutationtestingforacoverageanalysisoftheNVSsystems(Section6).Section7comparesthisexperimentwiththreepreviousexperimentsin[16][17][18].ConclusionsofthispaperareprovidedinSection8.
2.AnNVPDesignParadigmandRefinement
NVPhasbeendefinedas"theindependentgenerationofN≥2functionallyequivalentprogramsfromthesameinitialspecification[3].""Independentgeneration"meantthattheprogrammingeffortsweretobecarriedoutbyindividualsorgroupsthatdidnotinteractwithrespecttotheprogrammingprocess.TheNVPapproachwasmotivatedbythe"fundamentalconjecturethattheindependenceofprogrammingeffortswillgreatlyreducetheprobabilityofidenticalsoftwarefaultsoccurringintwoormoreversionsoftheprogram[3]."
ThekeyNVPresearchefforthasbeenaddressedtotheformationofasetofguidelinesforsys-tematicdesignapproachtoimplementNVSsystems,inordertoachieveefficienttoleranceofdesignfaultsincomputersystems.Thegradualevolutionoftheserigorousguidelinesandtech-niqueswasformulatedin[19]asanNVSdesignparadigmbyintegratingtheknowledgeandexperienceobtainedfrombothsoftwareengineeringtechniquesandfaulttoleranceinvestiga-tions.Theword"paradigm"means"pattern,example,model,"whichreferstoasetofguidelinesandruleswithillustrations.
Theobjectivesofthedesignparadigmare:
(1)toreducethepossibilityofoversights,mistakes,andinconsistenciesintheprocessof
softwaredevelopmentandtesting;
(2)toeliminatemostperceivablecausesofrelateddesignfaultsintheindependentlygen-
eratedversionsofaprogram,andtoidentifycausesofthosewhichslipthroughthe
-3-
designprocess;
(3)tominimizetheprobabilitythattwoormoreversionswillproducesimilarerroneous
resultsthatcoincideintimeforadecision(consensus)actionofanNVXenvironment.Theapplicationofaprovensoftwaredevelopmentmethod,orofdiversemethodsforindividualversions,remainsthecoreoftheNVPprocess.Thisprocessissupplementedbyproceduresthataim:(1)toattainsuitableisolationandindependence(withrespecttosoftwarefaults)oftheNconcurrentversiondevelopmentefforts,(2)toencouragepotentialdiversityamongthemultipleversionsofanNVSsystem,and(3)toelaborateefficienterrordetectionandrecoverymechan-ism.Thefirsttwoproceduresservetoreducethechancesofrelatedsoftwarefaultsbeingintro-ducedintotwoormoreversionsviapotential"faultleak"links,suchascasualconversationsormailexchanges,commonflawsintrainingorinmanuals,useofthesamefaultycompiler,etc.Thelastprocedureservestoincreasethepossibilitiesofdiscoveringmanifestederrorsbeforetheyareconvertedtocoincidentfailures.Figure1describesthecurrentNVPparadigmforthedevelopmentofNVS.
InFigure1,theNVPparadigmiscomposedoftwocategoriesofactivities.Thefirstcategory,representedbyboxesandsingle-linearrowsattheleft-handside,containstypicalsoftwaredevelopmentprocedures.Thesecondcategory,representedbyovalsanddouble-linearrowsattheright-handside,describestheconcurrentenforcementofvariousfault-toleranttechniquesundertheN-versionprogrammingenvironment.Table1summarizestheactivitiesandguide-linesincorporatedineachphaseofsoftwaredevelopmentlifecycle[19].Thisdesignparadigmhasbeenrevisedaccordingtotheexperienceofitsexecutionin[18],wherethecorrespondingamendmentsareshowninitalicsinTable1.
Thesemodificationsdonotshowdramaticchangesfromtheoriginalparadigm.Nevertheless,theyareimportantinavoidingtwotypesofspecification-relatedfaults:oneistheabsenceofappropriateresponsestospecificationupdates,andtheotheristheincorrecthandlingofmatchingfeaturesrequiredbyanNVXenvironment(e.g.,theplacementofvotingroutines).
-4-
Start
SystemRequirement
PhaseSoftwareRequirement
PhaseSoftwareSpecification
Phase
DesignPhaseCodingPhase
DetermineMethodofNVSSupervisionSelectSoftware
DiversityErrorandRecoveryAlgorithms
ConductNVSDevelopmentProtocol
TestingPhase
ExploitPresenceofNVSDemonstrateAcceptanceofNVS
EvaluationandAcceptancePhaseno
yes
OperationalPhase
andNVSMaintenancePolicy
End
Figure1:ADesignParadigmforN-VersionProgramming
-5-
