Strong watermark numbers encoded as reducible permutation graphs against edge modification attacks
Anna Mpanti, Stavros D. Nikolopoulos, Leonidas Palios · Journal of Computer Security · 2022
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 [Formula: see text] embeddable in the code through the use of a self-inverting permutation [Formula: see text]. In this work, we theoretically investigate this watermarking system and exploit structural properties of the self-inverting permutation [Formula: see text] encoding the watermark in order to prove its resilience to edge-modification attacks on the flow-graph [Formula: see text]. Based on the minimum number of edge modifications needed to be applied on [Formula: see text] 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.