4551
правка
Анализ неуспешных обращений к кэшу: различия между версиями
Материал из WEGA
Анализ неуспешных обращений к кэшу (посмотреть исходный код)
Версия от 23:16, 7 августа 2022
, 7 августа 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 55: | Строка 55: | ||
где <math>\alpha = \alpha(a) = a / (a!)^{1 / a}, P_{tail}(n, p, a) = \sum_{i \ge a} \binom{n}{i} p^i (1 - p)^{n - i}</math> – ''кумулятивная биномиальная вероятность'', а <math>\beta := 1 + \alpha(\left \lceil ax \right \rceil)</math>, где <math>x = x(a) = inf \{ 0 < z < 1 : z + z / \alpha (\left \lceil az \right \rceil) = 1 \}</math>. | '''где <math>\alpha = \alpha(a) = a / (a!)^{1 / a}, P_{tail}(n, p, a) = \sum_{i \ge a} \binom{n}{i} p^i (1 - p)^{n - i}</math> – ''кумулятивная биномиальная вероятность'', а <math>\beta := 1 + \alpha(\left \lceil ax \right \rceil)</math>, где <math>x = x(a) = inf \{ 0 < z < 1 : z + z / \alpha (\left \lceil az \right \rceil) = 1 \}</math>.''' | ||
Здесь 1 < | Здесь <math>1 \le \alpha < e</math> и <math>\beta(1) = 2, \beta(\infty) = 1 + e \approx 3.71</math>. Этот анализ предполагает, что нарушитель (соперник) планирует доступ к последовательностям. Для нижней границы соперник первоначально продвигает последовательность <math>s_i</math> для i = 1, ..., k на </math>X_i</math> элементов, где <math>X_i</math> выбираются равномерно и независимо из {0, M - 1}. Затем соперник обращается к последовательностям в порядке круговой очереди. | ||
Параметр k в верхней границе учитывает возможный дополнительный блок, обращение к которому может выполняться из-за рандомизации начальных адресов. Член -kM в нижней границе учитывает тот факт, что неудачные обращения к кэшу не могут быть подсчитаны, когда противник первоначально перебирает последовательности. | Параметр k в верхней границе учитывает возможный дополнительный блок, обращение к которому может выполняться из-за рандомизации начальных адресов. Член -kM в нижней границе учитывает тот факт, что неудачные обращения к кэшу не могут быть подсчитаны, когда противник первоначально перебирает последовательности. | ||
Границы имеют вид pN + c, где c не зависит от N, а p называется вероятностью неудачи при обращении к кэшу. Положим r = k/m (отношение между количеством последовательностей и количеством блоков кэша), тогда границы для вероятности неудачи при обращении к кэшу в Теореме 1 приобретают следующий вид [3]: | |||
Границы имеют вид pN + c, где c не зависит от N, а p называется ''вероятностью неудачи при обращении к кэшу''. Положим r = k/m (отношение между количеством последовательностей и количеством блоков кэша), тогда границы для вероятности неудачи при обращении к кэшу в Теореме 1 приобретают следующий вид [3]: | |||
