Abstract:
A space-efficient and flexible mechanism for implementing a virtual machine in a resource-constrained environment such as a smartcard is proposed. The virtual machine is designed for interpreting or carrying out instructions which are identified by an instruction code, also called opcode. Both, the addresses, respectively identifiers, of the functions implementing the instruction codes, respectively opcodes, which the virtual machine interprets, as well as parameters to those functions are kept within lookup tables.

Description:
FIELD OF THE INVENTION 
     The invention relates to a method and a device for carrying out at least one function assigned to an instruction code. More particularly, the method, respectively the device, represents a space-efficient and flexible mechanism for implementing a virtual machine in a resource-constrained environment such as a smartcard, particularly a smartcard offering a Java environment, such as a Javacard. 
     TECHNICAL FIELD AND BACKGROUND OF THE INVENTION 
     In a system environment with constrained resources such as limited code storage area, usually a ROM, limited application storage area, usually an EEPROM, limited runtime memory, usually a RAM, and limited compute power, i.e, small CPU and low clock cycle rate, the interpretive approach to running applications is well-known. Due to the higher level of abstraction provided by the interpreted code over the machine code, the use of more compact application code is possible, which is an essential requirement in the aforementioned environments. Therefore, the availability of an interpreter is desirable in an embedded system. 
     OBJECT AND ADVANTAGES OF THE INVENTION 
     It is an object of the invention according to claim 1 and 8, to provide a method and a device for executing instruction codes, which require less memory. It is another object of the invention according to claim 1 and 8, to provide a method and a device for executing instruction codes which provides for an easier way to amend the instructions codes, respectively functions which are to be carried out. 
     The above mentioned objects are met by a method according to claim 1 and a device according to claim 8. Regardless of whether the interpreter, also called “virtual machine”, is implemented in software or in hardware, the following two problems are solved: 
     Firstly, the size of the internal main loop serving for the dispatching respectively executing of the codes, herein called “opcodes”, interpreted in the virtual machine, as well as the size and also number of functions necessary to implement the opcodes is reduced. It is most advantageous to get both to the minimum size because of the aforementioned resource constraints in embedded systems, i.e. a system e.g. on a smartcard. 
     Secondly, it might be desirable to be able to change and/or enhance the semantics of single opcodes without changing the code of either the main loop or code implementing the other opcodes. The latter is especially important in an area where opcodes can change due to specification changes, error fixes, particularly at the level of single opcodes, or performance improvements requiring the modification/addition of single opcodes. 
     The approach using a virtual machine which is designed for interpreting or carrying out instructions which are identified by an instruction code whereby the addresses of the functions implementing the opcodes which the virtual machine interprets, as well as parameters to those functions are kept within lookup tables, yields two primary benefits: 
     First, the main interpreter loop is very small, and due to the parameter table, generic functions can be referred to by the opcode table, thus leading to a very space-efficient representation of the virtual machine code. 
     Second, by placing these tables into a mutable memory, such as an EEPROM, error-fixing as well as general maintenance of the virtual machine is feasible at the level of single opcodes even after production of the actual hardware. 
     SUMMARY OF THE INVENTION 
     The invention uses generic opcode tables in conjunction with parameter tables. The idea is to use two types of lookup tables at the core of the virtual machine implementation. The first table, called also “opcode lookup table”, contains for each opcode the address of a function implementing its semantics. As these functions might be generic, i.e., serve for several opcodes as their implementation, a second, discriminating table, also called “parameter lookup table”, is used. Both tables contain the same number of entries, which is identical to the number of opcodes understood by the respective virtual machine. The tables can also be unified to one single table with the opcodes, the functions and the parameters as entries. 
     Especially in a scenario, where many functions can be shared between opcodes, this approach is advantageous: Only a minimum number of these generic routines, which hence results in an according minimum requirement of code size, need be employed because of the use of the functionality-discriminating parameter table. For example, it is assumed that such a scenario of function-sharing for opcode implementations is common if a virtual machine originally intended for a non-resource-constrained environment has to be semantically stripped down to run in a resource-constrained environment. Therewith, the reduction of the functionality of the virtual machine eventually leads to a reduction in complexity of many opcodes, in turn leading to the aforementioned opportunity to create generic functions. 
     Execution of the virtual machine main loop then can proceed as follows: 
     An opcode to be interpreted is loaded from memory. 
     The address of the opcode-realizing function is looked up from the opcode lookup table. 
     A parameter for this function is read from the parameter lookup table. This part of the procedure is optional. Possibly no parameter may be needed. The lookup then returns no parameter or a read parameter can be ignored by the function. 
     The parameter can be loaded into a unique address, e.g., a variable. 
     The function for the instruction code is called and executed. 
     The function returns, and the next opcode is fetched and executed. 
     This way, the code of the core of the virtual machine does not need modification, even if new opcodes are added, since the table is in that case just extended. Also, if old codes are changed, address and parameter entries can be simply changed at the index corresponding to the respective opcode. If opcodes are to be removed, table entries can be invalidated. 
     By the invention&#39;s concept, the implementation of the virtual machine core and the implementation of each single opcode are separated. 
     This yields the following advantages: The virtual machine core is extremely small in size. By having the lookup tables reside in immutable memory, e.g. a ROM, an implementation of a virtual machine can be secured against future changes. By having the lookup tables reside in mutable memory, e.g. EEPROM, an implementation of a virtual machine can be changed after delivery of the implementation to the customer. 
     Although optimizing compilers are known to build memory-efficient jump tables for the alternative implementation of a virtual machine core, i.e., CASE or SWITCH statements, they have four primary disadvantages solved by the proposed concept: First, they still bear an overhead due to the inclusion of the inevitable ‘JMP’ machine code statement, which is necessary, since executable code must be the result of a compiler/linker. Second, they always reside in the immutable area shared with all machine code. Third, it is impossible to only change single cases, i.e., implementations of single opcodes after the code has been produced, i.e., put into ROM or hardware. Fourth, compiler-generated optimizations are highly compiler-dependent and cannot be relied on to be done correctly on all platforms. 
     The advantage of the proposed solution is that it works on all system architectures the virtual machine is intended to work in, without change. In fact, if the virtual machine core were implemented in hardware, by putting the lookup tables into mutable memory, this approach would permit the enhancement of a hardware-based virtual machine even after production “in the field”, i.e., even after a customer has started to use it. This is an invaluable advantage if resources are scarce, thus not permitting an update of the complete virtual machine if only single opcode&#39;s implementations need enhancements. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     An example of the invention is depicted in the drawing and described in detail below by way of example. It is shown in an arrangement with a virtual machine and a memory section for the lookup functions for instruction code. The figure is for sake of clarity not shown in real dimensions, nor are the relations between the dimensions shown in a realistic scale. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In the following, the various exemplary embodiments of the invention are described. 
     As shown in the figure, a protocol-handling unit  15 , denoted with “PHU”, comprises a device driver  16 , denoted with “DD”, and a read-write unit  17 , denoted with “RW”. The PHU  15  communicates bidirectionally with a virtual machine  10 , also called “VM”, serving as control means, which comprises a main loop unit  11 , also called “ML”, and a function section  12 , also called function memory, in which a set of possible functions Function 1 , Function 2 , Function 3 , Function 4  is stored in form of machine code. Each function Function 1 , Function 2 , Function 3 , Function 4  is addressable via an identifier Fn 1 , Fn 2 , Fn 3 , Fn 4 . 
     The VM  10  provides a program counter PC which is assigned to a virtual machine instruction-code-storing means  14  in which code sequences  18  which belong to methods which themselves belong to applets are stored. Applets are collections of data and the therewith-operating methods. 
     The code sequences  18  consist of single instruction codes opcode 1 , opcode 2 , opcode 3 , opcode 4 , opcode 5 , opcode 6 . The virtual machine instruction-code-storing means  14 , also called code memory or CM  14 , is communicated with by the ML  10  which again communicates with a first table means  23  and a second table means  24  which both together with a heap memory  26  form part of a memory unit  25 , here exemplarily an EEPROM, short EE. The outputs of the table means  23 ,  24  lead back to the function section  12  to which the heap memory  26  is bidirectionally connected. The PHU  15  further is connected to a random-access memory or RAM  20  which comprises an APDU-object-storing section  21 , short AO, and a stack-storing section  22 , short St. This St  22  has a bidirectional connection to the function section  12  of the VM  10  and is bound to a stack pointer SP which is provided by the ML  11 . The RW  17  can bidirectionally exchange data with the memory unit  25 . 
     An initialization unit  13 , denoted “Ini”, is receiving external input via a Power-On line PON and is providing its output to the PHU  15 . The PHU  15  receives external input via an input line which delivers application protocol data units, short APDUs. An applet administration unit, also called runtime environment  19 , short RTE  19 , is communicating bidirectionally with the VM  10 . 
     The depicted arrangement is preferably arranged on a portable carrier, such as a smartcard, or Javacard. The card can be inserted into a card reader which provides an interface towards external circuitry which communicates with the smartcard via this interface. The interface is to a high degree standardized. APDUs arrive via the card reader at the DD  16  of the PHU  15 . The PHU  15  can handle various types of APDUs, which types are “SELECT” APDUs, “READ EE” APDUs, “WRITE EE” APDUs and other APDUs, herein called “standard” APDUs. The type of APDU which is arriving is recognized in the PHU  15 . 
     During an initialization phase, the initialization unit  13  is active. Upon power on, arriving via the PON line, which simply may be the necessary electrical power needed to run the card circuitry, and a reset signal, inter alia the St  22  is cleared, the PC and the SP are reset, the RAM  20  is cleared, the heap memory  26  is initialized and in the St  22  a system APDU object is initialized in that an APDU object header is written. The PHU  15  is then enabled and waiting for input. 
     As next step, upon arrival of a first APDU which is a SELECT APDU, in the case, when a default applet has not been chosen as the so-called “current applet”, the SELECT APDU is recognized by the PHU  15 , such that the applet in the CM  14  which is identified by the SELECT APDU is selected to be the current applet. Each stored applet contains a number of methods, among which inter alia is stored a process-method, a select-method, an install method and a deselect-method. 
     The arrival of a standard APDU triggers the use of the predetermined current applet for the standard APDU, and more particularly the process-method of the current applet. The VM execution start address of the process-method of the current applet is the address where the first to execute instruction code opcode  1 - 6  for that process-method is stored in the CM  14 . This address is known by the RTE  19  which provides via the VM  10  for the PC being set on that address in the CM  14 . 
     The VM  10  begins to interpret the instruction code sequence  18  from the VM execution start address on. This interpretation comprises the determination of the respective functions to be carried out for this instruction code sequence  18 , starting with the function Function 1 - 4  for the first instruction code opcode  1 - 6  of that instruction code sequence  18 . 
     Therefor, the instruction code opcode  1 - 6  at the address which the PC points to is fed to the first table means  23  which for every possible instruction code opc  1 - 6  comprises the respective function identifier Fn 1 - 4  which identifies the function Function 1 - 4  which is assigned to the respective instruction code opcode  1 - 6 . The instruction code opcode  1 - 6  at the address which the PC points to is also fed to the second table means  24  which for every possible instruction code opc  1 - 6  comprises the respective parameters P 1 , P 2 , P 3  which belong to the identified function Function 1 - 4  for this instruction code opcode  1 - 6 . This feeding is executed by the ML  11 . 
     The found function identifier Fn 1 - 4  together with the identified parameters P 1 , P 2 , P 3  is delivered to the function section  12  where the function identifier Fn 1 - 4  is used to address the storage cell where the respective function Function 1 - 4  is stored. This addressing is again carried out by the ML  11  which then effects that the identified function Function 1 - 4  is then carried out. 
     The functions can perform various actions. A function Function 1 - 4  can e.g. access the heap memory  26  or the stack-storing section  22  and can thereby modify the SP and/or the PC of the VM  10 . As long as the St  22  is not empty, the PC is incremented either by one step or by the number of steps, an instruction code opcode  1 - 6  contains as function Function 1 - 4 , i.e. a “Goto” or “Jump” function Function 1 - 4 . 
     After completing the function Function 1 - 4  for the last instruction code opcode  1 - 6  of a method, the stack pointer SP arrives at a predetermined value indicating to the VM  10  that the stack-storing section  22  is empty. Then, the control is given back to the PHU  15  which returns data, such as status data via the OUT line to the card reader and then expects the next APDU to arrive. 
     The PHU  15  receives the APDUs and stores them, but usually only one at a time, in the RAM  20  at the area of the APDU object payload, assigned to the existing object header which was generated during the initialization phase. 
     In the RAM  20 , the APDU object is stored, which is then accessible by the instruction codes. Thereby, the instruction codes can access data which is needed to perform a particular action, e.g. reading a number representing a monetary value which is to be charged onto a storage cell, which represents the saldo of an account. 
     In the case, when a SELECT APDU is recognized by the PHU  15 , the current applet is used, but now as a first action the deselect-method thereof is to be used instead of the process-method. The respective instruction code sequence  18  of the deselect-method is hence executed via the VM  10 . Afterwards, as a second action, a new current applet is selected according to the information from the SELECT APDU and for the new current applet the select-method is executed by the VM  10 . 
     When a READ APDU is recognized, then the VM  10  is not activated but the memory unit  25  is directly accessed by the PHU  15  for a read-operation, whose result is then output to the card reader via the OUT line. When a WRITE APDU is recognized, then the VM  10  is not activated but the memory unit  25  is directly accessed by the PHU  15  for a write-operation, using the respective part of the content of the WRITE APDU as the new content of a specific memory cell in the memory unit  25 . The processing of READ APDUs and WRITE APDUs may be disabled via a suited mechanism, be it a hardware- or a software-implemented mechanism, to avoid misuse of these APDUs for forbidden actions on the smartcard. 
     The tables  23 ,  24  can be unified to one single table which then contains only one address to determine the function identifier Fn 1 - 4  and the corresponding parameters P 1 , P 2 , P 3  in ony single step. This saves time and memory. 
     The tables can be stored in non-mutable as well as in mutable memory. The use of mutable memory is advantageous since then changes in the assignment between functions and instruction codes are easily executable. Also a mixed use of mutable and non-mutable memory can be suitable, particularly when some content of the tables is to be protected from erroneous or even intentional amendment and other content is to be rendered easily accessible for such amendments. Basic functions and/or a sort of default settings can e.g. be stored in non-mutable memory, to preserve card functionality in any case. A new function Function 1 - 4  can be added to the set of available functions Function 1 , Function 2 , Function 3 , Function 4  in that the new function Function 1 - 4  is entered in a mutable new-function memory and that the identifier Fn 1 - 4  in the first table  23  is changed to identify the new function Function 1 - 4  in the mutable new-function memory. The mutable new-function memory can be a separate memory section, but of course be also unified or identical with the function memory  12 . 
     For an instruction code opcode  1 - 6  which is at least temporarily no longer needed, an identifier Fn 1 - 4  can be entered in the first table  23  which signalizes that no function Function 1 - 4  is to be executed. 
     The number of instruction codes, storage cells, functions a.s.o. is exemplary only and hence not limited to the herein chosen number. Additionally another heap memory  26  can be arranged in the ram  20 , which heap memory  26  can also be accessible by the functions. (Javacard is a trademark of Sun Microsystems, Inc.)