code clone detection llvm devmtg15 poster
1.0.0
このリポジトリには、「Clang Static Analyzer」ポスターの「コードクローン検出」のラテックスソースコードが含まれています。
コンパイルされたPDFバージョン。
このポスターは、LLVM開発者の会議2015のために準備されました。LLVM開発者の会議は、毎年開催される世界中のコンパイラスペシャリスト向けの最大の会議です。 Google、Apple、Intelで働いている数十人のエンジニアが会議に出席し、貴重な経験を交換しています。
この研究により、Clang Static Analyzerのalpha.clone.CloneCheckerが行われました。このチェックは、元の実装が検出できたものの一部を検出することができますが、より安定して生産対応です。
単体テストでは、現在の上流の実装で検出できるコードピースの概要を説明します。 CloneCheckerはClang Static Analyzerの一部であり、Clang Binaryで出荷されています。カスタムファイルでこのチェックを実行するには、Clangをインストールし、次のコマンドを入力してください。
$ clang++ -cc1 -analyze -analyzer-checker=alpha.clone.CloneChecker source.cpp
このポスターに記載されている作業は、Google Summer of Code 2015の観点から行われ、Googleによってサポートされています。
私はVassil Vassilev（Cern/Fnal）の指導の下でLLVMコミュニティと協力していました。 Vassilは、CERNで使用されるインタラクティブなC ++インタープリターであるClingの作成者であり、Cernで使用されるClingの作成者です。
GSOCプロジェクトページには、私が書いた要約の大部分がそこからアクセスできないという知識が不足しているため、悲しいことに多くの情報は含まれていません。ただし、このポスターには、2015年夏に行われた作業の広範な概要が含まれています。
コードクローンの検出は過去数年間非常に人気のあるトピックであるにもかかわらず、拡張可能で、オープンで、使いやすく、実際に本当に良い解決策がありました。いくつかのソリューションが存在していましたが、それらのほとんどは最新のコンパイラテクノロジーを利用しておらず、非常に素朴な試みが広く既存のコードクローンの小さな部分を検出することにつながりました。
多数の研究論文がテキストベースのアプローチを提案しましたが、これはスケーラブルで非効率的ではありません。 AST分析に焦点を当てた試み（最も顕著な試み）のみ（最も顕著な試み）は、大幅に優れた結果をもたらしました。 C、C ++、およびObjective-Cの豊富なASTを提供するClangインフラストラクチャの再利用を活用すると、さらに良い解決策が得られます。
Clangインフラストラクチャの再利用により、最新のCおよびC ++方言を解析し、非常に洗練されたコードクローンインスタンスを検出できます。
このポスターは、提案された実装がパフォーマンス、検出されたコードクローンの範囲、使いやすさの既存のソリューション（私が知っているもの）を上回ることを示しています。速度を目指している多くのアプローチは、ほとんどのタイプIIおよびタイプIIIクローンをできません（メモのコードクローン分類法を参照してください）。より多くの種類の類似性を検出しようとしている人は、深刻なパフォーマンスの問題を抱えています。私の仕事は、検出機能を制限することなく、パフォーマンス効率を組み合わせています。
このペーパーで使用されるコードは、Clangリポジトリのフォークで入手できます。
次の表は、コードクローンチェックの素朴な実装でさえ、巨大なオープンソースプロジェクトを処理し、多くの同様のコードを見つけることができることを示しています。
| プロジェクト | 通常のビルド時間 | BasicCloneCheck Timeで構築します | クローンが見つかりました |
|---|---|---|---|
| openssl | 1m26s | 9m27s | 180 |
| git | 0m26s | 2M46S | 34 |
| SDL | 0m26s | 1M59S | 170 |
2016年夏、私はGoogle Munichでインターンを務め、Clang-Renameに大規模な改善を導入し、Clang-Refactorを始めました（参照についてはDesign Docを参照）。したがって、私はコーディング側での仕事を続けることができず、いくつかの議論に参加しました。 Vassil Vassilevの指導下にあるRaphael Isemannは、Apple Static Anlysisチームエンジニアの助けを借りて、現在のインフラストラクチャ（GSOCプロジェクトページを参照）を改善し、最終的にClangリポジトリにコードをプッシュしました。
Clang Static Analyzerは、翻訳ユニット間で情報を渡すことができません。残念ながら、この性質のためにコードクローン検出の大きな制限です。ほとんどのクローンは異なる翻訳ユニットになり、チェックによって報告されません。適切な解決策を作成する場合、説明された制限を克服する必要があります。 Clang-Refactorに関する私の仕事は、効率的なソリューションに役立つかもしれません。
Vassil Vassilev、ガイダンスとサポート、LLVMコミュニティ、素晴らしい提案、そしてもちろん、Googleをサポートしてくれたすべての作業に感謝します。
C ++プロジェクトと比較して、Cで書かれたプロジェクトは、コードの重複の問題に大幅に悩まされています。
次のコードは、クローンインスタンスの1つでバグを修正したり、他を無視したりするなど、潜在的なエラーを防ぐために、機能に簡単にラップすることができます。
分析全体でもう少し、十分な大きさの約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 et al。によるかなり最近の論文を参照してください。
