{'fraction_non_alphanumeric': 0.03479036574487065, 'fraction_numerical': 0.0, 'mean_word_length': 5.198895027624309, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Efficient Graph Codec System for Software Watermarking

In this paper we propose an efficient and easily implemented codec system for encoding watermark numbers as reducible permutation flow-graphs. More precisely, in light of our recent encoding algorithms which encode a watermark value w as a self-inverting permutation π*, we present an efficient algorithm which encodes a 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 permutation π* 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 codec system resilient to attacks.