Abstrakt. Vi presenterar ett nytt tillvägagångssätt för automatisk verifiering av databeroende program som manipulerar dynamiska högar. En hög kodas av en graf där noderna representerar cellerna, och kanterna återspeglar pekarstrukturen mellan cellerna i högen. Varje cell innehåller en uppsättning variabler som sträcker sig över de naturliga talen. Vår metod bygger på standard bakåtåtkomlighetsanalys, där huvudidén är att använda en enkel uppsättning predikat, kallade signaturer, för att representera dåliga uppsättningar av högar. Exempel på dåliga högar är sådana som innehåller antingen sopor, listor som inte är välformade eller listor som inte sorteras. Vi presenterar resultaten för fallet med program med en enda nästa-väljare, och där variabler kan jämföras för (i)jämlikhet. Detta gör att vi kan verifiera till exempel att ett program, som bubbla sort eller insättning sort, returnerar en lista som är väl formad och sorterad, eller att sammanslagningen av två sorterade listor är en ny sorterad lista. Vi rapporterar om resultatet av att köra en prototyp baserad på metoden på ett antal program.
I REF föreslogs ett annat tillvägagångssätt för att verifiera databeroende egenskaper hos program med listor.
Automated analysis of datadependent programs with dynamic memory
{'venue': 'In ATVA', 'journal': None, 'mag_field_of_study': ['Computer Science']}