“Abstractions for Program Analysis” by Kyle Martin, explores how different abstractions simplify the process of analyzing software to find bugs, understand malware, or verify code behavior.
Here are the key takeaways from the talk:
- Redefining “Program”: Martin suggests viewing a program not just as a list of instructions, but as a set of states and the transformations that move and manipulate data between them. This perspective is more useful for automated analysis and fuzzing.
- The “Standard Model” of Analysis: He introduces a foundational framework for querying code based on four concepts: analyzing data flow forwards or backwards, and asking what may happen versus what must happen. Combinations of these queries can identify common vulnerabilities like uninitialized variables, null pointer dereferences, and use-after-free bugs.
- The Importance of Semantics and Types: While emulators focus on the mechanical execution of bits (execution characteristics), analysts need to understand the meaning or intent of the code (semantics). Types are the ultimate abstraction for this, as they define the structure of data and the rules for how it can be manipulated.
- Intermediate Languages (ILs): Because languages like C and assembly lack strict semantic context, analysts use ILs to translate code into a more structured, rule-based format. There are many flavors of ILs, each with different trade-offs regarding verbosity, ease of parsing, and the amount of type information they retain.
- Normal Forms: These are established rules for rewriting code to make specific questions easier to answer.
- A-Normal Form (ANF): Simplifies complex expressions to ensure evaluation order is explicit.
- Single Static Assignment (SSA): A crucial abstraction where every variable is defined only once. It uses a
ΦΦ(Phi) function to merge different possible states of a variable after a branch, making data flow tracking straightforward and enabling parallelizable analysis. - Single Static Information (SSI): While SSA handles merging paths, SSI improves upon it by using a
σσ(Sigma) function to split variable uses at branches. This allows analysts to track more precise constraints on a variable’s value along specific execution paths, which is necessary for analyzing loops and complex conditionals.
- Conclusion: Martin advises the audience to stop writing custom parsers and compilers. Instead, analysts should leverage existing tools and choose the specific abstraction (or translate between several) that best fits the problem they are trying to solve, rather than seeking a single, universal IL.