| --George W. Bush, Greater Nashua, NH, January 27, 2000 | ||
Previous chapters took a close look at a wide range of fuzzers. From simple byte-mutating generic file fuzzers to the most currently evolved fuzzing frameworks, fuzzing technologies overcome a number of automated software testing hurdles. In this chapter, we introduce the most advanced forms of fuzzing and the attempts to solve a dilemma common among all fuzzing technologies. Specifically, we tackle the indomitable task of breaking down a protocol into its basic building blocks.
The chapter begins with a discussion of primitive techniques targeted at automating protocol dissection and then advances into the application of bioinformatics and genetic algorithms. At the cutting edge of the automated software testing field, these subjects are largely theoretical and are currently being actively researched by a number of individuals.
The single most painful aspect of fuzz testing is the barrier to entry, especially when dealing with undocumented, complex binary protocols that require a great deal of research to understand. Imagine the task of fuzzing the Microsoft SMB protocol prior to 1992, when the first version of Samba[1] was released. The Samba project has since matured into a full-fledged and Windows-compatible SMB client–server. This is possible thanks to countless volunteer man hours. Do you currently have such a large team and over a decade of time to fuzz a similarly undocumented proprietary protocol?
Fuzzing your own protocols is easy. You are familiar with the format, the nuances, the complexities and even which areas you might have coded on little sleep and want to give extra attention to. Fuzzing a documented protocol such as HTTP is relatively easy as well. Detailed RFCs[4] and other public documents are available for reference. It’s a simple matter of data entry to produce an effective and thorough series of test cases. Beware however, even though a protocol is both common and documented does not guarantee that a software vendor has strictly adhered to the published standards. Consider the real-world example with Ipswitch IMail. In September 2006 a remotely exploitable stack overflow vulnerability was publicly disclosed[5] affecting Ipswitch’s SMTP daemon. The flaw exists due to a lack of bounds checking during the parsing of long strings contained within the characters @ and :. When looking at the right area in the binary the issue is trivial to spot. However, as the vulnerable functionality is a proprietary Ipswitch feature and not documented in any standard, there is less of a chance that a fuzzer would discover it.
Fuzzing a proprietary third-party protocol, no matter how simple, can be challenging at best. Pure random fuzzing is quickest to implement but yields far from intelligent results. Other generic techniques, such as byte flipping, provide better testing but require an extra step: Valid traffic between the client and server must first be observed. Fortunately, triggering communications between an arbitrary client–server pair is a simple task in most cases. However, there is no way to state with certainty what percentage of the protocol remains unobserved. For example, take HTTP with no assumptions of prior knowledge. Observing traffic for a short period of time will likely reveal the GET and POST actions. However, more obscure actions such as HEAD, OPTIONS, and TRACE are less likely to be observed. How do we uncover the less frequently used portions of an arbitrary protocol? To better dissect the target protocol, a reverse engineer can be unleashed on the client and server binaries. This is an expensive step as experienced reverse engineers are highly skilled and hard to find. In some cases, particularly with plain text protocols, additional functionality may sometimes be guessed. This luxury is less often available with a binary protocol.
Before going to the expensive of hiring or tasking of a skilled reverse engineer, be sure to leverage the work of others. The world is a big place and chances are that if you want details on a proprietary protocol, someone else has faced the same frustration. Before diving too deep be sure to ask your friend Google what he knows about the problem. You might be pleasantly surprised to uncover unofficial documentation produced by another individual that has already taken on the same challenge. Wotsit.org is also a great resource for file formats, both documented and undocumented. For network protocols, the source code to Wireshark and Ethereal also provides a good starting point, as this code includes protocol definitions for many of the better known proprietary protocols that have already been thoroughly dissected.
When the burden of deciphering a proprietary protocol falls solely on your shoulders, a less manually intensive approach is strongly desired. This chapter is dedicated to various methodologies that can assist in automating the process of detecting the signals, or structure, among the noise, or data, within network protocols and file formats.
The two techniques presented in this section are not true forms of automated protocol dissection. Rather, these heuristic-based techniques can be applied to improve fuzzing automation and performance. They are presented here to kick the chapter off prior to delving into more complicated methodologies.
The first heuristic-based dissection technique we discuss is implemented by a privately developed[6] fuzzing engine aptly named ProxyFuzzer. In the typical network-based client–server model, there is direct communication between the client and the server as shown in Figure 22.1.
As the name implies, a proxy fuzzer must sever the connection between client and server to position itself as a relay. To effectively accomplish this task, both the client and server must be manually configured[7] to look for one another at the address of the proxy. In other words, the client sees the proxy as the server and the server sees the proxy as the client. The new network diagram including the spliced-in fuzzer is shown in Figure 22.2.
The solid connecting lines between the nodes shown in Figure 22.2 represent original unmodified data that at this point has simply been rerouted through the proxy. In its default mode, ProxyFuzzer blindly relays received traffic on both ends while recording the transactions in a format suitable for programmatic modification or replay. This is a handy feature on its own as it allows researchers to skip the intermediary steps associated with generating and modifying raw packet capture (PCAP) files. As an aside, modifying and replaying recorded transactions is an excellent manual approach for reversing unknown protocols and is a technique well implemented by Matasano’s Protocol Debugger (PDB).[8]
Once ProxyFuzzer has been successfully configured and validated to be functioning, its automatic mutation engine can be enabled. In this mode, ProxyFuzzer processes relayed traffic looking for plain text components. It does so by identifying bytes that fall within the valid ASCII range in sequences longer than a specified threshold. Once identified, the discovered strings are either randomly lengthened or modified with invalid characters and format string tokens. Figure 22.3 depicts the mutated streams with dashed lines.
Although simplistic, ProxyFuzzer is extremely easy to use, provides assistance with manual analysis, and has even discovered security vulnerabilities in its current form! Perhaps the greatest benefit to inline (proxy) fuzzing is that the majority of the protocol remains intact while individual fields are mutated. Leaving the bulk of the data transfer untouched allows for successful fuzzing with little analysis. Consider, for example, complex protocols that implement sequence numbers at the data level. An invalid sequence number results in the immediate detection of protocol corruption and the remainder of the data, including the fuzzed field, is not parsed. By sitting inline, a fuzzer can leverage valid transactions and generate mutations valid enough to reach the parser.
Improvements are currently under development to make ProxyFuzzer “smarter.” Additional heuristics have been considered to assist in automated field detection and subsequent mutation. The current traffic parser is capable of isolating plain text fields from the remainder of a binary protocol. Identified plain text fields should be further processed, looking for common field delimiters and terminators such as spaces, colons, and so on. Additionally, raw bytes prior to detected strings can be searched for string length and type specifications (i.e., TLV fields). Possible length prefixes can then be verified through cross-examination across a number of packets. Raw bytes after strings can also be studied to detect padding of static fields. IP addresses of both the client and server frequently appear within the data stream (outside of the TCP/IP headers). As this information is known, the analysis engine can scan network data for both raw and ASCII representations.
By assuming that most simple protocols can be described as a sequence of fields that fall into one of the categories shown in Figure 22.4, we can begin to model the hierarchy of an unknown protocol through a series of guesses and validations.
This rudimentary technique will likely provide little value in dissecting complex binary protocols such as SMB. However, the end goal here is not to conduct a full protocol dissection, but rather to extend the range of simple protocols suitable for automatic fuzzing. As an applied example, consider the following contrived network data, shown here as one transaction per line with raw hex bytes bounded by the pipe (|) character:
|00 04|user|00 06|pedram|0a 0a 00 01|code rev 254|00 00 00 00 be ef|END |00 04|user|00 04|cody|0a 0a 00 02|code rev 11|00 00 00 00 00 de ad|END |00 04|user|00 05|aaron|0a 0a 00 03|code rev 31337|00 00 00 c0 1a|END
A human (and perhaps even a dolphin) can easily glance over these three transactions and quickly make educated guesses as to the specifics of the protocol. Let’s take a look at what our improved auto-analysis might uncover by examining solely the first transaction. To begin, a four-byte IP address field is quickly detected and anchored on (0a 0a 00 01 = private IP address 10.10.0.1). Next, four ASCII strings are detected: user, pedram, code rev 254, and END. The byte values ahead of each string are scanned for a one-byte valid length value, then a two-byte, three-byte, and finally four-byte value. The analysis routine can now guess that the protocol begins with two variable length strings, prefixed with a two-byte length, followed by the IP address of the connecting client. Scanning the next string for a length prefix yields no results. Assuming that this next ASCII field is of a static size, the engine looks for and finds four trailing null bytes. This next field is guessed to be a 10-byte static-sized ASCII field. The final string, END, contains no length prefix, nor is it followed by padding. This field is assumed to be a three-byte static-sized ASCII field. No assumption can be made about the field containing the remaining two bytes, 0xbeef. It can be static or variable length, so further analysis is required. Putting it all together, the engine was able to deduce the following protocol structure from the first transaction:
Two-byte string length followed by string.
Two-byte string length followed by string.
Four-byte client IP address.
10-byte static-length null-padded ASCII string.
Unknown binary field of static or variable length.
Three-byte static-length ASCII string.
The engine now proceeds to subsequent transactions to put the guesses made in the initial analysis to test. By doing so certain assumptions are confirmed and others are invalidated, all the while continuing to improve the accuracy of the modeled protocol. Unlike other simplified examples, this heuristic-based approach will fail on more complicated protocols. Keep in mind that the purpose was not to completely understand the underlying protocol, but rather improve unassisted fuzzing.
The application of (dis)assembly-level heuristics to assist in fuzzer effectiveness is a concept that has yet to be used by any publicly available fuzzing tools or frameworks. The concept is simple: While fuzzing, monitor code execution on the target through the use of a runtime instrumentation tool such as a debugger. In the debugger, look for static string and integer comparisons. Pass this information back to the fuzzer to be considered for inclusion in future generated test cases. Results will vary from case to case; however, the fuzzer can undoubtedly generate smarter data by properly leveraging this feedback loop. Consider the following code excerpt from real-world production server software:
0040206C call ds:__imp__sscanf 00402072 mov eax, [esp+5DA4h+var_5CDC] 00402079 add esp, 0Ch 0040207C cmp eax, 3857106359 ; string prefix check 00402081 jz short loc_40208D 00402083 push offset 'string' ; "access protocol error" 00402088 jmp loc_401D61
Raw network data is converted into an integer with the assistance of the sscanf() API. The resulting integer is then compared against the static integer value 3857106359 and if the values do not match then the protocol parser returns due to an “access protocol error.” The first time the fuzzer traverses this block of code the debugger component will discover the “magic” value and pass it through the feedback loop. The fuzzer can then include the value in a number of formats in hopes of tickling the target in the correct manner to expose further code coverage. Without the feedback loop, the fuzzer is dead in the water.
A proof of concept implementation of a target monitoring fuzzer feedback debugger was developed in little more than a couple of hours using the PyDbg component of the PaiMei[9] reverse engineering framework. Check http://www.fuzzing.org for the relevant source code.
With the more primitive techniques covered, we next take a look at a more advanced approach toward dissection automation with the introduction of bioinformatics.
Wikipedia defines bioinformatics, or computational biology, as a broad term that generalizes the use of “applied mathematics, informatics, statistics, computer science, artificial intelligence, chemistry and biochemistry to solve biological problems usually on the molecular level.”[10] In essence, bioinformatics encompasses various techniques that can be applied to discover patterns in long sequences of complex but structured data, such as gene sequences. Network protocols can also be viewed as long sequences of complex but structured data. Can software testers therefore borrow techniques from biologists to make fuzzing any easier?
The most basic analysis in bioinformatics is the ability to align two sequences, regardless of length, to maximize likeness. Gaps can be inserted into either sequence during alignment to facilitate this goal. Consider the following amino acid sequence alignment:
Sequence One: ACAT TACAGGA
Sequence Two: ACATTCCTACAGGAThree gaps were inserted into the first sequence to force length alignment and maximize similarity. A number of algorithms exist for accomplishing this and other sequence alignment tasks. One such algorithm, the Needleman-Wunsch (NW) algorithm,[11] was originally proposed in 1970 by Saul Needleman[12] and Christian Wunsch.[13] The NW algorithm is commonly applied in the field of bioinformatics to align two sequences of proteins or nucleotides. This algorithm is an example of “dynamic programming,” which is a method of solving larger problems by breaking them into a number of smaller problems.
Perhaps the first public demonstration of applying theorems from bioinformatics to the world of network protocol analysis was in late 2004 at the ToorCon[14] hacker conference held in San Diego, California. At the conference, Marshall Beddoe unveiled an experimental Python framework named Protocol Informatics (PI) that made quite a splash, even picking up a Wired article.[15] The original Web site has since been taken down and the framework has not been actively maintained. As the author of PI was hired by security analysis company Mu Security,[16] some speculate that the technology is no longer publicly available to make way for a commercial offering. Fortunately, a copy of the beta-quality PI code is still available for download from Packet Storm.[17]
The objective of the PI framework is to automatically deduce the field boundaries of arbitrary protocols through analysis of large quantities of observed data. PI has been demonstrated to successfully identify fields from the HTTP, ICMP, and SMB protocols. It does so with the assistance of the Smith-Waterman[18] (SW) local sequence alignment algorithm, the NW global sequence alignment algorithm, similarity matrices and phylogenetic trees. Although the fine details of the bioinformatics sciences applied by the PI framework goes beyond the scope of this book, the high-level overview and at least the names of the algorithms utilized are presented here.
Network protocols can contain a number of drastically different message types. Attempting a sequence alignment between different message types is fruitless. To address this issue, the SW algorithm for local sequence alignment is first applied to a pair of sequences to locate and match similar subsequences. These locations and matched pairs are later used to assist the NW global sequence alignment. Similarity matrices are used to assist the NW algorithm in optimizing the alignment between sequences. Two commonly used matrices, Percent Accepted Mutation (PAM) and the Blocks Substitution Matrix (BLOSUM), are applied by the PI framework to more appropriately align sequences based on data types. In application, this generalizes to aligning binary data with other binary data and ASCII data with other ASCII data. The distinction allows for more accurate identification of variable length fields within the protocol structure. The PI framework takes this a step further by performing multiple sequence alignment to better understand the target protocol. To dodge the computational infeasibility of applying NW directly, the Unweighted Pairwise Mean by Arithmetic Averages (UPGMA) algorithm is used to generate a phylogenetic tree that is then used as a heuristic guide to perform multiple alignments.
Let’s look at the framework in action by examining its ability to dissect a simple fixed length protocol, the ICMP.[19] Here are the basic steps to using the PI framework to dissect ICMP. First, some ICMP packets must be gathered for analysis:
# tcpdump -s 42 -c 100 -nl -w icmp.dump icmp
Next, the captured traffic can be run through the PI framework:
# ./main.py -g -p ./icmp.dump Protocol Informatics Prototype (v0.01 beta) Written by Marshall Beddoe <[email protected]> Copyright (c) 2004 Baseline Research Found 100 unique sequences in '../dumps/icmp.out' Creating distance matrix .. complete Creating phylogenetic tree .. complete Discovered 1 clusters using a weight of 1.00 Performing multiple alignment on cluster 1 .. complete Output of cluster 1 0097 x08 x00 xad x4b x05 xbe x00 x60 0039 x08 x00 x30 x54 x05 xbe x00 x26 0026 x08 x00 xf7 xb2 x05 xbe x00 x19 0015 x08 x00 x01 xdb x05 xbe x00 x0e 0048 x08 x00 x4f xdf x05 xbe x00 x2f 0040 x08 x00 xf8 xa4 x05 xbe x00 x27 0077 x08 x00 xe8 x28 x05 xbe x00 x4c 0017 x08 x00 xe8 x6c x05 xbe x00 x10 0027 x08 x00 xc3 xa9 x05 xbe x00 x1a 0087 x08 x00 xdd xc1 x05 xbe x00 x56 0081 x08 x00 x88 x42 x05 xbe x00 x50 0058 x08 x00 xb0 x42 x05 xbe x00 x39 0013 x08 x00 x3e x38 x05 xbe x00 0067 x08 x00 x99 x36 x05 xbe x00 x42 0055 x08 x00 x0f x56 x05 xbe x00 x36 0004 x08 x00 xe6 xda x05 xbe x00 x03 0028 x08 x00 x83 xd9 x05 xbe x00 x1b 0095 x08 x00 xc1 xd9 x05 xbe x00 x5e 0093 x08 x00 xb6 x05 xbe x00 x5c [ output trimmed for sake of brevity ] 0010 x08 x00 xd1 xb6 x05 xbe x00 0024 x08 x00 x11 x8f x05 xbe x00 x17 0063 x08 x00 x11 x04 x05 xbe x00 x3e 0038 x08 x00 x37 x3b x05 xbe x00 x25 DT BBB ZZZ BBB BBB BBB BBB ZZZ AAA MT 000 000 081 089 000 000 000 100 Ungapped Consensus: CONS x08 x00 x3f x18 x05 xbe x00 ??? DT BBB ZZZ BBB BBB BBB BBB ZZZ AAA MT 000 000 081 089 000 000 000 100 Step 3: Analyze Consensus Sequence Pay attention to datatype composition and mutation rate. Offset 0: Binary data, 0% mutation rate Offset 1: Zeroed data, 0% mutation rate Offset 2: Binary data, 81% mutation rate Offset 3: Binary data, 89% mutation rate Offset 4: Binary data, 0% mutation rate Offset 5: Binary data, 0% mutation rate Offset 6: Zeroed data, 0% mutation rate Offset 7: ASCII data, 100% mutation rate
Although not immediately obvious, the results of the generated analysis translate into the following protocol structure:
[ 1 byte ] [ 1 byte ] [ 2 byte ] [ 2 byte ] [ 1 byte ] [ 1 byte ]
The results are not far off from the real structure of the protocol:
[ 1 byte ] [ 1 byte ] [ 2 byte ] [ 2 byte ] [ 2 byte ]
The mistake in identifying the last field is due to the limited number of ICMP packets captured for analysis. The misidentified field is actually a 16-bit sequence number. As only 100 packets were used, the greatest significant byte of the field was never incremented. Had more data been passed to PI, the field size would have been correctly identified.
The application of bioinformatics to automated protocol dissection is a very interesting and advanced approach. Results are currently limited and a number of researchers are skeptical about the overall benefit of applying these techniques.[20] Nevertheless, as the PI framework has provided evidence of success, we can hope to see future developments on this methodology.
A genetic algorithm (GA) is an approximating search technique used by software that mimics evolution. A GA performs mutations on a base population while maintaining favored hereditary traits in future generations. Rules of natural selection are applied to choose generated samples that are more “fit” for their environment. The chosen samples are then mated and mutated and the process continues. Three components are typically required to define a GA:
A representation of what the solution might look like.
A fitness function for evaluating how good an individual solution might be.
A reproduction function responsible for mutation and crossover between two solutions.
To better illustrate these concepts, let’s consider a simple problem and its GA solution. The groundbreaking problem we would like to solve is maximizing the number of 1s in a binary string of length 10. The representation and fitness function for this problem are straightforward. Possible solutions are represented as a string of binary digits and the fitness function is defined as the count of the number of ones within the string. For our reproduction or mating function, we arbitrarily choose to swap the two strings at positions 3 and 6 and to randomly flip a bit in the offspring. This mating function might not be the most effective, but it satisfies our needs. The swapping rules allow parents to pass hereditary information and the bit flip accounts for random mutation. The GA evolves as follows:
To see it in action, let’s begin with a population of four randomly generated binary strings (solutions) and calculate each one’s fitness:
0100100000 2 1000001010 3 1110100111 7 0000001000 1
The center pair (highlighted in bold) are calculated as the most “fit” and are therefore chosen to mate (lucky them). Swapping at position 3 generates one pair of offspring and swapping at position 6 generates another:
1000001010 3 100 + 0100111 -> 1000100111 1110100111 7 111 + 0001010 -> 1110001010 1000001010 3 100000 + 0111 -> 1000000111 1110100111 7 111010 + 1010 -> 1110101010
The generated offspring then go through a random mutation (highlighted in bold) and the fitness function is applied again:
1000100111 -> 1010100111 6 1110001010 -> 1110000010 4 1000000111 -> 1000001111 5 1110101010 -> 1110101110 7
We can see the success of the GA as the average fitness of the new population has increased. In this specific example, we used a static mutation rate. In a more advanced example, we might choose to automatically raise the rate of mutation if generated offspring are not evolving over some threshold of time. Note that genetic algorithms are considered stochastic global optimizers. In other words, there is a random component to the algorithm so outputs are constantly changing. However, although a GA will continue to find better solutions it might not ever find the best possible solution (a string of all 1s in our example), regardless of runtime.
Applying genetic algorithms to improve fuzz testing is a subject matter that was most recently researched by a team at the University of Central Florida (UCF) and presented at the BlackHat US 2006 USA security conference.[21] The UCF team demonstrated a proof of concept tool, named Sidewinder, capable of automatically crafting inputs to force a designated execution path. The GA solutions in this case are generated fuzz data that are represented as context-free grammars.[22] A nontraditional fuzzing approach was then decided on to define a fitness function. Instead of generating data and monitoring for faults, potentially vulnerable code locations such as insecure API calls (e.g., strcpy) are first statically located. This step in the process is similar to how Autodafé locates points of code to apply increased weight to markers as discussed in the previous chapter. Next, the control-flow graph (CFG; not to be confused with a context-free grammar) for the entire target binary is examined and the subgraphs between the socket data entry points (calls to recv) and potentially vulnerable code locations are extracted. Figure 22.5 depicts an example CFG containing both of these points. For a detailed definition and explanation of CFGs, refer to Chapter 23, “Fuzzer Tracking.”
In the next step, the nodes on all paths connecting the entry point and the target vulnerable code must be identified. Figure 22.6 shows the same CFG with the nodes along the connecting path highlighted in black.
Next, the exit nodes within the same CFG are identified. An exit node is defined as the border node just outside the connecting path. If an exit node is reached then execution has deviated from any of the possible paths to the vulnerable code. Figure 22.7 shows the same CFG as before, with nodes along the connecting path highlighted in black. Additionally, the exit nodes are highlighted in white.
With the final highlighted CFG in hand, a fitness function can be defined. The UCF team applied a Markov process to the resulting CFG to calculate fitness based on the probability of traversing certain paths. In application and simpler terms, the following steps take place. A debugger is used to attach to the target process and set breakpoints on the entry node, the target node, the exit nodes, and all nodes along the connecting path. These breakpoints are monitored as they are reached to evaluate the progress on the runtime execution path for a given input (solution). Execution is tracked until an exit node is reached. Inputs are generated by the fuzzer and fed to the target process. Inputs with the highest “fitness” values are chosen to reproduce and the process continues until the target node, designating a potential vulnerability, is successfully reached.
Sidewinder combines static analysis, graph theory, and debugger instrumented runtime analysis to essentially brute force an input that can reach arbitrary locations within the target process. Although a powerful concept, there are a number of current limitations that make this a far from perfect solution. First, not all CFG structures are suitable for genetic algorithms to learn from. Specifically, some dependency must exist between the graph structure and data parsing. Also, extraction of accurate CFGs through static analysis is not always possible. An inaccurately extracted CFG will more than likely cause the entire process to fail. Finally, this approach can take an inordinately long time to generate valid data for protocols that contain TLV style fields. When fuzzing a protocol with a calculated CRC value, for example, our sun will likely supernova before the GA produces any useful results.
All in all, this technique is interesting to study and certainly adds value in some cases. Perhaps the best usage of Sidewinder is to assist a fuzzer in mutating inputs to traverse a small subpath to increase code coverage when necessary, as opposed to discovering an input that can traverse the entire connecting path from entry to target.
This chapter began with the statement that the most difficult aspect to fuzzing is overcoming the barrier to entry involved with understanding and modeling the target protocol or file format. Three general methodologies to assist in both manual and automated dissection were presented. Heuristic techniques, bioinformatics, and GAs were each described and reviewed as possible solutions. The concepts presented in this chapter are at the cutting edge of fuzzing research with advancements being made on a daily basis. For more up-to-date information and resources, visit http://www.fuzzing.org.