pq_map/render/
graph.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use chrono::{DateTime, Utc};
4
5use crate::model::{
6    ChainEntry, DomainState, Host, MatchKind, ProbeStatus, cert_key_name, cert_signature_from_db,
7};
8
9use serde::Serialize;
10
11#[derive(Debug, Serialize)]
12struct Node {
13    id: String,
14    label: String,
15    #[serde(rename = "type")]
16    node_type: &'static str,
17    #[serde(skip_serializing_if = "Option::is_none")]
18    group: Option<&'static str>,
19    #[serde(skip_serializing_if = "Option::is_none")]
20    metadata: Option<CertMetadata>,
21}
22
23#[derive(Debug, Serialize)]
24struct CertMetadata {
25    ca_role: &'static str,
26    #[serde(skip_serializing_if = "Option::is_none")]
27    sans: Option<Vec<String>>,
28    #[serde(skip_serializing_if = "Option::is_none")]
29    not_before: Option<DateTime<Utc>>,
30    #[serde(skip_serializing_if = "Option::is_none")]
31    not_after: Option<DateTime<Utc>>,
32}
33
34#[derive(Debug, Serialize)]
35struct Link {
36    source: String,
37    target: String,
38    label: &'static str,
39}
40
41#[derive(Debug, Serialize)]
42struct Graph {
43    nodes: Vec<Node>,
44    links: Vec<Link>,
45}
46
47struct CertNode {
48    id: String,
49    label: String,
50    metadata: Option<CertMetadata>,
51    cert_signature: Option<String>,
52    cert_key: Option<String>,
53    issuer: Option<String>,
54    chain: Vec<ChainEntry>,
55}
56
57struct CertFacts<'a> {
58    common_name: Option<String>,
59    serial: &'a str,
60    ct_id: Option<u64>,
61    cert_signature: Option<String>,
62    key_alg: Option<&'a str>,
63    key_size: Option<i64>,
64    curve: Option<&'a str>,
65    issuer: Option<String>,
66    identities: Vec<String>,
67    not_before: Option<DateTime<Utc>>,
68    not_after: Option<DateTime<Utc>>,
69    chain: Vec<ChainEntry>,
70}
71
72fn cert_node(f: CertFacts<'_>) -> CertNode {
73    let cn = f.common_name.unwrap_or_else(|| f.serial.to_string());
74    let id = match f.ct_id {
75        Some(id) => format!("cert:{cn}:{id}"),
76        None => format!("cert:{cn}"),
77    };
78    let sans: Vec<String> = f.identities.iter().filter(|i| **i != cn).cloned().collect();
79    let label = match sans.len() {
80        0 => cn.clone(),
81        1 => format!("{cn} +1 SAN"),
82        n => format!("{cn} +{n} SANs"),
83    };
84    let metadata = CertMetadata {
85        ca_role: "leaf",
86        sans: (!sans.is_empty()).then_some(sans),
87        not_before: f.not_before,
88        not_after: f.not_after,
89    };
90    CertNode {
91        id,
92        label,
93        metadata: Some(metadata),
94        cert_signature: f.cert_signature,
95        cert_key: cert_key_name(f.key_alg, f.key_size, f.curve),
96        issuer: f.issuer,
97        chain: f.chain,
98    }
99}
100
101fn is_self_issued(entry: &ChainEntry) -> bool {
102    match (entry.ski.as_deref(), entry.aki.as_deref()) {
103        (Some(ski), Some(aki)) if !ski.is_empty() && ski == aki => true,
104        _ => match (&entry.common_name, &entry.issuer_ca_name) {
105            (Some(cn), Some(issuer)) => ca_cn(issuer) == *cn,
106            _ => false,
107        },
108    }
109}
110
111fn ca_slug(cn: &str) -> String {
112    let mut slug = String::new();
113    let mut prev_dash = true;
114    for c in cn.chars() {
115        if c.is_ascii_alphanumeric() {
116            slug.push(c.to_ascii_lowercase());
117            prev_dash = false;
118        } else if !prev_dash {
119            slug.push('-');
120            prev_dash = true;
121        }
122    }
123    while slug.ends_with('-') {
124        slug.pop();
125    }
126    slug
127}
128
129fn ca_id(dn: &str) -> (String, String) {
130    let cn = ca_cn(dn);
131    (format!("ca:{}", ca_slug(&cn)), cn)
132}
133
134fn ca_cn(dn: &str) -> String {
135    for part in split_unescaped_commas(dn) {
136        let part = part.trim();
137        if let Some(cn) = part.strip_prefix("CN=") {
138            return cn.trim().to_string();
139        }
140    }
141    dn.to_string()
142}
143
144fn split_unescaped_commas(s: &str) -> Vec<&str> {
145    let mut out = Vec::new();
146    let mut start = 0;
147    for (i, c) in s.char_indices() {
148        if c == ',' && !s[..i].ends_with('\\') {
149            out.push(&s[start..i]);
150            start = i + 1;
151        }
152    }
153    out.push(&s[start..]);
154    out
155}
156
157/// The certificate to attribute to a host: the leaf it served live (resolved
158/// through the CT map for CT ids and merged facts), or the covering CT
159/// certificate with the latest expiry.
160fn host_cert(state: &DomainState, host: &Host) -> Option<(CertNode, &'static str)> {
161    if let Some(served) = host.endpoint.as_ref().and_then(|e| e.served.as_ref()) {
162        let facts = match state.certs.get(&served.serial) {
163            Some(ct) => CertFacts {
164                common_name: ct.common_name.clone(),
165                serial: &served.serial,
166                ct_id: ct.ct_ids.first().copied(),
167                cert_signature: ct.cert_signature.clone(),
168                key_alg: ct.key_algorithm.as_deref(),
169                key_size: ct.key_size,
170                curve: None,
171                issuer: ct.issuer.clone(),
172                identities: ct.identities.clone(),
173                not_before: ct.not_before,
174                not_after: ct.not_after,
175                chain: ct.chain.clone(),
176            },
177            None => CertFacts {
178                common_name: served.common_name.clone(),
179                serial: &served.serial,
180                ct_id: None,
181                cert_signature: served.cert_signature.clone(),
182                key_alg: served.pubkey_alg.as_deref(),
183                key_size: None,
184                curve: served.pubkey_curve.as_deref(),
185                issuer: served.issuer.clone(),
186                identities: served.identities.clone(),
187                not_before: served.not_before,
188                not_after: served.not_after,
189                chain: Vec::new(),
190            },
191        };
192        return Some((cert_node(facts), "presents_certificate"));
193    }
194    let exact: Vec<_> = host
195        .ct_refs
196        .iter()
197        .filter(|r| r.kind == MatchKind::Exact)
198        .collect();
199    let pool: Vec<_> = if exact.is_empty() {
200        host.ct_refs.iter().collect()
201    } else {
202        exact
203    };
204    let covering = pool
205        .iter()
206        .filter_map(|r| state.certs.get(&r.serial))
207        .max_by_key(|c| c.not_after)?;
208    Some((
209        cert_node(CertFacts {
210            common_name: covering.common_name.clone(),
211            serial: &covering.serial,
212            ct_id: covering.ct_ids.first().copied(),
213            cert_signature: covering.cert_signature.clone(),
214            key_alg: covering.key_algorithm.as_deref(),
215            key_size: covering.key_size,
216            curve: None,
217            issuer: covering.issuer.clone(),
218            identities: covering.identities.clone(),
219            not_before: covering.not_before,
220            not_after: covering.not_after,
221            chain: covering.chain.clone(),
222        }),
223        "certificate_for",
224    ))
225}
226
227pub fn graph(state: &DomainState) -> String {
228    let mut nodes: BTreeMap<String, Node> = BTreeMap::new();
229    let mut links: BTreeSet<(String, String, &'static str)> = BTreeSet::new();
230
231    let node = |nodes: &mut BTreeMap<String, Node>,
232                id: &str,
233                label: String,
234                node_type: &'static str,
235                group: &'static str| {
236        nodes.entry(id.to_string()).or_insert_with(|| Node {
237            id: id.to_string(),
238            label,
239            node_type,
240            group: (group != node_type).then_some(group),
241            metadata: None,
242        });
243    };
244
245    for host in state.hosts.values() {
246        let exposed = matches!(
247            host.endpoint.as_ref().map(|e| &e.status),
248            Some(ProbeStatus::Ok)
249        );
250        let host_id = format!("host:{}", host.name);
251        nodes.entry(host_id.clone()).or_insert_with(|| Node {
252            id: host_id.clone(),
253            label: host.name.clone(),
254            node_type: "host",
255            group: None,
256            metadata: None,
257        });
258
259        if exposed {
260            node(
261                &mut nodes,
262                "service:tcp/443",
263                "TCP/443".to_string(),
264                "service",
265                "tcp_service",
266            );
267            links.insert((host_id.clone(), "service:tcp/443".to_string(), "exposes"));
268        }
269        for scan in &host.ports {
270            if scan.state != crate::model::ScanState::Open {
271                continue;
272            }
273            let id = format!("service:tcp/{}", scan.port);
274            let label = format!("{}:{}", crate::model::port_service(scan.port), scan.port);
275            node(&mut nodes, &id, label, "service", "tcp_service");
276            links.insert((host_id.clone(), id, "exposes"));
277        }
278
279        if let Some(negotiated) = host.endpoint.as_ref().and_then(|e| e.negotiated.as_ref()) {
280            if let Some(kx) = &negotiated.kx_group {
281                let id = format!("kx:{kx}");
282                node(&mut nodes, &id, kx.clone(), "crypto", "key_exchange");
283                links.insert((host_id.clone(), id, "negotiated_kx"));
284            }
285            if let Some(cipher) = &negotiated.cipher {
286                if let Some(sym) = crate::model::symmetric_name(cipher) {
287                    let id = format!("cipher:{sym}");
288                    node(&mut nodes, &id, sym.clone(), "crypto", "symmetric");
289                    links.insert((host_id.clone(), id, "symmetric_cipher"));
290                }
291            }
292        }
293
294        if let Some((cert, cert_edge)) = host_cert(state, host) {
295            node(
296                &mut nodes,
297                &cert.id,
298                cert.label.clone(),
299                "pki",
300                "certificate",
301            );
302            if let Some(metadata) = cert.metadata {
303                if let Some(existing) = nodes.get_mut(&cert.id) {
304                    existing.metadata = Some(metadata);
305                }
306            }
307            links.insert((host_id.clone(), cert.id.clone(), cert_edge));
308
309            if let Some(sig) = cert.cert_signature {
310                let id = format!("certsig:{sig}");
311                node(
312                    &mut nodes,
313                    &id,
314                    sig.clone(),
315                    "crypto",
316                    "certificate_signature",
317                );
318                links.insert((cert.id.clone(), id, "cert_signature"));
319            }
320            if let Some(key) = cert.cert_key {
321                let id = format!("certkey:{key}");
322                node(&mut nodes, &id, key.clone(), "crypto", "certificate_key");
323                links.insert((cert.id.clone(), id, "cert_key"));
324            }
325            let mut prev_ca: Option<String> = cert
326                .issuer
327                .as_deref()
328                .map(|dn| format!("ca:{}", ca_slug(&ca_cn(dn))));
329            if let Some(issuer) = cert.issuer {
330                let (ca_id, ca_label) = ca_id(&issuer);
331                node(&mut nodes, &ca_id, ca_label, "pki", "issuer");
332                links.insert((cert.id.clone(), ca_id, "issued_by"));
333            }
334            for entry in cert.chain.iter().filter(|e| e.depth >= 1) {
335                let Some(cn) = entry.common_name.as_deref().filter(|c| !c.is_empty()) else {
336                    continue;
337                };
338                let ca_id = format!("ca:{}", ca_slug(cn));
339                node(&mut nodes, &ca_id, cn.to_string(), "pki", "issuer");
340                if let Some(existing) = nodes.get_mut(&ca_id) {
341                    existing.metadata = Some(CertMetadata {
342                        ca_role: if is_self_issued(entry) {
343                            "root"
344                        } else {
345                            "intermediate"
346                        },
347                        sans: None,
348                        not_before: entry.not_before,
349                        not_after: entry.not_after,
350                    });
351                }
352                if let Some(sig) = cert_signature_from_db(
353                    entry.key_algorithm.as_deref(),
354                    entry.key_size,
355                    entry.signature_key_algorithm.as_deref(),
356                    entry.signature_hash_algorithm.as_deref(),
357                ) {
358                    let id = format!("certsig:{sig}");
359                    node(
360                        &mut nodes,
361                        &id,
362                        sig.clone(),
363                        "crypto",
364                        "certificate_signature",
365                    );
366                    links.insert((ca_id.clone(), id, "cert_signature"));
367                }
368                if let Some(key) =
369                    cert_key_name(entry.key_algorithm.as_deref(), entry.key_size, None)
370                {
371                    let id = format!("certkey:{key}");
372                    node(&mut nodes, &id, key.clone(), "crypto", "certificate_key");
373                    links.insert((ca_id.clone(), id, "cert_key"));
374                }
375                if let Some(prev) = prev_ca {
376                    if prev != ca_id {
377                        links.insert((prev, ca_id.clone(), "issued_by"));
378                    }
379                }
380                prev_ca = Some(ca_id);
381            }
382        }
383    }
384
385    let graph = Graph {
386        nodes: nodes.into_values().collect(),
387        links: links
388            .into_iter()
389            .map(|(source, target, label)| Link {
390                source,
391                target,
392                label,
393            })
394            .collect(),
395    };
396    serde_json::to_string_pretty(&graph)
397        .unwrap_or_else(|_| "{\"nodes\":[],\"links\":[]}".to_string())
398}
399
400#[cfg(test)]
401mod tests {
402    use super::*;
403    use crate::model::fixture;
404
405    type Edge = (String, String, String);
406
407    fn edges(json: &str) -> Vec<Edge> {
408        let v: serde_json::Value = serde_json::from_str(json).unwrap();
409        v["links"]
410            .as_array()
411            .unwrap()
412            .iter()
413            .map(|l| {
414                (
415                    l["source"].as_str().unwrap().to_string(),
416                    l["label"].as_str().unwrap().to_string(),
417                    l["target"].as_str().unwrap().to_string(),
418                )
419            })
420            .collect()
421    }
422
423    #[test]
424    fn exposed_host_has_full_edge_set() {
425        let state = fixture();
426        let json = graph(&state);
427        let e = edges(&json);
428        assert!(e.contains(&(
429            "host:www.example.com".to_string(),
430            "negotiated_kx".to_string(),
431            "kx:X25519MLKEM768".to_string()
432        )));
433        assert!(e.contains(&(
434            "host:www.example.com".to_string(),
435            "symmetric_cipher".to_string(),
436            "cipher:AES256-GCM".to_string()
437        )));
438        assert!(e.contains(&(
439            "host:www.example.com".to_string(),
440            "exposes".to_string(),
441            "service:tcp/443".to_string()
442        )));
443        assert!(e.contains(&(
444            "host:www.example.com".to_string(),
445            "presents_certificate".to_string(),
446            "cert:www.example.com:9612296601".to_string()
447        )));
448        assert!(e.contains(&(
449            "cert:www.example.com:9612296601".to_string(),
450            "cert_signature".to_string(),
451            "certsig:RSA-SHA256".to_string()
452        )));
453        assert!(e.contains(&(
454            "cert:www.example.com:9612296601".to_string(),
455            "cert_key".to_string(),
456            "certkey:RSA-2048".to_string()
457        )));
458        assert!(e.contains(&(
459            "cert:www.example.com:9612296601".to_string(),
460            "issued_by".to_string(),
461            "ca:digicert-tls-rsa-sha256-2020-ca-1".to_string()
462        )));
463        assert!(e.contains(&(
464            "ca:digicert-tls-rsa-sha256-2020-ca-1".to_string(),
465            "issued_by".to_string(),
466            "ca:digicert-global-root-ca".to_string()
467        )));
468        assert!(e.contains(&(
469            "ca:digicert-tls-rsa-sha256-2020-ca-1".to_string(),
470            "cert_signature".to_string(),
471            "certsig:RSA-SHA256".to_string()
472        )));
473        assert!(e.contains(&(
474            "ca:digicert-tls-rsa-sha256-2020-ca-1".to_string(),
475            "cert_key".to_string(),
476            "certkey:RSA-2048".to_string()
477        )));
478        assert!(e.contains(&(
479            "ca:digicert-global-root-ca".to_string(),
480            "cert_signature".to_string(),
481            "certsig:RSA-SHA256".to_string()
482        )));
483        assert!(!e.iter().any(|(_, l, _)| l == "uses"));
484    }
485
486    #[test]
487    fn unprobed_hosts_route_through_their_cert() {
488        let state = fixture();
489        let json = graph(&state);
490        let e = edges(&json);
491        assert!(e.contains(&(
492            "host:vpn.example.com".to_string(),
493            "certificate_for".to_string(),
494            "cert:*.example.com:9612297416".to_string()
495        )));
496        assert!(e.contains(&(
497            "cert:*.example.com:9612297416".to_string(),
498            "cert_signature".to_string(),
499            "certsig:ECDSA-P256".to_string()
500        )));
501        assert!(e.contains(&(
502            "cert:*.example.com:9612297416".to_string(),
503            "cert_key".to_string(),
504            "certkey:EC-256".to_string()
505        )));
506        assert!(e.contains(&(
507            "host:old.example.com".to_string(),
508            "certificate_for".to_string(),
509            "cert:*.example.com:9612297416".to_string()
510        )));
511        assert!(
512            !e.iter()
513                .any(|(s, l, _)| s == "host:vpn.example.com" && *l != "certificate_for")
514        );
515    }
516
517    #[test]
518    fn exact_cert_match_outranks_the_wildcard() {
519        let state = fixture();
520        let e = edges(&graph(&state));
521        assert!(e.contains(&(
522            "host:eas.example.com".to_string(),
523            "certificate_for".to_string(),
524            "cert:eas.example.com:9612300001".to_string()
525        )));
526        assert!(!e.contains(&(
527            "host:eas.example.com".to_string(),
528            "certificate_for".to_string(),
529            "cert:*.example.com:9612297416".to_string()
530        )));
531    }
532
533    #[test]
534    fn fact_nodes_are_deduplicated() {
535        let state = fixture();
536        let json = graph(&state);
537        let v: serde_json::Value = serde_json::from_str(&json).unwrap();
538        let ids: Vec<&str> = v["nodes"]
539            .as_array()
540            .unwrap()
541            .iter()
542            .map(|n| n["id"].as_str().unwrap())
543            .collect();
544        let mut sorted = ids.clone();
545        sorted.sort_unstable();
546        sorted.dedup();
547        assert_eq!(ids.len(), sorted.len(), "duplicate node ids in {ids:?}");
548        assert_eq!(ids.iter().filter(|i| **i == "service:tcp/443").count(), 1);
549        assert_eq!(
550            ids.iter()
551                .filter(|i| **i == "cert:www.example.com:9612296601")
552                .count(),
553            1
554        );
555        assert_eq!(
556            ids.iter()
557                .filter(|i| **i == "ca:digicert-tls-rsa-sha256-2020-ca-1")
558                .count(),
559            1
560        );
561    }
562
563    #[test]
564    fn nodes_carry_semantic_metadata() {
565        let state = fixture();
566        let json = graph(&state);
567        let v: serde_json::Value = serde_json::from_str(&json).unwrap();
568        let find = |id: &str| {
569            v["nodes"]
570                .as_array()
571                .unwrap()
572                .iter()
573                .find(|n| n["id"] == id)
574                .unwrap()
575                .clone()
576        };
577        let host = find("host:www.example.com");
578        assert_eq!(host["type"], "host");
579        assert!(host.get("group").is_none());
580        assert!(host.get("axis").is_none());
581        assert_eq!(host["label"], "www.example.com");
582        let kx = find("kx:X25519MLKEM768");
583        assert_eq!(kx["type"], "crypto");
584        assert_eq!(kx["group"], "key_exchange");
585        let cipher = find("cipher:AES256-GCM");
586        assert_eq!(cipher["type"], "crypto");
587        assert_eq!(cipher["group"], "symmetric");
588        let svc = find("service:tcp/465");
589        assert_eq!(svc["type"], "service");
590        assert_eq!(svc["group"], "tcp_service");
591        assert_eq!(svc["label"], "SMTPS:465");
592        let cert = find("cert:www.example.com:9612296601");
593        assert_eq!(cert["type"], "pki");
594        assert_eq!(cert["group"], "certificate");
595        assert_eq!(cert["label"], "www.example.com +1 SAN");
596        assert_eq!(cert["metadata"]["ca_role"], "leaf");
597        assert_eq!(cert["metadata"]["sans"], serde_json::json!(["example.com"]));
598        assert!(cert["metadata"]["not_before"].is_string());
599        assert!(cert["metadata"]["not_after"].is_string());
600        let inter = find("ca:digicert-tls-rsa-sha256-2020-ca-1");
601        assert_eq!(inter["metadata"]["ca_role"], "intermediate");
602        assert!(inter["metadata"]["not_before"].is_string());
603        let root = find("ca:digicert-global-root-ca");
604        assert_eq!(root["metadata"]["ca_role"], "root");
605        let sig = find("certsig:RSA-SHA256");
606        assert_eq!(sig["type"], "crypto");
607        assert_eq!(sig["group"], "certificate_signature");
608        let key = find("certkey:RSA-2048");
609        assert_eq!(key["type"], "crypto");
610        assert_eq!(key["group"], "certificate_key");
611        assert_eq!(key["label"], "RSA-2048");
612        let ca = find("ca:digicert-tls-rsa-sha256-2020-ca-1");
613        assert_eq!(ca["type"], "pki");
614        assert_eq!(ca["group"], "issuer");
615        assert_eq!(ca["label"], "DigiCert TLS RSA SHA256 2020 CA-1");
616        let service = find("service:tcp/443");
617        assert_eq!(service["type"], "service");
618        assert_eq!(service["group"], "tcp_service");
619        assert_eq!(service["label"], "TCP/443");
620    }
621
622    #[test]
623    fn unprobed_hosts_route_through_their_cert_semantics() {
624        let state = fixture();
625        let json = graph(&state);
626        let v: serde_json::Value = serde_json::from_str(&json).unwrap();
627        let vpn = v["nodes"]
628            .as_array()
629            .unwrap()
630            .iter()
631            .find(|n| n["id"] == "host:vpn.example.com")
632            .unwrap()
633            .clone();
634        assert_eq!(vpn["type"], "host");
635        assert!(vpn.get("group").is_none());
636    }
637}
pq_map/render/graph.rs

pq_map/render/
graph.rs
