Statically Detecting Likely Buffer Overflow Vulnerabilities
| 1988: Morris worm exploits buffer overflows in fingerd to infect 6,000 servers | ||
| 2001: Code Red exploits buffer overflows in IIS to infect 250,000 servers | ||
| Single largest cause of vulnerabilities in CERT advisories | ||
| Buffer overflow threatens Internet- WSJ(1/30/01) | ||
Why arent we better off than we were 13 years ago?
| Ignorance | ||
| C is difficult to use securely | ||
| Unsafe functions | ||
| Confusing APIs | ||
| Even security aware programmers make mistakes. | ||
| Security Knowledge has not been codified into the development process | ||
| Run-time solutions | ||
| StackGuard[USENIX 7], gcc bounds-checking, libsafe[USENIX 2000] | ||
| Performance penalty | ||
| Turns buffer overflow into a DoS attack | ||
| Compile-time solutions - static analysis | ||
| No run-time performance penalty | ||
| Checks properties of all possible executions | ||
| Tool that can be used by typical programmers as part of the development process | ||
| Fast, Easy to Use | ||
| Tool that can be used to check legacy code | ||
| Handles typical C programs | ||
| Encourage a proactive security methodology | ||
| Document key assumptions | ||
| Document assumptions about buffer sizes | ||
| Semantic comments | ||
| Provide annotated standard library | ||
| Allow user's to annotate their code | ||
| Find inconsistencies between code and assumptions | ||
| Make compromises to get useful checking | ||
| Use simplifying assumptions to improve efficiency | ||
| Use heuristics to analyze common loop idioms | ||
| Accept some false positives and false negatives (unsound and incomplete analysis) | ||
| Extended LCLint | ||
| Open source checking tool [FSE 94] [PLDI 96] | ||
| Uses annotations | ||
| Detects null dereferences, memory leaks, etc. | ||
| Integrated to take advantage of existing checking and annotations (e.g., modifies) | ||
| Added new annotations and checking for buffer sizes | ||
| requires, ensures | ||
| maxSet | ||
| highest index that can be safely written to | ||
| maxRead | ||
| highest index that can be safely read | ||
| char buffer[100]; | ||
| ensures maxSet(buffer) == 99 | ||
| void func(char *str){ char buffer[256]; strncat(buffer, str, sizeof(buffer) - 1); return; | |
| } |
| Intraprocedural | ||
| But use annotations on called procedures and global variables to check calls, entry, exit points | ||
| Expressions generate constraints | ||
| C semantics, annotations | ||
| Axiomatic semantics propagates constraints | ||
| Simplifying rules (e.g. maxRead(str+i) ==> maxRead(str) - i) | ||
| Produce warnings for unresolved constraints | ||
| Recognize common loop idioms | ||
| Use heuristics to guess number of iterations | ||
| Analyze first and last iterations | ||
| Example: | ||
| for (init; *buf; buf++) | ||
| Assume maxRead(buf) iterations | ||
| Model first and last iterations | ||
| wu-ftpd 2.5 and BIND 8.2.2p7 | ||
| Detected known buffer overflows | ||
| Unknown buffer overflows exploitable with write access to config files | ||
| Performance | ||
| wu-ftpd: 7 seconds/ 20,000 lines of code | ||
| BIND: 33 seconds / 40,000 lines | ||
| Athlon 1200 MHz | ||
| int acl_getlimit(char *class, char *msgpathbuf) | |
| { | |
| struct aclmember *entry = NULL; | |
| while (getaclentry("limit", &entry)) { | |
| strcpy(msgpathbuf, entry->arg[3]); |
| Lexical analysis | ||
| grep, its4, RATS, FlawFinder | ||
| Wagner, Foster, Brewer [NDSSS 00] | ||
| Integer range constraints | ||
| Flow insensitive analysis | ||
| Dor, Rodeh and Sagiv [SAS 01] | ||
| Source-to-source transformation with asserts and additional variables. | ||
Impediments to wide spread adoption
| People are lazy | |
| Programmers are especially lazy | |
| Adding annotations is too much work (except for security weenies) | |
| Working on techniques for automating the annotation process |
| 2014:??? | ||
| Will buffer overflows still be common? | ||
| Codify security knowledge in tools real programmers can use | ||
| Beta version now available: http://lclint.cs.virginia.edu | ||
| David Larochelle David Evans | ||
| larochelle@cs.virginia.edu evans@cs.virginia.edu | ||