Sounds horrible! I shouldn't have to give them my address book to find out if whomever is calling me is a spammer. I wonder what they're doing with the data? Also, phone numbers change hands. What happens when my friend John Doe changes his number and it goes to a spammer? Do I suddenly get marked somehow as being associated with spammers?

I think it does not come from your address book. Rather, it builds the database from each one of us who register with truecaller with thier numbers. So for example: I register with my phone number 123456789, and you register with your phone number 987654321. Both these numbers would be stored on Truecaller's servers and when you get a call from my number 123456789, and even if you don't have my phone number in your phonebook, you still get to see that I am calling you with my name (the details come from the server). You need Wifi/data connection to get truecaller working. That's my understanding , unless I am utterly wrong.