Characterizing Watermark Numbers encoded as Reducible Permutation Graphs against Malicious Attacks
This work addresses software watermarking security for protecting intellectual property, but it is incremental as it builds on prior graph-theoretic methods.
The authors theoretically analyzed the W-RPG watermarking system to characterize watermark numbers as strong or weak based on their resilience to edge-modification attacks, computing the minimum number of bit modifications needed to produce valid but incorrect watermarks.
In the domain of software watermarking, we have proposed several graph theoretic watermarking codec systems for encoding watermark numbers $w$ as reducible permutation flow-graphs $F[π^*]$ through the use of self-inverting permutations $π^*$. Following up on our proposed methods, we theoretically study the oldest one, which we call W-RPG, in order to investigate and prove its resilience to edge-modification attacks on the flow-graphs $F[π^*]$. In particular, we characterize the integer $w\equivπ^*$ as strong or weak watermark through the structure of self-inverting permutations $π^*$ which encodes it. To this end, for any integer watermark $w \in R_n=[2^{n-1}, 2^n-1]$, where $n$ is the length of the binary representation $b(w)$ of $w$, we compute the minimum number of 01-modifications needed to be applied on $b(w)$ so that the resulting $b(w')$ represents the valid watermark number $w'$; note that a number $w'$ is called valid (or, true-incorrect watermark number) if $w'$ can be produced by the W-RPG codec system and, thus, it incorporates all the structural properties of $π^* \equiv w$.