Network protocol implementations are susceptible to problems caused by their lack of ability to handle invalid inputs. We present ASPIRE: Automated Systematic Protocol Implementation Robustness Evaluation, an automated approach to pro-actively test protocol implementations by observing their responses to faulty Protocol Data Units (PDUs) or messages. In contrast to existing approaches, we sample the faulty PDU space in a systematic manner, thus allowing us to evaluate protocol implementations in the face of a wider variety of faulty PDUs. We use a pruning strategy to reduce, from exponential, the size of the faulty PDU set to polynomial in the number of fields of a PDU. We have implemented the ASPIRE algorithms and evaluated them on implementations of HTTP (Apache, Google Web Server (GWS), and Microsoft IIS) and SMTP (Sendmail and Microsoft Exchange) protocols. Our results show that Apache, GWS, and IIS, although implementing the same protocol specification, behave differently on faulty HTTP PDUs; Sendmail and Exchange are different in handling our faulty SMTP PDUs.