- کد مرده [۴]واقع نشده باشد.
- آلودگی: بعد از اجرای محل نقصدار، برنامه در یک وضعیت اشتباه قرار گیرد.
- انتشار: آلودگی ایجاد شده از طریق اجرای بخش نقص دار باید در قسمت های مختلف برنامه انتشار پیدا کند تا آنجا که خروجی برنامه تغییر کند و آن را نادرست کند.
همانطور که در علم پزشکی پیشگیری بهتر از درمان است، برای جلوگیری از شکست برنامه بهتر است با بهره گرفتن از روشهای موجود تا آنجایی که امکان دارد از ورود نقصها به کد برنامه جلوگیری کنیم. این موضوع اولین بار توسط Myers طرح شد، وی مدعی شد تست نرمافزار موفق، تستیاست که سبب از کار افتادگی نرمافزار شود به عبارت دیگر دیدگاه Myers استفاده از نقصهای شناخته شده جهت یافتن خطاهای پنهان موجود در برنامه بود به این روش تست، تست نقص میگویند. در این روش به جای آنکه به دنبال خطا در برنامه برویم نشان می دهیم که برنامه بدون نقص است.
( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
بهره گیری از طبیعت
پدیده های طبیعی از گذشته همواره مورد توجه و الهام بخش انسان برای حل مسائل زندگی خود بوده است، یکی از جالبترین آنها اجتماع زنبوران و مورچهها است که برای حل مسائل خود (به عنوان مثال پیدا کار کردن غذا ) از راهکارهای سادهای استفاده می کنند که نه تنها قادر به حل مسائل خود هستند بلکه ما میتوانیم با مشاهده و الگو برداری از رفتار آنها بسیاری از مسائل پیچیدهای که نیاز به راه حلهای پویا دارند را به طور کارا حل کنیم، اما این الگوهای پیچیده رفتاری از کجا ایجاد می شود؟ پاسخ این سوال استفاده از هوش جمعی است، به عنوان مثال تصور کنید قرار است به محلی بروید که از آدرس آن به طور کامل آگاهی ندارید. یکی از راهکارهای موثر پرسش از کسانی است که در راه با آنها برخورد میکنید در برخی از موارد ممکن است پاسخهای نادرست دریافت کنید اما شما با توجه به پیش زمینه ذهنی و هدف از پیش تعریف شده خود تا حدی قادر به تشخیص آنها خواهید بود. در حقیقت شما ممکن است در کارهای روزمره خود بارها از هوش جمعی برای یافتن پاسخ مشکلات خود بهرهمند شوید. متاسفانه تاکنون تعریف دقیق ریاضی برای هوش جمعی وجود ندارد اما به طور کلی سیستمهایی که براساس هوش جمعی مسائل خود را حل می کنند در ویژگیهای زیر مشترک هستند:
- توانایی حل مسائل پیچیده
- توانایی حل مسائل به صورت توزیع شده
- کار در محیط پویا
- عدم نیاز به هر گونه کمک از محیط بیرون در هنگام حل مسائل
- و بدون نیاز به سیستم کنترلی(مدیریت درونی)
اگر به زندگی مورچهها نگاه کنیم، برای حل مسائل خود از چندین روش استفاده می کنند که یکی از مهمترین آنها مادهی شیمیایی به نام فرمون است و از خواص این ماده بوی آن است که بعد از گذشت زمان از شدت آن کاسته شده و به تدریج از بین میرود. اما این ویژگی چه کمکی به حل مسائل مورچهها می کند؟ به عنوان مثال مسئله یافتن کوتاه ترین مسیر را در نظر بگیرید در حقیقت مورچهها با گذشت زمان یاد گرفتهاند که برای یافتن غذا همواره کوتاهترین مسیر را از کلونی تا غذای خود پیدا کنند. هنگامی که اولین مورچه برای یافتن غذا خارج می شود یک مسیر را از میان چندین مسیر به صورت تصادفی انتخاب می کند. هر مورچه در مسیری که طی می کند از خود فرمون به جای می گذارد وبعد از یافتن غذا از مسیر پیموده شده خود که برروی آن فرمون به جای گذاشته است به کلونی باز میگردد. از آنجایی که تعداد مورچههای زیادی به طور همزمان برای یافتن غذا از کلونی خارج میشوند نخستین مورچهای که به کلونی باز میگردد به احتمال زیاد مسیر کوتاهتری به نسبت سایر مورچهها پیموده است و بوی فرمون آن ماندگاری بیشتری دارد چون در مدت زمان کمتری طی شده است پس آن مسیر توسط سایر مورچهها انتخاب خواهد شد.
هدف از انجام
علیرغم اینکه تست نرمافزار یکی از مهمترین مراحل توسعه نرمافزار است اما در کشور ما در حد اهمیتش به آن پرداخته نمی شود و تنها عنوانهای تحقیقاتی به چند مورد خاص در شبکه محدود می شود از طرف دیگر اغلب مهندسان نرمافزار به دلیل عدم آگاهی و یا هزینه عملیات تست آن را تنها در سطح یک دیباگ [۵] ساده انجام می دهند در حالیکه تست نرمافزار از سطوح مختلفی تشکیل شده که پایینترین سطح آن دیباگ است [۱]. از مشکلات دیگر این حوزه عدم شفافیت در بیان اطلاعات و در دسترس نبودن ابزارهای ارائه شده است بطوریکه از نه عنوان مطرح شده در [۲] که با زبان جاوا کار می کنند کمتر از نیمی به صورت کد منبع باز در دسترس هستند. در این پایان نامه همت خود را بر آن گذاشتیم که تا حد امکان از این موضوع پنهان مانده برای مهندسین نرمافزار ایرانی پرده برداری کنیم تا موجب آشنایی بیشتر جامعه علمی و افزایش عنوانهای تحقیقاتی در این زمینه شود. برای نیل به این هدف تمامی مقالات ذکر شده در این پایان نامه با ذکر مثال، رابطه های مربوطه و با شرح بیشتر آورده شده است و سعی شده تا جایی که امکان دارد به شکلی ساده بیان شود. از طرف دیگر با پیادهسازی یک ابزار و در دسترس قرار دادن آن در راه رسیدن به هدف خود که آشنایی بیشتر جامعه مهندسان ایرانی با تست نرمافزار است گام دوم را برداشتهایم. امید است با پیوستگی گامهای کوچک به این هدف بزرگ دست یابیم.
ترتیب فصول این پایان نامه بدین شرح است در فصل دوم به شرح مختصری از تاریخچه تست به خصوص تاریخچه تست جهش خواهیم پرداخت در فصل سوم به شرح روشهای ممکن برای پیادهسازی یک ابزار تست و روش پیاده سازی شده در این پایان نامه خواهیم پرداخت، در فصل چهارم یافتههای این تحقیق را در قالب نمودار نشان میدهیم و در فصل پنجم نتیجه گیری خواهیم داشت.
| فصل دوم ادبیات و پیشینه تحقیق |
تست جهش
تئوری و نظریات
یافتن خطاها در نرمافزار از گذشته همواره یکی از اصلی ترین دغدغه های توسعه دهندگان نرمافزار بوده است و تاکنون روشهایی برای تست نرمافزار عرضه شده است اما چگونه میتوان دریافت که تستی موفق بوده یا نه؟ آیا نبود خطا در کد برنامه، نشانهی موفقیت تست است یا شکست آن؟ در حقیقت، ممکن است تستی در کد برنامه خطایی را پیدا نکند به دلیل آنکه توانایی شناسایی خطا را در کد برنامه (که ممکن است ناشی از عدم دسترسی به کد خطا باشد) نداشته باشد یکی از روشهای مناسب برای پاسخ به سوالات بالا استفاده از داده های تست مناسب است بطوریکه بتواند بیشتر انشعابات برنامه را پوشش دهد و به تست کننده این اطمینان را بدهد که در صورت وجود نقص در برنامه می تواند آن را شناسایی کند. اما چگونه میتوان داده های مناسب را تولید کرد؟ یکی از راه حلهای مناسب شبیه سازی، عمل تست است. به عبارت دیگر میتوانیم با قرار دادن نقصها در کد برنامه به طور مصنوعی که در اصطلاح جهش نامیده میشوند یک برنامهی نقصدار ایجاد کنیم، با این کار میتوانیم از نقصدار بودن برنامه خود اطمینان حاصل کنیم و داده های تست ورودی را به خوبی ارزیابی کنیم. ایده تست جهش، برای اولین بار در یک مقاله دانشجویی به نام R.lipton [3] سال ۱۹۷۱ مطرح شد اما زیر بنای تست جهش، در دههی ۷۰ با کارهای G. J. Myers [4] و R. G. Hamlet [5] شکل گرفت. ایده اصلی تست جهش استفاده از نقص ها، برای تولید داده های مناسب و شایسته برای تست نرمافزار است که به طور کلی براساس دو فرضیه استوار است:
- برنامه نویسان لایق: از آنجا که برنامه نویسان، ماشین نیستند برنامهای تولید می کنند که نزدیک به برنامهی صحیح است. به عبارت دیگر برنامهی تولید شده ممکن است حاوی نقصهایی باشد که برنامه نویسان، ناخواسته در کد آن، وارد کرده اند. البته در اکثر موارد به دلیل آنکه نرمافزار تولید شده نزدیک به نرمافزار صحیح است، نقصها به صورت ساده است طوریکه با یک تغییر کوچک در کد برنامه قابل اصلاح هستند.
- اثر اتصال: دادهی تستی که قادر است تمام تفاوتهای یک برنامهی صحیح را از یک برنامهی نادرست با بهره گرفتن از شناسایی خطاهای ساده تشخیص دهد آنقدر نسبت به وجود خطا حساس استکه می تواند خطاهای پیچیده تر را نیز تشخیص دهد. در حقیقت خطاهای ساده به خطاهای پیچیده متصل هستند[۴].
Offutt, A Jefferson [6] موضوع اثر اتصال را به طور دقیقتر، و در تست جهش بررسی کرده است. برای این کار، ابتدا برای تولید جهشهای پیچیدهتر تغییراتی در سیستم مٌدرا ایجاد می کند سپس با قرار دادن این جهشها در برنامههایی مانند تشخیص نوع مثلث[۶]، جستجو[۷]، و یافتن [۸]میانه به صورت تجربی نشان میدهد جهشهای سادهتر، دشوارتر از جهشهای پیچیدهتر از میان میروند و تعریفی را برای فرضیه اتصال در تست جهش به این صورت مطرح می کند: اتصال جهشهای پیچیده به جهشهای ساده به گونه ای است که داده های تست، درصد بیشتری از جهشهای پیچیده را نسبت به جهشهای ساده شناسایی می کند. برای اثبات این قضیه در برخی مقالات مانند [۴] تنها با بهره گرفتن از مشاهدات تجربی بیان شده است اما در این زمینه مقالاتی برای ارائه یک اثبات دقیق و ریاضی نیز یافت می شود. به عنوان نمونه K. Kapoor [7] نظریه اتصال را برای فرمولهای بولی و نقصهای منطقی به صورت رسمی تحلیل می کند. یکی از موضوعاتی که با اثر اتصال جهشها ارتباط نزدیکی دارد سطح جهشها است که به این صورت تعریف می شود جهش سطح n ام از ترکیب جهشهای سطح اول، دوم، سوم تا n-1 ام بدست می آید. جهشهای سطح اول همان نقصها هستند که به صورت مصنوعی به کد برنامه تزریق میشوند و جهشهای سطوح بالاتر هر ترکیبی از جهشهای سطح اول است. Yue Jia *, Mark Harman [8] جهشهای سطح بالاتر را براساس دو پارامتر متصل [۹]بودن و شامل [۱۰]بودن به شش دسته، تقسیم می کنند. متصل بودن بدان معناست که اگر ورودی تستی بتواند تمام جهشهای سطح اولیه که یک جهش سطح بالاتر را میسازند از میان ببرد، می تواند آن جهش سطح بالاتر را نیز از بین ببرد و برعکس آن تعریفی برای عدم اتصال است. شامل بودن جهشهای سطح بالایی است که به نسبت جهشهای سطح اولیه شان سختتر از میان میروند. دستهی اول جهشهای متصلِ شامل قوی: اشتراک داده های استفاده شده برای از میان بردن جهشهای سطح اولیه میتوانند برای از میان بردن جهشهای سطح بالاتر استفاده شوند. دستهی دوم جهشهای متصل شامل ضعیف: تنها بخشی از داده های اشتراکی و غیر اشتراکی تولید شده برای از میان بردن جهشهای سطح اول در از بین بردن جهشهای سطح بالاتر قابل بکارگیری هستند. دستهی سوم جهشهای غیر متصل شامل ضعیف: در این دسته دادههایی که جهش سطح بالا را از بین میبرند با دادههایی که جهش سطح اولیه را از بین میبرند هیچ نقطهی اشتراکی ندارند دستهی چهارم و پنجم جهشهای غیر متصل غیر شامل: در این دسته داده های ورودی یا مانند دستهی سوم هستند یا جهش سطح بالای به وجود آمده جهش برابر[۱۱](که در ادامه توضیح داده خواهد شد) است که هیچ دادهای نمیتواند جهش سطح بالا را از میان ببرد. دستهی ششم جهشهای متصل غیر شامل: در این دسته جهش سطح بالای ایجاد شده نسبت به جهشهای سطح اولیه خود راحتتر از میان میرود. در این مقاله نویسنده دستههای اول، دوم و سوم را در گروه جهشهای سخت قرار میدهد.
متدلوژی
همانطور که در شکل(۲-۱) نشان داده شده است ابتدا برنامه وارد شده را با اعمال تغییراتی در کد آن، جهشدار میکنیم سپس با بهره گرفتن از روشهای خودکار و یا غیر خودکار برای آن یک مجموعه ی ورودی تست آماده میکنیم. در این هنگام، به جهت اطمینان از عدم وجود خطا در برنامه جهش نیافته آنرا با ورودیهای تولید شده، تست میکنیم در صورت وجود بافتن خطا در برنامه جهش نیافته، آنرا جهت تعمیر ارسال میکنیم. (این مرحله برای آن است که بتوانیم خروجیهای برنامهی جهش یافته را با برنامه اصلی به طور دقیق مقایسه کنیم.) در صورت عدم وجود خطا در برنامه اصلی، برنامهی جهش نیافته را با داده های تست، آزمایش میکنیم سپس از طریق مقایسه خروجی برنامهی اصلی و برنامهی جهش یافته و شمارش جهشهای کشف نشده امتیاز جهش را از طریق معادله(۲-۲) به دست میآوریم:
| معادله(۲‑۱): |
که در صورت مشاهده بدست آمدن امتیاز جهش بالا، تست پایان یافته است. در غیر این صورت آنرا برای یافتن جهشهای برابر[۱۲] ارسال میکنیم.
شکل(۲‑۱): چارت فرایند تست جهش
عملگرها
برای ایجاد تغییرات یا به اصطلاح ایجاد جهش در کد برنامه، عملگرهای زیادی برای ایجاد تغییراتی مانند درج حذف جا به جایی و … معرفی شده اند. که برخی در سطح توابع استفاده میشوند و به تازگی عملگرهایی جدیدی مطرح شده اند که در سطح کلاس استفاده میشوند.
عملگرهای سطح تابع
همانطور که از نام آنها مشخص است این عملگرها با توابع و هر آنچه درون آن است سروکار دارند در ابتدا ۲۲ عملگر توسط مٌدرا [۹] برای زبان فرترن ارائه شد که در جدول(۲-۱) آورده شده است.
جدول(۲‑۱): ۲۲ عملگر مُدرا [۹]
| توضیح | عملگر جهش |
| جا به جایی منبع آرایه(Array reference for array reference replacement) | AAR |
| فرار دادن مقدار مطلق (Absolute value insertion) | ABS |
| جا به جایی آرایه با یک مقدار ثابت(Array reference for constant replacement) | ACR |
| جا به جایی عملگرهای حسابی(Arithmetic operator replacement) | AOR |
| جا به جایی آرایه با متغییرهای عددی(Array reference for scalar variable replacement) | ASR |
| جابهجای مقدار ثابت با آرایه (Constant for array reference replacement) | CAR |
| جا به جایی نام یک آرایه(Comparable array name replacement) | CNR |
| جایگذاری مقادیر ثابت(Constant replacement) | CRP |
| جایگذاری مقادیر ثابت با متغییرها(Constant for scalar variable replacement) | CSR |
| جایگذاری برچسب عبارت do (DO statement end replacement) | DER |
| همانند CRPاست اما بر عبارتهای دادهای تاثیر می گذارد(DATA statement alterations) | DSA |
| جایگذاری برچسب GOTO) (GOTO label replacement | GLR |
| جایگذاری اتصال منطقی(Logical connector replacement) | LCR |
| جایگذاری عملگر رابطهای(Relational operator replacement) | ROR |
| جایگذاری عبارت (RETURN statement replacement) return | RSR |
| هر عبارتی که درون یک بلاک پایه و یا درون یک عبارت شرطی باشد با TRAPجایگزین می شود(Statement analysis) | SAN |
| جایگذاری آرایهها با متغییرها (Scalar variable for array reference replacement) ذازی |
SAR |
| جا به جایی متغییرها با مقادیر ثابت (Scalar for constant replacements) | SCR |
| حذف یک عبارت (Statement deletion) | SDL |
| هر ثابت ریاضی با ثابت ریاضی دیگر جایگزین می شود (Source constant replacement) | SRC |
| جایگزینی متغییرهای عددی (Scalar variable replacement) | SVR |
| درج عملگرهای یگانی (Unary operator insertion) | UOI |
اکنون برای شرح دقیق تر موضوع عملگرهای ABS، UOI، ROR، AOR وLOR ، که برای زبان جاوا طراحی شده است را شرح میدهیم [۱]:
ABS قرار دادن مقدار مطلق: هر عبارت و زیر عبارت محاسباتی توسط سه تابع abs()، negAbs() و failOnZero() تغییر داده می شود. ABS مقدار مطلق عدد را برمیگرداند، negAbs مقدار منفی یک عدد مطلق را برمیگرداند، failOnZero بررسی می کند که آیا مقدار عبارت برابر با صفر است یا خیر، به عنوان مثال: عبارت X=3 * a; را در نظر بگیرید اگر عملگر بالا را روی آن اعمال کنیم بدین شکل می شود:
X=3*abs(a);
X=3*-abs(a);
X=3* failOnZero(a);
UOI عملگر درج یگانی: هر عملگر یگانی مانند +، -،! ، ~، قبل از هر عبارت و با توجه به نوع عبارت، درج می شود به عنوان مثال: عبارت X=3 * a; در نظر بگیرید:
X=3*+a;
X=3*-a;
X=+3*a;
X=-3*a;
X=!3*a;
همانطور که مشاهده میکنید در جهش آخر، به دلیل عدم تطبیق نوع عملگر و عبارت، خطا رخ داده است.
ROR عملگر جا به جایی ارتباط: هرکدام از عملگرهای رابطهای () با یکدیگر جابهجا شده و یا با بهره گرفتن از دو تابع trueOP() وfalseOP() (که تنها مقدار “False”و “True” را درون عبارت شرط قرار می دهند)مقدار خروجی را تغییر می دهند به عنوان مثال: جهشهای عبارت شرطی if(m>n) عبارتند از:
If(m>=n)
if(m<n)
if(m<=n)
if(m==n)
if(m!=n)
if(false)
if(true)
AOR جا به جایی عملگرهای محاسباتی: جا به جایی هر یک از عملگرهای محاسباتی (*،**،/، -،+ و% ) و یا با بهره گرفتن از دو عملگر rightOp و LeftOp(که به ترتیب عملوند سمت راست یا چپ را حذف می کنند) میتوان در کد برنامه تغییر ایجاد کرد. به عنوان مثال: جهشهای عبارت X=a+b; را در نظر بگیرید
X=a-b;
X=a*b;
X=a/b;
X=a**b;
X=a;
X=b;
X=a%b;
LOR جایگزینی عملگر منطقی: جا به جایی هر کدام از نشانه های عملگرهای منطقی (&، |، ^) و یا هرکدام از عملگرهای rightOp و LeftOpمیتواند در کد برنامه، تغییر ایجاد کند. به عنوان مثال جهشهای عبارت x=m & n را در نظر بگیرید:
x=m|n;
x=m^n;
x=m;
x=n;
عملگرهای سطح کلاس
در برنامه نویسی شئگرا خواص جدیدی نسبت به برنامه های سنتی همچون کپسوله سازی، ارث بری و چند ریختی وجود دارد، این ویژگیها زمینه جدیدی برای تست جهش ایجاد می کند در تست واحد و تست یکپارچه سازی به چهار سطح تقسیم میشوند:
- درون توابع: نقص درون توابع زمانی رخ میدهد که عملکرد یک تابع به طور نادرستی پیاده سازی شده است. که مشابه با عملگرهای درون توابع است.
- بین توابع: نقص بین توابع در ارتباط بین جفت توابع در یک کلاس رخ میدهد.
- درون کلاس: در این سطح به بررسی هر آنچه که در یک کلاس قرار دارد می پردازد که می تواند شامل تعامل توابع عمومی درون یک کلاس زمانی که با ترتیبهای مختلف فراخوانی میشوند و … باشد.
- بین کلاسها: در این سطح به بررسی نقصها در نحوی یکپارچه سازی کلاسها می پردازد در این بخش نقصها بیشتر مربوط به چندریختیها، ارث بری و دسترسی به کلاسها هستند
در جدول(۲-۲) این عملگرها نشان داده شده اند[۱۰].
جدول(۲‑۲): عملگرهای جهش ارائه شده در سطح بین کلاس [۱۰]
| ویژگی زبانی | عملگر | شرح |
| کنترل دسترسی | AMC | تغییر دسترسی خصیصه های موجود در کلاس مانند: عمومی، خصوصی و محافظت شده(Access modifier change) |
| ارث بری | IHD | مخفی سازی حذف متغییرها (Hiding variable deletion) |
| IHI | مخفی سازی درج متغییرها (Hiding variable insertion) | |
| IOD | Override حذف یک تابع (Overriding method deletion) | |
| IOP | Override تابعی که محل فراخوانی آن تغییر کرده (overriding method calling position change) | |
| IOR | Override تغییر نام یک تابع (Overriding method rename) | |
| ISK | حذف عبارت کلیدی Super | |
| IPC | حذف فراخوانی متد سازندهی والد (Explicit call of a parent’s constructor deletion) | |
| چندریختی | PNC | جایگزینی فراخوانی تابع با نوع کلاس فرزند (new method call with child class type) |
| PMD | جایگزینی یک متغییر با نوع کلاس والد (Instance variable declaration with parent class type) | |
| PPD | جایگزینی متغییر پارامتر [۱۳]با نوع(type) کلاس فرزند (Parameter variable declaration with child class type) | |
| PRV | تخصیص مرجع به انواع قابل مقایسه (Reference assignment with other comparable type) | |
| بارگذاری [۱۴] | OMR | بارگذاری تغییر محتوی تابع (Overloading method contents change) |
| OMD | بارگذازی حذف تابع (Overloading method deletion) | |
| OAO | تغییر ترتیب آرگومان (Argument order change) | |
| OAN | تغییر تعداد آرگومان (Argument number change) | |
| اشتباههای رایج در برنامه نویسی | EOA | جایگزینی مرجع تخصیص [۱۵]با مرجع محتوی (Reference assignment and content assignment replacement) |
| EOC | جایگزینی مرجع مقایسه با محتوی مقایسه (Reference comparison and content comparison replacement) | |
| EAM | تغییر تابع Accessor (Accessor method change) | |
| EMM | تغییر توصیف کننده تابع (Modifier method change) |
تکینکهای کاهش هزینه
در روشهای سنتی برای کاهش هزینه تست، ابتدا برنامه جهش یافته از روی کد برنامهی اصلی ایجاد شده سپس به صورت جداگانه با ورودیهای تست کامپایل می شود و در نهایت نتایج خروجی بدست آمده از آنها با یکدیگر مقایسه میشد. اگرنتایج بدست آمده، متفاوت بود جهش از میان رفته بود و در غیر این صورت باید فرایند جستجو برای جهش برابرآغاز میشد که انجام این فرایند، نیازمند تلاش انسانی و صرف هزینه میشد. به همین دلیل تا قبل از آنکه تکنیکهایی برای خودکارسازی فرایند تست عرضه شود این روش، به عنوان یک روش گران قیمت و ناکار آمد شناخته میشد تا آن زمان که تکنیکهای کاهش هزینه را به سه دستهی انجام کمتر، انجام هوشمندانه و انجام سریعتر تقسیم شد [۱۱]. در این پایان نامه، مشابه [۲] آنها را به دو دستهی تولید کمتر جهش و کاهش هزینه اجرا تقسیم میکنیم. همانطور که در شکل(۲-۲) [۲] (که حاصل بررسی ۳۹۰ مقاله است) مشاهده می شود تاکنون تکنیکهای جهش انتخابی و جهش ضعیف در مقایسه با سایر روشها بیشتر مورد توجه بوده است.( سایر روشها اغلب حاصل کمتر از ۵ مقاله بوده است.)
شکل(۲‑۲): درصد استفادهی مقالات از تکنیکهای کاهش هزینه [۲]
تولید جهش کمتر
یکی از ابتدایی ترین روشهای کاهش هزینه، تولید جهش کمتر است. زیرا هر چه تعداد جهشهای موجود در کد برنامه بیشتر باشد به همان نسبت نیاز به تولید داده های تست بیشتری داریم این کار هزینه بر است اما از طرف دیگر کاهش تعداد جهشها ممکن است اثر بخشی فرایند تست را پایین بیاورد. در این زمینه تلاش شده تا ضمن حفظ یا کاهش حداقل اثر بخشی تعداد جهشها را نیز کاهش داد. در زیر به چند روش اشاره میکنیم:
نمونه برداری از جهشها: در این روش، تمرکز بر پیدا کردن مجموعه ای از موارد تست است که با وجود موارد تست کمتر معیار پوشش را حفظ کند. در اینجا لازم است کمی در مورد معیار پوشش توضیح دهیم: هر کد برنامه را میتوان به صورت یک گراف نمایش داد که هر گره ی آن، بخشی از کد است که قابلیت اجرا در یک واحد زمانی را داشته باشد. از طرف دیگر یالها نیز نحوی ارتباطات این گرهها با یکدیگر را نشان می دهند. در هرگراف، مسیرهایی وجود دارد که دنبالهای از گرهها را شامل می شود. هر مسیر، شامل چندین زیر مسیر است که برخی از آنها مسیر تست هستند. مسیرهای تست مسیرهایی هستند که از گره آغازین گراف شروع و به گره پایانی آن ختم میشوند. در هر بار فرایند تست، تنها یکی از مسیرهای تست اجرا خواهد شد. پس در حقیقت داده های ورودی که بتواند مسیرهای تست بیشتری را اجرا کند، بهتر خواهد بود. برای پوشش، به طورکلی دو معیار وجود دارد: ۱- ساختیافته ۲-جریان داده، معیارهای ساختیافته تنها برروی گرافی تعریف میشوند که شامل گره و یال است و میتوان به عنوان مثال به معیارهای NC [۱۶](پوشش تمامی گرههای گراف) EC [۱۷](پوشش تمامی یالهای گراف) و… . معیار جریان داده ها تنها برروی گرافهایی، قابل تعریف است که در آن منبع هر متغییر ذکر شده باشد. هدف این معیار ردگیری محل تعریف def [۱۸]و استفادهی use متغییرها، جهت کسب اطمینان از استفادهی درست از آنها استdef (n). و def (e) به متغییرهایی گفته می شود که در یال e و یا گره n تعریف میشوند و متقابلا use (n) و use (e) به متغییرهایی گفته می شود که در گره n و یا یال e استفاده میشوند.
- Horgan [12] با ایجاد مجموعه تستهای کمینه سعی در کاهش هزینه تست دارد بگونهای که در عین کاهش تعداد موارد تست بتوانند کیفیت تست را ثابت نگاه دارد. در این تحقیق برای تولید مجموعه تستهای کمینه از ابزاری به نام ATACMIN استفاده می شود که با بهره گرفتن از آن در ابتدا برای ۱۰۰۰ جهش مورد تست، تولید می شود سپس آنها را براساس پوشش بلاکها در دستههای (۵۰-۵۵)% ، (۶۰-۶۵)%، (۷۰-۷۵)%، (۸۰-۸۵)% و (۹۰-۹۵)% قرار میگیرند پس از بررسیهایی که بر روی ۱۰ نرمافزار انجام شد چهار نتیجه دست آمد که عبارت است از:
- کاهش اثر بخشی: کاهش مقدار اثر بخشی بر اثر کاهش کمینه سازی دسته های تست (۵۰-۵۵)% ، (۶۰-۶۵)%، (۷۰-۷۵)%، (۸۰-۸۵)% و (۹۰-۹۵)% به ترتیب برابر است با: ۰%، ۰٫۰۳%، ۰٫۰۱%، ۰٫۳۸%و۱٫۴۵% است که این مقدار در کاهش اثر بخشی قابل چشم پوشی است.
- کاهش اندازه: کاهش اندازه برای هر دسته تست (۵۰-۵۵)% ، (۶۰-۶۵)%، (۷۰-۷۵)%، (۸۰-۸۵)% و (۹۰-۹۵)% به ترتیب برابر است با: ۱٫۱۹%، ۴٫۴۶%، ۷٫۷۸%، ۱۷٫۴۴% و ۴۴٫۲۳% است که در برابر کاهش اثر بخشی ناچیز آن، قابل توجه است.
- تاثیر سختی نقصها: در این بخش نویسنده به بررسی ارتباط میان نقصهای پیچیده و کمینه سازی مجموعه تست پرداخته است. برای این کار در ابتدا نقصها را به چهار دسته از ۱تا۴ به از پیچیده تا ساده تقسیم می کند و نشان میدهد کاهش اثر بخشی برای هر دسته به ترتیب ۰٫۳۹%، ۰٫۶۶%، ۰٫۰۹۸% و ۰% است این مساله نشان میدهد نقصهایی که توسط تعداد محدودی از موارد تست کشف می شود ممکن است در صورت کاهش مجموعه تست قابل کشف نباشند. در این مورد نیز کاهش اثر بخشی آنقدر نیست که قابل ملاحظه باشد [۱۳].
در روش دیگر از روشهای تصادفی برای انتخاب بخشی از داده های تست مناسب استفاده می شود (به عنوان مثال از ۱۰% تا ۴۰% از داده های تست را انتخاب می شود) سپس با انجام آزمایشهای مختلف به این نتیجه میرسد که برای پوشش تمام معیارها، تنها کمتر از ۱۴% درصد تمام موارد تست نیاز است [۱۴].
روش دستهبندی: ایده اصلی این روش ابتدا توسط S. Hussain[15] مطرح شد در این روش جهشهای تولید شده را براساس ویژگیهای مشترک دستهبندی میشوند سپس از میان آنها چند جهش انتخاب شده و برای هر دسته به طور مجزا داده های تست تولید می شود. برای دستهبندی جهشهای پنج برنامه از دو روش K-means ، Agglomerative (که در فصل ضمایم توضیح داده شده اند) و کد فاصله همینگ استفاده شده است. با بهره گرفتن از این فاصله میتوانیم فاصلهی بین جهشها را اندازه گیری کرده و جهشهای مشابه را در یک دسته قرار دهیم برای این کار به عنوان مثال سه جهش و به صورت جدول(۲-۳) در نظر بگیرید.
جدول(۲‑۳): سه جهش و [۱۵]
| ۱ | ۰ | ۱ | ۰ | ۰ | ۱ | ۱ | M1 |
| ۰ | ۰ | ۱ | ۱ | ۱ | ۱ | ۱ | M2 |
| ۰ | ۰ | ۱ | ۱ | ۱ | ۱ | ۰ | M3 |
همانطور که مشاهده میکنید برای هر جهش هفت ویژگی در نظر گرفته شده است که در صورت وجود آن ویژگی مقدار آن با یک و در صورت عدم وجود با صفر نمایش داده شده است. برای اندازه گیری فاصلهی همینگ قسمت های متفاوت هر M با یک دیگر جمع شده تا فاصلهی همینگ مطابق جدول(۲-۴) بدست آید.
جدول (۲‑۴): : فاصلهی همینگ سه جهش و [۱۵]
| M3 | M2 | M1 | |
| ۴ | ۳ | ۰ | M1 |
| ۱ | ۰ | ۳ | M2 |
| ۰ | ۱ | ۴ | M3 |
درنهایت با انجام تکنیکهای فوق جهشها را دسته بندی کرده و همانطور که در جدول (۲-۵) مشاهده می کنید در عین صرفه جویی در تعداد نقصها و موارد تست، تنها سبب از دست رفتن بخشی از امتیازجهش، تنها دریک برنامه شده است.
جدول(۲‑۵): خلاصهی نتایج بدست آمده حاصل از اجرای روش دستهبندی بر روی پنج برنامه [۱۵]
| برنامه ها | تعداد کل جهشها | اعداد بهینه جهشها باقی مانده بر اثر دستهبندی | کل موارد تست | موارد تست کاهش یافته | میانگین امتیاز جهش |
| Triangle | ۵۸۴ | ۶۲ | ۳۴ | ۱۲ | ۹۵٫۶% |
| TCAS | ۸۵۶ | ۲۱۲ | ۱۶۰۸ | ۲۱ | ۱۰۰% |
| Schedul | ۹۷۲ | ۸۳ | ۱۳۹۹ | ۲ | ۱۰۰% |
| Totinfo | ۱۸۷۹ | ۱۷۳ | ۱۰۵۲ | ۷ | ۱۰۰% |
| Printtokens | ۵۰۶ | ۶۸ | ۲۰۲۱ | ۴ | ۱۰۰% |
- Ji, Z[16] هر برنامه را به سه بخش دامنهی ورودی، مسیر شرطی و مسیر ماژول بعدی تقسیم می کند. هر مسیر شرطی در هنگام اجرا برنامه چندین شرط را از چندین ماژول را با عملگر منطقی عطف و نقیض یکپارچه می کند. بهعنوان مثال اگر Condition 1 و Condition 2 به ترتیب شروط ماژول ۱ و ۲ باشند پس از اجرای مسیر شرطی به صورت یکپارچهسازی می شود C. Ji, Z. برای تشخیص جهشها در مسیر شرطی متغییرهایی تعریف می کند که به شرح زیر است:
- شرط عدم خروج: انتخاب مسیر جهشی که سبب خروج از برنامه نشود.
- شرطهای تودرتو: در یک ماژول، ممکن است شرطهای تودرتویی وجود داشته باشد که برای ارضاء شرط جهش، نیاز به ارضاء تمام آنها است.
- شرطهای جهش یافته: عملگرهای جهشیکه سبب تغییر دستوری در کد شرط می شود.
دامنه ورودی باید ترکیبی از این شرطها را ارضاء کند. از این سه شرط برای اندازه گیری فاصلهی همینگ جهشها استفاده می شود. پس از اندازه گیری فاصله همینگ برای قرار گیری هر جهش در دسته مناسب متغیری به نام K که مقدار آن برابر نیمی از تعداد کل جهشها، و یک حد آستانه که مقدار آن برابر با نیمی از بیشتر فاصلهی بین دو جهش است تعریف میشوند. در ابتدا K جهش به صورت تصادفی انتخاب می شود و آنها را در دستههای اولیه قرار میدهد سپس باقی جهشها با توجه به آنکه فاصلهی آنها کمتر از حد آستانه است دستهبندی می شود. در مرحله بعد از هر دسته یک جهش به صورت تصادفی انتخاب شده و خود یک دستهبندی جدید را تشکیل میدهد که با بهره گرفتن از این روش، علاوه بر کاهش تعداد جهشها موارد تستی که نتواند دسته جهشی را از بین ببرد از مجموعه تست حذف می شود.
جهش انتخابی: یکی از روشهای کاهش تعداد جهشها، کاهش تعداد عملگرهای استفاده شده برای تولید جهش است. مانند روشهای قبل، این روش نیز در کنار کاهش تعداد جهشها حفظ اثر بخشی تست مهم است. برای افزایش سرعت اجرای برنامههایی که کامپایل آنها زمان بر است، ابزاری به نام CIT[19] معرفی شده است که این ابزار امکان تست یکپارچه و تولید جهش را به کامپایلر میدهد و از طرف دیگر آنرا برای انجام، به صورت همزمان کارآمد می کند. همچین برای اولینبار روش جهش محدود شده که منجر به حذف دو عملگر SVR و ASR مطرح می شود [۱۷] ، این ایده، به نام جهش انتخابی دوگانه، مطرح شده است. A. J. Offutt [18] در تلاش اول، برای تخمین پیچیدگی جهش ازطریق فرمولهای همبستگی خطی ساده و همبستگی چندگانهی خطی به بررسی ارتباط میان تعداد جهشهای تولید شده، خطوط برنامه، تعداد متغییرهای برنامه، تعداد منابع متغییرها و تعداد انشعابات می پردازد سپس ایدهی جهش انتخابی دوگانه را بسط داده و برای جهشهای چهارگانه و ششگانه نیز مطرح می کند. میانگین صرفه جویی در تعداد جهشهای تولید شده در پیاده سازی این روش روی ده برنامه به ترتیب ۲۳٫۹۸% برای جهش انتخابی دوگانه و ۴۱٫۳۶% برای جهشهای چهارگانه است. R. H. Untch [19] عملگرها را به صورت کلاسهای دسته بندی (مانند ES-Selective mutation که از۲۲ عملگر، عملگرهای AAR, ACR, ASR, CAR, CNR, CRP, CSR, SAR, SCR, SRC, وSVR در آن وجود ندارند) دستهبندی می کند و پس از ترکیب دستههای مختلف به این نتیجه میرسد، که پنج عملگر ABS، AOR، LCR، ROR و UOI.توانایی تولید ۹۵% از جهشها را دارند. در نتیجه عملگرهای کلیدی نامیده میشوند.
جهشهای سطح بالاتر
میتوان با ترکیب جهشهای سطوح مختلف جهشهای سطح بالاتری به وجود آورد به گونه ای که با کاهش مقدار ناچیزی از کیفیت تست مقدار قابل توجهی در تعداد ورودیهای تست و جهشهای برابر وارد شده به کد برنامه، صرفه جویی کرد. برای ایجاد این گونه جهشها سه استراتژی وجود دارد که اولین بار در [۲۰] مطرح شد. این سه استراتژی عبارت است از:
- ادغام تصادفی”RandomMix”: جهشهای به وجود آمده در این روشحاصل از ترکیب تصادفی دو عملگر است.
- عملگرهای مختلف “DifferentOperators” : جهشهای ایجاد شده در این روش حاصل از ترکیب دو عملگر متفاوت است.
- روش آخر به اول “LastToFirst”: جهشها براساس ترکیب عملگر جهش اول با عملگر جهش آخر در لیست عملگرهای جهشهای انتخابی اعمال میشوند.
سپس تاثیر حاصل از ترکیب جهشهای برابر و نابرابر نشان میدهد که در جدول(۲-۶) آورده شده است
جدول(۲‑۶): تاثیر حاصل ترکیب جهش های برابر و نابرابر با یکدیگر
| جهش برابر | جهش برابر | جهش برابر |
| جهش برابر | جهش غیر برابر | جهش غیر برابر |
| جهش غیر برابر | جهش برابر | جهش غیر برابر |
| جهش غیر برابر | جهش غیر برابر | جهش غیر برابر(به احتمال زیاد) |
Mike Papadakis [21] سه استراتژی موجود برای ترکیب جهشهای سطح اول که مطرح شد را بررسی می کند و به تاثیر آن پنج استراتژی دیگر معرفی می کند که عبارتند از:”First2Last”، “SameNode”، “SU_F2Last”، “SU_DiffOp”و “DiffOp” سپس نشان میدهد جهشهای سطح بالاتر اگر با استراتژی مناسبی ترکیب شوند میتوانند ۸۰ تا ۹۰ درصد جهش برابر کمتری تولید کنند. از طرف دیگر موارد تست مورد نیاز نیز به نسبت جهش قوی به مقدار قابل توجهای کاهش میابد.
تکنیکهای کاهش هزینه در زمان اجرای برنامه
یکی ازروشهای دیگر صرفه جویی درهزینه وزمان تست جهش استفاده ازتکنیکهای بهینه سازی فرایند اجرای تست است که به طور کلی به دو دستهی شیوه اجرای کد جهش یافته و تکنیکهای مربوط به کامپایلرها و مفسرها تقسیم میشوند.
شیوه اجرای کد جهش یافته
به طور کلی کد جهش یافته را به سه صورت میتوان اجرا کرد که در اصلاح به آن، جهش قوی[۲۰]، جهش ضعیف [۲۱]و جهش محکم [۲۲]میگویند :
جهش قوی: این روش برای اولین بار توسط R. A. DeMillo [4] مطرح شد. دو برنامه (جهش یافته و نیافته) به طور مجزا در این روش اجرا میشوند و خروجی حاصل از اجرای آنها تنها پس از اجرای کامل خطوط هر دو برنامه (جهت مشاهده تغییر) با یکدیگر مقایسه خواهد شد که این روش از نظر هزینه به صرفه نیست.
جهش ضعیف: در روش اجرای ضعیف جهش فرض می شود که برنامه از یک مجموعه n مؤلفه مانند تشکیل شده است که در هر مؤلفه میتوانیم به طور مجزا جهش ایجاد کرده وآنرا با نشان میدهیم سپس برای از بین بردن جهشهای برای مولفهی جهش یافته، داده های تست مناسب تولید میکنیم و خروجی حاصل از اجرای همان مؤلفه را با خروجیهای مولفهی نظیر در برنامه اصلی، مقایسه میکنیم در صورت مشاهده تغییر، جهش از میان رفته است. مولفههای هر برنامه را به پنج دستهی منبع متغییرها، متغییرهای تخصیص یافته، عبارت محاسباتی، عبارت ارتباطی و عبارت منطقی تقسیم می شود. A. J. Offutt [22] این ایده را گسترش داده و چهار متغییر برحسب نقطه از کد که خروجی برنامهی جهش یافته آن با خروجی برنامهی اصلی مقایسه می شود تعیین میگردد این چهار متغییر عبارتند از:
- (Expression-weak/1)EX-weak/1: نقطهی پایان اجرا و مقایسه خروجی در عبارتهای داخلی کد برنامه بعد از اولین اجرا و پیرامون عبارت جهش یافته در برنامه است.
- (Statement-weak/1)ST-weak/1: نقطهی پایان اجرا و مقایسه خروجیها دقیقا پس از اجرای عبارت جهش یافته است.
- (Basic block weak /1 execution)BB-weak/1: هر بلاک پایه تکهای از کد برنامه است که تنها میسر ورودی به آن وارد شده و تنها یک مسیر خروجی نیز از آن خارج می شود پس نقطهی پایان اجرا و مقایسه خروجی در پایان پس از اجرای هر بلاک پایه است.
- (Basic block weak /n execution)BB-weak/n: نویسنده با بررسی حلقهها در مییابد که برخی از جهشها در حلقه تنها با یک بار اجرا از میان نمیروند و برای از بین بردن آنها نیاز به اجرای n بار یک حلقه داریم پس نقطهی پایان اجرا و مقایسه خروجی بعد از اجرای n بار یک بلاک پایه است.
در شکل(۲-۳) برنامهی جهش یافته تبدیل ضرب به جمع و محدوده چهار متغییر بالا نشان داده شده است . یکی از مشکلات روش جهش ضعیف تفاوت خروجی حاصل از اجرای مولفههای برنامهی با اجرای کل برنامه است که از اثر بخشی روش جهش ضعیف میکاهد [۲۳].
شکل(۲‑۳): چهار متغییر مقایسه جهش ضعیف [۲۳]
جهش محکم: اجرای بخشی از کد برنامه بیش از یک بار که خطایی ساده به آن وارد شده است را جهش قوی گویند این روش از مزایای هر دو روش جهش ضعیف و قوی استفاده می کند. برای مقایسه روش محکم با روش جهش ضعیف و قوی M. Woodward [24] دو متغییر به نام: بخشی از اجرای برنامه است که تغییرات ایجاد می شود و: بخشی از اجرای برنامه است که تغییرات به حالت اولیه بازگردانده می شود و خروجیها مقایسه میشوند. برای مثال: جهش قوی و ضعیف با این دو متغییر به این صورت تعریف میشوند. اگر قبل و بعد از اجرای کامل برنامه باشد جهش قوی و اگر قبل و بلافاصله بعد از یک بار اجرای مولفهی خاصی در کد برنامه باشد جهش ضعیف است. در حالیکه در جهش محکم و قبل و بعد یک محدوده از پیش تعیین شده در کد برنامه قرار میگیرند محلی از کد که برای تغییر انتخاب شده است ممکن است به تعداد مولفههای اجرا شده یا به مقدار داده ها در کد برنامه بستگی داشته باشد. از مزایای این روش، میتوان به آزادی عمل بیشتر در استفاده از عملگرهای جهش و اعمال آن بر روی مولفهها، کنترل بیشتر جهت مقایسه نتایج بدست آمده از خروجی برنامه و کم هزینه بودن نسبت به روش جهش قوی اشاره کرد و از معایب آن میتوان به عدم وجود روشی مشخص برای تعیین ناحیهای که توسط جهش قوی اجرا می شود نام برد.
تکنیکهای مربوط به اجرای کد جهش یافته توسط کامپایلرها و مفسرها
به طور کلی در این تکنیکها با ایجاد تغییر در کامپایلرها و مفسرها سعی در افزایش سرعت کامپایل کد جهش یافته دارد. M. E. Delamaro و J. C. Maldonado [25] سیستمی به نام Proteum معرفی می کنند که توانایی کامپایل جداگانهی هر جهش را پیش از اجرا دارد اما در این روش مشکلی به نام گلوگاه وجود دارد. این مشکل زمانی به وجود می آید که زمان کامپایل برنامه از زمان اجرای آن بیشتر شود. برای حل مشکل گلوگاه یک کامپایلر یکپارچه ایجاد می شود که کدهای جهش به صورت تکهی برنامههایی مجزا کامپایل می کند و برحسب اولویتشان بر روی کد برنامهی اصلی یک بار کامپایل شده اعمال میشوند. [۲۶] اما همواره استفاده از کامپایلر یکپارچه سبب افزایش سرعت فرایند تست نمی شود. برای پیدا کردن سرعت مناسب دو پارامتر به نام زمان کامپایل و زمان اجرا را مطرح می شود. در صورتیکه زمان اجرا > زمان کامپایل باشد، روش کامپایل مجزا سبب افزایش سرعت فرایند تست می شود و زمانیکه زمان اجرا< زمان کامپایل باشد، روش کامپایلر یکپارچه روش مناسبی است [۲۷]. از روشهای جدیدتر میتوان به روشهای ترجمهی “بایت کد" [۲۳]اشاره کرد [۱۰] و [۲۸] که بیشتر در زبان جاوا کاربرد دارند. به طور کلی در این روشها جهشها تبدیل به بایت کد میشوند و از آنجاییکه کدهای “بایتکد” توانایی اجرا به صورت مستقیم بدون نیاز به کامپایل را دارند، در زمان انجام فرایند تست صرفه جویی می شود.
روش کاهش دامنه
تکنیک کاهش دامنه در ابزاری به نام Godzilla [29] قرار گرفت. این روش به محدودیتهای تولید شده برای موارد تست برنامه به شکل یک فضای N جهته از مقادیر ورودی مینگرد که با بهره گرفتن از پیدا کردن مقادیر برای متغیرهای درون محدودیتهای کوچکتر و جانشانی آن در متغیرهای بزرگتر قادر به حل محدودیتها خواهد بود. تکنیک کاهش دامنه در CBT [۲۴]دارای پنج ایراد است: ۱- قبل از شروع ارضاء محدودیتها، نیاز به در دسترس بودن تمام محدودیتها است. ۲- چون تخصیص مقادیر به متغییرها به صورت تصادفی صورت میگیرد، ممکن است به یک متغییر چندین مقدار یکسان، تخصیص یابد. ۳- فرایند کاهش دامنه بسیار ساده است که با پیچیده شدن حالات نرمافزارهای واقعی نمیتواند عملکرد مناسبی داشته باشد. ۴- با اجرای حقلهها مشکل دارد ۵- ارائهها را به صورت یک متغییر در نظر میگیرد. برای حل برخی از مشکلات روش پیشین کاهش دامنه پویا (DDR) [30] مطرح شد. برای شروع کار با این روش، نیاز به اطلاعاتی همچون گراف کنترل جریان برنامه، گره آغازی و گره پایانی و دامنه مقادیر تمام متغییرهای برنامه هست. سپس در گام اول مجموعه ای متناهی از مسیرهای تست شناسایی پیموده و تحلیل میشوند. با بهره گرفتن از شرط مسیر پیموده شده محدوده دامنه کوچکتر شده تا آنکه به محدوده مورد نظر برسد برای اشکار شدن بیشتر موضوع، به مثال زیر توجه کنید: میخواهیم با بهره گرفتن از روش کاهش دامنه پویا دامنه سه متغییر تابعی به نام MID (x,y,z) که هدف از آن پیدا کردن میانه بین سه متغییر است کاهش دهیم به طور پیش فرض دامنه هر متغییر بین -۱۰ تا ۱۰ است. گراف کنترل جریان به در شکل(۲-۴) نشان داده است در این گراف گره آغازین ۱ و گره پایانی ۱۰ است حال فرض کنید بخواهیم مسیر ۱-۲-۳-۵-۱۰ را مطابق آنچه که با خطوط نقطه چین نشان داده شده است طی کنیم در این مسیر سه شرط وجود دارد که دامنه ورودی متغییرها را محدود خواهند کرد زمانیکه بخواهیم از مسیر بین ۱-۲ عبور کنیم که شرط آن به صورت y < z است نیاز به یک نقطه برای تقسیم دامنه داریم این نقطه را صفر در نظر میگیریم و دامنه بین ۱۰- تا ۰ را به y و دامنه بین ۱ تا ۱۰ را به z اختصاص میدهیم برای عبور از مسیر ۲-۳ که شرط آن x<= y است نقطهی تقسیم کننده دامنه را -۵ در نظر میگیرم که دامنهی x بین ه تا -۵ و دامنه y بین -۵ تا -۱۰ است این فرایند در شکل(۲-۵) نشان داده شده است.
شکل (۲‑۴):گراف کنترل جریان برنامهی MID [30]
شکل (۲‑۵): نمایش دامنه قبل و بعد از تقسیم [۳۰]
روش اسکیما:
از روشهایی مورد توجه در زمینه کاهش هزینه اجرا، روش تولید جهش اسکیما MSG [31][25] است به طور کلی در این روش تکه برنامهای مشابه از برنامهی اصلی ایجاد شده که در آن مشخصههایی مانند شناساگرهای داده ها، ثابتها و … وجود ندارد و این مساله باعث افزایش سرعت کامپایل می شود. این روش از چهار متغییر اصلی (Meta Mutant) M، G (Mutagens) ،ِD ، Meta procedure تشکیل شده است برای تولید M برای برنامهی P ابتدا ابر جهش مورد نظر را از درون لیست تولید کننده جهش G که از مجموعه ای از ابر رویه ها است (به عنوان مثال ابر رویه عملگر جایگزینی حسابی *AOR در قطعه کد زیر نمایش داده شده است) انتخاب می شود.
PROCEDURE AOrr
(LeftOp,RightOp:REAL; ChangePt:INTEGER):REAL;
BEGIN
CASE Variant(ChangePt) OF
aoADD: RETURN LeftOp + RightOp;
| aoSUB: RETURN LeftOp - RightOp;
| aoMULT: RETURN LeftOp * RightOp;
| aoDIV: RETURN LeftOp / RightOp;
| aoMOD: RETURN LeftOp MOD RightOp;
| aoRIGHT: RETURN RightOp;
| aoLEFT: RETURN LeftOp;
ELSE
Error( “AOrr CASE out of range” );
RETURN 0.0;
END;
END AOrr;
پس از انتخاب و تولید جهش مورد نظر با بهره گرفتن از لیست توصیف کننده جهش D ارگومانهای ورودی ابر رویهی جهش، مقدار دهی می شود و بعد از آن بر روی برنامهی p اعمال و با مجموعه تست تولید و اجرا میشوند در نهایت نیز امتیاز جهش، محاسبه می شود در شکل(۲-۶) این فرایند نشان داده شده است. در کل این روش با جمع آوری برنامه اصلی و برنامهی جهش یافته در یک نسخه برنامه سبب کاهش هزینه فضای تست جهش می شود.
شکل (۲‑۶): فرایند MSG [31]
جهشهای برابر
گاهی اوقات ایجاد تغییر در کد برنامه سبب می شود که کد تغییر یافته از نظر دستوری با کد برنامه، برابر باشد اما از نظر مفهومی عملکرد مشابهای با قبل از تغییر آن داشته باشد وجود این گونه جهشها اگر چه در کارکرد ظاهری برنامه تفاوتی ایجاد نمیکند اما با ایجاد اختلال در محاسبهی امتیاز جهش، سبب سردرگمی و اختلال در تشخیص مجموعه تست مناسب می شود. در [۳۲] برای بررسی اثرات و چالشهای ایجاد شده بر اثر جهشهای برابر، یک چهار چوب به نام JAVALANCHE [33] براساس پارامترهای :۱- تمرکز برروی استفادهی کمتر از عملگرهای جهش ۲- استفاده از جهش اسکیما ۳- پوشش داده ها، ارائه شده که با بهره گرفتن از آن برای برنامهی JAXEN XPATH query engine 9819 جهش منحصر به فرد ایجاد می کند که ۵۱۲۷ تای آنها با هیچ مورد تستی کشف نشدهاند. نویسنده به طور کلی جهشها را به سه دسته تقسیم می کند: ۱- جهشهای پوشش داده نشده جهشهایی هستند که توسط هیچ مورد تستی اجرا نشدهاند که تعداد آنها ۳۱۹۴ (۳۲%) بود. ۲- جهشهایی که از بین رفتهاند تعداد این جهشها ۴۶۹۲ (۴۸%) بود. ۳- جهشهایی که اجرا شده اند اما از بین نرفتهاند که تعداد آن ۱۹۳۳ (۲۰%) بود. و در ادامه نویسنده ۲۰ نمونه جهش را به صورت تصادفی انتخاب می کند که برای کشف یک جهش برابر زمانی بین ۱ نا ۵۰ دقیقه و برای از بین بردن تمام جهشها ۱۰ ساعت صرف شد در مجموع تعداد جهشهای برابر در یک مجموعه جهش درصدی بین ۱۰ تا ۴۰ است. این مساله جهشهای برابر را تبدیل به یکی از دغدغه های تست جهش کرده است و تاکنون روشهای زیادی برای مقابله با تولید و کشف آن ارائه شده است. یکی از این روشها CBT[26] است. به طور کلی برای آنکه یک جهش، توسط موارد تست از بین برود، باید سه شرط وجود داشته باشد ۱- مورد تست بتواند به بخشی از کد برنامه که جهش یافته دسترسی داشته باشد و آنرا اجرا کند. (شرط دسترسی[۲۷]) ۲- پس از اجرای یک ماژول خاص، خروجی برنامهی جهش یافته با خروجی برنامهی اصلی، تفاوت داشته باشد. (شرط ضرورت[۲۸]) ۳- پس از اجرای کامل برنامه جهش یافته، آلودگی ایجاد شده در برنامه به سبب جهش در کل برنامه پخش شده تا آنکه خروجی آن، با خروجی برنامهی اصلی متفاوت شود. ( شرط کفایت[۲۹]) سیستم محدودیت چیست؟ یک ساختار مرکب سلسله مراتبی از حالات، محدودیتها و عبارتها[۳۰] است که هر حالت شامل متغییرها، پرانتزها و عملگرهای آن زبان خاص است و به طور مستقیم از عبارت درون شرطها و یا سمت راست عبارتهای برنامه ایجاد می شود هرمحدودیت شامل جفتی از حالات است که با بهره گرفتن از عملگرهای رابطهای مانند یا با عملگری مانند NOT به هم متصل میشوند، هر عبارت لیستی از محدودیتها است که میتوانند به صورت عطفی یا فصلی به هم متصل شوند CBT از طریق سیستم محدودیت، تکه کدهایی برای تضمین ارضاء شرط ضرورت به برنامه اضافه می کند اما در مورد شرط کفایت تنها به این فرض که اگر شرط ضرورت ارضاء شود شرط کفایت نیز ارضاء خواهد شد بسنده می کند. برای شرح بیشتر به عنوان مثال: کد برنامهی پیدا کردن بیشترین که در زیر نوشته شده است را در نظر بگیرید، خطوطی از کد برنامه که با مشخص شده اند کدهای جهش یافتهی اضافه شده به برنامه هستند. اگر خط کد MAX = ABS (M) را در نظر بگیریم برای آنکه جهش ایجاد شده توسط تابع قدر مطلق تبدیل به یک جهش برابر نشود محدودیت متناظر M < 0 برای آن تولید می شود زیرا تنها در صورتی که مقدار M منفی باشد این جهش، در خروجی برنامه تغییر ایجاد می کند پس باید دادهی تستی که برای M تولید می شود محدودیت تخصیص یافته به آن را نیز ارضاء کند [۲۹].
| COSNSTRAINT | FORTRAN SOURCE | |
| MAX=M | ۱ | |
| M≠N | MAX=N | |
| M<0 | MAX=ABS(M) | |
| IF (N .GT. M) MAX = N | ۲ | |
| (N > M) ≠ (N < M) | IF (N. LT. M) MAX= N | |
| (N > M) ≠ (N ≥ M) | IF (N. GE. M) MAX = N | |
| RETURN | ۳ | |
در جدول(۲-۶) محدودیتهای متناظر با هر جهش، ذکر شده است. در این جدول A و B نماد آرایه، و عملوندهای شامل عدد کاراکتر و … ، و عملگر دوگانی، C مقدار ثابت و X و Y متغییرهای عددی هستند.
جدول(۲‑۷): محدودیتهای تولید شده متناظر با جهشها [۲۹]
| Constraint | Type |
| aar | |
| abs | |
| acr | |
| aor | |
| asr | |
| car | |
| cnr | |
| csr | |
| der | |
| lcr | |
| ror | |
| sar | |
| scr | |
| svr |
- DeMilli و A. J. Offutt[29] [34] یک روش منطقی ریاضی برای تشخیص خودکار مسیرهای غیر قابل دسترسی، در برنامه ارائه می کنند. ابتدا برای تعریف هر کدام از شرایط کفایت s ضرورت n و دسترسی r با بهره گرفتن از D که نماد کل دامنه ورودی تست است نمادهای به شکل ،، که به ترتیب که به ترتیب شروط کفایت، ضرورت و دسترسی را ارضاء می کند، است به عنوان مثال: شرط کفایت اینگونه بیان می شود: که در آن شامل بخشی از دامنه است به طوریکه شرط کفایت را ارضاء می کند و بخشی از دامنه است که شرط را ارضاء نمیکند. به طور کلی، رابطه دامنه ورودی تولید شده برای سه شرط فوق الذکر مطابق شکل(۲-۷) است. به طور خلاصه میتوان نوشت t دادهی مورد تست موثر برای از بین بردن جهش M است اگر برای M، باشد(برهان ۱)، اگر t یک مورد تست موثر باشد که جهش M را از بین ببرد آنگاه (برهان ۲) . (برهان ۳) اگر P یک برنامه باشد و M یک نسخه جهش یافته از P باشد و P(t) ، M(t) خروجیهای هر دو برنامه باشد M یک جهش برابر با P است اگر تنها برای تمامی t عضو D، P(t) = M(t) باشد. در ادامه برای نشان دادن کشف خودکار جهشهای برابر، سه تئوری مطرح و اثبات می کند که به طور اختصار یکی از آنها را بررسی خواهیم کرد. فرض کنید بخشی از دامنه باشد وموارد تست درآن بتواند شرط دسترسی را برای جهش M ارضاء کند. اگر غیر قابل دسترسی باشد ( تهی باشد) جهش برابر است. و نتیجه برابر است. اثبات:
| M is equivalent | از روی تعریف و برهان ۱ |
| . | برهان ۳ |
| از روی قوانین مجموعه و برهان ۳ | |
| is equivalent | در نتیجه کل |
شکل (۲‑۷): ارتباط دامنه ورودی سه شرط کفایت، ضرورت و دسترسی [۲۹] [۳۴]
برای تشخیص جهشهای برابر(که براثر مسیرهای غیرقابل دسترس وتولید کد برابر به وجود میآِید ) با بهره گرفتن از تشخیص تضاد میان آنها عمل می کند: ۱-شرط شرط را خنثی می کند اگردامنهی آنها با یکدیگر همپوشانی نداشته باشد و همچنین متغییرهای آنها تمام مقادیر دامنه را پوشش دهند. (مثال و ) ۲- شرط بخشی از شرط را خنثی می کند اگر دامنه آنها با یکدیگر همپوشانی نداشته باشد و همچنین متغییرهای آنها تمام مقادیر دامنه را پوشش ندهند. (مثال و ) ۳- دو شرط به صورت مفهومی برابر هستند اگر در یک دامنه تعریف شوند. ۴- دو شرط در صورتی باهم برابرند، که در یک دامنه تعریف شوند و از نظر کد کاملا یکسان باشند.
خودکار سازی تست
تاکنون روشهای زیادی برای تولید خودکار موارد تست ارائه شده است که برخی از آنها را در زیر نامبرده و به اختصار شرح میدهیم:
روش تولید محدودیت
تحقیقات R. DeMilli و A. J. Offutt [29] منجر به تولید ابزاری برای خودکار سازی به نام Godzilla شد این ابزار با بهره گرفتن از روش CBT* و عملگرهای موجود، برای برنامههایی با زبانهایی مانند Berkeley، UNIX و … به طور خودکار جهش ایجاد می کند.
روش اجرای سمبلیک برای پوشش ساختار برنامه
این روش یک تکنیک برای تحلیل کد برنامه است(پس یک روش تست جعبه سفید است) در این روش به جای استفاده از داده های واقعی برای تست برنامه از سمبلها استفاده می شود. ایده اصلی روش اجرای سمبلیک اولین بار در ابزاری به نام DART [۳۱]مطرح شد [۳۵]. به طور خلاصه DART از سه تکنیک که در زیر عنوان شده است برای انجام خودکار تست واحد [۳۲]بهره میبرد:
- استخراج واسط برنامه
- ایجاد خودکار یک درایور برای واسط استخراج شده به جهت انجام تست خودکار
- تحلیل روند اجرای برنامه با تستهای تصادفی برای تولید ورودیهای جدید و تست مسیرهای مختلف برنامه با آنها
در حقیقت DART از ترکیبی از دو روش تست تصادفی و تولید تست پویا با بهره گرفتن از سمبلها بهره میبرد. DART با بهره گرفتن از روش تست پویا برخلاف روشهای تست تصادفی ساده در هر بار اجرای کد برنامه شرطهایی از آنرا که می تواند ارضاء کند را به محدودیتهای مسیر یا همان PC عطف می کند و برای ارضاء سایر شرطها نیز بردارهای ورودی جدید تولید می کند تا زمانیکه به یک خطا در برنامه برخورد کند. یکی از اشکالات عمدهی روش DART این است که با برخی از ورودیهایی که برای پوشش مسیرها تولید شده اند در حلقهی بینهایت قرار گیرد. در حقیقت در پایان اجرای DART در سه حالت می تواند اتفاق بیافتد: ۱- پوشش تمام مسیرها ۲- برخورد به خطا ۳- قرار گرفتن در حلقهی بینهایت. نزدیکترین روش اجرای سمبلیک به DART، CUTE [۳۳][۳۶] است، این روش برخلاف DART علاوه بر پشتیبانی از داده های صحیح از اشارهگرها نیز پشتیبانی می کند، همچنین می تواند برای عبارتهای شرطی درون توابع ورودی تولید کند. CUTE توانایی استخراج واسط را به طور خودکار ندارد و آنرا به کاربر محول کرده است یکی دیگر از مزیتهای مهم آن استفاده از دو روش: تولید ورودی به ترتیب فراخوانی [۳۴]و حل ساختارهای دادهای ثابت [۳۵] است که مشکل قرار گیری DART در حلقهی بینهایت را حل می کند. PexMutator [22] یکی از اولین روشهایی است که روش تولید خودکار موارد تست را با تست جهش ترکیب می کند. PexMutator به جای آنکه محدودیتها بر روی برنامهی اصلی قرار دهد و اجرا کند آنرا بر روی ابر برنامهای[۳۶] ایجاد شده از آنها قرار میدهد. PexMutator در چهار مرحله یک برنامه را تست می کند: ۱- تولید جهش برای برنامهی تحت تست با بهره گرفتن از سه عملگر تولید کننده جهش ABS، AOR، LCR، ROR و UOI 2- تولید محدودیتهای کشندهی ضعیف [۳۷] (این محدودیتها در حقیقت همان محدودیتهای تولید شده توسط CBT هستند.) برای هر جهش تولید شده. ۳- قراردادن محدودیتها تولید شده در محل مناسب در ابر برنامه: قرار دادن محدودیتها در جای نامناسب سبب ایجاد نقص در اجرای برنامه می شود بنابراین قرار دادن آنها در جای مناسب حائز اهمیت است، برای این کار ابتدا آنها را به دو دسته عبارتهای شرطی و غیر شرطی تقسیم می کند. در هر عبارت شرطی سه نقطه می تواند کاندید قرار گیری محدودیت باشد که عبارتند از: قبل از عبارت شرطی، درون عبارت شرطی و بعد از عبارت شرطی که بهترین محل قبل از عبارت شرطی است از طرف دیگر برای عبارتهای غیر شرطی نیز بهترین محل برای قرارگیری محدودیتها قبل از عبارت غیر شرطی است. ۴- استفاده از موتور DSE ، PEX [37] برای ت ولید ورودیهای تست به جهت ارضاء محدودیتها برای نرمافزارهای .NET استفاده می کند.
یکی از پروژه های خوش نام که در این حوزه برای برنامه های تحت زبان جاوا وجود دارد JPF [۳۸][۳۸] است JPF در حقیقت خود یک ماشین مجازی بر روی ماشین مجازی جاوا است که توانایی تست برنامه ها به صورت اجرای سمبلیک را دارد. البته اجرای سمبلیک تنها یکی از ویژگیهای JPF است از ویژگیهای دیگر JPF میتوان به چک کننده مدل [۳۹] آن اشاره کرد که با بهره گرفتن از آن می تواند بخش عمدهای از کد برنامه را پوشش دهد به گونه ای که حتی بخشهایی از برنامه که پتانسیل خطا در آن وجود دارد را شناسایی کند یکی دیگر از ویژگیهای خوب JPF شناسایی بخشهایی در کد برنامه است که در امکان ایجاد شرایط رقابتی وجود دارد. در JPF ابزارهایی به صورت افزونه برای روش اجرای پویای سمبلیک وجود دارد که تاکنون با ورژن جدید سازگار نشده اند. در سالهای اخیر با بهره گرفتن از ویژگیهای JPF روشهای جدیدی ارائه شده است که در مقالات [۳۹] و [۴۰] به آن پرداخته شده است.که در فصل سوم به تفصیل توضیح داده خواهد شد.
نتیجه گیری
در این بخش ابتدا فرضیات تست جهش را مطرح کردیم سپس درباره عملگرهای موجود برای ایجاد جهش در سطح تابع و در سطح کلاس را معرفی کردیم در قسمت بعد چالشهای پیش روی تست جهش، از جمله هزینه بالا و جهشهای برابر را شرح دادیم و تکنیکهایی برای حل آن ارائه دادیم که از جمله آنها میتوان به تولید کمتر جهشها (که یکی از بهترین روشها در این حوزه دستهبندی جهشها [۱۵] است)، روش CBT [29] که دامنه ورودی ها و تعداد جهشهای برابر را کاهش میدهد، اجرای سمبلیک برای تولید ورودیهای تست به صورت پویا [۴۱] که هزینه اجرای تست را کاهش میدهد. در انتها نیز برخی از روشهای ذکر شده را در جدول(۲-۷) مقایسه میکنیم لازم به ذکر است به دلیل آن که در انجام تست جهش، ما دو پارامتر از بین رفتن جهشها و پوشش مسیرهای تست را مورد توجه قرار دادهایم مقالاتی که معیارشان پوشش مسیرهای گراف کنترل جریان بوده نیز در این جدول آورده شده است.
جدول(۲‑۸): مقایسه بین روشهای مختلف
| ردیف | نام | روش مورد استفاده | مدل نگاشت کد برنامه | نوع داده های ورودی | درصد پوشش مسیر “پ” / از بین بردن جهش“ج” | سطح جهش | بیشترین تعداد خط کد تست شده Max Loc | نحوه دستهبندی مسیرهای تست | روش تولید ورودیهای تست | معیارهای مورد بحث |
| ۱ | Godzilla | CBT(Constrained Based Testing) | _ | عددی | ۹۸%ج | یک | ۵۵ | _ | خودکار-تخمینی | از بین بردن جهش |
| ۲ | PexMutatuor | DSE | درخت اجرا | عددی | ۴%/۸۶ج | یک | _ | _ | خودکار-تصادفی اجرای سمبلیک |
از بین بردن جهش |
| ۳ | [۳۹] | DSE/MSG | گراف کنترل جریان | عددی | ۸۵% ج | یک | ۵۰۰ | _ | الگوریتم ژنتیک اجرای سمبلیک | از بین بردن جهش |
| ۴ | [۴۰] | DSE/MSG/Evolutionary | گراف کنترل جریان | عددی | ج۸۳٫۳% | _ | _ | _ | الگوریتم ژنتیک اجرای سمبلیک | از بین بردن جهش |
| ۵ | [۴۲] | Ant colony | _ | عددی پیوسته | ۸۹% ج | یک | _ | کلونی مورچه و PDF | از بین بردن جهش | |
| ۶ | [۴۳] | Bee colony | گراف کنترل جریان | عددی | پ۹۳٫۰۷% | _ | _ | کلونی زنبور | پوشش کد | |
| ۷ | [۱۵] | k-means | _ | عددی | % ۹۹٫۶ج | یک | _ | k-means | _ | از بین بردن جهش |
| ۹۹٫۳%ج | یک | _ | agglomerative |
| فصل سوم روش تحقیق |
در ابتدای این فصل به شرح روشهایی که تاکنون برای انجام تست جهش استفاده شده است میپردازیم و سپس به شرح روش ارائه شده در این پایان نامه که از دو بخش اصلی تزریق جهشها به کد برنامه و تولید ورودیهای تست از طریق روش بهینه سازی زنبور است میپردازیم.
شرح روشهای مشابه
روش مبتنی بر CBT
در شکل(۳-۱) ساختار Godzilla نمایش داده شده است. همانطور که مشاهده میکنید سه گره از این گراف که با مستطیل نشان داده شده اند، سه ابزار مجزا هستند که از طریق ارتباط بین فایلها که با بیضی نمایش داده شده اند با یکدیگر تعامل دارند، برای هر عبارت در برنامه تحلیلگر مسیر، یک محدودیت ایجاد کرده و تا زمانی که محدودیت ارضاء نشود، مسیر برنامه اجرا نخواهد شد. از طرف دیگر تولید کننده محدودیت برای عبارتهای شرطی و ارضاء شرط ضرورت* محدودیت تولید می کند و سپس به ارضاء کننده محدودیت ارسال می شود. ارسال کننده، تمام شرطهای ضرورت را دریافت می کند، عبارتهای برابر را پیدا کرده و آنها را در یک مسیر مناسب عطف نموده و در نهایت برای آنها داده های تست تولید می کند.
شکل (۳‑۱): ساختار Godzilla
روش اجرای سمبلیک
هر نقطه از اجرای سمبلیک برنامه شامل مقادیری برای متغییرهای برنامه در همان نطقه، محدودیت مسیر بر مقادیر در ان نقطه و شمارندهی برنامه است. محدودیت مسیر در حقیقت یک فرمول بولی است که از ترکیب عطفی شرطهای مسیر پیموده شده در برنامه جمع آوری می شود و مقادیر سمبلیک ورودی باید این شرطهای را ارضاء کنند و شمارندهی برنامه عبارت بعدی در برنامه که باید اجرا شود را نشان میدهد، برای هر برنامه درخت اجرایی ایجاد می شود در حقیقت با عبور از هر شرط در کد برنامه از طریق دستور fork یک انشعاب در این درخت ایجاد می شود، اگر عبارت شرطی این انشعابات غیر ارضاء شدنی باشد مسیر مربوط غیر ممکن می شود و اگر عبارت شرطی انشعاب برنامه ارضاء شدنی باشد آن مسیر، به عنوان یک مسیر ممکن [۴۰]تلقی میگردد [۴۱]. به طور کلی داده های تست تولید شده، به سه گروه تقسیم میشوند:۱- داده های تست ساختاری که تولید میشوند تا مولفههای خاصی از ساختار برنامه پوشش دهند. ۲- تولید کننده مشخصهی داده ها که داده های تست را برای دامنهی ورودی به صورت رسمی بیان می کند. ۳- تولید داده ها به صورت خودکار. به طور معمول در روش ساختاری یک مدل انتزاعی از برنامه (یک گراف کنترل جریان) و بعضی از مدلهای اجرای سمبلیک نمایش داده میشوند. برخی از موارد اجرای سمبلها نیاز به توان محاسبات عادی دارد. این محاسبات توسط عملگرهایی که در زبان برنامه نویسی برای اجرا سمبلها تعریف شده اند، پشتیبانی میشوند. در اجرای سمبلیک یک برنامه، مفاهیم تغییر می کنند اما قواعد دستوری و کد برنامهی اصلی، تغییر نخواهد کرد. تنها راه ورودی اشیا دادهای سمبلیک به برنامه، از طریق ورودیهای آن است. این ورودی ها به صورت لیستی مانند تعریف میشوند و به متغییرهای برنامه اختصاص داده میشوند. از دیگر پارامترهای مهم در اجرای سمبلیک PC [۴۱] که از شرط مسیرهای طی شده بدست آمده است در حقیقت PC شرط مسیرهای موجود را به جهت ادامه اجرای یک مسیر با یکدیگر عطف می کند و هر اجرای سمبلیک با مسیری آغاز می شود که PC آن از قبل درست باشد [۴۴]. به عنوان مثال اگر قطعه کدی به صورت زیر داشته باشیم:
| int x, y; if(x > y) } x = x+y; y = x-y; x = x-y; if(x - y > 0) assert false; { print(x, y) |
اجرای سمبلیک کد به صورت شکل(۳-۲) است در این شکل X و Yنمادهای سمبلیک استفاده شده برای متغییرهای x و y هستند شمارندهی برنامه [۴۲]با دوایر قرمز در شکل مشخص شده است و مقدار محدودیت مسیر نیز در ابتدای اجرا برابر true قرار گرفته اما در ادامه با توجه به شرطهای مسیرهایی که از آنها عبور می کند تغییر می کند.
شکل(۳‑۲): نمونه ای از اجرای سمبلیک
همانطور که در جدول(۳-۱) مشاهده میکنید در این قطعه کد به طور کلی سه مسیر مستقل وجود دارد که هر کدام محدودیت مخصوص به خود را دارند محدودیت مسیرهای ۱و۲ را میتوان با ورودیهای مناسب ارضاء کرد اما محدودیت مسیر ۳ را نمی توان با هیچ گونه ورودی ارضاء کرد بنابراین ۳ مسیر در بخش مسیرهای غیرممکن قرار میگیرد.
جدول(۳‑۱): نمونه ای از مسیرها و محدودیتهای انها در اجرای سمبلیک
| ردیف | مسیر | محدودیت مسیر |
| ۱ | ۸،۱ | X <= Y |
| ۲ | ۸،۵،۴،۳،۲،۱ | X>Y & Y-X<=0 |
| ۳ | ۶،۵،۴،۳،۲،۱ | X>Y & Y-X>0 |
برای ارضاء محدودیتهای بدست آمده از مسیر در روش اجرای سمبلیک از ابزارهایی که براساس تئوری پیمانهای قابلیت ارضاء SMT [۴۳] هستند استفاده می کنند در این روش که از معروفترین آنها میتوان از Yices [45] نام برد این ابزار براساس الگوریتم DPLL [۴۴] کار می کند که شرح آن از حوصلهی این پایان نامه خارج است اما به طور خلاصه میتوان اشاره کرد که برای حل مسائل از جدول سیمپلکس بهره میبرد و با از آن میتوان در مورد ارضاء پذیر بودن یا نبودن یک ترکیب خطی بولی از معادلات یا نامعادلات تصمیم گیری کرد. روش Yices می تواند درباره ارضاء پذیر بودن یا نبودن فرمولهای مختلف شامل معادلات حقیقی خطی صحیح، اسکالرها، رکوردها، نوع داده های تودرتو، ارائههای توسعه پذیر، بردارهای بیتی ثابت و… تصمیم گیری کند یکی از مشکلات اصلی این روشها چنانکه در بالا مطرح شد قابلیت حل معادلات یا نامعادلات تنها به صورت خطی است در حالیکه ممکن است محدودیتهای مسیر به صورت خطی نباشد برای حل این مشکل روشهایی دیگری در این حوزه مطرح شد که اجرای پویای سمبلیک DSE[45] نام دارد تفاوت اصلی روش اجرای پویای سمبلیک و روش اجرای سمبلیک در توانایی اجرای یک برنامه به صورت واقعی [۴۶] برنامه، در کنار اجرای سمبلیک آن است برای آشکار شدن این موضوع به مثال زیر توجه کنید:
فرض کنید قطعه برنامهای به صورت زیر داشته باشیم. و فرض کنید مقادیر ۳- و ۷ به طور تصادفی و به ترتیب برای x و y تولید شده است چون محدودیت انشعاب برنامه به صورت معادله خطی نیست SMT نمیتواند آن را ارضاء کند بنابراین انشعاب Else اجرا خواهد شد در حالیکه مقدار واقعی z برابر با ۹ بوده است که با استفاده قابلیت اجرا واقعی یک برنامه در کنار اجرای سمبلیک روش DSE، میتوان مقدار ۹ را برای z قرار داد و انشعاب then شرط را نیز اجرا کرد.
void test_me(int x,int y){
z = x*x*x + 3*x*x + 9;
if(z != y){
printf(“Good branch”);
} else {
printf(“Bad branch”);
abort();
}
}
ترکیب روش اجرای پویای سمبلیک (DSE) با اسکیما
Mike Papadakis و Nicos Malevris از ترکیب دو روش DSE و اسکیما چهارچوبی برای تست جهش نرمافزارهای جاوا ارائه می کنند. فرایند تست با تولید ابر برنامهی اسکیما آغاز می شود همچنین ابزارهای تولید کنندهی اسکیما توانایی ایجاد ساختار برنامه به صورت گراف کنترل جریان را دارند سپس با بهره گرفتن از اجرای DSE بر روی ابر برنامهی اسکیمای ایجاد شده موارد تست مناسب ایجاد می شود و به اجرا کننده تست سپرده میشوند تا مسیر اجرا را انتخاب کند و با آنها اجرا کند این روند تا زمانیکه به میزان مشخصی از تعداد تکرار یا محدودیت زمانی برسیم ادامه میابد. یکی از مزیتهای مهم این روش نسبت به روشهای دیگر استفاده از مکانیزمی برای یافتن کوتاهترین مسیر در کد برنامه به جهت رسیدن به عبارت جهش یافته است، این امر از طریق یک روش اکتشافی محقق می شود در حقیقت برنامه به دنبال اجرای انشعاباتی است که کمترین فاصله را با عبارت جهش یافته داشته باشند. مشابه با کار فوق الذکر چهارچوب دیگری در این زمینه وجود دارد که با گرد آوری ابزارهای مختلف یک گام به جلو رفته و تست جهش را با ترکیب سه روش DSE، روشهای تکاملی و به ویژه اسکیما انجام میدهد. به بیان نویسنده با ترکیب این سه ابزار و اضافه کردن روش اسکیما به آن میتوان یک چهارچوب که عملکردی به مراتب قویتر از آنها به صورت جداگانه دارد ایجاد کرد ، در گام نخست همانگونه که در شکل(۳-۳) نشان داده شده است برای تولید ورودیهای تست از ECFG [۴۷] استفاده می کند که توانایی پوشش انشعابات برنامه و از بین بردن جهشها را به صورت خودکار دارد. در گام دوم با بهره گرفتن از روش اسکیما جهشها را درون کد برنامه جایگذاری می کند. در مرحله سوم از سه ابزارetoc (این ابزار با بهره گرفتن از الگوریتم ژنتیک ورودیهای مناسب تست را تولید می کند)، concolic و JPF-SE[48] (قابلیت اجرای پویایی سمبلیک را دارند) برای تولید ورودیهای تست، بهره میگیرد و همچنین عملکرد این سه ابزار را باهم مقایسه می کند.
شکل(۳‑۳): چهارچوب ارائه شده در مقاله [۴۰]
روش مشابه دیگری در این حوزه توسط Mike Papadakis مطرح شده است که مانند روش قبل با بهره گرفتن از شمای جهش و DSE به از بین بردن جهشها می پردازد مهمترین تفاوت این روش با روش قبل در استفاده از یک تابع اکتشافی [۴۹]مناسب برای یافتن کوتاهترین به جهت رسیدن به کد جهش یافته است در این روش انشعاباتی از کد برنامه اجرا خواهد شد که فاصلهی کمتری در رسیدن به کد جهش یافته دارند.
روشهای مبتنی بر جستجو
توسط K. Ayari،S. Bouktif و G. Antoniol [42] ارائه شده و براساس الگوریتم کلونی مورچه است. در مدل ارائه شده که در شکل(۳-۴) نشان داده شده است هر گره نشان دهنده یک پارامتر ورودی است. مسیرهای بین گرهها نشان دهنده تمامی مقادیر ممکن در دامنه آن گره است هر مورچه در هنگام شروع به صورت تصادفی مسیرهای بین گرهها را میپیماید پس از عبور از تمامی گرهها، برنامه را تست کرده و نتایج آنها را ارزیابی می کند. یکی از دغدغه های اصلی نویسنده ایجاد روشی برای تولید داده های ورودی پیوسته است برای حل این مشکل از روش[۵۰] PDF استفاده می کند. با بکارگیری این روش هر مورچه در هنگام عبور از مسیر فرمون دار به تشخیص خود می تواند مقداری از مسیر اصلی فاصله بگیرد تا بتوان دامنه پیوستهای از ورودی ها به وجود آورد.
شکل(۳‑۴): کلونی مورچه و تست جهش
شرح ابزار ارائه شده
ابزار ارائه شده براساس برنامههایی که با زبان جاوا نوشته شده اند کار می کند ما در روش خود برای تحقق سه اصل مطرح شده انجام کمتر، انجام هوشمندانه و انجام سریعتر به ترتیب از تکنیکهای تولید کمتر جهش، استفاده از یک روش فرابتکاری برای تولید داده های تست همراه با برخی ماژولهای کمکی اجرا به تست به صورت موازی و ابزارهای ترجمه بایت کد در جاوا استفاده کردیم. ابزار ارائه شده از چهار بخش اصلی تشکیل شده است که به شرح زیر است:
- تولید کننده جهشها
- تولید کننده ورودیهای تست
- اجرا کننده تست
- دستیاران
در ادامه هر کدام از بخشها را به طور جداگانه توضیح میدهیم و در انتها با جمع بندی بخشها مدل نهایی را ارائه خواهم نمود.
ابزارهای ارائه شده مبتنی بر جاوا
Jester [۵۱]: این ابزار توسط Ivan Moore بین سالهای ۲۰۰۰ تا ۲۰۰۵ ایجاد شد به گفته ی سایت Jester این ابزار بخشی از کد های نرمافزار را میابد که با تست های معمولی پوشش داده نشدهاند. یکی از مشکلات عمدهی این ابزار کند بودن آن است که با تحقیقات انجام شده مشخص شد کندترین بخش درآن کامپایل کد است زیرا این ابزار تغییرات را بر کد منبع اعمال می کند که نیاز به کامپایل مجدد دارد.
Jumble[52]: Jumble به شما از صفر تا صد را میگوید! Jumble، یک ابزار تست جهش است که در بین سالهای ۲۰۰۳ تا ۲۰۰۶ توسعه یافته است که در سطح کلاس عمل کرده و با Juint تجمیع شده است. هدف این ابزار اندازه گیری کارائی داده های ورودی است. در این ابزار برای اولین بار جهش ها با بهره گرفتن از ترجمه بایت کد با بهره گرفتن از ابزار BCEL اعمال شد از سوی دیگر از روشهای اکتشافی برای چک کردن جهشها استفاده شده است.
Judy [46]: یک ابزار مدرن برای تست جهش است که از ۲۷ عملگر پشتیبانی می کند. برای کاهش هزینه کامپایل Judy از یک روش به نام FAMTA [۵۳]رونمایی کرد عملگرهای جمعی و اسکیما استفاده می کند که در مجموعه تعداد کامپایلها را به یک کاهش میدهد در بخش ارزیابی این ابزار نیز نتایج خوبی حاصل شده چنان که برای برنامهای با ۴۲۲۱۲ خط کد پوشش ۹۵% بدست آمده است.
PIT[54]: تست جهش واقعی! PIT یک ابزار تجاری در زمینه تست جهش است که به نقل از وب سایت آن سرعت، راحتی استفاده، توسعه پویا و پشتیبانی پویا را میتوان به عنوان مزایای آن دانست. اما مزایای آن به همین جا ختم نمی شود PIT از یک مکانیزم افزایشی برای بهینه سازی استفاده می کند به گونه ای که با ذخیره نتایج تست قبلی و مقایسه آن با پیش فرضهایی که از قبل دارد نتایج برخی از اجرایهای کد را پیش از اجرای آن حدس میزند در نتیجه آنها را اجرا نمیکند.
Bacterio [47]: بیشتر روشهای تست جهش از جهشهای قوی ضعیف تا اجرای موازی در این ابزار پیاده سازی شده است.
Javalanche [48]: یکی از ابزارهای آکادمیک در زمینه تست جهش است، که براساس عملگرهای جهش انتخابی به منظور کاهش تعداد عملگرها، اجرای موازی جهشها، اسکیما، ترجمهی بایت کد به منظور جلوگیری از کامپایل مجدد کد جهش یافته و بهینه سازی تولید ورودی ها از طریق ذخیره سازی اطلاعات پوشش هر ورودی، به جهت پوشش بخش جهش یافته عمل می کند. یکی از مزایای عمدهی این ابزار تولید بسیار کم جهشهای برابر است.
Mujava [۵۵] [۱۰]: پس از تستی که ما بر روی این ابزار انجام دادیم میتوان برخی از مزایا و معایب آن را ذکر کرد، از مزایای آن میتوان به ۱- استفاده از روش ترجمه بایت کد جاوا که از ابزار BCEL [۵۶][۴۹] و همچنین تولید تابع ابر جهش است (که در بخش روش اسکیما در فصل۲ توضیح داده شده است) که سبب کاهش تعداد دفعات کامپایل به دو مرتبه می شود یک مرتبه برای کامپایل کد برنامهی اصلی و یک مرتبه برای کامپایل ابر برنامهی جهش یافته۲ - پیاده سازی عملگرهای تست جهش در سطح کلاس اشاره کرد و در سطح تابع به طور کامل ۳- واسط کاربری مناسب ۴- و در دسترس بودن ( بسیاری از ابزارهایی که تاکنون پیاده سازی شده اند در دسترس قرار ندارند)۵-پشتیبانی از Junit [۵۷]که از طرفی هم می تواند مزیت باشد هم عیب باشد زیرا استفاده از Junit نیاز به دانش خاصی دارد. اشاره کرد. از معایب آن میتوان ۱-عدم ارائه مکانیزمی برای جلوگیری از ورود جهشهای برابر ۲- عدم ایجاد جهشهای سطحهای بالاتر ۳- عدم تولید داده های تست به صورت خودکار اشاره کرد.
تولید کننده جهشها
در ابزار ارائه شده برای تولید جهشها نیازی به کد برنامه نداریم و تنها با دستکاری بایت کدهای جاوا، جهشها را به کد برنامه اعمال میکنیم برای این امر به طور خودکار یک نسخه کپی از بایت کد برنامه اصلی تهیه میکنیم سپس یک نسخه از آن را پس از آماده سازی* که در بخش دستیاران به آن خواهیم پرداخت به عنوان فایل اصلی نگهداری کرده و نسخه دیگر را پس از اعمال جهشهای لازم به محل مناسبی کپی میکنیم.
برای اعمال جهشها از پنج عملگر کلیدی که در بخش پیشین مطرح شد استفاده کردیم ABS، UOI، ROR، AOR وLOR همانطور که در فصل دوم اشاره شد این عملگرها توانایی تولید ۹۵% جهشها را دارند[۱۹]. از طرف دیگر ماژول تولید کننده جهش می تواند هر سطحی و هر ترکیبی (البته به تعدادی که سبب جلوگیری از کارکرد برنامه نشود و به بیان دیگر نقصها سبب از کار افتادگی برنامه نشود) از جهشها را بر روی یک فایل اعمال کند. برای افزایش سرعت و جلوگیری از کامپایل مجدد کد جهش یافته ما از ترکیب سه روش کامپایل جداگانه، ترجمهی بایت کد و اسکیما استفاده کردیم برای این کار ابتدا توابعی از پیش کامپایل شده را به عنوان عملگر جهش ایجاد کردیم که متغییرهای قطعه کدی از برنامه را به عنوان ورودی دریافت می کنند و با توجه به ارگومان انتخاب عملگر که با مشخص شده است جهشها اعمال میشوند. مقدار برابر تعداد حالتهای ممکن برای ایجاد جهش است به عنوان مثال در زیر شبه کد این تابع را برای عملگر AOR نشان دادیم در این تابع مقدار است(لازم به ذکر است که در حال حاضر این تابع برروی قطعه کدهایی از برنامه که شامل حداکثر دو متغییر هستند و یا عملگرهای میانشان یکسان است قابل اعمال است):
- Int AOR(, ,…,i)
- {
- switch(i){
- case1:
- return + + …
- case 2:
return - -…
- case 3:
return …
- case 4:
return …
}
}
اعمال این توابع به بایت کد برنامه اصلی، ما را از داشتن کد آن بی نیاز می کند که سبب می شود حتی برنامههایی که به صورت کد منبع بسته [۵۸] ارائه شده اند را تست کنیم و از طرف دیگر تنها نیازی به کامپایل کد آن نداریم (گرچه این شرایط زمانی محقق خواهد شد که در کد برنامه تغییراتی به وجود آید که با روش ما سازگار شود) برای شروع این کار باید با ساختار بایت کد در جاوا آشنایی داشته باشیم که البته آشنایی با بایت کد بدون واسطه کار دشواری است زیرا بایت کدها جاوا قابلیت خواندن و درک توسط انسان را ندارند بنابراین برای تغییر بایت کدهای جاوا ناگزیر به استفاده از ابزارهای واسط هستیم که میتوان به BCEL ، ASM [50] و SERP[51] اشاره کرد. ما برای تزریق جهشها به کد برنامه به علت افزایش سرعت و کارایی بیشتر از ASM استفاده کردیم.
از طرف دیگر با بهره گرفتن از این روش برای اعمال جهشها نیازی به لود مداوم بایت کد برنامه نداریم تنها با یک بار لود میتوانیم به تعداد محلهای مناسب از یک نوع جهش بر روی یک فایل جهش اعمال کنیم.
پس از انجام جهشهای لازم ماژول تولید کننده جهش آدرس های فایلهای جهش یافته و جهشهای موجود در هر یال را برمیگرداند[۵۹] تا توسط تابع تولید کننده و اجرا کننده تست مورد استفاده قرار گیرد از طرف دیگر این اطلاعات را درون لاگ [۶۰]فایل ذخیره می کند تا در صورت تمایل کاربر بتواند بدون ایجاد جهشهای جدید تست جهش را با داده های متنوع دیگری اجرا کند. در شکل(۳-۶) این کلاس و زیر بخشهای آن نشان داده شده است.
شکل(۳‑۵): ماژول تولید کننده جهش
تولید کننده ورودیهای تست
این بخش یکی از مهمترین مراحل انجام تست است و به عبارت دیگر عامل تعیین کننده موفقیت یا شکست یک تست است به طور کل برای تولید ورودی تست دو روش پویا و ایستا وجود دارد. روش ایستا مشابه آنچه که در بخش دوم تحت عنوان روش اجرای سمبلیک مطرح شده است که بدون استفاده از روش پویا قادر به حل برخی از مسائل نیست و روش پویا اجرای واقعی برنامه و استفاده از الگوریتمهای جستجو برای یافتن بهترین ورودیهای تست است که هردو روش دارای مزایا و معایب خود هستند [۴۳]. روش تولید داده ما مشابه روش ارائه شده در [۵۲] که برای تولید ورودیهای تست به جهت پوشش گراف کنترل جریان از الگوریتم کلونی زنبور [۵۳] بهره برده است.
الگوریتم کلونی زنبور
الگوریتمهای مبتنی بر هوش جمعی در سالهای اخیر در شاخه های مختلفی از علوم مورد توجه بوده است. یکی از ویژگیهای مشترک این الگوریتمها خاصیت مدیریت خود مختار [۶۱]است که خود دارای ۴ ویژگی است: ۱- بازخورد مثبت[۶۲]: یک قانون سرانگشتی[۶۳] است که برای ارتقاء در تولید ساختارهای مناسب استفاده می شود مانند مسیر به جای مانده از برخی گونه های مورچهها.۲- بازخورد منفی: ایجاد توازن برای بازخورد مثبت و کمک به حفظ ماندگاری ساختاری که براساس الگوهای جمعی کار می کند.۳- روشهایی مانند قدم زدن تصادفی و یا جابه جایی وظایف میان مولفههای جمعی برای انجام کار خلاقانه ضروری است. ۴- در کل خاصیت مدیریت خود مختار کمترین تقابل در انجام کارها را در سطح مولفههای اولیه تحمل می کند که به آنها این امکان را میدهد که همانگونه که از نتایج خود استفاده می کنند از نتایج دیگران نیز استفاده کنند. در این سیستمها چون کارها توسط موجودیتهای منحصربفرد انجام میگیرد اغلب، قابلیت انجام کارها به صورت موازی نیز وجود دارد.
در الگوریتم کلونی زنبور سه مولفهی اساسی وجود دارد: ۱- مواد غذایی که همان جوابهای مساله هستند. ۲-کارگران مستخدم ۳- کارگران غیر مستخدم، از طرف دیگر مولفههای الگوریتم کلونی زنبور میتوانند در دو مد کار کنند، جستجو برای پیدا کردن یک منبع شهد و ترک یک منبع غذایی. ارزش منابع غذایی به فاکتورهای زیادی وابسته است از جمله میتوان به میزان انباشت انرژی و میزان انرژی که میتوان از آن استخراج کرد اشاره کرد. زنبورهای مستخدم زنبورهایی هستند که به یک منبع غذایی مشخص منتصب شده اند در این وضعیت دو حالت ممکن است رخ بدهد استفاده از آن منبع و یا به اصطلاح استخدام شده در منبع. این زنبورها حامل اطلاعاتی در مورد یک منبع غذایی خاص شامل فاصله، جهت تا کندو و شایستگی منبع غذایی هستند که این اطلاعات را با احتمال مشخصی با زنبورهای دیگر به اشتراک میگذارند. زنبورهای غیر مستخدم این دسته از زنبورها به طور پیوسته به دنبال یک منبع غذایی برای استفاده هستند به طور کلی دو دسته زنبور غیر مستخدم وجود دارد دستهی اول زنبورهای پیشاهنگ هستند که اطراف کندو را برای منابع غذایی جدید جستجو می کنند. دستهی دوم زنبورهای ناظر هستند که در کندو منتظر اطلاعات زنبورهای مستخدم هستند این اطلاعات در بخشی به نام سالن رقص [۶۴]مبادله می شود تا با بهره گرفتن از آن یک منبع غذایی جدید را انتخاب کنند. به طور کلی الگوریتم کلونی زنبور در مراحل زیر خلاصه می شود
- ارسال پیشاهنگ به برای یافتن محل غذا
- فرستادن زنبورهای مستخدم بر منبع غذایی و اندازه گیری مقدار شهدشان
- اندازه گیری مقدار احتمال انتخاب یک منبع غذایی با توجه به ترجیحات زنبورهای ناظر
- توقف استفاده فرایند استفاده از منابع غذایی و ترک آنها توسط زنبورها
- ارسال زنبورهای پیشاهنگ برای جستجوی منطقه برای یافتن منابع غذایی بهتر به صورت تصادفی
- به خاطر سپردن محل بهترین منبع غذایی
تکرار مراحل ۲ تا ۶ تا هنگامی که نیازها برآورده شود.
کلاس تولید کننده موارد تست
تولید کننده موارد تست شامل یک بردار داده های ورودی و دو متد برای یکی برای تولید داده های اولیه و دیگری برای انجام جستجوی محلی است. ابتدا مولفههای بردار داده های ورودی و پس از آن متدهای تولید داده های اولیه و جستجوی محلی را شرح میدهیم.
هر بردار ورودی شامل مولفههایی است که در زیر مشاهده میکنید:
- لیست داده های ورودی
- لیستی از جهشهای از بین رفته به ازای هر مورد تست
- لیستی از مسیرهای پوشش داده شده در گراف کنترل جریان برنامه(CFG)[65]
- شایستگی [۶۶]
- احتمال انتخاب
لیست داده های ورودی را به صورت زیر نمایش داده و تعریف میکنیم:
هر نشان دهنده یک بردار داده و هر نشان دهنده یک دادهی ورودی است که در آن و قرار دارد در مورد i ذکر این نکته حائز اهمیت است که n برابر با تعداد زنبورها است از طرف دیگر تعداد زنبورها یا به عبارت دیگر تعداد دستههای گل باید حداقل ۲ باشد زیرا برای یافتن منبع غذایی با شایستگی بالاتر از میانگین شایستگی بردارها استفاده میکنیم در صورتیکه تست را با یک بردار و یک زنبور انجام دهیم به دلیل اینکه میانگین هر عدد خودش است الگوریتم به سمت بهینگی پیش نخواهد رفت.
برای آنکه بتوانیم از داده های تولید شده استفاده کنیم باید ابتدا واسط [۶۷] کد تحت [۶۸] تست را استخراج کنیم به عبارت دیگر تعداد و نوع متغییرهای ورودی آن را بدست آوریم که این کار با بهره گرفتن از خواندن از بایت کد جاوا به سادگی امکان پذیر است پس از استخراج تعداد متغییرهای عددی بردار ورودی ما به شکل زیر تغییر پیدا خواهد کرد:
هر یک مورد تست [۶۹] است به صورتی که که در آن n برابر تعداد موارد تستی است که کاربر در ابتدای اجرای تست مشخص می کند همچنین هر برابر:
که در آن هر نشان دهنده یک دادهی ورودی است که و n برابر با تعداد پارامترهای ورودی کد تحت تست است.
جهشهای از بین رفته
برای محاسبهی تعداد جهشهای از بین رفته نیاز به آگاهی از تعداد جهشهای موجود در هر یال از گراف داریم تا در صورت تغییر خروجی اجرای برنامه آنها را به عنوان جهشهای از بین رفته محاسبه کنیم.
پوشش کد
برای محاسبهی معیار پوشش به جای در نظر گرفتن مسیرهای گراف کنترل جریان، یالهای آن را در نظر میگیریم که با علامت گذاری مناسب (که در بخش دستیاران در مورد آن توضیح خواهیم داد) هر یال میتوانیم در هنگام اجرا از پوشش هر یال آگاه شویم در هر تکرار تست با ورودی ها، تعداد یالهای مجزایی و جدیدی که ملاقات شده اند را در لیست یالهای پوشش داده شده ثبت میکنیم در صورتیکه مورد تستی سبب پوشش یال جدیدی نشود برای آن مقدار صفر درج می شود.
شایستگی
پس از هر مرحله اجرا برای هر بردار ورودی یک عدد شایستگی محاسبه میکنیم برای محاسبهی شایستگی دو فاکتور امتیاز جهش و پوشش مسیر را در نظر میگیرم به طور کلی شایستگی از طریق معادله(۳-۱) قابل محاسبه است:
| معادله(۳۳۱‑): |
در رابطه بالا () تعداد یالهای جدید بازدید شده، تعداد جهشهای کشته شده برای هر یال که حاصل از اجرای هر درایهی بردار ورودی است که توسط F ، تابع محاسبه کننده شایستگی محاسبه شده و به عنوان شایستگی یک بردار ورودی ذخیره میگردد. ضرایب و اثر میزان پوشش مسیر و یا از بین بردن جهشها در محاسبهی شایستگی را تعیین می کنند. درحقیقت روش ما به گونه ای طراحی شده است که با توجه به تمایل کاربر ورودی مناسب جهت تست جهش یا پوشش کد را تولید می کند.
برای توصیف بیشتر حالات امکان پذیر، آنها را در جدول(۳-۲) نشان دادهایم، همانطور که مشاهده میکنید حالت ۱ بیشترین شایستگی را داشته و حالت ۴ کمترین شایستگی را دارد. منظور از ستون ” تعداد یالهای جدید ملاقات شده” تعداد یالهایی است که جدا از یالهایی جهشدار ملاقات شده اند.
جدول(۳‑۲): بررسی حالات مختلف برای محاسبهی شایستگی
| حالت | آیا جهش از بین رفته است؟ | تعداد جهشهای موجود در یالهای ملاقات شده | تعداد یالهای جدید ملاقات شده | شایستگی |
| ۱ | بله | + | ||
| ۲ | خیر | |||
| ۳ | بله | غیر ممکن | ||
| ۴ | خیر | |||
| ۵ | بله | |||
| ۶ | خیر | |||
| ۷ | بله | غیر ممکن | ||
| ۸ | خیر | ۰ |
برای محاسبهی امتیاز جهش ابتدا تعداد جهشهای موجود در هر یال را از بخش تولید کننده جهش بدست آوریم تا در صورتی که خروجی برنامه دچار تغییر شد این جهشها را به عنوان جهش از بین رفته در نظر بگیریم همچنین در پایان هر مرحله اجرا شایستگی کل را از طریق معادله(۳-۲) محاسبه میکنیم (این مرحله مشابه استقرار زنبورهای مستخدم بر منابع غذایی است).
| معادله(۳۲‑): |
محاسبهی احتمال انتخاب یک بردار ورودی
در این مرحله بردارهای ورودی که شایستگی آنها از میانگین شایستگیها بالاتر است برای انجام عمل جستجوی محلی و به عبارت دیگر برای حرکت زنبورهای ناظر[۷۰] انتخاب خواهند شد. احتمال انتخاب بردار ورودی ( یک زنبور مستخدم) از طریق معادله(۳-۳) قابل محاسبه است:
| معادله(۳‑۳): |
در این رابطه برابر احتمال انتخاب برای بردار ورودی و میزان شایستگی بردار ورودی است.
متد تولید داده های اولیه
برای تولید ورودیهای تست درگام نخست به طور تصادفی و به تعداد نخهایی از سیستم که در الگوریتم تست شرکت خواهند کرد (که مشابه زنبورهای پیش آهنگ[۷۱] در الگوریتم کلونی زنبور است) بردارهای داده به طور تصادفی تولید میکنیم (این بردارها مشابه دستههای گلی[۷۲] /منابع غذایی [۷۳] است که توسط زنبورهای پیشاهنگ در الگوریتم کلونی زنبور یافت شده اند) اگرچه به جهت تولید داده های ورودی بهتر اقداماتی دیگری نیز انجام دادهایم که در بخش دستیاران شرح خواهیم داد در مرحله بعد با بهره گرفتن از اطلاعات بدست آمده از واسط ورودی کد تحت تست موارد تست را ایجاد کرده سپس یک نمونه از فایل اصلی برنامه و یک نمونه از فایل جهش یافته آن را توسط نخ ها با تک تک موارد تست، تست میکنیم. با بهره گیری از تابع شایستگی مقدار شایستگی هر بردار محاسبه شده، (مشابه عملکرد زنبورهای مستخدم) و منتظر پایان اجرای تمامی نخها میشویم سپس شایستگی کل و احتمال انتخاب هر بردار ورودی محاسبه می شود. آن دسته از بردارهای ورودی که شایستگی بیشتر از میانگین دارند و به عبارت دیگر امید بیشتری دارند برای جستجوی محلی انتخاب شده (مشابه عملکرد زنبورهای ناظر) و مابقی ترک خواهند شد.
متد جستجوی محلی
پس از انتخاب بردارهای دادهی ورودی با احتمال بالاتر عملیات جستجوی محلی را برای آن انجام میدهیم برای پیدا کردن محلهای جدید (که توسط زنبورهای ناظر انجام می شود) از طریق معادله(۳-۴) محاسبه می شود.
| معادله (۳‑۴): |
که در آن درایهی i ام در تکرار j ام در بردار ورودی ، محل جدید (مقدار جدید) محاسبه شده برای دادهی ورودی i ام در تکرار j ام در همسایگی است و K برابر (تعداد پارامترهای ورودی برنامه) است. علاوه بر روابط بالا برای ایجاد تنوع بیشتر در داده های ورودی عملیاتی چون تعویض جای داده ها افزایش و یا کاهش داده ها انجام میپذیرد. همانطور که در یک کلونی ۱۰% از جمعیت زنبورها را زنبورهای پیشاهنگ تشکیل می دهند این سهم در روش ما نیز وجود دارد به گونه ای که در صورت ناامید شدن از یک منبع غذایی این دسته از زنبورها وارد عمل شده و به منبع غذایی دیگری به صورت تصادفی مهاجرت می کنند. در شکل(۳-۷) ماژول تولید کننده ورودی تست نشان داده شده است.
شکل (۳‑۶): ماژول تولید کننده ورودیهای تست
اجرا کننده تست
در ابتدا بردارهای ورودی را ایجاد کرده و درون یک آرایه ذخیره میکنیم سپس به تعداد ورودی کاربر نخ ایجاد میکنیم بعد نخها را برای اجرا فایل اصلی و فایل جهش یافته آماده میکنیم این آماده سازی با اضافه کردن موارد تست، تنظیم مقدار ورودی برای ارگومان انتخاب گر تابع عملگر جهش، اضافه آدرسهای فایل اصلی و جهش یافته صورت میگیرد در مرحله بعد تست را با هر نخ به صورت مجزا اجرا میکنیم پس از اجرا اطلاعاتی مانند پوشش یالها و جهشهای از میان رفته بدست می آید که در بخش مربوط در هر بردار قرار میگیرند در گام بعدی براساس احتمال انتخاب، بردارهای ورودی را انتخاب میکنیم و جستجوی محلی را انجام میدهیم تعداد زنبورهای شرکت کننده در هر بردار همسایگی (بردارهایی که از جستجوی محلی بدست میآیند) به صورت تصادفی مشخص میگردد این روال آنقدر تکرار می شود که یا تمام جهشها از میان برود یا شرط محدودیت تکرار ارضاء (که توسط کاربر مشخص می شود) شود. بعد از اجرای عملیات تست برای یک تابع، عملیات مشابه را برای تابع دیگر برنامه تکرار میکنیم تا در نهایت داده های ورودی مناسب را برای کل کلاس تحت تست به دست آوریم. هرچه تعداد نخها بیشتر باشد خروجیهای بهتر و بیشتر بدست خواهد آمد همچنین با توزیع محاسبات برروی پردازندههای بیشتر سریعتر میتوان به نتایج دلخواه دست یافت[۵۲]. در شبه کد زیر روند اجرای تست نشان داده شده است:
Function Runner(iteration_limit:Integer, Number of threads:integer, range:integer, Files:String, MaxFitness:float)
{
While(Not iteration_limit OR Not MaxFittness )
{
If (this is the first iteration)
{
Input_Vector[ ] IV=Create_input_vectors(range);
Threads[ ] T=Create_threads(Number of threads);
}
else
{
Search_for_new_results(IV);
}
Start_and _prepare_threads(IV,Files);
Start_Test_Foreach_Threads(T)
Wait_for_all_threads();
Input_Vector[ ] Best Vectors=Calculating_fitness();
}
دستیاران
در این بخش به جمع آوری برخی از اطلاعات ضروری برای انجام عملیات تست میپردازیم با استفاده خواندن از بایت کدهای جاوا کد تحت تست میتوان برخی از اطلاعات نظیر نام کلاس، تعداد و نوع پارامترهای ورودی هر تابع، تعداد و نام توابع موجود در کلاس تحت تست بدست آورد اما برای محاسبهی اطلاعاتی نظیر مسیرهای برنامه و یا Cyclomatic complexity برنامه نیاز به تلاش بیشتری داریم. برای این کار از روش ارائه شده توسط Ira. D. Baxter [54] استفاده میکنیم به نظر نویسنده شناسایی بلاکهای پایهای به دلیل تفاوت ساختارهای مختلف دستوری در زبانهای برنامه نویسی مختلف کار دشواری است. این موضوع در مورد بایت کدهای جاوا نیز صادق است زیرا در بایت کدهای جاوا متغییرها نام خود را از دست می دهند، از طرف دیگر شناسایی انشعابهای والد و فرزند در انشعابات تو در تو کار دشواری است برای حل این مشکل از روش علامت گذاری استفاده میکنیم برای آشکار شدن بیشتر موضوع به مثال زیر توجه کنید:
فرض کنید کد برنامهی تشخیص نوع مثلث را به صورت زیر در اختیار داشته باشیم:
| program TRIANGLE | Src |
| input (a) input (b) input © |
A |
