整数/算术Overflor检测工具 [英] Integer / Arithmetic Overflor Detection Tool

问题描述

我目前正在阅读软件学士学位，作为论文的一部分，我需要使用定制的Lexical Analayzer静态检测代码中任何可能的整数溢出。



我还需要使用类似工具评估我的Lexer。



也许有人知道一种能够分析C代码的检测工具整数溢出？





提前致谢。

I am currently reading a Bachelors Degree in software and as part of my thesis I am required to statically detect any possible integer overflow in my code, using a custom built Lexical Analayzer.

I am also required to evaluate my Lexer with a similar tool.

Would perhaps anyone know of a detection tool which is capable of analysing C code for integer overflows?


Thanks in advance.

推荐答案

First of所有，请看我对这个问题的评论。



此外，你搜索这样的工具及其作者的想法在逻辑上是不一致的，至少在你如何制定它时。首先，你声明溢出应该用一些lexer来检测。我们稍后会讨论它。之后，您将这个假设产品称为我的词法分析器。在下一个子句中，您说溢出检测应该由您要查找的工具完成。这与先前的陈述相矛盾。你真的想做什么？



无论如何，让我们考虑你论题的主题的计算机科学方面。我认为检测词汇层面的溢出在理论上是不可能的。这很明显，但正式的数学上严格证明这种不可能性会有点棘手，需要花费很多时间。但如果我告诉你这个想法，你就可以严格理解这个陈述。粗略地说，很容易使任何确定性程序的行为变得不可预测。特别是，在一般情况下，您不能预测执行是否进入某个分支。要进一步了解详情，请阅读：

http://en.wikipedia.org/wiki / Halting_problem [ ^ ]，

http://en.wikipedia.org/wiki/Undecidable_problem [ ^ ]。



如果位置在指令流中执行是不可判定的，你无法预测是否会达到一些算术运算，甚至不太可能预测将达到这一点的操作数集。在数学和计算数学中，有许多具有不可判定的值的算法的例子。所以，它不能基于词法分析来决定。



同时，如果你能检查给定操作数的算术运算是否会溢出，那么溢出检测很容易。您需要在每个算术运算之前插入此类检查，并在溢出即将发生时抛出异常。从技术上讲，这是不切实际的。溢出检测应该是硬件辅助的，实际上是。请参阅： http://www.emulators.com/docs/LazyOverflowDetect_Final.pdf [ ^ ]。



所以，你的目标是无法解决的问题，而不是实际上无法解决的问题，而是针对甚至没有理论意义而且实际上简单荒谬的问题。对不起，但如果我是你的官方对手，我将不得不阻止你的论文成功辩护（在实践中，我可以拒绝提前发挥这个角色的建议）。但顺便说一句，这种失败将是非同寻常的案例。该怎么办？你必须尽快改变论文的主题;这是唯一的解决方案。



您是否会说这个主题是由您的科学顾问指导给您的？那真是太可悲了。大自然的丑恶事实是：一些顾问甚至普通教授都是完全文盲。它们只是假的，带有所有的标志。小心。

-SA

First of all, please see my comment to the question.

Moreover, your idea for search of such tool and its authorship looks logically inconsistent, in least in how you formulated it. First, you state than the overflow should be detected with some "lexer". We will discuss it later. Later, you call this hypothetical product "my lexer". In next clause, you say that the overflow detection should be done by the tool you want to find. This contradict to the previous statements. What do you really want to do?

No matter, let's consider the computer-science aspect of your topic for the thesis. I maintain that detection of overflow on lexical level it theoretically impossible. This it pretty obvious, but formal mathematically strict proof of this impossibility would be a bit tricky and take a lot of time. But if I tell you the idea, you can get strict understanding of this statement. Roughly speaking, it's easy to make behavior of any deterministic program unpredictable. In particular, you cannot, in general case, predict it the execution comes into certain branch or not. To get an idea in further detail, please read:
http://en.wikipedia.org/wiki/Halting_problem[^],
http://en.wikipedia.org/wiki/Undecidable_problem[^].

If the position of the execution in the instruction flow is undecidable, you cannot predict if some arithmetic operation will even be reached, and it's even "less possible" to predict with what set of operands this point will be reached. In mathematics and computation mathematics, there is a number of examples of the algorithms with undecidable values. So, it cannot be decided based on lexical analysis.

At the same time, overflow detection is easy if you can check up if the arithmetic operation with given operands will get into overflow. You would need to insert such check before each and every arithmetic operation and throw exception if overflow is about to take place. Technically, this is impractical. Overflow detection should be hardware-assisted, and in practice, it is. Please see: http://www.emulators.com/docs/LazyOverflowDetect_Final.pdf[^].

So, you are aimed for unsolvable problem, and not to practically unsolvable, but for the problem which makes no even theoretical sense and practically simply absurd. Sorry, but if I was your official opponent, I would have to prevent successful defense of your thesis (in practice, I could turn down the suggestion to play this role in advance). But the way, such failure would be extraordinary case. What to do? You have to change the topic of you thesis as soon as possible; this is the only solution.

Are you going to say that this topic was given to you by your scientific adviser, a guide? That would be really sad. The ugly fact of nature is: some advisers and even universally professors are totally illiterate. They are just fake, with all their regalia. Be careful.

—SA

这篇关于整数/算术Overflor检测工具的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！