Middleboxes are typically hardware-accelerated appliances such as firewalls, Proxies, WAN optimizers, and NATs that play an important role in service provisioning over today's Data Centers. We focus on the placement of virtualised security services in multi-tenant Data Centers. Customised security services are provided to tenants as software VNF modules collocated with switches in the network. Our placement formulation satisfies the allocation constraints while maintaining efficient management of the infrastructure resources. We propose a Constraint Programming (CP) formulation and a CPLEX implementation. We also formulate a heuristic-based algorithm to solve larger instances of the placement problem. Extensive evaluation of the algorithms has been conducted, demonstrating that the VNF approach provides more than 50% reduction in resource consumption compared to other heuristic algorithms.