Быстрая оценка постоянного времени от "x==7" до 1 (true) или 0 (false) в Java

Question

Быстрая оценка постоянного времени от "x==7" до 1 (true) или 0 (false) в Java

Я хочу перенести криптографическую функцию с C на Java. Функция должна выполняться за постоянное время, поэтому никакие условные переходы (и поиск таблиц по x) не допускаются.

Исходный код C:

int x,result;
...
result = (x==7);
...

Таким образом, "результат" устанавливается в 1, если "x==7", и в 0 в противном случае. Затем переменная "результат" используется в дальнейших вычислениях.

Я сейчас ищу лучший способ перенести это на Java. Так как в выражениях Java вычисляются булевы значения, а не целые числа, необходимо моделировать вышеприведенные операторы.

Я сейчас пользуюсь

int x,result;
...
result = (1<<(x-7))&1;
...

который отлично работает для меня, так как мой х находится в диапазоне {0,...,15}. (Обратите внимание, что функция сдвига использует только младшие 5 битов, так что вы получите ложные срабатывания, когда x слишком большой.)

Выражение будет оцениваться миллионы раз, поэтому, если, к примеру, найдется умное решение, которое использует только 2 оператора вместо 3, это ускорит общее вычисление.

7

java performance bit-manipulation constant-time

Источник

user4303790 04 сен '15 в 23:13

5 ответов

Другие вопросы по тегам java performance bit-manipulation constant-time

user4856258 05 сен '15 в 04:18 2015-09-05 04:18 · Answer 1 · 2015-09-05 04:18

Наилучшим вариантом, как отмечает @Hosch250, является троичный оператор. Давайте посмотрим на ассемблер, сгенерированный компилятором JIT для этого метода:

public static int ternary(int x) {
    return x == 7 ? 1 : 0;
}

Это на самом деле зависит от профилирования веток. Когда ваш x имеет значение 7 довольно часто он составляется так:

xor %r11d,%r11d
mov $0x1,%eax
cmp $0x7,%edx
cmovne %r11d,%eax  ;*ireturn
                   ; - Test::ternary@11 (line 12)

Смотрите, что троичный был заменен cmovne которая не является инструкцией ветки.

С другой стороны, если вы пройдете 7 в очень редких случаях (например, один раз на 5000 звонков), тогда ответвление находится здесь:

cmp $0x7,%edx
je <slowpath>  ;*if_icmpne
                       ; - Test::ternary@3 (line 12)
xor %eax,%eax

Теперь ветвление почти никогда не используется, поэтому чем быстрее выполняется условие, так как предиктор ветвления ЦП будет почти всегда верным. Обратите внимание, что <slowpath> это не просто return 1; также обновляет профиль ветвления, поэтому, если случается, что шаблон изменился во время выполнения программы (7 станет появляться чаще), тогда метод будет перекомпилирован в первую версию.

В общем, не пытайтесь быть умнее JIT-компилятора в таких простых случаях.

user139985 05 сен '15 в 04:18 2015-09-05 04:18 · Answer 2 · 2015-09-05 04:18

Итак, я думаю, что причина, по которой вы спрашиваете это, заключается в том, что если время выполнения крипто-функции зависит от входных данных функции, то злоумышленник может получить подсказки относительно этих входных данных, измерив время выполнения. (Следовательно, обычные рекомендации "преждевременной оптимизации" и "не пытаться перехитрить компилятор" на самом деле не применимы.)

В свете этого, вот мои предложения:

Если x является константой во время компиляции (или JIT-компиляции), то есть вероятность, что код будет оптимизирован либо result = true; или же result = false;

Если x не является константой, но существует небольшой диапазон возможных значений, тогда , вероятно, будет работать один из следующих подходов:

// It is possible but unlikely that the JIT compiler will 
// turn this into conditional code.
private boolean[] LOOKUP = new boolean[] {
        true, true, true, true, true, true, true, false};
...
result = LOOKUP[x];

// This depends on how the JIT compiler translates this to native
// code.
switch (x) {
case 0: case 1: case 2: case 3: case 4: case 5: case 6: 
    result = false;
case 7:
    result = true;
}

Проблема заключается в том, что при любом подходе, который я могу придумать, JIT-компилятор может юридически оптимизировать код без ветвления в код с ветвлением. Если это критично для безопасности, вам необходимо изучить фактический собственный код, генерируемый для каждой платформы, которую необходимо сертифицировать.

Другой подход заключается в следующем:

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

Конечно, еще одна вещь, которую стоит отметить, это то, что это может быть спорным в любом случае; например, если result затем используется в другой части криптографической функции для выбора пути выполнения.

А также...

Выражение будет оцениваться миллионы раз, поэтому, если, к примеру, найдется умное решение, которое использует только 2 оператора вместо 3, это ускорит общее вычисление.

Если это ваша реальная мотивация... тогда мой совет: не беспокойся. Это преждевременная оптимизация. Оставьте это JIT-компилятору.

user3427419 05 сен '15 в 05:13 2015-09-05 05:13 · Answer 3 · 2015-09-05 05:13

Поскольку целью является достижение

if (x == 7)
    result = 1;
else
    result = 0;

в некотором роде алгебраической моды без ветвления,

result = 1 >> (x^7);

Но тогда это не работает, потому что правое смещение маскируется до нескольких бит. Итак, что вы можете сделать, это

result = 1 >> Integer.bitCount(x^7);

но он по-прежнему маскируется для случая -6 (все биты установлены в случае -6 ^ 7), поэтому

int bc = Integer.bitCount(x^7);
return 1 >> (bc | (bc>>1));

Итак, насколько медленнее, чем условная ветвь? Выше решение, использующее bitCount(), для сравнения всего диапазона int range более одного раза,

user    0m5.948s

Используя ветвление, (x == 7? 1: 0),

user    0m2.104s

Так что это не так уж и плохо, учитывая, что вы получаете сравнение с постоянным временем, которое работает для любого значения, 7 является лишь примером. Да, Integer.bitCount() тоже постоянное время.

user780717 12 сен '15 в 21:42 2015-09-12 21:42 · Answer 4 · 2015-09-12 21:42

Воспользовавшись чрезвычайно ограниченным диапазоном x, который находится в [0,15], я предлагаю использовать поиск в регистровой таблице, используя один бит на элемент таблицы. В таблице есть бит i, установленный для тех входов, которые должны выдавать 1, и ноль в противном случае. Это означает, что наша таблица является литеральной константой 2⁷ = 128:

int x,result;
result = (128 >> x) & 1;

user2509848 05 сен '15 в 00:09 2015-09-05 00:09 · Answer 5 · 2015-09-05 00:09

A ternary would be a good option here:

result = x == 7 ? 1 : 0;

This code assigns 1 в result если выражение x == 7 оценивает true, and assigns 0 иначе.

2

Источник

user2509848 05 сен '15 в 00:09