Per Erik Strandberg /cv /kurser /blog


This paper is published with Open Access, so you can download it from ACM here: [1] (or here: [2])

Informal summary

In this paper we improve the process of positioning a test case on a test system -- the "mapping". This is an important problem because we want most test cases to run on most test systems. We used graph theory, and in particular the subgraph isomorphism problem, as our approach. It was evaluated with more than ten thousand pairs of real test cases and test systems in use at the time of writing the paper.

One positive effect was to get the test case to "move around" on the test system over time, so that we get better topology coverage and better resource usage. Here is an image from the presentation of the paper that illustrates the goal:


Communication devices such as routers and switches play a critical role in the reliable functioning of embedded system networks. Dozens of such devices may be part of an embedded system network, and they need to be tested in conjunction with various computational elements on actual hardware, in many different configurations that are representative of actual operating networks. An individual physical network topology can be used as the basis for a test system that can execute many test cases, by identifying the part of the physical network topology that corresponds to the configuration required by each individual test case. Given a set of available test systems and a large number of test cases, the problem is to determine for each test case, which of the test systems are suitable for executing the test case, and to provide the mapping that associates the test case elements (the logical network topology) with the appropriate elements of the test system (the physical network topology).

We studied a real industrial environment where this problem was originally handled by a simple software procedure that was very slow in many cases, and also failed to provide thorough coverage of each network’s elements. In this paper, we represent both the test systems and the test cases as graphs, and develop a new prototype algorithm that a) determines whether or not a test case can be mapped to a subgraph of the test system, b) rapidly finds mappings that do exist, and c) exercises diverse sets of network nodes when multiple mappings exist for the test case. The prototype has been implemented and applied to over 10,000 combinations of test cases and test systems, and reduced the computation time by a factor of more than 80 from the original procedure. In addition, relative to a meaningful measure of network topology coverage, the mappings achieved an increased level of thoroughness in exercising the elements of each test system.

Source, Cite

Some source code for non-company-specific parts of the implementation: [3]

Cite with bibtex:

  title={Automated test mapping and coverage for network topologies},
  author={Strandberg, Per Erik and Ostrand, Thomas J and Weyuker, Elaine J and Sundmark, Daniel and Afzal, Wasif},
  booktitle={Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis},
  url = {}

Belongs to Kategori Publikationer