2

Assume we’re on an x86-64 machine and that we have read-access to the state of a program at a given instant, but we don’t have debugging symbols; in particular, we can read the program’s address space and the registers.

Is it possible to reliably determine the depth of the call stack? Under which assumptions (e.g., calling conventions)?

By the depth of the call stack I mean the number of call instructions minus the number of ret instructions that have happened in total in the course of the execution of the program. In the following pseudo trace, the number in the bracket is the depth of the call stack after the instruction in the respective line:

add eax ebx [0]
...
call 0x1234 [1]
call 0x2345 [2]
call 0x3456 [3]
add eax ebx [3]
jmp 0x4567  [3]
...
ret         [2]
...
ret         [1]
call 0x1234 [2]
...
ret         [1]
ret         [0]

I’m not yet an expert in x86, calling convention and the stack layout. However, I vaguely suppose that one can “walk” the stack with the help of the ebp and esp registers.

2

ret instructions are not going to the call stack. When a function executes call, the next instruction address is pushed to the stack and when ret instruction is executed, eip is updated with the next instruction from the stack.

After the next instruction address is popped from the stack by ret, the address at the stack will most likely be overwritten by a stack frame of a function. Therefore it's impossible to know at a given time, how many calls were made until this point from the beginning - what you call depth of the call stack.

A possible implementation of the current depth will be parsing the values from esp to the bottom of the stack, looking for pointers - values that point to the .text or any executable page of your memory.

| improve this answer | |
  • Can I start at the current stack base ebp, then load the previous stack base (which is stored somewhere in the current stack frame), then load the stack base before that (which is stored somwhere in the previous stack frame), and so on, until I hit the stack base? Or does something obscure the stack layout and prevent me from doing so? As far as I understand, if it works, the number of iterations should be the “depth of the call stack” that I’m looking for. – Lumen Feb 26 at 9:39
  • It will work, but you were talking about that have happened in total in the course of the execution of the program - What you are describing now is the total calls in the current time - not from the beginning of the program. In addition, you should note that some of the functions use ebp as a general-purpose register. – macro_controller Feb 26 at 9:43
  • I see, my wording was unclear. What I meant is the difference between total calls ever and total rets ever, which – I think – should net the number of calls “right now”. Also, thanks for the warning about ebp. I will accept the answer soon. – Lumen Feb 26 at 10:02
  • So yes, if that what you meant, it should give you what you asked. – macro_controller Feb 26 at 10:04
0

For Windows x64 systems, there is Microsoft’s StackWalk64 function from dbghelp.h. From my experience, it reliably recognizes stack frames on the stack and can thus be used to determine the depth of the call stack.

The only problem is obtaining a valid CONTEXT for the current thread because, according to the docs, GetThreadContext cannot be used for the current thread. You might have to suspend the thread first; in my case, a library is doing that for me so I’m not including the code here.

Given a valid CONTEXT Context, setup the necessary data:

STACKFRAME64 StackFrame;
StackFrame.AddrPC.Offset = Context.Rip;
StackFrame.AddrPC.Mode = AddrModeFlat;
StackFrame.AddrFrame.Offset = Context.Rbp; // maybe .Rsp
StackFrame.AddrFrame.Mode = AddrModeFlat;
StackFrame.AddrStack.Offset = Context.Rsp;
StackFrame.AddrStack.Mode = AddrModeFlat;

// Arguments for StackWalk64
DWORD MachineType = IMAGE_FILE_MACHINE_AMD64;
HANDLE hProcess = GetCurrentProcess();
HANDLE hThread = GetCurrentThread();
LPSTACKFRAME64 pStackFrame = &StackFrame;
PVOID ContextRecord = &Context;
PREAD_PROCESS_MEMORY_ROUTINE64 ReadMemoryRoutine = NULL;
PFUNCTION_TABLE_ACCESS_ROUTINE64 FunctionTableAccessRoutine = SymFunctionTableAccess64;
PGET_MODULE_BASE_ROUTINE64 GetModuleBaseRoutine = SymGetModuleBase64;
PTRANSLATE_ADDRESS_ROUTINE64 TranslateAddress = NULL;

Then walk the stalk:

int depth = 0;

while (StackWalk64(
        MachineType,
        hProcess,
        hThread,
        &StackFrame,
        ContextRecord,
        ReadMemoryRoutine,
        FunctionTableAccessRoutine,
        GetModuleBaseRoutine,
        TranslateAddress)
    )
{
    ++depth;
}
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.