@InProceedings{	  venkatesan01graph,
  author =	 {Ramarathnam Venkatesan and Vijay Vazirani and
                  Saurabh Sinha},
  title =	 {A Graph Theoretic Approach to Software Watermarking},
  booktitle =	 {4th International Information Hiding Workshop},
  year =	 2001,
  address =	 {Pittsburgh, PA},
  month =	 apr,
  abstract =	 {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. },
  url =
                  {http://link.springer.de/link/service/series/0558/bibs/2137/21370157.htm},
  cache =	 {venkatesan01.pdf},
  section = {SOFTWARE-WATERMARKING}
}