In this paper, we study the immunity of Boolean functions against probabilistic algebraic attacks. We first show that there are functions, using as filters in a linear feedback shift register based nonlinear filter generator, such that probabilistic algebraic attacks outperform deterministic ones. Then we introduce two notions, algebraic immunity distance and
-error algebraic immunity, to measure the ability of Boolean functions resistant to probabilistic algebraic attacks. We analyze both lower and upper bounds on algebraic immunity distance, and also present the relations among algebraic immunity distance,
-error algebraic immunity, algebraic immunity and high order nonlinearity.