Forensic engineering techniques for VLSI CAD tools

ABSTRACT

The proliferation of the Internet has affected the business model of almost all semiconductor and VLSI CAD companies that rely on intellectual property (IP) as their main source of revenues. The fact that IP has become more accessible and easily transferable, has influenced the emergence of copyright infringement as one of the most common obstructions to e-commerce of IP. In this paper, we propose a generic forensic engineering technique that addresses a number of copyright infringement scenarios. Given a solution SP to a particular optimization problem instance P and a finite set of algorithms A applicable to P, the goal is to identify with a certain degree of confidence the algorithm Ai which has been applied to P in order to obtain SP. We have applied forensic analysis principles to two problem instances commonly encountered in VLSI CAD: graph coloring and boolean satisfiability. We have demonstrated that solutions produced by strategically different algorithms can be associated with their corresponding algorithms with high accuracy.

REFERENCES

• Bak98: B.S. Baker and U. Manber. Deducing similarities in Java sources from bytecodes. USENIX Technical Conference, pp.179-90, 1998.
• Bay96: R.J. Bayardo and R. Schrag. Using CSP look-back techniques to solve exceptionally hard SAT instances. Principles and Practice of Constraint Programming, pp.46-60, 1996.
• Beh98: Brian C. Behrens , Reuven R. Levary, Practical legal aspects of software reverse engineering, Communications of the ACM, v.41 n.2, p.27-29, Feb. 1998 [doi>10.1145/269012.269017]
• Bre79: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• Bri95: Sergey Brin , James Davis , Héctor García-Molina, Copy detection mechanisms for digital documents, ACM SIGMOD Record, v.24 n.2, p.398-409, May 1995
• Bry95: Randal E. Bryant, Binary decision diagrams and beyond: enabling technologies for formal verification, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.236-243, November 05-09, 1995, San Jose, California, United States
• Cha99: E. Charbon and I. Torunoglu. Watermarking layout topologies. ASP-DAC, pp.213-16, 1999.
• Col99: Christian Collberg , Clark Thomborson, Software watermarking: models and dynamic embeddings, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-324, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292569]
• Cra93: J.M. Crawford. Solving Satisfiability Problems Using a Combination of Systematic and Local Search. Second DIMACS Challenge, 1993.
• Cul99: http://www.cs.ualberta.ca/ joe
• DeG89: M. DeGroot. Probability and statistics. Addison-Wesley, Reading, 1989.
• EET99: http://eet.com/news/O7/O46news/evidence.html
• GCW99: Gray Cary Ware 8z Freidenrich LLP. http://www.gcwf.com/firm/groups/tein/case.html
• Gar79: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Goe95: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• Kah98: Andrew B. Kahng , Stefanus Mantik , Igor L. Markov , Miodrag Potkonjak , Paul Tucker , Huijuan Wang , Gregory Wolfe, Robust IP watermarking methodologies for physical design, Proceedings of the 35th annual conference on Design automation, p.782-787, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277241]
• Kam93: A.P. Kamath, et al. An interior point approach to Boolean vector function synthesis. Midwest Symposium on Circuits and Systems, pp.185-9, 1993.
• Kir98: Darko Kirovski , Miodrag Potkonjak, Efficient coloring of a large spectrum of graphs, Proceedings of the 35th annual conference on Design automation, p.427-432, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277165]
• Lei79: F.T. Leighton. A Graph Coloring Algorithm for Large Scheduling Algorithms. Journal of Res. Natl. Bur. Standards, vol.84, pp.489-506, 1979.
• McG95: D.F. McGahn. Copyright infringement of protected computer software: an analytical method to determine substantial similarity. Rutgers Computer 8z Technology Law Journal, vol.21, (no.l), pp.88-142, 1995.
• Oli99: 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]
• Qu98: 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]
• Sel92: B. Selman, H.J. Levesque, and D. Mitchell. A New Method for Solving Hard Satisfiability Problems. National Conference on Artificial Intelligence, 1992.
• Sel93: B. Selman and H. Kautz. Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems. International Conference on Artificial Intelligence, 1993.
• Sel93a: B. Selman, H. Kautz, and B. Cohen. Local Search Strategies for Satisfiability Testing. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993.
• Sel95: B. Selman. Stochastic search and phase transitions: AI meets physics. IJCAI, pp.998-1002, vol.1, 1995.
• Sil99: João P. Marques-Silva , Karem A. Sakallah, GRASP: A Search Algorithm for Propositional Satisfiability, IEEE Transactions on Computers, v.48 n.5, p.506-521, May 1999 [doi>10.1109/12.769433]
• Tae98: http://www.taeus.com/
• Tsu93: Y. Tsuji and A. Van Gelder. Incomplete thoughts about incomplete satisfiability procedures. Proceedings of the 2nd DIMACS Challenge, 1993.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

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