Safety verification of neural network based systems using formal methods

Contexte: la thèse a porté sur l'étude et la vérification de la sûreté de fonctionnement de systèmes contrôlés par réseaux de neurones. Ce type de système combine un système physique et un contrôleur basé réseaux de neurones. L'utilisation de ce type de contrôleur peut avoir differents intérêts: (1) approximer un autre contrôleur, déjà existant, mais en demandant moins de ressources de calcul (sachant qu'un contrôleur dispose souvent de ressources limitées) ou (2) reproduire le comportement d'un humain (ce qui peut s'avérer intéressant pour les systèmes autonomes). Dans le cas où le système contrôlé par réseaux de neurones est critique i.e., une défaillance de ce système peut entraîner des conséquences graves, alors il est important de vérifier sa sûreté de fonctionnement i.e., montrer qu'il n'atteint pas d'états non sûrs.Hypothèses: Dans la lignée des cas d'études présents dans la littérature, nous avons restreint notre étude à une forme particulière de contrôleur basé réseaux de neurones : un classificateur basé sur un ou plusieurs réseaux de neurones. Par ailleurs, nous avons considérés uniquement des réseaux de neurones feed-forward fully connected avec des fonctions d'activation ReLU.Exemple: un exemple typique de ce type de système est l'ACAS Xu qui comprend un contrôleur basé réseaux de neurones dont le rôle est d'éviter une collision entre deux avions. Pour ce système, le contrôleur basé réseaux de neurones approxime un autre contrôleur mais avec une empreinte mémoire très réduite. C'est un système critique car une défaillance peut entraîner une collision.Contributions: Afin de démontrer la sûreté de fonctionnement du système d'intérêt, nous avons d'abord considéré le cas où le contrôleur basé réseaux de neurones approxime un autre contrôleur. Pour ce cas de figure, nous avons développé une méthode et un outil afin de comparer les deux contrôleurs et montrer que le contrôleur basé réseaux de neurones est une approximation correcte du contrôleur cible. Notre méthode et notre outil ont été appliqués à l'ACAS Xu. Pour ce système en particulier, nous avons montré que nos travaux pouvaient servir au développement d'un contrôleur hybride, combinant le contrôleur basé réseaux de neurones et le contrôleur original, offrant à la fois une empreinte mémoire réduite et un comportement sûr. Pour notre seconde contribution, nous nous sommes concentrés sur la vérification du système contrôlé par réseaux de neurones en entier, pas seulement le contrôleur. Cette seconde contribution comporte deux aspects: (i) le développement d'un modèle basé automate hybride du système étudié et (ii) un outil, appelé SAMBA, qui permet l'analyse de cet automate hybride. Nos travaux ont été appliqués à l'ACAS Xu et nous avons aussi mené des comparaisons poussées avec d'autres outils de l'état de l'art. Ces comparaisons ont été menées sur la base de trois cas d'usages, parmi lesquels l'ACAS Xu, présentant différents types de dynamique, linéaire ou non linéaire, et impliquant des réseaux de neurones de différentes tailles. Les outils ont été comparés notamment sur leur capacité à résoudre un large éventail de problèmes de vérification. Nous avons aussi pu tirer plusieurs leçons de ces expériences et une méthodologie pour choisir le meilleur outil pour un problème de vérification donné.Context: the thesis focused on the study of neural network controlled systems and the verification of their safety. Such systems combine a physical system with a neural network controller. The use of a neural network controller in this context can have several interests: (1) approximate the behavior of an existing controller while demanding less computational resources (which is of particular interest for a controller that generally has limited resources) or (2) reproduce a human-like behavior (which can be particularly interesting for autonomous systems). If the neural network controlled system is safety-critical i.e., a failure of it can lead to serious consequences, then it is of particular interest to demonstrate that it is safe i.e., it does not encounter any unsafe state over time.Assumptions: in line with some use cases from the literature, we restricted our work to a particular form of neural network controller: a classifier based on one or multiple trained neural networks. Moreover, we considered only the case of feed-forward fully connected neural networks with Rectified Linear Unit activation functions.Example: a typical example is the ACAS Xu system, which involves a neural network controller that aims at avoiding a collision between two aircraft. In this system, the neural network controller approximates another controller but with dramatically reduced memory footprint. Such a system is safety-ciritcal since a failure of it could lead to a collision.Contributions: To demonstrate the safety of a neural network controlled system, we first considered the case where the neural network controller approximates another existing controller. For this case, we developed a method and a tool to compare the two controllers and show that the neural network controller correctly approximates the target controller. Our method and tool were applied to the ACAS Xu use case. For this particular system, we could show that our work could be used to design a hybrid controller, combining the network controller and the original one, providing both a reduced memory footprint and a safe behavior. In our second contribution, we addressed the verification of the whole neural network controlled system, not only the controller. More precisely, we developed: (i) a hybrid-automaton model of the neural network controlled system assumed in the thesis and (ii) a tool, called SAMBA, that allows the analysis of this hybrid automaton. Our work was applied to the ACAS Xu use case and we also conducted a thorough comparison between our tool SAMBA and 2 other state-of-the-art verification tools. The comparison was performed based on three use cases, including the ACAS Xu, which present different types of dynamics, linear or non-linear, and involve neural networks of different sizes. The tools were compared based on their capacity to solve a large variety of verification problems. We could draw some conclusions from these experiments, including some lessons learned and a methodology for choosing the best tool, for a given verification problem