Source code
Revision control
Copy as Markdown
Other Tools
//! This module implements support for breakpad's text-based STACK CFI and STACK WIN
//! unwinding instructions. This isn't something you need to actually use
//! directly, it's just public so these docs will get a nice pretty rendering.
//!
//! The rest of this documentation is discussion of STACK CFI and STACK WIN
//! format -- both how to parse and evaluate them.
//!
//! Each STACK line provides instructions on how to unwind the program at
//! a given instruction address. Specifically this means how to restore
//! registers, which most importantly include the instruction pointer ($rip/$eip/pc)
//! and stack pointer ($rsp/$esp/sp).
//!
//! STACK WIN lines are completely self-contained while STACK CFI lines may
//! depend on the lines above them.
//!
//! Note that all addresses are relative to the start of the module -- resolving
//! the module and applying that offset is left as an exercise to the reader.
//!
//! See also [the upstream breakpad docs](https://chromium.googlesource.com/breakpad/breakpad/+/master/docs/symbol_files.md)
//! which are *ok* but can be a bit hazy around the details (I think they've
//! just partially bitrotted). To the best of my ability I have tried to make
//! these docs as accurate and detailed as possible.
//!
//! I also try to be honest about the places where I'm uncertain about the
//! semantics.
//!
//!
//!
//!
//!
//! # Known Differences Between This Implementation and Breakpad
//!
//! I haven't thoroughly tested the two implementations for compatibility,
//! but where I have noticed a difference I'll put it here so it's
//! documented *somewhere*.
//!
//!
//!
//! ## Register Names
//!
//! Breakpad assumes register names are prefixed with `$` *EXCEPT*
//! on ARM variants. These prefixes are hardcoded, so if you hand it
//! `$rax` or `x11` it will be happy, but if you hand it `rax` or `$x11`
//! it will freak out and be unable to parse the CFI expressions.
//!
//! This implementation doesn't have any notion of "valid" registers
//! for a particular execution, and so just unconditionally strips leading
//! $'s. So `$rax`, `$x11`, `rax`, and `x11` should all be valid.
//!
//! Registers names are otherwise only "validated" by the [FrameWalker][],
//! in that it will return an error if we try to get or set a register name
//! *it* doesn't recognize (or doesn't have a valid value for). But it
//! doesn't ever expect `$`'s, so that detail has been erased by
//! the time it's involved.
//!
//! The author of this document may or may not know this as a result of
//! accidentally causing mozilla/dump_syms to emit `$x11` in some situations.
//! If that is the case, they fixed it, so everything's fine, right?
//!
//! It's bad to be a permissive parser, but symbol files are already
//! an inconsistent mess, so you kind of *have* to be permissive in random
//! places? And we don't have a conformance test suite to keep everything
//! perfectly bug-compatible with breakpad when it doesn't document
//! everything enough to know what's "intended".
//!
//!
//!
//! ## cfi_scan hacks
//!
//! This is technically a technique that the *user* of walker.rs would
//! implement, but it's worth discussing here since it relates to cfi
//! evaluation.
//!
//! When evaluating STACK WIN expressions, breakpad will apply several
//! heuristics to adjust values. This includes scanning the stack to
//! try to "refine" the inputs and outputs.
//!
//! At the moment, we implement very few of these heuristics. We definitely
//! don't do any scanning when evaluating STACK WIN.
//!
//! The ones we *do* implement (and that I can recall) are:
//!
//! * changing the value of searchStart based on whether the program
//! includes an `@`.
//!
//! * trying to forward the value of `$ebx` in more situations
//! than the STACK WIN suggests you should.
//!
//! At this point I don't recall if these were implemented to fix actual
//! issues found during development, or if I just cargo-culted them
//! because they seemed relatively inoffensive.
//!
//!
//!
//!
//!
//! # STACK CFI
//!
//! STACK CFI lines comes in two forms:
//!
//! `STACK CFI INIT instruction_address num_bytes registers`
//!
//! `STACK CFI instruction_address registers`
//!
//!
//! A `STACK CFI INIT` line specifies how to restore registers for the given
//! range of addresses.
//!
//! Example: `STACK CFI INIT 804c4b0 40 .cfa: $esp 4 + $eip: .cfa 4 - ^`
//!
//! Arguments:
//! * instruction_address (hex u64) is the first address in the module this line applies to
//! * num_bytes (hex u64) is the number of bytes it (and its child STACK CFI lines) covers
//! * registers (string) is the register restoring instructions (see the next section)
//!
//!
//! A `STACK CFI` line always follows a "parent" `STACK CFI INIT` line. It
//! updates the instructions on how to restore registers for anything within
//! the parent STACK CFI INIT's range after the given address (inclusive).
//! It only specifies rules for registers that have new instructions.
//!
//! To get the final rules for a given address, start with its `STACK CFI INIT`
//! and then apply all the applicable `STACK CFI` "diffs" in order.
//!
//! Example: `STACK CFI 804c4b1 .cfa: $esp 8 + $ebp: .cfa 8 - ^`
//!
//! Arguments:
//! * instruction_address (hex u64) is the first address to apply these instructions
//! * registers (string) is the new register restoring instructions (see the next section)
//!
//!
//!
//! ## STACK CFI registers
//!
//! A line's STACK CFI registers are of the form
//!
//! `REG: EXPR REG: EXPR REG: EXPR...`
//!
//! Where REG is `.cfa`, `.ra`, `$<alphanumeric>`, or `<alphanumeric>`
//! (but not a valid integer literal).
//!
//! And EXPR is `<anything but ":">` (see next section for details)
//!
//! Each `REG: EXPR` pair specifies how to compute the register REG for the
//! caller. There are three kinds of registers:
//!
//! * `$XXX` or `XXX` refers to an actual general-purpose register. In REG position it
//! refers to the caller, in an EXPR it refers to the callee. Register names
//! can in theory be any alphanumeric string that isn't a valid integer literal.
//! e.g. `$rax`, `x11`. `$` prefixes are expected for all platforms except ARM
//! variants. This parser is more permissive and allows for either form on all
//! platforms. Completely invalid register names (`x99`) will be caught at evaluation time.
//!
//! * `.cfa` is the "canonical frame address" (CFA), as used in DWARF CFI. It
//! abstractly represents the base address of the frame. On x86, x64, and
//! ARM64 the CFA is the caller's stack pointer from *before* the call. As
//! such on those platforms you will never see instructions to restore the
//! frame pointer -- it must be implicitly restored from the cfa. `.cfa`
//! always refers to the caller, and therefore must be computed without
//! use of itself.
//!
//! * `.ra` is the "return address", which just abstractly refers to the
//! instruction pointer/program counter. It only ever appears in REG
//! position.
//!
//! `.cfa` and `.ra` must always have defined rules, or the STACK CFI is malformed.
//!
//! The CFA is special because its computed value can be used by every other EXPR.
//! As such it should always be computed first so that its value is available.
//! The purpose of the CFA is to cleanly handle the very common case of registers
//! saved to the stack. Every register saved this way lives at a fixed offset
//! from the start of the frame. So we can specify their rules once, and just
//! update the CFA.
//!
//! For example:
//!
//! ```text
//! STACK CFI INIT 0x10 16 .cfa: $rsp 8 + .ra: .cfa -8 + ^
//! STACK CFI 0x11 .cfa: $rsp 16 + $rax: .cfa -16 + ^
//! STACK CFI 0x12 .cfa: $rsp 24 +
//! ```
//!
//! Can be understood as (pseudo-rust):
//!
//! ```rust,ignore
//! let mut cfa = 0;
//! let mut ra = None;
//! let mut caller_rax = None;
//!
//!
//! // STACK CFI INIT 0x10's original state
//! cfa = callee_rsp + 8;
//! ra = Some(|| { *(cfa - 8) }); // Defer evaluation
//!
//!
//! // STACK CFI 0x11's diff
//! if address >= 0x11 {
//! cfa = callee_rsp + 16;
//! caller_rax = Some(|| { *(cfa - 16) }); // Defer evaluation
//! }
//!
//!
//! // STACK CFI 0x12's diff
//! if address >= 0x12 {
//! cfa = callee_rsp + 24;
//! }
//!
//! caller.stack_pointer = cfa;
//!
//! // Finally evaluate all other registers using the current cfa
//! caller.instruction_pointer = ra.unwrap()();
//! caller.rax = caller_rax.map(|func| func());
//! ```
//!
//!
//!
//! ## STACK CFI expressions
//!
//! STACK CFI expressions are in postfix (Reverse Polish) notation with tokens
//! separated by whitespace. e.g.
//!
//! ```text
//! .cfa $rsp 3 + * ^
//! ```
//!
//! Is the postfix form of
//!
//! ```text
//! ^(.cfa * ($rsp + 3))
//! ```
//!
//! The benefit of postfix notation is that it can be evaluated while
//! processing the input left-to-right without needing to maintain any
//! kind of parse tree.
//!
//! The only state a postfix evaluator needs to maintain is a stack of
//! computed values. When a value (see below) is encountered, it is pushed
//! onto the stack. When an operator (see below) is encountered, it can be
//! evaluated immediately by popping its inputs off the stack and pushing
//! its output onto the stack.
//!
//! If the postfix expression is valid, then at the end of the token
//! stream the stack should contain a single value, which is the result.
//!
//! For binary operators the right-hand-side (rhs) will be the first
//! value popped from the stack.
//!
//! Supported operations are:
//!
//! * `+`: Binary Add
//! * `-`: Binary Subtract
//! * `*`: Binary Multiply
//! * `/`: Binary Divide
//! * `%`: Binary Remainder
//! * `@`: Binary Align (truncate lhs to be a multiple of rhs)
//! * `^`: Unary Dereference (load from stack memory)
//!
//! Supported values are:
//!
//! * `.cfa`: read the CFA
//! * `.undef`: terminate execution, the output is explicitly unknown
//! * `<a signed decimal integer>`: read this integer constant (limited to i64 precision)
//! * `$<alphanumeric>`: read a general purpose register from the callee's frame
//! * `<alphanumeric>`: same as above (can't be an integer literal)
//!
//! Whether registers should be `$reg` or `reg` depends on the platform.
//! This parser is permissive, and just accepts both on all platforms.
//!
//! But I believe `$` is "supposed" to be used on every platform except for
//! ARM variants.
//!
//!
//!
//! # STACK WIN
//!
//! STACK WIN lines try to encode the more complex unwinding rules produced by
//! x86 Windows toolchains. On any other target (x64 windows, x86 linux, etc),
//! only STACK CFI should be used. This is a good thing, because STACK WIN is
//! a bit of a hacky mess, as you'll see.
//!
//!
//! ```text
//! STACK WIN type instruction_address num_bytes prologue_size epilogue_size parameter_size
//! saved_register_size local_size max_stack_size has_program_string
//! program_string_OR_allocates_base_pointer
//! ```
//!
//!
//! Examples:
//!
//! ```text
//! STACK WIN 4 a1080 fa 9 0 c 0 0 0 1 $T0 .raSearch = $eip $T0 ^ = $esp $T0 4 + =`
//!
//! STACK WIN 0 1cab960 68 0 0 10 0 8 0 0 0
//! ```
//!
//!
//! Arguments:
//! * type is either 4 ("framedata") or 0 ("fpo"), see their sections below
//! * instruction_address (hex u64) is the first address in the module this line applies to
//! * num_bytes (hex u64) is the number of bytes it covers
//! * has_program_string (0 or 1) indicates the meaning of the next argument (implied by type?)
//! * program_string_OR_allocates_base_pointer is one of:
//! * program_string (string) is the expression to evaluate for "framedata" (see that section)
//! * allocates_base_pointer (0 or 1) whether ebp is pushed for "fpo" (see that section)
//!
//! The rest of the arguments are just values you may need to use in the STACK WIN
//! evaluation algorithms:
//!
//! * prologue_size
//! * epilogue_size
//! * parameter_size
//! * saved_register_size
//! * local_size
//! * max_stack_size
//!
//! Two useful values derived from these values are:
//!
//! ```rust,ignore
//! grand_callee_parameter_size = callee.parameter_size
//! frame_size = local_size + saved_register_size + grand_callee_parameter_size
//! ```
//!
//! Having frame_size allows you to find the offset from $esp to the return
//! address (and other saved registers). This requires grand_callee_parameter_size
//! because certain windows calling conventions makes the caller responsible for
//! destroying the callee's arguments, which means they are part of the caller's
//! frame, and therefore change the offset to the return address. (During unwinding
//! we generally refer to the current frame as the "callee" and the next frame as
//! the "caller", but here we're concerned with callee's callee, hence grand_callee.)
//!
//! Note that grand_callee_paramter_size is using the STACK WIN entry of the
//! *previous* frame. Although breakpad symbol files have FUNC entries which claim
//! to provide parameter_size as well, those values are not to be trusted (or
//! at least, the grand-callee's STACK WIN entry is to be preferred). The two
//! values are frequently different, and the STACK WIN ones are more accurate.
//!
//! If there is no grand_callee (i.e. you are unwinding the first frame of the
//! stack), grand_callee_parameter_size can be defaulted to 0.
//!
//!
//!
//!
//! # STACK WIN frame pointer mode ("fpo")
//!
//! This is an older mode that just gives you minimal information to unwind:
//! the size of the stack frame (`frame_size`). All you can do is find the
//! return address, update `$esp`, and optionally restore `$ebp` (if allocates_base_pointer).
//!
//! This is best described by pseudocode:
//!
//! ```text
//! $eip := *($esp + frame_size)
//!
//! if allocates_base_pointer:
//! // $ebp was being used as a general purpose register, old value saved here
//! $ebp := *($esp + grand_callee_parameter_size + saved_register_size - 8)
//! else:
//! // Assume both ebp and ebx are preserved (if they were previously valid)
//! $ebp := $ebp
//! $ebx := $ebx
//!
//! $esp := $esp + frame_size + 4
//! ```
//!
//! I don't have an interesting explanation for why that position is specifically
//! where $ebp is saved, it just is. The algorithm tries to forward $ebx when $ebp
//! wasn't messed with as a bit of a hacky way to encourage certain Windows system
//! functions to unwind better. Evidently some of them have framedata expressions
//! that depend on $ebx, so preserving it whenever it's plausible is desirable?
//!
//!
//!
//!
//! # STACK WIN expression mode ("framedata")
//!
//! This is the general purpose mode that has you execute a tiny language to compute
//! arbitrary registers.
//!
//! STACK WIN expressions use many of the same concepts as STACK CFI, but rather
//! than using `REG: EXPR` pairs to specify outputs, it maintains a map of variables
//! whose values can be read and written by each expression.
//!
//! I personally find this easiest to understand as an extension to the STACK CFI
//! expressions, so I'll describe it in those terms:
//!
//! The supported operations add one binary operation:
//!
//! * `=`: Binary Assign (assign the rhs's integer to the lhs's variable)
//!
//! This operation requires us to have a distinction between *integers* and
//! *variables*, which the postfix evaluator's stack must hold.
//!
//! All other operators operate only on integers. If a variable is passed where
//! an integer is expected, that means the current value of the variable should
//! be used.
//!
//! "values" then become:
//!
//! * `.<alphanumeric>`: a variable containing some initial constants (see below)
//! * `$<alphanumeric>`: a variable representing a general purpose register or temporary
//! * `<alphanumeric>`: same as above, but can't be an integer literal
//! * `.undef`: delete the variable if this is assigned to it (like Option::None)
//! * `<a signed decimal integer>`: read this integer constant (limited to i64 precision)
//!
//!
//! Before evaluating a STACK WIN expression:
//!
//! * The variables `$ebp` and `$esp` should be initialized from the callee's
//! values for those registers (error out if those are unknown). `$ebx` should
//! similarly be initialized if it's available, since some things use it, but
//! it's optional.
//!
//! * The following constant variables should be set accordingly:
//! * `.cbParams = parameter_size`
//! * `.cbCalleeParams = grand_callee_parameter_size` (only for breakpad-generated exprs?)
//! * `.cbSavedRegs = saved_register_size`
//! * `.cbLocals = local_size`
//! * `.raSearch = $esp + frame_size`
//! * `.raSearchStart = .raSearch` (synonym that sometimes shows up?)
//!
//! Note that `.raSearch(Start)` roughly corresponds to STACK CFI's `.cfa`, in that
//! it generally points to where the return address is. However breakpad seems to
//! believe there are many circumstances where this value can be slightly wrong
//! (due to the frame pointer having mysterious extra alignment?). As such,
//! breakpad has several messy heuristics to "refine" `.raSearchStart`, such as
//! scanning the stack. This implementation does not (yet?) implement those
//! heuristics. As of this writing I have not encountered an instance of this
//! problem in the wild (but I haven't done much testing!).
//!
//!
//! After evaluating a STACK WIN expression:
//!
//! The caller's registers are stored in `$eip`, `$esp`, `$ebp`, `$ebx`, `$esi`,
//! and `$edi`. If those variables are undefined, then their values in the caller
//! are unknown. Do not implicitly forward registers that weren't explicitly set.
//!
//! (Should it be an error if the stack isn't empty at the end? It's
//! arguably malformed input but also it doesn't matter since the output is
//! in the variables? *shrug*)
//!
//!
//!
//! ## Example STACK WIN framedata evaluation
//!
//! Here is an example of framedata for a function with the standard prologue.
//! Given the input:
//!
//! ```text
//! $T0 $ebp = $eip $T0 4 + ^ = $ebp $T0 ^ = $esp $T0 8 + =
//! ```
//!
//! and initial state:
//!
//! ```text
//! ebp: 16, esp: 1600
//! ```
//!
//! Then evaluation proceeds as follows:
//!
//! ```text
//! Token | Stack | Vars
//! ---------+--------------+----------------------------------------------------
//! | | $ebp: 16, $esp: 1600,
//! $T0 | $T0 | $ebp: 16, $esp: 1600,
//! $ebp | $T0 $ebp | $ebp: 16, $esp: 1600,
//! = | | $ebp: 16, $esp: 1600, $T0: 16,
//! $eip | $eip | $ebp: 16, $esp: 1600, $T0: 16,
//! $T0 | $eip $T0 | $ebp: 16, $esp: 1600, $T0: 16,
//! 4 | $eip $T0 4 | $ebp: 16, $esp: 1600, $T0: 16,
//! + | $eip 20 | $ebp: 16, $esp: 1600, $T0: 16,
//! ^ | $eip (*20) | $ebp: 16, $esp: 1600, $T0: 16,
//! = | | $ebp: 16, $esp: 1600, $T0: 16, $eip: (*20)
//! $ebp | $ebp | $ebp: 16, $esp: 1600, $T0: 16, $eip: (*20)
//! $T0 | $ebp $T0 | $ebp: 16, $esp: 1600, $T0: 16, $eip: (*20)
//! ^ | $ebp (*16) | $ebp: 16, $esp: 1600, $T0: 16, $eip: (*20)
//! = | | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
//! $esp | $esp | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
//! $T0 | $esp $T0 | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
//! 8 | $esp $T0 8 | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
//! + | $esp 24 | $ebp: (*16), $esp: 1600, $T0: 16, $eip: (*20)
//! = | | $ebp: (*16), $esp: 24, $T0: 16, $eip: (*20)
//! ```
//!
//! Giving a final output of `ebp=(*16)`, `esp=24`, `eip=(*20)`.
use super::{CfiRules, StackInfoWin, WinStackThing};
use crate::FrameWalker;
use std::collections::HashMap;
use std::str::FromStr;
use tracing::{debug, trace};
pub fn walk_with_stack_cfi(
init: &CfiRules,
additional: &[CfiRules],
walker: &mut dyn FrameWalker,
) -> Option<()> {
trace!("trying STACK CFI exprs");
trace!(" {}", init.rules);
for line in additional {
trace!(" {}", line.rules);
}
// First we must collect up all the `REG: EXPR` pairs in these lines.
// If a REG occurs twice, we prefer the one that comes later. This allows
// STACK CFI records to apply incremental updates to the instructions.
let mut exprs = HashMap::new();
parse_cfi_exprs(&init.rules, &mut exprs)?;
for line in additional {
parse_cfi_exprs(&line.rules, &mut exprs)?;
}
trace!("STACK CFI parse successful");
// These two are special and *must* always be present
let cfa_expr = exprs.remove(&CfiReg::Cfa)?;
let ra_expr = exprs.remove(&CfiReg::Ra)?;
trace!("STACK CFI seems reasonable, evaluating");
// Evaluating the CFA cannot itself use the CFA
let cfa = eval_cfi_expr(cfa_expr, walker, None)?;
trace!("successfully evaluated .cfa (frame address)");
let ra = eval_cfi_expr(ra_expr, walker, Some(cfa))?;
trace!("successfully evaluated .ra (return address)");
walker.set_cfa(cfa)?;
walker.set_ra(ra)?;
for (reg, expr) in exprs {
if let CfiReg::Other(reg) = reg {
// If this eval fails, just don't emit this particular register
// and keep going on. It's fine to lose some general purpose regs,
// but make sure to clear it in case it would have been implicitly
// forwarded from the callee.
match eval_cfi_expr(expr, walker, Some(cfa)) {
Some(val) => {
walker.set_caller_register(reg, val);
trace!("successfully evaluated {}", reg);
}
None => {
walker.clear_caller_register(reg);
trace!("optional register {} failed to evaluate, dropping it", reg);
}
}
} else {
// All special registers should already have been removed??
unreachable!()
}
}
Some(())
}
fn parse_cfi_exprs<'a>(input: &'a str, output: &mut HashMap<CfiReg<'a>, &'a str>) -> Option<()> {
// Note this is an ascii format so we can think chars == bytes!
let base_addr = input.as_ptr() as usize;
let mut cur_reg = None;
let mut expr_first: Option<&str> = None;
let mut expr_last: Option<&str> = None;
for token in input.split_ascii_whitespace() {
if let Some(token) = token.strip_suffix(':') {
// This token is a "REG:", indicating the end of the previous EXPR
// and start of the next. If we already have an active register,
// then now is the time to commit it to our output.
if let Some(reg) = cur_reg {
// We compute the the expr substring by just abusing the fact that rust substrings
// point into the original string, so we can use map addresses in the substrings
// back into indices into the original string.
let min_addr = expr_first?.as_ptr() as usize;
let max_addr = expr_last?.as_ptr() as usize + expr_last?.len();
let expr = &input[min_addr - base_addr..max_addr - base_addr];
// Intentionally overwrite any pre-existing entries for this register,
// because that's how CFI records work.
output.insert(reg, expr);
expr_first = None;
expr_last = None;
}
cur_reg = if token == ".cfa" {
Some(CfiReg::Cfa)
} else if token == ".ra" {
Some(CfiReg::Ra)
} else if let Some(token) = token.strip_prefix('$') {
// x86-style $rax register
Some(CfiReg::Other(token))
} else {
// arm-style x11 register
Some(CfiReg::Other(token))
};
} else {
// First token *must* be a register!
cur_reg.as_ref()?;
// This is just another part of the current EXPR, update first/last accordingly.
if expr_first.is_none() {
expr_first = Some(token);
}
expr_last = Some(token);
}
}
// Process the final rule (there must be a defined reg!)
let min_addr = expr_first?.as_ptr() as usize;
let max_addr = expr_last?.as_ptr() as usize + expr_last?.len();
let expr = &input[min_addr - base_addr..max_addr - base_addr];
output.insert(cur_reg?, expr);
Some(())
}
fn eval_cfi_expr(expr: &str, walker: &mut dyn FrameWalker, cfa: Option<u64>) -> Option<u64> {
// FIXME: this should be an ArrayVec or something, most exprs are simple.
let mut stack: Vec<u64> = Vec::new();
for token in expr.split_ascii_whitespace() {
match token {
// FIXME?: not sure what overflow/sign semantics are, but haven't run into
// something where it actually matters (I wouldn't expect it to come up
// normally?).
"+" => {
// Add
let rhs = stack.pop()?;
let lhs = stack.pop()?;
stack.push(lhs.wrapping_add(rhs));
}
"-" => {
// Subtract
let rhs = stack.pop()?;
let lhs = stack.pop()?;
stack.push(lhs.wrapping_sub(rhs));
}
"*" => {
// Multiply
let rhs = stack.pop()?;
let lhs = stack.pop()?;
stack.push(lhs.wrapping_mul(rhs));
}
"/" => {
// Divide
let rhs = stack.pop()?;
let lhs = stack.pop()?;
if rhs == 0 {
// Div by 0
return None;
}
stack.push(lhs.wrapping_div(rhs));
}
"%" => {
// Remainder
let rhs = stack.pop()?;
let lhs = stack.pop()?;
if rhs == 0 {
// Div by 0
return None;
}
stack.push(lhs.wrapping_rem(rhs));
}
"@" => {
// Align (truncate)
let rhs = stack.pop()?;
let lhs = stack.pop()?;
if rhs == 0 || !rhs.is_power_of_two() {
return None;
}
// ~Bit Magic Corner~
//
// A power of two has only one bit set (e.g. 4 is 0b100), and
// subtracting 1 from that gets you all 1's below that bit (e.g. 0b011).
// -1 is all 1's.
//
// So XORing -1 with (power_of_2 - 1) gets you all ones except
// for the bits lower than the power of 2. ANDing that value
// to a number consequently makes it a multiple of that power
// of two (all the bits smaller than the power are cleared).
stack.push(lhs & (-1i64 as u64 ^ (rhs - 1)))
}
"^" => {
// Deref the value
let ptr = stack.pop()?;
stack.push(walker.get_register_at_address(ptr)?);
}
".cfa" => {
// Push the CFA. Note the CFA shouldn't be used to compute
// itself, so this returns None if that happens.
stack.push(cfa?);
}
".undef" => {
// This register is explicitly undefined!
return None;
}
_ => {
// More complex cases
if let Some((_, reg)) = token.split_once('$') {
// Push a register
stack.push(walker.get_callee_register(reg)?);
} else if let Ok(value) = i64::from_str(token) {
// Push a constant
// FIXME?: We do everything in wrapping arithmetic, so it's
// probably fine to squash i64's into u64's, but it seems sketchy?
// Division/remainder in particular seem concerning, but also
// it would be surprising to see negatives for those..?
stack.push(value as u64)
} else if let Some(reg) = walker.get_callee_register(token) {
// Maybe the register just didn't have a $ prefix?
// (seems to be how ARM syntax works).
stack.push(reg);
} else {
// Unknown expr
debug!(
"STACK CFI expression eval failed - unknown token: {}",
token
);
return None;
}
}
}
}
if stack.len() == 1 {
stack.pop()
} else {
None
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum CfiReg<'a> {
Cfa,
Ra,
Other(&'a str),
}
#[cfg(feature = "fuzz")]
pub fn eval_win_expr_for_fuzzer(
expr: &str,
info: &StackInfoWin,
walker: &mut dyn FrameWalker,
) -> Option<()> {
eval_win_expr(expr, info, walker)
}
fn eval_win_expr(expr: &str, info: &StackInfoWin, walker: &mut dyn FrameWalker) -> Option<()> {
// TODO?: do a bunch of heuristics to make this more robust.
// So far I haven't encountered an in-the-wild example that needs the
// extra heuristics that breakpad uses, so leaving them out until they
// become a problem.
let mut vars = HashMap::new();
let callee_esp = walker.get_callee_register("esp")? as u32;
let callee_ebp = walker.get_callee_register("ebp")? as u32;
let grand_callee_param_size = walker.get_grand_callee_parameter_size();
let frame_size = win_frame_size(info, grand_callee_param_size);
// First setup the initial variables
vars.insert("$esp", callee_esp);
vars.insert("$ebp", callee_ebp);
if let Some(callee_ebx) = walker.get_callee_register("ebx") {
vars.insert("$ebx", callee_ebx as u32);
}
let search_start = if expr.contains('@') {
// The frame has been aligned, so don't trust $esp. Assume $ebp
// is valid and that the standard calling convention is used
// (so the caller's $ebp was pushed right after the return address,
// and now $ebp points to that.)
trace!("program used @ operator, using $ebp instead of $esp for return addr");
callee_ebp.checked_add(4)?
} else {
// $esp should be reasonable, get the return address from that
callee_esp.checked_add(frame_size)?
};
trace!(
"raSearchStart = 0x{:08x} (0x{:08x}, 0x{:08x}, 0x{:08x})",
search_start,
grand_callee_param_size,
info.local_size,
info.saved_register_size
);
// Magic names from breakpad
vars.insert(".cbParams", info.parameter_size);
vars.insert(".cbCalleeParams", grand_callee_param_size);
vars.insert(".cbSavedRegs", info.saved_register_size);
vars.insert(".cbLocals", info.local_size);
vars.insert(".raSearch", search_start);
vars.insert(".raSearchStart", search_start);
// FIXME: this should be an ArrayVec or something..?
let mut stack: Vec<WinVal> = Vec::new();
// hack to fix bug where "= NEXT_TOKEN" is sometimes "=NEXT_TOKEN"
// for some windows toolchains.
let tokens = expr
.split_ascii_whitespace()
.flat_map(|x| {
if x.starts_with('=') && x.len() > 1 {
[Some(&x[0..1]), Some(&x[1..])]
} else {
[Some(x), None]
}
}) // get rid of the Array
.flatten(); // get rid of the Option::None's
// Evaluate the expressions
for token in tokens {
match token {
// FIXME: not sure what overflow/sign semantics are
"+" => {
// Add
let rhs = stack.pop()?.into_int(&vars)?;
let lhs = stack.pop()?.into_int(&vars)?;
stack.push(WinVal::Int(lhs.wrapping_add(rhs)));
}
"-" => {
// Subtract
let rhs = stack.pop()?.into_int(&vars)?;
let lhs = stack.pop()?.into_int(&vars)?;
stack.push(WinVal::Int(lhs.wrapping_sub(rhs)));
}
"*" => {
// Multiply
let rhs = stack.pop()?.into_int(&vars)?;
let lhs = stack.pop()?.into_int(&vars)?;
stack.push(WinVal::Int(lhs.wrapping_mul(rhs)));
}
"/" => {
// Divide
let rhs = stack.pop()?.into_int(&vars)?;
let lhs = stack.pop()?.into_int(&vars)?;
if rhs == 0 {
// Div by 0
return None;
}
stack.push(WinVal::Int(lhs.wrapping_div(rhs)));
}
"%" => {
// Remainder
let rhs = stack.pop()?.into_int(&vars)?;
let lhs = stack.pop()?.into_int(&vars)?;
if rhs == 0 {
// Div by 0
return None;
}
stack.push(WinVal::Int(lhs.wrapping_rem(rhs)));
}
"@" => {
// Align (truncate)
let rhs = stack.pop()?.into_int(&vars)?;
let lhs = stack.pop()?.into_int(&vars)?;
if rhs == 0 || !rhs.is_power_of_two() {
return None;
}
// ~Bit Magic Corner~
//
// A power of two has only one bit set (e.g. 4 is 0b100), and
// subtracting 1 from that gets you all 1's below that bit (e.g. 0b011).
// -1 is all 1's.
//
// So XORing -1 with (power_of_2 - 1) gets you all ones except
// for the bits lower than the power of 2. ANDing that value
// to a number consequently makes it a multiple of that power
// of two (all the bits smaller than the power are cleared).
stack.push(WinVal::Int(lhs & (-1i32 as u32 ^ (rhs - 1))));
}
"=" => {
// Assign lhs = rhs
let rhs = stack.pop()?;
let lhs = stack.pop()?.into_var()?;
if let WinVal::Undef = rhs {
vars.remove(&lhs);
} else {
vars.insert(lhs, rhs.into_int(&vars)?);
}
}
"^" => {
// Deref the value
let ptr = stack.pop()?.into_int(&vars)?;
stack.push(WinVal::Int(
walker.get_register_at_address(ptr as u64)? as u32
));
}
".undef" => {
// This register is explicitly undefined!
stack.push(WinVal::Undef);
}
_ => {
// More complex cases
if token == ".undef" {
stack.push(WinVal::Undef);
} else if token.starts_with('$') || token.starts_with('.') {
// Push a register
stack.push(WinVal::Var(token));
} else if let Ok(value) = i32::from_str(token) {
// Push a constant
// FIXME: We do everything in wrapping arithmetic, so it's fine to squash
// i32's into u32's?
stack.push(WinVal::Int(value as u32));
} else {
// Unknown expr
trace!(
"STACK WIN expression eval failed - unknown token: {}",
token
);
return None;
}
}
}
}
let output_regs = ["$eip", "$esp", "$ebp", "$ebx", "$esi", "$edi"];
for reg in &output_regs {
if let Some(&val) = vars.get(reg) {
walker.set_caller_register(®[1..], val as u64)?;
}
}
trace!("STACK WIN expression eval succeeded!");
Some(())
}
fn win_frame_size(info: &StackInfoWin, grand_callee_param_size: u32) -> u32 {
info.local_size + info.saved_register_size + grand_callee_param_size
}
enum WinVal<'a> {
Var(&'a str),
Int(u32),
Undef,
}
impl<'a> WinVal<'a> {
fn into_var(self) -> Option<&'a str> {
if let WinVal::Var(var) = self {
Some(var)
} else {
None
}
}
fn into_int(self, map: &HashMap<&'a str, u32>) -> Option<u32> {
match self {
WinVal::Var(var) => map.get(&var).cloned(),
WinVal::Int(int) => Some(int),
WinVal::Undef => None,
}
}
}
pub fn walk_with_stack_win_framedata(
info: &StackInfoWin,
walker: &mut dyn FrameWalker,
) -> Option<()> {
if let WinStackThing::ProgramString(ref expr) = info.program_string_or_base_pointer {
trace!("trying STACK WIN framedata -- {}", expr);
clear_stack_win_caller_registers(walker);
eval_win_expr(expr, info, walker)
} else {
unreachable!()
}
}
pub fn walk_with_stack_win_fpo(info: &StackInfoWin, walker: &mut dyn FrameWalker) -> Option<()> {
if let WinStackThing::AllocatesBasePointer(allocates_base_pointer) =
info.program_string_or_base_pointer
{
// FIXME: do a bunch of heuristics to make this more robust.
// Haven't needed the heuristics breakpad uses yet.
trace!("trying STACK WIN fpo");
clear_stack_win_caller_registers(walker);
let grand_callee_param_size = walker.get_grand_callee_parameter_size();
let frame_size = win_frame_size(info, grand_callee_param_size) as u64;
let callee_esp = walker.get_callee_register("esp")?;
let mut eip_address = callee_esp + frame_size;
let mut caller_eip = walker.get_register_at_address(eip_address)?;
// Check for a "leftover return address": in some pathological cases the return address isn't popped off the stack
// after a return instruction. According to breakpad, this can happen for "frame-pointer-optimized
// system calls", which implies that the callee must be a context frame.
//
// To detect these cases, we check whether
// 1. we are in a context frame. We approximate this by checking whether there's a grand-callee.
// 2. the caller's eip (aka the return address) is the same as the callee's eip.
//
// If we detect a leftover return address, we skip it and try again one word
// further down the stack.
let callee_is_context_frame = !walker.has_grand_callee();
if callee_is_context_frame && caller_eip == walker.get_callee_register("eip")? {
eip_address += 4;
caller_eip = walker.get_register_at_address(eip_address)?;
}
let caller_esp = eip_address + 4;
trace!("found caller $eip and $esp");
let caller_ebp = if allocates_base_pointer {
let ebp_address =
callee_esp + grand_callee_param_size as u64 + info.saved_register_size as u64 - 8;
walker.get_register_at_address(ebp_address)?
} else {
// Per Breakpad: We also propagate %ebx through, as it is commonly unmodifed after
// calling simple forwarding functions in ntdll (that are this non-EBP
// using type). It's not clear that this is always correct, but it is
// important for some functions to get a correct walk.
if let Some(callee_ebx) = walker.get_callee_register("ebx") {
walker.set_caller_register("ebx", callee_ebx)?;
}
walker.get_callee_register("ebp")?
};
trace!("found caller $ebp");
walker.set_caller_register("eip", caller_eip)?;
walker.set_caller_register("esp", caller_esp)?;
walker.set_caller_register("ebp", caller_ebp)?;
trace!("STACK WIN fpo eval succeeded!");
Some(())
} else {
unreachable!()
}
}
/// STACK WIN doesn't want implicit register forwarding
fn clear_stack_win_caller_registers(walker: &mut dyn FrameWalker) {
let output_regs = ["$eip", "$esp", "$ebp", "$ebx", "$esi", "$edi"];
for reg in output_regs {
walker.clear_caller_register(reg);
}
}
#[cfg(test)]
mod test {
use super::super::types::{CfiRules, StackInfoWin, WinStackThing};
use super::{eval_win_expr, walk_with_stack_cfi, walk_with_stack_win_fpo};
use crate::FrameWalker;
use std::collections::HashMap;
// Eugh, need this to memoize register names to static
static STATIC_REGS: [&str; 14] = [
"cfa", "ra", "esp", "eip", "ebp", "eax", "ebx", "rsp", "rip", "rbp", "rax", "rbx", "x11",
"x12",
];
struct TestFrameWalker<Reg> {
instruction: Reg,
has_grand_callee: bool,
grand_callee_param_size: u32,
callee_regs: HashMap<&'static str, Reg>,
caller_regs: HashMap<&'static str, Reg>,
stack: Vec<u8>,
}
trait Int {
const BYTES: usize;
fn from_bytes(bytes: &[u8]) -> Self;
fn into_u64(self) -> u64;
fn from_u64(val: u64) -> Self;
}
impl Int for u32 {
const BYTES: usize = 4;
fn from_bytes(bytes: &[u8]) -> Self {
let mut buf = [0; Self::BYTES];
buf.copy_from_slice(bytes);
u32::from_le_bytes(buf)
}
fn into_u64(self) -> u64 {
self as u64
}
fn from_u64(val: u64) -> Self {
val as u32
}
}
impl Int for u64 {
const BYTES: usize = 8;
fn from_bytes(bytes: &[u8]) -> Self {
let mut buf = [0; Self::BYTES];
buf.copy_from_slice(bytes);
u64::from_le_bytes(buf)
}
fn into_u64(self) -> u64 {
self
}
fn from_u64(val: u64) -> Self {
val
}
}
impl<Reg: Int + Copy> FrameWalker for TestFrameWalker<Reg> {
fn get_instruction(&self) -> u64 {
self.instruction.into_u64()
}
fn has_grand_callee(&self) -> bool {
self.has_grand_callee
}
fn get_grand_callee_parameter_size(&self) -> u32 {
self.grand_callee_param_size
}
/// Get a register-sized value stored at this address.
fn get_register_at_address(&self, address: u64) -> Option<u64> {
let addr = address as usize;
self.stack
.get(addr..addr + Reg::BYTES)
.map(|slice| Reg::from_bytes(slice).into_u64())
}
/// Get the value of a register from the callee's frame.
fn get_callee_register(&self, name: &str) -> Option<u64> {
self.callee_regs.get(name).map(|val| val.into_u64())
}
/// Set the value of a register for the caller's frame.
fn set_caller_register(&mut self, name: &str, val: u64) -> Option<()> {
STATIC_REGS.iter().position(|®| reg == name).map(|idx| {
let memoized_reg = STATIC_REGS[idx];
self.caller_regs.insert(memoized_reg, Reg::from_u64(val));
})
}
fn clear_caller_register(&mut self, name: &str) {
self.caller_regs.remove(name);
}
/// Set whatever registers in the caller should be set based on the cfa (e.g. rsp).
fn set_cfa(&mut self, val: u64) -> Option<()> {
self.caller_regs.insert("cfa", Reg::from_u64(val));
Some(())
}
/// Set whatever registers in the caller should be set based on the return address (e.g. rip).
fn set_ra(&mut self, val: u64) -> Option<()> {
self.caller_regs.insert("ra", Reg::from_u64(val));
Some(())
}
}
impl<Reg: Int + Copy> TestFrameWalker<Reg> {
fn new(stack: Vec<u8>, callee_regs: HashMap<&'static str, Reg>) -> Self {
TestFrameWalker {
stack,
callee_regs,
caller_regs: HashMap::new(),
// Arbitrary values
instruction: Reg::from_u64(0xF1CEFA32),
has_grand_callee: true,
grand_callee_param_size: 4,
}
}
}
/// Arbitrary default values in case needed.
fn whatever_win_info() -> StackInfoWin {
StackInfoWin {
address: 0xFEA4A123,
size: 16,
prologue_size: 4,
epilogue_size: 8,
parameter_size: 16,
saved_register_size: 12,
local_size: 24,
max_stack_size: 64,
program_string_or_base_pointer: WinStackThing::AllocatesBasePointer(false),
}
}
fn build_cfi_rules(init: &str, additional: &[&str]) -> (CfiRules, Vec<CfiRules>) {
let init = CfiRules {
address: 0,
rules: init.to_string(),
};
let additional = additional
.iter()
.enumerate()
.map(|(idx, rules)| CfiRules {
address: idx as u64 + 1,
rules: rules.to_string(),
})
.collect::<Vec<_>>();
(init, additional)
}
#[test]
fn test_stack_win_doc_example() {
// Final output of `ebp=(*16)`, `esp=24`, `eip=(*20)`.
let expr = "$T0 $ebp = $eip $T0 4 + ^ = $ebp $T0 ^ = $esp $T0 8 + =";
let input = vec![("ebp", 16u32), ("esp", 1600)].into_iter().collect();
let mut stack = vec![0; 1600];
const FINAL_EBP: u32 = 0xFA1EF2E6;
const FINAL_EIP: u32 = 0xB3EF04CE;
stack[16..20].copy_from_slice(&FINAL_EBP.to_le_bytes());
stack[20..24].copy_from_slice(&FINAL_EIP.to_le_bytes());
let mut walker = TestFrameWalker::new(stack, input);
let info = whatever_win_info();
eval_win_expr(expr, &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 3);
assert_eq!(walker.caller_regs["esp"], 24);
assert_eq!(walker.caller_regs["ebp"], FINAL_EBP);
assert_eq!(walker.caller_regs["eip"], FINAL_EIP);
}
#[test]
fn test_stack_win_ops() {
// Making sure all the operators do what they should.
let input = vec![("esp", 32u32), ("ebp", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
let info = whatever_win_info();
// Addition!
walker.caller_regs.clear();
eval_win_expr("$esp 1 2 + = $ebp -4 0 + =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 3);
assert_eq!(walker.caller_regs["ebp"], -4i32 as u32);
// Subtraction!
walker.caller_regs.clear();
eval_win_expr("$esp 5 3 - = $ebp -4 2 - =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 2);
assert_eq!(walker.caller_regs["ebp"], -6i32 as u32);
// Multiplication!
walker.caller_regs.clear();
eval_win_expr("$esp 5 3 * = $ebp -4 2 * =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 15);
assert_eq!(walker.caller_regs["ebp"], -8i32 as u32);
// Division!
walker.caller_regs.clear();
eval_win_expr("$esp 5 3 / = $ebp -4 2 / =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 1);
// TODO: oh no this fails, u64/u32 mismatches ARE a problem... at least
// for this synthetic example!
// assert_eq!(walker.caller_regs["ebp"], -2i32 as u32);
// Modulo!
walker.caller_regs.clear();
eval_win_expr("$esp 5 3 % = $ebp -1 2 % = ", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 2);
assert_eq!(walker.caller_regs["ebp"], 1);
// Align!
walker.caller_regs.clear();
eval_win_expr("$esp 8 16 @ = $ebp 161 8 @ = ", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 0);
assert_eq!(walker.caller_regs["ebp"], 160);
// Operator Errors - Missing Inputs
// + missing args
assert!(eval_win_expr("1 + ", &info, &mut walker).is_none());
// - missing args
assert!(eval_win_expr("1 -", &info, &mut walker).is_none());
// * missing args
assert!(eval_win_expr("1 *", &info, &mut walker).is_none());
// / missing args
assert!(eval_win_expr("1 /", &info, &mut walker).is_none());
// % missing args
assert!(eval_win_expr("1 %", &info, &mut walker).is_none());
// @ missing args
assert!(eval_win_expr("1 @", &info, &mut walker).is_none());
// ^ missing arg
assert!(eval_win_expr("^", &info, &mut walker).is_none());
// Operator Errors - Invalid Inputs
// / by 0
assert!(eval_win_expr("$esp 1 0 / = $ebp 1 =", &info, &mut walker).is_none());
// % by 0
assert!(eval_win_expr("$esp 1 0 % = $ebp 1 =", &info, &mut walker).is_none());
// @ by 0
assert!(eval_win_expr("$esp 1 0 @ = $ebp 1 =", &info, &mut walker).is_none());
// @ not power of 2
assert!(eval_win_expr("$esp 1 3 @ = $ebp 1 =", &info, &mut walker).is_none());
}
#[test]
fn test_stack_win_corners() {
// Making sure all the operators do what they should.
let input = vec![("esp", 32u32), ("ebp", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
let info = whatever_win_info();
// Empty expression is ok, just forward through registers
walker.caller_regs.clear();
eval_win_expr("", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 32);
assert_eq!(walker.caller_regs["ebp"], 1600);
// Undef works
walker.caller_regs.clear();
eval_win_expr("$esp .undef = $ebp .undef =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 0);
// Idempotent works
walker.caller_regs.clear();
eval_win_expr("$esp $esp = $ebp $ebp =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 32);
assert_eq!(walker.caller_regs["ebp"], 1600);
// Trailing garbage in the stack is ok
walker.caller_regs.clear();
eval_win_expr("$esp 1 = $ebp 2 = 3 4 5", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 1);
assert_eq!(walker.caller_regs["ebp"], 2);
// Trailing garbage in the stack is ok (with variables)
walker.caller_regs.clear();
eval_win_expr("$esp 1 = $ebp 2 = 3 4 5 $esp $eax", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 1);
assert_eq!(walker.caller_regs["ebp"], 2);
// Temporaries don't get assigned to output
walker.caller_regs.clear();
eval_win_expr("$t0 1 = $esp $t0 5 + = $ebp 2 =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 6);
assert_eq!(walker.caller_regs["ebp"], 2);
// Variables can be assigned after they are pushed
walker.caller_regs.clear();
eval_win_expr("$esp $T0 $T0 2 = = $ebp 3 =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 2);
assert_eq!(walker.caller_regs["ebp"], 3);
}
#[test]
fn test_stack_win_errors() {
// Making sure all the operators do what they should.
let input = vec![("esp", 32u32), ("ebp", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
let info = whatever_win_info();
// Deref out of bounds
assert!(eval_win_expr("$esp 2000 ^ =", &info, &mut walker).is_none());
// Reading undefined value
assert!(eval_win_expr("$esp $kitties =", &info, &mut walker).is_none());
// Reading value before defined
assert!(eval_win_expr("$esp $kitties = $kitties 1 =", &info, &mut walker).is_none());
// Reading deleted value
assert!(eval_win_expr("$esp .undef = $ebp $esp =", &info, &mut walker).is_none());
// Assigning value to value
assert!(eval_win_expr("0 2 =", &info, &mut walker).is_none());
// Assigning variable to value
assert!(eval_win_expr("0 $esp =", &info, &mut walker).is_none());
// Variables must start with $ or .
assert!(eval_win_expr("esp 2 = ebp 3 =", &info, &mut walker).is_none());
}
#[test]
fn test_stack_win_equal_fixup() {
// Bug in old windows toolchains that sometimes cause = to lose
// its trailing space. Although we would ideally reject this, we're
// at the mercy of what toolchains emit :(
// TODO: this test currently fails! (hence the #[ignore])
let input = vec![("esp", 32u32), ("ebp", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
let info = whatever_win_info();
eval_win_expr("$esp 1 =$ebp 2 =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 1);
assert_eq!(walker.caller_regs["ebp"], 2);
}
#[test]
#[ignore]
fn test_stack_win_negative_division() {
// Negative division issues
// TODO: this test currently fails! (hence the #[ignore])
let input = vec![("esp", 32u32), ("ebp", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
let info = whatever_win_info();
// Division!
walker.caller_regs.clear();
eval_win_expr("$esp 5 3 / = $ebp -4 2 / =", &info, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["esp"], 1);
assert_eq!(walker.caller_regs["ebp"], -2i32 as u32);
}
#[test]
fn test_stack_win_leftover_return_address() {
// The return address on top of the stack (0xABCD_1234) is equal to the callee's eip, indicating
// a return address that was left over from a return. The stackwalker should skip it and
// return the second value on the stack (0xABCD_5678) as the caller's eip.
let stack = vec![0x34, 0x12, 0xCD, 0xAB, 0x78, 0x56, 0xCD, 0xAB];
let mut walker = TestFrameWalker {
instruction: 0xABCD_1234u32,
has_grand_callee: false,
grand_callee_param_size: 0,
callee_regs: vec![("eip", 0xABCD_1234), ("esp", 0), ("ebp", 17)]
.into_iter()
.collect(),
caller_regs: HashMap::new(),
stack,
};
// these are all dummy values
let info = StackInfoWin {
address: 0,
size: 0,
prologue_size: 0,
epilogue_size: 0,
parameter_size: 0,
saved_register_size: 0,
local_size: 0,
max_stack_size: 0,
program_string_or_base_pointer: WinStackThing::AllocatesBasePointer(false),
};
walk_with_stack_win_fpo(&info, &mut walker).unwrap();
assert_eq!(walker.caller_regs["esp"], 8);
assert_eq!(walker.caller_regs["ebp"], 17);
assert_eq!(walker.caller_regs["eip"], 0xABCD_5678);
}
#[test]
fn test_stack_cfi_doc_example() {
// Final output of:
//
// cfa = callee_rsp + 24
// ra = *(cfa - 8)
// rax = *(cfa - 16)
let init = ".cfa: $rsp 8 + .ra: .cfa -8 + ^";
let additional = &[".cfa: $rsp 16 + $rax: .cfa -16 + ^", ".cfa: $rsp 24 +"];
let input = vec![("rsp", 32u64), ("rip", 1600)].into_iter().collect();
let mut stack = vec![0; 1600];
const FINAL_CFA: usize = 32 + 24;
const FINAL_RA: u64 = 0xFA1E_F2E6_A2DF_2B68;
const FINAL_RAX: u64 = 0xB3EF_04CE_4321_FE2A;
stack[FINAL_CFA - 8..FINAL_CFA].copy_from_slice(&FINAL_RA.to_le_bytes());
stack[FINAL_CFA - 16..FINAL_CFA - 8].copy_from_slice(&FINAL_RAX.to_le_bytes());
let mut walker = TestFrameWalker::new(stack, input);
let (init, additional) = build_cfi_rules(init, additional);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 3);
assert_eq!(walker.caller_regs["cfa"], FINAL_CFA as u64);
assert_eq!(walker.caller_regs["ra"], FINAL_RA);
assert_eq!(walker.caller_regs["rax"], FINAL_RAX);
}
#[test]
fn test_stack_cfi_ops() {
// Making sure all the operators do what they should, using 32-bit
// to stress truncation issues from u64 <-> u32 mapping of the
// abstraction.
let input = vec![("esp", 32u32), ("eip", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
// Addition!
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 1 2 + .ra: -4 0 +", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 3);
assert_eq!(walker.caller_regs["ra"], -4i32 as u32);
// Subtraction!
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 5 3 - .ra: -4 2 -", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 2);
assert_eq!(walker.caller_regs["ra"], -6i32 as u32);
// Multiplication!
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 5 3 * .ra: -4 2 *", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 15);
assert_eq!(walker.caller_regs["ra"], -8i32 as u32);
// Division!
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 5 3 / .ra: -4 2 /", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 1);
assert_eq!(walker.caller_regs["ra"], -2i32 as u32);
// Modulo!
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 5 3 % .ra: -1 2 %", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 2);
assert_eq!(walker.caller_regs["ra"], 1);
// Align!
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 8 16 @ .ra: 161 8 @", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 0);
assert_eq!(walker.caller_regs["ra"], 160);
// Operator Errors - Missing Inputs
// + missing args
let (init, additional) = build_cfi_rules(".cfa: 1 + .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// - missing args
let (init, additional) = build_cfi_rules(".cfa: 1 - .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// * missing args
let (init, additional) = build_cfi_rules(".cfa: 1 * .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// / missing args
let (init, additional) = build_cfi_rules(".cfa: 1 / .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// % missing args
let (init, additional) = build_cfi_rules(".cfa: 1 % .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// @ missing args
let (init, additional) = build_cfi_rules(".cfa: 1 @ .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// ^ missing arg
let (init, additional) = build_cfi_rules(".cfa: ^ .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Operator Errors - Invalid Inputs
// / by 0
let (init, additional) = build_cfi_rules(".cfa: 1 0 / .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// % by 0
let (init, additional) = build_cfi_rules(".cfa: 1 0 % .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// @ by 0
let (init, additional) = build_cfi_rules(".cfa: 1 0 @ .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// @ not power of 2
let (init, additional) = build_cfi_rules(".cfa: 1 3 @ .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
}
#[test]
fn test_stack_cfi_errors() {
// Checking various issues that we should bail on
let input = vec![("rsp", 32u64), ("rip", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
// Basic syntax
// Missing .ra
let (init, additional) = build_cfi_rules(".cfa: 8 16 +", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Missing .cfa
let (init, additional) = build_cfi_rules(".ra: 8 16 *", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// No : at all
let (init, additional) = build_cfi_rules(".cfa 8 16 *", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Doesn't start with a REG
let (init, additional) = build_cfi_rules(".esp 8 16 * .cfa: 16 .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// .cfa has extra junk on stack
let (init, additional) = build_cfi_rules(".cfa: 8 12 .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// REG has empty expr (trailing)
let (init, additional) = build_cfi_rules(".cfa: 12 .ra: 8 $rax:", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// REG has empty expr (trailing with space)
let (init, additional) = build_cfi_rules(".cfa: 12 .ra: 8 $rax: ", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// REG has empty expr (middle)
let (init, additional) = build_cfi_rules(".cfa: 12 .ra: 8 $rax: $rbx: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Make sure = operator isn't supported in this implementation
let (init, additional) = build_cfi_rules(".cfa: 12 .ra: $rsp $rip =", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// .cfa is undef
let (init, additional) = build_cfi_rules(".cfa: .undef .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// .ra is undef
let (init, additional) = build_cfi_rules(".cfa: 8 .ra: .undef", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Reading out of bounds
let (init, additional) = build_cfi_rules(".cfa: 2000 ^ .ra: 8", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Reading fake $reg
let (init, additional) = build_cfi_rules(".cfa: 8 .ra: $kitties", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Reading real but still undefined $reg
let (init, additional) = build_cfi_rules(".cfa: 8 .ra: $rax", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Reading .cfa for .cfa's own value
let (init, additional) = build_cfi_rules(".cfa: .cfa .ra: 2", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Reading .ra for .cfa's value
let (init, additional) = build_cfi_rules(".cfa: .ra .ra: 2", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Reading .ra for .ra's value
let (init, additional) = build_cfi_rules(".cfa: 1 .ra: .ra", &[]);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
// Malformed doc example shouldn't work (found while typoing docs)
// Note the first .cfa in the additional lines has no `:`!
let (init, additional) = build_cfi_rules(
".cfa: $rsp 8 + .ra: .cfa -8 + ^",
&[".cfa $rsp 16 + $rax: .cfa -16 + ^", ".cfa $rsp 24 +"],
);
assert!(walk_with_stack_cfi(&init, &additional, &mut walker).is_none());
}
#[test]
fn test_stack_cfi_corners() {
// Checking various issues that we should bail on
let input = vec![("rsp", 32u64), ("rip", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
// Just a value for each reg (no ops to execute)
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 8 .ra: 12 $rax: 16", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 3);
assert_eq!(walker.caller_regs["cfa"], 8);
assert_eq!(walker.caller_regs["ra"], 12);
assert_eq!(walker.caller_regs["rax"], 16);
// Undef $REGs are ok, Undef in the middle of expr ok
walker.caller_regs.clear();
let (init, additional) =
build_cfi_rules(".cfa: 8 .ra: 12 $rax: .undef $rbx: 1 .undef +", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 8);
assert_eq!(walker.caller_regs["ra"], 12);
// Unknown $reg output is ok; evaluated but value discarded
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 8 .ra: 12 $kitties: 16", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 8);
assert_eq!(walker.caller_regs["ra"], 12);
// Smooshed regs are garbage but we don't validate the string so it should work
// the same as an unknown reg (dubious behaviour but hey let's be aware of it).
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 12 .ra: 8 $rax:$rbx: 8", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 12);
assert_eq!(walker.caller_regs["ra"], 8);
// Evaluation errors for $reg output ok; value is discarded
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 1 .ra: 8 $rax: 1 0 /", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 1);
assert_eq!(walker.caller_regs["ra"], 8);
// Duplicate records are ok (use the later one)
walker.caller_regs.clear();
let (init, additional) =
build_cfi_rules(".cfa: 1 .cfa: 2 .ra: 3 .ra: 4 $rax: 5 $rax: 6", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 3);
assert_eq!(walker.caller_regs["cfa"], 2);
assert_eq!(walker.caller_regs["ra"], 4);
assert_eq!(walker.caller_regs["rax"], 6);
// Using .cfa works fine
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 7 .ra: .cfa 1 + $rax: .cfa 2 -", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 3);
assert_eq!(walker.caller_regs["cfa"], 7);
assert_eq!(walker.caller_regs["ra"], 8);
assert_eq!(walker.caller_regs["rax"], 5);
// Reading .ra for $REG's value is ok; value is discarded
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 1 .ra: 2 $rax: .ra", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 1);
assert_eq!(walker.caller_regs["ra"], 2);
// Undefined destination .reg is assumed to be an ARM-style register, is dropped
let (init, additional) = build_cfi_rules(".cfa: 8 .ra: 12 .kitties: 16", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 8);
assert_eq!(walker.caller_regs["ra"], 12);
// Trying to write to .undef is assumed to be an ARM-style register, is dropped
let (init, additional) = build_cfi_rules(".cfa: 8 .ra: 12 .undef: 16", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 2);
assert_eq!(walker.caller_regs["cfa"], 8);
assert_eq!(walker.caller_regs["ra"], 12);
}
#[test]
fn test_stack_cfi_arm() {
// ARM doesn't prefix registers with $
// Checking various issues that we should bail on
let input = vec![("pc", 32u64), ("x11", 1600)].into_iter().collect();
let stack = vec![0; 1600];
let mut walker = TestFrameWalker::new(stack, input);
// Just a value for each reg (no ops to execute)
walker.caller_regs.clear();
let (init, additional) = build_cfi_rules(".cfa: 8 .ra: 12 x11: 16 x12: x11 .cfa +", &[]);
walk_with_stack_cfi(&init, &additional, &mut walker).unwrap();
assert_eq!(walker.caller_regs.len(), 4);
assert_eq!(walker.caller_regs["cfa"], 8);
assert_eq!(walker.caller_regs["ra"], 12);
assert_eq!(walker.caller_regs["x11"], 16);
assert_eq!(walker.caller_regs["x12"], 1608);
}
}