Vi tar upp frågan om automatisk invariant syntes för sekventiella program som manipulerar individuellt kopplade listor som transporterar data över oändliga datadomäner. Vi definierar för detta en ram baserad på abstrakt tolkning som kombinerar en specifik finit-range abstraktion på formen av högen med en abstrakt domän på sekvenser av data, som betraktas som en parameter av metoden. Vi omedelbart vårt ramverk genom att införa olika abstraktioner om datasekvenser som gör det möjligt att resonera om olika aspekter såsom deras storlek, summor eller multiuppsättningar av deras element, eller relationer på deras data på olika (linjärt beställda eller på varandra följande) positioner. För att uttrycka de senare relationerna definierar vi en ny domän vars element motsvarar en uttrycksfull klass av första ordningens universellt kvantifierade formler. Vi har implementerat våra tekniker i ett effektivt prototypverktyg och vi har visat att vårt tillvägagångssätt är tillräckligt kraftfullt för att generera icke-triviala invarianter för en betydande klass av program. Vi definierar μ 1 M μ 2 att vara en förening av atomformler som visas i både Saturate(μ 1 ) och Saturate(μ 2 ). M μ 2 definieras som en förening av atomformler som förekommer i Saturate(μ 1 ) eller Saturate(μ 2 ). Eftersom vår abstrakta domän innehåller ett ändligt antal element, kan vi överväga  och M. Abstraktioner av k-heap grafer som i Figur 5 kallas k-abstrakt hög grafer. I följande definition antar vi att det för varje nod av en hög graf finns en dataordvariabel med samma namn. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. En k-abstrakt hög över PVar, DVar, och en DW-domän A W är en tuple H = N, S, V, W där N, S, V är som i definitionen av k-heap grafer, och W är ett abstrakt värde i A W över dataord variablerna N − {-} och datavariabler DVar. Därefter definierar vi domänen för k-abstrakt hög grafer parametrized av A W, betecknad som A H (k, A W ). Två abstrakta höggrafer är isomorfa när deras underliggande grafer Lattice-operatörerna av denna domän erhålls genom att tillämpa motsvarande operatörer från A W mellan abstrakta värden som hör till isomorfa abstrakta höggrafer. Således, för alla H = N, S, V, W och de abstrakta värdena sådan att de använder samma variabel för isomorphic noder) och (2) för Sammanfogningen och breddning (meet, resp.) av två icke-isomorfa abstrakta hög grafer är  på W ( till W, resp.). Förslag 1. Innebördsförhållandet  på H är ljud, det vill säga H  på H H ′ innebär γ H ( H)  och γ H ( H ′ ). Dessutom är H och H den minst övre gränsen och den största nedre gränsen, respektive, och H är en vidgande operatör. Bevis: Egenskaperna hos  till H,  till H, och  till H, resp. följa direkt från liknande egenskaper hos  till W,  till W, och  till W, resp. Beviset för den expanderande operatören bygger på det faktum att de högar som genereras av den programklass som avses i avsnitt 2 innehåller ett begränsat antal skärpunkter [17]. 2 Lägg märke till att H inte är komplett. Det vill säga, vi kan hitta två abstrakta högar H och H ′ sådan att γ H ( H)  till γ H ( H ′ ) inte innebär H  till H H ′. Baserat på Galois anslutning (α W, γ W ) definierar vi Galois anslutning (α H, γ H ) mellan lattice av uppsättningar av k-heap grafer och A H (k, A W ). Värdet av α H för en uppsättning isomorfa k-heap grafer S är den underliggande grafen i indata hög grafer tillsammans med ett värde i A W som erhålls genom att tillämpa α W till värdet av α H för en uppsättning k-heap grafer som innehåller minst två icke-isomorfisk hög grafer är  på H. Konkretiseringsfunktionen γ H definieras med hjälp av γ W på ett liknande sätt. Vi definierar A HS (k, A W ) = L HS (k, A W ),  en HS, en HS, en HS, en HS, en finit powerset domän som motsvarar A H (k, A W ). Dess element kallas k-abstrakt höguppsättningar. I denna förordning gäller följande definitioner: En k-abstrakt hög uppsättning över PVar, DVar, och en DW-domän A W är en ändlig uppsättning icke-isomorfisk k-abstrakt hög grafer över PVar, DVar, och A W. Operatörerna som är associerade till A HS (k, A W ) och dess bredare operatör erhålls från de av A H (k, A W ) som vanligt [7]. Innebördsförhållandet är den vanliga Hoare powerdomain partiell ordning [1], det vill säga för alla A H och A ′ H i A HS (k, A W ), A H H A ′ H iff för alla H  till A H det finns H ′ A ′ H sådan att H H H H ′ ′. Låt A H och A ′ H  på L HS. För att göra definitionerna av alla operatörer av den abstrakta domänen enhetliga, antar vi att för varje abstrakt hög N, S, V, W  på vilken vi inte kan hitta en isomorf abstrakt hög i A ′ H lägger vi till A ′ H den abstrakta högen (N, S, V, W ) och vice versa. Sedan, för alla  påse (=),  och vi definierar A H. HS A ′ H för att vara den abstrakta högen uppsättning som innehåller för två abstrakta högar H = N, S, V, W A H och H. Dessutom är H och H den minst övre och största nedre gränsen, respektive, och HS är en expanderande operatör. Bevis: Direkt från egenskaperna hos H, H, H, H och H. 2 Precis som i det tidigare fallet, notera att HS inte är komplett. Den Galois anslutning (α HS, γ HS ) mellan lattice av uppsättningar av k-heap grafer och A HS (k, A W ) definieras på följande sätt. Den abstraktion funktion α HS tillämpas på vissa uppsättning av k-hack grafer S returnerar en ändlig uppsättning k-abstract hög grafer, en för varje ekvivalens klass av S med avseende på isomorfism förhållandet. Denna k-abstrakta högkurva definieras genom att tillämpa α H på uppsättningen höggrafer i ekvivalensklassen. Konkretiseringsfunktionen γ HS är en punktvis förlängning av γ H. Den abstrakta postvillkor operatör på abstrakta höguppsättningar som motsvarar post k, betecknad post # k, erhålls genom att ersätta varje betongtransformator F  och {sglt, isSglit, split, proj, updateFirst, concat} med dess abstraktion F #. Till exempel, den abstrakta versionen av förfarandet Uncover, betecknad Uncover #, används i post # k (free(p), A H ) anges i figur 6. För varje abstrakt hög graf H = N, S, V, W i den abstrakta högen uppsättning A H, Uncover # (A H, p) gör en av följande:
Bouajjani m.fl. REF syntetiserar automatiskt invarianter för lista manipulera program över oändliga datadomäner med hjälp av en graf representation av högen.
Invariant Synthesis for Programs Manipulating Lists with Unbounded Data
{'venue': 'CAV', 'journal': None, 'mag_field_of_study': ['Computer Science']}