REGISTER  |  SIGN IN


The Patents.com acquisition of PatentMonkey.com finds us in a position where we are moving our data to new facilities. Please bear with us during the move, and look for our new home Patents.com.
- Optimized representation of data type information in program verification
RRtechlaw
 Patent URL 
ClaimsAbstractDescription

What is claimed is:
1. A method for program verification, the method comprising: receiving a program unit; determining data types used by said program unit; creating a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and using said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.
2. The method of claim 1 wherein said first mapping represents all data types used by said program unit.
3. The method of claim 1 wherein said first mapping represents a subset of data types used by said program unit.
4. The method of claim 1 wherein said first mapping represents most-used data types of said program unit.
5. The method of claim 1 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.
6. The method of claim 1 wherein said program comprises a Java.TM. program.
7. The method of claim 6 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.
8. A method for program verification, the method comprising: step for receiving a program unit; step for determining data types used by said program unit; step for creating a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and step for using said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.
9. The method of claim 8 wherein said first mapping represents all data types used by said program unit.
10. The method of claim 8 wherein said first mapping represents a subset of data types used by said program unit.
11. The method of claim 8 wherein said first mapping represents most-used data types of said program unit.
12. The method of claim 8 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.
13. The method of claim 8 wherein said program comprises a Java.TM. program.
14. The method of claim 13 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.
15. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for program verification, the method comprising: receiving a program unit; determining data types used by said program unit; creating a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and using said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.
16. The program storage device of claim 15 wherein said first mapping represents all data types used by said program unit.
17. The program storage device of claim 15 wherein said first mapping represents a subset of data types used by said program unit.
18. The program storage device of claim 15 wherein said first mapping represents most-used data types of said program unit.
19. The program storage device of claim 15 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.
20. The program storage device of claim 15 wherein said program comprises a Java.TM. program.
21. The program storage device of claim 20 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.
22. An apparatus for program verification, the apparatus comprising: means for receiving a program unit; means for determining data types used by said program unit; means for creating a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and means for using said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.
23. The apparatus of claim 22 wherein said first mapping represents all data types used by said program unit.
24. The apparatus of claim 22 wherein said first mapping represents a subset of data types used by said program unit.
25. The apparatus of claim 22 wherein said first mapping represents most-used data types of said program unit.
26. The apparatus of claim 22 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.
27. The apparatus of claim 22 wherein said program comprises a Java.TM. program.
28. The apparatus of claim 27 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.
29. An apparatus for communicating program verification, comprising: a memory for storing a program comprising a plurality of program units; and a processor configured to: receive a program unit; determine data types used by said program unit; create a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and use said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.
30. The apparatus of claim 29 wherein said first mapping represents all data types used by said program unit.
31. The apparatus of claim 29 wherein said first mapping represents a subset of data types used by said program unit.
32. The apparatus of claim 29 wherein said first mapping represents most-used data types of said program unit.
33. The apparatus of claim 29 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.
34. The apparatus of claim 29 wherein said program comprises a Java.TM. program.
35. The apparatus of claim 34 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.
36. A memory for storing data for access by an application program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information used by said program to verify a program unit, said data structure comprising a type mapped representation of data types used by said program unit during simulated execution of said program unit, said type map comprises a bitmap, each bit in said bitmap representing a data type used by said program unit.
37. The memory of claim 36 wherein said representation represents all data types used by said program unit.
38. The memory of claim 36 wherein said representation represents a subset of data types used by said program unit.
39. The memory of claim 36 wherein said representation represents most-used data types of said program unit.
40. The memory of claim 36 wherein said representation is exclusive of data types represented by another type mapped representation representing data types used by a higher-level program unit.
41. The memory of claim 36 wherein said program comprises a Java.TM. program.
42. The memory of claim 41 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.


  Add Private Notes on this Patent
Register to save notes on current patent

Save   Cancel  

United States Patent7165246
de JongJanuary 16, 2007
Optimized representation of data type information in program verification
Abstract
A method for program verification comprises receiving a program unit, determining data types used by the program unit, creating a first mapping for the data types and using the first mapping to represent type information in verification information for the program unit. The verification information comprises the data type of entries on an operand stack or in a register file during simulated execution of the program unit.
Inventors:de Jong; Eduard (Amsterdam, NL)
Assignee:Sun Microsystems, Inc. (Santa Clara, CA)
Appl. No.:10/346,227
Filed:January 16, 2003
PCT Pub Date:January 23, 2007
Current U.S. Class:717/166 
Current International Class:G06F 9/44 (20060101)
Field of Search:717/165-167,177-178,116,118 365/200 711/206 726/20 707/1,10 709/203,229 705/75
[References Cited] - [Referenced By]
U.S. Patent Documents
20020010679January 2002Felsher
20020040936April 2002Wentker et al.
20020093856July 2002Baentsch et al.
20020144243October 2002Alexander, III et al.
20020165961November 2002Everdell et al.
20020174071November 2002Boudou et al.
20030028742February 2003Hameau et al.
20030028811February 2003Walker et al.
20030062202April 2003Parry
20030095690May 2003Su et al.
20030229769December 2003Montemayor
20040083469April 2004Chen et al.
20040088562May 2004Vassilev et al.
20050097550May 2005Schwabe et al.
5421016May 1995Conner et al.
5721781February 1998Deo et al.
5761513June 1998Yellin et al.
5778234July 1998Hecht et al.
5781723July 1998Yee et al.
5802519September 1998De Jong
5812662September 1998Hsu et al.
5889999March 1999Breternitz, Jr. et al.
5930509July 1999Yates et al.
5950009September 1999Bortnikov et al.
5991774November 1999Tate et al.
5999731December 1999Yellin et al.
5999732December 1999Bak et al.
6005942December 1999Chan et al.
6006033December 1999Heisch
6032137February 2000Ballard
6052690April 2000de Jong
6081800June 2000Ozbutun et al.
6092147July 2000Levy et al.
6094656July 2000De Jong
6131159October 2000Hecht et al.
6141681October 2000Kyle
6202060March 2001Tran
6205465March 2001Schoening et al.
6223340April 2001Detlefs
6233683May 2001Chan et al.
6233733May 2001Ghosh
6272674August 2001Holiday, Jr.
6308317October 2001Wilkinson et al.
6314562November 2001Biggerstaff
6367012April 2002Atkinson et al.
6463581October 2002Bacon et al.
6481632November 2002Wentker et al.
6487714November 2002Azagury et al.
6526571February 2003Aizikowitz et al.
6574618June 2003Eylon et al.
6604114August 2003Toong et al.
6643652November 2003Helgeson et al.
6648821November 2003Lebel et al.
6792536September 2004Teppler
6807561October 2004Lagosanto et al.
6836884December 2004Evans et al.
6880155April 2005Schwabe et al.
6895581May 2005Chkodrov et al.
6931635August 2005Inagaki et al.
6948070September 2005Ginter et al.
6961587November 2005Vilppula et al.
6961664November 2005Selifonov et al.
6981212December 2005Claussen et al.
6985956January 2006Luke et al.
Foreign Patent Documents
0 751 459Jan., 1997EP
0 969 362Jan., 2000EP
1 011 043Jun., 2000EP
1 022 638Jul., 2000EP
97/45817Dec., 1997WO
98/19237May., 1998WO
WO 00/46667Aug., 2000WO
WO 01/50230Jul., 2001WO
WO 02/062007Aug., 2002WO
WO 03/003694Jan., 2003WO
Other References
Ross Anderson et al., "A New Family of Authentication Protocols", pp. 1-13. cited by other .
Zhiqun Chen, "Java Card Technology for Smart Cards", Jun. 2000, pp. 11-16. cited by other .
Deianov Borislav, "Authentication-Lamport hash and biometrics", Jan. 9, 2002, pp. 1-3. cited by other .
Naor et al., "Universal One-Way Hash Functions and their Cryptographic Applications", Mar. 13, 1995, pp. 1-14. cited by other .
George C. Necula et al., "Proof-Carrying Code", Nov. 1996, pp. 1-60. cited by other .
George C. Necula et al., "Safe Kernal Extensions Without Run-Time Checking", pp. 1-16. cited by other .
Sun Microsystems, Inc., "Smart cards: A primer", Apr. 22, 200., pp. 1-13. cited by other .
Bowles et al., "A Comparison of Commercial Reliability Prediction Programs", Proceedings Annual Reliability and Maintainability Symposium, IEEE, pp. 450-455. cited by other .
Lindsay et al., "A Generic Model for Fine Grained Configuration Management Including Version Control and Traceability", Proceedings of the Australian Software Engineering Conference(ASWEC'97), IEEE Computer Society, pp. 27-36 (1997). cited by other .
Zhao, Jianjun "Applying Program Dependence Analysis to Java Software" Fukuoka Kogyo Daigaku Kenkyu Ronshu (Research Bulletin of Fukuoka Institute of Technology), vol. 31, No. 1, pp. 29-41 1998. cited by other .
Mark Russinovich, "Inside On-Access Virus Scanners," Windows IT PRO, Online! Sep. 1997, XP002298829. cited by other .
Bauspiess, Fritz, et al., "Requirements for Cryptographic Hash Functions", Computer & Security, vol. 11, No. 5, pp. 427-437, Elsevier Science Publishers, Amsterdam, NL, Sep. 1, 1992. (XP000296996). cited by other .
Zhiqun Chen, "Technology for Smart Cards: Architecture and Programmer's Guide", Addison Wesley, (Online) Jun. 6, 2000, (XP002305506). cited by other .
Sundaresan, Vijay et al., "Practical Virtual Method Call Resolution for Java", OOPSLA 2000. Conference on Object-Oriented Programming Systems, Languages and Applications, pp. 264-280, Minneapolis, MN, Oct. 31, 2000. (XP002336235). cited by other .
R. Rivest, "The MD4 Message Digest Algorithm", Request for Comments (RFC) 1320, MIT Laboratory for Computer Science and RSA Data Security, Inc., Apr. 1992, pp. 1-20. cited by other .
R. Rivest, "The MD5 Message-Digest Algorithm", Request for Comments (RFC) 1321 MIT Laboratory for Computer Science and RSA Data Security, Inc., Apr. 1992. cited by other .
"Secure Hash Standard", Federal Information Processing Standard Publication 180-1, Apr. 17, 1995. cited by other .
"Smard Card Stage 1 Description", Version 1.1, CDMA Development Group-Smart Card Team Document, May 22, 1996. cited by other .
"Digital Cellular Telecommunications Systems(Phase 2+); AT Command Set for GSM Mobile Equipment(ME)", ETSI TS 100 916 V7.4.0, 1998. cited by other .
"Wireless Identity Module Pert: Security" Version 12, Wireless Application Protocol WAP-260-WIM-20010712-a, Jul. 2001. cited by other .
"3.sup.rd Generation Partnership Project: Technical Specification Group Terminals; USIM and IC Card Requirements(Release 4)", 3GPP TS 21.111 V4.0.0, 2001. cited by other .
"3.sup.rd Generation Partnership Project 2: Removable User Identity Module for Spread Spectum Systems" 3GPP2 C.S0023-A, Version 1.0, Sep. 13, 2002, pp. 1-1-5-2, A1-A4. cited by other .
Baase, "Computer Algorithms, Introduction to Design and Analysis", 1988, Addison-Wesley Publishing Company, Second Edition, pp. 11-14. cited by other .
Genet et al., "A Java Card CAP converter in PVS", Sep. 26, 2002, pp. 1-59. cited by other.~
Primary Examiner: Zhen; Wei
Assistant Examiner: Deng; Anna
Attorney, Agent or Firm:Gunnison, McKay & Hodgson, L.L.P. Gunnison; Forrest
Claims

What is claimed is:
1. A method for program verification, the method comprising: receiving a program unit; determining data types used by said program unit; creating a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and using said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.

2. The method of claim 1 wherein said first mapping represents all data types used by said program unit.

3. The method of claim 1 wherein said first mapping represents a subset of data types used by said program unit.

4. The method of claim 1 wherein said first mapping represents most-used data types of said program unit.

5. The method of claim 1 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.

6. The method of claim 1 wherein said program comprises a Java.TM. program.

7. The method of claim 6 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.

8. A method for program verification, the method comprising: step for receiving a program unit; step for determining data types used by said program unit; step for creating a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and step for using said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.

9. The method of claim 8 wherein said first mapping represents all data types used by said program unit.

10. The method of claim 8 wherein said first mapping represents a subset of data types used by said program unit.

11. The method of claim 8 wherein said first mapping represents most-used data types of said program unit.

12. The method of claim 8 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.

13. The method of claim 8 wherein said program comprises a Java.TM. program.

14. The method of claim 13 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.

15. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method for program verification, the method comprising: receiving a program unit; determining data types used by said program unit; creating a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and using said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.

16. The program storage device of claim 15 wherein said first mapping represents all data types used by said program unit.

17. The program storage device of claim 15 wherein said first mapping represents a subset of data types used by said program unit.

18. The program storage device of claim 15 wherein said first mapping represents most-used data types of said program unit.

19. The program storage device of claim 15 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.

20. The program storage device of claim 15 wherein said program comprises a Java.TM. program.

21. The program storage device of claim 20 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.

22. An apparatus for program verification, the apparatus comprising: means for receiving a program unit; means for determining data types used by said program unit; means for creating a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and means for using said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.

23. The apparatus of claim 22 wherein said first mapping represents all data types used by said program unit.

24. The apparatus of claim 22 wherein said first mapping represents a subset of data types used by said program unit.

25. The apparatus of claim 22 wherein said first mapping represents most-used data types of said program unit.

26. The apparatus of claim 22 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.

27. The apparatus of claim 22 wherein said program comprises a Java.TM. program.

28. The apparatus of claim 27 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.

29. An apparatus for communicating program verification, comprising: a memory for storing a program comprising a plurality of program units; and a processor configured to: receive a program unit; determine data types used by said program unit; create a first mapping for said data types, said first mapping comprises a bitmap, each bit in said bitmap representing a data type used by said program unit; and use said first mapping to represent type information in verification information for said program unit, said verification information comprising the data type of at least one entry on an operand stack or in a register file during simulated execution of said program unit.

30. The apparatus of claim 29 wherein said first mapping represents all data types used by said program unit.

31. The apparatus of claim 29 wherein said first mapping represents a subset of data types used by said program unit.

32. The apparatus of claim 29 wherein said first mapping represents most-used data types of said program unit.

33. The apparatus of claim 29 wherein said first mapping is exclusive of data types represented by a second mapping representing data types used by a higher-level program unit.

34. The apparatus of claim 29 wherein said program comprises a Java.TM. program.

35. The apparatus of claim 34 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.

36. A memory for storing data for access by an application program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information used by said program to verify a program unit, said data structure comprising a type mapped representation of data types used by said program unit during simulated execution of said program unit, said type map comprises a bitmap, each bit in said bitmap representing a data type used by said program unit.

37. The memory of claim 36 wherein said representation represents all data types used by said program unit.

38. The memory of claim 36 wherein said representation represents a subset of data types used by said program unit.

39. The memory of claim 36 wherein said representation represents most-used data types of said program unit.

40. The memory of claim 36 wherein said representation is exclusive of data types represented by another type mapped representation representing data types used by a higher-level program unit.

41. The memory of claim 36 wherein said program comprises a Java.TM. program.

42. The memory of claim 41 wherein said program unit comprises one of a package, a class, a method, an instance variable and a class variable.
Description
CROSS REFERENCE TO RELATED APPLICATIONS

This application is related to the following:

U.S. patent application Ser. No. 10/346,581, filed Jan. 16, 2003 in the name of inventor Eduard de Jong, entitled "System for Communicating Program Data Between a First Device and a Second Device", commonly assigned herewith.

U.S. patent application Ser. No. 10/346,230, filed Jan. 16, 2003 in the name of inventor Eduard de Jong, entitled "Signing Program Data Payload Sequence in Program Loading", commonly assigned herewith.

U.S. patent application Se. No. 10/346,238, filed Jan. 16, 2003 in the name of inventor Eduard de Jong, entitled "Using a Digital Fingerprint to Commit Loaded Data in a Device", commonly assigned herewith.

U.S. patent application Ser. No. 10/346,586, filed Jan. 16, 2003 in the name of inventor Eduard de Jong, entitled "Ordering Program Data for Loading on a Device", commonly assigned herewith.

U.S. patent application Ser. No. 10/346,243, filed Jan. 16, 2003 in the name of inventor Eduard de Jong, entitled "Run Time Code Integrity Checks", commonly assigned herewith.

U.S. patent application Ser. No. 10/346,579, filed Jan. 16, 2003 in the name of inventor Eduard de Jong, entitled "Linking of Virtual Methods", commonly assigned herewith.

FIELD OF THE INVENTION

The present invention relates to the field of computer science. More particularly, the present invention relates to optimized representation of data type information in program verification.

BACKGROUND OF THE INVENTION

FIG. 1 is a block diagram that illustrates a typical mechanism for communicating program data between a host computer and a smart card. Smart cards 110 typically communicate with other computers 100 via APDUs (Application Protocol Data Units). The APDU protocol is specified in International Standard ISO/IEC 7816-3. An APDU includes either a command 115 or a response 120 message. A smart card 110 receives a command APDU 115 from a host computer 100, executes the instruction specified in the command 115 and replies to the host computer 100 with a response APDU 120. Command APDUs 115 and response APDUs 120 are exchanged alternately between a card 110 and a host computer 100.

According to the APDU protocol, APDU messages comprise two structures. One structure is used by a host application on a loading terminal to send commands to the card. The other structure is used by the card to send responses back to the host application. The former is referred to as the command APDU (C-APDU) and the latter is referred to as the response APDU (R-APDU). Their structures are illustrated in FIGS. 2A and 2B, respectively. Some C-APDU components are optional.

Java Card.TM. technology enables programs written in the Java.TM. programming language to run on smart cards and other resource-constrained devices. Java Card.TM. technology is described in Z. Chen, Java Card.TM. Technology for Smart Cards (2000).

Turning now to FIG. 3, a block diagram that illustrates loading a converted applet (CAP) file is presented. The Java Card.TM. Virtual Machine (JCVM) comprises an on-card portion that includes the Java Card.TM. bytecode interpreter 345 and an off-card portion called a converter 310. Taken together, the interpreter 345 and the converter 310 implement all the virtual machine functions, including loading Java.TM. class files 300 and executing them with a particular set of semantics. The converter 310 loads and pre-processes the class files 300 that comprise a Java Card.TM. program that may be structured in one or more packages and produces a CAP (converted applet) file 350. The CAP file 350 is then loaded on a Java Card.TM. technology-enabled smart card 330 and executed by the interpreter 345. The CAP file 350 includes an executable binary representation of the classes in a Java.TM. package 350. The Java Card.TM. interpreter 345 provides runtime support of the Java.TM. language execution model.

In Java Card.TM. technology, the mechanisms to download and install a CAP file 350 are embodied in a unit called the installer 340. The Java Card.TM. installer 340 resides within the card 330. It cooperates with an off-card installation program 320. The off-card installation program 320 transmits the executable binary and possibly other data in a CAP file 350 to the installer 340 running on the card 330 via a loading terminal 325. The installer 340 writes the binary into the smart card memory, links it with the other classes that have already been placed on the card 330 and creates and initializes any data structures that are used internally by the Java Card.TM. runtime environment. An optional on-card verifier 335 performs bytecode verification of downloaded code before the downloaded code is interpreted by bytecode interpreter 345.

The APDU protocol limits the size of the payload or data field (reference numeral 240 of FIG. 2) to a small number of bytes (typically less than 128) determined by the restricted size of RAM. Data structures larger than the limitation must be split among the payload portion of multiple APDUs. This splitting is typically performed without regard to the data content. For example, a particular APDU may contain a portion of one data structure and a portion of another data structure. This is explained in more detail below, with reference to FIG. 4.

Turning now to FIG. 4, a flow diagram that illustrates loading a CAP file from the perspective of a loading terminal is presented. At 400, a CAP file is received. At 405, the CAP file and associated authentication data is split amongst multiple APDUs. At 410, the APDUs are transmitted to the target smart card according to the APDU protocol.

Turning now to FIG. 5, a flow diagram that illustrates loading a CAP file from the perspective of a smart card is presented. At 500, the CAP file is reassembled in the smart card. At 505, the reassembled CAP file is decrypted. At 510, the decrypted CAP file data is authenticated. In another solution, the CAP file is authenticated and then decrypted. In yet another solution, the CAP file is communicated without encryption. At 515, the content of the authenticated CAP file is installed on the smart card.

Turning now to FIG. 6, a flow diagram that illustrates reassembling a CAP file in a smart card is presented. At 600, an APDU is received. At 605, the APDU is stored in a persistent mutable memory such as an EEPROM (electrically erasable programmable read-only memory). Alternatively, the APDU payload is not stored in a persistent mutable memory. At 610, receipt of the APDU is acknowledged. At 615, a determination is made regarding whether another APDU needs to be processed. Additional APDUs are processed beginning at 600.

Turning now to FIG. 7, a block diagram that illustrates modifying a stored program having link data to resolve static references is presented. Card memory 700 represents card memory before using embedded link data (704, 712, 728) to link executable code segments (702, 706, 708, 710, 712, 716, 718, 720, 722, 724, 726, 728, 732). Card memory 750 represents card memory after the embedded link data (704, 712, 728) has been used to link executable code segments (702, 706, 708, 710, 712, 716,
718, 720, 722, 724, 726, 728, 732). Referring to card memory 700, method "A1A" code 702 calls method "A1C" 708, method "A2A" code 712 calls method "B1A" 720 and method "B2A" code 728 calls method "B1D" 726. Method "A1A" link data 704 comprises an indication of how to resolve the reference to method "A1C" 708. Method "A1A" link data 704 may additionally comprise an indication of how method "A1A" code 702 must be modified. Likewise, method "A2A" link data 714 comprises an indication of how to resolve the reference to method "B1A" 720. Method "A2A" link data 714 may additionally comprise an indication of how method "A2A" code 712 must be modified. Additionally, method "B2A" link data 730 comprises an indication of how to resolve the reference to method "B1D" 726. Method "B2A" link data 730 may additionally comprise an indication of how method "B2A" code 728 must be modified. Referring to card memory 750 of FIG. 7, symbolic references to called methods have been replaced with the addresses of the called methods and the link data is not stored.

Unfortunately, storing the re-created CAP file in a persistent mutable memory and then processing the CAP file contents to create linked executable code requires a significant amount of available memory and is time consuming.

Accordingly, a need exists in the prior art for a method and apparatus for communicating program data between a host computer and a smart card that is relatively efficient. A further need exists for such a solution that is relatively secure. Yet another need exists for such a solution that detects when program data has been tampered with.

SUMMARY OF THE INVENTION

A method for program verification comprises receiving a program unit, determining data types used by the program unit, creating a first mapping for the data types and using the first mapping to represent type information in verification information for the program unit. The verification information comprises the data type of entries on an operand stack or in a register file during simulated execution of the program unit.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated into and constitute a part of this specification, illustrate one or more embodiments of the present invention and, together with the detailed description, serve to explain the principles and implementations of the invention.

In the drawings:

FIG. 1 is a block diagram that illustrates a typical mechanism for communicating program data between a host computer and a smart card.

FIG. 2A is a block diagram that illustrates a typical Command Application Protocol Data Unit (C-APDU).

FIG. 2B is a block diagram that illustrates a typical Response Application Protocol Data Unit (RAPDU).

FIG. 3 is a block diagram that illustrates loading a converted applet (CAP) file.

FIG. 4 is a flow diagram that illustrates loading a CAP file from the perspective of a loading terminal.

FIG. 5 is a flow diagram that illustrates loading a CAP file from the perspective of a smart card.

FIG. 6 is a flow diagram that illustrates reassembling a CAP file in a smart card.

FIG. 7 is a block diagram that illustrates modifying a stored program having link data to resolve static references.

FIG. 8 is a block diagram of a computer system suitable for implementing aspects of the present invention.

FIG. 9 is a block diagram that illustrates a system for communicating program data between a host computer and a smart card in accordance with one embodiment of the present invention.

FIG. 10 is a high level flow diagram that illustrates communicating program data from a host computer to a smart card in accordance with one embodiment of the present invention.

FIG. 11 is a low level flow diagram that illustrates communicating program data from a host computer to a smart card in accordance with one embodiment of the present invention.

FIG. 12 is a flow diagram that illustrates a method for communicating program data from a host computer to a loading terminal from the perspective of a host computer in accordance with one embodiment of the present invention.

FIG. 13 is a block diagram that illustrates partitioning a CAP file into one or more logical APDUs in accordance with one embodiment of the present invention.

FIG. 14 is a flow diagram that illustrates a method for using program unit type map information in accordance with one embodiment of the present invention.

FIG. 15A is a block diagram that illustrates a CAP file comprising package-structured data.

FIG. 15B is a use diagram corresponding to the program within the CAP file of FIG. 15A.

FIG. 15C is a block diagram that illustrates the CAP file of FIG. 15A ordered based upon the use diagram of FIG. 15B in accordance with one embodiment of the present invention.

FIG. 16 is a flow diagram that illustrates a method for ordering program units for optimized verification and linking in accordance with one embodiment of the present invention.

FIG. 17A is a block diagram that illustrates a CAP file comprising package-structured data.

FIG. 17B is a use diagram corresponding to the program within the CAP file of FIG. 17A.

FIG. 17C is a block diagram that illustrates the CAP file of FIG. 17A ordered based upon the use diagram of FIG. 17B in accordance with one embodiment of the present invention.

FIG. 18 is a flow diagram that illustrates a method for disassembling a CAP file into one or more logical APDUs in accordance with one embodiment of the present invention.

FIG. 19 is a flow diagram that illustrates a method for disassembling a CAP file into one or more logical APDUs including APDUs comprising verification data in accordance with one embodiment of the present invention.

FIG. 20A is a flow diagram that illustrates a method for computing an authentication fingerprint over an APDU data stream where verification APDUs are included in the fingerprint in accordance with one embodiment of the present invention.

FIG. 20B is a flow diagram that illustrates a method for computing an authentication fingerprint over an APDU data stream where verification APDUs are excluded from the fingerprint in accordance with one embodiment of the present invention.

FIG. 21 is a flow diagram that illustrates a method for communicating program data from a host computer to a loading terminal from the perspective of a loading terminal in accordance with one embodiment of the present invention.

FIG. 22 is a flow diagram that illustrates a method for disassembling an augmented CAP file into one or more logical APDUs in accordance with one embodiment of the present invention.

FIG. 23 is a flow diagram that illustrates a method for disassembling an augmented CAP file including verification data into one or more logical APDUs including APDUs comprising verification data in accordance with one embodiment of the present invention.

FIG. 24 is a flow diagram that illustrates a method for disassembling an augmented CAP file not including verification data into one or more logical APDUs including APDUs comprising verification data in accordance with one embodiment of the present invention.

FIG. 25 is a flow diagram that illustrates a method for disassembling an augmented CAP file into one or more logical APDUs including APDUs comprising link data in accordance with one embodiment of the present invention.

FIG. 26 is a flow diagram that illustrates a method for disassembling an augmented CAP file including verification data into one or more logical APDUs including APDUs comprising verification data and APDUs comprising link data in accordance with one embodiment of the present invention.

FIG. 27 is a flow diagram that illustrates a method for disassembling an augmented CAP file not including verification data into one or more logical APDUs including APDUs comprising verification data and APDUs comprising link data in accordance with one embodiment of the present invention.

FIG. 28 is a flow diagram that illustrates a method for creating one or more method link APDUs in accordance with one embodiment of the present invention.

FIG. 29 is a flow diagram that illustrates a method for communicating program data from a loading terminal to a smart card from the perspective of a smart card in accordance with one embodiment of the present invention.

FIG. 30 is a flow diagram that illustrates a method for communicating program data from a loading terminal to a smart card from the perspective of a smart card using an authentication fingerprint that is a HMAC in accordance with one embodiment of the present invention.

FIG. 31 is a flow diagram that illustrates a method for performing load initialization in accordance with one embodiment of the present invention.

FIG. 32 is a flow diagram that illustrates a method for processing a logical APDU stream in accordance with one embodiment of the present invention.

FIG. 33 is a flow diagram that illustrates a method for computing an authentication fingerprint in accordance with one embodiment of the present invention.

FIG. 34 is a flow diagram that illustrates a method for processing a logical APDU in accordance with one embodiment of the present invention.

FIG. 35 is a block diagram that illustrates data structures for linking a program including virtual methods in accordance with one embodiment of the present invention.

FIG. 36 is a block diagram that illustrates modifying a stored program having link data to resolve dynamic references in accordance with one embodiment of the present invention.

FIG. 37 is a flow diagram that illustrates modifying a stored program having link data to resolve dynamic references in accordance with one embodiment of the present invention.

FIG. 38 is a block diagram that illustrates a hierarchy of program unit commitment fingerprints in accordance with one embodiment of the present invention.

FIG. 39 is a block diagram that illustrates a data structure including program code and program unit commitment fingerprints in accordance with one embodiment of the present invention.

FIG. 40 is a block diagram that illustrates a data structure including program code and a load storage commitment fingerprint in accordance with one embodiment of the present invention.

FIG. 41 is a flow diagram that illustrates a method for using a program unit commitment fingerprint to determine whether a program unit may be used, in accordance with one embodiment of the present invention.

FIG. 42 is a flow diagram that illustrates a method for determining whether stored program unit data is valid in accordance with one embodiment of the present invention.

FIG. 43 is a block diagram that illustrates a smart card configured to ensure a called method has been verified prior to execution in accordance with one embodiment of the present invention.

FIG. 44 is a flow diagram that illustrates a method for ensuring a called method has been verified prior to execution in accordance with one embodiment of the present invention.

DETAILED DESCRIPTION

Embodiments of the present invention are described herein in the context of optimized representation of data type information in program verification. Those of ordinary skill in the art will realize that the following detailed description of the present invention is illustrative only and is not intended to be in any way limiting. Other embodiments of the present invention will readily suggest themselves to such skilled persons having the benefit of this disclosure. Reference will now be made in detail to implementations of the present invention as illustrated in the accompanying drawings. The same reference indicators will be used throughout the drawings and the following detailed description to refer to the same or like parts.

In the interest of clarity, not all of the routine features of the implementations described herein are shown and described. It will, of course, be appreciated that in the development of any such actual implementation, numerous implementation-specific decisions must be made in order to achieve the developer's specific goals, such as compliance with application--and business-related constraints, and that these specific goals will vary from one implementation to another and from one developer to another. Moreover, it will be appreciated that such a development effort might be complex and time-consuming, but would nevertheless be a routine undertaking of engineering for those of ordinary skill in the art having the benefit of this disclosure.

In accordance with one embodiment of the present invention, the components, process steps, and/or data structures may be implemented using various types of operating systems (OS), computing platforms, firmware, computer programs, computer languages, and/or general-purpose machines. The method can be run as a programmed process running on processing circuitry. The processing circuitry can take the form of numerous combinations of processors and operating systems, or a stand-alone device. The process can be implemented as instructions executed by such hardware, hardware alone, or any combination thereof. The software may be stored on a program storage device readable by a machine.

In addition, those of ordinary skill in the art will recognize that devices of a less general purpose nature, such as hardwired devices, field programmable logic devices (FPLDs), including field programmable gate arrays (FPGAs) and complex programmable logic devices (CPLDs), application specific integrated circuits (ASICs), or the like, may also be used without departing from the scope and spirit of the inventive concepts disclosed herein.

In accordance with one embodiment of the present invention, the method may be implemented on a data processing computer such as a personal computer, workstation computer, mainframe computer, or high performance server running an OS such as Solaris.RTM. available from Sun Microsystems, Inc. of Santa Clara, Calif., Microsoft.RTM. Windows.RTM. XP and Windows.RTM. 2000, available from Microsoft Corporation of Redmond, Wash., or various versions of the Unix operating system such as Linux available from a number of vendors. The method may also be implemented on a multiple-processor system, or in a computing environment including various peripherals such as input devices, output devices, displays, pointing devices, memories, storage devices, media interfaces for transferring data to and from the processor(s), and the like. In addition, such a computer system or computing environment may be networked locally, or over the Internet.

In the context of the present invention, the term "network" includes local area networks, wide area networks, the Internet, cable television systems, telephone systems, wireless telecommunications systems, fiber optic networks, ATM networks, frame relay networks, satellite communications systems, and the like. Such networks are well known in the art and consequently are not further described here.

In the context of the present invention, a hash function h is commutative if h(x,y)=h(y,x) for all x and y. In other words, the result of the hash function is independent of the argument order.

In the context of the present invention, the term "fingerprint" is defined as the result of a function that identifies or detects one or more changes in a byte sequence. By way of example, a fingerprint may comprise a non-commutative hash of an arbitrary byte sequence or a noncommutative hash of a sequence of one or more byte sequences. As a further example, a fingerprint may comprise a CRC (cyclic redundancy code), a message digest, or the like. Such functions are described in Knuth, D. The Art of Computer Programming, Volume 2: Seminumerical Methods, Chapter 5. Addison Wesley, 1981.

In the context of the present invention, the term "authentication code" is defined as a digital signature, or a Message Authentication Code (MAC) using a block cipher. By way of example, an authentication code may be generated using the DES algorithm (Federal Information Processing Standards Publication 46-3, Data Encryption Standard (DES), Oct. 25, 1999; Federal Information Processing Standards Publication 197, Advanced Encryption Standard (AES), Nov. 26, 2001), the Rijndael algorithm (J. Daemen and V. Rijmen, AES Proposal: Rijndael, AES Algorithm Submission, Sep. 3, 1999), or the like. An authentication code produced as a result of a keyed hash function is an example of an authentication code that is also a fingerprint.

In the context of the present invention, a keyed hash-based message authentication code (HMAC) is defined as a MAC that uses a cryptographic key in conjunction with a hash function. A HMAC is both a fingerprint and a MAC.

In the context of the present invention, the term "authenticated fingerprint" is defined as an authentication code based at least in part on a fingerprint.

In the context of the present invention, the term "authentication fingerprint" is defined as a fingerprint used to create an authenticated fingerprint.

In the context of the present invention, the term "session" or "user session" is defined as a period that begins when a user inserts a secure portable device such as a smart card or the like into a communications device such as a loading terminal or card acceptance device (CAD), and ends when the secure portable device is removed from the communications device. A "session ID" is used to describe an identifier that uniquely identifies such a session. One or more session ID may be used to uniquely identify the same session.

In the context of the present invention, the term "package-structured data" is defined as executable code using Java.TM.-like naming conventions for references to external program units. By way of example, the Java.TM. naming convention for an external class includes a package name followed by the class name.

In the context of the present invention, the term "verification APDU" is defined as an APDU comprising a command and verification data. The verification data is located within the data field (reference numeral 240 of FIG. 2) of the APDU.

In the context of the present invention, the term "link APDU" is defined as an APDU comprising a command and link data. The link data is located within the data field (reference numeral 240 of FIG. 2) of the APDU.

In the context of the present invention, the term "program unit" is defined as an identifiable unit of program behavior. A higher-level program unit may include one or more lower-level program units. For example, a Java.TM. class may include one or more method.

FIG. 8 depicts a block diagram of a computer system 800 suitable for implementing aspects of the present invention. As shown in FIG. 8, computer system 800 includes a bus 802 which interconnects major subsystems such as a central processor 804, a system memory 806 (typically RAM), an input/output (I/O) controller 808, an external device such as a display screen 810 via display adapter 812, serial ports 814 and 816, a keyboard 818, a fixed disk drive 820, a floppy disk drive 822 operative to receive a floppy disk 824, and a CD-ROM player 826 operative to receive a CD-ROM 828. Many other devices can be connected, such as a pointing device 830 (e.g., a mouse) connected via serial port 814 and a modem 832 connected via serial port 816. Modem
832 may provide a direct connection to a server via a telephone link or to the Internet via a POP (point of presence). Alternatively, a network interface adapter 834 may be used to interface to a local or wide area network using any network interface system known to those skilled in the art (e.g., Ethernet, xDSL, AppleTalk.TM.).

Many other devices or subsystems (not shown) may be connected in a similar manner. Also, it is not necessary for all of the devices shown in FIG. 8 to be present to practice the present invention, as discussed below. Furthermore, the devices and subsystems may be interconnected in different ways from that shown in FIG. 8. The operation of a computer system such as that shown in FIG. 8 is readily known in the art and is not discussed in detail in this application, so as not to overcomplicate the present discussion. Code to implement the present invention may be operably disposed in system memory 806 or stored on storage media such as fixed disk 820, floppy disk 824 or CD-ROM 828.

Signature Protocol for Card Loading

Turning now to FIG. 9, a block diagram that illustrates a system for communicating program data between a host computer and a smart card in accordance with one embodiment of the present invention is presented. System 900 comprises a host computer 910, a loading terminal 985 and a smart card 950. Host computer 910 comprises an off-card installer 915 for augmenting a CAP file 980 comprising package-structured data 905 to create an augmented CAP file 920 comprising the package-structured data 925, an authentication fingerprint 940, one or more loading terminal authentication codes 930 and one or more target smart card authentication codes 935. Augmented CAP file 920 may also comprise verification data 945 that verifies CAP file content. Authentication fingerprint 940 is computed over the payload portion of logical APDUs derived from the package-structured data 925. Logical APDUs are illustrated in more detail below with reference to FIG. 13. As explained in more detail below, the similarity of the processes used by host computer 910, loading terminal 985 and target smart card 950 to compute an authentication fingerprint guarantees that if the APDU payload remains the same, the same authentication fingerprint will be generated regardless of the entity performing the computation. Conversely, if the APDU payload changes between when each entity performs the computation, a different fingerprint will be generated, signaling a change in the payload.

According to one embodiment of the present invention, one or more of loading terminal authentication codes 930 and target smart card authentication codes 935 are based at least in part on authentication fingerprint 940. According to another embodiment of the present invention, the authentication fingerprint 940 comprises a keyed hash-based message authentication code (HMAC). According to another embodiment of the present invention, one or more of loading terminal authentication codes 930
and target smart card authentication codes 935 comprise a digital signature computed over augmented CAP file 920, without regard to logical APDUs.

According to embodiments of the present invention, a logical program unit APDU may be followed and/or preceded by one or more APDUs that provide verification information (verification APDU) and/or linking information (link APDU). The verification data may be embedded in the CAP file. Alternatively, the verification data may be computed by the loading terminal. If verification data is included in the CAP file, it may be used to compute an authentication fingerprint. Linking data may also be computed by the loading terminal. Linking data may be based on data obtained from the card, data obtained from the Web, data in the CAP file, or any combination thereof.

Still referring to FIG. 9, loading terminal 985 is configured to receive the augmented CAP file 920, create one or more logical APDUs from package-structured data 925, authenticate the CAP file based at least in part on the loading terminal authentication code 930, create one or more APDUs comprising a selected target smart card authentication code 935 and the authentication fingerprint 940, and communicate the one or more APDUs to target smart card 950.

According to one embodiment of the present invention, host computer 910 communicates an augmented CAP file without verification data. According to another embodiment of the present invention, host computer 910 communicates an augmented CAP file having verification data.

According to one embodiment of the present invention, loading terminal 985 receives an augmented CAP file 920 without verification data, computes verification data and creates one or more verification APDUs. According to another embodiment of the present invention, loading terminal 985 receives an augmented CAP file 920 with verification data and creates one or more verification APDUs. According to another embodiment of the present invention, loading terminal 985 computes link data and creates one or more link APDUs.

According to one embodiment of the present invention, smart card 950 comprises a secure portable device such as a Java Card.TM. technology-enabled smart card, or the like.

According to one embodiment of the present invention, smart card 950 comprises a CDMA technology-enabled smart card. CDMA technology-enabled smart cards are described in Smart Card Stage I Description, Version 1.1, CDMA Development Group--Smart Card Team Document (May 22, 1996).

According to another embodiment of the present invention, smart card 950 comprises a SIM (Subscriber Identity Module card) card. The term "SIM card" describes the smart card used in GSM (Global System for Mobile Communications) mobile telephones. The SIM includes the subscriber's personal cryptographic identity key and other information such as the current location of the phone and an address book of frequently called numbers. The SIM is described in Digital cellular telecommunications system (phase 2+); Specification of the Subscriber Identity Module--Mobile Equipment (SIM-ME) interface, ETSI, GSM 11.11 version 7.4.0, Release 1998.

According to another embodiment of the present invention, smart card 950 comprises a WIM (Wireless Interface Module). A WIM is a smart card in a WAP (Wireless Application Protocol) phone. It is described in Wireless Identity Module Part: Security, WAP-260-WIM-20010712-a, Wireless Application Protocol Forum, Jul. 12, 2001.

According to another embodiment of the present invention, smart card 950 comprises a USIM (Universal Subscriber Identity Module). A USIM is a smart card for a 3GPP (3.sup.rd Generation Partnership Project) mobile phone. It is described in 3rd Generation Partnership Project; Technical Specification Terminals; USIM and IC card requirements, Release 4, 3GPP TS 21.111 V4.0.0 (2001 03).

According to another embodiment of the present invention, smart card 950 comprises a UIM (User Identity Module). A UIM is a smart card for a 3GPP Project 2 (3GPP2) mobile phone. The term "R-UIM" is used when the smart card is removable. A UIM is a super set of the SIM and allows CDMA (Code Division Multiple Access)-based cellular subscribers to roam across geographic and device boundaries. The R-UIM is described in a specification issued by the 3rd Generation Partnership Project 2 (3GPP2) and entitled 3rd Generation Partnership Project 2; Removable User Identity Module (R-UIM) for cdma2000 Spread Spectrum Systems, 3GPP2 C.S0023-0, Jun. 9, 2000.

The above description regarding various mobile phone technologies is not intended to be limiting in any way. Those of ordinary skill in the art will recognize that other user devices may be used.

Turning now to FIG. 10, a high level flow diagram that illustrates communicating program data from a host computer to a smart card in accordance with one embodiment of the present invention is presented. At 1020 an augmented CAP file is prepared. The augmented CAP file may comprise package-structured data and an authentication fingerprint computed over an APDU data stream comprising the package-structured data. Alternatively, the augmented CAP file may comprise package-structured data and at least one authentication code based at least in part on the authentication fingerprint.

According to one embodiment of the present invention, preparing an augmented CAP file (1020) is preceded by determining a loading order of program elements for optimized verification and linking (1015). The load order used in 1015 may be used in
1020 to determine the order of logical APDUs in the computation of the authentication fingerprint. In a Java.TM. environment, the loading order for one or more classes, methods in classes or fields in methods is determined. The program elements may be ordered based at least in part on a use graph of the program in the CAP file. The "use" of a method may comprise, by way of example, calling the method. The "use" of a field may comprise, by way of example, accessing the field. The program elements may also be ordered based at least in part on type map information defined for the program. Type maps are explained in more detail below with reference to FIG. 14. Ordering program elements is explained in more detail below with reference to FIGS. 15A
15C.

Still referring to FIG. 10, at 1025 the augmented CAP file is communicated to a loading terminal. At 1030, the loading terminal receives the augmented CAP file and initializes loading of an applet. At 1035, authenticated applet code is loaded on a target smart card. At 1040, applets are initialized. At 1045, a proof of loading received from the target smart card is processed to determine and record whether the load was successful.

Still referring to FIG. 10, smart card 1050 receives a load request from the loading terminal. At 1055, the smart card processes logical APDUs received from the loading terminal. The processing includes computing an authentication fingerprint over the APDU payload. At 1060, initialization data received from the loading terminal is used to initialize the smart card. At 1065, a proof of loading is sent to the loading terminal.

Turning now to FIG. 11, a low level flow diagram that illustrates communicating program data from a host computer to a smart card in accordance with one embodiment of the present invention. FIG. 11 provides more detail for FIG. 10. More particularly, reference numerals 1106 1116, 1118 1136 and 1140 1150 of FIG. 11 correspond with reference numerals 1020 1025, 1030 1045 and 1050 1065 of FIG. 10, respectively. At 1106, a host computer disassembles a CAP file into logical data units, and the logical data units are partitioned into one or more APDUs. At 1108, an authentication fingerprint is computed over the APDU data stream, as described below with reference to FIGS. 20A and 20B. At 1110, one or more loading terminal authentication codes are created. At 1112, one or more target smart card authentication codes are created. At 1114, the CAP file is augmented with the authentication codes, fingerprint, or both. At 1116, the augmented CAP file is communicated to a loading terminal.

Still referring to FIG. 11, at 1118 the loading terminal receives a load request including the augmented CAP file, an applet ID (AID) or the like, initialization instructions and initialization data. The term "AID" is defined by International Standards Organization (ISO) Standard ISO-IEC 7816-3. At 1120, loading of the applet is initiated. The initiating may include separating any authentication codes and fingerprint from the augmented CAP file and obtaining linking information. Optionally, at 1121 a loading order of program elements for optimized verification and linking is determined. The loading order of program elements may be determined as described with respect to reference numeral 1015 of FIG. 10. Alternatively, the order may be determined from an indicator stored in an augmented CAP file. At 1122, the augmented CAP file is disassembled into one or more logical APDUs. At 1124, the augmented CAP file is authenticated based on a loading terminal authentication code. At 1126, a target authentication code is selected from the target smart card authentication codes in the augmented CAP file based upon the target smart card. At 1128, one or more logical APDUs are communicated to the target smart card. At 1130, the fingerprint or authentication code based on a fingerprint is sent to the smart card. At 1132, the target smart card authentication code is sent to the smart card. At 1134, initialization instructions and load data are sent to the target smart card. At
1136 a proof of loading is received from the target smart card.

According to embodiments of the present invention, processes 1122 and 1124 are performed before processes 1126, 1128 and 1130. However, the order of processes 1126, 1128 and 1130 with respect to one another may be changed.

Still referring to FIG. 11, at 1140 the target smart card receives a load request from the loading terminal and performs load initialization. The load initialization may include receiving the fingerprint or authentication code based on a fingerprint that was sent at 1130. At 1142, logical APDUs received from the loading terminal are processed. The processing includes computing an authentication fingerprint over the logical APDU payload. The processing may also include receiving the fingerprint or authentication code based on a fingerprint that was sent at 1130. At 1144, the received content is authenticated based on the target smart card authentication code. The authenticating may include receiving the fingerprint or authentication code based on a fingerprint that was sent at 1130. At 1146, the received content is committed to memory on the smart card if the received fingerprint and the computed fingerprint matches, and if the received content is properly authenticated. At 1148, initialization data received from the loading terminal is used to initialize the card. At 1150, a proof of loading is sent to the loading terminal.

Alternatively, the processes illustrated in FIGS. 10 and 11 may performed without using loading terminal authentication codes and/or target smart card authentication codes. The decision to use or not use authentication codes may be based at least in part on a level of trust in host computer 1100, loading terminal 1105 and/or smart card 1110. By way of example, if the loading terminal is trusted, the processes illustrated in FIGS. 10 and 11 may be performed without a loading terminal authentication code. Thus if a card issuer uses its own terminals to update a card, a terminal authentication code is not needed since the card issuer can trust terminals which the issuer controls. But if a third party terminal at a point of sale remote from the card issuer is used to update the card and the card has been in the possession of a user, a terminal authentication code may be needed because the card issuer may have little if any control over the terminal. Similarly, if the target smart card is trusted, the processes illustrated in FIGS. 10 and 11 may be performed without a target smart card authentication code.

Additionally, those of ordinary skill in the art will recognize that other mechanisms for creating a terminal authentication code may be used.

According to one embodiment of the present invention, the host computer 1100 and the loading terminal 1105 comprise the same device.

Host Computer

Turning now to FIG. 12, a flow diagram that illustrates a method for communicating program data from a host computer to a loading terminal from the perspective of a host computer in accordance with one embodiment of the present invention is presented. FIG. 12 provides more detail for reference numerals 1015 1025 of FIG. 10 and reference numerals 1106 1116 of FIG. 11. At 1200, a CAP file is received. At 1205, the CAP file is disassembled into one or more logical APDUs. At 1210, an authentication fingerprint is computed over the APDU data stream. Alternatively, the authentication fingerprint may be computed upon creation of a logical APDU (i.e. as part of the CAP file disassembly process 1205). At 1215, the CAP file is augmented to include the authentication fingerprint, at least one data authentication code based at least in part on the authentication fingerprint, or any combination thereof. At 1220, the augmented CAP file is communicated to a loading terminal.

Turning now to FIG. 13, a block diagram that illustrates partitioning a CAP file into one or more logical APDUs in accordance with one embodiment of the present invention is presented. FIG. 13 provides more detail for reference numeral 1205 of FIG. 12. CAP file 1300 is partitioned into one or more APDUs comprising package definition data 1305 for any package in the CAP file. Package definition data may comprise a package identifier. A class within a package is partitioned into one or more APDUs comprising class definition data 1310 for any class in the package. Class definition data may comprise, by way of example, a class identifier, a base class identifier and one or more interface identifiers. For any method in a class, the method is partitioned into one or more APDUs comprising method definition data 1315 and one or more APDUs comprising method code data 1320. For any field in a class, the field is partitioned into one or more APDUs comprising field definition data 1325. For static fields, the fields are also partitioned into one or more APDUs comprising field initialization data 1330.

Method definition data 1315 may comprise, by way of example, a method identifier, a return type identifier, one or more parameter type identifiers and one or more throwable exception type identifiers. Method code data 1320 may comprise, by way of example, executable bytecodes. Field definition data 1325 may comprise, by way of example, a field count, and a field type identifier for each field included in the field count. Field initialization data 1330 may comprise, by way of example, data used to initialize constant data.

According to embodiments of the present invention, one or more APDUs comprising verification data may be associated with a program unit such a package, a class or a method, or the like. The verification information is computed off-card by a host computer or a loading terminal, and loaded onto the card for use at laod time, and possibly for use during programming. The one or more verification APDUs may be inserted in the APDU data stream before the corresponding logical program unit APDUs. The one or more verification APDUs may also be inserted in the APDU data stream after the corresponding logical program unit APDUs. The verification data includes information for use in predicting program behavior during execution. Verification data may include, by way of example, primitive data type information such as bounds on values belonging to a particular data type. Verification data may also include program stack state information, such as the data type of entries on the program stack during simulated execution of the associated method code. The program stack state information may also include one or more reference to classes which are composite data types.

According to one embodiment of the present invention, class verification APDUs supplement verification data in the method verification APDUs for methods in a particular class. Such class verification APDUs may be used, by way of example, when a particular load order results in incomplete verification information availability when performing a per-method verification.

According to another embodiment of the present invention, package verification APDUs supplement verification data in the class verification APDUs for classes in a particular package. Such package verification APDUs may be used, by way of example, when a particular load order results in incomplete verification information availability when performing a per-class verification.

Type Map Information

According to another embodiment of the present invention, verification information is condensed using one or more type maps. The one or more type maps refer to sets of types that are relevant to a particular program unit. The one or more type maps refer to the data type of entries on an operand stack or in a register file during simulated execution of the corresponding code. The type maps allow optimization of verification by using relatively smaller numbers to refer to predefined sets of types as the types used in the corresponding code. This provides a relatively condensed representation of the types that need to be checked during verification of a program unit. This is explained in more detail below, with reference to FIG. 14.

Turning now to FIG. 14, a flow diagram that illustrates a method for using program unit type map information in accordance with one embodiment of the present invention is presented. At 1400, a program unit is received. Using Java.TM. technology as an example, a method, class or package is received. At 1405, the types used by the program unit are determined. At 1410, a mapping for the types is created. At 1415, the program unit mapping information is used in verification information for the program unit.

According to one embodiment of the present invention, program unit type map information is used to represent all type information in a program unit. According to another embodiment of the present invention, program unit type map information is used to represent a subset of type information in a program unit. By way of example, a type map may be used to represent the most-used types in the program unit.

According to one embodiment of the present invention, a type map comprises a bitmap, each bit of the type map representing a particular data type. By way of example, a 16-bit type map may be used to represent 16 types.

According to another embodiment of the present invention, type map information for a lower-level program unit is cumulative with respect to type map information for a higher-level program unit. By way of example, a package-level 4-bit type map may be used to represent the 16 most-used types in a package. A class-level 4-bit type map may be used to represent the 16 most-used types in a class, exclusive of the 16 types represented by the package-level type map. As a further example, a bitmapped package-level 4-bit type map may be used to represent the 4 most-used types in a package. A bitmapped class-level 4-bit type may be used to represent the 4 most-used types in a class, exclusive of the 4 types represented by the package level type map.

According to one embodiment of the present invention, a trailer APDU indicates the last APDU associated with a program unit. According to another embodiment of the present invention, a header APDU precedes one or more APDUs associated with a program unit and defines the expected sequence of logical program unit APDUs to follow.

Program Element Order

FIGS. 15A 17C illustrate determining the order of program elements in a CAP file in accordance with one embodiment of the present invention. FIGS. 15A 17C provide more detail for reference numeral 1015 of FIG. 10 and reference numeral 1121 of FIG. 11. FIG. 15A illustrates a CAP file before ordering, FIG. 15B illustrates a use graph of the program elements in the CAP file of FIG. 15A and FIG. 15C illustrates the ordering of program elements in the original CAP file based at least in part on the use graph of FIG. 15B. According to one embodiment of the present invention, the original CAP file is ordered based at least in part on the corresponding use graph. The ordered file is communicated to the target device. According to another embodiment of the present invention, the original CAP file is modified to include an order indicator that indicates the load order for the CAP file content. The modified CAP file is communicated to the target device. According to another embodiment of the present invention, the original CAP file and an order indicator that indicates the load order for the CAP file content are communicated to the target device.

Turning now to FIG. 16, a flow diagram that illustrates a method for ordering program units for optimized verification and linking in accordance with one embodiment of the present invention is presented. At 1600, a program including multiple program units targeted to a device such as a smart card or the like is received. At 1605, a use graph of the program is obtained. At 1610, the program units are ordered to create an ordered program. The ordering is based at least in part on the use graph obtained at 1605. At 1615, the ordered program is communicated to the device.

According to one embodiment of the present invention, a "depth-first" approach for ordering program elements is followed. Using FIGS. 15A 15C as an example, method A.B.C (1540) is the main method and it calls method A.B.A (1542). Method A.B.A (1542) calls method A.B.B (1544) first and method A.A.B (1546) second. Neither method A.B.B (1544) nor method A.A.B (1546) calls other methods. Method A.B.C (1540) also calls method A.A.A (1548), followed by method A.A.C (1550). Following the use graph of FIG. 15B, and proceeding in a depth-first, left-to-right manner, the resulting order is: A.B.B (1544), A.A.B (1546), A.B.A (1542), A.A.A (1548), A.A.C (1550), A.B.C (1540). This is the order reflected in the ordered package illustrated in FIG.
15C.

FIGS. 17A 17C illustrate determining the order CAP file content based on a use diagram to create a more flattened ordered CAP file. FIGS. 17A 17C are similar to FIGS. 15A 15C except that the ordered CAP file 1502 of FIG. 15C retains the class structure of the original CAP file 1500, whereas the ordered CAP file 1702 of FIG. 17C has been flattened and thus does not retain the original class structure in the CAP file 1700. FIG. 17A illustrates a CAP file comprising package-structured data. FIG. 17B illustrates a use diagram corresponding to the program within the CAP file of FIG. 17A. FIG. 17C illustrates the CAP file of FIG. 17A ordered based upon the use diagram of FIG. 17B in accordance with one embodiment of the present invention.

As shown in FIG. 17C, the first-used method is method A.B.B 1754. The use of method A.B.B 1754 requires class A.B data 1724 and class A.B fields 1726, so this information is placed before method A.B.B 1728 in the ordered CAP file 1702. The next-used method is method A.A.B 1756. The use of method A.A.B 1756 requires class A.A data 1730 and class A.A fields 1733. Since the required class and field data does not occur earlier in the ordered CAP file, the required class and field data is placed before method A.A.B 1734 in the ordered CAP file 1702. Placement of succeeding methods in the ordered CAP file 1702 proceeds according to the order of use, without regard to which class a method belongs to. In the present example, no further class or field data needs to be loaded because class and field data for the only two classes present in the original CAP file 1700 has already been placed in the ordered CAP file 1702.

The program elements and use graph shown in FIGS. 15A 17C are for purposes of illustration only. Those of ordinary skill in the art will recognize a use graph may be used to represent the use of other portions of a program. By way of example, a use graph may also represent the use of fields or other program constructs. Additionally, portions of a program from different packages may be ordered in a fashion similar to that shown in FIG. 17C, with package data for a particular package being positioned in the resulting file before any program units of the package. Also, those of ordinary skill in the art will recognize that many combinations of program elements and calling relationships between those program elements are possible.

According to another embodiment of the present invention, APDUs are arbitrarily ordered, with each APDU including context information. By way of example, an APDU may include information identifying the APDU contents as the fourth method of the second class. Including context information in an APDU facilitates loading all static data first (all the fields, classes and names) and then loading all the methods, ensuring information used by the methods for use in verification and linking is available first.

According to one embodiment of the present invention, a host computer inserts an ordering indicator in an augmented CAP file containing program data. A loading terminal uses the ordering indicator to determine the ordering of APDUs created as a result of the CAP file disassembly process. According to one embodiment of the present invention, the ordering indicator is based at least in part on a use graph of the program. By way of example, type map information may be loaded relatively late in the loading process, thus minimizing the amount of memory required. Alternatively, type map information may be loaded relatively early in the loading process, thus increasing the probability that the type information will be resident on the card when the types are referenced.

According to one embodiment of the present invention, one or more field definition APDUs 1325 and field initialization APDUs 1330 corresponding to a particular class are processed before any corresponding method definition APDU 1315 or method code APDU 1320 of the class.

CAP File Disassembly

FIGS. 18 and 19 are flow diagrams that illustrate disassembling a CAP file into logical APDUs from the perspective of a host computer in accordance with embodiments of the present invention. FIG. 18 illustrates disassembling a CAP file that does not include verification data and FIG. 19 illustrates disassembling a CAP file that includes verification data.

Turning now to FIG. 18, a flow diagram that illustrates a method for disassembling a CAP file into logical APDUs in accordance with one embodiment of the present invention is presented. The process illustrated within box 1800 is performed per package. At 1805, one or more package definition APDUs comprising package definition data are created for a package. The process illustrated within box 1810 is performed per class. At 1815, one or more class definition APDUs comprising class definition data are created for a class. At 1820, one or more field definition APDUs comprising field definition data are created for the class. The process illustrated within box 1825 is performed per method. At 1835, one or more method definition APDUs comprising method definition data are created for a method. At 1840, one or more code APDUs comprising the method code are created for the method. At 1830, one or more data initialization APDUs are created.

According to embodiments of the present invention, verification data may be created for program units. The verification data may be created for program units such as packages, classes, methods, or the like, or any combination thereof. As mentioned previously, the verification data for a program unit may be inserted in an APDU stream before the corresponding program unit code APDU or program unit definition APDU. In one embodiment, the verification data is inserted immediately before the corresponding program unit code APDU or program unit definition APDU. Alternatively, the verification data for a program unit may be inserted in an APDU stream after the corresponding program unit code APDU or program unit definition APDU. In one embodiment, the verification data is inserted immediately after the corresponding program unit code APDU or program unit definition APDU. This is explained in more detail below with reference to FIG. 19.

Turning now to FIG. 19, a flow diagram that illustrates a method for disassembling a CAP file into logical APDUs including APDUs comprising verification data in accordance with one embodiment of the present invention is presented. FIG. 19 is similar to FIG. 18, except that verification data is included in FIG. 19 at reference numerals 1940, 1945 and 1955. The process illustrated within box 1900 is performed per package. At 1905, one or more package definition APDUs comprising package definition data are created for a package. The process illustrated within box 1910 is performed per class. At 1915, one or more class definition APDUs comprising class definition data are created for a class. At 1920, one or more field definition APDUs comprising field definition data are created for the class. The process illustrated within box 1925 is performed per method. At 1930, one or more method definition APDUs comprising method definition data are created for a method. At 1935, one or more code APDUs comprising the method code are created for the method. At 1940, one or more method verification APDUs comprising method verification data are created for a method. At 1945, one or more class verification APDUs comprising class verification data are created for a class. At 1950, one or more data initialization APDUs are created. At 1955, one or more package verification APDUs comprising package verification data are created for a package.

According to embodiments of the present invention, one or more verification APDUs are inserted into the APDU stream before and/or after the corresponding one or more code or definition APDUs. Using FIG. 19 as an example, one or more package verification APDUs may be inserted into the APDU stream (1955) after inserting the corresponding one or more package definition APDUs (1905). Alternatively, one or more package verification APDUs may be inserted into the APDU stream before inserting the corresponding one or more package definition APDUs. Similarly, one or more class verification APDUs may be inserted into the APDU stream (1945) after inserting the corresponding one or more class definition APDUs (1915). Alternatively, one or more class verification APDUs may be inserted into the APDU stream before inserting the corresponding one or more class definition APDUs. As a further example, one or more method verification APDUs may be inserted into the APDU stream (1940) after inserting the corresponding one or more method definition APDUs (1930). Alternatively, one or more method verification APDUs may be inserted into the APDU stream before inserting the corresponding one or more method definition APDUs. A verification APDU that precedes or succeeds the corresponding one or more code or definition APDUs may comprise, by way of example, one or more type maps.

FIGS. 20A and 20B are flow diagrams that illustrate methods for computing an authentication fingerprint over an APDU data stream in accordance with embodiments of