Python Decorators

Just as a reminder for myself in case I ever forget how Python decorators work: This blog post gives an understandable and also concise introduction to decorators. It is very clear in describing how they work and what they are useful for. So if you have not used decorators so far, this might be a trigger for you to start using them.

Estimating Pi Using Random Samples

Programming languages usually come with defined values of pi. However, if you want to estimate it yourself, there is a very simple way to do so.
The area of a circle is given by \[A_c = \pi r^2\]
The area of a square is given by \[A_s = a^2\]
Choose the circle to be the unit circle and the square to be enclosing the circle and draw random numbers that are uniformly distributed over the square. By calculating the ratio of the number n of samples within the circle and all samples N you can get an estimation for pi. a and r are chosen according to above descriptions.
\[pi = \frac{n}{N}\frac{a^2}{r^2} = \frac{n}{N}\frac{2^2}{1^2} = 4\frac{n}{N}\]
In Python numpy this can be done within a few lines of code, in fact you can even condense it to one line.

import numpy as np

def estimate_pi(N):
    rand = 2.0*np.random.rand(2, N) - 1.0
    dist = rand[0,:]*rand[0,:] + rand[1,:]*rand[1,:]
    return np.sum(dist <= 1)*4.0/N

You should choose a large N, as you will get a better and more stable estimate:

Calculating pi using 1000 random samples
pi = 3.092
derivation from numpy.pi =  0.0157858319197

Calculating pi using 100000 random samples
pi = 3.1438
derivation from numpy.pi =  0.000702620184601

Calculating pi using 10000000 random samples
pi = 3.1424128
derivation from numpy.pi =  0.000261060710487

Note: Even if you do not know how to calculate the area of a circle, you still can calculate the area of a circle with an arbitrary radius using this method and then you can figure out that the area is a quadratic function of the radius.

Buffer Overflow Exploit

Yesterday I have been told about the buffer overflow exploit. The idea is very simple and an example can be implemented very easily. Nowadays compilers provide protection against Stack Overflows, still it is a good idea to write your programs overflow safe. The example I show here demonstrates an unsafe password authentiaction, given you disable your compiler's stack protection. Basically, you provide char arrays, that hold the user name and password, and an indicator variable for the result of user name and password comparison.

#include <iostream>
#include <cstring>
using namespace std;

int main (int argc, char** argv) {
  if (argc != 3) {
    return 1;
  }
  char user[10];
  char pass[10];
  int granted(0);
  strcpy(user, argv[1]);
  strcpy(pass, argv[2]);
  if (strcmp(user, "admin") == 0 && strcmp(pass, "pw") == 0) {
    granted = 1;
  }
  if (granted) {
    cout << "Access granted\n";
  } else {
    cout << "Access denied\n";
  }

  return 0;
}

If you are using gcc, your need to disable stack protection:

g++ -fno-stack-protector -o overflow main.cxx

If you choose your user name long enough you cause an overflow and change the value of the variable "granted". In my case the user name needs to be at least 13 characters long.

~ » ./overflow abc 123
Access denied
~ » ./overflow admin 123
Access denied
~ » ./overflow admin pw
Access granted
~ » ./overflow AAAAAAAAAAAAA AA
Access granted

If you build your program with debugging symbols, you can print the value of the variables. For the last case, you will have an output like (granted != 0):

(gdb) print user
$5 = "AAAAAAAAAA"
(gdb) print pass
$6 = "AA\000\000\000\000\000\000\220\006"
(gdb) print granted
$7 = 65

This very simple way of exploiting overflows can be avoided very easily, e.g. length checks, and only works if you disable stack protection. However, it shows the very basic idea behind overflow exploitation and should convince you to write code that is overflow safe.

i3 tiling window manager

These days it just so happened that I got to know of the tiling window manager i3. So far I had only used desktop environments like Gnome, KDE, etc and was currently quite happy with Cinnamon. Nevertheless the concept of a tiling window manager seemed quite convinced to me so I gave it a shot. My impression is that it is very intuitive to use. It has a good multi-screen support and can be configured via plain text in a config file, which makes modification quite easy. It is very helpful for working with an editor when at the same time you want to have a shell and a webbrowser to be visible and accessible, so I do recommend it for any programmer.

Depending on your OS you might even have a version in your repos. Unfortunately, the version I found in the Linux Mint 12 repos is quite old. With Ubuntu 12.04 you will have access to a newer version.

If you want to check it out yourself, go to http://i3wm.org/ or just install it from your repos.

Update: I added a screenshot (version 3.e-bf3 (2011-05-08)) with emacs, shell and chrome.