Skip to main content

zond_engine/diff/
pairing.rs

1// Copyright (c) 2026 Erik Lening (hollowpointer) and Contributors
2//
3// This file is part of Zond Engine, licensed under the GNU Affero General
4// Public License, version 3 or later. See the LICENSE file for details, or
5// <https://www.gnu.org/licenses/agpl-3.0.html>.
6//
7// SPDX-License-Identifier: AGPL-3.0-or-later
8
9//! # Deciding which record describes which host
10//!
11//! Ports pair by number and transport, which is exact. Hosts do not: a machine can
12//! change address between two scans, answer at one address in one scan and
13//! another in the next, or be seen as one record by a privileged scan and two by
14//! an unprivileged one. Pairing them wrong invents a host that appeared and one
15//! that vanished.
16//!
17//! ## How the decision is made
18//!
19//! Each record yields a set of identity tokens under the caller's
20//! [`HostIdentity`] policy. A baseline record and a current record are linked
21//! when they share a token. The links form a bipartite graph, and each connected
22//! component of that graph is one host as far as the comparison is concerned.
23//!
24//! Greedy pairing would have to break ties, and a tie is information. A component
25//! with one record on each side is the ordinary case. One record on one side and
26//! two on the other means the scans grouped the same addresses differently, which
27//! is reported as such.
28//!
29//! ## Link-local addresses carry their interface
30//!
31//! `fe80::1` names a different machine on every segment, so the token for a
32//! link-local address includes the zone the record was found on.
33//!
34//! A record that names no zone gets no zone in its token, and two of those at one
35//! address fold together. Only a scan that reached the link layer records a zone,
36//! so a report rebuilt from a foreign scanner's output always lands here. Pairing
37//! under [`PrimaryAddress`](HostIdentity::PrimaryAddress) declines the guess.
38
39use std::collections::hash_map::Entry;
40use std::collections::{HashMap, HashSet};
41use std::net::IpAddr;
42use std::sync::Arc;
43
44use crate::model::host::Host;
45use crate::model::mac::MacAddr;
46
47/// What makes two records, in two different scans, the same host.
48///
49/// The default is [`AnyAddress`](Self::AnyAddress), which follows a dual-stack
50/// host keyed under IPv4 one night and IPv6 the next.
51#[non_exhaustive]
52#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
53pub enum HostIdentity {
54    /// Two records are the same host when their primary addresses match.
55    ///
56    /// The strictest policy. A host whose primary address changed reads as one
57    /// host gone and another arrived, which is right when the address is the
58    /// asset, as in an external scan of a public range.
59    PrimaryAddress,
60
61    /// Two records are the same host when they share any address.
62    ///
63    /// Follows a host whose primary address was re-picked between scans, as
64    /// happens when a global address displaces a link-local one or a dual-stack
65    /// host answers over the other family first.
66    #[default]
67    AnyAddress,
68
69    /// As [`AnyAddress`](Self::AnyAddress), and two records are also the same
70    /// host when they share a hardware address.
71    ///
72    /// Follows a machine across a DHCP lease change on a segment where the scan
73    /// reached the link layer. Not the default because a hardware address is not
74    /// always the host's own: a router answering ARP for the machines behind it
75    /// lends them its address, and under this policy they fold into one.
76    Hardware,
77}
78
79/// One host, as the two scans hold it.
80///
81/// Indices into the baseline and current host lists the comparison was given.
82/// Both are ascending. An empty side is a host only the other scan has.
83#[derive(Debug, Clone, PartialEq, Eq)]
84pub(crate) struct Component {
85    pub(crate) baseline: Vec<usize>,
86    pub(crate) current: Vec<usize>,
87}
88
89/// What links two records into one host.
90#[derive(Debug, Clone, PartialEq, Eq, Hash)]
91enum Token {
92    /// An address, with its zone when it is link-local.
93    Address(IpAddr, Option<Arc<str>>),
94    /// A hardware address the record was seen at.
95    Hardware(MacAddr),
96}
97
98/// Groups the two host lists into components, ascending by lowest baseline index
99/// and then by lowest current index, so the same two reports always compare to
100/// the same list.
101pub(crate) fn components(
102    baseline: &[&Host],
103    current: &[&Host],
104    identity: HostIdentity,
105) -> Vec<Component> {
106    let baseline_tokens: Vec<HashSet<Token>> =
107        baseline.iter().map(|host| tokens(host, identity)).collect();
108    let current_tokens: Vec<HashSet<Token>> =
109        current.iter().map(|host| tokens(host, identity)).collect();
110
111    let mut baseline_index = index(&baseline_tokens);
112    let mut current_index = index(&current_tokens);
113
114    let mut baseline_seen = vec![false; baseline.len()];
115    let mut current_seen = vec![false; current.len()];
116    let mut components = Vec::new();
117
118    for start in 0..baseline.len() {
119        if baseline_seen[start] {
120            continue;
121        }
122        baseline_seen[start] = true;
123
124        let mut component = Component {
125            baseline: Vec::new(),
126            current: Vec::new(),
127        };
128        let mut baseline_queue = vec![start];
129        let mut current_queue: Vec<usize> = Vec::new();
130
131        // Alternating flood fill across the two sides. Each record is queued at
132        // most once, and each token's list is removed as it is walked, so it is
133        // walked at most once. That matters under `Hardware`: a router answering
134        // ARP for a segment puts its address on every record, and walking the
135        // list per record would be quadratic.
136        while !baseline_queue.is_empty() || !current_queue.is_empty() {
137            while let Some(i) = baseline_queue.pop() {
138                component.baseline.push(i);
139                for token in &baseline_tokens[i] {
140                    for j in current_index.remove(token).unwrap_or_default() {
141                        if !current_seen[j] {
142                            current_seen[j] = true;
143                            current_queue.push(j);
144                        }
145                    }
146                }
147            }
148
149            while let Some(j) = current_queue.pop() {
150                component.current.push(j);
151                for token in &current_tokens[j] {
152                    for i in baseline_index.remove(token).unwrap_or_default() {
153                        if !baseline_seen[i] {
154                            baseline_seen[i] = true;
155                            baseline_queue.push(i);
156                        }
157                    }
158                }
159            }
160        }
161
162        component.baseline.sort_unstable();
163        component.current.sort_unstable();
164        components.push(component);
165    }
166
167    // Whatever the flood fill never reached is a host only the current scan
168    // holds.
169    for (j, seen) in current_seen.iter().enumerate() {
170        if !seen {
171            components.push(Component {
172                baseline: Vec::new(),
173                current: vec![j],
174            });
175        }
176    }
177
178    components.sort_by_key(|component| {
179        (
180            component.baseline.first().copied().unwrap_or(usize::MAX),
181            component.current.first().copied().unwrap_or(usize::MAX),
182        )
183    });
184    components
185}
186
187/// Groups records from any number of sources into one entry per host.
188///
189/// Records are given flattened, in the order the caller wants them folded, and
190/// come back as groups of indices into that list: ascending within a group, and
191/// the groups ascending by their lowest index, so the same input always groups
192/// the same way.
193///
194/// [`components`] answers a different question: which of tonight's records
195/// continues which of last night's. There, two baseline records that share an
196/// address stay two records and `HostDelta::is_regrouped` reports the
197/// disagreement. Here, records sharing an address are one host whichever
198/// document they came from. The tokens, identity policy and link-local zone rule
199/// are shared.
200pub(crate) fn groups(records: &[&Host], identity: HostIdentity) -> Vec<Vec<usize>> {
201    let mut sets = DisjointSet::new(records.len());
202    let mut first_holder: HashMap<Token, usize> = HashMap::new();
203
204    for (i, host) in records.iter().enumerate() {
205        for token in tokens(host, identity) {
206            match first_holder.entry(token) {
207                Entry::Occupied(held) => sets.union(*held.get(), i),
208                Entry::Vacant(slot) => {
209                    slot.insert(i);
210                }
211            }
212        }
213    }
214
215    // Roots in first-appearance order are ascending by lowest member.
216    let mut grouped: HashMap<usize, Vec<usize>> = HashMap::new();
217    let mut order: Vec<usize> = Vec::new();
218    for i in 0..records.len() {
219        let root = sets.find(i);
220        grouped.entry(root).or_insert_with(|| {
221            order.push(root);
222            Vec::new()
223        });
224        grouped.get_mut(&root).expect("just inserted").push(i);
225    }
226
227    order
228        .into_iter()
229        .map(|root| grouped.remove(&root).expect("a root that was recorded"))
230        .collect()
231}
232
233/// Union-find over record indices, by size with path compression.
234struct DisjointSet {
235    parent: Vec<usize>,
236    size: Vec<usize>,
237}
238
239impl DisjointSet {
240    fn new(len: usize) -> Self {
241        Self {
242            parent: (0..len).collect(),
243            size: vec![1; len],
244        }
245    }
246
247    fn find(&mut self, mut i: usize) -> usize {
248        while self.parent[i] != i {
249            self.parent[i] = self.parent[self.parent[i]];
250            i = self.parent[i];
251        }
252        i
253    }
254
255    fn union(&mut self, a: usize, b: usize) {
256        let (mut a, mut b) = (self.find(a), self.find(b));
257        if a == b {
258            return;
259        }
260        if self.size[a] < self.size[b] {
261            std::mem::swap(&mut a, &mut b);
262        }
263        self.parent[b] = a;
264        self.size[a] += self.size[b];
265    }
266}
267
268/// The tokens a record is linked by under `identity`.
269fn tokens(host: &Host, identity: HostIdentity) -> HashSet<Token> {
270    let zone = host.zone().map(|zone| Arc::from(zone.name()));
271
272    let mut tokens: HashSet<Token> = match identity {
273        HostIdentity::PrimaryAddress => {
274            let ip = host.primary_ip();
275            HashSet::from([Token::Address(ip, scope_of(&ip, &zone))])
276        }
277        HostIdentity::AnyAddress | HostIdentity::Hardware => host
278            .ips()
279            .iter()
280            .map(|ip| Token::Address(*ip, scope_of(ip, &zone)))
281            .collect(),
282    };
283
284    if identity == HostIdentity::Hardware
285        && let Some(hardware) = host.hardware()
286    {
287        tokens.extend(hardware.macs().keys().copied().map(Token::Hardware));
288    }
289
290    tokens
291}
292
293/// The zone that disambiguates `ip`, for link-local addresses only. A global
294/// address is the same machine on every interface.
295fn scope_of(ip: &IpAddr, zone: &Option<Arc<str>>) -> Option<Arc<str>> {
296    is_link_local(ip).then(|| zone.clone()).flatten()
297}
298
299/// Whether an address is only meaningful on one link.
300fn is_link_local(ip: &IpAddr) -> bool {
301    match ip {
302        IpAddr::V4(v4) => v4.is_link_local(),
303        IpAddr::V6(v6) => (v6.segments()[0] & 0xffc0) == 0xfe80,
304    }
305}
306
307/// Which records carry each token.
308fn index(tokens: &[HashSet<Token>]) -> HashMap<&Token, Vec<usize>> {
309    let mut index: HashMap<&Token, Vec<usize>> = HashMap::new();
310    for (i, set) in tokens.iter().enumerate() {
311        for token in set {
312            index.entry(token).or_default().push(i);
313        }
314    }
315    index
316}
317
318// ╔════════════════════════════════════════════╗
319// ║ ████████╗███████╗███████╗████████╗███████╗ ║
320// ║ ╚══██╔══╝██╔════╝██╔════╝╚══██╔══╝██╔════╝ ║
321// ║    ██║   █████╗  ███████╗   ██║   ███████╗ ║
322// ║    ██║   ██╔══╝  ╚════██║   ██║   ╚════██║ ║
323// ║    ██║   ███████╗███████║   ██║   ███████║ ║
324// ║    ╚═╝   ╚══════╝╚══════╝   ╚═╝   ╚══════╝ ║
325// ╚════════════════════════════════════════════╝
326
327#[cfg(test)]
328mod tests {
329    use std::net::{Ipv4Addr, Ipv6Addr};
330
331    use super::*;
332    use crate::model::host::HostStatus;
333    use crate::model::ip::scoped::Zone;
334    use crate::model::mac::MacAddr;
335
336    fn v4(last: u8) -> IpAddr {
337        IpAddr::V4(Ipv4Addr::new(203, 0, 113, last))
338    }
339
340    fn host(primary: IpAddr) -> Host {
341        let mut host = Host::new(primary);
342        host.set_status(HostStatus::Up);
343        host
344    }
345
346    /// Components, sorted so an assertion does not depend on iteration order.
347    fn shape(components: &[Component]) -> Vec<(Vec<usize>, Vec<usize>)> {
348        let mut out: Vec<(Vec<usize>, Vec<usize>)> = components
349            .iter()
350            .map(|c| {
351                let mut b = c.baseline.clone();
352                let mut n = c.current.clone();
353                b.sort_unstable();
354                n.sort_unstable();
355                (b, n)
356            })
357            .collect();
358        out.sort();
359        out
360    }
361
362    #[test]
363    fn a_host_at_the_same_address_pairs_with_itself() {
364        let before = [host(v4(1))];
365        let after = [host(v4(1))];
366        let components = components(
367            &before.iter().collect::<Vec<_>>(),
368            &after.iter().collect::<Vec<_>>(),
369            HostIdentity::AnyAddress,
370        );
371        assert_eq!(shape(&components), vec![(vec![0], vec![0])]);
372    }
373
374    #[test]
375    fn hosts_sharing_no_address_do_not_pair() {
376        let before = [host(v4(1))];
377        let after = [host(v4(2))];
378        let components = components(
379            &before.iter().collect::<Vec<_>>(),
380            &after.iter().collect::<Vec<_>>(),
381            HostIdentity::AnyAddress,
382        );
383        assert_eq!(
384            shape(&components),
385            vec![(vec![], vec![0]), (vec![0], vec![])],
386            "one host went away and another arrived"
387        );
388    }
389
390    /// A machine answering at a second address in the later scan is one host.
391    #[test]
392    fn a_shared_secondary_address_pairs_two_records() {
393        let mut before = host(v4(1));
394        before.add_ip(v4(50));
395        let after = host(v4(50));
396
397        let components = components(&[&before], &[&after], HostIdentity::AnyAddress);
398        assert_eq!(shape(&components), vec![(vec![0], vec![0])]);
399    }
400
401    /// Under `PrimaryAddress` the same pair does not, because only the primary
402    /// is a token.
403    #[test]
404    fn a_shared_secondary_address_does_not_pair_under_primary_address() {
405        let mut before = host(v4(1));
406        before.add_ip(v4(50));
407        let after = host(v4(50));
408
409        let components = components(&[&before], &[&after], HostIdentity::PrimaryAddress);
410        assert_eq!(
411            shape(&components),
412            vec![(vec![], vec![0]), (vec![0], vec![])]
413        );
414    }
415
416    /// Two records on one side and one on the other form one component.
417    #[test]
418    fn records_the_two_scans_grouped_differently_form_one_component() {
419        let mut merged = host(v4(1));
420        merged.add_ip(v4(2));
421        let split_a = host(v4(1));
422        let split_b = host(v4(2));
423
424        let components = components(&[&merged], &[&split_a, &split_b], HostIdentity::AnyAddress);
425        assert_eq!(shape(&components), vec![(vec![0], vec![0, 1])]);
426    }
427
428    /// `fe80::1` names a different machine on every segment, so two records on
429    /// two interfaces must not fold into one.
430    #[test]
431    fn link_local_addresses_on_different_zones_are_different_hosts() {
432        let link_local = IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 1));
433
434        let mut before = Host::new(link_local);
435        before.set_zone(Zone::new(1, "en0"));
436        before.set_status(HostStatus::Up);
437
438        let mut after = Host::new(link_local);
439        after.set_zone(Zone::new(2, "en1"));
440        after.set_status(HostStatus::Up);
441
442        let components = components(&[&before], &[&after], HostIdentity::AnyAddress);
443        assert_eq!(
444            shape(&components),
445            vec![(vec![], vec![0]), (vec![0], vec![])],
446            "the same link-local address on two segments is two machines"
447        );
448    }
449
450    #[test]
451    fn hardware_identity_pairs_a_host_that_changed_address() {
452        let mac = MacAddr::new(0x2c, 0xcf, 0x67, 0x00, 0x00, 0x01);
453
454        let mut before = host(v4(1));
455        before.record_mac(mac);
456        let mut after = host(v4(2));
457        after.record_mac(mac);
458
459        let components = components(&[&before], &[&after], HostIdentity::Hardware);
460        assert_eq!(
461            shape(&components),
462            vec![(vec![0], vec![0])],
463            "a DHCP lease moving is not a host being replaced"
464        );
465    }
466
467    #[test]
468    fn groups_folds_records_that_share_an_address() {
469        let mut one = host(v4(1));
470        one.add_ip(v4(9));
471        let two = host(v4(9));
472        let three = host(v4(3));
473
474        let mut groups = groups(&[&one, &two, &three], HostIdentity::AnyAddress);
475        for group in &mut groups {
476            group.sort_unstable();
477        }
478        groups.sort();
479        assert_eq!(groups, vec![vec![0, 1], vec![2]]);
480    }
481}