Experience with Software WatermarkingJens Palsberg, Sowmya Krishnaswamy, Minseok Kwon, Di Ma, Qiuyun Shao, Yi ZhangProperties of WatermarksEasy to createEasy to verifyDifficult to removeDifficult to alterStatic Software WatermarksStatic data watermarks are easy to alter and removeCan be attacked by static code analyzersMany semantics-preserving modifications will automatically remove them.Dynamic Software WatermarksMuch more difficult to attackNearly impossible to statically analyzeAltering final runtime structure by changing the program is very difficultExamples“Easter Egg” watermarksWatermarks which depend on the object graphGraph based watermarkingInserting the watermarkCreate a watermark graphInsert it into the program’s object graphRecovering the watermarkCreate a copy of the runtime object graphFind a subgraph isomorphic to the watermark graphWithout prior knowledge, this is an NP Complete ProblemWhat are PPCTs?Stands for “Planted Plane Cubic TreeA binary tree structure, with an extra “Origin” nodeOrigin node and leaf nodes form a circularly linked listOriginFigure 1. PPCTC(1) = 1C(2) = 1C(3) = 2C(4) = 5000000 1100 1122... ...Figure 2. Enumeration of PPCTrepresented integer by . Thenwhere function gives the number ofleaves of the tre e rooted by .2.2 Watermark EmbeddingTo watermark a Java program with a given number, wefirst determine its PPCT representation . Next we choose abase class from the original program and convert it into anode class by adding some fields. E a c h ad ditional field willhold an outgoing edge to another node object. The nodeclass is now a building block for constru c ting the PPCT,and off-line we generate straight-line code that constructsthe PPCT. The graph c onstruction code is then merged withthe original progra m. We do this in a particular ly simpleway to illustrate the idea without getting into implementin gfull-fledged randomiza tion, o bfuscation, and tamperproof-ing. We view th e se other protection techniques as buildingblocks that can be ad ded on to p of our appr oach. In ourimplementation on ly the “new” expression s in the originalcode will be changed. Intuitively if there is an expression”new A()”, then we may change it to ”new A1()”, and adda class A1 which extends A a nd place some watermarkingcode in its constructor.For example, suppose we have the following code forclass A:class A{A(){a1 = 0;}int a1;}We can change the code into:class A1{A1(){a1 = 0;<code for buildingwatermark>/ / produce d offline}int a1;}While this may seem simp le, bordering on trivial,it is sufficient to protect against a variety of program-transform a tion attacks, as we will show later.4What are PPCTs?Each leaf node points to itselfEach node has two pointers in itNote that from any node, you can reach the origin node.OriginFigure 1. PPCTC(1) = 1C(2) = 1C(3) = 2C(4) = 5000000 1100 1122... ...Figure 2. Enumeration of PPCTrepresented integer by . Thenwhere function gives the numb e r ofleaves of the tre e rooted by .2.2 Watermark EmbeddingTo watermark a Java program with a given number, wefirst determine its PPCT representation . Next we choose abase class from the original program and convert it into anode class by adding some fields. Each additional field willhold an outgoing edge to another node object. The nodeclass is now a building block for constru c ting the PPCT,and off-line we generate straight-line code that constructsthe PPCT. The graph c onstruction code is then merged withthe original progra m. We do this in a particular ly simpleway to illustrate the idea without getting into implementin gfull-fledged randomiza tion, o bfuscation, and tamperproof-ing. We view th e se other protection techniques as buildingblocks that can be ad ded on to p of our appr oach. In ourimplementation on ly the “new” expression s in the originalcode will be changed. Intuitively if there is an expression”new A()”, then we may change it to ”new A1()”, and adda class A1 which extends A a nd place some watermarkingcode in its constructor.For example, suppose we have the following code forclass A:class A{A(){a1 = 0;}int a1;}We can change the code into:class A1{A1(){a1 = 0;<code for buildingwatermark>/ / produce d offline}int a1;}While this may seem simp le, bordering on trivial,it is sufficient to protect against a variety of program-transform a tion attacks, as we will show later.4How to represent a watermark with a PPCTEach PPCT with a certain number of nodes has an enumerable set of treesMake a tree large enough to represent your numberOriginFigure 1. PPCTC(1) = 1C(2) = 1C(3) = 2C(4) = 500000011001122... ...Figure 2. Enumeration of PPCTrepresented integer by . Thenwhere function gives the number ofleaves of the tree ro oted by .2.2 Watermark EmbeddingTo watermark a Java progra m with a given number, wefirst de termine its PPCT representation. Next we choose abase c lass from the original program an d co nvert it into anode class by adding some fields. Each additional field willhold an outgoing edge to another node object. The nod eclass is now a building block for constructing the PPCT,and off-line we generate straigh t-line code that constructsthe PPCT. The graph construction code is then m e rged withthe original program. We do this in a particularly simpleway to illustrate the idea without getting into im plementingfull-fledged randomization, obfuscation, and tamperproof -ing. We view the se oth e r protec tion tech niques as buildingblocks that can be added on top of our ap proach. In ourimplementation only the “new” expressions in the originalcode will be changed. Intu itively if there is an expression”new A( )”, then we may change it to ”new A1()”, and adda class A1 which extends A and place some watermarkingcode in its constructor.For example, sup pose we have the following code forclass A:class A{A(){a1 = 0;}int a1;}We can change the code into:class A1{A1(){a1 = 0;<code for buildingwatermark>/ / produced offline}int a1;}While this may seem simple, bordering on trivial,it is sufficient to protect against a variety of program-transform a tion attacks, as we will show later.4How do we create the object graph?Find all the non-library classesCan’t rely on names, because they may have been obfuscatedFind all objects in memory of those classes (nodes)Find pointers/references between these objects (edges)How do we find the PPCT?In the object graph, find potential leaf nodes (nodes which have edges to themselves)Try to