随着大数据时代的到来，代码资源在开源社区呈爆炸式增长，开发人员相互间分享和复制代码已成常态，并且利用应用编程接口(API)作为已有代码库或应用框架的访问接口，实现对高质量代码模块的复用．API的提供方通过API文档中的规约说明了API如何使用，比如Java编程中常用的JavaDoc文档．但是调查显示，开发人员往往在不熟悉API规约的情况下编程[1]．当API的使用违反了API规约中的使用规则，致使程序无法正确执行时，就产生了API误用缺陷[2]．以OpenSSL为例，对其API的错误使用会导致重大的安全隐患[3]．API误用缺陷检测的主要方法是分析API使用规约并检测违例．但形式化规约的构建过程须要考虑到API的所有使用条件，过程相当复杂，并且部分API规约本身自带缺陷[4]．本研究不分析API使用规约，而是提出一种基于序列模式匹配的API误用缺陷检测方法，通过分析已知缺陷中的API误用模式，再结合序列模式匹配方法，检测目标软件中尚未发现的API误用缺陷．本研究在实验中设计和实现了检测系统AD_SP并证实了方法的有效性．1 相关工作基于规约的检测方法对API规约进行描述，检查目标系统是否满足规约描述的性质，从而检测违例．Static Driver Verifier[5]是由微软开发的一款驱动代码静态验证工具，支持用户设定API使用规则，然后检测驱动代码对API的调用是否出错．文献[6]针对Ubuntu系统中使用SSL/TLS协议的相关程序，先将正确的API使用规约建模成为程序依赖图，再采用图查询的方式查找被测程序中的API调用是否符合正确的调用模式，最后检测出27个未公开的API误用缺陷．文献[7]提出使用SCTPL和SLTPL逻辑对API使用规约进行描述，然后使用模型检验方法对API误用缺陷进行检测．极少会有API的开发方严格地用逻辑语言对API使用规约进行形式化描述，因为这种描述过程复杂又繁琐[8]．为此，相关方法从API文档和API相关代码中对规约进行自动化挖掘、对使用规则中的约束进行提取，分析的数据来源主要包括客户代码、注释、文档和库代码[9]．文献[10]通过对函数、变量和数据类型等程序元素挖掘频繁项集，统计出API调用的编程规则，再指导缺陷检测．文献[11]分析大量客户端代码用有限状态自动机(FSA)描述API调用规则，正确的API调用顺序能使得FSA达到结束状态．文献[12]通过命名实体识别技术从API函数的描述文档里分析出对应的动作和资源，然后比照一个预先定义的模版挖掘规约．文献[8]利用符号执行技术挖掘API正确调用过程的语义约束，包括前置和后置条件等，再通过语义交叉验证，查找被测程序违反语义约束的API误用缺陷．文献[13]专门针对异常处理不充分问题，提出从异常处理代码中挖掘异常处理规约．文献[14]总结了基于代码自动化挖掘规约的三个步骤：对代码库进行预处理；数据挖掘方法抽取出编程规则；检测违例并报告为可能的缺陷．文献[15]提出从测试代码中挖掘API调用规约，测试代码用于验证被测API能否正确工作．上述方法关注于挖掘“显”式规约，即挖掘后能够对编程规则进行明确描述．另外，有些方法利用统计概率学判定目标API的调用序列是否存在缺陷，所挖掘的规约无法“显”式描述．文献[16]利用N-gram语言模型检测较低概率出现的API调用序列，并认为可能是API误用．文献[2]利用贝叶斯框架检测低概率出现的API调用序列．文献[17]在大量开源Java代码的基础上，构造API使用规约的训练样本，再搭建循环神经网络学习API使用规约并检测低概率出现的API调用序列．无论是基于严格的形式化方法描述“显”式规约，还是利用大数据的思想学习“隐”式规约，均存在两个问题：缺陷检测的准确度依赖于规约的准确度；当一个正确调用模式没有在被挖掘样本中出现时，不能学习出相应规则，此时基于规约的违例检测就会造成误报．不同于上述方法，本研究不挖掘规约，而是基于已经发生缺陷的实例展开工作，通过抽取API调用序列来刻画API误用模式，再基于序列模式匹配方法检测目标被测软件中的相似缺陷．基于已知缺陷和相似性分析进行缺陷检测的类似方法有Vuddy[18]和Vfdetect[19]，它们在函数粒度判别目标被测代码与缺陷代码的相似性，尚不支持面向更细粒度的API调用序列进行代码相似性分析．2 基于序列模式匹配的检测方法AD_SP的检测流程如图1所示，包括三个阶段：API误用模式分析；面向程序多路径的API调用序列抽取；序列模式匹配和报告相似缺陷．首先，针对历史已经发现的API误用缺陷，通过抽取其缺陷代码和补丁代码，分析缺陷的API误用模式；然后，针对被测软件代码，面向程序多路径进行分析，抽取API调用序列；最后，通过序列模式匹配判定被测程序代码中的API调用序列与历史已知缺陷的API误用模式是否存在关联，并报告相似缺陷．10.13245/j.hust.210218.F001图1AD_SP的检测流程示意图2.1　API误用模式分析API误用缺陷发生的根本原因是对API方法的不恰当使用，本研究关注六种类型[20]，即多余调用(superfluous call)、缺失调用(missing call)、错误调用(wrong call)、缺失前置(missing precondition)、缺失异常处理(missing error handling)和方法的返回结果未检查(ignored result)．以JCE(java cryptography extension)包为例，JCE包提供加解密功能，开发人员调用JCE包的Cipher.init方法可能出现两类缺陷：在调用该方法后未捕捉异常；在调用该方法前没有调用instance方法来实例化Cipher类对象．两类缺陷都会导致程序异常和崩溃，其缺陷代码及补丁文件的示例通过网址https://github.com/alibaba/druid/commit/e10f28 49d046265bf17360ab4aa9eb60fd3ab8de获得．缺陷模式(bug pattern)是从不断重复的或类似的软件缺陷中抽象出的规律描述．参照缺陷模式的定义[13]，针对API误用缺陷，给出API误用模式的定义．定义1 API误用模式．一个API误用模式是指对某个API方法的不恰当调用产生了错误的程序行为，并且有确定的错误原因和修复措施，同时该模式会重复出现在不同的软件产品中．API误用模式包含关键方法、错误调用序列和正确调用序列三个要素．程序必须调用关键方法才有可能出现该模式下的缺陷．错误调用序列包含了关键方法的错误使用方式，是API缺陷发生的原因．正确调用序列提供了修复该缺陷的方式．以Cipher.init方法为例，当调用该方法后未进行异常捕捉时，误用模式的三要素中关键方法是Cipher.init，错误调用序列是“Cipher.i-nit”，正确调用序列是“try Cipher.init catch”．当调用该方法之前未初始化实例对象时，误用模式的三要素中关键方法是Cipher.init，错误调用序列是“Cipher.init”，正确调用序列是“javax.crypto.Cipher.getInstance Cipher.init”．对于同一个API方法，可能存在多个误用模式，如上述的Cipher.init方法．对于不同的API方法，其误用模式之间可能具有共性，如两个不同方法在调用之后都须要进行异常捕捉．针对历史已知的API误用缺陷，根据补丁文件中缺陷修复前后的代码片段可以分析出该缺陷的误用模式和相应的三要素．六种类型的API误用缺陷中，多余调用类型缺陷的误用模式的正确调用序列是错误调用序列的子序列．设定某个多余调用类型缺陷的误用模式为P，判定目标被测代码T是否符合模式P，只须要判定T中是否存在一个API调用序列S满足两个条件：S调用了P的关键方法；P的错误调用序列是S的非连续子序列．当条件成立时，可以认为T中存在与P相似的API误用缺陷．对于其余类型的API误用缺陷，判定条件为：S调用了P的关键方法；P的错误调用序列是S的非连续子序列；P的正确调用序列不是S的非连续子序列．使用非连续子序列的原因是，对于API调用序列而言，某个API的误用会夹杂在其余无关的API方法之中，对误用模式的匹配须要排除其余无关方法的干扰．2.2　面向程序多路径分析的API调用序列抽取检测API误用缺陷须要分析程序的每条执行路径，只考虑一条程序执行路径会造成缺陷漏报，因此面向程序多路径分别抽取API调用序列．但是，这样做会遇到“路径爆炸”问题[21]，即程序的可执行路径数目随着程序中分支节点的数目成接近指数倍增长．如果在每条程序路径上抽取API调用序列进行模式匹配，那么将会造成巨大的时空开销，因此在序列抽取过程中必须进行路径剪枝．剪枝策略只能一定程度缓解路径爆炸问题，对于经过剪枝后路径数目仍旧十分庞大的程序，本研究面向单路径进行分析，即不考虑分支节点的影响，对整个程序按照逐行分析的原则，只抽取一条API调用序列．这样做虽然导致缺陷漏报，但是也是路径爆炸问题无法解决时的折中方法．使用JavaParser1抽取Java程序中每个函数的API调用序列．JavaParser能够获取Java源代码文件的抽象语法树，支持对各级粒度的Java语句块进行分析．当分析程序的多路径时，须要特殊考虑的Java控制结构包括if，while，try，for和foreach．此外，考虑到实例对象名称的多样性，须要将对象名称统一用所属类的类型表示．使用JavaParser提供的CombinedTypeSolver解析器，结合Java反射机制完成从实例对象到所属类的映射．融入剪枝策略，面向Java程序进行多路径分析和抽取API调用序列的过程见图2．其中：BlockStmt表示块语句；Statement表示语句，并且是BlockStmt的父类．JavaParser用Statement的子类型IfStmt，WhileStmt，TryStmt，ForStmt和ForEachStmt等分别表示带有if，while，try，for和foreach等控制节点的语句．当具体抽取API调用时，主要判定当前Statement中包含的表达式是否属于对象创建类型ObjectCreationExpr、方法调用类型MethodCallExpr和成员访问类型FieldAccessExpr．依据这三种类型表达式，可以从Statement中抽取出对API方法的调用，并按顺序添加到已抽取序列之中；同时，对于在方法的参数中又嵌套了方法调用的情形，按照先分析参数，再分析方法的顺序抽取API调用．10.13245/j.hust.210218.F002图2API调用序列抽取的流程示意图针对目标程序的每个函数，抽取出一个API调用序列的集合．历史已知缺陷的API误用模式将在该集合中的每一条API调用序列上进行匹配，查找符合误用模式的相似缺陷．2.3　基于改进AC算法的多模式匹配给定API误用缺陷数据库，分析出缺陷库中所有缺陷的误用模式，并设定关键方法的集合为M，错误调用序列的集合为W，正确调用序列的集合为R．此时，面向目标程序查找相似API误用缺陷的过程包括四个步骤．步骤1 抽取出目标程序的API调用序列集合S．步骤2 对于S的每一条序列s进行分析，判定s调用了M中的哪些关键方法，并按照相同下标从W和R中分别抽取出相应的序列，形成新的集合W*和R*．步骤3 对于W*中的每条错误调用序列w，判别w是否是s的非连续子序列．若是则转向步骤4；否则重复步骤3直到W*中的所有序列分析完毕．步骤4 若w对应的API误用模式P属于多余调用类型，则目标程序存在与P相似缺陷并报告．若P属于非多余调用类型，则从R*中取出w相应下标的正确调用序列r，判别r是否是s的非连续子序列．若是则转向步骤3；若不是则目标程序存在与P相似缺陷并报告．在报告相似缺陷的同时，将序列r报告为该缺陷的修复措施，并转向步骤3继续分析．上述步骤在最差的情况下须要对目标序列扫描(1+2|W*|)遍．为了降低计算复杂度，改进AC(aho-corasick)算法[22]进行多模式匹配．AC算法将多个模式预处理为确定有限状态自动机，然后对目标序列进行一次扫描便可以得出序列中是否存在所有的待查模式．但AC算法只能用于检测连续子序列，由于须要检测误用模式中的错误/正确调用序列是否是目标被测序列的非连续子序列，因此对AC算法进行改进，主要包括两点．a. 在前缀树上的状态转移从单个字符的比较变为字符串的比较．以Cipher.init未进行实例化的缺陷为例，须要判定正确调用序列“instance，Cipher.init”在目标被测序列中是否存在．由于待匹配序列本身不再是字符的序列，而是字符串的序列，因此最小的比较单元也由字符变为字符串．b. 不再使用确定有限状态自动机进行单一节点状态转移，而是在前缀树上同时进行多节点的状态转移．改进过程去除了AC算法的Failure表，保留了Success表．改进AC算法的具体流程包括如下3个步骤．步骤1 基于待匹配模式集合构造前缀树．记前缀树所有节点的集合为G，所有边的集合为E，已覆盖节点的集合A初始化为根节点，待分析边的集合B初始化为根节点引出的边的集合．步骤2 对于目标序列中的每个元素t进行分析．若B为空则转向步骤3，否则对于B的每个边e进行分析，并判别边e的比较单元与t是否匹配．若匹配则将边e指向的节点g加入A中，同时从B中去除e，并将g引出的边加入B．重复步骤2，直至目标序列扫描完毕．步骤3 A中所有属于模式匹配成功状态的节点，其对应的模式即为匹配到的模式，作为输出．通过上述过程，改进AC算法在状态转移过程中将正在分析的序列单元同时与B中的所有待分析的边进行比较，并将匹配到的边指向的节点加入已覆盖节点A中，同时将这些边从B中删除，后续不再分析．当序列扫描完毕时，若B为空，则说明前缀树的所有边均在状态转移过程中被覆盖过，即所有模式串都能在目标序列中被检测到．以字符串“uhiteeceh”为例，改进AC算法以非连续子序列查找的方式在该字符串中检测四个模式串“it/hit/ice/itch”时构造的前缀树如图3所示．10.13245/j.hust.210218.F003图3改进AC算法构造的前缀树示例以gi表示第i个树节点，具体匹配过程如下：a. 当分析字符“u”时，A={g0}，B={e1，e2}；b. 当分析字符“h”时，A={g0，g3}，B={e1，e8}；c. 当分析字符“i”时，A={g0，g3，g1，g4}，B={e3，e6，e9}；d. 当分析字符“t”时，A={g0，g3，g1，g4，g2，g5}，B={e4，e6}；e. 当分析字符“e”时，A和B均无变化；f. 当分析字符“e”时，A和B均无变化；g. 当分析字符“c”时，A={g0，g3，g1，g4，g2，g5，g6，g8}，B={e5，e7}；h. 当分析字符“e”时，A={g0，g3，g1，g4，g2，g5，g6，g8，g7}，B={e5}；i. 当分析字符“h”时，A={g0，g3，g1，g4，g2，g5，g6，g8，g7，g9}，B=∅．可以看出：前缀树中去除了传统AC算法在匹配失败时的转移路线．同AC算法一样，改进算法扫描一次字符串，即可查找出所有存在的模式，并且是以检测非连续子序列的方式．所有被覆盖的并且属于模式匹配成功状态的节点对应的模式即为目标字符串“uhiteeceh”中成功匹配到的模式．3 实验与分析针对Java语言的API误用缺陷，实现了本研究方法的原型系统AD_SP，并从开源代码仓库GitHub中检测出真实的API误用缺陷．3.1　基础缺陷数据库从MUBench[20]和文献[16]、[23]和[24]中的数据集中筛选出具有代表性的真实API误用缺陷共计61个，包含缺失调用、错误调用、缺失前置、缺失异常处理和返回结果未检查5种类型．筛选的原因是这些文献中录入的部分缺陷难以复现，并且部分缺陷缺少修复前后的代码对比，难以测试其准确性．以MUBench记录的“Cipher.init连续调用两次”和“Cipher.doFinal调用时未对byte数组指定编码格式”的两个缺陷为例，经实验测试，连续调用Cipher.init仅在程序上多余，在功能上不会造成任何异常和故障，同时当调用doFinal未制定编码时，它会采取系统默认编码．两个缺陷均难以复现．将筛选后的缺陷作为本研究方法的基础缺陷，先分析其误用模式，并构建数据库．所有缺陷的来源文献及详细的信息均可以从网址https://github.com/zyj183247166/API_Misuse_Detector_Sequence_ Pattern下载．AD_SP将应用序列模式匹配方法在GitHub代码仓库中检测出与这些基础缺陷相似的API误用缺陷．基础缺陷数据库中的每条缺陷依次存入编号、关键方法、是否参数相关、错误调用序列、正确调用序列和缺陷类型六方面信息，每个缺陷的编号唯一．对于参数相关类型缺陷，方法的参数同样参与模式匹配过程．对于存在多种修复方式的缺陷，利用特殊字符串“########”将多个修复序列连接后存储．对于Map.get缺少null检查的缺陷，由于Map支持Map〈Integer〉和Map〈String〉等多种类型的定义，为了避免尖括号中内容对模式匹配过程造成干扰，将API调用序列的尖括号中内容全部去除．数据库支持扩展．当扩充新的缺陷及误用模式时，一方面，对AD_SP进行扩展，将该缺陷相关API的jar包导入系统，以支持对相关API进行序列抽取；另一方面，按特定格式录入前述六方面信息．3.2　检测对象针对数据库中的缺陷，首先提取关键词．以关键方法为“javax.crypto.Cipher.init”的缺陷为例，用符号“．”划分出四个关键词，同时所有缺陷的关键方法的自身名称也是关键词；然后，编写爬虫，以这些关键词为检索条件，从GitHub中自动检索项目并下载至本地，同时建立GitHub项目地址与本地项目地址的映射关系．AD_SP在本地项目上检测．3.3　检测结果AD_SP一共分析GitHub项目1 142个，分析Java文件2.241 1×104个，部分项目不含Java文件，分析时间约5.36 h．时间主要耗费在解析程序的抽象语法树和面向多路径抽取API调用序列．最终在113个项目和1 359个Java文件中检测到2 416个相似缺陷(经人工确认)，其中缺失异常判断类型缺陷1 688个；同时人工确认出误报49个，对于缺失异常判断类型的缺陷，误报数目为0．与基础缺陷数据库中每个缺陷相似的缺陷数目分布如图4所示．检测的所有项目和缺陷详细信息可从https://github.com/ zyj183247166/ API_ Miuse_ Detector_ Sequence_ Pattern/blob/master/FoundAPIMisuse.json下载．10.13245/j.hust.210218.F004图4AD_SP检测到的缺陷数目分布图图4中缺失异常处理类型缺陷较多，说明程序员在调用API方法时往往忽视潜在的异常．与基础缺陷数据库中编号47的误用模式相似的缺陷数目最多(365个)，该模式为调用Random.nextInt后未处理可能的异常[23]．文献[23]分析了GitHub中包含Random.nextInt调用的1.910 2×104个代码样本，得出该方法调用后应进行异常判断的结论．与编号26的误用模式相似的缺陷数目最少(1个)，该缺陷为RandomAccessFile对象未关闭造成资源泄露．此外，在缺失调用类型缺陷中，缺陷数目最高(197个)的误用模式为InputStream对象未关闭造成资源泄露．检测结果发现：大量缺陷在项目内和项目间呈现复用关系，软件复用使得API误用模式在不同的代码文件或软件之间被广泛传播；同时，存在从同一个Java文件中检测出多种缺陷的情形．3.4　真实缺陷分析3.4.1　缺失调用File.createNewFile()用于在指定路径下创建一个新文件．调用该方法前须要判断路径的最后一级目录是否存在，如果不存在将抛出IO异常，并导致文件创建失败，其正确的调用序列是“File.exists File.mkdirs File.createNewFile”．Rocksdb是Facebook开源在GitHub中的1.71×104星优质项目，是用于持久化存储的高性能数据库引擎，被广泛用于数据库构建．从补丁2中分析出createNewFile的误用模式，并录入基础缺陷数据库．AD_SP从Rocksdb中再次检测到相似缺陷，汇报后得到开发者的确认和修复．问题代码位于NativeLibraryLoader.loadLibraryFromJarToTemp方法中，它在创建文件过程判断了变量tmpDir是否为空及目标文件是否已经存在，但是没有判断tmpDir是否指向一个不存在的目录地址．当tmpDir指向的目录无效时，temp.createNewFile将直接抛出异常，导致文件创建失败．该缺陷会导致Rocksdb无法加载库文件，影响正常使用．InputStream表示字节输入流，在使用完毕后应调用close方法释放资源，以避免内存泄露．Tink是Google研发的一个跨平台加密库，在GitHub上为1.03×104星项目．AD_SP在其StreamingTestUtil. testFileEncryptionWithStream方法中检测出未关闭输入流缺陷．问题代码在执行完decrypted.read操作后，未调用close方法释放资源．3.4.2　错误调用File.mkdir和mkdirs均用于创建文件目录．但是前者只能创建单层目录，后者则可以创建多层目录．假设“C:/a”目录不存在，调用File.mkdir(“C:/a/b”)将不会报出任何异常，也无法创建任何目录；因此，为了避免创建多层目录时失败，应使用File.mkdirs．I2P (invisible internet project)，俗称大蒜路由，是一个在匿名网络环境(暗网)下进行安全数据传输的框架，在GitHub上为1 000星项目．AD_SP在其SSLClientListenerRunner.verifyKeyStore方法中检测出相似缺陷．问题代码中，当变量ks指向的文件不存在时，程序会调用mkdir创建目录．当目录为多层时，将创建失败．3.4.3　缺失前置Iterator是一种迭代器，用于遍历序列、列表或集合中的对象．当执行next方法时，应先判断序列中是否仍存在元素．只有存在才能调用next方法取出元素进行后续分析，因此应在next方法的前置条件中调用hasNext或isEmpty方法判断序列是否已空．Jackrabbit是Java内容仓库的实现，是一种既可存储文本又可存储二进制数据的文档数据库，在GitHub中为259星项目．其LazyItemIterator.skip方法中存在相似缺陷．问题代码中，当变量skipNum超出迭代器iter对应集合的元素个数时，调用iter.next将报出异常．3.5　误报案例分析满足误用模式的目标序列可能并非缺陷．以Jackrabbit的SimpleAccessManager.hasPrivileges方法为例，该程序虽然调用next方法前没有调用hasNext或者isEmpty等方法来判断集合是否为空，但是调用了size()方法判断集合大小是否为1，程序不会在调用next方法时抛出任何异常．与之类似，I2P的MigrateJetty.migrate方法中，调用File.mkdir也不会报出任何异常．该程序在实际执行过程中，利用xmlFile.exists判断文件是否存在，若不存在，则不会执行后续mkdir过程；若存在，则说明文件目录也一定存在．因此在文件目录下再创建contexts子目录，调用mkdir方法将能正确执行．由此看出：基于序列模式匹配的检测方法具有一定的检测效果，但是仍停留在静态源码分析层面，无法分析程序的动态执行信息，加之程序动态执行时的上下文环境具有不确定性，检测方法存在一定程度的误报．4 结语提出一种基于序列模式匹配的API误用缺陷检测方法，总结已知的API误用缺陷，检测出与它们在误用模式上相似的未知缺陷．实验说明了方法的有效性，但是方法仍存在一定程度的误报．而如何利用API误用缺陷的补丁信息，通过分析修复前后代码并自动总结出误用模式，将是下一步的工作方向．