code clone detection llvm devmtg15 poster
1.0.0
ที่เก็บนี้มีซอร์สโค้ด LaTeX สำหรับโปสเตอร์
คอมไพล์เวอร์ชัน PDF
โปสเตอร์จัดทำขึ้นสำหรับการประชุมนักพัฒนา LLVM ในปี 2558 การประชุมนักพัฒนา LLVM เป็นการประชุมที่ใหญ่ที่สุดสำหรับผู้เชี่ยวชาญด้านคอมไพเลอร์จากทั่วทุกมุมโลกที่จัดขึ้นทุกปี วิศวกรหลายสิบคนที่ทำงานที่ Google, Apple และ Intel กำลังเข้าร่วมการประชุมและแลกเปลี่ยนประสบการณ์ที่มีค่า
การวิจัยนี้ส่งผลให้ alpha.clone.CloneChecker ใน Clang Static Analyzer การตรวจสอบนี้มีความสามารถในการตรวจจับส่วนหนึ่งของสิ่งที่การใช้งานดั้งเดิมสามารถตรวจจับได้ แต่มีความเสถียรและพร้อมการผลิตมากขึ้น
การทดสอบหน่วยให้ภาพรวมที่ดีของชิ้นส่วนโค้ดซึ่งสามารถตรวจพบได้โดยการใช้งานต้นน้ำในปัจจุบัน CloneChecker เป็นส่วนหนึ่งของ Clang Static Analyzer ซึ่งจัดส่งด้วย binary clang ในการเรียกใช้การตรวจสอบนี้บนไฟล์ที่กำหนดเองเพียงติดตั้งระบบและพิมพ์คำสั่งต่อไปนี้
$ clang++ -cc1 -analyze -analyzer-checker=alpha.clone.CloneChecker source.cpp
งานที่อธิบายไว้ในโปสเตอร์นี้ทำในแง่ของ Google Summer of Code 2015 และสนับสนุนโดย Google
ฉันทำงานกับชุมชน LLVM ภายใต้การให้คำปรึกษาของ Vassil Vassilev (CERN/FNAL) Vassil เป็นผู้เชี่ยวชาญด้านคอมไพเลอร์ที่รู้จักและเป็นผู้สร้าง CLING ซึ่งเป็นล่าม Interactive C ++ ที่ใช้ใน CERN
หน้าโครงการ GSOC น่าเศร้าไม่มีข้อมูลมากนักเนื่องจากขาดความรู้ว่าส่วนใหญ่ของบทสรุปที่ฉันเขียนจะไม่สามารถเข้าถึงได้จากที่นั่น แม้ว่าโปสเตอร์นี้มีภาพรวมที่กว้างขวางของงานที่ทำในช่วงฤดูร้อนปี 2558
แม้จะมีการตรวจจับการโคลนโค้ดเป็นหัวข้อที่ได้รับความนิยมในช่วงหลายปีที่ผ่านมา แต่ก็ไม่มีทางออกที่ดีซึ่งขยายได้เปิดใช้งานง่ายและใช้งานได้จริงและจริง ๆ แล้วจะทำงานได้ดีจริงๆ ในขณะที่การแก้ปัญหาบางอย่างมีอยู่ส่วนใหญ่ไม่ได้ใช้ประโยชน์จากเทคโนโลยีคอมไพเลอร์ที่ทันสมัยและความพยายามที่ไร้เดียงสามากนำไปสู่การตรวจจับส่วนเล็ก ๆ ของโคลนรหัสที่มีอยู่อย่างกว้างขวาง
เอกสารการวิจัยจำนวนมากเสนอวิธีการบนข้อความซึ่งไม่สามารถปรับขนาดได้และไม่มีประสิทธิภาพ มีเพียงไม่กี่ความพยายาม (ที่สะดุดตาที่สุด) มุ่งเน้นไปที่การวิเคราะห์ AST ซึ่งให้ผลลัพธ์ที่ดีกว่าอย่างมีนัยสำคัญ การใช้ประโยชน์จากการใช้โครงสร้างพื้นฐานของเสียงดังอีกครั้งซึ่งให้ AST ที่หลากหลายสำหรับ C, C ++ และ Objective-C นำไปสู่การแก้ปัญหาที่ดียิ่งขึ้น
การนำโครงสร้างพื้นฐานของการร้องมาใช้ใหม่ช่วยให้สามารถแยกวิเคราะห์ภาษา C และ C ++ ที่ทันสมัยและตรวจจับอินสแตนซ์ของรหัสโคลนที่ซับซ้อนมาก
โปสเตอร์แสดงให้เห็นว่าการใช้งานที่เสนอนั้นมีประสิทธิภาพสูงกว่าโซลูชันที่มีอยู่ (ที่ฉันทราบ) ในประสิทธิภาพช่วงของโคลนรหัสที่ตรวจพบและการใช้งาน วิธีการหลายอย่างซึ่งมีจุดมุ่งหมายเพื่อความเร็วไม่สามารถโคลน Type II และ Type III ส่วนใหญ่ (โปรดดูที่ code clone taxonomy ในหมายเหตุ) ผู้ที่พยายามตรวจจับความคล้ายคลึงกันประเภทนี้มีปัญหาเรื่องประสิทธิภาพอย่างจริงจัง งานของฉันรวมประสิทธิภาพประสิทธิภาพในขณะที่ไม่จำกัดความสามารถในการตรวจจับ
รหัสที่ใช้สำหรับบทความนี้มีอยู่ในที่เก็บข้อมูลของฉัน
ตารางต่อไปนี้แสดงให้เห็นว่าแม้แต่การใช้งานการตรวจสอบรหัสโคลนที่ไร้เดียงสาก็สามารถประมวลผลโครงการโอเพนซอร์ซขนาดใหญ่และค้นหารหัสที่คล้ายกันมากมาย:
| โครงการ | เวลาสร้างปกติ | สร้างด้วยเวลา BasicloneCheck | พบโคลน |
|---|---|---|---|
| openssl | 1m26s | 9m27s | 180 |
| กระตวน | 0M26S | 2m46s | 34 |
| SDL | 0M26S | 1m59s | 170 |
ในช่วงฤดูร้อนปี 2559 ฉันเป็นผู้ฝึกงานใน Google Munich ซึ่งฉันแนะนำการปรับปรุงที่สำคัญในการส่งต่อและเริ่ม clang-refactor (ดู Design Doc สำหรับการอ้างอิง) ดังนั้นฉันจึงไม่สามารถทำงานด้านการเข้ารหัสต่อไปและมีส่วนร่วมในการอภิปรายเพียงไม่กี่ครั้ง Raphael Isemann ภายใต้การให้คำปรึกษาของ Vassil Vassilev และด้วยความช่วยเหลือของวิศวกรทีม Anlysis ของ Apple Static ทำงานได้อย่างยอดเยี่ยมในการปรับปรุงโครงสร้างพื้นฐานปัจจุบัน (ดูหน้าโครงการ GSOC) และในที่สุดก็ผลักดันรหัสไปยังที่เก็บเสียงดัง
Clang Static Analyzer ไม่สามารถผ่านข้อมูลระหว่างหน่วยการแปลและสิ่งนี้น่าเสียดายที่เป็นข้อ จำกัด อย่างมากสำหรับการตรวจจับการโคลนรหัสเนื่องจากลักษณะของมัน: โคลนส่วนใหญ่จบลงในหน่วยการแปลที่แตกต่างกันและไม่ได้รับการรายงานจากการตรวจสอบ หากมีการแก้ปัญหาที่เหมาะสมมีความจำเป็นที่จะต้องเอาชนะข้อ จำกัด ที่อธิบายไว้ งานของฉันเกี่ยวกับ clang-refactor อาจมีประโยชน์สำหรับการแก้ปัญหาที่มีประสิทธิภาพ
ฉันขอขอบคุณ Vassil Vassilev สำหรับคำแนะนำและการสนับสนุนชุมชน 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
}กระทำ 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.
