Workflow difference detection based on basis paths. (May 2019)

• Record Type: Journal Article
• Authors: Cao, Bin; Hong, Feng; Wang, Jiaxing; Fan, Jing; Lv, Mingqi
• Is Part Of: Engineering applications of artificial intelligence. Volume 81(2019)
• Page Start: 420
• Page End: 427
• Publication Date: 2019-05
• Subjects: Workflow model -- Difference detection -- Behavioral difference -- Basis paths; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2019.03.009
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: Detecting workflow difference is meaningful for many applications, e.g., in-vehicle system testing. However, current workflow difference detection methods stress on structural differences while ignoring the behavioral aspects of the workflow models. Due to the large number of possible behaviors for a workflow model, it is challenging to detect the behavioral difference. To address this problem, this paper introduces the idea of basis path testing from the software testing field, and presents an efficient method for detecting the workflow difference in terms of their behaviors. First, we compute the cyclomatic complexity according to the number of nodes and arcs in the workflow model. Then, based on the cyclomatic complexity we design an algorithm that can retrieve the basis paths from a tree structure converted from the workflow model. At last, the Kuhn–Munkres (KM) algorithm is used to map the independent paths from two workflow models and generate the optimal mapping that the overall distance is the minimum. The experimental evaluation shows that our proposed method has been proved feasible in terms of both efficiency and effectiveness.