Ce travail porte sur le test structurel des programmes réactifs synchrones érits en Lustre et sur la définition de critères de couverture pour assurer ce test structurel. Lustre est un langage réactif synchrone flot de données, largement utilisé pour la spécification et la programmation des applications critiques dans des domaines comme l'aéronautique, l'énergie ou les transports. L'application à Lustre des critères de couverture usuels basés sur le flot de contrôle (couverture des instructions, couverture des branches,...) n'est pas significative. <br /><br />Nous avons, en conséquence, défini une hiérarchie de critères adaptés au paradigme flot de données synchrone. Les critères permettent de mesurer la couverture des chemins dans un réseau d'opérateurs. Un réseau d'opérateurs est une modélisation graphique des flots de données dans un programme Lustre. Les critères sont basés sur le calcul symbolique des conditions d'activation de ces chemins. <br /><br />Un outil nommé Lustructu, a été réalisé pour mesurer la couverture atteinte par un jeu de tests selon ces critères. Lustructu analyse le programme sous test et calcule les chemins et leurs conditions d'activation. L'évaluation de la couverture par Lustructu est non-intrusive (pas d'instrumentation du code). L'applicabilité et la pertinence des critères ont été évaluées sur une étude de cas significative issue du secteur de l'aéronautique.

Le test structurel est généralement limité aux test unitaires et basé sur une définition claire de la couverture du code. En particulier, le critère tous-les-chemins, qui requiert au moins un cas de test par chemin faisable, est reconnu comme offrant un haut niveau de confiance dans les test effectués. Ce document traite des difficultés de l'utilisation de ce type de test sur des fonctions composées d'appels à d'autres fonctions. Pour limiter l'explosion combinatoire du nombre de chemins résultant d'un traitement "inlining", nous choisissons d'abstraire les fonctions appelées par leurs spécifications. Nous incluons les informations fonctionnelles des fonctions appelées aux informations structurelles de la fonction appelante données sous forme de graphe de flot de contrôle. Cette représentation fonctionnelle et structurelle peut être vue comme une extension du CFG classique ce qui nous permet de définir de nouveaux critères de couverture assurant le maintien de la couverture complète de la fonction appelante tout en limitant au maximum le nombre de cas de test nécessaires.

Les circuits intégrés devenant de plus en plus complexes, leur test demande des efforts considérables se répercutant sur le coût de développement et de production de ces composants. De nombreux travaux ont donc porté sur la réduction du coût de ce test en utilisant en particulier les techniques de compression de données de test. Toutefois ces techniques n'adressent que des coeurs numériques dont les concepteurs détiennent la connaissance de toutes les informations structurelles et donc en pratique n'adressent que le test de sous-blocs d'un système complet. Dans cette thèse, nous proposons tout d'abord une nouvelle technique de compression des données de test pour les circuits intégrés compatible avec le paradigme de la conception de systèmes (SoC) à partir de fonctions pré-synthétisées (IPs ou coeurs). Puis, deux méthodes de test des systèmes utilisant la compression sont proposées. La première est relative au test des systèmes SoC utilisant l'architecture de test IEEE 1500 (avec un mécanisme d'accès au test de type bus), la deuxième concerne le test des systèmes pour lesquels la communication interne s'appuie sur des structures de type réseau sur puce (NoC). Ces deux méthodes utilisent conjointement un ordonnancement du test des coeurs du système avec une technique de compression horizontale afin d'augmenter le parallélisme du test des coeurs constituant le système et ce, à coût matériel constant. Les résultats expérimentaux sur des systèmes sur puces de référence montrent des gains de l'ordre de 50% sur le temps de test du système complet. / While microelectronics systems become more and more complex, test costs have increased in the same way. Last years have seen many works focused on test cost reduction by using test data compression. However these techniques only focus on individual digital circuits whose structural implementation (netlist) is fully known by the designer. Therefore, they are not suitable for the testing of cores of a complete system. The goal of this PhD work was to provide a new solution for test data compression of integrated circuits taking into account the paradigm of systems-on-chip (SoC) built from pre-synthesized functions (IPs or cores). Then two systems testing method using compression are proposed for two different system architectures. The first one concerns SoC with IEEE 1500 test architecture (with bus-based test access mechanism), the second one concerns NoC-based systems. Both techniques use test scheduling methods combined with test data compression for better exploration of the design space. The idea is to increase test parallelism with no hardware extra cost. Experimental results performed on system-on-chip benchmarks show that the use of test data compression leads to test time reduction of about 50% at system level.

Ce document retrace de manière synthétique mes travaux de recherche depuis septembre 1999, date à laquelle j'ai été recruté sur un poste de Maître de Conférences à l'université Joseph Fourier (Grenoble 1).<br />Ces travaux, menés au sein de l'équipe VASCO du laboratoire LIG, portent sur le test des logiciels et sont étroitement liés aux recherches effectuées de 1993 à 1997, période pendant laquelle j'ai été thésard, puis chercheur contractuel dans cette même équipe.<br />Le test logiciel est une discipline qui embrasse l'ensemble du cycle de développement.<br />En effet, dès l'analyse des besoins d'une application, apparaissent des exigences et des propriétés à tester dont la caractérisation et l'identification font partie des compétences des testeurs. Il en est de même pour la spécification du produit, la conception de son architecture technique ou la programmation. <br />Le test logiciel est également une discipline qui se veut étroitement liée et utile à la pratique professionnelle. La prise en compte des problématiques issues de cette dernière s'est faite, entre autres, au moyen de nombreuses collaborations industrielles qui ont ponctué mes travaux, en particulier dans le cadre de projets nationaux (RNRT, RNTL).

Le problème abordé dans cette thèse concerne la productionautomatique de données de test permettant de prouver des propriétés de programmes. Nous nous situons ainsi à mi-chemin entre le domaine du test et celui de la vérification de programmes. Les travaux dans le domaine du test ont conduit à des outils semi-automatiques d'utilisation simple, mais qui reposent sur des hypothèses difficilement vérifiables en pratique. Dans le domaine de la vérification, des outils basés sur des méthodes formelles ont été développés, mais ils nécessitent un utilisateur expert dans les techniques de preuve utilisées par l'outil. Cette situation est due aux problèmes d'indécidabilité engendrés par la puissance des formalismes traités. La thèse que nous présentons est qu'il est possible de développer des méthodes formelles automatiques pour prouver des propriétés de programmes, à condition de considérer des formalismes restreints. Notre principale contribution est une nouvelle approche pour la vérification de programmes, intégrant les techniques de test et d'analyse statique. Nous proposons une méthode formelle de génération de jeux de test finis complets permettant de prouver qu'un programme vérifie une propriété donnée. Cette méthode utilise le texte du programme et de la propriété, qui doivent appartenir à certaines classes de programmes (ou de propriétés). Ces classes sont représentées par des hiérarchies de schémas, qui peuvent être vues comme modélisant des hypothèses de test. Tout programme appartenant à un de nos schémas et passant le jeu de test avec succès vérifie la propriété testée. Pour une propriété donnée, notre méthode est complètement automatique et ne nécessite donc aucune compétence particulière de l'utilisateur. Nous avons implanté cette méthode dans un prototype (traitant un langage fonctionnel restreint), pour le cas de propriétés s'exprimant en termes de longueurs de listes.

La validation des logiciels est une partie cruciale dans le cycle de leur développement. Deux techniques de vérification et de validation se sont démarquées au cours de ces dernières années : l'analyse statique et l'analyse dynamique. Les points forts et faibles des deux techniques sont complémentaires. Nous présentons dans cette thèse une combinaison originale de ces deux techniques. Dans cette combinaison, l'analyse statique signale les instructions risquant de provoquer des erreurs à l'exécution, par des alarmes dont certaines peuvent être de fausses alarmes, puis l'analyse dynamique (génération de tests) est utilisée pour confirmer ou rejeter ces alarmes. L'objectif de cette thèse est de rendre la recherche d'erreurs automatique, plus précise, et plus efficace en temps. Appliquée à des programmes de grande taille, la génération de tests, peut manquer de temps ou d'espace mémoire avant de confirmer certaines alarmes comme de vraies erreurs ou conclure qu'aucun chemin d'exécution ne peut atteindre l'état d'erreur de certaines alarmes et donc rejeter ces alarmes. Pour surmonter ce problème, nous proposons de réduire la taille du code source par le slicing avant de lancer la génération de tests. Le slicing transforme un programme en un autre programme plus simple, appelé slice, qui est équivalent au programme initial par rapport à certains critères. Quatre utilisations du slicing sont étudiées. La première utilisation est nommée all. Elle consiste à appliquer le slicing une seule fois, le critère de simplification étant l'ensemble de toutes les alarmes du programme qui ont été détectées par l'analyse statique. L'inconvénient de cette utilisation est que la génération de tests peut manquer de temps ou d'espace et les alarmes les plus faciles à classer sont pénalisées par l'analyse d'autres alarmes plus complexes. Dans la deuxième utilisation, nommée each, le slicing est effectué séparément par rapport à chaque alarme. Cependant, la génération de tests est exécutée pour chaque programme et il y a un risque de redondance d'analyse si des alarmes sont incluses dans d'autres slices. Pour pallier ces inconvénients, nous avons étudié les dépendances entre les alarmes et nous avons introduit deux utilisations avancées du slicing, nommées min et smart, qui exploitent ces dépendances. Dans l'utilisation min, le slicing est effectué par rapport à un ensemble minimal de sous-ensembles d'alarmes. Ces sous-ensembles sont choisis en fonction de dépendances entre les alarmes et l'union de ces sous-ensembles couvre l'ensemble de toutes les alarmes. Avec cette utilisation, on a moins de slices qu'avec each, et des slices plus simples qu'avec all. Cependant, l'analyse dynamique de certaines slices peut manquer de temps ou d'espace avant de classer certaines alarmes, tandis que l'analyse dynamique d'une slice éventuellement plus simple permettrait de les classer. L'utilisation smart consiste à appliquer l'utilisation précédente itérativement en réduisant la taille des sous-ensembles quand c'est nécessaire. Lorsqu'une alarme ne peut pas être classée par l'analyse dynamique d'une slice, des slices plus simples sont calculées. Nous prouvons la correction de la méthode proposée. Ces travaux sont implantés dans sante, notre outil qui relie l'outil de génération de tests PathCrawler et la plate-forme d'analyse statique Frama-C. Des expérimentations ont montré, d'une part, que notre combinaison est plus performante que chaque technique utilisée indépendamment et, d'autre part, que la vérification devient plus rapide avec l'utilisation du slicing. De plus, la simplification du programme par le slicing rend les erreurs détectées et les alarmes restantes plus faciles à analyser

Compte tenu de la complexité des circuits intégrés de nos jours et des nœuds technologiques qui ne cessent pas de diminuer, être au rendez-vous avec les demandes de design, test et fabrication des dispositifs de haute qualité est devenu un des plus grands défis. Avoir des circuits intégrés de plus en plus performants devrait être atteint tout en respectant les contraintes de basse consommation, de niveaux de fiabilité demandés, de taux de défauts acceptables ainsi que du bas coût. Avec ce fascinant progrès de l’industrie des semi-conducteurs, les processus de fabrication sont devenus de plus en plus difficile à contrôler, ce qui rend les puces électroniques de nos jours plus disposés aux défauts physiques. Le test était et restera l’unique solution pour lutter contre l’occurrence des défauts de fabrication ; même il est devenu un facteur prédominant dans le coût totale de fabrication des circuits intégrés. Même si des solutions de test, qui existent déjà, étaient capables de satisfaire ce fameux compromis coût-qualité ces dernières années, il arrive d’observer encore des mécanismes de défauts malheureusement incontrôlables. Certains sont intrinsèquement reliés au processus de fabrication en lui-même. D’autres reviennent sans doute aux pratiques de test et surtout quand on analyse le taux de défauts détectés et le niveau de fiabilité atteint.L’objectif principal de cette thèse est d’implémenter des stratégies de test robustes et efficaces qui répondent aux lacunes des techniques de tests classiques et qui proposent des modèles de fautes plus réalistes et répondent au mieux aux attentes des fournisseurs. Dans l’objectif d’améliorer l’efficacité de test en termes de coût, capacité de couverture de faute, nous présentons divers contributions significatives qui touchent différents domaines entre-autres le test sur le terrain, les tests à hautes fréquences sous contraintes de puissance et finalement le test des chaines de scan.La partie majeure de cette thèse était consacrée pour le développement de nouvelles techniques de tests fonctionnels ciblant les systèmes à processeurs.Les méthodologies appliquées couvrent les problèmes de test sur terrain aussi bien que les problèmes de test de fabrication. Dans le premier cas, la techniques adoptée consiste à fusionner et compacter un ensemble initial de programmes fonctionnels afin d’atteindre une couverture de faute satisfaisante tout en respectant les contraintes du test sur terrain (temps de test réduit et ressource mémoire limitée). Cependant dans le deuxième cas, comme nous avons assez d’informations sur la structure du design, nous proposons un nouveau protocole de test qui va exploiter l’architecture de test existante. Dans ce contexte, nous avons validé et confirmé la relation complémentaire qui joint le test fonctionnel avec le test structurel. D’autres part, cette prometteuse approche assure un test qui respecte les limites de la consommation fonctionnelle et donc une fiabilité meilleure.La dernière contribution de cette thèse accorde toute l’attention à l’amélioration de test de la structure DFT « Design For Test » la plus utilisée qui est la chaîne de scan. Nous présentons dans cette contribution une approche de test qui cible les défauts physiques au sein de la cellule en elle-même.Cette approche représente une couverture de défauts meilleure et une longueur de test plus réduit si nous la comparons avec l’ATPG classique ciblant les mêmes défauts « Intra-cell defect ATPG ».Comme résultat majeur de cette efficace solution de test, nous avons observé une amélioration de 7.22% de couverture de défaut accompagné d’une réduction de 33.5% du temps de test en comparaison avec la couverture et le temps du test atteints par le « Cell-awer ATPG ». / In light of the aggressive scaling and increasing complexity of digital circuits, meeting the demands for designing, testing and fabricating high quality devices is extremely challenging.Higher performance of integrated circuits needs to be achieved while respecting the constraints of low power consumption, required reliability levels, acceptable defect rates and low cost. With these advances in the SC industry, the manufacturing process are becoming more and more difficult to control, making chips more prone to defects.Test was and still is the unique solution to cover manufacturing defects; it is becoming a dominant factor in overall manufacturing cost.Even if existing test solutions were able to satisfy the cost-reliability trade-off in the last decade, there are still uncontrolled failure mechanisms. Some of them are intrinsically related to the manufacturing process and some others belong to the test practices especially when we consider the amount of detected defects and achieved reliability.The main goal of this thesis is to implement robust and effective test strategies to complement the existing test techniques and cope with the issues of test practices and fault models. With the objective to further improve the test efficiency in terms of cost and fault coverage capability, we present significant contributions in the diverse areas of in-field test, power-aware at-speed test and finally scan-chain testing.A big part of this thesis was devoted to develop new functional test techniques for processor-based systems. The applied methodologies cover both in-field and end-of manufacturing test issues. In the farmer, the implemented test technique is based on merging and compacting an initial functional program set in order to achieve higher fault coverage while reducing the test time and the memory occupation. However in the latter, since we already have the structure information of the design, we propose to develop a new test scheme by exploiting the existing scan chain. In this case we validate the complementary relationship between functional and structural testing while avoiding over as well under-testing issues.The last contribution of this thesis deals with the test improvement of the most used DFT structure that is the scan chain. We present in this contribution an intra-cell aware testing approach showing higher intra-cell defect coverage and lower test length when compared to conventional cell-aware ATPG. As major results of this effective test solution, we show that an intra-cell defect coverage increase of up to 7.22% and test time decrease of up to 33.5 % can be achieved in comparison with cell-aware ATPG.

La validation des logiciels est une partie cruciale dans le cycle de leur développement. Deux techniques de vérification et de validation se sont démarquées au cours de ces dernières années : l’analyse statique et l’analyse dynamique. Les points forts et faibles des deux techniques sont complémentaires. Nous présentons dans cette thèse une combinaison originale de ces deux techniques. Dans cette combinaison, l’analyse statique signale les instructions risquant de provoquer des erreurs à l’exécution, par des alarmes dont certaines peuvent être de fausses alarmes, puis l’analyse dynamique (génération de tests) est utilisée pour confirmer ou rejeter ces alarmes. L’objectif de cette thèse est de rendre la recherche d’erreurs automatique, plus précise, et plus efficace en temps. Appliquée à des programmes de grande taille, la génération de tests, peut manquer de temps ou d’espace mémoire avant de confirmer certaines alarmes comme de vraies erreurs ou conclure qu’aucun chemin d’exécution ne peut atteindre l’état d’erreur de certaines alarmes et donc rejeter ces alarmes. Pour surmonter ce problème, nous proposons de réduire la taille du code source par le slicing avant de lancer la génération de tests. Le slicing transforme un programme en un autre programme plus simple, appelé slice, qui est équivalent au programme initial par rapport à certains critères. Quatre utilisations du slicing sont étudiées. La première utilisation est nommée all. Elle consiste à appliquer le slicing une seule fois, le critère de simplification étant l’ensemble de toutes les alarmes du programme qui ont été détectées par l’analyse statique. L’inconvénient de cette utilisation est que la génération de tests peut manquer de temps ou d’espace et les alarmes les plus faciles à classer sont pénalisées par l’analyse d’autres alarmes plus complexes. Dans la deuxième utilisation, nommée each, le slicing est effectué séparément par rapport à chaque alarme. Cependant, la génération de tests est exécutée pour chaque programme et il y a un risque de redondance d’analyse si des alarmes sont incluses dans d’autres slices. Pour pallier ces inconvénients, nous avons étudié les dépendances entre les alarmes et nous avons introduit deux utilisations avancées du slicing, nommées min et smart, qui exploitent ces dépendances. Dans l’utilisation min, le slicing est effectué par rapport à un ensemble minimal de sous-ensembles d’alarmes. Ces sous-ensembles sont choisis en fonction de dépendances entre les alarmes et l’union de ces sous-ensembles couvre l’ensemble de toutes les alarmes. Avec cette utilisation, on a moins de slices qu’avec each, et des slices plus simples qu’avec all. Cependant, l’analyse dynamique de certaines slices peut manquer de temps ou d’espace avant de classer certaines alarmes, tandis que l’analyse dynamique d’une slice éventuellement plus simple permettrait de les classer. L’utilisation smart consiste à appliquer l’utilisation précédente itérativement en réduisant la taille des sous-ensembles quand c’est nécessaire. Lorsqu’une alarme ne peut pas être classée par l’analyse dynamique d’une slice, des slices plus simples sont calculées. Nous prouvons la correction de la méthode proposée. Ces travaux sont implantés dans sante, notre outil qui relie l’outil de génération de tests PathCrawler et la plate-forme d’analyse statique Frama-C. Des expérimentations ont montré, d’une part, que notre combinaison est plus performante que chaque technique utilisée indépendamment et, d’autre part, que la vérification devient plus rapide avec l’utilisation du slicing. De plus, la simplification du programme par le slicing rend les erreurs détectées et les alarmes restantes plus faciles à analyser / Software validation remains a crucial part in software development process. Two major techniques have improved in recent years, dynamic and static analysis. They have complementary strengths and weaknesses. We present in this thesis a new original combination of these methods to make the research of runtime errors more accurate, automatic and reduce the number of false alarms. We prove as well the correction of the method. In this combination, static analysis reports alarms of runtime errors some of which may be false alarms, and test generation is used to confirm or reject these alarms. When applied on large programs, test generation may lack time or space before confirming out certain alarms as real bugs or finding that some alarms are unreachable. To overcome this problem, we propose to reduce the source code by program slicing before running test generation. Program slicing transforms a program into another simpler program, which is equivalent to the original program with respect to certain criterion. Four usages of program slicing were studied. The first usage is called all. It applies the slicing only once, the simplification criterion is the set of all alarms in the program. The disadvantage of this usage is that test generation may lack time or space and alarms that are easier to classify are penalized by the analysis of other more complex alarms. In the second usage, called each, program slicing is performed with respect to each alarm separately. However, test generation is executed for each sliced program and there is a risk of redundancy if some alarms are included in many slices. To overcome these drawbacks, we studied dependencies between alarms on which we base to introduce two advanced usages of program slicing : min and smart. In the min usage, the slicing is performed with respect to subsets of alarms. These subsets are selected based on dependencies between alarms and the union of these subsets cover the whole set of alarms. With this usage, we analyze less slices than with each, and simpler slices than with all. However, the dynamic analysis of some slices may lack time or space before classifying some alarms, while the dynamic analysis of a simpler slice could possibly classify some. Usage smart applies previous usage iteratively by reducing the size of the subsets when necessary. When an alarm cannot be classified by the dynamic analysis of a slice, simpler slices are calculated. These works are implemented in sante, our tool that combines the test generation tool PathCrawler and the platform of static analysis Frama-C. Experiments have shown, firstly, that our combination is more effective than each technique used separately and, secondly, that the verification is faster after reducing the code with program slicing. Simplifying the program by program slicing also makes the detected errors and the remaining alarms easier to analyze