Further improvements to reporting

[mlevesquedion]

A recent PR #204 implemented better formatting for report messages, as well as the possibility of using a custom message, which is printed after the generic report message.

I am starting this discussion to discuss how reporting could be further improved. The following are some of my ideas, I encourage you to add your own and we can discuss what improvements we want to make.

Report source types

Reports currently do not include the type of the source, but it is common to have multiple different values wrapped into a single line, such that it can sometimes be difficult to identify which one is the source:

x, err := Propagates(ProducesSource(Propagates("key")))

Having the type would also help determine which matcher triggered the propagation.

Report sources a single time

With the current reporting scheme, we produce one report for each sink that is reachable from a given source:

pkg/foo/bar.go:78:17: a source has reached a sink
 source: pkg/foo/bar.go:75:33
pkg/foo/bar.go:80:17: a source has reached a sink
 source: pkg/foo/bar.go:75:33

This feels a bit noisy to me, since the source information is duplicated. I think it would be preferable to produce the report at the position of the source, and to list the sinks afterward:

pkg/foo/bar.go:75:33: this source has reached the following sinks
 pkg/foo/bar.go:78:17
 pkg/foo/bar.go:80:17

Including the names of the sinks in the report may also be useful.

Only report the file path once

Since the analysis is intraprocedural, it is impossible for a source and sink to be in separate files, and in fact, in separate functions. This will change when we implement interprocedural analysis, but for the time being, reporting the path more than once is redundant.

Expose a flag to report the full propagation

Currently, we only report the beginning (source) and end (sink) of a propagation. To properly assess whether taint can actually reach a sink, it is therefore necessary to reconstruct the taint propagation path manually. In addition to the source and sink, it would be useful to report the full propagation path, which essentially means dumping the Propagation.preOrder (that won't actually work, but that would be an implementation detail - one approach would be to record additional info during the traversal and use that to reconstruct the path afterwards). This would make it much easier to determine exactly how a source reached a sink. Since it is unreasonable to assume that users of the tool will be familiar with the ssa package, this flag should be off by default. However, it should be possible for users to turn it on if they wish. From personal experience, I believe such an option would be very useful.

[vinayakankugoyal]

Good ideas! My priority order for these would be

1. Expose a flag to report the full propagation.
2. Report source types.
3. Report Sources a single time.
4. Only report file path once.

The complexity of implementing these roughly follows the same order?

[mlevesquedion]

I think the complexity for the first one is much greater than for the others, but I may be wrong. Here are some thoughts on implementation:

• Expose a flag to report the full propagation: exposing the flag should be straightforward, but currently we don't compute specific source --> sink paths, we store the full preorder + whether or not a sink is reachable from a source. We will need to collect additional information during the traversal so that paths can be reconstructed as needed.
• Report source types: add the source type to the report message using %T.
• Report sources a single time: instead of producing a report as soon as we find a sink that's reachable from a source, accumulate sinks that are reachable from a source and produce a report when we're done looping over the functions/blocks/instructions.
• Only report file path once: in the function that's producing the report, use a subset of position.Position.(Filename|Offset|Line|Column).

[vinayakankugoyal]

In addition to the above ideas I think we should also consider:
Adding presubmit tests that run levee changes against large code base(s).

[mlevesquedion]

I agree that this is important, but I think this is orthogonal to reporting. 🤔

[vinayakankugoyal]

I realized that after typing it. 🤦

[PurelyApplied]

I generally agree with Vinayak's value assessment, but maybe not with complexity.

• I think Report source types might be pretty trivial to add, so I might do that first as a low-hanging fruit.
• Reporting sources only once should be pretty simple to implement, but since it will have us changing the Pos of where a diagnostic is emitted, it will require us to update every test. Cumbersome, but straight-forward.
• I think Only report the file path once is easy to enforce if we ensure reports in a given package are only produced by the analysis pass for that package. I believe this concern arose in initial drafts of interprocedural work.
• Enabling full propagation reports is going to be a good body of work. Valuable, but definitely requires significant rewriting to existing propagation logic.

[PurelyApplied]

Regarding full propagation reporting, we'll want to decide if it's worth it to report every propagation path between a source and a sink, or if it's okay to tell a user that they need to run it again to verify. E.g., considering:

func Foo(s Source){
  output, err := doSomethingFancy(s)
  if err != nil {
    Sink("oh no, %v %v", output, err)
  }
}

We have propagation paths of source -> output -> sink and output -> err -> sink. But since our current implementation is essentially a big ol' BFS, it might end up being a lot harder to report both than it would be to report the sequence of edges we happen to follow. This is getting into implementation weeds a bit, but I would be okay with propagation reports being informative rather than comprehensive.