3 ms·

I think you mean "false-positives". Most static analysis tools are "conservative": will throw more warnings than they can prove. But assuming they're "sound" (a

I think you mean "false-positives". Most static analysis tools are "conservative": will throw more warnings than they can prove. But assuming they're "sound" (and don't "give up" because of time/space constraints), there'd be no "false-negatives".

UncleMeat 7y ago
Vanishingly few (maybe even zero) industrial static analysis tools are sound. FPs are too common, especially for something like C++ where common code patterns can only be soundly handled by just forcing everything to Top. Good luck with your sound interprocedural pointer analysis as soon as somebody makes an indirect call.
- thekhatribharat 7y ago
  I think you mean industrial static analysis tools aren't complete. Sound means no FNs, Complete means no FPs.
  - UncleMeat 7y ago
    No I meant what I said. Virtually no tool is sound (zero false negatives, lots of false positives) because in practice false positives just make people stop using tools when they are too common.
    - mgerdts 7y ago
      At my previous job, we used an internally developed static analysis tool. While false positives were a problem, the team responsible for the tool took bug reports and fixed these issues. There was a way to silence false positives as well as a mode to only see new (potential) problems. Once code was clean, the false positive rate was low enough to not really be a problem. The bar of zero false negatives is not useful for me when the alternative is to rely solely human code analysis and tests. One thing I learned from using this tool is that static analyzers need to be able to configured to know about side effects of functions that are in libraries. For example, if a library function will free memory, it is important that there's a way to tell the analyzer about this behavior to avoid false positives about leaks. Proper design, careful coding, static analysis, code review, and various forms of testing all have roles to play in delivering reliable code.
      - UncleMeat 7y ago
        But you can't fix all false positives with bug reports. Its fundamental if you want soundness. And for lots of properties (like I said, pointer analysis in C++) the only scalable and sound techniques basically havoc as soon as interesting things start to happen. The community even has a term (soundiness) to describe how everybody throws out certain kinds of soundness (indirect calls through function pointers, reflection in java, tons of features in javascript, etc). Requiring the user to add piles of annotations still sucks, even if you are smart and do something like abductive inference to identify minimally required annotations. Even something as simple as the checker framework in Java has trouble getting people to write correct annotations and has a few corner cases (what is the nullness property of a field in code reachable from a constructor, for example). Nobody does this stuff correctly for something like dataflow annotations on methods. I've got a PhD in this and develop a static analysis tool for my job. I've never seen a productionized, fully sound tool for general purpose static analysis of general programs that solves problems more difficult that slightly augmented type checking.
    - thekhatribharat 7y ago
      So if industrial static analysis tools aren't sound, which means they produce false negatives (ie. they can pass programs with logical errors they're meant to detect), how do you use them to assure code quality?
      - UncleMeat 7y ago
        Same way you use anything. Testing isn't perfect, yet it is still useful. Fuzzing isn't perfect, yet it is still useful. Unsound static analysis techniques aren't perfect, yet they are still useful. The alternative is that your abstract interpretation is pinning to Top very quickly and then throwing false positives everywhere.
      - stjohnswarts 7y ago
        You can't assure code quality, you can only use them to make you code is a bit better because you fixed issues found by the tool and asymptotically approach ideal code and lower the probability there are serious errors. AKA better than nothing.
- pjmlp 7y ago
  Which is why some OS vendors just gave up and are going with hardware pointer validation nowadays. If all goes according to plan, I guess in a couple of decades there won't be any modern computer not making use of it.

UncleMeat 7y ago

Vanishingly few (maybe even zero) industrial static analysis tools are sound. FPs are too common, especially for something like C++ where common code patterns can only be soundly handled by just forcing everything to Top. Good luck with your sound interprocedural pointer analysis as soon as somebody makes an indirect call.

thekhatribharat 7y ago
I think you mean industrial static analysis tools aren't complete. Sound means no FNs, Complete means no FPs.
- UncleMeat 7y ago
  No I meant what I said. Virtually no tool is sound (zero false negatives, lots of false positives) because in practice false positives just make people stop using tools when they are too common.
  - mgerdts 7y ago
    At my previous job, we used an internally developed static analysis tool. While false positives were a problem, the team responsible for the tool took bug reports and fixed these issues. There was a way to silence false positives as well as a mode to only see new (potential) problems. Once code was clean, the false positive rate was low enough to not really be a problem. The bar of zero false negatives is not useful for me when the alternative is to rely solely human code analysis and tests. One thing I learned from using this tool is that static analyzers need to be able to configured to know about side effects of functions that are in libraries. For example, if a library function will free memory, it is important that there's a way to tell the analyzer about this behavior to avoid false positives about leaks. Proper design, careful coding, static analysis, code review, and various forms of testing all have roles to play in delivering reliable code.
    - UncleMeat 7y ago
      But you can't fix all false positives with bug reports. Its fundamental if you want soundness. And for lots of properties (like I said, pointer analysis in C++) the only scalable and sound techniques basically havoc as soon as interesting things start to happen. The community even has a term (soundiness) to describe how everybody throws out certain kinds of soundness (indirect calls through function pointers, reflection in java, tons of features in javascript, etc). Requiring the user to add piles of annotations still sucks, even if you are smart and do something like abductive inference to identify minimally required annotations. Even something as simple as the checker framework in Java has trouble getting people to write correct annotations and has a few corner cases (what is the nullness property of a field in code reachable from a constructor, for example). Nobody does this stuff correctly for something like dataflow annotations on methods. I've got a PhD in this and develop a static analysis tool for my job. I've never seen a productionized, fully sound tool for general purpose static analysis of general programs that solves problems more difficult that slightly augmented type checking.
  - thekhatribharat 7y ago
    So if industrial static analysis tools aren't sound, which means they produce false negatives (ie. they can pass programs with logical errors they're meant to detect), how do you use them to assure code quality?
    - UncleMeat 7y ago
      Same way you use anything. Testing isn't perfect, yet it is still useful. Fuzzing isn't perfect, yet it is still useful. Unsound static analysis techniques aren't perfect, yet they are still useful. The alternative is that your abstract interpretation is pinning to Top very quickly and then throwing false positives everywhere.
    - stjohnswarts 7y ago
      You can't assure code quality, you can only use them to make you code is a bit better because you fixed issues found by the tool and asymptotically approach ideal code and lower the probability there are serious errors. AKA better than nothing.
pjmlp 7y ago
Which is why some OS vendors just gave up and are going with hardware pointer validation nowadays. If all goes according to plan, I guess in a couple of decades there won't be any modern computer not making use of it.