A Formal Logic Approach to Constrained Combinatorial Testing

Combinatorial testing is as an effective testing technique to reveal failures in a given system, based on input combinations coverage and combinatorial optimization. Combinatorial testing of strength t (t ≥ 2) requires that each t-wise tuple of values of the different system input parameters is covered by at least one test case. Combinatorial test suite generation algorithms aim at producing a test suite covering all the required tuples in a small (possibly minimal) number of test cases, in order to reduce the cost of testing. The most used combinatorial technique is the pairwise testing (t = 2) which requires coverage of all pairs of input values. Constrained combinatorial testing takes also into account constraints over the system parameters, for instance forbidden tuples of inputs, modeling invalid or not realizable input values combinations. In this paper a new approach to combinatorial testing, tightly integrated with formal logic, is presented. In this approach, test predicates are used to formalize combinatorial testing as a logical problem, and an external formal logic tool is applied to solve it. Constraints over the input domain are expressed as logical predicates too, and effectively handled by the same tool. Moreover, inclusion or exclusion of select tuples is supported, allowing the user to customize the test suite layout. The proposed approach is supported by a prototype tool implementation and results of experimental assessment are also presented.     

A meta-index for querying distributed moving object database servers

Distributed moving object database servers offer a feasible solution to the scalability problems of centralized database systems. In these potentially large-scale systems, querying about the time-varying location of specific moving objects can be particularly expensive in terms of running time. This work proposes a meta-index   based strategy that can significantly speed up the processing of these queries. The meta-index acts as an entry point for spatio-temporal queries and quickly drives the search process to the database servers that contain solutions. It also enables very fast approximated solutions to queries such as top-k$k$ and spatio-temporal range queries.     

A real-time versatile roadway path extraction and tracking on an FPGA platform

This paper presents an algorithm for roadway path extraction and tracking and its implementation in a Field Programmable Gate Array (FPGA) device. The implementation is particularly suitable for use as a core component of a Lane Departure Warning (LDW) system, which requires high-performance digital image processing as well as low-cost semiconductor devices, appropriate for the high volume production of the automotive market. The FPGA technology proved to be a proper platform to meet these two contrasting requirements. The proposed algorithm is specifically designed to be completely embedded in FPGA hardware to process wide VGA resolution video sequences at 30 frames per second. The main contributions of this work lie in (i) the proper selection, customization and integration of the main functions for road extraction and tracking to cope with the addressed application, and (ii) the subsequent FPGA hardware implementation as a modular architecture of specialized blocks. Experiments on real road scenario video sequences running on the FPGA device illustrate the good performance of the proposed system prototype and its ability to adapt to varying common roadway conditions, without the need for a per-installation calibration procedure.     

Secure electronic bills of lading: blind counts and digital signatures

Electronic documents used in the framework of the goods delivery industry—i.e. electronic bills of lading (e-BOLs)—are the enablers of any payment, and therefore exposed to frauds. As of today, e-BOLs are handled by special private companies, which provide paperless trading services through their trade chains. This paper contributes a zero-knowledge open solution to the problem of designing secure electronic bills of lading, in the framework of a shipper-carrier-buyer transmission model. The suggested solution is a cryptographic protocol based on digital signatures and blind merchandise counts—that is, counts that do not reveal any information about actually counted quantities. The model is designed to mitigate a number of security threats and assumes the existence of both a trusted third party and a bank in charge of payment procedures. The paper discusses the drawbacks of the existing proprietary solutions and shows how the suggested open protocol addresses them.     

A numerical procedure for predicting the performance of high pressure homogenizing valves

This paper describes a numerical procedure for the prediction of the homogenizing performance of high pressure homogenizing valves used in diary plants. The method is based on a strict interaction between a complex CFD code and a simple homogenizing simulation code developed by the authors. This latter implements a mathematical model for the evaluation of droplets break-up, that needs an accurate evaluation of few significant fluid dynamic parameters in the whole fluid dynamic domain inside the valve. Due to the relevant pressure gradients within the flow and to the possibility of cavitation, particular attention has been paid in defining the fluid model, the mesh and the parameters required for CFD simulations. Notwithstanding the quite simple model of the homogenizing process, comparatively with the complexity of phenomena involved, the first results obtained are in general agreement with the experimental data available. These results point out the potential of the procedure proposed as a starting point for further implementation of more complex effects.     

Automated GUI performance testing

A significant body of prior work has devised approaches for automating the functional testing of interactive applications. However, little work exists for automatically testing their performance. Performance testing imposes additional requirements upon GUI test automation tools: the tools have to be able to replay complex interactive sessions, and they have to avoid perturbing the application’s performance. We study the feasibility of using five Java GUI capture and replay tools for GUI performance test automation. Besides confirming the severity of the previously known GUI element identification problem, we also describe a related problem, the temporal synchronization problem, which is of increasing importance for GUI applications that use timer-driven activity. We find that most of the tools we study have severe limitations when used for recording and replaying realistic sessions of real-world Java applications and that all of them suffer from the temporal synchronization problem. However, we find that the most reliable tool, Pounder, causes only limited perturbation and thus can be used to automate performance testing. Based on an investigation of Pounder’s approach, we further improve its robustness and reduce its perturbation. Finally, we demonstrate in a set of case studies that the conclusions about perceptible performance drawn from manual tests still hold when using automated tests driven by Pounder. Besides the significance of our findings to GUI performance testing, the results are also relevant to capture and replay-based functional GUI test automation approaches.     

A heuristic approach for packing identical rectangles in convex regions

In this paper we propose a heuristic approach for the problem of packing equal rectangles within a convex region. The approach is based on an Iterated Local Search scheme, in which the key step is the perturbation move. Different perturbation moves, both combinatorial and continuous ones, are proposed and compared through extensive computational experiments on a set of test instances. The overall results are quite encouraging.     

Computing integrals over polynomially defined regions and their boundaries in 2 and 3 dimensions

We use the cylindrical algebraic decomposition algorithms implemented in Mathematica to produce procedures to analytically compute integrals over polynomially defined regions and their boundaries in two and three dimensions. Using these results, we can implement the divergence theorem in three dimensions or the Green's theorems in two dimensions. These theorems are of central importance in the applications of multidimensional integration. They also provide a strong correctness test for the implementation of our results in a computer algebra system. The resulting software can solve many of the two and some of the three dimensional integration problems in vector calculus textbooks. The three dimensional results are being extended. The results in this paper are being included in an automated student assistant for vector calculus.