进化算法与符号执行结合的程序复杂度分析方法

doi:10.11896/jsjkx.210200052

计算机科学 ›› 2021, Vol. 48 ›› Issue (12): 107-116.doi: 10.11896/jsjkx.210200052

进化算法与符号执行结合的程序复杂度分析方法

周晟伊^1,2, 曾红卫¹

1 上海大学计算机工程与科学学院上海200444
2 上海市计算机软件评测重点实验室上海201112

收稿日期:2021-02-04 修回日期:2021-07-07 出版日期:2021-12-15 发布日期:2021-11-26
通讯作者: 曾红卫(zenghongwei@shu.edu.cn)
作者简介:2792186589@qq.com
基金资助:
国家重点研发计划 (2020YFB1006003)

Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution

ZHOU Sheng-yi^1,2, ZENG Hong-wei¹

1 School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China
2 Shanghai Key Laboratory of Computer Software Evaluating and Testing,Shanghai 201112,China

Received:2021-02-04 Revised:2021-07-07 Online:2021-12-15 Published:2021-11-26
About author:ZHOU Sheng-yi,born in 1997,postgraduate.Her main research interests include program analysis and so on.
ZENG Hong-wei,born in 1966,Ph.D,professor,Ph.D supervisor,is a senior member of China Computer Federation.His main research interests include software formal method and software testing.
Supported by:
National Key R & D Program of China(2020YFB1006003).

摘要/Abstract

摘要： 程序的最坏执行路径是计算程序复杂度的一项重要指标,有助于发现系统可能存在的复杂性漏洞。近年来将符号执行应用于程序复杂度分析的研究取得了不小的进展,但现有方法存在通用性较差、分析时间较长的问题。文中提出一种面向最坏路径探测的进化算法——EvoWca,其核心思想是利用程序在较小输入规模下的已知最坏路径特征指导较大输入规模下初始路径集合的构建,然后模拟进化算法,对路径进行组合、突变和选择迭代,使得在搜索范围内探测到的最坏路径逼近于最坏时间复杂度对应的路径。基于该算法实现了一个用于程序复杂度分析的原型工具EvoWca2j,使用该工具和已有技术对一组Java程序进行最坏路径探索和执行效率评估,实验结果表明,相比现有方法,EvoWca2j的通用性和探索效率都有明显提高。

关键词: 符号执行, 复杂度分析, 进化算法, 路径探测, 最坏执行路径

Abstract: The worst case execution path is an important indicator of program complexity,which helps to discover possible complexity vulnerabilities in the system.In recent years,the application of symbolic execution in program complexity analysis has made great progress,however,the existing methods have the problems of poor generality and long analysis time.EvoWca,an evolutionary algorithm for worst-case path detection,is proposed in this paper.Its core idea is to use known worst-case path characteristics of programs at smaller input sizes to guide the construction of initial path sets at larger input sizes.Evolutionary algorithm is then simulated to combine,mutate,and select routes iteratively,and the worst path detected within the search range approximates the path corresponding to the worst time complexity.Based on this algorithm,a prototype tool EvoWca2j for program complexity analysis is implemented.The tool and existing technologies are used to explore the worst path and evaluate the execution efficiency of a group of Java programs.The experimental results show that,compared with the existing methods,EvoWca2j'sgenerality and exploration efficiency are significantly improved.

Key words: Complexity analysis, Evolutionary algorithm, Path detection, Symbolic execution, Worst case execution path

中图分类号:

TP311.5

周晟伊, 曾红卫. 进化算法与符号执行结合的程序复杂度分析方法[J]. 计算机科学, 2021, 48(12): 107-116. https://doi.org/10.11896/jsjkx.210200052

ZHOU Sheng-yi, ZENG Hong-wei. Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution[J]. Computer Science, 2021, 48(12): 107-116. https://doi.org/10.11896/jsjkx.210200052

参考文献

[1]ANDALAM S,ROOP P S,GIRAULT A,et al.A Predictable Framework for Safety-Critical Embedded Systems[J].IEEE Transactions on Computers,2014,63(7):1600-1612.
[2]HANSEN J,HISSAM S A,MORENO G A.Statistical-Based WCET Estimation and Validation[C]//International Workshop on Worst-case Execution Time Analysis.DBLP,2009.
[3]FERDINAND C.Worst case execution time prediction by static program analysis[C]//18th International Parallel and Distributed Processing Symposium.IEEE,2004.
[4]LUCKOW K,KERSTEN R,PASAREANU C.Symbolic Complexity Analysis Using Context-Preserving Histories[C]//2017 IEEE International Conference on Software Testing,Verification and Validation (ICST).IEEE,2017.
[5]AQUINO A,DENARO G,SALZA P.Worst-Case Execution Time Testing via Evolutionary Symbolic Execution[C]//2018 IEEE 29th International Symposium on Software Reliability Engineering (ISSRE).IEEE,2018.
[6]NOLLER Y,KERSTEN R,PÂSÂREANU C S.Badger:com- plexity analysis with fuzzing and symbolic execution[C]//Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis.2018:322-332.
[7]ZHANG J,ZHANG C,XUAN J F,et al.Recent Progress in Program Analysis[J].Journal of Software,2019,30(1):80-109.
[8]CADAR C,SEN K.Symbolic execution for software testing: three decades later[J].Communications of the ACM,2013,56(2):82-90.
[9]BALDONI R,COPPA E,DELIA D C,et al.A Survey of Symbolic Execution Techniques[J].ACM Computing Surveys,2018,51(3):1-39.
[10]CREPINSEK M,LIU S H,MERNIK M.Exploration and ex- ploitation in evolutionary algorithms:A survey[J].ACM Computing Surveys,2013,45(3):35.
[11]JANSEN T,WEGENER I.The Analysis of Evolutionary Algorithms－A Proof that Crossover Really Can Help[J].Algorithmica,2002,34(1):47-66.
[12]STEPHENS N,GROSEN J,SALLS C,et al.Driller:Augmenting Fuzzing Through Selective Symbolic Execution[C]//Network and Distributed System Security Symposium.2016.
[13]GODEFROID P,LEVIN M,MOLNAR D.Automated whitebox fuzz testing[C]//Proceedings of the Network and Distributed System Security Symposium(NDSS 2008).San Diego,California,USA,DBLP,2008.
[14]AVGERINOS T,REBERT A,CHA S K,et al.Enhancing symbolic execution with veritesting[J].Communications of the ACM,2016,59(6):93-100.
[15]YI Q,YANG Z,GUO S,et al.Eliminating Path Redundancy via Postconditioned Symbolic Execution[J].IEEE Transactions on Software Engineering,2017,44(1):25-43.
[16]HAVELUND K,PRESSBURGER T.Model checking JAVA programs using JAVA PathFinder[J].International Journal on Software Tools for Technology Transfer,2000,2(4):366-381.
[17]ANAND S,PASAREANU C S,VISSER W.JPF-SE:A symbo- lic execution extension to Java pathfinder[C]//Tools & Algorithms for the Construction & Analysis of Systems,Internatio-nal Conference,Tacas,Held As Part of the Joint European Conferences on Theory & Practice of Software.Braga,Portugal,Proceeding,2007.
[18]MOFFETT Y,DINGEL J,BEAULIEU A.A.Verifying Protocol Conformance Using Software Model Checking for the Mo-del-Driven Development of Embedded Systems[J].IEEE Transac-tions on Software Engineering,2013,39(9):1307-1325.
[19]BAI G,YE Q,WU Y,et al.Towards Model Checking Android Applications[J].IEEE Transactions on Software Engineering,2017,44(6):595-612.
[20]BURNIM J,JUVEKAR S,SEN K.WISE:Automated test ge- neration for worst-case complexity[C]//2009 IEEE 31st International Conference on Software Engineering.IEEE,2009:463-473.

相关文章 15

[1]	刘宝宝, 杨菁菁, 陶露, 王贺应. 基于DE-LSTM模型的教育统计数据预测研究 Study on Prediction of Educational Statistical Data Based on DE-LSTM Model 计算机科学, 2022, 49(6A): 261-266. https://doi.org/10.11896/jsjkx.220300120
[2]	孙刚, 伍江江, 陈浩, 李军, 徐仕远. 一种基于切比雪夫距离的隐式偏好多目标进化算法 Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance 计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[3]	李明磊, 黄晖, 陆余良, 朱凯龙. SymFuzz:一种复杂路径条件下的漏洞检测技术 SymFuzz:Vulnerability Detection Technology Under Complex Path Conditions 计算机科学, 2021, 48(5): 25-31. https://doi.org/10.11896/jsjkx.200600128
[4]	李笠, 李广鹏, 常亮, 古天龙. 约束进化算法及其应用研究综述 Survey of Constrained Evolutionary Algorithms and Their Applications 计算机科学, 2021, 48(4): 1-13. https://doi.org/10.11896/jsjkx.200600151
[5]	赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法 Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform 计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085
[6]	朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌. 基于改进多目标进化算法的微服务用户请求分配策略 Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms 计算机科学, 2021, 48(10): 343-350. https://doi.org/10.11896/jsjkx.201100009
[7]	张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法 Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery 计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[8]	董明刚, 弓佳明, 敬超. 基于谱聚类的多目标进化社区发现算法研究 Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering 计算机科学, 2020, 47(6A): 461-466. https://doi.org/10.11896/JsJkx.191100215
[9]	杨浩, 陈红梅. 基于量子进化算法的非平衡数据混合采样算法 Mixed-sampling Method for Imbalanced Data Based on Quantum Evolutionary Algorithm 计算机科学, 2020, 47(11): 88-94. https://doi.org/10.11896/jsjkx.191000102
[10]	王瑄, 毛莺池, 谢在鹏, 黄倩. 基于差分进化的推断任务卸载策略 Inference Task Offloading Strategy Based on Differential Evolution 计算机科学, 2020, 47(10): 256-262. https://doi.org/10.11896/jsjkx.190800159
[11]	谢腾宇,周晓根,胡俊,张贵军. 基于接触图残基对距离约束的蛋白质结构预测算法 Contact Map-based Residue-pair Distances Restrained Protein Structure Prediction Algorithm 计算机科学, 2020, 47(1): 59-65. https://doi.org/10.11896/jsjkx.181202395
[12]	黄钊,黄曙光,邓兆琨,黄晖. 基于SEH的漏洞自动检测与测试用例生成 Automatic Vulnerability Detection and Test Cases Generation Method for Vulnerabilities Caused by SEH 计算机科学, 2019, 46(7): 133-138. https://doi.org/10.11896/j.issn.1002-137X.2019.07.021
[13]	肖鹏, 邹德旋, 张强. 一种高效动态自适应差分进化算法 Efficient Dynamic Self-adaptive Differential Evolution Algorithm 计算机科学, 2019, 46(6A): 124-132.
[14]	李章维, 郝小虎, 张贵军. 蛋白质结构从头预测多级个体筛选进化算法 Multi-layer Screening Based Evolution Algorithm for De Novo Protein Structure Prediction 计算机科学, 2019, 46(6A): 80-84.
[15]	耿焕同, 韩伟民, 周山胜, 丁洋洋. 一种基于新型邻域更新策略的MOEA/D算法 MOEA/D Algorithm Based on New Neighborhood Updating Strategy 计算机科学, 2019, 46(5): 191-197. https://doi.org/10.11896/j.issn.1002-137X.2019.05.029

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

进化算法与符号执行结合的程序复杂度分析方法

Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0