بخشی از مقاله
چکیده
در مهندسی نرم افزار مهمترین مساله، ارائه نرم افزارهای با کیفیت و با کارایی بالا و خدمات پس از فروش آن است. به همین دلیل مهندسان نرمافزار، شاخهی بخصوصی را با نام تکامل نرمافزار - Software Evolution - معرفی کردند که در آن هدف، ارتقای نرمافزارها پس از تولید آنها است. یکی از مباحث پایه در تکامل نرمافزار، تشخیص کلونیهای کد - Code Clone - یا همان تکه کد های تکراری در نرم افزارها است. در حقیقت شاید بتوان تشخیص کلونی ها را پایه تکامل نرمافزار معرفی نمود، چرا که بیشتر مباحث تکامل نرم افزار، به نوعی به تشخیص کلونی ها وابسته هستند. تاکنون روش های متنوعی، از جمله دو روش مبتنی بر رفتار - کندتر و دقیقتر - و مبتنی بر حالت حافظه - سریعتر با دقت متوسط - ارائه شدهاند.
در این پژوهش، هدف یافتن کلونهای بیشتر با دقتی مناسب نسبت به روش مبتنی بر حالت حافظه است - کاهش . - False Negative برای انجام این کار از ترکیب دو روش حالت حافظه انتزاعی - - Abstract Memory State و گراف وابستگی برنامه - - Program Dependency Graph استفاده شده است. ضمنا از روش اجرای تکه کدها با مقادیر تصادفی نیز بهره برده شده است. روش ارائه شده در این پژوهش با روش مبتنی بر حالت حافظه مقایسه شده و در نهایت، ارزیابیها نشان میدهند که این پژوهش توانسته است کلونهای نوع 3،2،1 و 4 را شناسایی کند و False Negative را کاهش دهد.
-1 مقدمه
یکی از زمینههای تحقیقاتی مهندسی نرمافزار ، تکامل نرم افزار است. در تکامل نرمافزار بحثهای مربوط به توسعه و نگهداری نرمافزار، پس از تولید آن، مطرح میشود. یکی از بخشهای مهم در تکامل نرم افزار، تشخیص کلونیهای کد - Code Clones - در نرمافزار است. با توجه به تعریف ارائه شده توسط Roy و همکارانش [1]، کلونیهای کد، تکه کدهایی هستند که به علت کپی و تکرار آن توسط توسعه دهندگان نرمافزار به صورت خواسته و یا ناخواسته، در نقاط مختلف نرم افزار به وجود میآیند.
تحقیقات گذشته نشان داده که 7 الی 23 درصد از سیستم های نرم افزاری دارای کدهای تکراری هستند [1,2,3,4,5,6] و این میزان تا 59 درصد نیز گزارش شده است.[7] بنابراین حجم قابل توجهی از نرم افزار را کلونیهای کد تشکیل میدهند. کلونی های کد می توانند فرآیند توسعه و نگهداری نرم افزار را با مشکل روبروکنند که در نهایت منجر به کاهش رضایت مندی مشتریان و افزایش هرینه ها خواهد شد.
بنابراین مساله اصلی یافتن این تکه کدها و سپس حذف، مدیریت و کنترل آن ها میباشد. از جمله مزایای تشخیص کلونیهای کد میتوان به تشخیص دزدیهای ادبی - Plagiarism Detection - ، تشخیص خطا - Bug Detection - ، شناسایی کدهای کاندید برای تبدیل برنامه به جنبه گرایی - Aspect-Oriented - - Aspect Mining - ، شناسایی ویروسها، تشخیص نقض گواهی مالکیت - License Violation - Detection و ادغام کدهای منبع اشاره کرد .[8] - Merging - در بخش زیر تعاریف اولیه و انواع کلونیهای کد ارائه شده است.
انواع کلونیهای کد
تاکنون مراجع مختلف، تقسیم بندیهای مختلفی را برای کلونیهای کد ارائه کردهاند:
نوع - Exact Clones - 1
کپی عینا کد از لحاظ متنی و دارای تفاوت در فضاهای خالی - Spaces - ، توضیحات - Comments - و قالب [Layout] [9,10]
نوع - Renamed Clones - 2
کپی کد از لحاظ نحوی - Syntactically - ، شامل تغییرات بیشتر بر روی متغیرها - Variables - ، نوعها - Types - ، شناسههای توابع - Function - Identifier و ثابتها - Literals - [9,10]
نوع - Gapped Clones - 3
کپی کد، شامل تغییرات بیشتر همچون حذف، تغییر و یا افزودن دستورات[9,10]
نوع - Semantic Clones - 4
قطعات کد مشابه از لحاظ عملکرد، اما متفاوت از لحاظ نحوی، ساختاری و متنی[10] تا کنون سه روش کلی برای شناسایی کلونهای معنایی ارائه شده است.
این روشها عبارتانداز:
روشهای مبتنی بر گراف [11,12,13] روشهای مبتنی بر رفتار[14] روشهای مبتنی بر حالت حافظه [15] مشکل اصلیای که در روشهای مبتنی بر گراف وجود دارد این است که تنها وابستگی خطوط را در نظر میگیرند و در حالت کلی تنها توانایی شناسایی کدهایی با ترتیب خطوط متفاوت را دارند و اگر دو تکه کد که شباهت ساختاری ندارند - و یا شباهت کمی دارند - و عملکرد برابری دارند، به این تکنیک ها داده شود، نمیتوانند آن کلونها را تشخیص دهند - همانند دو کد مرتبسازی اعداد با روش کاری متفاوت - . روشهای مبتنی بر رفتار، در صورتی که بتوانند از تمام تکه کدها، با توجه به تمام ورودیهای ممکن، اجرا بگیرند میتوانند روشهای بسیار دقیقی باشند.
با توجه به توضیحات ارائه شده توسط Kim و همکارانش [15]، روش ارائه شده در [14] که مبتنی بر رفتار می باشد، دارای این مشکل است که از تمام ورودیهای ممکن اجرا نمیگیرد که منجر به کاهش دقت آن می شود. از سوی دیگر روشهای مبتنی بر رفتار بسیار زمان بر هستند و همچنین نیاز به تجهیزات محاسباتی بسیار قوی دارند. روش های مبتنی بر حالت حافظه انتزاعی دارای دقتی بیشتر از روشهای مبتنی بر گراف و کمتر از روش های مبتنی بر رفتار می باشند. این روش ها دارای مزایایی همچون: زمان اجرای بسیار کم و دقتی نسبتا مناسب، میباشند.
روش ارائه شده در [15]، که مبتنی بر حالت حافظه انتزاعی می باشد، تنها کلون های تابعی را تشخیص می دهد و سطوح دانهبندی کوچکتر از تابع را نمی تواند تشخیص دهد. مشکل دیگر روش[15] این است که کدهای نامرتبط را در فرآیند ساخت حافظه انتزاعی آن تکه کد لحاظ می کند. روش های ترکیبی که توانایی تشخیص کلونی های نوع 4 را دارا باشند، تاکنون بسیار کم ارائه شده اند و تکنیک هایی هم که این توانایی را دارند - همچون روش - [13] تنها از روشهای مبتنی بر گراف بهره میبرند. در این پژوهش سعی بر این است که مشکلات مطرح شده در بالا، برطرف گردد.
روش کار به این صورت است که عمل تشخیص کلونی های موجود، با استفاده از روش حالت حافظه انتزاعی در سطوح دانه بندی کوچکتری - نسبت به تابع - [15] انجام شود. همچنین گراف وابستگی برنامه، نیز استخراج گردد و کلونیهای آن، تشخیص تشخیص داده شود که در نتیجه این دو عمل، انتظار کاهش False Negative می رود. در ادامه تحقیق به این موضوع پی برده شد که تشخیص برابری گزاره ها و عبارت های محاسباتی تنها با توجه به متن آن ها می تواند کاهش دقت را به دنبال داشته باشد. با توجه به این مساله از اجرای تکه کدها با مقادیر تصادفی نیز بهره گرفته شد.
-2 ادبیات تحقیق
با توجه به انواع کلونیهای کد، روشهای بسیاری برای یافتن این تکه کدها ارائه شده است. مراجع تقسیم بندیهای تقریبا مشابهی را برای این روشها ارائه کردهاند[9,11 ,16,17]، اما در یک جمعبندی کلی، تقسیم بندی زیر را میتوان ارائه نمود - از آنجائیکه تمرکز روش ارائه شده در این پژوهش بر روی روشهای ترکیبی و معنایی است، بیشتر ارجاعات به این روشها میباشد -
-1-2 مبتنی بر متن یا رشته - Text or String - based
دراین روشها متن خام کدهای مختلف با یکدیگر مقایسه میشوند و - معمولا - هیچگونه تبدیل و یا نرمالسازی، در این روشها انجام نمیگیرد. کاملا واضح است که در این روشها کلونهای نوع 1 شناسایی میشوند.[18]
-2-2 روشهای مبتنی بر معیار - Metric based -
در این روشها ابتدا یک سری معیار - Metric - مشخص میشود، سپس تکه های کد بر اساس این معیارها دستهبندی میشوند. در نهایت هر کدام از دسته ها شامل کلونی های کد خواهند بود. این که این روش ها بتوانند کدامیک از انواع کلونها را تشخیص دهند، رابطهی مستقیمی با معیارهای درنظر گرفته شده دارد، اما معمولا در شناسایی کلونهای نوع 1، نوع 2، نوع 3 بهکار برده میشوند.[18 ,19]
-3-2 روشهای مبتنی بر گراف - Graph based -
در این روشها، ابتدا برای کدهای منبع، گرافهای وابستگی برنامه PDG - Program Dependency Graph - ایجاد میشود که دارای یالهایی برای مشخص کردن وابستگی کنترلی - Control Dependence - و وابستکی دادهای - Data Dependence - میان دستورات برنامه میباشند. سپس این گرافها با یکدیگر مقایسه شده و کلونیهای کد شناسایی میشوند.
در گذشته روش های مبتنی بر گراف را جزء روش های شناسایی کننده کلون های نوع 4 دسته بندی میکردند، اما امروزه، این روشها در دسته روشهای تشخیص دهنده کلونهای نوع 1، نوع 2 و نوع 3 قرار گرفتهاند. هرچند همچنان برخی محققان این قبیل روشها را جزء روشهای تشخیص دهندهی کلونهای نوع 4 قرار میدهند.[11,12,13,20]
-4-2 روشهای مبتنی بر حالت حافظه - Memory - State based
در این روشها حالتهای حافظه انتزاعی - Abstract Memory State of - Code با یکدیگر مقایسه می شوند. این روش ها نیز در تشخیص کلونهای نوع 4 به کار گرفته شده اند. هرچند سرعت آن ها نسبت به روشهای مبتنی بر رفتار بیشتر بوده و هزینه ی کمتری دارند، اما تاکنون دقت و قدرت آن ها نسبت به روشهای مبتنی بر رفتار کمتر بوده است.[15]
-5-2 روشهای مبتنی بر رفتار - Behavior based -
در این روشها از تکه کدها اجرا گرفته میشود، به این صورت که به تکه کدها ورودیهای یکسان داده میشود، سپس اگر خروجی این تکه کدها با هم یکسان باشد، این تکه کدها به عنوان کد کلون معرفی میشوند. این روشها در تشخیص کلونهای نوع 4 به کار گرفته میشوند. از مزایای این روش میتوان دقت و قدرت بالا در تشخیص کلونهای کد و از معایب آن میتوان به هزینه و زمان زیاد، اشاره کرد.[14]
-6-2 روشهای مبتنی بر نشانه و یا لغوی - Lexical - or Token based
در این روشها کد منبع به یک توالی - Sequence - از نشانه ها تبدیل میشود و بعد از آن نشانهها با هم مقایسه میشوند. این روشها در شناسایی کلون های نوع 2 بسیار قدرتمند هستند که در آن ها تغییرات اندک و در حد فضاهای خالی، توضیحات و قالب است.[21,22]
-7-2 روشهای مبتنی بر درخت - Tree Based -
در این روشها ابتدا کدهای منبع به تعدادی درخت نحو انتزاعی - Abstract Syntax Tree - AST تبدیل میشوند. سپس این ASTها با یکدیگر مقایسه شده و کلونی های کد شناسایی می شوند. این روشها میتوانند کلونهای نوع 1، نوع 2 و تا حدودی نوع 3 را شناسایی کنند.[22,23]
-8-2 روشهای ترکیبی - Hybrid -
این روشها، از ترکیبی از روشهای 1-1-2 تا 7-1-2 برای تشخیص کلونها استفاده میکنند. همچنین مراجع، هرتکنیکی را که از روشهای -2 1-1 تا 7-1-2 استفاده نمیکنند، جزء این روشها به حساب میآورند,31] .[13 ,18 ,22 ,24 ,25 ,26 ,27 ,28 ,29 ,30
-3 شرح کلی سیستم
متغیرهای تعریف شده به تفکیک نوع آنها استخراج میشوند. سپس شرطهای موجود استخراج شده و گزاره برای متغیرها با توجه به عبارت انتساب یافته به آنها ایجاد میشود. حال با توجه به گزاره استخراج شده و عبارت منتسب به هر متغیر، یک گزاره ایجاد و برای هر متغیر ذخیره میشود. یک گراف وابستگی نیز برای برنامه ایجاد میگردد که هر کدام از گرههای آن مربوط به یکی از خطوط برنامه است.
سپس وارد مرحله نرمال سازی ثانویه میشود. در این مرحله برای هر خط از کد، یک مقدار هش کد تولید میشود و تا حد امکان سعی میشود اثر جابهجایی متغیرها و تفاوت نام آنها از بین برود تا کد هش تولید شده در دو کد ورودی به یکدیگر نزدیکتر باشند. در ادامه خروجی دو مرحله آنالیز لغوی و نرمالسازی ثانویه به مراحل "مقایسه گراف وابستگی برنامه دو کد منبع" و همچنین "مقایسه حافظه انتزاعی متغیرهای دو کد منبع" ارسال میشوند.
در مرحله مقایسه گراف وابستگی برنامه دو کد منبع، مقادیر کد هش تمام خطوط به صورت دو به دو با یکدیگر مقایسه میشوند - برابری گراف - و تا حد امکان، این دو گراف پیمایش شده و مقادیر هش خطوط با یکدیگر مقایسه میشوند و در نهایت این شباهتها به عنوان کلون در خروجی به چاپ میرسند. در مرحله مقایسه حافظه انتزاعی متغیرهای دو کد منبع، حافظه انتزاعی متغیرها به صورت دوبهدو با یکدیگر مقایسه میشوند و در صورت برابری، وابستگیهای کنترلی و دادهای آنها استخراج شده و به صورت جداگانه در خروجی به چاپ میرسند. الگوریتمهای 1 - ،2و - 3 عملیات شرح داده شده را نشان میدهد. در ادامه تمام مراحل مذکور به همراه عملکرد الگوریتم شرح داده خواهند شد.
- 1 - الگوریتم DSCCD
- 2 - الگوریتم FindAMSClones
- 3 - الگوریتم FindPDGClones
ابتدا همانند تمام روش های تشخیص کلون، میبایستی یک نرمالسازی اولیه برروی کدهای ورودی انجام گیرد تا زوائد از متن ورودی حذف گردد. سپس کدهای نرمال شده به مرحله آنالیز لغوی ارسال میشوند.
