  Software watermarking involves embedding a unique identifier or,
equivalently, a watermark value within a software to prove owner's authenticity
and thus to prevent or discourage copyright infringement. Towards the embedding
process, several graph theoretic watermarking algorithmic techniques encode the
watermark values as graph structures and embed them in application programs.
Recently, we presented an efficient codec system for encoding a watermark
number $w$ as a reducible permutation graph $F[\pi^*]$ through the use of
self-inverting permutations $\pi^*$. In this paper, we propose a dynamic
watermarking model, which we call WaterRPG, for embedding the watermark graph
$F[\pi^*]$ into an application program $P$. The main idea behind the proposed
watermarking model is a systematic use of appropriate calls of specific
functions of the program $P$. More precisely, for a specific input $I_{key}$ of
the program $P$, our model takes the dynamic call-graph $G(P, I_{key})$ of $P$
and the watermark graph $F[\pi^*]$, and produces the watermarked program $P^*$
having the following key property: its dynamic call-graph $G(P^*, I_{key})$ is
isomorphic to the watermark graph $F[\pi^*]$. Within this idea the program
$P^*$ is produced by only altering appropriate calls of specific functions of
the input application program $P$. We have implemented our watermarking model
WaterRPG in real application programs and evaluated its functionality under
various and broadly used watermarking assessment criteria. The evaluation
results show that our model efficiently watermarks Java application programs
with respect to several watermarking metrics like data-rate, bytecode
instructions overhead, resiliency, time and space efficiency. Moreover, the
embedded watermarks withstand several software obfuscation and optimization
attacks.
