An Abstract Interpretation-Based Framework for Software Watermarking

Patrick Cousot and Radhia Cousot

To appear at Principles of Programming Languages (POPL04), Venice, Italy, January 14-16, 2004


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.

Server START Conference Manager
Update Time 19 Sep 2003 at 17:40:43
Start Conference Manager
Conference Systems