I find fuzzing a bit to basic method if it comes to black box apps. I am specifically interested how to find a vulnerability in network protocols. I have read "Attacking Network Protocols" but only fuzzing was discussed.
On a pure black box where all you have is input and output, you would have to fuzz it.
If all you had was an obscured executable file, which executed on a remote system available only by an API, that would be the closest you could really get to a pure black box test. For something like that fuzzing is the entry point.
Once you fuzzed you may find an error indicating input is being filtered for usage in a relational database. You may learn input limits, restricted words, rate limiting, etc.
It all starts with fuzzing.