Skip to content

Month: March 2018

Conway’s Game of Life (JavaScript)

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.

.

Video recording of simulation, live demo can be found here.

Conway’s Game of Life is awesome for being the simplest example of artifical life. It implements a rule-based system for determining whether elements in a grid should be alive or dead, with a very simple rule system. But like with DNA or Ant Colonies (read about it!) a simple set of rules can result in an amazing array of diverse behaviour.

Conway’s Game of Life isn’t hard to implement, and seems like a great target for optimisation. The logic is pretty simple, we need a grid of cells. A lot of people
use two-dimensional arrays for this, but I opted for a 1D array where the rows/columns are calculated through a translation function. Each cell contains a value of 0 or 1 for dead or alive.

The Code

class Grid {
  constructor() {
    this.grid = new Uint8Array(GRID_SIZE);
    this.next = new Uint8Array(GRID_SIZE);
    this.init();
  }

  dump() {
    return this.next;
  }
  swap() {
    this.grid = this.next;
    this.next = new Uint8Array(GRID_SIZE);
  }
  at(x, y) {
    return y * GRID_WIDTH + x;
  }
  init() {
    this.grid = fast_random(GRID_SIZE);
  }

The first part of the Grid class, the main meat of the code, is pretty simple. The Grid stores a current grid and a next grid, which is updated and then swapped with the current one during animation cycles. When the Grid is initialized it grabs GRID_SIZE bits using the fast_random function (more on this later).

Survival Function

For each cell within the “grid”, we need to calculate the number of neighbours to figure out its fate in the next generation. The rules for the game are as follows:

Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overpopulation.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

 

  update() {
    for (let x = 0; x < GRID_WIDTH; x++) {
      for (let y = 0; y < GRID_WIDTH; y++) {
        let score = 0;
        const CURRENT_LOCATION = this.at(x, y);
        for (let i = -1; i < 2; i++) {
          for (let j = -1; j < 2; j++) {
            if (i == 0 && j == 0) {
              // skip self
            } else {
              score += this.grid[this.at(x + i, y + j) % GRID_SIZE];
            }
          }
        }

Here we’re just looping over every cell of the grid, and for each of the cells adding up the 1s in the surrounding 8 cells. From this we can figure out whether it’s going to be alive or dead based on its current state and its neighbour count:

        switch (this.grid[CURRENT_LOCATION]) {
          case 0:
            if (score == 3) {
              this.next[CURRENT_LOCATION] = 1;
            } else {
              this.next[CURRENT_LOCATION] = 0;
            }
            break;
          case 1:
            if (score > 3 || score < 2) {
              this.next[CURRENT_LOCATION] = 0;
            } else {
              this.next[CURRENT_LOCATION] = 1;
            }
            break;
        }
      }

Pretty simple!

Rendering the Output

I wanted to write several potential renderers to test what gave the best performance. Each simply takes a grid as an array and draws it.

const renderer = RectangleRenderer;
render = new renderer();
let grid = new Grid();

function iterate() {
  grid.update();
  render.render(grid.dump());
  grid.swap();
  requestAnimationFrame(iterate);
}

var ctx;
$(document).ready(function() {
ctx = $("#game-view")[0].getContext("2d");
iterate();
});

Initial Optimisations

Ok so, one problem. With a 256×256 grid the initial start-up takes up to 9 seconds. Some quick JS Profiling in chrome seemed to indicate that the culprit was the init() function.

The init() function was seeding the grid by iterating over the entire grid’s X/Y coordinates and filling each cell with a random 0 or 1. But in order to do this, the Math.random() function was being called for each cell (meaning it needs to be called 65535 times) as the following:

  cell = Math.floor(Math.random()*2)

As it turns out this is extremely wasteful. In theory, each call to Math.random() could be used to supply up to 32 unique bits per call, which would reduce the number of calls significantly. After implementation, the init() function began to run almost instantaneously:

function random_byte() {
  let el = Math.round(Math.random() * (Number.MAX_SAFE_INTEGER/2) + Number.MAX_SAFE_INTEGER/2);
  let bits = [];
  static_counter += 1;

  while (el > 1) {
    let bit = Math.floor(el % 2);
    bits.push(bit);
    el = el / 2;
  }

  return bits;
}

function fast_random(size) {
  let array = [];

  while (array.length < size) {
    let c = random_byte();
    array = array.concat(c);
  }

  return array.slice(0,size);
}

With this function added, the initial delay disappeared entirely for a 256x256 grid. In the next article I'm going to look at some of the algorithms used in speeding up the Game of Life as an implementation level.

Ruby’s Array#map_with_index and each_with_index in Javascript

#each_with_index and #map_with_index are commonly used Ruby features that can be easily achieved in JavaScript

Each with index

In Ruby we can do this:

x = ["a","b","c","d","e"]

x.each_with_index { |el,n| puts "#{n} is #{el}" }

Output:

0 is a
1 is b
2 is c
3 is d
4 is e

In Javascript it’s possible to do something very similar. The documentation for JavaScript’s Array.forEach function states that the three arguments passed to the callback function are:

callback is invoked with three arguments:

the element value
the element index
the array being traversed

Therefore we can do this:

let array = ["a","b","c","d","e","f"];

array.forEach((x,n) => (console.log(x + " is " + n)));
a is 0
b is 1
c is 2
d is 3
e is 4
f is 5

Map with index

In Ruby it’s possible to do this:

x = ["a","b","c","d","e","f"]

z = x.map.with_index { |el,n| (el.ord + n).chr }

puts z

Output:

a
c
e
g
i
k

Similar to with forEach, Map has the following arguments passed to its function argument:

currentValue

The current element being processed in the array.

indexOptional

The index of the current element being processed in the array.

arrayOptional

The array map was called upon.

Which makes it possible to do this:

let array = ["a","b","c","d","e","f"];

let new_array = array.map((x,n) => String.fromCharCode(x.charCodeAt(0)+n));

console.log(new_array);

Output

[ 'a', 'c', 'e', 'g', 'i', 'k' ]

Pwnable.kr CTF writeup: level 6 – random

This one turned out to be surprisingly easy. What’s required is an understanding of random number generators, and how they’re not really random. Implementations of random number generators are known as PRNGs, acknowledging that they are pseudo random number generators. They use various tricks in order to produce streams of not obviously connected numbers, but without an understanding of how they’re meant to work it can be easy to produce a problem similar to the one described in this CTF.

Code

#include

int main(){
unsigned int random;
random = rand(); // random value!

unsigned int key=0;
scanf("%d", &key);

if( (key ^ random) == 0xdeadbeef ){
printf("Good!\n");
system("/bin/cat flag");
return 0;
}

printf("Wrong, maybe you should try 2^32 cases.\n");
return 0;
}

Pretty simple to understand, we have two variables, random and key. A decimal value is read into key through scanf, and rand() assigns a “random” number to the variable ‘random’. We then XOR the values and if the result is 0xdeadbeef we give up the flag. In theory, this should be hard to beat. Wouldn’t we have to keep trying values until we happen to get the right one? And with such a large problem space, that could take a very long time.

Key Insight

The most important thing to recognise is that this is incorrect use of the rand() function. Using PRNG correctly involves “seeding” the generator with a value that changes frequently, a common tactic is to use the current timestamp supplied to srand (there are some issues with this too, see if you can figure them out). This leads to predictable behaviour, which becomes a problem when knowing the random value allows us to exploit the behaviour. A list of historical examples of where this has been used in real-world attacks can be found on wikipedia’s page on random number generator attacks

Since the rand() call isn’t seeded, it’s fairly trivial to check the value of a few runs of the program in GDB. Setting a breakpoint for the next line after the call to rand() makes it easy to observe what’s returned from the function into the RAX register (the one used to store return values traditionally). A few runs through and it’s easy to see that this value doesn’t change. Due to failure to seed the PRNG it’s returning the exact same value each time, which happens to be 0x6b8b4567. Now we have the following simple equation to solve: something XOR 0x6b8b4567 = 0xdeadbeef. The value we’re looking for will be 0xdeadbeef XOR 0x6b8b4567, which ends up being = 0xb526fb88 which is 3039230856. Let’s try it:

random@ubuntu:~$ ./random 
3039230856
Good!
Mommy, I thought libc random is unpredictable...