# Searching for errors by means of virtual values evaluation

In the process of static analysis, exact values or ranges of values of some variables and expressions can be evaluated\. This is useful information, which can be used when searching for errors\. We call such values 'virtual values', and this article is devoted to this topic\. 

![0394_VirtualValues/image1.png](https://import.viva64.com/docx/blog/0394_VirtualValues/image1.png)

If a static analyzer is able to evaluate an expression, this will allow to perform more in\-depth analysis, and detect more errors\. It certainly is not only about the exact results of the expressions such as 1\+2, but also about evaluating the range of values taken by a variable at a certain point in the program\. In [PVS\-Studio](https://pvs-studio.com/en/pvs-studio/) analyzer, we call the algorithms responsible for evaluation of ranges a mechanism of virtual values\. Such a mechanism is there in the C/C\+\+ kernel of the analyzer, as well as in the C\# kernel\. In this article we discuss the mechanism of virtual values using C\#\-analyzer as an example\. 

In order to search for bugs in C\# projects we use [Roslyn](https://github.com/dotnet/roslyn) in PVS\-Studio analyzer to get all the necessary information about the source code\. Roslyn provides us with a syntax tree, information about the types, a search for dependencies and so on\. During the analysis process, PVS\-Studio traverses a syntax tree and applies the diagnostics to its nodes\. Besides that, the analyzer collects the information that can be of use later while traversing\. An example of such additional information is virtual values\.

## Creating virtual values

Virtual values are stored for fields, properties, variables, and parameters when they are first mentioned in the code\. If the first mention is the variable declaration or assignment, we try to evaluate the virtual value by analyzing the expression to the right of the equal sign\. Otherwise, we usually don't know anything about the property/field/parameter, and suppose that it can be of any legitimate value\. Here is an example:

```cpp
public class MyClass
{
    private bool hasElements = false;
    public void Func(byte x, List<int> list)
    {
        int y = x;
        hasElements = (list.Count >= 0);
        if (hasElements && y >= 0) //V3022
        {
        }
    }
}
```

When the analyzer gets to the body of the _Func _function during the traverse of the tree, it will start evaluating virtual values of the variables\. In the first string we'll have the declaration of _y_ variable that is initialized with _x_ value\. Since all we know about _x_ is that it has a _byte_ type, then it can take any value from 0 to 255\. So, this range of values will be assigned as the virtual value of the _y_ variable\. The same will be done for the field _hasElements_: the analyzer knows that the _Count_ property of the list cannot take negative values, that's why _true_ will be assigned as a virtual value of the _hasElements_ variable\. Now during the analysis of _hasElements && y \>\= 0_ condition, we know that the left and the right part are true, so the whole condition is also always true, which triggers the [V3022](https://pvs-studio.com/en/docs/warnings/v3022/) diagnostic\. 

Let's take a closer look at how the virtual value of an expression is evaluated\. 

## Evaluation of a virtual value of an expression

The virtual value is evaluated differently for variables of different types\. In the case that a variable is of an integer type, the virtual value is stored as a set of value ranges which the variable can be in\. For example, consider this code:

```cpp
public void Func(int x)
{
    if (x >= -10 && x <= 10 && x != 0)
    {
        int y = x + 5;
    }
}
```

In the beginning of the function, we don't know anything about _x_ variable; its range of values \- all legitimate values if _int_ type: \[int\.MinValue, int\.MaxValue\]\. When entering the _if_ block, we can improve the virtual value based on the condition\. Thus, within the _if_ block, the variable _x_ will have the range of \[\-10, \-1\], \[1, 10\]\. So, now the analyzer will take into account the virtual value if _x_ is used during the evaluation of the expression\. In our example, _y_ will receive the virtual value \[\-5, 4\], \[6, 15\]\.

For the expressions of _bool_ type, the virtual value is evaluated differently\. Here we have only three options: false, true, or unknown value\. So, we'll just substitute enough values for all variables of the expression, and check whether the expression will take one and the same value\. For example:

```cpp
public void Func(uint x)
{
    bool b = (x >= 0); //V3022
}
```

No matter what values of _x_ parameter we take, the expression _x \>\= 0_ will always be true\. That's why by substituting several values instead of _x_, we'll make sure of it, and assign _true_ as the virtual value for _b_\. 

One more example from the Umbraco project:

```cpp
private object Aggregate(object[] args, string name)
{
    ....
    if (name != "Min" || name != "Max") //V3022
    {
        throw new ArgumentException("Can only use min or max...");
    }
    ....
}
```

To make sure that the condition in the example is always true, the analyzer will substitute _name_ with_ "Min",_ _"Max",_ _"", null_ values\. In each of these cases, either the left or right side of the expression is true, then the expression in the condition is always true\.

Virtual values evaluated for all variables are stored separately for each block\. Entering the nested block, the analyzer creates its own set of virtual values based on the parent block\. For a simple nested block, it's just a copy of all virtual values\. For conditions, loops, and other blocks, the virtual values aren't just copied, some additional restrictions can be imposed on them\. 

## Improving virtual values in the if/else block

Let's take a look at the virtual values during the processing of _if/else_ block\. 

```cpp
public void Func(int x)
{
    if (x >= 0)
    {                    //x:[0, int.MaxValue]
        if (x <= 10)
        {                //x:[0, 10]
        ....
        }
        else
        {                //x:[11, int.MaxValue]
        ....
        }
    }
}
```

Having analyzed the condition _x_ _\>_ _\=_ _0_, PVS\-Studio will limit the range of the _x_ variable for the first _if_ block with values \[0, int\. MaxValue\]\. After processing the second condition _x_ _<\=_ _10,_ the analyzer will create two more copies of virtual values of _x_ variable \- one for the _if_ block and the other \- for the _else_ block\. Moreover, these copies will be restricted, taking into account the virtual value of this variable from the parent block and the virtual value of the expression in the condition\. So for a nested _if_ block,_ _the virtual value of_ x_ variable will be \[0, 10\], and for the_ else_ block _\-_ all other values \- \[11, int\.MaxValue\]\.

After the traversing of _if/else_ block, it is necessary to combine virtual values from the _if_ and _else_ blocks for each variable\. We should also remember that if in the end of _if_ or _else_ block there was a jump statement, _return_, for instance, then we don't have to combine the values from this block\. Examples:

```cpp
public void Func1(int x)
{
    bool b1 = false;
    bool b2 = false;
    if (x >= 0)
    {
        ....
        b1 = true;
        b2 = true;
    }
    else
    {
        ....
        b1 = true;
    }
    //Here we know that b1 is always true
    //b2 can take any value
}

public void Func2(int x)
{
    if (x < 0)
        return;
    //Here we know that x is always non-negative
}
```

## Loop processing

The peculiarity of virtual values evaluation for loops, is that the body of the loop should be traversed twice\. Let's look at an example\.

```cpp
public void Func()
{
    int i = 0;
    while (i < 10)
    {
        if (i == 5)
        {
        ....
        }
        i++;
    }
}
```

If we just copied virtual values from the parent block to the _while_ block, then we would get a false positive of V3022 during the analysis of the condition _i \=\= 5, _as we know, before the loop the _i_ variable_ _was zero\. That's why before analyzing the body of the loop, we should evaluate which values variables can take at the end of each iteration, and also in all blocks containing _continue_ statement, then combine all these values with the values of the variables before the loop is entered\. Besides that if we analyze the _for_ loop, we need to consider the initialization blocks and the changes of the counter\. After the values of all the possible entry points of the loop are combined, we should apply the condition of the loop in the same way as it is done for the _if_ block\. In such a way we will get correct virtual values for the variables, and we can start the second traverse of the loop, where we'll have the diagnostics applied\. 

After traversing the loop we should combine all virtual values of variables from all the points, from which we get to the statement that follows the loop\. These are values we had before the beginning of the loop \(if there was no iteration\), values of variables in the end of the body of the loop, and values of variables in the blocks, containing the _break_ or _continue_ statement\. All these values we have already evaluated and remembered when the loop was traversed for the first time\. Now we should combine them all and apply a condition, which is the opposite to the condition of the loop\. 

This was quite a complicated explanation, so let's look at an example\.

```cpp
public void Func(bool condition1, bool condition2, bool condition3)
{
    int x = 0;
    while (condition1)
    {
        //x:[0, 1], [3]
        if (condition2)
        {
            x = 2;
            break;
        }
        if (condition3)
        {
            x = 3;
            continue;
        }
        x = 1;
    }
    //x:[0, 3]
}
```



In this example the x variable is zero before entering the loop\. Having done the first traverse of the loop, the analyzer will evaluate that the x variable can also take the value 1 and 2 in the block with break, and 3 in the block with continue\. Since we have three points of transition to the next iteration of the loop, the variable x can be 0, 1 or 3 at the beginning of the loop body\. We can get from four points to the statement following the loop\. So here x can be 0, 1, 2 or 3\. 

Also the analyzer evaluates which values can accept the variables inside _case_ blocks of _switch _statement, inside the _try/catch/finally_ and for other language constructs\.

## Division by zero

Division by zero, is one of the mistakes which can be found by means of virtual values\. This diagnostic is peculiar due to the fact that not every division, where we may theoretically have a zero in the denominator, will trigger it\. Let's look at an example:

```cpp
public int GetBlockCount(int dataLength, int blockSize)
{
    return dataLength / blockSize;
}
```

In this function, the _blockSize_ can theoretically take any _int_ value, and zero is included in this range\. But if the diagnostic is issued for this code, it will not make sense, as the warnings that are actually useful, will be lost among false positives\. So we had to teach the analyzer to detect real suspicious divisions in the mass of all divisions, like these for example: 

```cpp
public string GetDownloadAvgRateString() {
    if (SecondsDownloading >= 0) {
        return GetSpeed(Downloaded / SecondsDownloading);
    } else {
        return "";
    }
}
```

or these:

```cpp
public void Func(int x, int y)
{
    for (int i = -10; i <= 10; i++)
    {
        y = x / i;
    }
}
```

As a solution, we differentiate ranges of virtual values as precise and non\-precise\. By default, the range is considered to be non\-precise, until it is updated by explicit assignment of a constant, or a variable with a precise range, or by limiting in the condition of _if_ or loop statement\. If a zero gets into the precise range or to the precise range bound, then the analyzer will issue a diagnostic "Division by zero"\.

## Examples

Now let's take a look at several examples taken from real projects, which were found by PVS\-Studio with the help of virtual values\. 

**Example N1 \(RavenDB\)\.**

```cpp
internal static void UrlPathEncodeChar (char c, Stream result)
{
    if (c < 33 || c > 126) {
        byte [] bIn = Encoding.UTF8.GetBytes (c.ToString ());
        for (int i = 0; i < bIn.Length; i++) {
            ....
        }
    }
    else if (c == ' ') { //V3022
        result.WriteByte ((byte) '%');
        result.WriteByte ((byte) '2');
        result.WriteByte ((byte) '0');
    }
    else
        result.WriteByte ((byte) c);
}
```

The first condition of the _UrlPathEncodeChar _function processes special characters, the second condition is a special optimization for the space\. But as the ASCII code of the space is 32, then the space will be handled by the first block\. PVS\-Studio finds this error in the following way: inside the _if_ block, the virtual value of the _c_ variable will be equal to \[0, 32\], \[127, char\.MaxValue\], and inside the first _else_ block \- all the other values : \[33, 126\]\. As the code of the space doesn't get into this range, the analyzer reports about the error [V3022](https://pvs-studio.com/en/docs/warnings/v3022/) \- expression c \=\= ' ' is always false\.



**Example N2 \(ServiceStack\)\.**

```cpp
protected override sealed void Initialize()
{
    if (RootDirInfo == null)
        RootDirInfo = new DirectoryInfo(WebHostPhysicalPath);

    if (RootDirInfo == null || !RootDirInfo.Exists) //V3063
        throw new ApplicationException("...");
    ....
}
```

We don't know anything about the _RootDirInfo_ property in the beginning of the _Initialize_ function\. After the analysis of the _RootDirInfo \=\= null _two more copies of virtual values are created: one for the _if_ block, where _RootDirInfo_ is _null_, the second \- for the _else_ block, where _RootDirInfo_ isn't _null_\. Although there is no else block in the example, the virtual values are still created for it\. Furthermore, inside the if block, the RootDirInfo property is assigned with a new value, which was received after the call of the constructor\. As the constructor never returns _null_, then the value of RootDirInfo in the _if_ block isn't _null_\. Also, as the RootDirInfo for the else block isn't _null_ either, then we see that when combining these two branches RootDirInfo will never be equal to _null_ after the processing of the first condition\. That's why PVS\-Studio will issue a warning during the analysis of the second condition [V3063](https://pvs-studio.com/en/docs/warnings/v3063/) \- a part of the condition is always false\.



**Example N3 \(ServiceStack\)\.**

```cpp
public static TextNode ParseTypeIntoNodes(this string typeDef)
{
    ....
    var lastBlockPos = typeDef.IndexOf('<');
    if (lastBlockPos >= 0)
    {
        ....
        //V3022
        while (lastBlockPos != -1 || blockStartingPos.Count == 0)
        {
            var nextPos = typeDef.IndexOfAny(blockChars,
                lastBlockPos + 1);
            if (nextPos == -1)
                break;
            ....
            lastBlockPos = nextPos;
        }
    }
}
```

Let's see what happens with the variable _lastBlockPos _in this example\._ _First it is assigned with a result of _IndexOf_ function\. The analyzer knows that the functions _IndexOf, IndexOfAny, LastIndexOf, LastIndexOfAny_ return non\-negative values, or \-1\. Therefore, the range of values of the _lastBlockPos_ variable is \[\-1, int\.MaxValue\]\. After entering the _if_ block, the range will be limited only by non\-negative values \[0, int\.MaxValue\]\. Then the analyzer will traverse the body of the _while_ loop\. During the declaration, the _nextPos_ variable will get the range \[0, int\.MaxValue\]\. After the analysis of the condition if \(nextPos \=\= \-1\) two copies of virtual values of the _nextPost_ variable get created: \[\-1\] for the _if _branch, and \[0, int\.MaxValue\] for the _else_ branch\. As the _if_ branch has the _break_ statement, then in the rest of the body of the loop for the _nextPost_ variable, only virtual values are used for the _else_ branch: \[0, int\.MaxValue\], that are then assigned in the end of the _lastBlockPos_ variable\. 

Thus, we have two transition points to the body of the loop: one when entering a loop in which _lastBlockPos_ has a value of \[0, int\. MaxValue\], and the second when moving to the next iteration in which _lastBlockPos_ has a value of \[0, int\. MaxValue\]\. Consequently, _lastBlockPos_ never gets negative values in the condition of the loop, which means that the condition of the loop is always true; so the [V3022](https://pvs-studio.com/en/docs/warnings/v3022/) diagnostic is issued for this code\. 

It should be noted, that this error is really hard to detect manually, because the body of the loop contains about forty lines, and it's hard to track the way all branches get traversed\. 



**Example N4 \(TransmissionRemoteDotnet\)\.**

```cpp
// Converts an IPv4 address into a long, for reading from geo database
long AddressToLong(IPAddress ip)
{
    long num = 0;
    byte[] bytes = ip.GetAddressBytes();
    for (int i = 0; i < 4; ++i)
    {
        long y = bytes[i];
        if (y < 0) //V3022
            y += 256;
        num += y << ((3 - i) * 8);
    }

    return num;
}
```

Here the variable _y_ of _long_ type is assigned with a value having _byte_ type\. So, the check _y < 0_ makes no sense, because the _byte_ type is unsigned\. 



**Example N5 \(MSBuild\)\.**

```cpp
private bool ValidateTaskNode()
{
    bool foundInvalidNode = false;
    foreach (XmlNode childNode in _taskNode.ChildNodes)
    {
        switch (childNode.NodeType)
        {
            case XmlNodeType.Comment:
            case XmlNodeType.Whitespace:
            case XmlNodeType.Text:
                // These are legal, and ignored
                continue;
            case XmlNodeType.Element:
                if (childNode.Name.Equals("Code") ||
                    childNode.Name.Equals("Reference") ||
                    childNode.Name.Equals("Using"))
                {
                    continue;
                }
                else
                {
                     foundInvalidNode = true;
                }
                break;
            default:
                foundInvalidNode = true;
                break;
        }

        if (foundInvalidNode) //V3022
        {
            ....
            return false;
        }
    }

    return true;
}
```

In this example, the body of the loop contains two statements \- _switch_, and _if_\. Let's look at _switch_ block\. The first section with three _case _labels, contains only the _continue_ statement, that's why we cannot move to checking the condition _foundInvalidNode\._ The second case section either moves to the next loop iteration, or sets _foundinvalidNode_ and exits from _switch_\. And, finally, the _default_ section also sets _foundinvalidNode _and exits from _switch_\. Thus, after exiting the _switch_, the _foundInvalidNode_ variable will always be true, which means that the following _if _is redundant\. The analyzer took into account that there is a _default _branch in this _switch _block, so the control cannot go to checking the condition directly \- one of the _switch_ sections will be executed\. 

We should also say that inside this _switch_ statement, the _continue_ statement is related to the loop, while _break_ exits the _switch_, not the loop\! 

## Conclusion

Evaluation of variable values during the static analysis is a powerful tool for searching out bugs in the code\. The code can contain complex branching, nested conditions and loops, blocks having the size of hundreds of lines\. To trace the changes of the variable manually and find an error can be really difficult, that's why [PVS\-Studio](https://pvs-studio.com/en/pvs-studio/) static analyzer can be of great help\.