Reputation scoring

Deep dive

How it works

Parts:

• Counter — decayed good/bad pair plus last-update time per key.
• Hierarchy path — leaf-to-root keys, e.g. ip:192.0.2.7, net:192.0.2.0/24, asn:64500; for URLs: URL, host, registrable domain (needs the Public Suffix List).
• Beta posterior — parent mean as prior worth k events, plus the level's own evidence.
• Policy — thresholds on a conservative bound.

1. On an event, for each key on the path: multiply both counters by 2^(-(now-t)/T), add the event weight to good or bad, set t = now.
2. To score, decay each level to now, walk root to leaf.
3. Level prior: Beta(k·m, k·(1-m)), m = the parent's posterior mean (root: a global rate such as 0.9).
4. The parent's counts include the child's events, so use only the parent's own evidence (parent minus child) when forming m, otherwise one event counts once per level.
5. Posterior Beta(a,b): mean a/(a+b), variance ab/((a+b)²(a+b+1)).
6. Lower bound mean - z·sd (z about 1-2) feeds the policy: block below one threshold, allow above another, challenge or rate-limit between.

event ─► ip ─► /24 ─► asn          score:  global ─► asn ─► /24 ─► ip
         each level decays + counts        prior flows down, own evidence added

DNS blocklists are the published, read-only form. RFC 5782: query the reversed octets (192.0.2.99 asks 99.2.0.192.<zone>); a listed IP has an A record in 127.0.0.0/8 (127.0.0.2 by convention, other values encode sublists) and optionally a TXT reason. Every IPv4 list must list 127.0.0.2 and must not list 127.0.0.1, so clients can self-test. Spamhaus ZEN merges SBL, CSS, XBL and PBL and returns one code per dataset.

Code

use std::collections::HashMap;

/// Decayed evidence for one key. Counts are "effective events" as of `t`.
#[derive(Clone, Copy, Default)]
pub struct Counter { good: f64, bad: f64, t: f64 }

impl Counter {
    fn decayed(&self, now: f64, half_life: f64) -> (f64, f64) {
        let f = 0.5f64.powf((now - self.t).max(0.0) / half_life); // exp. decay: 2^(-dt/T)
        (self.good * f, self.bad * f)
    }
}

pub struct Store {
    map: HashMap<String, Counter>,
    half_life: f64,   // seconds; evidence loses half its weight per half_life
    root_prior: f64,  // global P(bad-free) before any evidence, e.g. 0.9
    strength: f64,    // pseudo-count k: how many events the parent prior is worth
}

impl Store {
    pub fn new(half_life: f64, root_prior: f64, strength: f64) -> Self {
        assert!(half_life > 0.0 && (0.0..=1.0).contains(&root_prior) && strength > 0.0);
        Store { map: HashMap::new(), half_life, root_prior, strength }
    }

    /// Record one observation on every level of `path` (leaf first, e.g.
    /// ["ip:192.0.2.7", "net:192.0.2.0/24", "asn:64500"]). `w` weights the event.
    pub fn record(&mut self, path: &[&str], good: bool, w: f64, now: f64) {
        assert!(w >= 0.0 && !path.is_empty());
        for k in path {
            let c = self.map.entry(k.to_string()).or_default();
            let (g, b) = c.decayed(now, self.half_life); // decay lazily, only on touch
            *c = Counter { good: g + if good { w } else { 0.0 }, bad: b + if good { 0.0 } else { w }, t: now };
        }
    }

    /// Posterior mean P(good) and std-dev of the leaf. Walks root -> leaf; each level's
    /// Beta prior is its parent's posterior mean worth `strength` pseudo-events. The parent
    /// aggregate includes the child's events, so they are subtracted to avoid counting twice.
    pub fn score(&self, path: &[&str], now: f64) -> (f64, f64) {
        let ev: Vec<(f64, f64)> = path.iter().rev()
            .map(|k| self.map.get(*k).map_or((0.0, 0.0), |c| c.decayed(now, self.half_life)))
            .collect(); // root first
        let (mut mean, mut sd) = (self.root_prior, 0.0);
        for i in 0..ev.len() {
            let (g, b) = ev[i];
            // evidence seen *only* at this level (not already counted at the next, finer one)
            let (g_own, b_own) = match ev.get(i + 1) {
                Some(&(cg, cb)) => ((g - cg).max(0.0), (b - cb).max(0.0)),
                None => (g, b),
            };
            let (a0, b0) = (self.strength * mean, self.strength * (1.0 - mean));
            let (a, bb) = (a0 + g_own, b0 + b_own);
            let n = a + bb;
            mean = a / n;
            sd = (a * bb / (n * n * (n + 1.0))).sqrt(); // Beta variance
        }
        (mean, sd)
    }

    /// Conservative score: mean - z*sd, so low-volume keys never look better than proven ones.
    pub fn lower_bound(&self, path: &[&str], now: f64, z: f64) -> f64 {
        let (m, sd) = self.score(path, now);
        (m - z * sd).clamp(0.0, 1.0)
    }
}

#[derive(Debug, PartialEq)]
pub enum Action { Allow, Challenge, Block }

/// Score -> action with a hysteresis-free two-threshold rule on the lower bound.
pub fn decide(lb: f64, block_below: f64, allow_above: f64) -> Action {
    assert!(block_below < allow_above);
    if lb < block_below { Action::Block } else if lb >= allow_above { Action::Allow } else { Action::Challenge }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn behaviour() {
        let day = 86_400.0;
        let mut s = Store::new(7.0 * day, 0.9, 10.0);
        let p = ["ip:192.0.2.7", "net:192.0.2.0/24", "asn:64500"];
        assert!((s.score(&p, 0.0).0 - 0.9).abs() < 1e-12);          // cold start = prior
        s.record(&p, false, 1.0, 0.0);
        assert!((s.score(&p, 0.0).0 - 9.0 / 11.0).abs() < 1e-9);    // Beta(9,2): no triple count
        for _ in 0..50 { s.record(&["ip:192.0.2.9", "net:192.0.2.0/24", "asn:64500"], false, 1.0, 0.0); }
        let sib = ["ip:192.0.2.99", "net:192.0.2.0/24", "asn:64500"];
        assert!(s.score(&sib, 0.0).0 < 0.5);                        // unseen sibling inherits
        assert!((s.score(&sib, 70.0 * day).0 - 0.9).abs() < 0.01);  // 10 half-lives: forgotten
        let lb = s.lower_bound(&p, 0.0, 1.0);
        assert!(lb <= s.score(&p, 0.0).0);
        assert_eq!(decide(lb, 0.3, 0.8), Action::Block);
        assert_eq!(decide(0.95, 0.3, 0.8), Action::Allow);
    }
}

Complexity and constants

• Event and lookup: O(L) for path length L (usually 3): one hash probe and one powf per level.
• Memory: 24 B of counters per key plus key string and map overhead (order of 100 B per key with String keys; packed IPs or 64-bit key hashes cut that substantially).
• Measured here (Apple Silicon, release build, 200,000 distinct IPs, 3 levels, SipHash, one String allocation per new key): about 370 ns per recorded event and 460 ns per score, single thread. Cost drivers: hashing, allocation, cache misses on a table far bigger than L2.
• Safe Browsing keeps hash prefixes (4-32 bytes, usually 4) locally; a DNSBL lookup is one small UDP exchange.

Efficiency

Cost: a few hundred ns per event (measured above), dominated by hashing and cache misses; memory is the bound at order of 100 B per key. No fsync on the hot path: counters are soft state.

Levers:

• Lazy decay on touch — no periodic sweep over all keys, O(1) per event — always.
• Evict by decayed weight — keys with almost no decayed evidence score the same as the prior, so deleting them changes nothing — large key spaces.
• Batch updates per shard — one counter write per key per interval, not per message — high-volume streams.
• Cache verdicts — DNSBL answers carry DNS TTLs, a local cache avoids repeat queries — per-connection checks.
• Local hash-prefix filter before a network call — Safe Browsing's Update API (v4) stores SHA-256 prefixes locally and asks the server only on a prefix hit (Google docs) — URL checks.

Naive → standard → state of the art:

• Naive: lifetime bad/total ratio in a database · one query per message, one bad event condemns a new key, never forgets
• Standard: decayed counts + Beta prior + hierarchy in memory · hundreds of ns per event, order of 100 B per key
• State of the art: the same counters as features of a learned model, as in SNARE and Notos · same lookup cost, better separation

Implementation notes

• Weight events by evidence quality instead of keeping separate counters.
• Half-life per entity type: IPs get recycled (shorter), domains and accounts live longer. rspamd's default window is 30 days.
• EWMA alternative: rspamd stores one score per bucket and blends in each message with alpha = 1 - exp(-dt/window). One float per key, but no uncertainty, so thin keys look like proven ones.
• Cold start: a new key gets the parent mean, capped by a rate limit or token bucket until it earns evidence.
• Hysteresis on actions (block at 0.3, unblock at 0.5, say) so entities do not flap.

Pitfalls

• Feedback loop: blocked senders stop generating events, so bad scores are never corrected by new data; decay is what lets them out. Keep a quarantine or sampled path.
• Poisoning: false reports smear a victim, or cheap good history is built up and then abused. Weight reports by reporter trust, cap each reporter's influence per key, and key on authenticated identity (verified domain), not spoofable fields.
• Shared infrastructure: one bad tenant lowers the /24 or ASN prior for everyone behind it; use a small k at coarse levels and exempt known shared hosts.
• Double counting across levels (step 4).
• Thresholds on the mean: 1 good event and 0 bad is not 10,000 good and 0 bad; threshold the lower bound.

Variants and alternatives

In production

• Email: servers combine DNSBL lookups, per-sender reputation (rspamd; SpamAssassin TxRep tracks sender address, IP and IP block, domain, DKIM signature, HELO name) and content scores.
• Web browsing: Google Safe Browsing lists unsafe URLs for browsers; clients match local hash prefixes first.
• Network security: Spamhaus blocklists are queried as DNSBLs; CrowdSec shares a crowdsourced blocklist of malicious IPs; Notos scores domains from DNS features (Antonakakis et al. 2010).
• E-commerce: the Beta reputation system was designed to combine feedback in e-commerce (Jøsang and Ismail 2002); a design, not a named deployment.

Implementations

Sources

• Audun Jøsang, Roslan Ismail, The Beta Reputation System, 15th Bled Electronic Commerce Conference 2002. paper
• Shuang Hao, Nadeem Ahmed Syed, Nick Feamster, Alexander G. Gray, Sven Krasser, Detecting Spammers with SNARE: Spatio-temporal Network-level Automatic Reputation Engine, USENIX Security 2009. paper
• Manos Antonakakis, Roberto Perdisci, David Dagon, Wenke Lee, Nick Feamster, Building a Dynamic Reputation System for DNS, USENIX Security 2010. paper
• J. Levine, DNS Blacklists and Whitelists, RFC 5782, 2010. rfc
• Google, Safe Browsing APIs (v4): URLs and Hashing, Update API. docs
• rspamd, Reputation module. docs
• Apache SpamAssassin, TxRep plugin. docs
• Edwin B. Wilson, Probable Inference, the Law of Succession, and Statistical Inference, JASA 22(158), 1927. doi