Sharing And Encoding Algorithm Based On Tamper-resistant Software Watermarking

Software Watermarking is an important technology used to protect the software copyright,which can achieve the goal of identity authentication through embedding speciifc information ofthe copyright holder to the target program. According to the Software Watermarking embeddingtime, Software Watermarking can be divided into Dynamic Software Watermarking and StaticSoftware Watermarking, where Dynamic Graph Watermarking and Equation SoftwareWatermarking are two typical technologies respectively.The essential technologies of Software Watermarking involved Watermarking Sharingtechnology, Watermarking Encoding technology and Watermarking Tamper-prooifng technology,they inlfuence the Software Watermarking system performance evaluation indicators e.g. datarate, stealthiness and robustness. Revolved round the essential technologies of SoftwareWatermarking, this paper carried out research as follows:(1)Towardsthe issue of low data rate, high time complexity of encoding and decodingwatermarking graph and poor robustness in the traditional Dynamic Graph Watermarkingalgorithm, this paper proposed a Extended Public Planar Cubic Tree encoding structure namedEPPCT. This encoding structure added two pointer ifelds in each PPCT node for expressing thequaternary encoding coefficient, which reduced the time complexity of encoding and decodingwatermarking graph in the same space complexity and increased the watermarking data rate.Meanwhile, according to the pointer relationship of EPPCT node and the sequence number ofpreorder traversal, this paper proposed a tamper-prooifng schema based on Cyclic RedundancyCheck(CRC).This schema ifgured out the information code and the corresponding CRC code andthen inserted the decoding validation function generated by the CRC decoding function into theexecuting codes in the program, which increased the robustness of watermarking.(2)Towardsthe issue of granularity heterogeneity, high time complexity and independentencoding of sub-watermarking in watermarking sharing algorithm, this paper proposed awatermarking sharing algorithm based on m-n Variable Carrying Rule. This algorithm establishedthe corresponding relationship and transformation rule among integer number, m-n VariableNumber, Permutation Number and Reducible Permutation Graph (RPG) structure. When sharingthe watermarking, spitted the watermarking into several sub-watermarking presenetd by m-nVariable Carrying Number with the method of Remainder-Divided-/? algorithm, which increasedthe watermarking sharing eiffcient; When encoding the watermarking, ifrstly converted the m-nVariable Carrying Number to Permutation Number through a Perfect Hash Function based onlinear list, then encoded all the sub-watermarkings as a RPG structure in according with thePermutation Number, which avoided independent encoding of each sub-watermarking. (3) Towards the issue of low data and space utilization rate, poor robustness in EquationReordering Static Software Watermarking, this paper proposed a Equation Reordering algorithmbased on Perfect Variable Carrying Number. This algorithm searched the Securable SwappedEquation satisifed by certain conditions as Key Vector, converted the watermarking into PerfectVariable Carrying Number—a the special case of the Variable Carrying Number, by the methodof Remainder-Divided-/? algorithm, and then reordered the operators in the Key Vector through aPerfect Hash Function based on Cyclic Right Rotate, which improved the hiding and extractioneiffciency of the watermarking. This algorithm extended the number expressing range, increasedthe data rate of the Equation Reordering Static Software Watermarking algorithm, and can resistvarious Distortive Attack.