An Empirical Study of the Robustness of Windows NT Applications Using Random Testing

3.1 Applications and Platform

We selected a group of over 30 application programs. While we tried to select applications that were representative of a variety of computing tasks, the selection was also influenced by what software was commonly used in the Computer Sciences Department at the University of Wisconsin. The software includes word processors, Web browsers, presentation graphics editors, network utilities, spread sheets, software development environments, and others. In addition to functional variety, we also strove to test applications from a variety of vendors, including both commercial and free software.

The operating system on which we ran and tested the applications was Windows NT 4.0 (build 1381, service pack 5). To insure that our results were timely, we tested a subset of the applications on the new Windows 2000 system (version 5.00.2195). For the 14 applications that we re-tested on Windows 2000, we obtained similar results to those tested under NT 4.0. The hardware platform used for testing was a collection of standard Intel Pentium II PCs.

3.2 The Fuzz Testing Tool

The mechanism we used for testing applications was a new tool, called fuzz, that we built for applications running on the Windows NT platform. Fuzz produces repeatable sequences of random input and delivers them as input to running applications via the mechanisms described in Section 2. Its basic operation is as follows:

1. Obtain the process ID of the application to be tested (either by launching the application itself or by an explicit command line parameter).
2. Determine the main window of the target application along with its desktop placement coordinates.
3. Using one of SendMessage, PostMessage, or keybd_event and mouse_event, deliver random input to the running application.

Fuzz is invoked from a command line; it does not use a GUI so that our interactions with the tool do no interfere with the testing of the applications. The first version of our Windows NT fuzz tool had a GUI interface but the use of the GUI for the testing tool interfered with the testing of the applications. As a result, we changed fuzz to operate from a command line. The fuzz command has the following format:

fuzz [-ws] [-wp] [-v] [-i pid] [-n #msgs] [-c] [-l] [-e seed] [-a appl cmd line]

Where -ws is random Win32 messages using SendMessage, -wp is random Win32 messages using PostMessage, and -v is random valid mouse and keyboard events. One of these three options must be specified.

The -i option is used to start testing an already-running application with the specified process ID, and -a tells fuzz to launch the application itself. The -n option controls the maximum number of messages that will be sent to the application, and -e allows the seed for the random number generator to be set.

The -l and -c options provide finer control of the SendMessage and PostMessage tests, but were not used in the tests that we report in this paper. Null parameters can be included in the tests with -l and WM_COMMAND messages (control activation messages such as button clicks) can be included with -c.

3.3 The Tests

Our tests were divided into three categories according to the different input techniques described in Section 2. As such, the application underwent a battery of random tests that included the following:

• 500,000 random Win32 messages sent via the SendMessage API call,
• 500,000 random Win32 messages sent via the PostMessage API call, and
• 25,000 random system events introduced via the mouse_event and keybd_event API calls.

The first two cases use completely random input and the third case uses streams of valid keyboard and mouse events.

The quantity of messages to send was determined during preliminary testing. During that testing, it appeared that if the application was going to fail at all, it would do so within the above number of messages or events. Each of the three tests detailed above was performed with two distinct sequences of random input (with different random seeds), and three test trials were conduced for each application and random sequence, for a total of 18 runs for each application. The same random input streams were used for each application.

4.1 Quantitative Results

The outcome of each test was classified in one of three categories: the application crashed completely, the application hung (stopped responding), or the application processed the input and we were able to close the application via normal application mechanisms. Since the categories are simple and few, we were able to categorize the success or failure of an application through simple inspection. In addition to the quantitative results, we report on diagnosis of the causes of the crashes for the two applications for which we have source code.

Table 1 summarizes the results of the experiments for Windows NT 4.0 and Table 2 has results for a subset of the applications tested on Windows 2000. If an application failed on any of the runs in a particular category (column), the result is listed in the table. If the application neither crashed nor hung, it passed the tests (and has no mark in the corresponding column).

---

Application	Vendor	SendMessage	PostMessage	Random Valid Events
Access 97	Microsoft	C	C	H
Access 2000	Microsoft	C	C	H
Acrobat Reader 4.0	Adobe Systems	C	C
Calculator 4.0	Microsoft		C
CD-Player 4.0	Microsoft	C	C
Codewarrior Pro 3.3	Metrowerks	C	C	C
Command AntiVirus 4.54	Command Software Systems	C	C
Eudora Pro 3.0.5	Qualcomm	C	C	H
Excel 97	Microsoft	C	C
Excel 2000	Microsoft	C	C
FrameMaker 5.5	Adobe Systems		C
FreeCell 4.0	Microsoft	C	C
Ghostscript 5.50	Aladdin Enterprises	C	C
Ghostview 2.7	Ghostgum Software Pty	C	C
GNU Emacs 20.3.1	Free Software Foundation	C	C
Internet Explorer 4.0	Microsoft	C	C	C
Internet Explorer 5.0	Microsoft	C	C
Java Workshop 2.0a	Sun Microsystems		C	H
Netscape Communicator 4.7	Netscape Communications	C	C	C
NotePad 4.0	Microsoft	C	C
Paint 4.0	Microsoft	C	C
Paint Shop Pro 5.03	Jasc Software		H
PowerPoint 97	Microsoft	H	H	H
PowerPoint 2000	Microsoft	H		H
Secure CRT 2.4	Van Dyke Technologies	C	C	H
Solitaire 4.0	Microsoft		C
Telnet 5 for Windows	MIT Kerberos Group		C
Visual C++ 6.0	Microsoft	C	C	C
Winamp 2.5c	Nullsoft	H	C
Word 97	Microsoft	C	C	C
Word 2000	Microsoft	C	C	C
WordPad 4.0	Microsoft	C	C	C
WS_FTP>	Ipswitch	C	C	H
Percent Crashed		72.7%	90.9%	21.2%
Percent Hung		9.0%	6.0%	24.2%
Total Percent Failed		81.7%	96.9%	45.4%

Table 1: Summary of Windows NT 4.0 Test Results
C = Crash, H = Hang.
Note that if an application both crashed and hung, only the crash is reported.

---

---

Application	Vendor	SendMessage	PostMessage	Random Valid Events
Access 97	Microsoft	C	C
Access 2000	Microsoft	C	C	C
Codewarrior Pro 3.3	Metrowerks			C
Excel 97	Microsoft	C	C
Excel 2000	Microsoft	C	C
Internet Explorer 5	Microsoft	C	C
Netscape Communicator 4.7	Netscape Communications	C	C	C
Paint Shop Pro 5.03	Jasc Software			H
PowerPoint 97	Microsoft	H		H
PowerPoint 2000	Microsoft	H		H
Secure CRT 2.4	Van Dyke Technologies	C	C
Visual C++ 6.0	Microsoft	C	C	C
Word 97	Microsoft	C	C	C
Word 2000	Microsoft	C	C	C
Percent Crashed		71.4%	71.4%	42.9%
Percent Hung		14.3%	0.0%	21.4%
Total Percent Failed		85.7%	71.4%	64.3%

Table 2: Summary of Windows 2000 Test Results
C = Crash, H = Hang.
Note that if an application both crashed and hung, only the crash is reported.

---

The overall results of the tests show that a large number of applications failed to deal reasonably with random input. Overall, the failure rates for the Win32 message tests were much greater than those for the random valid keyboard and mouse event tests. This was to be expected, since several Win32 message types include pointers as parameters, which the applications apparently de-reference blindly. The NT 4.0 tests using the SendMessage API function produced a crash rate of over 72%, 9% of the applications hung, and a scant 18% successfully dealt with the random input. The tests using the PostMessage API function produced a slightly higher crash rate of 90% and a hang rate of 6%. Only one application was able to successfully withstand the PostMessage test.

The random valid keyboard and mouse event results, while somewhat improved over the random Win32 message test, produced a significant number of crashes. Fully 21% of the applications crashed and 24% hung, leaving only 55% of applications that were able to successfully deal with the random events. This result is especially troublesome because these random events could be introduced by any user of a Windows NT system using only the mouse and keyboard.

The Windows 2000 tests have similar results to those performed on NT 4.0. We had not expected to see a significant difference between the two platforms, and these results confirm this expectation.

4.2 Causes of Crashes

While source code was not available to us for most applications, we did have access to the source code of two applications: the GNU Emacs text editor and the open source version of Netscape Communicator (Mozilla). We were able to examine both applications to determine the cause of the crashes that occurred during testing.

Emacs Crash Analysis

We examined the emacs application after it crashed from the random Win32 messages. The cause of the crash was simple: casting a parameter of the Win32 message to a pointer to a structure and then trying to de-reference the pointer to access a field of the structure. n the file w32fns.c, the message handler (w32_wnd_proc) is a standard Win32 callback function. This callback function tries to de-reference its third parameter (lparam); note that there is no error checking or exception handling to protect this de-reference.

    LRESULT CALLBACK
    w32_wnd_proc (hwnd, msg, wParam, lParam)
    {
        . . .
        POINT *pos;
        pos = (POINT *)lParam;
        . . .
        if (TrackPopupMenu((HMENU)wParam,
            flags, pos->x, pos->y, 0, hwnd,
            NULL))
            . . .
    }

The pointer was a random value produced by fuzz, and therefore was invalid; this de-reference caused an access violation. It is not uncommon to find failures caused by using an unsafe pointer; our previous studies found such cases, and these cases are also well-documented in the literature [13]. From our inspection of other crashes (based only on the machine code), it appears that this problem is the likely cause of many of the random Win32 message crashes.

Mozilla Crash Analysis

We also examined the open source version of Netscape Communicator, called Mozilla, after it crashed from the random Win32 messages. The cause of the crash was similar to that of the emacs crash. The crash occurred in file nsWindow.cpp, function nsWindow::ProcessMessage. This function is designed to respond to Win32 messages posted to the application's windows. In fashion similar to the GNU emacs example, a parameter of the function (lParam in this case) is assumed to be a valid window handle.

    nsWindow* control = (nsWindow*)::GetWindowLong((HWND)lParam, GWL_USERDATA);
    if (control) {
        control->SetUpForPaint((HDC)wParam);
    . . .

The value is passed as an argument to the GetWindowLong function, which is used to access application specific information associated with a particular window. In this case, the parameter was a random value produced by fuzz, so the GetWindowLong function is retrieving a value associated with a random window. The application then casts the return value to a pointer and attempts to de-reference it, thereby causing the application to crash.

5. Analysis and Conclusions

The goal of this study was to provide a first look at the general reliability of a variety of application programs running on Windows NT. We hope that this study inspires the production of more robust code. We first discuss the results from the previous section then provide some editorial discussion.

The tests of random valid keyboard and mouse events provide the best sense of the relative reliability of application programs. These tests simulated only random keystrokes, mouse movements, and mouse button clicks. Since these events could be caused by a user, they are of immediate concern. The results of these tests show that many commonly-used desktop applications are not as reliable as one might hope.

The tests that produced the greatest failure rates are the random Win32 message tests. In the normal course of events, these messages are produced by the kernel and sent to an application program. It is unlikely (though not impossible) that the kernel would send messages with invalid values. Still, these tests are interesting for two reasons. First, they demonstrate the vulnerability of this interface. Any application program can send messages to any other application program. There is nothing in the Win32 interface that provides any type of protection. Modern operation systems should provide more durable firewalls. Second, these results point to a need for more discipline in software design. Major interfaces between application software components and between the application and the operating system should contain thorough checks of return values and result parameters. Our inspection of crashes and the diagnosis of the source code shows the blind de-referencing of a pointer to be dangerous. A simple action, such as protecting the de-reference with an exception handler (by using the Windows NT Structured Exception Handling facility, for example), could make a qualitative improvement in reliability.

As a side note, many of those applications that did detect the error did not provide the user with reasonable or pleasant choices. These applications did not follow with an opportunity to save pending changes made to the current document or other open files. Doing a best-effort save of the current work (in a new copy of the user file) might give the user some hope of recovering lost work. Also, none of the applications that we tested saved the user from seeing a dialog pertaining to the cause of the crash that contained the memory address of the instruction that caused the fault, along with a hexadecimal memory dump. To the average application user, this dialog is cryptic and mysterious, and only serves to confuse them.

Our final piece of analysis concerns operating system crashes. Occasionally, during our UNIX study, tests resulted in OS crashes. During this Windows NT study, the operating system remained solid and did not crash as a result of testing. We should note, however, that an early version of the fuzz tool for Windows NT did result in occasional OS crashes. The tool contained a bug that generated mouse events only in the top left corner of the screen. For some reason, these events would occasionally crash Windows NT 4.0, although not in a repeatable fashion.

These results seem to inspire comments such as "Of course! Everyone knows these applications are flaky." But it is important to validate such anecdotal intuitions. These results also provide a concrete basis for comparing applications and for tracking future (we hope) improvements.

Our results also lead to observations about current software testing methodology. While random testing is far from elegant, it does bring to the surface application errors, as evidenced by the numerous crashes encountered during the study. While some of the bugs that produced these crashes may have been low priority for the software makers due to the extreme situations in which they occur, a simple approach to help find bugs should certainly not be overlooked.

The lack of general access to application source code prevented us from making a more detailed report of the causes of program failures. GNU Emacs and Mozilla were the only applications that we were able to diagnose. This limited diagnosis was useful in that it exposes a trend in poor handling of pointers in event records. In our 1990 and 1995 studies, we were given reasonable access to application source code by the almost all the UNIX vendors. As a result, we provided bug fixes, in addition to our bug reports. Today's software market makes this access to application source code more difficult. In some extreme cases (as with database systems, not tested in this study), even the act of reporting bugs or performance data is forbidden by the licence agreements [1] (and the vendors aggressively pursue this restriction). While vendors righteously defend such practices, we believe this works counter to producing reliable systems.

Will the results presented in this paper make a difference? Many of the bugs found in our 1990 UNIX study were still present in 1995. Our 1995 study found that applications based on open source had better reliability than those of the commercial vendors. Following that study, we noted a subsequent overall improvement in software reliability (by our measure). But, as long as vendors and, more importantly, purchasers value features over reliability, our hope for more reliable applications remains muted.

Opportunity for more analysis remains in this project. Our goals include

1. Full testing of the applications on Windows 2000: This goal is not hard to achieve, and we anticipate having the full results shortly.
2. Explanation of the random Win32 message results: We were surprised that the PostMessage and SendMessage results differed. This difference may be caused by the synchronous vs. asynchronous nature of PostMessage and SendMessage, or the priority difference between these two types of messages (or other reasons that we have not identified). We are currently exploring the reasons for this difference.
3. Explanation of the Windows NT 4.0 vs. Windows 2000 results: Given that we test identical versions of the applications on Windows NT 4.0 and Windows 2000, our initial guess was that the results would be identical. The differences could be due to several reasons, including timing, size of the screen, or system dependent DLLs. We are currently exploring the reasons for this difference.

6. Related Work

Random testing has been used for many years. In some ways, it is looked upon as primitive by the testing community. In his book on software testing [7], Meyers says that randomly generated input test cases are "at best, an inefficient and ad hoc approach to testing". While the type of testing that we use may be ad hoc, we do seem to be able to find bugs in real programs. Our view is that random testing is one tool (and an easy one to use) in a larger software testing toolkit.

An early paper on random testing was published by Duran and Ntafos [3]. In that study, test inputs are chosen at random from a predefined set of test cases. The authors found that random testing fared well when compared to the standard partition testing practice. They were able to track down subtle bugs easily that would otherwise be hard to discover using traditional techniques. They found random testing to be a cost effective testing strategy for many programs, and identified random testing as a mechanism by which to obtain reliability estimates. Our technique is both more primitive and easier to use than the type of random testing used by Duran and Ntafos; we cannot use programmer knowledge to direct the tests, but do not require the construction of test cases.

Two papers have been published by Ghosh et al on random black-box testing of applications running on Windows NT [5,6], These studies are extensions of our earlier 1990 and 1995 Fuzz studies [8,9]. In the NT studies, the authors tested several standard command-line utilities. The Windows NT utilities fared much better their UNIX counterparts, scoring less than 1% failure rate. This study is interesting, but since they only tested a few applications (attrib, chkdsk, comp, expand, fc, find, help, label, and replace) and most commonly used Windows applications are based on graphic interfaces, we felt a need for more extensive testing.

Random testing has also been used to test the UNIX system call interface. The "crashme" utility [2] effectively exercises this interface, and is actively used in Linux kernel developments.

Source Code

The source and binary code for the fuzz tools for Windows NT is available from our Web page at: ftp://ftp.cs.wisc.edu/paradyn/fuzz .

Acknowledgments

We thank Susan Hazlett for her help with running the initial fuzz tests on Windows NT, and John Gardner Jr. for helping with the initial evaluation of the Fuzz NT tool. We also thank Philip Roth for his careful reading of drafts of this paper. Microsoft helped us in this study by providing a pre-release version of Windows 2000. The paper referees, and especially Jim Gray, provided great feedback during the review process.

This work is supported in part by Department of Energy Grant DE-FG02-93ER25176, NSF grants CDA-9623632 and EIA-9870684, and DARPA contract N66001-97-C-8532. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.

References

1. M. Carey, D. DeWitt, and J. Naughton, "The 007 Benchmark", 1993 ACM SIGMOD International Conference on Management of Data, May 26-28, 1993, Washington, D.C. pp. 12-21.
2. G.J. Carrette, "CRASHME: Random Input Testing",
   http://people.delphi.com/gjc/crashme.html, 1996.
3. J. W. Duran and S.C. Ntafos, "An Evaluation of Random Testing", IEEE Transactions on Software Engineering SE-10, 4, July 1984, pp. 438-444.
4. S. Garfinkel and G. Spafford, Practical UNIX & Internet Security, O'Reilly & Associates, 1996.
5. A. Ghosh, V. Shah, and M. Schmid, "Testing the Robustness of Windows NT Software", 1998 International Symposium on Software Reliability Engineering (ISSRE'98), Paderborn, Germany, November 1998.
6. A. Ghosh, V. Shah, and M. Schmid, "An Approach for Analyzing the Robustness of Windows NT Software", 21st National Information Systems Security Conference, Crystal City, VA, October 1998.
7. G. Meyers, The Art of Software Testing, Wiley Publishing, New York, 1979.
8. B. P. Miller, D. Koski, C. P. Lee, V. Maganty, R. Murthy, A. Natarajan, J. Steidl, "Fuzz Revisited: A Re-examination of the Reliability of UNIX Utilities and Services", University of Wisconsin-Madison, 1995. Appears (in German translation) as "Empirische Studie zur Zuverlasskeit von UNIX-Utilities: Nichts dazu Gerlernt", iX, September 1995.
   http://www.cs.wisc.edu/paradyn/papers/fuzz-revisited.pdf.
9. B. P. Miller, L. Fredriksen, B. So, "An Empirical Study of the Reliability of UNIX Utilities", Communications of the ACM 33, 12, December 1990, pp. 32-44. Also appears in German translation as "Fatale Fehlerträchtigkeit: Eine Empirische Studie zur Zuverlassigkeit von UNIX-Utilities", iX (March 1991). http://www.cs.wisc.edu/paradyn/papers/fuzz.pdf
10. C. Petzold, Programming Windows, 5th ed., Microsoft Press, Redmond, WA, 1999.
11. J. Richter, , 3rd ed., Microsoft Press, Redmond, WA, 1997.
12. D. Solomon, Inside Windows NT, 2nd ed., Microsoft Press, Redmond, WA, 1998.
13. J. A. Whittaker and A. Jorgensen, "Why Software Fails", Technical Report, Florida Institute of Technology, 1999,
    http://se.fit.edu/papers/SwFails.pdf.