Two New Algorithms for Software Watermarking by Register Allocation and their Empirical Evaluation

QP and QPS algorithms embed a message into a program by adding extra edges to an interference graph that represents dependency among the variables in the program. QP algorithm has a drawback that the embedded watermarks are not always extractable from the watermarked programs. Though QPS algorithm can avoid extraction failure by introducing extra constraints on edge addition, the lengths of the embeddable messages are extremely shortened. In this paper we propose CC (color change) and CP (color permutation) algorithms. The proposing algorithms provide more capacity for embeddable information than the fore-mentioned two algorithms while they also offer assurance of extraction of embedded messages. CC and CP algorithms only change the colors of nodes in an interference graph without changing its structure. CC algorithm is effective when the number of the nodes in the interference graph is large enough where as CP algorithm is effective when the number of the colors needed for interference graph coloring is large enough.