Introduction

Introduction In this book, you're asked to accept one basic assumptionthat all memory corruption vulnerabilities should be treated as exploitable until you can prove otherwise. This assumption might seem a bit extreme, but it's a useful perspective for a code auditor. Attackers can often leverage an out-of-bounds memory write to modify a program's runtime state in an arbitrary manner, thus violating any security policy an application should be enforcing. However, it's hard to accept the severity of memory corruption vulnerabilities or even understand them until you have some knowledge of how memory corruption is exploited. Exploit creation and software auditing are two differentbut highly complementaryskill sets. An auditor with a good understanding of exploit development is more effective, as this knowledge is useful for determining the difference between an innocuous bug and a genuine vulnerability. There are many well-documented techniques for exploiting memory corruption vulnerabilities, and this chapter provides a brief introduction to some basic approaches for the Intel x86 architecture (although the concepts are applicable to all architectures). Along with exploit techniques, you learn more details about anti-exploit technologies and strategies for determining exploitability. The coverage is not intended as a definitive guide to exploiting memory corruption vulnerabilities, but it does provide the background you need to understand and appreciate many of the vulnerabilities covered throughout this book. Note Readers interested in learning more about exploiting memory corruption vulnerabilities should pick up The Shellcoder's Handbook (Wiley, 2004) by Jack Koziol et al. or Exploiting Software (Addison-Wesley, 2004) by Greg Hoglund and Gary McGraw. You can also find numerous online resources about exploitation techniques, such as phrack magazine (www.phrack.org) and Uninformed magazine (www.uninformed.org).

Race Conditions

Race Conditions UNIX applications have to be very careful when interacting with the file system, because of the danger of race conditions. Race conditions, in general, are situations in which two different parties simultaneously try to operate on the same resource with deleterious consequences. In the context of security flaws, attackers try to manipulate the resource out from underneath the victim. For UNIX file system code, these issues usually occur when you have a process that gets preempted or enters a blocking system call at an inopportune moment. This inopportune moment is typically somewhere in the middle of a sensitive multiple-step operation involving file and directory manipulation. If another process wins the race and gets scheduled at the right time in the middle of this "window of inopportunity," it can often subvert a vulnerable nonatomic sequence of file operations and wrest privileges from the application. Listing 9-3 shows an example. Listing 9-3. Race Condition in access() and open() res = access("/tmp/userfile", R_OK); if (res!=0) die("access"); /* ok, we can read from /tmp/userfile */ fd = open("/tmp/userfile", O_RDONLY); ... This code represents a setuid root program opening the /tmp/userfile file, which can be controlled by users. It uses the access() function to make sure users running the program have permission to read from the /tmp/userfile file. access() is specially designed for setuid programs; it performs the privilege check by using the process's real user ID rather than the effective user ID. For a setuid root program, this is typically the user that ran the executable. If users don't have permission to read /tmp/userfile, the program exits. This call to access() protects the program from following a symbolic link at /tmp/userfile and opening a sensitive file or from opening a hard link to a sensitive file. The problem is that attackers can alter /tmp/userfile after the access() check but before opening the file. Figure 9-7 outlines this attack. Say attackers create an innocuous regular file named /tmp/userfile. They let the preceding code do its access check and come back with a clean result. Then the process gets swapped out, and a process controlled by attackers runs. This evil process can unlink /tmp/userfile and replace it with a symbolic link to /etc/shadow. When the privileged program resumes, it does open("/tmp/userfile", O_RDONLY), which causes it to follow the symbolic link to /etc/shadow. The privileged program then reads in the shadow password file, which likely leads to an exposure of sensitive information later on. Figure 9-7. Program flow for Listing 9-3 Auditing Tip The access() function usually indicates a race condition because the file it checks can often be altered before it's actually used. The stat() function has a similar problem. TOCTOU The concept of exploiting the discrepancy between a security check on a resource and the use of a resource is known as a time of check to time of use (TOCTOU or TOCTTOU) issue. This concept doesn't apply to just file manipulation. Any time that the state of a resource can change in between when an access check is done and when an action is performed on it creates an opportunity for TOCTOU attacks. If you refer to Figure 9-7, you can see the time of check and time of use labeled for clarity. It might seem unrealistic that a program could get swapped out at the exact moment for attackers to take advantage of this "window of inopportunity." Remember that attackers are determined and resourceful, and it's usually safe to bet they can find some way to exploit even an improbable vulnerability. In the scenario depicted in Figure 9-7, attackers could take action in the background to try to slow down the system, such as a network-intensive flood of data or heavy use of the file system. They could also send job control signals to the setuid root program that is performing the potentially dangerous file operations to stop and start it constantly in a tight loop. Depending on the file system, they might be able to watch for access times on files that are being updated or even watch the progress of the setuid program through system-specific interfaces. There's plenty of system-specific functionality that can be leveraged with some creativity. For example, Linux 2.4 and later has a flag that can be used with the fcntl() function, F_NOTIFY, that causes a signal to be delivered to your program when certain actions occur in a directory. Several advanced race condition exploits for Linux make use of this flag. The stat() Family of Functions Many of the TOCTOU examples you encounter feature the use of stat() or one of its variations. These functions are designed to give the caller extensive information about a file. The three primary functions that return this information are stat(), lstat(), and fstat(). The stat() function has the following prototype: int stat(const char *pathname, struct stat *buf); The pathname parameter specifies the file to be checked and the buf parameter points to a structure that's filled in with file information. lstat() works similarly, except, as noted in "Symbolic Links," if pathname is a symbolic link, information is returned about the link rather than the link's target. Finally, there is fstat(), which takes a file descriptor rather than a pathname. Of these functions, fstat() is the most resilient function in terms of race conditions, as it's operating on an previously opened file. The information returned in the stat structure includes most of the statistics about a file that might be useful to developers. Information returned includes, but is not limited to, the owner of the file, the owning group of the file, the number of hard links to the file, and the type of the file. By examining the type of the file, it is possible to use these functions to determine whether a file is really a regular file, a link file, a device file, and so on. The following macros are defined for testing the file type: S_ISREG tests if the file is a regular file. S_ISDIR tests if the file is a directory. S_ISCHR tests if the file is a character device. S_ISBLK tests if the file is a block device. S_ISFIFO tests if the file is a named pipe. S_ISLNK tests if the file is a symbolic link. S_ISSOCK tests if the file is a socket. As you have probably guessed, a standard method for protecting against link-based attacks is to use lstat() on a requested filename and either explicitly check if it's a link, or check if it's a regular file and fail if it is not. Say a privileged program wants to work with a file but wants to make sure it isn't going to be tricked into following a symbolic link. Listing 9-4 shows some code from the Kerberos 4 library that's used by a kerberized login daemon. Listing 9-4. Race Condition from Kerberos 4 in lstat() and open() errno = 0; if (lstat(file, &statb) < 0) goto out; if (!(statb.st_mode & S_IFREG) #ifdef notdef || statb.st_mode & 077 #endif ) goto out; if ((fd = open(file, O_RDWR|O_SYNC, 0)) < 0) goto out; This code uses lstat() to check whether the file is a symbolic link. If it isn't, the program knows it's safe to open the file. However, what happens if attackers replace the file with a symbolic link after the lstat() call but before the open() call? It causes a TOCTOU situation. The potential attack is shown in Figure 9-8. In this vulnerability, attackers are able to overwrite arbitrary files as root when the kerberized login daemon creates new tickets. (Note that this code is also vulnerable to a hard link attack because it doesn't check the link count lstat() returns.) Figure 9-8. Program flow for Listing 9-4 Note that it's possible to have a race condition if you do things in the opposite order, with the check coming after the use, as shown in Listing 9-5. Listing 9-5. Race Condition in open() and lstat() fd = open(fname, O_RDONLY); if (fd==-1) perror("open"); if (lstat(fname, &stb1) != 0) die("file not there"); if (!S_ISREG(stbl.st_mode)) die("its a symlink"); ... It might seem as though this program isn't susceptible to a race condition because it opens the file first, and then checks whether it's valid. However, it suffers from a similar problem. Attackers can create the malicious symbolic link the program opens, and then delete or rename that symbolic link and create a normal file with the same name. If they get the timing right, lstat() operates on the normal file, and the security check is passed. The kernel doesn't care if the file that fd indexes has been deleted or renamed. As long as the file descriptor is kept open, the file and its corresponding inode in the file system stay available. This process is shown in Figure 9-9. Figure 9-9. Program flow for Listing 9-5 Here's another example of a race condition from an old version of the SunOS binmail program, discovered by a rather clever hacker group known as "8 Little Green Men," or 8lgm for short. Binmail runs as root and is used to deliver mail to local users on the system. This local mail delivery is performed by opening the user's mail spool file in a public sticky directory and appending the new mail to that file. The following code is used to open the mail spool file: if (!(created = lstat(path, &sb)) && (sb.st_nlink != 1 || S_ISLNK(sb.st_mode))) { err(NOTFATAL, "%s: linked file", path); return(1); } if ((mbfd = open(path, O_APPEND|O_WRONLY|O_EXLOCK, S_IRUSR|S_IWUSR)) < 0) { if ((mbfd = open(path, O_APPEND|O_CREAT|O_WRONLY|O_EXLOCK, S_IRUSR|S_IWUSR)) < 0) { err(NOTFATAL, "%s: %s", path, strerror(errno)); return(1); } } This program first checks to see whether the mail spool is a symbolic link or a hard link by performing an lstat(). If the file doesn't exist or looks like a normal file, binmail attempts to open the file for appending. If the open fails, binmail attempts to open the file again, but it tells the OS to create the file if it doesn't exist. The problem is the race condition between the lstat() call and the open() call. Attackers can place an innocuous file there or delete the mail spool, wait for the lstat() to occur, and then place a symbolic link or hard link pointing to a sensitive file. The mail sent to that user is appended to the sensitive file, if it exists; if it doesn't, it's created as root and written to. Furthermore, a symbolic link pointing to a target file that isn't present can be used to have binmail create an arbitrary file as root. (This bug is documented in a bugtraq post by 8lgm, archived at http://seclists.org/bugtraq/1994/Mar/0025.html.) File Race Redux Most file system race conditions can be traced back to using system calls that work with pathnames. As discussed, every time a system call takes a pathname argument, the kernel resolves that pathname to an inode by traversing through the relevant directory entries. So if you have this code: stat("/tmp/bob", &sb); stat("/tmp/bob", &sb); The first call to stat() causes the kernel to look up the inode for the /tmp/bob pathname, open that inode, and collect the relevant information. The second time stat() is called, the same thing happens all over again. If someone changes /, /tmp, or /tmp/bob between the two stat() calls, the system could easily end up looking at two different files. Now take a look at this code: fd=open("/tmp/bob", O_RDWR); fstat(fd, &sb); fstat(fd, &sb); The call to open() resolves the /tmp/bob pathname to an inode. It then loads this inode into kernel memory, creates the required data structures to track an open file, and places a pointer to them in the process's file descriptor table. The call to fstat() simply takes the file descriptor index fd, looks in the table and pulls out the pointer, and ends up looking directly at the data structure encapsulating the inode. The second fstat() does the same thing as the first one. If someone unlinked /tmp/bob in the middle of the fstat() calls, it wouldn't matter because the file descriptor would still reference the inode on the disk that was /tmp/bob when open() was called. That inode isn't deallocated until its reference count goes away, which doesn't happen until the process uses close(fd). Renaming and moving the file doesn't change the target of fstat(), either. The permissions are established by how the file is opened and the security checks occurring at the time it's opened, so even if the file is marked with permission bits 0000, it doesn't matter to the process after it has successfully opened the file for reading. Pathnames Versus File Descriptors The basic difference between pathnames and file descriptors is in how they're used by functions. Functions that take pathnames are looking up which file to work with each time they're called. Functions that work with file descriptors are going straight to the same inode that was opened initially. Any time you see multiple system calls that use a file path, it's worth considering what would happen if the file was changed in between those calls. Remember that changing any directory component between the starting directory and the target file can potentially disrupt a process's intended file actions. In general, if you see anything besides a single filename-based system call to open a resource followed by multiple file-descriptor-based calls, there's a reasonable chance of a race condition occurring. Evading File Access Checks One basic pattern to look for is a security check function that uses a filename followed by a usage function that uses a filename. The basic vulnerability pattern is the file being checked using something like stat(), lstat(), or access(), and, providing that the check succeeds using something like open(), fopen(), chmod(), chgrp(), chown(), unlink(), rename(), link(), or symlink(). In general, the safe form of a security check involves checks and usage on a file descriptor. It's guaranteed that a file descriptor, after the kernel creates it, refers to the same file system object for the duration of its lifetime. Therefore, functions that work with a file descriptor can often be used in a safe fashion when their filename counterparts can't. For example, fstat(), fchmod(), and fchown() can be used to query or modify a file that has already been opened safely, but the corresponding stat(), chmod(), and chown() functions might be susceptible to race conditions if the file is tampered with right after it has been opened. Permission Races Sometimes an application will temporarily expose a file to potential modification for a short window of time by creating it with insufficient permissions. If attackers can open that file during this window, they get an open file handle to the file that locks in the insufficient permissions, and lets them retain access to the file after the permissions have been corrected, as shown in this example: FILE *fp; int fd; if (!(fp=fopen(myfile, "w+"))) die("fopen"); /* we'll use fchmod() to prevent a race condition */ fd=fileno(fp); /* lets modify the permissions */ if (fchmod(fd, 0600)==-1) die("fchmod"); This code excerpt opens a file for reading and writing by using the fopen() function. If the file doesn't already exist, it's created by the call to fopen(), and the umask value of the process determines its initial file permissions. This will be discussed in more detail in "The Stdio File Interface," but the important detail that need to know for now is that fopen() calls open() with a permission argument of octal 0666. Therefore, if the process's umask doesn't take away world write permissions, any user on the file system is able to write to the file. The program immediately changes its file to mode 0600, but it's too latea race condition has already occurred. If another process can use open() on the file requesting read and write access, immediately after it's created but before its permission bits are changed, that process has a file descriptor open to the file with read and write permissions. Ownership Races If a file is created with the effective privileges of a nonprivileged user, and the file owner is later changed to that of a privileged user, a potential race condition exists, as shown in this example: drop_privs(); if ((fd=open(myfile, O_RDWR | O_CREAT | O_EXCL, 0600))<0) die("open"); regain_privs(); /* take ownership of the file */ if (fchown(fd, geteuid(), getegid())==-1) die("fchown"); This code is similar to the permission race code you examined previously. A privileged application temporarily drops its privileges to create a file safely. After the file is created, it wants to set file ownership to root. To do this, the program regains its root privileges and then changes the file's ownership with the fchown() system call. The vulnerability is that if unprivileged users manage to open the file between the call to open() and the call to fchown(), they get a file descriptor with a file access mask permitting read and write access to the file. Directory Races Programs that traverse through directories in the file system have to be careful about trusting the integrity of the directory hierarchy. If a program descends into user-controllable directories, users can often move directories around in devious ways from under the program and cause it to operate on sensitive files inadvertently. Caveats If a program attempts to recurse through directories, it needs to account for infinitely recursive symbolic links. The kernel notices infinite symbolic links as it resolves a pathname, and it returns an error in the case of too much recursion. If a program attempts to traverse a path itself, it might need to replicate the logic the kernel uses to avoid ending up in an infinite loop. Another possible point of confusion that you need to be aware of is that symbolically linked directories are not reflected in pathnames returned by system calls that retrieve a current path. If you're using a command shell and issue cd to change to a directory that's a symbolic link, typing pwd reflects that symbolic link. However, from the kernel's perspective, you're in the actual target directory, and any system call to return your current path doesn't include the symbolic link. If a symbolic link named /bob points to the /tmp/bobshouse directory, and you change your current directory to /bob, the getcwd() function reports your current directory to you as /tmp/bobshouse, not /bob. Directory Symlinks for Exploiting unlink() It's important to consider the effects of malicious users manipulating directories that are one or two levels higher than a process's working space. Wojciech Purczynski discovered a vulnerability in the Solaris implementation of the UNIX job-scheduling at command. The -r argument to at tells the program to delete a particular job ID. According to Wojciech, at had roughly the following logic: logic for /usr/bin/at -r JOBNAME /* chdir into at spool directory */ chdir("/var/spool/cron/atjobs") /* check to make sure that the file is owned by the user */ stat64(JOBNAME, &statbuf) if (statbuf.st_uid != getuid()) exit(1); /* unlink the file */ unlink("JOBNAME") The at command changes to the atjobs spool directory, and if users own the file corresponding to the job they specify, the job file is deleted. The first vulnerability in at is that the job name can contain ../ path components. So attackers could use the following command: at -r ../../../../../../tmp/somefile The at command would delete /tmp/somefile, but only if somefile is owned by the user. So you can use it to delete files you own, which isn't all that interesting. However, there's a race condition between the call to stat() and the call to unlink() in the code. Keep in mind that unlink() doesn't follow symbolic links on the last directory component. So if you use the normal attack of putting a normal file for stat() to see, deleting it, and placing a symlink to the sensitive file, the unlink() call would just delete the symbolic link and not care what it pointed to. The trick to exploiting this code is to remember that unlink() follows symbolic links in directory components other than the last component. This attack is shown in Figure 9-10. Figure 9-10. Attacking the Solaris at command First, attackers create a /tmp/bob directory, and in that directory create a normal file called shadow. The attackers let at run and perform the stat() check on the /tmp/bob/shadow file. The stat() check succeeds because it sees a normal file owned by the correct user. Then attackers delete the /tmp/bob/shadow file and the /tmp/bob directory. Next, they create a symbolic link so that /tmp/bob points to /etc. The at command proceeds to unlink /tmp/bob/shadow, which ends up unlinking /etc/shadow and potentially bringing down the machine. Moving Directories Underneath a Program Wojciech Purczynski also discovered an interesting vulnerability in the GNU file utils package. The code is a bit complicated, so the easiest way to show the issue is show the program's behavior at a system call trace level. The following code is based on his advisory (archived at http://seclists.org/bugtraq/2002/Mar/0160.html): Example of 'rm -fr /tmp/a' removing '/tmp/a/b/c' directory tree: (strace output simplified for better readability) chdir("/tmp/a") = 0 chdir("b") = 0 chdir("c") = 0 chdir("..") = 0 rmdir("c") = 0 chdir("..") = 0 rmdir("b") = 0 fchdir(3) = 0 rmdir("/tmp/a") = 0 If you have a directory tree of /tmp/a/b/c, and you tell rm to recursively delete /tmp/a, it basically recurses into the deepest directory /tmp/a/b/c, and then uses chdir("..") and removes c. The rm program then uses chdir("..") to back up one more directory and delete b. Next, it uses fchdir() to go back to the original starting directory and delete /tmp/a. Wojciech's attack is quite clever. Say you let the program get all the way into the c directory, so it has a current working directory of /tmp/a/b/c. You can modify the directory structure before rm uses chdir(".."). If you move the c directory so that it's underneath /tmp, the rm program is suddenly in the /tmp/c directory instead of /tmp/a/b/c. From this point, it recurses upward too far and starts recursively removing every file on the system. Note Nick Cleaton discovered similar race conditions in the fts library (documented at http://security.freebsd.org/advisories/FreeBSD-SA-01:40.fts.asc), which is used to traverse through file systems on BSD UNIX derivatives. He's quite clever, too, even though he's not Polish.

6.4 From Execution to Conservative Flow Analysis

6.4 From Execution to Conservative Flow Analysis

Data flow analysis algorithms can be thought of as a kind of simulated execution. In place of actual values, much smaller sets of possible values are maintained (e.g., a single bit to indicate whether a particular variable has been initialized). All possible execution paths are considered at once, but the number of different states is kept small by associating just one summary state at each program point (node in the control flow graph). Since the values obtained at a particular program point when it is reached along one execution path may be different from those obtained on another execution path, the summary state must combine the different values. Considering flow analysis in this light, we can systematically derive a conservative flow analysis from a dynamic (that is, run-time) analysis.

As an example, consider the "taint-mode" analysis that is built into the programming language Perl. Taint mode is used to prevent some kinds of program errors that result from neglecting to fully validate data before using it, particularly where invalidated data could present a security hazard. For example, if a Perl script wrote to a file whose name was taken from a field in a Web form, a malicious user could provide a full path to sensitive files. Taint mode detects and prevents use of the "tainted" Web form input in a sensitive operation like opening a file. Other languages used in CGI scripts do not provide such a monitoring function, but we will consider how an analogous static analysis could be designed for a programming language like C.

When Perl is running in taint mode, it tracks the sources from which each variable value was derived, and distinguishes between safe and tainted data. Tainted data is any input (e.g., from a Web form) and any data derived from tainted data. For example, if a tainted string is concatenated with a safe string, the result is a tainted string. One exception is that pattern matching always returns safe strings, even when matching against tainted data - this reflects the common Perl idiom in which pattern matching is used to validate user input. Perl's taint mode will signal a program error if tainted data is used in a potentially dangerous way (e.g., as a file name to be opened).

Perl monitors values dynamically, tagging data values and propagating the tags through computation. Thus, it is entirely possible that a Perl script might run without errors in testing, but an unanticipated execution path might trigger a taint mode program error in production use. Suppose we want to perform a similar analysis, but instead of checking whether "tainted" data is used unsafely on a particular execution, we want to ensure that tainted data can never be used unsafely on any execution. We may also wish to perform the analysis on a language like C, for which run-time tagging is not provided and would be expensive to add. So, we can consider deriving a conservative, static analysis that is like Perl's taint mode except that it considers all possible execution paths.

A data flow analysis for taint would be a forward, any-path analysis with tokens representing tainted variables. The gen set at a program point would be a set containing any variable that is assigned a tainted value at that point. Sets of tainted variables would be propagated forward to a node from its predecessors, with set union where a node in the control flow graph has more than one predecessor (e.g., the head of a loop).

There is one fundamental difference between such an analysis and the classic data flow analyses we have seen so far: The gen and kill sets associated with a program point are not constants. Whether or not the value assigned to a variable is tainted (and thus whether the variable belongs in the gen set or in the kill set) depends on the set of tainted variables at that program point, which will vary during the course of the analysis.

There is a kind of circularity here - the gen set and kill set depend on the set of tainted variables, and the set of tainted variables may in turn depend on the gen and kill set. Such circularities are common in defining flow analyses, and there is a standard approach to determining whether they will make the analysis unsound. To convince ourselves that the analysis is sound, we must show that the output values computed by each flow equation are monotonically increasing functions of the input values. We will say more precisely what "increasing" means below.

The determination of whether a computed value is tainted will be a simple function of the set of tainted variables at a program point. For most operations of one or more arguments, the output is tainted if any of the inputs are tainted. As in Perl, we may designate one or a few operations (operations used to check an input value for validity) as taint removers. These special operations always return an untainted value regardless of their inputs.

Suppose we evaluate the taintedness of an expression with the input set of tainted variables being {a,b}, and again with the input set of tainted variables being {a,b,c}. Even without knowing what the expression is, we can say with certainty that if the expression is tainted in the first evaluation, it must also be tainted in the second evaluation, in which the set of tainted input variables is larger. This also means that adding elements to the input tainted set can only add elements to the gen set for that point, or leave it the same, and conversely the kill set can only grow smaller or stay the same. We say that the computation of tainted variables at a point increases monotonically.

To be more precise, the monotonicity argument is made by arranging the possible values in a lattice. In the sorts of flow analysis framework considered here, the lattice is almost always made up of subsets of some set (the set of definitions, or the set of tainted variables, etc.); this is called a powerset lattice because the powerset of set A is the set of all subsets of A. The bottom element of the lattice is the empty set, the top is the full set, and lattice elements are ordered by inclusion as in Figure 6.12. If we can follow the arrows in a lattice from element x to element y (e.g., from {a} to {a,b,c}), then we say y > x. A function f is monotonically increasing if

Figure 6.12: The powerset lattice of set {a,b,c}. The powerset contains all subsets of the set and is ordered by set inclusion.

Not only are all of the individual flow equations for taintedness monotonic in this sense, but in addition the function applied to merge values where control flow paths come together is also monotonic:

If we have a set of data flow equations that is monotonic in this sense, and if we begin by initializing all values to the bottom element of the lattice (the empty set in this case), then we are assured that an iterative data flow analysis will converge on a unique minimum solution to the flow equations.

The standard data flow analyses for reaching definitions, live variables, and available expressions can all be justified in terms of powerset lattices. In the case of available expressions, though, and also in the case of other all-paths analyses such as the one we have called "inevitability," the lattice must be flipped over, with the empty set at the top and the set of all variables or propositions at the bottom. (This is why we used the set of all tokens, rather than the empty set, to initialize the Avail sets in Figure 6.7.)

Section 8.4. Example: A Toggle Button

[Page 365] 8.4. Example: A Toggle Button The ability to extend an existing class is one of the most powerful features of object-oriented programming. It allows objects to reuse code defined in the superclasses without having to redefine or recompile the code. As we saw in Chapter 4, a programmer-defined applet, such as GreeterApplet, uses the public methods defined for JApplets, JPanels, Containers, Components, and Objects simply because it is a subclass of JApplet (Fig. 4.11). By the same token, it can use all of the public and protected instance variables and constants defined in these classes by simply referring to them in its own code. Reusing code In this section, we present an example of how inheritance can be used to extend and customize the functionality of a Java library class. As we saw in Chapter 4, a JButton is a GUI component that can be associated with a particular action by implementing the ActionListener interface. For example, we used a JButton in the GreeterApplet to generate a greeting to the user. In this section, we will design a more sophisticated button. We will call it a ToggleButton and define it as a JButton subclass that toggles its label whenever it is clicked, in addition to carrying out some kind of associated action. Problem decomposition A light switch behaves similarly to a ToggleButton in this sense. Whenever you flick a light switch, it changes its label from "on" to "off," but it also turns the lights on or off. Although different switches are associated with different lights, every light switch toggles its label each time it is clicked. So let's design a ToggleButton that behaves like a light switch. The main idea in our design is that a ToggleButton is a JButton that has two labels. By default, a JButton has just a single label. Thus, because of the type of behavior we want to elicit, we need to define ToggleButton as a subclass of JButton with two String variables that will serve as its alternative labels (Fig. 8.8). Note that we give it a constructor method that will allow us to provide the initial value of its two label strings. Another important feature of a ToggleButton is that it should act as its own ActionListener so that it can toggle its label whenever it is clicked. Therefore, it must also implement the ActionListener interface. Figure 8.8. A ToggleButton is a JButton with two labels. The complete definition of ToggleButton is given in Figure 8.9. Note how we have defined its constructor. Recall that the JButton class has a constructor method with the signature JButton(String), which allows us to set a JButton's label during instantiation. We need to do the same thing with one of ToggleButton's two labels. That is, when we create a ToggleButton, we want to initialize its label to one of its two alternative labels (here, "On" or "Off"). [Page 366] Figure 8.9. Definition of the ToggleButton class. import java.awt.*; import java.awt.event.*; import javax.swing.*; public class ToggleButton extends JButton implements ActionListener { private String label1; // Toggle between two labels private String label2; public ToggleButton(String l1, String l2) { // Constructor super(l1); // Use l1 as the default label label1 = l1; label2 = l2; addActionListener(this); } public void actionPerformed(ActionEvent e) { String tempS = label1; // Swap the labels label1 = label2; label2 = tempS; setText(label1); } // actionPerformed() } // ToggleButton class Because constructor methods are not inherited by the subclass, we want to invoke the superclass's constructor in the ToggleButton() constructor using the super keyword. This must be done as the first statement in the ToggleButton() constructor. By passing l1 to the superconstructor, we are making the first string that the user gives us the default label for our ToggleButton. This will be the label that appears on the button when it is first displayed in the applet. Note also in the ToggleButton() constructor that the ToggleButton is designated as its own ActionListener, so whenever it is clicked, its actionPerformed() method will be invoked. The actionPerformed() method exchanges the button's current label for its other label. Swapping two values in memory is a standard programming practice used in many different algorithms. In order to do it properly, you must use a third variable to temporarily store one of the two values you are swapping. The comments in actionPerformed() provide a step-by-step trace of the values of the three variables involved. Swapping algorithm Java Programming Tip: Swapping Values It is necessary to use a temporary variable whenever you are swapping two values of any type in memory. The temporary variable holds the first value while you overwrite it with the second value. The first statement in actionPerformed() creates a temporary String variable named tempS and assigns it the value of label1. Recall that label1 was the button's initial label. To make this example easier to follow, let's suppose that initially label1 is "off" and label2 is "on". After line 1 is executed, both tempS and label1 contain "off" as their value. Line 2 then assigns label2's value to label1. Now both label1 and label2 store "on" as their value. In line 3 we assign tempS's value to label2. Now label2 stores "off" and label1 stores "on", and we have effectively swapped their original values. Swapping values requires a temporary variable [Page 367] The next time we invoke actionPerformed(), label1 and label2 will have their opposite values initially. Swapping them a second time will assign them their initial values again. We can continue toggling their values in this way indefinitely. To complete the method, the last statement in actionPerformed() assigns label1's current value as the new ToggleButton's label. Now that we have seen that a ToggleButton toggles its label between two values, what about performing an associated action? To do this, we need a design involving multiple event handlers, one to handle the toggling of the button's label and the other to handle its associated action (Fig 8.10). In this design, lightSwitch has two listeners that respond to its events: the lightSwitch itself, as a result of the actionPerformed() method in its class, and the ToggleApplet, as a result of the actionPerformed() method in this class. Figure 8.10. The ToggleButton has two ActionListeners. When the button is clicked, the JVM will call each listener's actionPerformed() method, and each listener will take its own independent action. Multiple event handlers The implementation of this design is given by ToggleApplet, an applet that uses a ToggleButton (Fig. 8.11). Like the applet we designed in Chapter 4, this applet extends the JApplet class and implements the ActionListener interface. In this example we use a ToggleButton to simulate a light switch. Note that we assign the applet itself as an ActionListener for the lightSwitch, so that when lightSwitch is clicked, the applet displays the message "The light is on" or "The light is off" in its status bar (Fig. 8.12). This is a somewhat trivial action, but it illustrates that a ToggleButton both toggles its own label and carries out some associated action. [Page 368] Figure 8.11. Definition of the ToggleApplet class. (This item is displayed on page 367 in the print version) import java.applet.*; import java.awt.*; import java.awt.event.*; import javax.swing.*; public class ToggleApplet extends JApplet implements ActionListener { private ToggleButton lightSwitch; public void init() { lightSwitch = new ToggleButton ("off","on"); getContentPane().add(lightSwitch); lightSwitch.addActionListener(this); } // init() public void actionPerformed(ActionEvent e) { showStatus("The light is " + lightSwitch.getText()); } // actionPerformed() } // ToggleApplet class Figure 8.12. When clicked, ToggleApplet button causes "The light is on" or "The light is off" to appear in the applet's status bar. The ToggleButton design satisfies several key design principles of object-oriented programming. First and foremost, it uses inheritance to extend the functionality of the predefined JButton classthe extensibility principle. Second, it encapsulates a ToggleButton's essential behavior within the ToggleButton class itselfthe modularity principle. Finally, it hides the mechanism by which a ToggleButton manages its labelsthe information-hiding principle. Object-oriented design principles Effective Design: Inheritance Inheritance enables you to specialize an object's behavior. A ToggleButton does everything a JButton does, plus it can toggle its own label. Self-Study Exercises Exercise 8.9 Write a code segment (not a whole method) to swap two boolean variables, b1 and b2. Exercise 8.10 Suppose you are designing an applet that plays a card game, and you want a single button that can be used both to deal the cards and to collect the cards. Write a code segment that creates this type of button, adds it to the applet, and designates the applet as its ActionListener.

Example: A Socket-Based Server with New Features

Example: A Socket-Based Server with New Features serverSK, Program 12-2, is similar to serverNP, Program 11-3, but there are several changes and improvements. Rather than creating a fixed-size thread pool, we now create server threads on demand. Every time the server accepts a client connection, it creates a server worker thread, and the thread terminates when the client quits. The server creates a separate accept thread so that the main thread can poll the global shutdown flag while the accept call is blocked. While it is possible to specify nonblocking sockets, threads provide a convenient and uniform solution. It's worth noting that a lot of the extended Winsock functionality is designed to support asynchronous operation, and Windows threads allow you to use the much simpler and more standard synchronous socket functionality. The thread management is improved, at the cost of some complexity, so that the state of each thread is maintained. This server also supports in-process servers by loading a DLL during initialization. The DLL name is a command line option, and the server thread first tries to locate an entry point in the DLL. If successful, the server thread calls the DLL entry point; otherwise, the server creates a process, as in serverNP. A sample DLL is shown in Program 12-3. If the DLL were to generate an exception, the entire server process would be destroyed, so the DLL function call is protected by a simple exception handler. In-process servers could have been included in serverNP if desired. The biggest advantage of in-process servers is that no context switch to a different process is required, potentially improving performance. The server code is Windows-specific, unlike the client, due to thread management and other Windows dependencies. Program 12-2. serverSK: Socket-Based Server with In-Process Servers /* Chapter 12. Client/server. SERVER PROGRAM. SOCKET VERSION. */ /* Execute the command in the request and return a response. */ /* Commands will be executed in process if a shared library */ /* entry point can be located, and out of process otherwise. */ /* ADDITIONAL FEATURE: argv [1] can be name of a DLL supporting */ /* in-process servers. */ #define _NOEXCLUSIONS #include "EvryThng.h" #include "ClntSrvr.h" /* Defines request and response records. */ struct sockaddr_in SrvSAddr; /* Server's socket address structure. */ struct sockaddr_in ConnectSAddr; /* Connected socket. */ WSADATA WSStartData; /* Socket library data structure. */ typedef struct SERVER_ARG_TAG { /* Server thread arguments. */ volatile DWORD number; volatile SOCKET sock; volatile DWORD status; /* Explained in main thread comments. */ volatile HANDLE srv_thd; HINSTANCE dlhandle; /* Shared library handle. */ } SERVER_ARG; volatile static ShutFlag = FALSE; static SOCKET SrvSock, ConnectSock; int _tmain (DWORD argc, LPCTSTR argv []) { /* Server listening and connected sockets. */ BOOL Done = FALSE; DWORD ith, tstatus, ThId; SERVER_ARG srv_arg [MAX_CLIENTS]; HANDLE hAcceptTh = NULL; HINSTANCE hDll = NULL; /* Initialize the WSA library, Ver 2.0, although 1.1 will work. */ WSAStartup (MAKEWORD (2, 0), &WSStartData); /* Open command library DLL if specified on command line. */ if (argc > 1) hDll = LoadLibrary (argv [1]); /* Initialize thread arg array. */ for (ith = 0; ith < MAX_CLIENTS; ith++) { srv_arg [ith].number = ith; srv_arg [ith].status = 0; srv_arg [ith].sock = 0; srv_arg [ith].dlhandle = hDll; srv_arg [ith].srv_thd = NULL; } /* Follow standard server socket/bind/listen/accept sequence. */ SrvSock = socket (AF_INET, SOCK_STREAM, 0); SrvSAddr.sin_family = AF_INET; SrvSAddr.sin_addr.s_addr = htonl ( INADDR_ANY ); SrvSAddr.sin_port = htons ( SERVER_PORT ); bind (SrvSock, (struct sockaddr *) &SrvSAddr, sizeof SrvSAddr); listen (SrvSock, MAX_CLIENTS); /* Main thread becomes listening/connecting/monitoring thread. */ /* Find an empty slot in the server thread arg array. */ /* status values: 0 -- slot is free; 1 -- thread stopped; 2 -- thread running; 3 -- stop entire system. */ while (!ShutFlag) { for (ith = 0; ith < MAX_CLIENTS && !ShutFlag; ) { if (srv_arg [ith].status==1 || srv_arg [ith].status==3) { /* Thread stopped, normally or by shutdown request. */ WaitForSingleObject (srv_arg[ith].srv_thd INFINITE); CloseHandle (srv_arg[ith].srv_thd); if (srv_arg [ith].status == 3) ShutFlag = TRUE; else srv_arg [ith].status = 0; /* Free thread slot. */ } if (srv_arg [ith].status == 0 || ShutFlag) break; ith = (ith + 1) % MAX_CLIENTS; if (ith == 0) Sleep (1000); /* Break the polling loop. */ /* Alternative: use an event to signal a free slot. */ } /* Wait for a connection on this socket. */ /* Separate thread so we can poll the ShutFlag flag. */ hAcceptTh = (HANDLE)_beginthreadex (NULL, 0, AcceptTh, &srv_arg [ith], 0, &ThId); while (!ShutFlag) { tstatus = WaitForSingleObject (hAcceptTh, CS_TIMEOUT); if (tstatus == WAIT_OBJECT_0) break; /* Connection made. */ } CloseHandle (hAcceptTh); hAcceptTh = NULL; /* Prepare for next connection. */ } _tprintf (_T ("Server shutdown. Wait for all srvr threads\n")); /* Terminate the accept thread if it is still running. * See the Web site for more detail on this shutdown logic. */ if (hDll != NULL) FreeLibrary (hDll); if (hAcceptTh != NULL) TerminateThread (hAcceptTh, 0); /* Wait for any active server threads to terminate. */ for (ith = 0; ith < MAX_CLIENTS; ith++) if (srv_arg [ith].status != 0) { WaitForSingleObject (srv_arg[ith].srv_thd, INFINITE); CloseHandle (srv_arg[ith].srv_thd); } shutdown (SrvSock, 2); closesocket (SrvSock); WSACleanup (); return 0; } static DWORD WINAPI AcceptTh (SERVER_ARG * pThArg) { /* Accepting thread that allows the main thread to poll the */ /* shutdown flag. This thread also creates the server thread. */ LONG AddrLen, ThId; AddrLen = sizeof (ConnectSAddr); pThArg->sock = accept (SrvSock, /* This is a blocking call. */ (struct sockaddr *) &ConnectSAddr, &AddrLen); /* A new connection. Create a server thread. */ pThArg->status = 2; pThArg->srv_thd = (HANDLE) _beginthreadex (NULL, 0, Server, pThArg, 0, &ThId); return 0; /* Server thread remains running. */ } static DWORD WINAPI Server (SERVER_ARG * pThArg) /* Server thread function. Thread created on demand. */ { /* Each thread keeps its own request, response, and bookkeeping data structures on the stack. */ /* ... Standard declarations from serverNP omitted ... */ SOCKET ConnectSock; int Disconnect = 0, i; int (*dl_addr)(char *, char *); char *ws = " \0\t\n"; /* White space. */ GetStartupInfo (&StartInfoCh); ConnectSock = pThArg->sock; /* Create a temp file name. */ sprintf (TempFile, "%s%d%s", "ServerTemp", pThArg->number, ".tmp"); while (!Done && !ShutFlag) { /* Main command loop. */ Disconnect = ReceiveRequestMessage (&Request, ConnectSock); Done = Disconnect || (strcmp (Request.Record, "$Quit") == 0) || (strcmp (Request.Record, "$ShutDownServer") == 0); if (Done) continue; /* Stop this thread on "$Quit" or "$ShutDownServer". */ hTmpFile = CreateFile (TempFile, GENERIC_READ | GENERIC_WRITE, FILE_SHARE_READ | FILE_SHARE_WRITE, &TempSA, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL); /* Check for a DLL command. For simplicity, shared */ /* library commands take precedence over process commands. First, extract the command name. */ i = strcspn (Request.Record, ws); /* Length of token. */ memcpy (sys_command, Request.Record, i); sys_command [i] = '\0'; dl_addr = NULL; /* Will be set if GetProcAddress succeeds. */ if (pThArg->dlhandle != NULL) { /* Try server "in process." */ dl_addr = (int (*)(char *, char *)) GetProcAddress (pThArg->dlhandle, sys_command); if (dl_addr != NULL) __try { /* Protect server process from exceptions in DLL. */ (*dl_addr) (Request.Record, TempFile); } __except (EXCEPTION_EXECUTE_HANDLER { ReportError (_T ("Exception in DLL"), 0, FALSE); } } } if (dl_addr == NULL) { /* No in-process support. */ /* Create a process to carry out the command. */ /* ... Same as in serverNP ... */ } /* ... Same as in serverNP ... */ } /* End of main command loop. Get next command. */ /* End of command loop. Free resources; exit from the thread. */ _tprintf (_T ("Shutting down server# %d\n"), pThArg->number); shutdown (ConnectSock, 2); closesocket (ConnectSock); pThArg->status = 1; if (strcmp (Request.Record, "$ShutDownServer") == 0) { pThArg->status = 3; ShutFlag = TRUE; } return pThArg->status; } A Security Note This client/server system, as presented, is not secure. If you are running the server on your system and someone else knows the port and your system name, your system is at risk. The other user, running the client, can run commands on your system that could, for example, delete or modify files. A complete discussion of security solutions is well beyond this book's scope. Nonetheless, Chapter 15 shows how to secure Windows objects, and Exercise 1214 suggests using SSL.

< Day Day Up >

---

Chapter 5: Pole Placement

 Download CD Content

5.1 Introduction

In this chapter, I introduce the pole placement design method, which allows the designer to locate the closed-loop system poles at arbitrarily selected points in the complex plane. With an appropriate choice of pole locations, the closed-loop system can exhibit any response speed and damping characteristics desired. This assumes the plant and actuators are capable of producing an approximately linear response and some enabling conditions on the plant are satisfied.

However, this design freedom comes at a small cost. The control algorithm used in pole placement assumes that the full internal state of the plant is known at all times. Most often, this is not the case. In a typical design, perhaps only one of several internal state variables is measured. The values of the unmeasured states must be estimated during controller operation.

An observer (also called a state estimator) performs the task of estimating the complete set of state variables internal to the plant. The observer develops state estimates on the basis of the measured plant outputs and the known plant inputs.

Two restrictions on the structure of the plant model must be satisfied for the pole placement design method to succeed. The first requires that the actuators be capable of driving the system in a manner that allows control of all modes of behavior. This property is called controllability. The other restriction is that the sensors must measure sufficient system parameters to enable construction of a complete state estimate. This is called observability. Some straightforward tests of the plant model will determine whether it is controllable and observable.

This design approach is applicable to MIMO systems as well as to SISO systems. The same general state-space model form is used for SISO and MIMO systems, and the steps in the design method are applicable in both situations.

The pole placement design method uses some fairly complex matrix algorithms for controller and observer design. The MATLAB Control System Toolbox provides robust implementations of these algorithms. The algorithms themselves will not be discussed here. Instead, I cover the steps necessary to apply the commands in the Control System Toolbox for pole placement design.