We present a graph theoretic approach for watermarking software in a robust fashion. While watermarking typical software that are small in size (e.g. a few kilobytes) may be infeasible through this approach, it seems to be a viable scheme for large applications. Our approach works with program ow graphs and uses some abstractions, approximate k-partitions, and a random walk method to embed the watermark, with the goal of minimizing and controlling the additions to be made for embedding, while keeping the estimated e ort to undo the Watermark (WM) as high as possible. The watermarks are so embedded that small changes to the software or ow graphs are unlikely to disable detection by a probabilistic algorithm that has a secret. This is done by using some relatively robust graph properties, and with some error correcting codes. Under some natural assumptions about the added code to embed the WM, locating the WM by an attacker is related to some graph approximation problems. Since hardness of typical instances of graph approximation problems has little theoretical work done so far, we present some heuristics to generate such hard instances and in a limited case present some heuristic analysis of how hard it is separate the WM in an information theoretic model. We describe some related experimental work. Our watermarking scheme has connections to software tamper resistance as well. The problem of software watermarking, at a very basic level, is to insert some data W (the watermark) into a program P, so that in the resulting program P 0 it is not easy to detect and remove the watermark. To motivate our approach, we look at some toy examples of watermarking schemes and possible attacks against each. Scheme 1: Let W k be a small piece of W, and let cr(W k ) be an encryption of W k . Suppose we insert W k in the form of an instruction like move RegisterX, cr(W k ) just before another instruction that writes RegisterX. We could insert all pieces W k of W in this manner, distributed at di erent places in the program. However, a simple algorithm that does register ow analysis would discover that the instructions we inserted are dead code, and remove them altogether. Clearly, this scheme of inserting
Later, it was proposed to incorporate graph theoretical approaches in software watermarking REF .
A Graph Theoretic Approach to Software Watermarking
IN 4TH INTERNATIONAL INFORMATION HIDING WORKSHOP
Computer Science