Encoding Watermark Numbers as Reducible Permutation
Graphs using Self-inverting Permutations

arXiv:1712.08482v1 [] 21 Dec 2017

Maria Chroni Stavros D. Nikolopoulos Leonidas Palios
Department of Computer Science & Engineering
University of Ioannina
GR-45110 Ioannina, Greece
{mchroni,stavros,palios}@cs.uoi.gr

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 π ∗ , an algorithm for encoding the self-inverting permutation π ∗
into a reducible permutation graph F [π ∗ ] whose structure resembles the structure of real
program graphs, as well as decoding algorithms which extract the permutation π ∗ from the
reducible permutation graph F [π ∗ ] and the number w from π ∗ . 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
π ∗ and the reducible permutation graph F [π ∗ ], 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 [π ∗ ] and the results show that we can detect such attacks
with high probability.
Keywords: Watermarking, self-inverting permutations, reducible permutation graphs, polynomial codec algorithms, structural properties, evaluation.

1

Introduction

Software watermarking is a technique that is currently being studied to prevent or discourage
software piracy and copyright infringement. The idea is similar to digital (or media) watermarking
where a unique identifier is embedded in image, audio, or video data through the introduction
of errors not detectable by human perception [14]. The software watermarking problem can be
described as the problem of embedding a structure w into a program P producing a program Pw
such that w can be reliably located and extracted from Pw even after Pw has been subjected to
code transformations such as translation, optimization, and obfuscation [24]. More precisely, given
a program P , a watermark w, and a key k, the software watermarking problem can be formally
described by the following two functions: embed(P, w, k) → Pw and extract(Pw , k) → w.
Although digital watermarking has made considerable progress and become a popular technique
for copyright protection of multimedia information [14, 27, 29], research on software watermarking
has only recently received considerable attention. The patent by Davidson and Myhrvold [15]

1

presented the first published software watermarking algorithm. The preliminary concepts of software watermarking also appeared in the patents [21, 28]. Collberg et al. [10] presented detailed
definitions for software watermarking. Zhang et al. [31] and Zhu et al. [32] have given brief surveys
of software watermarking research (see also Collberg and Nagra [7] for an exposition of the main
results).
Graph-based Software Watermarking. Recently, several graph-based software watermarking
techniques have been proposed that encode identification data w as graph structures G[w] and
embed them into software ensuring functionality, usability and reversibility. We refer to the identification data w as the identifier and to the graph structure G[w] as the watermark graph; we may
regard identifiers as numbers (integers in this paper) and refer to them as watermark numbers or,
simply, watermarks.
A typical graph-based software watermarking system is mainly comprised of the following four
functions:
• encoder: it makes use of an encoding function encode which converts a watermark w into
a graph G[w], i.e., encode(w) → G[w];
• embedder: it mainly uses a function which takes as input the program P (either binary or
source code), the intended watermark graph G[w], and possible a secret key k, and returns
the modified program Pw containing the graph G[w], i.e., embed(P, G[w], k) → Pw ;
• extractor: it undertakes to retrieve the watermark graph G[w] from the watermarked
program Pw using an appropriate function, i.e., extract(Pw ) → Gw ;
• decoder: it consists of a decoding function decode which converts the watermark graph
G[w] into the watermark w, i.e., decode(G[w]) → w.
In this domain, we usually call the pair (encode, decode)G[w] codec system and refer to both
functions encode and decode as codec algorithms [8]. In a similar manner, we may use the terms
embex system and embex algorithms for the pair (embed, extract)G[w] and the corresponding embed
and extract functions, respectively.
(I) Codec systems. While designing a codec system (encode, decode)G that is appropriate for
use in a real software watermarking environment, we are mainly looking for a class of graphs
G, along with the corresponding functions encode and decode, having the following desirable
properties and characteristics:
◦ appropriate graph types: graphs in G should be directed having appropriate properties
(e.g., nodes with small outdegree) so that their structure resembles that of real program
graphs;
◦ high resilience: the function decode(G[w]) should be insensitive to small changes of G[·]
(e.g., insertions or deletions of a constant number of nodes or edges), that is, if G[w] ∈ G
and decode(G[w]) → w then decode(G′ [w]) → w with G′ [w] ≈ G[w];
◦ small size: the size |Pw | − |P | of the embedded watermark graph G[w] should be small;
◦ efficient codecs: both encode and decode functions should be polynomially computable.
In this paper, we focus on the codec part of a software watermark system and propose the
codec (encode, decode)F [π∗ ] which incorporates several of the above properties and characteristics making it appropriate for practical use.
(II) Embex systems. On the other hand, for the design of an efficient embex system
(embed, extract)G , we are usually looking for techniques which associate a program P to
a directed graph G[P ] representing the structure of P as sequences of instructions and methods which handle the graph G[P ] and the watermark graph G[w] in an appropriate way;
2

that is the reason we require the structure of G[w] produced by a codec system resembling
that of real program graphs. Such a graph G[P ] may be the control flow-graph (CFG) of P
which can be obtained by means of a static analysis [26]. In a straight-forward approach,
the embedder inserts appropriate code into P , thus producing the watermarked program Pw ,
so that the watermark graph G[w] shows up as an induced subgraph of G[Pw ]. In turn, the
extractor retrieves that subgraph G[w] of Pw and passes it to the codec system, where its
decoder converts the watermark graph G[w] into w. Note that, the embedding process must
preserve program semantics, that is, P and Pw must have the same behavior.
We should mention that a software watermarking system usually contains of another function
namely recognizer: it takes the program Pw , the watermark w and the key k as input and
returns how confident we are that the Pw contains w, i.e., recognize(Pw, w, k) → [0.0, 1.0] [7].
Techniques and Previous Results. The major software watermarking algorithms currently
available are based on a number of techniques, such as the register allocation, spread-spectrum,
opaque predicate, abstract interpretation, and dynamic path techniques (see [1, 6, 12, 13, 22, 25]).
In general, according to Collberg and Thomborson’s informal taxonomy [10], the software
watermarking techniques can be broadly divided into two main categories, namely, static and
dynamic: in a static technique the watermark w is stored inside the program P in a certain
format, either as data or code, and its extraction from the watermarked program Pw requires no
execution of Pw , whereas in a dynamic one w is stored in P during the execution stage, perhaps
only after a particular sequence of input has been used, and it might be retrieved by analyzing the
data structures built when Pw is running; see also [7, 15, 21, 30]. We should also point out that a
different software watermarking technique, namely, abstract watermarking, has also been proposed:
in an abstract framework the watermark w is built in memory, in an abstract data structure, only
when P is executed on a particular abstract domain and its extraction requires static analysis on
Pw using some abstract interpretation of the semantics of Pw [12, 16, 17].
We next report some of the pioneering results in the area of graph-based software watermarking.
Indeed, in 1996 Davidson and Myhrvold [15] proposed the first static algorithm which embeds the
watermark by reordering the basic blocks of a control flow-graph. Based on this idea, Venkatesan,
Vazirani, and Sinha [30] proposed the first graph-based software watermarking algorithm which
embeds the watermark by extending a method’s control flow-graph through the insertion of a
directed subgraph; it is a static algorithm and is called VVS or GTW. Collberg et al. [9] proposed
the first publicly available implementation (GTWsm ) of algorithm GTW; in GTWsm the watermark is
encoded as a reducible permutation graph (RPG) [8], which is a reducible control flow-graph with
maximum out-degree of two, mimicking real code. The first dynamic watermarking algorithm
(CT) was proposed by Collberg and Thomborson [10]; it embeds the watermark through a graph
structure which is built on a heap at runtime. Recently, authors of this paper have contributed in
this area by proposing several codec and embex systems [3–5, 23].
Attacks. A successful attack against the watermarked program Pw prevents the recognizer from
extracting the watermark while not seriously harming the performance or correctness of Pw . It
is generally assumed that the attacker has access to the algorithm used by the embedder and
recognizer. There are four main ways to attack a watermark w ≡ G[w] stored in Pw :
◦ additive attacks: encode a new watermark w′ and embed the corresponding watermark graph
G[w′ ] into software P , so that an ambiguity is caused and thus the original copyright owners
of the software cannot prove their ownership;
◦ subtractive attacks: remove the watermark G[w] of the watermarked software Pw without
affecting the functionality of the watermarked software;

3

◦ distortive attacks: modify the watermark graph G[w] to prevent it from being extracted by
the copyright owners and still keep the usability of the software (in this case the decoder
fails to return any output);
◦ recognition attacks: modify the watermark G[w] so that the recognizer gives a misleading
result, that is, the extractor retrieves the graph G[w′ ] and the decoder returns w′ 6= w.
Typical attacks against the watermark graph G[w] can mainly occur in the following three ways:
(i) edge-flip attacks, (ii) edge-addition/deletion attacks, and (iii) node-addition/deletion attacks.
Our Contribution. In this paper, we present an efficient and easily implementable codec system
for encoding integer numbers as reducible permutation graphs, whose structure resembles that of
real program graphs, through the use of self-inverting permutations (or SiP, for short).
More precisely, we first present an efficient algorithm which encodes an integer watermark
number w as a self-inverting permutation π ∗ . Our algorithm, which we call Encode W.to.SiP,
takes as input an integer w, computes its binary representation, constructs a bitonic permutation
on n∗ = 2n + 1 numbers, and finally produces a self-inverting permutation π ∗ of length n∗ in O(n∗ )
time and space. We also present the corresponding decoding algorithm Decode SiP.to.W, which
converts the permutation π ∗ into the integer w within the same time and space complexity.
Having designed an efficient method for encoding integers as self-inverting permutations, we
next describe an algorithm for encoding a self-inverting permutation π ∗ of length n∗ as a reducible
permutation graph or, equivalently, watermark flow-graph F [π ∗ ]. In particular, we propose the
algorithm Encode SiP.to.RPG which exploits domination relations on the elements of π ∗ and
properties of a DAG representation of π ∗ , and produces a reducible permutation flow-graph F [π ∗ ]
on n∗ + 2 nodes; the whole encoding process takes O(n∗ ) time and requires O(n∗ ) space. The
corresponding decoding algorithm Decode RPG.to.SiP extracts the self-inverting permutation π ∗
from the graph F [π ∗ ] by first converting it into a directed tree Td [π ∗ ] and then applying DFS-search
on Td [π ∗ ]. The decoding process takes time and space linear in the size of the flow-graph F [π ∗ ], that
is, the decoding algorithm takes O(n∗ ) time and space; recall that the length of the permutation π ∗
and the size of the flow-graph F [π ∗ ] are both O(n∗ ) = O(n), where n = ⌈log2 w⌉.
Our codec algorithms are very simple, use elementary operations on sequences and linked
structures, and have very low time and space complexity. Moreover, both the permutation π ∗ and
the flow-graph F [π ∗ ] incorporate the binary representation of the watermark w in their structure
and thus possess important structural properties; experimental evaluation results substantiate that
edge modifications attackes on the graph F [π ∗ ] can be detected with high probability.
Road Map. The paper is organized as follows: In Section 2 we establish the notation and related
terminology and present background results. In Section 3 we describe the main components of our
codec system and present the encoding and decoding algorithms for the two main phases of our
system, namely W-SiP and SiP-RPG. In Sections 4 and 5 we provide structural properties and
characterizations of the self-inverting permutation π ∗ and the reducible permutation graph F [π ∗ ],
while in Section 6 we experimentally show that these properties help prevent edge and/or node
modifications attacks. Finally, in Section 7 we conclude the paper and discuss possible future
extensions.

2

Theoretical Framework

In this section, we present background results and the main components, namely, the self-inverting
permutations (SiP) and the reducible permutation graphs (RPG), which are used in the design of
our codec system.

4

2.1

Preliminaries

We consider finite graphs with no multiple edges. For a graph G, we denote by V (G) and E(G)
the vertex set and edge set of G, respectively. The neighborhood N (x) of a vertex x of the graph G
is the set of all the vertices of G which are adjacent to x. The degree of a vertex x in the graph G,
denoted deg(x), is the number of edges incident on x; thus, deg(x) = |N (x)|. For a node x of a
directed graph G, the number of directed edges coming in x is called the indegree of x and the
number of directed edges leaving x is its outdegree.
Next, we introduce some definitions that are key to our algorithms for encoding numbers as
graphs. Let π be a permutation over the set Nn = {1, 2, . . . , n}. We think of permutation π as
a sequence (π1 , π2 , . . . , πn ), so, for example, the permutation π = (1, 4, 2, 7, 5, 3, 6) has π1 = 1,
π2 = 4, etc. By πi−1 we denote the position in the sequence of number i ∈ Nn ; in our example,
π4−1 = 2, π7−1 = 4, π3−1 = 6, etc [18]. The length of a permutation π is the number of elements
in π. The reverse of π, denoted π R , is the permutation π R = (πn , πn−1 , . . . , π1 ). The inverse
of π is the permutation τ = (τ1 , τ2 , . . . , τn ) with τπi = πτi = i. For example, the inverse of the
permutation π = (2, 5, 1, 4, 3) is the permutation τ = (3, 1, 5, 4, 2). Clearly, every permutation has
a unique inverse, and the inverse of the inverse is the original permutation.
A subsequence of a permutation π = (π1 , π2 , . . . , πn ) is a sequence σ = (πi1 , πi2 , . . . , πik ) such
that i1 < i2 < · · · < ik . If, in addition, πi1 < πi2 < · · · < πik , then we say that σ is an increasing
subsequence of π, while if πi1 > πi2 > · · · > πik we say that σ is a decreasing subsequence of π; the
length |σ| of a subsequence σ is the number of elements in σ.
The concatenation σ1 || σ2 || · · · || σk of k subsequences σ1 , σ2 , . . . , σk of a permutation π is a
sequence σ of length |σ1 | + |σ2 | + · · · + |σk | such that for 1 ≤ j ≤ k and 1 ≤ i ≤ |σj |, the
(|σ1 | + |σ2 | + · · · + |σj−1 | + i)th element of σ is equal to the ith element of σj where, by convention,
|σ0 | = 0. Additionally, we denote by π\σ the subsequence which results from π after having
ignored the elements of the subsequence σ; more generally, we denote by π\{σ1 , σ2 , . . . , σk } the
subsequence which results from π after having ignored the elements of the subsequences σ1 , σ2 ,
. . . , σk .
A cycle of a permutation π = (π1 , π2 , . . . , πn ) is an index sequence c = (i1 , i2 , . . . , ip ) with
πi1 = i2 , πi2 = i3 , · · · , πip = i1 . For example, the permutation π = (4, 7, 1, 6, 5, 3, 2) has three
cycles c1 = (1, 4, 6, 3), c2 = (2, 7), and c3 = (5) of lengths 4, 2, and 1, respectively. In general, a
permutation π contains ℓ cycles, where 1 ≤ ℓ ≤ n; for example, the identity permutation over the
set Nn contains n cycles of length 1. Throughout the paper, a cycle of length k is referred to as a
k-cycle.
A left-to-right maximum (left-to-right minimum, resp.) of π is an element πi , 1 ≤ i ≤ n,
such that πj < πi (πj > πi , resp.) for all j < i. The increasing (decreasing, resp.) subsequence
σ = (πi1 , πi2 , . . . , πik ) is a left-to-right maxima (minima, resp.) subsequence if it consists of all
the left-to-right maxima (minima, resp.) of π; clearly, πi1 = π1 . For example, the left-to-right
maxima subsequence of the permutation π = (5, 6, 2, 8, 1, 9, 7, 4, 3) is (5, 6, 8, 9), while the left-toright minima subsequence of π is (5, 2, 1).
The 1st increasing (decreasing, resp.) subsequence S1 of a permutation π is defined to be the
left-to-right maxima (minima, resp.) subsequence of π. The ith increasing (decreasing, resp.)
subsequence Si of π is defined to be the left-to-right maxima (minima, resp.) subsequence of π ′ ,
where π ′ results from π after having ignored the elements of the 1st, 2nd, . . . , (i − 1)st increasing
(decreasing, resp.) subsequences of π, i.e., π ′ = π\{S1 , S2 , . . . , Si−1 }. For example, the increasing
subsequences of the permutation π = (5, 6, 2, 8, 1, 9, 7, 4, 3) are S1 = (5, 6, 8, 9), S2 = (2, 7) since
π ′ = π\S1 = (2, 1, 7, 4, 3), S3 = (1, 4), and S4 = (3), while its decreasing subsequences are
S1 = (5, 2, 1), S2 = (6, 4, 3), S3 = (8, 7), and S4 = (9).
We say that an element i of a permutation π over the set Nn dominates the element j if i > j and
πi−1 < πj−1 . An element i directly dominates (or d-dominates, for short) the element j if i dominates
j and there exists no element k in π such that i dominates k and k dominates j; for example, in the

5

permutation π = (8, 3, 2, 7, 1, 9, 6, 5, 4), the element 7 dominates the elements 1, 6, 5, 4 and directly
dominates the elements 1, 6. Let d-dom(j) be the set of all the elements of a permutation π which
d-dominate the element j and dmax(j) be the element of the set d-dom(j) with maximum value; for
example, in π = (8, 3, 2, 7, 1, 9, 6, 5, 4), d-dom(6) = (7, 9) and dmax(6) = 9, and d-dom(1) = (2, 7)
and dmax(1) = 7. By definition, the element i of a permutation π such that i = dmax(j) is the
rightmost element on the left of j in π that d-dominates j.

2.2

Self-inverting Permutations (SiP)

We next define the main component of our codec system, namely, the self-inverting permutation
(SiP), and prove key properties for encoding numbers as reducible permutation graphs.
Definition 2.1 Let π = (π1 , π2 , . . . , πn ) be a permutation over the set Nn . A self-inverting permutation (or involution) is a permutation that is its own inverse: ππi = i.
The definition of the inverse of a permutation implies that a permutation is a self-inverting
permutation iff all its cycles are of length 1 or 2; hereafter, we shall denote a 2-cycle by (x, y) with
x > y and a 1-cycle by (x) or, equivalently, (x, x).
Definition 2.2 A sequence C = (c1 , c2 , . . . , ck ) of all the 2- and 1-cycles of a self-inverting permutation π is a decreasing cycle representation of π if c1 ≻ c2 ≻ · · · ≻ ck where ci = (ai , bi ) ≻
cj = (aj , bj ) (with ai ≥ bi and aj ≥ bj ) if bi > bj , 1 ≤ i, j ≤ k. The cycle ck containing the
smallest element among the elements of the cycles is the minimum element of the sequence C.

2.3

Reducible Permutation Graphs (RPG)

A directed graph G is strongly connected if for every ordered pair of vertices (x, y) of G there is a
directed path in G from x to y. A node y is an entry for a subgraph H of the graph G if there is
an edge (x, y) in G such that y ∈ H and x 6∈ H.
Definition 2.3 A flow-graph G is a directed graph with a source node s ∈ V (G) from which
all other nodes are reachable. A flow-graph is reducible if it does not have a strongly connected
subgraph with two (or more) entries.
We can equivalently define a reducible flow-graph G as a directed graph with a source node
s ∈ V (G) such that every node of G is reached from s and every directed path from s to a directed
cycle C reaches C at the same node.
There are at least two other equivalent definitions, as Theorem 2.1 shows. These definitions
use a few more graph-theoretic concepts. For some node x, the edge (x, x) is a cycle-edge. A depth
first search (DFS) traversal of a graph G partitions its edges into tree, forward, back, and cross
edges. The tree, forward, and cross edges of G form a dag known as a DFS dag.
Theorem 2.1 [19, 20] Let F be a flow-graph. The following three statements about F are equivalent:
(i) the graph F is reducible;
(ii) the graph F has a unique DFS dag;
(iii) the graph F can be transformed into a single node by repeated application of the transformations φ1 and φ2 , where φ1 removes a cycle-edge, and φ2 picks a non-initial node y that has
only one incoming edge (x, y) and glues nodes x and y.
It is well-known that a reducible flow-graph has at most one Hamiltonian path [8].

6

3

Our Codec System

For encoding a watermark number w, our codec system uses two main components: (i) the selfinverting permutation π ∗ and (ii) the reducible permutation graph F [π ∗ ]; see Figure 1. The same
figure also depicts the two main phases of our codec system process:
(I) Phase W–SiP: it uses two algorithms, one for encoding the watermark number w into a
self-inverting permutation π ∗ and the other for extracting w from π ∗ ;
(II) Phase SiP–RPG: this phase uses two algorithms as well, one for encoding the self-inverting
permutation π ∗ into a reducible permutation graph F [π ∗ ] and the other for extracting π ∗
from F [π ∗ ].
Our codec system encodes an integer w as a self-inverting permutation π ∗ using a construction
technique which captures into π ∗ important structural properties (see Section 4). As we shall
see in Section 6, these properties enable an attack-detection system to identify edge and/or node
modifications made by an attacker to π ∗ . Moreover, the encoding approach adopted in our system
enables it to encode any integer w as a self-inverting permutation π ∗ of length n∗ = 2n + 1, where
n = 2⌈log2 w⌉ + 1.
The reducible permutation graph F [π ∗ ] produced by our system’s algorithms consists of n∗ + 2
nodes, say, un∗ +1 , un∗ , . . . , ui , . . . , u0 , which include:
(A) A header node: it is a root node with outdegree 1 from which all other nodes of the
graph F [π ∗ ] are reachable; note that every control flow-graph has such a node. In F [π ∗ ] the
header node is denoted by s = un∗ +1 ;
(B) A footer node: it is a node with outdegree 0 that is reachable from all other nodes of the
graph F [π ∗ ]. Every control flow-graph has such a node representing the exit of the method.
In F [π ∗ ] the footer node is denoted by t = u0 ;
(C) The body: it consists of n∗ nodes un∗ , un∗ −1 , . . . , ui , . . . , u1 each with outdegree 2. In
particular, each node ui (1 ≤ i ≤ n∗ ) has exactly two outgoing pointers: one points to node
ui−1 and the other points to a node um with m > i; recall that un∗ +1 = s and u0 = t.
By construction, the reducible permutation graph F [π ∗ ] is of order (i.e., number of nodes) n∗ + 2
and size (i.e., number of edges) 2n∗ + 1. Thus, since n∗ = 2n + 1, both the order and size of
graph F [π ∗ ] are of O(n), where n = 2⌈log2 w⌉ + 1.
Recall that our contribution in this paper has to do with both the W–SiP and the SiP–RPG
phase. We design and analyze algorithms for encoding a watermark number w as a SiP π ∗ and
algorithms for encoding a SiP π ∗ as a reducible permutation flow-graph F [π ∗ ] along with the
corresponding decoding algorithms; we also show properties of our codec system that prevent edge
and/or node modification attacks.

3.1

Codec Algorithms for Phase W-SiP

In this section, we first introduce the notion of a Bitonic Permutation and then we present two
algorithms, namely Encode W.to.SiP and Decode SiP.to.W, for encoding an integer w into a selfinverting permutation π ∗ and for extracting it from π ∗ , respectively. Both algorithms run in O(n)
time, where n = log2 w is the length of the binary representation of the integer w [3].
Bitonic Permutations: A permutation π = (π1 , π2 , . . . , πn ) over the set Nn is called bitonic
if it either monotonically increases and then monotonically decreases, or monotonically decreases
7

The watermark n-bit integer number w
Phase W-SiP
W.to.SiP

SiP.to.W

∗
)
π ∗ = (π1∗, π2∗, . . . , π2n+1

Phase SiP-RPG
SiP.to.RPG

RPG.to.SiP

F [π ∗ ]

s

2n+1

2n

...

2n-1

3

2

1

t

Figure 1: The main data components used by the codec system W-RPG for encoding a watermark
number w: (i) the self-inverting permutation π ∗ and (ii) the reducible permutation graph F [π ∗ ].

and then monotonically increases. For example, the permutations π1 = (1, 4, 6, 7, 5, 3, 2) and
π2 = (6, 4, 3, 1, 2, 5, 7) are both bitonic. Trivially, an increasing or decreasing permutation is
considered bitonic.
Let π = (π1 , π2 , . . . , πi , πi+1 , . . . , πn ) be a bitonic permutation over the set Nn that first monotonically increases and then monotonically decreases and let πi be the leftmost element of π
such that πi > πi+1 ; note that πi is the maximum element of π. Then, we call the sequence
X = (π1 , π2 , . . . , πi−1 ) the increasing subsequence of π and the sequence Y = (πi , πi+1 , . . . , πn )
the decreasing subsequence of π. Note that although (π1 , π2 , . . . , πi ) is increasing, the increasing
subsequence of π is defined up to the element πi−1 .
Notations: If B1 = b1 b2 · · · bn and B2 = d1 d2 · · · dm are two binary numbers, then the number
B1 ||B2 is the binary number b1 b2 · · · bn d1 d2 · · · dm . The binary sequence of the number B =
b1 b2 · · · bn is the sequence B ∗ = (b1 , b2 , . . . , bn ) of length n.
3.1.1

Algorithm Encode W.to.SiP

We next present an algorithm for encoding an integer as a self-inverting permutation without
having to consult a list of all self-inverting permutations. Our algorithm takes as input an integer
w, computes its binary representation, and then produces a self-inverting permutation π ∗ in time
linear in the length of the binary representation of w. The proposed algorithm is the following:
Algorithm Encode W.to.SiP
1. Compute the binary representation B of w and let n be the length of B;
2. Construct the binary number B ′ = |00 {z
· · · 0} ||B||0 of length n∗ = 2n + 1, and then the binary
sequence B ∗ of B ′ ;

n

8

w: watermarking integer
B:

binary representation
b1 b2 · · · bn of the integer w

B:

binary number of the 2nd block of B ′
b1 b2 · · · bn = b′n+1 b′n+2 · · · b′n′ −1

B′:

binary number 0n || b1 b2 · · · bn || 0
on 2n + 1 bits

B′:

binary number of sequence B ∗
b′1 b′2 · · · b′n b′n+1 b′n+2 · · · b′n′ −1 b′′n′

B∗:

sequence of 1s and 0s of the
binary number B ′

B∗:

binary sequence with 1s (0s) at the
positions corresp. to X’s (Y ’s) elements

X:
Y:

sequence of indices of 0s in B ∗
sequence of indices of 1s in B ∗

X:
Y:

the increasing subsequence of π b
the decreasing subsequence of π b

πb:

bitonic permutation constructed
by X and Y R , i.e., X||Y R

πb:

bitonic permutation constructed from
the decreasing cycle representation of π ∗

C:

set of 2-cycles and 1-cycle
constructed from π b

C:

decreasing cycle representation of π ∗

π ∗: self-inverting permutation
Figure 2: The main data components used by Algorithms Encode W.to.SiP and Decode SiP.to.W.

3. Construct the sequence X = (x1 , x2 , . . . , xk ) of the 1s’ positions and the sequence Y =
(y1 , y2 , . . . , ym ) of the 0s’ positions in B ∗ from left to right, where k + m = n∗ ;
4. Construct the bitonic permutation π b = X||Y R = (x1 , x2 , . . . , xk , ym , ym−1 , . . . , y1 ) over the
set Nn∗ = N2n+1 ;
5. for i = 1, 2, . . . , n = ⌊n∗ /2⌋ do
{construct a 2-cycle with the i-th element of π b from left and the i-th element from right }
construct the 2-cycle ci = (πib , πnb ∗ −i+1 );
b
construct the 1-cycle ci = (πn+1
);
6. Initialize the permutation π ∗ to the identity permutation (1, 2, . . . , 2n + 1);
for each 2-cycle (πi , πj ) computed at Step 5, set ππ∗i = πj and ππ∗j = πi ;
7. Return the self-inverting permutation π ∗ ;
Example 3.1 Let w = 12 be the input watermark integer in the algorithm Encode W.to.SiP. We
first compute the binary representation B = 1100 of the number 12; then we construct the binary
number B ′ = 000011000 and the binary sequence B ∗ = (0, 0, 0, 0, 1, 1, 0, 0, 0) of B ′ ; we compute
the sequences X = (5, 6) and Y = (1, 2, 3, 4, 7, 8, 9), and then construct the bitonic permutation
π b = (5, 6, 9, 8, 7, 4, 3, 2, 1) on n∗ = 9 numbers; since n∗ = 9 is odd, we form four 2-cycles (5, 1),
(6, 2), (9, 3), (8, 4) and one 1-cycle (7), and then construct the self-inverting permutation π ∗ =
(5, 6, 9, 8, 1, 2, 7, 4, 3).
Time and Space Complexity. The encoding algorithm Encode W.to.SiP performs basic operations
on sequences of O(n) length, where n is the number of bits in the binary representation of w (see
Figure 2). Thus, the whole encoding process requires O(n) time and space, and the following
theorem holds:

9

Theorem 3.1 Let w be an integer and let b1 b2 · · · bn be the binary representation of w. The
algorithm Encode W.to.SiP encodes the number w in a self-inverting permutation π ∗ of length
2n + 1 in O(n) time and space.

3.1.2

Algorithm Decode SiP.to.W

Next, we present an algorithm for decoding a self-inverting permutation. More precisely, our
algorithm, which we call Decode SiP.to.W, takes as input a self-inverting permutation π ∗ produced
by Algorithm Encode W.to.SiP and returns its corresponding integer w. Its time complexity is
linear in the length of the permutation π ∗ . We next describe the proposed algorithm:
Algorithm Decode SiP.to.W
1. Compute the decreasing cycle representation C = (c1 , c2 , . . . , cn+1 ) of the self-inverting permutation π ∗ = (π1 , π2 , . . . , πn∗ ), where n∗ = 2n + 1;
2. Construct the bitonic permutation π b of length n∗ as follows:
let C = ((a1 , b1 ), (a2 , b2 ), . . . , (an+1 , bn+1 )), where ci = (ai , bi ) with ai > bi , 1 ≥ i ≥ n + 1,
and b1 > b2 > · · · > bn+1 ;
◦ compute Q = (an+1 , an , . . . , a2 , a1 , b1 , b2 , . . . , bn+1 );
◦ delete from Q the element ai which forms the 1-cycle (ai , bi ) of π ∗ and thus ai = bi ;
b
◦ set π b = (π1b , π2b , . . . , πn+1
) ← Q;
3. Construct the increasing subsequence X = (π1b , π2b , . . . , πkb ) of π b and then the decreasing
b
b
b
subsequence Y = (πk+1
, πk+2
, . . . , πnb ∗ ), where πk+1
is the top element of π b ;
4. Construct the binary sequence B ∗ = (b1 , b2 , . . . , bn∗ ) by setting 1 in positions π1b , π2b , . . . , πkb
b
b
and 0 in positions πk+1
, πk+2
, . . . , πnb ∗ ;
5. Compute B ′ = b′1 b′2 . . . , b′n , b′n+1 · · · b′n∗ −1 b′n∗ from B ∗ ;
6. Return the decimal value w of the binary number B = b′n+1 b′n+2 · · · b′n∗ −1 ;
The decoding algorithm Decode SiP.to.W is essentially the reverse of the corresponding encoding
algorithm Encode W.to.SiP.
Example 3.2 Let π ∗ = (5, 6, 9, 8, 1, 2, 7, 4, 3) be a self-inverting permutation produced by Algorithm Encode W.to.SiP. The decreasing cycle representation of π ∗ is the sequence C =

(7, 7), (8, 4), (9, 3), (6, 2), (5, 1) ; we take the cycles in C from right to left and construct the
permutation π b = (5, 6, 9, 8, 7, 4, 3, 2, 1); then, we compute the increasing subsequence X = (5, 6)
and the decreasing subsequence Y = (9, 8, 7, 4, 3, 2, 1) of π b ; we next construct the binary sequence
B ∗ = (0, 0, 0, 0, 1, 1, 0, 0, 0) of length 9 and finally the the sequence B ′ = 000011000 of the elements
of B ∗ ; the decimal value of the binary number 1100 is the integer w = 12.
Time and Space Complexity. It is easy to see that the decoding algorithm Decode SiP.to.W
performs the same basic operations on sequences of O(n) length as the encoding algorithm (see
Figure 2). Thus, we obtain the following result:
Theorem 3.2 Let w be an integer (whose binary representation has length n) and let π ∗ be the
self-inverting permutation of length n∗ = 2n+ 1 produced by Algorithm Encode W.to.SiP to encode
w. Algorithm Decode SiP.to.W correctly extracts w from π ∗ in O(n∗ ) = O(n) time and space.

10

π ∗ = (5, 6, 9, 8, 1, 2, 7, 4, 3)
D[π ∗ ]

Td [π ∗ ]

s

5

s

5
6

6

9

9
8

8
1

1
7

2

7

2
4

4

t

3

t

3

Figure 3: The DAG D[π ∗ ] of the self-inverting permutation π ∗ and the corresponding Dmax-tree Td [π ∗ ].

3.2

Codec Algorithms for Phase SiP-RPG

In this section, we concentrate on the system’s phase SiP–RPG and present an efficient algorithm
for encoding a self-inverting permutation π ∗ into a reducible permutation graph F [π ∗ ], along with
the corresponding decoding algorithm.
The proposed encoding algorithm, which we call Encode SiP.to.RPG, takes as input the selfinverting permutation π ∗ produced by the algorithm Encode W.to.SiP and constructs a reducible
permutation flow-graph F [π ∗ ] by using a DAG representation D[π ∗ ] of the permutation π ∗ ; in
fact, it uses a parent-relation of a tree obtained from the graph D[π ∗ ] defined below. The whole
encoding process takes O(n∗ ) time and requires O(n∗ ) space, where n∗ is the length of the input
self-inverting permutation π ∗ .
Next, we first describe the main ideas and the structures behind our encoding algorithm.
In particular, given a self-inverting permutation π ∗ we construct a directed acyclic graph and a
directed tree by taking advantage of the dmax values of the elements of π ∗ (recall that dmax(i)
with respect to the permutation π ∗ , where 1 ≤ i ≤ n∗ , is equal to the maximum value element
among the elements in π ∗ that d-dominate i; see Subsection 2.1).
DAG Representation D[π ∗ ]: We construct the directed acyclic graph D[π ∗ ] by exploiting the
d-domination relation of the elements of π ∗ as follows: (i) for every element i of π ∗ , we create a
corresponding vertex vi and we add it into the vertex set V (D[π ∗ ]) of D[π ∗ ]; (ii) for every pair
of vertices (vi , vj ) where vi , vj ∈ V (D[π ∗ ]), we add the directed edge (vi , vj ) in E(D[π ∗ ]) if the
element i d-dominates the element j in π ∗ ; (iii) we create two dummy vertices s = vn∗ +1 and
t = v0 and we add them both in V (D[π ∗ ]); then, we add in E(D[π ∗ ]) the directed edge (s, vi ) for
every vi with indegree equal to 0, and the edge (vj , t) for every vj with outdegree equal to 0.
Figure 3 depicts the graph D[π ∗ ] of the permutation π ∗ = (5, 6, 9, 8, 1, 2, 7, 4, 3). Note that, by
construction, i > j for every directed edge (vi , vj ) of D[π ∗ ] since the element i d-dominates the
element j in π ∗ .
Dmax-tree Td [π ∗ ]: We next construct the directed tree Td [π ∗ ], which we call Dmax-tree, by
exploiting the dmax values of the elements on the nodes of D[π ∗ ]. The Dmax-tree Td [π ∗ ] is simply
constructed as follows:
(i) construct the DAG D[π ∗ ];

11

(ii) delete the directed edge (vi , vj ) from D[π ∗ ] if i 6= dmax(j).
The Dmax-tree Td [π ∗ ] of the permutation π ∗ = (5, 6, 9, 8, 1, 2, 7, 4, 3) is shown in Figure 3. We point
out that the construction of the Dmax-tree Td [π ∗ ] can also be done directly from permutation π ∗
by computing the element dmax(i) for each element i ∈ π ∗ , 1 ≤ i ≤ n∗ ; note that s = vn∗ +1
dominates all the elements of π ∗ .
3.2.1

Algorithm Encode SiP.to.RPG

Given a self-inverting permutation π ∗ of length n∗ , our proposed encoding algorithm
Encode W.to.SiP works as follows: first, it computes the dmax value of each of the n∗ elements of
the self-inverting permutation π ∗ (Step 1), which it then uses to construct a directed graph F [π ∗ ]
on n∗ + 2 nodes (Steps 2 and 3). Next, we present the encoding algorithm in detail.
Algorithm Encode SiP.to.RPG
1. for each element i ∈ π ∗ , 1 ≤ i ≤ n∗ , do
◦ Compute P (i) = dmax(i);
2. Construct a directed graph F [π ∗ ] on n∗ + 2 vertices as follows:
◦ V (F [π ∗ ]) = {s = un∗ +1 , un∗ , . . . , u1 , u0 = t};
◦ add the forward edges (ui+1 , ui ) in E(F [π ∗ ]), for 0 ≤ i ≤ n∗ ;
3. for each vertex ui ∈ V (F [π ∗ ]), 1 ≤ i ≤ n∗ , do
◦ add the backward edge (ui , um ) in E(F [π ∗ ]), where m = P (i);
4. Return the graph F [π ∗ ];
Time and Space Complexity. The most time-consuming step of the algorithm is the computation
of the value dmax(i) for each element i of π ∗ (Step 1). On the other hand, the construction of the
reducible permutation flow-graph F [π ∗ ] on n∗ + 2 nodes requires only the forward edges (Step 2)
which can be trivially computed, and the backward edges (Step 3) which can be computed using
the values of dmax.
Returning to Step 1, since dmax(i) is the rightmost element on the left of the element i in the
permutation π ∗ that is greater than i, the values P (i) can be computed using the input permutation
as follows:
(i) insert the element s with value n∗ + 1 into an initially empty stack S;
(ii) for each element πi∗ , i = 1, 2, . . . , n∗ , do the following:
while the element at the top of S is less than πi∗
pop it from the stack S;
P (πi∗ ) = element at the top of S;
push πi∗ into the stack S;
For the correctness of this procedure, note that the contents of the stack S are in decreasing order
from bottom to top; in fact, at the completion of the processing of element πi∗ , S contains (from
∗
top to bottom) the left-to-right maxima of the reverse subpermutation (πi∗ , πi−1
, . . . , π1∗ , n∗ + 1).
∗
Additionally, it is important to observe that the value n + 1 at the bottom of the stack S is never
removed.
The time to process element πi∗ in step (ii) is O(1 + ti ) where ti is the number of elements
popped from the stack S while processing πi∗ . Since the number of pops from S does not exceed
the number of pushes in S and since each element of the input permutation π ∗ is inserted exactly
once in S, the whole computation of the function P () takes O(n∗ ) time and space, where n∗ is the
length of the permutation π ∗ . Thus, we obtain the following result.
12

π ∗ = (5, 6, 9, 8, 1, 2, 7, 4, 3)

↓↑

P (i) = dmax(i)
P (1) = 8

P (6) = s

P (2) = 8

P (7) = 8

P (3) = 4

P (8) = 9

P (4) = 7

P (9) = s

5

s

Td[π ∗]

6

9
8

2

1

P (5) = s

4

↓↑
FI [π ∗ ]

s

9

7

3
8

7

6

5

4

3

2

1

t

Figure 4: The main structures used or constructed by the algorithms Encode SiP.to.RPG and
Decode RPG.to.SiP, that is, the self-inverting permutation π ∗ , the function P (), the reducible graph
FI [π ∗ ] = F [π ∗ ], and the Dmax-tree Td [π ∗ ].

Theorem 3.3 The algorithm Encode SiP.to.RPG for encoding a self-inverting permutation π ∗ of
length n∗ as a reducible permutation flow-graph F [π ∗ ] requires O(n∗ ) time and space.

3.2.2

Algorithm Decode RPG.to.SiP

Having presented the encoding algorithm Encode SiP.to.RPG, we are interested in designing an
efficient and easily implementable algorithm for decoding the permutation π ∗ from the graph F [π ∗ ].
Thus, we next present such a decoding algorithm, we call it Decode RPG.to.SiP, which is easily
implementable: indeed, the only operations used by the algorithm are edge modifications on F [π ∗ ]
and DFS-search on trees.
The algorithm takes as input a reducible permutation flow-graph F [π ∗ ] on n∗ + 2 nodes constructed by Algorithm Encode SiP.to.RPG, and produces a permutation π ∗ of length n∗ ; it works
as follows:
Algorithm Decode RPG.to.SiP
1. Delete the forward edges (ui , ui−1 ) from the set E(F [π ∗ ]), 1 ≤ i ≤ n∗ + 1 = s, and the node
t = u0 from V (F [π ∗ ]) = {s = un∗ +1 , un∗ , . . . , u1 , u0 = t};
2. Flip all the remaining edges (backward edges) of the graph F [π ∗ ] yielding the Dmax-tree
Td [π ∗ ] with nodes s, u1 , u2 , . . . , un∗ ;
3. Perform DFS-search on the tree Td [π ∗ ] starting at node s by always proceeding to the
minimum-labeled child node and compute the DFS discovery time d[u] of each node u of
Td [π ∗ ];
4. Order the nodes u1 , u2 , . . . , un∗ of the tree Td [π ∗ ] by their DFS discovery time d[] and let
π = (u′1 , u′2 , . . . , u′n∗ ) be the resulting order;
5. Return π ∗ = π;
13

Time and Space Complexity. The size of the reducible permutation graph F [π ∗ ] constructed by
the algorithm Encode SiP.to.RPG is O(n∗ ), where n∗ is the length of the permutation π ∗ , and
thus the size of the resulting tree Td [π ∗ ] is also O(n∗ ). It is well known that the DFS-search on
the tree Td [π ∗ ] takes time linear in the size of Td [π ∗ ]. Thus, the decoding algorithm is executed in
O(n∗ ) time using O(n∗ ) space. Thus, the following theorem holds:
Theorem 3.4 Let F [π ∗ ] be a reducible permutation flow-graph of size O(n∗ ) produced by the algorithm Encode SiP.to.RPG. The algorithm Decode RPG.to.SiP decodes the flow-graph F [π ∗ ] in
O(n∗ ) time and space.

4

Structure and Properties of the SiP π ∗

In this section, we analyze the structure of a self-inverting permutation π ∗ produced by the algorithms Encode W.to.SiP and present properties which are important in their own right, at least
from a graph-theoretic point of view, and prove useful in shielding our watermark graph F [π ∗ ]
against attacks.

4.1

The Subsequences π1∗ and π2∗

Consider a self-inverting permutation π ∗ encoding an integer w in the range [2n−1 , 2n − 1], where
n is the length of the binary representation of w; we distinguish the following two cases:
All-One case: Suppose that w = 2n − 1, that is, all the bits in w’s binary representation are 1.
Then, according to Algorithm Encode W.to.SiP, B ′ = 0n 1n 0, π b = (n+ 1, n+ 2, . . . , 2n+ 1, n, n−
1, . . . , 2, 1), and π ∗ = (n + 1, n + 2, . . . , 2n, 1, 2, . . . , n, 2n + 1), that is, π ∗ is the concatenation
of the (increasing) subsequences π1∗ and π2∗ where
π1∗ = (n + 1, n + 2, . . . , 2n)

and

π2∗ = (1, 2, . . . , n, 2n + 1).

(1)

Zero-and-One case: Suppose that w 6= 2n − 1. Then, the concatenation of the binary representation of w with a trailing 0 consists of a1 1s, followed by b1 0s, followed by a2 1s, followed by b2
0s, and so on, followed by aℓ 1s, followed by bℓ 0s where ℓ ≥ 1, ai , bi > 0, and a1 < n.
Pj
Pj
For convenience, let Aj = t=1 at and Γj = t=1 (at + bt ) for 0 ≤ j ≤ ℓ; note that A0 = 0,
Γ0 = 0, Γℓ = 2n + 1, and Aℓ is equal to the number of 1sin the binary
representation of w.

Pj
Pℓ
Additionally, let Bj =
t=1 bt for 0 ≤ j ≤ ℓ, and B j =
t=1 bt − Bj , which imply that

B0 = B ℓ = 0, B j−1 = B j + bj , and Γℓ = Aℓ + Bℓ = Aℓ + B 0 .
Then, according to Algorithm Encode W.to.SiP, B ′ = 0 · · · 0||B||0 where B is the binary
representation of w, and π b = X || Y R where X is the sequence of the 1s’ positions in B ′ and Y R
is the reverse of the sequence of the 0s’ positions in B ′ , that is,
X

=
=

X
 1 || X2 || . . . || Xi || . . . || Xℓ
n + 1, . . . , n + a1 , n + Γ1 + 1, . . . , n + Γ1 + a2 , . . . , n + Γi−1 + 1, . . . , n + Γi−1 + ai ,
{z
} |
{z
}
|
{z
}
|
a1
a2
ai

. . . , n + Γℓ−1 + 1, . . . , n + Γℓ−1 + aℓ
{z
}
|
aℓ

and
YR

= YℓR || . . . || YiR || . . . || Y1R || Y0R
14

=



n + Γℓ , . . . , n + Γℓ − bℓ + 1, . . . , n + Γi , . . . , n + Γi − bi + 1, . . . ,
|
|
{z
}
{z
}
bℓ
b
i
n + Γ1 , . . . , n + Γ1 − b1 + 1, n, n − 1, . . . , 2, 1 .
{z
} |
{z
}
|
n

b1

(Note that Γi−1 + ai = Γi − bi .)
Next, because the total length of the concatenation of X1 , X2 , . . . , Xℓ , YℓR , . . . , Y1R is n + 1
whereas the length of Y0R is n, the cycles constructed in Step 5 of Algorithm Encode W.to.SiP are:
• 2-cycles: the 2-cycles in increasing order of their second elements from 1 to n are (note that
A0 = B ℓ = Γ0 = 0, Aℓ + B 0 − 1 = Γℓ − 1 = (n + 1) − 1 = n, and Γi−1 + ai = Γi − bi ):
(n + 1, A0 + 1), (n + 2, A0 + 2), . . ., (n + a1 , A1 ),
(n + Γ1 + 1, A1 + 1), (n + Γ1 + 2, A1 + 2), . . ., (n + Γ1 + a2 , A2 ),
···
(n + Γi−1 + 1, Ai−1 + 1), (n + Γi−1 + 2, Ai−1 + 2), . . ., (n + Γi−1 + ai , Ai ),
···
(n + Γℓ−1 + 1, Aℓ−1 + 1), (n + Γℓ−1 + 2, Aℓ−1 + 2), . . ., (n + Γℓ−1 + aℓ , Aℓ ),
(n + Γℓ , Aℓ + B ℓ + 1), (n + Γℓ − 1, Aℓ + B ℓ + 2), . . ., (n + Γℓ − bℓ + 1, Aℓ + B ℓ−1 ),
···
(n + Γi , Aℓ + B i + 1), (n + Γi − 1, Aℓ + B i + 2), . . ., (n + Γi − bi + 1, Aℓ + B i−1 ),
···
(n + Γ2 , Aℓ + B 2 + 1), (n + Γ2 − 1, Aℓ + B 2 + 2), . . ., (n + Γ2 − b2 + 1, Aℓ + B 1 ),
(n + Γ1 , Aℓ + B 1 + 1), (n + Γ1 − 1, Aℓ + B 1 + 2), . . ., (n + Γ1 − b1 + 2, Aℓ + B 0 − 1);
• 1-cycle: the 1-cycle involves the last element of Y1R , that is, it is (n+Γ1 −b1 +1) = (n+a1 +1).
Therefore, the self-inverting permutation π ∗ is the concatenation of π1∗ and π2∗ , where
π1∗ = X1 || X2 || . . . || Xℓ || YℓR || . . . || Y2R || ΨR
1

(2)

R
with ΨR
1 = (n + Γ1 , . . . , n + Γ1 − b1 + 2) (note that Ψ1 is empty if b1 = 1 otherwise it is equal to
Y1R without its last element n + Γ1 − b1 + 1 = n + a1 + 1) and

π2∗ =
1, 2, . . . , A1 , n + A1 + 1, n, n − 1, . . . , n − B1 + 2,
|
|
{z
}
{z
}
a1

b1 −1

A + 1, A1 + 2, . . . , A2 , n − B1 + 1, n − B1 , . . . , n − B2 + 2,
|1
{z
} |
{z
}
a2

b2

··· ,
Ai−1 + 1, Ai−1 + 2, . . . , Ai , n − Bi−1 + 1, n − Bi−1 , . . . , n − Bi + 2,
{z
} |
{z
}
|
ai

bi

··· ,

Aℓ−1 + 1, Aℓ−1 + 2, . . . , Aℓ , n − Bℓ−1 + 1, n − Bℓ−1 , . . . , n − Bℓ + 2
{z
} |
{z
}
|
aℓ

(3)

bℓ

(note that the last element of π2∗ is n − Bℓ + 2 = (Γℓ − 1) − Bℓ + 2 = (Aℓ + Bℓ − 1) − Bℓ + 2 = Aℓ + 1).
It is interesting to note that π1∗ is a permutation of the numbers n + 1, n + 2, . . . , 2n + 1 except for
n + a1 + 1; in turn, π2∗ is a permutation of the numbers 1, 2, . . . , n and n + a1 + 1. Additionally, π2∗
consists of the a1 numbers 1, 2, . . . , A1 followed by b1 numbers larger than Aℓ +1, followed by the a2
numbers A1 + 1, A1 + 2, . . . , A2 , followed by b2 numbers larger than Aℓ + 1, and so on, up to the aℓ
numbers Aℓ−1 + 1, Aℓ−1 + 2, . . . , Aℓ that are followed by the bℓ numbers Aℓ + bℓ , Aℓ + bℓ − 1, . . . , Aℓ
(note that n−Bℓ−1 +1 = (Γℓ −1)−Bℓ−1 +1 = (Aℓ +Bℓ −1)−Bℓ−1 +1 = Aℓ +(Bℓ −Bℓ−1 ) = Aℓ +bℓ ).
Example 4.1 Consider w = 220. The binary representation of w is 11011100, and hence n = 8.
From the concatenation of the binary representation of w with the additional trailing 0, we have
15

that ℓ = 2, a1 = 2, b1 = 1, a2 = 3, b2 = 3; in turn, A1 = a1 = 2, A2 = a1 + a2 = 5,
B1 = B 1 = b1 = 1, B2 = B 0 = b1 + b2 = 4, Γ1 = A1 + B1 = 3, and Γ2 = A2 + B2 = 9. Then,
π b = (0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0)
|
{z
} |
{z
}
n=8

n=8

and π1∗ = (9, 10, 12, 13, 14, 17, 16, 15) and π2∗ = (1, 2, 11, 3, 4, 5, 8, 7, 6); thus,
π ∗ = (9, 10, 12, 13, 14, 17, 16, 15, 1, 2, 11, 3, 4, 5, 8, 7, 6).

4.2

The 4-Chain Property

Based on the structure of a self-inverting permutation π ∗ produced by algorithm Encode W.to.SiP,
we next present four important properties of π ∗ which are incorporated into our codec watermark
graph F [π ∗ ] making it resilient against attacks.
• Odd-One property: The self-inverting permutation π ∗ produced by the encoding algorithm
Encode W.to.SiP has always odd length and contains exactly one cycle of length 1.
• Bitonic property: The self-inverting permutation π ∗ is constructed from the bitonic sequence π b = X||Y R , where X and Y are increasing subsequences (see Step 4 of our encoding
algorithm Encode W.to.SiP), and thus the bitonic property of π b is encapsulated in π1∗ .
Indeed, the first n elements of permutation π ∗ form the bitonic sequence π1∗ (π1∗ first monotonically increases and then monotonically decreases or simply monotonically increases). We
say that the SiP π ∗ has the Bitonic property if π1∗ is a bitonic sequence.
It is easy to see that there exists SiPs which have the Odd-One property but do not satisfy
the Bitonic property; consider, for example, the permutation π = (2, 1, 4, 3, 6, 5, 7).
• Block property: The algorithm Encode W.to.SiP takes the binary representation of the integer w and initially constructs the binary number B ′ (see Step 2). The binary representation
of B ′ = 00
· · · 0} ||B||0 consists of three parts (or blocks):
| {z
n

(i) the first part contains the leftmost n bits, each equal to 0,
(ii) the second part contains the next n bits which form the binary representation B of the
integer w, and
(iii) the third part of length 1 contains a bit 0.
The structure of B ′ affects the construction of both subsequences X and Y (see Bitonic
property), and thus the elements of π1∗ , i.e., the first n elements of permutation π ∗ , have
values in the set H = {n + 1, n + 2, . . . , 2n, 2n + 1}. Consequently, we say that the SiP π ∗
has the Block property if all the elements of π1∗ belong to H.
Since |π1∗ | = n and |H| = n + 1, there is one element α ∈ H which does not participate
in π1∗ . Moreover, since π ∗ is a SiP and its first n elements have values greater that n, it
follows that the element α forms the 1-cycle (α, α) of π ∗ . For example, consider the SiP
π ∗ = (5, 6, 9, 8, 1, 2, 7, 4, 3) which encodes the integer w = 12 with binary representation
B = 1100; the element α has value 7 since n = 4, H = {5, 6, 7, 8, 9}, and π1∗ = (5, 6, 9, 8).
Notice that there exist SiPs having the Bitonic property which do not satisfy the Block
property; for example, π = (5, 6, 9, 4, 1, 2, 8, 7, 3) is such a SiP.

16

• Range property: Let Rn denote the range of all the integers w having n-bit representation
with the most significant bit (msb) equal to 1. Thus, Rn = [2n−1 , 2n − 1], n ≥ 1.
For any integer w ∈ Rn , the n-bit representation of w has msb=1 and thus the first element
of sequence X is equal to n + 1 (see Step 3 of algorithm Encode W.to.SiP). Then, by construction, the first element of the SiP π ∗ has value n + 1. We say that a SiP π ∗ has the
Range property if the first element of π1∗ has value n + 1; in this case, by definition, the first
element of π2∗ is equal to 1.
Note: Clearly we can use n bits to represent an integer w′ ∈ Rn′ , where n > n′ (for example,
the 4-bit representation of w′ = 5 ∈ R3 is the binary number B = 0101); then, the msb
is equal to 0. In this case, our algorithm Encode W.to.SiP works correctly and produces a
SiP π ∗ of length n∗ = 2n + 1 which has both the Bitonic property and the Block property,
but does not have the Range property. For example, for w′ = 5 and n = 4 our algorithm
produces the SiP π ∗ = (6, 8, 9, 7, 5, 1, 4, 2, 3).
Observation 4.1 Let w be an integer in Rn = [2n−1 , 2n − 1] and let π ∗ be the SiP of length n∗ =
2n + 1 produced by our encoding algorithm Encode W.to.SiP. By construction, in all the cases
the maximum element 2n + 1 of π ∗ participates in π1∗ , except for the case where w is the last
integer in the range Rn , i.e., w = 2n − 1. In that case, since the binary representation of w is
B = 11 · · · 1, the bitonic sequence π1∗ is (n + 1, n + 2, . . . , 2n), which is trivially bitonic since it
monotonically increases. It follows that α is the maximum element 2n + 1, which is located in the
last position of π ∗ ; see the All-One case analysis in Subsection 4.1. We can see the structure of
π ∗ by considering, for example, the encoding of integer w = 15 ∈ R4 , where B = 1111 and thus
π ∗ = (5, 6, 7, 8, 1, 2, 3, 4, 9).
Hereafter, the term SiP will refer to a self-inverting permutation over the set Nn∗ having the above
four properties.

4.3

The Structure of the SiP

Let w ∈ Rn = [2n−1 , 2n − 1] be an integer encoded by the SiP π ∗ = π1∗ ||π2∗ where π1∗ and π2∗
are subsequences of lengths n and n + 1, respectively; see Subsection 4.1. As in Subsection 4.2,
α denotes the element of π ∗ which forms its 1-cycle. Moreover, by β and γ we denote the last
elements of π1∗ and π2∗ , respectively.
Based on the structures of the two subsequences π1∗ and π2∗ , we conclude that the structure of
the SiP π ∗ = π1∗ ||π2∗ has the following two forms:
(i) All-One case: w = 2n − 1. In this case, the SiP π ∗ is the concatenation of two increasing
sequences:
π1∗ = (n + 1, n + 2, . . . , 2n) and π2∗ = (1, 2, . . . , n, 2n + 1)
where the maximum element 2n + 1 of π ∗ belongs to π2∗ and, since π ∗ = π1∗ ||π2∗ , it is located
in the last position of π ∗ , i.e., α = γ = 2n + 1.
bn = [2n−1 , 2n − 2]. In this general case, the structure of π ∗ is of
(ii) Zero-and-One case: w ∈ R
the form:
π1∗ = (n + 1, n + 2, . . . , n + k, n + k1 , . . . , 2n + 1, . . . , β) and π2∗ = (1, 2, . . . , k, α, . . . , γ)
where k ≥ 1 and k1 > k + 1. Moreover, α = n + k + 1. Notice that the All-One case follows
from the general Zero-and-One case by setting k = n.

17

Recall that π1∗ and π2∗ are of lengths n and n + 1, respectively, that the sequence π1∗ is bitonic
whose elements have values greater than n and its first element always has value n + 1, and that
the sequence π2∗ always contains the element α and its first element has value 1.
Increasing Subsequences: Let π ∗ = (π1 , π2 , . . . , πn∗ ) be a SiP of length n∗ = 2n+1 produced by
our encoding algorithm Encode W.to.SiP and let I1 , I2 , . . ., Ih be the 1st, 2nd, . . ., hth increasing
subsequence of π ∗ , respectively; see Subsection 2.1.
(i) In the All-One case, where the number w = 2n − 1 is encoded, the SiP π ∗ has two increasing
subsequences I1 and I2 having the following form:
I1 = (n + 1, n + 2, . . . , 2n, 2n + 1) and

I2 = (1, 2, . . . , n)

that is, I1 = π1∗ ||(2n + 1) and I2 = π2∗ \(2n + 1).
bn = [2n−1 , 2n − 2], and let
(ii) Let us now consider the Zero-and-One case, where w ∈ R
∗
∗
∗
∗
π1∗ = π11
||π12
and π2∗ = π21
||π22
where:
∗
∗
∗
∗
= (1, 2, . . . , k, α), π22
= (q1 , q2 , . . . , γ).
π11
= (n + 1, . . . , 2n + 1), π12
= (p1 , p2 , . . . , β) and π21
∗
From the structure of subsequences π1∗ and π2∗ and since π ∗ is a SiP, it follows that π11
is an
∗
∗
increasing sequence, π12 is a decreasing sequence (because π1 is bitonic) whose minimum element β
∗
∗
∗
is larger than all the elements in π21
||π22
, π21
is an increasing sequence whose maximum element α
∗
is larger than all the elements in π22 , and γ is equal to the index of the maximum element 2n + 1
in π ∗ ; see Equation 3.
∗
We next focus on the structure of the sequence π22
= (q1 , q2 , . . . , γ). To this end, we rewrite the
∗
∗
∗
∗
sequence π1 more analytically as the concatenation of three subsequences, that is, π1∗ = π1a
||π1b
||π1c
such that
∗
∗
∗
π1a
= (n + 1, n + 2, . . . , n + k), π1b
= (n + k1 , n + k2 , . . . , n + km ), π1c
= (2n + 1, p1 , p2 , . . . , β)

where k ≥ 1 and m ≥ 0. By construction:
∗
= (n + 1, n + 2, . . . , n + k) form the
Fact 4.1. The indices of the elements of the subsequence π1a
∗
sequence π21 \(α) = (1, 2, . . . , k).

Indeed, n + 1 is the 1st element of π ∗ , n + 2 is the 2nd element, while n + k is the kth element of
π ∗ and the length of π1∗ is n. Additionally,
Fact 4.2. The indices of the elements of the subsequence
∗
∗
π1b
||π1c
= (n + k1 , n + k2 , . . . , n + km , 2n + 1, p1 , p2 , . . . , β)
∗
= (q1 , q2 , . . . , γ), where γ is the index of the maximum element 2n + 1.
form the sequence π22
∗
The indices of the elements of π22
are in the range [k + 1, n]; indeed, n + k1 is the (k + 1)st element
∗
of π , n + k2 is the (k + 2)nd element, while its last element β is the nth element of π ∗ . Thus, the
∗
∗
indices of the subsequence π1b
||π1c
have the following form:

(k + 1, k + 2, . . . , k + m) || (γ, γ + 1, γ + 2, . . . , n)
Since the sequence of indices (γ, γ + 1, γ + 2, . . . , n) corresponds to the elements of the decreasing
∗
∗
sequence π1c
= (2n+1, p1, p2 , . . . , β), it follows that these indices will appear in π22
in reverse order,
i.e., n, n − 1, . . . , γ. Moreover, since the sequence of indices (k + 1, k + 2, . . . , k + m) corresponds to
∗
= (n + k1 , n + k2 , . . . , n + km ), these indices will appear
the elements of the increasing sequence π1b
∗
in π22 in increasing order, i.e., k + 1, k + 2, . . . , k + m. Moreover, the maximum element k + m in
(k + 1, k + 2, . . . , k + m) is less than the min element γ in (γ, γ + 1, γ + 2, . . . , n).
18

∗
∗
Let λ be the length of the sequence π1c
= (2n + 1, p1 , p2 , . . . , β). Then the sequence π22
is
the concatenation of λ increasing subsequences Φ1 , Φ2 , . . . , Φλ with last elements n, n − 1, . . . , γ,
∗
respectively. That is, π22
has the following form:
∗
π22
= Φ1 || Φ2 || · · · || Φλ = (σ1 , n) || (σ2 , n − 1) || · · · || (σλ , γ)

where σ1 , σ2 , . . . , σλ are subsequences (some of which may be empty) such that σ1 || σ2 || . . . || σλ =
(k + 1, k + 2, . . . , k + m).
∗
∗
∗
∗
Having analyzed the structure of the four subsequences π11
, π12
, π21
, and π22
in the case where
n−1 n
∗
∗
∗
b
w ∈ Rn = [2
, 2 − 2], along with the subsequences π1a , π1b and π1c , we can then easily get the
structure of the increasing subsequences of π ∗ . It is easy to see that π ∗ is the concatenation of
2λ + 1 consecutive increasing subsequences:
π ∗ = I1 || I2 || . . . || Iλ || Ic || Iλ+1 || Iλ+2 || . . . || I2λ
where I1 = (n + 1, n + 2, . . . , 2n + 1), I2 = (p1 ), I3 = (p2 ), . . ., Iλ = (β), Ic = (1, 2, . . . , k, α),
Iλ+1 = Φ1 , Iλ+2 = Φ2 , . . ., I2λ = Φλ . Hereafter, the sequence
I(π ∗ ) = [I1 , I2 , . . . , Iλ , Ic , Iλ+1 , . . . , I2λ ]
will be referred to as the increasing-subsequence representation or, for short, I-representation of
π∗ .
Additionally, Facts 4.1 and 4.2 and since the first element of π2∗ is equal to 1 imply the following
lemma.
Lemma 4.1 Let π ∗ be a self-inverting permutation of length n∗ = 2n + 1 produced by algorithm
Encode W.to.SiP and let π ′ be the sequence resulting from π ∗ after either its leftmost n elements
or its rightmost n elements have been deleted. The SiP π ∗ can be fully reconstructed from π ′ .
Example 4.2 Consider the SiP π ∗ = (8, 9, 10, 11, 12, 13, 14, 1, 2, 10, 3, 7, 6, 4, 15) which encodes the number w = 127, that is, the last number in the range R7 = [2n−1 , 2n − 1] = [64, 127];
the binary representation of w is 1111111 and thus n = 7 (case All-One). In this case, the two
subsequences π1∗ and π2∗ are:
π1∗ = (8, 9, 10, 11, 12, 13, 14) and π2∗ = (1, 2, 3, 4, 5, 6, 7, 15)
where α = γ = 2n + 1 = 15. The SiP π ∗ consists of two increasing subsequences I1 = π1∗ ||(2n + 1)
and I2 = π2∗ \(2n + 1) and, thus, its I-representation I(π ∗ ) = [I1 , I2 ] is:
I(π ∗ ) = [(8, 9, 10, 11, 12, 13, 14, 15), (1, 2, 3, 4, 5, 6, 7)].
Example 4.3 Consider now the SiP π ∗ = (8, 9, 11, 14, 15, 13, 12, 1, 2, 10, 3, 7, 6, 4, 5) which
encodes the number w = 105; the binary representation of w is 1101001 and w belongs to the range
b7 = [2n−1 , 2n − 2] = [64, 126] (case Zero-and-One). The subsequences π ∗ , π ∗ , π ∗ , and π ∗ are:
R
11
12
21
22
∗
∗
∗
∗
π11
= (8, 9, 11, 14, 15), π12
= (13, 12), π21
= (1, 2, 10) and π22
= (3, 7, 6, 4, 5)

where α = 10, β = 12, γ = 5, and the maximum element of π ∗ is 2n + 1 = 15. Since the decreasing
∗
subsequence (15, 13, 12) has length λ = 3, it follows that their indices 5, 6, 7 appear in π22
in
∗
reverse order and thus π22 is the concatenation of 3 increasing subsequences Φ1 , Φ2 , and Φ3 with
last elements 7, 6, 5, respectively; indeed, Φ1 = (3, 7), Φ2 = (6) and Φ3 = (4, 5). Thus, the whole
SiP π ∗ is the concatenation of 2λ + 1 = 7 increasing subsequences
π ∗ = I1 || I2 || I3 || Ic || I4 || I5 || I6
19

and has the following I-representation:
I(π ∗ ) = [(8, 9, 11, 14, 15), (13), (12), (1, 2, 10), (3, 7), (6), (4, 5)].
CiS and 2iS Properties: Let π be a permutation over the set N2n+1 , n ≥ 1, and let S1 ,
S2 , . . ., Sk (k ≥ 1) be the 1st, 2nd, . . ., kth increasing subsequences of π, respectively; see
Subsection 2.1. We say that the permutation π has the consecutive increasing subsequence property
(or CiS property, for short) if π = S1 ||S2 || · · · ||Sk , k ≥ 1. Additionally, we say that π has the two
increasing subsequence property (or 2iS property, for short) if it has 2 increasing
subsequences


S1 = (n + 1, n + 2, . . . , 2n, 2n + 1) and S2 = (1, 2, . . . , n) and π = S1 \(2n + 1) || S2 || (2n + 1).
For example, the permutation π ∗ = (5, 6, 9, 8, 1, 2, 7, 4, 3) satisfies the CiS property since S1 =
(5, 6, 9), S2 = (8), S3 = (1, 2, 7), S4 = (4) and S5 = (3), and π = S1 ||S2 || . . . ||S5 , whereas the
permutation π ∗ = (5, 6, 7, 8, 1, 2, 3, 4, 9) satisfies the 2iS property.

Our analysis of the structure of the permutation π ∗ encoding a number w in the range Rn =
[2
, 2n − 1] with respect to its increasing subsequences establishes that π ∗ has the 2iS property
bn =
in the case where w = 2n − 1 (case All-One) and the CiS property in the case where w ∈ R
n−1 n
[2
, 2 − 2] (case Zero-and-One); see also Examples 4.2 and 4.3. Thus, we can state the following
result.
n−1

Theorem 4.1 Let π ∗ be the SiP which encodes a number w of the range Rn = [2n−1 , 2n − 1] and
let I1 , I2 , . . . , Ik be the 1st, 2nd, . . ., kth increasing subsequences of π ∗ , respectively. Then:
bn = [2n−1 , 2n − 2], π ∗ satisfies the CiS property, i.e., π ∗ = I1 || I2 || . . . || Ik , k ≥ 3;
(i) if w ∈ R


(ii) if w = 2n − 1, π ∗ satisfies the 2iS property, i.e., π ∗ = I1 \(2n + 1) || I2 || (2n + 1), where
I1 = (n + 1, n + 2, . . . , 2n, 2n + 1) and I2 = (1, 2, . . . , n).

5

Properties of the Flow-graph F [π ∗ ]

Collberg et al. [8, 10] describe several techniques for encoding watermark integers in graph structures. Based on the fact that there is a one-to-one correspondence, say, C, between self-inverting
permutations and isomorphism classes of RPGs, Collberg et al. [8] proposed a polynomial-time
algorithm for encoding the integer w as the RPG corresponding to the wth self-inverting permutation π in C. This encoding exploits only the inversion property of a self-inverting permutation
and does not incorporate any other property.
In our codec system (encode, decode)F[π∗] an integer w is encoded as a self-inverting permutation π ∗ using a construction technique which captures into π ∗ important properties such as the
odd-one, the bitonic, the block and the range properties. In this section, we describe the main properties of our reducible permutation graph F [π ∗ ] produced by the algorithm Encode SiP.to.RPG;
we mainly focus on the properties of F [π ∗ ] derived from permutation π ∗ and discuss them with
respect to resilience to attacks.

5.1

Codec Properties

In a graph-based watermarking environment, the watermark graph G[w] should not differ from
the graph data structures of real programs. Important properties are the maximum outdegree of
G which should not exceed two or three, and the existence of a unique root node so that all other
nodes can be reached from it. Moreover, G[w] should be resilient to attacks against edge and/or
node modifications. Finally, G[w] should be efficiently constructed.
Our watermark graph F [π ∗ ] incorporates all the above properties; indeed, the graph F [π ∗ ] and
the corresponding codec and system (encode, decode)F[π∗ ] have the following properties:
20

s

Td[π ∗]

n+1

n+2

...

2n

1

2

...

n

2n+1

Td[π ∗]

s

I1

n+1

...

n+2

n+k

n+k1

...

2n+1

I1
I2

...

I2

(a)
(a) All-One case:
π1∗ = (n + 1, n + 2, . . . , 2n)
π2∗ = (1, 2, . . . , n, 2n + 1)

1

2

...

k

α

Ic

π1∗||π2∗

Iλ+1
...
I2λ−1

...
In both cases: π =

Iλ

...

(b) Zero-One case:
π1∗ = (n + 1, n + 2, . . . , n + k, n + k1, . . . , 2n + 1, . . . , β)
π2∗ = (1, 2, . . . , k, α, . . . , γ)
∗

β

γ

I2λ

(b)

Figure 5: (a) All-One case: π ∗ = (I1 , I2 ), where I1 = π1∗ ||(2n+1) and I2 = π2∗ \(2n+1). (b) Zero-and-One
case: π ∗ = (I1 , I2 , . . . , Iλ , Ic , Iλ+1 , Iλ+2 , . . . , I2λ ).

• Appropriate graph types: The graph F [π ∗ ] is a directed graph on n∗ + 2 nodes with
outdegree at most two; that is, it has low max-outdegree, and thus it matches real program
graphs.
• High resilience: Since exactly one node of the graph F [π ∗ ] has outdegree 0, exactly one has
outdegree 1, and the rest have outdegree 2, we can with high probability identify and correct
edge modifications, i.e., edge-flips, edge-additions, or edge-deletions. Thus, the graph F [π ∗ ]
enables us to correct edge changes (see Section 6.2).
• Small size: The size |Pw | − |P | of the embedded watermark w is relatively small since the
size of the corresponding watermark graph F [π ∗ ] is O(n∗ ); in fact, F [π ∗ ]’s size is O(log2 w)
because n∗ = 2n + 1 and n = ⌈log2 w⌉.
• Efficient codecs: The codec (encode, decode)F [π∗ ] has low time and space complexity;
indeed, we have showed that both the encoding algorithm Encode SiP.to.RPG and the decoding algorithm Decode RPG.to.SiP require O(n∗ ) time and space, where n∗ is the size of
the input permutation π ∗ (see Theorems 3.3 and 3.4).
It is worth noting that our encoding and decoding algorithms use basic data structures and operations, and thus they are easily implementable.

5.2

Structural Properties

The algorithm Encode SiP.to.RPG presented in Subsection 3.2, which encodes a SiP π ∗ as a
reducible permutation graph F [π ∗ ], constructs the graph F [π ∗ ] by computing the function P (i) =

21

dmax(i) for each element i ∈ π ∗ , 1 ≤ i ≤ n∗ ; recall that dmax(i) is the maximum element in the
set of all the elements of π ∗ that d-dominate the element i (see Section 2.1).
Let I(π ∗ ) = [I1 , I2 , . . . , Iλ , Ic , Iλ+1 , . . . , I2λ ] be the I-representation of a SiP π ∗ having
bn = [2n−1 , 2n − 2] (case Zero-and-One), and
the CiS property, i.e., π ∗ encodes a number w ∈ R
let i be an element of the k-th increasing subsequence Ik of π ∗ , 1 ≤ k ≤ 2λ + 1. Based on the
structure of I(π ∗ ), it is easy to see that dmax(i) is the maximum element of the (k−1)-st increasing
subsequence Ik−1 of π ∗ which, in turn, is the last element of Ik−1 ; by convention, I0 = (s). Indeed,
in our Example 4.3 where π ∗ encodes the number w = 105, we have
I(π ∗ ) = [(8, 9, 11, 14, 15), (13), (12), (1, 2, 10), (3, 7), (6), (4, 5)]
and we can easily see that dmax(5) = dmax(4) = 6, dmax(6) = 7, dmax(7) = dmax(3) = 10,
dmax(10) = 12, and so on, whereas dmax(15) = dmax(14) = dmax(11) = dmax(9) = dmax(8) =
s.
In the case where π ∗ does not satisfy the CiS property, i.e., π ∗ encodes the last number in the
range Rn = [2n−1 , 2n − 1] (case All-One), we have a similar property. In this case, I(π ∗ ) = [I1 , I2 ]
where I1 = π1∗ ||(2n + 1) and I2 = π2∗ \(2n + 1) (see Section 4.3). We observe that for each element
i ∈ I1 , dmax(i) is the maximum element of the increasing subsequence I0 = {s}, whereas for each
element i ∈ I2 , dmax(i) is the 2nd largest element of the increasing subsequence I1 of π ∗ ; see such
a SiP π ∗ along with its I-representation I(π ∗ ) in Example 4.2.
Then, the Dmax-tree Td [π ∗ ] presented in Subsection 3.2, which is constructed by exploiting the
dmax values, has the following structure:
(i) All-One case: The tree Td [π ∗ ] consists of the root-node s at level 0 and 2 more levels: the 1st
level contains the elements of the 1st increasing subsequence I1 = π1∗ ||(2n + 1); the 2nd level
contains the elements of the 2nd increasing subsequence I2 = π2∗ \(2n + 1). All the nodes
of the 2nd level of Td [π ∗ ] have the node labeled with the number 2n (i.e., the 2nd largest
element of I1 ) as their parent node.
(ii) Zero-and-One case: In this general case, the tree Td [π ∗ ] consists of the root-node s
at level 0 and 2λ + 1 more levels, where 2λ + 1 is the length of the I-representation
I(π ∗ ) = [I1 , I2 , . . . , Iλ , Ic , Iλ+1 , . . . , I2λ ] of the SiP π ∗ : the kth level contains the elements
of the kth increasing subsequence Ii of I(π ∗ ). All the nodes of the kth level of Td [π ∗ ] have
as their parent node the node labeled with the maximum element of the (k − 1)-st increasing
subsequence Ik−1 of π ∗ ; by convention, we consider I0 = {s}.
The two different structures of the Dmax-tree Td [π ∗ ] corresponding to the All-One and the Zeroand-One cases are presented in Figure 5.
It is worth noting that the very strict structure of a self-inverting permutation π ∗ produced by
Algorithm Encode W.to.SiP enables us to obtain the increasing subsequences of π ∗ and construct
the watermark graph F [π ∗ ] in time linear in its size and, more importantly, makes the graph F [π ∗ ]
robust and resilient to attacks.

5.3

Unique Hamiltonian Path

It is well-known that any acyclic digraph G has at most one Hamiltonian path (HP) [8]; G has
one HP if there exists an ordering (v1 , v2 , . . . , vn ) of its n nodes such that in the subgraphs
G0 , G1 , . . . , Gn−1 the nodes v1 , v2 , . . . , vn , respectively, are the only nodes with indegree zero,
where G0 = G and Gi = G\{v1 , v2 , . . . , vi }, 1 ≤ i ≤ n − 1. Furthermore, it has been shown that
any reducible flow-graph has at most one Hamiltonian path [8].
It is not difficult to see that the reducible permutation graphs F [π ∗ ] constructed by Algorithm Encode SiP.to.RPG have a unique Hamiltonian path HP(F [π ∗ ]); it is precisely the path

22

(un∗ +1 , un∗ , · · · , u1 , u0 ). Such a path can be found in time linear in the size of F [π ∗ ] by the
following algorithm.
Algorithm Unique HP
1. Find the unique node, say, u, of the graph F [π ∗ ] with outdegree 1;
2. Perform DFS-search on graph F [π ∗ ] starting at node u and compute the DFS discovery
time d[v] of each node v of F [π ∗ ];
3. Return HP(F [π ∗ ]) = (u′0 , u′1 , . . . , u′n∗ +1 ) where (u′0 , u′1 , . . . , u′n∗ +1 ) is the ordering of the nodes
of the graph F [π ∗ ] by increasing DFS discovery time d[], i.e., d[u′i ] < d[u′j ] for i < j, 0 ≤
i, j ≤ n∗ + 1;
Since the graph F [π ∗ ] contains n∗ + 2 nodes and 2n∗ + 1 edges, both finding the node of F [π ∗ ]
with outdegree 1 and performing DFS-search on F [π ∗ ] take O(n∗ ) time and require O(n∗ ) space.
Moreover, the ordering of the nodes by their DFS discovery time is readily obtained during the
DFS-traversal. Thus, we have the following result.
Theorem 5.1 Let F [π ∗ ] be a reducible permutation graph of size O(n∗ ) constructed by algorithm
Encode SiP.to.RPG. The algorithm Unique HP correctly computes the unique Hamiltonian path of
F [π ∗ ] in O(n∗ ) time and space.

6

Detecting Attacks

In this section, we show that the malicious intentions of an attacker to prevent our system from
returning the correct watermark value by modifying node-labels or edges of the graph F [π ∗ ] can
be efficiently detected in most cases.

6.1

Node-label Modification

By construction, our reducible permutation graph F [π ∗ ] is a node-labeled graph on n∗ + 2 nodes,
where n∗ is the length of π ∗ . The labels of F [π ∗ ] are numbers of the set {0, 1, . . . , n∗ + 1}, where
the label n∗ + 1 is assigned to header node s = un∗ +1 , the label 0 is assigned to footer node t = u0 ,
and the label n∗ + 1 − i is assigned to the ith node un∗ +1−i of the body of F [π ∗ ], 1 ≤ i ≤ n.
A label modification attacker may perform swapping of the labels of two nodes of F [π ∗ ], altering
thus the value of the label of a node, or even removing all the labels of the graph F [π ∗ ] resulting in a
node-unlabeled graph. Since the decoding of the watermark w relies on the labels of the flow-graph
F [π ∗ ] (see algorithm Decode RPG.to.SiP), it follows that our codec system (encode, decode)F[π∗ ]
is susceptible to node-label modification attacks.
Therefore, it is important to have a way to decode the watermark w efficiently from F [π ∗ ]
without relying on its labels. The correct labels can be easily obtained in O(n∗ ) time and space
thanks to the unique Hamiltonian path HP(F [π ∗ ]) and the fact that the node-labels of F [π ∗ ]) are
encountered along HP(F [π ∗ ]) in decreasing order. Thus, we have the following result.
Lemma 6.1 Let F [π ∗ ] be a reducible permutation graph of size O(n∗ ) produced by algorithm
Encode SiP.to.RPG and let F ′ [π ∗ ] be the graph resulting from F [π ∗ ] after having modified or
deleted the node-labels of F [π ∗ ]. The flow-graph F [π ∗ ] can be reconstructed from F ′ [π ∗ ] in O(n∗ )
time and space.
Moreover, since the number of nodes of the graph F [π ∗ ] is odd, any single node modification
in F [π ∗ ], i.e., a node-addition or a node-deletion, can be easily identified.

23

True-incorrectness Results
Edges
Range
R4
R5
R6
R7
R8
R9
R10

1

2

3

4

5

6

0
0
0
0
0
0
0

0
0
0
0
0
0
0

0.0005
0.0003
0.0002
0.0001
0.00008
0.00005
0.00003

0.0002
0.00005
0.00001
0.7 × 10−5
0.4 × 10−5
0.2 × 10−5
0.9 × 10−6

0.00009
0.7 × 10−5
0.1 × 10−5
0.9 × 10−6
0.5 × 10−6
0.1 × 10−6
0.8 × 10−7

0.00003
0.2 × 10−5
0.2 × 10−6
0.1 × 10−6
0.1 × 10−7
0.1 × 10−7
0.1 × 10−8

Table 1: The ratio of experiments in which the flow-graph F [π ∗ ] encoding the number w ∈ Rn =
[2n−1 , 2n − 1] was found to be true-incorrect after k edge-modifications, where 1 ≤ k ≤ 6 and n =
4, 5, . . . , 10.

6.2

Edge Modification

We next argue that we can decide, in nearly all cases, whether the reducible permutation
graph F [π ∗ ] produced by our codec system has suffered an attack on its edges.
Let F [π ∗ ] be a flow-graph which encodes the integer w and let F ′ [π ∗ ] be the graph resulting
from F [π ∗ ] after an edge modification. Then, we say that F ′ [π ∗ ] is either a false-incorrect or a
true-incorrect graph:
• F ′ [π ∗ ] is false-incorrect if our codec system fails to return an integer from the graph F ′ [π ∗ ],
whereas
• F ′ [π ∗ ] is true-incorrect if our system extracts from F ′ [π ∗ ] and returns an integer w′ 6= w.
Since the SiP properties of the permutation π ∗ which compose the 4-Chain property (see Subsection 4.2) are incorporated in the structure of the reducible permutation graph F [π ∗ ], it follows
that the graph F ′ [π ∗ ] resulting from F [π ∗ ] after any edge modification is false-incorrect if at least
one of the SiP properties does not hold.
We experimentally evaluated the resilience of the watermark graph F [π ∗ ] in edge modifications.
To this end, we have produced graphs F [π ∗ ] on 2n + 3 = 11, 13, . . . , 23 nodes (i.e., n = 4, 5, . . . , 10)
and computed the ratio of the experiments in which the graph Fk [π ∗ ] was found to be true-incorrect,
where Fk′ [π ∗ ] is the graph resulting from F [π ∗ ] after the modification of k edges, 1 ≤ k ≤ 6. More
precisely, our experimental study is based on the following algorithmic scheme:
for each n = 4, 5, . . . , 10:
for each number wi in the range Rn = [2n−1 , 2n − 1]:
1. encode the number wi as a SiP π ∗ of length n∗ = 2n + 1 using Algorithm
Encode W.to.SiP and then encode π ∗ as a reducible permutation graph F [π ∗ ] of order n∗ + 2 using Algorithm Encode SiP.to.RPG;
2. for each k = 1, 2, . . . , 6:
repeat the following two steps Nn = ⌈ (2n+1)
× 105 ⌉ times in order to randomly
9
∗
modify k edges of the graph F [π ] and count the number N (wi , n, k) of times that
the modified graph Fk′ [π ∗ ] is true-incorrect;
a. randomly select k edges (ux , uy ) and k nodes uz from the graph F [π ∗ ];
b. delete the k edges (ux , uy ) and add the k edges (ux , uz ) thus yielding the modified graph Fk′ [π ∗ ];
for each n = 4, 5, . . . , 10 and each k = 1, 2, . . . , 6:
P n


2 −1
print the ratio
N
(w
,
n,
k)
/ 2n−1 × Nn of true-incorrect cases.
n−1
i
i=2
24

×10−3

3-edge
4-edge
5-edge
6-edge

0.6

0.5

attacks
attacks
attacks
attacks

Ratio

0.4

0.3

0.2

0.1

0
R4

R5

R6

R7

R8

R9

R10

Ranges - Number of Nodes

Figure 6: The ratio of experiments in which the RPG F [π ∗ ] was found to be true-incorrect after a
modification of 3, 4, 5, and 6 edges.

Note that as n increases, the size of the reducible permutation graph F [π ∗ ] increases linearly; thus,
for each wi ∈ Rn = [2n−1 , 2n − 1], we repeat the edge modification experiment Nn times, where
Nn depends linearly on n.
The experimental results show that the computed ratio of true-incorrect cases is really small
and falls dramatically as n gets larger (see Table 1 and Figure 6); in fact, no true-incorrect case
is possible if at most 2 edges are modified [2]. Thus, we can decide with high probability whether
our reducible permutation graph F [π ∗ ] has suffered an attack on its edges.

7

Concluding Remarks

In this paper we proposed an efficient and easily implementable codec system for encoding watermark numbers as graph structures. Our codec (encode, decode)F [π∗ ] system incorporates several
important properties and characteristics which make it appropriate for use in a real software watermarking environment. The reducible permutation flow-graph F [π ∗ ] resembles the graph data
structures of real programs since its maximum outdegree does not exceed two and it has a unique
root node. Additionally, the self-inverting permutation π ∗ and the flow-graph F [π ∗ ] encompass
important structural properties, which make our codec system resilient to attacks; indeed, the
graph F [π ∗ ] is highly insensitive to small edge-changes and fairly insensitive to small node-changes
of F [π ∗ ]. Finally, we point out that our codec system has very low time and space complexity which
is O(n), where n is the number of bits in the binary representation of the watermark integer w.
In light of the two main data components of our codec system, i.e., the permutation π ∗ and
the graph F [π ∗ ], it would be very interesting to come up with new efficient codec algorithms and
structures exhibiting an improved behavior with respect to resilience to attacks; we leave it as an
open question. Another interesting question with practical value is whether the class of reducible
permutation graphs can be extended so that it includes other classes of graphs with structural
properties capable to efficiently encode watermark numbers.
Finally, the evaluation of our codec algorithms and structures under other watermarking measurements in order to obtain detailed information about their practical behavior is an interesting
problem for future study.
25

References
[1] G. Arboit. A method for watermarking Java programs via opaque predicates. 5th International
Conference on Electronic Commerce Research (ICECR-5), 2002.
[2] L.M.S. Bento, D. Boccardo, R.C.S. Machado, V.G. Pereira, and J.L. Szwarcfiter. Towards a
provably resilient scheme for graph-based watermarking. Int’l Workshop on Graph-Theoretic
Concepts in Computer Science (WG’13), LNCS 8165, 50-63, 2013.
[3] M. Chroni and S.D. Nikolopoulos. Encoding watermark integers as self-inverting permutations.
International Conference on Computer Systems and Technologies (CompSysTech’10), ACM
ICPS 471, 125–130, 2010.
[4] M. Chroni and S.D. Nikolopoulos. An Efficient Graph Codec System for Software Watermarking. Proc. 36th IEEE Conference on Computers, Software, and Applications (COMPSAC’12),
IEEE Proceedings, 595–600, 2012.
[5] I. Chionis, M. Chroni, S.D. Nikolopoulos. A Dynamic Watermarking Model for Embedding
Reducible Permutation Graphs into Software. Proc. 10th Int’l Conference on Security and
Cryptography (SECRYPT’13), SciTePress Digital Library, 74–85, 2013.
[6] C. Collberg, E. Carter, S. Debray, A. Huntwork, J. Kececioglu, C. Linn and M. Stepp. Dynamic
path-based software watermarking. Proc. ACM Conference on Programming Language Design
and Implementation, ACM SIGPLAN 39, 107–118, 2004.
[7] C. Collberg and J. Nagra. Surreptitious Software. Addison-Wesley, 2010.
[8] C. Collberg, S. Kobourov, E. Carter, and C. Thomborson. Error-correcting graphs for software watermarking. Proc. 29th Workshop on Graph-Theoretic Concepts in Computer Science
(WG’03), LNCS 2880, 156–167, 2003.
[9] C. Collberg, A. Huntwork, E. Carter, G. Townsend, and M. Stepp. More on graph theoretic
software watermarks: Implementation, analysis, and attacks. Information and Software Technology 51, 56–67, 2009.
[10] C. Collberg and C. Thomborson. Software watermarking: models and dynamic embeddings.
Proc. 26th ACM SIGPLAN-SIGACT on Principles of Programming Languages (POPL’99),
311–324, 1999.
[11] C. Collberg, C. Thomborson, and G.M. Townsend. Dynamic graph-based software fingerprinting. ACM Transactions on Programming Languages and Systems 29, 1-67, 2007.
[12] P. Cousot and R. Cousot. An abstract interpretation-based framework for software watermarking. Proc. 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming
Languages (POPL’04), 173–185, 2004.
[13] D. Curran, N. Hurley and M. Cinneide. Securing Java through software satermarking, Proc.
Int’l Conference on Principles and Practice of Programming in Java (PPPJ’03), 145–148, 2003.
[14] I. Cox, J. Kilian, T. Leighton, and T. Shamoon. A secure, robust watermark for multimedia.
Proc. 1st Int’l Workshop on Information Hiding, LNCS 1174, 317–333, 1996.
[15] R.L. Davidson and N. Myhrvold. Method and system for generating and auditing a signature
for a computer program. US Patent 5.559.884, Microsoft Corporation, 1996.
[16] R. Giacobazzi, I. Mastroeni, M.D.Preda. Maximal incompleteness as obfuscation potency.
Formal Asp. Comput. 29(1), 3–31, 2017.
26

[17] R. Giacobazzi. Hiding information in completeness holes: new perspectives in code obfuscation
and watermarking. Proc. 6th IEEE International Conference on Software Engineering and
Formal Methods (SEFM’08), 7–18, 2008.
[18] M.C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York
(1980). Second edition, Annals of Discrete Math. 57, Elsevier, 2004.
[19] M.S. Hecht and J.D. Ullman. Flow graph reducibility. SIAM J. Computing 1, 188–202, 1972.
[20] M.S. Hecht and J.D. Ullman. Characterizations of reducible flow graphs. Journal of the
ACM 21, 367–375, 1974.
[21] S.A. Moskowitz and M. Cooperman. Method for stegacipher protection of computer code. US
Patent 5.745.569, 1996.
[22] A. Monden, H. Iida, K. Matsumoto, K. Inoue and K. Torii. A practical method for watermarking Java programs, Proc. 24th Computer Software and Applications Conference (COMPSAC’00), 191–197, 2000.
[23] A. Mpanti and S.D. Nikolopoulos. Graph-structured watermarking using bitonic sequences
of self-inverting permutations, Proc. 20th Pan-Hellenic Conference on Informatics (PCI’16),
ACM Didital Lib, Article No. 13, 2016.
[24] G. Myles and C. Collberg. Software watermarking via opaque predicates: Implementation,
analysis, and attacks. Electronic Commerce Research 6, 155–171, 2006.
[25] J. Nagra and C. Thomborson. Threading software watermarks. Proc. 6th Int’l Workshop on
Information Hiding (IH’04), LNCS 3200, 208-223, 2004.
[26] F. Nielson, H.R. Nielson, and C. Hanking. Principles of Program Analysis, Springer-Verlag,
2004.
[27] A.S. Panah, R. Van Schyndel, T. Sellis and E. Bertino. On the properties of non-media digital
watermarking: a review of state of the art techniques, IEEE Access 4, 2670–2704, 2016.
[28] P. Samson. Apparatus and method for serializing and validating copies of computer software.
US Patent 5.287.408, 1994.
[29] H. Tamada, M. Nakamura, A. Monden, and K. Matsumoto. Design and evaluation of birthmarks for detecting theft of Java programs. Proc. Int’l Conference on Software Engineering
(SE’04), 569–575, 2004.
[30] R. Venkatesan, V. Vazirani, and S. Sinha. A graph theoretic approach to software watermarking. Proc. 4th Int’l Workshop on Information Hiding (IH’01), LNCS 2137, 157–168, 2001.
[31] L. Zhang, Y. Yang, X. Niu, and S. Niu. A survey on software watermarking. Journal of
Software 14, 268–277, 2003.
[32] W. Zhu, C. Thomborson, and F.Y. Wang. A survey of software watermarking. Proc. IEEE
Int’l Conference on Intelligence and Security Informatics (ISI’05), LNCS 3495, 454–458, 2005.

27

