OSFPMiner: An Optimal Weighted Traversal Software Patterns Miner Based on Complex Network

HE Haitao; SHAN Chun; HE Hongdou; ZHAO Guyu; ZHANG Yangsen; TIAN Xiangmin

doi:10.1049/cje.2020.01.002

Volume 29 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2020 > 29(2): 255-264

HE Haitao, SHAN Chun, HE Hongdou, et al., “OSFPMiner: An Optimal Weighted Traversal Software Patterns Miner Based on Complex Network,” Chinese Journal of Electronics, vol. 29, no. 2, pp. 255-264, 2020, doi: 10.1049/cje.2020.01.002

Citation:

HE Haitao, SHAN Chun, HE Hongdou, et al., “OSFPMiner: An Optimal Weighted Traversal Software Patterns Miner Based on Complex Network,” Chinese Journal of Electronics, vol. 29, no. 2, pp. 255-264, 2020, doi: 10.1049/cje.2020.01.002

Citation:

PDF( 1702 KB)

OSFPMiner: An Optimal Weighted Traversal Software Patterns Miner Based on Complex Network

doi: 10.1049/cje.2020.01.002

1.
College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China;
2.
Beijing Key Laboratory of Software Security Engineering Technique, Beijing Institute of Technology, Beijing 100081, China;
3.
School of Information Management, Beijing Information Science&Technology University, Beijing 100192, China

Funds: This work is supported by the National Key R&D Program of China (No.2016YFB0800700), the National Natural Science Foundation of China (No.61772449, No.61572420, No.61772451, No.61807028, No.61802332) and the Natural Science Foundation of Hebei Province, China (No.F2019203120).

More Information

Corresponding author: SHAN Chun (corresponding author) received her Ph.D. degree in Computer Science from Beijing Institute of Technology in 2015. She is an associate professor and master tutor of school of computer science in Beijing Institute of Technology. Her research interests include Software Security, Network Security and Artificial Intelligence. (Email:sherryshan@bit.edu.cn)
Received Date: 2019-02-15
Rev Recd Date: 2019-12-27
Publish Date: 2020-03-10

Abstract

Abstract

The weighted traversal pattern is important in software system for a better understanding of the internal structure and behavior of software. To mine important patterns of software, a complex network-based Optimal Software Fault Patterns Miner is presented. By analyzing the multiple execution traces of software and the relations among functions, we establish the Weighted Software Execution Dependency Graph model ultimately. The traversal database is generated through depth-first search strategy and the extraction of software path traversals. According to the downward-closure property, a pruning strategy is adopted by Weighted Frequent Candidate Pattern Tree to cut off more unpromising patterns in advance. A set of important patterns is derived without repeated calculation. The experimental results show that the proposed approach has good performance in the number of weighted frequent candidate patterns and time efficiency.
- Complex network,
- Weighted traversal pattern,
- Upper-bound,
- Pruning

FullText(HTML)

References(25)

References

Z. Yan and C. Prehofer, “Autonomic trust management for a component-based software system”, IEEE Transactions on Dependable & Secure Computing, Vol.8, No.6, pp.810-823, 2011.

P. Yan and Z. Yan, “A survey on dynamic mobile malware detection”, Software Quality Journal, Vol.26, No.3, pp.891-919, 2017.

F. Tong and Z. Yan, “A hybrid approach of mobile malware detection in Android”, Journal of Parallel and Distributed Computing, Vol.103, pp.22-31, 2017.

C. Li and L. Liu, “Complex networks with external degree”, Chinese Journal of Electronics, Vol.23, No.3, pp.442-447, 2014.

Q. Sun, K. R. Moniz and Y. Yuyu. “Ranking modules for integrate testing based on pagerank algorithm”, Chinese Journal of Electronics, Vol.26, No.5, pp.993-998, 2017.

H. Cheng, D. Lo, Y. Zhou, et al., “Identifying bug signatures using discriminative graph mining”, Proc. of the eighteenth international symposium on Software testing and analysis, Chicago, IL, USA, pp.141-152, 2009.

X. Su, T. T. Wang, S. J. Yang, et al., “Fault localization based on weighted software behavior graph mining”, Chinese Journal of Computers, Vol.39, No.11, pp.2175-2188, 2016.

Z. Abubakar, S. P. Lee and Y. Chong, “Simultaneous localization of software faults based on complex network theory”, IEEE Access, Vol.6, pp.23990-24002, 2018.

Y. Yang, J. Ai and F. Wang, “Defect prediction based on the characteristics of multilayer structure of software network”, 2018 IEEE International Conference on Software Quality, Reliability and Security Companion, Lisbon, Portugal, pp.27-34, 2018.

H. He, J. Ren, G. Zhao, et al., “Mining of probabilistic controlling behavior model from dynamic software execution trace”, IEEE Access, vol.7, pp.79602-79616, 2019.

G. Huang, P. Zhang, B. Zhang, T. Yin and J. Ren, “The optimal community detection of software based on complex networks”, International Journal of Modern Physics C, Vol.27, No.8, pp.1650085, 2016.

A. Floratou, S. Tata and J. M. Patel, “Efficient and accurate discovery of patterns in sequence data sets”, IEEE Transactions on Knowledge and Data Engineering, Vol.23, No.8, pp.1154-1168, 2011.

K. Gouda, M. Hassaan and M. J. Zaki, “Prism: A primalencoding approach for frequent sequence mining”, Proc. of the 7th IEEE International Conference on Data Mining, Omaha, Nebraska, USA, pp.487-492, 2007.

D. Y. Chiu, Y. H. Wu and A. L. Chen, “Efficient frequent sequence mining by a dynamic strategy switching algorithm”, The VLDB Journal, Vol.18, No.1, pp.303-327, 2009.

R. Agrawal, T. Imielinski and A. Swami, “Mining association rules between sets of items in large database”, SIGMOD, Vol.22, No.2, pp.207-216, 1993.

J. Han, J. Pei and Y. Yin, “Mining frequent patterns without candidate generation”. SIGMOD, Vol.29, No.2, pp.1-12, 2000.

U. Yun and J. J. Leggett, “WSpan: Weighted sequential pattern mining in large sequence databases”, Proc. of the 3rd International IEEE Conference on Intelligent Systems, London, UK, pp.512-517, 2006.

D. L. Seong and H. C. Park, “Mining frequent patterns from weighted traversals on graph using confidence interval and pattern priority”, International Journal of Computer Science and Network Security, Vol.6, No.5A, pp.136-141, 2006.

D. L.Seong and H. C. Park, “Mining weighted frequent patterns from path traversals on weighted graph”, International Journal of Computer Science and Network Security, Vol.7, No.4, pp.140-148, 2007.

R. Geng, X. Dong and W. Xu, “Efficient algorithm for mining weighted sequential patterns based on graph traversals”, Journal of Control and Decision, Vol.24, No.5, pp.663-668, 2009.

M. Chen, J. S. Park and P. Yu, “Efficient data mining for path traversal patterns”, IEEE Transactions on Knowledge and Data Engineering, Vol.10, No.2, pp.209-221, 1998.

G. Lan, T. Hong and H. Lee, “An efficient approach for finding weighted sequential patterns from sequence databases”, Applied Intelligence, Vol.41, No.2, pp.439-452, 2014.

A. Mohan and R. Visakh, “Survey on weighted frequent pattern mining”, International Journal of Computer Trends & Technology, Vol.9, No.3, pp.102-106, 2014.

H. He, T. Yin, C. Pei, H. Wu and J. Ren, “Mining weighted frequent traversal pattern from software executing graph”, ICIC Express Letters, Vol.9, No.11, pp.2893-2900, 2015.

G. Huang, P. Zhang, Y. Li and J. Ren, “Mining the important nodes of software based on complex networks”, ICIC Express Letters, Vol.9, No.12, pp.3263-3268, 2015.

Relative Articles

Supplements(0)

Cited By

Proportional views