Marca d’água estruturada
Resumo
Uma marca d’água em artefato digital corresponde a uma informação de identificação embarcada naquele objeto de forma oculta, podendo ser usada para comprovar autoria/propriedade, com o objetivo de desencorajar a distribuição ilegal de software. Dentre as técnicas de marca d’água de software apresentadas na literatura, destacam-se os esquemas baseados em grafos, nos quais uma chave secreta é codificada e inserida no grafo de fluxo de controle do programa. Recentemente têm sido realizados diversos esforços para melhorar esses esquemas com relação à resiliência a ataques. Neste artigo, apresentamos um novo esquema de marca d’água baseado em grafos com duas características principais: nosso algoritmo de codificação emprega aleatoriedade; e, o que é mais importante, nossas marcas d’água estão em conformidade com códigos estruturados. A capacidade de codificar uma mesma chave de distintas formas e a ausência de subestruturas semelhantes a peculiares goto’s conferem maior diversidade e furtividade às nossas marcas d’água, tornando-as mais resilientes a ataques de subtração e distorção. Apresentamos também uma implementação em tempo linear.Referências
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.
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.
Publicado
06/11/2017
Como Citar
BENTO, Lucila Maria de Souza; BOCCARDO, Davidson Rodrigo; MACHADO, Raphael Carlos Santos; SÁ, Vinícius Gusmão Pereira de; SZWARCFITER, Jayme Luiz.
Marca d’água estruturada. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 17. , 2017, Brasília.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 388-399.
DOI: https://doi.org/10.5753/sbseg.2017.19514.
