Здравствуйте, Shmj, Вы писали:

S>Но ведь мир компьютерный мы создали сами, верно? По идее могли предусмотреть чтобы в нем этой "чумы", с которой нужно постоянно бороться, не было? Но почему оно таки само все возникло?

Вопрос поставлен не вполне корректно. Оно не возникало (тем более, само), оно там изначально существовало и иначе даже быть не могло. По той же причине, по которой существуют алгоритмически-неразрешимые задачи: из-за фундаментальных ограничений и особенностей формальных вычислительных систем, безотносительно их конкретных физических воплощений. Попробую объяснить, почему так.

Какой минимум функциональных возможностей должен присутствовать в вычислительной системе, чтобы она была полной по Тьюрингу? Например, такой:

1. наличие памяти с произвольным доступом (произвольным -- осуществляемым в любую ячейку за конечное количество шагов без потери значений в каких-либо ячейках), желательно бесконечной ;
2. возможность чтения / записи в эту память;
3. возможность реализации циклов, инварианты которых могут зависеть от значений конкретных ячеек памяти.

Всё. Т.е. возможности инкремента/декремента по текущему указателю, инкремента/декремента значения самого указателя и банального while от значения по текущему указателю (это брейнфак, если кто не узнал) -- уже достаточно для программирования машины Тьюринга (на самом деле, действительно обязательных операций ещё меньше, но сейчас не об этом). С оговоркой о конечности памяти в реальной системе, конечно.

Однако, есть и четвёртая "контрольная" фича, присутствие которой и доказывает полноту по Тьюрингу любой системы с реализованными 1-3 или их функциональными аналогами:

4. самоприменимость.

Это значит, что полная по Тьюрингу вычислительная система должна уметь выполнять саму себя (иными словами, должна позволять реализовать универсальную вычислительную функцию aka универсальный вычислитель). Ну, то есть, к примеру, тьюринг-полный язык должен позволять запилить на самом себе свой собственный интерпретатор. Однако же полнота по Тьюрингу даром не даётся и именно это свойство также и делает неразрешимыми проблемы остановки, анализа самоприменимости и прочие частные случаи теоремы Райса

Автор: kochetkov.vladimir
Дата: 19.04.17

.

Теорема Райса является прямым следствием другой замечательной теоремы -- Клини, о неподвижной точке, утверждающей, что для любой универсальной вычислительной функции f(x) найдётся такая функция x, при которой f(x) будет равно x. Из чего следует, что для любого универсального вычислителя можно построить такую программу, которая будет знать свой собственный код. Благодаря чему и является возможным существование квайнов, BTW. Но, раз программа знает свой код, значит она может его и а) модифицировать, б) записывать в память? Запомним этот факт.

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

Что мешает в такой реализации одной программе перезаписать код другой? Ровным счётом ничего. Что мешает одной программе дописать в другую свой собственный код, чтобы он выполнялся при старте "заражённой" программы? Тоже ничего. По крайней мере, в наивной реализации вычислителя.

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

P.S.

Да, есть возможность реализовать в универсальном вычислителе механизм защиты адресных пространств и рубить все программы, посягающие на чужую территорию. Именно так и поступают в современных системах т.н. принстонской архитектуры, используемой чуть менее, чем повсеместно. А есть возможность помещать код программ в физически выделенную память, писать что-либо в которую интерпретируемые программы не смогут. Это путь т.н. гарвардской архитектуры, используемой в настоящее время преимущественно в микроконтроллерных системах. Однако и в том, и в другом случае, таки возможно существование разделяемой памяти, через которую программы могут влиять друг на друга, в том числе описанным образом. Это -- внешняя память, из которой код программ загружается в адресное пространство и в которую программы (как правило) могут записывать результаты своей работы. Можно реализовать механизмы защиты и этого типа памяти, запрещая программам писать туда, откуда могут загружаться другие программы, например. Собственно, всевозможные штатные политики разграничения доступа, а также SELinux/AppArmor в Linux и MIC в Windows как раз и призваны решать в т.ч. эту задачу. Принципиальная способность программ к саморазмножению в этом случае, как и в случае с защитой памяти, целиком зависит от корректности реализации защитных механизмов и их конфигурации. То есть на практике мы имеет здесь ситуацию гонки щита и меча.

И всё было бы здорово (на самом деле), если бы не один нюанс: универсальный вычислитель -- это не обязательно CPU, виртуализирующий его гипервизор и т.п. Это абсолютно любой код, который может интерпретировать любой другой код. Небольшая задачка, напоследок. Несложно представить себе, как CPU выполняет код ОС, загружающий и запускающий процесс веб-сервера. Этот процесс, в результате обработки каждого очередного HTTP-запроса, загружает с диска некоторый PHP-код (не к ночи будет упомянут) и запускает в отдельном потоке интерпретатор, выполняющий этот код. По ходу выполнения PHP-кода, из данных HTTP-запроса формируется SQL-запрос, который из PHP-кода отправляется в DBMS. DBMS интерпретирует этот запрос и возвращает полученные в результате данные обратно PHP-коду. PHP-код записывает полученные данные на диск под именем, которое содержалось в этих же данных от DBMS.

Атакующий отравляет HTTP-запрос, данные которого сформированы таким образом, что после выполнения SQL-кода DBMS вернёт в ответ злонамеренный PHP-код, который будет записан штатным PHP-кодом под именем index.php в корне веб-сайта. И который в дальнейшем, при каждом запросе к этой странице будет заражать собой все доступные ему на диске php-файлы, а также запускать в отдельном потоке процесс сканирования других веб-серверов на предмет наличия в них известных уязвимостей, которые бы позволили внедрить в их веб-сайты код этого зловреда. Собственно, примерно так и работает современная веб-малварь.

Сосбственно сама задачка: сколько раз в описанном выше сценарии произошло конвертирование вида "данные <-> код" и как от этого спасли рассмотренные выше защитные механизмы?

Здравствуйте, Shmj, Вы писали:

S>Но ведь мир компьютерный мы создали сами, верно? По идее могли предусмотреть чтобы в нем этой "чумы", с которой нужно постоянно бороться, не было? Но почему оно таки само все возникло?

Вопрос поставлен не вполне корректно. Оно не возникало (тем более, само), оно там изначально существовало и иначе даже быть не могло. По той же причине, по которой существуют алгоритмически-неразрешимые задачи: из-за фундаментальных ограничений и особенностей формальных вычислительных систем, безотносительно их конкретных физических воплощений. Попробую объяснить, почему так.

Какой минимум функциональных возможностей должен присутствовать в вычислительной системе, чтобы она была полной по Тьюрингу? Например, такой:

1. наличие памяти с произвольным доступом (произвольным -- осуществляемым в любую ячейку за конечное количество шагов без потери значений в каких-либо ячейках), желательно бесконечной ;
2. возможность чтения / записи в эту память;
3. возможность реализации циклов, инварианты которых могут зависеть от значений конкретных ячеек памяти.

Всё. Т.е. возможности инкремента/декремента по текущему указателю, инкремента/декремента значения самого указателя и банального while от значения по текущему указателю (это брейнфак, если кто не узнал) -- уже достаточно для программирования машины Тьюринга (на самом деле, действительно обязательных операций ещё меньше, но сейчас не об этом). С оговоркой о конечности памяти в реальной системе, конечно.

Однако, есть и четвёртая "контрольная" фича, присутствие которой и доказывает полноту по Тьюрингу любой системы с реализованными 1-3 или их функциональными аналогами:

4. самоприменимость.

Это значит, что полная по Тьюрингу вычислительная система должна уметь выполнять саму себя (иными словами, должна позволять реализовать универсальную вычислительную функцию aka универсальный вычислитель). Ну, то есть, к примеру, тьюринг-полный язык должен позволять запилить на самом себе свой собственный интерпретатор. Однако же полнота по Тьюрингу даром не даётся и именно это свойство также и делает неразрешимыми проблемы остановки, анализа самоприменимости и прочие частные случаи теоремы Райса

Автор: kochetkov.vladimir
Дата: 19.04.17

.

Теорема Райса является прямым следствием другой замечательной теоремы -- Клини, о неподвижной точке, утверждающей, что для любой универсальной вычислительной функции f(x) найдётся такая функция x, при которой f(x) будет равно x. Из чего следует, что для любого универсального вычислителя можно построить такую программу, которая будет знать свой собственный код. Благодаря чему и является возможным существование квайнов, BTW. Но, раз программа знает свой код, значит она может его и а) модифицировать, б) записывать в память? Запомним этот факт.

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

Что мешает в такой реализации одной программе перезаписать код другой? Ровным счётом ничего. Что мешает одной программе дописать в другую свой собственный код, чтобы он выполнялся при старте "заражённой" программы? Тоже ничего. По крайней мере, в наивной реализации вычислителя.

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

P.S.

Да, есть возможность реализовать в универсальном вычислителе механизм защиты адресных пространств и рубить все программы, посягающие на чужую территорию. Именно так и поступают в современных системах т.н. принстонской архитектуры, используемой чуть менее, чем повсеместно. А есть возможность помещать код программ в физически выделенную память, писать что-либо в которую интерпретируемые программы не смогут. Это путь т.н. гарвардской архитектуры, используемой в настоящее время преимущественно в микроконтроллерных системах. Однако и в том, и в другом случае, таки возможно существование разделяемой памяти, через которую программы могут влиять друг на друга, в том числе описанным образом. Это -- внешняя память, из которой код программ загружается в адресное пространство и в которую программы (как правило) могут записывать результаты своей работы. Можно реализовать механизмы защиты и этого типа памяти, запрещая программам писать туда, откуда могут загружаться другие программы, например. Собственно, всевозможные штатные политики разграничения доступа, а также SELinux/AppArmor в Linux и MIC в Windows как раз и призваны решать в т.ч. эту задачу. Принципиальная способность программ к саморазмножению в этом случае, как и в случае с защитой памяти, целиком зависит от корректности реализации защитных механизмов и их конфигурации. То есть на практике мы имеет здесь ситуацию гонки щита и меча.

И всё было бы здорово (на самом деле), если бы не один нюанс: универсальный вычислитель -- это не обязательно CPU, виртуализирующий его гипервизор и т.п. Это абсолютно любой код, который может интерпретировать любой другой код. Небольшая задачка, напоследок. Несложно представить себе, как CPU выполняет код ОС, загружающий и запускающий процесс веб-сервера. Этот процесс, в результате обработки каждого очередного HTTP-запроса, загружает с диска некоторый PHP-код (не к ночи будет упомянут) и запускает в отдельном потоке интерпретатор, выполняющий этот код. По ходу выполнения PHP-кода, из данных HTTP-запроса формируется SQL-запрос, который из PHP-кода отправляется в DBMS. DBMS интерпретирует этот запрос и возвращает полученные в результате данные обратно PHP-коду. PHP-код записывает полученные данные на диск под именем, которое содержалось в этих же данных от DBMS.

Атакующий отравляет HTTP-запрос, данные которого сформированы таким образом, что после выполнения SQL-кода DBMS вернёт в ответ злонамеренный PHP-код, который будет записан штатным PHP-кодом под именем index.php в корне веб-сайта. И который в дальнейшем, при каждом запросе к этой странице будет заражать собой все доступные ему на диске php-файлы, а также запускать в отдельном потоке процесс сканирования других веб-серверов на предмет наличия в них известных уязвимостей, которые бы позволили внедрить в их веб-сайты код этого зловреда. Собственно, примерно так и работает современная веб-малварь.

А теперь, сама задачка: сколько раз в описанном выше сценарии произошло конвертирование вида "данные <-> код" и как от этого спасли рассмотренные выше защитные механизмы?