Souvent, dû a l'aspect cyclique des programmes embarqu és, les traces de microcontrôleurs contiennent beaucoup de donn ées. De plus, dans notre contexte de travail, pour l'analyse du comportement, une seule trace se terminant sur une défaillance est disponible. L'objectif du travail pr esent é dans cette th ese est d'aider à l'analyse de trace de microcontrôleurs. La premi ère contribution de cette th èse concerne l'identifi cation de cycles, ainsi que la g én ération d'une description pertinente de la trace. La d étection de cycles repose sur l'identifi cation du loop- header. La description propos ée à l'ing enieur est produite en utilisant la compression bas ée sur la g én ération d'une grammaire. Cette derni ère permet la d etection de r ép étitions dans la trace. La seconde contribution concerne la localisation de faute(s). Elle est bas ée sur l'analogie entre les ex écutions du programme et les cycles. Ainsi, pour aider dans l'analyse de la trace, nous avons adapt é des techniques de localisation de faute(s) bas ée sur l'utilisation de spectres. Nous avons aussi d éfi ni un processus de filtrage permettant de r éduire le nombre de cycles àa utiliser pour la localisation de faute(s). Notre troisi ème contribution concerne l'aide a l'analyse des cas o ù les multiples cycles d'une même ex écution interagissent entre eux. Ainsi, pour faire de la localisation de faute(s) pour ce type de cas, nous nous int eressons à la recherche de r égles d'association. Le groupement des cycles en deux ensembles (cycles suspects et cycles corrects) pour la recherche de r égles d'association, permet de d e finir les comportements jug és correctes et ceux jug és comme suspects. Ainsi, pour la localisation de faute(s), nous proposons à l'ing enieur un diagnostic bas é sur l'analyse des r égles d'association selon leurs degr és de suspicion. Cette th èse pr esente également les évaluations men ées, permettant de mesurer l'efficacit e de chacune des contributions discut ées, et notre outil CoMET. Les r ésultats de ces évaluations montrent l'e fficacit e de notre travail d'aide à l'analyse de traces de microcontrôleurs.

Dans le domaine de l'aéronautique, les systèmes embarqués ont fait leur apparition durant les années 60, lorsque les équipements analogiques ont commencé à être remplacés par leurs équivalents numériques. Dès lors, l'engouement suscité par les progrès de l'informatique fut tel que de plus en plus de fonctionnali- tés ont été numérisées. L'accroissement permanent de la complexité des systèmes a conduit à la définition d'une architecture appelée Avionique Modulaire Intégrée (IMA pour Integrated Modular Avionics). Cette architecture se distingue des architectures antérieures, car elle est fondée sur des standards (ARINC 653 et ARINC 664 partie 7) permettant le partage des ressources de calcul et de communication entre les différentes fonctions avioniques. Ce type d'architecture est appliqué aussi bien dans le domaine civil avec le Boeing B777 et l'Airbus A380, que dans le domaine militaire avec le Rafale ou encore l'A400M. Pour des raisons de sûreté, le comportement temporel d'un système s'appuyant sur une architecture IMA doit être prévisible. Ce besoin se traduit par un ensemble d'exigences temps réel que doit satisfaire le système. Le problème exploré dans cette thèse concerne la vérification d'exigences temps réel dans les systèmes IMA. Ces exigences s'articulent autour de chaînes fonctionnelles, qui sont des séquences de fonctions. Une exigence spécifie alors une borne acceptable (minimale ou maximale) pour une propriété temporelle d'une ou plusieurs chaînes fonctionnelles. Nous avons identifié trois catégories d'exigences temps réel, que nous considérons pertinentes vis-à-vis des systèmes étudiés. Il s'agit des exigences de latence, de fraîcheur et de cohérence. Nous proposons une modélisation des systèmes IMA, et des exigences qu'ils doivent satisfaire, dans le formalisme du tagged signal model. Nous montrons alors comment, à partir de ce modèle, nous pouvons générer pour chaque exigence un programme linéaire mixte, c'est-à-dire contenant à la fois des variables entières et réelles, dont la solution optimale permet de vérifier la satisfaction de l'exigence.

Cette thèse présente Lion, un système de navigation utilisant des informations visuelles et inertielles pour l'atterrissage planétaire de précision. Lion est conçu pour voler au-dessus de n'importe quel type de terrain, plat ou accidenté, et ne fait pas d'hypothèse sur sa topographie. Faire un atterrir un véhicule d'exploration planétaire autonome à moins de 100 mètres d'un objectif cartographié est un défi pour la navigation. Les approches basées vision tentent d'apparrier des détails 2D détectés dans une image avec des amers 3D cartographiés pour atteindre la précision requise. Lion utilise de façon serrée des mesures venant d'un nouvel algorithme d'appariement imagecarte afin de mettre à jour l'état d'un filtre de Kalman étendu intégrant des données inertielles. Le traitement d'image utilise les prédictions d'état et de covariance du filtre dans le but de déterminer les régions et échelles d'extraction dans l'image où trouver des amers non-ambigus. Le traitement local par amer de l'échelle image permet d'améliorer de façon significative la répétabilité de leur détection entre l'image de descente et l'image orbitale de référence. Nous avons également conçu un banc d'essai matériel appelé Visilab pour évaluer Lion dans des conditions représentatives d'une mission lunaire. L'observabilité des performances de navigation absolue dans Visilab est évaluée à l'aide d'un nouveau modèle d'erreur. Les performances du systèmes sont évaluées aux altitudes clés de la descente, en terme de précision de navigation et robustesse au changement de capteurs ou d'illumination, inclinaison de la caméra de descente, et sur différents types de relief. Lion converge jusqu'à une erreur de 4 mètres de moyenne et 47 mètres de dispersion 3 RMS à 3 kilomètres d'altitude à l'échelle.

Cette thèse expose nos travaux de certification d'une partie d'un programme C/C++ nommé SimSoC (Simulation of System on Chip), qui simule le comportement d'archi- tectures basées sur des processeurs tels que ARM, PowerPC, MIPS ou SH4. Un simulateur de System on Chip peut être utilisé pour developper le logiciel d'un système embarqué spécifique, afin de raccourcir les phases des développement et de test, en particulier quand la vitesse de simulation est réaliste (environ 100 millions d'instructions par seconde par cœur dans le cas de SimSoC). Les réductions de temps et de coût de développement obtenues se traduisent par des cycles de conception interactifs et rapides, en évitant la lourdeur d'un système de développement matériel. SimSoC est un logiciel complexe, comprenant environ 60 000 de C++, intégrant des parties écrites en SystemC et des optimisations non triviales pour atteindre une grande vitesse de simulation. La partie de SimSoC dédiée au processeur ARM, l'un des plus répandus dans le domaine des SoC, transcrit les informations contenues dans un manuel épais de plus de 1000 pages. Les erreurs sont inévitables à ce niveau de complexité, et certaines sont passées au travers des tests intensifs effectués sur la version précédente de SimSoC pour l'ARMv5, qui réussissait tout de même à simuler l'amorçage complet de linux. Un problème critique se pose alors : le simulateur simule-t-il effectivement le matériel réel ? Pour apporter des éléments de réponse positifs à cette question, notre travail vise à prouver la correction d'une partie significative de SimSoC, de sorte à augmenter la confiance de l'utilisateur en ce similateur notamment pour des systèmes critiques. Nous avons concentré nos efforts sur un composant particulièrement sensible de SimSoC : le simulateur du jeu d'instructions de l'ARMv6, faisant partie de la version actuelle de SimSoC. Les approches basées sur une sémantique axiomatique (logique de Hoare par exemple) sont les plus répandues en preuve de programmes impératifs. Cependant, nous avons préféré essayer une approche moins classique mais plus directe, basée sur la sémantique opérationnelle de C : cela était rendu possible en théorie depuis la formalisation en Coq d'une telle sémantique au sein du projet CompCert et mettait à notre disposition toute la puissance de Coq pour gérer la complexitité de la spécification. À notre connaissance, au delà de la certification d'un simulateur, il s'agit de la première expérience de preuve de correction de programmes C à cette échelle basée sur la sémantique opérationnelle. Nous définissons une représentation du jeu d'instruction ARM et de ses modes d'adressage formalisée en Coq, grâce à un générateur automatique prenant en entrée le pseudo-code des instructions issu du manuel de référence ARM. Nous générons égale- ment l'arbre syntaxique abstrait CompCert du code C simulant les mêmes instructions au sein de Simlight, une version allégée de SimSoC. À partir de ces deux représentations Coq, nous pouvons énoncer et démontrer la correction de Simlight, en nous appuyant sur la sémantique opérationnelle définie dans CompCert. Cette méthodologie a été appliquée à au moins une instruction de chaque catégorie du jeu d'instruction de l'ARM. Au passage, nous avons amélioré la technologie disponible en Coq pour effectuer des inversions, une forme de raisonnement utilisée intensivement dans ce type de situation.

Le domaine scientifique dans lequel nos recherches s'insèrent est celui des Systèmes Multi-Agents. Dans ce domaine, nous nous intéressons à l'élaboration de modèles globaux définissant et structurant l'activité commune d'agents autonomes. En effet l'autonomie d'un agent se traduit par sa capacité à déterminer ses propres buts face à la configuration de l'environnement ainsi qu'à ses motivations. Du fait de cette autonomie, des conflits liés à l'existence de buts propres à chacun des agents autonomes d'une société d'agents peuvent être incompatibles, complémentaires ou en compétition avec les objectifs de la société. Des modèles de gestion de conflits existent, et dans le cadre de ce travail, nous nous sommes intéressés aux modèles organisationnels. Nous défendons la thèse selon laquelle la définition et la mise en place de contraintes globales influençant le fonctionnement d'agents autonomes doit être faite de manière à prendre en compte l'éventualité que les agents puissent ne pas respecter les contraintes selon les contextes et les objectifs individuels de chacun. Afin d'atteindre ces objectifs, nous proposons un modèle d'Institution Electronique comportant une description explicite et déclarative des contraintes à appliquer aux agents ainsi qu'un système de supervision et de renforcement de ces contraintes. Ce modèle permet de définir et de structurer grâce à MoiseInst l'activité d'un ensemble d'agents autonomes au sein d'une organisation normée et de superviser son respect grâce au système d'arbitrage Synai. Ce dernier est composé d'un ensemble d'agents de supervision capables de mettre en place des mécanismes de régulation et de renforcement de ces contraintes sur les agents autonomes. L'application du modèle se fait dans deux domaines totalement différents puisqu'ils concernent la création et l'exécution de contenu pour la télévision interactive d'un côté et la gestion de contrats électroniques d'une plate-forme de e-commerce de l'autre. Ils exhibent cependant la même problématique d'arbitrage d'entités autonomes devant respecter des contraintes. De plus, ces deux applications sont complémentaires par leur différence de portée de l'Institution.

Je présente une approche cognitive pour la planification de trajectoire sous contraintes. Elle repose en premier lieu sur DKP : un planificateur de trajectoires par échantillonnage. DKP construit un arbre d'exploration dans les parties atteignables de l'environnement à la manière d'un A∗ . Les solutions sont des trajectoires splines quadratiques adaptées au contrôle de robots à deux roues indépendantes. La couche de propagation construit un espace des paramètres, contenant toutes les valeurs des paramètres laissés libres dans les solutions. Il est représenté sous la forme d'une surface contenant toutes les solutions locales qui respectent les contraintes du problème : vitesse, accélération, évitement d'obstacle. . . Ensuite, une recherche de solutions est effectuée sur l'espace des paramètres selon un critère d'optimisation. DKP a la propriété d'être entièrement déterministe : les résultats sont reproductibles et son comportement est complètement contrôlable. Ce contrôle me sert à définir des comportements de pilotage. Ils sont exprimés sous la forme d'un arbre de comportements : chaque comportement agit sur la manière dont l'arbre d'exploration produit par DKP progresse dans l'environnement. De plus, les comportements sont appliqués en fonction de la partie explorée. Ainsi, seuls les comportements faisables sont développés. TÆMS permet de décrire ces comportements de pilotage puis d'évaluer les solutions ainsi construites. Pour résumer, mon approche cognitive repose sur l'évolution conjointe d'un arbre de comportements de pilotage et d'un arbre d'exploration : elle fait ainsi le lien entre planification classique et planification de trajectoire sous contraintes.

Thesis (M.S.)--State University of New York at Binghamton, Systems Science and Industrial Engineering Department, 2006. / Includes bibliographical references.

Thesis (Ph. D.)--University of Sydney, 1999. / Title from title screen (viewed Apr. 16, 2008). Submitted in fulfilment of the requirements for the degree of Doctor of Philosophy to the School of Electrical and Information Engineering, Faculty of Engineering. Degree awarded 1999; thesis submitted 1998. Includes bibliography. Also available in print form.

Thesis (M.Sc.) - Carleton University, 2006. / Includes bibliographical references (p. 143-147). Also available in electronic format on the Internet.

Thesis (doctoral)--Technische Universiteit Delft, 1991. / Summary and vita in Dutch and English; "stellingen" in Dutch. "Stellingen" inserted. Includes bibliographical references (p. 227-252) and index.