源代码等价性验证装置以及源代码等价性验证方法

摘要

通过符号执行进行针对由人工实施的重构的等价性验证时，能够不使计算量爆发，而迅速地进行。在验证源代码的等价性时，进行基于解析源代码而得的结构图的结构比较的验证和符号执行的验证这两种验证。并且，在通过基于结构图的结构比较能够判定为结构一致的情况下，不进行符号执行。此外，在进行基于结构比较的验证前，对于重构前后的各个源代码，根据对每个重构模式决定的正规化信息对结构图进行正规化，在重构正当时，调整为结构一致。并且，对将重构前后的各个结构图进行抽象化而得的图进行符号执行来进行验证，由此限定进行符号执行的位置。

说明书

技术领域

本发明涉及一种源代码等价性验证装置以及源代码等价性验证方法，尤其 涉及一种在软件重构中为了防止因重构实施导致的不良混入，在通过符号执行 方法验证作为程序的动作等价的情况下，用于防止计算量的爆发式增加，迅速 验证重构的正当性的优选的源代码等价性验证装置以及源代码等价性验证方 法。

背景技术

近年来，随着信息处理社会发展，软件系统浸透到一般社会，对于软件要 求的可靠性成为非常高的问题。另一方面，软件随着常年的差异/派生开发而 踏上复杂化且大规模化的方向，软件的易扩展性或易理解性等维护性下降成为 问题。

重构是在非专利文献1至3中所公开的方法，通过不改变软件的动作地变 更内部结构来改善软件的设计品质的方法的总称，是减轻复杂度提高维护性的 方法。该重构的方法是对于确保踏上复杂化以及大规模化的方向的软件的维护 性有希望的技术，但由于变更源代码，因此存在新混入不良的可能性。具体而 言，在重构中存在被分类为多个模式的方法，明示或暗示地决定各源代码的变 更顺序以及针对用于保证通过该变更不会改变软件的动作的源代码的条件。在 不按照该变更顺序地变更了源代码的情况下，或者，变更了不遵从这样的条件 的源代码的情况下，不保证不改变成为对象的软件动作，因此有可能在软件中 混入不良。因此，软件开发者在软件的维护阶段，有担心因重构原因而在准确 地动作的软件中混入不良，而做出不进行重构的判断的可能性。因此，在软件 的维护阶段，为了积极地进行重构，要求验证没有由重构导致的不良的混入的 方法。

在非专利文献3中，定义了72种典型使用的重构模式(以下，简单称为 “重构模式”)。

在本说明书中，将两个源代码外在的动作相同，即针对相同输入在执行时 得到相同输出定义为两个源代码“等价”，将验证重构实施前的源代码和重构 实施后的源代码等价称为“等价性验证”。

作为验证重构实施前的源代码和重构实施后的源代码等价的方法所要求 的条件，有如下的条件。

(1)一个条件是其作业的大部分被自动化，基于人工的作业较少。以往， 通过基于人工的评价或测试来验证源代码的等价性。通过对其实现基于工具的 自动性验证，削减验证用时，促进重构。

(2)另一个条件是通过重构验证方法判断为动作等价或非等价的情况下， 向开发者提示成为其根据的信息。通过向开发者提示易懂的成为判定基准的信 息，开发者自身能够进行再验证，针对工具的可靠性提高，促进重构。

作为等价性验证的方法，有：通过专利文献1公开的源代码比较，对产生 差异的部分实施测试，比较其结果的方法；通过图表表现非专利文献1公开的 源代码，每次重构时验证图表否满足所决定的事先条件的方法；以及使用非专 利文献2公开的符号执行，来验证动作被保持的方法。

现有技术文献

专利文献

专利文献1：美国专利申请公开第2007/0033576号说明书

非专利文献

非专利文献1：T.Mens,S.Demeyer,D.Janssens,"FormalisingBehaviour PreservingProgramTransformations",ProceedingsoftheFirstInternational ConferenceonGraphTransformation,USA,2002

非专利文献2：S.Person,M.B.Dwyer,S.Elbaum,C.S.Pasareanu, "DifferentialSymbolicExecution",Proc.ofACMSIGSOFTSymposiumonthe FoundationsofSoftwareEngineering2008,USA,2008

非专利文献3：M.Fowleretal.,“Refactoring:ImprovingtheDesignof ExistingCode”,USA,Addison-WesleyProfessional,1edition,July8,1999

发明内容

发明要解决的课题

在非专利文献1中公开了如下的方法：用图表表现程序的方法调用关系， 每次重构时验证是否满足所决定的事先条件。在该方法中，通过结构上的验证 实现动作的验证，因此每次重构时，严密地定义其操作后收罗不会对动作产生 影响的条件。因此，事实上，存在必须通过工具使重构自动化，不能用于通过 可能错误进行重构操作其本身的人工的重构验证的问题。

在专利文献1中公开了通过使用符号执行，生成针对成为对象的源代码的 测试用例的方法。并且，在专利文献1中公开了使用不同的抽象度来抑制符号 执行的计算量的爆发并生成测试用例的方法。为了将这些方法应用于重构前后 的等价性验证，生成与重构前和重构后的源代码相关的测试，实施对各源代码 生成的测试，验证它们的结果。这些在实施重构时不需要特别的过程，但存在 几个问题。根据重构位置影响波及范围较广，仅通过所生成的测试还存在无法 完全验证等价性的可能性。此外，即使是没有影响的波及的仅差异部分的验证， 也存在因测试的覆盖率产生验证遗漏等可能性。此外，基于测试的等价性验证 有验证遗漏等可能性，因此不完全。此外，作为等价性的判断根据，对开发者 提示所实施的测试用例。但是，存在仅通过测试用例的举例，开发者无法判断 这些是否是充分的测试用例的问题。

在非专利文献2中，作为对重构前后的源代码进行等价性验证的技术，公 开了使用符号执行的方法。

符号执行是作为对象的程序输入，代替赋予数值，而通过赋予符号来网罗 解析程序的动作的方法。

以下，使用图19说明符号执行的一例。

图19是为了说明符号执行的一例，表示源代码和由此派生的数据结构的 图。

在符号执行中，使用被称为符号变量的符号来表现输入变量的值，解析该 符号变量在程序中如何被参照/更新。在此，以记载于用C语言记述的源代码 E001中的函数foo为对象实施符号执行。在对成为符号执行的对象的源代码 E001进行符号执行时，首先，与对通常的源代码进行编译时同样地，实施字 句解析或句法解析。根据该结果得到从源代码E001提取了控制流程或控制依 存图、数据依存图等的结构图E002。在符号执行中，使用结构图E002来生成 执行树E020。执行树E020中的各节点由通过用于达到该节点的符号变量所表 现的路径制约和通过符号变量变现了该节点中的各变量的值的变量状态构成。 在图19的执行树E020中，在各节点的上侧表现路径制约，在下侧表现变量 状态。

以下，详细说明执行树E020的生成过程。

在符号执行的开始阶段，在源代码E001中，对成为程序的输入的变量分 配符号变量。在源代码E001的例子中，全局变量a、b、c是成为输入的变量， 因此分别对它们分配α、β、γ这样的符号变量。在结构图E002上，在与节点 E003对应的开始状态，执行树E020是仅由单一的节点E010构成的执行树。 节点E010的路径制约E010a成为表示无制约(对任意的变量状态满足制约) 的真(true)，变量状态E010b按照符号变量的分配表示与各变量对应的符号 变量相等。

在结构图E002上，接着节点E003执行节点E004。与之相伴，在执行树 中也生成E010的子节点E011。关于子节点E011中的路径制约E011a以及变 量状态E011b，复制母节点E010的路径制约E010a以及变量状态E010b后， 执行结构图E002上的节点E004。

在节点E004中，对变量a代入0。因此，将针对执行树的节点E011的变 量状态E011b中的变量a的状态更新为a＝0。

在结构图E002上，接着节点E004执行的是节点E005。在节点E005中， 没有进行变量状态的更新，因此不生成执行树中的新节点。节点E005是基于 若(if)文的条件分支。因此，在结构图E002的控制流程中成为下个的节点 是节点E006和节点E007这两个节点。在符号执行中，为了网罗所有能够取 得的控制流程，在条件分支中，生成与各个分支对应的子节点。即，与节点 E006对应地生成E012作为执行树中的节点E011的子节点，与节点E007对 应地生成E013作为执行树中的节点E011的子节点。

执行树的节点E012的路径制约E012a成为母节点的路径制约E011a和条 件分支的分支条件的逻辑积(AND，在图中为&)。节点E00中的分支条件为 c＜0，此外，从变量状态E011b，如果用符号变量表示变量c，则成为γ，由 此可知用于使条件分支成立的条件为γ＜0。因此，真(rrue)和γ＜0的逻辑 积即γ＜0成为节点E012中的路径制约E012a。

接着，子节点E013的路径制约E013a，与在E013的条件分支的分支条件 不成立的情况下对应，因此成为母节点的路径制约E011a和条件分支的分支条 件的否定(NOT(逻辑非)，在图中为！)的逻辑积。即，真(true)和！(γ＜0) 的逻辑积即！(γ＜0)成为子节点E013的路径制约E013a。

关于节点E011的子节点E012的变量状态E012b、子节点E013的变量状 态E013b，在复制母节点E011的变量状态E011b后继续进行计算。关于节点 E012的变量状态E012b，在节点E006向变量c代入0，因此针对c的变量状 态被更新为c＝0。关于节点E013的变量状态E013b，在节点E007向变量a 代入变量c的值。在该时间点，变量c的变量状态成为符号变量的γ，因此在 变量状态E013b，变量a的变量状态被更新为a＝γ。

之后也按照与上述同样的顺序生成执行树。在控制流程中，接着节点E006 的节点是E008，该E008为条件分支，因此在执行树对节点E012生成两个子 节点E014和E015。节点E008中的分支条件为(b＜0)，但使用变量状态E012b 以符号变量表现他们时成为(β＜0)。因此，子节点E014和E015的路径制约 成为针对母节点E012的路径制约E012a分别取(β＜0)和！(β＜0)的逻辑 积。在子节点E014中，接着执行控制流程上的节点E009a。节点E009a是向 变量a代入a－b的的值而得的节点，根据变量状态可知变量a的状态为0，变 量b的状态为β，因此将变量a的状态更新为－β。在子节点E015中，接着执 行控制流程上的节点E009b。E009b是向变量a代入a+b的值而得的节点，根 据变量状态可知变量a的状态为0，变量b的状态为β，因此将变量a的状态 更新为β。

在控制流程中，接着节点E007的节点是E008，该E008为条件分支，因 此在执行树中对节点E013生成两个子节点E016和E017。节点E008中的分 支条件为(b＜0)，但使用变量状态E013b以符号变量表现他们时成为(β＜0)。 因此，子节点E016和E017的路径制约为分别对母节点E013的路径制约E013a 取(β＜0)和！(β＜0)的逻辑积。在子节点E016中，接着执行控制流程上 的节点E009a。E009a是向变量a代入a－b的值而得到节点，根据变量状态可 知变量a的状态为γ，变量b的状态为β，因此将变量a的状态更新为γ－β。 在子节点E017中，接着执行控制流程上的节点E009b。E009b是向变量a代 入a+b的值而得到的节点，根据变量状态可知变量a的状态为γ，变量b的状 态为β，因此将变量a的状态更新为γ+β。

对于执行树E020的所有叶节点，其控制流程到达函数结束时，结束执行 树的生成。图19的执行树E020表示针对函数foo的符号执行结束的时间点的 执行树。收集符号执行结束的时间点的执行树的各叶节点而成为符号执行的结 果(这些被称为“成为符号一览”)。符号变量α、β、γ的任意的组合满足符号 执行一览中的各叶节点中的任意路径制约。通过使用该节点所包含的变量状 态，能够从成为输入的符号变量的值知道程序执行后的各变量的值。例如，在 函数foo执行前的变量a、b、c的值都是1的情况下，符号变量成为α＝β＝γ ＝1，满足节点E017的路径制约。从节点E017的变量状态可知函数foo执行 后的变量a的值成为a＝γ+β＝2、b＝β＝1、c＝γ＝1。如上所述，符号执行 是在网罗程序能够取得的控制路径基础上，能够求出以程序执行前后的变量值 的关系为输入值的条件(路径制约)和输出变量的状态(变量状态)的组的集 合即符号执行一览的计算。

针对重构前后的源代码的结构图，分别进行符号执行，在得到逻辑上等价 的符号执行一览时，即在针对相同输入得到相同输出的情况下，如以上定义的 那样，能够判定为源代码等价。这样，符号执行因为网罗性地解析对象的程序 的能够取得的动作系列，因此不会产生使用了测试的验证中的覆盖率问题或事 先条件的验证中的工具依存问题。另一方面，在具有重复文或递归结构的程序 中，执行树变得复杂，计算量容易发散爆发。为了抑制计算量，需要限定符号 执行的范围或限制基于事先条件的执行，失去符号执行的优点即验证的完全 性。

在非专利文献2中，着眼于在要比较的源代码之间存在共有部分这一点， 在维持完全性的状态下试图减少计算量。通过函数(uninterruptedfunction，不 中断函数)表现没有变更的共有的程序段的执行结果，由此防止执行树上的计 算量的发散。然而，依然存在差异部分的执行树上的计算量发散的用例，存在 计算量爆发的可能性。此外，也没有提及与硬件等外界具有相互作用的程序的 处理。

本发明是为了解决上述问题点而提出的，其目的是提供一种通过符号执行 进行针对人工实施的重构的等价性验证时，不使计算量爆发，而能够迅速地进 行的源代码等价性验证方法。

用于解决课题的手段

为了解决上述课题，在本发明中，提供一种验证最初的源代码和重构实施 后的源代码的等价性的源代码等价性验证装置，使该源代码等价性验证装置构 成为具有如下单元：源代码输入单元，其输入重构前的源代码和重构后的源代 码；重构模式输入单元，其输入所述源代码的重构模式信息；源代码信息生成 单元，其进行所述重构前的源代码和所述重构后的源代码各自的字句解析/句 法解析，并变换为结构图，生成重构前源代码信息和重构后源代码信息；正规 化单元，其参照对重构模式信息定义的正规化信息，对所述重构前源代码信息 和所述重构后源代码信息进行正规化，分别生成重构前正规化源代码信息和重 构后正规化源代码信息；结构比较单元，其比较所述重构前正规化源代码信息 和所述重构后正规化源代码信息的结构；符号执行单元，其对所述重构前正规 化源代码信息和所述重构后正规化源代码信息进行符号执行；以及等价性判定 单元，其比较基于所述符号执行单元的符号执行的结果，来判定所述重构前源 代码和所述重构后源代码的等价性。

此外，为了解决上述课题，在本发明中，在所述源代码等价性验证装置中， 所述结构比较单元比较所述重构前正规化源代码信息和所述重构后正规化源 代码信息的结构图，在判定为结构一致的情况下，判定所述重构前源代码和所 述重构后源代码等价，结束等价性验证处理，在判定为所述结构不一致的情况 下，向所述符号执行单元的处理转移。

此外，为了解决上述课题，在本发明中，在所述源代码等价性验证装置中， 所述正规化单元还具备：变更位置确定单元，其参照对所述重构模式信息定义 的变更位置确定信息，比较所述重构前源代码信息和所述重构后源代码信息， 生成用于确定源代码的结构上的变更位置的变更位置信息；所述符号执行单元 还具备：抽象化单元，其参照通过所述变更位置确定单元提取的所述重构前源 代码信息与所述重构后源代码信息的变更位置信息以及对所述重构模式信息 定义的抽象化信息，对所述重构前正规化源代码信息和所述重构后正规化源代 码信息进行抽象化，对所述抽象化单元生成的重构前抽象化源代码信息和重构 后抽象化源代码信息进行符号执行。

此外，为了解决上述课题，在本发明中，在验证最初的源代码和重构实施 后的源代码的等价性的源代码等价性验证方法中，具有如下步骤：源代码输入 步骤，输入重构前的源代码和重构后的源代码；重构模式输入步骤，输入所述 源代码的重构模式信息；源代码信息生成步骤，进行所述重构前的源代码和所 述重构后的源代码各自的字句解析/句法解析，并变换为结构图，生成重构前 源代码信息和重构后源代码信息；正规化步骤，参照对重构模式信息定义的正 规化信息，对所述重构前源代码信息和所述重构后源代码信息进行正规化，分 别生成重构前正规化源代码信息和重构后正规化源代码信息；结构比较步骤， 比较所述重构前正规化源代码信息和所述重构后正规化源代码信息的结构；符 号执行步骤，对所述重构前正规化源代码信息和所述重构后正规化源代码信息 进行符号执行；以及等价性判定步骤，比较基于所述符号执行步骤的符号执行 的结果，来判定所述重构前源代码和所述重构后源代码的等价性。

发明效果

根据本发明，能够提供一种通过符号执行进行针对由人工实施的重构的等 价性验证时，能够不使计算量爆发，而迅速地进行的源代码等价性验证方法。

附图说明

图1是本发明一实施方式的源代码等价性验证装置的硬件结构图。

图2是本发明一实施方式的源代码等价性验证装置的软件结构图。

图3是本发明一实施方式的源代码等价性验证装置的功能结构图。

图4是表示本发明一实施方式的源代码等价性验证装置整体的功能和数 据流程的图。

图5是表示本发明一实施方式的源代码等价性验证装置的处理的流程图。

图6是表示输入部1100的功能的细节和数据流程的图。

图7是表示正规化部1200的功能的细节和数据流程的图。

图8是表示结构比较验证处理部1300的功能的细节和数据流程的图。

图9是表示符号执行实施判定部1700的功能的细节和数据流程的图。

图10是表示符号执行验证处理部1400的功能的细节和数据流程的图。

图11是表示重构前后的源代码的例子的图(之一)。

图12是表示与重构前后的源代码对应的源代码信息的例子的图(之一)。

图13是表示针对源代码信息进行的正规化的例子的图。

图14是表示用于显示通过结构比较对正规化后的结构图进行了等价性验 证而得的结果的输出部的显示例的图。

图15是表示重构前后的源代码的例子的图(之二)。

图16是表示与重构前后的源代码对应的源代码信息的例子的图(之二)。

图17是表示抽象化后的源代码信息的例子的图。

图18是表示针对重构前源代码和重构后源代码进行了符号执行时的执行 树的例子。

图19是为了说明符号执行的一例，表示源代码和由其派生的数据结构的 图。

图20是表示用于显示通过符号执行验证处理部进行了等价性验证而得的 结果的显示部的显示例的图。

图21是表示重构前后的源代码的例子的图(之三)。

图22是表示与重构前的源代码对应的源代码信息的例子的图(之三)。

图23是表示与重构后的源代码对应的源代码信息的例子的图(之三)。

图24是表示正规化后的重构后的源代码信息的例子的图。

图25是表示抽象化后的源代码信息的例子的图。

图26是表示被抽象化时的、针对重构前源代码和重构后源代码进行了符 号执行时的执行树的例子。

图27是表示被抽象化时的、基于显示部的等价性验证结果的显示例的图。

具体实施方式

以下，使用附图对本发明的实施方式进行说明。

实施例1

以下，使用图1至图10，对本发明一实施方式的源代码等价性验证装置 1000的结构和处理进行说明。

首先，使用图1对本发明一实施方式的源代码等价性验证装置的硬件结构 进行说明。

作为本发明一实施方式的源代码等价性验证装置的硬件结构，例如通过图 1所示的一般的个人计算机来实现。

源代码等价性验证装置1000是将CPU(CentralProcessingUnit，中央处 理单元)101、主存储装置102、网络I/F103、图形I/F104、输入输出I/F105、 辅助存储装置I/F106通过总线而结合的方式。

CPU101控制源代码等价性验证装置100的各部，将源代码等价性验证程 序200加载到主存储装置102来执行。

通常，主存储装置102由RAM等易失性存储器构成，从辅助存储装置等 加载CPU101执行的程序、参照的数据并存储。

网络I/F103是用于与外部网络150连接的接口。

图形I/F104是用于与LCD(LiquidCrystalDisplay，液晶显示器)等显示 装置120连接的接口。

输入输出I/F105是用于与输入输出装置连接的接口。在图1的例子中， 连接有键盘131和作为指示设备的鼠标132。

辅助存储装置I/F106是用于连接HDD(HardDiskDrive，硬盘驱动器)、 DVD(DigitalVersatileDisk，数字通用光盘)驱动装置142等辅助存储装置的 接口。

HDD141具有大容量的存储容量，存储用于执行本实施方式的源代码等价 性验证程序200。

DVD驱动装置142是向DVD或CD等光盘写入数据或从光盘读入数据的 装置，源代码等价性验证程序200例如能够安装由CD－ROM提供的程序。

本实施方式的源代码等价性验证装置1000在上述那样的个人计算机上安 装源代码等价性验证程序200来执行各功能。

接着，使用图2对本发明一实施方式的源代码等价性验证装置的软件结构 进行说明。

在源代码等价性验证装置1000中执行的程序等价性验证程序200的模块 结构由子程序即源代码解析模块201、结构图生成/更新模块202、结构图解析 模块203、执行树生成模块204、符号执行执行模块205、输入输出模块206 和数据库模块207构成。

另外，程序等价性验证程序200是在OS(OperatingSystem，操作系统) 上运行的应用软件，作为源代码等价性验证装置的软件结构，还包含OS、库 程序，但在的图中被省略。

源代码解析模块201是进行源代码的字句解析/句法解析，取出为了结构 图生成所需要的信息的模块。

结构图生成/更新模块202是根据源代码解析模块201的解析结果生成或 更新结构图的模块。

结构图解析模块203是解析结构图的图结构的模块。

执行树生成模块204是根据结构图解析模块203的解析结果生成执行树的 模块。

符号执行执行模块205是进行针对执行树生成模块204生成的执行树的符 号执行的模块。

输入输出模块206是从外部输入输出必要的数据的模块。

数据库模块207是用于访问各种数据库的模块。

图3是表示源代码等价性验证装置1000的功能结构图。控制部110由图 1的CPU101、主存储装置102构成，存储部1600由图1的HDD141构成， 但有时也包含主存储装置102。输入装置130包括图1的输入输出I/F105、键 盘131、鼠标132等，还可以包括经由辅助存储装置I/F106从DVD驱动装置 142读入的结构。输出装置120包括图形I/F104、显示装置120等，还可以包 括经由辅助存储装置I/F106向DVD驱动装置142写入的结构。通信部103表 示图1的网络I/F103，经由网络150例如与外部计算机160连接。

存储部1600预先具备源代码等价性验证程序200、在本装置中预先登录 有对应的重构的种类的重构模式登录信息1120、针对每个上述重构模式预先 登录有对重构前/后源代码信息实施的正规化处理的正规化数据库1601以及针 对每个上述重构模式预先登录有对重构前/后源代码信息实施的抽象化处理的 抽象化数据库1602。

存储部1600还具有在实施源代码等价性验证处理时要确保的重构前/后源 代码存储区域1603、重构前/后源代码信息存储区域1604、重构前/后符号执行 结果存储区域1605以及验证结果存储区域1606。

控制部110从存储部1600加载源代码等价性验证程序200并通过CPU101 执行，由此实现输入部1100、正规化部1200、结构比较验证处理部1300、符 号执行实施判定部1700、符号执行验证处理部1400、输出部1500的各功能。

接着，使用图4至图10，对本发明一实施方式的源代码等价性验证装置 的各功能和它们的处理进行说明。

图4是表示本发明一实施方式的源代码等价性验证装置整体的功能和数 据流程的图。

图5是表示本发明一实施方式的源代码等价性验证装置的处理的流程图。

图6是表示输入部1100的功能的细节和数据流程的图。

图7是表示正规化部1200的功能的细节和数据流程的图。

图8是表示结构比较验证处理部1300的功能的细节和数据流程的图。

图9是表示符号执行实施判定部1700的功能的细节和数据流程的图。

图10是表示符号执行验证处理部1400的功能的细节和数据流程的图。

软件开发者为了对通过安装在外部计算机160上的软件开发装置生成的 软件实施重构来验证重构实施后的源代码是否与重构实施前的源代码等价，将 重构前/后源代码经由网络150发送给源代码等价性验证装置1000，委托验证。 所委托的重构前/后源代码被存储在存储部1600的重构前/后源代码存储区域 1603中，进行等价性验证处理。

或者，当软件开发装置被安装在与本实施方式的源代码等价性验证装置 1000相同的个人计算机上的情况下，软件开发者通过图3的输入装置130等 输入重构前/后源代码，将这些数据存储在重构前/后源代码存储区域1603中并 执行等价性验证处理。

当软件开发者输入重构前/后源代码来委托等价性验证处理时，附加输入 表示实施了什么种类的重构的重构模式输入信息0003。

如图4所示，本实施方式的源代码等价性验证装置1000通过输入重构前 源代码0001、重构后源代码0002两个源代码和针对重构前源代码0001应用 的与重构模式相关的输入信息即重构模式输入信息0003，来验证重构前源代 码0001和重构后源代码0002的源代码的等价性。

首先，在输入部1100接受输入的或已存储在存储部1603中的重构前源代 码0001(图5的S101)。在重构后源代码输入步骤S102中，在输入部1100 接受重构后源代码0002(S102)。此外，在输入部1100接受重构模式输入信 息0003的输入(S103)。

以下，使用图6说明上述输入部1100的功能的细节及其处理。

如图6所示，重构前源代码0001通过输入部1100中的源代码输入部1101 被接受，进行源代码的字句解析和句法解析，变换为重构前源代码信息1001。 重构后源代码0002也通过输入部1100中的源代码输入部1101被接受，进行 源代码的字句解析和句法解析，变换为重构后源代码信息1002，存储在存储 部1600中。此外，重构模式输入信息0003通过输入部1100中的重构模式输 入部1102被接受，变换为表示重构模式种类的重构模式信息1003，存储在存 储部1600中。

接着，比较重构前源代码信息1001和重构后源代码信息1002，确定源代 码的结构上的变更位置(S1041)。

然后，正规化部1200使用存储在存储部1600中的信息，进行重构前源代 码信息1001和重构后源代码信息1002的正规化(S1042)。

在此，正规化表示将进行了重构的源代码的源代码信息变换为与该源代码 等价的源代码所对应的源代码信息。以适于之后接下来的结构比较步骤S1043 和符号执行步骤S1045的形式进行该正规化。

以下，使用图7说明上述正规化部1200的功能的细节及其处理。

向正规化部1200的变更位置确定部1201输入重构前源代码信息1001和 重构后源代码信息1002。另一方面，读出与存储在正规化DB1601中的重构 模式信息1003对应的变更位置确定信息1007b。然后，变更位置确定部1201 比较源代码信息，参照与重构模式信息1003对应的变更位置确定信息1007b， 确定源代码的构造上的变更位置，生成变更位置信息1004(S1041)。

接着，从存储部1600的正规化DB1601取得与重构模式输入信息1003对 应的表示正规化方法的正规化信息1007a(S1042)。在正规化DB1601中存储 与每个重构模式对应的正规化信息1007a。在正规化部1200的源代码正规化 部1202中，根据所取得的正规化信息1007a针对重构前源代码信息1001进行 正规化，生成重构前正规化源代码信息1005。此外，在正规化部1200的源代 码正规化部1202中，根据正规化信息1007a针对重构后源代码信息1002进行 正规化，生成重构后正规化源代码信息1006。

接着，结构比较验证处理部1300比较重构前正规化源代码信息1005和重 构后正规化源代码信息1006的结构，验证是否是相同结构(步骤S1043)。

以下，使用图8说明结构比较验证处理部1300的功能的细节及其处理。

结构比较验证处理部1300接受重构前正规化源代码信息1005和重构后正 规化源代码信息1006，进行两个正规化后的源代码信息的结构是否一致的比 较，在一致的情况下，作为结构比较结果1008而生成一致这样的信息，在不 一致的情况下，作为结构比较结果1008而生成不一致这样的信息(S1043)。

接着，在符号执行实施判定部1700中判定是否应进行符号执行(S1047)。 在此，在上述的结构比较步骤S1043的结果中，若判定为结构一致，则向等价 非等价输出步骤S105前进，若判定为结构不一致，则向源代码信息抽象化步 骤S1044前进。

以下，使用图9说明符号执行实施判定部1700的功能的细节及其处理。

符号执行实施判定部1700接受结构比较结果1008，在结构比较结果1008 中，若结构为“一致”，则向等价非等价输出步骤S105转移，通过输出部1500 输出验证结果0004来作为源代码等价。

在输出了源代码等价这样的结果时，用户能够判定为进行的重构是正当 的。

符号执行实施判定部1700接受结构比较结果1008，在结构比较结果1008 中，若结构为“不一致”，则生成符号执行开始指示1009。

接着,进行源代码信息的抽象化(S1044)。

在此，源代码信息的抽象化表示针对各个源代码信息进行了符号执行时， 在维持赋予相同输入而输出相同结果的状态下，简化源代码信息。

接着，对抽象化后的重构前的源代码信息和抽象化后的重构后的源代码信 息进行符号执行(S1045)。

然后，逻辑性比较符号执行的结果(符号执行一览)，在对相同输入得到 相同结果时，判定为原始的源代码等价，在输出(符号执行一览)不同时，判 定为原始的源代码非等价(S1046)而进行等价非等价的结果输出。

比较重构前和重构后的符号执行的结果即符号执行一览，通过使用SAT 解法或SMT解法或被称为决定手续等的方法来进行逻辑上是否等价的判定。 针对构成符号执行一览的各叶节点求出其路径制约和变量状态的逻辑积，通过 计算它们的逻辑和能够生成用于表现符号执行一览的逻辑式。通过SAT解法 判定由重构前的符号执行一览生成的逻辑式和由重构后的符号执行一览生成 的逻辑式等价，由此能够判定符号执行一览的等价性。

在此，当输出源代码为等价的结果时，用户可以判断为所进行的重构是正 当的，当输出源代码为非等价的结果时，用户可以判断为所进行的重构是不当 的。然后，用户在判断为所进行的重构不当时，能够重新评价所进行的重构， 开始修正为正当的作业。

符号执行验证处理部1400接受符号执行开始指示1009并开始源代码抽象 化步骤S1044。在源代码抽象化步骤S1044中，使用存储在存储部1600的抽 象化DB1602中的抽象化信息1010，接受重构前正规化源代码信息和变更位 置信息1004并进行抽象化，生成重构前抽象化源代码信息1403。此外，在源 代码抽象化步骤S1044中，使用存储在存储部1600的抽象化DB1602中的抽 象化信息1010，接受重构后正规化源代码信息和变更位置信息1004并进行抽 象化，生成重构后抽象化源代码信息1404。在此，存储在抽象化DB中的抽 象化信息1010是与以下的处理方法相关的信息：针对正规化后的源代码信息 置换与变更位置信息1004无关的位置和循环或递归调用的位置，在进行之后 的符号执行步骤S1045时，变换为不对与变更位置信息1004无关的位置和循 环或递归调用的位置进行符号执行。

在符号执行步骤S1045中，在符号执行部1402对重构前抽象化源代码信 息1403和重构后抽象化源代码信息1404进行符号执行，分别得到重构前符号 执行结果1405和重构后符号执行结果1406。在符号执行结果比较步骤S1046 中，在符号执行结果比较部1407比较判定重构前符号执行结果1405与重构后 符号执行结果1406是否相同。在符号执行结果比较部1407中，在重构前符号 执行结果1405与重构后符号执行结果1406相同的情况下，向等价非等价输出 步骤S105转移，作为等价而向输出部1500输出验证结果0004。在符号执行 结果比较部1407中，在重构前符号执行结果1405与重构后符号执行结果1406 不同的情况下，向等价非等价输出步骤S105转移，作为非等价而向输出部1500 输出验证结果0004。

根据本实施方式的源代码等价性验证装置，在进行计算量容易爆发的符号 执行前，分别对重构前后的各个源代码信息进行正规化后进行结构比较，在判 定为成为其原始的源代码等价的情况下，不进行符号执行。

此外，通过结构比较判定为成为原始的源代码非等价的情况下，进行源代 码信息的抽象化，缩减源代码信息后进行符号执行，因此能够削减符号执行的 计算。

实施例2

以下，参照上述图5，使用图11至图14，对本发明一实施方式的源代码 等价性验证装置的处理的具体例进行说明。该例子是通过图5的符号执行实施 判定S1047的处理，判定为源代码信息即结构图的结构一致的例子。

图11是表示重构前后的源代码的例子的图(之一)。

图12是表示与重构前后的源代码对应的源代码信息的例子的图(之一)。

图13是表示针对源代码信息进行的正规化的例子的图。

图14是表示用于显示通过结构比较对正规化后的结构图进行了等价性验 证而得的结果的输出部的显示例的图。

在该例子中，作为针对源代码的重构，说明进行基于重构模式提取方法 (Extractmethod)的重构的情况。重构模式提取方法是在多个位置进行相同 处理的源代码中，将该相同处理作为函数来提取，将在多个位置进行相同处理 的位置置换为向所提取的函数的调用，对存在于多个位置的源代码进行共有化 的重构模式。也可以将该重构模式提取方法用作在一个函数中源代码的记述量 较多的情况下，为了提高函数的可读性，将该函数内的源代码的一部分作为其 他函数提取的重构。

以下，根据图11说明通过重构模式提取方法进行源代码的重构的例子。

源代码C001是应用重构模式提取方法前的源代码，是在主(main)函数 中对全局变量global＿var代入10的程序。对于该源代码C001，应用了重构 模式提取方法的源代码成为C002。源代码C002将源代码C001中的global＿ var＝10；这种向全局变量的赋值语句作为函数foo提取，将作为global＿var ＝10；的记述部分的位置置换为函数foo的调用。

首先，说明图11所示的重构例子中的、图5的重构前源代码输入S101、 重构后源代码输入S102以及重构模式S10的步骤。

在输入部1100中，通过源代码输入部1101接受重构前源代码0001和重 构后源代码0002来生成对应的重构前源代码信息1001和重构后源代码信息。 在此，重构前源代码0001对应于源代码C001，重构后源代码0002对应于源 代码C002。

在源代码等价性验证装置1000中，通过源代码输入部1101对重构前源代 码0001和重构后源代码0002进行字句解析和句法解析，变换为图12的例子 中所示的在内部处理的结构图。在重构模式提取方法的例子中，源代码C001 变换为结构图M001，源代码C002变换为结构图M002。在此，重构前源代码 信息1001对应于结构图M001，重构后源代码信息1002对应于结构图M002。

在输入部1100中，在重构模式输入部1102接受重构模式输入信息0003 来生成重构模式信息1003。在该例子中，例如当重构模式输入信息0003为表 示重构模式提取方法的字符串“表示重构模或画面菜单中的选择编号时，在内 部生成用于指示重构模式提取方法的代码作为重构模式信息1003。

接着，对图5的变更位置确定S1041的步骤进行说明。

在正规化部1200的变更位置确定部1201中，根据重构前源代码信息 1001、重构后源代码信息1002以及重构模式信息1003，参照与存储在正规化 DB1601中的对应的变更位置确定信息1007b，从结构图上确定变更了源代码 上的哪些地方并输出变更位置信息1004。在该重构模式提取方法的例子中， 重构模式提取方法根据在重构后源代码信息1002中函数(entryfoo)增加的特 征，比较重构前源代码信息1001和重构后源代码信息1002的函数的声明，将 仅在重构后源代码信息1002出现的函数确定为变更位置。在图12中，在重构 前源代码信息1001的结构图M001和重构后源代码信息1002的结构图M002 中比较表示函数的进入(entry)，节点M003指示的进入的foo函数增加，因 此节点M003和调用foo函数的节点M004相当于变更位置信息1004。

接着，对图5的源代码信息正规化S1042的步骤进行说明。在正规化部 1200的源代码正规化部1202中，根据变更位置信息1004和重构前源代码信 息1001使用与存储在正规化DB1601中的对应的正规化信息1007a进行正规 化，生成重构前正规化源代码信息1005。重构后源代码信息1002也同样地进 行正规化，生成重构后正规化源代码信息1006。表示该重构模式提取方法的 源代码正规化部1202的例子时，成为如图13所示。首先，从正规化DB1601 取得重构模式信息1003即与重构模式提取方法对应的正规化信息1007a。根 据与重构模式信息1003的提取方法对应的正规化信息1007a，正规化方法将 提取的重构后源代码信息0002中的变更位置1004的函数设为表示进行内联扩 展而返回到原始时的源代码的结构。

图13中的变更位置信息1004是重构后源代码信息1002的结构图M002 中的节点M003和节点M004，这些节点是通过重构生成并被提取的函数foo， 因此若对该函数foo进行正规化而返回到原始，则成为结构图M006。其成为 重构后正规化源代码信息1006。重构前正规化源代码信息1005对重构模式提 取方法没有进行正规化处理，因此图13中的重构前源代码信息0001的结构图 M001在正规化中没有任何变更，而直接成为结构图M005。

接着，对图5的构造比较S1043的步骤进行说明。

在结构比较验证处理部1300中接受重构前正规化源代码信息1005和重构 后正规化源代码信息1006，进行源代码信息的结构的比较，将其结果生成为 结构比较结果1008。在进行了基于重构模式提取方法的重构的图13的例子中， 因重构前正规化源代码信息1005的图M005和重构后正规化源代码信息1006 的图M006两个图是相同结构且各个节点相同，因此作为结构比较结果1008， 结构比较验证处理部1300判定源代码C001和源代码C002等价。

接着，对图5的符号执行实施判定S1047的步骤进行说明。

在进行了基于重构模式提取方法的重构的图11的例子中，作为结构比较 结果1008，符号执行实施判定部1700判定重构前后的源等价，因此向等价非 等价输出步骤S105转移，输出部1500接受结构比较验证处理部1300判定为 等价的结果，作为验证结果0004输出等价。

在进行了基于重构模式提取方法的重构的图11的例子中，符号执行实施 判定部1700根据基于正规化部1200的变换和结构比较验证处理部1300的判 定处理能够判定为重构前后的源代码分别等价，因此不需要通过符号执行验证 处理部1400进行符号执行的计算，不增加不必要的计算量地能够进行迅速的 等价判定。

图14表示通过结构比较验证处理部1300的判定处理判定为等价时的基于 输出部1500的验证结果0004的显示例。在图14所示的显示例中示出了作为 判定结果P100通过结构比较进行判定的情况以及判定为其结果等价的情况。 此外，作为在结构比较中使用的结构图数据，显示实施了正规化后的重构前正 规化源代码信息的结构图P111和重构后正规化源代码信息的结构图P112。并 且，作为重构应用信息P120显示了应用的重构模式名即提取方法、通过提取 方法提取的函数名即foo，作为应用该重构模式的位置信息对重构应用前源代 码显示文件名sample.c和行编号3，对重构应用后源代码显示文件名sample.c 和行编号6。

通过观察图14所示的重构应用信息P120，能够确认等价性验证装置识别 出的重构模式和位置与开发者所意图的重构一致。

实施例3

以下，参照上述图5，使用图15至图20，对本发明一实施方式的源代码 等价性验证装置的处理的具体例进行说明。该例子是通过图5的符号执行实施 判定的处理，在被实施了不依赖于重构模式的重构的源代码中，判定为源代码 信息即结构图的结构不一致的例子。

图15是表示重构前后的源代码的例子的图(之二)。

图16是表示与重构前后的源代码对应的源代码信息的例子的图(之二)。

图17是表示抽象化后的源代码信息的例子的图。

图18是表示针对重构前源代码和重构后源代码进行了符号执行时的执行 树的例子。

图19是为了说明符号执行的一例，表示源代码和由其派生的数据结构的 图。

图20是表示用于显示通过符号执行验证处理部进行了等价性验证而得的 结果的显示部的显示例的图。

在该例子中，作为针对源代码的重构，说明不变更源代码的条件式地进行 整理向变量的代入的重构的情况。

在图15中示出了重构前的源代码C003和重构后的源代码C004，在源代 码C003和源代码C004之间应用不变更源代码的条件式地整理向变量的代入 的重构。具体而言，在重构前的源代码C003中，在源代码部分C005所示的 位置，针对变量a代入值，在源代码部分C006所示的位置，使用变量a(右 边)的值进行运算并代入到变量a(左边)。在重构后的源代码C004中，在源 代码部分C007所示的位置，针对变量b代入值，在源代码部分C008所示的 位置，使用变量b的值进行运算并代入到变量a。在重构前后，存在于源代码 部分C005所示的位置和源代码部分C007所示的位置的条件式与存在于源代 码部分C006所示的位置和源代码部分C008所示的位置的条件式一致，但变 更使用的变量，源代码C004的源代码行数少可读性高。图15的例子所示的 重构不符合非专利文献4所记载的72种重构模式，在本实施方式的源代码等 价性验证装置1000中，也没有作为模式登录在数据库中。

首先，说明图15所示的重构例子中的、图5的重构前源代码输入S101 和重构后源代码输入S102。在该重构的例子中，重构前源代码0001对应于源 代码C003，重构后源代码0002对应于源代码C004。在输入部1100中，通过 源代码输入部1101接受重构前源代码0001和重构后源代码0002来生成对应 的重构前源代码信息1001和重构后源代码信息1002。在图15的重构例子中， 源代码输入部1101接受源代码C003作为重构前源代码0001，进行字句解析 和句法解析，作为重构前源代码信息1001变换为图16的结构图M008。此外， 源代码输入部1101接受源代码C004作为重构后源代码0002，进行字句解析 和句法解析，作为重构后源代码信息1002变换为图16的结构图M009。在此， 重构前源代码信息1001对应于结构图M008，重构后源代码信息1002对应于 结构图M009。

接着，对输入与重构模式相关的信息的S103的步骤进行说明。

在输入部1100中，在重构模式输入部1102接受重构模式输入信息0003 来生成重构模式信息1003。在该重构例子中，假定没有登录重构模式，因此 向重构模式输入部1102输入表示“入符合”的字符串或菜单的选择编号，重构 模式输入部生成表示“无符合”的代码作为重构模式信息1003。

接着，对图5的变更位置确定S1041的步骤进行说明。

在正规化部1200的变更位置确定部1201中，根据重构前源代码信息1001 和重构后源代码信息1002确定变更了源代码中的哪个位置，输出变更位置信 息1004。在该重构例子中，比较重构前源代码信息1001即结构图M008与重 构后源代码信息0002即结构图M009，在双方中存在函数foo和函数var，因 此没有函数等级的增减，在foo函数的内部中可观察到差异，因此变更位置确 定部1201输出foo函数的内部作为变更位置信息1004。另外，在该例子中， 作为重构模式是“，作为重，因此不参照正规化DB1601的变更位置确定信息 1007b，而仅通过解析结构图的结构来确定变更位置。

接着，对图5的源代码信息正规化S1042的步骤进行说明。

在正规化部1200的源代码正规化部1202中，根据变更位置信息1004和 重构前源代码信息1001使用正规化DB1601中的对应的正规化信息1007a的 正规化方法来进行正规化，生成重构前正规化源代码信息1005。重构后源代 码信息1002也同样地进行正规化，生成重构后正规化源代码信息1006。在该 重构例子中，从正规化DB1601取得重构模式信息1003与“无符合”对应的 正规化信息。在此，重构模式信息1003与“无符合”对应的正规化信息没有 变换，因此源代码正规化部1202对重构前源代码信息1001和重构后源代码信 息1002不进行任何变更地输出重构前正规化源代码信息1005重构后正规化源 代码信息1006。在正规化部1200没有进行变换，因此重构前正规化源代码信 息1005是图16中的结构图M008，重构后正规化源代码信息1006是图16中 的结构图M009。

接着，对图5的构造比较S1043的步骤进行说明。

在结构比较验证处理部1300中接受重构前正规化源代码信息1005和重构 后正规化源代码信息1006，进行源代码信息的结构的比较，生成结构比较结 果1008。

考虑了各种探索多个图结构之间的一致/不一致的方法，例如列举了这样 的方法：以从层级的最上位节点开始比较，之后进行其子节点间的比较，进一 步其子节点间的比较的方式依次降低层级，进行所有层级的节点间的比较，若 在其中途判定为不一致，则判定为两图结构不同。

在该重构例子中，比较重构前正规化源代码信息1005的图M008与重构 后正规化源代码信息1006的结构图M009，在图M009中没有节点“进入foo (entryfoo)”的子节点“a＝0”，因此明确判定为图结构不同，将结构比较结果 1008判定为重构前后的源代码非等价。

接着，对图5的符号执行实施判定步骤S1047进行说明。

在该重构例子中，作为结构比较结果1008，符号执行实施判定部1700判 定为源代码非等价，因此生成符号执行开始指示1009的指令。

接着，对图5的源代码信息抽象化步骤S1044进行说明。

在符号执行验证处理部1400接受符号执行开始指示1009时，在抽象化部 1401使用变更位置信息1004和抽象化DB1602的记录了抽象化方法的抽象化 信息1010进行重构前正规化源代码信息1005和重构后正规化源代码信息 1006的抽象化。在抽象化DB1602的抽象化信息1010中与变更位置信息1004 对应地记录有恰当的抽象化方法。在该重构例子中，判明变更位置信息1004 为函数foo的内部，因此从抽象化DB1602取得抽象化信息1010，其中，该抽 象化信息1010记载了在去除了函数foo的源代码中，将在重构前后没有差异 的函数变换为变量并抽象化的方法。表示在抽象化部1401将在重构前后没有 差异的函数变换为变量并抽象化的方法应用于重构前正规化源代码信息1005 的图M008和重构后正规化源代码信息1006的图M009的结果时，成为如图 17所示。在图16的重构前正规化源代码信息1005的结构图M008中，节点 M010的函数var通过重构没有产生差异，因此与调用函数var的位置的节点 M011对应地作为变量v进行抽象化，变换为图17的结构图M014。但是，在 该抽象化中，节点M010和其他节点必须没有数据依存性(DataDependency)。 关于图16中的重构后正规化源代码信息1006的图M009，同样地进行抽象化 而变换为结构图M015。抽象化部1401将上述结构图M014作为重构前抽象化 源代码信息1403输出，将上述结构图M015作为重构后抽象化源代码信息1404 输出。在此，应注意关于该抽象化，在各个结构图M008、M009中，节点被 剪切，在对各个进行了符号执行时计算量减少。

接着，对图5的符号执行S1045的步骤进行说明。

在符号执行验证处理部1400中，在抽象化部1401进行了抽象化后，在符 号执行部1402分别对重构前抽象化源代码信息1403和重构后抽象化源代码信 息1404进行符号执行，作为其结果生成重构前符号执行结果1405和重构后符 号执行结果1406。在该重构例子中，在符号执行部1402对上述重构前抽象化 源代码信息1403和重构后抽象化源代码信息1404进行了符号执行的结果成为 如图18所示。在该重构例子中，重构前抽象化源代码信息1403相当于图17 的结构图M014，对结构图M014进行符号执行时，能够得到图18中的执行树 E100。此外，图18的执行树E100中的符号执行一览即E101、E102、E103、 E104是针对重构前抽象化源代码信息1403的重构前符号执行结果1405。重 构后抽象化源代码信息1404相当于图17的结构图M015，对结构图M015进 行符号执行时，能够得到图18中的执行树E200。此外，图18的执行树E200 中的符号执行一览即E201、E202、E203、E204是针对重构后抽象化源代码信 息1404的重构后符号执行结果1406。

接着，对图5的符号执行结果比较S1046的步骤进行说明。

在符号执行验证处理部1400的符号执行结果比较部1407中比较重构前符 号执行结果1405和重构后符号执行结果1406是否逻辑上等价，进行重构前后 的源代码等价还是非等价的判定。在图15的重构例子中，重构前符号执行结 果1405是E101、E102、E103、E104，重构后符号执行结果1406是E201、 E202、E203、E204。按以下方式判定这些两个符号执行结果逻辑上等价。

作为表示重构前的符号执行一览的逻辑式，取E101的路径制约和变量状 态的逻辑积、E102的路径制约变量状态的逻辑积、E103的路径制约和变量状 态的逻辑积、E104的路径制约变量状态的逻辑积这4个逻辑式的逻辑和。即， ((β＜0)AND(γ＜0)AND(a＝－γ)AND(b＝0)AND(v＝γ))OR((β ＜0)AND(NOT(γ＜0))AND(a＝γ)AND(b＝0)AND(v＝γ))OR((NOT (β＜0))AND(γ＜0)AND(a＝β－γ)AND(b＝β)AND(v＝γ))OR((NOT (β＜0))AND(NOT(γ＜0))AND(a＝β+γ)AND(b＝β)AND(v＝γ)) 是表现重构前的符号执行一览的逻辑式。作为表示重构后的符号执行一览的逻 辑式，取E201的路径制约和变量状态的逻辑积、E202的路径制约和变量状态 的逻辑积、E203的路径制约和变量状态的逻辑积、E204的路径制约和变量状 态的逻辑积这4个逻辑式的逻辑和。方便起见，将重构后的输出变量a、b、v 的值分别设为a’，b’，v’时，表现重构后的符号执行一览的逻辑式为((β＜0) AND(γ＜0)AND(a’＝－γ)AND(b’＝0)AND(v’＝γ))OR((β＜0)AND (NOT(γ＜0))AND(a’＝γ)AND(b’＝0)AND(v’＝γ))OR((NOT(β ＜0))AND(γ＜0)AND(a’＝β－γ)AND(b’＝β)AND(v’＝γ))OR((NOT (β＜0))AND(NOT(γ＜0))AND(a’＝β+γ)AND(b’＝β)AND(v’＝γ))。

判定表现重构前的符号执行一览的逻辑式和表现重构后的符号执行一览 的逻辑式在逻辑上是否等价。

在该判定方法中，在表现上述重构前的符号执行一览的逻辑式和表现重构 后的符号执行一览的逻辑式分别包含的符号变量的值相同的情况下，只要验证 输出变量的值相等即可。关于这点，可以通过SAT解法解决针对表现重构前 符号执行一览的逻辑式、表现重构后符号执行一览的逻辑式以及逻辑式NOT ((a＝a’)AND(b＝b’)AND(v＝v’))的逻辑积的式的充分可能性问题来 实现。若通过SAT解法解决的结果为不可能充分，则在赋予相同输入值的情 况下，可知在重构前和重构后不可能得到不同的输出值，因此判定为逻辑上等 价。在可能充分的情况下，表示存在对相同输入值在重构前和重构后得到不同 值的情况。此时，使用SAT解法输出的可能充分的值的例子，能够得到非等 价的输入值的例子(反例)。在此使用的SAT解法使用一般提供的程序。

在该例子中，能够得到两者的逻辑式等价的结果。该结果也可以分别从 E101和E201的对、E102和E202的对、E103和E203的对、E104和E204的 对的路径制约和变量状态一致中获知。

符号执行结果比较部1407将通过SAT解法得到的等价的判定发送给输出 部1500。此时，在重构前的符号执行树E100和重构后的符号执行树E200之 间产生结构上的差异，但符号执行的最终的符号执行一览逻辑上一致，因此判 定为源代码等价。

接着，对图5的等价非等价输出S105的步骤进行说明。

输出部1500接受符号执行结果比较部1407判定为源代码等价的结果后， 作为验证结果0004输出源代码等价。图20表示输出部1500输出的验证结果 0004的例子。

在图20所示的显示例中示出了作为判定结果P200通过符号执行判定的情 况以及判定为该结果等价的情况。此外，作为在结构比较中使用的结构图数据， 显示实施了正规化后的重构前正规化源代码信息的结构图P211和重构后正规 化源代码信息的结构图P212。并且，作为重构应用信息P220显示所应用的正 规化重构模式为“化重构模。在结构图P211和P212中，通过对结构比较的结 果判断为差异的节点改变颜色，知道结构比较的结果源代码中的哪个部分被判 断为不等价。此外，通过比较显示结构图，知道如何实施了抽象化。

在图20所示的显示例中，作为基于符号执行的判定特有的信息显示针对 重构前的源代码的符号执行一览信息P230以及针对重构后的源代码的符号执 行一览信息P231。在符号执行一览信息P230和P231中，分别逐行显示E101、 E102、E103、E104以及E201、E202、E203、E204中的路径制约和变量状态。 由此，开发者能够知道符号执行的结果，且能够知道使用哪些逻辑式对等价性 进行了判定。并且，由此用户能够判断重构妥当。

图20所示的显示例是通过符号执行判定为等价的情况的显示例。在通过 符号执行判定为非等价的情况下，除了图20所示的信息外，还显示反例信息。 反例信息是通过SAT解法得到的、重构前的符号执行一览和重构后的符号执 行一览不等价的输入例。通过显示该反例信息，开发者能够知道针对哪些输入 进行了重构前的源代码和重构后的源代码不同的输出。由此，能够分析成为不 恰当的重构的原因。

在本例子中，通过符号执行实施判定S1047的判定确认作为源代码信息的 结构图上的结构的差异，因此为了验证源代码等价而实施符号执行。通过进行 源代码信息的抽象化、源代码信息的缩减，在符号执行处理中能够削减符号执 行的计算量。

实施例4

以下，参照上述图5，使用图21至图27，对本发明一实施方式的源代码 等价性验证装置的处理的具体例进行说明。该例子通过图5的符号执行实施判 定S1047的处理，在被实施了与登录的重构模式对应的重构的源代码中，判定 源代码信息即结构图的结构不一致。

图21是表示重构前后的源代码的例子的图(之三)。

图22是表示与重构前的源代码对应的源代码信息的例子的图(之三)。

图23是表示与重构后的源代码对应的源代码信息的例子的图(之三)。

图24是表示正规化后的重构后的源代码信息的例子的图。

图25是表示抽象化后的源代码信息的例子的图。

图26是表示被抽象化时的、针对重构前源代码和重构后源代码进行了符 号执行时的执行树的例子。

图27是表示被抽象化时的、基于显示部的等价性验证结果的显示例的图。

在该例子中，作为针对源代码的重构，说明根据重构模式参数化方法 (ParameterizedMethod)进行了重构的情况。重构模式参数化方法是在多个位 置进行相似处理的源代码中，将该相似处理作为函数来提取，将在多个位置进 行相似处理的位置置换为所提取的函数的调用，对存在于多个位置的相似源代 码进行共有化的重构模式。

两者的不同点在于，在上述的提取方法中假定了提取相同处理，但参数化 方法假定了提取类似但不相同的处理。在参数化方法中，在实现类似但不相同 的处理的提取时，在所提取的函数中接受表示处理的差异的种类的自变量，通 过针对该自变量的条件分支实现差异。在所提取的位置中附带表示差异的自变 量调用所提取的函数，来吸收处理的差异。

在图21中示出了重构前的源代码C009和重构后的源代码C010。源代码 C009是重构模式参数化方法的应用前的源代码，函数foo1由将全局变量a和 全局变量b相加后代入到全局变量c，并以全局变量c为自变量调用函数bar 的C011部分和以全局变量c为自变量调用函数qux1的C012部分构成，函数 foo2由将全局变量a和全局变量b相减后带入到全局变量c，并以全局变量c 为自变量调用函数bar的C013部分和以全局变量c为自变量调用函数qux2的 C014部分构成。源代码C010是重构模式参数化方法应用后的源代码，将源代 码C009中的函数foo1内的处理的一部分即C011的位置和类似的函数foo2内 的处理的一部分即C013的位置作为函数baz来提取，在与所提取的位置对应 的位置即C015和C015中置换为向函数baz的调用。在所提取的函数baz中， 在C019所示的处理部分通过针对取真假值的自变量的条件分支分配函数foo1 的C011和函数foo2的C013的差异即全局变量a和全局变量b的相加处理和 相减处理而对应。

说明图21所示的重构例子中的、图5的重构前源代码输入S101和重构后 源代码输入S102。在该重构的例子中，重构前源代码0001对应于源代码C009， 重构后源代码0002对应于源代码C010。在输入部1100中，通过源代码输入 部1101接受重构前源代码0001和重构后源代码0002来生成对应的重构前源 代码信息1001和重构后源代码信息1002。

在图21的重构例子中，源代码输入部1101接受源代码C009作为重构前 源代码0001，进行字句解析和句法解析，作为重构前源代码信息1001变换为 图22的结构图M017。此外，源代码输入部1101接受源代码C010作为重构 后源代码0002，进行字句解析和句法解析，作为重构后源代码信息1002变换 为图23的结构图M018。在此，重构前源代码信息1001对应于结构图M017， 重构后源代码信息1002对应于结构图M018。

接着，对输入与重构模式相关的信息的S103的步骤进行说明。

在输入部1100中，在重构模式输入部1102接受重构模式输入信息0003 来生成重构模式信息1003。在该例子中，例如当重构模式输入信息0003为表 示重构模式参数化方法的字符串“表示重构模(ParameterizedMethod)”或画 面菜单中的选择编号时，参照重构模式登录信息1120，在内部生成用于指示 重构模式参数化方法的代码即重构模式信息1003。

接着，对图5的变更位置确定S1041的步骤进行说明。

在正规化部1200的变更位置确定部1201中，根据重构前源代码信息 1001、重构后源代码信息1002以及重构模式信息1003，参照与登录在正规化 DB1601中的对应的变更位置确定信息1007b，确定变更了源代码上的哪些地 方并输出变更位置信息1004。在该重构模式参数化方法的例子中，重构模式 参数化方法根据在重构后源代码信息1002函数增加的特征，比较重构前源代 码信息1001和重构后源代码信息1002的函数的声明，将仅在重构后源代码信 息1002出现的函数声明节点确定为变更位置信息。此外，将调用仅在重构后 源代码信息1002出现的函数的节点也设为变更位置信息1004。在图22和图 23中，在重构前源代码信息1001的结构图M017和重构后源代码信息1002 的结构图M018中，比较表示函数的进入(entry)节点，节点M019指示的进 入(entry)节点的函数baz增加，因此节点M019相当于变更位置信息1004。 并且，调用函数baz的节点M020和M021也相当于变更位置信息1004。

接着，对图5的源代码信息正规化S1042的步骤进行说明。在正规化部 1200的源代码正规化部1202中，根据变更位置信息1004和重构前源代码信 息1001使用与正规化DB1601中的对应的正规化信息1007a来进行正规化， 生成重构前正规化源代码信息1005。重构后源代码信息1002也同样地进行正 规化，生成重构后正规化源代码信息1006。根据作为重构模式信息1003的与 重构模式参数化方法对应的正规化信息1007a，正规化方法将针对重构后源代 码信息0002在变更位置1004识别并提取的函数设为表示进行内联扩展时的源 代码的结构。表示针对重构后源代码信息1002通过源代码正规化部1202进行 了正规化的例子时，成为如图24所示。

图24中的变更位置是重构后源代码信息1002的结构图M018中的节点 M019、节点M020以及节点M021，这些节点是通过重构提取的函数baz的声 明以及调用位置，因此若对该函数baz进行正规化并内联扩展，则成为结构图 M022。其成为重构后正规化源代码信息1006。重构前正规化源代码信息1005 关于重构模式参数化方法，没有进行正规化处理，因此重构前源代码信息1001 的结构图M017在正规化中没有任何变更，而直接成为重构前正规化源代码信 息1005。

接着，对图5的构造比较S1043的步骤进行说明。

在结构比较验证处理部1300中接受重构前正规化源代码信息1005和重构 后正规化源代码信息1006，进行源代码信息的结构的比较，将其结果生成为 结构比较结果1008。在进行了基于重构模式参数化方法的重构的图21的例子 中，结构比较验证处理部1300比较重构前正规化源代码信息1005的图M017 和重构后正规化源代码信息1006的图M022两个图，图结构明确不同，因此 将结构比较结果1008判定为重构前后的源代码为结构不一致的非等价。

接着，对图5的符号执行实施判定步骤S1047进行说明。

在该重构例子中，作为结构比较结果1008，符号执行实施判定部1700判 定为源代码非等价，因此生成符号执行开始指示1009的指令。

接着，对图5的源代码信息抽象化步骤S1044进行说明。

在符号执行验证处理部1400接受符号执行开始指示1009时，在抽象化部 1401使用变更位置信息1004和抽象化DB1602的记录了抽象化方法的抽象化 信息1010进行重构前正规化源代码信息1005和重构后正规化源代码信息 1006的抽象化。在抽象化DB1602的抽象化信息1010中与重构模式信息1003 和变更位置信息1004对应地登录有恰当的抽象化方法。在重构模式信息1003 为重构模式参数化方法的例子中，比较重构前正规化源代码信息1005即图 M017与重构后正规化源代码信息1006即图M022，从抽象化DB1602取得记 载了删除所有具有相同图结构的位置的抽象化信息1010。表示在抽象化部 1401中对重构前正规化源代码信息1005即图M017和重构后正规化源代码信 息1006即图M022应用抽象化信息1010而得的结果时，成为如图25所示。 比较表示重构前正规化源代码信息1005即图M017的函数foo1的图与表示重 构后正规化源代码信息1006即图M022的函数foo1的图时，调用函数bar的 图M017的节点M023和图M022的节点M025一致，调用函数qux的图M017 的节点M024和图M022的节点M026一致，因此删除这些节点，同样地对函 数foo2删除所有的具有相同图结构的位置时，重构前正规化源代码信息1005 即图表M017被抽象化成图M027，重构后正规化源代码信息1006即图M022 被抽象化成图表M028。图M027相当于重构前抽象化源代码信息1403，图 M028相当于重构后抽象化源代码信息1404。在此，应注意关于该抽象化，在 各个图M017、M022中，节点数量减少，对各个图进行了符号执行时其计算 量减小。

接着，对图5的符号执行S1045的步骤进行说明。

在符号执行验证处理部1400中，在抽象化部1401进行了抽象化后，在符 号执行部1402分别对重构前抽象化源代码信息1403和重构后抽象化源代码信 息1404实施符号执行，作为其结果生成重构前符号执行结果1405和重构后符 号执行结果1406。在该重构例子中，在符号执行部1402对上述重构前抽象化 源代码信息1403和重构后抽象化源代码信息1404的各个函数foo1进行了符 号执行的结果，成为如图26所示。在该重构例子中，重构前抽象化源代码信 息1403相当于图25的结构图M027。对结构图M027进行符号执行时，能够 得到图26中的执行树E300。此外，图26的执行树E300中的符号执行一览即 E301成为与重构前抽象化源代码信息1403对应的重构前符号执行结果1405。 在图21的重构例子中，重构后抽象化源代码信息1404相当于图25的结构图 M028，对结构图M028进行符号执行时，能够得到图26中的执行树E400。 此外，图26的执行树E400中的符号执行一览即E401、E402成为与重构后抽 象化源代码信息1404对应的重构后符号执行结果1406。关于函数foo2，在符 号执行部1402中同样地分别对重构前抽象化源代码信息1403和重构后抽象化 源代码信息1404进行符号执行。对重构前抽象化源代码信息1403生成执行树 E350，执行树E350中的符号执行一览即E351成为重构前符号执行结果1405。 对重构后抽象化源代码信息1404生成执行树E450，其符号执行一览即E451 和E452成为重构后符号执行结果1406。

接着，对图5的符号执行结果比较S1046的步骤进行说明。

在符号执行验证处理部1400的符号执行结果比较部1407中，进行重构前 符号执行结果1405和重构后符号执行结果1406的比较，进行重构前后的源代 码等价还是非等价的判定。在图21的重构例子中，针对函数foo1的重构前符 号执行结果1405是E301，重构后符号执行结果1406是E401、E402。通过 SAT解法比较这两个符号执行结果，由此符号执行结果比较部1407对函数 foo1判定源代码等价。在该例子中，从因E402的路径制约为矛盾式而认为E402 不存在，以及E301和E401的变量状态一致，且路径制约都是恒真式中知道 符号执行一览等价。此时，因为在重构前的符号执行树E300和重构后的符号 执行树E400之间产生结构上的差异，但符号执行的最终的符号执行一览逻辑 上等价，因此判定为源代码等价。在符号执行结果比较部1407中，对函数foo2 同样地进行比较，并判定为等价。从因E451的路径制约为矛盾式而认为E451 不存在，以及E351和E452的变量状态一致，且路径制约都是恒真式中也可 知道针对函数foo2的符号执行一览等价。符号执行比较部将判定的结果发送 给输出部1500。

接着，对图5的等价非等价输出S105的步骤进行说明。

输出部1500接受符号执行结果比较部1407判定为源代码等价的结果后， 作为验证结果0004输出源代码等价。图27表示输出部1500输出的验证结果 0004的例子。

在图27所示的显示例中示出了作为判定结果P300通过符号执行判定的情 况以及判定为其结果等价的情况。此外，作为用于结构比较的结构图数据，显 示实施了正规化后的重构前正规化源代码信息1005的结构图P311和重构后正 规化源代码信息1006的结构图P312。在结构图P311和P312中，通过对结构 比较的结果判断为差异的节点改变颜色，知道结构比较的结果源代码中的哪个 部分判断为不等价。此外，通过观察结构图，知道如何实施了正规化。

并且，在图27中，作为重构应用信息P320显示应用的正规化重构模式即 “示应用的正”，作为对象函数名信息显示baz，作为应用位置信息显示分别 对重构应用前后应用了重构的文件名和行编号。由此，开发者能够确认等价性 验证装置处理的重构模式以及应用位置是否与想要的结果一致。

在图27所示的显示例中，作为基于符号执行的判定特有的信息而显示针 对重构前的源代码的符号执行一览信息P330以及针对重构后的源代码的符号 执行一览信息P331。在符号执行一览信息P330和P331中，分别一行一行显 示E301、E351以及E401、E402、E451、E452中的路径制约和变量状态。由 此，开发者能够知道符号执行的结果，且能够知道使用哪些逻辑式来判定等价 性。并且，由此用户能够判断重构妥当。

图27所示的显示例是通过符号执行判定为等价的情况的显示例。在通过 符号执行判定为非等价的情况下，除了图27所示的信息外，还显示反例信息。 反例信息是通过SAT解法得到的、重构前的符号执行一览和重构后的符号执 行一览不等价的输入例。通过显示该反例信息，开发者能够知道针对哪些输入 进行了针对重构前的源代码和重构后的源代码不同的输出。由此，能够分析成 为不恰当的重构的原因。

在本例子中，产生源代码信息即结构图的构造的差异，因此为了通过 S1047的判定验证源代码等价，需要进行符号执行，但进行源代码信息的抽象 化、源代码信息的缩减，因此能够削减符号执行的计算量。

符号说明

0001重构前源代码

0002重构后源代码

0003重构模式

0004验证结果

101CPU

102主存储装置

103网络I/F

104图形I/F

105输入输出I/F

106辅助存储装置I/F

110控制部

120显示/输出装置

130输入装置

131键盘

132鼠标

141HDD(HardDiskDrive：硬盘)

142DVD驱动装置

150外部网络

160外部计算机

200源代码等价性验证程序

1000源代码等价性验证装置

1100输入部

1120重构模式登录信息

1200正规化部

1300结构比较验证处理部

1400符号执行验证处理部

1500输出部

1600存储部

1601正规化数据库

1602抽象化数据库

1603重构前/后源代码存储区域

1604重构前/后源代码信息存储区域

1605重构前/后符号执行结果存储区域

1606验证结果存储区域

1700符号执行实施判定部

1001重构前源代码信息

1002重构后源代码信息

1003重构模式信息

1004变更位置信息

1005重构前正规化源代码信息

1006重构后正规化源代码信息

1007a正规化信息

1007b变更位置确定信息

1008结构比较结果

1009符号执行开始指示

1010抽象化信息

1101源代码输入部

1102重构模式输入部

1201变更位置确定部

1202源代码正规化部

1401抽象化部

1402符号执行部

1403重构前抽象化源代码信息

1404重构后抽象化源代码信息

1405重构前符号执行结果

1406重构后符号执行结果

1407符号执行结果比较部

1601正规化数据库

1602抽象化数据库

S101重构前源代码输入步骤

S102重构后源代码输入步骤

S103重构模式输入信息输入步骤

S1041变更位置确定步骤

S1042源代码正规化步骤

S1043结构比较步骤

S1044源代码抽象化步骤

S1045符号执行步骤

S1046符号执行结果比较步骤

S1047符号执行实施判定步骤

S105等价非等价输出步骤

C001重构应用前的源代码

C002重构应用后的源代码

C003重构应用前的源代码

C004重构应用后的源代码

C005C003中的函数foo内的源代码的前半部分

C006C003中的函数foo内的源代码的后半部分

C007C004中的函数foo内的源代码的前半部分

C008C004中的函数foo内的源代码的后半部分

C009重构应用前的源代码

C010重构应用后的源代码

C011C009中的函数foo1内的源代码的前半部分

C012C009中的函数foo1内的源代码的后半部分

C013C009中的函数foo2内的源代码的前半部分

C014C009中的函数foo2内的源代码的后半部分

C015C010中的函数foo1内的源代码的前半部分

C016C010中的函数foo1内的源代码的后半部分

C017C010中的函数foo2内的源代码的前半部分

C018C010中的函数foo2内的源代码的后半部分

C019C010中的函数baz内的源代码的前半部分

C020C010中的函数baz内的源代码的后半部分

E001用于说明符号执行的源代码

E002源代码的结构图

E003表示结构图中的函数foo的entry的节点

E004表示结构图中的E003的迁移目的的节点

E005表示结构图中的E004的迁移目的的节点

E006表示结构图中的E005的分支目的的节点

E007表示结构图中的E005的分支目的的节点

E008结构图中的E006和7的迁移目的的节点

E009a结构图中的E008的分支目的的节点

E009b结构图中的E008的分支目的的节点

E010与E003对应的执行树节点

E010aE010的路径制约

E010bE010的变量状态

E011与E004对应的执行树节点

E011aE011的路径制约

E011bE011的变量状态

E012与E006对应的执行树节点

E012aE012的路径制约

E012bE012的变量状态

E013与E007对应的执行树节点

E013aE013的路径制约

E013bE013的变量状态

E014经由E006时的与E009对应的执行树节点

E015经由E006时的与E009a对应的执行树节点

E016经由E007时的与E009对应的执行树节点

E017经由E007时的与E009a对应的执行树节点

E020符号执行的执行树

E100重构应用前的源代码信息的符号执行的执行树

E101E100中的符号执行一览所包含的节点

E102E100中的符号执行一览所包含的节点

E103E100中的符号执行一览所包含的节点

E104E100中的符号执行一览所包含的节点

E200重构应用后的源代码信息的符号执行的执行树

E201E200中的符号执行一览所包含的节点

E202E200中的符号执行一览所包含的节点

E203E200中的符号执行一览所包含的节点

E204E200中的符号执行一览所包含的节点

E300针对重构应用前的函数foo1的抽象化源代码信息的符号执行的执行 树

E301E300中的符号执行一览所包含的节点

E350针对重构应用前的函数foo2的抽象化源代码信息的符号执行的执行 树

E351E350中的符号执行一览所包含的节点

E400针对重构应用后的函数foo1的抽象化源代码信息的符号执行的执行 树

E401E400中的符号执行一览所包含的节点

E402E400中的符号执行一览所包含的节点

E450针对重构应用后的函数foo2的抽象化源代码信息的符号执行的执行 树

E451E450中的符号执行一览所包含的节点

E452E450中的符号执行一览所包含的节点

M001重构应用前的源代码的结构图

M002重构应用后的源代码的结构图

M003表示通过重构追加的函数的节点

M004调用通过重构追加的函数的节点

M005重构应用前的源代码信息的已正规化的结构图

M006重构应用后的源代码信息的已正规化的结构图

M007通过正规化展开函数而得的结果的链路

M008重构应用前的源代码的结构图

M009重构应用后的源代码的结构图

M010表示M008中的函数var的节点

M011调用M008中的函数var的节点

M012表示M009中的函数var的节点

M013调用M009中的函数var的节点

M014重构应用前的源代码信息的已抽象化的结构图

M015重构应用后的源代码信息的已抽象化的结构图

M016表示M014中的被抽象化的位置的节点

M017重构应用前的源代码的结构图

M018重构应用后的源代码的结构图

M019表示通过重构追加的函数的节点

M020调用通过重构追加的函数的节点

M021调用通过重构追加的函数的节点

M022重构应用后的源代码信息的已正规化的结构图

M023调用M017中的函数bar的节点

M024调用M017中的函数qux1的节点

M025调用M022中的函数bar的节点

M026调用M022中的函数qux1的节点

P100针对C001和C002的等价性验证的验证结果显示中的判定结果

P111针对C001和C002的等价性验证的验证结果显示中的C001的已正 规化的结构图

P112针对C001和C002的等价性验证的验证结果显示中的C002的已正 规化的结构图

P120针对C001和C002的等价性验证的验证结果显示中的重构应用信息

P200针对C003和C004的等价性验证的验证结果显示中的判定结果

P211针对C003和C004的等价性验证的验证结果显示中的C003的已正 规化的结构图

P212针对C003和C004的等价性验证的验证结果显示中的C004的已正 规化的结构图

P220针对C003和C004的等价性验证的验证结果显示中的重构应用信息

P230针对C003和C004的等价性验证的验证结果显示中的C003的符号 执行一览显示

P231针对C003和C004的等价性验证的验证结果显示中的C004的符号 执行一览显示

P300针对C009和C010的等价性验证的验证结果显示中的判定结果

P311针对C009和C010的等价性验证的验证结果显示中的C009的已正 规化的结构图

P312针对C009和C010的等价性验证的验证结果显示中的C010的已正 规化的结构图

P320针对C009和C010的等价性验证的验证结果显示中的重构应用信息

P330针对C009和C010的等价性验证的验证结果显示中的C009的符号 执行一览显示

P331针对C009和C010的等价性验证的验证结果显示中的C010的符号 执行一览显示。