Statslös modellkontroll är en kraftfull teknik för programverifiering, som dock lider av en exponentiell ökning av antalet utforskade utföranden. En framgångsrik teknik för att minska detta antal, samtidigt som fullständig täckning, är Dynamic Partial Order Reduction (DPOR). Vi presenterar en ny DPOR-algoritm, som är den första att vara bevisligen optimal genom att den alltid utforskar det minimala antalet utföranden. Det är baserat på en ny klass av uppsättningar, kallas källkodsuppsättningar, som ersätter rollen av ihållande uppsättningar i tidigare algoritmer. Först visar vi hur man modifierar en befintlig DPOR algoritm för att arbeta med källuppsättningar, vilket resulterar i en effektiv och enkel att implementera algoritm. För det andra, vi utökar denna algoritm med en ny mekanism, kallad wakeup träd, som gör det möjligt att uppnå optimalitet. Vi har implementerat båda algoritmerna i en statslös modellkontrollverktyg för Erlangprogram. Experiment visar att källuppsättningar avsevärt ökar prestandan och att uppvaknande träd endast ådrar sig en liten overhead i både tid och rum.
Optimala dynamiska partiella orderreduktionsREF undersöker ett minsta antal representativa trådkopplingar.
Optimal dynamic partial order reduction
{'venue': "POPL '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}