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
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