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.

    miércoles, 18 de julio de 2012

    Distancia de edición

    adminitrador: Saludos User123
    user123: Saludos
    adminitrador: disculpe por las molestias, pero lamento informaros que nuestra base de datos ha sido comprometida y por lo que parece, por una persona de nuestro equipo.
    user123: Lo lamento, pero y  ¿por qué me estás diciendo eso? no tengo nada que ver con lo que ha sucedido.
    adminitrador: estamos llevando una investigación a fondo, y como se podrá . . .

    ¡Espera un momento! ¿Quién diablos es ese? ¡administrador sin s!

    Bueno, sin duda ese era alguien un poco más astuto de la cuenta, y estoy seguro de que hubo personas que no pudieron percibir ese pequeño detalle mientras leían la parte de arriba.

    El robo de identidad es algo muy común en la red y muchas veces es muy fácil de llevar a cabo, veamos como podemos proteger a los usuarios y nuestra web, en lo posible, de este tipo de cosas utilizando la distancia de edición de Levenshtein, o simplemente distancia de Levenshtein:

    Antes de comenzar, necesitarás la siguiente gema:
    gem install levenshtein
    Continuando, según el ejemplo del timador de arriba, para nuestros fines, consideraremos insegura cualquier palabra que necesita dos o menos cambios para convertirse en otra.

    Primero probemos un poco con irb:
    irb(main):001:0> require 'levenshtein'
    => true
    irb(main):002:0> Levenshtein.distance("administrador", "adminitrador")
    => 1
    irb(main):003:0> Levenshtein.distance("webmaster", "wepmaster")
    => 1
    irb(main):004:0> Levenshtein.distance("administrador", "administradores")
    => 2
    irb(main):005:0>
    
    Viendo los resultados, podríamos concluir que si tenemos un usuario de nombre webmaster, sería inseguro aceptar otro usuario de nombre wepmaster, de la misma manera para: administrador y adminitrador; administrador y administradores.

    Preparemos ahora otro ejemplo, pero esta vez uno que lea una lista de usuarios y de ellas nos diga si es seguro aceptar el usuario o no.
    require 'levenshtein'
    
    RULE= 2
    
    def safe_name?(pool, username, rule=RULE)
         not pool.any? do|name|
              Levenshtein.distance(name, username) <= rule
         end
    end
    
    if ARGV.empty?
         $stderr.puts "Uso: ruby #{$0} <usuario>"
         exit
    end
    
    # pool = IO.read('lista_usuarios.txt').scan(/\w+/)
    
    pool = %w{ administrador abogado policia admin webmaster
               paypal google yahoo amazon dios jesus gandhi}
    
    if safe_name?(pool, ARGV[0].downcase)
         puts "El nombre de usuario `#{ARGV[0]}' es seguro."
    else
         puts "`#{ARGV[0]}' no es un nombre de usuario seguro."
    end
    

    ~ $ ruby edit_distance.rb googel
    `googel' no es un nombre de usuario seguro.
    
    $ ruby edit_distance.rb jesu
    `jesu' no es un nombre de usuario seguro.
    
    $ ruby edit_distance.rb gandi 
    `gandi' no es un nombre de usuario seguro.
                                            
    ~ $ ruby edit_distance.rb abogados
    `abogados' no es un nombre de usuario seguro.
    

    Conclusión

    Últimamente los entornos de trabajo modernos (frameworks) integran mecanismo como este, de modo que la responsabilidad de comprobar este tipo de cosas recae en el sistema y no en el programador, pero nunca está de más estar alerta y consciente de los lugares de entrada y la forma de tapar esos huecos.

    Ya con esto haremos que nuestros usuarios estén un metro más lejos de las garras de personas malintencionadas y brindaremos una capa más de seguridad a nuestra aplicación. Para aquellos que utilicen PHP en vez de Ruby, buenas noticias, PHP incluye en su librería estándard la función levenshtein() .

    Enlaces Útiles

    domingo, 15 de julio de 2012

    Esteganografía: El canal alfa

    ¿Has sentido la necesidad de pasar información a través de un canal público? ¿Has sentido la necesidad de no levantar sospechas? o solo quieres ocultar información, sea cual sea tú fin, en esta entrada encontrarás un programa que te será muy útil así como la descripción de una técnica relativamente práctica que utiliza imágenes para ocultar información.


    Ocultando información

    Debido a  que a muchas personas no les interesa la teoría detrás de esta técnica, he comenzado por la parte práctica, la cual es de interés común.

    Necesitarás:
    •  Ruby
    • El código del programa, descargar AQUÍ
    • Instalar la gema ChunkyPNG
      gem install chunky_png
    • La siguiente imagen para seguir los ejemplos al pie:


    Primero veamos las opciones que nos proporciona el programa con la opción --help y de camino veamos también que espacio de almacenamiento tenemos disponible en la imagen.
    Bueno, a simple vista se puede ver que el programa nos ofrece muchas opciones útiles para manipular la imagen, y también nos muestra que tenemos apróx. 145 KB de espacio útil dentro de la imagen.

    Ahora veamos como se oculta y revela información dentro de la imagen

    También podrías — si el texto es muy grande — especificar un fichero completo y ocultarlo dentro con la opción --file, o podrías también si consideras que la información dentro de la imagen es muy grande, volcarla en un fichero, con la opción --output-file. Veamos

    ¿Cómo funciona?


    Antes que nada aclaremos unas cosas, por ejemplo el título de la entrada:

     ¿Qué es la esteganografía?
    es la parte de la criptología en la que se estudian y aplican técnicas que permiten el ocultamiento de mensajes u objetos, dentro de otros, llamados portadores, de modo que no se perciba su existencia. Wikipedia
    Es preciso aclarar, que la esteganografía y la criptografía van de la mano pero el fin de ambas es diferentes. La esteganografía falla cuando se descubre la presencia de información oculta dentro del portador, aún si esta está cifrada. La criptografía falla cuando el sistema de cifrado falla.

    Para mas información visita wikipedia.

    El canal alfa

    Ya a estas altura de juego ya muchos de ustedes estarán familiarizado con la representación hexadecimales de los colores en la web, por ejemplo dos colores muy comunes y que posiblemente sabes son el blanco #FFFFFF y el negro #000000. Para el que no lo sepa, esas representaciones son números, números que indican la cantidad de ciertos colores preestablecidos, los cuales son: Rojo, Verde y Azul. De ahí su nombre, colores RGB.

    Continuando, para representar dichos colores se necesitan 3 bytes, en cierta forma un byte por cada dos dígitos hexadecimales de ahí la decisión por adoptar la representación base dieciséis, es mucho fácil de recordar. Ahora, imagina que preparas una imagen y has seleccionado un color, pero pasa algo, sucede que es un color muy intenso y quieres darle un poco de opacidad — que se vea algo transparente — ¿Cómo lo logras? ¡pues con el canal alfa!

    El canal alfa es un cuarto byte A dentro de la representación numérica del color RGB de un píxel y representa la opacidad que este tiene. Cuando se utiliza el canal alfa, el píxel se denomina por el cuarteto RGBA — Un píxel es, por así decirlo, un punto de color dentro de la imagen  — .

    — ¿Qué pasaría si decidiera darle total opacidad a un píxel?
    — Pues simple, conseguirías un píxel trasparente.
    — Un píxel transparente es un píxel invisible ¿no?
    — exacto.

    De  forma resumida, para ocultar información dentro de una imagen con canal alfa, solo tendríamos que insertar la información en el espacio RGB de un píxel y ocultarla dándole total opacidad con el canal alfa ... solo eso ...

    Debilidades

    Esta técnica presenta una debilidad y es que cualquier persona podría poner visibles todos los pixeles transparentes de una imagen y ver una evidente anomalía en la imagen. Veamos como se logra esto con el programa de la entrada y la opción --show-alpha:

    y el resultado es el siguiente:


    Conclusión


    Aquí no está, quizás esté en otra parte :P

     Referencias


    Este artículo está  basado en otro escrito por Daniel Lerch en su extraordinario blog.

    Enlaces de interés

    martes, 22 de mayo de 2012

    Técnicas de búsqueda: Introducción


    Lunes 8:45pm, luego de un largo día de trabajo abres el navegador y buscas la información habitual: como preparo la cena ... ¡Clic! 0.20 s después, con 2.560 millones de resultados en frente de ti, comienza la búsqueda por una comida apropiada ¡Clic! ¡Clic! ¡Clic! y al cabo de unos segundos ya estás listo para ir a preparar la cena.

    ¡Espera un momento!

    ¿Tardar menos de un minuto para encontrar la información que se desea dentro de 2 560 000 resultados?

    Bueno, el propósito de esta entrada no es explicar la cantidad de ordenadores necesarios para lograr tal rapidez, algoritmos de caché, base de datos ni tampoco hablar del pago de la factura de luz de un buscador como ese. El objetivo de este artículo es mostrar una de las técnicas más básicas pero sin embargo más importante cuando se quiere alcanzar la mayor relevancia posible.

    No es necesario conocimientos previos de programación para aprovechar esta entrada, pero ayudaría mucho. Si piensas seguir el artículo al pie, al menos deberás tener instalado una versión de ruby >= 1.9.2 e instalar una gema que programé específicamente para este artículo: 

    gem install estem

    para más información visita: https://github.com/MaG21/estem

    Stemming

    Es una técnica que consiste en reducir a la raíz una palabra, dicha palabra puede ser una palabra derivada o estar en su forma conjugada p . ej. supón que tienes dos fragmentos de textos, la palabra clave pescadería y deseas saber cuál podría ser el más relevante de los dos.
    primer fragmento
    La pescadería es el lugar donde venden pescados atrapados por los pescadores. El pescador es la persona que atrapa el pescado.
    segundo fragmento
    Por este medio le informamos que cerraremos la pescadería Mar. Por favor perdone los inconvenientes que esto podría causar, nuestra prioridad es abrir la pescadería lo más pronto posible.
    Una persona ingenua haría una búsqueda por palabras clave contra esos dos fragmentos, a continuación un modelo en ruby de como se vería una búsqueda por palabras claves común y corriente:
    ~ $ irb
    irb(main):001:0> frag1 = "La pescadería es..."
    irb(main):002:0> frag2 = "Por este medio l..."
    irb(main):003:0> st = "\033[47m\033[1;31m"
    irb(main):004:0> en = "\033[m"
    irb(main):005:0> re = /pescadería/
    irb(main):006:0? idx = 0
    irb(main):007:0> [frag1,frag2].each do|txt|
    irb(main):008:1*    ret = txt.gsub(re,"#{st}\\&#{en}")
    irb(main):009:1>    puts "Fragmento #{idx+=1}\n#{ret}\n"
    irb(main):010:1> end
    Fragmento 1
    La pescadería es el lugar donde venden pescados atrapados por
    los pescadores. El pescador es la persona que atrapa el pescado.
    
    Fragmento 2
    Por este medio le informamos que cerraremos la pescadería Mar. Por
    favor perdone los inconvenientes que esto podría causar, nuestra
    prioridad es abrir la pescadería lo más pronto posible.
    Según los resultados, el segundo fragmento es el que más coincidencias posee y  por ende, para este criterio de búsqueda, el más relevante.  Sin duda el segundo fragmento es el menos relevante, pues aunque una persona explícitamente desee la información del segundo fragmento, con esa sola palabra clave sería ilógico entregar un resultado tan alejado del significado de la misma. Si la persona desea obtener lo que busca, simplemente deberá entregar más de una palabra clave  p. ej. el nombre de la pescadería.

    Veamos como se vería el resultado de la búsqueda anterior, aplicando otro criterio de búsqueda a partir de raíces gramaticales, dichas raíces si no lo son, son muy parecidas a los lexemas y son el resultado de aplicar la técnica del Stemming a una palabra. Continuando con la sesión de irb anterior, tenemos:
    irb(main):011:0> require 'estem'
    irb(main):012:0> re = %r{\b#{'pescadería'.es_stem}[a-zA-ZáéíóúüÁÉÍÓÚÜÑñ]++}
    irb(main):013:0? idx = 0
    irb(main):014:0> [frag1,frag2].each do|txt|
    irb(main):015:1*    ret = txt.gsub(re,"#{st}\\&#{en}")
    irb(main):016:1>    puts "Fragmento #{idx+=1}\n#{ret}\n"
    irb(main):017:1> end
    Fragmento 1
    La pescadería es el lugar donde venden pescados atrapados por
    los pescadores. El pescador es la persona que atrapa el pescado.
    
    Fragmento 2
    Por este medio le informamos que cerraremos la pescadería Mar. Por
    favor perdone los inconvenientes que esto podría causar, nuestra
    prioridad es abrir la pescadería lo más pronto posible.  
    A simple vista se puede ver que el primer fragmento es el más relevante, y sin duda lo es. Ahora te podrías estar preguntando ¿Qué pasó? Bueno no mucho en realidad, simplemente se cargo la gema, se aplicó Stemming a la palabra pescadería y se utilizó dicho resultado junto con una expresión regular para agarrar, por así decirlo, las palabras que concuerden.

    Palabras vacías

    Las palabras vacías o en inglés stop words, son palabras que la mayor parte de las veces no aportan un nivel de relevancia mayor, son palabras que por su propio significado y alta frecuencia estropean las búsquedas p. ej. tu, yo, el, ellos, para, contra, con, de. Para el español opino que es una lista muy numerosa. Si deseas una lista exhaustiva de palabras vacías, por favor visita la siguiente dirección, donde Martin Porter nos ofrece una gran cantidad: http://snowball.tartarus.org/algorithms/spanish/stop.txt

    Veamos un ejemplo funcional:
    primer fragmento
    Por favor, note que algunos baños son únicamente para mujeres.
    Le pedimos que sea cuidadoso. Gracias por cooperar.

    segundo fragmento
    Un animal herbívoro es aquel que se alimenta de las plantas,
    árboles, arbustos y hierbas. 

    Aplicando todo lo que se ha visto hasta ahora, nos queda un programa de prueba como este:
    #!/usr/bin/env ruby
    # encoding: UTF-8
    # URL: newbieshell.blogspot.com
    
    require 'estem'
    require 'getoptlong'
    
    
    EQU = {'a' => '[aAáÁ]', 'e' => '[eEéÉ]','i' => '[iIíÍ]','o' => '[oOóÓ]','u' => '[uUúÚ]',
           'á' => '[áÁaA]', 'é' => '[éÉeE]','í' => '[íÍiI]','ó' => '[óÓoO]','ú' => '[úÚuU]',
           'ü' => '[üÜuU]', 'Á' => '[áÁaA]','É' => '[éÉeE]','Í' => '[íÍiI]','Ó' => '[óÓoO]',
           'Ú' => '[úÚuU]', 'Ü' => '[üÜuU]','Ñ' => '[ñÑ]','ñ' => '[ñÑ]'}
    
    STOPWORDS = ['por', 'de', 'los', 'que', 'mucho',
                 'algunos', 'son', 'el', 'ellos', 'qué']
    
    $stopwords = false
    
    def get_words(string)
         # I am in love with ruby, look:
         ret = if $stopwords
              string.scan(/[a-zA-ZáéíóúüÁÉÍÓÚÜÑñ]+/) -  STOPWORDS
         else
              string.scan(/[a-zA-ZáéíóúüÁÉÍÓÚÜÑñ]+/)
         end
    
         ret.collect { |w| w.es_stem }
    end
    
    def make_es_regexp(string)
         words = get_words(string)
    
         re_words = words.collect do|w|
              w.each_char.collect do|c|
                   'aeiouAEIOUáéíóúüÁÉÍÓÚÜÑñ'.include?(c) ? EQU[c] : c
              end.join()
         end
    
         Regexp.new("(?<![a-záéíóúüÁÉÍÓÚÜÑñ])(#{re_words.join('|')})[a-záéíóúüÁÉÍÓÚÜÑñ]*", Regexp::IGNORECASE)
    end
    
    begin
         opt = GetoptLong.new(['--stop-words', GetoptLong::NO_ARGUMENT])
         opt.quiet = true
     
         $stopwords = true if opt.get
    rescue
         $stderr.puts "Opción inválida"
         exit
    end
    
    # Estas dos cadenas de caracteres se utilizan para darle color
    # a los resultados encontrados. NOTA necesita una terminal ANSI
    st = "\033[47m\033[1;31m"
    en = "\033[m"
    
    frag1 = <<EOF
    Por favor, note que algunos baños son únicamente para mujeres. 
    Le pedimos que sea cuidadoso. Gracias por cooperar.
    EOF
    
    frag2 = <<EOF
    Un animal herbívoro es aquel que se alimenta de las plantas,
    árboles, arbustos o hierbas.
    EOF
    
    # búsqueda: "por qué algunos animales son herbívoros?"
    re = make_es_regexp("por qué algunos animales son herbívoros?")
    
    [frag1,frag2].each do|text|
         puts text.gsub(re,"#{st}\\&#{en}"), "\n\n"
    end
    Ahora ejecutemos el ejemplo, las palabras de búsqueda para este ejemplo son: por qué algunos animales son herbívoros?
    ~$ ruby search.rb
    Por favor, note que algunos baños son únicamente para mujeres. 
    Le pedimos que sea cuidadoso. Gracias por cooperar.
    
    Un animal herbívoro es aquel que se alimenta de las plantas,
    árboles, arbustos o hierbas.
    El texto más irrelevante que alguien se pueda imaginar para esta búsqueda es el primer fragmento, pero gracias a las palabras vacías toma relevancia falsa.  Ejecutemos el programa y esta vez, quitando las palabras vacías:
    ~$ ruby search.rb --stop-words
    Por favor, note que algunos baños son únicamente para mujeres. 
    Le pedimos que sea cuidadoso. Gracias por cooperar.
    
    Un animal herbívoro es aquel que se alimenta de las plantas,
    árboles, arbustos o hierbas.
    Como se ve, remover las palabras vacías de los términos de búsquedas, tiene sus beneficios, pero también tiene sus desventajas, de las cuales no hemos hablado, la más notable es que no se podrán realizar búsquedas por frase, algo un poco más complejo si se quiere hacer bien.

    Conclusión

    Si tienes intenciones de adentrarte en el mundo de la extracción de información, existen muchos acercamientos que podrían ser de interés y no se mencionaron, p. ej. un acercamiento estadístico, utilizando el teorema de Bayes; un acercamiento tomando en cuenta el momento de la consulta, si es hora de comida o una hora de trabajo; búsqueda geolocalizadas; búsquedas sentimentales o por supuesto, una combinación de todos esos acercamientos.

    Sin duda faltan muchos pequeños detalles por tomar en cuenta, pero con lo mencionado anteriormente, es suficiente para entender un poco acerca de los buscadores, y si se cuenta con los conocimientos necesarios de programación, cualquier persona sería capaz de programar un algoritmo de búsqueda superior a una innumerable cantidad de paginas web allá afuera.

    La brevedad es difícil de alcanzar y sin cuidado complica lo que se quiere simplificar en primer lugar.  Ten cuidado con la codificación de los textos que manejas; Se organizado; clasifica la información e Intenta ejecutar todo lo que se presenta aquí.

    Referencias

    1.  Spanish Stemming Algorithm, Martin Porter

    Enlaces Útiles

    1.  Lista de palabras vacias
    2. https://github.com/MaG21/estem
    3. IMG, Enlace directo a la página del autor de la imagen de la portada.