A group of four computer scientists urged Microsoft to redesign the way it distributes patches, after they created a technique that automatically produces attack code by comparing the vulnerable and repaired versions of a program. The technique, which the researchers refer to as automatic patch-based exploit generation (APEG), can create attack code for most major types of vulnerabilities in minutes by automating the analysis of a patch designed to fix the flaws, the researchers stated in a paper released last week.
If Microsoft does not change the way its patches are distributed to customers, attackers could create a system to attack the flaws in unpatched systems minutes after an update is released by the software giant, said David Brumley, a PhD candidate in computer science at Carnegie Mellon University.
"When Microsoft releases a patch, what they are saying - from a security standpoint - is, 'Here is an exploit,'" Brumley said.
Brumley along with computer scientists at Carnegie Mellon University, the University of California at Berkeley and the University of Pittsburgh built on already-familiar techniques used by many security researchers. Many security professionals reverse engineer patches - particularly patches pushed out by Microsoft - to find any vulnerabilities fixed by the update. In many cases, they create exploits for the flaws manually. Within a few days, and sometimes hours, of Microsoft releasing its monthly patches, attack code for the many of the flaws are created.
"People have been doing this for years," said Robert Graham, CEO of security firm Errata Security, who described a technique at a security conference last summer for discovering vulnerabilities by analyzing the signatures distributed by intrusion-detection system vendors. "There will be black hats that have the exploits in hours - Chinese hackers, Russian hackers among others."
In its recent Security Intelligence Report, Microsoft found that a third of the flaws patched by the company were exploited either before or after the update was released.
Yet, the APEG research could turn an unfavorable situation into a much more threatening one. In their research paper, Brumley and his colleagues demonstrate a method of automatically finding exploit candidates for flaws using a hybrid technique based on automatic test-case generation. The result: Given the differences between a patched and unpatched program, the APEG technique can generate exploit code in seconds or, at most, minutes, the researchers stated.
"I would say this is the next evolutionary step in the malware development cycle," said John C. Bambenek, a handler at the Internet Storm Center, a network-monitoring group, and researcher programmer at the University of Illinois.
The automatic patch-based exploit generation (APEG) requires that the differences in patched and unpatched binaries be found first. The researchers used eEye's Binary Diffing Suite (EBDS), but others - such as the well-known bindiff - could be used as well. The researchers then tested a number of heuristics for determining which of the changes actually fixed the flaw and discovered that, frequently, the smallest changes typically acted as a reliable marker for the location of a new sanity check.
Using principles from automated test-case generation processes, the four researchers modeled the flow of the program and used an intermediate language, known as Vine, to express the sequence of instructions that lead to the vulnerable code being executed. Knowing the execution path allows the researchers to place constraints on the inputs that could trigger the exploitation of the vulnerability, significantly reducing the number of possible variables through which the APEG has to search. The researchers used a combination of static analysis, where a single execution of the program is used to determine program flow, and dynamic analysis, where an abstract graph represents all the control-flow possibilities.
The result is a constraint formula, the solution to which are candidate exploits. The possible exploits can then be tested to determine which ones are true exploits for the vulnerability.
Brumley and his colleagues used the automatic patch-based exploit generation (APEG) system to create exploits from five recent Microsoft patches. After the differences between patched and unpatched binaries were found, the system took as little as six seconds to, at most, about three minutes to find an exploit.
"Specific types of attacks, such as control hijack, are just an extra condition on the set of all possible exploits for a single bug," Brumley said. "We can include such conditions in our approach."
Even though the system does not create fully weaponize exploits and may not work for all types of vulnerabilities, it does show that developing exploits from patches could be done in minutes. Yet, Microsoft has not taken adequate steps to make such attempts more difficult, Brumley said. The researchers suggested possible avenues that Microsoft could pursue to increase the likelihood that customers received patches before attackers could reverse engineer them, including obfuscating the code, encrypting the patches and waiting to distribute the key simultaneously, and using peer-to-peer distribution to push out patches faster.
"There are ways that Microsoft could distribute patches and not tip off the attackers," Brumley said.
Microsoft declined to comment for this article, except to say that the company is reviewing the research.
Some security experts doubt whether the APEG process could result in weaponized exploits quickly enough to pose a threat.
"Every patch from Microsoft has differences," Errata Security's Graham said. "There is nothing that can really generalize across Microsoft patches. There are a lot of possibilities for diagnostic tools that will shorten the time (to create an exploit), but that time will never go to zero."
Yet, even with his doubts, Graham stressed that the trend is clear and agreed that Microsoft should be thinking about making patches more difficult to exploit.
"You (developers) should generally be thinking about this," he said. "As reverse engineering gets more prevalent in the industry, you should be generally thinking about how to change your code to make it harder to do."
Brumley and his colleagues will present the paper at the annual IEEE Symposium on Security and Privacy in May. The co-authors of the paper are Pongsin Poosankam of Carnegie Mellon University, Dawn Song of University of California at Berkeley, and Jiang Zheng of University of Pittsburgh.
This article originally appeared in Security Focus.
Copyright © 2008, SecurityFocus