В информатике , анализ указателей или точек-анализа , является статический анализ кода метод , который определяет , какая указатели , или куча ссылок, может указывать на какие переменные или места хранения. Часто это компонент более сложного анализа, такого как анализ побега . Тесно связанный метод - анализ формы .
(Это наиболее распространенное использование термина в разговорной речи. Во вторичном использовании анализ указателя является собирательным названием как для анализа точек до , так и для анализа псевдонимов. Анализ точек и псевдонимов тесно связаны, но не всегда эквивалентны проблемы.)
Пример
Для следующей примерной программы анализ точек будет вычислять, что набор точек p
равен { x
, y
}.
int x ; int y ; int * p = unknown () ? & x : & y ;
Вступление
Как форма статического анализа, можно показать, что полностью точный анализ указателя неразрешим . [1] Большинство подходов являются разумными , но они сильно различаются по производительности и точности. Для больших программ могут потребоваться некоторые компромиссы, чтобы завершить анализ в разумные сроки и в разумных пределах. Два примера этих компромиссов: [2]
- Обработка всех ссылок от структурированного объекта как от объекта в целом. Это известно как нечувствительность к полю или нечувствительность к структуре .
- Игнорирование потока управления при анализе того, какие объекты назначены указателям. Это известно как контекстно-нечувствительный анализ указателя (при игнорировании контекста, в котором выполняются вызовы функций) или нечувствительный к потоку анализ указателя (при игнорировании потока управления внутри процедуры).
Недостатком этих упрощений является то, что вычисляемый набор объектов, на которые указывают, может стать менее точным.
Нечувствительные к контексту, нечувствительные к потоку алгоритмы
Алгоритмы анализа указателей используются для преобразования собранных использований необработанных указателей (присвоения одного указателя другому или присвоения указателя, указывающего на другой) в полезный график того, на что может указывать каждый указатель. [3]
Алгоритм Steensgaard в и алгоритм Андерсена являются общими контекстно-нечувствительным, проточным нечувствительны алгоритмами для анализа указателей. Они часто используются в компиляторах и имеют реализации в кодовой базе LLVM .
Подходы, нечувствительные к потоку
Многие подходы к анализу указателей, нечувствительному к потоку, можно понимать как формы абстрактной интерпретации , когда выделения в куче абстрагируются по месту их размещения (т. Е. Местоположению программы). [4]
Многие алгоритмы, нечувствительные к потоку, указаны в Datalog , в том числе в структуре анализа сажи для Java. [5]
Контекстно-зависимые, нечувствительные к потоку алгоритмы достигают более высокой точности, как правило, за счет некоторой производительности, анализируя каждую процедуру несколько раз, один раз для каждого контекста . [6] В большинстве анализов используется подход «строка контекста», когда контексты состоят из списка записей (общие варианты записи контекста включают сайты вызовов, сайты распределения и типы). [7] Чтобы гарантировать завершение (и, в более общем смысле, масштабируемость), такой анализ обычно использует подход k- ограничения, когда контекст имеет фиксированный максимальный размер, а наименее недавно добавленные элементы удаляются по мере необходимости. [8] Три распространенных варианта контекстно-зависимого, нечувствительного к потоку анализа: [9]
- Чувствительность call-site
- Чувствительность объекта
- Чувствительность к типу
Чувствительность call-site
В случае чувствительности сайта вызова набор точек для каждой переменной (набор абстрактных распределений кучи, на которые может указывать каждая переменная) дополнительно уточняется контекстом, состоящим из списка сайтов вызова в программе. Эти контексты абстрагируют поток управления программой.
Следующая программа демонстрирует, как чувствительность к месту вызова может обеспечить более высокую точность, чем нечувствительный к потоку и контекстно-независимый анализ.
int * id ( int * x ) { вернуть х ; } int main () { int y ; int z ; int * y2 = идентификатор ( & y ); // вызываем сайт 1 int * z2 = id ( & z ); // call-site 2 return 0 ; }
Для этой программы контекстно-независимый анализ (обоснованно, но неточно) пришел бы к выводу, что x может указывать либо на выделение, содержащее y, либо на z , поэтому y2 и z2 могут быть псевдонимами, и оба могут указывать на любое выделение. Чувствительный к call-сайту анализ будет анализировать id дважды, один раз для call-site 1 и один раз для call-site 2, и факты, указывающие на x , будут квалифицированы сайтом call-site, что позволит анализу вывести это, когда основной возврат , y2 может указывать только на хранение y, а z2 может указывать только на хранение z .
Чувствительность объекта
В объектно-чувствительном анализе набор точек каждой переменной определяется выделением абстрактной кучи объекта-получателя вызова метода. В отличие от чувствительности сайта вызова, объектная чувствительность не является синтаксической или нелокальной : записи контекста извлекаются во время самого анализа точек. [10]
Чувствительность к типу
Чувствительность к типу - это вариант чувствительности объекта, при котором место размещения объекта-получателя заменяется классом / типом, содержащим метод, содержащий сайт размещения объекта-получателя. [11] Это приводит к строго меньшему количеству контекстов, чем могло бы использоваться в объектно-чувствительном анализе, что обычно означает лучшую производительность.
Рекомендации
- ^ Репс, Томас (2000-01-01). «Неразрешимость контекстно-зависимого анализа зависимости данных» . Транзакции ACM по языкам и системам программирования . 22 (1): 162–186. DOI : 10.1145 / 345099.345137 . ISSN 0164-0925 . S2CID 2956433 .
- ^ Барбара Г. Райдер (2003). «Измерения точности справочного анализа объектно-ориентированных языков программирования». Конструирование компиляторов, 12-я Международная конференция, CC 2003, проведенная в рамках совместных европейских конференций по теории и практике программного обеспечения, ETAPS 2003 Варшава, Польша, 7–11 апреля 2003 г. Материалы . С. 126–137. DOI : 10.1007 / 3-540-36579-6_10 .
- ^ Зырянов, Влас; Newman, Christian D .; Guarnera, Drew T .; Collard, Michael L .; Малетик, Джонатан И. (2019). «srcPtr: платформа для реализации подходов к анализу статических указателей» (PDF) . ICPC '19: Материалы 27-й Международной конференции IEEE по пониманию программ . Монреаль, Канада: IEEE.
- ^ Смарагдакис, Яннис; Бравенбоер, Мартин; Лхотак, Ондрей (26 января 2011 г.). «Правильно подбирайте контекст: понимание объектной чувствительности» . Материалы 38-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ПОПЛ '11. Остин, Техас, США: Ассоциация вычислительной техники: 17–30. DOI : 10.1145 / 1926385.1926390 . ISBN 978-1-4503-0490-0. S2CID 6451826 .
- ^ Антониадис, Тони; Триантафиллу, Константинос; Смарагдакис, Яннис (18.06.2017). «Перенос doop на Soufflé: рассказ о переносимости между ядрами для анализа на основе данных Datalog» . Материалы 6-го международного семинара ACM SIGPLAN по современному состоянию программного анализа . SOAP 2017. Барселона, Испания: Ассоциация вычислительной техники: 25–30. DOI : 10.1145 / 3088515.3088522 . ISBN 978-1-4503-5072-3. S2CID 3074689 .
- ^ ( Смарагдакис и Балацурас , стр.29 )
- ^ Тиссен, Рей; Lhoták, Ondřej (14.06.2017). «Преобразования контекста для анализа указателя» . Уведомления ACM SIGPLAN . 52 (6): 263–277. DOI : 10.1145 / 3140587.3062359 . ISSN 0362-1340 .
- ^ ( Ли и др. , Стр. 1: 4)
- ^ ( Смарагдакис и Балацурас )
- ^ ( Смарагдакис и Балацурас , стр. 37)
- ^ ( Смарагдакис и Балацурас , стр.39 )
Библиография
- Зырянов, Влас; Newman, Christian D .; Guarnera, Drew T .; Collard, Michael L .; Малетик, Джонатан И. (2019). «srcPtr: платформа для реализации подходов к анализу статических указателей» (PDF) . ICPC '19: Материалы 27-й Международной конференции IEEE по пониманию программ . Монреаль, Канада: IEEE.
- Смарагдакис, Яннис; Балацурас, Джордж (2015). «Анализ указателя» (PDF) . Основы и тенденции в языках программирования . 2 (1): 1–69. DOI : 10.1561 / 2500000014 . Проверено 30 мая 2019 года .
- Ли, Юэ; Тан /, Тиан; Мёллер, Андерс; Смарагдакис, Яннис (18.05.2020). «Принципиальный подход к выборочной контекстной чувствительности для анализа указателя» . Транзакции ACM по языкам и системам программирования . 42 (2): 10: 1–10: 40. DOI : 10.1145 / 3381915 . ISSN 0164-0925 . S2CID 214812357 .
- Майкл Хинд (2001). «Анализ указателя: мы еще не решили эту задачу?» (PDF) . PASTE '01: Материалы семинара ACM SIGPLAN-SIGSOFT 2001 г. по анализу программ для программных средств и инженерии . ACM. С. 54–61. ISBN 1-58113-413-4.
- Стинсгаард, Бьярне (1996). «Точечный анализ за почти линейное время» (PDF) . POPL '96: Материалы 23-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . Нью-Йорк, Нью-Йорк, США: ACM. С. 32–41. DOI : 10.1145 / 237721.237727 . ISBN 0-89791-769-3.
- Андерсен, Ларс Оле (1994). Анализ и специализация программ для языка программирования C (PDF) (кандидатская диссертация).