x64 Call Stack Walking

The call stack is a data structure that stores information about active subroutines in a program.

When a function is called, a stack frame is allocated for that function which contains information it’s local variables, parameters, and it’s return address. The return address states where the code should return to after execution.

When a function calls other functions, it’s stack frame is pushed to the top of the call stack. Similarly, when a function exits, it’s stack frame is popped off the stack.

This process is easier to understand with an example. The following C++ code will be used for this purpose;

#include <iostream>

void FunctionB()
{
    std::cout << "FunctionB\n";
}

void FunctionA()
{
    std::cout << "FunctionA\n";
    FunctionB();
}

int main()
{
    std::cout << "Main\n";
    FunctionA();
}

With the above code, the call stack will track that FunctionB was called from FunctionA, and FunctionA was in turn called from main. The system maintains this chain of events so if an exception occurs in a function that is unhandled, it can check if the parent function has an appropriate handler.

The code should be compiled for x64, as x32 systems use a different method of tracking call stack behaviour.

Stacking Walking with WinDBG

If we add a breakpoint to pause execution on FunctionB, we can use the k command in WinDBG to view the call stack showing the previous functions that got us to this point.

0:000> bp StackWalking!FunctionB
0:000> knf
 #   Memory  Child-SP          RetAddr               Call Site
00           0000002a`1733f608 00007ff6`fad52103     StackWalking!FunctionB
01         8 0000002a`1733f610 00007ff6`fad52333     StackWalking!FunctionA+0x33
02       100 0000002a`1733f710 00007ff6`fad52bb9     StackWalking!main+0x33 
03       100 0000002a`1733f810 00007ff6`fad52a5e     StackWalking!invoke_main+0x39
04        50 0000002a`1733f860 00007ff6`fad5291e     StackWalking!__scrt_common_main_seh+0x12e
05        70 0000002a`1733f8d0 00007ff6`fad52c4e     StackWalking!__scrt_common_main+0xe
06        30 0000002a`1733f900 00007fff`2d6b257d     StackWalking!mainCRTStartup+0xe
07        30 0000002a`1733f930 00007fff`2e36aa58     KERNEL32!BaseThreadInitThunk+0x1d
08        30 0000002a`1733f960 00000000`00000000     ntdll!RtlUserThreadStart+0x28

The output shows two values of interest;

  • The return address (RetAddr), which is where execution will continue to when the function exits
  • The Child Stack Pointer (Child-SP). This is the address of the stack pointer for that particular frame. The stack pointer always points to the current location where memory will be pushed and popped.

Determining the return address is simple, after entering FunctionB, the first QWORD address on the stack will be our return address.

0:000> dq rsp L1
0000002a`1733f608  00007ff6`fad52103

Determining what the Child-SP values are is a slightly more involved process.

The PDATA Section

.pdata is a section of a PE32 that contains information related to exception handling. The section can be viewed using the !dh command in WinDBG.

0:000> !dh StackWalking

File Type: EXECUTABLE IMAGE
FILE HEADER VALUES
    8664 machine (X64)
       A number of sections

<output_truncated>

SECTION HEADER #5
  .pdata name
    2238 virtual size
   1E000 virtual address
    2400 size of raw data
    C200 file pointer to raw data
       0 file pointer to relocation table
       0 file pointer to line numbers
       0 number of relocations
       0 number of line numbers
40000040 flags
         Initialized Data
         (no align specified)
         Read Only

The PDATA section contains the information we need to determine the Child-SP values. To understand how this works, let’s first ensure the functions prologue has executed.

In WinDBG if we break on a function this will occur before the function prologue;

0:000> u rip
StackWalking!FunctionB
00007ff6`fad52120 4055            push    rbp
00007ff6`fad52122 57              push    rdi
00007ff6`fad52123 4881ece8000000  sub     rsp,0E8h

Stepping through these instructions, we can FunctionB now has 0x100 bytes allocated.

0:000> knf
 #   Memory  Child-SP          RetAddr               Call Site
00           0000002a`1733f510 00007ff6`fad52103     StackWalking!FunctionB+0x2e
01       100 0000002a`1733f610 00007ff6`fad52333     StackWalking!FunctionA+0x33
02       100 0000002a`1733f710 00007ff6`fad52bb9     StackWalking!main+0x33
03       100 0000002a`1733f810 00007ff6`fad52a5e     StackWalking!invoke_main+0x39
04        50 0000002a`1733f860 00007ff6`fad5291e     StackWalking!__scrt_common_main_seh+0x12e
05        70 0000002a`1733f8d0 00007ff6`fad52c4e     StackWalking!__scrt_common_main+0xe
06        30 0000002a`1733f900 00007fff`2d6b257d     StackWalking!mainCRTStartup+0xe
07        30 0000002a`1733f930 00007fff`2e36aa58     KERNEL32!BaseThreadInitThunk+0x1d
08        30 0000002a`1733f960 00000000`00000000     ntdll!RtlUserThreadStart+0x28

Analysing the UNWIND Structure

The PDATA section of the executable contains UNWIND data structures, that provide the information required to undo the changes made by the function prologue.

The .fnent command can be used to display the UNWIND instructions.

0:000> .fnent StackWalking!FunctionB
Debugger function entry 0000022d`5f255d30 for:
 StackWalking!__empty_global_delete
Exact matches:
    StackWalking!FunctionB (void)

BeginAddress      = 00000000`00012120
EndAddress        = 00000000`00012158
UnwindInfoAddress = 00000000`0001c5ec

Unwind info at 00007ff6`fad5c5ec, e bytes
  version 1, flags 0, prolog f, codes 5
  frame reg 5 (rbp), frame offs 20h
  00: offs f, unwind op 3, op info 2	UWOP_SET_FPREG.
  01: offs a, unwind op 1, op info 0	UWOP_ALLOC_LARGE FrameOffset: e8.
  03: offs 3, unwind op 0, op info 7	UWOP_PUSH_NONVOL reg: rdi.
  04: offs 2, unwind op 0, op info 5	UWOP_PUSH_NONVOL reg: rbp.

The Unwind instructions are essentially the reverse of the prologue. Microsoft have documented the purpose of each of these instructions here.

So, the unwind instructions would be;

add rsp, 0e8h # UWOP_ALLOC_LARGE FrameOffset: e8.
pop rdi # UWOP_PUSH_NONVOL reg: rdi.
pop rbp # UWOP_PUSH_NONVOL reg: rbp.

The total stack size before allocation is always 8 (for a return address).

(Current-ChildSP + add rsp e8 + POP RDI + POP RBP + RET)

So, we just need to add these offsets together to determine the parent function Child-SP Value.

0:000> ? 0000002a1733f510 + 0e8h + 0x8 + 0x8 + 0x8 
Evaluate expression: 180777907728 = 0000002a1733f610

This can be verified using the knf command.

0:000> knf
 #   Memory  Child-SP          RetAddr               Call Site
00           0000002a`1733f510 00007ff6`fad52103     StackWalking!FunctionB+0x2e
01       100 0000002a`1733f610 00007ff6`fad52333     StackWalking!FunctionA+0x33

Iterating through this process, we could go from FunctionB back to our main() function.

In Conclusion

Security products may analyse call stack information to determine if a call to a function has been made from a suspicious origin. For instance, copying shellcode in heap memory and executing it in place will lead to a highly unusual call stack.