Encoding numbers into reducible permutation graphs using heap-ordered trees

ABSTRACT

Information hiding is widely used in almost all intelligence and security software systems as a standard technology to prevent piracy and copyright infringement. This technology mainly involves the idea of digital watermarking where a unique identifier (or, watermark number) is embedded into software, image, audio, or video data through the introduction of errors not detectable by human perception. In software watermarking, the proposed graph theoretic methods usually encode watermark numbers as graphs whose structure resembles that of real program graphs. In this paper, in light of our recently published algorithms which encode a watermark number w as a self-inverting permutation, we present an efficient encoding method, along with its corresponding decoding one, which embeds a self-inverting permutation π* into reducible permutation graphs F[π*]. More precisely, we present an encoding algorithm which embeds the permutation π* into F[π*] by first computing the heap-ordered tree of π* (i.e., a rooted binary tree having specific node-value and child-parent properties) using the lattice representation of π* and then, based on the heap node-value properties, producing a reducible permutation graph F[π*]. Moreover, we exploit the max-heap and min-heap representation tree of permutation π* and show that we can efficiently encode the same watermark w into two different reducible permutation graphs F₁[π*] and F₂[π*]. In general, such a property increases the safety performance of a watermarking system against attacks since it can embed multiple copies of the same watermark value w into a digital object.

References

1. G. Arboit. A method for watermarking java programs via opaque predicates. In Proc. 5th International Conference on Electronic Commerce Research (ICECR-5), 2002.
2. M. Chroni and S. Nikolopoulos. Encoding watermark integers as self-inverting permutations. In Proc. Int'l Conference on Computer Systems and Technologies (CompSysTech'10), volume ACM ICPS 471, pages 125--130, 2010.
3. M. Chroni and S. Nikolopoulos. Encoding watermark numbers as cographs using self-inverting permutations. In Proc. Int'l Conference on Computer Systems and Technologies (CompSysTech'11), volume ACM ICPS 578, pages 142--148, 2011.
4. M. Chroni and S. Nikolopoulos. An efficient graph codec system for software watermarking. In 36th IEEE Conference on Computers, Software, and Applications (COMPSAC'12), volume IEEE Proc., pages 595--600, 2012.
5. M. Chroni and S. Nikolopoulos. Multiple encoding of a watermark number into reducible permutation graphs using cotrees. In 13th Int'l Conference on Computer Systems and Technologies (CompSysTech'12), volume ACM, pages 118--125, 2012.
6. M. Chroni and S. Nikolopoulos. Design and evaluation of a graph codec system for software watermarking. In 2nd Int'l Conference on Data Management Technologies and Applications (DATA'13), volume SciTePress, pages 277--284, 2013.
7. C. Collberg, E. Carter, S. Debray, A. Huntwork, J. Kececioglu, C. Linn, and M. Stepp. Dynamic path-based software watermarking. In ACM Sigplan Notices, volume 39, pages 107--118, 2004.
8. C. Collberg, E. Carter, S. Kobourov, and C. Thomborson. Error-correcting graphs for software watermarking. In Proc. 29th Workshop on Graphs in Computer Science (WG'03), volume LNCS 2880, pages 156--167, 2003.
9. C. Collberg, A. Huntwork, E. Carter, G. Townsend, and M. Stepp. More on graph theoretic software watermarks: Implementation, analysis, and attacks. Information and Software Technology, 51:56--67, 2009.
10. C. Collberg and C. Thomborson. Software watermarking: models and dynamic embeddings. In Proc. 26th ACM SIGPLAN-SIGACT on Principles of Program. Languages (POPL'99), pages 311--324, 1999.
11. P. Cousot and R. Cousot. An abstract interpretation-based framework for software watermarking. In Proc. 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'04), pages 173--185, 2004.
12. D. Curran, N. Hurley, and M. Cinneide. Securing java through software watermarking. In Proc. Int'l Conference on Principles and Practice of Programming in Java (PPPJ'03), pages 145--148, 2003.
13. M. Hecht and J. Ullman. Flow graph reducibilit. SIAM J. Computing, 1:188--202, 1972.
14. A. Monden, H. Iida, K. Matsumoto, K. Inoue, and K. Torii. A practical method for watermarking java programs. In Proc. 24th Computer Software and Applications Conference (COMPSAC'00), pages 191--197, 2000.
15. J. Nagra and C. Thomborson. Threading software watermarks. In Proc. 6th Int'l Workshop on Information Hiding (IH'04), volume LNCS 3200, pages 208--223, 2004.
16. G. Qu and M. Potkonjak. Analysis of watermarking techniques for graph coloring problem. In Proc. IEEE/ACM Int'l Conference on Computer-aided Design (ICCAD'98), volume ACM Press, pages 190--193, 1998.
17. R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison Wesley, 1996.
18. J. Stern, G. Hachez, F. Koeune, and J. Quisquater. Robust object watermarking: Application to code. In Proc. 3rd Int'l Workshop on Information Hiding (IH'99), volume LNCS 1768, pages 368--378, 1999.
19. R. Venkatesan, V. Vazirani, and S. Sinha. A graph theoretic approach to software watermarking. In Proc. 4th Int'l Workshop on Information Hiding (IH'01), volume LNCS 2137, pages 157--168, 2001.

Index Terms

• Information systems

  • Information storage systems

    • Record storage systems

      • Directory structures

        • B-trees

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Permutations and combinations

    • Graph theory

      • Graph algorithms

      • Trees

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Software architectures