In recent years, the focus on validating the statistical methods used in the field of neuroimaging has increased. While several papers have already highlighted the importance of non-parametric methods and especially permutation testing for general linear models (GLMs), it seems like the importance of validating classification results other than through cross-validation has taken a back seat. But classification, especially binary classification, is one of the most common tools in neuroimaging. Often permutations are not performed using the argument that they are too computationally expensive, especially for trainingintensive classifier as e.g. neural networks. In the following we want to re-visit the use of permutation tests for validating cross-validation results statistically and employ recent approximate permutation methods that reduce the number of permutations that need to be performed. We evaluate the feasibility of using full as well as approximate permutation methods in the extreme cases of small and unbalanced data sets. Our results indicate the applicability of a tail and Gamma approximation to perform permutation testing for binary classification tasks.