Method and system for hardware based program flow monitor for embedded software

• US 7,861,305 B2
• Filed: 02/07/2007
• Issued: 12/28/2010
• Est. Priority Date: 02/07/2007
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Weber, Samuel M., Palmer, Elaine R., McIntosh, Michael G., Toll, David, Paradkar, Amitkumar M., McIntosh, Suzanne, Brand, Daniel, Kaplan, Matthew, Karger, Paul A.
• Primary Examiner(s): Korzuch; William R
• Assistant Examiner(s): Vaughan; Michael R
• Application Number:
  US11/672,288
• Publication Number:
  US 20080189530A1
• Time in Patent Office: 1,420 Days
• Field of Search: None
• US Class Current: 726/24
• CPC Class Codes: G06F 11/28 by checking the correct order of processing G06F11/08 - G06F11/26 take precedence; monitoring patterns of pulse trains H03K5/19
• CPC Class Codes: G06F 21/563 by source code analysis

Abstract

A method for malware detection, wherein the method includes: utilizing a hardware based program flow monitor (PFM) for embedded software that employs a static analysis of program code; marrying the program code to addresses, while considering which central processing unit (CPU) is executing the program code; capturing an expected control flow of the program code, and storing the control flow as physical address pairs of leaders and followers (LEAD-FOLL pair) in a Metadata Store (MDS) within the PFM; monitoring control flow at runtime by the PFM; and comparing runtime control flow with the expected control flow.

Claims

1. A method for malware detection, wherein the method comprises:

utilizing a hardware based program flow monitor (PFM) for embedded software that employs a static analysis of program code;

marrying the program code to addresses, while considering which central processing unit (CPU) is executing the program code;

capturing an expected control flow of the program code, and storing the control flow as physical address pairs of leaders and followers (LEAD-FOLL pair) in a Metadata Store (MDS) within the PFM;

monitoring control flow at runtime by the PFM;

comparing runtime control flow with the expected control flow; and

wherein the method further comprises;

a) receiving a series of instruction addresses fetched by the central processing unit (CPU) into a logic unit (LU) within the PFM;

b) latching by the LU of each of the series of instruction addresses placed on an address bus by the CPU on completion of a read operation, and storing the latched address in a register file (RF);

c) storing at PFM power up the first address the CPU fetches to a first location in the RF, the highest program address referenced by a Metadata Store (MDS) into a second location in the RF, and latching the next instruction address fetched by the CPU into a third location in the RF;

d) performing a lookup of the address contained in the first location in the MDS;

e) generating an alarm if the address in the first location is greater than the address stored in the second location;

f) generating an alarm if the address in the first location is not found in the MDS;

g) generating an alarm if the address in the first location is found in the MDS, but the address in the third location is not listed as a valid follower;

h) copying the address in the third location to the first location if the LEAD-FOLL pair is found in the MDS;

i) latching by the LU of the next instruction address fetched by the CPU and storing it in the third location;

j) repeating steps d-j, until the program code has been fully executed by the PFM.

2. The method of claim 1, wherein the storing the control flow as physical address pairs of leaders and followers comprises:

metadata burned into read only memory (ROM), or captured in a non-volatile, non-programmable memory device where the metadata is protected from modification once programmed.

3. The method of claim 1, wherein each leader has at least one follower, where the follower is the address of the next instruction to be carried out;

and

wherein a leader can be a member of more than one LEAD-FOLL pair.

4. An article comprising non-transitory machine-readable storage media containing instructions that when executed by a processor enable the processor to provide malware detection, wherein the instructions cause implementation of:

utilizing a hardware based program flow monitor (PFM) for embedded software that employs a static analysis of program code;

marrying the program code to addresses, while considering which central processing unit (CPU) is executing the program code;

capturing an expected control flow of the program code, and storing the control flow as physical address pairs of leaders and followers (LEAD-FOLL pair) in a Metadata Store (MDS) within the PFM;

monitoring control flow at runtime by the PFM; and

comparing runtime control flow with the expected control flow;

wherein the instructions further cause implementation of;

a) receiving a series of instruction addresses fetched by the central processing unit (CPU) into a logic unit (LU) within the PFM;

b) latching by the LU of each of the series of instruction addresses placed on an address bus by the CPU on completion of a read operation, and storing the latched address in a register file (RF);

c) storing at PFM power up the first address the CPU fetches to a first location in the RF, the highest program address referenced by a Metadata Store (MDS) into a second location in the RF, and latching the next instruction address fetched by the CPU into a third location in the RF;

d) performing a lookup of the address contained in the first location in the MDS;

e) generating an alarm if the address in the first location is greater than the address stored in the second location;

f) generating an alarm if the address in the first location is not found in the MDS;

g) generating an alarm if the address in the first location is found in the MDS, but the address in the third location is not listed as a valid follower;

h) copying the address in the third location to the first location if the LEAD-FOLL pair is found in the MDS;

i) latching by the LU of the next instruction address fetched by the CPU and storing it in the third location;

j) repeating steps d-j, until the program code has been full executed by the PFM.

5. A system for malware detection, the system comprising:

a hardware based program flow monitor (PFM) for embedded software that employs a static analysis of program code;

the PFM marrying the program code to addresses, while considering which central processing unit (CPU) is executing the program code;

the PFM capturing an expected control flow of the program code, and storing the control flow as physical address pairs of leaders and followers (LEAD-FOLL pair) in a Metadata Store (MDS) within the PFM;

wherein the PFM further comprises;

a logic unit (LU);

and

a register file (RF)

wherein the PFM performs a process of;

a) receiving a series of instruction addresses fetched by the CPU into the LU within the PFM;

b) latching by the LU of each of the series of instruction addresses placed on an address bus by the CPU on completion of a read operation, and storing the latched address in the RF;

c) storing at PFM power up the first address the CPU fetches to a first location in the RF, the highest program address referenced by the MDS into a second location in the RF, and latching the next instruction address fetched by the CPU into a third location in the RF;

d) performing a lookup of the address contained in the first location in the MDS;

e) generating an alarm if the address in the first location is greater than the address stored in the second location;

f) generating an alarm if the address in the first location is not found in the MDS;

g) generating an alarm if the address in the first location is found in the MDS, but the address in the third location is not listed as a valid follower;

h) copying the address in the third location to the first location if the LEAD-FOLL pair is found in the MDS;

i) latching by the LU of the next instruction address fetched by the CPU and storing it in the third location;

j) repeating steps d-j, until the program code has been fully executed by the PFM.

6. The system of claim 5, wherein:

the MDS is never modified during program execution.

7. The system of claim 5, wherein:

the MDS may be reprogrammed offline only.

8. The system of claim 5, wherein:

the MDS is a read-only memory device (ROM) accessible only by the PFM.

9. The system of claim 5, wherein:

the MDS has metadata specific to a given executable image that is collected offline and used at runtime by the LU to continuously monitor program flow by monitoring program memory addresses fetched.

10. The system of claim 5, wherein:

the PFM detects faulty hardware as well as the presence of malware in embedded software.

11. The system of claim 5, wherein:

the PFM is for use in embedded devices and can be applied in both single and multi-core processors.

12. The system of claim 5, wherein the RF further comprises:

a leader (LEAD) register for storing instruction addresses;

a follower (FOLL) register for storing the next address of the instruction to be executed based on the instruction address stored in the LEAD register;

a return address (RETADDR) for storing an address for a return from an interrupt instruction; and

a maximum address (MAXADDR) for storing the highest address in the program code.

13. The system of claim 5, wherein:

the LU takes as input instruction address lines, data pre-programmed into the MDS, and the data in the RF; and

wherein the LU updates a set of registers in the RF to record state changes.