code clone detection llvm devmtg15 poster
1.0.0
Repositori ini berisi kode sumber lateks untuk poster "Kode Klon dalam Poster Analyzer Statis".
Versi PDF yang dikompilasi.
Poster ini disiapkan untuk pertemuan pengembang LLVM 2015. Pertemuan Pengembang LLVM adalah konferensi terbesar untuk spesialis kompiler dari seluruh dunia yang diadakan setiap tahun. Lusinan insinyur yang bekerja di Google, Apple dan Intel menghadiri konferensi dan bertukar pengalaman yang berharga.
Penelitian ini menghasilkan alpha.clone.CloneChecker di Clang Static Analyzer. Cek ini mampu mendeteksi bagian dari apa yang dapat dideteksi oleh implementasi asli, tetapi lebih stabil dan siap produksi.
Tes unit memberikan gambaran yang baik tentang potongan kode, yang dapat dideteksi dengan implementasi hulu saat ini. CloneChecker adalah bagian dari penganalisa clang static, yang dikirimkan dengan clang biner. Untuk menjalankan cek ini pada file khusus, instal dentang dan ketik perintah berikut.
$ clang++ -cc1 -analyze -analyzer-checker=alpha.clone.CloneChecker source.cpp
Pekerjaan yang dijelaskan dalam poster ini dilakukan dalam hal Google Summer of Code 2015 dan didukung oleh Google.
Saya bekerja dengan komunitas LLVM di bawah bimbingan Vassil Vassilev (CERN/FNAL). Vassil adalah spesialis kompiler yang dikenal dan pencipta Cling, interpreter C ++ interaktif yang digunakan di CERN.
Halaman Proyek GSOC sayangnya tidak mengandung banyak informasi karena kurangnya pengetahuan saya bahwa sebagian besar ringkasan yang saya tulis tidak akan dapat diakses dari sana. Poster ini, bagaimanapun, berisi tinjauan luas tentang pekerjaan yang dilakukan selama musim panas 2015.
Meskipun deteksi klon kode menjadi topik yang cukup populer selama beberapa tahun terakhir tidak ada solusi yang baik, yang dapat diperluas, terbuka, mudah digunakan dan benar-benar akan melakukan tugasnya dengan sangat baik. Sementara beberapa solusi ada, sebagian besar dari mereka tidak memanfaatkan teknologi kompiler modern dan upaya yang sangat naif menyebabkan mendeteksi sebagian kecil dari klon kode yang ada secara luas.
Sejumlah makalah penelitian mengusulkan pendekatan berbasis teks, yang tidak dapat diskalakan dan tidak efisien. Hanya beberapa upaya (terutama, yang satu ini) yang berfokus pada analisis AST, yang memberikan hasil yang jauh lebih baik. Mengambil keuntungan dari penggunaan kembali infrastruktur dentang, yang menyediakan AST yang kaya untuk C, C ++ dan Objective-C, mengarah pada solusi yang lebih baik.
Menggunakan kembali infrastruktur dentang memungkinkan untuk menguraikan dialek C dan C ++ terkini dan mendeteksi instance klon kode yang sangat canggih.
Poster menunjukkan bahwa implementasi yang diusulkan mengungguli solusi yang ada (yang saya sadari) dalam kinerja, kisaran klon kode yang terdeteksi dan kegunaan. Banyak pendekatan, yang bertujuan untuk kecepatan, tidak mampu paling mampu tipe II dan tipe III (silakan merujuk pada kode klon taksonomi dalam catatan). Mereka yang mencoba mendeteksi lebih banyak jenis kesamaan memiliki masalah kinerja yang serius. Pekerjaan saya menggabungkan efisiensi kinerja sambil tidak membatasi kemampuan deteksi.
Kode yang digunakan untuk makalah ini tersedia di repositori Fork of Clang saya.
Tabel berikut menunjukkan bahwa bahkan implementasi naif dari pemeriksaan klon kode dapat memproses proyek open-source yang sangat besar dan menemukan banyak kode yang serupa:
| Proyek | Waktu pembangunan normal | Bangun dengan waktu BasicClonecheck | Klon ditemukan |
|---|---|---|---|
| Openssl | 1M26S | 9m27s | 180 |
| Git | 0M26S | 2M46S | 34 |
| Sdl | 0M26S | 1M59S | 170 |
Selama musim panas 2016 saya adalah magang di Google Munich, di mana saya memperkenalkan perbaikan besar pada dentang-rename dan mulai mengoceh (lihat Design Doc for Reference). Oleh karena itu saya tidak dapat melanjutkan pekerjaan saya di sisi pengkodean dan hanya berpartisipasi dalam beberapa diskusi. Raphael Isemann di bawah bimbingan Vassil Vassilev dan dengan bantuan Apple Static Anlysis Team Engineers melakukan pekerjaan besar meningkatkan infrastruktur saat ini (lihat halaman proyek GSOC) dan akhirnya mendorong kode ke repositori Clang.
Clang Static Analyzer tidak dapat melewati informasi antara unit terjemahan dan ini, sayangnya, adalah batasan besar untuk deteksi klon kode karena sifatnya: sebagian besar klon berakhir di unit terjemahan yang berbeda dan tidak dilaporkan oleh cek. Jika solusi yang tepat harus dilakukan, ada kebutuhan untuk mengatasi batasan yang dijelaskan. Pekerjaan saya pada clang-refactor mungkin menjadi berguna untuk solusi yang efisien.
Saya ingin mengucapkan terima kasih kepada Vassil Vassilev untuk bimbingan dan dukungan, komunitas LLVM untuk saran bagus dan semua pekerjaan yang dilakukan untuk mendukung kontributor baru dan, tentu saja, Google - untuk menciptakan peluang besar bagi siswa dari seluruh dunia dan pendanaan.
Dibandingkan dengan proyek C ++, proyek yang ditulis dalam C menderita masalah duplikasi kode secara signifikan.
Potongan kode berikut dapat dengan mudah dibungkus ke dalam fungsi untuk mencegah kesalahan potensial, seperti memperbaiki bug di salah satu instance klon dan mengabaikan yang lain.
Sedikit lebih banyak di seluruh analisis dapat mengidentifikasi sekitar 500 klon kode yang cukup besar (lihat contoh berikut).
Project Commit Commit untuk analisis: B77B6127E8DE38726F37697BBBC736CED7B49771.
if ( encrypt ) {
while ( l -- ) {
if ( n == 0 ) {
n2l ( iv , v0 );
ti [ 0 ] = v0 ;
n2l ( iv , v1 );
ti [ 1 ] = v1 ;
BF_encrypt (( BF_LONG * ) ti , schedule );
iv = ( unsigned char * ) ivec ;
t = ti [ 0 ];
l2n ( t , iv );
t = ti [ 1 ];
l2n ( t , iv );
iv = ( unsigned char * ) ivec ;
}
c = * ( in ++ ) ^ iv [ n ];
* ( out ++ ) = c ;
iv [ n ] = c ;
n = ( n + 1 ) & 0x07 ;
}
} else {
while ( l -- ) {
if ( n == 0 ) {
n2l ( iv , v0 );
ti [ 0 ] = v0 ;
n2l ( iv , v1 );
ti [ 1 ] = v1 ;
BF_encrypt (( BF_LONG * ) ti , schedule );
iv = ( unsigned char * ) ivec ;
t = ti [ 0 ];
l2n ( t , iv );
t = ti [ 1 ];
l2n ( t , iv );
iv = ( unsigned char * ) ivec ;
}
cc = * ( in ++ );
c = iv [ n ];
iv [ n ] = cc ;
* ( out ++ ) = c ^ cc ;
n = ( n + 1 ) & 0x07 ;
}
} if (! b -> Z_is_one ) {
if (! field_sqr ( group , Zb23 , b -> Z , ctx ))
goto end;
if (! field_mul ( group , tmp1 , a -> X , Zb23 , ctx ))
goto end;
tmp1_ = tmp1 ;
} else
tmp1_ = a -> X ;
if (! a -> Z_is_one ) {
if (! field_sqr ( group , Za23 , a -> Z , ctx ))
goto end;
if (! field_mul ( group , tmp2 , b -> X , Za23 , ctx ))
goto end;
tmp2_ = tmp2 ;
} else
tmp2_ = b -> X ;
/* compare X_a*Z_b^2 with X_b*Z_a^2 */
if ( BN_cmp ( tmp1_ , tmp2_ ) != 0 ) {
ret = 1 ; /* points differ */
goto end;
}
if (! b -> Z_is_one ) {
if (! field_mul ( group , Zb23 , Zb23 , b -> Z , ctx ))
goto end;
if (! field_mul ( group , tmp1 , a -> Y , Zb23 , ctx ))
goto end;
/* tmp1_ = tmp1 */
} else
tmp1_ = a -> Y ;
if (! a -> Z_is_one ) {
if (! field_mul ( group , Za23 , Za23 , a -> Z , ctx ))
goto end;
if (! field_mul ( group , tmp2 , b -> Y , Za23 , ctx ))
goto end;
/* tmp2_ = tmp2 */
} else
tmp2_ = b -> Y ; if ( Xp && rsa -> p == NULL ) {
rsa -> p = BN_new ();
if ( rsa -> p == NULL )
goto err;
if (! BN_X931_derive_prime_ex ( rsa -> p , p1 , p2 ,
Xp , Xp1 , Xp2 , e , ctx , cb ))
goto err;
}
if ( Xq && rsa -> q == NULL ) {
rsa -> q = BN_new ();
if ( rsa -> q == NULL )
goto err;
if (! BN_X931_derive_prime_ex ( rsa -> q , q1 , q2 ,
Xq , Xq1 , Xq2 , e , ctx , cb ))
goto err;
}Patch 8.0.0071.
Sekitar 300 potongan kode serupa secara total ditemukan di VIM.
// Chunk 1.
switch ( gchar_cursor ())
{
case ALEF :
tempc = ALEF_ ;
break ;
case ALEF_U_H :
tempc = ALEF_U_H_ ;
break ;
case _AYN :
tempc = _AYN_ ;
break ;
case AYN :
tempc = AYN_ ;
break ;
case _GHAYN :
tempc = _GHAYN_ ;
break ;
case GHAYN :
tempc = GHAYN_ ;
break ;
case _HE :
tempc = _HE_ ;
break ;
case YE :
tempc = YE_ ;
break ;
case IE :
tempc = IE_ ;
break ;
case TEE :
tempc = TEE_ ;
break ;
case YEE :
tempc = YEE_ ;
break ;
default :
tempc = 0 ;
}
...
// Chunk 2.
switch ( gchar_cursor ())
{
case ALEF :
tempc = ALEF_ ;
break ;
case ALEF_U_H :
tempc = ALEF_U_H_ ;
break ;
case _AYN :
tempc = _AYN_ ;
break ;
case AYN :
tempc = AYN_ ;
break ;
case _GHAYN :
tempc = _GHAYN_ ;
break ;
case GHAYN :
tempc = GHAYN_ ;
break ;
case _HE :
tempc = _HE_ ;
break ;
case YE :
tempc = YE_ ;
break ;
case IE :
tempc = IE_ ;
break ;
case TEE :
tempc = TEE_ ;
break ;
case YEE :
tempc = YEE_ ;
break ;
default :
tempc = 0 ;
} // Code chunk 1.
/* Optional arguments: line number to stop searching and timeout. */
if ( argvars [ 1 ]. v_type != VAR_UNKNOWN && argvars [ 2 ]. v_type != VAR_UNKNOWN )
{
lnum_stop = ( long ) get_tv_number_chk ( & argvars [ 2 ], NULL );
if ( lnum_stop < 0 )
goto theend;
#ifdef FEAT_RELTIME
if ( argvars [ 3 ]. v_type != VAR_UNKNOWN )
{
time_limit = ( long ) get_tv_number_chk ( & argvars [ 3 ], NULL );
if ( time_limit < 0 )
goto theend;
}
#endif
}
...
// Code chunk 2.
if ( argvars [ 5 ]. v_type != VAR_UNKNOWN )
{
lnum_stop = ( long ) get_tv_number_chk ( & argvars [ 5 ], NULL );
if ( lnum_stop < 0 )
goto theend;
#ifdef FEAT_RELTIME
if ( argvars [ 6 ]. v_type != VAR_UNKNOWN )
{
time_limit = ( long ) get_tv_number_chk ( & argvars [ 6 ], NULL );
if ( time_limit < 0 )
goto theend;
}
#endif
}Komit BE5A750939C212BC0781FFA04FABCFD2B2BD744E.
} else if (! strcmp ( name , "cloning" )) {
if (! strcmp ( value , "true" ))
options . cloning = 1 ;
else if (! strcmp ( value , "false" ))
options . cloning = 0 ;
else
return -1 ;
return 0 ;
} else if (! strcmp ( name , "update-shallow" )) {
if (! strcmp ( value , "true" ))
options . update_shallow = 1 ;
else if (! strcmp ( value , "false" ))
options . update_shallow = 0 ;
else
return -1 ;
return 0 ;Yang ini terlihat sangat aneh.
if (( mlim = xdl_bogosqrt ( xdf1 -> nrec )) > XDL_MAX_EQLIMIT )
mlim = XDL_MAX_EQLIMIT ;
for ( i = xdf1 -> dstart , recs = & xdf1 -> recs [ xdf1 -> dstart ]; i <= xdf1 -> dend ; i ++ , recs ++ ) {
rcrec = cf -> rcrecs [( * recs ) -> ha ];
nm = rcrec ? rcrec -> len2 : 0 ;
dis1 [ i ] = ( nm == 0 ) ? 0 : ( nm >= mlim ) ? 2 : 1 ;
}
if (( mlim = xdl_bogosqrt ( xdf2 -> nrec )) > XDL_MAX_EQLIMIT )
mlim = XDL_MAX_EQLIMIT ;
for ( i = xdf2 -> dstart , recs = & xdf2 -> recs [ xdf2 -> dstart ]; i <= xdf2 -> dend ; i ++ , recs ++ ) {
rcrec = cf -> rcrecs [( * recs ) -> ha ];
nm = rcrec ? rcrec -> len1 : 0 ;
dis2 [ i ] = ( nm == 0 ) ? 0 : ( nm >= mlim ) ? 2 : 1 ;
}[0] Untuk referensi tentang Kode Taksonomi Klon, lihat makalah yang cukup baru oleh Roy et al.
