什么是“倒著跑”的程序？
正常的程序都是正著跑的：CPU 里有一個程序計數(shù)器（PC），用來記錄當(dāng)前正在執(zhí)行的指令的地址。執(zhí)行完 PC 處的指令后，CPU 會接著執(zhí)行 PC+1 處的指令。
而倒著跑的程序指的是：執(zhí)行完 PC 處的指令后，程序回過頭去執(zhí)行 PC-1 處的指令。如果你反匯編這個程序，你會看到程序中機器指令的序列也是完全倒過來的，比如程序看起來會先調(diào)用函數(shù)，后傳參。
等等，這樣的程序是真實存在的嗎？
是的，而且我真的寫了一個這樣的 x86-64 程序，還把它出成了一道 CTF 逆向題！
你可以下載這道題的附件：
然后反匯編看一下：
IDA 反匯編的結(jié)果
正著看確實狗屁不通，反過來理解卻合情合理。最主要的是，這個 Linux 程序真的能在 x86-64 CPU 上跑起來！你可以自己找臺 20.04 的服務(wù)器嘗試一下。
這個程序真的能跑
那么，這個程序是怎么實現(xiàn)的呢？
緣起
某天刷知乎的時候看到了這個回答：
具體的各種爭奪手法差不多可以寫本書了，這里就舉一個有趣的加密手法：
利用int3讓內(nèi)存里的程序倒序執(zhí)行。或者說倒序才是正確的打開方式。
本來第n條指令執(zhí)行完畢之后應(yīng)該執(zhí)行第n+1條指令，加密程序利用int3在執(zhí)行完第n條指令之后，把命令指針改成n-1，從而實現(xiàn)倒序執(zhí)行。
靜態(tài)分析，內(nèi)存里的代碼簡直狗屁不通。
動態(tài)跟蹤你就得去截int3。可你一篡改int3，程序就沒法倒序執(zhí)行了，結(jié)果就更是狗屁不通了，從而達成防止破解的目的。
我覺得很有意思，剛好當(dāng)時在籌備下一屆 ，于是決定把這個思路出成一道逆向，雖然我自己完全不會逆向（遺憾）。
但讓一個合法的 x86-64 程序倒序執(zhí)行，并不是一個簡單的事情，我們需要考慮很多問題，包括：
好在思考了一段時間，外加一通 STFW 之后，我還是找到了一種可行的實現(xiàn)方法。
實現(xiàn)思路倒序執(zhí)行
如何倒序執(zhí)行程序呢？
首先，負責(zé)執(zhí)行程序的是 CPU。而據(jù)我所知，世界上的絕大多數(shù) CPU，都只會按照 PC 遞增方向執(zhí)行代碼（控制轉(zhuǎn)移指令除外），同時也不提供更改代碼執(zhí)行方向的配置選項。
不過并不是說這個事是解決不了的，或者說，既然 CPU 本身沒辦法解決這個事，我們也許可以換種思路：
讓 CPU 單步執(zhí)行代碼。使用軟件接管單步執(zhí)行的流程。在一次單步執(zhí)行結(jié)束后，修改 PC，使其指向上一條指令而非下一條。繼續(xù)單步執(zhí)行。
好，之前的問題解決了，但我們又多出三個問題：
如何讓 CPU 單步執(zhí)行代碼？如何使用軟件接管單步執(zhí)行的流程？如何修改 PC 使其指向上一條指令？
我們的目標(biāo)是寫出一個倒著跑的 x86-64 程序，而在 x86 上，CPU 恰好為我們提供了一種單步執(zhí)行的機制：trap flag，確切的說是 flags// 寄存器的第 8 位。
8086 的 flags 寄存器，第 8 位為 TF
在設(shè)置 trap flag 之后，CPU 會進入單步模式，每執(zhí)行一條指令觸發(fā)一次異常，之后進入異常處理程序。而運行于 CPU 之上的操作系統(tǒng)，會根據(jù)異常原因識別出這一行為，并且通知當(dāng)前執(zhí)行的進程發(fā)生了 trap。
在 Linux（或者說 POSIX）中，這種通知機制由 機制實現(xiàn)。發(fā)生 trap 時，程序會收到 信號。如需自行處理該信號，程序可注冊對應(yīng)的 。
不過，一般情況下， 會由調(diào)試器觸發(fā)，比如你正在單步調(diào)試。此時程序內(nèi)是沒有任何 處理這個信號的，調(diào)試器會使用 來處理被調(diào)試進程的 。
所以，為了實現(xiàn)（至少是部分代碼的）倒序執(zhí)行，我們可以在程序啟動后設(shè)置 的 ，然后設(shè)置 trap flag，之后在 中處理更新 PC 的邏輯。
那么，如何在 中，將 PC 指向上一條指令呢？
仔細閱讀 Linux 手冊中和 相關(guān)的部分，例如 ，其中提到 具備三個參數(shù)，其中第三個參數(shù) 的描述如下：
This is a to a , cast to void *.
The to by this field that was saved on the user-space stack by the ; for , see (2). about the can be found in (3) and (7).
, the doesn't make any use of the third .
也就是說，我們可以借助 ，修改由內(nèi)核保存的，和該進程相關(guān)的上下文（），其中自然包括了所有寄存器的值。在 x86-64 中，我們只需要修改 rip（ ）寄存器，即可控制程序的 PC，很簡單吧！
然而，上帝這個 byd 在為你打開一扇窗之后，就必然會關(guān)閉一扇門。在 x86-64 下，我們還需要考慮另一個問題：作為古老的 CISC 架構(gòu)，x86-64 的指令是變長的，我們沒辦法簡單地通過“將 rip 的值減去固定數(shù)值”的方式，讓程序倒序執(zhí)行。更蛋疼的是，x86-64 的指令編碼是一種前綴碼，你只能通過從前往后掃描來確定指令的邊界，從后往前掃是不行的。
x86 的變長指令編碼
也許這個問題有很多種解決方式，比如往程序里嗯塞一個 x86-64 （如 iced），或者利用 CPU 來幫我們完成一部分譯碼的任務(wù)（其實我沒想好這樣要怎么搞）。但在權(quán)衡實現(xiàn)的復(fù)雜性之后，我還是決定用一種非常簡單粗暴的方式來解決這個問題：打表。
當(dāng)然，為了進一步簡化實現(xiàn)，縮小程序的體積，我們可以把這個表壓縮成位圖（）：也就是說，指定一串?dāng)?shù)據(jù)，其中的每一位對應(yīng)程序代碼段的每一個字節(jié)。如果某個字節(jié)是某條指令的開頭，就將位圖里對應(yīng)位設(shè)為 1，否則設(shè)為 0。這個位圖可以提前用其他方式生成，然后嵌入到程序中。
在需要更新 rip 的時候，我們可以根據(jù) rip 目前的值，找到位圖中的對應(yīng)位。需要注意的是，在設(shè)置 trap flag 的情況下，CPU 執(zhí)行完一條指令之后，會將 rip 指向下一條指令，然后再觸發(fā)異常，進入 。所以我們需要在位圖中找到 rip 對應(yīng)指令之前第二條指令的開頭，并將 rip 設(shè)為對應(yīng)的地址。
處理控制流
經(jīng)過一通折騰，我們終于找到了一種可行的方法，將整個順序執(zhí)行的指令流變成倒序執(zhí)行。不過，現(xiàn)實世界的程序中，幾乎不可能只有順序執(zhí)行這一種情況，還會出現(xiàn)分支、跳轉(zhuǎn)、函數(shù)調(diào)用/返回等各類控制流轉(zhuǎn)移的情況。怎么處理這類情況呢？
其實我們剛剛提出的處理方式已經(jīng)可以完全兼容控制流了，只需要做出一些小小的改動。考慮以下情況：
inst1
inst2
jump label1
inst3
inst4
label1:
inst5
inst6如果我們把它簡單地連 label 一起倒過來：
inst6
inst5
label1:
inst4
inst3
jump label1
inst2
inst1然后按照我們剛剛的思路，從 inst1 開始倒序執(zhí)行，你會發(fā)現(xiàn)：執(zhí)行完 jump 之后，rip 會指向 inst4。接著進入 ， 會將 rip 前移兩條指令，也就是指向 inst6，然后開始執(zhí)行。
但程序原本的執(zhí)行流程應(yīng)該是，遇到 jump 之后，接著從 inst5 開始執(zhí)行。為了實現(xiàn)這樣的效果，我們只需要把 label 往后挪一個指令：
inst6
inst5
inst4
label1:
inst3
jump label1
inst2
inst1這樣，倒序執(zhí)行時的執(zhí)行流就和順序時完全一致了。這種處理方式對于分支，函數(shù)調(diào)用等等其他控制流指令也同理。不過需要注意以下的情況：
func:
inst1
inst2
inst3
call func倒過來之后，我們需要往開頭（或者說結(jié)尾）加兩條別的指令，然后才能把 func label 挪下去：
call func
inst3
inst2
inst1
nop
func:
nop當(dāng)然如果沒出錯直接用二進制寫程序，這兩條指令永遠都不會被執(zhí)行到，所以其實把它們換成任何指令都是可以的。
自動化
首先，很顯然，人肉寫匯編的話，按照上面我們討論的思路手搓一個倒序執(zhí)行的程序，是完全可行的。
然而，作為一個能寫腳本就決不躬親的極致懶狗，讓我手搓還不如把我揚了——而且這樣一點也不酷。跑個自動化腳本，啪的一下，很快啊，你寫的源代碼直接就變成一個倒著執(zhí)行的二進制了，這才符合我對計算機的想象，科技并帶著趣味。
所以我是怎么實現(xiàn)自動化的呢？首先我決定用 C 來編寫這樣的程序——其實用什么語言無所謂了，不過 C 會省心很多。我將前文提到的若干內(nèi)容封裝成了頭文件，包括：
任何需要倒序執(zhí)行的程序，只需 上述頭文件即可，非常省事。
接下來是負責(zé)把程序生成的機器指令倒過來的部分，這部分我選擇用以下方法實現(xiàn)：
首先 gcc -S 輸出 C 程序?qū)?yīng)的匯編。然后寫個腳本，按照前文提到的邏輯把匯編倒過來，同時修改所有 label 的位置。指定使用修改過的鏈接器腳本鏈接這個匯編程序，以便 C 里判斷代碼段范圍的邏輯生效。
最后，我們需要生成 ，然后將其嵌入程序。這里我偷個懶，用 掃一遍剛剛得到的二進制，然后用腳本簡單解析一下輸出，生成一個 。最后用 定位二進制內(nèi) 符號的偏移量，把 寫到二進制文件即可。
相關(guān)工具及用法
好消息：我開源了剛剛提到的自動化腳本。
如果你也像我一樣閑，希望搞一個能倒著跑的 x86-64 Linux 程序的話，可以直接參考這套實現(xiàn)：
具體來說，你需要：
下載 rev.h。寫一個普通的 C 語言程序。注意這個實現(xiàn)暫不支持多文件（當(dāng)然你感興趣的話可以改改），所以你必須把代碼寫在一個文件里。在程序的開頭 rev.h。下載 .py，執(zhí)行 ./.py 你寫的C文件 編譯程序。程序會保存在當(dāng)前目錄，運行一下看看吧！
說實話這個腳本寫的有點直接用二進制寫程序，里面依賴了很多 gcc、ld、 和 的特性。而且，我只測試了給 出題用的那個程序（以及其他簡單的例子），對此這個腳本是可以正常工作的，但我不保證對于其他的 C 程序，這個腳本還能生成一個能跑的 ELF。
為了避免這個腳本在你的環(huán)境上崩潰，我還提供了一個 。你可以執(zhí)行（請確保你的 CPU 是 x86-64 架構(gòu)）：
docker build -f Dockerfile路徑 -t rev然后在生成的鏡像里跑這個腳本，或者測試腳本生成的程序。
你可以用它做什么？
玩。