Watermarking integer linear programming solutions

ABSTRACT

Linear programming (LP) in its many forms has proven to be an indispensable tool for expressing and solving optimization problems in numerous domains. We propose the first set of generic watermarking techniques for integer-LP (ILP). The proof of authorship by watermarking is achieved by introducing additional constraints to limit the solution space and can be used as effective means of intellectual property protection (IPP) and authentication. We classify and analyze the types of constraints in the ILP watermarking domain and show how ILP formulations provide more degrees of freedom for embedding signatures than other existing approaches. To demonstrate the effectiveness of the proposed ILP watermarking techniques, the generic discussion is further concretized using two examples, namely Satisfiability and Scheduling.

REFERENCES

• 1: 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.
• 2: A.G. Bors and I. Pitas. Image Watermarking Using DCT Domain Constraints. International Conference on Image Processing, Vol.3, pp.231--244, 1996.
• 3: Catherine H. Gebotys , Mohamed I. Elmasry, Simultaneous scheduling and allocation for cost constrained optimal architectural synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.2-7, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127609]
• 4: 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
• 5: Inki Hong , Miodrag Potkonjak, Behavioral synthesis techniques for intellectual property protection, Proceedings of the 36th ACM/IEEE conference on Design automation, p.849-854, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310085]
• 6: 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]
• 7: Darko Kirovski , Miodrag Potkonjak, Localized watermarking: methodology and application to operation scheduling, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.596-599, November 07-11, 1999, San Jose, California, United States
• 8: E.A. Lee, D.G. Messerschmitt. Synchronous Dataflow. Procs. of the IEEE, Vol.75, (no.9), pp.1235--45, 1987.
• 9: João P. Marques-Silva , Karem A. Sakallah, Boolean satisfiability in electronic design automation, Proceedings of the 37th conference on Design automation, p.675-680, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337611]
• 10: Seapahn Meguerdichian , Miodrag Potkonjak, Watermarking while preserving the critical path, Proceedings of the 37th conference on Design automation, p.108-111, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337328]
• 11: P.G. Paulin and J.P. Knight. Force-Directed Scheduling For The Behavioral Synthesis Of ASICs. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol.8, pp.661--679, 1989.
• 12: Gang Qu , Jennifer L. Wong , Miodrag Potkonjak, Optimization-intensive watermarking techniques for decision problems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.33-36, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309860]
• 13: Gang Qu , Jennifer L. Wong , Miodrag Potkonjak, Fair watermarking techniques, Proceedings of the 2000 conference on Asia South Pacific design automation, p.55-60, January 2000, Yokohama, Japan [doi>10.1145/368434.368512]
• 14: John A. StankovicThis work was done while the , Marco Spuri , Marco Di Natale , Giorgio C. Buttazzo, Implications of Classical Scheduling Results for Real-Time Systems, Computer, v.28 n.6, p.16-25, June 1995 [doi>10.1109/2.386982]
• 15: J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Economics, Legal Aspects, Theory

Keywords:
digital watermarking, intellectual property protection