Packet filtering plays a critical role in the performance of many network devices such as firewalls, routers and intrusion detection and prevention systems. Tremendous amount of research works on packet classification was proposed to optimize packet filtering. However, most works use deterministic techniques and do not take into consideration the traffic characteristics. Moreover, most packet classifiers give no specific consideration for optimizing early packet rejection (compared with packet acceptance), which is very important for improving firewall performance. In this paper, we are limited to survey firewall early packet rejection techniques. The strengths and limitations of the techniques are discussed. Also, some improvements have been proposed. This work can be the basis to enhance these techniques or for proposing new approaches that provide better firewall performance.