اجرای نمادین

برنامه زیر را درنظر بگیرید، این برنامه یک مقدار ورودی را می‌خواند و اگر ورودی ۶ باشد، مقدار «شکست» را برمی‌گرداند.

int f() {  ...  y = read();  z = y * 2;  if (z == 12) {    fail();  } else {    printf("OK");  }}

در مدت اجرای نرمال (یا اجرای واقعی)، برنامه یک مقدار ورودی واقعی (مثل 5) را می‌خواند و آن را به y انتساب می‌دهد. سپس اجرا با یک ضرب و شاخه شرطی ادامه می‌یابد، که به مقدار شکست ارزیابی شده و OK را چاپ می‌کند.

در مدت اجرای نمادین، برنامه یک مقدار نمادین (مثل λ) را می‌خواند و آن را به y انتساب می‌دهد. سپس برنامه با ضرب ادامه می‌یابد و مقدار λ * 2 را به z انتساب می‌دهد. موقعی که به بیانیه if می‌رسد، عبارت λ * 2 == 12 را ارزیابی می‌کند. در این نقطه از برنامه، λ هر مقداری را می‌تواند اخذ کند، و اجرای نمادین می‌تواند در امتداد هر دو شاخه ادامه پیدا کند، این کار با انشعاب‌دهی (fork کردن) به دو مسیر انجام می‌شود. در هر دستورالعمل شاخه‌گزینی به هر مسیر یک «کپی از وضعیت برنامه» و نیز یک «محدودیت مسیری» انتساب داده می‌شود. در این مثال، محدودیت مسیری برای شاخه then همان λ * 2 != 12 و برای شاخه else همان λ * 2 == 12 است. در اینجا هر دو مسیر به صورت مستقل قابل اجرای نمادین هستند. موقعی که مسیر خاتمه پیدا کند (مثلاً به عنوان نتیجه اجرای fail() یا با خارج‌شدن ساده)، اجرای نمادین یک مقدار غیرانتزاعی، برای λ محاسبه می‌کند، این کار با حل کردن محدودیت‌های مسیری انباشه‌شده در هر مسیر انجام می‌شود. این مقادیر غیرانتزاعی را می‌توان به عنوان آزمایه‌های غیرانتزاعی درنظر گرفت، که این مزیت را دارند که مثلاً می‌توانند به توسعه‌دهندگان در ایجاد مجدد اشکال‌های نرم‌افزاری کمک کنند. در این مثال، حل‌کننده محدودیت تعیین می‌کند که برای آنکه به بیانیه fail() برسیم، نیاز است که λ برابر 6 شود.

انفجار مسیری

اجرای نمادین همه مسیرهای ممکن برنامه، قابل مقیاس‌دهی به برنامه‌های بزرگ نیست. اگر سایز برنامه افزایش یابد، تعداد مسیرهای ممکن در یک برنامه به صورت نمایی افزایش می‌یابد، و حتی در حالت برنامه‌هایی که تکرارهای حلقه‌ای غیرمحدود دارند، تعداد مسیرها می‌تواند بینهایت باشد.^[۱] راه‌حل‌ها برای مسئله «انفجار مسیری» معمولاً یا از هیوریستیک‌هایی برای یافتن مسیر برای افزایش پوشاندن کد استفاده می‌کند،^[۲] که زمان اجرا را موازی‌سازی کرده، و مسیرهای مستقل کاهش را می‌دهد،^[۳] یا از ادغام مسیرهای مشابه استفاده می‌کنند.^[۴]

کارایی وابسته به برنامه

از اجرای نمادین برای استنتاج‌هایی در مورد یک برنامه به صورت «مسیر-به-مسیر» استفاده می‌شود، که این موضوع یک مزیت نسبت به استنتاج در مورد برنامه به صورت «ورودی-به-ورودی» (که دیگر الگوهای آزمون، مثل تحلیل پویای برنامه، از آن استفاده می‌کنند) است. با این حال، اگر تعداد کمی از ورودی‌ها در طول برنامه، یک مسیر مشابه را بگیرند، نسبت به حالت آزمون هر ورودی به صورت مجزا، بهبود زیادی حاصل نشده‌است.

دگرنامی به حافظه

اگر محل حافظه مشابه توسط نام‌های متفاوتی دستیابی شوند (که به این کار الیاس یا دگرنامی می‌گویند)، اجرای نمادین سخت‌تر شده‌است. همیشه نمی‌توان دگرنام‌ها را به صورت ایستا تشخیص داد، از این رو موتور اجرای نمادین نمی‌تواند تشخیص دهد که اگر مقدار یک متغیر را تغییر بدهیم، دیگری هم تغییر خواهد کرد.^[۵]

آرایه‌ها

به دلیل آنکه یک آرایه گردآوردی از تعداد زیادی از مقادیر متمایز است، اجرای نمادین می‌تواند به کل آرایه به عنوان یک مقدار برخورد کند یا اینکه با هر عنصر آرایه به صورت یک محل مجزا برخورد کند. اینجا مشکلی که در مورد برخورد با هر عنصر آرایه به صورت مجزا وجود دارد آن است که یک ارجاع مثل "A[i]" را موقعی که یک مقدار واقعی برای i به آن داده‌ایم، فقط به صورت پویا می‌توان تعیین نمود.^[۵]

تعامل‌های محیطی

برنامه‌ها با انجام تماس سامانه‌ای، گرفتن سیگنال، و غیره با محیط خود تعامل دارند. و مشکلات سازگاری می‌تواند موقعی بروز می‌کند که اجرا به مولفه‌هایی برسد که تحت کنترل ابزار اجرای نمادین نیست (مثل هسته یا کتابخانه). مثال زیر را درنظر بگیرید:

int main(){  FILE *fp = fopen("doc.txt");  ...  if (condition) {    fputs("some data", fp);  } else {    fputs("some other data", fp);  }  ...  data = fgets(..., fp);}

این برنامه یک فایل را باز می‌کند، سپس بر اساس یک شرط، مقادیر متفاوتی از داده را به فایل می‌نویسد. سپس داده نوشته‌شده را بازخوانی می‌کند. از لحاظ نظری، اجرای نمادین دو مسیر را در خط ۵ انشعاب داده است، و هر مسیر از آنجا کپی فایل خاص خود را خواهد داشت. بیانیه موجود در خط ۱۱، مقدار داده‌ای را بازمی‌گرداند که با مقدار «شرط» موجود در خط ۵ سازگار است. در عمل، عملیات فایل به صورت تماس سامانه‌ای در هسته پیاده‌سازی می‌شود، و از کنترل ابزار اجرای نمادین خارج است. دیدگاه‌های اصلی برای رسیدگی به این چالش‌ها از این قرار هستند:

به صورت مستقیم تماس با محیط را اجراکنیم. مزیت این دیدگاه آن است که پیاده‌سازی‌اش ساده است. اما ایرادش آن است که اثرجانبی این تماس‌ها به همه حالت‌های مدیریت شده توسط موتور اجرای نمادین ضربه وارد می‌کند. در مثال بالا، بر اساس ترتیب دنباله‌ای حالت‌ها، دستورالعمل خط ۱۱، مقدار "some datasome other data" یا "some other datasomedata" را برخواهد گرداند.

مدل‌سازی محیط. در این حالت، موتور، تماس سامانه‌ای را با یک «مدل» ابزارسازی می‌کند که این مدل تاثیراتش را شبیه‌سازی کرده، و همه اثرات جانبی‌اش را در ذخیره هر-وضعیتی نگهداری می‌کند. مزیت این کار آن است که موقعی به نتایج درست می‌رسیم که برنامه‌هایی که با محیط تعامل دارند را به صورت نمادین اجرا کنیم. ایرادش آن است که باید مدل‌های بالقوه پیچیده زیادی را برای تماس سامانه‌ای پیاده‌سازی و نگهداری کنیم. ابزارهایی مثل مثل KLEE, Cloud9^[۶] و Otter,^[۷] از این دیدگاه استفاده کرده‌اند، یعنی آن‌ها مدل‌هایی را برای عملیات سیستم فایل، سوکت‌ها و IPC و غیره پیاده‌سازی کرده‌اند.

انشعاب کل حالت سامانه. ابزارهای اجرای نمادین براساس ماشین مجازی، مسئله محیط را با انشعاب کل حالت VM حل می‌کند. برای مثال، در S2E^[۸] هر حالت یک برگرفت مستقل VM است، که قابلیت اجرای جداگانه دارد. این دیدگاه نیاز برای نوشتن و نگهداری مدل‌های پیچیده را کاهش می‌دهد، و همچنین امکان اجرای نمادین مجازی هر برنامه‌ای را می‌دهد. اما این روش، سربار استفاده از حافظه بالاتری دارد (برگرفت‌های VM می‌تواند بزرگ باشند).

EXE^[۱۰] یک نسخه اولیه برای KLEE است. مقاله EXE را می‌توان در اینجا یافت.

مفهوم اجرای نمادین به صورت دانشگاهی با توصیف این موارد معرفی شد: سامانه Select،^[۱۱] سامانه EFFIGY،^[۱۲] سامانه DISSECT،^[۱۳] و سامانه Clarke's.^[۱۴] کتابشناسی را برای مقاله‌های فنی‌تر منتشر شده دربارهٔ اجرای نمادین ببینید.

مشارکت‌کنندگان ویکی‌پدیا. «Symbolic execution». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۱ مهٔ ۲۰۲۱.