Firewalls are crucial elements to enhance network security by examining the field value of every packet and decide whether to accept or discard the packet according to the firewall policy. However, the design of firewall policies, especially for enterprise networks, is complex and error‐prone. This paper aims to propose an effective firewall design method to ensure the consistency, compactness and completeness of firewall rules. Specifically, we develop a new designing model, namely firewall design matrix, and the corresponding construction algorithm for mapping firewall rules to firewall design matrix. A firewall generation algorithm is proposed to generate the target firewall rules that are equivalent to the original ones while maintaining the completeness. Theoretical proof and extensive experiments on both real‐world and synthetic firewalls are conducted to evaluate the performance of the proposed method. The results demonstrate that it can achieve a high compression ratio efficiently while maintaining the firewall rules conflict‐free. Copyright © 2013 John Wiley & Sons, Ltd.