Store version ranges

[pombredanne]

To support vulnerabilities that impact or fix a package version range, we would need to store that data.
In addition to that, we would also store the relationship between vuln and package for every known packages at the time we create or update a vuln.
This is follow up of package-url/purl-spec#119

[pombredanne]

From dupe 248:

package-url/purl-spec#65 and package-url/purl-spec#84 don't provide concrete versions hence we need to store version ranges for that we must first improve the data models

[sbs2001]

Context

Security advisories as a part of convention provide patched/vulnerable packages using a version range. For eg ruby provides this https://github.com/rubysec/ruby-advisory-db/blob/6efbdb053cbe41e55f435ddee25a1562fb73f3f2/gems/actionpack/CVE-2012-1099.yml#L23

When an advisory provides such version ranges we in ideal case want to convert the version range into a discrete set of versions, ie "resolve the range".

We do this by

1. Obtaining all the version released till date of the given package by calling some API. In this case the endpoint will be https://rubygems.org/api/v1/versions/actionpack.json .

2. Now we classify the versions into two groups. a. Satisfies the range b. Does not satisfy any range. And then using some logic a group packages are either vulnerable or patched while b group packages have opposite vulnerability status than the a group ones.

The actual problem :

In some cases there is no API to carry out step 1 . ie Version ranges can't be resolved into discrete versions. We want some way to store such data in a similar manner when we have discrete versions. Eg https://security.gentoo.org/glsa/202009-18

[copernico]

Maybe it is not necessary to require that version ranges should be resolved a-priori (that is, resolved to generate a finite set of existing artifacts); they could be used to determine a-posteriori whether or not a given artifact is in the range or not. The advantage of the latter method is that you would not need the API to determine what exists.
In practice though, one needs to enforce some limits on how to interpret intervals that are open-ended (for example, version 2.2 and up).

One way could be to allow only the "last segment" of the version to vary; for example:

2.2 and up --> 2.2, 2.3, 2.4,....... (but not 3.0)
2.2.1 and up --> 2.2.1, 2.2.2, 2.2.3 (but not 2.3.x)
3.0 and up --> any 3.x (but not 4.x, 5.x etc)

Would this make sense? It's a compromise, this still requires enumerating a few intervals to achieve the correct semantics, but at least it is simple, hopefully easy to grasp, and quite flexible to cover the large majority of cases.

Your thoughts?

[sbs2001]

@copernico

Ranges with single bound are problematic (they ignore backports). A more formal way of allow only the last segment is to use the pessimistic-operator https://thoughtbot.com/blog/rubys-pessimistic-operator . There's tooling for that alright.

Unrelated to this :
I actually proposed something similar which was to avoid resolving ranges entirely and store them directly in DB (you can find the convo with @haikoschol and @pombredanne in the chat if you scroll wayyyy up). We rejected the proposal primarily because assuming versioning format is a bad idea. My current opinion is to use ranges as a last resort/fallback.

Primary motivation to store ranges ATM is avoid losing data from places like https://security.gentoo.org/glsa and then have something to fallback on when some specific version is not present in our data.

[copernico]

@sbs2001 I think the pessimistic operator (which I ignored, thanks for the pointer) describes exactly the semantics I had in mind. Re: backports: I am not sure I understand what you mean; in any case I would stay away from using wallclock time (as in released-before, or released-after) when determining if a version is "after" or "before" another: I guess what matters are version identifiers: for sure 3.1 is after 3.0; but is 2.1 after 3.0? maybe, or maybe not, we need a separate interval expression for 2.x
Basically, if a fix of, say, version 3.1.1 is then backported to, say, 2.1.14, what we would have to do is to also specify 2.1.4 and subsequent as fixed, in a separate (extended-)purl.

[pombredanne]

@sbs2001 you wrote:

I actually proposed something similar which was to avoid resolving ranges entirely and store them directly in DB (you can find the convo with @haikoschol and @pombredanne in the chat if you scroll wayyyy up). We rejected the proposal primarily because assuming versioning format is a bad idea. My current opinion is to use ranges as a last resort/fallback.

Do you mind digging this up and pasting the chat log in a comment here?

[pombredanne]

For reference there is a related Package URL PR by @david-a-wheeler at package-url/purl-spec#93 that I need to reply to and tickets at package-url/vers-spec#9 and package-url/purl-spec#84
And also ossf/wg-vulnerability-disclosures#28 (comment)

[pombredanne]

Here are some thoughts and background rehashing for reference:

Context

There is no (mostly) universal syntax for version ranges and there is no (mostly) universal ways to compare two versions. Each package type may define their own syntax and semantics. For instance:

• Rubygems https://guides.rubygems.org/patterns/#semantic-versioning
• node-semver as used for npms https://github.com/npm/node-semver#ranges
• Python https://www.python.org/dev/peps/pep-0440/
• Debian and Ubuntu https://www.debian.org/doc/debian-policy/ch-relationships.html
• RPM distros https://rpm.org/user_doc/dependencies.html#versioning and https://fedoraproject.org/wiki/Archive:Tools/RPM/VersionComparison
• Perl https://perlmaven.com/how-to-compare-version-numbers-in-perl-and-for-cpan-modules
• of course NVD CPEs https://nvd.nist.gov/General/News/CPE-Range-Notification
• Apache maven http://maven.apache.org/enforcer/enforcer-rules/versionRanges.html
• NuGet https://docs.microsoft.com/en-us/nuget/concepts/package-versioning
• Apache and Nuget following more or less math intervals https://en.wikipedia.org/wiki/Interval_(mathematics)
• Gentoo https://wiki.gentoo.org/wiki/Version_specifier
• Alpine linux https://gitlab.alpinelinux.org/alpine/apk-tools/-/blob/master/src/version.c (which might be using Gentoo conventions)
• Go https://golang.org/ref/mod#versions which uses semver with some twists

Problem

Version ranges are useful because they can help to map a future, not-yet-known package version to a known vulnerability impacting it if that package version is within that range.

Some solution elements

There are a few things to consider:

1. in all cases storing version ranges when available in a vulnerability is a useful data point
2. since there is no universal syntax and algorithm for version comparison we could either:
   2.1 define a mostly universal syntax for ranges (as part of Package URLs) and package-specific way to normalize to that syntax.
   2.2 use a package-specific syntax and do not normalize it
3. regardless of the syntax selected, the semantics of versions comparison would need to be package type-specific at best to be correct, and in some cases they may be specific to  package instance e.g. there would be a collection of algorithm to choose from with type defaults and possibly an override at a package level ( and a package-level version scheme feels rather contrived)

As for the problem at hand here:

• We want to store the versions range
• We want to store concrete real relationships between a package version and a vulnerability. This matters because storing a version range only (e.g. potential relationship) may need to be overridden. Also it allows us to navigate the graph of relationships between packages and vulnerabilities efficiently. This means that each time we add a new vulnerability we need to resolve a possible range to a list of concrete known package versions.
• Yet at the same time, we do not know yet about future versions (or may not be up to date about all the known version of a package just now) so we would also need a way to resolve any version that would not be found as stored in the DB against version ranges. 

So in recap IMHO we should ideally:

1. store version range
2. store concrete relationships
3. resolve ranges on create or on access or on query either using a list of known versions or without that list