Network services are a critical component of today's networks. They apply critical functions (e.g. security, routing or quality of service) to traffic to enhance the network operators and application consumers experience. Today these services are inserted physically on the data-forwarding plane without providing much flexibility to deal with different traffic types or affiliations. Cloud Computing, however, demands policy enforcement on a per-Provider, per-Service and/or per-Tenant basis. In addition, there is an increasing need for dynamic transparent network chaining independent of the underlying transport infrastructure. We first introduce the concept of Universal Cloud Classification as a Service (UCCaaS). Followed by highlighting how it can be leveraged in conjunction with Network Service Headers (NSH) to address above challenges. UCC provides an addressing scheme to isolate traffic streams on a per-provider, per-service and/or per-tenant basis. To enable bi-directional policy enforcement in network functions we extend the UCC proposal by adding source and destination support. NSH is a way to steer network traffic dynamically across a set of network functions. We demonstrate the feasibility and advantages of our UCCaaS + NSH proposal with an example application, where a service chain defines Access Control Lists and traffic rate limiting on a per-Service and per-Tenant basis. Our proposal opens a door for a wide range of cloud-aware network services and functions.