McSema и декомпиляция в исходный код LLVM: реально ли это?22.01.2018 11:18

Представьте себе, что есть некая очень полезная программа, но она, например, существует только в версии Windows и только 64 бита. А вам нужно, например, под ARM64 и под другую ОС, соответственно. Причём исходников у вас нет, и достать их невозможно.

image

Что делать? Существует проект MCSema (пост на хабре про mcsema: https://habrahabr.ru/post/232871/). Его создатели (а они на финансировании DARPA, между прочим), обещают сказочные вещи: перевод бинарников в LLVM IR, оптимизации, семантический анализ кода и т.д. И конечно же, перекомпиляцию на любые архитектуры, которые поддерживает LLVM. Проект опенсорсный (ссылка на гитхаб: https://github.com/trailofbits/mcsema)

А теперь посмотрим, что происходит на самом деле.

Во-первых, нужно сразу прояснить, что MCSema не умеет сама дизассемблировать бинарники. Для этого нужен IDA Pro, дорогой продукт сам по себе. Но это дело решаемое, в принципе, можно заменить IDA Pro чем-то другим, если сильно захотеть.

Но как происходит волшебство преобразования ассемблера в IR?

(Если кто не в курсе: IR — промежуточный язык LLVM, своего рода обобщённый ассемблер, более высокоуровневый, чем ассемблеры процессоров.)

Очень просто. Весь набор регистров x86–64 можно представить в виде структуры под названием SimulatedCPU, которую, с некоторыми сокращениями, вы можете увидеть здесь:

регистры x86
struct SimulatedCPU
{
	enum CPUFlags	// See: https://en.wikibooks.org/wiki/X86_Assembly/X86_Architecture
	{
		CF	= (1 <<  0),
		// 1 is 1
		PF	= (1 <<  2),
		// 3 is 0
		AF	= (1 <<  4),
		// 5 is 0
		ZF	= (1 <<  6),
		SF	= (1 <<  7),
		TF	= (1 <<  8),
		IF	= (1 <<  9),
		DF	= (1 << 10),
		OF	= (1 << 11),
		// 12-13 is IOPL
		// 14 is NT
		// 15 is 0
		// 16 is RF
		// 17 is VM
		// 18 is AC
		// 19 is VIF
		// 20 is VIP
		ID	= (1 << 11),	// ID flag
		// rest is 0
	};

	enum FPUControl	// See: http://www.plantation-productions.com/Webster/www.artofasm.com/Linux/HTML/RealArithmetic.html
	{
		// Exception masks
		FPUC_InvalidOpMask			=	(1 <<  0),
		FPUC_DenormalMask			=	(1 <<  1),
		FPUC_ZeroDivideMask			=	(1 <<  2),
		FPUC_OverflowMask			=	(1 <<  3),
		FPUC_UnderflowMask			=	(1 <<  4),
		FPUC_PrecisionMask			=	(1 <<  5),
		// 6 is 1 (no idea why)
		// 7 is 0
		FPUC_PrecisionControlMask	=	(3 <<  8),	// 2 bits, 00 - 24 bits (float) , 01 - reserved, 10 - 53 bits (double), 11 - 64 bits (FP80), default 11
		FPUC_RoundingMask			=	(3 << 10),	// 2 bits, 00 - to nearest or even, 01 - down, 10 - up, 11 - truncate, default 00
		FPUC_Infinity				=	(1 << 12),
		// rest is 0
	};

	enum FPUStatus	// 16 bits
	{
		FPUS_InvalidOpFlag			=	(1 <<  0),
		FPUS_DenormalFlag			=	(1 <<  1),
		FPUS_ZeroDivideFlag			=	(1 <<  2),
		FPUS_OverflowFlag			=	(1 <<  3),
		FPUS_UnderflowFlag			=	(1 <<  4),
		FPUS_PrecisionFlag			=	(1 <<  5),
		FPUS_StackFaultFlag			=	(1 <<  6),	// that's for FPU stack (8 regs)
		FPUS_ExceptionFlag			=	(1 <<  7),	// set if any previous is set
		FPUS_C0						=	(1 <<  8),	// Condition bit 0
		FPUS_C1						=	(1 <<  9),	// Condition bit 1
		FPUS_C2						=	(1 << 10),	// Condition bit 2
		FPUS_TOP_Mask				=	(7 << 11),	// top-of-stack pointer (3 bits)
		FPUS_C3						=	(1 << 14),	// Condition bit 3
		FPUS_Busy					=	(1 << 15),	// 1 is FPU is busy. I don't expcet any code to ever use it.
	};

	enum SSE_MXCSR
	{
		MXCSR_InvalidOp					= (1 <<  0),
		MXCSR_Denormal					= (1 <<  1),
		MXCSR_DivideByZero				= (1 <<  2),
		MXCSR_Overflow					= (1 <<  3),
		MXCSR_Underflow					= (1 <<  4),
		MXCSR_Precision					= (1 <<  5),
		MXCSR_DenormalsAreZero			= (1 <<  6),
		MXCSR_InvalidOpExceptionMask	= (1 <<  7),
		MXCSR_DenormalExceptionMask		= (1 <<  8),
		MXCSR_DivideByZeroExceptionMask	= (1 <<  9),
		MXCSR_OverflowExceptionMask		= (1 << 10),
		MXCSR_UnderflowExceptionMask	= (1 << 11),
		MXCSR_PrecisionExceptionMask	= (1 << 12),
		MXCSR_RoundingModeMask			= (3 << 13),	// 2-bit, so it's a mask
		MXCSR_FlushToZero				= (1 << 15),
	};

	// General Purpose Registers (32-bit in 32-bit mode, 64-bit in 64-bit mode)
	UINT_PTR	RegAX;					// 0x00 (0)
	UINT_PTR	RegBX;					// 0x04 (4)
	UINT_PTR	RegCX;					// 0x08 (8)
	UINT_PTR	RegDX;					// 0x0C (12)
	UINT_PTR	RegSI;					// 0x10 (16)
	UINT_PTR	RegDI;					// 0x14 (20)
	UINT_PTR	RegSP;					// 0x18 (24)
	UINT_PTR	RegBP;					// 0x1C (28)

#ifdef EON_WIN64

	UINT_PTR	Reg08;
	UINT_PTR	Reg09;
	UINT_PTR	Reg10;
	UINT_PTR	Reg11;
	UINT_PTR	Reg12;
	UINT_PTR	Reg13;
	UINT_PTR	Reg14;
	UINT_PTR	Reg15;
	UINT_PTR	RegRIP;					// possibly it won't be needed, if we fold all RIP-relative instructions on conversion. If you remove it, see about padding below.

#endif

	// Various often used flags - close to other registers to improve caching if possible
	// EFLAGS (some)
	BYTE		FlagCF;					// 0x20 (32)
	BYTE		FlagPF;					// 0x21 (33)
	BYTE		FlagAF;					// 0x22 (34)
	BYTE		FlagZF;					// 0x23 (35)
	BYTE		FlagSF;					// 0x24 (36)
	BYTE		FlagDF;					// 0x25 (37)
	BYTE		FlagOF;					// 0x26 (38)

	// FPU Status Word (some)
	BYTE		FlagFPU_C0;				// 0x27 (39)
	BYTE		FlagFPU_C1;				// 0x28 (40)
	BYTE		FlagFPU_C2;				// 0x29 (41)
	BYTE		FlagFPU_C3;				// 0x2A (42)
	BYTE		FlagFPU_TOP;			// 0x2B (43)

	// FPU Control Word (some)
	BYTE		FlagFPU_PC;				// 0x2C (44)
	BYTE		FlagFPU_RC;				// 0x2D (45)

	// Rarely used flags, serving as paddding

	// FPU Control Word (some)
	BYTE		FlagFPU_IM;				// 0x2E (46)
	BYTE		FlagFPU_DM;				// 0x2F (47)
	BYTE		FlagFPU_ZM;				// 0x30 (48)
	BYTE		FlagFPU_OM;				// 0x31 (49)
	BYTE		FlagFPU_UM;				// 0x32 (50)
	BYTE		FlagFPU_PM;				// 0x33 (51)
	BYTE		FlagFPU_X;				// 0x34 (52)

	// FPU Status Word (some)
	BYTE		FlagFPU_ES;				// 0x35 (53)

	// Tag Word
	WORD		FPUTagWord;				// 0x36 (54)

	UINT_PTR	ThreadEnvironmentBlock;	// 0x38 (56)
	UINT_PTR	ZeroRegister;			// 0x3C (60) zero-filled dummy to give as CS,ES or SS register

	// XMM registers (aligned on 64-bit alignment)
#ifdef EON_WIN64
	BYTE		XMMRegs[16*16];			// 16 128-bit (16-byte) registers
#else
	BYTE		XMMRegs[8*16];			// 0x40 (64) 8 128-bit (16-byte) registers
#endif

	// x87 FPU registers (aligned on 64-bit alignment)
	DOUBLE		FPURegs[8];				// 0xC0 (192)

	// Rarely used flags and other rarely used members

	// FPU Status Word (some)
	BYTE		FlagFPU_IE;				// 0x100 (256)
	BYTE		FlagFPU_DE;				// 0x101 (257)
	BYTE		FlagFPU_ZE;				// 0x102 (258)
	BYTE		FlagFPU_OE;				// 0x103 (259)
	BYTE		FlagFPU_UE;				// 0x104 (260)
	BYTE		FlagFPU_PE;				// 0x105 (261)
	BYTE		FlagFPU_SF;				// 0x106 (262)
	BYTE		FlagFPU_B;				// 0x107 (263)

	// MXCSR
	BYTE		SSEFlag_InvalidOperation;		// 0x108 (264)
	BYTE		SSEFlag_Denormal;				// 0x109 (265)
	BYTE		SSEFlag_DivideByZero;			// 0x10A (266)
	BYTE		SSEFlag_Overflow;				// 0x10B (267)
	BYTE		SSEFlag_Underflow;				// 0x10C (268)
	BYTE		SSEFlag_Precision;				// 0x10D (269)
	BYTE		SSEFlag_DenormalsAreZero;		// 0x10E (270)
	BYTE		SSEFlag_InvalidOperationMask;	// 0x10F (271)
	BYTE		SSEFlag_DenormalMask;			// 0x110 (272)
	BYTE		SSEFlag_DivideByZeroMask;		// 0x111 (273)
	BYTE		SSEFlag_OverflowMask;			// 0x112 (274)
	BYTE		SSEFlag_UnderflowMask;			// 0x113 (275)
	BYTE		SSEFlag_PrecisionMask;			// 0x114 (276)
	BYTE		SSE_RoundingMode;				// 0x115 (277)
	BYTE		SSEFlag_FlushToZero;			// 0x116 (278)

	BYTE		FlagID;							// 0x117 (279) - EFLAGS' ID flag

	// FPU debugging, currently unused but reserved
	UINT_PTR	LastInstructionPtrOffset;		// 0x118 (280)
	UINT_PTR	LastDataPtrOffset;				// 0x11A (281)
	WORD		FPUFopcode;						// 0x11E (282)
	WORD		LastInstructionPtrSeg;			// 0x120 (283)
	WORD		LastDataPtrSeg;					// 0x122 (284)

#ifdef EON_WIN64
	UINT_PTR	StackValueAtLastNativeCodeEntry;	// 0x124 (286), this is used to unwind simulated stack when part of it was used by native code
#endif
 //...
};


В ассемблере LLVM эта структура отражается очень просто: 

%SimulatedCPU = type <{ i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i3, i2, i2, i1, i1, i1, i1, i1, i1, i1, i1, i16, i64, i64, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, [8 x double], i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i2, i1, i1, i64, i64, i16, i16, i16 }>

(i64, i1 и т.п. — это целочисленные типы в LLVM IR, имеющие, соответственно, размер 64 бита, 1 бит и т.п.) То есть регистры общего назначения имеют тип i64, флаги — тип i1, далее идут 128-битные регистры XMM, регистры FPU (типа double), флаги FPU и разные служебные регистры.
Пусть у нас есть некоторая функция исходной программы, которая начинается, например, так: 

0000000140820d40         mov        rax, rsp                                    
0000000140820d43         push       rbp
0000000140820d44         push       rbx
0000000140820d45         push       rsi
0000000140820d46         push       rdi
0000000140820d47         push       r12
0000000140820d49         push       r13
0000000140820d4b         push       r14
0000000140820d4d         push       r15

Ничего необычного, в прологе функции мы копируем значение RSP в RAX и сохраняем в стек некоторые регистры, в соответствии с Calling Convention. То есть это даже ещё не сама содержательная часть функции, это только часть пролога.

Во что превращает это код MCSema (с сокращениями): 


%0 = type opaque
%SimulatedCPU = type <{ i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i3, i2, i2, i1, i1, i1, i1, i1, i1, i1, i1, i16, i64, i64, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, [8 x double], i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i2, i1, i1, i64, i64, i16, i16, i16 }>

define hidden fastcc void @Foo(%SimulatedCPU* noalias nocapture align 16 dereferenceable(542)) 
entry:
  %R15_val = alloca i64
  %XMM9_val = alloca i128
  %XMM8_val = alloca i128
 ...
  %RSP_val = alloca i64
  %RBP_val = alloca i64
  ...
  %RAX_val = alloca i64
...
  %1 = getelementptr inbounds %SimulatedCPU, %SimulatedCPU* %0, i64 0, i32 0
  %2 = load i64, i64* %1
  store i64 %2, i64* %RAX_val
...
%13 = getelementptr inbounds %SimulatedCPU, %SimulatedCPU* %0, i64 0, i32 6
  %14 = load i64, i64* %13
  store i64 %14, i64* %RSP_val
  %15 = getelementptr inbounds %SimulatedCPU, %SimulatedCPU* %0, i64 0, i32 7
  %16 = load i64, i64* %15
  store i64 %16, i64* %RBP_val
...
block_0x10820d40:                                 ; preds = %entry
  %165 = load i64, i64* %RSP_val
  store i64 %165, i64* %RAX_val
  %166 = load i64, i64* %RBP_val
  %167 = load i64, i64* %RSP_val
  %168 = sub i64 %167, 8
  %169 = inttoptr i64 %168 to i64*
  store volatile i64 %166, i64* %169, align 4

Для тех, кто не знает LLVM IR, некоторые пояснения:
1.В функцию всегда передаётся один аргумент — указатель на глобальную структуру SimulatedCPU. Функция всегда возвращает void.
2.Выделяем на стеке память для переменной 64 бита:
%RSP_val = alloca i64
3.Получаем адрес 6-го элемента в структуре SimulatedCPU (т.е. регистра RSP)
%13 = getelementptr inbounds %SimulatedCPU, %SimulatedCPU* %0, i64 0, i32 6
4. Получаем значение RSP:
%14 = load i64, i64* %13
5. Сохраняем его в заранее выделенную память под именем RSP_val:
store i64%14, i64* %RSP_val
6. Снова загружаем значение RSP в переменную
%165 = load i64, i64* %RSP_val
7. Копируем в RAX (память под RAX была выделена аналогичным образом):
store i64%165, i64* %RAX_val
8. Получаем значение RBP:
%166 = load i64, i64* %RBP_val
9. Получаем значение RSP
%167 = load i64, i64* %RSP_val
10. Вычитаем 8 из значения RSP (т.е. увеличиваем стек на 8 байт)
%168 = sub i64%167, 8
11. Преобразуем полученное значение в указатель
%169 = inttoptr i64%168 to i64*
12. Сохраняем значение RBP по полученному адресу
store volatile i64%166, i64* %169, align 4

Это команды, в которые MCSema превратил одну команду исходной программы: push rbp.

Но это неоптимизированный код, может быть, оптимизатор opt сделает его эффективным?

Посмотрим: 


%0 = type opaque
%SimulatedCPU = type <{ i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i64, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i3, i2, i2, i1, i1, i1, i1, i1, i1, i1, i1, i16, i64, i64, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, i128, [8 x double], i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i1, i2, i1, i1, i64, i64, i16, i16, i16 }>

define hidden fastcc void @Foo(%SimulatedCPU* noalias nocapture align 16 dereferenceable(542)) {
entry:
...
  %12 = getelementptr inbounds %SimulatedCPU, %SimulatedCPU* %0, i64 0, i32 6
  %13 = load i64, i64* %12, align 16
  %14 = getelementptr inbounds %SimulatedCPU, %SimulatedCPU* %0, i64 0, i32 7
  %15 = load i64, i64* %14, align 8
...
  %56 = add i64 %13, -8
  %57 = inttoptr i64 %56 to i64*
  store volatile i64 %15, i64* %57, align 4

Итак, оптимизатор убрал размещение на стеке копий регистров симулируемого процессора, заменив их прямыми операциями чтения/записи в глобальную структуру SimulatedCPU. Стала ли от этого программа более эффективной? Однозначно нет. Больше оптимизатор не может сделать ничего: квалификатор volatile является для него непреодолимым препятствием.

Если собрать получившийся код и запустить на ARM64, то он будет приблизительно на два порядка медленнее исходного кода на x86–64.

MCSema не видит никаких переменных на стеке функции: она тупо превращает элементарные операции с регистрами даже не в операции с регистрами целевого процессора (таргета), а в операции со структурой SimulatedCPU, которая расположена в памяти (если программа многопоточная, то каждому потоку соответствует своя копия этой структуры).

Выводы, которые можно сделать из вышеописанного: пока что рано говорить о переводе бинарных файлов с одной архитектуры на другую. Вместо обещанного семантического анализа мы имеем просто очень неэффективную эмуляцию работы процессора. Такой подход в принципе не позволяет добиться эффективной работы программы на процессоре с другой архитектурой.

Ссылки по теме:
1. Andrew Ruef. There and back again. Binary Analysis with mcsema. https://tilde.town/~awruef/binaries.pdf
2. Lifting Windows Driver Binaries into LLVM IR. https://sslab.gtisc.gatech.edu/2017/win-lift.html

© Habrahabr.ru