Ejemplo de fragmentación de memoria con Arduino

En dispositivos con poca memoria RAM, como es el caso de Arduino, cuando se asigna memoria de forma dinámica puede surgir el problema de la fragmentación. Se produce cuando la memoria libre esta fragmentada en trozos tan pequeños que no se puede reservar suficiente memoria contigua libre aunque la suma total de memoria libre es mayor que la que se trata de reservar.

Veamos un ejemplo de como se produce esta fragmentación, para ello empezaremos reservando un bloque de 1000 bytes de memoria (memory1) para limitar la memoria disponible. Luego reservamos un bloque de memoria de 300 bytes (memory2) otro de un byte (memory3) y otro de 300 (memory4) de nuevo. La función de ese bloque de un único byte es evitar que al liberar los otros dos bloques estos puedan unirse en un mismo bloque. Liberamos los dos bloques de 300 bytes por lo que ahora debería haber libre un mínimo de 600 bytes libres, sin embargo si tratamos de reservar 500 bytes (memory5) y no puedo (el puntero tiene valor 0). Hay memoria libre suficiente pero esta divida en bloques más pequeños del que necesito. Con solo un byte estratégicamente colocado hemos causado un problema de fragmentación. Los bloques más pequeños (memory6) pueden reservar memoria sin problemas.

byte* memory1;
byte* memory2;
byte* memory3;
byte* memory4;
byte* memory5;
byte* memory6;

void setup() {  
  Serial.begin(9600);
  while (!Serial) {
    ; // esperamos a que el puerto este inicializado 
  }

  memory1 = (byte*) calloc (1000, sizeof(byte)); //reservamos 1000
  memory2 = (byte*) calloc (300, sizeof(byte)); //reservamos 300
  memory3 = (byte*) calloc (1, sizeof(byte)); //reservamos 1
  memory4 = (byte*) calloc (300, sizeof(byte)); //reservamos 300
  free(memory2); // liberamos 300
  free(memory4); //liberamos 300 
  memory5 = (byte*) calloc (500, sizeof(byte)); //reservamos 500
  memory6 = (byte*) calloc (300, sizeof(byte)); //reservarmos 300

  Serial.println((long)memory1);
  Serial.println((long)memory2);
  Serial.println((long)memory3);
  Serial.println((long)memory4);
  Serial.println((long)memory5);
  Serial.println((long)memory6);
}
 
void loop() {

}

Veamos un ejemplo de salida:

466
1468
1770
1774
0
1468

Se puede ver que memory5 no puede reservar memoria mientras que a memory6 se le asigna el primer bloque libre que coincide con el memory2 que acaba de ser liberado.

Este ejemplo esta pensado para una placa Arduino UNO en caso de usarlo en otra placa habrá que ajustar el tamaño del primer bloque.

Arduino, leer puerto serie usando serialEvent

SerialEvent es una función que se llama automáticamente cuando hay datos esperando a ser leídos en el puerto serie. Se invoca tras cada iteración de la función loop, por lo que cualquier delay o bloqueo en la función loop retrasa su invocación. Es una forma sencilla de integrar la gestión de los datos por puerto serie nuestro código.

void setup() {
  Serial.begin(9600);
}

void loop() {

}

void serialEvent() {
  //mientras tenga datos que leer
  while (Serial.available()) {
	//leer datos
  }	
}

Para las placas que tienen más de un puerto serie existe una función serialEvent distinta para cada uno:

  • Serial – serialEvent
  • Serial1- serialEvent1
  • Serial2 – serialEvent2
  • Serial3 – serialEvent3

Esta función no esta disponible para todos los puerto serie de todas las placas, por ejemplo no esta disponible para las placas basadas en microcontroladores SAMD, para Arduino Due o las placas Leonardo, Micro, o Yún que no funciona serialEvent (serialEvent1 si que funciona).

Trabajar con datos tipados de un dispositivo desde una página web

Cada vez hay más integración entre la web y la domática, «internet of things» o «web of things» son ejemplos de ello. Uno de los problemas que te puedes encontrar es que a nivel de programación son dos mundos muy dispares. En los dispositivos electrónicos reina C/C++ y similares, mientras que en la web el más usado es JavaScript. Aunque ambos lenguajes no trabajan directamente uno con otro lo hacen a través de API a veces surge el problema tratar los datos y es que mientras que C tiene un tipado de datos muy específico el de JS es menos concreto. ¿Qué podemos hacer cuando necesitamos un tipado de datos muy concreto que nos permita incluso trabajar a nivel de bits?. Simplemente usar datos tipados en JS.

Datos tipados en JavaScript

Pese a su fama JS tiene más tipos de datos que los conocidos String, boolean, number.

En este caso vamos a centrarnos en los siguientes tipos que podemos usar para imitar los tipos habituales de C/C++. Podemos elegir el tamaño en bits, si es con signo o sin signo incluso la forma en que se comporta cuando hay un desbordamiento. La única pega, solo funciona con arrays lo que nos supone una incomodidad a la hora de trabajar con un único elemento (tendremos que usar un array de tamaño 1).

TipoRangoTamaño (bytes)DescripciónTipo en C/C++
Int8Array -128…12718-bit con signoint8_t
Uint8Array 0…25518-bit sin signouint8_t
Uint8ClampedArray 0…25518-bit sin signo (clamped)uint8_t
Int16Array -32768…32767216-bit entero con signoint16_t
Uint16Array 0…65535216-bit entero sin signouint16_t
Int32Array -2147483648… 2147483647432-bit entero con signoint32_t
Uint32Array 0…4294967295432-bit entero sin signouint32_t
Float32Array 1.2E-38…3.4E38432-bit punto flotantefloat
Float64Array 5E-324…1.8E308864-bit punto flotantedouble
BigInt64Array -2^63…2^63 – 1864-bit entero con signoint64_t
BigUint64Array 0…2^64 – 1864-bit entero sin signouint64_t

Lo valores en punto flotante siguen el estándar IEEE.

Veamos algunos ejemplos de como usarlos y alguna propiedades interesantes (BYTES_PER_ELEMENT, byte que ocupa cada elemento; byteLength, longitud total del array en bytes):

var int8 = new Int8Array(3);
int8[0] = 42;
console.log(int8[0]); //42
console.log(int8.length); //3
console.log(int8.BYTES_PER_ELEMENT); //1
console.log(int8.byteLength); //3 = length * BYTES_PER_ELEMENT

var int16 = new Int16Array(3);
int16[0] = 42;
console.log(int16[0]); //42
console.log(int16.length); //3
console.log(int16.BYTES_PER_ELEMENT); //2
console.log(int16.byteLength); //6 = length * BYTES_PER_ELEMENT

Un dato clamped (acotado) es un dato que cuando se produce un desbordamiento de su valor por arriba o por abajo el dato toma su mayor y menor valor. O más simplemente explicado si intentas asignarle un valor mayor de 255 o menor que 0 se le asignará el valor 255 y 0 respectivamente. Lo datos que no son de tipo clamped simplemente ignoran los bits del desbordamiento. Podemos verlo mejor con un ejemplo:

var uInt8Clamped = new Uint8ClampedArray(1);
var uInt8 = new Uint8Array(1);

uInt8Clamped[0] = 256;
uInt8[0] = 256;
console.log(uInt8Clamped[0]); //255 
console.log(uInt8[0]); //0

uInt8Clamped[0] = 265;
uInt8[0] = 265;
console.log(uInt8Clamped[0]); //255 
console.log(uInt8[0]); //9

ArrayBuffer y Dataview

Aún hay un truco más que permite JS para trabajar con estos datos. Crear un ArrayBuffer que permite reservar un «espacio de memoria» indicando el tamaño del mismo en bytes. Desde un ArrayBuffer no puedes ni leer ni escribir esta memoria, para ello tienes que asignarlo a un array tipado como los uqe hemos visto antes. Puedes asignar el mismo ArrayBuffer a varios arrays tipados que lo compartirán:

var buffer = new ArrayBuffer(2);
var view8 = new Uint8Array(buffer);
var view16 = new Uint16Array(buffer);
view16[0] = 258;
console.log(view16[0]);// 258 -> 00000001 00000010
console.log(view8[0]); // 2 -> 00000010
console.log(view8[1]); // 1 -> 00000001

En el ejemplo se ve como un ArrayBuffer de 2 bytes se puede leer desde un array de 1 elemento de 16 bits o un array de un array de 2 elementos de 8 bits y como los valores se solapan.

Hay otra forma de hacerlo, con un DataView. Las ventajas de los DataView son dos:

  • Permiten escribir y leer en el ArrayBuffer con cualquier tipo de datos usando el métodoset y get correspondiente getUint8(), setUint8(), getInt8(), setInt8(), getUint16(), setUint16(), …
  • El orden en que se recuperan los bytes es más intuitivo

El ejemplo anterior con DataView

const buffer = new ArrayBuffer(2);
var view = new DataView(buffer, 0);
view.setUint16(0, 258); // (max unsigned 16-bit integer)
console.log(view.getUint16(0));// 258 -> 00000001 00000010
console.log(view.getUint8(0)); // 1 -> 00000001
console.log(view.getUint8(1)); // 2 -> 00000010

Gamificación en el diseño del software

La gamificación consiste en aplicar mecánicas del juego a otros entornos para lograr un refuerzo de los comportamientos deseados del usuario. Es útil conocer sus mecanismos para poder aplicarlos al diseño de software al que puede aportar varios beneficios:

  • Aumenta el engagement.
  • Reduce el estrés del usuario.
  • Motiva el uso del software.
  • Reduce el esfuerzo de aprender a usarlo.
  • Motiva que los usuarios compartan su experiencia y avances entre sus conocidos ayudando a la difusión.

Tipos de jugadores:

Segun Richard Bartle:

  • Achievers (10%): tienen como objetivo resolver retos con éxito y conseguir una recompensa por ello.
  • Explorers (10%): quieren descubrir y aprender cualquier cosa nueva o desconocida del sistema.
  • Socializers (80%): sienten atracción por los aspectos sociales por encima de la misma estrategia del juego.
  • Killers (1%): buscan competir con otros jugadores

Jugadores VS. Mundo: algunos usuarios (Socializers y Killers) que buscan relacionarse, sea del modo que sea, con otros usuarios, mientras que otros (Explorers y Achievers) prefieren dinámicas que les permitan relacionarse con el mundo del sistema.

Interacción VS. Acción: algunos usuarios (Killers y Achievers) quieren actuar directamente sobre algún elemento, ya sea otro usuario o el propio sistema, mientras que otros (Socializers y Explorers) prefieren dinámicas de interacción mutua.

Mecánicas de juego:

Las mecánicas de juego son aquellas reglas que consiguen que la actividad se asimile a un juego o a una actividad lúdica, pues consiguen la participación y el compromiso por parte de los usuarios a través de una sucesión de retos y barreras que han de superar.  Existen muchas mecánicas de juego distintas, pero cabe destacar:

  • Recolección: se usa la afición de coleccionar de los usuarios y la posibilidad de presumir ante nuestras amistades de estas colecciones.
  • Puntos: trata de incentivar al usuario mediante un sistema de puntos con el que conseguir algo, como prestigio o premios.
  • Comparativas y clasificaciones: someten a los usuarios a un sistema de clasificación que tiene en cuenta su implicación en la actividad. De esta manera se explota el espíritu competitivo de los usuarios.
  • Niveles: con este sistema se premia la implicación del usuario en la actividad otorgándole un nivel o descripción con el que distinguirse del resto, y que anima a los usuarios nuevos a igualarlos.
  • Realimentación o feedback: cuando el sistema responde a las actividades del usuario, éste valora que el trabajo que ha hecho tiene una implicación relevante.
  • Reconocimiento social: Se da a conocer públicamente que logros o acciones ha realizado el usuario

Prácticas para aumentar el engagement:

  • Adaptación hedónica: premiar cada vez que se entra de alguna forma. Se crea la sensación de que es necesario entrar a diario. Sentimiento de beneficio si se entra de pérdida si no se entra.
  • Generar tareas incompletas (Efecto Zeigarnik): el usuario tiene tendencia a recordar las tareas no terminadas y sentir la necesidad de darles fin. La forma es estructurar la gamificación por “capítulos” que indiquen, u obliguen, cuando parar pero que dejen tareas pendientes.
  • Sensación de control: el usuario debe de tener la sensación de que sus acciones son las que causan todo.
  • Captar la atención rápidamente: un usuario prueba entre entre 90 segundos y 3 minutos antes de decidir si sigue. Hay que engancharle pronto y darle alguna recompensa por hacerlo bien lo antes posible. No perder tiempo, no dejarle “explorar” ir directos a engancharle.
  • Interactividad: el usuario debe de estar realizando acciones, no es un ente pasivo.
  • Perseguir al usuario: notificaciones, emails, insistir sin resultar pesado.
  • Refuerzo positivo: hacer que el usuario sienta que es realmente bueno en su labor. Alabar su desempeño. 
  • Interacciones personalizadas: usar el nombre del usuario, un trato cercano y el humor aumenta el éxito de las interacciones.
  • Crear competición: compararse con los demás incentiva a avanzar para superarles.

Que hace a una gamificación buena:

  • No ha de ser intrusiva, se tiene que poder usar el software sin participar en el juego.
  • Orientada a unir al equipo más que a la competición.
  • Permite socializar (el 80% de los jugadores son sociales).
  • No es cuestión de hacer que el trabajo sea un juego es cuestión de dar un extra para incentivar.
  • Buscar el refuerzo positivo y premiar. Evitar el castigo y las penalizaciones.
  • Hay tareas o momento mentalmente desagradables, la gamificación puede hacer el trance más fácil.
  • Hay que tratar de integrarla dentro de “una historia” que motive al usuario a seguir a delante.
  • Tener objetivos personalizados.
  • Permitir compararse con los demás promoviendo la sana competencia.
  • Ser útil, no ha de ser simplemente dar puntos o premios, los objetivos propuestos deben de tener un fin más allá de simplemente “enganchar” al usuario.

Transformar un valor de una escala a otra en Arduino. Map

Hay veces que tenemos un valor expresado en una escala y queremos pasarla a otra. Por ejemplo uno de los casos más habituales es el calcular un porcentaje. Que pasamos un número expresado en una escala a otra que va de 0 a 100. En Arduino para pasar un valor de un rango o escala [in_min, in_max] a otro [out_min, out_max] podemos usar la función map.

long map(long x, long in_min, long in_max, long out_min, long out_max)

La función map toma 5 parámetros:

  • x: Valor a transformar
  • in_min: Valor más bajo de la escala origen
  • in_max: Valor más alto de la escala origen
  • out_min: Valor más bajo de la escala destino
  • out_max: Valor más alto de la escala destino.

La función tiene la siguiente implementación interna:

long map(long x, long in_min, long in_max, long out_min, long out_max) { 
    return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min; 
}

Os habréis dado cuenta de que trabajo con long ¿Qué pasa si queremos otro tipo de datos?. Muy fácil, nos hacemos nosotros mismos la función:

float floatMap(float x, float in_min, float in_max, float out_min, float out_max) { 
    return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min; 
}


double doubleMap(double x, double in_min, double in_max, double out_min, double out_max) { 
    return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min; 
}

Optimizar la función map

Ya que nos hemos puesto a crear nuestras funciones veamos como podemos optimizar los cálculos, si siempre tenemos que usar la función map con los mismos rango de números podemos crear nuestra versión personalizarla para que se ejecute más rápido. Es tan sencillo como sustituir los valores min y max de cada rango y simplificar. Veamoslo con un ejemplo, vamos a crearnos nuestro propio map que transforme de la escala de 0 a 1023 a otra escala de 0 a 255.

in: 0..1023
out: 0..255
int_min = 0
int_max = 1023
out_min = 0
out_max = 255

Reemplazamos:

long customMap(long x) { 
    return ((x - 0) * (255 - 0) / (1023 - 0)) + 0; 
}

Simplificamos donde podamos:

long customMap(long x) { 
    return (x * 255) / 1023; 
}

Ahora tenemos nuestra función personalizada que realiza solo dos operaciones. Como no es necesario pesarle los rangos usa solo un parámetro.

Lanzar tareas en una web cuando el navegador está desocupado. RequestIdleCallback

Un problema típico cuando desarrollas webs con mucho javascript es tener que ejecutar ciertas funciones (precarga, envío de estadísticas, actualizar los datos almacenados en local,…) pero que esta ejecución ocurra cuando la carga de la web haya terminado. Y con carga no me refiero únicamente a que haya terminado de cargar el documentos, si no de inicia izar todas las librerías para no afectar al rendimiento de la web. Para ello existe una solución en los navegadores: RequestIdleCallback

RequestIdleCallback lo que hace es encolar las funciones que se le pasan y llamarlas cuando el el navegador tenga poca carga de trabajo, así se mejora el rendimiento de la web y la experiencia de usuario. Su uso es muy sencillo:

requestIdleCallback(nonEssentialFunction);

Donde nonEssentialFunction es la función a la que se llamará cuando el navegador quede inactivo. La función recibe un parámetro un objeto deadline que tiene dos propiedades que podemos usar para planificar la ejecución de nuestro código:

  • timeRemaining(), una función que devuelve cuanto tiempo tenemos para ejecutar nuestro código.
  • didTimeout, que indica si el tiempo fijado como limite para ejecutar nuestra función (más adelante lo veremos) ha expirado. Si su valor es true, timeRemaining() devolverá 0.

Es decir que consultando deadline.timeRemaining() podemos saber si tenemos tiempo suficiente para ejecutar nuestro código. Hay que decir que es un valor orientativo y que si realmente nuestro código tarda más tiempo en terminar no pasara nada.

Veamos el ejemplo más simple, ejecutar una solo función:

function nonEssentialFunction(deadline) {
  task();
}

Si tenemos que realizar varias tareas podemos ir haciéndolas de una en una hasta que se termine el tiempo. na vez terminado el tiempo no se han acabado todas las tareas se puede volver a llamar a requestIdleCallback:

function nonEssentialFunction(deadline) {
    while (deadline.timeRemaining() > 0){ //mientras quede tiempo
        task(n); //ejecutar tarea n
        n--;
    }

    if(n > 0) { //si aun quedan tareas se encola la función otra vez
        requestIdleCallback(nonEssentialFunction);
    }
}

Veamos un ejemplo completo:

<html>
<script>
    function nonEssentialFunction(deadline) {
        while (deadline.timeRemaining() > 0)
            console.log(deadline.timeRemaining());
    }

    //Se prepara la función cuando este libre el procesador
    requestIdleCallback(nonEssentialFunction);
</script>

<body>
</body>

<script>
    //esto se ejecuta antes que nonEssentialFunction
    for(let i = 0; i < 100; i++){
        console.log(i);
    }    
</script>
</html>

Poner un limite de tiempo

Puede ser que no queramos que la función que queremos llamar se retrase demasiado, para ellos podemos pasar otro parámetro que establece el tiempo de expiación, pasado ese tiempo se lanza la ejecución de la función:

requestIdleCallback(nonEssentialFunction, { timeout: 2000 });

El tiempo viene expresado en milisegundos.

Cuando una función es ejecuta porque expira el tiempo fijado en timeout se puede ver en que deadline.didTimeout es true.

function nonEssentialFunction(deadline) {
    while (deadline.timeRemaining() > 0 || deadline.didTimeout )
        console.log(deadline.timeRemaining());
}


requestIdleCallback(nonEssentialFunction, {timeout, 3000});

Comprobar la aleatoriedad. Test de rachas.

Uno de los problemas de tener un generador de números que parecen aleatorios es estar seguro de si lo son. Hay que tener en cuenta que hablamos de números aleatorios justos, donde todos sean igual de probables, en este caso de números binarios que con un 50% salga 0 o 1 (existen formas de asegurarse de que una fuente aleatoria es justa). Vamos a ver el test de rachas para validar la aleatoriedad.

Test de rachas

En el caso de números binarios este test es muy fácil de entender, contamos el número de rachas que hay en los datos. ¿Qués un racha? Cada vez que un valor es distinto que el valor anterior. Por ejemplo:

00110101100111100

Si lo separamos en rachas:

00 – 11 – 0 – 1 – 0 – 11 – 00 – 1111 – 00

Ahora contamos las rachas, los ceros y los unos. En este caso hay 9 rachas, 8 ceros y 9 unos.

Si el número de rachas es R, el número de ceros es n0, el de uno es n1 y n = n0+n1.

media => u = (2*n0 *n1 / n) + 1

varianza => var = 2*n0*n1*(2*n0*n1-n) / n² * (n-1)

desviación típica => des = sqrt(var)

Z = R + c – u / des

Si R > u → c = -0,5

Si R < u → c = 0,5

El resultado es el Z score. Podemos usar tablas para saber su valor pero si queremos tener una buena aproximación con una seguridad del 95% de que es una distribución aleatoria no puede ser mayor de 1.6 ni menor de -1.6.

R = 9

n0 = 8

n1 = 9

n = 17

u = (298 / 17) +1 = 9,47

var = 298 * (298-17) / 17² * (17-1) = 18,10

des = 4,25

Z = 9 – 0,5 – 9,47 / 4,25 = -0,22

-0,22 esta entre 1.6 y -1.6 con lo cual lo consideraríamos como aleatorio.

Creatividad artificial. Generar imágenes para microcuentos con VQGAN+CLIP

Llevo un tiempo probando VQGAN+CLIP para generar imágenes a partir de texto y quería hacer algo con él, pero no sabia el que. Hasta que recordé que hace años tenia un twitter llamado tweetcuento donde publicaba unos microcuentos que escribía. Sin entrar en detalles sobre mi calidad como cuentista me pareció que podría ser una buena idea usarlo de base para un experimento de creación de imágenes

VQGAN+CLIP es la unión de dos sistemas. VQGAN y CLIP . CLIP funciona como un puente entre las imágenes y el texto. Explicado pronto y mal, CLIP generaría el mismo valor (o al menos uno muy cercano) para una foto de una gafas que para la palabra «gafas». Ahí radica la clave de este sistema de generación de imágenes, se le pasa un texto a CLIP y luego una imagen generada por VQGAN. Y trata de que el valor del texto y la imagen se aproximen. VQGAN usa este valor para mejorar su resultado. Si queréis una explicación más exhaustiva DotCSV tiene un video estupendo sobre el tema.

Todo este proceso lo he realizado a partir de un notebook de google colab creado por Katherine Crowson . Sin embargo para usarlo con mis cuentos tenia que realizar varios pasos.

CLIP solo funciona en inglés así que toca traducir los microcuentos. Podría hacerlo yo pero me parece más interesante que lo haga un traductor automático (y es posible que lo haga mejor que yo). He recurrido al traductor de Google, pero no uso directamente sus resultados. Antes los reviso y solo los modifico si hay alguna palabra cuya traducción es errónea ya que podría influir en el resultado. En el resto delos casos dejo la traducción como esta. En las pruebas realizadas hasta ahora no he necesitado modificar la mayoría de los resultados.

Luego adapto el texto para pasarlo a CLIP. Elimino los símbolos que no sean letras o números. Cada frase separada por un punto la separo, los mismo hago con las conversaciones.

- Quiero ese globo - la niña señaló un pobre globo que apenas se elevaba del suelo
- Los hay más bonitos
- Si, pero este sé que no me dejará

Se convierte en

["Quiero ese globo", "la niña señaló un pobre globo que apenas se elevaba del suelo", "Los hay más bonitos", "Si pero este sé que no me dejará"]

En realidad el texto estaría en inglés pero el ejemplo se entiende mejor así.

Otra condición que me he autoimpuesto es que se generan solo 3 imágenes por cada cuento. Elegiré la que me parezca más adecuada, si dudo entre varias imágenes publicaré todas entre las que esté dudando.

Además esperare un par de días para evitar sesgos. He notado que cuando estas mirando como el sistema produce sus imágenes te parecen mucho mas sorprendentes unos que días después.

Las imágenes obtenidas son tal y como las genera VQGAN+CLIP . Muchas de ellas serian fácilmente mejorables con algún pequeño retoque.

Por último y puesto que no podían faltar los NFTs cada imagen es convertida en un NFT y ofrecida en una galería en Opensea. No creo que nadie vaya a comprarlas pero quería aprender el proceso.

Veamos un ejemplo de todo este proceso, partiendo del cuento:

"Las máquinas se rebelaron, ganaron la guerra y esclavizaron a la humanidad. Se convirtieron en los amos del mundo. Esta situación se prolongó durante tres años hasta que las máquinas perdieron ante su mayor enemigo, la obsolescencia programada."

La imagen obtenido ha sido:

Para ver mas ejemplos los iré publicando poco a poco en tweetcuento

Password de un solo uso (OTP) en Arduino (HMAC, HTOP, TOTP)

Los password de un solo uso también llamados OTP (One Time Password) son passwords que solo se pueden usar una vez o durante un periodo de tiempo breve. Es una buena medida de seguridad, aunque estas contraseñas sean robadas o interceptadas se reduce el tiempo que el atacante puede acceder al sistema. Uno de sus usos es como segundo factor de autenticación. Casi todos habremos tenido que usar alguna vez códigos que nos envían al móvil o que genera algún aplicación y cuyo tiempo de vida es breve. Eso es un OTP.

Cuando hay un canal seguro para notificar el OTP, por ejemplo un mensaje por SMS. Es sencillo crear un OTP, se genera un código aleatorio asociado a ese usuario y listo.

Pero no siempre hay un canal seguro. En ese caso la solución es algo más complicada. Necesitamos tener dos programas que generen exactamente la misma contraseña en el mismo momento. Para estos sistemas necesitaremos dos cosas.

  • Un secreto o clave, que es compartido por ambos sistemas y debe de permanecer en secreto para que sea seguro. La llamaremos k
  • Una secuencia o contador, este dato puede ser publico sin ningún problema (en teoría) sirve para que ambos programas generadores creen la misma contraseña. Lo llamaremos c

Con random

Una implementación muy sencilla y de muy baja seguridad (suficiente para proyectos caseros) es usar el generado de números pseudoaleatorios de Arduino. En este caso el secreto es la semilla con la que se inicializa el generador. En este caso la secuencia o contador no es explicito, no se le pasa es implícito al numero de veces que se ha llamado a la función random. Lo que añade la dificultad añadida de tener ambas secuencias sincronizadas.

long randNumber;
void setup() {
  randomSeed(k);
}
void calculateOTP() {
  return random(10000, 99999);//contraseña de 5 digitos
}

Otro problema es que cada vez que se reinicia perdemos el punto donde estábamos de la secuencia y esta vuelve a empezar. Seria necesario guardar en la EEPROM el número de veces que hemos generado un OTP y luego llamar a la función ese numero de veces para resincronizar el estado del generador de números pseudoaletaorios.

Con una función hash

Otra táctica parecida es usar una función de hash. Para calcular la primera contraseña se llama a la función de hash con el secreto k, luego se usa el password anteriror, añadiendole el secreto k para calcular el siguiente:

k0 = H(k)

k1 = H(k0+k)

k2 = H(k1+k)

k3 = H(k2+k)

….

kn = H(kn-1+k)

La ventaja de este sistema es que basta con guardar en la EEPROM el último password generado para mantener la sincronización.

HTOP

Estos dos sistemas nos sirven para desarrollos caseros que no requieren demasiada seguridad para hacer una implementación segura podemos usar HMAC (hash-based message authentication code). HMAC usa una función de hash, un secreto o clave y un mensaje, en este caso el mensaje será el contador. A esta implementación se le conoce como HTOP (HMAC-based one-time password).

Empecemos viendo como funciona HMAC

HTOP(k, c) = HMAC(k, c) = H( (k ^ opad) || H(k ^ ipad) || c )

  • H es la función e hash
  • k es la clave secreta
  • c es el contador
  • opad es un bloque formado por el valor 0x5c repetido
  • opad es un bloque formado por el valor 0x36 repetido
  • || es la operación OR
  • ^ es la operación XOR

En este caso no necesitamos tener el contador sincronizado. El contador se puede pasar en la petición. Supongamos que el dispositivo B intenta contactar con el dispositivo A, el proceso puede ocurrir de dos maneras:

  • B usa su contador interno y la pasa el password (TokenB ) con el contador usado para calcularlo. A calcula el password con el contador que le pasa B y verifica si coinciden
  • B le pide a A un contador y A le pasa el contador con el que B tiene que generar el password (tokenB) y se lo devuelve a A que verifica si coinciden

El segundo caso es más seguro ya que evitamos que un atacante

TOTP

Lo ideal seria que ninguno tuviera que intercambiar el contador, que ambos tuvieran un contador sincronizado. Una opción seria usar la hora actual. O un timestamp que exprese la hora actual como milisegundos transcurridos desde el 1 de enero de 1970 a las 00:00:000. Es decir que TOTP (Time-based One-time Password) es HMAC usando como mensaje el tiempo o lo que es lo mismo usar HTOP usando como contador el tiempo.

El único problema aquí es que cada milisegundo la contraseña cambia y puede ser muy poco tiempo para realizar el intercambio de password. La solución es dejar una ventana de tiempo durante la cual el password es válido. Si usamos t para indicar el tiempo en milisegundo y vt el tiempo (en milisegundos) durante el cual el password es válido.

c = Trunc(t/vt)

TOTP(k, c) = HMAC(k, c)

Así nos ahorramos la parte de tener que intercambiar el contador entre dispositivos. Ambos usan la hora actual con una ventana de tiempo vt.

El problema es que Arduino no tiene un RTC (real time clock) por lo que no tiene forma de saber directamente qué hora es, necesita un elemento externo que le informe de ello.

«TOTP» sin RTC

Hay una forma un poco tramposa de implementar TOTP sin usar un RTC. En este caso partimos de HTOP, usaremos la segunda forma de HTOP en la que A le pasa el contador a B. El funcionamiento es exactamente igual que antes solo que tras un periodo de tiempo t la variable contadorA se incrementa automáticamente dejando a B con un OTP que ya no es valido.

No es un sistema tan cómodo como tener ambos sistemas sincronizados por su reloj. Ademas de que si varios dispositivos quieren conectarse al dispositivo A puede ser complicado de gestionar y necesitarías un contador y un secreto para cada uno.

¿Cual elegir?

Las soluciones basadas en HMAC son las más seguras pero también las más exigentes en tiempo y memoria. Y aunque TOTP es la segura y cómoda implica tener un RTC y que todos los dispositivos lo tengan sincronizados. Cada uno tiene que elegir el método según el balance de seguridad y coste.

Código

Para implementar todo esto podemos usar la librería Cryptosuite para Arduino. Permite usar la funciones hash SHA-1 y SHA-256.

Una vez copiada a nuestro directorio de librerías de Arduino puede usarse añadiendo el include correspondiente

#include "sha1.h"
#include "sha256.h"

Un ejemplo de uso de HMAC es:

 uint8_t *hash;
 Sha256.initHmac(key,keyLength); //secreto y su longitud
 Sha256.print(counter); //contador
 hash = Sha256.resultHmac();

Regresión lineal con incertidumbre en Arduino

Vamos a empezar este texto develando el truco que usaremos para representar incertidumbre con la regresión lineal para Arduino y que se basa en emplear la versión con pesos del algoritmo de regresión lineal. La incertidumbre estará representada como valores con una variación de pesos según la certeza que tengamos de su valor. Usaremos el peso como porcentaje de certeza de ese dato

Esta no es la mejor ni la única manera de hacerlo. No hay que olvidar que aquí se trata de hacerlo en algo tan limitado en memoria y potencia como pude ser un Arduino UNO.

Usaremos la librería regressino, en concreto su librería para regresión lineal:

#include <LinearRegression.h>

LinearRegression lr = LinearRegression();

Una forma de incertidumbre es cuando directamente tenemos valores de los que «nos fiamos» menos que de otros. Por ejemplo, porque vienen de dos fuentes distintas. En este caso los datos menos fiables tendrán que tener un peso más bajo que los más fiables para que su influencia sobre el resultado final sea menor.

//datos fuente no fiable
lr.learn(1, 3, 0.5);
lr.learn(2, 5, 0.5);
lr.learn(3, 6, 0.5);

//datos fuente fiable
lr.learn(2, 4, 1);
lr.learn(4, 5, 1);
lr.learn(5, 6, 1);

Pero hay otro caso de incertidumbre, cuando no conocemos el valor del dato con seguridad, lo que conocemos son los valores entre los que está comprendido. Generalmente tenemos dos valores, un mínimo y un máximo o tres valores con uno más probable y un mínimo y un máximo (a veces representados como errores) entre los que ese valor puede variar. En este caso tenemos que definir cómo se distribuye el peso (probabilidad) entre estos valores. Hay que recordar que la suma total de los pesos tiene que ser igual a 1.

Una vez definida la forma en que se distribuye la probabilidad hay que descuartizarla en puntos. La idea es que esto funcione en un Arduino UNO y no podemos trabajar directamente con funciones de probabilidad.

Supongamos que para x = 10 sabemos que el valor de y está comprendido entre 2 y 3. Ahora hay que saber cómo está distribuida la probabilidad entre esos dos valores. Veamos algunas posibilidades:

  • Toda la probabilidad se concentra en cada uno de esos valores por lo tanto el 2 tendría un 50% de certeza y el 3 otro 50%. O lo que es lo mismo un peso de 0.5
lr.learn(10, 2, 0.5);
lr.learn(10, 3, 0.5);
  • La probabilidad se distribuye de forma uniforme por todo el espacio entre esos dos puntos. Para representarlo tómanos varios puntos entre 2 y 3 y les asignamos a todos la misma probabilidad.
lr.learn(10, 2, 0.2);
lr.learn(10, 2.25, 0.2);
lr.learn(10, 2.5, 0.2);
lr.learn(10, 2.75, 0.2);
lr.learn(10, 3, 0.2);
  • El punto central es mucho más probable que los extremos. Un ejemplo de como podemos hacerlo.
lr.learn(10, 2, 0.25);
lr.learn(10, 2.5, 0.5);
lr.learn(10, 3, 0.25);
  • Si por ejemplo queremos simular una distribución en campana de media u y con desviación estándar s
lr.learn(10, u, 0.682);
lr.learn(10, u-s, 0.136);
lr.learn(10, u-(2*s), 0.023);
lr.learn(10, u+s, 0.136);
lr.learn(10, u+(2*s), 0.023);