To analyze the robustness of network anomaly detection systems, we introduce a new class of polymorphic attacks, called polymorphic blending attacks (PBA). PBA can effectively evade a payload-based network anomaly IDS by carefully matching the statistics of the mutated attack instances to the normal profile. We present a formal framework for the analysis of PBA. We show that in general, generating a PBA that optimally matches the normal traffic profile is a hard problem (NP-complete). However, the problem of finding a PBA can be reduced to the SAT or ILP problems so that solvers available in those domains can be used to find a near-optimal solution. We also present a heuristic (hill-climbing) to find an approximate solution. We have experimented with our framework using the PAYL 1-gram and 2-gram anomaly detection system, and demonstrate that these attacks are indeed feasible. We provide some insight into possible countermeasures that can be used as defense against PBA.