Vi presenterar den första verifieringen av fullständig funktionell korrekthet för en rad länkade datastrukturimplementeringar, inklusive muterbara listor, träd, grafer och hashtabeller. Vi presenterar specifikt användningen av Jahob-verifieringssystemet för att verifiera formella specifikationer, skrivna i klassisk högre ordningslogik, som helt fångar det önskade beteendet hos Java datastrukturimplementeringar (med undantag för egenskaper som innefattar exekveringstid och/eller minnesförbrukning). Med tanke på att de önskade korrekthetsegenskaperna omfattar svåråtkomliga konstruktioner som kvantifierare, transitiv stängning och lambda-uttag är det en utmaning att framgångsrikt bevisa de genererade verifieringsförhållandena. Vårt Jahob-verifieringssystem använder ett integrerat resonemang för att dela upp varje verifieringsvillkor i en kombination av enklare underformer och sedan tillämpa en mångfald av specialiserade beslutsförfaranden, första ordningens teoremprovare och, i värsta fall, interaktiva teoremprovare för att bevisa varje underformel. Tekniker som att ersätta komplexa underformer med starkare men enklare alternativ, utnyttja strukturer som finns i kontrollförhållandena, och vid behov infoga verifierade lemmas och bevis tips i den tvingande källkoden gör det möjligt att sömlöst integrera alla specialiserade beslutsförfaranden och teorem bevis i ett enda kraftfullt integrerat resonemang system. Genom att på lämpligt sätt tillämpa flera bevis tekniker för att urladdning olika underformer, detta resonemang system kan effektivt bevisa de komplexa och utmanande kontrollförhållanden som uppstår i detta sammanhang.
Zee och Al. I REF presenterades till och med den första kontrollen av fullständig funktionell korrekthet för vissa länkade genomföranden av datastruktur.
Full functional verification of linked data structures
{'venue': "PLDI '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}