سؤال مصاحبه

همان 46 بایت، همان بازآدرس‌دهی، اما جدول اشتباه

Same 46 bytes, same relocation, wrong table

  • سطح ۳: ارشد
  • طراحی
  • ۱۰ دقیقه

گام دوم اثبات بازسازی (rebuild proof) را طراحی کنید: هر کاندیدا را با همان کامپایلر و فلگ‌هایی که فایل اصلی را تولید کرده‌اند بیلد کنید، سپس آن را با تابع اصلی بسنجید. هشت کاندیدا پیش رو داریم؛ از جمله دو بازسازی برای percent_change که خطوط کد مبدأ متفاوتی دارند، یک کاندیدای grade که 46 بایت کد و ساختار بازآدرس‌دهی (relocation) آن دقیقاً با نسخه‌ی اصلی همخوانی دارد اما case 10 آن عدد 3 را برمی‌گرداند، و کاندیداهایی که مقدار افزوده (addend) بازآدرس‌دهی آن‌ها با نسخه‌ی اصلی فرق می‌کند. مشخص کنید که مقایسه در هر مرحله چه کاری انجام می‌دهد، جلوی کدام کاندیدا را می‌گیرد و قبولی در آزمون دقیقاً به چه معناست.

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

پاسخ کوتاه

سه مرحله به‌ترتیب: صفر کردن بایت‌های تمام فیلدهای بازآدرس‌دهی در هر دو طرف (ماسک کردن) و مقایسه‌ی کدها؛ مقایسه‌ی رکوردهای بازآرایی (relocation records) بر اساس آفست، نوع و بخش مقصد، بدون در نظر گرفتن مقدار افزوده (زیرا نسخه‌ی اصلی به rodata+0x10. و همه‌ی کاندیداها به rodata-0x4. اشاره دارند و این فقط نشان‌دهنده‌ی موقعیت متفاوت جدول است، نه تفاوت در خود تابع)؛ و در نهایت خواندن بایت‌هایی که هر بازآدرس‌دهی به آن اشاره می‌کند (در اینجا پنج کلمه‌ی 4 بایتی) و مقایسه‌ی آن‌ها با یکدیگر. کاندیدایی که مقدار ثابتِ اشتباه دارد از دو مرحله‌ی اول می‌گذرد و فقط در مرحله‌ی سوم رد می‌شود: مقایسه‌ی 1, 2, 3, 4, 4 در برابر 1, 2, 3, 4, 3. قبولی در این بررسی اثبات می‌کند که این کامپایلر با این فلگ‌ها، کد و داده‌های مرجع یکسانی از آن کاندیدا تولید کرده است؛ اما اثبات نمی‌کند که کاندیدا همان متن اصلی کد مبدأ است، چرا که دو بازسازی percent_change با وجود متن‌های متفاوت، به 16 بایت کاملاً یکسان کامپایل می‌شوند.

پاسخ کامل

هر کاندیدا در کدام مرحله متوقف می‌شود

کاندیدا اندازه بایت‌های ماسک‌شده رکوردها جدول وضعیت
percent_change_mul_first 16 و 16 برابر ندارد ندارد قبولی
percent_change_split 16 و 16 برابر ندارد ندارد قبولی
percent_change_wide 16 و 26 اندازه‌ی متفاوت ندارد ندارد رد
percent_change_div_first 16 و 18 اندازه‌ی متفاوت ندارد ندارد رد
grade_switch 46 و 46 برابر ساختار یکسان برابر قبولی
grade_table 46 و 46 برابر ساختار یکسان برابر قبولی
grade_thresholds 46 و 39 اندازه‌ی متفاوت 1 در برابر 0 ندارد رد
grade_case10_wrong 46 و 46 برابر ساختار یکسان متفاوت رد

اندازه صرفاً معیاری تشخیصی است و هرگز مبنای پذیرش نیست: در یکی از پروژه‌های ثبت‌شده‌ی بازسازی، کاندیدایی گزارش شده که با وجود طول کاملاً یکسان، در صدها بایت با فایل اصلی اختلاف داشته است.

چرا وقتی فیلد از قبل صفر است باز هم ماسک می‌کنیم؟

در یک آبجکت‌فایل RELA، مقدار افزوده داخل خود رکورد نگهداری می‌شود و چهار بایت فیلد در هر دو طرف صفر است؛ بنابراین یک مقایسه‌ی ساده قبول می‌شود، در حالی که دو بازآدرس‌دهی به مکان‌های متفاوتی اشاره دارند. با این حال ماسک کردن باعث می‌شود روش یکسانی برای آبجکت‌فایل‌های REL و Mach-O (که مقدار افزوده را درون خود فیلد حمل می‌کنند) حفظ شود. اختلاف مقادیر افزوده به این دلیل است که آبجکت‌فایل اصلی یک جدول دیگر هم پیش از جدول switch در rodata. دارد، اما آبجکت‌فایل کاندیدا فاقد آن است.

چرا باید مقادیر ثابت را بخوانیم؟

این مرحله به‌خاطر یک باگ مستند در پروژه‌ی بازسازی دیگری وجود دارد: در آن پروژه، فرآیند مقایسه آدرس مقصد را درون فیلد بازآدرس‌دهی بازپخش (replay) می‌کرد و بایت‌های دستورالعمل را می‌سنجید، اما هرگز داده‌های موجود در آن آدرس را بررسی نمی‌کرد؛ در نتیجه لیترالِ 0.0 در کد مبدأ در برابر لیترالِ 128.0 مقصد کاملاً یکسان به نظر می‌رسید، تا اینکه 1,548 مرجع ممیز شناور بازبینی شدند. کاندیدای دارای مقدار ثابتِ اشتباه در این مجموعه‌داده‌ی نمونه (fixture)، دقیقاً روایتی از همان نقص است و خواندن جدول همان ممیزی به حساب می‌آید. تعداد پنج‌تایی از متن لیستینگ به دست می‌آید: مقایسه با عدد 4 همراه با پرش بدون علامت، فقط اندیس‌های 0 تا 4 را می‌پذیرد و دستور لود، به ازای هر اندیس 4 بایت می‌خواند.

مقایسه‌ی خود ابزار چه چیزهایی را می‌بیند؟

ابزار مقایسه، تفاوت‌های بازنگری (diff) خط‌به‌خط متن تولیدی (provider text) را در هشت بُعد بررسی می‌کند و بُعدِ اسمبلی آن دو محدودیت ثابت دارد: متن دقیق خروجی بدون نرمال‌سازی آدرس‌ها یا نام‌های تولیدشده مقایسه می‌شود، و اسمبلی متنی مبهم (opaque) است که امکان نرمال‌سازی بازآدرس‌دهی روی آن وجود ندارد. برچسب unchanged در بُعد اسمبلی یعنی متن یکسان از یک موتور خروجی، و changed یعنی متن متفاوت؛ هیچ‌کدام بیانی درباره‌ی وضعیت بایت‌ها نیستند. دو نسخه از یک کدِ یکسان در آدرس‌های مختلف، خروجی changed تولید می‌کنند. اثبات در سطح بایت بخشی است که ابزار بر عهده‌ی خود شما می‌گذارد.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 3: چرا هنگام تطبیق دو رکورد بازآرایی، مقدار افزوده نادیده گرفته می‌شود؟ انتظار می‌رود پاسخ دهید: مقدار افزوده محل قرارگیری جدول در rodata. آن آبجکت‌فایل را مشخص می‌کند؛ این مقدار به محتوای دیگر موجود در آن آبجکت‌فایل بستگی دارد، نه به عملکرد خود تابع.
  • سطح 3: برچسب changed در بُعد اسمبلی ابزار مقایسه، چه چیزی درباره‌ی بایت‌های دو تابع به ما می‌گوید؟ انتظار می‌رود پاسخ دهید: هیچ‌چیز؛ این صرفاً یک diff متنی حاوی آدرس‌هاست، و مقایسه‌ی یک آبجکت‌فایل بازآدرس‌پذیر با ایمیج لینک‌شده‌ی آن همیشه نتیجه‌ی changed می‌دهد.
  • سطح 4: دو کاندیدا با متن کد مبدأ کاملاً متفاوت، در تمام بررسی‌های بایتی قبول می‌شوند. چه چیزی را اثبات کرده‌اید؟ انتظار می‌رود پاسخ دهید: اینکه این کامپایلر هر دو را به کد و داده‌های یکسانی تبدیل کرده است، نه اینکه کدام‌یک کد مبدأ اصلی بوده‌اند؛ تعریف‌نشده بودن سرریز علامت‌دار (signed overflow) به کامپایلر اجازه می‌دهد دو عمل ضرب را با هم merge کند.
  • سطح 4: یک کاندیدا در تطابق بایت‌ها و مقادیر ثابت قبول می‌شود. آیا رفتار تابع قطعی شده است؟ انتظار می‌رود پاسخ دهید: روی همان معماری بله، زیرا کد و داده‌های مرجع برابرند؛ با این حال وضعیت سلول trap همچنان به میزبانی بستگی دارد که شبکه (grid) را اجرا می‌کند، بنابراین متن اثبات صریحاً نام آن را قید می‌کند.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «اندازه‌ی برابر یعنی تابع برابر.» اندازه صرفاً معیاری تشخیصی است؛ کاندیدایی با طول کاملاً درست می‌تواند در صدها بایت با اصل تفاوت داشته باشد.
  • «تطابق بایتی یعنی بازیابی کد مبدأ.» متن‌های مبدأ متفاوت می‌توانند به بایت‌های کاملاً یکسانی کامپایل شوند؛ تطابق بایت‌ها فقط بیانی درباره‌ی یک کامپایلر و یک مجموعه فلگ مشخص است.
  • «چون ابزار مقایسه وضعیت را unchanged اعلام کرد، پس بایت‌ها مطابقت دارند.» این ابزار متن دکامپایلر را همراه با آدرس‌های درون آن مقایسه کرده و در محدودیت‌های خودش هم صراحتاً به این نکته اشاره کرده است.

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

درس بازسازی پیاده‌سازی ماسک کردن، مقایسه‌ی رکوردها و خواندن جدول را آموزش می‌دهد؛ بخش بستر آزمایشی اثبات وضعیت هشت کاندیدا را ثبت کرده است؛ و بخش مقایسه به محدودیت مقایسه‌ی اسمبلی اشاره دارد.