Living Document Notice
Published 2026-09-19. The evolving architecture, revisions, and connected notes for this dispatch live in the Stax Digital Garden.

Wall-Clock Execution Budgets - Eliminating Infinite Loops in Regex Tokenizers

Summary

Catastrophic backtracking in regular expression engines can stall document parsing indefinitely. When importing malformed HTML or Markdown text with deeply nested emphasis delimiters, non-linear backtracking regexes consume 100% CPU on single threads, causing ingestion pipelines to hang without emitting diagnostic output.

Outrigger implements dual-tier wall-clock and CPU cycle execution budgets for all parsing tasks. By pairing POSIX interval timers with asynchronous watchdog threads, the supervisor runtime terminates runaway regex evaluations, isolates the offending note segment, and returns worker threads to processing queues.

The Vulnerability Profile of Backtracking Regex Engines

Standard regex implementations utilizing non-deterministic finite automata (NFA) engines exhibit worst-case exponential time complexity O(2^n) when handling ambiguous, nested grammar. A pattern matching markdown bold tags such as (\*\*|__)(.*?)\1 applied to an unclosed 50KB string triggers billions of state branch evaluations.

Because users export notes containing arbitrarily broken markdown syntax, parsing engines cannot assume input conformity. Relying on cooperative yielding inside tokenization loops fails when third-party C libraries execute inside atomic native blocks.

Outrigger enforces uncooperative preemption by configuring operating system interval timers that fire asynchronous hardware signals when execution exceeds pre-allocated thresholds.

POSIX Interval Timers via timer_create

On POSIX systems, Outrigger provisions high-resolution timers using timer_create configured to measure CPU time consumed strictly by the target thread (CLOCK_THREAD_CPUTIME_ID).

#include <signal.h>
#include <time.h>
#include <stdio.h>
#include <unistd.h>

void arm_thread_cpu_budget(timer_t *timerid, long timeout_milliseconds) {
    struct sigevent sev;
    sev.sigev_notify = SIGEV_SIGNAL;
    sev.sigev_signo = SIGALRM;
    sev.sigev_value.sival_ptr = timerid;

    timer_create(CLOCK_THREAD_CPUTIME_ID, &sev, timerid);

    struct itimerspec its;
    its.it_value.tv_sec = timeout_milliseconds / 1000;
    its.it_value.tv_nsec = (timeout_milliseconds % 1000) * 1000000;
    its.it_interval.tv_sec = 0;
    its.it_interval.tv_nsec = 0;

    timer_settime(*timerid, 0, &its, NULL);
}

When the allocated budget expires, the kernel delivers SIGALRM directly to the active thread, interrupting the execution of the backtracking loop. The signal handler unwinds the thread context and transfers execution to the quarantine reporting handler.

Regex Performance Under Pathological Input Payloads

The table below details parsing response times and termination behavior across 1,000 pathological backtracking payloads with varying execution budget configurations.

Deploying kernel-level thread timers caps processing latency on adversarial payloads without degrading throughput on well-formed markdown documents.

Watchdog Struct Configuration in Rust Runtimes

In multi-threaded Rust execution workers, Outrigger encapsulates regex evaluations inside a watchdog supervisor configured with monotonic duration bounds.

use std::time::{Duration, Instant};
use std::sync::mpsc::channel;
use std::thread;

pub struct ExecutionBudget {
    pub max_duration: Duration,
}

impl ExecutionBudget {
    pub fn execute_bounded<F, T>(&self, task: F) -> Result<T, &'static str>
    where
        F: FnOnce() -> T + Send + 'static,
        T: Send + 'static,
    {
        let (tx, rx) = channel();
        thread::spawn(move || {
            let result = task();
            let _ = tx.send(result);
        });

        match rx.recv_timeout(self.max_duration) {
            Ok(val) => Ok(val),
            Err(_) => Err("Execution budget exceeded: thread aborted"),
        }
    }
}