Abstrakt. En etablerad metod för programvaruverifiering är SAT-baserad begränsad modellkontroll där en stat rymdmodell kodas som en Boolesk formel och prospekteringen utförs via SAT-lösning. De flesta befintliga metoder i SAT-baserad modellkontroll bygger på allmänna mållösare som inte utnyttjar de strukturella egenskaperna hos kodningen. Syftar på en betydligt bättre körtid prestanda i sådana inställningar, visar vi i detta dokument att SAT algoritmer kan skräddarsys specifikt w.r.t. strukturen för Boolesk kodning av modellkontrollproblemen som ska lösas. Vi definierar ett tillstånd utrymme kodning av samtidiga mjukvarusystem som bevarar kontrollflöde information. Detta gör det möjligt att ändra lösaren så att antalet SAT beslutsnivåer kan minskas avsevärt genom att tilldela en uppsättning atomer på varje nivå. Ett sådant inställt uppdrag kännetecknar alltid en plats i det kodade systemets kontrollflöde. Dessutom introducerar vi heuristik som guidar SAT-sökningen i riktningar där en kränkning av egendomen av intresse sannolikt kan upptäckas. Det heuristiska tillvägagångssättet gör det möjligt att snabbt upptäcka fel samtidigt som den faktiskt utforskade delen av statsrymden hålls liten.
Författarna till REF föreslår en boolesk kodning för tillståndet utrymme i ett system utöver en uppsättning heuristik som påskyndar processen för att hitta feltillstånd.
Model Checking of Concurrent Software Systems via Heuristic-Guided SAT Solving
{'venue': 'FSEN', 'journal': None, 'mag_field_of_study': ['Computer Science']}