بازیابی داده‌ها و ساختار نوع‌ها: استراکت‌ها، آرایه‌ها، اشیاء ++C و DWARF 5

در مهندسی معکوس فایل‌های باینری فاقد نمادهای خطایابی (Stripped)، تحلیل‌گر همواره با عباراتی گنگ و خام مانند `*(int *)(param_1 + 4)` در دکامپایلر مواجه می‌شود؛ عباراتی که فهم جریان منطقی برنامه را بسیار زمان‌بر و طاقت‌فرسا می‌کنند. تفاوت یک کد خوانا نظیر `a->balance` با دسترسی‌های خام حافظه، صرفاً در وجود جدولی از تعریف نوع‌ها (Type table) نهفته است.

در این درس یاد می‌گیرید چگونه با ردیابی سیستماتیک آفست‌ها، عرض عملوندها و الگوهای تکرار در دستورالعمل‌های اسمبلی، جدول نوع‌ها، اندازه‌ی اعضای ساختار (Struct) و گام‌های پرش آرایه را دقیقاً استخراج کنید. سپس با تحلیل استاندارد DWARF 5 در فایل‌های کامپایل‌شده، حقایق قطعی اثبات‌شده توسط اسمبلی را در برابر تعاریف رسمی کامپایلر قرار می‌دهید و چیدمان اشیاء ++C و جدول توابع مجازی (vtable) را ارزیابی می‌کنید.

دکامپایلر وقتی جدول نوع‌ها (Type table) را داشته باشد عبارت a->balance را چاپ می‌کند و وقتی آن را نداشته باشد، *(int *)(param_1 + 4) را تحویل می‌دهد. در این درس، این جدول را بر اساس الگوهای دسترسی بازسازی می‌کنیم، جدول واقعی را مستقیماً از DWARF 5 می‌خوانیم و نشان می‌دهیم این دو کجا بر هم منطبق می‌شوند.

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

• دسترسی به اعضای ساختار (Struct) را بر مبنای قواعد آدرس‌دهی Intel SDM به‌صورت «رجیستر مبنا به‌علاوه‌ی جابه‌جایی» (Displacement)، و دسترسی به آرایه را به‌صورت «مبنا به‌علاوه‌ی اندیس ضرب‌در استراید (گام لغزش)» تحلیل کنید.
• قواعد هم‌ترازی (Alignment) استاندارد System V را به‌صورت دستی روی struct account پیاده کنید و دلیل تک‌تک بایت‌های پدینگ (حاشیه‌گذاری) را توضیح دهید.
• یک گذر بازسازی نوع (Type-recovery pass) بسازید که دسترسی‌های موجود در فهرست دیس‌اسمبلی را همراه با شواهد (Evidence) هر مورد، به آفست فیلدها، عرض، انواع داده، یک استراید و اندازه‌ی نهایی تبدیل کند.
• یک خواننده‌ی DWARF 5 برای بخش‌های .debug_info، .debug_abbrev، .debug_str_offsets و .debug_addr یک فایل شیء بازتخصیص‌پذیر بنویسید و خروجی آن را با llvm-dwarfdump بسنجید.
• چیدمان بازسازی‌شده را با چیدمان DWARF مقایسه کنید و هر تفاوت را با یکی از برچسب‌های «فقدان شواهد»، «دسترسی ادغام‌شده» یا «نوع اثبات‌ناپذیر» مشخص نمایید.
• ساختار جدول متدهای مجازی (vtable) در استاندارد Itanium C++، اطلاعات نوع زمان اجرا (Typeinfo) و نام‌های تغییریافته (Mangled names) را از روی بازتخصیص‌ها (Relocations) بخوانید و یک فراخوانی مجازی را به اسلات متناظرش منتسب کنید.

صورت مسئله

کد account.c را بدون فلگ -g کامپایل کرده‌اید و از یک ایجنت (Agent) پرسیده‌اید تابع bump چه کاری انجام می‌دهد. ایجنت فایل کامپایل‌شده را به Ghidra 12.1.4 فرستاده و این خروجی را گرفته است:

void bump(long param_1,int param_2)
{
  *(int *)(param_1 + 4) = param_2 + *(int *)(param_1 + 4);
  return;
}

همین کد منبع اگر با فلگ -g کامپایل شود، خروجی همان دکامپایلر چنین خواهد بود:

int bump(account *a,int by)
{
  a->balance = by + a->balance;
  return a->balance;
}

دستورالعمل‌ها در هر دو فایل کاملاً یکسان‌اند؛ تنها تفاوت، وجود جدول نوع‌هاست. با داشتن این جدول، دکامپایلر می‌داند پارامتر اول به ساختاری 32 بایتی اشاره دارد که فیلد آن در آفست 4، یک int چهار بایتی به نام balance است. بدون آن، دکامپایلر فقط می‌داند داده‌ای 8 بایتی در رجیستر %rdi دریافت شده و 4 بایت در آفست +4 خوانده و نوشته شده است.

تک‌تک داده‌های آن جدول منبع مشخصی دارند: آفست 4 از بایت جابه‌جایی در دستور addl 0x4(%rax), %ecx می‌آید؛ عرض 4 بایتی از پسوند l استخراج می‌شود؛ نام فیلد هم از یک مدخل DW_TAG_member در بخش .debug_info می‌آید. در این درس هر دو نیمه را می‌سازیم: گذری که حقایق اثبات‌شده توسط دستورالعمل‌ها را بازسازی می‌کند، و خواننده‌ای که ثبت‌شده‌های کامپایلر را رمزگشایی (Decode) می‌نماید. فاصله‌ی میان این دو، هزینه‌ای است که برای داشتن نام نوع‌ها می‌پردازیم.

دسترسی به عضو ساختار همان جابه‌جایی است

جلد اول راهنمای توسعه‌دهندگان اینتل (Intel SDM)، بخش 3.7.5، آدرس مؤثر را به‌صورت Offset = Base + (Index * Scale) + Displacement تعریف می‌کند؛ با مقیاس (Scale) برابر با 1، 2، 4 یا 8 و جابه‌جایی (Displacement) برابر با 8، 16 یا 32 بیت. بخش 3.7.5.1 حالت 64 بیتی آن یعنی RIP + Displacement را اضافه می‌کند. دسترسی به عضو ساختار از فرم اول بدون عبارت اندیس استفاده می‌کند: رجیستر مبنا آدرس شیء را نگه می‌دارد و جابه‌جایی، همان آفست عضو ساختار است. دسترسی به آرایه، عبارت اندیس را اضافه می‌کند که در آن مقیاس یا یک عمل ضرب جداگانه، اندازه‌ی هر عنصر را تعیین می‌نماید.

تابع bump را در سطح بهینه‌سازی -O0 در نظر بگیرید. خروجی llvm-objdump -d -r چنین است:

       4: 48 89 7d f8                  	movq	%rdi, -0x8(%rbp)
       e: 48 8b 45 f8                  	movq	-0x8(%rbp), %rax
      12: 03 48 04                     	addl	0x4(%rax), %ecx
      15: 89 48 04                     	movl	%ecx, 0x4(%rax)

بایت‌های 03 48 04 را با قواعد درس 33 رمزگشایی کنید. 03 یعنی ADD r32, r/m32. بایت ModRM با مقدار 48 برابر است با 01 001 000: بخش mod = 01 یعنی عملوند حافظه با یک جابه‌جایی 8 بیتی، reg = 001 رجیستر %ecx و r/m = 000 رجیستر %rax است. بایت جابه‌جایی 04 است. این دستورالعمل، 4 بایت را در آدرس %rax + 4 می‌خواند و آن را با %ecx جمع می‌کند. پسوند l در خروجی llvm-objdump اندازه‌ی عملوند را نشان می‌دهد، بنابراین این فیلد 4 بایت عرض دارد. مقدار %rax از اسلات فریم در -0x8(%rbp) آمده است، و آن اسلات هم مقدار رجیستر %rdi (اولین آرگومان عدد صحیح طبق قرارداد فراخوانی System V) را دریافت کرده بود. از این تحلیل سه واقعیت به‌دست می‌آید: پارامتر اول یک اشاره‌گر است، شیئی که به آن اشاره می‌کند یک فیلد 4 بایتی در آفست 4 دارد، و تابع bump آن فیلد را می‌خواند و می‌نویسد.

هیچ‌کدام از این بایت‌ها نامی از int، balance یا struct account نمی‌آورند. هیچ داده‌ای هم اندازه‌ی این شیء را مشخص نمی‌کند. 28 بایت باقی‌مانده‌ی ساختار برای تابع bump کاملاً نامرئی است.

قواعد چیدمان System V

سند x86-64 psABI در بخش 3.1.2 سه قانون برای انواع داده‌ی مرکب (Aggregates) بیان می‌کند: «ساختارها و یونیون‌ها، هم‌ترازی سخت‌گیرانه‌ترین مؤلفه‌ی خود را دریافت می‌کنند. هر عضو به کمترین آفست در دسترس با هم‌ترازی مناسب اختصاص می‌یابد. اندازه‌ی هر شیء همیشه مضربی از هم‌ترازی خود آن شیء است.» شکل 3.1 همان سند، اندازه و هم‌ترازی انواع اسکالر را مشخص می‌کند: char دارای اندازه و هم‌ترازی 1 و 1، short برابر 2 و 2، int برابر 4 و 4، double برابر 8 و 8، و هر اشاره‌گری برابر 8 و 8.

این قواعد را روی ساختار موجود در account.c پیاده کنید:

struct account {
    char kind;
    int balance;
    short code;
    double rate;
    const char *label;
};

آخرین عضو در آفست 32 تمام می‌شود. سخت‌گیرانه‌ترین هم‌ترازی 8 است و 32 بر 8 بخش‌پذیر است؛ بنابراین اندازه بدون نیاز به پدینگ انتهایی برابر 32 می‌شود. از این 32 بایت، 9 بایت پدینگ است و psABI صراحتاً می‌گوید «محتوای پدینگ تعریف‌نشده است».

ترتیب چیدمان اعضا، اندازه‌ی نهایی را تعیین می‌کند. اگر همین پنج عضو را به‌ترتیب double, pointer, int, short, char مرتب کنیم، آفست‌های 0، 8، 16، 20 و 22 را پر کرده و در آفست 23 تمام می‌شوند که به بالا گرد شده و 24 می‌شود. تابع sysv_layout() در فایل code/main.py این سه قانون را اعمال کرده و هر دو نتیجه را تولید می‌کند. ماژول ctypes پایتون هم همین قواعد را از طریق قرارداد کامپایلر میزبان پیاده می‌کند؛ توابع ctypes.sizeof، ctypes.alignment و خصوصیت .offset هر فیلد برای همین ساختار، به‌ترتیب مقادیر 32، 8 و مقادیر 0, 4, 8, 16, 24 را بازمی‌گردانند. خود برنامه نیز با کامپایل و اجرا روی این ماشین، نسخه‌ی سوم را چاپ می‌کند:

sizeof 32 align 8
kind 0 balance 4 code 8 rate 16 label 24
sum 315 tag -3 projected 318.75 label_length 7

این بیلد بومی روی معماری arm64 است. سند Arm AAPCS64 در بخش 5.10.1 همین قوانین داده‌های مرکب را آورده و مستندات arm64 اپل نیز اندازه‌ی این پنج نوع اسکالر را یکسان نگه می‌دارد؛ بنابراین اعداد روی هر دو تارگت بر هم منطبق‌اند. فایل‌های شیء x86-64 این درس با فلگ -target x86_64-unknown-linux-gnu کامپایل شده‌اند تا خواننده‌ی ELF درس 33 و خواننده‌ی DWARF در ادامه بتوانند روی آن‌ها کار کنند.

بازخوانی دستی سایر بخش‌های ساختار

تابع bump فقط یک فیلد را می‌بیند. چهار تابع دیگر در account.c بقیه‌ی فیلدها را بررسی می‌کنند و هرکدام شکل متفاوتی از دستورالعمل‌ها را به نمایش می‌گذارند. تمام آدرس‌های زیر از account-x86_64-O0-g.objdump.txt برداشته شده‌اند.

تابع sum_balances روی آرایه‌ای از این ساختار اندیس می‌زند:

      51: 48 8b 45 f8                  	movq	-0x8(%rbp), %rax
      55: 48 63 4d ec                  	movslq	-0x14(%rbp), %rcx
      59: 48 c1 e1 05                  	shlq	$0x5, %rcx
      5d: 48 01 c8                     	addq	%rcx, %rax
      60: 8b 40 04                     	movl	0x4(%rax), %eax

رجیستر %rax نشان‌دهنده‌ی list است، رجیستر %rcx همان متغیر i با گسترش علامت (Sign-extended) به 64 بیت است، و دستور shlq $0x5 آن را در 32 ضرب می‌کند. پس از اجرای addq، مقدار %rax برابر با list + 32 * i می‌شود و عمل بارگذاری (Load)، 4 بایت را از آفست 4 در عنصر i می‌خواند. تعداد بیت شیفت (Shift count) تنها جایی در این فایل شیء است که اندازه‌ی ساختار به‌صورت یک عدد صریح دیده می‌شود. حلقه‌ای که شامل این دستورالعمل‌هاست از آدرس 0x49 تا jmp 0x49 در آدرس 0x72 اجرا می‌شود.

تابع tag دو فیلد کم‌عرض را می‌خواند:

      8c: 0f be 00                     	movsbl	(%rax), %eax
      98: 0f bf 48 08                  	movswl	0x8(%rax), %ecx

دستور movsbl یک بایت را از آفست 0 می‌خواند و آن را با علامت گسترش می‌دهد؛ بنابراین فیلد موجود در آفست 0 یک عدد صحیح 1 بایتی علامت‌دار است. دستور movswl دو بایت را از آفست 8 با گسترش علامت بارگذاری می‌کند، پس فیلد موجود در آفست 8 یک عدد صحیح 2 بایتی علامت‌دار است. در سطح بهینه‌سازی -O1، دسترسی اول به cmpb $0x6c, (%rdi) تبدیل می‌شود که همچنان نشان‌دهنده‌ی 1 بایت در آفست 0 است اما درباره‌ی علامت‌دار بودن آن چیزی نمی‌گوید.

تابع projected یک مقدار ممیز شناور را می‌خواند:

      cc: f2 0f 2a 40 04               	cvtsi2sdl	0x4(%rax), %xmm0
      d5: f2 0f 59 40 10               	mulsd	0x10(%rax), %xmm0

دستور cvtsi2sdl یک عدد صحیح 32 بیتی علامت‌دار را از حافظه به double تبدیل می‌کند، که تأیید می‌کند آفست 4 حاوی یک عدد صحیح علامت‌دار 4 بایتی است. دستور mulsd عمل ضرب را با یک مقدار double از حافظه انجام می‌دهد، پس آفست 16 یک مقدار ممیز شناور 8 بایتی را نگه می‌دارد.

تابع label_length یک اشاره‌گر را می‌خواند و سپس به آدرس آن می‌رود (Dereference):

      f3: 48 8b 40 18                  	movq	0x18(%rax), %rax
      f7: 48 63 4d f4                  	movslq	-0xc(%rbp), %rcx
      fb: 80 3c 08 00                  	cmpb	$0x0, (%rax,%rcx)

دستور movq مقدار 8 بایت را از آفست 24 می‌خواند. این مقدار به‌تنهایی می‌تواند یک عدد صحیح 8 بایتی یا یک اشاره‌گر باشد. دستور cmpb از مقدار بارگذاری‌شده به‌عنوان مبنای عملوند حافظه استفاده می‌کند؛ مقداری هم که به‌عنوان آدرس استفاده شود، قطعاً اشاره‌گر است. دستور cmpb یک بایت را در اندیس %rcx از آن می‌خواند، و در بهینه‌سازی -O1 اشاره‌گر با دستور leaq 0x1(%rcx), %rcx درون حلقه جلو برده می‌شود؛ بنابراین عناصر مورد اشاره 1 بایت از هم فاصله دارند.

با تجمیع این پنج تابع، ساختار به دست می‌آید: { i8 at 0, i32 at 4, i16 at 8, f64 at 16, pointer at 24 } با استراید 32. فضاهای خالی در 1 تا 3 و 10 تا 15 دقیقاً همان پدینگی هستند که قواعد psABI پیش‌بینی کرده بود. چیزهایی که دستورالعمل‌ها نشان نمی‌دهند: نام اعضا، این‌که اشاره‌گر از نوع const char * است، نوع اعلام‌شده‌ی بایت علامت‌دار در آفست 0 که در کد منبع char تعریف شده، و این واقعیت که هر پنج تابع یک نوع داده‌ی یکسان دریافت می‌کنند. ادعای آخر از تابع main سرچشمه می‌گیرد که یک شیء فریم یکسان را به هر پنج تابع ارسال می‌کند. در سطح -O0، نقاط فراخوانی (Call sites) این موضوع را آشکار می‌کنند: دستور leaq -0x70(%rbp), %rdi و به‌دنبال آن addq $0x20, %rdi قبل از callq bump، و addq $0x40, %rdi قبل از callq tag. آفست‌های 0، 0x20 و 0x40 سه عنصر از یک آرایه‌اند و دستور memcpy با مقدار 0x60 بایت که آن را پر می‌کند، 96 بایت یعنی دقیقاً سه عنصر 32 بایتی است.

گذر تحلیل

تابع trace_function() در فایل code/main.py دستورالعمل‌های هر تابع را به‌ترتیب آدرس پیمایش کرده و یک وضعیت انتزاعی کوچک را نگه‌داری می‌کند. یک نگهدارنده (Holder) می‌تواند یک رجیستر 64 بیتی یا یک اسلات فریم مانند -0x8(%rbp) باشد. هر نگهدارنده یکی از سه مقدار ممکن را می‌گیرد: یک Pointer شامل یک ریشه به‌علاوه‌ی آفست ثابت و مجموعه‌ای از استرایدها است (که استراید نشان می‌دهد مضرب نامعلومی از چند بایت به آن اضافه شده است). یک Index یک عدد صحیح با مقدار نامشخص است که مضربی از یک مقیاس معین است. هر حالت دیگری معادل هیچ (Nothing) خواهد بود.

وضعیت اولیه با شش رجیستر آرگومان در System V شروع می‌شود که مقادیر Pointer("param0", 0) تا Pointer("param5", 0) را در خود دارند. سپس هر دستورالعمل یک قانون را اعمال می‌کند:

• دستور movq بین رجیستر 64 بیتی و اسلات فریم، مقدار را کپی می‌کند. نوشتن یک مقدار 32 بیتی یا کم‌عرض‌تر در یک رجیستر، آن را تبدیل به یک Index با مقیاس 1 می‌کند.
• دستور leaq با مبنای اشاره‌گر، اشاره‌گری با جابه‌جایی اضافه‌شده تولید می‌کند؛ و با یک رجیستر اندیس، مقدار scale * index_scale را به استرایدها می‌افزاید. اگر مبنای leaq رجیستر %rbp یا %rsp باشد، به یک شیء روی فریم اشاره دارد که تابع main از همین طریق rows را ارسال می‌کند.
• دستور shlq $n روی یک Index مقیاس آن را در 2^n ضرب می‌کند و imulq $k آن را در k ضرب می‌نماید.
• دستور addq روی اشاره‌گر و اندیس، اشاره‌گر را حفظ کرده و مقیاس اندیس را به استرایدها اضافه می‌کند. دستور addq $k روی اشاره‌گر، آفست آن را تغییر داده و به‌عنوان افزایش (Increment) آن رجیستر ثبت می‌شود.
• فراخوانی یک تابع باعث می‌شود مقدار تمام رجیسترهای caller-saved نامشخص شود، و رجیسترهای آرگومان حاوی اشاره‌گر به‌عنوان یک نقطه‌ی فراخوانی ثبت می‌گردند.
• هر عملوند حافظه که رجیستر مبنای آن یک اشاره‌گر باشد تبدیل به یک Access می‌شود که شامل ریشه و آفست اشاره‌گر، عرض و نوع داده برگرفته از کد دستور (Mnemonic)، و یک پرچم نوشتن (Store flag) است.

عرض و نوع داده صرفاً از روی خود کد دستور به دست می‌آیند. تابع access_width() پسوندهای b، w، l و q را به 1، 2، 4 و 8 بایت نگاشت می‌کند؛ movsbl و movswl را به بارهای علامت‌دار کم‌عرض، movzbl را به بارگذاری بدون علامت، دستورات اسکالر SSE یعنی sd و ss را به ممیز شناورهای 8 و 4 بایتی، cvtsi2sdl را به مبدأ عدد صحیح 4 بایتی علامت‌دار، و خانواده‌ی 16 بایتی movaps را به بردار نگاشت می‌دهد. دستورات leaq و انواع nop دسترسی به حساب نمی‌آیند.

if memory.base in FRAME_REGISTERS:
    return Pointer(f"frame({memory.base}{format_signed(memory.displacement) if memory.displacement else ''})", 0)
base = env.get(memory.base)
if not isinstance(base, Pointer):
    return Unknown
strides = set(base.strides)
if memory.index is not None:
    index_value = env.get(memory.index)
    strides.add((index_value.scale if isinstance(index_value, Index) else 1) * memory.scale)
return Pointer(base.root, base.offset + memory.displacement, frozenset(strides), base.origin)

بارگذاری 8 بایت از طریق یک اشاره‌گر، اشاره‌گر جدیدی تولید می‌کند که ریشه‌ی آن نام فیلد منبع را مشخص می‌کند؛ مانند param0->0x18. اگر بعداً از این مقدار به‌عنوان مبنا استفاده شود یا با leaq افزایش یابد، فیلد منبع آن به‌عنوان یک اشاره‌گر اثبات‌شده علامت‌گذاری می‌شود. این همان قاعده‌ای است که آفست 24 را از «8 بایت» به «اشاره‌گر» تبدیل می‌کند.

چهار دسته‌بندی از شواهد استراید

تابع infer_layout() دسترسی‌های همه‌ی توابع شاهد را ادغام کرده و استراید را از چهار منبع، هرکدام همراه با دستورالعملی که آن را ایجاد کرده، گردآوری می‌کند.

یک حلقه با یک jmp رو به عقب یا پرش شرطی مشخص می‌شود، و مقدار افزایش رجیستر فقط زمانی معتبر است که محدوده‌ی حلقه هم افزایش و هم دسترسی را در بر بگیرد. این قاعده مانع از احتساب addl $0x1, %eax می‌شود که در -O0 متغیر i را جلو می‌برد، زیرا این یک جمع 32 بیتی است و دسترسی نیز از طریق رجیستر %eax انجام نمی‌شود. استراید نهایی برابر با بزرگ‌ترین مقسوم‌علیه مشترک (ب.م.م) تمام مقادیر کشف‌شده است. اگر استراید حداقل به بزرگی پایان آخرین فیلد باشد، به‌عنوان اندازه‌ی ساختار در نظر گرفته می‌شود.

حلقه‌ی برداری‌شده در سطح -O2

در سطح -O2 کامپایلر clang حلقه‌ی sum_balances را برداری (Vectorize) می‌کند. بدنه‌ی حلقه از آدرس 0x50 تا 0xaa در هر پیمایش، هشت عنصر را می‌خواند:

      3b: 48 8d 87 e4 00 00 00         	leaq	0xe4(%rdi), %rax
      50: 66 0f 6e 50 80               	movd	-0x80(%rax), %xmm2
      55: 66 0f 6e 98 60 ff ff ff      	movd	-0xa0(%rax), %xmm3
      61: 66 0f 6e 90 40 ff ff ff      	movd	-0xc0(%rax), %xmm2
      69: 66 0f 6e a0 20 ff ff ff      	movd	-0xe0(%rax), %xmm4
      7d: 66 0f 6e 10                  	movd	(%rax), %xmm2
      81: 66 0f 6e 58 e0               	movd	-0x20(%rax), %xmm3
      8a: 66 0f 6e 50 c0               	movd	-0x40(%rax), %xmm2
      8f: 66 0f 6e 60 a0               	movd	-0x60(%rax), %xmm4
      a0: 48 05 00 01 00 00            	addq	$0x100, %rax
      aa: 75 a4                        	jne	0x50 <sum_balances+0x40>

رجیستر %rax از آدرس list + 0xe4 شروع می‌شود. هشت جابه‌جایی مختلف، عمل بارگذاری را در آفست‌های 0x04, 0x24, 0x44, 0x64, 0x84, 0xa4, 0xc4, 0xe4 نسبت به list قرار می‌دهند که برابر با 4, 36, 68, 100, 132, 164, 196, 228 است. گام افزایش برابر با 0x100 یعنی 256 است. تحلیلی که آفست‌ها را بدون بررسی ساختار حلقه ثبت کند، هشت فیلد و ساختاری حداقل 232 بایتی گزارش می‌دهد. متن دیس‌اسمبلی درست است اما نتیجه‌گیری اشتباه خواهد بود.

تابع fold_unrolled() یک قانون ساده را پیاده می‌کند: درون یک حلقه، دسترسی‌های هم‌عرض از طریق یک رجیستر مبنا را در نظر بگیرید. آفست‌های آن‌ها به‌اندازه‌ی d با هم فاصله دارند (در اینجا 32). اگر گام حلقه برابر با k * d باشد و دقیقاً k آفست متمایز وجود داشته باشد، این حلقه k بار باز (Unroll) شده است و هر دسترسی در واقع دسترسی به همان عنصر در آفست (offset - lowest) mod d است. در اینجا 256 = 8 * 32 با هشت آفست داریم؛ بنابراین تمام این هشت بارگذاری روی آفست 4 ادغام (Fold) می‌شوند و شواهد استراید مقادیر offset-delta 32، unrolled 32 و loop-step 256 را ثبت می‌کنند. حلقه‌ی باقیمانده‌ی اسکالر در آدرس 0xe0 مقادیر scale 32 حاصل از shlq $0x5, %rdx و loop-step 32 از addq $0x20, %rdx را اضافه می‌کند. بزرگ‌ترین مقسوم‌علیه مشترک هر پنج مقدار برابر با 32 است.

در تصویر تعاملی دکمه‌ای برای خاموش کردن این ادغام تعبیه شده است. بدون آن، بیلد -O2 هفت فیلد فراتر از بایت 32 را نشان می‌دهد و هیچ اندازه‌ای شناسایی نمی‌کند. این حالت دقیقاً همان وضعیتی است که در صورت اعتماد به مقادیر جابه‌جایی بدون تحلیل حلقه پیش می‌آید.

استخراج DWARF 5 از بایت‌ها

بیلد -g فایل account.c هشت بخش دیباگ دارد: بخش .debug_info برابر 493 بایت، .debug_abbrev برابر 179، .debug_str برابر 230، .debug_str_offsets برابر 124، .debug_addr برابر 112، .debug_line برابر 312، .debug_line_str برابر 12 و .debug_frame برابر 264 بایت است. در مقدمه‌ی استاندارد DWARF 5 ذکر شده که بخش‌های .debug_str_offsets، .debug_addr و .debug_line_str در نسخه‌ی 5 جدید هستند. خواننده‌ی موجود در code/main.py به پنج بخش اول نیاز دارد.

هدر واحد کامپایل

بخش 7.5.1.1 استاندارد، هدر کامل واحد کامپایل (Compilation Unit Header) را به این شکل معرفی می‌کند: unit_length، version، unit_type، address_size و debug_abbrev_offset. دوازده بایت اول .debug_info به‌صورت زیر است:

e9 01 00 00   unit_length = 0x1e9 = 489
05 00         version = 5
01            unit_type = DW_UT_compile
08            address_size = 8
00 00 00 00   debug_abbrev_offset = 0

بایت unit_type در نسخه‌ی 5 اضافه شده و استاندارد در همان بخش این موضوع را توضیح داده است. طول واحد، تعداد بایت‌های بعد از خود فیلد طول را می‌شمارد؛ بنابراین واحد بعدی در 4 + 489 = 493 یعنی انتهای بخش آغاز می‌شود. ابزار llvm-dwarfdump --debug-info همین پنج مقدار را در خط Compile Unit: چاپ می‌کند و اولین تست ما این خط را خوانده و با پیاده‌سازی مقایسه می‌کند.

اختصارات (Abbreviations)

بخش 2.1 می‌گوید هر مدخل اطلاعات دیباگ (DIE) «شامل یک تگ شناسایی و مجموعه‌ای از ویژگی‌ها (Attributes) است». خود این مدخل فقط یک کد اختصار را ذخیره می‌کند. این کد، تعریفی را در بخش .debug_abbrev (بخش 7.5.3) انتخاب می‌کند که نام تگ، وجود یا عدم وجود فرزندان، و فهرست ویژگی‌ها را به‌همراه فرم (Form) آن‌ها مشخص می‌نماید. این فایل شیء شامل 14 تعریف است که دو مورد برای ما اهمیت دارند:

[12] DW_TAG_structure_type  DW_CHILDREN_yes
     DW_AT_name              DW_FORM_strx1
     DW_AT_byte_size         DW_FORM_data1
     DW_AT_decl_file         DW_FORM_data1
     DW_AT_decl_line         DW_FORM_data1
[13] DW_TAG_member           DW_CHILDREN_no
     DW_AT_name              DW_FORM_strx1
     DW_AT_type              DW_FORM_ref4
     DW_AT_decl_file         DW_FORM_data1
     DW_AT_decl_line         DW_FORM_data1
     DW_AT_data_member_location  DW_FORM_data1

تابع parse_abbreviations() مقادیر ULEB128 برای کد و تگ، یک بایت برای فرزندان، و سپس جفت‌های ویژگی و فرم را تا رسیدن به جفت 0, 0 می‌خواند. بخش 7.5.6 انکودینگ فرم‌ها را مشخص می‌کند: data1 یک بایت است، ref4 آفست 4 بایتی نسبت به ابتدای واحد است، strx1 اندیس 1 بایتی در جدول آفست‌های رشته است، sec_offset و data4 چهار بایت هستند، addrx اندیس ULEB128 در جدول آدرس‌هاست، exprloc یک طول ULEB128 همراه با بایت‌های مربوط به آن است، و flag_present اصلاً هیچ بایتی مصرف نمی‌کند.

رمزگشایی دستی عضو balance

مدخل ساختار account در آفست 0x195 با بایت‌های 0c 15 20 00 03 آغاز می‌شود. کد اختصار 12 است که ساختار را نشان می‌دهد. ویژگی DW_AT_name اندیس رشته‌ی 0x15 است، DW_AT_byte_size برابر با 0x20 (یعنی 32) است، DW_AT_decl_file برابر 0 و DW_AT_decl_line برابر 3 است که خط تعریف struct account { در کد منبع را نشان می‌دهد.

مدخل دومین عضو در آفست 0x1a3 با بایت‌های 0d 10 88 01 00 00 00 05 04 شروع می‌شود:

1. مقدار 0d اختصار 13 است که یک عضو را مشخص می‌کند.
2. مقدار 10 ویژگی DW_AT_name با فرم strx1 است: اندیس رشته‌ی 16.
3. بایت‌های 88 01 00 00 ویژگی DW_AT_type با فرم ref4 است: آفست 0x188 نسبت به ابتدای واحد، که مدخل DW_TAG_base_type با نام int را نشان می‌دهد.
4. مقدار 00 برای DW_AT_decl_file و 05 برای DW_AT_decl_line است: خط 5 فایل account.c.
5. مقدار 04 برای DW_AT_data_member_location است: آفست 4.

بخش 5.7.6 می‌گوید یک مدخل عضو «می‌تواند دارای ویژگی DW_AT_data_member_location یا ویژگی DW_AT_data_bit_offset باشد» و یک ثابت صحیح «آفست به بایت از ابتدای موجودیت دربرگیرنده است». این بایت دقیقاً همان عدد جابه‌جایی در دستور addl 0x4(%rax), %ecx است، و تابع compare_layouts() تابعی است که این دو را روبه‌روی هم قرار می‌دهد.

ارجاع به رشته‌ها و آدرس‌ها از طریق دو جدول

اندیس رشته‌ی 16 مستقیماً یک آفست در .debug_str نیست. خواننده مقدار DW_AT_str_offsets_base را از مدخل واحد (که برابر با 8 است) برمی‌دارد و مدخل 4 بایتی را در آفست 8 + 4 * 16 درون .debug_str_offsets می‌خواند. آن مدخل آفست رشته‌ی "balance" را در بخش .debug_str مشخص می‌کند. همین سطح از ارجاع غیرمستقیم برای آدرس‌ها نیز اعمال می‌شود. مدخل تابع sum_balances با بایت‌های 07 07 شروع می‌شود: اختصار 7 (یک subprogram)، و سپس ویژگی DW_AT_low_pc به‌شکل اندیس addrx با مقدار 7. مدخل 8 بایتی در آفست 8 + 8 * 7 از بخش .debug_addr برابر با 0x30 است که آدرس تابع را در بخش .text نشان می‌دهد. شش مدخل اول این جدول، آدرس شش رشته‌ی ثابت متنی (String literals) هستند.

در یک فایل شیء بازتخصیص‌پذیر، هیچ‌کدام از این دو جدول مقادیر نهایی را در خود ندارند. در فایل، تمام ورودی‌های .debug_str_offsets صفر هستند و بخش .rela.debug_str_offsets شامل 29 بازتخصیص از نوع R_X86_64_32 نسبت به .debug_str است که آفست واقعی در مقدار افزوده (Addend) آن قرار دارد. بخش .debug_addr دارای 13 بازتخصیص R_X86_64_64 نسبت به .text و .rodata.str1.1 است. بخش .debug_info نیز چهار بازتخصیص مستقل دارد: آفست جدول اختصارات، ویژگی DW_AT_str_offsets_base به‌شکل .debug_str_offsets+0x8، ویژگی DW_AT_stmt_list و ویژگی DW_AT_addr_base به‌شکل .debug_addr+0x8. متد ElfObject.relocated() پیش از آنکه خواننده بخش را پارس کند، فرمول S + A را برای انواع 32 و 64 بیتی اعمال می‌نماید. در فایل شیء نمادهای بخش (Section symbols) مقدار 0 دارند، بنابراین فیلد مستقیماً مقدار افزوده را دریافت می‌کند. ابزار llvm-dwarfdump نیز همین کار را انجام می‌دهد و به همین دلیل در خروجی آن تمام اندیس‌ها همراه با نام‌ها و آدرس‌های حل‌شده نشان داده می‌شوند.

نوع‌ها، توابع و مکان‌ها

متد DwarfInfo.type_name() ارجاعات DW_AT_type را دنبال می‌کند. فیلد label به یک DW_TAG_pointer_type اشاره دارد، آن به یک DW_TAG_const_type، و آن هم به نوع پایه‌ی char اشاره می‌کند؛ بنابراین نام کامل const char * به دست می‌آید. متد type_size() مقدار DW_AT_byte_size را برای ساختارها و نوع‌های پایه، مقدار 8 را برای اشاره‌گر، و حاصل‌ضرب تعداد در اندازه‌ی عنصر را برای آرایه بازمی‌گرداند. متد type_kind() مقدار DW_AT_encoding در یک نوع پایه را به int علامت‌دار/بدون علامت یا float، و یک اشاره‌گر را به pointer تقلیل می‌دهد که همان واژگان مقایسه‌ی ماست.

متد DwarfInfo.functions() شش مدخل DW_TAG_subprogram را استخراج می‌کند. محدوده‌ی تابع bump از 0x0 تا 0x21 است که از جمع DW_AT_low_pc با طول DW_AT_high_pc به دست می‌آید. مبنای فریم آن DW_OP_reg6 RBP است و پارامتر a عبارت مکانی 91 78 را دارد: عملوند DW_OP_fbreg با مقدار SLEB128 برابر با 0x78 که معادل -8 است. این همان اسلات فریم -0x8(%rbp) است که دیس‌اسمبلی در آدرس 0x4 رجیستر %rdi را درون آن ذخیره کرده بود. اطلاعات دیباگ و دستورالعمل‌های اسمبلی، یک اسلات واحد را از دو دیدگاه مختلف توصیف می‌کنند.

مقایسه‌ی دو چیدمان

تابع compare_layouts() اعضای DWARF را پیمایش کرده و به‌دنبال فیلدی با آفست یکسان در چیدمان بازسازی‌شده می‌گردد. عضوی که هیچ فیلدی برای آن ثبت نشده باشد برچسب no-evidence می‌گیرد. فیلدی با اندازه‌ی متفاوت، برچسب size-mismatch دریافت می‌کند. عضو اشاره‌گری که فیلد آن هرگز دی‌ریفرنس نشده باشد، pointer-unproven می‌شود. اگر نوع داده‌ها همخوانی نداشته باشد (مثلاً یک ممیز شناور در جایی که دستورالعمل‌ها از محاسبات صحیح استفاده کرده‌اند) وضعیت kind-mismatch خواهد بود. فیلدهای بازسازی‌شده‌ای که از وسط یک عضو یا درون پدینگ شروع شوند، unexpected نامیده می‌شوند. در نهایت، اندازه‌ی ساختار از مقایسه‌ی استراید کشف‌شده با DW_AT_byte_size به دست می‌آید.

ارقام مربوط به سه بیلد، حاصل از اجرای python3 code/main.py:

فضاهای خالی کشف‌شده در تمام بیلدها بایت‌های 1 تا 3 و 10 تا 15 هستند، که دقیقاً بر بایت‌های پدینگ چیدمان DWARF منطبق می‌شوند. هر فیلد بازسازی‌شده روی مضربی از اندازه‌ی خود نشسته است؛ یعنی همان شرطی که قوانین psABI دیکته می‌کنند و متد natural_alignment_ok() آن را ثبت می‌نماید.

اگر توابع را یکی‌یکی اضافه کنید، تصویر متفاوتی شکل می‌گیرد. فقط با داشتن bump، چیدمان تنها شامل یک فیلد در آفست 4 است، اندازه نامشخص و کران پایین آن 8 خواهد بود. تابع sum_balances استراید را اضافه می‌کند. تابع tag آفست‌های 0 و 8 را مشخص می‌نماید. تابع projected ممیز شناور آفست 16 را می‌آورد. تابع label_length فیلد آفست 24 را افزوده و اثبات می‌کند که یک اشاره‌گر است. تابع main در بیلد -O0 نقاط فراخوانی را اضافه می‌کند و در بیلدهای -O1 و -O2 چیزی اضافه نمی‌کند، زیرا کامپایلر تمام فراخوانی‌ها را درون‌خطی (Inline) کرده است. تصویر تعاملی این مراحل را گام‌به‌گام برای هر بیلد نشان می‌دهد.

سه چیز همواره خارج از دسترس می‌مانند: نام‌ها درون دستورالعمل‌ها وجود ندارند؛ قید const در دستورالعمل‌ها نیست؛ نوع مقداری که label به آن اشاره می‌کند تنها به‌صورت «عناصری با فاصله‌ی 1 بایت» از روی دستور leaq 0x1(%rcx), %rcx در حلقه‌ی رشته استنباط می‌شود که با هر سه نوع char، unsigned char و _Bool سازگار است. در بیلد -O1 علامت بایت موجود در آفست 0 ناشناخته است، زیرا cmpb $0x6c, (%rdi) بدون گسترش علامت عمل مقایسه را انجام می‌دهد. این گذر در آنجا مقدار int8 را گزارش می‌دهد اما در -O0 که movsbl با گسترش علامت بارگذاری کرده، مقدار i8 را به ثبت می‌رساند. این‌ها دقیقاً همان مواردی هستند که در درس 35 به‌عنوان مجهولات ثبت می‌شوند.

اشیاء ++C

کد shapes.cpp شامل کلاس Shape با مخرب مجازی، متد مجازی خالص area() و متد مجازی name()، و کلاس Rect است که از Shape ارث‌بری کرده و دو عضو int اضافه می‌کند. استاندارد Itanium C++ ABI چگونگی چیدمان این کلاس‌ها توسط کامپایلر clang را روی x86-64 لینوکس تعیین می‌کند.

نام‌های تغییریافته (Mangled names)

بخش 5.1.2 از استاندارد ABI مشخص می‌کند که «یک نام با افزودن پیشوند _Z به کدگذاری نام آن، تغییر می‌یابد». این فایل شیء شامل 19 نماد از این دست است. رشته‌ی _ZNK4Rect4areaEv این‌گونه خوانده می‌شود: ابتدا _Z، سپس N برای نام تو در تو (Nested)، مقدار K برای متد const، نام‌های پیشوندشده با طول 4Rect و 4area، علامت E برای بستن نام تو در تو و v برای فهرست پارامترهای خالی. ابزار llvm-cxxfilt آن را به‌صورت Rect::area() const چاپ می‌کند. نماد _Z8describeRK5Shapei به‌صورت describe(Shape const&, int) باز می‌شود: R برای مرجع (Reference)، مقدار K برای const، عبارت 5Shape برای نام کلاس و i برای نوع int. نام‌های ویژه در بخش 5.1.4 عبارت‌اند از _ZTV برای جدول vtable، مقدار _ZTI برای typeinfo و _ZTS برای رشته‌ی نام typeinfo. سازنده‌ها و مخرب‌ها با کدهای C1، C2، D0، D1 و D2 مشخص می‌شوند؛ بنابراین هر دو نماد _ZN4RectD0Ev و _ZN4RectD2Ev به‌صورت Rect::~Rect() چاپ می‌شوند، چرا که مخرب حذف‌کننده (Deleting destructor) و مخرب شیء پایه (Base-object destructor) نام یکسانی در کد منبع دارند.

کلاس Demangler در code/main.py این زیرمجموعه را همراه با کدهای نوع توکار در بخش 5.1.5.2 و جایگزینی‌های S_ در بخش 5.1.10 پوشش می‌دهد. تست مربوطه تمام 19 نام را تبدیل کرده و با خروجی ابزار llvm-cxxfilt --no-strip-underscore مقایسه می‌نماید. این فلگ در macOS حیاتی است؛ چرا که این ابزار به‌طور پیش‌فرض یک خط زیر ابتدایی را حذف می‌کند و سپس در شناسایی Z8describe... دچار خطا می‌شود.

استخراج vtable از روی بازتخصیص‌ها

بخش 2.5.2 استاندارد ABI اجزای جدول متدهای مجازی را به‌ترتیب فهرست می‌کند: آفست‌های فراخوانی مجازی، آفست‌های کلاس پایه‌ی مجازی، آفست به بالاترین بخش شیء (Offset to top)، اشاره‌گر typeinfo، و سپس اشاره‌گرهای توابع مجازی. نقطه‌ی آدرس‌دهی (Address point) که vptr شیء به آن اشاره می‌کند، آدرس اولین اشاره‌گر تابع است (بخش 2.6.2). کلاس Rect فاقد پایه‌ی مجازی است، بنابراین جدول آن تنها شامل آفست به رأس، typeinfo و توابع است.

نماد _ZTV4Rect دارای اندازه‌ی 0x30 بایت یعنی شش اسلات 8 بایتی است. در فایل شیء تمام این بایت‌ها صفر هستند. محتوای واقعی در بخش بازتخصیص .rela.data.rel.ro._ZTV4Rect قرار دارد:

0000000000000008 R_X86_64_64              _ZTI4Rect
0000000000000010 R_X86_64_64              _ZN4RectD2Ev
0000000000000018 R_X86_64_64              _ZN4RectD0Ev
0000000000000020 R_X86_64_64              _ZNK4Rect4areaEv
0000000000000028 R_X86_64_64              _ZNK4Rect4nameEv

اسلات 0 آفست به رأس را نگه می‌دارد که 0 است و نیازی به بازتخصیص ندارد. اسلات 1 همان typeinfo است. نقطه‌ی آدرس‌دهی در آفست +16 قرار دارد. با شروع از آنجا، اسلات 0 مخرب شیء کامل، اسلات 1 مخرب حذف‌کننده، اسلات 2 متد area و اسلات 3 متد name است. تابع read_vtable() اندازه‌ی نماد، بازتخصیص‌های آن محدوده و مقدار صفر در آفست 0 را می‌خواند. جدول کلاس Shape چیدمان مشابهی دارد که در اسلات 2 آن مقدار __cxa_pure_virtual قرار گرفته است؛ یعنی همان تابع محیط اجرا (Runtime) که فراخوانی یک متد مجازی خالص به آن ختم می‌شود.

اطلاعات نوع زمان اجرا (RTTI)

بخش 2.9.4 ساختار std::type_info را به‌صورت یک vptr توصیف می‌کند که به‌دنبال آن اشاره‌گری به نام تغییریافته‌ی نوع قرار دارد، و کلاس‌های مشتق‌شده از آن را فهرست می‌نماید. نماد _ZTI4Rect سه بازتخصیص دارد: _ZTVN10__cxxabiv120__si_class_type_infoE+0x10، _ZTS4Rect و _ZTI5Shape. اولی vtable کلاس __si_class_type_info است (کلاسی که ABI برای نوعی با یک پایه‌ی عمومی غیرمجازی در آفست صفر در نظر می‌گیرد) و +0x10 نقطه‌ی آدرس‌دهی آن vtable است. دومی به رشته‌ی 4Rect یعنی نام تغییریافته‌ی نوع اشاره می‌کند که متد name() روی یک شیء type_info دقیقاً همان را بازمی‌گرداند. سومی اشاره‌گر به کلاس پایه است. نماد _ZTI5Shape از __class_type_info استفاده می‌کند و فاقد اشاره‌گر کلاس پایه است. تابع read_typeinfo() این سه واقعیت را بازمی‌گرداند.

فراخوانی مجازی

تابع describe در سطح بهینه‌سازی -O0 یک فراخوانی مجازی انجام می‌دهد:

       f: 48 8b 7d f8                  	movq	-0x8(%rbp), %rdi
      13: 48 8b 07                     	movq	(%rdi), %rax
      16: ff 50 10                     	callq	*0x10(%rax)

دستور movq اول اشاره‌گر شیء را بارگذاری می‌کند. دستور دوم 8 بایت را از آفست 0 شیء می‌خواند که همان vptr است، زیرا طبق ABI در کلاسی با توابع مجازی، این اشاره‌گر در ابتدای شیء قرار می‌گیرد. دستور callq از طریق آفست 0x10 بعد از vptr انجام می‌شود و 0x10 / 8 نشان‌دهنده‌ی اسلات 2 است. تابع find_virtual_calls() این الگو را تطبیق داده و هر دو گزینه‌ی احتمالی را گزارش می‌کند: Rect::area() const از _ZTV4Rect و __cxa_pure_virtual از _ZTV5Shape. این‌که کدام‌یک در عمل اجرا شود به شیء بستگی دارد، و به همین دلیل این فراخوانی غیرمستقیم است.

سیستم DWARF نیز همین اسلات را ثبت کرده است. مدخل‌های DW_TAG_subprogram برای area در هر دو کلاس دارای ویژگی DW_AT_vtable_elem_location (DW_OP_constu 0x2) هستند؛ متد name اسلات 3 و مخرب‌ها اسلات 0 را نشان می‌دهند. کلاس Rect یک DW_TAG_structure_type به اندازه‌ی 16 بایت است که مدخل DW_TAG_inheritance آن به Shape در آفست 0 ارجاع داده و اعضای w و h را در آفست‌های 8 و 12 قرار می‌دهد. کلاس Shape کلاسی 8 بایتی با یک عضو ساختگی به نام _vptr$Shape است. دو تحلیل مستقل، اسلات 2 را برای متد area اثبات می‌کنند: جدول بازتخصیص و مدخل‌های اطلاعات دیباگ.

در سطح بهینه‌سازی -O1، فایل شیء اساساً هیچ vtable ثبتی ندارد. تابع main شیء Rect را به‌صورت متغیر محلی می‌سازد؛ بنابراین کامپایلر فراخوانی‌های r.name() و describe(r, 2) را در زمان کامپایل حل کرده و آن‌ها را درون‌خطی می‌کند. چون هیچ کدی آدرس این جدول را برنمی‌دارد، جدول اصلاً به فایل خروجی فرستاده نمی‌شود. با این حال تابع describe همچنان شامل دستورات movq (%rdi), %rax و callq *0x10(%rax) است، چون پارامتر ورودی آن می‌تواند هر شیئی از نوع Shape باشد. غیبت جدول vtable، واقعیتی مربوط به ساختار یک فایل شیء مشخص است، و تست test_the_optimised_object_keeps_the_call_pattern_but_drops_the_vtables هر دو بخش ماجرا را بررسی می‌کند.

استاندارد مایکروسافت (Microsoft ABI) در تک‌تک این جزئیات تفاوت دارد. نام‌های تزیین‌شده (Decorated names) با علامت ? شروع می‌شوند و قرارداد فراخوانی را در خود کد می‌کنند؛ بنابراین تابع void test(void) که به‌صورت __cdecl در ++C کامپایل شده باشد تبدیل به ?test@@ZAXXZ می‌شود. ساختار مکان‌یاب RTTI در خانه‌ی vfptr[-1] به‌شکل _RTTICompleteObjectLocator می‌نشیند، و نمادها به‌شکل ??_7 برای جدول vftable و ??_R4 برای مکان‌یاب نام‌گذاری می‌شوند. خود مستندات مایکروسافت صراحتاً بیان می‌کنند که «هیچ استانداردی برای نام‌گذاری ++C میان سازندگان مختلف کامپایلر وجود ندارد». فیکسچرهای این درس منحصراً بر مبنای Itanium هستند.

نوع‌های بازیابی‌شده در ابزارهای مختلف

هر ردیف جدول زیر که خروجی خاصی را نشان می‌دهد، روی همین سیستم تولید و در پوشه‌ی code/fixtures/tools/ ذخیره شده است. مواردی که روی سیستم نصب نبوده‌اند، بر اساس مستندات رسمی توصیف شده‌اند و این موضوع ذکر شده است.

خروجی Ghidra بدون DWARF همان دو قاعده‌ی اصلی را نشان می‌دهد: دکامپایلر آن برای پارامتر تابع tag نوع char * در نظر گرفت چون تابع یک بایت را از طریق آن مقایسه می‌کند، و برای فیلد موجود در 0x18 نوع char ** را منظور کرد چون تابع label_length مقدار بارگذاری‌شده را دی‌ریفرنس کرده و بایت‌ها را مقایسه می‌نماید. این‌ها همان دو قاعده‌ای هستند که گذر این درس اعمال می‌کند: تعیین عرض از روی دستورالعمل، و اثبات اشاره‌گر از روی عمل دی‌ریفرنس. مستندات دکامپایلر Ghidra توضیح می‌دهند که متغیرهای واسط p-code لزوماً از ابتدا نوع داده ندارند، و دکامپایلر در نهایت یک نوع رسمی را از طریق فرآیند انتشار (Propagation) به آن‌ها منتسب می‌کند. گزینه‌ی «Infer constant pointers» همین انتشار را برای مقادیر ثابت تعمیم می‌دهد. نسخه‌ی Ghidra 12.1 قابلیت بازیابی فیلدهای بیتی (Bitfield) را نیز به دکامپایلر افزود، که فیکسچرهای این درس به آن‌ها نمی‌پردازند.

جدولی که دستی ساخته می‌شود سوی دیگر این فرآیند است. بخش Data Type Manager در Ghidra، بخش Local Types در IDA، آرشیوهای نوع در Binary Ninja و دستور td در rizin، همگی به شما اجازه می‌دهند ساختار را از روی چیدمان بازیابی‌شده تایپ کنید و تغییر خروجی دکامپایلر را ببینید. گذر ما به شما نشان می‌دهد دقیقاً چه چیزهایی را باید تایپ کنید و کدام فیلدها حاصل حدس و گمان هستند.

ابزار rea 6.5.0 با ارائه‌دهنده‌ی Ghidra خود، متن دکامپایلر را به‌شکل یک رکورد تحویل می‌دهد. تمام موارد جدول Ghidra در مورد آن نیز صدق می‌کند و این رکورد، نام نوع‌ها را بدون ذکر شواهدی که آن‌ها را اثبات کرده در بر دارد. اجرای python3 code/main.py infer روی همان لیست دیس‌اسمبلی، این شواهد را در اختیارتان می‌گذارد.

پژوهش‌های حوزه‌ی استنتاج نوع (Type Inference)

گذری که در اینجا پیاده کرده‌ایم، نیمه‌ی مربوط به «تولید قیود» در یک سیستم استنتاج نوع است که به یک ساختارِ در دسترس از طریق پارامتر ورودی محدود شده است. کارهای تحقیقاتی این حوزه بسیار فراتر رفته‌اند:

• پژوهش TIE (توسط Lee، Avgerinos و Brumley، کنفرانس NDSS 2011) بازسازی نوع را به‌صورت تولید و حل قیدها روی نمایش میانی باینری فرمول‌بندی کرد، میزان دقت (Precision) و محافظه‌کاری را سنجید و نتایج را روی 87 برنامه‌ی coreutils با یک دکامپایلر تجاری مقایسه نمود.
• سیستم Retypd (توسط Noonan، Loginov و Cok، کنفرانس PLDI 2016) مفاهیم زیرنوع‌ها (Subtyping)، چندریختی (Polymorphism) و نوع‌های بازگشتی را اضافه کرد و بازسازی اصلاح‌کننده‌های const اشاره‌گر را با بازخوانی (Recall) 98 درصدی گزارش داد. پیاده‌سازی متن‌بازی از آن با نام شرکت GrammaTech در دسترس است.
• سیستم OSPREY (توسط Zhang و همکاران، IEEE S&P 2021) هر موقعیت حافظه را یک متغیر تصادفی فرض کرده و محتمل‌ترین نوع‌ها را استنتاج می‌کند.
• پروژه‌های DIRTY (توسط Chen و همکاران، USENIX Security 2022) و ReSym (توسط Xie و همکاران، CCS 2024) خروجی دکامپایلر را با مدل‌های یادگیری ماشین پس‌پردازش می‌کنند، و ReSym دقت 72.9 درصدی را روی چیدمان کامل ساختارها گزارش داده است.
• ابزار RecStruct (توسط Chen و همکاران، USENIX Security 2026) ساختارهای تو در تو را بدون نیاز به دکامپایلر و با استفاده از اجرای نمادین غیرحساس به جریان داده (Flow-insensitive) و الگوریتم Union-Find روی اسلات‌های استک بازیابی می‌کند.

ساختار روی فریم استک نخستین موردی است که گذر این درس از آن صرف‌نظر می‌کند. در سطح بهینه‌سازی -O1، تابع main متغیر rows را روی استک نگه می‌دارد و کد درون‌خطی‌شده مقادیر 0x24(%rsp)، 0x40(%rsp)، 0x48(%rsp)، 0x30(%rsp) و 0x38(%rsp) را می‌خواند. این آفست‌ها به پیمانه‌ی 32 برابر با 4، 0، 8، 16 و 24 هستند: یعنی همان ساختار، بدون این‌که پارامتری وجود داشته باشد که تحلیل را از آن شروع کنیم. در بخش آزمایشگاه تمرینی، بازسازی این حالت را پیاده خواهید کرد.

پیاده‌سازی گام‌به‌گام

اجرای دموی اصلی:

cd phases/13-tools-and-protocols/41-recovering-data-and-types
python3 code/main.py

خروجی یک گزارش JSON با پنج بخش اصلی است: dwarf هدر واحد، ساختارها و توابع شیء ساخته‌شده با -O0 را نگه می‌دارد؛ oracles چیدمان طبق قوانین psABI، چیدمان ctypes، چیدمان DWARF، اجرای بومی و پرچم تطابق (agree) را دارد؛ builds دسترسی‌ها، چیدمان بازسازی‌شده و مقایسه را برای هر سه فایل ارائه می‌کند؛ cxx نام‌های بدون تزیین، هر دو vtable، هر دو رکورد typeinfo، فراخوانی متد مجازی و اسلات‌های DWARF را در بر دارد؛ tools نیز خروجی ابزارهای مختلف را فهرست می‌کند.

شکل کلی خروجی مورد انتظار:

{
  "dwarf": {"unit": {"unitLength": 489, "version": 5, "unitType": "DW_UT_compile", "addressSize": 8, "abbrevOffset": 0}, "...": "..."},
  "oracles": {"agree": true, "psabiRules": {"size": 32, "align": 8, "...": "..."}, "...": "..."},
  "builds": {
    "O0": {"layout": {"stride": 32, "size": 32, "gaps": [1, 2, 3, 10, 11, 12, 13, 14, 15], "...": "..."}, "comparison": {"matches": 5, "members": 5, "...": "..."}},
    "O1": {"...": "..."},
    "O2": {"...": "..."}
  },
  "cxx": {"virtualCalls": [{"slot": 2, "candidates": {"Shape": "__cxa_pure_virtual", "Rect": "_ZNK4Rect4areaEv"}, "...": "..."}], "...": "..."}
}

فایل code/main.py را به‌این‌ترتیب مطالعه کنید:

1. کلاس ElfObject بخش‌ها، نمادها و بازتخصیص‌ها را می‌خواند و متد relocated() فرمول S + A را روی بخش دیباگ اعمال می‌کند.
2. متدهای parse_abbreviations() و DwarfInfo._parse_unit() هدر، جدول اختصارات و مدخل‌ها را پارس کرده و کدهای strx و addrx را از طریق آن دو جدول حل می‌کنند.
3. متدهای DwarfInfo.struct_layouts() و functions() مدخل‌ها را به رکوردهای StructLayout و FunctionInfo تبدیل می‌کنند، به‌همراه متدهای type_name()، type_size() و type_kind().
4. توابع parse_listing()، parse_memory() و access_width() متون خروجی llvm-objdump را می‌خوانند.
5. تابع trace_function() همان ماشین وضعیت (State Machine) انتزاعی است، و fold_unrolled() و infer_layout() دسترسی‌ها را به یک چیدمان تبدیل می‌کنند.
6. تابع compare_layouts() ردیف‌های مقایسه را می‌سازد، و sysv_layout() به‌همراه ctypes_layout() دو مرجع محاسباتی دیگر ما هستند.
7. کلاس‌های Demangler، read_vtable()، read_typeinfo() و find_virtual_calls() بخش‌های مربوط به شیء ++C را پوشش می‌دهند.

چهار دستور جانبی دیگر هم وجود دارد: دستور python3 code/main.py dwarf FILE.o ساختارها و توابع هر فایل شیء بازتخصیص‌پذیر DWARF 5 را چاپ می‌کند؛ دستور python3 code/main.py infer LISTING.txt [FILE.o] گذر تحلیلی را روی یک فایل متنی دیس‌اسمبلی اجرا می‌کند و در صورت ارائه فایل شیء، آن را با DWARF می‌سنجد؛ دستورات python3 code/main.py demangle NAME... و python3 code/main.py vtable FILE.o بخش ++C را تحلیل می‌کنند.

استفاده‌ی عملی

روی یک فایل شیء جدید که خودتان کامپایل کرده‌اید:

1. خروجی llvm-objdump -d -r را گرفته و متن آن را کنار فایل شیء نگه دارید. گذر تحلیلی این متن را می‌خواند.
2. دستور python3 code/main.py infer را روی این متن دیس‌اسمبلی اجرا کنید. ابتدا خط توابع شاهد (Witnesses) را بخوانید: این خط نام توابعی را نشان می‌دهد که از پارامتر اول آن‌ها به‌عنوان مبنای حافظه استفاده شده است. اگر تابعی غایب است، یا پارامتر آن به هیچ عملوند حافظه‌ای نرسیده، یا از مسیری رفته که گذر ما آن را دنبال نمی‌کند.
3. هر فیلد را به‌همراه تعداد دسترسی‌های آن بررسی کنید. یک دسترسی به‌معنای یک شاهد است. فیلدی را که فقط یک شاهد دارد، به‌عنوان فیلد حدسی ثبت کنید.
4. شواهد استراید را ارزیابی کنید. شواهد نوع call-site یا scale قوی هستند. وجود یک شاهد تکی از نوع loop-step بدون هیچ نشانه‌ی دیگر ضعیف محسوب می‌شود، زیرا یک حلقه‌ی بازشده گام جابه‌جاییِ چند عنصر را هم‌زمان گزارش می‌دهد. اگر شاهد unrolled ظاهر شد، فرآیند ادغام را دستی بازبینی کنید.
5. اگر بیلد -g در دسترس است، مقایسه را اجرا کنید و تمام ردیف‌هایی را که وضعیتی غیر از match دارند بخوانید. ردیف no-evidence عضوی را نشان می‌دهد که هیچ تابعی به آن دست نزده است. ردیف unexpected دسترسی‌ای را نشان می‌دهد که گذر نتوانسته در ساختار جای دهد.
6. چیدمان به‌دست‌آمده را به‌عنوان یک struct وارد بخش Type Manager ابزار دکامپایلر خود کنید، و فیلدها، نام‌ها و نوع‌هایی را که حاصل حدس بوده‌اند مشخص نمایید.

هر سه مرجع محاسباتی را دم دست نگه دارید. هر زمان که میان قواعد تحلیلی، خروجی ctypes و DWARF در مورد یک چیدمان تناقض دیدید، با یک ساختار فشرده‌شده (Packed struct)، یک فیلد بیتی یا پلتفرمی با قواعد متفاوت روبه‌رو شده‌اید.

آزمایشگاه تعاملی

بخش اول: رمزگشایی مدخل عضو ساختار

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

cd phases/13-tools-and-protocols/41-recovering-data-and-types/code
python3 -q

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

from main import *
elf = load_object("account-x86_64-O0-g.o")
dwarf = DwarfInfo(elf)
dwarf.header()
elf.section(".debug_info").data[0x1a3:0x1ac].hex(" ")
dwarf.dies[0x1a3].attributes
dwarf.type_name(dwarf.type_of(dwarf.dies[0x1a3]))

پیش از نگاه کردن به دیکشنری، این 9 بایت را روی کاغذ و با کمک اختصار شماره‌ی 13 رمزگشایی کنید. سپس داده‌های خام بخش را بدون اعمال بازتخصیص‌ها با دستور elf.section(".debug_str_offsets").data[8:16].hex() و پس از بازتخصیص با دستور elf.relocated(".debug_str_offsets")[8:16].hex() بخوانید و تفاوت را توضیح دهید.

بخش دوم: ردیابی اجرای یک تابع

listing = load_listing("account-x86_64-O0-g.objdump.txt")
trace = trace_function("label_length", listing["label_length"])
[(hex(a.address), a.root, a.offset, a.width, a.kind) for a in trace.accesses]
trace.pointer_uses
trace_function("sum_balances", listing["sum_balances"]).loops

قبل از اجرا، روی کاغذ بنویسید کدام دسترسی اثبات می‌کند آفست 24 یک اشاره‌گر است. سپس همین کدها را روی متن دیس‌اسمبلی بیلد -O1 اجرا کنید و دستور leaq 0x1(%rcx), %rcx را درون مجموعه‌ی trace.increments بیابید.

بخش سوم: ادغام حلقه‌ی برداری‌شده

o2 = load_listing("account-x86_64-O2-g.objdump.txt")
trace = trace_function("sum_balances", o2["sum_balances"])
sorted({a.offset for a in trace.accesses})
folded, evidence = fold_unrolled(trace, trace.accesses)
sorted({a.offset for a in folded}), [(e.kind, e.value, e.text) for e in evidence]

سپس دستور analyze_build("O2", fold=False)["comparison"] را اجرا کنید و تعداد ردیف‌های unexpected را بشمارید. شرط قاعده را طوری تغییر دهید که الزام کند گام حلقه دقیقاً برابر با k * d با مقدار k حداقل 2 باشد، و تأیید کنید که در بیلد -O1، حلقه با یک دسترسی و گام 32 دست‌نخورده باقی می‌ماند.

بخش چهارم: جدول vtable و نام‌ها

shapes = load_object("shapes-x86_64-O0-g.o")
read_vtable(shapes, "_ZTV4Rect")
read_typeinfo(shapes, "_ZTI4Rect")
demangle("_ZNK4Rect4areaEv"), demangle("_Z8describeRK5Shapei")
find_virtual_calls(load_listing("shapes-x86_64-O0-g.objdump.txt"), [read_vtable(shapes, "_ZTV5Shape"), read_vtable(shapes, "_ZTV4Rect")])

شماره‌ی اسلات را از دستور callq *0x10(%rax) روی کاغذ محاسبه کنید، سپس آن را با مقدار DwarfInfo(shapes).struct("Rect").virtual_methods مقایسه نمایید. در ادامه، فایل shapes-x86_64-O1-g.o را لود کرده و متد read_vtable را روی آن فراخوانی کنید. خطای ElfError را بخوانید و بگویید چرا این نماد در فایل وجود ندارد.

آزمایشگاه تمرینی

ساختار موجود روی استک را درون تابع main در بیلد -O1 بازیابی کنید.

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

• متد trace_function() را طوری توسعه دهید که یک محدوده‌ی اسلات فریم بتواند به‌عنوان یک «ریشه» شناخته شود. این مقدار را بر اساس دستورات ذخیره‌ی movaps که فضای 0x0(%rsp) تا 0x5f(%rsp) را از بخش .data.rel.ro پر می‌کنند (مقدار اولیه‌ی 96 بایتی برای آرایه‌ی rows) مقداردهی اولیه کنید.
• دسترسی‌های درون‌خطی‌شده در آدرس‌های 0x24(%rsp)، 0x40(%rsp)، 0x48(%rsp)، 0x30(%rsp) و 0x38(%rsp) را به آن ریشه منتسب کرده و آفست‌های آن‌ها را به پیمانه‌ی یک استراید کاندید گزارش دهید.
• استراید 32 را از حلقه‌ی موجود در محدوده‌ی 0x120 تا 0x12c استخراج کنید؛ جایی که رجیستر %r14 از 4 شروع شده و با گام‌های 0x20 جلو می‌رود تا به 0x64 برسد، و نشان دهید که کران بالای حلقه یعنی 0x64 برابر با حاصل سه عنصر به‌علاوه‌ی آفست فیلد است.
• نتیجه را با چیدمان استخراج‌شده از DWARF مقایسه کرده و به 5 تطابق کامل برسید، و انواع داده‌ای را که غیرقابل‌اثبات باقی مانده‌اند ثبت کنید.
• تستی اضافه کنید که اگر ریشه‌ی فریم به اشتباه به‌عنوان یک پارامتر شناسایی شود، با خطا مواجه گردد.

معیار موفقیت این است که دستور python3 code/main.py infer روی دیس‌اسمبلی بیلد -O1، تابع main را به‌عنوان یک شاهد با ریشه‌ی فریم گزارش دهد و جدول مقایسه، 5 تطابق کامل را صرفاً بر اساس تحلیل تابع main ثبت کند.

خروجی این درس

این درس شامل فایل outputs/skill-recovering-data-and-types.md است. از آن برای تبدیل یک فهرست دیس‌اسمبلی و بیلد دیباگ اختیاری، به چیدمان ساختار همراه با شواهد هر فیلد، مقدار استراید و منابع آن، مقایسه با DWARF و فهرستی از ناشناخته‌ها استفاده کنید. ساخت این سند مستلزم ثبت جدول دسترسی‌ها، شواهد استراید، اعتبارسنجی ادغام حلقه، مرجع DWARF (در صورت وجود) و گزارشی از نام‌ها و قیدهایی است که هیچ دستورالعملی قادر به ارائه‌ی آن‌ها نیست.

اعتبارسنجی

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

cd phases/13-tools-and-protocols/41-recovering-data-and-types
python3 code/main.py
python3 -m unittest discover -s code/tests -v

اعتبارسنجی باید موارد زیر را اثبات کند:

• هدر واحد، 14 اختصار و آفست پنج عضو کاملاً با خروجی llvm-dwarfdump مطابقت دارند؛
• نام‌ها از طریق جدول بازتخصیص‌یافته‌ی .debug_str_offsets به دست می‌آیند و مقادیر str_offsets_base و addr_base در واحد برابر با 8 هستند؛
• شش تابع دارای همان بازه‌ها، و اطلاعات مکانی DW_OP_reg6 RBP و DW_OP_fbreg در خروجی دامپ هستند و آدرس‌های پایینی آن‌ها با شروع توابع در دیس‌اسمبلی برابر است؛
• فایلی فاقد .debug_info خطا ایجاد می‌کند، و رمزگشاهای LEB128 مقدار 0x78 را به‌صورت -8 می‌خوانند؛
• ابزارهای pyelftools و lldb همان چیدمان تولیدی خواننده‌ی ما را چاپ می‌کنند؛
• قوانین psABI، ماژول ctypes، ساختار DWARF و اجرای بومی همگی آفست‌های 0, 4, 8, 16, 24 و اندازه‌ی 32 را نشان می‌دهند، و ساختار بازآرایی‌شده 24 بایت می‌شود؛
• پارسر دیس‌اسمبلی 13 دستورالعمل را در تابع bump می‌خواند، بازتخصیص R_X86_64_PLT32 bump-0x4 را به فراخوانی موجود در 0x194 متصل می‌کند و پرش رو به عقب در 0x72 را می‌یابد؛
• عملوندهای حافظه، عرض‌ها، نوع‌ها و علامت‌ها از روی متن نحو AT&T و کد دستورالعمل رمزگشایی می‌شوند؛
• تابع bump در سطح -O0 اشاره‌گر را از اسلات فریم بازخوانی می‌کند و سه دسترسی در آفست 4 ایجاد می‌نماید؛
• استراید از دستور shlq $0x5 در بیلد -O0، از دستور addq $0x20, %rdx در بیلد -O1، و از هشت بارگذاری ادغام‌شده با گام 256 در بیلد -O2 استخراج می‌گردد؛
• تابع label_length با دی‌ریفرنس کردن فیلد آفست 24، اشاره‌گر بودن آن را اثبات می‌کند؛
• تابع main در سطح -O0 یک شیء فریم را در آفست‌های 0، 0x20 و 0x40 ارسال می‌کند و در -O1 به‌جز printf هیچ تابعی را صدا نمی‌زند؛
• هر سه بیلد، انطباق پنج عضو از پنج عضو را با اندازه‌ی 32 و فاصله‌های پدینگ معادل DWARF اثبات می‌کنند؛
• بدون فرآیند ادغام، بیلد -O2 هفت فیلد فراتر از بایت 32 را گزارش می‌کند و هیچ اندازه‌ای برای آن نمی‌یابد؛
• ماژول demangler تمام 19 رشته‌ی خروجی llvm-cxxfilt را دقیقاً بازسازی می‌کند؛
• هر دو vtable، هر دو رکورد typeinfo و فراخوانی مجازی در آدرس 0x16 همگی روی اسلات 2 حل می‌شوند و DWARF نیز آن را تأیید می‌کند؛
• شیء ++C در بیلد -O1 الگوی فراخوانی را حفظ می‌کند اما فاقد جدول vtable است؛
• داده‌های استخراج‌شده از Ghidra، rizin و radare2 ساختار را با وجود DWARF همراه با نوع‌ها، و بدون آن به‌شکل آفست‌های خام نشان می‌دهند؛
• تصویر تعاملی دقیقاً همان داده‌های محاسباتی تحلیل را در خود جای داده است.

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

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

یک فیلد را بر اساس «دسترسی» و استراید را بر اساس «حلقه» بازیابی کنید، و دستورالعمل اثبات‌کننده را به هرکدام پیوست نمایید. پیش از آنکه آفستی فراتر از استراید را بپذیرید، حلقه‌های بازشده را ادغام کنید. اطلاعات DWARF را همیشه از طریق جداول اختصارات و جداول بازتخصیص‌یافته بخوانید، نه با اندیس مستقیم در بخش رشته‌ها. داده‌ها را فیلد به فیلد مقایسه کنید و هر عضو فاقد سند، هر اشاره‌گر اثبات‌نشده و تمام نام‌ها را به‌عنوان «نامشخص» علامت بگذارید. در اشیاء ++C، جدول vtable را از روی بازتخصیص‌های آن و شماره‌ی اسلات را از دستور فراخوانی بخوانید، سپس از DWARF برای تأیید شماره اسلاتی که خوانده‌اید بهره بگیرید.

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

• System V Application Binary Interface, AMD64 Architecture Processor Supplement, section 3.1.2: Data Representation
• Procedure Call Standard for the Arm 64-bit Architecture (AAPCS64), section 5.10: Composite Types
• Writing ARM64 code for Apple platforms
• Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1, section 3.7.5: Specifying an Offset
• DWARF Debugging Information Format Version 5, sections 2.1, 5.7.6, 7.5.1.1, 7.5.3, 7.5.6
• Itanium C++ ABI, sections 2.5 (Virtual Table Layout), 2.9 (Run-Time Type Information), 5.1 (External Names)
• Microsoft Learn: Decorated names و Name Decoration
• llvm-dwarfdump command guide و llvm-cxxfilt command guide
• Python ctypes: Structure layout, sizeof, alignment
• Ghidra Data Type Manager، Decompiler Concepts، Decompiler Options، و Ghidra 12.1.4 release
• IDA 9.1 user guide: Types، IDA 9.4 release post، و IDA Free
• Binary Ninja user guide: Types و Binary Ninja 6.0 Krypton
• radare2 6.2.4 release و rizin v0.9.1 release
• GDB manual: Examining the Symbol Table, ptype /o
• pyelftools on PyPI
• Lee, Avgerinos, Brumley, "TIE: Principled Reverse Engineering of Types in Binary Programs" (NDSS 2011)
• Noonan, Loginov, Cok, "Polymorphic Type Inference for Machine Code" (PLDI 2016) و the retypd repository
• Zhang et al., "OSPREY: Recovery of Variable and Data Structure via Probabilistic Analysis for Stripped Binary" (IEEE S&P 2021)
• Chen et al., "Augmenting Decompiler Output with Learned Variable Names and Types" (USENIX Security 2022)
• Xie et al., "ReSym: Harnessing LLMs to Recover Variable and Data Structure Symbols from Stripped Binaries" (CCS 2024)
• Chen et al., "RecStruct" (USENIX Security 2026)