code clone detection llvm devmtg15 poster
1.0.0
Este repositório contém código -fonte de LaTex para o pôster "Code clone in Clone in Clang Static Analyzer".
Versão PDF compilada.
O pôster foi preparado para a reunião do LLVM Developer's Meeting 2015. A Reunião dos Desenvolvedores da LLVM é a maior conferência para especialistas em compiladores de todo o mundo realizada todos os anos. Dezenas de engenheiros que trabalham no Google, Apple e Intel estão participando da conferência e trocando experiência valiosa.
Esta pesquisa resultou em alpha.clone.CloneChecker no analisador estático de Clang. Esta verificação é capaz de detectar uma parte do que a implementação original foi capaz de detectar, mas é mais estável e pronta para a produção.
Os testes de unidade fornecem uma boa visão geral das peças de código, que podem ser detectadas pela implementação atual a montante. CloneChecker faz parte do Clang Static Analyzer, que é enviado com binário de Clang. Para executar essa verificação em um arquivo personalizado, basta instalar o Clang e digite o seguinte comando.
$ clang++ -cc1 -analyze -analyzer-checker=alpha.clone.CloneChecker source.cpp
O trabalho descrito neste pôster foi realizado em termos do Google Summer do Code 2015 e suportado pelo Google.
Eu estava trabalhando com a comunidade LLVM sob orientação do Vassil Vassilev (CERN/FNAL). Vassil é um especialista em compilador conhecido e o criador do Aplicação, um intérprete de C ++ interativo usado no CERN.
Infelizmente, a página do projeto GSOC não contém muita informação devido à minha falta de conhecimento de que grande parte do resumo que escrevi não estará acessível a partir daí. Este pôster, no entanto, contém uma extensa visão geral do trabalho realizado durante o verão de 2015.
Apesar da detecção de clones de código ser um tópico bastante popular nos últimos anos, não havia boa solução, que era extensível, aberta, fácil de usar e realmente faria seu trabalho muito bom. Embora algumas soluções existissem, a maioria delas não aproveitou as tecnologias modernas do compilador e as tentativas muito ingênuas levam a detectar uma pequena parte de clones de código amplamente existentes.
Numerosos trabalhos de pesquisa propuseram a abordagem baseada em texto, que não é escalável e ineficiente. Apenas algumas tentativas (principalmente, essa) focaram na análise AST, o que fornece resultados significativamente melhores. Aproveitar a reutilização da infraestrutura de Clang, que fornece um rico AST para C, C ++ e Objective-C, leva a uma solução ainda melhor.
A reutilização da infraestrutura de CLANG permite analisar os dialetos atualizados C e C ++ e detectar instâncias de clone de código muito sofisticadas.
O pôster mostra que a implementação proposta supera as soluções existentes (aquelas que eu conheço) no desempenho, gama de clones de código detectados e usabilidade. Muitas abordagens, que visam a velocidade, não são capazes de mais clones do tipo II e do tipo III (consulte a taxonomia do clone de código nas notas). Aqueles que tentam detectar mais tipos de similaridade têm um problema sério de desempenho. Meu trabalho combina a eficiência de desempenho e não limita os recursos de detecção.
O código usado para este artigo está disponível no meu fork do repositório de Clang.
A tabela a seguir mostra que mesmo uma implementação ingênua da verificação do clone de código é capaz de processar enormes projetos de código aberto e encontrar muitas peças de código semelhantes:
| Projeto | Tempo de construção normal | Construa com o tempo BasicCloneCheck | Clones encontrados |
|---|---|---|---|
| OpenSSL | 1m26s | 9m27s | 180 |
| Git | 0M26S | 2m46s | 34 |
| Sdl | 0M26S | 1m59s | 170 |
Durante o verão de 2016, fui estagiário no Google de Munique, onde introduzi grandes melhorias no Clang-Renames e comecei a Clang-Refactor (consulte o Doc de design para referência). Portanto, não consegui continuar meu trabalho no lado da codificação e participei apenas de poucas discussões. Raphael Iseemann sob orientação do Vassil Vassilev e com a ajuda dos engenheiros da equipe da Apple Static Anlysis fez um ótimo trabalho melhorando a infraestrutura atual (consulte a página do projeto GSOC) e finalmente empurrando o código para o repositório Clang.
O analisador estático de Clang não consegue passar informações entre as unidades de tradução e isso, infelizmente, é uma enorme limitação para a detecção de clones de código devido à sua natureza: a maioria dos clones acaba em diferentes unidades de tradução e não é relatada pelo cheque. Se uma solução adequada for feita, é necessário superar a limitação descrita. Meu trabalho no Clang-Refactor pode se tornar útil para uma solução eficiente.
Gostaria de agradecer à Vassil Vassilev pela orientação e suporte da comunidade LLVM por ótimas sugestões e todo o trabalho realizado para apoiar novos colaboradores e, é claro, o Google - por criar uma ótima oportunidade para estudantes de todo o mundo e financiamento.
Comparados aos projetos C ++, os projetos escritos em C sofrem de problemas de duplicação de código significativamente mais.
As seguintes partes do código podem ser facilmente envolvidas em funções para evitar erros em potencial, como a fixação de um bug em uma das instâncias do clone e ignorar os outros.
Um pouco mais ao longo da análise foi capaz de identificar cerca de 500 clones de código grande o suficiente (consulte os exemplos a seguir).
Comprometimento do projeto usado para análise: 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.
Cerca de 300 peças de código semelhantes no total encontradas em 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
}CONMITE BE5A750939C212BC0781FFA04FABCFD2B2BD74E.
} 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 ;Este parece especialmente estranho.
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] Para referência sobre a taxonomia do clone de código, consulte um artigo bastante recente de Roy et al.
