Strong watermark numbers encoded as reducible permutation graphs against edge modification attacks

Abstract

Software watermarking is a defense technique used to prevent or discourage software piracy by embedding a signature in the code. In (Discrete Applied Mathematics 250 (2018) 145–164), a software watermarking system is presented which encodes an integer number w (i.e., a watermark) as a reducible permutation flow-graph  $\mathit{F}[{\mathit{\pi }}^{\ast }]$ embeddable in the code through the use of a self-inverting permutation  ${\mathit{\pi }}^{\ast }$ . In this work, we theoretically investigate this watermarking system and exploit structural properties of the self-inverting permutation ${\mathit{\pi }}^{\ast }$ encoding the watermark in order to prove its resilience to edge-modification attacks on the flow-graph $\mathit{F}[{\mathit{\pi }}^{\ast }]$ . Based on the minimum number of edge modifications needed to be applied on $\mathit{F}[{\mathit{\pi }}^{\ast }]$ so that a different watermark can be extracted from the resulting graph, we give a characterization of the watermarks as strong, intermediate or weak and provide good recommendations for the choices of watermark.