А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 232
Текст из файла (страница 232)
Резюме к главе 12 + Построение графа вызовов. Поскольку в 3ача имеются виртуальные методы, межпроцедурный анализ требует, в первую очередь, ограничиться процедурами, которые могут быть вызваны в данной точке вызова. Главным способом поиска границ того, что и где может быть вызвано, является анализ типа объектов и использование того факта, что фактический метод, на который ссылается вызов виртуального метода, должен принадлежать соответствующему классу. + Контекстно-чувствительный аналш.
В случае рекурсивньсх процедур мы должны уплотнить информацию, содержащуюся в строках вызова, в конечное количество контекстов. Эффективный способ добиться этого — опустить из строки вызова все точки вызова, где процедура вызывает другую процедуру (возможно, саму себя), взаимно рекурсивную с вызывающей. Используя такое представление, можно модифицировать правила внутри- процедурного анализа указателей так, чтобы контекст участвовал в предикатах.
Этот подход имитирует анализ на основе клонирования. + Диаграммьс бинарного выбора. ВОР является компактным представлением булевых функций ориентированным ациклическим графом с корнем. Внутренние узлы ориентированного ациклического графа соответствуют булевым переменным и имеют по два дочерних узла — нижний (представляющий значение 0) и верхний (представляющий 1). Имеется также два листа с метками 0 и 1. Набор значений переменных делает представляемую функцию истинной тогда и только тогда, когда путь от корня, на котором мы переходим к нижнему дочернему узлу при равенстве переменной О, и к верхнему — при 1, приводит нас в лист 1.
+ ВРР и отссоисения. ВРР может служить компактным представлением одного из предикатов Ра1а!оя-программы. Константы кодируются наборами значений булевых переменных, а функция, представляемая ВРР, истинна тогда и только тогда, когда булевы переменные представляют истинный факт для данного предиката.
+ Реалшация анализа потока Данных с использованием ВРР. Любой анализ потока данных, который может быть выражен Раса!од-правилами, может быть реализован при помощи манипуляций с диаграммами бинарного выбора, представляющими предикаты, включенные в эти правила. Зачастую такое представление приводит к более эффективной реализации анализа потока данных, чем любые другие подходы. 1128 Глава 12. Межпроцедурный анализ 12.9 Список литературы к главе 12 Некоторые базовые концепции межпроцедурного анализа можно найти в [1, 6, 7 и 2!].
Каллагэн (СайаЬап) и другие [11] описывают межпроцедурный алгоритм распространения констант. Стинсгард (Б!еепвйаап1) [22] опубликовал первый масштабируемый анализ псевдонимов указателей, являющийся контекстно-нечувствительным, чувствительным к потоку и основанным на эквивалентности. Контекстно-нечувствительная версия основанного на включении анализа целей указателей была разработана Андерсеном (Апдегвеп) [2]. Позже Хайнце (Не!п1х) и Тардью (Тагйеи) [15] описали эффективный алгоритм этою анализа.
Фяндрих (РаЬпс1псЬ), Рехоф (КеЬо1) и Дас (Паз) [14] представили контекстно-чувствительный, нечувствительный к потоку, основанный на эквивалентности анализ, масштабируемый до больших программ наподобие асс. Среди попыток создать контекстно-чувствительный анализ целей указателей на основе включения следует отметить работу Эмами (Ешапн), Гия (ОЬ!уа) и Хендрена (Непдгеп) [13], разработавших основанный на клонировании и включении контекстно-чувствительный, чувствительный к потоку алгоритм анализа целей указателей. Диаграммы бинарного выбора впервые появились в работе Брянта (Вгуапг) [9]. Впервые они были применены для анализа потока данных Берндлом (Вегпд!) с коллегами в работе [4].
О применении В(111 к нечувствительному анализу указателей сообщили Жу (г.Ьп) [25], Берндл (Вепкй) и другие [8]. Вэли (%Ьа1еу) и Лам (1.аш) [24] описали первый контекстно-чувствительный, нечувствительный к потоку, основанный на включении алгоритм, который, как было показано, применим к реальным приложениям. В статье описывается инструмент под названием ЪсЫЬсЫЬ, который автоматически преобразует анализ, описанный 1)а1а!о8-программой, в ВО!3-код. Объектная чувствительность введена Миланова (Мйапоча), Рунтевом (Коппгеч) и Райдером (Крег) [18].
Рассмотрение 13а1а!ой можно найти в работе Ульмана (1Л!шап) и Видома (%н!ош) [23]. Кроме того, в работе Лама (Еаш) с коллегами [16] описывается связь анализа потока данных с 1)а!а!ой. Инструментарий проверки кода Ме!а! описан Энглером (Еп81ег) и другими [12], а программа проверки РКЕбх разработана Бушем (ВпвЬ), Пинкусом (Р!исав) и Силаффом (Б!е1ай) [1О]. Болл (Вай) и Раджамани (Ка!ашаш) [4] разработали анализатор БРАМ, использующий модель проверки и символьного выполнения для имитации возможного поведения системы. На основе ЯЕАМ путем применения ВО)3 Болл (Вай) и другие [5] разработали статический анализатор ВОН для поиска ошибок использования АР1 в программах драйверов устройств, написанных на С.
Лившиц (Е!чзЬ!!з) и Лам (Еат) [17] описали, как можно использовать контекстно-чувствительный анализ целей указателей для поиска уязвимых мест в %еЬ- 1129 12.9. Список литературы к главе 12 приложениях 1ача, связанных с 814ь. Рувейз (Кцччазе) и Лам (Еаш) 120! описали, как отслеживать расширения массивов и автоматически вставлять динамические проверки границ. Ринард (Е!пап!) и другие 1! 9! описали, как динамически расширять массивы для предотвращения переполнения. Авоц (Ачогз) и другие [31 распространили контекстно-чувствительный анализ целей указателей )ача на язык программирования С и показали, каким образом его можно использовать для снижения стоимости динамического обнаружения переполнений буферов.
!. Айеп, Е Е., "1пгегргосег(ша1 г)ага бочч апа!уяз", Рюс. 1Р(Р Сол8гекг 1974, рр. 398-402, ХоггЬ Но!1апб, Ашзгегг(оп, 1974. 2. Апдегзеп, 1, Рю8гат Апа!узм апА Брес!айвайоп 7ог гле С Рюдгатт!лд Еал8иаяе, РЬ.(3. йеяз, 13!К(), ()п!ч. оГ СорепЬа8еп, Вепшагк, !994. 3. Ачогз, 13., М. 13а!гоп, Н. В. 1лчзЫгз, апд М, 8. Еагп, "1гпргочш8 зо((зчаге весапгу чч!1Ь а С ро!пгег апа1уяз", 1СБЕ 2005: Рюс. 27гл 1пгегпайопа! Соп~егелсе ол Бо7!ваге Еп8!пеег!л8, рр. 332-34!. 4. Ва!1, Т.
апб 8. К. Еа!ашап1, "А зушЬо1!с пюре! сЬескег Гог Ьоо!еап рго8гашз", Ргос. БР11ч' 2000 Рог!створ оп Мог1е! С!гес!г!п8 о7 Бо(Ьчаге, рр. ! 13 — ! 30. 5. Ва!1, Т., Е. Воцшпюча, В. Соо1с, Н. Ееч!п, 1. 1лсйепЬег8, С. Мсбагчеу, В. Опдпззе!г, 8. Рха)ашап(, апг( А. ()зпшег, "ТЬогоц8Ь згабс апа!уяз оГ меч!се ббчегз", ЕигоБуз (2006), рр.
73-85. 6. Вапгппй, 3. Р., "Ап ейс!епГ ччау го бпд 1Ье з!де ейесГз оГ ргосег)цга! са!1з апб йе а!!ввез оГ чапаЫез", Рюс. Б!хгл Аппиа! Бутрозгит оп Рг!пс!р!ея о~ Рю8гатт!лд Еал8иадез (1979), рр. 29-41. 7. Вагй, Л М., "А ргасбса! !пгегргосег1цга! с!ага бочч апа!уяз а!8оПйгп", Сотт. АСМ 21:9 (1978), рр. 724 — 736. 8. Вегпд!, М., О. 1.оЫа1г, Е ()!ап, 1.. Непдгеп, апг( Х.
()шалее, "Ро!пгзмо апа!- уяз цяп8 ВП(3'з", Ргос. АСМ Б16РЕАХ 2003 Сопгегепсе оп Рго8гаттгпд Еапдиа8е 1)ез!дл аЫ 1тр!етепгаг!оп, рр. 103 — 1! 4. 9. Вгуапй К. Е., "ОгарЬ-Ъазед а18обйппв Гог Воо!еап бзпсг!оп шап!рц!аг!оп", !ЕЕЕ Тгапя. оп Сотригегя С-35:8 (1986), рр. 677-691. 1О. ВцзЬ, 'чН. К., 1. 13. Ршсцз, апд О. 1. 8!е1ай; "А згабс апа1ухег Гог бпг(!п8 дупаппс рго8гаппп!п8 еггогз", Бо!Ьчаге — Ргасйсе апс( Ехрег!елее, 30:7 (2000), рр. 775-802. 1!. Са!!аЬап, 13., К. Р. Соорег, К. Кеппен, апг( Е.
Тогсхоп, "!пгегргосебпга! сопв[апг ргора8агюп", Ргос. ЯБР!А!ч' 1986 Бутрогйит оп Сотр!!ег Сопяггисбоп, ЯСРЕ А1ч' !чог!сея 21:7 (1986), рр. 152-161. 1130 Глава 12. Межпроцедурный анализ 12. Епй!ег, О., В. СЬе)й А. СЬон, апг( 8. Найегп, "СЬесЫпц вувгеш пг!ез няпй вузгеш-врес!йс, ргойгапнпег-ччпг!еп сошрйег ех!епяопв*', Ргос.
ЯхгЬ УБЕМХ Соп~егепсе оп Орегаг!пй Бувгетз Оеяйп апг( 1тр(етеп!а!гоп (2000). рр. ! — 16. 13. Ешапн, М., К.. ОЬ(уа, апо 1.. 1. Непйгеп, "СопГехпвепяйче !пгегргосеопга! ро(пгв-го апа1уяв ш 1Ье ргевепсе оГ йзпс!(оп ро(псегв", Ргос. Б1ИРЕАЬ! СопГегепсе оп Рго8гаттгпй Еапдиайе Оез!дп ат1 1тр!етепгайоп (1994), рр. 224- 256. 14. РаЬпг)псЬ, М., 1. КеЬоГ, апй М. Оав, тйса!аЫе сопгехг-вепяйче йозч апа!уяз няпй шв!апйайоп сопвгга(пГв", Ргос.
Б1бРЕА(з( Соп)егепсе оп Ргойгатт!пй З.апйиайе Оеядп апг! 1тр!етепгайоп (2000), рр. 253 — 263. 15. Не(пгге, )з!. апо О. Таго)ен, '"'1511га4авг айаяпй апа1уяв няпй С!.А: а пнйгоп !шез оГ С сойе ш а весопд", Ргос, о7 гЬе Б16РЬА!з! Соп!егепсе оп Ргодгатт!п8 Ьапдиаде Оев!Бп апг! 1тр!етепгайоп (200!), рр. 254 — 263.
16. 1.аш, М. Я., 1. %Ьа!еу, Ч. В. 1лчвЬ1!в, М. С. Магйп, О. Ачогв, М. СагЬш, апд С. 1)п)ге1, "Соп1ехг-вепяйче ргойгагп апа!уяв ав г)агаЬазе г(пег!ев", Ргос. 2005 АСМ Бутрояит оп Рг!пс!р!ез о!'ОагаЬазе Бувгетг, рр. 1 — 12. 17. !.!чзЬ11з, Ч. В. апд М. 8. 1.аш, "Рзпейпй зеснп1у чп1пеиЬП11!ев (п 1ача арр10 сайопв няпй вгайс апа!уяз", Ргос.
14й (1БЕЮ1ХБесиг!гу Бутрояит (2005), рр. 271-286. 18. Мйапоча, А., А. Конпгеч, апо В. б. Куоег, "Рагашегепгед оЬ)есг веня!!ч(гу Гог ро(пГв-го апй в!ое-ейесс апа1узев Гог 1ача", Ргос. 2002 АСМ Б16БОРТ 1пгегпайопа! Бутрояит оп Бо!Ьчаге Тевг!п8 аль Апа!уз!з, рр, 1 — 1!. 19. К(пагг(, М., С. Саоаг, О, Ошп)ггап, О. Коу, апо Т.
1 еп, "А йупапнс гесЬпн1не Гог е!нпзпайпй Ьн(Тег очегйозч ъ п!пегаЬз!гйев (апд о1Ьег гпегпогу епогв)", Ргос. 2004 Аппиа! Сотригег Бесиг!гу Арр!кабопв Соп/егепсе, рр. 82 — 90. 20. Кпзчаве, О, апг) М. 8. Еаш, "А ргасйса! йупаппс Ьн(Тег очегйозч оесессог", Ргос. 11й Аппиа! (з!егзчог!г апг! О!згг!Ьигег! Буяет Бесиг!гу Бутрояит (2004), рр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
