code clone detection llvm devmtg15 poster
1.0.0
該存儲庫包含“ Clang靜態分析儀中的代碼克隆檢測”海報的乳膠源代碼。
編譯的PDF版本。
海報是為LLVM開發人員2015年會議準備的。 LLVM開發人員會議是每年舉行的全世界最大的編譯器專家會議。在Google，Apple和Intel工作的數十名工程師正在參加會議並交換寶貴的經驗。
這項研究導致Clang靜態分析儀中的alpha.clone.CloneChecker 。此檢查能夠檢測到原始實施能夠檢測到的部分，但更穩定和準備就緒。
單元測試給出了代碼件的良好概述，可以通過當前上游實現來檢測。 CloneChecker是Clang靜態分析儀的一部分，該分析儀以Clang二進制運輸。要在自定義文件上運行此檢查，只需安裝clang並鍵入以下命令。
$ clang++ -cc1 -analyze -analyzer-checker=alpha.clone.CloneChecker source.cpp
此海報中描述的工作是根據Google Summer的2015年進行的，並得到了Google的支持。
在Vassil Vassilev（CERN/FNAL）的指導下，我在LLVM社區工作。瓦西爾（Vassil）是一位已知的編譯器專家，也是Cring的創建者，這是CERN中使用的交互式C ++解釋器。
由於我缺乏我所寫的摘要的很大一部分，因此，GSOC項目頁面不包含太多信息，因此無法從那裡訪問。不過，這張海報包含了2015年夏季所做的工作的廣泛概述。
儘管代碼克隆的檢測是過去幾年中非常受歡迎的話題，但沒有一個好的解決方案，這是可擴展的，開放的，易於使用的，並且實際上會做得很好。儘管存在一些解決方案，但大多數解決方案並沒有利用現代編譯器技術，並且非常天真的嘗試導致檢測到廣泛現有的代碼克隆的一小部分。
許多研究論文提出了基於文本的方法，既無法擴展又效率低下。只有很少的嘗試（最值得注意的是，這一嚐試）專注於AST分析，這給出了更好的結果。利用重複使用Clang基礎架構，為C，C ++和Objective-C提供了豐富的AST，從而提供了更好的解決方案。
重複使用Clang基礎架構允許解析最新的C和C ++方言，並檢測非常複雜的代碼克隆實例。
海報表明，擬議的實施方法在性能，檢測到的代碼克隆範圍和可用性方面優於現有解決方案（我知道的解決方案）。許多旨在以速度為目標的方法無法大多數II型和III型克隆（請參閱註釋中的代碼克隆分類法）。那些試圖檢測更多類型的相似性的人存在嚴重的性能問題。我的工作結合了性能效率，同時不限制檢測功能。
本文使用的代碼可在我的Clang存儲庫中使用。
下表顯示，即使是幼稚的代碼克隆檢查，也能夠處理龐大的開源項目並找到許多類似的代碼：
| 專案 | 正常的構建時間 | 使用基本售前時間構建 | 克隆發現 |
|---|---|---|---|
| Openssl | 1M26S | 9M27 | 180 |
| git | 0m26s | 2M46S | 34 |
| SDL | 0m26s | 1M59 | 170 |
在2016年夏季，我是Google慕尼黑的一名實習生，在那裡我對Clang-Rename進行了重大改進，並開始了Clang-Refactor（請參閱Design Doc以獲取參考）。因此，我無法繼續在編碼方面繼續工作，只參加了一些討論。 Raphael Isemann在Vassil Vassilev的指導下，在Apple靜態Anlysis團隊工程師的幫助下，改善了當前的基礎架構（請參閱GSOC項目頁面），並最終將代碼推到Clang存儲庫。
Clang靜態分析儀無法在翻譯單元之間傳遞信息，不幸的是，由於其性質，這是代碼克隆檢測的巨大限制：大多數克隆最終以不同的翻譯單元形成，並且不受支票報告。如果要製定適當的解決方案，則需要克服所述的限制。我對clang-Refactor的工作可能對有效的解決方案有用。
我要感謝Vassil Vassilev的指導和支持，LLVM Community為支持新貢獻者而做的所有工作，當然還有Google - 為來自世界各地的學生和資金創造了一個絕佳的機會。
與C ++項目相比，C中編寫的項目遭受代碼重複問題的困擾更大。
以下代碼可以輕鬆地包裹在功能中以防止潛在錯誤，例如在一個克隆實例中修復錯誤並忽略其他錯誤。
整個分析的更多內容能夠識別出大約500個大約500個（請參見以下示例）代碼克隆。
用於分析的項目提交：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;
}補丁8.0.0071。
在VIM中發現了大約300件類似的代碼。
// 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
}提交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 ;這個看起來特別奇怪。
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]有關代碼克隆分類法的參考，請參見Roy等人的最新論文。
