Semantics-based software watermarking by abstract interpretation

Software watermarking is a software protection technique used to defend the intellectual property of proprietary code. In particular, software watermarking aims at preventing software piracy by embedding a signature, i.e. an identier reliably representing the owner, in the code. When an illegal copy is made, the owner can claim his/her identity by extracting the signature. It is important to hide the signature in the program in order to make it dicult for the attacker to detect, tamper or remove it. In this work we present a formal framework for software watermarking, based on program semantics and abstract interpretation, where attackers are modeled as abstract interpreters. In this setting we can prove that the ability to identify signatures can be modeled as a completeness property of the attackers in the abstract interpretation framework. Indeed, hiding a signature in the code corresponds to embed it as a semantic property that can be retrieved only by attackers that are complete for it. Any abstract interpreter that is not complete for the property specifying the signature cannot detect, tamper or remove it. We formalize in the proposed framework the major quality features of a software watermarking technique: secrecy, resilience, transparence and accuracy. This provides an unifying framework for interpreting both watermarking schemes and attacks, and it allows us to formally compare the quality of dierent watermarking techniques. Indeed, a large number of watermarking techniques exist in the literature and they are typically evaluated with respect to their secrecy, resilience, transparence and accuracy to attacks. Formally identifying the attacks for which a watermarking scheme is secret, resilient, transparent or accurate can be a complex and error-prone task, since attacks and watermarking schemes are typically dened in dierent settings and using dierent languages (e.g. program transformation vs. program analysis), complicating the task of comparing one against the others.