سناریوی رخداد

بازنویسی تابعی که موجه به نظر می‌رسید، اما معادل نبود

A rebuilt function that was plausible, not equal

  • سطح ۴: استف
  • سناریوی رخداد
  • ۳۰ دقیقه

وضعیت

از یک ایجنت خواسته می‌شود دو تابع percent_change و grade را از روی شبه‌کد Ghidra در مجموعه‌داده‌ی نمونه‌ی (fixture) ledger بازنویسی کند تا تیم بتواند فایل شیء (object file) اصلی را کنار بگذارد. ایجنت تابع percent_change را با نوع long (که دیکامپایلر پیشنهاد داده بود) و تابع grade را در قالب چهار مقایسه‌ی آستانه‌ای می‌نویسد. سپس 10 تست دست‌نویسِ بستر آزمایشی (harness) درس را اجرا می‌کند و هر 10 تست پاس می‌شوند. در ادامه، verify_reconstruction را روی دو رکورد compare_functions (مربوط به بیلد‌های -O1 و -O2) اجرا می‌کند؛ با قبولیِ دو ادعا و رد شدن دو تای دیگر، گزارش می‌دهد: «برابری percent_change تأیید شد؛ total بین دو بیلد تغییر کرده، پس کامپایلر آن را خراب کرده است.»

سرپرست تیم پس از خواندن گزارش، دو پرسش مطرح می‌کند: تأیید یک ادعا در این ابزار چه چیزی را درباره‌ی تابع اثبات می‌کند و رد شدن آن چه معنایی دارد؟ همچنین کدام تست تعیین می‌کند که توابع بازنویسی‌شده واقعاً با نسخه‌های اصلی معادل‌اند یا نه؟ شما رکورد اعتبارسنجی، یادداشت‌های بستر آزمایشی و خروجی‌های بستر آزمایشی را برای دو جفت کاندید در اختیار دارید.

نسخه
rea 6.7.0 at 27dc42d with the Ghidra provider
مدل
no model; the fixtures are the ledger binaries built at -O1 and -O2
سخت‌افزار
one aarch64 Mac

شواهد

equal-pair.txt
title: the equal pair over the grid
source: manuals/reverse-engineering-101/capture/out/17-harness-execute-equal.json
lines: 1-13
lang: json
note: No mismatch and no oracle disagreement on the same 92 cells.
---
{
  "candidates": {
    "percent_change": "phases/13-tools-and-protocols/36-rebuild-and-prove-equal/code/fixtures/candidates/percent_change_mul_first.c",
    "grade": "phases/13-tools-and-protocols/36-rebuild-and-prove-equal/code/fixtures/candidates/grade_switch.c"
  },
  "original": "fixtures/ledger.c compiled with the host clang at -O1",
  "original_kind": "fixture-source",
  "host": "aarch64 Darwin",
  "arch": "aarch64",
  "naive_passed": true,
  "cells": 92,
  "mismatches": [],
  "oracle_disagreements": [],
plausible-grade-misses.txt
title: the two grade cells that the threshold rebuild got wrong
source: manuals/reverse-engineering-101/capture/out/17-harness-execute-plausible.json
lines: 299-318
lang: json
note: Both cells sit beyond the last case of the switch.
---
    {
      "function": "grade",
      "args": [
        110
      ],
      "kind": "beyond the switch",
      "original": 0,
      "candidate": 4,
      "match": false
    },
    {
      "function": "grade",
      "args": [
        2147483647
      ],
      "kind": "beyond the switch",
      "original": 0,
      "candidate": 4,
      "match": false
    }
plausible-pair.txt
title: the plausible pair over the grid, head and first mismatch
source: manuals/reverse-engineering-101/capture/out/17-harness-execute-plausible.json
lines: 1-22
lang: json
note: The ten naive cases passed. The first mismatch is an overflow cell.
---
{
  "candidates": {
    "percent_change": "phases/13-tools-and-protocols/36-rebuild-and-prove-equal/code/fixtures/candidates/percent_change_wide.c",
    "grade": "phases/13-tools-and-protocols/36-rebuild-and-prove-equal/code/fixtures/candidates/grade_thresholds.c"
  },
  "original": "fixtures/ledger.c compiled with the host clang at -O1",
  "original_kind": "fixture-source",
  "host": "aarch64 Darwin",
  "arch": "aarch64",
  "naive_passed": true,
  "cells": 92,
  "mismatches": [
    {
      "function": "percent_change",
      "args": [
        3,
        2147483647
      ],
      "kind": "overflow",
      "original": -133,
      "candidate": -1431655899,
      "match": false
the-harness.txt
title: what the harness is and what it ran
source: manuals/reverse-engineering-101/capture/out/17-harness.txt
lang: text
note: Two legs: run both over a grid, then compare bytes after relocation masking.
---
harness: phases/13-tools-and-protocols/36-rebuild-and-prove-equal/code/main.py loaded from phases/13-tools-and-protocols/36-rebuild-and-prove-equal/code
original object: fixtures/ledger-x86_64-O1.o (9a4a8082ba5e285a732552981a6935e0c5255725664f380e37c44ebfb04d803f)
host: aarch64 Darwin, compiler /usr/bin/clang
leg one: fixtures/ledger.c and each candidate compiled natively at -O1 into one program with phases/13-tools-and-protocols/36-rebuild-and-prove-equal/code/driver.c, then run over 92 cells
leg two: each candidate compiled with `clang -target x86_64-unknown-linux-gnu -O1 -fno-asynchronous-unwind-tables -c`, then compared with the original after relocation masking
files: 17-harness-grid.json, 17-harness-execute-plausible.json, 17-harness-execute-equal.json, 17-harness-bytes.json
total-assembly-claim.txt
title: the total-assembly claim
source: manuals/reverse-engineering-101/capture/out/10-mcp-22-verify-reconstruction.json
lines: 195-199
lang: json
note: The observed status is the status of one dimension of one comparison record.
---
                "claim_id": "total-assembly",
                "kind": "structural-function",
                "dimension": "assembly",
                "status": "fail",
                "observed_status": "changed",
verify-status-and-first-claim.txt
title: the verification status, the summary, and the first claim
source: manuals/reverse-engineering-101/capture/out/10-mcp-22-verify-reconstruction.json
lines: 81-98
lang: json
note: Two passed and two failed. The first claim reads unchanged on its one dimension.
---
          "status": "fail",
          "specification_sha256": "9e8d22fa6db331994f2e80be5b728575a0e9cb17ff1e63d24ece22d235084bfe",
          "summary": {
            "total": 4,
            "passed": 2,
            "failed": 2,
            "unknown": 0,
            "behavioral": 0,
            "structural": 4
          },
          "claims": {
            "items": [
              {
                "claim_id": "percent-change-assembly",
                "kind": "structural-function",
                "dimension": "assembly",
                "status": "pass",
                "observed_status": "unchanged",
wrong-constant-passes-bytes.txt
title: a rebuild with one wrong table entry in leg two
source: manuals/reverse-engineering-101/capture/out/17-harness-bytes.json
lines: 261-300
lang: json
note: Masked bytes equal, relocations match, and the status is still fail. Read the two tables.
---
      "candidate": "grade_case10_wrong",
      "source": "phases/13-tools-and-protocols/36-rebuild-and-prove-equal/code/fixtures/candidates/grade_case10_wrong.c",
      "original_size": 46,
      "candidate_size": 46,
      "masked_equal": true,
      "differing_offsets": [],
      "masked_ranges": [
        [
          38,
          4
        ]
      ],
      "relocations_match": true,
      "relocations": [
        {
          "offset": 38,
          "type": "R_X86_64_PC32",
          "original_target": ".rodata+0x10",
          "candidate_target": ".rodata-0x4",
          "same_shape": true
        }
      ],
      "original_table": [
        1,
        2,
        3,
        4,
        4
      ],
      "candidate_table": [
        1,
        2,
        3,
        4,
        3
      ],
      "status": "fail",
      "reasons": [
        "referenced constants differ: [1, 2, 3, 4, 4] vs [1, 2, 3, 4, 3]"
      ]

سؤال‌ها

  1. ادعایی با وضعیت observed_status: "unchanged" پاس شده است. چه چیزی با چه چیزی مقایسه شده و واژه‌ی unchanged اینجا چه معنایی دارد؟
  2. با وجود این‌که هر دو بیلد تابع total از یک خط کد منبع یکسان تولید شده‌اند، ادعاهای مربوط به آن رد شده‌اند. آیا رد شدن یک ادعا نشان می‌دهد که رفتار تابع تغییر کرده است؟
  3. هر 10 تست ساده‌لوحانه برای جفت پیشنهادیِ ایجنت پاس شدند. این جفت در چند تا از 92 خانه‌ی شبکه‌ی ورودی‌ها اشتباه کرد و این خطاها به کدام دسته‌های ریسک (hazard classes) تعلق دارند؟
  4. کدام جفت در تمام خانه‌های شبکه خروجی یکسان می‌دهد و این جفت چه آزمون‌های دیگری را باید پاس کند تا بتوان آن را معادل نامید؟
  5. کاندیدی با یک درایه‌ی اشتباه در جدول، بایت‌های ماسک‌شده‌ی یکسان و رکوردهای بازآرایی (relocation records) منطبق دارد. چه آزمونی مچ این خطا را می‌گیرد؟
  6. قانون پذیرشِ یک تابع بازنویسی‌شده را به ترتیب مراحل بنویسید.

اول شواهد را بخوانید و به سؤال‌ها جواب بدهید، بعد راه‌حل را باز کنید.

راه‌حل گام‌به‌گام
  1. بررسی کنید مدل اعتبارسنج (verifier) دقیقاً چه چیزی را مقایسه می‌کند. رکورد اعتبارسنجی دارای وضعیت status: "fail" همراه با دو ادعای ساختاریِ پاس‌شده و دو ادعای ردشده است. اولین ادعا، یعنی percent-change-assembly، وضعیت pass با مقدار unchanged دارد. یک ادعای ساختاری وضعیت خود را از یک بُعدِ مشخص در یک رکورد compare_functions می‌گیرد؛ آن بُعد چیزی نیست جز تفاوت‌های بازنگریِ (diff) خط‌به‌خط متنی که Ghidra چاپ کرده است. بنابراین، پاس شدن ادعا صرفاً به این معناست که دو متن اسمبلی خط‌به‌خط هم‌خوانی داشته‌اند و نه چیزی بیشتر. حتی در محدودیت‌های ذکرشده در خودِ این رکورد آمده که پاس شدن، هیچ اثباتی بر هم‌ارزی کل پیاده‌سازی ارائه نمی‌دهد.
  2. ادعای ردشده را بررسی کنید. ادعای total-assembly وضعیت fail و مقدار changed دارد. متن خروجی Ghidra برای بیلد -O2 تابع total با متن بیلد -O1 تفاوت دارد، زیرا بهینه‌ساز حلقه را باز کرده است (loop unrolling). در مستندات دستی، 62 دستورالعمل شمرده شده، در حالی که بیلد -O1 تنها 13 دستورالعمل داشت. یک خط کد منبع، دو متن متفاوت. رد شدن ادعای متنی اصلاً به معنای تغییر رفتار تابع نیست و جمله‌ی ایجنت درباره‌ی خراب شدن تابع total هیچ پشتوانه‌ای ندارد.
  3. عملکرد بستر آزمایشی را بررسی کنید. یادداشت‌های بستر آزمایشی دو مرحله (leg) را شرح می‌دهند: مرحله‌ی اول کد منبع اصلی و هر کاندید را در قالب یک برنامه‌ی واحد کامپایل کرده و هر دو را روی 92 خانه اجرا می‌کند. مرحله‌ی دوم هر کاندید را برای هدف (target) اصلی کامپایل کرده و پس از ماسک‌کردن بازنشانی‌ها (relocation masking)، با فایل شیء اصلی مقایسه می‌کند. ابزار rea 6.7.0 هیچ‌کدام از این دو مرحله را ندارد؛ این دقیقاً همان بخشی بود که ایجنت باید اجرا می‌کرد و نکرد.
  4. جفت پیشنهادی ایجنت را روی شبکه‌ی ورودی‌ها بررسی کنید. جفت موجه، بازنویسی percent_change با نوع long و بازنویسی grade با شرط‌های آستانه‌ای است. مقدار naive_passed برابر true است، اما لیست عدم تطابق‌ها بلافاصله آغاز می‌شود: در ورودیِ before برابر 3 و after برابر 2147483647، تابع اصلی مقدار 133- و تابع کاندید مقدار 1431655899- را برمی‌گرداند. شمارش دستی در کل فایل نشان می‌دهد که این جفت در 28 خانه از 92 خانه خطا دارد؛ 26 مورد از آن‌ها مربوط به سرریز در percent_change است، جایی که تابع اصلی حاصل‌ضرب را قبل از تقسیم به 32 بیت محدود می‌کند (wrap)، اما بازنویسی با long این کار را انجام نمی‌دهد.
  5. دو خانه‌ی مربوط به تابع grade را بخوانید. بازنویسی مبتنی بر آستانه برای نمره‌ی 110 و همچنین مقدار INT_MAX عدد 4 را برمی‌گرداند، در حالی که ساختار switch اصلی هیچ حالتی (case) برای آن‌ها ندارد و 0 برمی‌گرداند. دسته‌ی ریسک این خطا «فراتر از محدوده‌ی سوییچ» است. 10 تست ساده‌لوحانه هرگز به هیچ‌کدام از این دو موقعیتِ پرریسک نرسیدند و به همین دلیل همگی پاس شدند.
  6. جفت معادل را بررسی کنید. جفتی که اول ضرب را انجام می‌دهد و ساختار switch را حفظ می‌کند، روی همان 92 خانه هیچ عدم تطابق و هیچ اختلافی با اوراکل (oracle) ندارد. یعنی مرحله‌ی اول را پاس کرده است؛ اما این هنوز اثباتی بر برابری بایت‌ها نیست.
  7. مرحله‌ی دوم را روی کاندیدِ دارای ثبات اشتباه بررسی کنید. کاندید grade_case10_wrong پس از ماسک‌کردن، دارای 46 بایت کد برابر با نسخه‌ی اصلی و یک بازآدرس‌دهی (relocation) با آفست، نوع و بخشِ کاملاً یکسان است، ولی وضعیت آن fail می‌شود. مقادیر جدول آن 1، 2، 3، 4، 3 است، در حالی که جدول اصلی 1، 2، 3، 4، 4 را نشان می‌دهد. تنها با خواندن مقادیر از طریق بازآدرس‌دهی می‌توان مچ این خطا را گرفت. یک بازنویسی ممکن است ادعای متنی را پاس کند، در مقایسه‌ی بایت‌های ماسک‌شده هم قبول شود، اما همچنان نمره‌ی متفاوتی را محاسبه کند.
نتیجه

گزارش پس گرفته می‌شود و دوباره نوشته خواهد شد. ادعاهای پاس‌شده‌ی percent_change صرفاً می‌گویند Ghidra برای هر دو بیلد متن یکسانی چاپ کرده است، و ادعاهای ردشده‌ی total نشان می‌دهند که متن متفاوتی چاپ شده است؛ هیچ‌کدام چیزی درباره‌ی رفتار نمی‌گویند و در بیلد -O2 نیز چیزی خراب نشده است. دو کاندید ایجنت صرفاً موجه به نظر می‌رسند: آن‌ها کامپایل می‌شوند، 10 تست ساده را پاس می‌کنند، و در 28 خانه از 92 خانه‌ی شبکه شکست می‌خورند. کاندیدهای پذیرفته‌شده عبارت‌اند از percent_change با اولویت ضرب و grade با ساختار switch. آن‌ها در تمام 92 خانه با نسخه‌ی اصلی هم‌خوانی دارند، بایت‌های ماسک‌شده‌ی آن‌ها با نسخه‌ی اصلی برابر است، رکوردهای بازآرایی آن‌ها ساختار یکسانی دارد و جدولی که به آن ارجاع می‌دهند در هر دو طرف مقادیر 1، 2، 3، 4، 4 را نشان می‌دهد.

قانون پذیرشی که تیم تدوین می‌کند چهار مرحله دارد و هر نتیجه‌ای کمتر از قبولی در تک‌تک مراحل، به معنی رد شدن کل فرایند خواهد بود: ادعاهای ساختاری در rea پاس شوند، در مرحله‌ی اول رفتار تابع روی تمام خانه‌های شبکه در یک میزبان مشخص یکسان باشد، در مرحله‌ی دوم بایت‌های ماسک‌شده و رکوردهای بازآرایی تطابق داشته باشند، و بایت‌هایی که هر بازآدرس‌دهی به آن‌ها اشاره می‌کند خوانده و مقایسه شوند. مشخصات سیستم میزبان و کامپایلر همراه با اثبات ثبت می‌شوند، زیرا خانه‌ی تله (trap cell) روی این سیستمِ میزبان با معماری arm64 مقداری را برمی‌گرداند، اما روی x86-64 متوقف می‌شود و خطای سخت‌افزاری ایجاد می‌کند.

مسیرهای اشتباه رایج
  • «ابزار verify_reconstruction برای percent_change پاس شد، پس بازنویسی تأیید شده است.» ادعاها صرفاً دو متن Ghidra را از دو بیلدِ نسخه‌ی اصلی با هم مقایسه کردند. آن‌ها هرگز کد بازنویسی‌شده را ندیدند، و قبولی در اینجا یعنی همان متن.
  • «ادعاهای total رد شدند، پس کامپایلر خروجیِ محاسباتیِ total را تغییر داده است.» دو متن متفاوت از یک خط کد منبع. رد شدن این ادعا فقط می‌گوید متن‌ها فرق دارند و در همین نقطه متوقف می‌شود.
  • «هر 10 تست شامل مقسوم‌علیه صفر و نمره‌ی منفی پاس شدند، پس بازنویسی درست است.» هیچ‌کدام از این 10 تست به خانه‌های سرریز یا نمره‌های فراتر از آخرین case نمی‌رسند. شبکه‌ی آزمون دقیقاً به همین دلیل 92 خانه دارد.
  • «بایت‌های ماسک‌شده برابرند و بازآدرس‌دهی‌ها تطابق دارند، پس می‌توان از خواندن جدول صرف‌نظر کرد.» خواندن داده‌های جدول تنها بررسی‌ای است که کاندیدِ دارای ثبات نادرست را رد می‌کند. بایت‌هایی را که هر بازآدرس‌دهی به آن‌ها اشاره می‌کند حتماً بخوانید.
درس کلی

یک مدل اعتبارسنج تنها می‌تواند ادعاهایی را ارزیابی کند که برای سنجش آن‌ها ساخته شده است، و حکم ارزیابیِ (verdict) آن همیشه با محدودیت‌هایی همراه است که خودش چاپ می‌کند. پیش از پذیرش یک حکم، بپرسید چه چیزی با چه چیزی مقایسه شده و آیا اصلاً دست‌سازه‌ی (artifact) مد نظر شما در ورودی وجود داشته است یا نه. برای یک تابع بازنویسی‌شده، برابری زنجیره‌ای از بررسی‌هاست که هر یک از آن‌ها نقصی را می‌گیرد که مرحله‌ی قبلی متوجهش نشده است: متن، رفتار روی شبکه‌ای از ورودی‌ها که به تک‌تک خطرات دیده‌شده در لیستینگ کد می‌رسد، بایت‌های ماسک‌شده، و در نهایت داده‌هایی که آن بایت‌ها به آن‌ها اشاره دارند. تست‌هایی که بدون رسیدن به شرایط پرریسک پاس می‌شوند، هیچ معیاری برای سنجش درستیِ رفتار کد در آن شرایط به دست نمی‌دهند.

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

در صفحه‌ی اعتبارسنجی Reverse Engineering 101 چهار ادعا بررسی شده‌اند، در صفحه‌ی بستر آزمایشی هر دو مرحله روی این کاندیدها اجرا می‌شود، در درس 36 این بستر آزمایشی پیاده‌سازی شده، و در درس حالت‌های شکست (failure modes) ادعای موفقیتی بررسی می‌شود که هیچ بررسیِ وضعیتی از آن پشتیبانی نمی‌کند.