基于LLVM Pass實作控制流平坦化

文章目錄

基于LLVM Pass實作控制流平坦化
- 0x00. 什麼是LLVM和LLVM Pass
- 0x01. 首先寫一個能跑起來的LLVM Pass
- 0x02. 控制流平坦化的基本思想和實作思路
- 0x03. 基于LLVM Pass實作控制流平坦化
- 0x04. 混淆效果測試

轉載：https://mp.weixin.qq.com/s/FD5YRurcLGh_VlV9GlWB8w

提到代碼混淆時，我首先想到的是著名的代碼混淆工具OLLVM。OLLVM(Obfuscator-LLVM)是瑞士西北應用科技大學安全實驗室于2010年6月份發起的一個項目，該項目旨在提供一套開源的基于LLVM的代碼混淆工具，以增加逆向工程的難度。

OLLVM的核心功能，也就是代碼混淆，基于LLVM的一個重要架構——LLVM Pass。簡單來說，LLVM Pass可以對代碼編譯的結果産生影響，以達到優化、混淆等目的。本文的主要内容即是講解基于LLVM Pass架構的代碼混淆方法，以及動手實作一個簡易的控制流平坦化混淆。

0x00. 什麼是LLVM和LLVM Pass

在學習LLVM Pass之前，我們有必要對LLVM有一些簡單的了解。簡單來說，我們可以把LLVM看成一個先進的編譯器。

傳統編譯器（比如我們熟悉的GCC）的工作原理基本上都是三段式的，可以分為前端（Frontend）、優化器（Optimizer）、後端（Backend）。前端負責解析源代碼，将其翻譯為抽象的文法樹（Abstract Syntax Tree）；優化器對這一中間代碼進行優化；後端則負責将優化器優化後的中間代碼轉換為目标機器的代碼。

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

LLVM本質上還是三段式，但LLVM架構不同語言的前端，會産生語言無關的的中間代碼LLVM Intermediate Representation (LLVM IR)。優化器對LLVM IR進行處理，産生新的LLVM IR，最後後端将LLVM IR轉化為目标平台的機器碼。其過程如下圖所示：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

這樣設計的好處是當我們需要新支援一種語言時，由于統一的中間代碼LLVM IR的存在，我們隻需要實作該語言的前端即可，可拓展性極強。并且我們可以通過LLVM提供的一系列豐富的函數庫操控LLVM IR的生成過程，我們用來操控LLVM IR生成過程的架構被叫做LLVM Pass，官方文檔稱其為“where most of the interesting parts of the compiler exist”，可見其功能之強大。

還有一個容易混淆的點是Clang與LLVM的關系，可以用一張圖來解釋：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

更詳細的内容可以看：深入淺出讓你了解什麼是LLVM

https://www.jianshu.com/p/1367dad95445

0x01. 首先寫一個能跑起來的LLVM Pass

我們的第一個目标是讓我們寫的LLVM Pass能夠順利運作，之後的工作無非是往我們的Pass裡不斷添加内容罷了。

首先我們需要從官網下載下傳LLVM Project中LLVM和Clang部分的源碼，将其放在同一個目錄，編譯。這個過程可以參考知乎上的一個教程——LLVM Pass入門導引以及官方文檔，這裡不再贅述了。我的編譯環境是Ubuntu 18.04、gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0。

官方的教程Writing an LLVM Pass中提供了一個示例，它的作用是列印所有函數的名稱：

test.sh

./build/bin/clang -c -emit-llvm test.cpp -o test.bc./build/bin/opt -load ./build/lib/LLVMHello.so -hello test.bc -o /dev/null

test.cpp

#include <cstdio>
void func1(){}
void func2(){}
int main(){
    puts("Hello!");
}

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

然而示例代碼還是有點複雜，可以把它的代碼簡化一下，友善我們了解：

Obfu.cpp

#include "llvm/IR/Function.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
namespace{
    struct Obfu : public FunctionPass{
        static char ID;
        Obfu() : FunctionPass(ID){}
        bool runOnFunction(Function &F) override{
            outs() << "Function: " << F.getName() << "\n";
            return false;
        }
    };
}
char Obfu::ID = 0;
static RegisterPass<Obfu> X("obfu", "My obfuscating pass");

寫好之後重新編譯LLVM，之前編譯過的話重新編譯的速度會很快，然後運作一下我們寫的Pass：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

OK！這樣後續的混淆功能隻需要在這個架構上添加行了。

0x02. 控制流平坦化的基本思想和實作思路

控制流平坦化(Control Flow Flattening)的基本思想主要是通過一個主分發器來控制程式基本塊的執行流程，例如下圖是正常的執行流程：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

經過控制流平坦化後的執行流程就如下圖：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

可以看到除了基本塊1外，其他的基本塊都集中到了同一個層次上。不同基本塊的排程順序由主分發器決定（在程式裡可以看做一個switch，不同的基本塊就對應不同的case）。這樣可以模糊基本塊之間的前後關系，增加程式分析的難度。

控制流平坦化的過程相當于把原有程式正常的邏輯改為一個循環嵌套一個switch的邏輯。

以上圖代表的程式為例，執行完基本塊1後程式進入主分發器，然後執行基本塊2對應的case。在原邏輯中基本塊2的末尾是一個條件跳轉，可以跳轉到基本塊3或者基本塊4，在平坦化中基本塊2的末尾會根據原有跳轉的條件修改switch變量的值，使其接下來能執行到基本塊3或者基本塊4對應的case，然後傳回主分發器（即進入下一個循環）。

如果是非條件跳轉的話，比如基本塊5到基本塊6，在基本塊5的末尾修改switch變量的值，使下一個循環中switch能到達基本塊6對應的case即可。

用僞代碼表示，未混淆的邏輯是這樣：

基本塊1
基本塊2
if(condition){
	基本塊3
}else{
	基本塊4
}
基本塊5
基本塊6

控制流平坦化的邏輯是這樣：

基本塊1;
switchVar = 2;
while(true){
    switch(switchVar){
        case 2:
            基本塊2;
            switchVar = condition ? 3 : 4;
        case 3:
            基本塊3;
            switchVar = 5;
        case 4:
            基本塊4;
            switchVar = 5;
        case 5:
            基本塊5;
            switchVar = 6;
        case 6:
            基本塊6;
            goto end;
    }
}
end:

0x03. 基于LLVM Pass實作控制流平坦化

LLVM Pass的所有操作都是基于LLVM IR的，是以你需要對LLVM IR有所了解：LLVM IR Tutorial（https://link.zhihu.com/?target=https%3A//llvm.org/devmtg/2019-04/slides/Tutorial-Bridgers-LLVM_IR_tutorial.pdf）

LLVM Pass的一些重要API也很有必要看一看：LLVM Programmer’s Manual（https://llvm.org/docs/ProgrammersManual.html）

控制流平坦化的實作代碼我參考的是：OLLVM控制流平坦化源代碼（https://github.com/obfuscator-llvm/obfuscator/blob/llvm-4.0/lib/Transforms/Obfuscation/Flattening.cpp）

首先把函數的定義移到外面去，讓重點更突出一點，現在我們隻需要關注flatten函數的實作就可以了：

#include "llvm/IR/Function.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/IR/Instructions.h"
#include <vector>
using namespace llvm;
namespace{
    struct Obfu : public FunctionPass{
        static char ID;
        Obfu() : FunctionPass(ID){}
        bool flatten(Function *f);
        bool runOnFunction(Function &F);
    };
}
bool Obfu::runOnFunction(Function &F){
    return flatten(&F);
}
bool Obfu::flatten(Function *f){ }
char Obfu::ID = 0;static RegisterPass<Obfu> X("obfu", "My obfuscating pass");

首先周遊函數中所有基本塊，将其存到一個vector中：

// 周遊函數所有基本塊，将其存到vector中
vector<BasicBlock*> origBB;
for(BasicBlock &BB: *f){
    origBB.push_back(&BB);
}// 基本塊數量不超過1則無需平坦化
if(origBB.size() <= 1){
    return false;
}

根據平坦化的基本思想，第一個基本塊是要單獨拿出來處理的：

// 從vector中去除第一個基本塊
origBB.erase(origBB.begin());
BasicBlock *firstBB = &f->front();

如果第一個基本塊的末尾是一個條件分支，則把條件跳轉的兩個IR指令（類似于彙編裡的cmp和jmp）單獨分離出來作為一個基本塊，友善與非條件跳轉統一處理：

// 如果第一個基本塊的末尾是條件跳轉
if(isa<BranchInst>(firstBB->getTerminator())){
    BranchInst *br = cast<BranchInst>(firstBB->getTerminator());
    if(br->isConditional()){
        CmpInst *cmpInst = cast<CmpInst>(firstBB->getTerminator()->getPrevNode());
        BasicBlock *newBB = firstBB->splitBasicBlock(cmpInst,"newBB");
        origBB.insert(origBB.begin(), newBB);
    }
}

這裡出現了一個函數splitBasicBlock，如果你想知道這個函數到底做了什麼操作，可以直接閱讀源碼内的注釋，其他函數也是一樣。簡而言之，splitBasicBlock函數在給定位置将一個基本塊分為兩個，并且在第一個基本塊的末尾加上一個非條件跳轉：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

有關isa和cast兩個泛型函數的用法，參考上面提到的重要API文檔：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

接下來建立循環的循環頭和循環尾，注意到新建立的基本塊是被插入到firstBB前面的，是以還需要把firstBB移回頂部：

// 建立循環
BasicBlock *loopEntry = BasicBlock::Create(f->getContext(), "loopEntry", f, firstBB);
BasicBlock *loopEnd = BasicBlock::Create(f->getContext(), "loopEnd", f, firstBB);
firstBB->moveBefore(loopEntry);

對第一個基本塊做一些處理，主要包括去除第一個基本塊原來的跳轉，插入初始化switch on變量的指令，插入新的跳轉使其進入循環：

// 去除第一個基本塊末尾的跳轉
firstBB->getTerminator()->eraseFromParent();
// 用随機數初始化switch on變量
srand(time(0));
int randNumCase = rand();
AllocaInst *swVarPtr = new AllocaInst(int32Type, 0, "swVar.ptr", firstBB);
new StoreInst(ConstantInt::get(int32Type, randNumCase), swVarPtr, firstBB);
// 使第一個基本塊跳轉到loopEntry
BranchInst::Create(loopEntry, firstBB);

在loopEntry中插入load指令，load指令類似于C語言裡的指針取值：

// 在進入loopEntry讀取switch on變量
LoadInst *swVar = new LoadInst(int32Type, swVarPtr, "swVar", false, loopEntry);BranchInst::Create(loopEntry, loopEnd);

建立循環内的switch。這裡swVar是LoadInst類型，它被當做switch on的變量傳入了SwitchInst的構造函數，在LLVM Pass中，常數（Constant）、參數（Argument）、指令（Instruction）和函數（Function）都有一個共同的父類Value。Value class是LLVM Pass很重要的基類（參見：The Value class）：

// 初始化switch的default case
// default case實際上不會被執行
BasicBlock *swDefault = BasicBlock::Create(f->getContext(), "swDefault", f, loopEnd);
BranchInst::Create(loopEnd, swDefault);
SwitchInst *swInst = SwitchInst::Create(swVar, swDefault, 0, loopEntry);

建立完switch之後，插入原基本塊到switch中，注意這裡僅是位置意義上的插入，而不是邏輯意義上的：

for(BasicBlock *BB : origBB){
    ConstantInt *numCase = cast<ConstantInt>(ConstantInt::get(int32Type, randNumCase));
    BB->moveBefore(loopEnd);
    swInst->addCase(numCase,BB);
    randNumCase = rand();
}

接下來要從邏輯意義上往switch中插入基本塊了，即添加新的case。

所有基本塊按後繼基本塊的數量分成了三類：

第一類是沒有後繼基本塊，這類基本塊一般是以retn或者call exit結尾的基本塊，統一叫做retn BB這類基本塊不用做處理。
第二類是僅有一個後繼基本塊，即以非條件跳轉結尾的基本塊，在這類基本塊的末尾我們需要更新switch on的變量，使下一輪循環中能夠按原有的邏輯到達下一個基本塊。
第三類是有兩個後繼基本塊，即以條件跳轉結尾的基本塊，在這類基本塊的末尾我們要插入select指令，類似于C語言的三元運算符。

實作代碼如下：

// 添加case
for(BasicBlock *BB : origBB){
    // retn BB
    if(BB->getTerminator()->getNumSuccessors() == 0){
        continue;
    }
    if(BB->getTerminator()->getNumSuccessors() == 1){
        BasicBlock *sucBB = BB->getTerminator()->getSuccessor(0);
        BB->getTerminator()->eraseFromParent();
        ConstantInt *numCase = swInst->findCaseDest(sucBB);
        new StoreInst(numCase, swVarPtr, BB);
        BranchInst::Create(loopEnd, BB);
        continue;
    }
    if(BB->getTerminator()->getNumSuccessors() == 2){
        ConstantInt *numCaseTrue = swInst->findCaseDest(BB->getTerminator()->getSuccessor(0));
        ConstantInt *numCaseFalse = swInst->findCaseDest(BB->getTerminator()->getSuccessor(1));
        BranchInst *br = cast<BranchInst>(BB->getTerminator());
        SelectInst *sel = SelectInst::Create(br->getCondition(), numCaseTrue, numCaseFalse, "", BB->getTerminator());
        BB->getTerminator()->eraseFromParent();
        new StoreInst(sel, swVarPtr, BB);
        BranchInst::Create(loopEnd, BB);
    }
}

至此整個平坦化的過程就已經完成了。

0x04. 混淆效果測試

編譯，運作test.sh測試：

IDA打開，檢視CFG：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

是不是有内味了：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

F5檢視僞代碼，可以看到IDA并沒有像我們預想的那樣識别出switch。經過我的測試如果switch on的變量很規律（比如1,2,3,4,5,6…），IDA就能準确識别出switch，如果是随機數則不行，是以随機數的混淆效果比單純的遞增要好：

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

【轉載】基于LLVM Pass實作控制流平坦化基于LLVM Pass實作控制流平坦化

基于LLVM Pass實作控制流平坦化

文章目錄

0x00. 什麼是LLVM和LLVM Pass

0x01. 首先寫一個能跑起來的LLVM Pass

0x02. 控制流平坦化的基本思想和實作思路

0x03. 基于LLVM Pass實作控制流平坦化

0x04. 混淆效果測試

繼續閱讀

簡明扼要地談談v8的隐藏類和Inline Cache（內聯緩存）

C編譯器反證Fermat大定理

編譯器發展史5個十年3大人物及編譯器知識(公号回複“編譯器”下載下傳PDF資料，歡迎轉發、贊賞、支援科普)

編譯器優化--1--概述簡介編譯器優化–1--概述簡介

在LLVM中使用垃圾收集

編譯器優化–5--消除備援編譯器優化–5--消除備援

不幸的問題還是出現了：Chromium代碼上整理patch（working目錄/master分支），部分檔案做了git checkout恢複，結果GYP再編譯就出錯了

指令選擇器調查（6）5. 基于圖的做法

指令選擇器調查（7完）6. 模拟7. 結論

未定義行為：不隻是程式設計語言

未定義行為 != 不安全的程式設計