负载均衡技术在并行化符号执行中的应用

doi:10.3969/j.issn.1006-2475.2018.07.018

计算机与现代化

负载均衡技术在并行化符号执行中的应用

（南京航空航天大学计算机科学与技术学院，江苏南京211106）

收稿日期:2017-11-23 出版日期:2018-08-23 发布日期:2018-08-27
作者简介:李航(1991-)，男，河南新郑人，南京航空航天大学计算机科学与技术学院硕士研究生，CCF会员，研究方向：软件测试；臧洌(1965-)，女，江苏南京人，副教授，研究方向：机器学习；甘露(1991-)，女，安徽黄山人，硕士研究生，研究方向：机器学习，软件缺陷预测。

ApplicationofLoadBalancingTechnologyinParallelSymbolExecution

(CollegeofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing211106,China)

Received:2017-11-23 Online:2018-08-23 Published:2018-08-27

摘要/Abstract

摘要： 动态符号执行在一定的并行算法下是可以并行化的，而且研究发现并行下的路径搜索任务之间没有偏序关系。并行化下的任务调度经常采用集中式策略，但传统的集中式策略由于任务分发的问题，易产生处理单元空闲等待的情况。基于以上分析，本文先采用任务队列缓冲区解决处理单元空闲等待的问题，其次，抓住并行任务无偏序关系的特点，无需考虑任务的执行优先级，只需用负载均衡技术保证各处理单元的工作负荷大致相等即可。实验证明，集中式策略的改进和负载均衡技术的使用显著提升了并行化符号执行的效率。

关键词: 并行算法, 负载均衡, 符号执行, 集中式策略

Abstract: Dynamicsymbolexecutioncanbeparallelundercertainparallelalgorithms,andthestudyfindsthatthereisnopartialorderrelationshipbetweenthepathsearchtasksunderparallel.Paralleltaskschedulingoftenusescentralizedstrategy.However,duetotheproblemoftaskdistribution,thetraditionalcentralizedstrategyeasilycausesthecomputingunittowaitfortask.Basedontheaboveanalysis,thispaperfirstusesthebuffertostorethetasktosolvetheproblemofcomputingunitwaitingfortask.Secondly,wegraspthecharacteristicsthatparalleltasksdon’thavepartialorderrelationship,regardlessofthepriorityofthetask,butbalancetheworkloadofeachcomputingunitbyloadbalancingtechnology.Experimentsshowthatloadbalancingtechniquesandimprovedcentralizedstrategiessignificantlyimproveparallelefficiency.

Key words: parallelalgorithm, loadbalancing, symbolexecution, centralizedstrategy

中图分类号:

TP311

李航，臧洌，甘露. 负载均衡技术在并行化符号执行中的应用[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2018.07.018.

LIHang，ZANGLie，GANLu. ApplicationofLoadBalancingTechnologyinParallelSymbolExecution[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2018.07.018.

参考文献

［1］KingJC.Symbolicexecutionandprogramtesting［J］.CommunicationsoftheACM，1976,19(7):385-394.
［2］WangHaijun,LiuTing,GuanXiaohong,etal.Dependenceguidedsymbolicexecution［J］.IEEETransactionsonSoftwareEngineering,2017,43(3):252-271.
［3］LiuLingyi,VasudevanShobha.ScalinginputstimulusgenerationthroughhybridstaticanddynamicanalysisofRTL［J］.ACMTransactionsonDesignAutomationofElectronicSystems,2014,20(1):1-33.
［4］AdachiT,YamaneS,SakuraiK.DistributedCFG-basedsymbolicexecutionforassemblyprograms［C］//IEEEthe4thGlobalConferenceonConsumerElectronicsConsumerElectronics.2015:76-80.
［5］ZhangYufeng,ChenZhenbang,WangJi.S2PF:SpeculativesymbolicPathFinder［J］.ACMSigsoftSoftwareEngineeringNotes,2012,37(6):1-5.
［6］ZouQuanchen,HuangWei,AnJing,etal.Redundantconstraintseliminationforsymbolicexecution［C］//IEEEConferenceonInformationTechnology，Networking，ElectronicandAutomationControl.2016:235-240.
［7］LiXin,LiangYongjun,QianHong,etal.Symbolicexecutionofcomplexprogramdrivenbymachinelearningbasedconstraintsolving［C］//Proceedingsofthe31stIEEE/ACMInternationalConferenceonAutomatedSoftwareEngineering.2016:554-559.
［8］汤恩义,周岩,欧建生,等.面向条件判定覆盖的线性拟合制导测试生成［J］.软件学报,2016,27(3):593-610.
［9］PersonS,YangGuowei,RungtaN,etal.Directedincrementalsymbolicexecution［C］//Proceedingsofthe32ndACMSIGPLANConferenceonProgrammingLanguageDesignandImplementation.2011:504-515.
［10］ZhangYufeng,ChenZhenbang,WangJi,etal.Regularpropertyguideddynamicsymbolicexecution［C］//Proceedingsofthe37thInternationalConferenceonSoftwareEngineering.2015:643-653.
［11］GuoShengjian,KusanoM,WangChao,etal.Assertionguidedsymbolicexecutionofmultithreadedprograms［C］//Proceedingsofthe201510thJointMeetingonFoundationsofSoftwareEngineering.2015:854-865.
［12］SiddiquiJH,KhurshidS.Scalingsymbolicexecutionusingrangedanalysis［C］//ACMInternationalConferenceonObjectOrientedProgrammingSystemsLanguagesandApplications.2012:523-536.
［13］孙盼盼,董威.分布式符号执行平台［J］.计算机系统应用,2016,25(4):43-48.
［14］RakadjievE,ShimosawaT,MineH,etal.ParallelSMTsolvingandconcurrentsymbolicexecution［C］//Proceedingsofthe2015IEEETrustcom/BigDataSE/ISPA.2015:17-26.
［15］刘同.负载均衡技术在数据库集群系统中的应用与实现［D］.长沙：国防科学技术大学,2009.
［16］GodefroidP,KlarlundN,SenK.DART:Directedautomatedrandomtesting［J］.ACMSigplanNotices,2009,40(6):213-223.
［17］ZhuHong,HallPAV,MayJHR.Softwareunittestcoverageandadequacy［J］.ACMComputingSurveys,1997,29(4):366-427.

[1]	王重阳, 庄毅. 基于SDN和改进CSA算法的多作业集群的负载均衡算法[J]. 计算机与现代化, 2023, 0(11): 28-35.
[2]	袁嘉立, 刘梦赤. 面向信息网模型的动态数据划分算法[J]. 计算机与现代化, 2022, 0(10): 100-105.
[3]	倪雅婷, 杨文晖, 苗放, 黄安琪, 蒋媛. 基于Nginx的DRC集群动态负载均衡策略[J]. 计算机与现代化, 2022, 0(04): 58-64.
[4]	段鹏飞, 兰茹. 基于区块链的网络级移动目标防御系统设计[J]. 计算机与现代化, 2021, 0(08): 121-126.
[5]	李娟. 基于物联网技术的异构集群动态负载均衡算法[J]. 计算机与现代化, 2021, 0(04): 104-108.
[6]	李曈, 丁国富. 一种支持多线程程序的符号执行技术[J]. 计算机与现代化, 2020, 0(06): 60-.
[7]	彦逸,周开东,林细君,麦晓辉,肖建毅,曾朝霖. 基于因果规则的电力营销系统故障定位算法[J]. 计算机与现代化, 2020, 0(03): 13-.
[8]	戴延军1，吴志强2，刘杰1，刘朝晖1，陈智2，肖安红2. 一种安全关键软件系统符号执行优化方法[J]. 计算机与现代化, 2020, 0(01): 96-.
[9]	文婷婷,李洪赭. 面向云服务平台的弹性负载均衡算法[J]. 计算机与现代化, 2019, 0(10): 28-.
[10]	屠雪真. 一种优化的内核态文件发送方法[J]. 计算机与现代化, 2019, 0(05): 13-.
[11]	李永刚1，岳文涛1，李龙江2. 一种TD-LTE与eHRPD系统重叠覆盖下的负载均衡算法[J]. 计算机与现代化, 2017, 0(5): 5-9.
[12]	栾志坤1，牛超2. 云数据中心中负载均衡的虚拟机调度方法[J]. 计算机与现代化, 2017, 0(5): 24-36.
[13]	张楠,柴小丽,谢彬,唐鹏. Storm流处理平台中负载均衡机制的实现[J]. 计算机与现代化, 2017, 0(12): 65-70+76.
[14]	徐欢1,冯钧1,张鹏程1,唐志贤2,刘艺1,陈志飞1,张立霞1. 基于Hadoop的分布式CIF四叉树索引方法[J]. 计算机与现代化, 2016, 0(11): 12-19,24.
[15]	冉迅，袁建华，刘玉国，胡杨. 基于负载均衡的移动发票管理系统研究[J]. 计算机与现代化, 2016, 0(10): 121-.

负载均衡技术在并行化符号执行中的应用

ApplicationofLoadBalancingTechnologyinParallelSymbolExecution

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价