بخشی از مقاله
چکیده
تولید داده آزمون به صورت خودکار، یکی از مهم ترین گام ها در آزمون نرم افزار می باشد. از چالش های عمده در آزمون نرم افزار، کاهش تعداد داده های آزمون و کاهش زمان تولید آن ها است. در این مقاله با استفاده از الگوریتم بهینه سازی فاخته به عنوان یکی از این الگوریتم ها سعی در کاهش زمان تولید داده های خودکار برای چند نمونه مسئله شده است. ضمناً با مقایسه انجام شده بر روی الگوریتم ژنتیک به عنوان یکی از رایج ترین الگوریتم های استفاده شده در آزمون نرم افزار مشخص گردید زمان لازم برای تولید داده آزمون مناسب در الگوریتم فاخته نسبت به الگوریتم ژنتیک کاهش خواهد یافت.
مقدمه
آزمون نرم افزار فقط می تواند وجود خطاها را نشان دهد ولی نمی تواند عدم وجود خطا را تضمین نماید ]١.[ تولید خودکار داده های آزمون با استفاده از منبع برنامه یکی از روش های آزمون جعبه سفید می باشد. هدف از این مقاله استفاده از الگوریتم فاخته ]١٠[ به عنوان یکی از الگوریتم های فرا اکتشافی می باشد. استفاده از الگوریتم های فرا اکتشافی در ]٢[ و ]۴[ به عنوان یکی از روش های پرکاربرد در تولید خودکار داده های آزمون معرفی شده است. در ]٣[ و ]۶[ نویسندگان از الگوریتم ژنتیک برای پوشش مسیر استفاده نموده اند.
در ]۴[ تولید خودکار داده آزمون به وسیله الگوریتم ممتیک انجام شده است. کارایی آزمون بهبود بخشیده شده و زمان و هزینه آزمون به حداقل رسیده است. در ]١١[ و ]۴[ از سه فاکتور برای تولید یک داده آزمون مناسب استفاده شده است. این سه فاکتور عبارتند از احتمال، نزدیکی به مقادیر مرزی و پوشش تصمیم. تابع برازش بر اساس میانگین سه فاکتور فوق محاسبه شده است. از این سه فاکتور برای به دست آوردن داده ای مناسب در این مقاله نیز استفاده شده است. محققان در ]۵[ با استفاده از ازدحام ذرات، بدون دانش اولیه و با کمترین زمان ممکن داده های آزمون را تولید نموده اند که روش آن ها تنها برخی از جواب ها را تعیین می کند.
در ]٧[ از الگوریتم زنبورعسل برای تولید داده آزمون استفاده شده است و در مواردی که داده های ورودی بسیار بزرگ باشد الگوریتم خوب جواب نمی دهد. در ]٨[ و ]٩[ روش مؤثر برای تولید داده آزمون با استفاده از الگوریتم های جستجوی فاخته و جستجوی ممنوعه ارائه شده است. فاکتورها و تابع هدف استفاده شده با آنچه در این مقاله بیان خواهد شد متفاوت است. به صورت کلی در آزمون ساختاری برنامه فضای جستجوی مسئله از روی گراف کنترل جریان برنامه که ساختار برنامه را نشان می دهد، به دست می آید. در همه روش های ارائه شده یک داده آزمون به صورت تصادفی به عنوان ورودی الگوریتم داده شده سپس با استفاده از عملگرهای الگوریتم فرا اکتشافی و تابع برازندگی انتخاب شده تلاش برای بهینه نمودن آن و تولید داده هایی کارآمد در حداقل زمان ممکن شده است.
در این مقاله برای تولید خودکار داده آزمون از برنامه دسته بندی مثلث ]۵[ و ]١١[ و برنامه مرتب سازی تعویضی جهت نمایش توانایی الگوریتم پیشنهادی استفاده شده است. از فاکتورها و تابع هدف بکار گرفته شده در ]١١[ برای بهینه نمودن الگوریتم استفاده خواهد شد. ساختار این مقاله به صورت زیر است. بیان مسئله در بخش دوم، مقایسه و پیاده سازی در بخش سوم و در انتها نتیجه گیری و کارهای آینده آمده است.
٢ بیان مسئله
تولید خودکار داده آزمون یکی از مسائل نسبتاً پیچیده در آزمون نرم افزار می باشد ]١.[ در این مقاله با استفاده از گراف کنترل جریان برنامه ]١[ جهت مشخص نمودن مسیرها و پیمایش آن ها و به کمک الگوریتم بهینه سازی فاخته که اطلاعات تکمیلی آن در ]١٠[ آمده است به تولید خودکار داده آزمون می پردازیم. در اینجا جهت فهم مسئله به برخی از پارامترهای این الگوریتم اشاره خواهد شد. الگوریتم فاخته همانند سایر الگوریتم های تکاملی با یک جمعیت اولیه کار خود را شروع می کند. این جمعیت در الگوریتم فاخته، تعدادی تخم است که در لانه تعدادی پرنده میزبان دیگر قرار می گیرد ]١٠.[ وقتی تمام فاخته ها به سمت نقطه هدف مهاجرت کردند و نقاط سکونت جدید هر کدام مشخص شد، هر فاخته صاحب تعدادی تخم می شود.
تابع هزینه از میانگین سه فاکتور برای هر تخم به دست می آید. سه فاکتور شامل:
١ - احتمال مسیر: مسیری که احتمال بیشتری داشته باشد برای اجرا انتخاب می شود و با p - t - نمایش داده می شود.
٢ - نزدیک به مقادیر مرزی: احتمال خطا در مقادیری که به مرز نزدیک هستند بیشتر است پس این مقادیر احتمال بیشتری برای انتخاب دارند. نزدیک به مقادیر مرزی با N - T - نشان داده می شود.
٣ - پوشش تصمیم: هر چه تعداد یال های پیمایش شده در یک مسیر بیشتر باشد احتمال انتخاب آن مسیر بیشتر است. پوشش تصمیم با D - T - نشان داده شده است.
٢ . ١ گراف کنترل جریان
برای تولید خودکار داده آزمون، ابتدا گراف جریان برنامه رسم می شود. این گراف برای تولید تعداد کافی داده آزمون برای پوشش فضای جستجو در مسیرهای شدنی یک گراف کنترل جریان برنامه است. الگوریتم و گراف کنترل جریان برنامه مثلث به ترتیب درقسمت آ و ب در شکل ١ آورده شده است. مسیرها بر اساس گراف جریان کنترل برنامه انتخاب می شوند.
٣ مقایسه و پیاده سازی
الگوریتم فاخته همانند سایر الگوریتم های فرا اکتشافی با یک جمعیت اولیه کار خود را شروع می کند. جمعیتی متشکل از فاخته ها، این جمعیت از فاخته ها تعدادی تخم دارند که آن ها را در لانه تعدادی پرنده میزبان خواهند گذاشت ]١٠.[ به دلیل نبود دانش اولیه، جمعیت اولیه تصادفی در نظر گرفته شده است. تابع هزینه شامل میانگین سه فاکتور برای تخم ها است و داده آزمون برای ٠۵ نسل آموزش داده شده اند. سپس نتایج ده سری اجرا میانگین گیری شده اند. برای مقایسه نتایج روش های ژنتیک و فاخته، آن ها را در محیط برنامه نویسی متلب پیاده سازی کردیم و شرایط حاکم بر دو الگوریتم یکسان در نظر گرفته ایم.
به عنوان نمونه مقدار جمعیت اولیه دو الگوریتم تصادفی است، تعداد نسل تولیدشده برای برنامه مثلث ١٠٠ و برنامه مرتب سازی تعویضی ٠۵ است و تعداد کروموزم با تعداد تخم نیز برابر در نظر گرفته شده است. جهت پیاده سازی تولید خودکار داده آزمون با الگوریتم فاخته و ژنتیک از تابع هدف]١١[ استفاده شده است. جدول ١ نشان دهنده ی کاهش زمان اجرای الگوریتم فاخته نسبت به الگوریتم ژنتیک در مسئله تولید خودکار داده آزمون برای برنامه مثلث و برنامه مرتب سازی تعویضی است.
همان طور که گفته شد به دلیل فرا اکتشافی بودن الگوریتم های فوق هر کدام ده بار در نرم افزار متلب اجراشده و نتایج آن ها میانگین گیری شده اند. همان طور که از جدول ١ مشخص است الگوریتم فاخته زمان اجرای کمتری دارد و در سایر موارد هر دو الگوریتم یکسان عمل کرده اند که در کل نتایج بیانگر بهبود عملکرد الگوریتم فاخته نسبت به الگوریتم ژنتیک در تولید خودکار داده آزمون است.
۴ نتیجه گیری و کارهای آینده
آزمون نرم افزار پرهزینه ترین مرحله ی تولید نرم افزار است و ازآنجایی که آزمون نرم افزار نقش مهمی در تولید خودکار داده برای کاهش هزینه و زمان را دارد. مهم ترین مرحله در آزمون نرم افزار، تولید داده آزمون است.
