© Springer International Publishing Switzerland 2015. This paper discusses how Sybil attacks can undermine trust management systems and how to respond to these attacks using advanced techniques such as credibility and probabilistic databases. In such attacks end-users have purposely different identities and hence, can provide inconsistent ratings over the same Web Services. Many existing approaches rely on arbitrary choices to filter out Sybil users and reduce their attack capabilities. However this turns out inefficient. Our approach relies on non-Sybil credible users who provide consistent ratings over Web services and hence, can be trusted. To establish these ratings and debunk Sybil users techniques such as fuzzy-clustering, graph search, and probabilistic databases are adopted. A series of experiments are carried out to demonstrate robustness of our trust approach in presence of Sybil attacks.