Invariant Synthesis for Verification of Parameterized Cyber-Physical Systems with Applications to Aerospace Systems

Johnson, Taylor T.; Mitra, Sayan

doi:10.2514/6.2013-4811

Abstract:

In this paper, we describe a method for synthesizing inductive invariants for cyber-physical aerospace systems that are parameterized on the number of participants, such as the number of aircraft involved in a coordinated maneuver. The methodology is useful for automating the traditionally manual process of deductive verification of safety properties, such as collision avoidance, and establishes such properties regardless of the number of participants involved in a protocol. We illustrate the methodology using a simplified model of the landing protocol of the Small Aircraft Transportation System (SATS) as a case study. Each participant (aircraft) in the protocol is modeled as a hybrid automaton with both discrete and continuous states and potentially nondeterministic evolution thereof. Discrete states change instantaneously according to transitions and continuous states evolve according to rectangular differential inclusions. The invariant synthesis method enables a fully automatic verification of the main safety property of SATS, namely, safe separation of aircraft on approach to the runway. The method is implemented in a prototype verification tool called Passel. We present promising experimental results using the methodology, which has enabled a fully automatic proof of safe separation for the model of SATS.

Reference:

Taylor T. Johnson, Sayan Mitra, "Invariant Synthesis for Verification of Parameterized Cyber-Physical Systems with Applications to Aerospace Systems", In Proceedings of the AIAA Infotech at Aerospace Conference (AIAA Infotech 2013) (, ed.), AIAA, vol. , Boston, MA, pp. , 2013, aug.

Bibtex Entry:

@inproceedings{johnson2013infotech,
        author          =       {Taylor T. Johnson and Sayan Mitra},
        title           =       {Invariant Synthesis for Verification of Parameterized Cyber-Physical Systems with Applications to Aerospace Systems},
        year            =       {2013},
        booktitle       =       {Proceedings of the AIAA Infotech at Aerospace Conference (<a href="http://www.aiaa.org/boston2013/">AIAA Infotech 2013</a>)},
    address     =   {Boston, MA},
        month           =       aug,
    isbn        =   {},
    volume      =   {}, 
    gsid        =   {},
    editor      =   {},
    doi     =   {10.2514/6.2013-4811},
    publisher   =   {AIAA},
    pages       =   {},
        abstract        =       {In this paper, we describe a method for synthesizing inductive invariants for cyber-physical aerospace systems that are parameterized on the number of participants, such as the number of aircraft involved in a coordinated maneuver. The methodology is useful for automating the traditionally manual process of deductive verification of safety properties, such as collision avoidance, and establishes such properties regardless of the number of participants involved in a protocol. We illustrate the methodology using a simplified model of the landing protocol of the Small Aircraft Transportation System (SATS) as a case study. Each participant (aircraft) in the protocol is modeled as a hybrid automaton with both discrete and continuous states and potentially nondeterministic evolution thereof. Discrete states change instantaneously according to transitions and continuous states evolve according to rectangular differential inclusions. The invariant synthesis method enables a fully automatic verification of the main safety property of SATS, namely, safe separation of aircraft on approach to the runway. The method is implemented in a prototype verification tool called Passel. We present promising experimental results using the methodology, which has enabled a fully automatic proof of safe separation for the model of SATS.},
        pdf = {http://www.taylortjohnson.com/research/johnson2013infotech.pdf},
}