А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 221
Текст из файла (страница 221)
Вот как выглядит запрос после удаления комментария: ЯЕЕЕСТ Ьа1апсе ГНОМ АсссРаса ИНЕНЕ паве = 'СЬаг1ея Шс1сепя' В примере 12.10 "плохие" строки располагаются в двух переменных, которые могут быть переданы между процедурами. Однако в более реалистических случаях такие строки могут быть много раз скопированы или объединены с другими для образования полного запроса. Мы не можем надеяться на обнаружение ошибок, приводящих к уязвимости посредством Я И=ввода, без полного межпроцедурного анализа всей программы в целом. 1080 Глава 12. Межпроцедурный анализ 12.2.6 Переполнение буфера Атака путем переполнения буфера осуществляется путем передачи пользователем специальным образом созданных данных за пределами предназначенного для них буфера и получения посредством этого доступа к управлению программой.
Например, программа на языке программирования С может считывать предоставляемую пользователем строку а и копировать ее в буфер 6 с использованием вызова функции втксру(Ь, з );. Если строка а длиннее буфера 6, то будут изменены значения ячеек памяти, не являющиеся частью буфера о. Это может привести к некорректной работе программы или как минимум к получению неверных результатов, поскольку изменяются используемые программой данные. Что еще хуже — хакер может выбрать строку з так, что она приведет к более серьезным последствиям, чем просто ошибка.
Например, если буфер находится в стеке времени выполнения, то он располагается вблизи адреса возврата из функции. Специально подобранное значение з может переписать адрес возврата и прн выходе из функции управление будет передано в место, выбранное хакером. Если хакер хорошо знает операционную систему и аппаратное обеспечение, то он сможет заставить программу выполнить команду, которая передаст ему управление над машиной.
В некоторых случаях может даже иметься возможность так подменить адрес возврата, что управление будет передано коду, являющемуся частью строки з, позволяя, таким образом, вставить в выполняемый код любую хакерскую подпрограмму. Для предотвращения переполнения буфера для любой операции, которая выполняет запись в массив, должно быть выполнено статическое доказательство невозможности выхода за границы массива либо соответствующая проверка должна выполняться динамически.
Поскольку такая проверка должна вноситься в программы на языке программирования С или С++ вручную, очень легко либо забыть ее внести, либо ошибиться при ее написании. В настоящее время разработаны эвристические инструменты, которые позволяют выполнить проверку наличия как минимум некоторых тестов перед вызовом функции вт.кору. Избежать динамических проверок невозможно, поскольку размер пользовательского ввода не может быть определен статически. Все, чего можно добиться с помощью статического анализа, — убедиться в наличии динамических проверок.
Таким образом, разумная стратегия состоит в том, чтобы заставить компилятор вставлять динамические проверки границ массивов при каждой записи н использовать статический анализ как средство для оптимизации и устранения по возможности как можно большего количества проверок. При этом нет необходимости отлавливать каждое потенциальное нарушение; более того, можно оптимизировать только часто выполняемые области кода. Вставка проверки выхода за границы массива в программу на языке программирования С вЂ” задача нетривиальная, даже если забыть о стоимости таких 1ОВ1 12.3.
Логическое представление потока данных проверок. Указатель может указывать внутрь некоторого массива, причем мы можем не знать размер этого массива. В настоящее время разработаны методы динамического отслеживания размеров буферов, на которые указывает каждый из указателей. Такая информация позволяет компилятору вставить проверки выхода за границы массива для всех обращений. Достаточно интересно, что останавливать про~рамму при обнаружении выхода за границу массива не рекомендуется.
В действительности переполнение буферов встречается на практике, так что, если запретить все переполнения, программа может просто перестать работать. Решение заключается в динамическом изменении размера массива для предотвращения переполнения буфера. Для снижения стоимости динамических проверок выхода за границы массива можно использовать межпроцедурный анализ. Предположим, например, что нас интересует только отлавливание переполнения буфера строками пользовательского ввода. Тогда можно использовать статический анализ для определения того, какие переменные могут хранить содержимое, предоставленное пользователем. Как и в случае Я( Н.-ввода, отслеживание копирований входных данных между процедурами позволяет устранить излишние проверки выхода за границы массива.
12.3 Логическое представление потока данных До этого момента наше представление задач потоков данных и их решений можно было охарактеризовать как представление с использованием теории множеств. Мы представляли информацию в виде массивов и вычисляли интересующие нас результаты с использованием операторов наподобие объединения и пересечения массивов. Например, в задаче достигающих определений в разделе 9.2.4 мы вычисляем множества пч 1В~ и о11т [В~ для базового блока В и описываем их как множества определений. Содержимое блока В мы представляем множествами дел и lпП. Чтобы справиться со сложностями межпроцедурного анализа, требуется более обобщенное н лаконичное представление, основанное на логике. Вместо того чтобы говорить нечто наподобие "определение О входит в пч (В1", для обозначения этого мы используем запись типа 1п (В, Р)1.
Это позволяет нам записать краткие "правила" вывода логических заключений о программе. Кроме того, такие правила можно эффективно реализовать, как обобщение подхода с битовыми векторами для операций над множествами. Наконец, логический подход позволяет комбинировать несколько анализов в один интегрированный алгоритм. Например, в разделе 9.5 мы описали устранение частичной избыточности как последовательность из четырех анализов потоков данных и двух дополнительных промежуточных ша- 1ОВ2 Глава 12. Межпроцедурный анализ гов. В случае логического представления все эти шаги могут быть объединены в один набор логических правил, которые решаются одновременно.
12.3.1 Введение в Оа1а1од Ра!а)оя — это язык, использующий запись наподобие используемой в языке программирования Рго!ой, но с более простой по сравнению с Рго1оя семантикой. Начнем с того, что элементами Ра!а!оя являются атомы вида р1Хз, Хз,..., Х„). Здесь 1. р — прсдикат, символ, который представляет тип инструкции наподобие "определение достигает начала блока"; 2. Хз, Хз,..., Մ— члены, такие как переменные или константы; в качестве аргументов предиката могут выступать простые выражения.' Основной атом (дгоппд а!ош) представляет собой предикат, аргументами которого являются только константы. Каждый основной факт является утверждением о некотором конкретном факте, и его значением является либо истина, либо ложь.
Часто оказывается удобным представлять предикат отношением или таблицей его истинных основных атомов. Каждый основной атом представлен одной строкой, или кори!ежам (!цр!е), отношения. Столбцы отношения называются атрибутами, и каждый кортеж имеет компонент для каждого атрибута. Атрибуты соответствуют компонентам основных атомов, представленных отношением. Любой основной атом в отношении истннен, а основные атомы, не входящие в отношение, ложны. Пример 12.11. Предположим, что преднкат кп (В, Р) означает "определение Р достигает начала базового блока В". Мы можем предположить, что для некоторого графа потока истинными являются предикаты зп (Ьз, 4), зп (Ьз, 4) и ья (Ьз, с1з).
Предположим также, что все остальные зп для данного графа потока ложны. Тогда отношение на рис. !2.12 представляет значение данного предиката для рассматриваемого графа потока. Атрибутами отношения являются В и Р, а тремя кортежами отношения— (Ьз,с!!), (Ьз,4) и (Ьз,т!з).
!э Мы также иногда будем встречаться с атомами, которые представляют собой сравнения переменных и констант. Примерами таких атомов могут служить Х ф У и Х = 10. В этих примерах предикаты представляют собой операторы сравнения, т.е. мы можем рассматривать сравнение Х = 10 как предикат вида Формально такие члены построены из символов функций и сушественно усложнякп Оаш!оа Однако мы будем использовать лишь несколько операторов, таких как сложение и вычитание констант, в контексте, который не усложнит наше рассмотрение. 1ОВЗ 12.3, Логическое представление потока данных Рнс. !2.12. Представление значения нреднката отношением едиаЬ 1Х, 10).
Однако между предикатами сравнения и прочими имеется важное различие. Предикаты сравнения имеют стандартную интерпретацию, в то время как обычные предикаты наподобие 1и означают только то, что определено программой Оа1а!оя (об этом будет сказано ниже). Литерал представляет собой либо атом, либо его отрицание. Отрицание обозначается с использованием слова НОТ перед атомом. Таким образом, 1чОТ 1н(В, Р) является утверждением, что определение не достигает начала базового блока В. 12.3.2 Правила Ва1а10р Правила представляют собой способ выражения логических выводов.
В Па1- а!оя правила служат также для предложения того, каким способом должны быть вычислены истинные факты. Правила имеют вид Н:-В, аВ,а" аВ„ Ниже перечислены компоненты правила. ° Н является атомом, а Вы Вз,..., В„являются литералами — либо атомами, либо их отрицаниями. ° Н вЂ” заголовок правила, а Вы Вз,..., В„образуют его тело. ° Каждый из литералов В, называется также нодцелью (знЬяоа!) правила. Символ ": -" должен читаться как "если". Смысл правила — "заголовок истинен, если истинно тело". Говоря более точно, мы применяем правило к данному множеству основных атомов следующим образом.
Рассмотрим все возможные подстановки констант вместо переменных в правиле. Если подстановка делает каждую подцель тела истинной (т.е. истинны все данные основные атомы, и только они), то можно сделать вывод, что заголовок при такой подстановке констант вместо переменных является истинным фактом. Подстановки, которые не делают истинными все подцели, не несут для нас никакой информации — заголовок может быть, а может и не быть истинным. Программа Вага1од представляет собой набор правил. Такая программа применяется к "данным", т.е. к множеству основных атомов для некоторых предикатов.
Результатом выполнения программы является множество основных атомов, 1084 Глава 12. Межпроцедурный анализ Соглашения Рв1в!о8 В программах Раьз!ой мы будем использовать следующие соглашения. 1. Переменные начинаются с прописной буквы. 2. Все остальные элементы начинаются со строчных букв или иных символов, таких как цифры. Эти элементы включают предикаты и константы, являющиеся аргументами предикатов. полученное путем применения правил до тех пор, пока не будут сделаны все возможные выводы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
