Stack traces using shadow stack

Patent metadata

Field	Value
Publication number	US-11294682-B2
Application number	US-201916417493-A
Country	US
Kind code	B2
Filing date	May 20, 2019
Priority date	May 20, 2019
Publication date	Apr 5, 2022
Grant date	Apr 5, 2022

Abstract

A program is executed using a call stack and shadow stack. The call stack includes frames having respective return addresses. The frames may also store variables and/or parameters. The shadow stack stores duplicates of the return addresses in the call stack. The call stack and the shadow stack are maintained by, (i) each time a function is called, adding a corresponding stack frame to the call stack and adding a corresponding return address to the shadow stack, and (ii) each time a function is exited, removing a corresponding frame from the call stack and removing a corresponding return address from the shadow stack. A backtrace of the program's current call chain is generated by accessing the return addresses in the shadow stack. The outputted backtrace includes the return addresses from the shadow stack and/or information about the traced functions that is derived from the shadow stack's return addresses.

First claim

The invention claimed is:

1. A method comprising:
executing, by a processor, a program, the program comprising functions, each function comprising respective code for respective functions and calls invoking the functions, the executing comprising:
maintaining a call stack comprised of frames corresponding to respective invocations of the functions by the calls, each frame comprising a corresponding return address;
maintaining a shadow stack, the maintaining the shadow stack comprising adding/removing return addresses to/from the shadow stack in correspondence with adding/removing the frames to/from the call stack; and

receiving a request for a stack trace, and based thereon, accessing both the call stack and the shadow stack to generate the stack trace by combining information obtained from the shadow stack, the information obtained from the shadow stack comprising respective return addresses, with information obtained from the call stack, the respective return addresses obtained from the shadow stack acting as an index to obtain the information from the call stack.

2. A method according to claim 1 , further comprising, for a first return address in the shadow stack, obtaining at least some corresponding function metadata from the call stack.

3. A method according to claim 2 , further comprising, for the first return address in the shadow stack, obtaining additional corresponding function metadata from the program.

4. A method according to claim 1 , wherein the processor implements the shadow stack by providing a call instruction for which a single execution thereof causes a corresponding return address to be pushed onto the call stack and onto the shadow stack.

5. A method according to claim 1 , wherein the maintaining of the shadow stack is performed by the program.

6. A method according to claim 1 , wherein the generating the stack trace comprises copying the shadow stack and storing the copy of the shadow stack and storing an indication that the copy of the shadow stack is associated with the program.

7. A method according to claim 1 , wherein the executing further comprises:
deriving an enriched backtrace comprising the respective return addresses from the shadow stack and additional corresponding information from the call stack.

8. A method according to claim 1 , wherein the respective return addresses from the shadow stack acting as the index to the information obtained from the call stack comprises the respective return addresses in the shadow stack being correlated with frames and return addresses in the call stack.

9. Computer-readable storage hardware storing instructions configured to cause a computing device to perform a process, the computing device comprising processing hardware and memory, the process comprising:
executing a program by the processing hardware, the executing comprising providing a call stack and shadow stack in the memory, the call stack comprising stack frames, each stack frame comprising a respectively corresponding return address, some of the stack frames further comprising corresponding local variables and/or parameters, the shadow stack comprising return addresses that respectively correspond to the return addresses in the call stack, the providing the call stack and the shadow stack comprising:
when a function is called by the program, adding a corresponding stack frame to the call stack and adding a corresponding return address to the shadow stack; and
when the function is exited by the program, removing a corresponding stack frame from the call stack and removing a corresponding return address from the shadow stack; and

receiving a backtrace request in association with the program, and based on the backtrace request, forming a backtrace of the program by combining information obtained from both the call stack and the shadow stack, the information obtained from the shadow stack comprising respective return addresses, the respective return addresses from the shadow stack acting as an index to obtain the information from the call stack.

10. Computer-readable storage hardware according to claim 9 , the process further comprising determining that the shadow stack is available, wherein the forming the backtrace is only performed when the shadow stack has been determined to be available.

11. Computer-readable storage hardware according to claim 9 , wherein the forming the backtrace further comprises:
using the respective return addresses in the shadow stack to identify text strings respectively corresponding to the respective return addresses in the shadow stack, and
including the text strings in the backtrace, the backtrace comprising the text strings arranged in an order corresponding to an order of the respective return addresses in the shadow stack when the backtrace request was received.

12. Computer-readable storage hardware according to claim 9 , wherein the process further comprises, based on a second request from the program, configuring execution of the program such that backtrace requests capture respective backtraces only if a shadow stack is available.

13. Computer-readable storage hardware according to claim 9 , wherein the providing the call stack and the shadow stack comprises the processing hardware providing a call instruction for which a single execution thereof causes a first return address to be pushed onto both the call stack and the shadow stack.

14. Computer-readable storage hardware according to claim 9 , wherein the program comprises a plurality of call stacks and respective shadow stacks.

15. Computer-readable storage hardware according to claim 9 , wherein the forming the backtrace further comprises:
for a first return address in the shadow stack, obtaining at least some corresponding function metadata from the call stack.

16. Computer-readable storage hardware according to claim 9 , wherein the respective return addresses from the shadow stack acting as the index to the information obtained from the call stack comprises the respective return addresses in the shadow stack being correlated with frames and return addresses in the call stack.

17. A device comprising:
processing hardware; and
storage hardware storing instructions configured to cause the processing hardware to perform a process, the process comprising:
executing a program, the executing including maintaining a call stack and a corresponding shadow stack; and
while the program is executing and a chain of functions have been invoked by the program, responding to a request to generate a backtrace for the program by copying return addresses from the shadow stack, obtaining additional information from the call stack, the return addresses from the shadow stack acting as an index to obtain the additional information from the call stack, and outputting a combination of the copied return addresses and the additional information obtained from the call stack.

18. A device according to claim 17 , wherein the processing hardware comprises hardware instructions that include a call instruction, the call instruction configured to manage the shadow stack.

19. A device according to claim 18 , wherein the processing hardware instructions further comprise a return instruction, the call instruction configured to push addresses onto both the call stack and the shadow stack, and the return instruction configured to compare addresses from the call stack to corresponding addresses from the shadow stack.

20. A device according to claim 17 , the process further comprising the program calling a backtrace functi

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Niu Ben
• Colombo Gregory John
• Cui Weidong
• Lin Jason
• Johnson Kenneth Dean

Classifications

• G06F11/3698

  Environments for analysis, debugging or testing of software · CPC title

• G06F11/3612

  by runtime analysis (performance monitoring G06F11/3466) · CPC title

• G06F9/4484 Primary

  Executing subprograms · CPC title

• G06F21/52

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

• G06F9/3806 Primary

  using address prediction, e.g. return stack, branch history buffer · CPC title