basic research in computer science and software engineering at sklcs

The State Key Laboratory of Computer Science (SKLCS) is committed to basic research in computer science and software engineering. The research topics of the laboratory include: concurrency theory, theory and algorithms for real-time systems, formal specifications based on context-free grammars, semantics of programming languages, model checking, automated reasoning, logic programming, software testing, software process improvement, middleware technology, parallel algorithms and parallel software, computer graphics and human-computer interaction. This paper describes these topics in some detail and summarizes some results obtained in recent years.

a backtracking search tool for constructing combinatorial test suites

Combinatorial testing is an important testing method. It requires the test cases to cover various combinations of parameters of the system under test. The test generation problem for combinatorial testing can be modeled as constructing a matrix which has certain properties. This paper first discusses two combinatorial testing criteria: covering array and orthogonal array, and then proposes a backtracking search algorithm to construct matrices satisfying them. Several search heuristics and symmetry breaking techniques are used to reduce the search time. This paper also introduces some techniques to generate large covering array instances from smaller ones. All the techniques have been implemented in a tool called EXACT (EXhaustive seArch of Combinatorial Test suites). A new optimal covering array is found by this tool.

关于蜕变测试和特殊用例测试的实例研究

提出了基于蜕变测试方法的集成测试环境MTest,进而为检验蜕变测试方法的能力和效率,以稀疏矩阵乘法程序为例设计了一组实验.该实验基于变异分析技术,分别以mutation score和错误发现率为度量指标,定量地分析和对比了特殊用例测试,以特殊测试用例和随机测试用例为源测试用例的蜕变测试这3种方法的测试能力和效率.该实验可在MTest测试环境下自动完成.实验结果表明,蜕变测试与特殊用例测试之间是互补的,而且就蜕变测试的源测试用例而言,随机测试用例在测试能力和效率上优于特殊测试用例.

an efficient method to generate feasible paths for basis path testing

Basis path testing is a very powerful structural testing criterion. The number of test paths equals to the cyclomatic complexity of program defined by McCabe. Traditional test generation methods select the paths either without consideration of the constraints of variables or interactively. In this note, an efficient method is presented to generate a set of feasible basis paths. The experiments show that this method can generate feasible basis paths for real-world C programs automatically in acceptable time.

automated test case generation for the stress testing of multimedia systems

With the advancement in network bandwidth and computing power, multimedia systems have become a popular means for information delivery. However, general principles of system testing cannot be directly applied to testing of multimedia systems on account of their stringent temporal and synchronization requirements. In particular, few studies have been made on the stress testing of multimedia systems with respect to their temporal requirements under resource saturation. Stress testing is important because erroneous behavior is most likely to occur under resource saturation. This paper presents an automatable method of test case generation for the stress testing of multimedia systems. It adapts constraint solving techniques to generate test cases that lead to potential resource saturation in a multimedia system. Coverage of the test cases is defined upon the reachability graph of a multimedia system. The proposed stress testing technique is supported by tools and has been successfully applied to a real-life commercial multimedia system. Although our technique focuses on the stress testing of multimedia systems, the underlying issues and concepts are applicable to other types of real-time systems.

Real-Time Measurement on Deformation Fields of Hole-Excavated Samples under Impact Tension

In this paper, the real-time deformation fields are observed in two different kinds of hole-excavated dog-bone samples loaded by an SHTB, including single hole sample and dual holes sample with the aperture size of 0.8mm. The testing system consists of a high-speed camera, a He-Ne laser, a frame grabber and a synchronization device with the controlling accuracy of I microsecond. Both the single hole expanding process and the interaction of the two holes are recorded with the time interval of 10 mu s. The observed images on the sample surface are analyzed by newly developed software based on digital correlation theory and a modified image processing method. The 2-D displacement fields in plane are obtained with a resolution of 50 mu m and an accuracy of 0.5 mu m. Experimental results obtained in this paper are proofed, by compared with FEM numerical simulations.

Strength of Offshore Pipelines in Different Operation States and Analyzing Software

在近海管线的铺设、安装、使用过程中有多种作业状态：在位、悬跨、挖沟、提吊、铺管等。各种状态下管线的受力特点不同,加上管线结构、海况和海底土壤等因素又都很复杂,所以近海管线的强度分析难度大、内容多。分别采用解析方法、数值方法（有限元法、打靶法）和二者结合来解决理论上的（如几何非线性、动边界等）、实用性方面的难点。在理论分析的基础上,编制了符合产业部门工程师使用要求的近海管线强度分析软件。介绍了该软件进行力学分析时采用的理论以及软件界面。

Real-Time Measurement on Deformation Fields of Hole-Excavated Samples under Impact Tension

In this paper, the real-time deformation fields are observed in two different kinds of hole-excavated dog-bone samples loaded by an SHTB, including single hole sample and dual holes sample with the aperture size of 0.8mm. The testing system consists of a high-speed camera, a He-Ne laser, a frame grabber and a synchronization device with the controlling accuracy of I microsecond. Both the single hole expanding process and the interaction of the two holes are recorded with the time interval of 10 mu s. The observed images on the sample surface are analyzed by newly developed software based on digital correlation theory and a modified image processing method. The 2-D displacement fields in plane are obtained with a resolution of 50 mu m and an accuracy of 0.5 mu m. Experimental results obtained in this paper are proofed, by compared with FEM numerical simulations.

A small arc-heated plasma testing facility for thermal protection materials

Experimental research on a 150 kW arc-heated plasma testing facility was conducted. Stable plasma jets with different gas compositions, temperatures and velocities were obtained at chamber pressure between 400 Pa – 100 kPa. Stagnation ablation experiments were conducted on samples of typical super alloys used for thermal protection systems. The microstructure and hardness of alloys before and after ablation were compared.

Wave-front analysis method of circular aperture sampling for collimation testing

A new type of wave-front analysis method for the collimation testing of laser beams is proposed. A concept of wave-front height is defined, and, on this basis, the wave-front analysis method of circular aperture sampling is introduced. The wave-front height of the tested noncollimated wave can be estimated from the distance between two identical fiducial diffraction planes of the sampled wave, and then the divergence is determined. The design is detailed, and the experiment is demonstrated. The principle and experiment results of the method are presented. Owing to the simplicity of the method and its low cost, it is a promising method for checking the collimation of a laser beam with a large divergence. © 2005 Optical Society of America.

Collimation testing using axial intensity

We proposed a new method of measuring the degree of collimation of laser beam using axial intensity information near paraxial focus. Preceding methods for collimation testing are mainly either based on self-imaging or interferometric techniques. The new method is to employ the diffraction behavior of noncollimated wave in circular aperture diaphragm. The principle of the proposed method and experiment results are presented. Due to simplicity of the method and its low cost, it is a promising method for checking the collimation of laser beam. (c) 2005 Published by Elsevier GmbH.

用于机载激光测深系统的时间间隔测量模块

机载海洋激光测深系统不仅要求精确测量激光从海表的入射点到海底目标点之间的距离，还要精确测定飞机到海表入射，点之间的距离，为水深数据的海浪校正而确定平均海平面以及波高。为此设计和研制了一高精度时间间隔测量器，该单元基于专用时间数字转换芯片开发，采用延迟线插入法技术，双通道工作，具有高时间分辨率(最高可达250ps)和高测量重复率的特性。给出硬件和软件设计方法以及单元的测试结果。