Automatic Exploit Generation: First of its Kind
Note that I don’t claim to be an expert in this topic at all. This is just a review based off of what I have read. I would appreciate any constructive criticism.
Automatic Exploit Generation, is as it sounds, an automatic way of generating security exploits for vulnerabilities in a program. This is known as the AEG challenge. This paper details the first end-to-end system for fully automatic exploit generation. The CMU team first shows how exploit generation for control flow hijack attacks can be modeled as a formal verification problem, then propose preconditioned symbolic execution (a novel technique for targeting symbolic execution), and finally present a general approach for generating working exploits. Also, here is a nice demo.
Before I describe how the system works, I want to go over some key terms that are important for understanding the paper.
- End to end system: As it sounds, an end-to-end system is a system that will do everything from analyzing source code to generating the input to exploit the system. AEG analyzes source code, generates symbolic execution formulas, solves them, performs binary analysis, and generates some specific exploit you want to perform.
- Binary analysis: Essentially threat assessment and vulnerability testing at the binary level. See here for more info.
- Control flow Hijack: Control flow exploits allow an attacker to execute arbitrary code (so anything) on a computer.
- Preconditioned symbolic execution: A novel technique which targets paths that are more likely to be exploitable. E.g. Explore only paths with the maximum input length, or paths related to HTTP GET requests. Note that most paths in this paper deal with memory issues
- Symbolic execution: A formal verification technique that explores program paths and checks if each path is exploitable
- Shell: User interface for access to computing system’s services.
How the AEG works:
TL;DR: AEG finds bugs, determine whether the bug is exploitable, if so produce a working control flow hijack exploit string. The string can then be directly fed into the vulnerable application to get a shell.
I want to talk a little bit about the background first:
Background & Previous Tries:
Novelty #0: Here is a nice quote from the paper:
Current state-of-the-art in control flow exploit generation is for a human to think very hard about whether a bug can be exploited. Until now, automated exploit generation where bugs are automatically found and exploits are generated has not been shown practical against real programs.
This paper claims to generate control flow hijack sequences automatically
- Source Code analysis: Source code analysis alone is insufficient to report whether a potential bug is exploitable because errors are found with respect to source code level abstractions: Source code analysis is like combing through the program for syntactical errors but we there is low chances of these errors. The ones we are looking to exploit are semantic ones, the ones that occur due to errors in logic or flaws in the abstract level of the code.
- The alternative is considering binary code analysis (looking at exactly what the code does every step of the way, where we can find some mistake in logic flow), runtime-level details, stack frames, memory address, etc. However this is unscalable.
Novelty #1 : Combine source-code level analysis and binary analysis
This is a pretty novel concept because it combines the use of source code analysis, which will find concrete bugs that will result in faulty execution with some sort of semantical meaning/logic through the binary analysis. Note that both methods previously existed, but the thought of combing them itself is novel. Furthermore, the code will work for a given system, not just a specific chunk of code.
- Now that we have some exploitable code, we need to find exploitable paths amongst an infinite number of paths that the code can take. Programs can have loops, which means that they potentially have an infinite number of paths.
- Here is where preconditioned symbolic execution comes into play. Preconditioned symbolic execution is similar to forward symbolic execution in that it incrementally explores the state space to find bugs, however preconditioned symbolic execution takes in an additional parameter. This gives way to a path prioritization technique.
- Given some predicate (aka the “additional parameter”) that asks the user what specific exploit they want to perform, the conjunction of the exploit predicate will induce constraints on the final solution. If the final constraints are not met, we consider the bug as non-exploitable.
Novelty #2 : Path Prioritization technique — use heuristics to choose likely more exploitable paths first
Why is this beneficial? Previously, we just had an infinite number of paths that we iterated through until we found something that maybe had an exploit. With a prioritization technique, we are able to run through a finite number of paths instead, focusing on our more potential paths first.
Ok, now to the actual process (from the article):
- Search for bugs at source code level by exploring execution paths (executes iwconfic using symbolic arguments as input soruces)
- Follow the path, detects an out of bounds or memory out of bounds error on some variable.
- AEG Solves the current path constraints and generates a concrete input that will trigger the detected bug
- Perform dynamic analysis on the iwconfig binary using input from step 2
- Generate constraints describing the exploit using the information from step 3
Their AEG was able to find two zero-day exploits for previously unknown vulnerabilities. Their AEG was also able to find such bugs “within seconds”, quite an astonishing result.
First, this paper is really technically heavy and difficult to understand because of how abstruse it is. I had a lot of trouble understanding it and relied on my advisor and peers to help me understand it. I still don’t think I fully understand it.
Second, there are no citations for the heuristics. They mention using heuristics, which is defined to be some practical solution that is not optimized/rational but works, without actually stating their references for choosing said heuristics. This is a little suspicious, but their results seem promising.
My friend pointed out that if it only takes 1 second to run, why not run more tests. Especially since this is such a shocking paper, why not just run hundreds or thousands of tests to solidify the case that the AEG is sure to work? The majority of examples in the paper are also centered around memory issues.
There are still issues such as creating an AEG that generates exploits directly from binary. Other issues include improve performance, scalability, etc. Another point the authors made was that of advanced exploits. They talked about extending AEG to handle heap-based over-flows. The trouble here is to extend control flow reasoning to also consider heap management structures. I would like to conclude with a quote from the paper, which is well written albeit technical.
We also do not claim AEG is a “solved” problem; there is always opportunity to improve perfor- mance, scalability, to work on a larger variety of exploit classes, and to work in new application settings.