💻 computer science

Branch Landing: Bloom Filter-Based Source Authorization for Forward-Edge CFI on RISC-V

The paper proposes Branch Landing (BRL), a RISC-V hardware-assisted CFI framework that uses Bloom filter-based membership queries and lightweight ISA extensions to provide scalable, low-overhead source authorization for forward-edge control flow protection.

Original authors: You Wu, Peter Beerel

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: You Wu, Peter Beerel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a high-security building manager. You have two main ways to keep intruders out, but both have a "blind spot" that clever thieves (hackers) are starting to exploit.

The Problem: The "Identity Crisis" in Security

Currently, computer security uses two main methods to protect the "doors" (indirect jumps) in a program:

The "Uniform" Method (Type-based): This is like saying, "Anyone wearing a blue suit can enter this room." It’s easy to check, but if a thief puts on a blue suit, they get in. They don't have to be a legitimate guest; they just have to look the part.
The "VIP List" Method (Tag-based): This is like having a guest list with specific names. It’s much safer, but the guest list is tiny—it only has room for, say, four names. If a fifth legitimate guest shows up, the security guard has to turn them away because the list is full.

Hackers use a trick called JOP (Jump-Oriented Programming). They don't try to break the door down; they just find a way to "jump" from one legitimate-looking room to another, chaining small actions together to steal data. Because they are using "legitimate" doors, the current security doesn't realize they are actually a thief in a blue suit.

The Solution: "Branch Landing" (The Magic Guest List)

The researchers proposed a new system called Branch Landing (BRL). Instead of checking if a person is wearing the right suit or checking a tiny physical list, they use a Bloom Filter.

Think of a Bloom Filter as a "Magic Fingerprint Scanner."

Instead of a list of names, the security guard has a magical, compact digital pad. When a guest arrives, they press their finger to it. The pad doesn't store the whole name; it just checks a series of complex patterns.

If the pattern doesn't match, the guard knows instantly that this person is an intruder.
If the pattern matches, they are let in.
The best part? The pad is tiny, but it can represent thousands of different guests without ever running out of space.

How it Works (The Two-Step Dance)

BRL uses two new "security moves" built directly into the computer's brain (the RISC-V processor):

The "ID Badge" (bld): Right before a person (a piece of code) moves from one room to another, they must grab a digital ID badge that says exactly who they are.
The "Scanner" (brl): When they arrive at the new room, a scanner immediately checks that ID badge against the "Magic Fingerprint Pad" (the Bloom Filter) for that specific room. If the ID isn't on the "authorized" list, the alarm sounds, and the program stops immediately.

Why is this a big deal?

The researchers tested this on a huge variety of computer programs, and the results were impressive:

It’s incredibly fast: It’s like adding a security checkpoint that takes almost zero time. The "speed penalty" is less than 0.5%—you wouldn't even notice it's there.
It’s tiny: It doesn't take up much extra "storage space" in the computer's memory.
It’s much smarter: It doesn't just check if you're wearing a blue suit; it checks if you specifically are allowed to be in that specific room. It narrowed down the "allowed" targets by over 32%, making it much harder for a hacker to find a way in.

In short: Branch Landing gives computers a way to verify not just where a program is going, but who is allowed to send it there, using a high-speed, high-capacity digital "guest list" that never runs out of room.

Technical Summary: Branch Landing (BRL)

Title: Branch Landing: Bloom Filter-Based Source Authorization for Forward-Edge CFI on RISC-V
Authors: You Wu and Peter Beerel (University of Southern California)

1. The Problem: The "Source-Authorization Gap"

Current Control-Flow Integrity (CFI) mechanisms primarily focus on protecting the "forward-edge" (indirect branches like jalr and jr in RISC-V) to prevent Jump-Oriented Programming (JOP) attacks. However, existing defenses suffer from a lack of precise source-domain authorization:

Coarse Landing-Based CFI (e.g., Intel CET, ARM BTI): These only verify if a destination is a valid "landing site." They do not check which source initiated the jump, allowing attackers to chain legitimate gadgets together.
Type-Based CFI (e.g., Clang CFI): These restrict targets to functions with matching signatures. However, any caller with the same signature is authorized, meaning an attacker can use a legitimate but unintended caller to reach a target.
Tag-Based Hardware CFI (e.g., Bratter): These use hardware registers to store tags for specific sources. The critical flaw is scalability: hardware registers have fixed widths (e.g., a few slots), creating a "hard ceiling." If a target has more legitimate callers than available register slots, the security policy cannot be enforced for the remaining callers.

2. Methodology: The Branch Landing (BRL) Framework

The authors propose Branch Landing (BRL), a framework that shifts the enforcement paradigm from "one-to-one equality checks" (is Tag A == Tag B?) to "set-based membership queries" (is Source SID $\in$ Allowed Set?).

Core Components:

Bloom Filter Integration: Instead of storing individual tags in registers, BRL uses Bloom filters to represent the set of authorized callers for every landing site. This decouples the number of authorized sources from hardware register constraints.
ISA Extensions:
- bld (Branch Landing Descriptor): Inserted before an indirect branch. It writes a Section Identifier (SID) into a dedicated, non-memory-mapped architectural register called BRState.
- brl (Branch Landing Verification): Inserted at the target landing site. It retrieves the target's Bloom filter from a read-only descriptor table and performs a membership query using the SID currently in BRState.
BRState Register: A specialized CSR containing a valid bit and a 31-bit sid field. It is "single-use"—the brl instruction clears the valid bit upon execution to prevent "replay attacks" (reusing authorization from one transfer for another).
Configurable Granularity: The system is policy-agnostic. By changing how SIDs are assigned at compile-time, it can support:
- Function-level (BRL-Func): Similar to type-based CFI.
- Basic-block-level (BRL-CFG): Uses interprocedural CFG analysis to ensure only specific call sites can reach specific targets.

3. Key Contributions

Scalable Source Authorization: Introduced a mechanism that supports an arbitrary number of authorized callers per target using Bloom filters, overcoming the fixed-slot limitations of prior tag-based hardware.
Policy-Agnostic Hardware: Designed a static hardware/ISA substrate (bld/brl) that can implement various security policies (Type-based, CFG-derived, etc.) simply by changing compiler instrumentation.
Efficient Implementation: Developed an LLVM RISC-V backend and a Spike ISA simulator prototype to demonstrate practical viability.

4. Results and Evaluation

The authors evaluated BRL on 81 BEEBS benchmarks using two policies: BRL-Func and BRL-CFG.

Performance Overhead: Extremely low. Under an optimistic 3-cycle latency model (brl3), the mean runtime overhead was only 0.210% (BRL-Func) and 0.421% (BRL-CFG). Even under a conservative 10-cycle model, overhead remained below 1.3%.
Code Size: Minimal growth, averaging 0.46% to 0.52%.
Security Precision: The BRL-CFG policy reduced the average Equivalence Class (EC) size by 32.5% compared to the type-based policy, meaning it significantly narrows the window of opportunity for an attacker.
Correctness: Zero false positives (no legitimate executions were blocked) and zero enforcement failures across all benchmarks.

5. Significance

Branch Landing represents a significant advancement in hardware-assisted CFI. By moving from rigid equality checks to probabilistic set membership, it provides a mathematically sound way to implement fine-grained, context-sensitive security without the prohibitive hardware costs of large register files. It effectively bridges the gap between the high performance of coarse-grained CFI and the high security of fine-grained, CFG-based CFI.