c - 意外的循环运行时间

Question

我正在编写侧信道攻击演示。我期望进行简单的逐字符检查并提前返回，以便对第一个不正确的字符采取线性比例的时间。例如，如果我有密码 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)

这让我感到惊讶，因为第一种情况是检查所有字母(好吧，应该花费最长的时间)，第二种情况是检查除最后​​一个字母之外的所有字母(应该与第一种情况花费大约相同的时间？ )，最后一个案例应该只检查第一个字母(好的，花费最少的时间)。

我的问题是，为什么在完全正确的情况下需要这么长的时间，而在所有其他情况下却需要这么快的时间(即使中间有错误的字母)？

完整代码为( Try It Online ):

#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);
}

Answer 1

问题出在你的代码中。如果所有字符都匹配，则会检查 100000 次。但是，如果任何一个字符不匹配，那么您将从第一次迭代本身的循环中返回。因此，当所有字符都不匹配时，时间差异很小。

在 if block 中放置一个 break 语句，而不是 return

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