568 DynamicWatermarking j oin() , which forces the main thread to block until the child threads tl and t2 have completed executing. Notice that this new program has four possible combinations in which threads t 1 and t2 can execute the functions b10CkA and b10CkB. First, either thread tl or t2 will win the contention for mutexl, and the winning thread executes the function b10ckA. second, once mutexl has been released, bOth threads will contend for mutex2' and the winning thread gets t0 execute b10ckB. SO you get the following four possible executlon orders : tl: tl: 1 b10ckA b10ckB tl: t2 : 2 b10ckA b10ckB t2 : t 1 : 3 b10ckA b10ckB t2 : t2 : 4 b10ckA b10ckB This is the way in which monitors are usually used, but it turns out that this isn't particularly useful t0 us. Now have a 100k at the light gray code in Listing 9.1 う 67 (d), where we've switched the order ⅲ which you lock and release the monitors. This code is almost identical t0 (b) and is ⅲ fact semantically equivalent—they b0th execute blockA and bIOCkB sequentially. NOW, however, whichever thread wins the first contentlon and then locks on mutexl is the 0 〃 thread that tries tO lock mutex2. The losing thread is still waiting on mutex 1 , SO the winmng thread is guaranteed tO 从 , ln again ! This means that whichever thread executes b10CkA also executes b10CkB. Since there are only two threads, there are now only two possible paths: t 1 : tl: 1 b10ckA b10ckB t2: t2 : 2 b10ckA b10ckB The two snippets are very similar, differing only in the order 0f lock operations. If you had a snippet 0f code (c) that caused different threads t0 execute different blocks, you would be able to distinguish the behavior of (b) from (d) at runtime solely by watching their execution. You could use this distinction ⅲ behavior tO dynamically decode a bit of the watermark. Of course, you would still have the problem that the snippets are 立 4 〃 / different, but later you'll will see how t0 overcome this problem. ProbIem 9.7 write the missrng code snippet in Listing 9. し、 567 (c) that uses only lock and unlock calls tO guarantee tWO different threads will execute b10CkA and

2 Dynamic Analysis void dbg-setSWBreakpoint(uint32 addr) { swBPAddr = addr ; traplnstr = origlnstr = dbg-readText (swBPAddr) ; ((char*) &traplnstr) [ ① ] @xCC ; dbg-writeText(swBPAddr , traplnstr) ; 151 Our debugger only supports setting one software breakpoint at a time, but the generalization t0 multiple breakpoints is straightforward. When the breakpoint is hit, you restore the instructlon tO the original, single step over it (remembering tO first decrement the instruction pointer! ) , and then rewrite the trap instruction SO it's ready for the next tlme execution hits the breakpoint address: int dbg-hand1eSWBreakpoint ( ) { struct user—regs—struct regs ; dbg-getRegs(&regs) ; dbg-writeText (swBPAddr , regs ・ e1P- dbg-setRegs(&regs) ; dbg-step(l) ; dbg-writeText (swBPAddr , origlnstr) ; traplnstr) ; The only thing that's le 丘 to do is to figure out ル the debugee yielded control. lt could be because it's done with a single-step operation, because it hit a hardware breakpoint, or because it hit a software breakpoint. The X86 has a debug status register (D6) that helps with this classification: enum event {swBPhit , hwBPhit , taskSwitch , singlestep , dbgReg , none} ; int dbg-getEvent() { uint32 dr6 = dbg-getDbgReg(6) ;

126 Program Analysis reachable at runtime. Conceptually, the nodes of a call graph consist of the control flow graph for the corresponding function, although in practice the call graph and the control flOW graphs are usually separate entlties. ln general, the call graph is a 4 〃 / - g 戸ん since one caller function can invoke the same callee multiple times from multiple call sites. Here's a simple program and its corresponding call gr 叩 h: void g(){ void 王 ( ) { void h() ; void h() { void k() { } void (*P) ( ) int main() { ma1n Actually, this graph is wrong! Looking at it, you would draw the conclusion that function k would never be called, but as you see from the source code, it な called albeit indirectly through a pointer. This tells you that building a call graph is easy as long as there are no function pointers involved. ln this simple case, it would be enough tO reason that "only one function has its address taken (k), SO the only value p can take is &k, SO main must call k. ln object-oriented languages, you get similar problems S1nce every method ⅲ - vocatmon is through a pointer. Fortunately, simple type analysis can sometmes help

58 Obfuscation Theory number Of variables used, but it is trivial to compute these properties given the source code Of the program. As Listing 5.5 第 7 illustrates, there is a fundamental difference between source-code access and oracle access. ln Listing 5. う、 7 (a) and (b), you have access to the algorithm being executed (and may recognize the Collatz problem). You also are able to tell what the size of the input set is and you are in a position tO bOth modify and run the program. The source a compressed summary of all l/O relations of the function it computes that is presented in a forr that can be used and analyzed by other programs. ln Listing 5. う 7 (c) , running a compiled program exemplifies accessing an oracle. You cannot tell from the interaction what all the inputs accepted by the program are, and the only I/O relations you learn are the ones that result from your execution. What is more, you are only able to execute finitely many such querles and thus are not in a position to determine all the properties of the program. Let's come up with some definitions of what is computable given source code or oracle-only access tO a program: Definition 5.6 (Source-code computable probability). Given a program P' and a source-code analyzer ス for some property of the program, let the notation be the probability that ス is able to compute that property of P'. Definition 5.7 (oracle access computable probability). Given a program P' with running time time( (') and an oracle access analyzer R for some property of the program, let the notation 怦い切 ( 1 represent the probability that R is able to compute that P' has that property. You are now able to state what properties of a blackbox you desire from an obfuscated program: Definition 5.8 (VirtuaI blackbox). Given an obfuscator 0 , an oracle access analyzer R, and a source-code analyzer 4 0 is a virtual blackbox if, for all properties of an obfuscated program P' = 〇 ( P), its source-code computable probability approximately the same as its oracle access computable probability,

113 Encrypted Execution 113.1 The XOM Architecture AS a representative example of this type of processor design, let's have a 100k at Stanford's XOM architecture. Although never implemented in silicon, the design IS complete enough tO have been simulated in software, and an operating system, X 〇 MO を was built to run on top of it. ln a multi-tasking operatlng system, several programs can execute at the same time, and each one may have different security reqmrements. ln fact, encrypted programs are slower than cleartext programs, a single program may want to switch between running ⅲ unencrypted mode for bread-and-butter code and encrypted mode for security-sensltive code. For this reason, the CPU supports び 0 戸 4 ″ e 〃な , which are logical contalners that protect one process' code and data from being observed or modified by another process. Keep in mind that in the scenario we're working in here, the operatlng system is untrusted, which means that it must run ln its own compartment. Even a severely subverted operating system won't be a Ⅱ 0 从℃ d tO examine or mampulate another protected process ! A CPU will only support a small number of compartments. Let's assume 4 , num_ bered O... ろ . Compartment 0 (the 〃ツ / compartment) is special—that's the insecure compartment where code runs unencrypted. There's a special ACTIVE register that holds the number of the currently executing compartment. Each compartment is associated with a session key, and a e zo 〃 - 走ツ / 4 みな maintains the mapping between compartment ID and the corresponding session key. Every cache line and every register is tagged with a compartment ID to mark which compartment code and data it belongs to. For efficiency reasons, code and data that's on-chip is kept in cleartext, but the tags ensure that only the owner of a datum can access it. Only on a cache flush do you have to encrypt data and write it out to RAM. To illustrate, let's consider a very concrete situation where t 嶬 programs ス and B are running.• 685 CPU session-key ね b 厄 session-key 0 1 2 3 addr cache line 0 1 2 3 ACT Ⅳ E 2 RAM register file contents tag 42 0 67 2 314 2 218 1 tag reg ワ」 -1 sym 2

.1 Static Analysis ⅲ disambiguating pointers. Have a 100k at th1S Java example: class A { void m() { } class B extends A { void m() { } class C extends B { void m() { } static void main() { B b if (. a = new B(); e1se a = new C(); 127 By looking at the static type ofb, you can tell that the call b. m() can only go t0 B's m or c's m. Thus, the call graph would have edges main → B :m, main → c : m. Similarly, if you 100k at the possible types 0f objects a could point t0, you would have t0 assume that a. m() could invoke any one 0f A : m, B :m, and C : m. However, if you 100k not JLISt at the call a. m() in isolation, but alSO consider the preceding if-statement, you can work out that a can't point tO an A Object and hence only B : m and C : m can be called! This requires ノ 4 / 4 ア 0 ル 4 〃 4 なゞな , which is going tO be our next topic. 5.1.2 Data 日 ow Analysis Data flO 从 " analysis glves you conservative information abOtIt hO 嶬 , variables are used in a program. lt's normally computed over a control flow graph; for interprocedural data flow analysis, it's computed over the control flow graph and the call graph.

562 Dyn amic Waterm arking 9.1.5.1 Avoiding Global Variables First, you ve seen that having t0 store the root of the graph ⅲ a global variable is a dead giveaway. Object-oriented programs' ⅲ particular, have few globals, and it's easy t0 scan the code for where they are being assigned tO. ' I 、 0 solutions come tO mind tO alleviate this problem : You c an litter the program with bogus global variables' or you can pass the root 0f the graph in formal methOd parameters. Here's an example where we've split the graph into two components. Normally, you'd have tO store a pointer tO node n2 ⅲ a global variable so that the light gray component will be accessible when it's merged with the dark gray component, but instead you can pass れ 2 ⅲ a formal parameter: public static VOid main ( string args[]) { れ u11 い ー Node れ 2 i f ( arg s [ ① ] . e qua 1 s ( ” 2 ” ) ) new N0de ( ) : れ 2 れ e 曾 Node(); Node れ 3 れ2 . digit れ 3 ; n3; れ 2 . s i れ 0 system . out . print1n("NO"); return ; System . out . println("YES"); if (found(args[@] ,args,i わ ) { for (int i=l; i く args . length; i + + ) { public static boolea れ found ( string value , String args[] , int i, iN0de れ { if (value . equals(args[i])) { i f ( ( i = = 4 ) & & ( n2 ! = nul 1 ) { 1. digitzæれ 1 を : ~ 20S i れ 0 : spi れ 0 れ 1 : 2 . spinev. igit Od をで 00t = れ e 評製 0 は 0 ( ) : 00 て . spines 第 1 第 : り return true; return false ・ ln practice, Of course, this is only possible if there's a direct runtlme path between the two graph-building sites. lf, on the other hand' the two components are built by tWO different threads, some Other means Of communication has tO be used. The SandMark [ 81 ] t001 uses a tracing run t0 determine suitable locations for embedding. During the trace, they also build an accurate call graph that allows them tO pick locations between which there are direct communication paths using only formal parameters. 9.1.5.2 Avoiding Unstealthy Node Classes One serious problem of WMCT is that it reqtllres a Java class ()r c-' or pascal record' and SO (n) tO represent the nodes 0f the graph. If there are only a few such data structures ⅲ the program' it will be an easy task for the attacker tO examine them tO see which ones are being used tO create suspicious linked structures.

4 Obfuscation Theory The first limitation of secure multi-party computation is speed. The gain in prwacy is attained with a large data overhead, and many of the protocols are ex- tremely slow. As a result, only very simple arithmetic and relational computations are practical. Second, many secure multi-party computation algorithms are only resilient tO passive attacks from malicious participants. This means, for example, that the protocol gives correct results only if the participants follow the protocol correctly. Some proposed algorithms require all participants to act honestly, while others work correctly if a maJority ofthe participants are honest. For example, ⅲ the Cheapskate Problem, any one of the friends is able to secretly influence the total that is computed. They are able tO derive information from the computed average while preventing other parucipants from doing so. As a result, they gain an unfair advan- tage. Other protocols defend against this possibility by allowing members to detect this type of fraud and stop the computation before their information has leaked. TO address these difficulties, many secure multi-party protocols are devised not tO perform arbitrary computations but rather highly specific ones using optlmized and efficient prrmitives. Nevertheless, secure multi-party computation can be used tO build secure protocols for auctions, votrng, private information retrieval, and Other types Of sensltive distributed computations, and in essence can a Ⅱ 0 从 , you tO build a slow, Turing complete, virtual machine. 5.6 DiscuSS10n ln this chapter you saw recent work on the theory and limits of obfuscation. 嶬 showed how fundamental problems ln computer science such as the halting prob- lem and the equivalence problem provide bounds on what kind of obfuscation is possible. You saw examples of provably secure obfuscation of point-functions used tO obfuscate access control and regular expressions and the Of an obfuscated database. We also discussed encryption algorithms and how to perform some operations on encrypted values using properties ofthe underlying encryption scheme. We were not able tO extend this scheme to securely hide the encryption or decryption itself. However, we showed you the whitebox approaches that currently are being used to try to securely obfuscate cryptographic algorithms like DES. AII of these examples were building up to the famous Theorem う .1 40 , which states that, under a very strict definition of obfuscation, obfuscation is impossible or, more precisely, programs exist that cannot be obfuscated. You have also seen how contrived the counterexample required to prove this lmpossibility result was. This does not mean the theorem is mconsequential or

Hardwar for Protecting Softwave he focus of this book is on software-based techniques for software protection. The advantage of software-only approaches is exactly that—they reqmre no special hardware tO run. This means that your protected program should run everywhere regardless of the c 叩 abilities your customer's hardware happens to have. The dis- advantage is that the code is always available to the attacker to examme and modify You can make it more difficult for him to do so, using the obfuscation and tam_ perproofing techniques from previous chapters, but the code な there ready to be attacked, and with the current state of the art, given an adversary with enough tenacity, defenses will eventually be breached. There have been many attempts at enhancing software protection by adding some sort of hardware support. The basic idea is to add a physical module that you assume will resist observation, tampering, and copying by a malicious user. The module a secret—such as a serial number, a piece Of COde, a cryptO_ graphic key—and the security of the program rests on keeping this secret. call the secret and the hardware it's wrapped ⅲ the root 0 / 〃〃立 , and the fact that you're allowed to trust that it won't be subverted is what sets hardware approaches apart from software-only approaches. Another way oflooking at the difference between software-based and hardware- based systems is that hardware-based protection often has an easily identifiable point of failure: There's a single strongly guarded root of trust that, if subverted, will compromlse your system, and everyone knows what that is. For example, ⅲ a 655

18 What ls 、 " 印あ、ゞ 0 ア尾 ? and the keys it uses. Dynamic attacks are also possible. For example, cryptographic algorithms have very specific execution patterns (think tight 100PS with lots of xors) and if they're not heavily obfuscated, they'd be easy to find using a dynamlc trace of the program. The keys themselves are a weak point. They're long strings of bits with a high degree of randomness, and as such, unusual beasts in most programs. So Axel could simply scan through the player code looking for, say, a う 12-bit long string that's more random than expected. Any code that uses this string is likely to be the decryptor. Once AxeI has found the location of the decryptor, he should have little problem finding where the decrypted media is generated and sent to the decoder. He can then simply add some code that writes the decrypted content to a 61C , and he's done. What welearn from this is that Doris needs to obfuscate her code SO that a simple pattern-match against it won't reveal the location of the decryptor or decoder, or the interfaces between them. She needs to tamperproof the code so that Axel can't lnsert new code, she needs to obfuscate not only the static code but also the dynamic behavior of the player, and she needs to obfuscate static data (the keys) ⅲ the code as well. And, still she has to assume that these defense measures are only temporary. Given enough time, Axel will bypass them all, and so she needs t0 have a plan for what t0 d0 when the system is broken. 1.4.13 Mobile Agent Computing ln our next scenario, Doris sends out a mobile shopping agent, which visits online stores ⅲ order t0 find the best deal on a particular CD. The agent traverses the 、 b and asks every store it encounters if they have the CD and how much it costs, records the best price so far, and eventually, returns to Doris with the site where she can get the best deal. Of course, if evil Axel runs a store there's no reason why he wouldn't cheat. First of all he can Just erase the information that the agent has collected SO far and substitute his own price: MobiIe Shopping Agent Best price: $ 12.95 Best vendor: CDAxel.com CDAxel.com This strategy will only help him if the agent returns directly to Doris when it's done with Axel's site. Much better (for AxeI) would be to manipulate the code so that regardless 0f which stores it visits after his, it will still record his (higher) price as the best one.