zond-engine 0.17.0

The core networking library powering Zond. Raw packet injection, protocol parsing, service and OS fingerprinting, and asynchronous network scanning.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
// Copyright (c) 2026 Erik Lening (hollowpointer) and Contributors
//
// This file is part of Zond Engine, licensed under the GNU Affero General
// Public License, version 3 or later. See the LICENSE file for details, or
// <https://www.gnu.org/licenses/agpl-3.0.html>.
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! # The route a probe took to reach a host
//!
//! [`NetworkPath`] is the sequence of routers between this machine and one
//! target: what a traceroute establishes, and the one finding in this engine
//! that describes the space *between* two addresses rather than either of them.
//!
//! ## A hop is a distance, not an index
//!
//! Every [`Hop`] carries the [`distance`](Hop::distance) it was measured at,
//! meaning the hop limit whose expiry produced it, rather than being identified
//! by its position in a list. The two come apart constantly:
//!
//! - **A router may decline to answer.** Many do not send Time Exceeded at all,
//!   or rate-limit it to nothing. That leaves a gap, and a gap has to stay a gap:
//!   collapsing the list would silently renumber every router beyond it and
//!   report a five-hop path as four.
//! - **A path may be spliced.** When one trace recognises a router another trace
//!   already found, the rest is taken from the earlier one rather than measured
//!   again; see [`Hop::inferred`]. Those hops keep the distance they were
//!   originally measured at.
//!
//! So a path is stored sorted by distance, may have holes in it, and a reader
//! that wants "the third router" should ask for distance three rather than index
//! two.
//!
//! ## A router the scan may not name
//!
//! A router whose address falls under the scan's
//! [`Exclusions`](crate::model::exclusion::Exclusions) keeps its distance and
//! loses its address: see [`Hop::withheld`]. The policy promises that no
//! excluded address appears in the report, and a trace hears from such a
//! router without having asked it anything, since the probe it discarded was
//! addressed to somebody else. Nothing was sent to it, so the recording half of
//! the promise is the only half a path can break.
//!
//! Each of the other shapes that would keep the address out says something
//! false. Recorded as silent, the hop claims nothing answered when a router did.
//! Left out, the distance reads as one the trace knows nothing about, and where
//! it is the furthest router a trace reached, the path reads a router shorter
//! than it is. What a withheld hop says instead is exactly what the report may
//! say: a router stood at this distance on the way to this host, and the scan
//! will not say which.
//!
//! ## What a hop does and does not establish
//!
//! It establishes that a router at that address discarded a packet of ours that
//! had travelled that far. That is a strong statement: a router is
//! obliged to identify itself when it discards a packet (RFC 792, RFC 4443
//! ยง3.3), where it is under no obligation at all when it forwards one.
//!
//! It does not establish that the router is *on* the path in any other sense.
//! The address a router replies from is the one it chose, usually the
//! interface the probe arrived on but not always the same one on the way back.
//! Two traces to neighbouring hosts can name different addresses for what is
//! physically one device, and nothing here can tell.
//!
//! A round-trip time is to the router rather than between routers. It is measured
//! from this machine, so hop three's timing includes hops one and two. It is also
//! the time a router took to generate an error, which many treat as the
//! lowest-priority work they do, so a hop slower than the one after it is ordinary
//! and says nothing about the path.

use std::net::IpAddr;
use std::time::Duration;

/// One router on the way to a host, at a known distance.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Hop {
    distance: u8,
    answer: Answer,
    rtt: Option<Duration>,
    inferred: bool,
}

/// What was heard from a distance.
///
/// One value rather than an address and a flag beside it, so that a withheld
/// hop carrying an address cannot be built.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Answer {
    /// Nothing answered.
    Silent,
    /// A router answered, from this address.
    Router(IpAddr),
    /// A router answered, from an address the scan may not report.
    Withheld,
}

impl Hop {
    /// A router that answered, at `distance` hops, in `rtt`.
    pub fn answered(distance: u8, address: IpAddr, rtt: Option<Duration>) -> Self {
        Self {
            distance,
            answer: Answer::Router(address),
            rtt,
            inferred: false,
        }
    }

    /// A distance nothing answered at.
    ///
    /// Recorded rather than omitted, because the two are different findings and
    /// only one of them is about the network. A missing entry would say the path
    /// is shorter than it is; this says a router is there and would not say so.
    pub fn silent(distance: u8) -> Self {
        Self {
            distance,
            answer: Answer::Silent,
            rtt: None,
            inferred: false,
        }
    }

    /// A distance a router answered at, from an address the scan's exclusions
    /// forbid it to report.
    ///
    /// Neither [`silent`](Self::silent), which would say nothing answered, nor
    /// left out, which would say nothing is known; the module documentation
    /// weighs the three. It carries no round trip either: that times the
    /// router's own generation of an error, which is a fact about the router
    /// rather than about the route.
    ///
    /// A scan does not build these by hand. A router is recorded as it
    /// answered, and the scan withholds its address where the policy names it,
    /// on every way a hop reaches a host's record. This is how a record of one
    /// is read back.
    pub fn withheld(distance: u8) -> Self {
        Self {
            distance,
            answer: Answer::Withheld,
            rtt: None,
            inferred: false,
        }
    }

    /// The same hop, marked as taken from another host's trace rather than
    /// measured on this one. See [`inferred`](Self::inferred).
    #[must_use]
    pub fn as_inferred(mut self) -> Self {
        self.inferred = true;
        // A round trip belongs to the trace that measured it. Carrying one
        // across would report a timing for a probe this host never drew.
        self.rtt = None;
        self
    }

    /// How many hops from this machine this router sits.
    pub fn distance(&self) -> u8 {
        self.distance
    }

    /// The address the router answered from, or `None` if nothing answered at
    /// this distance or the address is [withheld](Self::is_withheld).
    pub fn address(&self) -> Option<IpAddr> {
        match self.answer {
            Answer::Router(address) => Some(address),
            Answer::Silent | Answer::Withheld => None,
        }
    }

    /// How long the probe that expired here took to be answered, measured from
    /// this machine. `None` for a silent hop, an inferred one and a withheld
    /// one.
    pub fn rtt(&self) -> Option<Duration> {
        self.rtt
    }

    /// Whether a router answered here from an address the scan may not report.
    ///
    /// The one case where [`address`](Self::address) is `None` and something
    /// answered, so a reader drawing a path has to ask this before it draws a
    /// gap: a withheld router is there and did identify itself, and the scan
    /// declines to repeat what it said. See [`withheld`](Self::withheld).
    pub fn is_withheld(&self) -> bool {
        self.answer == Answer::Withheld
    }

    /// Whether anything answered at this distance, whether or not the report
    /// may say what.
    fn is_answer(&self) -> bool {
        self.answer != Answer::Silent
    }

    /// Whether this hop was measured on the way to *this* host, or copied from
    /// an earlier trace that passed through the same router.
    ///
    /// A path assembled partly from another host's trace is a weaker claim than
    /// one probed end to end: the two hosts were assumed to share everything
    /// upstream of the router where the traces met, which is true of nearly every
    /// network and is still an assumption. A reader acting
    /// on a single hop should know which kind they are looking at, and a report
    /// that did not distinguish them would present an inference as a
    /// measurement.
    pub fn inferred(&self) -> bool {
        self.inferred
    }
}

/// The routers between this machine and one host, in order of distance.
///
/// Sorted by distance and holding at most one hop per distance. Both invariants
/// are established by [`record`](Self::record), which is the only way in, and
/// the only other change a path takes is withholding a router's address, which
/// rewrites a hop where it stands and never moves one.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct NetworkPath {
    hops: Vec<Hop>,
}

impl NetworkPath {
    /// An empty path.
    pub fn new() -> Self {
        Self::default()
    }

    /// Records `hop`, replacing whatever was known at that distance.
    ///
    /// A measurement replaces an inference and never the reverse. A trace
    /// that spliced in another host's hops and then measured one of them for
    /// itself has learned something; the same in reverse would throw away the
    /// stronger of two claims about the same router. An answered hop likewise
    /// replaces a silent one, since silence is the absence of a finding rather
    /// than a finding of absence. A [withheld](Hop::withheld) hop is an answered
    /// one: a router answered there, and only its address goes unreported.
    pub fn record(&mut self, hop: Hop) {
        match self
            .hops
            .binary_search_by_key(&hop.distance, |known| known.distance)
        {
            Ok(index) => {
                let known = &self.hops[index];
                // The two rules above are ranked rather than added together.
                // Whether anything answered comes first, because silence is the
                // absence of a finding and an answer is one; provenance decides
                // only between two hops that agree about that.
                //
                // Or-ing them let a *measured silence* displace an *inferred
                // answer*, which is a router's address traded for the news that
                // it declined to answer this time. `Host::merge` replays one
                // record's hops into another's in whatever order the two were
                // folded, so it took no exotic trace to reach.
                let stronger = match (known.is_answer(), hop.is_answer()) {
                    (false, true) => true,
                    (true, false) => false,
                    _ => known.inferred && !hop.inferred,
                };
                if stronger {
                    self.hops[index] = hop;
                }
            }
            Err(index) => self.hops.insert(index, hop),
        }
    }

    /// Withholds the address of every router `keep` refuses, and returns
    /// whether it withheld any.
    ///
    /// For the exclusion policy, which holds for the routers on a host's path as
    /// it does for the host's own addresses. Each refused hop becomes
    /// [`Hop::withheld`] at the same distance and with the same provenance, so a
    /// spliced router stays marked as spliced, and loses its round trip with
    /// its address.
    pub(crate) fn withhold(&mut self, keep: impl Fn(&IpAddr) -> bool) -> bool {
        let mut withheld = false;
        for hop in &mut self.hops {
            if let Answer::Router(address) = hop.answer
                && !keep(&address)
            {
                *hop = Hop {
                    inferred: hop.inferred,
                    ..Hop::withheld(hop.distance)
                };
                withheld = true;
            }
        }
        withheld
    }

    /// Every hop, ascending by distance. May have gaps; see the module docs.
    pub fn hops(&self) -> &[Hop] {
        &self.hops
    }

    /// Whether anything is known about the path at all.
    pub fn is_empty(&self) -> bool {
        self.hops.is_empty()
    }

    /// How far away the furthest known router is, or `None` for an empty path.
    ///
    /// The last *known* distance rather than a count of hops, which differ
    /// whenever a router declined to answer.
    pub fn length(&self) -> Option<u8> {
        self.hops.last().map(Hop::distance)
    }

    /// The address at `distance`, if a router answered there and its address
    /// is not withheld.
    pub fn at(&self, distance: u8) -> Option<IpAddr> {
        self.hops
            .binary_search_by_key(&distance, |hop| hop.distance)
            .ok()
            .and_then(|index| self.hops[index].address())
    }
}

// โ•”โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•—
// โ•‘ โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•—โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•—โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•—โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•—โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•— โ•‘
// โ•‘ โ•šโ•โ•โ–ˆโ–ˆโ•”โ•โ•โ•โ–ˆโ–ˆโ•”โ•โ•โ•โ•โ•โ–ˆโ–ˆโ•”โ•โ•โ•โ•โ•โ•šโ•โ•โ–ˆโ–ˆโ•”โ•โ•โ•โ–ˆโ–ˆโ•”โ•โ•โ•โ•โ• โ•‘
// โ•‘    โ–ˆโ–ˆโ•‘   โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•—  โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•—   โ–ˆโ–ˆโ•‘   โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•— โ•‘
// โ•‘    โ–ˆโ–ˆโ•‘   โ–ˆโ–ˆโ•”โ•โ•โ•  โ•šโ•โ•โ•โ•โ–ˆโ–ˆโ•‘   โ–ˆโ–ˆโ•‘   โ•šโ•โ•โ•โ•โ–ˆโ–ˆโ•‘ โ•‘
// โ•‘    โ–ˆโ–ˆโ•‘   โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•—โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•‘   โ–ˆโ–ˆโ•‘   โ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ–ˆโ•‘ โ•‘
// โ•‘    โ•šโ•โ•   โ•šโ•โ•โ•โ•โ•โ•โ•โ•šโ•โ•โ•โ•โ•โ•โ•   โ•šโ•โ•   โ•šโ•โ•โ•โ•โ•โ•โ• โ•‘
// โ•šโ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•

#[cfg(test)]
mod tests {
    use super::*;
    use std::net::Ipv4Addr;

    fn ip(last: u8) -> IpAddr {
        IpAddr::V4(Ipv4Addr::new(10, 0, 0, last))
    }

    /// An answer displaces silence whatever measured it, and provenance decides
    /// only between two hops that agree about whether anything answered.
    ///
    /// The two rules are ranked. Added together, as they were, a *measured
    /// silent* hop displaced an *inferred answered* one: a router's address
    /// traded for the news that it declined to answer this time, which is the
    /// absence of a finding rather than a finding of absence. `Host::merge`
    /// replays one record's hops into another's in whatever order the two were
    /// folded, so it took no exotic trace to reach.
    #[test]
    fn an_answer_is_never_traded_for_a_silence_that_measured_it() {
        let spliced = Hop::answered(4, ip(4), None).as_inferred();

        let mut path = NetworkPath::new();
        path.record(spliced);
        path.record(Hop::silent(4));
        assert_eq!(
            path.at(4),
            Some(ip(4)),
            "a measured silence does not erase a router somebody found"
        );

        // And the other way round, which was already right.
        let mut reverse = NetworkPath::new();
        reverse.record(Hop::silent(4));
        reverse.record(spliced);
        assert_eq!(reverse.at(4), Some(ip(4)));

        // Where both answered, the measurement wins, which is the rule that
        // ranking these did not weaken.
        let mut both = NetworkPath::new();
        both.record(Hop::answered(1, ip(9), None).as_inferred());
        both.record(Hop::answered(1, ip(1), None));
        assert_eq!(both.at(1), Some(ip(1)), "a measurement beats an inference");

        // And where neither did, an inference has nothing to offer a
        // measurement, so the record stands.
        let mut neither = NetworkPath::new();
        neither.record(Hop::silent(2));
        neither.record(Hop::silent(2).as_inferred());
        assert_eq!(neither.hops().len(), 1);
        assert!(!neither.hops()[0].inferred());
    }

    /// Hops arrive in whatever order their replies do, and a path reads in
    /// order of distance regardless.
    ///
    /// Traces run their probes concurrently, so hop five is answered before hop
    /// two often enough that ordering on arrival would be the common case rather
    /// than the odd one.
    #[test]
    fn a_path_reads_in_order_of_distance_however_the_replies_arrived() {
        let mut path = NetworkPath::new();
        path.record(Hop::answered(3, ip(3), None));
        path.record(Hop::answered(1, ip(1), None));
        path.record(Hop::answered(2, ip(2), None));

        let distances: Vec<u8> = path.hops().iter().map(Hop::distance).collect();
        assert_eq!(distances, vec![1, 2, 3]);
        assert_eq!(path.length(), Some(3));
        assert_eq!(path.at(2), Some(ip(2)));
    }

    /// A router that will not answer leaves a hole, and the hole is the finding.
    ///
    /// Dropping it would renumber everything past it: this path would read as
    /// two hops long when the target is three routers away.
    #[test]
    fn a_silent_router_holds_its_place() {
        let mut path = NetworkPath::new();
        path.record(Hop::answered(1, ip(1), None));
        path.record(Hop::silent(2));
        path.record(Hop::answered(3, ip(3), None));

        assert_eq!(path.hops().len(), 3);
        assert_eq!(path.at(2), None);
        assert_eq!(path.length(), Some(3), "the target is still three away");
    }

    /// What is known about a distance only ever gets stronger.
    ///
    /// The three transitions that must hold, and the three that must not. A
    /// trace which splices another host's hops and then measures one for itself
    /// has to keep the measurement; the same events in the other order must not
    /// throw it away, and reply ordering decides which order they arrive in.
    #[test]
    fn a_measurement_outranks_an_inference_and_an_answer_outranks_silence() {
        let measured = Hop::answered(2, ip(2), Some(Duration::from_millis(5)));
        let inferred = Hop::answered(2, ip(9), None).as_inferred();

        let mut upgrading = NetworkPath::new();
        upgrading.record(inferred);
        upgrading.record(measured);
        assert_eq!(upgrading.at(2), Some(ip(2)));
        assert!(!upgrading.hops()[0].inferred());

        let mut downgrading = NetworkPath::new();
        downgrading.record(measured);
        downgrading.record(inferred);
        assert_eq!(downgrading.at(2), Some(ip(2)), "a measurement is not lost");
        assert_eq!(downgrading.hops()[0].rtt(), Some(Duration::from_millis(5)));

        let mut filling = NetworkPath::new();
        filling.record(Hop::silent(2));
        filling.record(measured);
        assert_eq!(filling.at(2), Some(ip(2)));

        let mut keeping = NetworkPath::new();
        keeping.record(measured);
        keeping.record(Hop::silent(2));
        assert_eq!(
            keeping.at(2),
            Some(ip(2)),
            "silence does not erase an answer"
        );
    }

    /// A withheld router ranks as the answer it was, not as the silence its
    /// missing address resembles.
    ///
    /// Ranked by whether an address is present, a measured silence would
    /// displace a spliced router whose address was withheld, and the path
    /// would claim nothing answered at a distance where a router did. The
    /// order `Host::merge` replays two records in decides which comes first.
    #[test]
    fn a_withheld_router_still_outranks_silence() {
        let spliced = Hop::withheld(3).as_inferred();

        let mut path = NetworkPath::new();
        path.record(spliced);
        path.record(Hop::silent(3));
        assert!(path.hops()[0].is_withheld(), "{path:?}");

        // Between two answers, provenance still decides.
        let mut measured = NetworkPath::new();
        measured.record(Hop::answered(3, ip(3), None).as_inferred());
        measured.record(Hop::withheld(3));
        assert!(measured.hops()[0].is_withheld());
        assert!(!measured.hops()[0].inferred());
    }

    /// Withholding takes what is about the router and leaves what is about the
    /// route: the distance, and whether this host's own trace measured it.
    #[test]
    fn withholding_a_router_keeps_its_place_and_its_provenance() {
        let mut path = NetworkPath::new();
        path.record(Hop::answered(1, ip(1), Some(Duration::from_millis(1))));
        path.record(Hop::answered(2, ip(2), Some(Duration::from_millis(2))).as_inferred());
        path.record(Hop::answered(3, ip(3), Some(Duration::from_millis(3))));

        assert!(path.withhold(|address| *address != ip(2)));

        let withheld = path.hops()[1];
        assert_eq!(withheld.distance(), 2);
        assert!(withheld.is_withheld());
        assert!(withheld.inferred(), "a spliced router stays marked as one");
        assert_eq!(withheld.address(), None);
        assert_eq!(withheld.rtt(), None);
        assert_eq!(path.at(1), Some(ip(1)), "a permitted router is untouched");
        assert_eq!(path.length(), Some(3));

        assert!(
            !path.withhold(|address| *address != ip(2)),
            "there is nothing left to withhold"
        );
    }

    /// An inferred hop carries no round-trip time, because the probe that
    /// produced one was sent to somewhere else.
    #[test]
    fn an_inferred_hop_reports_no_timing_of_its_own() {
        let inferred = Hop::answered(4, ip(4), Some(Duration::from_millis(9))).as_inferred();

        assert!(inferred.inferred());
        assert_eq!(inferred.address(), Some(ip(4)));
        assert_eq!(inferred.rtt(), None);
    }
}