A Unicorn Seeking Extraterrestrial Life: Analyzing SETI@home's Source Code

• More about the project
• Analysis results
  • A warm-up
  • Pointers and memory handling
  • Loops
  • Other suspicious fragments
• What else did I find?
• Conclusion

Two possibilities exist: Either we are alone in the Universe or we are not. Both are equally terrifying. (c) Arthur Charles Clarke.

Debates on whether or not we are alone in the Universe have been exciting our minds for many decades. This question is approached seriously by the SETI program whose mission is to search for extraterrestrial civilizations and ways to contact them. It is the analysis of one of this program's projects, SETI@home, that we are going to talk about in this article.

More about the project

SETI@home is an Internet-based public volunteer computing project whose purpose is to analyze radio signals, searching for signs of extraterrestrial intelligence. The project employs an open-source software platform for distributed computations, BOINC, written in C++.

To carry out the analysis, I used PVS-Studio, a static analyzer for C/C++ code. The SETI@home project's source files are available for download at the official site. The guide on how to build the project can be also found there. So, having prepared all I needed for the analysis and having made me a cup of coffee, I set about to work.

Analysis results

Honestly, before I started the analysis, I had anticipated finding a pile of issues in the project. But, surprising as it may be, the analyzer found quite few really interesting errors and defects there, which indicates the high quality of the code.

Nevertheless, there are still a few suspicious fragments I'd like to discuss in this article.

A warm-up

The code samples in this section can't be put into any particular single category such as, say, "pointers" or "loops" because they refer to different patterns, and yet each of them is interesting in itself.

So here we go:

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;
  ....
}

PVS-Studio's diagnostic message: V560 A part of conditional expression is always true: 0xff. seti_header.cpp 96

What the analyzer doesn't like is the '&&' operator used to get an integer value. Perhaps in this case, it is the '&' operator that should have been used instead because the 'splitter_version' variable will otherwise take one of the two values, 0 or 1, all the time.

Of course, there is some probability that the programmer did mean adding 0 or 1 to 'splitter_version', but I'm sure you, too, don't believe it's really so. After all, the programmer could have implemented it in a more comprehensive way (for example by using a ternary operator) if it was the case.

The next suspicious code fragment deals with methods that are meant to return a value but for some reason don't do that. Moreover, their bodies are empty. Such code fragments look odd, to say the least. Take a look yourself:

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

PVS-Studio's diagnostic messages:

• 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

As you can see from this fragment, none of the methods returns anything. I had deliberately singled out this code fragment and was very astonished on finding that it had compiled successfully. The compiler didn't generate any warnings either. But it runs smoothly only until those methods are called. When it happens, a compilation error pops up.

What is it - a rough draft to be completed in the future or a bug? I'm not sure because there are no comments regarding this in the code. Just keep in mind what I have told and shown you.

But let's go on.

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=")]));
  ....
}

PVS-Studio's diagnostic message: V593 Consider reviewing the expression of the 'A = B != C' kind. The expression is calculated as following: 'A = (B != C)'. xml_util.h 891

During the parsing of input data, a length value was to be calculated (the variable 'length').

What did the programmer really mean by that? That line contains a search for the "length=" substring, and if it is found, the substring beginning index is written into the 'len' variable. After that, the original line is converted into a C-string from where the necessary length value is extracted by the indexing operator. It is the index of the "length=" substring and its length which are used to calculate the index of the character storing the length value.

However, because of the operation precedence (or incorrectly put parentheses in the condition which are duplicated), it all will go wrong. First, the comparison to the 'npos' value will be executed, and then the result of this comparison (0 or 1) will be saved into the 'len' variable, which will result in incorrect calculation of the array index.

While examining the analysis log, I came across a couple of interesting macros. Here they are:

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

PVS-Studio's diagnostic message: V606 Ownerless token '0'. analyzefuncs.cpp 212

Notice that this macro was found more than once throughout the entire code. Why not simply throw an exception, I wonder? Instead of that, the programmer preferred to use a strange lexeme and a loop with only one iteration. That's an interesting approach, but what's the point inventing that 'bicycle'?

Pointers and memory handling

Here's a code sample with pointers, just for a change. You are generally much more likely to get into a trap when working with code where pointers or addresses are handled. That's why we are especially interested in them.

size_t GenChirpFftPairs(....) 
{
  ....
  double * ChirpSteps;
  ....
  ChirpSteps = (double *)calloc(swi.num_fft_lengths, sizeof(double));
  ....
  CRate+=ChirpSteps[j];
  ....
  if (ChirpSteps) free (ChirpSteps);
  ....
}

PVS-Studio's diagnostic message: V595 The 'ChirpSteps' pointer was utilized before it was verified against nullptr. Check lines: 138, 166. chirpfft.cpp 138

The analyzer warns us that a pointer is used before being checked for null. If memory fails to be allocated and the 'calloc' function returns 'NULL', null pointer dereferencing will occur, which, as we all know, is no good thing.

Another trouble about it is that the 'free' function is only called when the pointer is not 'NULL'. This check is superfluous since the 'free' function can easily handle null pointers.

Here's another code sample where the 'memset' function is used in an odd way:

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;
    ....
  }
  ....
}

PVS-Studio's diagnostic message: V579 The memset function receives the pointer and its size as arguments. It is possibly a mistake. Inspect the third argument. analyzereport.cpp 271

As you can see, memory for an array is allocated first, after which its items are filled with the value '-1', and then they are being handled. But the trouble is that it's the pointer size, instead of the array size, which is passed into the 'memset' function as a third argument. To correctly fill the array with the necessary characters, it is the buffer size which should have been passed as a third argument.

Loops

In many projects, you can find loops whose bodies are either iterated infinitely or not iterated at all. SETI@home is no exception. On the other hand, the consequences of such bugs don't look that harmful here as in some other projects.

std::string hotpix::update_format() const
{
  std::ostringstream rv("");
  for (int i=2;i<2;i++) 
    rv << "?,";
  rv << "?";
  return rv.str();
}

PVS-Studio's diagnostic message: 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

The error is pretty trivial. As we all know, the body of the 'for' loop keeps iterating as long as its conditional statement holds true. But in this case, the condition will evaluate to false right at the very first iteration, so the loop will be quitted immediately. Personally I can't seem to figure out what the programmer really meant by this, but the fact remains that this loop will never execute.

I found another similar code fragment but in a different method of a different class:

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

And here's a not so transparent, yet a potentially incorrect code sample:

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

PVS-Studio's diagnostic message: 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

Since we are discussing loops, it's not hard to guess that the error has occurred in the 'while' loop termination condition. Many of you, though, may not even notice anything strange because the method used here does look quite standard and legal. However, there is a hidden trap in it, otherwise I wouldn't cite it here.

You see, this check won't be sufficient when a data reading failure occurs. If it happens, the 'eof()' method will be constantly returning 'false' and, as a consequence, we'll get an infinite loop.

To fix the error, we need to add one more condition. Then the loop will look like this:

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

Other suspicious fragments

One should be careful when working with bitwise operations, too. The analysis revealed a code fragment leading to undefined behavior:

int seti_analyze (ANALYSIS_STATE& state) 
{
  ....
  int last_chirp_ind = - 1 << 20, chirprateind;
  ....
}

PVS-Studio's diagnostic message: V610 Undefined behavior. Check the shift operator '<<'. The left operand '-1' is negative. analyzefuncs.cpp 177

As seen from this code, a variable is initialized to a value acquired through a bitwise shift operation. It would be OK, but the left operand is negative, so, under the C++11 standard, this operation causes undefined behavior.

It may cut both ways. On the one hand, code like that has been used for multiple times and for a long time; on the other, the standard still interprets it as leading to undefined behavior.

The final decision is up to the programmer, but I had to mention this issue.

More than once, I came across code fragments where one and the same variable was assigned different values twice on end, without any other operations in between. Here's one of these examples:

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);
  ....
}

PVS-Studio's diagnostic message: V519 The 'retval' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 450, 452. seti.cpp 452

I can't say for sure what was really meant here or how to fix it. But the programmer who wrote this code will probably figure out the reason for handling a variable in a way like that. We can only wonder at and make guesses about this code.

I found four more code fragments like that. Here are the corresponding warnings by the analyzer:

• 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

Maybe these variables were simply used to check the values returned by functions in the debug mode. Then there is nothing dangerous about them and the warnings can be ignored or suppressed through one of the numerous means provided by the PVS-Studio analyzer.

To round off the article, here's an example where the 'strlen' function is used somewhat irrationally:

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);
  }
  ....
}

PVS-Studio's diagnostic message: 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

Since the buffer (the 'buf' variable) is not changed while executing the loop, there's no need to calculate its length at every iteration. It'd probably be more reasonable to create a separate variable for this purpose and compare against it. It doesn't affect the performance that strongly when dealing with smaller buffers, but with larger ones, with a larger number of iterations, it's quite more prominent.

There was more than one instance of this issue. Here are a few more:

• 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

What else did I find?

There had been some other warnings generated by the analyzer, but those were the code fragments I didn't find interesting enough to discuss here. Just read this section through for details.

For example, there were "hanging" arrays, declared yet not used in any way. At least they were of a fixed and small size. However, they were still consuming some stack memory, which didn't look reasonable.

There were also a few instances of pointer dereferencing with a subsequent increment (*p++). At the same time, the value stored in the pointer was not used in any way. The corresponding examples suggested that the programmer had really wanted to simply change the size of the pointer itself, but for some reason also dereferenced it. These are potential errors, for in some of the cases, it may be needed to change the value stored in a pointer, not the pointer itself. So don't disregard such warnings.

More than once, I encountered 'fprintf' functions whose format string didn't correspond to the actual arguments passed into it. Such issues result in undefined behavior and may, for example, cause printing of some rubbish.

Conclusion

The check left me with a somewhat ambiguous feeling. On the one hand, I was a bit upset about finding much fewer bugs than expected, which meant picking lesser material for the article. On the other hand, I finally analyzed that project and it had been an interesting experience. After all, the small number of bugs indicates the high code quality, which is cool.

What to add here? Install the SETI@home client: contribute what you can to the search for extraterrestrial intelligence; and install PVS-Studio: it will help you in your search for bugs in C/C++ source code.