Несмотря на большое количество доступных инструментов поиска утечек памяти, в том числе от таких гигантов ИТ как FaceBook, существует ряд ограничений применимости этих инструментов. В данной статье я хочу подробно представить и сравнить существующие инструменты и их границы применимости.

Инструмент SMOKE

SMOKE использует два этапа для достижения высокой точности и масштабируемости. Сначала используется быстрей, но неточный анализ для обнаружения всех возможных путей утечки памяти. Для этого строится программное представление под названием граф потока использования (ГПИ) (use-flow graph), который явно моделирует жизненный цикл указателей динамической памяти. Далее используется более точный анализ для каждого обнаруженного пути ошибки. Применяется решатель (solver) ограничений Z3 для проверки выполнимости путей.

Инструмент PCA

PCA построен на базе компиляторной инфраструктуры LLVM. На первом этапе инструмент компилирует исходные файлы в промежуточное представление LLVM и выполняет анализ указателей Андерсена. С использованием полученной информации строится граф вызовов. На втором этапе строится межпроцедурный граф зависимостей данных (ГЗД). Для обнаружения утечки памяти PCA собирает все узлы для заданной инструкции выделения памяти, которые доступны на ГЗД. Если в множестве собранных вершин не содержится вызов функции free(), тогда происходит утечка памяти.

Инструмент SVF

SVF также построен на базе LLVM и использует его промежуточное представление для анализа указателей (доступно несколько вариантов, включая анализ указателей Андерсена). На базе промежуточного представления LLVM и информации об указателях строится граф потока значений (ГПЗ) (value flow graph). Узлы ГПЗ — это все переменные программы. Ребра строятся на основе информации об указателях и use-def анализа. SVF позволяет реализовать разные детекторы на основе ГПЗ. Примером является детектор утечки памяти, который рассматривает задачу как проблему источника приемника (source-sink проблема), каждое выделение памяти на каждом пути должно достигать своего освобождения.

Инструмент Fastcheck

Fastcheck реализует межпроцедурный алгоритм обнаружения утечек памяти. Производится отслеживание потока значений от точек выделения динамической памяти к точкам его освобождения с использованием разреженного графа потока значений. Ребра из инструкций вызовов и возврата помечены информацией о вызванной функции, что обеспечивает контекстную чувствительность анализа. Обнаружение утечки памяти сводится к проблеме достижимости через разреженный граф потока значений. Fastcheck для каждого выделения памяти пытается найти пути в ГПЗ с инструкциями его освобождения. Если существует хоть один выполнимый путь (проверяется SMT-решателем) без инструкции освобождения, тогда выдается сообщение об утечке памяти.

Инструмент Clang Static Analyzer

Clang Static Analyzer (CSA) производит поиск разных ошибок путем символьного выполнения программ. Для анализа используется структура данных под названием разобранный граф (РГ) (exploded graph). РГ строится на базе абстрактного синтаксического дерева и потока управления программы. Ядро анализа производит символьное выполнение, и во время обхода потока управления программы строится РГ. Вершины РГ содержат в себе следующую пару:

1. ProgramPoint – точка между двумя инструкциями в потоке управления программы,

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

Ребром между двумя вершинами «(Point1, State1), (Point2, State2)» в РГ является инструкция программы. Инструкция находится между точками Point1, Point2, и ее выполнение обеспечивает переход программы из состояния State1 в State2. Для поиска ошибок (в том числе утечки памяти) существуют отдельные детекторы. Утечки памяти находятся путем прослеживания указателей выделенных участков динамической памяти. Если существуют пути выполнения, на которых освобождение не производится, детектор выдает ошибки и соответствующие пути.

Инструмент Infer

Infer позволяет найти утечки памяти и использование нулевых указателей для Java и Си/Си++. Во время анализа каждая функция представляется в виде:

{Precondition (P)} Command(C) {Postcondition(Q)} = Hoare3, где P и Q - модели памяти по сепарационной логике, а C - инструкция или функция, которая выполняется. Значение Hoare3 - “истина”, если выполнение C приводит память из состояния P в Q. Для каждого пути графа вызовов последовательно выполняются соответствующие функциям тройки Hoare3, на основе состояния модели памяти Q обнаруживается утечка. Инструмент обеспечивает чувствительность к потоку, путям, полям и контексту программы.

Инструмент PML Checker

PML Checker получает абстрактное синтаксическое дерево (АСД) для входной программы. Из АСД строится граф потока управления, и из него удаляются все базовые блоки и ребра, выполнение которых не влияет на выделение и освобождение динамической памяти. На базе графа потока управления строится поток данных для инструкций, производящий выделение динамической памяти. Инструмент рассматривает все пути выполнения программы. Если существует путь, на котором производится выделение памяти, и поток данных этой инструкции не доходит до инструкций освобождения, тогда считается, что существует потенциальная утечка памяти. Для окончательной проверки применятся символьный решатель.

Сравнение инструментов и заключение

В таблице ниже приводим сравнение чувствительности рассмотренных инструментов.

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

Утечка-1
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct node {
  struct node *next;
  int *value;
} node_type;
static node_type *create_node(int value) {
  node_type *p = (node_type *)malloc(sizeof(node_type));
  p->value = (int *)malloc(sizeof(int));
  p->next = NULL;
  return p;
}
static void delete_node_leak(node_type **list_pptr, int value) {
  node_type *list = *list_pptr, *prev = NULL, *t;
  while (list != NULL && *(list->value) != value) {
    prev = list;
    list = list->next;
  }
  if (list == NULL)
    return;
  if (*(list->value) == value) {
    if (prev == NULL) {
      t = list;
      *list_pptr = list->next;
      free(t); // t-value is not freed
    } else {
      t = list;
      prev->next = list->next;
      free(t); // t-value is not freed
    }
  }
}
static void free_nodes_correct(node_type *list) {
  node_type *tlist;
  while (list != NULL) {
    tlist = list->next;
    free(list->value);
    free(list);
    list = tlist;
  }
}
int main(void) {
  node_type *list = create_node(1);
  list->next = create_node(2);
  delete_node_leak(&list, 2);
  free_nodes_correct(list);
  return 0;
}

Утечка-2
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct node {
  struct node *next;
  int value;
} node_type;
static void delete_node(node_type **list, int value) {
  node_type *l = *list, *p = NULL;
  while (l != NULL && l->value != value) {
    p = l;
    l = l->next;
  }
  if (list == NULL)
    return;
  if (l->value == value) {
    if (p == NULL) {
      node_type *t = l;
      *list = l->next;
      free(t);
    } else {
      node_type *t = l;
      p->next = l->next;
      free(t);
    }
  }
}
static void free_nodes(node_type *list) {
  node_type *t;
  while (!list) {
    t = list->next;
    free(list);
    list = t;
  }
}
int main(void) {
  int nodes = 0;
  node_type *head = NULL;
  while (nodes < 1000) {
    // two nodes added each time
    node_type *plist = (node_type *)malloc(sizeof(node_type));
    plist->value = 1;
    node_type *tmp = (node_type *)malloc(sizeof(node_type));
    tmp->value = 2;
    tmp->next = head;
    plist->next = tmp;
    head = plist;
    // only delete node with value=2
    delete_node(&head, 2);
    nodes++;
  }
  free_nodes(head);
  return 0;
}

Утечка-3
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct node {
  struct node *next;
  int value;
} node_type;
static void free_nodes_leak(node_type *list) {
  node_type *t;
  while (list != NULL) {
    t = list->next;
    if (list->value == 2)
      free(list); // leak if list->value != 2
    list = t;
  }
}
int main(void) {
  node_type *list = (node_type *)malloc(sizeof(node_type));
  list->value = 1;
  node_type *tmp = (node_type *)malloc(sizeof(node_type));
  tmp->value = 2;
  tmp->next = NULL;
  list->next = tmp;
  free_nodes_leak(list);
  return 0;
}

Утечка-4
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct node {
  struct node *next;
  int value;
} node_type;
static node_type *list = NULL; 
static void free_nodes_leak(void) {
  node_type *l = list, *t;
  while (l != NULL) {
    t = l->next;
    if (l->value == 2)
      free(l); // leak if l->value != 2
    l = t;
  }
}
void insert_node(node_type *x) {
  x->next = list;
  list = x;
}
int main(void) {
  node_type *node = (node_type *)malloc(sizeof(node_type));
  node->value = 1;
  node->next = NULL;
  insert_node(node);
  node = (node_type *)malloc(sizeof(node_type));
  node->value = 2;
  node->next = NULL;
  insert_node(node);
  free_nodes_leak();
  return 0;
}

Утечка-5
#include <stdlib.h>

typedef struct node {
  struct node *next;
  int *data;
} node_type;
node_type *alloc_node(void) {
  node_type *p;
  p = (node_type *)malloc(sizeof(node_type));
  p->data = (int *)malloc(sizeof(int));
  return p;
}
void free_node(node_type *p) {
  if (p->data != NULL)
    free(p->data);
  free(p);
}
void insert_node(node_type **head, node_type *node) {
  node->next = *head;
  *head = node;
}
void free_nodes(node_type *head) {
  node_type *node;
  node = head;
  while (node != NULL) {
    head = node->next;
    free(node); // p->data not freed
    node = head;
  }
}
int main(void) {
  node_type *p, *head = NULL;
  p = alloc_node();
  insert_node(&head, p);
  p = alloc_node();
  insert_node(&head, p);
  free_nodes(head);
  return 0;
}

Утечка-6
#include <stdlib.h>

typedef struct node {
  struct node *next;
  int *data;
} node_type;
node_type *alloc_node(void) {
  node_type *p;
  p = (node_type *)malloc(sizeof(node_type));
  p->data = (int *)malloc(sizeof(int));
  return p;
}
void free_node(node_type *p) {
  if (p->data != NULL)
    free(p->data);
  free(p);
}
int always_false(void){
  return 0;
}
void insert_node(node_type **head, node_type *node) {
  if (always_false()) {
    node->next = *head;
    *head = node;
  }
}
void free_nodes(node_type *head) {
  node_type *node;
  node = head;
  while (node != NULL) {
    head = node->next;
    free(node->data);
    free(node);
    node = head;
  }
}
int main(void) {
  node_type *p, *head = NULL;
  p = alloc_node();
  insert_node(&head, p); // p is not inserted into head
  p = alloc_node();
  insert_node(&head, p); // p is not inserted into head
  free_nodes(head);
  return 0;
}

Требуется обратить отдельное внимание на Утечку-2. Фактически там не происходит утечки памяти, а можно было бы в цикле производить освобождение, тем самым оптимизируя потребление памяти. В таблице ниже приводятся результаты инструментов.

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

В связи с вышесказанным нами было принято организовать международный конкурс по анализу программного обеспечения (Global Software Analysis Competition – GSAC 2023). В рамках данного конкурса одной из задач является разработка качественного инструмента поиска утечек памяти. У нас большая надежда на то, что талантливые молодые ребята, а также опытные специалисты, смогут найти новые подходы для решения данной задачи. Для мотивации команд выделен призовой фонд в размере $30K. Подробности конкурса можно найти на вебсайте - https://gsac.tech/.

Список литературы

1. Clang Static Analyzer - https://clang-analyzer.llvm.org/

2. SVF - https://github.com/SVF-tools/SVF

3. Infer - https://fbinfer.com/

4. Fastcheck - https://www.cs.cornell.edu/projects/crystal/fastcheck/fastcheck-pldi07.pdf

5. SMOKE - https://gangfan.github.io/assets/papers/gang_smoke_icse2019_preprint.pdf

6. PML Checker - https://www.researchgate.net/publication/326103866_A_Projection-Based_Approach_for_Memory_Leak_Detection

7. LLVM - https://llvm.org/

8. Z3 - https://github.com/Z3Prover/z3

9. GSAC 2023 - https://gsac.tech/