code clone detection llvm devmtg15 poster
1.0.0
Dieses Repository enthält Latex -Quellcode für das Poster "Code -Klonerkennung im Clang Stater Analyzer".
Kompilierte PDF -Version.
Das Poster wurde für das Treffen des LLVM -Entwicklers 2015 vorbereitet. LLVM -Entwicklertreffen ist die größte Konferenz für Compiler -Spezialisten aus aller Welt, die jedes Jahr stattfinden. Dutzende von Ingenieuren, die bei Google, Apple und Intel arbeiten, nehmen an der Konferenz teil und tauschen wertvolle Erfahrungen aus.
Diese Forschung führte zu alpha.clone.CloneChecker in Clang Static Analyzer. Diese Überprüfung ist in der Lage, einen Teil dessen zu erkennen, was die ursprüngliche Implementierung erkennen konnte, ist jedoch stabiler und produzierter.
Unit -Tests geben einen guten Überblick über Codestücke, die durch aktuelle Upstream -Implementierung erkannt werden können. CloneChecker ist Teil des Clang Static Analyzer, der mit Clang -Binary versandt wird. Um diese Überprüfung einer benutzerdefinierten Datei auszuführen, installieren Sie einfach Clang und geben Sie den folgenden Befehl ein.
$ clang++ -cc1 -analyze -analyzer-checker=alpha.clone.CloneChecker source.cpp
Die in diesem Poster beschriebenen Arbeiten wurden in Bezug auf Google Summer of Code 2015 durchgeführt und von Google unterstützt.
Ich arbeitete mit der LLVM -Community unter Mentoring von Vassil Vassilev (CERN/FNAL). Vassil ist ein bekannter Compiler -Spezialist und der Schöpfer von CLING, einem interaktiven C ++ - Interpreter, der in CERN verwendet wird.
Die GSOC -Projektseite enthält leider nicht viel Informationen, da ein großer Teil der von mir geschriebenen Zusammenfassung von dort aus nicht zugänglich ist. Dieses Poster enthält jedoch einen umfangreichen Überblick über die im Sommer 2015 geleisteten Arbeit.
Obwohl die Erkennung von Code-Klonen in den letzten Jahren ein sehr beliebtes Thema war, gab es keine gute Lösung, die erweiterbar, offen, leicht zu bedienen war und seine Arbeit tatsächlich wirklich gut erledigen würde. Während einige Lösungen existierten, nutzten die meisten von ihnen keine modernen Compiler -Technologien und sehr naive Versuche führten dazu, einen kleinen Teil weit verbreiteter Codeklone zu erkennen.
Zahlreiche Forschungsarbeiten schlugen einen textbasierten Ansatz vor, der sowohl nicht skalierbar als auch ineffizient ist. Nur wenige Versuche (vor allem diese) konzentrierten sich auf die AST -Analyse, was signifikant bessere Ergebnisse liefert. Die Wiederverwendung der Klanginfrastruktur, die einen reichen AST für C, C ++ und Objektiv-C bietet, führt zu einer noch besseren Lösung.
Die Wiederverwendung von Clang-Infrastruktur ermöglicht es, die aktuellen C- und C ++-Dialekte zu analysieren und sehr ausgefeilte Code-Kloninstanzen zu erkennen.
Das Poster zeigt, dass die vorgeschlagene Implementierung vorhandene Lösungen übertrifft (die mir bewusst) in der Leistung, den erkannten Codeklonen und der Benutzerfreundlichkeit. Viele Ansätze, die Geschwindigkeit abzielen, sind nicht in der Lage, die meisten Klone vom Typ II und III zu entsprechen (siehe Code -Klon -Taxonomie in Notizen). Diejenigen, die versuchen, mehr Arten von Ähnlichkeit zu erkennen, haben ein ernstes Leistungsproblem. Meine Arbeit kombiniert die Leistungseffizienz, ohne die Erkennungsfähigkeiten zu begrenzen.
Der für dieses Papier verwendete Code ist in meiner Clang -Repository erhältlich.
Die folgende Tabelle zeigt, dass selbst eine naive Implementierung der Code-Klonprüfung riesige Open-Source-Projekte verarbeiten und viele ähnliche Code-Teile finden kann:
| Projekt | Normale Bauzeit | Erstellen Sie mit BasicClonecheck -Zeit | Klone gefunden |
|---|---|---|---|
| OpenSSL | 1m26s | 9m27s | 180 |
| Git | 0M26s | 2m46s | 34 |
| SDL | 0M26s | 1m59s | 170 |
Im Sommer 2016 war ich Praktikant in Google München, wo ich Clang-Rename wichtige Verbesserungen einführte und Clang-Refactor begann (siehe Design DOC als Referenz). Daher konnte ich meine Arbeit auf der Codierungsseite nicht fortsetzen und nahm nur wenige Diskussionen teil. Raphael Isemann unter Mentorship of Vassil Vassilev und mit Hilfe von Apple Static Anlysis -Teamingenieuren hat großartige Arbeit geleistet, um die aktuelle Infrastruktur zu verbessern (siehe GSOC -Projektseite) und schließlich den Code in das Clang -Repository weiterzugeben.
Clang Static Analyzer ist nicht in der Lage, Informationen zwischen Übersetzungseinheiten zu übergeben, und dies ist leider eine enorme Einschränkung für die Erkennung von Code -Klonen aufgrund seiner Natur: Die meisten Klone landen in verschiedenen Übersetzungseinheiten und werden nicht durch die Prüfung gemeldet. Wenn eine ordnungsgemäße Lösung vorgenommen werden soll, müssen die beschriebene Einschränkung überwunden werden. Meine Arbeit an Clang-Refactor könnte für eine effiziente Lösung nützlich werden.
Ich möchte Vassil Vassilev für die Anleitung und Unterstützung, die LLVM -Community für großartige Vorschläge und all die Arbeiten zur Unterstützung neuer Mitwirkender und natürlich Google danken - für die Schaffung einer großartigen Gelegenheit für Schüler aus aller Welt und Finanzmittel.
Im Vergleich zu C ++ - Projekten leiden in C geschriebene Projekte erheblich mehr unter Code -Duplikationsproblemen.
Die folgenden Code -Teile können leicht in Funktionen eingebunden werden, um potenzielle Fehler zu verhindern, z.
Ein wenig mehr während der gesamten Analyse war in der Lage, rund 500 Codeklone zu identifizieren (siehe folgende Beispiele).
Projektkomite für Analyse: 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.
Insgesamt rund 300 ähnliche Codestücke in 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 ;Dieser sieht besonders seltsam aus.
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] als Referenz zur Code -Klon -Taxonomie siehe ziemlich aktuelles Papier von Roy et al.
