Last time, I wrote about a brute force web crawler. This time, I'm writing about an elegant web crawler. As you would expect from elegant code, I didn't write it.
The Pirates BATH game had a pregame website. Teams could log in to the web site. There was a web form which I'd programmed before I'd dropped out of Game Control. This web form allowed teams to "search for treasure": enter a string of text. Game Control gave them some strings of text that they could enter: entering one of those into the web form yielded puzzles. When a team solved the puzzle, the answer was a phrase: entering the phrase into the web form yielded a hint which would be useful during the upcoming game.
If they entered text that wasn't a puzzle and wasn't an answer, they were told that they'd found nothing. And if they paid attention, they also noticed some black dots, some white dots, and some xs. These were a "Mastermind" puzzle. If they entered a nonsense phrase, a program figured out which "useful" word was closest; it would then display one white dot for each letter in the correct place; a black dot for each correct letter in the wrong place; an X for each incorrect letter. So if "BELOW" was a word and someone entered "BLOW", they'd see a white dot (for the B), three black dots (for L, O, and W), and an X (for the E).
This was the way to find one game hint: no puzzles solved to the correct word for this hint. But four puzzles gave words that didn't actually yield hints--but instead were just near to the word to enter for this special hint.
What if a team just tried to guess every possible text string? They could guess A B C ... Y Z AA AB AC ... ZY ZZ AAA AAB AAC ... Of course, that would take a long time. It would probably take less time to just solve the puzzles.
So I was kind of surprised when my pager started buzzing one day: BATH Game Control was sending me messages: Team Scoobies had set up a bot to crawl the server! The Scoobies had found puzzles that they couldn't have found!
I looked over the logs. There was a program crawling the system, but the Scoobies weren't running it. Team Blood was running it. The bot was not brute-forcibly checking every possible text string. It was playing Mastermind!
It would guess "A". If it got back a white dot, it knew that at least one word started with A. If it got back a white dot, it knew that at least one word started with A. (A white dot meant right letter in right place.) Next it would try try AA AB AC AD AE ... AZ. If AA returned just one white dot (not two), then the bot knew no words started with AA (e.g., no word was AARDVARK). So it never tried AAA AAB AAC... Thus, it didn't need to check so many things. Thus, elegance.
When I reported my findings to Game Control, they decided that this thing must be stopped. Though it was elegant, what if it allowed the team to bypass puzzles? Game Control figured that this would be unfair.
Hmm, how to stop the bot without disrupting other teams? How did the bot work? Team Blood was running it. Rich Bragg captained Team Blood. I worked at the same company as Rich. Maybe he'd written this program while at work? And maybe he'd left the program somewhere where I could find it? I thought about it: If I were Rich and I'd written this program at work, where would I have put the source code? I looked there: no program. Then I tried my second guess and saw a file: piratebath.py. Bingo. It was a web crawler, a very specialized web crawler.
#!/usr/bin/python2.4
import cookielib
import re
import time
import urllib2
def Login():
print "Logging in..."
cj = cookielib.CookieJar()
opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cj))
opener.open("http://www.piratesbath.com/log_in.php",
"access_login=blood&access_password=bythepint")
return opener
def NumMatches(html_data, substring):
matches = re.findall(substring, html_data)
if not matches:
return 0
return len(matches)
def NumLettersCorrect(html_data):
return NumMatches(html_data, "dot_white.gif")
def FoundTreasure(html_data):
return NumMatches(html_data, "No treasure found.") == 0
def SearchOne(opener, results, query):
data = opener.open("http://www.piratesbath.com/search.php?q=" +
query).read()
letters_correct = NumLettersCorrect(data)
print "Query:", query, "had", letters_correct, "of", len(query), "letters"
all_correct = letters_correct == len(query)
if all_correct and FoundTreasure(data):
print "Found:", query
results.append(query)
return all_correct
def SearchAll(opener, results, query_prefix = ''):
alphabet = list('abcdefghijklmnopqrstuvwxyz')
for letter in alphabet:
if SearchOne(opener, results, query_prefix + letter):
SearchAll(opener, results, query_prefix + letter)
def Run(query_prefix = ''):
opener = Login()
results = []
SearchAll(opener, results, query_prefix)
print "Results: ", len(results), "words starting with '%s'" % query_prefix
for word in results:
print word
Run()
Aha, the code was checking for text in the page: dot_white.gif and No treasure found. If I just added some visible-to-bots-but-invisible-to-humans text like that, I could fool the bot into mis-counting white dots or what-have-you. So that's what I did. (Security-minded folks in the audience might say: uhm, but what about stopping the general case of bots? Yeah, I set up code for that too, but wanted to let Game Control configure it to say how much guessing was "too much", and that took a while. Fooling Rich's bot--that was a quick-n-dirty fix.)
(I notice that this code imports the "time" module, but doesn't use it. I wonder if an earlier version of code politely "slept" a little between queries--but maybe Rich figured out that the server was waiting a second between responding to a team's queries anyhow, and that the sleep was thus not so useful...)
Rich noticed when his bot started generating garbage results. He mailed Game Control to make sure there were no hard feelings. Game Control asked him to stop running it, and he did. He said that this script was basically another monitor: it alerted the team to the presence of new puzzles; thus no-one had to go re-check the piratesbath.com web site each day.
In hindsight, when I programmed that web form, we should have used it only for entering answers, not for getting puzzles. We should have used some other way to distribute puzzles. Thus, a team could monitor that to look for puzzles and Game Control wouldn't need to panic that someone was bypassing the puzzles to get the answers.
Labels: arrr, programming, puzzlehunts