Fuzzing

Brute Force Vulnerability Discovery

Michael Sutton
Adam Greene
Pedram Amini

Upper Saddle River, NJ • Boston • Indianapolis • San Francisco
New York • Toronto • Montreal • London • Munich • Paris • Madrid
Cape Town • Sydney • Tokyo • Singapore • Mexico City

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals.

The author and publisher have taken care in the preparation of this book but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein.

The publisher offers excellent discounts on this book when ordered in quantity for bulk purchases or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focus, and branding interests. For more information, please contact:

U.S. Corporate and Government Sales
800-382-3419
corpsales@pearsontechgroup.com

For sales outside the United States, please contact:

International Sales
international@pearsoned.com

Visit us on the Web: www.awprofessional.com

Library of Congress Cataloging-in-Publication Data:

Sutton, Michael, 1973–
Fuzzing : brute force vulnerability discovery / Michael Sutton, Adam Greene, Pedram Amini. --
1st ed.
p. cm.
Includes index.
ISBN 0-321-44611-9 (pbk. : alk. paper) 1. Computer security. 2. Computer networks--Security
measures. 3. Computer software--Development. I. Greene, Adam, 1983– II. Amini, Pedram. III.
Title.
QA76.9.A25S89 2007
005.8--dc22
2007011463

Copyright © 2007 Pearson Education, Inc.

All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permissions, write to:

Pearson Education, Inc.
Rights and Contracts Department
One Lake Street
Upper Saddle River, NJ 07458
Fax: (201) 236-3290

Text printed in the United States on recycled paper at R. R. Donnelley, Crawfordsville, Indiana

First printing, June 2007

This book is dedicated to the two most important women in my life. Mom, without your many sacrifices, nothing would have been possible. This book is only one small example. Amanda, your unwavering love and support inspire me to achieve each and every day. I am truly a fortunate man to be married to such an amazing woman.

—Michael Sutton

This work is dedicated to my family and friends. Thank you all for your support and patience.

—Adam Greene

I dedicate this book to George W. Bush, my Commander-in-Chief, whose impressive career advancement despite remedial language skills inspired me to believe that I was capable of authoring a book.

—Pedram Amini

Contents

Foreword

Preface

Acknowledgments

About the Author

Part I Background

Chapter 1 Vulnerability Discovery Methodologies

White Box Testing

Source Code Review

Tools and Automation

Pros and Cons

Black Box Testing

Manual Testing

Automated Testing or Fuzzing

Pros and Cons

Gray Box Testing

Binary Auditing

Automated Binary Auditing

Pros and Cons

Summary

Chapter 2 What Is Fuzzing?

Definition of Fuzzing

History of Fuzzing

Fuzzing Phases

Fuzzing Limitations and Expectations

Access Control Flaws

Poor Design Logic

Backdoors

Memory Corruption

Multistage Vulnerabilities

Summary

Chapter 3 Fuzzing Methods and Fuzzer Types

Fuzzing Methods

Pregenerated Test Cases

Random

Manual Protocol Mutation Testing

Mutation or Brute Force Testing

Automatic Protocol Generation Testing

Fuzzer Types

Local Fuzzers

Remote Fuzzers

In-Memory Fuzzers

Fuzzer Frameworks

Summary

Chapter 4 Data Representation and Analysis

What Are Protocols?

Protocol Fields

Plain Text Protocols

Binary Protocols

Network Protocols

File Formats

Common Protocol Elements

Name–Value Pairs

Block Identifiers

Block Sizes

Checksums

Summary

Chapter 5 Requirements for Effective Fuzzing

Reproducibility and Documentation

Reusability

Process State and Process Depth

Tracking, Code Coverage, and Metrics

Error Detection

Resource Constraints

Summary

Part II Targets and Automation

Chapter 6 Automation and Data Generation

Value of Automation

Helpful Tools and Libraries

Ethereal/Wireshark

libdasm and libdisasm

Libnet/LibnetNT

LibPCAP

Metro Packet Library

PTrace

Python Extensions

Programming Language Choice

Data Generation and Fuzz Heuristics

Integer Values

String Repetitions

Field Delimiters

Format Strings

Character Translation

Directory Traversal

Command Injection

Summary

Chapter 7 Environment Variable and Argument Fuzzing

Introduction to Local Fuzzing

Command-Line Arguments

Environment Variables

Local Fuzzing Principles

Finding Targets

UNIX File Permissions Explained

Local Fuzzing Methods

Enumerating Environment Variables

The GNU Debugger (GDB) Method

Automating Environment Variable Fuzzing

Library Preloading

Detecting Problems

Summary

Chapter 8 Environment Variable and Argument Fuzzing:Automation

Features of iFUZZ Local Fuzzer

Development

Development Approach

Language

Case Study

Benefits and Room for Improvement

Summary

Chapter 9 Web Application and Server Fuzzing

What Is Web Application Fuzzing?

Targets

Methods

Set Up

Inputs

Vulnerabilities

Detection

Summary

Chapter 10 Web Application and Server Fuzzing:Automation

Web Application Fuzzers

Features

Requests

Fuzz Variables

Responses

Necessary Background Information

Identifying Requests

Detection

Development

Approach

Language Selection

Design

Case Studies

Directory Traversal

Overflow

SQL Injection

XSS Scripting

Benefits and Room for Improvement

Summary

Chapter 11 File Format Fuzzing

Targets

Methods

Brute Force or Mutation-Based Fuzzing

Intelligent Brute Force or Generation-Based Fuzzing

Inputs

Vulnerabilities

Denial of Service

Integer Handling Problems

Simple Stack and Heap Overflows

Logic Errors

Format Strings

Race Conditions

Detection

Summary

Chapter 12 File Format Fuzzing:Automation on UNIX

notSPIKEfile and SPIKEfile

What’s Missing?

Development Approach

Exception Detection Engine

Exception Reporting (Exception Detection)

Core Fuzzing Engine

Meaningful Code Snippets

Usually Interesting UNIX Signals

Not So Interesting UNIX Signals

Zombie Processes

Usage Notes

Adobe Acrobat

RealNetworks RealPlayer

Case Study: RealPlayer RealPix Format String Vulnerability

Language

Summary

Chapter 13 File Format Fuzzing:Automation on Windows

Windows File Format Vulnerabilities

Features

File Creation

Application Execution

Exception Detection

Saved Audits

Necessary Background Information

Identifying Targets

Development

Approach

Language Selection

Design

Case Study

Benefits and Room for Improvement

Summary

Chapter 14 Network Protocol Fuzzing

What Is Network Protocol Fuzzing?

Targets

Layer 2: Data Link Layer

Layer 3: Network Layer

Layer 4: Transport Layer

Layer 5: Session Layer

Layer 6: Presentation Layer

Layer 7: Application Layer

Methods

Brute Force or Mutation-Based Fuzzing

Intelligent Brute Force or Generation-Based Fuzzing

Modified Client Mutation Fuzzing

Fault Detection

Manual (Debugger Based)

Automatic (Agent Based)

Other Sources

Summary

Chapter 15 Network Protocol Fuzzing:Automation on UNIX

Fuzzing with SPIKE

Choosing the Target

Reversing the Protocol

SPIKE 101

Fuzz Engine

Generic Line-Based TCP Fuzzer

Block-Based Protocol Modeling

Additional SPIKE Features

Protocol-Specific Fuzzers

Protocol-Specific Fuzz Scripts

Generic Script-Based Fuzzers

Writing the SPIKE NMAP Fuzzer Script

Summary

Chapter 16 Network Protocol Fuzzing:Automation on Windows

Features

Packet Structure

Capturing Data

Parsing Data

Fuzz Variables

Sending Data

Necessary Background Information

Detection

Protocol Driver

Development

Language Selection

Packet Capture Library

Design

Case Study

Benefits and Room for Improvement

Summary

Chapter 17 Web Browser Fuzzing

What Is Web Browser Fuzzing?

Targets

Methods

Approaches

Inputs

Vulnerabilities

Detection

Summary

Chapter 18 Web Browser Fuzzing:Automation

Component Object Model Background

History in a Nutshell

Objects and Interfaces

ActiveX

Fuzzer Development

Enumerating Loadable ActiveX Controls

Properties, Methods, Parameters, and Types

Fuzzing and Monitoring

Summary

Chapter 19 In-Memory Fuzzing

In-Memory Fuzzing: What and Why?

Necessary Background Information

No Really, What Is In-Memory Fuzzing?

Targets

Method: Mutation Loop Insertion

Method: Snapshot Restoration Mutation

Testing Speed and Process Depth

Fault Detection

Summary

Chapter 20 In-Memory Fuzzing:Automation

Required Feature Set

Language Choice

Windows Debugging API

Putting It All Together

How Do We Implement Our Need to “Hook” into the Target Process at Specific Points?

How Do We Handle Process Snapshots and Restores?

How Do We Choose Our Hook Points?

How Do We Locate and Mutate Target Memory Space?

PyDbg, Your New Best Friend

A Contrived Example

Summary

Part III Advanced Fuzzing Technologies

Chapter 21 Fuzzing Frameworks

What Is a Fuzzing Framework?

Existing Frameworks

antiparser

Dfuz

SPIKE

Peach

General Purpose Fuzzer

Autodafé

Custom Fuzzer Case Study: Shockwave Flash

Modeling SWF Files

Generating Valid Data

Fuzzing Environment

Testing Methodologies

Sulley: Fuzzing Framework

Sulley Directory Structure

Data Representation

Session

Postmortem

A Complete Walkthrough

Summary

Chapter 22 Automated Protocol Dissection

What’s the Problem with Fuzzing?

Heuristic Techniques

Proxy Fuzzing

Improved Proxy Fuzzing

Disassembly Heuristics

Bioinformatics

Genetic Algorithms

Summary

Chapter 23 Fuzzer Tracking

What Exactly Are We Tracking?

Binary Visualization and Basic Blocks

CFGs

CFGs Illustrated

Architecting a Fuzzer Tracker

Profiling

Tracing

Cross-Referencing

Dissecting a Code Coverage Tool

PStalker Layout Overview

Data Sources

Data Exploration

Data Capture

Limitations

Data Storage

Case Study

Strategy

Tactics

Benefits and Future Improvements

Future Improvements

Summary

Chapter 24 Intelligent Fault Detection

Primitive Fault Detection

What Are We Looking For?

A Note on Choosing Fuzz Values

Automated Debugger Monitoring

A Basic Debugger Monitor

A More Advanced Debugger Monitor

First-Chance Versus Last-Chance Exceptions

Dynamic Binary Instrumentation

Summary

Part IV Looking Forward

Chapter 25 Lessons Learned

Software Development Lifecycle

Analysis

Design

Coding

Testing

Maintenance

Implementing Fuzzing in the SDLC

Developers

QA Researchers

Security Researchers

Summary

Chapter 26 Looking Forward

Commercial Tools

Beyond Security beSTORM

BreakingPoint Systems BPS-1000

Codenomicon

GLEG ProtoVer Professional

Mu Security Mu-4000

Security Innovation Holodeck

Hybrid Approaches to Vulnerability Discovery

Integrated Test Platforms

Summary

Index

Foreword

Vulnerabilities are the life-blood of security research. Whether you are performing a penetration test, evaluating a new product, or auditing the source code of a critical component—vulnerabilities drive your decisions, provide justification for your time, and influence your choices for years to come.

Source code auditing is a white box testing technique that has long been a popular approach for uncovering vulnerabilities in software products. This method requires the auditor to know every programming concept and function used in the product, and to have a deep understanding of the product’s operating environment. Source code auditing also has one obvious pitfall—the source code for the product must be available.

Thankfully, there are black box alternatives that do not require access to source code. One such alternative is a technique known as fuzzing, which has proven successful at discovering critical vulnerabilities in products that would not be feasible to audit any other way. Fuzzing is the process of sending intentionally invalid data to a product in the hopes of triggering an error condition or fault. These error conditions can lead to exploitable vulnerabilities.

There are no real rules for fuzzing. It is a technique where success is measured solely by the results of the test. For any given product, there may be an infinite number of inputs you can provide. Fuzzing is the process of predicting what types of programming errors may exist in the product and the inputs that will trigger those errors. For this reason, fuzzing is much more of an art than a science.

Fuzzing can be as simple as randomly hitting keys on a keyboard. The 3-year-old son of a friend once discovered a vulnerability in the Mac OS X operating system’s screen lock using this technique. My friend locked his screen and walked to the kitchen to get a drink. By the time he got back, his son had managed to disable the screen lock, and open a web browser, just by banging on the keyboard.

Over the last few years, I have used fuzzing tools and techniques to discover hundreds of vulnerabilities in an extensive range of software. In December 2003, I wrote a simple tool that sent a stream of random UDP packets to a remote service. This tool was used to discover two new vulnerabilities in the Microsoft WINS server. The same tool later aided in identifying serious flaws in a handful of other products. It turned out that a random stream of UDP packets was all that was needed to identify vulnerabilites in multiple Computer Associates products, the Norton Ghost management service, and a common service exposed on the Mac OS X operating system.

Fuzzers are useful for much more than network protocols. In the first quarter of 2006, I collaborated on three different browser fuzzing tools, leading to the discovery of dozens of flaws across a wide range of web browsers. In the second quarter of 2006, I wrote an ActiveX fuzzer (AxMan) that discovered over 100 unique flaws across Microsoft products alone. Many of these flaws were profiled during the Month of Browser Bugs project and led to the development of exploit modules for the Metasploit Framework. I am still finding new vulnerabilities with AxMan, nearly a year after it was originally developed. Fuzzers truly are the gift that keeps on giving.

This book is the first resource to do justice to fuzzing as a technique. The knowledge provided in this book is everything you need to start fuzzing new products and to build effective fuzzing tools of your own. The key to effective fuzzing is knowing what data to use for which products, and the tools needed to manipulate, monitor, and manage the fuzzing process. The authors of this book are pioneers in the area of fuzzing techniques and do an excellent job of covering the intricacies of the fuzzing process.

Happy bug hunting!

—HD

Preface

“I know the human being and fish can coexist peacefully.”

—George W. Bush, Saginaw, Mich., Sept. 29, 2000

Introduction

The concept of fuzzing has been around for almost two decades but has only recently captured widespread attention. A plague of vulnerabilities affecting popular client-side applications, including Microsoft Internet Explorer, Microsoft Word, and Microsoft Excel, were seen in the year 2006 and a large portion of these vulnerabilities were discovered through fuzzing. This effective application of fuzzing technologies gave rise to new tools and increased exposure. The sheer fact that this is the first published book dedicated to the subject matter is an additional indicator that there is an increasing interest in fuzzing.

Having been involved in the vulnerability research community for years, we have used a variety of fuzzing technologies in our day to day work, ranging from immature hobby projects to high end commercial products. Each of the authors has been involved in the development of both privately held and publicly released fuzzers. We leveraged our combined experience and ongoing research projects to compose this bleeding edge book, which we hope you will find beneficial.

Intended Audience

Security books and articles are frequently written by security researchers for the benefit of other security researchers. We strongly believe that the quantity and severity of vulnerabilities will continue to grow so long as security is deemed to be the sole responsibility of a security team. As such, we have taken strong efforts to write for a large audience including both readers who are new to fuzzing and those who have already had significant exposure.

It is unrealistic to believe that secure applications can emerge from the development process if we simply hand completed applications to a security team for a quick audit prior to production launch. Gone are the days when a developer or a member of the QA Team can say, “security’s not my problem – we have a security team that worries about that”. Security must now be everyone’s problem. Security must be baked into the software development lifecycle (SDLC), not brushed on at the end.

Asking the development and QA teams to focus on security can be a tall order, especially for those that have not been asked to do so in the past. We believe that fuzzing presents a unique vulnerability discovery methodology that is accessible to a wide audience due to the fact that it can be highly automated. While we are hopeful that seasoned security researchers will gain valuable insights from this book, we are equally hopeful that it will be accessible to developers and QA teams. Fuzzing can and should be an integral part of any SDLC, not just at the testing phase, but also during development. The earlier a defect can be identified, the less costly it will be to remediate.

Prerequisites

Fuzzing is a vast subject. While we cover many non-fuzzing specific basics throughout the book, a number of assumptions regarding prior knowledge have been made. Readers should have at least a basic understanding of programming and computer networking prior to taking on this book. Fuzzing is all about automating security testing so naturally much of the book is dedicated to building tools. We have purposely selected multiple programming languages for these tasks. Languages were selected according to the task at hand, but this also demonstrates that fuzzing can be approached in numerous ways. It is certainly not necessary to have a background in all of the languages used, but having a language or two under your belt will go a long way in helping you to get the most from these chapters.

We detail numerous vulnerabilities throughout the book and discuss how they might have been identified through fuzzing. However, it is not our goal to define or dissect the nature of the vulnerabilities themselves. Many excellent books have been written which are dedicated to this topic. If you are looking for a primer on software vulnerabilities, Exploiting Software by Greg Hoglund and Gary McGraw, books from the Hacking Exposed series and The Shellcoder’s Handbook by Jack Koziol, David Litchfield, et al. are great references.

Approach

How to best leverage this book depends upon your background and intentions. If you are new to fuzzing, we would recommend digesting the book in a sequential manner as it has been intentionally laid out to provide necessary background information prior to moving onto more advanced topics. If however, you’ve already spent time using various fuzzing tools, don’t be afraid to dive directly into topics of interest as the various logical sections and chapter groupings are largely independent of one another.

Part I is designed to set the stage for the specific types of fuzzing that are discussed in the remainder of the book. If you’re new to the world of fuzzing, consider this to be required reading. Fuzzing can be used as a vulnerability discovery methodology for just about any target, but all approaches follow the same basic principles. In Part I, we seek to define fuzzing as a vulnerability discovery methodology and detail the knowledge that will be required regardless of the type of fuzzing which is conducted.

Part II focuses on fuzzing specific classes of targets. Each target is divided across two or three chapters. The first chapter provides background information specific to the target class and the subsequent chapters focus on automation, detailing the construction of fuzzers for that particular target. Two automation chapters are provided when separate tools are deemed necessary for the Windows and UNIX platforms. For example, consider the chapter triplet on “File Format Fuzzing” starting with Chapter 11 which details background information related to fuzzing file parsers. Chapter 12, “File Format Fuzzing: Automation on UNIX” details the actual programming of a UNIX-based file fuzzer and Chapter 13, “File Format Fuzzing: Automation on Windows” details the construction of a file format fuzzer designed to run in the Windows environment.

Part III tackles advanced topics in fuzzing. For readers who already have a strong knowledge of fuzzing it may be appropriate to jump directly into Part III, while most readers will likely want to spend time in Parts I and II before moving onto these topics. In Part III, we focus on emerging technologies that are just beginning to be implemented but will become critical for advanced vulnerability discovery tools that leverage fuzzing in the future.

Finally, in Part IV, we reflect on what we’ve learned throughout the book and then peer into the crystal ball to see where we’re headed in the future. While fuzzing is not a new concept, it still has plenty of room to grow, and we hope that this book will inspire further research in this space.

A Touch of Humor

Writing a book is serious work, especially a book on a complex subject like fuzzing. That said, we like to have fun as much as the next person (actually probably significantly more than the average person) and have made our best effort to keep the writing entertaining. In that spirit, we decided to open each chapter with a brief quotation from the 43rd President of the United States, George W. Bush (a.k.a. Dubya). No matter what your political affiliation or beliefs may be, no one can argue that Mr. Bush has cooked up many entertaining quotes over the years, enough to fill entire calendars[1] even! We’ve compiled some of our favorites to share with you and hope you find them as funny as we do. As you’ll see throughout the book, fuzzing can be applied against a variety of targets, evidently even the English language.

[1] http://tinyurl.com/33l54g

About the Cover

At times, vulnerabilities have at times been referred to as “fish.” (For example, see the thread on “The L Word & Fish”[2] from the DailyDave security mailing list.) This is a useful analogy that can be applied across the board when discussing security and vulnerabilities. A researcher can be called a fisherman. Reverse engineering the assembly code of an application, line by line, in search of a vulnerability may be referred to as “deep sea fishing.” In comparison to many other auditing tactics, fuzzing for the most part only scratches the surface and is highly effective at capturing the “easy” fish. In addition, the grizzly bear is a notable “fuzzy,” yet powerful animal. Combined, these are the main motivations behind our choice of cover art where the bear, representing a fuzzer, is shown capturing a fish, representing a vulnerability.

[2] http://archives.neohapsis.com/archives/dailydave/2004-q1/0023.html

Companion Website:www.fuzzing.org

The fuzzing.org website is an absolutely integral part of this book as opposed to a supplemental resource. In addition to housing errata that is sure to emerge post publication, the website will serve as the central repository for all source code and tools covered throughout the book. Over time, we intend to evolve fuzzing.org beyond a book-centric companion website into a valuable community resource with tools and information related to all fuzzing disciplines. We welcome your feedback in order to help make the site a valuable and open knowledgebase.

Acknowledgments

Group Acknowledgements

While only three names appear on the cover of the book, there was a significant supporting cast behind the scenes that was responsible for making this book a reality. First and foremost are friends and family that put up with many late nights and lost weekends. We collectively owe several beers, movies, and quiet evenings at home that were missed out on during this project but to those affected, fear not, those debts will be repaid in full. While we’ll miss our regular Thursday night book meetings, we recognize that others aren’t likely to miss them at all.

Peter DeVries once commented, “I love being a writer. What I can’t stand is the paperwork.” We couldn’t agree more. Coming up with the thoughts and ideas is only half the battle. Once the draft was laid out, a small army of reviewers joined the battle in an effort to convince the world that we could write a book. We would like to personally thank our technical editors who did their level best to point out our mistakes and challenge our assumptions. Most notably Charlie Miller, who went through great lengths to help make the book “cutting edge.” We also sincerely appreciate the effort that H.D. Moore put in reviewing the book and writing the foreword. We would also like to thank the team from Addison-Wesley that helped guide us through the process, including Sheri Cain, Kristin Weinberger, Romny French, Jana Jones, and Lori Lyons. Last but not least, a special thanks to our acquisitions editor, Jessica Goldstein, who was willing to take a chance on three guys with a crazy idea and the naive belief that writing a book couldn’t possibly be all that hard.

Michael’s Acknowledgements

I would like to take this opportunity to thank my wife Amanda for her patience and understanding throughout the writing of this book. We were planning a wedding throughout much of the writing process and there were far too many evenings and weekends spent poring over a computer screen which should have been spent enjoying a bottle of wine on the porch. I also sincerely appreciate the support given to me by all members of my family who encouraged me to pursue this project and actually believed that we could do it. Thanks also the iDefense Labs team and my coworkers at SPI Dynamics who supported and inspired me throughout the process. Finally, I want thank my co-authors for joining me on this journey, putting up with my sporadic GOYA speeches, motivating me to GOMOA and collectively producing a far stronger piece of work than I ever could have produced on my own.

Adam’s Acknowledgements

I would like to thank my family (especially my sister and parents), teachers and counselors at JTHS, Mark Chegwidden, Louis Collucci, Chris Burkhart, sgo, Nadwodny, Dave Aitel, Jamie Breiten, the Davis family, the Brothers Leondi, Reynolds, Kloub and AE, Lusardi, Lapilla and last and definitely least, Richard.

Pedram’s Acknowledgements

I would like to thank my co-authors for the opportunity to write this book and for keeping me motivated over the long course to completion. I extend my gratitude to Cody Pierce, Cameron Hotchkies and Aaron Portnoy, my team at TippingPoint, for their ingenuity and technical reviews. Thanks to Peter Silberman, Jamie Butler, Greg Hoglund, Halvar Flake and Ero Carrera for inspiration and providing non-stop entertainment. Special thanks to David Endler, Ralph Schindler, Sunil James and Nicholas Augello, my “brothers from other mothers,” for always being available to lean on. Finally, a heartfelt thanks to my family for being patient during my absence to complete this book.

About the Authors

Michael Sutton

Michael Sutton is the Security Evangelist for SPI Dynamics. As Security Evangelist, Michael is responsible for identifying, researching, and presenting on emerging issues in the web application security industry. He is a frequent speaker at major information security conferences, has authored numerous articles, and is regularly quoted in the media on various information security topics. Michael is also a member of the Web Application Security Consortium (WASC), where he is project lead for the Web Application Security Statistics project.

Prior to joining SPI Dynamics, Michael was a Director for iDefense/VeriSign, where he headed iDefense Labs, a team of world class researchers tasked with discovering and researching security vulnerabilities. Michael also established the Information Systems Assurance and Advisory Services (ISAAS) practice for Ernst & Young in Bermuda. He holds degrees from the University of Alberta and The George Washington University.

Michael is a proud Canadian who understands that hockey is a religion and not a sport. Outside of the office, he is a Sergeant with the Fairfax Volunteer Fire Department.

Adam Greene

Adam Greene is an engineer for a large financial news company based in New York City. Previously, he served as an engineer for iDefense, an intelligence company located in Reston, VA. His interests in computer security lie mainly in reliable exploitation methods, fuzzing, and UNIX-based system auditing and exploit development.

Pedram Amini

Pedram Amini currently leads the security research and product security assessment team at TippingPoint. Previously, he was the assistant director and one of the founding members of iDefense Labs. Despite the fancy titles, he spends much of his time in the shoes of a reverse engineer—developing automation tools, plug-ins, and scripts. His most recent projects (a.k.a. “babies”) include the PaiMei reverse engineering framework and the Sulley fuzzing framework.

In conjunction with his passion, Pedram launched OpenRCE.org, a community website dedicated to the art and science of reverse engineering. He has presented at RECon, BlackHat, DefCon, ShmooCon, and ToorCon and taught numerous sold out reverse engineering courses. Pedram holds a computer science degree from Tulane University.

Part I. Background

Chapter 1: Vulnerability Discovery Methodologies

Chapter 2: What Is Fuzzing?

Chapter 3: Fuzzing Methods and Fuzzer Types

Chapter 4: Data Representation and Analysis

Chapter 5: Requirements for Effective Fuzzing

1. Vulnerability Discovery Methodologies

“Will the highways of the Internet become more few?”

—George W. Bush, Concord, N.H., January 29, 2000

Ask any accomplished security researcher how he discovers vulnerabilities and you’re likely to get a multitude of answers. Why? There are a variety of approaches, each with its own advantages and disadvantages. No one approach is correct and no single method can uncover all possible vulnerabilities for a given target. At a high level, there are three primary approaches to discovering security vulnerabilities: white box, black box, and gray box testing. The differences among these approaches can be determined by the resources to which you, as the tester, have access. At one extreme, the white box approach requires complete access to all resources. This includes access to source code, design specifications, and perhaps even the programmers themselves. On the other extreme, the black box approach requires little to no knowledge of internals and is limited to blind testing for the most part. Pen testing a remote Web application with no access to source code is a good example of black box testing. Sitting in the middle is gray box testing, the definition of which varies depending on who you ask. For our purposes, gray box testing requires, for example, that you have access to compiled binaries and perhaps some basic documentation.

In this chapter we explore various high- and low-level approaches for vulnerability discovery, starting with white box testing, which you might have otherwise heard referred to as clear, glass, or translucent box testing. We then define black box and gray box testing, which would include fuzzing. We look at the pros and cons of each, as this will provide the necessary background when focusing exclusively on fuzzing throughout the remainder of the book. Fuzzing is only one approach to vulnerability discovery and it is important to recognize where alternate approaches might be more practical.

White Box Testing

Fuzzing as a testing methodology falls mostly in the realm of black and gray box testing. However, we start by examining a common alternate approach to vulnerability discovery used by software developers known as white box testing.

Source Code Review

A source code review can be accomplished either manually or with the assistance of automation tools. Given that computer programs are commonly comprised of tens to hundreds of thousands of lines of code, a pure manual review is generally impractical. Automated tools are an invaluable resource that will reduce the tedious task of poring over individual lines of code but can only identify potentially vulnerable or suspicious code segments. Human analysis is required to determine if detected issues are indeed valid.

There are a multitude of hurdles that source code analysis tools must overcome to produce useful results. Dissecting these various complex issues is beyond the scope of this book, but consider the following C language code sample, which simply copies the word test into a 10-byte character array:

Next, consider the same code sample, which has been modified to allow user input to be copied into the character array.

Both code segments use the strcpy() routine to copy data into a stack-based buffer. The usage of strcpy() is generally discouraged in C/C++ programming due to its lack of bounds checking on the buffer to which data is being copied. As a result, if the programmer is not careful to add his or her own checks, an overflow can occur, placing data outside of the bounds of the intended container. The first example will not cause a buffer overflow because the size of the string “test” (including the terminating null byte) is and always will be 5, and is therefore smaller than the 10-byte buffer into which it is being copied. The second scenario might or might not cause a buffer overflow, depending on the size of the user-supplied argument on the command line. The key here is whether or not the user has control over the input provided to the vulnerable function. A rudimentary code review would flag the strcpy() line in both code samples as being potentially vulnerable. However, tracing of input values is required to understand if an exploitable condition truly exists. This is not to say that source code reviews cannot be valuable tools for security researchers. Source code reviews should be performed whenever the code is available. However, depending on your role and perspective, it is common not to have access to this level of detail.

People often incorrectly assume that white box testing is more effective than black box testing. What view of software can be better or more complete than access to the source code? Keep in mind, however, that what you see is not necessarily what you execute when it comes to source code. The software build process can make drastic changes during the conversion of source code to assembly code. This, among other reasons, is why it isn’t possible to state that one testing approach is necessarily better than another. They are simply different approaches that will generally uncover different types of vulnerabilities. For complete coverage, it is necessary to combine multiple approaches.

Microsoft Source Code Leak

To defend the claim that a source code review is not superior to black box testing, consider an event that occurred in February 2004. Without warning, archives of code began to circulate on the Internet that were rumored to contain large excerpts of source for the Microsoft Windows NT 4.0 and Windows 2000 operating systems. Microsoft later confirmed that the archives were indeed genuine. Many corporations were extremely nervous that this leak would quickly lead to a flood of vulnerabilities in the two popular operating systems. That didn’t happen. In fact, to this day we can attribute only a handful of vulnerabilities to the leaked source code. Among that short list of vulnerabilities is CVE-2004-0566, which details an integer overflow that could be triggered when rendering bitmap files.[1] Interestingly, Microsoft disputed the discovery, claiming that the software company had already uncovered the issue during an internal audit.[2] Why didn’t we see a flood of vulnerabilities? Shouldn’t access to source code reveal all? The truth is that a source code review, although a very important component of an application or operating system security audit, can also be difficult to perform due to the size and complexity of the code. Furthermore, disassembly analysis techniques can cover much of the same ground. For example, take a look at the TinyKRNL[3] and ReactOS[4] projects, both of which aim to provide Microsoft Windows kernel and operating system compatibility. The developers of these projects didn’t have access to the Microsoft kernel source code and yet were able to create projects that at least to some extent, provide a compatible Windows environment. When auditing the Windows operating system, you won’t likely have access to the Windows source code either, but the source code for these projects can be used as a guide when interpreting the Windows disassembly.

[1] http://archives.neohapsis.com/archives/fulldisclosure/2004-02/0806.html

[2] http://news.zdnet.com/2100-1009_22-5160566.html

[3] http://www.tinykrnl.org/

[4] http://www.reactos.org/

Tools and Automation

Source code analysis tools generally fall into one of three categories—compile time checkers, source code browsers, or automated source code auditing tools. Compile time checkers look for vulnerabilities as source code is compiled. The tools are generally integrated with compilers but attempt to identify security-specific issues as opposed to problems with application functionality. The /analyze compiler option in Microsoft Visual C++ is an example of a compile time checker.[5] Microsoft also provides PREfast for Drivers,[6] which can detect various classes of vulnerabilities specific to driver development that might not be detected by the compiler.

[5] http://msdn2.microsoft.com/en-us/library/k3a3hzw7.aspx

[6] http://www.microsoft.com/whdc/devtools/tools/PREfast.mspx

Source code browsers are tools designed to assist in the manual exploration and review of source code. This class of tools allows the reviewer to apply advanced searches across the code as well as enumerate and navigate cross-references between locations. For example, a reviewer might use such a tool to locate all uses of the strcpy() call in an effort to identify potential buffer overflow vulnerabilities. Cscope[7] and Linux Cross-Reference[8] are popular source code browsers.

[7] http://cscope.sourceforge.net/

[8] http://lxr.linux.no/

Automated source code auditing tools are designed to scan source code and automatically identify potential areas of concern. As with most security tools, automated source code auditing tools are available as both commercial and freeware solutions. Moreover, the tools tend to focus on specific programming languages so multiple tools might be required if your target is built using different programming languages. On the commercial front, products exist from vendors such as Fortify,[9] Coverity,[10] KlocWork,[11] GrammaTech,[12] and others. Table 1.1 provides a list of some popular freeware tools, the languages they audit, and the platforms they support.

[9] http://www.fortifysoftware.com/

[10] http://www.coverity.com/

[11] http://www.klocwork.com/

[12] http://www.grammatech.com/

Table 1.1. Freeware Source Code Auditing Tools

It is important to keep in mind that no automation tool can ever replace the skills of an experienced security researcher. They are simply tools that streamline the overwhelming task of digesting thousands of lines of source code and assist in saving time and frustration. The reports generated by such tools must still be reviewed by an experienced analyst to identify false positives, and by developers to actually implement a fix. Consider, for example, the following sample output generated by the Rough Auditing Tool for Security (RATS) across the contrived vulnerable example code shown earlier in the chapter. RATS points out two potential security issues. It highlights the fact that a fixed buffer was used and that strcpy() is potentially unsafe. It does not, however, definitively state that a vulnerability exists. It only draws the attention of the user to potentially unsafe code regions and relies on him or her to determine if the code is indeed unsafe.

Pros and Cons

As mentioned previously, there is no single correct approach to discovering security vulnerabilities. So how does one choose an appropriate methodology? Well sometimes the decision is made for us. White box testing, for example, is not possible if we do not have access to the source code of the target. This is the case for most security researchers and end users, especially those who are dealing with commercial software in the Microsoft Windows environment. What are the advantages of white box testing?

- Coverage. Due to the fact that all source code is available, a code review allows for complete coverage. All possible code paths can be audited for potential vulnerabilities. This can, of course, lead to false positives as code paths might not be reachable during code execution.

Code reviews are not always possible. Even when they can be conducted, they should be combined with other vulnerability discovery methodologies. Source code analysis has the following shortcomings.

- Complexity. Source code analysis tools are imperfect and produce false positives. Therefore, the error reports produced by such tools are not an end game. They must still be reviewed by experienced programmers to identify issues that represent legitimate security vulnerabilities. Because significant software projects typically contain hundreds of thousands of lines of code, the reports can be lengthy and require significant time to wade through.

- Availability. Source code is not always available. Although many UNIX projects are open source and allow for source code to be reviewed, this situation is relatively rare in a Win32 environment and generally nonexistent when dealing with commercial software. Without access to source code, this form of white box testing is not even an option.

Black Box Testing

Black box testing implies that you only have knowledge of what you can observe. You as the end user control the input that goes into the black box and you can observe the output that emerges from the other end, but you do not have knowledge of the inner workings of your target. This situation is most commonly found when remotely accessing Web applications and Web services. You can craft inputs in the form of Hypertext Markup Language (HTML) or Extensible Markup Language (XML) requests and observe the generated Web page or return value, respectively, but have no idea what is going on under the hood.

As another example consider that whenever you purchase an application such as Microsoft Office, you generally receive a precompiled binary application, not the source code that was used to build it. Your perspective in this situation will determine the shade of box color for the testing approach. If you do not intend to apply reverse engineering techniques, you will be effectively testing the software in a black box. Otherwise, you will be applying a gray box approach, discussed in the next section.

Manual Testing

Sticking with Web applications as an example, manual testing could involve using a standard Web browser to explore a Web site hierarchy while tediously inserting potentially dangerous inputs throughout observed areas of interest. During the most nascent stages of auditing, this technique might be applied sporadically, for example, by adding single quotes to various parameters in hopes of uncovering a SQL injection vulnerability.

Manually testing applications for vulnerabilities without the aid of automated tools is not generally a practical approach (unless your firm hires a giant horde of interns). One scenario in which it can be very beneficial is when it is used for sweeping multiple applications for a similar vulnerability. Sweeping takes advantage of occurrences where numerous programmers make the same mistakes in different projects. For example, perhaps a buffer overflow is found in a particular Lightweight Directory Access Protocol (LDAP) server and testing that same exploit vector against other LDAP servers reveals that they are also vulnerable. Given that programs often share code or the same programmers work on multiple projects, this is not an uncommon occurrence.

Sweeping

CreateProcess() is a function exposed through the Microsoft Windows application programming interface (API). As the name implies, CreateProcess() will start a new process and its primary thread.[13] The prototype of the function is shown here:

[13] http://msdn2.microsoft.com/en-us/library/ms682425.aspx

It is known and documented behavior that if the lpApplicationName parameter is specified as a NULL value, then the process that will be launched is the first white space delimited value in the lpCommandLine parameter. Consider, for example, this call to CreateProcess():

In this situation, CreateProcess() will iteratively try to launch each of the following space-delimited values.

c:\program.exe
c:\program files\sub.exe
c:\program files\sub dir\program.exe

This will continue until an executable is found or all possibilities have been exhausted. Therefore, if a program.exe executable were placed in the c:\ directory, applications with insecure calls to CreateProcess() with the aforementioned structure would execute program.exe. This provides attackers with a handy trick for trying to get a file executed when execute permissions are out of reach.

In November 2005, a security advisory[14] was issued identifying several popular applications that utilized insecure calls to CreateProcess(). The discoveries resulted from a successful and very simple sweeping exercise. If you’d like to sweep for the same vulnerabilities, copy and rename a simple application such as notepad.exe and place it in the c:\ directory. Now use the machine as you normally would. If the copied application suddenly launches unexpectedly, you’ve likely uncovered an insecure call to CreateProcess().

[14] http://labs.idefense.com/intelligence/vulnerabilities/display.php?id=340

Automated Testing or Fuzzing

Fuzzing, for the most part, is a brute force technique and what it lacks in elegance, it makes up for in simplicity and effectiveness. In Chapter 2, “What Is Fuzzing?” we define and dissect the term in full detail. In a nutshell, fuzzing consists of throwing everything but the kitchen sink at a target and monitoring the results. Most software is designed to work with specific inputs but should be robust enough to gracefully recover from situations where abnormal inputs are received. Consider the simple Web form depicted in Figure 1.1.

Figure 1.1. Simple Web form

It is fair to assume that the Name field should receive a string value and that the Age field should receive an integer. What will happen if the user accidentally reverses the input values and plugs a string into the age field? Will the string value be automatically converted to an integer based on the ASCII values of the characters? Will an error message be displayed? Will the application crash? Fuzzing seeks to answer these questions through an automated process. The researcher requires no knowledge about the internal workings of the application and is therefore conducting a black box test. You are standing back, throwing rocks at the target, and waiting to hear a window break. In this sense, fuzzing falls into the black box category. However, throughout the book we’ll demonstrate how brute force fuzzing can be made more surgical to ensure that the rock flies straight and true every time; therefore fuzzing also applies in the gray box category.

Does Microsoft Fuzz?

The answer is yes. The Trustworthy Computing Security Development Lifecycle document[15] (SDL) published by Microsoft in March 2005 makes it clear that fuzzing is considered by Microsoft to be a key tool for identifying security vulnerabilities before software is released. The SDL was an initiative to embed security within the software development lifecycle, making security the responsibility of everyone participating in the development process. Fuzzing is mentioned in the SDL as a class of security testing tools that should be leveraged during the implementation phase. The document actually states that “heavy emphasis on fuzz testing is a relatively recent addition to the SDL, but results to date are very encouraging.”

[15] http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnsecure/html/sdl.asp

Pros and Cons

Black box testing, although not always the best approach, is always an option. Advantages of black box testing include the following:

- Availability. Black box testing is always applicable and even in situations when source code is available, black box testing can still be beneficial.

- Reproducibility. Because black box testing makes no assumptions about the target, a black box test against one File Transfer Protocol (FTP) server, for example, can be easily repurposed to test any other FTP server.

- Simplicity. Although approaches such as reverse code engineering (RCE) require specialized skills, pure black box testing at its most basic level can be conducted without a strong knowledge of the application internals. However, in reality, whereas basic denial of service vulnerabilities can be found simply through the use of automated testing tools, a deeper knowledge is generally required to determine if a simple application crash can be expanded into something more interesting such as code execution.

Despite the accessibility of black box testing, it does have some shortcomings. The disadvantages of black box testing include the following:

- Coverage. One of the biggest challenges with black box testing is determining when to stop testing and how effective the testing has been. We address this issue in greater detail in Chapter 23, “Fuzzer Tracking.”

- Intelligence. Black box testing is best suited to scenarios in which a vulnerability is caused by an individual input vector. Complex attacks might, however, require multiple attack vectors, some of which place the target application into a vulnerable state and others that trigger exploitation. Attacks such as these require a strong understanding of the underlying application logic and will typically only be uncovered with manual source code audits and RCE.

Gray Box Testing

Floating in between white and black box analysis, we define gray box testing to include black box auditing plus the additional insights offered through reverse engineering (RE), also known as reverse code engineering (RCE). Source code is an invaluable resource that is reasonably easy to read and provides a strong understanding of how specific functionality operates. Additionally, it communicates the inputs that specific functionality expects and the output that the same functionality can be expected to generate. Not all is lost in the absence of this great resource. Analysis of the compiled assembly instructions can help unfold a similar story, albeit with increased efforts. Security evaluation at the assembly as opposed to source code level is typically referred to as binary auditing.

Binary Auditing

RCE is often used synonymously with the phrase binary auditing, but for our purposes we treat RCE as a subcategory to distinguish it from fully automated methods. The ultimate goal of RCE is to determine the underlying functionality of a compiled binary application. Although it is not possible to convert a binary file back into its original source code representation, it is possible to reverse engineer sequences of assembly instructions into a format that lies between the original source code and the machine code that makes up the binary file(s). Generally, this middle ground is a combination of assembly language and graphical representations of the flow of code within the application.

Once the binary file has been converted to a human-readable form, the code can then be reviewed for locations that could potentially contain vulnerabilities in much the same way as a source code review. As with a source code review, locating potentially vulnerable code segments is not the end game. It is also necessary to determine if an end user can influence the vulnerable code segment. Following this logic, binary auditing can be referred to as an inside-out technique: The researcher first identifies an interesting line deep within the disassembly and then traces it backward to determine if the vulnerability is exploitable.

Reverse engineering is a surgical technique that employs tools such as disassemblers, decompilers, and debuggers. Disassemblers parse illegible machine code into some flavor of assembly language suitable for digestion by a human. Various freeware disassemblers are available but for serious RCE work you will likely want to invest in a copy of DataRescue’s Interactive Disassembler (IDA) Pro,[16] shown in Figure 1.2. IDA is a commercial disassembler that runs on Windows, UNIX, and MacOS platforms and is capable of dissecting binaries from a wide range of architectures.

[16] http://www.datarescue.com/

Figure 1.2. DataRescue IDA Pro

Similar to a disassembler, a decompiler statically analyzes and converts binary code into a human-readable format. Instead of directly translating to assembly instructions, a decompiler attempts to produce higher level language constructs such as conditionals and loops. Decompilers are not capable of recovering the original source code because information that was contained in the source code such as comments, variable names, function names, and even basic structure is not retained when source code is compiled. Decompilers for languages that compile to machine code (e.g., C and C++) tend to have significant limitations and are mostly experimental in nature. Boomerang[17] is an example of a decompiler for machine code. Decompilers are more common for languages that compile to some intermediate form of byte code such as C#, as more detail is retained in the compiled code and decompilation is therefore generally more successful.

[17] http://boomerang.sourceforge.net/

Unlike disassemblers and decompilers, debuggers apply dynamic analysis by opening or attaching to a target program and monitoring its execution. A debugger can display the contents of CPU registers and the state of memory while the application is running. Popular debuggers for the Win32 platform include OllyDbg,[18] a screen shot of which is shown in Figure 1.3, and Microsoft WinDbg (pronounced “wind bag”).[19] WinDbg is part of the Debugging Tools for Windows[20] package and is available as a free download from Microsoft. OllyDbg is a shareware debugger developed by Oleh Yuschuk that is a bit more user friendly than WinDbg. Both debuggers allow for the creation of custom extensions and numerous third-party plug-ins are available to extend OllyDbg’s functionality.[21] Various debuggers exist for the UNIX environment, with the GNU Project Debugger[22] (GDB) being the most popular and portable. GDB is a command-line debugger that is included with many UNIX/Linux distributions.

[18] http://www.ollydbg.de/

[19] http://www.openrce.org/forums/posts/4

[20] http://www.microsoft.com/whdc/devtools/debugging/default.mspx

[21] http://www.openrce.org/downloads/browse/OllyDbg_Plugins

[22] http://www.gnu.org/software/gdb/gdb.html

Figure 1.3. OllyDbg

Automated Binary Auditing

There are a handful of tools emerging that attempt to automate the process of RCE in an effort to identify potential security vulnerabilities in binary applications. The primary applications include both commercial and freeware varieties and are either IDA Pro plug-ins or freestanding applications. Table 1.2 lists a handful of these.

Table 1.2. Automated Binary Auditing Tools

Pros and Cons

As mentioned, gray box testing is somewhat of a hybrid solution that incorporates traditional black box testing with insights gained from RCE efforts. As with other approaches, gray box testing has advantages and disadvantages. Advantages of gray box testing include the following:

- Availability. With the exception of remote Web services and applications, binary versions of software are always available.

- Coverage. Information gleaned through gray box analysis can be utilized to assist and improve otherwise pure black box fuzzing techniques.

The disadvantages of black box testing include the following:

- Complexity. RCE is a specialized skill set and therefore resources might not be available to apply this approach.

Summary

At the highest level, vulnerability discovery methodologies can be divided into white, black, and gray box testing. The resources made available to the tester determine the distinction among the three. White box testing makes all possible resources including source code available, whereas black box testing provides access only to the inputs and observed outputs. Sitting between the two, gray box testing provides additional information over black box analysis through RCE of available binaries.

White box testing involves various approaches to source code analysis. This can be accomplished manually or by leveraging automated tools such as compile time checkers, source code browsers, or automated source code auditing tools.

When conducting black box testing, source code is not available. Fuzzing via black box testing is considered blind. Inputs are generated and responses are monitored but no details regarding the internal state of the target are available for analysis. Fuzzing via gray box testing is similar to the black box approach with the addition of augmented data from RCE efforts. Fuzzing attempts to repeatedly provide an application with unexpected input and simultaneously monitor for exceptions that might result. The remainder of this book focuses on fuzzing as an approach to discovering security vulnerabilities.

2. What Is Fuzzing?

“They misunderestimated me.”

—George W. Bush, Bentonville, Ark., November 6, 2000

The term fuzzing does not exist in mainstream vocabulary, has many aliases, and might be entirely new to some readers. Fuzzing is a broad field and an exciting approach toward software security analysis. Throughout this book we dive into the specifics of various fuzzing aspects and targets. Before doing so, we begin in this chapter with a definition for the term, explore the history of fuzzing, examine the individual phases of a complete fuzzing audit, and conclude with the limitations of fuzz testing.

Definition of Fuzzing

Look up fuzzing in your dictionary and you’re not likely to find anything that will help you to define the term as it is used by security researchers. The first public mention of fuzzing came from a University of Wisconsin-Madison research project, and the term has since been adopted to describe an entire methodology for software testing. In the academic world, fuzzing can be most closely related to boundary value analysis (BVA),[1] where you look at the range of known good values for a particular input and create test values that straddle the boundary cases of known good and bad values. The results of the BVA can help to ensure that exception handling appropriately filters out unwanted values while allowing the full range of acceptable inputs. Fuzzing is similar to BVA, but when fuzzing, we are not solely focused on boundary values, but additionally any inputs that can trigger undefined or insecure behavior.

[1] http://en.wikipedia.org/wiki/Boundary_value_analysis

For the purposes of this book we define fuzzing as a method for discovering faults in software by providing unexpected input and monitoring for exceptions. It is typically an automated or semiautomated process that involves repeatedly manipulating and supplying data to target software for processing. This is, of course, a very generic definition, but it captures the basic concept of fuzzing. All fuzzers fall into one of two categories: mutation-based fuzzers, which apply mutations on existing data samples to create test cases, and generation-based fuzzers, which create test cases from scratch by modeling the target protocol or file format. Both methods carry pros and cons. In Chapter 3, “Fuzzing Methods and Fuzzer Types,” we further categorize fuzzing methodologies and discuss benefits and pitfalls.

If you are new to fuzzing, consider the analogy of breaking into a house. Assume that you failed in your current career and have turned to a life of crime. If you were taking a pure white box approach to breaking into a home, you would have full access to all information about the home prior to breaking in. This might include blueprints, a list of lock manufacturers used, details of the construction materials used in building the home, and more. Although this approach provides some distinct advantages, it is not foolproof or without disadvantages. With this method you are statically analyzing the design of the home as opposed to examining it at runtime, during the actual break-in. Say, for example, you decide during your research that the side living room window represents a weak point that could be smashed to gain entry. You might not, however, anticipate the presence of the angry owner cradling a shotgun and waiting for you on the inside. On the other hand, if you were applying a pure black box testing method to breaking in, you might approach the home under the cover of darkness and quietly test all of the doors and windows, peering into the house to determine what the best point of entry is. Finally, if you chose to use fuzzing to break into the home, you might dispense with researching the blueprints or manually testing the locks. You could simply automate the process by picking up a gun and blowing your way into the home—brute force vulnerability discovery!

History of Fuzzing

The earliest reference to fuzzing of which we are aware dates back to 1989. Professor Barton Miller (considered by many to be the “father” of fuzzing) and his Advanced Operating Systems class developed and used a primitive fuzzer to test the robustness of UNIX applications.[2] The focus of the testing was not necessarily to assess the security of the system, but rather the overall code quality and reliability. Although security considerations were mentioned in passing throughout the study, no particular emphasis was placed on setuid applications during testing. In 1995, this testing was repeated with an expanded set of UNIX utilities and operating systems being tested. The 1995 study found an overall improvement in application reliability, but still noted “significant rates of failure.”

[2] http://www.cs.wisc.edu/~bart/fuzz/

The fuzz testing method employed by Miller’s team was very crude. If the application crashed or hung, it had failed the test. If it did not, it had succeeded. It accomplished this by simply throwing random strings of characters at target applications, a pure black box approach. Although this might seem overly simplistic, keep in mind that the concept of fuzzing was relatively unheard of at the time.

Around 1999, work began at the University of Oulu on their PROTOS test suite. Various PROTOS test suites were developed by first analyzing protocol specifications and then producing packets that either violated the specification or were deemed likely not to be handled properly by specific protocol implementation. Producing such test suites took considerable effort up front, but once produced, the test suites could be run against multiple vendor products. This is an example of a mixed white and black box approach and marked an important milestone in the evolution of fuzzing due to the large number of faults that were uncovered using this process.

In 2002 Microsoft provided funding to the PROTOS initiative[3] and in 2003 members of the PROTOS team launched Codenomicon, a company dedicated to the design and production of commercial fuzz testing suites. The product today is still based on the original Oulu test suite but includes a graphical user interface, user support, and fault detection through a health-checking feature, among other things.[4] More information on Codenomicon and other commercial fuzzing solutions is presented in Chapter 26, “Looking Forward.”

[3] http://www.ee.oulu.fi/research/ouspg/protos/index.html

[4] http://www.codenomicon.com/products/features.shtml

As PROTOS matured in 2002, Dave Aitel released an open sourced fuzzer named SPIKE[5] under the GNU General Public (GPL) license. Aitel’s fuzzer implements a block-based approach[6] intended for testing network-enabled applications. SPIKE takes a more advanced approach than Miller’s fuzzer, most notably including the ability to describe variable-length data blocks. Additionally, SPIKE can not only generate random data, but also bundles a library of values that are likely to produce faults in poorly written applications. SPIKE also includes predefined functions capable of producing common protocols and data formats. Among them are Sun RPC and Microsoft RPC, two communication technologies that have been at the heart of many past vulnerabilities. As the first publicly available framework allowing users to effortlessly create their own fuzzers, the release of SPIKE marked a significant milestone. This framework is mentioned a number of times throughout the book including in Chapter 21, “Fuzzing Frameworks.”

[5] http://immunityinc.com/resources-freesoftware.shtml

[6] http://www.immunityinc.com/downloads/advantages_of_block_based_analysis.html

Around the same time as the initial release of SPIKE, Aitel also released a local UNIX fuzzer named sharefuzz. In contrast to Miller’s fuzzer, sharefuzz targets environment variables as opposed to command-line arguments. Sharefuzz also employs a useful technique to facilitate the fuzzing process. It uses shared libraries to hook function calls that return environment variable values to return long strings as opposed to the actual values in an effort to reveal buffer overflow vulnerabilities.

The majority of fuzzing innovations following the release of SPIKE came in the form of tools for different specific classes of fuzzing. Michal Zalewski[7] (a.k.a. lcamtuf) drew attention to Web browser fuzzing in 2004 with the release of mangleme,[8] a Common Gateway Interface (CGI) script designed to continually produce malformed HTML files that are repeatedly refreshed within a targeted Web browser. Other fuzzers designed to target Web browsers soon followed. H.D. Moore and Aviv Raff produced Hamachi[9] to fuzz Dynamic HTML (DHTML) implementation flaws and the two later teamed up with Matt Murphy and Thierry Zoller to produce CSSDIE,[10] a fuzzer that targets cascading style sheet parsing.

[7] http://lcamtuf.coredump.cx/

[8] http://lcamtuf.coredump.cx/mangleme/mangle.cgi

[9] http://metasploit.com/users/hdm/tools/hamachi/hamachi.html

[10] http://metasploit.com/users/hdm/tools/see-ess-ess-die/cssdie.html

File fuzzing came into vogue in 2004. That year Microsoft released security bulletin MS04-028 detailing a buffer overrun in the engine responsible for processing JPEG files.[11] Although this was not the first discovered file format vulnerability, it attracted attention due to the number of popular Microsoft applications that shared the vulnerable code. File format vulnerabilities also presented a unique challenge for those tasked with protecting networks. Although a surprising number of similar vulnerabilities would emerge in the following years, it was not realistic to simply block potentially vulnerable file types from entering a corporate network. Images and media files comprise a significant portion of Internet traffic. How exciting could the Web be without images? Moreover, the majority of the vulnerabilities that would soon plague Microsoft related to Microsoft Office document files—file types critical to virtually all businesses. File format vulnerabilities turned out to be a prime candidate for mutation-based fuzzing as samples are readily available and can be mutated in rapid succession while monitoring the target application for faults. We presented at the Black Hat USA Briefings in 2005[12] and released a series of both mutation- and generation-based tools designed to fuzz file formats including FileFuzz, SPIKEfile, and notSPIKEfile.[13]

[11] http://www.microsoft.com/technet/security/bulletin/MS04-028.mspx

[12] http://www.blackhat.com/presentations/bh-usa-05/bh-us-05-sutton.pdf

[13] http://labs.idefense.com/software/fuzzing.php

In 2005, a company named Mu Security began development of a hardware fuzzing appliance designed to mutate protocol data as it traverses a network.[14] The emergence of this commercial vendor coincides with a present trend indicating heightened interest in fuzz testing. We are beginning to see increasing availability of commercial fuzzing solutions alongside the evolution of freely available fuzzing technologies. Additionally, a large community of developers and security researchers interested in fuzzing now exists, as evident with the creation of the Fuzzing mailing list,[15] maintained by Gadi Evron. Only time will tell what exciting innovations await us.

[14] http://www.musecurity.com/products/overview.html

[15] http://www.whitestar.linuxbox.org/mailman/listinfo/fuzzing

ActiveX fuzzing became a popular target in 2006 when David Zimmer released COMRaider and H.D. Moore published AxMan.[16] Both tools focused on ActiveX controls that could be instantiated by Web applications when accessed with the Microsoft Internet Explorer Web browser. Remotely exploitable vulnerabilities in such applications represent a high risk due to the large user base. ActiveX controls, as it turns out, are an excellent fuzzing target due to the fact that they include descriptions of the interfaces, function prototypes, and member variables within the actual control, allowing for intelligent automated testing. ActiveX and browser fuzzing on a whole are studied in further detail in Chapter 17, “Web Browser Fuzzing,” and Chapter 18, “Web Browser Fuzzing: Automation.”

[16] http://metasploit.com/users/hdm/tools/axman/

There are many other milestones and markers in the history of fuzzing, but what has been provided thus so far suffices in painting the overall picture. A graphical representation of the brief history of fuzzing is given in Figure 2.1.

Figure 2.1. Fuzzing history

Despite the advances made thus far, fuzzing remains a technology in its infancy. The majority of tools to date are relatively small projects maintained by small groups of individuals or even a single programmer. It has only been in the past couple of years that early-stage startups have entered the commercial space. Although this lends credibility to fuzzing as a field on its own, it is also an indication that fuzzing will see many further innovations and reach new milestones in the coming years as increased funding is made available for research.

In the next section, we cover the various phases involved in conducting a complete fuzzing audit.

Fuzzing Phases

Depending on various factors, the fuzzing approach chosen can vary greatly. There is no correct approach to fuzzing. It is entirely dependent on the target application, the skills of the researcher, and the format of the data being fuzzed. However, no matter what you are fuzzing or what approach you decide on, the same basic phases always apply.

1. Identify target. It isn’t possible to select a fuzzing tool or technique until we have a target in mind. If you are fuzzing an internally developed application during a security audit, target selection will be taken care of for you. If, however, you are conducting vulnerability research to uncover vulnerabilities in third-party applications, you’ll have some flexibility. When identifying a target, look at a vendor’s past history with regard to previously discovered vulnerabilities. Check vulnerability aggregation sites such as SecurityFocus[17] or Secunia.[18] A vendor with a poor track record for past vulnerabilities is more than likely to have poor coding practices that will ultimately lead to the discovery of further vulnerabilities. Beyond selecting an application, it might also be necessary to target a specific file or library within the application. If that’s the case, you might want to look for binaries that are shared across multiple applications, as vulnerabilities in such targets will be of higher risk due to the expanded user base.

2. Identify inputs. Virtually all exploitable vulnerabilities are caused by applications accepting user input and processing that data without first sanitizing it or applying validation routines. Enumerating input vectors is pivotal to the success of fuzzing. Failing to locate potential sources of input or the expected input values can severely limit testing. Apply lateral thinking when looking for input vectors. Whereas some input vectors are obvious, others are subtler. In the end, anything sent from the client to the target should be considered an input vector. That includes headers, filenames, environment variables, registry keys, and so on. All should be considered input vectors and are therefore potential fuzz variables.

3. Generate fuzzed data. Once input vectors have been identified, fuzz data must be generated. The decision to use predetermined values, mutate existing data, or generate data dynamically will depend on the target and data format. Regardless of the approach selected, automation should be applied to this process.

4. Execute fuzzed data. This step goes hand in hand with the previous one and is where fuzzing becomes a verb. Execution could involve the act of sending a data packet to the target, opening a file, or launching a target process. Again, automation is crucial. Without it, we’re not really fuzzing.

5. Monitor for exceptions. A vital but often overlooked step during fuzzing is the exception or fault monitoring process. Transmitting 10,000 fuzz packets to a target Web server, for example, and ultimately causing that server to crash is a useless endeavor if we are unable to pinpoint the packet responsible for the crash. Monitoring can take many forms and will be dependent on the target application and type of fuzzing being used.

6. Determine exploitability. Once a fault is identified, depending on the goals of the audit, it might also be necessary to determine if the uncovered bug can be further exploited. This is typically a manual process that requires specialized security knowledge. It might therefore be a step performed by someone other than the person conducting the initial fuzzing.

[17] http://www.securityfocus.com/

[18] http://secunia.com/

A graphical representation of the fuzzing phases is shown in Figure 2.2.

Figure 2.2. Fuzzing phases

All of the phases should be addressed regardless of the type of fuzzing that is being conducted, with the possible exception of determining exploitability. The order of the phases and emphasis placed on each can be altered depending on the goals of the researcher. Although powerful, fuzzing is by no means going to uncover 100 percent of the bugs in any given software target. In the next section we outline some bug classes that are likely to fly under the radar.

Fuzzing Limitations and Expectations

Fuzzing by its nature lends itself to locating certain types of weaknesses in a target. It also has particular limitations in the types of vulnerabilities it will find. In this section we present several classes of vulnerabilities that typically go undiscovered by a fuzzer.

Access Control Flaws

Some applications require privilege layers to support multiple accounts or user levels. Consider, for example, an online calendaring system that might be accessed via a Web front end. The application might specify an administrator that controls who is allowed to log on to the system. There might be a special group of users capable of creating calendars. All other users might only have read privileges. The most basic form of access control will ensure that a regular user cannot perform administrative tasks.

A fuzzer might be able to discover a fault in the calendaring software that allows an attacker to take complete control of the system. At a low level, software faults are generic across different targets so the same logic can be applied to detect them across the board. During the testing process the fuzzer might also successfully access admin-only functionality with only the credentials of a regular user. However, it is very unlikely that this access control bypass will be detected. Why? Well, consider the fact that the fuzzer does not have an understanding of the logic of the program. There is no way for the fuzzer to know that the admin area should not be accessible to a regular user. Implementing logic-aware functionality into the fuzzer is plausible but can be extremely complex and most likely cannot be reapplied when testing other targets without significant modification.

Poor Design Logic

Fuzzers are also not the best tools to use for identifying poor design logic. Consider, for example, the vulnerability discovered in Veritas Backup Exec that allows attackers to remotely access the Windows server registry to create, modify, or delete registry keys.[19] Such access can almost trivially lead to a complete system compromise. The exposure exists thanks to a listening service that implements a remote procedure call (RPC) interface on a Transmission Control Protocol (TCP) endpoint that requires no authentication and yet accepts commands for manipulating the registry. This was not an authentication issue, as by design there was no authentication required. Rather, it was an inappropriate design decision that likely stemmed from a failure to assume that attackers would be willing to invest the time to decipher the Microsoft Interface Description Language (IDL) used to describe the target routine and subsequently build a custom utility to communicate with the server.

[19] http://labs.idefense.com/intelligence/vulnerabilities/display.php?id=269

Although a fuzzer might uncover poor parsing of data supplied over the RPC connection that results in some form of low-level fault, it is incapable of determining that the exposed functionality is insecure. This concept plays an important role later when we take a look at ActiveX fuzzing in Chapter 18, “Web Browser Fuzzing: Automation,” as many controls simply expose methods allowing an attacker, for example, to create and execute files. Special consideration is given to detecting these design bugs.

Backdoors

For a fuzzer, with limited or no information about the structure of a target application, a backdoor is seen no differently than any other target logic, such as a login screen. Both are simply input vectors receiving authentication credentials. Furthermore, unless the fuzzer has been given enough information to recognize successful logins, it will have no way to identify a successful login attempt using a hard-coded password even if it does randomly uncover one. For example, during the fuzzing of the password field a malformed input that resulted in a crash is typically discovered by a fuzzer but a randomly guessed hard-coded password is not.

Memory Corruption

Memory corruption issues often lead to a crash of the target process. This type of issue can then be recognized by the same symptoms as in a denial of service. However, some memory corruption issues are gracefully handled by the target application and will never be recognized by a simple fuzzer. Consider, for example, a format string vulnerability that could go undetected without attaching with a debugger to the target process. A format string vulnerability often boils down to one offending instruction at the machine code level. For example, on an x86 Linux machine, a symptom of a format string attack with a %n in it will often fault on the following instruction:

mov    %ecx,(%eax)

If the fuzzer is throwing random data to the process with some format triggering characters such as %n here and there, the eax register will in many cases not contain a writable address but instead some garbage word from the stack. In this case, the instruction will raise a segmentation violation signal, SIGSEGV. If the application has a SIGSEGV signal handler, it might simply kill this process and spawn a new one. With some applications, the signal handler might even attempt to allow execution to continue within that process without restarting. With a format string vulnerability, this actually becomes possible (although extremely ill advised) due to the fact that memory might not have actually been corrupted before the SIGSEGV signal occurred. So what if our fuzzer does not detect this? The process does not crash and instead gracefully handles the fault through the signal handler, so there is no security issue, right? Well, keep in mind that a successful format string exploit will write to areas of memory and subsequently use those controlled memory locations to silently gain control of the process. A signal handler will not stop a precise exploit, as a precise exploit will not cause any fault at all.

Depending on the extent of your target monitoring, your fuzzer might or might not catch such situations.

Multistage Vulnerabilities

Exploitation is not always as simple as attacking a single weakness. Complex attacks often involve leveraging several vulnerabilities in succession to compromise a machine. Perhaps an initial flaw grants unprivileged access to a machine, and a subsequent flaw allows for privilege escalation. Fuzzing might be useful for identifying the individual flaws but will not generally be valuable for chaining together a series of minor vulnerabilities or otherwise uninteresting events to identify a multivector attack.

Summary