Dynamic Binary TranslationLecture 24acknowledgement: E. Duesterwald (IBM), S. Amarasinghe (MIT)1Ras Bodik CS 164 Lecture 24Lecture Outline Binary Translation: Why, What, and When. Why: Guarding against buffer overruns What, when: overview of two dynamic translators: Dynamo-RIO by HP, MIT CodeMorph by Transmeta Techniques used in dynamic translators Path profiling2Ras Bodik CS 164 Lecture 24Motivation: preventing buffer overrunsRecall the typical buffer overrun attack:program calls a method foo()foo() copies a string into an on-stack array: string supplied by the user users malicious code copied into foos array foos return address overwritten to point to user codefoo() returns unknowingly jumping to the user code3Ras Bodik CS 164 Lecture 24Preventing buffer overrun attacksTwo general approaches: static (compile-time): analyze the program find all array writes that may outside array bounds program proven safe before you run it dynamic (run-time): analyze the execution make sure no write outside an array happens execution proven safe (enough to achieve security)4Ras Bodik CS 164 Lecture 24Dynamic buffer overrun preventionthe idea, again: prevent writes outside the intended array as is done in Java harder in C: must add “size” to each array done in CCured, a Berkeley project5Ras Bodik CS 164 Lecture 24A different ideaperhaps less safe, but easier to implement: goal: detect that return address was overwritten.instrument the program so that it keeps an extra copy of the return address:store aside the return address when function called (store it in an inaccessible shadow stack) when returning, check that the return address in AR matches the stored one; if mismatch, terminate program6Ras Bodik CS 164 Lecture 24Commercially interesting Similar idea behind the product by determina.com key problem: reducing overhead of instrumentation whats instrumentation, anyway? adding statements to an existing program in our case, to x86 executables Determina uses binary translation7Ras Bodik CS 164 Lecture 24What is Binary Translation? Translating a program in one binary format to another, for example:MIPS x86 (to port programs across platforms) We can view “binary format” liberally:Java bytecode x86 (to avoid interpretation) x86 x86 (to optimize the executable)8Ras Bodik CS 164 Lecture 24When does the translation happen? Static (off-line): before the program is run Pros: no serious translation-time constraints Dynamic (on-line): while the program is running Pros: access to complete program (program is fully linked) access to program state (including values of data structs) can adapt to changes in program behavior Note: Pros(dynamic) = Cons(static) 9Ras Bodik CS 164 Lecture 24Why? Translation Allows Program ModificationProgram Compiler Linker Loader Runtime SystemStatic Dynamic Instrumenters Load time optimizers Shared library mechanism Debuggers Interpreters Just-In-Time Compilers Dynamic Optimizers Profilers Dynamic Checkers instrumenters Etc.10Ras Bodik CS 164 Lecture 24Applications, in more detail profilers: add instrumentation instructions to count basic block execution counts (e.g., gprof) load-time optimizers: remove caller/callee save instructions (callers/callees known after DLLs are linked) replace long jumps with short jumps (code position known after linking) dynamic checkers finding memory access bugs (e.g., Rational Purify)11Ras Bodik CS 164 Lecture 24Dynamic Program ModifiersRunning ProgramDynamic Program Modifier: Observe/Manipulate Every Instruction in the Running ProgramHardware Platform12Ras Bodik CS 164 Lecture 24In more detailcommon setupCPUOSDLLapplicationCodeMorphOSDLLapplicationCPU=VLIWCodeMorph (Transmeta)Dynamo- RIO (HP, MIT)CPU=x86DLLapplicationDynamoOS13Ras Bodik CS 164 Lecture 24Dynamic Program ModifiersRequirements: : Ability to intercept execution at arbitrary points Observe executing instructions Modify executing instructions Transparency - modified program is not specially prepared Efficiency - amortize overhead and achieve near-native performance Robustness Maintain full control and capture all code- sampling is not an option (there are security applications)14Ras Bodik CS 164 Lecture 24HP Dynamo-RIOBuilding a dynamic program modifierTrick I: adding a code cache Trick II: linking Trick III: efficient indirect branch handling Trick IV: picking traces Dynamo-RIO performance Run-time trace optimizations15Ras Bodik CS 164 Lecture 24next VPCInstruction InterpreterSystem I: Basic Interpreterdecodefetch next instructionexecuteexception handlingupdate VPC Intercept execution Observe & modify executing instructions Transparency Efficiency? - up to several 100 X slowdown16Ras Bodik CS 164 Lecture 24context switchBASIC BLOCK CACHEnon-control-flow instructionsTrick I: Adding a Code Cachenext VPCfetch block at VPClookup VPC emit blockexception h