# Static - Static Analysis

*Статический анализ (static analysis): Анализ артефактов разработки программного обеспечения, таких как требования или программный код, проводимый без исполнения этих программных артефактов. Статический анализ обычно выполняется при помощи вспомогательных инструментов. (ISTQB)*

Статический анализ - это анализ программных артефактов, таких как программный код (или требования, дизайн), выполняемый статически, т.е. без запуска и, очевидно, методом белого ящика. Основная цель этого анализа - как можно раньше найти ошибки, независимо от того, могут ли они вызывать отказы (failures). Как и в случае с обзорами (reviews), статический анализ обнаруживает ошибки (bugs), а не отказы. Обычно статический анализ проводят до формальной проверки, даже до unit testing, путём добавления этих проверок специалистами DevOps в пайплайн проекта. Статический анализ не связан с динамическими свойствами требований, дизайна и кода, такими как покрытие тестами (test coverage). Существует множество инструментов для статического анализа, которые в основном используются разработчиками до или во время тестирования компонентов или интеграции (чаще новые и измененные классы и функции), а также дизайнерами во время моделирования программного обеспечения. Инструменты могут отображать не только структурные атрибуты, такие как глубина вложенности или число цикломатической сложности и проверка на соответствие стандартам кодирования, но также графические изображения потока управления, взаимосвязи данных и количество отдельных путей от одной строки кода к другой. Информация может использоваться вплоть до формальных методов, которые математически подтверждают свойства данной программы.

Инструменты помогают в выявлении следующих дефектов:

* Неиспользуемые переменные;
* Части кода, которые никогда не выполнятся;
* Бесконечные циклы;
* Переменная с неопределенным значением;
* Неправильный синтаксис;
* Несогласованные интерфейсы между модулями и компонентами, такие как неправильное использование объекта, метода или функции, включая неправильные параметры;
* Уязвимости безопасности, такие как проблемы безопасности, связанные с переполнением буфера, возникающим из-за невозможности проверить длину буфера перед копированием в буфер;
* Различные типы нарушения стандартов программирования, как нарушения, создающие риск фактического сбоя, так и нарушения, которые усложняют тестирование, анализ и поддерживаемость кода;

**Методы статического анализа**:

* **Анализ управления** (Control Analysis): фокусируется на изучении элементов управления, используемых в структуре вызовов, анализе потока управления и анализе переходов состояний (calling structure, control flow analysis and state transition analysis). Структура вызова связана с моделью путем идентификации вызовов и их структуры. Вызывающая структура может быть процессом, подпрограммой, функцией или методом. Анализ потока управления проверяет последовательность передачи управления и может выявить неэффективные конструкции в модели. Создается граф модели (CFG - Control Flow Graph), в котором условные ветви и стыки модели представлены узлами. По итогам также можно рассчитать цикломатическую сложность программы. Для анализа потока управления [могут быть](https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D1%83%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F) использованы: Абстрактная интерпретация, Удовлетворение ограничений, Типизация данных;
* **Анализ данных** (Data Analysis): обеспечивает правильную работу с объектами данных, такими как структуры данных и связанные списки. Кроме того, этот метод также обеспечивает правильное использование определенных данных. Анализ данных включает два метода, а именно: зависимость данных и анализ потока данных (data dependency and data flow analysis). Зависимость данных необходима для оценки точности синхронизации между несколькими процессорами. Анализ потока данных проверяет определение и контекст переменных. Виды анализа потока данных:
  * Reaching Definitions;
  * Available Expressions;
  * Constant Propagation;
  * Very Busy Expressions;
  * Live Variables;
  * Use-Definition & Definition-Use;
* Анализ неисправностей / отказов (Fault/Failure Analysis): анализирует неисправности (некорректный компонент) и отказ (некорректное поведение компонента модели) в модели. Этот метод использует описание преобразования ввода-вывода для определения условий, являющихся причиной сбоя. Для определения отказов в определенных условиях проверяется проектная спецификация модели (model design specification);
* Анализ интерфейса (Interface Analysis): проверяет взаимодействующие и распределенные модели для проверки кода (This software verifies and verifies interactive and distribution simulations to check the code). Существует два основных метода анализа интерфейса, и анализ пользовательского интерфейса исследует интерфейсы подмоделей и определяет точность структуры интерфейса. Анализ пользовательского интерфейса исследует модель пользовательского интерфейса и меры предосторожности, предпринимаемые для предотвращения ошибок во время взаимодействия пользователя с моделью. Этот метод также фокусируется на том, насколько точно интерфейс интегрирован в общую модель и симуляцию.

Анализ потока управления (Control Flow Analysis) и анализ потока данных (Data Flow Analysis) взаимозависимы: чтобы получить точные результаты для анализа потока данных, необходимо учитывать поток управления (поскольку порядок операций влияет на возможные значения данных в конкретном месте программы). Чтобы получить точные результаты для анализа потока управления, необходимо учитывать поток данных, поскольку поток динамического управления (решение, принимаемое во время выполнения) зависит от значений данных в конкретных местах программы. Однако эти два анализа преследуют разные цели.

**Граф потока управления (Control Flow Graph)**

Граф потока управления (CFG) - это графическое представление потока управления или вычислений во время выполнения программ или приложений. Графы потока управления в основном используются в статическом анализе, а также в приложениях-компиляторах, поскольку они могут точно представлять поток внутри программного модуля. Характеристики графа потока управления:

* Граф потока управления процессно-ориентированный (process oriented);
* Граф потока управления показывает все пути, которые можно пройти во время выполнения программы;
* Граф потока управления - это [ориентированный](https://ru.wikipedia.org/wiki/%D0%9E%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84) граф;
* Рёбра в CFG изображают пути потока управления, а узлы в CFG изображают базовые блоки.

[Полное описание возможных элементов графа](https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D1%83%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F).

**Цикломатическая сложность (Cyclomatic Complexity)**

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

Определение из книги Ли Копланда - “A Practitioner's Guide to Software Test Design”, Главы 10:

Цикломатическая сложность​ - это конечное минимальное количество независимых, нецикличных маршрутов (называемых основными маршрутами), которые могут образовывать все возможные линейные пути в программном модуле.

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

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

*M = E − N + 2P*,

где:

* M = цикломатическая сложность,
* E = количество ребер в графе,
* N = количество узлов в графе,
* P = количество компонент связности.

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

*M = E − N + P*.

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

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

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

Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна

*π − s + 2*,

где:

* π - число точек ветвления в программе,
* s - число точек выхода.

Применение:

* Ограничение сложности при разработке: одно из первоначально предложенных Маккейбом применений состоит в том, что необходимо ограничивать сложность программ во время их разработки. Он рекомендует, чтобы программистов обязывали вычислять сложность разрабатываемых ими модулей и разделять модули на более мелкие всякий раз, когда цикломатическая сложность этих модулей превысит 10. Эта практика была включена НИСТ-ом в методику структурного тестирования с замечанием, что со времени исходной публикации Маккейба выбор значения 10 получил весомые подтверждения, однако в некоторых случаях может быть целесообразно ослабить ограничение и разрешить модули со сложностью до 15. В данной методике признается, что иногда могут существовать причины для выхода за рамки согласованного лимита. Это сформулировано как рекомендация: «Для каждого модуля следует либо ограничивать цикломатическую сложность до согласованных пределов, либо предоставить письменное объяснение того, почему лимит был превышен»;
* Применение при тестировании программного обеспечения: определение количества тестов, необходимых для полного покрытия кода. Цикломатическая сложность M имеет два свойства, для конкретного модуля:
  * M - оценка сверху для количества тестов, обеспечивающих покрытие условий (точек ветвления);
  * M - оценка снизу для количества маршрутов через граф потока управления и, таким образом, количества тестов для полного покрытия путей.
* В составе других метрик: используется в качестве одного из параметров в индексе удобства сопровождения (англ. maintainability index).

Источники:

* [Types of Static Analysis Methods](https://www.geeksforgeeks.org/types-of-static-analysis-methods/)
* [Software Testing - Static Testing](https://www.geeksforgeeks.org/software-testing-static-testing/)
* [Static program analysis](https://en.wikipedia.org/wiki/Static_program_analysis)
* [What is Static Analysis](https://www.educba.com/what-is-static-analysis/)
* [Software Engineering - Control Flow Graph (CFG)](https://www.geeksforgeeks.org/software-engineering-control-flow-graph-cfg/?ref=lbp)
* [Цикломатическая сложность](https://ru.wikipedia.org/wiki/%D0%A6%D0%B8%D0%BA%D0%BB%D0%BE%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C)

Доп. материал:

* [Михаил Моисеев - “Формальные методы обеспечения качества ПО: Введение в статический анализ”](http://kspt.icc.spbstu.ru/media/files/2010/course/softwarequality/lec3.pdf)
* [Y.N. Srikant - “Control Flow Analysis”](https://www.iith.ac.in/~ramakrishna/fc5264/control-flow-analysis.pdf)
* [Levels in Data Flow Diagrams (DFD)](https://www.geeksforgeeks.org/levels-in-data-flow-diagrams-dfd/)
* [Control Flow Graph (CFG)](https://www.geeksforgeeks.org/software-engineering-control-flow-graph-cfg/)
* [Static analysis tools](https://github.com/analysis-tools-dev/static-analysis/blob/master/README.md)
* [Podlodka #227 - Статический анализ кода](https://www.youtube.com/watch?v=S-ZRIKdZezQ)
* [Архитектурное тестирование](https://habr.com/ru/post/590555/)