TEST AND DIAGNOSTICS

Fuzz Testing and its Role for Software Assurance

Software assurance is level of confidence that software is
free from vulnerabilities, either intentionally designed into the
software or accidentally inserted at any time during its life cycle
and that the software functions in the intended manner [1].
Multiple techniques and tools should be used for software
assurance. Static analysis tools examine code for weaknesses
without executing it. On the other hand, testing evaluates a
program by executing it with test inputs and then compares the
outputs with expected outputs. Both static analysis and testing
have a place in the software development life cycle.
Positive testing checks whether a program behaves as ex-
pected when provided with valid input. On the other hand, nega-
tive testing checks program behavior by providing invalid data as
input. Due to time constraints, negative testing is often excluded
from the software development life cycle. This may allow vulner-
abilities to persist long after release and be exploited by hackers.
Fuzz testing is a type of negative testing that is conceptually
simple and does not have a big learning curve.
Fuzz testing, or fuzzing, is a software testing technique that
involves providing invalid, unexpected, or random test inputs to
the software system under test. The system is then monitored
for crashes and other undesirable behavior [2].
The first fuzzing tool simply provided random inputs to about
90 UNIX utility programs [3]. Surprisingly, this simple approach
led to crashes or hangs (never-ending execution) for a substan-
tial proportion of the programs (25 to 33%).
Fuzz testing has been used to find many vulnerabilities in
popular real-life software. For example, a significant proportion

Fuzz Testing
of recent vulnerabilities in Wireshark (http://www.wireshark.org),
a network protocol analyzer, were found by fuzzing. Large orga-
nizations are taking note. For example, Microsoft includes fuzz
testing as part of its Security Development Lifecycle (http://

for Software
www.microsoft.com/security/sdl/default.aspx).
A fuzzing tool, or fuzzer, consists of several components and
a fuzzing process involves several steps [4]. First, a generator
produces test inputs. Second, the test inputs are delivered to

Assurance
the system under test. The delivery mechanism depends on the
type of input that the system processes. For example, a delivery
mechanism for a command-line application is different from one
for a web application. Third, the system under test is monitored
for crashes and other basic undesirable behavior.

Strengths and Limitations of Fuzz Testing

Vadim Okun, NIST Fuzz testing is conceptually simple and may offer a high ben-
Elizabeth Fong, NIST efit-to-cost ratio. In traditional testing, each test case consists of
an input and the expected output, perhaps supplied by an oracle.
Abstract. Multiple techniques and tools, including static analysis and testing, The output of the program is compared to the expected output
should be used for software assurance. Fuzz testing is one such technique that to see whether the test is passed or failed. In the absence of
can be effective for finding security vulnerabilities. In contrast with traditional executable specifications or a test oracle (e.g. a reference imple-
testing, fuzz testing only monitors the program for crashes or other undesirable mentation or checking procedure), finding the expected output
behavior. This makes it feasible to run a very large number of test cases. This for a lot of test cases can be costly. In contrast, fuzz testing only
article describes fuzz testing, its strengths and limitations, and an example of its monitors the program for crashes or other undesirable behavior.
application for detecting the Heartbleed bug. This makes it feasible to run hundreds of thousands or millions
of test cases.

CrossTalk—March/April 2015 35
TEST AND DIAGNOSTICS

Fuzz testing is effective for finding vulnerabilities because instead there must be monitoring for crashes or other generally
most modern programs have extremely large input spaces, while undesirable behavior. However, many types of weaknesses do
test coverage of that space is comparatively small [5]. not produce clearly undesirable behavior. Therefore, more so-
While static source code analysis or manual review are not phisticated detection that test input caused a failure can signifi-
applicable to systems where source code is not available, fuzz cantly expand the classes of weaknesses uncovered by fuzzing.
testing may be used. Fuzz testing is a general technique and The following Section describes an example of using dynamic
therefore may be included in other testing tools and techniques analysis tools to detect a weakness that does not cause a crash
such as web application scanners [6]. under normal operation.
Fuzz testing has a number of limitations [7]. First, exhaustive
testing is infeasible for a reasonably large program. Therefore, Protocol Testing Experiment
typical software testing, including fuzz testing, cannot be used to The Heartbleed bug is a widely known vulnerability in
provide a complete picture of the overall security, quality or ef- OpenSSL, a popular implementation of the cryptographic proto-
fectiveness of a program in any environment. Second, it is hard cols Secure Sockets Layer (SSL) and Transport Layer Security
to exercise the program thoroughly without detailed understand- (TLS). Briefly, under the Heartbeat protocol, the client sends a
ing, so fuzz testing may often be limited to finding shallow weak- message and the message length to the server, and the server
nesses with few preconditions. Third, finding out what weakness echoes back the message.
in code caused the crash may be a time-consuming process. Fi- The Heartbleed vulnerability can be exploited to leak con-
nally, fuzz testing is harder to apply to categories of weaknesses, fidential information, including passwords and authentication
such as buffer over-reads, that do not cause program crashes. data. It was caused by the failure of OpenSSL to validate the
message length, which caused Buffer over-read weakness [10].
Fuzzing Approaches For more details, an interested reader can examine Heartbit,
Test input generation can be as simple as creating a se- an abstracted version of the OpenSSL code demonstrating the
quence of random data [3]. This approach does not work well Heartbleed vulnerability [11]. Even though buffer overflow, which
for programs that expect structured input. No matter how many includes buffer over-read, is a well-known weakness, software
tests are generated, the vast majority might only exercise a assurance tools missed it [12].
small validation routine that checks for valid input. Simple fuzz testing, which looks for crashes, would not have
In regression testing, valid inputs may be collected, for example, detected Heartbleed. The reason is that buffer over-reads rarely
from historical databases of unusual inputs that caused errors lead to program crashes. However, fuzz testing in combination
in the past versions of the software, and then supplied to the with a memory error detection tool, may have detected Heart-
program without modification. Such approach can help uncover a bleed, as demonstrated in [13].
weakness that reoccurs between versions or implementations, but Memory error detection tools, such as Valgrind (http://val-
is unlikely to uncover new weaknesses. grind.org) and AddressSanitizer (http://code.google.com/p/
Most fuzz generators can be divided into two major categories: address-sanitizer), are a type of dynamic analysis tools that can
mutation based and generation based fuzzers [8]. A mutation be used to instrument code to detect various memory errors,
based fuzzer produces test inputs by making random changes such as buffer overflows and use-after-free errors that may not
to valid test input, such as those from regression testing. This cause a crash under normal operation.
approach can be quickly applied to systems, such as protocols In the first experiment, [13] ran a vulnerable version of
or word processors, that accept complex inputs. However, the OpenSSL with Valgrind. When the fuzzer sent an exploiting
coverage is only as strong as the set of valid test inputs. If there is Heartbleed request, Valgrind produced an error trace highlight-
no valid test input for a particular system component, the mutation ing the bug. In the second experiment, a vulnerable version of
based fuzzer is unlikely to cover this component. OpenSSL was compiled with the AddressSanitizer compiler
A generation based fuzzer produces test inputs based on option. When an exploiting Heartbleed request was sent to the
some specification of the input format. While implement- server, it terminated and an error trace was produced. In both
ing the input format in enough detail requires a significant experiments, a programmer could use the error trace to find the
upfront effort, the generation based fuzzer can achieve very Heartbleed bug.
high coverage at lower cost.
A relatively recent approach, whitebox fuzz testing, combines Conclusions
symbolic execution with constraint solving to construct new Typical software testing, including fuzz testing, cannot be used
inputs to a program [9]. Whitebox fuzzing has been used by Mi- alone to produce bug-free software. Since fuzz testing does not
crosoft to find one third of all the bugs discovered by file fuzzing require a sophisticated oracle, it can quickly test a very large
during the development of Windows 7. number of unexpected inputs. When combined with appropriate
The next step after producing test inputs is providing them to supplemental tools, this makes it possible to find security vulner-
the system under test. Some common delivery mechanisms are abilities, such as the Heartbleed bug, which may be missed by
files, environment variables, command line and API parameters, and other tools. As demonstrated by a large number of bugs recently
operating system events, such as mouse and keyboard events.
Fuzz testing does not require knowing the expected output,

36 CrossTalk—March/April 2015
 TEST AND DIAGNOSTICS

discovered in production software, fuzz testing can be used to

increase software assurance.
REFERENCES
1. CNSS, National Information Assurance (IA) Glossary CNSSI-4009, 26 April 2010,
Disclaimer: p. 69, http://www.ncix.gov/publications/policy/docs/CNSSI_4009.pdf.
Any commercial product mentioned is for information only; it 2. Wheeler, David A. and Rama S. Moorthy, “SOAR for Software Vulnerability
does not imply recommendation or endorsement by NIST nor Detection, test and Evaluation,” IDA paper P-5061, July 2014.
does it imply that the products mentioned are necessarily the 3. Miller, Barton P., Lars Fredriksen, and Bryan So, “An Empirical Study of the
best available for the purpose. Reliability of UNIX Utilities,” Communications of ACM 33(12):32-44 (Dec. 1990).
4. McNally, R., Yiu, K., Grove, D., and Gerhardy, D., “Fuzzing: The State of the Art,”
Technical Note DSTO-TN-1043, 2012.
ABOUT THE AUTHORS 5. Householder, Allen D., “Why Fuzzing (Still) Works,” in Metrics and Standards for
Software Testing (MaSST) workshop, p. 39-59, December 2012,
Vadim Okun is a Computer Scientist at http://samate.nist.gov/docs/MaSST_2012_NIST_IR_7920.pdf.
the National Institute of Standards and 6. Fong, Elizabeth, Romain Gaucher, Vadim Okun, Paul E. Black, and Eric Dalci,
Technology, where he is leading the SA- “Building a Test Suite for Web Application Scanners,” 41st Hawaii Int’l Conf. on
MATE (http://samate.nist.gov/) team. His System Sciences (HICSS), January 2008.
current research focuses on software as- 7. West, Jacob, “How I Learned to Stop Fuzzing and Find More Bugs,” DefCon,
surance, in particular, the effect of tools on Las Vegas, August 2007.
security. He organized Static Analysis Tool 8. Neystadt, John, “Automated Penetration Testing with White-Box Fuzzing,”
Expositions (SATE) – large-scale evalua- http://msdn.microsoft.com/en-us/library/cc162782.aspx, Microsoft, February 2008.
tions to support research in, and improve- 9. Bounimova, Ella, Patrice Godefroid, and David Molnar, “Billions and Billions of
ment of, static analysis tools. Previously, Constraints: Whitebox Fuzz Testing in Production,” ICSE 2013:122-131.
Okun contributed to the development 10. Wheeler, David A., “How to Prevent the next Heartbleed,”
of automated software testing methods: http://www.dwheeler.com/essays/heartbleed.html, 2014.
specification-based mutation analysis and 11. Bolo – Joseph T. Burger, “Heartbit test case,”
combinatorial testing. He received a Ph.D. http://samate.nist.gov/SARD/view_testcase.php?tID=149042.
in Computer Science from University of 12. Kupsch, James A. and Miller, Barton P. “Why Do Software Assurance Tools Have
Maryland Baltimore County. Problems Finding Bugs Like Heartbleed?” Continuous Software Assurance
Marketplace, 22 Apr. 2014, https://continuousassurance.org/swamp/SWAMP-Heartbleed.pdf.
E-mail: vadim.okun@nist.gov 13. Vassilev, Apostol and Christopher Celi, “Avoiding Cyberspace Catastrophes through
Smarter Testing,” IEEE Computer, October 2014; 47(10):86-90.
Elizabeth Fong is a computer scientist
currently working in the Software and
Systems Division, Information Technol-
ogy Laboratory of National Institute of
Standards and Technology. She performs
research, analysis, and evaluation of in-
novative information technology software
and practices with emphasis on new
fields of computer technology for Federal
Government applications. Recent work
involved software assurance, smart card
technology, XML registry framework and
standards, and interoperability testing
technology. Earlier work included tech-
nologies and standards development for
Object-Oriented, distributed database
management and agent-based comput-
ing. She has many years of experience in
the development of software testing and
reference models for information tech-
nologies. She received B.SC (Math) New
York University, New York, NY,
M.S. (Computer Science) Stanford Univer-
sity, CA and Graduate Courses (Computer
Science) U. of Maryland, MD.

E-mail: efong@nist.gov
CrossTalk—March/April 2015 37