微处理器体系结构级测试程序自动生成技术

提出了一种由体系结构描述驱动的基于约束求解的微处理器体系结构级测试程序自动生成的新方法,并基于此开发了原型系统--MA2TG(microprocessor architectural automatic test program generator).该系统不仅可以随机生成测试程序,最主要的是可以产生针对特定要求的测试程序.其优点在于:首先,通过体系结构语言描述简化了体系结构建模,方便了对目标处理器体系结构的探索;第二,利用比较成熟的约束求解技术来生成满足需求的测试程序;第三,极大地缩减了测试程序的大小以及微处理器的验证时间.MA2TG已应用于DLX处理器和自主开发的EStar嵌入式微处理器的验证.实验结果表明了此方法的有效性.     

基于程序约束的细粒度JVM测试程序约简方法

为了对Java虚拟机(JVM)进行测试,开发人员通常需要手工设计或利用测试生成工具生成复杂的测试程序,从而检测JVM中潜在的缺陷。然而,复杂的测试程序给开发人员定位及修复缺陷带来了极高的成本。测试程序约简技术旨在保障测试程序缺陷检测能力的同时,尽可能的删减测试程序中与缺陷检测无关的代码。现有研究工作基于Delta调试在C程序和XML输入上可以取得较好的约简效果,但是在JVM测试场景中,具有复杂语法和语义依赖关系的Java测试程序约减仍存在粒度较粗、约简效果较差的问题,导致约简后的程序理解成本依然很高。因此,针对具有复杂程序依赖关系的Java测试程序,本文提出一种基于程序约束的细粒度测试程序约简方法JavaPruner。首先在语句块级别设计细粒度的代码度量方法,随后在Delta调试技术上引入语句块之间的依赖约束关系来对测试程序进行约简。以Java字节码测试程序为实验对象,通过从现有的针对JVM测试的测试程序生成工具中筛选出具有复杂依赖关系的50个测试程序作为基准数据集,并在这些数据集上验证JavaPruner的有效性。实验结果表明,JavaPruner可以有效删减Java字节码测试程序中的冗余代码。与现有方法相比,在所有基准数据集上约减能力平均可提升37.7%。同时,JavaPruner可以在保障程序有效性及缺陷检测能力的同时将Java字节码测试程序最大约简至其原有大小的1.09% ,有效降低了测试程序的分析和理解成本。     

基于覆盖率的微处理器运算单元验证技术

根据微处理器运算单元功能较多的特点,基于覆盖率的验证方法,设计一种自检查的测试程序生成器(SATG)验证方法。SATG采用一种“闭环”结构,并以功能覆盖率量化分析为核心,使用随机生成和约束求解的方法,自动生成验证程序。实验结果表明,该方法在微处理器运算单元的验证中,能提高验证效率和覆盖率,增强验证平台的可重用性。     

基于MAS的分布式约束满足求解在供应链研究中的应用

简要介绍了多智能体系统(MAS)在供应链研究中的应用，给出了约束满足问题(Constraint Satisfaction Problem,CSP)和分布式约束满足问题(Distributed CSP)的定义以及其应用现状，提出了一个利用基于MAS的分布式约束满足求解来研究供应链问题的基本框架，并给出了其求解过程。     

协同设计中定量化约束求解方法

通过对约束满足与约束冲突的分析，提出了约束求解的定量化策略．基于变量不确定性，量化了约束满足程度与约束冲突程度，解决了约束求解过程中的优先权问题；给出了约束变化量及关联函数，为约束求解确立了具体的目标和实施方法，实现了约束求解过程的有序搜索．定量化约束求解策略不仅实现了对约束的有序及有效求解，而且真正地实现了在上游约束求解过程中定量地考虑下游约束求解问题．最后，利用随机仿真技术实现了基于变量不确定性的约束求解策略的验证．     

基于随机模型预测控制的四旋翼无人机研究

由于随机扰动(可能无界)的存在，四旋翼无人机系统存在控制性能不稳定、输入抖动大的问题。针对这种情况，提出一种随机模型预测控制算法。算法对控制约束进行软化，使其在一定范围内可以违反约束以满足系统性能的提高，并添加扰动反馈结构进行实时监测。运用分布式鲁棒的方法对扰动进行重构，扰动重构后再分别对单输入机会约束与联合状态机会约束进行可计算的精确凸优化重构。加入精确罚函数方法以进一步保证系统可行性。实验对比结果表明，与无扰动的模型预测控制(MPC)算法相比，该算法能够在满足约束的情况下克服任意随机扰动(可能无界)完成目标跟踪，且具备更优秀的预测性能。     

一种基于场景的随机模型预测飞行策略

提出一种飞机运动基于场景的随机模型预测控制策略，对于飞机位置实施了机会约束，但是由于干扰的复杂性，机会约束问题的难以计算。为了解决该问题，参考基于场景的随机求解算法，以相对低的计算量找到机会约束有限水时域优化问题的近似解，使得飞机有效地跟踪参考轨迹。此外，控制器也满足了飞机的动力学和物理限制，且对干扰具有鲁棒性。仿真结果验证了该方法的有效性。     

ATS模拟总线及其控制模型的建立

介绍了ATS(自动检测系统)模拟总线的概念，并叙述了模拟总线的控制模型及控制程序的设计方法。这种技术不但可以简化测试程序的设计，还可以实现测试程序与信号转接通道设计的无关性，从而大大提高测试程序的可重用性和可维护性。     

基于参数的测试程序开发技术研究

针对基于编程的测试程序(TP)开发技术在实际应用中存在的问题,提出了基于参数的TP开发技术.介绍了基于参数的TP开发原理、参数测试程序的开发、基于参数的TP开发以及测试执行引擎的设计.基于参数的测试程序开发过程实际上是根据测试需求选择参数、确定参量,组合、调试、封装测试程序的过程,实践表明基于参数的测试程序开发技术可有效解决传统TP开发方式编程困难、重复编程等共性问题,具有较强的推广和应用价值.     

基于符号执行的Tcache Poisoning堆漏洞自动验证方法研究

Tcache Poisoning是面向堆管理机制的一种堆漏洞利用方法，现有的堆漏洞自动验证工作未考虑Tcache带来的影响，无法适用于高版本Glibc堆漏洞自动验证。分析Tcache机制以及Tcache Poisoning验证方法的原理，提出一种基于符号执行的Tcache Poisoning堆漏洞自动验证方法。定义多元组对堆块的状态进行形式化描述，通过对关键API函数的挂钩，在程序运行过程中收集堆块的状态信息，并引入符号变元将外部输入数据符号化，实现关键信息的获取。通过状态监控检测堆漏洞触发，依据Tcache Poisoning堆漏洞自动验证模型，逐步生成Tcache Poisoning攻击约束和攻击载荷约束，最后通过约束求解生成漏洞验证代码。基于S2E符号执行平台实现自动验证系统TPAEG，并对10个测试程序进行测试，其中在Tcache Poisoning方法的7个测试程序中有5个生成了验证代码。实验结果表明，TPAEG可有效地检测堆溢出漏洞和释放后重用漏洞，并能够针对符合Tcache Poisoning攻击特征的场景实现自动验证，完成控制流的劫持并生成验证代码。     

基于约束的软件失效域识别与特征分析

随机测试是实践中广泛采用的一种黑盒测试方法.近年来提出的适应性随机测试方法改进了随机测试的不足,仿真实验结果表明,改进效果取决于软件失效域的特征.提出以测试约束刻画软件失效域在输入域上的分布,探讨了基于现有的程序分析技术构造测试约束的过程,讨论了基于测试约束的软件失效域的特征分析方法.以一个实例软件验证所提出的测试约束构造过程及其软件失效域特征分析方法.测试约束揭示了软件故障的触发与传播的内在机制,基于测试约束的软件失效域的特征分析方法有助于改进测试用例的设计质量以及评价适应性随机测试方法的适用性.     

A uniform random test data generator for path testing

Path-oriented Random Testing (PRT) aims at generating a uniformly spread out sequence of random test data that execute a single control flow path within a program. The main challenge of PRT lies in its ability to build efficiently such a test suite in order to minimize the number of rejects (test data that execute another control flow path). We address this problem with an original divide-and-conquer approach based on constraint reasoning over finite domains, a well-recognized Constraint Programming technique. Our approach first derives path conditions by using backward symbolic execution and computes a tight over-approximation of their associated subdomain by using constraint propagation and constraint refutation. Second, a uniform random test data generator is extracted from this approximated subdomain. We implemented this approach and got experimental results that show the practical benefits of PRT based on constraint reasoning. On average, we got a two-order magnitude CPU time improvement over standard Random Testing on a set of paths extracted from classical benchmark programs.     

Generating test data for both path coverage and fault detection using genetic algorithms

The aim of software testing is to find faults in a program under test, so generating test data that can expose the faults of a program is very important. To date, current studies on generating test data for path coverage do not perform well in detecting low probability faults on the covered path. The automatic generation of test data for both path coverage and fault detection using genetic algorithms is the focus of this study. To this end, the problem is first formulated as a bi-objective optimization problem with one constraint whose objectives are the number of faults detected in the traversed path and the risk level of these faults, and whose constraint is that the traversed path must be the target path. An evolutionary algorithmis employed to solve the formulatedmodel, and several types of fault detectionmethods are given. Finally, the proposed method is applied to several real-world programs, and compared with a random method and evolutionary optimization method in the following three aspects: the number of generations and the time consumption needed to generate desired test data, and the success rate of detecting faults. The experimental results confirm that the proposed method can effectively generate test data that not only traverse the target path but also detect faults lying in it.     

An empirical study on constraint optimization techniques for test generation

Constraint solving is a frequent, but expensive operation with symbolic execution to generate tests for a program. To improve the efficiency of test generation using constraint solving, four optimization techniques are usually applied to existing constraint solvers, which are constraint independence, constraint set simplification, constraint caching, and expression rewriting. In this paper, we conducted an empirical study, using these four constraint optimization techniques in a well known test generation tool KLEE with 77 GNU Coreutils applications, to systematically investigate how these optimization techniques affect the efficiency of test generation. The experimental results show that these constraint optimization techniques as well as their combinations cannot improve the efficiency of test generation significantly for ALL-SIZED programs. Moreover, we studied the constraint optimization techniques with respect to two static metrics, lines of code (LOC) and cyclomatic complexity (CC), of programs. The experimental results show that the “constraint set simplification” technique can improve the efficiency of test generation significantly for the programs with high LOC and CC values. The “constraint caching” optimization technique can improve the efficiency of test generation significantly for the programs with low LOC and CC values. Finally, we propose four hybrid optimization strategies and practical guidelines based on different static metrics.     

一种基于双约束传播的面向路径自动随机测试方法

随机测试是一种常用的软件测试自动化方法。该方法随机地从程序输入域中选取测试输入,其自动测试实现容易。但随机地从输入域中选取满足某种测试准则的输入数据,测试生成效率较低。为此提出了一种基于双约束传播的面向路径自动随机测试方法,通过对输入变量的取值范围进行切分,执行两次约束传播来求取指定路径的输入域,在此基础上开发了一个自动随机测试生成系统,并与PRT方法进行了实验对比分析。结果表明,该方法计算出的路径输入域更加精确,可有效地减少对无效域的测试生成,提高了随机测试的效率。     

GC-MCR: Directed Graph Constraint-guided Concurrent Bug Detection Method

Constraint solving has been applied to many domains of program analysis and is further used in concurrent program analysis. Concurrent programs have been widely used with the rapid development of multi-core processors. However, concurrent bugs threaten the security and reliability of concurrent programs, and thus it is of great importance to detect concurrent bugs. The explosion of thread interleaving caused by the uncertainty of the execution of concurrent program threads brings some challenges to the detection of concurrent bugs. Existing concurrent defect detection algorithms reduce the exploration cost in the state space of concurrent programs by reducing invalid thread interleaving. For example, the maximal causal model algorithm transforms the state space exploration problem of concurrent programs into a constraint solving problem. However, it will produce a large number of redundant and conflicting constraints during constraint construction, which greatly prolongs the time of constraint solving, increases the number of constraint solver calls, and reduces the exploration efficiency of concurrent program state space. Thus, this study proposes a directed graph constraint-guided maximal causality reduction method, called GC-MCR. This method aims to improve the speed of constraint solving and the efficiency of the state space exploration of concurrent programs by filtering and reducing constraints using directed graphs. The experimental results show that the GC-MCR method can effectively optimize the expression of constraints, so as to improve the solving speed of the constraint solver and reduce the number of solver calls. Compared with the existing J-MCR method, GC-MCR can significantly improve the detection efficiency of concurrent program bugs without reducing the detection ability of concurrent bugs, and the test time on 38 groups of concurrent test programs widely used by existing research methods can be reduced by 34.01% on average.     

基于覆盖率驱动的高性能DSP指令集验证方法

针对传统定向测试效率较低且容易遗漏边界条件,以及测试平台扩展性、移植性差等问题,利用SystemVerilog的面向对象特性、随机约束求解机制以及覆盖率统计机制,提出一种快速搭建覆盖率驱动的随机测试平台的方法。采用面向对象方法对指令集建模,同时定义功能覆盖点和交叉覆盖率,并对随机约束规则进行描述,利用SystemVerilog的约束求解机制在覆盖率驱动下生成大量的测试指令码。对"银河飞腾"高性能DSP芯片指令集进行验证,结果表明,与定向测试相比,随机测试的寄存器和数据通路覆盖率提高50%,操作数覆盖率提高90%以上,交叉覆盖率提高75%以上,同时功能覆盖率能在较短的时间内达到预期值,从而缩短验证周期。     

LEARNING TO SUPPORT CONSTRAINT PROGRAMMERS

This paper describes the Adaptive Constraint Engine (ACE), an ambitious ongoing research project to support constraint programmers, both human and machine. The program begins with substantial knowledge about constraint satisfaction. The program harnesses a cognitively-oriented architecture (FORR) to manage search heuristics and to learn new ones. ACE can transfer what it learns on simple problems to solve more difficult ones, and can readily export its knowledge to ordinary constraint solvers. It currently serves both as a learner and as a test bed for the constraint community.     

Code-coverage guided prioritized test generation

Most automatic test generation research focuses on generation of test data from pre-selected program paths or input domains or program specifications. This paper presents a methodology for a full solution to code-coverage-based test case generation, which includes code coverage-based path selection, test data generation and actual test case representation in program’s original languages. We implemented this method in an automatic testing framework, eXVantage. Experimental results and industrial trials show that the framework is able to generate tests to achieve program line coverage from 20% to 98% with reduced overall testing effort. Our major contributions include an innovative coverage-based program prioritization algorithm, a novel path selection algorithm that takes into consideration program priority and functional calling relationship, and a constraint solver for test data generation that derives constraints from bytecode and solves complex constraints involving strings and dynamic objects.     

A CP framework for testing CP

The success of several constraint-based modeling languages such as OPL, ZINC or COMET, appeals for better software engineering practices, particularly in the testing phase. This paper introduces a testing framework enabling automated test case generation for constraint programming. We propose a general framework of constraint program development which supposes that a first declarative and simple constraint model is available from the problem specifications analysis. Then, this model is refined using classical techniques such as constraint reformulation, surrogate, redundant, implied, global constraint and symmetry-breaking to form an improved constraint model that must be thoroughly tested before being used to address real-sized problems. We think that most of the faults are introduced in this refinement step and propose a process which takes the first declarative model as an oracle for detecting non-conformities and derive practical test purposes from this process. We implemented this approach in a new tool called CPTEST that was used to automatically detect non-conformities on classical benchmark programs, such as the Golomb rulers, n-queens, social golfer and the car-sequencing problems.