ԿՈԴԻ ԿԼՈՆՆԵՐԻ ՈՐՈՆՈՒՄ «JAVA» ԾՐԱԳՐԱՎՈՐՄԱՆ ԼԵԶՎԻ ՀԱՄԱՐ՝ ՀԻՄՆՎԱԾ ԾՐԱԳՐԻ ՍԵՄԱՆՏԻԿՀԵՏԱԶՈՏՈՒԹՅԱՆ ՎՐԱՆերածություն։
   Ծրագրավորողը  կարող  է  օգտագործել  ծրագրի  միևնույնմասը մի  քանի անգամ՝ որոշակիորեն այն  փոփոխելով։
  Կոդի պատճենումն ունրա օգտագործումը կարող է հանգեցնել սեմանտիկ սխալների։
  Օրինակ, ծրագրավորողը  կարող  է  մոռանալ  կոդի  պատճենված  մասի  որոշ  փոփոխականների  վերանվանումը,  որը  կհանգեցնի  սխալի։
   Կոդի  հատվածի  կրկնակի  օգտագործումը  հաճախ  է  հանդիպում  մեծ  ծրագրային  համակարգերում։
   Այնծրագիրը, որտեղ կլոնները շատ են, հավանաբար, կպարունակի շատ սխալներև  կունենա  ցածր  որակ։
   Ըստ  տարբեր  հետազոտությունների  [1,  2]  ծրագրի20%-ը  կարող  է  լինել  կլոն։
   Կոդի  կլոնների  որոնման  գործիքներն  ունեն  բազմաթիվ կիրառություններ․●  Կոդի որակի անալիզ ●  Հեղինակային իրավունքների խախտումների հայտնաբերում●  Վիրուսների հայտնաբերում●  Սխալների հայտնաբերումՀոդվածում  կներկայացվի,  թե  ինչպես  է  իրականացվում  կոդի  կլոններիորոնումը Java ծրագրավորման լեզվի համար։
  Առաջին մասում ներկայացվում էծրագրի  կախվածությունների  գրաֆի  (PDG)  ստացումը։
   Երկրորդ  մասումանալիզ  են  արվում  PDG-ները՝  կոդի  կլոններ  որոնելու  համար։
   Կիրառվում  էնոր  ալգորիթմ՝  PDG-ից  ծառ  ստանալու  և  երկու  ծառերի  մաքսիմալ  իզոմորֆենթածառեր  գտնելու  համար։
   Ալգորիթմը  նախնական  կոդի  միլիոնավոր  տողերի անալիզի հնարավորություն է տալիս։
 Կոդի  կլոնի տիպեր։
  Գոյություն ունեն 3 հիմնական տիպի կոդի կլոններ։
 Առաջին  տիպի  կլոնները  դրանք  կոդի  այն  հատվածներն  են,  որոնք  կարող  ենտարբերվել միայն բացատներով և մեկնաբանություններով (T1) ։
  Երկրորդ տիպի կլոնները դրանք կոդի այն հատվածներն են, որոնք կարող են տարբերվելբացատներով,  մեկնաբանություններով,  փոփոխականների  անուններով,նրանց  տիպերով  և  արժեքներով  (T2)։
   Երրորդ  տիպի  կլոնները  դրանք  կոդիայն  հատվածներն  են,  որոնք  կարող  են  տարբերվել  բացատներով,  մեկնաբանություններով,  փոփոխականների  անուններով,  նրանց  տիպերով  և  արժեքներով, ինչպես նաև կարող են ավելանալ կամ ջնջվել կոդի որոշ տողեր (T3) [3](Նկ․ 1)։
 4։
  void sumProd(int5։
  ﬂoat sum = 0.0;6։
  ﬂoat prod = 1.0;7։
  for (int i = 1;8։
  sum = sum + i;9։
  prod = prod * i;10։
  foo(sum, prod);11։
  }12։
  }Գծ․ 1․ Երեք տիպի կլոնների օրինակներԿոդի  կլոնների  որոնման  մոտեցումները։
   Կոդի  կլոնների  որոնման  համար կիրառվում են տարբեր մոտեցումներ։
  Ամեն մոտեցում ունի իր առավելությունները  և  թերությունները  կոնկրետ  տիպի  կլոններ  գտնելու  համար։
   Բոլորմոտեցումների  դեպքում  գլխավոր  պահանջը  գտնված  կլոնների  կոռեկտությունն է։
  Գոյություն ունի կոդի կլոնների որոնման 5 հիմնական մոտեցում․ Տեքստային Լեքսիկական Սինտաքսային  Մետրիկաների վրա հիմնված Սեմանտիկական 1.  Տեքստային  մոտեցում։
   Ալգորիթմները,  որոնք  հիմնված  են  այսմոտեցման  վրա,  հիմնականում  հեշավորում  են  մի  քանի  տողեր,  այնուհետևհամեմատում  են  հեշերը  [4]։
   Եթե  հեշերը  համընկնում  են,  ապա  ալգորիթմըդրանք համարում է կլոններ։
  Որոշ ալգորիթմներ կարողանում են գտնել նմանֆայլեր։
   Այդ  դեպքում  վերցվում  է  որոշակի  տողերի  հաջորդականություն  ևհաշվվում  է  ստուգիչ  գումար  նրանց  համար։
   Այնուհետև  ֆայլերի  փոխարենհամեմատվում  են  այդ  գումարները։
   Համընկնման  դեպքում  ֆայլերը  համարվում  են  կլոններ։
   Այս  մոտեցման  թերությունն  այն  է,  որ  գտնում  է  միայն  (T1)տիպի  կլոններ։
   Այսպիսի  ալգորիթմների  բարդությունը  քառակուսային  էստացված հեշերի քանակի նկատմամբ։
 2. Լեքսիկական մոտեցում։
  Այս մոտեցման դեպքում լեքսիկական անալիզատորի  միջոցով  կոդը  թարգմանվում  է  թոքենների  հաջորդականության,  ինչից հետո ալգորիթմը որոնում է համընկնող թոքենների ենթահաջորդականություններ  [5]։
   Այս  մոտեցմամբ  հնարավոր  է  գտնել  (T1)  և  (T2)  տիպի  կլոններ։
 Վատագույն դեպքում այսպիսի ալգորիթմների բարդությունը քառակուսային էթոքենների  թվից  կախված,  սակայն  գործնականում  նրանք  աշխատում  ենբավական արագ։
 3.  Սինտաքսային  մոտեցում։
   Այս  մոտեցումը  հիմնված  է  AST  (abstractsyntax  tree)  ծառերի  վրա։
   Կլոններ  համարվում  են  AST  ծառի  իզոմորֆ  ենթածառերը։
   Իզոմորֆ  ենթածառերի  որոնման  համար  կիրառվում  են  տարբերալգորիթմներ․ երկու ծառերի մեջ փնտրվում է ամենամեծ ընդհանուր ենթածառը [6]։
  երկու ծառերի համար կառուցվում են վերջածանցային ծառեր, որոնցվրա որոնվում են կլոններ [7]։
  երկու  ծառերի  ենթածառերի  համար  կառուցվում  են  բնութագրիչվեկտորներ, որոնք և համեմատվում են [8]։
 Այսպիսի  ալգորիթմների  բարդությունը  տատանվում  է  գծայինից  մինչևքառակուսայինի  AST  ծառի  գագաթների  թվի  նկատմամբ։
   Այն  կախված  էմինիմալ  դիտարկվող  ենթածառերի  չափերից։
   Այս  մոտեցման  վրա  հիմնվածմեթոդները գտնում են բոլոր տիպի կլոններ։
 4.  Մետրիկայի  վրա  հիմնված  մոտեցում։
   Կոդի  կտորների  համար  հաշվվում  են  տարբեր մետրիկաներ, իսկ հետո համեմատում են  ստացված մետրիկաները։
   Հիմնականում  հաշվում  են  AST  ծառերի,  ծրագրի  կախվածությունների  գրաֆի  կամ  տվյալների  հոսքի  գրաֆի  համար  մետրիկաներ։
   Այսինքն,նախապես  նախնական  կոդից  ստացվում  է  AST  ծառ,  ծրագրի  կախվածությունների  գրաֆ  կամ  տվյալների  հոսքի  գրաֆ,  նրանց  համար  սահմանվում  էկոդի  միավոր,  ապա  յուրաքանչյուր  կոդի  միավորի  համար  հաշվվում  են  մետրիկաները։
   Մետրիկաները  հաշվարկվելուց  հետո  զույգ  առ  զույգ  համեմատվում  են  [9]։
   Որպես  կանոն  այս  մոտեցման  մեթոդներն  աշխատում  են  ավելիարագ,  քան  AST  ծառերի,  ծրագրի  կախվածությունների  գրաֆի  (PDG)  կամտվյալների  հոսքի  գրաֆի  վրա հիմնված ալգորիթմները,  սակայն ունեն ավելիփոքր ճշտություն։
  Այսպիսի ալգորիթմների բարդությունը տատանվում է գծայինից  մինչև  քառակուսայինի՝  կախված  AST  ծառի  գագաթների  թվից  կամծրագրի  կախվածությունների  գրաֆի  գագաթներից։
   Այս  մոտեցման  վրահիմնված մեթոդները գտնում են բոլոր տիպի կլոններ։
 5. Սեմանտիկական մոտեցում։
  Այս մոտեցման հիմքում ընկած է ծրագրիկախվածությունների  գրաֆը՝  PDG  (program  dependence  graph)։
   Այս  մոտեցման  վրա  հիմնված  ալգորիթմը  որոնում  է  իզոմորֆ  ենթագրաֆներ  [10,  11]։
 Այսպիսի ալգորիթմների բարդությունը կարող է էքսպոնենցիալ լինել։
  Այսպիսիմեթոդների ճշտությունը մեծ է մյուս մոտեցումների համեմատությամբ, սակայնարագությունը  զգալի  զիջում  է։
   Այս  մոտեցման  վրա  հիմնված  մեթոդներըգտնում են բոլոր տիպի կլոններ։
 Մոտեցումների  համեմատում։
   Լեքսիկական  և  տեքստային  մոտեցումները բոլոր տիպի կլոնները չեն գտնում։
  Մյուս մեթոդները բոլոր երեք տիպի կլոնները  գտնում  են,  բայց  մետրիկաների  վրա  հիմնված  մոտեցումների  ճշգրտությունը ցածր է։
  Ընդհանուր առմամբ PDG-ի վրա հիմնված ալգորիթմներն ավելի ճշգրիտ են քան AST-ի վրա հիմնված մեթոդները։
  Քանի որ AST-ն պարունակում է միայն ծրագրի կառուցվածքի մասին ինֆորմացիա։
  Իսկ PDG-ն ունի ինֆորմացիա  ինչպես  կառուցվածքի,  այնպես  էլ  սեմանտիկայի  մասին։
   Հետևաբար  բարձր  ճշտություն ապահովելու համար պետք  է  օգտագործել սեմանտիկական մոտեցումը։
 Java-ի դաս ֆայլ։
  Java-ի դաս ֆայլը՝ դա Java բայթկոդ պարունակող ֆայլէ  (.class  ընդլայնումով),  որը  կարող  է  կատարվել  Java-ի  վիրտուալ  մեքենայիվրա։
   Java  բայթկոդը  Java-ի  վիրտուալ  մեքենայի  ինստրուկցիաների  բազմություն  է։
   Java-ի  դաս  ֆայլը  ստեղծվում  է  Java  ծրագրավորման  լեզվի  նախնական ֆայլերից (.java ֆայլ)՝ Java-ի կոմպիլյատորի միջոցով։
  Եթե մի նախնականֆայլն ունի մեկից ավել դասեր, ապա յուրաքանչյուր դասի կոմպիլյացիայի արդյունքը պահվում է տարբեր դասի ֆայլերում։
 Java-ի դաս ֆայլը բաղկացած է 10 հիմնական մասից․1.  Մոգական համար՝ 0xCAFEBABE2.  Դաս  ֆայլի  ֆորմատի  տարբերակ`  դաս  ֆայլի  մինոր  և  մաժոր  տարբերակները 3.  Հաստատունների ավազան՝ դաս ֆայլի հաստատունների համար4.  Հասանելիության դրոշ՝ օրինակ՝ արդյո՞ք դասը աբստրակտ է, ստատիկև այլն5.  This դաս՝ ընթացիկ դասի անունը6.  Super դաս` super դասի անունը7.  Ինտերֆեյսներ՝ դասում գտնվող ինտերֆեյսները8.  Դաշտեր՝ դասում գտնվող դաշտերը9.  Մեթոդներ՝ դասում գտնվող մեթոդները10.  Ատրիբուտներ՝  դասի  ատրիբուտները  (օրինակ՝  նախնական  ֆայլիանունը ․․․)Ծրագրի  կախվածության  գրաֆի  գեներացիա։
   Ծրագրի  կախվածությունների  գրաֆը՝  PDG,  ուղղորդված  գրաֆ  է,  որն  այս  դեպքում  ստացվում  էJava-ով գրված ծրագրի կոմպիլյացիայի արդյունքում ստացվող բայթկոդից (Նկ․2)։
   PDG-ի  գագաթներին  համապատասխանում  են  բայթկոդի  ինստրուկցիաներ, իսկ կողերին՝ այդ ինստրուկցիաների միջև տվյալների կամ ղեկավարմանհոսքի  կախվածություններ։
   Գոյություն  ունեն  3  հիմնական  տիպի  տվյալներիկախվածություններ՝ ճիշտ (true), անտի (anti) և արտաքին (output)։
  Աշխատանքում օգտագործվել են ղեկավարման և տվյալների հոսքից՝ ճիշտ տիպի տվյալների կախվածությունները։
  Ստացված PDG-ն գրվում է ֆայլում։
 Նկ․ 2։
  PDG-ի գեներացիա .class ֆայլի հիման վրաPDG-ից ծառի ստացում։
  Որպեսզի գրաֆը ծառի ձևափոխելուց PDG-ումպարունակվող  ինֆորմացիան  հնարավորինս  ճիշտ  պահպանվի  (այսինքներկու գրաֆների ինչ-որ ենթագրաֆներ, որոնք իզոմորֆ են, ծառի ձևափոխվելուց մնան իզոմորֆ), ավելացվում են նոր գագաթներ և կողեր։
 Ծառ ստանալու ալգորիթմի նկարագրություն․ 1.  Մուտք․ PDG գրաֆ2.  Գագաթները դասավորվում են ըստ իրենց ID-ների աճման կարգի3.  Եթե  ∃v  ∈PDG  գագաթ,  որի  մտնող  կողերի  թիվը  1-ից  մեծ  է,  ապաանցում է կատարվում 4 քայլին, հակառակ դեպքում՝ 5 քայլին4.  Նոր գագաթ է ստեղծվում, որն ունի նույն տվյալները ինչ v-ն և ավելացվում  v-ի  ծնող  u  գագաթին  որպես  որդի,  v  և  u  գագաթները  միացնողկողը  հեռացվում  է։
   Այս  քայլը  կատարվում  է  v-ի  բոլոր  ծնողների  համար, բացի վերջինից և անցում է կատարվում 3 քայլին5.  Կատարվում է ցիկլերի հեռացում6.  Ելք․ ծառՑիկլերի հեռացում․1.  Մուտք․ PDG գրաֆ2.  Բոլոր գագաթների mark-երին վերագրվում է 0։
 3.  Քանի  դեռ  կա  չդիտարկված  գագաթ,  դիտարկվում  է  հերթական  գագաթը։
  Հակառակ դեպքում կատարվում է անցնում 8 քայլին4.  Եթե գագաթի mark-ը 0 է, տեղադրվում է հերթի մեջ5.  Եթե  հերթը  դատարկ  չէ,  հերթից  հանվում  է  currNode  գագաթը  և  իրmark-ին վերագրվում 1։
  Հ․դ․ կատարվում է անցում 3 քայլին6.  Եթե  currNode-ից  դուրս  եկող  v  գագաթի  mark-ը  1  է,  այսինքն  արդենդիտարկվել  է  նախորդ  քայլերում,  ապա  currNode  և  v  գագաթներըմիացնող կողը հեռացվում է7.  Հակառակ դեպքում, եթե v գագաթի mark-ը 0 է, այն ավելացվում է հերթում և անցում կատարվում 5 քայլին8.  Ելք․ ծառԿլոնների որոնման ալգորիթմի նկարագրություն։
  Այն հիմնված է ստացված ծառի գագաթների համեմատման վրա։
  Ալգորիթմը համեմատում է երկուծառեր՝ P1 և P2, որոնցից ստացվում են ենթածառեր, որոնք հանդիսանում ենկլոններ։
  Ալգորիթմն աշխատում է հետևյալ քայլերի հաջորդականությամբ․Դիտարկվում է PDT1 և PDT2-ից կազմված անտառը։
  Ալգորիթմի ընթացքում անտառի յուրաքանչյուր գագաթի վերագրվում է ամբողջ թիվ այնպես, որցանկացած  երկու  գագաթի  վերագրված  է  միևնույն  թիվը  այն  և  միայն  այնդեպքում, երբ նրանցով առաջացած ենթածառերը իրար իզոմորֆ են։
 Իզոմորֆիզմի ալգորիթմ․1.  Մուտք․ PDT1, PDT2 2.  Մի  ծրագրի  կախվածության  ծառի  գագաթների  mark-ը  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.  Ելք․ Որոշակի հաշվարկներ․1.  Ամեն մի գագաթի համար պահում ենք որդիների քանակը2.  Եթե որդի չունի, ապա մակարդակին վերագրում ենք 0, գագաթը ավելացնում հերթի մեջ Ամբողջ թվի վերագրում․1.  Վեկտորի  մեջ  պահում  ենք  currNode-ի  բոլոր  որդիներին  վերագրվածամբողջ թվերը։
  Սորտավորում, ավելացնում դիմացից currNode-ի Id-ն2.  Եթե  setMap-ում  արդեն  կա  այդպիսի  վեկտոր,  ապա  անցնում  ենք  2.1քայլին, հ․դ․՝ անցնում ենք 3 քայլին2.1. Այդ  վեկտորին  համապատասխան  ամբողջ  թիվը  վերագրում  ենքգագաթին2.2. Տրված թիվը ունեցող գագաթների վեկտորի մեջ ավելացնում ենքայդ գագաթը, անցնում 7 քայլին3.  SetMap-ում ավելացնում ենք վեկտորը4.  Նրան և currNode գագաթին համապատասխանեցնում count-ը5.  Count ունեցողների մեջ ավելացնում այդ գագաթը6.  Count-ը մեծացնում 1-ով 7.  Ելք․Ցանկալի է տեսնել ալգորիթմի աշխատանքի որոշակի հետազոտություն,արագագործության և որակի գնահատականներ և համեմատություններԳրականությունtools։
   a  qualitative  approach”,  Science  of  Computer[5]   T.Kamiya,  S.Kusumoto,  K.Inoue,  “CCFinder։
   A  multilinguistic  token-based  code  clone[8].   L.Jiang,  G.Misherghi,  Z.Su,  S.Glondu,  “DECKARD։
   Scalable  and  accurate  tree-basedՀարությունյան ՄարիամԿՈԴԻ ԿԼՈՆՆԵՐԻ ՈՐՈՆՈՒՄ JAVA ԾՐԱԳՐԱՎՈՐՄԱՆ ԼԵԶՎԻ ՀԱՄԱՐ՝ ՀԻՄՆՎԱԾԾՐԱԳՐԻ ՍԵՄԱՆՏԻԿ ՀԵՏԱԶՈՏՈՒԹՅԱՆ ՎՐԱԲանալի բառեր՝ Կոդի կլոն, PDG, նախնական կոդ, Java, բայթկոդ, սեմանտիկ անալիզԱմփոփում։

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