Analyzing and Deobfuscating Polaris's BogusControlFlow Pass - Detecting Opaque Predicates with angr
About the author. I’m Colin Xiao — an independent reverse engineer, mostly working solo on contract jobs. I dig into compiled code of every kind, including but not limited to: Android and iOS apps, x86/x64/ARM native binaries, packers and obfuscators, DRM and license checks, network protocols and APIs, crypto and signature algorithms, malware, game binaries, and embedded/IoT firmware. I also handle large-scale data collection and vulnerability research. If you have any project in mind, I’d be glad to take it on — whatever it is, as long as it’s within my wheelhouse. Just reach out. You can reach me on X at @colinxiao_lab or on Telegram at https://t.me/ColinXiao666.
This research is published for educational and defensive purposes. The target sample is anonymized throughout.
Introduction
This obfuscation is an old trick inherited from OLLVM. Simply put: for a basic block, create an identical block before it that contains an opaque predicate (a condition that is always true or always false, so the new block is never actually executed). You can also stuff junk instructions into that new block so a decompiler can’t parse it correctly.
Details here: https://github.com/obfuscator-llvm/obfuscator/wiki/Bogus-control-flow
Implementation details
Let’s analyze it function by function.
1. Cloning a basic block (cloneAlterBasicBlock)
BasicBlock *BogusControlFlow::cloneAlterBasicBlock(BasicBlock *BB) {
ValueToValueMapTy VMap;
BasicBlock *CBB = CloneBasicBlock(BB, VMap, "cloneBB", BB->getParent());
BasicBlock::iterator Iter = BB->begin();
for (Instruction &I : *CBB) {
for (unsigned i = 0; i < I.getNumOperands(); i++) {
Value *V = MapValue(I.getOperand(i), VMap);
if (V) {
I.setOperand(i, V);
}
}
SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
I.getAllMetadata(MDs);
for (std::pair<unsigned, MDNode *> pair : MDs) {
MDNode *MD = MapMetadata(pair.second, VMap);
if (MD) {
I.setMetadata(pair.first, MD);
}
}
I.setDebugLoc(Iter->getDebugLoc());
Iter++;
}
return CBB;
}This clones a basic block, renaming variables and cloning metadata. It makes no modifications — no junk code is added.
2. Splitting basic blocks
/* 将函数中的每个基本块按每 Size 条指令拆分成多个较小的块 */
void BogusControlFlow::splitBasicBlock(Function &F, unsigned Size) {
std::vector<Instruction *> SplitPoints;
for (BasicBlock &BB : F) {
unsigned Idx = 0;
for (auto Iter = BB.getFirstInsertionPt(); Iter != BB.end(); Iter++) {
Instruction &I = *Iter;
if (I.isTerminator()) {
continue;
}
if (Idx % Size == Size - 1) {
SplitPoints.push_back(&I);
}
Idx = (Idx + 1) % Size;
}
}
for (Instruction *I : SplitPoints) {
BasicBlock *BB = I->getParent();
BB->splitBasicBlock(I);
}
}This splits every basic block into smaller blocks of Size instructions. The point is to increase the block count so more opaque predicates can be inserted later.
3. The process function
First, create two variables Var and Var0 at the function entry:
IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
Value *Var = IRB.CreateAlloca(IRB.getInt64Ty());
Value *Var0 = IRB.CreateAlloca(IRB.getInt64Ty());Then derive two values Mod and X:
Mod = 0x100000000 - rand32()
X = randPrime() mod Moduint64_t Mod = 0x100000000 - getRand32();
// X is just a random prime % Mod
uint64_t X =
primes[getRandomNumber() % (sizeof(primes) / sizeof(primes[0]))] % Mod;Both Var and Var0 are initialized to X:
// Both Var and Var0 are set to X at the beginning of the function.
IRB.CreateStore(IRB.getInt64(X), Var);
IRB.CreateStore(IRB.getInt64(X), Var0);Next comes the tricky part. First the code, then the analysis:
std::vector<BasicBlock *> BBs;
for (BasicBlock &BB : F) {
// At the end of each basic block
IRB.SetInsertPoint(BB.getTerminator());
// a*x - b = x (mod m)
// (a - 1) * x = b (mod m)
uint64_t B = getRand32() % Mod;
uint64_t Inv = getInverse(X, Mod);
uint64_t A = ((B * Inv) % Mod + 1) % Mod;
Value *V = IRB.CreateLoad(IRB.getInt64Ty(), Var0);
IRB.CreateStore(
IRB.CreateURem(
IRB.CreateSub(IRB.CreateURem(IRB.CreateMul(IRB.getInt64(A), V),
IRB.getInt64(Mod)),
IRB.getInt64(B)),
IRB.getInt64(Mod)),
Var0);
BBs.push_back(&BB);
}What does that IR actually compute?
%v = load i64, ptr %Var0
%mul = mul i64 A, %v
%rem1 = urem i64 %mul, Mod
%sub = sub i64 %rem1, B
%rem2 = urem i64 %sub, Mod
store i64 %rem2, ptr %VarAs high-level code:
Var0 = ((A * Var0) % Mod - B) % ModWhat does this compute? From the construction:
B = rand32() mod Mod
A = ((B * Inv(X, Mod)) mod Mod + 1) mod ModThe deliberately constructed A and B satisfy:
(A - 1) * X = B mod Modwhere X can be any value less than Mod. Substituting the definitions of A and B verifies it. Rearranging slightly:
A * X = (X + B) mod ModPlugging this into the Var0 transform gives:
So Var0 never actually changes — it stays equal to Var. All that computation is just to stop the compiler/decompiler from optimizing it away.
Note: there’s actually a bug in this implementation. The derivation is correct under mathematical modulo, but the IR uses
sub i64(unsigned 64-bit subtraction) plusurem i64. When(A * X) % Mod < B, thesubunderflows (unsigned), wrapping to a large number near 2^64, so the subsequenturemis no longer equivalent to mathematical modulo. For example, withMod=11, X=3, B=8: mathematically(-8) mod 11 = 3, but in uint640 - 8 = 2^64 - 8, and(2^64 - 8) mod 11 = 8 != 3. This makes the opaque predicate no longer always-true, and the program can loop forever.
Now the block and opaque-predicate injection:
for (BasicBlock *BB : BBs) {
if (isa<InvokeInst>(BB->getTerminator()) || BB->isEHPad() ||
BB->isEntryBlock()) {
continue;
}
BasicBlock *BodyBB =
BB->splitBasicBlock(BB->getFirstNonPHIOrDbgOrLifetime(), "bodyBB");
BasicBlock *TailBB =
BodyBB->splitBasicBlock(BodyBB->getTerminator(), "endBB");
BasicBlock *CloneBB = cloneAlterBasicBlock(BodyBB);
BB->getTerminator()->eraseFromParent();
BodyBB->getTerminator()->eraseFromParent();
CloneBB->getTerminator()->eraseFromParent();
IRB.SetInsertPoint(BB);
if (getRandomNumber() % 2) {
Value *Cond = IRB.CreateICmpEQ(IRB.CreateLoad(IRB.getInt64Ty(), Var),
IRB.CreateLoad(IRB.getInt64Ty(), Var0));
IRB.CreateCondBr(Cond, BodyBB, CloneBB);
} else {
Value *Cond = IRB.CreateICmpNE(IRB.CreateLoad(IRB.getInt64Ty(), Var),
IRB.CreateLoad(IRB.getInt64Ty(), Var0));
IRB.CreateCondBr(Cond, CloneBB, BodyBB);
}
IRB.SetInsertPoint(BodyBB);
if (getRandomNumber() % 2) {
Value *Cond = IRB.CreateICmpEQ(IRB.CreateLoad(IRB.getInt64Ty(), Var),
IRB.CreateLoad(IRB.getInt64Ty(), Var0));
IRB.CreateCondBr(Cond, TailBB, CloneBB);
} else {
Value *Cond = IRB.CreateICmpNE(IRB.CreateLoad(IRB.getInt64Ty(), Var),
IRB.CreateLoad(IRB.getInt64Ty(), Var0));
IRB.CreateCondBr(Cond, CloneBB, TailBB);
}
IRB.SetInsertPoint(CloneBB);
IRB.CreateBr(BodyBB);
}The insertion is a little involved — it’s a graph transformation. The resulting structure:
Source: https://www.apriorit.com/dev-blog/obfuscating-code-to-secure-android-apps
The core is the opaque-predicate construction. If you can optimize the opaque predicate away, the specific insertion layout doesn’t matter — the decompiler prunes the dead blocks automatically.
BogusControlFlow2
Looking quickly at the source, there are two BogusControlFlow passes: BogusControlFlow (the one analyzed above) and BogusControlFlow2. The latter is the simpler version — I believe this is what OLLVM used originally:
Value *createBogusCmp(BasicBlock *insertAfter) {
// if((y < 10 || x * (x + 1) % 2 == 0))
Module *M = insertAfter->getModule();
LLVMContext &context = M->getContext();
GlobalVariable *xptr = new GlobalVariable(
*M, Type::getInt32Ty(context), false, GlobalValue::CommonLinkage,
ConstantInt::get(Type::getInt32Ty(context), 0), "x");
GlobalVariable *yptr = new GlobalVariable(
*M, Type::getInt32Ty(context), false, GlobalValue::CommonLinkage,
ConstantInt::get(Type::getInt32Ty(context), 0), "y");
IRBuilder<> builder(context);
builder.SetInsertPoint(insertAfter);
LoadInst *x = builder.CreateLoad(Type::getInt32Ty(context), xptr);
LoadInst *y = builder.CreateLoad(Type::getInt32Ty(context), yptr);
Value *cond1 =
builder.CreateICmpSLT(y, ConstantInt::get(Type::getInt32Ty(context), 10));
Value *op1 =
builder.CreateAdd(x, ConstantInt::get(Type::getInt32Ty(context), 1));
Value *op2 = builder.CreateMul(op1, x);
Value *op3 =
builder.CreateURem(op2, ConstantInt::get(Type::getInt32Ty(context), 2));
Value *cond2 =
builder.CreateICmpEQ(op3, ConstantInt::get(Type::getInt32Ty(context), 0));
return BinaryOperator::CreateOr(cond1, cond2, "", insertAfter);
}The opaque predicate here is much simpler — no modular inverse. And in Pipeline.cpp, it’s BogusControlFlow2 that’s actually registered as the pass; the more complex BogusControlFlow isn’t used at all.
else if (pass == "bcf") {
FunctionPassManager FPM;
FPM.addPass(BogusControlFlow2());
MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
}Example
After bcf-obfuscating a csmith-generated test sample:
if (iVar4 == 0) {
if (y.12 < 10 || ((x.11 + 1) * x.11 & 1U) == 0) goto LAB_001012af;
do {
local_28->f0 = 1;
LAB_001012af:
local_28->f0 = 1;
} while (9 < y.14 && ((x.13 + 1) * x.13 & 1U) != 0);
}
}
if (y.16 < 10 || ((x.15 + 1) * x.15 & 1U) == 0) goto LAB_0010132a;Note this uses the old BogusControlFlow2, so the opaque predicates are simple.
Deobfuscation prototype
The core is recognizing opaque predicates. The workflow:
- collect: use DDG-based backward slicing to collect all instructions affecting the branch guard.
- merge (optional): an opaque predicate may be split into multiple separate conditions after compilation; merge them into a full predicate. Not encountered in the test samples, so skipped for now.
- solve: use symbolic execution on the collected predicate to get an optimized condition. For BogusControlFlow, the result is simply true or false.
- patch: patch the binary to remove the opaque predicate’s effect on the decompiler.
In practice each step is more involved:
- collect: decide which code constructs to collect. For IndirectCall we just iterate over indirect call sites. BogusControlFlow is trickier — in principle we need to collect over all branch predicates.
- solve: symbolically execute along the slice to the branch, then check whether the guard can only take one value. Since an opaque predicate is always-true or always-false, that’s the signal.
- patch: just patch to a direct jump — not hard.
The implementation:
Step 1: find all branches
Find all conditional-branch instructions in the target function. In VEX IR, a conditional branch block has jumpkind Ijk_Boring and contains an Exit statement (also Ijk_Boring).
def find_branches(proj, func):
result = []
for block_addr in func.block_addrs:
block = proj.factory.block(block_addr)
irsb = block.vex
if irsb.jumpkind == 'Ijk_Boring' and any(
isinstance(s, pyvex.stmt.Exit) and s.jumpkind == 'Ijk_Boring'
for s in irsb.statements
):
branch_insn = block.capstone.insns[-1]
result.append(branch_insn.address)
return resultStraightforward: walk all basic blocks, find those containing a conditional branch (default exit is Ijk_Boring, with an inner Exit also Ijk_Boring), and record the branch instruction’s address.
Step 2: backward slicing
For each branch, do a backward slice to collect all instructions affecting the guard, using angr’s DDG.
def backward_slice_from(proj, cfg, ddg, target_insn_addr):
block_node = cfg.model.get_any_node(target_insn_addr, anyaddr=True)
if block_node is None:
raise RuntimeError(f"No CFG node found containing 0x{target_insn_addr:x}")
irsb = proj.factory.block(block_node.addr).vex
exit_indices = {
i for i, s in enumerate(irsb.statements)
if isinstance(s, pyvex.stmt.Exit)
} or {-2}
seed_nodes = [
n for n in ddg.graph.nodes()
if getattr(n, 'block_addr', None) == block_node.addr
and getattr(n, 'stmt_idx', None) in exit_indices
]
if not seed_nodes:
raise RuntimeError(f"No DDG nodes found for ins_addr=0x{target_insn_addr:x}")
# BFS backward through the DDG
visited = set()
queue = deque(seed_nodes)
slice_cls = set()
while queue:
cl = queue.popleft()
if cl in visited:
continue
visited.add(cl)
slice_cls.add(cl)
for pred in ddg.graph.predecessors(cl):
queue.append(pred)
return slice_clsFlow:
- Find the CFG node containing the target instruction.
- Find all
Exitstatements in the VEX IR — those are the conditional-branch guards. - Find the corresponding DDG nodes as seeds.
- BFS backward from the seeds to collect every node reaching them — the backward slice.
The resulting slice_cls is the set of instructions affecting the branch guard’s value.
Step 3: symbolic-execution solving
With the slice in hand, symbolically execute to decide whether the guard is an opaque predicate.
def analyze_branch_guard(proj, slice_cls, branch_block_addr):
block_addrs = sorted(set(
cl.block_addr for cl in slice_cls if cl.block_addr is not None
))
if branch_block_addr not in block_addrs:
block_addrs.append(branch_block_addr)
state = proj.factory.blank_state(addr=block_addrs[0])
simgr = proj.factory.simgr(state)
for next_addr in block_addrs[1:]:
simgr.step()
simgr.move('active', 'deadended', lambda s, na=next_addr: s.addr != na)
if not simgr.active:
breakCollect and sort all block addresses in the slice, then symbolically execute from the first block, stepping to each next block. After each step, move any state that reached the “wrong” address to the deadended stash — keeping execution on the slice path only.
# 从VEX IR中获取conditional exit语句
irsb = proj.factory.block(branch_block_addr).vex
cond_exit = next(
(s for s in irsb.statements if isinstance(s, pyvex.stmt.Exit)),
None,
)
if cond_exit is None:
return 'unconditional', None
# 在branch block再step一次，观察产生的successor数量
succs = simgr.active[0].step()
if len(succs.successors) == 1:
taken_addr = cond_exit.dst.value
resolved_addr = succs.successors[0].addr
if resolved_addr == taken_addr:
return 'always_true', None
else:
return 'always_false', None
# 有两个successor，用solver检查guard的可满足性
guard = succs.successors[0].history.jump_guard
solver = simgr.active[0].solver
can_be_true = solver.satisfiable(extra_constraints=[guard])
can_be_false = solver.satisfiable(extra_constraints=[claripy.Not(guard)])
if can_be_true and not can_be_false:
return 'always_true', guard
elif can_be_false and not can_be_true:
return 'always_false', guard
else:
return 'symbolic', guardAt the branch block, step once more and check how many successors are produced:
- 1 successor: angr already concretized the guard, so it’s an opaque predicate. Compare the resolved address against the
Exittarget to tellalways_truevsalways_false. - 2 successors: the guard is symbolic. Use the solver to check satisfiability of the guard being true and false:
- only true →
always_true(opaque predicate) - only false →
always_false(opaque predicate) - both →
symbolic(a real branch, not opaque)
- only true →
Step 4: patch
Once a branch is confirmed as an opaque predicate, patch the binary.
def build_slice_patch(proj, slice_cls, target_addr, insn="jmp"):
# 收集slice中所有指令的地址和大小
seen = {}
for cl in slice_cls:
addr = cl.ins_addr
if addr is None or addr in seen:
continue
for i in proj.factory.block(addr).capstone.insns:
if i.address == addr:
seen[addr] = i.size
break
insns = sorted(seen.items())
# 找到第一个连续区域 >= 5 bytes（jmp指令需要5字节）
patch_start = patch_total = None
for i, (addr, size) in enumerate(insns):
run_size = size
for j in range(i + 1, len(insns)):
if insns[j-1][0] + insns[j-1][1] != insns[j][0]:
break
run_size += insns[j][1]
if run_size >= INSN_SIZE:
break
if run_size >= INSN_SIZE:
patch_start, patch_total = addr, run_size
break
# 在找到的区域放置jmp指令，其余全部NOP
asm_bytes, _ = ks.asm(f"{insn} 0x{target_addr:x}", addr=patch_start)
patches = {}
patches[patch_start - file_base] = bytes(asm_bytes) + b'\x90' * (patch_total - len(asm_bytes))
for addr, size in insns:
if patch_start <= addr < patch_start + patch_total:
continue
patches[addr - file_base] = b'\x90' * size
return patchesPatch strategy:
- Collect the addresses and sizes of all instructions in the backward slice.
- Find a contiguous region of at least 5 bytes — the size of an x86-64
jmp rel32. - Place an unconditional
jmp targetthere, targeting the branch the opaque predicate always takes. - NOP out every other instruction in the slice — they only compute the opaque predicate, so removing them doesn’t affect correctness.
Main flow
Tie it together:
proj, main_func, cfg, ddg = load_everything(
TARGET_BINARY, target_func_name=TARGET_FUNC_NAME,
cfg_type="Emulated", auto_load_libs=False
)
branches = find_branches(proj, main_func)
print(f"Found {len(branches)} branches in {TARGET_FUNC_NAME}.")
all_patches = []
for branch_addr in branches:
block_node = cfg.model.get_any_node(branch_addr, anyaddr=True)
block_addr = block_node.addr
slice_cls = backward_slice_from(proj, cfg, ddg, branch_addr)
kind, guard = analyze_branch_guard(proj, slice_cls, block_addr)
print(f" Guard: {kind}")
if kind in ('always_true', 'always_false'):
irsb = proj.factory.block(block_addr).vex
cond_exit = next(s for s in irsb.statements if isinstance(s, pyvex.stmt.Exit))
taken_addr = cond_exit.dst.value
fall_addr = irsb.next.con.value
patch_target = taken_addr if kind == 'always_true' else fall_addr
all_patches.append(build_slice_patch(proj, slice_cls, patch_target, insn='jmp'))
if all_patches:
apply_patches(all_patches, TARGET_BINARY, OUTPUT_BINARY)
print(f"\nWrote {len(all_patches)} patches -> {OUTPUT_BINARY}")For each branch:
- backward slice
- symbolic execution to decide whether it’s an opaque predicate
- if so, pick the correct jump target (
always_true→ taken branch,always_false→ fallthrough) and build the patch - write all patches to the output in one pass
Evaluation
Before (obfuscated):
After deobfuscation:
Limitations
- Works well on simple opaque predicates like
x*(x+1) % 2 == 0; more complex constructions (like the modular-inverse scheme analyzed above) may need stronger constraint solving. - Contiguity assumption in the patch stage. The patch assumes the slice contains a contiguous region of at least 5 bytes for the
jmp. Usually true in practice, but theoretically a slice could be extremely fragmented.
Code
https://github.com/Taardisaa/DePolaris
Colin Xiao — I take on contract reverse-engineering work, and writeups like this are how I show what I can do. If you need help with anything in this space — including but not limited to the areas I cover above — I’m available. No project is too big or too small — if it’s reverse engineering and I can do it, I’ll take it. DM me on X (@colinxiao_lab) or Telegram (@ColinXiao666).
Get in touch