۹۹٫۳%ج

یک

_

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