1、Ras Bodik CS 164 Lecture 24,1,Dynamic Binary Translation,Lecture 24acknowledgement: E. Duesterwald (IBM), S. Amarasinghe (MIT),Ras Bodik CS 164 Lecture 24,2,Lecture Outline,Binary Translation: Why, What, and When.Why: Guarding against buffer overrunsWhat, when: overview of two dynamic translators: D
2、ynamo-RIO by HP, MIT CodeMorph by TransmetaTechniques used in dynamic translators Path profiling,Ras Bodik CS 164 Lecture 24,3,Motivation: preventing buffer overruns,Recall the typical buffer overrun attack:program calls a method foo()foo() copies a string into an on-stack array: string supplied by
3、the user users malicious code copied into foos array foos return address overwritten to point to user codefoo() returns unknowingly jumping to the user code,Ras Bodik CS 164 Lecture 24,4,Preventing buffer overrun attacks,Two general approaches:static (compile-time): analyze the program find all arra
4、y writes that may outside array bounds program proven safe before you run itdynamic (run-time): analyze the execution make sure no write outside an array happens execution proven safe (enough to achieve security),Ras Bodik CS 164 Lecture 24,5,Dynamic buffer overrun prevention,the idea, again:prevent
5、 writes outside the intended array as is done in Java harder in C: must add “size” to each array done in CCured, a Berkeley project,Ras Bodik CS 164 Lecture 24,6,A different idea,perhaps less safe, but easier to implement: goal: detect that return address was overwritten.instrument the program so th
6、at 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 program,Ras Bodik CS 164 Lecture 24,7,Commercially interes
7、ting,Similar idea behind the product by key problem: reducing overhead of instrumentation whats instrumentation, anyway? adding statements to an existing program in our case, to x86 executables Determina uses binary translation,Ras Bodik CS 164 Lecture 24,8,What is Binary Translation?,Translating a
8、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),Ras Bodik CS 164 Lecture 24,9,When does the translation happen?,Static (off-line):
9、 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 behaviorNote: Pros(dynamic) =
10、 Cons(static),Ras Bodik CS 164 Lecture 24,10,Why? Translation Allows Program Modification,Program,Compiler,Runtime System,Static,Dynamic,Load time optimizers Shared library mechanism,DebuggersInterpretersJust-In-Time CompilersDynamic OptimizersProfilersDynamic CheckersinstrumentersEtc.,Ras Bodik CS
11、164 Lecture 24,11,Applications, 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
12、 known after linking) dynamic checkers finding memory access bugs (e.g., Rational Purify),Ras Bodik CS 164 Lecture 24,12,Dynamic Program Modifiers,Running Program,Dynamic Program Modifier: Observe/Manipulate Every Instruction in the Running Program,Hardware Platform,Ras Bodik CS 164 Lecture 24,13,In
13、 more detail,common setup,CPU,OS,DLL,application,CodeMorph,OS,DLL,application,CPU=VLIW,CodeMorph (Transmeta),Dynamo-RIO (HP, MIT),CPU=x86,DLL,application,Dynamo,OS,Ras Bodik CS 164 Lecture 24,14,Dynamic Program Modifiers,Requirements: Ability to intercept execution at arbitrary points Observe execut
14、ing 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),Ras Bodik CS
15、164 Lecture 24,15,HP Dynamo-RIO,Building a dynamic program modifier Trick I: adding a code cache Trick II: linking Trick III: efficient indirect branch handling Trick IV: picking traces Dynamo-RIO performance Run-time trace optimizations,Ras Bodik CS 164 Lecture 24,16,next VPC,Instruction Interprete
16、r,System I: Basic Interpreter,decode,fetch next instruction,execute,exception handling,update VPC,Intercept executionObserve & modify executing instructionsTransparency Efficiency? - up to several 100 X slowdown,Ras Bodik CS 164 Lecture 24,17,context switch,BASIC BLOCK CACHE,non-control-flow instruc
17、tions,Trick I: Adding a Code Cache,next VPC,fetch block at VPC,lookup VPC,emit block,exception handling,execute block,Ras Bodik CS 164 Lecture 24,18,add %eax, %ecx cmp $4, %eax jle $0x40106f,add %eax, %ecx cmp $4, %eax jle jmp mov %eax, eax-slot # spill eax mov &dstub1, %eax # store ptr to stub tabl
18、e jmp context_switch mov %eax, eax-slot # spill eax mov &dstub2, %eax # store ptr to stub table jmp context_switch,frag7:stub1:stub2:,Example Basic Block Fragment,Ras Bodik CS 164 Lecture 24,19,context switch,BASIC BLOCK CACHE,non-control-flow instructions,Runtime System with Code Cache,next VPC,bas
19、ic block builder,Improves performance:slowdown reduced from 100x to 17-26xremaining bottleneck: frequent (costly) context switches,Ras Bodik CS 164 Lecture 24,20,add %eax, %ecx cmp $4, %eax jle $0x40106f,add %eax, %ecx cmp $4, %eax jle jmp mov %eax, eax-slot mov &dstub1, %eax jmp context_switch mov
20、%eax, eax-slot mov &dstub2, %eax jmp context_switch,frag7:stub1:stub2:,Linking a Basic Block Fragment,Ras Bodik CS 164 Lecture 24,21,context switch,BASIC BLOCK CACHE,non-control-flow instructions,Trick II: Linking,next VPC,fetch block at VPC,lookup VPC,emit block,exception handling,execute until cac
21、he miss,link block,Ras Bodik CS 164 Lecture 24,22,Performance Effect of Basic Block Cache with direct branch linking,Performance Problem: mispredicted indirect branches,Ras Bodik CS 164 Lecture 24,23,ret ,mov %edx, edx_slot # save apps edx pop %edx # load actual targetcmp %edx, $0x77f44708 # compare
22、 to# preferred target jne mov edx_slot, %edx # restore apps edx,Conditionally “inline” a preferred indirect branch target as the continuation of the trace,Indirect Branch Handling,Indirect Branch Linking,H,I,K,L,J,original target F original target H,Shared Indirect Branch Target (IBT) Table,linked t
23、argets,if equal goto lookup IBT table if (! tag-match) goto jump to tag-value,Ras Bodik CS 164 Lecture 24,25,basic block builder,context switch,indirect branch lookup,BASIC BLOCK CACHE,non-control-flow instructions,next VPC,miss,miss,Trick III: Efficient Indirect Branch Handling,Ras Bodik CS 164 Lec
24、ture 24,26,Performance Effect of indirect branch linking,Performance Problem: poor code layout in code cache,Ras Bodik CS 164 Lecture 24,27,Trick IV: Picking Traces,Block Cache has poor execution efficiency: Increased branching, poor locality Pick traces to: reduce branching & improve layout and loc
25、ality New optimization opportunities across block boundaries,A,B,D,G,E,C,F,H,I,J,K,L,A,B,E,F,H,D,G,K,J,Block Cache,Trace Cache,Ras Bodik CS 164 Lecture 24,28,basic block builder,trace selector,START,dispatch,context switch,indirect branch lookup,BASIC BLOCK CACHE,TRACE CACHE,non-control-flow instruc
26、tions,non-control-flow instructions,Picking Traces,Ras Bodik CS 164 Lecture 24,29,Picking hot traces,The goal: path profiling find frequently executed control-flow paths Connect basic blocks along these paths into contiguous sequences, called traces.The problem: find a good trade-off between profili
27、ng overhead (counting execution events), and accuracy of the profile.,Ras Bodik CS 164 Lecture 24,30,Alternative 1: Edge profiling,The algorithm: Edge profiling: measure frequencies of all control-flow edges, then after a while Trace selection: select hot traces by following highest-frequency branch
28、 outcome.Disadvantages: Inaccurate: may select infeasible paths (due to branch correlation) Overhead: must profile all control-flow edges,Ras Bodik CS 164 Lecture 24,31,Alternative 2: Bit-tracing path profiling,The algorithm: collect path signatures and their frequencies path signature = .history ex
29、ample: .0101101 must include addresses of indirect branches Advantages: accuracy Disadvantages: overhead: need to monitor every branch overhead: counter storage (one counter per path!),Ras Bodik CS 164 Lecture 24,32,Alternative 3: Next Executing Tail (NET),This is the algorithm of Dynamo: profiling:
30、 count only frequencies of start-of-trace points (which are targets of original backedges)trace selection: when a start-of-trace point becomes sufficiently hot, select the sequence of basic blocks executed next. may select a rare (cold) path, but statistically selects a hot path!,Ras Bodik CS 164 Le
31、cture 24,33,NET (continued),A,B,D,G,E,C,F,H,I,J,K,L,Advantages of NET: very light-weight #instrumentation points = #targets of backward branches#counters = #targets of backward branchesstatistically likely to pick the hottest pathpick only feasible paths easy to implement,Ras Bodik CS 164 Lecture 24
32、,34,Spec2000 Performance on Windows (w/o trace optimizations),Ras Bodik CS 164 Lecture 24,35,Spec2000 Performance on Linux (w/o trace optimizations),Ras Bodik CS 164 Lecture 24,36,Performance on Desktop Applications,Ras Bodik CS 164 Lecture 24,37,Performance Breakdown,Ras Bodik CS 164 Lecture 24,38,
33、Trace optimizations,Now that we built the traces, lets optimize them But whats left to optimize in a statically optimized code? Limitations of static compiler optimization: cost of call-specific interprocedural optimization cost of path-specific optimization in presence of complex control flow diffi
34、culty of predicting indirect branch targets lack of access to shared libraries sub-optimal register allocation decisions register allocation for individual array elements or pointers,Ras Bodik CS 164 Lecture 24,39,Maintaining Control (in the real world),Capture all code: execution only takes place out of the code cache Challenging for abnormal control flow System must intercept all abnormal control flow events: Exceptions Call backs in Windows Asynchronous procedure calls Setjmp/longjmp Set thread context,
