计算机科学 ›› 2017, Vol. 44 ›› Issue (11): 226-231.doi: 10.11896/j.issn.1002-137X.2017.11.034

• 第六届全国软件分析测试与演化学术会议 • 上一篇    下一篇

基于函数调用序列模式挖掘的程序缺陷检测

崔展齐,牟永敏,张志华,王伟光   

  1. 北京信息科技大学计算机学院 北京100101;计算机软件新技术国家重点实验室南京大学 南京210023,北京信息科技大学计算机学院 北京100101,北京信息科技大学计算机学院 北京100101,华为技术有限公司南京研究所 南京210008
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家重点研发计划(2016YFC0801407),计算机软件新技术国家重点实验室开放课题(KFKT2016B12),北京信息科技大学学校科研基金(1625008),计算机学院大类人才培养模式改革项目(5111623409)资助

Defects Detection Based on Mining Function Call Sequence Patterns

CUI Zhan-qi, MU Yong-min, ZHANG Zhi-hua and WANG Wei-guang   

  • Online:2018-12-01 Published:2018-12-01

摘要: 程序中通常会隐含大量编程规则,若在程序编写过程中违反此类规则,则可能引发软件缺陷。函数调用规则是其中一类常见的程序隐含规则,常见的函数调用规则挖掘工作将整个函数体内的函数调用作为一个项集来进行分析,未使用程序中函数调用先后顺序等约束信息,导致软件缺陷挖掘结果的误报率较高。通过简单的静态分析即可获取函数调用序列信息,如在缺陷挖掘过程中充分利用函数调用序列信息,将有效提高缺陷挖掘精度。基于上述思路,提出了一种基于函数调用序列模式挖掘的缺陷检测方法,该方法自动检测程序中违反函数调用序列模式的疑似缺陷,并报告可疑度较高的缺陷。基于该方法,在一组开源项目上进行的实验的结果表明,此方法能有效发现程序中由于违反函数调用序列模式而导致的缺陷,减少了缺陷误报,从而降低了人工核查疑似缺陷开销。

关键词: 函数调用序列,序列模式挖掘,缺陷检测

Abstract: Large scale programs usually imply a large number of programming rules.However,if programmers violate those rules in the process of programming,it is possible to cause software defects.The function call rule is one kind of the typical implicit rules in programs.Previous work on mining function rules handle function calls in the body of a function definition as an itemset,and the constraints implied in function call sequences are not utilized,which can lead to high false positive rates.If the function call sequence information is exploited in the process of mining rules,it will effectively improve the accuracy of mining defects.This paper proposed a defect detection approach based on mining function call sequence patterns.In the approach,the suspected defects which violate function call sequence patterns are detected automatically,and the defects with high suspicious degrees are reported.Based on this approach,experiments were carried out in a group of open source projects.The expriment results show that this approach can effectively find defects which violate function call sequence patterns in programs,and reduce false positives.As a result,the overhead of veri-fying suspicious defects are also reduced.

Key words: Function call sequence,Sequence pattern mining,Defects detection

[1] LI M,HUO X.Software Defect Mining Based on Semi-supervised Learning[J].Journal of Data Acquisition and Processing,2016,1(1):56-64.(in Chinese) 黎铭,霍轩.半监督软件缺陷挖掘研究综述[J].数据采集与处理,2016,31(1):56-64.
[2] LI Z,LU S,MYAGMAR S,et al.CP-Miner:a Tool for Finding Copy-Paste and Related Bugs in Operating System Code[C]∥Conference on Symposium on Opearting Systems Design & Implementation.2004:289-302.
[3] LI Z M,ZHOU Y Y.PR-Miner:Automatically Extracting Implicit Programming Rules and Detecting Violations in Large Software Code[C]∥European Software Engineering Conference Held Jointly with,ACM Sigsoft International Symposium on Foundations of Software Engineering.Lisbon,Portugal,2005:306-315.
[4] LU S,PARK S,HU C,et al.MUVI:Automatically Inferring Multi-Variable Access Correlations and Detecting Related Semantic and Concurrency Bugs[C]∥ACM Symposium on Ope-rating Systems Principles 2007(SOSP 2007).Stevenson,Washi-ngton,USA,2010:103-116.
[5] XIE T,PEI J.MAPO:Mining API Usages from Open SourceRepositories[C]∥International Workshop on Mining Software Repositories(MSR 2006).Shanghai,China,2006:54-57.
[6] QU W,JIA Y,JIANG M.Pattern Mining of Cloned Codes inSoftware Systems[J].Information Sciences,2014,259(3):544-554.
[7] HAN J,PEI J,KAMBER M.Data Mining:Concepts and Techniques[M].Elsevier,2011.
[8] HARRINGTON P.Machine Learning in Action[M].Green-wich,CT:Manning,2012.
[9] AGRAWAL R,SRIKANT R.Fast Algorithms for Mining Association Rules in Large Databases[C]∥International Confe-rence on Very Large Data Bases.Morgan Kaufmann Publishers Inc.,1994:487-499.
[10] HAN J.Mining Frequent Patterns without Candidate Generation[J].ACM Sigmod Record,2000,29(2):1-12.
[11] YOUNG M,PEZZE M.Software Testing and Analysis:Process,Principles and Techniques[M].John Wiley & Sons,2007.
[12] MEI H,WANG Q X,ZHANG L,et al.Software Analysis:aRoad Map[J].Chinese Journal of Computers,2009,2(9):1697-1710.(in Chinese) 梅宏,王千祥,张路,等.软件分析技术进展[J].计算机学报,2009,32(9):1697-1710.
[13] AGRAWAL R,SRIKANT R.Mining Sequential Patterns[C]∥IEEE 29th International Conference on Data Engineering.1995:3-14.
[14] SRIKANT R,AGRAWAL R.Mining Sequential Patterns:Ge-neralizations and Performance Improvements[C]∥International Conference on Extending Database Technology:Advances in Database Technology.Springer-Verlag,1996:1-17.
[15] TAN L,ZHANG X,MA X,et al.AutoISES:Automatically Inferring Security Specifications and Detecting Violations[C]∥Conference on Security Symposium.2008:379-394.
[16] TAN L,YUAN D,KRISHNA G,et al./*iComment:Bugs or Bad Comments?*/[C]∥ACM Symposium on Operating Systems Principles 2007(SOSP 2007).Stevenson,Washington,USA,2007:145-158.
[17] TAN L,ZHOU Y,PADIOLEAU Y.aComment:Mining Annotations from Comments and Code to Detect Interrupt Related Concurrency Bugs[C]∥Proceeding of International Conference on Software Engineering.2011:11-20.
[18] YU X M,LIANG B,CHEN H,et al.Path-Sensitive Multi-Varia-ble Access Correlations Mining and Related Source Code Defects Detection[J].Pattern Recognition and Artificial Intelligence,2012,5(4):691-698.(in Chinese) 于秀梅,梁彬,陈红,等.路径敏感的源码关联变量模式挖掘及缺陷检测[J].模式识别与人工智能,2012,25(4):691-698.
[19] ENGLER D,CHEN D Y,HALLEM S,et al.Bugs as Deviant Behavior:a General Approach to Inferring Errors in Systems Code[J].ACM Sigops Operating Systems Review,2010,35(5):57-72.
[20] MAFFORT C,VALENTE M T,BIGONHA M,et al.Mining Architectural Patterns Using Association Rules[C]∥International Conference on Software Engineering and Knowledge Engineering.2013:375-380.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!