软件测试力求以更低的成本和更快的效率,生成与选择具有代表性的测试用例来检测软件程序中的故障。在现有的测试用例生成方法中,随机测试(Random Testing,RT)能够根据其随机分布的特点来挑选测试用例。该方法因其简单实用的特性,已广泛应用于实际测试中,但它并不能有效地利用测试用例的空间位置等信息,所以故障检测效果并不理想。为了提升随机测试的故障检测效果,研究人员提出了适应性随机测试(Adaptive Random Testing,ART)方法,它利用已执行但未发现故障的测试用例位置信息来产生测试用例,保证测试用例尽可能“均匀”地分布在输入域中,进而显著地提升故障检测效果。作为适应性随机测试的典型研究方法,FSCS-ART(Fixed-Sized-Candidate-Set ART)因其具备较好的检测效果,自提出便被深入研究。然而随着输入域维度的升高,它所生成的测试用例很大程度靠近于输入域边缘,导致故障检测效果变差,不仅如此,庞大的计算开销也会使得运行效率急剧下降。针对FSCS-ART方法中存在的故障检测效果差和运行效率低这两类问题,本研究提出了一种新的适应性随机测试用例生成算法——基于网格区域密度的适应性随机测试用例生成算法ART-DGR(ART by Density of Grid Region)。该算法利用动态网格划分思想对输入域进行划分,使得生成的测试用例在输入域中显得更加均匀。同时综合考虑区域数量和用例之间的距离情况,使用区域候选策略和距离候选策略来对候选目标进行双重筛选,并且通过区域密度指标来了解当前子区域和整个输入域的紧密联系程度,改善FSCS-ART算法的故障检测效果。针对算法高维情况下存在的复杂邻域查询开销和计算开销问题,提出了基于曼哈顿距离的遗忘策略来改进算法,使得计算效率得到大幅度提升,从而解决了FSCSART算法存在的效率问题。最后通过开展详细的模拟实验和实证实验,来验证ART-DGR算法的有效性。实验结果表明,本研究设计的ART-DGR算法符合“均匀分布”的要求,计算开销理想,相比于FSCS-ART算法有着较好的故障检测效果。在高维输入域中,改进后的ART-DGR算法也表现出了更快的计算运行效率。测试用例生成技术研究有助于测试人员在短时间内更准确地检测出程序故障,大大减少了人力资源成本和时间消耗。本文对适应性随机测试展开研究,改进了其产生随机测试用例的生成策略,对比分析了FSCS-ART算法和其它ART方法,提出了ART-DGR算法及其高维改进后的算法,对软件测试学术领域和工业实际测试领域具有重要的参考意义。