Securing software by enforcing data flow integrity

Patent metadata

Field	Value
Publication number	US-9390261-B2
Application number	US-30618807-A
Country	US
Kind code	B2
Filing date	May 4, 2007
Priority date	Jun 23, 2006
Publication date	Jul 12, 2016
Grant date	Jul 12, 2016

Abstract

The majority of such software attacks exploit software vulnerabilities or flaws to write data to unintended locations. For example, control-data attacks exploit buffer overflows or other vulnerabilities to overwrite a return address in the stack, a function pointer, or some other piece of control data. Non-control-data attacks exploit similar vulnerabilities to overwrite security critical data without subverting the intended control flow in the program. We describe a method for securing software against both control-data and non-control-data attacks. A static analysis is carried out to determine data flow information for a software program. Data-flow tracking instructions are formed in order to track data flow during execution or emulation of that software. Also, checking instructions are formed to check the tracked data flow against the static analysis results and thereby identify potential attacks or errors. Optional optimisations are described to reduce the resulting additional overheads.

First claim

The invention claimed is:

1. A method comprising:
(i) providing access to the results of a static analysis of a software program the static analysis results comprising data flow information, the static analysis including a set of reaching defintion identifiers associated with a use, the set of reaching definition identifiers including a first reaching definition that cannot reach the use at runtime;
(ii) forming data-flow tracking instructions in order to track data flow within the software;
(iii) forming checking instructions in order to check the tracked data flow against the static analysis results and thereby identify potential flaws in the software program, the checking instructions using a first memory area associated with a second memory area associated with the software program, a plurality of memory addresses of the second memory area being associated with a plurality of memory addresses of the first memory area, the plurality of memory addresses of the first memory area storing instruction indicators indicating an instruction that most recently wrote to a corresponding address in the second plurality of memory addresses;
(iv) establishing a guard page between the first and second memory areas, each memory address of the plurality of memory addresses of the first memory area being computable by bit shifting the corresponding address in the second plurality of memory addresses by a first constant, multiplying the result by a second constant, and adding a third constant; and
(v) adding the data-flow tracking instructions and the checking instructions to the software.

2. A method as claimed in claim 1 , wherein the data-flow tracking instructions and the checking instructions are formed and added to the software using any of a modified compiler and a binary re-write tool.

3. A method as claimed in claim 1 , wherein the data-flow tracking instructions and the checking instructions are implemented using any of a machine emulator arranged to emulate a processor executing the software program and a hardware equivalent of the machine emulator.

4. A method as claimed in claim 1 , wherein said potential flaws comprise both control-data attacks and non-control-data attacks.

5. A method as claimed in claim 1 , wherein the static analysis results comprise, for each value read by an instruction in the software program, a set of instructions from the software program that may write that value.

6. A method as claimed in claim 1 , which further comprises carrying out the static analysis of the software program by computing reaching definitions from source code of the software program.

7. A method as claimed in claim 1 , wherein the data flow tracking instructions are arranged to maintain a mapping between identifiers and memory positions, the identifiers being of the last instruction to write to each of the memory positions.

8. A method as claimed in claim 1 , wherein the checking instructions are associated with read instructions.

9. A method as claimed in claim 6 , wherein a checking instruction associated with a read instruction is arranged to check if an identifier of the instruction that wrote the value being read by the authorised read instruction is an element of an associated set computed by the static analysis.

10. A method as claimed in claim 5 , which further comprises determining equivalence classes of instructions and assigning the same identifier to all the instructions in the same class.

11. A method as claimed in claim 1 , which further comprises removing some of the data-flow tracking instructions and some of the checking instructions on the basis of a second static analysis.

12. A method as claimed in claim 1 , which further comprises carrying out the static analysis of the software program by computing reaching definitions and renaming at least some of those reaching definitions in order to improve the performance of a process of making checks against those reaching definitions.

13. A method comprising:
(i) accessing the results of a static analysis of a software program the static analysis results comprising data flow information, the data flow information including one or more value locations and a set of program locations of the program that may write a value for each of the one or more value locations, the set of program locations including one or more program locations of the program that cannot write the value at runtime;
(ii) tracking data flow in the software program during execution or emulation of that software program; and
(iii) checking the tracked data flow against the static analysis results and raising an exception if a mismatch is found, the mismatch being associated with at least a control-data attack or a non-control data attack, the checking comprising separating a first virtual address space from a second virtual address space associated with the first virtual address space using a guard page, an address of the first virtual address space being computable by bit shifting an address of the second virtual address space by a first constant, multiplying the result by a second constant, and adding a third constant, the second virtual address space being used by the software program.

14. A computer-readable storage medium, the computer-readable storage medium being hardware, containing computer-executable instructions comprising:
(i) computer-executable instructions to provide access to the results of a static analysis of a software program the static analysis results comprising data flow information;
(ii) computer-executable instructions to form data-flow tracking instructions in order to track data flow within the software;
(iii) computer-executable instructions to form checking instructions in order to check the tracked data flow against the static analysis results and thereby identify potential flaws in the software program, the potential flaws being associated with at least a control-data attack or a non-control data attack, the checking instructions using a first memory area associated with a second memory area associated with the software program, a plurality of memory addresses of the second memory area being associated with a plurality of memory addresses of the first memory area, the plurality of memory addresses of the first memory area storing instruction indicators indicating an instruction that most recently wrote to a corresponding address in the second plurality of memory addresses; and
(iv) computer-executable instructions to establish a guard page between the first and second memory areas, each memory address of the plurality of memory addresses of the first memory area being computable by bit shifting the corresponding address in the second plurality of memory addresses by a first constant, multiplying the result by a second constant, and adding a third constant.

15. A computer readable storage medium, the computer readable storage medium being hardware, containing computer-executable instructions comprising:
(i) computer-executable instructions to access the results of a static analysis of a software program the static analysis results comprising data flow information, the static analysis including a set of reaching defintion identifiers associated with a use, the set of reaching definition identifiers including a first reaching definition that cannot reach the use at runtime;
(ii) computer-executable instructions to add tracking data flow instructions to the software program;
(iii) computer-executable instructions to track data flow in the software program during execution or emulation of that software program; and
(iv) computer-executable instructions to check the track

Assignees

• Costa Manuel
• Castro Miguel
• Harris Tim
• Microsoft Technology Licensing Llc

Inventors

• Costa Manuel
• Castro Miguel
• Harris Tim

Classifications

• G06F21/54 Primary

  by adding security routines or objects to programs · CPC title

• G06F21/52

  during program execution, e.g. stack integrity {; Preventing unwanted data erasure; Buffer overflow} · CPC title

• G06F9/06 Primary

  using stored programs, i.e. using an internal store of processing equipment to receive or retain programs · CPC title

• G06F11/08

  Error detection or correction by redundancy in data representation, e.g. by using checking codes · CPC title

• G06F9/30

  Arrangements for executing machine instructions, e.g. instruction decode (for executing microinstructions G06F9/22) · CPC title