Неожиданное время выполнения цикла - PullRequest
Новая
       17

Неожиданное время выполнения цикла

0 голосов
/ 30 октября 2019

Я кодирую демонстрацию атаки по побочному каналу. Я ожидал, что простая посимвольная проверка с ранним возвратом займет линейно-пропорциональное время для первого неверного символа. Например, если у меня есть пароль password и ввод qassword (первая буква неверна) и passwore (последняя буква неверна), я ожидал, что qassword займет меньше времени для сравнения, чем passwore (потому чтоон выходит рано, с первой неправильной буквы).

Цикл, о котором идет речь: 

for (int i = 0; i < 26; i++) {
    if (a[i] != in[i]) {
        return 1;
    }
}
return 1;

Я отключил оптимизацию с помощью -O0.

Выводполный код: 

Diff(9326)
Diff(2)
Diff(1)
Diff(9292)

Это удивляет меня, потому что первый случай проверяет все буквы (хорошо, должно занять больше всего времени), второй случай проверяет все, кроме последней буквы (следуетзаймет примерно столько же времени, что и в первом случае?), а в последнем случае следует проверять только первую букву (хорошо, это занимает наименьшее количество времени).

Мой вопрос: почему так долгослучай, когда он полностью правильный и быстрый для всех остальных случаев (даже если неправильная буква находится посередине)?

Полный код ( Попробуйте онлайн ): 

#include <stdio.h>
#include <time.h>

int check(char* in) {
    const char* a = "abcdefghijklmnopqrstuvwxyz";

    for (int j = 0; j < 100000; j++) {
        for (int i = 0; i < 26; i++) {
            if (a[i] != in[i]) {
                return 1;
            }
        }
    }

    return 1;
}

int main() {
    clock_t start;
    clock_t diff;

    // All correct
    start = clock();
    check("abcdefghijklmnopqrstuvwxyz");
    diff = clock() - start;

    printf("Diff(%ld)\n", diff);

    // Last letter wrong
    start = clock();
    check("abcdefghijklmnopqrstuvwxya");
    diff = clock() - start;

    printf("Diff(%ld)\n", diff);

    // First letter wrong
    start = clock();
    check("zbcdefghijklmnopqrstuvwxyz");
    diff = clock() - start;

    printf("Diff(%ld)\n", diff);

    // Check if cache issue (same as case 1)
    start = clock();
    check("abcdefghijklmnopqrstuvwxyz");
    diff = clock() - start;

    printf("Diff(%ld)\n", diff);
}

1 Ответ

0 голосов
/ 30 октября 2019

Проблема в вашем коде. Если все символы совпадают, то он выполнит проверку 100000 раз. Но если какой-либо один символ не совпадает, вы вернетесь из цикла в самой первой итерации. Следовательно, разница во времени невелика, когда все символы не совпадают.

Вместо return поместите оператор break внутри блока if 

        for (int j = 0; j < 100000; j++) {
                 for (int i = 0; i < 26; i++) {
                     if (a[i] != in[i]) {
                         break;
                     }
                  }
        }
...