Rudder: The BitBlaze Mixed Execution Component
[Overview] [Publications] [Back to BitBlaze]
The BitBlaze infrastructure provides a component, called
Rudder, for online dynamic symbolic execution that interleaves
concrete and symbolic execution, which we call mixed execution. Mixed
execution begins by a user marking data locations of interest, such as
memory locations, registers, return values from functions, etc. The
marked locations are assigned a symbolic variable. Mixed execution
then executes all code which is independent of the marked
locations concretely on the native processor, and all code which is
dependent symbolically. Symbolic execution builds up a logical
formula based upon the operands. For example, if R_EAX is symbolic,
and the instruction sequence:
R_ECX = R_EAX + 5
R_EDX = R_ECX + R_ECX
The final formula for R_EDX will be equivalent to (R_EAX+5)*2.
Mixed execution has two important properties. First, any execution
based upon a symbolic variable is not constrained to a particular
value. Thus, we can reason about any actual value for such
variables. Second, any code that does not depend upon a symbolic
variable is executed efficiently on the native processor. In a sense,
the concrete execution allows us to perform constant propagation and
constant folding for many instructions using the native processor. We
have found in many problem scenarios upwards of 99% of all code can
be executed concretely, thus yielding a tremendous performance
improvement over symbolic execution alone.
- Automatically Identifying
Trigger-based Behavior in Malware
- David Brumley, Cody Hartwig, Zhenkai Liang James Newsome,
Dawn Song, and Heng Yin. Book chapter in "Botnet Analysis and Defense", Editors Wenke Lee et. al., 2007.
- BitScope: Automatically Dissecting Malicious Binaries
- David Brumley, Cody Hartwig, Min Gyung Kang, Zhenkai Liang
James Newsome, Pongsin Poosankam, Dawn Song, and Heng Yin.
Technical Report CMU-CS-07-133, School of Computer Science, Carnegie
Mellon University, March 18, 2007
Back to BitBlaze