This week, Slam Jam Socialism ran an
online arcade for a chance to win
some Yeezy Boost 350s. My friend Marc sent me the link and asked if I could
hack the leaderboards and cop some shoes. Here’s how I did it.
The game was a single-player version of Pong, written in plain JavaScript
using <canvas>. Each time the ball hits a paddle, you get a point and it
speeds up until you inevitably lose. While playing the game, I had Chrome’s
Network tab open to see how it reported actions to the server.
So: every time you lose, the game sends a POST request to the site at
/callback.php along with some parameters. Most notably, pointz.
So you can just send a new request and set
pointz to 99999, right? As I soon discovered, it’s not that easy. When I
tried it, I got an error message: "Sorry, please try again". Hmm, my request
was almost identical to the legitimate one, though. But what’s sec? It looks
like a random hash…
Turns out that sec stands for secret, and the score is one of the inputs to
the hash. If the server’s hash doesn’t match yours, then your score gets
rejected. The hash must be generated client-side, so I just need to look
through the source to find out where the POST request is sent:
The game is somehow in hex. No, wait—they’re variables but
they just look like memory addresses. That eval is the code that gets executed. We can just console.log
what is getting evaled:
This is a lot better, but it’s still minified. Luckily, there’s jsnice
to prettify it for us:
// some code above...functionstart(){// some code here...over=1;$.ajax({method:"POST",url:"callback-ism.php",data:{action:"setpoint",email:email,pointz:y,sec:s(email,y,token)}}).done(function(opt_classNames){// more code below...
Well that worked way better than I expected. So sec is generated from a function
s, which takes in email, y (which is pointz), and token. What’s s?
The hash is produced from iteratively hashing substrings of my email, the
points I scored, and a token generated on each session that’s set server-side.
Now all that’s left to do is calculate the hash of the number of points I want,
and replace the parameters in the curl request with my new score and hash.
The edit distance between two strings refers to the minimum number of character
insertions, deletions, and substitutions required to change one string to the
other. For example, the edit distance between “kitten” and “sitting” is three:
substitute the “k” for “s”, substitute the “e” for “i”, and append a “g”. Our
particular metric, which allows insertions, deletions, and substitutions is
called the Levenshtein distance (other variants exist, such as the LCS (longest
common subsequence) distance, which disallows substitution). Edit distance is
useful for measuring similarity between strings. Superficial similarity is
implied here, as in: the content and meaning of the words don’t matter; for
semantic similarity, look at Jaccard’s similarity coefficient.
Let’s implement the Wagner-Fischer algorithm, which computes the edit distance
between two strings.
The key insight required to understand this algorithm is – as usual – recursive.
Notice that if we have the edit distance d between two strings minus the first
character, then the actual edit distance will be d + 1 only if the first characters
of both strings are not the same. Take the words “jewels” and “mogwai”: assuming
we have the edit distance between “ewels” and “ogwai” (5), then the actual distance
will be 6, since “j” and “m” are different. We can simply apply this rule until
we hit the end of one (or both) of the strings. Then the edit distance will just
be the length of the remaining string, as we just can add the requisite characters.
The astute reader will notice that there is a mistake in our analysis, however:
we’ve only covered the substitution rule. Evaluating “godspeed” and “speed” using
this rule would result in an edit distance of 8, which is clearly wrong, since
we should be able to do it in 3 moves by deleting “god” from “godspeed”. We can
support suffix alignment by computing our first rule, then the edit distance
between each string and the last n-1 characters of the other plus one, and then
taking the minimum between all of these computations. This essentially ends up
trying each path to see whether we can find a common fragment in both strings
that isn’t necessarily aligned.
However, this is really inefficient because of all the repeated subcomputations.
Running this on the first two sentences of lorem ipsum doesn’t even terminate
in a reasonable amount of time. We can memoize, essentially caching our
subcomputations, which is a top-down dynamic programming strategy:
1
2
3
4
5
6
7
8
9
10
11
12
memo = {}
def levenshtein(s1, s2):
if len(s1) == 0 or len(s2) == 0:
return max(len(s1), len(s2))
if (s1, s2) not in memo:
memo[(s1, s2)] = min(levenshtein(s1[1:], s2) + 1,
levenshtein(s1, s2[1:]) + 1,
levenshtein(s1[1:], s2[1:]) if s1[0] == s2[0]
else levenshtein(s1[1:], s2[1:]) + 1)
return memo[(s1, s2)]
That’s easy, but boring. Plus, there’s still a lot of memory overhead from
the stack frames generated from all the recursion. Let’s take a bottom-up approach
to the problem instead. The actual Wagner-Fischer algorithm uses a two-dimensional
array (or matrix) to hold the edit distances between prefixes of each string.
The array (let’s call it A) has size m by n, where m and n are one plus the
lengths of the first and second strings s1 and s2, respectively. What is stored
at each index i, j is the edit distance between s1[:i] and s2[:j]. Then, from
our work above, we have the following relation:
Notice that the recursive part of the relation depends on the values directly above,
left, and upper left. This means we have to fill in the matrix in a certain order.
My solution works like this:
def levenshtein(s1, s2):
x = len(s1) + 1 # the length of the x-coordinate
y = len(s2) + 1 # the length of the y-coordinate
A = [[-1 for i in range(x)] for j in range(y)]
for i in range(x):
A[0][i] = i
for j in range(y):
A[j][0] = j
for i in range(1, y):
for j in range(1, x):
if s1[j- 1] == s2[i - 1]:
A[i][j] = A[i - 1][j - 1]
else:
A[i][j] = min(
A[i - 1][j] + 1,
A[i][j - 1] + 1,
A[i - 1][j - 1] + 1
)
return A[y - 1][x - 1] # return the edit distance between the two strings
And now you know how to compute the Levenshtein distance! As an exercise, try
reconstructing the actual transformations to go from s1 to s2.
I’m super excited to announce that I will be interning at
Yelp in San Francisco for the upcoming summer! I’ll be
joining the Consumer Team and working all over the stack.
Did you know that the URLs generated in Berri aren’t
short hashes but actually just really uncommon English words? If you
thought your room name was randomly generated because it’s
unrecognizable, it might be interesting to look up what the
definition is. Anyway, getting a list of uncommon words isn’t
too complicated, but it is fun and I wanted to write a blog post
so I’ll show you the nitty gritty.
If we remove all the common words from the set of all words,
then it follows that we are left with only the uncommon ones.
An easy source for the set of all words is /usr/share/dict/words,
which is just a pre-installed file with newline-separated words.
I say easy because everyone already has a copy and because it’s
in a nice, parseable format. Note, however, that it isn’t
necessarily a good dictionary: there are ~20000 words compared
to the Oxford English Dictionary’s ~600000. But I think
it’s a worthwhile tradeoff to not having to scrape the OED.
What about the set of common words? Well, we can scrape some
text from the web, and, if we find a word that’s being used,
we can consider it common enough to throw away. Let’s begin!
It turns out that we don’t need to scrape anything. Data dumps
of all of Wikipedia’s articles are readily available, so let’s
grab the latest one from the Simple Wikipedia data dump. Why
Simple Wikipedia? The Simple English Wikipedia dump is 473 MB
uncompressed, which when compared to the regular English
Wikipedia’s 44 GB uncompressed and considering the amount of
parsing and checking we are going to have to do suddenly seems
very reasonable. It also should contain very commonly-used words. Anyways:
<mediawikixmlns="http://www.mediawiki.org/xml/export-0.9/"xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation="http://www.mediawiki.org/xml/export-0.9/ http://www.mediawiki.org/xml/export-0.9.xsd"version="0.9"xml:lang="en"><siteinfo>
...
</siteinfo><page><title>April</title><ns>0</ns><id>1</id><revision><id>4784983</id><parentid>4657771</parentid><timestamp>2014-04-18T02:15:54Z</timestamp><contributor><ip>61.199.127.79</ip></contributor><comment>made the grammar better</comment><textxml:space="preserve">
'''April''' is the fourth [[month]] of the [[year]], and comes between [[March]] and [[May]]. It has 30 [[day]]s. April begins on the same day of week as [[July]] in all years and also [[January]] in leap years.
...
</text><sha1>jk9e5is1yxp1resnscpooes74s5fnc1</sha1><model>wikitext</model><format>text/x-wiki</format></revision></page>
So all the data is in the <text> tag under <revision> in each
<page>. We can use xsltproc to parse the XML using the following stylesheet:
Save the stylesheet as stylesheet.xsl and run
xsltproc stylesheet.xsl simplewiki-latest-pages-articles.xml > wiki-raw-text.
You can take a look at the output with less wiki-raw-text. It looks like
there’s still some scrubbing to do: we have to remove whitespace and other
non-alphabetic characters and put each word in its own line so we can parse
it the same way as /usr/share/dict/words. Let’s break out some good old UNIX tools.
First, we replace all non-alphabetic characters with spaces:
(If you are on OS X, you will have to download gnu-sed using brew install
gnu-sed for sed to read the newline character.)
Now we’ve got a complete set of words and a set of common words. The running
time for removing the common words from the complete set naively can get as
bad as O(m * n) where m and n are the sizes of the sets. We can do a lot
better using a Trie, which is a super hip data structure optimized for looking up and deleting
strings. Looking up a word in a trie is only O(len(word)), which doesn’t vary
too widely, so removing a set M from the complete set should only take O(M)
(after inserting all words, of course). Here’s my Python implementation of a Trie:
class Trie:
def __init__(self):
self._trie = {"word": ""}
def insert(self, x):
trie = self._trie
for index, char in enumerate(x):
if char not in trie:
trie[char] = {}
trie = trie[char]
if index == (len(x) - 1) :
trie["word?"] = True
return None
def delete(self, x):
trie = self._trie
try:
for index, char in enumerate(x):
trie = trie[char]
if index == (len(x) - 1):
trie["word?"] = False
except KeyError:
return False
return None
def get_all_strings(self):
trie = self._trie
queue = [trie]
lst = []
while queue:
d = queue[0]
current_word = d["word"]
if d.get("word?"):
lst.append(current_word)
d.pop("word?", None)
d.pop("word")
keys = list(d.keys())
for key in keys:
d[key]["word"] = current_word + key
queue.append(d[key])
queue.pop(0)
return lst
And my Python script that adds all the words to the trie, removes the
ones we’ve parsed, and prints out the remaining ones:
1
2
3
4
5
6
7
8
9
10
11
12
from trie import Trie
dicttrie = Trie()
with open("dict-parsed") as dictfile, open("wiki-parsed-text") as wikifile:
for line in dictfile:
word = line.rstrip("\n")
dicttrie.insert(word)
for line in wikifile:
word = line.rstrip("\n")
dicttrie.delete(word)
for word in dicttrie.get_all_strings():
print(word)
Now:
python3 words.py > uncommon-words
And there you have it. uncommon-words now contains the most uncommon words in the dictionary, such as
joskin
kendir
glazily
rubelet
suiform
bursicle
Cool beans.
Edit: My friend Jay pointed out that using the built-in set type was much faster than
using a trie:
1
2
3
4
5
6
7
8
9
10
with open("dict-parsed") as dictfile, open("wiki-parsed-text") as wikifile:
all_words = set()
for line in dictfile:
word = line.rstrip("\n")
all_words.add(word)
common_words = set()
for line in wikifile:
word = line.rstrip("\n")
common_words.add(word)
print(all_words - common_words)
takes about 1.5 seconds versus my trie-based implementation, which took 37 seconds.
But that is lame and boring and I implemented a really cool data structure for a real-world application so who’s really the winner here Jay?
Hi, I’m Lawrence. I’m a Computer Science student at the
University of Toronto. I’m interested in startups, software
development, programming languages, and systems design.
