4 ms·
The claim seems to be that the tool will always tell you absolutely whether a null-dereference will happen, and never say “maybe.” The Halting Problem is trivi
by drfuchs 9y ago
The claim seems to be that the tool will always tell you absolutely whether a null-dereference will happen, and never say “maybe.” The Halting Problem is trivially reducible to this (just put an intentional null-deref in front of each halt).
- taeric 9y agoNot necessarily the same point being made. At least, they are subtly different, to my understanding. It can tell you that, "if this line is reached, and it was called from this path (with evidence on how this could happen), it will dereference a null." It is not saying that "running this program will guarantee give you a null dereference." The halting problem is more in line with "this program will terminate on any possible inputs", which is more expansive. It is trivial to say that you can prove some programs won't terminate on a particular input. Question is if you can do it for all inputs, no?
- zenhack 9y agoRice's theorem is a bit more direct here: C is Turing complete, some C programs derefernce null pointers, and some don't. Therefore, the question of whether a an arbitrary C program derefernces a null pointer is in general undecidable. But I don't think the Op was claiming it was possible to do this perfectly, just possible to write very useful tools. You will always have either flase positives or false negatives (or I suppose inputs where you just hang). Turing completeness is the bane of static analysis, but that doesn't make it a fruitless endeavor.
- UncleMeat 9y agoI wouldn't say that Rice's thm is the bane of static analysis. It is what makes the field interesting. If the problems were not undecidable then we wouldn't have do so many interesting and challenging things to make working tools.