commit c3a852441dd9bf5e2e2b641815a80771d92e99d1
author Zvonimir Pavlinovic <zpavlinovic@google.com> Fri Jun 03 15:36:29 2022 -0700
committer Zvonimir Pavlinovic <zpavlinovic@google.com> Thu Jun 09 19:55:30 2022 +0000
tree 84a50d7416c721aa42652afca59a08fe4dfe3b29
parent 571ff30a41d13c7bd7bc17cb21600ff0f003e468

vulncheck: include call graph edges that could be missed due to recursion

Consider the call graph G <--> F -> V where F is an entry point function
and V is a vulnerable function. The current algorithm for creation of
vulnerability graphs might start with F, visit V, figure out that V is
vulnerable and hence add F -> V to the vulnerability graph. Then, since
F is in this graph, G will be added too as G calls F and vice versa.

But if we start by analyzing first F -> G, then G won't be added to the
vulnerability graph as F is not yet added to that graph (since we have
not yet analyzed V). Hence, we might miss adding some edges to the
vulnerability graph.

Note that this bug does *not* miss vulnerabilities, just some paths from
entry points to vulnerabilities. In the above example, the missed paths
can be characterized with (F -> G)+ -> V.

The fix is to compute the vulnerability graph by 1) computing a
backwards slice from vulnerabilities, 2) computing a forward slice from
affected entry points, and 3) creating a vulnerability graph from the
intersection of the two call graph slices.

Note that imports and module vulnerability graph creation is not
affected as there can be no recursion in such graphs.

Change-Id: I4509a639ab60a5441b1998d56420f6cc3c38f960
Reviewed-on: https://go-review.googlesource.com/c/vuln/+/411354
Reviewed-by: Jonathan Amsterdam <jba@google.com>