Анализ указателя

В информатике указатели анализ указателей или анализ точек на — это метод статического анализа кода , который устанавливает, какие или ссылки на кучу могут указывать на какие переменные или места хранения . Часто он является компонентом более сложных анализов, таких как анализ бегства . Близко к этому методу относится анализ формы .

Это наиболее распространенное разговорное употребление этого термина. Во вторичном использовании анализ указателей является собирательным названием как для анализа точек , определенного выше, так и для анализа псевдонимов . Анализ точек и псевдонимов — тесно связанные, но не всегда эквивалентные задачи.

Пример

В следующем примере программы анализ точек на вычислит, что набор точек на p является { x, y}.

int x;
int y;
int* p = unknown() ? &x : &y;

Введение

Можно показать, что как форма статического анализа полностью точный анализ указателей неразрешим . Большинство подходов надежны , но их производительность и точность сильно различаются. Многие проектные решения влияют как на точность, так и на производительность анализа; часто (но не всегда) более низкая точность приводит к более высокой производительности. Эти варианты включают в себя:

• Чувствительность поля (также известная как чувствительность структуры ): анализ может либо обрабатывать каждое поле структуры или объекта отдельно , либо объединять их.
• Чувствительность массива . Анализ указателей, чувствительный к массиву, моделирует каждый индекс в массиве отдельно. Другие варианты включают моделирование только первой записи отдельно, а остальных вместе или объединение всех записей массива.
• Контекстная чувствительность или поливариантность . Анализ указателей может квалифицировать информацию, указывающую на, с помощью сводки потока управления, ведущего к каждой точке программы.
• Чувствительность потока : анализ может моделировать влияние внутрипроцедурного потока управления на факты, указывающие на него.
• Моделирование кучи . Распределение во время выполнения может быть абстрагировано с помощью:
  • их сайты распределения (оператор или инструкция, выполняющая распределение, например, вызов malloc или конструктор объекта),
  • более сложная модель, основанная на анализе формы ,
  • тип распределения или
  • одно единственное распределение (это называется нечувствительностью к куче ).
• Клонирование кучи . Анализ кучи и контекстно-зависимый анализ могут дополнительно квалифицировать каждый сайт распределения путем сводки потока управления, ведущего к инструкции или оператору, выполняющему распределение.
• Ограничения подмножества или ограничения равенства : при распространении фактов, указывающих на, разные операторы программы могут налагать разные ограничения на наборы точек, принадлежащих переменной. Ограничения равенства (подобные тем, которые используются в алгоритме Стинсгаарда ) можно отслеживать с помощью структуры данных поиска по объединению , что приводит к высокой производительности за счет точности анализа, основанного на ограничениях подмножества (например, алгоритм Андерсена ).

потоконезависимые

Алгоритмы анализа указателей используются для преобразования собранных данных об использовании необработанных указателей (назначение одного указателя другому или присвоение указателя для указания на другой) в полезный график того, на что может указывать каждый указатель.

Алгоритм Стинсгаарда и алгоритм Андерсена являются распространенными контекстно-независимыми и нечувствительными к потоку алгоритмами для анализа указателей. Они часто используются в компиляторах и имеют реализации в SVF. и ЛЛВМ .

к

Многие подходы к анализу указателей, не зависящих от потока, можно понимать как формы абстрактной интерпретации , где выделение кучи абстрагируется по месту их размещения (т. е. местоположению программы).

Анализ указателей, нечувствительный к потоку, часто абстрагирует возможные выделения во время выполнения по их месту размещения. Во время выполнения эта программа создает три отдельных выделения кучи. Анализ указателей, нечувствительный к потоку, будет рассматривать их как одну абстрактную ячейку памяти, что приведет к потере точности.

Многие нечувствительные к потоку алгоритмы указаны в Datalog , в том числе в среде анализа сажи для Java.

Контекстно-зависимые и чувствительные к потоку алгоритмы достигают более высокой точности, как правило, за счет некоторой производительности, анализируя каждую процедуру несколько раз, по одному разу для каждого контекста . В большинстве анализов используется подход «контекстной строки», где контексты состоят из списка записей (обычные варианты записи контекста включают места вызова, места размещения и типы). Чтобы гарантировать завершение (и, в более общем смысле, масштабируемость), в таких анализах обычно используется подход с ограничением k , при котором контекст имеет фиксированный максимальный размер, а элементы, добавленные последними, удаляются по мере необходимости. Три распространенных варианта контекстно-зависимого и нечувствительного к потоку анализа:

• Чувствительность места вызова
• Чувствительность объекта
• Тип чувствительности

Чувствительность места вызова

В чувствительности к месту вызова набор точек на каждую переменную (набор абстрактных выделений кучи, на которые может указывать каждая переменная) дополнительно уточняется контекстом, состоящим из списка мест вызова в программе. Эти контексты абстрагируют поток управления программой.

Следующая программа демонстрирует, как чувствительность к месту вызова может обеспечить более высокую точность, чем нечувствительный к потоку и контекстно-независимый анализ.

int *id(int* x) {
  return x;
}
int main() {
  int y;
  int z;
  int *y2 = id(&y); // call-site 1
  int *z2 = id(&z); // call-site 2
  return 0;
}

Для этой программы контекстно-независимый анализ (здравый, но неточный) заключит, что x может указывать либо на выделение, содержащее y, либо на выделение z , поэтому y2 и z2 могут быть псевдонимами, и оба могут указывать на любое распределение. Анализ, чувствительный к месту вызова, будет анализировать id дважды: один раз для сайта вызова 1 и один раз для сайта вызова 2, а факты, указывающие на x, будут определяться сайтом вызова, что позволит анализу сделать вывод об этом, когда main вернет , y2 может указывать только на выделение, содержащее y , а z2 может указывать только на выделение, содержащее z .

Чувствительность объекта

В объектно-чувствительном анализе набор точек каждой переменной уточняется абстрактным выделением кучи объекта-получателя вызова метода. В отличие от чувствительности к месту вызова, чувствительность к объекту не является синтаксической или нелокальной : записи контекста извлекаются во время самого анализа точек.

Тип чувствительности

Чувствительность к типу — это вариант чувствительности к объекту, при котором место размещения объекта-получателя заменяется классом/типом, содержащим метод, содержащий место размещения объекта-получателя. В результате используется строго меньше контекстов, чем при объектно-зависимом анализе, что обычно означает более высокую производительность.

Библиография

• Зырянов, Влас; Ньюман, Кристиан Д.; Гуарнера, Дрю Т.; Коллард, Майкл Л.; Малетик, Джонатан И. (2019). «srcPtr: платформа для реализации подходов к статическому анализу указателей» (PDF) . ICPC '19: Материалы 27-й Международной конференции IEEE по пониманию программ . Монреаль, Канада: IEEE.
• Смарагдакис, Яннис; Балацурас, Джордж (2015). «Анализ указателя» (PDF) . Основы и тенденции в языках программирования . 2 (1): 1–69. дои : 10.1561/2500000014 . S2CID   207179267 . Проверено 30 мая 2019 г.
• Ли, Юэ; Тан/, Тянь; Мёллер, Андерс; Смарагдакис, Яннис (18 мая 2020 г.). «Принципиальный подход к выборочной контекстной чувствительности для анализа указателей» . Транзакции ACM в языках и системах программирования . 42 (2): 10:1–10:40. дои : 10.1145/3381915 . ISSN   0164-0925 . S2CID   214812357 .
• Майкл Хинд (2001). «Анализ указателя: мы еще не решили эту проблему?» (PDF) . PASTE '01: Материалы семинара ACM SIGPLAN-SIGSOFT 2001 г. по анализу программ для программных инструментов и проектирования . АКМ. стр. 54–61. ISBN  1-58113-413-4 .
• Стинсгаард, Бьярн (1996). «Анализ точек к почти линейному времени» (PDF) . POPL '96: Материалы 23-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 32–41. дои : 10.1145/237721.237727 . ISBN  0-89791-769-3 .
• Андерсен, Ларс Оле (1994). Анализ программ и специализация для языка программирования C (PDF) (кандидатская диссертация).