Effective Bug Discovery 9/2006 vf vf@nologin.org "If we knew what it was we were doing, it would not be called research, would it?" - Albert Einstein 1) Foreword Abstract: Sophisticated methods are currently being developed and implemented for mitigating the risk of exploitable bugs. The process of researching and discovering vulnerabilities in modern code will require changes to accommodate the shift in vulnerability mitigations. Code coverage analysis implemented in conjunction with fuzz testing reveals faults within a binary file that would have otherwise remained undiscovered by either method alone. This paper suggests a research method for more effective runtime binary analysis using the aforementioned strategy. This study presents empirical evidence that despite the fact that bug detection will become increasingly difficult in the future, analysis techniques have an opportunity to evolve intelligently. Disclaimer: Practices and material presented within this paper are meant for educational purposes only. The author does not suggest using this information for methods which may be deemed unacceptable. The content in this paper is considered to be incomplete and unfinished, and therefore some information in this paper may be incorrect or inaccurate. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, requires prior specific permission. Prerequisites: For an in-depth understanding of the concepts presented in this paper, a familiarity with Microsoft Windows device drivers, working with x86 assembler, debugging fundamentals, and the Windows kernel debugger is required. A brief introduction to the current state of code coverage analysis, including related uses, is introduced to support information presented within this paper. However, to implement the practices within this paper a deeper knowledge of aforementioned vulnerability discovery methods and methodologies are required. The following software and knowledge of its use is required to follow along with the discussion: IDAPro, Debugging tools for Windows, Debug Stalk, and a virtual machine such as VMware or Virtual PC. Thanks: The author would like to thank west, icer, skape, Uninformed, and mom. 2) Introduction 2.1) The status of vulnerability research Researchers employ a myriad of investigative techniques in the quest for vulnerabilities. In any case, there exists no silver bullet for the discovery of security related software bugs, not to mention the fact that several new security oriented kernel-mode components have recently been integrated into Microsoft operating systems that can make vulnerability investigations more difficult. Vista, particularly on the 64-bit edition, is integrating several mechanisms including driver signing, Secure Bootup using a TPM hardware chip, PatchGuard, kernel-mode integrity checks, and restricted user-mode access to . The Vista kernel also has an improved Low Fragmentation Heap and Address Space Layout Randomization. In later days, bugs were revealed via dumb fuzzing techniques, whereas this year more complicated bugs are indicating that knowledge of the format would require advanced understanding of a parser. Because of this, researchers are moving towards different discovery methods such as intelligent, rather than dumb, testing of drivers and applications. 2.2) The problem with fuzzing To compound the conception that these environments are becoming more difficult to test, monolithic black box fuzz testing, while frequently efficacious in its purpose, has a tendency for a exhibiting a lack of potency. The term ``monolithic'' is included as a reference to a comprehensive execution of the entire application or driver. Fuzzing is often executed in an environment where the tester does not know the internals of the binary in question. This leads to disadvantages in which a large number of tests must be executed to get an accurate estimate of binary's reliability. This investigation can be a daunting task if not implemented in a constructive manner. The test program and data selection should ensure independence from unrelated tests or groups of tests, thereby gaining the ability of complete coverage by reducing dependency on specific variables and their decision branching. Another disadvantage of monolithic black box fuzz testing is that it is difficult to provide coverage analysis even though the testing selection may cover the entire suite of security testing models. A further complication in this nature of testing is of cyclic dependency causing cyclic arguments which in turn leads to a lessening of coverage assurance. 2.3) Expectations This paper aims to educate the reader on the espousal of code coverage analysis and fuzzing philosophy presented by researchers as a means to lighten the burden of bug detection. A kernel mode device driver will be fuzzed for bugs using a standard fuzzing method. Results from the initial fuzzing test will be examined to determine coverage. The fuzz testing method will be revised to accommodate coverage concerns and an execution graph is generated to view the results of the previous testing. A comparison is then made between the two prior testing methods, proving how effective code coverage analysis through kernel mode Stalking can improve fuzzing endeavors. 3) QA Before understanding how the methodologies presented in this paper can be used, a few simple definitions and descriptions are addressed for the benefit of the reader. 3.1) What is code coverage? Code coverage, as represented by a Control Flow Graph (CFG), is defined as a measure of the exercised code within a program undergoing software testing. For the purpose of vulnerability research, the goal is to utilize code coverage analysis to obtain an exhaustive execution of all possible paths through code and data flow that may be relevant for revealing failures. It is used as a good metric in determining how a specific set of tests can uncover numerous faults. Techniques of proper code coverage analysis presented in this paper utilize basic mathematical properties of graph theory by including elements such as vertices, links and edges. Graph theory has lain somewhat dormant until recently being utilized by computer scientists which have subsequently defined their own sets of vocabulary for the subject. For the sake of research continuity and to link mathematical to computer science definitions, the verbiage used within this paper will equate vertices to code blocks, branches to decisions, and edges to code paths. To support our hypothesis, the aforementioned graph theory elements are compiled into CFGs. Informally, a Control Flow Graph is a directed graph composed of a finite set of vertices connected by edges indicating all possible routes a driver or application may take during execution. In other words, a CFG is merely blocks of code whose connected flow paths are determined by decisions. Block execution consists of a sequence of instructions which are free of branching or other control transfers except for the last instruction. These include branches or decisions which consist of Boolean expressions in a control structure. A path is a sequence of nodes traveled through by a series of uninterrupted links. Paths enable flow of information or data through code. In our case, a path is an execution flow and is therefore essential to measuring code coverage. Because of this factor, this investigation focuses directly on determining which paths have been traversed, which blocks and correlating data have been executed, and which links have been followed and finally applying it to fuzzing techniques. The purpose of code coverage analysis is ultimately to require all control decisions to be exercised. In other words, the application needs to be executed thoroughly using enough inputs that all edges in the graph are traversed at least once. These graphs will be represented as diagrams in which blocks are squares, edges are lines, and paths are colored. 4) Hypothesis: Code Coverage and Fuzzing In the security arena, fuzzing has traditionally manifested potential security holes by throwing random garbage at a target, hoping that any given code path will fail in the process of consuming the aforementioned data. The possibility of execution flowing through a particular block in code is the sum of probabilities of the conditional branches leading to blocks. In simplicity, if there are areas of code that are never executed during typical fuzz testing, then administering code coverage methodologies will reveal those unexecuted branches. Graphical code coverage analysis using CFGs helps determine which code path has been executed even without the use of symbol tables. This process allows the tester to more easily identify branch execution, and to subsequently design fuzz testing methods to properly attain complete code coverage. Prior experiments driven at determining the effectiveness of code coverage techniques identify that ensuring branch execution coverage will improve the likelihood of discovery of binary faults. 4.1) Process and Kernel Stalking One of the more difficult questions to answer when testing software for vulnerabilities is: ``when is the testing considered finished?'' How do we, as vulnerability bug hunters, know when we have completed our testing cycle by exhausting all code paths and discovering all possible bugs? Because fuzz testing can easily be random, so unpredictable, the question of when to conclude testing is often left incomplete. Pedram Amini, who recently released ``Paimei'', coined the term "Process Stalking" as a set of runtime binary analysis tools intended to enhance the visual effect of runtime analysis. His tool includes an IDA Pro plug-in paired with GML graph files for easy viewing. His strategy amalgamates the processes of runtime profiling through tracing and state mapping, which is a graphic model composed of behavior states of a binary. Pedram Amini's "Process Stalker" tool suite can be found on his personal website (http://pedram.redhive.com) and the reverse engineering website OpenRCE (http://www.openrce.org). -- might just use references or something. The fact that process stalker is used to reverse MS Update patches is irrelevant to the paper. 4.2) Stalking and Fuzzing Go Hand in Hand Process Stalker was transformed by an individual into a windbg extension for use in debugging user-mode and kernel-mode scenarios. This tool was given the title ``Debug Stalk,'' and until now this tool has remained unreleased. Process and Debug Stalker have overcome the static analysis visualization setback by implementing runtime binary analysis. Runtime analysis using Process and Debug Stalking in conjunction with mathematically enhanced CFGs exponentially improves the bug hunting mechanisms using fuzz techniques. Users can graphically determine via runtime analysis which paths have not been traversed and which blocks have not been executed. The user then has the opportunity to refine their testing approach to one that is more effective. When testing a large application, this technique dramatically reduces the overall workload of said scenarios. Therefore, iterations of the Process Stalk tool and the Debug Stalk tool will be used for investigating a faulty driver in this paper. Debug Stalk is a Windows debugger plug-in that can be used in places where Process Stalking may not be suited, such as in a kernel-mode setting. 5) Implementation For the mere sake of simple illustration, several tools have been created for testing our code coverage theories. Some of the test cases have been exaggerated and are not real world examples. This testing implementation is broken down into three parts: Part I includes sending garbage to the device driver with dumb fuzzing; Part II will include smarter fuzzing; Part III is a breakdown of how an intelligent level of fuzzing helps improve code coverage while testing. First, a very simple device driver named pluto.sys was created for the purpose of this paper. It contains several blocks of code with decision based branching that will be fuzzed. The fuzzer will send iterations of random data to pluto.sys. After fuzzing has completed, a post-analysis tool will review executed code blocks within the driver. Part II will contain the same process as Part I, however, it will include an updated fuzzer based on our Part I post-analysis that will allow the driver to call into a previously unexecuted code region. Part III uses the data collected in Parts I and II as illustrative example of a proof of a beneficiary code coverage thesis. 5.1) Stalking Setup Several software components need to be acquired before Stalking can begin: the Debug Stalk extension, Pedram's Process Stalker, Python, and the GoVisual Diagram Editor (GDE). Pedram's Stalker is listed on both his blog and on the OpenRCE website. The Process Stalker contains files such as the IDA Pro plug-in, and Python scripts that generate the GML graph files that will be imported into GDE. GDE provides a functional mechanism for editing and positioning of graphs including clustered graphing, creation and deletion of nodes, zooming and scrolling, automatic graph layout. Components can be obtained at the following locations: GDE: http://www.oreas.com/gde_en.php Python: http://www.python.org/download Proc Stalker: http://www.openrce.org/downloads/details/171/Process Stalker Debug Stalk: http://www.nologin.org/code 5.2) Installing the Stalker A walkthrough of installation for Process Stalker and required components will be covered briefly in this document, however, more detailed steps and descriptions are provided in Pedram's supporting manual. The .bpl file generated by the IDA plug-in will spit out a breakpoint list for entries within each block. The IDA plug-in processstalker.plw must be inserted into the IDA Pro plug-ins directory. Restarting IDA will allow the application to load the plug-in. A successful installation of the IDA plug-in in the log window will be similar to the following: [*] pStalker> Process Stalker – Profiler [*] pStalker> Pedram Amini [*] pStalker > Compiled on Sep 21 2006 Generating a .bpl file can be started by pressing Alt+5 within the IDA application. A dialog appears. Make sure that ``Enable Instruction Colors,'' ``Enable Comments,'' and ``Allow Self Loops'' are all selected. Pressing OK will prompt for a ``Save as'' dialog. The .bpl file must be named relative to its given name. For example, if calc.exe is being watched, the file name must be calc.exe.bpl. In our case, pluto.sys is being watched, so the file name must be pluto.sys.bpl. A successful generation of a .bpl file will produce the following output in the log window: talker> Profile analysis 25% complete. [*] pStalker> Profile analysis 50% complete. [*] pStalker> Profile analysis 7% complete. [*] pStalker> Profile analysis 100% complete. Opening the pluto.sys.bpl file will show that records are colon delimited: pluto.sys:0000002e:0000002e pluto.sys:0000006a:0000006a pluto.sys:0000007c:0000007c 5.3) Installing Debug Stalk The Debug Stalk extension can be built as follows. Open the Windows 2003 Server Build Environment window. Set the DBGSDK_INC_PATH and DBGSDK_LIB_PATH environment variables to specify the paths to the debugger SDK headers and the debugger SDK libraries, respectively. If the SDK is installed at c:\WINDBGSDK, the following would work: set DBGSDK_INC_PATH=c:\WINDBGSDK\inc set DBGSDK_LIB_PATH=c:\WINDBGSDK\lib This may vary depending on where the SDK is installed. The directory name must not contain a space (' ') in its path. The next step is to change directories to the project directory. If Debug Stalk source code is placed within the samples directory within the SDK (located at c:\WINDBGSDK), then the following should work: cd c:\WINDBGSDK\samples\dbgstalk-0.0.18 Typing build -cg at the command line to build the Debug Stalk project. Copy the dbgstalk.dll module from within this distribution to the root folder of the Debugging Tools for Windows root directory. This is the folder containing programs like cdb.exe and windbg.exe. If you have a default installation of "Debugging tools for Windows" already installed, the following should work: copy dbgstalk.dll "c:\Program Files\Debugging Tools for Windows\" The debugger plug-in should be installed at this point. It is important to note that Debug Stalk is a fairly new tool and has some reliability issues. It is a bit flakey and some hacking may be necessary in order to get it running properly. 5.4) Stalking with Kernel Debug 5.4.1) Part I For testing purposes, a Microsoft Operating System needs to be set up inside of a Virtual PC environment. Load the pluto.sys driver inside of the Virtual PC and attach a debug session via Kernel Debug (kd). Once kd is loaded and attached to a process within the Virtual Machine, Debug Stalk can be invoked by calling "!dbgstalk.dbgstalk [switches] [.bpl file path]" at the kd console. For example: C:\Uninformed>kd -k com:port=\\.\pipe\woo,pipe Microsoft (R) Windows Debugger Version 6.6.0007.5 Copyright (c) Microsoft Corporation. All rights reserved. Opened \\.\pipe\woo Waiting to reconnect... Connected to Windows XP 2600 x86 compatible target, ptr64 FALSE Kernel Debugger connection established. Windows XP Kernel Version 2600 (Service Pack 2) UP Free x86 compatible Product: WinNt, suite: TerminalServer SingleUserTS Built by: 2600.xpsp_sp2_rtm.040803-2158 Kernel base = 0x804d7000 PsLoadedModuleList = 0x8055ab20 Debug session time: Sat Sep 23 14:40:24.522 2006 (GMT-7) System Uptime: 0 days 0:06:50.610 Break instruction exception - code 80000003 (first chance) nt!DbgBreakPointWithStatus+0x4: 804e3b25 cc int 3 kd> .reload Connected to Windows XP 2600 x86 compatible target, ptr64 FALSE Loading Kernel Symbols ....................................................... Loading User Symbols Loading unloaded module list ........... kd> !dbgstalk.dbgstalk -o -b c:\Uninformed\pluto.sys.bpl [*] - Entering Stalker [*] - Break Point List.....: c:\Uninformed\pluto.sys.bpl [*] - Breakpoint Restore...: OFF [*] - Register Enumerate...: ON [*] - Kernel Stalking:.....: ON current context: eax=00000001 ebx=ffdff980 ecx=8055192c edx=000003f8 esi=00000000 edi=f4be2de0 eip=804e3b25 esp=80550830 ebp=80550840 iopl=0 nv up ei pl nz na po nc cs=0008 ss=0010 ds=0023 es=0023 fs=0030 gs=0000 efl=00000202 nt!RtlpBreakWithStatusInstruction: 804e3b25 cc int 3 commands: [m] module list [0-9] enter recorder modes [x] stop recording [v] toggle verbosity [q] quit/close Once Debug Stalk is loaded, a list of commands is available to the user. A breakdown of the command line options offered by Debug Stalk is as follows: [m] module list [0-9] enter recorder modes [x] stop recording [v] toggle verbosity [q] quit/close At this point, the fuzz tool needs to be executed to send random arbitrary data to the device driver. While the fuzzer is running, Debug Stalk will print out information to kd. Pressing 'g' at the command line prompt will resume execution of the target machine. This invocation will look something like this: kd> g [*] - Recorder Opened......: pluto.sys.0 [*] - Recorder Opened......: pluto.sys-regs.0 Modload: Processing breakpoints for module pluto.sys at f7a7f000 Modload: Done. 46 of 46 breakpoints were set. 0034c883 T:00000001 [bp] f7a83000 a10020a8f7 mov eax,dword ptr [pluto+0x3000 (f7a82000)] 0034ed70 T:00000001 [bp] f7a8300e 3bc1 cmp eax,ecx 0034eded T:00000001 [bp] f7a83012 a12810a8f7 mov eax,dword ptr [pluto+0x2028 (f7a81028)] 0034ee89 T:00000001 [bp] f7a8302b e9aed1ffff jmp pluto+0x11de (f7a801de) 0034ef16 T:00000001 [bp] f7a801de 55 push ebp 0034ef93 T:00000001 [bp] f7a80219 8b45fc mov eax,dword ptr [ebp-4] 0034f03f T:00000001 [bp] f7a80253 6844646b20 push 206B6444h 0034f0cb T:00000001 [bp] f7a802a2 b980000000 mov ecx,80h 0034f148 T:00000001 [bp] f7a802ab 5f pop edi 00359086 T:00000001 [bp] f7a8006a 8b4c2408 mov ecx,dword ptr [esp+8] 0035920c T:00000001 [bp] f7a800f6 833d0420a8f700 cmp dword ptr [pluto+0x3004 (f7a82004)],0 003592a9 T:00000001 [bp] f7a8010c 8b7760 mov esi,dword ptr [edi+60h] 00359345 T:00000001 [bp] f7a80114 8b4704 mov eax,dword ptr [edi+4] 003593e1 T:00000001 [bp] f7a80122 6a10 push 10h 0035945e T:00000001 [bp] f7a80133 85c0 test eax,eax 003594eb T:00000001 [bp] f7a80147 ff7604 push dword ptr [esi+4] 00359587 T:00000001 [bp] f7a80176 8bcf mov ecx,edi 00359614 T:00000001 [bp] f7a80182 5f pop edi 0035ac5b T:00000001 [bp] f7a8002e 55 push ebp current context: eax=00000001 ebx=0000c271 ecx=8055192c edx=000003f8 esi=00000001 edi=291f0c30 eip=804e3b25 esp=80550830 ebp=80550840 iopl=0 nv up ei pl nz na po nc cs=0008 ss=0010 ds=0023 es=0023 fs=0030 gs=0000 efl=00000202 nt!RtlpBreakWithStatusInstruction: 804e3b25 cc int 3 commands: [m] module list [0-9] enter recorder modes [x] stop recording [v] toggle verbosity [q] quit/close kd> q [*] - Exiting Stalker q Debug Stalk has finished Stalking the points in the driver allowed by the fuzzer. Files named "pluto.sys.0," "pluto.sys-regs.0 (optional)," have been saved to the current working directory. 5.5) Analyzing the output Pedram has developed a set of Python scripts to support the .bpl and recorder output file, such as adding register metadata to the graph, filtering generated breakpoint lists, additional GDE support for difficult graphs, combining multi-function graphs into a conglomerate graph, highlighting interesting blocks, importing back into the IDA changes made directly to the graph, adding function offsets to breakpoint addresses and optionally rebasing the recording addresses, and much more. Pedram provides detailed descriptions and usage of his python scripts in his manual. The Python scripts used for formatting the .gml files (for block based coverage) are psprocessrecording and psviewrecordingfuncs. The psprocessrecording script is executed first on the pluto.sys.0 which will produce another file called pluto.sys.0.BadFuzz-processed. The psviewrecordingfuncs is executed on the pluto.sys.0.BadFuzz-processed file to produce the file called BadFuzz.gml, which is the chosen name for the initial testing technique. More information on Pedram's Python scripts, reference the Process Stalking Manual. Opening the resulting .gml file will enable us to view the following graph. Executed blocks are available in pink, unexecuted blocks are shown as grey, paths of execution are green lines, and unexecuted paths are red lines. At this point it is important to note that the code block starting at address 00011169 does not get executed. This is detrimental to our testing process because it appears that fuzzer supplied data is passed to it and it does not appear to get executed. Based on this evidence, we can conclude that a readjustment of our testing methodologies needs to be put in place so that we can hit that unexecuted block. Analysis indicates that the device driver does not execute block 00011169 because a comparison is made in the block at address 00011147 which reveals that [eax] does not match a specified value. Since eax is pointing to the fuzzer supplied data, we should be able to adjust the fuzzer to meet the requirement of the 00011161 cmp dword ptr [eax], 0DEADBEEFh instruction, which will allow us to get into block 00011169. BetterFuzz.exe was improved to do complete the previous description. 5.5.1) Part II Determining that the previous testing methodology is not effective, a re-engineering of the test case has been implemented and re-testing the driver to hit the missed block can now be accomplished. Following the steps provided in Part I, the driver is loaded into the Virtual PC, kd is attached to the driver process, and Debug Stalk has been loaded into kd and has been invoked to run by using the 'g' command. The entire process is the same except that when the new fuzz test is invoked, different output is printed to kd: kd> g [*] - Recorder Opened......: pluto.sys.0 [*] - Recorder Opened......: pluto.sys-regs.0 Modload: Processing breakpoints for module pluto.sys at f7a27000 Modload: Done. 46 of 46 breakpoints were set. 004047a0 T:00000001 [bp] f7a2b000 a100a0a2f7 mov eax,dword ptr [pluto+0x3000 (f7a2a000)] 004052bc T:00000001 [bp] f7a2b00e 3bc1 cmp eax,ecx 00405339 T:00000001 [bp] f7a2b012 a12890a2f7 mov eax,dword ptr [pluto+0x2028 (f7a29028)] 004053e5 T:00000001 [bp] f7a2b02b e9aed1ffff jmp pluto+0x11de (f7a281de) 00405462 T:00000001 [bp] f7a281de 55 push ebp 004054ee T:00000001 [bp] f7a28219 8b45fc mov eax,dword ptr [ebp-4] 0040558b T:00000001 [bp] f7a28253 6844646b20 push 206B6444h 00405617 T:00000001 [bp] f7a282a2 b980000000 mov ecx,80h 00405694 T:00000001 [bp] f7a282ab 5f pop edi 00406ccc T:00000001 [bp] f7a2806a 8b4c2408 mov ecx,dword ptr [esp+8] 00406e04 T:00000001 [bp] f7a280f6 833d04a0a2f700 cmp dword ptr [pluto+0x3004 (f7a2a004)],0 00406eb0 T:00000001 [bp] f7a2810c 8b7760 mov esi,dword ptr [edi+60h] 00406f4c T:00000001 [bp] f7a28114 8b4704 mov eax,dword ptr [edi+4] 00406ff8 T:00000001 [bp] f7a28122 6a10 push 10h 00407075 T:00000001 [bp] f7a28133 85c0 test eax,eax 00407102 T:00000001 [bp] f7a28147 ff7604 push dword ptr [esi+4] 004071ae T:00000001 [bp] f7a28169 6a04 push 4 current context: eax=00000003 ebx=00000000 ecx=8050589d edx=0000006a esi=00000000 edi=f1499052 eip=804e3b25 esp=f3cbe720 ebp=f3cbe768 iopl=0 nv up ei pl zr na pe nc cs=0008 ss=0010 ds=0023 es=0023 fs=0030 gs=0000 efl=00000246 nt!RtlpBreakWithStatusInstruction: 804e3b25 cc int 3 commands: [m] module list [0-9] enter recorder modes [x] stop recording [v] toggle verbosity [q] quit/close kd> k ChildEBP RetAddr f3c1971c 805328e7 nt!RtlpBreakWithStatusInstruction f3c19768 805333be nt!KiBugCheckDebugBreak+0x19 f3c19b48 805339ae nt!KeBugCheck2+0x574 f3c19b68 805246fb nt!KeBugCheckEx+0x1b f3c19bb4 804e1ff1 nt!MmAccessFault+0x6f5 f3c19bb4 804da1ee nt!KiTrap0E+0xcc *** ERROR: Module load completed but symbols could not be loaded for pluto.sys f3c19c48 f79f0173 nt!memmove+0x72 WARNING: Stack unwind information not available. Following frames may be wrong. f3c19c84 8057a510 pluto+0x1173 f3c19d38 804df06b nt!NtWriteFile+0x602 f3c19d38 7c90eb94 nt!KiFastCallEntry+0xf8 0006fec0 7c90e9ff ntdll!KiFastSystemCallRet 0006fec4 7c81100e ntdll!ZwWriteFile+0xc 0006ff24 01001276 kernel32!WriteFile+0xf7 0006ff44 010013a7 betterfuzz_c!main+0xa4 0006ffc0 7c816d4f betterfuzz_c!mainCRTStartup+0x12f 0006fff0 00000000 kernel32!BaseProcessStart+0x23 current context: eax=00000003 ebx=00000000 ecx=8050589d edx=0000006a esi=00000000 edi=f1499052 eip=804e3b25 esp=f3c19720 ebp=f3c19768 iopl=0 nv up ei pl zr na pe nc cs=0008 ss=0010 ds=0023 es=0023 fs=0030 gs=0000 efl=00000246 nt!RtlpBreakWithStatusInstruction: 804e3b25 cc int 3 commands: [m] module list [0-9] enter recorder modes [x] stop recording [v] toggle verbosity [q] quit/close kd> q [*] - Exiting Stalker q C:\Uninformed> Generating the .gml file allows the tester to view the new execution path. In this case the block at address 00011169 is executed. All subsequent blocks underneath it are not executed because the driver BugChecks inside of this newly hit block indicating a bug of some sort. Command 'k' in kd produces the stack unwind information and we can see that a BugCheck was initiated for an Access Violation that occurs inside of pluto.sys. 5.6) Part III Analysis of the graph BadFuzz.gml generated in Part I indicated that the testing methods used were not effective enough to exhibit optimal code coverage of the device driver in question. Part II implemented an improved test case based on the coverage analysis used in Part I. Graph BetterFuzz.gml allowed test executers to view the improved testing methods to ensure that the missed block was reached. This process revealed a fault in block 00011169 which would have otherwise remained undetected without code coverage analysis. 6) Conclusion and Future Work This paper illustrated an improved testing technique by taking advantage of code coverage methods using basic graph theory. The author would like to reiterate that the driver and fuzz tool used in this paper were simple examples to illustrate the effectiveness of code coverage practices. Finally, more research and experimentation are needed to fully implement these theorems. The question remains on how to integrate a full code coverage analysis tool and a fuzzing tool. Much work has been done on code coverage techniques and their implementations. For example, the paper entitled Cryptographic Verification of Test Coverage Claims, Devanbu, et al presents protocols for coverage testing methods such as verifying coverage with and without source code, with just the binary which can utilize both block and branch testing (e0178[1].PDF). A tool to automate the espousal of code coverage and fuzz technologies needs to be implemented so that the two technologies may work together without manual investigation. Further research may include more sophisticated coverage techniques using graph theory such as super blocks, denominators, and applying weights to frequently used loops, paths and edges. CFGs may also benefit from Bayesian networks which are a directed cyclic graph of nodes represented as variables including distribution probability for these variables given the values of its parents. In other words, the Bayesian theory may be helpful for deterministic prediction of code execution which can in turn lead to more intelligent fuzzing. In closing, the author extends the hope that methods and methodologies shared herein can offer other ideas to researchers. A. References Devanbu, T (2000). Cryptographic Verification of Test Coverage Claims. IEEE. 2, 178-192.