code clone detection llvm devmtg15 poster
1.0.0
يحتوي هذا المستودع على رمز مصدر اللاتكس لملصق "الكشف عن استنساخ الكود في محلل Clang Static".
نسخة PDF.
تم إعداد الملصق لاجتماع مطور LLVM لعام 2015. اجتماع مطوري LLVM هو أكبر مؤتمر لأخصائيي البرمجيات من جميع أنحاء العالم الذي يقام كل عام. يحضر العشرات من المهندسين الذين يعملون في Google و Apple و Intel المؤتمر وتبادل الخبرة القيمة.
نتج عن هذا البحث alpha.clone.CloneChecker في Clang Static Analyzer. هذا الفحص قادر على اكتشاف جزء من ما كان التنفيذ الأصلي قادرًا على اكتشافه ، ولكنه أكثر استقرارًا وجاهزة للإنتاج.
تقدم اختبارات الوحدة نظرة عامة جيدة على قطع الرمز ، والتي يمكن اكتشافها عن طريق تطبيق المنبع الحالي. CloneChecker هو جزء من محلل Clang Static ، والذي يتم شحنه مع Clang 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 ، وهو مترجم C ++ التفاعلي المستخدم في CERN.
لا تحتوي صفحة مشروع GSOC للأسف على الكثير من المعلومات بسبب نقص المعرفة بأن جزءًا كبيرًا من الملخص الذي كتبته لن يكون متاحًا من هناك. على الرغم من ذلك ، يحتوي هذا الملصق على نظرة عامة واسعة على العمل الذي تم خلال صيف 2015.
على الرغم من كون الكشف عن استنساخ التعليمات البرمجية موضوعًا شائعًا للغاية على مدار السنوات الماضية ، لم يكن هناك حل جيد ، والذي كان قابلاً للتوسعة ومفتوحة وسهلة الاستخدام وسيقوم بالفعل بعمله جيدًا. في حين أن بعض الحلول موجودة لم يستفيد معظمها من تقنيات التحويل البرمجي الحديثة ، تؤدي المحاولات الساذجة للغاية إلى اكتشاف جزء صغير من استنساخ التعليمات البرمجية الموجود على نطاق واسع.
العديد من الأوراق البحثية المقترحة النهج النصية ، والتي ليست قابلة للتطوير وغير فعالة. ركزت محاولات قليلة فقط (وأبرزها ، هذه المجموعة) على تحليل AST ، مما يعطي نتائج أفضل بكثير. الاستفادة من إعادة استخدام البنية التحتية للتجميع ، والتي توفر AST الغنية لـ C ، C ++ و Objective-C ، تؤدي إلى حل أفضل.
تتيح إعادة استخدام البنية التحتية لـ Clang تحليل لهجات C و C ++ الحديثة واكتشاف مثيلات استنساخ رمز متطورة للغاية.
يوضح الملصق أن التنفيذ المقترح يتفوق على الحلول الحالية (تلك التي أعرفها) في الأداء ، ومجموعة من استنساخ التعليمات البرمجية المكتشفة وسهولة الاستخدام. العديد من الأساليب ، التي تهدف إلى السرعة ، غير قادرة على معظم استنساخ النوع الثاني والنوع الثالث (يرجى الرجوع إلى تصنيف Code Clone في الملاحظات). أولئك الذين يحاولون اكتشاف المزيد من أنواع التشابه لديهم مشكلة في الأداء الخطيرة. يجمع عملي بين كفاءة الأداء مع عدم الحد من قدرات الكشف.
الرمز المستخدم في هذه الورقة متاح في مستودع شوكة Clang.
يوضح الجدول التالي أنه حتى التنفيذ الساذج للتحقق من استنساخ التعليمات البرمجية قادر على معالجة مشاريع ضخمة مفتوحة المصدر والعثور على العديد من القطع المماثلة:
| مشروع | وقت البناء العادي | بناء مع الوقت الأساسي | تم العثور على الحيوانات المستنسخة |
|---|---|---|---|
| OpenSSL | 1M26S | 9m27s | 180 |
| غيت | 0M26S | 2M46S | 34 |
| SDL | 0M26S | 1M59S | 170 |
خلال صيف 2016 ، كنت متدربًا في Google Munich ، حيث أدخلت تحسينات كبيرة على Clang-Rename وبدأت Clang-Refactor (انظر Design Doc للرجوع إليها). لذلك لم أتمكن من مواصلة عملي على جانب الترميز وشاركت فقط في بعض المناقشات. قام Raphael Isemann تحت إشراف Vassil Vassilev وبمساعدة من مهندسي فريق Apple Static Anlysis بعمل رائع في تحسين البنية التحتية الحالية (انظر صفحة مشروع GSOC) وأخيراً دفع الكود إلى مستودع Clang.
لم يكن Clang Static Analyzer قادرًا على تمرير المعلومات بين وحدات الترجمة ، وهذا ، للأسف ، يعد قيودًا ضخمة للكشف عن استنساخ التعليمات البرمجية بسبب طبيعته: معظم الحيوانات المستنسخة تنتهي في وحدات ترجمة مختلفة ولا يتم الإبلاغ عنها بواسطة الشيك. إذا كان هناك حل مناسب ، فهناك حاجة للتغلب على القيد الموصوف. قد يصبح عملي على clang-refactor مفيدًا لحل فعال.
أود أن أشكر Vassil Vassilev على التوجيه والدعم ، مجتمع LLVM على الاقتراحات العظيمة وجميع الأعمال التي تم القيام بها من أجل دعم المساهمين الجدد ، وبالطبع Google - على خلق فرصة رائعة للطلاب من جميع أنحاء العالم والتمويل.
بالمقارنة مع مشاريع C ++ ، فإن المشاريع المكتوبة في C تعاني من قضايا تكرار الكود بشكل كبير.
يمكن لفت قطع الكود التالية بسهولة في وظائف لمنع الأخطاء المحتملة ، مثل إصلاح الخلل في إحدى مثيلات الاستنساخ وتجاهل الآخرين.
تمكنت أكثر من ذلك بقليل من التحليل من تحديد حوالي 500 كود كبير (انظر الأمثلة التالية) استنساخ رمز.
مشروع التزام المستخدمة للتحليل: B77B6127E8DE38726F37697BBBC736SED7B49771.
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] كمرجع على تصنيف Code Clone ، انظر الورقة الحديثة إلى حد ما من قبل Roy et al.
