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

Article type: Research Article

Authors: Mpanti, Anna | Nikolopoulos, Stavros D.^{; *} | Palios, Leonidas

Affiliations: Department of Computer Science & Engineering, University of Ioannina, Ioannina, Greece

Correspondence: [*] Corresponding author. E-mail: [email protected].

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 F[π∗] embeddable in the code through the use of a self-inverting permutation π∗. In this work, we theoretically investigate this watermarking system and exploit structural properties of the self-inverting permutation π∗ encoding the watermark in order to prove its resilience to edge-modification attacks on the flow-graph F[π∗]. Based on the minimum number of edge modifications needed to be applied on F[π∗] 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.

Keywords: Watermarking, self-inverting permutation, reducible permutation graph, strong watermark, weak watermark

DOI: 10.3233/JCS-210048

Journal: Journal of Computer Security, vol. 31, no. 2, pp. 107-128, 2023