A bitwise - Based indexing and heuristic-driven on - the - fly approach for Web service composition and verification

twise-based indexing with heuristic-driven
on-the-fly composition and verification
316 35 0.155
EDS (100) Full schema verification 27,400 275 5.570
On-the-fly composition and verification 20,824 275 4.579
Heuristic-driven on-the-fly composition and verification 3021 151 3.294
Combined bitwise-based indexing with heuristic-driven
on-the-fly composition and verification
316 35 0.155
ECS (200) Full schema verification 102,800 515 28.198
On-the-fly composition and verification 76,586 515 23.030
Heuristic-driven on-the-fly composition and verification 8324 287 18.273
Combined bitwise-based indexing with heuristic-driven
on-the-fly composition and verification
316 35 0.155
Global (1000) Full schema verification Out-of-memory Out-of-memory Out-of-memory
On-the-fly composition and verification Out-of-memory Out-of-memory Out-of-memory
Heuristic-driven on-the-fly composition and verification 91,457 1429 597.228
Combined bitwise-based indexing with heuristic-driven
on-the-fly composition and verification
316 35 0.155
Fig. 6 Visual representation of the experimental results
123
124 Vietnam J Comput Sci (2017) 4:111–126
As expected result, where the execution time mostly
depends on the number of expanded states and visited states,
all of our proposed methods are faster than the original one in
existing work and our new proposed bitwise-based indexing
approach achieves the fastest execution time (Fig. 6c).
6 Related works
6.1 Web service composition and verification
Research community has a lot of work related to WSC prob-
lem, which can be classified into three groups as follows.
6.1.1 Composition based on hard constraints
WSC only involves the functional properties (hard con-
straints) which is the classic problem of SOA, which are
mostly based on the theory of planning of the artificial intel-
ligence field (AI Planning), such as [4] and [19]. Some recent
studies are based on abstract models, such as Petri net or Col-
ored Petri Net [12–14] to compose and verify Web services.
PORSCE II [4] is a framework implementing the WSC-based
on the requirements on input and output of the services. Sim-
ilarly, OWL-S-XPlan [19] also uses Web services expressed
by OWL-S to transform the problem from WSC domain to
planning domain and uses the planner named XPlan, con-
structed by author. The studies [12–14] give the automatic
WSC techniques based on Petri net (or Colored Petri net).
6.1.2 Composition based on hard and soft constraints
WSC method which combines functional properties (hard
constraints) and QoS properties (soft constraints) has been
proposed in [16]. In [16], the authors have proposed apply-
ing genetic algorithm (GA) to solve the problem with each
possible composition encoded as a gene, to calculate value
for specific kinds of QoS properties. However, this study
only provides us a mechanism to choose the best (possible)
composition from a set of composition ways (full compo-
sition schema) rather than composes from the component
Web services. Besides, the application of genetic algorithms
has increased the complexity of the problem and thus very
difficult to apply in practice.
A different approach proposes the automated recovery
when a WSC falls into the failure state (a Web service could
not be accessed or unsatisfied the user requirement) [20].
With this approach, we have to have a full composition
schema described in BPEL [21] language, which is trans-
formed into a Labelled Transition System (LTS), monitored
by a monitor automata. When an error arises (a state that
cannot be reached, corresponding to a Web service cannot
be accessed), the system will start calculating to choose the
recovery plan using the genetic algorithm. The difference
between [20] and [16] is that the size of gene in [20] is
unfixed, which depends on the number of back-tracking steps
from the error state.
6.1.3 Web service verification
As discussed, most of current researches of Web service ver-
ification only verify separately hard or soft constraints of the
services. WS-Engineer [22] is typical work for the Web ser-
vice verification based on the functional properties. A recent
study carried out to verify combined functional and non-
functional requirements of WSC is introduced as VeriWS [5],
which takes in a full composition schema expressed in BPEL
and uses the model checker to verify.
6.2 Web service indexing
The number of web services is increasing rapidly. That makes
the Web service composition approaches become more com-
plex and face many difficulties. Therefore, the Web service
indexing was suggested to support Web service accessing
more efficient. This issue has received the attention of many
researchers.
Aiello et al. [8] index the Web service repository based
on the services descriptions represented by the WSDL lan-
guage. This approach uses the hash table to implement the
index. The index structure consists of two tables, Partname
Index and Service Index. Partname Index uses a hashtable
to maintain the mapping from each partname into two lists
of service names, namely, in list and out list. The Service
Index utilizes a hashtable that maps a service name into detail
information of the correspondent service. The information is
request partnames, and response partnames. The study in [8]
was implemented as the VitaLab system which performs the
indexing of a large collection of WSDL service description
following a semantic description of operations (given as a
tree of “is-a” relations) and, given a request for a service,
composes the available services to satisfy the request.
Zhou et al. [15] proposed the way by which inverted
indexing can be used for fast discovery of Web services.
The indexing mechanisms can be either inverted indexing or
latent semantic indexing. Here, inverted index can be used
as a measure to check OWL-S description contain the given
term. Each keyword is connected to a list of document ids,
in which keyword occurs.
Czyszczo and Aleksander in [9] proposed the solution
for the problem of Web service retrieval by presenting a
new approach to indexing of both SOAP and RESTful Web
services. This approach uses index structure called para-
metric index that allows users to retrieve ranked results in
accordance with specific parameters. The parameters refer to
service’s integral components and are covered in presented
formal definition of a Web service. Second, the services are
123
Vietnam J Comput Sci (2017) 4:111–126 125
Table 8 Comparison on some
of Web service composition and
verification tools
Tool Composition Verification Hard const. Soft const. Temporal Input
OWL-S-XPlan X X OWL-S
PORSCE II X X OWL-S
WS-Engineer X X BPEL
AgFlow X X Statechart
VeriWS X X X X BPEL
WSCOVER X X X X X OWL-S
modelled in vector space that allows the evaluation of their
mutual relevance and enables obtaining ranked search results.
To reduce the index size and to decrease the search time,
the approach in [9] uses the method of conceptual indexing
which groups relevant service components into concepts.
6.3 Evaluation and comparison of our approach with
other studies
Table 8 presents the functional comparison our tool with
others previously discussed. As observed, WSCOVER can
perform both composition and verification at the same time
and on-the-fly. Our tool composes and verifies a composite
Web service on all kinds of constraints, hard and soft con-
straint, and also the temporal relations between component
Web services.
To support model checking for composition and verifica-
tion of Web services against a pre-defined goal in an effective
manner, our work suggested representing a repository of
Web services as a mathematical model, based on Labelled
Transition System (LTS), known as LTS for Web Services
(LTS4WS). Some other works, like the VeriWS tool [5], also
propose using LTS models for enabling the formal verifica-
tion of a WSC composition. However, our work distinguishes
to this work as follows:
• In [5], the LTS model is rebuilt when we consider new
composition goal, even though the repository remains the
same. In contrast, our LTS4WS model can be applied for
several various goals without being rebuilt.
• The work in [5] only verifies the composite Web service,
it does not perform the composition phase. Meanwhile,
our approach combines composition and verification at
the same time.
• We apply the heuristic search to model checking engine
based on the characteristics of Web service, so the veri-
fication performance is improved significantly.
• We also apply the bitwise-based indexing technique to
index the Web service repository. This approach helps
us to retrieve the Web services further faster and more
reasonably. To the best of our knowledge, it is the first
work that combines formal verification with indexing
techniques in the area of Web services processing.
7 Conclusion and future work
The tool WSCOVER, developed in this research, has offered
several useful functions that the other similar works do not
support, including the capability of composing and verify-
ing Web services, in an on-the-fly manner; and extending the
model checker by applying the heuristics specifying the Web
service nature. In addition, also through this paper, we have
some contributions about the formal representation of Web
service; the bitwise-based Web service indexing method to
index the Web service repository using the bitwise opera-
tors. This helps the building of the index table as well as the
retrieval of Web services more efficient.
As a result, WSCOVER can locate a composition solution
faster and more optimally. However, in the future, this effort
also needs to be compared with some other techniques, such
as the clustering approaches to learn more about the pros and
cons of our approach. In addition, in this work, we have not
yet considered the semantic aspect of the features of Web
services. We are going to develop a mechanism to calculate
the similarity between two sets of features when they do not
match completely.
Acknowledgements This research is funded by Vietnam National Uni-
versity HoChiMinh City under Grant Number C2015-20-10.
Open Access This article is distributed under the terms of the Creative
Commons Attribution 4.0 International License (
ons.org/licenses/by/4.0/), which permits unrestricted use, distribution,
and reproduction in any medium, provided you give appropriate credit
to the original author(s) and the source, provide a link to the Creative
Commons license, and indicate if changes were made.
References
1. Yin, R.: Study of composing web service based on soa, In:
Proceedings of the 2nd International Conference on Green Com-
munications and Networks 2012 (GCN 2012), vol. 2, pp. 209–214.
Springer (2013)
123
126 Vietnam J Comput Sci (2017) 4:111–126
2. Rostami, N. H., Kheirkhah, E., Jalali, M.: Web services composi-
tion methods and techniques: a review. Int J Comput Sci Eng Inf
Technol 3(6), 15–29 (2013)
3. Fitting, M.: First-order logic. In: First-order logic and automated
theorem proving, pp. 97–125. Springer, US (1990)
4. Hatzi, O., Vrakas, D., Bassiliades, N., Anagnostopoulos, D., Vla-
havas, I.: The porsce ii framework: using ai planning for automated
semantic web service composition. Knowl Eng Rev 28(02), 137–
156 (2013)
5. Chen, M., Tan, T. H., Sun, J., Liu, Y., Dong, J. S.: Veriws: a tool for
verification of combined functional and non-functional require-
ments of web service composition. In: Proceedings of the 36th
International Conference on Software Engineering. ACM, pp. 564–
567 (2014)
6. Kumara, B.T., Paik, I., Chen, W., Ryu, K.H.: Web service clustering
using a hybrid term-similarity measure with ontology learning. Int
J Web Serv Res (IJWSR) 11(2), 24–45 (2014)
7. Du, Y.Y., Zhang, Y.J., Zhang, X.L.: A semantic approach of service
clustering and web service discovery. Inf Technol J 12(5), 967–974
(2013)
8. Aiello, M., Platzer, C., Rosenberg, F., Tran, H., Vasko, M., Dustdar,
S.: Web service indexing for efficient retrieval and composition.
In: E-Commerce Technology, 2006. The 8th IEEE International
Conference on and Enterprise Computing, E-Commerce, and E-
Services, The 3rd IEEE International Conference on. IEEE, pp.
63–63 (2006)
9. Czyszczon´, A., Zgrzywa, A.: Indexing method for effective web
service retrieval. Int J Intell Inf Database Syst 8(3), 189–208 (2014)
10. Huynh, K. T., Quan, T. T., Bui, T. H.: Fast and formalized:
Heuristics-based on-the-fly web service composition and verifi-
cation. In: Information and Computer Science (NICS), 2015 2nd
National Foundation for Science and Technology Development
Conference on. IEEE, pp. 174–179 (2015)
11. Liu, Y., Sun, J., Dong, J. S.: Developing model checkers using PAT.
In: International symposium on automated technology for verifi-
cation and Analysis, pp. 371–377. Springer, Berlin, Heidelberg
(2010)
12. Fan, G., Yu, H., Chen, L., Liu, D.: Petri net based techniques
for constructing reliable service composition. J Syst Softw 86(4),
1089–1106 (2013)
13. Maung, Y.W.M., Hein, A.A.: Colored petri-nets (cpn) based model
for web services composition. IJCCER 2, 169–172 (2014)
14. Tian, B., Gu, Y.: Formal modeling and verification for web service
composition. J Softw 8(11), 2733–2737 (2013)
15. Zhou, B., Huang, T., Liu, J., Shen, M.: Using inverted index-
ing to semantic web service discovery search model. In: Wire-
less Communications, Networking and Mobile Computing, 2009.
WiCom’09. 5th International Conference on. IEEE, pp. 1–4 (2009)
16. AllamehAmiri, M., Derhami, V., Ghasemzadeh, M.: Qos-based
web service composition based on genetic algorithm. J AI Data
Min 1(2), 63–73 (2013)
17. Klusch, M.: Owls-tc: Owl-s service retrieval test collection, version
2.1. 
18. Burstein, M., Hobbs, J., Lassila, O., Mcdermott, D., Mcilraith, S.,
Narayanan, S., Paolucci, M., Parsia, B., Payne, T., Sirin, E., et al.:
Owl-s: Semantic markup for web services. W3C Member Submis-
sion (2004)
19. Klusch, M., Gerber, A., Schmidt, M.: Semantic web service com-
position planning with owls-xplan. In: Proceedings of the AAAI
Fall Symposium on Semantic Web and Agents. AAAI Press, USA
(2005)
20. Tan, T. H., Chen, M., André, É., Sun, J., Liu,Y., et al.: Automated
runtime recovery for qos-based service composition. In: Proceed-
ings of the 23rd international conference on World wide web.
International World Wide Web Conferences Steering Committee,
pp. 563–574 (2014)
21. Jordan, D., Evdemon, J., Alves et al.: Web services business process
execution language version 2.0. OASIS Stand 11, 10 (2007)
22. Foster, H., Uchitel, S., Magee, J., Kramer, J.: Wsengineer: A
model-based approach to engineering web service compositions
and choreography. In: Test and analysis of web services, pp. 87–
103. Springer, Berlin, Heidelberg (2007)
123