At a minimum $P(x)$ must be primitive and $f:\{0,1\}^n
\rightarrow \{0,1\}$ must be highly nonlinear and resilient of high order (correlation immune of high order plus balanced) are necessary conditions.
- Nonlinearity (minimal Hamming distance of the truth table of the boolean function from affine functions), must be high for resisting linear/affine approximation attacks. This is computed via the fast Walsh-Hadamard transform.
There is a more recent class of attacks which are resisted by functions $f$ with high algebraic immunity denoted $AI(f)$. Denote the state update mapping corresponding to the polynomial $P$ by $L:\{0,1\}^n\rightarrow \{0,1\}^n$ and note that the output bit $s_t$ is given by its $t-$fold composition where $x_0$ is the initial state of the LFSR, usually chosen randomly by using the secret key.
$$
s_t=L(L(\cdots L(x_0))):=L^t(x_0).
$$
The keystream $(s_t)$ is vulnerable to attacks if there are
relations of low degree between the keystream bits and bits of the state. These relations can exist even when the algebraic degree of $f$ is high.
Such relations correspond to low degree multiples of $f$, i.e.,
$$
g(x)f(x)=h(x)
$$
where we can find a polynomial $g(x)$ such that $h(x)$ has low degree. It turns out this is equivalent to the existence of a low degree annihilator of $f$ or $1+f$ and $f$ is said to have a high algebraic immunity if no low degree annihilator of $f$ or $1+f$ exists.
See Anne Canteaut's paper for details and some references here.
