SOFTWARE SECURITY VIA CONTROL FLOW INTEGRITY CHECKING

• US 20180101565A1
• Filed: 12/14/2017
• Published: 04/12/2018
• Est. Priority Date: 10/23/2012
• Status: Active Grant

• Current Assignee: Galois, Inc.
• Original Assignee: Galois, Inc.
• Inventors: Pike, Lee, Hickey, Patrick Christopher, Tomb, Aaron, Mertens, Eric
• Granted Patent: US 10,242,043 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 21/52 during program execution, e.g. stack integrity ; Preventing unwanted data erasure; Buffer overflow
• CPC Class Codes: G06F 21/566 Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities

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.

Claims

1. -21. (canceled)

22. One or more computer-readable devices comprising a data structure representing a 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.

24. The one or more computer-readable devices of claim 22 wherein:

the block table represents address ranges of blocks for the canonical control flow graph.

25. The one or more computer-readable devices of claim 22 wherein:

the maximum stack data used by the blocks indicates a maximum number of bytes pushed to a stack by an instruction range indicated by a particular block start address.

23. (canceled)

26. One or more non-transitory computer-readable storage media comprising a data structure representing a 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;

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.

27. The one or more non-transitory computer-readable storage media of claim 26 wherein:

the maximum stack data used by the plurality of blocks indicates a maximum number of bytes pushed to a stack by an instruction range indicated by a particular block identifier.

28. 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.

29. The method of claim 28 wherein:

taking action comprises halting execution of the program.

30. The method of claim 28 further comprising:

periodically interrupting the program during execution, wherein the observing is performed via the interrupting.

31. The method of claim 30 wherein the interrupting is performed by an operating system.

32. The method of claim 31 wherein the program is not instrumented to achieve the interrupting.

33. The method of claim 28 wherein:

the method is interruptible; and

upon resumption of the method, contents of the stack of a previous iteration are discarded in favor of current contents of the stack.

34. The method of claim 28 further comprising:

responsive to determining that a top of the stack contains cruft, removing the cruft before comparing the contents of the stack with the canonical control flow graph.

35. The method of claim 28 wherein:

the canonical control flow graph is annotated to indicate a number of data bytes pushed onto the stack by instructions within an indicated address range.

36. The method of claim 35 wherein:

the comparing comprises finding a stack frame for a prior call; and

finding a stack frame comprises accounting for the number of data bytes pushed onto the stack as indicated by the canonical control flow graph.

37. The method of claim 28 wherein:

storing the canonical control flow graph comprises storing a table of start addresses and respective end addresses for a plurality of instruction ranges.

38. The method of claim 28 wherein:

storing the canonical control flow graph comprises storing a table mapping instruction range identifiers to respective maximum stack data used by an instruction range.