EP1433065A1 - Procede et dispositif de verificateur de code optimise - Google Patents

Procede et dispositif de verificateur de code optimise

Info

Publication number
EP1433065A1
EP1433065A1 EP02783198A EP02783198A EP1433065A1 EP 1433065 A1 EP1433065 A1 EP 1433065A1 EP 02783198 A EP02783198 A EP 02783198A EP 02783198 A EP02783198 A EP 02783198A EP 1433065 A1 EP1433065 A1 EP 1433065A1
Authority
EP
European Patent Office
Prior art keywords
type
patterns
program
types
code
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP02783198A
Other languages
German (de)
English (en)
Inventor
Gilles Grimaud
Damien Deville
Antoine Requet
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Gemplus SA
Original Assignee
Gemplus Card International SA
Gemplus SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Gemplus Card International SA, Gemplus SA filed Critical Gemplus Card International SA
Publication of EP1433065A1 publication Critical patent/EP1433065A1/fr
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/36—Prevention of errors by analysis, debugging or testing of software
    • G06F11/3604—Analysis of software for verifying properties of programs

Definitions

  • the invention relates to the verification of program code loaded in an electronic device, for example - but not exclusively - a device with a limited memory such as a smart card or the like. More particularly, the invention is aimed at verifying programs which are organized according to types linked by parentage relationships, in accordance with current programming techniques in high-level language, and is based on a verification technique which implements a type unification process aimed at determining their common ascendancy.
  • the goal is to ensure that the loaded program is consistent with the specificities expected at the level of the device that integrates it.
  • an auditor is called upon, whose tasks are typically: to prohibit from: manufacturing and modifying pointers from explicit values;
  • program 4 Once program 4 has been loaded into the map, it is necessary to carry out an integration phase in order to make it operational. Verification takes place during this phase, and is used to decide whether the card should integrate the program or, on the contrary, reject it.
  • This task is carried out on the basis of an analysis of the byte code, or pseudocode, which will be designated below by the consecrated term of "byte code". It is performed by a byte code 6 checker, which constitutes a functional element of the virtual machine located upstream of the byte code 8 interpreter.
  • the verifier 6 determines that the structure of the loaded program 4 is functionally integrated and compatible with what is expected at the level of the card 2. If the verifier validates the program, it transmits it to the byte interpreter code 8 in seen from its execution. Otherwise, either a fault detection likely to jeopardize the card, the verifier 6 controls a process (symbol identified by the number 10) intended to reject the loaded program 4.
  • the implementation of such a verification process substantially demands the memory resources of the device in which the verification is carried out.
  • the iterative nature of the verification requires numerous updates of the result data, and therefore of transitions of logical states in the storage cells.
  • the memory space to be dedicated to the verification process can be considerable for a device with limited memory.
  • a safety block 16 - a safety block 16; - a frozen memory 18, accessible in read only (of the type known as ROM (read only memory) in English terminology);
  • a volatile working memory 20 (of the so-called RAM (radom access memory) or possibly FlashRAM type in English terminology);
  • EEPROM electrically erasable programmable read only memory
  • the micro-module 12 of the card 2 is better provided with persistent memory capacity 22 than with volatile memory 20
  • persistent memories have a very slow registration time relative to a volatile memory (by a factor ranging from 1000 to 10000), which greatly penalizes the "card" programmer.
  • the persistent memory 22 raises a reliability problem linked to its lifetime. Indeed, depending on the technology used, the logical transitions of the states of their memory cells during a writing cause wear which strongly depends on the direction of the transition; we then speak of "stressful" transitions, or operations. With each stressful writing of a value in persistent memory, there is an increasing probability that the memory cell used has a failure. In this case, the value that can be read later will not correspond to what has been written. For example, the founders guarantee a limited number of writes (between 10 4 and 10 6 ) for a persistent memory in EEPROM technology.
  • a persistent memory of type EEPROM has four operations:
  • - read to read a previously stored value
  • - erasure which consists in carrying out a logical state transition from 0 to 1, the storage cells being by default at state 1;
  • the erase operation is of the stressful type, and can lead to a failure of the associated memory cell.
  • the communication model between the smart card 2 and the terminal with which it communicates is standardized.
  • the card is considered as a server controlled by the terminal. Operation is carried out without any collision.
  • Communication is of the "half-duplex" type (communication in one direction only allowed at a time). The card does not send an answer to the terminal until after the terminal has asked it a question.
  • the “JavaCard” system we are based on an architecture in four layers, as represented in FIG. 3.
  • the highest layer contains the user applications, called “embedded” 28 which rely on libraries.
  • Java 30 dedicated to the card 2.
  • These libraries are a subset of the Java APIs (from the English “Application Program Interface”, or application program interface) constitute the second layer of the “JavaCard” system.
  • the applications code is expressed in a byte code which is interpreted by the virtual machine 32.
  • the latter executes the application programs and is based on a basic operating system managing the writes in memory, the input-output, calls to cryptographic routines ensuring security, and finally support for the various ISO standards.
  • the two lowest layers 32 and 34 are stored in the fixed memory ROM 18 of the card 2.
  • Each method has its own execution stack containing the variables and parameters that it manipulates.
  • the virtual machine uses registers to store the so-called local variables (variables allocated during the method as well as the parameters thereof).
  • Security in a virtual machine 32 is an important problem, because it is a support for the execution of mobile code, the latter being able to come from various and uncertain sources. Thus, the virtual machine 32 may be required to execute a code which jeopardizes the reliability of the system or of other components.
  • the defensive virtual machine is said to be "suspicious". During execution, it checks that each byte code element is not being used improperly (for example, it checks that each byte code has the right number of parameters on the execution stack, or also that each call to method is valid). This solution has the defect of severely straining the performance of the virtual machine.
  • the Java specification defines a security model based on the analysis of the byte code when it is loaded. The purpose of this analysis is to prove the safety of the loaded program; otherwise, it is rejected. The smart card has capacities deemed too limited to carry out this analysis. This is why various solutions have been proposed.
  • an external pre-processing is carried out enabling the code of additional information or proof to be provided allowing the card to verify the code during loading.
  • Other approaches aim to integrate a byte code checker into the resources of the device with restricted memory.
  • WO-A-01 14958 it has been proposed in patent document WO-A-01 14958 to make an "off-card" modification of the program code, so that the latter maintains its original meaning but becomes easier to verify. This simplifies the verification process by allowing one-pass verification.
  • it has the disadvantage of requiring modifications to the program code, and excludes the implementation of certain optimization techniques.
  • the verification consists in carrying out a pre-calculation, and in adding its result to the code. This added pre-calculation is then used by the byte code checker to allow the use of simpler algorithms. It is therefore a simplified version of the so-called verification code technique (also known by the term "PCC" from the English “Proof Carrying Code”, or code carrying proof).
  • Type inference can be considered as a data flow analysis, the data being the memory cells manipulated by the instructions, expressed in byte code, of the virtual machine. Its purpose is to defend the virtual machine, as well as the basic system, but also user applications, by refusing any code that could harm their integrity.
  • the main role of type inference is to make sure that each instruction that makes up a program manipulates the data (memory) and triggers the execution of other processes while respecting their specifications.
  • Type inference is a static code analysis process that takes place during the loading phase of an application. It is reputed to be an expensive algorithm in terms of execution time, and also in memory consumption. This can severely penalize the process of loading code into virtual machine 32. Thus, type inference is normally executed by an external third party when the hardware constraints are deemed to be too great (as in a smart card for example).
  • the invention proposes, according to a first aspect, a method of verifying a program during its phase of integration into an electronic device, the program being organized according to types linked by parentage relationships , each type being identified by a respective code, the method comprising a type unification phase aimed at determining their closest common ascendant, characterized in that the code is described in the form of a bit pattern according to a formalism which expresses the parentage of the type with which it is associated, and in that the unification phase comprises a logical combination of patterns attributed to the types to be unified, producing the pattern of the type which is their closest common ascendant.
  • its pattern contains at least one bit which is identical in value and in position to a corresponding bit of the pattern of its direct ascendant.
  • the pattern of a given type preferably comprises a number of bits in a predetermined logic state which is a function of the distance from the type of the common ascendant.
  • the memory storage cells are initialized in the logical state from which the transition is in the opposite direction to the direction of the weary transition.
  • the logical combination When the wear transition is in the direction from logical state 0 to logical state 1, the logical combination preferably consists in carrying out a logical operation of the AND type between each pair of bits of the same rank of the combined patterns.
  • the logical combination When the wear transition is in the direction from logical state 1 to logical state 0, the logical combination preferably consists in carrying out a logical operation of the OR type between each pair of bits of the same rank of the combined patterns.
  • the method can be implemented for a program which is in the form of a set of sections of code, each section being identified by a marking which corresponds to an instruction attainable from a connection, by carrying out the verification by sections in an order of sections given according to a determined heuristic.
  • the order of the sections to be verified may be the order of succession of a verified section followed by its section which is its successor.
  • a volatile memory is used as a cache for storing candidate patterns at the logical combining step, and the candidate patterns are chosen dynamically and by forecast as a function of connection points in the program to be checked. We can then select for storage in volatile memory those of the patterns which correspond to types likely to be the subject of a unification at a given time, and carry out this selection of the patterns to be stored by reference to a program control flow graph to verify.
  • control flow graph is established from the markings determined beforehand and from the instructions which link to these markings.
  • the verification process is carried out with the execution medium of the device intended to execute the code of the program being checked.
  • the invention is particularly advantageous for carrying out verification in an electronic device of the smart card type.
  • the invention relates to an electronic device for verifying a program during its phase of integration into an electronic device, the program being organized according to types linked by parentage relationships, each type being identified by a respective code, said device comprising means of type unification to determine their nearest common ascendant, characterized in that it comprises means of identification of type affiliation, the identification of a type being carried out on the base of a bit pattern which constitutes its code according to a determined formalism, and in that the unification means comprise means of logical combination of patterns attributed to the types to be unified, producing the pattern of the type which is their common ascendant. closer .
  • This verification device can be made to be able to carry out the method according to the first aspect.
  • the invention relates to an electronic device making it possible to load and execute a program organized according to types linked by parentage relationships, each type being identified by a respective code, characterized in that it incorporates a verification device according to the second aspect.
  • this device is produced in the form of a smart card.
  • - Figure 1 already described, is a diagram which illustrates the principle of integration of a code verifier in a portable device such as a smart card
  • - Figure 2 already described, is a block diagram of the functional elements which constitute a micro-module of an open architecture smart card
  • FIG. 4 is an example, presented in the form of a table, of a new trace of type inference after modification of the joining hypothesis
  • FIG. 5 represents an example of encoding of a non-stressful unifying trellis, in accordance with the preferred embodiment
  • FIG. 6 is an example illustrating the use of a control flow graph to speed up verification by means of a software cache.
  • the Java virtual machine is a battery machine. It performs operations on working variables called local variables, as well as on a stack. The purpose of this process is to determine the type of each of the local variables and each of the cells in the stack for each point in the program. To do this, we take advantage of the fact that Java byte codes are typed.
  • Type inference is based on a static analysis of the code.
  • Each instruction in the Java byte code can be modeled as taking its parameters on the stack or in local variables, and generating a result on the top of the stack or in a local variable, if necessary.
  • For Java objects and variables allocated during the method their types are determined using the byte code used for their creation.
  • T is the root of the trellis; it is only compatible with itself. It is the largest element of the trellis.
  • a variable of type T is an unusable variable.
  • the type "null” is the element closing the part of the trellis containing the Java classes. It is the smallest element of this part. It is therefore compatible with all Java classes.
  • the example of which the type inference trace is given in FIG. 4 illustrates another particularity of the type inference algorithm.
  • the first solution is to mark it as being of type T, therefore not usable.
  • the "must ()” method is a method defined in the "Father” class whose Java code is valid. Indeed, both "Filsl” and “Fils2" inherited this method.
  • this operation consists in determining the common father of two nodes. This node is called the LUB (from English terminology "least-upper-bound").
  • LUB from English terminology "least-upper-bound"
  • the complexity of this operation increases rapidly as the depth of the trellis increases. It is therefore non-trivial to set it up in the context of a device with limited memory, such as a smart card.
  • the local variable vl is of type "null".
  • the reference algorithm comprises two successive phases, respectively designated “initialization” and “main loop", the main steps of which are summarized as follows
  • Initialization - initialization of the information for each program instruction. Position all the instructions in the "unchanged” state, except for the first instruction which will be positioned in the state as "changed”; fill in the typing information of the latter using the signature, the variables having no type are initialized with T, initialize its TOS with the value 0;
  • JavaCard language requires a suitable typing, which implies modifications and adaptations of the algorithms described above, in particular with regard to the lattice of types and subroutines.
  • FIG. 5 An example of a JavaCard type lattice is shown in Figure 5.
  • the description first addresses the accelerating mechanisms of unification, followed by an optimization of the management of fixed points based on the use of software caches.
  • the embodiments address the problem posed by the complexity of inference by two solutions: a unification table and, optionally, an effective and non-stressful unifying coding for memories subject to wear by transitions in a certain direction. .
  • a first solution used by the embodiment consists in pre-calculating the unification rules of the types. We then obtain a table with two entries (the two types tl and t2 to be unified), which provides the answer to the question that is worth tl n t2. There then arises the problem linked to the infinity of types available: it is indeed possible to load a large number of classes into the smart card. Adding a new class would therefore result in the creation of a new row or column in the unification table, as well as the calculation of the result of unification thereof with all the types already present in the map to this moment .
  • Table 1 example of a portion of the unification acceleration table.
  • the information handled during the inference is the types.
  • a coding is established according to a formalism which expresses its filiation. This coding is used to achieve more efficient unification.
  • a technique using a bijection of the operations on the trellis to the Boolean operations is used.
  • the encodings used make it possible to find the common father of two elements of a trellis using a composition of logical functions.
  • the result, which constitutes unification, then returns the code which corresponds, according to the established formalism, to the common father of two types.
  • the typing information must, in most cases, be stored in persistent memory 22, in particular of the EEPROM type, because of their size.
  • This type of memory is subject to stress. More particularly, the memory suffers from wear caused by a plurality of transitions of logical states in a particular direction, in this case from 0 to 1.
  • FIG. 5 represents a case of non-stressful unifying lattice.
  • Top for "top” in English.
  • the formalism used in the embodiment adapted to avoid as much as possible the stressful transitions in the EEPROM memory 22 of the card 2, fixes as code for this common father a pattern formed by bits at state 0.
  • the number of bits forming this pattern is chosen according to the maximum number of types in the trellis which share the same common ascendant. Any type is coded with a pattern comprising the same number of bits. In the example, six bits constitute a pattern, the common father T having the pattern "00 0000". We ensure in particular that this number of bits allows:
  • its pattern comprises at least one bit which is identical in value and in position to the pattern of its direct ascendant.
  • each bit at state 1 of this ascendant is found at the same position in the pattern of this given type. (The latter also includes an additional bit at state 1 which is specific to it, and makes it possible to distinguish it between other direct descendants of this direct common ascendant.)
  • the most important property of this encoding is that it is particularly suitable for storage in EEPROM: we may have to store the typing information in the EEPROM in particular, because it can be large compared to the others memories available from the smart card.
  • the stress of the EEPROM is limited when dropping bits (going from 1 to 0). Unification being reduced to a logical AND, by applying it to two types, we only change bits from 1 to 0 and never from 0 to 1. Thus, we considerably reduce stress and increase the lifespan of the EEPROM.
  • Coding of this kind can be adapted to any type of EEPROM. Indeed, some have inverse properties for writing stress, ie a stressful transition caused by the passage 1 to 0. In this case, the coding is changed so that the unification is reduced to a logical OR. More particularly, the logical states of the patterns are systematically reversed with respect to those used for the AND combinations described above. To return to the example of FIG. 5, the common father T is then assigned the motif 11 1111, the motif 01 1111 of the "Int" type, etc. It can be easily verified on the basis of simple principles of Boolean logic that the same results are obtained in this case with the logical OR operation in place of the AND logical operation in the context of FIG. 5.
  • the coding can be made more compact using a more complex Boolean function, by means of storage in EEPROM memory which can cause stressful transitions.
  • a heuristic must make it possible to predict not only the patterns soon to be combined, but also, conversely, to predict those more likely to be combined in order to eliminate them. This implies dynamic and evolving management.
  • heuristics are advantageously used which require little calculation so as not to burden the resources used.
  • Marking selection heuristic to be checked The optimized type inference algorithm described above works at the connection points of JavaCard programs. During the inference, there may be several labels marked as being to be verified. This therefore leads to electing one of them and checking the corresponding code section. It is therefore necessary to have a selection criterion.
  • This heuristic can be used for reference. It provides good results on an evaluation game. It consists in choosing at random the next marking to be checked among the types marked. - The "Next" heuristic.
  • the "Next" heuristic is relatively simple. It consists in electing the marking which is the successor of the marking which has just been verified. The necessary number of linear verification passes are thus carried out.
  • the "Lazy” heuristic is optimal in terms of efficiency and simplicity. It consists of taking as a mark to verify the first marked.
  • JavaCard programs come from the conversion of Java code compiled using the Java development kit, known by the English term JDK from "Java Development Kit”. However, this generates fairly linear code. Program breakpoints are quite often found at the end of the byte code. This observation is exploited by therefore systematically using the first marking as being to be verified. Thus, we focus on the beginning of the program to never come back to it later.
  • the "Lazy” heuristic makes it possible to obtain a value of 1.3 for the ratio r defined above.
  • Fine-tuned heuristics can be implemented, in particular by using the flow control graph of the verified program.
  • the graph can in particular be used to control software caches.
  • a software cache is set up between the EEPROM and the RAM to better manipulate the type "frames". This implies a phase of electing the data to delete (destock) from the cache being verified, and therefore a cache management policy.
  • control flow graph determines the cache management policy.
  • the control flow graph is provided in accordance with the example illustrated with reference to FIG. 6.
  • Table II shows a possible trace of the type inference for this example.
  • Table II possible execution trace of the type inference for the example of FIG. 6.
  • the preferred embodiment makes it possible to obtain simple verification systems which opens up the possibility of implementing a verifier fully embedded in a microprocessor card or other device with restricted memory.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Computer Hardware Design (AREA)
  • Quality & Reliability (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)
  • Stored Programmes (AREA)

Abstract

La vérification s'applique à 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. On réalise une phase d'unification de types visant à déterminer leur ascendant commun le plus proche en utilisant, conformément à l'invention, une forme du code précité présentant un motif de bits selon un formalisme qui exprime la filiation du type auquel il est associé, et en réalisant une combinaison logique de motifs attribués aux types à unifier, produisant le motif du type qui est leur ascendant commun le plus proche. L'invention permet de réaliser la vérification dans des dispositifs électroniques limités en ressources mémoire, notamment des cartes à puce (2).

Description

PROCEDE ET DISPOSITIF DE VERIFICATEUR 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 ("overflo " / "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 1 ' 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 pseudo- code, 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 anglo- saxonne) ;
- 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é a 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 Formai Underpinnings of the Java Paradigm, OOPSLA '98, 1998 ; et Necula G.C. et Lee P. "Proof Carrying Code" Proceedings of the 24th ACM SIGPLAN- SIGACT 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 Vérification, 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 a 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 1 ' é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 a 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 1 ' affirmâtif , 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 celle- ci 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'ité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 ;
- 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 I 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 O la "frame de type" de I, et R celle de S ;
- si le TOS associé à S vaut -1 , R=0 (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 O (si les TOS des deux "frames de type" sont différents, la vérification échoue) ;
- si R n O ≠ R, marquer S comme "changed", R n O 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, 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 1 ' 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 I ci-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 t 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, 1 ' é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é a stocker les informations de typage dans 1' 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 1 '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 à 1 '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 anglo- saxon 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 récently 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 1 ' inférence de type pour cet exemple . Tableau II: trace d'exécution possible de l'inférence de type pour 1 ' 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 "labell" avec celle courante . On chargera donc les informations de typage du marquage "labell" 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 "labell" pour vérifier la section de code correspondante, conformément à l'utilisation de l'heuristique "Lazy" ; - on doit unifier avec le marquage "label2" ; 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 typage 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 "label2" les marquages "label2" et "label3" 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.

Claims

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 1 ' é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 l'on 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) .
EP02783198A 2001-09-24 2002-09-24 Procede et dispositif de verificateur de code optimise Withdrawn EP1433065A1 (fr)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
FR0112278A FR2830095B1 (fr) 2001-09-24 2001-09-24 Procede et dispositif de verifieur de code optimise
FR0112278 2001-09-24
PCT/FR2002/003249 WO2003027851A1 (fr) 2001-09-24 2002-09-24 Procede et dispositif de verifieur de code optimise

Publications (1)

Publication Number Publication Date
EP1433065A1 true EP1433065A1 (fr) 2004-06-30

Family

ID=8867556

Family Applications (1)

Application Number Title Priority Date Filing Date
EP02783198A Withdrawn EP1433065A1 (fr) 2001-09-24 2002-09-24 Procede et dispositif de verificateur de code optimise

Country Status (5)

Country Link
US (1) US20050044542A1 (fr)
EP (1) EP1433065A1 (fr)
CN (1) CN1589435A (fr)
FR (1) FR2830095B1 (fr)
WO (1) WO2003027851A1 (fr)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7320129B2 (en) * 2003-05-14 2008-01-15 Hewlett-Packard Development Company, L.P. Native language verification system and method
US7263690B1 (en) * 2003-11-14 2007-08-28 Sun Microsystems, Inc. Mechanism for safe byte code in a tracing framework
CN100465853C (zh) * 2004-11-15 2009-03-04 南京大学 基于程序内部行为监控的软件安全保障的方法
US8120583B2 (en) * 2006-09-08 2012-02-21 Aten International Co., Ltd. KVM switch capable of detecting keyword input and method thereof
US9286026B2 (en) 2006-09-08 2016-03-15 Aten International Co., Ltd. System and method for recording and monitoring user interactions with a server
US8201155B2 (en) * 2009-01-09 2012-06-12 Microsoft Corporation Handling multiple definition of types
US8549502B2 (en) * 2010-06-21 2013-10-01 Microsoft Corporation Compiler with user-defined type inference rules
CN112487841B (zh) * 2020-12-15 2024-08-16 北京爱创科技股份有限公司 一种快速验证包装关系的方法及装置

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO03027851A1 *

Also Published As

Publication number Publication date
FR2830095A1 (fr) 2003-03-28
US20050044542A1 (en) 2005-02-24
FR2830095B1 (fr) 2003-10-31
CN1589435A (zh) 2005-03-02
WO2003027851A1 (fr) 2003-04-03

Similar Documents

Publication Publication Date Title
EP2299363B1 (fr) Procédé de nivellement de l'usure dans une mémoire non volatile
EP3293637A1 (fr) Gestion d'index dans une mémoire flash
EP1433065A1 (fr) Procede et dispositif de verificateur de code optimise
WO2003010666A1 (fr) Procede pour la compression d'un code interprete par analyse semantique
FR2864654A1 (fr) Procede de determination de caracteristiques operationnelles d'un programme
EP1782191B1 (fr) Procede de chargement d'un logiciel en langage intermediaire oriente objet dans un appareil portatif
FR2823330A1 (fr) Procede et systeme de gestion de donnees destinees a etre stockees dans une memoire, par exemple du code d'une application charge dans une carte a puce programmable
FR2795835A1 (fr) Procede de verification de transformateurs de codes pour un systeme embarque, notamment sur une carte a puce
EP0838053B1 (fr) Procede et dispositif permettant a un programme fige de pouvoir evoluer
EP1512071B1 (fr) Procede de verification de codes pour microcircuits a ressources limitees
FR3051574A1 (fr) Gestion du stockage dans une memoire flash
WO2005101725A1 (fr) Procede d'authentification dynamique de programmes par un objet portable electronique
EP2252978B1 (fr) Carte a circuit integre ayant un programme d'exploitation modifiable et procede de modification correspondant
FR2854261A1 (fr) Procede d'execution d'une application logicielle par l'intermediaire d'un programme d'amorce logicielle et architecture informatique pour la mise en oeuvre du procede
WO1999000774A9 (fr) Module de securite comportant des moyens de creation de liens entre des fichiers principaux et des fichiers auxiliaires
EP3203405B1 (fr) Procede d'execution d'instructions d'applications orientees objet par un interpreteur
EP1770524A2 (fr) Détection d'erreur de séquencement dans l'exécution d'un programme
FR2877454A1 (fr) Procede de chargement d'un code logiciel en langage intermediaire oriente objet dans un appareil portatif
EP4312128A1 (fr) Procede de gestion d'une memoire d'un element securise
WO2021032919A1 (fr) Récuperateur de données dans un dispositif électronique
FR2935502A1 (fr) Procede d'optimisation de la duree de vie d'une memoire non volatile reinscriptible.
FR3051575A1 (fr) Gestion de l'effacement dans une memoire flash
FR2910658A1 (fr) Systemes electroniques securises,procedes de securisation et utilisations de tels systemes
FR2950464A1 (fr) Procede de nivellement de l'usure dans une memoire non volatile

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20040426

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR IE IT LI LU MC NL PT SE SK TR

AX Request for extension of the european patent

Extension state: AL LT LV MK RO SI

17Q First examination report despatched

Effective date: 20080104

GRAP Despatch of communication of intention to grant a patent

Free format text: ORIGINAL CODE: EPIDOSNIGR1

GRAC Information related to communication of intention to grant a patent modified

Free format text: ORIGINAL CODE: EPIDOSCIGR1

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20110117