use crate::model::host::{OsEvidence, OsSource};
use std::collections::BTreeMap;
use super::verdict::{MIN_REPORTABLE_ACCURACY, OsVerdict};
pub const MAX_FUSED_ACCURACY: u8 = 95;
pub fn resolve(evidence: Vec<OsEvidence>) -> Option<OsVerdict> {
let mut by_family: BTreeMap<&str, Vec<&OsEvidence>> = BTreeMap::new();
let mut abstained: Vec<&OsEvidence> = Vec::new();
for item in &evidence {
match item.family.as_deref() {
Some(family) => by_family.entry(family).or_default().push(item),
None => abstained.push(item),
}
}
let mut scored: Vec<(&str, f32, Vec<&OsEvidence>)> = by_family
.into_iter()
.map(|(family, items)| {
let score = combine_sources(&items);
(family, score, items)
})
.collect();
scored.sort_by(|a, b| {
b.1.partial_cmp(&a.1)
.unwrap_or(std::cmp::Ordering::Equal)
.then(a.0.cmp(b.0))
});
let mut answer = scored.first().map(|(family, score, items)| {
let against = combine(scored.iter().skip(1).map(|(_, score, _)| *score));
(
Some(*family),
score * (1.0 - against),
against,
items.clone(),
)
});
if answer
.as_ref()
.is_none_or(|(_, survived, ..)| percent(*survived) < MIN_REPORTABLE_ACCURACY)
&& !abstained.is_empty()
{
let alone = combine_sources(&abstained);
if answer
.as_ref()
.is_none_or(|(_, survived, ..)| alone > *survived)
{
answer = Some((None, alone, 0.0, Vec::new()));
}
}
let (family, survived, against, mut items) = answer?;
items.extend_from_slice(&abstained);
let accuracy = percent(survived);
if accuracy < MIN_REPORTABLE_ACCURACY {
return None;
}
let agreed = |part: fn(&OsEvidence) -> &Option<String>| -> Option<String> {
let mut stated = items.iter().filter_map(|item| part(item).as_deref());
let candidate = stated.next()?;
stated
.all(|other| other == candidate)
.then(|| candidate.to_owned())
};
let strongest = items
.iter()
.max_by(|a, b| {
a.confidence
.partial_cmp(&b.confidence)
.unwrap_or(std::cmp::Ordering::Equal)
})
.copied()?;
let mut lines: Vec<&str> = items.iter().map(|item| item.evidence.as_str()).collect();
lines.sort_unstable();
lines.dedup();
let (vendor, product, version, kernel, arch, cpe, device) = (
agreed(|item| &item.vendor),
agreed(|item| &item.product),
agreed(|item| &item.version),
agreed(|item| &item.kernel),
agreed(|item| &item.arch),
agreed(|item| &item.cpe),
agreed(|item| &item.device),
);
if family.is_none() && device.is_none() && vendor.is_none() && product.is_none() {
return None;
}
let refined = vendor.is_some()
|| product.is_some()
|| version.is_some()
|| kernel.is_some()
|| arch.is_some()
|| cpe.is_some()
|| device.is_some();
let detail_accuracy = refined.then(|| {
let stated: Vec<&OsEvidence> = items
.iter()
.copied()
.filter(|item| {
item.vendor.is_some()
|| item.product.is_some()
|| item.version.is_some()
|| item.kernel.is_some()
|| item.arch.is_some()
|| item.cpe.is_some()
|| item.device.is_some()
})
.collect();
percent(combine_sources(&stated) * (1.0 - against))
});
Some(OsVerdict {
family: family.map(ToOwned::to_owned),
device,
vendor,
product,
version,
kernel,
arch,
cpe,
accuracy,
detail_accuracy,
source: strongest.source,
evidence: lines.join(" | "),
})
}
fn percent(probability: f32) -> u8 {
(probability * 100.0)
.round()
.clamp(0.0, f32::from(MAX_FUSED_ACCURACY)) as u8
}
fn combine(confidences: impl Iterator<Item = f32>) -> f32 {
let doubt = confidences
.map(|confidence| 1.0 - confidence.clamp(0.0, 1.0))
.product::<f32>();
1.0 - doubt
}
fn combine_sources(items: &[&OsEvidence]) -> f32 {
let mut strongest: BTreeMap<OsSource, f32> = BTreeMap::new();
for item in items {
strongest
.entry(item.source)
.and_modify(|best| *best = best.max(item.confidence))
.or_insert(item.confidence);
}
combine(strongest.into_values())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::model::host::OsSource;
fn a_named_appliance() -> OsEvidence {
OsEvidence {
source: OsSource::SnmpAgent,
family: None,
device: Some("Printer".to_string()),
vendor: Some("Brother".to_string()),
product: Some("NC-8700w".to_string()),
version: Some("ZL".to_string()),
kernel: None,
arch: None,
cpe: None,
confidence: 0.56,
evidence: "snmp agent names NC-8700w".to_string(),
}
}
fn evidence(family: &str, confidence: f32, source: OsSource) -> OsEvidence {
OsEvidence {
source,
family: Some(family.to_string()),
device: None,
vendor: None,
product: None,
version: None,
kernel: None,
arch: None,
cpe: None,
confidence,
evidence: format!("{source:?} says {family}"),
}
}
fn every_source_at_its_ceiling() -> Vec<(OsSource, f32)> {
use super::super::{MAX_STACK_ACCURACY, ceiling, hardware, hostname};
macro_rules! rows {
($($source:ident => $price:expr),+ $(,)?) => {{
let price = |source: OsSource| match source {
$(OsSource::$source => $price),+
};
vec![$((OsSource::$source, price(OsSource::$source))),+]
}};
}
rows![
TcpStack => f32::from(MAX_STACK_ACCURACY) / 100.0,
HardwareVendor => hardware::CONFIDENCE,
ServiceBanner => ceiling(OsSource::ServiceBanner),
SnmpAgent => ceiling(OsSource::SnmpAgent),
MdnsResponder => ceiling(OsSource::MdnsResponder).max(hostname::CONFIDENCE),
Hostname => hostname::CONFIDENCE,
]
}
#[test]
fn two_agreeing_sources_are_worth_more_than_either() {
let stack = evidence("Linux", 0.65, OsSource::TcpStack);
let hardware = evidence("Linux", 0.30, OsSource::HardwareVendor);
let alone = resolve(vec![stack.clone()]).expect("one source names it");
let together = resolve(vec![stack, hardware]).expect("two sources name it");
assert!(together.accuracy > alone.accuracy);
assert_eq!(together.accuracy, 76, "1 - (0.35 x 0.70)");
}
#[test]
fn no_amount_of_agreement_reaches_certainty() {
let many: Vec<OsEvidence> = every_source_at_its_ceiling()
.into_iter()
.map(|(source, _)| evidence("Linux", 0.6, source))
.collect();
let resolved = resolve(many).expect("named");
assert_eq!(
resolved.accuracy, MAX_FUSED_ACCURACY,
"every source agreeing may be highly confident and must not be certain"
);
assert!(
resolved.accuracy < 100,
"certainty is reserved for a host that identified itself"
);
}
#[test]
fn no_single_source_settles_a_host() {
for (source, ceiling) in every_source_at_its_ceiling() {
let naming = |nth: usize| OsEvidence {
version: Some(nth.to_string()),
..evidence("Linux", ceiling, source)
};
let abstaining = |nth: usize| OsEvidence {
family: None,
device: Some("Router".to_string()),
..naming(nth)
};
let shapes: [(&str, Vec<OsEvidence>); 3] = [
("naming a family", (0..20).map(naming).collect()),
("naming only a device", (0..20).map(abstaining).collect()),
(
"mixing the two",
(0..20)
.map(|nth| {
if nth % 2 == 0 {
naming(nth)
} else {
abstaining(nth)
}
})
.collect(),
),
];
for (shape, many) in shapes {
if let Some(resolved) = resolve(many) {
assert!(
!resolved.to_fingerprint().is_highly_confident(),
"{source:?}, {shape}, settled a host on its own at {}",
resolved.accuracy
);
}
}
}
}
#[test]
fn one_source_counts_once_however_many_claims_it_files() {
let alone = resolve(vec![evidence("Linux", 0.55, OsSource::ServiceBanner)])
.expect("a banner names a host");
let contradicting: Vec<OsEvidence> = ["11", "12", "13"]
.into_iter()
.map(|release| OsEvidence {
version: Some(release.to_string()),
..evidence("Linux", 0.55, OsSource::ServiceBanner)
})
.collect();
let resolved = resolve(contradicting).expect("still names the family");
assert_eq!(
resolved.accuracy, alone.accuracy,
"a host that contradicted itself twice is not better attested than one that spoke once"
);
assert!(
resolved.version.is_none(),
"and the release the three disagree about is not reported"
);
}
#[test]
fn distinct_sources_still_corroborate() {
let banner = evidence("Linux", 0.55, OsSource::ServiceBanner);
let stack = evidence("Linux", 0.65, OsSource::TcpStack);
let alone = resolve(vec![stack.clone()]).expect("one source names it");
let both = resolve(vec![banner, stack]).expect("two sources name it");
assert!(
both.accuracy > alone.accuracy,
"a banner agreeing with the wire is worth more than the wire alone"
);
}
#[test]
fn disagreement_lowers_the_answer_rather_than_picking_a_winner() {
let uncontested = resolve(vec![evidence("Linux", 0.65, OsSource::TcpStack)])
.expect("one source names it")
.accuracy;
let contested = resolve(vec![
evidence("Linux", 0.65, OsSource::TcpStack),
evidence("Windows", 0.30, OsSource::HardwareVendor),
])
.expect("the leader survives one dissenter");
assert_eq!(contested.family.as_deref(), Some("Linux"));
assert!(
contested.accuracy < uncontested,
"a contested verdict must not score what an uncontested one does"
);
}
#[test]
fn an_even_conflict_names_nothing() {
assert!(
resolve(vec![
evidence("Linux", 0.65, OsSource::TcpStack),
evidence("Windows", 0.65, OsSource::HardwareVendor),
])
.is_none()
);
}
#[test]
fn a_source_with_nothing_to_say_about_a_product_does_not_veto_one() {
let mut precise = evidence("Linux", 0.65, OsSource::TcpStack);
precise.product = Some("Ubuntu".to_string());
let vague = evidence("Linux", 0.30, OsSource::HardwareVendor);
let resolved = resolve(vec![precise, vague]).expect("named");
assert_eq!(resolved.family.as_deref(), Some("Linux"));
assert_eq!(
resolved.product.as_deref(),
Some("Ubuntu"),
"the only source that could name a product named one, and nothing contradicted it"
);
}
#[test]
fn two_sources_naming_different_products_keep_neither() {
let mut stack = evidence("Linux", 0.65, OsSource::TcpStack);
stack.product = Some("Ubuntu".to_string());
let mut banner = evidence("Linux", 0.65, OsSource::ServiceBanner);
banner.product = Some("Debian".to_string());
let resolved = resolve(vec![stack, banner]).expect("the family is agreed");
assert_eq!(resolved.family.as_deref(), Some("Linux"));
assert_eq!(resolved.product, None);
}
#[test]
fn the_answer_does_not_depend_on_the_order_evidence_arrived_in() {
let a = evidence("Linux", 0.5, OsSource::TcpStack);
let b = evidence("macOS", 0.5, OsSource::HardwareVendor);
assert_eq!(
resolve(vec![a.clone(), b.clone()]),
resolve(vec![b, a]),
"the same evidence in the other order is the same evidence"
);
}
#[test]
fn nothing_in_names_nothing_out() {
assert!(resolve(Vec::new()).is_none());
}
#[test]
fn a_source_that_names_no_family_does_not_argue_with_one_that_does() {
let stack = evidence("Network device", 0.4, OsSource::TcpStack);
let resolved = resolve(vec![stack.clone(), a_named_appliance()]).expect("named");
assert_eq!(resolved.family.as_deref(), Some("Network device"));
assert_eq!(
resolved.accuracy,
percent(0.4),
"unreduced: nothing dissented"
);
assert_eq!(resolved.vendor.as_deref(), Some("Brother"));
assert_eq!(resolved.product.as_deref(), Some("NC-8700w"));
assert_eq!(resolved.device.as_deref(), Some("Printer"));
}
#[test]
fn an_abstention_alone_is_still_an_answer() {
let resolved = resolve(vec![a_named_appliance()]).expect("named");
assert_eq!(resolved.family, None);
assert_eq!(resolved.product.as_deref(), Some("NC-8700w"));
assert_eq!(resolved.accuracy, percent(0.56));
}
#[test]
fn a_family_too_contested_to_report_does_not_take_the_rest_with_it() {
let one = evidence("Linux", 0.5, OsSource::TcpStack);
let other = evidence("Windows", 0.5, OsSource::HardwareVendor);
assert!(
resolve(vec![one.clone(), other.clone()]).is_none(),
"two sources this far apart name nothing between them"
);
let resolved = resolve(vec![one, other, a_named_appliance()]).expect("named");
assert_eq!(
resolved.family, None,
"the contested family is still refused"
);
assert_eq!(resolved.product.as_deref(), Some("NC-8700w"));
}
#[test]
fn a_device_class_on_its_own_is_a_verdict() {
let class_only = OsEvidence {
vendor: None,
product: None,
version: None,
confidence: 0.5,
..a_named_appliance()
};
let resolved = resolve(vec![class_only]).expect("the class is the answer");
assert_eq!(resolved.device.as_deref(), Some("Printer"));
assert_eq!(
resolved.family, None,
"it still says nothing about software"
);
assert_eq!(
resolved.label(),
"Printer",
"and that is what a reader sees"
);
}
#[test]
fn evidence_that_establishes_no_part_of_an_identity_is_refused() {
let says_nothing = OsEvidence {
family: None,
device: None,
vendor: None,
product: None,
version: None,
..a_named_appliance()
};
assert!(resolve(vec![says_nothing]).is_none());
}
}