Anomaly detection when monitoring a large number of units is essential in a variety of applications, ranging from epidemiological studies to monitoring of complex systems.  In this work we take a distribution-free stance and introduce permutation and rank-based variants of the higher criticism test that do not require knowledge of the null distributions for proper calibration.  This results in exact tests in finite samples.  Furthermore, the rank-based approach is appropriate to use when each unit is associated with observations with a rather diverse nature.  We show under what conditions these methodologies are able to detect the presence of sparse anomalies.  For the rank-based test these conditions are stated in a general, non-parametric manner, and depend solely on the probabilities of anomalous observations exceeding nominal observations.  The analysis requires a refined understanding of the distribution of the ranks under the presence of anomalies, and in particular of the rank-induced dependencies.  Within the exponential family and a family of convolutional models, we analytically quantify the asymptotic performance of our methodologies and obtain phase-transitions reminiscent of those for detection of sparse heteroskedastic Gaussian mixtures.  As the proposed test itself does not rely on asymptotic approximations it typically performs better than other variants of higher criticism relying on such approximations (based on a collaboration with Ivo Stoepker and Ery Arias-Castro)