Code clone detection with convolutional neural network
Konvolüsyonel sinir ağı ile kod klon tespiti
- Tez No: 555901
- Danışmanlar: DR. ÖĞR. ÜYESİ AYŞE TOSUN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 65
Özet
Kaynak kod içindeki kod parçalarının kopyalanması ve yeniden kullanılmasıyla oluşturulan benzer veya aynı kod parçaları, kod klonları olarak adlandırılır. Kod klonları, genellikle programcılar tarafından kopyala-yapıştır işlemlerinin bir sonucu olarak ortaya çıkar. Bir kod parçasında hatalar mevcutsa, aynı hatalar büyük olasılıkla diğer kopyalarda da mevcuttur. Bu sebeple, birden fazla kopyası bulunan bir kod parçasının güncellemesi gerektiğinde, geliştirici sistemdeki beklenmedik çökmeleri önlemek için diğer bütün kopyaları kontrol etmek zorundadır. Çok sayıda klon içeren ve çok sayıda programcı tarafından geliştirilen bir yazılım sisteminde, bu kopyalanan kod bölümleri nedeniyle bakım maliyeti ciddi şekilde yüksek olabilir. Bu nedenle bir yazılım sistemindeki kod klonlarını tespit etmek, hem önemli bakım maliyetlerini hem de klon işlemleriyle ilişkili olası hata risklerini azaltmak için çok önemlidir. Herhangi bir kod satırı dizisi kod parçası (CF) olarak adlandırılır. Kod parçaları yorum satırı içerebilirler. Bir CF dosya adı, başlangıç satırı ve bitiş satırı oluşan üçlüler ile tanımlanır. Eğer iki kod parçası benzer yada birebir aynı ise bu kod parçaları kod klon olarak adlandırılır. Matematiksel olarak f(CF1) = f(CF2) şeklinde gösterilir (f benzerlik fonksiyonudur).Klon tipleri, program metinlerinin benzerliğine ve metinlerinden bağımsız olarak işlevselliklerinin benzerliğine dayanan iki ana tür olarak gruplandırılabilir. Metinsel klon tipleri Tip-1, Tip-2 ve Tip-3 olarak ayrılırken, işlevsel klon tipleri Tip-4 olarak bilinir. İki kod parçası, yorum veya boşluk dışında, birbirinin aynı ise Tip-1 klon olarak adlandırılırlar. İki kod parçası, sadece tanımlayıcılar, değişmezler, türler, boşluk ve yorumlar ile farklılaşmışsa, bunlar Tip-2 klonlardır. Eğer bir kod parçası, ifade ekleme-çıkarma ya da ifade değiştirme ile diğer bir kod parçasından elde edilmişse, bu iki kod parçası Tip-3 klonlardır. Eğer iki kod parçası tamamen farklı şekilde yazılmış olmasına rağmen aynı işi yapıyorsa, bu kod parçaları Tip-4 klon olarak bilinirler. Kod klon tespiti genel olarak beş adımdan oluşur: Ön işleme, dönüştürme, eşleşme tespiti, biçimlendirme ve işlem sonrası / filtreleme. Ön işleme aşamasında, kod ile alakasız kısımlar çıkarılıp, klon tespitinin hangi seviyede yapılacağı belirlenir. Dönüştürme aşamasında ise kaynak kod tokenlara, ağaç yapılarına veya grafik modellere dönüştürülüp yorum ve boşluklar kaldırılır. Dönüştürme aşaması tamamlandıktan sonra elde edilen çıktı herhangi bir karşılaştırma algoritmasına verilir. Karşılaştırma algoritması ile birbiriyle eşleşen bölümler tespit edilir. Eşleşme tespiti aşamasının çıktısı dönüştürülen koddaki eşleşme listesidir. Eşleşme aşamasında tespit edilen klonlar, biçimlendirme aşamasında orijinal koddaki hallerine döndürülerek klon tespiti tamamlanır. İşlem sonrası / filtreleme aşaması ise tespit edilen klonlar manuel olarak ya da otomatik yöntemler kullanarak filtrelenir. Klonlanmış kod parçalarının tespiti için farklı yaklaşımlar kullanan çeşitli çalışmalar yapılmıştır. Çalışmalarda önerilen yaklaşımlardan bazıları metne dayalı teknikler gerçekleştirirken, bazıları token tabanlı teknikler, diğerleri ise anlamsal veya ağaç bazlı teknikler kullanmaktadır. Metin tabanlı teknikler, kaynak kodunu kelimelerden oluşan dizeler olarak ele alır ve benzerliklerini tanımlamak için dizeleri birbirleriyle karşılaştırırlar. Diğer yaklaşımlar, klonlanmış parçaları tespit etmek için bir algoritma uygulamadan önce kaynak kodunu tokenlara veya grafik modellere dönüştürür. Kod klonu tespit modelini oluşturmak için, suffix tree, dotplot/scatter plot, hash-değeri karşılaştırması ve Öklid mesafesi gibi algoritmalar denenmiştir. Son zamanlarda, araştırmalar RNN (tekrarlayan sinir ağı) ve LSTM (uzun kısa süreli hafıza ağı) gibi derin öğrenme tekniklerin kaynak kodları modellemede kullanıldığını göstermektedir. Kaynak kodun modellenmesini gerektiren özel bir alan da kod klonu tespitidir. DNN (derin sinir ağı) gibi derin öğrenme teknikleri kullanılarak yapılan klon saptama çalışmaları, Tip-1 ve Tip-2 klonlarının en az% 98'inin tahmin edilebileceğini bildirmiştir. Çeşitli kaynaklar tarafından Tip-3 klonun en çok bulunan klon tipi olduğu belirtilmiştir. Ancak, Tip-3 klonlar Tip-4 klonlar ile birlikte saptanması en zor klon tipleridir. Derin öğrenme kullanarak bile, CClearner zayıf Tip-3 ve Tip-4 klonlarında maksimum% 28'lik bir tespit oranına ulaşmıştır. Bu nedenle, bütün klon tiplerini yüksek doğruluk oranıyla saptamak için kod klon tespiti konusunda daha fazla araştırma yapılması gerekmektedir. Bu çalışma, kaynak kodunu görüntü verisi biçimine dönüştürerek ve konvolüsyonel sinir ağı (CNN) kullanarak kod klonu tespiti yapan bir token-based teknik önermektedir. Bu çalışmada, aday klon çiftlerini tokenlarına ayırdık ve her bir tokenın kod içerisinde kaç defa geçtiğini çiftlerin her ikisi için de ayrı ayrı hesapladık. Hesaplanan değerleri frequency matrisleri olarak kaydettik. Böylece elimizde çiftlerin her ikisi için de ayrı ayrı hesaplanış matrisler oldu. Daha sonra bu iki matris birleştirilerek görüntü verisi olarak jpeg formatında kaydettik. Son olarak, CNN'i klon çiftlerini temsil eden bu görüntüler kullanılarak eğittik ve aday çiftleri“klon”ve“klon değil”olarak sınıflandırdık. Birleştirilen matris, görüntü verisine çok benzer olduğu için, bu matrisi görüntü verisiymişçesine kullanmayı uygun gördük. CNN'in girdileri görüntü olarak varsaydığı ve öznitelikleri mimariye kodlama özelliği sağladığı için CNN'i tercih ettik. Bu özellik, parametre sayısının azaltılmasına ve daha verimli uygulama yapılmasına yardımcı olmaktadır. Bu yaklaşımı uygulamak için, BigCloneBench veri kümesinden çıkarılan aday klon çiftlerini kullandık. BigCloneBench büyük java projelerindeki altı milyon doğrulanmış klondan oluşan bir veri kümesidir. Bu veri kümesinde, Tip-3 ve Tip-4 klon tipleri aralarındaki benzerlik oranına göre yeniden yorumlanmış ve toplamda altı adet klon tipi elde edilmiştir: T1 (Tip-1), T2 (Tip-2), VST3 (Çok Güçlü Tip-3), ST3 (Güçlü Tip-3), MT3 (Orta Tip-3) ve WT3/4 (Zayıf Tip-3 veya Tip-4). İki klon adayı arasındaki benzerlik oranı 0.9'dan daha büyükse, VST3 olarak etiketlenirler. Benzerlik oranı 0,7 ile 0,9 arasındaysa, bunlar ST3 klonlardır. Oran 0,7'den düşük ve 0,5'ten yüksek olduğunda, klon tipi MT3 olur. Benzerlik 0,5'in altında ise, klon tipi WT3/4 olarak adlandırılır. Yaklaşımımız üzerinde, BigCloneBench veri setinden elde edilen üç farklı eğitim seti kullanarak deneysel çalışmalar yaptık. İlk olarak veri setindeki oranları baz alarak toplamda 50 bin adet örnek aldık. Orijinal veri setininin %94.63'ü WT3/4 tipindeki klonlardan oluştuğundan, elde ettiğimiz eğitim seti de aynı oranda WT3/4 tipindeki klonlardan oluştu. İkinci olarak microsampling yöntemini denedik. Buna göre veri setindeki en az sayıda bulunan sınıfa eşit sayıda her sınıftan örnekler aldık. Verisetinde en az sayıda örneği bulunan sınıf VST3 klon tipidir ve 2083 adettir. Bu yüzden her bir klon tipinden 2000 adet örnekler aldık. Son eğitim setini ise toplamda 50 bin tane olacak şekilde rastgele örnekler alarak oluşturduk. Her bir eğitim seti için beş farklı test seti hazırladık ve her bir test setimiz 10 bin örnekten oluştu. Test setlerini hazırken, gerçek senaryoyu yansıtması için orijinal verisetindeki oranlara bağlı kaldık. Üç farklı eğitim-test seti kullanılarak CNN ile yapılan deneysel çalışmalarımız, yaklaşımımızın kod klonlarını, özellikle de karmaşık klon türlerini tespit etmede iyi bir performansa sahip olduğunu göstermektedir.
Özet (Çeviri)
Code clones are similar or identical code portions produced by duplicating existing source code for resusing in another part of the software system. Code clones are one of the main reasons of the bug propogation, and thus high maintenance cost. When a code piece is duplicated, software defects and bugs are also duplicated. Therefore, a developer should check for bugs in all copies to avoid unexpected failures in the system. If the software consists of a large number of code clones, maintenance costs may be dramatically high. For that reason, code clone detection is crutial in order to reduce both maintenance costs and crashes in a software system. In code clone detection, a group of code lines are named as code fragment (CF) and illustrated with file name, begin line and end line. A CF can include comments and white space. If two code fragments similar or identical, they are named as code clones. There are four type of code clones: Type-1, Type-2, Type-3, Type-4. Type-1 clones are identical code fragments except for white space and comments. In Type-2 clones, identifier names such as variables can be different. If a code fragment different sfrom another fragment by added, removed or modified line, they Type-3 clones. Type-4 clones are fragments performing same computation with different syntactic. Code cloning detection includes five steps: pre-processing, transformation, match detection, formatting and post-processing/filtering In the pre-processing phase, the irrelevant sections are removed and the level of clone detection is determined. In the conversion phase, the source code is converted to tokens, tree structures or graphic models, and comments and gaps are removed. After the conversion phase is complete, the resulting output is given to any comparison algorithm. The matching algorithm is used to identify the matching parts. The output of the match detection step is the match list in the converted code. Clones detected in the match phase are returned to their original form in the formatting phase and clone detection is completed. In post-processing/filtering, the detected clones are filtered manually or using automated methods. Several studies have been conducted using different approaches for the detection of cloned code fragments. However, very few of them take advantage of popular learning based approaches, such as deep learning. This thesis proposes a token-based technique that converts the source code into image data format and detects code clones using a convolutional neural network (CNN). We divided the candidate clone pairs into their tokens and calculated how many times each token passed in the code separately for both pairs. We recorded calculated values as frequency matrices, so we obtain separately calculated frequency matrices for both pairs. Then we combined these two matrices and save them as image data in jpeg format. Finally, we trained CNN using these images representing clone pairs and classify candidate clone pairs as“clone”and“not clone”. Since the merged matrix is very similar to image data, we considered it appropriate to use this matrix as image data. We chose CNN because CNN assumes inputs as images and provides attributes encoding architecture. This feature helps reduce the number of parameters and more efficient calculations. To implement this approach, we used candidate clone pairs extracted from the BigCloneBench data set. BigCloneBench is a set of six million validated clones in java projects. In this data set, Type-3 and Type-4 clone types were re-interpreted according to their similarity ratio and a total of six clone types were obtained. We conducted experimental studies on our approach using three different training sets from the BigCloneBench data set. First of all, we took 50 thousand samples in total based on the rates in the dataset. As 94.63% of the original data set consisted of WT3/4 clones, the training set we obtained consisted of clones of WT3/4 type at the same rate. Second, we tried the microsampling methodology. Accordingly, we received 2000 samples for each type since there are 2083 VST3 which has minimum number of elements in BigCloneBench. The final training set was composed of random samples with a total of 50 thousand. We prepared five test sets for each training set and each test set consisted of 10 thousand samples. When preparing the test sets, we adhered to the proportions of the original data to reflect the actual scenario. Our experimental studies with CNN using three different training-test sets show that our approach has a good performance in detecting code clones, especially complex clone types.
Benzer Tezler
- BGA malzemelerin x-ışını görüntülerindeki lehim hatalarının derin sinir ağı kullanarak tespiti
Detection of BGA solder defects from x-ray images using deep neural network
CEREN TÜRER AKDENİZ
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. ZÜMRAY ÖLMEZ
- Determining noise type in qr code images using classical machine learning algorithms
Klasik makine öğrenme algoritmalarıyla qr kodlu görüntülerde gürültü türünün belirlenmesi
AHMAD BILAL WARDAK
Yüksek Lisans
İngilizce
2022
Bilim ve Teknolojiİstanbul Aydın ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
Assist. Prof. Dr. JAWAD RASHEED
- Dijital görüntü işleme teknikleri kullanılarak görüntülerden detay çıkarımı
Feature extraction from images by using digital image processing techniques
GÜZİDE MİRAY PERİHANOĞLU
Yüksek Lisans
Türkçe
2015
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
ÖĞR. GÖR. MEHMET UFUK ÖZERMAN
- Nesneye dayalı programlama tabanlı yazılımlarda yazılım metrikleri kullanılarak yapısal kod klon tespiti
Structural code clone detection on object oriented software using software metrics
MUSTAFA KAPDAN
Yüksek Lisans
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MEHMET SIDDIK AKTAŞ
- Refactoring support in ide and code clone detection
Tümleşik geliştirme ortamlarında yazılım duzenleme desteği vekod klon algilama
ZHALA SARKAWT OTHMAN OTHMAN
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFırat ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
Assist. Prof. Dr. MEHMET KAYA