2011/10/06 by Maria Chroni, Chroni, Maria, Stavros D. Nikolopoulos +1
Computer Science · #Advanced Malware Detection Techniques #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #G.2.3 #Security and Verification in Computing #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1110.1194
arxiv created 2011/10/06 · openalex publication_date 2011/10/06 · arxiv updated 2011/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a software watermarking environment, several graph theoretic watermark methods use numbers as watermark values, where some of these methods encode the watermark numbers as graph structures. In this paper we extended the class of error correcting graphs by proposing an efficient and easily implemented codec system for encoding watermark numbers as reducible permutation flow-graphs. More precisely, we first present an efficient algorithm which encodes a watermark number w as self-inverting permutation π^* and, then, an algorithm which encodes the self-inverting permutation π^* as a reducible permutation flow-graph F[π^*] by exploiting domination relations on the elements of π^* and using an efficient DAG representation of π^*. The whole encoding process takes O(n) time and space, where n is the binary size of the number w or, equivalently, the number of elements of the permutation π^*. We also propose efficient decoding algorithms which extract the number w from the reducible permutation flow-graph F[π^*] within the same time and space complexity. The two main components of our proposed codec system, i.e., the self-inverting permutation π^* and the reducible permutation graph F[π^*], incorporate important structural properties which make our system resilient to attacks.