use std::time::{Duration, Instant};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SeriesSample {
pub at: Instant,
pub flags: u8,
pub sequence: u32,
pub ip_id: Option<u16>,
pub tsval: Option<u32>,
}
impl SeriesSample {
pub fn is_syn_ack(&self) -> bool {
use crate::protocols::tcp::flags;
self.flags & flags::SYN != 0 && self.flags & flags::ACK != 0
}
}
pub const MAX_INTERVAL_FOR_ID: Duration = Duration::from_millis(500);
const PLAUSIBLE_ID_RATE: f64 = 20_000.0;
const MAX_INTERVAL_FOR_CLOCK: Duration = Duration::from_millis(500);
const CLOCK_CEILING: f64 = 10_000.0;
const CLOCK_SPREAD: f64 = 2.0;
const MEANINGFUL_ISN_STEP: u32 = 1_024;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum IdClass {
Absent,
TooFew,
Unclear,
Zero,
Constant,
Counting,
Scattered,
}
impl IdClass {
pub const fn name(self) -> &'static str {
match self {
IdClass::Absent => "absent",
IdClass::TooFew => "too-few",
IdClass::Unclear => "unclear",
IdClass::Zero => "zero",
IdClass::Constant => "constant",
IdClass::Counting => "counting",
IdClass::Scattered => "scattered",
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum IsnClass {
NotRead,
TooFew,
Zero,
FixedStep(u32),
Multiples(u32),
Hashed,
}
impl IsnClass {
pub fn detail(self) -> String {
match self {
IsnClass::FixedStep(step) => format!("fixed-step({step})"),
IsnClass::Multiples(step) => format!("multiples({step})"),
other => other.name().to_owned(),
}
}
pub const fn name(self) -> &'static str {
match self {
IsnClass::NotRead => "not-read",
IsnClass::TooFew => "too-few",
IsnClass::Zero => "zero",
IsnClass::FixedStep(_) => "fixed-step",
IsnClass::Multiples(_) => "multiples",
IsnClass::Hashed => "hashed",
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum ClockClass {
None,
Zero,
TooFew,
Randomised,
Slower,
Hertz(u32),
}
impl ClockClass {
pub fn detail(self) -> String {
match self {
ClockClass::Hertz(hz) => format!("ticking({hz}Hz)"),
other => other.name().to_owned(),
}
}
pub const fn name(self) -> &'static str {
match self {
ClockClass::None => "none",
ClockClass::Zero => "zero",
ClockClass::TooFew => "too-few",
ClockClass::Randomised => "randomised",
ClockClass::Slower => "slower",
ClockClass::Hertz(_) => "ticking",
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SeriesClasses {
pub identifiers: IdClass,
pub sequences: IsnClass,
pub clock: ClockClass,
}
impl SeriesClasses {
pub fn from_samples(series: &[SeriesSample]) -> Self {
Self {
identifiers: read_identifiers(series).class,
sequences: read_sequences(series).class,
clock: read_clock(series).class,
}
}
pub fn summary(&self) -> String {
format!(
"id={} isn={} ts={}",
self.identifiers.name(),
self.sequences.detail(),
self.clock.detail()
)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Reading<T> {
pub class: T,
pub line: String,
}
pub fn read_identifiers(series: &[SeriesSample]) -> Reading<IdClass> {
let sampled: Vec<(Instant, u16)> = series
.iter()
.filter_map(|sample| sample.ip_id.map(|id| (sample.at, id)))
.collect();
let values: Vec<u16> = sampled.iter().map(|(_, id)| *id).collect();
if values.is_empty() {
return Reading {
class: IdClass::Absent,
line: "none - IPv6 has no identification field".to_string(),
};
}
if values.len() < 3 {
return Reading {
class: IdClass::TooFew,
line: format!("{values:?} - too few to read a policy from"),
};
}
let raw = format!("{values:?}");
let widest = sampled
.windows(2)
.map(|pair| pair[1].0.duration_since(pair[0].0))
.max()
.unwrap_or_default();
if widest > MAX_INTERVAL_FOR_ID {
return Reading {
class: IdClass::Unclear,
line: format!("{raw} - unclear"),
};
}
if values.iter().all(|&value| value == 0) {
return Reading {
class: IdClass::Zero,
line: format!("{raw} - zero throughout"),
};
}
if values.windows(2).all(|pair| pair[0] == pair[1]) {
return Reading {
class: IdClass::Constant,
line: format!("{raw} - constant"),
};
}
let steps: Vec<u16> = sampled
.windows(2)
.map(|pair| pair[1].1.wrapping_sub(pair[0].1))
.collect();
let fastest = sampled
.windows(2)
.zip(&steps)
.map(|(pair, step)| f64::from(*step) / pair[1].0.duration_since(pair[0].0).as_secs_f64())
.filter(|rate| *rate > 0.0)
.fold(f64::INFINITY, f64::min);
if fastest <= PLAUSIBLE_ID_RATE {
return Reading {
class: IdClass::Counting,
line: format!("{raw} - counting"),
};
}
Reading {
class: IdClass::Scattered,
line: format!("{raw} - scattered"),
}
}
pub fn read_sequences(series: &[SeriesSample]) -> Reading<IsnClass> {
if series.iter().all(|sample| !sample.is_syn_ack()) {
return Reading {
class: IsnClass::NotRead,
line: "not read - a reset opens no connection to number".to_string(),
};
}
let syn_acks: Vec<&SeriesSample> = series.iter().filter(|s| s.is_syn_ack()).collect();
let values: Vec<u32> = syn_acks.iter().map(|sample| sample.sequence).collect();
if values.iter().all(|&value| value == 0) {
return Reading {
class: IsnClass::Zero,
line: "zero throughout".to_string(),
};
}
if values.len() < 3 {
return Reading {
class: IsnClass::TooFew,
line: format!("{values:?} - too few to read a generator from"),
};
}
let steps: Vec<u32> = values
.windows(2)
.map(|pair| pair[1].wrapping_sub(pair[0]))
.collect();
if steps.windows(2).all(|pair| pair[0] == pair[1]) {
return Reading {
class: IsnClass::FixedStep(steps[0]),
line: format!("fixed step of {}", steps[0]),
};
}
let divisor = steps.iter().copied().fold(0u32, gcd);
if divisor >= MEANINGFUL_ISN_STEP {
return Reading {
class: IsnClass::Multiples(divisor),
line: format!("stepping in multiples of {divisor}"),
};
}
Reading {
class: IsnClass::Hashed,
line: format!("no common step (divisor {divisor}) - consistent with a hashed generator"),
}
}
pub fn read_clock(series: &[SeriesSample]) -> Reading<ClockClass> {
let sampled: Vec<(Instant, u32)> = series
.iter()
.filter_map(|sample| sample.tsval.map(|ts| (sample.at, ts)))
.collect();
if sampled.is_empty() {
return Reading {
class: ClockClass::None,
line: "none sent".to_string(),
};
}
let values: Vec<u32> = sampled.iter().map(|(_, ts)| *ts).collect();
if values.iter().all(|&value| value == 0) {
return Reading {
class: ClockClass::Zero,
line: "sent, but always zero".to_string(),
};
}
if values.len() < 2 {
return Reading {
class: ClockClass::TooFew,
line: format!("{values:?} - too few to read a rate from"),
};
}
let raw = format!("{values:?}");
let widest = sampled
.windows(2)
.map(|pair| pair[1].0.duration_since(pair[0].0))
.max()
.unwrap_or_default();
if widest > MAX_INTERVAL_FOR_CLOCK {
return Reading {
class: ClockClass::TooFew,
line: format!("{raw} - sampled too slowly for a rate"),
};
}
let rates: Vec<f64> = sampled
.windows(2)
.map(|pair| {
let ticks = pair[1].1.wrapping_sub(pair[0].1);
let secs = pair[1].0.duration_since(pair[0].0).as_secs_f64();
f64::from(ticks) / secs
})
.collect();
let slowest = rates.iter().copied().fold(f64::INFINITY, f64::min);
let fastest = rates.iter().copied().fold(0.0, f64::max);
if fastest > CLOCK_CEILING || fastest / slowest.max(f64::MIN_POSITIVE) > CLOCK_SPREAD {
return Reading {
class: ClockClass::Randomised,
line: format!("{raw} - randomised per connection"),
};
}
let hertz = rates.iter().sum::<f64>() / rates.len() as f64;
if hertz < 1.0 {
return Reading {
class: ClockClass::Slower,
line: format!("{raw} - slower than sampled"),
};
}
let rounded = (hertz / 10.0).round() * 10.0;
Reading {
class: ClockClass::Hertz(rounded as u32),
line: format!("{raw} - about {rounded:.0} Hz"),
}
}
fn gcd(a: u32, b: u32) -> u32 {
let (mut a, mut b) = (a, b);
while b != 0 {
let remainder = a % b;
a = b;
b = remainder;
}
a
}
#[cfg(test)]
mod tests {
use super::*;
use std::time::Duration;
fn series(
offsets: &[Duration],
identifiers: &[u16],
sequences: &[u32],
stamps: &[u32],
) -> Vec<SeriesSample> {
use crate::protocols::tcp::flags;
let base = Instant::now();
offsets
.iter()
.enumerate()
.map(|(index, offset)| SeriesSample {
at: base + *offset,
flags: flags::SYN | flags::ACK,
sequence: sequences.get(index).copied().unwrap_or(0),
ip_id: identifiers.get(index).copied(),
tsval: stamps.get(index).copied(),
})
.collect()
}
fn spaced(count: usize) -> Vec<Duration> {
(0..count)
.map(|i| Duration::from_millis(100 * i as u64))
.collect()
}
#[test]
fn identifiers_zero_constant_and_absent() {
let zero = series(&spaced(4), &[0, 0, 0, 0], &[], &[]);
assert_eq!(read_identifiers(&zero).class, IdClass::Zero);
let constant = series(&spaced(4), &[7, 7, 7, 7], &[], &[]);
assert_eq!(read_identifiers(&constant).class, IdClass::Constant);
let absent = series(&spaced(4), &[], &[], &[]);
assert_eq!(read_identifiers(&absent).class, IdClass::Absent);
let too_few = series(&spaced(2), &[5, 6], &[], &[]);
assert_eq!(read_identifiers(&too_few).class, IdClass::TooFew);
}
#[test]
fn a_wrapping_counter_is_still_counting() {
let wrapping = series(&spaced(4), &[65_530, 65_532, 65_534, 0], &[], &[]);
assert_eq!(read_identifiers(&wrapping).class, IdClass::Counting);
}
#[test]
fn a_slowly_sampled_series_is_unclear() {
let gaps = vec![
Duration::ZERO,
Duration::from_millis(100),
Duration::from_millis(900),
];
let slow = series(&gaps, &[10, 11, 12], &[], &[]);
assert_eq!(read_identifiers(&slow).class, IdClass::Unclear);
}
#[test]
fn randomised_identifiers_are_scattered() {
let scattered = series(&spaced(4), &[4_000, 61_000, 12_000, 33_000], &[], &[]);
assert_eq!(read_identifiers(&scattered).class, IdClass::Scattered);
}
#[test]
fn sequences_fixed_step_multiples_and_hashed() {
let stepping = series(
&spaced(4),
&[],
&[1_000_000, 1_064_000, 1_128_000, 1_192_000],
&[],
);
assert_eq!(read_sequences(&stepping).class, IsnClass::FixedStep(64_000));
let hashed = series(
&spaced(4),
&[],
&[2_147_483_647, 91_827_361, 3_918_273_645, 771_293_811],
&[],
);
assert_eq!(read_sequences(&hashed).class, IsnClass::Hashed);
let zero = series(&spaced(4), &[], &[0, 0, 0, 0], &[]);
assert_eq!(read_sequences(&zero).class, IsnClass::Zero);
}
#[test]
fn a_resets_sequence_number_is_not_read() {
use crate::protocols::tcp::flags;
let mut reset_series = series(
&spaced(4),
&[],
&[1_000_000, 1_064_000, 1_128_000, 1_192_000],
&[],
);
for sample in &mut reset_series {
sample.flags = flags::RST | flags::ACK;
}
assert_eq!(read_sequences(&reset_series).class, IsnClass::NotRead);
}
#[test]
fn clocks_none_zero_and_ticking() {
let none = series(&spaced(4), &[], &[], &[]);
assert_eq!(read_clock(&none).class, ClockClass::None);
let zero = series(&spaced(4), &[], &[], &[0, 0, 0, 0]);
assert_eq!(read_clock(&zero).class, ClockClass::Zero);
let ticking = series(
&spaced(6),
&[],
&[],
&[500_000, 500_100, 500_200, 500_300, 500_400, 500_500],
);
assert_eq!(read_clock(&ticking).class, ClockClass::Hertz(1000));
}
#[test]
fn a_clock_crossing_its_wrap_is_still_that_clock() {
let wrapping = series(
&spaced(6),
&[],
&[],
&[u32::MAX - 200, u32::MAX - 100, u32::MAX, 99, 199, 299],
);
assert_eq!(read_clock(&wrapping).class, ClockClass::Hertz(1000));
}
#[test]
fn a_per_connection_random_offset_is_not_a_clock() {
let randomised = series(
&spaced(6),
&[],
&[],
&[
1_913_402_881,
88_120_004,
3_774_119_855,
412_998_002,
2_660_001_913,
955_218_744,
],
);
assert_eq!(read_clock(&randomised).class, ClockClass::Randomised);
}
#[test]
fn endpoints_that_agree_do_not_make_the_middle_a_clock() {
let plausible = series(
&spaced(6),
&[],
&[],
&[500_000, 900_000, 100_000, 700_000, 200_000, 500_500],
);
assert_eq!(read_clock(&plausible).class, ClockClass::Randomised);
}
#[test]
fn a_clock_slower_than_the_sampling_says_so() {
let slow = series(&spaced(6), &[], &[], &[77_777; 6]);
assert_eq!(read_clock(&slow).class, ClockClass::Slower);
}
#[test]
fn the_names_are_coarse_where_the_values_vary() {
let slow_counter = series(&spaced(6), &[10, 11, 12, 13, 14, 15], &[], &[]);
let fast_counter = series(&spaced(6), &[900, 950, 1000, 1050, 1100, 1150], &[], &[]);
assert_eq!(
read_identifiers(&slow_counter).class.name(),
read_identifiers(&fast_counter).class.name(),
"two counters at different rates share one policy name"
);
let jittered = series(
&[Duration::ZERO, Duration::from_millis(251)],
&[],
&[],
&[500_000, 500_250],
);
let exact = series(
&[Duration::ZERO, Duration::from_millis(250)],
&[],
&[],
&[700_000, 700_250],
);
assert_eq!(
read_clock(&jittered).class,
ClockClass::Hertz(1_000),
"996 Hz measured is a 1000 Hz clock, and the rounding is what says so"
);
assert_eq!(
read_clock(&jittered).class.name(),
read_clock(&exact).class.name(),
"one clock measured with jitter reads as one clock"
);
}
#[test]
fn a_series_sample_knows_whether_it_answered_a_handshake() {
use crate::protocols::tcp::flags;
let handshake = series(&spaced(1), &[], &[], &[]);
assert!(handshake[0].is_syn_ack());
let mut reset = series(&spaced(1), &[], &[], &[]);
reset[0].flags = flags::RST;
assert!(!reset[0].is_syn_ack());
}
#[test]
fn gcd_finds_the_common_step() {
assert_eq!(gcd(0, 0), 0);
assert_eq!(gcd(64_000, 64_000), 64_000);
assert_eq!(gcd(48, 18), 6);
}
#[test]
fn samples_are_buildable_from_plain_values() {
let sample = SeriesSample {
at: Instant::now(),
flags: 0x12,
sequence: 42,
ip_id: Some(7),
tsval: None,
};
assert_eq!(sample.ip_id, Some(7));
}
}