taudit_core/
propagation.rs

1use crate::graph::{AuthorityGraph, EdgeId, NodeId, TrustZone};
2use serde::{Deserialize, Serialize};
3use std::collections::VecDeque;
4
5/// A path that authority took through the graph.
6/// The path is the product — it's what makes findings persuasive.
7#[derive(Debug, Clone, Serialize, Deserialize)]
8pub struct PropagationPath {
9    /// The authority origin (Secret or Identity).
10    pub source: NodeId,
11    /// Where authority ended up.
12    pub sink: NodeId,
13    /// The full edge path from source to sink.
14    pub edges: Vec<EdgeId>,
15    /// Did this path cross a trust zone boundary?
16    pub crossed_boundary: bool,
17    /// If crossed, from which zone to which zone.
18    #[serde(skip_serializing_if = "Option::is_none")]
19    pub boundary_crossing: Option<(TrustZone, TrustZone)>,
20}
21
22/// Default maximum BFS depth. Override via CLI --max-hops.
23pub const DEFAULT_MAX_HOPS: usize = 4;
24
25/// Walk the graph from every authority-bearing source node (Secret + Identity).
26/// Flag any path that reaches a node in a lower trust zone.
27///
28/// Propagation continues unless an explicit isolation boundary breaks it.
29/// Generic traversal with a configurable depth cap — no theory around hop count.
30pub fn propagation_analysis(graph: &AuthorityGraph, max_hops: usize) -> Vec<PropagationPath> {
31    let mut results = Vec::new();
32
33    for source_node in graph.authority_sources() {
34        // Find all steps that have access to this authority source.
35        // The edges point from step -> source (HasAccessTo), so we look at edges_to.
36        let accessor_steps: Vec<NodeId> = graph
37            .edges_to(source_node.id)
38            .filter(|e| e.kind == crate::graph::EdgeKind::HasAccessTo)
39            .map(|e| e.from)
40            .collect();
41
42        for start_step in accessor_steps {
43            // BFS from the step that holds this authority
44            let mut queue: VecDeque<(NodeId, Vec<EdgeId>, usize)> = VecDeque::new();
45            let mut visited = vec![false; graph.nodes.len()];
46
47            // Seed: the step that directly accesses the authority source
48            visited[start_step] = true;
49
50            // Add all outgoing edges from the start step
51            for edge in graph.edges_from(start_step) {
52                queue.push_back((edge.to, vec![edge.id], 1));
53            }
54
55            while let Some((current_id, path, depth)) = queue.pop_front() {
56                if depth > max_hops || visited[current_id] {
57                    continue;
58                }
59                visited[current_id] = true;
60
61                let current_node = match graph.node(current_id) {
62                    Some(n) => n,
63                    None => continue,
64                };
65
66                let source_zone = source_node.trust_zone;
67                let current_zone = current_node.trust_zone;
68                let crossed = current_zone.is_lower_than(&source_zone);
69
70                if crossed {
71                    results.push(PropagationPath {
72                        source: source_node.id,
73                        sink: current_id,
74                        edges: path.clone(),
75                        crossed_boundary: true,
76                        boundary_crossing: Some((source_zone, current_zone)),
77                    });
78                }
79
80                // Continue BFS through outgoing edges
81                for edge in graph.edges_from(current_id) {
82                    if !visited[edge.to] {
83                        let mut new_path = path.clone();
84                        new_path.push(edge.id);
85                        queue.push_back((edge.to, new_path, depth + 1));
86                    }
87                }
88            }
89        }
90    }
91
92    results
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98    use crate::graph::*;
99
100    fn make_source(file: &str) -> PipelineSource {
101        PipelineSource {
102            file: file.into(),
103            repo: None,
104            git_ref: None,
105        }
106    }
107
108    #[test]
109    fn detects_secret_propagation_across_trust_boundary() {
110        let mut g = AuthorityGraph::new(make_source("test.yml"));
111
112        // Secret in first-party zone
113        let secret = g.add_node(NodeKind::Secret, "AWS_KEY", TrustZone::FirstParty);
114        // First-party build step reads the secret
115        let build = g.add_node(NodeKind::Step, "build", TrustZone::FirstParty);
116        // Build produces an artifact
117        let artifact = g.add_node(NodeKind::Artifact, "dist.tar.gz", TrustZone::FirstParty);
118        // Third-party deploy step consumes the artifact
119        let deploy = g.add_node(NodeKind::Step, "deploy", TrustZone::ThirdParty);
120
121        g.add_edge(build, secret, EdgeKind::HasAccessTo);
122        g.add_edge(build, artifact, EdgeKind::Produces);
123        g.add_edge(artifact, deploy, EdgeKind::Consumes);
124
125        let paths = propagation_analysis(&g, DEFAULT_MAX_HOPS);
126
127        assert!(!paths.is_empty(), "should detect propagation");
128        assert!(paths
129            .iter()
130            .any(|p| p.source == secret && p.crossed_boundary));
131    }
132
133    #[test]
134    fn no_finding_when_same_trust_zone() {
135        let mut g = AuthorityGraph::new(make_source("test.yml"));
136
137        let secret = g.add_node(NodeKind::Secret, "TOKEN", TrustZone::FirstParty);
138        let step_a = g.add_node(NodeKind::Step, "lint", TrustZone::FirstParty);
139        let step_b = g.add_node(NodeKind::Step, "test", TrustZone::FirstParty);
140        let artifact = g.add_node(NodeKind::Artifact, "output", TrustZone::FirstParty);
141
142        g.add_edge(step_a, secret, EdgeKind::HasAccessTo);
143        g.add_edge(step_a, artifact, EdgeKind::Produces);
144        g.add_edge(artifact, step_b, EdgeKind::Consumes);
145
146        let paths = propagation_analysis(&g, DEFAULT_MAX_HOPS);
147
148        let boundary_crossings: Vec<_> = paths.iter().filter(|p| p.crossed_boundary).collect();
149        assert!(
150            boundary_crossings.is_empty(),
151            "no boundary crossing expected"
152        );
153    }
154
155    #[test]
156    fn respects_max_hops() {
157        let mut g = AuthorityGraph::new(make_source("test.yml"));
158
159        let secret = g.add_node(NodeKind::Secret, "KEY", TrustZone::FirstParty);
160        let s1 = g.add_node(NodeKind::Step, "s1", TrustZone::FirstParty);
161        let a1 = g.add_node(NodeKind::Artifact, "a1", TrustZone::FirstParty);
162        let s2 = g.add_node(NodeKind::Step, "s2", TrustZone::FirstParty);
163        let a2 = g.add_node(NodeKind::Artifact, "a2", TrustZone::FirstParty);
164        let s3 = g.add_node(NodeKind::Step, "s3", TrustZone::Untrusted);
165
166        g.add_edge(s1, secret, EdgeKind::HasAccessTo);
167        g.add_edge(s1, a1, EdgeKind::Produces);
168        g.add_edge(a1, s2, EdgeKind::Consumes);
169        g.add_edge(s2, a2, EdgeKind::Produces);
170        g.add_edge(a2, s3, EdgeKind::Consumes);
171
172        // With max_hops=2, should NOT reach s3 (which is 4 edges away)
173        let paths_short = propagation_analysis(&g, 2);
174        let boundary_short: Vec<_> = paths_short.iter().filter(|p| p.crossed_boundary).collect();
175        assert!(
176            boundary_short.is_empty(),
177            "should not reach untrusted at depth 2"
178        );
179
180        // With max_hops=5, should reach s3
181        let paths_long = propagation_analysis(&g, 5);
182        let boundary_long: Vec<_> = paths_long.iter().filter(|p| p.crossed_boundary).collect();
183        assert!(
184            !boundary_long.is_empty(),
185            "should reach untrusted at depth 5"
186        );
187    }
188
189    #[test]
190    fn identity_is_authority_source() {
191        let mut g = AuthorityGraph::new(make_source("test.yml"));
192
193        let identity = g.add_node(NodeKind::Identity, "GITHUB_TOKEN", TrustZone::FirstParty);
194        let step = g.add_node(NodeKind::Step, "publish", TrustZone::FirstParty);
195        let action = g.add_node(
196            NodeKind::Image,
197            "third-party/deploy@main",
198            TrustZone::Untrusted,
199        );
200
201        g.add_edge(step, identity, EdgeKind::HasAccessTo);
202        g.add_edge(step, action, EdgeKind::UsesImage);
203
204        let paths = propagation_analysis(&g, DEFAULT_MAX_HOPS);
205        assert!(paths
206            .iter()
207            .any(|p| p.source == identity && p.crossed_boundary));
208    }
209}
taudit_core/propagation.rs

taudit_core/
propagation.rs
