基于Petri网可达分析的代码搜索方法

丁雪儿 钮 俊,2 张开乐 毛昕怡

1(宁波大学信息科学与工程学院 浙江宁波 315211)2(嵌入式系统与服务计算教育部重点实验室(同济大学) 上海 201804)

随着计算机技术的发展和应用的逐渐深入，出现大量复杂大规模软件系统.软件系统功能的不断增强与完备等也正导致软件复杂度急剧增加，给设计、开发和部署、运维等带来新的挑战.通过代码复用来构造软件系统可提高软件开发效率，且对已被成功使用的各种代码的复用还可提高软件质量、降低软件风险[1].随着开源运动的兴起，互联网上已聚集大量开放代码可被学习和使用[2]；同时，企业组织内部也存在大量已被成功实践的程序代码[3]，为基于复用的高效率、低成本软件开发提供了基础和条件.

为了复用已有代码，首先需对已有代码进行有效组织管理，而快速、准确地搜索到期望代码则是代码复用的关键.当前已存在大量针对代码复用的代码搜索方法，从程序接口、语义、语法等角度去匹配候选代码[4].其中基于语义的代码搜索方法主要从用户期望程序的功能或行为的角度去搜索代码，能够更为快速、准确地定位用户所需代码，近年来获得学术界、工程界重点关注[5].代码、语句的功能或行为一般体现为对输入数据进行处理并获得输出结果，故基于输入/输出匹配的代码搜索是一种典型的基于语义的代码搜索方法.该方法[6-8]需要用户用多组输入输出对的形式给出自己期望代码的模糊功能描述，通过静态分析或符号执行等技术判断候选代码能否对给定输入获得期望输出.2014年，美国爱荷华州立大学的Stolee等人[6]提出一种基于输入/输出值匹配的代码搜索方法，该方法通过符号分析技术将顺序结构程序代码的语义转换为逻辑表达式，同时将用户提供的输入/输出值对转换为语义约束，借助于可满足性模理论(satisfiability modulo theories, SMT)求解器对二者的组合进行求解，进而判断是否匹配.2016年，文献[7]对该方法进行扩展，使其能够支持对分支结构代码的分析，并通过执行路径覆盖度排序等手段解决多路径代码的匹配.该方法能在一定程度上提高搜索准确度和效率，但也存在一些局限性：1)由于计算过程的复杂性，部分程序代码的输出值难以直接给出；2)用户只能提供有限的输入/输出值，且难以给出一些特殊的边界值；3)该方法难以应对如连接数据库等不具有显式输入/输出值的代码片段.

为了弥补上述不足，一种有效做法是用户在以输入/输出对形式进行功能描述时，不必给出具体值，仅给出输入输出数据的类型即可，从而提出基于输入/输出类型匹配的代码搜索方法[9-12].该类方法一般将代码功能行为表示为数据对象之间的类型转换图，基于用户提供的输入/输出类型，通过对图进行遍历以搜索从输入类型到输出类型的子图，每个子图所对应代码序列则构成一个解.这种方法忽略具体数值，从数据类型出发，在较高语义层次搜索代码，具有较好实用性，但已有工作也存在不足.首先，在查询形式上已有方法仅能处理单个输入类型，缺乏对多个输入类型匹配问题的研究.其次，在类型分析过程中，对具有多个同类型输入参数的情形缺乏分析.

针对上述问题，本文提出一种基于Petri网可达分析的代码语义搜索方法，整个搜索过程如图1所示.首先，借助程序分析技术解析候选代码，构建候选代码数据类型转换过程的Petri网模型.其次，对于用户提供输入/输出类型对，利用改进后的Petri网可达分析算法在Petri网上搜索从输入类型到输出类型的可达路径，并返回该路径所对应代码片段.最后采用路径长度和代码复用率2个评价指标对返回结果进行重排序.注意本文以“函数”粒度源代码作为分析对象.

本文的主要贡献有2个方面：

1) 提出一种基于Petri网的代码行为建模方法，以描述代码对数据类型的加工变换过程.与已有工作中所采用的图模型不同，本文基于Petri网对代码行为过程作进一步解析，采用Petri网有向弧表示类型间的转换，有向弧权重表示转换过程中参数类型个数，能够准确表达代码语句及数据对象依赖关系.

2) 提出一种基于Petri网可达分析的代码搜索方法.采用Petri网输入/输出标识表示用户提供查询中输入/输出数据对象的类型及个数，利用Petri网可达算法匹配由输入标识到输出标识的目标代码，能够有效地解决多种形式输入/输出类型的搜索问题；同时在基础Petri网可达算法上引入诱发网分析，以提高搜索效率.

1 相关工作

目前，基于输入/输出匹配的代码搜索方法大致分为2类：基于输入/输出测试值的代码匹配方法[6-8]和基于输入/输出类型的代码匹配方法[9-12].这2种方法的相同之处在于都是通过给定的输入/输出信息样例从语义角度描述用户搜索需求；区别则在于前者基于符号执行技术挖掘数据对象值的变化过程，后者则一般使用图模型描述数据对象类型的转换过程.实践表明，基于输入/输出测试值的代码语义搜索方法能够有效提高代码搜索的准确性，而基于输入/输出类型的代码匹配方法则适用更普遍的代码搜索问题.

根据图模型的不同，将基于输入/输出类型匹配的代码搜索方法分为基于全局图模型的方法和基于局部图模型的方法.其中，前者对所有源代码的行为过程进行统一建模，后者则对单个函数进行建模.为了更直观地描述现有方法的各种图模型，以图2(a)所示的数据库连接及表数据查询代码为例进行说明，图2(b)给出代码对应的类型变化过程.文献[9]根据类库和源代码中的函数依赖关系构建全局图模型，如图3(a)所示，节点表示数据对象类型，边表示实现类型间转换的函数调用，采用最短路径搜索算法求取输入类型到输出类型的函数序列.

文献[10-12]根据特定单元源代码中的函数依赖关系构建局部图模型.这些局部图模型具有各自的特点，文献[10]的图模型区别于文献[9]的图模型，增加了专门指向函数参数的边，如图3(b)所示；文献[11]的图模型将节点分为数据节点和动作节点，其中数据节点表示数据对象类型，动作节点表示函数调用，同时使用数据依赖边和控制依赖边描述数据节点以及动作节点间的关系，如图3(c)所示；在文献[12]的图模型中，节点表示语句，边表示语句次序，如图3(d)所示.同时上述工作的搜索策略也具有差异.文献[10,12]采用标准的图搜索算法查找输入类型到输出类型的最短函数序列.文献[11]则使用Grouminer工具挖掘常用的序列使用模式，然后匹配与查询相似的使用模式.总的来看，局部图模型能够缩小问题空间，相较于全局图模型有助于提升搜索的准确性，然而此类图模型缺乏考虑函数间的数据依赖关系(参数类型个数)，导致其描述的代码行为不完整，准确率仍有提升空间.同时，已有研究无法满足多个输入类型查询，适用性较低.

此外，文献[13-17]基于数据对象的类型来进行代码搜索，是与本文较为相关的工作.文献[13]结合静态分析将源代码构建成有限状态自动机，并基于自动机，通过对象类型查找语义相关的代码片段.但是该方法的查询形式不支持输入/输出类型，因此不能匹配满足要求的程序代码或序列.文献[14]允许用户使用尽可能准确的规格描述，包括关键字、类型、方法签名、测试用例等，通过一组程序转换规则将用户要求的内容映射到候选方法或类.文献[15-16]将类型、函数、接口、成员等代码结构信息组织为有向图结构，然后通过图搜索算法查找与用户提供的自然语言查询相关的代码图.然而由于自然语言与代码存在较大差异，难以准确地定位正确解.文献[17]提出基于神经网络的深度学习方法，首先以向量形式语义关联自然语言查询与代码，然后通过计算二者的余弦距离返回与查询语义相近的代码段.但是其训练过程过于复杂和耗时，难以被推广使用.

2 程序代码的语义描述

2.1 基于类型转换的代码语义描述

程序代码为由若干程序语句所构成的语句序列，每个语句代表1个执行数据加工的操作，包括操作名以及被加工数据对象2个部分.这些操作的具体功能通常为读取或修改对应的数据对象，其具体表现形式为基本运算符的运用或函数(或方法)调用，数据对象可能为常量、变量及数组、结构体、对象等扩展数据类型所对应数据实例.本文暂不考虑与程序结构、流程控制等有关结构语句、预编译指令等不涉及显式数据加工的语句.注意，为了方便描述，本文将融合多个数据加工的复杂语句划分为原子操作后进行讨论，比如，将语句“inta=b+c；”看作“算术求和”操作及“赋值”操作的复合.

定义1.数据对象.程序语句的数据对象定义为二元组(type,value)，其中type为数据类型，value为该数据对象的值.

定义2.原子操作.程序语句中的原子操作定义为三元组(c,I,o)，其中c为操作符，I为该操作输入数据对象集合，o为输出数据对象.

定义1,2中暂未考虑能够携带多个输出值的函数调用语句，比如C#语言中声明为out类型的函数参数.一般地，一段程序代码的功能或行为由其数据加工序列体现.具体来说，代码中所有数据对象的值的变化过程对应着代码功能，比如程序分析技术就主要通过符号化手段从值变化过程来模拟代码行为[18].事实上，忽略数据对象的值的具体变化过程，单纯从被加工数据对象的个数、类型的动态变化过程也能从某种程度上去考察代码的功能行为[19-20].

本文用程序代码的操作序列所体现的数据对象的个数及其类型的动态变化过程来刻画代码行为，以应对诸如连接数据库、模拟HTTP响应等不具有显式数据对象值的程序代码.Petri网作为一种经典的并发建模语言，能够很好地刻画并发系统的资源加工变化过程.本文将程序代码中的数据对象看作资源，用Petri网来刻画程序代码对数据对象的动态加工过程，并借助Petri网对应的分析方法来解决代码匹配问题.

2.2 Petri网基本概念

Petri网为由德国计算机科学家Carl Adam Petri于20世纪60年代提出的一种描述离散事件并发系统的形式化模型，具有严格数学定义和图形表达能力.Petri网由库所、变迁、有向弧3种基本元素组成，库所和变迁由有向弧连接.采用Petri网对系统进行分析时，将库所看作系统资源，变迁看作引起资源变化的事件或者操作[21].库所能够容纳一定数量的令牌，表示所代表资源的数量.为了方便描述，先给出Petri网的形式定义及简单实例.

定义3.Petri网.Petri网为五元组PN=(P,T,F,L,W)，其中：

1)P={p1,p2,…,pm}是库所的有限集合；

2)T={t1,t2,…,tn}是变迁的有限集合；

3)F⊆(P×T)∪(T×P)是连接库所和变迁的有向弧集合；

4)L:P→是库所集合上的标记函数，用于指定库所P所对应的令牌数量；

5)W:F→+是F的权函数，表示令牌传递中的加权系数，W(f)表示W中弧f∈F所对应的分量.

在变迁的触发过程中，各个库所的令牌数量会发生变化.各个库所对应的令牌数量所构成的向量称为标识M,记初始标识为M0.在标识M中，库所p所对应的分量记作M[p].

对∀x∈P∪T，记*x{y∈P∪T|(y,x)∈F}和x*{y∈P∪T|(x,y)∈F}，称*x和x*分别为x的前集或输入集和后集或输出集.如果∀p∈*t:M[p]≥W(*t)时，称变迁t在标识M下是使能的，记作M[t.如果状态标识M下t是使能的，表示资源的数量满足触发条件，称t可以触发.触发后得到的后继标识为M′，记作M[tM′，且有:

定义4.可达标识集.如果Petri网PN=(P,T,F,L,W)中存在t∈T，使M[tM′，称M′是从M一步可达的.如果存在变迁序列t1,t2,…,tk和标识序列M1,M2,…,Mk，使得M0[t1M1[t2…Mk-1[tkMk，称Mk是从M0多步可达的.从M0可达的标识集合称为可达标识集，记作R(M0)，且满足M0∈R(M0).

定义5.Petri网的可达图.Petri网PN的可达图为二元组GR(PN)=(S,E)，其中S=R(M0)是节点集，代表Petri网PN中所有的可达标识或者状态；E={(M,t,M′)|M,M′∈R(M0),M[tM′}是有向弧集，代表不同可达状态之间的使能变迁.

例1.Petri网是一种直观的图形化建模工具，一般用实心矩形“”表示变迁，库所用圆圈“○”表示，令牌用实心圆点“•”表示.为便于理解，以图4为例给出Petri网的数学形式化定义的图形表示.图4(a)为1个简单Petri网，其初始标识为M0=[p1|→2,p2|→0,p3|→1,p4|→0]，记作向量(2,0,1,0)T，表示库所p1的令牌数量为2，库所p3的令牌数量为1，其余为0；变迁t∈T的前置集为:*t1={p1}，*t2={p2}等；∀p∈*t1:M0[p]≥W(*t1)=2，故M0[t1，记作M0[t1M1，其中M1=(0,1,1,0)T为可达标识.图4(b)为该Petri网的状态可达图.

3 基于Petri网的代码行为建模

由2.1节可知，程序语句一般为执行数据加工的操作组成，而程序代码的功能行为则表现为数据对象类型及个数的转换过程.本文将操作的数据对象看作资源，程序操作则为导致资源流动的事件.根据定义3的Petri网定义，数据对象的类型和语句可以通过库所和变迁表示，数据对象的个数可以通过有向弧权重表示.基于Petri网的代码行为过程描述为：通过Petri网中有向弧的指向表示语句中数据对象间的类型转换关系，通过有向弧的权重表示语句中不同类型数据对象的个数.本节给出一种基于Petri网的代码行为过程建模方法.首先阐明基于Petri网的代码行为建模机制，制定Petri网元素与代码元素之间的对应关系；其次基于该对应关系，利用静态分析技术对程序代码进行分析处理，完成代码到Petri网的转换.

3.1 基于Petri网的代码行为模型

单个程序语句包括有关操作以及被加工的输入数据对象集和加工后所生成的输出数据对象.比如，函数调用语句由函数名、调用该函数的主动调用数据对象(caller)、作为参数的被调用数据对象(callee)以及返回数据对象组成，其中函数名为操作符，调用和被调用数据对象均为输入数据对象，返回数据对象为输出数据对象.

定义6.程序语句为三元组(Sc,Si,O)，其中Sc代表操作符集合，Si代表输入数据对象集合，O代表输出数据对象.对于∀c∈Sc，语句输入数据对象I⊆Si对应于操作c输入数据对象，语句输出数据对象o对应于优先级最低操作c的输出数据对象.

比如，语句“inta=b+c；”包括算术、赋值2个运算符，其中算术运算符优先级高于赋值运算符，显然整个语句功能应体现为赋值运算的最终结果，故将变量a作为最终输出对象.数据对象个数及类型变化过程可简单概括为：通过语句对数据对象进行加工处理，将一定数量的特定类型的输入数据对象转换为特定类型的输出数据对象.该过程在Petri网中可描述为：通过语句变迁的输入/输出弧的指向及权重，表示语句中输入数据对象到输出对象的转换过程，其中弧由输入数据对象类型指向输出数据对象类型，输入、输出弧的权重分别表示转换过程需要消耗的输入数据对象、生成的输出数据对象个数.

对于语句s∈S，用ts表示该语句变迁，对于其输入数据对象类型i∈Si，用pi表示输入数据对象类型库所，对于其输出数据对象类型o，用po表示输出数据对象类型库所.为了方便描述，连接语句变迁与输入数据对象类型库所的输入弧表示为(pi,ts)，输入弧权重表示为W(pi,ts)，即为语句s中类型为i的输入数据对象个数.连接语句变迁与输出数据对象类型的输出弧表示为(ts,po)，输出弧权重表示为W(ts,po)，且W(ts,po)=1.

在Petri网中用输入数据对象的消耗和输出数据对象的产生来建模程序语句，容易出现代码语义描述的不一致.比如，对于需要执行多次调用的某个主动对象x，当x执行一次方法调用后，在对应Petri网的语句描述上消耗了该数据对象x，从而导致不能准确描述将来其他涉及x调用的程序语句.因此，对于被多次重复使用的数据对象，用Y表示这类数据对象的类型.针对这类数据对象y∈Y，本文引入一个特殊的复制变迁Cy.连接复制变迁和数据对象类型库所的输入弧和输出弧分别表示为(py,Cy)和(Cy,py)，其中py表示类型库所.输入弧权重表示为W(py,Cy)，且W(py,Cy)=1.输出弧权重表示为W(Cy,py)，即为该类型的数据对象在程序代码中被重复使用的次数.本文给出程序代码元素与Petri网元素之间的对应关系，如表1所示:

此外，对于没有明显输入或者输出类型的语句，为了充分保留语句中的语义信息，用void来表示这类语句的输入或者输出数据对象类型，比如new语句的输入类型、close语句的输出类型等.

3.2 程序代码的Petri网构建过程

为了匹配程序代码，首先需要将所有候选代码转换成对应Petri网形式.代码片段到Petri网的转换过程如图5所示.本文以Java语言编写的程序代码为研究对象，首先借助已有代码分析工具解析候选代码片段，从而提取各个代码元素，如语句、操作、参数个数和类型等.其次基于3.1节所述代码元素到Petri网元素之间的映射关系，将候选代码构建成对应Petri网模型，存储于图数据库中，为后期代码匹配做准备.

为了便于与Java代码的无缝衔接及效率因素考虑，本文选择轻量级的Eclipse JDT代码解析组件ASTParser.该组件可以快速将Java语言程序代码解析成基于文档对象模型(document object model,DOM)结构的抽象语法树表示，代码中的每个元素对应于抽象语法树上某个节点.采用深度优先搜索策略并借助相关API便可获取代码元素如语句、操作、参数等以及彼此之间的上下文语义关系，即特定语句、操作、参数之间的对应，其中重复对象集的确定是通过判断抽象语法树上不同操作节点是否具有相同的输入变量.在此基础上，利用3.1节描述的代码元素与Petri网元素之间的映射关系，完成候选代码到Petri网模型的转换，详细步骤见算法1.

① https://neo4j.com/

算法1.Petri网构建算法constructPN.

输入：代码片段code_Func;

输出：Petri网PN.

①PN←{P,T,F,W,L};

②P←∅,T←∅,F←∅,W←∅,L←∅;

/*初始化Petri网*/

③S←parseStatement(code_Func);

/*将代码片段中的语句序列放入到语句集S中*/

④ whileS≠∅ do

⑤ 选择s∈S;

⑥S←S-{s};

⑦T←T∪{s};/*将语句添加到Petri网的变迁集中*/

⑧T_in←parseInputType(s);

/*将语句的输入数据对象类型放入集合T_in中*/

⑨ whileT_in≠∅ do

⑩ 选择t∈T_in;/*选择集合T_in中1个输入类型*/

/*解析语句中该类型输入数据对象的个数*/

/*解析语句中该类型输出数据对象的个数*/

需要指出，行③函数parseStatement()用以分析并确定代码操作，包括程序语句以及本文针对程序代码中重复使用对象设置的复制变迁；行⑧函数parseInputType()和行函数parseOutputType()用以分析某个具体操作的输入对象和输出对象，包括语句操作的输入类型和输出类型，以及复制变迁对应的重复使用对象类型；行函数parseInputNum()和行函数parseOutputNum()用以分析某个具体输入对象和输出对象在其操作语句中的数量，包括特定语句操作的某个输入类型个数和输出类型个数，以及特定复制变迁对应重复使用对象类型输入个数和输出个数(对象重复使用次数).

程序代码所对应的Petri网描述具有明显的网式结构化特征.为了提高后期代码匹配效率，本文采用高效的Neo4j①来存储程序代码所对应的Petri网信息.Neo4j具有与Petri网类似的数据组织方式和结构，即通过节点和边来构成图，并提供类似SQL的语言Cypher以方便用户执行查询、编辑等操作.

例2.图6中为数据库连接的Java代码，该代码对应Petri网如图7所示.为了方便描述，将类型标记于对应库所，语句标记于对应变迁，其中Class，String类型库所为该代码片段的起始库所，void类型库所为终止库所，其余类型库所为类型转换过程中的过渡或中间库所.由库所指向变迁的输入弧代表类型库所是语句变迁的输入数据对象，输入弧权重代表该类型的输入数据对象个数.由变迁指向库所的输出弧代表类型库所是语句变迁的输出数据对象，输出弧权重代表该类型的输出数据对象个数.此外，每个重复对象存在其相应的克隆变迁，由重复对象库所指向克隆变迁的输入弧权重为1，由克隆变迁指向重复对象库所的输出弧权重为对象重复使用的次数.比如，在函数getConnection调用语句中，输入数据对象包括3个类型为String的参数以及1个类型为DriverManager的调用者，因此输入弧由String库所和DriverManager库所指向语句变迁，且输入弧权重分别为3和1；输出数据对象是1个类型为Connection的返回者，因此输出弧由语句变迁指向Connection库所，且输出弧权重为1.Connection对象在程序片段中被重复使用2次，因此Connection库所处存在Cc克隆变迁，且Cc输入弧权重为1，输出弧权重为2.出于空间的考虑，在图6中采用函数名来表示函数调用语句.需要指出，示例中的异常处理及迭代仅作数据流分析.

Table 1 Mapping of Program Code Elements to Petri Net Elements

Table 2 Steps of Reachability Graph Generation Algorithm

Table 3 Experimental Query Test Set

Table 4 Experimental Results

try{Class.forName(dbClass);

Connectionconnection=DriverManager.getConnection(dbUrl,username,password);

Statementstatement=connection.createStatement();

ResultSetresultSet=statement.executeQuery(query);

while(resultSet.next()) StringtableName=resultSet.getString(1);

connection.close();}

catch(ClassNotFoundExceptione){e.printStackTrace();}}

Fig. 1 Overview of code search method based on the reachability analysis of Petri Nets

Fig. 2 Code example and its type representation

Fig. 3 Example of graph models in related work

Fig. 4 Formal definition and graphical representation of Petri Net

Fig. 5 Flow chart of Petri Nets construction process

图6 “Java数据库连接”代码示例

Fig. 7 Petri Net based on the example code of Fig.6

Fig. 8 Flow chart of method for matching code based on the reachability analysis of Petri Nets

Fig. 9 Induced Net of Petri Net in Fig. 7

Fig. 10 P@5 of each question under different methods

Fig. 11 P@10 of each question under different methods

Fig. 12 Trend diagram of Petri Nets construction time and code scale

Fig. 13 Influence of cloned transition on search precision

Fig. 14 Influence of reachability graph pruning on search time

4 基于Petri网可达分析的代码匹配方法

本节引入一种基于Petri网可达分析的代码匹配方法.该方法根据用户提供的输入数据对象个数、类型信息及期望输出数据对象类型，从候选代码所对应Petri网模型中搜索存在功能行为满足将输入类型转换为输出类型的代码片段.整个过程分为3个阶段，如图8所示.首先，在各个候选代码Petri网中，根据输入、输出数据对象信息在候选Petri网中确定初始标识M0和目标标识M*；然后基于初始标识M0，对Petri网进行可达分析，生成反映标识转换的可达图；最后通过分析候选Petri网可达图中是否存在目标标识M*来判断Petri网对应的程序代码是否为用户所期待代码片段.

4.1 确定初始标识与目标标识

为了分析Petri网的可达性，首先需借助用户提供的输入、输出数据对象信息确定Petri网PN=(P,T,F,L,W)的初始标识M0和目标标识M*.

定义7.查询类型对.查询类型对为二元组T=(I,o)，其中I代表输入数据对象的数据类型集，o代表输出数据对象的数据类型.

初始标识是指T中输入类型在Petri网对应库所的等量令牌数，用来表示需要消耗的数据对象资源.

定义8.初始标识.设在查询类型对T中，类型为i∈I的输入数据对象个数为n，如果在Petri网中存在库所p∈P的标记为i，则M0[p]=n，M0[void]=1，对于其他类型p′∈P，M0[p′]=0.

考虑到T中通常不包含void输入类型，为了保证无明显输入类型程序语句的匹配过程不受影响，因此设置void类型库所的令牌数为1.目标标识是指T中输出类型在Petri网对应库所中的等量令牌数，用来表示需要生成的数据对象资源.

定义9.目标标识.对于查询类型对T中输出数据对象o，如果在Petri网中存在库所p∈P的标记为o，则M*[p]=1，M*[void]≥0，对于其他类型p′∈P，M*[p′]=0.

void库所令牌数可能大于0的原因为：部分代码包含1个或多个无明显输出类型的语句，导致生成1个或多个void令牌；部分代码仅包含明显输入类型的语句，导致初始标识void库所中的令牌没有被消耗.

4.2 Petri网可达图生成与剪枝

为了判断Petri网中是否存在由初始标识可达的目标标识，需对Petri网进行可达分析，生成所有标识间可达关系图.对于较为复杂的Petri网，为了提高分析效率，还需进行可达图修剪，即去除不影响分析结论的多余库所或变迁.

4.2.1 可达图的生成

可达性分析是研究Petri网动态行为的重要手段[22].对已确定初始、目标标识的Petri网PN，其可达图生成过程如算法2所示.

算法2.Petri网可达图生成算法reachGraph.

输入：Petri网PN、初始标识M0、输出类型p*;

输出：PN的可达图GR*.

①GR*←(N,E);

②N←{M0};E←∅;/*初始化可达图*/

③Φ←{M0};

④ whileΦ≠∅ do/*当未处理标识集不为空时*/

⑤ 选择M∈Φ;/*选择未处理标识集中的1个标识*/

⑥Φ←Φ-{M};

⑦ for所有T∈enabled(M) do/*状态标识M下所有使能的变迁T*/

⑧ (M′,p)←fire(M,T);/*计算M的后继标识M′以及变迁T的输出库所p*/

⑨ ifpathExists(p,p*,α(PN)) then

/*判断α(PN)中是否存在p到p*的路径*/

⑩ Continue；

例3.以图4为例，假设输出类型为p4，表2说明Petri网可达图生成算法的执行过程.

4.2.2 可达图的修剪

随着代码规模的扩大，状态空间的组合爆炸将使可达性分析变得非常困难，基于Petri网的可达分析的复杂度呈指数增加[23].为了应对可能的状态爆炸问题或提高分析效率，本文通过分析Petri网对应有向网中的路径对可达图GR(PN)进行剪枝，使可达图GR(PN)得到化简，同时保证化简后的可达图GR*也足以反映给定输入/输出类型转换过程.

如果在PN中没有从某类型库所到输出类型库所的路径，则不需分析从该类型库所到输出类型库所的路径是否可达，即没有必要对该类型库所分配非零数量的令牌.本文基于这个观察来修剪GR(PN)冗余节点.为了分析PN类型库所间的路径存在的问题，本文定义诱发网α(PN)的概念，α(PN)忽略变迁及有向弧权重，仅用无权有向弧表示类型库所间可达关系.

定义10.诱发网.诱发网α(PN)是由Petri网PN=(P,T,F,L,W)诱发的表示为(V,E′)的有向网，其中V=P，(P,P′)∈E′，并且存在变迁t∈T使得(P,t)∈E，(t,P′)∈E.

例4.图7中Petri网的诱发网α(PN)如图9所示.出于空间考虑，长单词用缩写表示.

命题1.令α(PN)为Petri网PN的诱发网，设α(PN)中没有从某库所p到目标库所p*的路径，设M为PN中库所p内令牌数大于0的标识，M*为库所p*内令牌数为1的目标标识，则GR(PN)中没有从M到M*的路径.

定理1.约简模型中标识可达性是一致的.

证明.设PN的化简前可达图GR(PN)=(SM,SL)，化简后可达图GR*(PN)=(SM*,SL*)，其中SM和SM*表示可达标识，SL和SL*表示连接相邻标识的有向边.GR*(PN)满足：

1) ∀M∈SM，其中M[P]>0，P={p1,p2,…,pn}，若∀p∈P，α(PN)中都存在p到p*的路径，则M∈SM*.

2) ∀M,M′∈SM，M,M′∈SM*，若∃l(M,t,M′)∈SL，则l(M,t,M′)∈SL*.

上述描述表明GR*(PN)保留GR(PN)中所有可能到达目标标识M*(M*[p*]=1)的标识M及M→M*的路径，即约简模型中标识可达性是一致的.

证毕.

4.3 基于可达图的代码匹配算法

Petri网可达图反映了Petri网在初始标识M0下可达的标识空间.因此对于生成的可达图GR*，若GR*存在目标标识M*，则Petri网上存在从M0到M*的可达路径，表明该Petri网匹配.算法3描述了Petri网匹配的整个过程：首先初始化匹配Petri网集合、搜索次数(行①②)；其次，依次获取Petri网进行分析，生成其对应的可达图(行③～⑤)；然后，判断可达图是否存在目标标识，若存在，则将对应Petri网添加到匹配Petri网集(行⑥～⑧)；最后，当所有Petri网分析完毕，则循环结束，返回匹配Petri网集合(行⑨⑩).对于返回的匹配Petri网集，其对应的代码片段存在将输入类型转换为输出类型的语句序列，这些代码片段匹配，将其纳入候选代码片段集合.

算法3.Petri网匹配算法matchPN.

输入：待搜索的Petri网库PN_database、输出类型p*、初始标识M0、目标标识M*、搜索最大次数(Petri网个数)n_max;

输出：匹配Petri网集合Ok_PNs.

①Ok_PNs←∅;

②searchCount←0;

③ while(one_PN←nextFile(PN_database) andsearchCount≤n_max) do /*获取Petri网*/

④searchCount←searchCount+1;

⑤GR*←reachGraph(one_PN,M0,p*);

/*生成Petri网可达图*/

⑦Ok_PNs←Ok_PNs∪{one_PN};

/*若存在，Petri网匹配成功，添加到匹配Petri网集*/

⑧ end if

⑨ end while

⑩ returnOk_PNs.

4.4 候选代码排序

对于候选代码片段集合，本文使用2种代码质量评价指标对代码片段进行排序，帮助程序员快速识别所需的代码片段.

基于程序员经常倾向于使用较短序列而不是较长序列来实现其任务的现象[9-10,24]，本文采用序列长度作为评价代码质量的指标，越短的序列优先级越高.本文将代码片段中功能序列的长度作为序列长度，功能序列指将输入类型转换为输出类型的方法序列.

本文还采用代码复用率作为评价代码质量的指标.在许多代码搜索工作如PARSEWeb[10],DERECS[25]中都用到了复用率对结果进行排序，其基本考虑是代码的复用率(代码片段在软件开发过程中重复使用的频率)越高，参考价值越高，但计算方式各有差异.本文考虑相似代码片段在候选代码库中出现的频率.采用已有代码克隆检测方法CCFinderSW[26]来识别候选代码库中的相似代码，并将相似代码聚成一类，计算每一类集合中代码段个数作为此类代码段的复用率.CCFinderSW的源代码可以在GitHub上找到，本文用Java语言重新实现了此算法.

5 实验以及分析

为了验证本文所提出方法的有效性，本文进行了2个实验.在第1个实验中，我们验证了本方法的有效性，即能否解决多种形式的类型转换问题，并与其他检索方法的准确率进行对比；第2个实验则讨论了本方法中涉及的技术点对搜索效率的影响.

5.1 实验建立

5.1.1 实验准备

为了确保所收集源代码的真实性和可靠性，本文选择从软件项目托管平台GitHub上收集源代码.根据托管项目的Most Stars排序，本文选择了200个用户评价较高的Java语言开源项目，将项目以函数为粒度进行切分，得到函数级代码片段189 442个.

为了构建客观的用户真实查询测试集，我们从Stack Overflow中找到带有Java标签的问答对，并选取票数为正、答案中含有代码片段的热门的20个问题，同时提取答案代码示例中的输入/输出类型作为代码搜索工具的查询输入如表3所示.需要指出，我们将数组视为特殊的数据对象，其类型为元素类型.

5.1.2 评估指标

为了评价代码搜索的准确度或效率，本文采用P@n[27-28]，MAP(mean average precision)[7,29]，MRR(mean reciprocal rank)[7]作为评价指标.P@n表示返回前n个结果的准确率，计算公式为

(1)

其中，n表示返回的前n个结果，relk表示第k个结果的相关性，如果相关，relk=1，否则relk=0.MAP表示平均准确率，该指标对出现在列表中较高位置的相关结果给予较高的权重，计算公式为

(2)

(3)

其中，AveP表示单个查询的准确率，num表示相关结果的个数，P(k)表示对于查询Qi相关结果列表中排名为k的权重，例如结果列表共有2个相关代码段位于排名1和3，则P(1)=1，P(3)=0.67.MRR表示第1个相关结果排名的倒数，计算公式为

(4)

其中，ranki表示对于查询Qi第1个相关结果的排名.

5.1.3 比较对象

为了检测搜索方法的有效性，我们与2种典型的代码检索方法进行对比.第1种为基于文本匹配的方法.该方法源于大多源代码搜索引擎，通过相似度计算模型[30]计算查询与代码片段的文本相似度.第2种为基于类型匹配的方法.该检索方法只考虑有向图中是否存在一条路径以输入/输出类型作为起点和终点节点，不考虑路径的可达问题.

5.2 实验结果及分析

5.2.1 搜索结果对比分析

针对表3中的20个查询问题，本文对比了5.1.3节中2种方法检索结果的P@5，P@10评价指标，如图10和图11所示.

从图10和图11中可以看出，相比于基于输入/输出值的方法，本方法适用于更普遍的代码搜索问题，例如较好地解决了无法用具体值描述的查询4，6，7等编程任务.同时，本方法还能够有效地解决多种形式的类型转换问题，在已有类型匹配工作已解决的单个输入类型转换的基础上，解决了多个输入类型转换.为了能够更直观地验证本方法的有效性，针对单个输入/输出类型的查询，对比了2种方法检索结果的MAP和MRR这2种评价指标，实验结果如表4所示：

从表4中可以看出，本方法的搜索准确率要优于基于文本匹配和已有类型匹配的方法.基于文本匹配的方法获得了最低的准确率，表明仅利用文本相似性解决代码匹配问题，而忽略代码的语义信息，难以获得理想的结果.本文结合静态分析技术挖掘代码的行为过程，并采用Petri网将其整合起来，添加到搜索中，使检索的准确性得到了显著提升.已有类型匹配的方法在搜索过程中只是遍历路径的存在问题，而本文在此基础上将参数类型个数作为新的约束条件，利用Petri网可达分析挖掘更全面的代码行为，从而匹配到更多相关的代码片段.

5.2.2 Petri网构造过程分析

设单个代码片段中操作数为m，每个操作的输入数据对象类型数为n，则构建代码片段Petri网的时间复杂度为O(m×n+m).本文设计实验分别从参数、语句、函数调用数目及重复使用对象集4个方面对Petri网的构造时长进行考察，如图12所示.实验结果表明，Petri网的构造时间与语句数量、函数调用数量及重复使用对象数量均成正比关系，与参数数量大约为正比关系(除参数为0的情况).原因分析为：由时间复杂度可知，构造时长取决于代码操作与输入数据对象类型，且构造时长随二者数量的增加而增加，其中代码操作涉及代码语句及本文针对重复对象集设置的相应复制变迁；从语句内部分析，运算符操作通常对同类型数据对象加工，而函数调用往往需要处理多个不同类型的输入数据对象，因此代码中函数调用数量越多，涉及输入数据对象类型越复杂，导致构造时长增加；此外，在一般情况下参数数量与语句输入数据对象存在一定关联，参数数量越多，语句输入数据对象越多，但当参数为0时，输入数据对象与参数无直接关系，比如图6代码示例.

5.2.3 技术点分析

1) 复制变迁

为了表明在Petri网构建过程中增加复制变迁的重要性，本文针对表3的查询集进行检索实验，如图13所示.从图13中可知，复制变迁对提高搜索准确率起关键作用.原因分析为：传统Petri网模型难以蕴含程序片段中数据对象的重复使用过程，导致Petri网可达分析过程中重复使用对象的资源数不够，对应操作变迁无法触发，可达图生成不完整，进而影响搜索匹配结果.

2) 可达图修剪

图14说明了分析Petri网可达时设置可达图修剪的必要性.总的来看，在标准可达图生成算法的基础上，增加可达图修剪的操作能够明显减少搜索时间.

6 总结及未来工作

为了帮助程序员更好地检索以及复用已有代码，本文提出了一种基于Petri网可达分析的代码搜索方法.该方法基于已有代码库，结合静态分析技术分析、提取代码元素，构建代码的Petri网模型；根据给定输入/输出类型，通过Petri网可达分析匹配将输入类型转换为输出类型的代码片段，并采用序列长度和复用率代码质量评价指标对结果进行排序.使用真实的查询测试集，验证了本文方法的有效性.

在未来的工作中，我们将针对搜索结果的多种情况，完善该方法.例如对于返回代码段过少的问题，采取对查询进行一定程度的放松与收缩(如父类、子类替换)；对于返回代码段过多的问题，采用测试用例(具体的输入/输出值)进一步筛选代码段.此外，我们将进一步全方面探讨代码Petri网模型的可覆盖性、安全性、结构有界性等行为性质，增强代码Petri网模型的完备性.

作者贡献声明：丁雪儿负责论文思路的提出、论文写作、论文算法和论文实验；钮俊负责论文思路的把关、论文写作和实验监督；张开乐负责数据收集和论文写作完善；毛欣怡负责结果验证和论文写作完善.