Adapting Formal Testing Techniques for Windows[TM] Applications

Gretchen Bilson

{ewc navigate.dll, ewbutton, /Bcodeview /T"Click to open or copy the code samples from this article." /C"samples_1}

My favorite question to ask developers working in the MicrosoftÒ WindowsÔ graphical environment is, "Would you get in a plane flown by an autopilot you programmed with Windows1?" That’s a perfect example of mission-critical software. Other examples include systems for radioactive materials handling, satellite guidance, and securities trading. Mission-critical systems are characterized by the potentially disastrous consequences of disabled or malfunctioning software. Obviously, these applications must be rigorously tested before being released into production.

Though most Windows-based applications are not mission-critical, continuous bug-free execution is still essential. You need to be confident that your application will run for a certain number of hours or days without unrecoverable errors. Many experienced Windows applications developers have performed what seemed like exhaustive tests on their system and released them into production, only to get a call later from an irate user complaining about system freezes. (I received several during the 1987 stock market crash concerning some market data applications I had written in Windows.)

Sound testing strategies and tools can help ensure the robustness of application software. This article discusses a variety of formal testing theories and strategies, their appropriateness to Windows applications, and presents a tool called Autotest that can help reveal problems in your Windows applications.

I admit, I don’t think testing Windows software is fun. It’s about as much fun as solving a logic puzzle where you keep getting new bits of information just as you think you’re near the answer. You get irritated after this happens a few times. Testing your Windows application can eat up 50 percent or more of your total development time--but it’s time nobody likes to talk about. The pain is quickly forgotten once it’s over.

Testing demands a certain amount of faith. For one thing, logic-based testing theory (a theory not covered here) shows that no known testing method can demonstrate absolute program correctness. But applying testing techniques to narrower scopes of programs and environments can yield useful results.

Although Windows programs are tougher to test than traditional programs, formal testing theories and techniques can still serve as a guide for testing them. One standard test, branch coverage, exercises every branch of a conditional statement. A Windows program essentially consists of a set of callback routines that execute within a "driver routine"--the Windows operating environment. It is interesting to see whether there are significant differences in attempting to achieve branch coverage in callback functions that are made up almost entirely of nested case statements versus the traditional sort of program testing theorists had in mind when they developed their ideas. One difference seems to be the much heavier, line-by-line reliance a Windows application has on the system environment itself.

For the purpose of this article I assume that Windows is bug-free. (Many of you would argue that this is a mighty big assumption!) Compared to a Windows application under development, it is reasonable to assume that Windows itself is bug-free.

Testing Techniques

Testing techniques can be classified into two groups: functional testing and structural testing. The functional testing approach treats the program or system as a black box. This type of testing takes the end user’s point of view. A program’s input is defined, the program is invoked, and the results are compared with the program specifications.

The structural testing approach considers details of the program structure such as its language, programming style, control flow, and other coding elements. Structural tests are usually performed by someone who has advanced programming knowledge.

Path testing, one of the oldest of all structural testing techniques, is based on the selection of test paths through a program. A path is some sequence of statements that begins at an entry point, a junction (labeled statement), or a decision (conditional expression); includes zero or more statements of any sort; and ends at a junction, decision, or exit. The statements between each entry, junction, decision, or exit are called a link or a process. Path testing emphasizes the number of links in a path or the number of decisions (called nodes), not the number of statements executed along the path.

Figure 1 shows control flow graphs for the structure of a typical WinMain and window procedure (WinProc). In Figure 1, a circle or diamond with more than one arrow leaving it is a decision; a circle or diamond with more than one arrow entering it is a junction. Links are represented by arrows. The details of the links (some arbitrary number of nonbranching program statements) are not shown.

Figure 1 Control Flow in a WinMain and WinProc

Windows programs are typically made up of one or more procedures (WinProcs) containing nested case statements. Dialog box procedures and other application procedures very often have control flow structures similar to WinProcs. To simplify testing, Windows routines should be developed with a single-entry-single-exit structure wherever possible, because single-entry-multiple-exit routines make it necessary to test a higher number of interfaces between the program and Windows. Figures 2 and 3 show a WinMain and a WinProc rewritten with a single-entry-single-exit configuration.

Figure 2 Restructuring WinMain to a Single-Entry, Single-Exit Format

Single-entry, multiple-exit code

int PASCAL WinMain(hInstance, hPrevInstance, lpCmdLine, nCmdShow)

HANDLE hInstance; /* current instance */

HANDLE hPrevInstance; /* previous instance */

LPSTR lpCmdLine; /* command line */

int nCmdShow; /* show-window type (open/icon) */

{

MSG msg; /* message */

if (!hPrevInstance) /* Other instances of app running? */

if (!InitApplication(hInstance)) /* Initialize shared things */

return (FALSE); /* Exits if unable to initialize */

/* Perform initializations that apply to a specific instance */

if (!InitInstance(hInstance, nCmdShow))

return (FALSE);

/* Acquire and dispatch messages until a WM_QUIT message is received. */

while (GetMessage(&msg, /* message structure */

NULL, /* handle of window receiving the message */

NULL, /* lowest message to examine */

NULL)) /* highest message to examine */

{

TranslateMessage(&msg); /* Translates virtual key codes */

DispatchMessage(&msg); /* Dispatches message to window */

}

return (msg.wParam); /* Returns the value from PostQuitMessage */

}

Single-entry, single-exit code

int PASCAL WinMain(hInstance, hPrevInstance, lpCmdLine, nCmdShow)

HANDLE hInstance; /* current instance */

HANDLE hPrevInstance; /* previous instance */

LPSTR lpCmdLine; /* command line */

int nCmdShow; /* show-window type (open/icon) */

{

int iReturnCode = TRUE;

BOOL bRC1 = TRUE;

BOOL bRC2 = TRUE;

MSG msg; /* message */

/* if there are no other instances of this app running ? */

if (!hPrevInstance)

bRC1 = InitApplication(hInstance); /* initialize shared things */

if (!bRC1)

iReturnCode = FALSE; /* Exits if unable to initialize */

else

{

/* Perform initializations that apply to a specific instance */

bRC2 = InitInstance(hInstance, nCmdShow);

if (!bRC2)

iReturnCode = FALSE; /* Exits if unable to initialize */

else

{

/* Acquire and dispatch messages until a WM_QUIT message is received. */

while (GetMessage(&msg, /* message structure */

NULL, /* handle of window receiv. message */

NULL, /* lowest message to examine */

NULL)) /* highest message to examine */

{

TranslateMessage(&msg); /* Translates virtual key codes */

DispatchMessage(&msg); /* Dispatches message to window */

}

iReturnCode = msg.wParam; /* Exits if unable to initialize */

} /* else */

} /* else */

return (iReturnCode); /* Returns the value from PostQuitMessage */

}

Figure 3 Restructuring a WinProc to a Single-Entry, Single-Exit Format

Single entry, multiple-exit code

long FAR PASCAL MainWndProc(hWnd, message, wParam, lParam)

HWND hWnd; /* window handle */

unsigned message; /* type of message */

WORD wParam; /* additional information */

LONG lParam; /* additional information */

{

FARPROC lpProcAbout; /* pointer to the "About" function */

switch (message) {

case WM_COMMAND: /* message: command from application menu */

if (wParam = = IDM_ABOUT) {

lpProcAbout = MakeProcInstance(About, hInst);

DialogBox(hInst, /* current instance */

"AboutBox", /* resource to use */

hWnd, /* parent handle */

lpProcAbout); /* About() instance address */

FreeProcInstance(lpProcAbout);

break;

}

else /* Lets Windows process it */

return (DefWindowProc(hWnd, message, wParam, lParam));

case WM_DESTROY: /* message: window being destroyed */

PostQuitMessage(0);

break;

default: /* Passes it on if unproccessed */

return (DefWindowProc(hWnd, message, wParam, lParam));

}

return (NULL);

}

Single entry, single-exit code

long FAR PASCAL MainWndProc(hWnd, message, wParam, lParam)

HWND hWnd; /* window handle */

unsigned message; /* type of message */

WORD wParam; /* additional information */

LONG lParam; /* additional information */

{

LONG lReturnCode = NULL;

FARPROC lpProcAbout; /* pointer to the "About" function */

if ((message= = WM_COMMAND) && (wParam = = IDM_ABOUT))

{

lpProcAbout = MakeProcInstance(About, hInst);

DialogBox(hInst, /* current instance */

"AboutBox", /* resource to use */

hWnd, /* parent handle */

lpProcAbout); /* About() instance address */

FreeProcInstance(lpProcAbout);

}

else /* Lets Windows process it */

if (message = = WM_DESTROY) /* message: window being destroyed */

PostQuitMessage(0);

else

/* Passes it on if unproccessed */

lReturnCode = DefWindowProc(hWnd, message, wParam, lParam);

return (lReturnCode);

}

The paths of Windows programs differ from those in vanilla C programs in a number of ways. They tend to be shorter and contain a higher density of conditional branches and other control-flow statements. There are usually fewer long-running loops because they tie up the CPU. Also, along an execution path, an application instance may yield several times. GetMessage, PeekMessage, and WaitMessage may yield control to other applications while they check the message queue. (You would never guess that in Windows, certain functions such as the sound functions can also cause your application to yield.) Yielding is similar to another program getting scheduled to run in a standard time-sharing environment.

In a Windows application, one WinProc may be called by different instances of the application. In many cases the WinProc must retain information it obtains in one message to use while processing another message. This information, which is often held in static or global variables, increases the possibility of unreachable code statements (see Figure 4). Not only is the code in the HiddenWindow procedure of Figure 4 potentially unreachable, a deadlock condition may result. Deadlock conditions can arise in Windows if one application yields control while processing a message sent from another application by means of SendMessage.

Figure 4 Potentially Unreachable Code

/******************************************************************************/

/* Hidden Window Procedure that reads in routed packets into a buffer */

/******************************************************************************/

BOOL FAR PASCAL HiddenWindow(hWnd, message, wParam, lParam)

.

.

.

switch (message) {

case IDC_BUFFER_FULL:

/* if handle to buffer does not exist */

if (hMemGlobalHandle = = NULL)

.

.

.

else

{

wRetCode = SendMessage(hwnd, IDM_EMPTYOUTBUFFER, NULL, NULL);

/* potentially unreachable code */

if (wRetCode != NULL)

hMemGlobalHandle = NULL;

else

.

.

.

break;

/********************************************************/

/* Application Window Procedure that displays the buffer*/

/********************************************************/

long FAR PASCAL MainWndProc(hWnd, message, wParam, lParam)

.

.

.

case IDM_EMPTYOUTBUFFER:

lpDisplayDlg = MakeProcInstance((FARPROC) DisplayDlg, hInst);

hFile = DialogBox(hInst, "Buffer", hWnd, lpDisplayDlg);

FreeProcInstance(lpDisplayDlg);

break;

Statement, Branch, and Path Testing

The minimum IEEE unit test standard is to test all statements in a program at least once: this is 100 percent statement coverage. A more stringent standard, 100 percent branch coverage, is to test every alternative of each conditional branch, as well as the statements between branches. In Windows, achieving branch and statement coverage means that you test a larger ratio of paths to the total set of paths than you would with traditional C or FORTRAN programs. This is because Windows programs tend to have short paths with dense branches. Having to execute a larger proportion of paths is one reason why testing Windows applications takes longer than testing traditional applications (see Figure 5).

Figure 5 Statement, Branch, and Path Testing

Branch testing requires that you run enough tests so that every alternative of each conditional statement has been exercised once. But it may not reveal bugs that occur only when a particular control sequence is followed.

Path testing, which is more exhaustive than branch testing, requires testing every possible sequence of branches and statements from every entry to every exit. The application’s code must first be analyzed to determine if the paths can be achieved and what set of inputs drive them. This is done by formulating each path algebraically, where symbols represent numeric inputs and the conditions along the path are expressed as a group of equalities and inequalities (see Figure 6). If a set of input values that satisfy all conditions of the path cannot occur, the path is not achievable.

Figure 6 Path ABCD

A: m = 0115H (WM_VSCROLL)

B: w = 0000H (SB_LINEUP)

C: l1 > 200

D: l2 > 250

Because it’s usually impractical to test all paths, you need a method for identifying and evaluating the paths most likely to have bugs. Some techniques for identifying them in Windows applications follow. At a minimum you should exercise every statement and every branch of each conditional expression at least once.

Test paths with explicit entry and exit points to Windows. These exits include return statements and any yielding function calls such as PeekMessage, WaitMessage, and Yield. This is to ensure that statements after the yielding function calls are reachable. Also make sure that the statements after every SendMessage call are reachable.

Test paths with correlated branching statements; that is, branches that test the same input variables. For example, the branching statements

if (loword(lParam) = = 100)

and

if (((loword(lParam)) +

(HIWORD(lParam))) > 150)

are correlated. Correlated branching statements usually result from poor program logic and may cause some paths to be unexecutable.

Analyze the results of illegal combinations of input values to functions.

One handy technique is to insert conditionally compiled macros that record when particular branches down a path are taken. The macro could log the statement number, the interpretation of the path in terms of the input variables, and the current status of variables along the path. The idea is to insert probes after every statement along the execution path. The Postman utility in "Postman, a Handy Windows Debugging Utility, Lets You Post a Message to Any Window," MSJ (Vol. 6, No. 3) is a great tool to drive execution down a particular branch or path. Of course, the state of variables that branches or paths are dependent on must be considered.

Path testing requires intimate knowledge of the application’s source code. It’s most useful as part of unit testing by the application developer. But because statistics show that path testing catches only 35 percent of all bugs (see Error Detection Using Path Testing and Static Analysis by C. Gannon), you shouldn’t spend all your test time doing path testing. Also, some errors can be detected only through other testing methods. Path testing does not, for example, detect interface errors between applications and Windows, which usually show up via incorrect return codes after calls to Windows functions.

Domain Testing

Domain testing is a testing technique that views programs as groups of processes that categorize input data. All inputs that a program may process are partitioned into domains. Each conditional expression encountered along a path is interpreted in terms of the input variables that drive execution down that path. The result of this interpretation is usually a group of linear equalities and inequalities that define the input domain or set. The most common application of domain testing is based on program specifications. You apply it to combinations of input variables to derive the domains and analyze their correctness. However, domain testing theory is usually explained in terms of program implementation.

Let’s look at the Microsoft Windows Software Development Kit (SDK) program GENERIC.C to illustrate these concepts. Windows can send input from a variety of sources to the WinProc. This input may be generated by the user from the keyboard or mouse, from a timer, by Windows as part of its own processing, or from other hardware devices or application programs. These inputs can all be viewed as numbers. (For convenience, I use the numbers assigned to each message in WINDOWS.H.) Even character strings can be viewed as binary numbers by concatenating the bits represented by each character. These inputs are grouped into domains based on the processing done by your application. A code fragment from generic.c in Figure 7 shows the conditional expressions in the WinProc (MainWndProc) that determine which numbers belong to each domain and which do not.

Figure 7 GENERIC.C Code Fragment

long FAR PASCAL MainWndProc(hWnd, message, wParam, lParam)

HWND hWnd; /* window handle */

unsigned message; /* type of message */

WORD wParam; /* additional information */

LONG lParam; /* additional information */

{

FARPROC lpProcAbout; /* pointer to the "About" function */

switch (message) {

case WM_COMMAND: /* message: command from application menu */

if (wParam = = IDM_ABOUT) {

lpProcAbout = MakeProcInstance(About, hInst);

DialogBox(hInst, /* current instance */

"AboutBox", /* resource to use */

hWnd, /* parent handle */

lpProcAbout); /* About() instance address */

FreeProcInstance(lpProcAbout);

break;

}

else /* Lets Windows process it */

return (DefWindowProc(hWnd, message, wParam, lParam));

case WM_DESTROY: /* message: window being destroyed */

PostQuitMessage(0);

break;

default: /* Passes it on if unprocessed */

return (DefWindowProc(hWnd, message, wParam, lParam));

}

return (NULL);

}

The case, if, and return statements are conditional expressions and control flow statements that classify the domains in this example. (I have ignored the domains that will result from the creation of the dialog box routine. The dialog box function is its own callback routine and has its own interface with Windows.) The WinProc has the domains listed in Figure 8.

Figure 8 Domains from GENERIC.C's WinProc

In Figure 8 each domain is defined by a set whose boundaries are defined by four input variables. Each input variable adds a dimension to the definition of this set. These sets may be graphed (see Figure 9). Omitting lParam and assuming only one instance of hWnd simplifies the example and permits it to be graphed in two dimensions.

Figure 9 Graph of Input Domains

Graphing these domains shows how set theory applies to domain testing. Each input variable adds one dimension to the domain. Figure 9 shows two variables defining a domain in a plane; three variables would define a three-dimensional domain. Multidimensional domains are the most common type but are the hardest to visualize.

Domain testing looks for bugs in the definition of domains. A bug may mean that the boundaries of a domain are wrong due to errors in conditional expressions or other control flow statements that specify what numbers belong in the domain. Common domain errors are contradictory domains, ambiguous domains, and overspecified domains (where the domain is null).

Confirming boundaries is one of the most important parts of domain testing. Most domains in Windows programs can be expressed as linear equations, because most conditional expressions in Windows and C programs are linear. If the domains aren’t linear many more tests are required. Linear domains make it possible to apply good old linear algebra to characterize input domains. The sources listed at the end of this article cover the application of linear algebra to domain testing in greater detail.

Domains in Windows

Inputs from Windows are posted or sent using the hWnd, message, wParam, and lParam arguments of the WinProc. For dialog box procedures these are practically the same except that hDlg (really a type of window handle) is passed instead of hWnd. Consider the possible ranges for each of these arguments. I’ll ignore the ranges for hWnd because different functions aren’t often executed based on the values of hWnd. The ranges for Windows message numbers are shown in Figure 10.

Figure 10 Windows Messages

The message associated with each number is defined in WINDOWS.H. Windows applications usually use case statements to execute different functions for each message. When a WinProc receives a message, it may process the message, it may pass it on to the default WinProc, or it may ignore it and not pass it on. It may also perform some processing and then pass it on to the default WinProc for additional processing (subclassing is an example). The wParam and lParam define additional qualifiers or values for each message. As you can see from Figure 11, Windows programs tend to have small, discrete input domains; that is, domains with few input points. Domain testing does not work as well for arbitrary discrete sets of data objects because there are no simple, general strategies. You are also more likely to have coincidental correctness errors; that is, errors where the execution outcome is correct but the process that generated it is wrong.

Figure 11 Neat Versus Ugly Domains

Since multidimensional domains are difficult to visualize and hard to test without automated tools, and automated tools are not commercially available, it might seem futile to apply domain testing to Windows programming. But domain testing is useful because it directs you to which inputs to test. For instance, you are performing domain testing when you max out a buffer by opening an extremely large file via your File Open dialog box. The greatest benefit to be gained is in testing domain boundaries, checking for boundary closure errors, and in interface testing.

According to L. J. White et al. (see the source listing at the end of the article), domain testing theory states that the number of test points required to test a domain over an n-dimensional input space with P boundary segments is at most (n+1)P test points (see Figure 12). This includes testing n "on points" and 1 "off point" for each boundary or extreme point. A domain with 1 point defined in n dimensions has 1 boundary segment.

Figure 12 Testing (n+1)P Points in Domain D1

MYPAL.C (see Figure 13) is a sample application included in the Windows SDK. A code fragment is shown in Figure 14. MYPAL charts the current physical palette and displays useful information about pixel colors and palette indexes. To test the domain boundaries of this portion of MYPAL, you first build the list of domains. If you form a truth table (see Figure 15) with all the boundary-defining conditions from Figure 14 and eliminate the invalid domains, you are left with seven domains. Each domain is expressed in three dimensions and may be drawn as a line in a three-dimensional input space. Based on this information, you have to test one "on point" and three "off points" for each boundary segment. Each domain has one boundary segment so you must test at least 28 input points.

Figure 13 MYPAL

Figure 14 Code Fragment from MYPAL.C

long FAR PASCAL WndProc (hWnd, iMessage, wParam, lParam)

.

.

.

switch (iMessage)

{

.

.

.

case WM_LBUTTONDOWN:

/* determine which column was hit by the mouse */

x = LOWORD(lParam);

iIndex = (x / nIncr );

/* Make sure the palette index is within range else

set it to the limiting values and give a warning beep.

*/

if (iIndex < 0)

{

iIndex = 0;

MessageBeep(1);

}

else

{

if (iIndex > iNumColors-1)

{

iIndex = iNumColors-1;

MessageBeep(1);

}

}

pt.x = (iIndex * nIncr) +

iGlobalXOffset +

((nIncr > 1) ? (nIncr / 2) : 1);

pt.y = iYMiddle + iGlobalYOffset;

SetCursorPos (pt.x, pt.y);

if ( bCaptureOn = = TRUE )

{

MessageBeep(1);

break;

}

/* Select & realize the palette or the colors > 0x7

* will not match up.

*/

hDC = GetDC(NULL);

SelectPalette (hDC, hPal, 1);

RealizePalette (hDC) ;

dwColor = GetNearestColor (hDC, PALETTEINDEX (iIndex));

wsprintf ( szTitlebuf,

"MyPal Colors=%d Index=%d R=%3u G=%3u B=%3u",

iNumColors,

iIndex,

(WORD)(BYTE)GetRValue (dwColor),

(WORD)(BYTE)GetGValue (dwColor),

(WORD)(BYTE)GetBValue (dwColor)

);

SetWindowText (hWnd, (LPSTR)szTitlebuf);

ShowColor (hWnd,hDC);

ReleaseDC(NULL, hDC);

break;

.

.

.

}

return 0L ;

}

Figure 15 MYPAL Has Seven Domains

Closure errors occur when boundaries are incorrectly defined. For example, if the statement

if (iIndex >= iNumColors - 1)

is supposed to read

if (iIndex > iNumColors - 1)

a closure error exists in the code. Closure errors are detected as part of testing domain boundaries. These occur less frequently in Windows code because their domains tend to be made up of single, discrete points.

Integration Testing

Integration testing evaluates the correctness of the interface between two otherwise correct routines. It looks for bugs in the interface between functions, whether they are in function parameters, shared data objects, or values left in global variables. Domain testing concepts are applicable to integration testing. If the calling sequence of a function is correct and the function parameter types are compatible, domain testing techniques can be used to examine parameter domains as seen by the calling function and the called function.

In function interfaces, the output values produced by a function or subprocess are passed from the calling function to the called function. These output values become the input values to the called function. Bugs arise when there are incompatibilities between the span (that is, the range of possible values) of the variable from the calling routine and the span of expected inputs to the called routine. If the called routine’s domain has a smaller span than the caller expects or the output values passed don’t line up with the input values that the called function expects, the domains are mismatched. This may cause good values to be rejected or bad values to be accepted and can cause problems if the called routine isn’t robust enough. This is precisely why code to validate parameters has been incorporated in the beta releases of Windows 3.1. This prevents developers from passing invalid parameters to Windows functions, eliminating some GP faults and other UAEs. Windows 3.1 validates parameters passed to APIs, as well as the contents of Windows messages such as handles, pointers, and structures.

The most common parameter errors are invalid handles, pointers, and flags. Invalid handles may result if a handle value of NULL or 1 is passed as a parameter when it isn’t allowed, if previously destroyed or deleted handles are passed, if uninitialized stack variables are used, or if hDCs are passed instead of hWnds. Pointers may be invalid if NULL pointers are passed, if the size of the buffer pointed to is incorrect, if function pointers are improperly exported or MakeProcInstance’d, if strings lack the 0 termination character, if invalid fields in the structure are pointed to, if stack variables are uninitialized, or if read-only pointers are passed when read-write pointers are required. Flags may have illegal values such as meaningless bitflags or out-of-range indexes.

Domain testing is not only the most effective way for you to ensure that the invalid parameters listed here don’t exist in your code, it is also clearly better than random testing because it is unlikely that randomly chosen points will cause extreme input values to be exercised in Windows. If you plan to perform domain testing, you can identify and specify correct domains while designing your application and avoid non-linear expressions unless absolutely essential.

Because domain testing assumes that the processing of non-boundary-defining statements is bug-free, it should be augmented with some other form of testing.

Statistics-based Testing

The longer a program appears to work properly, the fewer bugs it’s assumed to have. This simple concept is the foundation of statistics-based testing theory. Most statistical models in testing are derived from the failure-rate model. This model assumes that a program has a certain probability of failure for random inputs; as more tests are conducted the observed number of failures approaches the actual probability. This implies that the mean time to failure for a system can be predicted from measurements of the times between its failures. The flaw with the failure rate model is that no relationship can be made between the size of the program, the number of inputs required, and the number of tests required. Even though the statistical model is flawed, we tend to have more faith in programs that have a long history of working properly.

Autotest

With each testing theory discussed, even the simplest program may require thousands of test cases to be generated. It is impractical to apply these testing methods without the help of automated tools. For developers to test efficiently, automated tools that are engineered for a particular operating environment and language are needed.

Autotest, a capture/playback tool based on the statistical model, is useful for stress-testing Windows applications just prior to their release into production. Autotest can help reveal memory-allocation problems such as incorrect memory flags, undiscarded objects, problems with errant pointers, and other subtle bugs that manifest themselves during repeated program execution.

This tool can greatly reduce the time required to detect these bugs. Autotest is also useful for automating manual test suites. It monitors and reports the effect of the program on the Windows environment. These effects are likely to go undetected by the testing methods discussed earlier.

Autotest is basically a macro-recording facility that is implemented using Windows system hooks. System hooks are special types of filter functions that process events before they reach any application’s message loop.

Every test tool used to insert probes in application code or to generate traces can reveal information about the system. However, the more information a tool collects, the more the application’s execution is disturbed and the further the test is removed from reality. Timings are distorted and some bugs such as race conditions may be masked. This is true for Windows hook functions, which are called by Windows whenever an event occurs. This tends to slow down the entire system. Autotest minimizes this overhead and timing distortion because it was designed to test software late in the testing cycle.

The interface to Autotest is necessarily simple (see Figure 16). It records a sequence of events that you input to the application(s) being tested (key presses, mouse moves and clicks, and so on). It then replays those events as many times as you specify. It also records trace data if requested during playback mode. User-specified parameters are passed to Autotest via the WIN.INI file. This allows Autotest to use the GetProfileInt and GetProfileString SDK functions rather than having to use custom dialog routines to read in these parameters. It also cuts down on the size of the application and the possibility of introducing errors. The WIN.INI file parameters are shown in Figure 17.

Figure 16 Autotest

Figure 17 Autotest Parameters in WIN.INI

[autotest]

NumberofIterations=10 ; Number of times to play back the recorded

; sequence

RecordTracefile=d:autorec1.trc ; File to write out recorded events

; located on RAM disk

PlaybackTracefile=d:autoply1.trc ; File to write out trace of events that

; are played back, located on RAM disk

FixedTimingFlag=TRUE ; Flag that determines whether to use

; a fixed value for the time between events

; or to use a percentage of the time

; recorded between events

TimeBetEvents=55 ; Fixed value in millisecs for the time

; between events, only used if the

; FixedTimingFlag = TRUE

PercentRecordTime=0 ; Percentage of the time between recorded

; events to be used during playback

NumEventstoBypass=5 ; Number of events to bypass between writes

; to the trace file

IOBufferSize=20 ; Number of events to buffer before

; writing out to the playback trace file

Reading parameters from the WIN.INI file slows the system only at startup, which is generally not a problem in a test environment.

Applications can be stress tested by varying the timing parameters. The WIN.INI parameters provided for this purpose are TimeBetEvents, PercentRecordTime, FixedTimingFlag, and NumEventstoBypass. If the FixedTimingFlag is set to TRUE, the tester must specify the value of the TimeBetEvents in milliseconds, which causes the playback filter function to wait for that number of milliseconds before replaying each event. The actual time recorded between events is not used in this case. Lower values cause the system to be stressed even further. If the FixedTimingFlag is set to FALSE, the PercentRecordTime parameter specifies the percentage of the recorded times between events to use in playback mode. A PercentRecordTime value of 100 means that events are played back using the actual time recorded between events. A PercentRecordTime value of 50 plays back events at twice the recorded speed.

To start recording a test sequence, select the Trace On menu pick. Then select the Start Recording menu pick and perform a sequence of actions on the application being tested. When you’re finished recording, select the Stop Recording menu pick; the list of recorded events is then written to the record trace file. This file never includes playback trace information, which is written to a different trace file when the Start Playback menu pick is chosen. This prevents Autotest from having to open, write to, and close a rapidly growing trace file every time an event is encountered. The record trace file is opened and written to only once at the end of a recording sequence. Each event is annotated in the file with an event number. These event numbers are important for interpreting the playback trace file.

Trace data is written out to the playback trace file during playback mode. The WIN.INI parameter NumEventstoBypass specifies how often the playback trace file is to be updated. For example, setting NumEventstoBypass to 15 causes trace information to be written after every fifteenth message has been processed. At test completion time, the record trace file and the playback trace file must be analyzed together since event numbers in the playback trace file refer to the previously recorded test sequence. A sample of the record trace file output and playback trace output are shown in Figure 18.

Figure 18 Sample Trace FileOutput

Record trace file output:

Recorded Event MSG 1= 260; paramL= 3812; paramH= 1; time= 659

Recorded Event MSG 2= 260; paramL= f09; paramH= 1; time= 879

Recorded Event MSG 3= 512; paramL= 191; paramH= 38; time= 1044

Recorded Event MSG 4= 257; paramL= 3812; paramH= 1; time= 1044

Recorded Event MSG 5= 512; paramL= 191; paramH= 38; time= 1099

Recorded Event MSG 6= 257; paramL= f09; paramH= 1; time= 1099

Recorded Event MSG 7= 256; paramL= 1c0d; paramH= 1; time= 1319

Recorded Event MSG 8= 257; paramL= 1c0d; paramH= 1; time= 1483

Recorded Event MSG 9= 512; paramL= 191; paramH= 38; time= 1868

Recorded Event MSG 10= 256; paramL= 4d27; paramH= 8001; time= 2197

Recorded Event MSG 11= 512; paramL= 70; paramH= 1c5; time= 2197

Recorded Event MSG 12= 256; paramL= 4d27; paramH= 8001; time= 2692

o

o

o

Playback trace file output:

[autotest]

NumberofIterations= 10

FixedTimingFlag= TRUE

TimebetEvents= 55

PercentRecordTime= 0

NumEventstoBypass= 5

IOBufferSize= 20

Iteration= 0, Event= 6, FreeSpace= 5945792

Iteration= 0, Event= 12, FreeSpace= 5926176

Iteration= 0, Event= 18, FreeSpace= 5926176

Iteration= 0, Event= 24, FreeSpace= 5926176

Iteration= 0, Event= 30, FreeSpace= 5926176

Iteration= 0, Event= 36, FreeSpace= 5926176

Iteration= 0, Event= 42, FreeSpace= 5926176

Iteration= 0, Event= 48, FreeSpace= 5926176

Iteration= 0, Event= 54, FreeSpace= 5926176

Iteration= 0, Event= 60, FreeSpace= 5926176

Iteration= 0, Event= 66, FreeSpace= 5943200

Iteration= 0, Event= 72, FreeSpace= 5943200

Iteration= 0, Event= 78, FreeSpace= 5943200

Iteration= 1, Event= 1, FreeSpace= 5943200

Iteration= 1, Event= 7, FreeSpace= 5943200

Iteration= 1, Event= 13, FreeSpace= 5923584

Iteration= 1, Event= 19, FreeSpace= 5923584

Iteration= 1, Event= 25, FreeSpace= 5923584

Iteration= 1, Event= 31, FreeSpace= 5923584

Iteration= 1, Event= 37, FreeSpace= 5923584

Iteration= 1, Event= 43, FreeSpace= 5923584

Iteration= 1, Event= 49, FreeSpace= 5923584

Iteration= 1, Event= 55, FreeSpace= 5923584

Iteration= 1, Event= 61, FreeSpace= 5923584

Iteration= 1, Event= 67, FreeSpace= 5940608

Iteration= 1, Event= 73, FreeSpace= 5940608

Iteration= 1, Event= 79, FreeSpace= 5940608

Iteration= 2, Event= 2, FreeSpace= 5940608

Iteration= 2, Event= 8, FreeSpace= 5940608

Iteration= 2, Event= 14, FreeSpace= 5920992

Iteration= 2, Event= 20, FreeSpace= 5920992

Iteration= 2, Event= 26, FreeSpace= 5920992

Trace file information is presented in a sparse format to reduce the overhead of writing out to a file. Trace files should be kept on a RAM disk to improve disk access times. (However, if your application causes a system crash, you won’t be able to recover your trace data from RAM!)

Autotest Structure

Autotest has two components: the Autotest application and a DLL named Tester. Autotest makes function calls to a routine in the DLL that’s also called Tester (see Figure 19).

Figure 19 How Autotest Calls Tester

As mentioned, Autotest is implemented using system hook filter functions that are application-supplied callback routines. System hook filter functions must reside in a fixed code segment of a DLL because they can be called by Windows at all times regardless of the active task. Autotest uses journal record (WH_JOURNALRECORD) and journal playback (WH_JOURNALPLAYBACK) hooks to record and play back event messages from the system queue. A comprehensive discussion on Windows hooks can be found in Chapter 6 of Jeffrey Richter’s book, Windows 3: A Developer’s Guide (M&T Books, 1991).

Tester calls the SetWindowsHook function to install the WH_JOURNALRECORD hook and its associated filter function. This is done when Tester is invoked with the AutotestMode parameter set to the IDD_STARTRECORD value. When Windows calls the journaling record filter function with the HC_ACTION hook code, the lParam parameter points to an EVENTMSG structure. This occurs every time an event is processed from the Windows system queue. The journaling record filter function appends a copy of the event message to an event array in global memory to be played back later on (see Figure 19). Each event has the following structure defined in the WINDOWS.H file:

typedef struct tagEVENTMSG

{

WORD message;

WORD paramL;

WORD paramH;

DWORD time;

} EVENTMSG;

typedef EVENTMSG FAR *LPEVENTMSGMSG;

The message member may contain a keyboard or mouse message. If a mouse message is recorded, paramL and paramH contain the x and y mouse coordinates. If a keyboard message is recorded, paramL and paramH hold the key scan codes and key repeat counts. When a mouse message is played back the mouse location is used to determine which window to send the mouse event to. This can cause problems if the window the message is intended for has been moved or if a monitor of a different resolution is used. To avoid sending messages to the wrong window or playing events into a nonexistent x , y coordinate space, you should use keyboard events as much as possible in your playback sequence. The time when the event occurred is specified in milliseconds and is measured from the beginning of the Windows session. This information is used later to control the rate at which messages are replayed.

The journaling playback filter function is also installed using the SetWindowsHook function call. SetWindowsHook must receive the procedure-instance address of your filter function just as it did for the journaling record filter function. DLLs can pass this address directly.

Windows sends the HC_GETNEXT and HC_SKIP hook codes to your journaling playback filter function. It also sends other hook code values (HC_SYSMODALON, HC_SYSMODALOFF, HC_LPFNNEXT, and HC_LPLPFNNEXT) that are not used in this routine. These are returned to Windows. (While the playback hook is executing, Windows throws away all mouse messages and delays the processing of any keyboard input. Since there is no special handling in this filter function for the handling of a system modal dialog box--hook codes HC_SYSMODALON and HC_SYSMODALOFF--Windows uses the default behavior, which is to wait for the user to respond. Then it returns to playback mode).

When the hook routine receives the HC_GETNEXT hook code, the current event message in the chain is copied into the EVENTMSG structure pointed to by the lParam parameter. The HC_SKIP hook code notifies your journaling playback filter function, called JournalPlaybackHook, to send the next event when Windows sends another HC_GETNEXT message (see Figure 20).

Figure 20 Processing HC_GETNEXT and HC_SKIP Hook Codes

case HC_SKIP:

o

o

o

++EventStats.wNumEventsPlayed;

if (EventStats.wNumEventsPlayed > EventStats.wNumEvents)

{

++EventStats.wNumIterationsPlayed;

if (EventStats.wNumIterationsPlayed < EventStats.wNumIterations)

{

EventStats.wNumEventsPlayed = 0;

EventStats.dwStartPlaybackTime = GetTickCount();

}

else

{

if (TraceOn)

WriteFile(lpTraceFileName, (LPSTR)&str);

Tester(IDD_STOPPLAY, (HANDLE)NULL, (HWND)NULL, 0, TraceOn,

(LPSTR)NULL);

}

}

/* if Trace Mode is on then capture information to be written

out to the playback trace file */

if (TraceOn)

{

++EventStats.wNumEventsBypassed;

if (EventStats.wNumEventsBypassed > EventStats.wNumEventstoBypass)

{

/* Write out data to trace file */

dwFreeSpace = GetFreeSpace(GMEM_NOT_BANKED);

--EventStats.wNumEventsBuffered;

/* Buffering required for file I/O */

wsprintf(strtemp, "Iteration= %d, Event= %d, FreeSpace= %lu\n",

EventStats.wNumIterationsPlayed,

EventStats.wNumEventsPlayed, dwFreeSpace);

lstrcat((LPSTR)&str, (LPSTR)&strtemp);

if (EventStats.wNumEventsBuffered = = 0)

{

WriteFile(lpTraceFileName, (LPSTR)&str);

EventStats.wNumEventsBuffered = EventStats.wBufferSize;

str[0] = NULL;

}

EventStats.wNumEventsBypassed = 0;

}

}

break;

case HC_GETNEXT:

// Copy the next event in the event queue into the EVENTMSG

// structure

wNumEvntsPlayed = EventStats.wNumEventsPlayed;

*((LPEVENTMSGMSG)lpEventMsg) = lpEventEntry[wNumEvntsPlayed];

// Add time delta (Event'n' - Event0) back to Start Playing time

((LPEVENTMSGMSG)lpEventMsg)->time +=EventStats.dwStartPlaybackTime;

// All times are expressed in terms of elapsed time in millisecs since

// system start

// We have used up some time doing all this processing

dwReturnCode = ((LPEVENTMSGMSG)lpEventMsg)->time - GetTickCount();

if ((signed long)dwReturnCode < 0)

dwReturnCode = 0;

break;

If you examine the code carefully, you will notice that the journaling playback filter function keeps sending the same event in response to an HC_GETNEXT until an HC_SKIP message is received. This is an extremely important point and the documentation on it is somewhat misleading. The documentation emphasizes that the filter function’s return value should be the amount of time (in clock ticks) Windows should wait before processing the message. When I traced through the sequence of calls to this hook routine, I noticed that Windows kept sending me HC_GETNEXT messages for the same event until the time specified in the DWORD returned to Windows had elapsed.

What Windows does is this: if no other activity is occurring in the system, Windows waits until the time you specify in your return from HC_GETNEXT to wake itself up and use your played-back event. This doesn’t happen very often. Usually other events occur that cause Windows to look into the system queue. Every time Windows looks into the system queue, it calls your hook with an HC_GETNEXT hook code. This can happen many times for the same event.

The time is computed by calculating the time elapsed from the start of the recording to the current message. If the recording is to be played back at the original recording speed, the time playback is started is added to the elapsed time and returned in the time variable in the event message data structure (see Figure 21).

Figure 21 Timing Calculations

CASE IDD_STOPRECORD:

o

o

o

for (EventQIndex= 1; EventQIndex < EventStats.wNumEvents; EventQIndex++)

{

lpEvent[EventQIndex].time -= lpEvent[0].time;

o

o

o

break;

case IDD_STARTPLAY:

o

o

o

// Perform calculations on timings

for (EventQIndex= 1; EventQIndex < EventStats.wNumEvents; EventQIndex++)

{

if ((EventStats.FixedTiming[0] = = 't') || (EventStats.FixedTiming[0] = = 'T'))

lpEvent[EventQIndex].time = lpEvent[0].time + (EventQIndex *

EventStats.wTimebetEvents);

else

if (EventStats.wPercentofTime > 0)

lpEvent[EventQIndex].time = (lpEvent[EventQIndex].time *

EventStats.wPercentofTime/100);

else

lpEvent[EventQIndex].time = (lpEvent[EventQIndex].time * 1 / 100);

}

Trace data such as the amount of free space is captured in the journaling playback filter function. Figure 20 shows the code that does this as part of processing the HC_SKIP message.

One of the trickiest parts of writing a filter function is passing back messages to the next function in the hook chain. When a hook is installed using the SetWindowsHook function call, Windows returns the address of the previously installed filter function. This must be saved in a global or static variable. The last function call that the hook makes should be to DefHookProc. The last parameter to DefHookProc must be the address in memory where the address to the next filter function can be found (see Figure 22). Implementing this feature incorrectly can cause an unrecoverable application error.

Figure 22 Passing Unused Hook Codes to Windows

// Install Windows hook in tester.dll

static FARPROC fnNextJrnlHookFunc = NULL;

o

o

o

fnNextJrnlHookFunc = SetWindowsHook(WH_JOURNALRECORD, (FARPROC)JournalRecordHook);

o

o

o

DWORD FAR PASCAL JournalRecordHook (int nCode, WORD wParam,

LPEVENTMSGMSG lpEventMsg)

{

o

o

o

dwReturnCode = DefHookProc(nCode, wParam,(LONG)lpEventMsg,

(FARPROC FAR*)&fnNextJrnlHookFunc);

return(dwReturnCode);

}

While the WH_JOURNALPLAYBACK hook and its filter function are active, Windows ignores all mouse input and deletes keyboard input. The filter function contains code that lets you terminate the hook via a Ctrl-Break key sequence. This is done by calling the GetAsyncKeyState within the filter function to see if Ctrl-Break has been hit. This is much easier than installing a special keyboard hook to implement the same feature.

case HC_SKIP:

if ((GetAsyncKeyState(VK_CONTROL) & 0x8001)

&& (GetAsyncKeyState(VK_CANCEL) & 0x8001))

{

if (TraceOn)

WriteFile(lpTraceFileName, (LPSTR)&str);

Tester(IDD_STOPPLAY, (HANDLE)NULL, (HWND)NULL,

0, TraceOn, (LPSTR)NULL);

Finding Bugs with Autotest

I created the original version of Autotest (see Figure 23) to stress-test a suite of Windows applications I was writing for a securities trading workstation. This tool cut the total time required to perform stress testing in half. All applications were fully unit-tested before I ran the stress tests. First I determined the minimum length of time an application had to be operational. I generated test cases with multiple instances of each application and exercised different paths within each instance, making sure to include the startup and shutdown of the application.

I ran the test cases for enough iterations to simulate the length of time that the system had to be operational. I would gradually rerun the test cases at faster speeds and then repeat the test with a group of different applications that had been already stress-tested alone. My objective was to be able to isolate the buggy application wherever possible.

Using this technique I uncovered bugs in applications that did not delete GDI resources such as bitmaps, brushes, cursors, DCs, icons, regions, and sound resources. I was also able to detect problems with bit settings for globally allocated memory.

Enhancements

Many enhancements could be made to this tool. The capability of reading a script from the record trace file and playing back from this script would be an obvious enhancement. A facility for editing the script and allowing the edited script to be replayed would be useful. More information on the Windows environment would be especially helpful if it could be generated without adding to the overhead of the tool. It would also be desirable to control the reporting of this information based on exceptions that occur in the Windows environment.

Although I’ve focused exclusively on program-based testing performed at the end of the development process, I strongly recommend integrating testing into your development plans from the very beginning of a project. It’s like the oil filter commercial says, "You can pay me now or pay me later." Preventing bugs early in the development cycle minimizes the time required to test at the end of a project.

Maybe your autopilot will make it through the flight after all . . . Happy landing!

References and for further reading:

ANSI/IEEE Standard 1008-1987, Software Unit Testing.

Beizer, B. Software Testing Techniques, 2nd Ed. Van Nostrand Reinhold.

Clarke, L.A., Hassel, J., and Richardson, D.J. "A Close Look At Domain Testing," IEEE Transactions on Software Engineering 2:215-222 (1976).

Gelperin, D., Hetzel, B. "The Growth of Software Testing," Communictions of the ACM, Volume 31, Number 6.

Hamlet, R. "Special Section on Software Testing," Communications of the ACM, Volume 31, Number 6.

Howden, W.E. "Reliability of the Path Analysis Testing Strategy," IEEE Transactions on Software Engineering 2:208-215 (1976).

White, L.J., Teng, F.C., Kuo, H., and Coleman, D. An Error Analysis of the Domain Testing Strategy. Technical Report OSU CISC-TR-78-2, Computer and Information Science Research Center, Ohio State University, Columbus, Ohio.

1For ease of reading, "Windows" refers to the Microsoft Windows graphical environment. "Windows" is a trademark that refers only to this Microsoft product and does not refer to such products generally.