Encoding watermark numbers as reducible permutation graphs using self-inverting permutations

DOI10.1016/J.DAM.2018.04.021MaRDI QIDQ1801057zbMATH OpenOpenAlexWikidataFDO

Authors Maria Chroni, Stavros D. Nikolopoulos, Leonidas Palios

Publication date 26 October 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.08482

zbMATH Keywords

evaluationstructural propertieswatermarkingreducible permutation graphspolynomial codec algorithmsself-inverting permutations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Flows in graphs (05C21)

Abstract: Several graph theoretic watermark methods have been proposed to encode numbers as graph structures in software watermarking environments. In this paper, we propose an efficient and easily implementable codec system for encoding watermark numbers as reducible permutation flow-graphs and, thus, we extend the class of graphs used in such a watermarking environment. More precisely, we present an algorithm for encoding a watermark number $w$ as a self-inverting permutation $p{i}^{\ast }$, an algorithm for encoding the self-inverting permutation $p{i}^{\ast }$ into a reducible permutation graph $F[p{i}^{\ast }]$ whose structure resembles the structure of real program graphs, as well as decoding algorithms which extract the permutation $p{i}^{\ast }$ from the reducible permutation graph $F[p{i}^{\ast }]$ and the number $w$ from $p{i}^{\ast }$. Both the encoding and the decoding process takes time and space linear in the length of the binary representation of $w$. The two main components of our proposed codec system, i.e., the self-inverting permutation $p{i}^{\ast }$ and the reducible permutation graph $F[p{i}^{\ast }]$, incorporate the binary representation of the watermark~$w$ in their structure and possess important structural properties, which make our system resilient to attacks; to this end, we experimentally evaluated our system under edge modification attacks on the graph $F[p{i}^{\ast }]$ and the results show that we can detect such attacks with high probability.

Recommendations

• scientific article; zbMATH DE number 2036026
• scientific article; zbMATH DE number 1958194
• scientific article; zbMATH DE number 1893217
• Full characterization of a class of graphs tailored for software watermarking
• Towards a provably resilient scheme for graph-based watermarking

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1919450 (Why is no real title available?)
• scientific article; zbMATH DE number 1893217 (Why is no real title available?)
• An abstract interpretation-based framework for software watermarking
• Characterizations of Reducible Flow Graphs
• Error-correcting graphs for software watermarking.
• Flow Graph Reducibility
• Maximal incompleteness as obfuscation potency
• Towards a provably resilient scheme for graph-based watermarking

Cited in

(3)

• On the resilience of canonical reducible permutation graphs
• Towards a provably resilient scheme for graph-based watermarking
• Full characterization of a class of graphs tailored for software watermarking

This page was built for publication: Encoding watermark numbers as reducible permutation graphs using self-inverting permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801057)