...

суббота, 30 мая 2015 г.

Единорог в поисках внеземного разума: анализ кода SETI@home

Существует две возможности: либо мы одиноки во Вселенной, либо нет. Обе одинаково ужасны. (с) Артур Чарльз Кларк

Дискуссии о том, одиноки ли мы во Вселенной, будоражат умы людей уже не один десяток лет. Серьёзное отношение к этому вопросу имеет проект SETI, занимающийся поиском внеземных цивилизаций и возможностью вступления с ними в контакт. Об анализе исходного кода одного из проектов этой программы — SETI@home — и пойдёт речь в данной статье.

Подробнее о проекте


SETI@home — научный некоммерческий проект добровольных вычислений, использующий свободные ресурсы на компьютерах добровольцев для поиска радиосигналов внеземных цивилизаций. Проект основан на открытой программной платформе для организации распределённых вычислений — BOINC, написанной на C++.

В качестве инструмента анализа использовался статический анализатор C/C++ кода — PVS-Studio. Исходные коды проекта SETI@home доступны на официальном сайте. Инструкцию о том, как собирать проект, найти также не сложно, так что, собрав всё необходимое и приготовив чашечку кофе, я приступил к делу.

Результаты проверки


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

Тем не менее, подозрительные места были, и некоторые из них я бы хотел рассмотреть.

Для разогрева


Примеры кода в этом разделе нельзя подвести под какую-то одну категорию, как например «указатели» или «циклы», так они имеют разную тематику, но по-своему интересны.

Поэтому предлагаю перейти ближе к делу:

struct SETI_WU_INFO : public track_mem<SETI_WU_INFO> 
{
  ....
  int splitter_version;
  ....
};
SETI_WU_INFO::SETI_WU_INFO(const workunit &w):....
{
  .... 
  splitter_version=(int)floor(w.group_info->
    splitter_cfg->version)*0x100;  
  splitter_version+=(int)((w.group_info->splitter_cfg->version)*0x100)  
    && 0xff;
  ....
}

Предупреждение анализатора: V560 A part of conditional expression is always true: 0xff. seti_header.cpp 96

Подозрительным выглядит оператор '&&', который используется для получения целочисленного значения. Возможно, в данном случае был необходим оператор '&', так как иначе переменная 'splitter_version' всегда будет принимать одно из двух значений: 0 или 1.

Конечно, вероятность того, что подразумевалась прибавка к 'splitter_version' 0 или 1 есть, но, думаю, вы согласитесь, что она не очень велика, и в таком случае можно было использовать более понятный код (например, тернарный оператор).

Следующий подозрительный фрагмент кода — методы, которые должны возвращать значение, но, тем не менее, ничего не возвращают. Более того — они имеют пустые тела. Такой код как минимум выглядит подозрительно. Предлагаю взглянуть самим:

struct float4 
{
  ....
  inline float4 rsqrt() const {
  }
  inline float4 sqrt() const {
  }
  inline float4 recip() const {
  }
  ....
};

Предупреждения анализатора:
  • V591 Non-void function should return a value. x86_float4.h 237
  • V591 Non-void function should return a value. x86_float4.h 239
  • V591 Non-void function should return a value. x86_float4.h 241
Как видно из этого фрагмента, ни один из методов ничего не возвращает. Я специально выписал отдельно данный участок кода, и был несколько удивлён, увидев, что компиляция проходит успешно. Никаких предупреждений компилятора также не было. Но только до тех пор, пока данные методы не будут вызваны. При попытке сделать это всё же возникает ошибка компиляции.

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

Но не будем зацикливаться на этом примере, лучше взглянем, что ещё удалось найти.

template <typename T>
std::vector<T> xml_decode_field(const std::string &input, ....) 
{
  ....
  std::string::size_type start,endt,enc,len;
  ....
  if ((len=input.find("length=",start)!=std::string::npos))
    length=atoi(&(input.c_str()[len+strlen("length=")]));
  ....
}

Предупреждение анализатора: V593 Consider reviewing the expression of the 'A = B != C' kind. The expression is calculated as following: 'A = (B != C)'. xml_util.h 891

Как понятно из кода, в ходе парсинга входных данных необходимо было получить значение длины (переменная 'length').

Что подразумевалось? В строке осуществляется поиск подстроки «length=», если она обнаружена, индекс начала подстроки записывается в переменную 'len'. После этого исходная строка преобразуется в C-строку, из которой при помощи оператора индексации извлекается необходимое значение длины. В качестве вычисления индекса символа, хранящего значение длины, как раз используется индекс подстроки «length=» и её длина.

Однако из-за приоритета операций (или неправильно расставленных скобок в условии, видно, что они дублируются) всё пойдёт не так. Сначала будет выполнено сравнение со значением 'npos', а результат этого сравнения (0 или 1) будет записан в переменную 'len', что приведёт к неправильному вычислению индекса массива.

В ходе просмотра лога анализа я наткнулся на парочку интересных макросов. Предлагаю взглянуть и вам:

#define FORCE_FRAME_POINTER (0)
#define SETIERROR( err, errmsg ) do { \
        FORCE_FRAME_POINTER; \
  throw seti_error( err, __FILE__, __LINE__, errmsg  ); \
} while (0)

Предупреждение анализатора: V606 Ownerless token '0'. analyzefuncs.cpp 212

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

Указатели и работа с памятью


Для разнообразия — пример кода с указателями. Как правило, во фрагментах кода, содержащих работу с указателями или адресами, вероятность наступить на грабли порядком возрастает. Поэтому они вызывают больший интерес.
size_t GenChirpFftPairs(....) 
{
  ....
  double * ChirpSteps;
  ....
  ChirpSteps = (double *)calloc(swi.num_fft_lengths, sizeof(double));
  ....
  CRate+=ChirpSteps[j];
  ....
  if (ChirpSteps) free (ChirpSteps);
  ....
}

Предупреждение анализатора: V595 The 'ChirpSteps' pointer was utilized before it was verified against nullptr. Check lines: 138, 166. chirpfft.cpp 138

Анализатор предупреждает о том, что указатель используется до того, как выполняется проверка, на то, является ли он нулевым. Если не удастся выделить память и функция 'calloc' вернёт значение 'NULL', будет выполнено разыменовывание нулевого указателя, что, как все мы прекрасно знаем, не очень хорошо.

Другой момент заключается в том, что функция 'free' вызывается только в том случае, если указатель не равен 'NULL'. Эта проверка избыточна, так как функция 'free' без проблем обрабатывает нулевые указатели.

Другой участок кода с подозрительным использованием функции 'memset'. Давайте посмотрим:

int ReportTripletEvent(....)
{
  ....
  static int * inv;
  if (!inv) 
    inv = (int*)calloc_a(swi.analysis_cfg.triplet_pot_length, 
      sizeof(int), MEM_ALIGN);
  memset(inv, -1, sizeof(inv));
  for (i=0;i<swi.analysis_cfg.triplet_pot_length;i++) 
  {
    j = (i*pot_len)/swi.analysis_cfg.triplet_pot_length;
    if (inv[j] < 0) 
      inv[j] = i;
    ....
  }
  ....
}

Предупреждение анализатора: V579 The memset function receives the pointer and its size as arguments. It is possibly a mistake. Inspect the third argument. analyzereport.cpp 271

Из данного фрагмента кода видно, что сначала выделяется память под массив, после чего его элементы заполняются значением '-1', а после с ними происходит работа. Но вот в функцию 'memset' третьим параметром передаётся не размер массива, а размер указателя. Для правильного заполнения массива необходимыми символами третьим аргументом следовало передавать размер буфера.

Циклы


Во многих проектах встречаются циклы, тело которых либо выполняется бесконечно, либо не выполняется вообще. SETI@home не стал исключением. С другой стороны — здесь последствия не выглядят такими критичными, как в некоторых других проектах.
std::string hotpix::update_format() const
{
  std::ostringstream rv("");
  for (int i=2;i<2;i++) 
    rv << "?,";
  rv << "?";
  return rv.str();
}

Предупреждение анализатора: V621 Consider inspecting the 'for' operator. It's possible that the loop will be executed incorrectly or won't be executed at all. schema_master.cpp 9535

Ошибка весьма тривиальна. Как все мы знаем, тело цикла 'for' выполняется, пока его условное выражение истинно. Здесь же уже на первой итерации условие будет ложным, так что сразу будет осуществлён выход из цикла. Лично я не могу понять, что здесь подразумевалось, но тем не менее тело этого цикла никогда не будет выполняться.

Аналогичный фрагмент кода встретился ещё раз, но в другом методе другого класса:

V621 Consider inspecting the 'for' operator. It's possible that the loop will be executed incorrectly or won't be executed at all. schema_master.cpp 11633

Не столь прозрачный, но потенциально ошибочный пример:

template <typename T>
std::istream &operator >>(std::istream &i, sqlblob<T> &b) 
{
  ....
  while (!i.eof()) 
  {
    i >> tmp;
    buf+=(tmp+' ');
  }
  ....
}

Предупреждение анализатора: V663 Infinite loop is possible. The 'cin.eof()' condition is insufficient to break from the loop. Consider adding the 'cin.fail()' function call to the conditional expression. sqlblob.h 58

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

Дело в том, что при возникновении сбоя чтения данных такой проверки будет недостаточно. В таком случае метод 'eof()' будет постоянно возвращать 'false', как следствие — бесконечный цикл.

Для исправления ошибки необходимо добавить дополнительное условие. Тогда цикл будет выглядеть следующим образом:

while(!i.eof() && !i.fail())
{
  //do something
}

Прочие подозрительные места


Аккуратными нужно быть и с битовыми операциями. В ходе анализа встретился участок кода, приводящий к неопределённому поведению:
int seti_analyze (ANALYSIS_STATE& state) 
{
  ....
  int last_chirp_ind = - 1 << 20, chirprateind;
  ....
}

Предупреждение анализатора: V610 Undefined behavior. Check the shift operator '

Как видно из кода, переменная инициализируется значением, полученным в результате битового сдвига. И всё бы ничего, но левый операнд отрицателен, а согласно стандарту C++11, эта операция приводит к неопределённому поведению.

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

Окончательное решение остаётся за программистом, но обратить внимание на это стоит.

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

int checkpoint(BOOLEAN force_checkpoint) 
{
  int retval=0, i, l=xml_indent_level;
  ....
  retval = (int)state_file.write(str.c_str(), str.size(), 1);
  // ancillary data
  retval = state_file.printf(
    "<bs_score>%f</bs_score>\n"
    "<bs_bin>%d</bs_bin>\n"
    "<bs_fft_ind>%d</bs_fft_ind>\n",
    best_spike->score,
    best_spike->bin,
    best_spike->fft_ind);
  ....
}

Предупреждение анализатора: V519 The 'retval' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 450, 452. seti.cpp 452

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

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

  • V519 The 'retval' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 470, 472. seti.cpp 472
  • V519 The 'retval' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 490, 492. seti.cpp 492
  • V519 The 'retval' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 513, 515. seti.cpp 515
  • V519 The 'retval' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 533, 536. seti.cpp 536
  • V519 The 'lReturnValue' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 85, 97. win_util.cpp 97

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

Напоследок приведу пример, где несколько нерационально используется функция 'strlen':

int parse_state_file(ANALYSIS_STATE& as) 
{
  ....
  while(fgets(p, sizeof(buf)-(int)strlen(buf), state_file)) 
  {
    if (xml_match_tag(buf, "</bt_pot_min")) 
      break;
    p += strlen(p);
  }
  ....
}

Предупреждение анализатора: V814 Decreased performance. Calls to the 'strlen' function have being made multiple times when a condition for the loop's continuation was calculated. seti.cpp 770

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

Данный код встречался неоднократно, вот ещё несколько подобных сообщений:

  • V814 Decreased performance. Calls to the 'strlen' function have being made multiple times when a condition for the loop's continuation was calculated. seti.cpp 784
  • V814 Decreased performance. The 'strlen' function was called multiple times inside the body of a loop. xml_util.cpp 663
  • V814 Decreased performance. The 'strlen' function was called multiple times inside the body of a loop. xml_util.cpp 686

Что ещё удалось найти?


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

Например, попадались «висящие» массивы, которые объявляются, но никак не используются. Благо, что размер их был фиксированным и небольшим. Тем не менее, стековая память под них выделялась, что нецелесообразно.

Также несколько раз встречалось разыменовывание указателя с последующим его увеличением (*p++). При этом значение, хранящееся в указателе, никак не использовалось. Из примеров было видно, что подразумевалось просто изменение самого указателя, но всё же его зачем-то разыменовывали. Данный код потенциально ошибочен, так как порой может подразумеваться изменение значения, хранящегося в указателе, а не его самого. Поэтому относиться с недоверием к этим предупреждениям не стоит.

Неоднократно встречалась функция 'fprintf', форматная строка которой не соответствовала передаваемым в функцию фактическим аргументам. Это приводит к неопределённому поведению и может служить причиной, например, вывода на экран бессмыслицы.

Заключение


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

Что ещё добавить? Устанавливайте клиент SETI@home — помогайте в поиске внеземных цивилизаций, устанавливайте PVS-Studio — он поможет вам в поиске ошибок в исходных кодах, написанных на C/C++.

Эта статья на английском


Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Sergey Vasiliev. A Unicorn Seeking Extraterrestrial Life: Analyzing SETI@home's Source Code.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Комментариев нет:

Отправить комментарий