Рандомізація функції

В інформатиці, функція рандомізації або рандомізація функції — це алгоритм або процедура, яка реалізує функцію, випадково обираючи між двома конкретними наборами, придатними для використання в увипадковленому алгоритмі.

Функція рандомізації пов'язана з генератором випадкових чисел і геш-функціями, але є декілька відмінностей у вимогах і використанні, і часто потрібні конкретні алгоритми.

Функція рандомізації використовується, щоб включити алгоритми, які мають хорошу очікувану продуктивність випадкових входів, в алгоритми, які мають таку ж продуктивність для будь-якого входу.

Залежність від методів генерації випадкових чисел

Якість та властивості рандомізованої функції безпосередньо залежать від обраного методу генерації випадкових значень.

Використання псевдовипадкових чисел

У випадках, коли рандомізація функції необхідна для комп'ютерного моделювання (наприклад, у методі Монте-Карло) або в рандомізованих алгоритмах (таких як Quicksort), зазвичай використовують генератори псевдовипадкових чисел (ГПВЧ).

Ключовою перевагою цього підходу є висока швидкість генерації, що дозволяє уникнути суттєвого уповільнення виконання основної функції. Важливою особливістю ГПВЧ є детермінованість: результат роботи функції можна точно відтворити, якщо відоме початкове значення (англ. seed). Ця властивість є критичною для налагодження коду та верифікації наукових експериментів.

Як стандарт для подібних задач часто застосовують алгоритм Вихор Мерсенна, який забезпечує довгий період повторюваності чисел та високу статистичну якість.

Використання істинно випадкових чисел

Для задач інформаційної безпеки, таких як рандомізація адресного простору, генерація криптографічних ключів або створення «солі» для хеш-функцій, рандомізація повинна базуватися на апаратних генераторах випадкових чисел (TRNG).

Джерелом ентропії для таких генераторів слугують фізичні стохастичні процеси: тепловий шум, фотоелектричний ефект або квантові явища. Використання істинно випадкових чисел робить поведінку рандомізованої функції непередбачуваною для зловмисника, навіть за умови повного знання алгоритму роботи системи.

Приклади використання

Фаззінг-тестування

Рандомізація вхідних даних функції є основою методології тестування програмного забезпечення, відомої як Фаззінг (англ. Fuzzing). Спеціалізоване ПЗ (фаззери) генерує значні обсяги випадкових, напіввипадкових або мутованих даних, які подаються на вхід цільової функції.

Метою такої рандомізації є перевірка стабільності та коректності роботи функції при обробці непередбачуваних, граничних або некоректних даних. Це дозволяє виявити приховані вразливості, витоки пам'яті, помилки обробки виключень та причини аварійних зупинок програми.

Рандомізоване швидке сортування

Класичним прикладом використання рандомізації є алгоритм швидкого сортування (англ. QuickSort). У цьому алгоритмі випадковість використовується для підвищення ефективності та уникнення найгірших сценаріїв виконання.

Багато детермінованих версій QuickSort мають часову складність ${\displaystyle O(n^{2})}$ при обробці n чисел для певних вироджених класів вхідних даних (наприклад, якщо вхідний масив вже є відсортованим або відсортованим у зворотному порядку). Така поведінка зумовлена фіксованим протоколом вибору опорних елементів (наприклад, коли опорним завжди обирається перший або останній елемент масиву).

Впровадження рандомізації у функцію вибору опорного елемента (коли він обирається рівномірно випадковим чином із доступного підмасиву) кардинально змінює характеристики алгоритму. У такому випадку доведено, що з високою ймовірністю алгоритм завершує роботу за час ${\displaystyle O(n\log n)}$, незалежно від характеристик або впорядкованості вхідних даних

Див. також

• Генератор випадкових чисел
• Рандомізований алгоритм
• Метод Монте-Карло

Джерела

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (вид. 3rd). MIT Press. с. 170—190. ISBN 978-0-262-03384-8.</ref>
• Matsumoto, Makoto; Nishimura, Takuji (1998). Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation. 8 (1): 3—30. doi:10.1145/272991.272995.</ref>
• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (вид. 3rd). Addison-Wesley. ISBN 978-0-201-89684-8.</ref>
• Katz, Jonathan; Lindell, Yehuda (2014). Introduction to Modern Cryptography. CRC Press. ISBN 978-1-4665-7026-9.</ref>
• D. Eastlake 3rd (June 2005). RFC 4086 - Randomness Requirements for Security. IETF.</ref>
• Shacham, H. (2004). On the effectiveness of address-space randomization. Proceedings of the 11th ACM conference on Computer and communications security (CCS '04). ACM. с. 298—307. doi:10.1145/1030083.1030124.</ref>

• Miller, Barton P.; Fredriksen, Louis; So, Bryan (1990). An Empirical Study of the Reliability of UNIX Utilities. Communications of the ACM. 33 (12): 32—44. doi:10.1145/96267.96279.</ref>