Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Verification of networks of communicating processes: Reachability problems and decidability issues
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Algorithmic Program Verification)
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Computer systems are used in almost all aspects of our lives and our dependency on them keeps on increasing. When computer systems are used to handle critical tasks, any software failure can cause severe human and/or material losses. Therefore, for such applications, it is important to detect software errors at an early stage of software development. Furthermore, the growing use of concurrent and distributed programs exponentially increases the complexity of computer systems, making the problem of detecting software errors even harder (if not impossible). This calls for defining systematic and efficient techniques to evaluate the safety and the correctness of programs. The aim of Model-Checking is to analyze automatically whether a given program satisfies its specification. Early applications of Model-Checking were restricted to systems whose behaviors can be captured by finite graphs, so called finite-state systems. Since many computer systems cannot be modeled as finite-state machines, there has been a growing interest in extending the applicability of Model-Checking to infinite-state systems.

The goal of this thesis is to extend the applicability of Model Checking for three instances of infinite-state systems: Ad-Hoc Networks, Dynamic Register Automata and Multi Pushdown Systems. Each one of these instances models challenging types of networks of communicating processes. In both Ad-Hoc Networks and Dynamic Register Automata, communication is carried through message passing. In each type of network, a graph topology models the communication links between processes in the network. The graph topology is static in the case of Ad-Hoc Networks while it is dynamic in the case of Dynamic Register Automata. The number of processes in both types of networks is unbounded. Finally, we consider Multi Pushdown Systems, a model used to study the behaviors of concurrent programs composed of sequential recursive sequential programs communicating through a shared memory.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2017. , p. 148
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1605
Keyword [en]
program verification, model checking, infinite-state systems, distributed programs, concurrent programs, networks of communicating processes, reachability, termination, decidability
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-334788ISBN: 978-91-513-0169-3 (print)OAI: oai:DiVA.org:uu-334788DiVA, id: diva2:1160675
Public defence
2018-01-12, ITC/2446, Polacksbacken, Lägerhyddsvägen 2,, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2017-12-21 Created: 2017-11-27 Last updated: 2018-03-08
List of papers
1. Budget-bounded model-checking pushdown systems
Open this publication in new window or tab >>Budget-bounded model-checking pushdown systems
2014 (English)In: Formal methods in system design, ISSN 0925-9856, E-ISSN 1572-8102, Vol. 45, no 2, p. 273-301Article in journal (Refereed) Published
Abstract [en]

We address the verification problem for concurrent programs modeled as multi-pushdown systems (MPDS). In general, MPDS are Turing powerful and hence come along with undecidability of all basic decision problems. Because of this, several subclasses of MPDS have been proposed and studied in the literature (Atig et al. in LNCS, Springer, Berlin, 2005; La Torre et al. in LICS, IEEE, 2007; Lange and Lei in Inf Didact 8, 2009; Qadeer and Rehof in TACAS, LNCS, Springer, Berlin, 2005). In this paper, we propose the class of bounded-budget MPDS, which are restricted in the sense that each stack can perform an unbounded number of context switches only if its depth is below a given bound, and a bounded number of context switches otherwise. We show that the reachability problem for this subclass is Pspace-complete and that LTL-model-checking is Exptime-complete. Furthermore, we propose a code-to-code translation that inputs a concurrent program and produces a sequential program such that running under the budget-bounded restriction yields the same set of reachable states as running . Moreover, detecting (fair) non-terminating executions in can be reduced to LTL-Model-Checking of . By leveraging standard sequential analysis tools, we have implemented a prototype tool and applied it on a set of benchmarks, showing the feasibility of our translation.

National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-234422 (URN)10.1007/s10703-014-0207-y (DOI)000343210700007 ()
Projects
UPMARCConcurrent recursive programs
Funder
Swedish Research Council
Available from: 2014-04-25 Created: 2014-10-17 Last updated: 2018-01-11
2. Verification of Directed Acyclic Ad Hoc Networks
Open this publication in new window or tab >>Verification of Directed Acyclic Ad Hoc Networks
2013 (English)In: Formal Techniques for Distributed Systems: FORTE 2013, Springer Berlin/Heidelberg, 2013, p. 193-208Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7892
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-211409 (URN)10.1007/978-3-642-38592-6_14 (DOI)978-3-642-38591-9 (ISBN)
Conference
Formal Techniques for Distributed Systems (FORTE 2013), June 3-5, 2013, Florence, Italy
Projects
ProFuN
Funder
Swedish Foundation for Strategic Research
Available from: 2013-11-27 Created: 2013-11-22 Last updated: 2017-11-27Bibliographically approved
3. Verification of Dynamic Register Automata
Open this publication in new window or tab >>Verification of Dynamic Register Automata
2014 (English)In: Leibniz International Proceedings in Informatics: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014), 2014Conference paper, Published paper (Refereed)
Abstract [en]

We consider the verification problem for Dynamic Register Automata (Dra). Dra extend classical register automata by process creation. In this setting, each process is equipped with a finite number of registers in which the process IDs of other processes can be stored. A process can communicate with processes whose IDs are stored in its registers and can send them the content of its registers. The state reachability problem asks whether a Dra reaches a configuration where at least one process is in an error state. We first show that this problem is in general undecidable. This result holds even when we restrict the analysis to configurations where the maximal length of the simple paths in their underlying (un)directed communication graphs are bounded by some constant. Then we introduce the model of degenerative Dra which allows non-deterministic reset of the registers. We prove that for every given Dra, its corresponding degenerative one has the same set of reachable states. While the state reachability of a degenerative Dra remains undecidable, we show that the problem becomes decidable with nonprimitive-recursive complexity when we restrict the analysis to strongly bounded configurations, i.e. configurations whose underlying undirected graphs have bounded simple paths. Finally, we consider the class of strongly safe Dra, where all the reachable configurations are assumed to be strongly bounded. We show that for strongly safe Dra, the state reachability problem becomes decidable. 

Keyword
Register Automata, State Reachability, Formal Verification
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-237854 (URN)
Conference
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India, December 15–17 2014.
Projects
ProFuNUPMARC
Available from: 2014-12-05 Created: 2014-12-05 Last updated: 2018-01-11Bibliographically approved
4. Verification of buffered dynamic register automata
Open this publication in new window or tab >>Verification of buffered dynamic register automata
2015 (English)In: Networked Systems: NETYS 2015, Springer, 2015, p. 15-31Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2015
Series
Lecture Notes in Computer Science ; 9466
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-247828 (URN)10.1007/978-3-319-26850-7_2 (DOI)978-3-319-26849-1 (ISBN)
Conference
NETYS 2015, May 13–15, Agadir, Morocco
Projects
ProFuNUPMARC
Funder
Swedish Foundation for Strategic Research , RIT08-0065
Available from: 2016-03-23 Created: 2015-03-24 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

fulltext(1576 kB)122 downloads
File information
File name FULLTEXT01.pdfFile size 1576 kBChecksum SHA-512
f34ed7800b7327293171aebe19f051b6e4ee31286e2a4138bfc734951a56b652bea6480ab7b5abb1e966eac21419a08d497b5d3fa8cbdc1857c8b1c23f97d9ce
Type fulltextMimetype application/pdf
Buy this publication >>

Search in DiVA

By author/editor
Rezine, Othmane
By organisation
Division of Computer SystemsComputer Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 122 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 781 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf