Is it possible to test implementation for side-channel attacks? When it comes to implementing cryptographic algorithms, there seems to be a big focus on the difficulty of doing so without introducing the potential for side channel attacks and the knowledge required.

Along with that seems to go the assumption that such code needs to be very carefully written and reviewed but I haven't found much in regards to testing.

Now of course it's hard to test in software whether an implementation is vulnerable against some side channel attacks but it seems to me that it should be possible for timing and maybe even cache based attacks.

Is that actually possible and where can I find information on that topic?

In particular I imagine one could observe how an implementation performs under random inputs and use CPU performance counters to monitor instruction counts and cache misses. Differences here for different inputs would probably be bad. At least for compiled languages it should also be possible to have tools that perform static analysis on machine code, shouldn't it?
At least for compiled languages it should also be possible to have
  tools that perform static analysis on machine code, shouldn't it?


Indeed, such tools exist. There are companies specialized in this domain which provide this kind of tools (see this datasheet for example). But you should note that an only software tool will not be able to detect all weaknesses against certain types of attacks (e.g. some fault injections).


  it should be possible for timing and maybe even cache based attacks


There is also CacheAudit which is a tool for the static analysis of cache side channels (plus, it's free). It can be configured to test your implementation against several architectures (e.g. separate or shared cache for data and instructions) and several attack models. Here is the description of the framework and you can download it here. To put it in a nutshell:


  CacheAudit takes as input a program binary  and  a  cache 
  configuration  and  delivers  formal  security  guarantees  that 
  cover  all  possible  executions  of the corresponding system.