The stateful firewall is a new type of firewall, and the traditional firewall decision diagrams (FDD) construction algorithm does not apply to stateful firewall rule set. This paper presented a stateful firewall decision diagrams (SFDD) construction algorithm, which transforms the stateful firewall ACLs into equivalent stateful firewall decision diagrams, and is applied to the stateful firewall rule set comparison. Theoretical analysis and simulation results have shown that the method can effectively detect all the differences between the rule sets. And when the number of rules for both the stateful and stateless section is 3000, the time cost is less than 2 s.