With sufficiently robust and constrained permissions, it wouldn't be out of the realm of possibility to offload the process to trusted third parties. If I could subscribe to Consumer Reports App Review, which was an app that itself was given some access to see binary signatures of installed applications, a robust third party review ecosystem could develop.
If applications were also given the capability to subscribe minimally to resources they require (e.g. this app will access foo.example.com, and bar.example.com, and otherwise interact with registered sharing handlers through the OS), etc, we could be a lot more assured of an application not secretly spiriting away our data, at least if we cared to pay attention.
Alas, neither app store is willing to throw away the billions of dollars in app sales they make, so while we might get more granular permissions over time, we'll likely never be allowed out of our walled gardens. "For our own good", of course.