سؤال مصاحبه

چند خانه برابری دو تابع کوچک را اثبات می‌کند؟

How many cells prove two small functions equal

  • سطح ۳: ارشد
  • تخمین
  • ۱۰ دقیقه

شبکه‌ی ورودی‌ای طراحی کنید که نسخه‌ی اصلی و بازسازی‌شده‌ی دو تابع percent_change(int before, int after) و grade(int score) را در کنار هم اجرا کند، طوری که برای هر مخاطره‌ای (hazard) که در متن اسمبلی (listing) دیده می‌شود دست‌کم یک خانه وجود داشته باشد. تخمین بزنید به چند خانه و در چه دسته‌هایی نیاز دارید، و بازسازی‌ای که نوع long ناشی از دیکامپایلر را حفظ کرده در چند خانه مردود می‌شود.

اول خودتان جواب بدهید، بعد پاسخ را باز کنید.

پاسخ کوتاه

مخاطرات را مستقیماً از روی کد اسمبلی بخوانید: یک بررسی مقدار صفر ناشی از TEST EDI, EDI، کوتاه‌سازی (truncation) به سمت صفر برای عملوندهای منفی، تقدم ضرب بر تقسیم برای گرد کردن، سرریز چرخشی 32 بیتی حاصل از IMUL EAX، تله‌ی تقسیم (divide trap) در حالتی که حاصل‌ضرب چرخیده برابر با INT_MIN و مقسوم‌علیه برابر با 1- باشد، و برای تابع grade، هر دو سمتِ مرز هر بازه به همراه نمراتی فراتر از دامنه‌ی دستور switch. حاصل‌ضرب 10 مقدار before در 7 مقدار after برابر با 70 خانه می‌شود؛ 22 نمره هم مابقی را پر می‌کنند که در مجموع می‌شود 92 خانه: 32 سرریز، 17 منفی، 14 مرزی، 12 معمولی، 7 بررسی صفر، 5 کوتاه‌سازی منفی، 2 خارج از بازه‌ی switch، 2 گرد کردن و 1 تله‌ی تقسیم. نسخه‌ی بازسازی‌شده با long در خانه‌های سرریز با شرط |before| > 1 مردود می‌شود (26 خانه)، و بازسازیِ مبتنی بر آستانه‌ی تابع grade هم در دو خانه‌ی فراتر از switch شکست می‌خورد؛ بنابراین این جفت پیاده‌سازی به‌ظاهر موجه در 28 خانه از 92 خانه رد می‌شوند، در حالی که هر 10 تست ساده‌لوحانه و دستی را با موفقیت پاس می‌کنند.

پاسخ کامل

هر دسته برای یک مخاطره

تست تفاضلی (Differential testing) نیازمند دو سیستم مقایسه‌پذیر است که ورودی‌های مکانیکی تولیدشده به آن‌ها داده شود، و بخش دشوار کار ارزیابی نتیجه است. در این‌جا کد اصلی همان اوراکل (oracle) است؛ بنابراین تنها پرسش این است که این دو نسخه در چه جاهایی ممکن است با هم اختلاف داشته باشند، و هر دسته به یکی از این پرسش‌ها پاسخ می‌دهد. خانه‌های بررسی صفر وارد مسیر خروج زودهنگام می‌شوند. خانه‌های منفی بررسی می‌کنند که مقدار -9 / 10 برابر با 0 و مقدار -10 / 10 برابر با 1- شود. خانه‌های گرد کردن وارسی می‌کنند که نتیجه‌ی (105 - 100) * 100 / 100 برابر با 5 شود نه 0. خانه‌های سرریز کاری می‌کنند که مقدار (after - before) * 100 از 32 بیت فراتر برود. تک‌خانه‌ی تله نیز حاصل‌ضرب چرخیده را با قرار دادن مقدار before برابر با 1- به INT_MIN می‌رساند: اختلاف برابر با 536870912 است که سرریز چرخشی آن 2147483648- می‌شود و مقسوم‌علیه نیز 1- است.

چرا سرریز در دامنه قرار دارد؟

سرریز علامت‌دار در زبان C رفتار تعریف‌نشده (undefined behavior) دارد، و اگر ابزار تولید برنامه‌ای از رفتار تعریف‌نشده دوری می‌کند به این دلیل است که اختلاف با اوراکل در چنین مواردی نویز به حساب می‌آید. اما این اوراکل یک شیء کامپایل‌شده (compiled object) با یک رفتار ثابت و معین است، پس خانه‌های سرریز در دامنه (scope) قرار دارند؛ درس مهم این است که بدانید کدام خانه‌ها متکی به استاندارد زبان هستند و کدام متکی به بایت‌های کامپایل‌شده. اسمبلی تکلیف را مشخص می‌کند: ضرب فقط 32 بیت پایینی را نگه می‌دارد، و نسخه‌ی بازسازی‌شده هم باید دقیقاً همین کار را بکند.

سیستم میزبان جزئی از نتیجه است

در معماری x86-64 خانه‌ی تله باعث ایجاد استثنای خطای تقسیم می‌شود، چون خارج‌قسمت در 32 بیت جا نمی‌گیرد؛ و درایور، سیگنال SIGFPE را به مقدار trap تبدیل می‌کند. در معماری AArch64 دستور sdiv اصلاً تله ندارد و مقدار 2147483648- را برمی‌گرداند. اجرای ثبت‌شده روی سیستم میزبان arm64 همین مقدار را همراه با match: true نشان می‌دهد، در حالی که اجرای همین شبکه روی x86-64 رشته‌ی trap را ثبت می‌کند. گزارش نهایی نام معماری را کنار هر سطر می‌آورد، و اثبات بدون ذکر نام میزبان ناقص است.

تفکیک مدل از اجرا

یک مدل پایتونی بر اساس کد اسمبلی، با در نظر گرفتن سرریز چرخشی 32 بیتی و تقسیم مشابه C، مقدار هر خانه را پیش‌بینی می‌کند؛ و اجرای آزمون آن را می‌سنجد. صفر بودن موارد اختلاف یعنی مدل و فایل باینری در تمام خانه‌ها با یکدیگر توافق دارند. مدل، شواهد استخراج‌شده (derived evidence) است و اجرا، شواهد مشاهده‌شده (observed evidence)؛ گزارش هم به جای این‌که یکی را به نفع دیگری ساده یا گرد کند، آن‌ها را در فیلدهای جداگانه نگه می‌دارد.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 3: چرا باید خانه‌هایی را وارد کنیم که رفتارشان در زبان C تعریف‌نشده است؟ پاسخ مورد انتظار: اوراکل یک شیء کامپایل‌شده با رفتاری مشخص است و کد اسمبلی پهنای بیت را نشان می‌دهد، بنابراین بازسازی باید منطبق بر بایت‌ها باشد نه استاندارد زبان.
  • سطح 3: از بین 32 خانه‌ی سرریز، نسخه‌ی بازسازی‌شده با long چند خانه را پاس می‌کند و چرا؟ پاسخ مورد انتظار: 6 خانه، همان‌هایی که مقدار before در آن‌ها 1 یا 1- است؛ چون خارج‌قسمت 64 بیتی بر حسب تصادف پس از کوتاه‌سازی به همان مقدار چرخیده برمی‌گردد.
  • سطح 4: شبکه‌ی آزمون روی سیستم میزبان arm64 پاس می‌شود. چه چیزی برای x86-64 اثبات‌نشده باقی می‌ماند؟ پاسخ مورد انتظار: خانه‌ی تله که نتیجه‌ی نسخه‌ی اصلی در آن بسته به معماری متفاوت است؛ باید روی x86-64 دوباره اجرا شود یا نام میزبان در کنار آن بیاید.
  • سطح 4: شبکه را برای تابع total(const int *values, int count) تعمیم دهید. چه دسته‌هایی پدیدار می‌شوند؟ پاسخ مورد انتظار: تعداد صفر، تعداد منفی، یک عنصر، و مجموع‌هایی که در 32 بیت سرریز چرخشی دارند؛ هر کدام همراه با دستور اسمبلی متناظری که دلیل وجود آن دسته است.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «10 تست دست‌نویس کل سناریوها را پوشش می‌دهد.» این تست‌ها روی هر دو بازسازیِ اشتباه پاس شدند؛ هیچ‌کدام وارد دامنه‌ی سرریز پهنای بیت یا مرز switch نشدند.
  • «به جای شبکه از فازینگ (Fuzzing) استفاده کنید.» ورودی‌های تصادفی مغایرت‌ها را پیدا می‌کنند اما نوع مخاطره را نام نمی‌برند؛ در نظر گرفتن یک دسته به ازای هر دستور مشخص می‌کند که شکست چه معنایی دارد و قبولی چه مواردی را پوشش داده است.
  • «خانه‌ی تقسیم بر منفی یک را نادیده بگیرید؛ هیچ‌کس چنین مقداری نمی‌دهد.» این تنها خانه‌ای است که نتیجه‌اش به معماری بستگی دارد و گزارش حتماً باید نام سیستم میزبان را ذکر کند.

کجای دوره آموزش داده می‌شود

درس بازسازی شبکه و درایور آزمون را می‌سازد، و بخش بستر آزمایشی اثبات 92 خانه، 28 عدم‌تطابق و سطر تله را روی یک میزبان arm64 ثبت می‌کند.