A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 5 Issue 1
Jan.  2018

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 6.171, Top 11% (SCI Q1)
    CiteScore: 11.2, Top 5% (Q1)
    Google Scholar h5-index: 51, TOP 8
Turn off MathJax
Article Contents
Dongming Xiang, Guanjun Liu, Chungang Yan and Changjun Jiang, "Detecting Data-flow Errors Based on Petri Nets With Data Operations," IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 251-260, Jan. 2018. doi: 10.1109/JAS.2017.7510766
Citation: Dongming Xiang, Guanjun Liu, Chungang Yan and Changjun Jiang, "Detecting Data-flow Errors Based on Petri Nets With Data Operations," IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 251-260, Jan. 2018. doi: 10.1109/JAS.2017.7510766

Detecting Data-flow Errors Based on Petri Nets With Data Operations

doi: 10.1109/JAS.2017.7510766
Funds:

the National Key R& D Program of China 2017YFB1001804

Shanghai Science and Technology Innovation Action Plan Project 16511100900

More Information
  • In order to guarantee the correctness of business processes, not only control-flow errors but also data-flow errors should be considered. The control-flow errors mainly focus on deadlock, livelock, soundness, and so on. However, there are not too many methods for detecting data-flow errors. This paper defines Petri nets with data operations (PN-DO) that can model the operations on data such as read, write and delete. Based on PN-DO, we define some data-flow errors in this paper. We construct a reachability graph with data operations for each PN-DO, and then propose a method to reduce the reachability graph. Based on the reduced reachability graph, data-flow errors can be detected rapidly. A case study is given to illustrate the effectiveness of our methods.

     

  • loading
  • [1]
    C. C. Dolean and R. Petrusel, "Data-flow modeling: a survey of issues and approaches, " Inf. Econ., vol. 16, no. 4, pp. 117-130, Oct. 2012. http://www.oalib.com/paper/2489639
    [2]
    W. M. Van Der Aalst, "Workflow verification: finding control-flow errors using petri-net-based techniques, " in Business Process Management: Models, Techniques, and Empirical Studies, W. van der Aalst, J. Desel, and A. Oberweis, Eds. Berlin Heidelberg, Germany: Springer, vol. 1806, pp. 161-183, 2000.
    [3]
    N. Trčka, W. M. P. Van der Aalst, and N. Sidorova, "Data-flow anti-patterns: Discovering data-flow errors in workflows, " in Proc. 21st Int. Conf. Advanced Information Systems Engineering, Heidelberg, Germany, 2009, pp. 425-439.
    [4]
    W. M. P. Aalst, K. M. Hee, A. H. M. Hofstede, N. Sidorova, H. M. W. Verbeek, M. Voorhoeve, and M. T. Wynn, "Soundness of workflow nets: classification, decidability, and analysis, " Formal Aspec. Comput., vol. 23, no. 3, pp. 333-363, 2011. doi: 10.1007/s00165-010-0161-4
    [5]
    G. J. Liu and C. J. Jiang, "Net-structure-based conditions to decide compatibility and weak compatibility for a class of inter-organizational workflow nets, " Sci. China Inf. Sci., vol. 58, no. 7, pp. 1-16, Jul. 2015. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jfxg201507011&dbname=CJFD&dbcode=CJFQ
    [6]
    H. S. Meda, A. K. Sen, and A. Bagchi, "On detecting data flow errors in workflows, " J. Data Inf. Qual., vol. 2, no. 1, Article No. 4, Jul. 2010. http://dl.acm.org/citation.cfm?id=1805290
    [7]
    S. Roy, A. S. M. Sajeev, S. Bihary, and A. Ranjan, "An empirical study of error patterns in industrial business process models, " IEEE Trans. Serv. Comput., vol. 7, no. 2, pp. 140-153, Apr. -Jun. 2014. http://ieeexplore.ieee.org/document/6464253/
    [8]
    S. G. Wang, M. D. Gan, and M. C. Zhou, "Macro liveness graph and liveness of omega-independent unbounded nets, " Sci. China Inf. Sci., vol. 58, no. 3, pp. 1-10, Mar. 2015. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jfxg201503010&dbname=CJFD&dbcode=CJFQ
    [9]
    S. Sadiq, M. Orlowska, and W. Sadiq, "Data flow and validation in workflow modelling, " in Proc. 15th Australasian Database Conf., Dunedin, New Zealand, 2004, pp. 207-214. http://dl.acm.org/citation.cfm?id=1012317
    [10]
    D. Sharma, S. Pinjala, and A. K. Sen, "Correction of data-flow errors in workflows, " in Proc. 25th Australasian Conf. Information Systems, Auckland, New Zealand, 2014.
    [11]
    X. T. Guo, S. X. Sun, and D. Vogel, "A dataflow perspective for business process integration, " ACM Trans Manage Inf. Syst., vol. 5, no. 4, Article No. 22, Mar. 2015.
    [12]
    S. X. Sun, J. L. Zhao, J. F. Nunamaker, and O. R. L. Sheng, "Formulating the data-flow perspective for business process management, " Inf. Syst. Res., vol. 17, no. 4, pp. 374-391, Dec. 2006. http://dl.acm.org/citation.cfm?id=1235156
    [13]
    H. S. Meda, A. K. Sen, and A. Bagchi, "Detecting data flow errors in workflows: A systematic graph traversal approach, " in Proc. 17th Annual Workshop on Information Technologies and Systems, Montreal, Canada, 2007. http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1328165
    [14]
    M. Varea, B. M. Al-Hashimi, L. A. Cortës, P. Eles, and Z. B. Peng, "Dual flow nets: modeling the control/data-flow relation in embedded systems, " ACM Trans. Embed. Comput. Syst., vol. 5, no. 1, pp. 54-81, Feb. 2006. http://dl.acm.org/citation.cfm?id=1132360
    [15]
    S. K. Fan, W. C. Dou, and J. J. Chen, "Dual workflow nets: mixed control/data-flow representation for workflow modeling and verification, " in Advances in Web and Network Technologies, and Information Management, K. C. C. Chang, W. Wang, L. Chen, C. A. Ellis, C. H. Hsu, A. C. Tsoi, and H. X. Wang, Eds. Heidelberg, Germany: Springer, vol. 4537, pp. 433-444, 2007.
    [16]
    A. Awad, G. Decker, and N. Lohmann, "Diagnosing and repairing data anomalies in process models, " in Business Process Management Workshops, S. Rinderle-Ma, S. Sadiq, and F. Leymann, Eds. Berlin, Heidelberg, Germany: Springer, vol. 43, pp. 5-16, 2009.
    [17]
    P. Baldan, A. Bruni, A. Corradini, B. König, C. Rodrïguez, and S. Schwoon, "Efficient unfolding of contextual Petri nets, " Theor. Comput. Sci. vol. 449, pp. 2-22, Aug. 2012. http://dl.acm.org/citation.cfm?id=2330480
    [18]
    U. Montanari and F. Rossi, "Contextual nets, " Acta Inf., vol. 32, no. 6, pp. 545-596, Jun. 1995.
    [19]
    R. Alur, R. K. Brayton, T. A. Henzinger, S. Qadeer, and S. K. Rajamani, "Partial-order reduction in symbolic state-space exploration, " in Proc. 9th Int. Conf. Computer Aided Verification, Berlin, Heidelberg, Germany, 1997, pp. 340-351. doi: 10.1007/3-540-63166-6_34
    [20]
    A. Lluch-Lafuente, S. Edelkamp, and S. Leue, "Partial order reduction in directed model checking, " in Proc. 9th Int. SPIN Workshop on Model Checking of Software, Grenoble, France, 2002, pp. 112-127. http://www.springerlink.com/index/tg30v4726p8qf2tf.pdf
    [21]
    A. Valmari and H. Hansen, "Can stubborn sets be optimal?, " in Proc. 31st Int. Conf. Applications and Theory of Petri Nets, Berlin, Heidelberg, Germany, 2010, pp. 43-62.
    [22]
    S. G. Wang, M. C. Zhou, Z. W. Li, and C. Y. Wang, "A new modified reachability tree approach and its applications to unbounded Petri nets". IEEE Trans. Syst. Man Cybern. Syst., vol. 43, no. 4, pp. 932-940, Jul. 2013. http://ieeexplore.ieee.org/document/6425512/
    [23]
    S. G. Wang, M. D. Gan, M. C. Zhou, and D. You, "A reduced reachability tree for a class of unbounded Petri nets, " IEEE/CAA J. Autom. Sin., vol. 2, no. 4, pp. 345-352, Oct. 2015. http://ieeexplore.ieee.org/document/7296528/
    [24]
    P. A. Bourdil, B. Berthomieu, S. D. Zilio, and F. Vernadat, "Symmetry reduced state classes for time Petri nets, " in Proc. 30th Annu. ACM Symp. Applied Computing, Salamanca, Spain, 2015, pp. 1751-1758.
    [25]
    M. Westergaard, L. M. Kristensen, G. S. Brodal, and L. Arge, "The ComBack method: extending hash compaction with backtracking, " in Proc. 28th Int. Conf. Application and Theory of Petri Nets, Berlin, Heidelberg, Germany, 2007, pp. 445-464. http://dl.acm.org/citation.cfm?id=1769081
    [26]
    G. J. Holzmann, "An analysis of bitstate hashing, " Formal Methods Syst. Des., vol. 13, no. 3, pp. 289-307, Nov. 1998. doi: 10.1023/A:1008696026254
    [27]
    S. Christensen, L. M. Kristensen, and T. Mailund, "A sweep-line method for state space exploration, " in Proc. 7th Int. Conf. Tools and Algorithms for the Construction and Analysis of Systems, Berlin, Heidelberg, Germany, 2001, pp. 450-464.
    [28]
    D. M. Xiang, G. J. Liu, C. G. Yan, and C. J. Jiang, "Checking the inconsistent data in concurrent systems by petri nets with data operations, " in Proc. IEEE 22nd Int. Conf. Parallel and Distributed Systems (ICPADS), Wuhan, China, 2016, pp. 501-508. http://ieeexplore.ieee.org/document/7823788/
    [29]
    W. Vogler, "Partial order semantics and read arcs, " in Proc. 22nd Int. Symp. Mathematical Foundations of Computer Science, Berlin, Heidelberg, Germany, 1997, pp. 508-517.
    [30]
    W. Vogler, "Efficiency of asynchronous systems and read arcs in Petri nets, " in Proc. 24th Int. Colloquium on Automata, Languages, and Programming, London, UK, 1998, pp. 538-548.
    [31]
    G. J. Liu, W. Reisig, C. J. Jiang, and M. C. Zhou, "A branching-processbased method to check soundness of workflow systems, " IEEE Access, vol. 4, pp. 4104-4118, Jan. 2016. http://ieeexplore.ieee.org/document/7527679/
    [32]
    W. Vogler, A. L. Semenov, and A. Yakovlev, "Unfolding and finite prefix for nets with read arcs, " in Proc. 9th Int. Conf. Concurrency Theory, London, UK, 1998, pp. 501-516. http://dl.acm.org/citation.cfm?id=701443
    [33]
    S. Christensen and N. D. Hansen, "Coloured Petri nets extended with place capacities, test arcs and inhibitor arcs, " in Proc. 14th Int. Conf. Application and Theory of Petri Nets, London, UK, vol. 691, pp. 186-205, 1993.
    [34]
    S. Bandinelli and A. Fuggetta, "Computational reflection in software process modeling: the SLANG approach, " in Proc. 15th Int. Conf. Software Engineering, Los Alamitos, CA, USA, 1993, pp. 144-154. http://dl.acm.org/citation.cfm?id=257604
    [35]
    L. Ma and J. P. Tsai, "Formal modeling and analysis of a secure mobileagent system, " IEEE Trans. Syst. Man Cybern. A Syst. Hum., vol. 38, no. 1, pp. 180-196, Jan. 2008.
    [36]
    J. Desel, V. Milijic, and C. Neumair, "Model validation in controller design, " in Lectures on Concurrency and Petri Nets, J. Desel, W. Reisig, and G. Rozenberg, Eds. Berlin Heidelberg, Germany: Springer, 2004, pp. 467-495.
    [37]
    C. X. Xu, W. L. Qu, H. P. Wang, Z. Z. Wang, and X. J. Ban, "A petri net-based method for data validation of web services composition, " in Proc. IEEE 34th Annu. Computer Software and Applications Conf., Washington, DC, USA, 2010, pp. 468-476. http://dl.acm.org/citation.cfm?id=1902089
    [38]
    B. Bonet, P. Haslum, V. Khomenko, S. Thiëbaux, and W. Vogler, "Recent advances in unfolding technique, " Theor. Comput. Sci., vol. 551, pp. 84-101, Sep. 2014.
    [39]
    J. Esparza, S. Römer, and W. Vogler, "An improvement of McMillanś unfolding algorithm, " Formal Methods Syst. Des., vol. 20, no. 3, pp. 285-310, May 2002. http://opus.bibliothek.uni-augsburg.de/opus4/frontdoor/index/index/docId/23667

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(10)  / Tables(7)

    Article Metrics

    Article views (1205) PDF downloads(205) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return