Research And Application Of Dynamic Graph Watermarking Algorithm

The Internet is developing fast, which benefits the spreading ofsoftware products significantly. However, the side effects of this spreadingarouse people's attention to them.The problem of software piracy isbecoming more and more serious. Therefore, how to take measures toprotect the intellectual properties of digital products has becoming thehotspot of all kinds of research areas. In the early time, people adopted theencryption technique, which could only control the users to access the datawhich have no relation to software itself, so once the method of encryptingis interpreted, all the data could be easily changed, copied or speeded.Inorder to settle this problem, people have proposed a new measure ofintellectualpropertyprotection——softwarewatermarkingtechnique.The software watermarking technique is one kind of research subjectdeveloped to settle the problem of software intellectual propertyauthentication. Some special secret information is embedded into thesoftware programs during the process of watermarking. If the technique ofsoftware watermarking is developing adequately, we can establish one kindof runtime checking and copying checking mechanisms effectivelymaking use to the excellent software watermarking checking mechanism,then the unlawful spreading and running of software are prohibited, whichreinforce the technique foundation of resolving the problem of softwarepiratingintheend.The dynamic graph watermarking is a new kind of dynamic softwarewatermarking technique, which establish a graph structure at runtime, andthis graph represents the watermarking number.For the difficulty ofanalyzing dynamic data, this technique has strong resistance against anyattacking. So the main factor which has effect to the dynamic graphwatermarking technique is whether we can find out an excellent graphstructure to represent the watermarking number. This thesis emphasises onthe analysis of performance and structure improvement of the dynamicgraphwatermarking. Thisthesisisdividedintothreeparts:First,wedoresearchandanalyzethe current dynamic graph watermarking topology structure, for example,the Radix-k, PPCT and intensified PPCT(IPPCT), we also point out theadvantages and disadvantages of each topology structure, analyze andcompare the rate of data embedding of each structure. Second, this thesisimproves the structure of intensified PPCT, proposes one kind of newdynamic graph watermarking structure, two-dimension IPPCT, fetches outthe constitution formula and numerical value of the rate of data embeddingof two-dimension PPCT.We also prove that the two-dimension IPPCThavea lot of advantages, such as high rate of data embedding,high level ofrobustness and the ability of establishing watermarking storehouse to resistcollusion attacks, and we got the conclusion that the data embedding rate of2-dimension IPPCT is higher than normal IPPCT. Then we propose onestructure model of multi-dimension IPPCT, fetch out the constitutionformula and data embedding rate of calculated formula and prove that thedata embedding rate of multiple-dimension will increase as the dimensionincreasing on condition that number of each structure have the same leaves.The data embedding rate of multiple-dimension IPPCT would approachmaximum with the increasing of the dimension, the thesis point out themaximumintheend.Thisthesisfetchouttheconceptof DataRate,HArea,f max, f min. The alter of DataRate will have great impact on characteristicofmultiple-dimensionIPPCT,includingthedataembeddingrate,robustandresilience, we also fetch out the normal principle of selectingmultiple-dimensionIPPCTstructures.Thisthesis alsopointouttheideathatif the value of DataRate belongs to the area of HArea, themultiple-dimension IPPCT will have a good performance, otherwise, theperformanceofitisnotacceptable.This thesis design and implement one kind of dynamic graphwatermarking system——n_IPPCT_Tester. n_IPPCT_Tester adoptsmultiple-dimension IPPCT as its dynamic graph structure, the functions areasfollowing:(1) Watermarking generation.The prime number P and Q must be inputted by the tester, so the watermarking number P×Q is confirmed.The tester should also input the index number of Catalan, the dimensionn and the number of leaves, so the structure of watermarking graph isconfirmed.(2) Watermarking embedding. The tester must select the location of theembeddingandthenexecutetheprocessofit.(3) Watermarking retrieval. n_IPPCT_Tester will analyze the stack ofcomputersystematruntime.(4) Watermarking performance analysis. n_IPPCT_Tester will analysis theresources employed and rate of data embedding of themultiple-dimensionIPPCTandpresenttheresultsattheGUI.We do experiment at n_IPPCT_Tester. The result of the experimentindicates that the data embedding rate of two-dimension IPPCT is high thannormal IPPCT on condition that they have the same leaf numbers. Thetwo-dimension IPPCT will consume less resource if theyrepresent the samewatermarkingnumber.This trendwill becomemoreclearlyifthis number isbig.Atlast,the author made a conclusion of this thesis and didanexpectation for the future work.