Predikativ abstraktion har blivit en av de mest framgångsrika metoderna för att bevisa säkerhet egenskaper program. Nyligen har flera abstraktionsmetoder föreslagits för att bevisa levande egenskaper. I denna uppsats studeras "ranking abstraction" där ett program förstärks av en icke-constraining progression monitor baserad på en uppsättning rankningsfunktioner, och ytterligare abstrakteras av predicate-abstraktion, för att möjliggöra automatisk verifiering av progressegenskaper. Till skillnad från många levande metoder, behöver inte förstärkningen en komplett rankning funktion som förväntas minska med varje hjälpbart steg. I stället är adekvata användartillhandahållna indata komponentrankningar från vilka en komplett rankningsfunktion automatiskt kan bildas. Tidningens premiss är en analogi mellan metoderna för att rangordna abstraktion och predikerad abstraktion, varav en ingrediens är förfining: När predikerad abstraktion misslyckas kan man förfina den. När rankningen abstraction misslyckas, måste man avgöra om den predikata abstraktionen, eller rankningen abstraction, behöver förfinas. I dokumentet presenteras strategier för att avgöra vilket fall som är aktuellt, och metoder för att utföra de lämpliga förbättringarna. Den andra delen av analogin är att automatiskt härleda deduktiva beviskonstruktioner: Predikativ abstraktion används ofta för att härleda programinvarianter för att bevisa säkerhetsegenskaper som en booleansk kombination av de givna predikaten. Avledande bevis på framsteg egenskaper kräver välgrundade rankingfunktioner utöver invarianter. Vi visar hur de konstruktioner som krävs för att dra av bevis på en godtycklig LTL-formel automatiskt kan extraheras från en framgångsrik tillämpning av rankning abstraktionsmetoden.
I detta dokument använder vi rankning abstraktionsmetoden för REF för att verifiera levande egenskaper, och vi använder oss av rankningsfunktionerna över individuellt kopplade listor som definieras i [3].
Modular ranking abstraction
{'venue': 'Int. J. Found. Comput. Sci.', 'journal': 'Int. J. Found. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}