FR 2817363 A1 20020531 FR 0015306 A 20001124 Vérification formelle notamment d'une machine virtuelle sécurisée La présente invention concerne la vérification d'un programme initialement écrit en un langage de haut niveau, lors de sa réalisation dans un milieu sécurisé et ainsi liée à des mécanismes de sécurité contrôlant des états possibles du programme. Par exemple, le programme est un interpréteur ou une machine virtuelle implantée dans une carte à puce ou un terminal radiotéléphonique portable. Dans les applications globales liées au réseau Internet, les éditeurs d'outils informatiques, particulièrement de navigateurs, ont été contraints à adopter un langage commun de haut niveau, tel que le langage orienté objet, appelé Java (marque déposée), pour la programmation répartie de communications entre des petits programmes locaux et des serveurs. La recherche de fonctionnalités, notamment de sécurité, de plus en plus nombreuses et souples pour des objets nomades, tels que radiotéléphones mobiles, cartes de paiement et assistants numériques personnels, a conduit à doter les microcontrôleurs inclus dans des cartes à puce et moyens de traitement de données analogues, de langages relativement complets tels que le langage Java. L'universalité, dans la variété des dispositifs connectés au plus grand des réseaux comme dans celles d'appareils de plus en plus petits, issus d'une multiplicité innombrable de constructeurs, d'architectures matérielles différentes, de systèmes informatiques divers, dans des contraintes très diverses, est un obstacle à un langage unique, interprété sans ambiguïté. Pour ces raisons a été définie une machine virtuelle capable d'exécuter tous les programmes écrits dans le langage Java. Les fournisseurs de matériel notamment de cartes à puce, ou les éditeurs de logiciels notamment de navigateurs Web, ont dû alors développer sur les outils qu'ils fournissent, un logiciel capable de réaliser les fonctions de cette machine virtuelle, appelée habituellement "machine virtuelle Java"JVM, propre à chaque outil logiciel ou matériel. A cause de la faible taille de la mémoire dans les cartes à puce, ce logiciel alors appelé"JavaCard"a été"allégé". Contrairement aux processeurs"nus", dont l'objectif est avant tout la performance de calcul ou de faible consommation, la machine virtuelle Java a été conçue pour fournir aux développeurs des fonctions de sécurité adaptées à des utilisations sensibles notamment dans le domaine de la monétique et de la sécurité. Par contre, l'exécution d'un programme Java n'est effectivement totalement sûre que si la machine JVM a été correctement réalisée pour toutes les fonctions critiques de sécurité. Les normes ITSEC (Information Technology Security Evaluation Criteria) de la Commission des Communautés Européennes conseillent pour l'analyse de la sécurité de systèmes informatiques : - de fixer des objectifs de sécurité ; - d'en déduire une politique de sécurité dont l'application permettra d'atteindre les objectifs de sécurité ; de définir des fonctions de sécurité dont l'exécution garantit que la politique de sécurité est respectée ; - de concevoir des mécanismes de sécurité qui sont la réalisation matérielle ou logicielle des fonctions de sécurité. Il est donc important pour les clientsutilisateurs finaux que la machine JVM soit conforme à la politique de sécurité que la nature de l'application par exemple dans le domaine de la monétique ou de la radiotéléphonie mobile, impose aux opérateurs, tels que banques ou opérateurs de télécommunication. Dans ce contexte, un fournisseur de la machine JVM supporté par un moyen de traitement de données a intérêt à démontrer que sa réalisation est conforme à une politique de sécurité que son client, opérateur ou banque, lui aura contractuellement définie, ou à celle que la loi ou les règlements imposent. Il faudra donc vérifier que telle ou telle faille de sécurité n'existe pas, quel que soit le programme Java exécuté par la machine JVM, et quel que soit l'environnement du moyen de traitement de données, tel qu'un processeur, qui exécute la machine JVM. Il s'agit donc d'un processus complexe et délicat, avec des implications économiques fortes. Une telle vérification repose sur des techniques formelles qui sont un ensemble d'outils, logiciels ou méthodologiques, garantissant de manière certaine des propriétés de logiciels. Au cours du processus de développement d'un programme, par exemple un interpréteur, en l'occurrence une machine virtuelle, ces techniques formelles mettent en oeuvre des démarches mathématiques qui assurent ces garanties. De nombreuses techniques sont disponibles, chacune ayant ses spécificités. Pour des raisons d'efficacité, certains des contrôles effectués par la machine virtuelle sont statiques, comme l'analyse sémantique d'un programme avant son exécution. Comme les algorithmes mis en jeu sont complexes, il est difficile de concevoir et d'implanter, c'est-à-dire réaliser une machine virtuelle. La vérification qu'une machine virtuelle Java respecte bien une politique de sécurité recherchée nécessite de passer, pour certaines propriétés, par l'utilisation conjointe de plusieurs techniques, formalismes, langages, qui structurent le développement. Plus particulièrement, l'invention concerne un procédé de vérification qui garantit que la spécification d'une machine virtuelle est correcte et non ambiguë, et que son implantation est sûre. Il s'agit de vérifier formellement la correction des contrôles statiques et de leur implantation. L'invention a pour objectif d'optimiser l'implantation d'un interpréteur de programmes en langage de haut niveau, tel qu'une machine virtuelle dont les mécanismes de sécurité, comportant par exemple des contrôles statiques, ont été vérifiés formellement en conformité avec une spécification de fonction de sécurité. A cette fin, un procédé pour vérifier et optimiser un programme initialement écrit en un langage de haut niveau et implanté dans un moyen de traitement de données, au cours duquel des contrôles sur des états du programme explorés par des mécanismes de sécurité prouvent formellement qu'un état interdit défini en langage de haut niveau est inatteignable par le programme, est caractérisé par une suppression de chemins d'exécution conduisant à l'état interdit dans le programme, de manière à transformer le programme en un programme équivalent écrit dans un langage de bas niveau. Ce dernier fournit alors les mêmes garanties de sécurité que le programme en langage de haut niveau. L'implantation en langage de haut niveau est ainsi transformée en une implantation optimisée dans un langage de bas niveau par application manuelle ou automatique de règles de transformation locales sur le code source de haut niveau. La simplicité et le caractère systématique de ces règles garantit semiformellement ou formellement la correction de l'implantation optimisée en langage de bas niveau par rapport à l'implantation de haut niveau, et par transitivité, par rapport à des spécifications des mécanismes de sécurité. Selon d'autres caractéristiques de l'invention, l'optimisation du programme, tel qu'interpréteur ou machine virtuelle, peut comprendre, en outre, un remplacement d'entiers non bornés du langage de haut niveau, par des entiers bornés du langage de bas niveau et/ou un remplacement de paramètres et d'appels de fonction en langage de haut niveau par des données allouées statiquement et des structures de contrôles impératives en langage de bas niveau. Le procédé de vérification selon l'invention peut être appliqué à un programme du type machine virtuelle connue comportant des données entières, des tableaux, des pointeurs sur les tableaux, des variables locales réutilisables ou registres, des exceptions, des sous-routines, ou une pile d'opérandes. Le jeu d'instructions de la machine virtuelle comporte des opérations arithmétiques, d'accès aux variables, d'accès aux tableaux, de manipulation de la pile, de test, de saut, d'appel et retour de sous-routines, de levée d'exceptions. Les contrôles statiques garantissent le respect de contraintes de typage des opérandes, de contraintes sur le flot de contrôle, de contraintes de non-débordement de la pile d'opérandes, et de contraintes sur l'utilisation de variables locales. D'autres caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture de la description suivante de plusieurs réalisations préférées de l'invention en référence aux dessins annexés correspondants dans lesquels : - la figure 1 est un algorithme d'interpréteur en langage de haut niveau avec contrôles dynamiques ; la figure 2 est un algorithme optimisé d'interpréteur en langage de bas niveau ; et la figure 3 illustre schématiquement un procédé de vérification formelle de machine virtuelle aboutissant à une optimisation selon l'invention. A titre d'exemple, on se réfère à un programme de type interpréteur constituant le moteur d'exécution d'une machine virtuelle implantée dans un moyen de traitement de données, dite plate-forme d'exécution, tel que le microcontrôleur d'un terminal radiotéléphonique mobile, ou d'une carte à puce telle qu'une carte de paiement ou une carte d'identité SIM (Subscriber Identity Module). L'interpréteur implémenté automatiquement à partir de spécifications formelles et écrit en langage source de haut niveau pour exécuter une instruction comme montré à la figure 1, est à optimiser selon l'invention en un langage de bas niveau montré à la figure 2. Par exemple, le langage source de haut niveau est un langage de la famille ML, tel que le langage CAML développé par l'INRIA en France, et le langage de bas niveau est le langage impératif C. L'implantation de l'interpréteur (interp) en langage de haut niveau est obtenue par un procédé automatique à partir de spécifications formelles écrites dans un langage à base de logique mathématique, ce qui assure sa conformité à ces spécifications. Elle comporte la structure de contrôle suivante : let interp m st = match (nth st. pc m. code) with ) None- > Interdit /Some Illegal- > Interdit ISome Iadd- > (match st. stack with ICons (Vint x, Cons (Vint y, stack'))- > Continuer [...] Interdit [...] Cette structure de contrôle assure les fonctions suivantes en référence aux étapes Hl à H7 de la figure 1. A l'étape Hl, lors d'une tentative de lecture de l'instruction courante I désignée par le compteur ordinal (st. pc) dans un état (st) pour un programme (m. code), la valeur de l'adresse d'exécution correspondant à l'instruction courante est contrôlée (match (nth st. pc m. code) ). Si l'adresse est invalidée puisqu'elle n'appartient pas au programme (None) ou désigne une instruction incorrecte (Some Illegal), le contrôle passe à un état"interdit"à l'étape H7 où il est arrêté. Sinon, à l'étape suivante H2, l'instruction courante I pointée par l'adresse d'exécution validée est contrôlée. Par exemple, l'instruction validée à l'étape H2 peut être l'instruction d'addition (Iadd). Dans ce cas, aux étapes suivantes H3 et H4 qui peuvent être réunies, les opérandes auxquelles l'instruction d'addition est appliquée sont contrôlées. En l'occurrence, si le sommet de la pile d'opérandes contient au moins deux valeurs (Cons valeurl (Cons valeur2 stack') ) et que ces deux valeurs sont de type entier (Vint), c'est-à-dire si l'addition est cohérente, l'exécution se poursuit normalement (Continuer), en dépilant les valeurs à l'étape H5, en empilant leur somme à l'étape H6, et en incrémentant le compteur ordinal et appelant récursivement l'interpréteur (interp m st') sur un nouvel état (st') de manière à revenir à l'étape Hl. Par contre, si l'instruction courante est Iadd alors que les opérandes ne sont pas en nombre suffisant ou ne sont pas du bon type, le contrôle passe à l'état interdit et est arrêté à l'étape H7. Selon une autre variante également montrée à la figure 1, lorsque l'instruction courante est l'instruction d'empilement d'une valeur constante C, la structure de contrôle comporte les étapes H8 et H9. L'étape H8 contrôle la hauteur de la pile d'opérandes et, si la pile n'est pas pleine, l'étape H9 empile la valeur C au sommet de la pile. Par contre, si la pile est pleine, la structure de contrôle va à l'état interdit à l'étape H7. Dans la figure 1, la structure de contrôle comporte trois chemins d'exécution issus des étapes Hl, H2 et (H3, H4), ou bien des étapes Hl, H2 et H8, qui correspondent à des échecs de contrôles et qui aboutissent à l'état interdit à l'étape H7. En référence maintenant à la figure 2, l'interpréteur en langage de bas niveau C après optimisation selon l'invention appliquée à l'interpréteur en langage de haut niveau ML, ne comporte plus que des étapes de processus Bl, B2, B5, B6 et B9 correspondant respectivement aux étapes Hl, H2, H5, H6 et H9, sans les étapes de contrôle dynamique H3-H4 et H8 et surtout sans l'étape d'état interdit H7. La structure de contrôle optimisée en langage de bas niveau C s'écrit : switch (code [pc]) { case IADD : stack [top+l] +=stack [top] ; ++top ; ++pc ; break ; [...] } où l'instruction d'analyse conditionnelle (switch) est lue à l'étape Bl pour décoder l'instruction suivante (case) associée à la valeur (pc) à l'étape B2 et désignant l'instruction d'addition (IADD) de deux valeurs entières d'adresses (top+1) et (top) à dépiler à l'étape B5. Ce code source de bas niveau est à la fois performant puisqu'il ne comporte pas de contrôles dynamiques inutiles et est sûr puisqu'il est directement dérivé d'un code source dont la correction a été prouvée formellement selon l'invention, comme on le verra ci-après. Comparativement à la figure 1, les chemins d'exécution aboutissant à l'état interdit de l'étape H7 sont supprimés du code source de l'interpréteur dans la figure 2, ce qui correspond aux optimisations suivantes : suppression de contrôle sur l'adresse d'exécution à l'étape Hl correspondant à l'étape Bl ; suppression du contrôle et du type des arguments auxquels l'opération d'addition est appliquée aux étapes H3 et H4 ; simplification de la représentation des données en machine, leur type n'étant plus représenté. Ces optimisations appliquées au code source de haut niveau ci-dessus ML conduisent, par l'application de transformations simples et locales, soit manuellement soit par l'utilisation d'un outil automatique, à un code source optimisé dans un langage de bas niveau, en l'occurrence le langage C. Le procédé de l'invention comporte l'obtention d'une preuve formelle de l'efficacité des mécanismes de contrôle statique de la machine virtuelle. En d'autres termes, si ces mécanismes ont autorisé l'exécution d'un programme donné (code), alors l'exécution de ce programme par l'interpréteur (interp) n'aboutira jamais à l'état interdit. Cette garantie est obtenue au cours des étapes suivantes El à E5 montrées à la figure 3. A l'étape El, un langage logique de spécification de la machine virtuelle qui est une variante de la théorie des types, permet de décrire et de raisonner sur des structures de données et des algorithmes dans un programme. Des mécanismes de sécurité prédéterminés, tels que des contrôles statiques (instruction ou adresse d'exécution incorrecte ; étape Hl ou H2), sont spécifiés comme un problème d'analyse de flot des états, ou variantes, possibles d'exécution du programme réalisant l'interpréteur, d'une manière analogue à l'analyse des comportements d'un objet symbolique. Des fonctions de sécurité comportent typiquement des contrôles de typage, d'accès aux données, d'accès aux opérations, et d'accès aux ressources. Si certains états atteignables par l'exécution du programme depuis des états initiaux de ceux-ci deviennent dangereux, ces états sont ramenés par des transitions à un état interdit (étape H7), et les autres états sont réputés sûrs. A l'étape E2, parmi les mécanismes de sécurité prédéterminés, des mécanismes de sécurité sont obtenus par reformulation du problème d'analyse de flot en la combinaison d'un problème d'abstraction et d'un problème d'exploration exhaustive d'un système à états et transitions. S'il existe un nombre infini d'états d'exécution du programme, ce nombre infini est ramené à un nombre fini d'états abstraits atteignables du programme qui sont explorés par les contrôles statiques. Les contrôles statiques vérifient que l'état abstrait"interdit"est inatteignable par le programme ainsi défini de manière à préserver des propriétés de sécurité du programme. L'étape E3 consiste à passer des étapes El et E2 à une étape E4, c'est-à-dire à spécifier l'interpréteur de la machine virtuelle pour qu'il comporte des assertions, par exemple les validations d'adresses ou d'instructions aux étapes Hl, H2 et les contrôles à l'étape de contrôle d'opérandes entiers H3-H4. Ces assertions expriment une politique de sécurité, ainsi qu'un état dit interdit (étape H7) qui est atteint chaque fois qu'une assertion échoue. L'interpréteur et ses mécanismes de sécurité sont implantés en langage de haut niveau de type ML, par exemple le langage CAML selon l'exemple ci-dessus et la figure 1, ou le langage SML, à partir de spécifications de la machine virtuelle et à l'aide d'un outil à base de logique. Cette implantation à l'étape E4 comporte des contrôles dynamiques correspondant aux assertions, lesquels contrôles dynamiques ramènent les états dangereux du programme à l'état interdit. Au cours de l'étape E4, il est prouvé à l'aide de l'outil à base de logique que si les mécanismes ont autorisé l'exécution d'un programme, alors son exécution par l'interpréteur n'aboutira jamais à l'état interdit. Puis selon l'invention, l'étape E5 optimise l'interpréteur de la machine virtuelle par application de trois transformations locales suivantes sur le code source en langage ML. Ces transformations sont réalisées manuellement par un programmeur, bien qu'en variante au moins certaines d'entre elles peuvent être réalisées automatiquement par des outils de programmation appropriés. E51) Une première transformation est une suppression des chemins d'exécution, par exemple entre les étapes Hl, H2, H3, H4 et l'étape H7, qui conduisent de façon certaine à l'état interdit. Cette suppression est garantie par les contrôles statiques qui ont assuré qu'aucun état atteignable par l'interpréteur n'est dangereux. En outre, les contrôles statiques justifient la simplification de la représentation des données en machine, la suppression de tests de débordement d'indices, et la suppression de tests sur le compteur ordinal d'instructions, comme montré par la comparaison des figures 1 et 2. E52) Une deuxième transformation est un remplacement des types entiers infinis, c'est-à-dire non bornés, du langage de haut niveau par des types entiers bornés, c'est-à-dire des entiers binaires finis, dans le langage de bas niveau C. Ce remplacement est effectué selon une première variante, lorsqu'il a été prouvé formellement que des bornes prédéterminées ne peuvent pas être atteintes par des variables entières du langage de haut niveau traitées par l'interpréteur. Selon une deuxième variante, ce remplacement est effectué lorsque les opérations appliquées sur ces variables entières sont telles que les bornes ne peuvent pas être atteintes par les variables entières en langage de haut niveau avant l'expiration d'une durée prédéterminée inférieure à la durée de vie de la machine virtuelle ; par exemple cette deuxième variante est appliquée lorsque les seules opérations sont des incrémentations et des décrémentations relatives à une valeur initiale faible. E53) Une troisième transformation est un remplacement des appels de fonction dits"récursifs terminaux" (en anglais"tail-recursive") et de leurs arguments en langage de haut niveau par des structures de contrôles impératives en langage de bas niveau et des données allouées statiquement. Par exemple, les appels récursifs terminaux de l'interpréteur (interp) sont remplacés par une boucle impérative, et son argument (st) représentant l'état du programme est remplacé par des données allouées statiquement, dont entre autres la pile d'opérandes (stack) et le compteur ordinal (pc) dans l'exemple en langage de bas niveau. Le domaine applicatif du procédé de vérification de l'invention concerne notamment des cartes à puce monétiques ou pour accès sécuritaire, et tout particulièrement des cartes à puce téléchargeables dont le code exécuté n'est pas connu a priori. Les cartes à puce peuvent être incluses dans des dispositifs dont la programmation est accessible à des parties tierces, notamment pour des applications de radiotéléphonie mobile, et tout particulièrement des applications téléphoniques Wap mêlant les deux aspects internet et mobile. REVENDICATIONS 1-Procédé pour vérifier et optimiser un programme initialement écrit en un langage de haut niveau et implanté dans un moyen de traitement de données, au cours duquel des contrôles (Hl, H2, H3H4) sur des états du programme explorés (E1-E2) par des mécanismes de sécurité prouvent formellement (E4) qu'un état interdit (H7) défini en langage de haut niveau est inatteignable par le programme, caractérisé par une suppression de chemins d'exécution (H1-H7, H2-H7, H3-H4-H7) conduisant à l'état interdit dans le programme, de manière à transformer le programme en un programme équivalent dans un langage de bas niveau. 2-Procédé conforme à la revendication 1, comprenant un remplacement d'entiers non bornés du langage de haut niveau, par des entiers bornés du langage de bas niveau. 3-Procédé conforme à la revendication 2, selon lequel ledit remplacement est effectué lorsqu'il a été prouvé formellement que des bornes prédéterminées des entiers du langage de haut niveau ne peuvent pas être atteintes. 4-Procédé conforme à la revendication 2, selon lequel ledit remplacement est effectué lorsque des bornes prédéterminées ne peuvent pas être atteintes par les entiers en langage de haut niveau avant l'expiration d'une durée prédéterminée. 5-Procédé conforme à l'une quelconque des revendications 1 à 4, comprenant un remplacement de paramètres et d'appels de fonction en langage de haut niveau par des données allouées statiquement et des structures de contrôles impératives en langage de bas niveau.