Robust IP Watermarking Methodologies for Physical DesignAndrew B. Kahng, Stefanus Mantik, Igor L. Markov, Miodrag Potkonjak,Paul Tucker†, Huijuan Wang and Gregory WolfeUCLA Computer Science Dept., Los Angeles, CA 90095-1596†UCSD Computer Science & Engineering Dept., La Jolla, CA 92093-0114AbstractIncreasingly popular reuse-based design paradigms create a press-ing need for authorship enforcement techniques that protect the in-tellectual property rights of designers. We develop the first intel-lectual property protection protocols for embedding design water-marks at the physical design level. We demonstrate that these pro-tocols are transparent with respect to existing industrial tools anddesign flows, and that they can embed watermarks into real-worldindustrial designs with very low implementation overhead (as mea-sured by such standard metrics as wirelength, layout area, numberof vias, routing congestion and CPU time). On several industrialtest cases, we obtain extremely strong, tamper-resistant proofs ofauthorship for placement and routing solutions.1 IntroductionDue to rapidly growing device counts, shortened design cycle timesand a compounding “design productivity shortfall” [9], core-baseddesign and software reuse strategies are widely believed to be theonly viable implementation alternatives for the next level of inte-grated circuits and their system integration. As a result, develop-ment of intellectual property protection (IPP) techniques and toolshas emerged as a very prominent open research topic. In this work,we develop the first protocols for IPP at the physical design level,using the concept of constraint-based watermarking.As defined in [5], a design watermark is an invisible (i.e., im-perceptible to human or machine analysis) identification code thatis permanently embedded as an integral part within a design. Vari-ous criteria for a given watermarking-based IPPtechnique, as deter-mined by a leading industry organization, include [12]: (i) mainte-nance of functional correctness, (ii) transparency to existing designflows; (iii) minimal overhead cost; (iv) enforceability; (v) flexibil-ity in providing a spectrom of protection levels; (vi) persistency;(vii) invisibility; and (viii) proportional component protection. In[5], we list other watermarking desiderata, and describe a canonicalapproach to watermarking-based IPP where additional constraintsencoding the IP author’s signature are added into a given designoptimization instance. The solution of the optimization instance,in satisfying these constraints (which would be unlikely in a ran-dom solution to the original instance), implicitly contains a proofof authorship. The approach described in [5] is transparent to ex-isting design flows in that it relies on preprocessing (of inputs) orWork by M. Potkonjak and G. Wolfe supported in part by DARPA under grantN66001-97-2-8901. Work by A. B. Kahng, S. Mantik, I. L. Markov, P. Tucker and H.Wang supported by a grant from Cadence Design Systems, Inc.postprocessing (of solutions) with respect to any given design opti-mization.We center on the physical design phase for several reasons.Physical design is traditionally viewed as a “difficult” do-main, where even a small percentage variation in solutionquality can make or break a design, and where high-qualitysolutions are known to have strong structural resemblanceto each other [4]. Devising a watermarking technique thatcan make a solution “unique”, without compromising solu-tion quality, is quite challenging in such a domain.With deep-submicron technology, many performance con-straints (e.g., budgeted edge delays consistent with path tim-ing bounds) cannot be considered satisfied until they are satis-fied in the physical design. Thus, for example, it is disingenu-ous to “watermark” a design by constraining timing budgets,without verifying that such constraints are satisfied after phys-ical design.Other trends – IP reuse methodologies, higher perceived valu-ation of “hard IP”, increasing availability of multiple foundrysources, difficulty of performance validation before physicaldesign, changing handoff models, etc. – all point to physi-cal design as an appropriate juncture in the design cycle forwatermarking.Contributions of Our WorkTo our knowledge, this work gives the first solution for IPP at thephysical design level. For placement, we propose a postprocessingflow that encodes a signature as specified parity (i.e., odd- or even-index) of the cell row within which particular standard cells must beplaced. For routing, we propose a preprocessing flow that encodesa signature as upper bounds on the wrong-way wiring used to routeparticular signal nets.1Using real industrial design examples andcommercial layout tools, we demonstrate the effectiveness of boththe preprocessing- and the postprocessing-based watermarking. Inparticular, strong signatures are achieved without compromisingany of the standard metrics for solution quality (routability, wire-length, number of vias, CPU time, etc.). We also demonstrate thatthese signatures are tamper-resistant. We conclude that address-ing IP protection at a lower level of abstraction has an advantage:designs inherently have orders of magnitude more components, al-lowing significantly stronger proofs of authorship as well as loweroverhead. We also conclude that the postprocessing approach isnot only feasible, but indeed quite attractive for several reasons: (i)it enables watermarking of already existing designs; (ii) it enablesdirect calculationg of the hardware overhead incurred by IPP;2and(iii) is may be likelier to find acceptance among designers and man-agers, since the complete design process is not altered in any way.1The particular constraints used to encode the watermark affect the strength of theauthorship proof as well as metrics of the layout solution. Devising constraint typessuch that strong signatures can be achieved transparently using existing flows and toolsis, in our experience, a very nontrivial task.2When preprocessing is used, two designs (one without additional signature con-straints, and one with) must be realized in order to determine the hardware overheadincurred by IPP.2 Related WorkRelated work in artifact watermarking and cryptography is re-viewed in [5].3We therefore focus our survey of related conceptswithin the physical design realm.No previous work in the literature deals with watermarking ofphysical design