We examine the currently proposed static and dynamic graph watermarking schemes. Graph based watermarking schemes, like other watermarking schemes, can be divided into two groups: static and dynamic. Static graph watermarks are embedding in a control-flow graph within a program whereas dynamic graph watermarks are embedding in a graph data-structure built at run-time. We report previous findings, describe some recent additions and conclude by suggesting a direction for future work.

We survey the proposed software watermarking algorithms based on code re-ordering. This family of static watermarks use semantics-preserving transformations to encode a watermark in a permutation of the existing code. We describe the existing techniques and highlight the short-comings of these algorithms, namely that they are highly susceptible to semantics preserving transformations attacks.

Decompilation of Java bytecode is the act of transforming Java bytecode to Java source code. Although easier than that of decompilation of machine code, problems still arise in Java bytecode decompilation. These include type inference of local variables and exception-handling.

In this paper, we examine register allocation based software watermarking algorithms; these algorithms are constraint-based static software watermarking techniques. Figure 1 shows the evolution of this family of algorithms on which we report previous findings, describe some recent additions (including a correction to a published algorithm) and conclude by suggesting a direction for future work.

Evolution of Register Allocation Based Software Watermarking. Oval shapes represent new algorithms, while rectangular shapes represent evaluations.

Software watermarks can be broadly divided into two categories: static and dynamic. The former embeds the watermark in the data and/or code of the program, while the latter embeds the watermark in a data structure built at runtime.

A diagram showing a simple dynamic watermarking system.

Software watermarking involves embedding a unique identifier into software in order to prove ownership, in a similar way to that of multimedia watermarking. The graph below shows the evolution of software watermarking from the first patents to the latest academic research in the area. The nodes are titles of patents, research papers, or books. Edges of the graph indicate that the items are in some way related, for example one item might build on a previous item, use similar ideas, or discuss a previous idea.