GraphSeq: a Graph Matching tool for the extraction of mobility patterns

Author(s): Minh Duc Nguyen, Helene Waeselynck, Nicolas Riviere
Venue: 2010 Third International Conference on Software Testing, Verification and Validation
Date: 2010

Type of Experiement: Survey/Multi-Case Study
Class/Experience Level: Undergraduate Student
Data Collection Method: Observation, Project Artifact(s)


This paper introduces GraphSeq, a graph-matching tool that can be used in the testing of mobile networks. Wireless networks are different from traditional wired networks in a couple key ways. The first is that the topology of the network configuration changes dynamically as mobility induced connections and disconnections are made to different nodes when they come in or go out of range. The second is the communication with unknown partners in a given context. The dynamic nature of these networks makes them difficult to test and verify. GraphSeq provides a method to analyze and test dynamically reconfigurable networks as a comparison of a sequence of graphs.

GraphSeq uses graph homomorphism to compare a concrete configuration with a scenario configuration and distinguishes failures or inconsistencies in the system or protocol. Importantly, GraphSeq introduces sequential graph comparisons and takes into account the random appearance and disappearance of nodes. Its algorithm relies on graph homomorphism and traversal. More detailed information about the algorithm can be found inside the paper. GraphSeq cannot process large sequences of graphs due to its exponential run time in some areas. The duration of a test from 5 to 50 nodes can run from 28s to 15 minutes respectively.

A case study was conducted by testing against the Group Membership Protocol (GMP). The test involved recording execution traces and finding scenario variants. The tests reported many protocol violations successfully. Later, GraphSeq is tested with a mobility simulator to demonstrate its real-world usage by factoring in distance and velocity measures. The creators of GraphSeq are now working on an automated analysis framework.