Optimized representation of data type information in program verification

• US 7,165,246 B2
• Filed: 01/16/2003
• Issued: 01/16/2007
• Est. Priority Date: 01/16/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: de Jong, Eduard
• Primary Examiner(s): Zhen; Wei
• Assistant Examiner(s): DENG, ANNA CHEN
• Application Number:
  US10/346,227
• Publication Number:
  US 20040143820A1
• Time in Patent Office: 1,461 Days
• Field of Search: 717165-167, 717177-178, 717/116, 717/118, 365/200, 711/206, 726/20, 707/1, 707/10, 709/203, 709/229, 705/75
• US Class Current: 717/166
• CPC Class Codes: G06F 9/44589 Program code verification, e.g. Java bytecode verification, proof-carrying code high-level semantic checks G06F8/43; testing and debugging software G06F11/36

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.

Claims

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™

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™

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™

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™

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™

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™

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.