Taint-анализ в C и C++ анализаторе PVS-Studio / Хабр

Ваш код принимает данные извне? Поздравляем, вы вступили на минное поле! Любой непроверенный ввод от пользователя может привести к уязвимости, и найти все "растяжки" вручную в большом проекте почти невозможно. Но есть "сапёр" — статический анализатор. Инструмент нашего "сапёра" — taint-анализ (aka анализ помеченных данных). Он позволяет обнаружить "грязные" данные, дошедшие до опасных мест без проверки. Сегодня мы расскажем о том, как он работает.

Да кто такой этот ваш taint-анализ?!

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

int main()
{
  char name[256];
  printf("Stand up. There you go. "
         "You were dreaming. What's your name?\n");
  scanf("%255s", name);
  printf(name);

  return 0;
}

Давайте мы пока закроем глаза на возможное переполнение буфера name при пользовательском вводе — это всего лишь наша вторая программа. Будем честны, этого количества символов хватит всем. Ну... почти всем. :) Однако в этой программе мы также сталкиваемся и с другой проблемой: в строке name содержатся помеченные данные. К чему может привести передача такой строки в функцию printf, мы рассказывали в отдельной статье.

"Такие косяки допускают только студенты", — скажете вы. Спешу раздосадовать: мы находили подобные ошибки вовсе не в курсовых работах.

Чтобы находить их на этапе написания кода, можно использовать статические анализаторы с применением технологии taint-анализа. Давайте же заглянем под капот C и C++ анализатора PVS-Studio и подробнее рассмотрим его устройство.

Да, у нас была стратегия

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

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

int getElement(int index)
{
  int arr[2] {0, 1};
  return arr[index];
}

int main()
{
  int index = 0;                         // index = 0
  std::cin >> index;                     // index = [INT_MIN; INT_MAX]
  index &= 1;                            // index = [0; 1]
  int element = getElement(index);
  return element;
}

В примере отмечено, какое виртуальное значение имеет переменная index в каждой точке выполнения программы.

При объявлении и инициализации переменой присваивается значение 0;
При получении индекса из консоли его значение становится любым и ограничивается только фантазией пользователя и диапазоном типа, т.е. [INT_MIN; INT_MAX];
После операции побитового "И" значение index принадлежит диапазону [0; 1].

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

Но что делать, если нам неизвестно виртуальное значение переменной? Например, это параметр функции. Давайте удалим функцию main из прошлого примера:

int getElement(int index)
{
  int arr[2] {0, 1};
  return arr[index]; // index is unknown
}

Вот перед нами просто функция, возвращающая значение массива по индексу. Во время анализа тела функции без межпроцедурной информации значение параметра index анализатору неизвестно.

Может возникнуть закономерный вопрос: "Разве index = [INT_MIN; INT_MAX] и index is unknown не одно и то же?"

Нет, это не одно и то же. Пожалуй, тут нужно отступить и пояснить один важный момент.

Существуют sound и unsound стратегии статического анализа. Обычно анализатор работает в unsound-стратегии и генерирует предупреждения только если может доказать наличие ошибки. И при такой стратегии предупреждение о выходе за границу массива в последнем примере выдано не будет. Мы не знаем значения индекса и несмотря на то, что выход за границу массива возможен, утверждать о наличии ошибки нельзя. В противном случае мы просто утонем в ложных и бессмысленных срабатываниях.

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

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

Не будем глубоко вдаваться в описание теории taint-анализа и статического анализа, в целом. В статьях про Java анализатор мы уже касались этой темы и даже подробно её рассматривали.

Заглянем под капот

Как мы уже выяснили, taint-анализ — это часть sound-стратегии, и работает он на основе анализа потока данных. Источниками помеченных данных, как правило, являются потоки ввода: консоль, файл, сокет и т.д. Так или иначе, все данные, полученные извне, а не посчитанные в процессе выполнения программы, являются потенциально помеченными.

Примечание. Помимо общеизвестных источников потенциально помеченных данных, таких как std::cin и scanf, в PVS-Studio есть возможность добавления пользовательских источников с помощью аннотаций в формате JSON.

Например, так пользователь может добавить свой собственный источник потенциально помеченных данных, проаннотировав его как taint_source:

std::string ReadStrFromStream(std::istream &input, std::string &str)
{
  ....
  input >> str; 
  return str;
  ....
}

"annotations": [
  ....
  {
    "type": "function",
    "name": "ReadStrFromStream",
    "params": [
      {
        "type": "std::istream &input"
      },
      {
        "type": "std::string &str",
        "attributes": [ "taint_source" ] // <=
      }
    ],
    "returns": { "attributes": [ "taint_source" ] }
  }
  ....
]

Подробнее про аннотации в формате JSON можно прочитать в нашей документации.

Полученные из источников данные считаются помеченными и отмечаются соответствующим тегом. При операциях с такими данными их статус может распространяться (taint propagation).

Например, при сложении достоверных данных с помеченными рез��льтат становится помеченным.

int taintedData;
scanf("%d", &taintedData);

int res = 5 + taintedData; // res now is tainted data too
....

// The same thing happens when using 
// tainted data in a loop condition
int taintedData;
scanf("%d", &taintedData);

for (int i = 0; i < taintedData; i++)
{
  //The value of i is in range [0; taintedData]
  //as a top bound of the range is tainted
  //the variable derived taint status too
}

Идём дальше и подходим к концу жизненного цикла помеченных данных — к приёмникам.

Приёмники потенциально помеченных данных (taint sink, сток) — это функции или операции, чувствительные к достоверности аргументов/операндов. Такими стоками, например, являются функции, выделяющие память, операция деления на ноль и оператор индексирования.

template <typename T, size_t size>
const auto &getElement(const std::array<T, size> &arr, size_t index)
{
  return arr[index]; // taint-sink operation
}

int main()
{
  size_t index;
  scanf("%zu", &index);

  std::array arr { 1, 2, 3, 4, 5 };
  return getElement(arr, index);
}

А с помощью аннотации taint_sink можно определить пользовательскую функцию-сток:

{
  ....
  "annotations": [
    {
      {
        "type": "function",
        "name": "DoSomethingWithData",
        "params": [ { "type": "std::string &str",
                      "attributes": [ "taint_sink" ] }] // <=
      }
    }
  ]
}

Казалось бы, при чём здесь контракты?

В С++26 в язык будут добавлены контракты. Да, они предназначены для обнаружения ошибок на этапе выполнения, но и статическому анализу они будут весьма полезны. Дело в том, что очень многие функции уже сейчас обладают неявными контрактами. Например, операция деления предполагает, что делитель не может быть равен нулю.

С помощью нового синтаксиса можно явно определить контракт функции (Function contract specifiers). Такие условия описываются в объявлении функции и доступны даже без её тела, что даёт возможность статическому анализатору сопоставлять предикаты с виртуальными значениями аргументов и выявлять ошибки.

Функция-сток, по сути, обладает контрактом, накладывая его на аргументы. Например, так будет выглядеть функция getElement с добавлением контрактов:

template <typename T, size_t size>
const auto &getElement(const std::array<T, size> &arr, size_t index)
  pre(index < std::size(arr))
{
  return arr[index];
}

Однако интересно то, что аналогичный неявный контракт имеет и сам operator[], т.е. при доступе к массиву индекс проверяется на соответствие контракту, и в случае его нарушения анализатор выдаёт предупреждение. Подобным образом анализатор может определять неявные контракты функций во время межпроцедурного анализа, основываясь на их содержании. Например, если аргументы функции внутри её тела передаются в функцию-сток, то контракт этого стока будет применён к функции-обёртке, и у диагностических правила появится больше информации для работы.

Разобравшись с условиями, при которых анализатор генерирует предупреждения при взаимодействии со стоками, перейдём к вопросу верификации данных. Очевидно, что для исправления ошибок при использовании помеченных данных их нужно каким-то способом проверить. Но как определить, что данные прошли верификацию и перестали быть потенциально помеченными? В случае с пользовательскими аннотациями это элементарно: данные, прошедшие через функцию, определённую пользователем как санитайзер, считаются достоверными. Но что, если пользовательских аннотаций нет? Неужели только и остается, что ориентироваться на "validate" и "check" в именах функций?

Верификация

Как мы определили выше, помеченными считаются данные, полученные извне и не прошедшие достаточной проверки.

И тут можно задаться вопросом: "А что значит "достаточная проверка"?"

Это хороший вопрос. Верификация является самой интересной частью taint-анализа. Именно этот этап описывают правила проверки помеченных данных.

Существуют разные способы проверки потенциально помеченных данных. В зависимости от типа для проверки можно использовать:

регулярные выражения. Строки можно проверять, сопоставляя с паттернами регулярных выражений;
экранирование. Замена управляющих последовательностей в потенциально помеченном тексте предотвращает выполнение вредоносного кода. Такой метод применяется при работе с SQL-инъекциями;
приведение типов. Способ проверки, применяемый к числовым данным. Включает в себя проверку диапазона допустимых значений, точности значений;
белый список. Сопоставление введённых данных с белым списком допустимых вариантов значений.

Но как удостовериться, что проверка будет исчерпывающей? Рассмотрим пример:

int getElement(int array[5], int index)
{
  scanf("%d", &index);

  if (index >= 0)
  {
    return array[index];
  }
  
  return 0;
}

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

Предупреждение PVS-Studio: V557 Array underrun/overrun is possible. The 'index' index is from potentially tainted source.

Попробуем выполнить более точную проверку:

int getElement(int array[5], int index)
{
  scanf("%d", &index);

  if (index >= 0 && index < 6)
  {
    return array[index];
  }
  
  return 0;
}

На этот раз мы проверили обе границы диапазона индекса, введённого пользователем, но проверили неправильно, поэтому использование его в operator[] всё равно может привести к выходу за границу массива. Это все ещё ошибка, вызванная помеченными данными? Или уже нет?

Предупреждение PVS-Studio: V557 Array overrun is possible. The value of 'index' index could reach 5.

Анализатор PVS-Studio предупредит об ошибке, однако на этот раз данные уже будут считаться достоверными, поскольку пользователь проверил обе границы.

Даже внутри нашей команды мнения насчёт проверки taint-данных разделились. Некоторые считают, что проверки двух границ для целочисленных данных достаточно, и в этом примере выход за границу массива уже никак с потенциально помеченными данными не связан. Однако есть и противоположное мнение: несмотря на проверку, пользовательский ввод все ещё может спровоцировать ошибку, а значит, и предупреждение о потенциально помеченных данных здесь уместно.

А что вы думаете об этом примере? Когда помеченные данные перестают быть таковыми?

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

Помимо ориентированности taint-анализа на поиск потенциальных уязвимостей, связанных с высокоуровневым кодом (SQL-инъекции, XXE, XEE и т.д.), существует также необходимость применять его и на гораздо более низком уровне. Например, в операциях индексирования, деления на ноль, выделении памяти и т.д. Поэтому taint-анализ востребован даже в условиях отсутствия пользовательских аннотаций.

В такой ситуации можно рассчитывать на оставшиеся два метода верификации: приведение типов и сопоставление с "белым" списком допустимых значений. Например, можно считать достоверными переменные, проверенные функциями equal или contains.

Как мы уже успели выяснить, проверку обеих границ диапазона для знаковых чисел и верхней границы для беззнаковых PVS-Studio считает верификацией. Например, внутри блока if при таком условии мы получим достоверный диапазон значений переменной:

int array[16] { };
int index;
scanf("%d", &index);

if (index > 0 && index < 16)
{
  // index = [1; 15] inside the if statement
  return array[index];
}

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

int array[16] { };
int index;
scanf("%d", &index);

int trustedValue1 = index & 0xf; // trustedValue1 = [0; 15]
array[trustedValue1] = 0;

int trustedValue2 = index % 16;  // trustedValue2 = [0; 15]
array[trustedValue2] = 0;

Пока PVS-Studio не поддерживает аннотаций для функций-санитайзеров, однако в ближайшее вр��мя планируется реализовать этот функционал.

Ну и в заключение

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

Для увеличения эффективности пользователь может применять аннотации в формате JSON, добавляя свои собственные источники и стоки помеченных данных. В любом случае, PVS-Studio может предложить базовый taint-анализ даже в отсутствие пользовательских аннотаций. А с приходом контрактов в C++26 качество анализа вырастет ещё сильнее.

Если вы хотите попробовать анализ помеченных данных самостоятельно, приглашаем вас воспользоваться бесплатной 30-дневной версией анализатора PVS-Studio.

Taint-анализ в C и C++ анализаторе PVS-Studio