code clone detection llvm devmtg15 poster
1.0.0
Этот репозиторий содержит исходный код латексного кода для плаката «Обнаружение клона кода в статическом анализаторе Clang».
Скомпилированная версия PDF.
Плакат был подготовлен для собрания разработчиков LLVM 2015. Заседание разработчиков LLVM является крупнейшей конференцией для специалистов по компиляторам со всего мира, проводимых каждый год. Десятки инженеров, работающих в Google, Apple и Intel, посещают конференцию и обмениваются ценным опытом.
Это исследование привело к alpha.clone.CloneChecker в статическом анализаторе Clang. Этот чек способен обнаружить часть того, что оригинальная реализация смогла обнаружить, но более стабильная и готовая к производству.
Модульные тесты дают хороший обзор деталей кода, которые могут быть обнаружены с помощью текущей реализации выше по течению. CloneChecker является частью статического анализатора Clang, который поставляется с бинарным классом Clang. Чтобы запустить эту проверку в пользовательском файле, просто установите Clang и введите следующую команду.
$ clang++ -cc1 -analyze -analyzer-checker=alpha.clone.CloneChecker source.cpp
Работа, описанная на этом плакате, была выполнена с точки зрения Google Summer of Code 2015 и поддерживалась Google.
Я работал с сообществом LLVM под наставницей Васила Вассилева (CERN/FNAL). Вассил является известным специалистом по компиляторам и создателем CLING, интерактивного интерпретатора C ++, используемого в CERN.
Страница проекта GSOC, к сожалению, не содержит много информации из -за отсутствия знаний о том, что большая часть резюме, которую я написал, не будет доступна оттуда. Этот плакат, однако, содержит обширный обзор работы, проделанной летом 2015 года.
Несмотря на то, что в последние годы обнаружение клонов кода была довольно популярной темой, не было хорошего решения, которое было бы расширяемо, открыто, простое в использовании и действительно сделало бы свою работу действительно хорошо. В то время как некоторые решения существовали, большинство из них не использовали преимущества современных технологий компилятора, и очень наивные попытки приводят к обнаружению небольшой части широко существующих клонов кода.
Многочисленные исследовательские работы предлагают текстовый подход, который не является масштабируемым и неэффективным. Лишь немногие попытки (в частности, этот) были сосредоточены на анализе AST, что дает значительно лучшие результаты. Используя преимущество в повторном использовании инфраструктуры Clang, которая обеспечивает богатый AST для C, C ++ и Objective-C, приводит к еще лучшему решению.
Повторное использование инфраструктуры Clang позволяет анализировать обновленные диалекты C и C ++ и обнаруживать очень сложные экземпляры клонов кода.
Плакат показывает, что предлагаемая реализация превосходит существующие решения (те, о которых я знаю) по производительности, диапазону обнаруженных кодовых клонов и удобство использования. Многие подходы, которые стремятся к скорости, не способны большинству клонов типа II и типа III (пожалуйста, обратитесь к таксономии кода в примечаниях). Те, кто пытается обнаружить больше типов сходства, имеют серьезную проблему производительности. Моя работа сочетает в себе эффективность производительности, не ограничивая возможности обнаружения.
Код, используемый для этой статьи, доступен в моей репозитории Clang.
Следующая таблица показывает, что даже наивная реализация проверки клонов кода способна обрабатывать огромные проекты с открытым исходным кодом и найти много подобных фрагментов кода:
| Проект | Нормальное время сборки | Построить со временем BasicCloneCheck | Клоны найдены |
|---|---|---|---|
| Openssl | 1m26s | 9m27s | 180 |
| Git | 0M26S | 2m46s | 34 |
| SDL | 0M26S | 1m59s | 170 |
Летом 2016 года я был стажером в Мюнхене Google, где я ввел значительные улучшения Clang-Rename и начал Clang-Refactor (см. Design Doc для справки). Поэтому я не смог продолжить свою работу на стороне кодирования и участвовал только в нескольких дискуссиях. Рафаэль Исеманн под наставником Васила Вассилева и с помощью инженеров команды Apple Static Anlysis проделал большую работу, улучшая текущую инфраструктуру (см. Страницу проекта GSOC) и, наконец, подтолкнув код в хранилище Clang.
Статический анализатор Clang не в состоянии передать информацию между переводами, и это, к сожалению, является огромным ограничением для обнаружения кода из -за его природы: большинство клонов заканчиваются в разных единицах перевода и не сообщаются чеком. Если должно быть принято правильное решение, необходимо преодолеть описанное ограничение. Моя работа над Clang-Refactor может стать полезной для эффективного решения.
Я хотел бы поблагодарить Васила Вассилева за руководство и поддержку, сообщество LLVM за отличные предложения и всю работу, выполненную для поддержки новых участников и, конечно же, Google - за создание прекрасной возможности для студентов со всего мира и финансирования.
По сравнению с проектами C ++, проекты, написанные в C, страдают от вопросов дублирования кода значительно больше.
Следующие фрагменты кода могут быть легко завернуты в функции, чтобы предотвратить потенциальные ошибки, такие как исправление ошибки в одном из экземпляров клона и игнорирование других.
Немного больше на протяжении всего анализа смог выявить около 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.
Около 300 аналогичных кусочков кода в общей сложности, найденных в 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
}Commit 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.
