That's not quite enough. The kernel and associated device drivers are also "interfaces" that a program binary invokes, so all the kernel code paths triggered by the program calling into the kernel should be inspected too.

That said pretty sure the GP hasn't had a deep dive into whether say the C library or Linux kernel has some funny O(n^4) stuff happening.