Аварийная ошибка программы

Question

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

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

Сотрудник сказал, что то, что я пытаюсь сделать, принципиально невозможно. Для меня это немного экстремально. Учитывая закономерность развития технологии Мура, вычислительная мощность, которая вне досягаемости, в конечном итоге станет реальностью - в конечном итоге. Казалось бы, немного преувеличением предположить, что такая вещь останется навсегда невозможно.

Почему это не может быть сделано?

Answer 1

Вот программа:

accept integer i greater than 2 
loop with k from 2 to 2*i 
    is k prime? 
    is 2*i-k prime? 
     exit safely 
end loop 
do something nasty. 

Если проследить входные данные, которые вызывают эту программу, чтобы сделать что-то противное, вы решили Goldbach's conjecture. Вы можете собрать медаль Филдса вместе с Нобелевской премией.

Это говорит о том, что некоторые программы не делают ничего противного. Я и другие работают над a framework in which you can do just that, using various techniques. Некоторые примеры:

This compression library could exhibit a memory error with input size 20, output size 40, but now it won't.

This binary search could fail, but now it won't.

Answer 2

Это один из святых Grails вычислительной техники и математики, известный как Entscheidungsproblem. Вы не собираетесь это решать. Самые яркие умы в обоих полях потратили на это много лет и доказали, что это невозможно решить. Когда nbt и Pascal Cuoq сказали, что вы выиграете Нобель и Филдс за это, они действительно это имели в виду.

Answer 3

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

Да, это возможно, несмотря на то, что говорят люди теории. Есть несколько компаний, которые продают продукты, которые делают именно то, что вы описываете, среди которых Vericode, Coverity, Fortify, Klocwork и Grammatech.

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

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

Редактировать, для комментариев Алекса
Я возьму математику ярлык, и сказать, что так как исходный вопрос: «Можно ли» существование нескольких жизнеспособных коммерческих продуктов доказывает, что ответ «да». Экономические зависимости, которые могут быть созданы с помощью коммерческого программного обеспечения, выходят за рамки первоначального вопроса.