Change search
Link to record
Permanent link

Direct link
BETA
Rezine, Othmane
Publications (8 of 8) Show all publications
Abdulla, P. A., Delzanno, G., Rezine, O., Sangnier, A. & Traverso, R. (2016). Parameterized verification of time-sensitive models of ad hoc network protocols. Theoretical Computer Science, 612, 1-22
Open this publication in new window or tab >>Parameterized verification of time-sensitive models of ad hoc network protocols
Show others...
2016 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 612, p. 1-22Article in journal (Refereed) Published
Abstract [en]

We study decidability and undecidability results for parameterized verification of a formal model of timed Ad Hoc network protocols. The communication topology is defined by an undirected graph and the behaviour of each node is defined by a timed automaton communicating with its neighbours via broadcast messages. We consider parameterized verification problems formulated in terms of reachability. In particular we are interested in searching for an initial configuration from which an individual node can reach an error state. We study the problem for dense and discrete time and compare the results with those obtained for (fully connected) networks of timed automata.

Keywords
Parameterized verification, Timed automata, Ad hoc networks, Graphs, Decidability, Well structured transition systems
National Category
Computer Engineering
Identifiers
urn:nbn:se:uu:diva-279630 (URN)10.1016/j.tcs.2015.07.048 (DOI)000369211200001 ()
Available from: 2016-03-08 Created: 2016-03-02 Last updated: 2018-01-10Bibliographically approved
Abdulla, P. A., Atig, M. F., Cederberg, J., Modi, S., Rezine, O. & Saini, G. (2015). MPass: An efficient tool for the analysis of message-passing programs. In: Formal Aspects of Component Software: . Paper presented at FACS 2014, September 10–12, Bertinoro, Italy (pp. 198-206). Springer
Open this publication in new window or tab >>MPass: An efficient tool for the analysis of message-passing programs
Show others...
2015 (English)In: Formal Aspects of Component Software, Springer, 2015, p. 198-206Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2015
Series
Lecture Notes in Computer Science ; 8997
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-237847 (URN)10.1007/978-3-319-15317-9_13 (DOI)978-3-319-15316-2 (ISBN)
Conference
FACS 2014, September 10–12, Bertinoro, Italy
Projects
ProFuNUPMARC
Available from: 2015-01-30 Created: 2014-12-05 Last updated: 2018-01-11Bibliographically approved
Abdulla, P. A., Atig, M. F., Kara, A. & Rezine, O. (2015). Verification of buffered dynamic register automata. In: Networked Systems: NETYS 2015. Paper presented at NETYS 2015, May 13–15, Agadir, Morocco (pp. 15-31). Springer
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
Abdulla, P. A., Atig, M. F., Rezine, O. & Stenman, J. (2014). Budget-bounded model-checking pushdown systems. Formal methods in system design, 45(2), 273-301
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
Abdulla, P. A., Atig, M. F., Kara, A. & Rezine, O. (2014). Verification of Dynamic Register Automata. In: Leibniz International Proceedings in Informatics: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014). Paper presented at IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India, December 15–17 2014..
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. 

Keywords
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
Abdulla, P. A., Atig, M. F. & Rezine, O. (2013). Verification of Directed Acyclic Ad Hoc Networks. In: Formal Techniques for Distributed Systems: FORTE 2013. Paper presented at Formal Techniques for Distributed Systems (FORTE 2013), June 3-5, 2013, Florence, Italy (pp. 193-208). Springer Berlin/Heidelberg
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
Abdulla, P. A., Atig, M. F., Stenman, J. & Rezine, O. (2012). Multi-Pushdown Systems with Budgets. In: Formal Methods in Computer-Aided Design. Paper presented at FMCAD 2012 (pp. 24-33).
Open this publication in new window or tab >>Multi-Pushdown Systems with Budgets
2012 (English)In: Formal Methods in Computer-Aided Design, 2012, p. 24-33Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-189987 (URN)
Conference
FMCAD 2012
Projects
UPMARCConcurrent recursive programsProFun
Available from: 2013-01-06 Created: 2013-01-06 Last updated: 2018-01-11
Abdulla, P. A., Delzanno, G., Rezine, O., Sangnier, A. & Traverso, R. (2011). On the verification of timed ad hoc networks. In: Formal Modeling and Analysis of Timed Systems: FORMATS 2011 (pp. 256-270). Springer Berlin/Heidelberg
Open this publication in new window or tab >>On the verification of timed ad hoc networks
Show others...
2011 (English)In: Formal Modeling and Analysis of Timed Systems: FORMATS 2011, Springer Berlin/Heidelberg, 2011, p. 256-270Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2011
Series
Lecture Notes in Computer Science ; 6919
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-165565 (URN)10.1007/978-3-642-24310-3_18 (DOI)978-3-642-24309-7 (ISBN)
Projects
ProFun
Available from: 2012-01-09 Created: 2012-01-09 Last updated: 2018-01-12Bibliographically approved
Organisations

Search in DiVA

Show all publications