A semantics-based approach to software watermarking by abstract interpretation

Software watermarking is a defence technique used to prevent software piracy by embedding a signature in the code. When an illegal copy is made, the ownership can be claimed by extracting the signature. The signature has to be hidden inside the code and it has to be difficult for an attacker to detect, tamper or remove it. In this paper we show how the ability of the attacker to identify the signature can be modelled in the framework of abstract interpretation as a completeness property. We view attackers as abstract interpreters that can precisely observe only the properties for which they are complete. In this setting, hiding a signature in the code corresponds to insert it in terms of a semantic property that can be retrieved only by attackers that are complete for it. Indeed, any abstract interpreter that is not complete for the property specifying the signature cannot detect, tamper or remove it.