A graph theoretic approach to software watermarking

Ramarathnam Venkatesan, Vijay Vazirani, Saurabh Sinha

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a graph theoretic approach for watermarking software in a robust fashion. While watermarking software that are small in size (e.g. a few kilobytes) may be infeasible through this approach, it seems to be a viable scheme for large applications. Our approach works with control/data flow graphs and uses abstractions,approximate k-partitions,and a random walk method to embed the watermark,with the goal of minimizing and controlling the additions to be made for embedding,while keeping the estimated effort to undo the watermark (WM) as high as possible. The watermarks are so embedded that small changes to the software or flow graph are unlikely to disable detection by a probabilistic algorithm that has a secret. This is done by using some relatively robust graph properties and error correcting codes. Under some natural assumptions about the code added to embed the WM,locating the WM by an attacker is related to some graph approximation problems. Since little theoretical foundation exists for hardness of typical instances of graph approximation problems,we present heuristics to generate such hard instances and,in a limited case, present a heuristic analysis of how hard it is to separate the WM in an information theoretic model. We describe some related experimental work. The approach and methods described here also suitable for solving the problem of software tamper resistance.

Original languageEnglish (US)
Title of host publicationInformation Hiding - 4th International Workshop, IH 2001, Proceedings
EditorsIra S. Moskowitz
Number of pages12
ISBN (Print)3540427333, 9783540427339
StatePublished - 2001
Externally publishedYes
Event4th International Information Hiding Workshop, IHW 2001 - Pittsburgh, United States
Duration: Apr 25 2001Apr 27 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Information Hiding Workshop, IHW 2001
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A graph theoretic approach to software watermarking'. Together they form a unique fingerprint.

Cite this