|
|
Toni Mancini, Federico Mari, Annalisa Massini, Igor Melatti, Fabio Merli, and Enrico Tronci. "System Level Formal Verification via Model Checking Driven Simulation." In Proceedings of the 25th International Conference on Computer Aided Verification. July 13-19, 2013, Saint Petersburg, Russia, 296–312. Lecture Notes in Computer Science 8044. Springer - Verlag, 2013. ISSN: 0302-9743. ISBN: 978-3-642-39798-1. DOI: 10.1007/978-3-642-39799-8_21.
|
|
|
|
Vadim Alimguzhin, Federico Mari, Igor Melatti, Ivano Salvo, and Enrico Tronci. "On-the-Fly Control Software Synthesis." In Proceedings of International SPIN Symposium on Model Checking of Software (SPIN 2013), 61–80. Lecture Notes in Computer Science 7976. Springer - Verlag, 2013. ISSN: 0302-9743. ISBN: 978-3-642-39175-0. DOI: 10.1007/978-3-642-39176-7_5.
|
|
|
|
Vadim Alimguzhin, Federico Mari, Igor Melatti, Ivano Salvo, and Enrico Tronci. "A Map-Reduce Parallel Approach to Automatic Synthesis of Control Software." In Proc. of International SPIN Symposium on Model Checking of Software (SPIN 2013), 43–60. Lecture Notes in Computer Science 7976. Springer - Verlag, 2013. ISSN: 0302-9743. ISBN: 978-3-642-39175-0. DOI: 10.1007/978-3-642-39176-7_4.
|
|
|
|
Federico Mari, Igor Melatti, Ivano Salvo, and Enrico Tronci. "Undecidability of Quantized State Feedback Control for Discrete Time Linear Hybrid Systems." In Theoretical Aspects of Computing – ICTAC 2012, edited by A. Roychoudhury and M. D'Souza, 243–258. Lecture Notes in Computer Science 7521. Springer Berlin Heidelberg, 2012. ISBN: 978-3-642-32942-5. DOI: 10.1007/978-3-642-32943-2_19.
|
|
|
|
Federico Mari, Igor Melatti, Ivano Salvo, and Enrico Tronci. "Synthesis of Quantized Feedback Control Software for Discrete Time Linear Hybrid Systems." In Computer Aided Verification, edited by T. Touili, B. Cook and P. Jackson, 180–195. Lecture Notes in Computer Science 6174. Springer Berlin / Heidelberg, 2010. DOI: 10.1007/978-3-642-14295-6_20.
Abstract: We present an algorithm that given a Discrete Time Linear Hybrid System returns a correct-by-construction software implementation K for a (near time optimal) robust quantized feedback controller for along with the set of states on which K is guaranteed to work correctly (controllable region). Furthermore, K has a Worst Case Execution Time linear in the number of bits of the quantization schema.
|
|
|
|
Federico Mari, Igor Melatti, Ivano Salvo, Enrico Tronci, Lorenzo Alvisi, Allen Clement, and Harry Li. "Model Checking Coalition Nash Equilibria in MAD Distributed Systems." In Stabilization, Safety, and Security of Distributed Systems, 11th International Symposium, SSS 2009, Lyon, France, November 3-6, 2009. Proceedings, edited by R. Guerraoui and F. Petit, 531–546. Lecture Notes in Computer Science 5873. Springer, 2009. DOI: 10.1007/978-3-642-05118-0_37.
Abstract: We present two OBDD based model checking algorithms for the verification of Nash equilibria in finite state mechanisms modeling Multiple Administrative Domains (MAD) distributed systems with possibly colluding agents (coalitions) and with possibly faulty or malicious nodes (Byzantine agents). Given a finite state mechanism, a proposed protocol for each agent and the maximum sizes f for Byzantine agents and q for agents collusions, our model checkers return Pass if the proposed protocol is an ε-f-q-Nash equilibrium, i.e. no coalition of size up to q may have an interest greater than ε in deviating from the proposed protocol when up to f Byzantine agents are present, Fail otherwise. We implemented our model checking algorithms within the NuSMV model checker: the first one explicitly checks equilibria for each coalition, while the second represents symbolically all coalitions. We present experimental results showing their effectiveness for moderate size mechanisms. For example, we can verify coalition Nash equilibria for mechanisms which corresponding normal form games would have more than $5 \times 10^21$ entries. Moreover, we compare the two approaches, and the explicit algorithm turns out to outperform the symbolic one. To the best of our knowledge, no model checking algorithm for verification of Nash equilibria of mechanisms with coalitions has been previously published.
|
|
|
|
Federico Mari, and Enrico Tronci. "CEGAR Based Bounded Model Checking of Discrete Time Hybrid Systems." In Hybrid Systems: Computation and Control (HSCC 2007), edited by A. Bemporad, A. Bicchi and G. C. Buttazzo, 399–412. Lecture Notes in Computer Science 4416. Springer, 2007. DOI: 10.1007/978-3-540-71493-4_32.
Abstract: Many hybrid systems can be conveniently modeled as Piecewise Affine Discrete Time Hybrid Systems PA-DTHS. As well known Bounded Model Checking (BMC) for such systems comes down to solve a Mixed Integer Linear Programming (MILP) feasibility problem. We present a SAT based BMC algorithm for automatic verification of PA-DTHSs. Using Counterexample Guided Abstraction Refinement (CEGAR) our algorithm gradually transforms a PA-DTHS verification problem into larger and larger SAT problems. Our experimental results show that our approach can handle PA-DTHSs that are more then 50 times larger than those that can be handled using a MILP solver.
Keywords: Model Checking, Abstraction, CEGAR, SAT, Hybrid Systems, DTHS
|
|
|
|
Giuseppe Della Penna, Benedetto Intrigila, Igor Melatti, Enrico Tronci, and Marisa Venturini Zilli. "Bounded Probabilistic Model Checking with the Mur$\varphi$ Verifier." In Formal Methods in Computer-Aided Design, 5th International Conference, FMCAD 2004, Austin, Texas, USA, November 15-17, 2004, Proceedings, edited by A. J. Hu and A. K. Martin, 214–229. Lecture Notes in Computer Science 3312. Springer, 2004. ISSN: 3-540-23738-0. DOI: 10.1007/978-3-540-30494-4_16.
Abstract: In this paper we present an explicit verification algorithm for Probabilistic Systems defining discrete time/finite state Markov Chains. We restrict ourselves to verification of Bounded PCTL formulas (BPCTL), that is, PCTL formulas in which all Until operators are bounded, possibly with different bounds. This means that we consider only paths (system runs) of bounded length. Given a Markov Chain $\cal M$ and a BPCTL formula Φ, our algorithm checks if Φ is satisfied in $\cal M$. This allows to verify important properties, such as reliability in Discrete Time Hybrid Systems. We present an implementation of our algorithm within a suitable extension of the Mur$\varphi$ verifier. We call FHP-Mur$\varphi$ (Finite Horizon Probabilistic Mur$\varphi$) such extension of the Mur$\varphi$ verifier. We give experimental results comparing FHP-Mur$\varphi$ with (a finite horizon subset of) PRISM, a state-of-the-art symbolic model checker for Markov Chains. Our experimental results show that FHP-Mur$\varphi$ can effectively handle verification of BPCTL formulas for systems that are out of reach for PRISM, namely those involving arithmetic operations on the state variables (e.g. hybrid systems).
|
|
|
|
Giuseppe Della Penna, Benedetto Intrigila, Igor Melatti, Enrico Tronci, and Marisa Venturini Zilli. "Integrating RAM and Disk Based Verification within the Mur$\varphi$ Verifier." In Correct Hardware Design and Verification Methods, 12th IFIP WG 10.5 Advanced Research Working Conference, CHARME 2003, L'Aquila, Italy, October 21-24, 2003, Proceedings, edited by D. Geist and E. Tronci, 277–282. Lecture Notes in Computer Science 2860. Springer, 2003. ISSN: 3-540-20363-X. DOI: 10.1007/978-3-540-39724-3_25.
Abstract: We present a verification algorithm that can automatically switch from RAM based verification to disk based verification without discarding the work done during the RAM based verification phase. This avoids having to choose beforehand the proper verification algorithm. Our experimental results show that typically our integrated algorithm is as fast as (sometime faster than) the fastest of the two base (i.e. RAM based and disk based) verification algorithms.
|
|
|
|
Giuseppe Della Penna, Benedetto Intrigila, Igor Melatti, Enrico Tronci, and Marisa Venturini Zilli. "Finite Horizon Analysis of Markov Chains with the Mur$\varphi$ Verifier." In Correct Hardware Design and Verification Methods, 12th IFIP WG 10.5 Advanced Research Working Conference, CHARME 2003, L'Aquila, Italy, October 21-24, 2003, Proceedings, edited by D. Geist and E. Tronci, 394–409. Lecture Notes in Computer Science 2860. Springer, 2003. ISSN: 3-540-20363-X. DOI: 10.1007/978-3-540-39724-3_34.
Abstract: In this paper we present an explicit disk based verification algorithm for Probabilistic Systems defining discrete time/finite state Markov Chains. Given a Markov Chain and an integer k (horizon), our algorithm checks whether the probability of reaching an error state in at most k steps is below a given threshold. We present an implementation of our algorithm within a suitable extension of the Mur$\varphi$ verifier. We call the resulting probabilistic model checker FHP-Mur$\varphi$ (Finite Horizon Probabilistic Mur$\varphi$). We present experimental results comparing FHP-Mur$\varphi$ with (a finite horizon subset of) PRISM, a state-of-the-art symbolic model checker for Markov Chains. Our experimental results show that FHP-Mur$\varphi$ can handle systems that are out of reach for PRISM, namely those involving arithmetic operations on the state variables (e.g. hybrid systems).
|
|
