On learning assumptions for compositional verification of probabilistic systems
<p>Probabilistic model checking is a powerful formal verification method that can ensure the correctness of real-life systems that exhibit stochastic behaviour. The work presented in this thesis aims to solve the <em>scalability</em> challenge of probabilistic model checking, by de...
| מחבר ראשי: | |
|---|---|
| מחברים אחרים: | |
| פורמט: | Thesis |
| שפה: | English |
| יצא לאור: |
2014
|
| נושאים: |
| _version_ | 1826315680443531264 |
|---|---|
| author | Feng, L |
| author2 | Kwiatkowska, M |
| author_facet | Kwiatkowska, M Feng, L |
| author_sort | Feng, L |
| collection | OXFORD |
| description | <p>Probabilistic model checking is a powerful formal verification method that can ensure the correctness of real-life systems that exhibit stochastic behaviour. The work presented in this thesis aims to solve the <em>scalability</em> challenge of probabilistic model checking, by developing, for the first time, fully-automated compositional verification techniques for probabilistic systems. The contributions are novel approaches for automatically learning probabilistic assumptions for three different compositional verification frameworks.</p> <p>The first framework considers systems that are modelled as Segala probabilistic automata, with assumptions captured by probabilistic safety properties. A fully-automated approach is developed to learn assumptions for various assume-guarantee rules, including an asymmetric rule Asym for two-component systems, an asymmetric rule Asym-N for n-component systems, and a circular rule Circ. This approach uses the L* and NL* algorithms for automata learning.</p> <p>The second framework considers systems where the components are modelled as probabilistic I/O systems (PIOSs), with assumptions represented by Rabin probabilistic automata (RPAs). A new (complete) assume-guarantee rule Asym-Pios is proposed for this framework. In order to develop a fully-automated approach for learning assumptions and performing compositional verification based on the rule Asym-Pios, a (semi-)algorithm to check language inclusion of RPAs and an L*-style learning method for RPAs are also proposed.</p> <p>The third framework considers the compositional verification of discrete-time Markov chains (DTMCs) encoded in Boolean formulae, with assumptions represented as Interval DTMCs (IDTMCs). A new parallel operator for composing an IDTMC and a DTMC is defined, and a new (complete) assume-guarantee rule Asym-Idtmc that uses this operator is proposed. A fully-automated approach is formulated to learn assumptions for rule Asym-Idtmc, using the CDNF learning algorithm and a new symbolic reachability analysis algorithm for IDTMCs.</p> <p>All approaches proposed in this thesis have been implemented as prototype tools and applied to a range of benchmark case studies. Experimental results show that these approaches are helpful for automating the compositional verification of probabilistic systems through learning small assumptions, but may suffer from high computational complexity or even undecidability. The techniques developed in this thesis can assist in developing scalable verification frameworks for probabilistic models.</p> |
| first_indexed | 2024-03-06T18:57:23Z |
| format | Thesis |
| id | oxford-uuid:12502ba2-478f-429a-a250-6590c43a8e8a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:30:31Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | oxford-uuid:12502ba2-478f-429a-a250-6590c43a8e8a2024-12-01T13:52:05ZOn learning assumptions for compositional verification of probabilistic systemsThesishttp://purl.org/coar/resource_type/c_db06uuid:12502ba2-478f-429a-a250-6590c43a8e8aTheory and automated verificationScalable systemsSoftware engineeringComputer science (mathematics)Applications and algorithmsEnglishOxford University Research Archive - Valet2014Feng, LKwiatkowska, M<p>Probabilistic model checking is a powerful formal verification method that can ensure the correctness of real-life systems that exhibit stochastic behaviour. The work presented in this thesis aims to solve the <em>scalability</em> challenge of probabilistic model checking, by developing, for the first time, fully-automated compositional verification techniques for probabilistic systems. The contributions are novel approaches for automatically learning probabilistic assumptions for three different compositional verification frameworks.</p> <p>The first framework considers systems that are modelled as Segala probabilistic automata, with assumptions captured by probabilistic safety properties. A fully-automated approach is developed to learn assumptions for various assume-guarantee rules, including an asymmetric rule Asym for two-component systems, an asymmetric rule Asym-N for n-component systems, and a circular rule Circ. This approach uses the L* and NL* algorithms for automata learning.</p> <p>The second framework considers systems where the components are modelled as probabilistic I/O systems (PIOSs), with assumptions represented by Rabin probabilistic automata (RPAs). A new (complete) assume-guarantee rule Asym-Pios is proposed for this framework. In order to develop a fully-automated approach for learning assumptions and performing compositional verification based on the rule Asym-Pios, a (semi-)algorithm to check language inclusion of RPAs and an L*-style learning method for RPAs are also proposed.</p> <p>The third framework considers the compositional verification of discrete-time Markov chains (DTMCs) encoded in Boolean formulae, with assumptions represented as Interval DTMCs (IDTMCs). A new parallel operator for composing an IDTMC and a DTMC is defined, and a new (complete) assume-guarantee rule Asym-Idtmc that uses this operator is proposed. A fully-automated approach is formulated to learn assumptions for rule Asym-Idtmc, using the CDNF learning algorithm and a new symbolic reachability analysis algorithm for IDTMCs.</p> <p>All approaches proposed in this thesis have been implemented as prototype tools and applied to a range of benchmark case studies. Experimental results show that these approaches are helpful for automating the compositional verification of probabilistic systems through learning small assumptions, but may suffer from high computational complexity or even undecidability. The techniques developed in this thesis can assist in developing scalable verification frameworks for probabilistic models.</p> |
| spellingShingle | Theory and automated verification Scalable systems Software engineering Computer science (mathematics) Applications and algorithms Feng, L On learning assumptions for compositional verification of probabilistic systems |
| title | On learning assumptions for compositional verification of probabilistic systems |
| title_full | On learning assumptions for compositional verification of probabilistic systems |
| title_fullStr | On learning assumptions for compositional verification of probabilistic systems |
| title_full_unstemmed | On learning assumptions for compositional verification of probabilistic systems |
| title_short | On learning assumptions for compositional verification of probabilistic systems |
| title_sort | on learning assumptions for compositional verification of probabilistic systems |
| topic | Theory and automated verification Scalable systems Software engineering Computer science (mathematics) Applications and algorithms |
| work_keys_str_mv | AT fengl onlearningassumptionsforcompositionalverificationofprobabilisticsystems |