Can the program determine the frequency of the CPU or is it impossible?
In these days of superscalar, multicore, virtualisation, power scaling, managed operating systems, and so on, what does "CPU frequency" even mean? 

Note that it may be possible for Alice to convince Bob that she has compute power capable of performing X operations of a known type in a given time, as you find in a proof-of-work system. If it is a problem for which parallel algorithms are believed not to be feasible, he may be convinced that it happened on a single compute device, and not (say) a cloud or cluster.

But for all Bob knows, Alice may have an asynchronous device which doesn't even have a clock speed.