用于计算多项式循环不变量的代数与算法方法

《Journal of Symbolic Computation》:Algebraic and algorithmic methods for computing polynomial loop invariants

【字体: 大 中 小 】 时间:2026年02月11日 来源:Journal of Symbolic Computation 0.9

编辑推荐:

  埃尔登贝亚尔·巴亚尔马格奈 | 法特梅赫·莫哈马迪 | 雷米·普雷贝 比利时鲁汶大学计算机科学系 摘要 循环不变量是程序循环在每次迭代前后都保持的属性。它们常被用于验证程序,确保算法在执行过程中始终产生正确结果。因此,为循环生成不变量是一项关键任务。我们重点研究多项

  埃尔登贝亚尔·巴亚尔马格奈 | 法特梅赫·莫哈马迪 | 雷米·普雷贝
比利时鲁汶大学计算机科学系

摘要
循环不变量是程序循环在每次迭代前后都保持的属性。它们常被用于验证程序,确保算法在执行过程中始终产生正确结果。因此,为循环生成不变量是一项关键任务。我们重点研究多项式循环,即循环条件及循环内的赋值均以多项式形式表达。尽管为一般循环计算多项式不变量是不可判定的,但针对某些特定类型的循环已开发出高效算法。例如,当while循环中的所有赋值都涉及线性多项式时,该循环即可被求解。在本研究中,我们探讨更一般的情况,即多项式可以具有任意阶数。借助代数几何工具,我们提出了两种算法,用于为带有非确定性条件语句的分支循环,在给定向量子空间内生成所有多项式不变量。这些算法将线性代数子程序与多项式理想运算相结合。根据循环变量的初始值是已指定还是作为参数处理,这些算法有所不同。此外,我们还提出了一种更为高效的算法,可用于为所有初始值生成特定形式的多项式不变量,且无需进行复杂的理想运算。

引言
循环不变量是指程序中每次循环迭代前后都成立的属性。当循环不变量为多项式方程或不等式形式时,称其为该循环的多项式不变量。本文仅聚焦于多项式方程形式的不变量,简称多项式不变量。它们在自动化程序验证中起着至关重要的作用,有助于确保算法在执行过程中始终得到正确结果。尤其是,一些成熟的安全性验证方法,如Floyd-Hoare归纳断言技术(Floyd,1993)以及通过标准排序函数进行终止性验证的技术(Manna和Pnueli,2012),都依赖循环不变量来验证正确性,从而实现验证过程的完全自动化。

本文专门研究多项式循环,即赋值表达式为程序变量多项式的循环。同时,我们仅考虑循环保护条件包含不等式的情况,不等式定义为方程的否定形式。需注意,若允许不变量和保护条件使用不等式,则不变量验证问题将比线性递归序列的正定性问题更为复杂,而后者的可判定性至今仍无定论(参见Kovács,2023及其中的参考文献)。

具体而言,设a=(a1,…,an)∈Cn,h=(h1,…,hs),F=(f1,…,fn)为C[x1,…,xn]中的两个多项式序列,其中xi表示程序变量,ai为循环的初始值。此时,L(a,h,F)表示相应的循环:若不考虑h,则记为L(a,1,F),因为这对应无限循环。若上下文已明确循环形式,则直接简写为L。

接下来,考虑一个多项式循环L(a,h,F)。首先定义本文要计算的核心对象。**定义1.1**:集合IL(a,h,F)?C[x1,…,xn],即L(a,h,F)的所有多项式不变量,被称为L的不变理想。如 Rodríguez-Carbonell和Kapur(2004)所指出的,该集合实际上是C[x1,…,xn]的一个理想。根据希尔伯特基定理,人们期望能找到这个理想的有限基,从而完整描述该不变理想。然而,正如Müllner等人(2024)最新研究表明,这一任务至少与斯柯伦问题一样困难,后者的可判定性至今仍悬而未决,已困扰了近一个世纪。因此,本文旨在部分计算该不变理想,具体定义如下:**定义1.2**:设E为C[x1,…,xn]中的一个有限维向量子空间,则L(a,h,F)在E中的多项式不变量记为IL(a,h,F),E。需要注意的是,这一受限的多项式不变量集合仍是C[x1,…,xn]的有限维向量子空间E的向量子空间。因此,我们可以将许多问题转化为线性代数问题,并为IL(a,h,F),E计算向量基。文献中常见的E选择是那些次数被限定在某个常数范围内的多项式集合。选择足够大的次数,既能保证存在某些多项式不变量属于E,又能控制问题的维度。

相关工作
过去二十年间,循环多项式不变量的计算已被广泛研究,例如Amrollahi等人(2022)、de Oliveira等人(2017)、Hrushovski等人(2018)、Karr(1976)、Kovács(2008、2023)、Rodríguez-Carbonell和Kapur(2004、2007a、2007b)、Amrollahi等人(2025)等人的工作。对于一般循环,这一问题是不可判定的(Hrushovski等人,2023)。因此,研究重点转向了某些特定类型的循环,尤其是那些断言均为线性或可转化为线性断言的循环。

生成多项式不变量的一种常见方法是:从循环中构建递推关系系统,求出该递推关系的封闭形式,然后通过从封闭形式中去除循环计数器来计算多项式不变量(如Katz和Manna,1976所述)。需要注意的是,从多项式不变量反推此类递推关系相对简单,但如Amrollahi等人(2022)所详述,反向过程只有在非常强的假设条件下才可行。具体而言,需要确定程序变量之间的多项式关系,而这是一项极具挑战性的任务。

当循环中的每个赋值都是线性函数时,Michael Karr提出了一种用于计算所有线性不变量的开创性算法(Karr,1976)。后续研究,如Müller-Olm和Seidl(2004b)以及Rodríguez-Carbonell和Kapur(2007a)的工作,将此算法扩展为可计算所有有界次数的多项式不变量。最近的一些方法则试图计算完整的不变理想。Hrushovski等人(2018)和Nosan等人(2022)的算法虽实现了这一目标,但复杂度极高:即使在最佳情况下,其时间复杂度也仍为多指数级。不过,对于某些受限类型的循环,复杂度可显著降低。例如,对于具有单一线性更新的非分支循环,Ait El Manssour等人(2025)提出了PSPACE级算法,表明在适当约束条件下,高效的不变量生成是可行的。

另一类成功计算出不变量的循环是可解循环。这类循环的特点是其多项式赋值要么本身就是线性的,要么可通过变量变换转化为线性形式,相关研究可见de Oliveira等人(2016)和Kovács(2008)的论述。关于可解循环所有多项式不变量的生成方法,可在de Oliveira等人(2016)和Rodríguez-Carbonell和Kapur(2004)的文章中找到。de Oliveira等人(2016)通过将可解循环转化为线性循环来实现,而Rodríguez-Carbonell和Kapur(2004)则依赖前向传播和不动点计算方法。Kovács(2008)提出的方法专为P-可解循环这一特殊情形设计,后来Humenberger等人(2017)对其进行了扩展。

对于具有非线性或不可解赋值以及嵌套非确定性分支的循环,仍然存在诸多挑战,相关研究可见Amrollahi等人(2022)、Cachera等人(2014)、Cyphert和Kincaid(2024)、Sankaranarayanan等人(2004)、Wang和Lin(2024)等人的工作。这些方法能够生成指定次数的多项式不变量,但虽然可靠,却无法保证完整性,即可能存在被遗漏的不变量。特别是Wang和Lin(2024)致力于寻找满足多维C-有限递推关系的有界次数多项式表达式,这些表达式构成一个向量空间,这一视角与我们基于向量空间的建模方法在概念上相似。

在Müller-Olm和Seidl(2004a)的研究中,他们采用了与我们的算法1类似的方法,不同之处在于,我们通过几何方法计算不变量集合,并通过比较根理想而非理想本身来建立更好的停止准则。他们还对初始值施加了代数约束,进而计算出必须适用于所有满足这些约束的初始值的多项式不变量,这意味着一些适用于除有限个初始值外所有情况的不变量可能会被忽略。相比之下,算法4生成的不变量依赖于初始值,能够解决更广泛的问题,据我们所知,此前尚未有人研究过此类问题。此外,算法5专门用于处理具有固定初始值的场景,其效率远高于算法3以及Müller-Olm和Seidl(2004a)中的对应算法。另外,算法6能够在存在时生成所有特定形式的一般不变量,从而让我们能够生成Amrollahi等人(2022)所提出的不变量。

最后,Chatterjee等人(2020)利用Putinar的Positivstellens?tz等工具,将多项式不变量视为不等式。但这属于另一个问题,涉及半代数集X,满足F(X)?X的条件,而多项式不变量并不一定具备这一性质。

我们的贡献
在本研究中,我们致力于完全生成给定向量空间E中,具有任意次数多项式更新及不等式作为保护条件的循环的所有多项式不变量集合IL(a,h,F),E。第2节中,我们介绍了不变量集合并给出了计算它们的算法1。第3节在此基础上发展出算法2,用于判断给定多项式是否为不变量。第4节结合第2节和第3节的结果,设计了两种算法(算法3、算法5),用于计算IL(a,h,F),E的基,具体取决于向量a是固定的还是保持符号形式。这些结果和算法还被进一步扩展到具有非确定性条件语句的分支循环。第5节中,我们引入了专门的算法6,它能更高效地计算形如f(x1,…,xn)?f(a1,…,an)的所有多项式不变量。值得注意的是,该算法无需进行任何多项式理想运算。例如,在Fib1、Fib2和Fib3测试基准上,算法5无法在360秒内计算出所有5次以内的多项式不变量,而算法6则能在不到120秒的时间内计算出这些形式下10次以内的所有不变量。第6节中,我们将具有不等式保护条件的循环的终止性与多项式不变量联系起来,推导出了若干必要或充分的条件。第7节则展示了我们算法的实现方式及实验结果。

扩展版本
本文是发表在ISSAC 2024会议论文集中的短篇论文(Bayarmagnai等人,2024)的扩展版本。它提供了更详细的说明,强化了部分结果,并带来了多项新贡献。具体而言,第4.1节中,我们提出了算法4,它能明确描述依赖于初始值的多项式不变量。第4.3节中,我们将先前介绍的算法扩展为可处理具有非确定性条件语句及不等式保护条件的分支循环;早期版本仅适用于无保护条件的单路径循环。第5节中,我们对(Bayarmagnai等人,2024,命题4.1)进行了进一步推广,并开发了算法6,它能计算分支循环中所有特定形式、给定次数以内的多项式不变量。该算法不依赖第4节中的方法,也无需进行复杂的理想运算。最后,在第7节中,我们将新的算法6与Polar Moosbrugger等人(2022)的方法进行了比较,并提供了通过优化算法5实现的新的测试基准。下图总结了各算法之间的依赖关系。核心组件是InvariantSet(算法1),除算法6外的所有其他算法都依赖于它(见图1)。

章节节选
**不变量集合**
在本节中,我们通过引入不变量集合来提供一种识别多项式不变量的方法。正如后面将看到的,这些集合与多项式不变量有着天然的联系。我们用C表示复数域。在整篇文章中,x表示x1,…,xn,C[x]表示这些变量的多项式环。

**测试多项式不变量**
既然我们已经有了计算不变量集合的算法,接下来我们将基于精心挑选的数据,给出一种利用不变量集合来识别多项式不变量的准则。这将引导我们开发出一种用于判断给定多项式是否为不变量的算法。由于保护条件[h1≠0,…,hs≠0]等价于[h1×?×hs≠0],因此我们可以考虑那些保护条件中只包含一个不等式的多项式循环。回忆一下,IL(a,h,F)表示L(a,h,F)的所有多项式不变量的集合。命题3.1:设h、g以及F=(f1,…)。在本节中,我们将根据循环的初始值是被指定还是被视为变量,介绍多种生成多项式不变量的算法,并将我们的结果扩展到分支循环。特定形式的一般多项式不变量:在本节中,我们将展示在寻找特定形式的多项式时,与第4节相比,可以更高效地识别出对任何初始值都成立的多项式不变量。具体而言,我们首先给出一个充分必要条件,用于识别仅常数系数依赖于初始值的多项式不变量。然后利用这一条件来检测并生成所有此类形式的多项式不变量。设h和F=(F1,…,Fn)是C[x]中的多项式。代数和半代数循环的终止性:在本节中,我们利用不变量集来为代数和半代数循环建立终止条件。我们首先给出代数循环终止的充分必要条件;而对于半代数循环,我们仅给出一个充分条件。命题6.1:设a∈Cn,g=(g1,…,gm)以及F=(f1,…,fn)是C[x]中的两个多项式序列。设X=V(g1,…,gm)?Cn。那么,多项式循环L(a,g=0,F)永远不会终止当且仅当a∈S(F,X)。证明:该结论可直接得出。实现与实验:在本节中,我们展示了本文所讨论算法的实现,并将其性能与Polar(Moosbrugger等人,2022年)进行了比较,后者主要基于Amrollahi等人(2022年)的研究成果,用于处理无法解决的循环问题。在所有表格中,n表示程序变量的数量,D则表示循环映射的度数。为了确保公平比较,并与现有文献保持一致,所有实验计算的多项式不变量的度数都受到限制。结论:我们提出了一种新方法,用于生成具有非确定性条件语句的分支循环在给定向量子空间E?Q[x]中的所有多项式不变量。我们的主要贡献包括:•针对没有固定初始值的循环的算法3和算法4;•针对具有指定初始值的循环的算法5;•用于计算所有形如f(x)?f(a)的不变量的算法6。其中,算法4提供了不变量的显式符号描述,而算法3则没有。CRediT作者贡献声明:Erdenebayar Bayarmagnai:写作——审阅与编辑,写作——初稿撰写,软件,方法论,研究,形式分析,概念设计。Fatemeh Mohammadi:写作——审阅与编辑,写作——初稿撰写,项目管理,方法论,研究,资金获取,形式分析,概念设计。Rémi Prébet:写作——审阅与编辑,写作——初稿撰写,软件,方法论,研究,形式分析,概念设计。致谢:我们感谢匿名审稿人提出的有益意见和建议。同时,我们也感谢George Kenison就Polar问题进行的深入讨论。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号