Measuring code coverage on object code (binary executable)

There are many tools to measure the thoroughness of testing for programs written in various languages, whether it's a mere statement coverage or a fancier MC/DC coverage. I wonder, however, if there's any tool that can measure the coverage directly on a machine-executable object code (preferably on x86). What if the source code is not available (as in COTS) while I still want to test the black-box myself and ensure the quality of it?

My preference is

1. Non-proprietary / open-source
2. Easily extendable.

I heard that a dynamic binary analysis instrumentation tool like PIN might do the job, but wasn't sure if it would worth the trial if there already is a tool available.

I appreciate any suggestion.