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            commit_sha: None,
106        }
107    }
108
109    #[test]
110    fn detects_secret_propagation_across_trust_boundary() {
111        let mut g = AuthorityGraph::new(make_source("test.yml"));
112
113        // Secret in first-party zone
114        let secret = g.add_node(NodeKind::Secret, "AWS_KEY", TrustZone::FirstParty);
115        // First-party build step reads the secret
116        let build = g.add_node(NodeKind::Step, "build", TrustZone::FirstParty);
117        // Build produces an artifact
118        let artifact = g.add_node(NodeKind::Artifact, "dist.tar.gz", TrustZone::FirstParty);
119        // Third-party deploy step consumes the artifact
120        let deploy = g.add_node(NodeKind::Step, "deploy", TrustZone::ThirdParty);
121
122        g.add_edge(build, secret, EdgeKind::HasAccessTo);
123        g.add_edge(build, artifact, EdgeKind::Produces);
124        g.add_edge(artifact, deploy, EdgeKind::Consumes);
125
126        let paths = propagation_analysis(&g, DEFAULT_MAX_HOPS);
127
128        assert!(!paths.is_empty(), "should detect propagation");
129        assert!(paths
130            .iter()
131            .any(|p| p.source == secret && p.crossed_boundary));
132    }
133
134    #[test]
135    fn no_finding_when_same_trust_zone() {
136        let mut g = AuthorityGraph::new(make_source("test.yml"));
137
138        let secret = g.add_node(NodeKind::Secret, "TOKEN", TrustZone::FirstParty);
139        let step_a = g.add_node(NodeKind::Step, "lint", TrustZone::FirstParty);
140        let step_b = g.add_node(NodeKind::Step, "test", TrustZone::FirstParty);
141        let artifact = g.add_node(NodeKind::Artifact, "output", TrustZone::FirstParty);
142
143        g.add_edge(step_a, secret, EdgeKind::HasAccessTo);
144        g.add_edge(step_a, artifact, EdgeKind::Produces);
145        g.add_edge(artifact, step_b, EdgeKind::Consumes);
146
147        let paths = propagation_analysis(&g, DEFAULT_MAX_HOPS);
148
149        let boundary_crossings: Vec<_> = paths.iter().filter(|p| p.crossed_boundary).collect();
150        assert!(
151            boundary_crossings.is_empty(),
152            "no boundary crossing expected"
153        );
154    }
155
156    #[test]
157    fn respects_max_hops() {
158        let mut g = AuthorityGraph::new(make_source("test.yml"));
159
160        let secret = g.add_node(NodeKind::Secret, "KEY", TrustZone::FirstParty);
161        let s1 = g.add_node(NodeKind::Step, "s1", TrustZone::FirstParty);
162        let a1 = g.add_node(NodeKind::Artifact, "a1", TrustZone::FirstParty);
163        let s2 = g.add_node(NodeKind::Step, "s2", TrustZone::FirstParty);
164        let a2 = g.add_node(NodeKind::Artifact, "a2", TrustZone::FirstParty);
165        let s3 = g.add_node(NodeKind::Step, "s3", TrustZone::Untrusted);
166
167        g.add_edge(s1, secret, EdgeKind::HasAccessTo);
168        g.add_edge(s1, a1, EdgeKind::Produces);
169        g.add_edge(a1, s2, EdgeKind::Consumes);
170        g.add_edge(s2, a2, EdgeKind::Produces);
171        g.add_edge(a2, s3, EdgeKind::Consumes);
172
173        // With max_hops=2, should NOT reach s3 (which is 4 edges away)
174        let paths_short = propagation_analysis(&g, 2);
175        let boundary_short: Vec<_> = paths_short.iter().filter(|p| p.crossed_boundary).collect();
176        assert!(
177            boundary_short.is_empty(),
178            "should not reach untrusted at depth 2"
179        );
180
181        // With max_hops=5, should reach s3
182        let paths_long = propagation_analysis(&g, 5);
183        let boundary_long: Vec<_> = paths_long.iter().filter(|p| p.crossed_boundary).collect();
184        assert!(
185            !boundary_long.is_empty(),
186            "should reach untrusted at depth 5"
187        );
188    }
189
190    #[test]
191    fn identity_is_authority_source() {
192        let mut g = AuthorityGraph::new(make_source("test.yml"));
193
194        let identity = g.add_node(NodeKind::Identity, "GITHUB_TOKEN", TrustZone::FirstParty);
195        let step = g.add_node(NodeKind::Step, "publish", TrustZone::FirstParty);
196        let action = g.add_node(
197            NodeKind::Image,
198            "third-party/deploy@main",
199            TrustZone::Untrusted,
200        );
201
202        g.add_edge(step, identity, EdgeKind::HasAccessTo);
203        g.add_edge(step, action, EdgeKind::UsesImage);
204
205        let paths = propagation_analysis(&g, DEFAULT_MAX_HOPS);
206        assert!(paths
207            .iter()
208            .any(|p| p.source == identity && p.crossed_boundary));
209    }
210}
taudit_core/propagation.rs

taudit_core/
propagation.rs
