Forum

is more than 125 years old. But with four or more pegs, the optimal solution length is not known in general. Using more than 2TB of disk space, we’ve completed breadth-first searches of the four-peg Towers of Hanoi problem with up to 22 discs, a problem with almost 17. 6 trillion states. We’ve also performed disk-based heuristic searches of the problem, confirming a 1941 conjecture due to J.S. Frame and B.M. Stewart about the optimal solutions to these problems for up to 31 discs.

As another example, the sliding-tile Fifteen Puzzle was by many accounts as famous in the 1880s as Rubik’s Cube in the 1980s, as documented by Jerry Slocum and Dic Sonneveld in their book The 15 Puzzle: How It Drove the World Crazy. In 2005, using 1.5TB of disk space, we completed a breadth-first search of the 4x4 Fifteen Puzzle, with more than 10 trillion states. This verified a result due to Adrian Brungger et al. that the most difficult problem instances take 80 moves to solve. We then found that the most difficult instance of the 2x8 Fifteen Puzzle takes 140 moves to solve.

More recently, we considered the pancake problem whose only claim to fame is that it is the subject of a technical paper coauthored by Bill Gates (“Bounds for Sorting By Prefix Traversal” in 1979). In it, we want to sort a stack of pancakes of different sizes using a spatula that flips over the top K pancakes as a group. In another version of the problem, one side of each pancake is burned; in addition to sorting them by size, we now want all burned sides face down. Using

3TB of disk storage, we found the maximum number of moves needed to solve the 14 and 15 unburned pancake problems and the 11 and 12 burned pancake problems. The 15 unburned pancake problem has more than 1. 3 trillion states; the 12 burned pancake problem has almost two trillion states.

In addition to these challenging toy problems, many of these techniques are applicable to real-world problems as well. In particular, most NP-complete problems are combinatorial in nature, and all known methods for solving them optimally involve searching large numbers of states. I agree with Kunkle and Cooperman that the use of magnetic disk can increase the feasible size of memory-limited searches by several orders of magnitude.

RICHARD E. KORF

Los Angeles

Author’s Response:

We thank Korf for his complimentary comment. We have long admired his own use of disk-based parallel computation. We look forward to the popularization of the technology and its increased use in real-world problems.

DANIEL KUNKLE GENE COOPERMAN

Boston

NO ROOM FOR WEAK LINKS IN SECURITY IN DEPTH Hal Berghel’s “Digital Village” column (Apr. 2008) “Faith-Based Security” made valid points and it’s title was somewhat provocative, but I take issue with its treatment of “security in depth.” SID has a simple definition: create a path of multiple sequential steps where the

sum of the least cost-path represents the optimal effort an attacker would have to expend to achieve the target (nefarious) effect.

The key words are “sequential” and “sum.” In terms of simple graph theory, SID forces the attacker to traverse multiple nodes representing independent compromises at cumulative cost across all edges (such as in two-factor authentication). In contrast, a “chain link” defense is only as strong as its weakest link because the attack takes place simultaneously on all nodes, so the compromise of any one of them compromises the entire defense (such as in port scanning). In the case of a physical chain, straining the chain simultaneously places sheering load where each link joins its neighbor. Once the chain breaks anywhere its ability to restrain is gone.

Amazing to me is how many security professionals and managers do not understand the fundamental difference between SID and the chain-link style of protection. Worse, they may think they have a SID architecture when in fact they have only a chain link.

ROBERT J. DUWORS

Bellevue, WA

FORGET WEP; GIVE ME WPA ENCRYPTION The discussion and advice in Alfred Loo’s “The Myths and Truths of Wireless Security” (Feb. 2008) did nothing to dispel the myths, even as it introduced some advice that should not have been included. For example, being told that “Users should turn on the encryption feature in the router” was misleading, as it indicates that