一种基于BP神经网络的代码相似性检测方法_熊浩

37320103ComputerScienceVol.37No.3Mar2010:2009204208:2009207216863(2007AA010302,2008AA012114),(60703057,60573084)(1985-),,,,E2mail:[e-mail];(1964-),,,,;,,;(1974-),,,;(1963-),,,,,BP1,21221(100191)1(100083)2(BP)7,,,,,BP,TP311ACodeSimilarityDetectionApproachBasedonBack2propagationNeuralNetworkXIONGHao1,2YANHai2hua1HUANGYong2gang2GUOTao2LIZhou2jun1(SchoolofComputerScienceandEngineering,BeihangUniversity,Beijing100191,China)1(ChinaInformationTechnologySecurityEvaluationCenter,Beijing100083,China)2AbstractItisveryimportanttofindplagiarizedprogramsinthefieldofcomputerscienceeducation.Traditionalmetho2dsforprogramsimilarityuseattributecountingorstructureinformationtodetectplagiarism.Thispaperpresentedaprogramsimilaritydetectionapproachbasedonbackpropagation(BPalgorithm)multi2layerfeed2forwardneuralnet2works.Weextractedsevencomparedfeaturesofthecodeastheinputoftheneuralnetwork,andobtainedtheprogramsimilaritythroughthenetworkcalculation.Comparingtheresultwiththethresholdvalue,wecanfindallgroupsofsimi2larprograms.Experimentalresultsshowthatourmethodiseffective.KeywordsPlagiarism,Similaritydetection,BPneuralnetwork,Comparedfeature,[1],[2,3],,,,BerkeleyMOSS[9]KarlsruheJPlag[10],,,,,,,,,BP:,,,7,;BP,BP,:,,JPlag,11.1Parker[4],,FaidhiRob2inson[5]7,Jones[6],10,951[15217],,,3:1):2):3):,1)2),,Faidhi7Jones10,,,1.240,,,[4]VERCO[7],,,111YAP3[8]RKR2GST2MOSS[9]StringMatching3JPLAG[10]GreedyStringTiling4Plague[11]LCSalgorithm5GPLAG[12]Graphisomorphismalgorithm6Bandit[13]LCSalgorithm7SIM[14]LocalAlignment,,2BP2.1BP[18],(BP),,11BP2.2BP,;,22BP,,7,,72.2.1[17],,,,,,,,OFFSET,FUNCTIONCONSTANTP1,P2,F(P1)F(P2)P1,P2,Sim(P1,P2),Sim(P1,P2)=(F(P1)F(P2))/(F(P1)F(P2))(1)(1),,,,,Sim(P1,P2)=matchmatch+(f(P1)-P1_match)+(f(P2)-P2_match)(2)(2)(1)f,P1_matchP1P2,matchP1_matchP2_match,(1)(2),2.2.2,,,,3,,061,,,,(),CALLFUNCTION(),,CALLFUNCTION3,(LCSalgorithm)[19]X=x1,x2,,xnY=y1,y2,,ym,C[i,j],m3n,LCS:1m=length[X],n=length[Y]2fori=1tom3C[i,0]=04forj=1ton5C[0,j]=06fori=1tom7forj=1ton8ifxi=yj9C[i,j]=C[i-1,j-1]+110elseifC[i-1,j]C[i,j-1]11C[i,j]=C[i-1,j]12elseC[i,j]=C[i,j-1]13returnC,C[m-1,n-1],Sim(P1,P2)=C[m-1][n-1]/min_line(3)Sim(P1,P2)=23C[m-1,n-1]/(m+n)(4)min_linemn(3)(4)[16],(3)(4),2.2.3,,3,74:1)2)3)4)5)6)7):1)2)3)4)7)2),/33/,3)4),,[4],,51)2)3)4)5)C,for,do/whilewhileif,switch/case,if/else?:P1,P2,,Pn,Px3:CS=a1x,a2x,,a7x,RS=b1x,b2x,,b4x,SC=c1x,c2x,,c5xPiPj,D(Pi,Pj)=7u=1(aui-auj)2(5),(021),CSa1x,a2x,,a7x=a1xnt=1a1t,a2xnt=1a2t,,a7xnt=1a7t(5)01,01,D(Pi,Pj)=7u=1(aui-auj)2/7(6)(6),16101PiPjSim(Pi,Pj)=1-D(Pi,Pj)(7),(6)(7)327BP,,2BP(SCD1)(1)(SCD2)(2)(SLC1)(3)(SLC2)(4)(SCS)(6)(7)(SRS)(6)(7)(SSC)(6)(7)3,,,,,BP3.13.1.13,,,,100,100,,4950,0()1()3.1.2GCCLinuxShellGCCGCCMatlab6.x,,7150,,,:10000;0.05;0.9BP,,L2M[21]3.1.34X,YBP0.0031,,4,,,,,,,,44,0.5,0.59,0.599.818%(/)0.53.1.4[20],73,,,3SCD10.14893SCD20.13105SLC10.13304SLC20.17211SCS0.16572SRS0.12267SSC0.126763.2JPlag[10]BuaaSim261[17],BuaaSimJPlag,3.2.175,,3.13.2.275(0-74)2775,50.5,98,6672(527)72,,54,BPBuaaSimJPlag,,5,6,15,17,51,67,:1);2);3)4BuaaSimBPJPlag{32,45},{52,58,68}BuaaSim{32,45},{35,42},{56,62},{70,72},{52,58,60,68},{4,12,19}BP{32,45},{35,42},{5,6},{15,16}{52,58,60,68},{4,12,19},{15,24}{17,56,62},{67,70,72},{24,51}{15,59},{15,63},{51,59},{51,63},{2,51}BuaaSim2)1)3),15514,,,7,4,BP,,JPlag,JPlagBuaaSim,JPlag,,BP,,,BP,,:,,,SVM,[1]McCabeD.LevelsofCheatingandPlagiarismRemainHigh[C/OL].CenterforAcademicIntegrity,DukeUniversity,2005.ht2tp://academicintegrity.org/[2]BullJ,CollinsC,CoughlinE,etal.TechnicalReviewofPlagia2rismDetectionSoftwareReport[C/OL].[3]SheardJ,DickM,MarkhamS,etal.Cheatingandplagiarism:perceptionsandpracticesoffirstyearITstudents[C]The7thAnnualJointConferenceonInnovationandTechnologyinCom2puterScienceEducation.Aarhus,Denmark,2002:1832187[4]ParkerA,HamblemJO.Computeralgorithmsforplagiarismdetection[J].IEEETransactionsonEducation,1989,32(2):94299[5]FaidhiJAW,RobinsonSK.AnEmpiricalApproachforDetec2tionProgramSimilarityandPlagiarismwithinaUniversityPro2grammingEnvironment[J].ComputersandEducation,1987,11(1):11219[6]JonesEL.Metricsbasedplagiarismmonitoring[C]The6thAnnualCSSCNortheasternConference.Middlebury,VT,2001[7]VercoKL,WiseMJ.Softwarefordetectingsuspectedplagia2rism:comparingstructureandattribute2countingsystems[C]Proceedingsofthe1stAustralianConferenceonComputerScien2ceEducation.1996:325[8]WISEMJ.YAP3:ImprovedDetectionofsimilaritiesincomputerprogramandotherTexts[C]ACMSIGCSE.1996:1302134[9]SchleimerS,WilkersonD,AikenA.Winnowing:LocalAlgo2rithmsforDocumentFingerprinting[C]ProceedingsoftheACMSIGMODInternationalConferenceonManagementofDa2ta.June2003:76285[10]PrecheltL,MalpohlG,PhilippsenM.FindingplagiarismsamongasetofprogramswithJPlag[J].JournalofUniversalComputerScience,2002,8(11):101621038[11]WhaleG.Plague:PlagiarismDetectionUsingProgramStructure361[R].Dept.ofComputerScienceTechnicalReport8805.Univer2sityofNSW,Kensington,Australasian,1988[12]LiuChao,ChenChen,HanJia2wei,etal.GPLAG:DetectionofSoftwarePlagiarismbyProgramDependenceGraphAnalysis[C]A