Imposing assertions in Maude via program transformation

Method

Article

Imposing

assertions

in

Maude

via

program

transformation

María

Alpuente

a,

*

,

Demis

Ballis

b,1

,

Julia

Sapiña

a,2

a_{VRAIN(ValencianResearchInstituteforArtificialIntelligence),UniversitatPolitècnicadeValència,Camino}

deVeras/n,Apdo22012,46071Valencia,Spain

b

DMIF,UniversityofUdine,ViadelleScienze,206,33100Udine,Italy ABSTRACT

Programtransformationiswidelyusedforproducingcorrectmutationsofagivenprogramsoastosatisfythe user’sintentthatcanbeexpressedbymeansofsomesortofspecification(e.g.logicalassertions,functional specifications,referenceimplementations,summaries,examples).Thispaperdescribesanautomatedcorrection methodologyforMaudeprogramsthatisbasedonprogramtransformationandcanbeusedtoenforceasafety policy,givenbyasetAofsystemassertions,inaMaudeprogramRthatmightdisprovesomeoftheassertions.The outcomeofthetechniqueisasafeprogramrefinementR'ofRinwhicheverycomputationisagoodrun,i.e.,it satisfiestheassertionsinA.Furthermore,thetransformationensuresthatnogoodrunofRisremovedfromR'. Advantagesofthiscorrectionmethodologycanbesummarizedasfollows.

Afullyautomaticprogramtransformationfeaturingbothprogramdiagnosisandrepairthatpreservesall executabilityrequirements.

Asimplelogicalnotationtodeclarativelyexpressinvariantpropertiesandothersafetyconstraintsthrough assertions.

Nodynamicinformationisrequiredtoinferprogramfixes:themethodologyisstaticanddoesnotneedto collectanyerrorsymptomatruntime.

©2019TheAuthor(s).PublishedbyElsevierB.V.ThisisanopenaccessarticleundertheCCBYlicense(http:// creativecommons.org/licenses/by/4.0/).

ARTICLE INFO

Methodname:TransformationmethodforenforcingsysteminvariantsinMaudeprograms

Keywords:Assertionenforcement,Automatedprogramtransformation,Programrepair,Equationalrewriting,Rewritinglogic, Maude

Articlehistory:Received12April2019;Accepted31October2019;Availableonline6November2019

*Correspondingauthor.

E-mailaddresses:[email protected](M.Alpuente),[email protected](D.Ballis),[email protected](J.Sapiña).

1 _{https://users.dimi.uniud.it/demis.ballis/.} 2

http://personales.upv.es/jusasan.

https://doi.org/10.1016/j.mex.2019.10.035

2215-0161/©2019TheAuthor(s).PublishedbyElsevierB.V.ThisisanopenaccessarticleundertheCCBYlicense(http:// creativecommons.org/licenses/by/4.0/).

ContentslistsavailableatScienceDirect

MethodsX

Shortintroductionregardingthemethodapplicabilityandmotivation

Thispaperdescribesanautomatedcorrectionmethodologythatcanbeappliedtoimposesafety properties on concurrentand nondeterministic softwaresystems that are modelled as Maude programs.Nonetheless,thecoreideaofourcorrectiontransformationcanbetransferredtovirtually anyrewriting-basedprogramminglanguage,fromsimpletermrewritingsystemsandrule-based languagessuchasCafeOBJ,OBJ,ASF+SDF,andELAN,towidespreadfunctionallanguagessuchas HaskellandErlang,providedthatthetransformationpreservestheexecutabilityconditionsrequired bythelanguage.Indeed,theproposedcorrectionmethodtransformsprogramrulesintoguarded programruleswhoseconditionssupersedethe(external)safetyassertionchecksandaresimply evaluatedbyusingtheverysamerewritinginfrastructureofthelanguage.Therefore,theprovided assertioncheckingmechanismcanbeembeddedintoanysettingthatsupportsrewritingwithan effortthatdependsonthecomplexityofthechosenformalframework.

Inthefollowing,weoutlinethecorrectionprocedureforrepairingMaudeprogramswithrespectto asafety policythatis expressedas asetof systemassertions; a similarmodusoperandican be followedtoreplicatethismethodindifferentrewritingframeworkssuchasthosementionedabove. Theadvantageofthetechniqueisthatmorerefinedversionsofaprogramcanbeincrementallybuilt withoutanyprogrammingeffortbysimplyaddingnewsafetyconstraintsintothesetofassertions. ThismakesitpossibletoadaptexistingMaudeprogramstopredefinedsafetypoliciesandallowsthe inexperiencedusertolargelyforgetaboutMaudesyntaxandsemantics.Aninfographicthatoutlines thebasicstepsofthecorrectionmethodologyisgiveninFig.1.

Ontherewriteframework

Maude[2]isahigh-performancelanguageandsystemthatef_ficientlyimplementsRewritingLogic [4],whichisalogicofchangethatseamlesslyunifiesawidevarietyofmodelsofconcurrency.AMaude programRisessentiallymadeupoftwocomponents,EandR,where

Eisacanonical(membership)equationaltheorythatmodelssystemstatesastermsofanalgebraic datatype,and

Risasetofrewriterulesthatdefinetransitionsbetweenstatesandwhichisassumedtobecoherent w.r.t.theequationsinthesetE.

CanonicityofEandcoherencebetweenRandEarefundamental executabilitypropertiesthat guaranteethesoundnessandcompletenessofMaude’sevaluationmechanism[3].

Algebraicstructuresofteninvolveaxiomslikeassociativity,commutativity,and/oridentity(also knownasunity)offunctionsymbols,whichcannotbehandledbyordinarytermrewritingbutinstead arehandledimplicitlybyworkingwithcongruenceclassesofterms.Moreprecisely,themembership equationaltheoryEisdecomposedintoadisjointunionE=D[Ax,where

thesetDconsistsof(conditional)membershipaxioms(i.e.,axiomsthatassertthetypeofsome terms) and equations that are implicitly oriented from left to right as rewrite rules (and operationallyusedassimplificationrules),and

Axisasetofalgebraicaxiomsthatareimplicitlyexpressedasfunctionattributesandaremainly usedforAx-matching.

Thesystemevolvesbyrewritingstatesusingequationalrewriting,i.e.,rewritingwiththerewrite rulesinRmodulotheequationsandaxiomsinE.Forthesakeofsimplicity,weonlyconsidertopmost Maudeprograms,thatis,Maudeprogramsinwhichrewritescanonlyhappenatthestatetoplevel position.Thisimplies thatnolocalstatechangesare allowed:inotherwords, each rewritestep completelyreplaceastates1withanewtermrepresentingthederivedstates2.In[1],increasingly

involvedMaudeprogramstructuresareconsidered(suchastopmostmoduloAxrewritetheoriesand Russiandolltheoriesthatsupportsystemstateswithrecursivelynestedstructures).

Inourframework,systemsafetypropertiesarespecifiedbymeansofassertions,thatis,logical statementsoftheformS|

f

,whereSisaterm(thestatetemplate)and

f

isaquantifier-free,first-order logicformula(thestateinvariant).AnassertionS|

f

holdsinasystemstatesiff,foreverysubtermofs thatmatches (moduloE)thealgebraicstructure ofthestatetemplateSwithsubstitution

s

,the constraintsgivenbytheinstantiatedformula

ws

aresatisfied.Inourscenario,thenotionofsatisfaction ofa(closed)instance

ws

of

w

boilsdowntoreducing

ws

toitstruthvalueviaequationalrewriting.Ifan assertiondoesnotholdinasystemstates,wesaythatthereisanassertionviolationins.

Maude'sformaltoolsarenumerousandperformdifferentanalysisandverificationtasks,either statically (e.g., Maude's theorem proverand model checker) or dynamically (Maude's assertion checker); see [1] for references. However, to the best of our knowledge, there is no previous methodologyforautomatedsafetyenforcementinMaude.

Theproposedmethod

Ourcorrectionmethodisbasedonatwo-phaseprogramtransformationtechniquethatallowsa MaudeprogramRtoberefinedintoaprogramR'w.r.t.asetofassertionsAasfollows.Letusassume thattheprogramRconsistsoftheequationsetEandtherewriterulesetR.

1ThefirstphasetranslatestheassertionsetAintoanexecutableequationaldefinitionEq(A)thatcan beusedtodetectassertionviolationswithinsystemstates.Roughlyspeaking,givenasystemstates,

ori(t’)=t.

Notethatassertioncheckingisexecutedoverrenamedversionsoftheoriginalprogramstates, whilelogicformulasareevaluatedbyusingtheoriginaloperatorsofR.Renamingiskeytoneatly separateassertioncheckingfromsystemcomputationsandavoidinterferencesthatmightjeopardize termination, con_fluence and/or coherence properties in the repaired program (for a detailed discussiononrenaming,see[1]).

2 ThesecondphasetransformstheoriginalrewriterulesofRintoguarded,conditionalrewriterules thatcanonlybefiredifnosystemassertionisviolated.Intuitively,thisisachievedbytransforming eachrewriteruler:(

l

→

r

ifC)ofRintoarefinedversionr’:(

l

→

r

ifC^ren(

r

)=/=fail)ofr,which containstheextraconstraintren(

r

)=/=failthatholdswhentherenamedapartinstancesofthe right-handside

r

oftherulercannotbesimplifiedtofailbyusingtheextendedequationaltheoryE [Eq(A).

Thisway,weensurethatanystatetransitionfromstates1tostates2isenabledintheprogramR’

onlyifs2isasafestate,thatis,everyassertionofAholdsins2.

Asanimportantadvantageofthemethod,executabilityconditionsofRandEarepreservedbythe correctiontransformation.Furthermore,themethodologycopeswithin_finitespacestatesanddoes notrequiretheknowledgeofanyfailingrun.Arigorousandcompleteformalizationofthemethodcan befoundin[1].

Atypicalcorrectiontransformationsession

To show how ourcorrection methodology works in practice, we consider a topmost Maude programRDthatspecifiesasimpledamcontrollerformonitoringandmanagingthewatervolumeofa

basin.TheworkflowofthecorrectionmethodologyisdepictedinFig.2.

Inthesequel,variablenamesarefullycapitalized.Weassumethatthedammodelisprovidedwith aspillwaycalledswhichhasthreepossibleaperturewidthsofincreasingdischargecapacityc,o1,o2. Aspillwayconfigurationisformallyspecifiedbyaterm[s,O],whereObelongstotheset{c,o1,o2}. Systemstatesaredefinedbytermsoftheform

whereSCisaspillwayconfiguration,Visarationalnumberthatindicatesthebasin watervolume(inm3_),

Tisanaturalnumberthattimestampsthecurrentconfiguration,andAC(aperturecommand)isaBoolean flagthatenableschangesofthespillwayaperturewidthsonlywhenitsvalueistrue.

3_{Notethat,inthecaseofmixfixoperators,wejustrenameoneoperatorsymbol.Forinstance,thebinary,mixfixoperator<_|}

Tokeeptheexpositionsimple,weassumethatthebasinwaterinflowisconstant,whilethebasin outflowdependsontheaperturewidthofthecurrentspillwayconfiguration.Basininflowandoutflow aremeasuredinm3/minandarespecifiedbythefollowingMaudeequations

Notethatmorerealisticscenarioscouldbeeasilydefinedbyspecifyingmoresophisticatedbasin inflowandoutflowfunctions.

Thedamcontrollerdynamicsismodeledbythefollowingeightrewriterules,whichimplement systemstatetransitions.

TheopenX-Yrewriterulesprogressivelyincrementtheaperturewidthofthespillways(e.g.,the ruleopen1-2increasestheapertureofthespillwaysfromlevelopen1tolevelopen2).Dually,closeX-Y rewriterulesprogressivelydecreasetheaperturewidthofaspillway.Therulenocmdspecifiesthe emptycommand,which basicallystatesthatnoaction istaken onthespillwayconfiguration by thedam controllerat time instantT. Theruleis firedonlywhen theAC flagis enabled,and its applicationdisablestheflagtoallowanewbasinwatervolumetobecomputedinthenexttime instant.Theserulesimplementinstantaneousspillwaymodificationsthatdonotchangethetime instantorthebasinwatervolume.

Thetemporalevolution ofthebasinwatervolumeisspecifiedbytheconditionalrewriterule volumethatcomputesthevolumeWattime T+deltaT,giventheinputvolumeVattime T.The parameterdeltaTismeasuredinminutesandcanbesetbytheuser.Thevolumecomputationchanges theinputvolumeVbyaddingthewaterinflowandsubtractingthecorrespondingwateroutflowover thedeltaTinterval.

TheuseoftheACflagintheruledefinitionsguaranteesafairinterleavingbetweentheapplications oftherulevolumeandtheremainingrewriterules.Specifically,thisimpliesthatanewbasinwater volumeiscomputedaftereachspillwayaperturewidthmodification.

NotethatcomputationsinRDmayreachpotentiallyhazardoussystemstates(e.g.,anextremely

highwater volume), since RD does not implement any spillway management policy that safely

These equations allow any renamed system state to be rewritten to fail whenever the correspondingassertionisviolated.

ThesecondphasetransformseachrewriteruleofRDintotheirrefinedconditionalcounterpartas

follows:

Byusingtherefinedrulesabove,anystatetransitionfromastates1toastates2occursonlywhens2

doesnotviolatetheassertionsinAD,therebyenforcingasafebehaviorofthecorrecteddamcontroller.

Methodimplementationandvalidation

ThecorrectionmethodologyhasbeenimplementedintheATAMEsystemthatisavailableathttp:// safe-tools.dsic.upv.es/atame.WeconductedathoroughexperimentalevaluationusingATAMEthat demonstratesgoodperformance(regardingcodesize,executiontime,andprogramtransformation time)for anumber ofbenchmarksthat areavailableand fullydescribedwithintheATAME web platformand in [1]. Asshown in[1], transformation timesare almostnegligible, andmoreover, runningthecorrectedprogramR'inMaude ismorethan50%fasteronaveragethanrunningthe originalprogramRinamonitoredenvironmentthatimplementsruntimeassertionchecking.

MaudeprogramscanbeeitheruploadedtoATAMEassimple“.maude”filesorwrittenfromscratch. Oncetheintendedassertionshavebeenalsointroducedinsideadedicatededitbox,thecorrection procedurecanbeexecutedbysimplyclickingthe“FixProgram”button,which deliversacoerced version of the program whose computations respectall the imposed assertions.Fig. 3 shows a fragmentofthedamcontrollerR’DthathasbeenautomaticallyfixedbyATAME.

Funding

ThisworkhasbeenpartiallysupportedbytheEU(FEDER)andtheSpanishMINECOundergrant RTI2018-094403-B-C32,andbyGeneralitatValencianaundergrantPROMETEO/2019/098.

DeclarationofCompetingInterest

TheAuthorsconfirmthattherearenoconflictsofinterest. Acknowledgements

Wegratefullyacknowledgetheanonymousreviewersforkindlyreviewingtheresearcharticleto whichthispaperiscompanion.

References

[1]M.Alpuente,D.Ballis,J.Sapiña,StaticcorrectionofMaudeprogramswithassertions,J.Syst.Softw.153(July)(2019)64–85. [2]M.Clavel,F.Duràn,S.Eker,S.Escobar,P.Lincoln,N.Martì-Oliet,J.Meseguer,C.Talcott,MaudeManual(Version2.7.1)

availableat:,SRIInternationalComputerScienceLaboratory,2016.http://maude.cs.uiuc.edu/maude2-manual/. [3]M.Clavel,F.Durán,S.Eker,P.Lincoln,N.Martí-Oliet,J.Meseguer,C.Talcott,AllaboutMaude-ahigh-performancelogical

framework,howtospecify,programandverifysystemsinrewriting,logic,LectureNotesinComputerScience,Springer, 2007,pp.4350.