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

Dongming Xiang; Guanjun Liu; Chungang Yan; Changjun Jiang

doi:10.1109/JAS.2017.7510766

Volume 5 Issue 1

Jan. 2018

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 11.8, Top 4% (SCI Q1)

CiteScore: 17.6, Top 3% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2018 > 5(1): 251-260

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

Citation:

PDF( 3449 KB)

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

doi: 10.1109/JAS.2017.7510766

Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 201804, China

Funds:

the National Key R& D Program of China 2017YFB1001804

Shanghai Science and Technology Innovation Action Plan Project 16511100900

More Information

Author Bio:
Dongming Xiang graduated from University of Jinan, China, in 2010. He received the M.S. degree from this university in 2013. He is currently working toward the Ph.D. degree in the Department of Computer Science and Technology, Tongji University. His research interests include model checking, Petri net, business process management, and service computing. (e-mail: flysky_xdm@163.com)

Guanjun Liu (M'2016) received the Ph.D. degree in computer software and theory from Tongji University, Shanghai, China, in 2011. He was a Postdoctoral Research Fellow at Singapore University of Technology and Design, Singapore, from 2011 to 2013. He worked at Humboldt-University zu Berlin, Germany, from 2013 to 2014 as a Postdoctoral Research Fellow supported by the Alexander von Humboldt Foundation. He is currently an Associate Professor with the Department of Computer Science and Technology, Tongji University. He has published 50+ papers. His research interests include Petri net theory, model checking, web service, workflow, discrete event systems, and information security. (e-mail: liugj1116@163.com)

Chungang Yan received the Ph.D. degree from Tongji University, Shanghai, China, in 2006. She is currently a Professor with the Department of Computer Science and Technology, Tongji University, Shanghai, China. Her current research interests include concurrent model and algorithm, Petri net theory, formal verification of software, and trusty theory on software process. She has published more than 30 papers in domestic and international academic journals and conference proceedings. (e-mail: yanchungang@tongji.edu.cn)

Changjun Jiang received the Ph.D. degree from the Institute of Automation, Chinese Academy of Science, Beijing, China, in 1995. He is currently the leader of the Key Laboratory of the Ministry of Education for Embedded System and Service Computing, Tongji University, Shanghai, China. He is an IET Fellow and an Honorary Professor with Brunel University London. He has published more than 300 papers in journals and conference proceedings, including Chinese Science, IEEE Transactions on Robotics and Automation, and IEEE Transactions on Fuzzy Systems. He has led over 30 projects supported by the National Natural Science Foundation of China, the National High Technology Research and Development Program of China, and the National Basic Research Developing Program of China. His research interests include concurrency theory, Petri nets, formal verification of software, cluster, grid technology, intelligent transportation systems, and service-oriented computing. Prof. Jiang has been the recipient of one international prize and seven prizes in the field of science and technology. (e-mail: cjjiang@tongji.edu.cn)
Corresponding author: Guanjun Liu, e-mail:liugj1116@163.com
Received Date: 2016-11-08
Accepted Date: 2017-01-16

Abstract

Abstract

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.
- Business process modeling,
- data-flow errors,
- Petri nets,
- reachability graph

FullText(HTML)

References(39)

References

[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

Supplements(0)

Cited By

Proportional views

Proportional views

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

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

Figures(10) / Tables(7)

Get Citation

PDF

XML

Article Metrics

Article views (1371) PDF downloads(209)

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

doi: 10.1109/JAS.2017.7510766

Abstract

References

Proportional views

Catalog

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

Article Metrics

Export File

Citation

Format

Content