Fun with Finite State Transducers
10 days ago
- #Static Analysis
- #GitHub Actions
- #Finite State Transducer
- The author used a finite state transducer (FST) to solve a problem in zizmor, a static analysis tool for GitHub Actions.
- The problem involved detecting template injection vulnerabilities in GitHub Actions workflows, where expressions could escape shell-level quoting.
- The solution involved mapping GitHub Actions context patterns to their 'capability' (arbitrary, structured, fixed) to assess injection risk.
- A helper script, webhooks-to-contexts.py, processed GitHub's OpenAPI schema to generate a CSV of context capabilities.
- The FST approach was chosen over a hash table or trie for its compact representation (~14.5KB vs ~240KB) and efficiency.
- The FST was precomputed at compile time, eliminating startup costs associated with other methods.
- The solution was included in zizmor 1.9.0, improving the tool's template-injection audit capabilities.