Статический анализ программ

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

Definition

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

Scope

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

Core questions

• Как свойства программы вычисляются путем распространения фактов по графу потока управления?
• Как чувствительность к потоку, контексту и пути влияет на точность и стоимость?
• Как корректный анализ проводится через вызовы процедур?
• Как анализ указателей справляется с псевдонимами и косвенной адресацией?

Key theories

Анализ потоков данных как неподвижная точка над решеткой

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

Межпроцедурный анализ через достижимость графа

Репс, Хорвиц и Сагив свели большой класс точных межпроцедурных задач анализа потоков данных к достижимости графа, что позволило эффективно проводить контекстно-чувствительный анализ через границы процедур.

Принципы и измерения анализа

Нильсон, Нильсон и Ханкин систематизируют анализы, основанные на потоках данных, ограничениях и типах, а также компромиссы между точностью и стоимостью, которые определяют их проектирование.

Clinical relevance

Статический анализ используется в оптимизации компиляторов, инструментах поиска ошибок и уязвимостей, линтерах и функциях интегрированных сред разработки (IDE). Корректные анализы могут подтвердить отсутствие определенных ошибок, в то время как масштабируемые эвристические анализы широко применяются для раннего выявления дефектов на стадии разработки.

History

Анализ потоков данных вырос из оптимизирующих компиляторов, при этом теоретическую основу обеспечили решеточная структура Килдалла 1973 года и анализы Аллена-Кока. Межпроцедурный анализ и анализ указателей развивались в 1980-х и 1990-х годах, включая формулировку достижимости Репса-Хорвица-Сагива, а статический анализ позднее масштабировался для промышленного поиска ошибок в очень больших кодовых базах.

Debates

Точность против масштабируемости

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

Key figures

• Gary Kildall
• Thomas Reps
• Susan Horwitz
• Flemming Nielson
• Hanne Riis Nielson

Seminal works

• kildall1973
• reps1995
• nielson1999

Frequently asked questions

Что означает корректность статического анализа?

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

Почему анализ указателей сложен?

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