Ir al contenido


Foto

¿Random en Lazarus es hackeable?

random lazarus

  • Por favor identifícate para responder
2 respuestas en este tema

#1 Delphius

Delphius

    Advanced Member

  • Moderadores
  • PipPipPip
  • 6.295 mensajes
  • LocationArgentina

Escrito 26 agosto 2015 - 02:30

¡Hola a todos! Esta vez no es tanto una duda, sino un pedido a que me aclaren alguito de lo que estoy "investigando".

 

Resulta que entre mis pruebas a algunos módulos de mis proyectos para generar números para probar cálculos empleaba la función Random.

Lo que me llamó la atención es que en cada vez que ejecutaba y hacía pruebas veía que me mostraba diferentes números.

 

Uno me dirá, pues claro, porque eso es lo que hace random. Pues si y no. Eso es el resultado esperado mientras se invoque inicialmente a Randomize. De otra forma SIEMPRE debería obtenerse la misma secuencia. Y justamente en ninguna parte del código había puesto Randomize.

 

Mi teoría entonces pasó a que la función Random que posee Lazarus no tiene un valor fijo de semilla. Asi que hice una proyecto en limpio para probar muy simple que estaba pasando. El proyecto contiene simplemente esto:


delphi
  1. procedure TForm1.Button1Click(Sender: TObject);
  2. var rn: integer;
  3. begin
  4. rn := trunc(random * 255);
  5. showMessage(IntToStr(rn));
  6. end;
  7.  
  8. procedure TForm1.Button2Click(Sender: TObject);
  9. var rn: double;
  10. begin
  11. rn := random;
  12. showMessage(FloatToStr(rn));
  13. end;

Y empecé a jugar... Cierro la aplicación y ejecuto de nuevo. Para mi sorpresa, volvía a dar los mismos números... derrumbando mi teoría.

 

Algo no me cuadraba... Entonces vi el porqué de mi rareza. Volví a ejecutar la aplicación y ahora empecé a alternar entre el botón 1 y 2 y ahora asi la secuencia se rompía. Descubrí así que no es que yo había escrito mal o tenía algo raro en mi aplicación.

 

Simplemente se debía a que estaba generando números en diferentes circunstancias de modo que mientras no respete ese mismo orden/secuencia de acciones no tendría el mismo resultado esperado. Todo porque invoco a random desde varios puntos. :D

 

Pero algo me seguía picando la curiosidad. ¿Cómo es la función random de Lazarus? ¿Cuál es el valor de semilla? Sabía que tenía una implementación diferente a la de Delphi, que hasta el momento y tengo entendido es un generador congruencial mixto/multiplicativo, pero no había visto nada sobre el tema. Me voy a leer la ayuda y encuentro esto:

 

 

The Free Pascal implementation of the Random routine uses the Mersenne Twister to simulate randomness. This implementation has a better statistical distribution than for example a Linear Congruential generator algorithm, but is considerably slower than the latter. If speed is an issue, then alternate random number generators should be considered.

 

¿Primos Mersenne? Interesante.

Los primos Mersenne para mi son conocidos, y si, se que los generadores utilizan números primos para obtener los números pseudoaleatorios. Lo que más me llama la forma en como se los aplica. Todo un mundo nuevo.

 

Leyendo en la wiki sobre esta técnica me doy con que es una implementación mucho más "académica", y mucho más pseudoaleatoria que los generadores congruenciales clásicos. Su contra: es más lento y para secuencias muy largas o en contextos que se va estar invocando generando miles de veces no es la mejor alternativa.

 

Como quien dice, ¡Todo los días se aprende algo nuevo!

 

Ya necesita ver esto de cerca, asi que me voy al código de random y me doy con el monstruo:


delphi
  1. {$ifndef FPUNONE}
  2. function random: extended;
  3. begin
  4. random := cardinal(genrand_MT19937) * (extended(1.0)/(int64(1) shl 32));
  5. end;
  6. {$endif}
  7. {$endif FPC_HAS_FEATURE_RANDOM}

Ummm veamos ese bicho de genrand_MT19937:


delphi
  1. function genrand_MT19937: longint;
  2. const
  3. mag01 : array [0..1] of longint =(0, longint(MT19937MATRIX_A));
  4. var
  5. y: longint;
  6. kk: longint;
  7. begin
  8. if RandSeed<>OldRandSeed then
  9. mti:=MT19937N+1;
  10. if (mti >= MT19937N) { generate MT19937N longints at one time }
  11. then begin
  12. if mti = (MT19937N+1) then // if sgenrand_MT19937() has not been called,
  13. begin
  14. sgenrand_MT19937(randseed); // default initial seed is used
  15. { hack: randseed is not used more than once in this algorithm. Most }
  16. { user changes are re-initialising reandseed with the value it had }
  17. { at the start -> with the "not", we will detect this change. }
  18. { Detecting other changes is not useful, since the generated }
  19. { numbers will be different anyway. }
  20. randseed := not(randseed);
  21. oldrandseed := randseed;
  22. end;
  23. for kk:=0 to MT19937N-MT19937M-1 do begin
  24. y := (mt[kk] and MT19937UPPER_MASK) or (mt[kk+1] and MT19937LOWER_MASK);
  25. mt[kk] := mt[kk+MT19937M] xor (y shr 1) xor mag01[y and $00000001];
  26. end;
  27. for kk:= MT19937N-MT19937M to MT19937N-2 do begin
  28. y := (mt[kk] and MT19937UPPER_MASK) or (mt[kk+1] and MT19937LOWER_MASK);
  29. mt[kk] := mt[kk+(MT19937M-MT19937N)] xor (y shr 1) xor mag01[y and $00000001];
  30. end;
  31. y := (mt[MT19937N-1] and MT19937UPPER_MASK) or (mt[0] and MT19937LOWER_MASK);
  32. mt[MT19937N-1] := mt[MT19937M-1] xor (y shr 1) xor mag01[y and $00000001];
  33. mti := 0;
  34. end;
  35. y := mt[mti]; inc(mti);
  36. y := y xor (y shr 11);
  37. y := y xor (y shl 7) and TEMPERING_MASK_B;
  38. y := y xor (y shl 15) and TEMPERING_MASK_C;
  39. y := y xor (y shr 18);
  40. Result := y;
  41. end;

Lo que me preocupa es justamente los comentarios: ¿Hack? ¿Es vulnerable? :|  ¡Mi no entender!

 

El código inicia según cierto valor de semilla, se ve claro en sgenrand_MT19937(randseed); pero el asunto es que en ningún momento se da algún valor a este parámetro. De hecho randSeed es una variable global que en ningún momento se establece valor alguno, que no sea en esta función (cuando hace randseed := not(randseed)) o en en Randomize:


delphi
  1. procedure randomize;
  2. begin
  3. randseed:=GetTickCount;
  4. end;

Por lo que su valor, al igual que oldRandSeed (otra variable global) inicialmente tienen en valor 0.

 

¡Que alguien me explique!

 

Saludos,


  • 0

#2 Agustin Ortu

Agustin Ortu

    Advanced Member

  • Moderadores
  • PipPipPip
  • 831 mensajes
  • LocationArgentina

Escrito 26 agosto 2015 - 03:46

En este contexto no significa que es vulnerable. Es un "hack de la programacion"
 
Es un alias de: mala programacion, codigo lento, dificil de mantener, dificil de depurar, que no tiene compatibilidad hacia atras/adelante, "code smell", que no sige los estandares (o incluso va en contra), que puede tener side-effects, que se puede romper sin que nadie se de cuenta, y miles de etc
 
http://programmers.s.../what-is-a-hack
 
Justamente los "hack" generan esa confusion que tenes ahora de, de donde sale esto, donde esta inicializado, etc
 
Este tipo de hacks fuerzan a algo a funcionar o bien es algo que funciona pero es peludo
 
Edito:
 
Un ejemplo bastante boludo
 
Imaginate que tengo la funcion OrdenAlfabetico que recibe un TStringList y me lo ordena alfabeticamente
 
Ahora, por la razon X si tengo "Pepito" y "Carlitos" seguidos, mi funcion te deja el restultado asi:
 
Pepito
Carlitos
 
Evidentemente esta mal. Entonces ahi es donde ocurre la magia:
 

delphi
  1. // Hack
  2. // we should... bla bla
  3. if (strings[i] = 'Pepito') and (strings[i+1] = 'Carlitos') then
  4. begin
  5. ...


  • 1

#3 Delphius

Delphius

    Advanced Member

  • Moderadores
  • PipPipPip
  • 6.295 mensajes
  • LocationArgentina

Escrito 26 agosto 2015 - 04:10

Gracias por la aclaración OrtuAgustin.

 

Si es una implementación no muy segura entonces quizá no siempre sea conveniente emplear esta función Random. En especial para proyectos importantes.

 

Para un trabajo a futuro que tengo en mente ya esto me convenció de que tendré que buscar otros generadores. No creo que me resulte complicado, ya antes hace unos años desarrollé una biblioteca de generadores y de test de aleatoriedad para la cátedra de Modelos y Simulación. Podría tomarla de nuevo, ampliarla y mejorarla (si es que no encuentro algo profesional ya hecho). Estoy previendo que necesitaré números bastantes grandes (en algunos casos de aritmética flotante y en otros casos números enteros... muy seguramente tenga que ir hacia el Int64) y en grandes cantidades asi que seguiré la advertencia que da la propia Wikipedia y la ayuda de Lazarus: ¡Usen otro!

 

EDITO:

Pues no se si será medio "hackeable" pero si que tiene una implementación un tanto insegura... la variable randseed pensé que a pesar de ser global, estaba dentro de la sección implementation para que no estuviera al alcance de cualquiera. Pero ya he visto que no... basta con meterse así:

 

System.randseed := 123456789;

 

Para cambiar la semilla en cualquier parte del código que uno quiera. El valor de semilla no debiera ser posible de alterar por uno que elija... Se supone que Randomize debe ser la única forma de "acceder", y sin saber el valor por el que se ha modificado.

 

Saludos,


  • 0





Etiquetado también con una o más de estas palabras: random, lazarus