Fun with Finite State Transducers

Summary

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: 1 2 3 - name: "Print the current ref" run: | echo "The current ref is: ${{ github.ref }}" If this step is part of a workflow that grants elevated privileges to third parties (like pull_request_target), and attacker can contrive a git ref that escapes the shell quoting and runs arbitrary code. For example, the following ref: 1 innocent";cat${IFS}/etc/passwd;true${IFS}" …would expand as: 1 echo "The current ref is innocent";cat /etc/passwd;true "" Fortunately, zizmor detects these: 1 2 3 4 5 6 7 8 9 10 11 12 zizmor hackme....