Using combinatorial testing to build navigation graphs for dynamic web applications

Modelling a software system is often a challenging prerequisite to automatic test case generation. Modelling the navigation structure of a dynamic web application is particularly challenging because of the presence of a large number of pages that are created dynamically and the difficulty of reaching a dynamic page unless a set of appropriate input values are provided for the parameters. To address the first challenge, some form of abstraction is required to enable scalable modelling. For the second challenge, techniques are required to select appropriate input values for parameters and systematically combine them to reach new pages. This paper presents a combinatorial approach in building a navigation graph for dynamic web applications. The navigation graph can then be used to automatically generate test sequences for testing web applications. The novelty of our approach is twofold. First, we use an abstraction scheme to control the page explosion problem, where pages that are likely to have the same navigation behaviour are grouped together and are represented as a single node in the navigation graph. Second, assuming that values of individual parameters are supplied manually or generated from other techniques, we combine parameter values such that well‐defined combinatorial coverage of input parameter values is achieved. Using combinatorial coverage can significantly reduce the number of requests that have to be submitted while still achieving effective coverage of the navigation structure. We implement our combinatorial approach in a tool, Tansuo, and apply the tool on seven open‐source web applications. We evaluate the effectiveness of Tansuo's exploration process guided by t‐way coverage, for t = 1,2,3, with respect to code coverage, and find that the navigation structure exploration by Tansuo, in general, results in high code coverage (more than 80% statement coverage for most of our subject applications when dead code is removed). We compare Tansuo's effectiveness with two other navigation graph tools and find that Tansuo is more effective. Our empirical results indicate that using pairwise coverage in Tansuo results in the efficient generation of navigation graphs and effective exploration of dynamic web applications. Copyright © 2016 John Wiley & Sons, Ltd.     

动态web应用中的缺陷定位研究

在动态web应用中,动态生成的HTML页面产生的缺陷难以定位并且会严重影响web应用程序的可用性和稳定性。针对以上问题,本文提出了一种基于符号约束集的web缺陷定位方法,通过对web服务端程序的动态符号执行生成一个带有符号约束的树模型,并给出了一个高效的缺陷映射定位算法。为验证该方法的有效性,本文对几个基于PHP的开源web程序进行实验,结果表明该方法在web应用的HTML缺陷检测定位覆盖率和准确率方面都有所改进。     

Metaheuristic Algorithm for State-Based Software Testing

This article presents a metaheuristic algorithm for testing software, especially web applications, which can be modeled as a state transition diagram. We formulate the testing problem as an optimization problem and use a simulated annealing (SA) metaheuristic algorithm to generate test cases as sequences of events while keeping the test suite size reasonable. SA evolves a solution by minimizing an energy function that is based on testing objectives such as coverage, diversity, and continuity of events. The suggested method includes a “significance weight” assigned to events, which leads to important web pages and ensures coverage of relevant features by test cases. The experimental results demonstrate the effectiveness of simulated annealing and show that SA yields good results for testing web applications in comparison with other heuristics.     

应用聚类技术分类提取Web页面

针对Web中数据密集型的动态页面,文本数据少,网页结构化程度高的特点,介绍了一种基于HTML结构的web信息提取方法。该方法先将去噪处理后的Web页面进行解析,然后根据树编辑距离计算页面之间的相似度,对页面进行聚类,再对每一类簇生成相应的提取规则,对Web页面进行数据提取。     

Practical minimization of pairwise-covering test configurations using constraint programming

Context: Testing highly-configurable software systems is challenging due to a large number of test configurations that have to be carefully selected in order to reduce the testing effort as much as possible, while maintaining high software quality. Finding the smallest set of valid test configurations that ensure sufficient coverage of the system’s feature interactions is thus the objective of validation engineers, especially when the execution of test configurations is costly or time-consuming. However, this problem is NP-hard in general and approximation algorithms have often been used to address it in practice.Objective: In this paper, we explore an alternative exact approach based on constraint programming that will allow engineers to increase the effectiveness of configuration testing while keeping the number of configurations as low as possible.Method: Our approach consists in using a (time-aware) minimization algorithm based on constraint programming. Given the amount of time, our solution generates a minimized set of valid test configurations that ensure coverage of all pairs of feature values (a.k.a. pairwise coverage). The approach has been implemented in a tool called PACOGEN.Results: PACOGEN was evaluated on 224 feature models in comparison with the two existing tools that are based on a greedy algorithm. For 79% of 224 feature models, PACOGEN generated up to 60% fewer test configurations than the competitor tools. We further evaluated PACOGEN in the case study of an industrial video conferencing product line with a feature model of 169 features, and found 60% fewer configurations compared with the manual approach followed by test engineers. The set of test configurations generated by PACOGEN decreased the time required by test engineers in manual test configuration by 85%, increasing the feature-pairs coverage at the same time.Conclusion: Our experimental evaluation concluded that optimal time-aware minimization of pairwise-covering test configurations is efficiently addressed using constraint programming techniques.     

Building test cases and oracles to automate the testing of web database applications

Many organizations rely on web applications that use back-end databases to store important data. Testing such applications requires significant effort. Manual testing alone is often impractical, so testers also rely on automated testing techniques. However, current automated testing techniques may produce false positives (or false negatives) even in a perfectly working system because the outcome of a test case depends on the state of the database which changes over time as data is inserted and deleted. The Automatic Database Tester (AutoDBT) generates functional test cases that account for database updates. AutoDBT takes as input a model of the application and a set of testing criteria. The model consists of a state transition diagram that shows how users navigate pages, a data specification that captures how data flows, and an update specification that shows how the database is updated. AutoDBT generates guard queries to determine whether the database is in a state conducive to performing and evaluating tests. AutoDBT also generates partial oracles to help validate whether a back-end database is updated correctly during testing. This paper describes the design of AutoDBT, a prototype implementation, several experiments with the prototype, and four case studies.     

基于协议混合变形的Web安全模糊测试与效用评估方法

在Web应用安全模糊测试中,存在测试用例覆盖率低、测试效用无法得到有效验证及漏洞检测结果无法得到有效评估等问题。提出了协议变形和动态特征并行混合的测试用例生成方法,建立了按典型漏洞分类的输入特征组合规则和协议变形规则,并形成了基于污染传播策略漏洞响应数据分析和有效性验证的方法。实验表明所提方法增大了测试用例的多样性以及提高了覆盖率,降低了在网站过滤环境复杂情况下的漏洞检测的漏报率和误报率。     

Towards generic representation of web applications: solutions and trade‐offs

Server pages (also called dynamic pages) render a generic web page into many similar ones. The technique is commonly used for implementing web application user interfaces (UIs). Yet our previous study found a high rate of repetitions (also called ‘clones’) in web applications, particularly in UIs. The finding raised the question as to why such repetitions had not been averted with the use of server pages. For an answer, we conducted an experiment using PHP server pages to explore how far server pages can be pushed to achieve generic web applications. Our initial findings suggested that generic representation obtained using server pages sometimes compromises certain important system qualities such as run‐time performance. It may also complicate the use of WYSIWYG editors. We have analysed the nature of these trade‐offs, and now propose a mixed‐strategy approach to obtain optimum generic representation of web applications without unnecessary compromise to critical system qualities and user experience. The mixed‐strategy approach applies the generative technique of XVCL to achieve genericity at the meta‐level representation of a web application, leaving repetitions to the actual web application. Our experiments show that the mixed‐strategy approach can achieve a good level of genericity without conflicting with other system qualities. Our findings should open the way for others to better‐informed decisions regarding generic design solutions, which should in turn lead to simpler, more maintainable and more reusable web applications. Copyright © 2008 John Wiley & Sons, Ltd.     

A novel strategy for automatic test data generation using soft computing technique

Software testing is one of the most crucial and analytical aspect to assure that developed software meets prescribed quality standards. Software development process invests at least 50% of the total cost in software testing process. Optimum and efficacious test data design of software is an important and challenging activity due to the nonlinear structure of software. Moreover, test case type and scope determines the quality of test data. To address this issue, software testing tools should employ intelligence based soft computing techniques like particle swarm optimization (PSO) and genetic algorithm (GA) to generate smart and efficient test data automatically. This paper presents a hybrid PSO and GA based heuristic for automatic generation of test suites. In this paper, we described the design and implementation of the proposed strategy and evaluated our model by performing experiments with ten container classes from the Java standard library. We analyzed our algorithm statistically with test adequacy criterion as branch coverage. The performance adequacy criterion is taken as percentage coverage per unit time and percentage of faults detected by the generated test data. We have compared our work with the heuristic based upon GA, PSO, existing hybrid strategies based on GA and PSO and memetic algorithm. The results showed that the test case generation is efficient in our work.     

基于两两覆盖准则的遗传算法测试用例生成

软件参数的组合测试是发现参数组合问题的重要方法,但是参数组合测试面临着组合爆炸问题,成对测试可以有效降低测试成本。提出了一种基于遗传算法的成对测试生成方法,该方法用于选择当前局部优化覆盖的测试用例,在此基础上构建满足成对测试基准的测试用例套,结果表明该方法能在不降低测试覆盖精度的情况下有效降低了测试用例数量。     

面向测试生成的ASM模型约简研究

基于模型的Web应用程序测试是软件测试的一个重要方法。ASM模型从源码解析的角度,基于Web应用程序表示层建立模型,描述了Web应用程序的交互性、动态性和低耦合性。基于ASM模型的测试用例生成,考虑用户的非预期行为,在主要路径的基础上,通过添加无效访问状态和无效迁移路径,扩充测试用例。然而,随着Web应用程序规模的扩大,无效访问状态和无效迁移路径的增加导致测试用例空间爆炸。在研究ASM模型的基础上,通过定义基于ASM模型测试生成的等价迁移和等价状态,合并迁移和状态,从而有效地对ASM模型进行约简,减少了无效访问状态和无效迁移路径的数量,实现测试用例空间约减。 对一个实际Web应用程序系统的评估结果表明,基于模型约简的测试用例优化,有效约减了74.38%的测试用例空间,并且对原子段的覆盖率和错误检测数目没有产生影响。     

Comparing coverage criteria for dynamic web application: An empirical evaluation

Web applications have become popular and a preferred mean for users to do various crucial tasks such as selling and buying goods, doing short tasks, controlling smart houses and bank account management. The correctness of all such applications is important and requires thorough testing. Structural testing is widely used to achieve correctness in traditional software's, however, for web applications, it is challenging because of its dynamic and heterogeneous nature. To achieve desired structural coverage of web applications different dynamic coverage criteria are used as a quality assessment indicator. However, there is a lack of empirical evidence regarding the effectiveness of the proposed coverage criteria. In this paper, we conduct an empirical evaluation by evaluating and comparing the fault detection effectiveness and efficiency of various dynamic coverage criteria by performing mutation analysis. We conduct a series of experiments to assess and compare four widely used coverage criteria on seven open-source case studies including small to large scale applications. We performed mutation analysis by first generating different faulty versions (mutants) for the case studies and then by executing test suites to record mutation score for each criterion. The results from most of the subject applications show that DOM coverage is the most effective and efficient criterion followed by Virtual DOM, HTML Element and Statement coverage criteria.     

基于Java的Web应用全球化自动测试设计

随着Internet的广泛应用,基于Web页面的应用已成为当前计算机应用软件中最常用的形式。每一个Web软件产品都会有很多Web页面,尤其是支持多种语言的应用,由于如今对Web应用的测试绝大部分还是手工完成,进而带来了测试难度和工作量问题。描述了如何用Java和J2SE1.4来部分实现Web页面全球化的自动测试架构。     

基于树模型算法的动态网页信息抽取研究和实现

动态网页是Internet上重要的网页类型,它们通常是由网站的后台数据库通过某种通用的模板构成.提出了一种新的基于树模型算法的动态网页信息抽取方法.它在已有算法和系统的基础上,进行了多方面的扩充.实验表明,这种基于树模型的抽取方法能够准确地定位和抽取动态网页信息.     

动态可靠性约束的多阶段测试资源分配研究

为满足测试资源分配过程中用户对软件可靠性的需求,构建一种动态可靠性约束的多阶段多目标测试资源分配模型DRC-MSMOTRA。从理论上分析不同阶段满足可靠性约束的测试时间下限并设计相应的种群初始化策略,结合参数估计、加权归一化方法和多目标差分进化,提出一种动态可靠性约束的多阶段多目标测试资源分配算法MS-DRC-GDE3。实验结果表明,与MSMOTRA模型相比,DRC-MSMOTRA模型在2种不同规模的软件系统上所获解的覆盖值分别提高约62和59个百分点,与MS-GDE3算法相比,MS-DRC-GDE3算法在2种软件系统上所获解的覆盖值分别提高约69和80个百分点,即所提模型和算法能够根据用户对可靠性的需求来为用户提供更多更优的测试资源分配方案。     

一种基于文本样式的Web主题信息提取方法研究

考虑Web页面表现形式对主题相关度的影响,提出了一个基于文本样式的Web主题提取算法。该算法解析Web页面中的文本样式,根据不同的文本样式来计算文本的重要度,选取重要度较高的文本作为该页面的主题。算法无须对页面进行复杂的结构分析,也避免了模板需要人工手动配置或训练的繁琐问题,具有较强的通用性。通过对十大类网站的一百个网页的测试,结果表明该算法具有较高的准确度。     

Unit Test Data Generation for C Using Rule-Directed Symbolic Execution

Unit testing is widely used in software development. One important activity in unit testing is automatic test data generation. Constraint-based test data generation is a technique for automatic generation of test data, which uses symbolic execution to generate constraints. Unit testing only tests functions instead of the whole program, where individual functions typically have preconditions imposed on their inputs. Conventional symbolic execution cannot detect these preconditions, let alone converting these preconditions into constraints. To overcome these limitations, we propose a novel unit test data generation approach using rule-directed symbolic execution for dealing with functions with missing input preconditions. Rule-directed symbolic execution uses predefined rules to detect preconditions in the individual function, and generates constraints for inputs based on preconditions. We introduce implicit constraints to represent preconditions, and unify implicit constraints and program constraints into integrated constraints. Test data generated based on integrated constraints can explore previously unreachable code and help developers find more functional faults and logical faults. We have implemented our approach in a tool called CTS-IC, and applied it to real-world projects. The experimental results show that rule-directed symbolic execution can find preconditions (implicit constraints) automatically from an individual function. Moreover, the unit test data generated by our approach achieves higher coverage than similar tools and efficiently mitigates missing input preconditions problems in unit testing for individual functions.

     

参数配对及n-way组合覆盖算法研究

组合测试是软件测试数据生成研究的一个重要领域,其中参数配对组合测试的应用最为广泛.对常用的参数配对组合覆盖方法进行了综述分析.目前主流的配对覆盖算法AETG和IPO所存在的主要问题是在确定水平取值时,具有盲目性和随机性,从而难以控制测试用例的规模.为此提出了改进的AETG算法和IPO算法,改进算法通过对参数进行预处理以及综合考虑各因素的水平组合等手段,对测试用例的规模进行控制,采用更加完备的方法尽早确定水平取值.为验证新算法的有效性,进行了仿真实验和实际测试,结果表明,改进算法所生成的测试用例数量要少于原算法,测试用例约减效果更为明显;测试用例数与配对数之间、测试用例数与因素水平数之间存在着某些规律性的联系,分析得出了一系列相关的结论.在配对覆盖的基础上,提出了遗传算法与AETG算法相结合的n-way组合覆盖算法,证明了其时间复杂性较已有算法得到了改善.     

一种约束求解的Web应用测试数据生成与筛选方法

传统基于随机算法、约束求解以及面向白盒测试的测试数据生成方法往往忽略了测试数据与数据库系统之间的依赖关系,同时并不适用于数据复用、Web应用测试。提出一种面向业务流程数据约束的测试数据生成与筛选方法,通过在Web业务流程模型中引入对测试数据的半形式化约束,利用数据池存储技术,并提高测试数据的复用性。通过案例表明,新的测试数据生成技术能够以较低的开销生成可用性高的测试数据集。