Today’s critical systems of military and aviation grade consist of several complex requirements that need to be assessed for a safe and continuous operation before they are deployed for use. Several coverage methodologies have been proposed over the years with Modified Condition / Decision Coverage (MC/DC) being chosen by the aviation industry. This practice is becoming a highly recommended coverage methodology among several modern standards such as the Automotive Safety Integrity Level (ASIL) of automotive standard ISO 26262 and the Safety integrity level (SIL) 4 in part 3 Annex B of the basic safety publication. The main focus of this thesis is to provide an automated process that can provide test vectors suitable for applying MC/DC testing. By using as the core engine a modified version of a hardware-oriented technique used in Automatic Test Pattern Generation (ATPG) called PODEM (Path-Oriented Decision Making) we get to produce several test vectors that can contribute towards MC/DC structural coverage.

Un système embarqué est un système électronique et informatique autonome dédié à une tâche précise. Dans le secteur de l’automobile, le nombre de systèmes embarqués dans les voitures a considérablement augmenté au cours de ces dernières années et va certainement continuer à augmenter. Ces systèmes sont dédiés entre autres, à la sécurité, au confort de conduite,et à l’assistance à la conduite. Cette croissance des systèmes est associée avec une croissance en taille des logiciels qui les contrôlent. En conséquence, leur gestion(système et logiciel) devient de plus en plus complexe et problématique. Par ailleurs, la concurrence dans le secteur automobile est très féroce et les temps de mise sur le marché sont de plus en plus courts. Ainsi, pour garantir le bon fonctionnement des systèmes en général et du logiciel en particulier, étant donné leur complexité,et aussi les délais courts de mise sur le marché des produits automobiles, de nouvelles méthodes de développement doivent être considérées. Ainsi, de nombreuses méthodes de développement, incluant de nouveaux standards (de développement) et approches automatiques ont émergé au cours de ces dernières années. Dans le cas particulier de la vérification et validation de logiciel, une des activités critiques qui a connu une avancée significative est la génération de cas de test, avec l’avènement d’approches automatiques.Malgré cela, ces approches peinent souvent à s’imposer en milieu industriel. Une des raisons est que celles ci sont souvent peu adaptées ou peu utilisées dans un contexte industriel.Dans ce contexte, cette thèse vise à proposer une approche de vérification et de validation de logiciels embarqués, basée sur la génération automatique de cas de test. Pour cela, nous avons mis en place une approche permettant de représenter sous forme de modèles abstraits les spécifications d’un logiciel, puis de générer à partir de ces modèles un ensemble de cas de test en considérant en particulier le critère de couverture MC/DC. / An embedded system is a system that performs a specific task and has a computer embedded inside. In the automotive sector, the amount of embedded systems in the vehicle has risen dramatically in recent years and is set to increase. They deal essentially with safety, comfort, and driving assistance. Furthermore, the increase in number and complexity of the systems is associated with a growth in software. As a consequence, their management (system and software) have become more and more complex and problematic. Also, the competition and time-to-market in the automotive industry are very tough. Thus, to guarantee the efficiency and reliability of the embedded systems in the vehicle in general and the software in particular, in view of the complexity as well as the competition and time-to-market law, new development methods should be considered. Therefore, new development methods including new standards, and automatic approaches have emerged over the last years. In the particular case of embedded software verification and validation, one of the most critical activities that has experienced a significant progress is test case generation with the advent of automatic approaches. Despite this, these approaches are not widely used or are not well adapted in industrial context. In that context, our goal in this PhD. thesis is to propose a new verification and validation approach, based on automatic test case generation of embedded embedded. Thus, we have set up an approach that automatically generates test cases, with respect to the MC/DC criterion, from abstract models of the software specifications expressed in the form of state-transition models.

Cette thèse présente une étude qui répond à un besoin industriel d'avoir des outils pour aider à la qualité et au respect des processus de développement de logiciels critiques comme ceux du domaine de l'avionique civile. Il s'agit de l'étude de la couverture de code structurelle pour un langage de la famille ML. Dans ce contexte, ML apparaît comme un langage particulièrement riche en constructions de haut-niveau d'abstraction et expressif. Son utilisation est un élément de progrès mais soulève des problèmes d'adaptation des pratiques du génie logiciel classique pour les systèmes critiques. Notamment, la notion de couverture des conditions et des décisions ainsi que les critères de couverture dérivés se complexifient rapidement. Nous donnons alors en première contribution plusieurs sémantiques pour l'interprétation des définitions des conditions et des décisions pour un langage d'expressions de haut-niveau que nous avons complètement formellement défini. Ensuite, nous donnons la sémantique formelle pour une implantation pour la mesure de couverture par réécriture du code source, ce que nous appelons l'instrumentation intrusive. Puis, nous étudions une technique qui ne réécrit pas le code, ce qui permet d'avoir la possibilité d'utiliser le même binaire pour les tests et pour la production. Cette technique, que nous appelons non intrusive, consiste à générer les informations de correspondance entre le code source et le code machine, et éventuellement d'autres informations, pour que l'environnement d'exécution incluant une machine virtuelle puisse enregistrer les traces nécessaires à l'élaboration des rapports de couverture. Enfin, nous comparons ces deux approches, en terme de sémantique, d'utilisation et d'implantation.

The importance and requirements of certifying safety critical software is today more apparent than ever. This study focuses on the standards and practices used within the avionics, automotive and medical domain when it comes to safety critical software. We identify critical problems and trends when certifying safety critical software and propose a proof-of-concept using static analysis, model checking and incremental SAT solving as a contribution towards solving the identified problems. We present quantitative execution times and code coverage results of our proposed solution. The proposed solution is developed under the assumptions of safety critical software standards and compared to other studies proposing similar methods. Lastly, we conclude the issues and advantages of our proof-of-concept in perspective of the software developer community