Abstrakt. Vi presenterar en teknik för modellering och automatisk verifiering av nätverksprotokoll, baserat på grafomvandling. Den är lämplig för protokoll med ett potentiellt obegränsat antal noder, där nätverkets struktur och topologi är en central aspekt, såsom routingprotokoll för ad hoc-nätverk. Säkerhetsegenskaper anges som en uppsättning oönskade globala konfigurationer. Vi verifierar att det inte finns någon oönskad konfiguration som kan nås från en initial konfiguration, med hjälp av symbolisk bakåtåtkomlig analys. I allmänhet går det inte att avgöra om det är möjligt att nå problemet. Vi implementerar tekniken i ett graf grammatikanalysverktyg, och verifierar automatiskt flera intressanta icke-triviala exempel. Framför allt visar vi oss vara fria från slingor för DYMO:s ad hoc routingprotokoll. DYMO är för närvarande på IETF standard spår, att potentiellt bli en Internet standard.
I REF Saksena m.fl. Definiera ett eventuellt icke-avslutande symboliskt förfarande baserat på graftransformationer för att verifiera routingprotokoll för Ad Hoc Networks.
Graph grammar modeling and verification of ad hoc routing protocols
{'venue': 'Lecture Notes in Computer Science', 'journal': 'Lecture Notes in Computer Science', 'mag_field_of_study': ['Computer Science']}