چکیدهبسیاری از هزینه‌های توسعه نرم‌افزار، مربوط به آزمون‌های مکرر، در مرحله نگهداری نرم‌افزار در حال تکامل و اصلاح است؛ زیرا ایجاد هر تغییر در کد نرم‌افزار، نسخه‌ی جدیدی به دست می‌دهد که درستی یابی آن، نیازمند طراحی آزمون‌های جدید و نیز انجام مجدد تمام آزمون‌های قبلی، برای اطمینان از عدم تأثیرپذیری نامطلوب عملکرد جاری نرم‌افزار از تغییرات صورت گرفته است. این فرایند آزمون رگرسیون نرم‌افزار نامیده می‌شود. به دلیل محدودیت منابع و زمان آزمون، نمی‌توان کل این حجم زیاد و رو به توسعه آزمون‌ها را در هر دور تکرار آزمون، مجددا اجرا کرد. یکی از مهم‌ترین فنون ارائه‌شده برای غلبه بر مشکل هزینه‌ی زیاد آزمون رگرسیون نرم‌افزار، انتخاب و اولویت‌دهی موارد آزمون است که منظور از آن، انتخاب و اجرای مهم‌ترین موارد آزمون، برحسب معیار شایستگی برای دستابی سریع‌تر به هدف آزمون است. مشکل اغلب فنون انتخاب و اولویت‌دهی ارائه‌شده، نادیده گرفتن پیاپی بودن اجرای آزمون رگرسیون، تأثیرگذاری کارایی آزمون‌ها در هر تکرار آزمون رگرسیون بر کارایی مراحل بعدی، تفاوت بین هزینه آزمون و دشواری خطا و نیز محدودیت زمان و منابع در محیط واقعی اجرای آزمون است. در این پایان‌نامه، روشی برای انتخاب و اولویت‌دهی موارد آزمون مبتنی بر پیشینه و آگاه از هزینه با استفاده از الگوریتم ژنتیک بر پایه‌ی پنج معیار سابقه‌ی کارایی کشف خطای موارد آزمون، احتمال انتخاب پیشین، پیشینه‌ی اجرای آن‌ها در جریان اجراهای متعدد آزمون رگرسیون، هزینه آزمون و دشواری خطا ارائه‌شده است که اثر محدودیت منابع بر اجرای آزمون‌ها نیز اعمال‌شده است.برای ارزیابی کمی سرعت آشکارسازی خطا برای روش پیشنهادی، پیاده‌سازی انجام شد که ارزیابی با استفاده از متریک APFDcانجام‌شده است. مقایسه عملکرد روش پیشنهادی با روش مبتنی بر پیشینه و روش تصادفی، انجام‌گرفته است. نتایج ارائه‌شده در پایان‌نامه، حاکی از بهبود حدود 30 % در سرعت و آشکارسازی خطای زودتر روش پیشنهادی نسبت به روش‌های مورد مقایسه است.واژه‌های کلیدی: آزمون رگرسیون نرم‌افزار، انتخاب موارد آزمون، اولویت‌دهی موارد آزمون، اولویت‌دهی مبتنی بر پیشینه، آگاه از هزینهفهرست مطالبعنوان صفحهفصل 1: مقدمه11-1- هدف21-2- انگیزه31-3- مروری بر روش‌های ارائه‌شده41-4- نوآوری بر روش‌های ارائه‌شده51-5- رئوس مطالب سایر فصل‌ها6فصل 2: اصول و مبانی نظری و پیشینه تحقیق72-1- مقدمه82-2- تعاریف اصول و مبانی نظری92-2-1- فرایند آزمون نرم‌افزار92-2-2- الگوریتم ژنتیک172-3- مروری بر ادبیات آزمون252-3-1- آزمون رگرسیون نرم‌افزار252-3-2- آزمون مجدد کامل262-3-3- آزمون رگرسیون انتخابی272-3-4- کاهش مجموعه آزمون332-3-5- اولویت‌دهی موارد آزمون342-3-6- کارهای پیشین402-4- نتیجه‌گیری61فصل 3: روش پیشنهادی633-1- مقدمه643-2- ایده عملکرد و ایرادات روش انتخاب و اولویت‌دهی موجود653-2-1- روش پیشنهادی673-3- نتیجه‌گیری80فصل 4: نتایج و تفسیر آن‌ها824-1- مقدمه834-2- متریک ارزیابی834-3- شرح آزمایش‌ها854-4-تحلیل نتایج864-5- نتیجه‌گیری89فصل۵: جمع‌بندی و پیشنهادها91۵-1- مقدمه925-2- یافته‌ها و دستاوردهای تحقیق935-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] در اولویت‌دهی موارد آزمون اين اسـت كـه بـا اجـراي مـوارد آزموني كه تعداد بيشتري از خطاها را اجرا می‌کنند، متوسـط كشـف خطا را در طول اجراي آزمون تا جاي ممكن افـزايش داد تـا بـا كشـف سریع‌تر اين خطاها امكان بازخورد سریع‌تر بـه گروه توسـعه نرم‌افزار و ارسال آن براي ويرايش و تصحيح خطا ميسر شود. با اين كار می‌توان مطمئن بود كه در صورت توقف و ناتمام ماندن جريان آزمون در هرجا، مؤثرترين آزمون‌ها انجام‌گرفته و حداكثر خطاهاي موجود کشف‌شده‌اند. هدف ما بهبود در این روش‌هاست.1-2- انگیزهآزمــون رگرسیون انتخابی را برای افزایش سرعت انجام فاز آزمون استفاده می‌کنند، در این روش بر اساس معیارهای که از قبل تعیین‌شده است از میان مجموعه آزمون تعدادی را انتخاب می‌کنند. آزمــون رگرسیون انتخابی به دنبال حداقل کردن دنباله آزمون است که اکثراً آگاه از اصلاحات است. انتخاب مورد آزمون فقط روی نسخه جاری استفاده می‌شود اما روی قسمتی از برنامه تمرکز می‌کند که اصلاح‌شده است[5].مسئله اولویت‌دهی موارد آزمون در حقيقت تعيـين جايگشـتي از كليـه موارد آزمون موجود در رشته آزمون است، به‌گونه‌ای كه ايـن ترتيـبِ اجرا، آشکارکننده حـداكثر خطاهـاي ممكـن باشـد؛ بنابراین مسـئله اولویت‌دهی موارد آزمون در حقيقت يك مسئله جستجو اسـت كـه در مراجع اين مسئله و پيچيـدگي آن را معـادل بـا مسـئله کوله‌پشتی می‌دانند كـه NP-hard بـوده و بـدون راه‌حل قطعـي اسـت. لـذا راه‌حل‌های موجود براي مسئله اولویت‌دهی موارد آزمون الزاماً مكاشـفه اي هستند و از طرفي هیچ‌یک جواب بهينه محسوب نمی‌شوند [2].در سال 1997 نخستين تعريف رسمي از مسـئله انتخاب و اولویت‌دهی مـوارد آزمون و نيز متريك APFD[3] كه درصد میانگین خطاهاي کشف‌شده در اجراي مجموعه آزمون است، براي ارزيابي روش‌های انتخاب و اولویت‌دهی آزمون ازلحاظ احتمال كشف زودتر خطاها ارائه شد [2]؛ اما این متریک دو محدودیت دارد، اول آنکه دشواری خطاها را یکسان در نظر می‌گیرد و دوم اینکه هزینه هر مورد آزمون را یکسان در نظر می‌گیرد؛ بنابراین معیار APFDc[4] درصد میانگین خطاهاي کشف‌شده در هزینه معرفی شد تا این محدودیت را از بین ببرند.1-3- مروری بر روش‌های ارائهشدهدر اغلب روش‌های اولویت‌دهی موجود، ديد محدودشده اي وجـود دارد و مدلي كـه محققـان در مطالعـات تجربی‌شان بـراي آزمـون رگرسـيون استفاده کرده‌اند، آن را به‌صورت يك آزمـون ”یک‌دفعه اي “در نظـر گرفته‌اند درحالی‌که مدل مناسب براي آزمـون رگرسـيون كـه نشـانگر خصوصيات آن باشد، آزموني ”مداوم “ و ”درازمدت“ است و به‌طور سلسله وار بعد از هر تغيير در نرم‌افزار اجـرا می‌شود، به‌گونه‌ای كـه كارايي هر كدام از آن‌ها بر آزمون‌های بعدي مؤثر است.در همين راستا در [6] نخستين بار بحـث ”حافظه‌دار كـردن“ آزمـون رگرســيون و اســتفاده از اطلاعــات پيشــينه كــارايي مــوارد آزمــون، در اولویت‌دهی مجموعه آزمون مطرح گرديد. روش مکاشفه‌ای ارائه‌شده در [6] درواقع تركيبي است از ”روش انتخابِ مبتني بر پیشینه در آزمـون “و سپس اولویت‌دهی موارد آزمون. به‌این‌ترتیب كـه در هـر رگرسيون گام از پيشينه اجراي موارد آزمون، براي انتخاب‌های بعدي موارد آزمـون استفاده می‌شود و در هر مرحله زیرمجموعه اي از مجموعـه آزمـون اوليه (بدون كاهش دائمي آن) را براي اولویت‌دهی و اجرا بر روي نسخه جديد نرم‌افزار انتخاب می‌کند. نشـان داده‌شده اسـت كـه [6] چنـين مكاشفه اي می‌تواند باگذشت اجراهاي طولاني، هزينه را كـاهش داده و كارايي آزمون رگرسيون را در محیط‌های توسعه محـدوديت دار كـاهش دهد.مشكل روش پيشينه محورِ جاري در اين است كـه در اطلاعـات پيشـينه اجراي موارد آزمون، تنها اثر ”اخيراَ “ اجراشدن نشدن مورد آزمون و يا آشكارسازي خطا یا عدم آن در اجراي قبل، آن‌هم ”به‌صورت صـفر و يك “ در رابطه بازگشتي احتمال انتخاب موارد آزمون در نظـر گرفته‌شده است. درحالی‌که براي اولویت‌دهی كـاراي پيشـينه محـور، هـم كارايي كشف خطا در طول اجراها بايـد در نظـر گرفتـه شـود و هـم از اولویت‌دهی پايين و منسوخ شدن دائمي يكسري از آزمون‌ها بايسـتي جلوگيري شود.فضل علیزاده و همکاران در [7]یک روش اولویت‌دهی مبتنی بر پیشینه را پیشنهاد کردند. این روش سه نوع اطلاعات پیشینه در مورد موارد آزمون مانند تعداد اجراها و تعداد زمان‌های کشف خطا را در یک رابطه ترکیب کرده است. آن‌ها به هر یک از این معیارها ضریب ثابتی می‌دهند، بنابراین هر معیار روی احتمال انتخاب تأثیر ثابتی دارد، سپس احتمال انتخاب محاسبه می‌شود و موارد آزمون به‌صورت نزولی ازنظر احتمال انتخاب زمان‌بندی می‌شوند.خلیلیان و همکاران در [8] رابطه ی برای اولویت‌دهی مورد آزمون ارائه دادند که از اطلاعات پیشینه استفاده می‌کند. ایده این روش این است که هر بخش از رابطه اولویت‌دهی باید تأثیر خاصی روی اولویت مورد آزمون داشته باشد و این تأثیرات ممکن است در طول آزمون رگرسیون متوالی تغییر کنند. آن‌ها رابطه ی ارائه دادند که از ضرایب متغیر بهبودیافته استفاده می‌کند، این متغیرها بر اساس دسترسی به پیشینه داده کارا هستند، پیشینه اطلاعات کارایی در هر مورد آزمون بر اساس همه مراحل آزمون است نه‌فقط در آزمون مرحله قبل. آن‌ها معتقدند که بر اساس داده‌های پیشینه و شرایط هر مرحله آزمون، هر نوع از اطلاعات باید تأثیر مناسبی روی تعیین احتمال هر مورد آزمون داشته باشند، تأثیر می‌تواند خیلی ناچیز و یا خیلی زیاد باشد.1-4- نوآوری بر روش‌های ارائهشدهدر روش پيشنهادي در اين پایان‌نامه، به ارائه راه حلي براي انتخاب و اولویت‌دهی مبتنی بر پيشينه موارد آزمون در هر گام اجرا، از سابقه كارايي موارد آزمون در كشـف خطـا و نيـز سـالمندي مـوارد آزمـون استفاده می‌شود به گونه‌ی که در هر بار اجرای آزمون رگرسیون موارد آزمون جدید انتخاب و اولویت‌دهی شوند. از طرفی هر مورد آزمون هزینه و دشواری مخصوص به خود را دارد که در هیچ‌یک از روش‌های ارائه‌شده به آن نپرداخته‌اند؛ بنابراین در این پایان‌نامه با استفاده از روش فرا ابتکاری ژنتیک مناسب‌ترین زیرمجموعه از موارد آزمون از طریق روش‌های مبتنی بر پیشینه انتخاب می‌شود و با تابع برازندگی مناسب اولویت‌دهی می‌شود تا درنهایت معیار APFDc افزایش یابد.