troll-patrol/src/lox_analysis.rs

use crate::analysis::Analyzer;
use lox_library::proto::{level_up::LEVEL_INTERVAL, trust_promotion::UNTRUSTED_INTERVAL};
use std::cmp::min;

// Get max value from slice, or 0 if empty
fn max(nums: &[u32]) -> u32 {
    let mut max_num = 0;
    for i in nums {
        if *i > max_num {
            max_num = *i;
        }
    }
    max_num
}

// Safe u32 subtraction: x - y or 0 if y > x
fn ssub(x: u32, y: u32) -> u32 {
    if y > x {
        0
    } else {
        x - y
    }
}

/// Analyzer for Lox bridges based on how long they've been active
pub struct LoxAnalyzer {
    // simple variable threshold from 0-4 or something
    harshness: u32,
}

impl Analyzer for LoxAnalyzer {
    // At this stage, we expect 0-10 users, so 0, 8, or 16 bridge-ips
    fn stage_one(
        &self,
        age: u32,
        _confidence: f64,
        bridge_ips: &[u32],
        bridge_ips_today: u32,
        _negative_reports: &[u32],
        negative_reports_today: u32,
    ) -> bool {
        // Get max bridge_ips we've seen
        let max_bridge_ips = max(bridge_ips);

        if self.too_few_bridge_ips(age, max_bridge_ips, bridge_ips_today, 0) {
            return true;
        }

        // If we have too many negative reports, consider the bridge
        // blocked
        self.too_many_negative_reports(negative_reports_today)
    }

    fn stage_two(
        &self,
        age: u32,
        _confidence: f64,
        bridge_ips: &[u32],
        bridge_ips_today: u32,
        _negative_reports: &[u32],
        negative_reports_today: u32,
    ) -> bool {
        // Get max bridge_ips we've seen
        let max_bridge_ips = max(bridge_ips);

        if self.too_few_bridge_ips(age, max_bridge_ips, bridge_ips_today, 0) {
            return true;
        }

        // If we have too many negative reports, consider the bridge
        // blocked
        self.too_many_negative_reports(negative_reports_today)
    }

    fn stage_three(
        &self,
        age: u32,
        _confidence: f64,
        bridge_ips: &[u32],
        bridge_ips_today: u32,
        _negative_reports: &[u32],
        negative_reports_today: u32,
        _positive_reports: &[u32],
        positive_reports_today: u32,
    ) -> bool {
        // Get max bridge_ips we've seen
        let max_bridge_ips = max(bridge_ips);

        if self.too_few_bridge_ips(
            age,
            max_bridge_ips,
            bridge_ips_today,
            positive_reports_today,
        ) {
            return true;
        }

        // If we have too many negative reports, consider the bridge
        // blocked
        self.too_many_negative_reports(negative_reports_today)
    }
}

impl LoxAnalyzer {
    pub fn new(harshness: u32) -> Self {
        Self { harshness }
    }

    // Maximum number of negative reports without considering the bridge blocked
    fn too_many_negative_reports(&self, negative_reports_today: u32) -> bool {
        // If we have more negative reports than 4 - harshness
        negative_reports_today > 4 - self.harshness

        // harshness: 4, blocked if 1 negative report
        // harshness: 3, blocked if 2 negative reports
        // harshness: 2, blocked if 3 negative reports
        // harshness: 1, blocked if 4 negative reports
        // harshness: 0, blocked if 5 negative reports
    }

    // Based on the age of the bridge and the max bridge-ips observed, do we
    // have too few today?
    fn too_few_bridge_ips(
        &self,
        days: u32,
        max_bridge_ips: u32,
        bridge_ips_today: u32,
        positive_reports_today: u32,
    ) -> bool {
        if days <= UNTRUSTED_INTERVAL {
            // We expect 0-10 users
            if self.harshness == 4 {
                // In the most extreme case, mark any bridge with 0 connections
                bridge_ips_today == 0
            } else if self.harshness >= 2 {
                // With medium harshness, mark any bridge that has had
                // 9+ connections and now sees 0
                max_bridge_ips > 8 && bridge_ips_today == 0
            } else {
                // With low harshness, we cannot make a judgement from
                // bridge stats
                false
            }
        } else if days <= UNTRUSTED_INTERVAL + LEVEL_INTERVAL[1] {
            // We expect 1-30 users

            let threshold = min(max_bridge_ips, 32);

            // If we're at least 4 - self.harshness bins below the
            // maximum value we've seen or 32 if we've seen a lot of
            // connections, consider the bridge blocked.
            bridge_ips_today < ssub(threshold, (4 - self.harshness) * 8)

            // Examples:
            // max 64 connections, harshness = 4
            //    Return true if today's count is less than 32
            // max 32 connections, harshness = 4
            //    Return true if today's count is less than 32
            // max 32 connections, harshness = 3
            //    Return true if today's count is less than 24
            // max 32 connections, harshness = 2
            //    Return true if today's count is less than 16
            // max 8 connections, harshness = 4
            //    Return true if today's count is less than 8
            // max 8 connections, harshness = 3
            //    Return false
        } else {
            // Similar, but consider positive reports as well
            let threshold = min(max_bridge_ips, 32);

            // We allow positive reports to increase the threshold for
            // considering the bridge blocked. 8 positive reports
            // (rounded up) remove 1 level reduction from the threshold
            let threshold = ssub(
                threshold,
                (4 - self.harshness + (positive_reports_today + 7) / 8) * 8,
            );

            // For example, suppose we've seen 32+ connections.
            //
            // If we have harshness 4, we mark the bridge blocked if it
            // has fewer than 32 connections.
            //
            // If we have harshness 4 but have seen 1-7 positive
            // reports, we mark the bridge blocked only if it has fewer
            // than 24 connections.
            //
            // 25 positive reports reduce all thresholds to 0, meaning
            // bridges will never be marked blocked from bridge stats
            // if the adversary can submit 25 positive reports.

            // Consider the bridge blocked if we have too few connections
            bridge_ips_today < threshold
        }
    }
}