一种改进的用于验证安全C字符串程序的方法

《Array》：An improved method for verifying safe C string programs

　　李学健|建行安徽大学，计算机科学与技术学院，合肥，230601，安徽，中国

摘要
自动化程序验证工具通常受到其集成自动定理证明器（ATPs）能力的限制，特别是在程序涉及字符串操作时，这带来了重大挑战。为了解决这个问题，本文提出了一种改进的转换方法，将字符串验证条件转换为SMT-LIB格式，该方法基于一个集成了满足性模理论（SMT）求解器的原型系统。在应用断言补全的基础上，所提出的方法进一步采用了两种策略：蕴含结果分割和否定，来重构验证条件，旨在降低ATP的验证复杂性。实验结果表明，使用这种方法转换的验证条件显著减少了ATP无法证明定理的情况。

1. 引言
程序验证作为一种关键技术，利用程序逻辑推理方法来确认程序的正确性。其中，基于定理证明的程序验证技术以“系统满足其规范”作为基本推理前提，结合相应的逻辑规则，并系统地生成一系列通过演绎推理需要验证的证明条件[1]。Floyd-Hoare逻辑[2]是此类推理规则的典型代表。该逻辑系统提出了Hoare逻辑三元组，并构建了一个完整的程序验证理论和推理规则框架，涵盖了赋值语句公理、条件语句规则、循环语句规则等，为程序正确性的形式化验证提供了理论基础。具体来说，Hoare逻辑三元组{P}s{Q}表示如果在满足前提P（一阶逻辑形式的断言）的条件下执行程序片段s，则后置条件Q（也是一阶逻辑形式的断言）必须成立。
基于自动定理证明器的程序验证工具利用Hoare逻辑或其他演绎逻辑作为其公理或规则基础。它们通过将程序源代码与带注释的断言相结合来进行程序正确性证明。带注释的断言用于精确描述程序在特定执行点应满足的属性。在验证过程中，通过应用相应的演绎公理或规则生成一系列验证条件。为了实现自动化求解，这些验证条件通常被转换为自动定理证明器可以识别的逻辑形式，并提交给它们进行满足性检查，从而间接验证程序的正确性。在国内，已经进行了大量关于安全编程语言设计和实现的研究[3]、[4]、[5]。独立开发的程序验证工具，如CPV，在验证处理可变数据结构的程序的正确性方面取得了一系列成果[6]、[7]、[8]。在国际上，广泛使用的程序验证器包括Dafny[9]和Why3[10]。在自动定理证明器领域，Z3[11]因其高效性和广泛适用性而备受推崇。其他主流的自动定理证明器包括CVC4[12]和Yices2[13]。随着技术的不断进步，现有自动定理证明器的验证能力显著提高，有效推动了形式化验证方法的发展和应用。
与半自动交互式定理证明工具（如Coq[14]和Isabelle/HOL[15]）相比，自动化程序验证显著减少了人工干预，并消除了频繁手动构建证明过程的需要，从而有效提高了证明效率。然而，在实际的程序验证过程中，仍然存在许多不可判定问题。此外，当前的自动定理证明器在特定领域的证明能力方面存在局限性：例如，Z3在处理浮点数相关问题时表现不佳，对涉及量词和数组的混合问题的支持较弱；CVC4在解决非线性实数和整数相关问题时的性能未能完全满足用户需求；Yices2在解决量词问题时也存在显著缺陷。
为了继续验证程序的相关属性，目前的常见做法是对不可解决的属性或程序进行适应性修改；在极端情况下，甚至可能需要放弃对该属性或程序的验证功能。以字符串属性验证为例，由于Z3的原生支持有限，许多定制的字符串属性和结构在验证过程中容易变得不可判定。
具体来说，Z3的原生支持限制体现在C字符串的两个问题模式中：（1）无界量词实例化：传统验证器将C字符串建模为字符数组。验证字符串等价属性需要使用全量词（例如，?i.A[i]=B[i]）。由于没有严格的数值界限，Z3的数组理论难以高效地实例化这些量词，经常导致状态空间爆炸并返回“未知”结果。（2）缺乏关系支持：原生SMT理论缺乏对无界内存缓冲区上的字典顺序比较（例如，<或≤）的直接支持，使得标准c库断言对求解器来说本质上是不可判定的。
为了有效应对现有研究中的挑战，本文提出了以下两种改进策略，旨在在z3自动定理证明器有限的求解能力基础上，最大化验证字符串程序正确性的效率。具体的改进方案如下：
首先，在验证过程中引入了一种结合验证信息补全、条件简化和重构的联合优化机制。该方法系统地完成隐式验证信息，并对初始验证条件进行多层次抽象和逻辑简化，从而显著降低验证条件的复杂性。这一策略专注于解决由于信息缺失或冗余导致的低解决效率问题，为后续的自动化验证奠定了基础。
其次，对于从程序证明侧到自动定理证明器求解侧的验证条件转换过程，提出了一种改进的字符串逻辑表达式转换方法。该方法通过优化转换规则和约束传播机制，有效减少了转换后验证条件中复杂逻辑结构（如量词、数组和谓词）的频率。实验表明，这种改进可以显著降低目标逻辑表达式的认知复杂性，从而提高z3解决字符串程序验证问题的成功率。

本文的具体贡献总结如下：
方法论：我们引入了一种结合断言补全、无关断言减少和结果分割的联合优化机制，严格控制验证条件的结构复杂性。
技术上：我们提出了一种语义驱动的转换映射，将c字符串操作安全地编码为smt-lib约束，有效缓解了原生数组理论的无界量词限制。
实证上：通过对标准c库函数的广泛评估，我们证明了所提出的方法在大幅提高自动化验证成功率的同时，显著减少了求解器的时间消耗。

本文的结构如下：引言部分介绍了程序验证领域的相关研究背景。第2节概述了当前验证字符串程序正确性工作的不足，并提出了一个改进的字符串程序验证框架。第3节介绍了所提出的断言补全和验证条件优化方法。第4节详细阐述了字符串验证条件的转换方法。第5节展示了本文提出的方法的实验验证。第6节总结了本文的研究内容。

2. 当前研究现状
safe c的行为规范语言（scsl）[5]是c99标准的一个安全子集，它参考acsl[16]设计，为safe c程序提供形式化注释支持。为了验证程序中复杂数据结构（如字符串）的属性和操作正确性，scsl引入了z3不原生支持的各种数据类型和操作。这些扩展通常涉及高阶谓词逻辑、数组操作和量词理论的混合应用。然而，z3在处理涉及全量词和数组理论耦合的一阶逻辑公式时，在约束求解方面仍有显著限制，这已成为限制程序验证技术发展的关键瓶颈之一。
在scsl中的字符串属性验证实践中，上述问题尤为突出。由于c语言缺乏原生字符串类型，传统实现使用字符数组（或字符指针）来表示字符串序列。scsl的早期版本通过数组类型定义字符串注释，导致断言的可读性较差，难以支持动态字符串操作（如连接）的验证。为了解决这个问题，scsl引入了一种逻辑字符串类型（string = char[] x int），使用记录类型结构，其中一个字段存储字符数组，另一个字段记录数组长度。然而，这种实现仍然基于静态字符数组，未能完全解决动态字符串验证的固有缺陷。在自动定理证明层面，scsl和z3都依赖于数组理论进行字符串属性验证。然而，z3的数组理论实现（仅提供基本的选择/存储操作）在处理字符串片段属性（如连接操作中的位置等价关系）时表现不佳，尤其是在全量词约束存在的情况下，解决效率显著降低。
具体来说，当前的验证方法存在以下技术限制：
（1）数组理论的表达能力不足：z3的数组理论通过选择/存储操作实现元素访问和更新，但在表达字符串片段的等价关系时表现不佳。例如，在字符串连接验证中，需要显式构建全量词约束来描述位置对应关系。然而，z3解决涉及全量词的数组问题的能力有限，经常导致超时或不可判定。
（2）自定义代数数据类型的开销：逻辑字符串采用二元对结构（带有内容和长度的数组），需要在z3中定义为代数数据类型。特别是，解决此类类型的满足性需要注入额外的辅助约束，引入辅助信息通常涉及全量词和复杂的谓词逻辑，进一步增加了z3的求解负担。
（3）字符值抽象层次限制：基于整数数组的字符串表示将验证范围限制在结构属性上，无法直接处理涉及特定字符值的验证要求（如字符编码约束和子字符串匹配），这限制了验证方法的适用场景。
为了解决上述挑战，本研究提出了一种改进的字符串程序验证方法。该方法将验证条件优化策略与z3str4[17]字符串理论相结合，通过以下技术方法提高验证效率：首先，设计了一种基于专用字符串理论的验证条件编码方案，以减少对通用数组理论的依赖；其次，优化了量词实例化策略，以减轻全量词引入的组合爆炸风险；最后，实现了字符级和结构级的层次处理机制。基于上述方法，我们在scsl注释语言和z3求解器的集成原型系统上构建了一个完整的字符串程序验证框架（如图1所示）。

下载：下载高分辨率图像（215kb）
下载：下载全尺寸图像
图1. 字符串程序验证框架。

3. 断言补全和验证条件优化
使用符号语言定义描述性字符串断言对于有效验证程序中字符串操作和结构属性的正确性是必要的。第a节详细阐述了scsl中定义的字符串逻辑表达式，并对其实际应用进行了合理的改进和优化。第b节重点介绍了断言补全方法，旨在完成验证所需的各种断言，确保验证过程的全面性和准确性。第c节深入探讨了验证条件优化方法，通过采用无关断言删除和验证条件重构等策略，有效减少了验证过程中的计算负担和复杂性，从而提高了验证效率。

3.1. 字符串断言的注释语法
字符串注释断言可以分为两部分：一部分涉及数组或指针操作，另一部分来源于字符串库函数（如string.h中的strcat函数）。注释过程中使用的表达式被定义为字符串逻辑表达式（sles）。 为了有效应对现有研究中的挑战，本文提出了以下两种改进策略，旨在在z3自动定理证明器有限的求解能力基础上，最大化验证字符串程序正确性的效率。具体的改进方案如下： 首先，在验证过程中引入了一种结合验证信息补全、条件简化和重构的联合优化机制。该方法系统地完成隐式验证信息，并对初始验证条件进行多层次抽象和逻辑简化，从而显著降低验证条件的复杂性。这一策略专注于解决由于信息缺失或冗余导致的低解决效率问题，为后续的自动化验证奠定了基础。 其次，对于从程序证明侧到自动定理证明器求解侧的验证条件转换过程，提出了一种改进的字符串逻辑表达式转换方法。该方法通过优化转换规则和约束传播机制，有效减少了转换后验证条件中复杂逻辑结构（如量词、数组和谓词）的频率。实验表明，这种改进可以显著降低目标逻辑表达式的认知复杂性，从而提高z3解决字符串程序验证问题的成功率。 本文的具体贡献总结如下： 方法论：我们引入了一种结合断言补全、无关断言减少和结果分割的联合优化机制，严格控制验证条件的结构复杂性。 技术上：我们提出了一种语义驱动的转换映射，将c字符串操作安全地编码为smt-lib约束，有效缓解了原生数组理论的无界量词限制。 实证上：通过对标准c库函数的广泛评估，我们证明了所提出的方法在大幅提高自动化验证成功率的同时，显著减少了求解器的时间消耗。 本文的结构如下：引言部分介绍了程序验证领域的相关研究背景。第2节概述了当前验证字符串程序正确性工作的不足，并提出了一个改进的字符串程序验证框架。第3节介绍了所提出的断言补全和验证条件优化方法。第4节详细阐述了字符串验证条件的转换方法。第5节展示了本文提出的方法的实验验证。第6节总结了本文的研究内容。 2. 当前研究现状 safe c的行为规范语言（scsl）[5]是c99标准的一个安全子集，它参考acsl[16]设计，为safe c程序提供形式化注释支持。为了验证程序中复杂数据结构（如字符串）的属性和操作正确性，scsl引入了z3不原生支持的各种数据类型和操作。这些扩展通常涉及高阶谓词逻辑、数组操作和量词理论的混合应用。然而，z3在处理涉及全量词和数组理论耦合的一阶逻辑公式时，在约束求解方面仍有显著限制，这已成为限制程序验证技术发展的关键瓶颈之一。 在scsl中的字符串属性验证实践中，上述问题尤为突出。由于c语言缺乏原生字符串类型，传统实现使用字符数组（或字符指针）来表示字符串序列。scsl的早期版本通过数组类型定义字符串注释，导致断言的可读性较差，难以支持动态字符串操作（如连接）的验证。为了解决这个问题，scsl引入了一种逻辑字符串类型（string=char[] x int），使用记录类型结构，其中一个字段存储字符数组，另一个字段记录数组长度。然而，这种实现仍然基于静态字符数组，未能完全解决动态字符串验证的固有缺陷。在自动定理证明层面，scsl和z3都依赖于数组理论进行字符串属性验证。然而，z3的数组理论实现（仅提供基本的选择 存储操作）在处理字符串片段属性（如连接操作中的位置等价关系）时表现不佳，尤其是在全量词约束存在的情况下，解决效率显著降低。 具体来说，当前的验证方法存在以下技术限制： （1）数组理论的表达能力不足：z3的数组理论通过选择 存储操作实现元素访问和更新，但在表达字符串片段的等价关系时表现不佳。例如，在字符串连接验证中，需要显式构建全量词约束来描述位置对应关系。然而，z3解决涉及全量词的数组问题的能力有限，经常导致超时或不可判定。 （2）自定义代数数据类型的开销：逻辑字符串采用二元对结构（带有内容和长度的数组），需要在z3中定义为代数数据类型。特别是，解决此类类型的满足性需要注入额外的辅助约束，引入辅助信息通常涉及全量词和复杂的谓词逻辑，进一步增加了z3的求解负担。 （3）字符值抽象层次限制：基于整数数组的字符串表示将验证范围限制在结构属性上，无法直接处理涉及特定字符值的验证要求（如字符编码约束和子字符串匹配），这限制了验证方法的适用场景。 为了解决上述挑战，本研究提出了一种改进的字符串程序验证方法。该方法将验证条件优化策略与z3str4[17]字符串理论相结合，通过以下技术方法提高验证效率：首先，设计了一种基于专用字符串理论的验证条件编码方案，以减少对通用数组理论的依赖；其次，优化了量词实例化策略，以减轻全量词引入的组合爆炸风险；最后，实现了字符级和结构级的层次处理机制。基于上述方法，我们在scsl注释语言和z3求解器的集成原型系统上构建了一个完整的字符串程序验证框架（如图1所示）。 下载：下载高分辨率图像（215kb） 下载：下载全尺寸图像 图1. 字符串程序验证框架。 3. 断言补全和验证条件优化 使用符号语言定义描述性字符串断言对于有效验证程序中字符串操作和结构属性的正确性是必要的。第a节详细阐述了scsl中定义的字符串逻辑表达式，并对其实际应用进行了合理的改进和优化。第b节重点介绍了断言补全方法，旨在完成验证所需的各种断言，确保验证过程的全面性和准确性。第c节深入探讨了验证条件优化方法，通过采用无关断言删除和验证条件重构等策略，有效减少了验证过程中的计算负担和复杂性，从而提高了验证效率。 3.1. 字符串断言的注释语法>为了有效应对现有研究中的挑战，本文提出了以下两种改进策略，旨在在z3自动定理证明器有限的求解能力基础上，最大化验证字符串程序正确性的效率。具体的改进方案如下：
首先，在验证过程中引入了一种结合验证信息补全、条件简化和重构的联合优化机制。该方法系统地完成隐式验证信息，并对初始验证条件进行多层次抽象和逻辑简化，从而显著降低验证条件的复杂性。这一策略专注于解决由于信息缺失或冗余导致的低解决效率问题，为后续的自动化验证奠定了基础。
其次，对于从程序证明侧到自动定理证明器求解侧的验证条件转换过程，提出了一种改进的字符串逻辑表达式转换方法。该方法通过优化转换规则和约束传播机制，有效减少了转换后验证条件中复杂逻辑结构（如量词、数组和谓词）的频率。实验表明，这种改进可以显著降低目标逻辑表达式的认知复杂性，从而提高z3解决字符串程序验证问题的成功率。

本文的具体贡献总结如下：
方法论：我们引入了一种结合断言补全、无关断言减少和结果分割的联合优化机制，严格控制验证条件的结构复杂性。
技术上：我们提出了一种语义驱动的转换映射，将c字符串操作安全地编码为smt-lib约束，有效缓解了原生数组理论的无界量词限制。
实证上：通过对标准c库函数的广泛评估，我们证明了所提出的方法在大幅提高自动化验证成功率的同时，显著减少了求解器的时间消耗。

本文的结构如下：引言部分介绍了程序验证领域的相关研究背景。第2节概述了当前验证字符串程序正确性工作的不足，并提出了一个改进的字符串程序验证框架。第3节介绍了所提出的断言补全和验证条件优化方法。第4节详细阐述了字符串验证条件的转换方法。第5节展示了本文提出的方法的实验验证。第6节总结了本文的研究内容。

2. 当前研究现状
safe c的行为规范语言（scsl）[5]是c99标准的一个安全子集，它参考acsl[16]设计，为safe c程序提供形式化注释支持。为了验证程序中复杂数据结构（如字符串）的属性和操作正确性，scsl引入了z3不原生支持的各种数据类型和操作。这些扩展通常涉及高阶谓词逻辑、数组操作和量词理论的混合应用。然而，z3在处理涉及全量词和数组理论耦合的一阶逻辑公式时，在约束求解方面仍有显著限制，这已成为限制程序验证技术发展的关键瓶颈之一。
在scsl中的字符串属性验证实践中，上述问题尤为突出。由于c语言缺乏原生字符串类型，传统实现使用字符数组（或字符指针）来表示字符串序列。scsl的早期版本通过数组类型定义字符串注释，导致断言的可读性较差，难以支持动态字符串操作（如连接）的验证。为了解决这个问题，scsl引入了一种逻辑字符串类型（string = char[] x int），使用记录类型结构，其中一个字段存储字符数组，另一个字段记录数组长度。然而，这种实现仍然基于静态字符数组，未能完全解决动态字符串验证的固有缺陷。在自动定理证明层面，scsl和z3都依赖于数组理论进行字符串属性验证。然而，z3的数组理论实现（仅提供基本的选择/存储操作）在处理字符串片段属性（如连接操作中的位置等价关系）时表现不佳，尤其是在全量词约束存在的情况下，解决效率显著降低。
具体来说，当前的验证方法存在以下技术限制：
（1）数组理论的表达能力不足：z3的数组理论通过选择/存储操作实现元素访问和更新，但在表达字符串片段的等价关系时表现不佳。例如，在字符串连接验证中，需要显式构建全量词约束来描述位置对应关系。然而，z3解决涉及全量词的数组问题的能力有限，经常导致超时或不可判定。
（2）自定义代数数据类型的开销：逻辑字符串采用二元对结构（带有内容和长度的数组），需要在z3中定义为代数数据类型。特别是，解决此类类型的满足性需要注入额外的辅助约束，引入辅助信息通常涉及全量词和复杂的谓词逻辑，进一步增加了z3的求解负担。
（3）字符值抽象层次限制：基于整数数组的字符串表示将验证范围限制在结构属性上，无法直接处理涉及特定字符值的验证要求（如字符编码约束和子字符串匹配），这限制了验证方法的适用场景。
为了解决上述挑战，本研究提出了一种改进的字符串程序验证方法。该方法将验证条件优化策略与z3str4[17]字符串理论相结合，通过以下技术方法提高验证效率：首先，设计了一种基于专用字符串理论的验证条件编码方案，以减少对通用数组理论的依赖；其次，优化了量词实例化策略，以减轻全量词引入的组合爆炸风险；最后，实现了字符级和结构级的层次处理机制。基于上述方法，我们在scsl注释语言和z3求解器的集成原型系统上构建了一个完整的字符串程序验证框架（如图1所示）。

下载：下载高分辨率图像（215kb）
下载：下载全尺寸图像
图1. 字符串程序验证框架。

3. 断言补全和验证条件优化
使用符号语言定义描述性字符串断言对于有效验证程序中字符串操作和结构属性的正确性是必要的。第a节详细阐述了scsl中定义的字符串逻辑表达式，并对其实际应用进行了合理的改进和优化。第b节重点介绍了断言补全方法，旨在完成验证所需的各种断言，确保验证过程的全面性和准确性。第c节深入探讨了验证条件优化方法，通过采用无关断言删除和验证条件重构等策略，有效减少了验证过程中的计算负担和复杂性，从而提高了验证效率。

3.1. 字符串断言的注释语法
字符串注释断言可以分为两部分：一部分涉及数组或指针操作，另一部分来源于字符串库函数（如string.h中的strcat函数）。注释过程中使用的表达式被定义为字符串逻辑表达式（sles）。>这些逻辑表达式仅在程序验证期间用于证明验证条件，并且对程序的实际执行没有影响。在注释中，对于字符串类型（STRING）的声明，可以先声明一个逻辑字符指针类型的变量，然后可以使用两个字符串逻辑表达式将其定义为字符串：string(str,m) 和 pstring(str,m)。具体来说，string(str,m) 用于描述长度至少为 m 的字符串 str，而 pstring(str,m) 用于描述长度为 m 的字符串 str，并指定第 (m+1) 个位置是字符串结束标识符 ?0。SCSL 有几个内置的逻辑表达式，其中 ?length 和 ?offset 属于 SCSL 的内置指针操作集 [6]。在指针三元组的内存抽象模型中，?length 用于表示指针所指向的内存块的长度，而 ?offset 用于表示当前指针在内存块中的偏移位置。表 1 列出了一系列针对字符串的逻辑表达式。它们的核心功能在于程序注释阶段，用于精确描述字符串的相关属性或特定操作。值得注意的是，表中显示的字符串关系逻辑表达式仅涵盖两种类型的关系：小于和等于运算符。

以图 2 中基于 string.h 库函数 strspn 的验证为例，下面详细说明了当前字符串的逻辑表达式如何有效地描述程序中字符串的属性。这里，prefunction 协议和 postfunction 协议分别表示调用或执行函数之前的条件和之后的条件。具体来说，在调用或执行字符串连接库函数之前，prefunction 条件应处于可满足状态；执行后，postfunction 条件也应保持可满足状态。在 strspn 的前提条件中，pstring 描述了两个长度分别为 m 和 n 的字符串 olds 和 oldaccept。这是因为在程序执行过程中 s 和 accept 指针的位置会发生变化；因此，提前保存这些变量的初始状态是重要的。在后置条件中，?result 是 SCSL 的一个内置元素，表示函数的返回值；逻辑表达式 membership 用于描述 olds 中的字符是否包含在 oldaccept 中。此外，declare 中声明的变量是非局部变量，可能会被函数修改。函数协议明确指出，对于长度分别为 m 和 n 的两个字符串，在调用 strspn 函数后，返回值必须等于前者字符串中属于后者字符串的连续字符的数量。这个数量应在 0 到 m 之间。如果超出这个范围，则表示函数中存在错误。

表 1. 字符串的逻辑表达式
| 操作 | 描述 |
|-----------------|-----------------------------------------|
| string (str, m) | 描述长度至少为 m 的字符串 |
| pstring (str, m) | 描述长度为 m 的字符串 |
| prefix (str, m) | 取字符串的前 m 个字符 |
| suffix (str, m) | 取字符串的最后 m 个字符 |
| membership (str, c) | 确定字符串 str 是否包含字符 c |
| contains (str, cstr) | 确定 cstr 是否是字符串 str 的子字符串 |
| index (str, cstr) | 计算 “str” 中 “cstr” 的第一次出现 |
| strlen(str) | 计算字符串的长度 |
| operator+ (strL, strR) | 描述字符串连接 |
| operator== (strL, strR) | 确定两个字符串是否相等 |
| operator< (strL, strR) | 确定字符串 strL 是否小于 strR |

图 2. strspn 函数的协议。

图 3. strcat 函数的后置条件。

3.2. 断言完成的分析
对字符串注释断言之间依赖关系的深入分析表明，完成缺失的断言可以为程序验证器提供强有力的支持，帮助他们证明由复杂逻辑表达式组成的验证条件。此外，在验证程序中字符串的特定属性时，自动定理证明器也可以由于这些完成的断言而提高验证效率。

3.2.1. 断言依赖性
在程序验证过程中，某些字符串逻辑表达式断言的验证信息的完整性依赖于其他相关断言。具体来说，这些断言包括它们必须满足的属性描述以及构建它们所需的子断言集。这些元素共同作用，以确保断言的逻辑完整性和验证有效性。在处理复杂逻辑表达式时，需要按照依赖关系逐层构建相关的断言。对于具有特殊属性的逻辑表达式，需要提供额外的辅助断言来描述相关变量之间的约束关系，以确保验证过程的严谨性和推导结果的可靠性。以下提供了断言依赖性的相关定义。

定义 1 断言依赖性
如果某个特定逻辑表达式需要基于其他断言的声明才有意义，则称该断言依赖于这些断言。其中一些断言是直接依赖关系，可以通过从内到外分析逻辑表达式获得；其他断言与特定逻辑表达式相关，由于它们的性质而具有特殊的变量关系。

以图 3 中 strcat 函数协议的后置条件为例，在使用逻辑表达式注释字符串连接时，不仅需要描述参与字符串连接操作的相关字符串指针的属性，还需要涵盖字符串连接和字符串相等性的特殊属性。具体来说，连接操作后的结果字符串的长度应等于参与连接的各个字符串的长度之和（即 t == m + n）。在演绎推理过程中，如果断言涉及指针操作，将生成一个指针三元组 oldest?=point(olddest?,?length(olddest),?offset(olddest))。随后需要进一步生成该三元组依赖的 ?length 和 ?offset 相关断言。如果 ?offset 没有明确注释，其默认值设置为 0。

定义 2 断言依赖抽象树
断言依赖抽象树（ADAT）是一种通过从外到内分析每个断言子句形成的抽象树状结构。以断言为根节点建立树状结构，此过程一直进行到子树中的某个节点是字符串声明或非字符串逻辑表达式的形式。此时，该子树分支的分析完成。

以图 3 中函数协议的后置条件中的 operator== 为例，通过依次分析注释点断言的组成，我们可以理解其断言依赖关系：operator== 依赖于 operator+ 和 pstring；operator+ 依赖于 string 和 pstring。通过将断言之间的依赖关系抽象为树状结构（如图 4 所示），断言之间的依赖关系更加清晰地呈现出来。在这种树结构中，父节点的验证依赖于子节点。这种层次关系有助于生成依赖于不同逻辑表达式的断言。其中，包含具有特殊属性的逻辑表达式的节点被强调以突出其重要性。

在整个分析过程中，使用临时变量连续存储分析过程中生成的值。一旦中间数据完成，就按顺序构建相关的断言。此外，为了全面描述变量之间的复杂约束关系，在分析阶段需要添加描述特殊变量之间关系的断言。这种方法的显著优势在于它能够自动推导和生成验证所需的断言，消除了手动注释的繁琐性和遗漏。此外，补充的附加信息为验证过程提供了更丰富的上下文支持，有助于提高验证的准确性和效率。

定义 3 断言记录表
为了防止重复生成现有的断言，需要一个表来记录当前生成的断言。如果断言已经存在，则可以避免再次生成它。断言记录表（ART）记录了当前程序点手动注释的断言以及通过断言依赖关系成功生成的断言。

以图 3 中字符串连接函数协议的后置条件为例，其逻辑表达式为 pstring (?result,t)== string(olddest,m) + pstring(oldsrc,n)。在对与字符串连接相关的断言进行依赖性分析时，共需要 5 个依赖断言。经过验证，其中 4 个断言已经手动注释，只有关键断言 t==m+n 需要自动生成。为了提高展示的简洁性和可读性，在展示过程中省略了中间推导中涉及的临时变量。

3.2.2. 算法设计
断言完成方法的核心在于处理更复杂的逻辑表达式，并通过细化断言信息为程序验证提供强有力的支持。具体的算法设计如下表所示。

表 2. 断言完成算法

步骤 1：对要验证的注释程序进行深入分析，并在函数入口点（function entry）、函数出口点（function exit）和循环点（即循环不变量 Loop）构建抽象断言记录表（ART），以记录在上述三个关键程序点注释的断言。ART 可以表示为：ART={ARTFEy,ARTFEt,ARTLoop}。

步骤 2：对三个程序 {ARTFEy,ARTFEt,ARTLoop} 中的断言点进行依赖性分析，并为相关断言构建抽象依赖分析表（ADAT），以澄清它们之间的依赖关系。

步骤 3：依次访问三个程序注释点 {ARTFEy,ARTFEt,ARTLoop} 中每个断言对应的 ADAT。对 ADAT 进行后序遍历，以确定节点表示的字符串逻辑表达式（SLE）是否已经存在于 ART 中。如果不存在，则生成 SLE 并将其添加到相应程序点的 ART 中。此外，进行深入分析以确定 SLE 中是否存在变量依赖关系。如果存在此类依赖关系且相关断言尚未包含在当前 ART 中，则应将其添加；如果已经存在，则继续后序遍历直到到达根节点。一旦分析完给定注释点的所有断言，就使用该时间点记录在表中的信息作为该点的注释。重复上述操作，直到所有程序注释点都被完全注释。

表 2. 断言完成算法。

3.3. 验证条件的优化
在基于 Hoare 规则进行演绎推理的过程中，程序验证器生成的验证条件以蕴含的形式表示，依赖于程序注释和各种程序语句。考虑到自动定理证明器的解决能力和验证时间消耗等关键因素，如果程序验证器不采取任何有效措施来处理这些验证条件，很可能会增加翻译和验证阶段的时间消耗，从而影响整体验证效率。本文提出的无关断言减少方法旨在有效减少验证时间并降低验证条件的复杂性。此外，当验证条件无法证明时，采用蕴含结果分解和蕴含结果否定方法来重构验证条件。严格的理论推导和实际验证表明，重构前后的验证条件在逻辑上是等价的，从而确保验证结果的准确性和可靠性。

3.3.1. 无关断言的减少
在基于演绎推理生成验证条件的过程中，其中包含大量先前推导出的断言信息。随着演绎推理的进行，大部分断言信息会保留在后续的验证条件中。然而，在程序验证的实际操作中，可能会出现验证条件包含许多与正在验证的属性无关的断言的情况。

以图 5 为例，程序语句仅涉及赋值语句 cp 和 src 的验证，但在生成的验证条件中有很多断言与这个语句无关。在图中，第3、6、15和19行是相关的断言，而其余的则是不相关的断言。在这样的验证条件下，如果可以移除不相关的断言，那么后续的翻译和验证过程的时间消耗将显著减少。值得注意的是，移除这些不相关的断言不会影响验证条件的满足性。相反，当这些不相关的断言具有高复杂性时，例如涉及非线性操作或全称量词时，它们会大大增加验证时间消耗，并对验证效率产生负面影响。为了解决上述问题，在为演绎推理中的不同程序语句生成验证条件时，可以采用以下优化策略：首先，对涉及该语句的相关变量进行深入分析，并明确识别这些变量以及在前件和后件中影响它们的其他变量。之后，只保留与这些变量相关的断言子句，并删除不相关的断言子句。在完成不相关断言的删除后，将简化的验证条件翻译并提交给自动定理证明器进行验证。值得注意的是，在后续的演绎推理过程中，仍然需要保留这些被删除的不相关断言，因为它们可能对后续验证条件的证明具有重要的断言信息价值。

为了定量估计这种复杂性的降低，考虑图5中所示的例子。通过仅隔离相关的断言，生成的VC从24个约束子句减少到仅4个基本子句，公式大小减少了大约83%。从质量上看，剪除这些冗余子句显著减少了提交给自动定理证明器的抽象语法树（AST）的深度。这直接减少了问题构造的实例化，例如对无关数组段的全称量词嵌套，这会严重降低SMT求解器的性能并经常引发不可判定性。

3.3.2. 蕴含关系的分解和否定
在程序验证过程中，当自动定理证明器无法直接解决或确定某个验证条件的满足性时，需要采取有针对性的措施来进一步简化验证条件，以提高验证效率和准确性。以下详细介绍了两种简化方法，其中分解方法在实际应用中通常被优先考虑。
(1) 分解。这种方法的核心思想是将验证条件的后件分解为多个子断言，然后分别验证前件是否可以蕴含每个子断言。具体来说，如果验证条件可以表示为蕴含关系P→(Q1∧Q2∧?∧Qn)，其中P是前件，Q1,Q2,…,Qn是后件的分解子断言，则需要验证n个子验证条件P→Q1, P→Q2, …, 和 P→Qn是否满足。如果所有子验证条件都满足，则可以确定原始命题是可满足的。推导过程可以正式表示为：
(1)P→(Q1∧Q2∧?∧Qn)
(2)??P∨(Q1∧Q2∧?∧Qn)
(3)?(?P∨Q1)∧(?P∨Q2)∧?∧(?P∨Qn)
(4)?(P→Q1)∧(P→Q2)∧?∧(P→Qn)

权衡和VC管理：虽然蕴含关系分解会线性增加子VC的总数，但这种权衡对于自动定理证明非常有利。像Z3这样的SMT求解器在解决数组上的非线性算术和量词实例化时，通常表现出指数级的最坏情况时间复杂度O(2^n)。将一个大小为n的复杂公式分解为k个子问题，从根本上将最坏情况的证明成本从O(2^n)改变为O(k?2^n/k)，有效地避免了状态空间爆炸。
为了管理生成多个VC的开销，我们的系统采用了一种动态回退机制：不随意应用蕴含关系分解。只有当定理证明器返回“未知”或超过原始复合VC的预定义时间阈值时，才会触发分解。

(2) 否定。与解决方法不同，当前件包含多个子断言时，可以尝试解决否定后的子断言与前件的合取的满足性。具体来说，对于验证条件P→(Q1∧Q2∧?∧Qn)，我们解决?(P→(Q1∧Q2∧?∧Qn)的满足性。如果这个合取是可满足的，那么表明原始命题并不总是正确的。推导过程可以正式表示为：
(5)P→(Q1∧Q2∧?∧Qn)
(6)??P∨(Q1∧Q2∧?∧Qn)
(7)??(P∧?(Q1∧Q2∧?∧Qn))
(8)??(P∧(?Q1∨?Q2∨?∨?Qn))
(9)??((P∧?Q1)∨(P∧?Q2)∨?∨(P∧?Qn))

以Z3定理证明器为例，它是一个基于求解满足性的定理证明工具。当使用Z3进行求解时，如果获得的模型包含一个特殊解，其中前件P为假，尽管此时蕴含关系P→Q自然成立，但这并不符合程序验证的目标（证明验证条件总是正确的）。因此，为了证明验证条件P→Q的始终正确的性质，通常需要将其转化为证明?(P→Q)或P∧?Q的不满足性。
从方程(1)到(9)的正式推导表明，VC的重构严格保持了逻辑等价性。从程序安全验证的角度来看，后件Q通常代表多个安全属性的合取，例如内存边界完整性和字符串结构有效性。

关于分解：转换(P→?i=1nQi)??i=1n(P→Qi)确保了验证各个安全子属性等同于验证原始的综合性属性。这种分解不会引入假阴性；如果在前提P下任何安全属性Qi被违反，相应的子VC将会失败，从而识别出安全漏洞。

关于否定：像Z3这样的SMT求解器旨在找到满足的赋值。证明P→Q的有效性（即程序始终是安全的）等同于证明P∧?Q的不满足性（即不存在反例/漏洞）。这种重构在标准一阶逻辑（FOL）的假设下是完全等价的，并且在这里是适用的，因为生成的VC代表了程序状态的静态、不可变的快照（例如，使用像oldest这样的版本化变量），在评估过程中没有副作用。

4. 字符串验证条件的翻译
之前已经解释了为什么使用SCSL语法格式通过演绎推理生成的验证条件不能直接输入Z3进行求解的原因。另一个重要原因是Z3支持的SMT-LIB [18]语言在形式上是S-expression [19]，这与通用安全C语言注释语言的语法和语义不同。鉴于此，不仅需要将程序注释语言翻译成自动定理证明器可以识别的 syntax 和语义形式，还需要将其转换为可以在Z3的求解能力范围内解决的形式。在本文中，第A节介绍了字符串断言的语法和语义规则。第B节解释了如何适当地翻译字符串断言的逻辑表达式。
为了避免符号歧义并确保从定义到验证模型的逻辑连贯性，我们首先建立了在整个方法论中使用的核心参数和上下文变量。我们模型中C字符串的正式表示依赖于以下统一参数：
•Δ：表示已建立的逻辑上下文环境。它包括所有已知的程序断言、类型声明以及到目前为止的分配内存界限。
•ρ 和 s：严格表示引用内存块基地址的逻辑字符指针。
•tint 和 tstr：分别表示评估为整数类型和字符串类型的抽象术语。
•m 和 n：专门用于表示表示字符串长度或索引偏移的整数值。

这些参数不仅仅是描述性的；它们构成了我们语义推理规则的操作支柱（详见图7）。例如，模型不是孤立地评估字符串指针s，而是在上下文Δ下进行评估。如字符串类型推导规则所示，这些参数作为前提条件被集成：Δ?\offset(s)+m≤\length(s)。这个数学构造明确使用了上下文参数Δ和指针s来保证长度参数m不超过动态分配的内存界限，从而直接驱动安全的SMT编码。

图6. 字符串断言的语法规则。

4.1. 字符串断言的语法和语义
本节首先详细介绍了字符串断言必须遵循的语法和语义规则。只有符合这些规则的字符串断言形成的验证条件才能实现准确的翻译。有关图7中显示的字符串的逻辑表达式的含义，请参阅表1。
我们框架中的验证条件（VCs）用SCSL的正式子集表示。图6指定了这种断言语言的正式语法，采用Backus–Naur形式（BNF）。该语言分为层次化组件：(1) 支持标准逻辑连接词的复合断言（F）；(2) 连接程序状态和逻辑属性的原子谓词（A）；以及(3) 分类为字符串类型（tstr）、整数类型（tint）和字符串声明（ts）的字符串特定术语。这种语法确保VC可以精确捕获高级字符串属性和低级内存布局属性，如?length和?offset。其中，逻辑连接词‘‘&&’’、‘‘||’’和‘‘!’’分别表示逻辑与、析取和否定。值得注意的是，在翻译涉及字符串声明的逻辑表达式时，会生成临时字符串变量来存储字符指针所指向的内存块中的有效长度的字符序列。这涉及两个关键符号：(ts) 和 ts。前者表示成功声明字符串后获得的字符序列，后者用于描述字符串是否可以成功构建。有关详细信息，请参见第B节中描述字符串的逻辑表达式的翻译方法。此外，tstr[tint] 和 tstr[tint..tint] 分别用于读取字符串中某个位置和某个范围内的值。?length 和 ?offset 来自指针三元组的操作语义，分别描述指针所指向的内存块的长度和当前指针偏移；strlen(str) 表示字符串str的长度。在程序中，只有在存在指向字符数组或字符串序列的字符指针char *p或注释中的逻辑字符指针逻辑char *p的情况下，才能使用与字符串相关的逻辑表达式。特别是，p + m 表示指针位置移动m个单位。

图7说明了字符串断言的标准语义，其中Δ表示程序和注释的上下文信息。字符串类型应确保它是一个从字符串指针的内存块偏移开始的有效长度序列，并且该序列不超过内存块的长度。特别是，pstring-type保证基于字符串类型的声明，字符串有一个明确的结束位置，并且该位置在有效内存范围内。
所有字符串断言的声明都应满足程序和注释的上下文要求，断言中的字符串逻辑表达式或操作应符合其操作语义。

4.2. 字符串逻辑表达式的翻译方法
目前，在断言中涉及的字符串操作中，常见的操作（如字符串值检索）已经大部分由Z3的内置函数覆盖，使得相应的翻译过程相对直接和简单。以下重点介绍第A节中定义的字符串逻辑表达式的翻译方法。鉴于这些方法在翻译过程中需要考虑多个因素，因此需要一个合理且适当的设计来确保翻译的准确性和有效性。
将字符串逻辑表达式（SLEs）翻译成SMT-LIB格式的方法遵循递归映射策略。对于语法树中的每个节点（如图6所定义），翻译器应用图7中的语义规则来生成目标S-expression。核心编码思想是将抽象的字符串谓词转换为指针三元组的具体算术约束。例如，如表3中详细说明的，string(s, m)的翻译不仅仅是类型转换；它被编码为一个包含显式边界检查（offset+m≤length）的功能谓词is_str。通过将这些数值界限直接注入SMT公式中，翻译限制了求解器的搜索空间，并防止了由于原生数组理论中无界量词实例化通常导致的“未知”结果。字符串逻辑表达式的翻译方法

- `string(s,m)`
(定义函数 `is_str`：`(s String) (strptr Int) (m Int) (str String)) Bool`
`(and (>= m 0) (< m (- (length strptr) (offset strptr)))`
`(forall ((i Int)) (=> (and (>= i (offset strptr)) (< i (+ (offset strptr) m)))`
`(and (not (= (str.at s i) "")) (= (str.at s i) (str.at str (- i (offset strptr)))))`

- `pstring(s,m)`
(定义函数 `is_pstr`：`(s String) (strptr Int) (m Int) (str String)) Bool`
`(and (is_str s strptr m str) (= (str.at s (+ m (offset strptr))) "")`
`(= m (str.len str))`

- `prefix(str,m)`
(定义函数 `str_prefix`：`(str String) (cstr String) (m Int)) Bool`
`(and (str_prefixof cstr str) (= m (str.len cstr)) (<= m (str.len str)) (>= m 0))`

- `suffix(str,m)`
(定义函数 `str_suffix`：`(str String) (cstr String) (m Int)) Bool`
`(and (str.suffixof cstr str) (= m (str.len cstr)) (<= m (str.len str)) (>= m 0))`

- `membership(str,cstr), contains(str,cstr)`
(定义函数 `str_contains`：`(str String) (cstr String)) Bool`
`(str.contains str cstr)`

- `index(str,cstr)`
(定义函数 `str_index`：`(str String) (cstr String) (index Int)) Bool`
`(and (= index (str.indexof str cstr)) (>= index 0) (<= index (- (str.len str) (str.len cstr)))`

- `strlen(str)`
(定义函数 `strlen`：`(str String) (strptr Int) (len Int)) Bool`
`(and (= (str.len str) len) (< len (- (length strptr) (offset strptr)))`
`(= (str.at str len) ""))`

- `operator+(strL,strR)`
(定义函数 `strcat`：`(strL String) (strptrL Int) (strR String) (str String)) Bool`
`(and (= str (str.++ strL strR)) (> (- (length strptrL) (offset strptrL)) (+ (str.len strL) (str.len strR)))`

- `str_is_integer(str)`
(定义函数 `str_int`：`(str String)) Bool`
`(forall ((i Int)) (=> (and (>= i 0) (< i (str.len str))) (`> (str.to_int (str.at str i)) ?1))`

- `operator<(strL,strR)`
(定义函数 `str_lt`：`(strL String) (strR String)) Bool`
`(not (=> (and (str_int strL) (str_int strR)) (not (exists ((x Int)) (and (>= x 0) (< x (str.len strR))) (forall ((y Int)) (=> (and (>= y 0) (< y x)) (= (str.at strR y) (str.at strL y)))) (`or (>= x (str.len strL)) (> (str.to_int (str.at strR x)) (str.to_int (str.at strL x)))))`

- `operator<=(strL,strR)`
(定义函数 `str_le`：`(strL String) (strR String)) Bool`
`(not (=> (and (str_int strL) (str_int strR)) (not (exists ((x Int)) (and (>= x 0) (< x (str.len strR))) (forall ((y Int)) (=> (and (>= y 0) (< y x)) (= (str.at strR y) (str.at strL y)))) (`or (>= x (str.len strL)) (>= (str.to_int (str.at strR x)) (str.to_int (str.at strL x)))))`

当翻译字符串的逻辑表达式时，如果遇到 `string(s,m)`，会生成一个中间变量 `str` 来存储字符指针 `s` 指向的有效字符序列。在翻译阶段，会生成 `is_str` 函数，如表3的第二行所示。`strptr` 是指针 `s` 指向的内存块，`offset` 是指针在内存块中的偏移量，默认为字符串指针在字符串中的位置，`length` 是指针指向的内存块的长度。

- **描述长度为 m 的字符串 (pstring)**
逻辑表达式描述了一个长度为 m 的字符串，其中第 (m+1) 位是字符串结束标记位。当翻译字符串的逻辑表达式时，如果遇到 `pstring`，会生成以下函数来确定字符串属性的可满足性。同样，会生成一个中间字符串变量 `str` 来存储指针 `s` 指向的有效字符序列。翻译方法如表3的第三行所示。逻辑表达式 1 和 2 限制字符串指针 `s` 是否可以构造为某种类型的字符串，而后续字符串逻辑表达式中涉及的字符串 `str` 指的是该过程中生成的所有中间字符串变量。

- **获取字符串的前 m 个字符（前缀）(prefix)**
当翻译字符串的逻辑表达式时，如果遇到 `prefix(str,m)`，会生成一个临时变量 `cstr` 来接收 `str` 的前 m 位，然后将其翻译为 `str_prefix(str,cstr,m)`。翻译方法如表3的第四行所示。

- **获取字符串的最后 m 个字符（后缀）(suffix)**
当翻译字符串的逻辑表达式时，如果遇到 `suffix(str,m)`，会生成一个临时变量 `cstr` 来接收 `str` 的后 m 位，然后将其翻译为 `str_suffix(str,cstr,m)`。翻译方法如表3的第五行所示。

- **确定字符串是否包含特定字符序列 (membership, contains)**
该方法采用字符串格式，支持子字符串和字符搜索。当翻译字符串逻辑表达式时，`membership(str,cstr)` 和 `contains(str,cstr)` 可以统一翻译为 `str_contains(str,cstr)`，如表3的第6行所示。

- **计算子字符串在另一个字符串中首次出现的位置 (index)**
当翻译字符串的逻辑表达式时，如果遇到 `index(str,cstr)`，会生成一个临时变量来接收返回的索引位置，然后将其翻译为 `str_index(str,cstr,index)`。翻译方法如表3的第7行所示。

- **计算字符串的长度 (strlen)**
该函数用于从字符串指针当前指向的内存块偏移量计算到字符串结束标记的长度。当翻译字符串的逻辑表达式时，如果遇到 `strlen(str)`，会生成相应的形式，翻译方法如表3的第八行所示。

- **描述字符串连接操作 (operator+)**
SCSL 使用 “+” 运算符来连接两个字符串。当翻译字符串的逻辑表达式时，如果遇到 `STRING+STRING`，会将其翻译为 `strcat(strL,strR,strptrL,str)`。`s` 表示两个原始字符串的连接结果。需要确保左侧字符指针所指示的内存空间足以容纳两个字符串的组合长度。翻译方法如表3的第9行所示。

- **描述字符串之间的关系运算符 (<,<=,==,!=,>,>=)`
Z3str4 支持字符串连接、模式匹配等操作，但缺乏 SCSL 定义的字符串关系比较操作。目前，Z3str4 仅支持字符串关系比较的相等或不相等判断。为了成功翻译用于描述字符串属性或操作的逻辑表达式，本节通过 Z3str4 提供的语法和语义规则扩展了字符串关系操作的判断方法。尽管 Z3str4 不支持字符串之间的比较或字符之间的比较，但它提供了从字符串到整数的转换操作 (`str.to_int`)。因此，这也为实现字符串关系比较提供了可能性。值得注意的是，在比较关系大小（不包括相等和不等关系）时，比较中涉及的每个字符串的字符都应被限制为整数类型，如表3的第10行所示。在 Z3 中，`str.to_int` 仅支持所有字符都是整数类型或转换位置处的字符是整数类型的字符串的转换。否则，如果被转换的字符串中存在其他数据类型的字符，整体结果为 ?1。在 SCSL 断言中遇到 “STRING op STRING” 时（其中 `gt` 表示大于，`ge` 表示大于或等于，`lt` 表示小于，`le` 表示小于或等于，`eq` 表示相等，`ne` 表示不相等），本文仅描述了与小于关系和小于或等于关系相关的字符串翻译方法，如表3的第11行和第12行所示。其他字符串关系的翻译方法非常相似，这里不再赘述。当然，也可以通过否定小于关系或小于或等于关系来获得它们；例如，`not str_lt` 等价于 `str_ge`。

为了明确缓解 Z3 的上述限制，我们提出的翻译策略采用了有界量词注入。如表3所示（例如关系运算符的编码），我们不依赖于原生的无界数组理论。相反，我们使用明确的内存块边界 (`?length`) 和当前指针位置 (`?offset`) 来限制所有全称（`forall`）和存在（`exists`）量词。此外，对于字典序比较，字符被转换为整数 (`str.to_int`) 并严格在这个有限搜索空间内进行评估。这种严格的限制防止了解算器进行无限量词实例化，有效地绕过了 Z3 的固有限制，确保了逻辑可判定性。

**5. 实验结果和讨论**
5.1 **实验设置**
为了验证所提出方法的有效性，我们对一组代表性的字符串操作函数进行了实验。基准测试套件包括 POSIX 标准 C 库（`string.h`）中的核心函数，具体为 `strspn`、`strcat`、`strcpy` 和 `strlen`。选择这些函数是因为它们代表了实际 C 字符串处理的基础逻辑，涉及复杂的指针运算和边界约束，这些经常导致安全漏洞。如表4所示，我们根据生成的验证条件（VCs）的逻辑复杂性和涉及的内存相关断言数量对它们进行了分类。
测试的硬件环境包括一个运行在 3.40 GHz 的 Intel(R) Core(TM) i5-7500 CPU、16 GB 内存和 1 TB 机械硬盘；软件环境包括 Visual Studio Code 1.63.2 和 FVC 1.0；操作系统是 Windows 10 21H2 Professional Edition。

表4. 基准测试套件的统计信息
| 函数 | 总 VC 数量 | 验证重点 |
|-----------------|---------|-----------------|
| `strspn.cglibc/string.h` | 100 | 前缀匹配逻辑 |
| `strcat.cglibc/string.h` | 51 | 连接与边界检查 |
| `strcpy.cglibc/string.h` | 56 | 缓冲区复制安全性 |
| `strlen.cglibc/string.h` | 45 | 空终止符检测 |

5.2 **结果分析**
在实验过程中，收集了需要验证的断言总数和成功验证的断言总数的详细统计信息。对本文提出的方法与 SCSL 验证方法进行了比较分析。实验结果显示，与 SCSL 验证方法相比，改进的验证方法有效减少了未验证的断言数量，并显著提高了断言验证的成功率。程序验证的时间消耗主要受未能成功证明的验证条件数量的影响。通常，一个未证明的验证条件就会耗尽预设的时间阈值。此外，无法直接证明的验证条件需要分解为多个子验证条件并逐一验证，这进一步增加了验证时间消耗。上述两个因素构成了程序验证的主要时间成本。两种方法之间的验证时间消耗比较结果详见表5。
通过对实验数据进行定量分析，改进方法在验证成功率上显示出显著提升。如图8所示，在 `strcat.c` 的情况下，基线方法的成功率为 71%，而我们的改进方法成功证明了 51 个 VC 中的 50 个，成功率为 98%。
求解器时间的减少同样显著。对于复杂的连接逻辑，平均验证时间从 33.1 秒（基线）降至 3.9 秒（改进方法），效率提高了 88.2%。我们方法中少数未证明的 VC 主要是由于求解器超时（超过 30 秒阈值）或由于量词嵌套深度过深导致的 “未知” 返回，而不是翻译逻辑中的错误。
实验结果表明，基于 Z3str4 理论的文本字符串验证方法在验证字符串程序时可以证明更多的验证条件，从而在验证时间上具有显著优势。特别是在验证 `strcat` 函数时，该函数的验证难度较高，有许多无法直接证明的验证条件，本文提出的方法的时间消耗比 SCSL 方法减少了约 30 秒。尽管在其他函数的验证中时间差异相对较小，但由于实验是在单个库函数上进行的，这种改进仍然具有重要意义。在验证过程中，我们采用了重构复杂且难以处理的验证条件的策略，有效地帮助自动化定理证明器完成了大多数验证条件的验证，进一步验证了本文提出方法的有效性和实用性。

表5. 验证时间比较
| 验证实例 | 改进方法耗时（秒） | SCSL 方法耗时（秒） |
|-----------------|-------------|-----------------|
| `strspn` | 0.8 | 1.2 |
| `strcspn` | 0.5 | 0.9 |
| `strcat` | 3.9 | 3.3 |
| `strncat` | 3.5 | 5.3 |
| `strcpy` | 4.3 | 5.8 |
| `strncpy` | 2.1 | 2.7 |**失败案例与局限性的讨论**

尽管取得了显著的改进，但对剩余未验证的验证条件（VCs）进行定性分析后仍发现了一些局限性。主要的失败场景发生在验证条件涉及多层嵌套量词，并且这些量词与非线性算术运算结合在指针属性上时。即使采用了当前的分割和界限策略，底层的SMT求解器（Z3）有时仍无法在规定的时间内找到有限的实例化界限。此外，当前框架假设字符值使用标准的整数表示。虽然这对于典型的安全属性来说已经足够，但依赖于特定非整数字符编码约束的验证任务（例如位屏蔽或字符到浮点数的转换）仍可能引发可判定性问题。在转换层中规定更细粒度的字符类型建模是未来工作的一个关键方向，以进一步提升该方法在工业级C项目中的实际应用效果。

**6. 结论**

在字符串程序验证领域，本文提出了一种相较于SCSL更具优势的验证方法。该方法利用断言完成技术来改进注释断言，为自动定理证明器的验证工作提供了强有力的支持。在验证过程中，通过采用无关断言移除和验证条件重构等策略，有效提高了程序验证的效率。此外，当与本文中改进的字符串逻辑表达式转换方法结合使用时，能够更高效地解决由字符串程序生成的涉及字符串属性的复杂验证条件，显著减轻了Z3求解器的负担。实验结果清楚地表明，与SCSL相比，本文提出的方法在证明效率和验证能力方面都有显著提升。

就实际应用而言，我们对POSIX标准库函数的实验结果表明，所提出的方法在验证现实世界的C语言字符串操作方面非常有效。然而，其实际应用仍面临某些定性限制。目前，转换机制依赖于将字符值表示为整数类型来进行关系比较。虽然这可以有效证明结构属性，但在验证使用特殊字符编码或需要复杂模式匹配任务（例如正则表达式）的现实世界软件时，会引入挑战。此外，工业级代码中大量嵌套的循环仍可能导致求解器超时。

为了解决这些实际限制，我们未来的工作将集中在两个主要方向上。首先，我们计划在转换层中规定更细粒度的字符类型建模框架，扩展对简单整数表示之外的原生支持。其次，我们旨在集成启发式预分析技术，在SMT编码之前自动划分复杂的验证条件。这些未来的改进将巩固该方法在软件形式验证更广泛领域中的实际应用效果和可扩展性。

**CRediT作者贡献声明**

- 李学健：撰写原始草案、监督、方法论设计、概念化。
- 行健：审阅与编辑、可视化。