code clone detection llvm devmtg15 poster
1.0.0
이 저장소에는 "Clang 정적 분석기의 코드 클론 감지"포스터에 대한 라텍스 소스 코드가 포함되어 있습니다.
컴파일 된 PDF 버전.
이 포스터는 LLVM Developer 's Meeting 2015를 위해 준비되었습니다. LLVM 개발자 회의는 매년 전 세계의 컴파일러 전문가를위한 가장 큰 회의입니다. Google, Apple 및 Intel에서 일하는 수십 명의 엔지니어가 회의에 참석하고 귀중한 경험을 교환하고 있습니다.
이 연구는 Clang 정적 분석기의 alpha.clone.CloneChecker 초래했습니다. 이 점검은 원래 구현이 감지 할 수있는 것의 일부를 감지 할 수 있지만 더 안정적이고 생산 준비가 가능합니다.
단위 테스트는 현재 업스트림 구현으로 감지 할 수있는 코드 조각에 대한 좋은 개요를 제공합니다. CloneChecker 는 Clang Binary가있는 Clang 정적 분석기의 일부입니다. 사용자 정의 파일 에서이 점검을 실행하려면 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의 제작자입니다.
GSOC 프로젝트 페이지에는 슬프게도 내가 쓴 요약의 상당 부분이 거기에서 액세스 할 수 없다는 지식이 부족하여 많은 정보가 포함되어 있지 않습니다. 그러나이 포스터에는 2015 년 여름에 수행 된 작업에 대한 광범위한 개요가 포함되어 있습니다.
지난 몇 년 동안 코드 클론 탐지가 매우 인기있는 주제 임에도 불구하고 좋은 솔루션은 없었습니다.이 솔루션은 확장 가능하고 개방적이며 사용하기 쉽고 실제로 그 일을 잘 수행 할 것입니다. 일부 솔루션이 존재했지만 대부분의 솔루션은 최신 컴파일러 기술을 이용하지 않았으며 매우 순진한 시도로 인해 널리 존재하는 코드 클론의 작은 부분을 감지합니다.
수많은 연구 논문은 확장 가능하고 비효율적이지 않은 텍스트 기반 접근법을 제안했습니다. AST 분석에 중점을 둔 시도 (가장 특히이 시도)는 거의 더 나은 결과를 제공합니다. C, C ++ 및 Objective-C에 풍부한 AST를 제공하는 Clang 인프라 재사용을 활용하면 더 나은 솔루션이됩니다.
Clang 인프라를 재사용하면 최신 C 및 C ++ 방언을 구문 분석하고 매우 정교한 코드 클론 인스턴스를 감지 할 수 있습니다.
포스터는 제안 된 구현이 성능, 감지 된 코드 클론의 범위 및 유용성에서 기존 솔루션 (내가 알고있는 솔루션)을 능가한다는 것을 보여줍니다. 속도를 목표로하는 많은 접근 방식은 대부분의 타입 II 및 유형 III 클론을 할 수 없습니다 (코드 클론 분류법을 참조하십시오). 더 많은 유형의 유사성을 감지하려는 사람들은 심각한 성능 문제가 있습니다. 내 작업은 성능 효율성을 결합하면서 감지 기능을 제한하지 않습니다.
이 논문에 사용 된 코드는 Clang 저장소의 포크에서 제공됩니다.
다음 표는 순진한 코드 클론 체크 구현조차도 거대한 오픈 소스 프로젝트를 처리하고 유사한 코드를 많이 찾을 수 있음을 보여줍니다.
| 프로젝트 | 정상적인 빌드 시간 | Basic CloneCheck 시간으로 빌드하십시오 | 클론이 발견되었습니다 |
|---|---|---|---|
| OpenSSL | 1M26S | 9M27S | 180 |
| git | 0m26s | 2M46S | 34 |
| SDL | 0m26s | 1M59S | 170 |
2016 년 여름에 나는 Google Munich의 인턴으로 Clang-Rename에 대한 주요 개선을 도입하고 Clang-Reactor를 시작했습니다 (참조는 Design Doc 참조 참조). 따라서 코딩 측면에서 계속 작업 할 수 없었고 몇 가지 토론에만 참여했습니다. Vassil Vassilev의 멘토링하에 Raphael Isemann과 Apple Static Anlysis 팀 엔지니어의 도움으로 현재 인프라를 개선하고 (GSOC 프로젝트 페이지 참조) 코드를 Clang 저장소로 푸시했습니다.
Clang STATIC 분석기는 번역 단위간에 정보를 전달할 수 없으며 불행히도, 이는 그 특성 때문에 코드 클론 감지에 큰 제한이 있습니다. 대부분의 클론은 다른 번역 단위로 끝나고 점검에 의해보고되지 않습니다. 적절한 해결책을 만들려면 설명 된 한계를 극복해야합니다. Clang-Refactor에 대한 저의 작업은 효율적인 솔루션에 유용 할 수 있습니다.
안내 및 지원에 대해 Vassil Vassilev, LLVM 커뮤니티에 대한 훌륭한 제안과 새로운 기고자를 지원하기위한 모든 작업과 Google은 전 세계의 학생들과 자금 지원을위한 훌륭한 기회를 창출 한 모든 작업에 감사드립니다.
C ++ 프로젝트와 비교할 때 C에 작성된 프로젝트는 코드 복제 문제로 인해 훨씬 더 많은 것을 겪습니다.
다음 코드 조각은 클론 인스턴스 중 하나에서 버그를 고정하고 다른 코드를 무시하는 것과 같은 잠재적 오류를 방지하기 위해 기능으로 쉽게 래핑 할 수 있습니다.
분석 전반에 걸쳐 조금 더 많은 것은 약 500 개의 큰 규모를 식별 할 수있었습니다 (다음 예제 참조) 코드 클론.
분석에 사용되는 프로젝트 커밋 : B77B6127E8DE38726F37697BBC736CED7B49771.
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.의 상당히 최근 논문을 참조하십시오.
