There is no one-size-fits-all protocol for this. It really depends on what kind of adversary you believe you are dealing with.
Either way, the first step is the same: don't panic, take a deep breath, and thoroughly consider your threat model, your options and goals. Do you really want to wipe the device? This can potentially destroy evidence that may be relevant in a future investigation. If you can afford it, you may want to isolate the device and have a professional perform forensics on your device to figure out what kind of backdoor you have and to preserve any evidence.
If this is not viable, the next question would be how thorough you want to be. There are more places than initially obvious where a backdoor can persist, although the more sophisticated ones are rather uncommon. This is where considering your threat model is really important. What kind of sophistication are you expecting? Is this some run-off-the-mill bootkit malware or are you facing a state-level actor (most people aren't the target of TAO attacks or the like, and if you think you are, but then there may be better places to get advice ;).
So let's go through some of the places where a backdoor might be installed, from least to most sophisticated (or well, likely to less likely):
- Somewhere on your operating system, i.e. on your HD / SSD. This would be destroyed through a reinstallation of your OS. While you claim that a reinstallation does not remove your backdoor, it is still prudent to reinstall the operating system, as a more sophisticated backdoor may persist here too.
- The boot loader. This depends a bit on whether you are using UEFI or a CSM / legacy BIOS bootloader. In both cases, the boot loader is stored on your disk, but it could either be inside the EFI system partition or in the first few sectors of the disk (MBR). In either case, it could be removed by completely wiping the disk.
- The BIOS / UEFI state, e.g. in UEFI variables or BIOS configuration. In either case, this is stored in a small flash chip or EEPROM on your mainboard. How this is completely cleared depends on your hardware - this could be as easy as removing a CMOS battery or could require clipping a cable to a chip on your mainboard.
- The BIOS / UEFI firmware, ME or other CPU / Mainboard firmware. Whether this can get cleared by a firmware reflash depends on the device - if you can't trust your computer to power up though, the only safe bet may be to connect a programming cable to the respective flash chips.
- Other peripheral firmware, e.g. the hard-drive or SSD controllers or network card firmware. Many peripherals have small CPUs on them that can be reprogrammed, and whether or how these can be restored again depends on your device. PCI devices can have so-called boot ROMs that get executed on the main CPU prior to system boot, and could backdoor later boot stages. How these get programmed again depends on the device in question.
- Potential hardware modifications - these may be very hard to spot and difficult to get rid of.
When wiping the disk, consider that you may not want to do this using the possibly compromised device. You may want to remove the disk, and attach it to a second computer without mounting it, and then overwriting it e.g. using
dd. If your device is an SSD with Secure Erase capabilities, you can also use those. This should remove any persistent malware on the disk, but not necessarily more sophisticated backdoors on the disk controller or other firmware.
Finally, the most paranoid option is to consider the device burned, power it off and don't use it anymore - although this is probably not within everyday joe's threat model.