Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Past-Free[ze] reachability analysis: reaching further with DAG-directed exhaustive state-space analysis

Ciprian Teodorov 1 Luka Le Roux 1 Zoé Drey 1 Philippe Dhaussy 1
1 Lab-STICC_ENSTAB_ CACS_MOCS
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Abstract : Model-checking enables the automated formal verification of software systems through the explicit enumeration of all the reachable states. While this technique has been successfully applied to industrial systems, it suffers from the state-space explosion problem because of the exponential growth in the number of states with respect to the number of interacting components. In this paper, we present a new reachability analysis algorithm, named Past-Free[ze], that reduces the state-space explosion problem by freeing parts of the state-space from memory. This algorithm relies on the explicit isolation of the acyclic parts of the system before analysis. The parallel composition of these parts drives the reachability analysis, the core of all model-checkers. During the execution, the past states of the system are freed from memory making room for more future states. To enable counter-example construction, the past states can be stored on external storage. To show the effectiveness of the approach, the algorithm was implemented in the OBP Observation Engine and was evaluated both on a synthetic benchmark and on realistic case studies from automotive and aerospace domains. The benchmark, composed of 50 test cases, shows that in average, 75% of the state-space can be dropped from memory thus enabling the exploration of up to 14 times more states than traditional approaches. Moreover, in some cases, the reachability analysis time can be reduced by up to 25%. In realistic settings, the use of Past-Free[ze] enabled the exploration of a state-space 4.5 times larger on the automotive case study, where almost 50% of the states are freed from memory. Moreover, this approach offers the possibility of analyzing an arbitrary number of interactions between the environment and the system-under-verification; for instance, in the case of the aerospace example, 1000 pilot/system interactions could be analyzed unraveling an 80 GB state-space using only 10 GB of memory
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-01373287
Contributeur : Annick Billon-Coat <>
Soumis le : mercredi 28 septembre 2016 - 14:44:07
Dernière modification le : mercredi 24 juin 2020 - 16:19:51

Lien texte intégral

Identifiants

Citation

Ciprian Teodorov, Luka Le Roux, Zoé Drey, Philippe Dhaussy. Past-Free[ze] reachability analysis: reaching further with DAG-directed exhaustive state-space analysis. Journal of Software Testing, Verification, and Reliability, John Wiley & Sons, 2016, ⟨10.1002/stvr.1611⟩. ⟨hal-01373287⟩

Partager

Métriques

Consultations de la notice

799