Existing methods for the specification and description of service compositions cannot ensure the correctness of the compositions to be verified and tested. Addressing this problem, we propose an algebraic specification method. A package facility is introduced into the serviceoriented formal specification language SOFIA to support the method. In this approach, various types of entities in a serviceoriented system are specified by a collection of algebraic specification units, and each specifies one type of entities in the system. When multiple services are composited together, based on the algebraic protocol package of these services, on the one hand, the interaction process and semantics of the composite service are abstractly defined so as to form the implementation specification that describes the implementation mode of the service composition. And on the other hand, the external interface and functional semantics of the composite service are abstractly defined so as to form the abstract specification that describes the requirements of the service composition. Based on the dual structure of the implementation specification and the abstract specification, the “implementation” relationship that must be satisfied between the implementation specification and the abstract specification is further defined, and it is proved that satisfying the “implementation” relationship can ensure the correctness of the implementation, thus laying the theoretical foundation of verification and testability of service composition. Finally, a case study demonstrates the abstractness, expressibility and verifiability of using algebraic specification to describe service composition.