ردیف

مسیر

محدودیت مسیر

۱

۸،۱

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 استفاده می­ کند. با بکارگیری این روش هر مورچه در هنگام عبور از مسیر فرمون دار به تشخیص خود می ­تواند مقداری از مسیر اصلی فاصله بگیرد تا بتوان دامنه­ پیوسته­ای از ورودی­ ها به وجود آورد.
شکل(‏۳‑۴): کلونی مورچه و تست جهش
شرح ابزار ارائه شده
ابزار ارائه شده براساس برنامه­هایی که با زبان جاوا نوشته شده ­اند کار می­ کند ما در روش خود برای تحقق سه اصل مطرح شده انجام کمتر، انجام هوشمندانه و انجام سریع­تر به ترتیب از تکنیک­های تولید کمتر جهش، استفاده از یک روش فرابتکاری برای تولید داده ­های تست همراه با برخی ماژول­های کمکی اجرا به تست به صورت موازی و ابزارهای ترجمه بایت کد در جاوا استفاده کردیم. ابزار ارائه شده از چهار بخش اصلی تشکیل شده است که به شرح زیر است:

• تولید کننده­ جهش­ها

• تولید کننده­ ورودی­های تست

• اجرا کننده­ تست

• دستیاران