基于接口自动机的web服务行为过滤研究
|
摘要
一种新的软件形态—面向服务的计算(Service-Oriented Computing,SOC)正在蓬勃兴起,旨在解决互联网上各种应用之间的互操作问题。因为基于不同中间件开发的不同应用,加上通信机制各不相同,服务之间难以互相合作。为了使不同服务构成的系统可以实现互相合作,服务组合问题便成为国内外众多专家学者深入探讨的课题。
为了解决服务之间不兼容的问题,本文介绍了一种基于接口自动机的web服务行为过滤的途径,其基本思想是:在接口自动机这一理论框架下,利用一个算法解决基于场景的构件行为过滤问题,基于构件和服务的相似性,实现构件行为过滤方法在webservice中的应用。
本文介绍了接口自动机理论,扩展了其中环境的概念,用接口自动机为构件建立行为模型。利用条件排斥环境的算法,描述了如何从构件中剔除场景规约中描述的用户不想要的行为,同时还要对构件中用户想要的行为予以保留,即基于场景的构件行为过滤问题。通过构造条件排斥环境的方法,由场景规约描述的原构件中的用户不想要行为均不保留在构件与条件排斥环境的组合中,而用户想要行为则均被保留在构件与条件排斥环境的组合中。
本文实现了web service的业务流程可执行语言BPEL到接口自动机的转换,其目的是用接口自动机对服务组合的行为进行检验。接口自动机这一形式化工具,可以提高服务的适应性,弥补BPEL语言本身对服务行为刻画的不足。
A new form of software, service orented computing, is rising vigorously.It is used to solve the problem of multi-operation in the internet Because of the different uses based on the different middleware, the communication mechanism isn't the same,the co-operation between the services are difficult.In order to make the system which composed by different services to realize co-operation,the problem of service composition becomes the subject which many experts and scholars from home and abroard discussed.
In order to solve the problem of uncompatible services, the paper introduces a method which is called filtering services' act based on interface automaton.The basic idea is: based on the theoretical framework of interface automaton, introducing an algorithm to filter the behavior of components based on scenes. Based on the similarity of component and service, achieving the filtering methods of component is applicated in web service.
This paper introduces the theory of interface automaton, extends it in the concept of environment. It uses interface automaton (1A) to model the behavior of components. Using the algorithm of conditional exclusive environment ,the paper descripes that how to discard the users' undesired behavior and preserve the desired behavior in components according to scenario specifications, i.e., the scenario-based components behavior filtration. For solving this problem, it introduces the conditional exclusive environment (CXE). All undesired behavior, specified by one scenario, of the component is removed in the composition of the component and the CXE. At the same time, all desired behavior, specified by the other scenario, of the component is preserved in the composition of the component and the CXE.
The paper realizes the transition from business process execution language to interface automaton. The purpose of the transition is using IA to verificate the service composition. As one formal tool, interface automaton, it can improve the adaptability of web service, fech up the deficiency which BPEL depicts the behavior of web service.
为了解决服务之间不兼容的问题,本文介绍了一种基于接口自动机的web服务行为过滤的途径,其基本思想是:在接口自动机这一理论框架下,利用一个算法解决基于场景的构件行为过滤问题,基于构件和服务的相似性,实现构件行为过滤方法在webservice中的应用。
本文介绍了接口自动机理论,扩展了其中环境的概念,用接口自动机为构件建立行为模型。利用条件排斥环境的算法,描述了如何从构件中剔除场景规约中描述的用户不想要的行为,同时还要对构件中用户想要的行为予以保留,即基于场景的构件行为过滤问题。通过构造条件排斥环境的方法,由场景规约描述的原构件中的用户不想要行为均不保留在构件与条件排斥环境的组合中,而用户想要行为则均被保留在构件与条件排斥环境的组合中。
本文实现了web service的业务流程可执行语言BPEL到接口自动机的转换,其目的是用接口自动机对服务组合的行为进行检验。接口自动机这一形式化工具,可以提高服务的适应性,弥补BPEL语言本身对服务行为刻画的不足。
A new form of software, service orented computing, is rising vigorously.It is used to solve the problem of multi-operation in the internet Because of the different uses based on the different middleware, the communication mechanism isn't the same,the co-operation between the services are difficult.In order to make the system which composed by different services to realize co-operation,the problem of service composition becomes the subject which many experts and scholars from home and abroard discussed.
In order to solve the problem of uncompatible services, the paper introduces a method which is called filtering services' act based on interface automaton.The basic idea is: based on the theoretical framework of interface automaton, introducing an algorithm to filter the behavior of components based on scenes. Based on the similarity of component and service, achieving the filtering methods of component is applicated in web service.
This paper introduces the theory of interface automaton, extends it in the concept of environment. It uses interface automaton (1A) to model the behavior of components. Using the algorithm of conditional exclusive environment ,the paper descripes that how to discard the users' undesired behavior and preserve the desired behavior in components according to scenario specifications, i.e., the scenario-based components behavior filtration. For solving this problem, it introduces the conditional exclusive environment (CXE). All undesired behavior, specified by one scenario, of the component is removed in the composition of the component and the CXE. At the same time, all desired behavior, specified by the other scenario, of the component is preserved in the composition of the component and the CXE.
The paper realizes the transition from business process execution language to interface automaton. The purpose of the transition is using IA to verificate the service composition. As one formal tool, interface automaton, it can improve the adaptability of web service, fech up the deficiency which BPEL depicts the behavior of web service.
引文
[1] Michael N. Huhns, Munindar P. Singh. Service-Oriented Computing: Key Concepts and Principles. IEEE Internet Computing. January/February 2005, 9(1):75-81
[2] Edward A. Lee, Yuhong Xiong. Behavioral Types for Component-Based Design. Technical Memorandum UCB/ERL M02/29, University of California, Berkeley, California 94720, USA, September 2002
[3] Ernesto Wandeler, JAorn W. Janneck, Edward A. Lee, Lothar Thiele. Counting Interface Automata and their Application in Static Analysis of Actor Models. In Proceedings of the 3rd IEEE International Conference on Software Engineering and Formal Methods (SEFM2005). Los Alamitos, California: IEEE Computer Society,2005,106-116
[4] Yanjun Wen, JiWang, Zhichang Qi. Bridging Refinement of Interface Automata to Forward Simulation of I/O Automata. In Proceedings of the 6th International Conference on Formal Engineering Method (ICFEM 2004). Vol.3308 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2004, 259-273
[5] Purandar Bhaduri. Synthesis of Interface Automata. In Proceedings of the 3rd International Symposium on Automated Technology for Verification and Analysis (ATVA 2005). Vol. 3707 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2005, 338-353
[6] Luca de Alfaro, Thomas A. Henzinger. Timed Interfaces. In Proceedings of the 2nd International Conference on Embedded Software (EMSOFT 2002). Vol. 2491 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2002,108-122
[7] Arindam Chakrabarti, Luca de Alfaro, Thomas A. Henzinger. Resource Interfaces. In Proceedings of the 3rd International Conference on Embedded Software (EMSOFT 2003). Vol. 2855 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2003,117-133
[8] Dirk Beyer, Arindam Chakrabarti, Thomas A. Henzinger. Web Service Interfaces. In Proceedings of the 14th International World Wide Web Conferences (WWW 2005). New York: ACM Press,2005,148-159
[9] Howard Smith, Peter Fingar. Workflow is just a Pi process. 2003. URL http://www. bpm3. com/picalculus
[10] Khodakaram Salimifard, Mike Wright. Petri net-based modelling of workflow systems: An overview. European Journal of Operational Research. November 2001,134(3):664-676
[11] W.M. P. van der Aalst. Workflow Patterns. Distributed and Parallel Databases. July 2003,14(1):5-51
[12] Jun Han. Interaction Compatibility: An Essential Ingredient for Service Composition. In Proceedings of the 2nd International Workshop on Grid and Cooperative Computing (GCC 2003) [172], 59-66
[13] Daniela Berardi, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Massimo Mecella. Automatic Composition of E-services That Export Their Behavior. In Proceedings of the 1st International Conference on Service Oriented Computing (ICSOC 2003). Vol.2910 of Lecture Notes in Computer Science. Berlin Heidelberg New York:Springer-Verlag, 2003, 43-58
[14] Yuji Sakata, Kazutoshi Yokoyama, Shigeyuki Matsuda. A Method for Composing Process of Non-deterministic Web Services. In Proceedings of the IEEE International Conference on Web Services (ICWS' 04) [113], 436-443
[15] Prashant Doshi, Richard Goodwin, Rama Akkiraju. Dynamic Workflow Composition using Markov Decision Processes. In Proceedings of the IEEE International Conference on Web Services (ICWS'04) [113], 576-582
[16] Mercedes Amor, Lidia Fuentes. Troya. Putting Together Web Services and Compositional Software Agents. (Editors) Proceedings of International Conference on Web Engineering (ICWE 2003). Vol.2722 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2003, 44-53
[17] Jun-Jang Jeng, Wang-Chuan Tsai. Designing An FSM Architectural Framework for Service-Based Applications. In Proceedings of the 24th International Computer Software and Applications Conference (COMPSAC 2000). Los Alamitos, California: IEEE Computer Society, 2000, 234-242
[18] Daniela Berardi, Diego Calvanese, Giuseppe De Giacomo, Richard Hull. Automatic Composition of Transition-based Semantic Web Services with Messaging.In Proceedings of the 31st International Conference on Very Large Data Bases(VLDB 2005).New York:ACM Press,2005,613-624
[19]Xiang Fu.Formal Specifcation and Verification of Asynchronously Communicating Web Services.Ph.D.thesis,University of California,Santa Barbara,California,September 2004
[20]Luca de Alfaro,Thomas A.Henzinger.Interface Automata.In Proceedings of the 9~(th)Annuat ACM Symposium on Foundations of Software Engineering(FSE 2001).New York:ACM Press,2001,109-120
[21]ErichGr(?)el,Wolfgang Thomas,Thomas Wilke.Automata,Logics,and Infinite Games:h Guide to Current Research,Vol.2500 of Lecture Notes in Computer Science.Springer-Verlag,2000
[22][美]John E.Hopcroft著.刘田,姜晖译.自动机理论、语言和计算导论.机械工业出版社.2004.6
[23]张岩,胡军.接口自动机-一种用于组件组合的形式系统.计算机科学.Vol.32No.11 2005
[24]程烨,高建华.基于有穷自动机的面向对象软件规约的测试.计算机工程.VoL33No.5 2007.3
[25]文艳军,王戟.一种接口自动机的组合精化检验方法.计算机工程与科学.Vol.28,No.4,2006
[26]张岩,胡军.场景驱动的构件行为抽取.软件学报.Vol.18,No.1 January 2007
[27]李景峰.UML顺序图的形式化描述.计算机科学.Vol.29 NO.6 2002
[28]黄陇,于洪敏.基于UML顺序图的测试场景自动生成研究.计算机应用与软件.Vol.23,No.4 Apr.2006
[29]蔡敏.UML基础与Rose建模教程.人民邮电出版社.2006
[30]李青山.消息序列图模式抽取与组合.系统工程与电子技术.Vol26.9 2004
[31]雷斌.SDT:一个面向场景规约的运行时测试工具.计算机科学.Vol.33 NO.1 2006
[32]周培德著.算法设计与分析.机械工业出版社.1992.5
[33]中国科学院成都计算机应用研究所编著.常用算法及应用教程.中国铁道出版社.1993.9
[34][美]Robert Sedgewick著.算法:C语言实现.机械工业出版社.2006.9
[35][美]Thomas H.Cormen编著.算法导论.高等教育出版社.2002.5
[36]王晓东编著.算法设计与分析.清华大学出版社.2003.1
[37]Jun Hu,Xiaofeng Yu,Yah Zhang,Tian Zhang,Linzhang Wang,Xuandong Li,Guoliang Zheng.Scenario-based Verification for Component-based Embedded Software Designs.In Proceedings of the 34th International Conference on Parallel Processing Workshops(ICPP 2005 Workshop).Los Alamitos,California:IEEE Computer Society,2005,240-247
[38]张德富编著.算法设计与分析:高级教程.国防工业出版社.2007.2
[39][美]Anany Levitin著.潘彦译.算法设计与分析基础.清华大学出版社.2007
[40]Jon Kleinberg.算法设计.清华大学出版社.2006
[41]刘智伟.协同动态工作流引擎的研究.昆明理工大学硕士学位论文.2007
[42]于守健,李卫民.BPEL中基于有限状态自动机的Web服务自动组合.小型微型计算机系统.Vol.28 No.4 2007
[43]张帆,杨文军.Web服务组装语言的研究.计算机工程与应用.2006.18
[44]杜林春.基于BPEL4WS的web服务组合.铁路计算机应用.Vol16.7 2007.7
[45]Mark Kennedy.Oracle(?)BPEL Process Manager Order Booking Tutorial,10g Release 2(10.1.2).Oracle Corporation,Redwood City,August 2005.URL http://download,oracle,com/otndocs/products/bpel/orderbooking,pd
[46]袁崇义.Petri网原理与应用.电子工业出版社.2005
[2] Edward A. Lee, Yuhong Xiong. Behavioral Types for Component-Based Design. Technical Memorandum UCB/ERL M02/29, University of California, Berkeley, California 94720, USA, September 2002
[3] Ernesto Wandeler, JAorn W. Janneck, Edward A. Lee, Lothar Thiele. Counting Interface Automata and their Application in Static Analysis of Actor Models. In Proceedings of the 3rd IEEE International Conference on Software Engineering and Formal Methods (SEFM2005). Los Alamitos, California: IEEE Computer Society,2005,106-116
[4] Yanjun Wen, JiWang, Zhichang Qi. Bridging Refinement of Interface Automata to Forward Simulation of I/O Automata. In Proceedings of the 6th International Conference on Formal Engineering Method (ICFEM 2004). Vol.3308 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2004, 259-273
[5] Purandar Bhaduri. Synthesis of Interface Automata. In Proceedings of the 3rd International Symposium on Automated Technology for Verification and Analysis (ATVA 2005). Vol. 3707 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2005, 338-353
[6] Luca de Alfaro, Thomas A. Henzinger. Timed Interfaces. In Proceedings of the 2nd International Conference on Embedded Software (EMSOFT 2002). Vol. 2491 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2002,108-122
[7] Arindam Chakrabarti, Luca de Alfaro, Thomas A. Henzinger. Resource Interfaces. In Proceedings of the 3rd International Conference on Embedded Software (EMSOFT 2003). Vol. 2855 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2003,117-133
[8] Dirk Beyer, Arindam Chakrabarti, Thomas A. Henzinger. Web Service Interfaces. In Proceedings of the 14th International World Wide Web Conferences (WWW 2005). New York: ACM Press,2005,148-159
[9] Howard Smith, Peter Fingar. Workflow is just a Pi process. 2003. URL http://www. bpm3. com/picalculus
[10] Khodakaram Salimifard, Mike Wright. Petri net-based modelling of workflow systems: An overview. European Journal of Operational Research. November 2001,134(3):664-676
[11] W.M. P. van der Aalst. Workflow Patterns. Distributed and Parallel Databases. July 2003,14(1):5-51
[12] Jun Han. Interaction Compatibility: An Essential Ingredient for Service Composition. In Proceedings of the 2nd International Workshop on Grid and Cooperative Computing (GCC 2003) [172], 59-66
[13] Daniela Berardi, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Massimo Mecella. Automatic Composition of E-services That Export Their Behavior. In Proceedings of the 1st International Conference on Service Oriented Computing (ICSOC 2003). Vol.2910 of Lecture Notes in Computer Science. Berlin Heidelberg New York:Springer-Verlag, 2003, 43-58
[14] Yuji Sakata, Kazutoshi Yokoyama, Shigeyuki Matsuda. A Method for Composing Process of Non-deterministic Web Services. In Proceedings of the IEEE International Conference on Web Services (ICWS' 04) [113], 436-443
[15] Prashant Doshi, Richard Goodwin, Rama Akkiraju. Dynamic Workflow Composition using Markov Decision Processes. In Proceedings of the IEEE International Conference on Web Services (ICWS'04) [113], 576-582
[16] Mercedes Amor, Lidia Fuentes. Troya. Putting Together Web Services and Compositional Software Agents. (Editors) Proceedings of International Conference on Web Engineering (ICWE 2003). Vol.2722 of Lecture Notes in Computer Science. Berlin Heidelberg New York: Springer-Verlag, 2003, 44-53
[17] Jun-Jang Jeng, Wang-Chuan Tsai. Designing An FSM Architectural Framework for Service-Based Applications. In Proceedings of the 24th International Computer Software and Applications Conference (COMPSAC 2000). Los Alamitos, California: IEEE Computer Society, 2000, 234-242
[18] Daniela Berardi, Diego Calvanese, Giuseppe De Giacomo, Richard Hull. Automatic Composition of Transition-based Semantic Web Services with Messaging.In Proceedings of the 31st International Conference on Very Large Data Bases(VLDB 2005).New York:ACM Press,2005,613-624
[19]Xiang Fu.Formal Specifcation and Verification of Asynchronously Communicating Web Services.Ph.D.thesis,University of California,Santa Barbara,California,September 2004
[20]Luca de Alfaro,Thomas A.Henzinger.Interface Automata.In Proceedings of the 9~(th)Annuat ACM Symposium on Foundations of Software Engineering(FSE 2001).New York:ACM Press,2001,109-120
[21]ErichGr(?)el,Wolfgang Thomas,Thomas Wilke.Automata,Logics,and Infinite Games:h Guide to Current Research,Vol.2500 of Lecture Notes in Computer Science.Springer-Verlag,2000
[22][美]John E.Hopcroft著.刘田,姜晖译.自动机理论、语言和计算导论.机械工业出版社.2004.6
[23]张岩,胡军.接口自动机-一种用于组件组合的形式系统.计算机科学.Vol.32No.11 2005
[24]程烨,高建华.基于有穷自动机的面向对象软件规约的测试.计算机工程.VoL33No.5 2007.3
[25]文艳军,王戟.一种接口自动机的组合精化检验方法.计算机工程与科学.Vol.28,No.4,2006
[26]张岩,胡军.场景驱动的构件行为抽取.软件学报.Vol.18,No.1 January 2007
[27]李景峰.UML顺序图的形式化描述.计算机科学.Vol.29 NO.6 2002
[28]黄陇,于洪敏.基于UML顺序图的测试场景自动生成研究.计算机应用与软件.Vol.23,No.4 Apr.2006
[29]蔡敏.UML基础与Rose建模教程.人民邮电出版社.2006
[30]李青山.消息序列图模式抽取与组合.系统工程与电子技术.Vol26.9 2004
[31]雷斌.SDT:一个面向场景规约的运行时测试工具.计算机科学.Vol.33 NO.1 2006
[32]周培德著.算法设计与分析.机械工业出版社.1992.5
[33]中国科学院成都计算机应用研究所编著.常用算法及应用教程.中国铁道出版社.1993.9
[34][美]Robert Sedgewick著.算法:C语言实现.机械工业出版社.2006.9
[35][美]Thomas H.Cormen编著.算法导论.高等教育出版社.2002.5
[36]王晓东编著.算法设计与分析.清华大学出版社.2003.1
[37]Jun Hu,Xiaofeng Yu,Yah Zhang,Tian Zhang,Linzhang Wang,Xuandong Li,Guoliang Zheng.Scenario-based Verification for Component-based Embedded Software Designs.In Proceedings of the 34th International Conference on Parallel Processing Workshops(ICPP 2005 Workshop).Los Alamitos,California:IEEE Computer Society,2005,240-247
[38]张德富编著.算法设计与分析:高级教程.国防工业出版社.2007.2
[39][美]Anany Levitin著.潘彦译.算法设计与分析基础.清华大学出版社.2007
[40]Jon Kleinberg.算法设计.清华大学出版社.2006
[41]刘智伟.协同动态工作流引擎的研究.昆明理工大学硕士学位论文.2007
[42]于守健,李卫民.BPEL中基于有限状态自动机的Web服务自动组合.小型微型计算机系统.Vol.28 No.4 2007
[43]张帆,杨文军.Web服务组装语言的研究.计算机工程与应用.2006.18
[44]杜林春.基于BPEL4WS的web服务组合.铁路计算机应用.Vol16.7 2007.7
[45]Mark Kennedy.Oracle(?)BPEL Process Manager Order Booking Tutorial,10g Release 2(10.1.2).Oracle Corporation,Redwood City,August 2005.URL http://download,oracle,com/otndocs/products/bpel/orderbooking,pd
[46]袁崇义.Petri网原理与应用.电子工业出版社.2005