It's a "the NSA wanted to have that for their own internal use” kind of scenario.

I have no concerns about it.

• It is well-known.
• It is completely open.
• It has been in wide use for decades.
• In that time, there has never been a reason to believe it's malicious.
• It is not an encryption tool, but an add-on for denying actions that would otherwise be allowed.

It's not unusual for US government agencies to develop or fund technologies that end up used by the whole world. The internet is another example.

If you're in the position that the NSA is in your system trying to bypass SELinux, you have much bigger problems.

Besides, in that case, having it disabled is going to make it easier for them anyway.

One question and some unfollowable advice.

Question: Why not use AppArmor? My understanding is that's what Debian uses by default instead of Selinux which is more native to Enterprise Linux (Fedora, RHEL, Rocky, Alma etc).

Unfollowable advice: As an EL admin where it's the default and very closely integrated, we have a saying; "It's not always dns, mostly it's Selinux". For most distro-sourced software, it's fine. But if you install software from other sources, you're going to hit problems.

Others have given good reasons to your specific questions, but one tip if you go down this route. We use a redhat tool, "setroubleshoot-server" which helps hugely in both identifying when something isn't working because SELinux has blocked it, but also gives you the commands to add an explicit rule to allow it, so you can view the log, understand why it's blocking, and allow it without needing to get too involved with the complicated file contexts.

Sadly, it looks like this tool isn't available in Debian, which would seem to make like a lot harder using selinux. Familiar as I am with selinux, I don't run it on my personal servers or this laptop, which are Debian.

SELinux has been GPL for 24 years.

It's part of what was called Rainbow Books, but is known more widely these days as the Common Criteria.
https://en.wikipedia.org/wiki/Common_Criteria

It's the "Government setting standards" sort of scenario.

It’s worth noting that SE Linux takes considerable knowledge to administer correctly in many scenarios, and can lead to some strange problems if you don’t know what you’re doing. Definitely worth learning about, though.