Formal verification of not fully symmetric systems using counter abstraction
Counter abstraction allows us to transform a concurrent system with an unbounded number of agents into a finite-state bounded abstraction, independent of the number of processes present in the implementation. In its general form it is not well suited for verification of parameterised concurrent syst...
| Main Author: | |
|---|---|
| Format: | Conference item |
| Published: |
2008
|
| _version_ | 1797092098632056832 |
|---|---|
| author | Mazur, T |
| author_facet | Mazur, T |
| author_sort | Mazur, T |
| collection | OXFORD |
| description | Counter abstraction allows us to transform a concurrent system with an unbounded number of agents into a finite-state bounded abstraction, independent of the number of processes present in the implementation. In its general form it is not well suited for verification of parameterised concurrent systems based on message passing that are not fully symmetric and/or use two-way handshaken synchronisation between processes. In this paper we present a method whose main idea is to count processes that are in certain equivalence classes. We use labelled transitions systems to model processes (both implementation and specification) and traces refinement for verification checks. Refinement is checked automatically using the FDR model checker. We illustrate the method on a token ring mutual exclusion algorithm from [P. Wolper and V. Lovinfosse, 1990]. |
| first_indexed | 2024-03-07T03:41:30Z |
| format | Conference item |
| id | oxford-uuid:be0bf116-3c86-4529-a382-647132ff1917 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:41:30Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | oxford-uuid:be0bf116-3c86-4529-a382-647132ff19172022-03-27T05:36:22ZFormal verification of not fully symmetric systems using counter abstractionConference itemhttp://purl.org/coar/resource_type/c_5794uuid:be0bf116-3c86-4529-a382-647132ff1917Department of Computer Science2008Mazur, TCounter abstraction allows us to transform a concurrent system with an unbounded number of agents into a finite-state bounded abstraction, independent of the number of processes present in the implementation. In its general form it is not well suited for verification of parameterised concurrent systems based on message passing that are not fully symmetric and/or use two-way handshaken synchronisation between processes. In this paper we present a method whose main idea is to count processes that are in certain equivalence classes. We use labelled transitions systems to model processes (both implementation and specification) and traces refinement for verification checks. Refinement is checked automatically using the FDR model checker. We illustrate the method on a token ring mutual exclusion algorithm from [P. Wolper and V. Lovinfosse, 1990]. |
| spellingShingle | Mazur, T Formal verification of not fully symmetric systems using counter abstraction |
| title | Formal verification of not fully symmetric systems using counter abstraction |
| title_full | Formal verification of not fully symmetric systems using counter abstraction |
| title_fullStr | Formal verification of not fully symmetric systems using counter abstraction |
| title_full_unstemmed | Formal verification of not fully symmetric systems using counter abstraction |
| title_short | Formal verification of not fully symmetric systems using counter abstraction |
| title_sort | formal verification of not fully symmetric systems using counter abstraction |
| work_keys_str_mv | AT mazurt formalverificationofnotfullysymmetricsystemsusingcounterabstraction |