Путь взрыва

В информатике масштабируемость взрыв путей является фундаментальной проблемой, которая ограничивает и /или полноту некоторых видов анализа программ , включая фаззинг , символьное выполнение и статический анализ с учетом пути . Взрыв путей относится к тому факту, что количество путей потока управления в программе растет экспоненциально («взрывается») с увеличением размера программы и может даже быть бесконечным в случае программ с неограниченными итерациями цикла. ^[1]^[2] Следовательно, любой анализ программы, который пытается исследовать пути потока управления через программу, либо будет иметь экспоненциальное время выполнения по длине программы (или, возможно, даже не сможет завершиться на определенных входных данных), либо будет вынужден выбирать анализ только подмножества все возможные пути. Когда анализ исследует только подмножество всех путей, решение о том, какие пути анализировать, часто принимается эвристически . ^[3]

Ссылки

^ Ананд, Сасват; Патрис Годфруа; Николай Тильманн (2008). «Композиционно-символическое исполнение, ориентированное на спрос». Инструменты и алгоритмы построения и анализа систем . Конспекты лекций по информатике. Том. 4963. стр. 367–381. дои : 10.1007/978-3-540-78800-3_28 . ISBN 978-3-540-78799-0 .
^ Бунстоппель, Питер; Кадар, Кристиан; Энглер, Доусон (2008). Рамакришнан, ЧР; Рехоф, Якоб (ред.). «RWset: Взрыв пути атаки при генерации тестов на основе ограничений» . Инструменты и алгоритмы построения и анализа систем . Берлин, Гейдельберг: Springer: 351–366. дои : 10.1007/978-3-540-78800-3_27 . ISBN 978-3-540-78800-3 . «Количество различных путей увеличивается экспоненциально с количеством пройденных условных операторов. Во всех программах, кроме самых маленьких, это обычно приводит к практически неисчерпаемому набору путей для исследования».
^ Ма, Кин-Кенг; Ху Йит Пханг; Джеффри С. Фостер; Майкл Хикс (2011). «Направленная символическая казнь» . Материалы 18-й Международной конференции по статистическому анализу . стр. 95–111. ISBN 9783642237010 . Проверено 3 апреля 2013 г.

[1] Ананд, Сасват; Патрис Годфруа; Николай Тильманн (2008). «Композиционно-символическое исполнение, ориентированное на спрос». Инструменты и алгоритмы построения и анализа систем . Конспекты лекций по информатике. Том. 4963. стр. 367–381. дои : 10.1007/978-3-540-78800-3_28 . ISBN 978-3-540-78799-0 .

[2] Бунстоппель, Питер; Кадар, Кристиан; Энглер, Доусон (2008). Рамакришнан, ЧР; Рехоф, Якоб (ред.). «RWset: Взрыв пути атаки при генерации тестов на основе ограничений» . Инструменты и алгоритмы построения и анализа систем . Берлин, Гейдельберг: Springer: 351–366. дои : 10.1007/978-3-540-78800-3_27 . ISBN 978-3-540-78800-3 . «Количество различных путей увеличивается экспоненциально с количеством пройденных условных операторов. Во всех программах, кроме самых маленьких, это обычно приводит к практически неисчерпаемому набору путей для исследования».

[3] Ма, Кин-Кенг; Ху Йит Пханг; Джеффри С. Фостер; Майкл Хикс (2011). «Направленная символическая казнь» . Материалы 18-й Международной конференции по статистическому анализу . стр. 95–111. ISBN 9783642237010 . Проверено 3 апреля 2013 г.

[1]

[2]

[3]