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

• 计算机软件 • 上一篇    下一篇

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

周晟伊1,2, 曾红卫1   

  1. 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-yi1,2, ZENG Hong-wei 1   

  1. 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).

摘要: 程序的最坏执行路径是计算程序复杂度的一项重要指标,有助于发现系统可能存在的复杂性漏洞。近年来将符号执行应用于程序复杂度分析的研究取得了不小的进展,但现有方法存在通用性较差、分析时间较长的问题。文中提出一种面向最坏路径探测的进化算法——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, Symbolic execution, Evolutionary algorithm, Path detection, Worst case execution path

中图分类号: 

  • TP311.5
[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.
[1] 李明磊, 黄晖, 陆余良, 朱凯龙. SymFuzz:一种复杂路径条件下的漏洞检测技术[J]. 计算机科学, 2021, 48(5): 25-31.
[2] 李笠, 李广鹏, 常亮, 古天龙. 约束进化算法及其应用研究综述[J]. 计算机科学, 2021, 48(4): 1-13.
[3] 赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法[J]. 计算机科学, 2021, 48(11A): 30-38.
[4] 朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌. 基于改进多目标进化算法的微服务用户请求分配策略[J]. 计算机科学, 2021, 48(10): 343-350.
[5] 张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法[J]. 计算机科学, 2020, 47(8): 284-290.
[6] 董明刚, 弓佳明, 敬超. 基于谱聚类的多目标进化社区发现算法研究[J]. 计算机科学, 2020, 47(6A): 461-466.
[7] 杨浩, 陈红梅. 基于量子进化算法的非平衡数据混合采样算法[J]. 计算机科学, 2020, 47(11): 88-94.
[8] 王瑄, 毛莺池, 谢在鹏, 黄倩. 基于差分进化的推断任务卸载策略[J]. 计算机科学, 2020, 47(10): 256-262.
[9] 谢腾宇,周晓根,胡俊,张贵军. 基于接触图残基对距离约束的蛋白质结构预测算法[J]. 计算机科学, 2020, 47(1): 59-65.
[10] 黄钊,黄曙光,邓兆琨,黄晖. 基于SEH的漏洞自动检测与测试用例生成[J]. 计算机科学, 2019, 46(7): 133-138.
[11] 李章维, 郝小虎, 张贵军. 蛋白质结构从头预测多级个体筛选进化算法[J]. 计算机科学, 2019, 46(6A): 80-84.
[12] 肖鹏, 邹德旋, 张强. 一种高效动态自适应差分进化算法[J]. 计算机科学, 2019, 46(6A): 124-132.
[13] 耿焕同, 韩伟民, 周山胜, 丁洋洋. 一种基于新型邻域更新策略的MOEA/D算法[J]. 计算机科学, 2019, 46(5): 191-197.
[14] 方皓, 吴礼发, 吴志勇. 基于符号执行的Return-to-dl-resolve利用代码自动生成方法[J]. 计算机科学, 2019, 46(2): 127-132.
[15] 金婷, 谭文安, 孙勇, 赵尧. 模糊多目标进化的社会团队形成方法[J]. 计算机科学, 2019, 46(2): 315-320.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 片兆宇,孟祥萍,张红. 多阶段车牌定位算法[J]. 计算机科学, 2009, 36(8): 296 -299 .
[2] 王学光. 基于Owen值算法的社会网络关键节点问题研究[J]. 计算机科学, 2016, 43(5): 47 -50 .
[3] 李斌, 周清雷, 斯雪明, 陈晓杰. 基于FPGA集群的Office口令恢复优化实现[J]. 计算机科学, 2020, 47(11): 32 -41 .
[4] 潘孝勤, 芦天亮, 杜彦辉, 仝鑫. 基于深度学习的语音合成与转换技术综述[J]. 计算机科学, 2021, 48(8): 200 -208 .
[5] 王俊, 王修来, 庞威, 赵鸿飞. 面向科技前瞻预测的大数据治理研究[J]. 计算机科学, 2021, 48(9): 36 -42 .
[6] 余力, 杜启翰, 岳博妍, 向君瑶, 徐冠宇, 冷友方. 基于强化学习的推荐研究综述[J]. 计算机科学, 2021, 48(10): 1 -18 .
[7] 王梓强, 胡晓光, 李晓筱, 杜卓群. 移动机器人全局路径规划算法综述[J]. 计算机科学, 2021, 48(10): 19 -29 .
[8] 高洪皓, 郑子彬, 殷昱煜, 丁勇. 区块链技术专题序言[J]. 计算机科学, 2021, 48(11): 1 -3 .
[9] 毛瀚宇, 聂铁铮, 申德荣, 于戈, 徐石成, 何光宇. 区块链即服务平台关键技术及发展综述[J]. 计算机科学, 2021, 48(11): 4 -11 .
[10] 张倩, 肖丽. 基于流线的流场可视化绘制方法综述[J]. 计算机科学, 2021, 48(12): 1 -7 .