Как теоретическая информатика связана с безопасностью?

Когда я думаю о программном обеспечении, которое небезопасно, я думаю, что оно «слишком полезно» и может быть использовано злоумышленником. Таким образом, обеспечение безопасности программного обеспечения - это процесс, который делает программное обеспечение менее полезным. В теоретической информатике вы не работаете с реальным миром. Так есть ли проблемы безопасности при работе с чистой теорией? Или другая сторона медали, влияет ли теоретическая информатика на реальный мир взлома людей? Если да, то какие темы безопасности считаются теоретическими?

Ваша интуиция о том, что «ненадежность» происходит из-за «слишком полезного» программного обеспечения, в некотором смысле верна. Существует большая и растущая теоретическая литература по «дифференциальной конфиденциальности», которая формализует вашу интуицию. Смотрите, например, здесь: research.microsoft.com/en-us/projects/databaseprivacy/dwork.pdf

Здесь мы считаем входные данные для алгоритма «базой данных», а алгоритм «небезопасен», если он раскрывает слишком много информации о данных какого-либо человека в базе данных. Алгоритм -differentially частный если выход алгоритма не зависит сильно от любого одного входа: в частности, изменение одной записи в базе данных ввода следует изменять только вероятность любого выхода алгоритма самое большее на е ε фактор.$\epsilon$$e^\epsilon$

Конечно, создание частного алгоритма делает его менее полезным: дифференциальный приватный алгоритм создает выходные данные, которые даже не являются функцией входных данных! Но оказывается, что вы можете попытаться тщательно сбалансировать компромисс между конфиденциальностью и полезностью, и можете получить очень частные алгоритмы, которые, тем не менее, очень нетривиально полезны.$0$

Несколькими способами:

• Криптография (чрезвычайно широкое обобщение информационной безопасности, от конфиденциальности до шифрования)
• Формальная проверка кода (см. Также проект seL4 )
• Отказоустойчивость и исправление ошибок
• Теоретические способы предотвращения вредоносных программ ( другое ), включая подписывание кода
• Взломостойкое оборудование
• Точечная обфусация (теоретический подход к информации, теоретически безопасная кодовая обфускация)
• Машинное обучение помогает предотвратить и предупредить попытки взлома в режиме реального времени (например, Active Wardens и Spam Filtering ).
• Гораздо больше

Рассмотрим пример Wired Equivalent Privacy , который на самом деле не таков: из-за смущающего базового теоретического упущения (pdf) WEP можно взломать за считанные минуты.

В «Почему компьютеры небезопасны,» язвительно заметил Брюс Шнайер

Проектирование безопасности включает программирование компьютера сатаны.

И компьютер сатаны сложно проверить.

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

Ю Гу, Эндрю МакКаллум и Дон Таусли. Обнаружение аномалий в сетевом трафике с использованием оценки максимальной энтропии. В IMC '05: Материалы 5-й конференции ACM SIGCOMM по измерениям в Интернете, страницы 1–6, 2005

В отличие от других ответов, это больше похоже на «вещи, о которых мы должны беспокоиться, когда говорим, что что-то« доказуемо безопасно », а не в тех местах, где TCS использовался в безопасности. Таким образом, он решает первый вопрос о проблемах безопасности при работе с теорией.

Как говорят хакеры, теоретические результаты часто касаются реальной безопасности. Такого рода аргументы были сделаны более теоретическими, научными и точными Альфредом Менезесом и Нилом Коблицем в их серии работ « Другой взгляд » (предупреждение: сайт кажется мне немного конфронтационным, но я думаю, что основная идея ставить под сомнение предположения очень важно). Они указывают на недостатки в стандартных допущениях в криптографии, даже в оригинальных работах.

Некоторые примеры (цитируя / перефразируя несколько пунктов с их сайта):

1. Теорема безопасности условна - она ​​предполагает неразрешимость некоторой математической задачи.

2. Часто предположение о неразрешимости делается для сложной и надуманной проблемы: в некоторых случаях эта проблема тривиально эквивалентна проблеме криптоанализа для протокола, безопасность которого «доказана».

3. Иногда в доказательстве имеется большой промежуток герметичности, но параметры все равно рекомендуется, как если бы доказательство было плотным. В таких случаях доказательство обычно дает бесполезную нижнюю границу времени выполнения успешной атаки. Кроме того, асимптотический результат не обязательно обеспечивает какую-либо гарантию безопасности для параметров в диапазоне, используемом на практике.

4. Теорема безопасности использует определенную модель безопасности. Определенные атаки, особенно атаки по побочным каналам, очень трудно смоделировать, а предложенные модели крайне неадекватны.

Доказатели теорем были использованы в некоторой степени для проверки правильности программного обеспечения, оборудования и протоколов. Смотрите, например, здесь или здесь .

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

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

В любом случае, исследовательское сообщество PL очень заинтересовано в безопасности (вы доверяете своему браузеру запускать произвольный иностранный код ?!), и его вопросы приводят ко многим классическим вопросам теории CS.