Fingerprinting intellectual property using constraint-addition

ABSTRACT

Recently, intellectual property protection (IPP) techniques attracted a great deal of attention from semiconductor, system integration and software companies. A number of watermarking-based techniques have been proposed for IPP. One of the key limitations of watermarking is that it does not facilitate tracing of illegally resold intellectual property (IP). Fingerprinting resolves this problem by providing each customer with a unique instance of functionally identical IP. We propose a general technique which enables fingerprinting at all level of design process and is applicable to an arbitrary optimization step. In particular, we address the following fingerprinting problem: How to generate a large number of high quality solution for a given optimization problem by solving the initial problem only once. In addition we also discuss how to select a subset of k solutions from the pool of n solutions so that the solutions are maximally different. In order to make our discussion concrete we focus on a single NP-complete problem -- graph coloring. We test the new fingerprinting on a number of standard benchmarks. Interestingly, while on random graphs it is relatively difficult to produce a large number of solutions without nontrivial quality degradation, on all real-life compilation graphs we are able to generate millions of solution which are all optimal.

REFERENCES

• 1: Ingrid Biehl , Bernd Meyer, Protocols for Collusion-Secure Asymmetric Fingerprinting (Extended Abstract), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.399-412, February 27-March 01, 1997
• 2: Dan Boneh , James Shaw, Collusion-Secure Fingerprinting for Digital Data (Extended Abstract), Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.452-465, August 27-31, 1995
• 3: L. Boney, A.H. Tewfik, and K.N. Hamdy. Digital watermark for audio signals. International Conference on Multimedia Computing and Systems, pp. 473-480, 1996.
• 4: E. Charbon. Hierarchical Watermarking in IC Design. IEEE 1998 Custom Integrated Circuits Conference, pp. 295-298, 1998.
• 5: Andrew E. Caldwell , Hyun-Jin Choi , Andrew B. Kahng , Stefanus Mantik , Miodrag Potkonjak , Gang Qu , Jennifer L. Wong, Effective iterative techniques for fingerprinting design IP, Proceedings of the 36th ACM/IEEE conference on Design automation, p.843-848, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310083]
• 6: Ming-Te Chao , John Franco, Probabilistic analysis of two heuristics for the 3-satisfiability problem, SIAM Journal on Computing, v.15 n.4, p.1106-1118, Nov. 1986 [doi>10.1137/0215080]
• 7: Benny Chor , Amos Fiat , Moni Naor, Tracing Traitors, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.257-270, August 21-25, 1994
• 8: I.J. Cox, J. Kilian, T. Leighton, and T. Shamoon. A secure, imperceptible yet perceptually salient, spread spectrum watermark for multimedia. Southcon, pp. 192-197, 1996.
• 9: A. B. Kahng , J. Lach , W. H. Mangione-Smith , S. Mantik , I. L. Markov , M. Potkonjak , P. Tucker , H. Wang , G. Wolfe, Watermarking techniques for intellectual property protection, Proceedings of the 35th annual conference on Design automation, p.776-781, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277240]
• 10: J.Lach, W.H.Mangione-Smith, and M.Potkonjak. FPGA Fingerprinting Techniques for Protecting Intellectual Property. Proceedings of CICC, 1998.
• 11: Arlindo L. Oliveira, Robust techniques for watermarking sequential circuit designs, Proceedings of the 36th ACM/IEEE conference on Design automation, p.837-842, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310082]
• 12: B. Pfitzmann, and M. Schunter. Asymmetric Fingerprinting. Advances in Cryptology - EUROCRYPT'96, Proceedings of International Conference on the Theory and Application of Cryptographic Techniques. Maurer (Ed.), Springer-Verlag, pp. 84-95, 1996.
• 13: Gang Qu , Miodrag Potkonjak, Analysis of watermarking techniques for graph coloring problem, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.190-193, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288607]
• 14: Neal R. Wagner, Fingerprinting, Proceedings of the 1983 IEEE Symposium on Security and Privacy, p.18, April 25-27, 1983
• 15: VSI Alliance. System Chip Letter. Issue 2, Summer 1998.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Experimentation, Measurement, Performance, Security, Standardization, Theory