Abstarct: Web Application Firewalls (WAFs) are responsible for the safety of numerous web applications that are brutally under attack. Due to the increasing sophistication of web attacks, WAFs have to be tested and updated regularly to resist the relentless flow of web attacks. In practice, using a brute-force attack to discover vulnerabilities is infeasible due to the wide variety of attack patterns. Thus, various black-box testing techniques have been proposed to provide a practical solution. However, these techniques are not mature enough and suffer from low efficiency. In this paper, we present an automated black-box testing strategy to discover injection vulnerabilities in WAFs. In particular, we focus on SQL injection and Cross-site scxripting (XSS), which have been among the top ten vulnerabilities over the past decade. In our proposed method, in the very first phase, an n-gram is used to decompose attack payloads into string fragments. Then, skip-gram is utilized to transform fragments into numerical vectors to cluster them in the next step using hierarchical clustering. In the last step, attack payloads are clustered using fragment clusters and autoencoder. In the second phase, first, non-informative fragments are removed in each cluster using entropy. Then, a weight is calculated for each fragment using Inverse-Document-Frequency (IDF) to form the final feature vectors. In the last phase, test oracle searches for bypassing payloads in two parallel steps: inter-cluster search and intra-cluster search. The inter-cluster search aims to discover clusters that include bypassing payloads using an e-greedy policy. Simultaneously, the intra-cluster search algorithm tries to discover bypassing payloads inside a selected cluster using Term-Frequency-Inverse-Document-Frequency (TF-IDF). In this research, the proposed method is compared to three state-of-the-art methods, namely ML-Driven E, ART4SQLi, and XSSART, using two datasets containing 2417720 and 1798062 SQLi and XSS payloads, respectively. Results show that the proposed method discovers an average of 33.53% more vulnerabilities than ML-Driven E. Moreover, on average, the proposed method consumes 63.16% fewer HTTP requests than ART4SQLi and XSSART before discovering the first bypassing payload.