The Art of Parsing and Comparing Version Strings

Software versions come in a variety of different formats and SecAlerts needs to understand them all. We might be most used to the standard semver convention major.minor.path - however, many well-known software don’t follow the standard. Google Chrome version string has an extra number (138.0.7204.51). OpenSSL versions would add a letter at the end of their version string (1.1.1t). Some use date based versioning (20181205), while others will use keywords like beta and alpha. Some even have different delimiters or formatting (21H2 (20348.169.210806-2348)).

All of these version strings need to be understood and comparable. We should be able to determine if one version string is less than, equal to or greater than any another version string.

Parsing

The first thing we must do is break apart the string into components. These are the component types we will recognise:

• numeric — digit sequences

• text — alphabetic text not part of a keyword

• hex — hexadecimal strings

• keyword — special keywords like beta, alpha, rc along with its numeric representation

• separator — special segment-level separator (like -)

• padding — used for length alignment (null or 0)

ℹ️ Note that we don’t need a component for separators like a dot or parenthesis, because they are implied. However a hyphen separates the version string into segments of versions that need to be compared per segment, so we do need a special component to represent it ... but more on that later.

We could likely parse this with some clever regexes, but we use a token stream parser to turn our version string into an array of components.

Example

For 1.2.3-alpha.2:

[
  { "type": "numeric", "value": 1 },
  { "type": "numeric", "value": 2 },
  { "type": "numeric", "value": 3 },
  { "type": "separator" },
  { "type": "keyword", "value": -3 },
  { "type": "numeric", "value": 2 }
]

Keyword components (like beta or rc) are considered less than numeric components so we represent them using negative values. Therefore alpha becomes -3, beta becomes -2, and rc becomes-1.

Padding

Once we have parsed the version string into its component representation we can look at how we might compare two versions.

When comparing 1 and 1.1, we must pad the shorter version:

• 1 → [ 1, <PAD> ]

• 1.1 → [ 1, 1 ]

When we encounter a separator component we need to treat that as a new segment. Padding is then applied per segment. For example:

• 1-2.0 → [ 1, <PAD>, <SEP>, 2, 0 ]

• 1.0-3 → [ 1, 0, <SEP>, 3, <PAD> ]

Each segment is essentially a self-contained version. Once padded, the component arrays are aligned and ready for comparison.

Comparison

We start comparing two version component arrays from the left to right and compare each component.

• Continue at each step if components are equal.

• If unequal, return the result and the depth (how many components were compared before the first difference).

Example

Compare A: 1-2.0 vs B: 1.0-3

Parsed and padded:

A: [ 1, <PAD>, <SEP>, 2, 0     ]
B: [ 1, 0,     <SEP>, 3, <PAD> ]

Step-by-step:

1. 1 vs 1 → equal

2. <PAD> vs 0 → equal

3. <SEP> vs <SEP> → equal

4. 2 vs 3 → less than

In our comparison A is less than B with a depth of 4.

But what if component types differ — say, a text vs a numeric component?

We use a comparator table keyed by type-pair (e.g. text-numeric) to dispatch the appropriate comparison logic. Inverses are automatically generated by flipping arguments and results.

comparatorLookup[`text-numeric`] = (a, b) => {
  return String(a.value).localeCompare(String(b.value));
};

// register the inverse
comparatorLookup[`numeric-text`] = (a, b) => 
  comparatorLookup[`text-numeric`](b, a) * -1;

Ranges

In the real world, vulnerabilities often list ranges of affected versions e.g. up to X, between X and Y.

Interpreting those ranges correctly has some nuance. Consider the scenario:

Vulnerability affects versions up to 1.3.5 and up to 1.4.1 Is 1.3.6 affected?

It falls between those bounds so we might think yes. However, intuitively we know that software typically receives patches for older version streams, so what this is really saying is up to 1.3.5 for all versions matching 1.3.x and up to 1.4.1 for all versions matching 1.4.x . Therefore, the answer is actually no, it is not affected.

Example

We first find the two surrounding version ranges for query Q:

A: ≤ 1.3.5
Q: 1.3.6
B: ≤ 1.4.1

Compare Q with both:

• A → mismatch, depth 3

• B → match, depth 2

Remember that the depth represents how far into the version component array before we got a non-equal result.

If both A and B match we can immediately determine that it’s affected. Conversely, if both A and B do not match, then it is not affected. If only one matches then use the result from the comparison with greater depth i.e. the more precise match.

The depth of A is 3, which is greater than the depth of B (2). Therefore, we return the result of A and can determine that Q is not affected.

—

Parsing and comparing version strings sometimes feels like a dark art rather than a science, but with a structured, depth-aware approach, it becomes a precise and predictable process. Our approach has allowed us to handle some very unexpected version strings in an intuitive way, thereby reducing the noise of vulnerabilities that don’t affect our users.