Управляющий граф программы AC, чтобы найти наихудший возможный путь
Существуют ли какие-либо инструменты, библиотеки или интегрированные среды, чтобы получить граф управления потоком программы на Си и найти худший из возможных путей, по которому может идти программа?
Когда я прочитал другие вопросы, связанные с графами потоков управления, я наткнулся на несколько инструментов, которые могут генерировать граф потоков управления. Есть ли способ использовать их, чтобы найти худший из возможных путей?
2 ответа
Если на графике когда-нибудь будут циклы, то нет - нет надежного способа понять это, так как вопрос эквивалентен проблеме остановки. Короткая версия: для программы, заданной произвольной другой программой, невозможно даже определить, вернется ли она когда-либо. Возможно, вы могли бы определить потенциальные бесконечные циклы, но единственный способ приблизиться к определенному - это запустить программу с исчерпывающим набором входных данных.
Вероятно, вас заинтересует наихудшее время выполнения дела, которое, в случае успеха, в каком-то смысле должно было найти ваш худший путь потока управления.
Что касается библиотек для вычисления потоковых графов управления C, см. Нашу поддержку анализа потоков для DMS для C и других языков,