Dynamic verification of validity of executable code

• US 7,984,304 B1
• Filed: 03/02/2004
• Issued: 07/19/2011
• Est. Priority Date: 03/02/2004
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Waldspurger, Carl A., Garfinkel, Tal, Zedlewski, John R., Chen, Xiaoxin, Agesen, Ole
• Primary Examiner(s): Orgad; Edan
• Assistant Examiner(s): TURCHEN, JAMES R
• Application Number:
  US10/791,602
• Time in Patent Office: 2,695 Days
• Field of Search: 713/187, 726/23, 726/24, 717/124, 717/126, 717/127
• US Class Current: 713/187
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 21/565 by checking file integrity

Abstract

Computer-executable instructions in a computer are verified dynamically, after they have been identified for submission for execution, but before they are actually executed. In particular, for at least one current instruction that has been identified for submission to the processor for execution, an identifying value, for example, a hash value, is determined for a current memory block that contains the current instruction. The identifying value of the current memory block is then compared with a set of reference values. If the identifying value satisfies a validation condition, then execution of the current instruction by the processor is allowed. If the validation condition is not satisfied, then a response is generated: In the common case, execution of the current instruction is not allowed, or some other predetermined measure is taken.

Claims

1. A method for protecting a computer from unauthorized code, the computer including at least one processor that executes instructions stored in a memory that is organized into separately addressable pages of memory, the method comprising:

executing a program, the program having a series of computer-executable instructions executed by the at least one processor, the at least one processor residing in a system hardware platform;

verifying that the program is valid using a verification engine including verification instructions for execution on the at least one processor residing in the system hardware platform, the program being valid when the program does not include the unauthorized code, wherein the verification engine resides in a system software layer, the system software layer performing hardware-interface and resource-allocating functions;

ensuring that the program is not executed without also dynamically performing the verifying; and

continuing execution of the program after dynamically performing the verifying by executing the next instruction as long as the verifying determines that the program is valid and generating a protective response when the verifying does not determine that the program is valid;

wherein the verifying that the program is valid comprises executing the verification instructions of the verification engine, the verification instructions causing the at least one processor to perform a method comprising;

identifying the next instruction to be executed in the program;

for the next instruction to be executed in the program, determining an identifying value for a page of memory that contains the next instruction;

determining whether the identifying value satisfies a validation condition, wherein the determining as to whether the identifying value satisfies the validation condition comprises comparing the identifying value of the page of memory with a set of reference values; and

determining that the program is valid only when the validation condition is satisfied.

2. The method of claim 1, wherein the validation condition is that the identifying value of the page of memory matches any reference value in the set of reference values.

3. The method of claim 1, wherein the validation condition is that the identifying value of the page of memory differs from each reference value in the set of reference values.

4. The method of claim 1, wherein the verifying that the program is valid further comprises:

for each of the separately addressable pages of memory, indicating in a structure whether the page is valid;

accessing the structure to determine whether the page of memory is valid prior to the determining of the identifying value; and

performing the determining of the identifying value when the structure does not indicate that the page of memory is valid and directly allowing execution of the next instruction when the structure indicates that the page of memory is valid.

5. The method of claim 4, wherein the structure comprises a group of hardware attribute indicators, and wherein the indicating in the structure whether the plurality of pages of memory are validated comprises setting one of the hardware attribute indicators, the one hardware attribute indicator corresponding to the page of memory.

6. The method of claim 5, in which the hardware attribute indicators are execute and write permission attributes associated with an entry in a translation lookaside buffer.

7. The method of claim 4, wherein the structure comprises a software data structure, and wherein the indicating in the structure whether the plurality of pages of memory are validated comprises making a corresponding entry in the software data structure.

8. The method of claim 4, wherein the determining of the identifying value for the page of memory and the determining of whether the identifying value satisfies the validation condition are performed only when the structure does not indicate that the page of memory is valid, the method further comprising:

when the structure does not indicate that the page of memory is valid, modifying the structure to indicate that the page of memory is valid when the identifying value satisfies the validation condition.

9. The method of claim 8, further comprising:

sensing modification of one of the pages of memory that the structure indicates is valid and, in response to the modification, setting its indication in the structure to indicate that the page of memory is not valid.

10. The method of claim 4, wherein the verifying that the program is valid further comprises:

determining a branch history for the next instruction; and

checking whether the pages of memory in which instructions in the branch history are located are valid, the validation condition including the requirement that each checked in the branch history is valid.

11. The method of claim 1, wherein the determining of the identifying value and the determining as to whether the validation condition has been satisfied are performed only after a triggering event occurs.

12. The method of claim 11, wherein the triggering event is writing of at least one new unit of code or data to any physical component within the computer.

13. The method of claim 11, in which the triggering event is an attempted execution of any instruction located on any unverified page of memory.

14. The method of claim 11, wherein the triggering event is an attempted execution of any instruction located on any unverified page of memory of newly installed software.

15. The method of claim 11, further comprising triggering the verification of the computer instructions depending on an identity of a user of the computer, the user having caused the next instruction to be identified for execution.

16. The method of claim 11, further comprising triggering dynamic verification depending on a context in which the next instruction is submitted for execution, wherein the context is a level of security clearance associated with the computer, a user of the computer, or a program of which the next instruction is a part.

17. The method of claim 1, wherein the identifying of the next instruction is performed for only a sample of the series of instructions.

18. The method of claim 17, wherein the sample is a time-sampled subset of the series of instructions.

19. The method of claim 17, wherein the sample is a sequentially sampled subset of the series of instructions.

20. The method of claim 17, wherein the sample is a subset of the series of instructions sampled spatially, the sampling being over a range of page of memory identifiers.

21. The method of claim 1, wherein the protective response comprises termination of a software entity with which the current page of memory is associated.

22. The method of claim 1, wherein the protective response comprises suspension of execution of a software entity with which the current page of memory is associated.

23. The method of claim 1, wherein the protective response comprises a message posted to a user, system administrator, or other predetermined recipient.

24. The method of claim 1, wherein:

the computer includes a virtual machine running in a direct execution mode on an underlying hardware platform via an intermediate software layer; and

the protective response comprises a switching of an execution mode of the virtual machine from the direct execution mode to a binary translation mode.

25. The method of claim 1, wherein:

the computer includes a virtual machine running on the underlying hardware platform via an intermediate software layer; and

the protective response includes checkpointing the state of the virtual machine.

26. The method of claim 1, wherein the protective response is a first possible response, the method further comprising:

associating the first possible response with the page of memory;

associating a second possible response with a different page of memory; and

upon detection of failure of the next instruction to satisfy the validation condition, identifying which one of the possible responses is associated with the page of memory, and generating the one possible response associated with the page of memory in which the next instruction is located.

27. The method of claim 1, further comprising:

associating reference values from the set of reference values with respective programs such that each association signifies that the reference value corresponds to a page of memory storing instructions for one of the programs; and

tracking which of the respective programs is being executed and the association between the matching reference value and the corresponding one of the programs.

28. The method of claim 1, wherein:

the computer includes a virtual machine (VM) running on the underlying hardware platform via the system software layer operable to switch the virtual machine between a direct execution mode and a binary translation mode; and

the series of instructions comprise VM-is sued instructions issued in conjunction with binary translation of any of the VM-issued instructions, the VM-issued instructions thereby being verified.

29. The method of claim 1, wherein the identifying value is a hash value that is computed as a function of all contents of the page of memory.

30. The method of claim 1, wherein the identifying value is a hash value that is computed as a function of contents of the page of memory such that some of the contents of the page of memory are ignored when computing the hash value, the ignored portion being defined by a subset selection structure.

31. The method of claim 1, wherein ensuring that the program is not executed without dynamically performing the verifying comprises interrupting execution of the series of computer-executable instructions of the program while dynamically performing the verifying to execute the verification instructions of the verification engine using the at least one processor to perform.

32. The method of claim 1, wherein:

the series of computer-executable instructions belong to an instruction set associated with the at least one processor, and

the verification instructions belong to the instruction set associated with the at least one processor.

33. The method of claim 1, wherein the dynamically performing of the verifying is initiated from the system software layer.

34. A method for protecting a computer from unauthorized code, the computer including at least one processor that executes instructions stored in memory that is organized into separately addressable pages of memory, the method comprising:

executing a program, the program having a series of computer-executable instructions;

verifying that the program is valid as the program executes, the program being valid when the program does not include the unauthorized code, the verifying based on a current instruction to be executed when executing the series of instructions in the program;

generating a protective response when the verifying determines that the program is not valid; and

executing the current instruction when the verifying determines that the program is valid;

wherein the verifying that the program is valid comprises;

identifying the current instruction to be executed when executing the series of instructions, the current instruction being one of the series of instructions being executed identified for submission to the processor for execution and not yet executed at a time of the identifying;

for at least the current instruction, computing a hash value as a function of a subset of contents of a current page of memory that contains the current instruction;

determining, during the executing of the series of instructions, whether the hash value satisfies a validation condition by comparing the hash value of the current page of memory with a set of reference values; and

determining that the program is valid when the hash value satisfies the validation condition, and determining that the program is not valid when the hash value does not satisfy the validation condition;

wherein the computing of the hash value comprises applying a mask to the current page of memory, the mask being a data structure that designates at least one byte of the current page of memory to be ignored in the computing of the hash value, the data structure designating less than an entire page of memory so that the hash value is based on only part of the contents of the current page of memory.

35. The method of claim 34, further comprising:

identifying, an indeterminate portion of the current page of memory, the indeterminate portion being non-indicative of validity of the current page of memory as a whole; and

configuring the mask so that the mask designates at least the indeterminate portion to be ignored when generating the hash value.

36. A non-transitory machine readable storage medium embodying executable code for protecting a computer from unauthorized code, the computer including at least one processor that executes instructions stored in a memory that is organized into separately addressable pages of memory, the executable code being a verification engine causing the computer to perform a method having operations of:

executing a program, the program having a series of computer-executable instructions executed by the at least one processor, the at least one processor residing in a system hardware platform;

verifying that the program is valid using a verification engine including verification instructions for execution on the at least on processor residing in the system hardware platform, the program being valid when the program does not include the unauthorized code, wherein the verification engine resides in a system software layer, the system software layer performing hardware-interface and resource-allocating functions;

ensuring that the program is not executed without also dynamically performing the verifying, the verifying based on a next instruction to be executed in the series of computer-executable instructions in the program; and

continuing execution of the program as long as the verifying determines that the program is valid and generating a protective response when the verifying does not determine that the program is valid;

wherein the verifying that the program is valid comprises executing the verification instructions of the verification engine, the verification instructions causing the at least one processor to perform a method comprising;

identifying the next instruction of the series of computer-executable instructions to be executed when executing the program;

for the next instruction, and during the execution of the program, determining an identifying value for a page of memory that contains the next instruction;

determining whether the identifying value satisfies a validation condition, wherein the determining as to whether the identifying value satisfies the validation condition comprises comparing the identifying value of the page of memory with a set of reference values; and

determining that the program is valid only when the validation condition is satisfied.

37. The machine readable storage medium of claim 36, wherein the validation condition is that the identifying value of the page of memory matches any reference value in the set of reference values.

38. The machine readable storage medium of claim 36, wherein the validation condition is that the identifying value of the page of memory differs from each reference value in the set of reference values.

39. The machine readable storage medium of claim 36, wherein:

the identifying value is a hash value that is computed as a function of contents of the page of memory.

40. The machine readable storage medium of claim 39, wherein some of the contents of the page of memory are ignored when computing the hash value, the ignored portion being defined by a subset selection structure.

41. The machine readable storage medium of claim 40, wherein the subset selection structure is a mask.

42. The machine readable storage medium of claim 36, wherein the verifying that the program is valid further comprises:

for each of the separately addressable pages of memory, indicating in a structure whether the is valid;

accessing the structure to determine whether the page of memory is valid prior to the determining of the identifying value; and

performing the determining of the identifying value when the structure does not indicate that the page of memory is valid and directly allowing execution of the next instruction when the structure indicates that the page of memory is valid.

43. The machine readable storage medium of claim 42, wherein the structure comprises a group of hardware attribute indicators, and wherein the indicating in the structure whether the plurality of pages of memory is valid comprises setting one of the hardware attribute indicators corresponding to the page of memory.

44. The machine readable storage medium of claim 43, in which the hardware attribute indicators are execute and write permission attributes associated with an entry in a translation lookaside buffer.

45. The machine readable storage medium of claim 42, wherein the structure comprises a software data structure, and wherein the verifying further comprises selecting for verification only a sample of the next instructions.

46. The machine readable storage medium of claim 36, wherein:

the verification engine resides in an intermediate virtualization layer in the system software layer between a virtual machine and the hardware platform of the computer;

the next instruction is issued by the virtual machine; and

the verifying that the program is valid is performed while copying or translating in conjunction with binary translation of instructions for the virtual machine.

47. The machine readable storage medium of claim 46, wherein the protective response comprises switching the intermediate virtualization layer to a binary translation mode.

48. A method for verifying the validity of instructions in a computer that includes at least one physical processor that executes instructions stored in a memory of the computer, the memory being organized into separately addressable pages of memory, the computer also including system software and verification software residing in a system software layer, the verification software including verification instructions for execution on the at least one physical processor residing in a system hardware platform, the method comprising:

monitoring instructions to be executed by the at least one physical processor under control of the system software layer, the system software layer performing hardware-interface and resource-allocating functions;

as long as the instructions to be executed under control of the system software are stored in one or more pages of memory for which validation is deemed unnecessary, allowing the instructions to be executed under control of the system software on the at least one physical processor; and

detecting that an unvalidated instruction is to be executed under control of the system software, the unvalidated instruction being stored in a page of memory that has not been validated, and, before allowing the unvalidated instruction to execute, attempting to validate the unvalidated by executing the verification instructions of the verification software in the system software layer, the verification instructions causing the at least one physical processor to perform a method comprising;

determining an identifying value for the unvalidated page of memory;

comparing the identifying value of the unvalidated page of memory with a set of reference values;

if the identifying value satisfies a validation condition, allowing execution after satisfying the validation condition, under control of the system software layer, of instructions stored in the unvalidated page of memory; and

if the identifying value does not satisfy the validation condition, generating a response.

49. The method of claim 48, wherein the validation condition is that the identifying value of the page of memory matches any reference value in the set of reference values.

50. The method of claim 48, wherein the validation condition is that the identifying value of the page of memory differs from each reference value in the set of reference values.

51. The method of claim 48, wherein the determining of the identifying value comprises computing a hash value as a function of contents of the unvalidated page of memory, the identifying value being the hash value.

52. The method of claim 51, wherein some of the contents of the unvalidated page of memory are ignored when computing the hash value, the ignored portion being defined by a subset selection structure.

53. The method of claim 52, wherein the subset selection structure is a mask.

54. The method of claim 48, wherein the detecting that an unvalidated instruction is to be executed comprises:

for each of the separately addressable pages of memory, indicating in a structure whether the page of memory is valid;

accessing the structure to determine whether one of the pages of memory containing the instructions to be executed is valid prior to the determining of the identifying value; and

detecting that the instruction to be executed is unvalidated when the structure does not indicate that the page of memory that contains the instruction to be executed is valid.

55. The method of claim 54, wherein the structure comprises a group of hardware attribute indicators, and wherein the indicating in the structure whether the page of memory is valid comprises setting one of the hardware attribute indicators corresponding to the page of memory.

56. The method of claim 54, wherein the structure comprises a software data structure.

57. The method of claim 48, wherein:

the verification software resides in an intermediate virtualization layer of the system software layer between a virtual machine and a hardware platform of the computer;

the instructions to be executed that are being monitored comprise instructions issued by the virtual machine; and

the verifying of the validity of the instructions is carried out while copying or translating in conjunction with binary translation of the instructions to be executed.

58. The method of claim 48, wherein the detecting that an unvalidated instruction is to be executed further comprises:

determining a branch history for the unvalidated instruction; and

checking whether pages of memory in which instructions in the branch history are located are valid, the validation condition including the requirement that each checked page of memory in the branch history is valid.

59. The method of claim 48, wherein monitoring of the instructions to be executed and the detecting that the unvalidated instruction is to be executed are performed only after a triggering event occurs.

60. A method for protecting a computer from unauthorized code, the computer including at least one processor that executes instructions stored in a memory, the memory being organized into separately addressable pages of memory, the method comprising:

setting execute permission indicators for the separately addressable pages of memory in a structure, wherein an execute permission indicator for a page of memory indicates whether the page of memory is valid;

executing a program, the program having a series of computer-executable instructions being executed by the at least one processor;

determining when the program attempts to execute an instruction on a page of memory in which an indicator for the page of memory does not indicate that the page of memory is valid;

dynamically verifying that the page of memory is valid, the page of memory being valid when the page of memory does not include unauthorized code; and

continuing execution of the program after dynamically performing the verifying by executing the instruction as long as the verifying determines that the page of memory is valid and generating a protective response when the verifying determines that the program is not valid.

61. The method of claim 60, wherein the structure stores the execute permission indicators in a hardware structure, the method further comprising inspecting the hardware data structure to determine if the execute permission indicator indicates whether the page of memory is valid.

62. The method of claim 61, further comprising receiving a fault generated by the at least one processor, the fault being generated when the program attempts to execute the instruction on the page of memory in which the indicator for the page of memory does not indicate the page of memory is valid,

wherein the verifying is performed upon receiving the fault.

63. The method of claim 60, further comprising:

setting access control indicators for pages of memory marked as valid by the execute permission indicators;

determining a modification to a page of memory marked as valid, the modification violating the access control indicator for the page of memory; and

changing the execute permission indicator for the modified page of memory to indicate that the modified page of memory is not valid in response to determining the modification.

64. The method of claim 63, wherein the access control indicator indicates the page of memory is read-execute only.

65. The method of claim 60, wherein the structure comprises a software data structure, the method further comprising inspecting the software data structure to determine if the execute permission indicator indicates whether the page of memory is valid.

66. The method of claim 60, wherein the computer includes a virtual machine running in a direct execution mode on an underlying hardware platform via an intermediate software layer.

67. A method for protecting a computer from unauthorized code, the computer including at least one processor that executes instructions stored in a memory, the memory being organized into separately addressable pages of memory, the method comprising:

during execution of a program having a series of computer-executable instructions being executed by the at least one processor, determining one or more pages of memory from the separately addressable pages of memory to translate;

verifying, before the one or more pages of memory are stored in a translation lookaside buffer, that the one or more pages of memory are valid, the one or more pages of memory being valid when the one or more pages of memory do not include unauthorized code;

storing the one or more pages of memory in a translation lookaside buffer;

determining an instruction for execution;

determining if the instruction is found in a page of memory stored in the translation lookaside buffer; and

if the instruction is found in a page of memory stored in the translation lookaside buffer, executing the instruction without verifying of the page of memory.

68. The method of claim 67, further comprising setting one or more access control indicators for the one or more pages of memory stored in the translation lookaside buffer.

69. The method of claim 68, wherein the one or more access control indicators indicate the one or more pages are read-execute only.

70. The method of claim 69, wherein upon a write to a page of memory of the one or more pages of memory, the method further comprising:

removing the page of memory from the translation lookaside buffer, wherein verifying is performed before the page of memory is re-stored in the translation lookaside buffer.

71. The method of claim 67, wherein:

the computer includes a virtual machine (VM) running on an underlying hardware platform via an intermediate software layer; and

the series of instructions comprise VM-is sued instructions issued in conjunction with binary translation of any of the VM-issued instructions, wherein it is determined if the VM-issued instructions are found in a page of memory stored in the translation lookaside buffer.