Design and Implementation of a Special Purpose Static Program Analyzer
24
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
24
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Supérieur
Design and Implementation of a Special-Purpose Static Program Analyzer for Safety-Critical Real-Time Embedded Software Bruno Blanchet1, Patrick Cousot1, Radhia Cousot2, Jérôme Feret1, Laurent Mauborgne1, Antoine Miné1, David Monniaux1, Xavier Rival1 1 CNRS & École normale supérieure, 75005 Paris, France 2 CNRS & École polytechnique, 91128 Palaiseau cedex, France Abstract. We report on a successful preliminary experience in the de- sign and implementation of a special-purpose Abstract Interpretation based static program analyzer for the verification of safety critical embed- ded real-time software. The analyzer is both precise (zero false alarm in the considered experiment) and efficient (less than one minute of analysis for 10,000 lines of code). Even if it is based on a simple interval analysis, many features have been added to obtain the desired precision: expan- sion of small arrays, widening with several thresholds, loop unrolling, trace partitioning, relations between loop counters and other variables. The efficiency of the tool mainly comes from a clever representation of abstract environments based on balanced binary search trees. Dedicated to Neil Jones, for his 60th birthday. 1 Introduction 1.1 General-Purpose Static Program Analyzers The objective of static program analysis is to automatically determine run-time properties, statically, that is, at compile-time. This problem is in general un- decidable, so static program analysis relies on approximations as formalized by Abstract Interpretation [8,9].
Voir
Design and Implementation of a Special-Purpose Static Program Analyzer for Safety-Critical Real-Time Embedded Software Bruno Blanchet1, Patrick Cousot1, Radhia Cousot2, Jérôme Feret1, Laurent Mauborgne1, Antoine Miné1, David Monniaux1, Xavier Rival1 1 CNRS & École normale supérieure, 75005 Paris, France 2 CNRS & École polytechnique, 91128 Palaiseau cedex, France Abstract. We report on a successful preliminary experience in the de- sign and implementation of a special-purpose Abstract Interpretation based static program analyzer for the verification of safety critical embed- ded real-time software. The analyzer is both precise (zero false alarm in the considered experiment) and efficient (less than one minute of analysis for 10,000 lines of code). Even if it is based on a simple interval analysis, many features have been added to obtain the desired precision: expan- sion of small arrays, widening with several thresholds, loop unrolling, trace partitioning, relations between loop counters and other variables. The efficiency of the tool mainly comes from a clever representation of abstract environments based on balanced binary search trees. Dedicated to Neil Jones, for his 60th birthday. 1 Introduction 1.1 General-Purpose Static Program Analyzers The objective of static program analysis is to automatically determine run-time properties, statically, that is, at compile-time. This problem is in general un- decidable, so static program analysis relies on approximations as formalized by Abstract Interpretation [8,9].
- program analyzers
- real
- software model
- problems such
- effectiveness problems
- general-purpose static
- safety critical
- special-purpose static
Publié par
Langue
English
DesignandImplementationofaSpecial-PurposeStaticProgramAnalyzerforSafety-CriticalReal-TimeEmbeddedSoftwareBrunoBlanchet1,PatrickCousot1,RadhiaCousot2,JérômeFeret1,LaurentMauborgne1,AntoineMiné1,DavidMonniaux1,XavierRival11CNRS&Écolenormalesupérieure,75005Paris,France2CNRS&Écolepolytechnique,91128Palaiseaucedex,FranceAbstract.Wereportonasuccessfulpreliminaryexperienceinthede-signandimplementationofaspecial-purposeAbstractInterpretationbasedstaticprogramanalyzerfortheverificationofsafetycriticalembed-dedreal-timesoftware.Theanalyzerisbothprecise(zerofalsealarmintheconsideredexperiment)andefficient(lessthanoneminuteofanalysisfor10,000linesofcode).Evenifitisbasedonasimpleintervalanalysis,manyfeatureshavebeenaddedtoobtainthedesiredprecision:expan-sionofsmallarrays,wideningwithseveralthresholds,loopunrolling,tracepartitioning,relationsbetweenloopcountersandothervariables.Theefficiencyofthetoolmainlycomesfromacleverrepresentationofabstractenvironmentsbasedonbalancedbinarysearchtrees.DedicatedtoNeilJones,forhis60thbirthday.1Introduction1.1General-PurposeStaticProgramAnalyzersTheobjectiveofstaticprogramanalysisistoautomaticallydeterminerun-timeproperties,statically,thatis,atcompile-time.Thisproblemisingeneralun-decidable,sostaticprogramanalysisreliesonapproximationsasformalizedbyAbstractInterpretation[8,9].Forexample,typableprogramsdonotgowrongbutuntypableprogramsdonotallgowrong.Inmanycontexts,suchasprogramtransformation,theuncertaintyinducedbytheapproximationisacceptable.Forexample,intervalanalysiscanbeusedtoeliminateuselessarrayboundchecksatrun-time[7].Theselectionrate(i.e.theproportionofpotentialalarmsthataredefinitivelysolvedeitherpositivelyornegatively)isoftenbetween80and95%,sotheoptimizationisworthwhile.Moreover,itiscorrectsincetheremaining5to20%casesforwhichtestscannotbeeliminatedatcompile-timewillbecheckedatrun-time.Sometimes,staticprogramanalysiscandiscoverdefiniteerrorsatcompile-time(e.g.uninitializedvariables),whichisusefulfordebugging.Theobjectivesofsuchgeneral-purposestaticprogramanalyzersare:
1.tofullyhandleageneralpurposeprogramminglanguage(suchasAdaorC,includingthestandardlibraries);2.torequirenouser-providedspecification/annotation(exceptmaybelightonessuchas,e.g.,rangesofinputvariablesorstubsforlibraryfunctionsthesourceofwhichisnotavailable);3.tobepreciseenoughtoprovideinterestinginformationformostprograms(e.g.informationpertinenttostaticprogrammanipulationordebugging);4.tobeefficientenoughtohandleverylargeprograms(fromacostofafewmegabytesandminutestogigabytesandhourswhendealingwithhundredsofthousandsofsourcecodelines).Suchgeneral-purposestaticprogramanalyzersareverydifficulttodesignbe-causeofthecomplexityofmodernprogramminglanguagesandsystems.Somearecommerciallyavailableandhavehadsuccessesinrepairingfailuresorpre-ventingthemintheearlydevelopmentofprograms.Sincethecoverageis100%,thefalsealarmscanbehandled,e.g.,byclassicaltestingmethods,thusreduc-ingtheneedforactualtestofabsenceofrun-timeerrorbyaneconomicallysignificantfactorof80to95%.1.2ProgramVerificationInthecontextofsafetycriticalreal-timesoftwareasfound,e.g.,inthetrans-portationindustry,run-timecheckingoferrorsmaynotbeacceptableatall.Hence,thedebuggingcostisveryhighandsignificantlyhigherthanthesoftwaredevelopmentcostitself.Inthisparticularindustrialcontextwherecorrectnessisrequiredbysafetyandcriticality,rigorousformalmethodsshouldbedirectlyapplicableandeconomicallyaffordable.DeductiveMethods.Inpractice,deductivemethods(see,forexample,[1,17])arehardtoapplywhenlackingaformalspecificationandwhentheprogramsizeisverylarge.Indeed,thecostfordevelopingthespecificationandtheproof,evenwithaproofassistantoratheoremprover,isingeneralmuchhigherthanthecostfordevelopingandtestingoftheprogramitself(figuresof600person-yearsfor80,000linesofCcodehavebeenreported).Onlycriticalpartsofthesoftwarecanbecheckedformallyanderrorsappearelsewhere(e.g.atinterfaces).Moreover,forembeddedsoftwarewithalifetimeoftentotwentyyears,boththeprogramanditsproofhavetobemaintainedoverthatlongperiodoftime.SoftwareModelChecking.Softwaremodelchecking(see,forexample,[12])isalsohardtoapplywhenlackingaformalspecificationandwhentheprogramsizeisverylarge.Thisisbecausethecostofdevelopingboththespecificationandthemodeloftheprogramcanalsobeverylarge.Problemssuchasthedifficultytoprovidesensibletemporalspecificationsorthestateexplosionarewell-known.Ononehand,ifthemodelisnotprovedcorrect,thentheprogramcorrectnesscheckisnotrigorousandmostlyamountstodebugging.Ontheotherhand,the
