寫一個(gè)倒著跑的 x86-64 程序

Max Xing

http://github.com/MaxXSoft

什么是“倒著跑”的程序？

正常的程序都是正著跑的：CPU 里有一個(gè)程序計(jì)數(shù)器（PC），用來記錄當(dāng)前正在執(zhí)行的指令的地址。執(zhí)行完 PC 處的指令后，CPU 會(huì)接著執(zhí)行 PC+1 處的指令。

而倒著跑的程序指的是：執(zhí)行完 PC 處的指令后，程序回過頭去執(zhí)行 PC-1 處的指令。如果你反匯編這個(gè)程序，你會(huì)看到程序中機(jī)器指令的序列也是完全倒過來的，比如程序看起來會(huì)先調(diào)用函數(shù)，后傳參。

等等，這樣的程序是真實(shí)存在的嗎？

是的，而且我真的寫了一個(gè)這樣的 x86-64 程序，還把它出成了一道 CTF 逆向題！

你可以下載這道題的附件：

prob22-crackme

github.com/PKU-GeekGame/geekgame-2nd/raw/master/official_writeup/ttowrss/attachment/prob22-crackme

然后反匯編看一下：

正著看確實(shí)狗屁不通，反過來理解卻合情合理。最主要的是，這個(gè) Linux 程序真的能在 x86-64 CPU 上跑起來！你可以自己找臺(tái) Ubuntu 20.04 的服務(wù)器嘗試一下。

那么，這個(gè)程序是怎么實(shí)現(xiàn)的呢？

緣起

某天刷知乎的時(shí)候看到了這個(gè)回答：

在游戲的發(fā)展歷史中，出現(xiàn)過哪些有意思的加密反盜版機(jī)制和破解機(jī)制？2542 贊同 · 132 評(píng)論回答

具體的各種爭奪手法差不多可以寫本書了，這里就舉一個(gè)有趣的加密手法：
利用int3讓內(nèi)存里的程序倒序執(zhí)行?；蛘哒f倒序才是正確的打開方式。
本來第n條指令執(zhí)行完畢之后應(yīng)該執(zhí)行第n+1條指令，加密程序利用int3在執(zhí)行完第n條指令之后，把命令指針改成n-1，從而實(shí)現(xiàn)倒序執(zhí)行。
靜態(tài)分析，內(nèi)存里的代碼簡直狗屁不通。
動(dòng)態(tài)跟蹤你就得去截int3?？赡阋淮鄹膇nt3，程序就沒法倒序執(zhí)行了，結(jié)果就更是狗屁不通了，從而達(dá)成防止破解的目的。

我覺得很有意思，剛好當(dāng)時(shí)在籌備下一屆 GeekGame，于是決定把這個(gè)思路出成一道逆向，雖然我自己完全不會(huì)逆向（遺憾）。

但讓一個(gè)合法的 x86-64 程序倒序執(zhí)行，并不是一個(gè)簡單的事情，我們需要考慮很多問題，包括：

• 如何讓 rip 在跑完一條指令之后指向上一條指令，而不是下一條？

• 如何處理分支、跳轉(zhuǎn)，以及函數(shù)調(diào)用？

• 手寫匯編也許可以實(shí)現(xiàn)這樣的事情，但如何把整個(gè)過程自動(dòng)化？

好在思考了一段時(shí)間，外加一通 STFW 之后，我還是找到了一種可行的實(shí)現(xiàn)方法。

實(shí)現(xiàn)思路

倒序執(zhí)行

如何倒序執(zhí)行程序呢？

首先，負(fù)責(zé)執(zhí)行程序的是 CPU。而據(jù)我所知，世界上的絕大多數(shù) CPU，都只會(huì)按照 PC 遞增方向執(zhí)行代碼（控制轉(zhuǎn)移指令除外），同時(shí)也不提供更改代碼執(zhí)行方向的配置選項(xiàng)。

不過并不是說這個(gè)事是解決不了的，或者說，既然 CPU 本身沒辦法解決這個(gè)事，我們也許可以換種思路：

1. 讓 CPU 單步執(zhí)行代碼。

2. 使用軟件接管單步執(zhí)行的流程。

3. 在一次單步執(zhí)行結(jié)束后，修改 PC，使其指向上一條指令而非下一條。

4. 繼續(xù)單步執(zhí)行。

好，之前的問題解決了，但我們又多出三個(gè)問題：

1. 如何讓 CPU 單步執(zhí)行代碼？

2. 如何使用軟件接管單步執(zhí)行的流程？

3. 如何修改 PC 使其指向上一條指令？

我們的目標(biāo)是寫出一個(gè)倒著跑的 x86-64 程序，而在 x86 上，CPU 恰好為我們提供了一種單步執(zhí)行的機(jī)制：trap flag，確切的說是 flags/eflags/rflags 寄存器的第 8 位。

在設(shè)置 trap flag 之后，CPU 會(huì)進(jìn)入單步模式，每執(zhí)行一條指令觸發(fā)一次異常，之后進(jìn)入異常處理程序。而運(yùn)行于 CPU 之上的操作系統(tǒng)，會(huì)根據(jù)異常原因識(shí)別出這一行為，并且通知當(dāng)前執(zhí)行的進(jìn)程發(fā)生了 trap。

在 Linux（或者說 POSIX）中，這種通知機(jī)制由 signal 機(jī)制實(shí)現(xiàn)。發(fā)生 trap 時(shí)，程序會(huì)收到 SIGTRAP 信號(hào)。如需自行處理該信號(hào)，程序可注冊(cè)對(duì)應(yīng)的 signal handler。

不過，一般情況下，SIGTRAP 會(huì)由調(diào)試器觸發(fā)，比如你正在單步調(diào)試。此時(shí)程序內(nèi)是沒有任何 handler 處理這個(gè)信號(hào)的，調(diào)試器會(huì)使用 ptrace 來處理被調(diào)試進(jìn)程的 SIGTRAP。

所以，為了實(shí)現(xiàn)（至少是部分代碼的）倒序執(zhí)行，我們可以在程序啟動(dòng)后設(shè)置 SIGTRAP 的 handler，然后設(shè)置 trap flag，之后在 handler 中處理更新 PC 的邏輯。

那么，如何在 handler 中，將 PC 指向上一條指令呢？

仔細(xì)閱讀 Linux 手冊(cè)中和 signal 相關(guān)的部分，例如 sigaction，其中提到 signal handler 具備三個(gè)參數(shù)，其中第三個(gè)參數(shù) ucontext 的描述如下：

ucontext
This is a pointer to a ucontext_t structure, cast to void *.
The structure pointed to by this field contains signal context information that was saved on the user-space stack by the kernel; for details, see sigreturn(2). Further information about the ucontext_t structure can be found in getcontext(3) and signal(7).
Commonly, the handler function doesn't make any use of the third argument.

也就是說，我們可以借助 ucontext，修改由內(nèi)核保存的，和該進(jìn)程相關(guān)的上下文（context），其中自然包括了所有寄存器的值。在 x86-64 中，我們只需要修改 rip（instruction pointer）寄存器，即可控制程序的 PC，很簡單吧！

然而，上帝這個(gè) byd 在為你打開一扇窗之后，就必然會(huì)關(guān)閉一扇門。在 x86-64 下，我們還需要考慮另一個(gè)問題：作為古老的 CISC 架構(gòu)，x86-64 的指令是變長的，我們沒辦法簡單地通過“將 rip 的值減去固定數(shù)值”的方式，讓程序倒序執(zhí)行。更蛋疼的是，x86-64 的指令編碼是一種前綴碼，你只能通過從前往后掃描來確定指令的邊界，從后往前掃是不行的。

也許這個(gè)問題有很多種解決方式，比如往程序里嗯塞一個(gè) x86-64 decoder（如 iced），或者利用 CPU 來幫我們完成一部分譯碼的任務(wù)（其實(shí)我沒想好這樣要怎么搞）。但在權(quán)衡實(shí)現(xiàn)的復(fù)雜性之后，我還是決定用一種非常簡單粗暴的方式來解決這個(gè)問題：打表。

當(dāng)然，為了進(jìn)一步簡化實(shí)現(xiàn)，縮小程序的體積，我們可以把這個(gè)表壓縮成位圖（bitmap）：也就是說，指定一串?dāng)?shù)據(jù)，其中的每一位對(duì)應(yīng)程序代碼段的每一個(gè)字節(jié)。如果某個(gè)字節(jié)是某條指令的開頭，就將位圖里對(duì)應(yīng)位設(shè)為 1，否則設(shè)為 0。這個(gè)位圖可以提前用其他方式生成，然后嵌入到程序中。

在需要更新 rip 的時(shí)候，我們可以根據(jù) rip 目前的值，找到位圖中的對(duì)應(yīng)位。需要注意的是，在設(shè)置 trap flag 的情況下，CPU 執(zhí)行完一條指令之后，會(huì)將 rip 指向下一條指令，然后再觸發(fā)異常，進(jìn)入 handler。所以我們需要在位圖中找到 rip 對(duì)應(yīng)指令之前第二條指令的開頭，并將 rip 設(shè)為對(duì)應(yīng)的地址。

處理控制流

經(jīng)過一通折騰，我們終于找到了一種可行的方法，將整個(gè)順序執(zhí)行的指令流變成倒序執(zhí)行。不過，現(xiàn)實(shí)世界的程序中，幾乎不可能只有順序執(zhí)行這一種情況，還會(huì)出現(xiàn)分支、跳轉(zhuǎn)、函數(shù)調(diào)用/返回等各類控制流轉(zhuǎn)移的情況。怎么處理這類情況呢？

其實(shí)我們剛剛提出的處理方式已經(jīng)可以完全兼容控制流了，只需要做出一些小小的改動(dòng)?？紤]以下情況：

?inst1 ?inst2 ?jump label1 ?inst3 ?inst4 label1: ?inst5 ?inst6

如果我們把它簡單地連 label 一起倒過來：

?inst6 ?inst5 label1: ?inst4 ?inst3 ?jump label1 ?inst2 ?inst1

然后按照我們剛剛的思路，從 inst1 開始倒序執(zhí)行，你會(huì)發(fā)現(xiàn)：執(zhí)行完 jump 之后，rip 會(huì)指向 inst4。接著進(jìn)入 handler，handler 會(huì)將 rip 前移兩條指令，也就是指向 inst6，然后開始執(zhí)行。

但程序原本的執(zhí)行流程應(yīng)該是，遇到 jump 之后，接著從 inst5 開始執(zhí)行。為了實(shí)現(xiàn)這樣的效果，我們只需要把 label 往后挪一個(gè)指令：

?inst6 ?inst5 ?inst4 label1: ?inst3 ?jump label1 ?inst2 ?inst1

這樣，倒序執(zhí)行時(shí)的執(zhí)行流就和順序時(shí)完全一致了。這種處理方式對(duì)于分支，函數(shù)調(diào)用等等其他控制流指令也同理。不過需要注意以下的情況：

func: ?inst1 ?inst2 ?inst3 ?call func

倒過來之后，我們需要往開頭（或者說結(jié)尾）加兩條別的指令，然后才能把 func label 挪下去：

?call func ?inst3 ?inst2 ?inst1 ?nop func: ?nop

當(dāng)然如果沒出錯(cuò)，這兩條指令永遠(yuǎn)都不會(huì)被執(zhí)行到，所以其實(shí)把它們換成任何指令都是可以的。

自動(dòng)化

首先，很顯然，人肉寫匯編的話，按照上面我們討論的思路手搓一個(gè)倒序執(zhí)行的程序，是完全可行的。

然而，作為一個(gè)能寫腳本就決不躬親的極致懶狗，讓我手搓還不如把我揚(yáng)了——而且這樣一點(diǎn)也不酷。跑個(gè)自動(dòng)化腳本，啪的一下，很快啊，你寫的源代碼直接就變成一個(gè)倒著執(zhí)行的二進(jìn)制了，這才符合我對(duì)計(jì)算機(jī)的想象，科技并帶著趣味。

所以我是怎么實(shí)現(xiàn)自動(dòng)化的呢？首先我決定用 C 來編寫這樣的程序——其實(shí)用什么語言無所謂了，不過 C 會(huì)省心很多。我將前文提到的若干內(nèi)容封裝成了頭文件，包括：

• 設(shè)置 trap flag 和 signal handler 的代碼。

• signal handler 本體，包含 bitmap 的掃描和 rip 的更新操作。

• 預(yù)留出來的用來存放 bitmap 的空位，稍后會(huì)用其他方式替換掉二進(jìn)制里的 bitmap。

• 其他必要的判斷邏輯。例如我們只能倒序執(zhí)行程序里的代碼，而不能倒序執(zhí)行 shared library。為了判斷目前是否需要開啟倒序執(zhí)行，handler 會(huì)判斷 rip 的值是否落在了代碼段內(nèi)，這就要求程序必須獲知代碼段的起始和結(jié)束地址。我們可以通過修改鏈接器腳本（linker script）來實(shí)現(xiàn)這一操作。

任何需要倒序執(zhí)行的程序，只需 include 上述頭文件即可，非常省事。

接下來是負(fù)責(zé)把程序生成的機(jī)器指令倒過來的部分，這部分我選擇用以下方法實(shí)現(xiàn)：

1. 首先 gcc -S 輸出 C 程序?qū)?yīng)的匯編。

2. 然后寫個(gè)腳本，按照前文提到的邏輯把匯編倒過來，同時(shí)修改所有 label 的位置。

3. 指定使用修改過的鏈接器腳本鏈接這個(gè)匯編程序，以便 C 里判斷代碼段范圍的邏輯生效。

最后，我們需要生成 bitmap，然后將其嵌入程序。這里我偷個(gè)懶，用 objdump 掃一遍剛剛得到的二進(jìn)制，然后用腳本簡單解析一下輸出，生成一個(gè) bitmap。最后用 readelf 定位二進(jìn)制內(nèi) bitmap 符號(hào)的偏移量，把 bitmap 寫到二進(jìn)制文件即可。

相關(guān)工具及用法

好消息：我開源了剛剛提到的自動(dòng)化腳本。

如果你也像我一樣閑，希望搞一個(gè)能倒著跑的 x86-64 Linux 程序的話，可以直接參考這套實(shí)現(xiàn)：

A fun tool for generating an x86-64 Linux program that runs in reverse order.

gist.github.com/MaxXSoft/f043eff08634d9ea4bb7296d35a3e73e

具體來說，你需要：

1. 下載 rev.h。

2. 寫一個(gè)普通的 C 語言程序。注意這個(gè)實(shí)現(xiàn)暫不支持多文件（當(dāng)然你感興趣的話可以改改），所以你必須把代碼寫在一個(gè)文件里。

3. 在程序的開頭 include rev.h。

4. 下載 compile_rev.py，執(zhí)行 ./compile_rev.py 你寫的C文件 編譯程序。

5. 程序會(huì)保存在當(dāng)前目錄，運(yùn)行一下看看吧！

說實(shí)話這個(gè)腳本寫的有點(diǎn) tricky，里面依賴了很多 gcc、ld、objdump 和 readelf 的特性。而且，我只測試了給 GeekGame 出題用的那個(gè)程序（以及其他簡單的例子），對(duì)此這個(gè)腳本是可以正常工作的，但我不保證對(duì)于其他的 C 程序，這個(gè)腳本還能生成一個(gè)能跑的 ELF。

為了避免這個(gè)腳本在你的環(huán)境上崩潰，我還提供了一個(gè) Dockerfile。你可以執(zhí)行（請(qǐng)確保你的 CPU 是 x86-64 架構(gòu)）：

docker build -f Dockerfile路徑 -t rev

然后在生成的鏡像里跑這個(gè)腳本，或者測試腳本生成的程序。

你可以用它做什么？

玩。

編輯于 2022-11-28 11:03