一种用于程序约束挖掘的过采样方法

陈灯; 张彦铎; 魏巍; 王荣存; 李晓林; 刘玮; 王世勋; 朱锐

doi:10.1631/FITEE.1601783

Your Location：

Home >

Browse articles >

一种用于程序约束挖掘的过采样方法

常规文章 | Updated：2022-05-19

- 一种用于程序约束挖掘的过采样方法
- An oversampling approach for mining program specifications
- 信息与电子工程前沿（英文） 2018年19卷第6期页码：737-754
- Affiliations：
  
  Hubei Provincial Key Laboratory of Intelligent Robot, Wuhan Institute of Technology, Wuhan 430205, China
  School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China
  School of Computer and Information Engineering, Henan Normal University, Xinxiang 453007, China
- Author bio：
  
  Deng CHEN, E-mail: dchen@wit.edu.cn
- Funds：
  
  Project supported by the Scientific Research Project of the Education Department of Hubei Province, China (No. Q20181508), the Youths Science Foundation of Wuhan Institute of Technology (No. k201622), the Surveying and Mapping Geographic Information Public Welfare Scientific Research Special Industry (No. 201412014), the Educational Commission of Hubei Province, China (No. Q20151504), the National Natural Science Foundation of China (Nos. 41501505, 61502355, 61502355, and 61502354), the China Postdoctoral Science Foundation (No. 2015M581887), the Key Program of Higher Education Institutions of Henan Province, China (No. 17A520040), and the Natural Science Foundation of Henan Province, China (No. 162300410177)
- DOI：10.1631/FITEE.1601783
  中图分类号： TP311
- 收稿：2016-12-06，
  
  修回：2018-;6-12，
  
  纸质出版：2018-06
- Accepted：
Scan QR Code
陈灯, 张彦铎, 魏巍, 等. 一种用于程序约束挖掘的过采样方法[J]. 信息与电子工程前沿（英文）, 2018,19(6):737-754.

Deng CHEN, Yan-duo ZHANG, Wei WEI, et al. An oversampling approach for mining program specifications[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(6): 737-754.
陈灯, 张彦铎, 魏巍, 等. 一种用于程序约束挖掘的过采样方法[J]. 信息与电子工程前沿（英文）, 2018,19(6):737-754. DOI： 10.1631/FITEE.1601783.

Deng CHEN, Yan-duo ZHANG, Wei WEI, et al. An oversampling approach for mining program specifications[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(6): 737-754. DOI： 10.1631/FITEE.1601783.

摘要

自动协议挖掘是获取精确而完备的API使用协议的有效方法。然而，与其它数据挖掘应用类似，自动协议挖掘方法需要足够多训练数据（即对象使用场景）作为输入。虽然通过增加程序的规模可提取更多数量的对象使用场景，但这会导致程序分析运行时开销较大。本文针对面向对象程序提出一种基于继承关系的对象使用场景过采样方法。给定一个面向对象程序

，一般情况下，执行

所能获得的对象使用场景数不超过运行时实例化的对象数。而本文方法可获得多达上述

倍的对象使用场景，其中

为程序

中一般对象使用场景的平均父类数。为了验证效果，在前期API使用协议动态挖掘原型工具ISpecMiner中集成上述方法并开展实验研究。实验采用扩展后的ISpecMiner从多个实际的程序中挖掘API使用协议。结果显示，采用本文方法获得的对象使用场景数是一般化方法的1.95倍。不仅如此，对比实验结果表明本文方法有利于挖掘更加精确而完备的API使用协议。特别值得关注的是，本文方法适用于无法实例化的类并挖掘出其API使用协议。这类API使用协议对于验证软件架构、程序说明和理解具有重要意义。虽然本文方法会增加一定的运行开销，但其仍在可接受范围内。

Abstract

Automatic protocol mining is a promising approach for inferring accurate and complete API protocols. However

just as with any data-mining technique

this approach requires sufficient training data (object usage scenarios). Existing approaches resolve the problem by analyzing more programs

which may cause significant runtime overhead. In this paper

we propose an inheritance-based oversampling approach for object usage scenarios (OUSs). Our technique is based on the inheritance relationship in object-oriented programs. Given an object-oriented program

generally

the OUSs that can be collected from a run of

are not more than the objects used during the run. With our technique

a maximum of

times more OUSs can be achieved

where

is the average number of super-classes of all general OUSs. To investigate the effect of our technique

we implement it in our previous prototype tool

ISpecMiner

and use the tool to mine protocols from several real-world programs. Experimental results show that our technique can collect 1.95 times more OUSs than general approaches. Additionally

accurate and complete API protocols are more likely to be achieved. Furthermore

our technique can mine API protocols for classes never even used in programs

which are valuable for validating software architectures

program documentation

and understanding. Although our technique will introduce some runtime overhead

it is trivial and acceptable.

关键词

Keywords

references

R Alur , , , P Černý , , , P Madhusudan , , , 等 . . Synthesis of interface specifications for Java classes . . ACM SIGPLAN Not , , 2005 . . 40 ( ( 1 ): ): 98 - - 109 . . DOI: 10.1145/1047659.1040314 http://doi.org/10.1145/1047659.1040314 . .

G Ammons , , , R Bodík , , , JR Larus . . Mining specifications . . ACM SIGPLAN Not , , 2002 . . 37 ( ( 1 ): ): 4 - - 16 . . DOI: 10.1145/565816.503275 http://doi.org/10.1145/565816.503275 . .

KB Bruce , , , P Wegner . . An algebraic model of sybtypes in object-oriented languages (draft) . . ACM SIGPLAN Not , , 1986 . . 21 ( ( 10 ): ): 163 - - 172 . . DOI: 10.1145/323648.323756 http://doi.org/10.1145/323648.323756 . .

P Caserta , , , O Zendra . . JBInsTrace: a tracer of Java and JRE classes at basic-block granularity by dynamically instrumenting bytecode . . Sci Comput Program , , 2014 . . 79 116 - - 125 . . DOI: 10.1016/j.scico.2012.02.004 http://doi.org/10.1016/j.scico.2012.02.004 . .

RY Chang , , , A Podgurski , , , J Yang . . Finding what's not there: a new approach to revealing neglected conditions in software . . Proc Int Symp on Software Testing and Analysis , , 2007 . . p.163 - - 173 . . DOI: 10.1145/1273463.1273486 http://doi.org/10.1145/1273463.1273486 . .

D Chen , , , RB Huang , , , BB Qu , , , 等 . . Improving static analysis performance using rule-filtering technique . . Proc 26 th Int Conf on Software Engineering and Knowledge Engineering , , 2014 . . p.19 - - 24 . . . .

D Chen , , , RB Huang , , , BB Qu , , , 等 . . Mining class temporal specification dynamically based on extended Markov model . . Int J Softw Eng Knowl Eng , , 2015a . . 25 ( ( 3 ): ): 573 - - 604 . . DOI: 10.1142/S0218194015500047 http://doi.org/10.1142/S0218194015500047 . .

D Chen , , , YD Zhang , , , RC Wang , , , 等 . . Extracting more object usage scenarios for API protocol mining . . Proc 27 th Int Conf on Software Engineering and Knowledge Engineering , , 2015b . . p.607 - - 612 . . DOI: 10.18293/SEKE2015-212 http://doi.org/10.18293/SEKE2015-212 . .

D Chen , , , YD Zhang , , , W Wei , , , 等 . . Efficient vulnerability detection based on an optimized rule-checking static analysis technique . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 3 ): ): 332 - - 345 . . DOI: 10.1631/FITEE.1500379 http://doi.org/10.1631/FITEE.1500379 . .

JE Cook , , , AL Wolf . . Discovering models of software processes from event-based data . . ACM Trans Softw Eng Methodol , , 1998 . . 7 ( ( 3 ): ): 215 - - 249 . . DOI: 10.1145/287000.287001 http://doi.org/10.1145/287000.287001 . .

ZY Dai , , , XG Mao , , , Y Lei , , , 等 . . Compositional mining of multiple object API protocols through state abstraction . . Sci World J , , 2004 . . Article 171 647 . .

V Dallmeier , , , C Lindig , , , A Wasylkowski , , , 等 . . Mining object behavior with ADABU . . Proc Int Workshop on Dynamic Systems Analysis , , 2006 . . p.17 - - 24 . . DOI: 10.1145/1138912.1138918 http://doi.org/10.1145/1138912.1138918 . .

V Dallmeier , , , N Knopp , , , C Mallon , , , 等 . . Automatically generating test cases for specification mining . . IEEE Trans Softw Eng , , 2012 . . 38 ( ( 2 ): ): 243 - - 257 . . DOI: 10.1109/TSE.2011.105 http://doi.org/10.1109/TSE.2011.105 . .

D Engler , , , DY Chen , , , S Hallem , , , 等 . . Bugs as deviant behavior: a general approach to inferring errors in systems code . . ACM SIGOPS Oper Syst Rev , , 2001 . . 35 ( ( 5 ): ): 57 - - 72 . . DOI: 10.1145/502059.502041 http://doi.org/10.1145/502059.502041 . .

MD Ernst , , , JH Perkins , , , PJ Guo , , , 等 . . The Daikon system for dynamic detection of likely invariants . . Sci Comput Program , , 2007 . . 69 ( ( 1-3 ): ): 35 - - 45 . . DOI: 10.1016/j.scico.2007.01.015 http://doi.org/10.1016/j.scico.2007.01.015 . .

BW Kernighan , , , DM Ritchie . . The C Programming Language (2 nd Ed.) . . Prentice Hall, Englewood Cliffs, NJ , , 1988 . . .

ZM Li , , , YY Zhou . . PR-miner: automatically extracting implicit programming rules and detecting violations in large software codes . . ACM SIGSOFT Softw Eng Not , , 2005 . . 30 ( ( 5 ): ): 306 - - 315 . . DOI: 10.1145/1095430.1081755 http://doi.org/10.1145/1095430.1081755 . .

B Liskov . . Keynote address—data abstraction and hierarchy . . ACM SIGPLAN Not , , 1988 . . 23 ( ( 5 ): ): 17 - - 34 . . DOI: 10.1145/62139.62141 http://doi.org/10.1145/62139.62141 . .

D Lorenzoli , , , L Mariani , , , M Pezzè . . Automatic generation of software behavioral models . . Proc 30 th Int Conf on Software Engineering , , 2008 . . p.501 - - 510 . . DOI: 10.1145/1368088.1368157 http://doi.org/10.1145/1368088.1368157 . .

M Pradel , , , TR Gross . . Leveraging test generation and specification mining for automated bug detection without false positives . . Proc 34 th Int Conf on Software Engineering , , 2012 . . p.288 - - 298 . . DOI: 10.1109/ICSE.2012.6227185 http://doi.org/10.1109/ICSE.2012.6227185 . .

M Pradel , , , C Jaspan , , , J Aldrich , , , 等 . . Statically checking API protocol conformance with mined multi-object specifications . . Proc 34 th Int Conf on Software Engineering , , 2012 . . p.925 - - 935 . . DOI: 10.1109/ICSE.2012.6227127 http://doi.org/10.1109/ICSE.2012.6227127 . .

MK Ramanathan , , , A Grama , , , S Jagannathan . . Static specification inference using predicate mining . . ACM SIGPLAN Not , , 2007 . . 42 ( ( 6 ): ): 123 - - 134 . . DOI: 10.1145/1273442.1250749 http://doi.org/10.1145/1273442.1250749 . .

S Shoham , , , E Yahav , , , S Fink , , , 等 . . Static specification mining using automata-based abstractions . . Proc Int Symp on Software Testing and Analysis , , 2007 . . p.174 - - 184 . . DOI: 10.1145/1273463.1273487 http://doi.org/10.1145/1273463.1273487 . .

V Skala , , , R Petruska . . A new approach to hash function construction for textual data: a comparison . . Proc 4 th World Congress on Information and Communication Technologies , , 2014 . . p.39 - - 44 . . DOI: 10.1109/WICT.2014.7077299 http://doi.org/10.1109/WICT.2014.7077299 . .

M Tatsubori , , , T Sasaki , , , S Chiba , , , 等 . . A bytecode translator for distributed execution of "legacy" Java software . . Proc 15 th European Conf on Object-Oriented Programming , , 2001 . . p.236 - - 255 . . . .

S Thummalapenta , , , T Xie . . Alattin: mining alternative patterns for defect detection . . Autom Softw Eng , , 2011 . . 18 ( ( 3-4 ): ): 293 - - 323 . . DOI: 10.1007/s10515-011-0086-z http://doi.org/10.1007/s10515-011-0086-z . .

A Wasylkowski . . Mining object usage models . . Proc 29 th Int Conf on Software Engineering , , 2007 . . p.93 - - 94 . . DOI: 10.1109/ICSECOMPANION.2007.49 http://doi.org/10.1109/ICSECOMPANION.2007.49 . .

A Wasylkowski , , , A Zeller , , , C Lindig . . Detecting object usage anomalies . . Proc 6th Joint Meeting of the European Software Engineering Conf and the ACM SIGSOFT Symp on Foundations of Software Engineering , , 2007 . . p.35 - - 44 . . DOI: 10.1145/1287624.1287632 http://doi.org/10.1145/1287624.1287632 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Numerical investigation of resolution in single emitter localization-based imaging systems