Shamir Interpolation Problem (Recovering secret with fewer parts than the threshold)
I have picked all combinations $C^p_2$ and $C^p_3$ of $(x, (fx))$ to all polynomials $ a_3x^3 + a_2x^2 + a_1x + a0$ where  $\{a_3, a_2, a_1, a_0\} \in Z_{5}, Z_{7}$ and $a_3 &gt; 0$. I can always recover the secret using less points than the threshold.


From your comments, it sounds like when you say "I can always recover the secret" what you mean is that there is some subset of shares that results in the correct secret. Not that all subsets of shares always reveals the correct secret.

That is the expected behavior. Under the typical usage of Shamir secret sharing, a subset of fewer than the threshold can use their shares to try to recover a secret, but they will have no idea if they are correct, and their probability of being correct is no better than random guessing.

You said in a comment that "if you consider that the Dealer can be malicious". Shamir never claimed (or proved) the scheme to be secure in the presence of a malicious dealer. For that threat model, you would have to use other schemes.