We propose a new class of software watermarking and fingerprinting methods
called "abstract software watermarking". The key idea is to hide the
secret signature in a stegomark that is a piece of code which is inlayed in
the subject program. The extraction of the signature is by an abstract
interpretation-based static analysis of the transformed program. So the
signature extraction is neither "static" (in the watermarking community
sense) since it is based on the semantics of the program (not its syntax)
nor "dynamic" since no program execution can reveal the signature but
"abstract" (the signature can only be revealed by an abstract
interpretation of the program semantics). Since static analysis is
undecidable, the static analyzer which is used for signature extraction can
be involved enough so that extraction is impossible if it is not perfectly
known. Even if the signature extractor is made public, it is still
possible to use abstract domains parameterized by secret stegokeys which
make signature extraction computationally hard, if not impossible.
We exemplify an instance of the framework based on modular constant
propagation parameterized by a secret stegokey, which is equivalent to
infinitely many instances of the abstract watermarker.
The paper introduces the framework, its instantiation to parameterized
modular constant propagation, potential attacks and their deterrence.
