휴리스틱 없는 결정론적 완전 정적 전체 바이너리 번역

• Elevator는 디버그 정보·소스 코드·바이너리 레이아웃 가정 없이 x86-64 실행 파일 전체를 AArch64로 정적으로 번역함
• 코드·데이터 판별 휴리스틱 대신 각 바이트의 가능한 해석을 모두 담은 superset CFG를 만들고 종료 경로만 제거함
• x64 상태를 AArch64 레지스터에 일대일 매핑하고, 원본 주소에서 번역 코드로 가는 조회 테이블로 간접 분기를 처리함
• 오프라인 타일 뱅크는 x64 명령 의미를 C 템플릿으로 작성한 뒤 LLVM 20으로 AArch64 바이트 시퀀스로 컴파일됨
• 결과물은 런타임 번역 없는 자체 포함 AArch64 바이너리이며, SPECint 2006에서 QEMU 사용자 모드 JIT와 동등하거나 더 나은 성능을 냄

Elevator의 목표

• Elevator는 x86-64 실행 파일 전체를 AArch64로 옮기는 완전 정적 바이너리 번역기임
• 디버그 정보, 소스 코드, 원본 바이너리의 코드 패턴, 바이너리 레이아웃에 대한 가정을 사용하지 않음
• 기존 정적 번역기는 코드와 데이터를 구분하기 위해 휴리스틱이나 런타임 폴백에 의존하지만, Elevator는 원본 실행 파일의 모든 바이트를 가능한 해석별로 미리 번역함
• 어떤 바이트든 데이터, opcode 일부, opcode 인자 일부가 될 수 있으므로 가능한 제어 흐름을 모두 포함한 superset CFG를 만들고, 예외적 프로그램 종료로 이어지는 경로만 제거함
• 출력은 번역 코드, 원본 x64 바이너리, 주소 조회 테이블, 런타임 드라이버를 포함한 자체 포함 AArch64 바이너리로 구성됨
• 번역 완료 뒤에는 JIT나 런타임 번역 지원 없이 실행 가능함
• 같은 입력 바이너리를 두 번 번역하면 같은 출력 비트열이 생성되며, 테스트·검증·인증·암호화 서명 대상이 실제 배포 코드와 일치함
• 주요 비용은 코드 크기 증가이며, 그 대가로 에뮬레이터나 JIT 컴파일러보다 배포 전 검증 가능성이 커짐
• 평가에는 전체 SPECint 2006 벤치마크와 손으로 만든 바이너리가 포함됐고, 성능은 JIT 가속을 쓰는 QEMU 사용자 모드 에뮬레이션과 동등하거나 더 나은 수준으로 나옴
• 연구진은 프로젝트 종료 시 전체를 오픈소스로 공개하겠다고 밝힘

정적 번역이 필요한 이유와 기존 한계

• 하드웨어가 한 ISA에서 다른 ISA로 전환될 때 기존 소프트웨어를 새 플랫폼으로 가져가야 하며, 남아 있는 소스 코드를 재컴파일하는 방식만으로는 충분하지 않을 수 있음
• 검증 또는 인증된 레거시 코드에서는 소스 코드가 아니라 잘 테스트된 특정 권위 있는 바이너리 실행 파일이 인증 대상인 경우가 많음
• 나중에 소스에서 동일한 바이너리를 비트 단위로 재현하려면 당시의 컴파일러, 링커, 빌드 시스템 버전이 필요할 수 있어 현실적으로 어려움
• 제조사가 소스 코드를 거치지 않고 바이너리에 직접 패치를 적용한 경우, 보관된 소스로 다시 빌드하면 이미 수정된 오류가 되살아날 수 있음
• 기존 바이너리 직접 처리 방식은 에뮬레이션, 정적 번역, 동적 번역을 조합하지만, 번역된 프로그램과 함께 실행되는 추가 시스템 컴포넌트가 신뢰 기반 코드에 포함됨
• 동적 동작은 테스트 순서나 입력에 따라 달라질 수 있어 전체 신뢰성을 확인하기 어려움
• Horspool과 Marovac은 1980년에 실행 파일을 역변환하려면 코드와 데이터를 확실히 구별해야 하며, 대부분의 아키텍처에서 이는 정지 문제와 동등해 일반적으로 풀 수 없음을 보였음
• 기존 정적 바이너리 리프터는 코드와 데이터 구분을 휴리스틱으로 근사하며, 특히 간접 제어 흐름 전송의 목표를 예측할 때 문제가 커짐
• LLBT는 ARM 명령을 LLVM IR로 올려 대상 아키텍처로 재컴파일하지만, 간접 분기 목표 탐지에 휴리스틱을 사용하고 입력 바이너리에 여러 가정을 둠
• 좋은 휴리스틱도 일부 입력에서는 실패하며, 전체 바이너리를 올바르게 리프팅하려면 모든 코드·데이터 판별이 맞아야 하므로 바이너리가 클수록 실패 가능성이 커짐
• 동적 방식은 실제 실행된 명령 흐름을 따라가므로 명령 복구와 간접 제어 흐름을 처리할 수 있지만, 구체 실행에서 도달하지 않은 명령은 리프팅하지 못함
• x64처럼 가변 길이 명령을 가진 ISA에서는 명령 시퀀스 안에 다른 명령 시퀀스가 중첩될 수 있고, 다중 바이트 명령 중간으로 분기하면 기존 피연산자가 별도 명령으로 디코드될 수 있음
• ROP 공격과 코드 난독화는 이 특성을 활용할 수 있음
• Apple의 Rosetta II와 Microsoft의 Prism은 사전 번역과 동적 번역 컴포넌트를 결합함
• WYTIWYG와 Polynima는 동적 프로파일링으로 식별한 제어 흐름 경로를 따라 정적으로 리프팅하고, 보지 못한 목표 주소에 도달하면 동적으로 제어 흐름 정보를 수집하는 폴백을 사용함
• Elevator는 어떤 바이트가 코드인지 데이터인지, 명령어 워드인지 인자인지 결정하지 않고, 실행 파일의 각 바이트를 가능한 모든 해석으로 별도 제어 흐름 경로에 포함함
• 이 방식은 superset disassembly를 정적 재컴파일과 크로스 ISA 컴파일에 적용한 것으로, 디코딩 정밀도를 코드 증가와 맞바꿈

제어 흐름과 상태 보존

• Elevator는 번역된 AArch64 코드 안에서 x64 상태 전체 보존을 원칙으로 동작함
• x64 레지스터와 AArch64 레지스터를 일대일로 매핑해 각 x64 레지스터 상태를 대응 AArch64 레지스터에서 에뮬레이션함
• x64 스택은 AArch64 스택 위에서 직접 에뮬레이션되며, 실행 중 일반적인 스택 확장은 운영체제가 처리함
• 입력 x64 바이너리의 ABI를 분석하지 않고, 외부 코드로 실행이 넘어가거나 돌아오는 지점에서만 x64 System V ABI와 AArch64 Procedure Call Standard 규칙에 따라 ABI 번역을 수행함
• 완전한 상태 보존과 일대일 레지스터 대응 덕분에 각 x64 명령은 앞뒤 명령을 알지 못해도 독립적으로 번역될 수 있음
• 원본 바이너리의 각 실행 가능 바이트 오프셋은 데이터이면서 잠재적 명령 시퀀스의 시작점으로 동시에 해석됨
• 간접 점프, 콜백, 런타임 디스패치처럼 정적으로 분석할 수 없는 모든 잠재 목표에는 재작성된 바이너리 안에 대응 착지점이 생김
• 런타임에는 원본 명령 주소에서 번역된 코드 주소로 가는 조회 테이블을 최종 바이너리에 포함해 목표를 해석함

• 중첩 명령 예시

  • Listing 1은 .byte 0xB0에서 디코드를 시작하면 MOV AL, 0xC3 뒤에 RET이 나오고, 한 바이트 뒤 ReturnC2에서 시작하면 RET만 나오는 구조임
  • 두 디코드는 앞선 jz에서 모두 도달 가능하며, 번역기가 두 바이트에 대해 하나의 해석만 선택하면 한 경로를 놓치게 됨

• 계산된 간접 분기 예시

  • Listing 2는 call Label이 테이블 기준 주소를 만들고, pop rsi로 이를 회수한 뒤 입력 의존 오프셋을 더해 jmp rsi의 목표를 구성함
  • 분기는 인코딩 스트림에서 2바이트 간격으로 놓인 네 개의 inc eax 명령 중 하나로 착지할 수 있음
  • 정적으로 해석 가능한 점프 목표만 재작성하는 번역기는 이런 분기를 착지시킬 위치가 없음

• 호출·반환·분기

  • call, return, branch 명령은 반환 주소 위치, 프로그램 카운터, 조건 플래그 레이아웃이 x64와 AArch64에서 달라 C 타일로 표현할 수 없음
  • 직접 호출은 원본 x64 반환 주소를 에뮬레이션 스택에 푸시하고 callee의 번역 타일로 분기함
  • 간접 호출은 목표가 번역된 바이너리 내부인지 외부 라이브러리인지 확인하고, 내부 목표는 x64 오프셋-타일 테이블로 번역해 해당 타일로 분기함
  • 외부 목표는 AArch64 라이브러리가 돌아올 X30에 역 ABI 번역 gadget 주소를 넣고, exit ABI 번역을 수행한 뒤 외부 목표로 분기함
  • 반환은 에뮬레이션 스택에서 8바이트 반환 주소를 꺼내 내장 x64 바이너리 범위와 비교하고, 내부 반환이면 조회 테이블로 주소를 번역해 해당 타일로 분기함
  • 직접 분기는 번역 시점에 목표가 알려지며, 조건 분기는 X14에 보관된 x64 플래그 비트를 검사하는 AArch64 조건 분기로 번역됨
  • 간접 분기는 간접 호출·반환과 같은 bounds check를 방출하고, 목표가 외부이면 exit ABI 번역을 수행함

타일 기반 번역 파이프라인

• Elevator의 번역은 오프라인 타일 뱅크 생성, 입력 바이너리별 재작성, 최종 패키징의 세 단계로 나뉨
• 오프라인 단계는 x64 명령 의미를 C 함수로 표현하고, 고정된 x64-to-AArch64 레지스터 매핑 아래 피연산자 조합별로 특수화한 뒤 수정된 LLVM 20으로 컴파일해 재사용 가능한 AArch64 바이트 시퀀스를 만듦
• 입력 바이너리별 단계는 superset disassembly를 수행하고, 발견된 각 후보 명령에 대해 이름으로 타일을 찾아 AArch64 바이트 시퀀스를 이어 붙임
• 제어 흐름 전송과 ABI 경계처럼 C 타일로 표현하기 어려운 명령 범주는 손으로 만든 작은 템플릿으로 처리함
• 패키징 단계는 번역된 코드, 원본 x64 바이너리, 주소 조회 테이블, 런타임 드라이버를 결합해 독립 실행 AArch64 바이너리를 생성함

• 오프라인 타일 뱅크

  • x64 명령마다 동등한 AArch64 명령 시퀀스를 손으로 쓰는 방식은 실용적이지 않음
  • ADD Reg8, Reg8 같은 하나의 템플릿도 256개의 구체 레지스터 조합으로 확장되며, 전체 x64 명령 집합에는 레지스터, 메모리 피연산자, 즉시값 주소 지정 변형이 많음
  • Elevator는 각 x64 명령 의미를 작은 C 함수로 작성하고, 구체 피연산자 조합별로 특수화한 뒤 LLVM이 AArch64로 컴파일하게 함
  • ADD Reg8, Reg8 예시에서 템플릿은 목적지 레지스터의 하위 8비트를 8비트 합으로 갱신하고 상위 56비트는 유지해 x64의 부분 레지스터 쓰기 의미를 맞춤
  • x64 ADD Reg8, Reg8은 RFLAGS의 Carry, Parity, Auxiliary Carry, Zero, Sign, Overflow 플래그도 바꾸므로, 단일 반환값만 갖는 C 함수 제약 때문에 플래그 갱신은 별도 플래그 타일로 캡처됨
  • 하나의 x64 명령은 하나 또는 여러 타일에 대응할 수 있으며, 방출 시 이들을 다시 연속으로 붙여 전체 의미를 복원함
  • aarch64_custom_reg 속성은 LLVM이 반환값과 각 인자를 어느 AArch64 레지스터에 배치할지 선언함
  • 고정 매핑은 x64 System V와 AAPCS64의 callee-saved·caller-saved 성격을 맞추고, 정수 인자 레지스터 위치 재배열을 줄이며, 남는 AArch64 callee-saved 레지스터를 향후 그림자 상태용으로 남기도록 선택됨
  • x64의 RFLAGS 비트와 XMM 레지스터 파일도 같은 일대일 원칙 아래 전용 AArch64 레지스터에 보관됨
  • 수정된 LLVM 20은 함수별 aarch64_custom_reg 속성을 처리하고, 에뮬레이션된 x64 상태를 담는 AArch64 레지스터를 레지스터 할당기 안에서 callee-saved로 재분류함
  • TileGen은 C 템플릿을 순회해 허용 가능한 피연산자 조합마다 특수화된 사본을 만들고, 템플릿의 매개변수 위치와 레지스터 매핑으로 속성을 기계적으로 합성함

• 입력 바이너리별 재작성

  • 입력 x64 바이너리가 주어지면 per-binary 단계는 superset disassembly를 수행하고 결과 CFG를 순회함
  • 각 노드에서 포매터는 디코드된 명령의 opcode와 피연산자로부터 타일 이름을 만들며, 여러 타일이 필요한 명령에는 여러 이름을 조합함
  • x64는 스택 포인터 정렬 제한이 없지만, AArch64는 스택 포인터를 메모리 피연산자에 사용할 때 16바이트 정렬을 요구함
  • RSP를 SP에 직접 매핑하면 함수 프롤로그의 연속 PUSH처럼 일반적인 x64 코드 패턴이 AArch64에서 정렬 예외를 일으킬 수 있음
  • Elevator는 타일이 별도 레지스터 X25를 통해 스택에 접근하게 하고, 타일이 실제로 필요로 할 때만 SP를 그 안에 구체화함
  • LLVM으로 컴파일된 타일은 진입 시 16바이트 SP 정렬을 기대하므로, 스필 공간을 할당하는 것으로 감지된 타일을 실행하기 전 SP를 아래로 정렬하고 실행 뒤 복원함
  • 플래그 계산 타일은 상대적으로 비싸기 때문에, 이후 post-dominating 명령에서 읽히기 전에 플래그가 덮어써지는 경우 현재 노드의 플래그 계산을 제거함
  • 현재 미지원 명령은 주로 x64의 AVX2 및 이후 와이드 벡터 확장이며, 해당 위치에는 타일 대신 인터럽트 명령을 삽입함
  • SPECint 2006 전체 평가에서는 전체 x86-64 정수 ISA와 SPECint가 사용하는 SSE 부분집합만으로 모든 벤치마크 실행에 충분했음
  • 추가 명령 지원은 새 타일을 더하는 방식으로 확장 가능하지만, 추가 엔지니어링이 과학적 통찰을 더할 가능성은 낮다고 봄

ABI 경계 처리

• Elevator는 동적 링크 바이너리만 지원함
• 정적 링크 바이너리는 CPUID 같은 아키텍처 특화 명령을 직접 포함할 수 있지만, 동적 링크 바이너리는 이를 libc에 위임하므로 번역 필요가 줄어듦
• 동적 링크 라이브러리와 상호작용할 때 emulated x64 환경과 native AArch64 라이브러리 코드 사이를 오가기 위해 x64 Linux ABI와 AArch64 Linux ABI 사이의 전환을 지원함
• ABI 번역이 필요한 핵심 요소는 인자 배치와 반환 주소 위치임
• System V x64 ABI는 RDI, RSI, RDX, RCX, R8, R9 여섯 레지스터를 인자 레지스터로 사용하고, 추가 인자는 [RSP+8]부터 스택에 전달함
• x64 CALL은 반환 주소를 [RSP]에 저장함
• AArch64 Procedure Call Standard는 X0-X7 여덟 인자 레지스터를 사용하고, 남은 인자를 [SP]의 스택에 두며, 반환 주소는 X30에 저장함

• 외부 라이브러리 호출

  • 번역된 x64 호출이 외부 라이브러리를 목표로 하면 AArch64 호출 규약에 맞게 인자 레이아웃을 바꿔야 함
  • 먼저 SP에서 8을 빼 16바이트 경계에 다시 맞추고, 이미 스택에 있던 x64 반환 주소를 [SP+0x8]에 둠
  • [SP+0x10], [SP+0x18] 위치의 값을 X6, X7로 로드해 x64 코드가 스택에 둔 잠재적 7번째, 8번째 인자를 AArch64 라이브러리가 볼 수 있게 함
  • 남은 잠재 스택 인자는 [SP+0x20]부터 남아 있어 AArch64가 기대하는 위치와 맞지 않음
  • x64 반환 주소와 X6, X7로 옮긴 값을 스택에서 제거하는 방식은 해당 값이 실제 인자가 아니라 caller spill space나 caller 스택에 할당된 구조체 일부일 수 있어 안전하지 않음
  • Elevator는 caller의 스택 레이아웃을 건드리지 않고 n×8 바이트의 추가 스택 공간을 할당한 뒤, 현재 위치에서 잠재 8바이트 인자 n개를 복사함
  • 기본 n은 10이며, 입력 바이너리가 외부 라이브러리 함수에 총 16개보다 많은 인자를 전달하면 설정으로 늘릴 수 있음
  • 마지막으로 외부 라이브러리가 돌아올 gadget 주소를 X30에 저장함

• 외부 라이브러리에서 돌아오기

  • 외부 라이브러리 호출 전 X30에 저장한 gadget으로 제어가 돌아오면, 이전에 복사한 스택 인자를 정리하기 위해 스택 포인터에 n×8을 더함
  • 외부 라이브러리 반환값을 X0에서 emulated x64 코드가 기대하는 RAX 위치인 X9로 이동함
  • 원본 x64 반환 주소와 관련 패딩을 스택에서 꺼내 주소를 번역한 뒤 그곳으로 분기해 원래 CALL 다음 실행을 재개함

• 번역 코드로 들어오는 콜백

  • native AArch64 코드가 번역된 바이너리를 호출하면 AArch64 호출 규약을 x64 호출 규약으로 변환해야 함
  • emulated x64 코드는 7번째와 8번째 인자를 X6, X7이 아니라 스택에서 기대하므로, X7을 먼저 푸시하고 그다음 X6을 푸시해 x64가 기대하는 스택 위치에 배치함
  • callee가 실제로 7번째와 8번째 인자를 기대하지 않으면 이 푸시된 값들은 영향을 주지 않음
  • 외부 라이브러리의 AArch64 branch-and-link 명령이 X30에 넣은 반환 주소를 x64 반환 명령이 기대하는 스택 위치에 푸시함

• 콜백에서 외부 라이브러리로 반환

  • 번역된 코드가 콜백에서 외부 라이브러리로 돌아갈 때는 진입 과정을 반대로 수행함
  • 반환 주소를 스택에서 꺼내고, X6와 X7을 푸시하며 할당한 스택 공간은 스택 포인터에 0x10을 더해 정리함