Research And Implementation Of Dynamic Graph-Based Software Watermarking

The essential idea of dynamic graph software watermarking (DGW) algorithm is that the watermark is represented by the topology of some kind of data structure. The structure is created at runtime. Because of pointer aliasing effects it is difficult to carry out static analysis of the code that creates the data structure. Besides, it is easier to tamperproof this watermark than static watermarks or code watermarks. But DGW also has some defects. There are only two types of currently used watermark data structure:linked list and binary tree. Moreover, this algorithm has a low datarate when it strengthens the property of stealth.We implement some amelioration aim at the defects mentened above. The work of this paper includes the following two aspects.First, an important research about dynamic graph watermarking algorithm is to find out new dynamic graph data structures. The current commonly used data structures include Radix-k, PPCT and other data structures improved from them. This paper proposes digraph watermark encoding scheme through the study of digraph which is a kind of complex nonlinear data structure. In this encoding scheme we use the vertex-nodes and edge-nodes to carry out different types of coding.The vertex-nodes of a digraph form a circular linked list. Each vertex-node represents a weight value according to its location. In the same time we use the edge-nodes of a vertex-node to encode the coefficient of its weight value. According to the encoding scheme mentioned above, this article describes the implementation of the decoding algorithm. This article also carries out some analysis for the characteristics of the digraph encoding. In the worst case and average case, the datarate of digraph is slightly higher than the datarate of PPCT. In the best case the datarate of digraph exceeds the datarate of all current watermarking data structure. Therefore, this paper considers digraph structure is a very efficient structure in its best case.Second, this paper studies how to improve the performance of dynamic graph algorithm through changing the way of embedding watermark. Dynamic graph watermarking has a terrific stealth feature. But its datarate is very low. The datarate of static data watermarking is high. But the stealth feature of this algorithm is bad. This paper presents dynamic data graph watermarking (DDGW) which combines the ideas of static data watermarking and dynamic graph watermarking.The essential idea of DDGW is to create a type of graphic structure during the executable process of the program. The watermark number is stored in the data field of the nodes of the data structure. DDGW has a better stealth feature because of its dynamically allocation of space. And this algrithm has a higher datarate because it stores watermark numbers into the data field. After analysis, we find the datarate of dynamic data linked list structure is four times than that of Radix-k when the length of the data field of the node is 32 bits. The datarate of dynamic data PPCT also increases in similar extent. Therefore, this paper believes that DDGW algorithm is an important way of optimizing the performance of dynamic graph watermarking.Then, we implement and experiment with the algorithms we present on Sandmark. Sandmark is a tool for software watermarking, tamper-proofing, and code obfuscation of Java bytecode. We choose two programs of medium size as our samples and made them attacked on the SandMark. We also caculate the bytecodes of the samples with the statistical module. According to the results of the experiment we argue that the improved algorithms we proposed have great stealth and resilience feature.