Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/tools/go/analysis/passes/nilness: add -sound option #36977

Open
Matts966 opened this issue Feb 2, 2020 · 13 comments
Open

x/tools/go/analysis/passes/nilness: add -sound option #36977

Matts966 opened this issue Feb 2, 2020 · 13 comments

Comments

@Matts966
Copy link

@Matts966 Matts966 commented Feb 2, 2020

As of ecb101e, the nilness check is designed to be a complete static check, in other words, its diagnostics don't have false-positive cases.

However, for the safety, we sometimes want a sound static check even with false positive issues.

For example, facebook/infer, checks the NPE with false-positive cases. The java code below is checked and causes error: NULL_DEREFERENCE.

void mayCauseNPE(boolean option) {
  if (option) {
      Random rng = new Random();
      Pointers.A a = Pointers.mayReturnNull(rng.nextInt());
      // FIXME: should check for null before calling method()
      a.method();
  }
}
mayCauseNPE(false);

According to Rice's theorem, we can't get complete and sound diagnostics, so I think adding an option to switch between completeness and soundness is appropriate.

This requires at least 2 items below

  • checking functions, in which NPE can occur with nil arguments, and emitting diagnostics if they are called with nil arguments.
  • emitting diagnostics even with unknown (potentially nil) values
@gopherbot gopherbot added this to the Unreleased milestone Feb 2, 2020
@gopherbot gopherbot added the Tools label Feb 2, 2020
@cagedmantis
Copy link
Contributor

@cagedmantis cagedmantis commented Feb 7, 2020

@matloob
Copy link
Contributor

@matloob matloob commented Feb 7, 2020

I wonder if we should make that a separate analysis? (Maybe refactoring the nilness checking code to be parameterized so it can be used by nilness and the separate analysis). It's a lot easier to enable/disable analyses instead of passing flags.

@Matts966
Copy link
Author

@Matts966 Matts966 commented Feb 8, 2020

Thank you! I already wrote an analysis to check function call that can cause nil pointer dereference so I will investigate the way in which nilness's result is used as fact by this analysis.

@Matts966
Copy link
Author

@Matts966 Matts966 commented Feb 9, 2020

How about returning the data below by nilness?

// BlockToNilness maps ssa block to the information
// about the nillability of values in the block.
type blockToNilness map[*ssa.BasicBlock]nilnessFacts
type nilnessFacts []fact
func (*blockToNilness) AFact() {}

Also, I wonder if we have new 2 analyses, the first of which checks the functions that can cause error related to nil and returns the information and the second of which checks the actual calls of the checked functions. The first one does not depend on nilness so they can be run parallelly.

In any way, the new analyzer inevitably double-checks the whole SSA CFG.

@matloob
Copy link
Contributor

@matloob matloob commented Feb 10, 2020

cc @findleyr

Would the facts returned by nilness be unexported types? We'd also have to make it clear that the basic block references point back to the SSA returned by the SSA analysis.

@Matts966
Copy link
Author

@Matts966 Matts966 commented Feb 11, 2020

Thank you for your reviews!

  • The types should have been exported like buildssa.SSA to be used in the new analysis.
  • I think ssa.BasicBlock is common in all analysis because buildssa returns its result as reference, others refer to it, and the blocks are stored in the result as references. However, integration tests should be needed in advance.
  • Maybe ObjectFact should be used instead of a simple map? (object member and Object method should be added in the BasicBlock for this)

Also, I should change the new analysis's spec as follows

  • Check each function like nilness, but only isnonnil values other than builtin and parameters are allowed(dangerous operations with unknown values are not allowed).
  • Store the function calls with isnil or unknown arguments in the step above.
  • Check if the calls stored by the step above are dangerous or not like this code.
@matloob
Copy link
Contributor

@matloob matloob commented Feb 11, 2020

Hm, I don't know if adding Objects to BasicBlocks is the right idea: multiple objects could correspond to a basic block. I wonder if @findleyr has opinions about how facts about the SSA should be reported.

Another question: I wonder how this is going to be exposed: do you want to make the fact visible so that another Analysis, outside tools, would use it (preferred by me), or do you want to put the new Analysis in tools? We just drop most of the analyses in we have in go/analysis/passes as a default for gopls, but we wouldn't want to do that here, because we already have a very similar analysis.

@Matts966
Copy link
Author

@Matts966 Matts966 commented Feb 12, 2020

It's right. I thought that adding an option to nilness to switch between clarity and safety is good at first, but making them separte analysis and placing the new one outside of go/analysis can be better because of uesfullness and peformance (exporting the facts by nilness is difficult to understand for users and not good for performance because user should double-check blocks).

Also, the algorithm written above was not sound so the one below may be better.

  1. Check and classify values like nilness.
  2. Check all the calls of unexported fuctions and if all the calls of an unexported function are with nonnil value, then export the fact.
  3. Check while the facts are newly exported. Parameters with facts are treated as nonnil value.
  4. Finally check dangerous operations like nilness but not allowing unknown values. Parameters with facts are treated as nonnil because unexported functions are not called in other packages later with nil arguments.
@matloob
Copy link
Contributor

@matloob matloob commented Feb 13, 2020

I don't quite understand the algorithm: my main question is what does the fact you want to export signify?

I think we can answer that question, and then make an experimental fact that you can try using in the alternate version of the analysis. I'm not sure that I'd be the best person to review the actual analysis code, though.

@Matts966
Copy link
Author

@Matts966 Matts966 commented Feb 16, 2020

The fact I wanted to export signifies that a function is called with nil, unknown or nonnil arguments. For example,

func x(x, y *int) {} // want x: "&[isnil, isnonnil]"
z := 10
x(nil, &z)

The values are updated in the following priority
isnil <- unknown <- isnonnil
for the soundness.

I implemented an analysis though it emits too many false-positive cases and almost based on nilness.
https://github.com/Matts966/knil

Reducing false-positive issues by using some special comments or fixing problems is needed.

@matloob
Copy link
Contributor

@matloob matloob commented Feb 18, 2020

Okay, I'm curious what the data type of the fact would be.

@findleyr
Copy link
Contributor

@findleyr findleyr commented Feb 25, 2020

I don't think that using ObjectFacts makes sense here: nilness is an attribute of an ssa.Value within a BasicBlock, not an attribute of an Object.

I think the suggestion of exporting nilness.fact, and passing around a map[*BasicBlock][]nilness.fact might work. However, it should probably be the return value of the nilness analyzer, rather than a PackageFact: it doesn't need to be accessed outside the package analysis, and PackageFacts must be serializable.

@Matts966, does that make sense?

But I'm not sure we should make this change unless we have good reason. I am not surprised that your new analyzer emits too many false positives. Unless that can be fixed, we should probably wait for a valid use-case for nilness data before changing the API.

@Matts966
Copy link
Author

@Matts966 Matts966 commented Feb 28, 2020

@matloob
Thank you, the data type of the fact is like below, that means which argument can be nil
https://github.com/Matts966/knil/blob/ce5d9d2dd08afaf3dde41a430e3fc46d1e9c3276/knil.go#L68-L71

@findleyr
Makes sense, thank you.
I'm now improving my linter. It emits more than 21129 errors at first for golang.org/x/tools, but now the false positives are decreased to 7460.
Still, this linter can be improved by the items below.

  • Check the nilness of the functions' return values and use it in function calls
  • Handle method closures correctly

After that, I will report whether the linter is actually usable or not.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.