摘要:软件工程自从1968年提出以来,一直是提高软件开发效率、保障软件质量的有效手段.软件的发展及内涵被归纳为三个空间:平台空间、认知空间和问题空间,相应的,软件工程发展也从传统的模式化转向知识化和智能化.基于搜索的软件工程(Search Based Software Engineering, SBSE)是传统软件工程和智能计算(Intelligent Computing)交叉的新兴研究领域,从问题的解空间出发,采用智能计算领域的元启发式搜索优化算法解决软件工程相关问题,能够实现自动化和智能化.基于搜索的软件工程被2007年度IEEE国际软件工程大会(ICSE)确立为软件工程的发展方向之一,到目前为止已经在软件测试数据自动生成、程序错误自动修复等方面取得显著的研究成果,有效地促进了软件工程学科的发展.本专刊选题为“基于搜索的软件工程研究”,反映我国学者在这个领域的部分近期研究成果. 专刊公开征文历经两轮,共征得投稿28篇.此外,专刊组稿与第四届中国基于搜索的软件工程研讨会(CSBSE2015)和第十四届全国软件与应用学术会议(NASAC2015)合作,邀请CSBSE2015会议投稿中的高质量的论文作为第一轮投稿,并面向全国高校、科研院所等广泛征集第二轮投稿.上述稿件涉及软件测试、错误定位、软件产品线和云计算构件优化等诸多方面的研究内容.特约编辑先后邀请了40余位软件工程和智能计算相关领域的专家参与审稿工作,每篇投稿邀请2位专家进行评审.稿件评审历经6个月,经初审、复审、NASAC 2015会议宣读和终审各个阶段,最终有12篇论文入选本专刊.

摘要:自动程序修复帮助开发者降低人工修复bug的成本.基于测试集的修复方法旨在生成能够通过测试集的代码补丁,以使程序正常运行.回顾了基于测试集的程序修复的现有文献,按照自动修复方法和实证基础两个方面陈述了研究进展.首先,将已有的自动修复方法划分为3类,分别是基于搜索的、基于代码穷举的和基于约束求解的补丁生成方法;其次,细致地描述了程序修复的实证研究基础以及该研究领域中的争议;然后,简要介绍了程序修复的相关技术作为修复方法的补充;最后做出总结,描述了面临的机遇和挑战.

摘要:适应度函数的设计在基于搜索的测试用例生成技术中占据重要的位置,然而在某些特殊的程序中,如存在嵌套、非结构性跳转或因return,break等语句跳出循环的程序,已有的适应度函数无法评价到所有的分支.目前的方法是修改程序的源代码,以使每个分支得到评价.但修改源代码不但可能影响程序的原有结构、引入错误,而且很难实现自动化.针对这一问题,提出一种基于模式组合的粒子群优化测试用例生成方法.首先,将分支条件定义为"模式",即,一类具有相同特征且能提高适应度值的个体集合,并改变其分支函数的插桩方式,可解决分支条件不完全评价的问题;然后,设计一种新的交叉算子,寻找到所有使模式的分支函数值最小的个体,将这些个体中含有模式的部分通过交叉算子组合到一个个体上,既可防止模式在进化过程中被破坏,又可因多种模式的组合而提高个体的适应度值;最后,使用局部搜索策略对种群中的最优个体进行搜索,提高粒子群优化算法的局部搜索精度,进一步提高测试用例生成效率.为了评价该方法的有效性,基于一组基准程序和开源程序进行实验.实验结果表明:对于含有模式的程序,该测试用例生成方法与已有方法相比,在覆盖率和平均进化代数上均有明显优势.

摘要:路径覆盖是软件测试领域重要的测试方法之一.为了提高路径覆盖测试效率,在采用遗传算法进化生成路径覆盖的测试数据过程中,利用被测程序条件语句的相关性判定不可达路径,除路径中必经节点外,其他节点在不可达路径中出现的概率越大,穿越该节点的个体就具有越高的穿越度,在进化过程中应得到保护.提出了根据个体的穿越度设计适应度函数方法,从而提高测试数据的生成效率.将所提方法应用于基准程序和工业用例,并与同类方法比较可知,该方法生成路径覆盖的测试数据具有较高的效率.

摘要:测试数据的自动生成,是提高软件测试效率的重要手段.从软件测试工程实践的角度提出快速生成测试数据的完整模型,更有利于提高测试数据生成效率.为此:(1)提出关键点路径表示法,以得出待测程序的理论路径数,并快速确定已覆盖路径的邻近路径;(2)用随机生成的数据运行简化后的插装程序,得到部分测试数据;(3)将理论路径分成易覆盖路径、难覆盖路径和不可行路径;(4)根据已覆盖路径及其测试数据提供的信息,使用遗传算法生成难覆盖路径的测试数据.仿真实验结果表明了所提方法的有效性.

摘要:利用遗传算法生成复杂软件的测试数据,是软件测试领域一个全新的研究方向.传统的基于遗传算法的测试数据生成技术,需要以每个测试数据作为输入运行被测程序,以获得个体的适应值,因此,需要消耗大量的运行时间.为了降低运行程序带来的时间消耗,提出一种基于神经网络的路径覆盖测试数据进化生成方法,主要思想是:首先,利用一定样本训练神经网络,以模拟个体的适应值;在利用遗传算法生成测试数据时,先利用训练好的神经网络粗略计算个体适应值;对适应值较好的优秀个体,再通过运行程序,获得精确的适应值.最后的实验结果表明,该方法可以有效降低运行程序产生的时间消耗,从而提高测试数据生成的效率.

摘要:回归测试是迭代式软件开发的重要环节,测试数据生成是回归测试的前提.传统的回归测试方法,从已有的测试数据中选择部分测试数据,并生成一些新的测试数据,以验证程序的正确性.但是,该方法容易生成冗余的测试数据,从而降低了回归测试的效率.研究了回归测试的分支覆盖问题,通过利用已有测试数据的路径覆盖信息,并选择一定个数的路径,以覆盖所有的目标分支.首先,以若干路径形成的集合作为决策变量,以路径最少、覆盖的分支最多以及包含的未覆盖路径最少为目标,建立路径选择问题的3目标优化模型;然后,采用遗传算法求解上述模型时,设计了基于目标重要性的个体评价策略;最后,基于已有的测试数据与选择的路径之间的覆盖关系,确定需要生成的测试数据.将所提方法应用于6个基准工业程序测试中,并与其他方法比较.实验结果表明,采用该方法选择的路径,能够覆盖更多的分支,需要生成的测试数据更少,回归测试消耗的时间更短.

摘要:覆盖表生成问题是组合测试的重要研究内容之一,目前已有许多数学方法、贪心算法、搜索算法用于求解这一问题.蚁群算法作为一种能够有效求解组合优化问题的演化搜索算法,已被应用到求解覆盖表生成问题中.已有的研究工作表明:蚁群算法适于求解一般覆盖表、变力度覆盖表生成以及覆盖表排序等问题,但算法结果与其他覆盖表生成方法相比并不具有优势.为了进一步探索与挖掘蚁群算法生成覆盖表的潜力,进行了如下4个层次的改进工作:(1)算法变种集成;(2)算法参数配置优化;(3)演化对象结构调整及演化策略改进;(4)利用并行计算优化算法时间开销.实验结果表明:通过以上4个层次的改进,蚁群算法生成覆盖表的性能有了显著提升.

摘要:基于程序频谱的缺陷定位方法可以有效地辅助开发人员定位软件内部缺陷,但大部分已有自动化方法在解决多缺陷定位问题时表现不佳,部分效果尚可的方法因复杂度较高或需要开发人员较多交互而仍需进一步改善.为改善上述问题,提出一种基于遗传算法的多缺陷定位方法GAMFal,具体来说:首先基于搜索的软件工程思想对多缺陷定位问题进行建模,构建了候选缺陷分布的染色体编码方式,并基于扩展的Ochiai系数计算个体的适应度值;随后使用遗传算法在解空间中搜索具有最高适应度值的候选缺陷分布,在终止条件被满足后返回最优解种群;最后根据这个种群对程序实体进行排序.这样开发人员可以依次对程序实体进行检查并最终确定多个缺陷的具体位置.实证研究以Siemens套件中的7个程序和Linux的3个程序(gzip、grep和sed)作为评测对象,并扩展传统的定位方法评测标准EXAM至EXAMF和EXAML,通过与其他经典的缺陷定位方法(Tarantula、Improved Tarantula及Ochiai)进行对比,并通过Friedman检测和最小显著性差异测试可得,提出的GAMFal方法在整体定位效率方面优于传统方法,且需要更少的人工交互.除此之外,GAMFal的执行时间也在可接受的范围之内.

摘要:在大规模复杂系统产品线工程中,人工配置难免会导致配置的不一致,即,配置数据会违背预定义的约束(也可以称为一致性约束).对于大规模复杂系统产品线体系结构,比如信息物理系统产品线,往往存在成百上千的可变点以及约束,而且约束与可变点之间存在复杂的依赖关系,为不一致配置的修复带来很大的挑战.为了解决这个问题,针对前期提出的基于多目标搜索以及约束求解技术的自动不一致配置修复推荐框架(Zen-Fix),提出一种改进的IBEA算法(DeIBEA).DeIBEA通过将差分引入IBEA算法,搜索过程中,基于可行解和不可行解的差分变异产生后代,最终为用户推荐符合预定义约束并且对于配置效率来说最优的配置修复方案.基于一个工业案例海底油田采控系统产品线为例,通过模拟一个产品的配置过程,产生了10189个优化问题,结果表明:Zen-Fix框架结合DeIBEA算法,可以实时地为用户提供较优的不一致配置修复方案.此外,通过对这10189个问题的推荐方案进行对比,证明了DeIBEA算法无论从时间效率还是搜索性能上都优于原始的IBEA算法.

摘要:目前,对于SaaS优化放置问题的研究都是假定云环境中的虚拟机的种类和数量都是确定的,即,在限定的资源范围内进行优化.然而,在公有云环境下,SaaS提供者所需要的云资源数量是不确定的,其需要根据IaaS提供者所提供的虚拟机种类以及被部署的SaaS构件的资源需求来确定.为此,站在SaaS提供者角度,提出一种新的SaaS构件优化放置问题模型,并采用混合遗传模拟退火算法(hybrid genetic and simulated annealing algorithm,简称HGSA)对该问题进行求解.HGSA结合了遗传算法和模拟退火算法的优点,克服了遗传算法收敛速度慢和模拟退火算法容易陷入局部最优的缺点,与单独使用遗传算法和模拟退火算法相比,实验结果表明,HGSA在求解SaaS构件优化放置问题方面具有更高的求解质量.所提出的方法为SaaS服务模式的大规模应用提供了理论与方法的支撑.

摘要:形式化方法有助于从根本上提高软件系统的质量与可靠性,但其开发成本往往过于高昂.一种折衷的办法是在软件系统中选取关键性部件进行形式化开发,但目前尚无非常有效的定量选择方法.将软件系统中的形式化开发关键部件选取建模为一个0-1约束规划问题,以便使用元启发式搜索方法对其进行优化求解.另外,针对该问题专门设计了一种离散水波优化(water wave optimization,简称WWO)算法.在一个大型软件系统上的应用验证了问题模型的有效性,同时证明了WWO算法相对于其他若干典型元启发式搜索方法的优越性.

摘要:测试用例优先排序是一种基于整个测试用例集以寻找最优测试用例执行序列的软件回归测试技术.由于其能够尽早地发现错误,同时应用灵活度高、不会漏掉重要测试用例等,在实际软件测试过程中可以有效提高测试效率.多目标测试用例优化排序是寻找同时覆盖多个测试准则的用例执行序列,通常采用演化算法优化求解,但执行时间较长,严重影响了在实际软件测试中的应用.采用先进的GPU图形卡通用并行计算技术,提出了面向CPU+GPU异构计算下的多目标测试用例优先排序技术,在NSGA-Ⅱ算法中,实现了基于序列编码的适应度函数计算和交叉操作的GPU并行计算,在近6万行有效代码的工业界开源程序上实现了30倍的计算效率提升.同时,实验验证了不同并行策略的计算加速比,提出了切实可行的CPU+GPU异构计算模式,并提供了相应的原形工具.

摘要:安全攸关软件的可信性关乎生命安全和财产保全,因此,分析评价软件可信性是否符合用户的预期(即软件可信评估)至关重要.软件可信评估从主观和客观两个方面度量软件的质量,对软件生产和应用有着重要的意义.综述了可信评估管理中涉及到的标准、模型和工具,而非关注软件度量本身.首先分析对比了软件可信性、可信评估的定义,并在研究了与可信性密切相关的软件质量的联系与区别之后,从相关国际标准、评估涉及的模型(包括质量属性模型、证据模型、分级规范等)以及软件工具支持等方面综述了软件可信评估研究工作.并且区分了这些方面中领域相关、领域无关的不同之处.目前软件可信评估已取得了一定的理论成果,并开发了若干工具辅助进行可信评估,但仍需在通用性、可伸缩性等方面有所加强.

摘要:软件定义网络(software defined networking,简称SDN)初步实现了网络控制面与数据面分离的思想,然而在提供高度开放性和可编程性的同时,网络自身也面临着诸多安全问题,从而限制了SDN在很多场景下的大规模部署和应用.首先对SDN的架构和安全模型进行分析;其次,从"SDN特有/非特有的典型安全问题"和"SDN各层/接口面临的安全威胁"两方面,对SDN中存在的典型安全威胁和安全问题进行分析和归纳;随后从6个方面对现有SDN安全问题的主要解决思路及其最新研究进展分别进行探讨,包括SDN安全控制器的开发、控制器可组合安全模块库的开发和部署、控制器DoS/DDoS攻击防御方法、流规则的合法性和一致性检测、北向接口的安全性和应用程序安全性;最后对SDN安全方面的标准化工作进行了简要分析,并对SDN安全方面未来的研究趋势进行了展望.

摘要:软件定义网络(software defined networking,简称SDN)的产生使得网络中的数据平面与控制平面相分离,网络中的控制逻辑集中于控制器上,运行于控制器上的网络应用使得网络变得更加简单可控和灵活.软件定义网络中的北向接口是指控制器与网络应用之间进行通信的接口.在软件定义网络应用研究与开发的过程中,北向接口占据着一个重要的地位.综述了SDN中北向接口的编程语言,首先介绍北向接口编程语言的研究背景,然后根据编程语言的抽象程度、编程模型、实现机制以及是否引入新功能这4个方面将编程语言分类,详细介绍每个类别下各种北向接口语言的结构和核心特性,最后结合语言的应用场景对编程语言进行横向比较,进而展望了北向接口编程语言未来的研究方向.

摘要:随着计算机硬件技术的发展,如今我们已经迈入了多核CPU时代.然而,作为软件核心的数据结构仍然是按照单核CPU和顺序型准则来设计的.在基于共享内存的多核时代,大量并发运行的线程会交替地修改数据,产生不可预期的结果,因而我们面临着严峻挑战.针对基于共享内存多核时代数据结构的相关研究进行综述.首先,对比了并发与并行的区别,归纳了基于演进条件(progress condition)的多核数据结构分类,对近年来学术界对各种类型并发数据结构的研究进行综述.在此基础上,剖析了并发数据结构设计和实现的关键技术,并从并发数据结构的开发流程、正确性验证等方面进行了归纳阐述.最后,基于这些讨论,对多核架构下并发数据结构未来的研究趋势和应用前景进行了展望.

摘要:云计算引领了计算机科学的一场重大变革,但与此同时,也不可避免地带来了日益凸显的能源消耗问题,因此,云计算能耗管理成为近几年的研究热点.云计算系统的能耗测量和管理直接关系到云计算的可持续发展,能耗数据不仅关系到能耗模型的建立,而且也是检验云计算资源调度算法的基础.为此,在广泛研究现有能耗测量方法的基础上,归纳总结了当前云计算环境的4种能耗测量方法:基于软件或硬件的直接测量方法、基于能耗模型的估算方法、基于虚拟化技术的能耗测量方法、基于仿真的能耗评估方法,并分析和比较了它们的优势、缺陷和适用环境.在此基础上,指出了云计算能耗管理的未来重要研究趋势:智能主机电源模块、面向不同类型应用的能耗模型、混合任务负载的能耗模型、可动态管理的高效云仿真工具、动态异构分布式集群的能耗管理、面向大数据分析处理和任务调度的节能方法以及新能源供电环境下的节能规划,为云计算节能领域的研究指明了方向.

摘要:提出一种在不可信操作系统中保护应用程序的新方法AppISO.针对传统的虚拟化方法的高开销问题,AppISO在不可信操作系统的同一特权层引入内可信基,代替虚拟机监控器实施应用程序保护,避免了昂贵的特权层切换.同时利用硬件虚拟化,以及页表锁定、影子IDT、切换页面等软件技术保证内可信基的安全性.证明了所提内可信基方法与虚拟化方法具有同样的高安全性.实验和分析结果表明,内可信基方法可显著地提高系统性能.