An Efficient Graph Codec System for Software Watermarking

In this paper we propose an efficient and easily implemented codec system for encoding watermark numbers as reducible permutation flow-graphs. More precisely, in light of our recent encoding algorithms which encode a watermark value w as a self-inverting permutation π*, we present an efficient algorithm which encodes a self-inverting permutation π* as a reducible permutation flow-graph F[π*] by exploiting domination relations on the elements of π* and using an efficient DAG representation of π*. The whole encoding process takes O(n) time and space, where n is the binary size of the number w or, equivalently, the number of elements of the permutation π*. We also propose efficient decoding algorithms which extract the permutation π* from the reducible permutation flow-graph F[π*] within the same time and space complexity. The two main components of our proposed codec system, i.e., the self-inverting permutation π* and the reducible permutation graph F[π*], incorporate important structural properties which make our codec system resilient to attacks.