Brevet FR2830095A1 — publié le 20030328

PROCEDE ET DISPOSITIF DE VERIFIER DE CODE OPTIMISE L'invention concerne la vérification de code de programme chargé dans un dispositif électronique, par exemple-mais non exclusivement-un dispositif à mémoire restreinte tel qu'une carte à puce ou analogue. Plus particulièrement, l'invention s'adresse à la vérification de programmes qui sont organisés selon des types liés par des relations de filiation, conformément aux techniques actuelles de programmation en langage de haut niveau, et se base sur une technique de vérification qui met en oeuvre un processus d'unification de types visant à déterminer leur ascendant commun. Le but est de s'assurer que le programme chargé est cohérent avec les spécificités attendues au niveau du dispositif qui l'intègre. A cette fin, on fait appel à un vérifieur dont les tâches sont typiquement : d'interdire de : - fabriquer et modifier des pointeurs à partir de valeurs explicites ; - d'attaquer la pile ("overflow"/"underflow") ; et de garantir que : - chaque instruction a en entrée le bon nombre de paramètres et que ceux-ci sont bien typés ; et - tout objet a été initialisé une et une seule fois. On peut ainsi filtrer les programmes chargés avant de les intégrer, et notamment refuser ceux qui pourraient corrompre le bon fonctionnement du dispositif, soit intentionnellement par acte de malveillance, soit par erreur de programmation ou défaillance matérielle. Le problème global de la vérification de programmes sera présenté dans le cadre de dispositifs à mémoire restreinte, en l'occurrence une carte à puce à architecture dite ouverte. Ce type de carte permet à tout moment de charger et de modifier des programmes en langage de haut niveau. La carte à puce ouverte constitue alors une machine virtuelle autonome et communicante pouvant évoluer en fonction de nouvelles applications demandées par son porteur. La figure 1 illustre l'intervention d'un vérifieur dans ce contexte. La carte à puce 2 est à même de charger un ou plusieurs programmes, en l'occurrence du type"applet"4. Une fois le programme 4 chargé dans la carte, il est nécessaire de procéder à une phase d'intégration afin de le rendre opérationnel. La vérification intervient lors de cette phase, et sert à décider si la carte doit intégrer le programme ou, au contraire, le rejeter. Cette tâche est réalisée sur la base d'une analyse du code octet, ou pseudocode, que l'on désignera ci-après par le terme consacré de "byte code". Elle est réalisée par un vérifieur de byte code 6, qui constitue un élément fonctionnel de la machine virtuelle situé en amont de l'interpréteur de byte code 8. En opération, le vérifieur 6 détermine que la structure du programme chargé 4 est fonctionnellement intègre et compatible avec ce qui est attendu au niveau de la carte 2. Si le vérifieur valide le programme, il le transmet à l'interpréteur de byte code 8 en vu de son exécution. Dans le cas contraire, soit d'une détection de faille susceptible de mettre en péril la carte, le vérifieur 6 commande un processus (symbole repéré par le chiffre 10) destiné à rejeter le programme chargé 4. Dans le cas général, la mise en oeuvre d'un tel processus de vérification sollicite sensiblement les ressources mémoire du dispositif dans lequel s'effectue la vérification. En particulier, la nature itérative de la vérification nécessite de nombreuses mises à jour des données de résultat, et donc de transitions d'états logiques dans les cellules de mémorisation. Par ailleurs, l'espace mémoire à dédier au processus de vérification peut être considérable pour un dispositif à mémoire restreinte. En effet, le format de la carte impose des restrictions importantes dans ses ressources matérielles. Cet espace restreint est partagé en six composants fonctionnels, indiqués schématiquement à la figure 2, qui constituent un micro-module 12 de la carte 2, soit : - un microprocesseur 14 ; - un bloc sécurité 16 ; - une mémoire figée 18, accessible en lecture seulement (du type dit ROM (read only memory) en terminologie anglosaxonne) ; - une mémoire de travail volatile 20 (du type dit RAM (radom access memory) ou éventuellement FlashRAM en terminologie anglo-saxonne) ; - une mémoire persistante 22, soit non volatile, qui autorise néanmoins des cycles d'inscription et d'effacement. Cette mémoire est typiquement réalisée en technologie dite de mémoire ROM électriquement effaçable et inscriptible, dite EEPROM (electrically erasable programmable read only memory) en technologie anglo-saxonne ; et - des interfaces entrées/sorties 24. l'ensemble étant relié par un bus de données interne 26. Pour des raisons techniques, le micro-module 12 de la carte 2 est mieux pourvu en capacité de mémoire persistante 22 qu'en mémoire volatile 20. Or, les mémoires persistantes présentent un temps d'inscription très lent relativement à une mémoire volatile (d'un facteur allant 1000 à 10000), ce qui pénalise grandement le programmeur"carte". Qui plus est, la mémoire persistante 22 soulève un problème de fiabilité lié à sa durée de vie. En effet, selon la technologie employée, les transitions logiques des états de leurs cellules de mémorisation lors d'une écriture occasionnent une usure qui dépend fortement du sens de la transition ; on parle alors de transitions, ou opérations, "stressantes". A chaque écriture stressante d'une valeur en mémoire persistante, il existe une probabilité croissante que la cellule mémoire utilisée ait une défaillance. Dans ce cas, la valeur qui pourra être lue par la suite ne correspondra pas à ce qui a été écrit. A titre d'exemple, les fondeurs garantissent un nombre limité d'écritures (entre 104 et 106) pour une mémoire persistante en technologie EEPROM. Pour mémoire, une mémoire persistante de type EEPROM dispose de quatre opérations : - lecture, pour lire une valeur préalablement stockée ; - effacement, qui consiste à effectuer une transition d'état logique de 0 à 1, les cellules de stockage étant par défaut à l'état 1 ; - inscription, qui consiste à effectuer une transition d'état logique de 1 à 0 ; et - mise à jour, qui consiste à effectuer un effacement suivi d'une inscription. L'opération d'effacement est du type stressant, et peut entraîner une défaillance de la cellule mémoire associée. Le modèle de communication entre la carte à puce 2 et le terminal avec lequel elle communique est normalisé. La carte est considérée comme un serveur piloté par le terminal. Le fonctionnement se fait sans aucune collision. La communication est du type"demi-duplex" (communication dans un seul sens autorisé à la fois). La carte n'envoie une réponse vers le terminal qu'après que celui-ci lui ai posé une question. La tendance actuelle est d'intégrer la carte dans une informatique de plus en plus omniprésente. Pour ce faire, il a été développé des systèmes d'exploitation dit ouverts, tels que"JavaCard","Multos","Windows for Smartcards", et "Camille". Ces systèmes d'exploitation permettent à l'utilisateur de charger des applications, et ainsi d'enrichir à chaque instant l'usage qui peut être fait de la carte. De plus, ils permettent aussi aux applications encartées de communiquer entre elles. En ce qui concerne le système"JavaCard", on se base sur une architecture en quatre couches, telle que représentée à la figure 3. La couche la plus élevée contient les applications utilisateurs, dites "embarquées" 28 qui s'appuient sur des bibliothèques Java 30 dédiées à la carte 2. Ces bibliothèques sont un sous-ensemble des API Java (de l'anglais"Application Program Interface", soit interface de programme applicatif) constituent la deuxième couche du système"JavaCard". Le code des applications est exprimé dans un byte code qui est interprété par la machine virtuelle 32. Cette dernière exécute les programmes applicatifs et repose sur un système d'exploitation de base gérant les écritures en mémoire, les entrées-sorties, les appels aux routines cryptographiques assurant la sécurité, et enfin le support des diverses normes ISO. Les deux couches les plus basses 32 et 34 sont stockées dans la mémoire figée ROM 18 de la carte 2. Chaque méthode dispose de sa propre pile d'exécution contenant les variables et paramètres qu'elle manipule. La machine virtuelle utilise des registres pour stocker les variables dites locales (variables allouées en cours de méthode ainsi que les paramètres de celle-ci). La sécurité dans une machine virtuelle 32 est un problème important, car elle est un support d'exécution du code mobile, ce dernier pouvant être issu de sources diverses et incertaines. Ainsi, la machine virtuelle 32 peut être amenée à exécuter un code qui mette en péril la fiabilité du système ou d'autres composants. Au vu de ces difficultés, les techniques actuelles visent à faire de sorte que le dispositif à mémoire restreinte n'a pas à réaliser lui-même la vérification des programmes qu'il doit intégrer, cette tâche étant soit réalisée en amont, soit affranchie en s'appuyant sur des certificats d'homologation qui garantissent l'intégrité des programmes. Plus particulièrement, les solutions proposées reposent sur : - l'utilisation d'une machine virtuelle défensive ; - l'utilisation d'un organisme externe de certification à l'aide de cryptographie validant l'innocuité du code ; - l'utilisation d'algorithmes de vérification de byte code". La machine virtuelle défensive est dite"soupçonneuse". Pendant l'exécution, elle vérifie que chaque élément de byte code n'est pas utilisé à mauvais escient (par exemple, elle vérifie que chaque byte code dispose sur la pile d'exécution du bon nombre de paramètres, ou aussi que chaque appel de méthode est valide). Cette solution a le défaut de grever fortement les performances de la machine virtuelle. La solution utilisant un organisme de certification externe a l'avantage d'entraîner peu de modifications sur la machine virtuelle ; toutefois, cette solution est très lourde à déployer et nuit grandement à l'aspect ouvert de la machine virtuelle. La spécification Java définit un modèle de sécurité basé sur l'analyse du byte code lors de son chargement. Cette analyse a pour but de prouver l'innocuité du programme chargé ; dans le cas contraire, il est rejeté. La carte à puce dispose de capacités jugées trop limitées pour réaliser cette analyse. C'est pourquoi diverses solutions ont été proposées. Selon une autre approche connue, on réalise un prétraitement extérieur permettant de se munir du code d'informations additionnelles ou preuve permettant à la carte de vérifier le code lors du chargement. D'autres approches visent à intégrer un vérifieur de byte code dans les ressources du dispositif à mémoire restreinte. Ainsi a-t-il été proposé dans le document brevet WO-A-01 14958 de réaliser une modification"hors carte"du code du programme, de sorte que ce dernier maintienne sa signification d'origine mais devient plus aisé à vérifier. Cela simplifie le processus de vérification en permettant une vérification en une seule passe. Cependant, elle a l'inconvénient de nécessiter des modifications au code programme, et exclut la mise en oeuvre de certaines techniques d'optimisation. Selon encore une autre approche, utilisée notamment pour la machine virtuelle KVM (du terme consacré"K-virtual machine"), la vérification consiste à réaliser un pré-calcul, et à ajouter son résultat au code. Ce pré-calcul ajouté est ensuite utilisé par le vérifieur de byte code pour permettre l'utilisation d'algorithmes plus simples. Il s'agit donc d'une version simplifiée de la technique dite de code porteur de vérification (connue également par le terme"PCC"de l'anglais"Proof Carrying Code", soit code porteur de preuve). En langage Java, le byte code est spécifié de telle sorte qu'on puisse vérifier l'intégrité des opérations d'un programme statiquement. La vérification se décompose en deux parties : - une vérification structurelle ; et - une vérification de typage (l'inférence de type). L'inférence de type peut être considérée comme une analyse de flot de données, les données étant les cellules mémoires manipulées par les instructions, exprimées en byte code, de la machine virtuelle. Elle a pour but de défendre la machine virtuelle, ainsi que le système de base, mais aussi les applications utilisateurs, en refusant tout code qui pourrait nuire à leur intégrité. Le rôle principal de l'inférence de type est de s'assurer que chaque instruction qui compose un programme manipule les données (la mémoire) et déclenche l'exécution d'autres traitements en respectant leurs spécifications. L'inférence de type est un processus d'analyse statique de code qui s'effectue lors de la phase de chargement d'une application. Elle est réputée comme étant un algorithme coûteux en temps d'exécution, et aussi en consommation mémoire. Cela peut pénaliser fortement le processus de chargement du code dans la machine virtuelle 32. Ainsi, l'inférence de type est normalement exécutée par un tiers extérieur lorsque les contraintes matérielles sont jugées trop importantes (comme dans une carte à puce par exemple). Pour plus d'informations sur cet aspect, on peut faire référence aux publications : Rose E. et Rose K. H."Lightweight bytecode vérification" ; Workshop on Formal Underpinnings of the Java Paradigm, OOPSLA'98, 1998 ; et Necula G. C. et Lee P. "Proof Carrying Code"Proceedings of the 24th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages (POPL '97), pages 16-119, Paris, janvier 1997. Dans les articles de Colby C., Necula G. C., et Lee P."A proof carrying code architecture for Java"Computer Aided Verification, 2000 et Necula G. C."A scalable architecture for proof carrying code", Fifth International Symposium of Functional and Logic Programming, 2001, les inventeurs du PCC décrivent comment adapter cette technique à la vérification de bytecode Java et à la vérification embarquée. Les solutions connues offrent le même niveau de sécurité, et simplifient grandement le travail du vérifieur embarqué. Toutefois elles sont nettement moins souples qu'une solution totalement encartée, car toute application n'ayant pas son certificat avec elle sera rejetée, même si elle est valide. Le principal défaut des solutions à la PCC est que la preuve doit être chargée et stockée dans la carte. L'ajout d'un composant à charger ne contribue pas à diminuer le goulot d'étranglement qu'est le chargeur d'applications. De plus, la preuve doit être stockée en mémoire persistante (EEPROM) 22 du fait de sa taille, et souffre donc des problèmes de vitesse et de fiabilité. Les garanties apportées par l'inférence de type sont nombreuses et de nature variée. La plus importante concerne la sécurité de la machine virtuelle 32. On cherche à garantir la cohérence et la consistance de celle-ci. Au vu de ce qui précède, l'invention propose, selon un premier aspect, un procédé de vérification d'un programme lors de sa phase d'intégration dans un dispositif électronique, le programme étant organisé selon des types liés par des relations de filiation, chaque type étant identifié par un code respectif, le procédé comportant une phase d'unification de types visant à déterminer leur ascendant commun le plus proche, caractérisé en ce que le code est décrit sous forme de motif de bits selon un formalisme qui exprime la filiation du type auquel il est associé, et en ce que la phase d'unification comprend une combinaison logique de motifs attribués aux types à unifier, produisant le motif du type qui est leur ascendant commun le plus proche. Avantageusement, pour tout type ayant un ascendant, son motif contient au moins un bit qui est identique en valeur et en position à un bit correspondant du motif de son ascendant direct. Le motif d'un type donné comporte de préférence un nombre de bits à un état logique prédéterminé qui est fonction de l'éloignement du type de l'ascendant commun. Dans un mode de réalisation préféré, on utilise une mémoire sujette à une usure par des transitions d'état logique usantes, pour stocker au moins un motif destiné à être soumis à une combinaison logique ou qui résulte d'une combinaison logique dans la phase d'unification. On peut alors envisager un formalisme d'attribution de motif qui établit une prépondérance d'un état logique dans l'ensemble des motifs qui minimise le nombre de transitions usantes nécessaires pour réaliser le stockage des motifs dans la mémoire. De préférence, on initialise les cellules de stockage de la mémoire à l'état logique à partir duquel la transition est dans le sens opposé au sens de la transition usante. Lorsque la transition usante est dans le sens de l'état logique 0 à l'état logique 1, la combinaison logique consiste de préférence à réaliser une opération logique du type ET entre chaque paire de bits de même rang des motifs combinés. Lorsque la transition usante est dans le sens de l'état logique 1 à l'état logique 0, la combinaison logique consiste de préférence à réaliser une opération logique du type OU entre chaque paire de bits de même rang des motifs combinés. Par ailleurs, le procédé peut être mis en oeuvre pour un programme qui se présente sous forme d'un ensemble de sections de code, chaque section étant identifiée par un marquage qui correspond à une instruction atteignable depuis un branchement, en procédant à la vérification par sections dans un ordre de sections donné selon une heuristique déterminée. Dans ce cas, l'ordre des sections à vérifier peut être l'ordre de succession d'une section vérifiée suivi par sa section qui lui est son successeur. L'ordre des sections à vérifier peut aussi être donné par la première section marquée. Avantageusement, on met en oeuvre une mémoire volatile en tant que cache pour stocker des motifs candidats à l'étape de combinaison logique, et on choisit les motifs candidats de manière dynamique et par prévision en fonction de points de branchement dans le programme à vérifier. On peut alors sélectionner pour stockage dans la mémoire volatile ceux des motifs qui correspondent à des types susceptibles de faire l'objet d'une unification à une échéance donnée, et réaliser cette sélection des motifs à stocker par référence à un graphe de flot de contrôle du programme'à vérifier. A l'inverse, on peut sélectionner pour déstockage de la mémoire volatile ceux des motifs qui correspondent à des types plus susceptibles de faire l'objet d'une unification à une échéance donnée, et réaliser la sélection des motifs à déstocker par référence à un graphe de flot de contrôle du programme à vérifier. De préférence, on établit le graphe de flot de contrôle à partir des marquages préalablement déterminés et des instructions qui branchent vers ces marquages. Dans les modes de réalisation envisagés, on réalise le procédé de vérification avec le support d'exécution du dispositif destiné à exécuter le code du programme faisant l'objet de la vérification. L'invention est particulièrement avantageuse pour réaliser la vérification dans un dispositif électronique de type carte à puce. Selon un deuxième aspect, l'invention concerne un dispositif électronique de vérification d'un programme lors de sa phase d'intégration dans un dispositif électronique, le programme étant organisé selon des types liés par des relations de filiation, chaque type étant identifié par un code respectif, ledit dispositif comportant des moyens d'unification de types pour déterminer leur ascendant commun le plus proche, caractérisé en ce qu'il comprend des moyens d'identification de filiation de types, l'identification d'un type étant réalisée sur la base d'un motif de bits qui constitue son code selon un formalisme déterminé, et en ce que les moyens d'unification comprennent des moyens de combinaison logique de motifs attribués aux types à unifier, produisant le motif du type qui est leur ascendant commun le plus proche. Ce dispositif de vérification peut être réalisé pour être apte à exécuter le procédé selon le premier aspect. Selon un troisième aspect, l'invention concerne un dispositif électronique permettant de charger et exécuter un programme organisé selon des types liés par des relations'de filiation, chaque type étant identifié par un code respectif, caractérisé en ce qu'il intègre un dispositif de vérification selon le deuxième aspect. Dans les modes de réalisation envisagés, ce dispositif est réalisé sous forme de carte à puce. L'invention et les avantages qui en découlent apparaîtront plus clairement à la lecture de la description qui suit des modes de réalisation préférés, donnée purement à titre d'exemples non limitatifs, par référence aux dessins annexés dont : - la figure 1, déjà décrite, est un schéma qui illustre le principe d'intégration d'un vérifieur de code dans un dispositif portatif tel qu'une carte à puce ; - la figure 2, déjà décrite, est un schéma bloc des éléments fonctionnels qui constituent un micro-module d'une carte à puce à architecture ouverte ; - la figure 3, déjà décrite, est un schéma illustrant les couches constitutives d'une machine virtuelle ; - la figure 4 est un exemple, présenté sous forme de tableau, de nouvelle trace d'inférence de type après modification de l'hypothèse de jointure ; - la figure 5 représente un exemple d'encodage de treillis unifiant non stressant, conforme au mode de réalisation préféré ; et - la figure 6 est un exemple illustrant l'utilisation d'un graphe de flot de contrôle pour accélérer la vérification au moyen d'un cache logiciel. Avant de décrire les modes de réalisation de l'invention, il sera présenté les principes d'une vérification de byte code dans une machine virtuelle 32 à l'aide d'un algorithme dit"de référence", décrit dans le document brevet US-A-5 668 999. Pour faciliter la compréhension de l'algorithme de référence, aussi connu par le terme d'algorithme d'inférence de type, on utilisera sa description par des exemples appliqués au langage Java. Comme décrit précédemment, la machine virtuelle Java est une machine à pile. Elle effectue des opérations sur des variables de travail appelées variables locales, ainsi que sur une pile. Le but de ce procédé est de déterminer le type de chacune des variables locales et de chacune des cellules de la pile pour chaque point du programme. Pour ce faire, on tire parti du fait que les byte codes Java sont typés. Dans ce qui suit, on désigne "contexte d'exécution" le couple variables locales/pile. Il contient des informations de typage. L'inférence de type est basée sur une analyse statique du code. Chaque instruction du byte code Java peut se modéliser comme prenant ses paramètres sur la pile ou dans les variables locales, et en générant un résultat sur le sommet de pile ou dans une variable locale, si besoin est. Pour les objets et variables Java alloués en cours de méthode, on détermine leurs types à l'aide du byte code utilisé pour leur création. Il existe une relation d'ordre entre les classes que l'on illustrera par l'exemple suivant. On dispose de deux classes "Père" et "Fils", tel que "Fils"soit une sous-classe de"Père"liées par le code : "class Fils extends Père { public static Père m () { return new Fils () ; } La méthode"Fils m ()" affirme retourner une classe de type"Père", or elle retourne un élément de type"Fils". Un problème se pose lors de la vérification :"Fils"est elle compatible avec "père" ? On répond par l'affirmatif, car"Fils" est une sous-classe de"Père". Cet exemple illustre la nécessité d'une opération permettant de déterminer si un type est compatible avec un autre. Plus simplement, à l'aide de la relation d'ordre, on bâtit une fonction que permet d'affirmer si l'on peut utiliser un type en lieu et place d'un autre. Comportement de T vis à vis de la relation d'ordre Le type désigné "T" est la racine du treillis ; il n'est compatible qu'avec lui même. C'est le plus grand élément du treillis. Une variable du type T est une variable inutilisable. Comportement de"null"vis à vis de la relation d'ordre. Le type"null"est l'élément fermant la partie du treillis contenant les classes Java. C'est le plus petit élément de cette partie. Il est donc compatible avec toutes les classes Java. Unifieur et point fixe. L'exemple dont la trace d'inférence de type est donnée en figure 4 illustre une autre particularité de l'algorithme d'inférence de type. Par les deux chemins du programme, on établit deux hypothèses différentes sur le type de la variable en sommet de pile. La première solution est de marquer celleci comme étant du type T, donc non utilisable. Ceci est trop restrictif : la méthode "doit () " est une méthode définie dans le classe"Père"dont le code Java est valide. En effet, à la fois"Filsl"et"Fils2"ont hérité de cette méthode. A la sortie du bloc"if-else", on doit mettre en relation les deux hypothèses sur la variable en sommet de pile. Statiquement, on ne peut déterminer laquelle des deux est la bonne. Partant de la remarque que Père est la classe mère de "Filsl"et"Fils2", on peut dire que, à la sortie du bloc"if- else", le sommet de pile contient une référence sur un élément de type "Père", seule hypothèse compatible avec celles obtenues par inférence de type sur chacun des chemins de notre programme. On réalise ainsi une sorte de jointure des hypothèses. Cette jointure est appelée "unification". On définit ainsi une nouvelle relation qui consiste à trouver le"Père commun" à deux types. Comme le treillis est borné supérieurement ; on peut le définir et l'utiliser. On l'appelle"unifieur"et on le désigne par le symbole"n". Dans la théorie mathématique relative aux treillis, cette opération consiste à déterminer le père commun de deux noeuds. Ce noeud s'appelle le LUB (de la terminologie anglo-saxonne "least-upper-bound"). La complexité de cette opération augmente rapidement au fur et à mesure que la profondeur-du treillis augmente. Ainsi, il est non trivial de la mettre en place dans le contexte d'un dispositif à mémoire restreinte, tel qu'une carte à puce. De plus on peut être amené à réitérer le processus d'inférence de type sur une section de code. En effet, si l'on remet en cause des hypothèses au niveau du point d'entrée d'une section de code, il convient de la rejouer avec la nouvelle hypothèse. Le nombre d'itérations est nécessairement fini, car chaque unification contribue à remonter les types des variables vers T, que l'on atteindra dans le pire des cas. En effet, les transformations utilisées sont des fonctions monotones. Le programme Java suivant illustre une recherche de point fixe : "public static void m (boolean b) { Object o=null ; while (b) { o=new Object ; } } Au premier passage, la variable locale vl est du type "null". On exécute une première inférence de type sur la section de code correspondant au"while". Dans celle-ci, on stocke un"Object"dans la variable locale vl. Ensuite on branche au début du"while", et on effectue donc une jointure entre les deux hypothèses. La variable locale vl, qui était de type"null"au premier passage, est maintenant de type"ref Object", car"null"est compatible avec toutes les classes Java. On doit rejouer la section de code correspondant au "while"pour voir si la nouvelle hypothèse est compatible avec cette section de code. Dans l'exemple, elle l'est, et le programme est donc accepté. On dénomme ce qui précède une recherche de point fixe, car on cesse d'stérer le processus d'inférence de type lorsque l'on atteint un équilibre, ou plus exactement lorsque les unifications ne modifient plus les informations de typage. Algorithme de référence L'algorithme dans cette section est décrit sous sa forme la plus générique, qui ne correspond pas tout à fait à celui utilisé par la suite, car il est dépourvu de toute forme d'optimisation. Pour chacune des instructions utilisées, on dispose d'une sorte de tableau contenant le type de chacune des variables locales, celui des éléments de la pile, ainsi que la valeur de l'indice de pile, dénommé TOS (de l'anglais"top of stack", soit sommet de la pile). (En terminologie anglo-saxonne, ce tableau est connu par la désignation"type frame"). De plus, on dispose aussi d'un drapeau pour chaque instruction ; il illustre le fait que les informations de typage de l'instruction correspondante ont, ou n'ont pas, été modifiées par une des dernières unifications ayant été effectuée. Ce drapeau peut prendre deux valeurs :"changed" (changé) ou "unchanged" (inchangé). L'algorithme de référence comporte deux phases successives, désignées respectivement "initialisation" et "boucle principale", dont les étapes principales se résument comme suit Initialisation : - initialisation de l'information pour chaque instruction de programme. Positionner toutes les instructions à l'état "unchanged", hormis la première instruction qui sera positionné à l'état comme"changed" ; - remplir les informations de typage de celle-ci à l'aide de la signature, les variables n'ayant pas de type sont initialisées avec T, initialiser son TOS avec la valeur 0 i - pour les autres instructions I ; - mettre le drapeau de I à la valeur"unchanged" - initialiser le TOS à-1 (ceci pour marquer que cette instruction n'a pas encore été visitée) ; Boucle principale : - tant qu'il reste des instructions ayant leur drapeau à la valeur"changed" ; - choisir une instruction marquée comme"changed" ; on'la note I ; - marquer l comme "unchanged" ; - simuler l'exécution de I sur les informations de typage associées à celle-ci. Si cette simulation échoue, la méthode est rejetée. La"frame de type"obtenue est notée R - pour chacun des successeurs S de I ; - noter 0 la "frame de type" de I, et R celle de S ; - si le TOS associé à S vaut-1, R=O (et on copie aussi le TOS de I dans celui de S) ; - sinon, appliquer l'unification de R et de O. Le résultat est noté R n 0 (si les TOS des deux"frames de type" sont différents, la vérification échoue) ; - si R n O w R, marquer S comme"changed", R n 0 devient la nouvelle"frame de type"de S. On itère la boucle principale tant qu'il y a des instructions marquées comme"changed". L'arrêt se fait lorsque l'on obtient une position stable 1 d'où l'utilisation du terme point fixe. La simulation de l'exécution consiste, comme décrit précédemment, à vérifier les paramètres présents sur la pile (ils sont en nombre suffisant, et leurs types sont ceux attendus), puis à mettre à jour la"frame de type"en fonction du byte code exécuté. On vérifie ainsi qu'il n'y a pas de débordement supérieur et inférieur de la pile, et aussi que le typage est correct. Il sera maintenant abordé les aspects à considérer pour transposer ces notions de vérification dans le cadre d'une carte à puce. La problématique principale réside dans les limites de ressources de traitement et de stockage inhérentes aux cartes, ainsi présenté plus haut. De plus, à partir du byte code, il est nécessaire de retrouver le type de chacun des champs manipulés. Cette opération est délicate. Qui plus est, elle est exécutée de nombreuses fois lors de l'inférence de type, et requiert par conséquent de nombreux parcours dans des structures de tailles variables. Une solution est de se construire une représentation interne efficace. Typage propre au byte code JavaCard. Le langage JavaCard nécessite un typage adapté, ce qui implique des modifications et adaptations des algorithmes décrits précédemment, notamment en ce qui concerne le treillis des types et les sous-routines. Le treillis des types. Un exemple de treillis des types JavaCard est représenté à la figure 5. De ce qui précède, on constate que l'inférence de type requiert de nombreux appels à la fonction d'unification. La manière la plus standard de la mettre en oeuvre consiste à construire une structure ordonnée pour représenter le treillis. Cette solution est peu envisageable dans le contexte de la carte à microprocesseur car elle nécessiterait des quantités importantes de mémoire. La manière la plus standard de mettre en oeuvre en milieu fortement contraint consiste à utiliser une série de tests en cascade en fonction des deux types à unifier. Cette solution est non optimale. La solution retenue dans les modes de réalisation seront décrits dans le cadre de programmes embarqués dans un dispositif, notamment une carte à puce 2, qui permet de réaliser une inférence de type complète, grâce à des techniques et optimisations conformes à l'invention. La description aborde d'abord les mécanismes accélérateurs de l'unification, suivi d'une optimisation de la gestion des points fixes basée sur l'utilisation de caches logiciels. Gestion efficace de l'unification. Les modes de réalisation abordent le problème posé par la complexité de l'inférence par deux solutions : une table d'unification et, à titre optionnel, un codage unifiant efficace et non stressant pour les mémoires sujettes à usure par des transitions dans un certain sens. - Table d'unification. Une première solution utilisée par le mode de réalisation consiste à pré-calculer les règles d'unifications des types. On obtient alors une table à deux entrées (les deux types tl et t2 à unifier), qui fournit la réponse à la question que vaut tl n t2. Il se pose alors le problème lié à l'infinité de types à disposition : il est en effet possible de charger un nombre important de classes dans la carte à puce. L'ajout d'une nouvelle classe entraînerait donc la création d'une nouvelle ligne ou colonne de la table d'unification, ainsi que le calcul du résultat de l'unification de celle-ci avec tous les types déjà présents dans la carte à cet instant. Un exemple d'une portion d'une table d'accélération de l'unification est donné au tableau Ici-après. (Le symbole "T" (pour"top") désigne le père commun de tous les types, soit le sommet du treillis.) Table 1 : exemple d'une portion de table d'accélération de l'unification. Top int Objec array byte short int null t Top Top Top Top Top Top Top Top Top int Top int Top Top Top Top Top Top Objec Top Top Objec Objec Objec Objec Objec Objec t t t t t t t bool Top Top Objec bool Objec Objec Objec bool t t t t byte Top Top Objec Objec byte Objec Objec byte t t t t short Top Top Objec Objec Objec short Objec short t t t t int Top Top Objec Objec Objec Objec int int t t t t null Top Top Objec bool byte short int null L'utilisation d'une table pour faire l'unification est facile à mettre en place. De plus, la table étant calculée une et une seule fois, elle peut ainsi être stockée dans la mémoire ROM 18 de la carte 2. Par cette approche, on réduit l'unification à une lecture dans un tableau à deux entrées dans la majeure partie des cas. Codage unifiant efficace et non stressant. Les informations manipulées lors de l'inférence sont les types. Pour chaque type, on établit un codage selon un formalisme qui exprime sa filiation. Ce codage sert à obtenir une unification plus efficace. A cette fin, on utilise une technique mettant en oeuvre une bijection des opérations sur les treillis vers les opérations booléennes. Les encodages utilisés permettent de trouver le père commun de deux éléments d'un treillis à l'aide d'une composition de fonctions logiques. Le résultat, qui constitue l'unification, rend alors le code qui correspond, selon le formalisme établi, au père commun de deux types. Dans la pratique, les informations de typage doivent, dans la majeure partie des cas, être stockées en mémoire persistante 22, notamment du type EEPROM, du fait de leur taille. Or ce type de mémoire est sujet au stress. Plus particulièrement, la mémoire souffre d'une usure occasionnée par un cumul de transitions d'états logiques dans un sens particulier, en l'occurrence de 0 à 1. A l'inverse, l'opération consistant à faire tomber un bit de 1 à 0 en EEPROM est non stressante (elle n'abîme pas la cellule mémoire correspondante). Partant du fait que pendant une unification on remonte les types dans le treillis vers le type T, le formalisme adopté vise à faire que cette opération ne produise que des transitions des bits d'EEPROM de 1 à 0. Cette approche est illustrée par l'exemple représenté à la figure 5. La figure 5 représente un cas de treillis unifiant non stressant. Le père commun de tous les types, au sommet du treillis, est désigné Top (pour"top"en anglais). Le formalisme utilisé dans le mode de réalisation, adapté pour éviter autant que possible les transitions stressantes dans la mémoire EEPROM 22 de la carte 2, fixe comme code pour ce père commun un motif formé de bits à l'état 0. Le nombre de bits formant ce motif est choisi en fonction du nombre maximum de types dans le treillis qui partagent un même ascendant commun. Tout type est codé avec un motif comportant un même nombre de bits. Dans l'exemple, six bits constituent un motif, le père commun T ayant le motif"00 0000". On s'assure notamment que ce nombre de bits permette : - d'une part d'attribuer à chaque type du treillis un motif unique, et - d'autre part d'exprimer, sur la base du nombre de bits à l'état 1, 11 éloignement du type correspondant du sommet de treillis T, soit sa profondeur dans le treillis (en termes de nombre d'ascendants reliant ce type au père commun). Dans l'exemple, cet éloignement est indiqué directement par le nombre de bits à l'état 1, sauf pour le cas du type"Null"qui constitue le fond du treillis, auquel est attribué un motif à part, en l'occurrence"01 1111"dans l'exemple. On remarque que pour un type donné (hormis le père commun T), son motif comporte au moins un bit qui est identique en valeur et en position au motif de son ascendant direct. Pour un type donné ayant un ascendant direct qui n'est pas le père commun, chaque bit à l'état 1 de cet ascendant se retrouve à la même position dans le motif de ce type donné. (Ce dernier comporte en outre un bit supplémentaire à l'état 1 qui lui est spécifique, et permet de le distinguer entre d'autres descendants directs de cet ascendant commun direct.) Ainsi, lorsqu'il existe plusieurs types ayant un ascendant commun, une simple opération logique ET entre les motifs de deux motifs permet de reproduire le motif de l'ascendant commun direct. L'opération ET entre des motifs consiste à réaliser une opération ET entre chacun des bits à la même position des motifs. On réalise alors l'unification des types par cette opération ET sur leurs motifs. A titre illustratif, on vérifie que la combinaison ET des motifs attribués aux types"bool"et"short"de la figure 5, soit (01 0001) ET (01 0100) : 0 ET 0 = 1, 1 ET 1 = 1,... 1'ET 0 = 0, rend le motif 01 0000 qui correspond à leur père commun "Object". La propriété la plus importante de cet encodage est qu'il est particulièrement adapté au stockage en EEPROM : on peut être amené à stocker les informations de typage dans l'EEPROM en particulier, car celles-ci peuvent être de taille importante par rapport aux autres mémoires disponibles de la carte à puce. Le stress de l'EEPROM est limité lorsque l'on fait tomber des bits (passage de 1 à 0). L'unification se réduisant à un ET logique, en l'appliquant à deux types, on ne change que des bits de 1 à 0 et jamais de 0 à 1. Ainsi, on réduit considérablement le stress et on augmente la durée de vie de l'EEPROM. Un codage de cette sorte peut être adapté à tout type d'EEPROM. En effet, certaines ont des propriétés inverses pour le stress en écriture, soit une transition stressante occasionnée par le passage 1 à 0. Dans ce cas, on change le codage de telle sorte que l'unification se réduise à un OU logique. Plus particulièrement, on inverse systématiquement les états logiques des motifs par rapport à ceux utilisés pour les combinaisons ET décrites plus haut. Pour reprendre l'exemple de la figure 5, on attribue alors au père commun T le motif 11 1111, le motif 01 1111 au type"Int", etc. Il peut être aisément vérifié sur la base de simples principes de logique booléenne que l'on obtient dans ce cas les mêmes résultats avec l'opération logique OU à la place de l'opération logique ET dans le cadre de la figure 5. Au besoin, le codage peut être rendu plus compact en utilisant une fonction booléenne plus complexe, moyennant des stockages en mémoire EEPROM pouvant occasionner des transitions stressantes. Gestion efficace des points fixes. On rappelle que l'inférence de type est une recherche de points fixes. L'encodage des types décrit précédemment contribue nettement à la diminution du stress de l'EEPROM. Le mode de réalisation permet en outre de : - accélérer l'unification, - optimiser l'usage de la mémoire RAM 20, et - avoir un algorithme générique à la fois dans le cas où la vérification peut se faire en RAM, mais aussi lorsqu'il est fait appel à l'EEPROM. Ces avantages s'obtiennent d'une part en utilisant des heuristiques de sélection du marquage (aussi connu par le terme "label") à vérifier, et d'autre part en combinant cette sélection au pilotage d'un cache logiciel, c'est-à-dire une partie de mémoire RAM utilisée comme mémoire cache pour accès rapide aux données susceptibles d'être traitées dans l'immédiat. Le but consiste alors à charger dans le cache les motifs des types pour lesquels on envisage une opération d'unification à courte échéance. Ces motifs, dits motifs"candidats"sont choisis par des techniques prévisionnelles définies par une règle générale dénommée "heuristique". La capacité en mémoire cache logiciel étant limitée, une heuristique doit permettre de prévoir non seulement les motifs appelés prochainement à être combinés, mais aussi, à l'inverse, de prévoir ceux plus susceptibles d'être combinés afin de les éliminer. Cela implique une gestion dynamique et évolutive. Par ailleurs, on utilise avantageusement des heuristiques qui ne demandent que peu de calcul pour ne pas grever les ressources utilisées. Heuristique de sélection de marquage à vérifier. L'algorithme optimisé d'inférence de type décrit plus haut travaille au niveau des points de branchement des programmes JavaCard. Au cours de l'inférence, on peut avoir plusieurs labels marqués comme étant à vérifier. Cela amène donc à élire l'un d'eux et à vérifier la section de code correspondante. Il faut donc disposer d'un critère de choix. Pour mesurer et comparer les heuristiques possibles, un ratio, noté r, sera défini comme suit : r = Nombre d'unifications/Nombre de marquages. Il permet de mesurer le nombre de passages nécessaire par section de code pour atteindre un point fixe. - L'heuristique"Random" (aléatoire). Cette heuristique peut être utilisée à titre de référence. Elle permet d'obtenir de bons résultats sur un jeu d'évaluation. Elle consiste à choisir au hasard le prochain marquage à vérifier parmi les types marqués. - L'heuristique"Next" (prochain). L'heuristique"Next"est relativement simple. Elle consiste à élire le marquage qui est le successeur du marquage qui vient d'être vérifié. On effectue ainsi le nombre nécessaire de passes de vérification linéaire. - L'heuristique"Lazy" (recherche de simplicité). L'heuristique"Lazy"est optimale en termes d'efficacité et de simplicié. Elle consiste à prendre comme marquage à vérifier le premier marqué. En général, les programmes JavaCard sont issus de la conversion de code Java compilé à l'aide du kit de développement Java, connu par le terme anglosaxon JDK de"Java Development Kit". Or celui-ci génère du code assez linéaire. Les points d'arrêts des programmes se trouvent assez souvent à la fin du byte code. On exploite ce constat en utilisant donc systématiquement le premier marquage comme étant à vérifier. Ainsi, on s'acharne sur le début du programme pour ne plus y revenir ensuite. L'heuristique "Lazy"permet d'obtenir une valeur de 1,3 pour le ratio r définit plus haut. Des heuristiques plus fines peuvent être mises en place, notamment en utilisant le graphe de flot de contrôle du programme vérifié. Le graphe peut notamment servir pour piloter les caches logiciels. Caches optimaux. L'utilisation judicieuse de caches logiciels permet de gagner encore un facteur d'accélération, surtout lors de la vérification de programmes (tels que des applets) relativement importants, car ils diminuent notablement le nombre d'écritures en EEPROM. Ils accélèrent aussi considérablement la vérification des petits programmes en ne faisant aucune écriture en EEPROM. Pour faire l'inférence de type, il est nécessaire de détecter les points de branchement d'un programme. Ce faisant, il est facile et"gratuit"de construire le graphe de flot de contrôle de celui-ci. On rappelle que certaines méthodes nécessitent plus de 4Ko de mémoire pour être vérifiées, et qu'une carte à puce évoluée dans l'état de'la technique dispose de 8Ko de RAM). Il est donc envisageable de vérifier les applications utilisant de telles méthodes. Dans la mise en oeuvre, on met en place un cache logiciel entre l'EEPROM et la RAM pour manipuler au mieux les"frames" de type. Cela implique une phase d'élection des données à supprimer (déstocker) du cache en cours de vérification, et donc une politique de gestion du cache. A cette fin, on peut utiliser des politiques classiques, comme par exemple du genre LRU (élimination des données utilisées le moins récemment, de l'anglais" least recently used"). Cependant, on peut avantageusement exploiter le fait que puisqu'on dispose du graphe de flot de contrôle, il est facile de déterminer les données présentes dans le cache qui sont pertinentes et qui doivent donc être conservées. En connaissant le type de l'heuristique de sélection du marquage à vérifier, on peut facilement évaluer la pertinence d'une donnée du cache selon un mécanisme donné. A titre d'exemple, on peut se référer à un mécanisme décrit dans l'article de Chi-Keung Luk et Todd C. Mowry"Compiler-based prefetching for recursive data structures", ACM SIGPLAN Notices, 31 (9) : 222- 233,1996. L'utilisation du graphe de flot de contrôle pour déterminer la politique de gestion des caches sera montrée par l'exemple suivant. Le graphe de flot de contrôle est fourni conformément à l'exemple illustré par référence à la figure 6. Le tableau II indique une trace d'exécution possible de l'inférence de type pour cet exemple. Tableau II : trace d'exécution possible de l'inférence de type pour l'exemple de la figure 6. 1. Chargement du contexte courant avec celui du début de programme 2. Unification avec le labell 3. Unification avec le label2 4. Sélection de labell 5. Unification avec le label2 6. Sélection de label2 7. Unification avec le label3 8. Unification avec le label2 9. Sélection de label2 10. Unification avec le label3 11. Unification avec le label2 12. Sélection de label3 13. Fin de la vérification On prend comme hypothèse que l'on utilise l'heuristique "Lazy"pour la sélection du prochain marquage (label) à vérifier, et que l'on tente de faire les unifications dans la RAM 20 (i. e. dans le cache). La trace de vérification donnée à la figure 6 se réalise comme suit, pour le cas d'un cache initialement vide et disposant de deux cellules : - on commence par charger le descripteur courant à l'aide des informations de typage associées au début du programme 42 ; - on effectue la vérification de la première section de code et on atteint un branchement conditionnel 44 à destination du marquage "labell" 46. On doit donc unifier la"frame"de type du marquage "label111 avec celle courante. On chargera donc les informations de typage du marquage "label1" dans le cache ; on doit ensuite unifier 48 avec le marquage "label2"50 lors de la rencontre avec le deuxième branchement 48. Disposant d'une cellule de cache, on y charge les informations du marquage"label2" ; - on choisit le marquage IIlabel111 pour vérifier la section de code correspondante, conformément à l'utilisation de l'heuristique"Lazy" ; - on doit unifier avec le marquage" labe1211 ; or celui-ci est dans le cache. L'unification se fait donc en RAM ; - on sélectionne prochain marquage, soit"label2" ; on arrive au saut conditionnel 52 ayant comme destination le marquage"label3"54. On ne dispose pas des informations de typage correspondantes dans le cache. Celui-ci est plein (il contient les informations de typåge des marquages"labell"et"label2"). On doit donc élire un de ces marquages pour libérer une cellule du cache y charger les informations de typage du marquage"label3". En faisant référence au graphe de flot de contrôle, on constate que seuls sont accessibles les marquages"label2" et"label3"depuis la section de code courante (on peut regarder un niveau plus loin dans le graphe : depuis le marquage"labe12"lesmarquages"labe12"et"labe13"sont accessibles ; depuis le marquage"label3", aucun marquage n'est accessible. ). Ainsi, on peut éliminer le marquage "labell"du cache et mettre à jour sa copie en EEPROM ; - la vérification se poursuit sans encombre jusqu'à la fin du programme 56. Sans utiliser de cache, il aurait été nécessaire dans cet exemple de réaliser sept unifications en EEPROM (i. e. sept écritures en EEPROM). Avec le cache, on met à jour une et une seule fois les informations de typage du marquage"labell"en EEPROM. De plus, cette mise à jour n'est pas nécessaire car le marquage"labell"n'est plus accessible par aucun chemin du programme à ce moment de la vérification. Ses informations de typage ne sont donc plus nécessaires. On illustre ici les possibilités de l'utilisation du graphe de flot de contrôle des programmes à vérifier afin de piloter au mieux le cache. Ce faisant on se rapproche d'un cache optimal (i. e. la bonne information au bon moment dans le cache). Comme la construction du graphe de flot de contrôle est peu coûteuse dans le cas d'espèce, on peut s'en servir non seulement pour le pilotage du cache logiciel, mais aussi pour l'amélioration de l'heuristique de sélection du label à vérifier. Le mode de réalisation préféré permet d'obtenir des systèmes de vérification simples qui ouvre la possibilité de la mise en oeuvre d'un vérifieur entièrement embarqué dans une carte à microprocesseur ou autre dispositif à mémoire restreinte. Il apparaîtra à l'homme du métier que l'invention permet de nombreuses variantes et équivalences selon les conditions et critères de son exploitation, tant au niveau logique, matériel, ou d'environnement. REVENDICATIONS 1. Procédé de vérification d'un programme (4) lors de sa phase d'intégration dans un dispositif électronique (2), le programme étant organisé selon des types liés par des relations de filiation, chaque type étant identifié par un code respectif, ledit procédé comportant une phase d'unification de types visant à déterminer leur ascendant commun le plus proche, caractérisé en ce que ledit code est décrit sous forme de motif de bits selon un formalisme qui exprime la filiation du type auquel il est associé, et en ce que ladite phase d'unification comprend une combinaison logique de motifs attribués aux types à unifier, produisant le motif du type qui est leur ascendant commun le plus proche. 2. Procédé selon la revendication 1, caractérisé en ce que, pour tout type ayant un ascendant, son motif contient au moins un bit qui est identique en valeur et en position à un bit correspondant du motif de son ascendant direct. 3. Procédé selon l'une quelconque des revendications 1 ou 2, caractérisé en ce que le motif d'un type donné comporte un nombre de bits à un état logique prédéterminé qui est fonction de l'éloignement dudit type de l'ascendant commun. 4. Procédé selon l'une quelconque des revendications 1 à 3 caractérisé en ce que l'on utilise une mémoire (22) sujette à une usure par des transitions d'état logique usantes, pour stocker au moins un motif destiné à être soumis à une combinaison logique ou qui résulte d'une combinaison logique dans ladite phase d'unification. 5. Procédé selon la revendication 4, caractérisé en ce que le formalisme d'attribution de motif établit une prépondérance d'un état logique dans l'ensemble des motifs qui minimise le nombre de transitions usantes nécessaires pour réaliser le stockage des motifs dans ladite mémoire (22). 6. Procédé selon la revendication 4 ou 5, caractérisé en ce que l'on initialise les cellules de stockage de ladite mémoire (22) à l'état logique à partir duquel la transition est dans le sens opposé au sens de la transition usante. 7. Procédé selon l'une quelconque des revendications 4 à 6, caractérisé en ce que ladite transition usante étant dans le sens de l'état logique 0 à l'état logique 1, la combinaison logique consiste à réaliser une opération logique du type ET entre chaque paire de bits de même rang des motifs combinés. 8. Procédé selon l'une quelconque des revendications 4 à 6, caractérisé en ce que ladite transition usante étant dans le sens de l'état logique 1 à l'état logique 0, la combinaison logique consiste à réaliser une opération logique du type OU entre chaque paire de bits de même rang des motifs combinés. 9. Procédé selon l'une quelconque des revendications 1 à 8, mis en oeuvre pour un programme qui se présente sous forme d'un ensemble de sections de code, chaque section étant identifiée par un marquage qui correspond à une instruction atteignable depuis un branchement, caractérisé en ce que l'on procède à ladite vérification par sections dans un ordre de sections donné selon une heuristique déterminée. 10. Procédé selon la revendication 9, caractérisé en ce que l'ordre des sections à vérifier est l'ordre de succession d'une section vérifié suivi par sa section qui lui est son successeur. 11. Procédé selon la revendication 9, caractérisé en ce que l'ordre des sections à vérifier est donné par la première section marquée. 12. Procédé selon l'une quelconque des revendications 1 à 11, caractérisé en ce que l'on met en oeuvre une mémoire volatile (20) en tant que cache pour stocker des motifs candidats à l'étape de combinaison logique, et en ce que lron choisit lesdits motifs candidats de manière dynamique et par prévision en fonction de points de branchement dans le programme à vérifier (4). 13. Procédé selon la revendication 12, caractérisé en ce que l'on sélectionne pour stockage dans ladite mémoire volatile (20) ceux des motifs qui correspondent à des types susceptibles de faire l'objet d'une unification à une échéance donnée, et en ce que l'on réalise ladite sélection des motifs à stocker par référence à un graphe de flot de contrôle du programme à vérifier (4). 14. Procédé selon la revendication 12 ou 13, caractérisé en ce que l'on sélectionne pour déstockage de ladite mémoire volatile (20) ceux des motifs qui correspondent à des types plus susceptibles de faire l'objet d'une unification à une échéance donnée, et en ce que l'on réalise ladite sélection des motifs à déstocker par référence à un graphe de flot de contrôle du programme à vérifier. 15. Procédé selon la revendication 13 ou 14, caractérisé en ce que l'on établit le graphe de flot de contrôle à partir desdits marquages préalablement déterminés et des instructions qui branchent vers ces marquages. 16. Procédé selon l'une quelconque des revendications 1 à 15, caractérisé en ce que l'on réalise ladite vérification dans un dispositif électronique de type carte à puce (2). 17. Dispositif (6) de vérification d'un programme (4) lors de sa phase d'intégration dans un dispositif électronique (2), le programme étant organisé selon des types liés par des relations de filiation, chaque type étant identifié par un code respectif, ledit dispositif de vérification comportant des moyens d'unification de types pour déterminer leur ascendant commun le plus proche, caractérisé en ce qu'il comprend des moyens d'identification de filiation de types, l'identification d'un type étant réalisée sur la base d'un motif de bits qui constitue son code selon un formalisme déterminé, et en ce que lesdits moyens d'unification comprennent des moyens de combinaison logique de motifs attribués aux types à unifier, produisant le motif du type qui est leur ascendant commun le plus proche. 18. Dispositif selon la revendication 17, apte à exécuter le procédé selon l'une quelconque des revendications 1 à 15. 19. Dispositif électronique (2) permettant de charger et d'exécuter un programme organisé selon des types liés par des relations de filiation, chaque type étant identifié par un code respectif, caractérisé en ce qu'il intègre un dispositif de vérification selon la revendication 17 ou 18. 20. Dispositif selon la revendication 19, caractérisé en ce qu'il est réalisé sous forme de carte à puce (2).