بخشی از مقاله
خلاصه
استفاده نمودن از دادههای آزمون مناسب تاثیر بهسزایی در بالا بردن توانایی کشف خطای آزمون نرم افزار دارد. در سالهای اخیر شاهد افزایش علاقهمندی به استفاده از روشهای مبتنی بر جستجو در خودکارسازی فرآیند تولید داده آزمون هستیم. در روشهای آزمون مبتنی بر جستجو از الگوریتمهای فراابتکاری برای یافتن دادههای آزمونی مناسب استفاده میشود به نحویکه بتوانند ضمن بیشینه نمودن اهداف آزمون، هزینه انجام آزمون را کمینه نمایند. الگوریتم بهینهسازی غذایابی باکتری یکی از جدیدترین الگوریتمهای فراابتکاری است که تاکنون بهطور موفقیتآمیزی در زمینههای مختلف بکار گرفته شده است.
در این مقاله از الگوریتم غذایابی باکتری جهت تولید خودکار داده آزمون با هدف پوشش انشعابات برنامه استفاده نمودهایم. جهت ارزیابی روش پیشنهادی آنرا بر روی هفت برنامه محک استاندارد اعمال نموده و از معیارهای اثربخشی دادههای آزمون و کارائی روش تولید داده آزمون برای ارزیابی و مقایسه آن با روشهای دیگر استفاده نمودیم. نتایج آزمایشات انجام گرفته نشان از برتری الگوریتم پیشنهادی نسبت به الگوریتم ژنتیک در هر دو معیارها دارد. ضمن اینکه روش پیشنهادی از نظر معیار اثربخشی دادههای آزمون در بیشتر موارد بهتر از الگوریتمهای ازدحام ذرات و کلونی مورچه بوده و در معیار کارائی، عملکردی قابل مقایسه با این دو الگوریتم دارد.
کلمات کلیدی: آزمون نرم افزار، تولید داده آزمون، الگوریتم بهینهسازی غذایابی باکتری، الگوریتم فراابتکاری، پوشش انشعاب
.1 مقدمه
یک روش موثر در حصول اطمینان و افزایش کیفیت سیستمهای نرمافزاری آزمون نرمافزار است. تولید داده آزمون کاری دشوار و مهم در فرآیند آزمون نرمافزار میباشد چرا که کارائی1و اثربخشی2آزمون بهمیزان زیادی به کیفیت دادههای بکاررفته در آن وابسته است. تولید داده آزمون انتخاب ورودیهائی از فضای ورودی برنامه است که بتوانند خطاهای بالقوه موجود در برنامه را آشکار سازند. استفاده از مجموعه داده آزمون مناسب میتواند زمان اجرای آزمون را کاهش داده و احتمال کشف خطا را افزایش دهد. آز آنجاییکه تولید داده آزمون زمانبر، هزینه بر و مستعد خطاهای انسانی است، خودکارسازی آن بسیار اهمیت دارد.
روشهای مختلف تولید داده آزمون را میتوان به دو دسته کلی تقسیمبندی نمود: روشهای عملکردی - 3یا روشهای آزمون جعبه سیاه - که دادههای آزمون را از توصیفات برنامه تولید میکنند و روشهای ساختاری - جعبه سفید - که دادههای آزمون را از کد برنامه تحت آزمون تولید مینمایند.[1] در مقایسه با روشهای عملکردی روشهای آزمون ساختاری توانایی آشکارسازی خطای بالاتری دارند. در روش ساختاری، تمرکز بر پوشش عناصر ساختاری کد برنامه مانند دستورات، انشعابات، مسیرها یا زوجهای تعریف-استفاده است. در این روش، جهت ارزیابی کیفیت دادههای آزمون تولید شده از معیاری به نام نسبت پوشش4استفاده میگردد.
مقدار پوشش انشعابات از تقسیم تعداد انشعابات پوشش داده شده در طول فرآیند آزمون به تعداد کل انشعابات موجود در برنامه مورد آزمون بدست میآید. بر اساس نتایج پژوهشهای انجام گرفته پیشین، پوشش انشعابات 5روشی با بیشترین کارائی هزینه در بین روشهای آزمون ساختاری است.[2] در پژوهش حاضر نیز از این معیار در تحلیل آزمایشات خود استفاده خواهیم نمود.امروزه با رشد سریع اندازه و افزایش پیچیدگی نرمافزارها روشهای سنتی تولید داده آزمون ناکارآمد می باشند. از طرفی، به دلیل ماهیت غیرخطی نرم افزار - وجود دستورات شرطی، حلقههای تکرار و ... - تبدیل مسئله آزمون نرم افزار به یک مسئله بهینهسازی معمولا منجر به فضای جستجویی غیرخطی، گسسته وفمغشپیچیده میگردد که بکارگیری روشهای جستجوی فراابتکاری برای آنها گزینهای مناسب به نظر میرسد.
اصطلاح آزمون نرم افزار مبتنی بر جستجو1به روشهای آزمون نرمافزاری اطلاق میگردد که از الگوریتمهای جستجوی فراابتکاری در آزمون نرمافزار استفاده میکنند .[3] ایده اصلی در روشهای مبتنی بر جستجو، انطباق روشهای جستجوی فراابتکاری با مسئله تولید داده آزمون، با هدف انتخاب دادههائی از فضای ورودی برنامه است که نیازمندیهای آزمون2 خاصی را برآورده نموده و توان کشف خطا را افزایش دهد. از آنجا که آزمون نرم افزار کاری زمانبر است بنابراین هدف، تولید مجموعهای کمینه از دادهها میباشد تا زمان و هزینه آزمون کاهش یابد. حجم پژوهشهای انجام گرفته در زمینه تولید داده آزمون آنچنان زیاد بوده است که تاکنون شاهد ارائه چندین مقاله مروری در این زمینه بودهایم .[3-5]
الگوریتمهای فرابتکاری که معمولا از پدیدههای طبیعی الهام گرفته شدهاند با بهرهگیری از هیوریستیکهایی تلاش میکنند بهینه سراسری یا حداقل جوابی نزدیک به بهینه سراسری را بیابند. استفاده از این روشها خصوصا در مورد مسائل دشوار با فضای حالت بزرگ که استفاده از روشهای تحلیلی3مناسب نیست میتواند سودمند باشد. الگوریتم ژنتیک4، الگوریتم ازدحام ذرات5و الگوریتم کلونی مورچگان6مثالهایی از الگوریتمهای فراابتکاری هستند که در سالهای گذشته بهمیزان زیادی و در کاربردهایی مختلف به صورت موفقیت آمیز استفاده شدهاند. در سالهای اخیر شاهد استفاده از الگوریتمهای فراابتکاری مختلف در زمینه تولید خودکار داده آزمون بودهایم که در بخش 3 مروری مختصر بر پژوهشهای انجام گرفته پیشین در این زمینه خواهیم داشت.
الگوریتم بهینهسازی غذایابی باکتری یکی از جدیدترین الگوریتمهای فراابتکاری الهام گرفته از طبیعت است. از این الگوریتم بهطور موفقیتآمیزی در کاربردهای مختلف استفاده شده است [6-8] ولی تاکنون کارایی این الگوریتم جهت تولید داده آزمون ارزیابی نشده است. از این رو در پژوهش حاضر از الگوریتم بهینهسازی غذایابی باکتری در این حوزه کاربرد جدید استفاده نمودهایم. نتایج آزمایشهای انجام گرفته با هدف ارزیابی روش پیشنهادی و مقایسه آن با الگوریتمهای فراابتکاری دیگر مانند الگوریتم ژنتیک، کلونی مورچه و ازدحام ذرات نشان از کارایی مناسب روش پیشنهادی دارد.در ادامه مطالب این مقاله، در بخش دوم شرح مختصری از الگوریتم بهینهسازی غذایابی باکتری آورده شده است. در بخش سوم، مروری بر پژوهشهای پیشین انجام گرفته در زمینه تولید داده آزمون مبتنی بر جستجو انجام شده است. در بخش چهارم روش پیشنهادی شرح داده میشود. بخش پنجم شامل ارزیابی روش پیشنهادی است و در بخش ششم نیز به نتیجهگیری از پژوهش حاضر خواهیم پرداخت.
.2 الگوریتم بهینه سازی غذایابی باکتری
الگوریتم غذایابی باکتری 7یک الگوریتم بهینهسازی سراسری است که در [9] پیشنهاد شده است. این الگوریتم از الگوی تغذیهای نوعی باکتری به نام E.Coli در جستجوی غذا شکل گرفته است. پس از مدتی باکتری مواد غذایی اطراف خود را جذب و مصرف میکند و جای فعلی آن دیگر جای مناسبی جهت ادامه زندگی نیست زیرا از لحاظ مواد غذایی فقیر شده است و باید به مکانی غنیتر از لحاظ مواد غذایی نقل مکان کند کهنای وظیفه عمدتاً بر عهده اندامکی به نام تاژک میباشد که با حرکت دورانی خود باکتری را به جلو میراند. البته جالب است بدانید که تاژک تنها ابزار حرکتی باکتری نیست بلکه باکتری از مکانیسمهای متفاوتی جهت حرکت استفاده میکند.باکتریها در ابتدا به صورت کاملا تصادفی در محیطی که مواد غذایی وجود دارد، توزیع میشوند.
با گذشت زمان، باکتریها به سمت مناطقی با ارزش غذایی بالاتر حرکت میکنند. آندسته از باکتریهایی که در مناطق سمی هستند از بین میروند، آنهایی که در نواحی با ارزش غذایی کم قرار گرفتهاند پراکنده میشوند و باکتریهای موجود در نواحی مناسب تکثیر میشوند. رفتار تغذیهای باکتریها شامل سه مرحله مهم کموتاکسیس - 8چرخش و شنا - ، تکثیر و حذف/پراکندگی است.در مرحله کموتاکسیس، حرکت یک باکتری E.Coli به شکل شنا یا چرخش و از طریق تاژکها است. درمحیط طبیعی، این باکتری میتواند به دو طریق متفاوت حرکت کند: اولا"، میتواند در طول بازهای از زمان در یک جهت ثابت شناکند. ثانیا، میتواند بچرخد، که در طول زندگی بین این دو حرکت تغییر وضعیت میدهد. در مرحله تکثیر، باکتریها بر اساس شایستگی مرتب میشوند و نصف باکتریها که شایستگی پایین دارند از بین میروند و به جای آنها باکتریهایی در مکانهای تصادفی قرار میگیرند.
حذف/پراکندگی زمانی اتفاق میافتند که تغییرات کوچک یا غیرمنتظرهای - مانند تغییرات دما - در محیط رخ دهد. در این مرحله ممکن است خیلی از باکتریها از بین رفته یا به نواحی دیگری بروند.شبه کد الگوریتم بهینه سازی غذایابی باکتری در شکل 1 نشان داده شده است. تعداد کل باکتریها در مجموعه، تعداد مراحل حذف/پراکندگی، تعداد مراحل تکثیر و تعداد مراحل کموتاکسیس است. با فرض اینکه - , , - نشان دهنده i -امین باکتری در j -امین مرحله کموکتاسیس، -k امین مرحله تکثیر و -lامین مرحله حذف/پراکندگی باشد و طول گامی را که در جهت تصادفی مشخص با چرخش برداشته می شود با C - i - نشان دهیم - به این معنی که C - i - واحد طول گام است - ، برای محاسبه حرکت باکتری در کموتاکسیس می توان از رابطه - 1 - استفاده کرد:که در آن ∆ برداری در جهت تصادفی است که مقادیر آن در بازه 1]و[-1 قرار دارند.
.3 پژوهشهای پیشین
تولید داده آزمون مسئلهای کلیدی در آزمون خودکار نرمافزار میباشد که در چند دهه گذشته توجه گسترده پژوهشگران را به خود جلب نموده است. پژوهشهای انجام گرفته در زمینه خودکارسازی فرآیند تولید داده آزمون را میتوان به پنج دسته اصلی: آزمون تصادفی، اجرای نمادین1، آزمون مبتنی بر جستجو، آزمون ترکیبی2و آزمون مبتنی بر مدل تقسیمبندی نمود. در این بخش، به بررسی تعدادی از پژوهشهای انجام گرفته در زمینه آزمون مبتنی بر جستجو که از الگوریتمهای فراابتکاری به منظور تولید داده آزمون استفاده نمودهاند، خواهیم پرداخت. الگوریتم ژنتیک، ازدحام ذرات، تکامل تفاضلی، کلونی مورچه و کلونی زنبور عسل از جمله الگوریتمهای فراابتکاری استفاده شده به منظور تولید داده آزمون میباشند.
در دهه 1990، الگوریتم ژنتیک جهت تولید داده آزمون استفاده و سازگار گردید. در [10] و [11] بکارگیری الگوریتم ژنتیک برای تولید خودکار داده آزمون با هدف پوشش انشعاب بررسی گردید. آزمایشات انجام گرفته بر روی چند برنامه کوچک نشان داد که الگوریتم ژنتیک میتواند به میزان چشمگیری کارائی بالاتری نسبت به الگوریتم تصادفی داشته باشد. در سالهای بعد، مک مین و همکارانش در [12] و[13] مطالعاتی تجربی در زمینه تولید داده آزمون مبتنی بر الگوریتم ژنتیک بر روی برنامههای با مقیاس بزرگ انجام دادند و کارائی این الگوریتم را با الگوریتمهای فراابتکاری دیگر مقایسه نمودند.
در [14] معیار پوشش انشعاب به عنوان هدف آزمون انتخاب و از الگوریتم ازدحام ذرات جهت تولید داده آزمون استفاده گردید. نتایج آزمایشات انجام گرفته بر روی مجموعهای از برنامههای محک، نشان از کارائی بالاتر الگوریتم ازدحام ذرات نسبت به الگوریتم ژنتیک داشت. در [15] یک الگوریتم ازدحام ذرات بهبودیافته پیشنهاد گردید که از وزن اینرسی تطبیقی3استفاده مینمود. نتایج نشان میدهد که الگوریتم ازدحام ذرات پیشنهادی، کارائی بهتری نسبت به الگوریتم ژنتیک و ازدحام ذرات استاندارد دارد. در [16] الگوریتمهای ژنتیک و ازدحام ذرات با هم ترکیب و از الگوریتم ترکیبی به منظور تولید خودکار
