This paper presents a formal approach to specify and verify object-oriented programs written in the `programming to interfaces' paradigm. Besides the methods to be invoked by its clients, an interface also declares a set of abstract function/predicate symbols, together with a set of constraints on these symbols. For each method declared in this interface, a specification template is given using these abstract symbols. A class implementing this interface can give its own definitions to the abstract symbols, as long as all the constraints are satisfied. This class implements all the methods declared in the interface such that the method specification templates declared in the interface are satisfied w.r.t. the definitions of the abstract function symbols in this class. Based on the constraints on the abstract symbols, the client code using interfaces can be specified and verified precisely without knowing what classes implement these interfaces. Given more information about the implementing classes, the specifications of the client code can be specialized into more precise ones without re-verifying the client code. Several commonly used interfaces and their implementations (including Iterator, Observer, Comparable, and Comparator) are used to demonstrate that the approach in this paper is both precise and flexible.