code clone detection llvm devmtg15 poster
1.0.0
Este repositorio contiene el código fuente de látex para el "Código de detección de clones en el Analizador estático de Clang".
Versión PDF compilada.
El póster fue preparado para la reunión de desarrolladores de LLVM 2015. La reunión de desarrolladores de LLVM es la conferencia más grande para especialistas en compiladores de todo el mundo celebrada cada año. Docenas de ingenieros que trabajan en Google, Apple e Intel asisten a la conferencia e intercambian una valiosa experiencia.
Esta investigación dio como resultado alpha.clone.CloneChecker en el analizador estático de Clang. Esta verificación es capaz de detectar una parte de lo que la implementación original pudo detectar, pero está más estable y está listo para la producción.
Las pruebas unitarias proporcionan una buena descripción general de las piezas de código, que pueden detectarse mediante la implementación actual aguas arriba. CloneChecker es parte del analizador estático de Clang, que se envía con Clang Binary. Para ejecutar esta verificación en un archivo personalizado, simplemente instale Clang y escriba el siguiente comando.
$ clang++ -cc1 -analyze -analyzer-checker=alpha.clone.CloneChecker source.cpp
El trabajo descrito en este póster se realizó en términos de Google Summer of Code 2015 y compatible con Google.
Estaba trabajando con la comunidad LLVM bajo la tutoría de Vassil Vassilev (CERN/FNAL). Vassil es un especialista en compiladores conocido y el creador de la adherencia, un intérprete interactivo de C ++ utilizado en el CERN.
La página del proyecto GSOC lamentablemente no contiene mucha información debido a mi falta de conocimiento de que una gran parte del resumen que escribí no se puede acceder desde allí. Sin embargo, este póster contiene una amplia visión general del trabajo realizado durante el verano de 2015.
A pesar de que la detección de clones de código era un tema bastante popular en los últimos años, no hubo buena solución, que era extensible, abierta, fácil de usar y en realidad haría su trabajo realmente bueno. Si bien existían algunas soluciones, la mayoría de ellas no aprovechó las tecnologías de compiladores modernos y los intentos muy ingenuos condujeron a detectar una pequeña parte de clones de código ampliamente existentes.
Numerosos trabajos de investigación propusieron un enfoque basado en texto, que no es escalable e ineficiente. Solo unos pocos intentos (sobre todo, este) se centraron en el análisis AST, lo que proporciona resultados significativamente mejores. Aprovechando la reutilización de la infraestructura de Clang, que proporciona un AST rico para C, C ++ y Objective-C, conduce a una solución aún mejor.
La reutilización de la infraestructura de Clang permite analizar los dialectos de C y C ++ actualizados y detectar instancias de clones de código muy sofisticadas.
El póster muestra que la implementación propuesta supera a las soluciones existentes (aquellas que conozco) en el rendimiento, el rango de clones de código detectados y la usabilidad. Muchos enfoques, que apuntan a la velocidad, no pueden ser la mayoría de los clones de Tipo II y Tipo III (consulte la taxonomía del clon del código en las notas). Aquellos que intentan detectar más tipos de similitud tienen serios problemas de rendimiento. Mi trabajo combina la eficiencia del rendimiento sin limitar las capacidades de detección.
El código utilizado para este documento está disponible en mi bifurcación de repositorio de Clang.
La siguiente tabla muestra que incluso una implementación ingenua de la verificación de clonos de código puede procesar enormes proyectos de código abierto y encontrar muchas piezas de código similares:
| Proyecto | Tiempo de construcción normal | Construir con BasicClOnecheck Time | Clones encontrados |
|---|---|---|---|
| Openssl | 1M26S | 9m27s | 180 |
| Git | 0m26s | 2m46s | 34 |
| Sdl | 0m26s | 1M59S | 170 |
Durante el verano de 2016 fui pasante en Google Munich, donde introduje las principales mejoras en Clang-Rename y comencé Clang-Refactor (ver Doc de diseño para referencia). Por lo tanto, no pude continuar mi trabajo en la codificación y solo participé en pocas discusiones. Raphael Isemann bajo la tutoría de Vassil Vassilev y con la ayuda de los ingenieros del equipo de Anlysis de Apple Static hicieron un gran trabajo mejorando la infraestructura actual (consulte la página del proyecto GSOC) y finalmente llevó el código al apositorio de CLANG.
El analizador estático de Clang no puede aprobar información entre las unidades de traducción y esto, desafortunadamente, es una gran limitación para la detección de clones de código debido a su naturaleza: la mayoría de los clones terminan en diferentes unidades de traducción y el cheque no informa. Si se va a hacer una solución adecuada, es necesario superar la limitación descrita. Mi trabajo en Clang-Refactor podría ser útil para una solución eficiente.
Me gustaría agradecer a Vassil Vassilev por su orientación y apoyo, LLVM Community por sus excelentes sugerencias y todo el trabajo realizado para apoyar a los nuevos contribuyentes y, por supuesto, Google, por crear una gran oportunidad para los estudiantes de todo el mundo y la financiación.
En comparación con los proyectos de C ++, los proyectos escritos en C sufren de problemas de duplicación de código significativamente más.
Las siguientes piezas de código se pueden envolver fácilmente en funciones para evitar posibles errores, como arreglar un error en una de las instancias clon e ignorar a las demás.
Un poco más a lo largo del análisis pudo identificar alrededor de 500 clones de código lo suficientemente grandes (ver siguientes ejemplos).
Conjunto de proyecto utilizado para el análisis: 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;
}Parche 8.0.0071.
Alrededor de 300 piezas de código similares en total encontradas en 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 ;Este se ve especialmente extraño.
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 referencia sobre la taxonomía del clon del código, ver documento bastante reciente de Roy et al.
