06 September 2008

Boggle Solver

I've been working on a pet project with App Engine to try and get a better feel for it. It’s a Boggle puzzle solver that does some AJAXy tricks to multithread the solving work. The source code is online as well for anyone that’s curious. (There is a popular knockoff called “Scramble” on Facebook that is either different enough to keep Hasbro from filing a lawsuit or Hasbro’s lawyers are waiting around for them to make some money before bothering.)

In the case of App Engine it's particularly sensitive to requests that take “too long” to process. This was a particular hassle when I was importing the dictionary that is used. In order to solve a Boggle puzzle fairly quickly you want to have all the possible words arranged in a trie. This way you can stop quickly if you’re following letters that will never spell anything as you traverse the puzzle board. It took splitting the dictionary into 5000 separate pieces to get it to load without pushing me over my quota for “long” requests. Luckily we only have to do that once.

Next came the challenge of the puzzle solving itself. Again, solving the whole board in one request takes a while to process, apparently more than is allowed without running into that “long” request quota. Even in an optimized form (see the links to Dan Vanderkam’s work at the end of this entry), the full dictionary trie is 3MB and that takes a non-trivial amount of time to load in when you’re trying to handle requests within a few hundred milliseconds.

The solution was to reload the dictionary again but this time to break it up by initial trigrams. For every initial three letters, I store the appropriate shard of the dictionary (all the words that start with that combination) as a trie. There is also a blacklist of trigrams that form no words (for instance “frw”).

The javascript calls in with a copy of the puzzle and a point on the board to solve from. The server code then finds all the trigrams starting from the specified point and loads the appropriate dictionary shards. Since we're only solving from one point on the board there won't be more than 72 shards to load for any javascript call. (9 directions from the point and then 8 directions from each of those points because we're not allowed to backtrack.) The server then traverses the board using the dictionary tries hunting for words. When it finds them it stores the word and the places on the board where the word was found.

This information is all reduced into JSON and returned back to the browser that made the javascript call. The javascript on the browser is then responsible for taking all the found words and locations and sorting them in a sane way and displaying them for the end user.

Dan Vanderkam has written some interesting code and blog posts about optimizations in solving Boggle puzzles.

20 July 2008

Seven our new Rottweiler

Our newest addition is Seven, a 4 year old Rottweiler that we adopted from King County Animal Control in Bellevue. She’s not exactly a petite dog at 105 pounds and her snorts and grunt and growls belie her girlish charm and friendliness. Here she is with her backpack full of water bottles and dog supplies ready to go for a tromp.



Our understanding of her history is that she was bred in order to sell the puppies and one day the breeder asked the neighbors to watch the dog for a week, while they were going to be out of town and they never came back. Unfortunately the neighbors also couldn’t keep Seven because they were moving to a city with a breed ban against Rottweilers. As an aside, that's a ridiculous law since a recent study showed that the most aggressive breeds are actually Dachshunds and Chihuahuas, with Jack Russell Terriers rounding out the top three. Rottweilers and Pit Bulls were average or below average in aggression towards strangers amongst the breeds shown. Apparently some people in Seattle are clamoring for breed bans, but not on aggressive breeds like Chihuahuas, but instead on Pit Bulls. Luckily some sane owners have banded together and Pasado’s Safe Haven has also gotten involved.

After recovering from her spay surgery Seven is doing well and seems to be enjoying her new home. She trained incredibly quickly to the invisible fence and gets along with one of our cats, Jasmine, who isn’t being an idiot around her. Odie still needs to learn that waiting until the dog gets close and then running away like prey is a bad idea.

Just yesterday Seven had her first class at Cascade K9. The object lesson right now is getting her “walk” under better control so she doesn’t try to run out ahead. We also need to get a bench for her to hop up on to practice “climb” at home. As always, the most important element in dog training is the humans, so we’ll try hard to be up to the challenge and we’ll report the progress we make…

23 November 2007

Fred is Gone

Our trusted companion of the last couple years is gone. Fred came to us from Pasado's Safe Haven, rescued from death row at a local shelter. After we heard from vets that he only had months left, he proceeded to live two years of enthusiastic tromps in the snow, trips to the beach and hikes in the woods or just around the neighborhood. Slowly though, the degenerative myelopathy which afflicted him claimed his ability to control the back half of his body. Despite this, he soldiered on determined to follow his pack leaders and have fun doing it, until recently when he turned melancholy because he simply couldn't manage any more.

In his last hours we went, sat and relaxed along a sandy rivershore, watched the waves and the trees move and felt the breeze. He was treated to a special meal out and then we let him go. It is sad to lose him, but hopefully the two years we were able to provide him were as enjoyable for him as they were for us.

01 November 2007

Security Advisory: Norton AntiVirus for Macintosh

Synopsis


Symantec's Norton AntiVirus for Macintosh (NAV) contains a vulnerability that can lead to local privilege escalation from group admin to root (the super-user) without any of the usual password prompts Mac OS X presents for gaining super-user access. Group admin includes any users with the "Allow this user to administer this computer" box checked, this generally includes the first user created in an OS X install. This vulnerability is caused by a setuid-root binary in NAV which automatically runs another binary in a location where it can be replaced by users with group admin permissions. Since most Mac OS X users are in group admin on their computers, most NAV users will be vulnerable.


Mitigation


The easiest (and most foolproof) mitigation strategy is to uninstall NAV. (I sure don't feel very secure when a vendor allows a local privilege escalation vulnerability to fester in their security software for over 9 months. Your feelings may vary.)


Set the sticky bit on all directories between the vulnerable binary and the filesystem root that are writable by group admin. This can be done in Terminal.app with sudo chmod +t / /Library /Library/Application\ Support /Library/Application\ Support/Symantec /Library/Application\ Support/Symantec/SmallScanner.app etc. Keep in mind that running "Repair Permissions" on your disk will remove this change and leave your NAV install vulnerable once again. Apple has set the sticky bit on / and /Library by default on Mac OS X 10.5, but not /Library/Application Support and obviously not on the directories that NAV is installed into.


What Symantec Had to Say


The last time I heard from Symantec was August 29th:



As you know, Symantec developers reviewed the issue concerning NAV for the Mac that you sent to us, and agreed that there is cause for concern. However, they felt that the same problem could potentially affect other vendor’s[sic] software as well. We contacted Apple Product Security, and suggested some changes that could improve security for everyone.
...
Symantec does not currently plan to make changes to our existing products to directly address the problem you reported. The changes would require considerable architectural modifications for those products, and the changes could cause other problems for those products if Apple subsequently release an OS update to address the underlying problem.
...

Timeline


Just in case people think the vendor didn't have enough time to address this, here's the timeline:


  • 2007-Jan-16 - Reported issue to Symantec

  • 2007-Jan-17 - Symantec will "review as soon as possible"

  • 2007-Jan-31 - Symantec "working on planning a fix", will coordinate release when product update has ETA

  • 2007-Apr-20 - Symantec thinks it would be better if Apple made changes to Mac OS X to fix the problem in NAV

  • 2007-Jun-21 - Contacted Apple for status

  • 2007-Jun-22 - Apple communicates the changes they're going to make for Leopard. These changes are not enough to workaround Symantec's vulnerable software.

  • 2007-Aug-29 - Symantec says they've made suggestions to Apple, but otherwise aren't going to do anything to fix this issue (see the quote in the previous section)

  • 2007-Oct-01 - It turns out that Apple's Leopard builds at the time didn't do enough to cover up the vulnerability in NAV

  • 2007-Oct-11 - Contacted Symantec and Apple to let them know I was going to post this Nov-1

  • 2007-Nov-1 - Today.



Details


SmallScanner is run as root by the setuid-root binary
/Library/Application Support/Symantec/AntiVirus/DiskMountNotify.app/Contents/MacOS/DiskMountN
otify
. E.g. after inserting a data cdrom:
root 8734 28.9 -2.1 616152 43596 ?? U 7:51PM 0:16.13
/Library/Application Support/Symantec/AntiVirus/SmallScanner.app/Contents/MacOS/SmallScanner


Unfortunately /Library/Application Support/ is writable by group admin and by
mv'ing the Symantec subdirectory out of the way and installing a tree of
symlinks in its place except for malware in place of SmallScanner arbitrary
code can be executed as root. That is you can trampoline from group admin to
user root. (There were a variety of other ways to do this that were coming out
of the woodwork back in January.)



Using the symlink method described above to replace SmallScanner with the following shell script...

#!/bin/sh

touch /tmp/uhoh.this.is.very.bad.news
exec /Library/Application\ Support/Norton\ Solutions\ Support/Norton\ AntiVirus/SmallScanner.
app/Contents/MacOS/SmallScanner


And then inserting a disk (or using hdiutil to mount a disk image) results in normal looking behavior along with a new file...
-rw-r--r-- 1 root wheel 0 Jan 15 20:10 /tmp/uhoh.this.is.very.bad.news


Etc.


I'd like to thank the Apple Product Security team for being more forthright in their communication with me on this issue, it was a lot better than my previous interactions. I'd like to apologize to all the users that have been unknowingly insecure for the past 289 days, I think I like full disclosure better too given the way vendors seem to drag their feet.