Программа "лечащая" сама себя

[Amigo]

Тут в голову мысль одна пришла. Только как сформулировать её не знаю...
Но мысль примерно такая: доказать, что каков бы не был алгоритм - всегда
существует по крайней мере одна "поломка" которая самим алгоритмом не может
быть исправлена. Конечно тут все слова крайне не определены, но надеюсь, что мысль в целом понятна.


Сам вопрос родился когда в одной передаче, один английский учёный рассказывал,
что они создают настолько стабильно работающие программы (там задействованны какие то сумашедшие нейросети) , что если удалить даже 80 прочентов кода то программа всё равно
будет работать. Это меня крайне удивило. Потому как программы вылетают даже тогда,
когда вроде как код целый. Так вот, я тогда подумал - может они удалюют не тот участок кода? И где то есть критический участок, удалив который - программа работать не будет?
Так вот: как доказать, что такой участок всегда есть?

Или сформулируем по другому:
1. Доказать, что во всякой программе есть участок кода длиной в 1 бит, "повредив" который
программа перестанет работать, каков бы алгоритм она не осуществляла.
2. Доказать, что во всякой программе есть участок кода определённой длины, "повредив" который программа перестанет работать, каков бы алгоритм она не осуществляла.
3. Доказать, что не возможно создать алгоритмическую схему реализующую
возможность "лечения" любой своей ошибки.


Понимаю, что сумбурно. Но лучше не могу, простите.

P.s.
А может где то есть литература на эту тему? Не подскажите?

[Егор]

Amigo писал(а):

Сам вопрос родился когда в одной передаче, один английский учёный рассказывал, что они создают настолько стабильно работающие программы (там задействованны какие то сумашедшие нейросети) , что если удалить даже 80 прочентов кода то программа всё равно будет работать. Это меня крайне удивило. Потому как программы вылетают даже тогда, когда вроде как код целый. Так вот, я тогда подумал - может они удалюют не тот участок кода?

Согласен с Вашими подозрениями. Думаю, что какие-то "управляющие" фрагменты программы предполагаются неприкосновенными.

Amigo писал(а):

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

Это зависит от способа кодирования (и способа интерпретации) команд. Для любого натурального n можно придумать настолько избыточный способ кодирования команд, что интерпретатор сможет исправлять ошибки длины не более n.

Amigo писал(а):

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

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

[незваный гость]

Егор писал(а):

Думаю, что какие-то "управляющие" фрагменты программы предполагаются неприкосновенными.

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

[PAV]

Но все равно есть некоторая команда, которая выполняется самой первой (если действительно речь идет о линейных программах). Испортить ее - и все полетит в тартарары.

[GinGreen]

Amigo писал(а):

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

Может, учёный имел ввиду, что если 80% нейронов дадут сбой, то программа всеравно будет работать?
Я думаю, что решалась задача шумоустойчивости.

[PAV]

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

Но вообще не стоит обращать особого внимания на подобные громкие и красивые заявления без точных описаний сути достижений и ссылок на результаты.

[Amigo]

незваный гость писал(а):

:evil:

Егор писал(а):

Думаю, что какие-то "управляющие" фрагменты программы предполагаются неприкосновенными.

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

А я чего то не могу себе представить три таких экземпляра. Не поможите?

GinGreen писал(а):

Может, учёный имел ввиду, что если 80% нейронов дадут сбой, то программа всеравно будет работать?
Я думаю, что решалась задача шумоустойчивости.

Я в такие тоности не вникал. Тем более, что передача была года полтора назад по РБК
а я делал, что то на кухне в это время, и мельком смотрел.

PAV писал(а):

Но все равно есть некоторая команда, которая выполняется самой первой (если действительно речь идет о линейных программах). Испортить ее - и все полетит в тартарары.

Это если программа не загружена в опер. память. А если она уже загружена, то так ли уж нужна программе эта своя первая комманда?


Под линейным алгоритмом Вы понимаете: вычислитель который к каждую еденицу времени выполняет лишь одну комманду?


Уточним первоначальную формулировку: вместо алгоритма - как жестко детерминированной последовательности комманд. Будем иметь ввиду некий механический прибор. Ну например
станок какой нибудь. Это прибор обладает тем свойством, что он работает именно так как работает а не как либо по другому. Доказать, что в реальном физическом мире не возможно создать механический прибор способный починить любую свою поломку.

[Zai]

Amigo писал(а):

удалить даже 80 прочентов кода то программа всё равно будет работать

По всей видимости загрузчик сегмента программы в оперативную память проверяет контрольную сумму этого сегмента и если контрольная сумма не совпадает то грузится другой идентичный по функциональному наполнению сегмент. Такую программу действительно нельзя испортить.

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

[незваный гость]

Amigo писал(а):

А я чего то не могу себе представить три таких экземпляра. Не поможите?

Отчего же не помочь хорошему человеку?

Представьте себе: три процессора, общие 3 банка по 1 ХБ памяти . Для процессоров определены «левый» и «правый» «друг». Вся память уложена в адресное пространство каждого из процессоров просто: 0X — свой банк, 1Х — память левого друга, 2Х — память правого друга. (Это легко — с точностью до арбитрирования доступа — делается на схемном уровне.) В каждый банк загружается одна и та же программа. Всё, полетели.

PAV писал(а):

Но все равно есть некоторая команда, которая выполняется самой первой (если действительно речь идет о линейных программах). Испортить ее - и все полетит в тартарары.

Отчасти — смотри ответ выше. От другой части — на самом деле, полная робастность системы обычно практически не интересна. Интересна после некоторой стадии инициализации, после того, как система выдала сигнал готовности. То есть, первая команда не рассматривается как точка уязвимости.

Иначе мы начинаем раскручивать необходимость самолечащего BIOS'а, за ним — микрокода, и т.п. На практике — не интересно: если мы не можем включить прибор/систему, пусть катится в тартарары: может быть неисправно железо, и что тогда? Лучше уж и не пытаться пользоваться, искать какой-либо вариант выживания без него.

[offtop] Дней минувших анекдот: показывал я заказчику систему в DOS, написанную на Clipper'е. Уж не знаю почему, но он решил придраться — смотрите, говорит, на Ctrl-D система вылетает. Действительно, по Ctrl-D система входит в отладчик (из которого легко выйти). Объясняем. Нет, говорит, убрать. Мы спрашиваем: а Ctrl-Alt-Del? Шумит: тоже убрать! Мы (уже иронически): а как насчет Reset? (Это уже не так-то просто: перехватить Reset в принципе можно, при этом сохраняется состояние памяти, но теряется (по-моему, годы прошли) указатель стека. Так что, попотеть пришлось бы изрядно). Заказчик (облизываясь): убрать! Мы: а если Вы вилку из розетки выдерните? Тут до заказчика начало доходить... Договорились, как же не договорится: ему нужны программы, нам — деньги.[/offtop]

~~~~~~

Немного наблюдений: как правило, ремонтируют данные. Т.е., каким-либо образом находят ошибки в данных и их исправляют. Программа, с точки зрения компа — это разновидность данных. Этой разновидности, в последнее время, уделяется всё больше внимания. Это и управление исполнением данных (и на процессорном уровне, и на уровне OS), и верификация байт-кода (по меньшей мере, популяризованное Java). Это первое, что делает любой компилятор: рассматривает текст (данные) как исполняемую программу. И 50+ лет назад никто не рассматривал самомодифицирующуюся программу как нечто экзотическое: System/360 имела поддержку самомодификации в архитектуре процессора. Времена меняются, и, тем не менее, самолечащая программа занимает свое место в одном ряду с программой, печатающей свой текст (упражнение для первокурсников), вирусами (программами, воспроизводящими свой код в других программах), червями (программами, передающими свой код по сети).

[PAV]

Все верно, но это не совсем то, о чем спрашивал автор темы. Речь ведь шла о программе, которая лечит сама себя. А во всех обсуждениях лечением и восстановлением занимается некоторый загрузчик, в котором искажений не предполагается. Это все понятно, что таких систем можно сделать много. В качестве аппаратного примера можно еще привести отказоустойчивые дисковые массивы, в которых выход из строя любого одного жесткого диска не ведет к потере данных. Да и коды с исправлением ошибок - это то же самое.

[незваный гость]

PAV писал(а):

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

Ну почему же? В моем варианте (три процессора) как раз и предполагалось, что программа загружается в эту память, включая загрузчик/монитор. В частности, поэтому и понадобились хитрости с адресацией: как правило, обработчики/вектора прерываний находятся по фиксированным адресам. В этом случае, «загрузчик» является частью программы, причем тоже самовостанавливаемой.

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

[PAV]

PAV писал(а):

если действительно речь идет о линейных программах

Если три процессора - тогда конечно, я согласен.

[Amigo]

незваный гость писал(а):

:evil:

Amigo писал(а):

А я чего то не могу себе представить три таких экземпляра. Не поможите?

Представьте себе: три процессора, общие 3 банка по 1 ХБ памяти . Для процессоров определены «левый» и «правый» «друг». Вся память уложена в адресное пространство каждого из процессоров просто: 0X — свой банк, 1Х — память левого друга, 2Х — память правого друга. (Это легко — с точностью до арбитрирования доступа — делается на схемном уровне.) В каждый банк загружается одна и та же программа. Всё, полетели.

Нет, на таком уровне я понять не могу. Особенно не понятно, что будет делать эта программа, помимо того что бы просто существовать?
Вот такой вопрос: можно ли создать самоизлечивающуюся программу, которая бы
помимо прочего умела вычислять определитель матрицы?
И почему Вы изначально предложили схему именно с тремя процессорами? Что нельзя было
с двумя или с одним?

[незваный гость]

Amigo писал(а):

Особенно не понятно, что будет делать эта программа, помимо того что бы просто существовать?

Что нам нужно. Просто, среди прочего, она может отслеживать свое состояние здоровья.

Amigo писал(а):

Вот такой вопрос: можно ли создать самоизлечивающуюся программу, которая бы
помимо прочего умела вычислять определитель матрицы?

Конечно, можно.

Amigo писал(а):

И почему Вы изначально предложили схему именно с тремя процессорами? Что нельзя было с двумя или с одним?

Мне нужно было уйти от единственной точки уязвимости. В некотором смысле, три — первое число, пришедшее на ум. Может быть, можно и с двумя.

~~~

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

Другой аспект, требующий формализации — это что такое «болезнь» программы, требующая лечения.

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

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