Accord.Net: we are looking for an error in the code, because of which machines will enslave humanity / PVS-Studio Blog

Articles about checking open source projects are a good thing. Someone, including developers, will find out about the errors contained in the project, someone will learn about the static analysis methodology and begin to use it to improve the quality of their code. For us, this is a great way to popularize the PVS-Studio analyzer, and at the same time the possibility of additional testing. This time I checked the Accord.Net platform and found a lot of interesting snippets in the code.

About the project and the analyzer

Accord.Net is a .Net -based machine learning platform written in C #. The platform consists of several libraries covering a wide range of tasks, such as static data processing, machine learning, pattern recognition, etc. The source code of the project is available in the repository on GitHub .



To check the project, we used the PVS-Studio static code analyzer, which is available for download by link . In addition, you can read other articles about checking open source projects or the " error database " in which we collect bugs we found.

A bit about warnings

The analyzer issued 91 first level warning and 141 second level warning. 109 of these warnings have been described or mentioned in the article. A quick glance at the remaining warnings, I would have attributed another 23 errors to the errors, but they are not given in the article, since they seemed insufficiently interesting or were similar to those already described. It is already more difficult to judge the remaining warnings of the analyzer - you need to carefully understand and analyze the code. As a result, at least 132 of 232 warnings I would attribute to errors. This suggests that the number of false positives of the analyzer is approximately 46%. Well, no, wait ... This tells us that every second analyzer warning is an error in the code! In my opinion, this is a fairly strong argument for the need to use static analysis tools. About, how to use static analyzers correctly and incorrectly, is written at the end of the article. In the meantime, I propose to see what interesting could be found in the source code.

Found bugs

Identical subexpressions It is easy enough to make a

mistake caught by the diagnostic message V3001 , especially if you use copy-paste, or if the names of the variables used in the expression are similar. These errors are one of the most common, and this project could not have done without them. Try to find the error in the snippet below without looking at the analyzer warning.

public Blob[] GetObjects(UnmanagedImage image, 
                         bool extractInOriginalSize)
{
  ....
  if ((image.PixelFormat != PixelFormat.Format24bppRgb)    &&
      (image.PixelFormat != PixelFormat.Format8bppIndexed) &&
      (image.PixelFormat != PixelFormat.Format32bppRgb)    &&
      (image.PixelFormat != PixelFormat.Format32bppArgb)   &&
      (image.PixelFormat != PixelFormat.Format32bppRgb)    &&
      (image.PixelFormat != PixelFormat.Format32bppPArgb)
      )
  ....
}

PVS-Studio Warning : V3001 There are identical sub-expressions 'image.PixelFormat! = PixelFormat.Format32bppRgb' to the left and to the right of the '&&' operator. Accord.Imaging BlobCounterBase.cs 670

Here the image.PixelFormat! = PixelFormat.Format32bppRgb subexpression is repeated two times . It was quite simple to make a mistake with such names of enumeration elements, which happened. It is worth noting that, looking at such code, it is very easy to miss the extra subexpression. But whether one of the comparisons is superfluous, or if the enumeration was meant differently, is an interesting question. In one case, there will simply be redundant code, and in the other, a logical error.

This code is found again in the same file on line 833. Copy-paste ... Copy-paste never changes.

An erroneous condition for exiting a cycle.

We are all used to calling cycle counters by names like i , j , k , etc. As a rule, this is convenient and is a common practice, but sometimes it can stand sideways. As in the example below.

public static void Convert(float[][] from, short[][] to)
{
  for (int i = 0; i < from.Length; i++)
    for (int j = 0; i < from[0].Length; j++)
      to[i][j] = (short)(from[i][j] * (32767f));
}

PVS-Studio Warning: V3015 It is likely that a wrong variable is being compared inside the 'for' operator. Consider reviewing 'i' Accord.Audio SampleConverter.cs 611

The i variable is used to exit the second loop , although j is the counter for this loop . In this case, the variable i inside the body of the nested loop does not change. As a result, j will be incremented until it goes beyond the bounds of the array and an exception is thrown.

Different logic for the same conditions. A

code was encountered when different logic was provided for two identical if statements .

public void Fit(double[][] observations, 
                double[] weights, 
                MultivariateEmpiricalOptions options)
{
  if (weights != null)
    throw new ArgumentException("This distribution does not support  
                                 weighted  samples.", "weights");
  ....
  if (weights != null)
      weights = inPlace ? weights : (double[])weights.Clone();
  ....
}

PVS-Studio Warning: V3021 There are two 'if' statements with identical conditional expressions. The first 'if' statement contains method return. This means that the second 'if' statement is senseless Accord.Statistics MultivariateEmpiricalDistribution.cs 653

Strange code, right? Especially when you consider the fact that the variable weights is a parameter of the method and is not used in any way between these conditions. Thus, the second if statement will never be executed, because if the expression weights! = Null is true, an exception of type ArgumentException will be thrown .

This code is found again in the same file on line 687.

Conditions whose values ​​are always false

Diagnostic rule V3022 is very prettier from the first release and never ceases to amaze me. Let's see if it can surprise you either. To begin, I propose to find an error in the code without resorting to the analyzer with a diagnostic message. At the same time, I draw attention to the fact that this is already a simplified version, with cut out code fragments.

private static void dscal(int n, double da, double[] dx, 
                          int _dx_offset, int incx)
{
  ....
  if (((n <= 0) || (incx <= 0)))
  {
    return;
  }
  ....
  int _i_inc = incx;
  for (i = 1; (_i_inc < 0) ? i >= nincx : i <= nincx; i += _i_inc)
  ....
}

PVS-Studio warning : V3022 Expression '(_i_inc <0)' is always false. Accord.Math BoundedBroydenFletcherGoldfarbShanno.FORTRAN.cs 5222

Of course, now it’s easier to find the error, because fragments that were not interesting to us were specially cut from the method. And yet it’s hard to say right away where in this code the problem is. But the fact is (as you might have guessed by reading the analyzer message) that the expression (_i_inc <0) is always false. It should be noted here that the _i_inc variable is initialized to the value of the incx variable . At the same time, the value of the incx variable at the time of _i_inc initializationpositively, since otherwise it would have been possible to exit the method body higher in the code. Therefore, _i_inc can only have a positive value, the result of the comparison _i_inc <0 is always false , and the expression i <= nincx will always be the condition for exiting the loop .

Such in-depth analysis became available thanks to the virtual value mechanism , which greatly improved some of the analyzer's diagnostic rules.

private void hqr2()
{
  ....
  int low = 0;
  ....
  for (int i = 0; i < nn; i++)
  {
      if (i < low | i > high)
        ....
  }
  ....
}

PVS-Studio Warning: V3063 A part of conditional expression is always false: i <low. Accord.Math JaggedEigenvalueDecompositionF.cs 571 The

subexpression i <low will always be false , since the minimum value accepted by the variable i is 0, and the low value at the time of comparison will also always be 0. Therefore, the subexpression i <low will be calculated “idle” ".

There are many such places. I will not give all warnings, but I will list a few:

• V3063 A part of conditional expression is always false: i <low. Accord.Math JaggedEigenvalueDecompositionF.cs 972
• V3063 A part of conditional expression is always false: i <low. Accord.Math JaggedEigenvalueDecomposition.cs 571
• V3063 A part of conditional expression is always false: i <low. Accord.Math JaggedEigenvalueDecomposition.cs 972
• V3063 A part of conditional expression is always false: i <low. Accord.Math EigenvalueDecomposition.cs 567

Integer division with conversion to real type.

The analyzer found suspicious mathematical calculations in the code. It is enough just to forget that when dividing integers, integer division is performed. If material division was intended, an unpleasant and elusive error could occur. In some cases, it can be difficult for a third-party developer to say whether the expression contains an error, but it is worth checking such operations. I propose to consider several such cases.

public static double GetSpectralResolution(int samplingRate, 
                                           int samples)
{
  return samplingRate / samples;
}

PVS-Studio Warning: V3041 The expression was implicitly cast from 'int' type to 'double' type. Consider utilizing an explicit type cast to avoid the loss of a fractional part. An example: double A = (double) (X) / Y ;. Accord.Audio Tools.cs 158

This method divides two integer variables, however, the result of this division is implicitly cast to double . It looks suspicious.



But the following code looks even stranger:

public static int GreatestCommonDivisor(int a, int b)
{
  int x = a - b * (int)Math.Floor((double)(a / b));
  while (x != 0)
  {
    a = b;
    b = x;
    x = a - b * (int)Math.Floor((double)(a / b));
  }
  return b;    
}

PVS-Studio warnings:

• V3041 The expression was implicitly cast from 'int' type to 'double' type. Consider utilizing an explicit type cast to avoid the loss of a fractional part. An example: double A = (double) (X) / Y ;. Accord.Math Tools.cs 137
• V3041 The expression was implicitly cast from 'int' type to 'double' type. Consider utilizing an explicit type cast to avoid the loss of a fractional part. An example: double A = (double) (X) / Y ;. Accord.Math Tools.cs 142

The analyzer seemed suspicious expression (double) (a / b) . The Floor method returns the largest integer less than or equal to the specified double-precision floating-point number ( MSDN. Math.Floor ). But the variables a and b are of type int , therefore - integer division will be performed, the result of which will be an integer value. It turns out that there is no point in explicitly casting this value to double and calling the Floor method .

For the correct operation, it was necessary to cast to type doubleone of the operands. Then real division would be performed, and a call to the Floor method would be justified:

Math.Floor((double)a / b)

Method parameter, the value of which is always overwritten

Continue. Errors of the following type are not common, but still come across.

private static double WeightedMode(double[] observations, 
                                   double[] weights, 
                                   double mode, 
                                   int imax, 
                                   int imin)
{
  ....
  var bestValue = currentValue;
  ....
  mode = bestValue;
  return mode;
}

PVS-Studio Warning: V3061 Parameter 'mode' is always rewritten in method body before being used. Accord.Statistics TriangularDistribution.cs 646

One of the method parameters - mode - is overwritten and returned. At the same time, mode is not used in any way in the body of the method (apart from overwriting). I will not venture to say that this is a mistake (among the suspicious places found by this diagnostic rule in other projects, errors were clearly visible), but this code looks strange.

In general, there is an interesting feature: as a rule, errors in this project do not occur singly. Exactly the same code can be found in several places. Indeed copy-paste does not change ...

• V3061 Parameter 'mode' is always rewritten in method body before being used. Accord.Statistics TriangularDistribution.cs 678
• V3061 Parameter 'mode' is always rewritten in method body before being used. Accord.Statistics TriangularDistribution.cs 706
• V3061 Parameter 'mode' is always rewritten in method body before being used. Accord.Statistics TriangularDistribution.cs 735

Dereferencing null reference

public override string ToString(string format, 
                                IFormatProvider formatProvider)
{
  ....
  var fmt = components[i] as IFormattable;
  if (fmt != null)
    sb.AppendFormat(fmt.ToString(format, formatProvider));
  else
    sb.AppendFormat(fmt.ToString());
  ....
}

PVS-Studio Warning: V3080 Possible null dereference. Consider inspecting 'fmt'. Accord.Statistics MultivariateMixture'1.cs 697

Typically, errors that result in exceptions are caught during development if the code is tested thoroughly enough. But not always, and the example above is a proof of this. In case the expression fmt! = Null is false, the ToString instance method is called on the fmt object . Result? An exception of type NullReferenceException .

And, as you might have guessed, the same error occurred again: MultivariateMixture'1.cs 697

Mutual link assignment

public class MetropolisHasting : IRandomNumberGenerator
{
  ....        
  T[] current;
  T[] next;
  ....
  public bool TryGenerate()
  {
    ....
    var aux = current;
    current = next;
    next = current;
   ....
  }
  ....
}

Warning PVS-Studio: V3037 An odd sequence of assignments of this kind: A = B; B = A ;. Check lines: 290, 289. Accord.Statistics MetropolisHasting.cs 290

Obviously, in the given fragment of the TryGenerate method, they wanted to swap the links to the next and current arrays (the aux variable is not used anywhere else). But due to an error, it turned out that both current and next now store references to the same array - the one referenced in the next variable .

The correct code should look like this:

var aux = current;
current = next;
next = aux;

Potential division by 0.

The analysis revealed several errors of potential division by 0. A brief look at them:

public BlackmanWindow(double alpha, int length) 
    : base(length)
{
    double a0 = (1.0 - alpha) / 2.0;
    double a1 = 0.5;
    double a2 = alpha / 2.0;
    for (int i = 0; i < length; i++)
        this[i] = (float)(a0 - 
          a1 * Math.Cos((2.0 * System.Math.PI * i) / (length - 1)) +
          a2 * Math.Cos((4.0 * System.Math.PI * i) / (length - 1)));
}

PVS-Studio warnings:

• V3064 Potential division by zero. Consider inspecting denominator '(length - 1)'. Accord.Audio BlackmanWindow.cs 64
• V3064 Potential division by zero. Consider inspecting denominator '(length - 1)'. Accord.Audio BlackmanWindow.cs 65

The analyzer found the following code suspicious:

(2.0 * System.Math.PI * i) / (length - 1)

It is possible that in reality there will not be an error ( length is the length of a window, and for an error to occur, it must have a value of 1), but how do you know? It is better to play it safe, otherwise there is a great chance of getting a very unpleasant mistake, which, moreover, will be difficult to detect.

Another interesting piece of code met with a potential division by 0.

public static double[,] Centering(int size)
{
  if (size < 0)
  {
      throw new ArgumentOutOfRangeException("size", size,
          "The size of the centering matrix must 
           be a positive integer.");
  }
  double[,] C = Matrix.Square(size, -1.0 / size);
  ....
}

Warning PVS-Studio: V3064 Potential division by zero. Consider inspecting denominator 'size'. Accord.Math Matrix.Construction.cs 794

As for me - a very interesting and funny mistake. The analyzer noted that in the expression -1.0 / size it is possible to divide by 0. Now, pay attention to the check above. If size <0 , an exception will be generated, however if size == 0 , there will be no exception, but dividing by 0 will be. At the same time, in the literal passed to the exception constructor, it is written that the size of the matrix must be a positive number, but at the same time it is checked for non-negative values. A positive andnon - negative - yet different concepts. I suppose, to fix the error, it is enough to simply correct the check:

if (size <= 0)

Using a bit operator instead of a logical one

Sometimes one has to face the fact that not all programmers know the difference between bit and logical operators ('|' and '||', '&' and '&&'). This can lead to completely different consequences - from unnecessary calculations to falls. In this project, there were several suspicious places using bit operations:

public JaggedSingularValueDecompositionF(
         Single[][] value,
         bool computeLeftSingularVectors, 
         bool computeRightSingularVectors, 
         bool autoTranspose, 
         bool inPlace)
{
  ....
  if ((k < nct) & (s[k] != 0.0))
  ....
}

Warning PVS-Studio: V3093 The '&' operator evaluates both operands. Perhaps a short-circuit '&&' operator should be used instead. Accord.Math JaggedSingularValueDecompositionF.cs 461

The body of the if statement will be executed if both subexpressions ( k <nct and s [k]! = 0.0 ) are true . But at the same time, even if the value of the first subexpression ( k <nct ) is false , the second subexpression will still be computed, which would not have happened when using the && operator. So, if the programmer checked the value of k so as not to go beyond the boundary of the array, then nothing came of it.

• V3093 The '&' operator evaluates both operands. Perhaps a short-circuit '&&' operator should be used instead. Accord.Math JaggedSingularValueDecompositionF.cs 510
• V3093 The '&' operator evaluates both operands. Perhaps a short-circuit '&&' operator should be used instead. Accord.Math JaggedSingularValueDecompositionF.cs 595
• V3093 The '&' operator evaluates both operands. Perhaps a short-circuit '&&' operator should be used instead. Accord.Math JaggedSingularValueDecomposition.cs 461
• V3093 The '&' operator evaluates both operands. Perhaps a short-circuit '&&' operator should be used instead. Accord.Math JaggedSingularValueDecomposition.cs 510
• V3093 The '&' operator evaluates both operands. Perhaps a short-circuit '&&' operator should be used instead. Accord.Math JaggedSingularValueDecomposition.cs 595
• V3093 The '&' operator evaluates both operands. Perhaps a short-circuit '&&' operator should be used instead. Accord.Math Gamma.cs 296

Checking in the cycle of the same element An

error was found that was found by the diagnostic rule from the latest analyzer release.

public override int[] Compute(double[][] data, double[] weights)
{
  ....
  int cols = data[0].Length;
  for (int i = 0; i < data.Length; i++)
    if (data[0].Length != cols)
      throw new DimensionMismatchException("data", 
                  "The points matrix should be rectangular. 
                   The vector at position {} has a different
                   length than previous ones.");
  ....
}

PVS-Studio Warning: V3102 Suspicious access to element of 'data' object by a constant index inside a loop. Accord.MachineLearning BinarySplit.cs 121

An interesting error. The programmer wanted to verify that the jagged array of data is actually two-dimensional (i.e., it is a matrix). But I made a mistake in the expression data [0]. Length! = Cols , using not an i counter but an integer literal as the index value . As a result, the expression data [0]. Length! = Cols will always be false, since it is equivalent expression data [0] .ength! = data [0] .ength . If the data parameter were a two-dimensional array ( Double [,]), this error, as well as the entire verification, could have been avoided. But it is possible that the use of the gear array is due to some features of the application architecture.

Passing the method as an argument to the caller

The following code fragment also looks suspicious.

public static double WeightedMean(this double[] values, 
                                       double[] weights)
{
  ....
}
public override void Fit(double[] observations, 
                         double[] weights, 
                         IFittingOptions options)
{
  ....
  mean = observations.WeightedMean(observations);
  ....
}

PVS-Studio Warning: V3062 An object 'observations' is used as an argument to its own method. Consider checking the first actual argument of the 'WeightedMean' method. Accord.Statistics InverseGaussianDistribution.cs 325

The analyzer found it suspicious that the WeightedMean method takes the same object as its argument that it is called on. This becomes doubly strange when you consider that WeightedMean is an extension method. I conducted an additional study, looking at how this method is used in other places. In all places of its use, the weights array was used as the second argument (note that such an array also exists in the Fit method under consideration), so most likely this is an error and the correct code should look like this:

mean = observations.WeightedMean(weights);

Potential serialization error A potential serialization

problem has been identified for one of the classes.

public class DenavitHartenbergNodeCollection :  
  Collection
{ .... }
[Serializable]
public class DenavitHartenbergNode
{
  ....
  public DenavitHartenbergNodeCollection Children 
  { 
    get; 
    private set; 
  }
  ....
}

PVS-Studio Warning: V3097 Possible exception: the 'DenavitHartenbergNode' type marked by [Serializable] contains non-serializable members not marked by [NonSerialized]. Accord.Math DenavitHartenbergNode.cs 77

When serializing an instance of the DenavitHartenbergNode class , an exception of type SerializationException may occur . It all depends on the type of serializer you choose. If, for example, an instance of the BinaryFormatter type acts as a serializer, an exception will be thrown, since it is required that all serializable members (and this property is also serializable) be decorated with the [Serializable] attribute .

Some solutions:

• implement this property through a field decorated with the [NonSerialized] attribute . Then the field (and therefore the property associated with it) will not be serialized;
• implement the ISerializable interface , and in the GetObjecData method ignore serialization of this property;
• decorate the DenavitHartenbergNodeCollection type with the [Serializable] attribute .

Judging by the surrounding code (all other properties have serializable types), it is necessary to implement the latter case.

If the instances of this type are serialized using serializers that do not require all serializable members to be decorated with the [Serializable] attribute , you can not worry about this code.

The analyzer detected a lot of unsafe fragments of event calls. How much? 75 warnings to V3083 ! I propose to consider one piece of code, since the rest, in principle, are similar to it.

private void timeUp_Elapsed(object sender, ElapsedEventArgs e)
{
  ....
  if (TempoDetected != null)
    TempoDetected(this, EventArgs.Empty);
}

PVS-Studio Warning: V3083 Unsafe invocation of event 'TempoDetected', NullReferenceException is possible. Consider assigning event to a local variable before invoking it. Accord.Audio Metronome.cs 223

This code fragment checks to see if there are any subscribers to the TempoDetected event , and if there are any, an event is raised. It was assumed that if at the time of verification TempoDetected had no subscribers, this would avoid an exception. However, it is likely that at the time between checking TempoDetected for the inequality nulland by calling the event, it will not have subscribers (for example, in other threads there will be an unsubscription from this event). As a result, if at the time of the event call TempoDetected has no subscribers, an exception of type NullReferenceException will be thrown . You can avoid such problems, for example, using the null-conditional operator '?.', Added in C # 6.0. You can read more about the problem and other ways to solve it in the documentation for this diagnostic rule.

How to and how not to use a static analyzer

Before finishing, I would like to talk a bit about how all the same it is necessary to use the tools of static analysis. Often we have to deal with this approach: “We checked our project before release. Something nothing particularly interesting was found. ” No no no! This is the most incorrect way to use. As a parallel, we can give an example - abandon the development of programs in the IDE, write everything in a simple notebook. And before the release, start working in the IDE. Is it weird? Still would! What is the use of this IDE, if most of the time, when it would have been a good idea, did it gather dust on your SSD / HDD? The same situation is with static analyzers. You need to apply them regularly, and not one-time.



If you check the application code with the analyzer just before the release, it is obvious that many errors will already be fixed. But at what cost? At the cost of the nerves and time of the developers who wrote the code, at the cost of numerous tests designed to identify these very mistakes. As a result, the cost of such errors becomes, to put it mildly, considerable.

At the same time, all this could have been avoided if the analyzer were correctly introduced into the development process. By installing the analyzer locally on the machine for each developer, it is possible to ensure that most of the errors recorded by the analyzer are detected and corrected even before they get into the repository. Moreover, the detected and corrected error, which has not yet had time to grow with various dependencies, will cost much less. Contribute to error detection even moreincremental analysis mode , the use of which allows you to identify an error immediately after its occurrence.

A useful step would be the introduction of static analysis into the nightly assembly process. It will also allow you to quickly detect errors, as well as find out who made them into the repository. For developers, this will also be an additional incentive to write code more accurately.

Thus, it is the regular use of static analysis tools that will make it possible to get the most benefit from them.

Summary

Once again, we managed to check an interesting project, find no less interesting errors and talk about them. Perhaps someone will take note of something, learn something new or just be more careful when writing code. Nevertheless, we are all human, and it is human nature to make mistakes. PVS-Studio will help to correct errors made in the program code . Regular use of a static analyzer will reduce the headache associated with finding errors and correcting them.

If you want to share this article with an English-speaking audience, then please use the link to the translation: Sergey Vasiliev. Accord.Net: Looking for a Bug that Could Help Machines Conquer Humankind .