{'fraction_non_alphanumeric': 0.02764928511354079, 'fraction_numerical': 0.0066582562377347915, 'mean_word_length': 5.006524942117449, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Verification Framework for Control System Functionality of Unmanned Aerial Vehicles

A control system verification framework is presented for unmanned aerial vehicles using theorem proving. The framework's aim is to set out a procedure for proving that the mathematically designed control system of the aircraft satisfies robustness requirements to ensure safe performance under varying environmental conditions. Extensive mathematical derivations, which have formerly been carried out manually, are checked for their correctness on a computer. To illustrate the proceedures, a higher-order logic interactive theorem-prover and an automated theorem-prover are utilized to formally verify a nonlinear attitude control system of a generic multi-rotor UAV over a stability domain within the dynamical state space of the drone. Further benefits of the proceedures are that some of the resulting methods can be implemented onboard the aircraft to detect when its controller breaches its flight envelop limits due to severe weather conditions or actuator/sensor malfunction. Such a detection procedure can be used to advise the remote pilot or an onboard intelligent agent to decide on some alterations of the planned flight path or to perform emergency landing.


Introduction
Control law design for aircraft normally combines control engineering knowledge with tests of stability and smoothness of control responses under disturbances. This often takes the form of an iterative process of remodelling aerodynamics in wind tunnels and ultimately in flight tests. Given a particular open loop dynamical model, control engineering relies on mathematical theory that is implemented in computations of flight controllers onboard. When the flight envelop is defined, it introduces numerical values which need to be carried through derivations and proofs of stability and acceptable handling within the flight envelop. In this paper manual derivations are replaced by theorem proving methods. The procedures presented go beyond algebraic computation and use higher-order logic, including handling of functionals, operators, concepts of convergence, stability and levels of smoothness measures.
The approach taken in this paper fits into one of the three stages of formally verifiable controller design as outlined in [1], where robust control theory verification is followed by verification of the software used for implementation. A third stage is to prove that the quantisation effects of the obtained digital controller do not significantly effect the results in stage one of the controller theory used. In implementations of aviation software, verification is often followed by redundancy-based safety analysis for critical sensors and actuators using voting principles, the affect of which lies outside the scope of this paper.
Realtime code-verification is systematically checking the correctness of the encoded controller such as in [2,3] and [4]. This paper focuses on verification of the control principles before it is implemented in realtime code. An interactive theorem prover (ITP) is used for performance verification under nominal environment conditions and onboard stability and performance monitoring is based on an automated theorem prover (ATP) for excessive conditions, including some sensor or actuator failures.
There have been prior initiatives on verification of safety-critical and cyber-physical systems. Such are the European Integrated Tool Chain for Model-based Design of Cyber-Physical Systems (INTO-CPS) [5], where a Functional Mockup Interface (FMI) has been developed for integrating the formal verification of Cyber-Physical Systems using the PVS [6] theorem prover with model-based software to co-simulation these systems. This approach integrates simulated models in model-based tools such as Modelica [7] , Simulink/Matlab [8] or 20-sim [9] with the FMI interface to verify the control system according to the required specifications using formal methods.
The FMI is also implemented in [10] using Isabelle/UTP [11], where Modelica is used to model the control system of a train then the model is encoded in Isabelle/UTP with FMI framework for co-simulation. Another project is the ERATO Metamathematics for Systems Design (MMSD) [12], where a framework is developed to use formal methods to verify automotive-related applications in industry such as cars. Other projects are conducted by the verification team of NASA Langley Research Center [13] such as [14,15] and [16]. Though these approaches use formal methods to verify control systems, the derivations of control laws are not covered by verification before implementing them. In addition, there is an absence of onboard real-time stability monitoring of these systems by formal methods.
There have been several studies conducted to formally verify control systems. In [17], a framework for reasoning about the transfer function and steady state errors in feedback control systems using HOL Light [18] theorem prover is proposed. Adnan, et al. [19] formalised the theory of Laplace transforms using interactive theorem prover to analyse linear control systems. In [20], formal verification of transformation matrices of a coordinate system is proposed for aircraft control systems using the Coq [21] theorem prover. An autonomous vehicle controller is formalised and proved in [22] using the PVS [6] theorem prover to illustrate its correctness in terms of stability of the Jacobian matrix and then co-simulated using the PVSio environment in PVS prover. Denman et at. [23] presented a method of implementing a formal Nichols plot analysis of a flight control system using the MetiTarski ATP [24] for stability verification. Araiza-Illan et al. [25] proposed a framework for automatic translating the system block diagrams modelled in Simulink into the Why3 [26] prover for verification. Verifying hybrid control systems using differential dynamic logic in KeYmaera [27] prover also proposed in [28,29] where abstraction of the closed-loop behaviour is constructed for a class of controllers.
Our proposed framework is different from this approach as we are verifying the correctness of the derived control law of aviation systems at the design stage before the simulation step using an ITP, followed by real-time monitoring of stability by ATP.
The novelty of this paper is to demonstrate that formal methods in some iterative theorem provers are suitable to verify and prove the correctness of robust control theory for a prescribed flight envelope of a multirotor aerial vehicle. Although prior work suggested this may be a possibility, this is a first evidence of this kind. This involves formal stability analysis to guarantee system's robustness then ensure aircraft's safety by conducting continuous onboard stability monitoring using interactive and automated theorem provers. The methods are implemented in Isabelle [30] and MetiTarski [24] , and the codes have been made available online.
The proposed verification framework is applied to a control scheme of a generic quad-copter presented in [31], which consists of a nonlinear attitude controller to deal with modelling uncertainty and external disturbances that is designed using the well-known dynamic inversion technique [32,33]. Lyapunov's method [34] has been used as part of the attitude controller design and to analyse the system to ensure its stability. We have applied our verification scheme to the attitude control system since all definitions, assumptions, derivations and performance proofs of the system are formalised then proved in the Isabelle higher-order logic (HOL) ITP. Lyapunov stability of the control system is formalised and proved in Isabelle/HOL. We have implemented the stability analysis into the MetiTarski ATP for onboard stability testing to check whether the aircraft is in its stable region or goes beyond it since in the latter case the autopilot system can inform the pilot/station to perform an urgent action.
The paper is structured as follow: section 2 describes theorem proving tools where Isabelle and MetiTarski provers are introduced; section 3 presents the proposed verification framework of unmanned aerial vehicles; section 4 demonstrates the applicability of the framework on a multirotor control system and describe the onboard stability monitoring; and section 5 presents the conclusions of this work.

Theorem Proving
Computer based theorem proving is a computational tool set in some logical system that can be used to prove the soundness and correctness of mathematical arguments. There are two main types of theorem proving: Automated Theorem Proving (ATP), which proves mathematical statements automatically without human interaction, and Interactive Theorem Proving (ITP), which automates steps of formal proofs by aid of a developer guiding the process of proof. The automated steps rely on mathematical logic and automated reasoning techniques. ITP will be used and described further in this paper for the verification framework proposed. ITPs are proof assistants, which formally define and prove mathematical theorems. Therefore, their user can implement a mathematical theory by defining assumptions and some valid logical statements, to start with. Then the ITP procedure will try to prove a sequence of statements, relying on available formal theories, and also by using existing logical methods and techniques or some external resources, such as ATP tools .
The distinction between ITP and ATP systems is not only that ATP systems fully automate proofs but that ATPs tend to have restricted expressivity where, unlike ITPs, they cannot prove higher order mathematical theories. Instead, they can be used to prove non complex mathematical formulas that contain inequalities over real numbers, quantified variables, and special functions. On the other hand, ITP systems have the ability to support formalising and proving mathematical theories, which involve higher order logic, with the aid of a human supervisor in an interactive way.
However, using ATPs can be utilised locally in an ITP to prove a step in the proof, by adding their packages to the ITP. This can also be done online by using System on TPTP [35], which is a web-based system including the most powerful ATPs that can be used to proof mathematical statements automatically. A good example of a useful ATP, from the control engineering side, is MetiTariski , which is a first-order logic (FOL) prover that was designed to work over the field of real numbers.
One of the well known tools in testing of the designed models and formally verifying and validating their correctness are model checkers [36]. These tools are used to model a system as a finite state transition, like automata or timed automata, and system properties are expressed in the form of proposition temporal logic. Then, the checking problem is reduced to a graph search and an exhaustive exploration of all possible states is accomplished using symbolic algorithms. However, model checkers are not applicable with infinite state space designs and they can not use to prove the derivation correctness of the designed control system. In contrast, ITPs can be employed to verify infinite state space systems and mathematical arguments.

Isabelle/HOL
Isabelle is an interactive theorem prover (proof assistant) based on automated reasoning techniques and logical calculus. It is written using the ML functional programming language such that the rules are presented as propositions not as functions and the proofs are structured by combining rules based on the λ-calculus. It provides the ability to express the mathematical formulae in a formal language and prove them using different logical tools. Isabelle/HOL is one of Isabelle's platforms, which is based on higher-order logics with quantifiers and semantics. Isabelle/HOL has a proof language called Isar which structures the proofs in a readable and understandable mathematics-like syntax for both users and computers. The mathematical formulas can be formalised and proven in the Isar language with the aid of Isabelle's logical tools. Examples of such tools are the simplifier, which performs operation and reasoning on equations, the classical reasoner that carry out long chains of reasoning procedures to prove statements or theories, automatic proof of linear arithmetic statements, algebraic decision procedures for decision making verification, advanced pattern matching, and sledgehammer for automatically finding the proofs based on already proven theorems in Isabelle's library and also calling external FOL provers (ATPs).
However, Isabelle has been chosen in this work for its rich logical and automation techniques since it has a large library, which contains most of the mathematical theories that are useful in control systems verification. Some examples of these theories are real, integer and complex numbers; Euclidean, vector, norm spaces; differentiation and integration; real and transcendental norms; higher-order functions on different of number types; logical techniques; algebra; etc. Isabelle also support other logical systems such as Hoare logics for systems verification [37] in addition to the ability to generate executable codes of the proved statements.
There is a wide range of syntax and command types in the Isabelle/HOL, therefore, the most common and useful one for our framework will be described. Isabelle/HOL expressions and symbols are described in Table 1.

MetiTarski
MetiTarski is a FOL automated theorem prover, which is designed as a combination of the resolution prover M etis [38] and a decision procedure tool QEP CAD [39] to conduct proofs over the field of real numbers. It can be utilised to prove universally quantified inequalities of transcendental and other functions, for instance ln, log, exp, etc. MetiTarski reduces the problems to be decidable by replacing the functions with upper and lower bounds on the real numbers field. It can perform proofs with the aid of three reasoners: QEPCAD, Z3 [40] and Mathematica. However, we have chosen MetiTarski to check the stability of unmanned aerial vehicle (UAV) systems due to its features of proving quantified inequalities including the above functions over large scale real numbers.

An Aircraft Verification Framework
The proposed verification framework is shown in Fig.1 which starts with formalising the aircraft's dynamical equations of motion, the coordinate system in the rigid body frame, the controller design, and stability analysis in mapping from value to value or function to function. −→ refers to "imply" in HOL. ⇒ used to define a function with its corresponding variables types (e.g., real ⇒ real) that is a function maps from real to real variable. =⇒ refers to "imply" in Isar language in Isabelle. (e.g., x = 0 =⇒ y = x) that is x=0 is an assumption and y=x is the statement to be proven. refers to "for universal all " which applies to all assumptions and/or proof statements. ∀ means "for all " or "for any" and it is for a specific assumption or statement. ∃ means "there exist" or "there is". ∃! means "there is only one". ∧ refers to the logical and . ∨ refers to the logical or . an operator for the dot product of two vectors. * v an operator for the multiplication of a matrix and a vector. * s an operator for the multiplication of a scalar value and a vector. * * an operator for the multiplication of two matrices.
this is equivalent to the function x(t) but under the constraint of an argument (t).

norm(x)
the Euclidean norm of a vector or a matrix. SU P (x) the supremum value of x.
the HOL syntax of the Isabelle prover. In addition, the stability analysis step is formalised in the FOL syntax of the MetiTarski ATP for possible verification of stability onboard the craft. The verification framework consists of two stages: the ITP represented by Isabelle/HOL to prove the mathematical derivation of the designed control system and its stability analysis, and the ATP represented by MetiTarski prover for continuously checking the validity of aircraft's stability onboard during the flight. The next section will illustrate these two verification stages in detail.

Verification in Isabelle/HOL Prover
In this subsection, we will demonstrate the first stage of the verification framework shown in Fig. 1 using an attitude controller of a generic quadcopter UAV proposed in [31] with considering the assumptions and flight conditions made. In this proposed controller, the quadcopter's rotational dynamics are controlled using a robust nonlinear controller that takes into account the modelling uncertainty and external disturbances. To ensure correctness of the designed attitude control where simulation cannot guarantee that the UAV's control system is robust for all possible flight conditions, the design's derivations and stability analysis have been verified using Isabelle/HOL prover. Isabelle/HOL is chosen for this purpose due to its rich library of mathematical theorems which are required to perform the UAV's control system verification.
The verification process using Isabelle/HOL is illustrated in Fig. 2 which mainly consist of two stages: formalising and proving procedures. The first stage starts by formalising the quadcopter UAV system into Isabelle/HOL syntax such as the coordinate system, rotational dynamics, time-domain functions, proposed assumptions and aircraft's stability analysis. The implementation of the control design and aircraft's dynamics includes a series of definition, lemma, and theorem items. Some assistant lemmas were needed to be formalised and proven, which did not exist in Isabelle due to that prover library is still under development as is the case with other theorem provers. The formalisation also needs to import some pre-proven mathematical theories and lemmas from the prover library, which are used in formalising and proving the control system equations with the proposed assumptions and definitions.
Much needed theories under HOL platform will be described here to illustrate the formalisation and proof procedures. First of all, the main multivariable analysis package which includes Analysis.thy for functions operations over real field, Finite Cartesian Product.thy and Inner Product.thy for definitions and operations of real vectors, L2 norm.thy and Norm Arth.thy for real vector norms and their operations, etc. The HOL.thy is the core of HOL platform which includes definitions of real numbers (real.thy), functions (fun.thy), sets (set.thy), etc., which are necessary in all the formalising procedures. The main multi-variable analysis theory, Analysis.thy, which includes definitions of real vectors (Finite Cartesian Product .thy), vector norms (L2 norm.thy, Norm Arth.thy) and their operations. These theories are used to define the aircraft's three-dimensional rotation vectors and their norms such as the torque, angular velocity and acceleration vectors where each component of a vector represented as a continuous time-domain function f (t); the continuous function defined in F un.thy, F unction Algebras.thy and T opological Spaces theories are utilised for this purpose. The time sub-domain is defined by a time set T = {t. t ∈ {0..∞}} and is followed by definitions of sets of vectors, which are working within T .
The matrices components are formalised using M atrix.thy and their operations using Analysis.thy, F inite Cartesian P roduct.thy and Real V ector Spaces.thy. The rate change of the quadcopter attitudes, i.e. velocities and accelerations, are formalised by time derivation using Deriv.thy and derivative.thy theories. The quadcopter controller design includes several ro-bust assumptions which need inequalities over the real-numbers field. Fortunately, such inequalities have been defined in Isabelle prover under Orderings .thy theory. This is an important feature for any robust control design to be proven. However, the second stage (proving procedures) is an interactive process between the designer/engineer and the automated proving tools that Isabelle prover has or supported. The role of designer/engineer is to help the prover to step-by-step prove the statement in case that the prover is not able to solve the proof automatically by simplifying the statement into several steps. Each step should be proven suing the provided automated tools before moving to the next one otherwise the prover will not pass the statement. Example of the automated tools supported in Isabelle are: CVC4, Z3, SPASS, E prover, Remote Vampire and SMT sovlers. In addition, Isabelle has its own automatic proving tools such as auto, simp, blast, etc. Most of the control system that we have verified required our interaction with the prover due to the design complexity for the prover to solve them automatically. The Isabelle code is long to be stated here, where only the important definitions and proofs are shown, while the complete code can be found in our online repository 1 .

HOL Platform
The control input u in Eq. 18 - [31], and the control law in Eq. 12 - [31], are defined in the prover as the following code, definition "cont law (τ :: The derivation in Eq. 19 - [31], is formalised and proved in Isabelle/HOL based on the att dyms, cont u and cont law (see the proof in the repository). The closed-loop error dynamic in Eqs. 22 and 23 of [31] where are implemented as lemma Eq 22 : assumes "∀t. t ∈ T "and"(set of def initions φ θ ψ φ d θ d ψ d η η d η η d η η d u γ e e e τ d d hat proof - have "e = η d − η " using assms ddot error vec def set of def initions def by metis thus ? thesis by (smt B mat def assms(2) exhaust 3 set of def initions def ) qed The set of def initions in the above code is a definition used to call all the pre-defined definitions in one step. We formalised the assumptions proposed in [31] as follow: Assumption 1 (Eq. 14 [31]), Assumption 2 (Eq. 15 [31]), Assumption 3 (Eqs. 24, 25 and 26 [31]), in Isabelle/HOL as follow: definition "assump1 (d :: definition "assump2 (N : Stability analysis of the attitude controller as stated in Eqs. 27-37 of [31] is implemented in Isabelle/HOL using a set of definitions, def inition, several lemmas, lemma, and short theorems in terms of theorem, theorem. This structure of using several lemmas and theorems during the proof is due to the fact that the reasoning system of the theorem prover cannot handle long proofs with many assumptions, i.e. the system unable to prove many equations if they are formalised in only one lemma or theorem style. However, the stability analysis starts by defining the candidate Lyapunov function V as in Eq. 27 of [31] which is formalised as a definition in Isabelle/HOL: Taking the candidate Lyapunov function V , the time derivative of Lyapunov function is derived and the derivations in Eqs. 28-30 in [31] are proven symbolically and detailed in the online repository above.
Finally, based on all the above definitions and assumptions, it has been verified that the proposed control system is asymptotically stable since the time derivative of Lyapunov function in Eq. 36 and 37 - [31], is strictly negative for ∀E = 0. It has also been proven that the tracking error converges to zero as the time converges to infinity, ( E −→ 0). The code below illustrates the symbolic proof in Isabelle theorem prover.

Onboard Verification for a Safe Flight using MetiTarski prover
The control system of the UAV can be designed, simulated and verified at the model/design stage. The designed controller then formalised to its corresponding code and implemented into the autopilot system, which controls the aircraft trajectory. The aircraft controlled by the autopilot can be exposed to gusts of wind which may cause unstable flight. In this case, the autopilot system cannot be informed if the aircraft has entered an unstable region which may cause a crash or lose of human(s) life. Therefore, we proposed using of ATP tool represented by MetiTarski prover for onboard verification that the prover can check the stability state of the aircraft and inform the autopilot in case of any unstable behaviour detected.
The autopilot then can send warning messages to the user/pilot or base station to perform, for instance, an emergency safe landing using autolanding techniques such as in [41]. This will ensure more safe flight and may avoid losing the aircraft or any harm to humans and properties. We have chosen MetiTarski ATP to verify the controller stability of the aircraft due to its ability of deal with inequalities with numerical real numbers. Unlike the previous verification stage using Isabelle, MetiTarski proves the statements automatically without the need to any interaction with designer/engineer.
MetiTarski can be implemented on the autopilot's electronic board such as PixHawk [42] or Navio2 [43] Raspberry Pi. These electronic autopilots use the Linux operating system where MetiTarski can also be installed. Therefore, an interface between the two systems (autopilot and MetiTarski) is easy to create in practice. The proposed onboard framework is illustrated in Fig.3. The applicability of this approach is illustrated in simulation by interfacing the Simulink/Matlab model with MetiTarski and test system stability. Note that the quadcopter that has been implemented in Simulink considers the nonlinear dynamics of the craft based on the MathWorks model in [44], which is widely used. Considering the stability analysis stated in Eqs. (15) and (16), the time derivative of the Lyapunov function will be tested to check whether it is negative definite or not. If it is not negative definite, then this indicates that the control system is out of its stability region, hence the autopilot can pass warning messages to the pilot or station to take an action or perform an emergency landing. The verification process starts by formalising the stability equations (15) and (16) into a FOL syntax. The parameters of these equations are passed from the autopilot system to MetiTarski prover via an interface scheme. Afterwards, the test is conducted in the MetiTarski prover such thatV (E) < 0. We have simulated the above procedures in Simulink/Matlab to illustrate its applicability. The stability equations, Eqs. (15) and (16), are simplified using symbolic computations in Matlab before formalising them into FOL syntax. The parameters included in both stability equations are passed from Simulink/Matlab to MetiTarski to perform the monitoring test. The following code shows an example of stability check in MetiTarski prover for Eq. (15) (note that the full code can be found in our online repository):

Conclusions
This paper has introduced a new verification framework for safety-critical control systems by applying the power of higher-order-logic-based interactive theorem provers and a first-order logic-based automated theorem prover to verify the control system of unmanned aerial vehicles and to ensure aircraft control system stability and performance. The framework relies on two stages, the first is for verifying the design of the control system and its stability and the second is for onboard monitoring of the aircraft's stability to ensure flight safety. The framework has been demonstrated on a robust attitude controller of a generic quadcopter UAV to verify the correctness of the design and stability analysis in addition to onboard monitoring the conditions of its dynamical stability while the aircraft is flying. The aircraft's attitudes are controlled by a nonlinear robust controller, which is designed using inverse dynamics control and it takes into account dynamical uncertainty and external disturbances.
The methods used in the verification stages go significantly beyond symbolic computation of inequalities for the Lyapunov theory as concepts of convergence as mappings of functions and quantifications over sets of functions are used in Isabelle and as such they were not be found in prior literature in aviation control systems.
The paper illustrated the applicability and the power of interactive theorem provers relying on HOL and automated theorem prover represented by FOL for control theory. This is promising and may encourage the use of such methods in control system verification of safety-critical systems in general. The symbolic methods are generic and potentially generalise to verification of a variety of industrial control systems, where performance loss is damaging and therefore analysis is important to be carried out formally.