There's a far simpler and also very generic method that I'm surprised no one has really mentioned much, although it's well-known in some corners of the RE/Asm community and I believe some debuggers (but not gdb?) use it: scan the stack for values that look like valid code addresses, then disassemble backwards from there to see if they were actually return addresses written there by a call instruction. You will find a chain that leads back to the entry point.
Of course it won't work in edge cases like handwritten Asm that uses the stack in more clever ways, but when you're dealing with compiler output, it'll be fine. No need for all this complexity, and works in almost all cases.
That method is pretty much guarnateed to give you completely broken stacks. We (Sentry) use it as a fallback if nothing else works, and the success rate is awful.
Are you also doing back-disassembly to link the call chain? I've had very good success with it. I agree that without analysing the potential call sites and making sure that they are actually possible, it won't work.
Since we do post-hoc stack walking our ability to actually look at the assembly is limited. In most cases where we have no CFI we also do not have the binary to begin with, so we're in random memory land.
If we find such an instruction, we assume it's an ip value that was pushed by the CALL instruction that created the current frame.
I'm not familiar with Rust, but if I'm reading it correctly, you're not doing back-disassembly and only checking if an address on the stack is in a code region, which certainly won't work well.
Minidumps only contain the stack, yes, along with additional metadata, but not the original executable. This is an old format that I think Microsoft originally designed and that Google extended for the breakpad project. It's used by Chrome and Mozilla also uses it for Firefox. It's essentially a crash reporting binary format.
I linked you to it elsewhere in this thread. Sentry is using a rust implementation of the stack walker.
GP mentioned in another comment that they don't actually follow the algorithm described by userbinator -- checking the return address for a preceding call -- which would increase the number of false positives a lot.
The thing that makes this tricky is that x86 is a variable length instruction set: you don't know where the preceding call instruction might begin, and you can't decode backwards. You can do it speculatively, but ambiguities are still possible.
Given that the full technique apparently works well for userbinator, we can assume that this isn't a very significant issue. The chances of a phantom call instruction will be pretty low, and there's a fairly low maximum instruction length.
There's a chance of that, but in practice it's easy to filter them out, since only one of the chains will be complete from the very top of the stack to the current stack pointer. The others will almost certainly be partially overwritten by other stack activity and incomplete, or not match the current stack pointer.
This has been a fallback method for Google Breakpad's stackwalker for more than a decade. It generates basically useless stack traces, at least for stacks captured from Android where you're trying to trace through NDK code invoked from the ART. Compounding the problem is a complete lack of available symbols for Android.
I dug around in that code a little, and although it contains a disassembler, it's not being used for inspecting the call chain. All it does is check that the address appears to be inside a code section.
Do you analyze the dynamic loader segments (to determine code-like addresses) or just do some hard-coded approximations per platform? Pretty cute idea and I agree it will often work.
It just needs to be on an executable page. The processor doesn't care about anything else, so this will work with things like JIT-generated code too. The key idea is that in essentially all cases of compiler-generated code, every return address will be immediately after the call that wrote it.
Of course it won't work in edge cases like handwritten Asm that uses the stack in more clever ways, but when you're dealing with compiler output, it'll be fine. No need for all this complexity, and works in almost all cases.