为什么移植整数溢出不是一个好主意

本文重点关注未定义的行为和编译器优化,尤其是在有符号整数溢出的情况下。

译者的注意:在俄语中,“ wrap” /“ wrapping”一词在使用时没有明显的对应关系。 有一个数学术语“ transfer ”,它接近于所描述的现象,术语“ carry flag”是一种在整数溢出期间在处理器中设置标志的机制。 另一个翻译选项可能是短语“围绕零旋转/翻转/旋转”。 与“携带”相比,它更好地反映了“包装”的含义,因为 显示从正向负溢出时数字的过渡。 但是,事实证明,这些单词在测试读者的文本中看起来并不常见。 为简单起见,将来我们将“转移”一词作为“包装”一词的翻译。

C语言(和C ++)的编译器在其工作中越来越多地受到不确定行为的概念的指导-行为对于程序的某些操作行为不受标准的约束,并且在生成目标代码时,编译器有权从程序未执行此类操作的假设出发进行操作。 许多程序员反对这种方法,因为在这种情况下,生成的代码可能无法像预期的程序作者那样工作。 随着编译器使用更复杂的优化方法(可能基于不确定行为的概念),此问题变得更加严重。

在这种情况下,指示带符号整数溢出的示例。 大多数C开发人员为使用附加代码表示整数的机器编写代码,并且此表示形式中的加法和减法以完全相同的方式(无符号算术)实现。 如果两个带正负号的正整数之和溢出(即,它变得大于类型可容纳的整数),则处理器将返回一个值,该值被解释为带正负号的二进制补码,将被视为负数。 这种现象被称为“转移”,因为达到值范围上限的结果被“转移”并从下边界开始。

因此,有时您可以在C中看到以下代码:

int b = a + 1000; if (b < a) { //  puts("input too large!"); return; } 

if语句的任务是检测溢出情况(在这种情况下,它将在变量a的值加上1000之后发生)并报告错误。 问题在于,在C中,有符号整数溢出是未定义行为的情况之一。 一段时间以来,编译器一直认为这样的条件是错误的:如果将1000(或任何其他正数)加到另一个数字上,则结果不能小于初始值。 如果发生溢出,则存在未定义的行为,并且不允许这样做已经(显然)是程序员的关注点。 因此,编译器可以决定可以出于优化目的而完全删除条件运算符(毕竟,条件始终为false,不会影响任何内容,因此可以不使用它)。

问题在于,通过这种优化,编译器删除了程序员专门添加的检查,以检测未定义的行为并对其进行处理。 在这里,您可以了解实际情况。 (注意:托管该示例的godbolt.org网站非常酷!您可以编辑代码,然后立即查看不同的编译器如何处理它,并且其中有很多。实验!)。 请注意,如果您将类型更改为unsigned,编译器不会删除对溢出的检查,因为定义了C中unsigned溢出的行为(更确切地说,结果是使用unsigned算术传递的,因此实际上不会发生溢出)。

那是错的吗? 有人说是的,尽管很明显许多编译器开发人员认为此决定是合法的。 如果我理解正确,那么溢出期间传输的支持者(编辑:与实现有关)的主要参数如下:

  • 溢出是一种有用的行为。
  • 迁移是程序员期望的行为。
  • 不确定的溢出行为的语义没有提供明显的优势。
  • 用于未定义行为的C语言标准允许实现“完全忽略情况,结果将是不可预测的”,但这并没有赋予编译器基于根本不会发生未定义行为的情况来优化代码的权利。

让我们依次分析每个项目:

溢出迁移-有用的行为?

迁移主要在您需要跟踪已经发生的溢出时很有用。 (如果还有其他问题可以通过传输解决,而不能使用无符号整数变量解决,那么我将无法立即回忆起此类示例,并且我怀疑这些示例很少)。 尽管传递确实简化了使用错误地溢出的变量的问题,但它绝对不是万能药(记住两个未知量与一个未知符号的乘法或加法)。

在平凡的情况下,当传输仅允许您跟踪已发生的溢出时,也不难事先知道它是否会发生。 我们的示例可以重写如下:

 if (a > INT_MAX - 1000) { //    puts("input too large!"); return; } int b = a + 1000; 

即,您可以检查总和是否超过类型适合的最大数目,而不是计算总和然后确定是否发生溢出,而是检查结果的数学一致性。 (如果两个操作数的符号未知,则验证将非常复杂,但在传输过程中也同样适用)。

考虑到所有这些,我发现论点无法令人信服,在大多数情况下,转移是有用的。

迁移是程序员期望的行为吗?

这个论点很难争论,因为很明显至少某些 C程序员的代码假定传输语义带有符号整数溢出。 但是仅凭这一事实不足以认为这种语义是可取的(请注意,某些编译器允许您在必要时启用它)。

一个明显的问题解决方案(程序员期望此行为)是假设没有未定义的行为,使编译器在优化代码时发出警告。 不幸的是,正如我们在Godbolt.org上的示例中使用上面的链接所看到的那样,编译器并不总是这样做(Gcc 7.3版-是,但8.1版-否,所以要退一步)。

不确定的溢出行为的语义是否没有明显的优势?

如果此说明在所有情况下都是正确的,那么它将成为一个有力的论据,支持编译器默认情况下应遵守传输语义的事实,因为即使从技术角度来看该机制不正确,也可能允许进行溢出检查,尽管这是因为它可以用在可能损坏的代码中。

我认为普通C程序中的这种优化(消除数学上矛盾的条件的检查)通常可以忽略不计,因为它们的作者追求最佳性能并且仍然手动优化代码:也就是说,很明显, 如果if语句包含条件,这将永远不是真的,程序员可能会自己删除它。 实际上,我发现在一些研究中,这种优化的有效性受到质疑,测试并在控制测试的框架内几乎没有意义。 但是,尽管这种优化几乎永远不会在C语言中带来优势,但是代码生成器和编译器优化在大多数情况下是通用的,可以在其他语言中使用-对于他们而言,此结论可能是错误的。 让我们采用C ++语言的传统,即依靠优化器删除模板代码中的多余结构,而不是手动执行。 但是有些语言已由传输器转换为C,并且其中的冗余代码也由C编译器进行了优化。

另外,即使您继续检查溢出,即使在使用附加代码的机器上,传送整数变量的直接成本也不会是最小的事实。 例如,Mips体系结构只能在固定大小(32位)的寄存器中执行算术运算。 通常, short int类型的大小为16位,而char -8位; 当将这些类型之一的变量存储在寄存器中时,其大小将扩大,并且为了正确传输它,有必要执行至少一项附加操作,并可能使用附加寄存器(以容纳相应的位掩码)。 我必须承认,我很长一段时间都没有处理过Mips的代码,所以我不确定这些操作的确切成本,但是我确定它不是零,并且在其他RISC体系结构上也会出现相同的问题。

语言标准是否禁止在体系结构中使用变量包装?

如果您看,这个论点特别弱。 其实质是,该标准据说允许实现(编译器)仅在有限的程度上解释“不确定行为”。 在标准本身的案文中(在主张移交的主张的那个片段中),有以下说法(这是“不定行为”一词定义的一部分):

注意: 未定义的行为可能采取完全忽略情况的形式,而结果将是不可预测的,...

想法是,“完全忽略情况”一词并不表示不会发生导致未定义行为的事件(例如,加法期间溢出),但如果确实如此,则编译器应继续工作,就像在从来没有发生过,但还要考虑到如果他向处理器发送执行该操作的请求的结果(换句话说,就像源代码以一种简单明了的方式转换为机器代码一样)。

首先,应该注意的是,根据标准简介中提到的ISO指令,此文本是作为“注释”给出的,因此不是规范性的(也就是说,它不能规定某些内容):

根据ISO / IEC指令的第3部分,本序言,正文,注释,脚注和示例的介绍也仅用于提供信息。

由于此“不确定行为”段落是一个注释,因此不作任何规定。 请注意,“不定行为”的当前定义是:

因使用了无法忍受或不正确的软件设计或不正确的数据而引起的行为, 本国际标准对此不施加任何要求

我强调了主要思想:对不确定的行为不加任何要求。 注释中的“可能的不确定行为类型”列表仅包含示例,不能作为最终的处方。 短语“不提出要求”不能另外解释。

一些人发展了这一论点,认为不管语言是什么文本,语言委员会在制定这些词时都意味着行为总体上应与运行该程序的硬件架构相对应,这尽可能暗示了幼稚的翻译。变成机器代码。 尽管我还没有看到任何证据(例如历史文献)支持这一论点,但这可能是正确的。 但是,即使是这样,该语句也不适用于当前版本的文本。

最后的想法

赞成转让的论点在很大程度上是站不住脚的。 如果我们将它们结合起来,可能会得到最有力的论据:经验不足的程序员(他们不了解C语言的复杂性和其中的不确定行为)有时会期望转移,并且它不会降低性能-尽管后者在所有情况下都不正确,并且第一部分没有定论如果单独考虑。

就个人而言,我更希望阻塞(陷阱)而不是包装溢出。 也就是说,程序会崩溃,并且无法继续运行-行为不确定或结果可能不正确,因为在两种情况下均会出现漏洞。 这样的解决方案当然会稍微降低大多数(?)架构的性能,尤其是在x86上,但是,另一方面,溢出错误将立即被识别出来,并且一路使用它们将无法利用或获得不正确的结果。程序。 另外,从理论上讲,使用这种方法的编译器可以安全地删除冗余的溢出检查,因为它肯定不会发生,尽管如我所见,Clang和GCC都没有利用这个机会。

幸运的是,中断和移植都是在我最常使用的编译器GCC中实现的。 要在模式之间切换,分别使用-ftrapv-fwrapv命令行参数。

当然,有许多动作会导致未定义的行为-整数溢出只是其中之一。 我完全不认为将所有这些情况解释为不确定的行为是有用的,并且我确信在许多特定情况下,语义应由语言确定,或者至少应由实现方式自行决定。 而且,我担心编译器制造商会过度自由地解释这一概念:如果编译器的行为不符合开发人员的直觉想法,尤其是那些亲自阅读标准文本的开发人员,则可能导致真正的错误; 如果在这种情况下性能提升可忽略不计,则最好放弃这种解释。 在以下其中一篇文章中,我可能会研究其中一些问题。

补编(2018年8月24日)

我意识到上面的许多内容可以写得更好。 在下面,我简要总结并解释我的话,并补充一些小意见:

  • 我并没有说过无限行为更适合进行溢出-而是在实践中,转移并不比无限行为好得多 。 特别是,在第一种情况下会出现安全问题,在第二种情况下会发生安全问题-我敢打赌,由未及时捕获到的溢出(由编译器负责删除错误检查的那些漏洞)引起的许多漏洞实际上是由-由于结果的传输,而不是由于与溢出相关的不确定行为。
  • 传输的唯一真正优点是不会删除溢出检查。 尽管通过这种方式可以保护代码免受某些攻击情形的影响,但仍然有可能根本不会对某些溢出进行检查(即程序员将忘记添加此类检查)并且不会被注意到。
  • 如果安全问题不是那么重要,并且程序的高速发展成为首要任务,那么至少在某些情况下,未定义的行为将提供更多有利可图的优化并极大地提高生产率。 另一方面,如果安全性至上,则移植将充满漏洞。
  • 这意味着,如果您在中断,转移和未定义的行为之间进行选择,则很少有任务可以使用转移。
  • 至于对已发生的溢出的检查,我认为离开它们是有害的,因为这会产生错误的印象,即它们会起作用并且将一直起作用。 中断溢出可以避免此问题; 适当的警告-减轻它。
  • 我认为,任何编写安全性关键代码的开发人员在理想情况下都应该对他所使用的语言的语义有很好的掌握,并且要意识到其缺陷。 对于C,这意味着您需要了解溢出的语义和未定义行为的精妙之处。 令人遗憾的是,有些程序员还没有发展到这一水平。
  • 我曾经声称“大多数C程序员都希望迁移是默认行为”,但我不知道这样做的证据。 (在这篇文章中,我写了“一些程序员”,因为我从现实生活中知道了几个例子,而且总的来说,我怀疑有人会对此提出质疑)。
  • 有两个不同的问题:C语言标准要求什么以及编译器应实现什么。 我(通常)喜欢标准定义未定义溢出行为的方式。 在本文中,我将讨论编译器应该做什么。
  • 当溢出中断时,无需检查所有操作。 理想情况下,采用这种方法的程序在数学规则方面要么表现一致,要么停止工作。 在这种情况下,“临时溢出”的存在成为可能,这不会导致出现错误的结果。 然后可以将表达式a + b-b和表达式(a * b)/ b都优化为a (在传输过程中也可以使用前者,但不再存在后者)。

注意事项 文章的翻译在作者的允许下在博客上发布。 原文:戴文·麦考尔(Davin McCall)“ 包装整数溢出不是一个好主意 ”。

PVS-Studio团队的其他相关链接:

  1. 安德烈·卡波夫(Andrey Karpov)。 未定义的行为比您想像的要近
  2. Will Dietz,Peng Li,John Regehr和Vikram Adve。 了解C / C ++中的整数溢出
  3. V1026。 该变量在循环中递增。 如果有符号整数溢出,则会发生未定义的行为
  4. 堆栈溢出 在C ++中,有符号整数溢出仍然是未定义的行为吗?

Source: https://habr.com/ru/post/zh-CN427683/


All Articles