Измерение энтропии / обратимости выражения - PullRequest
Новая
       5

Измерение энтропии / обратимости выражения

0 голосов
/ 15 мая 2018

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

Iя пытаюсь измерить «энтропию» или «обратимость» выражения (закодировано в LLVM-IR , но это не имеет значения).Это немного расплывчато, но в основном речь идет о том, сколько информации я могу передать через функцию и выйти наружу.Чтобы попытаться быть более точным, если бы я выдвигал истинные случайные значения в качестве входных данных, насколько близко к истинному случайному значению я получал бы в качестве выходных.и общая выходная битовая ширина, и принять минимальную битовую ширину.Еще более жесткая верхняя граница состоит в прохождении минимального среза (в общей битовой ширине) по графику потока данных.Но мне интересно, есть ли общий способ приблизить это число еще лучше.Может быть, обобщенная форма анализа известных битов?

Например: 

; entropy = 64bit (fully reversible)
define i64 @test_a(i32 %x, i32 %y) {
    %x0 = zext i32 %x to i64
    %y0 = zext i32 %y to i64
    %z0 = shl i64 %x, 32
    %z = or i64 %z0, %y0
    ret i64 %z
}

; entropy < 64bit (it is not possible to distinguish permutation of the arguments,
;                  nor their respective prime decomposition)
define i64 @test_b(i32 %x, i32 %y) {
    %x0 = sext i32 %x to i64
    %y0 = sext i32 %y to i64
    %z = mult i64 %x0, %y0
    ret i64 %z
}

; entropy = 32bit (min-cut is on %z0 and is 32bit, the LSB of %z is %x xor %y)
define i64 @test_c(i32 %x, i32 %y) {
    %z0 = xor i32 %x, i32 %y
    %z1 = sext i32 %z0 to i64
    %z2 = shl i64 %z1, 32
    %z = xor i64 %z2, %z1
    ret i64 %z
}

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

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

...