A randomized graph-based scheme for software watermarking

• Lucila Maria Souza Bento UFRJ / INMETRO
• Davidson Rodrigo Boccardo INMETRO
• Raphael Carlos Santos Machado INMETRO
• Vinícius Gusmão Pereira de Sá UFRJ
• Jayme Luiz Szwarcfiter UFRJ / INMETRO

DOI: https://doi.org/10.5753/sbseg.2014.20119

Abstract

The insertion of watermarks into proprietary objects is a well-known means of discouraging piracy. It works by embedding into the object some (often surreptitious) data meant to disclose the authorship/ownership of the object. Some promising graph-based watermarking schemes to protect the intellectual property of software have been suggested in the literature, and recent efforts have been endeavored to improve their resilience to attacks. Among the pursued attributes of software watermarking solutions is the one referred to as "diversity", which is the ability to encode the intended information in many distinct forms, making it harder for an attacker to find and remove it. We introduce a graph-based scheme which achieves a high level of diversity through randomization, while admitting an efficient, linear-time implementation nonetheless.

References

Arboit, G. (2002). A method for watermarking Java programs via opaque predicates. In Proc. Int. Conf. Electronic Commerce Research (ICECR-5).

Bento, L. M. d. S., Boccardo, D., Costa, R., Machado, R. M. S., Pereira de Sá, V. G., and Szwarcfiter, J. L. (2013a). Fingerprinting de software e aplicações à metrologia legal. In Proc. 10th International Congress on Electrical Metrology (SEMETRO’13).

Bento, L. M. S., Boccardo, D. R., Machado, R. C. S., Pereira de Sá, V. G. a. P., and Szwarcfiter, J. L. (2013b). Towards a provably resilient scheme for graph-based watermarking. In Proc. Workshop on Graph-Theoretic Concepts in Computer Science (WG’13), LNCS 8165, pages 50–63. Springer.

Chroni, M. and Nikolopoulos, S. D. (2012a). An efficient graph codec system for software watermarking. In 36th IEEE Conference on Computers, Software, and Applications (COMPSAC’12), pages 595–600. IEEE Proceedings, 36th edition.

Chroni, M. and Nikolopoulos, S. D. (2012b). An embedding graph-based model for software watermarking. In Proc. International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP’12), pages 261–264. IEEE.

Chroni, M. and Nikolopoulos, S. D. (2012c). Multiple encoding of a watermark number into reducible permutation graphs using cotrees. In CompSysTech, pages 118–125.

Collberg, C., Carter, E., Debray, S., Huntwork, A., Linn, C., and Stepp, M. (2004). Dynamic path-based software watermarking. In Proc. Conference on Programming Language Design and Implementation (SIGPLAN’04).

Collberg, C., Kobourov, S., Carter, E., and Thomborson, C. (2003). Error-correcting graphs for software watermarking. In Proc. 29th Workshop on Graph-Theoretic Concepts in Computer Science (WG’03), LNCS 2880, pages 156–167. Springer.

Collberg, C. and Nagra, J. (2009). Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection. Addison-Wesley Professional.

Collberg, C. and Thomborson, C. (1999). Software watermarking: Models and dynamic embeddings. In Proc. 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL’99, pages 311–324. ACM.

Cousot, P. and Cousot, R. (2004). An abstract interpretation-based framework for software watermarking. In Proc. Conference Record of the 31st Annual ACM SIGPLANSIGACT Symposium on Principles of Programming Languages, pages 173–185. ACM Press, New York, NY.

Davidson, R. and Myhrvold, N. (1996). Method and system for generating and auditing a signature for a computer program. US Patent 5,559,884.

Hamming, R. W. (1950). Error detecting and error correcting codes. Bell System Technical Journal, 29(2):147–160.

Mann, H. (1968). Error Correcting Codes. John Wiley and Sons.

Monden, A. and Inoue, K. (2000). A practical method for watermarking Java programs. In Proc. 24th Computer Software and Applications Conference, pages 191–197.

Nagra, J. and Thomborson, C. (2004). Threading software watermarks. In Proc. 6th International Workshop on Information Hiding, LNCS 3200, pages 208–233. Springer.

Purser, M. (1995). Introduction to Error-Correcting Codes. Artech House Inc.

Qu, G. and Potkonjak, M. (1998). Analysis of watermarking techniques for graph coloring problem. In ICCAD, pages 190–193.

Reed, I. S. and Solomon, G. (1960). Polynomial Codes Over Certain Finite Fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304.

Venkatesan, R., Vazirani, V. V., and Sinha, S. (2001). A graph theoretic approach to software watermarking. In Proc. 4th International Workshop on Information Hiding (IHW’01), pages 157–168. Springer.

Wicker, S. B. (1995). Error control systems for digital communication and storage. Prentice Hall.