Abstrakt. Problemet med statsexplosion är en av de viktigaste flaskhalsarna vid modellkontroll av samtidig programvara. Vi visar hur man kan lindra problemet genom att kombinera förmågan av partiell ordning tekniker för att minska tillståndet utrymme av det samtidiga programmet med kraften av symbolisk modellkontroll för att utforska stora tillstånd utrymmen. Vår nya verifieringsmetod innebär att omvandla det givna samtidiga programmet till en kretsbaserad modell som ger oss flexibiliteten att sedan använda någon modellkontrollteknik av val -antingen SAT eller BDD-baserad - för att verifiera ett brett spektrum av linjära tidsegenskaper, inte bara säkerhet. Minskningen av det utforskade tillståndet-rymd erhålls genom att statiskt öka den symboliska kodningen av programmet genom ytterligare begränsningar. Dessa begränsningar begränsar schemaläggaren att välja mellan en minimal villkorlig envis uppsättning övergångar vid varje stat. Ett annat viktigt bidrag i dokumentet, är en ny metod för att upptäcka transaktioner i farten som tar hänsyn till mönster för lock förvärv och ger bättre minskningar än befintliga metoder som bygger på en lockset baserad analys. Dessutom till skillnad från befintliga tekniker, identifiera on-the-fly transaktioner inte kräver programmet att följa en lås disciplin för att få tillgång till delade variabler. Vi har tillämpat våra tekniker på Daisy testbänken och visat förekomsten av flera buggar.
I arbetet inom REF behandlas lockförvärvsmönster för att förfina begreppet självständighetsövergång, vilket senare leder till bättre minskningar.
Symbolic model checking of concurrent programs using partial orders and on-the-fly transactions
{'venue': 'In CAV’06: International Conference on Computer Aided Verification', 'journal': None, 'mag_field_of_study': ['Computer Science']}