How are zero days found?

Question

I believe that it was leaked recently that the NSA has a long list of zero day exploits on various software "for a rainy day," ie: for whenever it would be useful to them.

The question is, how do they find these zero days? Does someone have to physically sit at a computer and try a whole bunch of random things (ie: remote code execution encoded in base64 inside of a script in a PDF), or are there automated systems which actively pen-test pieces of software for holes where privilege escalation or remote code execution would work?

Answer 1

Zero-days are found in exactly the same ways as any other kind of hole. What makes a security hole a "zero day" relies exclusively on who is aware of the existence of the hole, not on any other technical characteristic.

Holes are found, usually, by inquisitive people who notice a funky behaviour, or imagine a possible bug and then try out to see if the programmer fell for it. For instance, I can imagine that any code which handles string contents and strives to be impervious to case differences (i.e. handles "A" as equivalent to "a") may run into problem when executed on a Turkish computer (because in Turkish language, the lowercase for "I" is "ı", not "i") which can lead to amusing bugs, even security holes (e.g. if some parts of the system checks for string equivalence in a locale-sensitive way, while others do not). Thus, I can try to configure my computer with a Turkish locale, and see if the software I target starts doing weird things (besides talking Turkish).

Part of bug-searching can be automated by trying a lot of "unusual combinations". This is known as fuzzing. It can help as a first step, to find input combinations which trigger crashes; anything which makes the target system crash ought to be investigated, because crashes usually mean memory corruption, and memory corruption can sometimes be abused into nifty things like remote code execution. However, such investigations must still be done by human brains.

(If there was a fully automatic way to detect security holes, then software developers would use it to produce bug-free code.)

Answer 2

To add to the excellent answer of Thomas Pornin, usually zero-day vulnerabilities are found through source code auditing, reverse engineering, and fuzzing (or fuzz testing).

The choice of the technique usually depends upon the information available at hand. For example, if the software is open source, then sifting through the source code and looking for vulnerabilities is the preferred way. Vulnerabilities found through source code auditing are usually the easier to exploit since you can examine and understand all execution branches by looking at the source code. The process of source code audit can be as simple as grep-ing for dangerous function calls like strcpy or can be as complex as automated code coverage testing looking for every branch code execution and analysis.

If source code is not available, the next option for the vulnerability researcher is to reverse engineer the application and analyse the low level code. When an application is analysed through a debugger or more preferably through a decompiler such as IDA, the code chunks and assembly mnemonics are mapped to a relatively high level language routine structures that are easy to analyse. The vulnerability researcher can then follow the execution flow and analyse the behaviour statically or dynamically for finding different security bugs. For example, allocating a fixed sized buffer and then copping user controlled input into the allocated buffer usually mean it can be exploited through a buffer overflow exploit.

The final method of finding new vulnerabilities in software is through fuzz testing. This can be also regarded as bug finding through bruteforcing since random input is generated and provided to all available input interfaces of the application in a hope that a specially crafted string (such as an overly long string or a string with special characters) can cause the software to crash. Once the software is crashed, the fuzz testing stops and let the vulnerability researcher analyse the input on which the application crashed. If the crash can be triggered reliably (for example every time a particular set of bytes provided to the application results in a crash) and the execution flow could be diverted to the user controlled data in an executable memory, then the bug is classified as remote code execution bug. Otherwise, if crash is reliable bug it can't be converted to code execution, then it is classified as a denial of service bug.