FLOYD, Circuit Judge.

Appellant Richard Lee Adams (Adams) challenges his conviction for being a felon in possession of a firearm in violation of 18 U.S.C. § 922(g). Adams argues that he is actually innocent of the § 922(g) offense because he was not, at the time of the offense, a convicted felon. We agree and accordingly vacate his conviction and direct entry of judgment in his favor.

I.

On January 2, 2008, a grand jury returned an eight count indictment against Adams alleging that he committed a series of armed robberies of convenience stores. In May 2009, Adams pleaded guilty pursuant to a written plea agreement to three of the eight counts: (1) robbery in violation of 18 U.S.C. § 1951 (Count 2); (2) using and carrying a firearm during a crime of violence in violation of 18 U.S.C. § 924(c) (Count 3); and (3) being a felon in possession of a firearm in violation of 18 U.S.C. § 922(g) (Count 8). The plea agreement contained a provision in which Adams waived his right to challenge his conviction or sentence in a motion pursuant to 28 U.S.C. § 2255 unless he did so on the basis of ineffective assistance of counsel or prosecutorial misconduct. Before accepting Adams's guilty plea, the district court held a colloquy pursuant to Federal Rule of Criminal Procedure 11. The district court singled out the waiver provision "in particular" and read it to Adams. J.A. 50. Adams indicated that he understood the appellate and collateral attack rights he was giving up as part of his plea agreement. In exchange for the concessions made by Adams in the plea agreement, the government agreed to dismiss the remaining five counts of the indictment relating to other armed robberies.

The district court held a sentencing hearing on October 23, 2009. Based on a total offense level of 23 and a criminal history category of IV, the district court determined the Sentencing Guidelines range as to Counts 2 and 8 to be 70 to 87 months imprisonment and as to Count 3 to be 120 months imprisonment to run consecutively with any term of imprisonment imposed with regard to Counts 2 and 8.

After a motion by the government, the court departed upward at sentencing. The district court sentenced Adams to a term of imprisonment of 120 months as to Counts 2 and 8 to run concurrently and a sentence of 120 months as to Count 3 to run consecutively to the sentences imposed in Counts 2 and 8. Adams's total sentence was, therefore, 240 months imprisonment. The court detailed its rationale for the upward departure in a written order issued on October 30, 2009. Adams appealed his sentence. This Court affirmed both his conviction and his sentence on January 3, 2011. United States v. Adams, 416 Fed.Appx. 233 (4th Cir.2011).

On August 28, 2012, Adams filed a motion pursuant to 28 U.S.C. § 2255 to vacate his § 922(g) conviction as a felon in possession of a firearm. Adams argued that none of his prior convictions—all of which were under North Carolina law—were felonies after our decision in United States v. Simmons, 649 F.3d 237 (4th Cir.2011) (overruling United States v. Harp, 406 F.3d 242 (4th Cir.2005)), and that he was, therefore, actually innocent of being a fellon on in possession of a firearm. In Simmons, we held that for an offense to be a prior felony under North Carolina's Structured Sentencing Act as then written, a defendant must have actually faced the possibility of more than a year in prison. 649 F.3d at 244-45. In other words, the government could not rely on hypothetical enhancements to determine the maximum term of imprisonment. Id. at 248-49. Adams further alleged that his attorneys were ineffective for failing to anticipate our ruling in Simmons.

The district court issued an order dismissing Adams's § 2255 motion on July 1, 2013. The court determined that the substantive Simmons-related claims Adams presented were barred by the waiver in his plea agreement. The court also determined that Adams suffered no prejudice from any Simmons-related error because even if his § 922(g) conviction were vacated, Adams would still be required to serve a sentence of 240 months in prison.1 With respect to Adams's ineffective assistance of counsel claims, the district court determined that Adams's attorneys were not ineffective for counselling him in then-applicable law. Further, the court again noted that it would have issued the same sentence even had Simmons applied, so Adams could not make the requisite showing of prejudice. The district court denied a certificate of appealability. Adams appealed nonetheless.

This Court granted Adams a certificate of appealability on the issue of whether Adams's waiver in his plea agreement barred consideration of his claim that Simmons rendered him actually innocent of the § 922(g) conviction. We conclude that Adams's claim of actual innocence is outside the scope of the appellate waiver, and, for the reasons explained below, we also conclude that Adams is indeed actually innocent.

II.

A.

We first examine whether Adams entered a valid waiver. The validity of a waiver of appeal and collateral attack rights is reviewed de novo, and we will enforce the waiver if it is valid and the issue appealed is within the scope of the waiver. United States v. Copeland, 707 F.3d 522, 529 (4th Cir.2013). A waiver must be knowing and voluntary. United States v. Lemaster, 403 F.3d 216, 220 (4th Cir.2005). In the absence of extraordinary circumstances, a properly conducted Rule 11 colloquy establishes the validity of the waiver. Id. at 221. Here, neither party argues that Adams's waiver was invalid, and there is no evidence in the record to support such a conclusion. Rather, the issue is whether Adams's Simmons-based claim is within the scope of the valid waiver in his plea agreement.

We have previously held that a Simmons-based challenge to a sentence falls within the scope of a valid appeal waiver. Copeland, 707 F.3d at 529-30. A waiver remains valid even "in light of a subsequent change in the law." Id. at 529 (citing United States v. Blick, 408 F.3d 162 (4th Cir.2005)).

Copeland, however, does not render all collateral challenges automatically within the scope of a valid waiver merely because such a challenge invokes Simmons. We will refuse to enforce an otherwise valid waiver if to do so would result in a miscarriage of justice. United States v. Johnson, 410 F.3d 137, 151 (4th Cir.2005). "A proper showing of `actual innocence' is sufficient to satisfy the `miscarriage of justice' requirement." Wolfe v. Johnson, 565 F.3d 140, 160 (4th Cir.2009) (explaining the meaning of "miscarriage of justice" in the context of procedural default). Such a showing renders the claim outside the scope of the waiver. Thus, if we determine that Adams has made a cognizable claim of actual innocence, Adams's § 2255 motion falls outside the scope of his waiver.

Miller v. United States, 735 F.3d 141 (4th Cir.2013)—a case cited by neither party—settles the key issue in this case: whether Adams properly alleges that he is actually innocent of the § 922(g) conviction. In Miller, a defendant filed a § 2255 petition claiming that his § 922(g) conviction should be vacated because, after Simmons, his predicate North Carolina convictions were no longer felonies. We agreed and ordered the district court to grant Miller's § 2255 motion, holding that Simmons announced a substantive rule retroactively applicable. Miller, 735 F.3d at 145-46. We concluded:

Id. at 146 (emphasis added). Adams makes exactly the same claim as Miller; like Miller, Adams makes a valid claim of actual innocence. Therefore, in keeping with our precedent and to prevent a miscarriage of justice, we conclude Adams's claim is outside the scope of his appeal waiver. The district court erred in dismissing Adams's claim as barred by the waiver provision in the plea agreement.

B.

Having determined that Adams's actual innocence claim is outside the scope of his appeal waiver, we reach the merits of his § 2255 motion. The government makes two arguments against Adams's claim of actual innocence, both of which rely on the Supreme Court's decision in Bousley v. United States, 523 U.S. 614, 118 S.Ct. 1604, 140 L.Ed.2d 828 (1998). First, the government contends that although Adams may have shown "legal innocence" he has not shown "factual innocence." Second, the government contends that Adams had not shown that he is also actually innocent of the conduct alleged in the five dismissed counts of the indictment.

In Bousley the Supreme Court observed that actual innocence "means factual innocence, not mere legal insufficiency." Id. at 623, 118 S.Ct. 1604. The government contends that although Adams may no longer be legally convicted of a violation of § 922(g) after Simmons, he remains, nonetheless, somehow still factually guilty.

We find this argument to be without merit. "To show a § 922(g)(1) violation, the government must prove three elements: (i) that the defendant was a convicted felon at the time of the offense; (ii) that he voluntarily and intentionally possessed a firearm; and (iii) that the firearm traveled in interstate commerce at some point." United States v. Gallimore, 247 F.3d 134, 136 (4th Cir.2001) (quotation marks and citation omitted). The government recognizes that Adams lacks the required predicate felony for conviction under § 922(g)(1) following Simmons. Appellee's Br. 10. Under our holding in Simmons, Adams was not a convicted felon at the time of the offense, and it was therefore not a violation of § 922(g)(1) for Adams to be in possession of a firearm. We conclude that Adams has, indeed, shown "factual innocence" as contemplated by Bousley because he has shown that it is impossible for the government to prove one of the required elements of a § 922(g)(1) charge—that the defendant was a convicted felon at the time of the offense. This is so because Adams was "in fact" not a felon.

In addition to requiring a showing of factual innocence, the Supreme Court in Bousley set out an additional requirement: "[i]n cases where the Government has forgone more serious charges in the course of plea bargaining, petitioner's showing of actual innocence must also extend to those charges." 523 U.S. at 624, 118 S.Ct. 1604. The government argues that a showing of factual innocence as to the § 922(g) charge is insufficient to support vacating Adams's conviction. Instead, the government urges us to read the above-quoted language from Bousley to require that Adams show that he is also factually innocent of the charges contained in the five dismissed counts of the indictment.

The facts of Bousley are instructive here and counsel against adoption of the government's reading of the case. In Bousley, Kenneth Bousley pleaded guilty to "using" a firearm in violation of 18 U.S.C. § 924(c)(1). Bousley, 523 U.S. at 616, 118 S.Ct. 1604. After Bousley pleaded guilty, the Supreme Court construed § 924(c)(1)'s "use" prong to require the government to show "active employment of the firearm." Bailey v. United States, 516 U.S. 137, 144, 116 S.Ct. 501, 133 L.Ed.2d 472 (1995). Bousley challenged his conviction via a motion pursuant to § 2255 and alleged that he was actually innocent of "using" a firearm as the Supreme Court had defined "use" in Bailey. Bousley, 523 U.S. at 623, 118 S.Ct. 1604. The government argued before the Supreme Court that Bousley had to show that he was actually innocent of both "using" and of "carrying" a firearm, both violations of § 924(c)(1), in order to show that he was actually innocent of his conviction under that provision. Id. at 624, 118 S.Ct. 1604. Because the indictment charged Bousley only with "using" a firearm and there was no record evidence that the government "elected not to charge" Bousley with "carrying" a firearm in exchange for his plea of guilty, the Supreme Court concluded Bousley needed to "demonstrate no more than that he did not `use' a firearm . . ." as charged in the indictment. Id.

The Supreme Court concerned itself with whether Bousley's conduct violated § 924(c), a statute criminalizing using, carrying, or possessing a firearm in relation to any crime of violence or drug trafficking crime. All of the Supreme Court's analysis related to what Bousley had to show to prove actual innocence of his § 924(c) crime of conviction. In other words, the Court focused on one instance of criminal conduct: whether Bousley violated § 924(c) by using, carrying, or possessing a firearm.

Our decision in Lyons v. Lee, 316 F.3d 528 (4th Cir.2003), employs a similar conduct-based approach. In Lyons we noted that to show actual innocence a defendant convicted of common law robbery after a guilty plea must also show factual innocence of the more serious, original charge of armed robbery. Id. at 533 n. 5. Thus, the actual innocence inquiry in Lyons focused on the underlying criminal conduct of robbery, just as Bousley focused on underlying criminal conduct relating to firearms.

Perhaps the criminal conduct inquiry can best be illustrated by a hypothetical. Consider a defendant who is charged with second-degree murder, a homicide crime, but who later negotiates a plea bargain whereby he pleads guilty to voluntary manslaughter. Under Bousley, if that defendant later wishes to attack his guilty plea to the lesser crime with a claim of actual innocence, he must show that he is factually innocent of the second-degree murder charge as well as the voluntary manslaughter charge to which he pleaded guilty. In other words, a defendant making a claim of actual innocence after a negotiated guilty plea must show that he is factually innocent of the underlying criminal conduct—use of a firearm in Bousley, robbery in Lyon, and homicide in the above hypothetical. Here, the dismissed counts related to separate allegations of different criminal conduct. Neither Bousley nor Lyons nor common sense requires Adams to show that he is actually innocent of other, dissimilar charged conduct in order to show that he is actually innocent of being a felon in possession of a firearm, when he was not, in fact, a convicted felon when he possessed the firearm.

We conclude Adams has made the requisite showing of actual innocence, and we will, therefore, grant his § 2255 motion and vacate his § 922(g) conviction.

III.

Finally, we are compelled to note our concern with the government's suggestion at oral argument and again in briefing after argument, that, if we vacate Adams's § 922(g) conviction because we conclude Adams is actually innocent of the crime of conviction, the government would seek to reinstate the dismissed counts against Adams pursuant to 18 U.S.C. § 3296 and would seek to add at least an additional fifty years to Adams's current sentence of twenty years in prison.2 The government indicated it may seek to add the additional fifty years even though nothing in our opinion today requires the district court to lessen Adams's current sentence of twenty years imprisonment.

Indeed, in the event we reached the holding we reach today, the government asked us to reinstate the dismissed charges of the indictment. Appellee's Br. 26. We decline to do so. The government treads dangerously close to punishing Adams for pursuing what we have ultimately determined to be a meritorious claim of actual innocence. "To punish a person because he has done what the law plainly allows him to do is a due process violation of the most basic sort." United States v. Goodwin, 457 U.S. 368, 372, 102 S.Ct. 2485, 73 L.Ed.2d 74 (1982) (citation and quotation marks omitted).

Just as the criminal justice system must see the guilty convicted and sentenced to a just punishment, so too it must ferret out and vacate improper convictions. Because Adams was not a convicted felon at the time of the charged offense, it was not illegal under § 922(g) for him to possess a firearm. He should not remain convicted of a crime of which he is, under our precedent in Simmons and Miller, actually innocent. We vacate Adams's § 922(g) conviction and its attendant sentence and special assessment. We direct the entry of judgment in favor of Adams on his § 2255 motion without remand.

VACATED.