Trace Execution Software Watermarks Based On Threshold Scheme And Branch Structure

As the spread of digital information becomes more and more convenient, software piracy gets rampant increasingly. According to the statistics in 2005, the global loss caused by software piracy reached up to 34 billion dollars, which is 1.6 billion dollars higher than that in 2004, and the global rate of pirated software on personal computers was 35%. Software industry is being challenged and software protection is drawing our attention gradually. Now, there are mainly two kinds of techniques for software protection: cipher and watermarking. Software watermarking is what this paper concentrates on.Software watermarking secretly embeds copyright notice or customer identification into a program without affecting its performance adversely. As a new research field, it has many theoretical and technological problems to solve.Now there are several possible attacks on software watermarks: subtractive attacks which find the location of the watermark and crop it out of the program, distortive attacks which transform the watermarked program and render the watermark unrecognizable, additive attacks which add new marks to an already watermarked application and make it impossible to determine which watermark is the original one. Furthermore, for software fingerprints which mark customers' identification, there exist collusive attacks which compare different fingerprinted programs and determine the locations of the marks.In terms of embedding and extracting method, software watermarks come in two flavors: static and dynamic. Static software watermarks are easy to embed and extract, but are susceptible to simple distortive attacks and can't be used in situations which demand high robustness. Oppositely, dynamic software watermarks have the advantage of being resilient to dewatermarking attacks; therefore, it becomes the focus of the field.After analyzing the advantages and disadvantages of all kinds of software watermarks, based on the existing dewatermarking attacks, this paper describes a new approach for execution trace watermarks. It consists of five phases:1. Dividing phase: According to Shamir threshold scheme, the watermark is divided into a several values;The watermark is decomposed into n values based on Shamir threshold scheme. In the identifying phase afterwards, k or more than k of the n values, combined with the stored parameters, can retrieve the original watermark (k≤n).2. Encrypting phase: The n values are encrypted with block cipher, the resulting values, combined with a cipher table, form the watermark shares;With DES block cipher, we encrypt the n values from the dividing phase. For each new value, take out the corresponding cipher from the cipher table; attach the cipher after the new value, then we get a watermark share. Obviously, watermark shares are binary strings.3. Tracing phase: Input a special sequence and, via tracing the program, decide the execution order of its basic blocks and the values of its variables;This phase is an important phase of the whole scheme. The results of the tracing results under the special input sequence not only help generate watermark code and find appropriate insertion positions in the embedding phase, but provide the only way to identify the watermark in the last phase.4. Embedding phase: Watermark shares are embedded into the program dynamically by modifying the behavior of the program under the special input sequence;Based on the trace results, choose appropriate positions in appropriate methods and insert condition statements. For each embedded condition statement, the branch which it selects on its first execution determines the watermark it will generate in the future. When executing a condition statement, if the branch it selects is similar to that of last execution, a 0 is encoded; otherwise, a 1 is encoded.5. Identifying phase: Input the special sequence, trace the program again and extract the watermark.Trace the program, based on the information stored by the software owner; retrieve the original watermark in the order contrary to the watermark embedding.In our scheme, the bi-Grams (i_l,M_l)(l =1,2,...,n) from the embeddingphase should be securely stored. Here, i_l is the independent variables selected in the dividing phase, M_l is the methods chosen to embed watermark shares, and n is the number of watermark shares. Except(i_l,M_l)(l= 1,2,...,n), the software owner should store several other parameters: the threshold value k, the size q of the finite field, the key in the DES encryption and the cipher table used in the encrypting phase. The information will be needed in the identifying phase to retrieve the original watermark and prove ownership.The main characteristics of our approach are as follows:1. It brings in Shamir threshold scheme and divides watermark into n values. k or more than k of the n values can retrieve the original watermark (k≤n). By doing that, we can retrieve the original watermark based on partial information, which increases resilience.2. It doesn't embed the values divided from the dividing phase into the program directly, but encrypts them with block cipher. Shamir threshold is based on a finite field GF(q), which, to some extent, doesn't meet randomicity. However, Block cipher can solve the problem effectively. The new values after being encrypted by DES are randomly in the range 0～2⁶⁴ .3. Watermark shares are embedded into the dynamic behavior of condition statements. On one hand, branch structure is a necessary component of a program and condition statements can be seen everywhere, which increases stealth; on the other, the resulting binary string won't change if the branches are reordered, or if instructions other than condition statements are inserted or deleted, which resists various kinds of attacks.4. Code obfuscating technique is brought in while embedding, which increases stealth further. It breaks the program's original structure without affecting its function and performance, which, on one hand, renders watermark recognition difficult, on the other, combines the inserted code with the original program well.5. To simplify watermark extracting, cipher table is used in the encrypting phase.We realized the watermarking system on an actual platform. This paper described the main steps and their details. We chose a program of appropriate size and embedded a watermark into it with the new system. At last, we performed some attacking experiments using the existing attacking tools and analyzed the results.The experimental results show: our watermark is robust and stealthy, and is easy to extract. Also, with the increase in redundancy, its robustness improves obviously. When redundancy reaches a certain grade, its robustness comes to perfection.At the end of this paper, we summarized our work and expected to the future.