We present a new algorithm for upper bounding the maximum average linear hull probability for SPNs, a value required to determine provable security against linear cryptanalysis. The best previous result (Hong et al. [9]) applies only when the linear transformation branch number (B) is M or (M + 1) (maximal case), where M is the number of s-boxes per round. In contrast, our upper bound can be computed for any value of B. Moreover, the new upper bound is a function of the number of rounds (other upper bounds known to the authors are not). When B = M, our upper bound is consistently superior to [9]. When B = (M + 1), our upper bound does not appear to improve on [9]. On application to Rijndael (128-bit block size, 10 rounds), we obtain the upper bound UB = 2⁻⁷⁵, corresponding to a lower bound on the data complexity of $ \frac{8} {{UB}} = {\text{2}}^{{\text{78}}} $ \frac{8} {{UB}} = {\text{2}}^{{\text{78}}} (for 96.7% success rate). Note that this does not demonstrate the existence of a such an attack, but is, to our knowledge, the first such lower bound.