Marca d’água estruturada

• Lucila Maria de Souza Bento Clavis Segurança da Informação
• Davidson Rodrigo Boccardo Clavis Segurança da Informação
• Raphael Carlos Santos Machado Inmetro / CEFET-RJ
• Vinícius Gusmão Pereira de Sá UFRJ
• Jayme Luiz Szwarcfiter UFRJ / IME

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

Abstract

A digital object watermark corresponds to embedded identification data which can be timely retrieved to reveal authorship/ownership, with aims at discouraging piracy. Software watermarking schemes based on immersing an encoded key into control flow graphs have been suggested in the literature. Considerable efforts have lately been put up into improving such schemes with respect resilience to attacks. We propose a novel graph-based watermarking scheme with two distinctive features: first, our encoding algorithm employs randomization; second, and more importantly, our watermarks conform to structured code. The ability to encode the key in distinct forms and the absence of awkward goto-like substructures lend our watermarks greater diversity and stealthiness, making them more resilient to subtraction and distortion attacks. A linear-time implementation is given.

References

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

Bento, L. M., Boccardo, D. R., Machado, R. C., de Sá, V. G. P., and Szwarcfiter, J. L. (2016). On the resilience of canonical reducible permutation graphs. Discrete Applied Mathematics (aceito para publicação).

Bento, L. M. S., Boccardo, D., Machado, R. C. S., Pereira de Sá, V. G., and Szwarcfiter, J. L. (2013). Towards a provably resilient scheme for graph-based watermarking. In Brandstädt, A., Jansen, K., and Reischuk, R., editors, Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers. Springer Berlin Heidelberg.

Bento, L. M. S., Boccardo, D. R., Machado, R., de Sá, V. G. P., and Szwarcfiter, J. L. (2014). A randomized graph-based scheme for software watermarking. In XIV Simpósio Brasileiro de Seguraça. Informação e de Sistemas Computacionais (SBSEG’ 14). SBC, Belo Horizonte, Brazil, pages 30–41.

Bento, L. M. S., Boccardo, D. R., Machado, R., de Sá, V. G. P., and Szwarcfiter, J. L. (2015). The graphs of structured programming. In 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, Istanbul, Turkey, May 26-28, 2015., pages 105–108.

Chroni, M. and Nikolopoulos, S. D. (2012a). An efficient graph codec system for software watermarking. In 2012 IEEE 36th Annual Computer Software and Applications Conference Workshops, pages 595–600.

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

Collberg, C., Carter, E., Debray, S., Huntwork, A., Kececioglu, J., Linn, C., and Stepp, M. (2004). Dynamic path-based software watermarking. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI ’04, pages 107–118, New York, NY, USA. ACM.

Collberg, C., Kobourov, S., Carter, E., and Thomborson, C. (2003). Error-correcting graphs for software watermarking. Lecture Notes in Computer Science, 2880:156–167.

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

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

Cousot, P. and Cousot, R. (2004). An abstract interpretation-based framework for software watermarking. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’04, pages 173–185, New York, NY, USA. ACM.

Dahl, O. J., Dijkstra, E.W., and Hoare, C. A. R., editors (1972). Structured Programming. Academic Press Ltd., London, UK, UK.

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

Dijkstra, E. W. (1968). Go-to statement considered harmful. Comm. ACM, 11:174–186.

Guruswami, V. (2005). List Decoding of Error-Correcting Codes: Winning Thesis of the 2002 ACM Doctoral Dissertation Competition (Lecture Notes in Computer Science). Springer-Verlag New York, Inc., Secaucus, NJ, USA.

Mann, H. B. (1968). Error correcting codes; proceedings of a symposium. Edited by Henry B. Mann. Wiley New York.

Monden, A., Iida, H., Matsumoto, K., Torii, K., and Inoue, K. (2000). A practical method for watermarking java programs. In 24th International Computer Software and Applications Conference (COMPSAC 2000), 25-28 October 2000, Taipei, Taiwan, pages 191–197.

Nagra, J. and Thomborson, C. D. (2004). Threading software watermarks. In Information Hiding, 6th International Workshop, IH 2004, Toronto, Canada, May 23-25, 2004, Revised Selected Papers, pages 208–223.

Purser, M. (1995). Introduction to error-correcting codes. Artech House.

Qu, G. and Potkonjak, M. (1998). Analysis of watermarking techniques for graph coloring problem. In Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design, ICCAD ’98, pages 190–193, New York, NY, USA. ACM.

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., and Sinha, S. (2001). A Graph Theoretic Approach to Software Watermarking, pages 157–168. Springer Berlin Heidelberg, Berlin, Heidelberg.

Zeng, Y., Liu, F., Luo, X., and Lian, S. (2012). Abstract interpretation-based semantic framework for software birthmark. Comput. Secur., 31(4):377–390.