Abstract: In this paper, based on comprehensive analysis of various service composition methods, we present a hierarchical structure on service composition framework and an approach to compose services automatically by using backward tree. Finally we build a ground model for dynamic service composition in pervasive computing based on ASM, then refine and verify the model by CoreASM tool.