Symbolisk modellkontroll ger delvis effektiva verifieringsförfaranden som kan hantera system med ett oändligt tillståndsutrymme. Så kallade "accelerationsmetoder" ökar konvergensen av fixpunktsberäkningar genom att beräkna den transitiva stängningen av vissa övergångar. I detta dokument utvecklar vi en ny ram för symbolisk modellkontroll med accelerationer. Vi föreslår och analyserar också nya symboliska algoritmer med hjälp av accelerationer för att beräkna tillgänglighetsuppsättningar. Sammanhang. Utvecklingen av modellkontrollteknik [19] för obegränsade statliga system är nu ett aktivt forskningsområde. Dessa tekniker gör det möjligt att överväga modeller som pushdown system [13], kanalsystem [1, 14], räknare system [8, 31, 38], och många andra mångsidiga familjer av modeller. Sådana modeller är mycket uttrycksfulla och leder ofta till obeslutsamma kontrollproblem. Detta avskräckte inte flera forskargrupper från att utveckla kraftfulla innovativa modellkontroller för oändliga statliga system. Till exempel verktyg för att kontrollera tillgängligheten egenskaper räknare system är ALV [6], BRAIN [37], LASH [33], TREX [3], och vår egen FAST [8]. För oändliga system måste modellkontroll vara "symbolisk" eftersom man manipulerar (symboliska representationer av) potentiellt oändliga uppsättningar av konfigurationer. De mest populära symboliska representationerna är baserade på vanliga språk: dessa är ganska uttrycksfulla och automatiska-teoretiska datastrukturer ger effektiva algoritmer som utför set-teoretiska operationer samt pre- och post-image beräkningar. Med dessa ingredienser blir det möjligt att starta en fixpoint beräkning för framåt eller bakåt räckvidd uppsättningar, som exemplifieras i [32]. Konvergensproblemet. När det gäller system med oändliga tillstånd har en naiv fixpoint-beräkningsmetod för att uppnå resultat, i stil med förfarande 1 (avsnitt 3.2), mycket liten chans att upphöra: konvergens i ett begränsat antal steg kan endast ske om det system som studeras är enhetligt avgränsat (se avsnitt 3.2). För att göra fixpoint Flat Acceleration i Symbolic Model Checking 475 beräkningar konvergera oftare, har så kallade "acceleration tekniker" utvecklats. Dessa tekniker kan beräkna undergrupper av den tillgängliga uppsättningen som inte är jämnt avgränsade. Detta kan exempelvis göras genom att ersätta en kontrollloop "x:=x+1; y:=y-1" med dess transitiva stängning "k:=random int(); x:=x+k; y:=y-k". För närvarande finns det många olika accelerationstekniker för olika familjer av system [1, 2, 12, 14, 26, 38]. Några av dem har genomförts [3, 8, 33] och lovande fallstudier har rapporterats [1, 2, 3, 8, 9]. Acceleration delar vissa likheter med de vidgade metoder som används i abstrakt tolkning [22] men uppvisar också vissa tydliga skillnader: acceleration syftar till exakt beräkning för vissa givna kontrollstrukturer, medan breddning mestadels ignorerar kontrollstrukturer och vanligtvis handlar exakthet för uppsägning. Ett område i behov av stiftelser. De befintliga accelerationsresultaten är vanligtvis ett (ibland svårt) teorem som anger att en åtgärds tillfälliga stängning, eller en sekvens av åtgärder, kan beräknas på ett effektivt sätt. Svårigheten med dessa resultat ligger vanligtvis i att hitta de exakta villkoren för åtgärden och i de inledande tillstånd som ger effektivitet. Hur man använder accelerationsresultat är inte riktigt känt: teorem och algoritmer för att beräkna tillgänglighetsuppsättningar med accelerationsmetoder finns inte i allmänhet! Med vissa verktyg, t.ex. LASH, måste användaren välja vilka slingor som ska accelerera och hur man ska blanda resultaten med mer standardiserade symboliska beräkningar; i andra fall, t.ex. med TREX, genomförs en viss standardstrategi utanför någon teoretisk ram och utan diskussioner om dess effektivitet eller fullständighet. Vi föreslår den första teoretiska ramen för symbolisk modellkontroll med acceleration. Vi skiljer tre naturliga nivåer för accelerationer ("loop", "flat" och "global"), beroende på vilka sekvenser av övergångar som kan beräknas: transitiv stängning av cykler (resp. längd 1) för plan (spe. slinga) acceleration, eller en regelbunden uppsättning sekvenser för global acceleration. Dessa nivåer kan redogöra för de flesta accelerationsresultat på specifika system (pushdown system, kanal system, räknare system,. ... ).......................................................................................................... För varje nivå ger vi en symbolisk algoritm med acceleration computing reachability set och vi karakteriserar de villkor som krävs för dess uppsägning. Flatacceleration är den mest intressanta nivån. I själva verket är inte slingaccelerationen tillräcklig för många av de exempelsystem som vi har analyserat med vårt verktyg FAST. Dessutom kan majoriteten av de befintliga accelerationsresultat som anges på accelerationsnivån för slingor utökas till nivån för schablonacceleration. I andra änden av spektrumet är global acceleration alltid tillräcklig, men den förekommer mycket sällan i praktiken och är i huvudsak begränsad till särskilda underklasser (t.ex. pushdown-system, reverserade räknarsystem [31] eller särskilda underklasser av Petri-nät). (2) Vi utvecklar nya koncept för algoritmiska studier av plan acceleration. Begreppen till platta och plana system ger den nödvändiga bron mellan platt acceleration och effektiv beräkning av tillgänglighetsmängden. Vi föreslår nya symboliska förfaranden och analyserar dem noggrant. Vi visar att förfarandet REACH2 upphör om det tillämpas på ett plant (i stället för plant) system, vilket är det första fullständighetsresultatet på symbolisk modellkontroll med acceleration. Vi noterar att de flesta fallstudier som vi analyserade i tidigare arbeten med FAST är platta men inte platta, vilket understryker betydelsen av detta koncept.
REF presenterar en övergripande ram för olika klasser av system som kan behandlas med exakt acceleration.
Flat acceleration in symbolic model checking
{'venue': "In ATVA'2005. LNCS 3707", 'journal': None, 'mag_field_of_study': ['Computer Science']}