¿Hay algún sistema operativo de comparación de cadenas de prueba de concepto que funcione?

4

He intentado reproducir un oráculo de tiempo de comparación de cadenas en dos idiomas (Java y Python), pero no veo ninguna correlación en el tiempo en función de la entrada en la comparación. ¿Hay algún ejemplo por ahí, o ves algún problema con mi código? Tenga en cuenta que me gustaría algo simple, como el ejemplo que he dado. Un ataque a un programa grande "en la naturaleza" no es un buen ejemplo.

Tampoco he podido encontrar ejemplos simples y listos para ejecutar de ataques de tiempo. Creo que he deshabilitado la optimización de Java con -Djava.compiler = NINGUNO. Se necesita una cantidad de tiempo considerable para ejecutar el código, por lo que claramente no está optimizando completamente el código.

Parece extraño que se haya hablado con frecuencia sobre esto, pero no hay ejemplos reales que se puedan encontrar fácilmente.

Aquí está mi código Java tal como está hoy. La salida varía un poco aleatoriamente sin aparentemente una correlación que haya identificado. He agregado algunas notas a la salida para que pueda ver cuáles deberían ser comparaciones más lentas.

public class TimingAttackJavaTest {
    public static void main(String[] args) {
        TimeCompare("a0", "b0", "a, b      ");
        TimeCompare("aaaaaaaaaa1", "bbbbbbbbbbb1", "a*10, b*10");
        TimeCompare("aaaaaaaaaa10", "bbbbbbbbbbb10", "a*10, b*10");
        TimeCompare("aaaaaaaaaa2", "b2", "a*10, b  ");
        TimeCompare("a3", "bbbbbbbbbbb3", "a, b*10  ");
        TimeCompare("aaaaaaaaaa4", "bbbbbbbbbbb4", "a*10, b*10  ");
        TimeCompare("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1", "a*100, a*100");
        TimeCompare("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1", "a*100, a*100");
        TimeCompare("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa2", "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb", "a*100, b*100");
        TimeCompare("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa2", "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb", "a*100, b*100");

        TimeCompare("a", "a", "a, a      ");
        TimeCompare("aaaaaaaaaaa", "aaaaaaaaaaa", "a*1, a*10 ");
        TimeCompare("1aaaaaaaaaa10", "2bbbbbbbbbbb10", "a*10, b*10");
    }


    static void TimeCompare(String a, String b, String outputLabel)
    {
        boolean temp = false;
        long startTime;
        long endTime;
        long duration;

        startTime = System.nanoTime();
        for(int i = 0; i < 10000000; i++)
        {
            temp = a.equals(b);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println(outputLabel + temp + "\t\t" + duration);

    }
}

Salida (tenga en cuenta que la primera comparación siempre es lenta, ya que el programa se inicia):

a, b      false     930418800
a*10, b*10false     513034800
a*10, b*10false     510905300
a*10, b  false      534267200
a, b*10  false      524720700
a*10, b*10  false       509250100
a*100, a*100false       516159000    **This should return slowly**
a*100, a*100false       508714700    **This should return slowly**
a*100, b*100false       511160700    **This should return quickly**
a*100, b*100false       522029800    **This should return quickly**
a, a      true      278492700
a*1, a*10 true      284238900
a*10, b*10false     506245000
    
pregunta Alex Lauerman 04.02.2014 - 15:39
fuente

1 respuesta

1

Su ejemplo no funciona por varias razones, y la principal es el hecho de que está usando los mejores datos de casos posibles (es decir, es menos probable que muestre las diferencias). Si la diferencia en las cadenas era al principio, la comparación anticipada debería alertarlo. Sin embargo, dado que estás utilizando un lenguaje JIT, existen todo tipo de posibilidades extrañas que podrían dificultar dicha comprobación.

La mejor forma de demostrar este tipo de ataque no es con los bucles, sino con una única medición en un lenguaje de bajo nivel como C.

Aquí hay un ejemplo rápido que funciona muy bien:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
using namespace std;

// this is just strcmp() wrapped in timer calls
bool CheckEqual(char* a, char* b, bool show)
{
    int i, r, trv;
    long time_pre, time_post;
    struct timespec ts;

    if((trv = clock_gettime(CLOCK_MONOTONIC,&ts)) != 0) {
        printf("Timing error, pre. Code = %d\n", trv);
    }
    time_pre = ts.tv_nsec + (ts.tv_sec * 1000000000L);

    r = strcmp(a, b);

    if((trv = clock_gettime(CLOCK_MONOTONIC,&ts)) != 0) {
        printf("Timing error, post. Code = %d\n", trv);
    }
    time_post = ts.tv_nsec + (ts.tv_sec * 1000000000L);

    if (show)
        printf("Time: %ld\n", time_post - time_pre);
    else
        printf("First compare done.\n");

    return r == 0;
}

// this function helps us avoid the problem of the compiler being too smart.
// if we were to use string literals that were equal, it'd optimise compile-time
// constant strings into a single instance, so strcmp() would just early-out on
// the fact that the two pointers were equal, which is not what we want to
// demonstrate here - in reality we'd be comparing buffers that aren't static.
char* MakeStr(char c, int n)
{
    int i;
    char* s = (char*)calloc(n+1, sizeof(c));
    for(i=0; i<n; i++)
        s[i] = c;
    return s;
}

int main()
{
    // equal apart from last
    char* aa = MakeStr('0', 64);
    char* ab = "0000000000000000000000000000000000000000000000000000000000000001";

    // equal apart from first
    char* ba = MakeStr('0', 64);
    char* bb = "1000000000000000000000000000000000000000000000000000000000000000";

    // inequality in the middle
    char* ca = "0000000000000000000000000000010000000000000000000000000000000000";
    char* cb = "0000000000000000000000000000001000000000000000000000000000000000";

    // equal
    char* da = MakeStr('0', 64);
    char* db = MakeStr('0', 64);

    // first call to strcmp() and time functions will result in cache misses
    // so we call it once and don't display output to account for that.
    CheckEqual(aa, ab, false);

    printf("Equal but last, ");
    CheckEqual(aa, ab, true);
    printf("Equal but first, ");
    CheckEqual(ba, bb, true);
    printf("Equal but mid, ");
    CheckEqual(ca, cb, true);
    printf("Completely equal, ");
    CheckEqual(da, db, true);

    free(aa); free(ba); free(da); free(db);
    return 0;
}

Tu salida debería tener un aspecto similar al siguiente:

First compare done.
Equal but last, Time: 345
Equal but first, Time: 229
Equal but mid, Time: 234
Completely equal, Time: 270

¿Nota la gran diferencia entre los dos primeros? Esto se debe a la optimización de early-out , por lo que la comparación sale tan pronto como encuentra una diferencia. En la segunda comparación, toma menos tiempo porque la comparación del primer personaje muestra que no es igual, por lo que puede regresar antes. En la tercera comparación, vemos que esto va un poco más lejos en la cadena, lo que resulta en un tiempo de ejecución ligeramente más largo que el "igual pero primero", pero más corto que el "igual pero último".

El completamente igual es una bestia interesante. Supongo que, cuando el último carácter no es igual, hay alguna lógica adicional requerida. En comparación, el completamente igual toma menos tiempo, asumo porque solo tiene que devolver 0.

    
respondido por el Polynomial 04.02.2014 - 17:46
fuente

Lea otras preguntas en las etiquetas