We demonstrate how to use a tiny domain-specific language for the description of APIs make it possible to perform black-box testing of APIs. Given an API, our testing framework behaves like regular client code and combines functions exported by the API to build elements of the data-types that are exported by the API. Once the API has been systematically exercised, the user can verify that some properties hold at the API level. In the submitted abstract, we use the running example of data-structures APIs, but the very same ideas apply to the smart-fuzzing of security APIs.