Design a detection rule evaluator

export type Scalar = string | number | boolean;

export type Matcher =
  | { op: "eq"; field: string; value: Scalar }
  | { op: "in"; field: string; values: readonly Scalar[] }
  | { op: "contains"; field: string; value: string; caseInsensitive?: boolean }
  | { op: "regex"; field: string; pattern: string }
  | { op: "exists"; field: string };

export type Expr =
  | Matcher
  | { op: "and"; all: readonly Expr[] }
  | { op: "or"; any: readonly Expr[] }
  | { op: "not"; expr: Expr };

export interface Threshold { count: number; windowMs: number; groupBy: readonly string[] }
export interface Rule { id: string; version: number; severity: 1 | 2 | 3 | 4; where: Expr; threshold?: Threshold }

export interface Event { time: number; fields: Readonly<Record<string, Scalar>> }
export interface Hit { ruleId: string; version: number; groupKey: string; count: number; firstAt: number; lastAt: number }

export class CompileError extends Error { constructor(m: string) { super(m); this.name = "CompileError"; } }

import RE2 from "re2";                                    // linear-time engine: no backtracking

type Fields = Event["fields"];
type Pred = (f: Fields) => boolean;

const MAX_DEPTH = 16;
const MAX_COST = 300;
const MAX_VALUE = 4096;                                     // matchers look at the first 4 KiB of a field
const MAX_PATTERN = 256;

const has = (f: Fields, k: string) => Object.hasOwn(f, k);  // never "constructor" or "__proto__" from the prototype
const text = (f: Fields, k: string): string | undefined => {
  const v = has(f, k) ? f[k] : undefined;
  return typeof v === "string" ? v.slice(0, MAX_VALUE) : undefined;
};

function safeRegex(pattern: string, ruleId: string): RE2 {
  if (pattern.length === 0 || pattern.length > MAX_PATTERN) throw new CompileError(ruleId + ": regex length must be 1.." + MAX_PATTERN);
  try { return new RE2(pattern); }                          // no g flag: test() stays stateless
  catch (e) { throw new CompileError(ruleId + ": unsupported regex (" + String(e) + ")"); }
}

export function compileExpr(root: Expr, ruleId: string): Pred {
  let cost = 0;
  const walk = (e: Expr, depth: number): Pred => {
    if (depth > MAX_DEPTH) throw new CompileError(ruleId + ": nested deeper than " + MAX_DEPTH);
    cost += e.op === "regex" ? 10 : 1;
    if (cost > MAX_COST) throw new CompileError(ruleId + ": rule cost exceeds " + MAX_COST);
    switch (e.op) {
      case "and": {
        if (e.all.length === 0) throw new CompileError(ruleId + ": empty and would match everything");
        const ps = e.all.map((x) => walk(x, depth + 1));
        return (f) => ps.every((p) => p(f));
      }
      case "or": {
        if (e.any.length === 0) throw new CompileError(ruleId + ": empty or never matches");
        const ps = e.any.map((x) => walk(x, depth + 1));
        return (f) => ps.some((p) => p(f));
      }
      case "not": {
        const inner = walk(e.expr, depth + 1);
        return (f) => !inner(f);
      }
      case "exists": return (f) => has(f, e.field);
      case "eq": return (f) => has(f, e.field) && f[e.field] === e.value;
      case "in": {
        if (e.values.length === 0) throw new CompileError(ruleId + ": empty in never matches");
        const set = new Set<Scalar>(e.values);
        return (f) => has(f, e.field) && set.has(f[e.field]);
      }
      case "contains": {
        if (e.value === "") throw new CompileError(ruleId + ": empty contains matches every string");
        const ci = e.caseInsensitive === true;
        const needle = ci ? e.value.toLowerCase() : e.value;
        return (f) => {
          const v = text(f, e.field);
          return v !== undefined && (ci ? v.toLowerCase() : v).includes(needle);
        };
      }
      case "regex": {
        const re = safeRegex(e.pattern, ruleId);
        return (f) => {
          const v = text(f, e.field);
          return v !== undefined && re.test(v);
        };
      }
      default: {
        const unknown: never = e;
        throw new CompileError(ruleId + ": unknown op " + JSON.stringify(unknown));
      }
    }
  };
  return walk(root, 0);
}

/** Per-group timestamps, ascending, never more than count of them; groups capped with LRU eviction. */
export class SlidingCounter {
  private readonly groups = new Map<string, number[]>();
  constructor(private readonly t: Threshold, private readonly maxGroups: number) {}

  /** Returns the window when the group reaches the threshold, then resets that group. */
  add(key: string, at: number): { count: number; firstAt: number; lastAt: number } | null {
    const ts = this.groups.get(key) ?? [];
    this.groups.delete(key);                                // re-inserted below, so Map order is LRU order
    let i = ts.length;
    while (i > 0 && ts[i - 1] > at) i--;                    // late events: sorted insert, at most count steps
    ts.splice(i, 0, at);
    const newest = ts[ts.length - 1];
    while (ts.length > 0 && ts[0] <= newest - this.t.windowMs) ts.shift();   // window is (newest - W, newest]
    if (ts.length > this.t.count) ts.splice(0, ts.length - this.t.count);
    if (ts.length >= this.t.count) return { count: ts.length, firstAt: ts[0], lastAt: newest };  // fired: not re-inserted = reset
    if (this.groups.size >= this.maxGroups) {
      const lru = this.groups.keys().next();
      if (!lru.done) this.groups.delete(lru.value);
    }
    this.groups.set(key, ts);
    return null;
  }
}

interface CompiledRule { rule: Rule; match: Pred; threshold?: { counter: SlidingCounter; groupBy: readonly string[] } }
export interface EvaluatorOptions { budgetMs: number; maxStrikes: number; maxGroups: number }
const DEFAULTS: EvaluatorOptions = { budgetMs: 2, maxStrikes: 20, maxGroups: 10_000 };

function compileRule(rule: Rule, maxGroups: number): CompiledRule {
  if (!rule.id) throw new CompileError("rule without id");
  const match = compileExpr(rule.where, rule.id);
  const t = rule.threshold;
  if (!t) return { rule, match };
  if (!Number.isInteger(t.count) || t.count < 1 || t.count > 1000) throw new CompileError(rule.id + ": count must be an integer in [1, 1000]");
  if (!Number.isFinite(t.windowMs) || t.windowMs <= 0 || t.windowMs > 86_400_000) throw new CompileError(rule.id + ": windowMs must be in (0, 24h]");
  if (t.groupBy.length > 5) throw new CompileError(rule.id + ": group by at most 5 fields");
  return { rule, match, threshold: { counter: new SlidingCounter(t, maxGroups), groupBy: t.groupBy } };
}

export class Evaluator {
  private readonly compiled: readonly CompiledRule[];
  private readonly strikes = new Map<string, number>();

  constructor(rules: readonly Rule[], private readonly opts: EvaluatorOptions = DEFAULTS, private readonly now: () => number = () => performance.now()) {
    const ids = new Set<string>();
    this.compiled = rules.map((r) => {
      if (ids.has(r.id)) throw new CompileError("duplicate rule id " + r.id);
      ids.add(r.id);
      return compileRule(r, opts.maxGroups);
    });
  }

  evaluate(ev: Event): Hit[] {
    if (!Number.isFinite(ev.time)) throw new TypeError("event time must be a finite number");
    const hits: Hit[] = [];
    for (const c of this.compiled) {
      const strikes = this.strikes.get(c.rule.id) ?? 0;
      if (strikes >= this.opts.maxStrikes) continue;         // quarantined: reported by quarantined() and a metric
      const t0 = this.now();
      const matched = c.match(ev.fields);
      if (this.now() - t0 > this.opts.budgetMs) this.strikes.set(c.rule.id, strikes + 1);
      if (!matched) continue;
      const base = { ruleId: c.rule.id, version: c.rule.version };
      if (!c.threshold) { hits.push({ ...base, groupKey: "", count: 1, firstAt: ev.time, lastAt: ev.time }); continue; }
      const groupKey = JSON.stringify(c.threshold.groupBy.map((f) => (Object.hasOwn(ev.fields, f) ? ev.fields[f] : null)));
      const w = c.threshold.counter.add(groupKey, ev.time);
      if (w) hits.push({ ...base, groupKey, ...w });
    }
    return hits;
  }

  quarantined(): string[] {
    return [...this.strikes].filter(([, n]) => n >= this.opts.maxStrikes).map(([id]) => id);
  }
}

import { describe, it, expect } from "vitest";

const bruteForce: Rule = {
  id: "auth-brute-force", version: 3, severity: 3,
  where: { op: "and", all: [{ op: "eq", field: "event.action", value: "login" }, { op: "eq", field: "outcome", value: "failure" }] },
  threshold: { count: 5, windowMs: 60_000, groupBy: ["actor.user"] },
};
const fail = (sec: number, user = "priya"): Event => ({ time: sec * 1000, fields: { "event.action": "login", outcome: "failure", "actor.user": user } });

// Each rule ships with fixtures: a name, the events, and the hits expected.
const cases: { name: string; events: Event[]; hits: Partial<Hit>[] }[] = [
  { name: "fires once on the fifth failure in a minute", events: [0, 10, 20, 30, 40, 50].map((s) => fail(s)),
    hits: [{ groupKey: '["priya"]', count: 5, firstAt: 0, lastAt: 40_000 }] },
  { name: "does not fire when failures straddle the window", events: [0, 20, 40, 60, 61].map((s) => fail(s)), hits: [] },
  { name: "groups per user", events: [0, 1, 2, 3].flatMap((s) => [fail(s, "priya"), fail(s, "sam")]), hits: [] },
];

describe(bruteForce.id, () => {
  for (const c of cases) {
    it(c.name, () => {
      const e = new Evaluator([bruteForce]);
      const hits = c.events.flatMap((ev) => e.evaluate(ev));
      expect(hits).toHaveLength(c.hits.length);
      c.hits.forEach((h, i) => expect(hits[i]).toMatchObject(h));
    });
  }
});

describe("compiler guards", () => {
  it("rejects an empty and", () => {
    expect(() => new Evaluator([{ ...bruteForce, where: { op: "and", all: [] } }])).toThrow(CompileError);
  });
  it("rejects lookaround, which needs backtracking", () => {
    expect(() => new Evaluator([{ ...bruteForce, where: { op: "regex", field: "cmd", pattern: "(?=a)a" } }])).toThrow(CompileError);
  });
  it("ignores prototype keys", () => {
    const e = new Evaluator([{ id: "proto", version: 1, severity: 1, where: { op: "exists", field: "constructor" } }]);
    expect(e.evaluate({ time: 0, fields: {} })).toEqual([]);
  });
});