ENOSUCHBLOG
Programming, philosophy, pedaling.
Aug 14, 2025 Tags: devblog, programming, rust, zizmor
I recently solved an interesting problem inside zizmor with a type of state machine/automaton I hadn’t used before: a finite state transducer (FST).
This is just a quick write-up of the problem and how I solved it. It doesn’t go particularly deep into the data structures themselves. For more information on FSTs themselves, I strongly recommend burntsushi’s article on transducers (which is what actually led me to his fst crate).
TL;DR: I used the fst crate to build a finite state transducer that maps GitHub Actions context patterns to their logical “capability” in the context of a potential template injection vulnerability. This ended up being an order of magnitude smaller in terms of representation (~14.5KB instead of ~240 KB) and faster and more memory efficient than my naïve initial approaches (tables and prefix trie walks). It also enabled me to fully precompute the FST at compile time, eliminating the startup cost of priming a trie- or table-based map.
Background
zizmor is a static analysis tool for GitHub Actions.
One of the categories of weaknesses it can find is template injections, wherein the CI author uses a GitHub Actions expression in a shell or similar context without realizing that the expression can escape any shell-level quoting intended to “defuse” it.
Here’s an example, derived from a pattern that gets exploited over and over again:
... continue reading