FastFilter Anti-Phishing Pipeline

1. Overview

The FastFilter module provides a header-only, ultra-fast anti-phishing decision engine designed for high-throughput URL screening in desktop AV and endpoint protection workloads.

The engine implements a layered detection pipeline optimized for early exits and predictable latency:

  • Bloom filter pre-check (probabilistic negative filter)
  • Aho–Corasick automaton for multi-pattern substring matching
  • Optional RE2 safe-regex stage for higher-precision rules
  • LRU cache for repeated URL lookups
  • SQLite loader and file loaders for rule ingestion

The module is written in C++17, supports drop-in inclusion, and provides thread-safe read operations for the hot-path (check_url()) via an immutable data layout after build-time.

2. Dataflow and Pipeline Stages

The evaluation path for each URL is strictly staged to minimize CPU work:

  1. Normalize input (lowercase)
  2. Cache lookup (LRU, keyed by 64-bit Murmur3 hash)
  3. Bloom negative test (fast reject if not present)
  4. Aho–Corasick scan (substring match across rule-set)
  5. Optional RE2 scan (partial-match against safe regex rules)
  6. Cache store (persist verdict for subsequent hits)

The engine is designed so that the most expensive stages (AC scan, regex checks) are only executed after passing cheaper probabilistic and cache gates.

3. Build and Integration

3.1 Header-Only Inclusion

The module is distributed as a single header file (fast_filter.h). It can be included directly into a C++17 project:

#define FASTFILTER_IMPLEMENTATION
#include "fast_filter.h"

No separate compilation unit is required.

3.2 Optional Dependencies

  • SQLite: required for load_patterns_sqlite() (-lsqlite3 or amalgamation)
  • RE2: optional; enabled by defining FASTFILTER_USE_RE2 and linking against -lre2

3.3 Recommended Usage Pattern

In production usage, rules are typically loaded from SQLite at startup:

fastfilter::Config cfg;
cfg.cache_capacity = 100000;
cfg.bloom_fp_rate = 0.01;

fastfilter::Engine eng(cfg);
eng.load_patterns_sqlite("/path/to/db.sqlite", "phishing_rules");

auto verdict = eng.check_url("https://bad.example/phish");
if (verdict.block) { /* enforce block */ }

4. Core Utilities and Hashing

4.1 Murmur3 64-bit Hash

The engine uses a 64-bit Murmur3 hash (x64_128 truncated) as a fast, non-cryptographic digest for:

  • LRU cache keys
  • Bloom filter hashing (double-hash technique)

The implementation includes:

  • rotl64() rotation helper
  • fmix64() finalization function
  • murmur3_64(key, len, seed) with configurable seed

Different seeds are used to derive independent hashes for Bloom filter hashing.

5. Bloom Filter Stage

5.1 Purpose

The Bloom filter provides a constant-time, memory-efficient probabilistic membership test that is used to quickly reject URLs that cannot match any known substring pattern.

A Bloom negative result is treated as a definitive non-match and returns immediately.

5.2 Parameterization

The Bloom filter is initialized via:

Bloom::init(n_items, fp_rate)

It computes:

  • m (number of bits) using: m = - (n * ln(fp)) / (ln2^2)
  • k (number of hashes) using: k = (m/n) * ln2

Bit storage uses a compact byte buffer (std::vector<uint8_t>) with bit addressing.

5.3 Hashing Strategy

Insertion and lookup use a double-hash scheme:

  • h1 = murmur3_64(s, seed1)
  • h2 = murmur3_64(s, seed2)
  • Hashes are generated as: h1 + i*h2 for i in [0..k-1]

6. Aho–Corasick Matcher

6.1 Purpose

The Aho–Corasick stage provides deterministic multi-pattern substring matching in a single pass over the URL string.

Patterns are inserted as lowercased strings and the input URL is normalized to lowercase before scanning.

6.2 Automaton Representation

The automaton uses a compact node structure:

  • next: transition map (std::unordered_map<char,int>)
  • fail: failure link index
  • out: terminal marker indicating at least one pattern ends at this node

The matcher stores nodes in a contiguous vector (std::vector<ACNode>) to improve locality relative to pointer-heavy designs.

6.3 Build Phase

Automaton construction occurs in two stages:

  1. Insert patterns using Automaton::add()
  2. Build failure links using BFS via Automaton::build()

During build, each node propagates terminal state:

  • g.out = g.out || g[g.fail].out

This ensures that matches on failure transitions are detected without additional output lists.

6.4 Search Execution

The search scans the normalized URL once:

  • Transition on matching characters
  • Follow failure links on mismatch
  • Return immediately on first terminal state (out == true)

The engine intentionally exposes a boolean match decision (search_any()) rather than full match metadata to keep the hot-path minimal.

7. Optional Safe Regex Stage (RE2)

7.1 Enablement

Regex support is compiled only when FASTFILTER_USE_RE2 is defined. Without this macro, regex loading returns false and the runtime stage is skipped.

7.2 Regex Loading Format

Regex patterns are loaded from a file where relevant lines begin with:

Pattern:

The parser strips the prefix, trims the remainder, and compiles each pattern into an RE2 object.

7.3 Regex Evaluation

When enabled, regex evaluation occurs only after an Aho–Corasick hit:

  • Each pattern is checked using RE2::PartialMatch()
  • A match triggers an immediate block=true verdict with stage REGEX
  • If no regex matches, the engine still blocks based on AC match (ac-match)

This strategy positions regex as a precision enhancement step rather than a primary detector.

8. LRU Cache

8.1 Purpose

The LRU cache is designed to reduce CPU usage and memory churn when the same URLs (or equivalent normalized URLs) are evaluated repeatedly, which is common in browser/network monitoring scenarios.

8.2 Implementation Details

The cache uses:

  • std::list<uint64_t> for eviction order (most-recent at front)
  • std::unordered_map mapping key → (verdict, iterator)

Operations:

  • get() updates recency on hit and returns cached verdict
  • put() inserts/updates and evicts the least-recent entry when capacity is reached

Cache keys are computed as Murmur3-64 of the normalized URL.

8.3 Capacity Control

Capacity is configurable via Config::cache_capacity (default: 100000).

9. Rule Loading

9.1 Loading from Text Files

The engine supports loading substring patterns from a plain text file:

bool Engine::load_patterns_file(const std::string& path)

File parsing rules:

  • Lines are trimmed
  • Empty lines are ignored
  • Comment lines starting with # are ignored
  • Patterns are normalized to lowercase before insertion

After loading, the engine builds:

  • Bloom filter (initialized with total pattern count)
  • Aho–Corasick automaton (insert + build)

9.2 Loading from SQLite

Recommended production ingestion uses SQLite:

bool Engine::load_patterns_sqlite(const std::string& db_path, const std::string& table)

The loader executes:

SELECT pattern, is_regex FROM <table>;

Rows are processed as follows:

  • pattern is trimmed and lowercased
  • If is_regex is false: the pattern is added to Bloom and Aho–Corasick
  • If is_regex is true: the pattern is stored as a regex candidate (compiled only if RE2 is enabled)

After ingestion:

  • Bloom filter and Aho–Corasick are rebuilt from substring patterns
  • Regex vector is replaced atomically (compile phase) when RE2 is enabled
  • total_patterns tracks substring rule count (non-regex)

Database connections and statements are closed/finalized deterministically (sqlite3_finalize, sqlite3_close).

10. check_url() Runtime Behavior

10.1 Normalization

The input URL is normalized to lowercase to provide case-insensitive matching consistency across all stages.

10.2 Cache First Strategy

Before any rule evaluation, the engine checks the LRU cache using the normalized URL hash.

On cache hit:

  • The function returns immediately
  • The returned verdict includes a “cache-hit” rationale

10.3 Bloom Negative Exit

If the Bloom filter is uninitialized or returns a negative test (might_contain == false), the URL is treated as clean and the result is cached as false.

This provides a high-performance reject path for the vast majority of benign URLs.

10.4 Aho–Corasick Match Decision

If Bloom is positive, the engine executes the Aho–Corasick scan. Behavior:

  • No match → allow, cache false, return ac-nohit
  • Match → proceed to regex stage (if enabled), otherwise block immediately

10.5 Regex Refinement (Optional)

If RE2 is enabled and regexes are loaded:

  • Any regex partial match results in block=true with stage REGEX
  • If no regex matches, the engine still blocks based on AC match with stage AC

If RE2 is not enabled, an Aho–Corasick hit always yields block=true.

11. Output Contract

The runtime decision is returned as a Verdict structure:

  • block – boolean enforcement decision
  • stage – indicates which pipeline stage determined the outcome (BLOOM, AC, REGEX)
  • why – a short rationale string (e.g., bloom-negative, ac-nohit, regex-match)

The module also exposes get_pattern_count() for reporting and diagnostics.

12. Runtime and Security Considerations

  • Deterministic runtime: staged early-exit design bounds CPU work for most inputs (cache/bloom dominate)
  • Memory efficiency: Bloom filter compact bit-array reduces memory relative to large hash sets
  • Safe regex engine: RE2 (when enabled) avoids catastrophic backtracking by design
  • Case normalization: all matching is performed on lowercased input to avoid bypass via casing
  • Rule integrity: SQLite ingestion relies on trusted table schema (pattern TEXT, is_regex INTEGER)
  • Cache semantics: cache key uses a non-cryptographic hash; collisions are statistically unlikely but not impossible and should be considered if used in adversarial contexts
  • Thread safety note: the hot-path is designed for concurrent reads after build, but the cache is mutable; if used from multiple threads, cache access should be guarded or replaced with a thread-safe variant
  • Input validation: normalization is limited to trimming/lowercasing; URL parsing/decoding should be performed upstream if required for robust canonicalization
Published on:
Last updated on: