تبدیل اسمبلی به شبه‌کد: پیاده‌سازی IR، فرم SSA و ساختاربندی از صفر

خروجی دیکامپایلرهایی مانند Ghidra یا ابزارهای مدرن هوش مصنوعی اغلب فریبنده است؛ کدی به ظاهر خوانا تولید می‌کنند، اما پشت صحنه‌ی این تولیدات پر از حدس‌های اثبات‌نشده، انواع داده‌ی اشتباه، و حتی پارامترها و شروط موهومی است. وقتی متخصصی نتواند زنجیره‌ی دقیق تبدیل بایت‌های ماشین به متغیرها و ساختارهای کنترلی زبان سطح بالا را دنبال کند، آسیب‌پذیری‌های امنیتی پنهان می‌مانند یا در تحلیل‌های بدافزار و مهندسی معکوس سردرگمی جدی رخ می‌دهد.

در این درس، تمام لایه‌های پنهان یک موتور دیکامپایلر را از پایه و بدون تکیه بر جعبه‌های سیاه بازسازی می‌کنید. یاد می‌گیرید که چطور دستورهای باینری x86-64 را به یک بازنمایی میانی (IR) شفاف بالا بکشید (Lift)، متغیرها را وارد فرم انتساب یگانه ایستا (SSA) کنید، الگوهای بهینه‌سازی محاسباتی مانند تقسیم‌های جادویی را بشکنید و ساختارهای حلقه و شرط را مستقیماً از روی گراف جریان کنترل بازسازی کنید.

تمام کدهای این درس به صورت بومی و در قالب اسکریپت پایتون و ابزارهای استاندارد مانند clang و llvm-objdump روی سیستم شخصی (حتی پردازنده‌های معمولی) قابل اجرا هستند و هیچ نیازی به پردازش ابری یا دسترسی‌های تحریم‌شده ندارند.

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

اهداف یادگیری

• بالا کشیدن (Lift) دستورهای رمزگشایی‌شده‌ی x86-64 به یک IR کوچک با پرچم‌ها، بارگذاری‌ها، ذخیره‌سازی‌ها، شاخه‌ها، فراخوانی‌ها و بازگشت‌های صریح.
• تبدیل اسلات‌های فریم استک به متغیرهای محلی و ثبات‌های ورودی System V به پارامترهای تابع.
• ساخت فرم SSA مینیمال با توابع phi روی مرزهای تسلط (Dominance frontiers)، و سپس جانشینی، ساده‌سازی و حذف کدهای مرده.
• بازیابی ساختارهای if، if به همراه else، while و do while از روی گراف جریان کنترل با پس‌مسلط‌ها (Post-dominators) و یال‌های برگشتی (Back edges).
• تحلیل و توجیه ضرب در 0x66666667 به‌صورت تقسیم بر 10 و اثبات این هم‌ارزی.
• خواندن خط‌به‌خط شبه‌کد Ghidra برای همین توابع و نسبت دادن تک‌تک تفاوت‌ها به یک دستور اسمبلی مشخص یا یک حدس.

صورت مسئله

از rea خواسته‌اید شبه‌کد percent_change را در فایل ledger-x86_64-O1.o استخراج کند. Ghidra 12.1.4 حدوداً ده ثانیه‌ای پاسخ داد:

undefined1  [16] percent_change(int param_1,int param_2,ulong param_3)

{
  long lVar1;
  undefined1 auVar2 [16];
  undefined1 auVar3 [16];
  
  if (param_1 != 0) {
    lVar1 = (long)((param_2 - param_1) * 100);
    auVar3._0_8_ = lVar1 / (long)param_1 & 0xffffffff;
    auVar3._8_8_ = lVar1 % (long)param_1 & 0xffffffff;
    return auVar3;
  }
  auVar2._8_8_ = 0;
  auVar2._0_8_ = param_3;
  return auVar2 << 0x40;
}

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

ابزار rea این متن را به‌عنوان نتیجه‌ی procedure_pseudo_code برمی‌گرداند و یک محدودیت به رکورد ضمیمه می‌کند: «شبه‌کد خروجی دیکامپایلر Ghidra است، نه سورس اصلی و نه هم‌ارز متنی خروجی Hopper». ابزار compare_functions شبه‌کدها را خط‌به‌خط مثل خطوط متنی مقایسه می‌کند. رکورد ابعاد خود این ابزار می‌گوید «اسمبلی متن ماتِ ارائه‌دهنده است» و نرمال‌سازی بازآرایی‌ها (Relocations) در دسترس نیست. نه rea می‌تواند درون این متن را تحلیل کند، و نه ایجنتی که صرفاً خواننده‌ی آن باشد.

رکورد DX-Ball در rea هزینه‌ی این بی‌خبری را نشان می‌دهد. اولین خروجی دیکامپایلر FUN_00406400(void) بود که __ftol() را فراخوانی می‌کرد. نمای دستورالعمل‌ها یک ورودی روی استک و یک عبارت x87 را نشان می‌داد. ایجنت فقط از این جهت به کارش ادامه داد که این دو نما با هم در تناقض بودند.

این درس استنتاجی را بازسازی می‌کند که دیکامپایلر پنهان کرده است. کار را از 56 دستورالعملی شروع می‌کنید که درس 33 رمزگشایی کرد؛ آن‌ها را به یک IR بالا می‌کشید، با تغییر نام به SSA می‌برید، ساده‌سازی می‌کنید و ساختار کنترل جریان را بازمی‌یابید. سپس شبه‌کد خودتان را کنار شبه‌کد Ghidra برای percent_change، grade و total می‌گذارید و علت تک‌تک تفاوت‌ها را بررسی می‌کنید. تست‌ها خروجی شما را با clang کامپایل کرده و آن را روی شبکه‌ای از ورودی‌های مختلف در برابر کد مبدأ اجرا می‌کنند.

فیکسچر و اوراکل (Oracle)

فایل code/fixtures/ledger.c فیکسچر مشترک این بخش از دوره است:

int percent_change(int before, int after) {
    if (before == 0) return 0;
    return (after - before) * 100 / before;
}

int grade(int score) {
    switch (score / 10) {
    case 10:
    case 9: return 4;
    case 8: return 3;
    case 7: return 2;
    case 6: return 1;
    default: return 0;
    }
}

int total(const int *values, int count) {
    int sum = 0;
    for (int i = 0; i < count; i++) sum += values[i];
    return sum;
}

تابع grade_label هم در فایل و هم در فایل شیء (Object file) موجود است، و کد دمو آن را نیز بالا می‌کشد. سه تابع بالا مواردی هستند که در این درس تست می‌شوند.

فایل شیء با دستور clang -target x86_64-unknown-linux-gnu -O1 -fno-asynchronous-unwind-tables -c ledger.c ساخته شده است. فایل شیء کامپایل‌شده با -O0 نیز برای بخش اسلات‌های استک در کنار آن قرار دارد. فایل code/fixtures/README.md هر دو دستور، هش SHA-256 هر شیء و دستور rea را که فیکسچرهای Ghidra را تولید کرده فهرست می‌کند. کل فرآیند بیلد، بایت‌به‌بایت روی زنجیره‌ابزار پین‌شده تکرارپذیر است.

اوراکل ما برای اعتبارسنجی دیکودر، ابزار llvm-objdump -d -r است. متن آن برای هر دو شیء به‌صورت ledger-x86_64-O1.objdump.txt و ledger-x86_64-O0.objdump.txt commit شده است. یک تست این فایل‌ها را پارس کرده و تک‌تک دستورها را بر اساس آدرس، بایت‌ها و متن AT&T مقایسه می‌کند. این تست تمامی 56 دستور در سطح -O1 و تک‌تک دستورهای سطح -O0 را پوشش می‌دهد. اگر llvm-objdump در مسیر پین‌شده نصب باشد، تستی دیگر آن را به‌صورت زنده اجرا کرده و دوباره مقایسه می‌کند.

خروجی چاپی اوراکل برای percent_change به این صورت است:

0000000000000000 <percent_change>:
       0: 85 ff                        	testl	%edi, %edi
       2: 74 09                        	je	0xd <percent_change+0xd>
       4: 29 fe                        	subl	%edi, %esi
       6: 6b c6 64                     	imull	$0x64, %esi, %eax
       9: 99                           	cltd
       a: f7 ff                        	idivl	%edi
       c: c3                           	retq
       d: 31 c0                        	xorl	%eax, %eax
       f: c3                           	retq

مرحله‌ی 1: تبدیل بایت‌ها به دستورالعمل‌ها

درس 33 بخش دیکودر را ساخت. در این درس نسخه‌ی کوچکی از آن نگه داشته شده تا کد مستقل اجرا شود. این پیاده‌سازی دقیقاً آپ‌کدهایی (Opcodes) را پوشش می‌دهد که کامپایلر clang برای ledger.c در سطوح -O0 و -O1 تولید کرده است. برای هر چیز دیگری، خطای DecodeError همراه با آدرس و بایتِ آپ‌کد صادر می‌شود.

دیکودر از ترتیب بایت‌های مشخص‌شده در راهنمای توسعه‌دهندگان اینتل (Intel SDM)، جلد 2، بخش 2.1 پیروی می‌کند. پیشوندها اول می‌آیند، سپس آپ‌کد، بعد ModR/M، سپس SIB، بعد جابه‌جایی (Displacement) و در نهایت مقدار فوری (Immediate). بخش 2.2.1 پیشوند REX را اضافه می‌کند؛ یک بایت بین 0x40 تا 0x4F که باید دقیقاً پیش از آپ‌کد بنشیند. بیت REX.W عملوند 64 بیتی را انتخاب می‌کند، REX.R فیلد reg را گسترش می‌دهد، REX.X فیلد اندیس SIB را بزرگ‌تر می‌کند و REX.B فیلد r/m یا پایه‌ی SIB را گسترش می‌دهد. بخش 2.1.3 سه فیلد ModR/M یعنی mod، reg و r/m، و سه فیلد SIB شامل scale، index و base را تعریف می‌کند. در حالت 64 بیتی، ترکیب mod = 00 با r/m = 101 یعنی یک جابه‌جایی 32 بیتی نسبت به دستور بعدی (بخش 2.2.1.6).

دستور leaq (%rip), %rcx در آدرس grade+0x23 هفت بایت با جابه‌جایی صفر است. فایل شیء یک بازآرایی با عنوان R_X86_64_PC32.rodata+0x10 در آفست 0x36 (یعنی همان فیلد جابه‌جایی) دارد. لایه‌ی بالا کشیدن (Lifter) این بازآرایی را در مرحله‌ی 3 حل‌وفصل می‌کند.

مرحله‌ی 2: بلوک‌ها و مسلط‌ها (Dominators)

یک بلوک پایه (Basic block) دنباله‌ای از دستورها است که دقیقاً یک نقطه‌ی ورود در ابتدا و یک نقطه‌ی خروج در انتها دارد. این تعریف آلن (Allen, 1970) است و تمام مقالات حوزه‌ی دیکامپایل از آن استفاده می‌کنند. تابع build_blocks() رهبرها (Leaders) را جمع‌آوری می‌کند: نقطه‌ی ورود تابع، تمام مقصدهای پرش درون تابع، و هر آدرسی که بلافاصله بعد از یک پرش یا return بیاید. هر بلوک، جانشین‌هایش (Successors) را از آخرین دستور خود می‌گیرد. پرش شرطی دو جانشین و پرش jmp یک جانشین دارد. دستور ret هیچ جانشینی ندارد، و بلوکی که به یک دستور عادی ختم شود، به رهبر بعدی می‌ریزد (Fall-through).

تابع total در سطح -O1 پنج بلوک دارد:

تابع immediate_dominators() همان الگوریتم تکرارشونده‌ی کوپر، هاروی و کندی (2001) است. این الگوریتم بلوک‌ها را در پیمایش پس‌مرتبه معکوس (Reverse postorder) بررسی می‌کند و اشتراک مسلط‌های پیشینیان پردازش‌شده را تا زمان همگرایی کامل می‌گیرد. روی چنین گراف‌های کوچکی، کار در دو گذر تمام می‌شود. برای total خروجی نشان می‌دهد که 0x44 بر 0x50 مسلط است. همچنین مشخص می‌کند که 0x50 از طریق یال برگشتی بر خودش تسلط دارد؛ مرحله‌ی 8 از همین طریق حلقه را پیدا می‌کند.

همین تابع دو بار دیگر هم اجرا می‌شود: dominance_frontiers() از آن برای SSA در مرحله‌ی 5 استفاده می‌کند؛ و post_dominators() آن را روی گراف معکوس همراه با یک گره خروج مجازی اجرا می‌کند تا نقاط پیوند (Joins) را در مرحله‌ی 8 پیدا کند.

مرحله‌ی 3: بالا کشیدن به یک IR کوچک

این IR شش نوع عبارت (Statement) دارد: Assign، Store، Branch، Jump، IndirectJump و Return. عبارت‌های محاسباتی شامل مقادیر ثابت، متغیرها، عملیات‌های دودویی با عرض مشخص، تبدیل‌های نوع (sext، zext، trunc) و بارگذاری‌ها هستند. پنج ساختار دیگر هم وجود دارند که تنها برای ساده‌سازی و حذف شدن در مراحل بعدی تعریف شده‌اند: Flags، Cond، Concat، SignFill و Symbolic.

ثبات‌ها متغیرهایی هستند که با نام خانوادگی 64 بیتی خود نام‌گذاری می‌شوند. نوشتن در %eax یک Assign به rax با عرض 32 است، و خواندن از %eax خواندن از rax در عرض 32 است. در حالت 64 بیتی، یک نوشتن 32 بیتی با اضافه کردن صفرها به کل ثبات گسترش می‌یابد (Zero-extension)، بنابراین خواندن 64 بیتی بعدی از همان مقدار تبدیل به یک zext می‌شود. لایه‌ی بالا کشیدن هنوز از تعریفِ حاکم (Reaching definition) خبر ندارد، به همین دلیل عرض خواندن را ثبت می‌کند و درج Cast لازم را به مرحله‌ی 5 (SSA) می‌سپارد.

پرچم‌ها متغیر هستند

هر دستوری که کدهای وضعیت را تغییر می‌دهد، روی یک متغیر واحد به نام flags می‌نویسد، و هر پرش شرطی آن را می‌خواند. دستور cmp a, b عبارت cmp(a, b) را می‌نویسد، دستور test a, b مقدار test(a, b) را ثبت می‌کند، و sub هم اثر جانبی مشابه cmp دارد. دستور jcc تبدیل به Branch(Cond(cc, flags), target, fallthrough) می‌شود. زمانی که این دو در مرحله‌ی 6 به هم می‌رسند، کد وضعیت، عملگر مقایسه را تعیین می‌کند:

دستور xorl %eax, %eax مستقیماً به eax = 0 تبدیل می‌شود. پرچم‌هایی که تنظیم می‌کند مشابه پرچم‌های add نوشته می‌شوند که هیچ پرشی در فیکسچر ما آن‌ها را نمی‌خواند. این ساختار xor در تابع grade اهمیت زیادی پیدا می‌کند؛ همان‌جایی که Ghidra مسیر را گم کرد.

دستورهای cltd و idiv

دستور cltd ثبات %edx را با بیت علامت %eax پر می‌کند. دستور idivl %edi زوج 64 بیتی %edx:%eax را بر %edi تقسیم می‌کند، خارج‌قسمت را در %eax و باقی‌مانده را در %edx می‌گذارد. لایه‌ی بالا کشیدن این زوج را ابتدا در یک متغیر موقت به نام dividend می‌نویسد. بدین ترتیب عبارت محاسبه‌ی باقی‌مانده، مقدار قدیمی %eax را می‌خواند نه خارج‌قسمت تازه‌تولیدشده را. در فرم SSA نیمه‌ی بالایی به‌صورت signfill از نیمه‌ی پایینی ظاهر می‌شود. ساده‌ساز این جفت را به نیمه‌ی پایینی کاهش می‌دهد و عمل تقسیم تبدیل به یک / عادی 32 بیتی می‌شود.

اسلات‌های استک در سطح -O0

در سطح -O0 کامپایلر clang تمام متغیرهای محلی را در فریم استک نگه می‌دارد. تابع percent_change ثبات %edi را در -0x8(%rbp) و %esi را در -0xc(%rbp) ذخیره می‌کند، و در هر بار استفاده دوباره آن‌ها را می‌خواند. لایه‌ی بالا کشیدن منتظر الگوی pushq %rbp به دنبال movq %rsp, %rbp می‌ماند. پس از این مقدمه، هر عملوند حافظه با پایه‌ی %rbp، بدون اندیس و دارای جابه‌جایی، تبدیل به متغیری با نام local_<hex> می‌شود؛ مثلاً -0x8(%rbp) به local_8 و -0xc(%rbp) به local_c تبدیل خواهد شد.

خود دستورهای مدیریت فریم، کدی در IR تولید نمی‌کنند؛ دستورهای subq و addq روی ثبات %rsp هم همین‌طور. سایر عملوندهای حافظه به‌صورت دست‌نخورده در قالب Load یا Store باقی می‌مانند.

بازآرایی‌ها (Relocations)

دستور leaq (%rip), %rcx در تابع grade در داخل فایل دارای جابه‌جایی صفر است. بازآرایی موجود در آفست 0x36 مقدار R_X86_64_PC32.rodata+0x10 را اعلام می‌کند. لینکر فرمول S + A - P را درون این فیلد می‌نویسد: S آدرس بخش .rodata، A همان Addend برابر با 0x10، و P آدرس خود فیلد است. در زمان اجرا، دستور مقدار next_ip + disp = (P + 4) + S + A - P = S + A + 4 را محاسبه خواهد کرد.

لایه‌ی بالا کشیدن همین محاسبات را بدون نیاز به لینکر شبیه‌سازی می‌کند. آفست مقصد برابر است با جمع Addend با فاصله‌ی فیلد تا انتهای دستور: 0x10 + 4 = 0x14. بنابراین در IR نوشته می‌شود: rcx = &.rodata+0x14. جدول موجود در آن نقطه، پنج مقدار int یعنی 1, 2, 3, 4, 4 را نگه‌داری می‌کند.

مرحله‌ی 4: استخراج پارامترها از قرارداد فراخوانی

بر اساس بخش 3.2.3 استاندارد System V AMD64 psABI، آرگومان‌های کلاس INTEGER به ترتیب در ثبات‌های %rdi، %rsi، %rdx، %rcx، %r8 و %r9 پاس داده می‌شوند. نتیجه ابتدا در %rax و سپس در صورت لزوم در %rdx برمی‌گردد. بخش 3.2.1 بیان می‌کند که ثبات‌های %rbp، %rbx و %r12 تا %r15 متعلق به فراخواننده (Caller) هستند و مقدارشان باید حفظ شود. بقیه‌ی ثبات‌ها در اختیار تابع فراخوانده‌شده (Callee) هستند.

تابع collect_params() یک قاعده را پیاده می‌کند: هر ثبات آرگومان که قبل از هرگونه نوشتن درون تابع خوانده شود، یک پارامتر است. بالاترین ثبات با این شرایط، تعداد کل پارامترها را تثبیت می‌کند؛ بنابراین تابعی که %rsi را بخواند ولی کاری با %rdi نداشته باشد، همچنان دو پارامتر دارد. تابع percent_change ثبات‌های %edi و %esi را می‌خواند، پس دو ورودی param_1 و param_2 دارد. تابع grade فقط %edi را می‌خواند. تابع total ثبات %rdi را به‌عنوان آدرس پایه‌ی 64 بیتی و %esi را به‌عنوان تعداد 32 بیتی می‌خواند.

اکنون دلیل حضور param_3 در خروجی Ghidra روشن می‌شود: دستور idivl روی %rdx می‌نویسد، و psABI اجازه می‌دهد مقدار بازگشتی INTEGER در حالت 128 بیتی درون زوج %rax:%rdx قرار گیرد. در یک فایل شیء هیچ فراخواننده‌ای وجود ندارد تا معلوم کند مقدار بازگشتی چقدر عریض است؛ در نتیجه Ghidra هر دو ثبات را مقدار بازگشتی در نظر گرفته است.

در مسیر مربوط به شرط صفر، دستور xorl %eax, %eax فقط روی %eax می‌نویسد. Ghidra در آن نقطه %rdx را به‌عنوان یک ورودی خواند، و همان ورودی تبدیل به param_3 شد. دستورها درست فهمیده شده‌اند؛ این امضای تابع است که صرفاً حدسی درباره‌ی بخش‌های نامشخص دستورها به شمار می‌رود.

مرحله‌ی 5: SSA، یک نام برای هر تعریف

پس از بالا کشیدن اولیه، تابع grade چهار بار روی rax و سه بار روی rcx مقدار می‌نویسد. سایترون، فرانته، روزن، وگمن و زادک (1991) فرم SSA (تک‌انتسابی ایستا) را تعریف کردند. هر متغیر دقیقاً یک بار مقداردهی می‌شود، و توابع phi در نقاط ادغام مشخص می‌کنند که کدام تعریف به آن‌ها رسیده است. ساختار آن‌ها دو گام دارد: بخش 5.1 توابع phi را با استفاده از مرزهای تسلط مستقر می‌کند، و بخش 5.2 با پیمایش درخت مسلط‌ها نام همه‌ی تعاریف و استفاده‌ها را بازنویسی می‌کند. توابع insert_phis() و rename() دقیقاً از همین دو بخش پیروی می‌کنند.

نمایش SSA برای تابع total خروجی این ساختار را نشان می‌دهد:

block 0x44 -> 0x50
  ecx_1 = esi_0
  edx_1 = 0
  eax_1 = 0
block 0x50 -> 0x50, 0x5b
  eax_2 = phi(0x44: eax_1, 0x50: eax_3)
  rdx_2 = phi(0x44: edx_1, 0x50: rdx_3)
  flags_2 = phi(0x44: flags_1, 0x50: flags_5)
  flags_3 = add(eax_2, load32(rdi_0 + rdx_2 * 4))
  eax_3 = eax_2 + load32(rdi_0 + rdx_2 * 4)
  flags_4 = inc(rdx_2, 1)
  rdx_3 = rdx_2 + 1
  flags_5 = cmp(zext64(ecx_1), rdx_3)
  if jne(flags_5) goto 0x50 else goto 0x5b

نسخه‌ی 0 یک ثبات، مقدار آن در بدو ورود به تابع است. esi_0 و rdi_0 همان پارامترها هستند. سربرگ حلقه در 0x50 دو پیش‌نیاز دارد: بلوک راه‌اندازی و خودش؛ به همین دلیل هر متغیری که درون حلقه تعریفی داشته باشد، در آنجا یک تابع phi دریافت می‌کند. متغیر flags_2 در بدو ورود مرده است؛ الگوریتم SSA مینیمال آن را به این دلیل قرار داده که flags در هر دو پیشین دارای تعریف بوده است، اما مرحله‌ی 6 آن را حذف می‌کند چون هیچ کدی آن را نمی‌خواند.

مرحله‌ی تغییر نام، مسأله‌ی عرض ثبات‌ها را هم برطرف می‌کند: edx_1 = 0 تعریفی 32 بیتی است در حالی که rdx_3 = rdx_2 + 1 مقداری 64 بیتی است؛ در نتیجه متغیر phi یعنی rdx_2 عرض بزرگ‌تر را به خود می‌گیرد. خواندن %rcx در دستور cmpq %rdx, %rcx به‌صورت 64 بیتی انجام می‌شود در حالی که تعریف آن یعنی ecx_1 = esi_0 مقداری 32 بیتی است، بنابراین استفاده از آن تبدیل به zext64(ecx_1) می‌شود. تمام تبدیل‌های نوع (Casts) در شبه‌کد نهایی بر اساس همین یک قاعده به وجود آمده‌اند.

بخش «سبک» کار، نحوه‌ی خروج از SSA است. تابع coalesce_webs() هر تابع phi را با آرگومان‌هایش در قالب یک متغیر ادغام‌شده (به نام Web) ترکیب می‌کند و یک نام واحد به آن می‌دهد. این کار برای الگوهایی که کامپایلر در این توابع تولید کرده کاملاً جواب می‌دهد. اما ممکن است در کپی‌های موازی—جایی که دو تابع phi در یک نقطه‌ی پیوند مقادیر را جابه‌جا می‌کنند—دچار مشکل شود؛ این پیاده‌سازی به آن مورد خاص نمی‌پردازد. بخش 7 مقاله‌ی سایترون خروج کلی را از طریق رنگ‌آمیزی گراف توضیح می‌دهد.

مرحله‌ی 6: ساده‌سازی، جانشینی، حذف کد مرده

تابع optimize() سه گذر را تا رسیدن به نقطه‌ی ثبات تکرار می‌کند. ساده‌ساز، عبارت‌ها را از پایین به بالا با قواعد زیر بازنویسی می‌کند:

جانشینی پیش‌رو (Forward substitution) یک تعریف را به تنها محل استفاده‌اش منتقل می‌کند. این قاعده سه شرط دارد: محل استفاده در همان بلوک باشد؛ محل استفاده یک دستور عادی باشد نه تابع phi؛ و اگر تعریف شامل بارگذاری است، هیچ دستور Store یا فراخوانی تابعی بین تعریف و استفاده قرار نگرفته باشد. مقدار ثابت یا آدرس بخش حافظه در همه‌جا به‌جز در آرگومان تابع phi جایگزین می‌شود، چرا که آرگومان phi باید متغیر باقی بماند تا ساختار Web حفظ شود.

حذف کدهای مرده، هر انتساب یا تابع phi را که مقصد آن مصرف‌کننده‌ای ندارد و عبارت آن فراخوانی تابع نیست پاک می‌کند. ترتیب اجرای گذرها اهمیت دارد: در percent_change باقی‌مانده‌ی تقسیم یعنی edx_2 = dividend_1 % edi_0 استفاده‌ای ندارد و مرده است، بنابراین اول حذف می‌شود. این کار باعث می‌شود edx_1 = signfill(eax_1) تنها یک مصرف‌کننده پیدا کند و درون dividend_1 = edx_1:eax_1 جانشین شود.

سپس قاعده‌ی ادغام زوج‌ها عبارت signfill(eax_1):eax_1 را به eax_1 کاهش می‌دهد، و تقسیم به‌صورت eax_1 / edi_0 درمی‌آید. حالا عبارت eax_1 = esi_1 * 100 فقط یک استفاده دارد، و esi_1 = esi_0 - edi_0 هم فقط یک مصرف‌کننده دارد؛ هر دو به درون دستور return منتقل می‌شوند. تعاریف flags هم در شروط انشعاب جانشین شده و ناپدید می‌شوند. چهار دستور به یک خط تبدیل می‌شوند:

return (param_2 - param_1) * 100 / param_1;

ضرب جادویی در 0x66666667

تابع grade امتیاز را بر 10 تقسیم می‌کند، اما کامپایلر clang اصلاً دستور idiv نزده است. به جای آن، ابتدا imulq $0x66666667, %rax, %rax، سپس روی یک کپی از آن sarq $0x22, %rcx و بعد shrq $0x3f, %rax را اجرا کرده و در نهایت این دو را جمع می‌کند. گرنلاند و مونتگومری در مقاله‌ی «Division by Invariant Integers using Multiplication» (PLDI 1994) این روش را توضیح داده‌اند: کامپایلر یک ضریب m و یک مقدار شیفت s انتخاب می‌کند به‌طوری که به ازای تمام مقادیر x در دامنه، حاصل عبارت (x * m) >> s دقیقاً برابر با x / d شود.

در اینجا m = 0x66666667 = 1717986919 و s = 34 است. محاسبات درستی فرمول را تأیید می‌کنند: 2^34 / 10 = 1717986918.4 که سقف (Ceiling) آن 1717986919 می‌شود. مقدار خطا برابر است با m * 10 - 2^34 = 6. برای این‌که این هم‌ارزی برای هر مقدار 32 بیتی x برقرار بماند، حاصل‌ضرب خطا در 2^31 باید کمتر از 2^34 بماند، یعنی خطا حداکثر می‌تواند 8 باشد. شش از هشت کمتر است، بنابراین (x * m) >> 34 برای هر عدد صحیح نامنفی (int) برابر با floor(x / 10) خواهد بود.

برای مقادیر منفی x، تابع کف (Floor) عدد را از صفر دور می‌کند در حالی که C آن را به سمت صفر گرد می‌کند. دستور shrq $0x3f بیت علامت حاصل‌ضرب را استخراج می‌کند که دقیقاً در صورت منفی بودن x برابر با 1 است. جمع کردن آن، گرد کردن را اصلاح کرده و با C هماهنگ می‌سازد.

تابع magic_divisor(m, s) یک زوج کاندید را می‌آزماید: خارج‌قسمت صحیح 2^s بر m را با عنوان d محاسبه کرده و هر دو حالت d و d + 1 را امتحان می‌کند. این تابع d را تنها زمانی می‌پذیرد که m مساوی با سقف 2^s / d باشد و کران خطا برقرار بماند. همین ضریب با شیفت s = 33 عدد d = 5 را به دست می‌دهد که درست است، چون 0x66666667 سقف 2^33 / 5 نیز هست. یک تست، این هم‌ارزی را در برابر c_div(x, 10) روی 2406 مقدار عددی شامل هر دو انتهای دامنه‌ی int می‌سنجد.

اگر شناسایی الگو روشن باشد، خروجی تابع grade به‌صورت ecx_1 = param_1 / 10 - 6; خوانده می‌شود. اما اگر شناسایی الگو را خاموش کنید، دمو فرم خام را چاپ می‌کند:

rax_1 = (long)param_1 * 0x66666667;
ecx_1 = (int)(rax_1 >> 34) + (int)((unsigned long)rax_1 >> 63) - 6;

هر دو فرم کامپایل می‌شوند و مقادیر یکسانی را حساب می‌کنند. این کلید را نگه دارید؛ وقتی با کد کامپایلری که مطالعه‌اش نکرده‌اید کار می‌کنید، فرم خام فرم صادقانه است.

مرحله‌ی 7: استخراج انواع داده از نحوه‌ی استفاده

کد ماشین صرفاً عرض داده‌ها را می‌شناسد و چیزی به نام نوع ندارد. تابع infer_types() سه نوع از شواهد را به انواع زبان C تبدیل می‌کند: وبی که تعاریفش 32 بیتی باشند int می‌شود و وب 64 بیتی long خواهد شد. اگر وبی مبنای دسترسی به یک آرایه به شکل base[idx] با عناصر 4 بایتی باشد، نوع int * می‌گیرد. نوع اشاره‌گر در امتداد کپی‌ها و توابع phi منتشر می‌شود، بنابراین local_8 = param_1 در سطح -O0 نوع هر دوی آن‌ها را int * می‌کند. نوع بازگشتی هم عرض مقدار موجود در دستورهای return است.

نتیجه برای total به‌صورت int total(int *param_1, int param_2) درمی‌آید. خروجی Ghidra به این شکل بود: int total(long param_1,uint param_2). هر دو با دستورهای ماشین همخوانی دارند. لایه‌ی بالا کشیدن ما از دسترسی مقیاس‌شده به‌عنوان شواهد اشاره‌گر استفاده کرد. اما Ghidra همان عرض ثبات را نگه داشت و دسترسی را به شکل *(int *)(param_1 + uVar2 * 4) نوشت. هیچ‌کدام نمی‌توانند const را ببینند، و هیچ‌کدام قادر نیستند تفاوت int * را با unsigned * تشخیص دهند.

لی، آوگرینوس و براملی (TIE, NDSS 2011) بازیابی انواع را به‌صورت حل مسأله‌ی ارضای قید روی یک مشبکه (Lattice) مدل کردند. نتیجه به جای یک حدس تنها، کران بالا و پایین نوع است. نونان، لاگینوف و کوک (Retypd, PLDI 2016) چندریختی و بازگشت را هم به آن اضافه کردند. آن‌ها بازخوانی 98 درصدی را برای شناسایی نشانه‌گذاری‌های اشاره‌گر const بر اساس الگوهایی که کامپایلر جا می‌گذارد گزارش کردند. در این درس از دو قاعده‌ی ساده‌ی آن مقالات استفاده شده و محدودیت‌های آن‌ها نیز نام برده شده است.

محاسبات بدون علامت درون عبارت‌ها نگه داشته می‌شوند نه در نوع متغیرها. دستور ja بعد از cmpl $0x4, %ecx به‌صورت (unsigned int)ecx_1 > 4 چاپ می‌شود، و shrq به شکل (unsigned long)rax_1 >> 63 می‌آید. متغیرها علامت‌دار می‌مانند تا خواننده هم مقدار ثبات را ببیند و هم تک نقطه‌ای را که دستور با آن مثل عدد بدون علامت رفتار کرده تشخیص دهد.

مرحله‌ی 8: ساختاربندی از روی گراف

سیفوئنتس (Cifuentes, 1994) در فصل ششم، نواحی مختلف گراف را با شکل‌های زبان‌های سطح بالا مطابقت می‌دهد: اول حلقه‌ها (6.6.1)، بعد شرط‌های دوطرفه (6.6.2)، و سپس شرط‌های چندطرفه (6.6.3). در مقابل، یکدان، اشویلر، گرهاردز-پادیلا و اسمیت (NDSS 2015) مسیر دیگری را پیش گرفتند: شرط اجرای هر گره را استخراج می‌کنند و ساختار را بدون تکیه بر قالب‌های ثابت از روی همان شروط می‌سازند. انگیزه‌ی آن‌ها آماری بود: خروجی Hex-Rays روی یک نمونه، 1571 دستور goto در طول 49514 خط کد داشت (یکی به ازای هر 32 خط)، در حالی که روش بدون قالب آن‌ها روی 1530 تابع از coreutils حتی یک goto هم تولید نکرد.

تابع structure() عضوی کوچک از دسته‌ی اول است. این تابع به دو داده از مرحله‌ی 2 نیاز دارد: پس‌مسلط بی‌واسطه‌ی بلوکی که به Branch ختم می‌شود، همان نقطه‌ی پیوند شرط است. یال برگشتی، یالی است به بلوکی که بر مبدأ خود یال تسلط دارد. حلقه‌ی طبیعی هم مجموعه‌ای از بلوک‌هاست که بدون عبور از سربرگ، به مبدأ یال برگشتی می‌رسند.

برای یک Branch با نقطه‌ی پیوند j:

• اگر j مقصد پرش باشد، if (!cond) { fallthrough region } را ثبت کن و از j ادامه بده.
• اگر j شاخه‌ی مستقیم باشد، if (cond) { target region } را ثبت کن و از j ادامه بده.
• اگر j نقطه‌ی خروج از تابع باشد، هر دو شاخه return می‌کنند. شاخه‌ی کوچک‌تر را به‌صورت if (cond) {... } ثبت کن و شاخه‌ی دیگر را بعد از آن، بدون else بیاور. این همان الگوی خروج زودهنگام در percent_change و total است.
• در غیر این صورت ساختار if (cond) { target } else { fallthrough } را بساز و کار را از j ادامه بده. این وضعیت در percent_change سطح -O0 رخ می‌دهد؛ جایی که هر دو شاخه در local_4 می‌نویسند و در بخش پایانی به هم می‌رسند.

برای سربرگ حلقه:

• اگر سربرگ با یک Branch ختم شود که یک جانشین بیرون از حلقه دارد، ساختار while (cond) { body } را بساز. تابع total در سطح -O0 دقیقاً همین شکل را دارد: سربرگ local_14 را با local_c مقایسه می‌کند و با jge خارج می‌شود.
• اگر سربرگ خودش همان بلوک دارای یال برگشتی باشد، یا خروج از طریق لچ (Latch) انجام شود، عبارت do { body } while (cond); را خروجی بده. تابع total در سطح -O1 این الگو را دارد: بلوک 0x50 جمع می‌زند، مقدار را زیاد می‌کند، مقایسه می‌کند و به خودش پرش می‌زند.

یک IndirectJump پایان بلوکی بدون جانشین است. تابع grade در سطح -O0 یک جدول پرش واقعی است: دستور jmpq *%rax از طریق پنج آفست نسبی در .rodata+0x0 پرش می‌کند و درس 33 این مقاصد را حل می‌کند. در این درس لایه‌ی بالا کشیدن یک یادداشت چاپ می‌کند: چهار بلوک در آدرس‌های 0x76، 0x7f، 0x88 و 0x91 صرفاً از طریق همین پرش غیرمستقیم در دسترس‌اند و بالا کشیده نشده‌اند. در کارگاه تمرینی بخش switch اضافه خواهد شد.

سطح -O1 با switch چه کرد؟

در سطح -O1 کامپایلر clang جدول پرش را برای grade نگه نداشت. به جای آن، score / 10 - 6 را حساب کرد و نتیجه را به عنوان عددی بدون علامت با 4 سنجید. سپس مقدار بازگشتی را از یک جدول پنج‌عنصری از int در بخش .rodata+0x14 لود کرد. این مقایسه‌ی بدون علامت، در قالب یک دستور، هر دو حالت score / 10 < 6 و score / 10 > 10 را پوشش می‌دهد؛ چون تفاضل منفی به یک مقدار بزرگ بدون علامت تبدیل می‌شود و از شرط رد نمی‌شود.

جدول شامل مقادیر 1, 2, 3, 4, 4 برای خارج‌قسمت‌های 6 تا 10 است. بدین ترتیب switch با پنج دستور return به یک if و یک خواندن از آرایه تبدیل شد. لایه‌ی بالا کشیدن دقیقاً همین را تولید می‌کند و نام جدول را به خاطر آفست آن lookup_14 می‌گذارد.

طول این جدول بر اساس یک روش اکتشافی به دست می‌آید: تابع table_values() بایت‌ها را از شروع جدول تا اولین آفست بعدی در .rodata که توسط یک بازآرایی در .text به آن ارجاع شده، یا تا انتهای بخش می‌خواند. در این شیء، آفست ارجاع‌شده‌ی بعدی 0x28 (جدول مربوط به grade_label) است؛ در نتیجه lookup_14 دارای (0x28 - 0x14) / 4 = 5 عنصر است. مقایسه‌ی بدون علامت با عدد 4 هم بر همین موضوع دلالت دارد. Ghidra هم طول را تشخیص نداده بود و آن را به شکل *(uint *)(&DAT_001000b4 + (ulong)uVar2 * 4) نوشت؛ یعنی یک آدرس بایت به اضافه‌ی آفست، و گشتن دنبال این پنج مقدار را به عهده‌ی خود خواننده گذاشت.

مقایسه‌ی شانه به شانه با Ghidra

کد دمو هر جفت را کنار هم چاپ می‌کند. متن Ghidra از فایل‌های code/fixtures/ghidra/*.json می‌آید؛ همان رکوردهای شواهدی که rea در تاریخ 2026-10-14 برگردانده است. دستور مربوطه npx -y rea-agents@6.5.0 decompile ledger-x86_64-O1.o <function> --provider ghidra --format json بود. هر رکورد شامل confidence: observed و authority: shipped-artifact است. این متن عیناً مشاهده شده؛ اما ادعاهای درون متن حاصل استنتاج‌هایی هستند که رکوردها مشخص نکرده‌اند کدام‌اند.

percent_change

lifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
int percent_change(int param_1, int param_2)   | undefined1  [16] percent_change(int param_1,int param_2,ulong param_3)
{                                              | {
  if (param_1 == 0) {                          |   long lVar1;
    return 0;                                  |   undefined1 auVar2 [16];
  }                                            |   undefined1 auVar3 [16];
  return (param_2 - param_1) * 100 / param_1;  |   if (param_1 != 0) {
}                                              |     lVar1 = (long)((param_2 - param_1) * 100);
                                               |     auVar3._0_8_ = lVar1 / (long)param_1 & 0xffffffff;
                                               |     auVar3._8_8_ = lVar1 % (long)param_1 & 0xffffffff;
                                               |     return auVar3;
                                               |   }
                                               |   auVar2._8_8_ = 0;
                                               |   auVar2._0_8_ = param_3;
                                               |   return auVar2 << 0x40;
                                               | }

نسخه‌ی اصلاح‌شده در code/fixtures/ghidra/ledger-x86_64-O1.ghidra-repaired.c فقط همین تابع را تغییر داده است، و تست آن را با کد مبدأ روی 81 جفت ورودی مقایسه می‌کند.

grade

lifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
static const int lookup_14[5] = {1, 2, 3, 4, 4}; | uint grade(int param_1)
int grade(int param_1)                         | {
{                                              |   uint uVar1;
  int eax_1;                                   |   uint uVar2;
  int ecx_1;                                   |   
                                               |   uVar2 = param_1 / 10 - 6;
  ecx_1 = param_1 / 10 - 6;                    |   uVar1 = -(param_1 >> 0x1f) ^ (uint)((ulong)((long)param_1 * 0x66666667) >> 0x3f);
  eax_1 = 0;                                   |   if (uVar2 < 5) {
  if ((unsigned int)ecx_1 <= 4) {              |     uVar1 = *(uint *)(&DAT_001000b4 + (ulong)uVar2 * 4);
    eax_1 = lookup_14[(unsigned long)(unsigned int)ecx_1]; |   }
  }                                            |   return uVar1;
  return eax_1;                                | }
}                                              |

total

lifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
int total(int *param_1, int param_2)           | int total(long param_1,uint param_2)
{                                              | {
  int eax_1;                                   |   int iVar1;
  int ecx_1;                                   |   ulong uVar2;
  long rdx_1;                                  |   
                                               |   if (0 < (int)param_2) {
  if (param_2 <= 0) {                          |     uVar2 = 0;
    return 0;                                  |     iVar1 = 0;
  }                                            |     do {
  ecx_1 = param_2;                             |       iVar1 = iVar1 + *(int *)(param_1 + uVar2 * 4);
  rdx_1 = 0;                                   |       uVar2 = uVar2 + 1;
  eax_1 = 0;                                   |     } while (param_2 != uVar2);
  do {                                         |     return iVar1;
    eax_1 = eax_1 + param_1[rdx_1];            |   }
    rdx_1 = rdx_1 + 1;                         |   return 0;
  } while ((unsigned long)(unsigned int)ecx_1 != rdx_1); | }
  return eax_1;                                |
}                                              |

تست رفتاری، کد Ghidra را برای grade و total دست‌نخورده کامپایل می‌کند؛ صرفاً دو خط typedef و تعریف DAT_001000b4 از روی بیست بایت موجود در .rodata+0x14 به آن اضافه می‌شود. هر دو تابع روی شبکه‌ی ورودی‌ها با کد مبدأ تطابق دارند.

پژوهش‌ها درباره‌ی خواندن شبه‌کد چه می‌گویند؟

پژوهش LLM4Decompile (در EMNLP 2024) نرخ اجرای مجدد (Re-executability) نرم‌افزار Ghidra را روی HumanEval-Decompile به‌تنهایی 20.12 درصد ارزیابی کرد. یعنی تقریباً فقط یک تابع از هر پنج تابع مجدداً کامپایل شد و تست‌های بنچمارک را پاس کرد. ارتقای خروجی Ghidra با مدل 6.7B آن‌ها این رقم را به 52.74 درصد رساند. ارزیابی DecompileBench (در Findings of ACL 2025) شش دیکامپایلر صنعتی و شش رویکرد مبتنی بر LLM را روی 23400 تابع از 130 برنامه بررسی کرد. خروجی مدل‌های زبانی متن بهتری داشت، اما صحت عملکردی آن‌ها 52.2 درصد کمتر بود.

لیو، رف و میسینسکی (در arXiv 2609.05370، سپتامبر 2026) ریشه‌ی این شکاف را توضیح دادند. آن‌ها از 300 تابع کتابخانه‌ای گیت‌هاب و 287 تابع مبتنی بر CVE استفاده کردند. قوی‌ترین مدل ارتقادهنده، نرخ بیلد Ghidra را از 75 به 90 درصد رساند؛ اما نرخ تطابق رفتاری برنامه از 74 به 62 درصد سقوط کرد. گزینه‌هایی که تک‌تک تست‌های بنچمارک را پاس می‌کردند، روی ورودی‌های فازینگ (Fuzzing) رفتار متفاوتی نشان دادند. این انحراف در 4.9 درصد موارد روی هشت سیستم، و تا 13 درصد در یکی از سیستم‌ها رخ داد. تا یک‌دهم از آسیب‌پذیری‌های امنیتی افشاشده در میان کدهای اصلاح‌شده ناپدید شدند.

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

دقیقاً به همین دلیل است که لایه‌ی بالا کشیدن عبارت (unsigned long)(unsigned int)ecx_1 را به جای نامی شکیل‌تر چاپ می‌کند. این ابزار به جای اختراع ساختار switch برای پرش حل‌نشده، یادداشت می‌گذارد؛ و به جای اسمی که مدل خلق کند، برچسب دقیق lookup_14 را می‌نویسد. هر خط خروجی، استنتاجی دارد که می‌توانید در code/main.py دنبالش کنید. خروجی زشت undefined1 [16] در Ghidra در واقع صادقانه است. امضای ترتمیز int percent_change(int, int) در مدل‌های زبانی، تصادفاً و با دلایل غلط درست از آب درآمده؛ همین مدل در تابع بعدی، امضایی تمیز اما کاملاً اشتباه تحویل خواهد داد.

ساخت پروژه

کد دمو را اجرا کنید:

cd phases/13-tools-and-protocols/34-lifting-to-pseudocode
python3 code/main.py

دمو هر چهار تابع شیء -O1 را رمزگشایی کرده و تک‌تک دستورها را با متن commit شده‌ی llvm-objdump مقایسه می‌کند. برای سه تابع percent_change، grade و total، لایه‌ی IR قبل از SSA، خروجی SSA با توابع phi، و شبه‌کد را در کنار متن Ghidra چاپ می‌کند. سپس grade را با خاموش کردن تشخیص تقسیم، نسخه‌های -O0 از percent_change، total و grade_label، و در نهایت خلاصه‌ی وضعیت را نشان می‌دهد:

{
  "functions": ["grade", "grade_label", "percent_change", "total"],
  "instructions": 56,
  "blocks": {"percent_change": 3, "grade": 3, "total": 5, "grade_label": 4},
  "phis": {"percent_change": 0, "grade": 1, "total": 2, "grade_label": 1},
  "objdumpDifferences": 0
}

فایل code/main.py را به این ترتیب بخوانید:

1. تابع read_object() هدرهای بخش‌ها، جدول نمادها و بخش‌های .rela از یک فایل شیء ELF64 قابل بازآرایی را می‌خواند.
2. توابع decode_one() و render_att() یک دستور را رمزگشایی کرده و مثل llvm-objdump چاپ می‌کنند.
3. توابع build_blocks()، immediate_dominators() و dominance_frontiers() حقایق گراف را می‌سازند.
4. تابع lift_insn() یک دستور را به عبارات IR تبدیل کرده و بازآرایی‌ها را حل می‌کند.
5. توابع insert_phis() و rename() ساختار SSA را می‌سازند و تبدیل‌های عرض داده را اعمال می‌کنند.
6. توابع make_simplifier()، substitute_once() و remove_dead_code() درون optimize() اجرا می‌شوند.
7. توابع collect_params()، coalesce_webs() و infer_types() وب‌ها را نام‌گذاری و نوع‌دهی می‌کنند.
8. تابع structure() با کمک post_dominators() و natural_loops() بدنه‌ی C را تولید می‌کند.
9. تابع lift_function() مراحل را به هم وصل می‌کند و lift_all() کل فایل شیء را همراه با امضای توابع فراخوانده‌شده بالا می‌کشد.

استفاده از ابزار

برای بالا کشیدن یک تابع از شیء خودتان، ابتدا آن را با دستور clang -target x86_64-unknown-linux-gnu -c بیلد کنید و سپس lift_all(read_object(path)) را صدا بزنید. اگر دیکودر خطای DecodeError داد، بایت آپ‌کد را از پیام بخوانید و در نقشه‌ی آپ‌کد SDM پیدا کنید؛ بعد یک سطر به جدول‌های ابتدای فایل اضافه کنید. اگر لایه‌ی بالا کشیدن روی نام نمادی ارور داد، قاعده‌ای به lift_insn() اضافه کنید. اگر بخش ساختاربندی دستور goto تولید کرد، گراف را با IrPrinter چاپ کنید و ببینید جای کدام قاعده‌ی شکلی خالی است. هر تغییر کوچک است و فوراً با تست‌های موجود در برابر llvm-objdump یا clang سنجیده می‌شود.

اگر Ghidra نصب دارید، rea را روی همان تابع اجرا کنید و دو متن را کنار هم بگذارید. قبل از اعتماد به هر متن، جدول مغایرت‌ها را کامل کنید. تفاوتی که یک دستور اسمبلی پشت آن نشسته باشد، سلیقه در نمایش است؛ اما تفاوتی که هیچ دستور اسمبلی معادلی نداشته باشد یک حدس است، و این حدس می‌تواند از طرف هر یک از دو سیستم باشد.

کارگاه تعاملی

کارگاه A: یک تابع در طول پنج مرحله

از پوشه‌ی code، مفسر پایتون را باز کنید:

cd phases/13-tools-and-protocols/34-lifting-to-pseudocode/code
python3 -q

دستورات زیر را اجرا کنید:

from main import *
obj = read_object(FIXTURES / "ledger-x86_64-O1.o")
lifted = lift_function(obj, "percent_change")
for insn in lifted.decoded: print(f"0x{insn.address:x}: {insn.raw.hex(' ')}  {insn.att()}")
print(lifted.ir_text)
print(lifted.ssa_text)
print(lifted.pseudocode)

مسیر ثبات %esi را دنبال کنید: از subl %edi, %esi به esi_1 = esi_0 - edi_0 و سپس به (param_2 - param_1). بایت fe همان بایت ModR/M برای دستور subl است با mod = 11، reg = edi و r/m = esi.

کارگاه B: الگوی بهینه‌سازی تقسیم

print(lift_function(obj, "grade", recognize_division=False).pseudocode)
print(magic_divisor(0x66666667, 34), magic_divisor(0x66666667, 33), magic_divisor(0x66666667, 31))

خط اول ضرب و شیفت‌های خام را چاپ می‌کند. خط دوم خروجی 10 5 None را می‌دهد. بررسی کنید چرا همین ضریب با یک شیفت کمتر بر 5 تقسیم می‌کند، و چرا شیفت 31 از محدوده‌ی مجاز کران خطا رد می‌شود.

کارگاه C: توقف دیکودر در مواجهه با شیء جدید

فیکسچر را در سطح -O2 بسازید و آن را بالا بکشید:

clang -target x86_64-unknown-linux-gnu -O2 -fno-asynchronous-unwind-tables -c fixtures/ledger.c -o "$TMPDIR/ledger-O2.o"
python3 -c 'from main import *; from pathlib import Path; import os; lift_all(read_object(Path(os.environ["TMPDIR"]) / "ledger-O2.o"))'

دیکودر در آدرس 0x56 با پیام opcode 81 is outside the fixture subset متوقف می‌شود. آپ‌کد 81 فرم گروه 1 با یک مقدار فوری 32 بیتی است. دستور مورد نظر andl $0x7ffffff8, %edx است که clang در حلقه‌ی برداری‌شده‌ی تابع total به کار برده است. آن را در کنار 0x83 در تابع decode_one() اضافه کنید، تست را دوباره اجرا کنید و ببینید آپ‌کد بعدی که سد راه می‌شود چیست. زیرمجموعه‌ی تحت پوشش گام‌به‌گام اضافه می‌شود و هر ورودی در برابر llvm-objdump بررسی خواهد شد.

کارگاه D: مقدار پیش‌فرض Ghidra در تابع grade

print(ghidra_pseudocode("grade"))
for score in (-25, 0, 59, 60, 100, 115):
    sign = -(score >> 31)
    product_sign = ((score * 0x66666667) & ((1 << 64) - 1)) >> 63
    print(score, sign ^ product_sign)

تمام سطرها عدد 0 چاپ می‌کنند. عبارت uVar1 در Ghidra در عین درستی، ناخواناست؛ در حالی که دستور xorl %eax, %eax همین را در دو بایت بیان کرده است.

تمرین عملی

بازیابی ساختار switch را برای تابع grade در سطح -O0 پیاده‌سازی کنید.

نیازمندی‌ها:

• پنج بازآرایی موجود در .rela.rodata از فایل ledger-x86_64-O0.o (که هرکدام به فرم R_X86_64_PC32.text+offset هستند) را بخوانید و پنج مقصد case را از روی جدول در .rodata+0x0 محاسبه کنید.
• ساختار پایان‌دهنده‌ی Switch را به عبارات IR اضافه کنید که شامل عبارت اندیس، لیست مقاصد، و مقصد default برگرفته از پرش ja پیش از بارگذاری جدول باشد.
• به بلوک switch به ازای هر مقصد یک یال جانشین بدهید تا الگوریتم‌های مسلط‌ها، پس‌مسلط‌ها و SSA درست کار کنند.
• خروجی را به فرم switch (local_10) { case 0:... } با یک برچسب case برای هر مقصد و یک بخش مشترک بعد از پیوند شاخه‌ها چاپ کنید.
• اگر با پرش غیرمستقیمی روبرو شدید که جدولش قابل تحدید نیست، همان یادداشت را نگه دارید.
• نتیجه را با clang کامپایل کرده و آن را در تست‌ها روی شبکه‌ی نمرات در برابر کد مبدأ مقایسه کنید.

موفقیت یعنی grade در سطح -O0 و -O1 روی کل شبکه‌ی ورودی‌ها خروجی یکسانی تولید کنند؛ با یک دستور switch و بدون هیچ goto.

تمرین نمره‌دار

پنج سؤال درباره‌ی فیکسچرهای این درس آماده شده است. با کدی که ساخته‌اید پاسخ‌ها را بیابید و در code/lab_answers.json بنویسید. اعداد را به‌صورت عدد یا رشته‌های هگز مانند "0x40"، و لیست‌ها را به‌صورت آرایه‌های JSON وارد کنید.

1. t1: پارامترهایی که قرارداد فراخوانی در سطح -O1 به percent_change اختصاص می‌دهد.
2. t2: توابع phi موجود در فرم SSA تابع total در سطح -O1.
3. t3: مقسوم‌علیهی که magic_divisor برای مقدار 0x66666667 همراه با شیفت 34 به دست می‌آورد.
4. t4: آخرین عبارت شبه‌کد percent_change در سطح -O1 به‌صورت یک خط متن.
5. t5: نوع زبان C بازیابی‌شده برای param_1 در تابع total در سطح -O1.

پاسخ‌هایتان را ارزیابی کنید:

cd phases/13-tools-and-protocols/34-lifting-to-pseudocode
python3 code/lab.py

ارزیاب، پاسخ‌های مورد انتظار را با اجرای مستقیم code/main.py روی فیکسچرهای commit شده استخراج می‌کند. برای هر سؤال یکی از وضعیت‌های PASS، FAIL یا TODO را به همراه نمره چاپ می‌کند، و فقط وقتی همه‌ی پنج بخش پاس شوند با کد 0 خارج می‌شود. با دستور python3 code/lab.py my-answers.json می‌توانید فایل‌های دیگر را ارزیابی کنید. تست code/tests/test_lab.py نشان می‌دهد که ارزیاب، پاسخ‌های درست را قبول و موارد غلط را رد می‌کند.

مشاهده‌ی اجرا

ماشین Inside a Decompiler این درس را در قالب مراحل پرس بالا کشیدن، پین‌های تعیین نوع، شابلون ساختاربندی و چاپگر، به همراه IR، SSA و شبه‌کد حاصل از code/main.py اجرا می‌کند. پیوند بالا فایل شیء سطح -O0 را باز می‌کند: سه اسلات استک به متغیرهای محلی تبدیل می‌شوند و شابلون، هر دو فک ساختار if/else را می‌بندد.

خروجی کار

این درس مستند outputs/skill-lifting-to-pseudocode.md را تولید می‌کند. از این سند برای بالا کشیدن یک تابع همراه با استنتاج مستندِ خط‌به‌خط و پر کردن جدول تفاوت‌ها در برابر متن دیکامپایلر استفاده کنید. این خروجی نیازمند دیس‌اسمبلی مرجع، بازآرایی‌ها، قرارداد فراخوانی، بررسی کامپایل، ارزیابی رفتاری و یک تحلیل دقیق برای هر خطِ مغایر است.

اعتبارسنجی نهایی

دمو و آزمون‌های قطعی را اجرا کنید:

cd phases/13-tools-and-protocols/34-lifting-to-pseudocode
python3 code/main.py
python3 -m unittest discover -s code/tests -v

این مجموعه 25 تست دارد. فرآیند ارزیابی موارد زیر را اثبات می‌کند:

• دیکودر بر سر تک‌تک دستورهای هر دو شیء با متن ثبت‌شده‌ی llvm-objdump (و همچنین در صورت نصب بودن، با اجرای زنده‌ی آن) توافق دارد.
• بایت‌های REX، ModR/M، SIB و آفست فیلد جابه‌جایی در leaq (%rip), %rcx طبق توضیحات راهنمای SDM رمزگشایی می‌شوند.
• مواجهه با هر آپ‌کد خارج از زیرمجموعه، به جای حدس زدن، خطای DecodeError می‌دهد.
• ماژول ELF هر چهار تابع و سه بازآرایی بخش .text را فهرست می‌کند.
• تابع total پنج بلوک دارد، 0x44 بر 0x50 مسلط است، و 0x50 سربرگ حلقه‌ای است که بدنه‌اش خود همان بلوک است.
• ثبات‌های %rdi و %rsi تبدیل به param_1 و param_2 می‌شوند، و param_1 در total از نوع int * است.
• ترکیب test و cmp با شروط je، jle، ja و jge به ترتیب به ==، <=، > (بدون علامت) و < تبدیل می‌شوند.
• ساختار SSA دو تابع phi فعال در سربرگ حلقه‌ی total قرار می‌دهد و در percent_change هیچ تابع phi نمی‌گذارد.
• شبه‌کد خروجی برای percent_change، grade و total دقیقاً با متن مورد انتظار برابر است.
• تابع grade با فعال بودن تشخیص الگو عبارت param_1 / 10 - 6، و با خاموش بودن آن محاسبات خام ضرب را چاپ می‌کند.
• ضریب 0x66666667 با شیفت 34 بر 10 و با شیفت 33 بر 5 تقسیم می‌کند، و هم‌ارزی روی دامنه‌ی ورودی‌ها برقرار است.
• اسلات‌های استک در سطح -O0 تبدیل به local_4، local_8 و local_c می‌شوند و اثری از اشاره‌گر فریم باقی نمی‌ماند.
• جدول موجود در .rodata+0x14 با تکیه بر بازآرایی، مقادیر 1, 2, 3, 4, 4 را برمی‌گرداند.
• پرش غیرمستقیم در grade سطح -O0 همراه با چهار بلوک تبدیل‌نشده‌اش گزارش می‌شود.
• فیکسچرهای Ghidra مقدار بازگشتی 16 بایتی، param_3، عبارت ساده‌نشده‌ی xor و long param_1 را در بر دارند.
• هر شش واحد کامپایل با دستور clang -std=c11 -Wall -Werror برای x86_64-unknown-linux-gnu بدون خطا کامپایل می‌شوند.
• توابع بالا کشیده شده، کد اصلاح‌شده‌ی Ghidra و کد مبدأ، 232 خط خروجی کاملاً یکسان روی شبکه‌ی مقادیر ورودی تولید می‌کنند.

حالت‌های شکست در محیط واقعی

دستورالعمل اجرایی

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

برای مطالعه‌ی بیشتر

• Intel SDM Volume 2, chapter 2, Instruction Format
• System V AMD64 psABI, section 3.2, Function Calling Sequence
• Cytron et al., Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, TOPLAS 1991
• Cooper, Harvey, Kennedy, A Simple, Fast Dominance Algorithm, 2001
• Cifuentes, Reverse Compilation Techniques, PhD thesis, QUT 1994
• Yakdan et al., No More Gotos, NDSS 2015
• Granlund, Montgomery, Division by Invariant Integers using Multiplication, PLDI 1994
• Lee, Avgerinos, Brumley, TIE, NDSS 2011
• Noonan, Loginov, Cok, Polymorphic Type Inference for Machine Code, PLDI 2016
• LLM4Decompile, EMNLP 2024
• DecompileBench, Findings of ACL 2025
• Liu, Raff, Micinski, When LLM Decompilers Recompile More and Preserve Less, 2026
• rea 6.5.0 Ghidra provider notes
• سورس‌کد rea 6.5.0 در تگ 3b79af2 که این درس شرح می‌دهد: src/domain/functionComparisonDimensions.ts و website/evidence/dx-ball-sound-pan.md.