一种基于程序依赖关系和符号分析的跨项目缺陷影响分析方法

本发明属于计算机技术领域，尤其是软件维护领域。本发明提供了一种面向软件生态系统的、基于程序依赖关系和符号分析的跨项目缺陷影响分析方法，用在修复跨项目缺陷过程中，为评估缺陷严重程度、设置修复优先级和设计缺陷修复方案提供辅助信息。

软件生态系统通常指“一系列具有一定程度共生关系的软件产品集合”。在软件生态系统中，不同项目通过依赖关系产生代码上的关联，其中提供功能或服务的项目被称为上游项目，使用者被称为下游项目。上下游项目是相对的，且一个项目在软件生态系统中会扮演不同的角。例如，在Python科学计算生态系统中，天文学领域核心库Astropy作为下游项目依赖于基础计算库Numpy；同时它作为上游项目为大量天文学领域附属软件提供丰富功能。由此，不同项目通过它们之间复杂多样的相互依赖关系共同发展和演化，这又给项目维护带来了新的挑战。在软件生态系统中，由于项目间依赖关系的存在，上游项目中的缺陷极有可能将其影响传播到下游项目，危害下游项目的正常运转，形成软件生态系统中独有的一类缺陷——跨项目缺陷。所谓跨项目缺陷，是指其产生的根本原因在上游项目，但其影响与修复除涉及本身项目外，涉及至少一个下游项目。

随着软件生态系统的发展，跨项目缺陷愈加不容忽视。相比于传统的项目内缺陷，跨项目缺陷的影响范围更广。由其定义可知，跨项目缺陷一旦产生，其影响不局限在单个项目内，可能破坏多个项目的正常功能，危害软件生态系统的健康与发展。且因影响多个项目，此类缺陷的修复过程更复杂。尽管跨项目缺陷最终在上游根源项目中被修复，但因其对下游项目功能产生干扰，在其修复过程中往往需要考虑下游项目的需求。然而，与独立项目开发模式不同，软件生态系统中不同项目的开发和维护是相对独立和异步的。上游修复一个跨项目缺陷并不代表消除了该缺陷对其它项目的影响，只有在上游发布了包含该缺陷修复补丁的新版本(修复版本)之后，下游才能摆脱影响。然而，如果修复版本仍然不能令下游满意，那么受影响的下游项目需要至少再等待一个发布周期才能获得新的修复版本，这无疑会扩大缺陷的影响，且耗费额外的维护工作量。因此，上游程序员在面对跨项目缺陷时往往非常谨慎，他们希望能从受影响的下游项目中获得建议。也就是说，为设计和提供令上下游均满意的修复方案，上游开发者需要了解哪些下游代码受到影响，并与其开发者进行沟通讨论。但是，手工识别受影响的下游模块(方法或类)极其耗时且容易出错。

近年来，已有部分研究人员注意到了跨项目缺陷的存在，并进行了初步的探索。例如，Decan等人在研究R语言生态系统时发现，当上游项目出现问题，下游开发者会遭遇很大的困难。Adams等人指出，整合开源软件的核心活动是同步新的上游版本；为避免上游缺陷，开发者需要在同步过程上花费大量精力。Canfora等人研究了FreeBSD和OpenBSD内核中的跨系统缺陷修复(CSBF)，并使用社会网络分析来探索贡献者的社会特征与CSBF的关系。他们着重关注了从代码修改中如何识别CSBF，并对比跨系统缺陷修复的参与者和非参与者之间的区别。Ding等人研究了在面对跨项目缺陷时，下游程序员的惯常行为，即在自己项目中提供的临时解决方案。然而，目前没有学者针对跨项目缺陷的影响进行研究或提出技术、工具。

本发明提供了一种面向软件生态系统的、基于程序依赖关系和符号分析的跨项目缺陷影响分析方法，用以识别可能受影响的下游模块(方法或类)。该方法应用于开始修复缺陷之前，它能够从生态系统大量下游模块中到所有受影响的部分，因而上游提出的修复方案更有可能满足所有的下游需求。具体来说，给定一个跨项目缺陷，已知造成缺陷的上游方法和缺陷触发条件，首先通过生态系统范围的依赖分析收集所有使用该上游方法的候选下游模块；然后对于每个模块，将模块入口处到调用点处的所有语句和缺陷触发条件共同编码成符号约束，通过约束求解判断该模块是否受影响。本发明旨在解决目前存在的缺乏针对跨项目缺陷影响分析、无法提示下游项目受影响模块等问题，进而指导跨项目缺陷的修复方案设计，提高缺陷修复补丁的质量，从而能更好地控制和管理软件生态系统的健康发展。

本跨项目影响分析方法包括下列步骤：

1)获取同一软件生态系统中不同项目、多个版本的程序源代码；

2)从每个项目基础版本的程序源代码中抽取调用关系，构建生态系统基本依赖网络；

3)从每个项目其它版本的程序源代码中获取代码变更，构建版本敏感的生态系统依赖网络；

4)对于给定的跨项目缺陷，已知其上游出错方法，挑选候选下游模块；

5)针对每个候选下游模块，进行代码预处理；

6)对每个预处理后的候选下游模块，进行符号编码；

7)对每个符号编码后的下游模块进行约束求解，如有解，则提示开发人员该模块可能受给定跨项目缺陷影响。

进一步，其中上述步骤1)的具体步骤如下：

步骤1)-1：起始状态；

步骤1)-2：根据项目名和版本号，从软件版本控制系统中获取每个项目、每个版本的源程序；

步骤1)-3：不同项目多个版本源程序采集完毕。

进一步，其中上述步骤2)的具体步骤如下：

步骤2)-1：起始状态；

步骤2)-2：对每个项目基础版本的源程序代码进行词法分析和语法分析，利用Python标准库中的ast模块生成对应的抽象语法树；

步骤2)-3：从抽象语法树中抽取四种类型的节点：方法调用节点、方法定义节点、类定义节点和import节点；

步骤2)-4：提取方法调用节点中的调用者和被调函数，并根据方法定义节点、类定义节点和import节点过滤定义在同个项目中的调用关系，即只保留跨项目调用关系；

步骤2)-5：将调用者m作为源节点，被调函数f作为目标节点，两者之间的调用关系e＝m→f作为有向边，生成生态系统基础依赖网络G(SE)＝，其中Vfrom为源节点集合，Vto为目标节点集合，E为边(调用关系)集合；

步骤2)-6：生态系统基础依赖网络构建完毕。

进一步，其中上述步骤3)的具体步骤如下：

步骤3)-1：起始状态；

步骤3)-2：对每个项目其它版本的源程序代码进行词法分析和语法分析，利用Python便准库中的ast模块生成对应的抽象语法树；

步骤3)-3：对比相邻两个版本的抽象语法树，提取方法调用节点、类定义节点和方法定义节点的变更；

步骤3)-4：为G(SE)中的每个目标节点f∈Vto维护一个元组类型的属性tf，记录其所属项目中包含方法f的最老和最新版本；对于每个调用关系e＝m→f∈E维护一个字典类型的属性c，记录从m的一个特定版本到f的版本范围的映射，用来表示该版本的m依赖于哪些版本的f；

步骤3)-5：根据节点变更信息更新tf和c的值；

步骤3)-6：版本敏感的生态系统依赖网络构建完毕；

进一步，其中上述步骤4)的具体步骤如下：

步骤4)-1：起始状态；

步骤4)-2：给定跨项目缺陷，已知其根源的上游出错方法和缺陷出发条件；

步骤4)-3：以出错上游方法为被调函数，利用版本敏感的生态系统依赖网络，收集所有调用了该出错上游方法的下游候选模块(方法或类)；

步骤4)-4：下游候选模块挑选完毕。

进一步，其中上述步骤5)的具体步骤如下：

步骤5)-1：起始状态；

步骤5)-2：对于每个下游候选模块，将其复杂语句标准化；

步骤5)-3：保留上游出错方法的接口部分，将其内部代码替换成if-else语句，其中条件为缺陷触发条件，True分支语句为return 1，False分支语句为return 0；

步骤5)-4：保留下游候选模块从模块入口处到上游方法调用点的所有语句；

步骤5)-5：下游候选模块代码预处理完毕。

进一步，其中上述步骤6)的具体步骤如下：

步骤6)-1：起始状态；

步骤6)-2：对输入变量进行初始化，即使用多种不同类型的符号变量来表示一个输入参数x的值；

步骤6)-3：逐一处理候选下游模块中的每一条语句，对于涉及x的语句s，所有代表x的符号变量都会被更新，以编码语句s在x属于不同类型时的可能行为；

步骤6)-4：剔除无法到达上游方法调用点处的路径，仅保留全部可达路径上的所有符号约束；

步骤6)-5：将缺陷触发条件编码成符号约束；

步骤6)-6：下游候选模块符号约束编码完毕。

进一步，其中上述步骤7)的具体步骤如下：

步骤7)-1：起始状态；

步骤7)-2：将步骤6)中收集的所有符号约束送入约束求解器；

步骤7)-3：对约束进行求解，如有解且变量result值为1，则被分析的下游候选模块受改给定跨项目缺陷影响；否则，不受影响；

步骤7)-4：下游候选模块影响分析完毕。

本发明基于项目间细粒度的相互依赖关系构建版本敏感的生态系统跨项目依赖网络，使得缺陷影响的分析与识别粒度深入到类或方法级别；在识别出调用给定上游出错方法的下游候选模块后，基于符号分析技术将模块入口到调用点处的语句编码成符号约束，通过约束求解判断受给定跨项目缺陷影响的下游项目模块，提高了缺陷修复补丁的质量，有利于保障软件生态系统的健康发展。

图1为本发明实施例的一种基于程序依赖关系和符号分析的跨项目缺陷影响分析方法的总体架构图。

图2为本发明实施例的一种基于程序依赖关系和符号分析的跨项目缺陷影响分析方法的流程图。

图3为本发明方法对上下游项目版本信息抽取过程的示意图。

图4为本发明方法对Python中“list comprehension”的转化处理。

图5为本发明方法对下游候选模块进行代码整合的过程。

本发明方法首先通过GIT等软件版本控制系统，收集了同一软件生态系统中不同项目、多个版本的程序源代码；接着对每个项目基础版本(最老版本)源程序进行词法分析和语法分析，生成抽象语法树，并抽取跨项目的调用关系，构建软件生态系统的基本依赖网络；然后生成每个项目其它版本的抽象语法树，并比较调用关系的改变，更新版本信息，构建版本敏感的软件生态系统依赖网络；接下来给定跨项目缺陷的根源上游出错方法，通过该网络识别使用上游出错方法的所有下游候选模块(方法或类)；然后对于每个候选模块，将其进行代码预处理，并符号化地编码从模块入口到调用点的路径，通过约束求解判断该模块是否受给定缺陷影响，并给出触发影响的下游模块输入。

为了更好地说明本发明的技术内容，特结合所附图式作如下说明。

本发明的总体架构图如图1所示，流程图如图2所示。本发明提出了一种基于程序依赖关系和符号分析的跨项目缺陷影响分析方法，包括下列7个步骤：

步骤1：获取同一软件生态系统中不同项目、多个版本的程序源代码。假设一个软件生态系统SE包含n个项目，每个项目Pi(0≤i≤n)有k个版本，即Vi0、Vi1、......、Vik。GIT等软件版本控制系统中保存了一个程序所有版本的提交，根据项目名和版本号从软件版本控制系统中获取软件生态系统中不同项目、多个本程序的源代码。

步骤2：生成软件生态系统基本依赖网络。作为生态系统SE中的一员，项目Pi(0≤i≤n)扮演两个角。一方面作为下游项目，Pi使用另一个项目Pj(0≤j≤n)提供的功能和服务，形成的跨项目调用关系构成了一个有向的跨项目依赖图G(Pi)＝，其中Vfrom为源节点集合，代表Pj中的模块(方法或类)；Vto为目标节点结合，代表Pj中的被Pi调用的方法和函数；为有向边的集合，代表调用关系。在后续叙述中，使用m∈Vfrom表示一个下游模块，使用f∈Vto表示一个上游方法。另一方面作为上游项目，Pi中的定义方法也被其它项目Pj所使用，成为G(Pj)中的目标节点。因此，为生成软件生态系统依赖网络，需要收集每个项目的方法定义和跨项目调用关系。

具体而言，对步骤1中获取每个项目Pi的基本版本(即最老版本Vi0)的源程序代码进行词法分析和语法分析，利用Python标准库中的ast模块生成抽象语法树，然后进一步分析其中的方法调用节点，提取调用者和被调函数。由于发明方法关注的是出错上游方法的跨项目影响，因此只保留跨项目的调用关系，即只保留定义在其它项目中的被调函数。为此，利用抽象语法树中的import信息、类定义和方法定义信息将定义在本项目内的被调函数排除在外。在抽取调用关系的同时，同样记录函数和方法定义实体，因为它们也可能是其它项目调用图的目标节点。在分析完每个项目的基础版本后，生态系统的基本依赖网络构建完毕。

步骤3：添加版本信息，生成版本敏感的软件生态系统依赖网络。为表示版本信息，对于每个方法f维护一个属性tf。它是一个元组，用来记录Pi中包含方法f的最老和最新版本。同时，对于每个调用关系e＝m→f∈E维护一个属性c。它是一个哈希表，记录从m的一个特定版本到f的版本范围的映射，用来表示该版本的m依赖于哪些版本的f。在基于Pi的基本版本Vi0构建基本调用图时，tf(表征在Pi哪些版本中该方法可用)被初始化为(Vi0，Vi0)；c(边e＝m→f∈E上的哈希表)的键被初始化为{Vi0}。为获得c的对应值，首先尝试从Pi的配置文件(如Python项目中的setup.py)中获取相关信息，可能会指明依赖的上游项目的最新和最老版本。然而，由于缺失配置文件或内容不全，版本信息通常不能完全由该途径获得。在这种情况下，依赖版本的上下界通常是Pj中包含方法f(具有完全相同的接口)的最新和最老版本。例如图3中示例，e.c初始化为{Vi0：(Vj1，f.tf[1])}，其中Vj1从配置文件中获得，f.tf[1]为Pj中包含f的最后一个版本。

然后，为添加版本信息，本发明方法以增量的方式比较Pi的两个相邻版本，以更新tf和c的值。具体来说，从基本版本外的最老版本Vi1到最新版本Vik，比较两个版本Vip和Vi(p-1)(1≤p≤k)的抽象语法树，记录四种更改：方法调用删除、方法调用插入、方法定义删除和方法定义插入，用以更新tf和c的值。

更新tf当Vip中一个新的方法被定义，其tf值被初始化为(Vip，Vip)；如果一个已有的方法在Vip中被删除，它的tf值保持不变；对于其它在Vip中方法，由于它们没有发生改变，其tf的第二个元素从Vi(p-1)更新为Vip。

更新c在Vip中，如果Pi的某一模块m发生更改，不再调用上游方法f，边e＝m→f的哈希表不发生改变；否则，在c中增加新的键以表示在Vip中存在该方法调用。例如在图2中，版本Vi4中模块m不再调用上游方法f，因此e.c的键中有四个元素，分别代表四个版本Vi0、Vi1、Vi2和Vi3。新增键所对应的值按上述方式由配置文件或f.tf获得。

所有版本都处理完毕后，tf和c的值都已确定。如图3中例子所示，边e上的哈希表表示：在Vi0版本的Pi中，m调用Vj1到Vj5版本Pj中的f；在Vi1版本的Pi中，m调用Vj2到Vj5版本Pj中的f；以此类推。注意，这里f：tf[1]为Vj5。在分析完生态系统的所有项目后，版本敏感的软件生态系统依赖网络即构建完成。

步骤4：对于给定的跨项目缺陷，已知其上游出错方法，挑选候选下游模块。已知被调函数，通过步骤3生成的版本敏感的软件生态系统依赖网络，即可获得调用该上游出错方法的所有下游候选模块(方法或类)。

步骤5：对每个下游候选方法进行代码预处理。预处理过程具体分为两步：代码标准化和代码整合。

a)代码标准化

在源代码文件中，一行源代码可能包含多个语句，一个长语句也可能跨越多行。为方便后续分析，首先对下游模块代码进行标准化，使得每行代码只包含一个简单操作。尽管包括C/C++和Java在内的一些编程语言已能很好地支持这类标准化处理(如通过编译器IR)，但在我们的目标语言Python中缺少此类支持。为此，本发明方法设计了针对Python的标准化方法，主要进行以下两类标准化操作。

线性化嵌套表达式 嵌套表达式将多个操作合并到一起，例如foo(a)+b。本发明方法将这类表达式分解成一组简单赋值语句，每条语句包含一个表达式。

简化复杂语法结构 Python提供丰富的语法来精确表达复杂语义。这为程序员编写程序提供了便利，但同时为程序分析带来了额外的困难。本发明方法将几类高级语法结构转换成一组基本操作。例如图4示意了Python中“list comprehension”的转化方式。该表达式“x＝[i+1for i in range(5)if i％2＝＝0]”以简洁的方法创建了一个列表，它可以转化成图右侧的一系列基本语句，包括嵌套if语句的for语句。

b)代码整合

在下游代码经标准化之后，本发明方法将上游出错方法抽象成一个简单的缺陷触发条件检查，其过程如图5所示。首先，仅保留上游出错方法upfunc()的接口部分，将其主体代码替换成一个if-else语句，从缺陷报告中获取的缺陷触发条件作为if-else语句的条件部分。然后，保留下游候选模块downfunc()中从第一行到调用上游方法之处的代码，并修改调用点处的语句，将原返回目标变量替换(或添加返回目标变量)为tmpResult。最终整合后的代码如图5(c)所示。

步骤6：对于整合后的下游候选模块代码进行符号分析。首先对输入变量进行初始化，然后将模块入口到上游出错方法调用点的路径进行符号编码，具体方法如下：

a)输入变量初始化

对于包括Python在内的动态编程语言，变量的类型信息不会显示给出。模块的一个给定输入参数可能为多种不同类型。例如，Numpy指定其方法numpy.nanpercentile()的输入参数axis可以为整型、整型列表或None。这为符号分析带来了挑战，因为符号分析必须显示指定类型。为处理此种情况，本发明使用多种不同类型的符号变量来表示一个输入参数x的值。对于涉及x的语句s，所有代表x的符号变量都会被更新，以编码语句s在x属于不同类型时的可能行为。

b)约束编码

约束编码器将对从模块入口处到调用处的可能路径进行符号化编码。编码时，它首先将每条路径转化为静态单赋值(SSA)形式，以保证每个变量都只被定义一次。下面具体介绍本发明方法如何编码几类代码结构。

赋值语句 对于常量赋值语句x＝v(v表示典型的对象保留字，包括数字、字符串和列表等)，编码器首先将其转化成SSA形式，然后编码成约束；对于简单赋值语句x＝y，编码器首先查y的最近定义。如果到，编码器先决断该定义并在将语句转化成SSA形式之后进行编码。若未到y的定义，则先用多个类型的符号变量将y初始化；对于二元操作如x＝y+z，处理方式类似。

方法调用 为保证影响分析的效率，编码过程限制在目标模块内部。除上游出错方法外，下游模块可能会调用其它方法或函数，因此我们按照符号分析中的惯例，手工为一些常用的库函数提供符号模型。对于其它未建模的外部函数，我们采用保守的方式处理。假设这些函数可以改变其所有输入参数的值，且可以返回任意类型的任意值。对于语句x＝f(p1，p2，...，pn)，它的返回目标变量x和每个输入参数pi(1≤i≤n)都重新初始化为多个不同类型的符号变量。由此，本发明方法的影响分析是保守的，即如果一个上游出错方法对某一下游模块造成影响，该方法一定会报告。该方式比缺陷检测中典型的无误报的方法更合适，因为识别出所有潜在受影响的下游模块对于上游修复跨项目缺陷是至关重要的。

分支结构 对于分支语句if conditions S1 else S2，首先决断断言，然后逐一处理S1和S2中的每一条语句。在编码过程中，路径可分为两个类别：中止和活跃。中止的路径无法到达上游出错方法的调用处，因此被排除在后续分析之外；活跃路径被符号执行到调用点。在模块内影响分析过程中，本发明方法仅关注活跃路径。

步骤7：约束求解，判断候选下游模块是否受影响。在步骤6中活跃路径上收集到的所有符号约束(包含编码后的缺陷触发条件)都将被传送到约束求解器中。如果求解器输出SAT且tmpResult的值为1，则被分析的下游候选模块被认为受给定跨项目缺陷影响。同时，触发影响的下游模块输入也可给出。

综上所述，本发明提供了一种软件生态系统的、基于程序依赖关系和符号分析的跨项目缺陷影响分析方法，解决了目前存在的缺乏针对跨项目缺陷影响分析、无法提示下游项目受影响模块等问题，进而指导跨项目缺陷的修复方案设计，提高缺陷修复补丁的质量，从而能更好地控制和管理软件生态系统的健康发展。