ارائه راهکاری برای انتخاب و اولویت‌دهی موارد تست رگرسیون مبتنی بر رهیافت ژنتیک WORD
 چکیده
بسیاری از هزینه‌های توسعه نرم‌افزار، مربوط به آزمون‌های مکرر، در مرحله نگهداری نرم‌افزار در حال تکامل و اصلاح است؛ زیرا ایجاد هر تغییر در کد نرم‌افزار، نسخه‌ی جدیدی به دست می‌دهد که درستی یابی آن، نیازمند طراحی آزمون‌های جدید و نیز انجام مجدد تمام آزمون‌های قبلی، برای اطمینان از عدم تأثیرپذیری نامطلوب عملکرد جاری نرم‌افزار از تغییرات صورت گرفته است. این فرایند آزمون رگرسیون نرم‌افزار نامیده می‌شود. به دلیل محدودیت منابع و زمان آزمون، نمی‌توان کل این حجم زیاد و رو به توسعه آزمون‌ها را در هر دور تکرار آزمون، مجددا اجرا کرد. یکی از مهم‌ترین فنون ارائه‌شده برای غلبه بر مشکل هزینه‌ی زیاد آزمون رگرسیون نرم‌افزار، انتخاب و اولویت‌دهی موارد آزمون است که منظور از آن، انتخاب و اجرای مهم‌ترین موارد آزمون، برحسب معیار شایستگی برای دستابی سریع‌تر به هدف آزمون است. مشکل اغلب فنون انتخاب و اولویت‌دهی ارائه‌شده، نادیده گرفتن پیاپی بودن اجرای آزمون رگرسیون، تأثیرگذاری کارایی آزمون‌ها در هر تکرار آزمون رگرسیون بر کارایی مراحل بعدی، تفاوت بین هزینه آزمون و دشواری خطا و نیز محدودیت زمان و منابع در محیط واقعی اجرای آزمون است. در این پایان‌نامه، روشی برای انتخاب و اولویت‌دهی موارد آزمون مبتنی بر پیشینه و آگاه از هزینه با استفاده از الگوریتم ژنتیک بر پایه‌ی پنج معیار سابقه‌ی کارایی کشف خطای موارد آزمون، احتمال انتخاب پیشین، پیشینه‌ی اجرای آن‌ها در جریان اجراهای متعدد آزمون رگرسیون، هزینه آزمون و دشواری خطا ارائه‌شده است که اثر محدودیت منابع بر اجرای آزمون‌ها نیز اعمال‌شده است. برای ارزیابی کمی سرعت آشکارسازی خطا برای روش پیشنهادی، پیاده‌سازی انجام شد که ارزیابی با استفاده از متریک APFDcانجام‌شده است. مقایسه عملکرد روش پیشنهادی با روش مبتنی بر پیشینه و روش تصادفی، انجام‌گرفته است. نتایج ارائه‌شده در پایان‌نامه، حاکی از بهبود حدود 30 % در سرعت و آشکارسازی خطای زودتر روش پیشنهادی نسبت به روش‌های مورد مقایسه است. واژه‌های کلیدی: آزمون رگرسیون نرم‌افزار، انتخاب موارد آزمون، اولویت‌دهی موارد آزمون، اولویت‌دهی مبتنی بر پیشینه، آگاه از هزینه فهرست مطالب عنوان صفحه فصل 1: مقدمه1 1-1- هدف2 1-2- انگیزه3 1-3- مروری بر روش‌های ارائه‌شده4 1-4- نوآوری بر روش‌های ارائه‌شده5 1-5- رئوس مطالب سایر فصل‌ها6 فصل 2: اصول و مبانی نظری و پیشینه تحقیق7 2-1- مقدمه8 2-2- تعاریف اصول و مبانی نظری9 2-2-1- فرایند آزمون نرم‌افزار9 2-2-2- الگوریتم ژنتیک17 2-3- مروری بر ادبیات آزمون25 2-3-1- آزمون رگرسیون نرم‌افزار25 2-3-2- آزمون مجدد کامل26 2-3-3- آزمون رگرسیون انتخابی27 2-3-4- کاهش مجموعه آزمون33 2-3-5- اولویت‌دهی موارد آزمون34 2-3-6- کارهای پیشین40 2-4- نتیجه‌گیری61 فصل 3: روش پیشنهادی63 3-1- مقدمه64 3-2- ایده عملکرد و ایرادات روش انتخاب و اولویت‌دهی موجود65 3-2-1- روش پیشنهادی67 3-3- نتیجه‌گیری80 فصل 4: نتایج و تفسیر آن‌ها82 4-1- مقدمه83 4-2- متریک ارزیابی83 4-3- شرح آزمایش‌ها85 4-4-تحلیل نتایج86 4-5- نتیجه‌گیری89 فصل۵: جمع‌بندی و پیشنهادها91 ۵-1- مقدمه92 5-2- یافته‌ها و دستاوردهای تحقیق93 5-4- پیشنهادها94 مراجع95 پیوست99 فهرست شکل‌ها عنوان صفحه شکل (2-1): دسته‌بندی تکنیک‌های آزمون نرم‌افزار ازنظر کاربرد [19] 13 شکل (2-2): چرخه نگهداری و آزمون رگرسیون ]62[26 شکل (2-3): ارتباط بین کلاسهای آزمون [26]28 شکل (2-4): مجموعه آزمون با اطلاعات تشخیص خطا واضح است که اجرای مورد آزمون C و بعدش E سودمندتر است [38]35 شکل (2-5): فلوچارت الگوریتم ژنتیک با استفاده از تکامل برای انتخاب زیرمجموعه جهش و مورد آزمون]50[ 43 شکل (2-6) الگوریتم اولویت‌دهی GA ]54[ 52 شکل (2-7) الگوریتم برای محاسبه مقدار پیشینه ]58[ 56 شکل (3-1) نمونه‌ی از کروموزوم70 شکل (3-2) شبه کد الگوریتم پیشنهادی71 شکل (3-3) شبه کد تولید زیرمجموعه مورد آزمون در الگوریتم ژنتیک72 شکل (3-4) شبه کد تولید جمعیت اول در الگوریتم ژنتیک73 شکل (3-5) شبه کد انتخاب والد در الگوریتم ژنتیک74 شکل (3-6) شبه کد ترکیب در الگوریتم ژنتیک75 شکل (3-7) نمونه از کاربرد ترکیب در الگوریتم ژنتیک76 شکل (3-8) شبه کد جهش در الگوریتم ژنتیک76 شکل (3-9) نمونه‌ی از کاربرد جهش در الگوریتم ژنتیک77 شکل (3-10) مروری بر روش پیشنهادی78 شکل (4-1): روند بهبود معیار APFDc در هر بار اجرای الگوریتم ژنتیک86 شکل (4-2) مقایسه روش پیشنهادی ازنظر APFDc 87 شکل (4-3) مقایسه روش پیشنهادی ازنظر APFD 88 شکل (4-4) تأثیر اعمال محدودیت روی روش پیشنهادی با معیار APFDc 88 شکل (4-5) تأثیر اعمال محدودیت روی روش پیشنهادی با معیار APFD 89
فهرست جدول‌ها عنوان صفحه جدول (3-1) نمونه ای از موارد آزمون و خطاهای شناسایی‌شده و هزینه و پوشش 79 جدول(3-2) ترتیب انتخاب موارد آزمون و اجرای آزمون رگرسیون79 جدول( 3-3) نمونه‌ی از خطا و دشواری خطا80 فصل 1: مقدمه 1-1- هدف در فاز توسعه و نگهداری نرم‌افزار بـرای رفـع خطاهـای موجـود در نرم‌افزار و همچنین پیاده‌سازی تغییراتی که در برنامـه ایجادشده است، متناوبا نرم‌افزار اصلاح می‌شود و تغییراتـی در آن داده می‌شود. پس از هر تغییر در نرم‌افزار، برای بررسی اینکه رفتار بر روی قسمت‌های بلا تغییر تاثیری نداشته باشد و همچنین بـرای اعتبارسـنجی مجدد، آزمون‌های فعلـی را تکرار می‌کنند. درعین‌حال اعتبارسنجی قسمت‌های تغییریافته نرم‌افزار هر بار نیازمند طراحی تعدادی آزمون‌های جدید است که به‌این‌ترتیب حجم آزمون‌های نرم‌افزار مرتباً رو به افـزایش اسـت. بنـابراین، ایـن فـاز ضروری در توسعه محصول نـرم افـزاری کـه بـرای آشکارسـازی عیـوب نرم‌افزار و مشــخص کــردن ســطح کیفــی آن بــا توجــه بــه یکســری خصوصیات منتخب، انجام می‌شود [1]، بسـیاری از هزینه‌های توسـعه نرم‌افزار (بین 30 تا 50 درصـد) را بـه خـود اختصـاص می‌دهند. ایـن آزمون‌های مکرر در مرحله نگهداری نرم‌افزار در حال تکامل و اصـلاح که با ایجاد هر تغییر در کد نرم‌افزار، برای اطمینان از عدم تأثیرپذیری نامطلوبِ بخش‌های اصلاح‌نشده کد از تغییرات صورت می‌گیرد آزمون رگرسیون نرم‌افزار[1] نامیده می‌شود. به دلیل محدودیت زمـان و منـابعِ در دسـترس بـرای گـروه آزمـون در دنیای واقعی، آزمون کامل اغلب غیرعملی است [2،1]. روش‌های گونـاگونی برای حل مشکل هزینه زیاد آزمون رگرسیون ارائه‌شده اسـت. در بـین این روش‌ها، سه روش عمده که بر پایـه اسـتفاده مجـدد از مخـزن آزمـون اســتوارند عبارت‌اند از: ” آزمــون رگرسیون انتخابی “، ”کاهش مجموعه آزمون“ و ”اولویت‌دهی موارد آزمون[2]“ [2]. روش آزمــون رگرسیون انتخابی از اطلاعات درباره برنامه، برنامه اصلاح‌شده و موارد آزمونی که برای زیرمجموعه آزمون انتخاب می‌شود، استفاده می‌کند. تکنیک‌های انتخاب آزمون معمولاً کد منبع برنامه را استفاده می‌کنند برای تعیین اینکه کدام مورد آزمون بهتر است در طول مرحله آزمون رگرسیون اجرا شود [3]. یکی از اهداف مهم انتخاب موارد آزمون افزایش نرخ قابلیت تشخیص خطا هست. روش اولویت‌دهی موارد آزمون تلاش می‌کند بـا ترتیـب دهـی اجـرای مـوارد آزمون بر اساس یک معیار شایستگی به بهبود آزمـون رگرسـیون نـرم افزاری بپردازد به‌گونه‌ای که مهم‌ترین‌ها ابتدا اجرا شوند. یکی از اهداف عمده [4] در اولویت‌دهی موارد آزمون این اسـت کـه بـا اجـرای مـوارد آزمونی که تعداد بیشتری از خطاها را اجرا می‌کنند، متوسـط کشـف خطا را در طول اجرای آزمون تا جای ممکن افـزایش داد تـا بـا کشـف سریع‌تر این خطاها امکان بازخورد سریع‌تر بـه گروه توسـعه نرم‌افزار و ارسال آن برای ویرایش و تصحیح خطا میسر شود. با این کار می‌توان مطمئن بود که در صورت توقف و ناتمام ماندن جریان آزمون در هرجا، مؤثرترین آزمون‌ها انجام‌گرفته و حداکثر خطاهای موجود کشف‌شده‌اند. هدف ما بهبود در این روش‌هاست. آزمــون رگرسیون انتخابی را برای افزایش سرعت انجام فاز آزمون استفاده می‌کنند، در این روش بر اساس معیارهای که از قبل تعیین‌شده است از میان مجموعه آزمون تعدادی را انتخاب می‌کنند. آزمــون رگرسیون انتخابی به دنبال حداقل کردن دنباله آزمون است که اکثراً آگاه از اصلاحات است. انتخاب مورد آزمون فقط روی نسخه جاری استفاده می‌شود اما روی قسمتی از برنامه تمرکز می‌کند که اصلاح‌شده است[5]. مسئله اولویت‌دهی موارد آزمون در حقیقت تعیـین جایگشـتی از کلیـه موارد آزمون موجود در رشته آزمون است، به‌گونه‌ای که ایـن ترتیـبِ اجرا، آشکارکننده حـداکثر خطاهـای ممکـن باشـد؛ بنابراین مسـئله اولویت‌دهی موارد آزمون در حقیقت یک مسئله جستجو اسـت کـه در مراجع این مسئله و پیچیـدگی آن را معـادل بـا مسـئله کوله‌پشتی می‌دانند کـه NP-hard بـوده و بـدون راه‌حل قطعـی اسـت. لـذا راه‌حل‌های موجود برای مسئله اولویت‌دهی موارد آزمون الزاماً مکاشـفه ای هستند و از طرفی هیچ‌یک جواب بهینه محسوب نمی‌شوند [2]. در سال 1997 نخستین تعریف رسمی از مسـئله انتخاب و اولویت‌دهی مـوارد آزمون و نیز متریک APFD[3] که درصد میانگین خطاهای کشف‌شده در اجرای مجموعه آزمون است، برای ارزیابی روش‌های انتخاب و اولویت‌دهی آزمون ازلحاظ احتمال کشف زودتر خطاها ارائه شد [2]؛ اما این متریک دو محدودیت دارد، اول آنکه دشواری خطاها را یکسان در نظر می‌گیرد و دوم اینکه هزینه هر مورد آزمون را یکسان در نظر می‌گیرد؛ بنابراین معیار APFDc[4] درصد میانگین خطاهای کشف‌شده در هزینه معرفی شد تا این محدودیت را از بین ببرند. 1-3- مروری بر روش‌های ارائه‌شده در اغلب روش‌های اولویت‌دهی موجود، دید محدودشده ای وجـود دارد و مدلی کـه محققـان در مطالعـات تجربی‌شان بـرای آزمـون رگرسـیون استفاده کرده‌اند، آن را به‌صورت یک آزمـون ”یک‌دفعه ای “در نظـر گرفته‌اند درحالی‌که مدل مناسب برای آزمـون رگرسـیون کـه نشـانگر خصوصیات آن باشد، آزمونی ”مداوم “ و ”درازمدت“ است و به‌طور سلسله وار بعد از هر تغییر در نرم‌افزار اجـرا می‌شود، به‌گونه‌ای کـه کارایی هر کدام از آن‌ها بر آزمون‌های بعدی مؤثر است. در همین راستا در [6] نخستین بار بحـث ”حافظه‌دار کـردن“ آزمـون رگرســیون و اســتفاده از اطلاعــات پیشــینه کــارایی مــوارد آزمــون، در اولویت‌دهی مجموعه آزمون مطرح گردید. روش مکاشفه‌ای ارائه‌شده در [6] درواقع ترکیبی است از ”روش انتخابِ مبتنی بر پیشینه در آزمـون “و سپس اولویت‌دهی موارد آزمون. به‌این‌ترتیب کـه در هـر رگرسیون گام از پیشینه اجرای موارد آزمون، برای انتخاب‌های بعدی موارد آزمـون استفاده می‌شود و در هر مرحله زیرمجموعه ای از مجموعـه آزمـون اولیه (بدون کاهش دائمی آن) را برای اولویت‌دهی و اجرا بر روی نسخه جدید نرم‌افزار انتخاب می‌کند. نشـان داده‌شده اسـت کـه [6] چنـین مکاشفه ای می‌تواند باگذشت اجراهای طولانی، هزینه را کـاهش داده و کارایی آزمون رگرسیون را در محیط‌های توسعه محـدودیت دار کـاهش دهد. مشکل روش پیشینه محورِ جاری در این است کـه در اطلاعـات پیشـینه اجرای موارد آزمون، تنها اثر ”اخیراَ “ اجراشدن نشدن مورد آزمون و یا آشکارسازی خطا یا عدم آن در اجرای قبل، آن‌هم ”به‌صورت صـفر و یک “ در رابطه بازگشتی احتمال انتخاب موارد آزمون در نظـر گرفته‌شده است. درحالی‌که برای اولویت‌دهی کـارای پیشـینه محـور، هـم کارایی کشف خطا در طول اجراها بایـد در نظـر گرفتـه شـود و هـم از اولویت‌دهی پایین و منسوخ شدن دائمی یکسری از آزمون‌ها بایسـتی جلوگیری شود. فضل علیزاده و همکاران در [7]یک روش اولویت‌دهی مبتنی بر پیشینه را پیشنهاد کردند. این روش سه نوع اطلاعات پیشینه در مورد موارد آزمون مانند تعداد اجراها و تعداد زمان‌های کشف خطا را در یک رابطه ترکیب کرده است. آن‌ها به هر یک از این معیارها ضریب ثابتی می‌دهند، بنابراین هر معیار روی احتمال انتخاب تأثیر ثابتی دارد، سپس احتمال انتخاب محاسبه می‌شود و موارد آزمون به‌صورت نزولی ازنظر احتمال انتخاب زمان‌بندی می‌شوند. خلیلیان و همکاران در [8] رابطه ی برای اولویت‌دهی مورد آزمون ارائه دادند که از اطلاعات پیشینه استفاده می‌کند. ایده این روش این است که هر بخش از رابطه اولویت‌دهی باید تأثیر خاصی روی اولویت مورد آزمون داشته باشد و این تأثیرات ممکن است در طول آزمون رگرسیون متوالی تغییر کنند. آن‌ها رابطه ی ارائه دادند که از ضرایب متغیر بهبودیافته استفاده می‌کند، این متغیرها بر اساس دسترسی به پیشینه داده کارا هستند، پیشینه اطلاعات کارایی در هر مورد آزمون بر اساس همه مراحل آزمون است نه‌فقط در آزمون مرحله قبل. آن‌ها معتقدند که بر اساس داده‌های پیشینه و شرایط هر مرحله آزمون، هر نوع از اطلاعات باید تأثیر مناسبی روی تعیین احتمال هر مورد آزمون داشته باشند، تأثیر می‌تواند خیلی ناچیز و یا خیلی زیاد باشد. 1-4- نوآوری بر روش‌های ارائه‌شده در روش پیشنهادی در این پایان‌نامه، به ارائه راه حلی برای انتخاب و اولویت‌دهی مبتنی بر پیشینه موارد آزمون در هر گام اجرا، از سابقه کارایی موارد آزمون در کشـف خطـا و نیـز سـالمندی مـوارد آزمـون استفاده می‌شود به گونه‌ی که در هر بار اجرای آزمون رگرسیون موارد آزمون جدید انتخاب و اولویت‌دهی شوند. از طرفی هر مورد آزمون هزینه و دشواری مخصوص به خود را دارد که در هیچ‌یک از روش‌های ارائه‌شده به آن نپرداخته‌اند؛ بنابراین در این پایان‌نامه با استفاده از روش فرا ابتکاری ژنتیک مناسب‌ترین زیرمجموعه از موارد آزمون از طریق روش‌های مبتنی بر پیشینه انتخاب می‌شود و با تابع برازندگی مناسب اولویت‌دهی می‌شود تا درنهایت معیار APFDc افزایش یابد.
جهت کپی مطلب از ctrl+A استفاده نمایید نماید |
