Learning to write a LLVM Pass for Code Obfuscation #2
This blog is a continuation of the previous blog where we covered some basics of C++, created a demo pass and prints function names following the LLVM guide. In this second part, we are gonna Leeroy Genkins it and dive straight into writing LLVM passes.
LLVM, IR and Clang
What even is LLVM IR? I am hoping that people reading this have some idea about what an IR is, but we need to see it in action. So, let’s start with a simple C code:
1 2 3 4 5 6
// classify.c
boolclassify(int x) { if (x > 0) returntrue; elsereturnfalse; }
Then, we can produce the IR with clang as follows:
1
clang -O0 -emit-llvm -S classify.c -o classify.ll
where,
clang is the llvm compiler frontend (for, just the compiler) -O0 turns off optimizations -emit-llvm tells clang to produce LLVM IR rather than native machine code -S tells clang to emit IR in text form
This should produce a classify.ll file as follows:
; Function Attrs: noinline nounwind optnone uwtable
This specifies the function’s attributes(duh!):
noinline: The function must never be inlined into its callers. The optimizer is forbidden from substituting the body at call sites. nounwind: The function does not throw / unwind exceptions. This is standard for C code and lets the compiler skip generating exception-handling (unwind) tables and bookkeeping. optnone: Do not optimize this function. It tells optimization passes to leave the function alone. uwtable: Generate an unwind table for it anyway — stack-frame metadata so debuggers/profilers and stack unwinders can walk the call stack (needed for backtraces, even though the function itself won’t throw).
nounwind and uwtable reflect the language/platform: C functions don’t unwind (nounwind), but the Linux x86-64 ABI still wants unwind tables for reliable backtraces (uwtable).
define: this tells the compiler that this is the actual function definition (with a body) instead of a function declaration. dso_local: this means that the function will live in the same DSO(dynamic shared object) as any code referencing it - which means the compiler can use direct calls without needing to go through PLT/GOT zeroext i1: Since we are returning a bool - which is a 1 bit value (signified by i1) - we need to zero extend the wider register where it is places (ret values are usually returned by placing them in rax) @classify: This is the global symbol name for our function. In LLVM, global symbols are denoted by the @ prefix and local symbols are prefixed by % i32 noundef %0: Remember how the classify() function took an integer as an input? This block specifies exactly that. The i32 means the input is an integer which can never be undefined(noundef) - and %0 is just the variable name #0 : This refers to the attribute group attributes #0 at the bottom - we would leave this for now - and might come back to this later if we need to.
This code block is called the entry block - all calls to the function hHAVE TO pass through this block regardless of the input value. Now one thing to note: LLVM usually assigns labels to code blocks(what is a code block? We will get to a more formal definition later). However when generating the textual IR, it skips naming the entry block but internally, it still consumes a label. LLVM IR, every code block and every value needs a name. We can specify an explicit name, but in our case, we did not, so LLVM assigns sequential integers: %0, %1, %2, and so on. Since we used %0 to denote the input variable, this block uses the (hidden) label 1, so the right definition would be:
The first line reserves a 1 bit address on the stack to hold the return value(%2). The second value(%3) creates a local variable to store the value of the input value locally. The third line copies the value of the input parameter into the slot.
The value stored in %3 is immediately popped back into %4 (yes, this is redundant code - remember we are not optimizing things as all?). %5 stores the value of the operation x>0. The icmp part stands for integers (signed) and the sgt means signed greater than - so this makes sure we are doing a signed comparision against 0 and stores the result. The last line reads as follows: If the 1 bit(i1) stored at %5 is true, jump to %6, else jump to %7. The br keyword represents that the code is branching from the given statement.
The key thing to understand: -O0 puts everything on the stack. It doesn’t try to keep values in registers, so each variable gets an alloca (stack allocation) and is shuffled in/out via store/load. Most optimizations should get rid of the redundant operations.
First, we have the branch labels %6 and %7 (DONT!). Notice the preds = %1 comment? It shows which blocks can reach the respective block. Since both blocks are just preceeded by the entry block aka %1 it says preds=1 (preds=predecessor). Each branch corresponds to each arm of the if/else condition. It stores a 1 bit (i1) value in %2, and then makes an unconditional jump to the code block represented by %8.
The final block is:
1 2
%9 = load i1, ptr %2, align 1 ret i1 %9
We load the value stored in %2 into another variable %9 and return it. Pretty simple, right?
But this code was very inefficient. Let’s see what happens when we turn up the optimization. After compiling with -O3 for examples, the resulting IR becomes:
See, how no variable is reused? A new variable is used with every store/load instruction. This is a small rule which we need to keep in mind for future references.
Now that we understand a bit of IR, time to move onto the next topic: Code blocks
Basic Blocks in LLVM
A basic block is a maximal sequence of instructions with:
exactly one entry point (the first instruction — you can only jump to the top of the block), and
exactly one exit point (the last instruction — control leaves only from the bottom).
This idea creates a bunch of paradigms:
A block has NO BRANCHES in the middle - all code must enter from the entrypoint aka the first instruction and nothing except the last instruction can transfer control elsewhere
Each block has exactly ONE TERMINATOR and it is at the very end. A terminator instruction is one which controls where the control flow goes next. Stuff like if/else, switch case, goto, returns
One thing to note is that a basic block CAN CONTAIN a function call - A normal call is an ordinary instruction. Control returns right after it, so it does not end the block. A call is just another instruction — execution flows into it and out the other side. Only terminators end blocks. (The one exception is invoke, used for exceptions, which is a terminator because it has two outgoing edges: normal return and exception.)
Phi Nodes
When two different paths through the Control Flow Graph(CFG) produce a value that is needed in a block that both paths reach, LLVM IR uses a phi instruction to select the correct value. Let’s take an example:
1 2 3 4 5 6 7
int x; if (condition) { x = 10; } else { x = 20; } int y = x + 1;
In SSA form, we cannot assign to x twice. So LLVM generates:
The phi instruction essentially says: “My value is 10 if I was reached from %true_branch, or 20 if I was reached from %false_branch.”
As a rule, if a basic block has a phi instruction - it must be the first instruction of that block.
Dominators and Dominator Trees
(Sigh)
A Basic Block A is said to dominate Basic Block B if every possible path from the function start to Block B passes through Block A - aka if a control flow is at BLOCK B, it MUST HAVE PASSED THROUGH BLOCK A. It goes without saying that the entry block dominates all other blocks in the function’s CFG.
Tree T is the dominator tree if and only if it has the parent and the sibling properties. In a dominator tree, if a block A immediately dominates block B, then A is the parent of B.
I would highly recommend going through the talk (its just 35 minutes!) or atleast the first 5 minutes.
LLVM C+ API for CFG Traversal
The LLVM Hierarchy Map
1 2 3 4
Module └── Function └── BasicBlock └── Instruction
For C-heads like me, we can think of it like nested Linked Lists:
In C++, LLVM models all of these as iterable containers. The Function class can be iterated like a std::vector<BasicBlock>, and the BasicBlock class can be iterated like a std::vector<Instruction>.
Iterating over Basic Blocks in a Function
Time to write some code - let’s write a program which iterates over all the basic blocks in a Function and prints some basic information.
static std::string blockLabel(const BasicBlock &BB){ // Prefer the block's own name; fall back to "<unnamed>". if (BB.hasName()) return BB.getName().str(); return"<unnamed>"; }
structBlockIterator: public PassInfoMixin<BlockIterator> { PreservedAnalyses run(Module &M, ModuleAnalysisManager &){ for (Function &F: M) { if (F.isDeclaration()) { outs() << "[+] Found Declaration: " << F.getName() << "\n"; continue; }
outs() << "[+] Found Function: " << F.getName() << "\n";
So everything works out just as we wanted! That’s good news. Now we know how to get down to the instruction level with LLVM. Now while I want to end the blog here(brain.exe isn’t working), there is one last thing I want to do.
Spliting Blocks for fun
So far we have only printed values instead of actually modifying stuff. This time we are gonna do that. The idea is simple: you take a basic block and split it into two basic blocks.
(We will just write the run() function for this.)
First, here’s the logic: If a basic block has more than 4 instructions, we split it into two blocks - connecting them with an unconditional jump.
For that, we need to maintain a list of all the blocks which have more than 4 instructions. We can use a helper function to do the calculations for us:
1 2 3 4 5 6 7 8 9 10
staticunsignedcountSplittableInstructions(BasicBlock &BB){ unsigned Count = 0; for (Instruction &I : BB) { // Skip PHI nodes (must stay at block start) and the terminator if (isa<PHINode>(&I)) continue; if (I.isTerminator()) continue; Count++; } return Count; }
We iterate over the instructions in the Basic block and first check if it is a PHI Node as it must stay at the block start. For this check we use the isa function template. It answers: “is this object actually a T at runtime?”.
Usually in C++ we use a dynamic_cast which returns nullptr if a value is NOT of the provided type. But it is slow and LLVM provided isa to make things faster. LLVM avoids standard C++ RTTI for performance. Instead, every Value subclass stores a numeric ValueID set at construction. isa calls T::classof(), which just compares that integer:
1 2 3 4
// Simplified version of what LLVM generates internally staticboolclassof(const Value *V){ return V->getValueID() == Value::BranchInstVal; }
No vtable lookup, no string comparison — just an integer range check. Now back to the original code.
We also check if the instruction is a Terminator (since there is no class for Terminators, we cannot call isa on it). Finally, we return the number of instructions. Simple enough.
Next up, we call the function from run() and pass all basic blocks through this function and store all the blocks with more than 4 instructions in a vector:
1 2 3 4 5 6 7 8
std::vector<BasicBlock *> BlocksToSplit;
for (BasicBlock &BB : F) { unsigned NumInstr = countSplittableInstructions(BB); if (NumInstr > 4) { BlocksToSplit.push_back(&BB); } }
Once we have a list of target blocks, we iterate over it to split it down the middle.
Instruction *SplitInstr = getInstructionAt(*BB, SplitAt); if (!SplitInstr) continue;
outs() << "BlockSplitter: splitting block '" << BB->getName() << "' in function '" << F.getName() << "' at instruction " << SplitAt << "/" << NumInstr << "\n";
// Split the block. The new block starts at SplitInstr. BasicBlock *NewBB = BB->splitBasicBlock(SplitInstr, BB->getName() + ".split"); outs() << " Created new block: " << NewBB->getName() << "\n"; Changed = true; }
Here is a breakdown:
First we get the number of instructions using the same helper function countSplittableInstructions. Then we get the get the midpoint and use another helper function getInstructionAt() to get the instruction at that position :
1 2 3 4 5 6 7 8 9 10
static Instruction *getInstructionAt(BasicBlock &BB, unsigned Idx){ unsigned Count = 0; for (Instruction &I : BB) { if (isa<PHINode>(&I)) continue; if (I.isTerminator()) continue; if (Count == Idx) return &I; Count++; } returnnullptr; }
It’s pretty similar to the last function - skip PHI Nodes, skip the terminator and if the index of the Instruction matches - return the pointer to the Instruction.
Returning to the run() function, once we have our pointer and it’s not nullptr - we print some information, and then split it using splitBasicBlock(). This is a function we need to talk about.
It essentially divides a block at a specific instruction.
1 2 3 4 5 6 7 8 9 10 11 12
Before split: After split at I3: +----------+ +----------+ | I1 | | I1 | (original block, now ends with br) | I2 | | I2 | | I3 | <-- split +----------+ | I4 | | | I5 | v +----------+ +----------+ | I3 | (new block starts here) | I4 | | I5 | +----------+
One important thing to note: whenever we update the CFG - we need to update the Dominator Tree. There are a couple of ways of doing this. For our example, we would invalidate the current analysis and tell LLVM to throw away cached results and recompute from scratch next time. This is exactly what we do in this example. So far, we have been calling PreservedAnalyses::all() and returning it. In this case however, once we have updated the CFG, we invalidate the CFG dependent analysis:
1 2 3 4 5
if (!Changed) return PreservedAnalyses::all();
PreservedAnalyses PA; return PA;
If there were no splits, we dont need to recompute stuff and can return the usual PreservedAnalyses::all() or else force a recomputation.
Finally, we have one last piece:
1
staticboolisRequired(){ returntrue; }
This tells the LLVM that: “Hey this pass is not optional and you need to run it on every pass - it is not optional”. Putting it all together:
BlockSplitter: splitting block '' in function 'classify' at instruction 2/5 Created new block: .split BlockSplitter: splitting block '' in function 'oddoreven' at instruction 3/6 Created new block: .split
And create the splits.ll file. In the original classify.ll file, we have the following IR:
