Serpent is a block cipher which was suggested as a candidate for the advanced encryption standard (AES). Several recently proposed ciphers are built with layers of small S-boxes, interconnected by linear key-dependent layers. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an over defined system of algebraic equations. We study general methods known for solving over defined systems of equations, such as XLS. Then we introduce a new method called XSL-A that uses the sparsity of the equations and their specific structure.