Programming Philosophy Security web-design

Breaking Rapidshare's Annoying Captcha the Easy Way

Like many others, I got stuck in front of Rapidshare’s captcha. After more than five attempts at reading different letters with kittens and other critters hidden behind them, I was thinking of giving up. Especially because each time I failed I had to wait a half a minute again. However, in one instance I went *back* via my browser, and tried solving the same captcha again. Turns out this works, and I got the file.

I know I could probably have solved it in a smarter fashion, but it wasn’t worth the effort.

My lesson:

When someone writes crappy software, their software is probably crappy in more than one way.

This is not the first time I’ve seen this happen.


Fat Spider

Remember them two bugs? I was playing with that fold the other day, and with a little squeezing I came up with this critter:

Origami fat_spider

Read on for the full instructions.

Graphics Programming Python

Python + Curses + Numpy -> Ascii Art Rotating Cube

Well, the title says it all, or at least most of it.
If you are still not convinced, a picture’s worth 500 dwords:

        / |\
       /  | \
      /   |  \
    //    |   \\
   /      |     \
  /       \      \
 |       / \      |
 |\     /   \    /|
 | \   /     \\ / |
 |  \ /       //  |
 |  /\       /  \ |
 | /  \\    /    \|
 |/     \  /      |
 /       \/       /
  \       |      /
   \      |     /
    \\    |   //
      \   |  /
       \  | /
        \  /

I’ve been toying with the idea of writing a roguelike, and I thought that it would be really fun if it had an ‘Eye-Of-The-Beholder’ kind of view as well, just in ascii-art. There are plenty of things I wanted to do with ascii-art, since it’s such a nice toy. So I started writing some code, and this is a small test on the way.

Nowadays, when I discuss 3d ascii-art, people usually think about a picture transformed with aalib or something similar. Although it is a (very) nice idea, I think it would be more fun to play with ascii-art directly.

Other playing possibilities include a ray-tracer. You could write some fps with ray-tracing ascii-art graphics, because there are so few pixels.
Maybe I’ll write one, when I get to it.

Oh! The code, what about the code?
Here it is.
A few notes:
1. The code ain’t too pretty, as it is a work in progress that doesn’t get much time invested in it. However, I’d still rather publish it.
2. It uses curses. Under windows you’ll have to get some replacement module.
3. It uses numpy. If you don’t have it already, be sure to get it.
4. Run ‘’. Use the direction keys to rotate the cube, ‘q’ to exit.

Assembly Challenges Programming Testing

Some Assembly Required No. 1

I’ve been working on some of the instruction tests in vial, and I wanted to test the implementation of LOOP variants. My objective was to make sure the vial version is identical to the real CPU version (as discussed here). To achieve this, I had to cover all of the essential behaviors of LOOP.

Well, using the framework Gil and I wrote, I hacked up some code that should cover the relevant cases:

code_template = """
mov edx, ecx ; control the start zf
mov ecx, eax ; number of iterations
mov eax, 0 ; will hold the result, also an iteration counter
    cmp eax, ebx    ; check if we need to change zf
    setz dh
    xor dh, dl      ; if required, invert zf
    inc eax         ; count the iteration
    cmp dh, 0       ; set zf
    loop%s loop_start
for loop_kind in ['','z','nz']:
    code_text = code_template % loop_kind
    c = FuncObject(code_text)
    for start_zf_value in [0,1]:
        for num_iters in [1,4,10]:
            for when_zf_changes in [1,2,15]:
                c(num_iters, when_zf_changes, start_zf_value)

Note that c(…) executes the code both on vial’s VM, and on the real cpu. c.check() compares their return value (EAX) and flags after the execution. I also wanted to avoid other kinds of jumps in this test.

To check that the code ran the same number of times, I returned EAX as the number of iterations.
All the games with edx are there to make sure that I’m testing different zf conditions.

The challenge for today:
Can you write a shorter assembly snippet that tests the same thing?

Programming Python Utility Functions

Python Tidbits

Memory Leaks

With the advent of the Python’s garbage collector, it would seem that Python programs should not leak memory. However, this is not always the case. With just a bit of circular references, you can find yourself leaking quite a bit of memory.

A simple example is a bidirectional data structure, like a 2-way linked list, or a tree where the nodes have a reference to their parents. To really free those, you have to break the cycle manually. Another option is to use a weakref for some of the references. (Usually, I like to use weakref.proxy for the parent links.)

An easy way to test code for memory leaks is to run it in a loop (allocate, do job, deallocate, repeat), and call gc.collect() before and after. If the value that gc.collect() returns after the loop grows with the size of the loop, you might have a memory leak.

I found out about a special case of a potential memory leak just the other day.
Let’s say you want to implement some switch code. A common idiom is to write it like this:

def a(x):
    print 'a', x
def b(x):
    print 'b', x
func = {0: a, 1: b}[x]

This works well enough. However, if you do the same thing in a class instance, things start to get messy:

class A(object):
    def __init__(self):
        self.lookup = {0: self.a, 1: self.b}
    def a(self, x):
        print 'a', x
    def b(self, x):
        print 'b', x
    def do_something(self):
        func = self.lookup[x]

In this simple example, __init__ creates a reference cycle. This is because self.a creates a method object on the spot, with a reference to self.
So, if z is an instance of A, our cycle is: z->lookup->z.a->z.

Take heed.
(Note: Some cycles are collectible with gc.collect(). The simple cycle described here is such a case. It may get ugly though.)

While writing the VM for vial, we needed some way to avoid testing assembly code for undefined values.

For example, after executing a div instruction, CF is undefined. We handle this in the templates by writing CF=UNKNOWN(), and we allow to VM to decide on a value. If you need the VM to just execute code, returning 0 for undefined values is fine. If, however, you are testing code, your actual CPU might return a non-zero value, and your test will fail with no real reason.

To solve this problem, our VM may be told to return a special singleton object for undefined values:

class _UndefinedNumber(object):
    def __eq__(self, other):
        if other is self:
            return True
        return False
    def __ne__(self, other):
        return not self == other
    def binary_action(self, other):
        return self
    def unary_action(self):
        return self
    def __str__(self):
        return "Undefined"
    __repr__ = __str__
    (__add__, __sub__, __mul__,
     __div__, __floordiv__, __mod__,
     __pow__, __and__, __xor__,
     __or__, __lshift__, __rshift__,
     __rlshift__, __rrshift__, __radd__,
     __rsub__, __rmul__, __rdiv__,
     __rfloordiv__, __rmod__, __rpow__,
     __rand__, __rxor__, __ror__) = 24*[binary_action]
    (__neg__, __pos__,
     __abs__, __invert__) = 4*[unary_action]
Undefined = _UndefinedNumber()

Now, we test only the flags that are not Undefined. Note that any operation on an Undefined returns an Undefined. This is done to allow registers to be Undefined as well. This way, if AX gets Undefined, so will AH and EAX.

Here is an example:

In [2]: Undefined + 1
Out[2]: Undefined
In [3]: Undefined * 2
Out[3]: Undefined
In [4]: Undefined / Undefined
Out[4]: Undefined

Note that this constant might behave a bit strangely. For example, Undefined * 0 is Undefined, and Undefined – Undefined is also Undefined. Because of that, I’m not sure using this object in production circumstances is a good idea, so in the meantime, this is just a testing utility.

Design Programming Python

Issues in writing a VM – Part 3 – State and Memory

When implementing the VM, I had to keep track of state. The state of the VM includes the registers, virtual variables and memory. Fortunately, keeping track of state information is pretty easy. Basically, it amounts to having a dict, where the keys are registers or variables, and the values are, well, their values.

Holding the state of registers is a bit involved by the fact that registers may overlap, as I mentioned in a previous article. To handle this, the class keeping track of the state information, upon seeing a request to change the value of a register, propagates this change to its parent and child registers.

Holding memory might be different though. At a first glance, it would seem that memory should be kept in some buffer. However, it is much easier to keep the memory in a python dict as well, and treat that dict as if it was a sparse array. This implementation allows programs to write at address 10, and at address 10000, without requiring the VM to keep track of all the addresses in between. (Of course, we are not going to implement paging just now :)

I really liked this idea of treating dicts as sparse lists. In fact, it could work even better with some tree data structure instead of a hash table. With a tree data structure your keys would be sorted, and you could do slices.
I went ahead and tried using tree data structures for this, but it seems to be more trouble than it’s worth, so I think that unless it becomes a real timing issue, I’ll let it go.

I did have some fun wrapping the memory in some class to abstract away the data structure, and to give it a few more capabilities:

In [2]: import vm
In [3]: m = vm.VMMemory()
In [4]: m.set(0, "hello world!\r\n")
In [5]: m.set(51, "foobar, foobar\x00")
In [6]: m.set(77, "a"*30)
In [7]: print m
0000: 68656c6c6f20776f726c64210d0a????  hello world!..??
0033: 666f6f6261722c20666f6f62617200??  foobar, foobar.?
004d: 61616161616161616161616161616161  aaaaaaaaaaaaaaaa
005d: 6161616161616161616161616161????  aaaaaaaaaaaaaa??
Algorithms Assembly decompilation Programming

First Code Transformation: Removing Flag Computations

Short introduction to code transformations

If you intend to write a decompiler, you’ll find yourself writing code transformations.
In our context, code transformations are operations that take as input an expression tree, and return an equivalent but different expression tree.

An equivalent expression tree is one that does the same thing as the original. More formally, it’s an expression tree that when run, will reach the same final state as the original expression tree.

Here’s a simple example, converting a while loop to a do-while loop:


while cond:


if cond:
    while cond

Code transformations are a very tricky business. You may find yourself changing the meaning of your expression trees without noticing. That’s one of the reasons we wrote the VM: we wanted to make sure that our code transformations will be correct.

Generally, you’ll want to transform your code to a somewhat ‘better’ version. ‘Better’ in what sense?
Well, the code may be:

  • More readable. A good purpose, as we are writing a decompiler for human beings. Unfortunately, this goal is not well defined. ‘More readable’ will have to be defined by heuristics.
  • Shorter/smaller. An easier goal to define, smaller code has the following advantages:
    • It might be faster to execute.
    • It might faster to process by other algorithms – after all, it is shorter.
    • It might be more readable.
  • Simpler, in the sense that it uses less types of operations. For example, take transforming a while to a do-while (shown above). If we wanted to analyze loops, it will allow us to write code to handle just do-while loops, instead of handling both cases.

There are many more possible goals for code transformations. The bottom line is that code transformations may do any of the following:
* Make the life of the human reader easier.
* Make the life of the decompiler programmer easier.
* Make the life of the decompiler easier.

An important aspect of code transformations is when to do them. Here is a good rule of thumb:

If it makes it harder for the programmer or the decompiler – it should be done as late as possible.
Otherwise – it should be done as early as possible.

Removing Flag Computations

This is the first code transformation we intend to write. Consider the following case:
sub eax, ebx
sub ebx, ecx

The equivalent expression tree for these two instructions looks something like this:

eax = eax - ebx
zf = eax == 0
ebx = ebx - ecx
zf = ebx == 0

Here I listed only the changes to zf and the actual registers. All the other flags (OF,CF,…) are changed as well. In a sequence of such instructions, all the modifications to the flags in the middle are actually dead code, and may be removed. This transformation will make the code shorter, faster to execute on our VM and faster to analyze by later stages.

This is a special case of dead code removal. This raises a valid question: why not let some general dead code removal transformation handle the flags?

There are a few reasons:

  • A general dead code removal might be more complex to write. Just writing exactly the same algorithm for general purpose registers will be more complicated, because of overlapping registers.
  • This transformation may remove up to 80% of many of the disassembled instructions. Flag calculations take up a lot nodes in the expression trees!
  • This transformation may be run as soon as the disassembly stage itself, while a general dead code removal transformation will not. This is so because of some assumptions we are allowed to make on the way flags behave. For example, an instruction template (“%0=%0-%1; ZF=%0==0” for sub) might have its parameters changed, but the flags affected stay the same.

The implementation of this transformation is not yet complete. When it is, I’ll talk a bit about the mechanics behind it. It is much more complicated than it seems!

Origami Personal

Exam is Done

A few hours ago, I had my exam in functional analysis. This should be the last exam for the semester.
Now I should have more time for my projects.

Currently on my radar: a startup, diStorm, and maybe a website. Of course, I expect the startup to eat a lot of my time. For now I’ll just have to see how it goes.

On another subject, I wanted to show instructions for the origrami lottery-spider. It turns out that this fold is modular in the sense that a piece of 1:n paper generates a critter with n+1 pairs of legs.
Here’s a proof of concept with a ratio of 1:8 (click for a larger version):

origami caterpillar

I’ll be making the instructions as soon as I get new batteries for my camera, and some spare time. (The caterpillar ate my batteries, along with my functional analysis books.)


Short Story: First Hit, Last Hit

I decided to try something a little bit different, and publish a short story I wrote. I’ll be glad to read any comments you might have on the subject, or the story itself. I might upload some more stories to the blog, but I’ll try to keep them technology-related.

Here’s the link to the story.

I actually wrote this one about a year ago, when I was discussing with Gadi his lecture on the bionic man. I thought the subject has a lot of room to play and a lot of security implications to consider. Some of our ideas became a reality when researchers managed to hack into a pace-maker.

Well, I hope this short story never comes true.