sábado, 22 de diciembre de 2012

Encontrando archivos duplicados con la Shell

Bueno, hablo de parte de las personas que conozco, pero al parecer los programadores de python detestan a Ruby. En vista esto, decidí hacer una entrada acerca de la entrada anterior, pero ahora, usando herramientas del sistema.

Utilizando La Orden Find Y Perl
Modo de invocación
find . -type f -exec sha1sum '{}' \; | perl script.pl
Fichero auxiliar, guárdese como script.pl, asegúrate de pasar la la dirección absoluta de este archivo a Perl.
use strict;

my %hsh = ();
while(<STDIN>) {
        /^([a-f0-9]+)\s+(.+)$/;
        print "$2\n";
        if( not $hsh{$1}) {
                @{$hsh{$1}} = ($2);
        } else {
                push @{$hsh{$1}}, $2
        }
}

print "\n\nDuplicates!\n\n";
for(keys %hsh) {
        next if(@{$hsh{$_}}==1); 
        print(join("\n  -> ", @{$hsh{$_}}));
        print "\n";
}
Utilizando La Orden Find Y AWK
Modo de invocacion
find . -type f -exec sha1sum '{}' \; | awk -f script.awk
Fichero auxiliar, guárdese como script.awk, asegúrate de pasar la la dirección absoluta de este archivo a AWK.
{
        path = substr($0, 41)
        print path
        if(!array[$1]) {
                array[$1]= path
                next
        }

        array[$1] = (array[$1] "\n  ->" path)
        duplicates[$1] = 1
}

END {
        if(!length(duplicates))
                exit

        print "\n\nDuplicates!\n\n"
        for(key in duplicates)
                print array[key] "\n\n"
}
Script Para Bash
Bueno, realmente considero que es un poco más práctico tener un script al que podamos invocar con argumentos, para esto seria conveniente incluir dentro de el  script de Bash el script para Perl, y con la opción -e pasar a Perl el programa como una cadena en vez de un fichero.  Por  motivos de brevedad, estaré utilizando la forma que he venido utilizando en toda la entrada.
#!/bin/bash

# By default, the current working directory is used.
DIR=$PWD

if [[ -n $1 ]]; then
        DIR=$1
fi
find $DIR -type f -exec sha1sum '{}' \; | perl script.pl

miércoles, 19 de diciembre de 2012

Es guay utilizar algoritmos de digest II

En la entrada anterior se habló de como utilizar las funciones hash para proteger un poco más nuestros datos. En esta entrada estaremos utilizando las funciones hash para conseguir los archivos duplicados dentro de nuestro sistema.

El tema de esta entrada es simple, la temática es la siguiente: Se calcula el hash de los datos en este caso de cada archivo y se está pendiente de que dos archivos no tengan la misma función hash, de ser así, se tiene un archivo duplicado y se procede con el procesamiento deseado.

Para ejecutar el siguiente programa se necesita:
  • Ruby
  • La gema Mp3Info
    gem install mp3info 
#!/usr/bin/env ruby
# encoding: utf-8
# Program that looks for duplicate files.
# Author: MaG, http://newbieshell.blogspot.com

require 'digest/sha2'
require 'find'
require 'mp3info'

class FileRecord
     attr_reader :file, :sum, :duplicates
     def initialize(path, sum)
          @file = path
          @sum = sum
          @duplicates = []
     end

     def has_duplicates?
          not @duplicates.empty?
     end

     def add(path)
          @duplicates.push path
     end
end

if ARGV[0].nil? or not File.directory? ARGV[0]
     $stderr.puts "Use: #$0 <directory>"
     exit 1
end

hsh = {}
EMPTY_STRING_SUM = Digest::SHA256.hexdigest ''

Find.find(ARGV[0]) do|path|
     next unless File.file? path

     puts path

     sum = nil
     if path =~ /\.mp3$/i
          begin
               mp3 = Mp3Info.new(path)
               pos, length = mp3.audio_content
               mp3.close
          rescue
               next # discard this problematic file
          end

          File.open(path) do|file|
               file.pos = pos
               sum = Digest::SHA256.hexdigest(file.read(length))
          end
     else
          sum = Digest::SHA256.file(path).hexdigest
     end

     next if sum == EMPTY_STRING_SUM

     # nah!, let's use +unless+
     unless hsh[sum]
          hsh[sum] = FileRecord.new(path, sum)
     else
          file_record = hsh[sum]
          file_record.add(path)
     end
end

print "\n\nduplicates!\n\n"

hsh.each_value do|record|
     next unless record.has_duplicates?

     print "#{record.file}:\n->"
     print record.duplicates.join("\n-> "), "\n\n"
end
Se utiliza la gema Mp3Info para localizar el segmento de audio y calcular la función hash a dicha parte del archivo. Se hace esto, porque es posible que los metadatos de dos archivos varíen y de esta manera corrompan la singularidad del archivo, aun cuando dichos archivos contengan el mismo audio.

Si bien, el programa utiliza un buen algoritmo, este requiere una cantidad considerable de cálculos, los cuales son directamente proporcionales al tamaño de los archivos dentro del directorio raíz en cuestión. Pero algo si es seguro, encuentra los archivos duplicados.

Conclusión
Es posible implementar este programa en un Shell Script utilizando la herramienta sha256sum y el comando find. Aunque con el Shell será un poco más difícil contrarrestar el problema de los metadatos en los archivos de tipo: mp3, jpeg, png, pdf, etc.

Al parecer, los formatos de audio parecen ser los más propensos a este tipo de casos, donde los metadatos corrompen la función hash. Es muy importante tener esto pendiente para cuando se necesite un poco más de precisión.

Si necesitas una solución utilizando Bash, o necesitas ayuda, deja un comentario o contáctame por correo, el cual está en la parte de arriba de este blog.

lunes, 17 de diciembre de 2012

Es guay utilizar algoritmos de digest

Las funciones hash o algoritmos de digest tienen muchas aplicaciones y sobre todo, son guay. En esta entrada estaré hablando del uso de las funciones hash y los datos de validación.

Las Funciones Hash Y Las Contraseñas
Imagina que eres un intruso con pocos privilegios dentro de un servidor.  Encuentras un programa que posee privilegios para apagar el sistema, pero necesita clave, por eso examinas su código:
#!/usr/bin/env ruby

print 'Password '
exec 'shutdown -h now' if gets.chomp == 'adios'

puts 'Wrong password, try again.'
 Y ahí está la clave, ahora la cuestión es ¿Cómo reparar el script de modo que otras personas con privilegios de lectura no puedan ver la contraseña? Pues es simple en realidad, con una función hash codificas la contraseña y a la hora de comprobar, codificas la entrada y luego compruebas el hash resultante con el hash previamente calculado, así:
#!/usr/bin/env ruby
require 'digest/sha2'

# pass = newbieshell
PASSWORD = 'eeedeff1fde3065be0afcfc56fc775fb6de1f449bcb3f1845a8503e113bd8236'

print 'Password: '
sha2 = Digest::SHA256.hexdigest(gets.chomp)

exec 'shutdown -h now' if PASSWORD == sha2

puts 'Wrong password, try again.'
De esta forma el usuario no podrá ver la contraseña, para eso deberá recurrir a la fuerza bruta y si la clave es seguraen, le será muy difícil hallarla, incluso si cuenta con todo procesamiento del mundo .

Guardando Información En La Base De Datos
Cualquier ordenador conectado al Internet es vulnerable, por más seguridad y cosas que se hagan para protegerlo, seguirá siendo vulnerable; es la pura realidad. Por esta razón, también se deberá poner hincapié en proteger la información sensible; poner todo lo más difícil posible para cuando penetren el sistema (!).

Pues bien, lo primero que se debe hacer es, poner clave de acceso a todos los servicios y base de datos, incluso si solo se pueden acceder de manera local. Codificar con una función hash todos los campos de las base de datos que solo se utilizan para validar, p. ej. nombre de usuario, contraseña, correo.

De esta forma, si sufrimos un ataque de inyección SQL u otro de la misma naturaleza y tenemos todo los campos de validación codificados con una función hash, cuando el atacante obtenga la información, tendrá todo un reto en frente de él.

viernes, 7 de diciembre de 2012

Implementación de un Queue FIFO en Redis con Ruby y C

En esta entradas implementaremos una cola de tareas usando Redis, para aquellos casos donde RabbitMQ y ZeroMQ resultan muy complejos para lo que se quiere lograr. Estaré implementando la cola con Ruby y también con C para darle algo de originalidad a la entrada. Por cierto debo aclarar que el código de Ruby está basado en un código python escrito por Peter Hoffman en su Blog.
require 'redis'

class RedisQueue
     attr_reader :qname

     def initialize(name, options={})
          @redis = Redis.new(options)
          @qname = name
     end

     def size
          @redis.llen(@qname)
     end

     def empty?
          @redis.llen(@qname).zero?
     end

     def put(item, options={})
          if options[:priority] == :high
               @redis.lpush(@qname, item)
          else
               @redis.rpush(@qname, item)
          end
     end

     def get(timeout=0)
          item = @redis.blpop(@qname, timeout)
          item ? item[1] : nil
     end

     def get_nonblock
          item = @redis.lpop(@qname)
          return item[1] if item
          fail Errno::EWOULDBLOCK  
     end

     def done!
          @redis.quit
     end
end

La clase anterior es muy fácil de usar, a continuación dejo un ejemplo de uso:
queue = RedisQueue.new('queue:app')

p queue.qname
p queue.size
p queue.empty?

queue.put 'Tuesday'
queue.put 'Wednesday'
queue.put 'Monday', :priority => :high  # Ahora Monday es lo primero en salir.

p queue.size
p queue.empty?

p queue.get
p queue.get
p queue.get
p queue.get(2)     # Espera por 2 segundos.

begin
     p queue.get_nonblock
rescue Errno::EWOULDBLOCK
     puts 'La cola no tiene elementos, intenta hacer algo mientras se llena.'
end

Implementación en C

La versión de C requiere un poquito más de nuestra parte, pues hay que estar pendiente de la memoria, pero sin duda la implementación en C es la ideal para los ambientes de producción, donde la velocidad importa mucho. El siguiente código hace uso de la librería Hiredis, la cual en mí opinión, necesita un fichero Coding Style urgentemente.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "hiredis.h"

struct redis_queue {
     redisContext   *redis;
     char           *qname;
};

/*
 * Se conecta con Redis y prepara el entorno de la cola.
 *
 * host: Servidor de Redis.
 * port: Puerto para conectar con Redis.
 * qname: Nombre de la cola.
 *
 * devuelve NULL en caso de error o una estructura redis_queue.
 */
struct redis_queue
*init_redis_queue(const char *host, short port, char *qname)
{
     struct redis_queue   *queue;

     queue = malloc(sizeof(*queue));

     queue->redis = redisConnect(host, port);
     if(queue->redis->err)
          return NULL;

     queue->qname = malloc(strlen(qname));
     memcpy(&queue->qname[0], qname, strlen(qname));
  return queue;
}

/*
 * Agrega un nuevo elemento a la cola.
 *
 * queue: Estructura previamente devuelta por init_redis_queue().
 * data: Datos para anexarlo a la cola.
 * nbytes: Numero de bytes para copiar a la cola desde la variable data.
 *
 * devuelve -1 en caso de error o un numero positivo proveniente de Redis.
 */
long long
queue_put(struct redis_queue *queue, char *data, size_t nbytes)
{
     long long    n;
     redisReply  *reply;

     if(!queue || !queue->qname)
          return -1;

     reply = redisCommand(queue->redis, "lpush %s %b", queue->qname, data, nbytes);

     if(!reply)
          return -1;

     n = reply->integer;
     freeReplyObject(reply);
   return n;
}

/*
 * Obtiene un elemento de la cola o se bloquea por tiempo indefinido.
 *
 * queue: Estructura previamente devuelta por init_redis_queue().
 *
 * devuelve NULL en caso de error o la información solicitada. El programador
 * es responsable de liberar con free() los datos devueltos por queue_get().
 */
unsigned char*
queue_get(struct redis_queue *queue)
{
     redisReply      *reply;
     unsigned char   *data;

     if(!queue || !queue->qname)
          return NULL;

     reply = redisCommand(queue->redis, "brpop %s 0", queue->qname);
     if(!reply || reply->elements!=2)
          return NULL;

     data = malloc(reply->element[1]->len);
     memcpy(&data[0], reply->element[1]->str, reply->element[1]->len);
     freeReplyObject(reply);
   return data;
}

/*
 * Obtiene la cantidad de elementos que posee la cola.
 *
 * queue: Estructura previamente devuelta por init_redis_queue().
 *
 * devuelve -1 en caso de error o un número positivo proveniente de Redis.
 */
long long
queue_size(struct redis_queue *queue)
{
     long long   size;
     redisReply  *reply;

     if(!queue || !queue->qname)
          return -1;

     reply = redisCommand(queue->redis, "llen %s", queue->qname);
     if(!reply)
          return -1;

     size = reply->integer;
     freeReplyObject(reply);
   return size;
}

El código anterior  se puede utilizar de la siguiente manera:

int
main(void)
{
     unsigned char        *data;
     struct redis_queue   *queue;

     queue = init_redis_queue("localhost", 6379, "Queue");
     if(!queue) {
          fprintf(stderr, "Error, imposible conectarse con Redis.\n");
          exit(EXIT_FAILURE);
     }

     queue_put(queue, "Hola\0", 5);
     queue_put(queue, "tio\0", 4);
     queue_put(queue, "que tal\0", 8);

     printf("Size: %lld\n", queue_size(queue));

     data = queue_get(queue);
     puts(data);
     free(data);

     data = queue_get(queue);
     puts(data);
     free(data);

     data = queue_get(queue);
     puts(data);
     free(data);
  return 0;
}
Realmente no se cual es la manera correcta de compilar un programa que depende de Hiredis y la documentación tampoco dice cómo, la manera en que lo haremos será: Descargar el código fuente desde github; descomprimir el archivo; con make compilar Hiredis; posicionas tu fichero fuente dentro de la carpeta de Hiredis y lo compilas contra la librería libhiredis.a, más o menos así:

$ make
    cc -std=c99 -pedantic -c -O3 -fPIC  -Wall -W -Wstrict-prototypes -Wwrite-strings   net.c
    cc -std=c99 -pedantic -c -O3 -fPIC  -Wall -W -Wstrict-prototypes -Wwrite-strings   hiredis.c
    cc -std=c99 -pedantic -c -O3 -fPIC  -Wall -W -Wstrict-prototypes -Wwrite-strings   sds.c
    cc -std=c99 -pedantic -c -O3 -fPIC  -Wall -W -Wstrict-prototypes -Wwrite-strings   async.c
    ...
$ gcc -c -o queue.o queue.c
$ gcc -o queue queue.o libhiredis.a

 Apéndice
La temática para implementar una cola FIFO es muy sencilla. Imagina que tienes una pila de platos donde uno esta encima del otro, ahora imagina que para obtener un plato de esa enorme pila solo puedes cogerlo desde abajo, allá en la base de la pila y que para agregar platos al montón, solo puedes hacerlo desde el tope. Si imaginas esto, estarás imaginando el funcionamiento de una cola FIFO. De manera semejante, para implementar una cola LIFO debes imaginar, que solo sacas y pones platos desde un mismo lugar, sea la base o la cima de la pila. A continuación un ejemplo de cómo hacerlo desde el CLI de Redis:
redis 127.0.0.1:6379> lpush COLA "Primer Elemento"
(integer) 3
redis 127.0.0.1:6379> lpush COLA "Segundo Elemento"
(integer) 4
redis 127.0.0.1:6379> brpop COLA 0
1) "COLA"
2) "Primer Elemento"
redis 127.0.0.1:6379> brpop COLA 0
1) "COLA"
2) "Segundo Elemento"
redis 127.0.0.1:6379> brpop COLA 0
^C
Para más información acerca de las ordenes que admite Redis, visita: http://redis.io/commands
Referencias
  1. http://peter-hoffmann.com/2012/python-simple-queue-redis-queue.html 

miércoles, 5 de diciembre de 2012

Cómo implementar un URL Shortener funcional con Sinatra y Redis

En esta entrada estaremos implementando un servicio web muy común, URL Shortening. Para lograr nuestros objetivos estaremos utilizando Ruby, Sinatra y Redis.

¿Por qué Sinatra?
 Es cierto que hay entornos más completos y funcionales que Sinatra, pero la pega está en que los entornos populares como Rails requieren una pila de dependencias enorme y están orientados para aplicaciones web un poco más complejas y extensas. Sinatra es la opción ideal debido a su simplicidad y su cantidad mínima de dependencias. más información

¿Por qué Redis?
Si bien se podría usar un Hash interno, que de manera más eficiente lleve el registro de todo. El uso de Redis agrega unas cuantas ventajas muy atractivas, como la persistencia de datos, tiempo de vida para los datos y la capacidad de acceder externamente y realizar métricas sobre los datos. más información

El Algoritmo
De toda la aplicación, esta es la parte mas fácil de implementar, pero sin embargo, es la que requiere un poco más de cuidado de nuestra parte. Una mala elección en el algoritmo interno podría resultar en procesamiento innecesario, perdidas de tiempo y por que no, problemas de mantenimiento. A continuación listo algunos acercamientos junto con sus pros y contras.

  1. Strings Aleatorios
    - PROS
             - Fácil de implementar.
    - CONS
             - Se debe comprobar mucho.
             - Se podría necesitar generar varias cadenas aleatorias para obtener una disponible.
  2. Strings Secuenciales
    - PROS
             - Fácil de implementar.
             - No requiere comprobaciones.
    - CONS
             - Cualquier usuario podría predecir direcciones válidas.
  3. Permutación De Carácteres
    - PROS
             - Fácil de implementar.
             - No requiere comprobaciones.
             - Las direcciones no se pueden predecir.
    - CONS
             -
    Para implementar el tercer acercamiento, solo basta con usar el método Array#permutation para generar las secuencias únicas, y para mitigar el problema de la predictibilidad, se baraja el array de carácteres con el método Array#shuffle y listo, solo queda iterar por todas las permutaciones.
    class Url
         def initialize(n=1)
              @n = n
              @seq = mkseq(@n)
         end
    
         def next
              begin
                   @seq.next.join
              rescue StopIteration   
                   @n += 1
                   fail 'No more resources available!' if @n > CHARS.length
    
                   @seq = mkseq(@n)
                   self.next()
              end
         end
    
         private
    
         def mkseq(n, random=true)
              if random
                   CHARS.shuffle.permutation(n)
              else
                   CHARS.permutation(n)
              end
         end
    
         CHARS = [*(0..9), *('A'..'Z'), *('a'..'z')]
    end 
    Es muy importante señalar que es una mala idea convertir el resultado del método Array#permutation en un array, pues podría resultar en una perdida de tiempo del orden de minutos o días. Bueno, implementado ya el corazón de la aplicación, solo nos queda manejar las peticiones con Sinatra y unir todo.

    La mecánica es la siguiente: Cuando un usuario hace una petición a nuestro servidor a través de una URL corta, se toma la segunda parte de la dirección — el recurso o path y se hace una petición a Redis, si dicho recurso existe, el usuario es redirigido al enlace devuelto por Redis utilizando el método redirect, si no existe, entonces en vez de redirigir al usuario, se presenta un aviso con información al respecto.
    #!/usr/bin/env ruby
    #encoding: UTF-8
    require './url.rb'
    require 'redis'
    
    rd_child, wr_parent = IO.pipe()
    rd_parent, wr_child = IO.pipe()
    
    if fork()
         rd_child.close
         wr_child.close
    
         resources = Url.new
         loop do
              IO.select([rd_parent])
              rd_parent.read(1)
              wr_parent.write(resources.next)
         end
    else
         rd_parent.close
         wr_parent.close
    
         require 'sinatra'
    
         redis = Redis.new
    
         set :static, true
         set :public_folder, File.join(File.dirname(__FILE__), 'static')
    
         get '/' do
              erb :index #template
         end
    
         get '/:resource' do
              @url = redis.get(params[:resource])
    
              if @url
                   redirect(@url)
              else
                   halt 400, '<html><head><title>Error</title></head><body><h1>Not Found</h1></body></html>'
              end
         end
    
         post '/create' do
              begin
                   URI.parse params[:url]
              rescue
                   halt 400, '<html><head><title>Error</title></head><body><h1>Bad Url</h1></body></html>'
              end
    
              wr_child.write('g')
              IO.select([rd_child])
              @resource = rd_child.sysread(512)
              redis.set(@resource, params[:url])
    
              erb :index   # tamplate
         end
    end
    Hay un pequeño inconveniente del que no se habla mucho en la documentación oficial de Ruby. Los Fibers no se pueden utilizar a través de múltiples hilos, por ejemplo si intentas ejecutar el siguiente código, producirá un error:
    fiber = nil
    Thread.new do
         fiber = Fiber.new do { Fiber.yield 1 }
    end
    fiber.resume # FiberError: fiber called across threads
    
    Debido a que el método Array#permutation utiliza Fibers y algunos servidores web como Thin usan Threads, en efecto,  para evitar errores en tiempo de ejecución está la decisión de crear dos procesos en el código de arriba, uno para ejecutar Sintra y otro exclusivamente para generar combinaciones. Bien, ahora solo queda la parte web; el front end.

    gina Web
    Bueno, como realmente el diseño es para los diseñadores, me haré de una página que genere una interfaz más o menos aceptable para luego descargar el código y modificarlo a gusto.

    Para lograr una interfaz parecida a la de esta entrada, visita http://www.phpform.org/ y selecciona a gusto los elementos de la página principal, descarga el código y personifícalo, recuerda, la página principal debe quedar lo más simple posible.

    Una cosa más, para mostrar la nueva url al usuario, se utiliza el valor almacenado por la aplicación en la variable de instancia @resource. Cada vez que se acorta un enlace, dicha variable es accesible desde el view, en mi caso el fichero index.erb — el cual elaboré a partir del código generado por la página phpform —. El siguiente es un fragmento del código necesario para mostrar la URL recién creada en el pie (footer) de la página desde el view index.erb.

    <div id="footer">
         <% if @resource %>
              <% url = "http://localhost:4567/#@resource" %>
              <p><a href="<%=url%>"><%=url%></a></p>
         <% else %>
              <p><a href="">Submit new url</a> </p>
         <% end %>
    </div>

    Descargar Aplicación De La Entrada
    Actualización 9/12/12
     Uso del método Array#permutation en lugar del método Array#combination.