Lars Hummelgren
Ett kontraktspråk för modulär specifikation och verifikation av temporala egenskaper
Abstract
Deduktiv mjukvaruverifikation används för att bevisa korrekthet av program med avseende på kontrakt. Kontrakt uttrycks ofta på procedurer i ett program med användning av Hoare-logik. Sådana kontrakt består av ett förvillkor som specificerar ett villkor som måste gälla innan proceduren exekveras och ett eftervillkor som uttrycker vad som garanteras i gengäld. Ett kontrakt kan ses som en överenskommelse mellan användaren av en procedur och dess utvecklare.
Det är viktigt att det på ett skalbart sätt går att verifiera att procedurer i ett program uppfyller deras respektive kontrakt. Skalbarhet kan uppnås genom att se till att verifikationen är procedur-modulär, vilket innebär att varje proceduranrop direkt ersätts med kontraktet som tillhör den anropade proceduren i stället för att proceduranropet utvärderas. Hoare-logikens axiom gör den till en bra grund för procedur-modulära resonemang. Men Hoare-logik är inte välanpassad för att resonera kring en procedurs beteende under en sekvens av tillstånd. Frågorna som ställs är hur ett kontraktspråk för att specificera sådana temporala egenskaper kan utformas samt hur en procedur kan verifieras att uppfylla kontrakt uttryckta i ett sådant kontraktspråk på ett procedur-modulärt sätt.
För att besvara frågan presenteras först ett enkelt programmeringsspråk med procedurer. Syftet är att kontrakt uttrycks på program skrivna i detta programspråk. Två kontraktspråk presenteras. Det visas hur kontrakt kan formuleras i dessa språk för att specificera temporala egenskaper av procedurer samt hur procedurer kan verifieras att uppfylla sådana temporala kontrakt. Det första kontraktspråket är begränsat med avseende på dess uttrycksfullhet, men dess kontrakt kan automatiskt verifieras. Det andra språket kan användas för att uttrycka mer komplicerade egenskaper, men dess verifikationsproblem visar sig vara oavgörbart. Alternativa tillvägagångssätt för att hantera dess verifikationsproblem diskuteras.