|
Federico Cavaliere, Federico Mari, Igor Melatti, Giovanni Minei, Ivano Salvo, Enrico Tronci, Giovanni Verzino, and Yuri Yushtein. "Model Checking Satellite Operational Procedures." In DAta Systems In Aerospace (DASIA), Org. EuroSpace, Canadian Space Agency, CNES, ESA, EUMETSAT. San Anton, Malta, EuroSpace., 2011.
Abstract: We present a model checking approach for the automatic verification of satellite operational procedures (OPs). Building a model for a complex system as a satellite is a hard task. We overcome this obstruction by using a suitable simulator (SIMSAT) for the satellite. Our approach aims at improving OP quality assurance by automatic exhaustive exploration of all possible simulation scenarios. Moreover, our solution decreases OP verification costs by using a model checker (CMurphi) to automatically drive the simulator. We model OPs as user-executed programs observing the simulator telemetries and sending telecommands to the simulator. In order to assess feasibility of our approach we present experimental results on a simple meaningful scenario. Our results show that we can save up to 90% of verification time.
|
|
|
Vadim Alimguzhin, Federico Mari, Igor Melatti, Ivano Salvo, and Enrico Tronci. "On Model Based Synthesis of Embedded Control Software." In Proceedings of the 12th International Conference on Embedded Software, EMSOFT 2012, part of the Eighth Embedded Systems Week, ESWeek 2012, Tampere, Finland, October 7-12, 2012, edited by Ahmed Jerraya and Luca P. Carloni and Florence Maraninchi and John Regehr, 227–236. ACM, 2012. ISBN: 978-1-4503-1425-1. Notes: Techreport version can be found at arxiv.org. DOI: 10.1145/2380356.2380398.
|
|
|
Federico Mari, Igor Melatti, Ivano Salvo, and Enrico Tronci. "From Boolean Relations to Control Software." In Proceedings of ICSEA 2011, The Sixth International Conference on Software Engineering Advances, 528–533. ThinkMind, 2011. ISSN: 978-1-61208-165-6. Notes: Best Paper Award.
Abstract: Many software as well digital hardware automatic synthesis methods define the set of implementations meeting the given system specifications with a boolean relation K. In such a context a fundamental step in the software (hardware) synthesis process is finding effective solutions to the functional equation defined by K. This entails finding a (set of) boolean function(s) F (typically represented using OBDDs, Ordered Binary Decision Diagrams) such that: 1) for all x for which K is satisfiable, K(x, F(x)) = 1 holds; 2) the implementation of F is efficient with respect to given implementation parameters such as code size or execution time. While this problem has been widely studied in digital hardware synthesis, little has been done in a software synthesis context. Unfortunately the approaches developed for hardware synthesis cannot be directly used in a software context. This motivates investigation of effective methods to solve the above problem when F has to be implemented with software. In this paper we present an algorithm that, from an OBDD representation for K, generates a C code implementation for F that has the same size as the OBDD for F and a WCET (Worst Case Execution Time) linear in nr, being n = |x| the number of input arguments for functions in F and r the number of functions in F.
|
|
|
Federico Mari, Igor Melatti, Ivano Salvo, and Enrico Tronci. "Linear Constraints as a Modeling Language for Discrete Time Hybrid Systems." In Proceedings of ICSEA 2012, The Seventh International Conference on Software Engineering Advances, 664–671. ThinkMind, 2012.
|
|
|
Federico Mari, Igor Melatti, Ivano Salvo, and Enrico Tronci. "Control Software Visualization." In Proceedings of INFOCOMP 2012, The Second International Conference on Advanced Communications and Computation, 15–20. ThinkMind, 2012. ISSN: 978-1-61208-226-4.
|
|
|
Benedetto Intrigila, Ivano Salvo, and Stefano Sorgi. "A characterization of weakly Church-Rosser abstract reduction systems that are not Church-Rosser." Information and Computation 171, no. 2 (2001): 137–155. Academic Press, Inc.. ISSN: 0890-5401. DOI: 10.1006/inco.2001.2945.
Abstract: Basic properties of rewriting systems can be stated in the framework of abstract reduction systems (ARS). Properties like confluence (or Church-Rosser, CR) and weak confluence (or weak Church-Rosser, WCR) and their relationships can be studied in this setting: as a matter of fact, well-known counterexamples to the implication WCR CR have been formulated as ARS. In this paper, starting from the observation that such counterexamples are structurally similar, we set out a graph-theoretic characterization of WCR ARS that is not CR in terms of a suitable class of reduction graphs, such that in every WCR not CR ARS, we can embed at least one element of this class. Moreover, we give a tighter characterization for a restricted class of ARS enjoying a suitable regularity condition. Finally, as a consequence of our approach, we prove some interesting results about ARS using the mathematical tools developed. In particular, we prove an extension of the Newman’s lemma and we find out conditions that, once assumed together with WCR property, ensure the unique normal form property. The Appendix treats two interesting examples, both generated by graph-rewriting rules, with specific combinatorial properties.
|
|
|
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, Enrico Tronci, Lorenzo Alvisi, Allen Clement, and Harry Li. "Model Checking Nash Equilibria in MAD Distributed Systems." In FMCAD '08: Proceedings of the 2008 International Conference on Formal Methods in Computer-Aided Design, edited by A. Cimatti and R. Jones, 1–8. Piscataway, NJ, USA: IEEE Press, 2008. ISSN: 978-1-4244-2735-2. DOI: 10.1109/FMCAD.2008.ECP.16.
Abstract: We present a symbolic model checking algorithm for verification of Nash equilibria in finite state mechanisms modeling Multiple Administrative Domains (MAD) distributed systems. Given a finite state mechanism, a proposed protocol for each agent and an indifference threshold for rewards, our model checker returns PASS if the proposed protocol is a Nash equilibrium (up to the given indifference threshold) for the given mechanism, FAIL otherwise. We implemented our model checking algorithm inside the NuSMV model checker and present experimental results showing its effectiveness for moderate size mechanisms. For example, we can handle mechanisms which corresponding normal form games would have more than $10^20$ entries. To the best of our knowledge, no model checking algorithm for verification of mechanism Nash equilibria has been previously published.
Keywords: Model Checking, MAD Distributed System, Nash Equilibrium
|
|
|
V. Alimguzhin, F. Mari, I. Melatti, I. Salvo, and E. Tronci. "Linearising Discrete Time Hybrid Systems." IEEE Transactions on Automatic Control 62, no. 10 (2017): 5357–5364. ISSN: 0018-9286. DOI: 10.1109/TAC.2017.2694559.
Abstract: Model Based Design approaches for embedded systems aim at generating correct-by-construction control software, guaranteeing that the closed loop system (controller and plant) meets given system level formal specifications. This technical note addresses control synthesis for safety and reachability properties of possibly non-linear discrete time hybrid systems. By means of syntactical transformations that require non-linear terms to be Lipschitz continuous functions, we over-approximate non-linear dynamics with a linear system whose controllers are guaranteed to be controllers of the original system. We evaluate performance of our approach on meaningful control synthesis benchmarks, also comparing it to a state-of-the-art tool.
|
|
|
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.
|
|