«JAVA» GRՐԱԳՐԱՎՈՐՈ ԼԵUՎԻ ԿՈԴ ԿԼՈՆՆԵՐԻ ՓՆՏՐՈՒՄ - EMՐԱԳՐԱՅԻՆ ONՐԱԳՐԻ ՀԻՄՆԱՎՈՐՎԱ Սեմալիստական ​​հետազոտություններ:   Րագրավորողը կարող է մի քանի անգամ օգտագործել ծրագրի նույն մասը ՝ որոշ չափով փոփոխելով այն:  Կոդի պատճենումը դրա օգտագործմամբ կարող է հանգեցնել իմաստային սխալների:  Օրինակ, մշակողը կարող է մոռանալ վերանվանել ծածկագրի պատճենված մասում որոշ փոփոխականներ, ինչը սխալ կհանգեցնի:   Կոդերի հատվածների վերաօգտագործումը տարածված է խոշոր ծրագրային համակարգերում:   Րագիրը, որտեղ կան բազմաթիվ կլոններ, հավանաբար շատ սխալներ է պարունակելու ՝ ունենալու է ցածր որակ:   Տարբեր ուսումնասիրությունների համաձայն [1, 2] ծրագրի 20% -ը կարող է լինել կլոն:   Կոդի կլոնների որոնման գործիքները շատ օգտագործումներ ունեն ● Կոդի որակի վերլուծություն ● Հեղինակային իրավունքի խախտման դեպքերի հայտնաբերում Վիրուսի հայտնաբերում ● Սխալի հայտնաբերում Այս հոդվածը ցույց կտա, թե ինչպես կատարել կոդերի կլոնավորում Java ծրագրավորման լեզվի համար:  Առաջին մասը ներկայացնում է ծրագրի կախվածության գծապատկերը (PDG):   Երկրորդ մասում վերլուծվում են PDG- ները ՝ կոդային կլոններ փնտրելու համար:   Նոր ալգորիթմը օգտագործվում է PDG- ից ծառ ստանալու համար `երկու ծառերի առավելագույն իզոմորֆ ծառերը գտնելու համար:   Ալգորիթմը թույլ է տալիս վերլուծել աղբյուրի ծածկագրի միլիոնավոր գծեր: Կոդի կլոնի տեսակները:  Կոդային կլոնների 3 հիմնական տեսակ կա. Առաջին տիպի կլոնները ծածկագրի այն մասերն են, որոնք կարող են տարբերվել միայն տարածություններով և մեկնաբանություններով (T1):  Երկրորդ տիպի կլոնները ծածկագրի այն մասերն են, որոնք կարելի է տարբերակել ըստ տարածությունների, մեկնաբանությունների, փոփոխական անունների, դրանց տեսակների և արժեքների (T2):   Երրորդ տեսակի կլոնները ծածկագրերի հատվածներն են, որոնք կարելի է տարբերակել տարածություններով, մեկնաբանություններով, փոփոխական անուններով, դրանց տեսակներով և արժեքներով, քանի որ ծածկագրի որոշ տողեր կարող են ավելացվել կամ ջնջվել (T3) [3] (Նկար ․ 1): 4  անվավեր sumProd (int5:  ﬂ վարսակի գումար = 0,0; 6  վարսակի արտադրության ժամանակ = 1.0; 7  համար (int i = 1; 8.  գումար = գումար + ես; 9  prod = prod * i; 10  foo (sum, prod); 11  } 12  Ծ տող ․ 1 Կլոնների երեք տեսակի կլոնների որոնման մոտեցումների օրինակներ   Կոդային կլոնների որոնման համար օգտագործվում են տարբեր մոտեցումներ:  Յուրաքանչյուր մոտեցում ունի կլոնների հատուկ տեսակներ գտնելու իր առավելություններն ու թերությունները:   Բոլոր մոտեցումների դեպքում հիմնական պահանջը գտնված կլոնների ճիշտությունն է:  Կոդային կլոններ գտնելու 5 հիմնական մոտեցում կա Տեքստային բառարանային շարահյուսություն, որը հիմնված է իմաստային մետրիկայի վրա 1. Տեքստային մոտեցում:   Այս մոտեցման վրա հիմնված ալգորիթմները հիմնականում պարզեցնում են մի քանի տող, ապա համեմատում հեշերը:   Եթե ​​հեշները համընկնում են, ալգորիթմը նրանց կլոն է համարում:  Որոշ ալգորիթմներ կարող են գտնել նմանատիպ ֆայլեր:   Այդ դեպքում որոշ տողերի հաջորդականություն է վերցվում ստուգում: Նրանց համար հաշվարկվում է չեկի գումար:   Հետո, ֆայլերի փոխարեն, այդ գումարները համեմատվում են:   Համընկնման դեպքում ֆայլերը համարվում են կլոններ:   Այս մոտեցման թերությունն այն է, որ այն գտնում է միայն (T1) տիպի կլոններ:   Նման ալգորիթմների բարդությունը քառակուսի հեշերի քանակի նկատմամբ: 2. Բառաբանական մոտեցում:  Այս մոտեցման մեջ ծածկագիրը թարգմանվում է նշանների հաջորդականության ՝ օգտագործելով բառարանային անալիզատոր, որից հետո ալգորիթմը որոնում է խորհրդանիշների համապատասխանող հաջորդականություններ:   Այս մոտեցմամբ հնարավոր է գտնել (T1) և (T2) տիպի կլոններ: Ամենավատ դեպքում նման ալգորիթմների բարդությունը քառակուսային է ՝ կախված նշանների քանակից, բայց գործնականում դրանք բավականին արագ են գործում: 3. շարահյուսական մոտեցում:   Այս մոտեցումը հիմնված է AST (abstractsyntax ծառ) ծառերի վրա:   Կլոնները համարվում են ՀՍՏ ծառի իզոմորֆ ենթատեսակներ:   Տարբեր ալգորիթմներ օգտագործվում են իզոմորֆ ենթատառեր որոնելու համար Երկու ծառերի մեջ փնտրվում է ամենամեծ ընդհանուր ենթատեսակը:  Երկու ծառերի համար էլ կառուցվում են ածանցներ, որոնց վրա փնտրվում են կլոններ:  Երկու ծառերի ենթածառերի համար կառուցվում են բնութագրական վեկտորներ, որոնք համեմատվում են [8]: Նման ալգորիթմների բարդությունը տատանվում է գծայինից քառակուսայինից մինչև ՀՍՏ ծառի գագաթների քանակը:   Դա կախված է քննարկվող ծառի չափից:   Այս մոտեցման վրա հիմնված մեթոդները գտնում են բոլոր տեսակի կլոնները: 4. Մետրիկների վրա հիմնված մոտեցում:   Կոդի կտորների համար հաշվարկվում են տարբեր չափումներ, ապա համեմատվում են ստացված չափանիշները:   Ընդհանուր առմամբ հաշվարկվում են ՀՍՏ ծառերի, ծրագրերի կախվածության գծապատկերների կամ տվյալների հոսքի գծապատկերների չափորոշիչները:   Այսինքն ՝ ՀՍՏ ծառը, ծրագրի կախվածության գծապատկերը կամ տվյալների հոսքի գծապատկերը ստացվում են սկզբնական ծածկագրից, նրանց համար սահմանվում է էկոդային միավոր, ապա հաշվվում են չափանիշները յուրաքանչյուր կոդային միավորի համար:   Չափանիշները հաշվարկվում են զույգերով:   Որպես կանոն, այս մոտեցման մեթոդներն ավելի արագ են աշխատում, քան ՀՍՏ ծառերի, ծրագրի կախվածության գծապատկերի (PDG) տվյալների հոսքի գծապատկերի վրա հիմնված ալգորիթմները, բայց ունեն ավելի քիչ ճշգրտություն:  Նման ալգորիթմների բարդությունը տատանվում է գծայինից քառակուսային, կախված ԱՍՏ ծառի գագաթների քանակից կամ ծրագրի կախվածության գծապատկերի գագաթներից:   Այս մոտեցման վրա հիմնված մեթոդները գտնում են բոլոր տեսակի կլոնները: 5. Իմաստային մոտեցում:  Այս մոտեցումը հիմնված է ծրագրի կախվածության գծապատկերի (PDG) վրա:   Այս մոտեցման վրա հիմնված ալգորիթմը որոնում է իզոմորֆ ենթակետեր [10, 11]: Նման ալգորիթմների բարդությունը կարող է ցուցիչ լինել:  Նման մեթոդների ճշգրտությունը բարձր է `համեմատած այլ մոտեցումների հետ, բայց արագությունը զգալիորեն ցածր է:   Այս մոտեցման վրա հիմնված մեթոդները գտնում են բոլոր տեսակի կլոնները: Մոտեցումների համեմատություն:   Բառաբանական և տեքստային մոտեցումները չեն գտնում բոլոր տեսակի կլոնները:  Այլ մեթոդներով հայտնաբերվում են կլոնների բոլոր երեք տեսակները, բայց մետրային վրա հիմնված մոտեցումների ճշգրտությունը ցածր է:  PDG- ի վրա հիմնված ալգորիթմները հիմնականում ավելի ճշգրիտ են, քան AST- ի վրա հիմնված մեթոդները:  Քանի որ ՀՍՏ-ն պարունակում է միայն տեղեկատվություն ծրագրի կառուցվածքի մասին:  Իսկ PDG- ն տեղեկություններ ունի ինչպես կառուցվածքի, այնպես էլ իմաստաբանության մասին:   Հետեւաբար, բարձր ճշգրտություն ապահովելու համար պետք է օգտագործել իմաստային մոտեցումը: Java դասի ֆայլ:  Java դասի ֆայլը Java bytecode պարունակող ֆայլ է (.class ընդլայնմամբ), որը կարող է գործարկվել Java վիրտուալ մեքենայի վրա:   Java bytecode- ը Java վիրտուալ մեքենայի հրահանգների ամբողջություն է:   Java դասի ֆայլը ստեղծվում է Java ծրագրավորման լեզվի բնօրինակ ֆայլերից (.java ֆայլ) ՝ օգտագործելով Java կազմող:  Եթե ​​նախնական ֆայլը մեկից ավելի դաս ունի, յուրաքանչյուր դասի կազմման արդյունքը պահվում է տարբեր դասի ֆայլերում: Java դասի ֆայլը բաղկացած է 10 հիմնական մասերից ․1: Կախարդական համարը ՝ 0xCAFEBABE2: Դասի ֆայլի ձևաչափի տարբերակը. Դասի ֆայլի փոքր-մեծ տարբերակները. 3. Դասի ֆայլի հաստատունների ֆիքսված ֆոնդ Մատչելիության դրոշը, օրինակ, դասի աբստրակտ է, ստատիկ և այլն: 5: Այս դասը ներկայիս դասի անունն է 6: Super class - գերադասի անվանում 7. Միջերեսներ - դասի միջերեսներ 8. Դաշտեր. Դասի դաշտեր 9. Մեթոդներ. Դասի մեթոդներ 10. Հատկանիշներ. Դասի հատկանիշներ (օրինակ ՝ նախնական ֆայլի անվանումը ․․․) Առաջացնում է a ծրագրի կախվածության գրաֆիկը:   Programրագրից կախվածության գրաֆիկը ՝ PDG- ն, ուղղված գրաֆիկ է, որն այս դեպքում ստացվում է բայթոդից, որը գեներացվել է Java- ով գրված ծրագիր կազմելու միջոցով (Նկար ․ 2):   Bytecode- ի հրահանգները համապատասխանում են PDG- ների գագաթներին, և կողերը կախված են տվյալ ցուցումների տվյալների կամ կառավարման հոսքի վրա:   Տվյալների կախվածության երեք հիմնական տեսակ կա ՝ իրական, հակաէներգետիկ և ելքային:  Օգտագործված աշխատանքը `ճիշտ տեսակի տվյալների կախվածությունը տվյալների հոսքի կախվածությունից:  Արդյունքում PDG- ն գրվում է ֆայլում: Նկար 2  PDG սերունդ: PDC- ից ծառ ձեռք բերելը .class ֆայլի հիման վրա:  PDG- ում պարունակվող տեղեկատվությունը պահպանելու համար, երբ գրաֆիկը ծառից ծառ է փոխակերպվում (երկու գրաֆիկների որոշ ենթակետեր, որոնք իզոմորֆ են, ծառի վերափոխումից հետո մնում են իզոմորֆ), ավելացվում են նոր գագաթներ: Treeառի ալգորիթմի նկարագրություն ստանալ 1. Մուտք ․ PDG գրաֆիկ 2. Գագաթները դասավորված են իրենց ID- ների աճման կարգով 3: Եթե ​​գագաթը ∃v ∈PDG է, կողոսկրների քանակը, որը 1-ից մեծ է, անցնում է 4-րդ քայլին, հակառակ դեպքում `54-րդ քայլին: Ստեղծվում է մի նոր գագաթ, որն ունի նույն տվյալները, ինչ ևս, ավելացվում է u գագաթին u- ի ծնողին: որպես որդի, և հեռացվում է vvu գագաթները կապող մեկը:   Այս քայլը կատարվում է v- ի բոլոր ծնողների համար, բացառությամբ վերջին և 3-րդ քայլերի կատարման 5: Cիկլերը հանվում են 6: Ելք Treeառերի ցիկլերի հեռացում ․1. Մուտք PDG գրաֆիկ 2. Բոլոր գագաթների նշանները նշանակվում են 0: 3. Քանի դեռ կա չնկատված գագաթ, համարվում է հաջորդ գագաթը:  Հակառակ դեպքում 8-րդ քայլը կատարվում է 4: Եթե ​​վերին նշանը 0 է, այն տեղադրվում է հերթում 5. Եթե հերթը դատարկ չէ, currNode գագաթը հանվում է հերթից 1-ը նշանակվում է դրա նշանին 1:  Հ․դ⁇ Անցում կա դեպի 3 քայլ 6: Եթե ​​currNode- ից դուրս եկող vertex- ի նշանը 1 է, այսինքն `արդեն նկատվել է նախորդ քայլերով, ապա currNode- ի և vert- ները միացնող կողը հանվում է: 7. Հակառակ դեպքում, եթե v գագաթնակետի նշանը 0 է, այն ավելացվում է հերթում և անցնում 5-րդ աստիճանի 8: Ելք ․ Կլոնների որոնման ալգորիթմի նկարագրություն:  Այն հիմնված է արդյունքի ծառի գագաթների համեմատության վրա:  Ալգորիթմը համեմատում է երկու ծառեր ՝ P1 և P2, որոնցից ստացվում են ենթա ծառեր, որոնք ընդգրկված չեն:  Ալգորիթմն աշխատում է հետևյալ քայլերի հաջորդականությամբ. Դիտվում է PDT1 և PDT2- ից բաղկացած անտառը:  Ալգորիթմի ընթացքում անտառի յուրաքանչյուր գագաթին նշանակվում է ամբողջ թիվ այնպես, որ նույն թիվը տրվի ցանկացած երկու գագաթնակետին միայն այն դեպքում, եթե նրանց կողմից կազմված ենթատառերը միմյանց համար իզոմորֆ են: Իզոմորֆիզմի gor1 ալգորիթմ: Մուտք PDT1, PDT2 2. Մենք մեկ ծրագրի ծառի գագաթների նշանը դնում ենք 0, մյուսը ՝ 1:  Բոլոր գագաթների համար կատարում է որոշակի հաշվարկներ: 3. Քանի դեռ դիտարկված գագաթների շրջադարձը դատարկ չէ 3.1. Հակառակ գագաթը վերագրեք CurrNode 3.2-ին: Եթե ​​currNode- ին հասնում է հաջորդ մակարդակից ակ-ից տրված մակարդակին, ապա համապատասխան f և s 3.3-ում մենք ավելացնում ենք նախորդ մակարդակի իզոմորֆ գագաթները: CurrNode- ի համար մենք անվանում ենք ամբողջ թվով նշանակման գործառույթ 3.4: Եթե ​​currNode- ը ծառի արմատ չէ 3.4.1. Նվազեցրեք չնկատված ծնողական գագաթների քանակը 1 ակինով CurrNode- ի մակարդակը նշանակեք 1-ին և 3.4.2-ին: Եթե ​​ծնողի չնկատված գագաթների թիվը 0 է, 4-ին հերթում մենք ավելացնում ենք ծնողը it Որոշակի հաշվարկներ ․1. Յուրաքանչյուր գագաթի համար մենք պահում ենք որդիների թիվը 2: Եթե ​​նա որդի չունի, 0-ին նշանակում ենք մակարդակին, հերթում ավելացնում գագաթը: Նշանակեք ամբողջ թիվը 1. Վեկտորում մենք պահում ենք currNode- ի բոլոր որդիներին վերագրված ամբողջ թվերը:  Տեսակավորեք, ավելացրեք currNode Id- ի ճակատը 2. Եթե setMap- ում արդեն կա այդպիսի վեկտորը, ապա մենք անցնում ենք 2.1 քայլին, ապա անցնում ենք 3.1 2.1 քայլին: Այդ վեկտորին համապատասխանող ամբողջ թիվը վերագրեք գագաթին 2.2: Տրված թվով գագաթների վեկտորում ավելացրեք էնամիդի գագաթը, անցեք 73-րդ քայլին: SetMap- ում մենք ավելացնում ենք վեկտորը 4. Իսկ currNode- ի վերևը համապատասխանում է հաշվարկին: 5. Հաշվի պահումը ավելացնում է այն գագաթը 6. Հաշիվն ավելանում է 1 7-ով Արդյունք isանկալի է տեսնել որոշ հետազոտություններ ալգորիթմի աշխատանքի, արագության և որակի գնահատականների վերաբերյալ Գ համեմատություններ Գրականության գործիքներ:   որակական մոտեցում », Science of Computer [5] T.Kamiya, S.Kusumoto, K.Inoue, CCFinder:   Բազմալեզվական խորհրդանիշների վրա հիմնված կոդի կլոն [8]: L.Jiang, G.Misherghi, Z.Su, S.Glondu, «DECKARD.   Մասշտաբային և ճշգրիտ ծառի վրա հիմնված Հարությունյան ՄարիամԿոդ Կլոնի որոնում ֆոնի վրա սեմալիստական ​​հետազոտությունների համար JAVA ծրագրավորման լեզվով Հիմնաբառեր. Ծածկագրային կլոն ։

Կոդի  կլոնների  որոնման  գոյություն  ունեցող  մեթոդներն  ունեն  որոշակի  սահմանափակումներ։
  Տեքստային և լեքսիկական մոտեցումները չեն գտնում խիստ փոփոխված կոդի  հատվածները։
   Սինտաքսային  և  մետրիկաների  վրա  հիմնված  մոտեցումները  գտնում  են  խիստ փոփոխված կոդի հատվածները, բայց ցածր ճշտությամբ։
  Ի տարբերություն թվարկվածների,  սեմանտիկ  մոտեցումը  գտնում  է  ինչպես  փոքր,  այնպես  էլ  մեծ  փոփոխությունների  ենթարկված  կոդի  կլոններ  բարձր  ճշտությամբ,  սակայն  գոյություն  ունեցող  մեթոդները, որոնք հիմնված են այս մոտեցման վրա կիրառելի չեն մեծ ծրագրերի համար։
   Հոդվածում ներկայացվում է կոդի կլոնների որոնման մեթոդ, որն օգտագործում է ծրագրի սեմանտիկ անալիզը։
  Այն ունի բարձր ճշտություն և կիրառվում է միլիոնավոր տողերից  բաղկացած նախնական կոդի անալիզի համար։
  Այս մեթոդի հիմքում ընկած է ծրագրի կախվածությունների  գրաֆը  (PDG),  որը  գեներացվում  է  Java-ով  գրված  ծրագրի  կոմպիլյացիայի հետևանքով ստացվող .class ընդլայնումով ֆայլերի հիման վրա։
