Abstrakt. Pushdown-system (PDS) modellerar naturligt sekventiella rekursiva program. Numeriska datatyper uppstår också ofta i verkliga program. Vi studerar utbyggnaden av PDS med obundna räknare, som naturligt modellerar numeriska datatyper. Även om denna förlängning är Turingpowerful, är nåbarhet känd för att vara decidable när antalet omsvängningar mellan ökande och minskande lägen begränsas. I detta dokument preciserar vi 1) hur lättåtkomlig och linjär/grenad tidsmodell som kontrollerar PDS med reverserade räknare (PCo) och 2) experimentellt visar hur effektivt vårt tillvägagångssätt är när det gäller att analysera programvara. Vi visar tillgänglighet över PCo är NP-komplett, medan LTL är coNEXP-komplett (coNP-komplett för fasta formler). Däremot bevisar vi att EF-logik över PCo är obeslutbart. Våra NP övre gränser är genom en direkt poly-tid minskning till tillfredsställelse över existentiella Presburger formler, så att vi kan koppla in i högt optimerade lösare som Z3. Även om omvänd-bunden analys är ofullständig för PDS med obundna räknare i allmänhet, våra experiment tyder på att vissa invecklade buggar (t.ex. från Linux enhetsdrivrutiner) kan upptäckas med ett litet antal reverseringar. Vi preciserar också decidability/komplexitet av olika förlängningar av PCo, t.ex., med diskreta klockor.
I det senaste arbetet REF visade vi att åtkomlighetsanalysen för pushdown automata med reverserade räknare är NP-komplett.
Model checking recursive programs with numeric data types
{'venue': 'In Proc. of CAV, volume 6806 of LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}