Vi tar itu med problemet med automatisk verifiering av program med dynamiska datastrukturer. Vi anser att det är fallet med sekventiella, icke-rekursiva program som manipulerar 1-väljarkopplade strukturer såsom traditionella länkade listor (eventuellt dela med sig av sina svansar) och cirkulära listor. Vi föreslår ett automatiserat tillvägagångssätt för en symbolisk verifiering av sådana program med hjälp av den vanliga modellen kontrollram. Med tanke på ett program, konfigurationerna av minnet är systematiskt kodade som ord över ett lämpligt finit alfabet, potentiellt oändliga uppsättningar av konfigurationer representeras av finit-state automata, och uttalanden av programmet automatiskt översättas till finit-state transducers som definierar regelbundna relationer mellan konfigurationer. Därefter tillämpas abstrakta regelbundna modellkontrolltekniker för att automatiskt kontrollera säkerhetsegenskaper avseende formen på de beräknade konfigurationerna eller för in- och utgångskonfigurationerna. För det, vi introducerar nya tekniker för beräkning av abstraktioner av uppsättningen av nåbara konfigurationer, och för att förfina dessa abstraktioner om falska motexempel upptäcks. Slutligen presenterar vi experimentella resultat som visar tillämpligheten av tillvägagångssättet och dess effektivitet.
Bouajjani m.fl. REF föreslår ett automatiserat tillvägagångssätt för att verifiera program med individuellt kopplade listor genom regelbunden modellkontroll.
Verifying programs with dynamic 1-selector-linked structures in regular model checking
{'venue': 'TACAS', 'journal': None, 'mag_field_of_study': ['Computer Science']}