[DynInst_API:] Proposed Interface for Stack Modifications

[Emily Gember-Jacobson <jacobson@xxxxxxxxxxx>]

Hi all,

I've been doing some work with modifying the stack frame layout of functions, and we're now planning on integrating this into Dyninst. ÂCurrently, this is primarily intended for use in binary rewriting; there are some potentially unresolved issues with dynamic instrumentation.Â

After some internal discussion, I'm sending this out for wider feedback. I'm including a proposed interface, with an overview of how we expect these features to work. Feedback is welcome.

A new abstract class: StackMod. A StackMod defines the modification that will be performed. We propose 5 child classes for StackMod (I've included constructors):
Insert(low, high);Â

This modification inserts stack space in the range [low, high), where low and high are stack offsets.Â

Remove(low, high);

This modification removes stack space in the range [low, high).

Move(sLow, sHigh, dLow);

ThisÂmodificationÂmoves stack space [sLow, sHigh) to [dlow, dLow+(sHigh-sLow)).

Canary();Â

ThisÂmodificationÂinserts a stack canary at function entry and corresponding canary check atÂfunction exit (uses the same canary/canary check as gcc's -fstack-protector).

Randomize();

ThisÂmodificationÂdiversifies the stack frame by randomizing the locations of DWARF-identified localÂvariables.

We define stack modifications to have function scope. Each stack modification defines both a change to the stack frame layout as well as a series of code changes required to perform such a change. Internally, we use stack analysis to determine any locations in the function where new code must be added to support a given modification. For example, to insert stack space, we emit code to shift the stack pointer by the specified amount. Some stack modifications require a second, paired modification (e.g., inserting stack space requires a corresponding remove before function exit); defining stack modifications at function scope allows use to easily add the corresponding cleanup.

Further, a sensitivity analysis has been added to determine which instructions access relocated stack memory or stack memory shifted due to modifications; these instructions are updated during relocation to access the new stack locations.

StackMods are installed with a new member function for BPatch_function:
bool addMods(std::set<StackMod*>);

This function performs error checking, generates padding when required for stack alignment, handles modifications the require cleanup, and generates the appropriate ASTs.

This function fails if the stack modifications are deemed unsafe (e.g., removing stack memory that is accessed by an instruction in the function), or if we are unable to perform the analysis required to guarantee safety.

If you're interested, a slightly longer explanation of the abstractions and analyses we use:

Stack modifications are based on the abstraction of stack locations, not the contents of these locations. We use the existing stack analysis (in DataflowAPI) and a simple per-instruction memory access analysis to determine whether an instructions accesses a stack memory locations (and the size of the access). Sensitivity analysis then determines which of these memory access instructions access stack locations that have been perturbed, and modifies the instruction accordingly. In cases where stack analysis finds a memory access off of a register with a non-unique (or not understood) stack height (i.e., BOTTOM in the lattice), we (conservatively) mark the function as un-modifiable.

We primarily use DWARF to provide information about the sizes of stack variables--in particular, sizes of aggregates, since these must be kept in-tact during any modifications; our instruction memory access analysis cannot detect aggregates. When we randomize a stack frame, we only move DWARF-identified local variables because these are an easier, safer subset than all accessed stack locations within a function.

Best,
Emily