Software security via control flow integrity checking
First Claim
Patent Images
1. One or more computer-readable devices comprising:
- a control flow graph builder tool configured to construct a data structure during static analysis of a program, the data structure representing a canonical control flow graph for validation of a call stack at runtime, the validation of the call stack at runtime comprising a comparison of contents of the call stack with the canonical control flow graph, the comparison accepting the canonical control flow graph along with one or more runtime stack observations as input and outputting a check result indicating whether the call stack conforms to the canonical control flow graph, wherein the data structure comprises;
a block table storing a table of block start addresses and respective block end addresses for a plurality of blocks indicative of instruction ranges in the canonical control flow graph;
a stack frame size table mapping block start addresses to respective maximum stack data used by the blocks identified by the block start addresses before a call;
a callee map table mapping block start addresses to respective lists of callers; and
a valid return map mapping child call sites to respective parent call sites.
1 Assignment
0 Petitions
Accused Products
Abstract
Various technologies related to control flow integrity checking are described herein and can be used to greatly improve software security. During static analysis, a canonical control flow graph can be built. Execution of a program can be interrupted at runtime, and the call stack can be observed to verify control flow integrity of the program using the canonical control flow graph. Attacks using stack tampering can be avoided, regardless of how the stack tampering is achieved. Non-invasive techniques can be used, making the technologies applicable in situations where source code is not available. Real-time operating system protection can be supported.
28 Citations
18 Claims
-
1. One or more computer-readable devices comprising:
-
a control flow graph builder tool configured to construct a data structure during static analysis of a program, the data structure representing a canonical control flow graph for validation of a call stack at runtime, the validation of the call stack at runtime comprising a comparison of contents of the call stack with the canonical control flow graph, the comparison accepting the canonical control flow graph along with one or more runtime stack observations as input and outputting a check result indicating whether the call stack conforms to the canonical control flow graph, wherein the data structure comprises; a block table storing a table of block start addresses and respective block end addresses for a plurality of blocks indicative of instruction ranges in the canonical control flow graph; a stack frame size table mapping block start addresses to respective maximum stack data used by the blocks identified by the block start addresses before a call; a callee map table mapping block start addresses to respective lists of callers; and a valid return map mapping child call sites to respective parent call sites. - View Dependent Claims (2, 3, 17, 18)
-
-
4. One or more non-transitory computer-readable storage media comprising:
-
a data structure representing a canonical control flow graph for validating a stack at runtime of a program, the canonical control flow graph constructed during static analysis of the program, and the validation of the stack at runtime comprising a comparison of contents of the stack with the canonical control flow graph; and instructions that, when executed, cause a computer to accept the canonical control flow graph along with one or more runtime stack observations as input, and output a check result indicating whether the stack conforms to the canonical control flow graph, wherein the data structure comprises; a block table storing a table of block address ranges for a plurality of blocks indicative of instruction ranges in the canonical control flow graph, wherein the block address ranges comprise respective block identifiers; a stack frame size table mapping block identifiers to respective maximum stack data used by the plurality of blocks identified by the block identifiers before a call, wherein the maximum stack data used by the plurality of blocks indicates a maximum number of bytes pushed to the stack by an instruction range indicated by a particular block identifier; a callee map table mapping block identifiers to respective lists of callers; and a valid return map mapping child call sites to respective parent call sites. - View Dependent Claims (5)
-
-
6. A method implemented at least in part by a computing device, the method comprising:
-
storing a canonical control flow graph indicating possible ordinary execution paths for a program, wherein the canonical control flow graph comprises (a)-(d); (a) a block table storing a table of block start addresses and respective block end addresses for a plurality of blocks indicative of instruction ranges in the canonical control flow graph; (b) a stack frame size table mapping block start addresses to respective maximum stack data used by the plurality of blocks identified by the block start addresses before a call; (c) a callee map table mapping block start addresses to respective lists of callers; and (d) a valid return map mapping child call sites to respective parent call sites; observing a stack during execution of the program, wherein the observing comprises determining contents of the stack; comparing the contents of the stack with the canonical control flow graph, wherein the comparing comprises determining whether the contents of the stack indicate an execution path not appearing in the possible ordinary execution paths; and responsive to determining that the contents of the stack indicate the execution path not appearing in the possible ordinary execution paths, taking action avoiding further execution of the program. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
Specification